Исследование RQ-системы m|e2|1 с вытеснением заявок и сохранением фазовой реализации обслуживания

ВЕСТНИК ТОМСКОГО ГОСУДАРСТВЕННОГО УНИВЕРСИТЕТА 2018 Управление, вычислительная техника и информатика № 42

УДК 519.872

DOI: 10.17223/19988605/42/8

А.А. Назаров, Я.Е. Измайлова

ИССЛЕДОВАНИЕ RQ-СИСТЕМЫ M|E2|1 С ВЫТЕСНЕНИЕМ ЗАЯВОК И СОХРАНЕНИЕМ ФАЗОВОЙ РЕАЛИЗАЦИИ ОБСЛУЖИВАНИЯ

Исследование выполнено при финансовой поддержке РФФИ в рамках научного проекта № 16-31-00292 мол а.

В работе исследована RQ-система с вытеснением заявок, простейшим входящим потоком, гиперэкспоненциальным распределением времени обслуживания и сохранением фазовой реализации обслуживания. Исследование системы проводилось методом асимптотического анализа в предельном условии большой задержки заявок на орбите. Показано, что предельная характеристическая функция числа заявок на орбите является асимптотически гауссовской. Найдены параметры этого распределения.

Ключевые слова: RQ-система; вытеснение заявок; фазовая реализация; зоны орбиты; большая задержка.

В литературе показано, что адекватными математическими моделями телекоммуникационных сетей связи являются RQ-системы (Retrial queueing system, или системы с повторными вызовами). Исследованием RQ-систем в настоящее время занято большое количество зарубежных и российских ученых. Значительный вклад в развитие теории внесли Г.И. Фалин, J.R. Artalejo [1], А.Н. Дудин [2], Г.П. Башарин, К.Е. Самуйлов. Однако этими учеными были получены аналитические формулы для систем с относительно простой конфигурацией, в то время как реальные системы являются сложными. RQ-системам с приоритетами посвящено немалое количество исследований, к которым можно отнести работы K. Avrachenkov [3, 4], G. Ayyappan, A. Muthu Ganapathi [5], П.П. Бочарова, О.И. Павловой [6], B. Krishna Kumar, A. Vijayakumar, D. Arivudainambi [7], C. Kim [8]. Кроме того, следует отметить работы, касающиеся изучения RQ-систем с дискретным временем. В работе I.M. Atencia [9] рассматривается система с повторными вызовами с дискретным временем, в которой прибывшая заявка, обнаружившая прибор занятым, может решить, начать ли обслуживание или присоединиться к орбите и повторить попытку позже согласно дисциплине FCFS (First Come First Served - первым пришел, первым обслужен). Современная литература по RQ-системам очень обширна и богата, последние обзоры можно найти в работе J.R. Artalejo. Однако в рассмотренных выше моделях приоритетных RQ-систем не учитывается эффект вытеснения требований, что существенно влияет на характеристики исследуемых систем. Данная работа будет посвящена исследованию систем с вытеснением требований.

1. Математическая модель и постановка задачи

Рассмотрим RQ-систему с вытеснением заявок (рис. 1).

Орбита

Яч-Яя-

,0,'iff, |а2\ст2

В

Рис. 1. RQ-система M|E2|1 с вытеснением заявок

На вход системы поступает простейший поток заявок с интенсивностью L Требование, заставшее прибор свободным, занимает его для обслуживания в течение времени, подчиняющегося гиперэкспоненциальному распределению B(x) с параметрами q, Ц1, Ц2. С вероятностью q заявка обслуживается экспоненциально распределенное время с параметром Ц1 (1 фаза), с вероятностью 1 - q заявка обслуживается экспоненциально распределенное время с параметром Ц2 (2 фаза). Если прибор занят, то поступившая заявка вытесняет обслуживаемую и сама занимает прибор для обслуживания, а заявка, которая обслуживалась, переходит на орбиту. Орбита разделяется на две зоны. Если заявка обслуживалась на первой фазе, то уходит в первую зону орбиты, если на второй фазе, то на вторую. В зонах орбиты заявки осуществляют случайную задержку, продолжительность которой имеет экспоненциальное распределение с параметром oí для первой зоны и 02 для второй. Из орбиты после случайной задержки заявка вновь обращается к прибору с повторной попыткой его захвата. Дисциплина обращений заявок с орбиты принципиально отличается от дисциплины обращения заявок, которые впервые прибыли в систему, так как для первичных заявок номер фазы определяется случайным образом с вероятностью q, а при повторном обращении номер фазы выбирается однозначно по номеру зоны. Так как орбита разделяется на две зоны, то заявки, находящиеся на орбите в первой зоне, будут осуществлять задержку с экспоненциально распределенным временем с параметром 01 = yío, на орбите во второй зоне - с параметром 02 = Y20.

