Paging mobile users in cellular networks: Optimality versus complexity and simplicity

A mobile user is roaming in a zone composed of many cells in a cellular network system. When a call arrives, the system pages the user in these cells since the user never reports its location unless it leaves the zone. Each cell is associated with a positive value which is the probability that the user resides in this cell. A delay constraint requires the user to be found within a predetermined number of paging rounds where in each round a subset of the cells is paged. The goal is to design a paging strategy that minimizes the expected number of paged cells until the user is found. Optimal solutions based on dynamic programming are known. The running time of former implementations is quadratic in the number of cells and linear in the number of rounds. We introduce two implementations whose running times are also linear in the number of cells, by proving that the dynamic programming formulation satisfies properties (like the Monge property) that enable us to use various dynamic programming speed-up techniques. We also propose a new heuristic of almost linear complexity that outperforms a known linear complexity heuristic while running faster when the number of rounds is far less than the number of cells. Our comprehensive simulations compare the non-optimal heuristics with the optimal solutions, demonstrating the trade-off between optimality and running time efficiency as well as implementation simplicity.