Зміст

• Вступ
• 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 мереж за рахунок використання іншої метрики при побудові маршрутів у протоколі маршрутизації 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 мереж, які працюють відповідно до стандарту IEEE 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) затримка і лінії даного маршруту, а TSR_i (Transmission Success Ratio) частка вдало переданих пакетів через і лінію даного маршруту. Чим менше значення фітнес функції, тим кращім вважається маршрут.

Оператор відбору (селекції) призначений для формування множини батьківських хромосом для подальшого кросинговеру. Відбір тим самим фокусується на дослідженні перспективних областей в просторі рішень. У роботі обрана турнірна селекція з розміром турніру рівним двом. Це сприяє більш випадковому вибору батьківських хромосом для кросинговеру. З батьківської популяції випадковим чином обирається дві хромосоми і порівнюються їх фітнес функції. Та хромосома у котрої значення фітнес функції менше записується у спеціальну базу з котрої у подальшому може бути обрана для кросинговеру.

Кросинговер призначений для формування нових маршрутів у результаті обміну двох обраних батьківських хромосом частинами маршруту. На рис. 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 року. Повний текст роботи та матеріали по темі можуть бути отримані у автора роботи або його наукового керівника після зазначеного терміну.

 

Резюме Біографія