TY - GEN
T1 - Paging mobile users efficiently and optimally
AU - Bar-Noy, Amotz
AU - Feng, Yi
AU - Golin, Mordecai J.
PY - 2007
Y1 - 2007
N2 - A mobile user is roaming in a zone composed of N cells in a cellular network system. When a call to the mobile user arrives, the system pages the mobile user in these cells since it never reports its location unless it leaves the zone. The N cells are associated with a probability vector (p1, . . . , pN) where pi is the probability that the mobile user resides in the ith cell and all the probabilities are independent. A delay constraint paging strategy must find the mobile user within D (1 ≤ D ≤ N) paging rounds; in each round a subset of the N cells is paged. The goal is to minimize the expected number of paged cells until the mobile user is found. Solutions based on dynamic programming that yield optimal strategies are known. The running time of the known implementations is Θ(N2D). Our first contribution is to improve the running time to Θ(ND) by proving that the dynamic programming recursive formulation satisfies the Monge property, permitting us to use various dynamic programming speedup techniques. A Θ(N) heuristic solution is also known. Our second contribution is a heuristic whose running time is Θ(N log D). Our heuristic outperforms the known heuristic while running faster for D N. We compare the non-optimal heuristics with the optimal solution demonstrating the tradeoff between optimality and running time efficiency of various solutions.
AB - A mobile user is roaming in a zone composed of N cells in a cellular network system. When a call to the mobile user arrives, the system pages the mobile user in these cells since it never reports its location unless it leaves the zone. The N cells are associated with a probability vector (p1, . . . , pN) where pi is the probability that the mobile user resides in the ith cell and all the probabilities are independent. A delay constraint paging strategy must find the mobile user within D (1 ≤ D ≤ N) paging rounds; in each round a subset of the N cells is paged. The goal is to minimize the expected number of paged cells until the mobile user is found. Solutions based on dynamic programming that yield optimal strategies are known. The running time of the known implementations is Θ(N2D). Our first contribution is to improve the running time to Θ(ND) by proving that the dynamic programming recursive formulation satisfies the Monge property, permitting us to use various dynamic programming speedup techniques. A Θ(N) heuristic solution is also known. Our second contribution is a heuristic whose running time is Θ(N log D). Our heuristic outperforms the known heuristic while running faster for D N. We compare the non-optimal heuristics with the optimal solution demonstrating the tradeoff between optimality and running time efficiency of various solutions.
UR - https://www.webofscience.com/wos/woscc/full-record/WOS:000249117703039
UR - https://www.scopus.com/pages/publications/34548312422
U2 - 10.1109/INFCOM.2007.222
DO - 10.1109/INFCOM.2007.222
M3 - Conference Paper published in a book
SN - 1424410479
SN - 9781424410477
T3 - Proceedings - IEEE INFOCOM
SP - 1910
EP - 1918
BT - Proceedings - IEEE INFOCOM 2007
T2 - IEEE INFOCOM 2007: 26th IEEE International Conference on Computer Communications
Y2 - 6 May 2007 through 12 May 2007
ER -