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

“КИЇВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ”

Асад Mахмуд Асад Аль Насер

(Йорданія)

УДК 681.3

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

Спеціальність 05.13.13 - Обчислювальні машини,

системи і мережі

А В Т О Р Е Ф Е Р А Т

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

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

Київ - 2003 р.

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

Робота виконана в Національному технічному університеті України "Київський політехнічний інститут", на кафедрі обчислювальної техніки.

Науковий керівник: | кандидат технічних наук, доцент

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

НТУУ "КПІ", доцент кафедри ОТ.

Офіційні опоненти: | доктор технічних наук, професор

Тоценко Віталій Георгійович, Інститут проблем реєстрації інформації НАН України, завідувач відділу надійності та діагностики.

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

Коваленко Анатолій Єпіфанович,

Український державний університет харчових технологій, завідувач кафедри інформатики.

Головна організація | Інститут проблем моделювання в енергетиці НАН України, відділ спеціалізованих засобів моделювання.

Захист відбудеться "_15_"_грудня_ 2003 р. о 14:30 на засіданні спеціалізованої ради Д 26.002.02 у НТУУ "КПІ (м. Київ, пр. Перемоги, 37, корп. 18, ауд. 306).

Відзиви на автореферат у двох екземплярах, завірені печаткою установи, просимо надсилати на адресу: 03056, м. Київ, пр. Перемоги, 37, вченому секретарю НТУУ "КПІ".

З дисертацією можна ознайомитись в бібліотеці Національного технічного університету України "Київський політехнічний інститут"

Автореферат розісланий "_14_"_листопада_ 2003 р.

Вчений секретар спеціалізованої ради, кандидат технічних наук, доцент | М.М. Орлова

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

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

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

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

Зв'язок роботи з науковими програмами, планами, темами. Дисертаційна робота виконувалася в 2000-2003 рр. відповідно до планів науково-дослідних робіт кафедри обчислювальної техніки НТУУ "КПІ": НДР № 0100U000703 "Розробка теорії, методів і засобів побудови обчислювальних систем з масовим розпаралелюванням обчислювального процесу" і в рамках НДР № 0102U000333 "Побудова масштабованих ізоефективних комп'ютерних систем", яка виконується на кафедрі обчислювальної техніки НТУУ "КПІ" в 2002-2004 рр.

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

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

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

Основні задачі дослідження, у відповідності з поставленою метою, полягають у наступному:

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

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

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

4. Розробка ефективної процедури формування і оновлення маршрутної інформації, що враховує імовірність переміщення АС.

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

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

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

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

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

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

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

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

5. Запропонована й обґрунтована структура маршрутизатора й адаптивний алгоритм його функціонування, який формує маршрут передачі інформації в залежності від інтенсивності реконфігурації мережі та завантаження її вузлів.

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

Особистий внесок здобувача. Основні результати отримані автором самостійно. Автор розробив наступне:

1.

2.

3.

4.

5.

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

Апробація роботи. Основні результати дисертаційної роботи обговорювалися на:

1. IX науково-технічній конференції “Вимірювальна та обчислювальна техніка в технологічних процесах ” (31 травня - 3 червня 2001 р., Хмельницький).

2. X науково-технічній конференції “Вимірювальна та обчислювальна техніка в технологічних процесах ” (30 травня - 2 червня 2002 р., Хмельницький).

Публікації. Основні результати дисертаційної роботи опубліковані в 9 наукових працях, серед яких 7 наукових статей у журналах, затверджених ВАК, і дві публікації матеріалів конференцій.

Структура й обсяг дисертації. Дисертаційна робота складається зі вступу, чотирьох розділів, висновків і додатку. Загальний обсяг роботи складає 131 сторінок друкованого тексту, 57 рисунків, 11 таблиць, і списку використаної літератури з 71 найменування.

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

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

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

Для мобільних комп'ютерних мереж як критерій оптимальності вибору маршруту необхідно розглядати час ремаршрутизації, що є складовою частиною часу пересилання. Ремаршрутизація містить у собі процедуру керування місцем розташування, що складається з реєстрації місцеположення і оновлення маршрутної інформації. В загальному вигляді час ремаршрутизації Тр дорівнює: Тр=kuЧ?u +ksЧ?s,

де: Тs - час реєстрації місця розташування; Тu - час оновлення маршрутної інформації, про одне переміщення між суміжними комірками.

