Анализ механизмов повышения эффективности передачи информации в высокоскоростных локальных и городских беспроводных сетях тема диссертации и автореферата по ВАК РФ 05.12.13, кандидат технических наук Якимов, Михаил Юрьевич

• Якимов, Михаил Юрьевич
• кандидат технических наук
• 2008

Оглавление диссертации кандидат технических наук Якимов, Михаил Юрьевич

Введение.

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

1.1. Стандартизация протоколов беспроводного доступа.

1.2. МАС-уровень протокола 802.11.

1.3.РНУ-уровень протокола 802.11.

1.4. Основные механизмы повышения производительности и надежности локальных беспроводных сетей.

1.5. Механизмы обеспечения качества обслуживания (QoS) в протоколе IEEE 802.11.

1.6. Стандарт IEEE 802.16 городских беспроводных сетей.

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

2. Исследование механизмов повышения эффективности передачи одноадресных сообщений в локальных беспроводных сетях.

2.1. Методы полиномиально-логарифмической и экспоненциально-логарифмической аппроксимации для оценки интенсивности ошибок в беспроводном канале.

2.2. Исследование механизмов переключения скорости передачи.

2.3.Метод совместной оптимизации скорости передачи и механизма фрагментации в канале точка-точка.

2.4. Механизм прямых соединений в беспроводных сетях с протоколом IEEE 802.11.

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

3.1. Мультилидерный подход при многоадресной передаче.

3.2. Оценка показателей производительности и надежности многоадресной передачи с фиксированными лидерами.

3.3. Анализ выполнимости QoS-требований.

3.4. Оценка показателей производительности и надежности многоадресной передачи со случайно выбираемыми лидерами.

4. Результаты применения разработанных методов и их анализ.

4.1. Оценка точности методов аппроксимации интенсивности ошибок в беспроводном канале с АБГШ.

4.2. Результаты исследования механизма переключения скорости передачи ARF.

4.3. Результаты совместной оптимизации скорости передачи и механизма фрагментации в канале точка-точка.

4.4. Численный анализ протоколов многоадресной передачи.

Введение диссертации (часть автореферата) на тему «Анализ механизмов повышения эффективности передачи информации в высокоскоростных локальных и городских беспроводных сетях»

Последнее десятилетие характеризуется бурным развитием беспроводных сетей передачи информации. В первую очередь это относится к сетям локального и городского масштаба, где применение беспроводных технологий обеспечивает гибкость архитектуры сети, включая поддержку мобильности, быстроту проектирования и низкие затраты на реализацию. Рост числа пользователей беспроводных сетей, а также объёмов передаваемых данных обусловил появление новых высокоскоростных технологий. За десять лет скорость передачи в локальных и городских беспроводных сетях выросла с 1-2 Мбит/с до 50-70 Мбит/с. В скором времени ожидается появление устройств беспроводного доступа со скоростями до 500 Мбит/с. На сегодняшний момент наиболее популярными технологиями построения высокоскоростных локальных и городских беспроводных сетей являются WiFi (стандарт IEEE 802.11 [1]) и WiMAX (стандарт IEEE 802.16 [2]).

Современные беспроводные протоколы должны обеспечивать не только высокоскоростную передачу данных, но и качественную доставку голосовой и видеоинформации в условиях наличия электромагнитных помех, неизбежных в локальных и городских беспроводных сетях. Под качеством понимается достижение определенных показателей производительности и надежности при передаче информации по беспроводной сети. В последних версиях стандартов беспроводных сетей появился ряд механизмов поддержки качества обслуживания. Однако, требуется детальное исследование эффективности этих механизмов, для чего необходимо разработать новые методы оценки производительности и надежности передачи данных. Проблемам оценки производительности сетей передачи информации на основе стохастических моделей посвящено значительное количество работ, среди которых следует отметить работы российских и зарубежных ученых: Г.П. Башарина, П.П. Бочарова, О.М. Брехова, В.М. Вишневского, B.C. Жданова, В.А. Жожикашвили, Н.А. Кузнецова, О.Г. Мелентьева, А.В. Печинкина, В.К. Попкова, В.В. Рыкова, С.Н. Степанова, G. Balbo, S.C. Bruell, L. Fratta, L. Kleinrock, M. Olivetty, H. Takagi, S.C. Borst, O.J. Boxma и др. Среди аналитических работ, посвященных исследованию протоколов IEEE 802.11 и IEEE 802.16 и оценке производительности построенных на их базе беспроводных сетей, наиболее значимыми являются работы А.В. Винеля, В.М. Вишневского, А.И. Ляхова, G. Bianchi, F. Cali, М. Conti, Е. Gregory, Q. Ni. В большинстве этих работ производительность оценивается в предположении идеального канала.

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

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

