Содержание к диссертации
Введение
ГЛАВА 1. Задачи проектирования беспроводных сетей 11
1.1. Обзор беспроводных сетей 11
1.2. Физический и канальный уровни передачи данных 16
1.3. Алгоритмы маршрутизации для беспроводных ad hoc сетей 20
1.4. Протоколы маршрутизации для беспроводных сетей 25
1.5. Методы моделирования сетей 42
ГЛАВА 2. Математические модели беспроводных сетей 48
2.1. Параметры беспроводных сетей 48
2.2. Математическая модель беспроводной ad hoc сети 50
2.3. Модели сетевой нагрузки 55
ГЛАВА 3. Разработка и исследование протоколов маршрутизации для беспроводных сетей 68
3.1. Особенности маршрутизации в беспроводных сетях с топологией "бутылочное горло" 68
3.2. Протокол DSFSR (Dislocated Scope Fisheye State Routing) 70
3.3. Критерии оценки качества передачи данных для беспроводных сетей со специальной топологией 73
3.4. Методика оценки и сравнения протоколов маршрутизации для беспроводных ad hoc сетей 77
ГЛАВА 4. Разработка программы имитационного моделирования беспроводных сетей со сложой структурой 82
4.1. Выбор программного обеспечения для имитационного моделирования беспроводных сетей 82
4.2. Разработка архитектуры модели беспроводной сети со сложной структурой в рамках системы имитационного моделирования 85
4.3. Проверка имитационной модели 89
4.4. Оценка качества протоколов маршрутизации для беспроводных сетей со сложной структурой 92
4.4.1. Исследование влияния плотности сети на качество обслуживания 95
4.4.2. Исследование влияния сетевой нагрузки на качество обслуживания 98
4.4.3. Исследование влияния размера пакетов на качество обслуживания 102
Заключение 106
Библиографический список 108
- Алгоритмы маршрутизации для беспроводных ad hoc сетей
- Математическая модель беспроводной ad hoc сети
- Критерии оценки качества передачи данных для беспроводных сетей со специальной топологией
- Оценка качества протоколов маршрутизации для беспроводных сетей со сложной структурой
Введение к работе
Характерной тенденцией современного этапа развития компьютерных сетей является интенсивное внедрение средств беспроводной связи. Электронные приборы с каждым днем становятся меньше, дешевле, потребляя при этом все меньше энергии. При этом большинство устройств оснащается одним или несколькими радиопередатчиками, что делает возможным обмен информацией даже между мобильными и портативными устройствами. Следует также отметить увеличение вычислительных возможностей: даже дешевые миниатюрные устройства могут обладать ресурсами, достаточными для решения широкого класса задач.
Успехи развития технологий уже на современном этапе делают возможным создание и развертывание беспроводных ad hoc сетей, состоящих из тысяч недорогих миниатюрных устройств. Такие сети предоставляют ряд принципиально новых возможностей [18]. В отличие от проводных сетей и систем, беспроводные ad hoc сети обладают такими качествами как мобильность, автономность составляющих элементов, отсутствие необходимости централизованного управления [6]. При этом практически отсутствует снижение функциональных возможностей беспроводных сетей по сравнению с проводными. Таким образом, беспроводные ad hoc сети позволяют эффективно решать множество задач, в число которых входит как передача данных общего назначения, так и работа в составе систем специального назначения. Например, беспроводные сенсорные сети позволяют круглосуточно, в режиме реального времени следить за физическими параметрами некоторой системы. Можно выделить следующие основные преимущества беспроводных сетей перед другими подходами, применяемыми для решения аналогичных задач [6]:
Низкая стоимость. Массовое производство электронных устройств значительно дешевле производства, установки и настройки многокомпонентного комплекса, решающего аналогичную задачу.
Быстрота развертывания. Беспроводная сеть готова к работе практически сразу же после размещения и включения всех устройств.
Высокая эффективность. Благодаря возможности одновременного применения большого количества устройств, беспроводная сеть обеспечивает высокую эффективность при решении практически любых задач, особенно, таких как сбор данных и мониторинг.
Таким образом, в ряде случаев развертывание беспроводной ad hoc сети оказывается экономически более выгодным, чем использование для тех же целей других средств. А прогресс производства вычислительной техники делает беспроводные сети перспективным направлением развития информационных технологий.
Беспроводные ad hoc сети, как новый класс вычислительных сетей, обладают рядом особенностей, которые вызывают ряд проблем на этапе их проектирования, развертывания и эксплуатации [64]. Следует особо отметить большое количество устройств (> 10000), что нехарактерно для классических сетей, единую среду передачи данных, отсутствие централизованного управления [12]. Другой важной особенностью таких сетей является возможная мобильность устройств, а в связи с их большим количеством и воздействием внешних факторов, можно также говорить об их низкой отказоустойчивости. Таким образом, беспроводные сети должны быть самонастраивающимися, а также иметь специализированные протоколы маршрутизации.
В числе научных школ, внесших серьезный вклад в проблематику разработки протоколов для беспроводных сетей, следует перечислить многие исследовательские центры. Среди них особо следует выделить группу MANET (Mobile Ad-hoc Networks) при организации IETF (Internet Engineering Task Force). Основная цель работы этой группы — стандартизация функциональных возможностей протоколов IP маршрутизации, подходящих
для беспроводных систем. При этом принимаются во внимание как статические, так и динамические топологии с большой изменчивостью, связанной с мобильностью устройств и другими факторами.
В калифорнийском университете были проведены исследования сетей со сложной топологией.
В университете Карнеги—Меллон были исследованы особенности протоколов маршрутизации для специальных беспроводных сетей.
В Санкт-Петербургском университете телекоммуникаций им. проф. М. А. Бонч-Бруевича были проведены исследования сенсорных сетей как интеллектуальной инфраструктуры.
В институте радиотехники и электроники им. В.А. Котельникова РАН, г. Москва, были проведены работы по созданию электронных компонентов для беспроводных сенсорных сетей.
В Нижегородском государственном университете им. Н.И. Лобачевского были разработаны новые способы передачи информации в беспроводных сетях, основанные на свойствах среды передачи данных
В университете Палермо были проведены исследования эффективности работы физического и канального уровней передачи данных для беспроводных радиоканалов.
Теоретические и практические аспекты решения задач в этой области рассмотрены в работах таких ученых как: Султанов А.Х., Захаров А.А., Рожков А.В., Аксенов К.А., Чинг-Чуан Чанг, Марио Герла, Цзу-ехи Цзаи.
Основные проблемы при проектировании беспроводных сетей связаны с ограниченными ресурсами дешевых малогабаритных устройств, быстро меняющейся топологии относительно большой сети, ненадежностью беспроводных каналов связи. Для преодоления этих проблем было проведено множество исследований таких сетей. Среди них следует выделить работы исследователей Калифорнийского университета, в частности Чинг-Чуан Чанга - исследования физических свойств беспроводных каналов связи и связанные с ними особенности протоколов маршрутизации, Марио Герлы -
б разработка, оценка и контроль распределенных систем, Цзу-ехи Цзаи -разработка сетевых протоколов для беспроводных систем. Различными научными школами была проведена классификация рассматриваемых сетей, был разработан целый спектр протоколов маршрутизации для различных их типов [59][84].
Недостатком проведенных на сегодняшний день исследований является отсутствие средств оценки и сравнения протоколов маршрутизации. Принятая в настоящее время классификация протоколов не позволяет оценить целесообразность применения конкретных решений в том или ином случае. Таким образом, имеется необходимость создания метода оценки и сравнения существующих и разрабатываемых протоколов маршрутизации для беспроводных ad hoc сетей.
Целью данной работы является разработка метода оценки качества передачи данных в беспроводных ad hoc сетях, включающего в себя критерии оценки качества, математические модели беспроводных сетей, программную реализацию имитационной модели беспроводной ad hoc сети, позволяющую получить значения параметров качества сети, а также методики оценки и сравнения протоколов, обеспечивающей выбор оптимального протокола маршрутизации для беспроводных сетей со специальной топологией.
В рамках диссертационной работы решались следующие основные задачи:
разработка комплексных критериев качества передачи данных для беспроводных сетей в соответствии с классами их целевого использования;
разработка имитационной модели беспроводных сетей, включающей в себя математические модели топологии, модели беспроводных каналов связи, модели сетевой нагрузки и алгоритмы, управляющие конечным устройством;
реализация разработанной имитационной модели с использованием инструментальных средств моделирования сетей;
разработка методики выбора и оценки алгоритмов маршрутизации для беспроводных сетей со сложной структурой.
разработка специализированного протокола маршрутизации для беспроводных сетей со специальной топологией;
оценка эффективности разработанного специализированного протокола маршрутизации для беспроводных сетей со специальной топологией;
Основные научные результаты диссертации заключаются в следующем:
Разработанные критерии комплексной оценки качества передачи данных в беспроводных ad hoc сетях со специальной топологией позволяют получить оценку протоколов маршрутизации в соответствии с решаемой практической задачей.
Предложенная объектно-ориентированная имитационная модель беспроводной ad hoc сети, основанная на потоковой схеме передачи пакетов, включающая в себя математические модели топологии и сетевой нагрузки, модели канального уровня передачи данных, может быть легко модифицирована путем замены части компонентов без изменения ее архитектуры. Это позволяет получить значения критериев оценки качества для широкого класса беспроводных ad hoc сетей.
Разработанная методика оценки и сравнения протоколов маршрутизации для беспроводных ad hoc сетей позволяет разработку на ее основе эффективных специализированных протоколов маршрутизации.
Предложенный специализированный протокол маршрутизации DSFSR для беспроводных сетей со специальной топологией
позволяет увеличить эффективность работы сети, в некоторых
случаях более чем в два раза. Апробация работы. Основные положения диссертационной работы докладывались на:
международной конференции «Computer Science and Information Technologies CSiT'2007», Уфа, 18-21 сентября 2007 г.;
всероссийской зимней школе-семинаре "Актуальные проблемы в науке и технике", Уфа, 20-23 февраля 2008 г.;
международной конференции «Computer Science and Information Technologies CSIT'2008», Уфа, 13-20 сентября 2008 г.;
региональной научно-практической конференции «Безопасность информационного пространства», Екатеринбург, 25-26 декабря 2008 г.;
всероссийской зимней школе-семинаре "Актуальные проблемы в науке и технике", Уфа, 18-21 февраля 2009 г.;
международной научно-практической конференции "Современные информационные технологии и ИТ-образование", Москва, 14-16 декабря 2009 г.;
Публикации.
По материалам диссертации опубликовано 10 печатных работ, в том числе 1 в рецензируемом журнале из списка периодических изданий, рекомендованных ВАК РФ.
Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения и библиографии. Текст диссертации изложен на 117 листах, включая 107 листов машинописного текста, 21 рисунок, 16 таблиц, список литературы (102 названия).
Научная новизна результатов:
1. Разработаны критерии комплексной оценки качества беспроводных ad hoc сетей, ориентированные на практические задачи, решаемые с использованием беспроводных сетей. Данные критерии позволяют, используя интегральные оценки эффективности, проводить
сравнение беспроводных сетей, предназначенных для решения целевых задач разного класса.
Разработана объектно-ориентированная потоковая имитационная модель беспроводной ad hoc сети. Основным отличием модели является использование объектно-ориентированного подхода для представления составляющих её компонентов и связи между ними. Данный подход обеспечивает архитектурное и функциональное соответствие модели рассматриваемой физической системе, простоту внедрения новых и замены существующих классов объектов без изменения концептуальной структуры модели, возможность настройки параметров и выходных данных модели под задачи исследования.
Предложена модель специальной топологии беспроводных ad hoc сетей - "бутылочное горло". Выделены области ее применения, проблемы, особенности. Основной особенностью предложенной топологии является ее ориентация на практические задачи, решаемые с помощью беспроводных ad hoc сетей. Для такой топологии был разработан специализированный протокол маршрутизации.
Практическая значимость результатов:
Разработана программная реализация имитационной модели беспроводной сети со сложной структурой, программно реализованы критерии оценки качества передачи данных в беспроводных ad hoc сетях.
Предложен протокол маршрутизации DSFSR, предназначенный для беспроводных ad hoc сетей со специальной топологией "бутылочное горло". Проведены эксперименты, подтвердившие увеличение эффективности протокола DSFSR в ряде случаев в два раза по сравнению с базовым протоколом.
На защиту выносятся следующие основные результаты:
Критерии комплексной оценки качества передачи данных в беспроводных сетях. Эти критерии позволяют оценивать протоколы маршрутизации в соответствии с решаемой практической задачей
Объектно-ориентированная имитационная модель беспроводной ad hoc сети. Модель основана на потоковой схеме передачи пакетов данных. Она может быть легко модифицирована путем замены части компонентов без изменения ее архитектуры, что существенно расширяет класс беспроводных сетей, для которых можно оценить качество передачи данных.
Методика оценки и сравнения протоколов маршрутизации для беспроводных ad hoc сетей. Применение этой методики позволило повысить эффективность протоколов маршрутизации.
Создание специализированного протокола маршрутизации DSFSR для беспроводных сетей. Его применение позволило более чем в два раза уменьшить суммарную среднюю задержку передачи данных по сравнению с американским протоколом FSR.
Алгоритмы маршрутизации для беспроводных ad hoc сетей
Каждый узел периодически широковещательно распространяет список узлов, с которыми он имеет прямую связь, включая самого себя. Узел определяется как лидер кластера, если он имеет максимальное количество непосредственных соседей среди всех не определившихся узлов. В случае равенства применяется критерий минимального идентификатора. Узел является не определившимся, если он еще не имеет лидера кластера среди своих непосредственных соседей. Узел, уже имеющий лидера, то есть принадлежащий некоторому кластеру, сам уже не может быть лидером. Алгоритм LCC (Least Clusterhead Change) Алгоритм LCC [42] является улучшением двух предыдущих алгоритмов, которые инициируют перевыборы в случае любого изменения состава участников кластера. LCC инициирует перевыборы лидера кластера только в двух случаях: Два лидера кластеров стали непосредственными соседями. Некоторый узел не имеет непосредственной связи ни с одним из лидеров. Таким образом, если некоторый узел попадает в уже сформировавшийся кластер, он не претендует на лидерство в данном кластере. Алгоритм LCC может использовать как критерий минимального идентификатора, так и критерий максимальной связности. Основные особенности вышеописанных алгоритмов: Никакие два лидера кластеров не имеют непосредственной связи друг с другом. Внутри кластера два узла имеют возможность связаться друг с другом не более чем с двумя ретрансляциями. Любой узел является либо лидером кластера, либо имеет непосредственную связь по крайней мере с одним из лидеров. Любой кластер имеет одного и только одного лидера. Алгоритм расширяемого круга (Expanding Ring Algorithm) Алгоритм расширяемого круга [70] начинает работу с «круга» из узлов, достижимых через одну ретрансляцию. После рассылки широковещательных сообщений с заданным TTL (Time То Live) и получения ответов, узел-инициатор оценивает количество узлов — членов кластера. В случае если размер кластера меньше запланированного - TTL увеличивается на 1. В случае, если количество членов больше, чем запланировано, некоторые узла получат уведомление-отказ, и не станут членами кластера.
Быстрый алгоритм [70] позволяет, аналогично предыдущему, сформировать кластер с фиксированным количеством узлов. Пусть В -количество узлов будущего кластера. В этом случае узел-инициатор распределяет бюджет из В-1 участников между своими непосредственными соседями (потомками). Соседние узлы, получив некоторый бюджет, распределяют его между своими соседями. Распространение таких сообщений завершится, когда бюджет будет исчерпан, либо закончатся узлы-соседи, способные стать членами кластера. Каждый узел-потомок, получивший сообщение, должен отправить подтверждение узлу-родителю. Подтверждение отправляется после получения подтверждений от всех собственных узлов-потомков, либо в случае истощения бюджета. Алгоритм завершится, когда лидер кластера получит подтверждение от всех своих потомков. После этого он сможет оценить размер, плотность и диаметр (в терминах количества ретрансляций) сети.
«Настойчивый» алгоритм (Persistent Algorithm) «Быстрый» алгоритм обладает относительно высокой скоростью работы и небольшим количеством служебных сообщений, порядка 2(5-1). Однако при неблагоприятном стечении обстоятельств он может сформировать очень маленький кластер. Наличие большого количества относительно небольших кластеров может негативно сказаться на эффективности работы сети. «Настойчивый» алгоритм [70] устраняет этот недостаток. После получения подтверждений от всех потомков узел не отправляет сразу подтверждение предку. Полученные подтверждения анализируются, и в случае, если количество привлеченных участников меньше выделенного бюджета, остаток бюджета перераспределяется между потомками, полностью исчерпавшими свой бюджет. Таким образом, описанный алгоритм формирует кластер заданного размера, если это возможно.
Три вышеописанных алгоритма позволяют сформировать кластер с фиксированным количеством узлов, однако требуют, чтобы лидер будущего кластера был заранее определен. Протоколы маршрутизации [22], предназначенные для работы в отдельном сегменте вычислительной сети [52], делятся на два класса: Протоколы, использующие вектор-расстояние. Протоколы, использующие состояние каналов.
Для обеспечения маршрутизации, основанной на векторе расстояния, каждый элемент хранит и обменивается с другими таблицей векторов, представляющих собой пару значений - расстояние (количество ретрансляций) и путь (следующий элемент). Недостаток таких протоколов -медленная передача маршрутной информации, а также тенденция к возникновению циклов. Такие протоколы используются обычно в небольших компьютерных сетях. Наиболее популярным протоколом, использующим вектор-расстояние, является протокол маршрутизации RIP [82].
Второй класс протоколов, основанных на алгоритме предпочтения кратчайшего пути, предполагает хранение полной информации о топологии сети, собираемой путем периодической рассылки информации о состоянии каналов связи с соседями. К сожалению, второй класс протоколов требует больших накладных расходов. Наиболее популярным протоколом, использующим состояния каналов, является протокол OSPF [25]. Для беспроводных сетей со сложной структурой, частным случаем которых являются сенсорные и Ad-Hoc сети, характерны: большое количество устройств, их мобильность, небольшая пропускная способность каналов связи, ограничения по вычислительным возможностям. Это значит, что устройства, входящие в состав беспроводной сети, не могут хранить большое количество маршрутной информации, а также часто обмениваться такой информацией. Поэтому для беспроводных сетей используются специальные протоколы маршрутизации. В зависимости от назначения, размера, и других характеристик сети используется один из трех типов протоколов: "плоские", иерархические, а также протоколы, основанные на информации о географическом положении беспроводных мобильных устройств [59]. На рис. 1.2 изображена классификация протоколов для специальных беспроводных сетей.
Математическая модель беспроводной ad hoc сети
Эти протоколы созданы на основе протокола DSDV (Destination Sequenced Distance Vector Routing) [79]. Протокол DSDV использует вектор-расстояния для поиска путей. Этот протокол был специально разработан для мобильных беспроводных сетей и имеет встроенные средства для предотвращения образования циклов.
Протокол DSCR [42], в отличие от DSDV, использует иерархическую организацию сети. Для организации кластеров используется протокол LCC. Для каждого кластера определяется один узел - лидер кластера, узлы, принадлежащие двум или более кластерам, являются шлюзами. Каждый узел хранит таблицу членства в кластере для всех остальных узлов сети. Узлы периодически обмениваются такими таблицами. Для предотвращения распространения устаревшей информации используются порядковые номера для каждой записи таблицы. Для отправки пакета по месту назначения, в таблице членства находится лидер кластера узла назначения, а затем пакет отправляется по найденному адресу. Для нахождения пути до лидера кластера используется протокол DSDV. Таким образом протокол DSCR позволяет значительно уменьшить размер маршрутных таблиц, так как для всех членов некоторого кластера хранится только одна запись в таблице маршрутизации протокола DSDV.
Протокол CGSR [42] аналогичен протоколу DSCR, однако использует иную стратегию формирования путей. Путь между двумя узлами выглядит следующим образом: «Лидер кластера - Шлюз — Лидер кластера - Шлюз...». Протокол CGSR позволяет повысить эффективность работы сети, по сравнению с DSCR, при условии использования специализированных протоколов для реализации канального уровня.
Протокол CGSR формирует пути, неоптимальные с точки зрения количества ретрансляций. В связи с этим возможно увеличение задержки доставки пакетов. Однако данный недостаток компенсируется очень низкой вероятностью коллизий при использовании единой среды для передачи. Данный протокол обеспечивает, относительно хорошую пропускную способность. Следует отметить, что все преимущества данного протокола проявляются только при использовании специализированных протоколов для реализации канального уровня передачи данных.
Иерархический протокол HSR [76] основан на информации о состоянии каналов. В процессе работы он формирует вложенную иерархию, где лидеры кластеров на более низком уровне становятся членами следующего, более высокого уровня. Эти узлы затем также объединяются в кластеры, и т.д. Такая организация сети позволяет уменьшить накладные расходы, связанные с хранением, обработкой и передачей маршрутных таблиц. Каждый узел должен иметь уникальный идентификатор (MAC адрес). Протокол HSR присваивает каждому узлу еще один адрес - HID (Hierarchical ID), который представляет собой последовательность MAC адресов узлов на пути от узла самой верхней иерархии до него самого. Для доставки пакет направляется на более высокий уровень иерархии, пока доставка до узла назначения не станет возможной. Данный протокол обеспечивает относительно плохую производительность, его применение оправдано только для очень больших сетей без особых требований к производительности. Протокол ZRP (Zone Routing Protocol) Протокол ZRP [58] использует одновременно стратегии упреждающего формирования маршрутной информации и формирования такой информации по запросу. Каждый узел имеет вокруг себя некоторую зону из узлов, доступных менее чем через N ретрансляций. Для узлов внутри зоны используется протокол с упреждающим формированием маршрутной информации. В случае необходимости доставить информацию до узла вне зоны, используется протокол, формирующий маршрутную информацию по требованию. Для этого используются пакеты запросов/ответов. Внутри зоны пути до любого узла известны, поэтому запросы распространяются от границы зоны до следующей границы. Такая схема позволяет значительно снизить накладные расходы на хранение и доставку маршрутной информации, так как каждый узел распространяет маршрутную информацию только внутри своей зоны, а запросы с требованием маршрута вне зоны распространяются только узлами, находящимися на границах зон. Комбинированное использование двух подходов для формирования маршрутной информации позволяет протоколу ZRP обеспечивать относительно высокую пропускную способность даже для больших сетей с достаточно интенсивным трафиком. Однако задержка для пакетов в сети с ZRP будет относительно большой. Протокол LANMAR (Landmark Ad Hoc Routing Protocol) Протокол LANMAR [56] разработан специально для сетей, узлы которых проявляют свойство групповой мобильности. Данный протокол способен формировать логические подсети, узлы которых выполняют сходные задачи и имеют тенденцию к групповому движению. LANMAR использует адреса, подобные адресам протокола IP, включающие в себя адрес подсети и адрес узла. В данном протоколе используется понятие меток (landmarks) для отслеживания мобильных подсетей. Каждая группа узлов имеет один, динамически выбираемый узел-метку. Для нахождения путей между узлами-метками используется протокол, основанный на векторе-расстоянии, например DSDV. Протокол LANMAR комбинирует маршрутизацию, основанную на векторе-расстоянии и маршрутизацию с различными областями видимости. Каждый узел определяет свою зону, состоящую из узлов, доступных через N ретрансляций. Для маршрутизации внутри такой зоны используется "плоский" протокол, например FSR. При необходимости доставки пакета до узла вне зоны, он отправляется по направлению к соответствующему узлу-метке. После достижения пакетом границы соответствующей зоны он отправляется по назначению с помощью локального протокола, возможно минуя сам узел-метку. Обычно собственная зона узла-метки включает в себя всю подсеть, иначе необходимо использовать дополнительные правила формирования маршрутных таблиц.
Протокол LANMAR позволяет уменьшить как размеры маршрутных таблиц, так и накладные расходы на доставку и обработку маршрутной информации. Этот протокол обеспечивает относительно хорошие характеристика пропускной способности и задержки для пакетов /78/. Сравнение иерархических протоколов маршрутизации
Существенное преимущество иерархических протоколов - уменьшение накладных расходов, связанных с доставкой маршрутной информации. Описанные выше протоколы используют для этого различные подходы. Протоколы ZRP и LANMAR используют неявное деление сети на логические части. Эти протоколы хорошо работают в относительно небольших сетях, однако с увеличением размера эффективность сети значительно уменьшается. В этом случае протокол ZRP начинает активно использовать стратегию поиска путей по запросу, a LANMAR генерирует больше служебного трафика, связанного с межгрупповой маршрутизацией. Протокол HSR, используя многоуровневую иерархию, значительно уменьшает накладные расходы на маршрутизацию, даже в больших сетях. Однако в связи с использованием логического разделения сети на части, слабо зависящего от физического расположения узлов, найденный маршрут может оказаться далеко не оптимальным. Протоколы DSCR и CGSR уменьшают накладные расходы за счет использования алгоритма, основанного на векторе-расстоянии. Протокол CGSR имеет преимущества только при условии использования специализированных протоколов для реализации канального уровня. В противном случае необходимо использовать DSCR. В таблице 1.3 приведены основные особенности иерархических протоколов [59].
Критерии оценки качества передачи данных для беспроводных сетей со специальной топологией
Для оценки качества сетей и их каналов обычно используются такие параметры как пропускная способность и задержка. Эти параметры позволяют оценить качество сети общего назначения для клиента некоторого узла, однако не позволяют произвести комплексную оценку качества сети. Беспроводные сети со сложной структурой состоят из относительно большого количества узлов и каналов связи, и при этом в общем случае не являются сетями общего назначения. Таким образом эффективность беспроводной ad hoc сети невозможно оценить лишь с помощью показателей качества для одиночного канала или клиента узла.
Для оценки производительности протоколов маршрутизации для беспроводных ad hoc сетей как правило используются особые методы [40] [49] [66]. Для сети, которая использует исследуемый протокол маршрутизации, разрабатывается сценарий ее работы. Такой сценарий включает в себя элементы сетевой топологии, такие как расположение источников трафика, а также выбор узлов - конечных приемников трафика [66]. Адекватность разработанного сценария проверяется путем анализа распределения длины маршрута между источником и приемником [40]. Для оценки производительности протоколов используются следующие характеристики: Коэффициент доставки пакетов — отношение количества доставленных пакетов к количеству отправленных. Такой коэффициент используется для оценки потерь пакетов, позволяя оценить максимальную пропускную способность сети. При оценке протокола маршрутизации это значение позволяет оценить его завершенность и корректность [40]. Накладные расходы при маршрутизации. Здесь оцениваемой величиной является общее количество служебных пакетов, сгенерированных протоколом маршрутизации за время моделирования. Такой параметр позволяет оценить масштабируемость протокола маршрутизации, его эффективность для работы в сетях с узкополосными каналами, а также способность экономно расходовать энергию автономных устройств. Оптимальность найденного пути. В этом случае для оценки протокола используется разность между длиной найденного и оптимального маршрутов. Такой параметр позволяет оценить, насколько протокол эффективно использует ресурсы сети [40]. Средняя задержка передачи пакета. Включает в себя все возможные задержки, такие как ожидание в очередях, задержки на канальном уровне, и т.д. Такой параметр может служить для оценки эффективности протокола при передаче best-effort трафика [49]. Описанные методы оценки производительности не позволяют комплексно оценить качество передачи данных для исследуемого протокола. Это связано с тем, что, во-первых, для оценки используется несколько частных значений, без объединения их в единый комплексный критерий. Во-вторых, сценарий работы сети плохо формализуем, и требует индивидуальной реализации в каждом конкретном случае. Однако тот факт, что назначение и условия работы такой сети известно еще во время ее проектирования, а область применения заранее определена, делает возможным разработку комплексных критериев оценки качества передачи данных, ориентированных на сеть со специальной топологией. Таким образом, были разработаны три типовых критерия оценки качества передачи данных для сетей с топологией "бутылочное горло": Критерий максимального среднего времени доставки: М(НШ) - математическое ожидание времени передачи пакета от узла і до базовой станции. Включает в себя время непосредственной передачи, а также другие задержки, такие как время инициализации передачи канальным уровнем, ожидание в очередях узлов-маршрутизаторов, и другие. Данный критерий учитывает только успешно доставленные пакеты. Поэтому для сети должен быть определен максимальный процент потери, зависящий от решаемой задачи. Например, для приложений не реального времени для высокого качества обслуживания потери должны составлять не более 2.5% [81]. Такой критерий подходит для систем, где единичная задержка доставки пакета некритична, однако в целом от сети ожидается эффективная производительность. Можно выделить следующие типы систем, для которых будет применим рассматриваемый критерий оценки качества: Системы с отложенной обработкой результатов. Для таких систем характерно наличие двух этапов работы: сбор данных и обработка данных. Во время первого этапа данные, полученные беспроводными устройствами сети, доставляются на некоторый центральный узел и сохраняются в базе данных. Во время второго этапа данные обрабатываются либо преобразуются для последующего использования. Следует отметить, что данные этапы слабо связаны по времени их проведения, а второй этап может проводиться не самой сетью, а некоторым внешним вычислительным центром. Сети, предоставляющие для беспроводных клиентов доступ к некоторым сервисам либо к сети Интернет. Здесь для каждого клиента, независимо от его места в сетевой топологии необходимо обеспечить некоторый гарантированный уровень качества обслуживания.
В качестве примеров можно привести: систему, собирающую информацию о физических параметрах исследуемых объектов. С помощью таких систем можно изучать как естественные особенности некоторой территории, так и промышленные объекты. Информация, полученная с помощью таких систем, изучается в дальнейшем в условиях офиса, лаборатории, и т.д. Другим примером является сеть, предоставляющая доступ к сети Интернет для ее клиентов. Здесь для каждого клиента, независимо от его места в сетевой топологии необходимо обеспечить некоторый гарантированный уровень качества обслуживания, однако допускаются кратковременные ухудшения качества передачи данных. Критерий максимального времени доставки:
Оценка качества протоколов маршрутизации для беспроводных сетей со сложной структурой
В рассматриваемой сети битовая скорость передачи данных между устройствами составляет 1024 Кбит/с. С учетом того, что все данные доставляются в единый центр обработки, а сеть состоит из 100 устройств, максимальная скорость передачи для одного устройства составляет за ошибок, коллизий и накладных расходов на работу протоколов такая скорость практически недостижима, и будет использоваться только как мера оценки верхней границы скорости передачи.
В процессе доставки пакета последний пройдет через несколько узлов: источник - маршрутизатор 1 - маршрутизатор2 - ... - маршрутизаторК -приемник. При каждом прыжке пакет будет занимать среду дважды - во время приема, и во время передачи. Таким образом за 100% затрузку сети примем скорость передачи 656 байт в секунду для каждого устройства.
В первом эксперименте будет исследовано поведение сети при изменении частоты появления пакетов.
В этом эксперименте исследовалось влияние частоты появления пакетов с полезными данными на качество обслуживания сети. Исследование проводилось для сети с большой плотностью, так как в такой сети протоколы маршрутизации показывают наиболее сходные значения качества, т.е. минимизированы остальные факторы, влияющие на эффективность работы сети. Значения критериев качества обслуживания представлены в таблице 4.4.
При увеличении частоты появления данных увеличивается время доставки пакетов через канальный уровень передачи, так как среда большее время занята, а также возрастает вероятность коллизий. Однако при уменьшении частоты появления полезных данных эффективность работы сети может уменьшиться, так как при редком появлении пакетов протоколу маршрутизации сложнее вычислить метрики каналов. Это может выражаться в неправильном назначении метрик для каналов, а также в их более частых изменениях. Такие особенности назначения метрик могут провоцировать выбор неверных маршрутов, а также появление циклов при доставке пакетов до узла назначения. Протокол DSFSR в ряде случаев показывает лучшую эффективность, так как быстрее реагирует на изменение состояния каналов.
В данном эксперименте проверялась зависимость качества обслуживания сети от размера пакетов с полезными данными. При этом сетевая нагрузка изменялась от 5.3% до 80%. Результаты представлены в таблице 4. При увеличении размер пакетов наибольшее влияние на эффективность оказывают, как правило, не протоколы маршрутизации, а технология доступа к среде передачи. Однако в любом случае, используемый протокол маршрутизации оказывает влияние на качество работы сети, так как только от него зависит количество служебного трафика, а также выбранный маршрут для доставки, который в свою очередь зависит от метрики канала, определяемой, в том числе, размером передаваемых пакетов.
Как видно из результатов эксперимента, в некоторых случаях протокол DSFSR обеспечивает лучшее качество обслуживания, так как модифицированный способ доставки маршрутной информации позволяет более эффективно использовать каналы передачи. Однако возможны ситуации, когда такой алгоритм показывает меньшую эффективность, так как увеличивает накладные расходы.
В данной главе была реализована имитационная модель беспроводной ad hoc сети. Были рассмотрены существующие системы имитационного моделирования, их достоинства и недостатки. Для моделирования рассматриваемых сетей была выбрана система DaSSF. С помощью реализованной имитационной модели были получены параметры качества передачи данных для сетей, использующих протоколы FSR и DSFSR.
Проведенные в рамках диссертационной работы исследования образуют теоретическую и практическую основу для проектирования беспроводных ad hoc сетей, а также разработки для них новых эффективных протоколов маршрутизации.
В качестве исследовательской базы при выполнении диссертационной работы использовалась учебно-вычислительная лаборатория кафедры вычислительной механики и информационных технологий Челябинского государственного университета.
