Регенеративное оценивание и его применение к системам с конечным буфером тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат физико-математических наук Некрасова, Руслана Сергеевна

• Некрасова, Руслана Сергеевна
• кандидат физико-математических наук
• 2012

Оглавление диссертации кандидат физико-математических наук Некрасова, Руслана Сергеевна

Введение

Глава 1. Элементы теории регенерации.

1.1. Предварительные результаты

1.2. Процессы восстановления.

1.3. Регенерирующие процессы.

1.4. Среднее по времени.

1.5. Предельное распределение регенерирующего процесса.

1.6. Процессы накопления.

Глава 2. Регенеративное оценивание среднего по времени

2.1. Задачи оценивания стационарных характеристик.

2.2. Регенеративное оценивание в дискретном времени.

2.3. Регенеративное оценивание в непрерывном времени.

2.4. Достаточное условие применимости РМ

2.5. Оценивание среднего на конечном интервале.ЗС

Глава 3. Регенеративный анализ систем с потерями.

3.1. Некоторые аналитические результаты.

3.2. Регенеративная структура систем с потерями.

3.3. Соотношение между вероятностью потери и вероятностью простоя

Глава 4. Регенеративный анализ систем с повторными вызовами

4.1. Модель системы с повторными вызовами.

4.2. Стационарность.

4.3. Ренеративная структура систем с повторными вызовами.

4.4. Предельная вероятность блокировки

4.5. Вероятность занятости.

4.6. Система с N классами заявок.

Глава 5. Имитационное моделирование систем с конечным буфером

5.1. Асимптотика Р 103$ при растущем буфере.

5.2. Потери на цикле занятости при р — 1.

5.3. Альтернативная оценка: Р^ь как функция Р^.

5.4. Исследование эффективности /с-регенераций.

5.5. Регенеративное оценивание Рогь в системе Е.

5.6. Оценка допредельной вероятности занятости в системе £

5.7. Анализ систем с двумя орбитами

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

Актуальность работы. Стохастические модели телекоммуникационных систем обслуживания в настоящее время имеют широкое распространение [8, 14, 18. 20, 41]. Предел среднего по времени значения случайного процесса является важной стационарной характеристикой при анализе таких систем. Если рассматриваемый случайный процесс регенерирует, то возможно построить несмещенные и состоятельные оценки требуемой стационарной характеристики на основе центральной предельной теоремы. В силу независимости и стохастической эквивалентности циклов, регенерирующие процессы охватывают широкий класс случайных процессов [15, 26], что позволяет рассматривать регенеративный метод как один из наиболее мощных методов исследования. В частности, независимость длин циклов регенерации обеспечивает возможность использования развитого аппарата теории восстановления для теоретического анализа процессов, а также классических методов для построения оценок при имитационном моделировании [9. 26. 52] и статистическом анализе [7. 62, 63].

