Библиотечный каталог авторефератов Украины

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

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

Халіль Хамді Атіє Аль Шкерат

(Йорданія)

УДК 681.3

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

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

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

А В Т О Р Е Ф Е Р А Т

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

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

Київ - 2004 р.

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

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

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

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

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

Автореферат розісланий  "_14_"_квітня_ 2004 р.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1. X науково-технічній конференції “Вимірювальна та обчислювальна техніка в технологічних процесах ” (28-31 травня 2003р., м. Хмельницький).
1. Четвертій міжнародній науково–практичній конференції "Сучасні інформаційні й електронні технології" (19-23 травня 2003р., м. Одеса).

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

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

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

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

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

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

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

Більшість відомих способів вибору структури мережі й пропускної спроможності каналів зв'язку використовують потокові моделі, засновані на інтенсивностях Fi,j трафіка в каналах ei,j мережі. Як функцію оптимізації в більшості випадків вибирають вартісну функцію вигляду: , де кожна функція Di,j є монотонно зростаючою. При цьому для обчислення Di,j (F i,j) використовується вираз: де Ci,j пропускна спроможність каналу зв'язку ei,j, tu –  затримка обробки і поширення. Передбачається, що трафік  потоку, що надходить у будь-який канал ei,j, змінюється тільки через відновлення маршрутів. Таке припущення є коректним, коли зміна трафіка відбувається відносно повільно в порівнянні з середнім часом, необхідним для зменшення черг у мережі, і коли потоки в лініях виміряються шляхом часового усереднення.

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

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

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

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

Комп'ютерна мережа представлена у вигляді навантаженого графа G(V, E), де V= { vi зi=1,2…m} - множина вершин графа, E={ei,j зi,j=1,2…m}–множина ребер графа. Кожне ребро ei,j графа характеризується вагою wi,j. При розгляді питань маршрутизації у магістральних мережах під вагою wi,j ребра ei,j мається на увазі  затримка ti,j одиниці інформації між вузлами мережі vi і vj. Обмеженням виступає значення припустимої затримки td доставки одиниці інформації між довільними вузлами мережі, а як параметр оптимізації розглядається сумарна затримка Ts,r на шляху Ls,r. В даному випадку завдання маршрутизації полягає в знаходженні шляху L(vs,vr)= (es,i, …, ej,r) між вершинами vs і vr   для якого виконується умова:

де: Ts,r - сумарна затримка на шляху L(vs,vr).

У якості обмежень на включення ребра ei,j до складу шляху Ls,r розглядаються умови:

• C(i,j)> cs, де: C(i,j) - пропускна спроможності каналу; cs - необхідне значення пропускної спроможності для доставки повідомлень шляхом Ls,r.
• td > tm , де: td – припустима затримка передачі пакетів; tm – максимальна затримка передачі пакетів між вузлами дерева передачі даних.

Відповідно до дворівневої структури корпоративної мережі, граф G(V, E) може бути представлений у вигляді графа G0 (V0, E0), що визначає структуру магістральної підмережі, і деякої множини підграфів {Gi(Vi, Ei) |i=1,…,n}, що відповідає локальним підмережам корпоративної мережі.

В загальному випадку, для вершини vs∈V1 підграфа G1 = (V1,E1) і вершини vr∈V2 підграфа G2 = (V2,E2), а також граничних вершин vk∈V1 (∃ ek,i , v i∈V0) і vm∈V2 (∃ em,j ,vj∈V0 ), шлях L(vs,vr) визначається виразом: L(vs,vr) = L1(vs,vk)+ L0(vk,vm) + L1(vm,vr) . Відповідно сумарна затримка Ts,r шляху L(vs,vr) дорівнює:

При перебуванні вершини джерела чи приймача всередині магістральної мережі відповідний доданок у виразі (2) відсутній. Наприклад, при vs∈V0 шлях L(vs,vr) = L0(vs,vm) + L1(vm,vr), відповідно:

При перебуванні джерела і приймача в одній локальній мережі, тобто при vs∈V1 і vr∈V1  , шлях L(vs,vr) = L1(vs,vr) , а величина Ts,r дорівнює:

Якщо швидкість передачі інформації в локальних підмережах вища швидкості передачі інформації в глобальних мережах, при L0(vs,vm) = L1(vm,vr),  де: L0(vs,vm) - довжина шляху на ділянці глобальної мережі; L1(vm,vr) - довжина шляху на ділянці локальної мережі, виконується умова:

