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

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

• В. Н. Малыш
• Е. С. Скаков

• Технические науки. Промышленность
• Физико-математические науки