Dokument: Avoiding the Gridlock -- Information Dissemination in Vehicular Networks

Titel:	Avoiding the Gridlock -- Information Dissemination in Vehicular Networks
URL für Lesezeichen:	https://docserv.uni-duesseldorf.de/servlets/DocumentServlet?id=9714
URN (NBN):	urn:nbn:de:hbz:061-20081127-135249-5
Kollektion:	Dissertationen
Sprache:	Englisch
Dokumententyp:	Wissenschaftliche Abschlussarbeiten » Dissertation
Medientyp:	Text
Autor:	Lochert, Christian [Autor]
Dateien:	[Dateien anzeigen] Adobe PDF [Details] 2,32 MB in einer Datei [ZIP-Datei erzeugen] Dateien vom 26.11.2008 / geändert 26.11.2008
Beitragende:	Prof. Dr. Mauve, Martin [Betreuer/Doktorvater] Prof. Dr. Hartenstein, Hannes [Gutachter]
Stichwörter:	Information Dissemination, VANET, Aggregation, Vehicular Networks
Dewey Dezimal-Klassifikation:	000 Informatik, Informationswissenschaft, allgemeine Werke
Beschreibungen:	In dieser Arbeit wird untersucht, wie sich Informationen in einem aus Fahrzeugen bestehenden, drahtlosen Ad-Hoc Netzwerk verbreiten können. Fahrzeuge kommunizieren mittels entsprechender Funktechnologie wie beispielsweise IEEE 802.11 direkt miteinander und bilden dadurch ein so genanntes Vehicular Ad-Hoc Network (VANET). Fahrzeuge machen autonom Beobachtungen über die aktuelle Straßenlage. Diese Beobachtungen werden von vielen Fahrzeugen zu vielen Fahrzeugen geschickt. Es entsteht somit eine n-zu-m-Kommunikation mit n Sendern und m Empfängern, wobei sowohl die Beobachtungen als auch die Sender und Empfänger über die Zeit veränderlich sind. Das Ziel dieser Arbeit ist es, Methoden zu entwickeln, um diese Informationen an die Teilnehmer des Netzwerks zu verteilen. Bei diesen können sie von einem Navigationssystem als Eingabe für die Routenberechnung verwendet werden. Wichtige Fragestellungen betreffen zum einen die Reichweite des Informationsaustauschs sowie zum anderen die Geschwindigkeit, mit der sich Informationen ausbreiten können. Ein wichtiges Hilfsmittel bei der Analyse von Mechanismen und Anwendungen für VANETs stellt die Verwendung von Simulatoren dar. Aufgrund der immensen Anforderungen an diese Simulatoren, die Realität so genau wie möglich abzubilden, dabei aber eine möglichst hohe Effizienz zu erreichen, existieren nur einige wenige Spezialsimulatoren. Diese dienen beispielsweise dazu, die Simulation von Daten und Signalen in Netzwerken oder die Bewegung von Fahrzeugen in Städten oder auf Autobahnen zu modellieren. Im ersten Schritt dieser Arbeit wird gezeigt, wie durch Kopplung einzelner Simulatoren ein Meta-Simulator erstellt werden kann. Dieser Simulator benutzt die (Teil-)Ergebnisse eines Spezialsimulators als Eingabe für den jeweils anderen Simulator. Dadurch ist es beispielsweise möglich, die Geschwindigkeit einzelner Fahrzeugen (in einem Vehrkehrssimulator) in Abhängigkeit von erhaltenen Datenpaketen (eines Netzwerksimulators) zu beeinflussen. Die Simulatorkopplung besteht aus dem Netzwerksimulator ns-2 sowie dem Verkehrssimulator VISSIM und stellt das zentrale Evaluationswerkzeug für alle in dieser Arbeit vorgestellten Protokolle und Algorithmen dar. Darauf folgend werden die beiden zentralen Herausforderungen der Informationsverbreitung in solchen Netzwerken formuliert: i) beschränkte Konnektivität und ii) beschränkte Bandbreite. Die erste Herausforderung betrifft die Fragestellung, wie sich Informationen generell und mit welcher Geschwindigkeit in einem VANET ausbreiten können. Von elementarer Bedeutung hierbei ist, dass die verwendete Technologie noch nicht weit verbreitet ist. Insbesondere während eines Einführungsszenarios wird die Penetrationsrate der Fahrzeuge, die mit Geräten zur Kommunikation ausgestattet sein werden, sehr gering sein. Bezogen auf das untersuchte Ad-Hoc Netzwerk lässt dies darauf schließen, dass das Netz durch Partitionierung in viele einzelne Teile aufgespalten sein wird. Durch diese Beschränkung ist eine schnelle und zuverlässige Verbreitung von Informationen nicht gewährleistet. Basierend auf dieser Erkenntnis wird das Konzept der Stützstellen vorgestellt. Diese stellen zusätzliche Infrastruktur für das ansonsten rein kooperative, selbständige Netzwerk dar. Sie bilden gewissermaßen ein Rückgrat für das allein auf Fahrzeugen basierende VANET. Da der Einsatz dieser Geräte mit zusätzlichem Aufwand verbunden ist, wird untersucht, welche Eigenschaften diese Stützstellen besitzen müssen. Weiterhin wird analysiert, wie viele Stützstellen mindestens nötig sind, um die Informationsverteilung positiv zu beeinflussen. Anhand einer Beispielapplikation wird gezeigt, wie bereits mit Hilfe weniger Stützstellen eine gute und schnelle Informationsverteilung bei sehr geringer Penetrationsrate über große Strecken hinweg gelingen kann. Durch die vielen existierenden Datenquellen, die mit zunehmender Netzwerkgröße weiter anwachsen, nimmt auch der Umfang der zu verteilenden Daten stark zu. Um die zweite Herausforderung der beschränkten Bandbreite anzugehen, wird untersucht, auf welche Weise die Datenmenge zunimmt. Es werden Schranken für Verfahren zur Informationsverteilung bestimmt, um die Kapazität des Netzwerkes nicht zu stark zu beanspruchen. Diese Schranken begründen den Einsatz von Aggregationsverfahren, die Informationen mit zunehmender Distanz zusammenfassen, und zeigen gleichzeitig wie stark die Aggregation der Daten über eine bestimmte Distanz durchgeführt werden muss. Aufbauend auf diesen Erkenntnissen wird ein Verfahren vorgestellt, welches diese beiden Herausforderungen bewältigt. Insbesondere wird ein Aggregationsverfahren für Stadtszenarien präsentiert. Diese Szenarien sind gekennzeichnet durch ihre Zweidimensionalität der zu betrachtenden Segmente bzw. Straßen. Informationen über Straßenabschnitte werden sinnvoll zusammengefasst und über weite Strecken verteilt. Die zentrale Eigenschaft dieses Aggregationsmechanismus besteht aus einer mehrschichtigen, hierarchischen Aggregation basierend auf dem Landmark-Prinzip. Um dem Problem der geringen Ausstattungsraten zu begegnen, wird ein Optimierungsverfahren vorgestellt, um möglichst gute Platzierungen für die oben genannten Stützstellen zu finden. Da der mögliche Lösungsraum sehr schnell sehr groß werden kann, wird ein genetischer Algorithmus für die Lösung des Optimierungsproblems benutzt. Durch die prototypische Implementierung eines Navigationssystems wird die Vorteilhaftigkeit des Aggregationsverfahrens in Zusammenspiel mit der optimierten Stützstellenplatzierung gezeigt. Aggregationsverfahren bewältigen allerdings nicht nur die genannten Herausforderungen, sondern sind auch Ursache für eine weitere Herausforderung, die in Verbindung mit dem Verschmelzen mehrerer Aggregate auftritt. Wenn ein Knoten zwei Datenpakete empfängt, die denselben Bereich beschreiben, muss entschieden werden, welches Aggregat "bessere" Informationen beinhaltet. Standardmäßig werden daher Zeitstempel vergeben, um die Aktualität der Aggregate und ihrer Inhalte zu kennzeichnen. Falls die Aggregation allerdings auf Flächen beruht und ein Knoten mehrere Aggregate mit sich teilweise überlappenden Gebieten erhält, kann mittels deterministischer Standardansätze nicht entschieden werden, wie diese Informationen zusammengefasst werden können. Im Ergebnis wird entweder ein falsches Aggregat berechnet oder es kann nur eines der beiden Aggregate für die weitere Verwendung herangezogen werden. In dem letzten Beitrag dieser Arbeit wird als Alternative dazu ein probabilistisches Verfahren vorgestellt. Die zentrale Eigenschaft dieses hierarchischen Aggregationsverfahrens ist, dass Aggregate implizit zusammengefasst werden können. Das neue Aggregat wird immer die Vereinigung der beiden alten Aggregate darstellen. Dabei ist es weder notwendig, dass sich Gebiete überlappen noch müssen die einzelnen Inhalte der Aggregate bekannt sein. In this thesis we analyze information dissemination in the context of vehicle-to-vehicle communication. Cars can communicate with each other by using radio technologies like IEEE 802.11. They implicitly form a so called Vehicular Ad-Hoc Network (VANET). Vehicles autonomously make observations about the current traffic situation of a road. In order to allow nodes to create an overview of the whole scenario these observations should be sent by many vehicles to many other vehicles probably far away. One goal of this thesis is thus to analyze the process of information dissemination as well as to provide mechanisms for the information dissemination. A navigation system may then use this data to calculate the fastest route based on the current traffic situation. In order to meet the requirements of such a system the information has to be transmitted in a timely fashion. It is furthermore important to reach distant regions to inform other vehicles in due time. In the analysis of mechanisms and applications for VANETs simulators are an important building block. However, it is a hard challenge to model the reality as precise as possible while gaining high efficiency during the execution of simulations. Only special simulators developed for one single purpose are able to deal with these demands. In the first contribution we present results of coupling different specialized simulators. We develop a meta-simulator environment which allows one simulator to interact with another simulator by exchanging (partial) results or to react upon the input of these results. We are thus now able to analyze the implications of information dissemination in a network for instance on the movement of vehicles in a given scenario. The following contribution poses in detail the two major challenges of information dissemination in VANETs: i) limited connectivity and ii) limited bandwidth. The first challenge corresponds to the general feasibility of information dissemination in a VANET and its dissemination speed. Especially during the rollout of this technology this is an important aspect to consider. In an early stage the penetration ratio of vehicles equipped with VANET devices will be low. Regarding the ad-hoc network, it becomes obvious that a lot of partitions will exist that hamper a proper, fast and reliable spread of data. In order to deal with these limitations during the rollout phase we introduce the concept of (stationary) supporting units. These supporting units represent additional infrastructure devices. They build a backbone for the VANET which is formed by vehicles and their ad-hoc communication. Due to the additional costs we analyze the minimum necessary deployment of these units. We further demonstrate by the means of an example application that only few of these supporting units are needed to improve the performance of information dissemination significantly by spanning distant regions in a timely fashion. By using multiple vehicles as data sources as well as with an increasing size of the network the amount of data, that is to be disseminated, grows significantly. In order to tackle the second challenge---limited bandwidth---we analyze how this increase in the amount of data looks like. We determine lower and upper bounds for the considered limitations of the bandwidth. These bounds motivate the usage of aggregation mechanisms. The main task of these mechanisms is to subsume information in relation to an increasing distance. Following these insights we present an approach which tackles both mentioned challenges. In particular, we present an aggregation mechanism dealing with the additional challenge of a city scenario. This specific type of scenario is defined by its two-dimensional characteristics of the considered topology or streets, respectively. By using this aggregation mechanism information about street segments can be subsumed in an efficient and meaningful manner. The algorithm is implemented by a multilayered and hierarchical aggregation based on the landmark principle. In addition, we present an optimization method for the proper placement of supporting units in order to deal with the low amount of equipped vehicles. Due to the rapid increase of the possible space of solutions we propose to make use of a genetic algorithm in order to solve this hard optimization problem. By implementing a prototype navigation system we underline the performance of the aggregation scheme in combination with the placement of supporting units. A distinct challenge of aggregation mechanisms is the merging of aggregates. For instance when one node receives two different aggregates describing the same area it has to decide which one of them contains "better" information. Thus, the last contribution of this thesis constitutes a probabilistic approach for the representation of aggregates. The central property of this hierarchical scheme is that overlapping aggregates can be subsumed implicitly. It is therefore not necessary to know the distinct entries of the aggregate. We show by means of an example application the benefit of this approach.
Lizenz:	Urheberrechtsschutz
Fachbereich / Einrichtung:	Mathematisch- Naturwissenschaftliche Fakultät » WE Informatik » Rechnernetze
Dokument erstellt am:	27.11.2008
Dateien geändert am:	26.11.2008
Promotionsantrag am:	21.10.2008
Datum der Promotion:	24.11.2008