[FoRK] /. [Wireless Positioning]

Eugen Leitl eugen
Tue Oct 4 09:32:58 PDT 2005


Link: http://slashdot.org/article.pl?sid=05/10/04/1418206
Posted by: CmdrTaco, on 2005-10-04 15:47:00

   An anonymous reader writes "This Intel-written whitepaper introduces a
   way to [1]determine location with the aid of freely accessible, nearby
   radio sources, such as fixed Bluetooth devices, 802.11 access points,
   and GSM cell towers. Basically, the device reads the IDs of these
   local 'radio beacons' (each of which has a unique or semi-unique ID),
   looks up their positions in a locally-cached database, and performs a
   computation akin to triangulation. Intel created [2]Place Lab in an
   effort to satisfy the emerging requirement for location-awareness
   within mobile devices such as smartphones, PDAs, and laptops, or even
   moving vehicles. According to the whitepaper, over four million of the
   required radio beacons have already been mapped."

References

   1. http://www.deviceforge.com/articles/AT8606455669.html
   2. http://www.placelab.org/

----- End forwarded message -----

by Anthony LaMarca (Sep. 9, 2005)

Foreword: This whitepaper introduces an open source toolkit that lets mobile devices determine their locations with the aid of freely accessible, nearby radio sources, such as fixed Bluetooth devices, 802.11 access points, and GSM cell towers. Basically, the device reads the IDs of these local "radio beacons" (each of which has a unique or semi-unique ID), looks up their positions in a locally-cached database, and performs a computation akin to triangulation. Intel created Place Lab in an effort to satisfy the emerging requirement for location-awareness within mobile devices such as smartphones, PDAs, and laptops, or even moving vehicles. According to the whitepaper, over four million of the required radio beacons have already been mapped.


Place Lab Uses Radio Beacons to Enable Location Awareness
by Anthony LaMarca


Overview: Barriers to Device Positioning

Allowing users to discover and communicate their positions in the physical world has long been identified as a key component in emerging mobile computing applications [note 1]. Dozens of research and commercial location systems have been built using sensing technologies including ultrasonic time-of-flight, infrared proximity, radio signal strength and time-of-flight, optical vision, and electro-magnetic field strength. There have been many research and commercial efforts to improve accuracy and precision, shrink the size of the sensing hardware, simplify deployment and calibration of sensors, and provide more convenient middleware.

Despite these efforts, building and deploying location-aware applications that are usable by a wide variety of people in everyday situations is arguably no easier now than it was ten years ago. First and foremost, current location systems do not work where people spend most of their time; coverage in current systems is either constrained to outdoor environments or limited to a particular building or campus with installed sensing infrastructure. Applications like location-aware instant messaging fall flat if they only work for a fraction of users or only during a fraction of a user's day.

Second, existing location technologies have a high cost of entry to both users and application developers. Many location systems require expensive infrastructure, time-consuming calibration, or special tags, beacons, and sensors. The privacy cost to the many stakeholders is also typically ignored or considered only after deployment.

A new approach

These barriers leave location-aware computing in an unfortunate cycle: There are very few users due to a dearth of applications; developers are not interested in writing applications for nonexistent infrastructure; infrastructure investments are based on user demand, of which there is little. This cycle has not prevented researchers from prototyping and innovating in the application space. It has, however, prevented the widespread experimentation and adoption of these applications by real users. The result is that while we can give compelling demonstrations of location-based applications, few can be used in the places they are most useful: where we live, where we socialize, where we shop.

Place Lab addresses both the lack of ubiquity and the high-cost of entry of existing approaches to location. Place Lab is a fundamentally different philosophy compared to previous work because we focus on:

    * Maximizing coverage as measured by the percent of time location fixes are available in people's daily lives, and

    * Providing a low barrier to entry for users and developers. 

The Place Lab approach is to allow commodity hardware clients like notebooks, PDAs and cell phones to locate themselves by listening for radio beacons such as 802.11 access points (APs), GSM cell phone towers, and fixed Bluetooth devices that already exist in the environment. These beacons all have unique or semi-unique IDs, for example, a MAC address. Clients compute their own location by hearing one or more IDs, looking up the associated beacons' positions in a locally cached map, and estimating their own position referenced to the beacons' positions.

