A heuristic search for generalized cellular network planning

This paper tries to solve the problem of cell to switch assignment (CSA), which plays an important role in designing an optimal location area for a mobile cellular network. The problem is conventionally formulated as a combinatorial optimization problem, which has been shown to be NP hard. So to solve this problem in real time, efficient heuristics and search strategies are necessary. In this work, the novel block depth first search (BDFS) algorithm using an admissible heuristic is deployed to assign cells to switches (i.e., to group base stations into location areas), so as to minimize the paging, updating, and physical infrastructure costs. The algorithm is flexible enough to handle both memory and time constraints while providing a satisfactory solution, which is very much useful for the mobile service providers in reconfiguring location areas online. Additionally, if the time constraint is relaxed, BDFS guarantees to produce the optimal solution, which may help a designer to properly plan a mobile cellular network in the pre-deployment stage.