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

• Лукин, Дмитрий Вадимович
• кандидат технических наук
• 2010

Оглавление диссертации кандидат технических наук Лукин, Дмитрий Вадимович

Введение.

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

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

1.2 Структура протокола IEEE 802.16.

1.3 Физический уровень.

1.3.1 Структура кадра.

1.3.2 Спецификации физического уровня.

1.3.3 Формат управляющей секции.

1.4 Подуровень преобразования сервиса.

1.5 Основной подуровень MAC.

1.5.1 Подзаголовок упаковки.

1.5.2 Подзаголовок фрагментации.

1.5.3 Механизм подтверждений.

1.6 Типы сервисов в протоколе IEEE 802.16.

1.7 Механизм запроса полосы пропускания.

1.7.1 Одноадресный опрос.

1.7.2 Передача ЗПП с прикреплением (piggy-backing).

1.7.3 Конкурентный период запросов на полосу пропускания.

1.7.4 Конкурентный запрос полосы пропускания на основе множественного доступа с кодовым разделением.

1.7.5 Инкрементные и агрегированные ЗПП.

1.7.6 Выделение полосы пропускания.

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

2. Базовая модель передачи пакетов в сети IEEE 802.16.

2.1 Оценка времени обслуживания пакетов.

2.2 Модель изменения очереди зарегистрированных пакетов.

2.3 Аналитическая модель конкурентного доступа.

3. Модель сети с прикреплением запросов полосы пропускания к пакетам данных.

3.1 Оценка средней длины очереди зарегистрированных пакетов и доли неактивных станций.

3.2 Аналитическая модель конкурентного доступа с учетом возможности прикрепления запросов.

4. Расширения моделей для учета специфики трафика и физической реализации сетей стандарта IEEE 802.16.

4.1 Расширение модели в случае группового потока.

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

4.3 Расширение модели для учета CDMA-режима запроса полосы пропускания.

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

5.1 Исследование работы сети без прикрепления запросов к данным.

5.2 Анализ сети с возможностью прикрепления запросов к данным.

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

В последние два десятилетия бурный рост вычислительной техники и компьютерного оборудования привели к стремительному развитию сетевых технологий. Основным направлением развития сетей в настоящее время является построение новых высокоскоростных беспроводных сетей, которые получают все большее и большее распространение, причем развитие получили не только беспроводные локальные сети (WLAN), но и городские беспроводные сети (Wireless Metropolitan Access Network, WirelessMAN).

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

Стандарт ШЕЕ 802.16 [2-3] является основой технологии широкополосной связи, рассчитанной на внедрение в городских беспроводных сетях. Стандарт ШЕЕ 802.16 определяет общие правила передачи, не оговаривая при этом конкретные способы реализации предусмотренных стандартом механизмов и взаимодействия их между собой, таким образом, предоставляя широкие возможности для выработки алгоритмов и проверки их эффективности [4]. Таким образом, требуется детальное исследование эффективности этих алгоритмов в сетях различной конфигурации и условиях динамически меняющихся потоков передаваемой информации. Проблемам оценки производительности сетей передачи информации на основе стохастических моделей и методам доступа посвящено значительное количество работ, среди которых следует отметить работы российских и зарубежных ученых: Г.П. Башарина, О.М. Брехова, В.М. Вишневского, B.C. Жданова, В.А. Жожикашвили, Н.А. Кузнецова, А. П. Кулешова, О.Г. Мелентьева, А.В. Печинкина, В.К. Попкова, В.В. Рыкова, О. В. Семенову, С.Н. Степанова, М. Adamou, G. Balbo, S.C. Borst, О,J. Boxma, S.C. Bruell, L. Fratta, L. Kleinrock,

M. Olivetty, Н. Takagi и др. Среди аналитических работ, посвященных исследованию протокола ШЕЕ 802.16 и оценке производительности построенных на их базе беспроводных сетей, наиболее значимыми являются работы A.B. Винеля, В.М. Вишневского, А.И. Ляхова, A.M. Тюрликова, D. Cho, С. Cicconetti, Q. Ni, J. Seo, D. Staehle, Y. Zhang.