Коефіцієнти ku і ks вибираються з врахуванням відношення r середнього числа запитів на з'єднання до числа переміщення між областями реєстрації, при цьому: ku = 1/r і ks = r.

З врахуванням цього, час ремаршрутизації Тр дорівнює: Тр= rЧ?s+1/rЧ?u.

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

Тс = Тз + Тр,

де: Тз - затримка в передачі по ланці дерева, тобто між сусідніми вершинами; Тр – час комутації в точці розгалуження.

При наявності деякого числа k проміжних ланок час маршрутизації дорівнює: Тс = ТзЧ k + Тр.

При розташуванні точки розгалуження на i-му рівні Тi дорівнює Тi = ТзЧ i + Тр.

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

. (1)

На підставі аналізу виразу (1) можна зробити висновок, що зі скороченням числа рівнів дерева скорочується час відновлення маршруту. Таким чином, задачу скорочення часу відновлення маршруту можна звести до задачі побудови дерева з мінімальним числом рівнів.

На основі аналізу відомих способів розподілу множин був запропонований алгоритм формування комірок мобільної мережі, що відрізняється від відомих кращою збіжністю. Як критерій розподілу мережі на комірки, розглядається мінімальна вартість мережі, що досягається при мінімальному числі комірок і базових станцій (БС). Як обмеження виступають: максимально припустимий діаметр комірки; максимальне значення пропускної здатності БС. Додатковим параметром оптимізації виступає інтенсивність потоку між комірками.

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

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

Для представлення мобільної мережі використовується випадковий граф

G = (V, E), кожному ребру якого ставиться у відповідність величина pi,j, що характеризує імовірність вилучення ребра ei,j із графа.

Відповідно, вираз p0i,j = 1- pi,j характеризує стійкість ребра ei,j між суміжними вершинами vi і vj, а вершина pi являє собою ймовірність вилучення або переміщення вершини.

В свою чергу, стійкість Sn,m шляху Zn,m є функцією стійкості si,j усіх ребер даного шляху, тобто:

(2)

З урахуванням виразу pi,j = pi . pj, маємо:

(3)

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

k= (T0 -- Ts)/ T0 ,

де T0 -– час життя маршруту, що залежить від стійкості вибраного маршруту, в якості вершин якого розглядаються БС.

В зв'язку з цим визначена необхідна й достатня умова вибору АС vi в якості БС bj комірки Сj:

bj = {vi (1– pj )=max vi Wj }, (4)

де: Wj - множина потенційних БС комірки Сj j .

Нехай Rj – радіус комірки С1, а ri – радіус покриття АС vi.

Умова ri = Rj припускає наявність єдиної АС, розташованої точно в центрі комірки.

Умова ri Rj допускає наявність декількох АС, розташованих в області Wj з радіусом rwj = ri – Rj . vi Wj є потенційними БС.

Число р, що визначає кількість vi Wj, називатимемо р-центром комірки.

Аналогічним чином визначаємо умову вибору АС vi як міст mi,j між комірками Сi і Сj:

; (5)

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

1. Формуємо множину V0 ={vi}, що складається з початкової вершини vi.

2. Визначаємо множину VГ ={vj vj Г(vi V0)} вершин vj, суміжних з вершинами множини V0.

3. Серед вершин множини VГ знаходимо вершину vj V\V0, з максимальнім значенням Si,j і включаємо її в множину V0. Запам'ятовуємо шлях Zi,j

4. Якщо VГ , то переходимо до пункту 3, інакше алгоритм завершує свою роботу. В результаті формується шлях Zi,j з максимальним значенням Si,j.

При відсутності шляху з заданим значенням стійкості замість одного шляху пропонується формувати стійкий підграф доставки повідомлень. Основна відмінність даного алгоритму від алгоритму формування стійкого шляху полягає в тому, що при формуванні множини B={bj} впорядкованих пар bj= (vi, Pi,j) для кожної вершини vj вибирається декілька bj з найбільшими значеннями Pi,j.

З метою зниження часової складності задачі маршрутизації, граф мережі розбивається на кілька K-кластерів, що перекриваються, де k – кліка кластера. В мобільних комп'ютерних мережах мінімальна складність маршрутизації досягається при k =1, однак у цьому випадку додавання нової вершини vi у графі G= (V, E) приводить до появи, принаймні, одного нового кластера. Це може привести до того, що один чи кілька кластерів стають надлишковими. В цьому випадку, необхідно вирішувати задачу видалення надлишкових кластерів. В роботі розглянуті наступні події, що можуть викликати зміни в структурі графа:

