Assigning cells to switches in mobile networks using an ant colony optimization heuristic

Autor: Joseph R. L. Fournier, Samuel Pierre
Rok vydání: 2005
Předmět:
Zdroj: Computer Communications. 28:65-73
ISSN: 0140-3664
DOI: 10.1016/j.comcom.2004.07.006
Popis: The problem of assigning cells to switches in a mobile network is an NP-Hard problem. It is therefore necessary to use a heuristic method to solve it in a reasonable amount of time. This paper applies the relatively new ant colony optimization meta-heuristic to this problem. It has also hybridized the local optimization k-opt technique with the heuristic. The developed algorithms have been applied to both problems (single and dual homing) described by the first studies regarding the assignment problem. In comparison to previous research, our methods are relatively efficient, regarding both quality of solutions provided and execution time of algorithms. It would thus be possible to increase the size of problem instances without augmenting the algorithm's execution time by a factor larger than n^2 and obtain solutions with an equivalent quality. The algorithm implemented for the double homing problem could be used to determine the best network configuration according to the number of known or anticipated calls for each cell, for each considered period of the day. It would afterwards be possible to design a dynamic algorithm that would take into account the existing physical links, which would determine in real time the appropriate moment for changing assignment (in respect of their management) of cells having two links, thus reducing the total number of handoffs occurring in the network.
Databáze: OpenAIRE