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