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

На правах рукописи

Поженко Михаил Александрович

АЛГОРИТМИЧЕСКОЕ ОБЕСПЕЧЕНИЕ ДЛЯ МАРШРУТИЗАЦИИ С ПОДДЕРЖКОЙ КАЧЕСТВА ОБСЛУЖИВАНИЯ ДАННЫХ В БЕСПРОВОДНЫХ ВЫЧИСЛИТЕЛЬНЫХ СЕТЯХ

05.13.11 — Математическое и программное обеспечение

вычислительных машин, комплексов и компьютерных сетей

Автореферат

диссертации на соискание ученой степени кандидата технических наук

Томск — 2003

Работа выполнена в Томском политехническом университете.

Научный руководитель:

доктор технических наук, профессор В.К. Погребной

Официальные оппоненты:

доктор технических наук, профессор В.П. Бондаренко кандидат технических наук, доцент Е.А. Мирошниченко

Ведущая организация:

Новосибирский государственный технический университет, г. Новосибирск

Защита состоится 24 декабря 2003 г. в /Гч. на заседании диссертационного совета Д 212.269.06 при Томском политехническом университете по адресу: 634034, г.Томск, ул. Советская, 84, институт «Кибернетический центр» ТПУ, ауд.214.

С диссертацией можно ознакомиться в библиотеке Томского политехнического университета по адресу: 634034, г.Томск, ул. Белинского, 53.

Автореферат разослан

М.А. Сонькин

I Ы/Z

з

Общая характеристика работы

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

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

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

Основные вопросы в области маршрутизации и обеспечения функционирования беспроводных сетей освещаются в работах отечественных ученых В.М.Вишневского, А.ИЛяхова, Р.В.Павлова, А.В.Умнова, А.В.Гуреева и др., а также зарубежных M.Gerla, C.Perkins, D.Johnson, C.-K.Toh, V.D.Park, N.H.Vaidya. В результате предлагается множество способов маршрутизации, но нахождение маршрута is них сводится лишь к отысканию кратчайшего пути с обеспечением доставки данных только «по возможности» т.е. передачи пакетов без соблюдения требований качества обслуживания. При этом передача данных приложений, чувствительных к величинам пропускной способности, задержки и потерь пакетов, при нагрузках становится практически невозможной.

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

Исследования и разработки по теме проводились в соответствии с утвержденными планами НИР Кибернетического центра ТПУ в 2000-2003 гг., в рамках Государственной НТП «Инновационная деятельность высшей школы», НТП «Инновационные научно-технические проекты по приици i е i ным направлениям науки и техники» и хоздоговорным работам кафедры И ic!30',.'^^®!!^ »НАЯ

БИБЛИОТЕКА С.Петервург t/лу 03

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Содержание работы

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

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

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

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

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

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

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

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

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

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

Для построения графовой модели (рис.1) представим сеть передачи данных как взвешенный граф Ь(У,Е). Вершины графа (V) представляют собой узлы сети. Ребра графа (Е) представляют собой каналы связи, соединяющие между собой узлы (V). Ребра графа ненаправленные только в том случае, если каналы связи всегда симметричны и имеют одинаковые характеристики (пропускную способность, задержку и т.д.) в оба направления.

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

Рис.1. Графовая модель сети

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

Используемые при маршрутизации весовые функции, согласно применяемым к ним правилам композиции классифицируются следующим образом. Пусть м/р,}), будет весовой функцией для канала связи (¡, Тогда для любого пути Р= /—► у—>к—».../—»7 эта функция будет:

аддитивной, если для маршрута она рассчитывается по формуле: и'(Р) = и> £ + V 0. к)+... + *>(!. О (1Л)

мультипликативной, если

м>(Р) = у, О,Л * м> 0. к)*... * * 0, 0 (12) вогнутой, если

и>(Р) = Мт[* 0,}), п 0, к).....">(1, 0] (13)

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

Формализовано задача маршрутизации с множественными ограничениями или многокритериальной маршрутизации (МКМ), выглядит следующим образом. Пусть Я будет набором положительных вещественных чисел и / набором положительных целых чисел. Рассмотрим ориентированный граф Е), узел-

источник 5, узел-адресат /, весовые функции: м>:£-»/? и :£->/?, две константы В е Я и О е /?; задача МКМ (С1,.у, /, и;, и>2, В, О) заключается в нахождении маршрута Р от 5 к I, удовлетворяющего условиям м\{Р) > В и м>г(Р) < £>, при условии существования такого маршрута.

Весовой функцией и'¡(Р) для маршрута Р = уо -» у -> ..., —> у, , считается функция, полученная в результате следующего соотношения:

и',(/») = М/И[И'1(У1,У)] , (1.4)

а весовой функцией \м:(Р) для маршрута Р = ув -> у -» ...,-> у, , >

о-5)

1*1

и'ДР) называется весом и пг(Р) - весом маршрута Л.

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

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

