Управление ресурсами в беспроводных сетях с переменной топологией тема диссертации и автореферата по ВАК РФ 05.13.01, кандидат технических наук Гайнулин, Андрей Габдулхакович

• Гайнулин, Андрей Габдулхакович
• кандидат технических наук
• 2009

Оглавление диссертации кандидат технических наук Гайнулин, Андрей Габдулхакович

ВВЕДЕНИЕ.

ГЛАВА 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-х этапный универсальный алгоритм маршрутизации передаваемых данных в беспроводных сетях, применение которого повышает суммарную пропускную способность сети.

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

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

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

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

Список литературы диссертационного исследования кандидат технических наук Гайнулин, Андрей Габдулхакович, 2009 год

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.