Дослідження алгоритмів маршрутизації у бездротових IP-мережах

Вступ

Актуальність роботи

Мета роботи – дослідити алгоритми маршрутизації в бездротових мережах і, на їх основі, розробити покращений алгоритм. Тема актуальна, завдяки швидкому розвитку бездротових мереж, що поступово витісняють дротяні.

Наукова і практична новизна

Можлива новизна полягає в удосконаленні існуючих алгоритмів і протоколів. Це повинно дозволити зменшити «паразитний трафік» і, можливо, поліпшити якість вибираних маршрутів. Відповідний драйвер для нового протоколу писати доки не планується, оскільки перед реалізацією необхідно спочатку провести моделювання (математично і програмно) і порівняння ефективності з існуючими аналогами.

Основний зміст роботи

Алгоритми маршрутизації

В першу чергу, буде промодельований протокол AODV (Ad-hoc On-Demand Vector Routing[2]), що використовує дистанційно-векторний алгоритм. Це реактивний протокол маршрутизації, який встановлює маршрут до адресата за вимогою (за допомогою відсилання пакетів RREQ). У AODV передача маршрутної інформації (окрім повідомлень вітання) не ведеться, поки немає необхідності у встановленні або відновленні маршруту.

Перед відправкою даних, вузол посилає пакет RREQ (запит маршруту) сусідам через свою зону широкомовлення. Ближні вузли, у свою чергу, пересилають запит своїм сусідам і так далі (див. рис.1), поки пакет із запитом не дійде до одержувача. При пересилці, проміжні вузли роблять відмітку про попередній вузол (таким чином, реєструючи свою частину маршруту), а також про початковий і кінцевий пункти маршруту. У випадку якщо проміжний вузол отримає декілька однакових пакетів(що можна відстежити по номеру запиту, вибираному вузлом так, щоб не перетнутися з останніми), то з них буде обрано пакет з найменшою кількістю хопів, забезпечуючи таким чином вибір найбільш оптимального маршруту.

Якщо проміжний вузол вже має маршрут до вузла призначення і прапор D(доставити до вузла призначення) в пакеті RREQ неактивний, він відповідає джерелу пакетом RREP(або посилає RREQ одержувачеві безпосередньо), підтверджуючи встановлення маршруту (і роблячи відмітку у своїй таблиці маршрутизації). Якщо прапор D активний, можливість використання вже відомого маршруту ігнорується (оскільки топологія мережі з часом змінюється, цей маршрут міг стати неоптимальним, ненадійним або зовсім зникнути).

