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

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

МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ

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

УДК 004.04 (043.3)

МЕТОД динамічної маршрутизації

з підтримкою якості обслуговування

в мобільних комп'ютерних мережах

05.13.13 - Обчислювальні машини, системи та мережі

Автореферат

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

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

Клименко Ірина Анатоліївна

Київ - 2006

АНОТАЦІЇ

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

Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 05.13.13 - Обчислювальні машини, системи та мережі. - Національний авіаційний університет МОН України, Київ, 2006.

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

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

Клименко И.А. Метод динамической маршрутизации с поддержкой качества обслуживания в мобильных компьютерных сетях. - Рукопись.

Диссертация на соискание ученой степени кандидата технических наук по специальности 05.13.13 - Вычислительные машины, системы и сети. - Национальный авиационный университет МОН Украины, Киев, 2006.

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

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

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

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

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

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

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

Klymenko I.A. The method of dynamic routing in the mobile computing networks with the current quality of service support. - Manuscript.

Dissertation for the scientific degree of the Candidate of Technical Sciences on specialty 05.13.13 - Computers, systems and networks. - National aviation university Ministry of Education and Science of Ukraine, Kyiv, 2006.

The aim of the dissertation is efficiency increase of routing in wireless network with providing the required level of quality of service in different types of traffic. The method of dynamic routing with quality of service support was suggested to accomplish the task of dissertation. The algorithm of dynamic clusters structure formation was developed for creation of hierarchical structure of the network. The hierarchical structure allows using the most effective algorithm of routing on each level, while the dynamic clusters reconfiguration increases the routing effectiveness by decreasing the routing time and of managing traffic size. The required level of quality of service is being obtained by increasing the virtual connection stability and using of complex routing metric, which is the battery of main parameters of quality of service in specified type of traffic.

Key words: mobile computing network, the method of dynamic routing, hierarchical routing, virtual connect, quality of service, QoS, multiprotocol switchboard.

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

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

Науковий керівник: доктор технічних наук, професор, заслужений винахідник України Жуков Ігор Анатолійович, Національний авіаційний університет МОН України, директор Інституту комп'ютерних технологій.

Офіційні опоненти: доктор технічних наук, доцент Дичка Іван Андрійович, Національний технічний університет України “Київський політехнічний інститут” МОН України, професор кафедри спеціалізованих комп'ютерних систем;

кандидат технічних наук, старший науковий співробітник Алішов Надір Ісмаіл-огли, Інститут кібернетики ім. В.М. Глушкова НАН України, провідний науковий співробітник.

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

Захист відбудеться " 26 " 04 2006 р. о 14 годині на засіданні спеціалізованої вченої ради Д 26.062.07 Національного авіаційного університету за адресою: 03058, м. Київ, проспект Космонавта Комарова 1.

З дисертацією можна ознайомитись в бібліотеці Національного авіаційного університету за адресою 03058, м. Київ, проспект Космонавта Комарова 1.

Автореферат розісланий " 24 " 032006 р.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Особистий внесок здобувача. Всі результати, що складають основний зміст дисертаційної роботи, отримані автором самостійно. По результатам наукових досліджень опублікована одна одноосібна праця [1]. В роботах, опублікованих у співавторстві, здобувачеві належить: [2] - алгоритм формування віртуальних каналів; [3] - алгоритм адаптивної маршрутизації; [4] - дослідження відомих методів маршрутизації з забезпеченням необхідного рівня якості обслуговування і визначення необхідності розробки нового адаптивного підходу до рішення задачі маршрутизації в мобільних комп'ютерних мережах; [5] - рішення задачі динамічного розподілення потоків трафіка в мобільних мережах.

Апробація результатів дисертації. Основні результати дисертаційної роботи доповідались та обговорювались на наукових семінарах кафедри обчислювальної техніки Інституту комп'ютерних технологій Національного авіаційного університету (м. Київ, Україна, 2004-2005 р.р.), на міжнародних та регіональних конференціях, а саме: Міжнародній конференції “Інформаційні технології в управлінні енергетичними системами ІТУЕС-2005” (м. Київ, Україна, 2005 р.), ІІ Міжнародній науково-практичній конференції “Науковий потенціал світу - 2005” (м. Дніпропетровськ, Україна, 2005 р.), Науково-практичній конференції молодих вчених та аспірантів “Інтегровані інформаційні технології та системи ІІТС -2005” (м. Київ, Україна, 2005 р.).

