Adaptive Paging Algorithms for Cellular Systems

Adaptive algorithms which optimize the paging activity in a Cellular Mobile Telephone System are presented. They are analyzed within the context of North American Cellular Systems serving EIA/TIA 553 and IS 54 Rev B standard compliant mobiles. The basic approach is to page the cells in the system in two steps. First, page only those cells the mobile is most likely to be in (paging zone), and if no page response is received from them, then page the rest of the system also. A fixed interval registration scheme is used for tracking the location of the mobiles in the system. Every time a mobile registers, the cell it registered from is recorded in the VLR. When a mobile needs to be paged, the paging zone is selected based on the cell that it had last registered from (last known cell). In this paper, a novel method of computing the optimal paging zones is presented. The Mobile Switching Center (MSC) continuously collects page response data in the Location Accuracy Matrix (LAM). LAM keeps count of precisely how many page responses are received from each cell in the system. Using the LAM data, we compute the mean probability of locating the mobile in any cell of the system at the time of paging, given its last known cell. We present algorithms that use these probabilities to compute the optimal paging zones. Variations of the two step paging algorithm such as multiple step paging, repage of the paging zone, zone only paging and paging during overload are also presented. We prove that the algorithms presented are optimal and illustrate through examples the reduction in paging activity and the trade offs involved in each case. In a typical cellular environment, a 75–80% page reduction over system wide paging is obtained. The algorithms presented could be used to design a self engineering MSC that can automatically generate optimal paging zones.