Планирование распределения ресурсов вышки мобильной связи

Задача составления расписания работы планировщика для вышки сотовой связи стала. популярна, в последнее десятилетие в связи с массовым использованием мобильных устройств для выхода, в Интернет и скачивания (просмотра.) больших объемов информации. В литературе по данному направлению прочно укрепился подход, при котором работа. планировщика, задается некоторым индексом: в данный момент времени обслуживается тот клиент (пользователь мобильного устройства), у которого значения этого индекса наибольшее. Индексы легко рассчитываются по накопленной на. вышке информации об истории обслуживания имеющихся сейчас клиентов и по известным текущим величинам пропускных способностей каналов передачи данных для каждого клиента. В литературе насчитываются десятки различных индексов, которые в зависимости от условий оказываются оптимальными, т.е. приводящими к оптимальным в некотором смысле расписаниям. В действительности, строгих результатов в данной области мало. В основном ставятся численные эксперименты, позволяющие отбирать среди различных вариантов наилучшие.

В данной работе также рассматриваются только численные эксперименты. Прежде всего, в работе показано, что при естественных условиях с помощью (выпуклой) комбинации имеющихся индексов не удается получить лучший по свойствам индекс. Это довольно неожиданный результат. Начиная работу в этом направлении, автор был уверен в обратном.

«Московский физико-технический институт (национальный исследовательский университет)», 2019

Также в работе были получены новые индексы, в некотором смысле обратные к общепринятым, которые показали хорошие результаты при использовании популярных у практиков критериев качества работы планировщика ALPT и logALPT.

Структура статьи следующая. В и. 2 приводится краткое описание технической стороны рассматриваемой задачи. В и. 3 задача ставится более формально, но все же по-прежнему не строго. Строго поставить задачу с критериями ALPT и logALPT, насколько нам известно, пока открытая задача. В п. 4 вводится понятие индексной стратегии планировщика и приводится небольшой обзор по наиболее конкурентным индексам, которые удалось найти в литературе. В и. 5 вводятся некоторые новые индексы, полученные с использованием информации о вероятностном распределении входных данных. Со всеми этими индексами проводились численные эксперименты на модельных данных, которые описаны в заключительном п. 6.

• 2.    Краткое описание физики процесса

• 3.    Постановка задачи

Вызвав в браузере web-страницу или просто начав скачивание какого-то файла с сотового устройства, на базовую станцию отправляется соответствующий запрос, который впоследствии (посредством использующегося протокола, например, протокола TCP/IP) ретранслируется по сети и доходит (по указанному в запросе ІР-адресу) на соответствующий сервер. С сервера начинается закачивание пакетов (отвечающих запросу) в буфер базовой станции. Буфер (ресурсы памяти), который базовая станция может выделить этим пакетам (поступающим с сервера), ограничен. Поэтому довольно типично закачивание больших файлов на сотовые устройства через базовую станцию осуществляется посредством нескольких заполнений/опустошений соответствующего буфера. Докачка с сервера продолжается только в момент, когда для этого освободится место (соответствующий буфер базовой станции полностью очистится), а это, в свою очередь, зависит от алгоритма, осуществляющего распределение ресурсов базовой станции. Характерное время, через которое начинается новая докачка в буфер базовой станции RTT, составляет 30 мс (миллисекунд). Есть известный закон, определяемый используемым протоколом TCP/IP, «геометрической прогрессии с насыщением», которому подчиняются размеры закачиваемых на базовую станцию порций файла. Базовая станция работает в определенном (ограниченном) диапазоне (несущих) частот. Этот диапазон разбит на интервалы частот, в каждом из которых базовая станция посылает (в каждую единицу времени ~ 1 мс) пакеты (данные) на одно из сотовых устройств. Таким образом, осуществляется постепенное опустошение буферов. Число пакетов (трафик) т^(t), которые можно в данный момент времени t передать (послать) от базовой станции пользователю к определяется его текущим местоположением (изменив это положение на несколько метров, пользователь заметно меняет интерференционную картину, складывающуюся в результате всевозможных отражений несущих волн от зданий и т.п.). Это приводит к тому, что тДк) непостоянны во времени. Типично, что т ^ (t) колеблются вокруг некоторого среднего значения с амплитудой, составляющей ~ 30% от этого среднего значения. Однако эти колебания носят существенно случайный (не регулярный) характер.

