Comparative analysis of calculation methods for overlapping area in antenna placement problem using brute force algorithm

Aye Min Thike, Sergey Lupin

Abstract


This paper presents a method to reduce the computational complexity of calculation the criterion function in a brute force algorithm to solve the antenna placement problem in a grid model. Calculating overlap zones between antennas is one of the criteria for optimizing wireless network topology. We present a comparative analysis of two methods for the calculating of this criterion. The impact of software implementation of these methods on computational complexity is discussed and theoretical estimates are confirmed by experimental results. The modified method involves performing an initial calculation of overlaps between antennas in all possible positions and storing this data in a multidimensional array, which allows for quick access during the main algorithm process. Our research focuses on a modified method that can reduce the computational burden of repetitive computations during the search for an optimal solution. The experimental results confirm that the presented modified method effectively reduces computing times in calculating the criteria function. This allows us to expand the possibilities of using the enumeration algorithm to solve large-scale optimization problems.

Full Text:

PDF

References


Sergi Gogokhia, Nikoloz Abzianidze, “Use of Geolocation in ACP Systems,” American Scientific Research Journal for Engineering, Technology, and Sciences (ASRJETS), vol. 66, no. 1, pp.14–25, 2020.

Aye Min Thike, Sergey A. Lupin, “Accelerate assessment calculations for quadratic assignment problem solution,” 2024 Conference of Young Researchers in Electrical and Electronic Engineering (ElCon), Saint Petersburg, Russian Federation, 2024, pp. 118–122, doi: 10.1109/ElCon61730.2024.10468348.

Zhaoyi Xu, Yanjie Guo, Joseph Homer Saleh, “Multi-objective optimization for sensor placement: an integrated combinatorial approach with reduced order model and Gaussian Process,” Measurement, vol. 187, 2022, 110370, ISSN 0263-2241, doi: https://doi.org/10.1016/j.measurement.2021.110370.

Yuta Nakano, Shigeyasu Uno, “Quadratic formulation of mutual information for sensor placement optimization using ising and quantum annealing machines,” Quantum Physics, pp. 1–7, July 2024, doi: https://doi.org/10.48550/arXiv.2407.14747.

Md. Harun Ar Rashid, “Algorithms and Techniques of polygon intersection,” online available: https://limbd.org/algorithms-and-techniques-of-polygon-intersection/, Aug 26, 2023.

Hesamoddin Tahami, Hengameh Fakhravar, “A literature review on combining heuristics and exact algorithms in combinatorial optimization,” European Journal of Information Technologies and Computer Science, vol. 2, no. 2, pp. 6–12, April 2022.

Federico Librino, Marco Levorato, Michele Zorzi, “An Algorithmic Solution for Computing Circle Intersection Areas and its Applications to Wireless Communications,” 7th International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks, Seoul, Korea (South), 2009, pp. 1-10, doi: 10.1109/WIOPT.2009.5291627.

Elias Mendez-Dominguez, Joaquim Fortuny-Guasch, “Optimization techniques for MIMO radar antenna systems,” EUR 23671 EN. Luxembourg: OPOCE; 2008. JRC49366, ISSN: 1018-5593.

Aye Min Thike, Lupin S.A., Fedyashin D.A., “Using MPI library for parallel implementation of a brute-force algorithm,” Software & Systems, 36(4), pp. 607–614 (in Russ.). doi: 10.15827/0236-235X.142.607-614.

Aldemir M. de Oliveira, Nelson Maculan, “Combinational optimization, combined algorithms and problem positioning radio stations based wireless and mobile,” Proceeding Series of the Brazilian Society of Applied and Computational Mathematics, vol. 3, no. 1, pp. 1–7, 2015, doi: https://doi.org/10.5540/03.2015.003.01.0424.

Francisco Calles-Esteban, Alvaro Antonio Olmedo, Carlos J. Hellín, Adrián Valledor, Josefa Gómez, Abdelhamid Tayebi, “Optimizing antenna positioning for enhanced wireless coverage: A genetic algorithm approach,” Sensors 2024, no. 7: 2165. doi: https://doi.org/10.3390/s24072165.

Hammad Hafiz, Harjeet Aulakh, Kaamran Raahemifar, “Antenna placement optimization for cellular network,” 2013 26th IEEE Canadian Conference on Electrical and Computer Engineering (CCECE), Regina, SK, Canada, 2013, pp. 1–6, doi: 10.1109/CCECE.2013.6567765.

Abhinav Jauhri, Jason D. Lohn, Derek S. Linden “A comparison of antenna placement algorithms,” GECCO Comp '14: Proceedings of the Companion Publication of the 2014 Annual Conference on Genetic and Evolutionary Computation, pp. 1223–1230, 2014. doi: https://doi.org/10.1145/2598394.260544

Robert M. Curry, J. Cole Smith, “A survey of optimization algorithms for wireless sensor network lifetime maximization,” Computers & Industrial Engineering (2016), doi: http://dx.doi.org/10.1016/j.cie. 2016.08.028.

Muhammad Tahseen Iqbal, Khurram Saleem Alimgeer, “Calculation of overlapping area for cellular systems,” International Journal of Technology and Research, vol. 1, no. 2, pp. 40–44, 2013.

Zhiyuan LIN, Yan LI, “An efficient algorithm for intersection, union and difference between two polygons,” 2009 International Conference on Computational Intelligence and Software Engineering, Wuhan, China, 2009, pp. 1–4, doi: 10.1109/CISE.2009.5364458.

Dr. Ismail Al-Rawi, “Implementation of an efficient scan-line polygon fill algorithm,” Computer Engineering and Intelligent Systems, vol. 5, no. 4, pp. 22–28, 2014, ISSN 2222-1719.

Douglas Werner, Micah Gregory, Zhi Hao Jiang, Donovan E. Brocker, “Optimization methods in antenna engineering,” In: Chen, Z. (eds) Handbook of Antenna Technologies. Springer, Singapore, pp. 1–47, 2015, doi: https://doi.org/10.1007/978-981-4560-75-7_15-1.

Y. Liu, Y. Jian, R. Sivakumar, D. M. Blough, "Maximizing line-of-sight coverage for mmwave wireless LANs with multiple access points," IEEE/ACM Transactions on Networking, vol. 30, no. 2, pp. 698–716, April 2022, doi: 10.1109/TNET.2021.3122378.


Refbacks

  • There are currently no refbacks.


Abava  Кибербезопасность Monetec 2026 СНЭ

ISSN: 2307-8162