ДонНТУ |
Портал магістрів ДонНТУ |
Про мене |
Актуальність теми
Сучасні бездротові мережи являють собою найкраще рішення для організації доступу по сукупності показників швидкості та коштовності
розвертання, простоті підключення користувачів, ступеню залежності від оточуючих умов. Використання бездротових технологій з часом
постає все більш розповсюдженим засобом доступу до Інтернету чи до локальних корпоративних, кампусових чи приватних мереж.
Проблема мобільного вузла - відносно нове явище, але, тим не менш, вона постає досить гостро. Мільйони людей в наші дні подорожують,
знаходяться у командировках. Багатьом з них просто необхідно мати доступ до свого ящика електронної пошти, своєї файлової системи.
Cьогодні гостро постає питання сумісності протоколів та стандартів при побудуванні бездротових мереж. У поданій статті розглядаються питання
оптимізації протоколів бездротових мереж за швидкістю та надійністю передачі та основні задачі, які постають при створенні оптимальних протоколів
маршрутизації у цих мережах.
Наукова значність роботи
Розвиток радиомереж передачі даних у наш час займає одне з найважливіших місць серед задач технічного прогресу. У першу чергу ці системи призвані
забезпечувати бездротовий доступ до вузлів провайдерів мережевих послуг, як для рухомих абонентів, так і для стаціонарних, в умовах, коли прокладка
кабелів до них технічно неможлива чи економічно невигідна.
Зараз поки що опубліковано дуже мало оглядів існуючих бездротових протоколів маршрутизації російською та українською, тоді як у англомовній
літературі ця тематика представлена досить широко. Подана робота має внести вклад у ліквідацію цього відставання та у оптимізацію існуючих методів
маршрутизації на прикладі пропонованого альтернативного алгоритму.
Маршрутизація у бездротових мережах має свої особливості. «Вузьким місцем» тут звичайно є фіксована інфраструктура з її обмеженнями на передачу
трафіка між користувачами. В такому випадку мобільні пристрої повинні функціонувати у автономному режимі, самостоійно проводячи встановлення з'вязку
з другими вузлами мережі, тим самим виконуючи деякі функції маршрутизатора. Ускладнення їх роботи зумовлено характером розглянутих нами мереж, де
вузли-користувачі можуть коли завгодно змінювати своє місцезнаходження, тим самим постійно змінюючи топологію та спілкуючись між собою без створення
яких-то певних стаціонарних путей передачі даних. Такі мережі носять назву MANET (mobile ad hoc networks). В цьому випадку вузли повинні співтрудничати для
забезпечення якісної маршрутизації, на віміну від традиційних WLAN, де абонентське обладнання централізовано керується точками доступу.
Всі ці особливості дозволяють мережам значно варіювати за кількістю абонентів: від кількох одиниць до сотен. Відповідно, для різних прикладів структури спроектовано
та створено багато протоколів, деякі з которих будуть розглянуті в поданій роботі.
Протоколи маршрутизації MANET поділяються на дві групи: проактивні (tabledriven/proactive routing protocols) і реактивні (on-demand/reactive routing protocols). Особливість
першої групи у тому, що вузли мережі постійно збирають та обновлюють інформацію про її стан, обмінюючись нею зі сусідами. Проактивні протоколи потребують від вузла
ведення таблиць маршрутизації, де вказані маршрути, котрі дозволяють досягнути будь-якого абонента мережі. Спеціальні алгоритми використовуються для підтримки
актуальності цієї інформації. У зв'язку з цим усі зміни в топології мережі розповсюджуються в неї. До проактивних протоколів відтносяться TBRPF (Topology Dissemination
Based on Reverse-Path Forwarding ), OLSR (optimized link state routing), DSDV (Highly Dynamic Destination-Sequenced Distance-Vector Routing).
У протоколах реактивної групи вузел шукає шлях до пункту призначення тільки за виникненням необхідності. Для цього існують дві основних операції: пошук маршруту та
підтримка маршруту. Коли вузел намагається встановити зв'язок та починає встановлювати маршрут, інформацію про доступні каналаи він отримає по запитах. Для підтримки
інформації про маршрути вузли повинні реагувати на зміни в топології мережі. Вузел, у якого є інформація про якийсь канал, повинен намагатися детектувати його відмову, якщо
це відбувається. Основні реактивні протоколи: DSR (Dynamic Source Routing protocol), AODV (Ad Hoc On-Demand Distance Vector), DYMO (Dynamic MANET On-demand).
Пізніше були пропоновані інші протоколи для пакетних радіомереж, в котрих було зроблено намагання об'єднати переваги і позбутися недоліків кожної з груп. Прикладом є
протокол BVR (Beacon Vector Routing), которий використовує технології «жадібного просунення пакетів» (greedy forwarding) та побудування системи логічних координат, запозичені
від попередніх протоколів мереж. Його особливістю є створення ряду «маяків» (beacons), випадково обраних вузлів, що грають роль синхронізаторів в мережі. На їх базі будується
«дерево» мережевої структури, визначаються показники маршрутів та здійснюється побудування шляхів до пунктів призначення: пошук найближчого сусіда, призначення його як
наступного елементу маршруту та перехід до його найближчого сусіда (реалізація алгоритму «жадібного просунення»). Відміною BVR є застосування при цьому не географічних, а
логічних координат. Головне призначення протоколу - підтримка з'єднань «точка-точка» (point-to-point). Пізніше на його основі було розроблено протокол LCR (Logical Coordinate
Routing).
У поданій роботі пропонується оптимізований варіант - алгоритм альтернативної маршрутизації, розроблений на базі існуючих рішень. Він використовує принципи побудування
найкоротших шляхів, які застосовано у алгоритмах Дейкстри і Беллмана-Форда, та засоби визначення середньої затримки, які є традиційними для мереж з пакетною комутацією.
Розроблений для ретрансляторів алгоритм альтернативної маршрутизації засновано на мінімізації середньої затримки на всіх найкоротших маршрутах, причому визначення затримок
на участках включає аналіз статичних характеристик мережі (топології та пропускових здатностей каналів зв'язку) та характеру переданого трафіку (урахування оптимальних показників
затримок для різних видів трафіку).
В алгоритмі передбачено механізми анализу пропускових здатностей каналів зв'язку з точки зору їх оптимальності, розрахунок оптимальної ваги шляхів на основі цієї інформації та
мінимізації функції затримки у мережі на основі аналізу потока по маршрутах, при котрому розмір затримки міг би відповідати загальноприйнятим характеристикам передачі певних видів
трафіку.
Алгоритм використовує принципи побудування найкоротших шляхів, які застосовано у алгоритмах Дейкстри і Беллмана-Форда, та засоби визначення середньої затримки, які є
традиційними для мереж з пакетною комутацією (відповідні формули наведено далі). Функціональну блок-схему алгоритму наведено на рисунку:
1. Блок визначення оптимальних пропускових здатностей - аналізує базову топологію мережі та визначає оптимальність пропускових здатностей. На основі отриманих даних підраховує
вагу каналів зв'язку мережі для подальшого аналізу.
2. Блок аналізу середнього часу затримки - відповідає за розрахунок середнього часу затримки у мережі на основі оптимальних пропускових здатностей та початкових потоків в мережі.
3. Блок визначення маршрутів - відповідає за побудову найкоротших маршрутів між усіма вузлами мережі.
4. Блок побудови допустимого потоку - забезпечує розподіл потоків по найкоротших шляхах.
5. Блок мінімізації середньої затримки - забезпечує розрахунок девіації потоку на основі мінімізованої функції значення середньої затримки в мережі.
6. Тіло алгоритму - об'єднує роботу кожного з блоків та забезпечує послідовне функціонування алгоритму.
Наступні задачі вирішаються алгоритмом:
1) найбільш раціональне використання каналів;
для розв'язання задачі використовуються наступні прийоми:
а) аналіз пропускних здатностей каналів зв'язку у мережі та розрахунок оптимальних міток;
б) використання альтернативних маршрутів;
в) розподіл трафіка між альтернативними маршрутами виходячи не з відношення сумарних метрик маршрутів, а з відношення максимальних метрик каналів
данного маршруту;
г) вибір доступних до використання альтернативних маршрутів тільки за критерієм максимального часу передачі (маршрут може бути прийнятий до використання, якщо час передачі по
маршруту не перевищує встановленого для даного типу трафіка максимально припустимого).
2) дотримання вимог до параметрів мережної передачі. Далі розглянемо прийоми розв'язання зазначених задач;
задача дотримання вимог до параметрів мережної передачі вирішується в такий спосіб:
а) мінімізація затримки передачі повідомлень у мережах складної топології;
б) мінімізація СКВ затримки.
Зробимо оцінку оптимальності функціонування за алгоритмом. Введемо позначення:
де і - номер пари вузол-адресат - вузол-одержувач;
первая формула - потік пакетів, які поступають до і-го каналу;
друга - потік пакетів, поступаючих з вузла до мережі.
Навантаження і-ого каналу пакетами рахуємо по наступній формулі:
де перший множитель - середня довжина пакета, Di - пропускова здатність і-ого каналу.
Среднее количество пакетов в і-ом канале составляет:
Враховуючи загальну кількість вузлів в мережі, середня кількість пакетів в мережі в цілому складає:
За формулою Літтла
де Т - середня затримка в мережі. Таким чином, отримаємо формулу Клейнрока для аналізу середньої
затримки в мережі: 
Отримана формула для оцінки часу затримки ефективно використовується для розв'язання різноманітних оптимізаційних задач. До таких
задач відносять оптимізацію пропускної здатності каналів та вибір маршрутів передачі повідомлень.
Подана робота присвячена проблемам оптимізації методів маршрутизації у сучасних бездротових мережах. Наведений огляд
існуючих протоколів повинен дати загальне поняття поточних проблем у галузі, переваг та недоліків існуючих рішень та можливі
шляхи розвитку.
Одним з перспективних рішень може стати пропонований у поданій роботі алгоритм маршрутизації для ретрансляторних станцій.
Він призваний оптимізувати їх функціонування у складі магістральної транспортної мережі мобільного зв'язку. Застосування
альтернативної маршрутизації, за результатами перевірки роботи алгоритму за допомогою спеціально розробленої програми,
дозволяє знизити майже вдвічи середню затримку в мережі, якщо порівнювати з результатами роботы за алгоритмами Дейкстри та
Беллмана-Форда.
Про мене |