Исследование методов маршрутизации

Размещено на http://www.allbest.ru/

Содержание

Введение

Глава 1. Общие сведения о технологии ZigBee5

Глава 2. Маршрутизация в беспроводных сетях

2.1 Задача маршрутизации

2.2 Маршрутизация в сетях MANET

Глава 3. Обзор основных протоколов маршрутизации

3.1 Протокол DSDV

3.2 Протокол OLSR

3.3 Протокол FSR

3.4 Протокол AODV

3.5 Протокол AOMDV

3.6 Протокол DSR

3.7 Протокол ZRP

3.8 Выбор протоколов маршрутизации для исследования

Глава 4. Выбор программного продукта для моделирования

4.1 Обзор существующих решений

4.2 OPNET Modeler

4.3 OMNet ++

4.4 NS-2

4.5 NS-3

4.6 COMNET III

4.7 BONes Designer

4.8 QualNet

4.9 Сравнение сетевых симуляторов

Глава 5. Результаты моделирования

5.1 Описание разработанной модели

5.2 Рабочие характеристики

5.3 Анализ полученных результатов для CBR-трафика

5.3.1 Задержки при передаче от источника к получателю

5.3.2 Вероятность потери пакетов

5.3.3 Производительность канала

5.4 Анализ полученных результатов для Pareto-трафика

5.4.1 Задержки при передаче от источника к получателю

5.4.2 Вероятность потери пакетов

5.4.3 Производительность канала

5.5 Анализ полученных результатов для Exponential-трафика

5.5.1 Задержки при передаче от источника к получателю

5.5.2 Вероятность потери пакетов

5.5.3 Производительность канала

Глава 6. Безопасность жизнедеятельности

6.1 Характеристика опасных и вредных факторов

6.2 Организация рабочего места

6.3 Меры по снижению шума

6.4 Вентиляция

6.5 Микроклимат

6.6 Требования по электробезопасности

6.7 Электромагнитное излучение

6.8 Освещение рабочего места

6.9 Пожарная безопасность

Заключение

Приложение А

Приложение Б

Библиографический список



Введение

В последние несколько лет широкое распространение получили сети MANET (Mobile Ad-hoc Network), в частности сети ZigBee, главной чертой которых является самоорганизация. Мобильные узлы могут присоединяться к сети, покидать ее, а также менять свое положение в ней, так что топология будет изменяться постоянно непредсказуемым образом. Каждый узел сети является не только оконечным пользовательским терминалом, но и ретранслятором-маршрутизатором, передавая пакеты других абонентов и непосредственно участвуя в процессе маршрутизации. Данные особенности сетей ZigBee делают невозможным применение в них существующих протоколов маршрутизации для проводных сетей.

На сегодняшний день существует множество различных протоколов маршрутизации для беспроводных персональных сетей. В данной работе будут рассмотрены наиболее популярные из них, а также произведено сравнение данных протоколов для основных параметров QoS: задержек, вероятности потери пакетов и производительности канала.



Глава 1. Общие сведения о технологии ZigBee

В 2001 году Институт инженеров электротехники и электроники IEEE разработал новый стандарт 802.15.4 семейства беспроводных персональных сетей WPAN (Wireless personal area network). В 2002 году был образован альянс ZigBee. Альянс ZigBee -- это консорциум поставщиков полупроводниковых компонентов, производителей готовых решений (в общей сложности более 90 компаний), который осуществляет разработку глобальной спецификации программного стека протоколов ZigBee. [1]

Основными областями применения ZigBee/IEEE 802.15.4 являются передача информации от движущихся и вращающихся частей механизмов (конвейеров, роботов), промышленные системы управления и мониторинга, беспроводные сети датчиков, отслеживание маршрутов движения и местоположения имущества и инвентаря, "интеллектуальное" сельское хозяйство, системы охраны.

В отличие от других беспроводных технологий, где ставится задача обеспечить высокую скорость передачи, большую дальность или высокое качество обслуживания, ZigBee/IEEE 802.15.4 создавался изначально по критериям малой дальности действия, низкой цены, низкой потребляемой мощности, низкой скорости передачи и малых габаритов. Эти свойства идеально соответствуют требованиям к большинству промышленных датчиков. Поэтому ZigBee часто отождествляют с промышленными беспроводными сенсорными сетями WSN (Wireless Sensor Network). Устройства ZigBee применяются в тех случаях, когда Bluetooth оказывается слишком дорогим, и не требуется высокая скорость передачи. [2]

ZigBee, как и Bluetooth, использует нелицензируемый диапазон 2,4 ГГц. Стандарт предусматривает также использование частот 868 МГц в Европе и 915 МГц в США. Максимальная скорость передачи составляет 250 кбит/с в диапазоне 2,4 ГГц. Диапазон 2,4 ГГц разделен на 11...26 каналов шириной по 5 МГц каждый.

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