Маршрут Р, удовлетворяющий условиям к-, (Р) > В н (Р) < Б, называется решением (допустимым маршрутом) для МКМ (С, 5, г, и>,, н>2, В, /)).

На рис.2 приведена укрупненная схема разработанного алгоритма нахождения пути для заданных двух ограничений.

Входными данными для алгоритма являются:

• множество вершин V графа С(У,Е)]

• множество ребер Е графа С(У,Е);

• узел-источник 5;

• узел-адресат /;

• две константы ограничения Вий.

Сначала алгоритм формирует массив пропускных способностей В[к]. Такой шаг нужен для увеличения вероятности нахождения допустимого маршрута Р. В существующих алгоритмах, при несоблюдении условия м'^Р) > В, алгоритм прекращают свою работу, и выдает как результат отсутствие

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

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

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

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

Определение маеоива

пропускных способностей

вро

Перебор значений маоаива выбор ограничения В-ВМ

Построение подграфа в ребрами удовлетворяющими условию ЬЦ>«8

Помех кратчайшего пути от источника а к адресату |в наименьшим значением с!

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

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

задержкой /и / равной,

Рис 2. Укрупненная схема алгоритма (МКМ)

т

=*•<*., 0-4)

где ge/? коэффициент, подбираемый алгоритмом, а - средняя задержка для ребра (i,j).

Таким образом, смешанную весовую функцию можно представить следующим образом,

и — d + s • т

¡.i i.J • i i i

= dIJ{l + sii-g)

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

к

U(P) = J^u(vM,vt) (1.6)

i-i

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

Описывается, что сети МЭБЛВС также характеризуются часто изменяющимися характеристиками каналов связи. Для обеспечения работы разработанных алгоритмов с учетом изменяющихся характеристик сети, предлагается использование переменных и A¿/y. Данные переменные поддерживаются в

каждом узле вместе с и dtj характеризующими, соответственно, пропускную способность и задержку. Все переменные обновляются одновременно и отражают действительное состояние канала связи. Переменные Дfoj""1** и ис-

пользуются для хранения значений Адо, и после обновления. Аналогично

используются переменные Adijcmap°' и AdijH°KK. Идентичным вышеописанному способом, добавлены переменные для обозначения предыдущего и текущего со-

j i старое i новое • i старое l новое _

стояний Oj - это utj и btj , и для Яу - это ау и ау . Значения

j новое I моет

и ау вычисляются при использовании протокола, учитывающего состояние канала связи. Значения Дбу и Д^0"4** также известны, поскольку легко вычислить разницу между предыдущим и текущим состояниями переменных ¿у и 0?у. Для расчета значений переменных Д6у и Adt] используется формула, схожая с формулой Якобсона для протокола TCP,

Дб/"*" = к ■ А+ (1-к)--bf*| (1.7)

где коэффициент к < 1 показывает, насколько быстро уничтожается информация об истории изменения переменной AbiJamv°', а значение (1 — к) - на. 1 L новое 11 новое т старое [

сколько быстро Д0у стремится к значению |0у — О^

Формула для вычисления Ad аналогична формуле 1.7,

M~ = k-AdJ^+(l-k)]du~~-d9aK~\ (1.8)

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

Ad у, без каких-либо функций распределения вероятности.

Проводится сравнение разработанного алгоритма (МКМ) с алгоритмом, ищущим маршрут последовательно по каждому ограничению. Данный подход известен как алгоритм ЗМ. Например, в случае трех ограничений, алгоритм, с учетом определенного класса обслуживания находит маршрут между двумя узлами с минимальной задержкой; если найдено больше одного маршрута, алгоритм выбирает маршрут с максимальной пропускной способностью; если и в этом случае найдено более одного маршрута, алгоритм выбирает маршрут с минимальными потерями. В настоящее время, алгоритм ЗМ наиболее популярен и позволяет осуществлять поиск маршрута с тремя ограничениями.

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

При моделировании сети из 50 узлов (рис.3) среднее суммарное значение коэффициента успешности алгоритма МКМ превосходит аналогичный показатель алгоритма ЗМ примерно на 16 процентов.

Рис.3. Сравнение алгоритмов на модели сети из 50 узлов Для выяснения зависимости коэффициента успешности от количества узлов в сети был поставлен дополнительный эксперимент. В данном эксперименте сравнивались те же алгоритмы, что и в предыдущем эксперименте, но значение коэффициента успешности усреднялось после окончания всего процесса моделирования. Тестировались сети с количеством узлов от 5 до 100 с нарастающим шагом в 5 узлов. Результат эксперимента представлен на рис.4._

0,9 0,8 0,7 0,6 0,6 0,4 0,3 0,2 0,1 0

•Е

В Алгоритм ЗМ ■Алгоритм МКМ

ч

I ГГМ111

II1.1! 111ГГ1

II 1| I; I III I I I 1)11 I I I I I 1П I I I! I III I I! I

-V*

ъ*

Количество узлов

Рис.4. Зависимость коэффициента успешности от размеров сети

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

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

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

1

