Содержание к диссертации
Введение
Глава 1, Особенности механизмов доставки данных в самоорганизующихся
1.1. Назначение беспроводных многошаговых самоорганизующихся сетей 8
1.3. Сети Wi-Fi Mesh стандарта IEEE 802.11s 24
1.4. Критерии эффективной работы сети 32
1.5. Постановка задач исследования 35
Глава 2. Анализ эффективности метода детерминированного доступа 41
2.1. Исследование передачи потоковых данных с помощью метода детерминированного доступа 41
2.2. Анализ влияния метода размещения биконов на метод детерминированного доступа 46
Глава 3. Исследование механизмов управления соединениями 59
3.1. Показатели эффективности механизма управления соединениями 60
3.2. Модель МУС без синхронизации состояний соединений 62
3.3. Модель МУС с синхронизацией состояний соединений 70
3.4. Численные результаты 78
3.5. Результаты сравнения механизмов управления соединениями 85
Глава 4. Исследование механизмов маршрутизации 88
4.1. Анализ ошибок маршрутизации, возникающих в сети MANET под управле
4.2. Исследование совместного использования проактивного и реактивного подхода при рассылке информации о соединениях 99
4.3. Метрики маршрутизации для случайного метода доступа 108
4.4. Метрика маршрутизации для детерминированного метода доступа 124
Заключение 131
Литература 132
- Сети Wi-Fi Mesh стандарта IEEE 802.11s
- Анализ влияния метода размещения биконов на метод детерминированного доступа
- Модель МУС без синхронизации состояний соединений
- Исследование совместного использования проактивного и реактивного подхода при рассылке информации о соединениях
Введение к работе
Актуальность работы
Одной из задач, сфокусировавшей на рубеже тысячелетий внимание исследователей и разработчиков беспроводных широкополосных сетей, стала задача построения децентрализованных сетей.
Децентрализованные сети, или сети класса ad hoc, - это сети, создаваемые при необходимости из равнозначных станций без какой-либо заранее развернутой инфраструктуры. Большая потребность в таких сетях нашла отражение в стандартах беспроводных сетей, например в стандарте IEEE 802.11, известном под коммерческой маркой Wi-Fi. В этом стандарте сети ad hoc создаются из однотипных устройств и используют распределенное управление, при этом каждая станция находится в зоне непосредственного радиоприема всех остальных станций. С момента публикации первой версии стандарта в 1997 г. появилось множество новых задач, которые требовали обеспечения бесперебойной работы движущихся станций и расширения зоны покрытия сети. Расширение зоны покрытия сети означает, что некоторые станции связной сети находятся вне зоны радиоприема друг друга, поэтому для доставки пакетов между ними требуется ретрансляция пакетов через промежуточные станции. Таким образом, расширение зоны покрытия сети приводит к переходу от одношаговой сети к многошаговой. Технологиями, обеспечивающими работу движущихся станций в многошаговой сети, стали 1) оформленная в виде спецификаций организации IEFT технология мобильных ас! hoc сетей (сетей MANET) и 2) технология mesh-сетей стандарта IEEE 802.11s (сетей Wi-Fi Mesh).
Хотя эти спецификации и позволили передавать данные в многошаговых мобильных сетях, потребности пользователей сетей все время растут и, как показывают последние отчеты телекоммуникационных компаний, в последние годы наблюдается резкий рост объема мультимедийного трафика. Это ставит перед исследователями и инженерами новые задачи, связанные с необходимостью не только передавать данные, но и выполнять при этом требования к качеству обслуживания.
Исследованию эффективности доставки данных в многошаговых беспроводных самоорганизующихся сетях посвящено значительное количество работ, среди которых следует особо отметить работы российских и зарубежных ученых: О.М. Брехова, А.В. Винеля, Н.Д. Введенской, А.Б. Гольдштейн, А.А. Гончарова, А.П. Кулешова, Д.В. Лаконцева, А.И. Ляхова, Д.Н. Мацне-ва, В.И. Неймана, Д.С. Осипова, А.Н. Рыбко, А.А. Сафонова, О.Д. Соколовой, С.Н. Степанова, И.И. Цитовича, М.Ю. Якимова, G. Bianchi, Т. Clausen, М. Conti, R.Draves, P. Jacquet, G. Hiertz, A. Nayebi, E.Perkins, R. Ramanathan, C. Santivanez, J. Sobrinho, M. Voorhaen, Y. Yang и др. Некоторые из этих работ
исследуют эффективность механизмов, отличных от используемых в недавно изданных спецификациях сетей MANET и сетей Wi-Fi Mesh. Другие анализируют передачу данных именно в таких сетях, но не уделяют достаточного внимания обеспечению выполнения требований к качеству обслуживания. Третьи, предполагая отсутствие случайных помех в беспроводном канале, получают завышенные показатели эффективности исследуемых механизмов. Таким образом, в настоящее время остается актуальной задача разработки методов анализа эффективности механизмов доставки данных, используемых в сетях MANET и Wi-Fi Mesh при передаче потоковых данных, чувствительных к выполнению требований к качеству обслуживания.
Цель диссертационной работы состоит в построении аналитических и имитационных моделей механизмов доставки потоковых данных в сетях MANET и Wi-Fi Mesh, позволяющих произвести оценку эффективности этих механизмов и настроить их для выполнения требований к качеству обслуживания трафика.
Для достижения поставленной цели в диссертации ставятся и решаются следующие задачи.
-
Аналитическое исследование влияния методов размещения биконов в сетях Wi-Fi Mesh, использующих детерминированный метод доступа, на емкость сети.
-
Разработка аналитической модели передачи данных постоянной интенсивности с выполнением требований к качеству обслуживания в условиях помех с помощью периодических резервирований канала.
-
Разработка аналитических моделей для оценки значений показателей эффективности механизмов управления соединениями.
-
Оценка эффективности различных механизмов маршрутизации в сетях Wi-Fi Mesh и MANET, в т. ч. метрик маршрутизации и механизмов рассылки информации о соединениях, при доставке данных с требуемым качеством обслуживания путем имитационного моделирования.
Методы исследования
В диссертации используются методы теории телекоммуникационных сетей, теории вероятности, теории случайных процессов, теории графов, комбинаторного анализа, вероятностно-статистические методы в теории принятия решения. При имитационном моделировании используется среда имитационного моделирования ns-3.
Научная новизна
В диссертации впервые:
разработана аналитическая модель передачи периодического трафика с помощью метода детерминированного доступа в сетях Wi-Fi Mesh, учитывающая требования к качеству обслуживания и помехи в канале;
исследовано влияние метода размещения биконов на емкость сети Wi-Fi
Mesh, использующей детерминированный метод доступа;
разработаны аналитические модели процесса изменения состояния соединений в сетях MANET и Wi-Fi Mesh, позволяющие оценить показатели эффективности механизмов управления соединениями;
исследованы ошибки маршрутизации, возникающие в сети под управлением проактивного протокола маршрутизации OLSR, и разработаны реактивные методы рассылки сетевой информации, дополняющие OLSR и снижающие вероятность возникновения ошибок маршрутизации;
предложены новые метрики маршрутизации потоковых данных, передаваемых с помощью случайного и детерминированного методов доступа в сетях Wi-Fi Mesh.
Практическая ценность и реализация результатов
Использование теоретических и практических результатов, полученных в диссертации, при разработке сетей MANET и Wi-Fi Mesh позволит существенно повысить их емкость и вероятность выполнения требований к качеству обслуживания мультимедийного трафика реального времени.
Результаты работы внедрены и используются на практике, а также в учебном процессе на кафедре МФТИ (ГУ) в ИППИ РАН «Проблемы передачи и обработки информации», что подтверждено соответствующими актами. В частности, разработанные модели и механизмы использованы в НИР, выполняемых ИППИ РАН по программе ОНИТ РАН «Фундаментальные проблемы разработки новых структурных решений и элементной базы в телекоммуникационных системах», в международном исследовательском проекте FLAVIA, проводимом в рамках 7-й рамочной программы Евросоюза, а также в НИР по заказу ЗАО «Телум».
Основные положения, выносимые на защиту
-
Разработанный метод аналитического моделирования передачи потоковых данных постоянной интенсивности с помощью периодических резервирований канала позволяет минимизировать объем зарезервированных канальных ресурсов при выполнении требований к качеству обслуживания трафика в условиях помех.
-
Построенные аналитические модели протоколов управления соединениями с синхронизацией и без синхронизации состояния соединения в сетях MANET и Wi-Fi Mesh позволяют оценивать значения показателей эффективности этих протоколов, а также определять область допустимых значений параметров протокола, при которых выполняются ограничения на значения показателей эффективности.
-
Разработанные метрики маршрутизации для сетей Wi-Fi Mesh, использующих как случайный, так и детерминированный методы доступа к каналу, а также реактивное дополнение к протоколу маршрутизации OLSR для сетей MANET позволяют в до 3 раз снизить вероятность
невыполнения требований к качеству обслуживания. Апробация работы
Основные результаты диссертации докладывались и обсуждались на ведущих международных и российских конференциях: 3rd Int. Workshop on Multiple Access Communications (Испания, 2010 г.), 8th IEEE Int. Conf. on Mobile Ad-hoc and Sensor Systems (Испания, 2011 г.), 29th Int. Symp. on Computer Performance, Modeling, Measurements and Evaluation (Нидерланды, 2011 г.), «Информационные технологии и системы» в 2009, 2010 и 2011 гг., а также на семинарах ИППИ РАН и МФТИ.
Публикации
Материалы диссертации опубликованы в 15 печатных работах, из них б статей ([1-6]) в рецензируемых изданиях, 3 из которых ([1-3]) входят в перечень ВАК, 9 статей ([7-15]) в сборниках трудов конференций. Подготовка к публикации полученных результатов проводилась совместно с соавторами, причем вклад диссертанта был определяющим.
Структура и объем диссертации
Сети Wi-Fi Mesh стандарта IEEE 802.11s
Беспроводные широкополосные сети резко расширили область своего применения на рубеже тысячелетий благодаря актуальности двух задач, известных как задача последней мили и задача построения децентрализованных сетей.
Задача последней мили заключается в организации доступа к сервисам традиционной проводной инфраструктурной сети для конечных пользователей. Для ее решения в проводную сеть включается специальное устройство - точка доступа, или базовая станция, к которой по беспроводному каналу подключаются клиентские станции конечных пользователей. В рамках такой архитектуры «клиент-сервер» доступ к среде может осуществляться централизованным или распределенным методами. В первом случае точка доступа монопольно управляет доступом к среде, предотвращая коллизии (одновременную передачу пакетов разными станциями), причем, так как в отсутствии точки доступа клиентские станции все равно не могут подключиться к проводной сети, наделение ее монопольными правами не снижает надежности сети в целом. Во втором случае доступ к среде осуществляется на конкурентной основе, и все клиентские станции, а также сама точка доступа соревнуются за право передать свои пакеты.
Децентрализованные сети, или сети класса ad hoc, - это самоорганизующиеся сети, создаваемые из равнозначных станций тогда, когда это необходимо, без проводной инфраструктуры. Задача построения таких сетей также может быть решена с помощью выделения в сети некоторого устройства-координатора и наделения его полномочиями «сервера» по отношению к остальным устройствам, играющим роль «клиентских» станций, но это нецелесообразно. В отличие от задачи последней мили, при решении которой архитектура «клиент-сервер» является естественной, искусственное назначение станциям ролей «клиентов» и «сервера» при решении задачи построения децентрализованных сетей снижает надежность сети. Действительно, выход из строя устройства-координатора прерывает ра боту сети, несмотря на то, что это устройство не выполняет никаких функций, которые не могли бы выполнять другие станции. Вот почему при решении задачи построения децентрализованных сетей предпочтительно использование исключительно распределенного управления доступом к каналу.
Отказ от архитектуры «клиент-сервер» при построении сетей класса ad hoc делает решения задачи последней мили и решения задачи построения децентрализованных сетей существенно разными, что наиболее ярко отражено в разработанном международным комитетом IEEE 802 стандарте IEEE 802.11 [16] беспроводных локальных сетей, известных под торговой маркой Wi-Fi, - в стандарте описаны два типа сетей: инфраструктурные сети и сети ad hoc.
Технология инфраструктурных сетей (Wi-Fi Hotspot) широко известна по миллионам точек беспроводного доступа, развернутых во всем мире. Опираясь на проводную инфраструктурную сеть, точки доступа предоставляют клиентским станциям, как правило, выход в Интернет. Благодаря своему широкому распространению и простоте технология Wi-Fi Hot Spot хорошо изучена и в данной работе рассматриваться не будет.
Сети ad hoc, не требующие инфраструктуры, в рамках базового стандарта IEEE 802.11 являются одноранговыми сетями, в которых каждая станция находится в зоне непосредственного радиоприема всех остальных станций. Однако с момента начала работы над стандартом появилось множество новых задач, связанных с развертыванием таких беспроводных сетей, как;
Расширение зоны покрытия сети означает, что, хотя сеть в целом остается связной, некоторые станции находятся вне зоны радиоприема друг друга, поэтому для доставки
В рамках комитета IEEE 802 LAN/MAN Standards Committee (Комитет Института инженеров электротехники и электроники по стандартам локальных и городских сетей) оформились в виде стандартов такие технологии, как Ethernet, Token Ring, Wi-Fi, Bluetooth и WiMAX, пакетов между ними требуется ретрансляция пакетов через промежуточные станции. Таким образом, расширение зоны покрытия сети приводит к переходу от одношаговой сети к многошаговой.
Движение же станций означает, что топология сети меняется со временем и станции могут в течение своей работы находиться то в зоне непосредственного радиоприема друг друга, то за пределами этой зоны. Технологиями, призванными расширить зону покрытия сети и обеспечить бесперебойную работу движущихся станций, стали технология самоорганизующихся мобильных ad hoc сетей MANET [17], оформленная в виде спецификаций организации IETF (англ.: Internet Engineering Task Force - Инженерный совет Интернета), и технология сетей Wi-Fi Mesh[18], разработанная в комитете IEEE 802 LAN/MAN Standards Committee.
Сети MANET (англ.: Mobile Ad hoc NETwork - мобильная децентрализованная сеть) представляют собой сети, координация которых осуществляется на сетевом уровне, а доступ к каналу осуществляется с помощью одной из уже существующих технологий, допускающей построение децентрализованных сетей. Наибольшее развитие и известность получили сети MANET, построенные на базе технологии Wi-Fi ad hoc, и использующие для многошаговой доставки пакетов протоколы маршрутизации, работающие на сетевом (IP) уровне.
Ранние протоколы маршрутизации в сетях MANET, такие как OLSR [19] (англ.: Optimized Link State Routing - оптимизированная маршрутизация, использующая информацию о соединениях), AODV [20[ (англ.: Ad hoc On-Demand Distance Vector Routing -реактивный протокол маршрутизации, использующий информацию о длинах маршрутов) и DSDV [21[ (англ.: Destination-Sequenced Distance Vector - проактивный протокол маршрутизации, использующий информацию о длинах маршрутов), представляют собой слегка адаптированную кальку с протоколов маршрутизации, разработанных для проводных сетей. Например, протокол OLSR очень похож на протокол OSPF (англ.: Open Shortest Path First - маршрутизация с использованием коротких путей), применяемого для маршрутизации в проводных сетях.
Работая на сетевом уровне, простые протоколы маршрутизации никак не взаимодействуют с канальным уровнем. Таким образом, им недоступна информация о вероятности искажения пакетов помехами и коллизиями, о свойствах сигнально-кодовых конструкций, используемых на каждом из соединений, а также о методе доступа к каналу и параметрах механизма повторов непринятых пакетов. Следовательно, эти протоколы не могут определить вероятность успешной передачи пакета по соединению, а также пропускную способность соединения, а маршруты, найденные с их помощью, обладают малой пропускной способностью и часто пропадают [22, 23]. Кроме того, протоколы маршрутизации зачастую не учитывают такие особенности беспроводной среды, как; высокую вероятность потери пакета при широковещательной передаче, что приводит к частой потере служебной информации; экспоненциальный рост вероятности потери пакета при увеличении его длины, что накладывает ограничения на возможности агрегирования пакетов; влияние передачи пакета одной станцией на передачу пакетов соседними с ней станциями и т. д.
Из-за этого сети MANET, работающие под управлением простых протоколов, обладают низкой производительностью (см., например, [12]), и возможности их использования весьма ограничены.
Развитие этих протоколов и включение в них более сложных механизмов привело к выделению в качестве самостоятельных спецификаций механизмов решения различных подзадач. При разработке второй версии протокола OLSR (OLSRv2[24]), работа над которой еще не завершена, в качестве отдельных механизмов были вынесены протокол обнаружения соседей и установления с ними соединений NHDP (англ.; Neighborhood Discovery Protocol - протокол обнаружения соседей), метрики маршрутизации (OLSRv2 не описывает их, но в отличие от первой версии допускает их использование), механизм формирования служебных пакетов [25[.
Анализ влияния метода размещения биконов на метод детерминированного доступа
Если очередь непуста, то возраст первого (самого старого) пакета обозначим как hr + , где h - некоторое неотрицательное целое число. Так как пакеты поступают в очередь строго периодически, число пакетов в очереди определяется величиной L J + 1, где [xj равно целой части ж, а возраст г-ого пакета равен [h — (i — l)tp]r + - см. рис. 2.2. Доопределим h для тех случаев, когда пакета в очереди нет; h О, /гт + - время до следующего поступления пакета в очередь.
Такое определение величины h позволяет представить передачу пакетов с помощью периодических МССА-резервирований одномерным марковским процессом J(t) с состоянием системы h(t) и дискретным временем, единица которого равна tr слотов, а моменты t и t + 1 соответствуют началам двух последовательных зарезервированных интервалов -см. рис. 2.1.
Опишем множество состояний процесса. Минимальное значение h(t) равно trp. Это значение достигается в момент t + І, когда пакет поступает в пустую очередь в слоте, предшествующем моменту i, и успешно передается в момент t. Очевидно, что максимальное значение h(t) равно d = _ т _ Опишем возможные одношаговые переходы между состояниями процесса.
Пусть О h(t),h(t) + U d. Тогда возможны 2 типа переходов. Обслуживаемый пакет покидает очередь. Так как возраст следующего пакета меньше на tp слотов, а единица модельного времени равна tr слотам, то с вероятностью р успешной попытки передачи система переходит в состояние h(t + 1) = h(t) — tp + tr.
Обслуживаемый пакет остается в очереди. С вероятностью 1 - р попытка передачи оказалась неудачной, и к моменту t + 1 возраст пакета увеличивается на tr слотов, т.е. система переходит в состояние h{t + 1) = h(t) + tr. Пусть h(t) 0. Тогда пакета в очереди нет, и к моменту i+1 время до прихода пакета уменьшится на величину tr, а если пакет придет, то его возраст будет равен + [tr + h{t)]r. В любом случае система переходит в состояние h(t + 1) = h(t) + tr с вероятностью 1.
Если h(t) +tr d, то вне зависимости от успеха попытки передачи пакета его обслуживание прекращается, так как в момент i + 1 его возраст превысит допустимый. Система переходит в состояние h(t + 1) = h(t) — ip + tr с вероятностью 1.
Очевидно, что долю потеряных пакетов можно определить как отношение среднего числа отброшенных за единицу времени пакетов к среднему числу поступивших пакетов. Пакет отбрасывается с вероятностью 1 - р после передачи пакета из любого такого состояния h, что h + tr d. Так как среднее число пакетов, поступивших за единицу времени, равно tr/tp, то доля потерянных пакетов определяется следующим выражением:
Используя разработанную аналитическую модель, исследуем, как выбор периода резервирований влияет на долю потерянных пакетов. На рис. 2.3 приведены результаты, полученные для интервала t = 20 мс между пакетами, типичного для голосового трафика, сгенерированного кодеком G.729, вероятности успешной попытки передачи пакета р = 0,7 и смещения = О, которое получается, если протокол резервирует первый интервал времени сразу после поступления пакета в очередь.
Рис. 2.3. PLR(t r) при 1 = 20 мс, р = О, 7. При t = t период резервирований совпадает с интервалом поступления пакетов, т.е. на один пакет приходится ровно одно резервирование (одна попытка передачи), доля потерянных пакетов равна 1 — р = О,7 независимо от ограничения на максимально допустимое время доставки DQoS. Уменьшение t и повышение допустимого времени доставки DQ0S уменьшают долю потерянных пакетов, так как более частые резервирования предоставляют в среднем большее число попыток передачи для каждого пакета, а увеличение допустимого времени доставки позволяет воспользоваться этими попытками.
Из полученных результатов видна особенность функции PLR(t r): она не является монотонной ни в одной точке по следующим причинам. Начнем с того, что построенная модель позволяет получить значения PLR(t ) только в таких точках, что ? является ради ональным числом. Далее заметим, что средний интервал времени от момента поступления пакета в очередь до первого резервирования равен + 1- т = + Щ - и немонотонно зависит от , так как т(t ) - не монотонна. Чем этот интервал меньше, тем больше попыток приходится на пакет для его передачи. Очевидно, что при = О и t = г (т.е. t = , к Є Ж) интервал минимален, и PLR(t = - ) имеет локальный минимум. На графике это точки t r = 10; 5 мс. «Глубина» этого минимума зависит от многих факторов. Во-первых, она зависит от т. Если г = tr и = 0, то первое резервирование всегда следует сразу за поступлением пакета в очередь. Это значит, что за время нахождения любого пакета в очереди совершается 1 + d/tr попыток передачи пакета. В то же время, если г tr, то только части пакетов соответствует l+d/tr попыток передачи, а остальным - всего d/tr попыток.
Во-вторых, при увеличении допустимого времени доставки и, соответственно, числа попыток передач, совершаемых, пока пакет находится в очереди, вклад дополнительной попытки передачи уменьшается. Поэтому при больших D функция ведет себя почти монотонно.
Используя предварительно вычисленную таблицу значений PLR(t r), станция может быстро подобрать необходимый период резервирований, обеспечивающий передачу пакетов с требуемым качеством обслуживания при минимальном потреблении канальных ресурсов. В следующем разделе будут выявлены особенности метода МССА, позволяющие значительно уменьшить объем этой таблицы.
В разделе 2.1 показано, как выбрать периодичность резервирований, чтобы минимизировать потребление канальных ресурсов, удовлетворяя при этом требования к качеству обслуживания передаваемого потока данных. Стандарт [IS] не выдвигает никаких ограничений на возможные значения периодичности I резервирований и поэтому допускает, что с помощью МССА могут передаваться потоки различной периодичности. Однако возмож на ситуация, когда установить резервирование невозможно несмотря на то, что имеется достаточное количество незарезервированного времени.
Приведем упрощенную иллюстрацию такой ситуации. Пренебрежем наличием бико-нов и предположим, что длительность d попыток передачи всех пакетов данных в сети одинакова. Примем длительность попытки передачи пакета за единицу времени d — 1. Пусть за DTIM-интервал (см. раздел 1.3.1) можно совершить только 12 попыток передачи пакетов данных. Иными словами, длина ВTIM-интервала равна 12. Как показано на рис. 2.4, если уже установлено резервирование периодичности /3 = 3, то невозможно установить резервирование периодичности U = 4 ни при каком значении смещения /, так как, по крайней мере, один интервал нового резервирования пересекается с интервалом уже установленного резервирования.
Стандарт не регламентирует, как поступить в такой ситуации, и станция, которая не в состоянии установить резервирование, может принять одно из следующих решений. 1. Станция отказывается от установления резервирования. 2. Станция отменяет существующие резервирования, чтобы установить новое. 3. Станция разбивает резервирование, которое надо установить, на резервирования с меньшей периодичностью (вплоть до единичной) и пытается установить их. Первый и второй способы не позволяют достичь высокой емкости сети: в рассмотрен ном примере она равна одному потоку. Более того, второй способ не позволяет гарантиро вать качество обслуживания потокам, которые уже передаются по сети. Третий же способ приводит к фрагментации резервирований и к высоким накладным расходам на управле ние ими и их рекламу. Таким образом, необходим метод предотвращения возникновения описанных ситуаций.
Модель МУС без синхронизации состояний соединений
При использовании МУС с условным подтверждением станция соглашается на открытие соединения, получив не менее / биконов подряд, в противном случае станция отказывает в открытии нового соединения. Как показано в разделе 3.3.1, разумно принять I — г — 1. Исходя из логики построения математической модели, очевидно, что введение данного параметра изменяет значение {Тдум) и не влияет на (TSYM) Пусть в момент io = О станция А не получила очередной бикон от станции В и закрыла существующее соединение. С этого момента рассмотрим агрегированную последовательность биконов {cr t}i, полученную следующим образом. Члены последовательности с четными индексами образуют последовательность биконов, принимаемую станцией А, а с нечетными индексами - станцией В. Как и ранее, «1» соответствует принятому бикону, «О» - непринятому. Открытие соединения произойдет в том и только том случае, когда в агрегированной последовательности встретится подпоследовательность из / + г = 2г — 1 единиц подряд. Из них г единиц соответствуют биконам, принятым на станции, которая инициирует открытие соединения, а другие г — 1 единиц - биконам, принятым станцией, которая подтвердит свое согласие на открытие соединения.
В данном случае под (2г — 1)-правильной последовательностью будем понимать последовательность { Jt}i, если она не содержит подпоследовательности из 2г — 1 единиц подряд. Пока агрегированная последовательность принимаемых обеими станциями бико-нов (2г — 1)-правильная, соединение открыто не будет. Как сказано выше, в последовательности четной длины последний член соответствует бикону, принимаемому станцией А, а в последовательности нечетной длины - станцией В. Таким образом, 2г_11_р(2п) определяет вероятность того, что агрегированная последовательность из 2п биконов является правильной, и поэтому станция А с вероятностью 02г-1,1-р(2п) не примет решение об открытии соединения до момента времени 2п+2- В свою очередь, ф2г-і,і-р(2п + 1) определяет вероятность того, что решение об открытии соединения не примет станция В до момента времени 2п+з (см. рис. 3.3).
Утверждение 8. При заданном т среднее время, в течение которого соединение закрыто при использовании МУС с условным подтверждением, определяется формулой
Доказательство. Пусть tu г = OToo, - отметки TBТТ станций А я В, введенные при доказательстве Утверждения 6. Так как соединение закрывается станцией А после того, как она не приняла очередной бикон от станции В в момент времени 0 = О, четные индексы соответствуют отметкам ТВТТ станции В, а нечетные индексы - отметкам ТВТТ станции А. Среднее время, в течение которого соединение остается закрытым, равно:
Оценим точность построенной модели, сравнив ее результаты с результатами, полученными в среде имитационного моделирования ns-3 [65]. Рассмотрим сценарий, в котором две станции, работающих по протоколу IEEE 802.11s со стандартными значениями параметров [18], располагаются на таком расстоянии друг от друга, что вероятность успешной попытки передачи пакета между ними равна р. Длительное наблюдение за состоянием соединения позволяет определить вероятность 7Г обнаружить соединение в открытом состоянии. Время наблюдения и число прогонов имитационной модели выбиралось таким образом, чтобы ошибка полученных результатов была меньше 2% .Значения тг измерены в точках, соответствующих различным р, и представлены на рис. 3.4. Непрерывные кривые на рисунке соответствуют результатам, полученным с помощью построенных аналитических моделей. Аналитические кривые с высокой точностью согласуются с результатами имитационного моделирования в широком диапазоне параметров г 1, s, / и р.
Проиллюстрируем возможность использования построенных моделей для настройки РМР с безусловным и с условным подтверждением в сети, передающей голосовые данные, созданный кодеком G.729 [50].
В ненагруженных сетях Wi-Fi Mesh со случайным методом доступа к среде время доставки пакетов гораздо меньше, чем требуемое для успешной доставки пакетов голосового трафика, а доля PLR потерянных пакетов может быть достаточно высокой, поэтому является критичным фактором для высокого значения R-фактора.
Согласно методике определения значения R-фактора это значение, измеренное на некотором интервале длительностью 1 с, оказывается меньше 50, и, соответственно, услуга доставки голосовых данных считается не предоставленной на этом интервале, если доля потерянных пакетов на этом интервале выше, чем 10%. Учитывая, что голосовой кодек G.729 генерирует поток интенсивностью 50 пакетов в секунду, R-фактор меньше 50, если каждую секунду теряется более 5 пакетов потока. Поскольку к пакетов теряются с вероятностью ,bQbkYMPLRk{l — PLR)50 k, чтобы достичь низкого значения NVA недоступности Настройка NHDP выполняется аналогичным образом и не приводится в диссертации. л где per - вероятность неудачной попытки передачи, р = 7 - ограничение IEEE 802.11 на максимальное число повторов передачи, для маршрутов, состоящих не более чем из D = 5 соединений, необходимо установить per 0,52, т.е. выбрать ро = 1 - per 0, 5.
Пусть L - такое расстояние между двумя станциями, что вероятность успешной попытки передачи p(L) = 0.5. Рассмотрим сеть из 50 мобильных станций, размещенных на квадратной площадке 2.3L х 2.3L. Высокая плотность станций гарантирует, что сеть почти всегда связна и почти все маршруты состоят не более, чем из Р = 5 шагов.
Станции двигаются согласно модели движения 2D Random Direction Mobility Model [70] со скоростью v = {0.005,0.01,0.02, 0.04}L за бикон-интервал, таким образом, среднее время (Тцпк), в течение которого расстояние между двумя станциями меньше L, определяется формулой [58]: (ТНпк) = . (3.25) Сеть Wi-Fi Mesh работает с настройками по умолчанию, однако вместо протокола HWMP используется протокол маршрутизации FRP. Этот протокол является проактивным протокола класса Link State с пошаговой ретрансляцией и описан в разделе 4.2. Максимальный период рассылки сетевой информации Tupdate = 4 бикон-интервала.
Определив, таким образом, ро, Tupdate and {Tlink), приступим к настройке РМР с безусловным подтверждением.
На первом шаге с помощью построенных моделей по формулам (3.21), (3.22), (3.24) найдем для различных параметров МУС значения р0 , т.е. согласно (3.3) такое значение р, при котором тг(р) = 0.5. Значения ро для г, s 10 приведены в табл. 3.1, 3.2, из которых видно, что для обеспечения ро = 0,5 следует выбрать значения s = г для МУС с безусловным подтверждением и s = 2г - 1 для МУС с условным подтверждением. Для других значений ро следует выбирать другие значения параметров МУС. Так как г и s могут принимать лишь натуральные значения, то могут возникать ситуации, когда условие (3.3) не выполняется точно. В таких случаях следует заменить точное равенство на приближенное, т.е. заменить (3.3) на тг = тго & 0,1. Например, для обеспечения
Исследование совместного использования проактивного и реактивного подхода при рассылке информации о соединениях
Стандарт [18] описывает единственную метрику маршрутизации Airtime, физический смысл которой - ожидаемое суммарное время занятости канала при всех попытках передачи пакета некоторой фиксированной длины. Из-за игнорирования степени занятости канала этой метрикой маршруты, выбираемые согласно Airtime, проходят через загруженные участки сети, в которых при случайном методе доступа практически невозможно выполнить требования к качеству обслуживания. Очевидно, что для избежания этого метрика должна учитывать не только время занятости канала, но и его ценность, которая тем больше, чем сильнее загружена среда в окрестности станции-ретранслятора. Особенностью случайного метода доступа к среде в сетях IEEE 802.11 является отсчет времени отсрочки, который замораживается, когда среда занята. Из-за этого при увеличении нагрузки на сеть значительно увеличивается время обслуживания пакета, т.е. длительность промежутка времени, состоящего из всех попыток передачи, а также интервалов отсрочки между ними. Это позволяет построить следующие метрики маршрутизации, значение которых значительно возрастает при увеличении доли времени, когда канал занят.
Построим метрику, значение которой равно ожидаемому времени обслуживания пакета при его передаче по соединению [15]. Для этого рассмотрим процесс передачи пакета.
Чтобы отправить пакет соседней станции у, станция г помещает его в очередь д, соответствующую его категории требований к качеству обслуживания (см. раздел 1.2.1).
Далее номер очереди/категории требований будем опускать для упрощения записи, помня, что
Если других пакетов в очереди нет, то станция сразу же начинает процедуру передачи пакета, как описано в разделе 1.2.1. Если же очередь не пуста, то пакет ожидает в ней, пока не закончится обслуживание предыдущего пакета. Обслуживание пакета прекращается, когда получен кадр АСК, подтверждающий получение пакета приемником, или исчерпаны все попытки передачи этого пакета.
Для каждого передаваемого пакета v станция может определить (см. рис. 4.9): момент Tfnqueue постановки пакета в очередь (определяется напрямую драйвером станции по запомненному при постановке пакета в очередь значению таймера станции); момент Tfnd получения кадра-подтверждения о доставке пакета или окончание интервала AckTimeout после последней возможной попытки передачи (определяется напрямую драйвером); момент T tart начала обслуживания пакета (если пакет попадает в пустую очередь, то он начинает сразу обслуживаться, поэтому TStart = Т Enqueue. иначе, то есть в случае, когда очередь не пуста, момент начала обслуживания совпадает с временем окончания передачи предыдущего пакета T tart = T Of).
Пусть пакет стандартного размера передается по некоторому маршруту. Определим метрику Busy маршрута как ожидаемое суммарное значение времен обслуживания этого пакета на каждом соединении (звене) выбранного маршрута [1,15]. Метрика Busy аддитивна, значение метрики соединения (г, j) равно средней длительности времени обслуживания пакета стандартной длины при передаче его по соединению (г,у): все вычисления проводятся для пакетов рассматриваемой категории. HBusy(iJ) = tar - T nd)v. (4.1) Суммарная ожидаемая длительность интервалов, в течение которых среда была занята в результате выполнения всех попыток передачи одного пакета, соответствует значению он, метрики Airtime, описанной в разделе 1.3.3. Обозначим ожидаемую суммарную длительность интервалов, в течение которых отсчитываются слоты при осуществлении всех необходимых попыток передачи, как backoffij. Поскольку математическое ожидание размера интервала отсрочки 6, выраженное в виртуальных слотах (см. раздел 1.3.1), равно Е{Ь) = , то где І - средняя длительность виртуального слота станции г (см. раздел 1.2.1), R = RL + 1 - максимально допустимое число попыток передач (см. раздел 1.2.1), CWk размер конкурентного окна при fc-той попытке передачи пакета, а Рц(к) - вероятность того, что при передаче пакета по соединению (г,j) будет сделано не менее к попыток {Рц(1) = 1). Таким образом , метрика соединения состоит из двух компонент: HBusy(i, i) = ощ + backoffij. (4.3)
В [32] доказывается бессмысленность учета времени отсчета слотов отсрочки backoffij. Авторы [32] сравнивают аналитически и при помощи имитационного моделирования величины а.ц и о.ц + backoff в зависимости от вероятности успешной передачи. Результаты исследования показывают заметное расхождение между этими величинами только при вероятности успешной передачи, близкой к нулю. Однако свое доказательство авторы строят в предположении, что только одна станция ведет передачу. В этом случае действительно уменьшение на 1 значения счетчика отсрочки происходит через малый интервал slot, так как все время, пока отсчитывается время отсрочки, среда свободна. Поэтому величина backoff , равная backoff , = YslotC fk-1, где / - вероятность неудачной попытки передачи, становится соизмерима с а.ц только тогда, когда счетчик инициализирован большим числом слотов отсрочки (CW 1000). В Здесь и далее мы пренебрегаем временем, в течение которого драйвер станции выполняет различные вычислительные процедуры. Учет этого времени приводит к появлению в формуле (4.3) дополнительного слагаемого, зависящего от типа станции и производительности ее процессора. реальности, как правило, несколько станций соревнуются за доступ к среде. В этом случае во время отсчета слотов отсрочки данной станцией, другие станции будут передавать свои пакеты, и таким образом, виртуальные слоты будут порядка времени занятия среды при одной попытке передачи пакета, то есть станут соизмеримы с а„. Поэтому и слагаемое backoffij может превосходить а.ц во много раз.
Метрика Busy растет быстрее метрики Airtime с увеличением загрузки сети за счет слагаемого backoffij. Рост значения этого слагаемого обусловлен ростом числа попыток передач из-за увеличения вероятности коллизий, ростом конкурентного окна, которое растет экспоненциально с увеличением номера попытки и увеличением средней длительности виртуальных слотов.
Значение метрики соединения будем оценивать после окончания обслуживания каждого пакета, используя экспоненциальное окно. После передачи пакета с номером v новое значение метрики Цву(ьз) выражается через старое l fiYV(hJ) следующим образом: CnZihJ) = C(i,i)(l -w) + (TvEnd - Tvstart)w, (4.4) где w — кв0 (1 — exp (—kBitv)) - вес нового значения, tv - время между началами передачи пакета г и и — 1, кВо и kBl - настраиваемые параметры метрики. Пакеты могут иметь различную длину Pv, а значение метрики должно соответствовать времени передачи пакета стандартного размера Р. Предполагая, что длина пакета слабо влияет на вероятность коллизии, пересчитаем длительность обслуживания пакета. Пусть длина пакета влияет только на время, в течение которого среда занята, и не влияет на количество попыток передачи и распределение скоростей, используемых для передачи пакета. Пусть при передаче пакета v было совершено r\v попыток, причем при попытке п,п = l,vv, использовалась скорость передачи rvn. Тогда длительность занятия среды при попытке п определяется выражением 0 + -, где константа О отвечает за накладные расходы при передаче пакета, не зависящие от скорости передачи и длины пакета. Если бы передавался пакет стандартного размера Р, то эта величина равнялась бы О + —.
