Photo: Brian Smale

The Global Positioning System has spawned a wealth of location-based consumer applications that would have been unthinkable a few years ago—cars that can give drivers door-to-door directions and, soon, cellphones that can tell you where the nearest shoe sale is happening. But these applications currently require a line of sight to three or four orbiting satellites simultaneously—something that can be a tall order in the dense, built-up urban areas that, ironically, are the areas most likely to produce lost drivers or shoe sales.

Leveraging that very density to give location-based applications an alternative to GPS is the goal of a new research project being conducted by our Place Lab, a collaboration between Intel Research Seattle, Intel Research Cambridge, in England, and the University of Washington, in Seattle.

We are building a geographic positioning system out of the constant fog of signals emitted by radio beacons, such as GSM cellular towers, Wi-Fi access points (IEEE 802.11), and Bluetooth devices. The plan is ambitious. With GSM (Global System for Mobile Communications) replacing older cellular technologies and Wi-Fi access points proliferating at breakneck speed, we hope to be able to support Place Lab deployments in major metropolitan areas around the world within a few years.

Today, Place Lab provides reasonable coverage in the 50 largest U.S. cities. This is not a commercial endeavor but rather a research project with a community-building focus. Our goal is to enable others to develop location-enhanced applications, products, and services that can run on top of our basic location technology; all of our work is openly available.

The foundation of this technology is that many radio sources constantly broadcast a digital beacon that contains a unique identifier. In the case of Wi-Fi, this is known as the MAC address and is typically broadcast every tenth of a second. You don't have to be logged on to a Wi-Fi access point in order to detect its beacon; just being within its broadcast range—about 50 to 200 meters—is sufficient. If a user's device knows the physical location of a large number of radio sources, it can triangulate its own position based on the set of beacons it is currently hearing. Our goal is to build such a system, complete with a database of known radio beacons and their locations, and thus provide a low-cost alternative to current location systems.

Our experiments show that although our location estimates yield lower accuracy than GPS (20 to 25 meters using Wi-Fi beacons and 100 to 150 meters using GSM towers, versus 8 to 10 meters for GPS), our system works indoors as well as outdoors. What's more, it runs on devices with Wi-Fi or GSM capability—without any extra hardware.

Since Place Lab is only as good as its underlying database of radio beacon locations, one of our key challenges is building a database that contains the locations of a significant fraction of all Wi-Fi and GSM radio sources. It would be prohibitively expensive to have a single entity map the entire world (or even a single country). Mapping is further complicated by the fact that new access points and cellular service towers are continually deployed and existing ones are moved or decommissioned.

To address these issues, we have decided to build what is called a distributed contributor database. Users of the system can upload information about access points in their local vicinity. This is similar to the model originally used by the Compact Disc Database Service, a cooperative database for CD track information that is routinely used by audio and computer equipment to display CD title and track information. It was developed by users, not the music industry.

Photo: Brian Smale

Photo: Brian Smale

Photo: Brian Smale

Companies, universities, and individual users who wish to contribute to Place Lab's efforts can go to our Web site and add the MAC address and location information for access points to the database. To kick-start coverage, Place Lab is also making use of public access point databases that have been built by the communities of "war drivers" and Wi-Fi clubs.

A relatively new phenomenon, war driving refers to hobbyists' using software on Wi-Fi and GPS-equipped mobile computers to create maps of the physical locations of access points. As of October, Place Lab users can obtain the locations of more than 1.6 million radio beacons in the United States and Western Europe.

Managing such a global database and keeping it up to date through a single central authority raises concerns about privacy. For example, a central server might be used to track the activities and locations of users. Place Lab is dealing with privacy worries by deploying a peer-to-peer mapping architecture, in which the location information is distributed across multiple independent servers. By spreading the data in this way, we also ensure that no single renegade server can tamper with the location data.

While past systems have estimated location using Wi-Fi signals, to our knowledge we are the first to build a positioning system that is capable of handling a wide diversity of radio sources that are changing constantly. Our system provides mechanisms for automatically filtering out access points that are, in fact, far away from where they are reported to be by comparing their positions with the reported positions of other access points that were detected by the user in the same neighborhood. Moreover, by incorporating support for diverse radio technologies, such as Wi-Fi and GSM, Place Lab can gracefully degrade its positioning accuracy based on the density and range of available radio sources.

We are also investigating how location systems and applications can be built to ensure the trust and privacy of users. Using passive scanning for radio beacons and a locally cached database to map radio sources to their locations, a device running Place Lab-based software computes its location without any need to log on to an access point or an external server (except for a single initial download to cache the radio beacon database).

Although Place Lab itself is privacy sensitive, applications built on top of Place Lab may need users to disclose their location in order to offer a service—for example, the ability to search for Italian restaurants and automatically filter the results based on their location. We are currently building demonstration applications and working with other researchers to design applications that allow users to control the level of disclosure they feel comfortable with.

In October, we released an open-source mapping and positioning tool kit that runs on Windows XP, Linux, Macintosh OS X, Windows CE/Pocket PC 2003, and Series 60 cellphones. If you are interested in getting involved in applications development, or if you simply want to try out the software, go to http://placelab.org.