4BA2

leaflet

Technology Survey

PlaceLab Geopositioning system

by Colm McMullan, David Cahill and David Fry

Introduction

What is Place Lab?

Placelab is a collaborative effort between Intel Research Seattle and various academic institutions to provide a privacy-observant, low cost and easy to use geo-positioning system. The system is reliant upon existing wireless network infrastructure to provide landmarks, which can be used to determine the current location of a device. This service not only informs the user where they are, it can also be utilised by location-based services (LBS).

The Place Lab software listens for wireless network base-stations, it can then look-up the coordinates of whatever networks it finds and will use triangulation to calculate its position.

A simple example of how Place Lab works is illustrated below:

In the following picture the person can see the three landmarks; The Eiffel Tower, Sacre-Couer and Notre Dame. Using these landmarks as fixed points of reference they can then approximate their position on a map.

A simple example of how Place Lab works

There is very little difference between how a person finds their position in this manner and how Place Lab does it. In the next diagram we see that the laptop can detect the three wireless antennae; A, B and C. The locations of these antennae are known by the client and therefore it can find its position by taking into account the strength of the signal it receives from each one (ie. the closer it is, the stronger the signal) and approximating its position on a map.

the laptop can detect the three wireless antennae; A, B and C

Of course, in order for this to work we need to know the location of the wireless networks around us. To accomplish this we need a device with any form of wireless technology available to it and a GPS device. When the device discovers a wireless network, it saves its ID (usually the MAC address) along with the co-ordinates shown on the GPS, and saves it locally. This is called War Driving is discussed further in the Technology section below. Later on, the user may upload their results to a central database where others users can access and use them.

Applications

What kind of Applications can be created with this technology?

The basic idea behind Location Based Systems (LBS) is to combine positioning data with location-specific information [7]. A LBS is able to answer three questions: Where am I? What's around me? How do I get there [8]?

LBS were originally conceived in order to find the location from which emergency calls were made, they are now being applied to a wide variety of problems. There are essentially two different types of LBS services; Passive, and, Active [9]. A Passive service is one which is constantly tracking some device. One could use this type of service for asset tracking, or for route-mapping in an automobile. An Active service is initiated by the user as a once-off event, such as "Where is my nearest...". Their most basic application is to mimic a GPS device connected to a computer via serial port. More interesting applications can also be created, such as: to inform a subscribed user about such things like weather and traffic conditions specific to their current location.

There are numerous programming API's available to developers. JSR179 is one such API. It is written for J2ME (Java 2 Platform, Micro Edition), it provides facilities for requesting and getting the current location of any device on which it is running [10]. Various other tools (eg. 'gpsd' [11]) have also been written to allow numerous programs to use the same positioning information. With these simple libraries it is becoming increasingly easier to create powerful LBS, and as a result, more popular.

There are many companies that have information that would be beneficial to a potential customer regarding a certain area. For example, a company that had hotel information for the whole of Dublin could have a LBS which a user could pose queries such as: "Where is the cheapest hotel within 5 miles of my current location?", or "Where is the nearest hotel that is open?". The company could charge for the query and possibly book a room for the user, it could also provide them with directions on how to get to the hotel, and most importantly, it is completely hassle free.

Value-added services like this could potentially be built into most existing software, giving the user more value for money, and as a result generating more business for the company involved.

Technology

How does PlaceLab work?

PlaceLab consists of a centralised database containing information on landmarks and client side code to perform the position calculation. [1]

The client side PlaceLab software exists in a downloadable form for multiple platforms. On almost all operating systems it is as simple as extracting files from an archive and executing a single command to get started. The database consists of a single table containing a unique identifier for each landmark (for instance the MAC address of a WiFi access point), a human readable name (eg. the SSID of a WiFi access point) and the landmark's latitude and longtitude.

Before a user can perform a position calculation some (or all) of the database must be downloaded and stored locally on the user's device. The PlaceLab client software contains a MapLoader application used to connect to the database and download the information for a selected region.

Database? What database?

The database is available online via PHP forms on the PlaceLab website and anyone is able to contribute to the data. Included in the PlaceLab software download is a PlaceLab stumbler application. This application is run on a mobile device in conjuction with a connected GPS device to firstly scan for landmarks and then log anything seen with a latitude and longtitude (dervied from the GPS device). When finished stumbling, the user uploads the log file created using a form on the PlaceLab website to contribute any new information to the database.

Client side PlaceLab software

The architecture of the PlaceLab software contains three key components; Spotters, Mappers and Trackers. [1]

