About Probability Characteristics Evaluation in Queuing System with Limited Resources and Random Requirements

Abstract


Mobile data traffic increases on everyday basis for the last decade and is going to keep this trend in the near future. Exponential growth of data traffic in wireless networks accelerates the development of new technologies and the transition to 5G networks. The ongoing improvements will allow to increase the channels throughput and will allow devices to simultaneously support both cellular and Wi-Fi networks, and even allow direct device-to-device (D2D) connection without any base station involved. Evolving heterogeneous networks promise more efficient radio resources usage by a macro cell traffic offloading to the small cells and uplink and downlink decoupling (DUDe). A resource-sharing model in heterogeneous networks is for the first time proposed to be analyzed in terms of queuing system with random requirements. We suggest a multiserver queuing network with limited resources where each class of customers requires a random vector of resources to be served. It has been proved that stationary probabilities of the system with aggregated flow of customers with mean-weighted requirement are equal to the stationary probabilities of the suggested system. The analytical method for the key probability characteristics evaluation requires calculating all k-fold convolutions for each set of vectors requirements. We propose a recurrent computation algorithm for normalization constant evaluation and efficient formulas for blocking probability, mean volume and variance of the occupied resources.


1. Введение Стремительный рост популярности мобильных приложений, по мнению представителей инфокоммуникационной отрасли, способствует активному развитию технологии 4G и уже к 2020 году приведёт к полномасштабному развёртыванию инфраструктур для технологии поколения 5G [1]. Изменения затронут физический уровень с целью повышения скорости передачи данных, а также коснутся сетевой архитектуры, современные мобильные устройства могут работать в двух режимах - поддерживать сотовое соединения и подключаться к частным сетям малых сот (микро-, пико-, фемтосот) [2]. Новый класс прямых соединений устройств D2D, которые могут осуществляться как внутри полосы пропускания, так и вне выделенной полосы, позволят производить обмен данными минуя базовые станции и не создавать дополнительную нагрузку на существующие каналы [3]. Все предложенные изменения подразумевают более эффективное использование и разделение ресурсов и позволят существенно улучшить пропускную способность беспроводных каналов передачи данных. Принцип гетерогенности сетей, согласно которому происходит наложение зон покрытия макросот и малых сот, оказался самым доступным и бюджетным способом улучшить пропускную способность сетей LTE. Концепция разделения ВК и НК была предложена в [4] и, по мнению авторов, должна повысить эффективность использования радиоресурсов беспроводных сетей. Приведённые в [5, 6] аналитические исследования и результаты имитационного моделирования свидетельствуют о существенном выигрыше в производительности сети при раздельной ассоциации. Существующие модели разделения радиоресурсов в гетерогенных сетях позволяют определить параметры сети при фиксированном количестве пользовательских устройств и не принимают во внимание процессы установления новых соединений и завершения существующих. Чтобы иметь возможность наблюдать за показателями качества сети в динамике, в [7] предложена модель разделения ресурсов со следующими предположениями: 1. поступивший запрос на установление соединения с базовой станцией требует некоторый случайный объем ресурсов нескольких типов; 2. если для обслуживания соединения недостаточно ресурсов, то запрос будет отклонён; 3. устройство занимает требуемый объем ресурсов на все время обслуживания и освобождает его по завершении обслуживания. Модель с требованиями случайного объёма была представлена в [8], её анализ в общем виде предложен автором в [9]. В [10] исследуется общая модель с ограниченным ресурсом и требованиями случайного объёма к различным типам ресурсов. Ресурсы занимаются на все время обслуживания, а по его окончании освобождается ровно тот объем ресурсов, который занимался. Случайный процесс, описывающий поведение системы, должен учитывать объёмы занятых ресурсов каждой из заявок, что существенно усложняет его анализ. Было предложено упрощение, согласно которому по завершении обслуживания заявки освобождается некий случайный вектор ресурсов, не зависящий от поведения системы в прошлом при заданной числе заявок и векторе занятых ресурсов. В [11] и [12] с помощью имитационного моделирования были получены вероятностные характеристики исходной и упрощённой моделей, а также были найдены стационарные вероятности в предположении о пуассоновском входящем потоке заявок и экспоненциальном времени их обслуживания. Было доказано, что полученные значения стационарных вероятностей для обеих моделей эквиваленты. Представленные в работе результаты являются продолжением исследований в [13, 14]. 2. Математическая модель Рассматривается многолинейная СМО ограниченной ёмкости. Число приборов для обслуживания в системе не превышает , а доступный ресурс ограничен вектором R = (1, . . . , ). В систему поступает поток заявок классов, каждой из заявок класса для обслуживания необходимо выделить вектор r = (1, . . . , ) случайных требований к ресурсам типов. Все значения векторов r независимы от входящего потока и независимы в совокупности. Моменты поступления заявок -го класса подчинены пуассоновскому распределению с интенсивностью , а времена обслуживания заявок независимы от процесса поступления заявок, независимы в совокупности и распределены экспоненциально с параметром . Заявка -го класса займёт r единиц ресурсов с вероятностью ,r . Если выражение является -кратной свёрткой вероятностей тогда все заявок класса займут r единиц ресурсов с вероятностью ( ). В [14] было доказано, что распределение стационарных вероятностей рассматриваемой СМО имеет вид (1) с начальным значением (2): Введём функцию (r), просуммировав вероятности (r1, ..., r) по всем векторам занятых ресурсов r = r1 + ... + r: . (3) Теорема 1. Распределение стационарных вероятностей СМО с объединённым входящим потоком со средневзвешенным требованием задаётся формулами: Доказательство. Просуммируем обе части равенства (1) по всем векторам r, r1 + ... + r = r Покажем теперь, что (r) является k -кратной свёрткой вероятностей r и (r) = (). Пусть zr = (1 , . . . , ), тогда производящая функция Π (z) для (r) имеет вид также является производящей функцией. Произведение k функций (z) является k -кратной свёрткой средневзвешенного требования r, т.е. Теорема 1 позволяет получить аналитические формулы для вероятности блокировки и среднего объёма занятых ресурсов b: 3. Рекуррентный алгоритм Формулы (5) требуют вычисления -кратных свёрток вероятностей r для всех возможных векторов r�R. Чтобы понизить вычислительную сложность формул, был разработан алгоритм для вычисления нормировочной константы (, R) = 0-1, аналогичный алгоритму в [15]. C помощью нормировочной константы были получены рекуррентные формулы для нахождения вероятностных характеристик СМО. Введём обозначение: Теорема 2. Функция (, r) удовлетворяет рекуррентному соотношению (6) с начальными условиями (7): Доказательство. Зададим шаг индукции: Следствие 1. Вероятность блокировки системы вычисляется по формуле: Доказательство. Получим из (4) рекуррентную формулу для вероятности блокировки СМО с учётом (6): Следствие 2. Средний объем занятых ресурсов b вычисляется по формуле: Следствие 3. Второй момент числа занятых ресурсов может быть найден по формуле: где b2 = 12, . . . , 2 . Тогда дисперсия объёма занятых ресурсов 2 = b(2) - b2. Доказательство. 4. Заключение Многолинейную СМО ограниченной ёмкости с вектором случайных требований к ресурсам и несколькими классами заявок предлагается анализировать в виде СМО с объединённым входящим потоком средневзвешенных требований без потери точности. В качестве эффективного метода расчёта стационарных вероятностей и вероятностных характеристик упрощённой СМО был разработан рекуррентный алгоритм вычисления нормировочной константы и получены рекуррентные формулы для вероятности блокировки и среднего объёма и дисперсии занятых ресурсов.

