Lade Inhalt...

Skalierbarkeit von Routingprotokollen in mobilen Ad-Hoc-Netzen

Bachelorarbeit 2008 47 Seiten

Informatik - Internet, neue Technologien

Leseprobe

Inhaltsverzeichnis

1 Problem- und Aufgabenstellung

2 Einleitung

3 Grundlagen
3.1 Eigenschaften und Anwendungsgebiete von mobilen Ad-Hoc-Netzwerken
3.2 Anforderungen an MANET-Routingprotokolle
3.3 Klassifizierung von MANET-Routingprotokollen

4 Ausgewählte Routingprotokolle für Mobile Ad-hoc-Netzwerke
4.1 Optimized Link State Routing (OLSR)
4.2 Ad Hoc On-Demand Distance-Vector (AODV)
4.3 Zone Routing Protocol (ZRP)
4.4 Fisheye State Routing (FSR)
4.5 Cluster Based Routing Protocol (CBRP)
4.6 Greedy Perimeter Stateless Routing (GPSR)

5 Methodik
5.1 Der Simulator NS-2
5.2 Die Simulationsumgebung
5.3 Verwendete Metriken
5.4 Implementierung der Simulation

6 Ergebnisse der Simulation
6.1 Packet Delivery Ratio
6.2 Average End-to-End Delay
6.3 Path Optimality
6.4 Throughput

7 Fazit

Abbildungs- und Tabellenverzeichnis

Abkürzungsverzeichnis

Literaturverzeichnis

1 Problem- und Aufgabenstellung

Ein mobiles Ad-Hoc-Netzwerk (MANET) ist eine Menge von mobilen Knoten, die über Funk miteinander kommunizieren und ein temporäres Netzwerk ohne bestehende Infra- struktur und ohne zentrale Administration bilden. Da die Übertragungsreichweite der einzelnen Knoten begrenzt ist, müssen zwei Knoten, die miteinander Daten austauschen wollen, dies meist mit Hilfe von zwischen ihnen liegenden Knoten bewerkstelligen. Die Kommunikation in einem MANET wird darüber hinaus durch die hohe Dynamik seiner Mitglieder erschwert. Diese Netze müssen daher flexibel auf Topologieänderungen reagie- ren können.

Aufgrund ihrer hohen Dynamik stellt das Routen von Paketen die größte Herausforderung in MANETs dar. Im Laufe der letzten Jahre wurde eine Vielzahl von Routingprotokol- len vorgestellt, die das Routingproblem in MANETS auf unterschiedliche Weise zu lösen versuchen. Im Rahmen dieser Arbeit wird untersucht, wie sich verschiedene MANET- Routingprotokolle im Hinblick auf ihre Leistung in Netzwerkszenarien von unterschiedli- cher Dimension, Teilnehmerzahl, Knotenmobilität sowie Netzwerklast bewähren.

2 Einleitung

Drahtlose Netze sind seit den Anfängen ihrer Entwicklung in den 1970er Jahren ein in- tensiv beforschtes Gebiet und haben eine kontinuierliche Entwicklung erfahren. Besonders seit dem letzten Jahrzehnt des 20. Jahrhunderts hat das Interesse an ihnen, bedingt durch die zunehmende Popularität von mobilen Geräten wie etwa Laptops, stark zugenommen.

Mobile drahtlose Netze lassen sich zurzeit in zwei Kategorien einteilen. Die erste Vari- ante wird als Infrastruktur-Netzwerk bezeichnet, da bei Netzen dieser Art eine zentrale Infrastruktur zur Verwaltung der einzelnen Netzknoten existiert. Die zweite Variante sind infrastrukturlose Netze, besser bekannt unter der Bezeichnung mobiles Ad-Hoc-Netzwerk (MANET).

