АРХИТЕКТУРА  И  ГИБРИДНЫЙ  ПРОТОКОЛ  МАРШРУТИЗАЦИИ  ДЛЯ  БЕСПРОВОДНЫХ  ЯЧЕИСТЫХ  СЕТЕЙ  НА  БАЗЕ  СТАНДАРТА  IEEE  802.11S

Дугаев  Дмитрий  Александрович

аспирант  Сибирского  Государственного  Университета  Телекоммуникаций  и  Информатики,  г.  Новосибирск

E-mail: 

ARCHITECTURE  AND  HYBRID  ROUTING  PROTOCOL  FOR  WIRELESS  MESH  NETWORKS  BASED  ON  IEEE  802.11S

Dmitry  Dugaev

graduate  student  Siberian  State  University  of  Telecommunications  and  Information  Sciences,  Novosibirsk

АННОТАЦИЯ

В  последнее  время  все  большую  популярность  приобретает  концепция  беспроводных  ячеистых  сетей  (WMN  —  Wireless  Mesh  Networks).  В  рамках  статьи  будет  произведен  обзор  стандарта  802.11s,  позволяющего  формировать  беспроводные  ячеистые  сети  на  основе  Wi-Fi  устройств.  Данная  работа  представляет  собой  обобщенное  описание  архитектуры  сети,  особенностей  функционирования  и  принципов  маршрутизации  в  802.11s,  выполненное  на  основе  изучения  российских  [4]  и  зарубежных  работ  [1—3]  по  данной  тематике.

ABSTRACT

Recently,  the  concept  of  Wireless  Mesh  Networks  (WMN)  is  getting  more  and  more  popular.  In  this  paper,  the  author  will  provide  a  survey  of  IEEE  standard  802.11s,  which  allows  forming  a  Wireless  Mesh  Network  structure  based  on  Wi-Fi  compatible  devices.  The  article  represents  a  general  description  of  network  architecture,  functioning  aspects  and  routing  techniques  in  802.11s,  which  is  performed  based  on  investigating  Russian  [4]  and  foreign  works  [1—3]  on  the  corresponding  topic.

Ключевые  слова:  беспроводные  ячеистые  сети  (WMN);  стандарт  802.11s;  реактивный  и  проактивный  режимы  маршрутизации;  протокол  HWMP.

Keywords:  wireless  mesh  networks  (WMN);  802.11s  standard;  reactive  and  proactive  routing  modes;  HWMP  protocol.

Стандарт  802.11s.  Основные  цели  и  задачи.

Стандарт  IEEE  802.11s  нацелен,  прежде  всего,  на  оптимизацию  маршрутов  в  сетях  с  беспроводной  ячеистой  топологией,  а  также  на  интегрирование  возможностей  WMN  в  существующие  сети  802.11  на  MAC  уровне  [4].  Поэтому,  основными  целями  стандарта  802.11s  являются:

·создание  беспроводной  системы  распределения  (wireless  distribution  system)  с  автоматическим  обновлением  топологии  и  конфигурацией  пути/маршрута;

·создание  сетей  небольших  размеров  (около  32  узлов);

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

·обеспечение  последующей  расширяемости  сети;

·обеспечение  совместимости  с  протоколами  более  высокого  уровня.

Рисунок  1.  Архитектура  WMN  сети  на  базе  802.11s

Структура  сети  WMN  на  базе  стандарта  802.11s  изображена  на  рисунке  1.  Она  состоит  из  четырех  классов  устройств  [2]:

1.  Mesh  Point  (MP):

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

2.  Mesh  Access  Point  (MAP):

Узел  ячеистой  сети  с  функцией  точки  доступа  (AP),  что  позволяет  различным  беспроводным  устройствам,  поддерживающим  стандарт  802.11,  подключаться  к  WMN.

3.  Mesh  Portal  (MPP):

Граничный  узел  сети  (шлюз),  который  позволяет  связать  ячеистую  сеть  с  внешней  проводной  или  беспроводной  сетью  (External  Network).

4.  Stations  (STA):

Беспроводные  устройства  с  поддержкой  стандарта  802.11,  которые  подключаются  к  MAP.

Маршрутизация  в  сетях  802.11s.

Существуют  три  основных  типа  протоколов  маршрутизации,  которые  могут  быть  использованы  в  WMN:  реактивные,  проактивные  и  гибридные  [4].  Основное  различие  между  ними  заключается  во  времени  установления  пути/маршрута  между  двумя  узлами.  В  протоколах  с  реактивным  режимом  маршрутизации,  путь  до  узла  назначения  устанавливается  в  момент  необходимости  передачи  данных,  тогда  как  в  проактивных  протоколах,  маршруты  практически  до  всех  узлов  уже  заложены  и  есть  в  маршрутной  таблице.  Гибридные  протоколы,  такие  как  HWMP  (Hybrid  Wireless  Mesh  Protocol  —  о  нем  подробнее  будет  сказано  ниже)  умеют  работать  в  обоих  режимах  —  реактивном  и  проактивном.

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

Поэтому,  в  сетях  WMN  с  относительно  стабильной  топологией  по  сравнению  с  классическими  ad-hoc  сетями,  более  привлекательно  выглядят  проактивные  (RA-OLSR)  и  гибридные  (HWMP)  протоколы  маршрутизации  [1].

