Исследование RQ-системы M|E2|1 с вытеснением заявок и сохранением фазовой реализации обслуживания | Вестн. Том. гос. ун-та. Управление, вычислительная техника и информатика. 2018. № 42. DOI: 10.17223/19988605/42/8

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

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

Research of RQ-system M|E2|1 with request displacement and conserving phase realization of servicing.pdf В литературе показано, что адекватными математическими моделями телекоммуникационных сетей связи являются 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). Орбита Яч-Яя- CT/iQ, а,' а. В(х) Рис. 1. RQ-система M|E2|1 с вытеснением заявок На вход системы поступает простейший поток заявок с интенсивностью L Требование, заставшее прибор свободным, занимает его для обслуживания в течение времени, подчиняющегося гиперэкспоненциальному распределению B(x) с параметрами q, Ц1, Ц2. С вероятностью q заявка обслуживается экспоненциально распределенное время с параметром Ц1 (1 фаза), с вероятностью 1 - q заявка обслуживается экспоненциально распределенное время с параметром Ц2 (2 фаза). Если прибор занят, то поступившая заявка вытесняет обслуживаемую и сама занимает прибор для обслуживания, а заявка, которая обслуживалась, переходит на орбиту. Орбита разделяется на две зоны. Если заявка обслуживалась на первой фазе, то уходит в первую зону орбиты, если на второй фазе, то на вторую. В зонах орбиты заявки осуществляют случайную задержку, продолжительность которой имеет экспоненциальное распределение с параметром oi для первой зоны и 02 для второй. Из орбиты после случайной задержки заявка вновь обращается к прибору с повторной попыткой его захвата. Дисциплина обращений заявок с орбиты принципиально отличается от дисциплины обращения заявок, которые впервые прибыли в систему, так как для первичных заявок номер фазы определяется случайным образом с вероятностью q, а при повторном обращении номер фазы выбирается однозначно по номеру зоны. Так как орбита разделяется на две зоны, то заявки, находящиеся на орбите в первой зоне, будут осуществлять задержку с экспоненциально распределенным временем с параметром 01 = yio, на орбите во второй зоне - с параметром 02 = Y20. Обозначим /1(Y) - число заявок на орбите в первой зоне, /2(0 - число заявок на орбите во второй зоне. Пусть k(t) определяет состояние прибора следующим образом: 0, если прибор свободен, к (t) = < 1, если прибор занят заявкой, находящейся на первой фазе обслуживания, 2, если прибор занят заявкой, находящейся на второй фазе обслуживания. Ставится задача нахождения совместного трехмерного распределения вероятностей чисел заявок в зонах на орбите и состояний прибора. 2. Система уравнений Колмогорова для частичных характеристических функций Рассмотрим трехмерный процесс {к(t), z'j(t), i2(t)}. Обозначим P {к(t) = к, i1 (t) = '1, i2 (t) = i2 } = Рк (', i2), к = 0,1, 2 стационарную вероятность того, что прибор в момент времени t находится в состоянии k, на орбите в первой зоне находится /1 заявок, на орбите во второй зоне находится /2 заявок. Введем частичные характеристические функции следующего вида: да да Нк(щ, u2) = да да Рк, i2), к = 0,1,2, ix = 0 i 2 = О где j = >/-1 - мнимая единица. Запишем систему для частичных характеристических функций: -XH0(u1,u2) + МдМ! + j'a2 дддu2) + ^ад,u2) + ц2И2(иъu2) = 0, Н du2 -Хдх (u, u2 ) - д (u, u2 ) + XqH0 (u, u2 ) + Xqe Jlt2H2 (ux, u2 ) + \qe1U1Hx (ux, u2 ) + дд (u, u ) -u. дНп (u, u9 ) u. -ju дд (u, щ ) +Jct2--- Me ju1-0V 1 2 - Jctjeju2 ju1-2V ^ 2 = 0, HU2 дu1 дu1 -XH2 (u, u2 ) - Ц2 д 2 (ux, u2 ) + X(1 - q)H0 (u, u2 ) + X(1 - q^^1! (u, ^ ) + X(1 - q)e JU^H2 (u, ^ ) + +j дН^^^^^ u2) - j - дH0(u1, u2) - j eju-u2Hu1.:u2) = 0. дu1 hu2 hu2 Аналитически данную систему решить затруднительно. Будем решать ее методом асимптотического анализа [10] в условии большой задержки, когда среднее время--, а ст^ 0, полагая что ст Ol = oyi, О2 = 072. 3. Асимптотика первого порядка Обозначим x„, n = 1, 2, - асимптотическое среднее значение числа заявок на n-й зоне орбиты, а Rk, к = 0, 1, 2, - распределение вероятностей состояний прибора. Сформулируем следующее утверждение. Теорема 1. Пусть ii(t) - число заявок на орбите в первой зоне, /2(0 - число заявок на орбите во второй зоне RQ-системы с вытеснением заявок и сохранением фазовой реализации. Тогда для последовательности характеристических функций выполняется равенство: lim М exp {щщ^(t) + >2^2(t)} = exP {Ju1x1 + ju2 x2}, ст^0 где xi, X2 являются решением системы уравнений -УЛА) + (k + У 2 X2)R1 - Y1x1R2 = 0 "У2X2R - У2X2R1 + (k + УА )R2 = 0 а вероятности Rk, к = 0, 1, 2, находятся из системы -(Л + у1х1 + У2 x2)R0 + Ц-JRJ + ц2 R2 = 0, (kq + УЛ )R0 - (k(1 - q) + Ц1 + У2x2 ) R1 + (kq + УЛ )R2 = 0, (k(1 - q) + У 2X2 ) R0 + (k(1 - q) + У 2X2 ) R1 - (kq + Ц2 + У1X1) R2 = 0, (2) R0 + R1 + R2 = 1. Из систем уравнений (1), (2) находятся средние числа xi, X2 заявок в зонах на орбите и распределение вероятностей Rk, к = 0, 1, 2, состояний прибора. Для более детального исследования рассмотрим асимптотику второго порядка. 4. Асимптотика второго порядка Построим гауссовскую аппроксимацию числа заявок на орбите. Сформулируем следующее утверждение. Теорема 2. Пусть i 1(t) - число заявок на орбите в первой зоне, i2(t)- число заявок на орбите во второй зоне RQ-системы с вытеснением заявок и сохранением фазовой реализации. Тогда имеет место предельное равенство: limM exp j ^Й^ + ju2 j = exp {j»2 й, + j»2 & + jj& }, где X1, X2 являются решением систем уравнений (1), (2), величины Q11, Q12, Q22 находятся из неоднородной системы линейных алгебраических уравнений Q11 (yR + У1R2 - y1R0z0 + У ЛZ1 + y1R2Z1 - y1R2Z2 ) + +Q12 (-У2R1 -У2R0Z0 +У2R0Z2 -У2R1z1 + У2R1z2 ) = 1 k(1 - q)R1 + 1УЛ^ + 1 kqR1 + +1R2У1Х1 + 1 R1y2X2 + y1X1R0Z1 - kqR1Z1 + y1X1R2Z1 - k(1 - q)R1Z2 - У2X2R1z2 , Q22 (У2R0 + У2R1 - У2R0У0 + У2R0У2 + У2^2 - У2АЛ ) + +Q12 (-y1R2 "УЛ У0 +y1R0 У "У^У + y1R2 У1 ) = 1 kqR2 + 1У2 X2R0 + 1 R2y1 X1 + (3) +1 k(1 - q)R2 + 1 R1y2X2 - kqR2У + У2X2R0У2 - k(1 - q)R2У2 + У2X2R1y2 - y1X1R2Уl, Qll (-YlR2 - YiRP0 + Yi^Pi + YlR2Pi - YlR22 ) + Ql2 (YlR + YlR2 + Y2R + Y2Rl - Y2RP0 + +Y2R0P2 - Y2RlPl + Y2RlP2 - YlRs0 + YlRsl - YlR2s2 + YlR2sl ) + +Q22 (-Y2Rl - Y2R0s0 + Y2R0s2 + Y2Rls2 - Y2Rlsl ) = -R2Ylxl - RlY2x2 + YA^Pi - XqRlPl + +YlxlR2Pi - X(l - q)RlP2 - Y2x2RlP2 - XqR2sl + Y2x2R0s2 - X(l - q)R2s2 + Y2x2Rls2 - YlxiR2sl Величины Z0, z\, Z2; J0,y\,У2;P0,p\,pi, S0, s\, S2 определяются из систем уравнений (4)-(7) соответственно. Для Z0, z\, Z2: -(X + Y^xi + Y 2 x2) z0 + (Xq + Yixi) zi + (X(l - q) + Y 2 x2) z2 = -Yixi, Mlz0 - (X(l - q) + Ml + Y2x2 ) zl + (X(l - q) + Y2x2 ) z2 = X + Y2x2, Ц2 z0 + (Xq + Yixi) zi- (Xq + Ц2 + Yixi) z2 = -Yixi • -(X + Yixi + Y2x2 ) У0 + (Xq + Ylxl ) У1 + (X(l - q) + Y2x2 ) У2 = -Y2x2 , Ц1У0 - (X(l - q) + Ml + Y2x2 ) У + (X(l - q) + Y2x2 ) У2 = -Y2x2 , Ц2 У0 + (Xq + Yixi) yi- (Xq + Ц2 + Yixi) У2 = X+Yixi • -(X + Yixi + Y 2 x2 ) P0 +(Xq + Ylxl ) Pi +(X(l - q) + Y 2 x2 ) P2 = Y 2 x2, MiP0- (X(l - q) + Mi + Y2x2) Pi + (X(l - q)+y2x2)P2 = -y2^ Ц2 P0 + (Xq+Yixi) Pi- (Xq + Ц2 + Yixi) P2 = X+Yixi • -(X + Yi x + Y2 x2 ) s0 +(Xq + Y x ) s + (X(l - q) + y2 x2 ) s2 = -Yi x, Ms - (X(l - q) + Ml + Y2x2 ) sj + (X(l - q) + y2x2 ) s2 = X + y2x2, M^0 + (Xq + Yjxj) sj - (Xq + M2 + Yix ) s2 = -Yix• (4) Для y0, У\, У2: (5) Для p0, p\, P2: (6) Для s0, s\, s2: (7) Заметим, что доказать асимптотическую гауссовость распределения числа заявок можно, записав характеристическую функцию в виде произведения: j*-Qll + j*-622 + jQl2 \exp{.Axj + Ax2 \. 2 a 2 a a I a a Откуда, выполнив несложные преобразования, получаем H(uj,U2) = expxj + Ax2 + Qll + 622 + ^612 \ . I a a 2a 2a a I Последнее выражение доказывает, что двумерное распределение вероятностей числа заявок на орбите является асимптотически гауссовским. H (ul, u2) = exp ■ 5. Численная реализация Были рассмотрены примеры численного решения систем (1)-(7) для различных значений параметров ц\ и Ц2 функции распределения времени обслуживания B(x) с преобразованием Лапласа-Стилтьеса B* (x) = q(l + -)-1 + (l - q)(l + -)-i Mi M2 и параметров X и o\, 02. Рассмотрим пример для случая X = 2, q = 0,6, у\ = 2, Y2 = 3. На рис. 2 представлен график плотности P(x, y) P(X,y) =-^-exp{- --.f fj^ _ 2 Q12 (x " X1 ) (y " X2) + fci^ Л ( У) 2nQnQ22^^aI { 2 (1 - Qi 2 2 ) I Q i2 Q12 Qi 1Q22 Q222 двумерного распределения вероятностей числа заявок на орбите. Рис. 2. График плотности P(x, y) при значениях = 4 и = 5 В работе [11] была рассмотрена RQ-система с вытеснением заявок, в которой обслуживание после прерывания начинается заново. Целесообразно выполнить сравнение значений асимптотических средних между среднимX, полученным с помощью метода, предложенного в [11], и асимптотическим средним x = xi + Х2, полученным с помощью метода асимптотического анализа RQ-системы с вытеснением заявок и сохранением фазовой реализации. Таблица 1 Значения асимптотических средних числа заявок на орбите для различных RQ-систем при yi = у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 приведены значения асимптотических средних для RQ-системы с вытеснением и сохранением фазовой реализации x и для RQ-системы, в которой после прерывания обслуживания у заявки обслуживание начинается заново, X при различных значениях параметров времени обслуживания. Как можно видеть из таблицы, среднее значение x суммарного числа заявок на орбите RQ-системы с вытеснением заявок и сохранением фазовой реализации в 3-4 раза меньше среднего числа заявок X RQ-системы с вытеснением заявок, в которой обслуживание после прерывания начинается заново. Заключение В данной работе была исследована RQ-система с вытеснением заявок и с сохранением фазовой реализации методом асимптотического анализа в предельном условии большой задержки заявок на орбите. Для нее получены уравнения для нахождения среднего числа заявок на орбите i(t) = ii(t) + /2(0, а также уравнения для нахождения стационарного распределения вероятностей состояний прибора. Модифицирован метод асимптотического анализа для исследования RQ-систем с сохранением фазовой реализации и вытеснением заявок. Было показано, что асимптотическая характеристическая функция числа заявок на орбите является асимптотически гауссовской. Был проведен численный анализ системы. Для конкретных значений параметров были получены асимптотические средние числа заявок на орбите, а также вторые центральные моменты и коэффициент корреляции между заявками на орбите в первой и второй зонах. Результаты выполненных исследований могут позволить решить задачи в области проектирования инфокоммуникационных систем, телекоммуникационных систем, управляемых протоколами случайного множественного доступа. Считаем целесообразным исследовать RQ-систему с дообслуживанием заявок и вытеснением.

Ключевые слова

RQ-система, вытеснение заявок, фазовая реализация, зоны орбиты, большая задержка, RQ-system, request displacement, phase realization, orbit zones, large delay

Авторы

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

Ссылки

Artalejo J.R. Accessible Bibliography on Retrial Queues // Progress in 2000-2009 Mathematical and Computer Modeling. 2010. V. 51. P. 1071-1081.
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.
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.
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.
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.
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.
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.
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.
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.
Назаров А.А., Моисеева С.П. Методы асимптотического анализа в теории массового обслуживания. Томск : Изд-во НТЛ, 2006. 112 c.
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.
 Исследование RQ-системы M|E2|1 с вытеснением заявок и сохранением фазовой реализации обслуживания | Вестн. Том. гос. ун-та. Управление, вычислительная техника и информатика. 2018. № 42. DOI: 10.17223/19988605/42/8

Исследование RQ-системы M|E2|1 с вытеснением заявок и сохранением фазовой реализации обслуживания | Вестн. Том. гос. ун-та. Управление, вычислительная техника и информатика. 2018. № 42. DOI: 10.17223/19988605/42/8