We suggest a recursive algorithm for calculating the stationary probabilities and probability characteristics of queueing system with random resource requirements. Consider the system with multiple classes of resource requirements described by a random vector. Each class of customers requires a random vector of resources to be served. Unlike to well-known models with constant requirements of resource units we analyse model with random requirements with both discrete and continuous resources. The key difference from already analysed model with random requirements concerns the volume of released resources at the end of customer service. General model requires to store all vectors of occupied resources, while described model deals with the total volume of occupied resources. Upon departure from the system, customer releases not the same volume of resources as it occupied, but some random volume which is independent from previous system‘s state and incoming flow. It was proved that in case of Poisson arrivals and exponential service time the general system is equivalent to the simplified system that deals with only total amount of occupied resources. Proposed simplification lowers the complexity of calculation algorithms. Then, we consider aggregation of customers with the same class of requirements. Summing up stationary probabilities over each class, we derived a formula for the normalized average requirement. The computing performance significantly depends on length of vector of resources and number of customers. To avoid calculating of all k-fold convolutions for each set of vectors we suggest the recursive algorithm. The algorithm is applied for calculation of blocking probability and vector of average occupied resources. Queueing system with random resource requirements adequately models radio resource allocation in modern heterogeneous networks and forthcoming 5G networks.
The work was financially supported by the Ministry of Education and Science of the Russian Federation (the Agreement number 02.A03.21.0008) and is partially supported by RFBR research projects No 15-07-03051, 16-07-00766.
Copyright © 2017 for the individual papers by the papers’ authors. Copying permitted for private and academic purposes. This volume is published and copyrighted by its editors.
In: K. E. Samouilov, L. A. Sevastianov, D. S. Kulyabov (eds.): Selected Papers of the VII Conference “Information and Telecommunication Technologies and Mathematical Modeling of High-Tech Systems”, Moscow, Russia, 24-Apr-2017, published at http://ceur-ws.org Разработан алгоритм вычисления стационарных вероятностей и ключевых вероятностных характеристик системы массового обслуживания (СМО) с ограниченным ресурсом и случайными требованиями. Рассматривается система со случайными требованиями нескольких классов, в которой каждой заявке для обслуживания необходимо выделить некоторый случайный вектор ресурсов. Отличие рассматриваемой исследуемой модели от классических ресурсных моделей теории массового обслуживания заключается в занятии не фиксированного количества единиц ресурса, а некоторого случайного объема, который может быть задан как непрерывной, так и дискретной случайной величиной. В отличие от известных моделей со случайными требованиями, предполагается, что поступившая на обслуживание заявка занимает случайный объем ресурсов, при этом по завершении обслуживания заявки будет освобожден также некоторый случайный объем ресурсов, отличный от занятого. Вместо того, чтобы запоминать для каждой заявки вектор занятых ею ресурсов, в рассматриваемой модели достаточно определить объем ресурсов, занимаемый всеми заявками. Предположение о суммарном объеме занятых ресурсов существенно упрощает дальнейший анализ случайного процесса во времени и уменьшает размерность пространства состояний СМО. Данное предположение было доказано для системы с пуассоновским входящим потоком и экспоненциальным временем обслуживания заявок: стационарные вероятности и вероятностные характеристики исходной и упрощенной моделей эквивалентны.
Объединение требований нескольких классов в один поток заявок со средневзвешенным требованием позволило упростить формулы для вычисления вероятности блокировки системы и среднего объема занятых ресурсов. К полученным формулам применяется разработанный рекуррентный алгоритм, который позволяет существенно сократить время вычислений и использование вычислительных ресурсов. Предложенная модель с ограниченным ресурсом и случайными дискретными требованиями применима к анализу показателей качества беспроводных сетей связи четвертого и пятого поколений.
Публикация подготовлена при финансовой поддержке Минобрнауки России (соглашение № 02.А03.21.0008), а также при поддержке РФФИ в рамках проектов № 15-07-03051, 16-07-00766.
Ключевые слова: СМО с ограниченным ресурсом, требования случайного объема, нормировочная константа, рекуррентный алгоритм, гетерогенная сеть.
1. Введение
В классических моделях Эрланга или Келли [
В [
Формулы для нахождения стационарных вероятностей системы требуют вычисления k-кратных сверток для каждого k = 0; N и для всех возможных наборов векторов длины M . В данной работе разработан рекуррентный алгоритм вычисления нормировочной константы, существенно упрощающий вычисление стационарных вероятностей СМО, вероятности блокировки и средний объем занятых ресурсов. 2.
Описание модели
По мнению экспертов инфокоммуникационной отрасли, к 2020 году произойдет
полномасштабное развёртывание инфраструктур технологии 5G [
X k1+ +kL=n
k1 kL p(1k;r11) : : : p(Lk;LrL) k1! 1 : : : L ; kL! 0 N
X
X
X n=0 k1+ +kL=n r1+ +rL=R k1 p(1k;r11) : : : p(Lk;LrL) k1! 1 : : : L kL! A
: Рассматриваемая модель позволяет проводить анализ характеристик сети с учетом динамики установления соединений.
Исследуется многолинейная СМО с ограниченным ресурсом, заданным вектором R = (R1; : : : ; RM ). В систему поступает пуассоновский поток заявок L классов с интенсивностями l, каждый из которых требует случайный вектор rl = (r1l; : : : ; rMl) ресурсов, векторы rl независимы от входящего потока и независимы в совокупности требования к ресурсу m-го типа. Времена обслуживания заявок имеют экспоненциальное распределение с параметром l, независимы от процесса поступления заявок и независимы в совокупности. Пусть заявка l-го класса занимает rl единиц ресурсов с вероятностью pl;rl , тогда kl таких заявок будут R занимать r единиц ресурсов с вероятностью pl(;krl), где pl(;kr) = P pl;rpl(;kr 1) – kj=0 кратная свертка вероятностей pl;r. Стационарные вероятности СМО могут быть найдена по формулам (1) и (2): (1) (2) (3) (4) (5) (6) а, следовательно, и основные вероятностные характеристики, такие как вероятность блокировки системы (5) и средний объем занятых ресурсов (6): qn (r) = q0p(rn) n ;
n!
3. Алгоритм вычисления нормировочной константы
Для расчетов характеристик СМО по формулам (5), (6) необходимо для
каждого k 2 f0; : : : ; N g и всех наборов векторов r 6 R хранить в памяти компьютера
значения сверток вероятностей pr. При больших значениях N и R, вычисление
блокировок СМО и объемов занятого ресурса по полученным формулам
нерационально. Чтобы сократить время вычисления характеристик был разработан
рекуррентный алгоритм вычисления нормировочной константы G (N; R) = q0 1. Также
были получены рекуррентные формулы для нахождения вероятностных
характеристик СМО. В основе алгоритма лежит принцип, описанный в [
G (n =
N R 1; r) = X X pr(n) Доказательство. Аналогично из (5) получена вероятность блокировки СМО: = n r n!
1)! j=0 n 1 r i
X pj(n 1)A =
1 0 = n!
j=0 n r
X pj (G (n 1; r j)
G (n 2; r j)) : B = 1 q0 X N 1 n XR Xj pipj i(n) = N 1 n XR pj(n+1) = 1 G 1 (N; R) X n=0 n! j=0 n=0 n! j=0 i=0
N 1 n RXi pj(n) = 1 G 1 (N; R) X pjG (N 1; R j):
R R = 1 G 1 (N; R) X pi X
i=0 n=0 n! j=0 j=0 Следствие 2. Средний объем занятых ресурсов b можно вычислить по формуле (10): b = R
M Rm G 1 (N; R) X em X G (N; R iem) : m=1 i=1 (10) Доказательство. b(2) = 2 XR r XR XN qn (j) = 2 XR r XR XN G 1 (N; R) nn! pjn =
r=0 j=r n=0 r=0 j=r n=0 = 2G 1 (N; R) XR r @0XR XN n pn r=0 j=r n=0 n! j
RXr XN N 1 j=0 n=0 nn! pjn + X
n=0 nn! prnA =
R N ! = 2G 1 (N; R) rX=0 r G (N; R) G (N; R j) + nX=0 nn! prn = Получены рекуррентные формулы для вычисления стационарных вероятностей, вероятности блокировки, вектора среднего объема занятых ресурсов и дисперсии модели с ограниченными ресурсами и случайными требованиями. Разработан рекуррентный алгоритм вычисления нормировочной константы, существенно упрощающий анализ СМО и вычисление ее ключевых вероятностных характеристик.
Литература