Existing radio beacon sources are sufficiently pervasive and can be mapped appropriately to meet Place Lab's goal of maximizing coverage in most people's daily lives. For example, Place Lab clients already have access to over four million mapped beacons situated in numerous cities, and mechanisms are in place to scale well beyond this number. This paper will also show how Place Lab's use of commodity hardware and commitment to user's privacy lowers the cost of entry to users and how the high beacon coverage combined with flexible programming interfaces lowers the cost of entry for developers.

Precision of the location estimates, while important, is secondary to coverage, privacy, and cost in Place Lab. That is, we believe it is important to model location uncertainty and minimize it to the extent possible without requiring custom hardware or limiting the operation to controlled environments.

This philosophy is similar to how ubiquitous wireless infrastructure remade telephony into an indispensable everyday tool. A cell phone with tremendous voice quality that only works in one building has quite different affordances than one with passable voice quality that works almost everywhere. The former tends to lend itself to more niche problems like office automation while the latter finds a home in the hands of anyone who wants to socialize and conduct business throughout their daily activities.

Place Lab architecture

The Place Lab architecture consists of three key elements: Radio beacons in the environment, databases that hold information about beacons' locations, and the Place Lab clients that use this data to estimate their current location (Figure 1).


Figure 1: Key components in the Place Lab architecture

Keep reading to learn more about each of these elements and how they are designed to help meet Place Lab's goals of maximal coverage of daily life and low barrier to entry for users and developers.

Radio beacons

Place Lab works by listening for the transmissions of wireless networking sources like 802.11 access points, fixed Bluetooth devices, and GSM (Global System for Mobile Communications) cell towers. We collectively call these radio sources beacons. They all employ protocols that assign beacons a unique or semi-unique ID. Hearing this ID greatly simplifies the client's task of calculating their position. The coverage and accuracy of Place Lab is dependent on the number and type of beacons in range of the client device. Fortunately, wireless networking infrastructure is being deployed at a rapid pace in places that users spend their time. Most developed areas of the world have GSM coverage and cities and towns are becoming blanketed with 802.11 access points (our measurements in downtown Seattle, for example, show an 802.11b density of 1200 access points per km2).

Place Lab devices need only interact with radio beacons to the extent required to learn their IDs. Place Lab clients do not need to transmit data to determine location, nor do they listen to other user's data transmissions. In the case of 802.11, receiving beacons can be done entirely passively by listening for the beacon frames periodically sent by access points. These beacon frames are sent in the clear, and are not affected by either WEP (Wired Equivalent Privacy) or MAC (Media Access Control) address authentication. Other technologies like Bluetooth require clients to initiate a scan in order to find nearby beacons. Due to restricted programming interfaces, detecting GSM cell IDs requires handsets to associate with nearby cell towers as they normally do when carried around and not on a phone call.

Beacon databases

Place Lab has a critical dependence on the availability of beacon locations; if Place Lab knows nothing about a beacon, being in range does not improve location estimates. In the Place Lab architecture, the beacon database plays the important role of serving this beacon location information to client devices. There can be multiple beacon databases and we do not specify whether beacon databases are private or public, how clients authenticate with a database or how many databases a client should load data from.

Many of these beacon databases come from institutions that own a large number of wireless networking beacons. Organizations like companies, universities and departments often know the locations of their 802.11 access points, since this information is commonly recorded as part of a deployment and maintenance strategy. These data sets tend to be on the order of tens or hundreds of access points, and the maps are typically quite accurate. While these data sets were not originally built for doing beacon-based location estimation, it only requires a format-translation step to add this data to Place Lab and location-enable the institution's building or campus.

