Dokument: Safe, Efficient, and Fair---A Top-Down Approach to Inter-Vehicle Communication

Titel:	Safe, Efficient, and Fair---A Top-Down Approach to Inter-Vehicle Communication
URL für Lesezeichen:	https://docserv.uni-duesseldorf.de/servlets/DocumentServlet?id=26333
URN (NBN):	urn:nbn:de:hbz:061-20130806-144611-7
Kollektion:	Dissertationen
Sprache:	Englisch
Dokumententyp:	Wissenschaftliche Abschlussarbeiten » Dissertation
Medientyp:	Text
Autor:	Baselt, Daniel [Autor]
Dateien:	[Dateien anzeigen] Adobe PDF [Details] 1,29 MB in einer Datei [ZIP-Datei erzeugen] Dateien vom 22.07.2013 / geändert 22.07.2013
Stichwörter:	Inter-Vehicle Communication, IVC, C2C, Top-Down
Dewey Dezimal-Klassifikation:	000 Informatik, Informationswissenschaft, allgemeine Werke » 004 Datenverarbeitung; Informatik
Beschreibungen:	Since the development of the first automobiles, individual traffic changed in many respects while the main objectives of transportation---safety and efficiency---have stayed the same. Perhaps the most obvious change is that traffic got denser. To support drivers coping with more and more cars that occupy the roads, car manufacturers developed aids of various kinds that assist driving according to those objectives. The assistants deployed today rely on information made available by a vehicle's on-board sensors and the decisions based on that data are made isolated from other cars. Cooperative decisions of vehicles are enabled by the active exchange of information using inter-vehicle communication. For example, drivers can coordinate with each other about route selections or can warn about hazards like the rear end of a traffic jam in time. The availability of low-cost wireless technology in recent years again inspired the network research community to develop novel protocols and algorithms for inter-vehicle communication. These were then used to build applications supporting the transportation objectives. The developed protocols are based on available or slightly modified standards; their suitability to the applications is limited by the technologies' constraints. Currently, car-to-car networks are designed as general-purpose networks, although the objectives for employing communication for exchanging car information are clear and very specific: optimize traffic safety and efficiency. In addition, the understanding of the application domain was not in focus in the depth that it deserves. With the knowledge available at the time work on this thesis was commenced, it was not possible to measure how well a protocol performs in view of the above objectives. There was in fact no information at all on how to relate available information in vehicles, how such information is exchanged, and the application objectives; the potential that inter-vehicle communication bears was unknown. But without a solid understanding of how these aspects interrelate, a protocol developer cannot be sure that what is pursued is the best---or even just a reasonably good---way of supporting road traffic by means of communication. This thesis proposes to complement the existing research on inter-vehicle communication with a top-down approach. Instead of starting out with a given technology and then developing protocols bottom-up, this approach begins with a formal discussion of what does not change: the objectives of traffic. For these, an optimal behavior of cars and, with this, information demands are deduced that good protocols have to satisfy. Thereafter, according protocols are developed, followed by a suitable communication technology. Because this is an enormous task, a roadmap is presented that describes how to properly divide it. In this thesis, the approach is applied to two basic road topologies up to the point a protocol is obtained. Followed by a comprehensive discussion of related work in the different areas of research that affect the top-down approach, the first steps of the road map are applied to a simplistic scenario. The influence of available information on the vehicles' behavior is considered. Different schemes for information exchange are analyzed including beaconing, a periodic information exchange. It turns out that a car's optimal behavior with beaconing is to drive with alternating periods of acceleration and deceleration which converge to a steady state. The scenario is extended to multiple cars and analyzed for the optimal sending times of information for a cruise control application. This provides us with detailed knowledge about how beaconing should work in a reliable communication environment. The discussion continues with considering the effects of packet losses and it is found that not only the direct follower of a sending car leaves its steady state, but a chain reaction affects numerous upstream cars. To withstand this effect, and in particular to cope with consecutive losses, the steady state distances are enlarged by multiples with beaconing. The then proposed algorithm Carrot is able to detect losses implicitly without a need for acknowledgments and to react via a fast repetition of the missing beacon. Analytical and simulative evaluations show that Carrot is able to repeat beacons in fractions of a beaconing interval, so that the steady state distances can be chosen very close to the minimum. Communication enables cars to cooperate and thereby allows for a third objective besides safety and efficiency that is not yet in focus of research for inter-vehicle communication: fairness. Towards this, this thesis contributes the definition of a fairness criterion for cooperation. This criterion is applied to the ordering of cars at a merging of two lanes. An analysis of the zipper merge, the only relevant merging scheme for today's cars if no lane is given the right of way, clearly shows an inherent unfairness. A coordination scheme is proposed that creates an optimal fair merge order. The scheme is adapted for distributed decisions with local knowledge and communication using a beacon-based approach. Evaluations which also accounts for unreliable wireless communication describe the influence of the ratio of participants on merging order fairness. The results show that the algorithm yields very good fairness even if only a small percentage of about 1 % of the cars follows the algorithm's guidance. Seit der Entwicklung der ersten Automobile hat sich der Individualverkehr in vielerlei Hinsicht gewandelt, allerdings sind die zentralen Ziele des Verkehrs -- Sicherheit und Effizienz -- gleich geblieben. Eine der sichtbarsten Veränderungen ist die Zunahme des Verkehrsaufkommens. Um auch bei den heute üblichen hohen Verkehrsdichten sicher und effizient fahren zu können, werden Fahrer moderner Fahrzeuge durch verschiedenste Assistenzsysteme unterstützt, welche auf Basis von Informationen arbeiten, die durch die im Fahrzeug vorhandenen Sensoren wie GPS, Radar und Lidar erzeugt werden. Die mit diesen Daten möglichen Entscheidungen werden isoliert von anderen Verkehrsteilnehmern getroffen. Erst durch den aktiven Austausch von Informationen zwischen Fahrzeugen können Entscheidungen auch gemeinschaftlich gefunden werden. So kann auf diese Weise die Wahl von Fahrtrouten koordiniert werden oder rechtzeitig vor Gefahren gewarnt werden, wie sie beispielsweise durch ein Stauende an einem uneinsehbaren Streckenteil entstehen. In den letzten Jahren hat die Forschung in diesem Bereich durch die Verfügbarkeit von kostengünstiger drahtloser Kommunikationstechnologie erneut Aufwind erhalten, es wurden neuartige Protokolle und Algorithmen für diese Technologien entwickelt, welche dann für die Konzeption von den Fahrer assistierenden Anwendungen verwendet wurden. Da jedoch die zugrundeliegenden Technologien bestehende oder lediglich leicht modifizierte Standards nutzen, ist die Anpassbarkeit der Protokolle begrenzt. Bisherige Entwürfe für Kommunikationssysteme der Fahrzeug-zu-Fahrzeug-Kommunikation setzen auf Protokolle, die für universelle Anwendbarkeit ausgelegt sind. Allerdings lassen sich die wesentlichen Anwendungen klar und präzise bestimmen: es geht um Verkehrssicherheit und die effiziente Nutzung verfügbarer Ressourcen. Hinzu kommt, dass ein definierbares Verständnis der Anwendungen bisher nicht im Fokus der Forschung in diesem Bereich war. Mit dem zum Beginn der Arbeit an dieser Dissertation verfügbaren Wissen und Werkzeugen war es nicht möglich zu bestimmen, wie gut sich ein Protokoll hinsichtlich von Anwendungszielen in einem absolutem Maßstab verhält. Es fehlten Informationen darüber, wie verfügbare Informationen, Methoden des Informationsaustausches und Anwendungsziele miteinander in Beziehung stehen. Dadurch war auch das tatsächliche Potenzial der Fahrzeug-zu-Fahrzeug-Kommunikation nicht bekannt, denn ohne eine verlässliche Kenntnis dieser Beziehungen können Entwickler nicht sicher sein, dass ihre Kommunikationsprotokolle dabei helfen, die Ziele im Straßenverkehr bestmöglich zu erreichen. Die vorliegende Arbeit beschreibt, wie die bestehenden Forschungsergebnisse in der Fahrzeug-zu-Fahrzeug-Kommunikation durch einen Top-Down-Ansatz ergänzt werden kann. Anstelle bestehende Standards vorauszusetzen und darauf Protokolle bottom-up aufzubauen, werden mit diesem Ansatz zunächst die bestimmenden Ziele im Straßenverkehr formal definiert, da diese sich im Vergleich zu Technologien längeren Bestand gezeigt haben. Für diese Ziele wird dann das optimale Verhalten von Fahrzeugen bestimmt und mit diesem Eigenschaften für gute Protokolle abgeleitet. Damit ist die Möglichkeit gegeben, entsprechende Protokolle und letztlich passende Kommunikationstechnologien zu entwerfen. Dies ist eine immense Aufgabe, weshalb in dieser Arbeit zunächst deren Aufteilung zu einem mehrschrittigen Vorgehen beschrieben wird. Danach wird der Top-Down-Ansatz auf zwei grundlegende Situationen im Straßenverkehr zur Entwicklung angepasster Protokolle angewendet. Nach einer umfassenden Diskussion verwandter Arbeiten aus den verschiedenen Forschungsbereichen, die von einem Top-Down-Ansatz berührt werden, werden die ersten Schritte des Ansatzes mit einem einfachen Szenario diskutiert und der Einfluss verfügbarer Informationen auf das Verhalten von Fahrzeugen betrachtet. Unterschiedliche Methoden des Informationsaustausches werden analysiert, unter anderem ein idealisiertes Beaconing, ein Verfahren für den periodischen Austausch von Informationen. Es wird festgestellt, dass das optimale Verhalten eines Fahrzeugs ein abwechselndes Bremsen und Beschleunigen ist, welches zu einem stabilen Zustand strebt. Darauffolgend wird das Szenario erweitert, um die optimalen Sendezeiten von mehreren Fahrzeugen für ein Geschwindigkeitsregelungssystem in einer Kolonne zu untersuchen. Diese Diskussion vertieft das Wissen darüber, wie Beaconing mit zuverlässiger Kommunikation funktionieren sollte. Darauf baut die anschließende Betrachtung von unzuverlässiger Kommunikation auf, bei der gezeigt wird, dass ein Paketverlust nicht nur einen direkten Hintermann in der Kolonne beeinflusst, sondern eine Kettenreaktion die stabilen Zustände zahlreicher folgender Fahrzeuge stört. Um diesem Effekt entgegenzuwirken, der besonders schwer bei mehreren Verlusten in Folge wiegt, wird bei Beaconing der stabile Zustand um ein Mehrfaches vergrössert. Mit dem dann vorgestellten Protokoll Carrot ist es möglich, Verluste implizit, also ohne zusätzliche Pakete, zu erkennen und auf diese mit einer schnellen Übertragungswiederholung zu reagieren. Analytische und simulative Auswertungen zeigen, dass Carrot Beacons in Bruchteilen eines Sendeintervalls wiederholt und damit ein stabiler Zustand nahe dem Minimum von verlustfreier Kommunikation gewährleistet werden kann. Die Fahrzeug-zu-Fahrzeug-Kommunikation ermöglicht die Unterstützung eines weiteren Zieles im Straßenverkehr neben Sicherheit und Effizienz, welches bislang nicht im Fokus der Forschung lag: Ein weiterer Beitrag dieser Arbeit ist die Definition des Kriteriums Fairness für die Kooperation von Fahrzeugen. Dieses Kriterium wird auf die Reihenfolge von Fahrzeugen bei der Überfahrt eines Spurzusammenschlusses angewendet. Eine Untersuchung des Reißverschlussverfahrens, dem einzig Relevanten wenn keiner Spur die Vorfahrt gegeben ist, mit diesem Kriterium zeigt dabei klar eine grundlegende Unfairness. Ein Verfahren zur fairen Koordination wird vorgestellt, welches optimale Fairness erreicht. Dieses wird dann abgewandelt, um eine verteilte Entscheidungsfindung mit lokalem Wissen und Beacon-basierter Kommunikation zu ermöglichen. Auswertungen wurden mit unzuverlässiger Kommunikation durchgeführt, um den Einfluss der Ausstattungsrate der Fahrzeuge auf die Fairness der Reihenfolge von Überfahrten zu bewerten. Die Ergebnisse zeigen, dass das entwickelte Protokoll die Fairness deutlich erhöht, selbst wenn nur ein kleiner Anteil der Fahrzeuge von 1 % den Empfehlungen folgt.
Lizenz:	Urheberrechtsschutz
Fachbereich / Einrichtung:	Mathematisch- Naturwissenschaftliche Fakultät » WE Informatik » Rechnernetze
Dokument erstellt am:	06.08.2013
Dateien geändert am:	06.08.2013
Promotionsantrag am:	17.06.2013
Datum der Promotion:	19.07.2013