Мультиагентна інформаційна технологія адаптивної маршрутизації в мобільних комп'ютерних мережах

Размещено на http://www.allbest.ru/

ВІННИЦЬКИЙ НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ

Спеціальність 05.13.06 - Інформаційні технології

УДК 004.04:004.057.5

Автореферат

дисертації на здобуття наукового ступеня кандидата технічних наук

Мультиагентна інформаційна технологія адаптивної маршрутизації в мобільних комп`ютерних МЕРЕЖАХ

Лисак Наталія

Володимирівна

Вінниця - 2008

Дисертацією є рукопис.

Роботу виконано у Вінницькому національному технічному університеті Міністерства освіти і науки України.

Науковий керівник:

кандидат технічних наук, доцент Хошаба Олександр Мирославович, Вінницький національний технічний університет, доцент кафедри інформаційного менеджменту

Офіційні опоненти:

доктор технічних наук, професор Квєтний Роман Наумович, Вінницький національний технічний університет, завідувач кафедри автоматики та інформаційно-вимірювальної техніки доктор технічних наук, професор Кулаков Юрій Олексійович, Національний технічний університет України “Київський політехнічний інститут”, професор кафедри обчислювальної техніки Захист відбудеться "16" травня 2008р. о 1230 годині на засіданні спеціалізованої вченої ради Д 05.052.01 Вінницького національного технічного університету за адресою: 21021, м. Вінниця, Хмельницьке шосе 95, ГУК, 210.

З дисертацією можна ознайомитись у бібліотеці Вінницького національного технічного університету за адресою: 21021, м. Вінниця, Хмельницьке шосе, 95.

Автореферат розісланий "15" квітня 2008 р.

Вчений секретар спеціалізованої вченої ради С.М. Захарченко

1. ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

Актуальність теми. Одним з найбільш динамічних напрямків розвитку комп'ютерних мереж сьогодні є розробка нових технологій та протоколів маршрутизації, здатних забезпечити функціонування ситуативних (ad hoc) мобільних мереж (СММ), які утворюються мобільними вузлами за рахунок здійснення транзитних передач без будь-якого попереднього конфігурування, інфраструктури або централізованого адміністрування мережі. СММ застосовуються при ліквідації стихійних лих; у військових діях; на зустрічах, учасники яких бажають поділитися інформацією і т. ін. Зростання інтересу до СММ підтверджує створення в межах IETF робочих груп MANET (Mobile Ad hoc NETworking) та ZEROCONF (Zero Configuration), а також проголошення NASA програми створення мережі супутників земної орбіти та марсіанської інформаційної мережі, що буде складатися зі супутників, марсоходів та різноманітних датчиків.

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

Останнім часом для маршрутизації СММ було запропоновано значну кількість протоколів, зокрема таких, як DSDV, AODV, DSR, ZRP, HARP, ZHLS та інші, кожен з яких має певні переваги і недоліки, але жоден з них не забезпечує масштабованості та ефективної роботи в умовах високої рухливості вузлів мережі, яка призводить до значного зростання накладних витрат маршрутизації, .затримки виявлення маршрутів та порушень зв'язності мережі.

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

Зв'язок роботи з науковими програмами, планами, темами.

Дисертаційна робота виконувалася відповідно з координаційним планом науково-дослідних робіт Міністерства освіти і науки України (наказ №37 від 13.02.1997 р.) за напрямком “Перспективні інформаційні технології, прилади комплексної автоматизації, системи зв'язку” у рамках науково-дослідних робіт Вінницького національного технічного університету “Розробка децентралізованого алгоритму маршрутизації на основі інтелектуальних агентів для мобільних комп'ютерних мереж” (ДР №0107U009286, відповідальний виконавець Лисак Н.В.) та “Розробка методу керування топологією мобільних комп'ютерних мереж” (ДР №0107U009285, відповідальний виконавець Лисак Н.В.).

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

Об'єктом дослідження є процес маршрутизації в мобільних комп'ютерних мережах.

Предметом дослідження є мультиагентні інформаційні технології та методи децентралізованої адаптивної маршрутизації в ситуативних мобільних комп'ютерних мережах.

Відповідно до поставленої мети, у дисертаційній роботі необхідно розв`язати такі основні завдання:

1. Проаналізувати ефективність застосування існуючих технологій маршрутизації в умовах високої рухливості вузлів ситуативної мобільної мережі за наявності обмежень на їх енергоспоживання і радіус передавання інформації.

