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

Лисак Наталія Володимирівна

УДК 004.04:004.057.5

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

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

Автореферат

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

кандидата технічних наук

Вінниця – 2008

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

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

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

кандидат технічних наук, доцент

Хошаба Олександр Мирославович,

Вінницький національний технічний університет,

доцент кафедри інформаційного менеджменту

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

доктор технічних наук, професор

Квєтний Роман Наумович,

Вінницький національний технічний університет,

завідувач кафедри автоматики та

інформаційно–вимірювальної техніки

доктор технічних наук, професор

Кулаков Юрій Олексійович,

Національний технічний університет України

“Київський політехнічний інститут”,

професор кафедри обчислювальної техніки

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

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

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

Вчений секретар

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

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

Актуальність теми. Одним з найбільш динамічних напрямків розвитку ком-п’ютерних мереж сьогодні є розробка нових технологій та про-то--колів мар-ш-ру-ти-за-ції, здатних забезпечити функціонування ситуативних (ad hoc) мо-біль-них ме-реж (СММ), які утворюються мобільними вуз-лами за рахунок здій-с-нення тран-зитних пе-ре-дач без будь-якого попереднього конфігуру-ван-ня, інфра-струк-ту-ри або централі-зо-ва-но-го ад-мі-ністру-вання мережі. СММ застосовуються при ліквіда-ції сти-хійних лих; у військових діях; на зустрічах, учасники яких ба-жа-ють по-ді--ли-ти-ся інформацією і т. ін. Зрос-тання інте-ре-су до СММ підтверджує ство-рен-ня в ме-жах IETF робо-чих груп MANET (Mobile Ad hoc NETта ZEROCONF (Zero Confiа також проголошення 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 акти про впровадження.

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

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

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

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

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

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

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

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

(1)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(2)

де 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 підтримуються кожним вузлом мережі та онов--люються кож-ного разу при прибутті до вузлу АМ.

Рис. 1. Структури даних агентів мережі:

а) таблиця маршрутизації;

б) таблиця локальної статистики

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

Кожному АД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). „Гарне значення” призначеної вузлу потужності визначається як зважена сума рейтингових і евристичних зна-чень сусідніх вузлів, які пропорційні кількості сусідів, від яких прийняті породжені в них пакети та протилежні рівню потужності цих пакетів.

Таблиця 1

Рейтингова таблиця вузла v1

Найкращий рівень потужності Pb вибирається на основі рівняння:

(3)

Де ,

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

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

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

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

(4)

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

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

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

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

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

(5)

де =+1/Pmax.

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

На рис.2 наведено результати комп’ютерного моделювання розробленого на основі запропо-но-ваного методу алгоритму АРР призначення потужностей передавання вузлам СММ та двох відомих алгоритмів CENT і CBTC. Алгоритм CENT здій-снює централізоване призначенням потужностей передавання вузлам СММ на основі гло-бальної інформації про її топологію. Розподілений алгоритм CBTC виконує при-значення потужностей передавання вузлам СММ з урахуван-ням інформа-ції про кут прийому хвилі.

Рис. 2. Порівняння характеристик АРР, CENT і CBTC:

а) максимальна потужність min{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. – С. 138–142.

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.

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

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

Роз--роблено