Fundamental storage mechanisms for location based services in mobile ad hoc networks

Abstract

The proliferation of mobile wireless communication technology has reached a considerable magnitude. As of 2009, a large fraction of the people in most industrial and emerging nations is equipped with mobile phones and other types of portable devices. Supported by trends in miniaturization and price decline of electronic components, devices become enhanced with localization technology, which delivers, via the Global Positioning System, the geographic position to the user. The combination of both trends enables location-based services, bringing information and services to users based on their whereabouts in the physical world, for instance, in the form of navigation systems, city information systems, and friend locators. A growing number of wireless communication technologies, such as Wireless Local Area Networks, Bluetooth, and ZigBee, enable mobile devices to communicate in a purely peer-to-peer fashion, thereby forming mobile ad-hoc networks. Together with localization technology, these communication technologies make it feasible, in principle, to implement distributed locationbased services without relying on any support by infrastructure components. However, the specific characteristics of mobile ad-hoc networks, especially the significant mobility of user devices and the highly dynamic topology of the network, make the implementation of locationbased services extremely challenging. Current research does not provide an adequate answer to how such services can be supported. Efficient, robust, and scalable fundamental mechanisms that allow for generic and accurate services are lacking.

This dissertation presents a solution to the fundamental support of location-based services in mobile ad-hoc networks. A conceptual framework is outlined that implements mechanisms on the levels of routing, data storage, location updating, and query processing to support and demonstrate the feasibility of location-based services in mobile ad-hoc networks. The first contribution is the concept of location-centric storage and the implementation of robust routing and data storage mechanisms in accordance with this concept. This part of the framework provides a solution to the problems of data storage that stem from device mobility and dynamic network topology. The second contribution is a comprehensive set of algorithms for location updating and the processing of spatial queries, such as nearest neighbor queries. To address more realistic location-based application scenarios, we consider the inaccuracy of position information of objects in the physical world in these algorithms. Extensive analytical and numerical analyses show that the proposed framework of algorithms possesses the necessary performance characteristics to allow the deployment of location-based services in purely infrastructureless networks. A corollary from these results is that currently feasible location-based services in infrastructure-based networks may be extended to the infrastructureless case, opening up new business opportunities for service providers.

Die Verbreitung mobiler drahtloser Kommunikationstechnologie hat ein beträchtliches Ausmaß erreicht: Im Jahre 2009 ist bereits ein großer Teil der Menschen in den Industrie- und Schwellenländern mit Mobiltelefonen sowie einer Vielzahl weiterer Arten von tragbaren Geräten ausgestattet. Unterstützt durch die technologischen Entwicklungen in der Miniaturisierung sowie dem Preisverfall elektronischer Komponenten werden Geräte zunehmend mit Lokalisierungstechnologien ausgerüstet, mit deren Hilfe die geographische Position von Benutzern ermittelt werden kann. Zu diesen Technologien zählen beispielsweise leistungsfähige integrierte Schaltungen, die mit Hilfe des satellitengestützten Global Positioning System (GPS) die geographische Position eines Benutzers mit hoher Genauigkeit ermitteln können. Durch die Verknüpfung dieser beiden Entwicklungen werden lokationsbasierte Dienste ermöglicht, die Benutzern Informationen und Dienste in Abhängigkeit von ihrem Ort in der physischen Welt zur Verfügung stellen können. Beispiele solcher Anwendungen sind Navigations- und Stadtinformationsysteme sowie Systeme zur gegenseitigen Lokalisierung von Personen.

Eine wachsende Zahl drahtloser Kommunikationstechnologien, darunter drahtlose lokale Netze (WLANs), Bluetooth und ZigBee, ermöglichen den mobilen Geräten eine Kommunikation nach dem Peer-to-Peer-Schema, wonach Geräte so genannte mobile Ad-hoc-Netze bilden. Gemeinsam mit den Lokalisierungstechnologien wird dadurch grundsätzlich die Umsetzung verteilter lokationsbasierter Dienste möglich, ohne dabei auf infrastrukturbasierte Netze zurückzugreifen. Die spezifischen Merkmale mobiler Ad-hoc-Netze, vor allem die beträchtliche Mobilität von Geräten und die hochdynamische Topologie dieser Netze, machen jedoch die Implementierung lokationsbasierter Dienste zu einer Herausforderung. Die aktuelle Forschung gibt keine hinreichende Antwort auf die Frage, wie solche Dienste in mobilen Ad-hoc-Netzen unterstützt werden können. Effiziente, robuste und zugleich skalierbare Grundverfahren, welche die Implementierung leistungsfähiger lokationsbasierter Dienste ermöglichen, fehlen gänzlich.

Die vorliegende Dissertation befasst sich mit dem Entwurf, der Implementierung und der Bewertung eines Rahmenwerkes, das grundlegende Verfahren für die Speicherung und Verwaltung von Daten in mobilen Ad-hoc-Netzen bereitstellt. Das Rahmenwerk trägt dabei insbesondere den Merkmalen mobiler Ad-hoc-Netze Rechnung, indem es Strategien und Mechanismen definiert, die diesen Merkmalen wirksam begegnen. Die Dissertation zeigt ferner, wie unter Ausnutzung der vorgestellten Grundverfahren solche Funktionalität bereitgestellt werden kann, die für lokationsbasierte Dienste von Bedeutung ist. Dies wird beispielhaft anhand räumlicher Anfragen gezeigt, wobei insbesondere die Ungenauigkeit der geographischen Positionen von Benutzern in der physischen Welt berücksichtigt wird. Ausführliche Messergebnisse zeigen, dass die betrachteten Verfahren als Grundlage für die Umsetzung einer Vielzahl von lokationsbasierten Diensten in mobilen Ad-hoc-Netzen geeignet sind.