Reducing computational complexity of brute force algorithm in solving optimal placement of directional antenna

Aye Min Thike, Sergey Lupin

Abstract


Determining the optimal placement of directional antennas in wireless networks is a challenging problem, which includes maximum coverage with minimal overlap. This study explores some reduction methods to improve the efficiency of the brute force algorithm for determining this problem. We propose and evaluate three reduction methods: restriction of antenna rotation angles, limitation of potential positions of directional antennas, and early termination of unsatisfactory calculations. In our computational experiments, we apply these methods separately, in combination, and alongside a parallel computing approach with a brute force algorithm for calculating maximum coverage with minimal overlap. The parallel computing approach improves the brute force algorithm’s performance using multi-core processing, while the combined reduction methods significantly improve efficiency by minimizing redundant and inefficient computations. Experimental results confirm that these methods successfully mitigate the limitations of the brute force algorithm, effectively reducing the computation time compared to the conventional brute force algorithm and improving scalability for solving optimal directional antenna placement problems.

Full Text:

PDF

References


Hong-Ning Dai, Kam-Wing Ng, Minglu Li and Min-You Wu, “An overview of using directional antennas in wireless networks”, International journal of communication systems, 2013, Vol. 26, pp. 419-448, doi: 10.1002/dac.13481.

Songwei Li, Chenyuan He, Mushuang Liu, Yan Wan, Yixin Gu, Junfei Xie, Shengli Fu, Kejie Lu, “The Design and Implementation of Aerial Communication Using Directional Antennas: Learning Control in Unknown Communication Environments”, IET Control Theory & Applications, 2019, Vol. 13 Iss. 17, pp. 2906-2916, doi: https://doi.org/10.1049/iet-cta.2018.6252.

A. M. Thike, S. Lupin, H. Tun, O. Kostrova and R. Chakirov, “Topology optimisation of wireless internet infrastructure”, 2016 IEEE NW Russia Young Researchers in Electrical and Electronic Engineering Conference (EIConRusNW), St. Petersburg, Russia, 2016, pp. 362-364, doi: 10.1109/EIConRusNW.2016.7448194.

Wang, Q., Dai, H.-N., Zheng, Z., Imran, M., Vasilakos, A.V., “On Connectivity of Wireless Sensor Networks with Directional Antennas”, Sensors 2017, 17, 134. doi: https://doi.org/10.3390/s17010134.

M. Rizkinia, T. Baba, K. Shirai and M. Okuda, “Local Spectral Component Decomposition for Multi-Channel Image Denoising”, in IEEE Transactions on Image Processing, vol. 25, no. 7, pp. 3208-3218, July 2016, doi: 10.1109/TIP.2016.2561320.

Xiaopeng Yang, Yuqing Li, Feifeng Liu, Tian Lan, Long Teng, Tapan K. Sarkar, “Antenna position optimization method based on adaptive genetic algorithm with self‐supervised differential operator for distributed coherent aperture radar”, IET Radar, Sonar & Navigation, 2021, Vol. 15, doi: https://doi.org/10.1049/rsn2.12055.

M. Bekar, C. J. Baker and M. Gashinova, “Sparse 2D MIMO Antenna Designs using Simulated Annealing”, 2023 20th European Radar Conference (EuRAD), Berlin, Germany, 2023, pp. 371-374, doi: 10.23919/EuRAD58043.2023.10289537.

X. Zheng, “Application of Swarm Intelligence Optimization Algorithm in Antenna Design”, 2021 International Conference on Intelligent Transportation, Big Data & Smart City (ICITBS), Xi'an, China, 2021, pp. 773-779, doi: 10.1109/ICITBS53129.2021.00193.

A. M. Thike, S. Lupin, B. H. Than and R. Chakirov, “The computational aspects of estimating the efficiency of wireless networks' topology”, 2017 IEEE Conference of Russian Young Researchers in Electrical and Electronic Engineering (EIConRus), St. Petersburg and Moscow, Russia, 2017, pp. 582-586, doi: 10.1109/EIConRus.2017.7910621.

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

