Имитационная модель канала коллективного доступа

В предыдущей статье мы оценивали вероятность успешного захвата канала в конкурентном окне.

Имитация процессов передачи и приёма кадра

1.1. В упрощенном виде, процесс передачи кадра по радиолучу (X_i, X_j) может быть представлен, как поведение композиции конечных автоматов, которая изображена на рисунке 1:

Рисунок 1

1.2. Изображённый на рисунке 1 «Таймер» X_i предназначен для определения моментов времени, соответствующих:

1) времени отсрочки начала передачи очередного пакета (кадра);

2) времени завершения передачи;

3) времени ожидания «квитанции».

При этом, поведение этого «таймера» может быть, как детерминировано (при определении момента времени, соответствующего завершению передачи пакета), так и псевдослучайным (при вычислении времени отсрочки начала передачи).

1.3. «Таймер» X_j – определяет момент начала и завершения передачи квитанции, причём поведение этого таймера всегда детерминировано. Следует отметить, что, как «Таймер» X_i, так и «Таймер» X_i, ведут отсчёт интервалов времени в особых условных единицах – «тиках».

Предположительно, один «тик» имитирует интервал времени, соответствующий длительности одного «слота».

1.4. Автомат, который имитирует процесс управления передачей кадра по радиолучу (X_i, X_j) фактически выполняет функции «диспетчера», взаимодействующим со своим «окружением» с помощью следующих сигналов:

1) сигналов S_тр⁽ⁱ⁾ и S_обс⁽ⁱ⁾, обеспечивающих взаимодействие с протоколом «высшего» уровня, который «поставляет» кадры для передачи, причём:

- сигнал S_тр⁽ⁱ⁾ соответствует поступлению очередного требования на передачу кадра;

- сигнал S_обс⁽ⁱ⁾, который соответствует запросу очередного требования на обслуживание, когда предыдущая заявка на обслуживание уже выполнена.

2) сигналов S_T⁽ⁱ⁾ и S_⁽ⁱ⁾, первый из которых определяет тип интервала времени, а именно:

- времени отсрочки передачи пакета;

- времени завершения передачи пакета;

- времени ожидания квитанции,

а второй – S_⁽ⁱ⁾ – завершению отсчёта заданного интервала.

3) сигналов S_прд⁽ⁱ⁾ и S_кв^(j), обеспечивающих имитацию взаимодействия с «приёмной стороной» (автоматом «Управление приёмом в X_j»). При этом сигнал S_прд⁽ⁱ⁾ = 1 оповещает все «станции» X_j о том, что передатчик X_i находится в состоянии передачи. 

4) и, наконец, сигнала S_зан, запрещающего выход в эфир, формируемого «анализатором занятости канала». Данный анализатор представляет собой тривиальный автомат, реализующий булеву функцию (1):

Sзан = A1i Sпрд(1) v A2i Sпрд(2) v . . . v ANi Sпрд(N)

(1)

где

- A_ki (k=1, 2, . . . , N) – элементы матрицы смежности A=║A_ij║, описывающей граф G=(E,Г), соответствующий текущему состоянию сети;

- S_прд^(k) (k=1, 2, . . . , N) – значения сигналов, соответствующих состояниям конкурирующих станций: если конкурент X_k ведёт передачу, то S_прд^(k) =1.

- N – число узлов в сети.

Следует отметить, что функция (1) может быть использована только в том случае, если все узлы сети работают на одной и той же частоте. Если же это условие не выполняется, то функция (1) должна быть дополнена действием (2):

Sпрд(k) : = 0, если Xiwi, Xjwi, но Xkwi

(2)

1.5. Хотя функции (1) и (2) и тривиальны, но, по-видимому, требуют пояснений. Для этого рассмотрим следующий пример. Пусть условия радиослышимости описываются графом, который изображён на рисунке 2:

Рисунок 2

Такому графу будет соответствовать матрица A=║A_ij║, которая представлена на рисунке 3:

	Xi	Xj	Xb	Xc	Xd
Xi	0	1	1	1	1
Xj	1	0	0	1	1
Xb	1	0	0	1	0
Xc	1	1	1	0	1
Xd	0	1	0	1	0

Рисунок 3

Теперь предположим, что на частоту w_i претендуют передатчик X_i и его конкуренты – станции X_b и X_d. Сравнивая пары значений A_ki S_прд^(k), получим картину, представленную на рисунке 4:

	Aki		Sпрд(k)
