Содержание к диссертации
Введение
1 Принципы построения и особенности широкополосных беспроводных региональных сетей . 9
1.1 Широкополосные беспроводные сети 9
1.2 Семейство протоколов IEEE 802.11 12
1.2.1 Архитектура и основные понятия 12
1.2.2 Уровень управления доступом к среде семейства протоколов IEEE 80
2.11. Распределенная функция координации (DCF) 17
1.2.3 Централизованная (PCF) и гибридная (HCF) функции координации 30
1.3 Принципы построения, особенности и характерные ситуации использования беспроводных широкополосных региональных сетей 36
2 Аналитическая модель радиосоты, работающей в режиме „последняя миля" . 49
2.1 Основные понятия и классификация систем поллинга 49
2.2 Аналитическая модель радиосоты в режиме „последняя миля" . 56
2.2.1 Математическая модель 56
2.2.2 Получение стационарного распределения состояний системы. 58
2.2.3 Получение характеристик производительности системы. 64
3 Аналитическая модель радиосоты, работающей в режиме сбор данных 67
3.1 Математическая модель 67
3.2 Стационарное распределение состояний системы 69
3.3 Определение характеристик производительности 70
4 Имитационное моделирование и оптимизация работы радиосоты. 72
4.1 Сравнение аналитических результатов с результатами имитационного моделирования 72
4.2 Оптимизация параметров схем Адаптивного Динамического Поллинга 84
4.3 Сравнение характеристик радиосоты при децентрализованном и при адаптивном динамическом централизованном управлениях 91
4.4 Программная реализация результатов работы 96
Заключение 99
Литература 101
- Уровень управления доступом к среде семейства протоколов IEEE
- Аналитическая модель радиосоты в режиме „последняя миля"
- Стационарное распределение состояний системы
- Сравнение характеристик радиосоты при децентрализованном и при адаптивном динамическом централизованном управлениях
Введение к работе
Объект исследования и актуальность темы. В последние годы беспроводные сети передачи данных заняли прочные позиции в повседневной жизни. Сфера их применения простирается от обеспечения взаимодействия между бытовыми приборами (например, между телефоном и телефонной гарнитурой, компьютером и монитором и т.д.) до построения сетей передачи мультимедийной информации городского и регионального масштаба. Построение беспроводных сетей передачи данных регионального масштаба на обширных территориях (например, в удаленных сельских регионах Российской Федерации) является единственным экономически оправданным и наиболее перспективным решением проблемы так называемого „информационного неравенства". При создании беспроводных сетей передачи данных регионального масштаба все большее распространение получают устройства на базе технологий IEEE 802.11 (WiFi). Активный рост числа беспроводных региональных сетей выдвигает в ряд первоочередных задач разработку методов оптимизации их работы, разработку новых алгоритмов функционирования таких сетей, а также оценку их производительности. Проблемам разработки математических моделей сетей передачи данных посвящено значительное количество работ. Среди наиболее известных работ, посвященных этим проблемам, следует отметить работы российских и зарубежных ученых: О.М. Брехова, В.А. Васенина, В.М. Вишневского, B.C. Жданова, Р.А. Минлоса, А.В. Печинкина, В.К.
Попкова, В.В. Рыкова, С.Н. Степанова, G. Balbo, S.C. Bruell, L. Fratta, L. Kleinrock, M. Olivetty, H. Takagi, S.C. Borst, O.J. Boxma и др. Среди аналитических работ, посвященных исследованию протоколов IEEE 802.11 и IEEE 802.16 и оценке производительности построенных на их базе беспроводных сетей, наиболее значимыми являются работы В.М. Вишневского, А.И. Ляхова, G. Bianchi, F. Cali, М. Conti, Е. Gregory, J. Weinmiller. Особенности региональных беспроводных сетей при оценке их производительности достаточно полно отражены в ряде работ, однако недостатками этих работ является, слабое внимание, уделяемое механизмам адаптивного централизованного управления, хотя именно эти механизмы нацелены на решение основной проблемы региональных беспроводных сетей — проблемы „скрытых станций". Таким образом, задача анализа, разработки и оптимизации механизмов адаптивного динамического управления является одной из важнейших для развития беспроводных широкополосных региональных сетей передачи данных. Кроме этого, требуется разработать комплекс аналитических и имитационных моделей механизмов централизованного управления для получения адекватных оценок показателей производительности и оптимизации устройств широкополосной беспроводной региональной сети.
В связи с вышеизложенным, целью диссертационной работы является разработка механизмов адаптивного динамического централизованного управления в широкополосных беспроводных региональных сетях передачи информации, а также исследование и оптимизация этих механизмов с помощью комплекса аналитических и имитационных моделей.
Методы исследования. Для достижения поставленной цели, в диссертационной работе используются методы теории вероятности, теории массового обслуживания и имитационного моделирования. Научная новизна:
• впервые разработан комплекс аналитических моделей, адекватно описывающих функционирование широкополосных беспроводных сетей с централизованным управлением;
• разработан комплекс имитационных моделей адаптивного динамического централизованного управления в широкополосных беспроводных сетях функционирующих под управлением семейства протоколов IEEE 802.11;
• на базе разработанного комплекса аналитических и имитационных моделей получены оптимальные параметры механизмов адаптивного централизованного управления в широкополосных беспроводных региональных сетях;
• предложены методы минимизации накладных расходов в работе беспроводных сетей с адаптивным динамическим централизованным управлением.
Научная и практическая ценность. Результаты работы внедрены и используются на практике, что подтверждено соответствующими актами. Изученные и предложенные механизмы адаптивного централизованного управления реализованы в радиомаршрутизаторе РЭС „Рапира", который был разработан ИППИ РАН в рамках Федеральной целевой научно-технической программы „Исследования и разработки по приоритетным на правлениям развития науки и техники" на 2002-2006 годы по Государственному контракту 02.477.11.1003 „Разработка технологии создания нового поколения широкополосных телекоммуникационных средств комплектации беспроводных систем передачи данных, голоса и информации". Радиомаршрутизатор РЭС „Рапира" используется в качестве базового устройства в ряде широкополосных беспроводных региональных сетей, в том числе в сети RadioNet ИППИ РАН, в беспроводной локальной вычислительной сети ИППИ РАН, в беспроводной сети ООО „Уникомпорт", в беспроводной сети ЗАО „НТЦ ФИОРД" и т.д. РЭС „Рапира" более года успешно работает в составе комплексной сети УФСБ по Амурской области, используемой для охраны государственной границы Российской Федерации с республикой Китай. Результаты, полученные в ходе решения задачи оптимизации работы широкополосной беспроводной сети, позволяют максимально эффективно использовать пропускную способность радиосоты региональной сети, что применялось при разработке, реализации и эксплуатации беспроводных сетей, перечисленных выше, а также опорной беспроводной сети г. Обнинск. Результаты диссертационной работы используются в учебном процессе Московского Физико-Технического Института при чтении лекций по курсу „Основы инфокоммуникационных технологий" и в лабораторных работах.
Апробация результатов работы. Основные результаты диссертации докладывались и обсуждались на:
• Международной конференции по информационным сетям, системам и технологиям (МКИССиТ-2002, Санкт-Петербург);
• Международном семинаре „Распределенные компьютерные и телекоммуникационные сети. Теория и приложения" (DCCN-2005, София, Болгария.);
• Третьей международной конференции по проблемам управления Института проблем управления (МКПУ III - 2006, Москва);
• Международном семинаре „Распределенные компьютерные и телекоммуникационные сети. Теория и приложения" (DCCN-2006, София, Болгария.);
• Семинарах ИППИ РАН.
Публикации. По теме диссертации опубликовано 9 научных работ, список которых приведен в конце автореферата. Кроме того, получены 2 свидетельства об официальной регистрации программ для ЭВМ, и 1 патент на полезную модель.
Структура и объем диссертационной работы. Диссертация состоит из введения, четырех глав, заключения, списка литературы, включающего 63 наименования, и приложения. Работа изложена на 108 страницах и содержит 23 рисунка и 14 таблиц.
Уровень управления доступом к среде семейства протоколов IEEE
Рассмотренные механизмы регламентирования коллективного доступа к среде передачи данных имеют одно узкое место — так называемую проблему „скрытых станций", или „скрытых узлов". Из-за наличия естественных препятствий возможна ситуация, когда два узла сети не могут „слышать" друг друга напрямую. Такие узлы называют скрытыми.
Для того чтобы разрешить проблему скрытых узлов, функции DCF и EDCF опционально предусматривают возможность использования алгоритма RTS/CTS.
В соответствии с алгоритмом RTS/CTS каждый узел сети, перед тем как послать данные „в эфир", сначала отправляет специальное короткое сообщение, которое называется RTS (Ready То Send) и означает готовность этого узла к отправке данных. Такое RTS-сообщение содержит информацию о продолжительности предстоящей передачи и об адресате и доступно всем узлам в сети (если только они не скрыты от отправителя). Это позволяет другим узлам задержать передачу на время, равное объявленной длительности сообщения, т.е. на это время среда передачи считается „виртуально занятой". Принимающая станция, получив сигнал RTS, отвечает посылкой кадра GTS (Clear То Send), свидетельствующего о готовности станции к приему информации. После этого передающая станция посылает пакет данных, а принимающая станция должна передать кадр АСК, подтверждающий безошибочный прием. Последовательность отправки кадров между двумя узлами сети показана на рис. 1.4. Теперь рассмотрим ситуацию, когда сеть состоит из четырех узлов: А, В, С и D рис. 1.5. Предположим, что узел С находится в зоне досягаемости только узла А, узел А находится в зоне досягаемости узлов С и В, узел В находится в зоне досягаемости узлов А и D, а узел D находится в зоне досягаемости только узла В. В такой сети имеются скрытые узлы: узел С скрыт от узлов В и D, а узел А скрыт от узла D.
В подобной сети алгоритм RTS/CTS позволяет справиться с проблемой возникновения коллизий, которая не решается посредством рассмотренного выше базового способа организации коллективного доступа в DCF. Действительно, когда узел А пытается передать данные узлу В, то для этого он посылает сигнал RTS, который, помимо узла В, получает также узел С, но не получает узел D. Узел С, получив данный сигнал, блокируется, то есть приостанавливает попытки передавать сигнал до момента окончания передачи между узлами А и В. Узел В в ответ на полученный сигнал RTS посылает кадр CTS, который получают узлы А и D. Узел D, получив данный сигнал, также блокируется на время передачи между узлами А и
У алгоритма RTS/CTS имеются свои недостатки, которые в определенных ситуациях могут приводить к снижению эффективности использования среды передачи данных. Например, в некоторых ситуациях возможно такое явление, как распространение эффекта ложных блокировок узлов, что в конечном счете может привести к ступору сети.
Аналитическая модель радиосоты в режиме „последняя миля"
Исследуемая модель представляет собой систему поллинга с несколькими очередями и одним обслуживающим прибором (сервером), который циклически обходит очереди. Время на переключение сервера между очередями принимается равным нулю. Полагаем, что имеется полная информация о состоянии системы в текущий момент времени. Очередь обслуживается, если ее длина превышает заданную величину (порог), при этом сервер готовится к обслуживанию очереди некоторое случайное время. Сервер производит обслуживание очереди до тех пор, пока она не опустеет. Такая дисциплина обслуживания называется исчерпывающей пороговой дисциплиной.
Пороговые дисциплины обслуживания введены в /40/, где представлен анализ систем поллинга с пороговым шлюзовым и глобально-шлюзовым обслуживанием. При шлюзовой дисциплине сервер обслуживает лишь те заявки, которые поступили в очередь до момента начала ее опроса. Глобально-шлюзовое обслуживание предусматривает обслуживание лишь тех заявок в очереди, которые поступили до предыдущего опроса первой очереди, т.е. в начале текущего цикла. Для такой системы поллинга получены оценки среднего времени цикла и среднего времени ожидания. Точное значение среднего времени ожидания может быть получено лишь с помощью значений средних длин очередей в моменты подключения сервера. Однако эти величины удалось получить только для частного случая, когда очередь обслуживается, если в ней есть хотя бы одна заявка /40, 41/. В этом случае также получено распределение времени ожидания.
В отличие от модели, рассмотренной в /40/, также предполагается, что если в момент окончания обслуживания некоторой очереди все остальные очереди имеют недостаточное для начала обслуживания число заявок, то сервер прекращает опрос и вновь начинает работу, когда какая-либо из очередей накопит требуемое число заявок. Таким образом, исследуемая система поллинга предполагает особый вид обслуживания очередей (исчерпывающее пороговое обслуживание), с возможным простаиванием сервера.
Системы поллинга с простоями сервера достаточно подробно исследовались в ряде работ: /42, 43, 44, 45/. В отличие от предлагаемой модели, в этих работах предполагалось, что простой сервера начинается с момента, когда система становится пустой. В /42, 43/ длительность простоя сервера зависит от числа заявок в системе. В моделях /42, 44/ простой сервера завершается в момент поступления заявки в систему. Обобщение таких систем поллинга представлено в /43/, где предполагается, что после окончания периода занятости системы сервер вновь начинает работу, когда число заявок в системе достигнет некоторого значения, называемого порогом. Для этой модели получено среднее время ожидания в каждой очереди. В /45/ исследована система поллинга с простоями сервера, длительности которых не зависят от состояния системы.
Отметим, что предположение о простое обслуживающего прибора (сервера) усложняет исследование модели, однако учет таких особенностей важен с точки зрения применения модели на практике.
Рассматривается циклическая система поллинга с одним обслуживающим прибором (сервером) и N очередями, имеющими неограниченное число мест для ожидания, N 2.
Поток заявок в г-ю очередь представляет собой простейший поток с параметром \, г = 1, N.
Сервер обходит очереди циклически (в порядке возрастания их номеров) и обслуживает лишь те очереди, число заявок в которых достигло определенного порога ( для г-й очереди), / 0, г = 1,N. Перед обслуживанием г -й очереди серверу требуется случайное, экспоненциально распределенное с параметром S{ время на подготовку к работе. Время обслуживания заявок в г -й очереди экспоненциально распределено с параметром ЦІ, г = 1, N. Очередь обслуживается до тех пор, пока она не опустеет, после чего сервер перемещается к следующей очереди, подлежащей обслуживанию. Если же все очереди содержат недостаточное для обслуживания число заявок (менее к{ для г-й очереди), сервер прекращает обход до тех пор, пока число заявок в одной из очередей не достигнет необходимого порога.
В следующем разделе введен случайный процесс, описывающий поведение системы, и приведена система уравнений для нахождения стационарных вероятностей состояний, позволяющих вычислить характеристики производительности системы.
Стационарное распределение состояний системы
В качестве приближенного анализа используем следующий подход. Предположим, что с некоторой вероятностью щ очередь в цикле опрашивается, а с вероятностью 1 — щ - нет. В этом смысле рассматриваемая модель сводится к системе поллинга с обслуживанием типа Бернулли.
Вероятности щ,..., UN могут быть вычислены следующим образом: где С - среднее время цикла. Поясним эту формулу. Очередь будет обслужена в текущем цикле, если она не была обслужена в предыдущем цикле с вероятностью 1 — щ или она была обслужена (с вероятностью щ) и за среднее время цикла С в нее поступили заявки. Из последнего равенства получаем формулу
Заметим, что если Л очень мало, то вероятность щ = 0,5, что согласуется с принятой адаптивной схемой поллинга. В случае, когда интенсивность потока заявок большая, тогда и среднее время цикла увеличивается и величина \С весьма большая, что позволяет принять e XiC равным нулю, откуда щ = 1, то есть при большой интенсивности входного потока очередь практически всегда не пуста и в каждом цикле опрашивается сервером.
Среднее время цикла вычисляется по формуле Заметим, что время цикла это либо время подключения к очередям, подлежащих обслуживанию в цикле, и совокупная длительность их обслуживания, либо простой сервера, если все очереди пропускаются в цикле.
Из равенств (3.1) и (3.2) получаем систему уравнений для нахождения неиЗВеСТНЫХ С И Щ,. . . , Идг.
Для нахождения средней длины очереди применяется метод анализа средних.
Приведем некоторые характеристики, получаемые с помощью среднего времени цикла С.
Среднее время обслуживания г-й очереди в цикле, при условии, что очередь в цикле опрашивается, есть величина
Средняя длина г-й очереди в момент опроса, при условии, что в этот момент очередь не пуста, определяется равенством
Обозначим через Ь{ среднюю длину г-й очереди в произвольный момент времени. Заметим, что произвольный момент времени может быть моментом обслуживания j-й очереди (с вероятностью pj), либо моментом подключения к ней (с вероятностью gjUj/C), либо моментом простоя с вероятностью УТ/С, ГДЄ V = Птп=і(1 _ ит) Применяя метод анализа средних, получаем следующую формулу для вычисления средней длины очереди Lf.
Сравнение характеристик радиосоты при децентрализованном и при адаптивном динамическом централизованном управлениях
Объектом моделирования служит локальная сеть, состоящая из нескольких устройств работающих с одной базовой станцией. В модели реализован случай скрытых станций (устройства при этом слышат только базовую станцию, но не друг друга, базовая станция слышит все устройства). Используются модель, реализующая работу радиосоты беспроводной региональной сети с использованием децентрализованной функции управления DCF, и модель, реализующая предложенный механизм адаптивного динамического централизованного управления. Все потоки трафика в обеих моделях идентичны. Потоки данных от оконечных станций к базовой и от базовой станции к оконечным симметричны.
Ввиду идентичности потока идущего от базовой к оконечной станции и обратного ему в режиме адаптивного динамического централизованного управления (АДП режиме), два потока заменены на один. Тестовым потоком данных в АДП режиме считается простейший поток с параметром Л. Для DCF режима два встречных потока нельзя заменить одним, так как пакеты этих потоков слышны разному количеству станций. Поэтому в этом случае, тестовым потоком будем называть простейший поток с параметром Л/2 от оконечной к базовой станции, и простейший поток с таким же параметром в обратном направлении, для обеспечения идентичной ADP режиму интерпретации термина.
Для моделирования системы выбраны следующие условия. Одна базовая станция, десять оконечных станций. Количество одновременных потоков на каждой абонентской станции одинаково. Полученные результаты для ADP и DCF режимов построены на одном графике для их сопоставления.
Для отображения качества работы сети используются следующие ее параметры: среднее время ожидания кадра в очереди и средняя длина очередей. Длина очередей показывает, какого размера буфера устройств достаточно для реализации такой системы. В данном моделировании считается, что предел для буфера устройства — 90 кадров. В модели ADP режима данный предельный размер буфера используется, так что более 90 кадров в очереди быть не может, остальные кадры просто отбрасываются, поэтому на графиках показанное количество пакетов никогда не превышает 90. Для DCF режима данное ограничение не используется, так как буфер базовой станции должен быть больше, чем абонентской, а моделируется она отдельно, в отличие от ADP режима. Поэтому количество кадров на графиках для DCF режима может быть более этого буфера, и нужно понимать, что в этом случае может происходить переполнение очередей, то есть на графике изображено не стационарное среднее число кадров в очереди, а число кадров накопившихся в данной очереди. Таким образом, стоит помнить, если на графике среднее число кадров велико, это не означает, что очередь действительно может вместить такое их количество. В этом случае вновь поступающие кадры отбрасываются.
На рис. 4.3 показан график зависимости среднего времени ожидания кадра в очереди для устройств, работающих в режиме АДП, а также для оконечных станций в режиме DCF и базовой станции в режиме DCF (как было сказано ранее, очереди, а значит и их характеристики у базовой и оконечных станций в режиме DCF различны) от нагрузки в очередях. Предполагается, что все станции передают данные с максимальной скоростью для протокола IEEE 802.11а — 54 Мбит/с. В результате, получаем 10 потоков данных с параметром Л для АДП режима и 20 потоков данных с параметром Л/2 для DCF режима.
Из графика видно, что время ожидания кадров в очереди остается очень малым при Л = 500 для DCF режима и Л = 600 для ADP. Далее начинается насыщение очередей в обоих режимах и резкое возрастание количества коллизий в DCF режиме. В результате чего время ожидание и его отклонение начинают резко возрастать.
