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

В настоящее время резко возрос интерес к беспроводным вычислительным сетям, в которых в качестве среды передачи используются радио или инфракрасные каналы. Во многих отраслях народного хозяйства наблюдается увеличение спроса на полностью мобильные портативные компьютеры, которые позволяли бы без наличия проводных соединений обмениваться информацией друг с другом и получать доступ к глобальной сети Internet. Так по данным агентства Gartner Dataquest [71] только для Европы прогнозируемый рост общего числа регулярных пользователей беспроводных вычислительных сетей вырастет к 2007 г. до 10 950 000 человек.

Одним из наиболее актуальных и динамично развивающихся сегодня направлений в беспроводных вычислительных сетях является создание мобильных эпизодических беспроводных локальных вычислительных сетей (МЭБЛВС). Повышенный интерес к ним вызван, прежде всего, такими свойствами сетей МЭБЛВС, как простота организации и возможность свободного перемещения беспроводных узлов. Сеть МЭБЛВС может быть создана в считанные минуты, и включать в себя десятки, а то и сотни беспроводных узлов. Мобильные эпизодические беспроводные сети могут использоваться при проведении встреч или конференций, операций поиска и спасения людей, обмена информацией в критических условиях, например при стихийных бедствиях или при проведении военных операций [57,80,86,106].

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

В процессе функционирования современных приложений, на алгоритмы маршрутизации ложится задача поиска таких маршрутов, которые удовлетворяют требуемым приложениями величинам пропускной способности, задержки и потерь пакетов. Данная задача в литературе описывается как задача качества обслуживания данных (QoS) [17,20,22,25].

Несмотря на достаточно большое количество существующих протоколов маршрутизации для МЭБЛВС, описанных в литературе [62,82,83,98,104,115,118], необходимо отметить, что нахождение маршрута в них сводится лишь к отысканию кратчайшего пути с обеспечением доставки данных только «по возможности». При этом передача данных приложений, чувствительных к величинам пропускной способности, задержки и потерь пакетов, становится практически невозможной. Применение же в сети МЭБЛВС традиционных протоколов маршрутизации, разработанных для проводных сетей [20,89,90], не эффективно, поскольку данный класс протоколов не предназначен для работы с изменяющейся топологией сети.

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

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

Для реализации поставленной цели необходимо последовательное решение следующих задач:

1. Создание и формализованное описание модели сети МЭБЛВС с обеспечением качества обслуживания и модели сети МЭБЛВС с учетом изменяющихся характеристик и топологии.

2. Решение задач маршрутизации с множественными ограничениями на искомый маршрут.

3. Разработка алгоритмического обеспечения для маршрутизации с поддержкой качества обслуживания сетей МЭБЛВС.

4. Разработка программного пакета для исследования моделей сетей МЭБЛВС, позволяющего с помощью имитационного моделирования оценивать эффективность новых и существующих алгоритмов маршрутизации сетей МЭБЛВС.

5. Апробация разработанных алгоритмов в функционирующих сетях МЭБЛВС.

Методы исследований. В работе использованы методы теории множеств, теории алгоритмов, теории графов и комбинаторики и теории моделирования.

Апробация работы. Основные результаты работы докладывались и обсуждались на следующих конференциях: Всероссийская научно-практическая конференция «Российская школа и интернет» (Санкт-Петербург, 2001), Вторая Международная научно-практическая конференция «Моделирование. Теория, методы и средства» (Новочеркасск, 2002), Третья научно-практическая конференция «Современные средства и системы автоматизации» (Томск, 2002), Четвертая научно-практическая конференция «Современные средства и системы автоматизации» в рамках Всероссийского конгресса «Системы и средства автоматизации управления» (Томск, 2003), The IEEE-Siberian conference on control and communications «SIBCON-2003» (Томск, 2003).

По результатам работы имеется 10 публикаций, в том числе 7 статей.

Кратко изложим основное содержание работы.

В первой главе описываются типы беспроводных вычислительных сетей и особенности их функционирования. Формулируются проблемы разработки алгоритмического обеспечения маршрутизации сетей МЭБЛВС. Обосновывается неэффективность применения традиционных протоколов маршрутизации в сетях МЭБЛВС.

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

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

На основе результатов проведенного анализа существующего алгоритмического обеспечения для маршрутизации сетей МЭБЛВС, а также программного обеспечения для исследования моделей сетей МЭБЛВС, формулируются цель и задачи диссертационной работы.

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

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

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

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

Приводится анализ эффективности алгоритма поиска маршрута с тремя ограничениями, на основе сравнения разработанного алгоритма с существующим алгоритмом, используемыми в современных сетях МЭБЛВС. Делаются выводы о зависимости степени эффективности алгоритмов от размеров сети. Приводится анализ эффективности алгоритмов с возможностью поиска альтернативного маршрута.

