|
Position-Based Packet Forwarding for Vehicular Ad-Hoc Networks
Füßler, Holger
![[img]](https://madoc.bib.uni-mannheim.de/style/images/fileicons/application_pdf.png)  Vorschau |
|
PDF
Fuessler2007VANETRouting_Dissertation_Revised.pdf
- Veröffentlichte Version
Download (6MB)
|
|
URL:
|
https://ub-madoc.bib.uni-mannheim.de/1406
|
|
URN:
|
urn:nbn:de:bsz:180-madoc-14066
|
|
Dokumenttyp:
|
Dissertation
|
|
Erscheinungsjahr:
|
2007
|
|
Titel einer Zeitschrift oder einer Reihe:
|
None
|
|
Verlag:
|
Universität Mannheim
|
|
Gutachter:
|
Effelsberg, Wolfgang
|
|
Datum der mündl. Prüfung:
|
30 April 2007
|
|
Sprache der Veröffentlichung:
|
Englisch
|
|
Einrichtung:
|
Fakultät für Wirtschaftsinformatik und Wirtschaftsmathematik > Praktische Informatik IV (Effelsberg 1989-2017)
|
|
Fachgebiet:
|
004 Informatik
|
|
Normierte Schlagwörter (SWD):
|
VANET , Angewandte Informatik , Ad-hoc-Netz , Routing
|
|
Freie Schlagwörter (Englisch):
|
MANET , VANET , Routing , Computer Science , Computer Networks
|
|
Abstract:
|
Mobile Ad-Hoc Networks, or MANETs, are data communication networks between (potentially) mobile computer systems equipped with wireless communication devices and — in their purest form — in complete absence of communication infrastructure. Usage scenarios for these systems include communication during disaster recovery or battlefield communications. One of the great research challenges concerning MANETs is the Packet Forwarding Problem, i.e., the question to which neighbor node a data packet should be handed over to reach non-neighboring nodes. While this problem has been previously solved by the adaption of classic routing algorithms from wired networks, the availability of GPS enables to include information about the geographic position of nodes into the routing decision, by selecting forwarders that are geographically closest to the destination. While these algorithms have been shown to improve communication performance in networks with a high degree of node mobility, they require (a) a beaconing service that allows every node to build a table of its neighbors and (b) a so-called Location Service that allows to acquire the current position of non-neighboring nodes in the network. In this thesis, we propose Contention-Based Forwarding (or CBF), a greedy routing heuristic that is no longer in need of a beaconing service. Moreover, a forwarding node running CBF does not at all select the next forwarder explicitly but broadcasts the packet containing its own position and the position of the destination. The selection of the forwarding is now done in a contention period, where every possible forwarder, i.e., every receiver of the packet, considers its own suitability to forward by calculating the geographical progress for the packet if forwarded by itself. Then it waits for a time reciprocal to this suitability before simply retransmitting. If the retransmission of a packet is overheard, the own postponed retransmission process is canceled. In this thesis, we demonstrate that CBF outperforms beacon and position-based routing by delivering packets with constant overhead, almost ignorant of mobility. Also, we introduce two strategies to cope with the problem of packet duplication. A problem left open by greedy routing heuristics is routing in the presence of local optima, or voids. Voids are node placement situations, where — in spite of an existing route — no neighboring node is geographically closer to the destination than the current forwarder. In these situations, greedy forwarding fails and standard graph-based recovery well known from classical Position-Based Forwarding cannot be applied due to the lack of the beacon-based construction of neighbor tables. As a solution, we propagate Contention-Based Distance Vector Routing, a contention-based adaption of AODV that acquires topology information in the area of the void and does contention on the topological distance to the forwarder. Besides the forwarding algorithms, we extend position-based routing by two location services. The first, the Reactive Location Service or RLS is simple, purely on-demand and very robust to mobility, the second Hierarchical Location Service, is more complex but outperforms RLS in scalability. The second big column in this thesis is ad-hoc multi-hop communication in the context of Vehicular Ad-Hoc Networks , or VANET, i.e., networks where the communication system is carried by vehicles. These systems very elegantly fit into the propositions and requirements for our more general routing approaches since they have (a) easy access to position information an (b) "suffer" from high mobility. For VANETs, we separate the routing problem into highway and city scenarios and study various routing algorithms in both. In the end, we advocate the usage of position-based routing in both scenarios; moreover, the contention-based approaches are most promising. While a lot of ad-hoc research has been deemed to be theoretical, we have also built a multi-car communication system. For this system, we provided the network and system architecture and provided the communication software. In this thesis, we will describe these efforts as a proof-of-concept and provide measurement results.
|
|
Übersetzter Titel:
|
Positionsbasiertes Paketweiterleiten in Vehikulären Ad-Hoc Netzwerken
(Deutsch)
|
|
Übersetzung des Abstracts:
|
Mobile Ad-Hoc Netzwerke (oder MANETs) sind Netzwerke, bei denen mobile, mit Funktechnik ausgerüstete Netzwerkknoten sich spontan zu einem Netzwerk organisieren. In seiner reinsten Form wird hier keine Infrastruktur in Form von, zum Beispiel, Sendemasten oder access points, verwendet. Die grundsätzlich akademische Ausrichtung der Erforschung dieses Netzwerktyps sieht unter anderem militärische Gefechtsfeldkommunikation oder etwa Kommunikation nach einen Ausfall der Kommunikationsinfrastruktur, zum Beispiel bei einer Naturkatastrophe, vor. Eine der großen Herausforderungen für MANETs ist das Problem der Paketweiterleitung oder des Routings, d.h. die Fragestellung, an welchen Netzwerknachbarn ein Datenpaket weitergeleitet werden soll, um ncht-benachbarte Systeme zu erreichen. Während grundsätzlich Lösungen für dieses Problem schon früher beschrieben wurden - im Wesentlichen durch Adaption von Verfahren aus der Welt der drahtgebundenen Kommunikation - hat die Verfügbarkeit von preiswerten GPS-Empfängern und damit die Fähigkeit, die geographische Position zu ermitteln, einer neuen Klasse von Routing Verfahren den Weg geebnet. Diese Verfahren, positionsbasierte Routingverfahren genannt, können nachweislich die Zustellzuverlässigkeit erhöhen, bzw. die dazu erforderliche Netzwerklast senken, insbesondere in Netzwerken, bei denen die Knoten hoher Mobilität unterliegen. Grundsätzlich funktionieren sie derart, dass jeder Knoten sogenannte beacon -Pakete schickt, die die eigene Position enthalten. Empfänger dieser Pakete erzeugen aus diesen Daten eine Tabelle über ihre eigene Netzwerk-Nachbarschaft. Wird Kommunikation mit einem Nicht-Nachbarknoten angefordert, wird ein sogenannter location service, das ist ein Netzwerkalgorithmus zur Ermittlung der Position von beliebigen, transitiv verbundenen Knoten, bemüht. Mit Hilfe dieser Zielposition und der Position der Nachbarn wird dann die Weiterleitungsentscheidung getroffen. In dieser Dissertation schlagen wir ein neues Verfahren zur Weiterleitung von Datenpaketen in MANETs vor - das Contention-Based Forwarding (CBF), oder etwa Wettbewerbsbasiertes Weiterleiten. Mit dieser Heuristik, die grundsätzlich nach dem greedy Prinzip funktioniert, wird der Einsatz von beacon-Paketen überflüssig. Dies wird dadurch erreicht, dass CBF den nächsten Weiterleiter nicht explizit berechnet, sondern das Paket an alle Nachbarn geschickt wird. Diese verwenden dann die im Paket-Kopf enthaltene Position des letzten Knotens und des Zieles, um die eigene Eignung zum Weiterleiten des Paketes als Funktion des Distanzfortschritts zu berechnen.1 Jeder potentielle Weiterleiter, d.h. jeder mit positivem Distanzfortschritt, wartet nun eine Zeit reziprok zu seiner Eignung. Hat er bis zu diesem Zeitpunkt keine Weiterleitung mitgehört, nimmt er an, der am besten geeignete Knoten zu sein und sendet das Paket. Das Mithören einer Weiterleitung führt hingegen dazu, den eigenen Sendewunsch zu verwerfen. In dieser Arbeit zeigen wir unter anderem, dass die Zustell-Leistung von CBF die des klassischen Routings mit Positionen übersteigt, mindestens jedoch - bei gleicher Leistung - das Zustellen mit beinahe mobilitäts-unabhängigen Kosten erreicht. Außerdem stellen wir zwei wirkungsvolle Strategien vor, mit denen Paket-Duplikate vermieden werden können. Ein Nachteil von greedy Routing-Heuristiken ist die fehlende Vollständigkeit. Dies bedeutet, dass es Knotenkonstellationen, sogenannte voids geben kann, bei denen diese Heuristiken keine Route zum Ziel finden, obwohl es eine solche gibt. Das ist genau dann der Fall, wenn keiner der Nachbarn eines Weiterleiters näher am Ziel liegt als er selbst. Für diesen Fall sieht das klassische Routing mit Positionen sogenannte recovery Strategien oder Rettungsstrategien. Diese beruhen allerdings auf der verteilten Planarisierung des Nachbarschaftsgraphen, der bei unserem wettbewerbsorientierten Verfahren nicht aufgebaut wird, was die direkte Verwendung dieser Verfahren ausschließt. Deswegen stellen wir in dieser Dissertation Contention-Based Distance Vector Routing oder CBDV vor. Hierbei handelt es sich um eine Wettbewerbs-Version des bekannten AODV. Dieses Verfahren gewinnt - um den void herum - Topologie-Informationen, die es dann dazu benutzt, diesen zu überwinden. Neben den Verfahren zur Weiterleitung präsentieren wir zwei der oben als location service (LS) bezeichneten Verfahren zur Ermittlung der geographischen Position von Knoten, die sich irgendwo in der transitiven Hülle befinden. Der erste, der Reactive Location Service oder RLS ist ein sehr einfacher LS, der nur dann Pakete austauscht, wenn er tatsächlich angefordert wird. HLS, oder Reactive Location Service hingegen, tauscht permanent Informationen aus. Dies fördert zum einen die Anfragegeschwindigkeit in großen Netzen und wirkt sich zum anderen positiv auf die Skalierbarkeit aus, offensichtlich auf Kosten von Implementierungskomplexität. Während Routing in Mobile Ad-Hoc Networks den Schwerpunkt der Arbeit darstellt, ist das zweite große Standbein die Anwendung dieser Verfahren bei MANETs, bei denen die Netzwerkknoten in straßengebundenen Fahrzeugen montiert werden. Diese vehikulären Ad-Hoc Netzwerke, oder Vehicular Ad-Hoc Networks (VANETs), sind erst kürzlich in den Blickpunkt der MANET Forschung gerückt. Sie sind für Routing-bezogene Forschung deswegen besonders interessant, weil sie zum einen hoher Mobilität unterliegen und zweitens der Zugriff auf Positionsinformationen in modernen Fahrzeugen durch integrierte Fahrzeugnavigationssysteme kein Problem darstellt. In dieser Arbeit zeigen wir, dass sich eine getrennte Betrachtung des VANET-Routingproblems, zum einen für Autobahnen und zum anderen für Städte, als sinnvoll erweist. Danach zeigen wir für beide Teilbereiche einsetzbare Verfahren und diskutieren Stärken und Schwächen. Am Ende empfehlen wir die Verwendung von positionsbasierten Verfahren. Insbesondere kommen wir zu dem Schluss, dass wettbewerbsbasierte Verfahren in vielen Fällen vorteilhaft sind. Viele Forschung in MANETs ist vorwiegend theoretischer Natur. Während der Anfertigung dieser Arbeit hatten wir das Privileg, im Praktischen ein Kommunikationssystem zur Fahrzeug-zu-Fahrzeug Kommunikation entscheidend mit zu gestalten, zu implementieren und zu erproben. Dieses, und einige gewonnene Evaluationsergebnisse, werden wir in dieser Arbeit ebenfalls darstellen.
(Deutsch)
|
|
Zusätzliche Informationen:
|
|
 | Das Dokument wird vom Publikationsserver der Universitätsbibliothek Mannheim bereitgestellt. |
 Suche Autoren in
Sie haben einen Fehler gefunden? Teilen Sie uns Ihren Korrekturwunsch bitte hier mit: E-Mail
Actions (login required)
 |
Eintrag anzeigen |
|