2. Розробити моделі інтелектуального агента маршрутизації та заснованого на агентах децентралізованого процесу маршрутизації в мобільних мережах, зручні з точки зору реалізації механізмів адаптації поведінки агентів маршрутизації в умовах непередбачуваних змін топології мережі.

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

4. Розробити модель та метод призначення потужностей передавання, що забезпечать гарантовану зв'язність вузлів мережі при мінімізації енергетичних та накладних витрат її вузлів на керування мережею в умовах непередбачуваних змін густини та рухливості її вузлів.

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

Методи досліджень, використані при розв`язанні поставлених задач, базуються на: теорії графів для представлення комп'ютерних мереж; теорії інтелектуальних агентів для моделювання вузлів мережі та мультиагентної системи маршрутизації; теорії адаптивних систем і мурашкових алгоритмів для формування таблиць маршрутизації; теорії ймовірностей та математичній статистиці для моделювання нестаціонарних і стохастичних потоків даних; теорії алгоритмів та програмування для моделювання, аналізу та перевірки достовірності теоретично отриманих даних.

Наукова новизна одержаних результатів визначається такими теоретичними і практичними результатами:

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

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

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

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

Практичне значення одержаних результатів дисертаційної роботи визначається тим, що запропоновані моделі та алгоритми дозволяють підвищити ефективність функціонування ситуативних мобільних комп'ютерних мереж на 8-12% та можуть бути застосовані при розробці нових або модифікації відомих протоколів маршрутизації.

Отримані у дисертаційній роботі результати впроваджені при побудові ситуативних мобільних мереж компаній ЗАТ “ДатаГруп” і ТОВ „Міротел”, використані при виконанні у Вінницькому національному технічному університеті науково-дослідних робіт “Розробка децентралізованого алгоритму маршрутизації на основі інтелектуальних агентів для мобільних комп'ютерних мереж” (номер державної реєстрації №0100U003953, відповідальний виконавець Лисак Н.В) і „Розробка методу керування топологією мобільних комп'ютерних мереж” (номер державної реєстрації №0100U003953, відповідальний виконавець Лисак Н.В) та застосовуються в навчальній дисципліні “Комп'ютерні мережі та телекомунікації”, яка викладається в Інституті інформаційних технологій та комп'ютерної інженерії Вінницького національного технічного університету, що підтверджено відповідними актами про впровадження.

Особистий внесок здобувача у роботах, виконаних у співавторстві, полягає у: виділенні трьох рівнів для побудови концептуальної моделі системи керування потоками даних в комп'ютерних мережах [1]; розробці концептуальної моделі системи керування потоками даних в комп'ютерних мережах [2]; проведенні аналізу методів побудови мультиагентних систем [3]; формулюванні властивостей інтелектуального агента маршрутизації СММ [5]; дослідженні задачі оптимізації функціонування МАС [7]; розробці структури системи керування потоками даних в комп'ютерних мережах [8]; дослідженні основних властивостей агентів [10]; розробці адаптивного алгоритму маршрутизації, заснованому на агентах [13]; розробці математичної моделі призначення потужностей передавання вузлам СММ [15].

Апробація результатів дисертації. Основні положення та результати дисертаційної роботи доповідались та обговорювались на наукових семінарах кафедр інтелектуальних систем та інформаційного менеджменту Вінницького національного технічного університету (м. Вінниця, 2005 - 2007 рр.), Херсонського національного технічного університету (м. Херсон, 2005 - 2007 рр.), Харківського національного університету радіоелектроніки (м. Харків, 2007 р.) та на 17 міжнародних та регіональних конференціях: ІІ - ІV міжнародні конференція “Інтернет-Освіта-Наука” (м. Вінниця, 2000, 2002, 2004 рр.); V наукова конференция “Интернет - среда за нови технологии в информационното общество” (м. Велико Тирново, Болгарія, 2002 р); IV міжнародна науково-технічна конференція “Оптико-електронні інформаційно-енергетичні технології” (м. Вінниця, 2002 р.); II міжнародна науково-практична конференція “Мікропроцесорні пристрої та системи в автоматизації виробничих процесів” (м. Хмельницький, 2003 р.); VIІ міжнародна конференція “Контроль і управління в складних системах” (м. Вінниця, 2003 р.); ХХХІІ - ХХХVІ науково-технічні конференції професорсько-викладацького складу, співробітників та студентів Вінницького національного технічного університету (м. Вінниця, 2003-2007 рр); VIІ міжнародна конференція “Правове, нормативне та метрологічне забезпечення систем захисту інформації в Україні” (м. Київ, 2003 р.); Міжнародна науково-практична конференція студентів, аспірантів та молодих вчених “Комп'ютери. Програми. Інтернет. 2003” (м. Київ, 2003 р.); ІІ міжнародна наукова конференція “Современные информационные системы: проблемы и тенденции развития”, (м. Туапсе, Російська Федерація, 2007 р.); Наукова конференція “Прогресивні інформаційні технології в науці і освіті” (м. Вінниця, 2007 р.).

Публікації. Основні результати дисертаційної роботи опубліковані в 15 статтях та тезах доповідей, в тому числі у 6 статтях у наукових фахових виданнях за переліком ВАК України [1-6] і 9 - у матеріалах конференцій [7-15].

Структура та обсяг дисертації. Дисертаційна робота, що викладена на 169 сторінках друкованого тексту, складається з вступу, чотирьох розділів і висновків, викладених на 135 сторінках основного тексту, списку використаної літератури з 112 найменувань і додатків. Дисертаційна робота містить 49 рисунків, 12 таблиць, 7 додатків, 3 акти про впровадження.

2. ОСНОВНИЙ ЗМІСТ РОБОТИ

У вступі обґрунтовано актуальність теми дисертаційної роботи, сформульовано мету і основні завдання досліджень, визначені предмет і об'єкт досліджень, зв'язок роботи з науковими програмами, планами, темами, наведено наукову новизну та практичну цінність одержаних результатів. Представлено дані про впровадження результатів роботи, особистий внесок здобувача в спільних наукових працях, публікації та апробацію результатів дисертації.

У першому розділі проведено аналіз основних теоретичних положень та результатів експериментальних досліджень, отриманих шляхом комп'ютерного моделювання сучасних протоколів маршрутизації для мобільних мереж, визначити основні методи розв'язання задачі маршрутизації в СММ, виявити причини їх переваг та недоліків з точки зору використання у ситуативних мобільних комп'ютерних мережах. Аналітичний огляд сучасних протоколів маршрутизації, що використовуються у СММ, засвідчив їх низьку придатність до використання в умовах значної рухливості вузлів СММ. Значний час виявлення маршруту реактивними протоколами, також як і значний час розповсюдження мережею маршрутної інформації проактивними протоколами, може перевищувати час змін її топології. У зв'язку з цим необхідною умовою стає базування технології маршрутизації СММ на основі локальної інформації. Це, у свою чергу, викликає необхідність її побудови на мультиагентній основі на базі принципів самоорганізації інтелектуальних агентів, що надають можливість задовольнити обмеження на час поширення мережею глобальної інформації маршрутизації та припустимі обсяги службової інформації. Основні механізми самоорганізації СММ можуть бути запозичені у природних мультиагентних систем: додатній зворотний зв'язок для забезпечення швидкої збіжності системи до кращих рішень; від`ємний зворотний зв'язок для відкидання рішень, які з часом втрачають свої переваги; випадковість, як критичний фактор пошуку нових рішень замість існуючих, навіть якщо останні здаються достатньо гарними.

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