Other sources of Place Lab mapping data are the large databases produced by the war-driving community. (The term war-driving is an allusion to the 1983 movie "WarGames" where Matthew Broderick's character David engaged in war-dialing by sequentially dialing blocks of phone numbers in an attempt to discover and establish a modem connection with interesting computers.) War-driving is the act of driving around with a mobile computer equipped with a GPS device and a radio (typically an 802.11 card but sometimes a GSM phone or Bluetooth device) in order to collect a trace of network availability.

War-driving has become a hobby for many radio enthusiasts and groups of war-drivers have formed online and offline clubs to share and pool their trace data. Each war-driving trace is a time-coded sequence of records containing the latitude and longitude of where the record was taken, as well as the list of radio sources and associates' signal strengths that could be heard at that time. By pooling their war drives together and applying some simple averaging, these groups have produced estimated locations for millions of beacons. Public domain war-driving software has been developed for most computing platforms, and there are many aggregation Web sites to which war-drives can be submitted. While war-driving has traditionally been performed in order to provide information about where nearby network access can be obtained, Place Lab uses these maps in reverse to infer where we are given a particular beacon is nearby.

Since the positions of beacons are being inferred from observations tied to GPS estimates, war-driving databases only contain estimates of beacons' positions. The error in these estimates translates into a decrease in the accuracy of location estimates made by Place Lab. However, what these databases lack in accuracy they make up for in coverage, making them highly useful for Place Lab. As an example, wigle.net is the largest of the 802.11 war-driving repositories, and contains over 2 million known AP positions, and the recent "World Wide War-drive" added 275,000 new access points over an 8 day period (worldwidewardrive.org).

At this time, Place Lab clients have access to location information for approximately 2.2 million radio beacons, primarily 802.11 access points. These mostly come from wigle.net, but we have more accurate databases for U.C. San Diego and the University of Washington, as well as some GSM tower locations imported from the FCC's database. To allow us to experiment with beacon placement algorithms, we also maintain our own database that currently has location estimates for around 40,000 GSM, 802.11, and Bluetooth beacons.

Place Lab clients

The Place Lab clients use live radio observations and cached beacon locations to form an estimate of their location. To make clients both extensible and portable, client functionality is broken into three logical pieces: spotters, mappers and trackers.

Spotters are the eyes and ears of the client and are responsible for the observing phenomenon in the physical world. Place Lab clients typically instantiate one spotter per radio protocol supported by the device. As an example, a laptop running Place Lab might have a Bluetooth and an 802.11 spotter, while a cell phone might run a Bluetooth and a GSM spotter. The spotter's task is to monitor the radio interface and share the IDs of the observed radio beacons with other system components.

An observation returned by a spotter is of little use if nothing is known about the radio beacons. The job of the mapper is to provide the location of known beacons. This information always includes a latitude and longitude, but may also contain other useful information like the antenna altitude, the age of the data, a learned propagation model, or the power of the transmitter. Mappers may obtain this data directly from a mapping database, or from a previously cached portion of a database. This cache can contain beacons for a large area, say the entire United States and Europe, or may, due to capacity concerns, just contain information for a single city.

The tracker is the Place Lab client component that uses the streams of spotter observations and associated mapper data to produce estimates of the user's position. The trackers encapsulate the system's understanding of how various types of radio signals propagate and how propagation relates to distance, the physical environment, and location.

Trackers may use only the data provided to them by the spotter and mapper, or may use extra data like road paths and building locations to produce more accurate estimates. As an example, Place Lab includes a simple tracker that computes a Venn diagram-like intersection of the observed beacons. This tracker uses very few resources, making it appropriate for devices like cell phones. Place Lab also includes a Bayesian particle filter [note 2] tracker that can utilize beacon-specific range and propagation information. While computationally more expensive, the Bayesian tracker provides about a 25 percent improvement in accuracy and allows Place Lab to infer richer information like direction, velocity and even higher level concepts like mode of transportation (walking, driving, etc.).

Privacy Concerns

Privacy issues have had a strong influence on the design, implementation and use of Place Lab. Place Lab's key privacy principle is that devices should be able to position themselves based on passive monitoring of the environment. This principle gives the user control over when their location is disclosed, laying the foundation for privacy-observant location-based applications. Unfortunately, while it is theoretically possible to construct a device that senses GSM, 802.11, and Bluetooth passively, current devices are not as passive as we would like. For example, some 802.11 device drivers broadcast their existence to the infrastructure regularly. Similarly, we are not aware of any GSM cell phone that does not report itself to the infrastructure. Although the Bluetooth standard does not require that a device transmit its MAC address to neighboring devices when scanning, many of today's Bluetooth devices do so anyway.

Apart from passive scanning issues, another privacy trade-off is the manner in which mapping data is downloaded to clients from the mapping databases. Due to capacity issues, impoverished devices may only be able to load a small portion of the mapping database. However, if mapping data is downloaded for a small region, say a neighborhood, the operator of a mapping database has a reasonably fine-grained estimate of a user's location or potential location. Loading (and possibly discarding most of) a country or continent's worth of beacon locations gives the mapping servers less information about a user's location.

The war-drivers submitting their traces also have privacy considerations. War-drivers who submit their logs may not want a permanent record kept of the path they take while collecting a log. An approach to mitigating this problem is to have trusted entities anonymize and aggregate logs. For example, Place Lab has a design for a distributed backend database that slices up logs on a per-beacon basis and randomly distributes information about each beacon to a different node. Using this scheme, a contributor's war-driving path cannot easily be reconstructed, yet the log is still useful for mapping. Of course any approach involving a trusted-entity still relies on users trusting that entity.

Finally, there are the privacy issues that affect the owners of the beacons used by Place Lab. Cell phone providers, coffee shops, and hotels probably do not mind if the existence and location of their network beacons are known. Individuals and corporations, however, may be wary in some cases of having information about their access points listed in a public database. They may be concerned about people attempting to steal network access or about revealing that they have computer equipment at a particular location. There are a variety of potential ways to mitigate these concerns. 802.11 and Bluetooth beaconing can be manually turned off, making them invisible to Place Lab.

As stronger authentication becomes available for wireless networks, some concern about beacon visibility may simply disappear. Finally, there are possibly technical solutions to protecting beacon owners' privacy in Place Lab, such as using an encrypted hash of beacon identifiers so that clients must actually hear a beacon to resolve the true ID.

Summary

Many emerging location-aware computing applications are going to require 100 percent availability of location information in real people's lives, similar to the way cellular phones are held to a 100 percent availability standard. Place Lab provides the necessary features to move in this direction with a beacon-based approach to location that can:

    * Maximize coverage as measured by the percent of time a location fix is available in people's daily lives and

    * Offer a low barrier to entry for users and application developers thanks to the use of commodity hardware, privacy awareness, and straightforward interfaces. 

Coverage experiments have confirmed the intuition that GPS, often thought of as a pervasive location technology, in fact lacks availability in people's daily lives since people are frequently indoors or under cover, whereas 802.11 and GSM beacons are frequently available both indoors and out.

We believe Place Lab is a useful artifact for the research community. Binary and source releases of Place Lab are available for many platforms along with sample radio traces at www.placelab.org. Adoption of Place Lab has already been encouraging; our system sees around 500 downloads per month and a number of research projects and Web services are using Place Lab as a component of their system.

More Info

    * Download the 18-page whitepaper from which this article is derived. It's located on the Place Lab website: Place Lab: Device Positioning Using Radio Beacons in the Wild (945KB PDF). In the full paper, you can read much more information, including experimental results quantifying the important relationships between beacon types, coverage, density, and accuracy, as well as future research problems and opportunities.

    * You can also learn more about Place Lab and download Place Lab's open source license at the Place Lab website.

    * Discover more about Intel's research at the Intel Web site, as well as about Intel Research Seattle. 


References

      [1] Want, R., Schilit, B., Adams, N., Gold, R., Petersen, K., Goldberg, D., Ellis, J., & Weiser, M., The ParcTab Ubiquitous Computing Experiment, in: Imielinski, T. (Ed.) Mobile Computing, pp. 45-101 (Kluwer Publishing). (1997)

      [2] Sequential Monte Carlo in Practice, Doucet A. & de Freitas, N. (Ed.) (New York, Springer-Verlag).(2001) 

-- 
Eugen* Leitl <a href="http://leitl.org">leitl</a>
______________________________________________________________
ICBM: 48.07100, 11.36820            http://www.leitl.org
8B29F6BE: 099D 78BA 2FD3 B014 B08A  7779 75B0 2443 8B29 F6BE



More information about the FoRK mailing list