Optimal Sequential Paging in Cellular Wireless Networks

In a high-capacity cellular network with limited spectral resources, it is desirable to minimize the radio bandwidth costs associated with paging when locating mobile users. Sequential paging, in which cells in the coverage area are partitioned into groups and paged in a non-increasing order of user location probabilities, permits a reduction in the average radio costs of paging at the expense of greater delay in locating the users. We present a polynomial time algorithm for minimizing paging cost under the average delay constraint, a problem that has previously been considered intractable. We show the conditions under which cluster paging, a simple heuristic technique proposed for use with dynamic location update schemes, is optimal. We also present analytical results on the average delay and paging cost obtained with sequential paging, including tight bounds.     

移动IP网络中基于遗传算法的多步寻呼策略及性能分析

在移动IP网络中,层次移动IP协议可降低移动IP位置管理的信令消耗。该文研究支持寻呼的HMIPv6,提出了时延限制下的多步寻呼策略以及基于遗传算法的多步寻呼方案——根据移动节点的位置概率分布,采用遗传算法对寻呼区域内的所有子网进行分组,每步寻呼一个组,使平均寻呼信令开销达到或接近最优。此外,对HMIPv6、单步寻呼的HMIPv6以及基于遗传算法的多步HMIPv6寻呼方案的信令开销进行了比较分析,得出寻呼节省信令开销的必要条件。最后,给出一组数值结果以说明所提出的寻呼策略的有效性。     

Information-Theory Based Optimal Location Management Schemes for Integrated Multi-System Wireless Networks

In a multisystem environment where a mobile node can utilize multiple interfaces and simultaneously connect to multiple providers, new opportunities exist for efficient location management strategies spanning heterogeneous cellular wireless networks. In this paper, an integrated framework is developed for location management in such a multi-system, fourth generation (4 G) wireless networks. This information-theoretic framework allows each individual sub-system to operate fairly independently, and does not require the knowledge of individual sub-network topologies. An efficient location management in such a loosely coupled network is designed by having a mobile node view its movement as a vector-valued sequence, and then transmit this sequence in an entropy coded form to the network. We demonstrate how an intelligent, integrated paging strategy must consider the joint residence probability distribution of a mobile node in multiple sub-networks. We prove that the determination of an optimal paging sequence is NP-complete, and also propose an efficient greedy heuristic to compute the paging sequence, both without and with bounds on the paging delay. Three different location tracking strategies are proposed and evaluated; they differ in their degrees of centralized control and provide tradeoff between the location update and paging costs. Simulation experiments demonstrate that our proposed schemes can result in more than 50% savings in both update and paging costs, in comparison with the basic movement-based, multi-system location management strategy.     

An optimal paging scheme for minimizing signaling costs under delaybounds

This letter introduces a method for minimizing paging costs in wireless systems with delay constraints. An optimal partition algorithm is proposed and the corresponding paging procedure is provided. Numerical results demonstrate that the new scheme outperforms other previous schemes for uniform and nonuniform location probability distributions     

Optimal decision strategies for paging in mobile cellular networks

A high‐level technical survey of paging in mobile cellular communication networks is presented in this paper. We view paging as an optimal decision problem and explore different strategies based on sequential decisions. The examined schemes concentrate on different perspectives of the problem, depending on the type of decisions and the amount of information available or exploitable by the system. This approach provides a useful categorization and an easy conceptual basis for their theoretical investigation, necessary for the deployment of advanced paging algorithms. Because of its suggested generality, the discussed framework is also laid as reference for further research. As modern networks evolve, more emphasis will be given towards optimization in all aspects of a network system. The schemes presented greatly reduce paging costs and can be used in cooperation with known location update strategies to make part of a real network location management system. Copyright © 2006 John Wiley & Sons, Ltd.     

A Combination of Optimal Partitioning and Location Prediction to Assist Paging in Mobile Cellular Networks

The correlated both in space and time user mobility behavior can aid significantly in the localization of a moving terminal in the network coverage area. However, there is always some uncertainty in mobile user position and a network-wide search cannot be done. Therefore, a predictive paging scheme must always be combined with a location update strategy and a compatible algorithm to conduct the search. In this paper, we introduce a new strategy that combines an optimal partitioning of the location area (LA) with a model to predict user movements, based on the additional information of the cell where the last interaction between the network and the terminal took place. We study the performance of the strategy under delay bounds and different mobility and call arrival characteristics. It is found that the new scheme further minimizes signaling costs and enhances previous sequential paging algorithms.     

