17.3 Pervasive Computing Requirements and Appropriate Location Representation

17.3 Pervasive Computing Requirements and Appropriate Location Representation

The basic goal of pervasive computing is clear: develop technologies that allow smart devices to automatically adapt to changing environments and contexts, making the environment largely imperceptible to the user. However, the set of candidate applications and their underlying technologies is anything but uniform! Developing a uniform location-management infrastructure is thus a challenging task. We identify the following location-related features, which a universal architecture must support:

  1. Interoperability across multiple technologies and resolutions: Current prototypes for pervasive applications typically choose a specific location-tracking technology that is suitable for their individual needs. A uniform location-management architecture must be capable of translating the location coordinates obtained by such systems into a universal format, which can be utilized by various application contexts. For example, cellular land-mobile systems will primarily need to resolve the location of a mobile device only up to the point of network attachment. Fleet management and tracking applications may, however, require explicit geometric information. The mobility management infrastructure should be capable of efficiently translating such location information between different representations, and also at different granularities (e.g., mobile commerce applications advertising E-coupons may not be interested in the precise room in which a user is located inside a hotel).

  2. Prediction of future location: Predicting the user's future location is often the key to developing smart pervasive services. For example, the ATIS active database can be triggered more intelligently by predicting the most-likely routes, and by warning the client about adverse road conditions along those routes. Prediction of an individual's future position in an indoor office can be very helpful in aggressive teleporting (to support follow-me applications). In addition to this explicit service-oriented need for prediction, there is also an implicit need for predictive mobility tracking from the network infrastructure viewpoint. In several location-independent computing scenarios, the network must meet stringent performance and latency bounds as it ensures uninterrupted access to global information and services, even as the users change their location. For example, to provide quality-of-service (QoS) guarantees for multimedia traffic (such as video or audio conferencing) in cellular networks, appropriate bandwidth reservations must be made between the terminal and the serving base station (BS), as well as between the BS and the backbone network. To meet strict bounds on the handoff delay, the network also must proactively reserve resources at the cells where the mobile is likely to move. Because many of the tracking technologies do not themselves offer such predictive capabilities, the infrastructure must be capable of constructing such predictive patterns based on collective or individual movement histories.

  3. Location fusion and translation: In several pervasive computing scenarios, location tracking is achieved through the combination of multiple technologies and access infrastructures. For example, an office application can resolve the location of a user at different levels of granularity using different technologies. Thus, the specific building could be identified through the current wireless LAN cell where the mobile currently resides, whereas an additional ultrasonic system (such as Cricket [18]) may be used to identify the precise orientation and room location of the mobile user. Because the user's complete location reference is obtained only by combining these distinct location management systems, our global location-management framework must efficiently fuse and merge location information from two or more distinct network technologies.

    The intelligent management of vertical (or intersystem) handoff, on the other hand, often requires the ability to translate the mobility and location-related information from one frame of reference to another. For example, when a user switches from a wireless LAN to an overlaid PCS network, the network must be able to translate the mobility patterns and location-prediction attributes from one system to the other, independent of the representation format imposed by each individual system.

  4. Scalable and near-optimal signaling traffic: The desire for efficient and provably optimal location update and paging strategies is not new; there has indeed been a great deal of work on efficient location-management strategies, especially for cellular systems. The pervasive world will however see a quantum jump in the number of mobile nodes (from millions of cell phones to billions of autonomous pervasive devices) and an even greater variation in the capability (such as power or memory constraints) of individual devices. We must therefore develop efficient and near-optimal signaling mechanisms that minimize any unnecessary signaling load on both the devices and the networking infrastructure.

  5. Security and privacy of location information: Security and privacy management are key challenges in pervasive networking environments; notwithstanding the availability of advanced devices and location-resolution technologies, users will not embrace a pervasive computing model until a scalable infrastructure for appropriately protecting such location information is in place. The problem is not one of simply making such location information either visible or invisible to specific networks; we must allow the user to dynamically configure the scope of location visibility, possibly in multiple representation formats, to individual pervasive services and applications. For example, a user may wish to expose his precise GPS coordinates to emergency response applications (such as 911), but only a much coarser view (perhaps at a granularity of 20 miles2) to insurance companies trying to monitor his driving profile. Alternatively, the user may specify his network point of attachment (symbolic information), but not his precise in-building location (geometric coordinates) to a pervasive enterprise application.

17.3.1 Geometric or Symbolic Representation?

While different pervasive location tracking and management systems resolve the location of a mobile node at different granularities, they can all be classified into two classes [19] (as per the taxonomy of Leonhardt and Magee [21]) based on the way in which they represent the location information of a mobile device:

  1. Geometric: The location of the mobile object is specified as an absolute n-dimensional coordinate, with respect to a geographical coordinate system that is independent of the network topology. The most-common form of geometric data representation in location-aware computing systems is the use of GPS data, which resolves the latitude and longitude of a mobile on the earth's surface using a satellite-based triangulation system.

  2. Symbolic: The user location data is specified not in absolute terms, but relative to the topology of the corresponding access infrastructure. This form of representation is in widespread use in current telecommunications networks. For example, the PCS/cellular systems identify the mobile phone using the identity of its serving MSC; in the Internet, the IP address associated with a mobile device (implicitly) identifies the subnet/domain/service provider with which it is currently attached.

