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

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

Гайнулин Андрей Габдулхакович

УПРАВЛЕНИЕ РЕСУРСАМИ В БЕСПРОВОДНЫХ СЕТЯХ С ПЕРЕМЕННОЙ ТОПОЛОГИЕЙ

Специальность 05.13.01. - "Системный анализ, управление и обработка информации (в науке и промышленности) по техническим наукам"

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

-о

о !

Нижний Новгород, 2009 г.

003467879

Работа выполнена на кафедре «Теория Цепей и Телекоммуникации» Нижегородского государственного технического университета им. Р.Е. Алексеева

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

доктор технических наук, профессор, Крылов Владимир Владимирович

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

доктор технических наук, доцент, Хранилов Валерий Павлович

кандидат технических наук, Егоров Евгений Евгеньевич

Ведущая организация: ФГУП ФНПЦ «НИИИС им. Ю.Е. Се-

дакова», г. Нижний Новгород

Защита диссертации состоится « 21 » мая 2009 года в 15 часов в ауд. 1258 на заседании диссертационного совета Д212.165.05 при Нижегородском государственном техническом университете им. Р.Е. Алексеева по адресу: 603950, г. Нижний Новгород, ул. Минина, 24

С диссертацией можно ознакомиться в библиотеке Нижегородского государственного технического университета им. P.E. Алексеева Автореферат разослан «_»_2009 года.

Ученый секретарь диссертационного совета

A.C. Суркова

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

В задачи работы входило

1. Построение математической модели высокоскоростной беспроводной сети.

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

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

4. Разработка системы тестирования протоколов.

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

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

Научная новизна и практическая ценность работы состоит в том, что:

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

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

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

В работе разработаны протоколы управления выделением ресурсов беспроводной ad hoc сети с адаптацией к параметрам сети, протокол маршрутизации передаваемых данных беспроводной ad hoc с поддержкой смешанных ти-

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

Полученные результаты могут найти применение при проектировании высокоскоростных беспроводных сетей со смешанными видами передаваемого трафика (как пакетного, так и потокового) и случайным доступом к разделяемым ресурсам сетей. Результаты исследований, полученные автором в работе, использованы в проектно-конструкторской деятельности ООО «Теком» при проектировании и разработке системы беспроводной связи «Falcon 3», что подтверждается актом о внедрении от 10 ноября 2008 года. Разработанная система моделирования беспроводных сетей WNS внедрена в компании «НКТ» для оценки параметров качества обслуживания проектируемых сетей беспроводной связи, что подтверждается актом о внедрении от 26 июня 2008 года.

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

- всероссийской научно-технической конференции «Информационные системы и технологии ИСТ-2007» (г. Нижний Новгород, 2007 г.)

- конференции ICTTA'06 - 2nd IEEE international conférence on information & communication technologies: from theoiy to applications (г. Дамаск, Сирия, 2006)

- всероссийской научно-технической конференции «Информационные системы и технологии ИСТ-2006» (г. Нижний Новгород, 2006 г.)

- IV молодежной международной научно технической конференции «Будущее технической науки» (г. Нижний Новгород, 2005 г.);

- всероссийской научно-технической конференции «Информационные системы и технологии ИСТ-2005» (г. Нижний Новгород, 2005);

- конференции PIMRC 2004 - 15 IEEE International Symposium on Personal, Indoor and Mobile Radio Communications (г. Барселона, 2004);

- 2-ой Международной конференция IEEE "Цепи и системы в телекоммуникациях" (г. Москва, 2004)

- научно-технической конференции «Технические, программные и математические аспекты управления сложными распределёнными системами» (г. Нижний Новгород, 2004).

Публикации. Основное содержание работы отражено в 19 печатных работах.

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

1. Математическая модель разделяемого канала беспроводной сети и построенная на ее основе модель беспроводной сети с переменной топологией.

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

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

4. Результаты анализа эффекта от применения протоколов в беспроводной сети передачи данных.

Структура и объем диссертации. Текст диссертационной работы состоит из введения, четырех глав, заключения, списка литературы (51 наименование) и приложения. Общий объема диссертации 168 страниц, в том числе 159 страниц основного текста, 7 страниц списка литературы, 2 страницы приложений, 6 таблиц, 60 рисунков.

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

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

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

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

Другая технология, интенсивно развивающаяся в настоящее время, предполагает построения беспроводных сетей с нефиксированной инфраструктурой - ad hoc сетей или MANET (mobile ad hoc networking) сетей. В отличие от сетей с фиксированной инфраструктурой, в ad hoc сетях все узлы являются мобильными и могут быть связаны динамически в произвольной форме. Все узлы ведут себя не только как оконечные пользовательские терминалы, но и как маршрутизаторы и принимают участие в обнаружении и обслуживании маршрутов к другим узлам сети.

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

передачи данных, больший диаметр сети и меньшую стоимость абонентского комплекта.

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