Все эти детали необходимо, конечно, учитывать при разработке алгоритма для планировщика, распределяющего ресурсы базовой станции среди клиентов. Для этого существуют специальные пакеты (симмуляторы) типа NS3. Однако в данной работе, как и в подавляющем большинстве других работ, разработка алгоритма для планировщика будет осуществляться при дополнительных упрощающих предположениях.

В частности, будем далее считать, что {т^(t)}_f является i.i.d. последовательностью (последовательностью независимых одинаково распределенных случайных величин). Величины т ^ (t) известны на базовой станции.

Аппаратура, установленная на базовой станции, вполне позволяет работать с поступающими данными (и хранить их) так, как это делает современный ноутбук. Доступным наблюдению на базовой станции являются объем уже переданного трафика на сотовое устройство (Rk(t) — размер трафика, нереданного к моменту t пользователю к) и текущий размер буферов, отвечающих активным в каждый момент пользователям (bk(t) — размер буфера пользователя к в момент t). Подчеркнем, что речь идет о размере буферов на базовой станции, но не на сервере. Размер буфера на сервере (объем того, что надо в итоге скачать), который может быть заметно больше, чем на базовой станции, к сожалению, не доступен наблюдению. Со временем ситуация может измениться, когда протокол передачи данных будет позволять передавать информацию о размере всего файла в первых пакетах и это можно будет считывать. Однако сейчас надо исходить из того, что базовая станция «не знает», сколько еще лежит на сервере данных, которые впоследствии надо будет закачать в соответствии с запросом пользователя. Объем файла, который хочет скачать пользователь к, обозначим через Ak- Для простоты мы отождествляем номер пользователя и номер файла. Понятно, что один пользователь может закачивать несколько файлов. Однако, не ограничивая общности, можно вторую сессию того же пользователя просто воспринимать как нового пользователя (если не пытаться учитывать в параметрической модели какие-то закономерности того, что это один и тот же человек - на данном этапе мы не будем на этом останавливаться).

Число клиентов (пользователей), доступных в данный момент, также всегда известно, и на каждого из них базовая станция заводит свой буфер. Число пользователей меняется со временем (кто-то приходит, кто-то уходит, когда его обслужили). Вся информация о появлении новых пользователей (Т⁰ — момент прихода пользователя к) и об уходе пользователей ( Т¹^ — момент уход а пользователя к) на базовой станции известна.

Таким образом, на базовой станции хранится история {тк (t)}k р {bk (t)}k p {Rk (t)}k p {Тк}k> V^k^'kk’ {Ak )k>^ИСХОД^{Я из} которой требуется построить оптимальное расписание распределения (временных) ресурсов базовой станции (будем обозначать это расписание буквой ж) в смысле критерия ALPT (Application Level Perceived Throughput):

F (ж) ^п=' lim

T Mro

1    ^N ( ^T )        A

1             ^A k

W) k= Т^ж)

—

t? ^

max ж

или logALPT

F(ж) n=L lim v ’ tx N (T)

N (T )

E logf k=1     V

^A k Т^Д)

—

T^J

^ max.

ж

• 4.    Краткий обзор литературы по близким постановкам (индексы)

шах

кЕ [ текущие

[пользователи

Т к (t)

) ^Ө к ^{(t —} 1)

(PFS)

называют Proportional-Fair Sharing (PFS).

С технической точки зрения, за такт времени базовая станция может обслуживать одновременно несколько клиентов. PFS (в варианте [2]) обобщается на этот случай. Однако всегда можно путем дополнительного (условного) разделения (частотным образом) ресурсов внутри такта времени свести постановку к рассмотрению ситуации, когда за такт времени базовая станция обслуживает ровно одного клиента. Далее мы будем именно так и считать.

Если считать, что т^(t) = г^ ив качестве критерия использовать

N (т )

ҒД) =L Ііш - У У^nd(x) — Т0') ^ min, т-\ Т^Х^       к    X к=1

то функционал можно представить классическим (для динамического программирования)

образом

Ғд1) =L

Ііш

Дю1-0

1 1—5

∞∞

уу^[

t=1 к=1

к-н клиент появился, но еще не полностью обслужен

]

Оптимальный алгоритм здесь [7]

arg

к Е^

шах текущие пользователи

Т к (t)

) ^Afe ^{— R} fe ^{(t —} 1)

К сожалению, этот (индексный) алгоритм (его обычно называют SRPT) относится к классу opportunistic (size-aware, anticipating). Это означает, что алгоритм требует знания А_к еще до момента полной загрузки клиентом файла. В реальности базовые станции узнают A fe только в момент полной загрузки файла (и никак не раньше). С помощью индексов Гиттинса [3] можно предложить non-anticipating вариант. Слабым местом здесь является не столько критерий¹, сколько предположение т ^ (t) = т^, которое далеко от истины. Численные эксперименты с реальными данными показали, что такое предположение является слишком грубым.

В литературе можно найти такой вариант SRPT-индекса:

arg max    -y^ (SE CTF), y^ Г текущис 1 У к (t)

[пользователю arg    max               (DAS).

к^ теку щис    ^R y ^(t 1)

[пользователиJ

Имеются также другие индексы, которые в определенных ситуациях используют на практике. Например, Round Robin, arg max y^ Г текущие ] [пользователю

—(PS), t ~ ^Tk

arg max     -y (t) (MaxC/I), k£ [пользователю arg r max M^ (TAS). ке\ тскуЩис P тУ [пользователю

Эти индексы имеют вполне понятный физический смысл (мы не будем здесь это обсуждать).

• 5.    Предложенные индексы

Рассмотрим выражение для критерия ALPT:

1 ^N

^A y

T end   t 0 ,

ALPT — N Е k=1

после чего заменим выражение под знаком суммы на его приближенное значение:

^А к

T end    т 0

______A y ______~______ A y______

(t - T 0 ) + (T l ^nd - t)   (t _ T°) + ^ - R yR- y .

В данном выражении фигурирует Ay, неизвестное нам до момента окончательной загрузки файла. Однако можно заменить Ay в данной формуле на некоторое ожидаемое expected значение Ay . Рассмотрим простои случаи, когда Ay есть случайная величина из распределения Парето n(Ay |m, а), г де m, а — некоторые известные константы. Тогда, по определению:

am “   const

^p(Ay) — a « +i ^— A“+1.

Из этого выражения видим, что вероятность обратно пропорциональна A“+1, что и будет использовано в дальнейшем.

Известно, что к моменту времени t на устройство уже была скачана некоторая часть файла размером R y (t — 1). Следователь но, оценивая A y в момент времени t, следует предположить, что Уж <  R y (t — 1) вероятность р(ж) — 0. То есть в дальнейшем мы будем использовать некоторую вероятностную функцию р : R ^ [0,1], такую что Уж <  R y (t — 1) : р(ж) — 0, а для ж >  R y (t — 1) будет выполняться р(ж) ~ ук+1-

Пусть С — коэффициент пропорциональности в выражении для р. Потребуем, чтобы выполнялось

∞

/      p(A y )dA y

— 1,

J Ry ( ^t— 1)

то есть

С Г   A

JR_k (t-1) ^A-+1

= С /      A-^(-+1)dA_k = С • (^A--)

JRk--^                 --“ /

∞

С

R _k (t - 1)     ctR^-^   1)

откуда

С = «R^-(t - 1).

Пусть

^expected d=. /

A k p(A_k )dA_k .

У Rk(t—1)

Тогда, используя полученное выражение для р, получаем

Ak^c_P^ected = f"° «R - ^- dA_k = _aR^- [°° ^dA^k = «R- ( dL ^-^       ,

'^Rk^{(t-1) A}k              ^RR_k^{(t-1) A-}          V ^-c) R k (t - 1)

A' ^X^ = « R-(t - 1) • R_k-^- (_t - 1) = ^Rk(t - 1). c - 1                       c - 1

_m                                                             a expected

Хеперь подставим полученное ожидаемое значение Ak     в оценку (1) выражения из формулы для ALPT, из чего получим некоторое ожидаемое значение критерия для к-го клиента:

«         R k (t - 1)

(T) ,

·

« - 1 (+ — Т°   ДД-Д

^{(t T} k ^{) +} C 1 R (t)

которое может быть использовано в качестве индекса: максимизируя это выражение мы также будем максимизировать и одно из слагаемых критерия качества ALPT.

Глядя на выражение для Т, можно понять, что значение индекса будет увеличиваться в следующих случаях:

• 1)    R k (t - 1) возрастает;

• 2)    Pk(t) возрастает;

• 3)    (t - Д) убывает.

• 6.    Вычислительный эксперимент

Тогда можно предложить упрощенный индекс, отражающий приведённые зависимости индекса Т

R k (t - 1)Tk (t) t -T k

(TK) .

В рамках данной работы была поставлена серия вычислительных экспериментов, целью которых является сравнение различных подходов для построения индексных стратегий. Эксперименты проводились на синтетических данных, и их задачей было ответить на следующие вопросы:

• 1)    Насколько хорошо работают предложенные в данной работе индексы по сравнению с уже имеющимися?

• 2)    Можно ли получить лучшее решение, если рассматривать не индексы по отдельности, а их линейные комбинации?

• 3)    Можно ли получить лучшее решение, если рассматривать вероятностные комбинации индексов?

• 6.1.    Описание данных

Для генерации данных был реализован эмулятор работы сотовой вышки и очереди клиентов. Код написан на языке Python 3.5 и находится в открытом доступе по ссылке2. В основе работы эмулятора лежит параметрическая модель генерации данных, базирующаяся на следующих предположениях:

• е    Времена между приходами двух подряд идущих клиентов Т^+і — Т 0 есть н. о. р. случайные величины из показательного распределения

р(х) = Ехр(ж|А).

В наших экспериментах А = 0.09, что соответствует средней нагрузке на систему в размере 11 клиентов в секунду.

• •    Размеры скачиваемых файлов А к есть н. о. р. случайные величины из смеси распределений Парето:

к

р(ж) = У^ р»П(ж|тда), г=1

где число элементов смеси соответствует количеству различных типов файлов, где каждый тип имеет свой характерный размер. В наших экспериментах использовалось 4 различных значения размеров файлов, соотуветствующих загрузке страницы с текстом, работе приложения, прослушивания аудиозаписи и просмотру видеоролика (в килобайтах): т і = 500,m2 = 5000, m3 = 25 000,т4 = 62 500. Соответствующие значения вероятностей р 1 = 0.4, р₂ = 0.3, рз = 0.2, р₄ = 0.1, пара метр a = 5.5.

• •    Пропускные способности устройств клиентов Т к (t) есть н. о. р. случайные величины из равномерного распределения:

р(ж) = и(ж|ок (t), Ьк (t)).

В наших экспериментах каждому из пользователей в момент создания запроса к базовой станции присваевается средняя пропускная способность Тк, являющаяся случайной величиной из равномерного распределения:

р(х) = U

(X

¯

-,3АА).

И для каждого определенного пользователя

«к(t) = 0.7 • 2 (sin (10-4 • 5 + 0.1) + 1) • Т к ,

Ь к (t) = 1.3 • - (sin (10^-4 • 5 + 0.1) + 1) • Т к .

• 6.2.    Сравнение различных индексов

• 6.3.    Линейная комбинация индексов

В первом эксперименте мы оцениваем качество работы планировщиков, построенных на различных индексах, и сравниваем, как качество работы предложенных в работе индексов соотносится с ними. Максимизируемым функционалом качества был выбран logALPT (аналогичные результаты наблюдались и для ALPT):

