Arbitrary order asymptotics for МАР|GI|x system under condition ofgrowing intensity of arrival process.pdf Системы массового обслуживания (СМО) с неограниченным числом приборовявляются адекватными математическими моделями реальных систем и процессовв различных предметных областях: экономике, телекоммуникации, сетях связии т.д.Исследованию таких систем массового обслуживания посвящены работы [1 -7]. Многочисленные исследования реальных потоков в различных предметныхобластях, в частности телекоммуникационных потоков, а также потоков в эконо-мических системах, выполненные зарубежными и отечественными специалиста-ми, позволили сделать вывод о существенной неадекватности классических моде-лей (пуассоновских, рекуррентных) реальных потоков. Исследователи, занимаю-щиеся потоками, разработали схемы специальных потоков (поток Кокса, рекур-рентный поток фазового типа, марковский модулированный поток (MMPP), мар-ковский поток однородных событий (MAP), групповой марковский поток одно-родных событий (BMAP)). Также представлены работы по изучению СМО с не-ограниченным числом приборов, на вход которой поступают специальные пото-ки. В работах Д. Баум [8], Л. Брoер [9], были рассмотрены СМО BMAP|GI|,COX|GI|, получено асимптотическое распределение числа занятых приборов вусловии растущего времени обслуживания.В данной работе рассматривается система MAP|GI|. Находится асимптотиче-ское распределение вероятностей числа занятых приборов в системе в условиирастущей интенсивности входящего потока и конечной загрузке. Эти условияимеют принципиальное отличие от условия растущего времени обслуживания.1 Работа выполнена в рамках аналитической ведомственной целевой программы «Развитие научногопотенциала высшей школы (2009 - 2010 годы)», проект № 4761.36 А.Е. Горбатенко1. Метод асимптотического анализаРассмотрим систему массового обслуживания с неограниченным числом при-боров, на вход которой поступает MAP-поток заявок [10, 11], управляемый эрго-дической цепью Маркова k(t), заданной матрицей Q инфинитезимальных характе-ристик qkƒ, набором неотрицательных величины ƒk(1) ≥ 0 и набором вероятностейdkƒ при всех k  ƒ.Продолжительности обслуживания различных заявок стохастически незави-симы, одинаково распределены и имеют заданную функцию распределения B1(x).Для исследования немарковских систем массового обслуживания с неограни-ченным числом приборов предложен метод просеянного потока [10]. Этот методзаключается в том, что в некоторый момент времени t [t0, t1] заявка входящегопотока, поступившая в систему, с вероятностью S1(t) = 1 - B1(t1 - t) формирует со-бытие просеянного потока (рис. 1).S1(t)t0 t1tРис.1. Метод просеянного потокаОбозначим n(t) - число событий просеянного потока, наступивших на интер-вале [t0, t1 ], i(t) - число занятых приборов в системе массового обслуживания намомент времени t.Если в начальный момент времени t0 система свободна, в ней нет заявок, тодля момента времени t1 выполняется равенство:i(t1) = n(t1). (1)Задача исследования системы массового обслуживания сводится к задаче ана-лиза нестационарного просеянного потока n(t) при t0 < t < t1 [12].Двумерный случайный процесс {k(t), n(t)} является нестационарной двумер-ной цепью Маркова [12].Для распределения вероятностейP(k,n,t) = P{k(t)=k,n(t)=n},полагая dkk = 0, нетрудно показать, что P(k, n, t) этой системы удовлетворяет сис-теме дифференциальных уравнений Колмогорова:1(1)1( , , ) { ( , , ) ( )[ ( , 1, ) ( , , )] }( )[ ( , 1, ) ( , , )] .k kkP k n t P nt S t P n t P nt d qtS t P k n t P k n tƒ ƒƒ= ƒ + ƒ − − ƒ ++ − − ƒƒ(2)Начальное условие для решения P(k, n, t) в момент времени t0 определим в виде{ 0( , , ) ( ), 0,0, 0,P k n t R k nn= =>(3)где R(k) - стационарное распределение вероятностей состояния цепи Маркова k(t).Обозначим( )0( , , ) jun ( , , ) ( ) { jun t | ( ) },nH k u t e P k n t R k M e k t k==ƒ = = (4)Асимптотики произвольного порядка 37из (2) и начальных условий (3) получим для этих функций задачу Коши(1)1 10 0 1( , , ) ( , , ){1 ( )( 1) } ( )( 1) ( , , ) ,( , , ) ( ), .ju juk k kH k u t H ut S t e d q S t e HkuttH k u t R k t t tƒ ƒƒ⎧ ⎪ = ƒ + − + − ƒ ⎨⎪⎩ = ≤ ≤ƒ (5)Задача исследования системы массового обслуживания сводится к нахожде-нию распределения вероятностей ( ) ( , , 1 )kP n = ƒP k n t , где распределениеP(k,n,t1) определяется функциями H (k,n,t1 ) .Поставленную задачу будем решать в асимптотическом условии растущей ин-тенсивности входящего МАР-потока.Условием растущей интенсивности МАР-потока будем называть соотношения(1) , ƒk =N⋅ƒk N, (6)определяющие большие значения интенсивности потока.С учетом (6) систему (5) перепишем в виде1 10 0 1( , , , ) ( , , , ){1 ( )( 1) } ( )( 1) ( , , , ) ,( , , , ) ( ), .ju juk k kH k u t N H u t N S t e d q S t e H k u t N NtH k u t N R k t t tƒ ƒƒ⎧ ⎪ = ƒ + − + − ƒ ⎨⎪⎩ = ≤≤ƒ (7)Для системы массового обслуживания будем рассматривать условие конечнойзагрузки:b(1) =bN,N  (8)и равномерной ограниченности (1) (1)ƒk ⋅b ≤C−const условных загрузок, где(1) ( ( ))10b 1 B x dx=  − - среднее время обслуживания заявки.В заданных условиях найдем асимптотическое распределение вероятностейчисла занятых приборов в системе массового обслуживания произвольного по-рядка.2. Асимптотика первого порядкаАналогично [13] обозначим ƒ = 1/ƒ и в задаче (7) с учетом (8) выполним сле-дующие замены:t , S1 (t) S( ),H(k,u,t,N) F(k,u, , )Nƒ= = ƒ = ƒ ƒ , (9)получим0 0 1( , , , ) ( , , , ){1 ( 1) } ( )( 1) ( , , , ) ,( , , , ) ( ), ,ju juk k kF k u F u e d q S e FkuF k u R kƒ ƒƒ⎧ ƒƒ ⎪ = ƒ ƒ ƒ ƒ + − + ƒ − ƒ ƒ ƒ ƒ ⎨⎪⎩ ƒ ƒ = ƒ ≤ ƒ ≤ ƒƒ (10)где ƒ0=t0N, ƒ1= t1N .Теорема 1. Если управляющая МАР-потоком цепь Маркова k(t) имеет конеч-ное число состояний, то для решения F(k, u,ƒ, ƒ) задачи (10) существует предел0 1lim F(k,u, , ) F (k,u, )ƒƒ ƒ = ƒ, (11)38 А.Е. Горбатенкогде функция F1(k, u,ƒ) имеет вид( )01( , , ) ( )exp ( ju 1)F k u R k e k S x dxƒƒ⎧⎪ ⎪⎫ ƒ = ⎨ − ƒ ⎬⎩⎪ ⎭⎪ . (12)Доказательство. В соответствии с теоремой Пуанкаре [14] об аналитическойзависимости решения от параметра можно утверждать, что существует предел(11).В задаче (10) выполним предельный переход при ƒ0, для F1(k,u,ƒ) получимследующую задачу:111 0 0 1( , , )( )( 1) ( , , ) ,( , , ) ( ), .jukF k u S e F kuF k u R k⎧ ƒ = ƒ − ƒ ƒ ⎪⎨ƒ⎩⎪ ƒ = ƒ ≤ ƒ ≤ ƒ(13)Отметим, что при таком предельном переходе задача Коши (10) для системыдифференциальных уравнений обращается в совокупность задач Коши (13) неза-висимых дифференциальных уравнений. Из задач Коши (13) функции F1(k,u,ƒ)определяются равенствами (12).Теорема доказана.Следствие 1. Асимптотическое распределение вероятностей числа событий,наступивших в просеянном потоке до момента времени t, имеет следующий вид:( ) 00( )1( , ) 1 ( )!tktt n Sx dxkk tP n t R k S x dx en⎛ ⎞ −ƒ = ⎜ƒ ⎟⎜ ⎟⎝ ⎠ƒ  . (14)Доказательство. Просуммируем (12) по k и, выполнив обратную к (9) заменуƒ = tƒ, получим( ) ( )01( , , ) ( )exp ( 1) ,tjukk k tF k u R k e S x dx h u t⎧⎪ ⎪⎫ ƒ = ⎨ − ƒ ⎬=⎩⎪ ⎪⎭ƒ ƒ  , (15)где h(u,t) - асимптотическая при ƒ0 (ƒ) функция, аналогичная характеристи-ческой, числа наступивших событий в просеянном потоке до момента времени t.Разложив экспоненту в ряд, получим следующее равенство:( ) 00( )0, () 1 ( )!tktt n Sx dxjunkn k th u t e R k S x dx en −ƒ=⎛ ⎞ = ⎜ƒ ⎟⎜ ⎟⎝ ⎠ƒ ƒ  . (16)Для достаточно малых ƒ (больших N) выполняется приближенное (асимптоти-ческое) равенство:H(k,u,t) = F(k,u,ƒ,ƒ) ≈ F(k,u,ƒ). (17)С другой стороны, H(k,u,t) определяется равенством (3). Также просуммировав(4) по k, получим0 0( , ) ( , , ) jun ( , , ) jun ( , )k n k nH u t H k u t e P k n t e P n t = ==ƒ =ƒ ƒ =ƒ . (18)Просуммировав по k (17), в силу (15), получим следующее асимптотическоеравенство:H(u,t) ≈ h(u,t).Асимптотики произвольного порядка 39Из полученного асимптотического равенства, в силу (16) и (18), получим (14),где P(n,t) ≈P1(n,t).Следствие 1 доказано.Следствие 2. Асимптотическое стационарное распределение вероятностейчисла занятых приборов в системе имеет следующий вид:( )( )1( )!kikkP i R k eiƒ −ƒ= ƒ , (19)где ( ( ))0k kb,b 1 B x dxƒ = ƒ =  − .Доказательство. В (14) положим t = t1 = 0 и t0  − , получим( ) ( ) ( )00 ( )1( ,0) 1 ( ) 1! !kkn S x dxn bk kk kP n R k S x dx e R k b en n−−ƒ−ƒ−⎛ ⎞ = ⎜⎜ƒ ⎟⎟ = ƒ⎝ ⎠ƒ  ƒ .В силу условия (1)P1(n,0) = P1(i,0) = P1(i).Таким образом, асимптотическое стационарное распределение вероятностейчисла занятых приборов в системе имеет вид (19), где P(i) ≈ P1(i) .Следствие доказано.Распределение вероятностей P1(i) является взвешенной суммой с весами R(k)пуассоновских распределений, поэтому рассматриваемое распределение можетбыть многомодальным [11].3. Асимптотика произвольного порядкаАппроксимацию первого порядка можно существенно уточнить, рассматриваяасимптотики более высокого порядка, полагая11( ) ( ) s ( )ssP i P i f i>= +ƒƒ .Под асимптотикой n-го порядка будем понимать асимптотическое распределе-ние вероятностей числа занятых приборов в системе массового обслуживания, ко-торое находится по следующей формуле:0( ) ( )nsssP i f i== ƒƒ , (20)где ( ) 1 ( )2juifsi eFsuduƒ−ƒ=ƒ  , (21)s( ) s( , ,0)kFu= ƒFku , при ƒ = ƒ1 = 0 и ƒ0  − .Для нахождения функций Fs(k,u,ƒ) , решение F(k,u,ƒ,ƒ) задачи (10) запишемв виде разложения10( , , , ) s ( , , )ssF k u F k u+=ƒ ƒ = ƒƒ ƒ. (22)40 А.Е. ГорбатенкоТеорема 2. Для функций Fs(k,u,ƒ) имеет место рекуррентное равенство{ }01( , , ) 1 ( )( 1) ( , , )exp ( 1) ( ) , 1.jus k k sjukzF k u q S z e d F u ze Sx dx dz sƒ+ ƒ ƒƒ ƒƒƒ = + − ƒ ⎧⎪ ⎪⎫  ⎨ − ƒ ⎬ >⎩⎪ ⎪⎭ƒ  (23)Доказательство. Подставим разложение (22) в задачу (10), получим{ }110 011 ƒ1 00( , ,ƒ)ƒ ( )( 1) ( , , )ƒƒ (ƒ, ,ƒ) 1 (ƒ)( 1) ,( , , ) ( ).s s ju sk ss ss jus k kssssF kuS e F kuF u S e d qF ku Rk ++= =+ ƒ ƒ=+=⎧ ⎪ = ƒ ƒ − ƒ ƒ +  ⎪⎪+ + − ⎨⎪⎪ƒ ƒ = ⎪⎩ƒ ƒƒ ƒƒПриравнивая коэффициенты при одинаковых степенях ƒ при s > 0 ,для Fs+1(k,u,ƒ) получим следующие задачи Коши:1 { }11 0( , , )( )( 1) ( , , ) ( , , ) 1 ( )( 1) ,( , , ) 0,s ju juk s s k ksF kuS e F ku F u S e d qF ku++ ƒ ƒƒ+⎧ ƒ ⎪ = ƒ − ƒ ƒ + ƒ ƒ + ƒ −ƒ ⎨⎪⎩ ƒ =ƒв которых системы распадаются на совокупность независимых задач Коши длянеоднородных уравнений и с нулевыми начальными условиями. Решение этихзадач имеет вид (23).Теорема доказана.Получим явный вид для функций Fs(k,u,ƒ) . Применим метод математическойиндукции, для этого подставим (12) в (23) при s = 1, полученное выражение под-ставим в (23) при s = 2 и т.д. В результате получим следующее равенство:{ } 1 21 11 1 0 0 01 11 , ,1 1( , , ) ( ) 1 ( )( 1)s sl l l lss z z zsjus s s k k l k kk k l z z zlF k u z R k q S z e d−+ +−− −= =⎛ ⎞ ⎧= ⎜ ⎟⋅ ⎨ + − ⎝ ⎠ ⎩ƒ…ƒ ƒ  … ƒ11 2 11exp ( 1) ( )llls zjuk s sl ze Sx dx dz dz dz−− −=⎧⎪ ⎪⎫  ⎨ − ƒ ⎬⎩⎪ ⎪⎭ƒ  … , (24)где zs = ƒ,z0= ƒ0.Просуммируем по ks (24), полагая ƒ = ƒ1 = 0 и ƒ0  - , найдём функцию{ }( )1 21 11 111 0 11 , ,1 111 2 11( ) ( , , )( ) 1 ( )( 1)exp ( 1) ( ) .ssl l l ls sls l sls s s sks z z sjuk k l k kk k k l ls zjuk k k s sl zF u F k u zR k q S z e de b S x dx dz dz dz−+ +−−− −= − − − =−− −== =⎛ ⎞ ⎧= ⎜ ⎟⋅ ⎨ + − ⎝ ⎠ ⎩⎧⎪ ⎡ ⎤⎫⎪  ⎨ − ⎢ƒ + ƒ − ƒ ⎥⎬⎩⎪ ⎣⎢ ⎦⎥⎭⎪ƒƒ ƒ ƒ ƒ    ƒƒ … …… (25)Асимптотики произвольного порядка 41Подставим (25) в (21), а затем, воспользовавшись разложением (20), найдемасимптотику n-го порядка.4. Область применимости асимптотических результатовк допредельной ситуацииВыше были получены формулы, позволяющие найти асимптотическое распре-деление числа занятых приборов. Допредельное распределение можно получить спомощью имитационного моделирования [15, 16]. Остается выяснить, насколькорезультаты, полученные с помощью асимптотического анализа, близки к резуль-татам имитационного моделирования системы массового обслуживания в допре-дельной ситуации. Для этого рассматривается имитационная модель данной сис-темы и строятся оценки ( )^P i значений вероятностей числа заявок в системе. Пооценкам значений вероятностей числа заявок в системе строятся следующие ве-личины:( ) ( )^ ^0, 0,1, 2,...imF i P m i==ƒ =и находится расстояние Колмогорова:( ) ( )^s max s iƒ = F i −F i ,где ( )^Fi - функция распределения, полученная с помощью имитационного моде-лирования, Fs (i) - функция распределения, полученная с помощью асимптоти-ческого анализа.Пусть0,03 0,02 0,010,03 0,04 0,010,04 0,02 0,06Q⎧− ⎫ =⎪ − ⎪ ⎨ ⎬⎪⎩ − ⎭⎪,0 0,3 0,70,5 0 0,5 ,0, 4 0,6 0d⎧⎪ ⎪⎫ = ⎨ ⎬⎩⎪ ⎭⎪ƒ(1) = N{2 7 18}.Время обслуживания заявок распределено по равномерному закону наинтервале [0, 2 b(1)], где b(1) = 2/N. В этом случае значения величины ƒs, s = 1, 2,составили:N 30 50ƒ1 0.0182 0.0144ƒ2 0.0163 0.0127На рис. 2 показаны распределения вероятностей числа занятых приборов (чис-ла заявок в системе), полученных с помощью имитационного моделирования иасимптотического анализа.42 А.Е. Горбатенко0 10 20 30 40 50 60 i0,020,040,060,080,10P i ( )имит. модел.асимптотика 1асимптотика 20 10 20 30 40 50 60 i0,020,040,060,080,10P i ( )имит. модел.асимптотика 1асимптотика 2Рис. 2. Распределение вероятностей числа занятых приборов в системеЗаключениеВ данной работе рассмотрена система массового обслуживания МАР|GI|. Спомощью метода просеянного потока и метода асимптотического анализа найденаасимптотика произвольного порядка. Сравнив полученные асимптотические рас-пределения первого и второго порядка с результатами имитационного моделиро-вания, можно сказать, что точность полученного асимптотического распределе-ния достаточно велика, так как расстояние Колмогорова не более 0,02. Получен-ное распределение также является многомодальным. Это имеет принципиальноезначение при численных реализациях, так как условием останова для численныхалгоритмов обычно является достижение определенного достаточно малого зна-чения вероятности, которое может достигаться в окрестности некоторого локаль-ного минимума.ЛИТЕРАТУРА1. Decreusefond L., Moyal P. A functional central limit theorem for the M/GI/ queue // Ann.Appl. Probab. 2008. V .18. No 6. P. 156 - 178.2. Tsoukato K.P., Makowski A.M. Heavy Traffic Analysis for A Multiplexer Driven byM/GI/infinity Input Processes [Электронный ресурс]. URL: http://handle.dtic.mil/100.2/ADA4555833. Van Doorn E.A., Jagers A. A. A Note on the GI/GI/infinity system with identical service andinterarrival-time distributions // J. Queueing Systems. 2004. No. 47. P. 45 - 52.Асимптотики произвольного порядка 434. Pang G., Whitt W. Two-Parameter Heavy-Traffic Limits for Infinite-Server QueuesProbability Surveys. 2008. V. 0. P. 1 - 56.5. Shore H. Simple Approximations for the GI/G/c queue // J. Operational Research Society.1988. No. 39. P. 279 - 284.6. Baykal-Gursoy M., Xiao W. Stochastic Decomposition in M/M/ queues with MarkovModulated Service Rates. Queueing Systems // Theory and Applications. 2004. V. 48. P. 75 -88.7. Baltzer J.C. On the fluid limit of the M/G/ queue queueing systems // Theory andApplications. 2007. V. 56. P. 255 - 265.8. Baum D., Kalashnikov V. No-Waiting stations with spatial arrival processes and customermotion // Информационные процессы. 2002. Т. 2. № 2. C. 143 - 145.9. Breuer L., Baum D. The Inhomogeneous BMAP/G/infinity Queue // MMB. 2001. P. 209 -223.10. Назаров А.А., Моисеева А.А. Метод асимптотического анализа в теории массового об-служивания. Томск: Изд-во НТЛ, 2006. 112 с.11. Гнеденко Б.В., Коваленко И.Н. Введение в теорию массового обслуживания. М.: Наука,2007. 336 с.12. Назаров А.А., Терпугов А.Ф. Теория вероятностей и случайных процессов: учеб. посо-бие. Томск: Изд-во НТЛ, 2006. 204 с.13. Горбатенко А.Е., Назаров А.А. Исследование системы МАР|GI| в условии растущейинтенсивности входящего потока // Теория вероятностей, случайные процессы, матема-тическая статистика и приложения: сб. науч. статей Международной научной конфе-ренции. Минск: Издательский центр БГУ, 2008. C. 52 - 56.14. Эльсгольц Л.Е. Дифференциальные уравнения и вариационное исчисление. М.: Наука,1969. 424 с.15. Марголис Н.Ю., Терпугов А.Ф. Имитационное моделирование случайности: учебно-справочное пособие. Томск: Изд-во Том. ун-та, 2003. 63 с.16. Шеннон Р. Имитационное моделирование систем. М.: Мир, 1978.Горбатенко Анна ЕвгеньевнаТомский государственный университетE-mail: anngo86@mail.ru Поступила в редакцию 21 ноября 2009 г

Скачать электронную версию публикации