1) Включення АС (Switching ON): включення АС vi відповідає додаванню вершини vi у граф та її підключення до всіх АС в зоні її дії. Отже, V ' = V { vi } і E ' = E {( ei,j), vi зв'язаний з vj }.

2) Відключення АС (Switching OFF): Відключення АС приводить до виключення вершини vi із графа і видалення всіх ії ребер. Отже, V ' = V - { vi } і E ' = E - { ei,j, vj V ' }.

3) АС vi з'єднана з АС vj: ребро між vi і vj буде додане в графі. Отже V ' = V і E ' = Е{( ei,j)}.

4) АС vi від'єднана від АС vj: ребро між vi і vj буде вилучене з графа. Отже, V ' = V і E ' = E- {( ei,j)}.

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

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

При переміщенні АС, що не є БС, або появі нової АС приймається, що вона або буде включена в один з існуючих кластерів, або буде створений новий кластер.

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

Якщо в кластері є n вузлів, що можуть виконувати функції БС, і ймовірність їхнього виходу за область, у якій вони можу виконувати роль БС, дорівнює pi, i ...n; Tl – час локальної ремаршрутизації мережі, а Тf – час повної ремаршрутизації, то загальна оцінка часу ремаршрутизації визначається за формулою:

T Tl Тf - Tl) ·p1· p2· ... ·pn). (6)

При цьому обсяг переданої службової інформації (SV ) дорівнює:

SV Sl Sf - Sl) ·p1· p2· ...· pn), (7)

де: Sf  ? обсяг службової інформації, необхідної для повної ремаршрутизації, Sl ? для ремаршрутизації в межах кластера.

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

Розроблено адаптивний алгоритм формування і оновлення маршрутної інформації, в рамках якого маршрутизація визначається через комплекс взаємодій спеціальних керуючих пакетів, названих сигнальними пакетами. Сигнальні пакети поділяються на два класи: прямі сигнальні пакети (ПСП) і зворотні сигнальні пакети (ЗСП). ПСП не виконують оновлення таблиць маршрутизації вузлів. Їх метою є збір інформації для ЗСП. Ця інформація представляється як час затримки передачі між вузлами мережі. ЗСП використовують інформацію, зібрану ПСП, для оновлення таблиць маршрутизації, елементами якої є імовірності переходів.

Таблиці маршрутизації обновлюються на основі динамічного параметра r’, що задається в такий спосіб:

; (8)

де T – час переходу, Tcp - середнє значення T, і c – змінний коефіцієнт, зазвичай рівний 2.

Імовірності таблиці маршрутизації оновлюються за такими правилами:

(9)

, (10)

де vj – вузол-одержувач, vi – вузол, з якого прийшов ЗСП, Vj =(vm vm= Г(vj)) - множина вузлів vm, суміжних з вузлом vj .

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

В рамках дисертаційної роботи проведений аналіз ефективності запропонованого алгоритму (Full Optimization) стосовно базового алгоритму DSR без оптимізацій (в програмі позначений як No Optimization) і алгоритму DSR з розширеним використанням прослуховування пакетів для відновлення маршрутної інформації (Base Optimization). При моделюванні досліджувалася залежність ефективності роботи алгоритмів від швидкості АС, їхньої концентрації й інтенсивності трафіка.

На рис. 3 представлена залежність ефективності алгоритмів для 11 АС та інтенсивності пакетів 0,125Кбіт/с від зміні швидкості переміщення АС. Як видно з цього рисунку, ефективність пропонованого алгоритму вища, ніж у інших алгоритмів. На рис. 4 приведене завантаження мережі для 11 АС та інтенсивності пакетів 0,125Кбіт/с.

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

,

де: – оптимальна оцінка прогнозу RTT для моменту часу tn+k; RTT- інтервал між посилкою пакета й одержанням підтвердження; – оптимальна оцінка процесу дробового броунівського руху з параметром Херста для моменту часу tn+k ; – оптимальна оцінка процесу дробового броунівського руху з параметром Херста для моменту часу tn+k-1 ; – мінімальна складова інтервалу часу без черги; – середнє збільшення значення RTT.

В роботі вводиться два граничних значення RTT0 і RTT1.