Для додаткового підтвердження може використовуватися пакет RREP-ACK, що посилається джерелом після отримання RREP (це може використовуватися для перевірки маршруту в мережах з ненадійним зв'язком).

У загальному вигляді, отриманий маршрут можна представити у вигляді зв'язного списку (фізично розподіленого по проміжних вузлах), кожна ланка якого записана у відповідну таблицю маршрутизації. Якщо прапор D в запиті на встановлення маршруту неактивний, то декілька маршрутів можуть перетинатися, тобто їх списки можуть містити загальні ланцюжки ланок (можливо, ця особливість буде використана для оптимізації алгоритму).

У протоколі використані наступні методи боротьби з паразитним трафіком:

• Обмеження часу життя пакету (TTL) до значення передбачуваного числа проміжних вузлів в мережі;
• Обмеження частоти повторення посилки запиту RREQ, в разі руйнування маршруту (або невдалого пошуку, наприклад, якщо на деякий час маршрут до вузла перестав існувати взагалі як такий). В цьому випадку джерело чекає час удвічі більше, ніж було необхідно для встановлення маршруту;

У протоколу є наступні переваги:

• Простота реализації;
• Відсутність додаткового трафіку при пересилці даних;
• Низькі вимоги до ресурсів.

Недоліком протоколу є великий час встановлення маршруту.

Протокол DSR (Dynamic Source Routing[1]), що застосовується в комірчастих (mesh) мережах, східний з AODV в тому, що також формує маршрут на вимогу, за допомогою передачі запиту (реактивний протокол маршрутизації). Основна відмінність в тому, що DSR накопичує інформацію про маршрут не в таблицях маршрутизації вузлів, а безпосередньо в пакеті запиту. Основний недолік – значне збільшення розміру пакету при довгих маршрутах або адресах (в цьому випадку накопичення адрес відключається, і використовуються безпосередньо таблиці маршрутизації).

Математична модель мережі та її основні параметри

У магістерській роботі планується промоделювати безпровідну мережу, що маршрутизується за модифікованим протоколом AODV і, можливо, mesh-мережі з DSR. Основною відмінністю безпровідних мереж від дротяних аналогів є погано структурована і така, що динамічно змінюється топологія, при ненадійному зв'язку між вузлами.

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

Також кожен з каналів характеризується провідною спроможністю (якістю зв'язку) і способом доступу, залежно від якого канал можна віднести до одного з наступних типів:

• виділений канал – використовується для однонаправленої передачі даних між парою вузлів, при цьому в інших вузлів в мережі немає доступу до ресурсів каналу;
• канал, що розділяється, – призначений для всенаправленого обміну даними між декількома вузлами;
• канал загального типу – може бути використаний і як виділений, і як канал, що розділяється.

Для визначення критеріїв ефективності обміну даними між вузлами в мережі розглянемо цей процес з точки зору дискретної математики і теорії множин. Нехай деякий вузол ‘I’ збирається передати своєму сусідові ‘j’ деяке повідомлення. В цьому випадку вузол ‘I’ повинен вибрати для передачі даних один з каналів до, що задовольняють умові:

де

Тобто, підмножина k – це безліч каналів тих, що зв'язують ці два вузли. Фізично ця підмножина може бути набором незайнятих іншими вузлами радіочастот(або смуг радіочастот), на яких можливий зв'язок між ‘I’ і ‘j’. Після звільнення одного з каналів цієї підмножини (з вищезгаданої класифікації виходить, що канал може бути зайнятий і іншими вузлами), вузол переводить його в стан «зайнятий» (наприклад, починаючи посилку преамбули і фрейму). При цьому даний канал не може бути використаний жодним з вузлів кластера, в які входять ‘I’ і ‘j’ (оскільки фізично вони розділяють один і той же радіоефір). Точніше, в кластері ‘I’ (ефір через який цей вузол може віщати по даному каналу) не може бути здійснена передача, а в кластері ‘j’ (ефір в якому цей вузол може прослухувати даний канал) - прийом.

Для багатоканальної передачі даних відправка повторюється кілька разів, що приводить до збільшення об'єму трафіку, реально обслугованого мережею, в N+1 разів, де N – кількість проміжних вузлів ретрансляторів в маршруті передачі повідомлення.

На основі приведеного вище опису можна ввести параметр інтенсивності трафіку, який складається з інтенсивності трафіку, створеного вузлом, і інтенсивності трафіку, що ретранслюється, і є характеристикою потоку обслуговуваних вузлом даних.

«Для безпровідних мереж з комутацією пакетів одним з найважливіших параметрів є середня затримка передачі даних. Цей параметр може бути обчислений наступним чином:

де

Для мережі, що складається з однакових пристроїв, параметр T є постійним для всіх вузлів і залежить, в основному, від довжини пакету і пропускної спроможності каналу зв'язку. Параметр ti залежить від інтенсивності обслуговування кожного i-го трафіку, тому для кожного вузла має сенс вести ще один додатковий параметр – інтенсивність трафіку, що обслуговується для кластера даного вузла, або коефіцієнт використання ресурсу, що розділяється (або ресурсів, у випадку, якщо їх декілька).»[2]

Моделююче програмне забезпечення

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

Графічний інтерфейс моделюючого програмного забезпечення(ПЗ).

У GUI запланована реалізація наступної функціональності:

• Редактор графу (з можливістю імпорту даних з xml-файлу).
• Графіки моделювання (відображують навантаження на вузли, швидкість передачі пакетів).
• Можливість керування процесом моделювання.
• Можливість зміни параметрів і структури графу під час моделювання (у режимі паузи).
• Можливість конфігурації моделюємих пристроїв

Структура ядра моделюючого ПЗ.

У моделюючому ПЗ запланована реалізація наступних класів:

• Node – описує вузол(зв'язаний пристрій)
• Device – описує пристрій комутації(параметри пристрою, таблиця зв'язків, таблиця маршрутизації)
  • WirelessDevice
  • AP – точка доступу
  • WirelessRouter
• Packet – описує пакет, передаваний по мережі (зокрема, його статистичні характеристики - кількість пройденних хопов, час доставки, розмір)
  • RoutingPacket – службовий пакет, призначений для встановлення маршруту.
  • Hello – пакет вітання (відсилається при активації вузла, тобто при додаванні його в мережу).
• Link – описує зв'язок (ребро) між вузлами
• Net – містить список вузлів мережі і деякі її характеристики
• Packets – містить список відстежуваних пакетів і їх загальні характеристики

Аналіз результатів моделювання

Розроблене програмне забезпечення повинне буде представляти статистику для різних протоколів маршрутизації, при різних топологіях, що дозволить порівняти їх з алгоритмом, що розробляється, і зробити виводи про ефективність його використання. В основному, будуть використані наступні критерії:

• Навантаження на вузли
• Навантаження на канали
• Затримка при передачі пакетів

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

1. Dynamic Souce Routing. Матеріал із Вікіпедії — вільної Енциклопедії / Інтернет ресурс. — Режим доступу: http://en.wikipedia.org/wiki/Dynamic_Source_Routing.
2. AODV. Матеріал із Вікіпедії — вільної Енциклопедії / Інтернет ресурс. — Режим доступу: http://en.wikipedia.org/wiki/AODV.
3. Гайдулин А. Моделирование алгоритма маршрутизации передаваемых данных в беспроводных сетях со смешанными типами коммутации / Вестник Нижегородского университета им. Н.И. Лобачевского, 2008, № 1, с. 93–99.
4. Chakeres Ian D., Belding-Royer Elizabeth M. AODV Routing Protocol Implementation Design / Dept. of Electrical & Computer Engineering, University of California, Santa Barbara / Інтернет ресурс. — Режим доступу: http://moment.cs.ucsb.edu/pub/wwan_chakeres_i.pdf.
5. Hadi Abd Rahman Abdul, Zukarnain Zuriati Ahmad. Performance Comparison of AODV, DSDV and I-DSDV Routing Protocols in Mobile Ad Hoc Networks/ Eurojurnals / Інтернет ресурс. — Режим доступу: http://www.eurojournals.com/ejsr_31_4_07.pdf.
6. Tsamis Dimitrios, Alpcan Tansu, Pal Singh Jatinder, Bambos Nick. Dynamic resource modeling for heterogeneous wireless networks / Stanford University, Stanford, CA 94305 / Інтернет ресурс. — Режим доступу: http://www.stanford.edu/~dtsamis/icc09tansu.pdf.
7. Крылов В.В., Самохвалова С.С. Теория телетрафика и ее приложения. Основы теории систем массового обслуживания для задач телекоммуникаций. СПб.: БХВ, 2005. 288 с. - C. 85-98.
8. Royer E., Toh C. A. Review of Current Routing Protocols for Ad-Hoc MobileWireless Networks // IEEE Personal Communications. 1999. V. 4. P. 46–55.
9. Панфилов Д., Соколов М. Введение в беспроводную технологию стандарта 802.15.4
   Электронные компоненты. — Киев, 2004. — №12(73). — С. 73-79.
10. Gislason Drew. Wireless Networking. — Newnes, 2008 - P. 302-318.