Метод декомпозиции для задачи размещения антенн на стадионе

Метод декомпозиции для задачи размещения антенн на стадионе

Юськов А. Д.
Дискретный анализ и исследование операций, 32, 1, 145-163 (2025)
Скачать статью

УДК 519.8 
DOI: 10.33048/daio.2025.32.809

Аннотация:

Рассматривается задача размещения антенн на стадионе. Стадион разделён на секторы, и на каждый сектор назначается некоторое число антенн связи. Пользователи должны получать сигнал определённого качества от антенн, назначенных на их сектор. Задача состоит в том, чтобы выбрать места размещения антенн, их типы, углы направления и назначения на сектора так, чтобы максимизировать три критерия качества решения: среднее отношение сигнал/помехи (signal to interference ratio, SIR), количество клиентов с хорошим качеством сигнала и согласованность назначения. Вычисление качества сигнала производится при помощи имитационной модели. В работе представлена трехэтапная эвристическая схема для решения задачи. Она использует конструктивную эвристику, процедуру локального улучшения и эвристику на основе декомпозиции задачи по секторам с использованием модели целочисленного линейного программирования. Проведены численные эксперименты на тестовых примерах с 94 антеннами 7 типов, 19 секторами и 4426 пользователями. На данных примерах удалось за 2 ч улучшить предоставленные базовые решения и получить решения, сравнимые с запуском метаэвристического пакета на 24 ч.

Табл. 2, ил. 3, библиогр. 17.

Литература:
  1. Kaya A. Ö., Calin D., Viswanathan H. On the performance of stadium high density carrier Wi-Fi enabled LTE small cell deployments // Proc. 2015 IEEE Wireless Communications and Networking Conf. (New Orleans, USA, Mar. 9–12, 2015). Piscataway: IEEE, 2015. P. 855–860. DOI: 10.1109/WCNC. 2015.7127581.
     
  2. Dapeng H., Ping C., Xiaoping T., Xingjian W. Design and optimization of high density wireless network in gymnasium of Beijing Normal University // Proc. 2020 IEEE 3rd Int. Conf. Information Systems and Computer Aided Education (Dalian, China, Sept. 27–29, 2020). Piscataway: IEEE, 2020. P. 28–32. DOI: 10.1109/ICISCAE51034.2020.9236883.
     
  3. Hata M. Empirical formula for propagation loss in land mobile radio services // IEEE Trans. Veh. Technol. 1980. V. 29, No. 3. P. 317–325. DOI: 10.1109/T-VT.1980.23859.
     
  4. Katev P. D. Propagation models for WiMAX at 3.5 GHz // Proc. 9th Int. Conf. 2012 ELEKTRO (Žilina — Rajecké Teplice, Slovakia, May 21–22, 2012). Piscataway: IEEE, 2012. P. 61–65. DOI: 10.1109/ELEKTRO.2012.6225572.
     
  5. Naderi Soorki M., Saad W., Bennis M. Optimized deployment of millimeter wave networks for in-venue regions with stochastic users’ orientation // IEEE Trans. Wirel. Commun. 2019. V. 18, No. 11. P. 5037–5049. DOI: 10.1109/TWC.2019.2931535.
     
  6. Šlapak E., Gazda J., Bugár G., Maksymyuk T. Review of cellular radio network cell placement design, from traditional to artificial intelligence based approaches // Proc. 61st Int. Symp. ELMAR-2019 (Zadar, Croatia, Sept. 23–25, 2019). Zadar: Croat. Soc. Electron. Marine, 2019. P. 93–96. DOI: 10.1109/ELMAR.2019.8918668.
     
  7. Vanhatupa T., Hannikainen M., Hamalainen T. D. Genetic algorithm to optimize node placement and configuration for WLAN planning // Proc. 4th Int. Symp. Wireless Communication Systems 2007 (Trondheim, Norway, Oct. 17–19, 2007). Piscataway: IEEE, 2007. P. 612–616. DOI: 10.1109/ISWCS. 2007.4392413.
     
  8. Narayanan L., Subramanian B., Arokiaswami A., Iruthayarajan M. W. Optimal placement of mobile antenna in an urban area using evolutionary multiobjective optimization // Microw. Opt. Technol. Lett. 2012. V. 54, No. 3. P. 737–743. DOI: 10.1002/mop.26627.
     
  9. Raisanen L., Whitaker R. M. Comparison and evaluation of multiple objective genetic algorithms for the antenna placement problem // Mobile Netw. Appl. 2005. V. 10, No. 1. P. 79–88. DOI: 10.1023/B:MONE.0000048547.84327. 95.
     
  10. Goldsmith A. Wireless communications. Cambridge: Camb. Univ. Press, 2005. 644 p.
     
  11. Audet C., Hare W. Derivative-free and blackbox optimization. Cham: Springer, 2017. 308 p. DOI: 10.1007/978-3-319-68913-5.
     
  12. Black box optimization, machine learning, and no-free lunch theorems. Cham: Springer, 2021. 388 p. DOI: 10.1007/978-3-030-66515-9.
     
  13. Yuskov A. D., Kulachenko I. N., Melnikov A. A., Kochetov Yu. A. Decomposition approach to simulation-based optimization of inventory management // Mathematical optimization theory and operations research: Recent trends. Rev. Sel. Pap. 22nd Int. Conf. MOTOR 2023 (Yekaterinburg, Russia, July 2–8, 2023). Cham: Springer, 2023. P. 259–273. (Commun. Comput. Inf. Sci.; V. 1881). DOI: 10.1007/978-3-031-43257-6_20.
     
  14. Yuskov A. D., Kulachenko I. N., Melnikov A. A., Kochetov Yu. A. Two-stage algorithm for bi-objective black-box traffic engineering // Optimization and applications. Rev. Sel. Pap. 14th Int. Conf. OPTIMA 2023 (Petrovac, Montenegro, Sept. 18–22, 2023). Cham: Springer, 2023. P. 110–125. (Lect. Notes Comput. Sci.; V. 14395). DOI: 10.1007/978-3-031-47859-8_9.
     
  15. Yuskov A. D., Kulachenko I. N., Melnikov A. A., Kochetov Yu. A. Stadium antennas deployment optimization // Mathematical optimization theory and operations research. Proc. 23rd Int. Conf. MOTOR 2024 (Omsk, Russia, June 30 – July 6, 2024). Cham: Springer, 2024. P. 449–461. (Lect. Notes Comput. Sci.; V. 14766). DOI: 10.1007/978-3-031-62792-7_30.
     
  16. Deb K., Agrawal S., Pratap A., Meyarivan T. A fast elitist non-dominated sorting genetic algorithm for multi-objective optimization: NSGA-II // Parallel problem solving from nature — PPSN VI. Proc. 6th Int. Conf. (Paris, France, Sept. 18–20, 2000). Heidelberg: Springer, 2000. P. 849–858. (Lect. Notes Comput. Sci.; V. 1917). DOI: 10.1007/3-540-45356-3_83.
     
  17. Hadka D., Reed P. Borg: An auto-adaptive many-objective evolutionary computing framework // Evol. Comput. 2013. V. 21, No. 2. P. 231–259. DOI: 10.1162/EVCO_a_00075.