Ein mobiles Ad-Hoc-Netzwerk bezeichnet also ein drahtloses Netz, das ohne Infrastruktur auskommt und jederzeit überall gebildet werden kann. Da die Sendeleistung der einzelnen Knoten beschränkt ist, erfolgt die Kommunikation in einem solchen Netz meist über temporäre Multihop-Relays, wobei einige Knoten in Selbstorganisation als Router agieren.

Aufgrund der erwähnten Eigenschaften von MANETs sind diese Netze neben ihrem ur- sprünglichen Einsatzgebiet – militärischen Operationen – beispielsweise für den Aufbau Smart Dust“) oder mobilen Fahrzeugnetzen (sog. VANETs) gut ge- ” eignet.

Das erwähnte Multihop-Routing, die willkürlichen Knotenbewegungen sowie andere MANET-Eigenschaften, wie z. B. begrenzte Energieressourcen oder die eingeschränkte Signalreichweite der mobilen Knoten, stellen jedoch auch eine große Herausforderung an das Routing in solchen Netzen dar. Daher stellt sich die Frage, wie die Routenfindung und -pflege unter solch schwierigen Umständen möglichst effizient gelöst werden kann.

Um das Multihop-Routingproblem in MANETs lösen zu können, ist eine Vielzahl unter- schiedlicher Protokolle entwickelt worden. Einige davon verfolgen einen sog. flachen An- satz, in dem es keine ausgezeichneten Knoten gibt, andere versuchen durch Einführung von Hierarchien die Effizienz, besonders in großen Netzen, zu steigern. Eine weitere Grup- pe von Protokollen macht sich etwa die Vorteile der satellitengestützten Navigation (z. B. GPS) zunutze, um die Probleme der zuvor angeführten topologiebasierten Verfahren zu umgehen. Diese Protokolle werden unter dem Begriff geographische Routingprotokolle subsumiert.

In dieser Arbeit werden ausgewählte Routingprotokolle aus den oben genannten Klas- sen beschrieben. Es sind dies als Vertreter der flachen Routingansätze OLSR, AODV, ZRP sowie das implizit hierarchische FSR. Als ein Protokoll, das einen hierarchischen Ansatz umsetzt, wird die Funktionsweise von CBRP näher erläutert. Das schlussendlich beschriebene GPSR gehört zur Familie der geographischen, positionsbasierten Protokolle.

Diese Routingprotokolle werden im Rahmen der vorliegenden Arbeit mittels NS-2- Simulator in Bezug auf ihre Leistungsfähigkeit getestet. Besonderes Augenmerk wird da- bei auf die Skalierbarkeit der Protokolle im Hinblick auf variierende Parameter gelegt. So werden die Protokolle in drei unterschiedlich groß dimensionierten Gebieten, mit unter- schiedlicher Knotenanzahl und -mobilität sowie unterschiedlichen Verkehrslasten getestet.

Die weitere Arbeit ist wie folgt aufgebaut:

In Kapitel 3 werden zunächst Eigenschaften und typische Anwendungsgebiete von MA- NETs beschrieben. Danach wird genauer auf die Routingproblematik in MANETs ein- gegangen und die speziellen Anforderungen an Routingprotokolle für mobile Ad-Hoc- Netzwerke dargelegt. Das Kapitel schließt mit einer umfassenden Klassifikation von MANET-Routingprotokollen.

In Kapitel 4 werden jene Routingprotokolle vorgestellt und näher beschrieben, die im Rah- men dieser Arbeit einem Leisungsvergleich unterzogen werden: Als Vertreter der flachen Routingprotokolle werden das proaktive OLSR-Protokoll, das reaktive AODV-Protokoll, das hybride ZRP-Framework sowie das implizit hierarchische FSR-Verfahren, als Vertreter des hierarchischen Ansatzes wird CBRP und als ein positionsbasiertes Routingprotokoll GPSR vorgestellt.