O G Vikhrova

Peoples’ Friendship University of Russia (RUDN University)

Author for correspondence.
Email: vikhrova_og@rudn.university
6 Miklukho-Maklaya St., Moscow, 117198, Russian Federation

Department of Applied Probability and Informatics

  • Cisco Visual Networking Index: Global Mobile Data Traffic Forecast Update, 2016-2021 (2017). URL http://www.cisco.com/c/en/us/solutions/collateral/service-provider/visual-networking-index-vni/mobile-white-paper-c11-520862.html
  • J. Andrews, H. Claussen, M. Dohler, S. Rangan, Femtocells: Past, Present, and Future, IEEE JSAC 30 (3) (2012) 497–508.
  • G. Fodor, S. Parkvall, S. Sorrentino, P. Wallentin, Q.Lu, N. Brahmi, Device-to-Device Communications for National Security and Public Safety, IEEE Access 2 (1) (2014) 1510–1520.
  • 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 54 (3) (2016) 110–117.
  • S. Singh, X. Zhang, J. Andrews, Joint Rate and SINR Coverage Analysis for Decoupled Up-link-Downlink Biased Cell Associations in HetNets, IEEE Transactions on Wireless Communication 14 (10) (2015) 5360–5373.
  • H. Elshaer, F. Boccardi, M. Dohler, R. Irmer, Downlink and Uplink Decoupling: A Disruptive Architectural Design for 5G Networks, Global Communications Conference (GLOBECOM) (2014) 1798–1803.
  • V. Naumov, K. Samouylov, E. Sopin, N. Yarkina, S. Andreev, A. Samuylov, LTE Performance Analysis Using Queuing Systems with Finite Resources and Random Requirements, in: 7th International Congress on Ultra Modern Telecommunications and Control Systems and Workshops, 6–8 Oct. 2015, IEEE, 2015, pp. 100–103. doi: 10.1109/ICUMT.2015.7382412.
  • O.M. Tikhonenko, Destricted Capacity Queueing Systems: Determination of their Characteristics, Automation and Remote Control 58 (1997) 969–973.
  • O.M. Tikhonenko, Generalized Erlang Problem for Service Systems with Finite Total Capacity, Problems of Information Transmission 41 (2005) 243–253.
  • V.A. Naumov, K.E. Samouylov, On the Modeling of Queuing Systems with Multiple Resources, Bulletin of Peoples’ Friendship University of Russia. Series: Mathematics. Information Sciences. Physics (3) (2014) 58–62.
  • V.A. Naumov, K.E. Samouylov, A.K. Samouylov, On the Total Amount of Resources Occupied by Serviced Customers, Automation and Remote Control 77 (2016) 1419–1427.
  • V. Naumov, K. Samuoylov, E. Sopin, S. Andreev, Two Approaches to Analysis of Queuing Systems with Limited Resources, in: Ultra Modern Telecommunications and Control Systems and Workshops, 6–8 Oct. 2014, IEEE, 2014, pp. 485–488. doi: 10.1109/ICUMT.2014.7002149.
  • 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 564 (2015) 393–403.
  • K. Samouylov, E. Sopin, O. Vikhrova, On Design of Efficient Algorithm for Blocking Probability Calculation in Queuing System with Random Requirements, in: Information technologies and mathematical modelling (ITMM–2016): XV International Scientific Conference named after A. F. Terpugov, Vol. 1, Tomsk State University, 2016, pp. 192–197.
  • J.P. Buzen, Computational Algorithms for Closed Queueing Networks with Exponential Servers, Communications of the ACM 19 (9) (1973) 527–531.

Views

Abstract - 510

PDF (Russian) - 75


Copyright (c) 2017 Vikhrova O.G.

Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.