Cost analysis and minimization of movement-based location management schemes in wireless communication networks: a renewal process approach

The paper makes new contributions to cost analysis and minimization of movement-based location management schemes in wireless communication networks. The main contributions of the paper are three-fold. First, we consider two different call handling models, that is, the call plus location update (CPLU) model and the call without location update (CWLU) model. We point out that all existing analysis of location update cost of a movement-based location management scheme (MBLMS) do not accurately capture the essence of the two models. Second, we analyze the exact location update cost of an MBLMS under both CPLU and CWLU models using a renewal process approach which has rarely been used before. We find that the location update cost of an MBLMS under the CWLU model is much easier to analyze than that of an MBLMS under the CPLU model. Furthermore, an MBLMS operated under the CWLU model has lower location update cost than an MBLMS operated under the CPLU model. Third, we are able to derive a closed form solution to the movement threshold that minimizes the total cost of location management in an MBLMS for the CPLU model when the inter-call time has an arbitrary distribution and the cell residence time has an Erlang distribution, and for the CWLU model when both inter-call time and cell residence time have arbitrary distributions. Such closed form solutions have not been available in the existing literature.     

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     

Movement-based location update and selective paging for PCSnetworks

This paper introduces a mobility tracking mechanism that combines a movement-based location update policy with a selective paging scheme. Movement-based location update is selected for its simplicity. It does not require each mobile terminal to store information about the arrangement and the distance relationship of all cells. In fact, each mobile terminal only keeps a counter of the number of cells visited. A location update is performed when this counter exceeds a predefined threshold value. This scheme allows the dynamic selection of the movement threshold on a per-user basis. This is desirable as different users may have very different mobility patterns. Selective paging reduces the cost for locating a mobile terminal in the expense of an increase in the paging delay. We propose a selective paging scheme which significantly decreases the location tracking cost under a small increase in the allowable paging delay. We introduce an analytical model for the proposed location tracking mechanism which captures the mobility and the incoming call arrival patterns of each mobile terminal. Analytical results are provided to demonstrate the cost-effectiveness of the proposed scheme under various parameters     

Mobile user location update and paging under delay constraints

Wireless personal communication networks (PCNs) consist of a fixed wireline network and a large number of mobile terminals. These terminals are free to travel within the PCN coverage area without service interruption. Each terminal periodically reports its location to the network by a process calledlocation update. When a call for a specific terminal arrives, the network will determine the exact location of the destination terminal by a process calledterminal paging. This paper introduces a mobile user location management mechanism that incorporates a distance based location update scheme and a selective paging mechanism that satisfies predefined delay requirements. An analytical model is developed which captures the mobility and call arrival pattern of a terminal. Given the respective costs for location update and terminal paging, the average total location update and terminal paging cost is determined. An iterative algorithm is then used to determine the optimal location update threshold distance that results in the minimum cost. Analytical results are also obtained to demonstrate the relative cost incurred by the proposed mechanism under various delay requirements.     

低轨卫星系统中结合时间和移动的位置更新策略

低轨(LEO)卫星快速运动,移动终端(MT)相对于卫星的位置信息也在不断变化,如何有效地管理MT的位置信息,减小位置更新频率和寻呼开销是研究位置管理的主要目的。为此,提出一种低轨卫星系统中的动态位置管理策略,基于时间和移动相结合进行位置更新,在不增加寻呼开销的条件下,减小了位置更新频率,从而有效降低了位置管理的总开销。     

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.     

小区分层依概率寻呼的位置管理策略

位置管理是移动通信领域的一个具有挑战性的问题,涉及到位置更新和位置查找操作.我国及其他国家目前正在使用的个人通信网络中,基本的位置管理策略(简称"基本策略")的位置查找操作采用的是,在整个位置区中同步寻呼移动台.由于所要寻找的移动台只在由众多小区所组成的位置区内的一个小区中,因此,"基本策略"会造成系统资源的极大浪费.本文给出一种对位置区内的小区进行分层,按移动台在各层小区的概率从大到小的次序,逐层进行寻呼的位置管理策略(简称"分层策略").在假定移动台在各个小区的逗留时间是符合一般概率分布的随机变量的条件下,推导出移动台处于各层小区的概率及"分层策略"所需搜索的小区平均个数公式.证明了"分层策略"的位置管理费用不大于"基本策略".     

Cooperative Location Management for a Cellular Network with Ad Hoc Communication

The cellular network with ad hoc communication has been foreseen in the next-generation mobile communication system. For such a network, a distance-based (DB) location management scheme cooperated with the ad hoc assistance node (DBCAN) is proposed in this paper. Allowing a mobile terminal to pass its mobility information to the ad hoc assistance node (AAN) with appropriate location updating, DBCAN can effectively reduce the paging cost and limit the paging delay. Moreover, DBCAN includes a method to determine whether AANs should be utilized or not to make cost effective. Our simulation results show that DBCAN can effectively reach cost reduction and still get performance improvement even if the probability to successfully deliver mobility information to AANs falls to the median level.     

Paging area optimization based on interval estimation in wireless personal communication networks

We consider an optimum personal paging area configuration problem to improve the paging efficiency in PCS/cellular mobile networks. The approach is to set up the boundaries of a one-step paging area that contain the locations of a mobile user with a high probability and to adjust the boundaries to gain a coverage that is matched to the mobile user's time-varying mobility pattern. We formulate the problem as an interval estimation problem. The objective is to reduce the paging signaling cost by minimizing the size of the paging area constrained to certain confidence measure (probability of locating the user), based on a finite number of available location observations of the mobile user. Modeling user mobility as a Brownian motion with the drift stochastic process and by estimating the parameters of the location probability distribution of the mobility process, the effects of the mobility characteristics and the system design parameters on the optimum paging area are investigated. Results show: (1) the optimum paging area expands with the time elapsed after the last known location of the user; (2) it also increases with the length of a prediction interval and the location probability; (3) the relative change in the paging area size decreases with the increase in the number of location observations. This revised version was published online in June 2006 with corrections to the Cover Date.     