0,9 & 0,8 §0.7 | 0,6 £ 0,5 -5 0,4 I 0,3 1 0.2

0,1 -0

1 6 11 16 21 26 31 36 41 46 51 56 61 66 71 76 81 86 91 96

Врмп моделирования

Рис.5. Сравнение алгоритмов ЗМ, МКМ без поиска альтернативного маршрута и МКМ с поиском альтернативного маршрута (МКМа) для модели сети из 50 узлов

На рис.5, показано, что использование МКМ с возможностью поиска альтернативного маршрута дает дополнительный выигрыш, приблизительно в 12 процентов по отношению к МКМ без использования такой возможности. Суммарно получилось, что при заданных условиях моделирования, алгоритм МКМ с использованием возможности альтернативного маршрута превосходит алгоритм ЗМ примерно на 30 процентов.

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

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

•Алгоритм ЗМ •Алгоритм МКМ -Алгоритм МКМа

I I I П 111 II I I 111 М III N 1Н I М1 I I II I I I И I I Н1 1 I I II I I II I II II I

I 1 I 1 II I I I М I I I II I I 11

ГП

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

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

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

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

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

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

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

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

Предлагаются следующие способы адаптации разработанных алгоритмов к изменяющейся топологии сети МЭБЛВС. Для быстрого нахождения нарушенных маршрутов применяется следующая схема маршрутизации. Если узел / не равный узлу-адресату с помощью протокола, находящего соседние узлы, обнаруживает, что его узел-последователь долгое время не отвечает, /' делает вывод, что маршрут Р нарушен на участке от него до его последователя. Предполагается, что каждый узел / поддерживает таблицу подключений, которая содержит запись для каждого подключения, проходящего через данный узел. Кроме того, в записях таблицы подключений хранится информация об узле-источнике, узле-адресате, зарезервированных ресурсах и другая полезная информация относительно подключения. Когда узел / обнаруживает, что соседний узел у больше не существует, следовательно, канал (У,/) нарушен, узел помечает в таблице, что все подключения использующие канал также нарушены.

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

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

Для уменьшения избыточности сообщений маршрутизации используются следующие способы модификации алгоритмов (рис.6). Сначала удаляются ненужные сообщения, посылаемые обратно отправителю, и используется конкретизация получателей сообщений маршрутизации, называемая локальной групповой рассылкой. Локальная групповая рассылка, позволяет определить как получателей подмножество соседних узлов. Набор получателей выражается, как Ян , в

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

(а) (б)

Рис.6. Уменьшение количества сообщений маршрутизации

