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

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

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

Введение

1 Принципы построения и особенности широкополосных беспроводных региональных сетей.

1.1 Широкополосные беспроводные сети.

1.2 Семейство протоколов IEEE 802.

1.2.1 Архитектура и основные понятия.

1.2.2 Уровень управления доступом к среде семейства протоколов IEEE 802.11. Распределенная функция координации (DCF).

1.2.3 Централизованная (PCF) и гибридная (HCF) функции координации.

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

2 Аналитическая модель радиосоты, работающей в режиме „последняя миля".

2.1 Основные понятия и классификация систем поллинга.

2.2 Аналитическая модель радиосоты в режиме „последняя миля". 56 2.2.1 Математическая модель.

2.2.2 Получение стационарного распределения состояний системы.

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

3 Аналитическая модель радиосоты, работающей в режиме „сбор данных".

3.1 Математическая модель.

3.2 Стационарное распределение состояний системы.

3.3 Определение характеристик производительности.

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

4.1 Сравнение аналитических результатов с результатами имитационного моделирования.

4.2 Оптимизация параметров схем Адаптивного Динамического Поллинга.

4.3 Сравнение характеристик радиосоты при децентрализованном и при адаптивном динамическом централизованном управлениях.

4.4 Программная реализация результатов работы.

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

Объект исследования и актуальность темы. В последние годы беспроводные сети передачи данных заняли прочные позиции в повседневной жизни. Сфера их применения простирается от обеспечения взаимодействия между бытовыми приборами (например, между телефоном и телефонной гарнитурой, компьютером и монитором и т.д.) до построения сетей передачи мультимедийной информации городского и регионального масштаба. Построение беспроводных сетей передачи данных регионального масштаба на обширных территориях (например, в удаленных сельских регионах Российской Федерации) является единственным экономически оправданным и наиболее перспективным решением проблемы так называемого „информационного неравенства". При создании беспроводных сетей передачи данных регионального масштаба все большее распространение получают устройства на базе технологий IEEE 802.11 (WiFi). Активный рост числа беспроводных региональных сетей выдвигает в ряд первоочередных задач разработку методов оптимизации их работы, разработку новых алгоритмов функционирования таких сетей, а также оценку их производительности. Проблемам разработки математических моделей сетей передачи данных посвящено значительное количество работ. Среди наиболее известных работ, посвященных этим проблемам, следует отметить работы российских и зарубежных ученых: О.М. Брехова, В.А. Васенина, В.М. Вишневского, B.C. Жданова, P.A. Минлоса, A.B. Печинкина, В.К.

Попкова, B.B. Рыкова, С.Н. Степанова, 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, J. Weinmiller. Особенности региональных беспроводных сетей при оценке их производительности достаточно полно отражены в ряде работ, однако недостатками этих работ является, слабое внимание, уделяемое механизмам адаптивного централизованного управления, хотя именно эти механизмы нацелены на решение основной проблемы региональных беспроводных сетей — проблемы „скрытых станций". Таким образом, задача анализа, разработки и оптимизации механизмов адаптивного динамического управления является одной из важнейших для развития беспроводных широкополосных региональных сетей передачи данных. Кроме этого, требуется разработать комплекс аналитических и имитационных моделей механизмов централизованного управления для получения адекватных оценок показателей производительности и оптимизации устройств широкополосной беспроводной региональной сети.

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

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

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

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

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

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

