Concurrently searching for mobile users in cellular networks

In today's systems, upon arrival of calls to mobile users, the system attempts to locate the users sequentially (one by one) through a paging operation. In this letter, we propose to concurrently search for a number of mobile users in a mobile network, significantly reducing the cost of locating mobile users. The reduction in the paging costs due to such a concurrent search can be quite substantial, depending on the knowledge of the probabilities of the users' locations, the number of cells in the network, and the number of mobiles to be located. Additionally, we propose a low-complexity heuristic that reduces the average paging cost by 25%, in the case of no knowledge of probabilities of the mobiles' locations. With such knowledge, further reduction in the average paging costs of up to 90% can be achieved.     

Searching for Multiple Mobile Users

The problem of searching for mobile users in cellular networks is addressed in this study. Previous studies addressing this issue have focused on the problem of searching for a single user. As it is shown in this study, the problem of maximizing the expected rate of successful searches under delay and bandwidth constraints is NP-hard. {bf When the potential locations of different users overlap, the derivation of an optimal concurrent search for many independent users from a set of optimal single user searches is NP-hard}. In reality, a cellular network has to serve many competing search requests sharing a limited bandwidth. Since the problem of maximizing the expected rate of successful searches under delay and bandwidth constraints is NP-hard, this study proposes a heuristic algorithm, that is optimal for most probable cases, and its worst case running time complexity is $O(n(log{n} + Clog{C}))$, where $n$ is the number of mobile users that must be found, and $C$ is the number of their potential locations. {bf The approximation ratio of the proposed search algorithm is less than 2}.     

Performance bounds of a multiple-step paging strategy in future universal mobile telecommunication systems

In future mobile telecommunications, due to the huge number of users and the specific functions that support mobility, a significant amount of signaling load will have to be carried by the finite capacity of the radio link. Hence, methods aiming at radio link signaling load reduction are welcome. In this paper we propose and analyze a method that saves paging signaling load by exploiting information related to the terminal location during the most recent interaction between the terminal and the network. The penalty paid is extra processing power and extra paging delays. An analytical model is developed so as to describe the performance versus traffic intensity and mobility conditions. The performance of the proposed paging scheme is investigated, and it is shown that the method operates well even in the worst case, which is the high user mobility conditions. Possible extensions of the method, which exploit information related to the mobility degree of each individual user or information characterizing the mobility conditions in a certain location area, are also proposed.This paper has been partially funded by CEC through the RACE 2066 Mobile Network (MONET) project. The paper does not present the views of the project as a whole, but those of the authors.     

Location area planning and cell-to-switch assignment in cellular networks

Location area (LA) planning plays an important role in cellular networks because of the tradeoff caused by paging and registration signalling. The upper boundary for the size of an LA is the service area of a mobile services switching center (MSC). In that extreme case, the cost of paging is at its maximum but no registration is needed. On the other hand, if each cell is an LA, the paging cost is minimal but the cost of registration is the largest. Between these extremes lie one or more partitions of the MSC service area that minimize the total cost of paging and registration. In this paper, we seek to determine the location areas in an optimum fashion. Cell to switch assignments are also determined to achieve the minimization of the network cost. For that purpose, we use the available network information to formulate a realistic optimization problem, and propose an algorithm based on simulated annealing (SA) for its solution. Then, we investigate the quality of the SA-based technique by comparing it to greedy search, random generation methods, and a heuristic algorithm.     

TMSI寻呼与选择性鉴权的使用

为了防止非法个人或团体通过监听无线路径上的信令交换而窃得移动用户真实的用户识别码（IMSI,International Mobi1e Subscriber Identification Number）或跟踪移动用户的位置,现在大多数交换机都开启了临时识别码（TMSI,Temporary Mobi1e Subscriber Identny）寻呼。而为了降低网络信令负荷,交换机可以将鉴权功能有选择性的打开。当TMSI寻呼和选择性鉴权同时打开时,有可能会造成用户的使用问题。这里主要讨论了TMSI寻呼和选择性鉴权的基本原理,并且根据在现网维护中遇到的用户投诉和河南部分交换机的设置分析二者同时打开时对网络的影响。     

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     

Enhanced distance-based location management of mobile communication systems using a cell coordinates approach

In managing the locations of mobile users in mobile communication systems, the distance-based strategy has been proven to have better performance than other dynamic strategies, but is difficult to implement. A simple approach is introduced to implement the distance-based strategy by using the cell coordinates in calculating the physical distance traveled. This approach has the advantages of being independent of the size, shape, and distribution of cells, as well as catering for the direction of movement in addition to the speed of each mobile terminal. An enhanced distance-based location management strategy is proposed to dynamically adjust the size and shape of location area for each individual mobile terminal according to the current speed and direction of movement. It can reduce the location management signaling traffic of the distance-based strategy by half when mobile terminals have predictable directions of movement. Three types of location updating schemes are discussed, namely, Circular Location Area, Optimal Location Area, and Elliptic Location Area. Paging schemes using searching techniques such as expanding distance search based on the last reported location and based on the predicted location, and expanding direction search are also explored to further reduce paging signal traffic by partitioning location areas into paging areas.     

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 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.     

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

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

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.     

A dynamic location management scheme for next-generation multitierPCS systems

