Time efficient heuristics for cell-to-switch assignment in quasi-static/dynamic location area planning of mobile cellular networks

This paper presents a set of time efficient, sub-optimal heuristics to solve the problem of assigning cells to mobile switching centers (or, switches in short) for an effective location area (LA) planning in a mobile cellular network (MCN). A common objective of this NP-hard optimization problem, termed as cell-to-switch assignment (CSA) in the literature, is to minimize the hybrid cost, comprising handoff cost between adjacent cells, and the cable cost between cells and switches, subject to the constraint that the call volume to be handled by a switch should not exceed its traffic handling capacity. To solve CSA for a quasi-static/dynamic LA design, we need fast algorithms capable of producing acceptable solutions within a reasonable time. In this work, we first propose four variants (termed as heuristics III through VI) of our earlier heuristic (termed as heuristic II) and compare all of them with other published heuristics in respect of execution time and solution cost. Results indicate that though no single heuristic performs equally well with respect to both optimality and speed, heuristic IV is the best of the lot. Secondly, we modify the original CSA problem to include the factor of load balancing amongst switches (thereby minimizing unfairness), and propose a new CSA algorithm with load balancing (CALB), which emphasizes more on load balancing than on cost optimization. It is found that CALB is fast as heuristic VI, and performs extremely well in balancing the traffic amongst the switches, thereby increasing the overall scalability of MCNs against the increase in either mobile user density or per user traffic.