A new analytic framework for dynamic mobility management of PCS networks

This paper presents a new analytic framework for dynamic location management of PCS networks. Based on the theory of hexagonal cellular patterns, a novel two-dimensional Markov walk model with six states is proposed to characterize the dynamic behavior of the intercell movements for a mobile station. We discover a broad class of isotropic processes having an identical uniform steady-state distribution of the six directions, but distinct circulant transition probability matrices. Six special isotropic processes exhibiting IID, directional, turning, ping-pong, h-spin, and t-spin mobility patterns are identified for performance comparison. We also generalize the selective paging strategy by introducing the concept of probabilistic selective paging (PSP) to reduce the paging cost. A unified analysis using recursive computations is carried out to compute the exact probability distribution for the number of per-call location updates. We calculate the location profile with respect to an incoming call and derive an exact expression of the average paging cost for PSP. With its ability to distinguish subtle performance variations and unveil new features of various dynamic location management schemes, our analytic framework is demonstrated to provide more precise and insightful results than conventional analysis.     

IP Paging Service for Mobile Hosts

In wireless networks, mobile hosts must update the network with their current location in order to get packets delivered. Paging facilitates efficient power management at the mobile host by allowing the host to update the network less frequently at the cost of providing the network with only approximate location information. The network determines the exact location of a mobile host through paging before delivering packets destined to the mobile host. In this paper, we propose the concept of paging as an IP service. IP paging enables a common infrastructure and protocol to support the different wireless interfaces such as CDMA, GPRS, wireless LAN, avoiding the duplication of several application layer paging implementations and the inter-operability issues that exist today. We present the design, implementation, and detailed qualitative and quantitative evaluation, using measurements and simulation, of three IP-based paging protocols for mobile hosts.     

Non-Blocking Pipeline Paging with Known Location Probabilities for Wireless Systems

Paging schemes for wireless systems have been well studied in the literature. However, most schemes are considered on per user basis. In these schemes, when an incoming call arrives at a mobile terminal (MT), a paging request (PR) is put in a queue. PRs are served in an FIFO manner. When a PR is served, a search process is carried out to find the corresponding MT in a location area (LA). Most schemes study how to achieve a better performance in terms of cost with/without delay constraints per PR, and totally ignore other PRs in the queue until the MT is found or all the cells in the LA have been paged. In this paper, we propose a non-blocking pipeline probability paging scheme, which assumes known knowledge on location probabilities of individual MTs, under a paging delay constraint, where the location probability of an MT in a cell is the probability that the MT is in the cell. The proposed scheme is independent of the number of PRs in the queue and the arrival rate of PRs. Our study shows that the proposed scheme outperforms both the sequential probability paging scheme with known knowledge on location probabilities of individual MTs and the blanket paging scheme in terms of discovery rate and the total delay. Finally, we study several optimization problems with quality of service constraint for the pipeline probability paging scheme.     

A Location Management Scheme Using Direction Characteristics of Mobile Terminals in Mobile Communication Networks

Recently, as the number of mobile terminals (or users) keeps explosively increasing, the location management to track the mobile terminals in mobile communication networks is becoming more important. However, previous schemes have used static location information without any consideration about the moving direction of a mobile terminal. For a fixed paging area, this results in unnecessary pagings, thus increasing the location management cost. In this paper, we propose a new location management scheme using the direction characteristics of a mobile terminal. The direction vector is defined to represent the moving direction of a mobile terminal and to compute a distance from the cell where a location update occurs to the current cell. The offset operation of direction vectors is also presented to represent the position of a mobile terminal in a paging area. This allows the mobile terminal to determine whether a location update will be performed or not. The mobile terminal can also vary its own paging area dynamically according to its moving direction whenever it moves across its paging area. In addition, we develop an analytical model for the proposed scheme which captures the direction characteristics of a mobile terminal based on the Markov model. Analytical results show that the proposed scheme can reduce location management cost by forming a dynamic paging area along the moving direction of a mobile terminal when compared to other schemes.Ui-Sung Song received his B.S and M.S. degrees in Computer Science and Engineering from Korea University, Seoul, Korea in 1997 and 1999, respectively. He is currently a Ph.D. candidate in Computer Science and Engineering from Korea University. Also, he is currently a researcher in the Research Institute of Computer Science and Engineering Technology at Korea University. His research interests include mobile IP, PCS networks, and ad-hoc networks.Joon-Min Gil received his B.S. and M.S. degrees in Computer Science from Korea University, Chochiwon, Korea in 1994 and 1996, respectively. He received his Ph.D. degree in Computer Science and Engineering from Korea University, Seoul, Korea in 2000. From 2001 to 2002, he was a visiting research associate in the Department of Computer Science at the University of Illinois at Chicago, U.S.A. He is currently a senior research engineer in Supercomputing Center at Korea Institute of Science & Technology Information, Daejeon, Korea. His recent research interests include distributed and mobile computing, wireless networks, Internet computing, P2P networks, and grid computing.Chong-Sun Hwang received his M.S. degree in Mathematics from Korea University, Seoul, Korea in 1970, and his Ph.D. degree in Statistics and Computer Science from the University of Georgia in 1978. From 1978 to 1980, he was an assistant professor at South Carolina Lander State University. He is currently a full professor in the Department of Computer Science and Engineering at Korea University, Seoul, Korea. Since 2004, he has been a Dean in the College of Information and Communications at Korea University. His research interests include distributed systems,distributed algorithm, and mobile computing systems     