In Kapitel 5 wird die Methodik, die dem praktischen Teil der Arbeit zugrunde liegt, erläutert. Zunächst wird ein grober Überblick über die Funktionalität des Netzwerk- Simulators NS-2 gegeben. Danach wird detailliert auf das Szenario der durchgeführten Simulation eingegangen und die verwendeten Metriken werden erläutert. Das Kapitel schließt mit einer kurzen Beschreibung der konkreten Simulationsimplementierung.

In Kapitel 6 werden die Ergebnisse der Simulation präsentiert.

Kapitel 7 schließt die Arbeit mit einer Zusammenfassung der vorgestellten Erkenntnisse ab.

3 Grundlagen

In diesem Kapitel werden die Grundlagen für die nachstehenden Kapitel kurz dargelegt. Zunächst werden Eigenschaften und Anwendungsgebiete von MANETs erläutert. Es folgt eine Beschreibung der speziellen Anforderungen, die ein MANET an Routingprotokolle stellt. Den Abschluss dieses Kapitels bildet eine umfassende Klassifizierung der für mobile Ad-Hoc-Netzwerke üblichen Routingprotokolle.

3.1 Eigenschaften und Anwendungsgebiete von mobilen Ad-Hoc- Netzwerken

Ein mobiles Ad-Hoc-Netzwerk (MANET) besteht aus mobilen Geräten (Knoten), die sich beliebig bewegen können. Jeder dieser Knoten besteht logisch gesehen aus einem Router, der mehrere Hosts und auch mehrere drahtlose Kommunikationsgeräte besitzen kann. Ein MANET ist ein autonomes System (AS) von mobilen Knoten. Ein solches Netzwerk besitzt keine feste Infrastruktur und muss sich selbst organisieren. Ein MANET kann isoliert operieren oder über Gateway-Router mit anderen Routern verbunden sein (Corson & Macker 1999, S. 3).

MANETs haben nach Corson & Macker (1999, S. 3f) folgende besondere Eigenschaften:

Dynamische Topologie: Da sich Knoten frei bewegen können, kann sich die Netz- werktopologie zufällig und schnell zu unvorhersehbaren Zeiten ändern. Verbindun- gen zwischen Knoten können uni- oder bidirektional sein. Das Routing hat typi- scherweise Multihop-Charakter.

Bandbreitenbeschränkung, variable Verbindungskapazitäten: Drahtlose Verbin- dungen haben eine wesentlich niedrigere Kapazität als drahtgebundene Verbindun- gen, außerdem ist der tatsächliche Durchsatz von drahtlosen Verbindungen zumeist niedriger als der maximal mögliche Wert einer Radiowellen- Übertragung. Dies wird durch verschiedene Faktoren wie mehrfacher Zugriff auf das Medium, Hintergrund- rauschen, Multihopping, die exponentielle Abschwächung des Signals sowie Interfe- renzen nahe gelegener drahtloser Verbindungen hervorgerufen.

Energieabhängiger Betrieb: In einem MANET haben viele oder auch alle Knoten nur eine beschränkte Energiemenge zur Verfügung, insofern ist die Optimierung des Energieverbrauchs dieser Knoten das wichtigste Designkriterium.

Eingeschränkte physische Sicherheit: Drahtlose Netzwerke sind generell anfälliger gegenüber physikalischen Sicherheitsbedrohungen als drahtgebundene Netze. So be- steht eine erhöhte Wahrscheinlichkeit, dass Pakete verworfen oder gefälscht wer- Denial of Service“-Attacken sind einfach durchzuführen. Oft werden Punkt-zu- ” -Sicherheitsverfahren verwendet, um die Sicherheitsbedrohung zu Punkt reduzieren. Als Vorteil eines MANETs kann jedoch der dezentralisierte Charak- ter gewertet werden. Das Netzwerk wird dadurch robuster gegen einzelne Knoten- ausfälle als bei zentralisierten Ansätzen.