У другому розділі розроблено модель інтелектуального агента маршрутизації та модель мультиагентної децентралізованої маршрутизації ситуативної мобільної комп`ютерної мережі на основі інтелектуальних агентів.

Формально, кожний агент i в системі діє в локальному оточенні. Отже, повне середовище системи може бути подано об'єднанням локальних оточень всіх агентів в системі у час t, які можуть частково перекриватися.

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

Внутрішній стан агента i у час t подамо такими компонентами його часткового уявлення:

де де - множина сусідніх агентів, які знаходяться у радіусі передавання вузла і з якими він може здійснювати безпосередній обмін повідомленнями;

- модель локального оточення - оцінка часу передавання пакета у межах радіусу передавання вузла і т. ін.;

- часткові знання від сусідніх агентів (вирахувана ними вартість маршрутів до місць призначення);

- локалізовані властивості системи (наближені знання від груп агентів або системи в цілому, що можуть виводитися з , і ) - оцінка кращого наступного переходу до місця призначення;

І - множина всіх можливих внутрішніх станів агента.

Множина всіх можливих станів системи S складається з множини всіх внутрішніх станів агентів st .

Введено абстрактну функцію корисності системи К, яка вимірює якість деякої бажаної системної властивості метрики для окремого стану системи і системного середовища.

Поведінку системи задамо як зміну станів системи і середовища. Стан системи повинен збігатися у напрямку до оптимальних станів.

Для координації поведінки агента і послідовного покращення бажаних властивостей системи необхідна деяка форма консенсусу відносно стану системи і середовища між підмножиною або всіма агентами системи.

Визначимо консенсус між множиною агентів введенням абстрактної метрики відстані a, що вимірює різницю між внутрішніми станами двох агентів. Будемо вважати, що система досягла строгого глобального консенсусу в час t, якщо відстань між будь-якими двома агентами в системі є нульовою.

Проте, така форма консенсусу неможлива, оскільки вона вимагала б синхронного отримання всіма агентами глобальних знань системи. Тому, агенти лише намагаються досягти локалізованих форм консенсусу в межах невеликих груп , де -множина агентів в системі у час t.

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

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

Індивідуальну поведінку П агента визначено трьома функціями:

де q - функція оцінювання корисності можливих у поточному стані дій;

c - функція вибору конкретної дії;

x - виконання відібраної дії.

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

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

Вибір конкретної дії (як на основі знань, так і дослідницької), здійснюється на основі імовірнісної моделі вибору дії с, яка повертає дискретний розподіл ймовірності (де - множина всіх розподілів ймовірностей на множині дій) такий, що

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

Адаптація агента полягає у оновлені його внутрішнього стану і поведінки внаслідок виконання дії x, як результату дій зворотного зв'язку з сусідніми агентами і локальним оточенням, і механізмів ослаблення.

Формально, утворений у час t зворотний зв'язок від агента j до агента i, визначимо як повідомлення зворотного зв'язку (де - множина всіх можливих повідомлень зворотного зв'язку), що генерується діями агента.

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

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

Зворотний зв'язок є головним механізмом адаптації поведінки агента.

У динамічних системах можливі два варіанти зворотного зв'язку: додатній і від`ємний, які підсилюють або послаблюють вибір дії агентом. Формально, додатній зворотний зв'язок підсилює використання дії агента i, якщо оновлений стан агента , покращує корисність цієї дії.

