17.2 Location Resolution and Management Techniques in Pervasive Computing Applications
17.2 Location Resolution and Management Techniques in Pervasive Computing Applications
To understand the functionality needed in any universal location-management architecture, it is helpful first to evaluate the various proposed application scenarios. It will become evident that these applications not only have differing performance requirements, but also exhibit significant diversity in the technologies that they use to obtain and track location information. Given the abundance of work in this area, we focus only on a selective subset that illustrates the main requirements and challenges.
17.2.1 IP Mobility Support Over Cellular Systems
Wireless cellular networks offer the best example of location-management protocols for location-independent computing. The cellular architecture employs a two-level hierarchy for tracking the location of a mobile device as it roams across the cellular network, and redirects traffic to and from the mobile node's current point of attachment. The entire network is partitioned into a number of distinct registration areas (RA), with a home mobile switching center (HMSC) handling all the incoming and outgoing calls for the mobile terminals that are homed in its registration area. Each registration area has a database, called the visiting location register (VLR), which stores the precise location of all mobiles currently resident in that RA. A pointer to the current VLR of a mobile terminal is held at the home location register (HLR), located in the home registration area of the mobile terminal. The first level of mobility support is provided by having the HMSC redirect all arriving calls (after appropriate query resolution via the HLR and VLR) to the mobile switching center (MSC) serving the current point of attachment of the mobile node.
Because each RA comprises several cells, we need additional location-management techniques to identify the precise cell in which the mobile node is currently resident. The resolution of the mobile node's (MN) precise cell of attachment is performed using two complementary techniques, viz., (1) location update or registration, and (2) paging. Location update refers to the process by which the mobile node proactively informs the network element (the MSC) of its current position (or other information, such as future locations). Conversely, paging is the process by which the network element (MSC) initiates a search for the MN in all cells where the mobile has a nonzero residence probability. There has been a significant amount of research on improved paging and location update strategies, such as the use of distance-based location update strategies or selective paging mechanisms. [3]
The introduction of packet-based data services over cellular networks and the predicted move toward IP-based fourth-generation (4G) cellular networks have resulted in several efforts to introduce protocols for IP-based mobility support. Mobile IP [4] is the current standard for IP-based mobility management and provides ubiquitous Internet access to an MN without modifying its permanent IP address. Two entities analogous to HLR and VLR, namely, the home agent (HA) and the foreign agent (FA), are used to tunnel packets addressed to this permanent address to the MN's current point of attachment. The base Mobile IP protocol, however, suffers from several drawbacks, such as high signaling latency, in the absence of a hierarchical infrastructure. Accordingly, several protocols, such as cellular IP, HAWAII, or IDMP, have been recently proposed for introducing a location-management hierarchy in IP networks and thereby providing more scalable intradomain mobility support. [5]
All these schemes express the location of the MN in symbolic form: the MN location is essentially expressed in terms of the ID (e.g., IP address of the FA or the MSC identifier) of the network element to which it is currently attached. Location update and paging schemes operate on this symbolic representation of location; for example, popular paging strategies consist of a sequential search for an MN over a list of cell IDs. The cellular network illustrates the design of a global location resolution framework that combines hierarchical call and packet redirection with suitable paging and registration mechanisms. Of course, the use of such symbolic location information implies that the location of an MN is resolved only up to the granularity of the individual cell or subnet of attachment. In Section 17.4, we shall discuss the design of a provably optimal location-management algorithm, which uses such symbolic location information to establish optimal paging and location update strategies.
17.2.2 Mobile Information Services
Location-aware mobile information services are often touted as the "killer application" for the first generation of ubiquitous computing. These services are typically based on an information service infrastructure that retrieves the current location of a mobile device, and then provides the device with information and resources that are local to the MN's current location. The primary aim of such services is not to track individual users, but to ensure that a specific network resource is available to users who are currently "close" to the resource.
One example of this service is the Traveller Information Service being developed as part of the Advanced Traveler Information Systems (ATIS) initiative for smart highways in several countries (e.g., TravTek in Orlando, SMART Corridor in Santa Monica, and CACS in Japan). We outline the example of Genesis, [6] a fairly comprehensive system under development at the University of Minnesota for the Minneapolis-St. Paul area. The ATIS server in the Genesis system maintains the master database, with each road segment associated with a start and end node in the database. Nodes are essentially named objects with location attribute (x,y) coordinates expressed in geographical coordinates. Active databases are used with proper choice of triggers, such as traffic congestion, accidents, road hazards, and constructions and detours, to support a wide range of spatially correlated queries. Due to the geometric representation of location information, the local environment of a user is defined using simple spatial queries.
The Cyberguide Project at Georgia Tech [7] is an effort to develop an electronic tourist guide for both wide area and local environments (such as a building). The Cyberguide architecture uses explicit GPS-based positioning for outdoor environments and infrared-based positioning for indoor environments; the indoor location resolution technology does not scale well to large coverage areas. Lancaster University's GUIDE project [8] is another experimental prototype of local information services. It uses a cellular network arrangement, with IEEE 802.11 LANs providing short-range coverage within a single cell. By making the coverage areas deliberately discontinuous, GUIDE ensures that each cell caters only to mobile nodes within a specific zone. Because GUIDE simply broadcasts zone-specific information from a Linux-based cell server to all nodes within the corresponding zone, the system does not require any explicit location or positioning support and does not need to track the movement of individual nodes.
17.2.3 Tracking Systems
Tracking applications differ from mobile information services in that they typically focus on the ability to continuously monitor the location of a mobile device. Present-generation tracking applications typically run as global services, where the location of the mobile nodes must be distributed over wide area networks. Fleet management applications are the most-obvious examples of present-day tracking systems. Most commercial fleet management systems (e.g., Qualcomm's OmniTRACS product) are based on the GPS technology, which provides the absolute location of a mobile device (relative to a geographical coordinate system) at varying levels of precision. Location update schemes in such systems employ dead reckoning, whereby the location information is extrapolated by the system based on velocity information; new updates are generated when the mobile object deviates from its predicted position by a distance threshold. A digital map database is maintained in a manner quite similar to that of ATIS, i.e., using path segments and nodes, along with their x,y coordinates. Depending on need, a portion of this database may be replicated in the memory of the on-board computers. Dynamic attributes and their indexing, spatio-temporal query languages, and uncertainty management are special features of such databases.
The Federal Communication Commission's (FCC) E911 initiative has made it mandatory for wireless cellular service providers to track the location of phones making emergency 911 calls. While GPS information provides the easiest way of determining location, most cell phones do not possess such technology. The location of a mobile user in such environments is often determined, typically in geographical coordinates, by triangulation technologies based on the relative signal strength of the cellular signal at multiple base stations. While GPS is indeed a popular technology for resolving location, it is applicable only to outdoor computing environments. Due to this limitation, as well as the fact that GPS technology cannot be embedded or is not available in all computing devices, GPS data cannot be used as the basis of a universal location representation scheme. Recently, several innovative research prototypes have focused on the problem of location tracking in indoor environments.
An example of such a research prototype is the Active Badge project, [9] originally conceived at the Xerox Palo Alto Research Center. Active badges are low-cost, low-power infrared beacon-emitting devices worn by employees in an office environment. Sensors are distributed in a pico-cellular fashion within the building, and the location of a badge is determined primarily by the identity of the sensor that reports the badge within its vicinity. Location management and paging algorithms are used to track the user's location, which is essentially expressed in symbolic form (based on the IDs of the neighboring sensors). While the infrared technology used in active badges can resolve device location up to the granularity of individual rooms, additional technologies are needed for finer location resolution. For example, Active Bats [10] have been developed to track both position and movement using ultrasonic technology; this approach can be considered the indoor analog of GPS because it expresses location in geometric coordinates. Follow-me applications in pervasive collaborate workspaces require such fine-grained location information; such applications also need efficient location prediction to ensure that computing and communication resources are available to a mobile device in an uninterrupted fashion.
Several other research prototypes have exploited alternative radio technologies for indoor location tracking. For example, MIT's Cricket Location Support System [11] requires the mobile devices to proactively report their locations. Such mobile devices use sophisticated triangulation mechanisms that monitor both RF and ultrasound signals emitted from wall- and ceiling-mounted beacons to resolve their geographical location information. Microsoft Research's RADAR system, [12] on the other hand, uses signal-to-noise ratio and signal strength measurements of IEEE 802.11 wireless LAN radios to resolve the location of indoor mobile nodes to a granularity of approximately 3-to-5-meter accuracy. While the accuracy of the resolution can suffer due to changes in the indoor layout (such as the moving of metal file cabinets), the approach offers the advantage of location resolution that piggybacks on the wireless networking infrastructure and does not require the extensive installation of new devices/radios. Pinpoint's 3D-ID performs indoor position tracking at 1-to-3-meter resolution using proprietary base station and tag hardware in the unregulated ISM band (also used by 802.11 LANs) to measure radio time of flight.
Research prototypes have also used alternative techniques for monitoring user location. Electromagnetic sensing techniques (e.g., Raab et al. [13]) generate axial magnetic-field pulses from a transmitting antenna in a fixed location and compute the position and orientation of the receiving antennas by measuring the response in three orthogonal axes to the transmitted field pulse, combined with the constant effect of the Earth's magnetic field. While they offer up to 1-mm spatial resolution, they suffer from limited tracking distances and steep implementation costs. Research projects also have used stereovision (e.g., Microsoft's Easy Living [14] project for indoor home environments) or ubiquitous pressure-sensing (e.g., Georgia Tech's Smart Floor proximity location system [15]) techniques to resolve the location of people in indoor environments. While such techniques may not be deployed universally, they do illustrate how the use of diverse location resolution and management techniques is a basic reality of pervasive computing architectures.
17.2.4 Additional Techniques
We have recently witnessed research efforts in ad hoc location sensing, where user location in wireless environments is estimated without the use of static beacons or sensors that provide a fixed frame of reference. Mobile nodes in such ad hoc environments essentially act as peers, sharing sensory information with one another to progressively converge on a true representation of device location. Doherty et al. [16] have presented an algorithmic approach to this problem, as well as a framework for describing error bounds on the computed locations.
Another interesting area of location management research is sensor fusion, where the location information is obtained by simultaneously aggregating information from multiple hierarchical or overlapping sensing technologies. By integrating location tracking systems with different error distributions, we can often provide increased accuracy and precision beyond the capabilities of an individual system. An example of such fusion can be found in multisensor collaboration robot localization problems (e.g., Fox et al. [17]), where information from multiple sensors (such as ultrasonic and laser rangefinders, cameras, etc.) is integrated using Bayesian or Markovian learning techniques to develop a "map" of a building.
Table 17.1 shows a selective list of the location-management techniques employed in various pervasive computing contexts. We can see that location management prototypes use both geometric and symbolic representations to resolve, track, and predict the location of mobile devices.
| Product/Research Prototype | Primary Goal | Underlying Physical Technology | Techniques Employed | Location Representation |
|---|---|---|---|---|
| Cellular voice | Continuous global connectivity for mobile users | GSM, IS-95, IS-51, NA-TDMA, CDMA-2000, WCDMA (forthcoming for 3G) | Location updates, paging, HLR/VLR | Symbolic |
| Internet (IP) mobility | Roaming support for mobile nodes | Any technology supporting IP tunneling | HA/FA, packet tunneling | Symbolic |
| Genesis | Highway information services | GPS | Active databases, spatial queries | Geometric |
| GUIDE | Hot-spot information services | 802.11 WLAN | Disconnected cellular topology | Symbolic |
| OmniTracks | Outdoor fleet management | GPS | Dead reckoning, paging | Geometric |
| Active Badge | Indoor tracking | Infrared | Vicinity-based reporting | Symbolic |
| ActiveBats | Follow-me indoor computing | Ultrasonic | Location updates, paging | Geometric |
| Cricket | Indoor location tracking | RF and ultrasound | Location updates | Geometric |
| RADAR | Indoor location tracking | 802.11 WLAN | Triangulation, location updates | Symbolic |
| SmartFloor | Indoor user tracking | Foot pressure | Location updates | Geometric |
[3]Yong, V.W.S. and Leung, V.C., Location management for next-generation personal communications networks, IEEE Network, 14(5), 18–24, Sept.–Oct. 2000.
[4]Leonhardt, U. and Magee, J., Toward a general location service for mobile environments, Proc. Int. Workshop on Services in Distributed and Networked Environments, Macau, June 1996, pp. 43–50.
[5]Das, S. et al., IDMP: an intradomain mobility management protocol for next generation wireless networks, IEEE Wireless Commun. (formerly IEEE Personal Commun.), 9 (3), 38–45, 2002.
[6]Shekhar, S. and Liu, D., Genesis and Advanced Traveler Information Systems (ATIS): killer applications for mobile computing?, Proc. NSF MOBIDATA Workshop on Mobile and Wireless Information Systems, Rutgers University, NJ, Nov. 1994.
[7]Abowd, G.D. et al., Cyberguide: a mobile context-aware tour guide, ACM/Baltzer Wireless Networks, 3 (5), 421–433, 1997.
[8]Cheverst, K. et al., Experiences of developing and deploying a context-aware tourist guide: the GUIDE project, Proc. 6th Ann. Int. Conference on Mobile Computing and Networking, pp. 1–12, Aug. 1999.
[9]Want, R. et al., The Active Badge location system, ACM Trans. Inf. Syst., 10 (1), 91–102, 1992.
[10]Harter, A. et al., The anatomy of a context-aware application, Proc. 5th Ann. Int. Conference on Mobile Computing and Networking, pp. 59–68, August 1999.
[11]Priyantha, N., Chakraborty, A., and Balakrishnan, H., The Cricket location support system, Proc. 6th Ann. Int. Conference on Mobile Computing and Networking, Boston, pp. 32–43, Aug. 2000.
[12]Bahl, P. and Padmanabhan, V., RADAR: an in-building RF-based user location and tracking system, Proc. IEEE Infocom, IEEE CS Press, Los Alamitos, California, pp. 775–784, 2000.
[13]Raab, F. et al., Magnetic position and orientation tracking system, IEEE Trans. Aerospace Electron. Syst., 15(5), 709–718, 1979.
[14]Krumm, J. et al., Multi-Camera Multi-Person Tracking for Easy Living, Proc. 3rd IEEE Int. Workshop on Visual Surveillance, IEEE Press, Piscataway, NJ, pp. 3–10, 2000.
[15]Orr, R.J. and Abowd, G.D., The Smart Floor: a mechanism for natural user identification and tracking, Proc. Conference on Human Factors in Computing Systems, ACM Press, New York, 2000.
[16]Doherty, L. et al., Convex position estimation in wireless sensor networks, Proc. Infocom 2001, IEEE CS Press, Los Alamitos, CA, 2001.
[17]Fox, D. et al., A probabilistic approach to collaborative multi-robot localization, Autonomous Robots, 325–344, June 2000.
EAN: 2147483647
Pages: 239