Communications of the ACM
Home/Magazine Archive/March 2005 (Vol. 48, No. 3)/Delivering Real-World -biquitous Location Systems/Full Text
The disappearing computer
Delivering Real-World -biquitous Location Systems
Location-enhanced applications are poised to become the first real-world example of ubiquitous computing [10]. Here, we emphasize the practical aspects of getting location-enhanced applications deployed on existing devices, such as laptops, tablets, PDAs, and cell phones, without the need to purchase additional sensors or install special infrastructure. Our goal is to provide an overview of the practical considerations currently faced, and the research challenges that lie ahead. We ground the article with a summary of initial work on two deployments of location-enhanced computing: multiplayer location-based games and a guide for the Edinburgh Festival.
A large number of research and commercial location systems have been developed over the past two decades [7]. In general, these systems have one of two goals: providing highly accurate location estimates, on the order of centimeters, within a small area, or providing lower accuracy over a wide coverage area [8]. Systems with a focus on accuracy typically require both extensive infrastructure and relatively expensive sensors. AT&T Cambridge's Active Bats [1] system, for example, employs active ultrasonic badges and requires the installation of ceiling-mounted ultrasound receivers every square meter.
GPS is perhaps the most familiar example of a location system that provides wide-area coverage. GPS is truly ubiquitous, covering the entire Earth's surface by using a constellation of low-orbit satellites. Unfortunately, GPS coverage has limitations in practice. The radio signals sent by the GPS satellites are too weak to penetrate most buildings or pass through dense vegetation. This leads to the urban canyon effect experienced in cities, where GPS functionality is lost because buildings occlude signals, or scatter them in multipath reflections. As a result, GPS works well outdoors but provides little to no coverage indoors where people spend most of their time. Unsurprisingly, GPS has been the dominant location system in navigation and way-finding applications, but has seen little use in other application domains.
Another class of wide-area location technologies is provided by wireless phone service companies, and uses cell tower observations of cell phones to estimate a user's location. The European and U.S. governments have mandated that providers be able to locate cell phones being used to make emergency calls to within 100m. To meet this constraint, providers are experimenting with a variety of techniques, including sophisticated signal propagation models and augmentation of handsets with GPS. As the cell phone is the most ubiquitous computing platform, it is an excellent candidate for location-based service deployment.
Three concerns with cell phone-based location are accuracy, privacy, and cost. Unlike GPS, where the user's device only listens to satellites, cell phone-based location solutions currently compute the user's location in the infrastructure and relay it back to the user's phone. Implicitly, users must trust their service provider is protecting their location information, and not selling it or using it in other inappropriate ways. Second, while 100m may be accurate enough for rescue workers to find someone in an emergency, it may prove inaccurate for many location-based applications. Finally, cell phone providers are not giving location information to users for free; rather they are selling it for as much as $1 (U.S.) per location request. This also threatens to constrain the class of applications for which this location platform makes sense.
GPS is truly ubiquitous, covering the entire Earth's surface by using a constellation of low-orbit satellites. Unfortunately, GPS coverage has limitations in practice.
A final, interesting category of location systems uses ambient 802.11 signals to estimate a user's location. Microsoft Research's RADAR system showed that estimating location based on nearby 802.11 base stations can provide location estimates with 3m accuracy on standard laptops. In RADAR, an initial calibration is performed in which 802.11 readings are taken on a 1m grid, in effect creating a map of which access points can be realized. Location estimates are produced by comparing radio scans to this map to find the closest matching location. This approach has also been used in commercial products by Ekahau, Inc., and others. Unfortunately, these systems require extensive calibration and do not scale to cover large areas. Furthermore, the signal strength fingerprints can vary due to changes in the environment, such as weather or moved furniture, and are sensitive to variation across hardware. As a result, these 802.11-based location systems wind up somewhere in the middle of the accuracy/coverage spectrum, providing less accuracy and requiring less infrastructure than other indoor location systems, and better accuracy, but less coverage than GPS.
These example systems are representative of the wide variety and large number of ubiquitous location systems available today. On the whole, they rely on listening to radio frequency signals and interpreting their relative timing and/or signal strength. These systems are hampered by inherent technology problems such as limits on coverage, signal interference, and reliance on infrastructure, and by broader issues such as privacy concerns.
Toward Truly Ubiquitous Location Systems
Attempts have been made to alleviate many of the hurdles and disadvantages of today's wide-area location solutions. There are a number of variants of the basic GPS strategy that improve the accuracy and time-to-lock for GPS handsets. Both ground-based and satellite-based versions of differential GPS improve accuracy from 8m10m to 5m for a non-enhanced unit. GPS chipsets are being integrated into mainstream cell phones and PDAs, lowering cost and decreasing the users' barrier to entry. To help meet the E911/E112 requirements [6], cell phone manufacturers are now producing handsets that use a mix of location technologies. When GPS is not available, the locations of nearby cell towers are used to produce a coarse location estimate. Based on this coarse location, the phone can download the expected position of the satellites, allowing the handset to lock on to GPS much more quickly (on the order of seconds instead of a minute or more) when GPS does become available. By 2008 the European Union will deploy Galileo, a next-generation GPS system that promises greater accuracy and operation covering both indoors and out, due to stronger radio signals that should penetrate most buildings.
Place Lab is a research project that attempts to solve the ubiquity issues surrounding 802.11-based location estimation [11]. Like RADAR, Place Lab uses a device's embedded 802.11 interface, but does not rely on precalibrated fingerprints. Instead, it predicts location via the known positions of the access points detected by the device [9]. The positions of these access points are provided by a database cached on the same device; this cache in turn can be filled from a variety of access point databases created by universities, radio hobbyists, war driving, and WiFi clubs. The largest of these databaseswigle.netcontains nearly two million access point locations, providing reasonable coverage in many large cities in the U.S. and Europe. The most recent "World Wide Wardrive" suggests that mapping efforts may keep up with the rapid deployment rate of 802.11 access points (nearly 300,000 new access points were mapped over an eight-day period last June). A similar but more geographically limited approach to Place Lab was used in the Lancaster Tour Guide [4].
A problem for 802.11-based location systems is the lack of 802.11 in less populated areas. While many cities have near-ubiquitous 802.11 coverage, rural area coverage is close to zero. To address this, Place Lab uses GSM cell towers and fixed Bluetooth devices as well as 802.11 access points. The near perfect coverage in Europe and the rapid deployment of GSM in the U.S. gives Place Lab improved coverage; the small range of Bluetooth devices improves Place Lab's accuracy when they are available.
Due to the minor amount of calibration required, Place Lab's location estimates are less accurate than those produced by systems like RADAR. In residential and urban settings with GSM coverage and moderate 802.11 density, Place Lab produces location estimates with 20m25m of accuracy, almost a factor of 10 worse than systems that maintain a more detailed radio map. Interestingly, Place Lab's accuracy falls between the 8m10m GPS levels and the mandated 100m accuracy of cell phone-based location estimates.
More significantly, however, Place Lab matches the privacy model of GPS, where devices listen to radio frequency (RF) signals and compute location estimates autonomously rather than divulging their location to an infrastructure. Users can use the location information as they see fit, and divulge it only when they desire [2, 5]. Many services can be provided using cached information on the user's device such as maps and schedules. Of course, more dynamic data such as traffic conditions and arrival/departure times will still require a connection to a network.
Two Case Studies
We present two case studies to show both the challenges and opportunities in real-world deployment of a location-enhanced application. The first is a guide for the Edinburgh Festival that starts from a set of requirements and develops the necessary technology elements. The second is a location-based game that starts with a location technology, and incorporates and exploits the limitations of the technology to create game strategies.
Ubiquitous location systems are part of the design of a visitor guide to the Edinburgh Festivalthe largest arts festival in the world, with thousands of events taking place in hundreds of venues. The Kelvin Institute, in collaboration with Intel Research Seattle and the Edinburgh Festival's organizers, is undertaking research into systems that support the visitor experience in terms of events to attend, places to go, and information to read.
Edinburgh is an old city with many narrow streets and high buildings; its latitude of 55° northalmost as far north as Alaskaaccentuates the urban canyon effects that hamper GPS. Indeed, GPS alone is not a reliable location system here, primarily because of the urban canyon effects. To assess the viability of Place Lab as a location system to either replace or complement GPS, a pilot study was conducted. In the summer of 2004, a war driving survey of 802.11 coverage in the city center was made, and nine festival visitors were recruited for a study. Each carried a PDA running Place Lab during a day at the festival, and a camera to take photographs of routes and destinations. The photographs and Place Lab logs were used in post-visit interviews to better understand the availability and accuracy of positioning, and to inform system development. While analysis is ongoing, some preliminary results are available.
On average, one or more access points were detected 48% of the time, and Place Lab could provide an accurate location. Two or more access points were detected for only 22% of the time. Indeed, the overall detection rate increased from 48% to 69% when excluding periods of time visitors appeared to be indoors. It was also noted that three visitors had walked along one particular street at different times, where 28% of the access points were detected by just one or another of the three visitors and, on average, each of them detected 81% of the access points. Overall, the study suggested that in an old world city like Edinburgh, 802.11 density is far lower than that of U.S. cities. Location systems that use combinations of 802.11, GPS, and other sources of data, such as the newest release of Place Lab, seem highly appropriate for increasing location system availability and accuracy in such urban settings. Using multiple technologies also allows festival organizers to add further 802.11 and Bluetooth "beacons" where greater accuracy is needed. Such beacons need not provide network access, necessarily, since only their identification is needed for the purpose of positioning.
Location systems are not yet ubiquitous, but are increasing their accuracy, coverage, and availability, and maintaining moderate cost. A number of candidate technologies are already in the marketplace, and new ones are continually being developed.
In light of the variable and local availability of RF-based systems, some researchers are exploring a seamful design approach, taking advantage of the limits, gaps, and seams of RF-based systems for location and communication. One example is the Seamful Game [3], a mobile multiplayer game developed within the U.K.'s Equator project (www.equator.ac.uk) for PDAs with 802.11 and GPS. Two teams of players gain information from a server about the locations of periodically appearing coins and the locations of other players. They also receive updates of a map overlay showing WiFi signal strength, sampled by players as they play the game. To gain points, a player must get close to a coin (according to GPS), and then use a GUI Pickup command to pick it up. If in network coverage, the player can Upload the coin to receive points, or use the Pickpocket command to steal coins out of the PDAs of any nearby players. The game interface is shown in Figure 2.
The game has built-in tension between being in network coverage and being out. Coins often appear in areas where there is no coverage and poor GPS, but one needs network coverage in order to upload coins, get game points, and receive game state updates. However, when in coverage with a good GPS fix, one gives away one's location and becomes open to pickpockets. Initially, players are uncertain as to where there is coverage, but they can watch and talk to other players as they move, and use the 802.11 map overlay as they reveal sampled coverage to each other.
The Seamful Game has been played at the University of Glasgow, as well as demonstrated and evaluated at the Ubicomp 2004 and Mobile HCI 2004 conferences. A number of practical and environmental effects on RF became apparent in these trials. The game designers were surprised, for example, that rain, snow, and leaves on trees strongly affect WiFi and GPS. Even the angle of a PDA with regard to the player's body affects its performance. Metal located near 802.11 access points also varies the distribution of RF, for example, a truck parked in front of an access point was found to radically inhibit its coverage.
Lastly, communication gray zones are created by the differences between the antennae of access points and mobile devices, and by the different bit rates used for broadcasts and for data transmissions. The transfer of packets to and from access points can show significant asymmetry, and high packet loss can occur despite apparent network access.
Conclusion
Location systems are not yet ubiquitous, but are increasing their accuracy, coverage, and availability, and maintaining moderate cost. A number of candidate technologies are already in the marketplace, and new ones are continually being developed. Alongside the developments of such infrastructure, commercial and research-oriented applications are being developed in significant numbers. In the future, the development of new location systems is likely to be influenced by market trends in the hardware and software platforms of mobile devicesmost particularly cell phonesas much as the technology options within location systems themselves.
Privacy is clearly a major factor in location systems' development and deployment. Indeed, privacy remains contentious, as discussed in the article by Lahlou et al. in this section. There is a high demand from users for security, privacy, and trustworthiness, but the very features that enable location identification also contribute to the privacy problem. The architecture shared by Place Lab and GPS gives users a degree of control over when and how their locations are revealed. Nevertheless, networked applications will appear that request this location information from the user, suggesting that new techniques must be developed that extend the user's control beyond his or her own device.
Developers of applications will have to accept variation in the accuracy and availability of location data for some time. Fusing multiple sources of location data [9] will be a key attribute of location systems that can handle the range of environments in which mobile devices are used; for example, shifting from GPS data, used in open areas, to GSM, WiFi, and Bluetooth beacons indoors and in built-up areas. Place Lab and a number of other research projects are already responding to this challenge, and commercial location systems may need to adapt in order to meet users' expectations of accuracy. In order to construct and maintain comprehensive databases to support such systems, it is likely that further work is needed on generating database updates as a by-product of mobile devices' everyday use.
In addition, we see significant potential in deliberately showing some of the seams in the infrastructure of ubiquitous computing systems, going beyond the simple displays of signal strength in phones and laptops, to offer people maps of availability of WiFi coverage and location services. Again, such information may be gathered as a by-product of use, as in the Seamful Game, or by simulation [12]. Systems that expose the variable accuracy and availability of location systems should not be seen as standing in opposition to research aimed at improving accuracy and broadening availability. Instead, such approaches should be seen as complementary. We should offer pragmatic solutions for developers delivering real-world applications for widespread use, while we continue to improve, adapt, and evaluate the underlying technology of ubiquitous location systems.
References
1. Addlesee M., et al. Implementing a sentient computing system. IEEE Computer 34, 8 (Aug. 2001).
2. Cahill V., et al. Using trust for secure collaboration in uncertain environments. IEEE Pervasive Computing (JulySept. 2003).
3. Chalmers M., et al. Seamful design: Showing the seams in wearable computing. In Proceedings of the IEEE Eurowearable (Birmingham, U.K. Nov. 17, 2003).
4. Cheverst K., et al. Developing a context-aware electronic tourist guide: Some issues and experiences. In Proceedings of the SIGCHI Conference on Human Factors in Computing Systems (The Hague, The Netherlands, Apr. 2000).
5. Consolvo S., et al. Exploring user attitudes about location privacy. In Proceedings of the Workshop on Ubicomp Privacy: Current Status and Future Directions at the Sixth International Conference on Ubiquitous Computing (Nottingham, U.K., Sept. 2004).
6. Geer, D. The E911 dilemma. Wireless Business and Tech (Nov./Dec. 2001).
7. Hazas M., Scott J., and Krumm J. Location-aware computing comes of age. IEEE Computer 37, 2 (Feb. 2004).
8. Hightower J., and Borriello G. Location systems for ubiquitous computing. IEEE Computer 34, 8 (Aug. 2001).
9. Hightower J., and Borriello G. Particle filters for location estimation in ubiquitous computing: A case study. In Proceedings of the Sixth International Conference on Ubiquitous Computing (Nottingham, U.K., Sept. 2004).
10. Rao, B., and Minakakis L. Mobile commerce opportunities and challenges: Evolution of mobile location-based services. Commun. ACM 46, 12 (Dec. 2003).
11. Schilit B., et al. Ubiquitous location-aware computing and the "Place Lab" Initiative. In Proceedings of the First ACM International Workshop on Wireless Mobile Applications and Services on WLAN Hotspots (San Diego, CA, Sept. 2003).
12. Steed, A. Supporting mobile applications with real-time visualisation of GPS availability. In Proceedings of Mobile HCI. Springer, 2004.
Figures
Figure 1. Place Lab and GPS are compared in this approximately 1km loop through downtown Seattle. The user started at the bottom and moved in a counterclockwise direction around the loop. The red line is the series of location estimates based on WiFi access points with Place Lab. The blue line is the series of location estimates from a GPS receivernote the gaps in GPS coverage when the user rides a bus (on the right corner of the loop and heading North) and enters a large shopping area (at the top corner).
Figure 2. In the Seamful Game, a map overlay shows 802.11 signal strength as transparent squares of green and yellow, on top of a monochrome street map. The maps are built up over time from samples gathered during game play, and are made available as a resource for players' system use and development of game tactics.
©2005 ACM 0001-0782/05/0300 $5.00
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee.
The Digital Library is published by the Association for Computing Machinery. Copyright © 2005 ACM, Inc.
No entries found