Міжагентний зворотний зв'язок, додатній або від`ємний, покращує консенсус між агентами. Якщо агент j посилає повідомлення зворотного зв'язку f до агента i, і агент i адаптує свій локальний стан, відстань між внутрішніми станами агентів i та j зменшується. Так само, коли агент i адаптує свій стан sі до зворотного зв'язку від середовища, sі стає більш узгодженим з еі.

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

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

Задача оптимізації формально визначена у контексті пошуку шляху у графі:

де S - множина розв'язків;

f - оціночна функція, що визначає якість розв'язку;

- кінцева множина обмежень.

Мета O полягає у знаходженні глобально мінімального розв'язку, що задовольняє обмеженням . Визначимо граф G = (C, L), множина С вершин якого подає компоненти, з яких може утворюватися розв`язок, а множина L ребер - множину зв'язків між компонентами. Початково G визначено як повний граф, і L подає всі можливі пари компонентів. Підмножина обмежень враховується видаленням з L певних ребер, чим відкидаються розв'язки, що не виконуються. Послідовність компонент , де визначимо як стан. Множину всіх можливих станів х позначимо Х.

Визначимо множину виконуваних станів , як множину станів, які не порушують обмеження , тобто

Множина розв'язків S - є власною підмножиною . Формалізуємо процес конструювання розв'язків з урахуванням механізмів самоорганізації:

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

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

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

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

Визначимо структури даних для моделі, що розробляється: агент маршрутизації (АМ); таблиця маршрутизації (рис.1а); таблиця локальної статистики ТЛСk. (рис.1б). Таблиці і ТЛСk підтримуються кожним вузлом мережі та оновлюються кожного разу при прибутті до вузлу АМ.

Для поєднання переваг проактивних та реактивних протоколів маршрутизації побудуємо два типи АМ: агентів дослідників (АД), та агентів конструкторів (АК), з однаковою структурою, але різною поведінкою у середовищі.

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

АК слідує у зворотному напрямку відкритим АД шляхом і модифікує Tk і ТЛСk.

Таблицю маршрутизації Tk організуємо як алгоритм вектору відстаней з імовірнісними значеннями Pnd, які для кожного можливого вузла призначення vd відображають бажаність вибору кожного сусіднього вузла vn як наступного транзитного вузла на шляху до vd.