Метрики  и  профили.

В  стандарте  используется  механизм  профилей.  Он  необходим  для  обеспечения  совместимости  устройств  с  различными  технологиями  от  различных  производителей.  Формат  профиля  имеет  следующий  вид:  {идентификатор  профиля;  идентификатор  протокола  маршрутизации;  идентификатор  метрики}.  Обязательным  является  использование  протокола  маршрутизации  HWMP  и  метрики  Airtime  Link  Metric  [1].  Однако  стандарт  даёт  возможность  производителям  использовать  другие  протоколы  и  метрики,  или  разрабатывать  свои  проприетарные  протоколы  маршрутизации.

В  качестве  Airtime  Link  Metric  используется  время  передачи  пакета  до  соседнего  узла,  которое  вычисляется  по  формуле  [1]:

                                           (1)

где:  O  —  константа,  определяющая  время  доступа  к  каналу  в  зависимости  от  физической  реализации  (802.11a,  802.11b);

B_t  —  число  битов  в  тестовом  пакете  (8192);

r  —  скорость  передачи  данных  в  канале  (Мбит/с);

e_f  —  вероятность  возникновения  ошибки  в  тестовом  пакете  (измеряется  экспериментально  на  пакетах  длиной  B_t  )  [4].

При  условии,  что  ошибки  в  пакете  возникают  независимо  друг  от  друга,  то  вероятность  возникновения  ошибки  e_f  можно  вычислить  следующим  образом:

                                   (2)

где:  p_o  —  вероятность  возникновения  битовой  ошибки  при  передаче;

n  —  число  передаваемых  бит  в  пакете.

Эта  метрика  представляет  собой  оценку  времени  передачи  (в  секундах)  пробного  пакета  длиной  B_t  с  учётом  возможных  ретрансляций  при  потерях  в  канале.  Способ  определения  параметров  r  и  e_f  в  стандарте  не  приводится,  однако  можно  предположить,  что  для  этого  должна  использоваться  периодическая  рассылка  пробных  пакетов  длиной  B_t  =  8192  бит  [4].

Протокол  маршрутизации  HWMP.

Протокол  HWMP  (Hybrid  Wireless  Mesh  Protocol)  является  гибридным  протоколом,  так  как  может  работать  как  в  реактивном,  так  и  в  проактивном  режимах  маршрутизации.

Рисунок  2.  Пример  построения  маршрута  от  узла  4  до  узла  9  в  реактивном  (а)  и  проактивном  (б)  режимах

В  реактивном  режиме,  маршрутные  таблицы  создаются  в  mesh-узлах  непосредственно  перед  передачей  (по  запросу  RREQ).  Перед  началом  передачи,  узел-отправитель  формирует  широковещательный  запрос  Path  Request  (RREQ)  ко  всем  соседним  узлам,  которые,  в  свою  очередь  вносят  необходимые  изменение  в  поле  метрики,  и  посылают  данный  запрос  далее.  Узел-получатель  принимает  пакет  RREQ  с  уже  сформировавшейся  информацией  о  метрике  всего  пути,  и  формирует  пакет  подтверждения  Path  Reply  (RREP),  который  отсылает  отправителю.  Отправитель,  приняв  пакет  RREP,  считывает  информацию  о  метрики  пути  и  принимает  решение  о  начале  процесса  передачи  (рисунок  2а).

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

Заключение.

Концепция  беспроводной  ячеистой  сети  является  перспективным  направлением  в  развитии  беспроводных  сетей,  так  как  она  позволяет  на  практике  реализовать  преимущества  именно  ячеистой  топологии  (высокая  надёжность,  гибкость,  расширяемость).  Основные  преимущества  WMN,  прежде  всего,  заключаются  в  их  быстром  и  дешёвом  развёртывании,  обеспечении  высокой  пропускной  способностью,  мобильности  конечного  пользователя,  а  также  в  совместимости  с  действующими  стандартами  WLAN  802.11.

Список  литературы:

1.IEEE  802.11s  Multihop  MAC:  A  Tutorial  Ricardo  C.  Carrano,  Luiz  C.S.  Magalhaes,  Debora  C.  Muchaluat  Saade  and  Celio  V.N.  Albuquerque,  IEEE  Communications  Surveys  and  Tutorials  Volume  13,  Number  1,  First  Quarter  2011.

2.IEEE  802.11s:  The  WLAN  Mesh  Standard  Guido  Hiertz,  Dee  Denteneer,  Sebastian  Max,  Rakesh  Taori,  Javier  Cardona,  Lars  Berlemann,  Bernhard  Walke,  IEEE  Wireless  Communications,  —  vol.  17,  №  1,  —  pp.  104—111,  —  2010.

3.IEEE  P802.11s/D1.00.  Amendment:  Mesh  Networking.  IEEE,  2006.

4.Вишневский  В.,  Д.  Лаконцев,  А.  Сафонов,  С.Шпилев,  mesh-сети  стандарта  IEEE  802.11s:  протоколы  маршрутизации,  Первая  миля,  —  2008,  —  №  2—3,  —  с.  26—31.