Paging area optimization based on interval estimation in wireless personal communication networks

We consider an optimum personal paging area configuration problem to improve the paging efficiency in PCS/cellular mobile networks. The approach is to set up the boundaries of a one-step paging area that contain the locations of a mobile user with a high probability and to adjust the boundaries to gain a coverage that is matched to the mobile user's time-varying mobility pattern. We formulate the problem as an interval estimation problem. The objective is to reduce the paging signaling cost by minimizing the size of the paging area constrained to certain confidence measure (probability of locating the user), based on a finite number of available location observations of the mobile user. Modeling user mobility as a Brownian motion with the drift stochastic process and by estimating the parameters of the location probability distribution of the mobility process, the effects of the mobility characteristics and the system design parameters on the optimum paging area are investigated. Results show: (1) the optimum paging area expands with the time elapsed after the last known location of the user; (2) it also increases with the length of a prediction interval and the location probability; (3) the relative change in the paging area size decreases with the increase in the number of location observations. This revised version was published online in June 2006 with corrections to the Cover Date.     

指针推进移动性管理策略中指针链长度的概率

为了降低移动通信网络中位置跟踪操作的代价,指针推进策略被提出.显然,指针链长度的确定对这一策略的有效应用是至为重要的.已有论文假定移动台在位置区的逗留时间服从指数分布的条件下,对指针链的长度进行研究,但指数分布的特殊性,限制了其研究结果的应用.本文推广了上述结果,研究了移动台在位置区的逗留时间服从一般概率分布的指针推进策略,通过构造向量马氏过程,利用密度演化方法,导出了指针链长度的概率公式,这个公式可用于对各种指针推进策略性能的评价.     

Dynamic mobile user location update for wireless PCS networks

The basic architecture of a personal communication network consists of a wireline network and mobile terminals. Each mobile terminal communicates with the wireline network through a nearby base station. In order to route incoming calls to a destination mobile terminal, the network must keep track of the location of each mobile terminal from time to time. This is achieved bylocation update such that each mobile terminal reports its current location to the network at specific time points. When an incoming call arrives, the network will page the mobile terminal starting from the last updated location. A trade-off, therefore, exists between the frequency of location update and the number of locations paged in order to track down the mobile terminal. This paper introduces a location update policy which minimizes the cost of mobile terminal location tracking. A mobile terminal dynamically determines when to update after moving to a new cell based on its mobility pattern and the incoming call arrival probability. The performance of this scheme is close to that of the optimal policy reported earlier. However, the processing time requirement of this scheme is very low. The minimal computation required by this scheme enables its usage in mobile terminals which has limited energy supply and computational power.     

A direction-based location update scheme with a line-pagingstrategy for PCS networks

On the problem of location update and terminal paging, many schemes using ring-paging strategies have been proposed. However, sequentially paging the rings surrounding the mobile user's last updated location may cause large paging cost. We propose a direction-based location update (DBLU) scheme using a line-paging strategy to reduce the paging cost. A moving direction identification mechanism using only simple computations detects the change of moving direction and updates the mobile's location. The numerical results show that our DBLU scheme achieves good performance when the paging cost is high     

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.     

An adaptive location management scheme for mobile broadband cellular systems

This paper presents an adaptive location management strategy that considers both location updating and paging by evaluating realistic mobility patterns. It proposes the design of an adaptive macro-location area based on multi-registration adapted to the terminals’ trajectory to reduce location updates. The solution includes an estimation of residence probabilities in the areas of the multi-registered list. This facilitates the design of a sequential paging scheme that reduces the average paging cost. Results show the capability of the solution to adapt to mobility patterns and traffic conditions in the network to minimize the overall location cost. Furthermore, the multi-registration approach and the reduced complexity in both network infrastructure and mobile terminals make the solution suitable for new packet-based broadband cellular systems.     

An adaptive distance-based location update algorithm fornext-generation PCS networks

In this paper, we propose a stochastic model to compute the optimal update boundary for the distance-based location update algorithm. The proposed model is flexible and captures some of the real characteristics in the wireless cellular environment. The model can adapt to arbitrary cell topologies in which the number of neighboring base stations at different locations may vary. The cell residence time can follow general distributions which captures the fact that the mobile user may spend more time at certain locations than others. The model also incorporates the concept of a trip in which the mobile user may follow a particular path to a destination. For implementation, the decision of location update can be made by a simple table lookup. Numerical results indicate that the proposed model provides a more accurate update boundary in real environment than that derived from a hexagonal cell configuration with a random walk movement pattern. The proposed model allows the network to maintain a better balance between the processing incurred due to location update and the radio bandwidth utilized for paging between call arrivals     

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.     

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.     

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     

A novel sectional paging strategy for location tracking in cellular networks

In this letter, we propose a new paging technique, sectional paging, that reduces the paging cost while complying with the delay constraint for mobiles roaming with traceable patterns. Without having to install much additional complexity, the developed scheme predicts the likelihood of residence and assigns optimal paging boundaries. Thus while complying with the required delay constraints, quality-of-service (QoS) measures will not need to be sacrificed as a result of increasing the update threshold. Under the same network conditions and mobile characteristics, simulation results reveal that the usage of sectional paging is most suitable when the roaming pattern is either traceable or can be predicted with reasonable precision.