15.6 Location Update


15.6 Location Update

In the previous section, the tracking of an MT has been discussed when an incoming call is to be delivered. As the MTs move around the network service area, the data stored in these databases may no longer be accurate. To ensure that calls can be delivered successfully, a mechanism is needed to update the databases with up-to-date location information. This is called location update (LU) or registration. Several location updating methods are based on LA structuring. Two automatic location area management schemes are very much in use: [23]

  1. Periodic location updating. This method, although the simplest, has the inherent drawback of having excessive resource consumption, which at times is unnecessary.

  2. Location updating on LA crossing. A network must retain information about the locations of endpoints in the network, in order to route traffic to the correct destinations. Location tracking (also referred to as mobility tracking or mobility management) is the set of mechanisms by which location information is updated in response to endpoint mobility. In location tracking, it is important to differentiate between the identifier of an endpoint (i.e., what the endpoint is called) and its address (i.e., where the endpoint is located). Mechanisms for location tracking provide a time-varying mapping between the identifier and the address of each endpoint.

Most location-tracking mechanisms may be perceived as updating and querying a distributed database (the location database) of endpoint identifier-to-address mappings. In this context, location tracking has two components: (1) determining when and how a change in a location database entry should be initiated, and (2) organizing and maintaining the location database. In cellular networks, endpoint mobility within a cell is transparent to the network, and hence location tracking is only required when an endpoint moves from one cell to another. Location tracking typically consists of two operations: (1) updating (or registration), the process by which a mobile endpoint initiates a change in the location database according to its new location; and (2) finding (or paging), the process by which the network initiates a query for an endpoint's location (which may result also in an update to the location database). Most location-tracking techniques use a combination of updating and finding in an effort to select the best trade-off between update overhead and delay incurred in finding. Specifically, updates are not usually sent every time an endpoint enters a new cell, but rather are sent according to a predefined strategy such that the finding operation can be restricted to a specific area. There is also a trade-off, analyzed formally in Madhow and coworkers, [24] between the update and paging costs. Figure 15.3 illustrates a classification of possible update strategies. [25]

click to expand
Figure 15.3: Classifications of location update strategies.

15.6.1 Location Update Static Strategies

In a static update strategy, there is a predetermined set of cells at which location updates may be generated. Whatever the nature of mobility of an endpoint, location updates may only be generated when (but not necessarily every time) the endpoint enters one of these cells. Two approaches to static updating are as follows.

  1. Location areas (also referred to as paging or registration areas). [26] In this approach, the service area is partitioned into groups of cells with each group as a location area. An endpoint's position is updated if and only if the endpoint changes location areas. When an endpoint needs to be located, paging is done over the most-recent location area visited by the endpoint. Location tracking in many 2G cellular systems, including GSM [27] and IS-41, [28] is based on location areas. [29] Several strategies for location area planning in a city environment have been evaluated, [30] including strategies that take into account geographical criteria (such as population distribution and highway topology) and user mobility characteristics.

  2. Reporting cells (or reporting centers). [31] In this approach, a subset of the cells is designated as the only one from which an endpoint's location may be updated. When an endpoint needs to be located, a search is conducted in the vicinity of the reporting cell from which the most-recent update was generated. In Bar-Noy and Kessler, [32] the problem of which cells should be designated as reporting cells so as to optimize a cost function is addressed for various cell topologies.

The principal drawback to static update strategies is that they do not accurately account for user mobility and frequency of incoming calls. For example, although a mobile endpoint may remain within a small area, it may cause frequent location updates if that area happens to contain a reporting cell.

15.6.2 Location Update Dynamic Strategies

In a dynamic update strategy, an endpoint determines when an update should be generated, based on its movement. Thus, an update may be generated in any cell. A natural approach to dynamic strategies is to extend the static strategies to incorporate call and mobility patterns. The dynamic location area strategy proposed in Xie and coworkers [33] dynamically determines the size of an endpoint's location area according to the endpoint's incoming call arrival rate and mobility. Analytical results presented in Xie and coworkers [34] indicate that this strategy is an improvement over static strategies when call arrival rates are dependent on user or time. The dynamic reporting centers strategy proposed in Birk and Nachman [35] uses easily-obtainable information to customize the choice of the next set of reporting cells at the time of each location update. In particular, the strategy uses information recorded at the time of the endpoint's last location update, including the direction of motion, to construct an asymmetric distance-based cell boundary and to optimize the cell search order. In Bar-Noy and coworkers, [36] three dynamic strategies are described in which an end-point generates a location update: (1) every T seconds (time-based), (2) after every M cell crossings (movement based), or (3) whenever the distance covered (in terms of number of cells) exceeds D (distance based). Distance-based strategies are inherently the most difficult to implement because the mobile endpoints need information about the topology of the cellular network. It was shown in Bar-Noy and coworkers, [37] however, that for memoryless movement patterns on a ring topology, distance-based updating outperforms both time-based and movement-based updating. In Madhow and coworkers, [38] a set of dynamic programming equations is derived and used to determine an optimal updating policy for each endpoint, and this optimal policy is in fact distance-based. Strategies that minimize location-tracking costs under specified delay constraints (i.e., the time required to locate an endpoint) also have been proposed. In Rose and Yates, [39] a paging procedure is described that minimizes the mean number of locations polled with a constraint on polling delay, given a probability distribution for endpoint locations. A distance-based update scheme and a complementary paging scheme that guarantee a predefined maximum delay on locating an endpoint are described in Akyildiz and Ho. [40] This scheme uses an iterative algorithm to determine the optimal update distance D that results in minimum cost within the delay bound.