Die wichtigsten Anwendungsgebiete von MANETs sind Bereiche, in denen keine entspre- chende Infrastruktur vorhanden ist und Netzwerke unterschiedlicher Größe schnell und dynamisch konfiguriert werden müssen. MANETs können nach Perkins (2001, S. 8–14) u. a. bei Einsätzen in Katastrophengebieten, im Bereich des Ubiquitous Computing“, bei sog. Personal Area Networks (PAN), Sensornetzwerken o ” in der Fahrzeugkommunika- tion (Vehicular Ad-hoc-Network, VANET) Anwendung finden.

3.2 Anforderungen an MANET-Routingprotokolle

Um die Leistung eines MANET-Routingprotokolls bewerten zu können, werden eine Reihe von qualitativen und quantitativen Metriken herangezogen. Diese Metriken müssen un- abhängig von dem verwendeten Routingprotokoll sein. Corson & Macker (1999, S. 6) nen- nen folgende wünschenswerte qualitative Eigenschaften eines MANET-Routingprotokolls:

Verteilte Verfahren: Aufgrund der hohen Dynamik in MANETs sind Verfahren mit zentraler Steuerung für diese Netze ungeeignet.

Schleifenfreiheit: Dies ist prinzipiell eine wünschenswerte Eigenschaft, um Probleme, wie z. B. Pakete, die eine willkürliche Zeit im Netz herumwandern“, zu vermeiden.

Sicherheit: Die Sicherheit spielt in mobilen Ad-hoc-Netzwerken, allein schon aufgrund der Kommunikation per Funk eine wichtige Rolle. Die Funkkommunikation kann wesentlich einfacher abgehört, manipuliert oder umgeleitet werden als die Kommu- nikation in Festnetzen. Daher sind ausreichende Sicherungsmaßnahmen erforderlich, um Störung oder Modifikation des Protokollbetriebs zu verhindern.

Schlafperioden: Da Knoten in MANETs oft beschränkte Energieressourcen haben, können Knoten, um Energie zu sparen, den Versand oder Empfang von Paketen für eine Dauer einstellen. Ein MANET-Routingprotokoll muss solche Schlafperioden berücksichtigen können, ohne dass daraus allzu große Nachteile entstehen.

Unidirektionale Verbindungen: Mobile Knoten in MANETs verfügen über unter- schiedliche Sende- und Empfangseinheiten. Daher sind asymmetrische Verbindun- gen möglich, d. h., der Transport von Paketen muss auf unterschiedlichen Hin- und Rückwegen abgewickelt werden können.

Außerdem gibt es eine Reihe quantitativer Metriken eines Routingprotokolls, wie Ende- zu-Ende-Datendurchsatz und -verzögerung, Routenfindungszeit oder Effizienz (Corson & Macker 1999, S. 8).

3.3 Klassifizierung von MANET-Routingprotokollen

Es können verschiedene Kriterien zur Klassifizierung von Routingprotokollen in mobilen Ad-Hoc-Netzwerken herangezogen werden, wie z. B. welche Routinginformationen ausge- tauscht werden, wann und wie diese Routinginformationen ausgetauscht oder wann und wie diese Routen berechnet werden.

Distanzvektor-Routing (DVR) – Link-State-Routing (LSR)

Beim DVR werden jene Daten der Netzwerktopologie aus den Routingtabellen entnom- men, die ein Knoten in regelmäßigen Abständen von seinen unmittelbaren Nachbarn als Kopien erhält. Das Verfahren beruht auf dem Bellman-Ford-Algorithmus, wobei die Kno- ten den besten Pfad ermitteln, indem sie die Metriken (z. B. Distanz oder Verzögerung) addieren, die sie als Routinginformation von ihren Nachbarn erhalten. Da die Topologie- informationen von Knoten zu Knoten weitergegeben werden, sind die Konvergenzzeiten relativ lang (vgl. Tanenbaum 2003, S. 357–358).