Соответствие между моделью построения стандарта ZigBee и многоуровневой архитектурой модели OSI представлено в таблице 1.1. Модель ZigBee включает в себя физический уровень (PHY), канальный уровень, состоящий из подуровня доступа к среде передачи MAC и LLC, которые определяются стандартом IEEE 802.15.4, а также сетевой уровень NWK (NetWorK) и уровень приложений APL, состоящий из подуровня поддержки приложений (APplication Support sub-layer - APS), подуровня объектов устройств ZigBee (ZigBee Device Object - ZDO) и объектов Application Objects, определяемых изготовителем ZigBee-устройств. [1]

Таблица 1.1 - Уровни модели OSI сети ZigBee/IEEE 802.15.4

Номер уровня	OSI модель	Сеть	Функции
7	Прикладной	APL (APS, ZDO и Application Objects) ZigBee	Передача сообщений, обнаружение устройств, определение роли устройств
6	Уровень представления	-	-
5	Сеансовый	-	-
4	Транспортный	-	-
3	Сетевой	NWK ZigBee	Безопасность, маршрутизация
2	Канальный	LLC IEEE 802.15.4	CSMA/CA, передача маячков, синхронизация
		SSCS IEEE 802.15.4
		MAC IEEE 802.15.4
1	Физический	PHY IEEE 802.15.4	Радиоканал 2,4 ГГц

Подуровень MAC управляет доступом к радиоканалу, используя метод CSMA/CA. Он также отвечает за передачу маячковых фреймов, синхронизацию и обеспечение надежных методов передачи информации. Подуровень SSCS (Service Specific Convergence Sublayer - "подуровень сближения специфических сервисов") выполняет роль интерфейса между подуровнями LLC и MAC. Подуровень LLC выполняет связь сетевого уровня с уровнем MAC.

Уровень NWK использует методы, обеспечивающие:

· регистрацию в сети нового устройства и исключение его из сети;

· обеспечение безопасности при передаче фреймов;

· указание маршрута фрейма к месту назначения;

· прокладку маршрутов между устройствами в сети;

· обнаружение в сети ближайших соседей;

· запоминание необходимой информации о соседних узлах.

В ZigBee имеются три типа устройств:

· координатор - формирует топологию сети и может устанавливать мосты с другими сетями. В каждой ZigBee сети имеется только один координатор;

· маршрутизатор - работает как промежуточное звено, передавая в нужном направлении данные от других устройств;

· конечное устройство - передает данные координатору или маршрутизатору и не может связываться с аналогичными ему устройствами.

Уровень NWK координатора отвечает за организацию новой сети, когда это нужно и назначение адресов новым устройствам, подключаемым к сети.

Подуровень APS уровня приложений обеспечивает:

· обслуживание таблиц для связывания устройств сети на основе информации о необходимости и возможности связывания;

· передачу сообщений между связанными устройствами;

· определение группового адреса устройств, удаление и фильтрацию сообщений с групповыми адресами;

· отображение 64-битного адреса в 16-битный;

· фрагментацию, перекомпоновку и транспортировку данных.

Подуровень ZDO обеспечивает:

· определение роли устройств в сети (координатор, маршрутизатор или оконечное устройство);

· инициирование или ответ на запрос соединения;

· защиту информации;

· обнаружение устройств в сети и определение, какой сервис они предоставляют.

Топология ZigBee-сети поддерживается уровнем NWK и может иметь форму звезды, дерева, ячеистой сети (mesh) и др.

Рисунок 1.1 - Поддерживаемые топологии сети ZigBee

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



Глава 2. Маршрутизация в беспроводных сетях

2.1 Задача маршрутизации

Задача маршрутизации включает в себя две подзадачи:

· определение маршрута;

· оповещение сети о выбранном маршруте.

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

После определения маршрута, необходимо оповестить о нем все устройства сети. Сообщение о маршруте должно нести каждому транзитному устройству примерно такую информацию: "каждый раз, когда в устройство поступят данные, относящиеся к потоку n, их следует передать для дальнейшего продвижения на интерфейс F". Каждое подобное сообщение о маршруте, обрабатывается устройством в результате создается новая запись в таблице маршрутизации. В этой таблице локальному или глобальному признаку потока (например, метке, номеру входного интерфейса или адресу назначения) ставится в соответствие номер интерфейса, на который устройство должно передавать данные, относящиеся к этому потоку. [3]



Таблица 2.1 - Фрагмент таблицы маршрутизации

Признаки потока	Направление передачи данных (номер интерфейса и/или адрес следующего узла)
…	…
n	F
…	…

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

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

2.2 Маршрутизация в сетях MANET

Сети MANET (Mobile Ad-hoc NETworks), представителем которых является технология ZigBee - это радиосети со случайными мобильными абонентами, реализующие полностью децентрализованное управление при отсутствии базовых станций или опорных узлов. Топология MANET динамична и соединение узлов является случайным. Беспроводные сети, построенные на базе мобильных устройств, обладают рядом особенностей:

· мобильность узлов ведет к дополнительному повышению динамичности топологии сети, поскольку, вследствие помех или включения/выключения узла, к возможности обрыва связи добавляется вероятность перемещения узлов;

