Содержание

• Введение
• 1. Актуальность темы
• 2. Цель и задачи исследования
• 3. Обзор источников
• 3.1 Обзор русскоязычных источников
• 3.2 Обзор международных источников
• 4. Улучшение системы маршрутизации для протокола OLSR
• Выводы
• Список источников

Введение

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

В данное время в разработке находится стандарт mesh сетей. Так комитет IEEE 802.11s стандартизирует Wireless Local Area Network (WLAN) mesh сети. Данный стандарт в дальнейшем должны будут поддерживать все производителя оборудования для беспроводных mesh сетей.

Беспроводные mesh сети обещают большую гибкость, повышение надежности и повышение продуктивности в сравнении с обычными беспроводными локальными сетями.

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

1. Актуальность темы

Для маршрутизации в беспроводных mesh сетях используются как протоколы маршрутизации разработанные для работы в мобильных ad hoc сетях, такие как Ad Hoc On Demand Distance Vector (AODV), Optimized Link-State Routing (OLSR), так и протоколы разработаны непосредственно для работы в беспроводных mesh сетях, такой как Hybrid Wireless Mesh Protocol (HWMP).

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

2. Цель и задачи исследования

Цели работы: улучшение эффективности использование ресурсов беспроводной mesh сети за счет правильного выбора протокола маршрутизации, а также за счет улучшения системы построения маршрута в выбранном протоколе.

Задачи работы:

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

Объектом исследования является система маршрутизации в беспроводных mesh сетях.

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

Планируемая научная и техническая новизна:

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

3. Обзор источников

3.1. Обзор русскоязычных источников

Анализ стандарта IEEE 802.11s проводится в публикациях Вишневского В., Лаконцева Д., Сафонова А., Шпилева С. [1-2]. В этих статьях авторы анализируют особенности будущего стандарта, а также протокол маршрутизации, предлагаемый в данном стандарте. Также в работе Многоканальные mesh-сети: анализ подходов и оценка производительности [3] проводится оценка производительности многоканальных беспроводных mesh сетей стандарта IEEE 802.11s. В работе Ефремова А.Ю. [4] предлагается алгоритм маршрутизации для беспроводных mesh сетей на основе виртуальных каналов. В своей работе Максимова Д.Ю. [5] предлагает использовать для маршрутизации в беспроводных mesh сетях нейронные методы коммутации.

3.2. Обзор международных источников

В англоязычных работах данной теме посвящено больше работ. В работе IEEE 802.11S: the wlan mesh standard [6] дается анализ будущего стандарта для беспроводных mesh сетей. В статье [7] авторы предлагают улучшить работу беспроводных mesh сетей за счет применения другой метрики построения в протоколе маршрутизации Hybrid Wireless Mesh Protocol (HWMP). Так вместо Airtime link metric (ALM) они предлагают свою собственную метрику Expected Forwarding Delay (EFD), которая позволяет повысить пропускную способность сети. В работе Improving IEEE 802.11s Wireless Mesh Networks for Reliable Routing in the Smart Grid Infrastructure [8] авторы также заняты улучшением работы беспроводной mesh сети по стандарту 802.11s. Они предлагают несколько механизмов по улучшению работы сети также за счет улучшения метрик, которые позволяют оценить эффективность маршрута.

4. Улучшение системы маршрутизации для протокола OLSR

На основе результатов полученных при моделировании работы протоколов маршрутизации AODV, OLSR, HWMP проведенных в работах [9-10] для дальнейшего улучшения системы построения маршрута был выбран протокол маршрутизации OLSR.

Основными особенностями работы протокола OLSR в соответствии со стандартом является [11]:

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

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

Кодирование маршрута. Каждая хромосома представляет собой существующий маршрут от источника к получателю. Каждый локус хромосомы содержит узел, принадлежащий выбранному маршруту. Пример представлен на рис.1, где S это источник, N1,…, Nk – узлы маршрута, D – узел назначения, l – порядковый номер локуса.

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

Формирование первоначальной популяции происходит случайным образом, в результате чего формируется n хромосом, то есть популяция.

Фитнес функция. Для оценки качества пути используется следующая функция:

где, DT_i (Delay Time) задержка i линии данного маршрута, а TSR_i (Transmission Success Ratio) доля успешно переданных пакетов через i линию данного маршрута. Чем меньше значение фитнесс функции тем лучшим считается маршрут.

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

Кроссинговер предназначен для формирования новых маршрутов в результате обмена двух выбранных родительских хромосом частями маршрута. На рис. 2 представлен пример осуществления операции кроссинговера.