Beim LSR hingegen ist allen Knoten die vollständige Netzwerktopologie bekannt, da sie in regelmäßigen Abständen Informationen über ihre Verbindungszustände im Netzwerk flu- ten. Dadurch können sie getrennt voneinander den jeweils kürzesten Pfad zum Ziel mittels SPF-Algorithmus (SPF) von Dijkstra berechnen. Beim LSR werden Aktualisierungen di- rekt durch A¨ nderungen in der Netzwerktopologie ausgelöst. Die weitergegebenen Topolo- gieinformationsnachrichten (Link State Packets, LSPs) sind relativ klein, dadurch sind die Konvergenzzeiten bei Topologieänderungen vergleichsweise kurz (vgl. Tanenbaum 2003, S. 361–365).

Proaktives Routing – Reaktives Routing

Beim proaktiven Routing-Verfahren (auch tabellenbasiertes Routing genannt) werden die Routen zu allen Zielen im Vorhinein berechnet. Dazu benötigt jeder Knoten teilweise oder komplette Information über die Verbindungszustände und Netzwerktopologie. Um diese Informationen auf dem Laufenden zu halten, müssen Knoten sie in regelmäßigen Abständen, bei A¨ nderung von Verbindungszuständen oder der Netzwerktopologie aktua- lisieren. Der Vorteil dieses Verfahrens ist, dass Routen von der Quelle zum Ziel jederzeit verfügbar sind, nachteilig ist der relativ hohe Verbrauch von Netzwerk-Bandbreite auf- grund der Übertragung von Kontrollnachrichten (Royer & Toh 1999, S. 46).

Beim reaktiven Routing (auch nachfragebasiertes Routing genannt) werden Routen nur dann berechnet, wenn sie nicht bekannt sind, aber benötigt werden. Aufgrund dieser Routenbestimmung ergibt sich eine Latenzzeit am Beginn der Übertragung eines Nutz- datenpaketes. Der Vorteil des reaktiven Ansatzes besteht darin, dass Kontrollnachrichten nur relativ wenig Bandbreite benötigen (Royer & Toh 1999, S. 48).

Topologiebasiertes Routing – Geographisches Routing

Bei Hong, Xu & Gerla (2002, S. 12) werden MANET-Routingprotokolle aufgrund der den Protokollen zugrunde liegenden Netzwerkstruktur beschrieben. Es werden drei Kate- gorien von MANET-Routingprotokollen unterschieden: Flaches Routing, das wiederum in proaktive, reaktive bzw. hybride Verfahren unterteilt werden kann, hierarchisches Routing sowie geographisches Routing. Die flachen und hierarchischen Routingprotokolle werden unter dem Begriff topologiebasiertes Routing subsumiert, da ihnen logische Informatio- nen über die Nachbarschaftsbeziehungen der Knoten (Singlehop oder Multihop) genügen (Das, Pucha & Hu 2005, S. 1). Abbildung 1 stellt diese Zusammenhänge graphisch dar.

Abbildung in dieser Leseprobe nicht enthalten

Abb. 1: Klassifikation von Ad-Hoc-Routingprotokollen.

Flaches Routing: Bei den flachen Routingverfahren haben alle Knoten dieselbe Rou- tingfunktionalität und befinden sich in ein und derselben Hierarchie. In dieser Arbeit betrachtete Beispiele für Protokolle dieser Kategorie sind das Optimized Link State Routing“-Protokoll (OLSR), das Ad Hoc On-Demand ” e-Vector“-Protokoll ”. (AODV), das Zone Routing Protocol“ (ZRP) sowie das Protokoll ” Fisheye State Routing“- ”(FSR)

