SEARCHING MOBILE USERS IN CELLULAR NETWORKS WITH A-PRIORI STATISTICAL KNOWLEDGE OF THEIR WHEREABOUTS

In cellular phone systems, when a call to a mobile user arrives, it is necessary to locate the user in order to establish the connection. In current systems, the user is paged among all possible cells. Such paging process is conducted in multiple rounds. In each round, a subset of the cells are paged. Once the cell that contains the user is paged, the paging process is completed. Given the limited bandwidth available in cellular networks, an important objective of paging process is to find the mobile user with minimum number of cells being paged. If there is no a-priori knowledge about user location, the best paging strategy is to randomly page the cells in rounds. However, in many cases, cell phone systems are with some a-priori knowledge about the probabilities of a user residing in different cells. Therefore, effective paging strategies should be able to reduce expected number of cells paged, and algorithms that efficiently generate such paging strategies are highly desired. Formally, let a mobile user roam in a zone of N cells, C_1, ..., C_N. Let p_1,..., p_N be the independent probabilities of the user residing in the cells. The user must be found within $D$ rounds. A paging strategy A is an ordered partition of the cells, A_1, ..., A_D, such that in the ith round, the cells in A_i are paged. The paging process terminates once the cell that contains the user is paged. The cost of the paging strategy is the expected number of cells being paged. Let |A_i| be the number of cells in A_i, the paging cost can be formally defined as:

cost(A)=\sum_{d=1}^{D}(|A_d|\sum_{C_j\in{\bigcup_{i=1}^{d}{A_i}}}p_j

There are two performance measurements of algorithms that generate paging strategies - efficiency and optimality. Efficiency is the time complexity for an algorithm generates a paging strategy, and optimality is the paging cost of a strategy generated by an algorithm. In this survey, the problem is introduced with formal definition. Various algorithms are reviewed and analyzed hierarchically in both their efficiency and optimality. Furthermore, the problem is generalized to the version of mutually paging multiple users. In the multiple-user paging problem, the hardness and approximation algorithms to the conference call problem and the yellow page problem are reviewed. In addition, algorithms that solve major paging problems, part of which serves as our future research direction, are reviewed and discussed.