The choice between a geometric and symbolic representation is one of the fundamental decisions in the development of a universal location-management architecture. We believe that the symbolic representation is the preferred form, primarily due to its structured nature. The main advantage of geometric representation is that it is invariant: because the location information is an intrinsic property of the mobile device, it can be uniformly interpreted across heterogeneous environments, and does not depend on the topology of the associated networks. In spite of this seeming attractiveness, geometric representation is not appropriate for a universal location-management infrastructure. For one thing, the same reference coordinate system is not universally applicable. As an example, GPS may be appropriate outdoors but does not apply indoors, where ultrasonic or infrared-based indoor positioning systems may use different location coordinates. Moreover, we have demonstrated how different pervasive applications and environments require the location of a mobile device at different levels of granularity. Thus, while GPS information may be accurate up to 5-m resolution, certain in-room pervasive applications may require tracking at submeter resolutions. Because we cannot practically mandate the universal deployment of a technology that provides location at the finest granularity (the tracking costs would become prohibitive), we must allow for the coexistence of different networks and access technologies, providing location information at varying resolutions. Finally, geometric location-resolution technologies are inapplicable to a large category of pervasive devices, which may not possess location-resolution hardware (such as GPS devices) due to restrictions on cost and form factors. In contrast, symbolic location information (such as the point of attachment to the network) can be obtained solely from the capabilities of the infrastructure.

Our preference for the symbolic form of location representation is based on the observation that most location-independent applications, and a significant number of location-aware ones, are interested primarily, not in the absolute location of the mobile device, but only its position relative to the networking infrastructure. More importantly, the location-independent applications are typically global in scope and cut across multiple network and access technologies. Accordingly, scalability concerns for the location-management infrastructure apply primarily to the location-independent component of the pervasive application space. The interaction between mobile devices and applications that require the explicit geometric location of such devices (such as map-based interactions), is often local and restricted to the access network. It thus makes sense to base the universal infrastructure on the symbolic representation, allowing each access network to make the appropriate translation to geometric coordinates whenever necessary (rather than the reverse). For example, consider applications such as wireless Internet access that need to resolve the location of a mobile device only up to the granularity of the point of attachment. Even apparently location-aware services, such as the Electronic Tourist Guide, are really interested in knowing the user's location relative to the access infrastructure; a museum information system needs to know only the current access point serving the mobile visitor to provide appropriately tailored local content. Similarly, follow-me applications are primarily interested in predicting the device's future point of attachment (rather than its absolute position), because the final objective is to make advance reservations on the network path to the future point of attachment. Furthermore, location data is much more amenable to database storage and retrieval if it is a named object — such an object hierarchy is possible only when location data is expressed in symbolic form relative to other objects. Because an object hierarchy also simplifies the computational burden associated with multiresolution processing, the translation of location data across different systems and location databases is more efficient when stored in symbolic format.

Of course, we must not lose sight of applications, such as dynamic floor maps, which do need geometric location information. Geometric coordinates are clearly better suited for answering spatial queries related to physical proximity and containment (e.g., is my device physically located within a designated building?). As stated earlier, we believe that such specialized geometric queries (e.g., directions to the nearest ATM or restroom facilities) typically involve "local" resources and interact with server applications lying within the access domain, especially in pervasive environments where access networks will have considerably greater intelligence. In the future, a user currently located on a street in New York City is likely to obtain the location of the nearest ATM from a local tourist-guide server, rather than relay his request back to a mapping software located on a server in San Francisco. While such queries may need to express location in geometric form, it is better to obtain such information either from "local" access-specific technologies, or by appropriate mapping from the universal symbolic location format. It is important also to not lose sight of the fact that many pervasive applications generate queries related to topological proximity and containment, where the query issuer is interested in resources relative to the network topology (i.e., which is the closest [fewest hops or least congested] video server? or, does this printer belong to the research division?). Thus, both geometric and symbolic representations appear to be equally balanced from a query suitability standpoint, with the geometric format better suited to spatial queries and the symbolic one more appropriate for topological queries.

The hierarchical nature of communication networks implies the imposition of a logical hierarchy on the symbolic location representation (which expresses location relative to the network layout) as well. As an example, we will consider an IEEE 802.11 wireless LAN infrastructure at a university campus, which is overlaid by the wide area cellular PCS infrastructure. For the sake of simplicity, we assume that each PCS cell consists of multiple 802.11 LANs. [22] We can then construct a symbolic positional hierarchy based on the coverage area of each technology, which yields the neighborhood graph shown in Figure 17.1. The top level (corresponding to the cellular network) has eight zones, a, b, c, d, e, f, g, h, connected by neighborhood relationship as in the graph shown next to it. The second level zones which correspond to the 802.11 LANs may be named al, a2, ...; bl, b2, ...; cl, c2, ..., where al, a2, ... are subzones in the zone a and so on.

click to expand
Figure 17.1: A hierarchical map and its top-level graph representation.

We now focus on evaluating the suitability of using symbolic information to satisfy the five requirements enumerated at the beginning of this section. We have already seen how symbolic information is better suited to requirement 1, because it does not need any special support from the wireless access technology. In the rest of this chapter, we focus on features 2 and 4, showing how we can develop a path-based location-prediction algorithm (based on symbolic representation) that is provably optimal for stationary mobility patterns. While we are currently working on requirement 3, the issue of configurable universal location security and privacy, although a very interesting problem area in itself, is essentially beyond the scope of this chapter. However, symbolic location should clearly be more amenable to location privacy; because the user location is specified only relative to the topology of the network infrastructure, precise location of a mobile node is not possible without a knowledge of the physical network topology.

[18]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.

[19]There is also the semisymbolic (or hybrid) model, [20] which essentially consists of both geometric and abstract (symbolic) representations. While such a model is more expressive, it suffers from the same drawbacks as the geometric one (the main problem being the need for location-specific hardware on the pervasive device itself).

[19]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.

[21]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.

[22]Of course, in general, algorithms for storing and manipulating such symbolic information must allow for hierarchies with partial or incomplete overlap (e.g., a WLAN may span multiple PCS cells).

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