Задачами диссертационного исследования являются:

1. Получение аналитических зависимостей вероятности искажения кадра от уровня помех;

2. Разработка метода совместной оптимизации скорости передачи и порога фрагментации;

3. Аналитическое исследование механизма переключения скоростей;

4. Изучение интерференции прямых соединений станций в сетях IEEE 802.11 и разработка механизмов избегания этой интерференции;

5. Разработка нового протокола надежной многоадресной передачи в беспроводной сети и его математической модели.

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

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

1. Методы полиномиально-логарифмической и экспоненциально-логарифмической аппроксимации вероятности искажения кадра;

2. Аналитическая модель обобщенного механизма переключения скорости передачи типа ARF (Auto-Rate Fallback);

3. Метод совместной оптимизации скорости передачи и механизма фрагментации;

4. Механизм защиты прямых соединений от интерференции в беспроводных сетях с протоколом IEEE 802.11;

5. Мультилидерный механизм многоадресной передачи;

6. Аналитическая модель мультилидерного механизма с фиксированными лидерами;

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

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

1. Разработаны новые методы полиномиально-логарифмической и экспоненциально-логарифмической аппроксимации зависимости вероятности искажения кадра от отношения сигнал/шум;

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

3. Разработан метод совместной оптимизации скорости передачи и механизма фрагментации;

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

5. Предложен новый механизм многоадресной передачи, основанный на выделении части получателей в качестве лидеров, ответственных за подтверждение многоадресных пакетов;

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

Практическая ценность и реализация результатов. Результаты работы внедрены и используются на практике, что подтверждено соответствующими актами. Предложенные и изученные механизмы переключения скорости передачи1 и многоадресной передачи реализованы в радиомаршрутизаторе РЭС «Рапира», который был разработан ИППИ РАН в рамках Федеральной целевой научно-технической программы «Исследования и разработки по приоритетным направлениям развития науки и техники» на 2002-2006 годы по Государственному контракту № 02.477.11.1003 «Разработка технологии создания нового поколения широкополосных телекоммуникационных средств комплектации беспроводных систем передачи данных, голоса и информации».

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

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

- Международных семинарах «Распределенные компьютерные и телекоммуникационные сети. Теория и приложения» (2003 г., 2007 г., Москва), (2006 г., София, Болгария);

- 4th IEEE International Conference on Mobile Ad-hoc and Sensor Systems (MASS 2007, Pisa, Italy);

- 3rd ACM International Workshop on QoS and Security for Wireless and Mobile Networks (Q2SWinet 2007, Chania, Crete Island, Greece);

- Международных конференциях по проблемам управления (МКПУ-Ш 2006г., 2008г., Москва);

- Научных конференциях МФТИ в 2005 и 2007г. (Долгопрудный);

- Конференции молодых ученых и специалистов "Информационные технологии и системы" (ИТиС-2007, Звенигород);