Hierarchisches Routing: Im Gegensatz zu den flachen Routingverfahren wird bei den hierarchischen Routingverfahren das Netz dynamisch in verschiedene Regionen un- einer terteilt, die ihrerseits wieder beliebig oft“ in größere Regionen zusammengefasst werden können. Innerhalb ” Region übernehmen bestimmte Knoten unterschied- liche Rollen. Da die Dynamik der Netzwerktopologie und die Verwaltung der Mit- gliedschaften auf die jeweilige Region begrenzt sind, werden zwischen den Regionen nur wenige benötigte Informationen ausgetauscht, was eine Reduktion des Kontroll- verkehrs zur Folge hat. Als Vertreter dieses Routingansatzes wird im Rahmen der vorliegenden Arbeit das Cluster Based Routing Protocol“ (CBRP) näher betrach- tet.”

Geographisches Routing: Geographische Routingprotokolle nutzen das Vorhanden- sein von Ortsinformationen über die Knoten im Netzwerk, wie sie z. B. von Po- sitionierungssystemen wie dem Global Positioning System (GPS) zur Verfügung ge- stellt werden, aus. Um Pakete zum Ziel routen zu können, muß der Quellknoten die tingverfahren sog. Position des Zielknotens ermitteln können. Daher spielen bei geographischen Rou- Location Services“, mit denen der Aufenthaltsort eines mobilen ” Knotens zurückverfolgt werden kann und Anfragen über dessen Position beantwor- Hier- Greedy tet werden können, eine zentrale Rolle. Das in Kapitel 4.6 beschriebene ” Perimeter Stateless Routing“-Protokoll (GPSR) kann beispielsweise mit dem ” archical Location Service“ (HLS) betrieben werden.

4 Ausgewählte Routingprotokolle für Mobile Ad-hoc- Netzwerke

In diesem Kapitel werden sämtliche Routingprotokolle, die im Rahmen dieser Arbeit einem Leistungsvergleich unterzogen werden, näher beschrieben. Zunächst werden Protokolle, die der Kategorie der flachen Routingprotokolle zuzurechnen sind, erläutert – OLSR, AODV, ZRP sowie das implizit hierarchische FSR. Als reiner Vertreter der hierarchischen MANET-Routingprotokolle wird anschließend die Funktionsweise von CBRP dargelegt. Den Abschluss des Kapitels bildet die Vorstellung des geographischen Routingprotokolls GPSR.

4.1 Optimized Link State Routing (OLSR)

OLSR ist ein proaktives LSR-Protokoll, das für MANETs optimiert worden ist. OLSR ist als experimentelles RFC (Clausen & Jacquet 2003) von der IETF spezifiziert worden. Im Gegensatz zum klassischen LSR, bei dem Verbindungsinformationen im gesamten Netz- werk geflutet werden (vgl. Kapitel 3.3), versucht OLSR Bandbreite zu sparen, indem das Fluten nur über ausgewählte Knoten durchgeführt wird. Diese Technik nennt sich Multi Point Relay (MPR) Flooding“. ”

Das OLSR-Protokoll enthält drei wesentliche konzeptuelle Elemente: einen Mechanismus zur Nachbarschaftserkundung ( Neighbor Detection“), einen Mechanismus, um Kontroll- nachrichten effizient an ” Netzwerk zu verteilen ( MPR Flooding“), und einen Knoten im ” Mechanismus, um ausreichend Topologieinformationen zur Bereitstellung optimaler Pfade zu gewinnen und diese im Netzwerk zu verteilen ( Topology Discovery“).

Neighbor Detection

Dieses Verfahren (Clausen & Jacquet 2003, S. 33–38) wird von Knoten angewendet, um A¨ nderungen in der Nachbarschaft zu erkennen, um zu überprüfen, ob Verbindungen zu benachbarten Knoten bidirektional sind, und um Topologieinformationen über die sog. 2-Hop-Nachbarschaft zu gewinnen. Dies wird durch periodisches Versenden von HELLO- Nachrichten ermöglicht, die eine Liste der Verbindungen zu den Knotennachbarn sowie den jeweiligen Status enthalten (der Status der Verbindung wird mittels Link Sensing“ ermittelt und kann symmetrisch oder asymmetrisch sein). ”

MPR Flooding

