Decentralized Location-Based Services - Geodemlia.KOM: A Novel Peer-to-Peer Overlay Providing Reliable Search, Persistent Storage, and Efficient Content Dissemination for Location-based Services

Christian Groß

Thursday September 04, 2014

English abstract:

In recent years, location-based services have gained a lot of importance due to the proliferation of position-aware devices and the ubiquitous availability of wireless Internet access. Location-based services are characterized by the fact that they store and process data that are bound to a certain geographical location. The wide-spread interest in location-based services as well as their distributed nature of locationbased data generation and consumption has resulted in a plethora of approaches for decentralized location-based services based on the Peer-to-Peer paradigm. PeertoPeer stands for a communication paradigm where equal users termed peers share their resources without any central instance to achieve a higher value service. In particular, the unique combination of data and geographical locations as well as the interest in searching for it has resulted in a variety of approaches for Peer-to-Peer location-based search. These approaches allow for the search of location-based data that fall into a given geographical area. Thereby, the search is realized in a fully decentralized way with peers providing their resources in terms of computing power, bandwidth, and storage capacity. In this context, Peer-to-Peer location-based services face a variety of challenges. First, the frequent join and leave of peers known as churn causes search mechanisms to return incomplete results. Second, the persistence of location-based data cannot be guaranteed as peers storing the data go offline. Third, the asymmetric Internet connections of peers make the dissemination and exchange of larger location-based data such as high resolution pictures or short video clips inefficient and time-consuming.
In order to solve these problems, this thesis provides the following contributions: First, we conduct a qualitative analysis of existing approaches for decentralized location-based search. We identify the relevant design decisions and discuss their influence on the performance and costs of the entire system. Subsequently, based on the gained insights, a novel Peer-to-Peer overlay termed Geodemlia.KOM is developed and its most important components GeoSearch.KOM, GeoReplica.KOM, and GeoSwarm.KOM are presented in detail. Unlike existing approaches Geodemlia. KOM uses a non-hierarchical and semi-structured overlay topology, which makes the overlay less susceptible to churn and guarantees a reliable area search. Furthermore, its built-in replication mechanism ensures the persistence of location-based data even under high churn rates. Finally, its multi-source content dissemination approach allows for the efficient exchange of location-based data over asymmetric links in the Internet. To demonstrate the superiority of Geodemlia.KOM, an in-depth performance and cost analysis is conducted using discrete event-based simulations. Furthermore, we compare Geodemlia.KOM against two other existing state-of-the-art systems for location-based search and show that it significantly outperforms the other two systems. We deploy Geodemlia.KOM in the G-Lab/ToMaTo testbed, which is based on the PlanetLab platform, and show that the simulative results can be confirmed in a real-world scenario.

German abstract:

Lokationsbasierte Dienste haben in den letzten Jahren stark an Bedeutung gewonnen, nicht zuletzt ausgelöst durch die starke Verbreitung mobiler Endgeräte, welche mit Techniken zur Standortbestimmung ausgetattet sind. Lokationsbasierte Dienste zeichnen sich unter anderem dadurch aus, dass von ihnen verarbeitete Daten mit einem geographischen Ortsbezug versehen sind. Diese einzigartige Verknüpfung von Daten und geographischen Positionen hat in den vergangenen Jahren zu einer ganzen Reihe von Peer-to-Peer-basierten Ansätzen für lokationsbasierte Suche geführt. Diese erlauben es in Abhängigkeit von einer gegebenen geographischen Position oder Region nach lokationsbasierten Daten zu suchen. Hierbei erfolgt die Diensterbringung vollständig dezentral, indem teilnehmende Peers ihre Ressourcen in Form von Rechenleistung, Bandbreite und Speicher dem System zur Verfügung stellen. Eine der zentralen Herausforderungen stellt dabei die Zuverlässigkeit der Diensterbringung sowie die Stabilität des Gesamtsystems dar, da die teilnehmenden Peers das System jederzeit betreten oder verlassen können. Dieses als Churn bezeichnete Phänomen hat zur Folge, dass gängige Peer-to-Peer Ansätze für lokationsbasierte Suche nur unzureichende Suchresultate zurückliefern und signifikante Stabilitätsprobleme aufweisen. Zudem verfügen die gängigen Ansätze über keinerlei oder nur unzureichende Replikationsverfahren, sodass das Verlassen von Peers zum Verlust von im System gespeicherten Daten führt. Ein weiteres Problem stellen die asymmetrischen Bandbreiten heutiger Internetzugänge dar, welche eine effiziente Verteilung von lokationsbasierten Daten erschweren. Insbesondere größere lokationsbasierte Daten, wie zum Beispiel hochaufgelöste Bilder oder kurze Videoclips, können auf Grund des geringen Verhältnisses von Upload- zu Downloadbandbreiten zwischen Peers nur langsam und ineffizient verteilt werden.
Um die genannten Probleme zu lösen, wird im Rahmen dieser Arbeit zunächst eine qualitative Analyse von existierenden Ansätzen für lokationsbasierte Suche durchgeführt. Hierzu werden alle relevanten Designentscheidungen identifiziert und hinsichtlich ihres Einflusses auf die Leistungsfähigkeit und Kosten des Gesamtsystems bewertet. Auf Basis der gewonnen Erkenntnisse wird anschließend ein neuartiges Design für ein semistrukturiertes Peer-to-Peer Suchoverlay mit Namen Geodemlia.KOM erarbeitet und vorgestellt. Sogar unter hohen Churnraten als auch asymmetrischen Bandbreitenbedingungen ermöglicht das System eine zuverlässige Suche nach lokationsbasierten Daten, deren persistente Speicherung und effiziente Verteilung. Um die genannten Eigenschaften von Geodemlia.KOM zu zeigen, wird das System zunächst mittels diskret ereignisbasierter Simulation evaluiert und eine geeignete Systemparameterkonfiguration abgeleitet. Anschließend wird das System mit zwei Ansätzen aus den verwandten Arbeiten verglichen und gezeigt, dass Geodemlia.KOM die Leistungsfähigkeit dieser signifikant übertrifft. Um die simulativen Ergebnisse zu überprüfen, werden Testbedexperimente mittels der Experimentalplattform G-Lab/ToMaTo, einer Weiterentwicklung der PlanetLab Plattform, durchgeführt.

PhD Theses