Автор: Я.О. Кравченко, Р.В. Мальчева
В данной статье проанализированы различные алгоритмы и протоколы маршрутизации сбора данных в беспроводных локальных сетях, их преимущества и недостатки. Также описаны ключевые тенденции и выделили десятку беспроводных технологий, которые займут доминирующее положение на рынке в качестве корпоративных архитектур нового поколения. Целью работы является обоснование и выбор наиболее эффективной организации передачи данных при проектировании конкретной беспроводной сети, параметры которой должны соответствовать требованиям технического задания.
За последние два десятилетия беспроводные технологии успели вытеснить из обихода множество традиционных средств связи и передачи информации. В ближайшие годы ожидается появление новых типов беспроводных коммуникаций, которые станут основой развития перспективных технологий, например робототехники, автономного наземного и авиатранспорта, медицинских гаджетов [1].
В промышленной автоматизации наибольшее распространение получили три типа беспроводных сетей: Bluetooth на основе стандарта IEEE 802.15.1, ZigBee на основе IEEE 802.15.4 и Wi-Fi на основе IEEE 802.11. Физические уровни модели OSI для этих сетей основаны на соответствующих стандартах IEEE, а протоколы верхних уровней разработаны и поддерживаются организациями Bluetooth, ZigBee и Wi-Fi, соответственно [2].
Быстрое развитие технологий привело к тому, что многие из тех, кто специализировался на беспроводной технологии, увеличили производительность и получили инвестиции и прибыль. Технология быстро развивается и становится более совершенной. В то же время сектор динамично меняется, оставаясь одним из самых важных для европейской экономики с годовым оборотом в 290 млрд. Евро и составляет 4% рабочих мест в Европейском Союзе [3].
Следующее поколение стандартов мобильной связи - 5G или система, также известная как WWWW (Wireless World Wide Web), поддерживает всю беспроводную связь неограниченно. Беспроводные веб-приложения 5G включают в себя полную мультимедийную возможность за пределами скорости 4G. Некоторые из преимуществ этой технологии заключаются в том, что она обеспечивает высокую скорость и быструю передачу данных по сравнению с предыдущими поколениями, поддерживает интерактивные медиа, потоковое видео с потоком голоса, бесконечную передачу данных в рамках последней мобильной операционной системы и т.д. В целом, текущая тенденция 5G технология имеет светлое будущее, потому что она обрабатывает лучшие технологии на доступных мобильных телефонах своим клиентам. Новаторские решения сделать мир более приятным [3].
На сегодняшний день существует множество проблем в области создания беспроводных самоорганизующихся сетей с переменной топологией. Одной из главных является проблема маршрутизации. Каждый тип протоколов маршрутизации потенциально имеет свои преимущества и недостатки при различных условиях (плотности узлов и скорости перемещения) использования.
Целью данной статьи является анализ существующих алгоритмов и протоколов маршрутизации для выбора наиболее эффективной организации передачи данных при проектировании конкретной беспроводной сети.
Алгоритмы маршрутизации применяются для определения наилучшего пути пакетов от источника к при?мнику и являются основой любого протокола маршрутизации. Для формулирования алгоритмов маршрутизации сеть рассматривается как граф. При этом маршрутизаторы являются узлами, а физические линии между маршрутизаторами — р?брами соответствующего графа. Каждой грани графа присваивается определ?нное число — стоимость, зависящая от физической длины линии, скорости передачи данных по линии или стоимости линии.
Большинство алгоритмов маршрутизации можно свести к трем основным алгоритмам [4].
Маршрутизация по вектору расстояния, в соответствии с которым определяются направление (вектор) и расстояние до каждого канала в сети
Маршрутизация на основе оценки состояния канала (также называемый выбором наикратчайшего пути), при котором воссоздается точная топология всей сети (или по крайней мере той части, где размещается маршрутизатор).
Гибридная маршрутизация, объединяющая аспекты алгоритмов с определением вектора расстояния и оценки состояния канала.
Алгоритмы маршрутизации на основе вектора расстояния (известные под названием алгоритмы Беллмана—Форда) предусматривают периодическую передачу копий таблицы маршрутизации от одного маршрутизатора другому. Алгоритм аккумулирует сетевые расстояния и поэтому способен поддерживать базу данных информации о топологии сети, но не позволяет маршрутизатору знать точную топологию всего сетевого комплекса.
Каждый маршрутизатор, использующий алгоритм маршрутизации по вектору расстояния, начинает с исследования своих соседей и открывает наилучший путь до сети пункта назначения на основе информации от каждого соседа. При изменении топологии сети таблицы маршрутизации должны быть обновлены шаг за шагом от одного маршрутизатора к другому.
Таким образом этот алгоритм аккумулирует сетевые расстояния и поэтому способен поддерживать базу данных информации о топологии сети. Но алгоритмы на основе вектора расстояния не позволяют маршрутизатору знать точную топологию всего сетевого комплекса.
Алгоритмы маршрутизации с учетом состояния канала связи (известные под названием алгоритмов выбора первого кратчайшего пути) поддерживают сложную базу данных топологической информации и собирают полные данные о дальних маршрутизаторах и о том, как они соединены друг с другом [5].
В этом типе маршрутизации, каждый маршрутизатор рассылает сообщения, когда он впервые становится активным, список маршрутизаторов к которым он непосредственно подсоединен, а также информацию об активности соединений с каждым маршрутизатором. Другие маршрутизаторы использует эту информацию для построения карты топологии сети, а затем использует карту для выбора лучшего пути к точке назначения.
Протоколы маршрутизации по состоянию канала быстро отслеживают изменения в сети, рассылая триггер обновления только при изменениях в сети, и рассылая периодические обновления о состоянии канала через большие промежутки времени.
Когда соединение изменяет состояние, устройство, которое обнаружит изменения, создает объявления о состоянии канала (LSA), и эти LSA распространяются ко всем маршрутизаторам, использующим алгоритм первоочередного открытия кратчайших маршрутов(OSPF). Каждый маршрутизатор OSPF получает копию LSA, обновляя свою базу данных о состоянии каналов, и пересылая LSA всем соседним OSPF маршрутизаторам. Все OSPF маршрутизаторы обновят свои базы данных, до создания обновленной таблицы маршрутизации, которая отражает новую топологию.
База данных о состоянии каналов, используется для вычисления лучшего пути через сеть, применяя алгоритм выбора кратчайшего маршрута (SPF) также называемый алгоритмом Дейкстра, для построения дерева кратчайших маршрутов из базы данных о состоянии каналов. Лучший путь потом выбирается из дерева кратчайших маршрутов и размещается в таблицу маршрутизации.
Алгоритмы маршрутизации различаются по нескольким ключевым характеристикам:
При разработке алгоритмов маршрутизации обычно ставится одна или несколько из следующих целей:
Под оптимальностью алгоритма маршрутизации понимается его способность выбрать лучший маршрут, что зависит от используемой при вычислениях метрики и удельного веса отдельных параметров.
Кроме того, алгоритмы маршрутизации стараются сделать как можно более простыми (должны эффективно выполнять свои функции с минимальными затратами на передачу служебной информации — как программными, так и аппаратными).
Эффективность алгоритма особенно важна в том случае, когда реализующее его программное обеспечение работает на компьютере с ограниченными физическими ресурсами.
Алгоритмы должны быть надежными, т.е. должны безошибочно работать в непредвиденных условиях, таких как аппаратные сбои, высокая нагрузка и неправильная установка.
Алгоритмы маршрутизации должны быстро сходиться. Под сходимостью понимается процесс согласования оптимальных маршрутов всеми маршрутизаторами. Если вследствие роста, реконфигурирования или отказа изменяется топология сети, то база знаний о сети должна изменяться тоже. При выходе из строя маршрутизатора или возобновлении его работы, другие маршрутизаторы распространяют по всем сетям сообщения об обновлении маршрутов, вследствие чего происходит повторное вычисление оптимальных маршрутов и согласование их между всеми маршрутизаторами.
Принято считать, что сетевой комплекс сошелся, когда все имеющиеся в нем маршрутизаторы работают с одной и той же информацией. Процесс и время, требующиеся для возобновления сходимости маршрутизаторов, меняются в зависимости от протокола маршрутизации. Если алгоритм маршрутизации медленно сходится, то это может привести к появлению петель маршрутизации или к недоступности части сети.
Алгоритм маршрутизации должен по возможности быть гибким, то есть адаптироваться к изменениям полосы пропускания, длины очереди на маршрутизаторе и сетевым задержкам, а также к другим параметрам.
Все алгоритмы маршрутизации для беспроводных сетей малой дальности можно разделить на две группы: алгоритмы общего назначения и специализированные алгоритмы.
Алгоритмы общего назначения разрабатываются без учета специфики конкретной беспроводной сети датчиков. К этим алгоритмам можно отнести AODV и DSR. Они более или менее работоспособны в любой среде, поэтому они используются в стандартных стеках ZigBee разных производителей. Недостатком алгоритмов общего назначения можно считать неоптимальное использование ресурсов сети.
Специализированные алгоритмы маршрутизации разрабатываются для более оптимального решения задач, стоящих перед сетью датчиков. При разработке этих алгоритмов в расчет берутся такие параметры, как топология сети, гомогенность или гетерогенность аппаратных средств сети, плотность размещения устройств, особенности архитектуры узлов датчиков, характер данных, которые собирает сеть и т.д.
Следует отметить, что приемы и идеи, лежащие в основе специализированных алгоритмов маршрутизации, вызванные трудностями и проблемами, которые возникают во время практической разработки и внедрения сетей датчиков. Специализированные алгоритмы должны работать там, где использование алгоритмов общего назначения неэффективно. Но это одновременно является и недостатком специализированных алгоритмов, поскольку сфера их применения ограничена классом задач, который решает специализированная сенсорная сеть. Поэтому задача сбора данных в беспроводных сетях остается актуальной.
Маршрутизация в беспроводных сетях имеет свои особенности: мобильные устройства должны функционировать в автономном режиме, самостоятельно проводя установление связи с другими узлами сети, тем самым выполняя некоторые функции маршрутизатора, узлыпользователи могут когда угодно изменять свое местоположение, тем самым постоянно изменяя топологию и общаясь между собой без создания каких-либо определенных стационарных путей передачи данных. Такие сети носят название MANET (mobile ad hoc networks).
Протоколы маршрутизации MANET делятся на следующие группы:
Особенность протоколов проактивной группы в том, что узлы сети постоянно собирают и обновляют информацию о ее состоянии, обмениваясь ею с соседями. Проактивные протоколы требуют от узла ведения таблиц маршрутизации, где указаны маршруты, которые позволяют достичь любого абонента сети. Специальные алгоритмы используются для поддержки актуальности этой информации. В связи с этим все изменения в топологии сети распространяются в ней. К проактивным протоколам относятся TBRPF, OLSR, DSDV.
Один из наиболее применяемых проактивных протоколов OLSR основан на сборе и распространении служебной информации о состоянии сети. В результате обработки этой информации каждый узел может построить модель текущего состояния сети в виде формального описания графа, вершины которого ставятся в соответствие узлам сети, р?бра – линиям связи. Имея такой граф, любой узел может вычислить «длины» кратчайших путей до всех адресатов в сети и выбрать «оптимальный» маршрут, ведущий к любому конкретному узлу сети.
Данный алгоритм хорошо реагирует на множество непредвиденных событий: спонтанные отказы/восстановления узлов и линий, повреждения и ремонт узлов сети, агрессивные воздействия «внешней среды» с блокировкой отдельных элементов системы, подключения и отключения узлов и линий при оперативной передислокации абонентов. Применение ресурса пропускной способности для служебного трафика протокола OLSR наиболее эффективно в сетях с высокой плотностью узлов.
Протокол DSDV основан на идее классического алгоритма маршрутизации Беллмана-Форда с некоторыми улучшениями. DSDV проактивный, дистанционно векторный алгоритм. Каждый узел поддерживает таблицу маршрутизации, в которой перечислены все доступные направления, количество маршрутизаторов («прыжков») до конечного пункта и номер версии. Узлы периодически передают свои таблицы маршрутизации ближайшим соседям. Узел также передает свою таблицу маршрутизации, если в ней произошло изменение с момента последнего отправленного обновления.
Основная задача алгоритма в том, чтобы исключить возможность создания циклических маршрутов. Для минимизации объема трафика, протокол предусматривает обмен полными таблицами маршрутизации только при серьезных изменениях в топологии сети.
Главным недостатком протоколов на базе DSDV является необходимость регулярной передачи служебной информации между узлами для обновления своих таблиц маршрутизации, что в условиях беспроводной сети ведет к увеличению расхода энергии батареи мобильного устройства и занимает часть полосы пропускания радиоканала, даже когда сеть не используется. Кроме этого, каждый раз, когда изменяется топология сети, создается новый порядковый номер для версии маршрутной информации.
При очень динамичных сетях, возможно переполнение данного параметра, т.е. DSDV не подходит для сетей с быстро изменяющейся топологией.
В протоколах реактивной группы узел ищет путь к пункту назначения только при возникновении необходимости. Для этого существуют две основных операции: поиск маршрута и поддержка маршрута. Когда узел намерен установить связь, и начинает устанавливать маршрут, информацию о доступных каналах он получает по запросам. Для поддержки информации о маршрутах узлы должны реагировать на изменения в топологии сети. Узел, у которого есть информация о каком-то канале, должен стремиться детектировать его отказ, если это происходит. Основные реактивные протоколы: DSR, AODV.
Протокол маршрутизации DSR – протокол динамической маршрутизации от источника. Основные механизмы DSR включают определение маршрута и его обслуживание. Эти два механизма работают совместно, чтобы определять и/или поддерживать маршруты в любую точку сети. При первоначальном определении маршрута пакеты отправляются по всем возможным направлениям и в заголовок добавляется информация о пройденном узле. В итоге по достижению цели, заголовок пакета содержит полностью сформированный маршрут между заданными узлами. В случае возникновения петель, т.е. повторного приема первого пакета, узел уничтожает данный пакет.
Одно из основных преимуществ этого протокола – это избавление от необходимости постоянной рассылки сообщений обновления таблицы маршрутизации. установка маршрута происходит по требованию и строится он только к узлу, который нам требуется, поэтому отсутствует необходимость в поиске путей ко всем узлам, что снижает загруженность сети. Для уменьшения времени передачи промежуточными узлами используется информация из кэша.
Из недостатков можно выделить то, что механизм поддержки маршрута не позволяет восстанавливать разорванные соединения. В кэше может находиться старая информация о маршруте, что будет вести за собой ошибки передачи. Также этот протокол имеет большую задержку при установке соединения, в отличие от табличных протоколов. Производительность теряется прямо пропорционально возрастанию подвижности узлов.
Дистанционно-векторный протокол AODV использует другой механизм для актуализации маршрутной информации [6-10]. Протокол AODV строит таблицы маршрутизации на каждом узле сети для минимизации времени передачи информации между узлами и находит пути маршрутизации независимо от использования маршрутов.
Первым шагом является построение таблиц маршрутизации на каждом узле. В таблице содержится длина кратчайшего пути к каждому узлу в сети через каждый соседний узел. На каждом следующем шаге каждый узел обменивается с соседними узлами информацией о каждом известном ему кратчайшем пути к каждому узлу сети. После некоторого количества шагов, зависящего от количества узлов в сети, таблицы маршрутизации на узлах перестают изменяться, после чего начинается передача данных по кратчайшему найденному пути [6].
Протокол AODV, как и протокол DSR, создает маршруты по необходимости. Тем не менее, AODV принимает традиционные таблицы маршрутизации. Однако используется одна запись на узел назначения, в отличие от DSR, в котором поддерживается несколько записей маршрута для каждого узла назначения. Как и DSDV, AODV предоставляет информацию о нарушении или изменении в сети и предоставляет альтернативные маршруты, но в отличие от DSDV, не требует глобальных периодических объявлений маршрутизации.
Помимо уменьшения количества трансляций в результате разрыва линии связи, AODV также имеет и другие существенные особенности. Каждый раз, когда маршрут от источника к получателю доступен, дополнительные поля заголовка к пакетам не добавляются. Процесс обнаружения маршрута начинается, когда маршруты не используются и/или истекло время жизни. Еще одна отличительная черта AODV заключается в способности обеспечивать однонаправленную, групповую и широковещательную передачу данных.
Гибридные протоколы совмещают в себе механизмы проактивных и реактивных протоколов. Как правило, они разбивают сеть на множество подсетей, внутри которых функционирует проактивный протокол, тогда как взаимодействие между ними осуществляется реактивными методами. В крупных сетях это способствует сокращению размеров таблиц маршрутизации, которые ведут узлы сети, так как им необходимо знать точные маршруты лишь для узлов подсети, к которой они принадлежат.
Также сокращается и объем пересылаемой по сети информации служебного характера, поскольку е? основная часть распространяется лишь в пределах подсетей. Один из самых известных гибридных протоколов носит название HwMP [7].
В отдельную группу протоколов маршрутизации MANET выделяются протоколы, использующие данные о местоположении абонентов сети (протоколы геомаршрутизации). Их основные преимущества заключаются в отсутствии необходимости в хранении маршрутной информации на транзитных узлах, возможностях оптимизировать маршруты, исходя из имеющейся информации о местоположении узлов.
Что касается протоколов маршрутизации MANET, то в данном случае, они должны, по возможности, свести к минимуму время, затраченное на построение маршрута, и время задержки доставки пакетов. А также максимизировать коэффициент доставки пакетов, рассылая как можно меньше служебной информации. При этом они должны успешно справляться с увеличением нагрузки при добавлении узлов.
Обеспечение данных условий требует от протоколов геомаршрутизации использования различных стратегий поиска маршрутов. Например, протокол геомаршрутизации GAF формирует виртуальную сетку покрытой области, в которой каждый узел соотносит себя с ближайшим пунктом на виртуальной сетке [8]. Узлы, связанные с конкретным пунктом на сетке, считаются равнозначными с точки зрения стоимости маршрутизации. Данный подход позволяет увеличивать время жизни сети при увеличении числа узлов. При этом узлы могут изменять свое состояние и переходить от спящего к активному, чтобы балансировать нагрузки.
Существуют три состояния, в которых могут находиться узлы:
Каждый узел в сетке оценивает свое время выхода из не? и посылает данную информацию своим соседям. Спящие соседние узлы корректируют сво? время сна, чтобы сохранить актуальность маршрутной информации. Прежде, чем наступит время, установленное для выхода узла из активного режима, один из соседних спящих узлов «просыпается» и переходит в активное состояние. Таким образом, протокол GAF всегда сохраняет сеть связанной, поддерживая один из узлов в активном состоянии для каждой области на виртуальной сетке.
Геопротокол GPSR — использует информацию о расположении узла для определения маршрута при пересылке пакетов. Пересылка осуществляется на основе «жадной» стратегии. Процесс ретрансляции пакетов промежуточными узлами продолжается до достижения пункта назначения.
В некоторых случаях данная стратегия может привести к ошибкам. Чтобы их исключить применяется «правило правой руки»: текущий узел, в случае отсутствия такового соседнего, более близкого к узлу-приемнику, передает пакеты первому узлу, передвигаясь против часовой стрелки. При увеличении подвижности узлов сети интервал пересылаемых служебных пакетов с геоинформацией, позволяющий держать таблицы маршрутизации в актуальном состоянии, должен быть уменьшен. Однако в действительности подобное приводит к большим накладным расходам, и чтобы их уменьшить, информация о местоположении узла должна отправляться вместе с пакетами данных.
Один из наиболее используемых протоколов географической маршрутизации — LAR [9]. Данный протокол использует информацию о местоположении узла-источника для ограничения области (зоны запроса), где производится поиск маршрута. В итоге количество сообщений о запросе искомого маршрута сокращается.
Также были предложены другие протоколы для пакетных радиосетей, в которых были сделаны попытки соединить преимущества и избавиться от недостатков каждой из групп [10]. Примером является протокол BVR, который использует технологии «жадного продвижения пакетов» (greedy forwarding) и построения системы логических координат, унаследованные от предыдущих протоколов. Его особенностью является создание ряда «маяков» (beacons), случайно выбранных узлов, которые играют роль синхронизаторов в сети.
На их основе строится «дерево» сетевой структуры, определяются показатели маршрутов и осуществляется построение путей к пунктам назначения: поиск ближайшего соседа, назначение его как следующего элемента маршрута и переход до его ближайшего соседа (реализация алгоритму «жадного продвижения»). Отличием BVR является применение при этом не географических, а логических координат. Главное назначение протокола - поддержка соединениий «точка-точка» (point-to-point). Позднее на его основе был разработан протокол LCR.
Выполненный анализ алгоритмов и протоколов маршрутизации данных показал не только их значительное количество и разнообразие, но и постоянное развитие. Существующие беспроводные решения совершенствуются и подстраиваются под нужды разработок нового поколения.
В некоторых случаях, напротив, появление принципиально новых перспективных технологических направлений диктует необходимость в разработке необычных коммуникаций со специфическими требованиями к мощности, экономии энергии, программному управлению, большой автономии и надежности [11]. Специалисты исследовательской компании Gartner проанализировали ключевые тенденции и выделили десятку беспроводных технологий, которые займут доминирующее положение на рынке в качестве корпоративных архитектур нового поколения.