^1<)gALPT   N £ log (Тк^П('— Тк⁰ ) .

В табл. 1 приведены значения критерия logALPT для различных индексов в эксперименте на синтетических данных. Как видно, предложенные индексы Т и ТК реализуют лучшие стратегии планировщика, чем все остальные индексы. В формуле, задающей индекс Т. значение константы С = _1п(0з⁶/₇) •

Таблица!

Значение функционала logALPT для различных индексных стратегий

Индекс	Формула	logALPT
T	R k (t - 1) о , Rk ё-1) t Tk + №к (t)	4 . 01 ± 0 . 09
TK	Т к (t)R k (t-1) t - T 0	3 . 93 ± 0 . 03
RoundRobin	1 t - Д О	3.69 ± 0.03
TAS	T k (t) t—T0	3.50 ± 0.05
Max C/I	Г к (і)	1.38 ± 0.24
DAS	Т к (t) R k (t-1)	0.71 ± 0.14
PF	Т к (t)(t - T k ) Rk (t-1)	-1.16 ± 0.05

В данном эксперименте новый индекс задаётся как линейная комбинация нескольких базовых индексов. Так как каждый индекс представляет собой некую оценку приоритета обслуживания клиента, их можно объединить в взвешенную линейную комбинацию, которая будет учитывать особенности сразу нескольких индексов:

к

Д((ДЛ, , ...Дк ) = ’^2'ШгІг, W1, . . . ,Wk > 0.

г=1

На рис. 1 показан график зависимости критерия качества logALPT от весов линейной комбинации (в данном случае это один параметр а, т.к. индексы, отличающиеся в константное число раз, дают одну и ту же стратегию планировщика и мы можем положить вес первого индекса равным 1). Лучшее значение функционала достигается при а = 0, что соответствует индексу А,, = /таз- Линейная комбинация индексов не даёт никакого выигрыша.

• 6.4.    Вероятностная комбинация индексов

В данном эксперименте индексная стратегия представляет собой вероятностную смесь нескольких уже известных индексов. Каждый раз перед тем как сделать выбор, какого клиента обслужить, разыгрывается случайная величина, определяющая индекс, который будет использоваться на данном шаге. Получаемая новая индексная стратегия может быть формально записана как

Дг(ДДД...,. Дк ) =

1 1 , с вероятностью р 1 ;

с вероятностью р2;

к

52 р г = 1.

г=1

1 к , с вероятностью р к .

I = CrAS + «/Huawei

Рис. 1. Значение критерия logALPT для линейной комбинации двух индексов: TAS и DAS. Как видно, наибольшее значение достигается на границе, что соответствует использованию одного лишь индекса TAS

На рис. 2 показан график зависимости функционала logALPT от вероятностей элементов смеси р 1 ,р₂,р з для комбинации из трёх индексов: Т, TAS и DAS. Лучшее значение функционала достигается тогда, когда мы на каждом шаге эмуляции выбираем индекс Т и никогда не выбираем TAS или DAS. Вероятностная комбинация индексов не позволяет улучшить качество работы планировщика.

Рис. 2. Значение критерия logALPT для вероятностной комбинации трёх индексов: Т, TAS и DAS. Как видно, наибольшее значение достигается на границе, что соответствует постоянному выбору одного индекса (Т) с вероятностью единица

• 7.    Заключение

• 8.    Благодарности

  Работа была написана во время июльской проектной смены 2017 года в лагере Сириус. Автор выражает благодарность профессору А.М. Райгородскому и А. С. Гусеву за приглашение и помощь в работе. Автор выражает благодарность Д.А. Шмелькину (Хуавей) и наставникам по проекту А. В. Гасникову и А. В. Грунчуку за ценные комментарии по содержанию работы. А также своим коллегам, в частности, индексы Т и ТК были предложены Тимофеем Ковалевым.

В работе исследуются различные индексные стратегии составления расписания обслуживания клиентов базовой станции (вышки сотовой связи). Показано, что при естественных условиях с помощью (выпуклой) комбинации индексов не удается получить лучший по свойствам индекс. Также в работе были предложены новые индексы, в некотором смысле обратные к общепринятым, которые показали хорошие результаты при использовании популярных у практиков критериев качества составленного расписания: ALPT и logALPT.