Математика/5. Математическое моделирование

Михеев П.А

Томский государственный университет, Россия

Захват среды передачи данных одной из станций беспроводной ЛВС стандарта 802.11

Введение. Беспроводные локальные вычислительные сети (ЛВС) стандарта 802.11 в качестве базового метода доступа к среде передачи данных используют распределенную функцию координации (DCF) [1, 2], и этот метод называется «множественный доступ с контролем несущей и предотвращением коллизий» (carrier sense multiple access with collision avoidance, CSMA/CA).

Данный механизм основан на том, что передающая станция проверяет, присутствует ли в среде сигнал несущей и, прежде чем начать отправку кадра, ожидает освобождения среды передачи данных. В силу того, что беспроводные станции стандарта 802.11, в отличие от проводных Ethernet, не способны обнаруживать коллизии в среде передачи данных [3, 4], обнаружение основано на механизме тайм-аутов и алгоритме положительной решающей обратной связи.

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

Здесь – начальное значение, задающее ширину конкурентного окна при первой попытке отправителя передать данные, а – номер повторной передачи. Ширина конкурентного окна не может превышать максимального значения установленного стандартом. Для всех физических уровней и способов модуляции стандарт 802.11 устанавливает максимальную ширину конкурентного окна равную [1]. Номер выбранного слота присваивается значению таймера отсрочки , после чего начинают отсчитываться слотовые интервалы. В конце каждого слотового интервала таймер отсрочки уменьшается на единицу, при этом прослушивается среда передачи данных. Как только фиксируется занятость среды, таймер отсрочки замораживается до тех пор, пока не освободится среда передачи данных. После освобождения среды таймер запускается со значения, зафиксированного непосредственно перед замораживанием. По истечении таймера отсрочки () станция-отправитель начинает передачу кадра данных. По окончании передачи отправитель ждет квитанции в течении времени , по истечении которого считается, что была коллизия и станции, попавшие в коллизию, увеличивают значение n на единицу, а действия, направленные на передачу данных, повторяются.

Математическое моделирование. Рассмотрим функционирование беспроводной локальной сети до первой безошибочной передачи кадра и получения квитанции об успешной доставке данных рассматриваемым абонентом [3]. Исходя из этого, найдем основные операционные характеристики системы. Предположим, что в беспроводной ЛВС имеется К станций – источников данных. Считаем, что все источники независимы, равноправны, всегда имеют кадры данных для отправки, а все интервальные промежутки выражены в слотовых интервалах .

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

Среднее время передачи кадра складывается из взвешенной суммы средних времен ожидания неудачных отправлений и времени, затраченном на успешную передачу [5]. Поскольку при неудачных передачах кадра получатель не отправляет подтверждений, то среднее время определится соотношением

. (1)

Здесь и – средние условные времена до неудачной и успешной N-ой повторной попытки отправить кадр рассматриваемым абонентом, а – функция вероятностей продолжительности конкуренции между абонентами за эфир, которая определяется вероятностью успешной передачи кадра на N-ом повторном шаге после (N - 1)-ой неудачной повторной попытки послать отправление:

.

Беспроводная ЛВС с станциями. Обозначим соперничающие (конфликтующие) станции через А и В. Найдем ВВХ процесса передачи данных станцией А. Обозначим через вероятность выбора случайной отсрочки длительностью, равной i слотовым интервалам на n–ой повторной передаче станцией А, а через – станцией В. Тогда условная вероятность возникновения конфликта на n–ой повторной передаче для станции А определится соотношением

Здесь и – рекуррентные вероятности движения станции В «снизу» к конфликтному слотовому интервалу i за множество шагов с успешными передачами:

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

А отсюда получаем вероятность конфликта на первой попытке передать данные:

.

Коэффициенты являются вероятностями того, что на n–ой повторной передаче станции А, у станции В это будет m–ая повторная передача, и они имеют вид:

Средние условные времена до неудачной и успешной n–ой попытки передачи данных и складываются из средней длительности случайной отсрочки (среднее количество слотов до начала передачи) и среднего количества заморозок из-за передачи данных станцией В – и (в случае неудачи) или (в случае успеха) соответственно.

где а среднее количество заморозок имеет следующую функциональную зависимость:

Здесь элементы и – являются средними длительностями заморозок абонента станции А при выборе ею на n-ой повторной передаче случайной отсрочки длительностью i слотовых интервалов, тогда как станцией В выбран j-й слот, предшествующий i-му:

Рис. 1. Зависимость среднего времени передачи кадра станцией А от степени начальной ширины окна для сети из двух станций.

Обсуждение полученных результатов. Численные исследования среднего времени передачи кадра абонентом показывают, что функция (1) имеет ярко выраженный минимум по координате (см. рис.1), определяющей начальный размер конкурентного окна и, как следствие, степень рассеяния станций по длительностям отсрочки перед началом процедуры соперничества. Для двух соперничающих станций минимум достигается при .

Кроме того, уже на этапе формализации задачи стал очевиден эффект захвата среды передачи данных одним из абонентов, о котором упоминается в [4]. Особенно сильно этот эффект проявляется при малых значениях . Уже при первой попытке соперничества двух станций возможен захват среды передачи данных (например станцией В), вероятность которого определится вероятностями того, что у одной из станций (В) длительность отсрочки окажется меньше длительности отсрочки другой станции (А), а затем у «успешной» станции (В) будет выпадать отсрочка нулевой длительности, чередуясь с отсрочками меньшими, чем оставшееся значение таймера отсрочки станции (А):

Рис. 2. Зависимость вероятности захвата среды передачи данных одной из станций на первой попытке передать данные в сети из двух станций от степени начальной ширины окна.

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

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

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

Литература

1. IEEE Std 802.11 – 2007, Revision of IEEE Std 802.11 – 1999. Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications. IEEE Computer Society, 2007. 1184 p.

2. Олифер В.Г., Олифер Н.А. Компьютерные сети. СПб.: Питер, 2006. 958 с.

3. Новиков Ю.В., Кондратенко С.В. Локальные сети: Архитектура, алгоритмы, проектирование. М.: ЭКОМ, 2000. 312 с.

4. Вишневский В.М., Ляхов А.И., Портной С.Л., Шахнович И.В. Широкополосные беспроводные сети передачи информации. М.: Техносфера, 2005. 592 с.

5. Михеев П.А. Индивидуальное быстродействие абонента беспроводной ЛВС стандарта 802.11. – // Труды 42-й международной научной конф. аспирантов и студентов. – СПб.: Издат. Дом С.-Петерб. гос. ун-та, 2011. – С. 315-320