Автоматика и телемеханика, № 11, 2019
© 2019 г. С.Н. СТЕПАНОВ, д-р техн. наук (stpnvsrg@gmail.com),
М.С. СТЕПАНОВ, канд. техн. наук (mihstep@yandex.ru)
(Московский технический университет связи и информатики)
ЭФФЕКТИВНЫЙ АЛГОРИТМ ОЦЕНКИ ТРЕБУЕМОГО
ОБЪЕМА РЕСУРСА БЕСПРОВОДНЫХ СИСТЕМ СВЯЗИ
ПРИ СОВМЕСТНОМ ОБСЛУЖИВАНИИ ГЕТЕРОГЕННОГО ТРАФИКА
УСТРОЙСТВ ИНТЕРНЕТА ВЕЩЕЙ1
Построена и исследована математическая модель распределения ре-
сурса передачи информации изолированной соты сети подвижной свя-
зи стандарта LTE при совместном обслуживании гетерогенного трафи-
ка устройств Интернета Вещей. В модели рассматривается произвольное
число потоков мультимедийного трафика, которые различаются интен-
сивностью поступления сессий связи, величиной ресурса, используемого
для обслуживания одной сессии, временем занятия ресурса и вероятно-
стью допуска сессии к передаче информационного потока. Определены
характеристики качества обслуживания поступающих сессий. Построен
эффективный алгоритм оценки объема ресурса, требуемого для обслу-
живания заданных потоков трафика с необходимым качеством. Эффек-
тивность алгоритма достигается в результате реализации рекурсии по
объему имеющегося ресурса и использования при проведении вычисле-
ний нормированных значений вероятностей состояний модели. Алгоритм
отличается вычислительной стабильностью и позволяет решать задачу
оценки ресурса во много раз быстрее, чем традиционные подходы, осно-
ванные на вычислении для каждой величины ресурса вероятностей всех
состояний и последующей их нормировкой. Приведены численные приме-
ры, иллюстрирующие особенности реализации разработанных вычисли-
тельных процедур.
Ключевые слова: Интернет Вещей, мультисервисный трафик, марковские
модели, система уравнений равновесия, рекурсивные алгоритмы, плани-
рование ресурса передачи.
DOI: 10.1134/S0005231019110060
1. Введение
Одной из основных тенденций развития сетей связи является реализация
положений концепции Интернета Вещей. Огромное количество разного рода
устройств, в их число входят датчики, видеокамеры и т.д., собирают и пере-
дают в аналитические центры сведения, необходимые для принятия решений,
направленных на обеспечение требуемого уровня безопасности жизнедеятель-
ности и повышение эффективности работы разнообразных технических си-
стем. Информация передается с использованием ресурса сетей связи. Часто
1 Работа выполнена при частичной финансовой поддержке Российского фонда фунда-
ментальных исследований (проект №16-29-09497офи-м).
108
устройства наблюдения устанавливаются в местах, где отсутствует возмож-
ность подключения к сети фиксированной связи. В этой ситуации для переда-
чи собираемой информации используется инфраструктура сетей подвижной
связи. Для реализации этой возможности консорциум 3GPP (3rd Generation
Partnership Project) разработал стандарт NB-IoT (Narrow Band Internet of
Things), где рассмотрены несколько сценариев подключения к сети LTE раз-
нообразных низкоскоростных датчиков телеметрии [1-4]. В соответствии с
решением ГКРЧ [5] полосы частот для NB-IoT разрешено выделить в диапа-
зоне от 400 до 2600 МГц. Это означает осуществимость совместной передачи
в одной полосе видеотрафика и трафика NB-IoT.
Для практических приложений представляет интерес реализация NB-IoT
в пределах частотного диапазона LTE. Этот сценарий носит название in band
[1-3]. В этом случае для трафика NB-IoT выделяется один из ресурсных бло-
ков LTE шириной 180 кГц. Для передачи трафика NB-IoT ресурсный блок
делится на 12 поднесущих по 15 кГц (уже стандартизировано решение, в
котором ресурсный блок делится на 48 поднесущих по 3,75 кГц). Для обслу-
живания одного устройства NB-IoT может использоваться одна поднесущая
(режим single tone) или несколько поднесущих (режим multitone). Последний
сценарий применим при наличии свободных поднесущих. Необходимо отме-
тить, что принятие стандарта еще не означает, что сформулированы правила
его применения. Подобные решения нуждаются в настройке, которая заклю-
чается в выборе значений параметров, регулирующих прием и обслуживание
поступающих информационных потоков применительно к особенностям рас-
сматриваемой системы связи. Обоснованный выбор численных значений па-
раметров и является основной целью научных исследований в этой области
телекоммуникаций. Обсудим задачи, возникающие при использовании ресур-
са LTE на передачу трафика NB-IoT.
В соответствии с действующим стандартом пока не реализована возмож-
ность динамического распределения совместно используемого ресурса между
трафиком LTE и NB-IoT. Ресурсные блоки закрепляются между трафиком
LTE и NB-IoT на этапе конфигурации сети. Как показывают результаты мо-
делирования [6], этот подход позволяет добиться требуемых показателей об-
служивания поступающего трафика, но по понятным причинам неэффекти-
вен с точки зрения занятия ресурса, а также весьма чувствителен к возмож-
ному изменению интенсивностей поступающих потоков. Для устранения от-
меченных недостатков проводятся теоретические исследования разных схем
динамического распределения совместно используемого ресурса [6-8]. Рас-
смотрим возникающие здесь проблемы более детально.
Информация датчиков и видеокамер передается в виде последовательно-
сти сессий связи. Поступающие информационные сообщения различаются по
объему необходимого ресурса и требованиям к условиям передачи. Так, на-
пример, для обслуживания сессий связи высокоскоростных видеокамер одно-
временно требуется большой объем ресурса и соответствующая информация
должна быть передана с минимальной задержкой и, напротив, сессии свя-
зи низкоскоростных смарт-счетчиков требуют малый объем ресурса и в ряде
случаев данные измерений могут быть переданы с небольшой задержкой.
109
Совместное использование ограниченного по разным причинам2 ресурса се-
тей подвижной связи приводит к его перераспределению в пользу потоков с
малыми запросами к скорости передачи. Особенно ярко это проявляется в
условиях перегрузки. Соответствующие численные данные будут приведены
в разделе 3.
Для выравнивания показателей качества обслуживания применяются раз-
личные формы ограничения доступа, позволяющие резервировать ресурс для
выделенной группы потоков. Один из таких подходов рассмотрен в [6]. Дей-
ствие механизма резервирования основано на перераспределении обслужи-
ваемого трафика, обеспечивающем наличие свойства мультипликативности у
значений стационарных вероятностей модели. Эта возможность требует вы-
полнения определенных предположений о характере времени обслуживания
трафика и конфигурации сети, поэтому не всегда реализуема. Выбор кон-
кретной процедуры во многом зависит от наличия эффективного и устойчи-
вого в вычислительном плане алгоритма оценки требуемого объема ресурса
и параметров его резервирования [6-13]. Наличие отмеченных свойств алго-
ритма является необходимым условием для его использования в программно-
аналитических комплексах планирования сетей связи [9, 10, 13, 14]. В работе
алгоритм с перечисленными свойствами будет получен для модели распре-
деления ресурса передачи информации изолированной соты сети подвижной
связи стандарта LTE при совместном обслуживании неоднородного трафика
устройств Интернета Вещей с использованием технологии NB-IoT . Для ре-
зервирования ресурса будет использована процедура фильтрации поступаю-
щих сессий, зависящая от номера потока и степени загрузки ресурса [9, 10].
В разделе 2 приведено математическое описание исследуемой системы свя-
зи. В модели рассматривается произвольное число потоков мультимедийного
трафика, которые различаются интенсивностью поступления сессий связи,
величиной ресурса, используемой для обслуживания одной сессии, временем
занятия ресурса и вероятностью допуска сессии к передаче информационно-
го потока. Определены характеристики качества обслуживания поступающих
сессий. В разделе 3 рассмотрены точные и приближенные алгоритмы оцен-
ки характеристик модели. В разделе 4 построен и исследован эффективный
алгоритм расчета объема ресурса, требуемого для обслуживания заданных
потоков трафика с необходимым качеством. Алгоритм отличается вычисли-
тельной стабильностью и позволяет решать задачу оценки величины ресурса
во много раз быстрее, чем традиционные подходы. Эффективность алгоритма
достигается в результате реализации рекурсии по объему имеющегося ресур-
са и использовании нормированных значений вероятностей состояний модели.
В разделе 5 приведены примеры, иллюстрирующие особенности реализации
разработанных вычислительных процедур.
2. Описание математической модели
Обсудим функциональные особенности исследуемой системы связи и
сформулируем основные предположения, которые будут использованы при
построении ее математической модели. Начнем с определения потоков требо-
2 Это ограничения физического плана, а также результат действий регулятора, направ-
ленных на предоставление операторам равных возможностей присутствия на рынке связи.
110
ваний на выделение ресурса передачи информации. В модели рассматривает-
ся процесс поступления и обслуживания n потоков сессий связи от устройств
Интернета Вещей, в число которых входят видеокамеры и другие подобные
им системы видеонаблюдений, а также устройства NB-IoT, состоящие из раз-
нообразных датчиков телеметрии. Среди них: медицинские датчики, навига-
ционные датчики, температурные датчики, приборы охранной сигнализации,
противопожарные датчики и т.п. Каждый поток является суперпозицией сес-
сий связи от большого числа независимых однотипных устройств, поэтому
исходя из известных положений теории вероятностей его можно приближен-
но считать пуассоновским.
В процессе обслуживания сессии, выделяется определенный объем ресур-
са который используется для поддержки запросов клиентов на передачу ин-
формации. Распределение ресурса рассматривается на шкале времени, опре-
деляемой поступлением заявок. Каждому запросу ставится в соответствие
случайный объем передаваемого пользовательского трафика, который име-
ет экспоненциальное распределение с известным средним значением. В сетях
подвижной связи на базе технологии LTE ресурсом обслуживания поступа-
ющих запросов является множество ресурсных блоков (РБ), зависящее от
выделенной полосы частот, например для 1,4 МГц — 6 РБ, для 5 МГц —
25 РБ, а для 20 МГц — 100 РБ. В зависимости от вида поступающего трафика
возможна дальнейшая грануляция ресурса. Понятно, что в рассматриваемой
модели минимальные требования к ресурсу имеют запросы на информацион-
ное обслуживание от NB-IoT-устройств. Среднее значение соответствующего
требования и будет единицей ресурса или виртуальным каналом. Обозначим
через rb общее число имеющихся ресурсных блоков, а через vc обозначим
число выбранных единиц ресурса, которое содержится в одном ресурсном
блоке. Для простоты будем предполагать, что vc целое число. Далее будет
рассмотрено решение задачи оценки необходимого по нагрузке и качеству об-
служивания объема ресурса в направлении восходящей линии связи (uplink
direction) от пользователей к ресурсу изолированной соты сети стандарта
LTE. Обозначим величину искомого ресурса через v. Значение v в соответ-
ствии с введенными параметрами определяется из выражения v = rbvc.
Введем параметры k-го потока сессий: λk — интенсивность поступления
сессий; bk — число единиц ресурса, используемого для обслуживания одной
сессии; 1/μk — среднее время обслуживания сессии. Будем предполагать, что
время обслуживания сессии k-го потока имеет экспоненциальное распределе-
ние с параметром μk и потоки занумерованы в порядке возрастания bk. Обо-
значим через ϕk(i) вероятностную функцию, которая будет использоваться
для фильтрации процесса доступа сессий к ресурсу в зависимости от зна-
чений k номера потока и i общего числа занятых единиц ресурса. Сессия
k-го потока, поступившая в момент занятости i единиц ресурса, принимается
к обслуживанию с вероятностью 1 - ϕk(i), а с противоположной вероятно-
стью ϕk(i) сессия получает отказ и не возобновляется.
Обсудим выбор значений функции ϕk(i). Поскольку ϕk(i) представля-
ет собой вероятность отказа в обслуживании, то выполняются неравенства
0 ≤ ϕk(i) ≤ 1, k = 1,...,n. Отказ в обслуживании из-за нехватки ресурса про-
исходит с вероятностью, равной единице. Следовательно, для сессий k-го по-
111
тока справедливы соотношения ϕk(i) = 1, если i = v - bk + 1, v - bk + 2, . . . , v.
Рассмотрим возможности использования функции ϕk(i) для реализации про-
цедуры резервирования ресурса в пользу отдельных потоков. Из свойств
пуассоновского потока (свойство PASTA [10]) следует, что для каждого по-
тока доля потерянных заявок совпадает с долей времени пребывания модели
в состоянии с числом занятых единиц ресурса, более или равном v - bk + 1.
Тогда, чтобы выравнять значения потерь для всех потоков, достаточно взять
(1)
ϕk(i) = 1, i = v - bn + 1, v - bn
+ 2, . . . , v; k = 1, . . . , n.
Назовем данный выбор традиционной процедурой резервирования ресурса.
Допустим ставится задача предоставить преимущество потокам сессий с
номерами ℓ, ℓ + 1, . . . , n. В этой ситуации функцию фильтрации сессий выбе-
рем из соотношений
ϕk(i) = 1, i = v - z, v - z + 1, . . . , v; k = 1, . . . , ℓ - 1;
(2)
ϕk(i) = 1, i = v - bn + 1, v - bn + 2, . . . , v; k = ℓ, ℓ + 1, . . . , n.
Будем предполагать, что z ≥ bn - 1. Значение z - bn + 1 определяет дополни-
тельный ресурс, который используется для создания преимущества сессиям
с номерами потоков k = ℓ, ℓ + 1, . . . , n. В контексте построенной модели это
сессии передачи видео. Рассмотренные процедуры резервирования ресурса
показаны на рис. 1 для модели с числом потоков n = 5. Потоки с номерами
1, 2, 3 представляют из себя сессии NB-IoT-устройств с малым потреблением
ресурса, а потоки с номерами 4, 5 — это сессии связи видеокамер с большим
потреблением ресурса.
Введенные процедуры резервирования позволяют выравнять потери, но
происходит это в результате недоиспользования ресурса передачи. Можно
рассмотреть компромиссный вариант резервирования, когда фильтрация сес-
сий происходит с вероятностью, меньшей единицы. Выбор величины вероят-
ности зависит от условий принятого соглашения об обслуживании.
Перейдем к построению случайного процесса, описывающего динамику
изменения состояний модели. Для k-го потока достаточность ресурса оце-
ним величиной πk долей потерянных сессий связи, а эффективность его ис-
пользования — значением mk (средним числом занятых единиц ресурса).
Для оценки этих характеристик достаточно знать долю времени пребыва-
ния модели в состоянии с известным числом сессий каждого потока, находя-
щихся на обслуживании. Выбор характеристик определяет состояние модели
в виде вектора (i1, . . . , in) с компонентами, удовлетворяющими неравенству
i1b1 + ... + inbn ≤ v, где ik — число сессий k-го потока, находящихся на об-
служивании, k = 1, . . . , n. Множество таких векторов представляет из себя
пространство теоретически возможных состояний модели. Пространство ре-
ально используемых состояний S является подмножеством Ω и определяется
выбором значений функций блокировки. Изменение состояний модели во вре-
мени описывается случайным процессом
r(t) = (i1(t), . . . , in(t)),
где ik(t) — число сессий k-го потока, находящихся на обслуживании в мо-
мент t. Процесс r(t) марковский, поскольку построен в соответствии с поло-
жениями конструктивного определения марковского процесса.
112
Cессии связи
Cессии связи
от устройств
для передачи
NB-loT
видео
v
Cессии k-го потока
получают отказ с
вероятностью единица
v bk + 1
(k = 3)
Ресурс,
резервируемый для
выравнивания
потерь
Уровень
v bn
+ 1
резервирования для
выравнивания потерь
сессий (n = 5)
Уровень
v z
резервирования для
преимущества сессиям
передачи видео
Ресурс,
резервируемый для
создания
преимущества
1
2
3
4
5
k
Номера потоков
сессий связи
Рис. 1. Функциональная модель резервирования ресурса.
Пусть p(i1, . . . , in) — стационарная вероятность состояния (i1, . . . , in), а
i = i1b1 + ... + inbn — число единиц ресурса, занятых в этом состоянии. Ис-
пользуя свойство PASTA и формулу Литтла, получаем расчетные выражения
для πk и mk:
∑
λk
(3)
πk =
p(i1, . . . , in) ϕk(i), mk =
(1 - πk
).
μk
(i1,...,in)∈S
Для оценки характеристик в соответствии с введенными определениями
необходимо найти p(i1, . . . , in). Отметим, что использование процедуры резер-
вирования может привести к появлению односторонних переходов между со-
стояниями r(t). Следовательно, процесс r(t) необратим и по этой причине не
113
имеет мультипликативной формы представления p(i1, . . . , in). Это свойство
затрудняет расчет характеристик обслуживания сессий связи и заставляет
искать альтернативные пути их оценки.
3. Точные и приближенные алгоритмы вычисления характеристик
Точные способы расчета введенных характеристик основаны на составле-
нии и решении системы уравнений равновесия. Для каждого (i1, . . . , in) ∈ Ω
составление уравнения равновесия сводится к реализации принципа равен-
ства среднего числа выходов r(t) в единицу времени из (i1, . . . , in) к сред-
нему числу переходов r(t) в единицу времени в это состояние. Далее в обо-
значениях вероятностей состояний будем использовать прописную букву для
ненормированных значений вероятностей и строчную — для нормированных.
Искомая система имеет вид
∑(
)
(
)
(4)
P (i1, . . . , in)
λk
1 - ϕk(i)
+ ik μk I(ik > 0)
=
k=1
∑
(
)
= P(i1,...,ik - 1,...,in)λk
1 - ϕk(i - bk)
I(ik > 0) +
k=1
∑
+ P(i1,...,ik + 1,...,in)(ik + 1)μk I(i + bk ≤ v),
k=1
(i1, . . . , in) ∈ Ω.
Здесь I(·) — индикаторная функция события, равная единице, если выпол-
нены сформулированные в скобках ограничения на изменение целочисленных
компонент состояния, и равная нулю в противном случае. Найденные величи-
ны P (i1, . . . , in) необходимо нормировать. Часть состояний из Ω по условиям
выбора функций блокировки может и не попасть в S. Величины их вероят-
ностей принимаются равными нулю.
Поскольку матрица (4) не обладает какими-либо специальными свойства-
ми, то для оценки стационарных вероятностей рекомендуется использовать
итерационные методы. Наиболее известным и простым в реализации являет-
ся итерационный метод Гаусса-Зейделя. Используя найденный вид (4), пере-
пишем систему рекурсивных соотношений алгоритма Гаусса-Зейделя в виде
одного выражения с коэффициентами, зависящими от компонент состояния
(i1, . . . , in) ∈ Ω:
1
(5)
P(s+1)(i1,... ,in) =
)×
∑(
(
)
λk
1 - ϕk(i)
+ ik μk I(ik > 0)
k=1
(
∑
(
)
×
P(s,s+1)(i1,... ,ik - 1,... ,in)λk
1 - ϕk(i - bk)
I(ik > 0) +
k=1
)
∑
+ P(s,s+1)(i1,... ,ik + 1,... ,in)(ik + 1)μk I(i + bk ≤ v)
k=1
114
В приведенном соотношении верхний индекс (s) означает s-е приближение
к P(i1,...,in), полученное с помощью введенной рекурсии. Верхний индекс
(s, s + 1) означает использование (s + 1)-го приближения к P (i1, . . . , in), если
же оно еще не найдено, то применяется известное s-е приближение.
В качестве начального приближения берется любое приближение с поло-
жительными компонентами. Приведенная выше реализация рекурсии Гаусса-
Зейделя не обладает гарантированной сходимостью применительно к реше-
нию систем уравнений равновесия, но в подавляющем большинстве случаев
она имеет место. Сходимость исследуется косвенными методами на основе
анализа близости последовательных приближений и выполнения известных
теоретических соотношений, например законов сохранения, следующих из
формулы Литтла. Если в (4) одну из неизвестных вероятностей положить
равной единице, убрать уравнение, соответствующее этому состоянию, и пе-
рейти к решению неоднородной системы линейных уравнений, то рекурсия
Гаусса-Зейделя всегда сходится (из-за наличия слабого диагонального преоб-
ладания) [15], но требует для своей реализации существенно большего числа
итераций, чем рекурсия по формуле (5).
Для исследуемой модели можно построить приближенный алгоритм оцен-
ки характеристик, отличающийся очень хорошей точностью. Обозначим при-
ближенные значения характеристик теми же символами, что и в исходной
модели, только со знакомˆ. Идея метода основана на постулируемом выпол-
нении в каждом состоянии (i1, . . . , in) ∈ S соотношений детального баланса
(
)
(6)
p(i1, . . . , ik - 1, . . . , in) λk
1 - ϕk(i - bk)
= p(i1, . . . , in) ik μk.
Введем обозначения:
∑
p(i) =
p(i1, . . . , in), i = 0, 1, . . . , v; ak = λk/μk.
(i1,...,in)∈S|i1b1+...+inbn=i
После суммирования (6) по всем (i1, . . . , in) ∈ S, удовлетворяющим условию
i1b1 + ... + inbn = i, получаем рекурсивное выражение, связывающее значе-
ни
P (i), i = 1, . . . , v:
1
∑
(
)
(7)
P (i) =
ak bk
P (i - bk)
1 - ϕk(i - bk)
i
k=1
После реализации рекурсии находим оценки характеристик:
∑
(8)
πk =
p(i) ϕk(i),
mk = ak bk (1 - πk
),
k = 1,...,n.
i=0
Построенную математическую модель и алгоритмы расчета ее характери-
стик можно использовать для численного исследования сценариев распреде-
ления ресурса передачи информации изолированной соты сети подвижной
связи стандарта LTE при совместном обслуживании гетерогенного трафи-
ка устройств Интернета Вещей. Рассмотрим процесс занятия ресурса в за-
висимости от увеличения общей загрузки соты. Уровень загрузки зададим
115
150
120
1
90
1, 2, 3
60
2
30
3
0
0,5
1,0
1,5
2,0
2,5
Загрузка канала,
Рис. 2. Зависимость mk, k = 1, 2, 3 от увеличения ρ без использования резер-
вирования и при его наличии.
величиной ρ предложенного трафика на единицу ресурса:
∑
1
(9)
ρ=
akbk.
v
k=1
Предположим, что в соте имеются три информационных потока и они со-
здают одинаковый предложенный трафик a1b1 = a2b2 = a3b3. Сформулиро-
ванное предположение и соотношение (9) позволяют определить интенсивно-
сти поступления сессий λk для каждого из имеющихся потоков по заданной
величине ρ. Фиксированные параметры модели принимают значения: v = 200;
n = 3, μ1 = 1; μ2 = 0,1; μ3 = 0,1; b1 = 1; b2 = 20; b3 = 30. В качестве единицы
времени выбрано среднее время передачи данных устройства NB-IoT с ис-
пользованием единицы ресурса соты. Величины v и bk, k = 1, 2, 3 выражены
в используемых единицах ресурса, и его резервирование не производится.
На рис. 2 показаны значения mk, k = 1, 2, 3, найденные с помощью (3) после
решения системы уравнений равновесия (4) с использованием рекурсивной
последовательности (5). Цифра у кривой указывает номер потока.
Приведенные данные показывают, что в отсутствие ограничения доступа
сессии связи с малым потреблением ресурса вытесняют из процесса совмест-
ного обслуживания ресурсоемкие сессии. Особенно ярко это проявляется в
условиях перегрузки. Резервирование ресурса с применением процедуры (1)
выравнивает πk, mk для всех потоков сессий связи. Соответствующая кривая
с пометкой 1, 2 или 3, показывает на рис. 2 среднее число занятых единиц
ресурса, одинаковое для каждого из трех потоков. Используя процедуру (2),
в частности варьируя параметр z, можно не только выравнять потери сес-
сий, но и предоставить преимущество сессиям передачи трафика реального
116
0,7
Точно
0,6
0,5
0,4
0,3
Прибл.
0,2
0,1
0
0,5
1,0
1,5
2,0
2,5
Загрузка канала,
Рис. 3. Точные и приближенные значения потерь сессий при наличии резер-
вирования ресурса по процедуре (1).
времени за счет некоторого повышения уровня потерь для сессий передачи
данных3.
Решение перечисленных задач методами, основанными на решении систе-
мы уравнений равновесия (4), — достаточно трудоемкий процесс. В этой си-
туации предпочтительней использовать приближенные алгоритмы, если, ко-
нечно, они обладают хорошей точностью. Погрешность оценки выравненных
потерь сессий для модели с параметрами, использованными при расчете кри-
вых, представленных на рис. 2, показана на рис. 3. Приближенные значения
потерь получены с применением рекурсии (7) и формул (8). Приведенные
данные показывают, что погрешность оценки достаточно мала и в большин-
стве случаев лежит в пределах 5-10%. Это позволяет использовать данный
подход для решения разного рода инженерных задач, относящихся к прак-
тическому применению модели.
Подбор требуемого по нагрузке и качеству обслуживания объема ресур-
са v и уровня его резервирования z остается трудоемкой задачей даже при
использовании рекурсии (7). В основном это происходит из-за необходимо-
сти искать решение в области больших значений v, часто достигающих ве-
личины в несколько сотен или даже тысяч единиц4. Большие значения v не
только увеличивают время счета, но и делают нестабильным расчетный алго-
ритм, поскольку в (7) вероятности состояний выражаются через вероятность
состояния с нулевым занятым ресурсом, а эта вероятность пренебрежимо
мала. В следующем разделе будет построена версия расчетного алгоритма,
3 Эту процедуру можно использовать, если передача данных допускает задержку или
имеется возможность повторной передачи соответствующего файла.
4 Это так, поскольку в качестве единицы ресурса выбирается требование к скорости
передачи трафика устройств NB-IoT, а это требование существенно меньше, чем величина
ресурса, необходимая при обслуживании видеотрафика.
117
основанная на (7), которая свободна от указанных недостатков. Алгоритм
отличается вычислительной стабильностью и позволяет решать задачу оцен-
ки требуемой величины ресурса во много раз быстрее, чем традиционные
подходы. Эффективность алгоритма достигается в результате реализации
рекурсии по объему имеющегося ресурса и использования нормированных
значений вероятностей состояний модели.
4. Эффективный алгоритм оценки требуемой величины ресурса
Будем предполагать, что значения n, ak, bk, k = 1, . . . , n фиксированы на
время решения задачи. Обозначим через b = max1≤k≤n bk максимальное тре-
бование сессий к ресурсу передачи. По построению модели b = bn. Также бу-
дем предполагать, что минимальное требование к ресурсу b1 = 1. Резервиро-
вание ресурса выполним с помощью обобщения процедуры, заданной соотно-
шением (1). Из практических приложений известно, что значения функций
блокировки отличны от нуля, главным образом, в состояниях, близких к пол-
ной занятости ресурса. Это позволяет переписать (1) в виде
ϕk(i) = 0, i = 0, 1, . . . , v - g - 1;
(10)
ϕk(i) > 0, i = v - g, v - g + 1, . . . , v - bk;
ϕk(i) = 1, i = v - bk + 1, v - bk + 2, . . . , v; k = 1, . . . , n,
где v - g несущественно отличается от v. Будем предполагать, что g ≥ b - 1.
Понятно, что традиционная форма резервирования ресурса, направленная
на выравнивание потерь, является частным случаем (10). Чтобы ее получить
достаточно положить g = b - 1 и ϕk(i) = 1, i = v - g, v - g + 1, . . . , v - bk;
k = 1,...,n.
Для оценки характеристик качества обслуживания поступающих сессий
связи воспользуемся приближенным методом, основанным на использовании
рекурсии (7). Достаточность ресурса оценим максимальной величиной забло-
кированных сессий
∑
(11)
πe = max
p(i) ϕk
(i).
1≤k≤n
i=v-g
Предполагается, что задано требуемое регулятором нормативное значение
потерь πnorm. В качестве начального значения v, требуемого по нагрузке и
качеству обслуживания, можно⌊взять це⌋ую часть среднего числа потенци-
∑
ально занятых единиц ресурса
akbk
k=1
Обозначим для исследуемой модели через
Ps(i) и ϕk,s(i) соответственно
зависимости вероятности и функции блокировки от общего числа единиц ре-
сурса s. Предположим, что имеющийся объем ресурса равен r - 1. Положим
Pr-1(0) = 1 и выразим вероятност
Pr-1(i) с помощью (7) чере
Pr-1(0). Для
i = 1,...,r - g - 1 вероятности ϕk,r-1(i - bk) в правой части (7) равны нулю
118
в силу (10) и соотношение (7) приобретает вид
∑
1
(12)
Pr-1(i) =
ak bk Pˆr-1(i - bk
),
i = 1,...,r - g - 1.
i
k=1
Для i = r - g, . . . , r - 1 вероятности ϕk,r-1(i - bk) могут отличаться от нуля
и форма (7) не меняется
1∑
(
)
(13)
Pr-1(i) =
ak bk Pˆr-1(i-bk)
1-ϕk,r-1(i-bk)
,
i=r-g,...,r-1.
i
k=1
Найденные вероятност
Pr-1(i) нормируются. Если πe > πnorm, то увели-
чиваем объем ресурса до r и заново рассчитываем вероятности состояний.
Выполним вычисления в виде следующей последовательности действий.
• Выберем начальное значение (7) из услови
Pr(0) = pr-1(0). Из вида ре-
курсии (7) и выбора значений ϕk,r(i), k = 1, . . . , n (10) следует соотношение
Pr(i) = pr-1(i), i = 0,... ,r - g - 1.
Таким образом, значени
Pr(i), i = 0,... ,r - g - 1 известны и заново для
величины ресурса r не рассчитываются.
• Выразим Nr,1 сумму вероятностей
Pr(0),...
Pr(r - g - 2) через сумму
(g + 1) вероятностей состояний, где возможна блокировка, найденных на
предыдущем шаге при общем числе единиц ресурса r - 1,
Nr,1
Pr(0) + ...
Pr(r - g - 2) =
= pr-1(0) + ... + pr-1(r - g - 2) =
= 1 - (pr-1(r - g - 1) + ... + pr-1(r - 1)).
• Рассчитываем, используя (7), вероятност
Pr(i), i = r - g,... ,r, поскольку
для этих значений i возможно изменение функции блокировки. Для реали-
зации этого шага используются вероятност
Pr(i), i = r - g - b,... ,r - 1,
участвующие в определении правой части рекурсии.
• Находим нормировочную константу Nr для объема ресурса r, используя
соотношение Nr = Nr,1
Pr(r - g - 1) + ...
Pr(r). Нормируем вероятно-
ст
Pr(i), i = r - g,... ,r и рассчитываем значение πe.
Последовательность применения
pr-1(i), i = 0, 1, . . . , r - 1 при расче-
те πe для величины ресурса r показана на рис. 4. Для вычисления pr(i),
i = r - g,...,r используются вероятности pr-1(i), i = r - g - 1,...,r - 1 при
расчете нормировочной константы и дополнительно к ним используются ве-
роятности pr-1(i), i = r - g - b, . . . , r - g - 2 при реализации рекурсии (7)
для i = r - g, . . . , r. Если выясняется, что πe > πnorm, то r увеличивается
на единицу и расчеты повторяются. Для этого дополнительно нормируют-
с
Pr(i) для i = r - g - b + 1,... ,r - g - 1. Из приведенного обсуждения сле-
дует, что для организации процесса вычисления характеристик при после-
довательном увеличении объема ресурса независимо от его величины надо
знать g + b стационарных вероятностей с максимальным занятым ресурсом.
119
Сумма вероятностей этих
состояний дополняет сумму
вероятностей, где возможна
блокировка до единицы
Вероятности
этих
состояний
0
0
сохранят
При расчете
свои
значения при
вероятностей этих
реализации
состояний в правой
части рекурсии
рекурсии
r g b
вероятности
блокировок равны
нулю
r g b + 1
Состояния,
используемые
при расчете
вероятностей
r g
1
r g
1
Вероятности
этих состояний
нормируются
r g
r g
для следующего
Состояния,
шага рекурсии
где возможна
блокировка
Вероятности
r
2
r
2
этих состояний
определяются
с новыми
r
1
r
1
вероятностями
блокировок
r
Рис. 4. Характер использования вероятностей состояний при изменении вели-
чины ресурса на единицу с r - 1 до r.
Выполненные преобразования дают основание сформулировать алгоритм
оценки требуемого объема ресурса в виде рекурсии по числу единиц ре-
сурса. Реализация алгоритма с промежуточного значения объема ресурса
r - 1 ≥ g + b имеет следующий вид:
1. Положи
Pr-1(0) = 1 и вырази
Pr-1(i) чере
Pr-1(0), используя соотно-
шение
1
∑
(
)
Pr-1(i) =
ak bk Pˆr-1(i - bk)
1 - ϕk,r-1(i - bk)
,
i = 1,...,r - 1.
i
k=1
Нормировка дает вероятности pr-1(r - 1), . . . , pr-1(r - g - b).
2. Далее рассчитываем πe. Если πe > πnorm, то объем ресурса увеличиваем
на единицу, положи
Pr(i) = pr-1(i), i = r - g - b,... ,r - g - 1 и опреде-
лим g + 1 значений ненормированных вероятносте
Pr(i), i = r - g,... ,r с
помощью рекурсии:
1
∑
(
)
Pr(i) =
ak bk Pˆr(i - bk)
1 - ϕk,r(i - bk)
,
i = r - g,...,r.
i
k=1
120
С
Состояния,
используемые при
эффективном методе
поиска требуемого
ресурса
Состояния,
используемые при
B
g + b
традиционном методе
поиска требуемого
ресурса
Начальное
значение
A
ресурса
D
Переменное значение ресурса, r
Рис. 5. Состояния, используемые при оценке требуемого объема ресурса тра-
диционным и эффективным алгоритмами.
3. Находим нормировочную константу
Nr = 1 - (pr-1(r - g - 1) + ... + pr-1(r - 1))
Pr(r - g - 1) + ...
Pr(r).
4. Выполняем нормировку вероятностей
Pr(i)
pr(i) =
,
i = r - g - b + 1,...,r
Nr
и переходим к шагу 2.
Обсудим преимущества построенного алгоритма оценки требуемого по на-
грузке объема ресурса в сравнении с известными подходами, основанными на
последовательном решении систем уравнений равновесия [6-13]. При его реа-
лизации с использованием вычислительной техники не возникает проблем с
переполнением или исчезновением порядка, поскольку расчеты выполняются
только с нормированными вероятностями состояний модели с максимальным
занятым ресурсом. По условиям анализа модели они имеют наибольшие отно-
сительные значения. Вычислительная стабильность имеет большое значение
при реализации алгоритма в так называемых «калькуляторах», применяемых
для решения задач планирования объема инфраструктуры сетей связи.
Рассмотренный алгоритм позволяет вести рекурсию по числу имеющихся
единиц ресурса. Для расчета характеристик и выполнения следующего шага
алгоритма достаточно знать вероятности g + b состояний с максимальным
занятым ресурсом. По сравнению с традиционным подходом рассмотренный
121
алгоритм сокращает расчетную работу при оценке требуемой величины ре-
сурса не менее чем вv2(g+b) раз. Соотношение между числом состояний, ис-
пользуемых при оценке требуемого объема ресурса традиционным (область
ABCD) и эффективным (заштрихованная область) методами, показано на
рис. 5.
Построенный алгоритм обобщает известные рекурсивные соотношения
для оценки требуемого объема ресурса систем связи. Если предположить, что
в модели нет резервирования и имеется один поток требований (моносервис-
ная модель Эрланга), то построенный алгоритм трансформируется в рекур-
сию по числу единиц ресурса r. Реализация рекурсии позволяет определить
минимальный объем ресурса для обеспечения заданного уровня потерь πnorm
aE(r - 1, a)
E(r, a) =
≤ πnorm, r = 1,... , (E(0,a) = 1).
r + aE(r - 1,a)
Здесь E(r, a) — формула Эрланга (доля потерянных заявок) для модели с
числом каналов r и интенсивностью предложенного трафика a.
Предположим, что в модели нет резервирования и рассматривается про-
цесс обслуживания n потоков гетерогенного трафика (мультисервисная мо-
дель Эрланга). В этой ситуации построенный алгоритм также трансформи-
руется в рекурсию по числу единиц ресурса r. Последовательное применение
рекурсии позволяет определить минимальный объем ресурса для обеспече-
ния заданного уровня потерь πnorm. Реализация рекурсии начиная с величины
ресурса r - 1 включает в себя следующие шаги.
1. Положим Pr-1(0) = 1 и выразим Pr-1(i) через Pr-1(0), используя соотно-
шение
∑
1
P (i) =
ak bk P(i - bk), i = 1,2,... ,r - 1.
i
k=1
После нормировки находим b вероятностей с максимальным занятым ре-
сурсом pr-1(r - 1), pr-1(r - 2), . . . , pr-1(r - b).
2. Далее, оценим качество обслуживания (см. п. 3). Если требуемый уровень
не достигнут, то объем ресурса увеличиваем до r и находим b нормирован-
ных вероятностей pr(i), i = r, r - 1, . . . , r - b + 1 с максимальным занятым
ресурсом. Для этого используем аналогичные вероятности, полученные на
предыдущем шаге. Вначале находим нормировочную константу для объе-
ма ресурса r
∑
1
Nr = 1 +
ak bk pr-1(r - bk) = 1 + Sr-1,
r
k=1
а затем сами вероятности
Sr-1
pr-1(i)
pr(r) =
,
i=r;
pr(i) =
,
i = r - 1,r - 2,...,r - b + 1.
Nr
Nr
122
3. Далее находим значение функционала, например максимум потерь за-
явок π = pr(r - b + 1) + pr(r - b) + . . . + pr(r). Величину π сравниваем с
его нормативным значением и, если требуемый уровень потерь не достиг-
нут, число каналов увеличиваем на единицу. Расчеты повторяем начиная
с п. 2.
Для расчета характеристик и выполнения следующего шага алгоритма до-
статочно знать вероятности b состояний с максимальным занятым ресурсом.
5. Примеры оценки объема ресурса и уровня его резервирования
Рассмотрим возможности применения построенной модели и алгоритмов
вычисления ее характеристик для решения задачи оценки общего объема ре-
сурса v и уровней его резервирования g, z при обслуживании с заданным
качеством известных потоков сессий связи видеокамер и устройств NB-IoT.
Формальная запись данной задачи имеет следующий вид. Обозначим через
πc(v,g,z) и πs(v,g,z) зависимость максимальной величины доли заблокиро-
ванных сессий связи соответственно для видеокамер и устройств NB-IoT от
v, g,z (соотношение между параметрами v и z см. рис. 1). Необходимо найти
значения v, g, z, удовлетворяющие неравенствам
(14)
πc(v,g,z) < πc, πs(v,g,z) < πs,
где πc и πs — требуемые значения максимальной доли заблокированных сес-
сий связи для видеокамер и устройств NB-IoT соответственно. Предполага-
ется, что πs ≥ πc.
Решение сформулированной задачи упрощает характер зависимости по-
терь πc(v, g, z) и πs(v, g, z) от изменения v, g, z при фиксированных значени-
ях остальных параметров модели. Из интуитивных соображений о процессе
обслуживания поступающих сессий связи понятно, что при увеличении v и
фиксированных g = z = b - 1 значения πc(v, g, z) и πs(v, g, z) уменьшаются, а
при увеличении z и фиксированных v, g = b - 1 значение πs(v, g, z) возраста-
ет, а величина πc(v, g, z), наоборот, убывает. Используя отмеченные свойства,
построим процедуру оценки v, g, z по заданным параметрам поступления и
обслуживания сессий связи и требуемым значениям πc и πs потерь сессий.
Расчетный алгоритм включает в себя следующие шаги.
1. Используя традиционный алгоритм резервирования (1), определим мини-
мальный объем ресурса v0, при котором величина выравненных по уровню
g = b - 1 (см. (11)) потерь удовлетворяет неравенству πe < πs. При прове-
дении вычислений используется эффективный алгоритм оценки ресурса,
построенный в разделе 4.
2. Для каждого v = v0, v0 + 1, . . . найдем минимальное значение z, при кото-
ром выполняется неравенство πc(v, g, z) < πc. Если таковое не находится,
то увеличиваем объем ресурса на число единиц, необходимое по условиям
реализации шага 1, и заново повторяем данный шаг алгоритма.
3. Проверяем для найденных v, g, z выполнение соотношений (14). Если
сформулированные неравенства выполняются, то полученные значения v,
g,z и будут искомым ответом на поставленную задачу. В противном случае
возвращаемся к предыдущим шагам алгоритма.
123
0,27
0,24
0,21
0,18
0,15
0,12
0,09
0,06
0,03
361
0,01
0
200
220
240
260
280
300
320
340
360
Объем ресурса, v
Рис. 6. Результаты промежуточных значений πe до выполнения соотношения
πe < πs.
Рис. 7. Результаты промежуточных значений πc(v, g, z) и πs(v, g, z) до выпол-
нения соотношений.
Приведем численный пример, иллюстрирующий применение построенного
алгоритма. Рассмотрим модель с параметрами поступления и обслуживания
сессий, использованными при расчете характеристик, приведенных на рис. 2.
Положим ρ = 1. Величины πc и πs выберем из соотношений: πc = 0,001 и
πs = 0,01. Результаты реализации 1-го шага показаны на рис. 6, откуда видно,
что v0 = 361, соответственно g = z = 29.
Далее проводится процесс уточнения полученных значений v, g, z. На
рис. 7 приведены значения πc(v, g, z) и πs(v, g, z) в зависимости от номера
итерации, где каждый номер — это результат выполнения 1-го и 2-го шагов
алгоритма. Ответ получен на 106-м шаге и приводит к следующим значениям
параметров: v = 419, g = 29, z = 75.
124
6. Заключение
Построена и исследована математическая модель распределения ресурса
передачи информации изолированной соты сети подвижной связи стандарта
LTE при совместном обслуживании неоднородного трафика устройств Интер-
нета Вещей, образованного сессиями связи видеокамер и смарт-датчиков, ис-
пользующих для передачи данных технологию NB-IoT. Для резервирования
ресурса применяется процедура фильтрации поступающих сессий, зависящая
от номера потока и степени загрузки ресурса. В модели рассматривается про-
извольное число потоков мультимедийного трафика, которые различаются
интенсивностью поступления сессий связи, величиной ресурса, используемой
для обслуживания одной сессии, временем занятия ресурса и вероятностью
допуска сессий к передаче информационного потока. Определены характери-
стики качества обслуживания поступающих сессий. Рассмотрены точные и
приближенные алгоритмы оценки характеристик модели. Построен эффек-
тивный алгоритм расчета объема ресурса, требуемого для обслуживания за-
данных потоков трафика с необходимым качеством. Эффективность алго-
ритма достигается в результате реализации рекурсии по объему имеющегося
ресурса и использования при проведении вычислений нормированных значе-
ний вероятностей состояний модели. Алгоритм отличается вычислительной
стабильностью и позволяет решать задачу оценки ресурса во много раз быст-
рее, чем традиционные подходы, основанные на вычислении для каждой ве-
личины ресурса вероятностей всех состояний с последующей их нормировкой.
Приведены численные примеры, иллюстрирующие особенности реализации
разработанных вычислительных процедур. Построенную модель и методы ее
расчета можно обобщить на случаи, когда учитывается зависимость поступ-
ления сессий от числа источников нагрузки и когда поступление сессий носит
групповой характер.
СПИСОК ЛИТЕРАТУРЫ
1. Study on provision of low-cost Machine-Type Communications (MTC) User
Equipments (UEs) based on LTE. 3GPP Technical Report (TR) 36.888/r12, 2013.
2.
3GPP. Standardization of NB-IOT completed.
3.
3GPP Technical Report (TR) 36.888/r12, Study on provision of low-cost Machine-
Type Communications (MTC) User Equipments (UEs) based on LTE. 2013.
aspx?specificationId=2578.
4. Rico-Alvarino A., Vajapeyam M., Xu H., Wang X., Blankenship Y., Bern J.,
Tirronen T., Yavuz E. An overview of 3GPP enhancements on machine to machine
communications // IEEE Commun. Mag. 2016. V. 54. No. 6. P. 14-21.
5. В декабре 2017 г. принято решение ГКРЧ по выделению частот для систем NB-
6. Begishev V., Petrov V., Samuylov A., Moltchanov D., Andreev S., Koucheryavy Y.,
Samouylov K. Resource Allocation and Sharing for Heterogeneous Data Collection
over Conventional 3GPP LTE and Emerging NB-IoT Technologies // Comput.
Communicat. 2018. V. 120. No. 2. P. 93-101.
125
7.
Shorgin S., Samouylov K., Gaidamaka Y., Chukarin A., Buturlin I., Begishev V.
Modeling Radio Resource Allocation Scheme with Fixed Transmission Zones for
Multiservice M2M Communications in Wireless IoT Infrastructure // Lecture Notes
Comput. Scie., Springer, Cham. 2015. V. 9012. P. 473-483.
8.
Бегишев В.О., Самуйлов А.К., Молчанов Д.А., Самуйлов К.Е. Стратегия рас-
пределения радиоресурсов в гетерогенных сетях с трафиком Narrow-Band IoT //
Системы и средства информатики. 2017. No. 4. Т. 27. С. 64-79.
9.
Broadband network traffic. Performance evaluation and design of broadband
multiservice networks. Final report of action COST 242 / James Roberts (ed).
Lecture notes in computer sciences. Springer, 1996. 584 p.
10.
Степанов С.Н. Теория телетрафика: концепции, модели, приложения. М.: Го-
рячая линия - Телеком, 2015. 868 с.
11.
Степанов С.Н. Модель совместного обслуживания трафика сервисов реального
времени и данных. I // АиТ. 2011. № 4. С. 121-132.
Stepanov S.N. Model of Joint Servicing of Real-Time Service Traffic and Data
Traffic. I // Autom. Remote Control. 2011. V. 72. No. 4. P. 787-797.
12.
Степанов С.Н. Модель совместного обслуживания трафика сервисов реального
времени и данных. II // АиТ. 2011. № 5. С. 139-147.
Stepanov S.N. Model of Joint Servicing of Real-Time Service Traffic and Data
Traffic. II // Autom. Remote Control. 2011. V. 72. No. 5. P. 1028-1035.
13.
Степанов С.Н., Степанов М.С. Планирование ресурса передачи при совмест-
ном обслуживании мультисервисного трафика реального времени и эластичного
трафика данных // АиТ. 2017. № 11. C. 79-93.
Stepanov S.N., Stepanov M.S. Planning Transmission Resource at Joint Servicing of
the Multiservice Real Time and Elastic Data Traffics // Autom. Remote Control.
2017. V. 78. No. 11. P. 2004-2015.
14.
Степанов С.Н., Степанов М.С. Планирование ресурса передачи информации
соединительных линий мультисервисных иерархических сетей доступа // АиТ.
2018. № 8. С. 66-80.
Stepanov S.N., Stepanov M.S. Planning the Resource of Information Transmission for
Connection Lines of Multiservice Hierarchical Access Networks // Autom. Remote
Control. 2018. V. 79. No. 8. P. 1422-1433.
15.
Степанов С.Н. О решении систем уравнений равновесия большой размерно-
сти // АиТ. 1989. № 5. C. 89-99.
Stepanov S.N. Solution of Simultaneous Large-Scale Equilibrium Equations //
Autom. Remote Control. 1989. V. 50. No. 5. Part 2. P. 647-655.
Статья представлена к публикации членом редколлегии А.И. Ляховым.
Поступила в редакцию 28.03.2019
После доработки 12.04.2019
Принята к публикации 18.07.2019
126
