Modification of the asymptotic analysis method under heavy load condition on the example of the study of the retrial que.pdf Retrial Queueing System (системы массового обслуживания с повторными вызовами, или RQ-системы) - математические модели, широко применяемые для анализа и оптимизации различных телекоммуникационных систем, сетей мобильной связи, call-центров и других технических и экономических систем [1-6]. Характерной чертой таких моделей является наличие повторных обращений заявок к прибору после неудачной попытки обслуживания спустя некоторое случайное время. Такие ситуации могут быть вызваны не только отсутствием свободных серверов в моменты поступления заявок в систему, но техническими причинами. Возникновение моделей RQ-систем прежде всего связывают с работами американских ученых R.I. Wilkinson [1] и J.W. Cohen [2] середины ХХ в., которые были посвящены практическим задачам, возникающим в телефонных сетях, и описанию влияния эффекта повторных вызовов на производительность технических систем. Первые подходы к математическому описанию RQ-систем были предприняты G. Gosztony [3] и A. Elldin [4]. Наиболее полное и детальное описание RQ-систем и их сравнение с классическими СМО было отражено в монографиях J.R. Artalejo, A. Gomez-Corral, G.I. Falin и J.G.C. Templeton [7, 8]. Ими получены аналитические результаты для RQ-систем M|M|1, M|GI|1, М|М|С и других систем с пуассоновским входящим потоком, а также рассмотрены разнообразные методы для исследования таких систем и проведено детальное сравнение RQ-систем с их классическими аналогами [9]. На сегодняшний день исследованию RQ-систем посвящено большое количество работ [7], однако аналитических формул получено немного (лишь для систем с простейшим входящим потоком) [8]. В основном возникающие задачи решаются численными методами или с помощью имитационного моделирования [10-12], и как следствие, результаты таких исследований имеют узкое применение. Ранее в работах [13, 14] был предложен метод асимптотического анализа (первого и второго порядков) для исследования RQ-систем при условии большой загрузки. Предложенным методом были исследованы системы с различными типами входящего потока и дисциплиной обслуживания (в том числе RQ-система MMPP|GI|1 [15]). Было показано, что асимптотика первого порядка имеет вид гамма-распределения вне зависимости от типа системы, но область ее применения достаточно узка. Асимптотика второго порядка позволила расширить область применения результатов в 4 раза, однако асимптотическая формула не обладает единообразием и требуется ее достаточно трудоемкий вывод для каждой системы. В связи с этим в данной статье предлагаются способы модификации метода асимптотического анализа в условии большой загрузки RQ-систем, позволяющие увеличить точность асимптотического метода. Описание методов приведено на примере простейшей RQ-системы M|M|1 для возможности сравнения асимптотических результатов с известным точным. В дальнейшем предложенные модификации могут быть применены для исследования различных RQ-систем, в том числе с непуассоновским входящим потоком. 1. Математическое описание RQ-системы M|M|1 Рассмотрим однолинейную RQ-систему (рис. 1), на вход которой поступает простейший поток заявок с параметром X, время обслуживания каждой заявки распределено по экспоненциальному закону с параметром ц. Если поступившая заявка застает прибор свободным, то она занимает его для обслуживания. Если прибор занят, то заявка переходит в источник повторных вызовов (ИПВ), где осуществляет случайную задержку, продолжительность которой имеет экспоненциальное распределение с параметром о. Из ИПВ после случайной задержки заявка вновь обращается к обслуживающему прибору с повторной попыткой его захвата. Если прибор свободен, то заявка из ИПВ занимает его для обслуживания, в противном случае она мгновенно возвращается в источник повторных вызовов для реализации следующей задержки. * (t ) = Рис. 1. RQ-система M|M|1 Пусть i(t) - число заявок в ИПВ, а k(t) определяет состояние прибора следующим образом: [0, если прибор свободен, [1, если прибор занят. Обозначим P{k(t) = k, i(t) = i} = P(k,i,t) вероятность того, что прибор в момент времени t находится в состоянии k и в источнике повторных вызовов находится i заявок. Причем процесс {k(t), i(t)} изменения состояний данной системы во времени является марковским. Тогда ставится задача нахождения распределения вероятностей числа заявок в источнике повторных вызовов такой системы. Для распределения вероятностей P(k,i,t) состояний рассматриваемой RQ-системы составим систему дифференциальных уравнений Колмогорова: = цР(1,i,t) - (X + ia)P(0,i,t), = XP(0,i,t) + (i + 1)a • P(0,i + 1,t) - (X + ц)P(1,i,t) + XP(1,i -1,t). dP (0, t) dt dP (1, i, t) dt (1) Перейдем к стационарным частичным характеристическим функциям H(k, u) = £eJulP(k, i), где i P(k, i) = lim P(k , i,t ) , а J - мнимая единица. t^x Введем параметр p = -, характеризующий загрузку системы. Тогда система (1) в стационарном ц режиме для характеристических функций перепишется в следующем виде: ц du pH(0,u)+(p(eJu -1)-1)(1,u) = Jae-Ju . ц du H(1,u)-pH(0,u) = -aj dH0U 2. Метод асимптотического анализа в условии большой загрузки В работах [13-15] для решения системы уравнений (2) был предложен метод асимптотического анализа в условиях большой загрузки, т.е. при р t1, который заключается в следующем. Вводятся обозначения s = 1 - р (тогда в условии большой загрузки s i 0), u = sw, H(0, u) =sF0(w, s), H(1, u) = F0(w, s) . Таким образом, система (2) принимает вид (3) F1(w, s) - (1 -s)sF0 (w, s) + j iFw^ = 0, д Cw (1 - s)sF0(w, s) + ((1 - s)(ew -1)-1), s) - j - e- jws = 0. д cw Далее используются следующие разложения: Fk (w, s) = Fk (w) + s- fk (w) + 0(s 2), (4) где 0(s ) - бесконечно малая величина порядка s2 . Допредельная характеристическая функция H (u) = H (1, u) + H (0, u) в условиях большой загрузки может быть приближенно определена равенством + 0(s 2). ( u > H (u) « F1 1 -Р Обозначим hi(u) асимптотическую характеристическую функцию первого порядка, которая равна ( u ^ Mu) = F1 1 -р В [13] было доказано, что hi(u) удовлетворяет следующей теореме. Теорема 1. Асимптотическая характеристическая функция числа заявок в ИПВ в RQ-системе M|M|1 имеет вид характеристической функции гамма-распределения (5) / \"а u h (u) = 1 - j- Л) у ^ д с параметрами формы а = -+1 и масштаба р = 1 - р . а В качестве критерия допустимости асимптотических результатов использовалось условие: расстояние Колмогорова Д < 0,05 . С помощью численного анализа было показано, что метод асимптотического анализа первого порядка в условиях большой загрузки может быть применим при значениях загрузки р > 0,95, что является достаточно узкой областью применимости. Поэтому также была получена асимптотическая характеристическая функция второго порядка h2(u): h2(u) = FI - | + (1 -р) ^т-рГ f111-р Для получения этой асимптотики второго порядка вместо разложений функций (4) необходимо было рассмотреть разложения Fk(w,s) = Fk (w) + s - fk(w) + s2 - 9k(w) + 0(s3) и, подставив их в систему (3), решить систему пяти дифференциальных уравнений. Тогда допредельная характеристическая функция может быть определяется равенством H (u) = h2(u) + 0(s3). Была доказана следующая теорема о виде функции h2(u) [14]. Теорема 2. Асимптотическая характеристическая функция второго порядка распределения вероятностей числа заявок в ИПВ в RQ-системе М|М|1 имеет вид 2 ju 1 -р ju -I ц+1l1 -р" ц+а а 2 ju _+Ц lnh - ju u h2(u) = 1 1 - j 1+(1 -р) 1-р 1 -р а 1-р ju 1 -р а 1- Численный анализ показал, что область применения асимптотики второго порядка р > 0,8, т.е. увеличивается в 4 раза (по сравнению с (5)). Однако для более сложных RQ-систем, например MMPP|GI|1, приходилось решать систему из семи и более дифференциальных уравнений, что достаточно трудоемко. 3. Гипергамма-асимптотика Заметив, что в ходе доказательства теоремы 1 была найдена и функция F0(w), было предложено провести численный анализ «промежуточной» асимптотики h (u): ( u \ ( u \ h (u) = F1 1-р + (1 -р^0 1 -р. В работе [13] показано выполнение следующих равенств: ц F)(w) = С(1 - jw), < F1(w) = С (1 - jw)-^-1. Имеем условие нормировки h(0) = H0(0) + H1(0) = 1. Так как H1(u) « F1(u), а H0(u) « (1 -р)F0(u), 1 то получаем h(0) = (1 - р) F0 (0) + F1(0) = (1 - р)С + C = 1. Отсюда С = 2-р Тогда имеем а 1-р h ■ u +--I 1 - Jh*(u) = 11 - j 2-р1 1 -р 2 - р 1 1 - р Заметим, что слагаемые функции h (u) являются характеристическими функциями гамма-распределения: a Y ц ju P а X Г(u) = |1 - , Г0(u) = I 1 , где a = -+1 и p = 1 -р . P Таким образом, получили, что «промежуточная» асимптотическая характеристическая функция распределения числа заявок в ИПВ имеет вид взвешенной суммы двух характеристических функций гамма-распределения h*(u) = дГ1 (u) + (1 - q)Г0 (u), (6) 1 где q = 2-р Будем называть такое распределение гипергамма-распределением (по аналогии с гиперэкспоненциальным). В табл. 1 приведены Д1, Ар, Д2 - расстояния Колмогорова между точным распределением и первой асимптотикой, гипергамма-распределением и второй асимптотикой соответственно. Из табл. 1 видно, что гипергамма-асимптотика значительно точнее асимптотики первого порядка, но уступает асимптотике второго порядка. Т а б л и ц а 1 Расстояние Колмогорова между точным и асимптотическими распределениями Значения параметров системы р = 0,7 р = 0,8 р = 0,9 р = 0,95 а = 10 Д1 0,251 0,170 0,086 0,043 Ap 0,097 0,060 0,028 0,014 Д2 0,035 0,022 0,009 0,005 а = 2 Д1 0,266 0,179 0,091 0,046 Ap 0,157 0,104 0,050 0,025 A2 0,088 0,047 0,016 0,005 а = 1 Д1 0,304 0,208 0,106 0,053 Ap 0,220 0,147 0,074 0,037 A2 0,124 0,052 0,013 0,003 Однако вывод асимптотической формулы второго порядка для более сложных RQ-систем затруднителен, тогда как «промежуточная» асимптотика не требует дополнительных выкладок, так как ее форма одинакова для RQ-систем с различными типами входящего потока и дисциплины обслуживания, а параметры гипергамма-распределения совпадают с параметрами первой асимптотики. Поэтому целесообразность ее использования для большинства практических задач очевидна. 4. Модификация гипергамма-асимптотики Известно, что Я1(0) = R1 = р, H0(0) = R0 = 1 - р . Однако в полученной «промежуточной» асимптотике (6) q^(0) = q * Ri и (1 - д)Г>(0) = 1 - q * R,. Перейдем от характеристических функций к функциям распределения вероятностей, обозначив их соответственно Г0 (x) и Г1 (x). Тогда qr1 (да) = q * R1 и (1 - q)Г0 (да) = 1 - q * R0 . В связи с этим предлагается модифицировать асимптотику следующим образом: >1( x) = q [Г 1( x + 5) -Г 1(5) ], F0( x) = ж + (1 -q) [Г 0( x + 5)-Г 0(5) ], где F1(x) и F0(x) - модифицированные частичные асимптотические функции распределения, а параметры 5 и п могут быть найдены из условия нормировки: 1>1(да) = q[1 -Ц(5) IF) (да) = ж + (1 - q) Из первого уравнения (7) имеем г1(5)=1 -р=з-р. q q Подставляя введенные ранее обозначения, нетрудно получить Г1 (5) = (1 -р)2. (8) Выразим величину п из второго уравнения (11): (1 -р)2 + (1 - р)Г0 (5) ж = • 2-р Подставляя (8), получим следующее выражение: ж=Г 1(5) + (1-р)Г 0(5) + (1-^(5). (9) 2-р Модифицированная асимптотическая функция распределения записывается как сумма F (x) = F1( x) + F0( x). Учитывая полученные выражения (11)-(13), имеем следующее равенство: = Р~ , (7) 1 - T0(5)J = 1 -р. F (x) = qt 1 (x + 5) + (1 - q)t 0 (x + 5). Проведем численный анализ модификации асимптотики и сравним ее с результатами, полученными ранее асимптотики (табл. 2, где ДМ - расстояние Колмогорова между точным распределением и модифицированной асимптотикой). Т а б л и ц а 2 Расстояние Колмогорова между точным, асимптотическими и модифицированным распределениями Значения параметров системы р = 0,5 р = 0,6 р = 0,7 р = 0,8 р = 0,9 р = 0,95 о = 10 Д1 0,378 0,321 0,251 0,170 0,086 0,043 Ap 0,180 0,137 0,097 0,060 0,028 0,014 ДМ 0,065 0,059 0,050 0,038 0,022 0,012 Д2 0,042 0,041 0,035 0,022 0,009 0,005 о = 2 A1 0,432 0,342 0,266 0,179 0,091 0,046 Ap 0,271 0,213 0,157 0,104 0,050 0,025 ДМ 0,079 0,077 0,068 0,050 0,031 0,017 Д2 0,192 0,139 0,088 0,047 0,016 0,005 о = 1 Д1 0,487 0,394 0,304 0,208 0,106 0,053 Др 0,364 0,291 0,220 0,147 0,074 0,037 ДМ 0,093 0,087 0,074 0,052 0,030 0,016 Д2 0,313 0,214 0,124 0,052 0,013 0,003 Данные табл. 2 показывают, что «модифицированное» распределение существенно улучшает результаты «промежуточной» асимптотики. При этом для построения модифицированного распределения необходимо лишь найти величину сдвига 5 из условия (8). Рассмотрим комбинацию «модифицированного» распределения и второй асимптотики Pm(2) = 1 (Pm + P(2)). Будем называть такое распределение «модификация-2». Проведем численный анализ модификации асимптотики и сравним ее с результатами, полученными ранее. Т а б л и ц а 3 Расстояние Колмогорова между точным, асимптотическими и модифицированными распределениями Значения параметров системы р = 0,5 р = 0,6 р = 0,7 р = 0,8 р = 0,9 р = 0,95 о = 10 Д1 0,378 0,321 0,251 0,170 0,086 0,043 Др 0,180 0,137 0,097 0,060 0,028 0,014 ДМ 0,065 0,059 0,050 0,038 0,022 0,012 Д2 0,042 0,041 0,035 0,022 0,009 0,005 ДМ2 0,034 0,024 0,018 0,013 0,009 0,005 о = 2 Д1 0,432 0,342 0,266 0,179 0,091 0,046 Др 0,271 0,213 0,157 0,104 0,051 0,025 ДМ 0,079 0,077 0,068 0,050 0,031 0,017 Д2 0,192 0,139 0,088 0,047 0,016 0,005 ДМ2 0,111 0,073 0,039 0,019 0,013 0,008 о = 1 Д1 0,487 0,394 0,304 0,208 0,106 0,053 Др 0,364 0,291 0,220 0,147 0,074 0,037 ДМ 0,093 0,087 0,074 0,052 0,030 0,016 Д2 0,313 0,214 0,124 0,052 0,013 0,003 ДМ2 0,150 0,087 0,046 0,022 0,012 0,007 В результате численного анализа был замечен интересный результат: «модификация-2» точнее второй асимптотики. При этом предложенная модификация применима для значений загрузки р>0,7, а при больших значениях параметра задержки о - для значений загрузки р>0,5. Заключение Таким образом, в работе предложены три модификации метода асимптотического анализа в условии большой загрузки RQ-систем: «промежуточная» асимптотика, имеющая вид гипер гамма-рас -пределения; модификация «промежуточной» асимптотики в виде сдвига распределения на параметр 5; полусумма распределений модифицированной и второй асимптотики. В статье также представлены результаты численного сравнения предложенных асимптотик с известным точным, позволяющие сделать заключения об области применения каждого метода. Обобщая вышесказанное, можно сделать вывод, что для практических задач, не требующих высокой точности аппроксимации, целесообразно использование результатов «промежуточной» асимптотики в силу ее простоты построения (имеет единую форму вне зависимости от типа входящего потока) и достаточно широкой области применимости (р > 0,8), а для задач, требующих более высокой точности аппроксимации, целесообразно применять предлагаемые в работе модификации 1 и 2.

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