Dokument: Content Location in Sparse Vehicular Ad-Hoc Networks - Feasibility, Implementation, Optimization on the Case of a City Scenario

Titel:	Content Location in Sparse Vehicular Ad-Hoc Networks - Feasibility, Implementation, Optimization on the Case of a City Scenario
Weiterer Titel:	Content Location in Sparse Vehicular Ad-Hoc Networks - Feasibility, Implementation, Optimization on the Case of a City Scenario
URL für Lesezeichen:	https://docserv.uni-duesseldorf.de/servlets/DocumentServlet?id=11293
URN (NBN):	urn:nbn:de:hbz:061-20090520-093714-7
Kollektion:	Dissertationen
Sprache:	Deutsch
Dokumententyp:	Wissenschaftliche Abschlussarbeiten » Dissertation
Medientyp:	Text
Autor:	Wewetzer, Christian [Autor]
Dateien:	[Dateien anzeigen] Adobe PDF [Details] 28,39 MB in einer Datei [ZIP-Datei erzeugen] Dateien vom 14.05.2009 / geändert 15.05.2009
Beitragende:	Prof. Dr. Mauve, Martin [Betreuer/Doktorvater] Prof. Dr. Schöttner, Michael [Gutachter]
Stichwörter:	Vehicular Ad-Hoc Networks, Content Location, Data Aggregation, Bloom Filter
Dewey Dezimal-Klassifikation:	000 Informatik, Informationswissenschaft, allgemeine Werke » 004 Datenverarbeitung; Informatik
Beschreibungen:	Spontane drahtlose Kommunikationsnetze zwischen Fahrzeugen---sogenannte Vehicular Ad-Hoc Networks (VANETs)---ermöglichen vielfältige Anwendungen zur Verbesserung der Verkehrssicherheit, der Verkehrseffizienz und des Fahrerlebnisses. Eine Gemeinsamkeit dieser Anwendungen ist, dass sie auf Informationen basieren, die zwischen den Netzknoten des VANET ausgetauscht werden. Bei genauerem Betrachten unterscheiden sich diese Anwendungen allerdings im zugrundeliegenden Kommunikationsparadigma: Anwendungen können benötigte Informationen proaktiv an andere Netzknoten im VANET verteilen (Push-basierte Kommunikation) oder können Informationen erst dann von anderen Netzteilnehmern anfragen, wenn sie benötigt werden (Pull-basierte Kommunikation). Diese Arbeit betrachtet ein spezielles Problem der Pull-basierten Kommunikation, bei dem ein Fahrzeug mit Interesse an einer bestimmten Information nicht weiss, ob und wo eine geeignete Informationsquelle existiert. Um diesem Problem zu begegnen, wird in dieser Arbeit ein verteilter Dienst entwickelt, der die Suche nach Informationen im VANET ermöglicht. Zum Einstieg wird zunächst in verwandten Forschungsgebieten nach Lösungsansätzen für das Suchproblem recherchiert. Als repräsentative Ansätze ergeben sich Fluten und Hash-Tabellen, welche über die einzelnen Netzknoten oder über geographische Gebiete verteilt sein können. Zur Beurteilung der Eignung dieser Ansätze für VANETs werden mathematische Modelle entwickelt, die eine Berechnung der Sucherfolgsquote und Suchlatenz ermöglichen. Die Modelle kombinieren Zufallsvariablen von Informationsausbreitungsgeschwindigkeit und Informationsausbreitungsdistanz. Für das betrachtete Beispielszenario ergeben sich selbst für Fluten nur geringe Erfolgsaussichten, was zu der Idee führt, die Kommunikation im VANET durch ein Netzwerk von Funkstationen---platziert an den meistbefahrenen Kreuzungen im Szenario---zu unterstützen. Dies führt zu deutlich verbesserten Erfolgsaussichten bei der Informationssuche. Dennoch haben die betrachteten Verfahren Nachteile: Fluten bietet die größten Erfolgschancen, erzeugt aber eine hohe Netzlast. Indexbasierte Ansätze verursachen zwar eine niedrigere Netzlast, dafür sind ihre Erfolgsaussichten deutlich geringer als die der Suche per Fluten. Es ergibt sich die Frage, ob die indexbasierten Verfahren derart verbessert werden können, dass ihre Erfolgsrate mit der von Fluten vergleichbar ist und ob die anhand der theoretischen Modelle errechneten Leistungswerte in einem realen System überhaupt erreicht werden können. Um diese Fragen zu beantworten, ist ein Ziel der Arbeit die Implementierung und Evaluation eines für infrastrukturgestützte VANETs optimierten, indexbasierten Suchverfahrens. Als Grundlage für die unterhalb des Suchverfahrens benötigte Netzwerkschicht wird jedoch zuerst ein Routingalgorithmus definiert. Der Algorithmus ist positionsbasiert und arbeitet nach dem Greedy-Prinzip. Er besitzt Erweiterungen, die den speziellen Herausforderungen in infrastrukturgestützten VANETs begegnen. Die Evaluation des Algorithmus zeigt, dass er im betrachteten Beispielszenario nahezu optimal arbeitet. Im nächsten Schritt werden zwei Suchverfahren konzipiert und implementiert. Das erste Suchverfahren basiert auf einem Index, der über die miteinander vernetzten Funkstationen verteilt ist, wodurch er sich von den zuvor theoretisch modellierten indexbasierten Lösungen unterscheidet. Fahrzeuge registrieren ihre Informationen regelmäßig an ihrer nächstgelegenen Funkstation, von wo aus sie jeweils an die gemäß eines Verteilungsschemas zuständige Funkstation weitergeleitet werden. Funkstationen sind für die Speicherung des Suchindex ideal, weil ihre Positionen fest und sie immer im Netz verfügbar sind. Darüber hinaus beinhaltet ein effizienter Kommunikationspfad zwischen weiter entfernten Fahrzeugen in den meisten Fällen sowieso eine Funkstation, weswegen der zu erwartende zusätzliche Kommunikationsaufwand für die Abfrage des Suchindex niedrig ist. Die Leistungsfähigkeit eines solchen Suchindex ist daher repräsentativ für den Best Case der indexbasierten Suche in infrastrukturgestützten VANETs. Das zweite Verfahren basiert auf Fluten und enthält Strategien zur Vermeidung unnötiger Nachrichtensendevorgänge mit dem Ziel der Netzlastreduktion. Korrekt konfiguriert erreicht das Verfahren dennoch die Erfolgsquote des theoretischen Modells einer Suche basiert auf Fluten; somit kann dessen Sucherfolgsquote als Referenz für das erste Verfahren dienen. Die beiden Suchverfahren werden mittels einer Parameterstudie für ein Beispielszenario konfiguriert und miteinander verglichen. In der besten untersuchten Konfiguration erreicht das indexbasierte Verfahren eine etwas niedrigere Erfolgsquote als Fluten, spart dabei aber einen großen Anteil an Netzlast ein. Die Verteilung des Index über Basisstationen führt zu einer deutlich geringeren Suchlatenz als die in den theoretischen Modellen betrachtete Verteilung über Fahrzeuge. Das implementierte indexbasierte Verfahren kann aber aufgrund des nicht perfekten Routingalgorithmus und alternder Positionsinformationen der beteiligten Fahrzeuge nicht ganz die Erfolgsquoten der theoretischen Modelle erzielen. Die für Fluten ermittelten Leistungswerte sind nah an denen des theoretischen Modells und stützen damit dessen Validität. Nachdem gezeigt wurde, dass das indexbasierte Verfahren in der Praxis eine gute Lösung des Suchproblems in infrastrukturgestützten VANETs bietet, wird abschließend die Netzlast für die Verwaltung eines Suchindex betrachtet. In den üblicherweise verwendeten inversen Indizes berechnen die Netzknoten für jede Information einen Schlüssel in Form eines Hashwertes und registrieren (Schlüssel, Stichwortliste)-Paare im Suchindex. Um die Größe dieser Registrierungsinformationen zu reduzieren, kann ein wohldefiniertes Beschreibungsschema für Informationen eingeführt werden, welches es an einer Information interessierten Knoten erlaubt, die entsprechende Beschreibung zu bestimmen; dann reicht es aus, wenn Informationsquellen nur die Hashwerte ihrer Informationsbeschreibungen registrieren. In dieser Arbeit wird untersucht, wie die bei der Übertragung der Informationsbeschreibungen aufkommende Datenmenge reduziert werden kann. Ein erster Ansatz ist, dass die Netzknoten einfach kürzere Hashwerte versenden. Der Nachteil dieses Ansatzes ist eine erhöhte Wahrscheinlichkeit von falschen Treffern bei der Abfrage des Suchindex: wenn eine angefragte Information nicht registriert ist, aber den gleichen Hashwert wie eine registrierte Information besitzt, wird eine falsche Information angefordert. Als alternative Lösungsmöglichkeit wird in dieser Arbeit die Kodierung der Informationen in Bloom-Filter vorgeschlagen, weil diese in komprimierter Form die theoretisch minimale Größe annehmen. Es wird bewiesen, dass Hashwerte bei gleicher Wahrscheinlichkeit falscher Treffer immer mehr Platz als komprimierte Bloom-Filter benötigen, und gezeigt, dass es einen Punkt gibt, ab dem Hashwerte ebenfalls mehr Platz als unkomprimierte Bloom-Filter benötigen. Darüber hinaus wird ein lokales, opportunistisches Aggregationsverfahren vorgeschlagen, in welchem benachbarte Netzknoten ihre Informationen in einem gemeinsamen Bloom-Filter registrieren. Dies führt zu einer weiteren Reduktion der Wahrscheinlichkeit falscher Treffer im Suchindex. Abschließend wird die Effizienz der Bloom-Filter-basierten Registrierung und der Aggregation in einer Simulationsstudie überprüft. Vehicular ad-hoc networks (VANETs) have many applications improving road safety, traffic efficiency, and driving experience. A commonality of all VANET applications is that they rely on information exchanged among VANET nodes. What differs is the communication paradigm underlying these applications: required information may be distributed proactively (push-based communication), or it may be requested on demand (pull-based communication). This thesis is concerned with a special problem in pull-based communication, where a vehicle in need of certain content is unaware of the existence and location of a suitable information source. To tackle this problem, we propose and study distributed services allowing for content location in VANETs. As a starting point, we look for existing solutions to the search problem that have been proposed in other domains. We identify flooding and hash tables---distributed either among nodes or over geographical regions---as representative search schemes and introduce mathematical models that allow for a calculation of the search latency and success rate of these schemes in VANETs. The models combine random variables of information propagation speed and information propagation distance. Unfortunately, the expected success rates are low in our sample scenario even for flooding-based search, motivating us to introduce a network of base stations at the most frequented road intersections. The base stations improve communication in the VANET and allow content search with high success rate. Nevertheless, flooding as search approach with the highest success rate causes very high network load; index-based methods cause less network load but have a lower success rate. A goal of this thesis is to investigate whether the index-based schemes can be improved to achieve similar success rates as flooding and whether the performance of our theoretical models can be achieved at all in practice. To answer these questions, we design, implement, and evaluate an index-based content location service that is tailored to infrastructure-supported VANETs. As basis of the network layer supporting the content location service, we first define an underlying routing algorithm. The algorithm is a position-based greedy algorithm extended to combat specific routing challenges occuring in infrastructure-supported VANETs. Simulative evaluation shows that the algorithm performs close to optimal in the considered sample scenario. In the next step we design and implement two search schemes. The first scheme relies on an index that is distributed among interlinked base stations, thereby differing from the theoretically modeled index-based search methods. Vehicles periodically register their search keys at the next available base station. Base stations are often involved in communication between distant vehicles, thus the cost in querying the search index is low. The performance of search with help of such an index can thus be regarded as best case performance of index-based search in infrastructure-supported VANETs. The second scheme is a flooding scheme that includes message suppression strategies to save network load but that nevertheless achieves success rates close to that of the theoretical model of flooding if parameterized correctly. We implement and optimize both search schemes in a parameter study in the sample scenario. With the best parameter sets, index-based search achieves a slightly lower success rate than flooding but saves a significant amount of network load. The implemented distribution of the index among base stations results in a latency that is lower than that of the theoretical models, where the index is distributed among vehicles. But due to imperfect routing and aging position information, our implemented scheme cannot achieve the success rate of the theoretical models. The performance of the implemented flooding scheme is close to that of our theoretical model, supporting its validity. After showing that the proposed index-based scheme is a good practical choice for content search in infrastructure-supported VANETs, we are concerned with the network load required for maintenance of such a decentralized index. In commonly used inverted indices, contributing nodes calculate an identifier in form of a hash value for each information item and register (identifier, keyword set)-pairs in the search index. For better space-efficiency, a well-defined description scheme of information items could be established, so that nodes can compute the description of an information item they are interested in; it then suffices to register only the hash key of this description. Our goal is to reduce the amount of data required for this key. As first idea, nodes could simply resort to sending shorter hash keys. The downside of such short hash keys is an increased chance of false-positive look ups in the search index: if a looked-up information item is not registered but has the same hash key as a registered item, other content than intended is requested. As alternative, we propose the encoding of each nodes' information items into Bloom filters because these---if compressed---achieve space-optimality. We prove that lists of hash-keys are always less space-efficient than equivalent compressed Bloom filters and that there is a break-even point from which on these lists of hash-keys are also less space-efficient than uncompressed Bloom filters. Furthermore, we propose a local opportunistic aggregation scheme in which vicinal nodes build a common Bloom filter, leading to an even lower false-positive rate of the search index. Lastly, we demonstrate the effectiveness of Bloom filters and of the aggregation scheme in a simulation study.
Lizenz:	Urheberrechtsschutz
Fachbereich / Einrichtung:	Mathematisch- Naturwissenschaftliche Fakultät » WE Informatik » Rechnernetze
Dokument erstellt am:	20.05.2009
Dateien geändert am:	15.05.2009
Promotionsantrag am:	25.03.2009
Datum der Promotion:	05.05.2009