Xi	0	&	1	= 0
Xj	1	&	0	= 0
Xb	1	&	1	= 1
Xc	1	&	0	= 0
Xd	0	&	1	= 0

Рисунок 4

Это означает, что станция X_i способна уступить канал станции X_b, но никогда не обнаружит каких-либо признаков активности со стороны станции X_d. Но, это - особенность IEEE 802.11 ….

1.6. Поведение автомата «Управление передачей» может быть описано диаграммой состояний, представленной на рисунке 5:

Рисунок 5

Данный автомат может находиться в одном из восьми состояний:

1. St₀ – исходное состояние - ожидание заявки на передачу кадра;
2. St₁ – ожидание освобождения канала;
3. St₂ – запуск таймера, обеспечивающего отсчёт времени отсрочки начала передачи пакета, а также момента времени завершения его передачи;
4. St₃ – ожидание собственного «слота»;
5. St₄ – передача пакета в эфир;
6. St₅ – запуск таймера ожидания квитанции;
7. St₆ – ожидание квитанции;
8. St₇ – оповещение о факте неудачной попытке передачи кадра.

Переходы данного автомата из одного состояния в другое осуществляются под воздействием символов входного алфавита - _i, то есть под воздействием конкретных комбинаций входных сигналов. Эти комбинации приведены в таблице 1:

Таблица 1

Символ входного алфавита	Значения входных сигналов
	Sтр(i)	S(i)	Sкв(i)	Sзан(i)
λ0	0	x	x	x
λ1	1	x	x	x
λ2	x	x	x	1
λ3	x	x	x	0
λ4	x	0	x	0
λ5	x	1	x	x
λ6	x	0	x	x
λ7	x	1	x	x
λ8	x	0	0	0
λ9	x	0	1	0

Рассматривая таблицу 1, нетрудно заметить, что, практически во всех комбинациях _i, большинству значений сигналов поставлен в соответствие знак «×». Это означает, что при рассмотрении условий перехода под воздействием символа _i данный сигнал должен игнорироваться.

Кроме того, условия выполнения некоторых переходов не заданы. Например, в представленной на рисунке 5 диаграмме не определены условия перехода из состояния St₂ в состояние St₃. Это объясняется следующим образом. При построении данной диаграммы считалось, что подобные переходы безусловны (на рисунке 5 такие переходы выделены жирными линиями). Обозначим такие переходы символом *.

1.7. Показанная на рисунке 5 диаграмма состояний может быть формализована и представлена в виде таблицы переходов, которая изображена на рисунке 6:

Состояние	Символы входного алфавита
	λ0	λ1	λ2	λ3	λ4	λ5	λ6	λ7	λ8	λ9	λ*
St0	St0	St1	-	-	-	-	-	-	-	-	-
St1	-	-	St1	St2	-	-	-	-	-	-	-
St2	-	-	-	-	-	-	-	-	-	-	St3
St3	-	-	St1	-	St3	St4	-	-	-	-	-
St4	-	-	-	-	-	-	St4	St5	-	-	-
St5	-	-	-	-	-	-	-	-	-	-	St6
St6	-	-	St7	-	-	-	-	St7	St6	St0
St7	-	-	-	-	-	-	-	-	-	-	St0

Рисунок 6

Такое представление изучаемого процесса достаточно удобно для его имитации.

1.8. Реакции автомата на входные сигналы представляются в виде выходного алфавита, каждый символ которого - µ_k, соответствует конкретной комбинации выходных сигналов. Перечень всех возможных комбинаций µ_k может быть оформлен в виде таблицы выходов, в данном случае – таблицы 2:

Таблица 2

Символ выходного алфавита	Значения выходных сигналов
	Sобс(i)	ST(i)	Sпрд(i)
µ0	Sобс(i)=1- запрос очередного кадра	0	0
µ1	0	0	0
µ2	0	ST(i)=1 – время отсрочки передачи	0
µ3	0	0	1
µ4	0	ST(i)=2 – время ожидания квитанции	0
µ5	Sобс(i)=2 – оповещение о неудаче	0	0

Данные символы ставятся в соответствие состояниям автомата. Для рассматриваемого автомата это соответствие может быть задано таблицей 3:

Таблица 3

Состояние автомата	Выходная комбинация
St0	µ0
St1	µ1
St2	µ2
St3	µ1
St4	µ3
St5	µ4
St6	µ1
St7	µ5