Структура даних ТЛСk, визначає просту параметричну статистичну модель розподілу трафіку у мережі, як вона бачиться з локального вузла vk.

Для обчислення локальної статистики використаємо експоненціальну стратегією.

Таблиці Tk і ТЛСk фіксують різні аспекти динаміки мережі. Модель ТЛСk підтримує абсолютні оцінки відстані/часу для усіх вузлів. Таблиця маршрутизації Tk надає відносні ймовірнісні критерії якості для кожного зв'язку поточного вузла з кожним з вузлів призначення при поточній політиці маршрутизації.

На основі комп'ютерного моделювання досліджено ефективності розробленого протоколу в залежності від мобільності вузлів мережі і отримано підтвердження його переваг перед існуючим протоколом AODV.

У четвертому розділі досліджено питання зв'язності СММ в умовах високої рухливості її вузлів та розроблено модель та метод призначення потужностей вузлам ситуативної мобільної мережі при відсутності будь-якої глобальної оптимізації. Здійснено реалізацію розробленої технології адаптивної маршрутизації в мобільних мережах.

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

Для формалізації задачі оптимізації енергетичних потужностей вузлів СММ і визначення теоретичної основи забезпечення зв'язності СММ введемо ряд визначень.

Визначення 1. Графом топології СММ назвемо граф G, множина V вершин якого відповідає множині вузлів СММ, множина ребер - множині зв'язків між вузлами, а кінцева множина ваг - множині дискретних рівнів потужності, максимальний з яких Pmax =, назвемо повною потужністю передавання.

Визначення 2. Назвемо вузол сусідом k-рангу (k-сусідом) вузла , що позначимо як , якщо при призначенні вузлу потужності не меншої за , вузол потрапляє до діапазону його передавання. Зауважимо, що для mn сусід m-го рангу завжди є й сусідом будь-якого n-го рангу.

Визначення 3. Множиною k-сусідів вузла u, назвемо множину вузлів мережі, які потрапляють до діапазону передавання вузла u при призначенні йому потужності , тобто .

Сусідством (,u) вузла u, назвемо множину вузлів мережі, які потрапляють до діапазону передавання вузла u при призначенні йому повної потужності Pmax, тобто . Зауважимо, що для двонаправлених зв'язків виконується .

Визначення 4. При заданих множині вузлів V і призначенні потужностей Zt, граф - подає топологію для визначення Zt, якщо

При цьому |{u|(,,u)}|- є ступенем вузла , а - вагою зв'язку (,).

Визначення 5. Для вузлів (u,v)V, v - є досяжним з u з потужністю , що позначимо як (, u, v), якщо, і тільки якщо виконується:

Визначення 6. Для вузлів (u,v)V, v - є зв'язним з u при призначенні потужностей Zt і позначається як СON(Zt, u, v), якщо, і тільки якщо

Аксіома 1. Якщо кожний вузол використовує максимальну енергію Pmax, мережа є зв'язною:

Лема 1. Нехай задані множина V вузлів мережі і множина Z визначення потужностей вузлам мережі. Якщо кожний вузол при заданих визначеннях потужностей є досяжним для всіх своїх сусідів, то кожний вузол є зв'язним з усіма своїми сусідам. Тобто для заданих V і Z виконується:

Лема 2. Якщо при заданому призначенні потужностей Z кожен вузол може досягти всіх своїх сусідів, то мережа зв'язна. Тобто, для заданого Z виконується:

Теорема 1. Задане визначення потужностей, якщо за умов визначення кожному вузлу повної потужності, всі його сусіди є досяжними, то мережа є зв'язною. Доведення теореми безпосередньо випливає з лем 1 і 2.

Теорема 1 свідчить, що для забезпечення зв'язності мережі, за умов відсутності рухливості її вузлів, кожному вузлу vi достатньо розіслати пакети з різними рівнями потужності, і зібрати пакети від своїх сусідів для визначення мінімальної потужності серед усіх тих рівнів p, які забезпечують можливість обміну пакетами в обох напрямках вузла vi зі всіма своїми сусідами SNB(,vi). Проте, при рухливості вузлів, множина сусідів кожного вузла може змінюватися швидше ніж він встигне зібрати всі пакети, передані всіма його сусідами з різними рівнями потужності. Адаптуємо розподілений інтелект АСО як евристичний пошуковий механізм для визначення мінімізованого рівню потужності. Для цього, у кожному вузлі vj СММ створимо рейтингову таблицю, яка підтримує змінювані у часі значення рейтингів кожного рівня потужності p для кожного з сусідніх вузлів (таблиця 1). „Гарне значення” призначеної вузлу потужності визначається як зважена сума рейтингових і евристичних значень сусідніх вузлів, які пропорційні кількості сусідів, від яких прийняті породжені в них пакети та протилежні рівню потужності цих пакетів.

