Personal Homepage of

Jürgen Bohn

Contact information:
Skype: juergen_j_bohn
E-Mail: jjbohn (at) jjbohn (dot) com
Internet: www.jjbohn.com/

Photo
Back to Main Page Back to Past Work @ ETH Zurich

Robust Probabilistic Positioning of Resource-Limited Mobile Devices

1 - Motivation
2 - Architecture of the Positioning System
3 - Implementation Aspects
4 - Screenshots
5 - Related Publications
6 - Related Student Projects

Motivation

Ubiquitous computing technology has become increasingly wide-spread in public places and even in private homes. For instance, wireless communication infrastructures such as Wireless LAN (WLAN) or Bluetooth have become quite popular in airports, train stations, and public buildings, and not only as substitutes for expensive wired networking. Simultaneously, other typical pervasive computing technologies such as radio frequency identification (RFID) have become commonplace in industrial and commercial facilities, such as in manufacturing plants, museums and department stores (e.g., see www.rfidjournal.com).

Considering emerging ubiquitous computing applications, context awareness has become a major field of research. Location awareness is of particular interest, and location information is even considered to be the "most important piece of context used in ubicomp applications". Consequently, numerous location aware systems have been conceived, such as the Lancaster mobile tourist guide, the Cricket location-support system, or the Active Badge location system.

However, with respect to dependability and reliability issues, the majority of existing positioning systems still suffers from various drawbacks. First, they are vulnerable to service disruption and temporary failures because they generally rely on a fixed set of location sensing technologies. Secondly, as a rule, they don't exploit the full spectrum of available sources of location information that are already available and implicitly provided by existing ubiquitous computing environments. Thirdly, these positioning systems are usually not suited to operate as an independent and autonomous service on small, resource-limited mobile devices. This is either because these systems depend on a centralized service which runs in the background infrastructure, or because they are too complex and resource-intensive since they were not designed to cope with the prevailing resource restrictions of small mobile devices.

In a first step, we have developed a robust and scalable probabilistic positioning system based on Java, which addresses the above-mentioned shortcomings of common ubicomp location systems. The system is based on a lightweight map-based fusion algorithm, which was explicitly tailored to operate efficiently and autonomously as a stand-alone service on small resource-limited devices. The architecture of our system is modular and supports an arbitrary number of sensors to be integrated. Further, our positioning system it is particularly suited to work with standard off-the-shelf sensor hardware that is typically found in ubiquitous computing environments, thus allowing to exploit existing ubicomp infrastructures for positioning.

Update: In the meantime, we completed iPOS - a fully revised and optimized version of the initial probabilistic positioning system for mobile handheld devices based on the CrEme JVM and the WinCE/PocketPC platform. The iPOS system architecture and the implemented iPOS prototype I describe in detail in my doctoral dissertation and in an article that was published in the July 2007 edition of the Sensor Review journal.

Top of page.


Architecture of the Positioning System

The first generation of the probabilistic positioning system we have devised consists of several separate components. The main architectural components are:

In the context of our work, a sensor may be either a physical device or an application that in turn preprocesses the location information of other physical devices or applications. A sensor plugin is associated with one specific type of sensor. It preprocesses and transforms sensory location information into an abstract representation of position estimates we call sensor events. Each sensor event contains an absolute position with respect to a given two-dimensional map model. New sensor events are written into an internal tuple space for later retrieval and further processing.

The central system component is the positioner, a separate module which performs the actual positioning computation. During each computational iteration step, the positioner calculates a single position by fusing the location information of the sensor events found in the internal event tuple space. The fusion process is accomplished by means of a lightweight probabilistic fusion algorithm running on top of a two-dimensional map model. In our case, map models represent geographic maps and are realized using an equidistant cell grid. The cell grid may contain obstacles (or walls) and arbitrary objects, e.g. markers for symbolic locations or sensors. The cell grid data structure also offers a range of auxiliary methods (e.g., to access and modify cells or to resolve the position of objects) and advanced methods (e.g., to calculate the degradation of cell occupancy probabilities or to compute the minimal distance between two cells with respect to blocking walls). The map manager unit is responsible for the loading of maps and the updating of position probabilities in cell grid data structures.

Whenever a position computation has completed, the resulting position estimate is converted into a position event and fed into the event infrastructure. Per default events are published to a local event space, which is readable to applications and services running on the mobile device only. Events can also be forwarded to a remote event space in order to reveal the position of the mobile device to other devices or services in the environment.

Fig.1: Architecture of the probabilistic positioning system.
Fig.1: Overview of the probabilistic positioning service. Red arrows indicate flow of sensorial input for sensor plugins, the blue arrows indicate flow of sensor and position events