Время работы централизованной сети под управлением протокола ШЕЕ 802.16 делится на кадры. Каждый кадр состоит из восходящего и нисходящего подкадров, используемых для передачи восходящего (от оконечных станций к базовой станции) и нисходящего (от базовой станции к оконечным станциям) трафика. При передаче оконечной станцией (ОС) регулярного трафика базовая станция (БС) выделяет фиксированные интервалы в восходящем подкадре для передачи данных на постоянной основе. При динамически меняющемся трафике ОС информируют базовую станцию о необходимости выделения полосы пропускания в следующих кадрах с помощью отправки запросов полосы пропускания (ЗПП). Получая ЗПП и учитывая количество буферизованных данных восходящего и нисходящего i трафика, БС выделяет время для» передачи данных- (полосу пропускания) в 1 восходящем подкадре для оконечных станций. Временем регистрации пакета называется интервал времени с момента прихода пакета в очередь ОС до окончания кадра, в котором ЗПП был успешно принят БС. Таким образом, время обслуживания пакета, которое отсчитывается с момента прихода пакета в очередь ОС до получения подтверждения от БС о получении пакета, складывается из с времени регистрации и времени передачи зарегистрированного пакета.

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

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

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

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

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

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

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

4. Исследование эффективности передачи пакетов в зависимости от особенностей физического уровня протокола ШЕЕ 802.16.

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

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

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

2. Аналитическая модель сети с прикреплением запросов полосы пропускания к данным;

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

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

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

Практическая ценность и реализация результатов. Результаты работы внедрены и используются на практике, а также в учебном процессе на базовой кафедре МФТИ (ГУ) в ИППИ РАН «Проблемы передачи и обработки информации», что подтверждено соответствующими актами. В частности, предложенные аналитические модели передачи данных и запросов полосы пропускания использованы при разработке НИР, проводимой ИППИ РАН, по программе Отделения нанотехнологий и информационных технологий РАН «Новые физические структурные решения в инфокоммуникациях».

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

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

- Конференция молодых ученых и специалистов "Информационные технологии и системы" (ИТиС-2009, пос. Бекасово, МО);

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

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

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

Структура и объем диссертационной работы. Диссертация состоит из введения, пяти глав, заключения, списка литературы, включающего 58 наименований. Работа изложена на 101 странице и содержит 33 рисунка и 10 таблиц.

Заключение диссертации по теме «Системы, сети и устройства телекоммуникаций», Лукин, Дмитрий Вадимович

Заключение

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

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

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

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

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

5. Проведен анализ эффективности передачи пакетов в зависимости от особенностей физического уровня протокола IEEE 802.16.

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

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

Список литературы диссертационного исследования кандидат технических наук Лукин, Дмитрий Вадимович, 2010 год

1. В. Вишневский, С. Портной, И. Шахнович. Энциклопедия WiMAX. Путь к 4G. М.: Техносфера, 2009.

2. IEEE Std 802.16-2004 (Revision of ШЕЕ Std 802.16-2001), ШЕЕ Standard for Local and metropolitan area networks, part 16: Air Interface for Fixed Broadband Wireless Access Systems.

3. ШЕЕ Std 802.16-2008 (Revision 2 of ШЕЕ Std 802.16-2001), ШЕЕ Standard for Local and metropolitan area networks, part 16: Air Interface for Fixed Broadband Wireless Access Systems.

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

5. А.И. Ляхов, Д.В. Лукин. Оценка производительности конкурентного доступа в сети IEEE 802.16. М.: Труды семинара Распределенные Компьютерные и Телекоммуникационные Сети: теория и приложения (DCCN-2007), 2007. Т.2, С. 53-58.

6. А.И. Ляхов, Д.В. Лукин. Аналитическая модель передачи данных в сети ШЕЕ 802.16. Автоматика и телемеханика. 2009. № 11. С. 87-100.

7. А.И. Ляхов, Д.В. Лукин. Оценка времени обслуживания пакетов в беспроводной сети под управлением протокола ШЕЕ 802.16. Труды конференции "Информационные технологии и системы" (ИТиС-2009), МО, пос. Бекасово, декабрь 2009, с. 42-47.

8. А.И. Ляхов, Д.В. Лукин. Оценка эффективности прикрепления запросов полосы пропускания к пакетам данных в беспроводной сети под управлением протокола IEEE 802.16. Информационные процессы, 2010. № 2.

9. Ou Yang, Jianhua Lu. A New Scheduling and CAC Scheme for Real-Time Video Application in Fixed Wireless Networks, In CCNC 2006 IEEE, 303-307.

10. C.-H. Jiang, T.-C. Tsai. Token Bucket Based CAC and Packet Scheduling for IEEE 802.16 Broadband Wireless Access Networks", In Proceedings of the CCNC 2006 IEEE, 183-187.

11. S. Chandra, A. Sahoo, An Efficient Call Admission Control for IEEE802.16 Networks, IEEE International Workshop on Local and Metropolitan Area Networks (LANMAN), Princeton, NJ, USA, June 2007.

12. K. Wongthavarawat, A. Ganz. Packet Scheduling for QoS Support in IEEE 802.16 Broadband Wireless Access Systems.