- множина сусідів vj у час t;

q[0,1]- випадкова змінна з нормальним розподілом;

q0[0,1] - настроюваний параметр;

PPs - рівень потужності, випадково вибраний з імовірністю .

де - евристика, визначена як (+1/p) і є інверсною рівню потужності, оскільки нижчі рівні потужності є більш привабливими;

- пристосовує відносні ваги різних рівнів потужності;

- врівноважує відносну вагу і ;

q0 - визначає компроміс між дослідженням нових рішень і експлуатацією наявних знань.

При отриманні пакету від вузла s з потужністю p, значення відповідного рейтингу підвищується згідно зі співвідношенням:

де =+1/Pmax.

У разі не підкріплення рейтингу певний період часу, його значення у рейтинговій таблиці зменшується.

На рис.2а наведено середню мінімізовану максимальну потужність min{Pmax} APP, CENT, і CBTC при змінній густині вузлів і максимальній швидкості 20 м/с. Із збільшенням густини вузлів мінімізована максимальна потужність трохи зменшується для CBTC, сильно зменшується для CENT і зменшується для APP між їхніми значеннями. Нагадаємо, що хоча CENT використовує глобальну інформацію для мінімізації потужностей передавання, він має невелику перевагу перед АРР у даному дослідженні і взагалі не може використовуватися при високій рухливості вузлів мережі, коли глобальна інформація стає недоступною.

2б показує залежність середнього ступеня вузла від густини вузлів. AРР має постійно більші значення ніж CBTC і CENT, які зростають із збільшенням густини вузлів. Відзначимо, що AРР min{} має середній ступінь вузла біля 6, який є оптимальним для зменшення інтерференції і нарощування мережі.

Згідно до вимог стандарту Інтернет RFC 2501 для СММ, для оцінки ефективності розробленої мультиагентної інформаційної технології адаптивної маршрутизації були використані такі показники, як накладні витрати маршрутизації, середня повна затримка даних та коефіцієнт доставки пакетів (КДП).

На рис.3а і 3б наведені результати дослідження впливу мобільності вузлів мережі на накладні витрати маршрутизації та КДП, відповідно, які свідчать про переваги розробленої технології над відомими протоколами AODV I DSR.

Рис.3. Вплив рухливості вузлів на характеристики ADK, AODV, DSR

а) накладні витрати маршрутизації;

б) КДП

Результати моделювання показали кращі показники розробленої мультиагентної технології щодо розв'язку задач адаптивної маршрутизації СММ і по інших показниках, засвідчивши підвищення ефективності функціонування і рівня масштабованості ситуативних мобільних комп'ютерних мереж.

ОСНОВНІ ВИСНОВКИ ТА РЕЗУЛЬТАТИ РОБОТИ

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

Внаслідок виконання дисертаційної роботи отримано такі основні наукові та практичні результати:

1. Здійснено теоретичний аналіз технологій маршрутизації та комп'ютерне моделювання відомих протоколів маршрутизації мобільних комп'ютерних мереж і визначено основні складнощі забезпечення маршрутизації в ситуативних мобільних комп'ютерних мережах. Це дозволило здійснити якісне і кількісне порівняння характеристик сучасних протоколів маршрутизації, зробити висновки щодо причин виявлених розбіжностей та обґрунтувати доцільність розробки мультиагентної інформаційної технології адаптивної маршрутизації СММ. Проаналізовано основні властивості природних мультиагентних систем та досліджено задачу побудови розподілених систем на основі принципу самоорганізації. Показано, що основними механізмами, що забезпечують самоорганізацію природних агентних систем є додатній і від`ємний зворотний зв'язок, випадковість та стігмергія, як непряма асинхронна форма комунікації агентів.

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