Effect of dormant registration on performance of mobility management based on IP paging in wireless data networks

Unlike traditional cellular networks, which provide mainly voice services, there is, at present, no method that enables the effective management of terminal mobility for both active and idle mobile terminals in data networks. Although IP paging has been introduced to reduce power consumption of dormant mobile terminals, there is no concern to design an effective IP paging method for real wireless environments. Therefore, we propose a new dormant registration based IP paging method and analyze the effect of the dormant registration threshold used in IP paging on the performance of mobility management. Moreover, we demonstrate the importance of selecting an appropriate value for the dormant registration threshold.     

User Independent Paging Scheme for Mobile IP

Multi-step paging has been widely proposed in personal communications services (PCS) systems to reduce the signaling overheads. Similar ideas can be applied to Mobile IP to provide IP paging services. However, current proposed multi-step paging schemes are user dependent under which the partition of paging areas and the selection of paging sequence are different for each user. The performance of a user dependent paging scheme for individual users may be affected by many factors. It is often difficult to achieve perfect performance for each user. In addition, when multiple users are paged at the same time, user dependent paging schemes may consume significant system resources. This paper introduces a user independent paging scheme where the paging criterion is not based on individual user information. The goal of user independent paging is to provide satisfactory overall performance of the whole system, when personalized optimal performance for each user is hard to obtain. The user independent paging scheme is proposed for IP mobility for its easy implementation and convenient combination with paging request aggregation. The paging criterion adopted is the mobility rate of each subnet determined by the aggregated movements of all mobile users. In order to implement the proposed scheme, a concept of “semi-idle state” is introduced and the detailed solution for obtaining mobility rate is presented. Analytical results show that when paging one user at a time, the performance of the proposed user independent paging scheme is comparable to that of the paging schemes based on perfect knowledge of user movement statistics. When paging multiple users simultaneously and when the knowledge on individual user behavior is not perfectly accurate, the proposed scheme has remarkable advantages in terms of reducing the overall paging cost. Jiang Xie received her B.E. degree from Tsinghua University, Beijing, China, in 1997, M.Phil. degree from Hong Kong University of Science and Technology in 1999, and M.S. and Ph.D. degrees from Georgia Institute of Technology in 2002 and 2004, respectively, all in electrical engineering. She is currently an assistant professor with the Department of Electrical and Computer Engineering at the University of North Carolina-Charlotte. Her current research interests include resource and mobility management of wireless networks,QoS provisioning, and next-generation Internet. She is a member of IEEE and ACM.     

Hash-Based Paging and Location Update Using Bloom Filters

We develop and analyze a hash-based paging and location update technique that reduces the paging cost in cellular systems. By applying a Bloom filter, the terminal identifier field of a paging message is coded to page a number of terminals concurrently. A small number of terminals may wake up and send what we call false location updates although they are not being paged. We compare the total number of paging and false location update messages with the cost of the standard paging procedure. Fortunately, the false location update probabilities can be made very small, and important bandwidth gains can be expected. The larger the size of the terminal identifier, the less probable are false location updates. Therefore, hash-based paging especially shows promise for IP paging in mobile IPv6 networks with 128-bit mobile host addresses.     