Публікації. Основні результати дисертаційної роботи опубліковані в 8 наукових працях, серед яких 5 - у фахових виданнях [1-5] і 3 - у матеріалах конференцій [6-8].

Структура та обсяг дисертації. Дисертаційна робота, що викладена на 216 сторінках друкованого тексту, складається з вступу, чотирьох розділів і висновків, викладених на 129 сторінках основного тексту, списку використаної літератури з 131 найменування і додатків. Дисертаційна робота містить 27 рисунків, 16 таблиць, 2 додатки, 3 акти про впровадження.

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

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

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

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

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

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

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

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

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

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

Для визначення метрики маршрутизації представимо мобільну мережу у вигляді орієнтованого графа G(V, E), де множина вершин графа V = {v₁, …, v_|V|} - надає мобільні вузли мережі, множина ребер графа E = {e₁, …, e_|E|} - надає канали зв'язку, що зв'язують дві суміжні вершини v та u, де (v, u)V. Кожному ребру e(v, u), де еЕ графа G ставиться у відповідність деяке значення його ваги, w_v,u= (b, d, л), де: b - пропускна здатність каналу; d - затримка передачі інформації; л - стійкість каналу.

Значення затримки для стану ребра e(i, j)E, де {i, j}V, визначається як сума затримки у буфері вузла (t_i) і часу розповсюдження даних по каналу (t_{e(i, j)}). Для каналу e(i, j) значення затримки d(i, j) дорівнює: d(i, j) = t _i + t _{(i, j)}

Тоді для любого маршруту P(v, u)G між двома вузлами v та u, де {v, u}V, метрика затримки передачі інформації D(н, u) дорівнює

.(1)

Якщо b(i, j) - пропускна здатність каналу e(i, j)E, де {i, j}V, то для любого маршруту P(v, u)G метрика пропускної здатності B(v, u) буде дорівнювати мінімальній пропускної здатності каналів на шляху між двома вузлами v та u, де {v, u}V.

. (2)

Стійкість л(i, j) каналу між двома суміжними вершинами i та j, де {i, j}V, дорівнює , де p(i, j) - імовірність видалення ребра e(i, j)E із графа G. Стійкість л(н, u) маршруту P(н, u) між двома вузлами v та u, де {v, u}V, являє собою функцію від стійкості усіх каналів даного маршруту.

.

Тоді метрика стійкості маршруту P(н, u)G між двома вузлами v та u, де {v, u}V, визначається наступним чином:

. (3)

Складена метрика маршрутизації визначається аналогічно композитарній метриці, що використовується у протоколі маршрутизації IGRP компанії Cisco. Складена метрика М(н, u), яка запропонована для пошуку оптимального маршруту P(н, u) | PG між двома вузлами v та u, де {v, u}V, визначається наступним чином:

,

де D(н, u) - час затримки передачі даних, B(н, u) -пропускна здатність, л(н, u) - стійкість, L(н, u) - завантаження маршруту. Складові метрики маршрутизації М(н, u) визначаються за виразами (1-3). Коефіцієнти K враховують ступінь впливу характеристик каналів на складену метрику маршрутизації, де k₁ - ваговий коефіцієнт пропускної здатності; k₂ - ваговий коефіцієнт завантаження; k₃ - ваговий коефіцієнт затримки; k₄ та k₅ - відповідно, первинний і вторинний вагові коефіцієнти стійкості маршруту.

Вхідними даними для побудови математичної моделі є характеристики каналів зв'язку, та топологія мережі. Топологія мережі задана у вигляді орієнтованого графа G(V, E). Де V={v₁, …, v_|V|} - множина вершин графа, що відповідають |V| вузлам мережі, E={e₁, …, e_|E|} - множина ребер, що відповідають |E| каналам зв'язку, причому парі вершин u і v, де {u, v} V, що мають між собою зв'язок, відповідає пара ребер: e(u, v) і e(v, u), де eE. Граф топології мережі зображений за допомогою матриці зв'язності H_G. Розмірність матриці дорівнює |V| |V|.

