SUBMITTED BY:
M.GUNASEKARAN

---

[attachment=10359]
A Dynamic Approach to Location Management in Mobile Computing Systems
Abstract:
Managing location information of mobile nodes is an important issue in mobile computing systems. There is a trade-off between location update effort (when a node moves) and node finding effort. In this paper we present a dynamic location management strategy that has the following features: all location servers need not maintain location information about every mobile node, a coterie based approach is adopted for location update and find, every node move does not result in location updates, location updates are done at a subset of location servers, a subset of location servers are queried when a mobile node is to be located, the set of location servers, corresponding to a mobile node, for location update and find operations is dynamic, the dynamic nature of these sets helps alleviate situations of heavy burden on some location servers, when a large number of mobile nodes are concentrated in a small geographical area. Thus, location management is done recently, and responsibility is shared fairly among location servers.
Keywords: mobile computing, location management, hashing.
1. Introduction:
The ability of mobile hosts (MHs) to autonomously move from one part of the network to another part in a mobile computing system, sets it apart from static networks. Unlike static networks, the network configuration and topology keep changing in mobile computing systems. The mobility of some nodes in the network raises interesting issues in the management of location information of these nodes. Creating a fixed location directory of all the nodes a priori is not a solution. The location directory has to be dynamically updated to account for the mobility of the MHs. The design of a location directory whose contents change dynamically raises important issues. Some of them are as follows:
(i) When should the location directory be updated? If the updates are done each time an MH's location changes, the directory will always have the latest location information, reducing the time and effort in locating an MH. However, such a policy imposes a heavy burden on the communication network and the location servers,
i:e:, nodes that maintain the directory.
(ii) Should the location directory be maintained at a centralized site, or should it be distributed? A central location server has problems with regard to robustness and scalability. Hence, a distributed directory server is preferable. This leads us to the next questions.
(iii) How should the location information be distributed among the location servers? and
(iv) Should location information about an MH be replicated across multiple location servers? It is not possible to a priori determine the variations in spatial distribution of MHs in the network, and the frequency with which node location will be updated or queried. Hence, a location management strategy should address issues (iii) and (iv) so as to ensure fair distribution of responsibility among all the location servers, and be scalable.
In this paper we propose a location management strategy in which the location directory is distributed among nodes in the static network, such that all the location servers share the responsibility fairly. Also, fluctuations in query rates of mobile hosts is accounted for, so that no location server is unduly burdened. Section 2 describes the model of the mobile computing system that is assumed in the rest of the paper. In Section 3, previous work on location management is described. Some of the inadequacies of the previous schemes, which motivate our work, are enumerated in Section 4. In Section 5, we present the basic idea behind the proposed location management strategy. The data structures, and the algorithm for this strategy are presented and described in Section 6. Section 7 describes how the location servers are selected for location updates and queries. In Section 8, we describe how the location management strategy handles fluctuations in location query rates of mobile hosts. The performance of the strategy is analyzed in Section 9, and the conclusion is presented in Section 10.
2. System Model:
We assume a cellular communication system that divides the geographical region served by it into smaller regions, called cells. Each cell has a base station, also referred to as the mobile service station (MSS). Figure 1 shows a logical view of a mobile computing system. The mobile service stations are connected to each other by a fixed wire network. A mobile service station can be in wireless communication with the mobile hosts in its cell. The location of a mobile host can change with time. It may move from its present cell to a neighboring cell while participating in a communication session, or it may stop communicating with all nodes for a period of time and then pop-up in another part of the network
. A mobile host can communicate with other units, mobile or static, only through the mobile service station of the cell in which it is present. If a node (static or mobile) wishes to communicate with a mobile host, first it has to determine the location of the MH (the cell in which the MH is currently residing). This location information is stored at location servers. Depending on the frequency of location updates, this location information may be current, or out-of-date. Once the location of the MH has been determined, the information is routed through the fixed wire network to the MSS of the cell in which the MH is present. Then the MSS relays the information to the destination MH over a wireless channel. We
assume that MSSs act as location servers. Hence, all the MSSs collectively maintain the location directory.
3. Previous Work
Updating the location directory each time an MH moves from one cell to another can be very expensive. Three alternatives, namely, time-based, number of movements-based, and distance-based strategies for directory updates have been proposed in [3]. The location updates are done less often, and impose lower overheads. A simple solution to location tracking is to have a centralized location server. However, if the node maintaining the directory crashes, location information about all the nodes becomes inaccessible. Also, a centralized directory is unable to exploit the geographical distribution of MHs in the system, and locality of reference patterns to minimize the cost of directory update and query operations. The locality of reference patterns is exploited in [7]. The notion of working set for mobile hosts is introduced. Nodes in an MH's working set communicate with the MH more frequently than nodes that are not in the working set. A location management scheme has been described in [7] in which an MH can dynamically determine its working set depending on the call-to-mobility ratio between network node and MH pairs. Nodes in the working set are informed about the location update when an MH moves, while other nodes are made to search for the MH when they wish to communicate with the MH. In [2], some MSSs are designated as reporting centers (similar to location servers). Location update is done when an MH moves into the cells corresponding to the reporting centers. When an MH has to be located, it is searched for in the vicinity of the reporting center at which the last update was made. However, an issue that needs to be addressed is how such a reporting center is determined. One simple solution would be to probe all
reporting centers to determine the one with the latest update. However, this imposes high communication overheads on the fixed network. In [1], a hierarchy of distributed regional directories is maintained.
The ith level regional directory enables a node, static or mobile, to track any mobile host within a distance of 2i from it. Corresponding to each level i, read and write sets of nodes are associated with nodes u, v such that readi(u) \ writei(v) 6= _, 8u; v within 2i distance from each other. The write set for a node is the set of nodes where the location information of the node is stored. The read set for a node is the set of nodes that will be probed to find the location of a target node.
4. Motivation:
In all the schemes described above, even though the location directory is distributed across several MSSs, the responsibility of location tracking is not guaranteed to be shared equally. This is due to the following reasons:
1. The geographical distribution of MHs may change with time. Quite often a significant fraction of MHs are concentrated in a very small area, while there is a very low density of MHs in the rest of the network. For example, most of the MHs may be situated on the highways and other major streets of a city during the morning and evening rush- hour traffic, and most of the MHs may be concentrated in the business districts of the city during rest of the day. In such situations, the directory servers [1] and reporting centers [2] in the high density regions will be overburdened, while the directory servers and reporting centers in other regions will be comparatively lightly loaded.
2. Location of some MHs will be queried more often than others. So, even when the MHs are evenly distributed across the network, the location servers (directory servers in [1] and reporting centers in [2]) for these MHs will be queried more often, increasing their load. If the identity of such MHs were known a priori, appropriate actions could be taken to distribute the load. However, such is not the case. An MH that is hot (location queried frequently) may go cold (location queried infrequently), and vice versa. Hence, there is a need for a distributed location directory management scheme that can adapt to changes in geographical distribution of MH population in the network, and to changes in MH location query rate.
5 Basic Idea:
The problem at hand is as follows: given an MH, determine the location server(s) that will store the location of the MH. Storing the location information of an MH at only one MSS (serving as the MH's location server) is not desirable due to the following reasons:
1. MHs exhibit a spatial locality of reference: even though all nodes in the system can potentially communicate with the network, bulk of the references originates from only a subset of them (referred to as the working set in [7]). The nodes in the working set may be clustered in different parts of the network. So, to reduce query costs, it is advisable to have location servers for the MH in the vicinity of such clusters.
2. Multiple location servers for an MH make the distributed directory tolerant to the failure of some of these servers. So, let there be a function f : MH ! SMSS, which given the identity of an MH, determines the set of MSSs that are the location servers for that MH. However, using only the MH's identity to determine its location servers fails to exploit the locality of reference characteristics of mobile networks. Regardless of where the MH is located in the network, its location information will always be stored at the same nodes. Usually, an MH is more likely to be in communication with nodes in its vicinity, than with nodes at a greater distance. As a result the working set of an MH can change with its location. Therefore, associating a static set of location servers with each MH is not advisable. The above problem can be solved as follows: let there be functions (i) g’ : MH ! MSS, which maps an MH to the MSS of its current cell, and (ii) g’’ : MSS ! SMSS, which maps an MSS to a set of MSSs. Then, we can define a function g : MH ! SMSS to be equivalent to g’’(g’(MH)). Given an MH, function g determines the location servers of the MH based on the cell in which the MH is present. So, the location servers of an MH change as the MH's location changes. However, determining the location servers of an MH based solely on the cell in which that MH is present will lead to uneven distribution of responsibility. For example, when there is a high concentration of MHs in a cell, all these MHs will be mapped to the same
location servers which will be overburdened. Hence, it is desirable that the location servers storing the location information of an MH be a function of the identities of the MH as well as the cell in which that MH is present. Such a function can be represented as follows: h : MSS _ MH ! SMSS. The location servers corresponding to an MH will change as the MH moves in the network. Also, MHs in the same cell need not have the same set of location servers. Nodes that wish to locate an MH should be able to access at least some of the location servers of the MH quickly, and in an inexpensive fashion. Broadcasting a query to the entire network is an expensive solution. Function h, described above, can also be employed to determine the set of location servers that should be queried when an MH is to be located.
The set h(MSS;MH) can represent the set of MSSs that a node, in the cell represented by MSS, should query when it wishes to locate a mobile host MH. Thus, function h determines the write set for location updates when an MH moves, and the read set for querying the location of the MH. A naive implementation of the function h would be to have a look-up table with an entry for each (MH, MSS) pair. Each entry would store the corresponding SMSS. The size of such a table will be large as there are a large number of MHs in a mobile computing system. Even if the location directory were to be distributed across all MSSs, each MSS would have to store its share of the look-up table, having as many entries as the number of MHs in the system. In order to avoid the storage overheads incurred by such a table, there is a need for function h to be computationally inexpensive, mapping (MH, MSS) pairs to SMSS. It will
be desirable if the mapping is distributed over the range of MSSs, for fairness. MHs that are hot will have their locations queried more frequently than other MHs. Nodes querying the locations of hot MHs may be spread all over the network. Therefore, a greater number of location servers, spread throughout the network, should maintain location information about hot MHs. Fewer location servers need to maintain location information about cold MHs. For this purpose, alias (es), referred to as virtual MH identity, are assigned to each MH. A hot MH is assigned multiple virtual identities, while a cold MH is assigned a single virtual identity, i.e., the location management scheme considers a hot MH to be equivalent to multiple cold MHs. Determination of location servers for an MH involves three steps: