МЕТОД ШТРАФНЫХ ФУНКЦИЙ ДЛЯ ЗАДАЧИ РАСПРЕДЕЛЕНИЯ МОЩНОСТЕЙ ПРОВАЙДЕРОВ В СЕТЯХ ТЕЛЕКОММУНИКАЦИИ
|
ВВЕДЕНИЕ 3
1. Постановка задачи 6
2. Обзор актуальных решений смежных задач 9
3. Решение задачи 12
3.1. Общая схема решения 12
3.2. Использование метода штрафных функций для задачи с ограничениями
мощностей 14
3.3. Применение метода условного градиента 17
3.4. Задача однопродуктового аукциона 22
3.5. Точность решения вспомогательной задачи с использованием метода
штрафных функций 24
4. Особенности реализации 27
5. Результаты экспериментов 33
ЗАКЛЮЧЕНИЕ 41
СПИСОК ЛИТЕРАТУРЫ 43
ПРИЛОЖЕНИЯ
1. Постановка задачи 6
2. Обзор актуальных решений смежных задач 9
3. Решение задачи 12
3.1. Общая схема решения 12
3.2. Использование метода штрафных функций для задачи с ограничениями
мощностей 14
3.3. Применение метода условного градиента 17
3.4. Задача однопродуктового аукциона 22
3.5. Точность решения вспомогательной задачи с использованием метода
штрафных функций 24
4. Особенности реализации 27
5. Результаты экспериментов 33
ЗАКЛЮЧЕНИЕ 41
СПИСОК ЛИТЕРАТУРЫ 43
ПРИЛОЖЕНИЯ
Актуальность работы обусловлена, прежде всего, ростом объема передаваемых данных в телекоммуникационных сетях. Из-за этого фактора провайдерам становится все сложнее распределить свои ресурсы. Повышаются требования для технических характеристик оборудования, для обслуживания клиентов необходимы значительные мощности, и это влечет все большие трудности при распределении имеющихся ресурсов. Необходимо знать, что у каждого обслуживаемого абонента есть определенный минимум по уровню услуг, который провайдер в конечном счете должен ему предоставить. Точно так же, как у любого провайдера есть суммарное ограничение по мощности ввиду его финансовых и технических возможностей. Кроме того, необходимо соблюсти финансовое условие неотрицательности прибыли, которую получит провайдер с учетом его затрат на обслуживание всех абонентов.
Все это значительно осложняется ростом трафика, а также непосредственного увеличения количества участников, как провайдеров, так и абонентов. В настоящее время однозначно прослеживается тенденция к росту активности в мобильных сетях не только в России, но и во всем мире. Это хорошо демонстрирует отчет компании Cisco, «Cisco VNI Forecast». Ежегодно специалистами компании выпускаются прогнозы по увеличению трафика, в которых отслеживаются и прогнозируются воздействия сетевых приложений на глобальные сети. В данных отчетах представлены основные глобальные прогнозы движения мобильных данных и тенденций роста [1]. Приведем некоторую статистику из отчета, выпущенного в декабре 2018 года.
Средняя скорость мобильной передачи данных стремительно растет. Для сравнения в конце 2015 года она составляла 4,4 экзабайта в месяц (один экзабайт равен одному миллиарду гигабайт). В 2017 году скорость мобильного трафика выросла в 2 раза. Средняя скорость в 2017 году составляла 12 Мбит/с, а в 2016 - 6,8 Мбит/с. Если взглянуть на статистику предыдущих 5 лет, то можно заметить, что объем всего трафика вырос в 18 раз [2]. К 2022 году специалисты Cisco предсказывают увеличение мобильного трафика на 46% (Рисунок 1).
Специалисты компании Cisco считают, что к 2022 году общий объем мобильного трафика вырастет в семь раз и достигнет 77 экзабайт в месяц, а средняя по всему миру скорость мобильного соединения превысит 20 Мбит/с. Фактическое увеличение объема данных за 5 лет сложно предсказуемо, поэтому стоит ожидать, что рост увеличится более чем в 7 раз. Кроме того, также растет количество различных типов мобильных устройств. Прогноз роста объема передачи данных по всему миру для них представлен на рисунке 2.
Global Internet Traffic by Device Type By 2022, non-PC devices will drive 81% of global Internet traffic
Одна из основных задач, которые возникают в данной области, заключается в распределении мощностей между заявками классов своих абонентов, поступающих за ограниченное количество времени. Как правило, у каждого абонента или класса абонентов есть определенная заявка по количеству услуги, которое он запрашивает. Однако в то же время у любого провайдера есть суммарное ограничение по мощности ввиду его финансовых и технических возможностей. Абоненты часто находятся в движении, и их количество постоянно меняется. В следующий отрезок времени исходные данные изменяются, и необходимо искать новое решение. Поэтому важно достаточно быстро решать задачи по распределению ресурсов провайдеров между своими абонентами.
Целью работы является создание алгоритма, способного решить задачу распределения мощностей провайдеров с заданной точностью. Предлагается алгоритм, состоящий из комбинации трех методов - метода штрафных функций, метода условного градиента и метода решения классической задачи аукциона. Были поставлены задачи разработки модели согласования параметров между используемыми методами, программной реализации созданного алгоритма и анализа результатов проведения экспериментов по выработке оптимальной стратегии изменения параметров созданного алгоритма.
Все это значительно осложняется ростом трафика, а также непосредственного увеличения количества участников, как провайдеров, так и абонентов. В настоящее время однозначно прослеживается тенденция к росту активности в мобильных сетях не только в России, но и во всем мире. Это хорошо демонстрирует отчет компании Cisco, «Cisco VNI Forecast». Ежегодно специалистами компании выпускаются прогнозы по увеличению трафика, в которых отслеживаются и прогнозируются воздействия сетевых приложений на глобальные сети. В данных отчетах представлены основные глобальные прогнозы движения мобильных данных и тенденций роста [1]. Приведем некоторую статистику из отчета, выпущенного в декабре 2018 года.
Средняя скорость мобильной передачи данных стремительно растет. Для сравнения в конце 2015 года она составляла 4,4 экзабайта в месяц (один экзабайт равен одному миллиарду гигабайт). В 2017 году скорость мобильного трафика выросла в 2 раза. Средняя скорость в 2017 году составляла 12 Мбит/с, а в 2016 - 6,8 Мбит/с. Если взглянуть на статистику предыдущих 5 лет, то можно заметить, что объем всего трафика вырос в 18 раз [2]. К 2022 году специалисты Cisco предсказывают увеличение мобильного трафика на 46% (Рисунок 1).
Специалисты компании Cisco считают, что к 2022 году общий объем мобильного трафика вырастет в семь раз и достигнет 77 экзабайт в месяц, а средняя по всему миру скорость мобильного соединения превысит 20 Мбит/с. Фактическое увеличение объема данных за 5 лет сложно предсказуемо, поэтому стоит ожидать, что рост увеличится более чем в 7 раз. Кроме того, также растет количество различных типов мобильных устройств. Прогноз роста объема передачи данных по всему миру для них представлен на рисунке 2.
Global Internet Traffic by Device Type By 2022, non-PC devices will drive 81% of global Internet traffic
Одна из основных задач, которые возникают в данной области, заключается в распределении мощностей между заявками классов своих абонентов, поступающих за ограниченное количество времени. Как правило, у каждого абонента или класса абонентов есть определенная заявка по количеству услуги, которое он запрашивает. Однако в то же время у любого провайдера есть суммарное ограничение по мощности ввиду его финансовых и технических возможностей. Абоненты часто находятся в движении, и их количество постоянно меняется. В следующий отрезок времени исходные данные изменяются, и необходимо искать новое решение. Поэтому важно достаточно быстро решать задачи по распределению ресурсов провайдеров между своими абонентами.
Целью работы является создание алгоритма, способного решить задачу распределения мощностей провайдеров с заданной точностью. Предлагается алгоритм, состоящий из комбинации трех методов - метода штрафных функций, метода условного градиента и метода решения классической задачи аукциона. Были поставлены задачи разработки модели согласования параметров между используемыми методами, программной реализации созданного алгоритма и анализа результатов проведения экспериментов по выработке оптимальной стратегии изменения параметров созданного алгоритма.
Главным образом, сложность процедуры поиска решений исходной задачи (1) вытекает из того, что функции могут быть нелинейными, и в настоящее время не существует универсального способа её решения. Однако мы можем свести исходную задачу к задаче аукциона. В этом случае нам потребуется решить задачу аукциона для каждого из абонентов, и это решение будет решением исходной задачи.
Для того чтобы найденные решения являлись решениями задачи распределения мощностей, необходимо, чтобы найденные объемы для всех абонентов в сумме не превосходили ограничений по мощностям для каждого из провайдеров. Кроме того, чтобы можно было перейти к задаче аукциона, нужно привести сложную (в общем случае) функцию к константе. Это две главные задачи в рамках данной работы. Первый вопрос был решен с помощью метода штрафов. Добавление штрафных слагаемых к исходной функции обеспечили условие ограничений по мощностям провайдеров. Второй вопрос с нелинейностью решен с помощью метода условного градиента.
Чтобы сразу избежать трудностей при дальнейшем сцеплении решений (у разных абонентов могут быть найдены такие объемы услуг от одного и того же провайдера, что их сумма превысит допустимые возможности технического оборудования этого провайдера), изначально мы использовали метод штрафных функций.
Так как на этом этапе мы решали вопрос о соблюдении неравенства Tj7j=ixij ^ о1, i = 1 , т, то штрафная функция была выбрана такой, чтобы она давала положительное значение, когда оно не выполняется. Таким образом, к нашей исходной функции прибавлялась функция следующего вида: рк ф1(х), где k - это итерация метода штрафа. При этом коэффициент штрафа - рк > 0, Пт рк = ю, а функция, обеспечивающая положительное значение, -
Таким образом, была достигнута цель работы - алгоритм, решающий задачу распределения мощностей провайдеров, использует следующую комбинацию методов: исходная задача решается методом штрафной функции, который сводится к решению задач минимизации функций с помощью метода условного градиента, которые решаются с помощью метода решения классической задачи аукциона для каждого фиксированного абонента. В результате выполнения работы были выполнены поставленные задачи: разработана модель согласования параметров между используемыми методами, созданный алгоритм был программно реализован, а также был выполнен анализ результатов проведения экспериментов, в результате которого была найдена оптимальная стратегия изменения параметров созданного алгоритма.
Для того чтобы найденные решения являлись решениями задачи распределения мощностей, необходимо, чтобы найденные объемы для всех абонентов в сумме не превосходили ограничений по мощностям для каждого из провайдеров. Кроме того, чтобы можно было перейти к задаче аукциона, нужно привести сложную (в общем случае) функцию к константе. Это две главные задачи в рамках данной работы. Первый вопрос был решен с помощью метода штрафов. Добавление штрафных слагаемых к исходной функции обеспечили условие ограничений по мощностям провайдеров. Второй вопрос с нелинейностью решен с помощью метода условного градиента.
Чтобы сразу избежать трудностей при дальнейшем сцеплении решений (у разных абонентов могут быть найдены такие объемы услуг от одного и того же провайдера, что их сумма превысит допустимые возможности технического оборудования этого провайдера), изначально мы использовали метод штрафных функций.
Так как на этом этапе мы решали вопрос о соблюдении неравенства Tj7j=ixij ^ о1, i = 1 , т, то штрафная функция была выбрана такой, чтобы она давала положительное значение, когда оно не выполняется. Таким образом, к нашей исходной функции прибавлялась функция следующего вида: рк ф1(х), где k - это итерация метода штрафа. При этом коэффициент штрафа - рк > 0, Пт рк = ю, а функция, обеспечивающая положительное значение, -
Таким образом, была достигнута цель работы - алгоритм, решающий задачу распределения мощностей провайдеров, использует следующую комбинацию методов: исходная задача решается методом штрафной функции, который сводится к решению задач минимизации функций с помощью метода условного градиента, которые решаются с помощью метода решения классической задачи аукциона для каждого фиксированного абонента. В результате выполнения работы были выполнены поставленные задачи: разработана модель согласования параметров между используемыми методами, созданный алгоритм был программно реализован, а также был выполнен анализ результатов проведения экспериментов, в результате которого была найдена оптимальная стратегия изменения параметров созданного алгоритма.