Investigation of retrial queue system M|M|1 with phase-type retrial times.pdf В работе рассмотрена RQ-система (Retrial Queueing System) с фазовым распределением повторного времени. Первая международная научная конференция по RQ-системам состоялась в Мадриде в 1998 г. К настоящему времени по этой тематике опубликованы сотни научных работ [1-13]. В монографии [3] список публикаций содержит более 700 наименований. Актуальность этих исследований определяется фундаментальной ролью повторного обращения заявок к обслуживающему прибору в таких реальных обслуживающих системах, как классические телефонные системы [7, 8], колцентры [9], мобильные телефонные системы [10], локальные компьютерные сети, управляемые протоколами случайного множественного доступа [11], и другие коммуникационные системы [12, 13]. Исследование RQ-систем с неэкспоненциальным повторным временем мотивировано реальными компьютерными и телекоммуникационными сетями, в которых повторное время вряд ли экспоненциально. Для RQ-системы M|M| 1 классическую повторную схему мы обобщаем, полагая, что повторное время (время пребывания заявки в источнике повторных вызовов) имеет PH-распределение, или, как его еще называют, распределение фазового типа. 1. Математическая модель В качестве математической модели RQ-системы рассмотрим марковскую однолинейную систему массового обслуживания. Имеется прибор, обслуживающий случайное время, распределенное по экспоненциальному закону с параметром ц. На вход системы поступает пуассоновский поток событий с интенсивностью L Заявка, прийдя из потока, осуществляет попытку захвата прибора. Если прибор свободен, то попытка считается удачной и заявка встает на обслуживание. Если же прибор занят, то заявка отправляется в источник повторных вызовов, где получает случайное время задержки, распределенное согласно PH-закону с параметрами (V, 9), по истечении которого она опять осуществляет попытку захвата прибора. Подробное описание распределения фазового типа см. в [4]. Пусть in(t) - число заявок на n-й фазе PH-распределения, n = 1,2,...Д, а k(t) - определяет состояние прибора как 2014 Обозначим P{k (t) = k, i (t) = i, i2 (t) = i2,..., iN (t) = iN } = Pk (i, i2,.., iN, t) = Pk (i, t), k = 0,1, вероятность того, что в момент времени t прибор находится в состоянии k и в источнике повторных вызовов находится i заявок на каждой из фаз PH-распределения, где i = {i1,i2,...iN}; Процесс{k(t), i(t)} изменений во времени состояний рассматриваемой системы M|M|1|PH является (N+^-мерной цепью Маркова, в которой лишь одна компонента k(t) принимает конечное число значений, а остальные N компонент имеют счетное множество значений. Требуется найти распределение вероятностей значений процесса £ ik - числа заявок в ИПВ. Этот процесс является немарковским, поэтому его исследование выполним методом введения дополнительных компонент, рассматривая (N+^-мерную цепь Маркова {k(t), i(t)}, для стационарного распределения вероятностей Pk (i, t) = Pk (i) которой запишем систему уравнений Колмогорова: N N N N N - (X + £ 0 k,oik + £ £ 0 k Jk )Po(i) + £ (it +1) £ 0 V + ek - О + MPi(i) = 0, 'k ,0' k k=1 k=1 v=1j k v = 1j k N x + Ц + £ik £ (0kjV + 0kj PiQ) + £ (i +1)0 k ,0 Po(i + ek )■ (1) k=1 V=\,VФ k N N N + XP0(i) + £ (ik +1) £ (0k,0Vj + 0kj)P1(i + ek - j + X£ VkPx(i - ek) = 0. k = 1 v = 1j k k = 1 2. Характеристическая функция распределения вероятностей состояний системы Применяя систему уравнений Колмогорова (1), составим систему уравнений для определения частичных характеристических функций H (и) = £ Pk (i)exp{j £ unin}, k = 0,ь i n=1 , а j = V-1 - мнимая единица. Из (1) получим n ан -XH0(u) + ^Hl(u) + j£a±»k,0 d k=1 duk k=1 ouj где и является вектором с компонентами u1,u2,...,uN N ац N + j£irL £ 0k,v(1 -expC;-(uv-uk))) = 0 k v=1,v*k 8Hn -XH1 (u) - ^(u) + XH 0 (u) -j £ -^ k ,0 exp(-X) + ХЦ (u )£ Vk exp(juk) + (2) k=1 duk k=1 n an N + j£~H± £ (0k,v + 0k,0Vv)(1 -exp(j(uv-uk))) = 0. k=1 duk v=1,V#k Уравнения в скалярной форме записи в дальнейшем приводят к довольно громоздким выкладкам. Поэтому осуществим переход к матричной форме записи системы уравнений (2). Для этого введем ряд обозначений: N N u1 0 U = 0 uN dH j (u) du dHj (u) du, dHj (u) duN exp >1 ...! 0 exp( jU) = ... 1 ... 0 ... j exp juN V = [V ... Vn f , E = [1 ... 1]T . Матрица 0 - неполная матрица инфинитезимальных характеристик. Вектор (-0E) имеет смысл интенсивностей обращений заявок к прибору с соответствующей фазы PH-распределения. С учетом матричных обозначений перепишем систему (2) в виде - Щ, (u) + цН (u) - j d^exp{- jU }0 exp(jU )E = 0, du -цН (u) + XH0(u) + Ж1 (u)(VT exp{jU} -1) + j dHo(u)exp{-jU}0E + (3) du + jexp{-jU}(0EVT -0)exp{jU}E = 0. du Система уравнений (3) служит основой для исследования рассматриваемой RQ-системы методом асимптотического анализа. В качестве предельного условия для использования этого метода выбрано условие неограниченно растущего повторного времени. Применение метода асимптотического анализа разбивается на две части - асимптотик первого и второго порядков. Результатом асимптотики первого порядка является вектор средних значений числа заявок в ИПВ на каждой фазе, а результатом асимптотики второго порядка - доказательство того факта, что асимптотическое распределение вероятностей является многомерным гауссовским, и выводится уравнение, определяющее его матрицу ковариаций. 3. Асимптотика первого порядка В системе (3) умножим матрицу 0 на -, где T - большой параметр, T , осуществив тем самым условие растущего времени задержки в ИПВ. Обозначим далее T = e и выполним следующие замены: W = diag(w), u = ew, Hk (u) = Fk (w, e), k = 0,1. С учетом этого перепишем систему уравнений (3) в условиях растущего повторного времени: - XF0(w,s) + M^(w,в) - j dF0(W,S) exp{-JsW}9exp( jeW)E = 0, dw -Fw,s) + XF0(w,s) + XF1(w,s)(VT exp{jsW} -1) + j dF0(W,S) exp{-jsW}9E + (4) dw + j dF1(w,s) exp{-JsW}(QEVt -9)exp{jsW}E = 0. dw Можно доказать следующее утверждение. Теорема 1. Предельные значения Fk (w) решений Fk (w, e) системы уравнений (4) при e ^ 0 определяются как Fk (w) = Rk exp( Jaw), X где R1 = -, R0 + R1 = 1, а вектор средних значений числа заявок на каждой из фаз PH-распределения a Ц определяется равенством a = -XRVT 0-1. (5) R0 Доказательство. В первом уравнении системы (4) осуществим предельный переход e ^ 0 : dF (w) -XF0 (w) + ^ (w) - j-^0E = 0 . dw Будем искать решение в виде Fk (w) = Rk O(w), где R0, R1 - стационарное распределение вероятностей состояний прибора. Тогда получаем -XR + MR - jR0 ^ 0E ф- = о . dw Ф( w) Полагая, что Ф(^) имеет вид O(w) = exp{ jaw}, получим следующее уравнение: -Щ + pR + R0 a0E = 0. Сложим теперь уравнения системы (4) и поделим сумму на s: E + j й^М e-jw (0evt - Q)ej*WE *- = 0 . dw s VTejWE - J e-jW - e-jeW 0ejsW ,dF0(w) +j XFJ(w) dw Раскладывая экспоненты в ряд Тейлора до первой степени порядка малости s, осуществив предельный переход s^ 0, получим равенство \lRVVT + R0 a0 - RJa(0EVT - 0) ] WE = 0, из которого следует, что вектор средних a удовлетворяет уравнению XRJVT + R0a0 - Ra(0EVT - 0) = 0 . Функции F0(w),FJ(w) имеют смысл частичных характеристических функций распределения вероятностей числа заявок в ИПВ для свободного и занятого состояний прибора соответственно. Вместе с условием нормировки для вероятностей R0, RJ последнее уравнение однозначно определяет компоненты вектор-строки средних a, что и есть равенство (5). Теорема доказана. 4. Асимптотика второго порядка В системе (3) умножим матрицу 0 на ^, где T - большой параметр, T ^ж. Теперь обозна- J 2 чим, в отличие от асимптотики первого порядка, ^ = 8 и выполним следующие замены: Hk (u) = H(2) (u) exp {jau}, k = 0,1. Тогда система (3) примет вид -Н»+цН(»-j dH02)(u) , - + jaH0 (u) exp{-jU}0 exp( jU) E = 0, du - цН(2) (u) + Ш02-1 (u) + AHJ2-1 (u)(V exp{jU} - 1) + H2) (2)/ exp{-jU}(0EVT - 0)exp{ jU}E = 0. dH(2)(u) dH0 (u) du + jaHj' (u) + jaH(u) exp{-jU}0E + j +j du Введя замены u = sw, Hk (u) = Fk (w, s), k = 0,1, и подставляя их в последнюю систему, получим dFi(w, s) dw dFj(w, s) -s)--j dz s+jaF0(w, s) exp{-jsW}0 exp( jsW) E = 0, - Fw, s) + ^F)(w, s) + Fw, s)(VT exp{jsW} - 1) + (6) dF0 -0 s + jaFo(w, s) dw dF1 exp{-jsW}0E + j s + jaF1( w, s) +j exp{-jsW}(QEVJ -0)exp{jsW}E = 0. dw Теорема 2. Предельные значения Fk (w) решений Fk (w, s) в системе уравнений (6) при s ^ 0 определяются как Fk (w) = Rk exp J -1ETWKWE1. При этом матрица ковариаций K является решением обратного матричного уравнения Ляпунова KA + ATK = -(B + BT), (7) где A = l(R1QEVT - 0) - R20Ea0, B = R02 [diag(a)0 -diag(a0)]Ea0 - Xdiag(a)(R10EVT -0). Доказательство. Проведем его в три этапа. При этом воспользуемся следующим разложением 1 , 2 Этап 1. В первом из уравнений системы (6) разложим экспоненты в ряд Тейлора вплоть до первой степени порядка малости 8 и, используя разложение (8), получим, группируя слагаемые при степенях 8: при 80 -AR + pR + R0a0E = 0, при 81 -lETWf0 + pETWf1 + R0ETWK0E + aR0(0 W - W0)E + a0E(ETWf) = 0 . (9) Этап 2. Складывая уравнения системы (6), раскладывая экспоненты в ряд Тейлора вплоть до второй степени порядка малости 8, используя разложение и, группируя слагаемые при степенях 8, получим: при 81 : Fk(w) = (Rk + JzEWfk)exp\ --ETWKWE \,k = 0,1. (8) XR1VT + R0a0 - Rla(0EVT - 0) = 0, при 82 : VTWW t t t QW2 T -Щ -2- E-X(ETWfl)VTWE - R0 ETWK QWE - aR (---W QW) E - aQE (ETWf0)WE + (10) E + a(ETWf1)(QEVT -Q)WE = 0. +R1E' WK QEQWE - aR1 WQEVT-QW - (QEV-Q)W2 Этап 3. Выражая из (9) ETWf и подставляя в (10), группируя слагаемые, получим следующее уравнение: -R0ETWKQWE + R0aWQWE + R1EWK(QEVT-Q)WE-R1aW(QEVT -Q)W -R 2 [etWKQE + a(QW - WQ)E]aQWE = 0. В последнем уравнении, переставляя сомножители требуемым образом, получим ETW [K {{RfiEVT -Q) - R02QEaQj + R02 {diag(a)Q - diag(aQ)}EaQ -Xdiag(a)(R1QEVT -Q)] WE = 0, или, что то же самое ETW (.KA + B)WE = 0. (11) Выражение (11) является некоторой квадратичной формой вида xтAx . Для того чтобы она принимала нулевые значения для всех x, достаточно, чтобы матрица A являлась кососимметричной, т.е. AT + A = 0. Применимо к квадратичной форме выражения (11) это означает, что для того, чтобы она принимала нулевые значения для любых матриц W, достаточно, чтобы KA+ATK+B+B =0. При этом решение K = -BAT не является допустимым, так как в этом случае матрица K не является симметричной. Следовательно, матрица ковариаций K многомерного нормального распределения является решением обратного уравнения Ляпунова (7), которое можно свести к системе N2 линейных алгебраических уравнений. Подробнее о методах решения подобных уравнений см. в [14]. 5. Сравнение с имитационным подходом Для рассматриваемой RQ-системы реализована имитационная модель. С ее помощью численно получено распределение вероятностей числа заявок в источнике повторных вызовов. Определим исходные параметры системы следующим образом: -0,30 0,10 0,10 I = 0,70, ц = 1, VT = [0,40 0,25 0,35], 0,10 - 0,20 0,05 0,15 0,15 - 0,60 = 8 при этом параметр 8 = {0,2; 0,1; 0,05; 0,01}. Для заданного набора параметров с помощью имитационной модели получены ряды распределения вероятностей числа заявок в источнике повторных вызовов. Для сравнения с асимптотическими результатами, определяемыми формулами (5) и (7), установим критерий сравнения - расстояние Колмогорова £P(i) -£ g(i). i=1 i=1 Здесь P(i) есть ряд распределения вероятностей, полученный подстановкой целых значений в функцию плотности вероятности нормального распределения, которое получено путем суммирования всех компонент вектора многомерного нормального распределения, а G(i) есть ряд распределения вероятностей, полученный с помощью имитационного моделирования. На графиках (рис. 1-4) приведены гистограммы рядов распределения вероятностей числа заявок в ИПВ, полученных асимптотически (сплошная линия) и имитационно (пунктирная линия) при значениях вышеуказанных параметров. = max Рис. 2. Гистограмма рядов распределения вероятностей числа заявок в ИПВ при 8 = 0,2 Рис. 1. Гистограмма рядов распределения вероятностей числа заявок в ИПВ при 8 = 0,1 Рис. 3. Гистограмма рядов распределения вероятностей числа заявок в ИПВ при 8 = 0,05 Рис. 4. Гистограмма рядов распределения вероятностей числа заявок в ИПВ при 8 = 0,01 Приведем таблицу расстояний Колмогорова для тех же параметров системы, которые соответствуют графикам на рис. 1-4. Значения расстояний Колмогорова d Е d 0,20 0,059 0,10 0,039 0,05 0,030 0,01 0,012 Данные таблицы указывают на то, что при уменьшении параметра s расстояние между асимптотическим и имитационным распределениями вероятностей уменьшается. Полагая допустимым погрешность в 0,05, можно считать, что допустимо применение асимптотических результатов при значении s менее 0,1. Заключение В работе показана возможность гауссовской аппроксимации распределения вероятностей числа заявок в источнике повторных вызовов и получены параметры для данного приближения. Построены графики асимптотического и имитационного распределений вероятностей состояний системы. Приведены табличные данные расстояния Колмогорова между имитационным и асимптотическим распределениями вероятностей в условии неограниченно растущего повторного времени. Сделан вывод о том, что при увеличении повторного времени расстояние между распределениями вероятностей сокращается. Установлена область применимости гауссовской аппроксимации.

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