SIMPLIFIED ROUTING ALGORITHM IN WI-FI MESH NETWORKS MONITORING

Abstract

This article discusses an algorithm designed for Wi-Fi networks for monitoring parameters of distributed objects.

Full Text

Введение Широкое распространение мобильных технологий и появление большого количества разнообразных мобильных устройств привело к необходимости создания новой технологии, которая обеспечивает надежную связь в условиях изменяющейся архитектуры сети. Для расширения зоны покрытия сети и обеспечения бесперебойной работы станций была разработана технология mesh-сетей (с маршрутизацией на канальном уровне), позволяющая доставлять пакеты между источником и адресатом не только напрямую, но и через промежуточные станции. В настоящее время наиболее проработанными и исследованными являются mesh-сети на базе стандарта 802.11s [1]. Архитектура mesh-сетей использует децентрализованную топологию, где каждый узел сети является не только точкой доступа, но и несет функцию ретранслятора и маршрутизатора. В связи с такими особенностями появляется возможность создания высокоскоростной самоуста-навливающейся и самоорганизующейся беспроводной сети. Основные задачи, которые возникают при разработке и построении беспроводных mesh-сетей, включат в себя оптимизацию потоков трафика и повышение пропускной способности каналов связи. В настоящее время mesh-сети строятся с использованием распространенного беспроводного стандарта Wi-Fi, а также распространенного беспроводного стандарта передачи данных третьего поколения 3G - WCDMA, WiMax [2]. Mesh-сети позволяют увеличивать область беспроводного покрытия за счет вовлечения самих узлов, передающих данные, в процесс маршрутизации, что позволяет сократить количество необходимых устройств доступа и увеличить территорию беспроводного доступа. Топология таких сетей изменяется во времени, поэтому маршрутизация должна осуществляться динамически. Структура пакетов MAC-уровня в mesh-сети Стандарт 802.11 определяет три класса кадров, передаваемых по каналу: информационные, служебные и управляющие. Все они имеют заголовки с множеством полей, используемых подуровнем MAC (Media Access Control). Кроме того, есть поля, используемые физическим уровнем, но они в основном относятся к методам модуляции. Структура пакетов MAC-уровня в mesh-сети (см. рис. 1) аналогична стандартному формату пакетов сетей 802.11 [1-2]. Формат заголовка МАС-пакета в mesh-сети такой же, как и в стандарте IEEE 802.11 (за исключением поля HT Control (High Throughput Control), предназначенного для поддержки оборудования стандарта IEEE 802.11n). Первые три поля заголовка и поле контрольной суммы FCS присутствуют во всех пакетах MAC-уровня. МАС-пакеты в 802.11s отличает mesh-заголовок в начале поля данных, который присутствует в пакетах, данных только тогда, когда они передаются от mesh-узла к mesh-узлу по установленному соединению, а также присоединяется к управляющим пакетам типа (Multihop Action). Mesh-заголовок содержит четыре поля. Байт mesh-флагов регулирует обработку mesh-заголовка. Поле «время жизни пакета в mesh-сети» (Mesh Time To Live - MTL) содержит оставшееся максимальное число шагов между узлами, которое может совершить пакет в mesh-сети. Таким образом, ограничивается время жизни пакета при многошаговой пересылке, что помогает бороться с образованием циклических маршрутов. Номер пакета в последовательности (Mesh Sequence Number) пресекает появление дубликатов пакетов при широковещательной и многоадресной посылке. Поле расширения mesh-адреса (Mesh Address Extension) может включать дополнительные адреса (Адрес 4-6, каждый по 6 байт), что позволяет mesh-пакетам содержать до 6 адресов. Адрес 4 используется в управляющих пакетах «Инфокоммуникационные технологии» Том 12, № 2, 2014 54 Голубничая Е.Ю., Лихтциндер Б.Я. типа Multihop Action (при эстафетной передаче в mesh-сети), поскольку в формате управляющих пакетов МАС-уровня поле Адрес 4 отсутствует. Адреса 5 и 6 служат для передачи адресов конечных отправителя и получателя. Поле управление кадром (Frame control) содержит 11 вложенных полей. Первое из них - «Версия протокола», которое позволяет двум протоколам работать одновременно в одной ячейки сети. Затем следуют поля «Тип» (информационный, служебный или управляющий) и «Подтип» (например, RTS или CTS). Биты «К DS» и «От DS» свидетельствуют о направлении движения кадра: к межсотовой системе распределения (например, Ethernet) или от нее. Бит «MF» говорит о том, что далее следует еще один фрагмент. Бит «Повтор» маркирует повторно посылаемый фрагмент. Бит «Питание» используется базовой станцией для переключения станции в режим пониженного потребления и выхода из этого режима. Бит «Продолжение» говорит о том, что у отправителя имеются еще кадры для пересылки. Бит «W» является индикатором использования шифрования в теле кадра по алгоритму WEP (Wired Equivalent Protocol - протокол обеспечения конфиденциальности). Бит «О» сообщает приемнику о том, что кадры с этим битом должны обрабатываться строго по порядку. Рис. 1. Формат MAC-кадра с Mesh-заголовком Протоколы маршрутизации в mesh-сетях Особенность Mesh-сети заключается в протоколах, использующих специальные алгоритмы, которые позволяют точкам доступа создавать списки абонентов сети, с контролем состояния транспортного канала. При отказе какой-либо точки происходит автоматическое перераспределение трафика по другим маршрутам, что гарантирует передачу трафика адресату с минимальной задержкой. Известные протоколы маршрутизации, как правило, включают в себя механизмы, отвечающие за следующие задачи [3]: - обнаружение соседних станций; - оценку качества канала между соседями; - распространение сетевой информации (информация о топологии и длинах маршрутов); - выбор на основании полученной сетевой информации маршрутов для передачи; - ретрансляцию полученных пакетов по выбранным маршрутам. Сетевая информация может распространяться проактивно (при изменении топологии сети инициируется широковещательная рассылка сообщений об этих изменениях) и реактивно (процессы маршрутизации начинаются по запросу). При выборе протокола маршрутизации важно обеспечивать эффективность его работы в широком диапазоне сценариев, с этой целью необходимо применять гибридный подход, суть которого состоит в том, что каждый узел использует информацию, полученную проактивно, пока не обнаружит, что эта информация неверна (в этом случае узел запускает реактивный сбор сетевой информации). Такой подход применяется в протоколе HWMP (Hybrid Wireless Mesh Protocol -гибридный протокол для беспроводных mesh-сетей) [4]. «Инфокоммуникационные технологии» Том 12, № 2, 2014 Голубничая Е.Ю., Лихтциндер Б.Я. 55 Построение пути означает обновление маршрутных таблиц в узлах mesh-сети либо непосредственно перед передачей данных (по запросу), либо на основе регулярной процедуры, которую инициирует корневой узел. При этом используются широковещательные пакеты. HWMP был разработан на основе хорошо известного протокола дистанционно-векторной маршрутизации по запросу (Ad Hoc On Demand Distance Vector, AODV) [1]. Однако в HWMP механизмы маршрутизации работают на MAC-уровне, где доступна информация о соседних узлах и условиях беспроводной передачи. Это делает алгоритмы маршрутизации более эффективными. Протокол маршрутизации HWMP обязателен для всех устройств стандарта IEEE 802.11s как протокол по умолчанию [5]. Режимы работы протокола HWMP Протокол HWMP может работать в реактивном и проактивном режимах. Далее рассмотрим принцип работы каждого из этих режимов. В реактивном режиме каждый узел генерирует широковещательный PREQ-пакет запроса пути (Path Request). Пути выбираются на основании метрики, для распространения информации о которой служит специальное поле в служебных пакетах запроса пути. По мере продвижения от узла к узлу модифицируется поле метрики пути от текущего узла до отправителя. В итоге формируется полная метрика пути получатель-отправитель. Схема работы протокола HWMP, представленная на рис. 2, повторяется для каждого узла сети. На рис. 2 используются следующие обозначения: - ША - широковещательный адрес рассылки; - R - начальный адрес (адрес начального узла, сгенерировавшего широковещательный пакет); - A, B, N - адреса промежуточных узлов, ретранслирующих широковещательный пакет. В реактивном режиме HWMP каждый узел генерирует широковещательный кадр со своим MAC-адресом в поле начального отправителя (правое поле, адрес R), при этом перед отправкой кадра записывает в левое поле пакета собственный MAC-адрес промежуточного отправителя R. Любой из соседних узлов, получивший этот кадр (на рис. 2 это узел А), не распаковывая его, проверяет, получал ли он уже PREQ-пакет с адре- Рис. 2. Реактивный режим работы протокола HWMP сом начального отправителя R. Если получал, то кадр отбрасывается. В случае если кадр с таким адресом начального отправителя отсутствует, кадр распаковывается, копируется и создается новая строка в таблице MAC-адресов (запись RR). В поле промежуточного отправителя заносится собственный MAC-адрес (адрес узла А) и производится широковещательная рассылка измененного кадра. Алгоритм широковещательной рассылки представлен на рис. 3. Аналогичные действия производит каждый узел сети, и в результате в каждом узле будет сформирована таблица MAC-адресов с числом строк, равным числу узлов всей сети. Далее рассмотрим проактивный режим, который отличается от реактивного тем, что в качестве начального адреса выступает единственный узел, который считается корневым (R). Рассылка управляющих пакетов от корневого узла происходит аналогично реактивному режиму (см. рис. 2). В отличие от реактивного режима в проактивном режиме каждый узел (не широковещательно) отправляет корневому узлу (R) пакет подтверждения PREP (Path Reply) о выполненной команде (см. рис. 4). «Инфокоммуникационные технологии» Том 12, № 2, 2014 56 Голубничая Е.Ю., Лихтциндер Б.Я. тверждении счетчик текущего времени обнуляется. Рис. 3. Алгоритм широковещательной рассылки Рис. 4. Рассылка пакетов подтверждения PREP корневому узлу При рассылке информационных пакетов каждый узел отправляет пакет, находит в своей таблице MAC-адресов адрес назначения (конечный адрес, которому предназначен пакет) и отправляет пакет в адрес достижения, по которому данный коммутатор должен передать пакет, адресованный по адресу назначения. Такие действия происходят, пока пакет не достигнет узла с адресом назначения. Алгоритм работы протокола HWMP представлен на рис. 5. Каждая строка таблицы MAC-адресов имеет «время жизни», несколько превышающее длительность одного цикла генерации PREQ-пакет. Если в течение времени генерации не произойдет подтверждение, то строка с данным адресом назначения уничтожается. При под- Рис. 5. Алгоритм работы протокола HWMP В сетях мониторинга распределенных объектов мало управляющей информации, и она стекается к корневому узлу mesh-сети, поэтому в данных сетях алгоритм маршрутизации может быть заметно упрощен, а именно: - используется метрика времени прихода пакета (пакет, пришедший первым, используется, а остальные игнорируются); - в поле данных широковещательных пакетов, рассылаемых корневым узлом, размещается управляющая информация для остальных узлов, при этом сокращается объем передаваемых данных по сети; - информационные пакеты от остальных узлов к корню, а также пакеты подтверждения о выполнении команд маршрутизируются с использованием стандартных протоколов маршрутизации. Заключение Технология mesh-сетей в настоящее время находится в стадии доработки, поскольку появляются новые методы и алгоритмы маршрутизации. Рассмотренный в статье упрощенный алгоритм маршрутизации позволяет организовать работу Wi-Fi mesh-сети мониторинга распределенных объектов. Управляющая информация передается от корневого узла совместно с ши- «Инфокоммуникационные технологии» Том 12, № 2, 2014 _57 роковещательными пакетами, организующими маршрутизацию, а контрольно-измерительная информация от объектов мониторинга передается к корневому узлу по протоколу HWMP в проактивном режиме. Такой алгоритм позволяет упростить процесс обмена командной информацией между корневым узлом и остальными узлами сети мониторинга.