В данном алгоритме предлагается использовать одноточечный кроссинговер. Механизм работы следующий: сначала из отобранных родительских хромосом, турнирным способом, выбираются случайно две хромосомы для кроссинговера; затем в выбранных хромосомах происходит поиск одинаковых узлов; после этого из набора найденных одинаковых узлов выбирается одна случайная пара для кроссинговера, в результате чего получается две новых хромосомы. Это продолжается до тех пор, пока не будет образовано n новых хромосом.

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

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

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

Выводы

Беспроводные mesh сети являются перспективным направлением развития городских сетей доступа, а также для развертывания временных недорогих сетей доступа.

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

• Проанализированы особенность работы беспроводных mesh сетей.
• Произведено моделирование и сравнение эффективности работы следующих протоколов маршрутизации: AODV, OLSR, HWMP.
• Для дальнейшего улучшения системы маршрутизации был выбран протокол OLSR.
• Был предложен алгоритм для построения наилучшего маршрута на основе генетических алгоритмов.

Дальнейшие исследования направлены на следующие аспекты:

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

Список источников

1. Вишневский В., Лаконцев Д., Сафонов А., Шпилев С. Маршрутизация в широкополосных беспроводных mesh-сетях стандарта IEEE 802.11s // ЭЛЕКТРОНИКА: Наука, Технология, Бизнес. – 2008. – c. 64-69.
2. Вишневский В., Лаконцев Д., Сафонов А., Шпилев С. Mesh-сети стандарта IEEE 802.11s – технологии и реализация // ЭЛЕКТРОНИКА: Наука, Технология, Бизнес. – 2008. – c. 98-105.
3. Ляхов А.И., Пустогаров И.А., Шпилев С.А. Многоканальные mesh-сети: анализ подходов и оценка производительности // Информационные процессы. – 2008. Том 8, № 3. – с. 173–192.
4. Ефремов А.Ю. Использование в mesh сетях стандарта IEEE 802.11 алгоритмов маршрутизации на основе виртуальных каналов // Технические и программные средства систем управления, контроля и измерения. – Москва, октябрь 2010. – с. 1-6.
5. Максимов Д.Ю. Нейронный метод коммутации в беспроводных сетях передачи данных с подвижными объектами // Технические и программные средства систем управления, контроля и измерения. – Москва, октябрь 2010. – с. 829-834.
6. Guido R. Hiertz, Dee Denteneer, Sebastian Max, Rakesh Taori. IEEE 802.11S: the wlan mesh standard // IEEE Wireless Communications. – February 2010. – pp. 104-111.
7. Md. Shariful Islam, Muhammad Mahbub, M. Abdul Hamid, Choong Seon Hong. High throughput path selection for IEEE 802.11s based Wireless Mesh Networks // Computer communication networks: network protocols. – Kprea. – 2010.
8. Ji-Sun Jung, Keun-Woo Lim, Jae-Beom Kim, Young-Bae Ko. Improving IEEE 802.11s Wireless Mesh Networks for Reliable Routing in the Smart Grid Infrastructure // Science and Technology. – 2010.
9. Чабанный А.А. Сравнение протоколов маршрутизации беспроводных mesh сетей // Сучасні проблеми радіотехніки та телекомунікацій «РТ - 2012»: Матеріали 8-ої міжнар. молодіжної наук.-техн. конф., Севастополь 23 — 27 квітня 2012 р. / М-во освіти і науки, молоді та спорту України, Севастоп. нац. техн. ун-т; наук. ред. Ю.Б.Гімпілевич. — Севастополь: СевНТУ, 2012.
10. Чабанный А.А. Дослідження роботи протоколів маршрутизації у бездротових mesh мережах // Тези всеукраїнського конкурсу студентських наукових робіт з технічних наук у 2011/2012 роках ("Телекомунікаційні системи та мережі", "Інформаційні мережі зв'язку"). - Одеса: ВМВ, 2012.
11. Стандарт протокола OLSR [Электронный ресурс]. – Режим доступа: http://www.ietf.org/rfc/rfc3626.txt
12. Luke S. Essentials of Metaheuristics. // A Set of Undergraduate Lecture Notes [Электронный ресурс]. September, 2009 – 237.

Важное замечание

На момент написания данного реферата квалификационная работа магистра еще не завершена. Дата окончательного завершения работы: декабрь 2012 года. Полный текст работы и материалы по теме могут быть получены у автора или его руководителя после указанного срока.

 

Резюме Биография Библиотека Ссылки Отчет о поиске Индивидуальный раздел