Dokument: Kooperative Peer-to-Peer-basierte Verkehrsinformationssysteme

Titel:	Kooperative Peer-to-Peer-basierte Verkehrsinformationssysteme
Weiterer Titel:	Cooperative Traffic Information Systems Based on Peer-to-Peer Networks
URL für Lesezeichen:	https://docserv.uni-duesseldorf.de/servlets/DocumentServlet?id=17569
URN (NBN):	urn:nbn:de:hbz:061-20110329-090612-3
Kollektion:	Dissertationen
Sprache:	Englisch
Dokumententyp:	Wissenschaftliche Abschlussarbeiten » Dissertation
Medientyp:	Text
Autor:	Rybicki, Jedrzej [Autor]
Dateien:	[Dateien anzeigen] Adobe PDF [Details] 4,31 MB in einer Datei [ZIP-Datei erzeugen] Dateien vom 19.03.2011 / geändert 19.03.2011
Beitragende:	Dr. Scheuermann, Björn [Betreuer/Doktorvater] Prof. Dr. Mauve, Martin [Gutachter]
Dewey Dezimal-Klassifikation:	000 Informatik, Informationswissenschaft, allgemeine Werke » 004 Datenverarbeitung; Informatik
Beschreibungen:	This thesis deals with cooperative traffic information systems, which support the driver of a car in selecting a route, based on traffic information collected by other cars. System participants contribute measurements of the traffic situation in their vicinity (e. g., current traffic flow speed) and use the measurements made by other drivers to find the fastest route to their destination with regard to the current conditions. Such systems help avoid traffic jams, highly congested roads, place of accidents and other unexpected deterioration. The communication pattern of the discussed application is quite challenging: continuously updated data (i.e., description of the current traffic conditions) are to be made available to multiple participants spread over relatively large geographical areas. Cooperative traffic information systems have primarily been discussed in the context of direct, ad-hoc communication between cars. We formally show in this thesis that a very special communication properties of the discussed application do not fit into the constrained capacity offered by mobile ad-hoc networks. Consequently, this work proposes an alternative design, based on a peer-to-peer paradigm and cellular networks, to efficiently distribute traffic information. Since the data maintained in a cooperative traffic information system have a very specific structure, it is particularly profitable---in terms of bandwidth consumption and latency---to tailor the system to this specific application domain instead of re-using generic peer-to-peer approaches. In our work we shall point out the limitations of generic P2P networks when it comes to the exchange of dynamic traffic related data. Then we will present Peer-to-Peer-based cooperative Traffic Information System: PeerTIS. That is an adjusted generic peer-to-peer overlay, which accounts for the special properties of the discussed application. In addition to a detailed description of such adjustments, we will also provide evaluation showing the technical feasibility of the peer-to-peer-based traffic information system. Although PeerTIS is a step forward towards an efficient implementation of a working inter-vehicular application, it still possesses some limitations. In particular, the unfair load distribution among the participants of PeerTIS might undermine the idea of cooperative systems, with all the participants being equal in rights and obligations. Thus latter in the thesis we will take a significant step further and develop GraphTIS---a peer-to-peer network specifically designed to manage traffic information. It is a novel peer-to-peer system that has specifically been designed to support traffic information systems. It preserves the structure of the stored data, allowing for a quick and efficient retrieval of the data, at the same time avoiding the pitfalls of PeerTIS. The efficient retrieval of the data stored in a traffic information system is only the first part of the complete solution. The data stored in the system are dynamic, thus a mechanism for keeping in touch with the updates must also be developed and implemented. In this thesis we will present a novel approach to achieve this aim. We will extend our peer-to-peer system with a publish/subscribe module to distribute the updates efficiently. The efficiency and feasibility of our algorithms are important properties of the proposed solution, but even more important is the assessment of the potential benefit for the user which our system can offer when deployed. We will devote a separate chapter of the work to the problem of dynamic routing with availability of traffic information. We discuss two possible routing algorithms and compare them in a simulation environment composed of a network simulator and the fully-fledged car traffic simulator SUMO. By using a traffic simulator and maps of a real agglomeration we increase the plausibility of the evaluation. Our results show that when deployed, the system can indeed bring benefits to its users by reducing the average travel times of the simulated cars. Das Thema dieser Dissertation sind kooperative Verkehrsinformationssysteme. Solche Systeme unterstützen den Fahrer bei der Auswahl seiner Route. Dabei wird die von anderen Teilnehmern beobachtete Verkehrssituation bei der Routenplanung durch ein Navigationssystem berücksichtigt. Alle Teilnehmer laden die Messungen der Verkehrssituation in ihrer Umgebung (z.B.: ihre aktuelle Geschwindigkeit) im das System hoch. Mit solchen Daten ist es dann möglich Staus, stark überlastete Straßen oder Unfallstellen zu vermeiden. Das Ziel dieser Arbeit ist es, Methoden zu entwickeln, um diese Informationen an die Teilnehmer des Netzwerks effizient zu verteilen. Das Kommunikationsmuster der betrachteten Anwendung ist sehr anspruchsvoll: Ständig aktualisierte Daten (die Messungen der aktuellen Verkehrssituation) werden an viele Teilnehmer in relativ großen geographischen Gebieten verteilt. Bisher wurde als Grundlage für solche Anwendungen vor allem die direkte Kommunikation zwischen Fahrzeugen untersucht. In dieser Arbeit zeigen wir formal, dass die besonderen Eigenschaften der diskutierten Anwendung die Kapazität des Netzwerkes sehr stark beanspruchen. Was zu hohen Latenzen bzw. Detailverlust der Daten führen kann. Deswegen schlagen wir eine neue Art von Verkehrsinformationssystemen vor. Hier werden die Verkehrsmessungen über infrastrukturbasierte Funktechnologien wie UMTS oder GSM in ein Peer-to-Peer-Overlay übermittelt und dort gespeichert. In einem solchen System werden die Verkehrsmessungen nicht nur kooperativ gesammelt, sondern auch verwaltet. Die Daten in einem kooperativen Verkehrsinformationssystem haben eine sehr spezifische Struktur, die ungefähr die Struktur der Straßennetzes widerspiegelt. Im ersten Teil der Arbeit zeigen wir, dass es besonders profitabel ist --- in Bezug auf Bandbreite und Latenz --- das System so zu bauen, dass diese spezifische Struktur erhalten bleibt. Wir präsentieren PeerTIS: ein angepasstes Peer-to-Peer-Overlay, das auf die speziellen Eigenschaften der Anwendung zugeschnitten ist. Neben der detaillierten Beschreibung dieser Anpassungen belegen wir in einer simulativen Studie die technische Machbarkeit des peer-to-peer-basierten Verkehrsinformationssystems. Wie sich herausstellt, weist schon dieser strukturell vergleichsweise einfache Ansatz sehr vorteilhafte Eigenschaften auf, welche seine prinzipielle Eignung für den Aufbau eines Peer-to-Peer-Verkehrsinformationssystems unterstreichen. Obwohl PeerTIS einen Schritt in Richtung einer effizienten Implementierung der Anwendung darstellt, leidet es unter einigen Einschränkungen. Insbesondere die unfaire Lastverteilung zwischen den Teilnehmern in PeerTIS wird zum Problem. Solche Unfairness kann die Idee des kooperativen Systems im Gefahr bringen. Es kann nämlich zu einer Situation führen in der manche Peers deutlich mehr Aufwand betreiben müssen, obwohl alle Teilnehmer die gleiche Daten im Tausch bekommen. Auf Basis der mit dem ersten Ansatz gewonnenen Erfahrungen gehen wir in einem zweiten Entwurf noch einen Schritt weiter: Um die Struktur der gespeicherten Daten noch besser auszunutzen wird ein neues Overlay entwickelt. Wir haben erkannt, dass für eine effiziente Speicherung und Bearbeitung der Anfragemuster der Anwendung die Topologie des Straßennetzes sehr wichtig ist. Deswegen wird in dem weiteren Teil der Arbeit ein neues System GraphTIS entwickelt --- ein Peer-to-Peer-Netzwerk speziell für die Verwaltung von Verkehrsinformationen. Dieses Peer-to-Peer-Netzwerk unterscheidet sich in wenigstens einer Hinsicht fundamental von existierenden Peer-to-Peer-Systemen. Es erhält die Struktur der gespeicherten Daten, in dem es einen Straßengraphen effizient verteilt speichert. Dadurch ermöglicht es ein effizientes und schnelles Auffinden der Daten, gleichzeitig vermeidet es die Lastverteilungsprobleme von PeerTIS. Das effiziente Auffinden der Daten im Verkehrsinformationssystem ist nur der erste Teil der vorgeschlagene Lösung. Die im System gespeichert Daten sind dynamisch, weil die Verkehrslage sich über die Zeit ändert. Deswegen wird ein Mechanismus für eine reibungslose und effiziente Verteilung der Änderungen benötigt. In dieser Arbeit präsentieren wir einen neuen Ansatz, das zu gewährleisten. Wir verwenden dabei das Publish/Subscribe-Paradigma. Unsere Evaluation zeigt, dass der Ansatz zu einer deutlichen Reduktion der Bandbreite führt. Die Effizienz und prinzipielle Machbarkeit unserer Algorithmen sind wichtige Eigenschaften der vorgeschlagenen Lösung, aber noch wichtiger ist die Evaluation der potentiellen Gewinne, die unser System dem Benutzer ermöglicht. Wir werden ein eigenes Kapitel der Arbeit dem Problem des dynamischen Routing mit Verfügbarkeit von dynamischen Verkehrsinformationen widmen. Insbesondere diskutieren wir zwei mögliche Routing-Algorithmen und vergleichen sie in einer realistischen Simulationsumgebung. Unsere Simulationsumgebung besteht aus dem Netzwerk-Simulator Oversim sowie dem Verkehrssimulator SUMO. Durch die Verwendung eines Verkehrssimulators und realen Karten erhöhen wir die Plausibilität der Evaluation. Unsere Ergebnisse zeigen, dass das System, wenn implementiert, seinen Nutzern in der Tat Vorteil bringen kann: die durchschnittlichen Fahrzeiten werden reduziert.
Lizenz:	Urheberrechtsschutz
Fachbereich / Einrichtung:	Mathematisch- Naturwissenschaftliche Fakultät
Dokument erstellt am:	29.03.2011
Dateien geändert am:	29.03.2011
Promotionsantrag am:	26.01.2011
Datum der Promotion:	16.03.2011