Das MPR-Fluten basiert auf folgendem Prinzip (vgl. Clausen & Jacquet 2003, S. 38– 42): Jeder Knoten A muss eine Menge (das sog. MPR Set“) aus seinen symmetrischen Nachbarn auswählen, sodass Nachrichten, die ¨ ” das MPR-Set weitergeleitet werden, von allen symmetrischen 2-Hop-Nachbarn erhalten werden. Im Gegenzug verwalten alle Knoten eine Liste der Menge von Nachbarn, die Knoten A als MPR gewählt haben ( MPR Selector Set“). Ein Knoten, der als MPR ausgewählt wurde, hat die Aufgabe, Nachr” hten, die von seinen MPR-Selectors geflutet wurden, weiterzuleiten. Abbildung 2 zeigt, wie das Fluten über MPRs das mehrfache Übertragen von Nachrichten im Vergleich zum klassischen Fluten signifikant reduziert.

Abbildung in dieser Leseprobe nicht enthalten

Abb. 2: Der Quellknoten ist der Knoten in der Mitte. Jeder Pfeil, der zu einem Knoten weist, zeigt, dass dieser Knoten eine Kopie der zu sendenden Nachricht erhält. Die schwarzen Knoten in (b) sind jene Knoten, die vom Quellknoten als MPRs ausgewählt worden sind.

Topology Discovery

Jeder Knoten konstruiert einen partiellen Topologie-Graphen, der alle erreichbaren Kno- ten im Netzwerk sowie deren Verbindungsinformationen enthält. Um diesen Graphen er- stellen zu können, generieren Knoten, deren MPR-Selector-Set nicht leer ist, periodisch Topology Control (TC)“-Nachrichten, in denen die Adresse des generierenden Knotens und die aller Knoten seines MPR-Selector-Sets enthalten sind. Diese T C-Nachrichten beinhalten somit die benötigten Verbindungsinformationen, um den Topologie-Graphen und damit kürzeste Routen erstellen zu können, und werden im Netzwerk mittels MPR- Fluten verteilt (Clausen & Jacquet 2003, S. 33–36). Die Routingtabellen werden durch Informationen aus den HELLO- und TC-Nachrichten von jedem Knoten gewonnen. Da- her muss, sobald sich eine A¨ nderung der lokalen Verbindungsinformationen oder der Topologieinformationen ergibt, die Routingtabelle neu berechnet werden (Clausen & Jacquet 2003, S. 37).

4.2 Ad Hoc On-Demand Distance-Vector (AODV)

AODV ist ein für MANETs optimiertes reaktives Protokoll, das auf dem DVR-Verfahren beruht. AODV ist als experimentelles RFC 3561 (Perkins, Belding-Royer & Das 2003) von der IETF spezifiziert worden.

In AODV werden Routen nur erforscht, wenn sie benötigt werden, und werden nur so lange verwaltet, wie sie gebraucht werden. AODV verwendet Sequenznummern, um die Aktualität von Routen zu überprüfen und um Schleifenfreiheit zu garantieren.

AODV definiert drei Nachrichtentypen, um Pfade berechnen und pflegen zu können (Perkins et al. 2003, S. 7–10):

RREQ: Falls eine Route zu einem Ziel nicht verfügbar ist, wird eine sog. ” ute Request Ro (RREQ)“-Nachricht im Netzwerk geflutet.

RREP: Ist ein Knoten entweder der Zielknoten oder kennt er eine gültige Route zum Ziel, sendet er per Unicast eine sog. Route Reply (RREP)“-Nachricht zurück zum Quell- knoten. ”

RERR: Wenn eine aktive Verbindung zusammenbricht, senden die Knoten an beiden Enden dieser Verbindung eine sog. Route Error (RERR)“-Nachricht aus, um ihre jeweiligen Endknoten darüber zu ” eren.

AODV beinhaltet zwei wichtige Phasen: Route Discovery“ und ” Route Maintenance“. ”

Route Discovery