Исследование выполнено за счёт бюджета за счет бюджета Новосибирского гос. университета. Дополнительных грантов на проведение или руководство этим исследованием получено не было.

Юськов Александр Дмитриевич
  1. Новосибирский гос. университет, 
    ул. Пирогова, 2, 630090 Новосибирск, Россия

E-mail: a.yuskov@g.nsu.ru

Статья поступила 19 июля 2024 г.
После доработки — 17 августа 2024 г.
Принята к публикации 22 сентября 2024 г.

Abstract:

We consider a stadium antenna deployment problem. The stadium is divided into sectors. Several antennas are assigned to each sector. Users should receive a signal of a certain quality from antennas assigned to their sector. The problem is to choose locations of antennas, their types, angles, and assignments to sectors to maximize three quality criteria: the mean signal to interference ratio (SIR), the number of clients with good signal quality, and the assignment consistency. We use a simulation to compute the signal quality. We present a three-stage heuristic approach to the problem. It uses a constructive heuristic, a local improvement procedure, and a decomposition-based MIP heuristic. We carry out numerical experiments on test instances with 94 antennas of 7 types, 19 sectors, and 4426 clients. It is possible to improve the provided baseline solutions in 2 h and obtain solutions comparable to running a metaheuristic package for 24 h. 

Tab. 2, illustr. 3, bibliogr. 17.