Научная и практическая ценность. Результаты работы внедрены и используются на практике, что подтверждено соответствующими актами. Изученные и предложенные механизмы адаптивного централизованного управления реализованы в радиомаршрутизаторе РЭС „Рапира", который был разработан ИППИ РАН в рамках Федеральной целевой научно-технической программы „Исследования и разработки по приоритетным направлениям развития науки и техники" на 2002-2006 годы по Государственному контракту 02.477.11.1003 „Разработка технологии создания нового поколения широкополосных телекоммуникационных средств комплектации беспроводных систем передачи данных, голоса и информации". Радиомаршрутизатор РЭС „Рапира" используется в качестве базового устройства в ряде широкополосных беспроводных региональных сетей, в том числе в сети 11ас1юНе1 ИППИ РАН, в беспроводной локальной вычислительной сети ИППИ РАН, в беспроводной сети ООО „Уникомпорт", в беспроводной сети ЗАО „НТЦ ФИОРД" и т.д. РЭС „Рапира" более года успешно работает в составе комплексной сети УФСБ по Амурской области, используемой для охраны государственной границы Российской Федерации с республикой Китай. Результаты, полученные в ходе решения задачи оптимизации работы широкополосной беспроводной сети, позволяют максимально эффективно использовать пропускную способность радиосоты региональной сети, что применялось при разработке, реализации и эксплуатации беспроводных сетей, перечисленных выше, а также опорной беспроводной сети г. Обнинск. Результаты диссертационной работы используются в учебном процессе Московского Физико-Технического Института при чтении лекций по курсу „Основы инфокоммуникационных технологий" и в лабораторных работах.

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

• Международной конференции по информационным сетям, системам и технологиям (МКИССиТ-2002, Санкт-Петербург);

• Международном семинаре „Распределенные компьютерные и телекоммуникационные сети. Теория и приложения" (DCCN-2005, София, Болгария.);

• Третьей международной конференции по проблемам управления Института проблем управления (МКПУ III - 2006, Москва);

• Международном семинаре „Распределенные компьютерные и телекоммуникационные сети. Теория и приложения" (DCCN-2006, София, Болгария.);

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

Публикации. По теме диссертации опубликовано 9 научных работ, список которых приведен в конце автореферата. Кроме того, получены 2 свидетельства об официальной регистрации программ для ЭВМ, и 1 патент на полезную модель.

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

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

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

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

Заключение

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

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

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

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

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

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

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

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

3. Вишневский В.М. Беспроводные сети широкополосного доступа к ресурсам Интернета // Электросвязь. 2000. №10. С. 9-13.

4. Vishnevsky V.M., Lyakhov A.I. Adaptive features of IEEE 802.11 Protocol: utilization, tuning and modifications // Proc. of 8th HP-OVUA Conf. Berlin, June 2001.

5. Баканов A.С., Вишневский В.M., Ляхов A.И. Метод оценки показателей производительности беспроводных сетей с централизованным управлением // АиТ. 2000. №4. С. 97-105.

6. Вишневский В.М., Ляхов А.И., Гузаков Н.Н. Оценка максимальной производительности беспроводного доступа в Интернет // АиТ. 2004. т. С. 52-70.

7. Лаконцев Д.В., Семенова О.В. Математические модели централизованного управления в беспроводных сетях IEEE 802.11 / Распределенные компьютерные и телекоммуникационные сети (DCCN-2005). М.: Техносфера, 2005. С. 77-83.

8. Vishnevsky V.M., Lyakhov A.I., Guzakov N.N. An adaptive polling strategy for IEEE 802.11 PCF // Proc. 7th Int. symp. on Wireless Personal Multimedia Communications (WPMC'04). Abano Terme, Italy, September 12-15, 2004. V. 1. P. 87-91.

9. Мацнев Д.Н. Разработка методов исследования протокола МАС-уровня беспроводных региональных сетей RadioEthernet: Дис. к.т.н. М., 2004 103с.

10. И. Столлингс В. Беспроводные линии связи и сети. : Пер. с англ. // М.: Издательский дом „Вильяме", 2003.

11. IEEE 802.11, The working Group for Wireless LANs // http: / / grouper.ieee.org/groups /802/11/index.html.

12. Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications // ANSI/IEEE Std 802.11, 1999 Edition.

13. Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications. Amendment 4: Further Higher Data Rate in the 2.4

14. GHz Band // IEEF Std 802.11g-2003 (Amendment to IEEE Std 802.11, 1999 Edition).

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

16. 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.11b-1999 (Supplement to ANSI/IEEE Std 802.11, 1999 Edition).

17. Borst S. C. Polling systems. Amsterdam: Stichting Mathematisch Centrum, 1996.

