Asymptotic analysis retrial queueing system with exclusion customers and phase follow-up.pdf В связи с тем, что в современном мире наблюдается ежегодное увеличение объема и размерности информационных данных, проблема проектирования и анализа телекоммуникационных систем является одним из приоритетных направлений развития любой страны. Система с повторными вызовами (RQ-система) - это модель массового обслуживания, которая характеризуется тем, что заявка, пришедшая в систему, если обнаружит прибор занятым, повторит попытку обращения для обслуживания через некоторое случайное время, в течение которого находится на орбите в зоне ожидания. В литературе показано, что такие модели являются адекватными математическими моделями телекоммуникационных сетей связи. Между повторами заявки (клиенты, требования) находятся на орбите. Первые системы с повторными вызовами были рассмотрены R.I. Wilkinson [1]. Наиболее полное и глубокое исследование разнообразных процессов в RQ-системах было приведено в работах Г.И. Фалина [2]. Одной из важных характеристик системы массового обслуживания является процесс обслуживания. В данной работе предлагается обслуживание в два этапа. На первом этапе прибор обрабатывает входящие заявки (первичная обработка), и после обслуживания на первой фазе заявки отправляются на вторую (фактическое обслуживание). Задачи, возникающие в системах управления и требующие двухфазного обслуживания, были предложены B.T. Doshi [3]. K.C. Madan [4] были рассмотрены системы массового обслуживания M/G/1, где заявка после обслуживания на первой фазе может покинуть систему или перейти на вторую фазу обслуживания. В работе B. Krishna Kumar [5] рассматривается система, в которой заявки, прибывшие в систему, вытесняют заявки, находящиеся только на первой фазе, и при этом обслуживающиеся в тот момент требования фактически покидают систему без обслуживания. Как правило, рассматриваются системы, в которых все требования однотипные, хотя в реальных системах некоторые должны претендовать на первоочередное обслуживание, т.е. на приоритет. Системам с приоритетами посвящено большое количество исследований, например работы K. Avrachenkov [6], G. Ayyappan, A. Muthu Ganapathi [7], П.П. Бочарова, О.И. Павловой [8], I.M. Atencia [9], C. Kim [1q], A.N. Dudin [11]. Литература по RQ-системам очень обширна. Некоторые обзоры моделей можно найти у J.R. Artalejo [12-13]. В данной работе будет рассмотрена RQ-система с повторными вызовами, фазовым дообслуживанием и вытеснением заявок. 29 А.А. Назаров, Я.Е. Измайлова 1. Математическая модель и постановка задачи Рассмотрим RQ- систему M/GI/1 с вытеснением заявок и обслуживанием заново (рис. 1). Рис. 1. RQ-система M/GI/1 с вытеснением заявок Fig. 1. Retrial queueing system M/GI/1 with exclusion customers Описание модели приведено в работе [14]. Показано, что пропускная способность RQ-системы с вытеснением заявок и обслуживанием их заново имеет вид S = B'(0), где B(x) - функция распределения времени обслуживания. Откуда для времени обслуживания, распределенного по закону Эрланга, получаем S = 0 . То есть стационарного режима в такой системе не существует. Поэтому рассмотрим RQ-систему с вытеснением заявок и фазовым дообслуживанием (рис. 2). Рис. 2. RQ-система M∕E2∕1 с вытеснением заявок и дообслуживанием Fig. 2. Retrial queueing system M/E2/1 with exclusion customers and phase follow-up На вход системы с повторными вызовами поступает простейший поток заявок, имеющий интенсивность λ. Если пришедшая заявка застает прибор свободным, то она занимает его для обслуживания на первой фазе. Время обслуживания на первой фазе имеет экспоненциальное распределение с параметром μ1. После успешного окончания обслуживания на первой фазе заявка переходит на вторую фазу обслуживания. Время обслуживания на второй фазе имеет экспоненциальное распределение с параметром μ2. Если в момент прихода заявки прибор оказывается занятым, то заявка, которая пришла, вытесняет обслуживаемую заявку и встает на прибор. Заявка, вытесненная мгновенно, переходит на орбиту в зону ожидания. Орбита условно разделяется на две зоны. Если заявка обслуживалась на первой фазе, то она уходит в первую зону орбиты, если на второй фазе, то во вторую. В зонах орбиты заявки осуществляют случайную задержку. Продолжительность таких задержек имеет экспоненциальное распределение с параметром σ. С орбиты после случайной задержки заявка вновь обращается к прибору с повторной попыткой обслуживания. С первой зоны орбиты обращается для обслуживания на первую фазу, со второй зоны - на вторую, таким образом, происходит фазовое до-обслуживание заявок, обслуживание которых было прервано. Так как орбита разделяется на две зоны, то будем полагать: - интенсивность обращения заявок с первой зоны орбиты; - интенсивность обращения заявок со второй зоны. Обозначим i(t) - число заявок в первой зоне орбиты; i(t) - число заявок на орбите во второй зоне, k(t) отвечает за состояние прибора: k(t) =0, если прибор свободен; k(t) =1, если прибор обслуживает заявку на первой фазе; k(t)=2, если прибор обслуживает заявку на второй фазе. Перед нами стоит задача нахождения двумерного распределения вероятностей числа заявок на орбите и состояний прибора. 30 Асимптотический анализ системы с повторными вызовами, вытеснением заявок 2. Уравнения Колмогорова Рассмотрим трехмерный процесс {k(t),i1(t), i2(t)} . Обозначим стационарные вероятности P{k(t) = k,i1(t) = i1,i2(t) = i2} = Pk(i1,i2), k = 0,1,2. Введем функции следующего вида: ∞ ∞ . . . . Hk(U1,U2k = ∑ ∑ ekkkPk(/1,i2k k = 0■1■ 2, i1=0i2=0 где j = 7-1 - мнимая единица, которые являются частичными характеристическими функциями. Можно показать, что система уравнений для частичных характеристических функций имеет вид: T ГТ Z ч • dH0(u1,U2) . 5H0(u1,U2) -λH0 (и1,u2^ ÷ Jσ1-----------÷ Jσ2-----------÷ Ц2h2 (и1,u2^ = 0, du1du2 -μ1H1(u1,u2) ÷ λH0(u1,u2) ÷ l£'’ju2H2(u1,u2) ÷ l£'’jU1 H1(u1,u2) - 'KH1(u1,u2) ÷ j^2 dH1(u1, u2) du2 - jσ e~JU1 dH0(и1,и2) jσ1e Ju1 dH2 (u1, ^2 ) _ ∩ du1 ’ -λH2(u1,U2) - μ2H2(u1,u2) ÷ μ1H1 (u1,u2) ÷ jσ1 2^u!^- 2 1 2 2 2 1 2 1 1 1 2 1 du1 Ju2 dH1(u1,'и2) _ Q du22du2 Данная система трудно решается аналитически, поэтому для исследования используем метод асимптотического анализа [15] в предельном условии большой задержки ( σ→0 ). - jσ1eju2 - ju1 du1 Ju2 dH0(u1,^2^ 2,. „ju1-Ju2 - Jσ2^ 2--Jσ2e 3. Асимптотический анализ Введем обозначения: K1 - предельное среднее значение числа заявок на орбиты в первой зоне; K - предельное среднее значение числа заявок на орбите во второй зоне; Rk , k = 0,1, 2 - распределение вероятностей состояний прибора. Теорема 1. Пусть (t), (t) - число заявок в зонах орбиты RQ-системы с вытеснением заявок и дообслуживанием. Тогда в предельном условии σ→ 0 для вероятностей состояний прибора Rk = P{k(t) = k} выполняются равенства λλ λ λ r0 =1 , R1 = , R2 = , (1) Ц1Ц2 Ц1 Ц2 а для характеристических функций выполняется предельное равенство limMexp{ju1σi1(t) ÷ ju2σi2(t)∖ = exp{Ju1K^1 ÷7u2κ2l, σ→0 где параметры K , K имеют вид: 2 λ Ц 2 (2) 1 γ1 (Ц1Ц2- λ(M∣ ÷μ2)Γ γ2 (^1^2- λ(^1 ÷^2)) Из полученных в теореме 1 равенств (2) допредельные средние значения числа заявок в зонах K на орбите можно аппроксимировать величинами - , k = 1,2 . σ В работе [14] дано определение пропускной способности. 31 А.А. Назаров, Я.Е. Измайлова Следствие. Из первого равенства в (1) теоремы 1 получаем значение пропускной способности RQ-системы с вытеснением заявок и фазовым дообслуживанием в виде: S ^μχμ^ > 0. μ1+ μ2 Поэтому стационарный режим в такой системе существует для любых λ)- κ2 σ→0 [ √σ -√σ = exp < ( jU1 )2 ( ju? )^ . Q11 + q22 + Ju-iJu2Q12 “, где κ1, κ2 определены выше, величины Q11, Q12, Q22 - решение неоднородной системы уравнений Q11 ( γ1R0 +γ1R2 - γ1R0z0 + γ1R0z1 + γ1R2z1 - γ1R2 z2 ) + Q12(-γ2R1-γ2R0z0 +γ2R0z2 -γ2R1z1+γ2R1z2)= = 1 λR1 + 1 γ1K1R0 + 1 R2γ1K1 + 1 R1γ2κ? +γ1K1R0 z1 -^^R1Z1 +γ1K1R2 z1 -γ? κ2r1z2, q22 (γ? r0 + γ? r1 - γ? r0 у0 + γ2Ro у?+ γ2R1У2- γ2R1.У1) +q12 (-γ 1 r? - γ1Ro у0 + γ1Ro у1 - γ1R2 у?+ γ1R2 у1 )= = 1 + 1 γ2κ2r0 + 1 r2γ1κ1 + 1 R1γ2κ2 -λR2у1 +γ2κ2r0у? +γ2κ2r1.Y2 -γ1K1R2У1, Q11(-γ1R2 - γ1R0 p0 + γ1R0 p1 + γ1R2 p1 - γ1R2 p2 ) + Q12 (γ1R0 +γ1R2 +γ2R0 +γ2R1-γ2R0p0 + +γ2R0p2 -γ2R1p1+γ2R1p2-γ1R0s0 +γ1R0s1-γ1R2s2 + γ1R2s1 ) + +Q22(-γ2R1-γ2R0s0 +γ2R0s2 + γ2R1s2 - γ2R1s1 ) = -R2γ1κ1 - R1γ2κ2 + +γ1κ1R0p1-λR1p1+γ1κ1R2p1-γ2κ2R1p2 -λR2s1+γ2κ2R0s2+γ2κ2R1s2-γ1κ1R2s1. (3) со- Величины z0, z1, z2; y0, y1, y2; p0, p1, p2; s0, s1, s2 являются решением систем уравнений (4)-(7) ответственно. Для z0, z1, z2: -(λ+γ1κ1+γ2κ2)z0+(λ+γ1κ1)z1+γ2κ2z2 =-γ1κ1,-(μ1+γ2κ2)z1+(μ1+γ2κ2)z2 =λ+γ2κ2, μ2z0 +(λ+γ1κ1)z1-(λ+μ2 +γ1κ1)z2 = -γ1κ1. (4) Для y0, y1, y2: -(λ + γ1κ1 +γ2κ2)у0 +(λ + γ1κ1)у1 +γ2κzV2 =-γ2κ2, -(Ц1 +γ2κ2)у1 +(Ц1 +γ2κ2)у? =-γ2κ2, μiV0+ (λ+γ1κ1) у1 - (λ+μ?+ γ1κ1) у?=λ+γ1κ1. (5) (6) Для p0, p1, p2: -(λ + Y1K1 ■ γ2K2)p0 +(λ + Y1K1)p1 +-J2^2p2 =-Y2^2, -(Ц1 +Y2^2),1 +(Ц1 +Y2^2)p2 =-^2^2, μ2 p0 + (λ + γ1κ1) p1 - (λ + Ц2 + γ1κ1) p? = λ + γ1κ1. Для s0, s1, s2: -(λ+γ1κ1+γ2κ2)s0+(λ+γ1κ1)s1+γ2κ2s2 =-γ1κ1,-(μ1+γ2κ2)s1+(μ1+γ2κ2)s2 =λ+γ2κ2, μ2s0 +(λ+γ1κ1)s1 -(λ+μ2 +γ1κ1)s2 =-γ1κ1. (7) Запишем характеристическую функцию распределения вероятностей числа заявок на орбите в следующем виде: h (u1, u2) = eχp < Ju1 κ1 + j^u^ κ2 + ^^ijuU^ q11 + (q22 + jU1jU2 q12 ^. σ σ T,σ T,σ σ Из вышеизложенного получаем, что двумерное распределение вероятностей числа заявок на орбите является в пределе гауссовским распределением. 32 Асимптотический анализ системы с повторными вызовами, вытеснением заявок Заключение В работе была исследована система с повторными вызовами, фазовым дообслуживанием и вытеснением заявок методом асимптотического анализа. Показано, что предельная характеристическая функция числа заявок на орбите имеет вид характеристической функции гауссовского распределения. Получено значение пропускной способности данной системы и сделан вывод о том, что при значениях параметра интенсивности входящего потока λ < S для RQ-системы с вытеснением заявок и фазовым дообслуживанием стационарный режим существует, в то время как для RQ-системы с вытеснением заявок и обслуживанием заново стационарного режима не существует. Считаем целесообразным исследовать RQ-систему с вытеснением заявок и фазовым дообслуживанием общего типа, т.е. когда присутствует N фаз.

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