Spotters are used to passively scan (ie. without neccessarily connecting to the host's network) the locality of a device for landmarks which will be used in position calculation. A generic interface (the AbstractSpotter) is the superclass of all spotters and different spotter code exists for different wireless technologies, for instance there exists a WiFiSpotter and a BluetoothSpotter. Native code (written in C) exists to make use of the drivers or libraries available on each operating system to perform the low level spotting, for instance PlaceLab on Linux uses the Wireless Extension API. Apart from this native code everything else is written in Java.

Essentially, the spotters return a list of the landmarks (WiFi access points or Bluetooth devices or GSM base stations depending on the spotter used) that are currently visible. It is then the job of the mapper to associate these with what is stored in the database. Only landmarks which are listed in the database are useful in performing position calculation since no location information is available for any other landmarks.

The tracker uses the output from the mapper to calculate an estimated latitude and longtitude and provide the user with this information. A number of different trackers exist and perform the estimation in varying ways. For instance the CentroidTracker simply calculates the geographic center of the known landmarks; the HamsterTracker prevent large (and possibly unrealistic) jumps in position akin to restricting the movement of a hamster in a ball; the SmoothingTracker uses movement history to bias the estimate in such a way that the distance moved is 'guessed' based on previous movement and other trackers exist and are currently being developed. [15]

Advantages of the PlaceLab approach

Since all position calculation is based on existing network infrastructure PlaceLab creates a low barrier of entry from the point of view of cost and hardware. The ability to use a variety of network infrastructures greatly increases the coverage available to users (by this it is meant that coverage is percentage of the users time that the PlaceLab service is available). While PlaceLab may not always provide a high degree of accuracy it is thought that a lower quality but highly available service is a better solution than a high quality but rarely available service such as the Active Badge System [13]. Also, since all position calculation is performed on the client side device any Big Brother concerns should be limited as is discussed in the Privacy section below. This is augmented by the open source approach of the development process so any inquisitive user is able to find out exactly what the software is doing.

Problems with the PlaceLab approach

To use PlaceLab there must exist a number of entries in the centralised database for landmarks in the user's locality. For users in well developed, technologically advanced areas this may not be a problem but for the majority of people this is unlikely and so it is crucial for PlaceLab to quickly develop a large community base to bootstrap the database and encourage use of the platform. This community already exists somewhat in the form of War Drivers who contribute to global databases of WiFi access points such as Wigle.net. Information from this database integrates easily with PlaceLab which partly solves this problem. Some functionality such as altitude and estimation accuracy is currently not provided although these issues will very likely be addressed in future versions.

Privacy

Privacy is a major barrier to adoption of location-based services. In [5], the focus is on PARCTab, a previous ubicomp experiment, identifying three major privacy problems experienced in relation to location tracking. In this section, we use those three problems as a framework to analyse PlaceLab's privacy problems and solutions.

Centralized location databases

PARCTab used a centralized location database, as it allowed for easier creation of applications. However, this situation means the user has to trust the system owners and administrators to use and protect their location data properly. As seen in Technology, PlaceLab works by passively scanning for beacons from various sources, then performing calculations using this information and cached mapping databases to determine a location estimate for the device. This is referred to in [4] as "position without communication", and it clearly provides better privacy.

Revealing - location granularity

PARCTab used 'all-or-nothing' location revealing - If users revealed their location at all, they revealed the exact room they were in. PlaceLab's solution to this is location granularity, and a privacy vs. utility trade-off. PlaceLab argues for a case-by-case basis for revealing our location at different granularities (county, city, street) to different applications. The decision is to be made on the basis of what information the application needs in order to be useful, and its level of utility. Thus, we reveal our location to obtain the benefit of the service.

Caching is another possibility. For example, we could download a district-sized chunk of a 'nearest-X' service and query it locally. We thus reveal our city instead of our street, trading redundancy and bandwidth for a higher level of privacy.

When and to whom

The last concern during the PARCTab experiment was who, when, could have access to a person's location info. In PARCTab, a 3rd-party could track a user by making repeated requests to the system. With PlaceLab, disclosure is voluntary. However, it will take time to find workable systems for social disclosure - a recent experiment in the area [3] showed misunderstandings, and one participant felt uncomfortable in retrospect about some location notifications she had set up.

Analysis

Location-based services are a new area, and the phenomenon of 'experience breeds trust' [5] which resulted in gradually increased credit-card use on the Internet, may apply. Perhaps experience will teach us that LBS are just as innocuous if the provider of the service is trustworthy.

PlaceLab in Context

In this section, we attempt to put PlaceLab in context with other location systems. The taxonomy used is a subset of that described in 'Location Systems for Ubiquitous Computing' [15].

Physical position and Symbolic Location

Symbolic location is to do with abstract ideas of location, e.g. 'at home', 'in Dublin'. PlaceLab, like GPS, provides physical positions such as 47 39 17 N, 122 18 23 W, however another layer can be built on top of this, using physical position to derive symbolic location.

Absolute versus relative

Certain devices, e.g. those used by mountain rescue teams, are configured to give relative positions - "Victim's avalanche transceiver is 500m away to the North East". However, PlaceLab, like GPS, provides absolute locations on a globally shared latitude / longitude grid.

Localized Location Computation

As mentioned in the section on Privacy, PlaceLab performs location computation on the client side. GPS also works this way, as the satellites are completely unaware of any device's location. However, some systems require devices to beacon periodically and the system to compute location, e.g. PARCTab and personal-badge-location systems such as ActiveBadge [14]. This approach requires complete trust of the system operator.

Accuracy

Accuracy means the grain size of location information provided, e.g. correct to within 1km or correct to 5 metres. Due to its reliance on 802.11 AP density and GSM cell density, it is impossible to give universal figures for this metric with regard to PlaceLab. However, in experiments documented in [1], accuracy was seen to approach 20m if a device could see '4 or 5 distinct beacons during a 10 second window'.

Cost

In most location systems, there is a cost of installation, administration, a cost for infrastructure and a cost for mobile devices. With PlaceLab, the infrastructure (WiFi APs, GSM masts) exists, the mobile device is the user's laptop or PDA, and administration of the mapping database is performed by researchers and community members, thus it is effectively free.

Limitations

GPS, the most famous location system, has a major limitation in that it is virtually useless indoors due to its dependency on receiving satellite transmissions. PlaceLab's dependence on 802.11 beacons, GSM masts and Bluetooth devices make it very useful indoors, but almost useless in rural areas. As mentioned before, PlaceLab aims to provide a high coverage in terms of the time in which the service is available to users and since most users are assumed to be in urban areas this is less of an issue.

Conclusion

In this survey we have introduced PlaceLab as a possible platform to develop Location Based Systems. We have given a brief overview of possible applications, how the system works, privacy issues and where PlaceLab fits in relation to other geopositioning systems. The project is still in the early phases of development but we believe that it will succeed in it's goal of kickstarting interest in location based systems.

Bibliography

  1. Place Lab: Device Positioning Using Radio Beacons in the Wild.
    Anthony LaMarca, Yatin Chawathe, Sunny Consolvo, Jeffrey Hightower, Ian Smith, James Scott, Tim Sohn, James Howard, Jeff Hughes, Fred Potter, Jason Tabert, Pauline Powledge, Gaetano Borriello and Bill Schilit.
    (to appear, Pervasive 2005, Munich Germany).
  2. Accuracy Characterization for Metropolitan-scale Wi-Fi Localization.
    Yu-Chung Cheng, Yatin Chawathe, Anthony LaMarca and John Krumm.
    IRS-TR-05-003 (to appear in Proceedings of Mobisys 2005).
  3. Social Disclosure Of Place: From Location Technology to Communication Practices.
    Ian Smith, Sunny Consolvo, Anthony LaMarca, Jeffrey Hightower, James Scott, Timothy Sohn, Giovanni Iachello and Gregory D. Abowd.
    (to appear, Pervasive 2005, Munich Germany).
  4. Challenge: Ubiquitous Location-Aware Computing and the Place Lab Initiative.
    Bill Schilit, Anthony LaMarca, Gaetano Borriello, William Griswold, David McDonald, Edward Lazowska, Anand Balachandran, Jason Hong and Vaughn Iverson.
    In Proceedings of The First ACM International Workshop on Wireless Mobile Applications and Services on WLAN (WMASH 2003), San Diego, CA. September 2003.
  5. Privacy and Security in the Location-enhanced World Wide Web.
    Jason Hong, Gaetano Borriello, James Landay, David McDonald, Bill Schilit and Doug Tygar.
    In Proceedings of Ubicomp 2003, Seattle, WA. October 2003.
  6. A Case Study in Building Layered DHT Applications.
    Yatin Chawathe, Sriram Ramabhadran, Sylvia Ratnasamy, Anthony LaMarca, Joseph Hellerstein and Scott Shenker.
    IRS-TR-05-001.
  7. Position yourself with LBS
    Johan-Gabriel Fritz
    http://www.ericsson.com/mobilityworld/sub/articles/other_articles/nl04apr07
  8. J2ME and Location-Based Services
    Qusay H. Mahmoud
    http://developers.sun.com/techtopics/mobility/apis/articles/location/
  9. Location Based Services
    ZIMPL.COM
    http://www.zimepl.com/products/location_services/overview.html
  10. JSR179 (Java API)
    Nokia Corporation
    http://www-users.cs.umn.edu/~czhou/docs/jsr179/lapi/javax/microedition/location/package-summary.html
  11. gpsd
    http://gpsd.berlios.de/
  12. Challenge: Ubiquitous Location-Aware Computing and the Place Lab Initiative.
    Bill Schilit, Anthony LaMarca, Gaetano Borriello, Willian Griswold, David McDonald, Edward Lazowska, Anand Balachandran, Jason Hong and Vaughn Iverson.
    Presentation at The First ACM International Workshop on Wireless Mobile Applications and Services on WLAN (WMASH 2003), San Diego, CA, September 19, 2003.
  13. Active Badge System - http://www.uk.research.att.com/ab.html
  14. Location Systems for Ubiquitous Computing
    Jeffrey Hightower, Gaetano Borriello
    IEEE Computer, 2001
  15. PlaceLab JavaDoc
    http://www.placelab.org/toolkit/doc/javadoc/