A grouping genetic algorithm for registration area planning

The enormous increase in wireless customers in recent years has taxed wireless network resources, in particular, the bandwidth available. The scarce bandwidth is not only consumed by placing and receiving calls on a portable, but by performing routine control functions to ensure universal service and increased quality of service. Among the control functions performed by a wireless network is finding the location of called mobiles. The registration area planning problem attempts to achieve this with minimal impact on the network's bandwidth. In this paper, we develop a grouping genetic algorithm to efficiently solve the registration area planning problem. The problem is NP-complete, therefore the literature has concentrated on heuristics to find good solutions in an acceptable time. The goal of registration area planning is to group wireless network cells into contiguous areas to minimize location update costs subject to paging bound and preset constraints. Therefore, the registration area planning problem is a grouping problem and grouping genetic algorithms, which have been shown to be a useful tool in solving these types of problems, are an applicable solution methodology. The proposed grouping genetic algorithm, GGARAP, has been extensively tested. Our results indicate that GGARAP is robust and finds good solutions for the registration area planning problem for a wide range of network situations. Furthermore, the computational effort involved in running GGARAP is minimal. (c) 2004 Elsevier Ltd. All rights reserved.