· запас источников питания мобильных узлов может быть ограничен, в связи, с чем при проектировании аппаратных средств и протоколов необходимо учитывать энергопотребление (особенно для сенсорных сетей).

Самоорганизующиеся сети MANET обладают следующими преимуществами над беспроводными сетями традиционной архитектуры:

· возможность передачи данных на большие расстояния без увеличения мощности передатчика;

· устойчивость к изменениям в инфраструктуре сети;

· возможность быстрой реконфигурации в условиях неблагоприятной помеховой обстановки;

· простота и высокая скорость развертывания.

В сетях MANET каждый узел может независимо перемещаться в произвольном направлении вследствие чего изменения в топологии сети должны быть переданы другим узлам для поддержания правильной маршрутизации. Например, когда узел MH2 (Рисунок 2.1) вследствие перемещения изменяет своё соединение с MH3 на соединение с узлом MH4, другие узлы сети должны получить информацию о новом маршруте от источника до пункта назначения через промежуточные узлы для пересылки пакетов между MH2 и МН3. [4]

Рисунок 2.1 - MANET сеть

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

· малым временем построения маршрута в условиях постоянно изменяющейся топологии сети;

· высокой надёжностью доставки пакетов в условиях постоянно изменяющихся межузловых связей;

· минимальным объёмом передаваемой служебной информации;

· не допускать формирования петель в маршрутах и иметь механизмы оперативного обнаружения и восстановления разорванных маршрутов;

· обеспечивать высокую масштабируемость сети при сохранении заданной производительности;

· поддерживать требуемый уровень качества обслуживания (QoS).

В соответствие с механизмами формирования таблиц маршрутизации в известных протоколах маршрутизации для Ad-hoc-сетей могут быть выделены три типа протоколов: проактивные (табличные), реактивные (по требованию) и гибридные (комбинированные), (Рисунок 2.2).



Рисунок 2.2 - Классификация протоколов маршрутизации

Проактивные или табличные (proactive, table-driven) протоколы строят маршруты на основе периодически рассылаемых во всех направлениях служебных сообщений с информацией о текущей топологии сети, в соответствии с которой каждый узел выбирает маршруты до всех остальных узлов и сохраняет их в таблице маршрутизации. Проактивные протоколы отличаются минимальной задержкой отправки пакетов узлами, так как используют имеющиеся таблицы маршрутизации, но загружают значительную часть пропускной способности сети для поддержания текущей маршрутной информации.

Реактивные или работающие по требованию (reactive, on-demand) протоколы формируют маршруты, используя механизм рассылки узлами-отправителями широковещательных запросов, приняв которые узлы-адресаты передают сообщения-подтверждения, на основе которых узел-отправитель строит требуемый маршрут, одновременно сохраняя его в своей таблице маршрутизации для повторных передач пакетов данному адресату. В случае обнаружения разрыва маршрута запускается процедура поиска маршрута до требуемого адресата. Реактивные требуют существенно меньшей пропускной способности сети, чем проактивные, но вносят значительную задержку на стадии определения маршрутов между конкретными узлами.

В гибридных (hybrid) протоколах комбинируются механизмы формирования таблиц маршрутизации, свойственные проактивным и реактивным протоколам. В частности, в сети выделяется ряд подсетей, в пределах которых используется один из типов проактивных протоколов, а маршрутизация между подсетями производится на основе реактивных протоколов. Такой подход сокращает размеры таблиц маршрутизации узлов внутри соответствующих подсетей и уменьшает объёмы текущей служебной информации, так как основная её часть циркулирует в пределах подсетей.

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

· наименьшее число ретрансляций пакета (хопов) между отправителем и адресатом (протоколы выбора вектора расстояния);

· комплексная оценка маршрутов по нескольким параметрам, например, минимальное число хопов, задержка на доставку пакетов, пропускная способность канала и др. (протоколы со сложной метрикой);

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



Глава 3. Обзор основных протоколов маршрутизации

3.1 Протокол DSDV

Протокол DSDV (Destination-Sequenced Distance-Vector Protocol) является проактивным, дистанционно-векторным протоколом, основанном на алгоритме Беллмана-Форда с некоторыми улучшениями. Каждый узел составляет таблицу маршрутизации, в которой хранятся данные обо всех доступных направлениях, количестве переходов от одного узла к другому до конечного пункта назначения и номере версии. Этими данными узел обменивается с соседями. Как только в маршрутной таблице узла происходят изменения, он инициализирует передачу маршрутной таблицы.

Для уменьшения потенциально большого объема служебного трафика при обновлении маршрутов используются два типа пакетов: full dump -пакеты с полной информацией о маршрутизации, передаваемые в периоды случайных перемещений узлов, и небольшие расширяемые пакеты с информацией об изменениях с момента последнего полного обновления таблиц маршрутизации. При этом мобильные узлы, используя задержку трансляции могут сократить сетевой трафик и исключить неоптимальные маршруты. [6]

3.2 Протокол OLSR

