Свободная касса

Один из самых близких любому человеку разделов математики наряду с арифметикой — как ни странно, теория массового обслуживания. Это прикладной раздел теории вероятностей, задачи которого окружают нас везде: от очереди в магазине или на посадку в самолет до пробок на дорогах и сетей мобильной связи новейшего поколения. О перспективах развития этого направления и о его практических приложениях редакция N + 1 поговорила с заведующим кафедрой прикладной информатики и теории вероятностей РУДН, профессором Константином Евгеньевичем Самуйловым.

N + 1: Что такое теория массового обслуживания?

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

Теория Марковских цепей описывает работу большого числа процессов в реальном мире, например, работу автопилота и систем хранения, изменение численности популяций организмов в природе, лежит в основе алгоритма PageRank поисковой системы Google и, конечно, служит фундаментом для теории массового обслуживания. В зарубежной литературе она называется теорией очередей. В английском языке используется термин queueing theory.

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

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

И где именно она применяется?

Важнейшее практическое приложение теории массового обслуживания с самого ее возникновения — сфера коммуникаций: сначала телефония, позднее — телекоммуникации.

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

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

Кроме того, мы еще смотрим в будущее и пытаемся понять, какие сети придут на смену нынешним. И соответственно, помогаем им родиться, проектируем их архитектуру.

Что можно сказать о современном состоянии телекоммуникаций с точки зрения теории массового обслуживания?

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

Важный вызов — это дефицит пропускной способности. Доступная полоса частот исчерпана во всех диапазонах вплоть до десятков гигагерц, в лицензируемых диапазонах свободных частот уже просто нет.

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

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

Если ли альтернатива?

В принципе, есть. Например, мы сейчас начали заниматься исследованиями сетей шестого поколения. Это так называемая многоуровневая «летающая и всепроникающая» телекоммуникационная сеть.

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

Что-то похожее на сеть StarLink компании SpaceX?

Примерно так. Причем в исследованиях сетей типа 6G уже недостаточно использовать одну только теорию массового обслуживания. Для эффективного проектирования и последующей эксплуатации таких сетей мы применяем комбинацию методов и подходов.

Мы уже начали изучать летающие сети разного уровня с точки зрения технологии ретрансляции сигнала, используя наземные, воздушные и спутниковые каналы.

А какая здесь математика?

Мы применяем математические инструменты, в том числе стохастическую геометрию. Нужно в каждый момент времени контролировать полет стаи дронов, контролировать местоположение каждого аппарата, выдерживать расстояниями между ними, которые, вообще говоря, случайны.

От расстояний зависит мощность передаваемого сигнала, интерференция сигналов от разных источников, отношение «сигнал-шум», а эти расстояния изменяются и случайны в каждый момент.

Например, в простейшем случае, необходимо решать задачи для треугольников со случайными сторонами или других геометрических фигур в терминах стохастической геометрии в трехмерном пространстве.

Вы говорите о чисто теоретических изысканиях или это часть практической разработки?

Конечно, часть практической разработки. Мы ведь не просто математики, мы работаем в тесной инженерной кооперации. Сейчас группа моих аспирантов и сотрудников находится в Технологическом университете города Брно в Чехии, это технический университет очень высокого уровня.

Как проанализировать надежность и качество канала передачи данных? Можно построить математическую модель — это самый быстрый и дешевый способ, но оценка будет неточной, недостаточной для практического применения.

Более сложный путь — проведение имитационного моделирования. Это дольше и дороже, точность выше, но погрешность все равно остается высокой. Самую полную и точную картину позволят получить лишь физические измерения на действующих объектах.

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

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

Необходимо описать с помощью стохастической геометрии взаимное расположение летящих дронов. Также надо описать и смоделировать поведение абонента, описываемое той или иной моделью случайного блуждания random walk, — этим случайным перемещениям абонента также посвящен известный раздел теории вероятности.

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

Каков вклад именно вашей группы в этот проект?

Мы хорошо разбираемся в приложениях для высокочастотных сетей. Важная их часть — выделение пользователям емкости канала по их запросу, то, что по-английски называется capacity-on-demand.

Для моделирования можно применять вычислительные инструменты — такие, как пакеты программ компании Wolfram Research. С их помощью можно проводить весьма сложные вычисления в аналитическом виде, например, вычислять в символьном виде обратное преобразование Лапласа. Но в силу сложности задач не всегда удается их решить за требуемое для индустрии время, которая значительно опережает фундаментальные исследования.

Получаемые теоретические наработки собираются и становятся основой для получения новых, чисто математических научных результатов.

Как можно описать эти результаты?

Недавно в журнале Probability in the Engineering and Informational Science у нас с соавторами вышла статья, в которой мы подробно описали решение для нового класса задач теории очередей для случая, когда пользователи могут не только забирать во временное пользование ограниченный ресурс системы, но также и добавлять свой ресурс в систему, расширяя ее возможности.

Ресурс, приносимый потребителем, описывается как отрицательный расход, при этом общий объем ресурсов, выделяемых потребителям, должен быть неотрицательным и не должен превышать предопределенные максимальные уровни (пороги).

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

Таким образом, нам удалось дать математическое описание этой новой в теории массового обслуживания идее.

Для решения каких задач, за пределами телекоммуникаций, можно применить разработанный вами математический аппарат?

Например, для разного рода систем бронирования. Представьте себе систему бронирования билетов на транспорте или товаров в интернет-магазине.

Важно, что тут мы говорим не про покупку, а про бронирование как действие, которое можно отменить. Человек забронировал себе некий ресурс, а потом снял бронь, и ресурс должен вернуться в систему.

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

А можно ли применить вашу методику, например, к области финтеха? Или к движению криптовалют?

В принципе, да, но надо понимать, что это особенные сферы, со своей информационной спецификой. Так, если взять задачи финансового рынка, то для него характерна закрытость информации. Соответственно, применять новые теории на этом рынке можно лишь очень ограниченно.

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

Беседовал Павел Бузин