Dezentrale und dynamische Routenplanung mit OverDrive
- Forschungsthema:P2P und Overlay-Netze / Algorithm Engineering
- Typ:Master-/Diplomarbeit
- Datum:Jun 2014
- Betreuung:
Martin Florian, Moritz Baum
- Bearbeitung:Matthias Preis
-
Beschreibung
Im Rahmen des iZEUS-Projekts wird an mehreren Instituten des KIT an Konzepten und Diensten für Smart Traffic, also dem intelligenten Fahrzeugverkehr der Zukunft, geforscht. Am Institut für Telematik werden z.B. dezentrale Overlay-basierte Kommunikationsstrukturen für Smart-Traffic-Anwendungen entwickelt. Das Institut für Theoretische Informatik beschäftigt sich im Rahmen des Projekts mit effizienten Algorithmen zur Planung verbrauchsoptimaler Routen für Elektrofahrzeuge. Als Berührungspunkt dieser beide Bereiche soll nun ein Konzept für dynamische Routenplanung entwickelt werden, wobei Informationen zu aktuellen Verkehrsereignissen (z.B. Stau) über ein dezentrales P2P-System zwischen einzelnen Verkehrsteilnehmern ausgetauscht werden. Die Routenplanung wird von den Verkehrsteilnehmern selbst ausgeführt und soll sich dynamisch an Straßenbegebenheiten anpassen können, ohne von einer zentralen Instanz mit globaler Sicht auf die Verkehrssituation abhängig zu sein.
Aufgabenstellung
In dieser Arbeit soll ein Konzept zur dynamischen Routenplanung entwickelt und simulativ evaluiert wer-den, bei dem aktuelle Verkehrsinformationen über das GeoCast-Overlay OverDrive bezogen werden. Dazu muss zunächst das von OverDrive verwendete Verkehrsmodell um besondere Verkehrsereignisse wie Staus oder Straßensperrungen erweitert werden. Darauf aufbauend gliedert sich die Arbeit in zwei ineinander greifende Teilbereiche: Zum einem müssen Algorithmen entworfen werden, um dynamische Routenplanung mit minimalem verfügbaren Wissen zu ermöglichen. Zum anderen müssen geeignete Ansätze entwickelt werden, um relevante Verkehrsinformationen effizient, also insbesondere mit geringem Kommunikationsaufwand, an interessierte Verkehrsteilnehmer zu verteilen.Ein Prototyp des entwickelten Konzepts soll für den Overlay-Simulator OverSim implementiert werden. Darauf folgt die Evaluation des Ansatzes, wobei vor allem die Qualität der gewählten Routen und die Bandbreitenanforderungen pro OverDrive-Teilnehmer betrachtet werden sollen. Abschließend erfolgt die ausführliche Dokumentation und Präsentation der Arbeit.
Arbeitsumgebung
Jederzeit geöffneter Institutspoolraum, leistungsstarke Simulationsrechner und Kaffeemaschine
Voraussetzungen
Programmierkenntnisse (C++) sollten vorhanden sein. Fundierte algorithmische Kenntnisse sowie Kenntnisse in den Bereichen Peer-to-Peer und Overlay-Netze sind hilfreich.