A tabu search approach for assigning cells to switches in cellular mobile networks

✍ Scribed by Samuel Pierre; Fabien Houéto

• Publisher: Elsevier Science
• Year: 2002
• Tongue: English
• Weight: 291 KB
• Volume: 25
• Category: Article
• ISSN: 0140-3664
• DOI: 10.1016/s0140-3664(01)00371-1

✦ Synopsis

This paper proposes a tabu search approach for assigning cells to switches in wireless cellular networks. This problem is NP-hard and consequently cannot be practically solved by exact methods for real size networks. We ®rst establish a new mathematical equivalence between the assignment problem and the well-known p-®xed hub location problem. From this equivalence as a basis for a heuristic method, initial solutions have been generated. Then, some ¯exible and powerful moves, a gain structure and its update procedures are de®ned and used to improve these initial solutions and generate near optimal ®nal solutions. To evaluate the performance of this approach, we de®ne two lower bounds for the global optimum, which are used as reference to assess the quality of the obtained solutions. Computational experiments show that our approach generally provides better results than those generated by other traditional heuristics found in the literature, especially for large-scale networks with more than 50 cells and 3 switches.