13. K. Wongthavarawat, A. Ganz. IEEE 802.16 Based Last Mile Broadband Wireless Military Networks with Quality of Service Support, In MILCOM 2003 IEEE, 2:779-784.

14. M. Hawa, D. W. Petr. "Quality of Service Scheduling in Cable and Broadband Wireless Access Systems", In Proceedings of International Workshop on Quality of Service (IWQoS) 2002 IEEE:247-255.

15. G. Chu, D. Wang, S. Mei. A Qos Architecture for the MAC Protocol of IEEE 802.16 BWA System, In ICC 2002, Circuits and Systems and West Sino Exposition Proceedings, l(4):435-439.

16. Dong-Hoon Cho, Jung-Hoon Song, Min-Su Kim, Ki-Jun Han. Performance Analysis of the IEEE 802.16 Wireless Metropolitan Area Network, In DFMA 2005 IEEE, 130-136.

17. G. Yangfeng, H. Aiqun. Bandwidth allocation algorithm of VoIP based on the adaptive linear prediction in the IEEE 802.16 system, Proceedings of the 6th International Conference on ITS Telecommunications, pp.16-19, 2006.

18. H. Lee, T. Kwon, D.-H. Cho. An enhanced uplink scheduling algorithm based on voice activity for VoIP services in IEEE 802.16d/e System. IEEE Communications Letters, N9, 2005, pp 691-693.

19. H. Lee, T. Kwon, D.-H. Cho. Extended-rtPS algorithm for VoIP services in IEEE 802.16 systems, Proc. EEEE International Conference on Communications, vol.5, pp.2060-2065, 2006.

20. H. Zhang, Y. Li, S. Feng, W. Wu. A new extended rtPS scheduling mechanism based on multi-polling for VoIP service in IEEE 802.16e system, Proceedings of the IEEE International Conference on Communication Technology, pp. 1—4, Nov. 2006.

21. Bong Joo Kim, Gang Uk Hwang. Performance Analysis of the ertPS Algorithm and Enhanced ertPS Algorithm for VoIP Services in IEEE 802.16e Systems, IEICE TRANS. COMMUN., VOL.E92-B, NO.6 June 2009.

22. Seungwoon Kim, Ikjun Yeom. TCP-aware Uplink Scheduling for IEEE 802.16, IEEE Communications Letters , Vol.11, No. 2, February 2007.

23. X. Bai, A. Shami, K. Meerjal, C. Assi. New Distributed QoS Control Scheme for IEEE802.16 Wireless Access Networks, Proc. 49th IEEE Global Telecommunications Conference (GLOBECOM 2006), San Francisco, California, USA, November 27 December 1, 2006.

24. V. Rangel, Y. Macedo, L. Ortiz, J. Gómez, R. Aquino, A. Edwards. QoS Management for Broadband IEEE 802.16 based Networks in FDD Mode Electronics and Electrical Engineering. Kaunas: Technologija, 2010. No. 2(98). -P. 3-9.

25. Claudio Cicconetti, Alessandro Erta, Luciano Lenzini, Enzo Mingozzi. Performance Evaluation of the IEEE 802.16 MAC for QoS Support, IEEE TRANSACTIONS ON MOBILE COMPUTING, VOL. 6, NO. 1, JANUARY 2007.

26. Jonqyin Sun. Design and Analysis of an ШЕЕ 802.16e-Based OFDMA Communication System, Bell Labs Technical Journal 11(4), 53-73 (2007).

27. Claudio Cicconetti, Luciano Lenzini, Enzo Mingozz. Quality of Service Support in ШЕЕ 802.16 Networks, ШЕЕ Network, March/April 2006.

28. C. Cicconetti, L. Lenzini, E. Mingozzi, A bandwidth request reiteration mechanism for ШЕЕ 802.16 wireless network, Wireless Networks, Vol. 16, No. 3, pp. 731-742, April 2010.

29. Jesús Delicado, Francisco M. Delicado and Luis Orozco-Barbosa, Study of the ШЕЕ 802.16 contention-based request mechanism, Telecommunication Systems, 2008, Volume 38, Numbers 1-2, pp 19-27.

30. D.Chuck, K.Y.Chen, J.M.Chang, A Comprehensive Analysis of Bandwidth Request Mechanisms in ШЕЕ 802.16 Networks, IEEE Transactions on Vehicular Technology, 59 (4):2046-2056, May 2010.

31. Cheng-Yueh Liu and Yaw-Chung Chen, An Adaptive Bandwidth Request Scheme for QoS Support in WiMAX Polling Services, Proceedings of the 2008 The 28th International Conference on Distributed Computing Systems Workshops, pp. 60-65.