18. Chang K.-H. First-come-first-served polling systems // Asia-Pacific J. Oper. Res. 2001. V. 18. No. 1. P. 1-11.

19. Takagi H. Analysis and applications of polling models / Performance Evaluat: Origins and Directions. Ed. Haring G., Lindemann Ch., Reiser M. Lecture Notes Comput. Sci. 2000. V. 1769. P. 423-442.

20. Takagi H. Analysis of polling systems. MIT Press, 1986. 175 p.

21. Takagi H. Queueing analysis of polling models: an update / Stochastic Analysis of Computer and Communication Systems. Ed. Takagi H. Amsterdam, North-Holland, 1990. P. 267-318.

22. Takagi H. Queueing analysis of polling models: progress in 1990-1994 / Frontiers in Queueing, ed. Dshalalow J.H., CRC, Boca Raton, FL, 1997. P. 119-146.

23. Levy H., Sidi M. Polling systems: applications, modeling and optimization 11 IEEE Trans. Commun. 1990. V. 38. No. 10. P. 1750-1760.

24. Bruneel H., Kim B G. Discrete-time models for communication systems including ATM. Boston: Kluwer Academic Publishers, 1993.

25. Grillo D. Polling mechanism models in communication systems -some application examples. / Stochastic Analysis of Computer and Communication Systems. Ed. Takagi H. Amsterdam, North-Holland, 1990. P. 659-698.

26. Takagi H. Applications of polling models to computer networks // Comput. Networks ISDN Syst. 1991. V. 22. No. 3. P. 193-211.

27. Bing B. Wireless local area networkss: the new wireless revolution. Wiley-Interscience, 2002.

28. Ziouva E., Antonakopoulos T. Improved IEEE802.il PCF performance using silence detection and cyclic shift on stations polling // IEE Proc. Commun. 2003. V. 150. No. 1. P. 45-51.

29. Ziouva E., Antonakopoulos T. Efficient voice communications over

30. EE802.il WLANs using improved PCF procedures // Proc. Third Int. Work Conf. INC 2002/07.

31. Ziouva E., Antonakopoulos T. Improved IEEE802.il PCF performance using silence detection and cyclic shift on stations polling // IEE Proc. Commun. 2003. V. 150. No. 1. P. 45-51.

32. Adán I.J.B.F., Boxma O.J., Resing J.A.C. Queueing models with multiple waiting lines // Queueing Syst. 2001. V. 37. No. 1-3. P. 65-98.

33. Bruno R., Conti M., Gregory E. Bluetooth: architecture, protocols and scheduling algorithms // Cluster Comput. 2002. V. 5. P. 117-131.

34. Kopsel A., Ebert J.-P., Wolisz A. A performance comparison of point and distributed function of an IEEE 802.11 WLAN in the presence of real-time reqiurements // Proc. Inf. Workshop MoMuc2000-Waseda. Japan. October 2000.

35. Olsen T.L., van Der Mei R.D. Polling systems with periodic server routing in heavy-traffic: renewal arrivals // Oper. Res. Lett. 2005. V. 33. No. 1. P. 17-25.

36. Qiao D., Choi S., Soomoro A., Shin K.G. Energy-efficient PCF operation of IEEE 802.11a Wireless LAN // Proc. of INFOCOM 2002. New York, June 2002.

37. Levy H., Sidi M., Boxma O.J. Dominance relations in polling systems // Queueing Syst. 1990. V. 6. No. 2. P. 155-171.

38. Khalid M., Vyavahare P.D., Kerke H.B. Analysis of asymmetric polling systems // Comput. Oper. Res. 1997. V. 42. No. 4. P. 317-333.

39. Miorandi D., Zanella A., Pierobon G. Performance Evaluat of Bluetooth polling schemes: an analytical approach // ACM Mobile Networks and Appl. 2004. V. 9. No. 2. P. 63-72.

40. Altman E., Blanc H., Khamisy A., Yechiali Y. Gated-type polling systems with walking and switch-in times // Commun. in Stat.: Stochastic Models. 1994. V. 10. No. 4. P. 741-763.

