=Paper=
{{Paper
|id=Vol-1995/paper-12-969
|storemode=property
|title=
Вычисление вероятностных характеристик СМО со случайными
требованиями
(Probability Characteristics Cvaluation in Queueing System with Random
Requirements)
|pdfUrl=https://ceur-ws.org/Vol-1995/paper-12-969.pdf
|volume=Vol-1995
|authors=Eduard S. Sopin,Olga G. Vikhrova
}}
==
Вычисление вероятностных характеристик СМО со случайными
требованиями
(Probability Characteristics Cvaluation in Queueing System with Random
Requirements)
==
https://ceur-ws.org/Vol-1995/paper-12-969.pdf
85
Probability Characteristics Cvaluation in Queueing System
with Random Requirements
Eduard S. Sopin‡§ , Olga G. Vikhrova‡
‡
Peoples’ Friendship University of Russia (RUDN University)
§
Institute of Informatics Problems
Federal Research Center “Computer Science and Control”
Email: sopin_es@rudn.university, vikhrova_og@rudn.university
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 Rus-
sian Federation (the Agreement number 02.A03.21.0008) and is partially supported by RFBR
research projects No 15-07-03051, 16-07-00766.
Key words and phrases: queuing system with random requirements, limited resource,
recursive algorithm, normalization constant, heterogeneous networks.
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
86 ITTMM—2017
Вычисление вероятностных характеристик СМО со
случайными требованиями
Э. С. Сопи퇧 , О. Г. Вихрова‡
‡
Российский университет дружбы народов
§
Институт проблем информатики ФИЦ ИУ РАН
Email: sopin_es@rudn.university, vikhrova_og@rudn.university
Разработан алгоритм вычисления стационарных вероятностей и ключевых вероят-
ностных характеристик системы массового обслуживания (СМО) с ограниченным ре-
сурсом и случайными требованиями. Рассматривается система со случайными требова-
ниями нескольких классов, в которой каждой заявке для обслуживания необходимо вы-
делить некоторый случайный вектор ресурсов. Отличие рассматриваемой исследуемой
модели от классических ресурсных моделей теории массового обслуживания заключа-
ется в занятии не фиксированного количества единиц ресурса, а некоторого случайного
объема, который может быть задан как непрерывной, так и дискретной случайной ве-
личиной. В отличие от известных моделей со случайными требованиями, предполагает-
ся, что поступившая на обслуживание заявка занимает случайный объем ресурсов, при
этом по завершении обслуживания заявки будет освобожден также некоторый случай-
ный объем ресурсов, отличный от занятого. Вместо того, чтобы запоминать для каждой
заявки вектор занятых ею ресурсов, в рассматриваемой модели достаточно определить
объем ресурсов, занимаемый всеми заявками. Предположение о суммарном объеме за-
нятых ресурсов существенно упрощает дальнейший анализ случайного процесса во вре-
мени и уменьшает размерность пространства состояний СМО. Данное предположение
было доказано для системы с пуассоновским входящим потоком и экспоненциальным
временем обслуживания заявок: стационарные вероятности и вероятностные характери-
стики исходной и упрощенной моделей эквивалентны.
Объединение требований нескольких классов в один поток заявок со средневзвешен-
ным требованием позволило упростить формулы для вычисления вероятности блокиров-
ки системы и среднего объема занятых ресурсов. К полученным формулам применяет-
ся разработанный рекуррентный алгоритм, который позволяет существенно сократить
время вычислений и использование вычислительных ресурсов. Предложенная модель с
ограниченным ресурсом и случайными дискретными требованиями применима к анали-
зу показателей качества беспроводных сетей связи четвертого и пятого поколений.
Публикация подготовлена при финансовой поддержке Минобрнауки России (соглаше-
ние № 02.А03.21.0008), а также при поддержке РФФИ в рамках проектов № 15-07-03051,
16-07-00766.
Ключевые слова: СМО с ограниченным ресурсом, требования случайного объема,
нормировочная константа, рекуррентный алгоритм, гетерогенная сеть.
1. Введение
В классических моделях Эрланга или Келли [1] требования в СМО задаются
постоянными величинами, которые, например, могут определять количество еди-
ниц канального ресурса, необходимого для обслуживания сессии. Авторами рас-
сматривается модель со случайными требованиями, которые могут быть заданы
как непрерывными, так и дискретными случайными величинами. Впервые СМО
со случайными требованиями были описаны в [2]. В [3] получено общее решение
системы в предположении о пуассоновском входящем потоке и экспоненциальном
времени обслуживания заявок. Анализ модели с ограниченным ресурсом и случай-
ными требованиями был продолжен в [4]. Рассматривается СМО с рекуррентным
Сопин Э. С., Вихрова О. Г. 87
входящим потоком и случайными требованиями M типов. Поступившая в систе-
му заявка требует случайный вектор ресурсов и занимает выделенный ей ресурс
на все время обслуживания. По окончании обслуживания заявки освобождается
в точности тот объем ресурсов, который изначально выделялся. В этом случае
необходимо запоминать вектор занятых ресурсов для каждой заявки в системе.
Пространство состояний системы состоит из k подмножеств всех векторов длины
k (M + 1) + 2, анализ системы при больших значениях k числа заявок затрудни-
телен. Предлагается по завершении обслуживания заявки освобождать некоторый
случайный вектор ресурсов, не зависящий от поведения системы в прошлом при
заданном числе заявок k и общем объеме занятых ресурсов. Для упрощенной мо-
дели не нужно запоминать векторы занятых ресурсов, достаточно знать объем
ресурсов, занятых всеми заявками. В [5] было доказано, что стационарные веро-
ятности исходной системы эквивалентны стационарным вероятностям упрощенной
системы в случае пуассоновского входящего потока и экспоненциального времени
обслуживания заявок.
В [6] и [7] анализируется многолинейная СМО со случайными требованиями
нескольких классов и ограниченным ресурсом. Требования к ресурсу определяет
непрерывная случайная величина с функцией распределения F (x). Для данной
системы были получены аналитические формулы для вычисления стационарных
вероятностей, а также были найдены ключевые вероятностные характеристики.
Для исследования задачи разделения ресурсов в беспроводных каналах передачи
данных в гетерогенных сетях связи в [8] анализируется СМО со случайными требо-
ваниями, выраженными дискретной случайной величиной. В более общем случае
модель была исследована в [9]. Авторы предлагают к исследованию многолиней-
ную СМО с дискретными случайными требованиями нескольких классов к множе-
ственным ресурсам. Получены формулы для вычисления стационарных вероятно-
стей СМО, вероятности блокировки системы и среднего объема занятых ресурсов.
В [10] доказано, что стационарные вероятности системы с требованиями несколь-
ких классов эквиваленты стационарным вероятностям СМО со средневзвешенным
требованием. Для полученной модели с агрегированным потоком требований были
получены основные вероятностные характеристики.
Формулы для нахождения стационарных вероятностей системы требуют вычис-
ления k-кратных сверток для каждого k = 0, N и для всех возможных наборов век-
торов длины M . В данной работе разработан рекуррентный алгоритм вычисления
нормировочной константы, существенно упрощающий вычисление стационарных
вероятностей СМО, вероятности блокировки и средний объем занятых ресурсов.
2. Описание модели
По мнению экспертов инфокоммуникационной отрасли, к 2020 году произойдет
полномасштабное развёртывание инфраструктур технологии 5G [11, 12]. Измене-
ния позволят улучшить скорость передачи данных в мобильных сетях [13], а так-
же будут способствовать дальнейшему развитию гетерогенных сетей [14] и нового
класса прямых соединений устройств D2D [15]. Гетерогенная организация совре-
менных беспроводных сетей является доступным и бюджетный способом повысить
пропускную способность современных сетей LTE. Предполагается, что концепция
разделение ВК и НК, предложенная в [16], позволит существенно улучшить пока-
затели качества в ВК и сбалансировать нагрузку в макросоте а также повысить
эффективность использования радио ресурсов. Приведенные в [17, 18] результаты
исследований свидетельствуют о снижении уровня интерференции в ВК и повыше-
нию скорости передачи данных. Существующие модели разделения радиоресурсов
в гетерогенных сетях позволяют моделировать их только в статичном состоянии.
88 ITTMM—2017
Рассматриваемая модель позволяет проводить анализ характеристик сети с учетом
динамики установления соединений.
Исследуется многолинейная СМО с ограниченным ресурсом, заданным век-
тором R = (R1 , . . . , RM ). В систему поступает пуассоновский поток заявок L
классов с интенсивностями λl , каждый из которых требует случайный вектор
rl = (r1l , . . . , rM l ) ресурсов, векторы rl независимы от входящего потока и неза-
висимы в совокупности требования к ресурсу m-го типа. Времена обслуживания
заявок имеют экспоненциальное распределение с параметром µl , независимы от
процесса поступления заявок и независимы в совокупности. Пусть заявка l-го клас-
са занимает rl единиц ресурсов с вероятностью pl,rl , тогда kl таких заявок будут
R
(k ) (k) P (k−1)
занимать r единиц ресурсов с вероятностью pl,rl , где pl,r = pl,r pl,r – k-
j=0
кратная свертка вероятностей pl,r . Стационарные вероятности СМО могут быть
найдена по формулам (1) и (2):
k1 k
n
X (k ) (k ) ρ1 ρLL
q1,...,L (r1 , . . . , rL ) = q0 p1,r11 . . . pL,rL ... , (1)
k1 +···+kL =n
L k1 ! kL !
−1
N k1 k
X X X(k ) (k ) ρ ρ L
q0 = p1,r11 . . . pL,rL 1 . . . L . (2)
L k ! kL !
n=0 k1 +···+kL =n r1 +···+rL =R 1
Поступающий поток заявок нескольких классов может быть объединен в один
L
P ρl
поток средневзвешенных требований с prl = p
ρ l,rl
— вероятностью того, что
l=1
всеми заявками l-го класса будет занято rl единиц ресурса. В этом случае стацио-
нарные вероятности могут быть найдены по формулам (3), (4):
n
(n) ρ
q n (r) = q0 pr , (3)
n!
−1
~
N X
R
X ρn
q0 = pr (n) , (4)
n=0 ~
n!
r =0
а, следовательно, и основные вероятностные характеристики, такие как вероят-
ность блокировки системы (5) и средний объем занятых ресурсов (6):
N −1 R
X ρn X (n+1)
B = 1 − q0 p , (5)
n=0
n! j j
N
X ρn X ~ (n) .
b = q0 Rjpj (6)
n=0
n!
~j
Сопин Э. С., Вихрова О. Г. 89
3. Алгоритм вычисления нормировочной константы
Для расчетов характеристик СМО по формулам (5), (6) необходимо для каж-
дого k ∈ {0, . . . , N } и всех наборов векторов r 6 R хранить в памяти компьютера
значения сверток вероятностей pr . При больших значениях N и R, вычисление
блокировок СМО и объемов занятого ресурса по полученным формулам нерацио-
нально. Чтобы сократить время вычисления характеристик был разработан рекур-
рентный алгоритм вычисления нормировочной константы G (N, R) = q0−1 . Также
были получены рекуррентные формулы для нахождения вероятностных характе-
ристик СМО. В основе алгоритма лежит принцип, описанный в [19], известный как
алгоритм Бузена. Введем обозначение
n X
r k
(k) ρ
X
G (n, r) = pj , n > 0, r > 0.
k=0 j=0
k!
Теорема. Функция G (n, r) удовлетворяет рекуррентному соотношению (7) с
начальными условиями (8)
r
ρ X
G (n, r) = G (n − 1, r) + pj (G (n − 1, r − j) − G (n − 2, r − j)) , (7)
n! j=0
r
X
G (0, r) = 1, r > 0, G (1, r) = 1 + ρ pj . (8)
j=0
Доказательство. Определим шаг индукции:
N X
R N −1 X
R R
X ρn X ρn ρn X (n)
G (n, r) − G (n − 1, r) = pr (n) − pr (n) = pr =
n=0 r=0
n! n=0 r=0
n! n! r=0
r j r r
ρn X X ρn X X
= pi pj−i (n−1) = pi pj−i (n−1) =
n! j=0 i=0 n! i=0 →
−
j= i
r r−i
ρn X ρn−1 X
= pi pj (n−1) =
n! i=0 (n − 1)! j=0
r
ρn X
= pj (G (n − 1, r − j) − G (n − 2, r − j)) .
n! j=0
Следствие 1. Вероятность блокировки системы B может быть вычислена по
формуле (9):
R
X
B = 1 − G−1 (N, R) pj G (N − 1, R − j) . (9)
j=0
Доказательство. Аналогично из (5) получена вероятность блокировки СМО:
90 ITTMM—2017
N −1 R N −1 n X R X j
X ρn X (n+1) X ρ
B = 1 − q0 pj = 1 − G−1 (N, R) pi pj−i (n) =
n=0
n! j=0 n=0
n! j=0 i=0
R N −1 R−i R
X X ρn X (n) X
= 1 − G−1 (N, R) pi pj = 1 − G−1 (N, R) pj G (N − 1, R − j).
i=0 n=0
n! j=0 j=0
Следствие 2. Средний объем занятых ресурсов b можно вычислить по фор-
муле (10):
M
X Rm
X
b = R − G−1 (N, R) em G (N, R − iem ) . (10)
m=1 i=1
Доказательство.
R X
M R X
N R X
M R X
N
X X X X ρn n
b= em qn (j) = em G−1 (N, R) p =
r=0 m=1 j=r n=0 r=0 m=1 j=r n=0
n! j
R X
M R X N R−r N N
−1
X X ρn n X X ρn n X ρn n
= G (N, R) em p − p + p =
n! r
r=0 m=1 j=0 n=0
n! j j=r n=0
n! j n=0
R X M N
!
−1
X X ρn n
= G (N, R) em G (N, R) − G (N, R − r) + p =
r=0 m=1 n=0
n! r
M
X Rm
X
= R − G−1 (N, R) em G (N, R − iem ).
m=1 i=1
Следствие 3. Дисперсия среднего числа занятых ресурсов может быть вычис-
лена по формуле (11), где b2 = b21 , . . . , b2M :
σ 2 = b(2) − b2 , (11)
R
" #
X
b(2) = 2 b + G−1 (N, R) r (G (N, R) − G (N, r)) .
r=0
Доказательство.
R R X N R R X N
X X X X ρn n
b(2) = 2 r qn (j) = 2 r G−1 (N, R) p =
r=0 j=r n=0 r=0 j=r n=0
n! j
R R X N R−r N N
−1
X X ρn n X X ρn n X ρn n
= 2G (N, R) r p − p + p =
n! r
r=0 j=r n=0
n! j j=0 n=0
n! j n=0
R N
!
−1
X X ρn n
= 2G (N, R) r G (N, R) − G (N, R − j) + p =
r=0 n=0
n! r
Сопин Э. С., Вихрова О. Г. 91
R
" #
X
= 2 b + G−1 (N, R) r (G (N, R) − G (N, r)) .
r=0
4. Выводы
Получены рекуррентные формулы для вычисления стационарных вероятно-
стей, вероятности блокировки, вектора среднего объема занятых ресурсов и дис-
персии модели с ограниченными ресурсами и случайными требованиями. Разрабо-
тан рекуррентный алгоритм вычисления нормировочной константы, существенно
упрощающий анализ СМО и вычисление ее ключевых вероятностных характери-
стик.
Литература
1. F. P. Kelly, Loss Networks. The Annals of Applied Probability (1991), Vol. 1, no. 3,
pp. 319–378.
2. O. M. Tikhonenko, Generalized Erlang problem for service systems with finite total
capacity, Problems of Information Transmission (2005), 41 (3), pp. 243–253.
3. V. A. Naumov, K. E. Samouylov, On the modeling of queuing systems with multiple
re-sources, Bulletin of PFUR. Series: Mathematics. Information Sciences. Physics
(2014), no. 3, pp. 58–62 [in Russian].
4. V. A. Naumov, K. E. Samuilov, A. K. Samuilov, On the total amount of resources
occupied by serviced customers, Automation and Remote Control (2016), Vol. 77,
issue 8, pp. 1419–1427.
5. V. Naumov, K. Samuoylov, E. Sopin, S. Andreev, Two approaches to analysis of
queuing systems with limited resources, IEEE: Ultra Modern Telecommunications
and Control Systems and Workshops (ICUMT), 2014, pp. 485–488.
6. K. Samouylov, E. Sopin, O. Vikhrova, Analyzing Blocking Probability in
LTE Wireless Network via Queuing System with Finite Amount of Resources,
Communications in Computer and Information Science (2015), Vol. 564, pp. 393–
403.
7. O. M. Tikhonenko, Destricted Capacity Queueing Systems: Determination of their
Characteristics, Automation and Remote Control (1997), Vol. 58, no. 6, pp. 969–
973.
8. E. Sopin, K. Samouylov, O. Vikhrova, R. Kovalchukov, D. Moltchanov,
A. Samuylov, Evaluating a case of downlink uplink decoupling using queuing system
with random requirements, Lecture Notes in Computer Science (2016), Vol. 9870,
pp. 440–450.
9. K. Samouylov, E. Sopin, O. Vikhrova, On design of efficient algorithm for
blocking probability calculation in queuing system with random requirements, 15th
International Scientific Conference (ITMM), 2016, Vol. 1, pp. 192–197.
10. V. Naumov, K. Samouylov, E. Sopin, N. Yarkina, S. Andreev, A. Samuylov,
LTE Performance Analysis Using Queuing Systems with Finite Resources and
Random Requirements, IEEE: 7th International Congress on Ultra Modern
Telecommunications and Control Systems and Workshops (ICUMT), 2015, pp. 100–
103.
11. Ericsson mobility report, Ericsson AB, 2015, https://www.ericsson.com/
mobility-report
12. Cisco Visual Networking Index: Global Mobile Data Traffic
Forecast Update, 2014–2019, http://www.cisco.com/c/en/us/
92 ITTMM—2017
solutions/collateral/service-provider/visual-networking-index-vni/
mobile-white-paper-c11-520862.html
13. J. Andrews, H. Claussen, M. Dohler, S. Rangan, Femtocells: Past, Present, and
Future, IEEE JSAC, 2012, Vol. 30, no. 3, pp. 497–508.
14. J. Lee, H. Wang, J. Andrews, D. Hong, Outage Probability of Cognitive Relay
Networks with Interference Constraints, IEEE Trans. Wir. Comm. (2011), Vol. 10,
no. 2, pp. 390–395.
15. G. Fodor, S. Parkvall, S. Sorrentino, P. Wallentin, Q. Lu, N. Brahmi, Device-
to-Device Communications for National Security and Public Safety, IEEE Access
(2014), Vol. 2, no. 1, pp. 1510–1520.
16. F. Boccardi, J. Andrews, H. Elshaer, M. Dohler, S. Parkvall, P. Popovski, S. Singh,
Why to Decouple the Uplink and Downlink in Cellular Networks and How To Do
It, IEEE Communications Magazine (2016), Vol. 54, no. 3, pp. 110–117.
17. S. Singh, X. Zhang, J. Andrews, Joint Rate and SINR Coverage Analysis
for Decoupled Up-link-Downlink Biased Cell Associations in HetNets, Wireless
Communication. IEEE Trans. Wireless Commun (2015), Vol. 14, no. 10, pp. 5360–
5373.
18. H. Elshaer, F. Boccardi, M. Dohler, R. Irmer, Downlink and Uplink Decoupling:
A disruptive architectural design for 5G networks, Global Communications
Conference (GLOBECOM), 2014, pp. 1798–1803.
19. J. P. Buzen, Computational algorithms for closed queueing networks with
exponential servers, Communications of the ACM (1973), 16(9), pp. 527.