LEO卫星网络基于动态位置区的寻呼策略

针对LEO卫星网络中具有自主定位能力的用户终端,采用基于地理位置的动态位置区划分方案,根据用户移动速度设置位置区的大小。在动态位置区的基础上,对高速移动用户提出了一种基于时延限制的分组寻呼策略。仿真结果表明,对于低速移动用户,二次寻呼策略的时延和开销性能最佳;对于高速移动用户,基于时延限制的分组寻呼策略最佳。     

A parallel shuffled paging strategy under delay bounds in wireless systems

In sequential paging schemes, the paging process is considered on per user basis. When an incoming call arrives to a mobile terminal (MT), the associated location area is divided into several paging areas (PAs) and PAs are paged one by one until the MT is found. Even though sequential paging algorithms can reduce the paging cost compared to the blanket-paging scheme, they introduce extra and unnecessary delay due to the fact that, during each paging cycle, unpaged cells are idle and unused in terms of paging. In this letter, a simple parallel shuffled paging strategy is proposed to reduce delay and improve performance. In the proposed scheme, multiple MTs can be paged in difference PAs in parallel. Our study shows that the proposed scheme outperforms both the sequential paging and the blanket paging in terms of discovery rate and queueing delay.     

Derivation of Moving Distance Distribution to Enhance Sequential Paging in Distance-Based Mobility Management for PCS Networks

The total signaling cost of distance-based location management scheme, which is the lowest among dynamic location management schemes for PCS networks, can be further reduced by a sequential paging strategy that pages first the cells in which the mobile is most likely located. To enable this strategy, we derive the probability distribution of a mobile's moving distances between the last location update and the next call arrival. An efficient and effective sequential paging scheme is presented, which guarantees that a mobile can be located during the first paging step with a probability equal to or better than a predefined value. The features of the proposed model include flexible cell topologies, general cell residence time, and full use of mobile's moving pattern     

关于TMSI寻呼与IMSI寻呼性能分析

随着移动用户的持续增长和手机新业务的不断推广,移动通信系统的寻呼负荷日益加重。以移动用户漫游被叫时的呼叫流程为例,分析IMSI寻呼和TMSI寻呼的原理,对比两种寻呼方式对网络性能影响,提出一种评估寻呼方式的量化计算方法。通过对寻呼容量较为紧张网元的试验证明,该方法可以科学指导寻呼方式的优化工作,提高移动通信网络的系统寻呼容量,改善移动通信系统寻呼性能。     

卫星与地面移动通信系统综合环境下的一种位置管理策略

提出了一种在卫星与地面移动系统综合环境下的位置管理方案，即把两系统相重叠的小区设置为边界位置区(BLA)，漫游用户在BLA中进行位置更新，呼叫到达时，BLA中的位置寄存器配合系统进行寻呼。通过计算和数值分析证明该方案不仅可以使原有两系统结构不发生变化，并且能有效减小位置更新与寻呼造成的系统开销。     

Efficient Location and Paging Area Planning in Future Cellular Systems

Efficient resource utilisation in future cellular systems is partly related to the location update and paging operations, which rely on proper planning of location and paging areas, and the application of efficient paging schemes. Important is the design of low complexity planning algorithms that may enable the system to dynamically adapt to new traffic and mobility conditions. In this paper we define and solve versions of the location and paging area planning problems focusing also on algorithms that are applicable in real-time. Thus, they can be used to adapt location and paging areas to traffic and mobility conditions. Starting from a formal definition and an optimal formulation, we solve efficiently by means of a low complexity heuristic, a general version of the location area planning problem. Regarding paging area planning, we provide a low complexity algorithm, under the assumption that the scheme applied falls within the last interaction based paging (LIBP) category. The results presented, and the low cost and complexity induced by the proposed schemes, indicates that the real-time application of the schemes is feasible.     

PCS网络中一种改进的寻呼算法

本文对PCS网络中用户处于归属LA时,提出了一种改进的寻呼算法:常驻小区寻呼法.通过对用户在归属LA各小区驻留时间的分析,系统首先寻呼用户常驻小区,若不成功再寻呼其它小区.与现有移动通信系统寻呼算法相比,它可使系统节省大量的寻呼开销、进一步提高无线资源利用率.本文的不足是用户在其非常驻小区时,有可能其首次被呼比现有移动通信系统的被呼要多一次寻呼延迟.