41. Singh M.P., Srinivasan M.M. Exact analysis of the state-dependent polling model // Queueing Syst. 2002. Vol. 41. P. 371-399.

42. Eisenberg M. The polling system with a stopping server // Queueing Syst. 1994. Vol. 18. P. 387-431.

43. Giinalay Y., Gupta D. Polling system with patient server and state-dependent setup times // HE Transactions. 1997. V. 29. No. 6. P. 469-480.

44. Giinalay Y,, Gupta D. Threshold start-up control policy for polling systems // Queueing Syst. 1998. V. 29. No. 2-4. P. 399-421.

45. Gupta D., Srinivasan M.M. Polling systems with state-dependent setup times // Queueing Syst. 1996. V. 22. No. 3-4. P. 403-423.

46. Fricker C., Jaibi M.R. Monotonicity and stability of periodic polling models // Queueing Systems, Theory and Applications. 1994. Vol. 15, No. 3. P. 211-238.

47. Fuhrmann S.W., Cooper R.B. Stochastic decompositions in the M/G/l queue with generalized vacations // Operations Research. 1985. Vol. 33, No. 5. P. 1117-1129.

48. Schriber T.J. Simulation using GPSS. John Wiley & Sons, 1974.

49. Liu Z., Nain P., Towsley D. On optimal polling policies // Queueing Syst. 1992. V.ll. No. 1-2. P. 59-83.

50. Boxma O.J., Levy H., Weststrate J.A. Efficient visit orders for polling systems // Performance Evaluat. 1993. V. 18. No. 2. P. 103-123.

51. Boxma O.J., Levy E., Weststrate J.A. Efficient visit frequencies for polling tables: minimization of waiting cost // Queueing Syst. 1991. V. 9. No. 1-2. P. 133-162.

52. Feng W., Kowada M., Adachi K. A two-queue model with Bernoulli service schedule and switching times // Queueing Syst. 1998. V. 30. No. 3-4. P. 405-434.

53. Feng W., Kowada M., Adachi K. Analysis of a multi-server queue with two priority classes rnd (M,N)-threshold service schedule I: non-preemptive priority // Int. Trans. Oper. Res. 2000. V. 7. No. 6. P. 653-671.

54. Feng W., Kowada M., Adachi K. Performance analysis of a two-queue model with an (M, ^-threshold service schedule // J. Oper. Res. Soc. Japan. 2001. V. 44. No. 2. P. 101-124.

55. Feng W., Kowada M., Adachi K. Two-queue and two-server model with a hysteretic control service policy // Sci. Math. Japonicae. 2001. V. 54. No. 1. P. 93-107.

56. Fischer M.J., Harris C.M., Xie J. An interpolation approximation for expected wait in a time-limited polling system // Comput. Oper. Res. 2000. V. 27. No. 4. P. 353-366.

57. Foss S., Kovalevskii A. A stability criterion via fluid limits and its application to a polling system // Queueing Syst. 1999. V. 32. No. 1-3. P. 131-168.

58. Foss S., Last G. On the stability of greedy polling systems with general service policies // Prob. Engineering Inform. Sei. 1998. V. 12. No. 1. P. 49-68.

59. Foss S., Last G. Stability of polling systems with exhaustive service policies and state-dependent routing // Ann. Appl. Prob. 1996. V. 6. No. 1. P. 116137.

60. Fournier L., Rosberg Z. Expected waiting times in cyclic service systems under priority disciplines // Queueing Syst. 1991. V. 9. No. 4. P. 419-439.

61. Frigui I., Alfa A.S. Analysis of a discrete time table polling system with MAP input and time-limited service discipline // Telecommunication Syst. 1999. V. 12. No. 1. P. 51-77.

62. Frigui I., Alfa A.S. Analysis of time-limited polling system // Comput. Commun. 1998. V. 21. No. 6. P. 558-571.

63. Fuhrmann S. W. A decomposition result for a class of polling models // Queueing Syst. 1992. V. 11. No. 1-2. P. 109-120.