Алгоритмическое обеспечение для маршрутизации с поддержкой качества обслуживания данных в беспроводных вычислительных сетях

• Автор: Поженко, Михаил Александрович
• Шифр специальности: 05.13.11
• Научная степень: Кандидатская
• Год защиты: 2003
• Место защиты: Томск
• Количество страниц: 136 с.

ОГЛАВЛЕНИЕ
ВВЕДЕНИЕ
ГЛАВА 1. ПРОБЛЕМЫ РАЗРАБОТКИ АЛГОРИТМИЧЕСКОГО ОБЕСПЕЧЕНИЯ ДЛЯ МАРШРУТИЗАЦИИ БЕСПРОВОДНЫХ ВЫЧИСЛИТЕЛЬНЫХ СЕТЕЙ.
1.1. Беспроводные вычислительные сети. Типы беспроводных локальных вычислительных сетей

1.2. Недостатки традиционных и актуальность разработки новых

алгоритмов маршрутизации БЛВС.

1.3. Анализ специализированных алгоритмов маршрутизации МЭБЛВС

1.3.1. Проактивная или табличная маршрутизация.

1.3.2. Иерархическая маршрутизация.

1.3.3. Реактивная маршрутизация или маршрутизация по требованию

1.4. Актуальность проблемы обеспечения качества обслуживания данных в сетях МЭБЛВС

1.5. Программные средства для моделирования беспроводных
вычислительных сетей
1.6. Цель и задачи исследования.
1.7. Основные результаты и выводы по главе
ГЛАВА 2. ЗАДАЧИ МНОГОКРИТЕРИАЛЬНОЙ МАРШРУТИЗАЦИИ В СЕТЯХ МЭБЛВС.
2.1. Построение графовой модели сети
2.2. Задача поиска маршрута с множественными ограничениями.
2.3. Алгоритм поиска маршрута с двумя ограничениями.
2.4. Алгоритм поиска маршрута с тремя ограничениями.
2.5. Алгоритм поиска маршрута с множественными ограничениями при изменяющемся состоянии сети.
2.6. Анализ эффективности разработанных алгоритмов
2.6.1. Анализ алгоритмов маршрутизации при использовании возможности
поиска альтернативного маршрута
2.7. Основные результаты и выводы по главе.
ГЛАВА 3. РЕАЛИЗАЦИЯ АЛГОРИТМОВ МАРШРУТИЗАЦИИ С ПОДДЕРЖКОЙ КАЧЕСТВА ОБСЛУЖИВАНИЯ В СЕТЯХ МЭБЛВС
3.1. Приближенная сетевая модель МЭБЛВС
3.2. Алгоритм КОмаршрутизации от источника
3.3. Алгоритм КОмаршрутизации от адресата.
3.4. Адаптация алгоритмов к изменяющейся топологии сети МЭБЛВС
3.4.1. Обнаружение нарушенных маршрутов.
3.4.2. По иск альтернат ивного маршрута.
3.4.3. Восстановление нарушенного маршрута
3.5. Модификация предложенных алгоритмов.
3.5.1. Локальная рассылка сообщений маршрутизации.
3.5.2. Сбор информации о расстояниях.
3.6. Анализ разработанных алгоритмов
3.7. Основные результаты и выводы по главе
ГЛАВА 4. ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ ДЛЯ ИССЛЕДОВАНИЯ МОДЕЛЕЙ СЕТЕЙ МЭБЛВС.
4.1. Подсистема редактирования модели.
4.2. Подсистема прогона модели
4.3. Подсистема обработки результатов.
4.4. Апробация разработанного программного пакета.
4.5. Основные результаты и выводы по главе
ЗАКЛЮЧЕНИЕ
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ


Описываются механизмы обнаружения и поиска альтернативных маршрутов при нарушении основного. Приводится разработанный алгоритм восстановления нарушенных маршрутов без полного перестроения уже существующих. Предлагаются способы модификации разработанных алгоритмов с целью уменьшения количества служебных сообщений, генерируемых алгоритмами. Приводится анализ разработанных алгоритмов и сравнение разработанных алгоритмов с учетом внесенных изменений. В четвертой главе рассматривается создание программных средств для исследования моделей сетей МЭБЛВС. Описывается структура разработанного программного пакета для исследова-• ния моделей сетей МЭБЛВС. Приводится описание разработанных подсистем редактирования модели, прогона модели и подсистемы работы с результатами прогона. Описывается апробация разработанного программного пакета, и приводятся примеры его применения. Указывается, что алгоритмические и программные средства внедрены в ООО «Стек» и ООО «Томская транковая компания». Приближенная сетевая модель, позволяющая учитывать особенности сетей МЭБЛВС и в том числе, динамически изменяющуюся топологию и характеристики сети. Разработанные алгоритмы многокритериальной маршрутизации, находящие маршруты с накладываемыми двумя и тремя ограничениями на искомый маршрут. Разработанный алгоритм, позволяющий находить маршрут с двумя ограничениями при изменяющемся состоянии сети. Разработанные алгоритмы маршрутизации сети МЭБЛВС, инициализируемые либо источником, либо адресатом, с учетом их последующих модификаций и адаптации. Результаты анализа алгоритмов маршрутизации с помощью исследования на моделях сетей МЭБЛВС в разработанном программном пакете, позволяющие делать выводы об эффективности применения разработанных алгоритмов для маршрутизации сетей МЭБЛВС. Практическая ценность и реализация результатов работы. Практически значимыми являются созданные модели, методы, алгоритмы и программные средства, позволяющие исследовать модели сетей МЭБЛВС. Программные средства функционируют на компьютерах типа IBM PC под управлением операционной системы Windows . Объем исходного кода системы составляет более строк кода на языке Object Pascal. Предложенные алгоритмы были внедрены в программное обеспечение для беспроводных систем, разрабатываемое в «Darim Vision Co. Ltd», что подтверждается соответствующим актом о внедрении. Созданные программные средства и алгоритмическое обеспечение используются в работе сетевых департаментов ООО «Стек» и ООО «Томская гранковая компания». Внедрение подтверждено соответствующими документами. Постановка задач исследования и разработка графовой модели сети МЭБЛВС выполнена автором совместно с В. К. Погребным. Формальное описание постановки задач маршрутизации с множественными ограничениями и описание алгоритмов для их решения с различными условиями выполнено лично автором. Приближенная сетевая модель и алгоритму для маршрутизации сети МЭБЛВС разработаны лично автором. Постановка задач исследования эффективности предложенных алгоритмов и результаты исследования получены автором. МЭБЛВС выполнена лично автором. Разработанные алгоритмы решения задач маршрутизации с множественными ограничениями позволяют находить маршрут с обеспечением качества обслуживания данных быстрее, чем алгоритмы, использующие последовательный поиск по каждому ограничению на маршрут (алгоритм ЗМ). Созданная приближенная сетевая модель позволяет адекватно описывать процессы изменения топологии, происходящие в сетях МЭБЛВС. Разработанные алгоритмы маршрутизации адаптированы к применению в сетях МЭБЛВС и позволяют находить маршрут с поддержкой качества обслуживания без дополнительных трат сетевых ресурсов. Автор выражает глубокую благодарность научному руководителю доктору технических наук, профессору В. К. Погребному за помощь в подготовке диссертационной работы, ценные замечания и советы. Автор также благодарит за плодотворные дискуссии доцентов Томского политехнического университета, кандидатов технических наук A. B. Кудинова, А. Ю. Демина и И. А. Ботыгина.