Efficient Dynamic Multi-Step Paging for Cellular Wireless Networks

摘要

This paper addresses a study on multi-step paging for cellular wireless networks. Multi-step paging reduces paging cost by paging a mobile device in several incremental steps instead of flooding paging messages to a whole paging group (PG). The key question in multi-step paging is how to partition the PG into steps in order to minimize paging cost while satisfying constraints around the average paging delay and the tolerable paging failure rate. To find an efficient solution for this NP problem, we develop the theory of multi-step paging on location space formalization (composed of the mobile presence probability and the non-uniform paging cost distributions). We then propose an algorithm whose performance is O(2N~2) where N is the cardinality of the location space. Our algorithm, a dynamic multi-step paging (DMP) implementation, is proposed in the dynamic context of a real network environment. An analytical model is also developed for Worldwide Interoperability for Microwave Access (WiMAX) networks. Simulation results show that our algorithm can reduce paging costs by 80 percent even under strict requirements for average delay and failure probability.