Modelos teóricos e algoritmos para a otimização da alocação de canais em redes móveis sem fio
Resumo
Problemas de alocação de canais são encontrados no planejamento de redes de telecomunicações, onde deve-se atribuir um canal por chamada efetuada respeitando restrições de separação entre estações transceptoras, de forma a otimizar algum critério. Neste trabalho, o problema foi explorado com enfoque de Otimização Combinatória, com a proposição de novos modelos teóricos envolvendo coloração de grafos, escalonamento em máquinas paralelas e geometria de distâncias, bem como com a definição de estratégias algorítmicas exatas e aproximadas envolvendo programação inteira e por restrições, e heurísticas baseadas em busca local, para a resolução dos mesmos. Os resultados computacionais obtidos foram competitivos com outros trabalhos da literatura, onde se provou a otimalidade em alguns casos e obteve-se melhores resultados e com melhor desempenho em outros. Em suma, as abordagens propostas permitem que o ferramental de outros problemas seja aplicado ao planejamento de redes móveis sem fio, além de apresentarem novos desafios científicos para a área.
Referências
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.
