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

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

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

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), которая «предвосхищает» результат попытки передачи пакета по соответствующему радиолучу. И ошибки в канале будут интерпретироваться как временные нарушения радиослышимости.

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

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