For creating and editing maps, we implemented a graphical map builder. The map builder provides the means to place and name objects, to draw walls and to insert transition cells to other maps, for instance. The editor has been enhanced by a simulation mode that allows the manual emulation of sensor events which proved suitable for preliminary testing of new heuristics and algorithms for positioning. We have also realized a monitor application that allows to continuously track the position of a mobile device and mark its position on the associated map. Since all communication between the positioner and the editor/monitor is event-based and performed asynchronously via tuple spaces, the functioning of the management tools is fully decoupled from the operation of the positioner, and they may anywhere in the network. This permits to run only those components on a resource-limited mobile device which are indispensable for positioning (i.e., the positioner, the event abstraction layer, and sensor plugins). The interaction and data flow between the essential system components is depicted in Fig. 1.

Top of page.


Implementation Aspects

Our probabilistic positioning system was fully implemented in Java. Currently, our implementation supports the following types of location sensor plugins and sensor hardware:

Please note that the bulk of our sensor hardware constitutes customary ubiquitous computing equipment with primary application areas that are not related to the task of positioning.

We used the IBM TSpace as the event tuple space implementation (available at the IBM alphaWorks web site at www.alphaworks.ibm.com/tech/tspaces), which proved to be easy to use and reliable.

Top of page.


Screenshots

Figure 2 shows a screenshot of the graphical map while editing a map for floor 'D' of our office building at ETH Zurich. Figure 3 displays a screenshot of the monitor application which we use to visualize the current position of the mobile device tracked by the positioner.

Fig.2: Screenshot of map editor while editing a map of our office building.
Fig.2: Screenshot of the map editor taken while editing the map for floor 'D' of our office building. The icon menu bar above the editing window features the available modes and tools, such as tools for adding, erasing or moving cells, walls, and objects

Fig.3: Screenshot of position tracking monitor application during operation of the positioner.
Fig.3: Screenshot of the position tracking monitor application during operation of the positioner. The last calculated position of the tracked mobile device is marked with a small black 'x'. The current state of the position probability distribution in the cell grid is visualized as gray-shaded areas. Darker shaded areas on the map correspond to higher position probabilities. Icons with text labels mark the position of beacons or of learned reference positions used by the respective sensor plugins (here: Nibble reference locations, Bluetooth beacons, active RFID beacons, passive RFID reader location)

Top of page.


Related Publications

Top of page.


Related Student Projects

In the following you find a list of related student projects which I supervised.

Completed Projects


TypeTitleStudentSupervisorSemester

S Bestimmung der Bewegung von Fahrzeugen mit Hilfe einer hochverteilten RFID-Tag Infrastruktur Thomas ZweifelJürgen BohnWS 05/06

S LuxTraceRT: A Self-Calibrating Real-Time Positioning System using Solar Cells as Main Sensory Input Martin BurriJürgen BohnSS 05

S Portierung von Kernkomponenten eines existierenden Java-basierten Positionierungssystems auf einen PDA (HP iPAQ, PocketPC 2002) René GallatiJürgen BohnWS 04/05
S iPOS: Ein adaptives System zur Selbst-Positionierung von mobilen ressourcenbeschränkten Geräten Marco Feriencik,
Matthias Leumann
Jürgen BohnWS 04/05
D Nachverfolgung und Positionierung von Fahrzeugen in Gebieten mit dicht verteilten RFID-Tags Nicola OprechtJürgen BohnWS 04/05

S Bestimmung der Position eines Lego-Mindstorm-Modellfahrzeuges in einem Testgelände mit zufälliger RFID-Tag-Verteilung Marco BärJürgen BohnSS 04
D Zuverlässige Patientenüberwachung in einer Ubiquitous-Computing-Umgebung Christian GegenschatzJürgen BohnSS 04

S Erweiterung eines bestehenden probabilistischen Positionierungsdienstes um einen kartenbasierten Mechanismus zur Positionsvorhersage Simon SchlachterJürgen BohnWS 03/04
S Erweiterung und Evaluierung eines Positionierungsdienstes Danat Pomeranets und Stephan SchneiderJürgen BohnWS 03/04

P Indoor Navigation for Visually Impaired People (Navigation Layer) Nicolas TissotJürgen Bohn,
Vlad Coroama
SS 03

D Heuristiken zur Positionsbestimmung in Gebäuden mittels Sensor-Fusion und 2D-Kartenmodell Christian SchärJürgen BohnSS 02

P Lokalisierung von WLAN-Benutzern im IFW-Gebäude Daniel SchädlerJürgen BohnSS 01

Top of page.

Last modified: Jun 06 2010 06:19:55  jb