Автор: Климов И. А., студент; Червинская Н. В., доцент каф. «Автоматика и Телекоммуникации» (Донецкий национальный технический университет, г. Донецк, Украина)
Источник: Автоматизація технологічних об’єктів та процесів. Пошук молодих. Збірник наукових праць ХІII науково-технічної конференції аспірантів та студентів в м. Донецьку 14–17 травня 2013 р. - Донецьк, ДонНТУ, 2013. – С. 76–80
Климов И. А., Червинская Н. В. Сравнение протоколов маршрутизации для беспроводных мобильных Ad-Hoc сетей.
Определен класс сетей типа MANET,
выявлены основные проблемы, рассмотрены принципы работы существующих протоколов маршрутизации для сетей этого класса.
Проанализированы основные особенности различных протоколов маршрутизации, выполнено моделирование их работы.
Сегодня интенсивно развивается научное направление в области построения телекоммуникационных систем с переменной топологией сети. Подобные системы получили название MANET (Mobile аd hoc Networks).
Итак, MANET это беспроводные децентрализованные сети, самоорганизующиеся, которые состоят из мобильных устройств. Каждое такое устройство может независимо перемещаться в любых направлениях, и, как следствие, часто разъединяться и подключаться c соседями.
Сети MANET самоорганизующиеся и обладают следующими преимуществами над беспроводными сетями традиционной архитектуры:
– Возможность передачи данных на большие расстояния без увеличения мощности передатчика;
– Устойчивость к изменениям в инфраструктуре сети;
– Возможность быстрой реконфигурации в условиях неблагоприятной электромагнитной обстановки;
Беспроводные сети, построенные на базе мобильных устройств, обладают рядом особенностей:
– Мобильность узлов ведет к дополнительному повышению динамичности топологии сети, так как к возможности обрыва связи из-за помех или включения / выключения узла добавляется вероятность его перемещения;
– Запас источников питания мобильных узлов может быть ограничен, в связи с чем при проектировании аппаратных средств и протоколов необходимо учитывать еще и энергопотребления (особенно это касается сенсорных сетей).
Сегодня можно выделить несколько классов проблем:
– Проблема обеспечения помехоустойчивости;
– Проблема обеспечения безопасности передаваемых данных;
– Проблема общей пропускной способности сетей;
– Проблема эффективности применяемых методов маршрутизации
Для успешного применения в Ad hoc-сетях протоколы маршрутизации должны обладать следующими качествами:
1. Обеспечивать надежную доставку пакетов в условиях постоянно изменяющейся топологии сети,
когда использование классических механизмов гарантированной доставки, как, например, на транспортном уровне в протоколе ТСР, затруднено.
2. Обеспечивать малое время построения маршрута в условиях постоянно изменяющейся топологии сети.
3. Обладать механизмами оперативного обнаружения разрыва маршрута и его восстановления.
4. Обладать высокой масштабируемостью, т.е. обеспечивать высокую производительность сети при различных ее размерах.
5. Поддерживать QoS.
Существующие протоколы маршрутизации по принципу работы можно разделить на:
– Проактивные или табличные (англ. proactive, table-driven). Периодически рассылают по сети служебные сообщения с информацией обо всех изменениях в ее топлогии.
В результате каждый узел сети на основе данной информации строит маршруты до всех остальных узлов и сохраняет их в таблицу маршрутизации, откуда они считываются
при необходимости передачи сообщения какому-либо адресату.
– Реактивные или работающие по запросу (англ. reactive, on-demand). Составляют маршруты до конкретных узлов лишь при возникновении необходимости в передаче им информации.
Для этого узел-отправитель широковещательно рассылает по сети сообщение-запрос, которое должно дойти до узла-адресата. В ответ адресат высылает сообщение-подтверждение,
из которого отправитель узнает необходимый маршрут и записывает его в свою таблицу маршрутизации. Для повторных отправок сообщений данному адресату маршрут просто считывается из таблицы.
Если обнаруживается его разрушение, то запускается так называемая процедура поддержания маршрута, которая фактически заключается в поиске нового маршрута до адресата.
– Гибридные (англ. hybrid). Данные протоколы комбинируют механизмы проактивных и реактивных протоколов. Как правило, они разбивают сеть на множество подсетей,
внутри которых функционирует проактивный протокол, а взаимодействие между ними осуществляется реактивными методами. В крупных сетях это позволяет сократить размеры таблиц маршрутизации,
которые ведут узлы сети, т.к. им необходимо знать точные маршруты лишь для узлов подсети, к которой они принадлежат. Также сокращается и объем рассылаемой по сети служебной информации,
т.к. основная ее часть распространяется лишь в пределах подсетей.
По критерию определения оптимальности маршрута:
1. Протоколы вектора расстояния (англ. distance-vector, hop-count). Всегда считают оптимальным маршрут, содержащий наименьшее число хопов (ретрансляций пакета) между отправителем и адресатом.
2. Протоколы со сложной метрикой маршрутов или протоколы состояния каналов (англ. link-state). Используют комплексную оценку маршрутов по нескольким параметрам, в которые, помимо числа хопов, обычно входят задержка на доставку пакета, пропускная способность канала и др.
AODV (англ. Ad hoc On–Demand Distance Vector) – протокол динамической маршрутизации для мобильных ad-hoc сетей (MANET) и других беспроводных сетей. Есть реактивным протоколом маршрутизации, т.е. устанавливает маршрут к адресату по требованию. Как следует из названия, для вычисления маршрутов используется дистанционно-векторный алгоритм маршрутизации. DSR (Dynamic Source Routing – Динамическая маршрутизация от источника) – протокол маршрутизации для MANET с топологией mesh. Cхож с AODV в том, что также формирует маршрут по-требованию, посредством передачи broadcast-запроса. Однако, он использует явную маршрутизацию, не полагаясь на таблицы маршрутизации на каждом промежуточном устройстве. Явное задание маршрута требует накопления адресов каждого устройства между источником и приемником во время его поиска. Информация о накопленном пути пополняется узлами, обрабатывают broadcast-запросы источника. Изучены таким образом пути и используются для маршрутизации пакетов. В результате, маршрутизируемые пакеты содержат адрес каждого устройства, через который они прошли. Благодаря явном задаче маршрутов, вся информация о них непрерывно обновляется мобильными узлами (пока через них проходит поток данных). Это позволяет избежать необходимости в периодической проверке маршрута (в отличие от AODV). В результате остаются только фазы поиска и поддержки. В любом случае, маршрут генерируется, только если сообщение с запросом достигло намеченного узла адресата (в ответ прилагается цепочка узлов, накопленный в запросе).
OLSR (англ. Optimized Link–State Routing) – протокол маршрутизации для MANET, который также может использоваться в других беспроводных сетях. OLSR - проактивный протокол маршрутизации, использующий обмен сообщениями приветствия и контроля для получения информации о топологии сети. Узлы используют эту информацию для определения следующего скачка в пути маршрутизации пакета. Каждый узел сети m выбирает несколько узлов из числа своих соседей (т.е. из узлов, с которыми у него подключена). В итоге в сети формируется набор узлов MPR (m). Каждый узел сети сохраняет свою таблицу маршрутизации, которую формирует на основании информации о топологии сети. Она распространяется по всей сети с помощью служебных пакетов выбора маршрута Topology Control (TC). Причем только MPR–узлы участвуют в пересылке ТС-пакетов, другие узлы принимают и обрабатывают такие пакеты, но не пересылают их дальше.
При разработке нового протокола 802.11s, рабочая группа фактически пошла по этому пути и создала новый гибридный протокол маршрутизации HWMP. HWMP (Hybrid Wireless Mesh Protocol) на основе хорошо известного протокола дистанционно-векторной маршрутизации по запросу (Ad Hoc On Demand Distance Vector, AODV). Однако в HWMP механизмы маршрутизации работают на MAC-уровне, где доступна информация о соседних узлах и условиях беспроводной передачи, что делает алгоритмы маршрутизации более эффективными. Гибридный протокол маршрутизации HWMP (Hybrid Wireless Mesh Protocol) объединяет в себе два режима построения путей: реактивный и проактивный, которые могут быть использованы как отдельно, так и одновременно в одной сети. При этом используются широковещательные пакеты. Протокол маршрутизации HWMP обязателен для всех устройств стандарта IEEE 802.11s, как протокол по умолчанию. Для выбора оптимальных маршрутов в сети используются различные критерии (метрики). Метрики могут включать в себя такую информацию, как длина пути (количество шагов), надежность, задержка, пропускная способность, загрузка, стоимость передачи трафика и так далее. Наиболее распространенной метрикой является длина пути. Другие протоколы определяют число шагов – сколько сетевых устройств (например, маршрутизаторов) должен пройти пакет на своем пути к получателю. К таким протоколам относятся AODV, DSR, OLSR. Стандарт IEEE 802.11s требует, чтобы все устройства поддерживали метрику времени передачи в канале (Airtime Link Metric). Это обязательное метрика необходима для совместимости устройств. Она задается формулой (1).
где O и Bt – константы, определенные стандартом для различных физических реализаций (802.11a, 802.11b): Bt – число битов в тестовом пакете (8192 бит), O – накладные расходы доступа к каналу, которые включают в себя заголовки пакетов, кадры протоколов доступа и т.д.; r – скорость передачи данных в канале (Мбит / с); ef – вероятность возникновения ошибки (измеряется экспериментально на пакетах длиной Bt). Эта метрика представляет собой оценку времени передачи (в секундах) пробного пакета длиной Bt с учетом возможных ретрансляций при потерях в канале. Способ определения параметров r и ef в стандарте не приводится, однако можно предположить, что для этого должна использоваться периодическая рассылка пробных пакетов длиной Bt = 8192 бит.
Каждый класс протоколов потенциально имеет свои преимущества и недостатки при использовании в условиях мобильных Ad hoc-сетей. Например, проактивные протоколы обладают явным преимуществом перед реактивными во времени построения маршрута. У проактивных протоколов этот процесс, по сути, происходит заранее, и требуется лишь считать маршрут из таблицы, тогда как реактивным протоколам необходимо разослать широковещательный запрос и дождаться подтверждения от адресата. Однако проактивным протоколам необходимо постоянно осуществлять широковещательные рассылки, на что может расходоваться значительная доля пропускной способности сети, особенно в условиях крупных сетей с высокой мобильностью узлов.
Wireless MESH (ячеистые сети, также называемые многоузловыми, mesh peer-to-peer, multi-hop, сетями). Работа сетей Mesh – это подкласс мобильной сети, использующей принцип доступа к узлам в зависимости от ситуации (MANET). Маршрутизаторы могут свободно перемещаться и организовать себя в единую сеть произвольной архитектуры. Таким образом, топология беспроводной сети может быстро и непредсказуемо меняться. Такая сеть может работать автономно или быть связанной с внешней сетью или Интернет. Сети MESH являются, самовосстанавливающиеся: сеть будет работать, даже если в сети имеется неисправный узел или потеряно подключение. В результате такой организации сети получается очень надежная сетевая инфраструктура. Это понятие применимо к соответствующим беспроводным сетям, проводным сетям и взаимодействует на уровне программного обеспечения.
Произведем моделирование работы протоколов маршрутизации и проанализируем полученные результаты
Моделирование работы протоколов будет проводиться в среде имитационного моделирования NS (Network Simulator). В зависимости от размера сети, а именно от количества узлов в ней, определим задержки, возникающие при передачи данных.
Условия моделирования следующие:
Результаты моделирования зависимости задержки передачи данных от количества узлов в сети приведены на рис.2, где d – это время необходимое для передачи данных от источника до получателя, а N – число узлов в сети.
На рисунке 2 видно, что наименьшую задержку в среднем обеспечивает протокол HWMP, а OLSR показывает наибольшую задержку. AODV не смотря на его долгую процедуру инициализации соединения, находится не в самом худшем положении. Это связано с тем, что со стремительным ростом количества ретрансляторов в сети ее динамика очень усиливается и стационарные записи в таблицах маршрутизации OLSR устаревают все чаще, а огромные широковещательные пересылки обновленных таблиц сильно снижают общую полезную пропускную способность. Из-за этого OLSR при большом количестве узлов в сети показывает не столь эффективную работу. Показатели HWMP обусловлены в первую очередь тем, что при построении маршрута по запросу данный протокол имеет наиболее свежую информацию о состоянии сети. Во вторых в протоколе HWMP используется метрика ALM (Airtime link metric), обязательная для стандарта IEEE 802.11s, которая учитывает условия доступа к среде передачи и позволяет найти более эффективный маршрут.
Следует, конечно, отметить, что коэффициент доставки пакетов при AODV может быть заметно выше, чем, например, при OLSR, однако время этой доставки иногда может быть крайне большим, вследствие чего переданные сообщения уже не будут нести той информативности. Поэтому при не больших размерах сети OLSR все же достаточно хорошо справляется с поставленной задачей, а при значительном росте узлов требуется гибридный протокол. Дальнейшим направлением развития MANET является построение систем связи, предназначенных для передачи интенсивного трафика, в том числе и трафика реального времени (голосовой и видеоинформации). Ключевым фактором, влияющим на такие параметры как производительность сети и задержка передачи данных, является работа протокола маршрутизации.
1. Климов И. А. Пояснительная записка к курсовому проекту по дисциплине «Проектирование средств и систем ТКС» [Текст]. / И. А. Климов – Донецк 2013 г. &ndash 65 c.
2. Общие понятия MANET [Электронный ресурс]. – Режим доступа: ru.wikipedia.org/wiki/MANET
3. Винокуров В. М. Маршрутизация в беспроводных мобильных Ad hoc-сетях [Текст] / В. М. Винокуров, А. В. Пуговкин, А. А. Пшенников // Доклады ТУСУРа. Управление, вычислительная техника и информатика. – декабрь 2010 г. – № 2 (22), часть 1. – С. 288–292
4. Зайцев Д. А. Моделирование телекоммуникационных сетей в системе NS [Текст] / Д. А. Зайцев, Т. Н. Шинкарчук // Збiрник Наукових праць ОНАЗ iм. О.С. Попова. – 2006 г. – № 2. – C. 35–43.
5. Bin Huang «Investigating Deployment Strategies for Multi-Radio Multi-Channel Residential Wireless Mesh Networks» [Текст] / Bin Huang, Yan He and Dmitri Perkins // IEEE International Conference on Wireless and Mobile Computing, Networking and Communications. – October 12–14, 2009, Marrakech, Morocco. – Session TS6
6. Терновой М. Ю. «Мобильные сети: IP маршрутизация и алгоритмы MANET маршрутизации»[Электронный ресурс]. – Режим доступа: www.its.kpi.ua/itm/ternovoy
Примечание: источники даны в порядке их появления в тексте.