In organizing the location database, one seeks to minimize both the latency and the overhead, in terms of the amount of storage and the number of messages required, in accessing location information. These are, in general, counteracting optimization criteria. Most solutions to the location database organization problem select a point, which is a three-way trade-off between overhead, latency, and simplicity. The simplest approach to location database organization is to store all endpoint identifier-to-address mappings in a single central place. For large numbers of reasonably mobile endpoints, however, this approach becomes infeasible in terms of database access time and storage space and also represents a single-point-of-failure.

The next logical step in location database organization is to partition the network into a number of smaller pieces and place a portion of the location database in each piece. Such a distributed approach is well suited to systems where each subscriber is registered in a particular area or home. With this organization, the location database in an area contains the locations of all endpoints whose home is that area. When the endpoint moves out of its home area, it updates its home location database to reflect the new location. The home location register (HLR) and visitor location register (VLR) schemes of emerging wireless cellular networks [41] are examples of this approach, as are the Mobile IP scheme [42] for the Internet and the GSM-based General Radio Packet Switching (GPRS) network for data transport over cellular networks. Studies [43], [44] have shown that with predicted levels of mobile users, signaling traffic may exceed acceptable levels. Thus, researchers have considered augmenting this basic scheme to increase its efficiency under certain circumstances. For instance, in Jain et al., [45] per-user caching is used to reuse location information about a called user for subsequent calls to that user, and is particularly beneficial for users with high call-to-mobility ratios (i.e., the frequency of incoming calls is much larger than the frequency of location updates). In Ho and Akyildiz, [46] "local anchoring" is used to reduce the message overhead by reporting location changes to a nearby VLR instead of to the HLR, thus increasing the location tracking efficiency when the call-to-mobility ratio is low and the update cost is high. As with most large organizational problems, a hierarchical approach provides the most general and scalable solution. By hierarchically organizing the location database, one can exploit the fact that many movements are local. Specifically, by confining location update propagation to the lowest level (in the hierarchy) containing the moving endpoint, costs can be made proportional to the distance moved. Several papers address this basic theme. In Awerbuch and Peleg, [47] a hierarchy of regional directories is prescribed where each regional directory is based on a decomposition of the network into regions. Here, the purpose of the i-th level regional directory is to enable tracking of any user residing within a distance of 2i. This strategy guarantees overheads that are poly-logarithmic in the size and diameter of the network. In Anantharam et al., [48] the location database is organized so as to minimize the total rate of accesses and updates. This approach takes into account estimates of mobility and calling rates between cells and a budget on access and update rates at each database site. In Badrinath and coworkers, [49] location database organization takes into account the user profile of an endpoint (i.e., the predefined pattern of movement for the endpoint). Partitions of the location database are obtained by grouping the locations among which the endpoint moves frequently and by separating those to which the endpoint relocates infrequently. Each partition is further partitioned in a recursive fashion, along the same lines, to obtain a location database hierarchy.

In the above strategies, the emphasis is on reducing update overhead, but it is equally important to reduce database access latency. One strategy for doing so is replication, where identical copies of the database are kept in various parts of the network so that an endpoint location may be obtained using a low-latency query to a nearby server. The problem here is to decide where to store the replications. This is similar to the classical database allocation [50] and file allocation [51] problems, in which databases or files are replicated at sites based on query-update or read-write access patterns. In Shivakumar and Widom, [52] the best zones for replication are chosen per endpoint location entry, using a minimum-cost maximum-flow algorithm to decide where to replicate the database, based on the calling and mobility patterns for that endpoint.

[23]Ramanathan S. and Steenstrup, M., A Survey of Routing Techniques for Mobile Communications Networks, 1996.

[24]Madhow, U., Honig, M.L., and Steiglitz, K., Optimization of wireless resources for personal communications mobility tracking, IEEE/ACM Trans. Networking, 3 (6), 698–706, 1995.

[25]Ramanathan S. and Steenstrup, M., A Survey of Routing Techniques for Mobile Communications Networks, 1996.