Neue Routen werden mittels RREQ-/RREP-Zyklus gefunden. Wenn ein Quellknoten A eine neue Route benötigt, sendet er RREQ per Broadcast an alle Knoten im Netzwerk. Knoten, die dieses Paket erhalten, aktualisieren ihre Information über den Quellknoten und de- finieren u. a. einen Reverse Route“-Eintrag zum Quellknoten in ihren Routingtabellen.

Ein Knoten, der RR” erhält und der Zielknoten H ist oder eine Route zu H kennt, deren Sequenznummer größer oder gleich der in RREQ enthaltenen Sequenznummer ist, sendet RREP per Unicast an Knoten A. Anderenfalls leitet er den RREQ per Broadcast weiter.

Während RREP zur Quelle zurückgesendet wird, fügen die auf diesem Weg liegenden Kno- ten einen Forward Path“-Eintrag in ihre Routingtabellen ein. Sobald der Knoten A RREP erhalten ” , kann er Daten auf dem Forward-Path an den Knoten H senden. Abbil- dung 3 verdeutlicht den Zusammenhang zwischen Reverse- und Forward-Path graphisch (vgl. Perkins et al. 2003, S. 14–21).

Route Maintenance

Nachdem eine bestimmte Ziel-Route gefunden wurde, wird diese so lange verwaltet, wie der Quellknoten sie benötigt ( aktiver Pfad“). Wenn sich der Quellknoten einer aktiven

Abbildung in dieser Leseprobe nicht enthalten

Abb. 3: AODV Routenfindung zwischen Knoten A und Knoten H.

Route bewegt, kann er eine neue Routenfindung starten. Wenn sich ein auf dem aktiven Pfad liegender Knoten oder der Zielknoten bewegt, sodass der Vorgängerknoten ihn trotz eventueller Reparaturversuche ( Local Repair“, vgl. Perkins et al. 2003, S. 26–27) nicht mehr erreichen kann, wird die ”erbindung als gestört betrachtet. Der Knoten, der den Fehler entdeckt hat, sendet RERR so lange an seine Vorgängernachbarn, bis der Quellknoten informiert worden ist, wobei die Vorgängerknoten die Route zum Zielknoten als ungültig markieren. Danach kann die Routenfindung neu gestartet werden (Perkins et al. 2003, S. 24–25).

Ein Knoten kann überdies eine lokale Verbindungspflege ( Local Connectivity Mainte- nance“) betreiben, indem er periodisch HELLO-Nachrichten barn sendet (vgl. Perkins et al. 2003, S. 23–24).

4.3 Zone Routing Protocol (ZRP)

” r Broadcast an seine Nach- Das hybride ZRP-Framework versucht die Vorteile des proaktiven und reaktiven Ansatzes zu vereinen. Es nutzt die Tatsache, dass in MANETs ein Großteil des Netzwerkverkehrs zwischen nahe beieinanderliegenden Knoten stattfindet, derart, dass es das Netzwerk in überlappende Zonen variabler Größe einteilt. ZRP verwendet proaktive Routingverfahren, um Nachbarknoten in einer Zone zu finden, sowie reaktive Mechanismen, um zwischen den Zonen zu routen (Haas, Pearlman & Samar 2002, S. 2).

Die ZRP-Architektur besteht im Wesentlichen aus dem Intrazone Routing Protocol (IARP) und dem Interzone Routing Protocol (IERP).

[...]

Details

Seiten
47
Jahr
2008
ISBN (eBook)
9783640638475
ISBN (Buch)
9783640638987
Dateigröße
871 KB
Sprache
Deutsch
Katalognummer
v151750
Institution / Hochschule
Fachhochschule Technikum Wien
Note
1,0
Schlagworte
ad hoc networks wireless networks ad hoc network routing protocols MANET

Autor

Teilen

Zurück

Titel: Skalierbarkeit von Routingprotokollen in mobilen Ad-Hoc-Netzen