Содержание к диссертации
Введение
Глава 1. Обзор существующих разработок в области построения беспроводных сетей 10
1.1. Состояние развития беспроводных сетей 10
1.2. Передача данных в беспроводных сетях, управление качеством обслуживания 13
1.3. Управление ресурсами в беспроводных сетях, обеспечение качества обслуживания 50
1.4. Выводы 57
Глава 2. Модель беспроводной сети передачи данных 59
2.1. Архитектура узла беспроводной сети 59
2.2. Топологическая модель сети 63
2.3. Оценка пропускной способности сети 65
2.4. Маршруты передачи сообщений 83
2.5. Выводы 90
Глава 3. Разработка и анализ эффективного протокола управления ресурсами беспроводной сети 91
3.1. Общее описание и задачи протокола 91
3.2. Алгоритм сбора информации о нагрузке 92
3.2. Модель виртуального канала передачи данных 95
3.3. Алгоритм маршрутизации передаваемых данных 99
3.4. Реализация протокола nrmp 121
3.5. Выводы 130
Глава 4. Исследование эффективности протокола управления ресурсами беспроводной сети 131
4.1. Построение системы для экспериментальной оценки параметров протокола управления ресурсами беспроводной сети 131
4.2. Моделирование передачи пакетных данных 139
4.3. Моделирование передачи потоковых данных 151
4.4. Выводы 156
Заключение 158
Список литературы
- Передача данных в беспроводных сетях, управление качеством обслуживания
- Топологическая модель сети
- Модель виртуального канала передачи данных
- Моделирование передачи пакетных данных
Введение к работе
Диссертационная работа посвящена исследованию алгоритмов и протоколов управления выделением и занятием ресурсов высокоскоростных беспроводных сетей с переменной топологией, поддерживающих смешанный тип коммутации передаваемых данных. Разработана модель беспроводной сети, инвариантная к используемым протоколам управления. Разработаны критерии оценки эффективности работы протоколов управления ресурсами. Показано, что применение существующих подходов к управлению ресурсами подобных сетей приводит к неэффективному использованию доступной пропускной способности. Разработаны новые протоколы управления выделением ресурсов и передачей данных в беспроводных сетях с переменной топологией. Изучен эффект от их применения с точки зрения улучшения характеристик работы сети. Методы и алгоритмы, предложенные в данной работе, были использованы при проектировании системы беспроводной связи "Falcon 3".
Целью настоящей работы является разработка принципов и алгоритмов управления ресурсами беспроводной высокоскоростной сети с переменной топологией, а также протоколов управления доступом к ресурсам разделяемых каналов передачи данных и занятием доступных выделенных каналов для передачи информации, способных адаптироваться к текущим параметрам сети (топологии, основным направлениям передачи информации, степени загрузки сети) и находить оптимальные решения для обеспечения наилучших показателей суммарной пропускной способности сети при условии удовлетворения требований по обеспечению запрошенного качества обслуживания для передаваемых потоков данных.
В задачи работы входило
Построение математической модели высокоскоростной беспроводной сети.
Разработка эффективного протокола для управления доступом к ресурсам беспроводного канала передачи данных.
Разработка эффективного алгоритм маршрутизации и управления ресурсами разделяемых и выделенных каналов при передаче потокового трафика в высокоскоростной беспроводной сети.
Разработка системы тестирования протоколов.
Актуальность работы состоит в том, что задача создания эффективных алгоритмов и протоколов управления занятием ресурсов беспроводной сети передачи данных с использованием анализа информации о текущей нагрузке в сети стоит в ряду основных проблем теории систем массового обслуживания, ко-
торые ждут своего решения. Существующие алгоритмы управления и протоколы передачи данных для беспроводных ad hoc сетей оказались неподходящими или малоэффективными при их применении для высокоскоростной многоканальной передачи данных. Все они были ориентированы на обмен данными в сетях, где доступен лишь один разделяемый канал передачи данных, и обмен данными производится в режиме коммутации пакетов. Потребовалось не просто модифицировать существующие подходы, но разработать качественно новые алгоритмы управления выделением ресурсов и протоколы передачи данных, способные адаптироваться к характеристикам обслуживаемой нагрузки и оптимизировать использование доступного ресурса пропускной способности сети. На сегодняшний день существование протоколов управления передачей данных для сетей подобного класса из открытых источников не известно. Разработка протоколов управления ресурсами такого рода сетей и анализ их применения в персональных сверхскоростных беспроводных сетях имеют научный и практический интерес.
Научная новизна и практическая ценность работы состоит в том, что:
Разработаны методы и алгоритмы решения задач управления передачей данных в беспроводных сетях с переменной топологией, использующие результаты анализа текущей загрузки сети и предсказания изменения характеристик предоставляемого качества обслуживания в сети в зависимости от параметров поступившего запроса на передачу данных.
Разработаны методы и алгоритмы решения задач управления выделением ресурсов беспроводной сети с переменной топологией, максимизирующие пропускную способность сети. Разработаны критерии оценки эффективности решения задач управления выделением ресурсов беспроводной сети с переменной топологией. Полученные критерии представлены в виде соотношений между практически и теоретически достижимыми значениями пропускной способности сети
Разработаны критерии оценки эффективности решения задач оптимизации распределения передаваемой нагрузки в беспроводных сетях с переменной топологией. Полученные критерии представлены в виде соотношений, позволяющих найти набор различных характеристик таких, как оптимальный и максимально допустимый уровни нагрузки в кластере сети, задержка при передаче пакетов данных через сеть.
В работе разработаны протоколы управления выделением ресурсов беспроводной ad hoc сети с адаптацией к параметрам сети, протокол маршрутизации передаваемых данных беспроводной ad hoc с поддержкой смешанных ти-
пов коммутации. Предложено применение разработанного протокола в беспроводных системах передачи данных.
Полученные результаты могут найти применение при проектировании высокоскоростных беспроводных сетей со смешанными видами передаваемого трафика (как пакетного, так и потокового) и случайным доступом к разделяемым ресурсам сетей. Результаты исследований, полученные автором в работе, использованы в проектно-копструкторской деятельности ООО «Теком» при проектировании и разработке системы беспроводной связи «Falcon 3», что подтверждается актом о внедрении от 10 ноября 2008 года. Разработанная система моделирования беспроводных сетей WNS внедрена в компании «НКТ» для оценки параметров качества обслуживания проектируемых сетей беспроводной связи, что подтверждается актом о внедрении от 26 июня 2008 года.
Апробация работы. Основные результаты диссертационной работы докладывались и обсуждались на следующих научных конференциях:
всероссийской научно-технической конференции «Информационные системы и технологии ИСТ-2007» (г. Нижний Новгород, 2007 г.)
конференции ICTTA'06 - 2nd IEEE international conference on information & communication technologies: from theory to applications (г. Дамаск, Сирия, 2006)
всероссийской научно-технической конференции «Информационные системы и технологии ИСТ-2006» (г. Нижний Новгород, 2006 г.)
IV молодежной международной научно технической конференции «Будущее технической науки» (г. Нижний Новгород, 2005 г.);
всероссийской научно-технической конференции «Информационные системы и технологии ИСТ-2005» (г. Нижний Новгород, 2005);
конференции PIMRC 2004 -15 IEEE International Symposium on Personal, Indoor and Mobile Radio Communications (г. Барселона, 2004);
2-ой Международной конференция IEEE "Цепи и системы в телекоммуникациях" (г. Москва, 2004)
научно-технической конференции «Технические, программные и математические аспекты управления сложными распределёнными системами» (г. Нижний Новгород, 2004).
Публикации. Основное содержание работы отражено в 19 печатных работах.
Основные положения, выносимые на защиту: 1. Математическая модель разделяемого канала беспроводной сети и построенная на ее основе модель беспроводной сети с переменной топологией.
Алгоритм маршрутизации и динамического занятия и освобождения выделенных каналов для беспроводной сети.
Протокол управления передачей пакетов с данными в беспроводных сетях с поддержкой приоритетов передачи и гарантированных параметров качества обслуживания.
Результаты анализа эффекта от применения протоколов в беспроводной сети передачи данных.
Структура и объем диссертации. Текст диссертационной работы состоит из введения, четырех глав, заключения, списка литературы (51 наименование) и приложения. Общий объема диссертации 168 страниц, в том числе 159 страниц основного текста, 7 страниц списка литературы, 2 страницы приложений, 6 таблиц, 60 рисунков.
Передача данных в беспроводных сетях, управление качеством обслуживания
На протяжении всей истории человеческого общества обмен информацией был одной из важнейших потребностей и движущих сил развития социума. Чем более высокоразвитым становился социум, тем больший объем данных требовалось передавать. По мере увеличения объема информации, знаний, накопленных об окружающем мире, все острее становился вопрос доступности информации для каждого нуждающегося в ней члена социума. Именно доступность информации являлась важнейшим ограничением при переходе от развитого индустриального общества к обществу информационному. Создание глобальных сетей передачи данных стало первым шагом на пути предоставления доступа каждому человеку ко всему информационному потенциалу, накопленному человеческим обществом за тысячелетия истории его развития. Однако этого оказалось недостаточно - созданные сети были в подавляющем большинстве проводными, и для обмена информацией человек должен был воспользоваться одним из терминалов доступа, имеющих фиксированное расположение. Требовалась технология, позволяющая снять это ограничение, обеспечить человека возможностью информационного обмена без необходимости находиться для этого в одной из строго фиксированных точек пространства. Решением этой проблемы стало использование беспроводных, мобильных сетей передачи данных. В этом случае оконечный терминал, обеспечивающий обмен данными находится непосредственно у человека, а связь осуществляется через радиоканал. В настоящее время в мире развернуты сотни тысяч беспроводных сетей передачи данных: сотовые, спутниковые, транкинговые, локальные беспроводные, персональные беспроводные и множество других видов сетей. Все они в значительной степени различаются по принципам организации, типам передаваемой информации, радиусу связи, времени жизни и многим другим параметрам.
На сегодняшний день подавляющее большинство наземных беспроводных сетей связи имеют фиксированную сетевую структуру и расположение базовых станций, связанных между собой, как правило, проводными линиями связи. Примером являются сотовые сети, транкинговые и пейджинговые сети связи [20]. Термин беспроводная сеть подразумевает в случае упомянутых сетей беспроводную связь между базовой станцией (БС) и мобильными оконечными терминалами. Мобильный оконечный терминал может двигаться географически во время своего соединения с БС. Выходя из зоны видимости одной БС, терминал "перескакивает" в зону видимости другой БС и поддерживает связь уже через нее (handoff-технология) [14]. В данном подходе проектирования сетей расположение базовых станций фиксировано. Другая технология сетей, интенсивно развивающаяся в настоящее время, касается построения беспроводных сетей с нефиксированной инфраструктурой - Ad Нос сетей или MANET (Mobile Ad Hoc Networking) сетей [27].
В отличие от сетей с фиксированной инфраструктурой, в Ad Н ос сетях все узлы являются мобильными и могут быть связаны динамически в произвольной форме. Все узлы ведут себя не только как оконечные пользовательские терминалы, но и как маршрутизаторы и принимают участие в обнаружении и обслуживании маршрутов к другим узлам сети. Ad Нос сеть может состоять как из десятков-сотен узлов (например, военные оперативные сети связи) и тысячи сетевых узлов (например, сети сенсорных узлов [43]). Сети MANET имеют достаточно широкую сферу применения. Ad Нос сети полезны в поисково-спасательных операциях, на встречах или конференциях, где пользователи желают обмениваться данными или вести телефонные разговоры на местности, где нет услуг сотовой связи. Предполагается, что Ad Нос сети могут послужить дешевой альтернативой обычной сотовой связи, поскольку связь между узлами сети не требует наличия базовых станций [27].
Исследуемые в настоящей работе высокоскоростные беспроводные сети связи могут работать как в режиме с переменной топологией (то есть принадлежать к классу Ad Нос сетей), так и в режиме централизованного управления. Ad Нос режим обеспечивает большую устойчивость сети от сбоев в работе отдельного устройства, в то время как режим с централизованным управлением обеспечивает обычно более высокую скорость передачи данных, больший диаметр сети и меньшую стоимость абонентского комплекта. Упрощенным примером такого типа сетей является так называемые Wi-Fi сети (стандарт IEEE 802.11b и 802.1 lg) [17, 22]. Однако сети Wi-Fi предназначены, в основном, для работы в режиме централизованного управления через так называемую «точку доступа», так как протокол передачи данных не поддерживает маршрутизацию передаваемых данных кроме как через точку доступа.
На сегодняшний день реально функционирующих высокоскоростных Ad Нос сетей пока еще очень немного. В основном сети с переменной топологией используются для обмена небольшими объемами данных (например, распределенные сети датчиков). Что касается передачи высокоскоростного потокового трафика (например, видео реального времени), то опять же известны только опытно-демонстрационные работы. Существование проектов Ad Нос сетей связи со смешанной коммутацией из открытых источников пока неизвестно. В то же время, сети, построенные по технологии Bluetooth [17, 22] (данный класс сетей относится к сетям связи с централизованным управлением), поддерживают такую возможность, предоставляя устройствам — членам сети канал со случайным доступом для обмена пакетными данными и несколько выделенных каналов для передачи голосового потокового трафика.
Топологическая модель сети
Рассмотрим применимость каждого из вышеописанных классов алгоритмов маршрутизации пакетов для высокоскоростных беспроводных сетей.
Первый подход — передача на основе таблицы маршрутизации -требует постоянного мониторинга изменений топологии сети и в случае быстро меняющейся высоко мобильной ad hoc сети данный подход оказывается неэффективным, так как накладные расходы, создаваемые служебными пакетами мониторинга топологии сети, оказываются очень значительными. Время стабильности маршрута для передачи данных при этом слишком мало, что приводит к постоянной необходимости поиска нового пути в результате нарушения радиосвязи на одном из пролетов старого маршрута.
Однако в том случае, если топология сети является медленно меняющейся (или неизменной), использование этого алгоритма является оптимальным, так как при этом трафик, создаваемый служебными пакетами с уведомлениями об изменениях в топологии сети, будет минимальным. Время отыскания маршрута при этом будет сильно зависеть от размера сети и производительности аппаратного обеспечения адаптера, но оно все равно будет намного меньше, чем время, которое требуется на отыскание маршрута с использованием алгоритмов по запросу. Более того, использование таких алгоритмов маршрутизации позволяет находить более одного пути (если они существуют) от отправителя к получателю, что может существенно повысить надежность соединения и минимизировать время восстановления соединения после сбоя на одном из участков маршрута. А применение адресной посылки, когда пакет ретранслируется только узлами, входящими в маршрут, позволит значительно повысить эффективность использования ресурса пропускной способности сети.
Но даже при условии медленно меняющейся топологии сети с увеличением размера сети начинают проявляться следующие недостатки: необходимость хранения достаточно большого объема информации, описывающей таблицу маршрутизации (что приводит к усложнению и, как следствие, к увеличению цены устройства — узла сети). значительная задержка в уведомлении об изменениях в топологии сети (время, которое уходит на оповещение всех узлов сети об изменении в топологии, прямо пропорционально числу элементов сети).
Резюмируя все вышесказанное, можно отметить, что данный вариант является оптимальным для умеренно мобильных беспроводных сетей. При этом обеспечивается наименьшее время, затрачиваемое на маршрутизацию трафика, но наличие в составе сети одного или нескольких высокомобильных устройств может привести к значительному увеличению накладных расходов от служебных пакетов (причем, чем больше сеть, тем значительнее будет объем этого служебного трафика и меньше эффективность использования доступной пропускной способности). При этом ни количество передаваемых данных, ни их характер практически не влияют на объем создаваемого служебного трафика.
Второй подход - передача с маршрутизацией по запросу - наиболее широко распространен в беспроводных сетях связи, где время передачи информации много больше времени, которое затрачивается на отыскание маршрута. При этом подавляющее большинство протоколов предусматривают вариант с отысканием единственного (чаще всего обеспечивающего минимальную задержку) маршрута от источника к получателю. Основными преимуществами данного протокола являются:
Простота реализации - поиск маршрута сводится к посылке пакета с адресом получателя и ожиданию ответного пакета, содержащего информацию о маршруте. отсутствие необходимости в хранении какой-либо информации о топологии сети, что позволяет значительно упростить (и, как следствие, удешевить) абонентский комплект.
Количество служебного трафика зависит от объема и характера передаваемого трафика и в малой степени от изменений топологии (в случае нарушения маршрута требуется инициировать процедуру поиска нового маршрута).
После отыскания маршрута возможно применение адресной посылки (как и в случае с маршрутизацией на основании таблиц) для более эффективного использования ресурса пропускной способности беспроводной сети.
С другой стороны, при использовании такого подхода приходится сталкивать со следующими его недостатками:
Значительная продолжительность процесса поиска маршрута. При этом с увеличением размера сети время на отыскание маршрута зависит от среднего диаметра сети (в количестве пролетов), а накладные расходы зависят от числа узлов сети.
Во многом случайный характер выбора отысканного пути. В случае, когда в сети от источника к получателю возможна передача данных по двум и более независимым маршрутам (множество узлов, входящих в один маршрут, не является подмножеством множества узлов, входящих в другой маршрут), выбор маршрута в значительной степени зависит от мгновенной нагрузки на его узлах. Именно эта нагрузка определяет задержку при прохождении служебного пакета, а значит и порядок прибытия пакетов на узел-источник.
В случае нарушения соединения узлу-источнику приходится вновь инициировать поиск маршрута, и, как следствие, затрачивать значительное время на его восстановление.
Таким образом, можно сделать следующие выводы: данный подход обеспечивает эффективную маршрутизацию в средне и слабо мобильных сетях, при этом оптимальным является его использование при передаче значительных объемов трафика в пределах одной сессии. Также следует отметить простоту реализации данного подхода в абонентских комплектах. Однако данный подход оказывается неэффективен при необходимости устанавливать большое число соединений для передачи небольших объемов трафика (в этом случае значительно возрастают накладные расходы, и становится существенным вклад задержки на отыскание маршрута в общее время передачи данных). Кроме того, с увеличением числа мобильных узлов значительно возрастают накладные расходы на повторное отыскание путей передачи, и падает эффективность использования пропускной способности сети из-за возникновения задержек на повторное отыскание маршрутов.
По мере увеличения числа узлов в сети соотношение объемов передаваемых полезных данных и служебной информацией начинает уменьшаться, причем, по достижению некоторого предела, объем передаваемых служебных данных становится так велик, что полезный трафик не может быть доставлен за приемлемый промежуток времени. Одним из вариантов решения этой проблемы стала разработка масштабируемых алгоритмов маршрутизации и обмена маршрутной информации, построенных на виртуальном преобразовании топологии сети из «плоской» (одноранговой) в «иерархическую» (многоранговую).
Иерархические алгоритмы маршрутизации для беспроводных сетей построены на идее организации узлов в пределах сети в группы и назначение разной роли для разных узлов в пределах групп. Наиболее популярным является подход объединения узлов в кластер по признаку близости их расположения (Здесь предполагается, что возможность радиосвязи между узлами зависит только от расстояния между ними; в реальности объединение узлов в кластер обычно производят не по близости их расположения, а по удаленности друг от друга, измеряемой в числе пролетов). В каждом кластере выбирается узел-лидер, который обменивается маршрутными данными с узлами-лидерами других кластеров от имени всего кластера. Наиболее популярными иерархическими алгоритмами маршрутизации в беспроводных ad hoc сетях являются CBRP [32], HSR [45], ZRP [42].
Модель виртуального канала передачи данных
Сбор информации о нагрузке, обслуживаемой в кластере, выполняется с использованием данных, получаемых от модуля контроля доступа к среде передачи данных [9]. С учетом различия походов при организации передачи данных в сетях с коммутацией каналов и пакетов, будут отличаться и алгоритмы оценки обслуживаемой нагрузки для каждого из вида передаваемых данных.
При этом в сетях передачи потоковой информации используемым ресурсом является набор выделенных каналов, доступных для организации приема и/или передачи данных (множество каналов приема и передачи могут совпадать, пересекаться или не пересекаться в зависимости от конкретной реализации беспроводной сети). Каждый узел в состоянии отследить и по запросу сообщить статус своих каналов приема передачи (занят или свободен), не имея возможности получить информацию о статусе соседних узлов с использованием средств протокола MAC уровня модели OSI (обмен этой информацией входит в задачи протоколов более высокого уровня). Это «мгновенное значение» доступного ресурса приемо-передачи узла является наблюдаемой величиной и в дальнейшем используется алгоритмом маршрутизации для выбора оптимального маршрута передачи данных.
В сетях передачи пакетных данных наблюдаемой величиной также является мгновенное значение величины обслуживаемой нагрузки. При этом учитываются: исходящая нагрузка, создаваемая узлом при передаче и ретрансляции данных входящая нагрузка, обусловленная приемом данных ожидание доступа - время, в течение которого канал связи является недоступным при обмене данными между другими узлами кластера
В общем случае объем обслуживаемой нагрузки в пакетных сетях является случайно величиной. Мгновенные значения случайной величины формируют некоторую случайную выборку, поэтому для оценки обслуживаемой нагрузки используют не мгновенные, а некоторые средние значения наблюдаемой величины.
С позиций теории систем массового обслуживания (СМО) наиболее важными являются 3 следующих параметра наблюдаемого случайного процесса: первый и второй моменты распределения длин пакетов и среднее количество передаваемых и принимаемых пакетов в пределах кластера за единицу времени. Данный набор параметров выбран из следующих соображений: традиционно для анализа СМО используются модели типа M/MIX, предполагающие, что поток обслуживаемых событий (в данном случае - пакетов с данными) является пуассоновским, а распределение времени обслуживания (в данном случае - длин пакетов с данными) подчиняется экспоненциальному закону. Первое утверждение верно для беспроводных пакетных сетей. Что касается второго утверждения, то в общем случае оно является неверным. Распределение длин пакетов действительно наиболее часто носит экспоненциальный характер, но есть несколько отличий, делающих использование модели M/MIX не вполне актуальным:
1. Наличие минимальной и максимальной длин пакетов. Минимальная длина пакета обусловлена использованием служебных заголовков и контрольных сумм. Максимальная длина позволяет ограничивать объем памяти, выделенной под очередь, и предотвращать излишние повторы, связанные с повторной ретрансляцией пакетов, в которых возникли ошибки при передаче.
2. Наличие защитных интервалов и обмена служебными сообщениями при передаче данных в беспроводных сетях. Как уже было показано во 2-ой главе, передача пакета с данными состоит из нескольких стадий, в том числе «прослушка» среды передачи, посылка служебных сообщений CTS и RTS, собственно передача пакета и защитный интервал после окончания передачи данных. Таким образом, закон распределения времени обслуживания имеет ПРВ, лежащую в отрезке от (7служ + Тмин) до (Тслуж + Тмакс), где
Тслуж — время, затрачиваемое на выполнение служебных операций («прослушка» среды передачи, посылка служебных сообщений CTS и RTS и защитный интервал после окончания передачи данных)
Таким образом, для учета вышеописанных ограничений необходимо перейти от модели M/MIX к модели M/G/1 [16], где длина пакета, и, следовательно, время передачи пакета в сети является некой случайной величиной с произвольной ПРВ. Для такой модели существуют аналитические выражения, связывающие усредненные параметры качества обслуживания (среднее время нахождения пакета в очереди и среднее время передачи пакета) с оценками математического ожидания и второго момента длин передаваемых пакетов и среднего интервала между приемом/передачей пакетов в пределах кластера сети.
В том случае, если в сети передаются пакеты с различными приоритетами, необходимо производить оценку 3-х вышеуказанных параметров для всех типов пакетов. Модель виртуального канала передачи данных
Разрабатываемый протокол предусматривает возможность оценки параметров качества обслуживания при передаче данных через беспроводную сеть. При этом алгоритм, занимающийся оценкой данных параметров, позволяет абстрагироваться от конкретной реализации протоколов передачи данных и доступа к среде, используя представление маршрута передачи данных, как некоторого виртуального канала связи, соединяющего узлы источника и получателя. Данный виртуальный канал характеризуется некоторым набором параметров, позволяющих получить оценку результирующих параметров качества обслуживания при передаче данных.
Виртуальный канал в данном случае удобно представить в виде последовательно соединенных СМО по числу узлов, передающих пакеты с данными на маршруте, соединяющем узел источник с узлом получателем:
Очередь данной СМО будет соответствовать буферу временного хранения сетевого адаптера устройства - узла беспроводной сети, обработка заявки в сервере СМО - передаче данных через разделяемый канал беспроводной сети.
На вход каждой СМО поступает 2 независимых потока заявок. Один поток заявок соответствует пакетам данных, которые уже передаются в пределах данного кластера («белые» заявки), второй поток заявок - это трафик, который необходимо передать через беспроводную сеть («черные» заявки). Заявки из обоих потоков ставятся в общую очередь и обслуживаются в порядке поступления в соответствии с их приоритетом (если он определен). На выходе СМО устанавливается диспетчер, который разделяет поступающие заявки по цвету и передает на вход следующей СМО только «черные» заявки (диспетчер в данной модели полагается идеальным, то есть с нулевой задержкой обработки заявки). Использование такого диспетчера позволяет рассматривать виртуальный канал как набор независимых СМО со своими входными параметрами.
Моделирование передачи пакетных данных
Одно деление временной оси соответствует 10 мкс. Стрелками на нижнем рисунке показаны запросы на поступления пакетов. Сплошная стрелка — передача пакета от 1-го узла 2-му узла, пунктирная стрелка — ретрансляция пакета от 1-го узла 2-м узлом 3-му узлу, стрелка с точкой на конце - передача пакета от 2-го узла 3-му узлу.
На верхнем рисунке показаны соответствующие этим пакетам события в планировщике. Белый прямоугольник с цифрой 1 - передача пакета от 1-го узла 2-му узла, серый прямоугольник с цифрой 1 -ретрансляция пакета от 1-го узла 2-м узлом 3-му узлу, Белый прямоугольник с цифрой 2 - передача пакета от 2-го узла 3-му узлу.
Как было сказано выше, планировщик является псевдопараллельным, то есть одному моменту времени могут соответствовать два не влияющих друг на друга события. Например, для сети из 5 узлов, где передача данных производится между 2 и 0 и 4 и 6 узлами, интервалы между посылками пакетов равны 25 мкс, длительность пакета 10 мкс, а время существования
При разработке системы моделирования беспроводной сети в нее был включен ряд особенностей и ограничений, характерных для данного типа сетей. Так, например, в главе 2 было показано, что для разделяемых каналов передачи данных существует некоторый максимальный предел использования пропускной способности, при превышении которого число конфликтов при передаче приводит к лавинообразному увеличению числа ретрансляций и резкому снижению реальной скорости передачи полезного трафика. Такой режим работы сети является неэффективным и неустойчивым, поэтому в основу работы модели было заложено ограничение на максимальную интенсивность обслуживаемой нагрузки в кластере сети. Данное ограничение позволяет пренебречь ретрансляциями при передаче данных в сети и рассматривать передачу данных узлом сети как СМО с простым входным потоком. Однако наличие подобного ограничения приводит к возможности возникновения отказа в обслуживании - ситуации, когда не существует маршрута между источником и получателем данных такого, чтобы на всем его протяжении средняя интенсивность обслуживаемого трафика была меньше граничной. Данное событие в некотором смысле является аналогичным сбою при передаче данных, связанным с потерей пакета или пакетов, возникающем при перегрузке на одном или нескольких узлах. Однако в отличие от сбоя при перегрузке отказ в обслуживании затрагивает только один поток данных, в то время как сбой при перегрузке затронет все потоки данных, проходящие через перегруженный кластер.
Аналогичная ситуация наблюдается и для выделенных каналов связи. Единственное отличие состоит в том, что отказ возникает из-за невозможности обеспечить заданную пропускную способность на всем маршруте из-за отсутствия необходимого числа выделенных каналов.
В качестве источника трафика в сети был выбран источник самоподобного пакетного трафика Верна Паксона, базирующийся на использовании быстрого преобразования Фурье для формирования последовательности заявок заданной интенсивности и с заданным параметром Херста. Распределение длин поступающих пакетов было получено в результате экспериментальных измерений длин передаваемых пакетов в локальной беспроводной сети компании «ТЕКОМ», в результате получена следующая гистограмма ПРВ длин пакетов: беспроводной сети с корпоративной локальной проводной сетью максимальный размер передаваемого пакета в беспроводной сети был ограничен для предотвращения фрагментации при передаче данных. Средняя длина пакета получилась равной 517 байтам.
Основные характеристика качества работы протокола
Основной задачей протокола управления ресурсами беспроводной сети является эффективное распределение и использование доступной пропускной способности разделяемых и выделенных каналов связи для повышения суммарной пропускной способности сети. Поэтому основным параметром качества работы протокола является максимально достижимая пропускная способность беспроводной сети. Однако, как было показано выше, по мере увеличения обслуживаемого трафика и роста нагрузки, обслуживаемой каждым из узлов сети, повышается вероятность возникновения отказа в обслуживании. Именно этот критерий (частота возникновения отказов в обслуживании) является индикатором нормальной работоспособности сети в целом.
Таким образом, основную характеристику качества работы протокола можно сформулировать, как максимально достижимая пропускная способность сети, при которой среднее количество отказов в передаче данных не превышает некоторого фиксированного значения.
Для экспериментальной оценки параметров качества работы алгоритма управления была предложена следующая схема эксперимента. Эксперимент проводился на сетях 3 размеров - малая сеть (20 узлов), средняя сеть (60 узлов), большая сеть (100 узлов). Узлы сети случайным образом размещаются на квадратной поверхности со стороной X (задается пользователем), радиус видимости узла равен 1. По результатам размещения строится граф сети, который проверяется на связность. В случае если граф является связным, вычисляется степень связности графа, как отношение количество ребер в графе к числу ребер в полносвязном графе с таким количеством вершин. Полученное размещение сохраняется в виде файла с информацией о размещении узлов, степени связности графа и т.п. Для каждого из размеров сетей создано по 100 вариантов уникальных размещений.
Для моделирования передачи данных создаются сценарии передачи данных с использованием генератора пакетного самоподобного трафика. Создаваемый трафик представляется в виде последовательных наборов данных, каждый из которых включает адрес источника, адрес получателя, набор интервалов между поступлениями пакетов, набор длительностей пакетов. Все наборы рассчитаны на соединение длительностью 100 секунд и интенсивностью в 1% пропускной способности канала связи. Для определенности битовая скорость канала связи полагается равной 100 Мбит/сек, таким образом, интенсивность одного потока трафика в среднем составляет около 125 Кбайт/сек.
Для каждого варианта размещения создано по 100 сценариев, по 50000 реализаций самоподобных выборок потока.
Как уже было сказано выше, основной характеристикой работы качества протокола является максимально достижимая пропускная способность сети при заданной частоте отказа в передаче данных. В данной работе было принято решение об установке значения порога Д=1% в качестве приемлемой частоты отказа в передаче данных. В качестве модели закона поступления запросов на передачу данных был выбран пуассоновский поток. Однако математически достаточно трудно оценить, при какой объеме передаваемого трафика будет достигаться такая частота, поэтому в качестве решения для экспериментальной оценки интенсивности обслуживаемого трафика был выбран метод последовательных приближений. Погрешность величины А должна была составлять не более 5% (то есть 0,95% А 1,05%).
Полученная величина интенсивности поступления потоков затем использовалась для моделирования передачи данных через сеть. При этом осуществлялась оценка средней интенсивности передачи данных через указанную сеть, как среднее количество потоков, передаваемых через сеть в установившемся режиме работы. Для этого результаты измерений первых и последних 10% времени моделирования отбрасывались, как имеющие характер переходных процессов при нарастании и убывании объема передаваемого трафика.
Полученные результаты для каждого сценария сохранялись в соответствующий для данного варианта расположения сети файл. Эти значения подвергались усреднению после окончания моделирования и использовались для сравнения эффективности различных алгоритмов и протоколов управления ресурсами.
