Minimizing the average cost of paging under delay constraints

Efficient paging procedures help minimize the amount of bandwidth expended in locating a mobile unit. Given a probability distribution on user location, it is shown that the optimal paging strategy which minimizes the expected number of locations polled E[L] is to query each location sequentially in order of decreasing probability. However, since sequential search over many locations may impose unacceptable polling delay, D, optimal paging subject to delay constraints is considered. It is shown that substantial reductions in E[L] can be had even after moderate constraints are imposed on acceptable D (i.e., D <= 3). Since all methods of mobility management eventually reduce to considering a time-varying probability distribution on user location, this work should be applicable to a wide range of problems in the area. most notably those with additive cost structures.