Для сетей с централизованным управлением характерной является иерархическая структура сети, в которой есть один или несколько центральных узлов, осуществляющих обработку и перенаправление данных от абонентов-источников к абонентам-получателям и управление сетью в целом. Типичными примерами таких сетей являются сети WiFi, BlueTooth. Управление передачей данных в таких сетях возможно в 2 режимах - использование выделенного канала с гарантированной задержкой и пропускной способностью или режим случайного доступа к разделяемому каналу связи с использованием протоколов CSMA и МАСА. Передача данных в таких сетях производится без маршрутизации и управления приоритетами.

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

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

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

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

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

• Разработка протокола управления ресурсами беспроводной сети на базе анализа текущей нагрузки, инвариантного к архитектуре построения сети и набору доступных ресурсов.

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

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

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

где ТЯ; - множество выделенных каналов, которые могут быть использованы для передачи данных узлом с порядковым номером 1 в маршруте, ЛС] -множество выделенных каналов, которые могут быть использованы для приема данных узлом с порядковым номером ] в маршруте, N - количество выделенных каналов, требуемое для обеспечения, заданной пропускной способности маршрута.

Выигрыш от переиспользования ресурсов составит

где Мкласт - количество ребер в пределах кластера сети, с! - число узлов-соседей в кластере сети, п - число смежных узлов-соседей в кластере сети.

, / е [о, длина маршрута - з]