В третьей главе рассматривается реализация алгоритмов маршрутизации в сети МЭБЛВС. Предлагается приближенная сетевая модель МЭБЛВС, описываются основные предположения, относимые к модели и маршрутная архитектура модели.

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

Предлагаются способы адаптации разработанных алгоритмов к изменяющейся топологии сети МЭБЛВС. Описываются механизмы обнаружения и поиска альтернативных маршрутов при нарушении основного. Приводится разработанный алгоритм восстановления нарушенных маршрутов без полного перестроения уже существующих.

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

Приводится анализ разработанных алгоритмов и сравнение разработанных алгоритмов с учетом внесенных изменений.

В четвертой главе рассматривается создание программных средств для исследования моделей сетей МЭБЛВС.

Описывается структура разработанного программного пакета для исследования моделей сетей МЭБЛВС. Приводится описание разработанных подсистем редактирования модели, прогона модели и подсистемы работы с результатами прогона. Описывается апробация разработанного программного пакета, и приводятся примеры его применения.

Указывается, что алгоритмические и программные средства внедрены в ООО «Стек» и ООО «Томская транковая компания».

Научную новизну полученных в работе результатов определяют:

1. Приближенная сетевая модель, позволяющая учитывать особенности сетей МЭБЛВС и в том числе, динамически изменяющуюся топологию и характеристики сети.

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

3. Разработанные алгоритмы маршрутизации сети МЭБЛВС, инициализируемые либо источником, либо адресатом, с учетом их последующих модификаций и адаптации.

4. Результаты анализа алгоритмов маршрутизации с помощью исследования на моделях сетей МЭБЛВС в разработанном программном пакете, позволяющие делать выводы об эффективности применения разработанных алгоритмов для маршрутизации сетей МЭБЛВС.

Практическая ценность и реализация результатов работы. Практически значимыми являются созданные модели, методы, алгоритмы и программные средства, позволяющие исследовать модели сетей МЭБЛВС. Программные средства функционируют на компьютерах типа IBM PC под управлением операционной системы Windows 2000. Объем исходного кода системы составляет более 8000 строк кода на языке Object Pascal.

Предложенные алгоритмы были внедрены в программное обеспечение для беспроводных систем, разрабатываемое в «Darim Vision Co. Ltd», что подтверждается соответствующим актом о внедрении.

Созданные программные средства и алгоритмическое обеспечение используются в работе сетевых департаментов ООО «Стек» и ООО «Томская транковая компания». Внедрение подтверждено соответствующими документами.

Личный вклад:

1. Постановка задач исследования и разработка графовой модели сети щ.

МЭБЛВС выполнена автором совместно с В. К. Погребным.

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

3. Приближенная сетевая модель и алгоритмьц для маршрутизации сети МЭБЛВС разработаны лично автором. Постановка задач исследования эффективности предложенных алгоритмов и результаты исследования получены автором.

4. Разработка программного пакета для исследования моделей сетей МЭБЛВС выполнена лично автором.

Основные положения, выносимые на защиту:

1. Разработанные алгоритмы решения задач маршрутизации с множественными ограничениями позволяют находить маршрут с обеспечением качества обслуживания данных быстрее, чем алгоритмы, использующие последовательный щ поиск по каждому ограничению на маршрут (алгоритм ЗМ).

2. Созданная приближенная сетевая модель позволяет адекватно описывать процессы изменения топологии, происходящие в сетях МЭБЛВС.

3. Разработанные алгоритмы маршрутизации адаптированы к применению в сетях МЭБЛВС и позволяют находить маршрут с поддержкой качества обслуживания без дополнительных трат сетевых ресурсов.

4. Программный пакет для исследования моделей сетей МЭБЛВС позволяет •" легко создавать модели при помощи визуальных компонентов и изучать работу сети с помощью имитационного моделирования.

Автор выражает глубокую благодарность научному руководителю доктору технических наук, профессору В. К. Погребному за помощь в подготовке диссертационной работы, ценные замечания и советы. Автор также благодарит за плодотворные дискуссии доцентов Томского политехнического университета, кандидатов технических наук А. В. Кудинова, А. Ю. Демина и И. А. Ботыгина.

4.5. Основные результаты и выводы по главе.

1. Приводится обоснование выбора инструментального средства для разработки программного пакета. В результате сравнения различных инструментальных средств, как оптимальный вариант для разработки программного пакета был выбран Borland Delphi.

2. Приводится описание структурного состава разработанного программного пакета и составляющих его подсистем.

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

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

5. Приводится описание подсистемы работы с результатами прогона моделей, позволяющей получать после прогона модели различные статистические отчеты.

6. Созданный программный пакет успешно апробирован на задачах исследования моделей проектируемых сетей в ООО «Стек» и ООО «Томская тран-ковая компания».

ЗАКЛЮЧЕНИЕ

.

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

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

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