1.9. Аналогичным образом может быть интерпретировано поведение приёмной стороны – автомата «Управление приёмом» (см. рисунок 1). Его поведение может быть описано диаграммой состояний, которая показана на рисунке 7:

Рисунок 7

Данный автомат может находиться в одном из пяти состояний:

1. St₀ – исходное состояние - ожидание очередного кадра;
2. St₁ –приём кадра;
3. St₂ – завершение приёма кадра; запуск таймера, отсчитывающего время передачи квитанции;
4. St₃ – передача квитанции;
5. St₄ – фиксация нарушения процесса приёма.

Входной алфавит данного автомата насчитывает всего шесть символов. Соответствующие этим символам комбинации сигналов приведены в таблице 4.

Таблица 4

Символ входного алфавита	Значения входных сигналов
	S*прд(i)	S(j)	Sош(j)	Sкол(j)
λ0	0	x	x	x
λ1	1	x	0	0
λ2	1	x	1	0
λ3	1	x	x	1
λ4	x	0	x	x
λ5	x	1	x	x

где S*_прд⁽ⁱ⁾ – определяется с помощью выражения (3)

S*прд(i) = Sпрд(i)Aij

(3)

1.10. Приведённой на рисунке 5 диаграмме состояний соответствует таблица переходов, которая представлена на рисунке 8:

Состояние	Символы входного алфавита
	λ0	λ1	λ2	λ3	λ4	λ5	λ*
St0	St0	St1	St4	St4	-	-	-
St1	St2	St1	St4	St4	-	-	-
St2	-	-	-	-	-	-	St3
St3	-	-	-	-	St3	-	-
St4	St0	-	St4	St4	-	-	-

Рисунок 8

1.11. Выходной алфавит автомата «Управление приёмом» может быть задан таблицей 5, а функция соответствия выходных символов состояниям данного автомата – таблицей 6:

Таблица 5

Символ выходного алфавита	Значения выходных сигналов
	Sкв(j)	ST(j)	Sтр(j)
µ0	0	0	0
µ1	0	1 – запуск таймера	1 – приём кадра
µ2	1- квитанция	0	0

Таблица 6

Состояние автомата	Выходная комбинация
St0	µ0
St1	µ0
St2	µ1
St3	µ2
St4	µ0

1.12. Рассмотренная модель управления процессом приёма кадра, хотя и проста, но всё же вполне адекватна поведению оригинала.

Это достигается тем, что в схему модели включён ещё один тривиальный автомат – «имитатор коллизий», суть работы которого заключается в следующем. Известно, что коллизии в канале могут возникнуть в следующих случаях:

1. если конкурирующая станция X_k не «слышит» передатчик X_i и может выйти в эфир, не дождавшись завершения процесса передачи кадра;
2. если станция X_k заняла тот же слот, что и X_i.

Очевидно, что, и в том, и другом случае, помешать успешной передаче кадра по радиолучу X_i – X_j может только та станция X_k, которая отвечает условию (4), что соответствует ситуации, когда станция X_j «слышит» X_k:

XkГ-1Xj

(4)

Условие возникновения подобного рода коллизий может быть сформулировано булевой функцией (5):

Sкол = A1j Sпрд(1) v A2j Sпрд(2) v . . . v ANj Sпрд(N)

(5)

где

- A_ki (k=1, 2, . . . , N) – элементы матрицы смежности A=║A_ij║, описывающей граф G=(E,Г), соответствующий текущему состоянию сети;

- S_прд^(k) (k=1, 2, . . . , N) – значения сигналов, соответствующих состояниям конкурирующих станций: если конкурент X_k ведёт передачу, то S_прд^(k) =1.

Следует отметить, что при вычислении значения S_кол, необходимо рассматривать только те сигналы S_прд^(k) индекс которых - k, не равен i, (передатчик - «сам себе» не мешает).

1.13. Очевидно, что исход попытки передачи пакета определяется не только коллизиями в канале. Любой пакет может быть потерян из-за случайных или преднамеренных помех.

Известно, что вероятность искажения пакета, в основном, зависит от уровня помех в эфире. Этот уровень описывается величиной SNR (Signal-to-Noise Ratio), или соотношением сигнал/шум, которое задаётся известной формулой (6):

SNR = 20 log10 (Ps / Pn)

(6)

где P_s и P_n – уровни сигнала и шума соответственно.