За умови RTT1 RTT RTT0 регулювання величини RTT здійснюється шляхом зменшення значення вхідного трафіка. При RTT RTT1 виконується процедура часткової чи повної ремаршрутизації.

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

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

Запропонована схема керування мобільністю заснована на дворівневій ієрархії даних, при якій для відстеження місця перебування АС використовуються регістри домашнього місця розташування ( HLR - Home Location Register) і регістри гостьового місця розташування (VLR- Visitor Location Rеgister). Інформація про кожного користувача, така як місце розташування та список наданих послуг, зберігається в профілі користувача, що знаходиться в HLR свого кластера. Кожний VLR зберігає інформацію про АС, що тимчасово знаходиться в даному кластері.

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

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

В результаті моделювання маршрутизації в мережі передачі даних, отримані наступні залежності:

1. Відношення числа оптимально обраних маршрутів до загального числа розрахованих маршрутів в залежності від інтенсивності відновлення маршрутної інформації при фіксованому значенні інтенсивності зміни метрик; На рис. 5 зображена залежність ефективності маршрутизації від інтенсивності оновлення маршрутної інформації. Суцільна лінія відповідає інтенсивності зміни вартості каналу в 0.2 с-1, переривчаста - 0.1 с-1.

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

На рис. 6 зображена залежність ефективності маршрутизації від інтенсивності зміни вартостей каналів. Суцільна лінія відповідає інтенсивності відновлення маршрутної інформації в 0.01 с-1, крупний штрих - 0.001 с-1, лінія з круглими мітками оригінальному алгоритму JEB.

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

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

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

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

Основні наукові і практичні результати роботи полягають у наступному:

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

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

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

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

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

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

Основні результати відображені у наступних публікаціях:

1. Асад Махмуд Асад Аль Насер. Формирование структуры беспроводной сети Аd Hoc // Вимірювальна та обчислювальна техніка в технологічних процесах. 2001. - № 3. - С. 187-190.

2. Асад Махмуд Асад Аль Насер. Алгоритмы формирование инфраструктуры беспроводной сети // Вісник НТУУ “КПІ” Інформатика, управління та обчислювальна техніка. – 2002. - № 37. - С. 98-105.

3. Кулаков Ю.А., Асад Махмуд Асад Аль Насер. Метод маршрутизации на основе использования модифицированной нейронной сети ДЭБ // Вимірювальна та обчислювальна техніка в технологічних процесах. – 2000. - № 4. - С. 95-98. – автору належить розробка методу маршрутизації інформації.

4. Кулаков Ю.А., Асад Махмуд Асад Аль Насер. Реализация распределенных вычислений в компьютерных сетях // Электроника и связь. – 2001. - № 13. -С. 80-84. – автором запропоновано алгоритм розподілених обчислень в комп`ютерних мережах.

5. Кулаков Ю.А., Асад Махмуд Асад Аль Насер, Муаффаг Ахмед Абдул-Рахман Абу-Алхайжа. Анализ протоколов маршрутизации в беспроводных компьютерных сетях // Вимірювальна та обчислювальна техніка в технологічних процесах. – 2002. - № 1. - С. 92-98. – автору належить аналіз протоколів маршрутизації в безпровідних мережах.

6. Кулаков Ю.А., Асад Махмуд Асад Аль Насер, Муаффаг Ахмед Абдул-Рахман Абу-Алхайжа. Управление трафиком в беспроводных сетях АТМ // Вимірювальна та обчислювальна техніка в технологічних процесах. – 2001. - № 4. - С. 99-104. – автором розроблено алгоритм керування доставкою повідомлень в мобільних мережах.

7. Асад Махмуд Асад Аль Насер, Аль Рабабах Мохамед Абдель-Кадер. Способ формирования устойчивых виртуальных соединений в мобильных компьютерных сетях // Вісник НТУУ “КПІ” Інформатика, управління та обчислювальна техніка. – 2002. - № 39. - С. 126-131. - автору належить розробка способу формування віртуальних з`єднань в мобільних мережах.

8. Асад Махмуд Асад Аль Насер. Кластерный подход к маршрутизации в беспроводных сетях АD НOC” // Вимірювальна та обчислювальна техніка в технологічних процессах, збірник наукових праць. – 2002. - № 9. - С. 168-171.

9. Кулаков Ю.А., Асад Махмуд Асад Аль Насер. Применение нейронов для маршрутизации информации в компьютерных сетях // Вимірювальна та обчислювальна техніка в технологічних процессах, збірник наукових праць. – 2001. - № 8. - С. 92-95. - автору належить розробка структури маршрутизатора нейронної мережі.