- 4-th IEEE Consumer Communications and Networking Conference (CCNC'07, Las Vegas, Nevada, USA);

- IX Международной научно-практической конференции "Проблемы функционирования информационных сетей" (ПФИС-2006, Новосибирск);

- Семинарах ИППИ РАН.

Публикации. По теме диссертации опубликовано 15 научных работ [3 - 17]. Из них 2 статьи [3, 4] опубликованы в рецензируемых научных журналах, один из которых утвержден в перечне ВАК. 13 работ [5 - 17] опубликованы в трудах ведущих международных и российских научно-технических конференций.

Структура и объем диссертационной работы. Диссертация состоит из введения, четырех глав, заключения, списка литературы, включающего 70 наименований и приложения. Работа изложена на 158 страницах и содержит 64 рисунка и 9 таблиц.

Заключение диссертации по теме «Системы, сети и устройства телекоммуникаций», Якимов, Михаил Юрьевич

Заключение

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

1. Проведен анализ основных механизмов повышения-эффективности передачи протоколов высокоскоростных локальных и городских' беспроводных сетей ГЕЕЕ 802.11 и IEEE 802.16;

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

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

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

5. На основе имитационного моделирования показано, что интерференция прямых соединений в структурированных сетях IEEE 802.11 приводит к существенно неравномерному распределению пропускной способности канала между соединениями. Для избегания этого эффекта разработан новый механизм работы прямых соединений, который был представленf на рассмотрение рабочей группы комитета IEEE;

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

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

Список литературы диссертационного исследования кандидат технических наук Якимов, Михаил Юрьевич, 2008 год

1. 1.EE Std 802.11, 2007 Edition, Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) specification, June 2007.

2. IEEE Std 802.16, 2004 Edition, Air Interface for Fixed Broadband Wireless Access Systems, October 2004.

3. Вишневский B.M., Ляхов А.И., Якимов М.Ю. Оптимизация работы высокоскоростной беспроводной сети в условиях помех. // Электросвязь. 2007, №8, стр. 16-19.

4. V. Vishnevskiy, A. Safonov, М. Yakimov, Eunsoo Shim, Alexander Gelman "Scalable Blind Search and Broadcasting over Distributed Hash Tables", Journal on Computer Communications, Elsevier, vol. 31, is. 2, pp. 292-303, 2008

5. Andrey Lyakhov, Vladimir Vishnevsky and Mikhail Yakimov. Multicast QoS Support in IEEE 802.11 WLANs. Proceedings of the 4th IEEE International Conference on Mobile Ad-hoc and Sensor Systems (MASS 2007), Oct. .2007, Pisa, Italy

6. Якимов М.Ю., Сафонов А.В. Обеспечение качества доставки многоадресных пакетов в WiFi сетях. // Труды 50-й научной конференции МФТИ, Долгопрудный, МО, Ноябрь 2007

7. Якимов М.Ю.*, Сафонов А.В. Поддержка надежной многоадресной передачи в беспроводном протоколе IEEE 802.11. // Труды, конференции "Информационные технологии и системы" (ИТиС-2007), Звенигород, сентябрь 2007, с. 54-58

8. В.М.Вишневский, А.И. Ляхов, А.А. Сафонов, М.Ю. Якимов. "Распределенный МАС-уровень высокоскоростных беспроводных персональных сетей." Тр. III Международной конференции по проблемам управления, Москва, 20-22 июня 2006 г., т.2, с. 148.

9. А.И. Ляхов, Д.Н. Мацнев, М.Ю. Якимов, Адаптация протокола IEEE 802.11 к среде передачи. // Труды международного семинара «Распределенные компьютерные и телекоммуникационные сети. Теория и приложения (DCCN-2003)», М.: Техносфера, 2003, т. 2, с. 92-114'

10. М.Ю. Якимов, Адаптация работы протокола IEEE 802.11а в режиме распределенного управления к условиям беспроводной среды передачи. // Труды 48-й научной конференции МФТИ, Долгопрудный, МО, Ноябрь 2005

11. И.В. Зарубинский, М.Ю. Якимов. "Обзор механизмов автоматического переключения скорости передачи в ШБС." Тр. Ш Международной конференции по проблемам управления, Москва, 7-9 апреля 2008 г., с. 245246.

12. Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications: Higher-Speed Physical Layer Extension in the 2.4 GHz Band // IEEE Std 802.1 lb-1999 (Supplement to ANSI/IEEE Std 802.11, 1999 Edition).

13. Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications: High-speed Physical Layer in the 5 GHz Band // IEEE Std 802.1 la-1999 (Supplement to IEEE Std 802.11, 1999 Edition).

14. Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications: Further Higher Data Rate Extension in the 2.4 GHz Band // IEEE