,

де і .

Кожному ребру e(v, u)E, де {v, u}V, графа G ставиться у відповідність деяке значення його ваги w_v,u={b, л, l, d, m}. Множина w_v,u визначає значення характеристик каналу зв'язку, де b - пропускна здатність, л - стійкість, l - завантаження, d - затримка передачі, m -максимальний розмір пакету. Для кожного значення характеристики каналу з множини w_v,u формується граф Gi, де iw_v,u, який зображується за допомогою матриці зв'язності W_Gi. Розмірність матриці W_Gi відповідає розмірності матриці H_G.

Розглянутий граф Gb(Vb, Eb) - множини вершин і ребер цього графа відповідають множинам V і E графа топології мережі G. Кожному ребру e(v, u)Eb, де {v, u}Vb, графа Gb ставиться у відповідність значення його ваги , що дорівнює значенню пропускної здатності цього каналу. Такий граф зображується матрицею зв'язності , елементами якої є значення пропускної здатності відповідних каналів,

де

Інші графи Gi | i w_v,u характеристик каналів аналогічно зображуються за допомогою матриць зв'язності , , та , елементами яких є значення стійкості, завантаження, затримки і максимального розміру пакета відповідно.

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

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

,

де - час, що відповідає одному такту роботи системи; - об'єм службової інформації, переданої за один такт по кожному окремому каналу.

Множина відповідає кожному елементу множини Е графа топології мережі, і відображає інформацію, що передана від вузла v до вузла u. Ця множина має наступну структуру:



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

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

для і , де .

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

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

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

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

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

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

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

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

, (4)

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

На основі аналізу відомих комутаторів і маршрутизаторів запропоновані структура (рис.1) і алгоритм функціонування багатопротокольного комутатора.

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

На рис. 2 наведений граф переходів, із указаними імовірностями P_i,j переходів між вершинами i та j. Позначення вершин наведеного графу відповідають наступним операціям, що виконуються у відповідному блоці багатопротокольного комутатора: 1 - затримка у вихідному буфері (BI), 2 - аналіз адресу вхідного пакету (S_w), 3 - звернення до таблиці внутрішньої маршрутизації (АК), 4 - процедура зовнішньої/внутрішньої маршрутизації (R), 5 - запис маршруту у таблицю внутрішньої маршрутизації (AK), 6 - звернення до таблиці зовнішньої маршрутизації (BA), 7 - запис маршруту у таблицю зовнішньої маршрутизації (BA), 8 - формування адресу вихідного пакету (S_w), 9 - затримка у вихідному буфері (BE).

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

, (5)

де - символ Кронекєра.

Граф переходів не вміщує циклів, тому у початковому стані процес знаходиться тільки один раз, тобто n₁=1. Відповідно до чого вираз (5) приймає наступний вигляд:

. (6)

За виразом (6) отримано:

;	;
;	;
;	;
;	.
;

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

,

де - час обслуговування пакету j блоком комутатора.

У четвертому розділі розглянуті питання вибору розміру та структури кластерів та представлений алгоритм формування динамічної структури кластерів.

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

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

.

Із збільшенням кількості реконфігурацій кластера, об'єм службового трафіка збільшується за нелінійним законом, за рахунок чого різко падає ефективність передачі даних. Відповідно до чого, для зменшення об'єму службового трафіка у кластері частота реконфігурацій на визначеному проміжку часу ДТ і кількість вузлів кластера повинні наближатися до мінімуму: F_r min, N₀ min.

Таким чином, оптимальный размір кластеру можна охарактеризувати за допомогою коефіцієнта:

, де .

По-друге, об'єм службового трафіка залежить від діаметра кластера D і ступеню зв'язності вузлів кластера S:

.