Асад Махмуд Асад Аль Насер „Організація процесів передачі інформації в мобільних комп'ютерних мережах з реконфігурацією топології”. Дисертація на здобуття вченого ступеня кандидата технічних наук за спеціальністю 05.13.13 – обчислювальні машини, системи і мережі. Національний технічний університет України “Київський політехнічний інститут”, Київ 2003.

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

Запропоновано спосіб формування стійкої топології мобільної мережі з реконфігурацією топології.

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

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

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

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

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

Асад Махмуд Асад Аль Насер „Организация процессов передачи информации в мобильных компьютерных сетях с реконфигурацией топологи”. Дисертація на здобуття вченого ступеня кандидата технічних наук за фахом 05.13.13 – обчислювальні машини, системи і мережі. Національний Технічний Університет України “Київський Політехнічний Інститут”, Київ 2003.

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

На основе анализа известных методов разбиения множеств предложен и обоснован способ формирования ячеек мобильной сети, позволяющий за счет соответствующего выбора базовых станций (БС) повысить устойчивость инфраструктуры мобильной сети. Выбор абонентской (АС) vi в качестве БС bj ячейки Сj осуществляется исходя из условия:

bj = {vi (1– pj )=max vi Wj },

где: Wj - множество потенциальных БС ячейки Сj.

АС vi Wj при условии ri =Rj , где: Rj – радиус ячейки С1, а ri - радиус покрытия АС vi. Аналогичным образом определяем условие выбора АС vi в качестве моста mi,j между ячейками Сi и Сj: .

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

где: pi - вероятность перемещения вершины во время Ts.

Процедура формирования максимально устойчивого пути заключается в следующем:

1. Формируем множество V0 ={vi}, состоящее из начальной вершины vi.

2. Определяем множество VГ ={vj vj Г(vi V0)}вершин vj, смежных с вершинами множества V0

3. Среди вершин множества VГ находим вершину vj V\V0, с максимальным значением Si,j и включаем ее во множество V0. Запоминаем путь Zi,j

4. Если VГ , то переход к пункту 3, иначе алгоритм завершает свою работу. В результате формируется путь Zi,j с максимальным значением Si,j.

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

T = Tl + ( Тf - Tl) · (p1·p2· ... ·pn),

где: Tl – время локальной ремаршрутизации внутри кластера, Тf – время ремаршрутизации, связанное с изменением общей структуры сети, pi – вероятность выхода АС vi за область, в которой она может выполнять роль БС, n - число АС , способных выполнять функции БС. При этом объем передаваемой служебной информации (SV ) равен:

SV = Sl + ( Sf - Sl) · (p1·p2·...·pn),

где: Sf -  объем служебной информации, необходимой для полной ремаршрутизации, Sl - для ремаршрутизации в пределах кластера.

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

и

,

где: Pj,i - вероятность перехода в направлении узла из которого пришел ОСП; Pj,m –вероятность перехода в направлении других узлов; r’ – динамический параметр, зависящий от времени прихода ОСП.

Начальное значение вероятности Pj,i определяется значением Sn,m.

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

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

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

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

Асад Махмуд Асад Аль Насер “Organization of processes of information transfer in mobile computer networks with reconfiguration of topology“. The dissertation on competition of a scientific degree of Cand.Tech.Sci. on a speciality 05.13.13 – computer system and networks. National University of Ukraine “Kiev Polytechnic Institute”, Kiev 2003.

Dissertational work dedicated to development ways and means of productivity increase in information communication procedure in mobile computer networks with reconfiguration topology.

The way of stable topology formation in mobile network with reconfiguration of topology is offered.

The adaptive algorithm of routing was developed which allow in comparison with known algorithms of routing reduce size of the control data, necessary for organization and maintenance of information communication process.

There is an algorithm of data thread control which in comparison with known algorithms raises efficiency of information transfer control procedure in mobile computer networks.

The approach to construction of the adaptive routers functioning on the basis by a principle of neural networks and oriented to functioning in networks with dynamic changing of links structure are offered.

From the practical point of view, the results which draw in-process, allow greatly increase the efficiency of functioning of mobile computer networks with reconfiguration topology.

Keywords: the mobile network, reconfiguration of topology, rerouting, a cluster, a base station.