References:
  1. A. Ö. Kaya, D. Calin, and H. Viswanathan, On the performance of stadium high density carrier Wi-Fi enabled LTE small cell deployments, in Proc. 2015 IEEE Wireless Communications and Networking Conf., New Orleans, USA, Mar. 9–12, 2015 (IEEE, Piscataway, 2015), pp. 855–860, DOI: 10.1109/ WCNC.2015.7127581.
     
  2. H. Dapeng, C. Ping, T. Xiaoping, and W. Xingjian, Design and optimization of high density wireless network in gymnasium of Beijing Normal University, in Proc. 2020 IEEE 3rd Int. Conf. Information Systems and Computer Aided Education, Dalian, China, Sept. 27–29, 2020 (IEEE, Piscataway, 2020), pp. 28–32, DOI: 10.1109/ICISCAE51034.2020.9236883.
     
  3. M. Hata, Empirical formula for propagation loss in land mobile radio services, IEEE Trans. Veh. Technol. 29 (3), 317–325 (1980), DOI: 10.1109/T-VT.1980. 23859.
     
  4. P. D. Katev, Propagation models for WiMAX at 3.5 GHz, in Proc. 9th Int. Conf. 2012 ELEKTRO, Žilina — Rajecké Teplice, Slovakia, May 21–22, 2012 (IEEE, Piscataway, 2012), pp. 61–65, DOI: 10.1109/ELEKTRO.2012.6225572.
     
  5. Naderi M. Soorki, W. Saad, and M. Bennis, Optimized deployment of millimeter wave networks for in-venue regions with stochastic users’ orientation, IEEE Trans. Wirel. Commun. 18 (11), 5037–5049 (2019), DOI: 10.1109/TWC. 2019.2931535.
     
  6. E. Šlapak, J. Gazda, G. Bugár and T. Maksymyuk, Review of cellular radio network cell placement design, from traditional to artificial intelligence based approaches, in Proc. 61st Int. Symp. ELMAR-2019, Zadar, Croatia, Sept. 23–25, 2019 (Croat. Soc. Electron. Marine, Zadar, 2019), pp. 93–96, DOI: 10.1109/ELMAR.2019.8918668.
     
  7. T. Vanhatupa, M. Hannikainen, and T. D. Hamalainen, Genetic algorithm to optimize node placement and configuration for WLAN planning, in Proc. 4th Int. Symp. Wireless Communication Systems 2007, Trondheim, Norway, Oct. 17–19, 2007 (IEEE, Piscataway, 2007), pp. 612–616, DOI: 10.1109/ISWCS.2007.4392413.
     
  8. L. Narayanan, B. Subramanian, A. Arokiaswami, and M. W. Iruthayarajan, Optimal placement of mobile antenna in an urban area using evolutionary multiobjective optimization, Microw. Opt. Technol. Lett. 54 (3), 737–743 (2012), DOI: 10.1002/mop.26627.
     
  9. L. Raisanen and R. M. Whitaker, Comparison and evaluation of multiple objective genetic algorithms for the antenna placement problem, Mobile Netw. Appl. 10 (1), 79–88 (2005), DOI: 10.1023/B:MONE.0000048547.84327.95.
     
  10. A. Goldsmith, Wireless Communications (Camb. Univ. Press, Cambridge, 2005).
     
  11. C. Audet and W. Hare, Derivative-Free and Blackbox Optimization (Springer, Cham, 2017), DOI: 10.1007/978-3-319-68913-5.
     
  12. Black Box Optimization, Machine Learning, and No-Free Lunch Theorems (Springer, Cham, 2021), DOI: 10.1007/978-3-030-66515-9.
     
  13. A. D. Yuskov, I. N. Kulachenko, A. A. Melnikov, and Yu. A. Kochetov, Decomposition approach to simulation-based optimization of inventory management, in Mathematical Optimization Theory and Operations Research: Recent Trends (Rev. Sel. Pap. 22nd Int. Conf. MOTOR 2023, Yekaterinburg, Russia, July 2–8, 2023) (Springer, Cham, 2023), pp. 259–273 (Commun. Comput. Inf. Sci., Vol. 1881), DOI: 10.1007/978-3-031-43257-6_20.
     
  14. A. D. Yuskov, I. N. Kulachenko, A. A. Melnikov, and Yu. A. Kochetov, Two-stage algorithm for bi-objective black-box traffic engineering, in Optimization and Applications (Rev. Sel. Pap. 14th Int. Conf. OPTIMA 2023, Petrovac, Montenegro, Sept. 18–22, 2023) (Springer, Cham, 2023), pp. 110–125 (Lect. Notes Comput. Sci., Vol. 14395), DOI: 10.1007/978-3-031-47859-8_9.
     
  15. A. D. Yuskov, I. N. Kulachenko, A. A. Melnikov, and Yu. A. Kochetov, Stadium antennas deployment optimization, in Mathematical optimization theory and operations research (Proc. 23rd Int. Conf. MOTOR 2024, Omsk, Russia, June 30 – July 6, 2024) (Springer, Cham, 2024), pp. 449–461 (Lect. Notes Comput. Sci., Vol. 14766), DOI: 10.1007/978-3-031-62792-7_30.
     
  16. K. Deb, S. Agrawal, A. Pratap, and T. Meyarivan, A fast elitist nondominated sorting genetic algorithm for multi-objective optimization: NSGAII, in Parallel Problem Solving from Nature— PPSN VI (Proc. 6th Int. Conf., Paris, France, Sept. 18–20, 2000) (Springer, Heidelberg, 2000), pp. 849–858 (Lect. Notes Comput. Sci., Vol. 1917), DOI: 10.1007/3-540-45356-3_83.
     
  17. D. Hadka and P. Reed, Borg: An auto-adaptive many-objective evolutionary computing framework, Evol. Comput. 21 (2), 231–259 (2013), DOI: 10.1162/ EVCO_a_00075.