3. Обґрунтовано придатність методу АСО для розв'язку децентралізованої задачі, якою є побудова мультиагентної інформаційної технології адаптивної маршрутизації ситуативних мобільних комп'ютерних мереж, та сформульовано основні переваги його використання. Розроблено математичну модель адаптивної маршрутизації СММ на основі інтелектуальних програмних агентів, яка відрізняється відображенням механізмів самоорганізації природних систем. Це забезпечує можливість розробки технології маршрутизації з високим ступенем децентралізації та адаптивності до змін топології мережі в умовах рухливості її вузлів. На основі запропонованої моделі розроблено здатну до самоорганізації, децентралізовану мультиагентну інформаційну технологію адаптивної маршрутизації в ситуативних мобільних комп'ютерних мережах, що відрізняється можливістю прийняття рішень маршрутизації на основі лише локальної інформації та знань про локалізовані властивості системи і, відповідно, швидкістю реагування на зміни топології, мінімізацією широкомовних повідомлень та накладних витрат маршрутизації, підвищеним рівнем масштабованості та ефективності функціонування мережі в умовах високої рухливості її вузлів. З метою дослідження поведінки показників ефективності розробленої технології в залежності від змін розміру мережі та густини і рухливості її вузлів, проведено імітаційне моделювання з урахуванням особливостей функціонування СММ. Це дозволило виконати дослідження основних метрик запропонованої технології та підтвердило переваги застосування запропонованої технології маршрутизації в умовах високої рухливості вузлів мобільної мережі.

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

5. Здійснено практичну реалізацію запропонованої інформаційної технології адаптивної маршрутизації СММ і виконано її комп'ютерне моделювання, результати якого підтвердили високу ефективність використання мультиагентної технології до розв'язку задач маршрутизації СММ. Впровадження розробленої технології адаптивної маршрутизації дозволило підвищити ефективність функціонування і масштабованість ситуативних мобільних комп'ютерних мереж відносно різних метрик у середньому на 8-12% порівняно з відомими протоколами маршрутизації.

Отримані у дисертаційній роботі результати впроваджено при побудові ситуативних мобільних мереж компаній ЗАТ “ДатаГруп” і ТОВ „Міротел”, використано при виконанні науково-дослідних робіт та в навчальному процесі Вінницького національного технічного університету.

СПИСОК ОПУБЛІКОВАНИХ ПРАЦЬ ЗА ТЕМОЮ ДИСЕРТАЦІЇ

1. Хошаба A.М., Месюра Н.В. Решение некоторых проблем управления и защиты информационных ресурсов в компьютерных сетях // Оптико-електронні інформаційно-енергетичні технології. - 2002. -Т.4, №2. - С. 244-249.

2. Хошаба A.М., Месюра Н.В., Войцех А.А. Методы построения систем управления и мониторинга потоков данных в компьютерных сетях на основе интеллектуальных технологий // Вестник Херсонского национального технического университета. - 2003. - Т.18, №2. - С. 172-178.

3. Хошаба О.М., Месюра Н.В., Войцех О.А. Використання інтелектуальних технологій при побудові засобів захисту інформації в комп'ютерних мережах // Вісник Технологічного університету Поділля. - 2003. - Т.1, №3. - С

4. Лисак Н.В. Мультиагентный подход на основе муравьиного алгоритма для управления потоками данных в компьютерных сетях // Вестник Херсонского национального технического университета. - 2006. - Т.24, №1. - С. 289-295.

5. Лисак Н.В., Ференець В.Д. Адаптивна маршрутизація в мобільних комп'ютерних мережах на основі інтелектуальних агентів // Вестник Херсонского национального технического университета. - 2007. - Т.27, №4. - С. 401-404.

6. Лисак Н.В. Модель адаптивної маршрутизаціі мобільних комп'ютерних мереж з довільною структурою в умовах динамічних змін топології мережі // Оптико-електронні інформаційно-енергетичні технології. -2007. -Т.14, №2. - С.272-276.

7. Хошаба A.М., Месюра Н.В., Войцех О.А. Использование мультиагентных интеллектуальных систем в международной компьютерной сети INTERNET // Интернет - среда за нови технологии в информационното общество: V Междунар. науч. конференция. Велико Търново, 16-19 октомври 2002 г. - С. 27 - 35.

8. Хошаба A.М., Месюра Н.В. Практика решения проблем контроля и управления потоком данных в компьютерных сетях // Контроль і управління в складних системах: VII Міжнар. наук.-тех. конференція. Вінниця, 4-6 жовт. 2003 р. - С. 110.

9. Лысак Н.В. Математическая модель муравьиной маршрутизации // Інтелектуальні системи прийняття рішень та прикладні аспекти інформаційних технологій: Міжнар. наук. конференція. Євпаторія, 15-18 трав. 2006 р. - Т.1. - С. 318-321.

