Asymptotical analysis of queueing system MMPP|M|N with feedback.pdf Обратная связь в контексте систем массового обслуживания понимается как повторное обращение заявки к обслуживающему устройству. Считается, что качество предоставленного обслуживания определяется интенсивностью повторного обращения заявок. Клиент может вернуться в систему за повторным обслуживанием по разным причинам: качественное первичное обслуживание, как гарантия качества последующих обращений или, наоборот, прерванное обслуживание или по каким-либо причинам не удовлетворяющее требованиям клиента. Самым очевидным примером таких систем являются сети коммуникации, при использовании которых искажение данных приводит к повторному отправлению данных адресату. В исследуемых системах существует два типа обратной связи, которые называют мгновенной и отсроченной обратной связью. После завершения обслуживания заявка может покинуть систему или потребовать повторного обслуживания мгновенно. Отсроченная связь реализуется посредством отправки заявки на орбиту, где она ожидает повторного обращения к обслуживающему устройству в течение случайного времени. Одни из первых публикаций, представляющих результаты исследований систем с повторными обращениями, принадлежат Л. Такачу [1, 2]. В них исследованы одноканальные системы массового обслуживания с неограниченной очередью и орбитой методом производящих функций. Исследования Такача в свое время были уникальными в данной тематике, и после его работ длительное время новые публикации не появлялись. В последние три десятилетия СМО с обратной связью активно исследуются. Отметим, что в [1, 3-10] представлены результаты исследований СМО с мгновенной обратной связью, а в [2, 11-21] изучены СМО с отстроченной, или отложенной, обратной связью. Также ряд работ [22-25] посвящен исследованию систем с обоими типами связей (в [22] имеется обзор публикаций до 2015 г.). Основная задача исследования систем массового обслуживания с обратной связью заключается в получении распределения вероятностей для многомерных цепей Маркова, представляющих математический смысл моделей. При исследовании моделей умеренной размерности с этой задачей помогают справиться программные средства, основанные на решении балансовых уравнений [26-27]. Также, используя различные подходы в решении основной задачи, ученые применяют матричногеометрический метод [28] и спектральный метод [29], а также их модификации. Следует отметить, что в использовании вышеуказанных методов встречаются и достаточно серьезные вычислительные проблемы, что серьезно повышает сложность решения. В настоящей работе при изучении СМО с мгновенной и отложенной обратной связью использован метод асимптотического анализа. 1. Математическая модель и постановка задачи Рассмотрим систему массового обслуживания с N обслуживающими устройствами и обратной связью (рис. 1). На вход системы поступает MMPP-поток заявок, заданный диагональной матрицей условных интенсивностей Л = [ХА], к = 1,2,...,К, матрицей инфинитезимальных характеристик Q = ], i j = 1,2,... , N , управляющей цепи Маркова k(t) =1,2,..., K . Рис. 1. СМО вида MMPP|M|N с обратной связью Fig. 1. Queueing system MMPP|M|N with feedback При поступлении в систему заявка занимает свободный прибор, где получает обслуживание в течение случайного времени, распределенного экспоненциально с параметром ц. Если в момент поступления в систему заявка обнаружит прибор занятым, она немедленно отправляется на орбиту, где осуществляет задержку в течение случайного времени, экспоненциально распределенного с параметром о. В момент окончания обслуживания заявка может покинуть систему с вероятностью r0, отправиться на повторное обслуживание, осуществляя мгновенную обратную связь, с вероятностью r1, отправиться на орбиту, осуществляя отсроченную обратную связь с вероятностью r2, где она задерживается в течение случайного времени, экспоненциально распределенного с параметром о, после чего требует повторного обслуживания. Если в момент поступления заявки с орбиты устройство оказывается свободным, то она занимает его в течение случайного времени, которое имеет экспоненциальное распределение с тем же параметром ц. Иными словами, первичные (заявки, которые поступают извне) и повторные заявки (заявки, которые поступают с орбиты) являются идентичными по времени их обслуживания, т.е. первичные и повторные заявки в приборах не различаются. Если в момент поступления повторной заявки с орбиты все приборы заняты, то она остается на орбите для повторения своего запроса. Предполагается, что возможны многократные повторения запросов для обслуживания, т.е. не имеется ограничений на число повторений обслуживания. Обозначим k(t) = k - состояние цепи Маркова, управляющей MMPP-потоком в момент времени t, k =1,2,...,K , n(t) - число занятых приборов в системе в момент времени t, n = 0,1,..., N , i(t) -число заявок на орбите в момент времени t. Ставится задача получения трехмерного стационарного распределения вероятностей P (k, n, i) = P[k (t) = k, n (t) = n,i (t) = i J. 2. Система уравнений Колмогорова Рассмотрим трехмерный марковский процесс {k(t),n(t),i(t)} , для его стационарного распределения вероятностей P{k(t) = k,n(t) = n,i(t) =i}= P(k,n,i) запишем систему уравнений Колмогорова: -(^ + (1 - r )пц + iG)P(k, n, i) + XkP(k, n -1, i) + +(i + 1)cP(k, n -1, i +1) + (n + 1)r pP(k, n +1, i) + +(n + 1)r pP(k, n +1, i -1) + ^ ^P(v, n, i) = 0,0 < n < N -1, -(Xt + (1 - r kN\\x)P(k, N, ik + \\P(k, N -1, i) + +XkP(k, N, i -1) + (i + 1)cP(k, N -1, i +1) + ^ qvtP(v, N,i) = 0. V Введем частичные характеристические функции вида H (k, n, u) = e]j'P(k, n, i), i = 0 где j = •$/-! мнимая единица. Тогда можем переписать систему (1): -(X - k + пц(1 - r ))H(k, n, u) + XkH(k, n -1, u) + jc dH(k’ n u) + du +(n + 1)ц(г0 + re )H(k, n +1, u) - jce-ju dH(k, n -1 u) + 02 +Z qvkH(v, n,u) = 0,0 < n < N -1, v (Xk (eu -1) - nm(1 - r))H(k, N, u)+ +XpPkk, N -1,u) - jp-p dH(k,P -1 u) ■ У qvkk(v,k,u) = 0. du (2) Обозначим вектор-строки H(n,u) ={H(1,n,u),..., H(K,n,u)}, dH(n,u) _ (dH(1,n,u) dH(K,N,u)\\ du du ’ ’ и перепишем (2) в матричном виде с учетом введенных обозначений: H(n, u)(Q - Л - иц(1 - r )I) + H(n -1, u)A + jc dH(n u) + 1 +(n + 1)ц(г0 + r2eju )H(n +1, u) - jce-P dH(n -1 u) = 0,0 < n < N -1, 02 H( N, u)(Q - (1 - e]u )Л - Рц(1 - r )I) + H(n -1, u)A --jce-Ju dH(p -1,u) = 0, du здесь I - единичная матрица размерности K x K. Введем следующие векторные обозначения: H(u)={H(0,u),H(1,u),...,H(N,u)}, dH(u) _ jdH(0, u) dH(1,u) dH(N, u) j du du ’ du ’ ’ du ’ и перепишем уравнения (3) в новой матричной форме: H(u)(A + eu b) + /n'H(ui(iii du - eiu I,) = 0, где "Q - Л Л 0 0 МГД Q - Л -pI(r0 + r2) Л 0 0 2PIr0 Q - Л - 2pI(r0 + r2 )) ... 0 0 0 0 Q- Л- -N plCr, + Г2)) _ ■ 0 0 0 0 ■ pI/j 0 0 0 B= 0 2pIr2 0 0 , 0 0 0 0 0 0 NpIr Л ’ 1 0 ... 0 0 ’ ■ 0 1 0 .. .0 0 ■ 0 1 ... 0 0 0 0 1 .. .0 0 I0= 0 0 ... 1 0 ,I1 = 0 0 0 .. .0 1 0 0 ... 0 0 0 0 0 .. .0 0 5 на единичный Умножим матричное уравнение (A + B)e = 0 и (Io - It )e = 0, получим вектор-столбец e, принимая во внимание H(u)Be + jce-u dH(u) Ioe = 0. du Таким образом, матричная система (3) и скалярное уравнение примут вид: H(u)(A + eub) + jcdH-)(Ii -e-uI,) = 0, du H(u)Be + jce-ju dH(u) Ioe = 0. du0 Будем искать решение задачи (4) методом асимптотического анализа в условии большой за держки заявки на орбите, т.е. G^0. (4) 3. Метод асимптотического анализа Обозначим c = s и выполним следующие замены в (4): u = sw, H(u) = F(w, s). (5) С учетом замен (5) перепишем уравнения (4): F(w, s)(A + ejSWB) + j dFWs) (Ie - e-iwI1) = 0, dw F(w,s)Be + je-jsw dF(w, s) dw I0e = 0. (6) Для решения системы (6) в условии s 0 особо важными являются следующие утверждения. Теорема 1. В рассматриваемой системе с обратной связью в предельном условии 0 предельная характеристическая функция нормированного числа i(t) заявок на орбите имеет вид: lim M\\e"'( )} = ejw, (Т) где значением параметра к является положительный корень x = к скалярного уравнения R( x )(B - xI0 )e = 0, (8) где вектор-строка R = {R(0),R(1),...,R(N)} - распределение вероятностей числа занятых приборов в системе, является решением системы уравнений r{(A + B) -x(I0 -I,)} = 0, Re =1. (9) Доказательство. Рассмотрим первое равенство в системе (6) в предельном условии £^0, обозначим limF(w,s) =F(w) и получим Е^0 F(-)(A + B) + j ^F(W)(Io - I,) = 0. (10) -w Будем искать решение F( w) системы (10) в виде F(w) = ReJwx, тогда получим следующую систему уравнений: r{(A + B) -x(Io -I,)} = 0, Re = 1, (11) что совпадает с (9) из формулировки теоремы. Так как F(w)e = ejwx, необходимо найти значение x =к из (7). Рассмотрим теперь второе равенство (6) в предельном условии s 0: F(w)Be + j Ioe = 0, ow и подставим решение в виде F(w)= Rejwx , тогда R(x)(B -xI )e =0. (12) Таким образом, значением параметра к является решение последнего скалярного уравнения, что совпадает с (8). Для дальнейшего исследования системы с обратной связью в (4) выполним замену J - к H(u) = e v H(2)(u), получим систему oH(2)(u) H(2)(u)(A + euB-K(Io -e-JuIi)) + jv--^-1 (Io -e-JuIi) = 0, ou -H(2) (u) H(2) (u)(Be - Ke’JuIoe) + e-ju jv-----(-) Ioe = 0. o-u o Обозначим v = s2 и выполним в (13) следующие замены: u = sw,H(2)(u) = F(2)(w,s), получим F(2) (w, s)(A + eJswB - k(I0 - e-Jsw^1)) + -F(2)(w,s) (Io-e-jswI1) =0, +j s---- -w -F(2) (w, s) F(2) (w, s)(Be - Ke-^Ioe) + ej js----Ioe = 0. o-w o (13) (14) (15) Основным результатом исследования рассматриваемой системы является следующее утверждение. Теорема 2. Предельная характеристическая функция центрированного и нормированного числа заявок на орбите в рассматриваемой системе с обратной связью имеет вид: j’w/a(/(/)--) (jw) к2 limM{e о} = Ф(>) = e 2 2, 0^0 где i

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