Протокол OLSR (Optimized Link-State Routing Protocol) решает задачи обнаружения соседних узлов и поддержания соединений с ними, распространения информации о существующих соединениях с соседними узлами по всей сети, поиска кратчайших маршрутов на основании имеющейся на узле маршрутной информации и пошаговой ретрансляции пакетов.

Для обнаружения соседних узлов и поддержания соединения с ними (пара узлов является соседями, если находится в области уверенного приема

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

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

Назовем узел n одношаговым соседом узла x, если узел х находится в области уверенного приема узла n. Узел d, не являющийся одношаговым соседом узла х, назовем двухшаговым соседом узла х, если узел d является одношаговым соседом хотя бы одного одношагового соседа узла х.

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

Все широковещательные служебные сообщения ретранслируются с использованием случайной задержки - джиттера; по умолчанию он выбирается равновероятно из интервала [0, HELLO_INTERVAL/4).

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

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

Ключевой особенностью протокола OLSR, снижающей загруженность сети при широковещательной рассылке, является использование так называемых MPR-ретрансляторов (MultiPoint Relays). Каждый узел выбирает из множества своих одношаговых соседей, с которыми установлено двунаправленное соединение, MPR-ретрансляторы таким образом, чтобы каждый двухшаговый сосед данного узла являлся одношаговым соседом по крайней мере одного из его MPR-ретрансляторов.

MPR-ретрансляторы играют важную роль при распространении маршрутной информации и пересылке широковещательных сообщений. Во-первых, каждый узел, по умолчанию, включает в сообщение TC информацию о двунаправленных соединениях только с теми соседями, которые выбрали данный узел в качестве MPR-ретранслятора. Благодаря этому уменьшается число соединений, информация о которых рассылается по сети. Во-вторых, узел Y пересылает широковещательное сообщение, полученное от его соседа - узла X, только в том случае, если Y является MPR-ретранслятором узла Х. Таким образом снижается число пересылок при распространении одного широковещательного сообщения. [7]



3.3 Протокол FSR

Протокол FSR (Fisheye State Routing) - это проактивный протокол, который использует иерархическую структуру маршрутизации, обеспечивающую сокращение рассылаемой по сети служебной информации путем введения многоуровневых областей. Аналогично OLSR использует механизм сохранения таблиц маршрутизации (локальных карт кратчайших путей) на каждом узле, которыми узел время от времени обменивается с другими узлами.

Отличие заключается в том, что в FSR область рассылки служебных пакетов зависит от числа хопов от источника: чем дальше узлы от источника, тем реже они получают рассылку. Таким образом, достигается уменьшение размеров пакетов, так как передача информация об обновлении таблиц маршрутизации до удалённых узлов производится с меньшей частотой. Использование протокола FSR обеспечивает эффективное масштабирование сети, без необходимости существенного увеличения рассылки служебной информации и сохранении приемлемой точности расчетов маршрутов. [4]

3.4 Протокол AODV

AODV (Ad hoc On-Demand Distance Vector) - специализированный протокол вектора расстояния по запросу. Узел не выполняет поиск маршрута или его поддержку до тех пор, пока ему не понадобится маршрут к другому узлу или пока он не предложит свои услуги в качестве промежуточного узла. Узлы, находящиеся в стороне активного маршрута, не поддерживают информацию о маршрутизации и не участвуют в формировании таблицы маршрутизации. AODV использует маршрутизацию от узла к узлу. Маршрутизация основана на динамической таблице, поддерживаемой в промежуточных узлах. Протокол аналогичен DSR, но DSR использует маршрутизацию источника.

Для определения местных соединений используются локальные сообщения "hello". Таким образом можно уменьшить время отклика на запросы маршрута и инициировать обновление по мере необходимости.

Маршрутам и записям в таблице маршрутизации присваиваются последовательные номера, которые используются для замещения устаревшей информации. Каждый узел поддерживает два счетчика: последовательный счетчик узла и широковещательный ID.

Запрос маршрута AODV инициируется в том случае, когда узел хочет соединиться с другим узлом, но не знает маршрута. Узел-источник посылает широковещательный пакет с запросом маршрута (RREQ) своим соседям. Поля пакета приведены на рисунке 3.1.

Рисунок 3.1 - Поля пакета RREQ

Порядковый номер источника в запросе маршрута показывает "степень свежести" обратного маршрута к источнику. Порядковый номер приемника показывает "степень свежести" обратного маршрута к приемнику.

Каждый узел, принимающий RREQ либо возвращает пакет с ответом маршрута (PREQ), либо пересылает RREQ своим соседям.

Поля source_addr и broadcast_id уникально идентифицируют RREQ. Broadcasr_id инкрементируется для каждого посылаемого пакета RREQ, так

что приемники могут распознать и удалить дублирующие пакеты RREQ.

Если узел не может ответить на RREQ, то он инкрементирует счетчик узлов и сохраняет информацию, необходимую для поддержки обратного маршрута (в протоколе предполагается наличие симметричных соединений). [4]

К необходимой информации относится:

· идентификатор соседнего узла, который прислал данный пакет RREQ;

· IP адрес места назначения;

· IP адрес источника;

· широковещательный ID;

· последовательный номер узла источника;

· время истечения записи для обратного маршрута.

Если узел принимает пакет RREQ и у него есть текущий маршрут к месту назначения, то он отошлет однонаправленный пакет с ответом маршрута (RREP) тому соседу, от которого он принял пакет RREQ. На рисунке 3.2 приведена структура пакета RREP.

Рисунок 3.2 - Структура пакета RREP

Промежуточные узлы будут ретранслировать первый RREP по направлению к источнику, используя кэшированные записи обратного маршрута. Остальные пакеты RREP отбрасываются до тех пор, пока номер dest_sequence_# больше предыдущего, либо dest_sequence_# такой же, но hopcnt меньше (то есть это лучший путь). В конце концов RREP достигает узла, который может использовать соседа, приславшего RREP, в качестве следующего луча для пересылки информации к месту назначения. Кэшированные обратные маршруты будут удаляться в тех узлах, которые не видят пакета RREP.

Причиной изменения маршрута может быть потеря периодических сообщений "hello", авария на связном уровне, ошибка передачи пакета к следующему узлу (может быть обнаружена с помощью прослушивания ретрансляции, если это не конечная точка назначения). Вышестоящий (по направлению к источнику) узел, обнаружив ошибку, передает пакет ошибочного маршрута (RERR) с новым порядковым номером места назначения и количеством лучей, равным бесконечности (недостижимый маршрут). Источник (или другой узел маршрута) может снова построить путь, послав пакет RREQ.

3.5 Протокол AOMDV

AOMDV (Ad hoc On-Demand Multipath Distance Vector) является расширением AODV с возможностью вычисления множества путей без петель и обнаружения разрыва соединений на маршрутах. Входные точки для каждого маршрута к любой точке назначения включают список промежуточных узлов пути с соответствующим счетчиком переходов. Все последующие промежуточные узлы имеют одинаковый порядковый номер. Это позволяет не сбиваться с пути. Для каждого пункта назначения узел хранит объявленный счетчик, который определяется как максимальное число переходов для всех возможных маршрутов к пункту назначения. Этот

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

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

Краткое описание алгоритма работы протокола AOMDV:

1. Пусть S - узел-отправитель, а R1, R2 и R3 - получатели. Прежде всего с помощью алгоритма Дейкстры вычисляется множество путей к получателям.

2. Отправитель посылает запрос маршрута по этим путям к получателям через промежуточные узлы.

3. Все промежуточные узлы получают сообщение RREQ если узел распознает надежный маршрут к получателю, то отправляет отчёт об этом в сообщении RREP к источнику.

4. Если этот текущий узел не является получателем, то проверяет, существует ли доступный путь к требуемому пункту назначения. Если путь существует, он пересылает RREQ соответствующему узлу.

5. После пересылки RREQ получателю текущий узел добавляет свой собственный адрес в список переходных узлов и рассылает обновленное сообщение RREQ.

6. Таким образом, получение сообщения RREP обозначает, что указанный маршрут доступен для установления соединения. Если отправитель получает сообщение RERR, соответствующий маршрут не может быть использован для передачи.

7. При передаче данных с множеством маршрутов параметры QoS рассчитываются для каждого пути отдельно и для соединения используется путь с лучшими параметрами.

8. Избыточные пути идентифицируются, а из подходящих путей, если их несколько, выбирается один случайно. [4]

3.6 Протокол DSR

DSR (Dynamic source routing) - реактивный протокол динамической маршрутизации от источника, как следует из названия, является одним из протоколов маршрутизации по требованию, основанный на концепции построения пути от источника передачи, то есть явную маршрутизацию. Сети на основе DSR полностью самоорганизующиеся и самостоятельно конфигурируемые. В DSR не применяется метод периодической рассылки сообщений как в AODV, таким образом снижается нагрузка на полосу пропускания, сохраняется заряд аккумулятора мобильных устройств, а также удается избежать слишком частого обновления маршрутных данных и обмена слишком большим количеством информации.

Согласно протоколу DSR поиск маршрута и поддержка информации о нем от узла к узлу осуществляется двумя главными механизмами: поиск маршрута и поддержка маршрута. DSR постоянно обновляет кэш маршрутов с целью доступности новых удобных маршрутов. "Поиск маршрута" - механизм, с помощью которого узел S, собирающийся послать некие пакеты узлу D, получает исходный маршрут к нему. Поиск маршрута используется только в том случае, если узел S в первый раз пытается получить доступ к D и не знает пути к нему. Поиск осуществляется отправкой broadcast-запроса RREQ. Во время поиска пути происходит накопление адресов устройств, находящихся между получателем и отправителем. В этом процессе участвуют все узлы, обрабатывающие broadcast-запрос. Информация об адресах узлов, через которые прошли пакеты маршрутизации, записывается в заголовках пакетов. Таким образом, узлы могут получать информацию о состоянии других устройств и существующих маршрутах, при условии, что через них проходят пакеты. Маршрут считается сформированным только в том случае, если пакет достиг адресата, тогда отправляется сообщение-ответ. Ответ может быть отправлен либо по известному маршруту, записанному в памяти узла-получателя, либо по цепочке, записанной в заголовке принятого пакета-запроса. В этом случае накладывается условие на линии связи сети - они должны быть симметричны. "Поддержка маршрута" - механизм, с помощью которого узел S способен обнаружить с помощью существующего маршрута к D, именилась ли топология сети таким образом, что данный маршрут более нельзя использовать вследствие потери соединения на пути. Если разрыв соединения между отправителем и получателем найден, узел-отправитель пытается подыскать другой путь или применяет механизм поиска маршрута DSR.

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

Итак, когда устройство хочет передать какие-то данные другому устройству, к которому нет известного пути, оно инициализирует пакет RREQ, который распространяется по сети. Каждый узел после получения пакета RREQ пересылает его своим соседям, если не является получателем и время жизни пакета не вышло. В случае, если копия этого пакета снова пришла в узел, повторно пересылаться она не будет. Проверка на дубликаты производится по порядковому номеру, записанному в заголовке пакета. Номер этот был присвоен узлом-источником, он запоминается каждым узлом, через который прошел однажды. Таким образом, петли в маршрутах полностью исключаются. Узел-адресат при получении этого пакета RREQ отвечает на запрос сообщением RREP, направляя по обратному маршруту, либо по уже существующему пути, хранящемся в кэше узла. [8]

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

3.7 Протокол ZRP

ZRP (Zone Routing Protocol) гибридный протокол, в котором используется проактивный механизм поиска узлов, находящихся в зоне маршрутизации, определяемой совокупностью узлов с минимальным расстоянием в хопах, не превышающем выбранный радиус зоны. Поиск маршрута вне зоны основан на рассылке служебной информации по её периметру, вместо рассылки по всей сети, и использовании реактивного механизма поиска маршрутов по требованию до пунктов назначения, расположенных за пределами зоны маршрутизации. Проактивный компонент ZRP, называемый внутризоновым протоколом маршрутизации (Intrazone routing protocol, IARP), реализован на основе дистанционно-векторного алгоритма поиска маршрутов, а межзоновый протокол (Interzone routing protocol, IERP) использует механизм запрос-ответ для поиска маршрутов по требованию для взаимодействия с узлами в разных зонах. [4]

3.8 Выбор протоколов маршрутизации для исследования

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

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

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

Среди множества протоколов маршрутизации выделяются AODV и DSR. Эта пара представляет два разных метода маршрутизации - от узла к узлу и от источника. Оба метода реализованы хорошо, что позволяет остановиться на данных протоколах. В добавок рассмотрим AOMDV, так как он является модификацией AODV и более приспособлен к меняющейся среде.



Глава 4. Выбор программного продукта для моделирования

4.1 Обзор существующих решений

В настоящее время существует широкий спектр различных программных средств для моделирования и исследования беспроводных сетей и систем связи:

- OPNET Modeler;

- OMNeT++;

- Ns-2;

- Ns-3;

- COMNET III;

- BONes Designer;

- QualNet.

В перечисленных системах имеются возможности моделирования беспроводных сетей, но в разной степени осуществлена поддержка данных сетей.

4.2 OPNET Modeler

OPNET Modeler является современной средой моделирования дискретных событий и состояний, способной к моделированию сетевых процессов, компонентов, приложений, их более сложных комбинаций. Программа включает большое количество библиотек сетевых технологий и протоколов связи (TCP/IP, ATM, HTTP, Frame Relay, Ip-QoS, 802.11 (Wi-Fi), ZigBee и прочие). Эти библиотеки предоставляют блоки для построения сетевых моделей. Программное обеспечение позволяет осуществлять импорт и экспорт данных о топологии сети и сетевом трафике. Поддерживается моделирование иерархических сетей, многопротокольных

глобальных и локальных сетей, учет алгоритмов маршрутизации. Используется объектно-ориентированный подход, что позволяет пользователю ускорить разработку, внесение изменений и усовершенствований, производить модели для многократного использования. Программа дает возможность автоматически сгенерировать случайный трафик на основе алгоритмов, предложенных пользователем, либо импортировать из форматов реальных трафиков линий. Также поддерживается автоматическая генерация графов и анимации трафика, возможность анализа результатов. Также имеются модели для имитации радиоканала - антенны радиопередатчика, антенны приемника, перемещающиеся объекты узла. Определение модели процесса производится через комбинацию алгоритма работы конечного автомата и операторов языка программирования С/С++. [9]

OPNET Modeler является коммерческой программой, что затрудняет его использование в рамках данной работы.

4.3 OMNeT++

OMNeT++ является системой моделирования на основе дискретных событий. По большей части данная система ориентирована на стандартные проводные и беспроводные сети IP коммуникаций. Данная система широко известна, расширяема и активно поддерживается сообществом своих пользователей.

Для имитационных моделей OMNeT++ применяется язык C++. Так же используется язык высокого уровня NED. Имитационные модели объединяются в крупные компоненты и представляют собой большие системы. В составе симулятора присутствуют графические инструменты для создания моделей и отображения результатов в режиме реального времени.

Симулятор хорошо масштабируем для очень больших сетевых топологий, в этом направлении возможности ограничиваются лишь ресурсами компьютера. В симуляторе определимы задержки для нижних уровней, например, MAC беспроводного канала. [9]

Симулятору не хватает протоколов и должного качества моделирования беспроводных сетей типа MANET. Отсутствует поддержка необходимых для исследования протоколов маршрутизации, так как продукт ориентирован в основном на поддержку IP-сетей.

4.4 NS-2

Ns2 - объектно-ориентированное программное обеспечение, ядро которого реализовано на языке C++. Интерпретатором служит язык OTcL (Object oriented Tool Command Language) - язык сценариев. Присущая обоим языкам иерархия классов полностью поддерживается в ns2, кроме того существует однозначное соответствие между классами двух иерархий.

В ns2 реализовано множество протоколов. Можно найти практически любой, применяемый в современных сетях связи протокол. В качестве примера можно привести MPLS, IPv6, OSPF, RSVP. Кроме того, реализованы дисциплины обслуживания очередей, такие как RED, WFQ, CBQ, SFQ и другие. Среди прочего следует отметить поддержку протоколов маршрутизации в беспроводных сетях, например, AODV, DSDV, DSR и так далее.

Благодаря применению математического аппарата в ns2 реализуются различные виды трафика - от простейшего, подчиняющегося закону Пуассона, до самоподобного. Гибкость ns2 дает возможность пользователю реализовывать собственные математические функции на C++.

В ns2 возможно моделирование возникновения ошибок в процессе передачи данных на канальном уровне, то есть искажения и потери информации. Задать можно как битовые, так и пакетные ошибки, кроме того можно обозначить вероятность ошибки в секунду или использовать пользовательскую модель ошибок. [9]

В ns2 имеется средство для визуализации результатов моделирования - NAM (Network Animator). NAM графически воспроизводит проведенный эксперимент: отображает топологию сети, потоки передаваемых пакетов, узлы, очереди и так далее. NAM работает с данными, полученными по ходу моделирования сети, записываемыми в специальный файл трассировки.

Также в ns2 присутствует средство построения графиков Xgraph, которое можно запустить прямо из скрипта *.tcl сразу по завершению процесса моделирования, получив, таким образом, графическое отображение статистических данных по моделируемой сети.

Ns2 является бесплатной программой, так как изначально разрабатывалась как программное обеспечение с открытым кодом. На распространение, модификацию и использование такого ПО не накладываются никакие ограничения. Другой особенностью ns2 с точки зрения гибкости является поддержка работы во многих операционных системах, таких как Linux, SunOS, Solaris, FreeBSD, Windows.

4.5 NS-3

Ns-3 разрабатывается с 2006 и является современным наследником ns-2, но при этом с ns-2 совершенно не совместим, так как писался с нуля. Так же, как и ns-2 является программным продуктом с открытым кодом и ориентирован на использование в исследовательской среде. Для работы с ним предполагается программирование на С++ и Python. Для визуализации процесса моделирования необходимы внешние программы.

Ns-3 отличает современная архитектура и качественное ядро, а также приближенные к реальности модели и интеграция с реальным ПО. Но в тоже время в программе довольно ограниченная библиотека моделей, отсутствует GUI/IDE. В данном продукте не представлены необходимые протоколы маршрутизации. [10]



4.6 COMNET III

COMNET III - приложение, предназначенное для коммерческого использования, задачей которого является предоставление пользователю возможности оценить характеристики производительности сетей. Описание требуемой сети производится графическим методом через оконный интерфейс, таким образом, от пользователя не требуется навыков программирования. Программа написана на языке MODSIM II, применяющем объектно-ориентированный подход. В COMNET III применяется метод симуляции на основе дискретных событий при выполнении разработанной сетевой модели. Как правило сначала проводится симуляция сети, в результате на выходе получаются статистические распределения и таблицы данных.

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

Система COMNET III оперирует с тремя видами узлов: процессорными узлами, узлами-маршрутизаторами, коммутаторами. [9]

Для моделирования каналов связи необходимо задавать их тип, а также пропускную способность и вносимую задержку распространения. Данные передаются по каналу кадрами, пакеты, соответственно, сегментируются на кадры. Система поддерживает существующие методы доступа к среде, такие как ALOHA, CSMA, Token Ring, FDDI и другие.

Рабочая нагрузка в COMNET III создается источником трафика, при этом каждый узел может взаимодействовать с несколькими источниками трафика разного типа. Существуют источники-приложения, источники вызовов, источники планируемой нагрузки и источники "клиент-сервер".

Алгоритмы маршрутизации, заложенные в программе, работают на основе принципа вычисления кратчайшего пути. Используются статические и динамические алгоритмы. В программе поддерживаются следующие протоколы маршрутизации: RIP, OSPF, IGRP, задаваемые пользователем таблицы маршрутизации. Программа не поддерживает необходимые для исследования протоколы маршрутизации в беспроводных сетях.

4.7 BONes Designer

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

В программе используется принцип симуляции на основе дискретных событий. Моделирование системы происходит с помощью применения блок-диаграмм, имеющих иерархию. Верхний уровень иерархии представляет общие характеристики системы, а нижние - все более и более детальное представление проектируемой сети. Блоки для построения сети содержатся в корневой библиотеке DESIGNER. В состав этой библиотеки входят готовые модели источников трафика, очередей, таймеров, задержек, серверных ресурсов, ресурсов приоритетов качества, генераторов случайных чисел, арифметических и логических операторов и так далее. Блоки самых нижних уровней зовутся примитивами. Они написаны на языке C++ и позволяют задавать структуру исходных данных, выполнять различные операции, такие как модификация полей структуры данных, и возвращают структуры данных на выход. Использование примитивов и более сложных блоков поможет конструировать модели в соответствии с

огромным разнообразием приложений дискретных-событий.

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

В процессе симуляции программа собирает данные о рабочих характеристиках. Точки и типы сбора данных задаются пользователем, также можно использовать значения по умолчанию. Эти данные позволяют получать информацию о задержках, пропускной способности, заполненности буфера, использовании каналов сети. Для графического отображения собранных данных можно использовать Post Processor (PP). PP может получить графики, диаграммы, создать на их основе таблицы. Также PP способен определить медиану, среднее, минимальное и максимальное значения, стандартное отклонение и доверительный интервал.

4.8 QualNet

Пакет QualNet также известен как GloMoSim, новое название получил в 2000 году. Этот пакет является популярным коммерческим продуктом, с большой библиотекой моделей, реализованных на языке C++. Ядро же симулятора написано на языке С. Отличительной особенностью симулятора является наличие параллельного дискретно-событийного ядра и развитый GUI. Программа имеет хорошо разработанные модули для симуляции беспроводных сетей, в том числе MANET, поддерживает большое количество сетевых протоколов. В QualNet широко представлены известные протоколы маршрутизации в беспроводных сетях, такие как AODV, DSR, ZRP, OLSR и другие.

В состав QualNet входит несколько инструментов, позволяющих не только производить симуляцию, но и анализировать и интерпретировать результаты.

QualNet Architect - графический инструмент для разработки сценария и визуализации. В режиме разработки пользователь может выбирать рельеф местности или физическую среду, сетевые соединения, подсети, типы мобильности при использовании беспроводных узлов и другие функциональные возможности сетевых компонентов. Создание сети дается легко, на интуитивном уровне, простыми операциями перетягивания и кликами мыши. Также можно реализовать собственные стеки протоколов для любых узлов. Имеется возможность задавать сетевой трафик и сервисы, используемые сетью. В режиме визуализации можно подробно рассмотреть и проанализировать созданный сетевой сценарий. Во время симуляции можно проследить на разных уровнях передаваемые по сети пакеты и проследить измеренные характеристики.

QualNet Analyzer - инструмент для построения графиков на основе статистических данных, полученных в ходе симуляции. Имеется возможность выбрать получение отчетов по умолчанию, либо настроить формат графиков с нужными статистическими данными. Также имеется поддержка вывода результатов нескольких экспериментов. Все полученные данные экспортируются в электронные таблицы формата CSV.

QualNet Packet Tracer - графический инструмент, который позволяет отображать трэйс-файлы пакетов, созданных в процессе симуляции разработанной модели. Трейс-файлы являются текстовыми файлами в формате XML, содержащими информацию о пакетах и их передвижению по сети. [12]

Пакет совместим с ОС Windows 7, 8 и Linux Ubuntu, CentOs, Red Hat Enterprise Linux.

Данный мощный программный продукт недоступен для проведения исследования вследствие коммерческой лицензии и высокой цены на продукт.

4.9 Сравнение сетевых симуляторов

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

Таблица 4.1 - Сравнение систем моделирования

Среда моделирования	Поддержка сетей ZigBee	Наличие протоколов маршрутизации	Наличие инструментов для обработки результатов моделирования	Доступность
OPNET Modeler	+	+	+	-
OMNeT++	-	-	+	+
Ns-2	+	+	+	+
Ns-3	+	-	-	+
COMNET III	+	-	+	-
BONes Designer	-	-	+	+
QualNet	+	+	+	-

Как видно из таблицы, наиболее подходящей средой моделирования является Ns-2, которая обладает всеми необходимыми характеристиками для данного исследования. Системы QualNet и OPNet также обладают довольно широким набором положительных качеств, имеют множество возможностей, но неприменимы для данной работы, так как не являются доступными.



Глава 5. Результаты моделирования

5.1 Описание разработанной модели

Для проведения исследования была разработана модель ZigBee сети, содержащая 25 узлов, положение которых выбрано случайным образом на определенной территории размером 50 на 50 метров. Узел 10 является передатчиком, узел 0 - приемником.

Рисунок 5.1 - Расположение узлов разработанной сети