Обозначим ií(t) - число заявок на орбите в первой зоне, Í2(t) - число заявок на орбите во второй зоне. Пусть k(t) определяет состояние прибора следующим образом: 0, если прибор свободен, к (t) = < 1, если прибор занят заявкой, находящейся на первой фазе обслуживания, 2, если прибор занят заявкой, находящейся на второй фазе обслуживания.

Ставится задача нахождения совместного трехмерного распределения вероятностей чисел заявок в зонах на орбите и состояний прибора.

2. Система уравнений Колмогорова для частичных характеристических функций

Рассмотрим трехмерный процесс {к(t),ij(t),i2(t)}.

Обозначим Р\к(t) = к,i1 (t) = i1,i2(t) = i2} = Pk(i1,i2), к = 0,1, 2 стационарную вероятность того,

что прибор в момент времени t находится в состоянии k, на орбите в первой зоне находится i1 заявок, на орбите во второй зоне находится i2 заявок.

Введем частичные характеристические функции следующего вида:

да да

нкщ) = да да eju1i1eju2i2Рк,i2), к = 0,1,2,

i¡ = 0 i 2 = О

где j = >/-Г - мнимая единица.

Запишем систему для частичных характеристических функций:

-Щ)(«1, «2) + м + jv2 "2) + *H1(«1, «2) + Ц2 н2(иъ u2) = 0,

oul ou2

—XHy («, u2 ) — H («, u2 ) + XqH0 («, u2 ) + Xqe J«2H2 («, u2 ) + A,qeju11 («, u2 ) +

8H

+JCT2--- Me Ju1-0V 1 2 - jctjeju2 Ju1-2V ^ 2 = 0,

8u2 8u1 8u1

-XH2 (u, u2 ) - Ц2 H2 (u1, u2 ) + X(1 - q)H (u1, u2 ) + X(1 - q)eju1H1 (щ, ^ ) + X(1 - q)e ju H2 (u, u¿) +

+j 8H^^^^^u2) - j - ^O^u2) - j j-Huíul = 0.

8u1 8u2 8u2

Аналитически данную систему решить затруднительно. Будем решать ее методом асимптотического анализа [10] в условии большой задержки, когда среднее время--»го, а ст^ 0, полагая что

а

Gl = Oyi, 02 = 072.

3. Асимптотика первого порядка

Обозначим x„, n = 1, 2, - асимптотическое среднее значение числа заявок на n-й зоне орбиты, а Rk, к = 0, 1, 2, - распределение вероятностей состояний прибора. Сформулируем следующее утверждение.