,[77?, плсм]и[га1Ч2 П ДО

(1)

При этом выигрыш будет тем больше, чем больше будет число соседей в кластере с! и меньше число общих соседей в кластере п. Проиллюстрируем зависимость величины выигрыша от количества соседей (1 при фиксированных значениях п=2 и п=3:

Рис. 1. Зависимость величины выигрыша при переиспользовании ресурсов

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

г- _

(2 • ^ - и +1) • Ьср • с где V/ - максимально достижимая пропускная способность сети, с1 - число узлов-соседей в кластере сети, п - число смежных узлов-соседей в кластере сети, N - общее число узлов в сети, Скс ~ пропускная способность канала связи (бит/с), Ьср - средняя длина сообщения (бит), а с - константа, определяемая конкретной структурой сети.

«XI100) : «41 ЮН

Рис. 2. Зависимость нормированной пропускной способности сети от среднего числа соседних узлов (п = ё/4). В беспроводных сетях с коммутацией пакетов неизбежно возникновение коллизий при передаче, которые приводят к необходимости повторно передачи и тем самым увеличивают фактическую величину поступившей нагрузки.

При этом соотношение между интенсивностью поступившей X и обслуженной А,' нагрузок описывается следующим выражением:

Я = (3)

где т - время прослушивания эфира, необходимое для обнаружения коллизии.

Учитывая, что наиболее популярным протоколом управления доступом является С8МА, для него были проанализированы параметры качества обслуживания при передаче данных через разделяемый канал. Так для 1-настойчивого протокола СБМА формула зависимости использования пропускной способности канала от суммарной обслуженной нагрузки имеет вид:

Я(Л') =

Л' • е'х'(Ма)[\ + Л' + аЛ'( 1 + Л' + аЛ' / 2)]

(4)

Л'(1 + 2а) - (1 - е" я'а) + (1 + аЛ')е~^а) где а - задержка распространения волны в пределах кластера сети, V -интенсивность обслуженной нагрузки с учетом повторных передач.

Для локальных сетей этой задержкой распространения обычно пренебрегают и выражение принимает вид:

Л ■е

■'МО

Х + ех'

Проиллюстрируем полученное выражение с помощью графика:

(5)

Рис. 3. Зависимость использования пропускной способности канала связи от интенсивности суммарной нагрузки в кластере сети Однако такое соотношение не позволяет оценить, какой объем поступившей нагрузки является для такой сети эффективно обслуживаемым (то есть суммарная скорость поступившей нагрузки не превышает доли реально используемой скорости передачи данных в канале связи). Для того, чтобы получить зависимость использования пропускной способности канала связи от интенсивности поступившей нагрузки в кластере сети построим график, в котором по оси X отложим значения а по оси У - значения 8(Х.'). Полученный график будет иметь вид:

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

Рис. 5. Зависимость отношения приведенного коэффициента использования пропускной способности канала от нормированной интенсивности поступившей нагрузки

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

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

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

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

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

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

На вход каждой СМО поступает 2 независимых потока заявок. Один поток заявок соответствует пакетам данных, которые уже передаются в пределах данного кластера («белые» заявки), второй поток заявок - это трафик, который необходимо передать через беспроводную сеть («черные» заявки). Заявки из обоих потоков ставятся в общую очередь и обслуживаются в порядке поступления в соответствии с их приоритетом (если он определен). На выходе СМО устанавливается диспетчер, который разделяет поступающие заявки по цвету и передает на вход следующей СМО только «черные» заявки (диспетчер в данной модели полагается идеальным, то есть с нулевой задержкой обработки заявки). Использование такого диспетчера позволяет рассматривать виртуальный канал как набор независимых СМО со своими входными параметрами.

Тсяущи» (рафм • пистсрвссп*

Рис. 6. Модель узла передачи данных беспроводной сети в виртуальном канале.

Суммарная задержка для виртуального канала передачи данных описывается следующим выражением:

ЯГ -2--(6)

к 2

где

I(i,L) = Л + Ф(/) • Л + Ф{Ь - i +1) • Л

О, *<0 х, О S х £ 2, 2, х>2

L - длина маршрута (количество пролетов), i - порядковый номер узла в пределах маршрута, /е[0,£-1], А - интенсивность потока передаваемых данных, к - приоритет передаваемого пакета, X - интенсивность обслуживаемой нагрузки, х2 - второй начальный момент распределения длин пакетов.

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

В наиболее общем случае работа алгоритма маршрутизации состоит из 3 этапов:

1) Отыскание доступных маршрутов от узла - источника до узла - получателя.

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

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

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

Введено понятие маршрута передачи сообщений в рамках предложенной модели сети. Маршрутом называется множество, состоящее из номеров узлов Nodes, через которые этот маршрут проходит. Весом маршрута будем называть

13

сумму весов всех входящих в него узлов. Ациклическим будем называть маршрут, множество вершин Nodes которого не содержит повторяющихся элементов. Независимыми будем называть такие два маршрута М| и что истинно следующее условие: (Nodes, о Nodes г * Nodes,) и (Nodes, л Nodes2 * Nodes2). С учетом определений, введенных выше, сформулирована задача первого этап работы алгоритма маршрутизации: отыскание всех ациклических независимых маршрутов от узла - источника данных до узла - потребителя информации.

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

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

Используя полученные во второй и третьей главах соотношения и алгоритмы разработан протокол управления ресурсами беспроводной сети Network Resource Management Protocol (NRMP). Разработана система команд протокола и полей данных, дано их подробное описание. Разработаны и формализованы процедуры поиска, занятия и освобождения маршрутов передачи данных и ресурсов сети.

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

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

14

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

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

Для экспериментальной оценки параметров качества работы алгоритма управления была предложена следующая схема эксперимента. Эксперимент проводился на сетях 3 размеров - малая сеть (20 узлов), средняя сеть (60 узлов), большая сеть (100 узлов). Узлы сети случайным образом размещаются на квадратной поверхности со стороной X. Для каждого из размеров сетей создано по 100 вариантов уникальных размещений. Для моделирования передачи данных создаются сценарии передачи данных с использованием генератора пакетного самоподобного трафика. Для каждого варианта размещения создано по 100 сценариев, по 50000 реализаций самоподобных выборок потока. Таким образом, общее число экспериментов, проведенное для сети определенного размера, составляет 10 000 штук.

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

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

• АСЮУ (как наиболее распространенный)

•ЫМШ> с критерием минимизации внесенной задержки •NN111? с критерием минимизации внесенной нагрузки • ЫМЯР с минимаксным критерием

Результаты моделирования для сетей, состоящих из 20, 60 и 100 узлов приведены на рисунках ниже. Все результаты представлены в нормированном виде. По оси абсцисс на сводном графике отложен порядковый номер эксперимента (от 1 до 100 по количеству вариантов размещения сетей), по оси ординат - выигрыш в процентах по сравнению с пропускной способностью, достигнутой с использованием протокола АСЮУ.

, Результаты моделирования для сети из 20 узлов

А

»

—*

и <1

г.г ■уп

»4

-I

"¡V

•• • -

- - • МОМР НОТРГМ

■ ч. . . .» - * I I I «' 'I 1 / ! Ч

ж

Рис. 7. Выигрыш от использования протокола ЫМЯР (20 узлов)

14.334

| 12.004 , I 10,054 • ■ДЭН * • «.оэк «,тч

МЭИ

Результаты моделирования для сети из 60 узлов

- ^ -м—

\ I* *** - * — 4 ~ —

) >, rJ.it;; ;[ I, < , у

» ^ ч *«»* ».; ' I • II. * чу

1 :>.'[< * , у :;»чА»"

1 4 Т 10 11 1» 19 22 2$ 21 31 М 17 40 43 4« 4* 32 » 91 <1 И <7 70 71 7» 71 «2 •» •• »1 »4 97 100

-< - ' ММ» ¿мерам - - - ИЯМГ Пиру»!

ЧМЙР Мкнюсмсм ЛООУ

Рис. 8. Выигрыш от использования протокола ИМ ЯР (60 узлов)

Результаты моделирования для сети из 100 узлов

Ю»МР 1едер.*ив

---№.№ Квгрузм

КМНР Минимокснм« -ЛООУ

1 й Й 88 £ 5 с

Рис. 9. Выигрыш от использования протокола NMRP (100 узлов)

Сводный анализ результатов для 3 типов сетей приведен ниже (пропускная способность приведена в нормированных величинах, нормировка пс пропускной способности разделяемого канала связи):

Таблица 1. Результаты моделирования работы протокола ЫМИР.

Протокол Измерения АСЮУ ИМЯР (мин. вн. задержки) ЫМЯР (мин. вн. нагрузки) К'МЯР (минимаксный) |

20 узлов В ^ПГО/ГУСКШЯ СПГХГОЕНОСТЬ 1,6246 1,6361 1,6341 1,6261

| 20 узлов ¡Выигрыш (%) — 0,71% 0,59% 0,09%

{ 60 узлов В У В ^пгош-сош снасшюсгь 2,4869 2,5947 2,5493 2,5257

60 узлов Выигрыш (%) — 4,41% 2,56% 1,6%

100 узлов у ^пютст.1Я СПОСОБНОСТЬ 3,871 4,4603 4,4096 4,0672

100 узлов | Выигрыш (%) — 15,28% 13,95% 5,10%

Построим зависимости максимально достижимой пропускной способности и выигрыша от использования протокола ЫМЯР от размера сети.

Суммарная пропускная способность сети

•— Н*М* Иримрий мшиимимцин «нмамиоЯ лдертш - «ИЯМР Критерий мииимюацим •мсмнио* нагруми

- КЯМ? МмютюскнЯ кр*т*р*Я -АООУ

Рис. 10. Зависимость суммарной пропускной способности сети для различных протоколов маршрутизации от размера сети

Выигрыш в пропусков способности по сравнению с АООУ

1ММ 1100%

- - - МЮ Принц«» тмивми ■««тт! чгууя»

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

Спи с «оммумциЯ ним ■ 201 «Ь МО умо*

Рис. 12. Выигрыш в пропускной способности сети от использования протокола КМЯР по сравнению с маршрутизацией по кратчайшему пути

Выигрыш в пропускной способности от использования протокола ЫМ11Р

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

! .

£ г

(3 «

и

Пропускная способность сети с коммутацией каналов

-ИМИ"

—Крпчайший л

<0

Ьжрсеп

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

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

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

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

В работе получены следующие основные результаты:

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

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

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

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

5. Математическая модель и алгоритм реализованы в виде библиотеки классов на языке С++.

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

7. Определены границы применимости разработанного протокола и математической модели канала передачи данных, лежащей в его основе.

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

ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ,

в ведущих рецензируемых научных журналах и изданиях из перечня ВАК министерства образования и науки РФ:

1. Гайнулин, А.Г. Моделирование алгоритма маршрутизации передаваемых данных в беспроводных сетях со смешанными типами коммутации / А.Г. Гайнулин // Вестник Нижегородского Университета им. Н.И. Лобачевского.-2008.-№ 1. - С.93-99.

патенты

2. Пат. 2291572 РФ, МКИ Н04В 7/24, H04J 4/00. Способ беспроводной локальной связи.

в прочих научных журналах и изданиях

3. Архитектура самоорганизующихся беспроводных сетей, использующих сверхширокополосные сигналы / А.Г. Гайнулин, В.Ю. Аристархов, А.В. Калинин, В.В. Крылов, Р.А. Левченко, А. А. Плужников, В.И. Шкунов // Сборник трудов НГТУ / НГТУ - Н. Новгород: Изд. НГТУ, 2004 - С. 99106.

4. Разработка физического уровня и моделирование персональных беспроводных сетей, использующих сверхширокополосные сигналы / А.Г. Гайнулин, В.Ю. Аристархов, А.В. Калинин, В.В. Крылов, Р.А. Левченко, А.А. Плужников, В.И. Шкунов // Сборник трудов НГТУ / НГТУ - Н. Новгород: Изд. НГТУ, 2004 - С. 107-113.

5. Gaynulin A. Ad hoc Circuit Switching Wireless Network Based on the UWB Technology / A. Gaynulin, V. Krylov, V. Aristarkhov // 2nd IEEE International Conference on Circuits and Systems for Communications (ICCSC'04). - 2004. -Vol. 2,-P. 182-186.

6. Gaynulin A. Ad hoc wireless network based on the UWB technology / A. Gaynulin, V. Krylov, V. Aristarkhov //Personal, Indoor and Mobile Radio Communications, 2004. PIMRC 2004. 15th IEEE International Symposium. - 2004. - Vol. 2,- P. 969-973.

7. Gaynulin A. Dynamic resource allocation in ad hoc hybrid high speed wireless network / A. Gaynulin, V. Krylov // 2nd IEEE international conference on information & communication technologies: from theory to applications (ICCTA'06). - 2006. - Vol. 2,- P. 2461- 2466.

8. Gaynulin A. Routing Algorithms for ad hoc High Speed Hybrid Wireless Networks / A. Gaynulin, V. Krylov // 4rth International Conference: Sciences of

Electronic, Technologies of Information and Telecommunications (SETIT 2007). - 2007. - Vol. 1,- P. 162-169.

9. Гайнулин, А.Г. Адаптивный алгоритм маршрутизации пакетного трафика в беспроводных сетях / А.Г. Гайнулин // Информационные системы и технологии. ИСТ - 2007: тезисы докладов Всероссийской научно-технической конференции / НГТУ - Н. Новгород: Изд. НГТУ, 2007 - С. 133.

10. Гайнулин, А.Г. Алгоритмы маршрутизации и динамическое управление ресурсами беспроводной сети с гибридной коммутацией / А.Г. Гайнулин, В.В. Крылов // Сборник трудов Второй Международной научно-практической конференции "Исследование, разработка и применение высоких технологий в промышленности" / СПб - СПб.: Изд-во Политехи, ун-та, 2005 - С. 34.

11. Гайнулин, А.Г. Архитектура самоорганизующихся беспроводных сверхширокополосных сетей / А.Г. Гайнулин, В.В. Крылов, А.А. Плужников // Молодежь и современные информационные технологии: Сборник трудов II Всероссийской научно-практической конференции студентов / ТПУ -Томск: Изд. ТПУ, 2004 - С. 153-154.

12. Гайнулин, А.Г. Архитектура самоорганизующихся беспроводных сетей, использующих сверхширокополосные сигналы / А.Г. Гайнулин // ТЕКОМ-2004: Актуальные вопросы построения систем управления сложным распределенным оборудованием и предоставлением услуг / НГТУ -Н. Новгород: Изд. НГТУ, 2004 - С. 15-16.

13. Гайнулин, А.Г. Динамическое управление ресурсами беспроводной сети с гибридной коммутацией / А.Г. Гайнулин, В.В. Крылов // Информационные системы и технологии. ИСТ - 2006: тезисы докладов Всероссийской научно-технической конференции / НГТУ - Н. Новгород: Изд. НГТУ, 2006-С. 126.

14. Гайнулин, А.Г. Исследование и анализ алгоритмов маршрутизации и синхронизации в ad hoc сетях / А.Г. Гайнулин, В.В. Крылов, К.А. Кручинкин // Информационные системы и технологии. ИСТ - 2005: тезисы докладов Всероссийской научно-технической конференции, посвященной 60-летию Победы в Великой Отечественной войне и 110-летию изобретения радио А. С. Поповым / НГТУ - Н. Новгород: Изд. НГТУ, 2005 - С. 53.

15. Гайнулин, А.Г. Маршрутизация в беспроводных сетях с коммутацией каналов / А.Г. Гайнулин // Тезисы докладов VI международной научно-технической конференции «Будущее технической науки» / НГТУ - Н. Новгород: Изд. НГТУ, 2007 - С. 91.

17.

18.

19.

Подписано в печать 20.04.09. Формат 60 х 84 '/16. Бумага офсетная. Печать офсетная. Уч.-изд. л. 1,0. Тираж 100 экз. Заказ 275.

Нижегородский государственный технический университет им. Р. Е. Алексеева. Типография НГТУ. 603950, Нижний Новгород, ул. Минина, 24.

Гайнулин, А.Г. Механизм самоорганизации узлов беспроводной сети, не имеющей строгой инфраструктуры / А.Г. Гайнулин, A.A. Плужников // Информационные системы и технологии. ИСТ - 2005: тезисы докладов Всероссийской научно-технической конференции, посвященной 60-летию Победы в Великой Отечественной войне и 110-летию изобретения радио А. С. Поповым / НГТУ - Н. Новгород: Изд. НГТУ, 2005 - С. 60. Гайнулин, А.Г. Механизм слияния беспроводных самоорганизующихся сетей с переменной топологией / А.Г. Гайнулин, В.В. Крылов, А.Г. Агафонов // Информационные системы и технологии. ИСТ - 2005: тезисы докладов Всероссийской научно-технической конференции, посвященной 60-летию Победы в Великой Отечественной войне и 110-летию изобретения радио А. С. Поповым / НГТУ - Н. Новгород: Изд. НГТУ, 2005 - С. 49. Гайнулин, А.Г. Оптимизация использования разделяемых ресурсов в беспроводной сети с переменной топологией / А.Г. Гайнулин, В.В. Крылов, A.B. Калачев // Информационные системы и технологии. ИСТ - 2005: тезисы докладов Всероссийской научно-технической конференции, посвященной 60-летию Победы в Великой Отечественной войне и 110-летию изобретения радио А. С. Поповым / НГТУ - Н. Новгород: Изд. НГТУ, 2005-С. 57.

Гайнулин, А.Г. Управление ресурсами в высокоскоростных беспроводных / А.Г. Гайнулин, В.В. Крылов // Тезисы докладов 11-й Нижегородской сессии молодых ученых (технические науки) / НГТУ - Н. Новгород: Изд. НГТУ, 2005-С. 41.

ВВЕДЕНИЕ.

ГЛАВА 1. ОБЗОР СУЩЕСТВУЮЩИХ РАЗРАБОТОК В ОБЛАСТИ ПОСТРОЕНИЯ БЕСПРОВОДНЫХ СЕТЕЙ.

1.1. Состояние развития беспроводных сетей.

1.2. Передача данных в беспроводных сетях, управление качеством обслуживания.

1.3. Управление ресурсами в беспроводных сетях, обеспечение качества обслуживания.

1.4. Выводы.

ГЛАВА 2. МОДЕЛЬ БЕСПРОВОДНОЙ СЕТИ ПЕРЕДАЧИ ДАННЫХ

2.1. Архитектура узла беспроводной сети.

2.2. Топологическая модель сети.

2.3. Оценка пропускной способности сети.

2.4. Маршруты передачи сообщений.

2.5. Выводы.

ГЛАВА 3. РАЗРАБОТКА И АНАЛИЗ ЭФФЕКТИВНОГО ПРОТОКОЛА УПРАВЛЕНИЯ РЕСУРСАМИ БЕСПРОВОДНОЙ СЕТИ.

3.1. Общее описание и задачи протокола.

3.2. Алгоритм сбора информации о нагрузке.

3.2. Модель виртуального канала передачи данных.

3.3. Алгоритм маршрутизации передаваемых данных.

3.4. Реализация протокола NRMP.

3.5. Выводы.

ГЛАВА 4. ИССЛЕДОВАНИЕ ЭФФЕКТИВНОСТИ ПРОТОКОЛА УПРАВЛЕНИЯ РЕСУРСАМИ БЕСПРОВОДНОЙ СЕТИ.

4.1. Построение системы для экспериментальной оценки параметров протокола управления ресурсами беспроводной сети.

4.2. Моделирование передачи пакетных данных.

4.3. Моделирование передачи потоковых данных.

4.4. Выводы.

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

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

Актуальность

Одной из важнейших потребностей современного технотронного общества является потребность в высокоэффективных системах обмена информацией. Окружив себя огромным количеством электронных устройств, человек создал не только глобальные сети передачи информации, но и сформировал мобильные, перемещающиеся вместе с ним самим персональные беспроводные сети. В состав таких сетей входят сотовые телефоны и другие мобильные средства связи, карманные персональные компьютеры (КПК), цифровые видео- и фотокамеры. Однако человеку оказалось недостаточно просто окружить себя такой сетью, необходимо было, чтобы такая сеть была интеллектуальной, то есть сама была в состоянии обнаруживать появление или исчезновение устройств - своих членов, отслеживать изменение их местоположения и т.п. факторы, влияющие на возможность обмена информации внутри такой сети. Для решения такого рода задач были созданы так называемые Ad Нос сети - сети с переменной топологией, без централизованного управления, где каждый узел обладал достаточной интеллектуальностью для осуществления всех вышеперечисленных действий. Так персональная сеть стала интеллектуальной, но оказалось, что человеку недостаточно независимой персональной сети. Использование такой сети было актуально именно во взаимодействии с другими существующими сетями и системами передачи информации. То есть возникла необходимость в создании некоторого единого протокола обмена данными между разнородными беспроводными персональными сетями, причем важным оказывались не только интеллектуальность и мобильность, но и очень высокая скорость передачи информации.

Последнее требование долгое время не удавалось удовлетворить, так как помехоустойчивость беспроводных систем передачи данных намного хуже, чем у проводных сетей, и, учитывая ограничения на ширину полосы передачи сигналов и мощность излучения, максимально достижимые скорости передачи составляли не более чем несколько десятков мегабит. Данную задачу особенно активно стали пытаться разрешить после того, как в 2002 году Федеральная комиссия по связи США регламентировала частотный диапазон для сверхширокополосной связи от 3.1 до 10.6 ГГц. Передача данных в этом диапазоне предполагала наличие большого количества каналов связи, доступных для обмена данными всем устройствам беспроводной сети, и как следствие, возможность передачи многочисленных потоков данных с различными требованиями к предоставляемому качеству обслуживания. Существующие алгоритмы управления и протоколы передачи данных для беспроводных Ad Нос сетей [14, 20, 25, 33, 48] оказались неподходящими или малоэффективными, когда речь шла о высокоскоростной многоканальной передаче данных. Все они были ориентированы на обмен данными в сетях, где доступен лишь один разделяемый канал передачи данных, и обмен данными производится в режиме коммутации пакетов. Потребовалось не просто модифицировать существующие подходы, но разработать качественно новые алгоритмы управления выделением ресурсов и протоколы передачи данных, способные адаптироваться к характеристикам обслуживаемой нагрузки и оптимизировать использование доступного ресурса пропускной способности сети. На сегодняшний день существование протоколов управления передачей данных для сетей подобного класса из открытых источников не известно. Разработка протоколов управления ресурсами такого рода сетей и анализ их применения в персональных сверхскоростных беспроводных сетях имеют научный и практический интерес.

Цель работы

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

Задачи работы

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

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

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

Методы исследования

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

Научная новизна

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

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

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

Практическая ценность

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

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

Результаты исследований, полученные автором в работе, использованы в проектно-конструкторской деятельности ООО «Теком» при проектировании и разработке системы беспроводной связи «Falcon 3», что подтверждается актом о внедрении от 10 ноября 2008 года (см. приложение 1). Разработанная система моделирования беспроводных сетей WNS внедрена в компании «НТК» для оценки параметров качества обслуживания проектируемых сетей беспроводной связи, что подтверждается актом о внедрении от 26 июня 2008 года (см. приложение 1).

Апробация работы

Основные результаты работы были доложены на:

- IV молодежной международной научно технической конференции «Будущее технической науки» (г. Нижний Новгород, 2005 г.);

- конференции «Информационные системы и технологии ИСТ-2005» (г. Нижний Новгород, 2005);

- конференции PIMRC 2004 - 15 IEEE International Symposium on Personal, Indoor and Mobile Radio Communications (г. Барселона, 2004);

- 2-ой Международной конференция IEEE "Цепи и системы в телекоммуникациях" (г. Москва, 2004)

- научно-технической конференции «Технические, программные и математические аспекты управления сложными распределёнными системами» (г. Нижний Новгород, 2004).

- конференции ICTTA'06 - 2nd IEEE international conference on information & communication technologies: from theory to applications (г. Дамаск, Сирия)

Публикации

Основное содержание диссертации отражено в 19 печатных работах [1-13, 18, 19, 28-31], в том числе опубликованные в изданиях, рекомендованных ВАК, [11].

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

1. Математическая модель разделяемого канала беспроводной сети и построенная на ее основе модель беспроводной сети с переменной топологией.

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

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

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

Структура и объем работы

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

4.4. Выводы

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

• Алгоритм, основанный на критерии минимизации внесенной задержки

• Алгоритм, основанный на критерии минимизации внесенной нагрузки

• Алгоритм, основанный на минимаксном критерии

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

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

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

• математическая модель и алгоритм реализованы в виде библиотеки классов на языке С++.

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

• определены границы применимости разработанного протокола и математической модели канала передачи данных, лежащей в его основе.

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

1. Гайнулин, А.Г. Динамическое управление ресурсами ad hoc сети с гибридной коммутацией / А.Г. Гайнулин, В.В. Крылов //

2. Информационные системы и технологии. ИСТ 2006: тезисы докладов Всероссийской научно-технической конференции / НГТУ - Н. Новгород: Изд. НГТУ, 2006 - С. 126.

3. Гайнулин, А.Г. Маршрутизация в беспроводных сетях с коммутацией каналов / А.Г. Гайнулин // Тезисы докладов VI международной научно-технической конференции «Будущее технической науки» / НГТУ Н. Новгород: Изд. НГТУ, 2007 - С. 91.

4. Гайнулин, А.Г. Моделирование алгоритма маршрутизации передаваемых данных в беспроводных сетях со смешанными типами коммутации / А.Г. Гайнулин // Вестник Нижегородского Университета им. Н.И. Лобачевского. 2008. - № 1. - С.93-99.

5. Гайнулин, А.Г. Управление ресурсами в высокоскоростных беспроводных сетях / А.Г. Гайнулин, В.В. Крылов // Тезисы докладов 11-й Нижегородской сессии молодых ученых (технические науки) / НГТУ Н. Новгород: Изд. НГТУ, 2005 - С. 41.

6. Громаков, Ю.А. Стандарты и подсистемы подвижной радиосвязи /Ю.А. Громаков М.: Эко-Трендз, 1998. - 239 с.

7. Егоров, Е.Е. Разработка алгоритмов управления в беспроводных сетях связи с коммутацией каналов: дис. . канд. техн. наук : 05.13.01: защищена 22.10.03 / Егоров Е.Е. НГТУ, 2003. - 149 с.

8. Крылов, В.В. Теория телетрафика и ее приложения. Основы теории систем массового обслуживания для задач телекоммуникаций / В.В. Крылов, С.С. Самохвалова.- БХВ-Петербург, 2005.- 288 с.

9. Олифер, В.Г. Компьютерные сети / В.Г. Олифер, Н.А. Олифер. СПб. : Питер, 2003. - 864 с.

10. Пат. 2291572 РФ, МКИ Н04В 7/24, H04J 4/00. Способ беспроводной локальной связи.

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

12. А.Г. Гайнулин, В.Ю. Аристархов, А.В. Калинин, В.В. Крылов, Р.А. Левченко, А.А. Плужников, В.И. Шкунов // Сборник трудов НГТУ / НГТУ Н. Новгород: Изд. НГТУ, 2004 - С. 107-113.

13. Ратынский, М. В. Основы сотовой связи / М. В. Ратынский; под ред. Д. Б. Зимина. 2-е изд., перераб. и доп. - М.: Радио и связь, 2000. - 248 с.

14. Шаповаленко, С.С. Динамическое моделирование и анализ корпоративных вычислительных систем / С.С. Шаповаленко // Сетевой журнал. 2001. - № 6. - С. 32-39.

15. Широкополосные беспроводные сети передачи информации / В.М. Вишневский, А.И. Ляхов, С.Л. Портной, И.В. Шахнович. М.: Техносфера, 2005. - 592 с.

16. Akavia G. Hierarchical Use of Dedicated Channels / G. Akavia, L. Kleinrock // An International Journal Performance Evaluation. 1989. - Vol. 9. - P. 135-142.

17. Anastasi G. HIPERLAN/1 MAC protocol: stability and performance analysis / G. Anastasi, L. Lenzini, E. Mingozzi // IEEE Journal on Selected Areas in Communications. 2000. - Vol. 18.- P. 1787-1798.

18. Cardei I. Resource Management for Ad-Hoc Wireless Networks with Cluster Organization /1. Cardei, M. Min // Cluster Computing. 2004. - Vol.7. - P. 91-103.

19. Chakeres I. AODV routing protocol implementation design /1. Chakeres, E. Belding-Royer // Proceedings. 24th International Conference on Distributed Computing Systems Workshops. 2004. - Vol. 1. - P. 698-703.

20. Gaynulin A. AD-HOC Circuit Switching Wireless Network Based on the UWB Technology / A. Gaynulin, V. Krylov, V. Aristarkhov // 2nd IEEE International Conference on Circuits and Systems for Communications (ICCSC'04). 2004. - Vol. 2.- P. 182-186.

21. Gaynulin A. Ad-hoc wireless network based on the UWB technology / A. Gaynulin, V. Krylov, V. Aristarkhov //Personal, Indoor and Mobile Radio Communications, 2004. PIMRC 2004. 15th IEEE International Symposium. -2004.-Vol. 2.-P. 969-973.

22. Guerino G. Radio resource management in infrastructure-based and ad hoc UWB networks / G. Guerino, C. Martello // Wireless communications and mobile computing. 2005.- Vol. 5. - P. 581-597.

23. Gupta P. The capacity of wireless networks / P. Gupta, P. Kumar // IEEE Transactions on Information Theory. 2000. - Vol. 2. - P. 388-404.

24. Hsien-Chou L. A WiMAX-based Connectionless Approach for High Mobility MANET / L. Hsien-Chou, L. Cheng-Jung // Advanced Communication Technology, the 9th International Conference. 2007. - Vol. 1. - P. 479-483.

25. Hussain A. The effect of detail on Ethernet simulation / A. Hussain, A. Kapoor, J. Heidemann //18th Workshop on Parallel and Distributed Simulation, 2004. PADS'04. 2004. - Vol. 1. - P. 97-104.

26. Johansson P. Rendezvous scheduling in Bluetooth scatternets / P. Johansson, M. Gerla // Communications, 2002. ICC 2002. IEEE International Conference. 2002. - Vol. 1.- P. 318-324.

27. Kelsch G. A comparison of battlefield carrier sense multiple access (CSMA) networks with theoretical CSMA network analysis / G. Kelsch // IEEE Military Communications Conference Proceedings, 1999. MILCOM 1999. -1999.-Vol. 2.-P. 761-765.

28. Khan R. An Efficient DSDV Routing Protocol for Wireless Mobile Ad Hoc Networks and its Performance Comparison / R. Khan, K. Reddy, A. Zaman // Second UKSIM European Symposium on Computer Modeling and Simulation EMS '08.-2008. Vol. 1.- P. 506-511.

29. Lam K. Optimization circuits for the Bellman-Ford computation algorithm / K.Lam, C. Tong // Electronics Letters. 1994. - Vol. 30.- P. 1584-1586.

30. Li H. Research on Mechanism Optimization of ZRP Cache Information Processing in Mobile Ad Hoc Network / H. Li, F. Qiu // International Conference on Wireless Communications, Networking and Mobile Computing. WiCom 2007. 2007. - Vol. 1.- P. 1593-1596.

31. Matria S. Sensor networks: an overview / S. Matria, M.Tubaishat // IEEE Potentials.- 2003.- Vol. 22.- P. 20-23.

32. Misra P. Routing Protocols for Ad Hoc Mobile Wireless Networks / P. Misra // Computer Science and Engineering. 1999. - Vol. 18.- P. 13-27.

33. Pei G. A wireless hierarchical routing protocol with group mobility / G. Pei, M. Gerla // IEEE Wireless Communications and Networking Conference. WCNC'99. 1999. - Vol. 3.- P. 1538-1542.

34. Qiang S. The Capacity of Wireless Ad Hoc Networks with Power Control / S. Qiang, Z. Xianwen // International Workshop on Cross Layer Design, 2007. IWCLD '07. 2007. - Vol. 1. - P. 20-24.

35. Ramanathan R. A brief overview of ad hoc networks: challenges and directions / R. Ramanathan, J. Redi // IEEE Communications Magazine. -2002. Vol. 40.- P. 20-22.

36. Royer E. A Review of Current Routing Protocols for Ad-Hoc Mobile Wireless Networks / E. Royer, C. Toh // IEEE Personal Communications. -1999,- Vol. 4.-P. 46-55.

37. Takagi H. Throughput Analysis for Persistent CSMA Systems / H. Takagi, L. Kleinrock // IEEE Transactions on Communications. — 1985. Vol. 33. - P. 627-638.

38. Ting-Hung C. Efficient Fisheye state routing protocol using virtual grid in high-density ad-hoc networks / C. Ting-Hung, H. Shyh-In // The 8th International Conference Advanced Communication Technology, 2006. ICACT 2006. 2006. - Vol. 3.- P. 4-10.

39. Tsu-Wei C. Global state routing: a new routing scheme for ad-hoc wireless networks / C. Tsu-Wei, M. Gerla// 1998 IEEE International Conference on Communications, 1998. ICC 98. Conference Record. 1998. - Vol. 1.- P. 171-175.