Modelos teóricos e algoritmos para a otimização da alocação de canais em redes móveis sem fio
Abstract
Channel allocation problems are found in the planning of telecommunication networks, where we must assign a channel for outgoing call restrictions respecting separation among transceiver stations, in order to optimize some criterion. In this work, this problem was explored with combinatorial optimization approach, with the proposition of new theoretical models involving graph coloring, scheduling on parallel machines and distance geometry, as well as the definition of exact and approximate algorithmic strategies, involving integer and constraint programming, and heuristics based on local search for solving them. The computational results obtained were competitive, which proved optimality in some cases and obtained better results and better performance in others. In short, the proposed approaches allow the tools of other problems is applied to the planning of mobile wireless networks and present new scientific challenges to the area.
References
Audhya, G., Sinha, K., Ghosh, S., and Sinha, B. (2011). A survey on the channel assignment problem in wireless networks. Wireless Communications and Mobile Computing, 11:583–609.
Dias, B. (2014). Modelos teóricos e algoritmos para a otimização da alocação de canais em redes móveis sem fio. Master’s thesis, Universidade Federal do Amazonas, Manaus - AM, Brasil.
Dias, B., Freitas, R., and Maculan, N. (2012). Alocação de canais em redes celulares sem fio: algoritmos e modelos teóricos em grafos e escalonamento. In Anais do XLIV Simpósio Brasileiro de Pesquisa Operacional. Sociedade Brasileira de Pesquisa Operacional (SOBRAPO).
Dias, B., Freitas, R., and Maculan, N. (2013a). Simulated annealing para a alocação de canais em redes móveis celulares. In Anais do XLV Simpósio Brasileiro de Pesquisa Operacional. Sociedade Brasileira de Pesquisa Operacional (SOBRAPO).
Dias, B., Freitas, R., and Maculan, N. (2014). Algorithms for min-max channel assignment problems in wireless networks. Computers and Operations Research. Submetido.
Dias, B., Freitas, R., Maculan, N., Szwarcfiter, J., and Michelon, P. (2015). Distance geometry approach for special graph coloring problems. International Transactions on Operational Research. A ser publicado.
Dias, B., Freitas, R., and Szwarcfiter, J. (2013b). On graph coloring problems with distance constraints. In Proceedings of I Workshop on Distance Geometry and Applications (DGA 2013).
Freitas, R., Dias, B., Maculan, N., and Szwarcfiter, J. (2014). On feasibility conditions in graph coloring problems with distance constraints. In Many Faces of Distances (Workshop).
Hale, W. K. (1980). Frequency assignment: Theory and applications. Proceedings of the IEEE, 25:1497–1514.
Koster, A. (1999). Frequency assignment: models and algorithms. Universiteit Maastricht.