На основании этой величины может быть определена средняя вероятность искажения одного бита пакета - P_ош. В случае отсутствия механизмов защиты от ошибок, зависимость между P_ош и SNR определяется типом модуляции сигнала которая, формально может быть представлена, как некая нелинейная функция (7):

Pош = Q [SNR]

(7)

В случае же наличия таких механизмов, реальный уровень P_ош будет значительно ниже по причине того, что искажённая помехами информация может быть частично восстановлена на приёмной стороне. Поэтому более целесообразно, определять величину P_ош, базируясь на экспериментальных данных. Например, для определения величины могут быть использованы графики зависимости интенсивности радиопомех (BER) от отношения сигнал/шум (SNR), которые представлены на рисунке 9:

Рисунок 9

Имея подобный график (разумеется, представленный в табличной форме), а также длину пакета – L, можно вычислить вероятность искажения пакета – P(L).

Если исходить из предположения, что искажения разных битов одного и того же пакета происходят независимо друг от друга, то величина P(L) может быть вычислена с помощью выражения (8):

P(L) = 1 – (1 - Pош) L

(8)

Но если учитывать тот факт, что, в сетях IEEE 802.11, заголовок кадра передаётся на минимальной скорости – V_min, а данные (на MAC-уровне) на более высокой – V_i, то выражение (7) перепишется, и будет иметь вид (9):

P(L) = [1 – (1 - Pош (1)) h] [1 – (1 - Pош (i)) l]

(9)

где

- P_ош ⁽¹⁾ – вероятность ошибки при передаче заголовка;

- h – длина заголовка (константа);

- P_ош ⁽ⁱ⁾ – вероятность ошибки при передаче MAC-части кадра;

- l - длина MAC-части.

1.14. При использовании графиков, подобных тем, которые представлены на рисунке 9, необходимо иметь величину SNR. Если исходить из предположения, что единственной причиной затухания сигнала является потери в свободном пространстве [1], то эта величина может быть вычислена с помощью выражения (10):

SNR = 10 lg [(4π)2 D2 / Gt Gr λ2]

(10)

где

- D – расстояние между антеннами;

- G_t - коэффициент усиления передающей антенны;

- G_r - коэффициент усиления приёмной антенны;

- λ – длина волны несущей.

Имея величину SNP можно определить вероятность успешной попытки передачи пакета. Для этого достаточно:

1. определить значение функции P_ош = Q [SNR] (см. п. 1.13.);
2. с помощью выражения (9) определить вероятность доведения пакета.

1.15. Поскольку выражение (9) является функцией от величины P_ош и длины пакета, то при имитации процесса передачи пакета по радиолучу (в ситуации, когда канал уже захвачен) лучше всего использовать следующий алгоритм:

1) при «возникновении» события, соответствующего началу передачи кадра, определяется величина P(L);

2) генерируется случайное число 0 <  < 1;

3) проверяется условие (11):

P(L) > 

(11)

3. если условие (11) выполняется, то сигнал S_ош^(j) (см. п. 1.9) приравнивается единице, в противном случае - тот же сигнал приравнивается нулю.

1.16. Но возможен и другой подход. Если дисперсия средней длины пакета (точнее кадра) невелика, то величины P(L) для всех радиолучей могут быть вычислены заранее, ещё при подготовке данных для моделирования, и внесены в матрицу P=║P_ij║ (см. п. 2.2.1), которая «предвосхищает» результат попытки передачи пакета по соответствующему радиолучу. И ошибки в канале будут интерпретироваться как временные нарушения радиослышимости.

Такой подход достаточно удобен для разработки ПО имитационной модели, к тому же он подходит для изучения процедур «самоорганизации» сети – соответствующие этим процедурам механизмы адаптации предусматривают, что неудачные попытки передачи пакетов должны восприниматься как изменение конфигурации сети.

Следующая статья будет посвящена вопросам реализации модели канала.

Вероятность успешного захвата канала в конкурентном окне

Напомним, ранее мы попытались оценить возможные потери при возникновении коллизий в канале коллективного доступа.

В IEEE 802.11 временной интервал, выделенный на захват канала какой-либо станцией, ограничен и разделён на более короткие интервалы – слоты, причём число таких слотов ограничено. При этом порядковый номер слота определяет время отсрочки процесса передачи пакета, привязанное к некоему событию, например, освобождению канала.

Каждая станция выбирает «свой» слот случайным образом и выходит в эфир только в том случае, если выполняются следующие условия:

1. канал свободен;
2. время отсрочки исчерпано.

Кроме того, будем считать, что захват одного и того же слота двумя и более станциями неизбежно приведёт к коллизиям.

Общее число ситуаций, которые могут возникнуть при случайном «розыгрыше» слотов, будет равняться числу размещений с повторением из k по S, и определяться выражением (1):

AkS = Sk+1

(1)

где

• S – общее число слотов;
• k+1 – общее число станций в «клике», включая рассматриваемую станцию «А».

Очевидно, что далеко не любая из этих ситуаций может привести к успешной передаче пакета. Например (см. рисунок 1), станция «А» может захватить и успешно использовать 1-й слот только тогда, когда её «конкуренты» будут претендовать только на захват последующих слотов.

Рисунок 1

Число таких ситуаций зависит от числа слотов - S и числа «конкурентов» - k, и определяется выражением (2):

(S-1) k

(2)

а вероятность захвата 1-го слота – выражением (3):

P1 = (S-1) k / Sk+1

(3)

Станция «А» может успешно использовать и 2-й слот, но только в том случае, если ни одна из конкурирующих станций не будет претендовать ни на 1-й, ни на 2-й слоты.

Соответствующий пример приведён на рисунке 2:

Рисунок 2

Вероятность подобной ситуации будет определяться выражением (4):

P2 = (S-2) k / Sk+1

(4)

Аналогичным образом может быть определена вероятность успешного использования третьего слота – см. выражение (5):

P2 = (S-3) k / Sk+1

(5)

В общем же случае, суммарная вероятность «победы» в конкурентной борьбе, нацеленной на захват канала, будет равняться величине P_зхв, которая может быть определена по формуле (6):

S-1
Pзхв = P1 + P2 + ... + PS-1 =  (S-i) k / Sk+1	(6)
i=1

Следует отметить, что формула (6) справедлива только при k>0. Очевидно, что, при k>0, последний слот не может быть захвачен и успешно использован двумя и более абонентами. Но если k=0, то последний, S-тый слот может быть также успешно использован, следовательно, величина P_зхв будет равна единице.

3.2.5. Графики функции (6) при различных значениях величины S представлены на рисунке 3:

Рисунок 3

Рассматривая приведённые графики можно прийти к следующему выводу: даже при небольшом числе конкурирующих станций, вероятность успешной попытки захвата канала очень мала. Причём увеличение числа слотов повышает эту вероятность, но незначительно, а при большом числе конкурентов стремится к нулю.

Пренебрегать этим обстоятельством нельзя, и очевидно, что имитация механизмов противодействия коллизиям (как на канальном, так и прикладном уровнях) должна рассматриваться как неотъемлемая часть разрабатываемой модели.

Но при этом необходимо ответить на следующий вопрос, - какой способ имитации этих процессов наиболее целесообразен?

Рассмотренные в данном разделе методики обладают рядом положительных качеств. Задачи решены «в общем виде» и не привязаны к конкретным числовым значениям параметров потока и системы обслуживания, что позволяет делать полезные общие заключения.

Но, к сожалению, эти методики позволяют находить общие решения для задач, сводящихся к элементарным ситуациям – то есть в случаях, когда поток заявок невелик и на один и тот же канал будут претендовать одна-две станции.

В принципе, такое допущение возможно и может считаться достаточно корректным. Например, при имитации движения пользовательского трафика можно считать, что нагрузка на любой канал не должна превышать 80% его производительности, поскольку в противном случае очереди в узлах будут стремительно расти. Для того, чтобы убедиться в этом, достаточно рассмотреть график, который приведён на рисунке 4:

Рисунок 4

Этот график показывает зависимость времени пребывания пакета в очереди от нагрузки на канал - Ψ=λ/μ, где λ – интенсивность потока заявок, а μ – производительность канала. (при построении графика предполагалось, что поток заявок – Пуассоновский, а время обслуживания – постоянное). Время ожидания показано в условных единицах: одна условная единица – время обслуживания одного пакета.

Тогда, рассматривая этот график можно прийти к следующему заключению: при Ψ=0.8 средняя величина очереди на канал равна двум. И можно допустить, что ситуации, при которых на один и тот же канал будут претендовать более 2-х станций, не представляют интереса, поскольку строить сети с «бесконечными» очередями не имеет смысла.
Далее мы рассмотрим имитационную модель канала коллективного доступа.