Мы обновили сайт. Добро пожаловать!

Добро пожаловать на новую версию сайта www.smartnlg.ru

Реализация модели канала

Продолжение темы имитационного моделирования канала коллективного доступа.

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

В общем случае, эти процессы не должны считаться независимыми, а а должны взаимодействовать между собой.

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

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

1. ожидание очередного кадра;
2. ожидание освобождения канала;
3. запуск таймера, определяющего время начала передачи кадра (основной принцип канального протокола – «слушать», прежде чем «вещать»);
4. ожидание завершения данного интервала;
5. захват канала и передача кадра.

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

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

Если какой либо другой аналогичный автомат находится в состоянии «захват канала», то рассматриваемый автомат будет получать сигнал «канал занят».

Рисунок 1

Из рассматриваемого примера видно, что в моделируемой сети могут сосуществовать параллельные «типовые» процессы, каждый из которых может находиться в своём уникальном состоянии. Но, при их имитации на одной ЭВМ, эти события необходимо рассматривать последовательно. Поэтому, совокупность параллельно протекающих процессов должна быть представлена в виде упорядоченной последовательности моментов наступления событий во времени.

При таких условиях, сканируя эту последовательность, и определяя, в каждый наступивший момент реакции автоматов на изменения входных сигналов, можно сымитировать любую ситуацию в системе. При этом, любая сложившаяся ситуация может быть представлена в виде вектора Z=║Z_n║, каждый элемент которого - Z_n, соответствует конкретному автомату - M_n, а значение этого элемента – состоянию данного автомата. Например, если некий автомат M₁ занял канал, (состояние St₄), а автомат M₂ ожидает его освобождения (состояние St₁), то фрагмент вектора Z будет содержать информацию, которая показана на рисунке 2:

Конечный автомат	Текущее состояние
M1	St4
M2	St1
.	.

Рисунок 2

При наступлении особого состояния, (изменении входных сигналов), этот вектор модифицируется с помощью следующего алгоритма:

- поочерёдно рассматриваются состояния всех автоматов;

- при рассмотрении каждого состояния определяется соответствующая ему выходная комбинация - µ;

- на основании полученных µ отыскиваются входные комбинации для всех автоматов - λ;

- найденные входные комбинации фиксируются в памяти ЭВМ;

- с помощью таблиц переходов определяются новые состояния автоматов.

В принципе, такие операции («ревизии» состояний системы) можно производить на каждом такте имитации – любая ситуация может считаться особым состоянием.

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

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

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

Как в реальной системе, так и в имитационной модели, могут одновременно работать k таймеров, причём каждый из них может завершить отсчёт в конкретный момент времени – T_k. Имея такие числа можно определить момент наступления ближайшего особого состояния системы, которое может быть определено с помощью проверки условия (1):

TR = min Tk	(1)
k

Далее, после активизации соответствующих процессов, значения всех запущенных таймеров уменьшается на величину T_R, позволяя тем самым определить момент наступления следующего особого состояния.

Следует отметить, что особые события могут порождаться не только таймерами, но и всеми другими автоматами. Причём эти автоматы могут находиться в пассивных состояниях, время выхода из которых – T_a, определить нельзя.

В таких случаях возможно следующее решение – если входной сигнал не меняет состояния автомата, то считать T_a = ∞. В противном же случае считать, что T_a = 0.

Для определения значения T_a можно воспользоваться таблицей переходов, действуя следующим образом:

1. выделить строку такой таблицы, которая соответствует текущему состоянию автомата;
2. убедиться в том, что текущая комбинация входных сигналов соответствует «петле», то есть возвращает автомат в то же состояние, в котором он уже находиться;
3. если это условие выполняется – то T_a : = ∞, в противном случае - T_a : = 0.

Например, в представленной на рисунке 3 таблице переходов, выделенные элементы соответствуют активным состояниям автомата, которые следует считать особыми событиями, а все остальные элементы – пассивным состояниям автомата.

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

Рисунок 3

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

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

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

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

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

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

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

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