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

Аннотация

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