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


https://doi.org/10.15217/issn1684-8853.2015.3.99

Полный текст:


Аннотация

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

Об авторах

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


Владимир Николаевич Малыш
Липецкий государственный педагогический университет
Россия


Список литературы

1. Вишневский В. М. Теоретические основы проектирования компьютерных сетей. - М.: Техносфера, 2003. - 512 с.

2. Ермолаев С. Ю. Оптимальное размещение базовых станций // Telecommunication Sciences. 2010. № 1. С. 349-355.

3. St-Hilaire M., Chinnek J. W., Chamberland S., Pierre S. Efficient Solution of the 3G Network Planning Problem // Computers & Industrial Engineering. 2012. N 4. P. 819-830.

4. Архангельский А. Я. Программирование в Delphi 7. - М.: Бином-Пресс, 2003. - 1152 с.

5. Koskie S., Gajic Z. A Nash Game Algorithm for SIR-based Power Control in 3G Wireless CDMA Networks // IEEE/ACM Transactions on Networking. 2005. N 5. P. 1017-1026.

6. Усманова А. Р. Метод поиска с запретами для задач упаковки в контейнеры: дис.. канд. физ.-мат. наук. - Уфа, 2002. - 101 с.

7. Скаков Е. С. Метод поиска с запретами для решения оптимизационных задач // Новое слово в науке и практике: гипотезы и апробация результатов исследований: тр. 15-й Междунар. конф., Новосибирск, 23 января 2015 г. Новосибирск, 2015. С. 166171.

8. Glover F. Tabu Search. Part I // ORSA Journal on Computing. 1989. N 3. P. 190-206.

9. Glover F. Tabu Search. Part II // ORSA Journal on Computing. 1990. N 1. P. 4-32.

10. Luke S. Essentials of Metaheuristics. - Lulu, 2013. - 242 p.

11. Gendreau M., Potvin J. Y. Handbook of Metaheuristics. - Springer, 2010. - 669 p.

12. Brenmo G., Christiansen M., Fagerholt K., Nygreen B. A Multi-Start Local Search Heuristic for Ship Scheduling - a Computational Study // Computers & Operations Research. 2007. N 3. P. 900-917.

13. Marti R., Resende M. G. C., Ribeiro C. C. Multi-Start Methods for Combinatorial Optimization // European Journal of Operational Research. 2013. N 1. P. 1-8.

14. Руднев А. С. Вероятностный поиск с запретами для задачи упаковки кругов и прямоугольников в полосу // Дискретный анализ и исследование операций. 2009. № 4. С. 61-86.

15. Гончаров Е. Н., Кочетов Ю. А. Вероятностный поиск с запретами для дискретных задач безусловной оптимизации // Дискретный анализ и исследование операций.2002. № 2. С. 13-30.

16. Кочетов Ю. А. Методы локального поиска для дискретных задач размещения: дис.. д-ра физ.-мат. наук. - Новосибирск, 2009. - 267 с.

17. Гончаров Е. Н., Кочетов Ю. А. Поведение вероятностных жадных алгоритмов для многостадийной задачи размещения // Дискретный анализ и исследование операций.1999. № 1. С.12-32.


Дополнительные файлы

Для цитирования: Скаков Е.С., Малыш В.Н. Использование алгоритмов мультистарта и поиска с запретами для решения задачи размещения базовых станций. Информационно-управляющие системы. 2015;(3):99-106. https://doi.org/10.15217/issn1684-8853.2015.3.99

For citation: Skakov E.S., Malysh V.N. Multi-Start and Tabu Search Algorithms in Base Station Location Problem. Information and Control Systems. 2015;(3):99-106. (In Russ.) https://doi.org/10.15217/issn1684-8853.2015.3.99

Просмотров: 43


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 1684-8853 (Print)
ISSN 2541-8610 (Online)