Асимптотический анализ многофазной бесконечнолинейной ресурсной системы массового обслуживания с входящим MMPP потоком | Вестник Томского государственного университета. Управление, вычислительная техника и информатика. 2018. № 45. DOI: 10.17223/19988605/45/2

Асимптотический анализ многофазной бесконечнолинейной ресурсной системы массового обслуживания с входящим MMPP потоком

Рассматривается бесконечнолинейная ресурсная система массового обслуживания MMPP/(GI/«)m. Решается задача исследования ^.M-мерного процесса чисел занятых приборов и суммарных объемов занятого ресурса на фазах системы в стационарном режиме функционирования. С помощью метода асимптотического анализа получена асимптотическая характеристическая функция распределения вероятностей исследуемого многомерного процесса, которая совпадает с характеристической функцией многомерного гауссовского распределения.

Asymptotic analysis of resource infinite-server queueing tandem with MMPP arrivals.pdf Математические модели бесконечнолинейных систем массового обслуживания представляют большой интерес для практического применения в области телекоммуникаций, например для моделирования беспроводных сетей связи с целью оптимизации существующих и проектирования новых сетей [1-2]. Кроме того, такие системы важны при моделировании инженерных устройств, где необходимо вычислить достаточный объем буфера для хранения данных. Так как необходимо учитывать объем передаваемой информации, то в связи с этим актуальной является разработка новых ресурсных моделей, сформулированных в терминах систем массового обслуживания (СМО), которые бы позволили оценить объемы занятого ресурса [3-4]. К сожалению, аналитические результаты получены лишь для систем с входящим простейшим потоком заявок и экспоненциальным временем обслуживания, которые не всегда соответствуют реальным сетям [5-7]. В настоящее время появляется все больше работ, посвященных исследованию многофазных систем массового обслуживания, которые состоят из нескольких последовательно соединенных подсистем, причем входящий поток каждой последующей подсистемы является выходящим для предыдущей, кроме последней. 1. Постановка задачи Рассмотрим M-фазную ресурсную СМО с неограниченным числом приборов и неограниченным объемом предоставляемого ресурса на каждой фазе. На вход системы поступает MMPP-поток заявок, управляемый цепью Маркова k(t) = 1, 2, ... K, которая задается матрицей инфинитезимальных характеристик Q = ||qj|| размера K х K, и диагональной матрицей условных интенсивностей Л = diag{X1,...,X,k} . Поступающее требование занимает любой свободный прибор на первой фазе, где обслуживается в течение случайного времени Т1 > 0 с функцией распределения B\(x) = P(i1 < x} и формирует запрос на предоставление случайного объема ресурса v > 0 с функцией распределения G(y) = P{v < y}. По окончании обслуживания на первой фазе заявка освобождает тот же объем ресурса, мгновенно переходит на вторую фазу, где обслуживается в течение случайного времени Т2 > 0 с функцией распределения B2(x) = Р{т2 < x} и занимает тот же объем ресурса, как и на первой фазе. И так далее; после окончания обслуживания наМ-й фазе заявка покидает систему и освобождает занимаемый ресурс. Пусть im(t) - число заявок на m-й фазе в момент времени t, Vm(t) - суммарный объем занятого ресурса на m-й фазе в момент времени t, где т = 1,м - номер фазы. Поставим задачу нахождения характеристик многомерного случайного процесса {i(t), V(t)} = {i (t),...,iM (t),V\ (t),..VM (t)}. Отметим, что исследуемый процесс не является марковским. Для его исследования применим метод многомерного динамического просеивания [8]. Изобразим M параллельных осей времени, пронумерованных от 0 до M (рис. 1). Ось под номером 0 будет отображать события входящего потока, ось под номером 1 будет соответствовать первому просеянному потоку, ось под номером 2 - второму и т.д., ось под номером M соответствует M-му просеянному потоку. Рис. 1. Просеивание входящего потока Пусть имеется набор функций Sm(t), т = 1,М , значения которых лежат в диапазоне [0, 1] и обладают свойством M MSm (t )< 1 m=\ для любых t. Событие входящего потока может просеяться только на одну из осей либо не просеяться ни на одну. Вероятность того, что заявка входящего потока, поступившая в систему в момент времени t > to, сформирует событие потока на m-й оси, то есть к моменту времени T будет находиться на обслуживании на m-й фазе, равна Sm (t) = B*m-1 (T-1)-B*m (T-1), где B*m (x) = (Bm_1 ■ Bm)(x) - свертка функций распределения Bm-i(x), Bm(x) длительности обслуживания на фазах системы. Вероятность того, что зам явка не сформирует событие ни на одной из осей, равна S0 (t) = 1 - X Sm (t), т.е. к моменту времени T m=1 заявка закончит обслуживание на всех фазах и покинет систему. Обозначим nm(t) - число событий, наступивших на m-й оси просеянного потока до момента t, Wm(t) - суммарный объем занятого ресурса просеянными заявками на m-й оси. Как показано в [8], многомерное распределение вероятностей числа заявок на фазах системы в момент времени T совпадает с многомерным распределением вероятностей числа просеянных заявок на соответствующие оси: P {i (T )= m} = P {n (T ) = m} для ливо любых m = [m!,...,mM ]. Нетрудно показать, что для исследуемого процесса {i(t), V(t)} справед- P{i (T ) = m, V (T )< z} = P {n (T ) = m, W (T )< z} (1) для любых m = [m1,..., mM ] и любых z = [z1,..., zM ]. Следует отметить, что неравенства V (T )< z , W(T)< z подразумевают поэлементное сравнение векторов, т.е. W1 (T)< Z1 и т.д. Будем использовать равенство (1) для исследования процесса {i(t), V(t)} с помощью исследования процесса {n(t), W(t)} . 2. Система дифференциальных уравнений Колмогорова Добавим компоненту k(t) - состояние управляющей цепи Маркова в момент времени t, к процессу {n(t), W(t)}, тогда полученный многомерный процесс будет являться марковским. Введем обозначение для его распределения вероятностей: P(k,n,w,t) = P{k(t) = k,n(t) = n, W(t) < w}. Для этого распределения составим At-методом прямую систему дифференциальных уравнений Колмогорова. По формуле полной вероятности запишем: P(k, n, w, t + At) = P(k, n, w, t) (1 - Xk At) (1 + qk At)+P(k, n, w, t )Xk AtS0 (t) + M wm + 1 К AtSm (t) J P (k, n - em, w - y m, t )dG (y)+ £ qvk AtP (V, n, w, t) + о (At) . (2) m=1 0 v^k Из (2) получаем систему дифференциальных уравнений Колмогорова + эт^(So (t)-1) P (k, n, w, t) + X qvkAtP ( V, n, w, t) + X XA (t) 1p (k, n - em , w - ym , t)dG (y) (3) v^k m=1 0 дляk = K; n = [щ,...,nM],w = [w,...,wM]. Начальное условие для решения P(k, n, w, t) в момент времени to определим в виде: , ч fr (k). n = w = 0. P(k,n,w,to) = fn( ) [0, иначе. где r(k) - стационарное распределение вероятностей состояний цепи Маркова k(t). Введем частичные характеристические функции вида: да да да да h(k,u, v,t)= eJU1n1 Jejv1w1 •... • eJUMnM Je^Mp(k,n,dw,t) , «1=0 0 «M =° 0 где j = V-T - мнимая единица. Тогда (3) можем переписать в виде следующей системы уравнений: 8k(k'U'V,t) =Xqvkh(k,u,v,t)+ Xk XSm(t)h(k,u,v,t)(eJUmG*(vm)-1 ot V m=1 V для k = 1, K, где да G* ( v) = J ejvydG (y) . 0 Перепишем эту систему в виде матричного уравнения: ЛM Sm (t)( eJUmG* (v„)- 1l + Q 8H (u, v, t) V = H (u, v, t) (4) 8t с начальным условием H(u, v, t0 ) = r, (5) где H (u, v, t ) = [h (1, u, v, t),..., h (K, u, v, t)], m=1 r = [r(1), ..., r(K)] - вектор стационарного распределения вероятностей состояний управляющей цепи Маркова k(t), удовлетворяющий системе frQ = 0, 1 Q 1 (6) vre = 1, и e - единичный вектор-столбец. 3. Метод асимптотического анализа Для решения задачи (4)-(5) воспользуемся методом асимптотического анализа [8] в условии растущей интенсивности входящего потока и предельно частых изменений состояний цепи Маркова [9-12]. Подставим в уравнение (4) Л = NAi и Q = NQi, где N ^ да - некоторый параметр, который используется для асимптотического анализа. Тогда можно записать (7) 1 SH(u,v,t) , ЧГ м ( ju * Л - (я; , 1 = H(u,v,t) Лх м Sm (t)l eJUmG (Vm)-1 + Qi N St _ m=1 V J с начальным условием (5). Теорема 1. Асимптотическая характеристическая функция первого порядка многомерного случайного процесса {n(t), W(t)} имеет вид: Г м t Г H (u, v, t) = r exp i NX M ( jUm + j^ ) I Sm ( T) dx\ , [ m=l t0 J где X = r^e - интенсивность входящего потока, ai - средний объем занимаемого одной заявкой ресурса. Доказательство. Обозначим -1 = 8, u = 8Х, V = 8y, H (u, v, t) = F1 (X, y, t,8) . (8) (9) Перепишем задачу (7)-(5) с учетом введенных обозначений: SF (х,y,t,8) ЧГ м ( jex * Л 8 1 ( I = F1 (х,y,t,8) Л1 MSm (t)( ejXmG (sym)-1 + Q1 St m=1 V J с начальным условием F1 (X,y,to,8) = r . (10) Найдем асимптотическое решение задачи (9)-(10) в два этапа. Этап 1. Подставляя в (9) s = 0, получим F1 (х, y, t) Q1 = 0 . Сравнивая это уравнение с первым в системе (6), можно сделать вывод, что его можно записать в виде: F (х, y,t ) = гФ^ (х, y, t), (11) где ф(х, y, t) - некоторая скалярная функция, которая удовлетворяет условию: Ф1 ( х, y, to ) = 1. (12) Этап 2. Умножим (9) на вектор e, подставим (11), учитывая разложение ejsx = 1 + jex + O(s2 ) , (13) разделим результаты на s и произведем предельный переход при s ^ 0. Тогда, учитывая, что Qie = 0 и re = 1, для функции Ф1 (х,У^) получим следующее дифференциальное уравнение: (х, y, t) ч м = фг (х, y, t )X M Sm (t)( jXm + jyma, ) . (14) St m=1 Проинтегрировав уравнение (14) от to до t, учитывая начальное условие (12), получим Г M t 1 Ф1 (X,y, t) = exp j X X (jxm + jyma1) J Sm (T)dT [. [ m=1 t0 J Подставляя это выражение в (11) и выполняя замены, обратные к (8), получим H(u, v, t) = F (X, y,t, e) * F (X, y, t) = Г M t 1 f M t 1 = r exp

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

многофазная система массового обслуживания, объем ресурса, метод асимптотического анализа, гауссовская аппроксимация, queueing tandem, random resource, method of asymptotic analysis, Gaussian approximation

Авторы

ФИООрганизацияДополнительноE-mail
Галилейская Анастасия Александровна Томский государственный университет магистрант кафедры теории вероятностей и математической статистики Института прикладной математики и компьютерных наукlusta.nastya@mail.ru
Лисовская Екатерина Юрьевна Томский государственный университет аспирант кафедры теории вероятностей и математической статистики Института прикладной математики и компьютерных наукekaterina_lisovs@mail.ru
Всего: 2

Ссылки

Тихоненко О.М. Моделирование процессов и систем обработки информации : курс лекций. Минск: Белорус. гос. ун-т, 2008. 148 с.
Вихрова О.Г., Сопин Э.С. Анализ показателей качества сети LTE с помощью систем массового обслуживания с ограничен ным ресурсом и случайными требованиями // Современные информационные технологии и ИТ-образование. 2015. Т. 2, № 11. С. 185-191.
Morozov E.V., Potakhina L.V. Speed-up estimation of a system with random volume customers // Распределенные компьютерные и телекоммуникационные сети: управление, вычисление, связь (DCCN-2016) : материалы 19-й междунар. науч. конф. М. : Моск. ун-т дружбы народов, 2016. C. 334-336.
Наумов В.А., Саймулов К.Е., Самуйлов А.К. О суммарном объеме ресурсов, занимаемых обслуживаемыми заявками // Ав томатика и телемеханика. 2016. № 8. С. 125-135.
Sengupta B. The Spatial Requirement of M/G/1 Queue or: How to Design for Buffer Space Modeling and Performance Evaluation Methodology // Lect. Notes Contr. Inf. Sci. / F. Baccelli, G. Fayolle, eds. Berlin, 1984. V. 60. P. 547-562.
Тихоненко О.М. Распределение суммарного объема сообщений в системах массового обслуживания с групповым поступ лением // Автоматика и телемеханика. 1987. № 11. С. 111-120.
Тихоненко О.М. Распределение суммарного объема сообщений в однолинейной системе массового обслуживания с груп повым поступлением // Автоматика и телемеханика. 1985. № 11. С. 78-83.
Моисеев А.Н., Назаров А.А. Бесконечнолинейные системы и сети массового обслуживания. Томск : Изд-во НТЛ, 2015. 240 с.
Назаров А.А., Моисеева С.П. Метод асимптотического анализа в теории массового обслуживания. Томск : Изд-во НТЛ, 2006. 112 с.
Лисовская Е.Ю., Моисеева С.П. Асимптотический анализ системы MMPP|GI|<» с обслуживанием требований случайного объема // Труды Томского государственного университета. Сер. физико-математическая. Т. 299: Математическое и программное обеспечение информационных, технических и экономических систем : материалы IV Междунар. молодежной науч. конф. Томск, 20-21 мая 2016 г. Томск : Издательский Дом ТГУ, 2016. С. 99-104.
Лисовская Е.Ю., Моисеева С.П. Исследование бесконечнолинейной системы массового обслуживания требований случайного объема с входящим MMPP-потоком // Информационные технологии и математическое моделирование (ИТММ-2016) : материалы XV Междунар. конф. им. А.Ф. Терпугова. Катунь, 12-16 сентября 2016 г. Томск : Изд-во Том. ун-та, 2016. Ч. 1. С. 77-82.
Лисовская Е.Ю., Моисеева С.П. Суммарный объем заявок в бесконечнолинейной системе массового обслуживания с рекуррентным входящим потоком // Распределенные компьютерные и телекоммуникационные сети: управление, вычисление, связь (DCCN-2016) : материалы Девятнадцатой междунар. науч. конф., 21-25 ноября 2016 г. М. : РУДН, 2016. С. 313-325.
 Асимптотический анализ многофазной бесконечнолинейной ресурсной системы массового обслуживания с входящим MMPP потоком | Вестник Томского государственного университета. Управление, вычислительная техника и информатика. 2018. № 45. DOI: 10.17223/19988605/45/2

Асимптотический анализ многофазной бесконечнолинейной ресурсной системы массового обслуживания с входящим MMPP потоком | Вестник Томского государственного университета. Управление, вычислительная техника и информатика. 2018. № 45. DOI: 10.17223/19988605/45/2