При розташуванні джерела й адресата в різних локальних мережах на значній відстані один від одного: .

В цьому випадку Ts,r ≈ Tk,m і, відповідно:        

Звідси випливає, що в даному випадку основну увагу необхідно приділяти питанням побудови оптимального шляху на графі G0 (V0, E0). При переміщенні мобільного абонента між локальними підмережами, представленими відповідно підграфами G1 = (V1,E1) і G2 = (V2,E2), у графі G0 (V0, E0) відбувається зміна початкового шляху L0(vk,vm) новим шляхом L1(vk,vl). Гранична вершина vi підграфа G2 = (V2,E2), визначається за умовою vk∈V2 (∃ek,i,vi∈V0). Припустимо, що шлях L0(vk,vm) складається з множин ребер EL0={ei,j∈L0(vk,vm), а шлях L1(vk,vl) складається з множин ребер EL1={ei,j∈L0(vk,vm). В результаті переміщення мобільного абонента деяка множина ребер Em ⊆ EL0 заміняється новою множиною ребер El ⊆ EL1. Об'єднання цих множин утворить множину Es ребер, що бере участь у процесі реконфігурації шляху. Потужність множини Es характеризує часову складність процедури реконфігурації вихідного шляху. Множина Es визначається наступним виразом:

Якщо шляхи L0(vk,vm) і L1(vk,vl) не співпадають, то EL0∩ EL1 =∅. В цьому випадку потужність множини Es буде максимальною. При формуванні маршруту L1(vk,vl) за рахунок продовження вихідного маршруту L0(vk,vm) потужність QS множини Es буде мінімальною. Припустимо, що в результаті зміни маршруту додається ребро ei,j. В цьому випадку множину ребер EL1={ EL0, ei,j} можна представити у вигляді EL1= EL0∪ {ei,j}. Таким чином: Es= (EL0∪ (EL0∪ {ei,j}))\ (EL0∩ (EL0∪ {ei,j})) =(EL0∪ ei,j)\ EL0 = {ei,j}.

При переміщенні мобільного абонента між декількома локальними мережами формується множина шляхів { Li(vk,vj) |i=0,…,(n-1); j=p,…q} між початковою вершиною vk і вершинами множини Vr = { vj | j=p,…q}, що відповідають переміщенню мобільного абонента. У даному випадку:

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

де: QLi - потужність множини ELi. Значення коефіцієнта ks змінюється в межах (0 ÷1). При ks → 0 реконфігурація буде мінімальною. При ks =1 шлях перебудовується повністю. Як випливає з виразу (9), ks → 0 при QS → 0. В свою чергу, величина QS визначається кількістю ребер, що формують шлях між вершинами vp і vq. Значення QS буде мінімальним тільки для найкоротшого шляху між вершинами vp і vq. Потім сформуємо найкоротший шлях від початкової вершини до найближчої вершини з множини вершин приймачів інформації. В результаті з множини шляхів буде сформоване остове дерево STk(Vk,Ek) з початковою вершиною vk і мінімальним значенням ks. Таким чином, задача формування маршрутів доставки інформації за критерієм часової складності ремаршрутизації зводиться до задачі побудови остового дерева з мінімальним числом ребер. Вирішення цієї задачі зручно розпочинати зі знаходження найкоротшого шляху від вершини vk до найближчої вершини vm ∈ Vr.

Алгоритм формування дерева

1. За допомогою алгоритму Дейкстри визначається мінімальний шлях L0(vk,vm) від вершини vk до найближчої вершини vm ∈ Vr.
2. Вершина vm вилучається із множини Vr і включається в множину EL0, тобто vm ∉ Vr → vm ∈ EL0.
3. Серед решти вершин множини Vr визначається вершина vi ∈ Vr , найближча до однієї з вершин vj ∈ EL0. За умови, що шлях L0(vk,vm) мінімальний, вершиною vj виступатиме вершина vm.
4. Формується шлях L1(vk,vi) = L0(vk,vm)+ em,i.
5. Вершина vi вилучається із множини Vr і включається в множину EL1, тобто vi ∉ Vr → vi ∈ EL1.
6. Серед решти вершин множини Vr визначається вершина vi+1 ∈ Vr , найближча до однієї з вершин vj ∈ EL0 або vl ∈ EL1.
7. При ei,j > ei,l формується шлях L1(vk,vi+1) = L1(vk,vl)+ el,i+1 інакше подовжується шлях L0(vk,vi+1)= L0(vk,vm)+ ej,i+1.
8. Вершина vi+1 вилучається із множини Vr і включається в множину EL1 або множину EL0.
9. При Vr ≠ ∅ перехід до пункту 6.
10. Завершення процесу формування дерева доставки.

В даному випадку формуються два шляхи L0(vk,vp) і L1(vk,vq) від вершини vk до крайніх вершин vp і vq. У випадку, коли в якості однієї з вершин vp чи vq виступає vm, формується тільки один шлях L0(vk,vp) або L0(vk,vq).

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

Для врахування обмеження на затримку передачі в пунктах 3 і 6  алгоритму формування дерева доставки при виборі вершини дерева, до якої підключаться нова вершина, додатково перевіряється умова td > tm. При виконанні цієї умови виконується підключення вершини. В протилежному випадку як претендент на підключення вибирається наступна вершина раніше сформованого дерева і так далі. У кращому випадку, як і без врахування умови td > tm , буде сформований тільки один шлях, що зв'язує усі вершини множини Vr з вершиною vk. У гіршому випадку, при жорстких обмеженнях на затримку передачі, дерево доставки може бути сформоване тільки за умови EL0∩ EL1 ∩ …∩ EL(n-1) =∅. При цьому задача реконфігурації віртуального каналу зводиться до повної ремаршрутизації.

Даний результат може бути узагальнений на випадок, коли і вершина vs переміщується. У цьому випадку дерево STk(Vk,Ek) доповнюється новими вершинами з множини Vs .

Алгоритм формування дерева доставки може бути використаний і для випадку, коли джерело ( вершина vs) переміщується. В цьому випадку в рамках підграфа G0 (V0, E0) формується множина Vs = { vz | z=k,…h}, що відображає переміщення vs. В результаті дерево STk(Vk,Ek) доповнюється новими вершинами з множини Vs ⊂ V0 . Підключення вершин vz ∈ Vs здійснюється відносно вершини vk у відповідності до приведеного вище алгоритму.

В третьому розділі розглядаються питання формування віртуальної структури корпоративної мережі. На рівні магістральної підмережі підграфа G0 (V0, E0) ця задача зводиться до задачі об'єднання остових підграфів у єдиний підграф Gd (Vd, Ed), оптимальний з точки зору обраних критеріїв  та обмежень. На рівні локальних мереж дана задача зводиться до задачі формування віртуальних підмереж з мінімальним потоками між підмережами. При цьому враховується область переміщення мобільного абонента. Вихідними даними є інтенсивність інформаційних потоків, характер переміщення й імовірність перебування мобільного абонента у тій чи іншій локальній мережі. Задача вирішується щодо всіх мобільних абонентів, які входять до складу корпоративної мережі, при цьому замість одного дерева формується множина дерев доставки ST0 ={ STk(Vk,Ek) з k=1,2,…,m}.

Задача зводиться до об'єднання множини дерев доставки ST0 у підграф Gd (Vd, Ed) , що задовольняє наступним вимогам:

При об'єднанні дерев STk(Vk,Ek) виникає задача розподілу потоків. З цією метою для кожного ребра ei,j дерева STk(Vk,Ek) передачі інформації будемо використовувати наступний коефіцієнт завантаження Ri,j

З урахуванням виразу (12), коефіцієнт завантаження RΣ всього дерева доставки повідомлень:

Далі визначимо варіацію коефіцієнта завантаження мережі:

де Np– кількість ребер дерева доставки. Для оптимального завантаження мережі необхідно, щоб δ → 0.

В роботі пропонується наступний алгоритм формування підграфа доставки повідомлень Gd (Vd, Ed) в рамках підграфа G0 (V0, E0) .

Алгоритм об'єднання множини дерев в підграф.

1. Початок.
2. У множині ST0 ={ STk(Vk,Ek) з k=1,2…m} дерев доставки вибираємо дерево STi(Vi,Ei) з максимальним діаметром Di.
3. Надаємо значення Dmax = Di.
4. Приймаємо Gd (Vd, Ed) = STi(Vi,Ei).
5. Формуємо множину ST0 = ST0 \ STi(Vi,Ei).
6. Серед дерев STi(Vi,Ei) ∈ ST0 обираємо дерево STj(Vj,Ej) з максимальним значенням Ed ∩ Ej.
7. Доповнюємо граф Gd (Vd, Ed) множиною вершин Vj і множиною ребер Ej .
8. При виконанні умови (11) переходимо до пункту 11.
9. Між кінцевими вершинами перевантаженої ділянки шляху формуємо додатковий шлях.
10. Множина ребер Ed доповнюється новими ребрами.
11. Граф перевіряється на надмірність, здійснюється оптимізація структури графа.
12. ST0 = ST0 \ STj(Vj,Ej).
13. Якщо ST0 ≠∅, то переходимо до пункту 5.
14. Кінець.

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

Формування локальних віртуальних підмереж здійснюється на основі ряду критеріїв, серед яких одним з основних є відношення інтенсивності зовнішніх потоків до інтенсивності внутрішніх потоків. Як обмеження тут можуть виступати обмеження на діаметр графа і завантаження каналів передачі даних. Запропоновано й обґрунтований  алгоритм формування локальних віртуальних підмереж з  урахуванням відносини kλ інтенсивності λi+ внутрішніх потоків до інтенсивності λi-  зовнішніх потоків підграфа Gi(Vi, Ei). Як обмеження виступають обмеження на діаметр підграфа і завантаження каналів передачі даних. Основною операцією алгоритму є послідовне формування  множин Vi з kλ > 1.  Як перший елемент множини  V1 вибирається вершина vi  з максимальною інтенсивністю потоків. Потім з  вершин множини V\V1  вибирається вершина vj з максимальним значенням kλ щодо множини {V1, vi }.         На другому  і наступному кроках аналогічно здійснюється включення чергових вершин vi ∈ V\V1 у множину V1. Процес формування множини V1 закінчується при відсутності вершин vi ∈ V\V1  зі значенням kλ > 1.

В четвертому розділі на прикладі технології АТМ розглядаються питання організації і підтримки віртуальних каналів. На основі аналізу відомих способів організації передачі даних, а також, з огляду на характерні особливості мобільних корпоративних мереж, розроблено адаптивний алгоритм маршрутизації. Формування шляху здійснюється в рамках віртуальної підмережі з мінімальною кількістю ребер, що сформована з урахуванням можливого переміщення мобільного абонента. Це дозволяє скоротити час і підвищити ефективність процедури маршрутизації. Формування дерева доставки STk(Vk,Ek) в рамках віртуальної підмережі здійснюється аналогічно алгоритму1, з урахуванням імовірності перебування мобільного абонента у тій чи іншій локальний підмережі. Це дозволяє сформувати шлях передачі інформації, з мінімальною часовою складністю його реконфігурації. На рис. 1 і рис. 2 наведені значення часової складності ремаршрутизації при різних способах формування дерева доставки інформації і різних мережевих топологіях. В якості початкової структури обрана повнозв'язана структура. Кожна нова структура формується з попередньої, шляхом вилучення окремих ребер у попередній структурі.

На рис. 1 представлена залежність часової складності при формуванні дерева доставки з трьома рівнями. На рис. 2 – для дерева з 10 рівнями. Як випливає з рис. 1 і рис. 2, зі збільшенням числа рівнів ефективність запропонованого способу перевищує ефективність способу, заснованого на алгоритмі Дейкстри.

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

де: tp,g - час передачі комірок по ребру ep,g на шляху LZ (vk,vm) переміщення мобільного абонента між зовнішніми маршрутизаторами і vm суміжних локальних підмереж. Оптимізація маршруту, а також виключення його зациклення здійснюється шляхом реконфігурації (переключення) раніше доданих ділянок шляху. На основі аналізу відомих схем переключення, в роботі пропонується схема адаптивного переключення, що є модифікацією схеми безрозривного переключення на базі аналізу переміщення мобільного абонента. На основі запропонованого способу ремаршрутизації розроблено адаптивний алгоритм маршрутизації. Проведено дослідження ефективності обраних рішень у залежності від мобільності мобільного абонента, їх концентрації й інтенсивності трафіка. Для оцінки ефективності використовувався коефіцієнт ефективності, що дорівнює відношенню числа передач пакетів даних до загального числа передач: KЭФ=VД/V0. Для оцінки завантаження використовувався коефіцієнт завантаження, що дорівнює відношенню загального числа передач до сумарної пропускної спроможності мережі: КЗ=V0/W.

Залежності ефективності алгоритму і завантаження мережі від швидкості руху мобільного абонента приведені відповідно на рис.3 і 4 .