Использование алгоритмов мультистарта и поиска с запретами для решения задачи размещения базовых станций

УДК 621.395.7, 519.854 doi:10.15217/issn1684-8853.2015.3.99

ИСПОЛЬЗОВАНИЕ АЛГОРИТМОВ МУЛЬТИСТАРТА И ПОИСКА С ЗАПРЕТАМИ ДЛЯ РЕШЕНИЯ ЗАДАЧИ РАЗМЕЩЕНИЯ БАЗОВЫХ СТАНЦИЙ

Е. С. Скакова, аспирант

В. Н. Малыша, доктор техн. наук, профессор

аЛипецкий государственный педагогический университет, Липецк, РФ

Постановка проблемы: синтез топологической структуры беспроводной сети передачи данных подразумевает планирование территориального размещения базовых приемо-передающих станций на местах-кандидатах и подключение к ним клиентов. Недостатками существующих подходов к решению этой задачи являются использование методов, не показывающих высокую скорость расчета (метода ветвей и границ, эвристического метода Лагранжа и др.); отсутствие ограничений, учитывающих уровень затухания сигнала при распространении от базовой станции к клиенту и обратно, а также уровень межсотовых помех; использование всего одного типа базовых станций. Целью исследования является создание модели решения задачи размещения базовых станций, не имеющей указанных недостатков. Результаты: сформулирована задача размещения базовых станций с учетом уровня отношения сигнала к помехам для клиентов сети. Решение задачи представляется в виде вектора структур, каждая из которых хранит информацию об одном месте-кандидате (тип установленной базовой станции, список подключенных клиентов). Разработаны модификации алгоритмов вероятностного поиска с запретами и мультистарта, в основе которых лежит понятие окрестности текущего решения. Новое решение из окрестности текущего может быть получено при помощи одной из шести операций: смены типа одной станции на более дешевый/дорогой, переподключения одного клиента, удаления одной базовой станции, добавления одной станции, перемещения одной базовой станции. С целью избежать «застревания» в локальных опти-мумах при поиске с запретами алгоритму запрещается просматривать решения из списка запретов. Новизна подхода заключается в том, что в список запретов добавляются не конкретные прошлые решения, а операции по изменению конфигурации сети, которые могут вернуть нас в старые локальные оптимумы. Сущность модифицированного алгоритма мультистарта состоит в следующем: используются всего две операции для получения нового решения (удаление базовой станции и смена типа на более дешевый), просматривается только часть окрестности, переход к новому решению осуществляется по принципу «первое улучшение», алгоритм поиска лучшего решения запускается несколько раз. Разработанные алгоритмы реализованы как программное обеспечение на языке Delphi. Показано, что новые алгоритмы демонстрируют лучшие результаты, чем метод локального поиска. Практическая значимость: разработанные модификации методов мультистарта и поиска с запретами позволяют находить решение задачи размещения базовых станций за приемлемое время, на много порядков быстрее точного метода полного перебора. Выявлена зависимость качества решения поставленной задачи методом вероятностного поиска с запретами от длины списка запретов и значения параметра рандомизации окрестности.

Введение

Как известно [1], задача проектирования сети (в том числе и беспроводной) может быть сведена к отысканию минимума функционала приведенной стоимости при наличии ограничений на вероятностно-временные и структурные характеристики сети и при требовании принадлежности множества вариантов архитектуры сети к области технически реализуемых решений.

Среди русскоязычных публикаций по проблеме размещения базовых станций (БС) отметим работу [2], посвященную сетям WiMAX. Подробная классификация алгоритмов размещения БС для сетей UMTS 3G дана в статье [3].

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

Постановка задачи размещения БС

Задача размещения БС заключается в том, что у нас есть Ы1р клиентов, каждого из которых необходимо подключить к БС. Базовая станция может быть установлена на одном из Ырв мест-кандидатов. Имеется И1уре1, типов БС, отличающихся по своим характеристикам. Задача сводится к минимизации общей стоимости установленных БС при выполнении ряда ограничений.

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

именем [4]. В нашем случае структура содержит в себе три поля:

— переменную type, показывающую, какого типа БС установлена на данном месте-кандидате (если type = 0, то БС не установлена);

— переменную clnbr — число клиентов, подключенных к данному месту;

