Efficient Location Area Planning for PErsonal Communication Systems

A central problem in personal communication systems is to optimize bandwidth usage. Network mobility management, and in particular, location management, consumes a significant portion of bandwidth, which is a necessary overhead for supporting mobile users. 

We focus our efforts on minimizing this overhead. Unlike previous works, we concentrate on optimizing existing schemes, and so the algorithms we present are easily incorporated into current networks. 

We present the first polynomial time approximation algorithms for minimum bandwidth location management. In planar graphs, our algorithm provably generates a solution that uses no more than a constant factor more bandwidth than the optimal solution. 

In general graphs, our algorithm provably generates a solution that uses just a factor O(log n) more bandwidth than optimal where n is the number of base stations in the network. 

We further provide heuristics that improve the solution of these algorithms and show that, in practice, our algorithm produces near-optimal results. For the important case of the line graph, we present a polynomial-time optimal algorithm.