Aye Min Thike, Sergey Lupin, “Parallel Application for Wireless Network Topology Optimisation”, International Journal of Electrical, Electronics and Data Communication, vol.7, Iss.4, pp. 14-20, April 2019, ISSN(p): 2320-2084, ISSN(e): 2321-2950.

A. M. Thike, S. Lupin, B. H. Than, H. H. Linn and K. N. Z. Lin, “Wireless network topology optimization — Decisions for directional antennas”, 2018 IEEE Conference of Russian Young Researchers in Electrical and Electronic Engineering (EIConRus), Moscow and St. Petersburg, Russia, 2018, pp. 1467-1471, doi: 10.1109/EIConRus.2018.8317374.

Ай Мин Тайк, Лупин С.А., Телегин П.Н., Шабанов Б.М, “Ускорение расчета критериальной функции в задаче размещения всенаправленных антенн”, Программные продукты и системы. 2024. Т. 37. № 3. С. 197–206. doi: 10.15827/0236-235X.142.

Hesham Adnan Alabbasi, Alaa Hussain Altimimy, “An Approach to Calculate Exact Coverage Area for Connected Wireless Sensor Network”, Journal of University of Babylon for Engineering Sciences, 2018, Vol. 26, No. 7, pp. 182-194.

Feng Pan and S. Kasiviswanathan, “Efficient placement of directional antennas in infrastructure-based wireless networks”, 2011 - MILCOM 2011 Military Communications Conference, Baltimore, MD, 2011, pp. 1796-1801, doi: 10.1109/MILCOM.2011.6127572.

A. M. Thike, S. Lupin and Y. Vagapov, “Implementation of brute force algorithm for topology optimisation of wireless networks”, 2016 International Conference for Students on Applied Engineering (ICSAE), Newcastle Upon Tyne, UK, 2016, pp. 264-268, doi: 10.1109/ICSAE.2016.7810200.

G. Hadynski, S. B. Lee, G. Rajappan, R. Sundaram, X. Wang and F. Zhou, “Optimization of directional antenna network topology in Airborne Networks”, 2010 - MILCOM 2010 MILITARY COMMUNICATIONS CONFERENCE, San Jose, CA, USA, 2010, pp. 68-73, doi: 10.1109/MILCOM.2010.5680269.

Ouamri Mohamed Amine, Abdelkrim Khireddine, “Base station placement optimisation using genetic algorithms approach”, International Journal of Computer Aided Engineering and Technology, 2019, Vol. 11, Iss. 6, pp 635-652, doi: https://doi.org/10.1504/IJCAET.2019.102495.

B. Joukar, M. Mohammadi and M. J. Ostovari, “Combination of Smart Antenna and Ant Colony Optimization in Multi-Purpose Wireless Sensor Networks”, 2019 27th Iranian Conference on Electrical Engineering (ICEE), Yazd, Iran, 2019, pp. 1315-1320, doi: 10.1109/IranianCEE.2019.8786612.

Aye Min Thike, Sergey Lupin, “Comparative Analysis of Calculation Methods for Over lapping Area in Antenna Placement Problem using Brute Force Algorithm”, 2025 Confer ence of Young Researchers in Electrical and Electronic Engineering (EICon2025), January 28 - 30, 2025, St. Petersburg, Russia.

Segura, C., González, Y., Miranda, G., León, C, “Parallel Hyperheuristics for the Antenna Positioning Problem”, Distributed Computing and Artificial Intelligence - 7th International Symposium, DCAI 2010, Vol. 79, pp. 471-479, doi:https://doi.org/10.1007/978-3-642-14883-5_61.


Refbacks

  • There are currently no refbacks.


Abava  Кибербезопасность ИБП для ЦОД СНЭ

ISSN: 2307-8162