Предлагается также использовать сообщения маршрутизации, рассылаемые по сети в различных целях, для сбора полезной информации. Так, каждое сообщение маршрутизации дополнительно может обладать полем, сохраняющим число узлов, пройденных сообщением. Каждый узел / поддерживает таблицу расстояний, состоящую из пар (j,dгде dt j - аппроксимация расстояния между узлами i и j. При поступлении в узел-источник s запроса на подключение к узлу-адресату t, узел s ищет в таблице расстояний пару (t, d^. При существовании

такой пары, узел s определяет значение поля TTL (Time То Live - время жизни) в сообщениях маршрутизации.

В результате применения данных модификаций, для примера на рис.6, число рассылаемых сообщений сводится с 57 до 9, а количество узлов-получателей (выделенных серым цветом) уменьшается до 10.

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

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

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

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

Описывается апробация разработанного программного пакета, и приводятся примеры его применения.

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

В заключении приведены основные выводы и результаты диссертационной работы.

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

Основные результаты работы

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

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

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

3. Сформулированы задачи маршрутизации с множественными ограничениями и описаны правила композиции различных видов ограничений на маршрут.

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

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

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

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

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

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

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

Основные публикации по теме диссертации

1. Pozhenko М.А. Designing of mobile wireless networks with use of specific algorithms of routing. //Proceedings of the International Conference Interactive systems: The problems of human-computer interaction, Ulyanovsk — 2003 — P.99-101.

Поженко M.A. Разработка мобильных беспроводных сетей с использованием специфических алгоритмов маршрутизации. // Материалы Международной конференции «Проблемы человеко-компьютерного взаимодействия», Ульяновск— 2003 — С.99-101.

2. Pozhenko М.А., Didenko S.V. Modeling of the Episodical Wireless Networks with Dynamic Topology. //Proceedings of the IEEE-Siberian conference on control and communications (SIBCON-2003), Tomsk — 2003 — P.60-63.

Поженко M.A., Диденко C.B. Моделирование эпизодических беспроводных сетей с динамической топологией. //Материалы международной конференции «Контроль и коммуникации (СИБКОН-2003)», Томск — 2003 — С.60-63.

3. Sonkin М.А., Grinemayer V.V., Pecherskaya ЕЛ., Didenko S.V., Pozhenko M.A. The Transfer Information System Basing on the VIP-M Packet Controller as a Mean of Multilevel Distributed Control Systems Constrution. //Proceedings of the IEEE-Siberian conference on control and communications (SIBCON-2003), Tomsk — 2003 — P.77-79.

Сонькин М.А., Гринемаер В.В., Печерская Е.И., Диденко C.B., Поженко М.А. Система передачи информации на основе пакетного контроллера ВИП-М как основа построения многоуровневой распределенной системы управления. // Материалы международной конференции «Контроль и коммуникации (СИБКОН-2003)», Томск — 2003 — С.77-79.

4. Ботыгин И.А., Поженко М.А. Объектно-ориентированное имитационное моделирование Intranet-сетей. // Материалы второй Международной научно-практической конференции «Моделирование. Теория, методы и средства». — Новочеркасск: Изд-во ООО НПО «ТЕМП», 2002, —Ч. 1. — С.15-18.

5. Поженко М.А. Применение имитационного моделирования в процессе проектирования беспроводных вычислительных сетей. //Тезисы докладов международной научно-технической конференции «Информатика и проблемы телекоммуникаций». — Новосибирск, 2003. — Т. 2. — С. 157-158.

6. Поженко М.А. Особенности построения модели компьютерной сети с динамически изменяющейся структурой. //Материалы второй Международной научно-технической конференции «Информатизация процессов формирования открытых систем на основе СУБД, САПР, АНСИ и систем искусственного интеллекта». — Вологда: Изд-во ВоГТУ, 2003г. — С.141-144.

7. Поженко М.А. Система объектно-ориентированного моделирования вычислительных процессов в информационных системах. //Материалы третьей Всероссийской очно-заочной научно-практической конференции «Информационные технологии в управлении и учебном процессе вуза». — Владивосток: Изд-во. Владивостокского государственного университета экономики и сервиса (ВГУЭС), 2003. —С.148-149.

8. Поженко М.А. Проектирование беспроводных вычислительных сетей. Особенности и алгоритмы маршрутизации. //Труды 4-й международной конференции молодых учёных и студентов «Актуальные проблемы современной науки». Естественные науки. Часть 17. Секции: информатика, вычислительная техника и управление. — Самара, 2003. — С.93-96.

9. Поженко М.А. Концепции визуального объектно-ориентированного модели- • рования в информационных системах. //Сборник материалов второй Всероссийской научно-практической конференции «Проблемы информатики в образовании, управлении, экономике и технике». — Пенза, 2002. — С.62-64.

10. Поженко М.А. Система объектно-ориентированного имитационного моделирования вычислительных процессов в сетях. // Научно-технический сборник «Математическое и программное обеспечение проектирования систем» Выпуск 2. — Томск: Изд-во. Томского политехнического университета,

2002. —С.38-41.

I

I

t

Подписано в печать 21.11.2003. Тираж 100 зкз.захаз№ 116. Бумага офсетная. Печать RISO. Отпечатано в типографии ООО «РауШ мбХ» Лицензия Серия ПД № 124)092 г. Томск, ул. Усова 7, ком. 052. тел. (3822) 56-44-54

* 18Ó72.

8672

• ВВЕДЕНИЕ.

ГЛАВА 1. ПРОБЛЕМЫ РАЗРАБОТКИ АЛГОРИТМИЧЕСКОГО ОБЕСПЕЧЕНИЯ ДЛЯ МАРШРУТИЗАЦИИ БЕСПРОВОДНЫХ ВЫЧИСЛИТЕЛЬНЫХ СЕТЕЙ.

1.1. Беспроводные вычислительные сети. Типы беспроводных локальных вычислительных сетей. ш 1.2. Недостатки традиционных и актуальность разработки новых алгоритмов маршрутизации БЛВС.

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

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

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

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

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

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

1.6. Цель и задачи исследования.

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

Одним из наиболее актуальных и динамично развивающихся сегодня направлений в беспроводных вычислительных сетях является создание мобильных эпизодических беспроводных локальных вычислительных сетей (МЭБЛВС). Повышенный интерес к ним вызван, прежде всего, такими свойствами сетей МЭБЛВС, как простота организации и возможность свободного перемещения беспроводных узлов. Сеть МЭБЛВС может быть создана в считанные минуты, и включать в себя десятки, а то и сотни беспроводных узлов. Мобильные эпизодические беспроводные сети могут использоваться при проведении встреч или конференций, операций поиска и спасения людей, обмена информацией в критических условиях, например при стихийных бедствиях или при проведении военных операций [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. Созданный программный пакет успешно апробирован на задачах исследования моделей проектируемых сетей в ООО «Стек» и ООО «Томская тран-ковая компания».

ЗАКЛЮЧЕНИЕ

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

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

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

1. Аничкин С.А., Белов С.А., Бернштейн А.В.и др. Протоколы информационно-вычислительных сетей: Справочник / Под ред. И.А.Мизина, А.П.Кулешова. — М.: Радио и связь, 1990. — 504 с.

2. Архангельский А.Я. Приемы программирования в Delphi. — СПб.: Изд-во «Бином», 2003 г. — 784 с.

3. Барфилд Эд , Уолтере Брайен. Программирование "клиент-сервер" в локальных вычислительных сетях: Учебник. /Пер.с англ. — М.:Филинъ, 1997.423 с.

4. Башилов Г. 108 Мбит/с по воздуху. // «Компьютера», 2002, № 01.2002 http://www.ferra.ru/online/networks/15085/ (06.11.2003)

5. Башилов Г. Wi-Fi: решение, оптимальное по цене. //Журнал СЮ 08.2002 http://www.ibusiness.ru/marcet/tele/19268/ (06.11.2003)

6. Бертсекас Д., Галлагер Р. Сети передачи данных: Пер. с англ. — М.: Мир, 1989. —544 с.

7. Блэк Ю. Сети ЭВМ: Протоколы, стандарты, интерфейсы. — М.: Мир, 1990.506 с.

8. Богуславский Л.Б. Управление потоками данных в сетях ЭВМ. — М.: Энер-гоатомиздат, 1984. — 168 с.

9. Ю.Бутрименко А.В. Разработка и эксплуатация сетей ЭВМ. — М.: Финансы и статистика. — 1981. — 256 с.

10. Буч Г. Объективно-ориентированное проектирование (с примерами применения). Пер. с англ. — М.: Конкорд, 1992. — 519 с.

11. Верма Преймоуд К. Сети связи ЭВМ. Оценка эффективности функционирования: Структурный анализ: Пер. с англ. — М.: Радио и связь, 1992. — 113 с.

12. З.Вишневский В.М. Теоретические основы проектирования компьютерных сетей. — М.: Техносфера, 2003. — 512 с.

13. Вишневский В.М., Ляхов А.И., Терещенко Б.И. и др. Региональные беспроводные сети передачи данных на базе протокола RADIO-ETHERNET: состояние, моделирование, примеры реализации // Информационные процессы — 2001. — Том. 1, №1 С. 10-32.

14. Вычислительные сети и сетевые протоколы: Пер. с англ. / Дэвис Д., Барбер Д., Прайс У., Соломонидес С. — М.: Мир, 1982. — 562 с.

15. Гуреев А.В., Кустов В.А. Компьютерное моделирование беспроводных сетей и проблемы их электромагнитной совместимости // Электронный журнал «Исследовано в России». №134/2002. С. 1505-1518. http://zhurnal.ape.relarn.rU/articles/2002/l 34.pdf (06.11.2003).

16. Ирвин Дж., Харль Д. Передача данных в сетях: инженерный подход: Пер. с англ. — СПб.: «БВХ-Петербург», 2003. — 448 с.

17. Клейнкрок Л. Вычислительные системы с очередями: Пер. с англ. — М.: Мир, 1979. —600 с.

18. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. /Пер. с англ. Под ред. А. Шеня. — М.: МЦНМО, 2002. — 960 с.

19. Компьютерные сети. Принципы, технологии, протоколы: Учебник для вузов. 2-е изд. / В .Г. Олифер, Н.А. Олифер. — СПб.: Питер, 2003. — 864 с.21 .Кристофидес Н. Теория графов. Алгебраический подход. — М.: Мир, 1978. — 432 с.

20. Круглински Дэвид Дж. Основы Visual С++. Пер. с англ. — М.: Изд-во «Русская редакция», ТОО «Channel Trading Ltd.», 1997. — 696 с.

21. Кульчин М. Технологии корпоративных сетей. — СПб: Изд-во «Питер», 2000. —704 с.

22. Кучерявый Е.А. NS2 как универсальное средство имитационного моделирования сетей связи. // Tampere University of Technology, http://www.cs.tut.fi/~yk (06.11.2003).

23. Леонов С. Беспроводные сети: стандарты и технологии. // "Компьютера", 2002, http://www.ferra.ru/online/networks/17031/ (06.11.2003).

24. Методические материалы и документация по пакетам прикладных программ. Выпуск 57. Телеобработка данных и вычислительные сети. Опыт разработки и применения международных стандартов. — М.: МЦНТИ, 1988.—4.1—223 с.

25. Мизин И.А., Богатырев В.А., Кулешов А.П. Сети коммутации пакетов. — М.: Радио и связь, 1986. — 408 с.

26. Нанс, Бэрри. Компьютерные сети: Пер.с англ. —М.:БИНОМ,1996 —395 с.

27. Нессер, Даниэль Дж. Оптимизация и поиск неисправностей в сетях: Пер. с англ. — Киев: Диалектика, 1996. — 372 с.

28. Норенков И.П., Трудоношин В.А. Телекоммуникационные технологии и сети. — М.: МГТУ им. Н.Э.Баумана, 1998. — 231 с.

29. Палладии А., Семенцов В. Беспроводные технологии в цифрах и фактах. // http://www.mobile-review.com/articles/2003/wireless-market.shtml (06.11.2003).

30. Поженко М.А. Система объектно-ориентированного моделирования вычислительных процессов в информационных системах. //Материалы третьей

31. Всероссийской очно-заочной научно-практической конференции «Информационные технологии в управлении и учебном процессе вуза». — Владивосток : Изд-во. Владивостокского государственного университета экономики и сервиса (ВГУЭС), 2003. — С. 148-149.

32. Протоколы и методы управления в сетях передачи данных. / Пер. с англ. Под ред. Ф.Ф.Куо. — М.: Радио и связь, 1985. — 480 с.

33. Робачевский A.M. Операционная система UNIX. — СПб.: BHV Санкт-Петербург, 1998. — 528 с.

34. Рули Джон Д., Мэсвин Д., Хендерсон Т., Хеллер М. Сети Windows NT 4.0: Пер. с англ. — Киев: BHV, 1997. — 798 с.

35. Самойленко С.И. Сети ЭВМ. — М.: Наука, 1986. — 243 с.

36. Семенов Ю. А. Протоколы и ресурсы Internet. — М.: Радио и связь, 1996 — 320 с.

37. Сетевые средства Windows NT. Windows NT Workstation и Windows NT Server версия 3.5 — СПб: BHV — Санкт-Петербург, 1996 — 496 с.

38. Сипсер Р. Архитектура связи в распределенных системах. В 2 кн. — М.: Мир, 1981. —744 с.

39. Стефан Томас А., Пламли С. Создание Intranet-сети в Windows NT 4.0. Пер. с англ. — Киев: BHV, 1997 — 395 с.

40. Столлингс В. Беспроводные линии связи и сети: Пер. с англ. — М.: Издательский дом «Вильяме», 2003. — 640 с.

41. Шамис В.А. Borland С++ Builder. Программирование на С++ без проблем. — М.: «Нолидж», 1997. — 266 с.

42. Шварц М. Сети связи: протоколы, моделирование и анализ: Пер. с англ. — М.: Наука, 1992. — 4.1. — 336 с.

43. Шварц М. Сети связи: протоколы, моделирование и анализ: Пер. с англ. — М.: Наука, 1992. — Ч.2.— 272 с.

44. Шварц М. Сети ЭВМ. Анализ и проектирование. / Пер. с англ. Под ред. В.А. Жожикашвили. — М.: Радио и связь, 1981. — 336 с.

45. Шиллер Иоган. Мобильные коммуникации: Пер. с англ. — М.: Издательский дом «Вильяме», 2002. — 384 с.

46. Щербо В.К., Киричев В.М., Самойленко С.И. Стандарты по локальным вычислительным сетям: Справочник / Под ред. С.И.Самойленко. — М.: Радио и связь, 1990. —304 с.

47. Якубайтис Э.Я. Локальные информационно-вычислительные сети. — Рига: Зинатне, 1985. — 284 с.

48. Ahn G-S., Campbell А.Т., Lee S-B., Zhang X. «INSIGNIA» // Internet Draft, http://www.comet.columbia.edu/insignia/ draft-ietf-manet-insignia-01 .txt (06.11.2003).

49. Andrew L. L. H., Kusuma A. A. N. A. Generalised analysis of a QoS-aware routing algorithm // IEEE GLOBECOM. — 1998. — P. 118-123.

50. Alwan A., Bagrodia R., Bambos N., Gerla M., Kleinrock L., Short J., Villasenor J. Adaptive Mobile Multimedia Networks. // IEEE PCS Magazine — 1996.

51. Barry M. Leiner, Robert J. Ruth, Ambatipudi R. Sastry. Goals and Challenges of the DARPA GloMo Program. // IEEE Personal Communications. — December1996. — №3(6). — P.34-43.

52. Brenner P. A Technical Tutorial on the IEEE 802.11 Protocol. // BreezeCom. —1997.

53. CACI Products Company // http://www.caciasl.com/products/products.cfm (06.11.2003).

54. Chiang C.C. Routing in Clustered Multihop, Mobile Wireless Networks with Fading Channel // Proceedings IEEE SICON'97. — April 1997. — P. 197-211.

55. Chen S., Nahrstedt K. Distributed Quality-of-Service Routing in Ad Hoc Networks. // IEEE Journal on Selected Areas in Communications, special issue on Wireless Ad Hoc Networks. —August 1999. — V. 17, №8. — P. 1488-1505.

56. Chen T.-W., Gerla M. Global State Routing: A New Routing Scheme for Ad-hoc Wireless Networks. // Proceedings of IEEE ICC. — Atlanta, GA. — Jun. 1998. — P.171-175.

57. Corson M. S., Ephremides A. A Distributed Routing Algorithm for Mobile Wireless Networks. // Journal of ACM/Baltzer Wireless Networks. — 1995. — VI, №1. — P.61-81.

58. Corson M. S., Papademetriou S., Papadopoulos P., Park V. D., Qayyum A. An Internet MANET Encapsulation Protocol (IMEP) Specification. // IETF Draft, draft-ietf-manet-imep-spec01.txt. — August 1998.

59. Costa L. H. M. K., Fdida, S., Duarte О. С. M. B. Distance-vector QoS-based Routing with Three Metrics. // IFIP Networking 2000 / HPN High Performance Networking. — May 2000. — P.847-858.

60. Costa L. H. M. K., Duarte, О. С. M. B. A Scalable QoS-based Routing Mechanism for Supporting Multimedia Applications. // IEEE ICMCS International Conference on Multimedia Computing Systems. — Florence, Italy. — June 1999. —V. 2. —P. 347-351.

61. Desbrandes F., Bertolotti S., Dunand L. Opnet 2.4: an environment for communication network modeling and simulation. // Proceedings of the European Simulation Symposium. — Delft, Netherlands. — October 1993. — P.609-614.

62. Dijkstra. E. A Note on Two Problems in Connexion with Graphs. // Numerische Mathematik. — 1959. — № 1. — P. 269-271.

63. Gafni E., Bertsekas D.D. Distributed Algorithms for Generating Loop-Free Routes in Networks with Frequently Changing Topology. // IEEE Trans. Com-mun. — January 1981.

64. Gartner Dataquest research and advisory firm, http://www.gartner.com/ (6.11.2003).

65. Guerin R., Orda A. QoS-based Routing in Networks with Inaccurate Information. // Theory and Algorithms. Infocom. — Japan. — April 1997.

66. Internet Engineering Task Force (IETF) Mobile Ad Hoc Networks (MANET) Working Group Charter, http://www.ietf.org/html.charters/manet-charter.html (06.11.2003).

67. Access Control (MAC) and Physical Layer (PHY) specifications," —1999 — http://standards.ieee.org/wireless/ (06.11.2003).

68. IEEE 802.1 lb-1999 Supplement to 802.11-1999,Wireless LAN MAC and PHY specifications: Higher speed Physical Layer (PHY) extension in the 2.4 GHz band — http://standards.ieee.org/wireless/ (06.11.2003).

69. Ko Y.-B., Vaidya N. H. Location-Aided Routing (LAR) in Mobile Ad Hoc Networks.//Proceedings of Mobicom '98 4th Annual ACM/IEEE International Conference on Mobile Computing and Networking, Dallas, TX. — October 1998. —P.66-75.

70. Krishna P., Vaidya N.H., Chatterjee M., Pradhan D.K. A Cluster-Based Approach for Routing in Dynamic Networks. // ACM SIGCOMM Computer Communications Review. — 1997. — P.102.

71. Lee S-B., Ahn G-S., Zhang X., Campbell A. T. INSIGNIA: An IP-Based Quality of Service Framework for Mobile ad Hoc Networks. // Journal of Parallel and Distributed Computing. — April 2000. — V. 60, N 4. — P.374-406.

72. Lee S.-J., Su W., Hsu J., Gerla M., Bagrodia R. A Performance Comparison Study of Ad Hoc Wireless Multicast Protocols. // Proceedings of the IEEE Conference on Computer Communications (INFOCOM), Tel Aviv, Israel. — March 2000. — P.565-574.

73. Lee S-B., Campbell A.T. INSIGNIA: In-band signaling support for QoS in mobile ad hoc networks.// Proceedings of 5th International Workshop on Mobile Multimedia Communications (MoMuC, 98), Berlin. — Oct. 1998.

74. Liu J., Perrone L. F., Nicol D. M., Liljenstam M., Elliott C., Pearson D. Simulation modeling of large-scale ad-hoc sensor networks.// European Simulation Interoperability Workshop. — 2001.

75. Lokesh Bajaj, Mineo Takai, Rajat Ahuja, Ken Tang, Rajive Bagrodia, Mario Gerla. GloMoSim: A Scalable Network Simulation Environment. //UCLA Computer Science Department Technical Report 990027. — May 1999.

76. Malkin G. RFC 1721: RIP Version 2 Protocol Analysis. // Network Working Group.—Nov. 1994.

77. Malkin G.S., Steenstrup M.E. Distance-Vector Routing, // Routing in Communications Networks, edited by M.E. Steenstrup, Prentice Hall. — 1995. — P.83-98.

78. McCanne S., Floyd S. The ns network simulator, http://www.isi.edu/nsnam/ns/ (06.11.2003).

79. Mingliang Jiang, Jinyang Li, Y.C. Tay, Cluster Based Routing Protocol //August 1999 IETF Draft, http://www.ietf.org/internet-drafts/draft-ietf-manet-cbrp-spec-01.txt (06.11.2003).

80. Moy J. OSPF Version 2. Internet RFC 1583.// Network Working Group — March 1994.

81. Park V.D., Corson M.S. A highly adaptive distributed routing algorithm for mobile wireless networks.// Proceedings INFOCOM'97. — Apr. 1997. http://www.ics.uci.edu/~-atm/adhoc/paper-collection/corson-adaptive-routing-infocom97.pdf (06.11.2003).

82. Perkins, C.E. and E.M. Royer. Ad-hoc On Demand Distance Vector Routing. //Proceedings of the 2nd IEEE Workshop on Mobile Computing Systems and Applications. — New Orleans, LA. — February 1999. — P.90-100.

83. Perkins C., Bhagwat P. Highly Dynamic Destination-Sequenced Distance Vector Routing (DSDV) for Mobile Computers. // ACM SIGCOMM'94. — October 1994.

84. Pozhenko M.A. Designing of mobile wireless networks with use of specific algorithms of routing. //Proceedings of the International Conference Interactive systems: The problems of human-computer interaction, Ulyanovsk. — 2003. — P.99-101.

85. Pozhenko M.A., Didenko S.V. Modeling of the Episodical Wireless Networks with Dynamic Topology. //Proceedings of the IEEE-Siberian conference on control and communications (SIBCON), Tomsk. — 2003. — P.60-63.

86. Raju, J. and J.J. Garcia-Luna-Aceves. A New Approach to On-demand Loop-Free Multipath Routing.//Proceedings of the 8 th Annual IEEE International

87. Conference on Computer Communications and Networks ICCCN'99— Boston—MA—October 1999—P.522-527.

88. Salama H. F., Reeves D. S., Viniotis Y. A Distributed Algorithm for Delay-Constrained Unicast Routing.// INFOCOM'97— Japan— April 1997—P.84-91.

89. Shin K. G., Chou C.-C. A Distributed Route-Selection Scheme for Establishing Real-Time Channel. // Sixth IFIP Int'l Conf. on High Performance Networking Conf. (HPN95) — Sep. 1995— P.319-329.

90. Sivakumar R., Bharghavan V. CEDAR: A Core-Extraction Distributed Routing Algorithm. IEEE Journal on Selected Areas in Communications. Vol 17, No. 8—August 1999.

91. Sivakumar R., Das В., Bharghavan V. An Improved Spine-based Infrastructure for Routing in Ad Hoc Networks.// IEEE Symposium on Computers and Communications— 1998.

92. Sun Q., Langendorfer H. A New Distributed Routing Algorithm with End-to-End Delay Guarantee.//Unpublished paper—1997.

93. Tanenbaum A.S. Computer Networks, 3rd Edition.// Prentice Hall, Upper Saddle River, NJ—March 1996.

94. Toh Chai-Keong. Associativity-Based Routing for Ad-Hoc Mobile Networks. Wireless Personal Communications, — 1997—P. 103-139.

95. Toh Chai-Keong. A novel distributed routing protocol to support Ad hoc mobile computing// Proc. 1996 IEEE 15th Annual Int'l. Phoenix Conf. Сотр. and Commun. —Mar. 1996 — P.480-486.

96. Toh C.-K. Long-lived Ad-Hoc Routing based on the concept of Associativity. // March— 1999— IETF Draft, 8 pages, http://www.ietf.org/internet-drafts/draft-ietf-manet-longlived-adhoc-routing-00.txt (06.11.2003).

97. Toh, C.-K. A Novel Distributed Routing Protocol to Support Ad Hoc Mobile Computing. //Proceedings of 15th IEEE Annual International Phoenix Conference on Computers and Communications, — 1996—P.480-486.

98. Tsai J., Gerla M. Multicluster, Mobile, Multimedia Radio Network.//ACM-Baltzer Journal of Wireless Networks—1995—P.255-265.

99. Tsu-Wei Chen and Mario Gerla. Global State Routing: A New Routing Scheme for Ad-hoc Wireless Networks .//Proceedings IEEE ICC'98—1998. http://www.ics.uci.edu/~atm/adhoc/paper-collection/gerla-gsr-icc98.pdf (06.11.2003).

100. Wang Z. and J. Crowcroft. QoS Routing for Supporting Resource Reservation.//IEEE J. Select. Areas Commun., vol. 14— Sept. 1996—P.1228-1234.

101. Wu K., Harms J. Location Trace Aided Routing in Mobile Ad Hoc Net-works./ЛЕЕЕ International Conference on Computer Communications and Networks ICCCN 2000— Las Vegas— Nevada— USA— October 2000.

102. Zhang L., Deering S., Estrin D., Shenker S., Zappala D. RSVP: A New Resource ReSerVation Protocol.// IEEE Network, September 1993.

103. Е® Encoetng f V»4«e Over ««fworfc | eroa«ca»t Vt«»e PfsKtotflan ( OieMal ettrvaiHtane* Security

104. THE BRANCH OF THE COMPANY "OARIM VISION Co., Ltd. 10/3, Academicheskii ave., Tomsk, RUSSIA, 634055 Tel.: /3822/ 25-94-48, Fax: /3822/ 25-93-88 E-mail: office@darim.ru1. DARIM1. Д^кгорТЪмсшго ф Bi1. Г.А. Стучебровшикала "Даримjfrffil 2003г.1. АКТ

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

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

107. Утверждаю" Технический директор х ООО «<$фма «Стек»,^J/jrT М.А. Лоосs/j^J 2003г. -. ■ • •«i1. АКТ

108. О внедрении результатов диссертационной работы аспиранта кафедры ИПС1. ТПУ Поженко М.А.