[26]Ketchum, J.W., Routing in cellular mobile radio communication networks, in Routing in Communication Networks, Steenstrup, M., Ed., Prentice-Hall, Englewood Cliffs, NJ, 1995.

[27]Mouly, M. and Pautet, M.B., The GSM system for mobile communications, M. Mouly, Palaiseu, France, 1992.

[28]Telecommunications Industry Association, Cellular radio telecommunication inter-system operation, TIA/EIA IS-41B, 1991.

[29]Mohan, S. and Jain, R., Two user location strategies for personal communications services, IEEE Personal Commun., First Quarter, 42–50, 1994.

[30]Markoulidakis, G.L. et al., Evaluation in LA planning in future mobile telecommunication systems, Wireless Networks, 1995.

[31]Bar-Noy, A. and Kessler, I., Tracking mobile users in wireless communications networks, IEEE Trans. Infor. Theory, 39 (6), 1877–1886, 1993.

[32]Bar-Noy, A. and Kessler, I., Tracking mobile users in wireless communications networks, IEEE Trans. Infor. Theory, 39 (6), 1877–1886, 1993.

[33]Xie, H., Tabbane, S., and Goodman, D.J., Dynamic location area management and performance analysis, Proc. 43rd IEEE Vehicular Tech. Conf., 1993, pp. 536–539.

[34]Xie, H., Tabbane, S., and Goodman, D.J., Dynamic location area management and performance analysis, Proc. 43rd IEEE Vehicular Tech. Conf., 1993, pp. 536–539.

[35]Birk Y. and Nachman, Y., Using direction and elapsed-time information to reduce the wireless cost of locating mobile units in cellular networks, Wireless Networks, 1 (4), 403–412, 1995.

[36]Bar-Noy, A., Kessler, I., and Sidi, M., Mobile users: to update or not to update?, Wireless Networks, 1 (2), 175–186, 1995.

[37]Bar-Noy, A., Kessler, I., and Sidi, M., Mobile users: to update or not to update?, Wireless Networks, 1 (2), 175–186, 1995.

[38]Madhow, U., Honig, M.L., and Steiglitz, K., Optimization of wireless resources for personal communications mobility tracking, IEEE/ACM Trans. Networking, 3 (6), 698–706, 1995.

[39]Rose, C. and Yates, R., Minimizing the average cost of paging under delay constraints, Wireless Networks, 1, 211–219, 1995.

[40]Akyildiz, I.F. and Ho, J.S.M., A mobile user location update and paging mechanism under delay constraints, Proc. of ACM SIGCOMM, Cambridge, Massachusetts, 1995, pp. 244–255.

[41]Mohan, S. and Jain, R., Two user location strategies for personal communications services, IEEE Personal Commun., First Quarter, 42–50, 1994.

[42]IETF Mobile-IP Working Group, IPv4 Mobility Support, Working draft, 1995.

[43]Meier-Hellstern, K. and Alonso, E., The use of SS7 and GSM to support high density personal communications, Proc. ICC, 1992, pp. 1698–1702.

[44]Lo, V.N., Wolf, R.S., and Bernhardt, R.C., Expected network database transaction volume to support personal communications services, 1st International Conference Universal Personal Communications Services, Dallas, 1992.

[45]Jain, R. et al., A caching strategy to reduce network impacts of PCS, IEEE J. Selected Areas Commun., 12 (8), 1434–1444, 1994.

[46]Ho, J.S.M. and Akyildiz, I.F., Local anchor scheme for reducing location tracking costs in PCNs, Proc. ACM MOBICOM, Berkeley, California, 1995, pp. 181–194.

[47]Awerbuch, B. and Peleg, D., Concurrent online tracking of mobile users, Proc. ACM SIGCOMM, Zurich, Switzerland, 1991, pp. 221–234.

[48]Anantharam, V. et al., Optimization of a database hierarchy for mobility tracking in a personal communications network, Perform. Eval., 20, 287–300, 1994.

[49]Badrinath, B.R., Imielinski, T., and Virmani, A., Locating strategies for personal communication networks, Proc. Workshop on Networking of Personal Communications Applications, 1992.

[50]Ozsu, M.T. and Valduriez, P., Principles of Distributed Systems, Prentice-Hall, Engle-wood Cliffs, NJ, 1991.

[51]Dowdy, L.W. and Foster, D.V., Comparative models of the file allocation problem, ACM Comput. Surv., 14 (2), 287–313, 1982.

[52]Shivakumar, N. and Widom, J., User profile replication for faster location lookup in mobile environments, Proc. ACM MOBICOM, Berkeley, California, 1995, pp. 161–169.




Wireless Internet Handbook. Technologies, Standards and Applications
Wireless Internet Handbook: Technologies, Standards, and Applications (Internet and Communications)
ISBN: 0849315026
EAN: 2147483647
Year: 2003
Pages: 239

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net