The Minimum Expected Cost Paging Problem for Multi-System Wireless

• Main Authors: ROY, Abhishek, MISRA, Archan, DAS, Sajal K.
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2004
• Subjects: Software Engineering
• Online Access: https://ink.library.smu.edu.sg/sis_research/696
• Institution: Singapore Management University

The paper discusses the problem of optimal (minimum expected cost) paging for multi-system, fourth generation (4G) wireless cellular networks. A mobile node can lie simultaneously in multiple, overlapping cells. Hence, at a particular point in the paging sequence, the probability of successfully paging the mobile in a particular cell will depend not just on its marginal residence probability in that cell, but instead on the joint probability distributions. Due to this fundamental difference with a single-system cellular network, the problem of obtaining the optimal paging sequence turns out to be NP-complete. After proving this NP-completeness result, the paper presents a greedy, and intuitively appealing heuristic, where the paging sequence is obtained by choosing cells in the decreasing order of their conditional residence probabilities. The probability is computed conditional on the mobile not being present in the previous cells of the paging sequence. The paper describes how such probabilities can be computed by using a mobile-node driven, asymptoticallyoptimal, location update strategy and also quantifies the resultant savings in the paging cost.