Модели с ограничениями, в частности, с конечным буфером играют важную роль в анализе современного телетрафика [32. 54]. В таких моделях поток, образованный потерянными заявками, часто является входным потоком для другого узла коммуникационной системы, а вероятность переполнения является ключевым показателем качества обслуживания. К потерям относится та часть поступающей нагрузки, которая не обслуживается из-за занятости обслуживающих устройств или переполнения буферов, предназначенных для ожидания в очереди. Отмстим, что теоретический анализ систем обслуживания, как правило, затрагивает марковский случай [21. 23. 60|. Однако регенеративная структура позволяет анализировать и оценивать предельные характеристики, в частности, стационарную вероятность переполнения для широкого класса немарковских процессов. В этом состоит одно пз основных преимуществ регенєративного метода.

Степень разработанности. Регенеративный метод оценивания стационарных характеристик в полной мере изложен в книгах С. Асмуссена [26], М. А. Крэйна и О. Д. Лемуана [56]. Также стоит отметить работы П. Глинна, Д. Иглхарта и В. Витта. касающиеся статистического анализа регенеративных систем, условий применимости регенеративного метода, эффективности регенеративных оценок.

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

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

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

3. Анализ условий стационарности систем с повторными вызовами, построение оценок основных характеристик на основе регенеративного метода в стационарном и нестационарном режимах.

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

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

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

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

На защиту выносятся следующие основные результаты и положения:

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

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

3. Получены необходимые условия стационарности систем с повторными вызовами и несколькими классами заявок (несколькими орбитами).

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

Апробация работы. Основные результаты диссертации докладывались на следующих конференциях: Международный научный семинар "Advances in Methods of Information and Communication Technology" (19-20 мая 2009 г. Петрозаводск); Международный научный семинар "Advances in Methods of Information and Communication Technology" (25-26 мая 2010 г. Петрозаводск): Международный семинар "Applied Problems in Theory of Probabilities and Mathematical Statistics related to modeling of information systems" в рамках конгресса ICUMT'10 (18-20 октября 2010 г. Москва); Modern Probabilistic Methods for Analysis and optimization of Information and Telecommunication Networks ("Современные вероятностные методы анализа и оптимизации информационно-телекоммуникационных сетей, 21-я Белорусская школа-семинар по теории массового обслуживания) (3-5 февраля 2011 г. Минск): Международный семинар "Northern Triangular seminar 2011" (11-13 апреля 2011 г. Санкт-Петербург); Международный научный семинар "Advances in Methods of Information and Communication Technology"' (28 апреля 2011 г. Петрозаводск): V Международный семинар "Прикладные задачи теории вероятностей и математической статистики, связанные с моделированием информационных систем" (10-16 октября 2011 г. Светлогорск); Международный научный семинар "Advances in Methods of Information and Communication Technology" (15-16 мая 2012 г. Петрозаводск): VIII Международная Петрозаводская конференция "Вероятностные методы в дискретной математике" (2-9 июня 2012 г. Петрозаводск); 9-й международный семинар ''9th International workshop on retrial queue" (28-30 июня 2012 г. Севилья).

Публикации.

Материалы диссертации опубликованы в 9 печатных работах, из них 3 статьи в журналах [6, 11. 12] (в том числе 2 работы в изданиях из перечня российских рецензируемых журналов [11. 12]). 3 статьи в сборниках трудов конференций [28. 48, 49] и 3 тезиса докладов [29. 47. 58]. Получено свидетельство о регистрации электронного ресурса [13].

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

Структура и объем диссертации. Диссертация состоит из введения, 5 глав, заключения, списка сокращении, библиографии, списка иллюстративного материала и приложения. Общий объем диссертации 124 страницы, из них 110 страниц текста, включая 16 рисунков и 10 таблиц. Библиография включает 79 наименований па 8 страницах.

Заключение диссертации по теме «Математическое моделирование, численные методы и комплексы программ», Некрасова, Руслана Сергеевна

Заключение

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

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

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

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

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

Список условных сокращений с в. 1 - с вероятностью 1 с. в. - случайная величина с. п. - случайный процесс н. о. р. с. в. — независимые одинаково распределенные случайные величины РИ - равномерная интегрируемость

- стохастическое равенство (по распределению) УЗБЧ — Усиленный Закон Больших Чисел н. и. Р. — непосредственная интегрируемость по Риману п. в. - почти всюду

ЦПТ — Центральная Предельная Теорема ц. р. - цикл регенерации м. р. — момент регенерации а Л Ь - тіп(а, Ъ)

РМ - регенератиный метод

N(0,1) - нормально распределенная случайная величина с нулевым математическим ожиданием и единичной дисперсией

Список литературы диссертационного исследования кандидат физико-математических наук Некрасова, Руслана Сергеевна, 2012 год

1. Байхельт Ф., Франкен П. Надежность и техническое обслуживание. Математический подход. М.: Радио и связь, 1988. С. 392.

2. Биллингсли П. Сходимость вероятностных мер. М.: Наука, 1977. С. 352.

3. Боровков А. А. Теория вероятностей. 2 изд. М.: Наука, 1986. С. 432.

4. Бочаров П. П., Печинкин А. В. Теория массового обслуживания. М.: РУДН, 1995. С. 529.

5. Гнеденко Б. В., Коваленко И. Н. Введение в теорию массового обслуживания. М.: Наука, 1987. С. 336.

6. Горичева Р. С., Морозов Е. В. Регенеративное моделирование вероятности потери в системах обслуживания с конечным буфером //' Труды карельского научного центра РАН. 2010. № 3. С. 20-29.

7. Ермаков С. М., Мелас В. Б. Математический эксперимент с моделями сложных стохастических систем. Санкт-Петербург: С.-Петербургский университет, 1993. С. 269.

8. Иглехарт Д. Л., Шедлер Д. С. Регенеративное моделирование сетей массового обслуживания. М.: Радио и связь, 1984. С. 136.

9. Крэйн М. А., Лемуан О. Д. Введение в регенеративный метод анализа моделей. М.: Наука, 1982. С. 104.

10. Морозов Е. В., Делгадо Р. Анализ стационарности регенеративных систем обслуживания /'/ Автоматика и телемеханика. 2009. С. 42-58.

11. Морозов Е. В., Некрасова Р. С. Оценивание вероятности блокировки в системе с повторными вызовами и постоянной скоростью возвращения заявок с орбиты // Труды карельского научного центра РАН. 2011. № 5. С. 63-74.

12. Морозов Е. В., Некрасова Р. С. Об оценивании вероятности переполнения конечного буфера в регенеративных системах обслуживания // Информатика и ее применения. 2012. Т. 6, № 3. С. 90-98.

13. Рыков В. В. Аналитические методы исследования систем массового обслуживания // Техническая кибернетика. 1983. Т. 6. С. 13-20.

14. Рыков В. В. Исследование одпоканальной системы общего вида методом регенерирующих процессов. Исследование основных процессов на периоде регенерации // Техническая кибернетика. 1984. Т. 1. С. 126-132.

15. Севастьянов Б. А. Теория восстановления. Итоги науки и техники. Теория вероятностей. Математическая статистика. Теоретическая кибернетика. М.: ВИНИТИ, 1973. Т. 11. С. 128.

16. Тихоненко О. М. Модели массового обслуживания в системах обработки информации. Минск: Университетское. 1990. С. 148.

17. Уолрэнд Д. Введение в теорию сетей массового обслуживания. М.: Мир, 1993. С. 336.

18. Феллер В. Введение в теории вероятностей и ее приложения. 2е изд. М.: Мир, 1964. Т. 2. С. 765.

19. Яшков С. Ф. Анализ очередей в ЭВМ. М.: Радио и связь, 1989. С. 216.

20. Abramov V. М. Stochastic Inequalities for Single-Server Loss Queueing Systems // Stochastic Analysis and Applications. 2006. Vol. 24. P. 1205-1221.

21. Abramov V. M. Takacs' Asymptotic Theorem and Its Applications: A Survey // Acta Applicandae Mathematica 2008. Pp. 609-651.

22. Andradottir S., Calvin J. M., Glynn P. W. Increasing the frequency of regeneration for rnarkov processes // Stanford University, technical Report. 1994. Pp. 94-10.

23. Artalejo J. R. Stationary analysis of the characteristics of the M/M/2 queue with constant repeated attempts / / Operation search. 1996. Vol. 33. Pp. 83-95.

24. Artalejo J. R., Gomez-Corral A. Neuts M. F. Analysis of multiserver queues with constant retrial rate // European Journal of Operational Research. 2001. Vol. 135. Pp. 569-581.

25. Asmussen S. Applied Probability and Queues. 2nd edition. New-York: Wiley, 2003. P. 476.

26. Asmussen S., Glynn P. W. Stochastic Simulation Algorithms and Analysis. New-York: Springer, 2007. P. 476.

27. Avrachenkov K., Morozov E., Nekrasova R., Steyaert B. On stability of a two-class retrial system with constant retrial rate // Proceedings of "9t,h International workshop on retrial queues" 2012. 2012. Pp. 15-16.

28. Avrachenkov K., Morozov E. V. Stability analysis of GI/G/c/K Retrial Queue with Constant Retrial Rate // INRIA(Sophia Antipolis), Research Report. 2010. Vol. 7335.

29. Avrachenkov K., Yechiali U. Retrial networks with finite buffers and their application to Internet data traffic // Probability in the Engineering and Informational Sciences. 2008. Vol. 22. Pp. 519 536.

30. Berger A. W , Whitt W. Comparisons of multi-server queues with finite waiting rooms // Commun. statist.-stochastic models. 1992. Vol. 8(4). Pp. 719-732.

31. Bertsekas D., Gallager R. Data Networks. Prentice-Hall International. 1992. Vol. 2.

32. Billingsley P. Convergence of probability measures. 2 edition. New-York: John Wiley, 1999. P. 669.

33. Bratley P., Fox B. L., Schrange L. E. A guide to simulation. 2 edition. New-York: Springer-Verlag, 1987. P. 397.

34. Choi B. D., Park K. K., Pearce C. E. iVI. An M/M/l retrial queue with control policy and general retrial times /'/ Queueing Systems. 1993. Vol. 14. P. 275-292.

35. Choi B. D., Rhee K. H., Park K. K. The M/G/l retrial queue with retrial rate control policy // Probability in the Engineering and Informational Sciences. 1993. Vol. 7. Pp. 29-46.

36. Fayolle G. A simple telephone exchange with delayed feedback // Teletraffic Analysis and Computei Performance Evaluation. 1986. Vol. 7. Pp. 245-253

37. Glynn P. W. Some topics in regenerative steady-state simulation /'/ Acta Appli-candae Mathematicae. 1994. Vol. 34. Pp. 225-236.

38. Glynn P. W., Iglehart D. L. A joint central limit theorem for the sample mean and regenerative variance estimator // Annals of operation researh. 1987. Vol. 8. Pp. 41-55.

39. Glynn P. W., Iglehart D. L. Simulation methods for queues: an overview // Queueing systems. 1988. Vol. 3. Pp. 221-237.

40. Glynn P. W. Iglehart D. L. Conditions for applicability of the regeneration method // Managment Sci. 1993. Vol. 39. Pp. 1108-1111.

41. Glynn P. W., Whitt W. A central-limit-theorem version // Queueing systems. 1986. Pp. 191-215.

42. Glynn P. W. Whitt W. Sufficient conditions for functional-limit-theorem versions // Queueing systems. 1987. Pp. 279-287.

43. Glynn P. W., Whitt W. Limit theorems for cumulative processes // Stochastic Processes and their applications. 1993. Pp. 299-314.

44. Glynn P. W., Whitt W. Logarithmic asymptotics for steady-state tail probabilities in a single-server queue // Adv. Appl. Prob. 1994. Pp. 131-156.

45. Goricheva R. S. Regenerative approach for retrial queuing system // Third Northern Triangular seminar. Programme and abstracts. 2011. Pp. 9-10.

46. Goricheva R. S., Morozov E. V. Regenerative simulation of finite buffer queuing systems / ' Proceedings of AMICT'2009. 2009. Vol. 11. Pp. 88-98.

47. Gut A. Stopped Random Walks. Springer, 1988. P. 263.

48. Gut A. Anscombe's theorem 60 years later // Department of Mathematics Uppsala University, Research Report. 2011. Vol. 14. P. 24.

49. Kalashnikov V. V. Regenerative queueing processes and their qualitive and quantitative analysis // Queueing Systems. 1990. Vol. 6. Pp. 113-136.

50. Kang W., Shahabuddin P., Whitt YV. Exploting Regenerative Structure to estimate finite time averages via simulation // ACM. 2006. Vol. 5. Pp. 1-38.

51. Kelly F. P. Loss Networks // The Annals of Applied Probability. 1991. Vol. 1, No. 3. Pp. 319-378.

52. Kiefer J., Wolfowits J. On the theory of queues with many servers // Trans. Amer. Math. Soc. 1955. Vol. 78. Pp. 1-18.

53. Law A. M., Kelton YV. D. Simulation modeling and Analysing. 2 edition. New-York: McGraw-Hill, 1991. P. 759.

54. Morozov E. V. Weak regeneration in modeling of queueing processes / / Queueing Systems. 2004. Vol. 46. Pp. 295-315.

55. Ramalhoto M. F., Gomez-Corral A. Some decomposition formulae for M/M/r/r+d queues with constant retrial rate // Stochastic Models. 1998. Vol. 14. Pp. 123-145.

56. Righter R. A note on loses in M/GI/l/n queues // Journal of Applied probability. 1999. Vol. 36. Pp. 1240-1243.

57. Serfozo R. Applied stochastic processes. Springer, 2009.

58. Shedler G. S. Regeneration and Networks Queues. New-York: Springer-Verlag, 1987. P. 224.

59. Shedler G. S. Regeneration Stochastic Simulation. Boston: Academic Press, 1993. P. 400.

60. Sherman R., Taqqu M., Willinger W. Wilson D. Self-Similarity Through Iiigh-Variability: Statistical Analysis of Ethernet LAN Traffic at the Source Level // IEEE/ACM Transactions on Networking. 1997. Vol. 5. Pp. 71-86.

61. Sigman K. One-dependant regenerative processes and queues in continious time // Math. Oper. Res. 1990. Vol. 15. Pp. 175-189.

62. Sigman K., Thorisson H., Wolff R. W. Note of existence of regeneration times // Tech. Rep. 1992.

63. Sigman K., Wolff R. W. Review of regenerative processes // SIAM Review. 1993. Vol. 35. Pp. 269-288.

64. Smith W. L. Regenerative stochastic processes // Proc. Royal Soc. Ser. A. 1955. Vol. 232. Pp. 6-31.

65. Smith W. L. Renewal theory and Its remifications // Journal of the Royal Statistical Society. 1958. Vol. 20. Pp. 243-302.

66. Sonderman D. Comparing multi-server queues with finite waitng rooms, I: Same number of servers // Advances in Applied Probability. 1979. Vol. 11. Pp. 439-447.

67. Sonderman D. Comparing multi-server queues with finite waiting rooms, II: Different number of servers //' Advances in Applied Probability. 1981. Vol. 11. Pp. 448-455.

68. Spricant R., Whitt W. Variance reduction in simulations of loss models // Operation research. 1999. Vol. 47. Pp. 509-523.

69. Takagi H. Queueing analysis. N.Holland: Finite systems, 1993. Vol. 2. P. 487.74. van der Vaart A. W. Asymptotic Statistics. Cambridge University Press, 1998. P. 462.

70. Whitt VV. Comparing counting processes and queues // Advanced in applied probability. 1981. Vol. 13, no. 1. Pp. 207-220.

71. Whitt W. Comparing counting processes and queues // Advances in Applied Probability. 1981. Vol. 13. Pp. 207-220.

72. Whitt W. A review of L — AW and extensions // Queueing Systems. 1991. Vol. 9. Pp. 235-268.

73. Wolff R. W. Stochastic Modeling and the Theory of Queues. Prentice-Hall, 1989. P. 556.

74. Wolff R. W. Loses per cycle in a single-server queue // J. Appl.Prob. 2002. Pp. 905-909.1. Список иллюстраций

75. Доверительное оценивание Р/„АЛ в системе М/М/3/0 при р = 1.5. 90

76. Зависимость Р/oss от величины буфера п в системе M/M/4/n прир — 4,06. 90

77. Доверительное оценивание P/0iS в системе М/Pareto/1/3 при р = 1. 92

78. Доверительное оценивание Р¡oss в системе М/Pareto/3/0 при р =1,5. 94

79. Доверительное оценивание Рioss в системе Pareto/М/2/0 при р = 6,67. 95

80. Доверительное оценивание Рioss на основе к — 0,3,6 регенераций, в системе М/М/2/4 при р/т — 0,5 . 96

81. Зоны стацнонарности/неотационарности системы вида М/М/1/0при Л = 1. 98

82. Зоны стационарности/нестационарности системы вида М/М/2/0при Л = 1. 99

83. Области малой (р < 1) и большой (р > 1) загрузки в зоне нестационарное™ системы вида М/М/1/0 при Л = 1.102

84. Области малой и большой загрузки в зоне нестационарности системы вида М/Pareto/1/0 при Л = 0. 5.104

85. Дисперсии оценок в системе М/Pareto/1/0 при Л = 0,5, до =0.15, cv = 3.107

86. Области стационарности/нестационарпости системы видаМ/М/1/0с двумя классами при Ai = 0, 5, Л2 = 4.109

87. Динамика орбит в системе вида М/М/I/O с двумя классами при

88. Г^ = 1,94, Г<2> = 0,4, д = 10.110

89. Динамика орбит в системе вида М/М/1/0 с двумя классами при

90. Г^ = 1,97, Г(2) = -0,15, д = 10.110

91. Динамика орбит в системе вида М/М/1/0 с двумя классами при

92. Г^ = 2,52, Г^2) = -1, 25, (1 = 10.110

93. Динамика орбит в системе вида М/М/1/0 с двумя классами при

94. Г^ = -1, 25, Г<2> = -8. ¡1 = 2. 5.111

95. А.1 Свидетельство о регистрации электронного ресурса.124