Досліджено характер впливу ступеня зв'язності вузлів мережі на об'єм службового трафіка. У мережі, що задана регулярним графом G(V,E), де V={v₁,…, v_|V|} - множина вершин графа, що відповідають |V| вузлам мережі, E={e₁,…, e_|E|} - множина дуг, що відповідають |E| каналам зв'язку, проведені розрахунки кількості службових повідомлень, що розповсюджуються при зміні стану вузла лавинним алгоритмом маршрутизації. Для мереж зі ступенями зв'язності вузлів, що дорівнюють S = 3, 4, 6 і 8 кількість службових повідомлень відповідно дорівнює:

,

,

,

,

де r - радіус мережі, S - ступінь зв'язності вузлів.

Середня кількість службових повідомлень Vсл_v, розповсюджених вузлом v | vV графу G(V, E), лавинним алгоритмом маршрутизації дорівнює:

.

У табл. 1 наведена середня кількість службових повідомлень, розповсюджених одним вузлом в мережі, в залежності від ступеню зв'язності вузлів кластера.

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

Для формування ієрархічної структури мережі запропонований алгоритм формування динамічної структури кластерів. Даний алгоритм передбачає вибір початкової вершини, у якості якої обирається вершина з максимальним або мінімальним ступенем зв'язності вузлів, в залежності від вхідних параметрів алгоритму. У якості вхідних розглядаються наступні параметри: ступінь зв'язності початкової вершини нового кластера (Head_NC); ступінь зв'язності вузла при наявності декількох вузлів з кількістю зв'язків що дорівнює ступеню зв'язності вершини кластера (Station_NC); максимальний діаметр кластера (Dmax); максимальна кількість вузлів кластера (Nmax).

Наведемо алгоритм формування динамічної структури кластерів:

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

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

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

Основні висновки та результати роботи

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

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

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

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

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

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

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

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

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

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

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

1. Клименко И.А. Способ динамической маршрутизации с поддержкой требуемого уровня качества обслуживания в мобильных сетях без фиксированной инфраструктуры // Проблеми інформатизації та управління: Зб. наук. пр. - К.: НАУ, 2005. - Вип. 15. - С. 102-112.

2. Клименко И.А., Аль Рабабах Мохаммед Абдель-Кадер, Мухаммед Ель Амин Бабикер. Организация виртуальных каналов в мобильной сети Интернет // Вісник Національного техн. ун-ту України “КПИ”: Інформатика, управління та обчислювальна техніка. - К.: ТОВ “ВЕК+”, 2004. - Вип. 42. - С. 84-93.

3. Клименко И.А., Хуссейн Ахмад Аль-Фади Аль-Офешат, Аль Рабабах Мохаммед Абдель-Кадер Способ и средства адаптивной маршрутизации в мобильных сетях // Проблеми інформатизації та управління: Зб. наук. пр. -К.: НАУ, 2005. - Вип. 12. - C. 74-75.

4. Жуков И.А., Клименко И.А. Обеспечение заданного уровня качества обслуживания в объединенных сетях // Проблеми інформатизації та управління: Зб. наук. пр. - К.: НАУ, 2005. - Вип. 13. - C.5-14.

5. Жуков И.А., Клименко И.А., Аленин О.И. Организация многопутевой маршрутизации средствами MPLS // Проблеми інформатизації та управління: Зб. наук. пр. - К.: НАУ, 2005. - Вип. 14. - С. 59-70.

6. Клименко И.А., Жуков И.А. Организация многопутевой маршрутизации средствами MPLS // Тр. II Міжнар. наук.-практичної конф. “Науковий потенціал світу - 2005”. - Дніпропетровськ: Наука і освіта, 2005. - Т. 10.- С. 40-42.

7. Жуков И.А., Клименко И.А. Адаптивная маршрутизация в объединенных компьютерных сетях управления энергетическими процессами // Тр. Міжнар. конф. “Інформаційні технології управління енергетичними системами” (ІТУЕС-2005). - Київ: ІТУЕС, 2005. - С. 44-45.

8. Клименко И.А. Способ адаптивной маршрутизации с учетом параметров качества обслуживания в мобильных сетях Ad Hoc // Тр. Наук.-практичної конф. молодих вчених та аспірантів “Інтегровані інформаційні технології та системи” (ІІТС-2005). - Київ: НАУ, 2005. - С. 78-80.

Размещено на Allbest.ru

...