15. Std 802.1 lg-2003 (Supplement to ANSI/IEEE Std 802.11, 1999 Edition).i t.

16. Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY)

17. Specifications: Medium Access Control (MAC) Quality of Service Enhancements //t

18. EE Std 802.1 le-2005 (Supplement to ANSI/IEEE Std 802.11, 1999 Edition).

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

20. G. Bianchi, "Performance Analysis of the IEEE 802.11 Distributed Coordination Function," IEEE Journal on Selected Areas in Communications, vol. 18, pp. 535547, March 2000.

21. F. Call, M. Conti, and E. Gregory, "Dynamic Tuning of the IEEE 802.11 Protocol to-Achieve a Theoretical Throughput Limit," IEEE/ACM Transactions on Networking, vol. 8, pp. 785-799, December 2000.

22. V.M. Vishnevsky and A.I. Lyakhov, "IEEE 802.11 Wireless LAN: Saturation Throughput Analysis with Seizing Effect Consideration," Cluster Computing, vol. 5, pp. 535-548, April 2002.

23. P. Chatzimisios, A. C. Boucouvalas, and V. Vitsas, "IEEE 802.11 packet delay a finite retry limit analysis," in Proc. IEEE Globecom, San Francisco, USA, Dec. 2003.

24. R. Iyengar, P. Iyer, B. Sikdar, "Delay Analysis of 802.16 based Last Mile Wireless Networks," Ргое. 49th IEEE Global Telecommunications Conference (GLOBECOM 2006), San Francisco, California, USA, November 27 December 1, 2006.

25. A. Vinel, Y. Zhang, Q. Ni, A. Lyakhov, "Efficient Request Mechanism Usage in IEEE 802.16," Proc. 49th IEEE Global Telecommunications Conference

26. GLOBECOM 2006), San Francisco, California, USA, November 27 December 1,2006.

27. A.I. Lyakhov, V.M. Vishnevsky, "Packet Fragmentation in Wi-Fi Ad Hoc Networks with Correlated Channel Failures," Proc. 1st IEEE Int. Conf. on Mobile Xd-hoc and Sensor Systems (MASS 2004), October 24-27, 2004, Fort Lauderdale, Florida, USA.

28. A.I. Lyakhov and V.M. Vishnevsky, "Comparative Study of 802.11 DCF and its Modification in the Presence of Noise," Wireless Networks, vol. 11, no. 6, November 2005, pp.729-740.

29. Q. Ni, T. Li, T. Turletti, and Y. Xiao, "Saturation throughput analysis of error-prone 802.11 wireless networks," Wireless Communications and Mobile Computing, vol. 5, no. 8, November 2005, pp.945-956.

30. Chatzimisios P, Boucouvalas AC, Vitsas V. Performance analysis of IEEE 802.11 DCF in presence of transmission errors. Proceedings of IEEE ICC 2004; 7: 38543858.

31. Velkov ZH, Spasenovski B. Saturation throughput delay analysis of IEEE 802.11 DCF in fading channel. Proceedings of IEEE ICC 2003; 1: 121-126.

32. Yin J, Wang X, Agrawal DP. Optimal packet size in error-prone channel for IEEE 802.11 distributed coordination function. Proceedings of IEEE WCNC 2004; 3: 1654-1659.

33. He JH, Tang ZY, Yang ZK, et al. Performance evaluation of distributed access scheme in error-prone channel. Proceedings of IEEE TENCON 2002; 2: 1142-1145.

34. Yeo J, Agrawala A. Packet error model for the IEEE 802.11 MAC protocol. Proceedings of IEEE PIMRC 2003; 2: 1722-1726.

35. Мелентьев О.Г. Теоретические аспекты передачи данных по каналам с группирующимися ошибками. Москва, Горячая линия Телеком, 2005, 232 с.

36. KAMERMAN A. and MONTEBAN L. WaveLAN-II: A high-performance wireless lan for the unlicensed band // AT&T Bell Labs Technical Journal, vol.2, no.3, рр.Ы8-133, Aug. 1997.