— одномерный массив (вектор) целых чисел CL размерности clnbr, содержащий номера клиентов, подключенных к данному месту.

Решение задачи мы будем представлять в качестве вектора Sol, элементами которого являются структуры, соответствующие местам-кандидатам (здесь и в дальнейшем запись вида A[j] означает обращение к j-му элементу вектора A; элементы массивов нумеруются, начиная с 1). Обращение к полю обозначается при помощи символа «.». То есть Sol[4].type означает тип БС 4-го места-кандидата, а, например, Sol[5].CL[3] — номер 3-го клиента, подключенного к БС на месте № 5.

Клиент может быть подключен к месту-кандидату, только если на нем уже установлена БС, т. е. для каждого места, у которого Sol[s].cl_nbr Ф 0, должно выполняться неравенство Sol[s].type ф 0.

Пусть b — вектор, элементами которого являются требуемые полосы пропускания для клиентов; р — вектор, элементами которого являются максимальные производительности БС разного типа. Для каждой установленной БС суммарный требуемый трафик не должен превосходить максимально возможную производительность оборудования:

Sol [s].cl_nbr

E b [Sol[s].CL[i]]< р [Sol[s].type] i=1

"s е{1,2,..., Nps }. (1)

Пусть Pgr — вектор, элементами которого являются максимальные мощности БС разного типа; PTpax — вектор максимальных мощностей клиентов; P¿aT — вектор, элементами которого являются чувствительности БС разного типа; PTa — вектор, элементами которого являются чувствительности клиентов; G — двумерный массив (матрица) размерности Ntp х Nps, каждый элемент которого 0 < G[i][s] < 1 отражает уровень затухания между i-м клиентом и местом установки s.

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