10. Хошаба О.М., Лисак Н.В., Ференець В.Д. Оцінка стійкості функціонування агентів мультиагентної системи в комп'ютерних мережах// Інтернет-Освіта-Наука: V Міжнар. наук. конференція. Вінниця, 10-14 жовт. 2006 р. - Т.2 - С. 383-388.

11. Лисак Н.В. Мультиагентний підхід до реалізації мурашкового алгоритму маршрутизації в дейтаграмних мережах // Інтернет-Освіта-Наука: V Міжнар. наук. конференція. Вінниця, 10-14 жовт. 2006 р. - Т.2. - С. 378-379.

12. Лисак Н.В. Мультиагентний підхід з використанням мурашкового алгоритму для маршрутизації // Інтелектуальний потенціал молоді в науці та практиці: Всеук. Наук. конференція студентів, аспірантів та молодих вчених Хмельницький, 19-20 жовт. 2006 р. - С.59-62.

13. Месюра В.И, Лысак Н.В. Управление топологией ситуативных мобильных компьютерных сетей на основе муравьиной оптимизации // Современные информационные системы. Проблемы и тенденции развития: ІІ Междунар. научн. конференція. Харьков, 2-5 окт. 2007 г. - С.71-72.

14. Лисак Н.В. Розробка і дослідження алгоритму маршрутизації мобільних комп'ютерних мереж з довільною структурою на основі інтелектуальних агентів // Прогресивні інформаційні технології в науці і освіті: Міжнар. наук. конференція. Вінниця, 10-14 жовт. 2007 р. - С.236-240.

15. Лисак Н.В., Месюра В.І. Математична модель інтелектуального агента для маршрутизації ситуативних мобільних мереж // Прогресивні інформаційні технології в науці і освіті: Міжнар. наук. конференція. Вінниця, 10-14 жовт. 2007 р. - С. 226-231.

АНОТАЦІЯ

Лисак Н.В. Мультиагентна інформаційна технологія адаптивної маршрутизації в мобільних комп`ютерних мережах. - Рукопис.

Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 05.13.06 - Інформаційні технології. - Вінницький національний технічний університет, Вінниця-2008.

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

Здійснений аналіз принципів самоорганізації природних мультиагентних систем доводить ефективність реалізації мультиагентної технології адаптивної маршрутизації ситуативних мобільних комп'ютерних мереж на основі методу мурашкової оптимізації.

Розроблено моделі інтелектуального агента маршрутизації та заснованого на агентах децентралізованого процесу маршрутизації в мобільних мережах, зручні з точки зору реалізації механізмів адаптації поведінки агентів маршрутизації в умовах недетермінованої топології мережі.

Доведено теорему зв'язності мережі, на основі якої запропоновано математичну модель та розроблено метод призначення потужностей передавання вузлам ситуативної мобільної мережі.

На основі запропонованих методів та моделей розроблено мультиагентну інформаційну технологію адаптивної маршрутизації ситуативних мобільних комп'ютерних мереж, комп'ютерне моделювання якої підтвердило високу ефективність її використання до розв'язку задач маршрутизації СММ.

Впровадження розробленої технології адаптивної маршрутизації дозволило підвищити ефективність функціонування і покращити масштабованість ситуативних мобільних комп'ютерних мереж відносно різних метрик у середньому на 8-12% порівняно з відомими протоколами маршрутизації.

Ключові слова: ситуативна мобільна комп'ютерна мережа, маршрутизація, агенти, мультиагентна системи, самоорганізація.

Лысак Н.В. Мультиагентная информационная технология адаптивной маршрутизации в мобильных компьютерных сетях. - Рукопись.

Диссертация на соискание ученой степени кандидата технических наук по специальности 05.13.06 - Информационные технологии. - Винницкий национальный технический университет, Винница-2008.

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

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

На основе осуществленного анализа принципов самоорганизации природных агентных систем показана эффективность реализации мультиагентной информационной технологии адаптивной маршрутизации ситуативных мобильных компьютерных сетей на основе метода АСО.

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

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

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

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

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

Внедрение разработанной технологии адаптивной маршрутизации позволило повысить эффективность функционирования и масштабируемость ситуативных мобильных компьютерных сетей относительно разных метрик в среднем на 8-12% в сравнении с известными протоколами маршрутизации. Результаты внедрения позволяют сделать вывод о правильности принципиальных положений, которые легли в основу работы.