37. LACAGE M., MANSHAEI M.H. and TURLETTI T. IEEE 802.11 rate adaptation: A practical approach // in Proceedings of MSWiM, 2004 ,42. http ://madwifi. org/browser/madwifi/trunk/athrate/onoe43. http://www.atheros.comI

38. HOLLAND G., VAIDYA N., and BAHL V. A rate-adaptive MAC protocol for , multihop wireless networks // in Proceedings of Mobicom, 2001

39. KIM J., KIM S., CHOI S., and QIAO D. CARA: Collision-aware rate adaptation for IEEE 802.11 WLANs // in Proceedings of IEEE INFOCOM, 2006

40. BICKET J.C. Bit-rate Selection in Wireless Networks // M.S Thesis, MIT, February 2005.

41. WONG S.H, YANG H., LU S., and BHARGAVAN V. Robust rate adaptation for 802.11 wireless networks // in Proceedings of Mobicom, 2006.48. http://madwifi.org/browser/madwifi/trunk/athrate/minstrel

42. K. Tang and M. Gerla, "Random Access MAC for Efficient Broadcast Support in Ad Hoc Networks," Proc. IEEE WCNC 2000, pp. 454-459, Sep. 2000.

43. К. Tang and M. Gerla, "MAC Reliable Broadcast in Ad Hoc Networks," Proc. IEEE MILCOM2001, pp. 1008-1013, Oct. 2001.

44. Min-Te Sun, Lifei Huang, Anish Arora, Ten-Hwang Lai, "Reliable MAC Layer Multicast in IEEE 802.11 Wireless Networks," Proc. of the International Conference on Parallel Processing (ICCP'02)

45. Joy Kuri, Sneha Kumar Kasera, "Reliable Multicast in Multi-access Wireless LANs," ACM/Kluwer Wireless Networks, vol. 7, pp. 359-369, 2001.

46. Han-Chieh Chao, S. W. Chang, J. L. Chen "Throughput Improvements Using the Random Leader Technique for the Reliable Multicast Wireless LANs," Lecture Notes In Computer Science, Proc. of the First ICN-Part 1 Vol. 2093, pp. 708 -719, 2001

47. Yongho Seok, Diego Dujovne, Thierry Turletti, Pedro Cuenca, "Leader based Multicast Proposal," IEEE 802.11 -07/0144r2, January 2007

48. S. Gupta, V. Shankar, and S. Lalwani, "Reliable multicast MAC protocol for wireless LANs," Proc. IEEE ICC'03, Anchorage, Alaska, May 2003

49. А.И. Ляхов, A.A. Сафонов, М.Ю. Якимов и др. "Fair and protected DLS" IEEE 802.11-07/2489rl

50. А.И. Ляхов, М.Ю. Якимов и др. "802.11 Multicast Enhancements for Multimedia Streaming" IEEE 802.1 l-07/2842r0

51. А.И. Ляхов, А А. Сафонов, М.Ю. Якимов и др. "Reliable multicast with QoS support in IEEE 802.11" IEEE 802.1 l-07/2554r063. http://www.mathworks.com

52. GPSS World // http://www.minutemansoftware.com

53. R. Bruno, M. Conti, E Gregori, "Throughput Analysis and Measurements in IEEE 802.11 WLANs with TCP and UDP Traffic Flows," IEEE Transactions on Mobile Computing, Volume 7, Issue 2, Feb. 2008, pp. 171 186

54. Ляхов А.И., Мацнев Д.Н., "Исследование функционирования городской беспроводной сети передачи данных", Электросвязь, 2003. № 6. С.40-43.

55. Вишневский В.М., Ляхов А.И., Мацнев Д.Н., Терещенко Б.Н.Деликин Ю.В.', " Сеть Radionet: опыт разработки и реализации," VII межд.конф. "Информационные сети, системы и технологии" (ICINASTe-2001),Минск, 2001. Т.2. С.135-139.

56. В. Bing. Wireless Local Area Networks: The New Wireless Revolution. New York: Wiley-Interscience, 2002.

57. Д. Бертсекас, P. Галлагер, «Сети передачи данных», Москва, Издательство «Мир», 1989, 544 с.