G [Sol[s].CL[i]][s]. PgSP [Sol[

PÍP1" [Sol [s].CL[i]

].tVPe\\ > 1

"s e{l,2,..., Nps}, "i e Sol [s].CL.

Ограничение (2) составлено для режима downlink. Для режима uplink аналогичное ограничение выглядит следующим образом:

G [Sol[s].CL[i]][s]. PTT [Sol[s].CL[i]&

"ве{1,2,...,ырз}, "Iе8о1[в].еь. (3)

Целевая функция, которую необходимо минимизировать, имеет вид

Ф = E Cost [Sol[s]. type] +

Nps Sol [s].cl_nbr

+ E £ SIRdB ■ k,

где Cost — вектор стоимостей (включая установку) БС разного типа.

Первое слагаемое (4) — суммарная стоимость комплекса. Второе слагаемое отвечает за учет уровня SIR для всех клиентов системы. SIR — отношение уровня сигнала к уровню помех (signal-to-interference ratio) [5], в общем случае оно рассчитывается так:

SIRdB = l°lg(Psignal /interference )■ (5)

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

Gsi ■ Pgax [Sol[s].type]

Nps Sol[q].cl_nbr

E E Gqz ■ Pfsax [Sol[q].type] ■ w^

Gsi = G [Sol[s].CL[i]][s], Gqz = G [Sol[[q ].CL[z]][q ], где wsi = 0, если s = q и i = z, иначе wsi = 1.

Коэффициент k обеспечивает одновременный учет в целевой функции затрат на создание сети и уровня SIR клиентов. k имеет размерность стоимости комплекса БС, тем самым обеспечивая сохранение размерности в формуле (4), так как SIR — безразмерная величина. k должен обеспечивать «штраф» за низкий уровень SIR и «награду» за высокий. В данной работе принято k = -10 условных единиц стоимости (k имеет отрицательное значение, так как мы решаем минимизацион-ную задачу, а значит, хороший высокий уровень SIR должен уменьшать целевую функцию).

Необходимо отсортировать типы БС по возрастанию цены. В дальнейшем мы будем исходить из того, что i-й тип БС дороже (i - 1)-го и дешевле (i + 1)-го.

Метод локального поиска

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

Ниже представлен простейший алгоритм ЛП для задачи минимизации [7]. Предполагается, что вектор x — решение некоторой оптимизационной задачи. Множество всех возможных векторов обозначим X. Пусть требуется минимизировать некоторую функцию f(x) на множестве X:

Метод поиска с запретами

Метод поиска с запретами (Tabu Search) является одним из наиболее эффективных метаэв-ристических методов. Предложил его в 80-е гг. Ф. Гловер (F. Glover) [8, 9]. Отличительная черта этого метода заключается в процессе введения и снятия некоторых искусственных ограничений задачи в ходе поиска решения [6].

Основным недостатком метода ЛП является его остановка при достижении локального оптимума. Мы же ищем глобальный оптимум. Очевидно, что глобальный оптимум есть также и локальный, поэтому для успешного поиска решений мы должны как-то переходить от одного локального оптимума к другому [10].

В методе ПЗ с целью преодолеть вышеописанный недостаток вводится так называемый список запретов (Tabu List). Этот список хранит некоторое количество предыдущих решений, и при выборе нового решения запрещается выбирать из окрестности решения, содержащиеся в списке запретов [10]. Данный прием помогает избегать «застревания» в локальном оптимуме, расширяет пространство поиска, позволяя алгоритму поиска с запретами находить лучшие решения, чем метод ЛП.

Метод мультистарта

Как уже было сказано, глобальный оптимум является в то же самое время одним из локальных оптимумов. Соответственно, если просмотреть все локальные оптимумы и выбрать из них лучший, то это даст нам окончательное решение задачи. Метод МС нацелен на то, чтобы обойти как можно большее число локальных оптимумов [11]. Суть метода проста: алгоритм ЛП (вернее, его модификация) запускается несколько раз. Лучшее решение, полученное при каждом запуске поиска, сохраняется в памяти. По окончании времени поиска лучший из локальных оптиму-мов возвращается в качестве решения задачи.

Метод даст хорошие результаты при выполнении двух условий [11]:

— каждый запуск алгоритма (будем называть его старт) должен стартовать из нового начального решения;

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

Метод МС показывает результаты, сопоставимые с другими метаэвристиками, и поэтому часто используется для решения NP-трудных задач [12, 13].

Окрестность решения

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

новую БС для i-го клиента, то мы должны последовательно [проверяя на соответствие ограничениям (1)-(3)] пробовать подключить его к одному из мест-кандидатов (кроме его текущего места), начиная с самого ближнего к клиенту i. Очевидно, что место w, к которому мы хотим подключить клиента, должно иметь активную БС (Sol[w]. type Ф 0).

Алгоритм вероятностного поиска с запретами для решения задачи размещения БС

Рассмотрим рандомизированную окрестность Np (x) С N(x), где каждый элемент окрестности N(x) включается в множество Np(x) с вероятностью 0 < p < 1 (p — параметр рандомизации окрестности) независимо от других элементов [14]. С ненулевой вероятностью множество Np(x) может совпадать с N(x), может оказаться пустым или содержать ровно один элемент. Алгоритм поиска с запретами, представленный в данном разделе, осуществляет вероятностный ЛП по рандомизированной окрестности (поэтому он называется вероятностный ПЗ), совершая шаги как улучшающие, так и ухудшающие целевую функцию, что позволяет алгоритму перемещаться от одного локального оптимума к другому в целях найти среди них лучшее решение.

Использование рандомизированной окрестности Np(x) дает лучшие результаты по сравнению с просмотром полной окрестности N(x) [14-16]. Очевидно, что при p = 1 окрестность Np(x) совпадает с N(x).

Основным механизмом, позволяющим алгоритму покидать локальные оптимумы, является

список запретов TL. Список строится по предыстории поиска, т. е. по нескольким последним итерациям, и запрещает часть окрестности N(x) текущего решения [7]. В классическом методе поиска с запретами в TL добавляются те решения, которые были признаны лучшими на соответствующей итерации и к которым был применен переход как к новым текущим решениям.

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

Поэтому мы предлагаем в список запретов добавлять не решения, а операции, которые нельзя будет осуществлять в течение l следующих итераций. То есть каждое изменение, примененное к решению, порождает запрет на операцию, которая может вернуть нас в это самое решение. Ниже приведены пары «изменение» — «запрет» (далее фразой типа «s-я БС» мы для краткости обозначаем БС, расположенную на s-м месте):

Представим общую схему вероятностного поиска с запретами для задачи размещения БС.

Введем обозначения: p — параметр рандомизации окрестности; TL — список запретов; Best_neigh — лучшее решение в текущей окрестности; cost_best_neigh — целевая функция решения Best_neigh; Best — лучшее решение задачи.

Алгоритм мультистарта

для решения задачи размещения БС

Введем понятие жадного алгоритма. В жадном алгоритме делается выбор, который является самым лучшим в данный момент, т. е. производится локально оптимальный выбор в надежде, что он приведет к оптимальному решению глобальной задачи [17]. В предлагаемом нами методе мультистарта используется жадная эвристика «первое улучшение» [11]. Суть ее заключается в том, что при ЛП мы рассматриваем одно случайное соседнее решение z из окрестности текущего решения x. Если f(z) лучше, чем f(x), то текущим решением становится z. Подобный переход к первому же лучшему решению расширяет пространство поиска, что в сочетании со стартами из разных начальных решений позволит попасть в большее количество разных локальных оптимумов.

Новые потенциальные решения мы будем генерировать не из окрестностей N(x) или Np(x), а из окрестности Ngreed(x). Ngreed(x) — окрестность, получаемая при помощи операций «удаление одной БС» и «смена типа одной БС на более дешевый» к x. Таким образом, Ngreed(x), в отличие от N(x), содержит только решения с целевой функцией, лучшие, чем у x.

Ниже представлена общая схема алгоритма мультистарта для задачи размещения БС.

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

n_iter = 0, иначе n_iter = n_iter + 1.

Компьютерное моделирование

Разработанные алгоритмы реализованы как программное обеспечение в среде Embarcadero Delphi XE5. С его помощью был проведен ряд вычислительных экспериментов по нахождению оптимального расположения БС и подключения к ним клиентов. Моделирование проводилось на компьютере с процессором Intel Core Í5-3470 и оперативной памятью 6 ГБ.

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

Пусть Ntypes = 2. Эксперименты проводились на 9 тестовых задачах (по 3 значения Ntp и Nps порождают 9 комбинаций). Зафиксируем параметры алгоритма ПЗ: l = 50, p = 0,15, time = 0,1 с. Параметры алгоритма МС: N_iter_max = 50, time = 0,1 с. Результаты работы алгоритмов приведены в табл. 1. Каждая ячейка табл. 1 содержит три строки: верхняя — это время работы алгоритма ПЗ в секундах, в скобках — значение соответствующей целевой функции в условных единицах, средняя и нижняя — аналогичные

■ Таблица 1. Сравнение результатов алгоритмов поиска с запретами и мультистарта с методом полного перебора

величины для МС и ПП соответственно. Время решения задачи для методов ПЗ и МС приводится как среднее за 10 запусков алгоритма, значение целевой функции — как лучшее за 10 запусков алгоритма. Представленные в табл. 1 данные свидетельствуют о том, что на задачах малой размерности предложенные алгоритмы обеспечивают получение точных значений целевой функции, как и метод ПП, который дает точное решение при каждом запуске алгоритма. При этом алгоритмы ПЗ и МС справляются с решением задач размещения БС за очень малое время.

Далее был проведен ряд вычислительных экспериментов с целью выявить влияние параметра рандомизации окрестности p и длины списка запретов l на качество получаемых решений методом ПЗ. В качестве тестового примера была выбрана задача следующей размерности: Ntp = 100, Nps = 100, Ntypes = 3. Результаты эксперимента представлены на рисунке. По оси абсцисс отложены значения p в диапазоне [5 %; 100 %] с дискретностью 5 %. По оси ординат отложены значения оценки относительной погрешности решений, которая считается как среднее отклонение полученных решений от лучшего из известных решений задачи. Для каждой пары p и l приведены усредненные результаты за 50 запусков, time = 20 с.

Как видно из графиков, на данных примерах алгоритм ПЗ достигает наибольшей эффективности при p Е [0,1; 0,35], что в целом согласуется с результатами работы [14]. Также выявлено, что при значениях длины списка запретов, равных 50-100, алгоритм поиска с запретами показывает наилучшие результаты. Наилучшее значение оценки относительной погрешности получено при l = 50 и p = 0,15 (2,709 %).

Также был проведен ряд вычислительных экспериментов с целью сравнить эффективность методов ЛП, ПЗ и МС при решении задач разной

>к о и

Й Ё1 а Ь S 0 м в

■ Влияние рандомизации окрестности и длины списка запретов на относительную погрешность решений

■ Таблица 2. Сравнение результатов локального поиска, алгоритма поиска с запретами и метода мультистарта

Размерность задачи Метод

(Ntp x Nps x Ntypes) ЛП ПЗ МС

размерности. Зафиксируем параметры алгоритма ПЗ: I = 50, р = 0,15. Параметры алгоритма МС: М_Нег_тах = 50. Моделирование производилось следующим образом: сначала каждую из задач мы решали методом ЛП (усредняя результаты за 50 запусков). Далее мы решали ту же задачу методами ПЗ и МС (те же 50 запусков для каждого метода), ограничивая их работу временем, которое понадобилось методу ЛП для решения задачи. Результаты эксперимента приведены в табл. 2. Каждая ячейка таблицы содержит две строки: верхняя — это время работы алгоритма, нижняя — значение оценки относительной погрешности решений, получаемых данным алгоритмом. Из таблицы видно, что методы ПЗ и МС решают задачу размещения БС лучше, чем алгоритм ЛП. При этом алгоритм МС показывает лучшие результаты, чем вероятностный ПЗ.

Заключение

Проведенное компьютерное моделирование позволяет сделать следующие выводы.

Литература

Efficient Solution of the 3G Network Planning Problem // Computers Industrial Engineering. 2012. N 4. P. 819-830.

A Multi-Start Local Search Heuristic for Ship Scheduling — a Computational Study // Computers Operations Research. 2007. N 3. P. 900-917.

UDC 621.395.7, 519.854 doi:10.15217/issn1684-8853.2015.3.99

Multi-Start and Tabu Search Algorithms for Base Station Location Problem

Skakov E. S.a, Post-Graduate Student, wallkirya@mail.ru Malysh V. N.a, Dr. Sc., Tech., Professor, vmalysh@mail.ru

aLipetsk State Pedagogical University, 42, Lenina St., 398020, Lipetsk, Russian Federation

Purpose: The synthesis of a topological structure for a wireless data network implies planning territorial distribution of the base transceiver stations on potential sites, and connecting to the clients. The existing approaches to this problem have shortcomings: using solution methods with low computing speed (branch and bound method, heuristic method of Lagrange, etc.); lack of restrictions which would take into account the level of signal fading during its propagation from the base station to the client and back and also the level of inter-cell interference; using only one type of base stations. The goal of this research is creating a model for base station location which would be free from the above-mentioned drawbacks. Results: The problem of base station location has been formulated, taking into account the signal-to-interference ratio for the network clients. A problem solution is represented as a vector of structures, each storing the information about one potential site (the installed base station type, the list of connected clients). Modified algorithms of probabilistic tabu search and multi-start have been developed, based on the concept of current solution neighborhood. A new solution from the neighborhood of the current solution can be obtained using one of the following six operations: changing the type of a station to a more cheap/expensive one, reconnecting a client, removing a base station, addind a station, moving a base station. In order to avoid getting stuck in local optima during the tabu search, the algorithm is disabled to browse solutions from the tabu list. The novelty of the approach is that the tabu list is filled not with real decisions made in the past, but with operations to change the network configuration which can bring us back to old local optima. The essence of the modified multi-start algorithm is as follows: only two operations are used to obtain a new solutions (removing a base station and changing the type of a station to a cheaper one); only a part of the neighborhood is browsed; the transition to a new solution is performed on the "first improvement" principle; the algorithm of finding the best solutions runs several times. The developed algorithms are implemented in Delphi programming environment. It has been shown that the new algorithms show better results than the local search method. Practical relevance: The developed modifications of tabu search and multi-start methods help to find the solution for the base station location problem in a reasonable time, many orders of magnitude faster than the exact method of exhaustive search. It has been found that the quality of the problem solution obtained by probabilistic tabu search depends on the length of the tabu list and on the value of the neighborhood randomization parameter.

References

К статье А. В. Назарова, В. Л. Якимова, В. А. Авдеева «Алгоритм максимизации энтропии обучающей выборки и его использование при синтезе моделей прогноза дискретных состояний нелинейных динамических систем» (ИУС, 2015, № 2, с. 57-66).

На с. 58 формула (2) напечатана в следующем Следует читать

виде: h h

_ _ 1 h _ _ 1 hs

G =-РОШ =-— £ Рош h, (2) G = 1-Porn = I" — £ Рош h, (2)

h3 h=1 h h=1

Редакция приносит извинения за допущенную ошибку.