Avoiding the Gridlock -- Information Dissemination in Vehicular Networks

In dieser Arbeit wird untersucht, wie sich Informationen in einem aus Fahrzeugen bestehenden, drahtlosen Ad-Hoc Netzwerk verbreiten konnen. 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 uber die aktuelle Strasenlage. Diese Beobachtungen werden von vielen Fahrzeugen zu vielen Fahrzeugen geschickt. Es entsteht somit eine n-zu-m-Kommunikation mit n Sendern und m Empfangern, wobei sowohl die Beobachtungen als auch die Sender und Empfanger uber die Zeit veranderlich sind. Das Ziel dieser Arbeit ist es, Methoden zu entwickeln, um diese Informationen an die Teilnehmer des Netzwerks zu verteilen. Bei diesen konnen sie von einem Navigationssystem als Eingabe fur die Routenberechnung verwendet werden. Wichtige Fragestellungen betreffen zum einen die Reichweite des Informationsaustauschs sowie zum anderen die Geschwindigkeit, mit der sich Informationen ausbreiten konnen. Ein wichtiges Hilfsmittel bei der Analyse von Mechanismen und Anwendungen fur VANETs stellt die Verwendung von Simulatoren dar. Aufgrund der immensen Anforderungen an diese Simulatoren, die Realitat so genau wie moglich abzubilden, dabei aber eine moglichst 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 Stadten 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 fur den jeweils anderen Simulator. Dadurch ist es beispielsweise moglich, die Geschwindigkeit einzelner Fahrzeugen (in einem Vehrkehrssimulator) in Abhangigkeit von erhaltenen Datenpaketen (eines Netzwerksimulators) zu beeinflussen. Die Simulatorkopplung besteht aus dem Netzwerksimulator ns-2 sowie dem Verkehrssimulator VISSIM und stellt das zentrale Evaluationswerkzeug fur alle in dieser Arbeit vorgestellten Protokolle und Algorithmen dar. Darauf folgend werden die beiden zentralen Herausforderungen der Informationsverbreitung in solchen Netzwerken formuliert: i) beschrankte Konnektivitat und ii) beschrankte Bandbreite. Die erste Herausforderung betrifft die Fragestellung, wie sich Informationen generell und mit welcher Geschwindigkeit in einem VANET ausbreiten konnen. Von elementarer Bedeutung hierbei ist, dass die verwendete Technologie noch nicht weit verbreitet ist. Insbesondere wahrend eines Einfuhrungsszenarios wird die Penetrationsrate der Fahrzeuge, die mit Geraten zur Kommunikation ausgestattet sein werden, sehr gering sein. Bezogen auf das untersuchte Ad-Hoc Netzwerk lasst dies darauf schliesen, dass das Netz durch Partitionierung in viele einzelne Teile aufgespalten sein wird. Durch diese Beschrankung ist eine schnelle und zuverlassige Verbreitung von Informationen nicht gewahrleistet. Basierend auf dieser Erkenntnis wird das Konzept der Stutzstellen vorgestellt. Diese stellen zusatzliche Infrastruktur fur das ansonsten rein kooperative, selbstandige Netzwerk dar. Sie bilden gewissermasen ein Ruckgrat fur das allein auf Fahrzeugen basierende VANET. Da der Einsatz dieser Gerate mit zusatzlichem Aufwand verbunden ist, wird untersucht, welche Eigenschaften diese Stutzstellen besitzen mussen. Weiterhin wird analysiert, wie viele Stutzstellen mindestens notig sind, um die Informationsverteilung positiv zu beeinflussen. Anhand einer Beispielapplikation wird gezeigt, wie bereits mit Hilfe weniger Stutzstellen eine gute und schnelle Informationsverteilung bei sehr geringer Penetrationsrate uber grose Strecken hinweg gelingen kann. Durch die vielen existierenden Datenquellen, die mit zunehmender Netzwerkgrose weiter anwachsen, nimmt auch der Umfang der zu verteilenden Daten stark zu. Um die zweite Herausforderung der beschrankten Bandbreite anzugehen, wird untersucht, auf welche Weise die Datenmenge zunimmt. Es werden Schranken fur Verfahren zur Informationsverteilung bestimmt, um die Kapazitat des Netzwerkes nicht zu stark zu beanspruchen. Diese Schranken begrunden den Einsatz von Aggregationsverfahren, die Informationen mit zunehmender Distanz zusammenfassen, und zeigen gleichzeitig wie stark die Aggregation der Daten uber eine bestimmte Distanz durchgefuhrt werden muss. Aufbauend auf diesen Erkenntnissen wird ein Verfahren vorgestellt, welches diese beiden Herausforderungen bewaltigt. Insbesondere wird ein Aggregationsverfahren fur Stadtszenarien prasentiert. Diese Szenarien sind gekennzeichnet durch ihre Zweidimensionalitat der zu betrachtenden Segmente bzw. Strasen. Informationen uber Strasenabschnitte werden sinnvoll zusammengefasst und uber 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 moglichst gute Platzierungen fur die oben genannten Stutzstellen zu finden. Da der mogliche Losungsraum sehr schnell sehr gros werden kann, wird ein genetischer Algorithmus fur die Losung des Optimierungsproblems benutzt. Durch die prototypische Implementierung eines Navigationssystems wird die Vorteilhaftigkeit des Aggregationsverfahrens in Zusammenspiel mit der optimierten Stutzstellenplatzierung gezeigt. Aggregationsverfahren bewaltigen allerdings nicht nur die genannten Herausforderungen, sondern sind auch Ursache fur eine weitere Herausforderung, die in Verbindung mit dem Verschmelzen mehrerer Aggregate auftritt. Wenn ein Knoten zwei Datenpakete empfangt, die denselben Bereich beschreiben, muss entschieden werden, welches Aggregat "bessere" Informationen beinhaltet. Standardmasig werden daher Zeitstempel vergeben, um die Aktualitat der Aggregate und ihrer Inhalte zu kennzeichnen. Falls die Aggregation allerdings auf Flachen beruht und ein Knoten mehrere Aggregate mit sich teilweise uberlappenden Gebieten erhalt, kann mittels deterministischer Standardansatze nicht entschieden werden, wie diese Informationen zusammengefasst werden konnen. Im Ergebnis wird entweder ein falsches Aggregat berechnet oder es kann nur eines der beiden Aggregate fur 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 konnen. Das neue Aggregat wird immer die Vereinigung der beiden alten Aggregate darstellen. Dabei ist es weder notwendig, dass sich Gebiete uberlappen noch mussen die einzelnen Inhalte der Aggregate bekannt sein.