Global wireless networks enable mobile users to communicate regardless of their locations. One of the most important issues is location management in a highly dynamic environment because mobile users may roam between different wireless systems, network operators, and geographical regions. A location-tracking mechanism is introduced that consists of intersystem location updates and intersystem paging. Intersystem update is implemented by using the concept of boundary location area, which is determined by a dynamic location update policy in which the velocity and the quality of service are taken into account on a per-user basis. Also, intersystem paging is based on the concept of a boundary location register, which is used to maintain the records of mobile users crossing the boundary of systems. This mechanism not only reduces location-tracking costs, but also significantly decreases call-loss rates and average-paging delays. The performance evaluation of the proposed schemes is provided to demonstrate their effectiveness in multitier personal communication systems     

Minimizing the average cost of paging under delay constraints

Efficient paging procedures help minimize the amount of bandwidth expended in locating a mobile unit. Given a probability distribution on user location, it is shown that the optimal paging strategy which minimizes the expected number of locations polledE[L] is to query each location sequentially in order of decreasing probability. However, since sequential search over many locations may impose unacceptable polling delay,D, optimal paging subject to delay constraints is considered. It is shown that substantial reductions inE[L] can be had even after moderate constraints are imposed on acceptableD (i.e.,D<-3).Since all methods of mobility management eventually reduce to considering a time-varying probability distribution on user location, this work should be applicable to a wide range of problems in the area. most notably those with additive cost structures.     

P-MIP: Paging Extensions for Mobile IP

As the number of Mobile IP users grows, so will the signalling overhead associated with Internet mobility management in the core IP network. This presents a significant challenge to Mobile IP as the number of mobile devices scale-up. In cellular networks, registration and paging techniques are used to minimize the signalling overhead and optimize the mobility management performance. Currently, Mobile IP supports registration but not paging. In this paper, we argue that Mobile IP should be extended to support paging to improve the scalability of the protocol to handle large populations of mobile devices. To address this, we introduce P-MIP, a set of simple paging extensions for Mobile IP, and discuss the construction of paging areas, movement detection, registration, paging and data handling. We present analysis and simulation results for Mobile IP with and without paging extensions, and show that P-MIP can scale well supporting large numbers of mobile devices with reduced signalling under a wide variety of system conditions.     

Location management of correlated mobile users in the UMTS

In this paper, we propose concurrently searching for correlated mobile users in mobile communications networks. Previous work either focuses on locating a single mobile user or assumes that the locations of mobile users are statistically independent. We first propose a mobility model in which the movements of mobile users are statistically correlated. Next, we use the theory of Markov chain to derive the joint probability density function of the locations of mobile users. In addition, we propose a novel approach to discover the correlations among the locations of mobile users without explicitly calculating the joint probability density function. Our simulation results indicate that exploring the correlations among the locations of mobile users could significantly reduce the average paging delay and increase the maximum stable throughput.     

Performance of improved probabilistic location update scheme forcellular mobile networks

This paper suggests an improved probabilistic location update (IPLU) scheme for advanced cellular mobile networks. The location management cost with IPLU is analyzed, and various performance characteristics of IPLU are investigated. It is shown that IPLU has the parameter q that can be used as a control parameter to achieve the best performance when the unit location update cost (U) and the unit paging cost (P) are given. In addition, this paper provides some recommendable values of q in two cases, P>U and P⩽U. As a result, we demonstrate a merit of IPLU, that is, simple implementation with an acceptable performance level, especially, under the future cellular mobile network environments where a vast number of microcells/picocells exist and the relative user mobility is very high     

A contention-free mobility management scheme based on probabilisticpaging

In forthcoming personal communication systems (PCSs), small cells are deployed to achieve high spectral efficiency. This has significant impacts on location tracking of mobile users. The increase in location update (LU) load leads to more contention on the reverse control channel. Thus, many algorithms are designed to distribute the LU load to a larger number of cells. This avoids the inefficiency of random accessing due to high offered load. In an alternative approach (Wong 1995), a contention-free LU algorithm is proposed. Two or more mobile units are permitted to register with a base station simultaneously without contention. A probabilistic paging mechanism called Bloom filtering is used to select cells to be paged. Since there is no contention in LU, inefficiencies due to random accessing are bypassed. In this paper, we present another contention-free LU algorithm. It is hybrid in the sense that LUs are temporally or geographically triggered. The use of hybrid LU alleviates inefficiencies inherent to temporal triggered LU in Wong. Three selective paging schemes are considered in this paper. Tradeoff between paging delay and paging bandwidth is addressed. The performance of this algorithm is compared to Wong and other conventional strategies. Numerical results show that the new algorithm compares favorably with previous proposed strategies     

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.     

Evaluation of location area planning scenarios in future mobile telecommunication systems

In third generation mobile telecommunication systems, signalling requirements due to location updating and paging are expected to be remarkable, mainly because of the huge number of mobile subscribers. Location area planning is characterised by the trade-off between the number of location updates and the amount of paging signalling that the network has to deal with. Location area planning should be based on criteria which guarantee that signalling load will be kept under tolerable levels. Various approaches for location area planning in a city environment—the worst case environment—are discussed in this paper. The simplest approach is the use of heuristic algorithms for approximating the optimum location area configuration. Then more complex scenarios which are based on geographical criteria (population distribution, highway topology, etc.) are investigated. Finally, user mobility characteristics are taken into account in the most complex scenarios. All scenarios are applied over a simulation model representing a city area, providing us with a very clear view of their performance characteristics.This paper has been partially funded by the CEC through the RACE 2066 MObile NETwork (MONET) project. The paper does not present the views of the project as a whole, but those of the authors.