32. V. A. Kobliakov, A. M. Turlikov, A. V. Vinel, Distributed queue random multiple access algorithm for centralized data networks. Proceedings of the 10th ШЕЕ Consumer Electronics Society 2006 (pp. 1-6), June 28-01 2006.

33. R. Pries, D. Staehle, D. Marsico. Performance Evaluation of Piggyback Requests in ШЕЕ 802.16, Proceedings, IEEE VTC-2007, Fall, Baltimore, 30 September-3 October, 2007.

34. J.B. Seo, H.W. Lee, C.H. Cho. Performance of ШЕЕ802.16 Random Access Protocol Transient Queueing Analysis, Proc. 49th ШЕЕ Global Telecommunications Conference (GLOBECOM 2006), San Francisco, California, USA, November 27 - December 1, 2006.

35. A. Vinel, Y. Zhang, M. Lott, A. Turlikov. Performance analysis of the random access in IEEE 802.16, In Proceedings of IEEE PIMRC, P. 1596 1600, September2005.

36. A. Vinel, Y. Zhang, Q. Ni, A. Lyakhov. Efficient Request Mechanism Usage in IEEE 802.16, Proc. 49th IEEE Global Telecommunications Conference (GLOBECOM 2006), San Francisco, California, USA, November 27 December 1,2006.

37. A. Vinel, Q. Ni, D. Staehle, A. Turlikov. Capacity Analysis of Reservation-Based Random Access for Broadband Wireless Access Networks, IEEE Journal on Selected Areas in Communications, Vol. 27, №2, 2009.

38. S. Andreev, Z. Saffer, A. Anisimov. Overall Delay Analysis of IEEE 802.16 Network, 2nd International Workshop on Multiple Access Communications (MACOM 2009), Proceedings, Dresden, 2009.

39. Sung-Min Oh and Jae-Hyun Kim, The analysis of the optimal contention period for broadband wireless access network, In proceedings of 3rd IEEE International Conference on Pervasive Computing and Communications (PerCom 2005) workshops, pp. 215-219, 2005.

40. J.B. Seo, H.W. Lee, C.H. Cho. Performance of IEEE802.16 Random Access Protocol Steady State Queuing Analysis Proc. 49th IEEE Global Telecommunications Conference (GLOBECOM 2006), San Francisco, California, USA, November 27 - December 1, 2006.

41. L.-W. Chen, Y.-C. Tseng. Design and Analysis of Contention-based Request Schemes for Best-Effort Traffics in IEEE 802.16 Network, IEEE Communications Letters, Vol. 12, No. 8, Aug. 2008, pp. 602-604.

42. Based CDMA Bandwidth Request Mechanism for the OFDMA Physical Layer. Proceedings of the 12th ACM international conference on Modeling, analysis and simulation of wireless and mobile systems, Tenerife, Canary Islands, Spain, October 2009.

43. Jeong-Jae Won, Choong-Ho Cho, Hyong-Woo Lee, Victor С. M. Leung. Stabilization of Contention-Based CDMA Ranging Channel in Wireless Metropolitan Area Networks, NETWORKING 2005: 1255-1266.

44. Young-June Choi, Suho Park, and Saewoong Bahk, Multichannel Random Access in OFDMA Wireless Networks, IEEE Journal on selected areas in communications, vol. 24, No. 3, March 2006.

45. S. Kwon and D. Cho, CDMA code-based bandwidth request mechanism in IEEE 802.16j mobile multi-hop relay (MMR) systems, in Proceedings of the 68th IEEE Vehicular Technology Conference (VTC '08), pp. 1-5, Calgary, Canada, September 2008.

46. G. Bianchi. Air Performance Analysis of the IEEE 802.11 Distributed Coordination Function // IEEE Journal on Selected Areas in Communications, Vol. 18, №3, 2000. P. 535-548.

47. W. Feller. An Introduction to Probability Theory and Its Applications.Vol.1, N.Y.: John Wiley & Sons, Inc., 1952.

48. B.M. Вишневский, А.И. Ляхов, A.A. Сафонов. Исследование эффективности механизмов синхронизации в беспроводных персональных сетях со сложной структурой. // Информационные технологии и вычислительные системы. 2008. №3. С. 63-77.

49. Р.А. Дунайцев, Е.А. Кучерявый. "Ускоряем Интернет". Сети и телекоммуникации 2004- № 6-7 - с. 46-51.

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

51. Yi Zhou, Kai Chen, Jianhua He, Haibin Guan, Yan Zhang, Alei Liang, Service differentiation in OFDM-based IEEE 802.16 networks, EURASIP Journal on Wireless Communications and Networking, 2009, p. 1-10, January 2009.