Base Station Placement across a Simulated City using a Biased Random-key Genetic Algorithm
Abstract
As mobile communication technologies evolve, smart base station positioning has been getting increasingly important. The base station placement problem deals with the problem of efficiently positioning cell sites, in order to achieve balance between coverage and service cost. This paper proposes an implementation using the BRKGA meta-heuristic, which focus on achieving a weighted coverage/cost balance. Several tests have been conducted to prove the effectiveness of the proposed solution, and BRKGA showed values 1.4% apart from optimal coverage, on average. These results are better in both execution time and area coverage, when compared to methods introduced in literature.
Keywords:
genetic algorithm, brkga, biased random-key genetic Algorithm, mobile networks, location optimization , base station placement
References
Ahmed, I. E., Qazi, B. R., and Elmirghani, J. M. H. (2012). Base stations locations optimisation in an airport environment using genetic algorithms. In 2012 8th International Wireless Communications and Mobile Computing Conference (IWCMC), pages 24–29.
Bean, J. C. (1994). Genetic algorithms and random keys for sequencing and optimization. ORSA Journal on Computing, 6(2):154–160.
Boccardi, F., Heath, R. W., Lozano, A., Marzetta, T. L., and Popovski, P. (2014). Five disruptive technology directions for 5g. IEEE Communications Magazine, 52(2):74– 80.
Cardeiro, J. and Correia, L. M. (2006). Optimisation of base station location in umtsfdd for realistic traffic distributions. In 2006 IEEE 17th International Symposium on Personal, Indoor and Mobile Radio Communications, pages 1–5.
Chen, Q. B., Wang, Y., Liu, Z. J., and Liang, C. C. (2012). A new intelligent approach based on genetic algorithm for finding optimal base stations configuration in the dynamic scenario used in son. In Frontiers of Manufacturing and Design Science II, volume 121 of Applied Mechanics and Materials, pages 4325–4329. Trans Tech Publications Ltd.
Gao, Z., Dai, L., Mi, D., Wang, Z., Imran, M. A., and Shakir, M. Z. (2015). Mmwave massive-mimo-based wireless backhaul for the 5g ultra-dense network. IEEE Wireless Communications, 22(5):13–21.
Ge, X., Tu, S., Mao, G., Wang, C., and Han, T. (2016). 5g ultra-dense cellular networks. IEEE Wireless Communications, 23(1):72–79.
Gonçalves, J. F. and Resende, M. G. C. (2011). Biased random-key genetic algorithms for combinatorial optimization. Journal of Heuristics, 17(5):487–525.
Holland, J. H. (1992). Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control and Artificial Intelligence. MIT Press, Cambridge, MA, USA.
Jin Kyu Han, Byoung Seong Park, Yong Seok Choi, and Han Kyu Park (2001). Genetic approach with a new representation for base station placement in mobile communications. In IEEE 54th Vehicular Technology Conference. VTC Fall 2001. Proceedings (Cat. No.01CH37211), volume 4, pages 2703–2707 vol.4.
Li, L., Ma, B., Jia, Z., and Si, Y. (2017). Base station locations optimization in lte using artificial immune algorithm. In 2017 10th International Symposium on Computational Intelligence and Design (ISCID), volume 1, pages 165–168.
Mathar, R. and Niessen, T. (2000). Optimum positioning of base stations for cellular radio networks. Wireless Networks, 6(6):421–428.
Skouby, K. E. and Lynggaard, P. (2014). Smart home and smart city solutions enabled by 5g, iot, aai and cot services. In 2014 International Conference on Contemporary Computing and Informatics (IC3I), pages 874–878.
Spears, W. and De Jong, K. (1991). On the virtues of parametrized uniform crossover.
Toskala, A., Holma, H., Pajukoski, K., and Tiirola, E. (2006). Utran long term evolution in 3gpp. In 2006 IEEE 17th International Symposium on Personal, Indoor and Mobile Radio Communications, pages 1–5.
Toso, R. and Resende, M. (2015). A c++application programming interface for biased random-key genetic algorithms. Optimization Methods and Software, 30.
Vieira, R. D., Paiva, R. C. D., Hulkkonen, J., Jarvela, R., Iida, R. F., Saily, M., Tavares, F. M., and Niemela, K. (2010). Gsm evolution importance in re-farming 900 mhz band. In 2010 IEEE 72nd Vehicular Technology Conference - Fall, pages 1–5.
Whitley, D. (2019). Next Generation Genetic Algorithms: A User’s Guide and Tutorial, pages 245–274. Springer International Publishing, Cham.
Zimmermann, J., Höns, R., and Mühlenbein, H. (2003). Encon: An evolutionary alrithm for the antenna placement problem. Computers Industrial Engineering, 44:209– 226.
Bean, J. C. (1994). Genetic algorithms and random keys for sequencing and optimization. ORSA Journal on Computing, 6(2):154–160.
Boccardi, F., Heath, R. W., Lozano, A., Marzetta, T. L., and Popovski, P. (2014). Five disruptive technology directions for 5g. IEEE Communications Magazine, 52(2):74– 80.
Cardeiro, J. and Correia, L. M. (2006). Optimisation of base station location in umtsfdd for realistic traffic distributions. In 2006 IEEE 17th International Symposium on Personal, Indoor and Mobile Radio Communications, pages 1–5.
Chen, Q. B., Wang, Y., Liu, Z. J., and Liang, C. C. (2012). A new intelligent approach based on genetic algorithm for finding optimal base stations configuration in the dynamic scenario used in son. In Frontiers of Manufacturing and Design Science II, volume 121 of Applied Mechanics and Materials, pages 4325–4329. Trans Tech Publications Ltd.
Gao, Z., Dai, L., Mi, D., Wang, Z., Imran, M. A., and Shakir, M. Z. (2015). Mmwave massive-mimo-based wireless backhaul for the 5g ultra-dense network. IEEE Wireless Communications, 22(5):13–21.
Ge, X., Tu, S., Mao, G., Wang, C., and Han, T. (2016). 5g ultra-dense cellular networks. IEEE Wireless Communications, 23(1):72–79.
Gonçalves, J. F. and Resende, M. G. C. (2011). Biased random-key genetic algorithms for combinatorial optimization. Journal of Heuristics, 17(5):487–525.
Holland, J. H. (1992). Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control and Artificial Intelligence. MIT Press, Cambridge, MA, USA.
Jin Kyu Han, Byoung Seong Park, Yong Seok Choi, and Han Kyu Park (2001). Genetic approach with a new representation for base station placement in mobile communications. In IEEE 54th Vehicular Technology Conference. VTC Fall 2001. Proceedings (Cat. No.01CH37211), volume 4, pages 2703–2707 vol.4.
Li, L., Ma, B., Jia, Z., and Si, Y. (2017). Base station locations optimization in lte using artificial immune algorithm. In 2017 10th International Symposium on Computational Intelligence and Design (ISCID), volume 1, pages 165–168.
Mathar, R. and Niessen, T. (2000). Optimum positioning of base stations for cellular radio networks. Wireless Networks, 6(6):421–428.
Skouby, K. E. and Lynggaard, P. (2014). Smart home and smart city solutions enabled by 5g, iot, aai and cot services. In 2014 International Conference on Contemporary Computing and Informatics (IC3I), pages 874–878.
Spears, W. and De Jong, K. (1991). On the virtues of parametrized uniform crossover.
Toskala, A., Holma, H., Pajukoski, K., and Tiirola, E. (2006). Utran long term evolution in 3gpp. In 2006 IEEE 17th International Symposium on Personal, Indoor and Mobile Radio Communications, pages 1–5.
Toso, R. and Resende, M. (2015). A c++application programming interface for biased random-key genetic algorithms. Optimization Methods and Software, 30.
Vieira, R. D., Paiva, R. C. D., Hulkkonen, J., Jarvela, R., Iida, R. F., Saily, M., Tavares, F. M., and Niemela, K. (2010). Gsm evolution importance in re-farming 900 mhz band. In 2010 IEEE 72nd Vehicular Technology Conference - Fall, pages 1–5.
Whitley, D. (2019). Next Generation Genetic Algorithms: A User’s Guide and Tutorial, pages 245–274. Springer International Publishing, Cham.
Zimmermann, J., Höns, R., and Mühlenbein, H. (2003). Encon: An evolutionary alrithm for the antenna placement problem. Computers Industrial Engineering, 44:209– 226.
Published
2019-10-15
How to Cite
AMORIM, Lucas; VASSALO, Daniel; PEREIRA, Gabriel; PINHEIRO, Rian.
Base Station Placement across a Simulated City using a Biased Random-key Genetic Algorithm. In: NATIONAL MEETING ON ARTIFICIAL AND COMPUTATIONAL INTELLIGENCE (ENIAC), 16. , 2019, Salvador.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2019
.
p. 984-995.
ISSN 2763-9061.
DOI: https://doi.org/10.5753/eniac.2019.9351.