Теорема 1. Пусть ii(t) - число заявок на орбите в первой зоне, /2(0 - число заявок на орбите во второй зоне RQ-системы с вытеснением заявок и сохранением фазовой реализации. Тогда для последовательности характеристических функций выполняется равенство:

lim М exp {щщ^(t) + ju1CTi1i1 (t)} = exp {julxl + ju2 x2},

ст^0

где xi, X2 являются решением системы уравнений

"Ylx1^0 + (K + У2x2)R1 -Tlx1R2 = °> -У2x2R0 - У2x2R1 + (K + yix1 )R2 = °>

а вероятности Rk, к = 0, 1, 2, находятся из системы

-

R + R1 + R2 = 1.

Из систем уравнений (1), (2) находятся средние числа xi, X2 заявок в зонах на орбите и распределение вероятностей Rk, к = 0, 1, 2, состояний прибора.

Для более детального исследования рассмотрим асимптотику второго порядка.

4. Асимптотика второго порядка

Построим гауссовскую аппроксимацию числа заявок на орбите. Сформулируем следующее утверждение.

Теорема 2. Пусть i 1(t) - число заявок на орбите в первой зоне, i2(t)- число заявок на орбите во второй зоне RQ-системы с вытеснением заявок и сохранением фазовой реализации. Тогда имеет место предельное равенство:

lim М exP { jU1 CTM|=i + ju2 } = exp { jÜ Qn + jux ju2Qa J,

где X1, X2 являются решением систем уравнений (1), (2), величины Q11, Q12, Q22 находятся из неоднородной системы линейных алгебраических уравнений

Q11 (yR + У1R2 - yRz0 + yRz1 + y1R2z1 - y1R2z2 ) + +Q12 (-У2R1 -У2R0Z0 +У2R0z2 -У2R1z1 + У2R1z2 ) = 1 K(1 - q)R1 + 1 У^Л + 1 KqR1 +

+1R2y1x1 + 1 R1y2x2 + y1x1R0Z1 - KqR1z1 + y1x1R2z1 - K

+1 K(1 - q)R2 + 1 RlУ2x2 - KqR2У + У2x2R0У2 - K(1 - q)R2У2 + У2x2R1J2 - УlX1R2Уь

Q\\ (-У^2 - Ул>Ро + уЛ>Р1 + У 1^2р1 - У 1^22 ) + 012 (ул + У1^2 + У2+ У2- У2ро +

+У2р2 - У2^р1 + У2я1р2 - У 1^0¿0 + У 1^0¿1 - У^2¿2 + У^2¿1) + +022 (-У2К1 - У2¿0 + У2¿2 + У 2^¿2 - У 2м) = -К2У1Х1 - ^У2Х2 + УЛ^ОР1 - Хч^л + +У1Х1^2р1 - Х(1 - чжр2 - У2Х2К1Р2 - хч^2¿1 + У 2Х2^0¿2 - Х(1 - ФК2¿2 + У2Х2^¿2 - УЛ^! Величины го, ^2;уо,у1,у2;ро,Р1,Р2; 5о, 51, 52 определяются из систем уравнений (4)-(7) соответственно. Для го, 21, 22'.

Для уо, У1, У2.

Для ро, Р1, Р2.

Для 5о, 51, 52.

-(Х + У1Х1 + У2Х2 ) 20 + (хч + У1Х1 ) 21 + (Х(1 - ч) + У2Х2 ) 22 = -У1Х1, И120 - (Х(1 - ч) + И + У2Х2 ) 21 + (х0 - ч) + У2Х2 ) 22 = Х + У2Х2, Ц2 + (хч + У1Х1 ) 21 - (хч + Ц2 + У1Х1 ) 22 = -У1Х1

-(Х + У1Х1 + У2Х2 ) Уо + (хч + У1Х1) у1 + (м1 - ч) + У 2Х2 ) у2 = -У 2Х2 > ^1-уо - (Х(1 - ч) + И + У2Х2 ) у1 + (Х(1 - ч) + У2Х2 ) у2 = -У 2Х2 > ^2уо + (хч + У1Х1)у1 - (хч + ^2 + У1Х1 )у2 = Х + У1Х1

(Х + У1Х1 + У 2 Х2 ) ро + (хч + У1Х1 ) р1 + (Х(1 - ч) + У 2 Х2 ) р2 = У 2 Х2' иро - (Х(1 - ч) + И + У2Х2 ) р1 + (х0 - ч) + У2Х2 ) р2 = -У2Х2' ц.2 ро + (хч + У1Х1) р1 - (хч + И2 + У1Х1) р2 = Х + УЛ

-(Х + ух х + Уг х) ¿о + (Хч + у х) ¿1 + (Х(1 - ч) + Уг х) ¿2 =-У х, ^¿0 - (Х(1 - ч) + И1 + у2х2 ) ¿1 + (Х(1 - ч) + у 2х2 ) ¿2 = X + у2х2, ^¿о + (Хч + У1х1) ¿1 - (ХЧ + Ц.2 + У1х1) ¿2 = -У1х1.

Заметим, что доказать асимптотическую гауссовость распределения числа заявок можно, записав характеристическую функцию в виде произведения.

Н (и1, и2) = ехр

ЩР- Й1 + ^ 622 + ^ 012 } ехр {а х1 + .а х2 } . 2а 2а а I а а

Откуда, выполнив несложные преобразования, получаем

Н(и1,и2) = ехр{{Х1 + АХ2 + ^011 + 022 + Щ012 } •

I а а 2а 2а а I

Последнее выражение доказывает, что двумерное распределение вероятностей числа заявок на орбите является асимптотически гауссовским.

5. Численная реализация

Были рассмотрены примеры численного решения систем (1)-(7) для различных значений параметров Ц1 и Ц2 функции распределения времени обслуживания В(х) с преобразованием Лапласа-Стилтьеса

б* ( х) = ч(1 +х)-1 + (1 - ч)(1 + —)-и1 и

и параметров X и 01, 02.

Рассмотрим пример для случая

X = 2, ч = 0,6, у1 = 2, 72 = 3.

На рис. 2 представлен график плотности P

P(x, y) =-^—exp {- , 1 „ f fL _ 2Q 12( x " X1)(y " ^ +

( У) 2nQiiQ22j^Q~? { 2 (1 - Ö122)1 Ö112 Q12 011022 Ö222

двумерного распределения вероятностей числа заявок на орбите.

Рис. 2. График плотности Р(х, у) при значениях = 4 и = 5

В работе [11] была рассмотрена ЯО-система с вытеснением заявок, в которой обслуживание после прерывания начинается заново. Целесообразно выполнить сравнение значений асимптотических средних между среднимX, полученным с помощью метода, предложенного в [11], и асимптотическим средним х = Х1 + Х2, полученным с помощью метода асимптотического анализа ЯО-системы с вытеснением заявок и сохранением фазовой реализации.

Таблица 1

Значения асимптотических средних числа заявок на орбите для различных RQ-систем при у1 = у2

Н-2 2 3 4

x X x X x X

20 0,341 0,913 0,194 0,707 0,141 0,582

30 0,314 0,794 0,177 0,612 0,126 0,500

40 0,302 0,738 0,169 0,566 0,119 0,460

В табл. 1 приведены значения асимптотических средних для ЯО-системы с вытеснением и сохранением фазовой реализации х и для ЯО-системы, в которой после прерывания обслуживания у заявки обслуживание начинается заново, X при различных значениях параметров времени обслуживания. Как можно видеть из таблицы, среднее значение х суммарного числа заявок на орбите ЯО-системы с вытеснением заявок и сохранением фазовой реализации в 3-4 раза меньше среднего числа заявок X ЯО-системы с вытеснением заявок, в которой обслуживание после прерывания начинается заново.

Заключение

В данной работе была исследована ЯО-система с вытеснением заявок и с сохранением фазовой реализации методом асимптотического анализа в предельном условии большой задержки заявок на орбите. Для нее получены уравнения для нахождения среднего числа заявок на орбите /(О = /1(0 + /2(0, а также уравнения для нахождения стационарного распределения вероятностей состояний прибора. Модифицирован метод асимптотического анализа для исследования ЯО-систем с сохранением фазовой реализации и вытеснением заявок. Было показано, что асимптотическая характеристическая функция числа заявок на орбите является асимптотически гауссовской. Был проведен численный анализ

системы. Для конкретных значений параметров были получены асимптотические средние числа заявок на орбите, а также вторые центральные моменты и коэффициент корреляции между заявками на орбите в первой и второй зонах.

Результаты выполненных исследований могут позволить решить задачи в области проектирования инфокоммуникационных систем, телекоммуникационных систем, управляемых протоколами случайного множественного доступа.

Считаем целесообразным исследовать RQ-систему с дообслуживанием заявок и вытеснением.

ЛИТЕРАТУРА

1. Artalejo J.R. Accessible Bibliography on Retrial Queues // Progress in 2000-2009 Mathematical and Computer Modeling. 2010.

V. 51. P. 1071-1081.

2. Chakravarthy S.R., Dudin A. Analysis of a retrial queuing model with MAP arrivals and two types of customers. // Mathematical

and Computer Modelling. 2003. V. 37, No. 3-4. P. 343-363.

3. Avrachenkov K., Dudin A., Klimenok V. Queueing Model MMAP/M 2/1 with Two Orbits // Lecture Notes in Comput. Sci. Berlin :

Springer, 2010. 6235. P. 107-118.

4. Avrachenkov K., Nain Ph., Yechiali U. A retrial system with two input streams and two orbit queues // Queueing Systems. 2014.

V. 77, No. 1. P. 1-31.

5. Ayyappan G., Ganapathi M.A., Sekar G. M/M/1 Retrial Queuing System with Loss and Feedback under Pre-Emptive Priority

Service // International Journal of Computer Applications. 2010. V. 2, No. 6. P. 27-34.

6. Bocharov P.P., Pavlova O.I., Puzikova D.A. M| G| 1 |r retrial queueing systems with priority of primary customers // Mathematical

and computer Modeling. 1999. V. 30, No. 3-4. P. 89-98.

7. Kumar B.K., Vijayakumar A., Arivudainambi D. An M/G/1 Retrial Queueing System with Two-Phase Service and Preemptive

Resume // Annals of Operations Research. 2002. V. 113, No. 1-4. P. 61-79.

8. Kim C. Priority tandem queueing system with retrials and reservation of channels as a model of call center // Computers & Industrial

Engineering. 2016. V. 96. P. 61-71.

9. Atencia I.M. A Geo/G/1 retrial queueing system with priority services // European Journal of Operational Research. 2017. V. 256,

No. 1. P. 178-186.

10. Назаров А.А., Моисеева С.П. Методы асимптотического анализа в теории массового обслуживания. Томск : Изд-во НТЛ, 2006. 112 c.

11. Nazarov A., Chernikova Ya. Gaussian Approximation of Distribution of States of the Retrial Queueing System with r-Persistent Exclusion of Alternative Customers // Information Technologies and Mathematical Modelling. Queueing Theory and Applications : Procceding of the 14th International Scientific Conference. 2015. V. 564. P. 200-208. DOI: 10.1007/978-3-319-25861-4_19.

Назаров Анатолий Андреевич, д-р техн. наук, профессор. E-mail: nazarov.tsu@gmail.com Измайлова Яна Евгеньевна, канд. физ.-мат. наук. E-mail: evgenevna.92@mail.ru Национальный исследовательский Томский государственный университет

Поступила в редакцию 2 декабря 2017 г.

Nazarov Anatoly A., Izmailova Yana E. (National Research Tomsk State University, Russian Federation). Research of RQ-system M| E2| 1 with request displacement and conserving phase realization of servicing. Keywords: RQ-system; request displacement; phase realization; orbit zones; large delay.

DOI: 10.17223/19988605/42/8

The paper considers an RQ-system which could be used as a mathematical model of a 5G new generation telecommunication network. The input of the system is a simplest request flow with intensity X.

Request that found server free is then serviced for a duration of time that has hyper exponential distribution with parameters q, Ц1, Ц2. With probability q request that came from the flow is then serviced for an exponential time with parameter (1st phase), and with probability 1 - q the request is serviced for an exponential time with parameter ^2 (2nd phase).

If the server is busy then the incoming request pushes the previous request out of service and takes its place, while the pushed out request goes to the orbit. Orbit is divided in 2 zones. If a request was being serviced at the 1st phase of hyper exponential distribution -it goes to the 1st zone of the orbit, and it was being serviced at the 2nd phase - it goes to the 2nd zone.

At the orbit zones requests are randomly delayed and duration of delay has an exponential distribution with parameter 01 for the 1st zone and 02 for the 2nd. From there, after a random delay, request again returns to the server.

The appeal discipline of requests from the orbit is fundamentally different from the appeal discipline of requests that are new to the system, as for the new requests the phase number is determined randomly by the probability q, when the returning requests already have a zone number that determines the number of a phase.

The research is conducted using the asymptotic analysis method in the limit condition of a large delay of requests on the orbit, characterized by a condition ст^ 0, assuming that 01 = 071, 02 = 072.

In order to use this method we've obtained the Kolmogorov equation system for probability distribution of a 3-dimensional process of number of requests at the zones on an orbit and statuses of the server, we've also made transition from the equation system for probabilities to the Kolmogorov equation system for partial characteristic functions.

The first order asymptote was reviewed. We've obtained equations for finding the distribution of probabilities of statuses of the server Rk, k = 0, 1, 2, and for finding asymptotic mean xn, n = 1, 2, of number of requests at the zones of the orbit. We've reviewed the second order asymptote. We've obtained equations for finding second asymptotic moments: variance and correlation coefficient between number of requests in the 1st and the 2nd zones.

We've found limit characteristic function (at a^0) of a normalized number of requests at the orbit that has the form

H(«,u2) = exP \j~x\ + x2 + (jUl) Qn + (ju2) q22 + juiju2 q^ I , i.e. the form of a characteristic function of the 2-dimen-I a a 2a 2a a I

sional Gauss distribution.

Numerical experiments were conducted for different parameter values of time of servicing and intensity of incoming flow. The obtained results of asymptotic mean of number of requests at the orbit of an RQ-system with request displacement and conservation of phase realization were compared to the asymptotic mean number of requests at the orbit of an RQ-system with request displacement and servicing returning requests as the new ones.

It is established that by conserving phase realization the mean number of requests at the orbit is 3-4 times smaller than the mean number of requests at the orbit with servicing them as new each time. Obtained results could be useful in designing informational-communicational systems controlled by random multiple access protocols.

We've concluded it to be expedient to research the RQ-system with requests displacement and after service, because such a model would be very important in designing communication networks, since this problem wasn't solved in science literature.

REFERENCES

1. Artalejo, J.R. (2010) Accessible Bibliography on Retrial Queues. Progress in 2000-2009 Mathematical and Computer Modeling 51.

pp. 1071-1081. DOI: 10.1016/j.mcm.2009.12.011

2. Chakravarthy, S.R. & Dudin, A. (2003) Analysis of a retrial queuing model with MAP arrivals and two types of customers. Mathe-

matical and Computer Modelling. 37(3-4). pp. 343-363. DOI: 10.1016/S0895-7177(03)00011-6

3. Avrachenkov, K., Dudin, A. & Klimenok, V. (2010) Queueing Model MMAP/M 2/1 with Two Orbits. Lecture Notes in Comput.

Sci. 6235. pp. 107-118.

4. Avrachenkov, K., Nain, Ph. & Yechiali, U. (2014) A retrial system with two input streams and two orbit queues. Queueing Systems.

77(1). pp.1-31. DOI: 10.1007/s11134-013-9372-8

5. Ayyappan, G., Ganapathi, M. & Sekar, G. (2010) M/M/1 Retrial Queuing System with Loss and Feedback under Pre-Emptive

Priority Service. International Journal of Computer Applications. 2(6). pp.27-34. DOI: 10.5120/672-945

6. Bocharov, P.P., Pavlova, O.I. & Puzikova, D.A. (1999) M| G| 1 |r retrial queueing systems with priority of primary customers.

Mathematical and computer Modelling. 30(3-4). pp. 89-98. DOI: 10.1016/S0895-7177(99)00134-X

7. Atencia, I.M. (2017) A Geo/G/1 retrial queueing system with priority services. European Journal of Operational Research. 256(1).

pp. 178-186. DOI: 10.1016/j.ejor.2016.07.011

8. Kim, C. (2016) Priority tandem queueing system with retrials and reservation of channels as a model of call center. Computers &

Industrial Engineering. 96. pp. 61-71. DOI: 10.1016/j.cie.2016.03.012

9. Kumar, B.K., Vijayakumar, A. & Arivudainambi, D. (2002) An M/G/1 Retrial Queueing System with Two-Phase Service and

Preemptive Resume. Annals of Operations Research. 113(1-4). pp. 61-79. DOI: 10.1023/A:1020901710087

10. Nazarov, A.A. & Moiseeva, S.P. (2006)Metody asimptoticheskogo analiza v teorii massovogo obsluzhivaniya [The Asymptotical Analysis Method in Queueing Theory]. Tomsk: NTL.

11. Nazarov, A. & Chernikova, Ya. (2015) Gaussian Approximation of Distribution of States of the Retrial Queueing System with r-Persistent Exclusion of Alternative Customers. Information Technologies and Mathematical Modelling. Queueing Theory and Applications: Procceding of the 14th International Scientific Conference. 564. pp. 200-208. DOI: 10.1007/978-3-319-25861 -4_19