Kurzfassung und Abstract

Kurzfassung

Ein mobiles Ad-Hoc-Netzwerk (MANET) besteht aus mobilen Knoten, die ¨ uber Funk mit-einander kommunizieren und daf¨ ur keine Infrastruktur ben¨ otigen. Wachsende Knotenanzahl, erh¨ ohte Verkehrslast und steigende Knotenmobilit¨ at bedeuten f¨ ur Routingprotokolle in MANETs eine Herausforderung in Hinblick auf ihre Skalierbarkeit.

In dieser Arbeit soll ein ¨ Uberblick ¨ uber verschiedene Routingans¨ atze wie flaches Routing, hierarchisches Routing und geographisches Routing gegeben werden. Dabei werden ausgew¨ ahlte MANET-Routingprotokolle (AODV, OLSR, CBRP, FSR, ZRP, GPSR) als Vertreter der jeweiligen Ans¨ atze n¨ aher beschrieben.

Die ausgew¨ ahlten MANET-Routingprotokolle wurden im Netzwerksimulator NS-2 einem Leistungsvergleich im Hinblick auf ihre Skalierbarkeit in unterschiedlich großen MANETs (bis zu 200 Knoten) mit variierenden Parametern, wie Verkehrslast oder Pausenzeiten, unterzogen. Dabei wurden die Metriken Zustellrate, Verz¨ ogerung und Pfadoptimalit¨ at sowie Durchsatz herangezogen. Die daraus gewonnenen Ergebnisse werden pr¨ asentiert und bewertet. Es wird gezeigt, dass die getesteten Protokolle in großen Netzen mit hoher Knotenzahl, vor allem bez¨ uglich der Metriken Zustellrate und Durchsatz, deutlich schw¨ achere Leistungen erbringen als in kleineren Netzen mit weniger Knoten.

Abstract

Mobile ad hoc networks (MANETs) are networks of wireless mobile nodes without fixed infrastructure. Due to the highly dynamic topology there are special demands for routing protocols. Many routing protocols for MANETs have been proposed.

This paper deals with both a classification of MANET routing protocols and a review of the protocols AODV, OLSR, CBRP, FSR, ZRP and GPSR. Some results are presented, derived from the extended simulations that have been performed with the NS-2 network simulator, in order to compare the efficiency of the above protocols with respect to Paket Delivery Ratio, Average End-to-End Delay, Path Optimality and Throughput. Simulation results show that in terms of Paket Delivery Ratio and Throughput most protocols perform worse in larger networks with many nodes than in smaller ones with less nodes.

Keywords: ad hoc networks, wireless networks, ad hoc network routing protocols

FH Technikum Wien

FH Technikum Wien

Inhaltsverzeichnis

Inhaltsverzeichnis   

1  Problem- und Aufgabenstellung  2

2  Einleitung  3

3  Grundlagen  5

3.1  Eigenschaften und Anwendungsgebiete von mobilen Ad-Hoc-Netzwerken  5

3.2  Anforderungen an MANET-Routingprotokolle  6

3.3  Klassifizierung von MANET-Routingprotokollen  6

4  Ausgew ahlte Routingprotokolle f ur Mobile Ad-hoc-Netzwerke  9

4.1  Optimized Link State Routing (OLSR)  9

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

4.3  Zone Routing Protocol (ZRP)  12

4.4  Fisheye State Routing (FSR)  14

4.5  Cluster Based Routing Protocol (CBRP)  15

4.6  Greedy Perimeter Stateless Routing (GPSR)  17

5  Methodik  21

5.1  Der Simulator NS-2  21

5.2  Die Simulationsumgebung  22

5.3  Verwendete Metriken  23

5.4  Implementierung der Simulation  24

6  Ergebnisse der Simulation  26

6.1  Packet Delivery Ratio  26

6.2  Average End-to-End Delay  29

6.3  Path Optimality  33

6.4  Throughput  35

7  Fazit  39

Abbildungs  - und Tabellenverzeichnis  41

Abk  urzungsverzeichnis  42

Literaturverzeichnis   43

FH  Technikum Wien Seite  1

1 Problem- und Aufgabenstellung

Ein mobiles Ad-Hoc-Netzwerk (MANET) ist eine Menge von mobilen Knoten, die ¨ uber

Funk miteinander kommunizieren und ein tempor¨ ares Netzwerk ohne bestehende Infrastruktur und ohne zentrale Administration bilden. Da die ¨ Ubertragungsreichweite der

einzelnen Knoten begrenzt ist, m¨ ussen zwei Knoten, die miteinander Daten austauschen wollen, dies meist mit Hilfe von zwischen ihnen liegenden Knoten bewerkstelligen. Die Kommunikation in einem MANET wird dar¨ uber hinaus durch die hohe Dynamik seiner Mitglieder erschwert. Diese Netze m¨ ussen daher flexibel auf Topologie¨ anderungen reagieren k¨ onnen.

Aufgrund ihrer hohen Dynamik stellt das Routen von Paketen die gr¨ oßte Herausforderung in MANETs dar. Im Laufe der letzten Jahre wurde eine Vielzahl von Routingprotokollen vorgestellt, die das Routingproblem in MANETS auf unterschiedliche Weise zu l¨ osen versuchen. Im Rahmen dieser Arbeit wird untersucht, wie sich verschiedene MANET-Routingprotokolle im Hinblick auf ihre Leistung in Netzwerkszenarien von unterschiedlicher Dimension, Teilnehmerzahl, Knotenmobilit¨ at sowie Netzwerklast bew¨ ahren.

FH Technikum Wien Seite 2

2 Einleitung

Drahtlose Netze sind seit den Anf¨ angen ihrer Entwicklung in den 1970er Jahren ein intensiv 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¨ at von mobilen Ger¨ aten wie etwa Laptops, stark zugenommen.

Mobile drahtlose Netze lassen sich zurzeit in zwei Kategorien einteilen. Die erste Variante 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 ¨ uberall gebildet werden kann. Da die Sendeleistung der einzelnen Knoten beschr¨ ankt ist, erfolgt die Kommunikation in einem solchen Netz meist ¨ uber

tempor¨ are Multihop-Relays, wobei einige Knoten in Selbstorganisation als Router agieren.

Aufgrund der erw¨ ahnten Eigenschaften von MANETs sind diese Netze neben ihrem urspr¨ unglichen Einsatzgebiet - milit¨ arischen Operationen - beispielsweise f¨ ur den Aufbau von Sensornetzen ( ” Smart Dust“) oder mobilen Fahrzeugnetzen (sog. VANETs) gut geeignet.

Das erw¨ ahnte Multihop-Routing, die willk¨ urlichen Knotenbewegungen sowie andere MANET-Eigenschaften, wie z. B. begrenzte Energieressourcen oder die eingeschr¨ ankte 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¨ anden m¨ oglichst effizient gel¨ ost werden kann.

Um das Multihop-Routingproblem in MANETs l¨ osen zu k¨ onnen, ist eine Vielzahl unterschiedlicher Protokolle entwickelt worden. Einige davon verfolgen einen sog. flachen Ansatz, in dem es keine ausgezeichneten Knoten gibt, andere versuchen durch Einf¨ uhrung von Hierarchien die Effizienz, besonders in großen Netzen, zu steigern. Eine weitere Gruppe von Protokollen macht sich etwa die Vorteile der satellitengest¨ utzten Navigation (z. B. GPS) zunutze, um die Probleme der zuvor angef¨ uhrten topologiebasierten Verfahren zu umgehen. Diese Protokolle werden unter dem Begriff geographische Routingprotokolle subsumiert.

In dieser Arbeit werden ausgew¨ ahlte Routingprotokolle aus den oben genannten Klassen beschrieben. Es sind dies als Vertreter der flachen Routingans¨ atze OLSR, AODV, ZRP sowie das implizit hierarchische FSR. Als ein Protokoll, das einen hierarchischen Ansatz umsetzt, wird die Funktionsweise von CBRP n¨ aher erl¨ autert. Das schlussendlich beschriebene GPSR geh¨ ort zur Familie der geographischen, positionsbasierten Protokolle.

Diese Routingprotokolle werden im Rahmen der vorliegenden Arbeit mittels NS-2-Simulator in Bezug auf ihre Leistungsf¨ ahigkeit getestet. Besonderes Augenmerk wird dabei auf die Skalierbarkeit der Protokolle im Hinblick auf variierende Parameter gelegt. So werden die Protokolle in drei unterschiedlich groß dimensionierten Gebieten, mit unterschiedlicher Knotenanzahl und -mobilit¨ at sowie unterschiedlichen Verkehrslasten getestet.

FH Technikum Wien Seite 3

Die weitere Arbeit ist wie folgt aufgebaut:

In Kapitel 3 werden zun¨ achst Eigenschaften und typische Anwendungsgebiete von MA-NETs beschrieben. Danach wird genauer auf die Routingproblematik in MANETs eingegangen und die speziellen Anforderungen an Routingprotokolle f¨ ur 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¨ aher beschrieben, die im Rahmen 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¨ autert. Zun¨ achst wird ein grober ¨ Uberblick ¨ uber die Funktionalit¨ at des Netzwerk-Simulators NS-2 gegeben. Danach wird detailliert auf das Szenario der durchgef¨ uhrten Simulation eingegangen und die verwendeten Metriken werden erl¨ autert. Das Kapitel schließt mit einer kurzen Beschreibung der konkreten Simulationsimplementierung.

In Kapitel 6 werden die Ergebnisse der Simulation pr¨ asentiert.

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

FH Technikum Wien Seite 4

3 Grundlagen

In diesem Kapitel werden die Grundlagen f¨ ur die nachstehenden Kapitel kurz dargelegt. Zun¨ achst werden Eigenschaften und Anwendungsgebiete von MANETs erl¨ autert. Es folgt eine Beschreibung der speziellen Anforderungen, die ein MANET an Routingprotokolle stellt. Den Abschluss dieses Kapitels bildet eine umfassende Klassifizierung der f¨ ur mobile Ad-Hoc-Netzwerke ¨ ublichen Routingprotokolle.

3.1 Eigenschaften und Anwendungsgebiete von mobilen Ad-Hoc-

Netzwerken

Ein mobiles Ad-Hoc-Netzwerk (MANET) besteht aus mobilen Ger¨ aten (Knoten), die sich beliebig bewegen k¨ onnen. Jeder dieser Knoten besteht logisch gesehen aus einem Router, der mehrere Hosts und auch mehrere drahtlose Kommunikationsger¨ ate 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 ¨ uber 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¨ onnen, kann sich die Netzwerktopologie zuf¨ allig und schnell zu unvorhersehbaren Zeiten ¨ andern. Verbindungen zwischen Knoten k¨ onnen uni- oder bidirektional sein. Das Routing hat typischerweise Multihop-Charakter.

Bandbreitenbeschr¨ ankung, variable Verbindungskapazit¨ aten: Drahtlose Verbindungen haben eine wesentlich niedrigere Kapazit¨ at als drahtgebundene Verbindungen, außerdem ist der tats¨ achliche Durchsatz von drahtlosen Verbindungen zumeist niedriger als der maximal m¨ ogliche Wert einer Radiowellen- ¨ Ubertragung. Dies wird

durch verschiedene Faktoren wie mehrfacher Zugriff auf das Medium, Hintergrundrauschen, Multihopping, die exponentielle Abschw¨ achung des Signals sowie Interferenzen nahe gelegener drahtloser Verbindungen hervorgerufen.

Energieabh¨ angiger Betrieb: In einem MANET haben viele oder auch alle Knoten nur eine beschr¨ ankte Energiemenge zur Verf¨ ugung, insofern ist die Optimierung des Energieverbrauchs dieser Knoten das wichtigste Designkriterium.

Eingeschr¨ ankte physische Sicherheit: Drahtlose Netzwerke sind generell anf¨ alliger gegen¨ uber physikalischen Sicherheitsbedrohungen als drahtgebundene Netze. So besteht eine erh¨ ohte Wahrscheinlichkeit, dass Pakete verworfen oder gef¨ alscht werden, und auch ” Denial of Service“-Attacken sind einfach durchzuf¨ uhren. Oft werden Punkt-zu-Punkt-Sicherheitsverfahren verwendet, um die Sicherheitsbedrohung zu reduzieren. Als Vorteil eines MANETs kann jedoch der dezentralisierte Charakter gewertet werden. Das Netzwerk wird dadurch robuster gegen einzelne Knotenausf¨ alle als bei zentralisierten Ans¨ atzen.

FH Technikum Wien Seite 5

Die wichtigsten Anwendungsgebiete von MANETs sind Bereiche, in denen keine entsprechende Infrastruktur vorhanden ist und Netzwerke unterschiedlicher Gr¨ oße schnell und dynamisch konfiguriert werden m¨ ussen. MANETs k¨ onnen nach Perkins (2001, S. 8-14) u. a. bei Eins¨ atzen in Katastrophengebieten, im Bereich des ” Ubiquitous Computing“, bei

sog. Personal Area Networks (PAN), Sensornetzwerken oder in der Fahrzeugkommunikation (Vehicular Ad-hoc-Network, VANET) Anwendung finden.

3.2 Anforderungen an MANET-Routingprotokolle

Um die Leistung eines MANET-Routingprotokolls bewerten zu k¨ onnen, werden eine Reihe von qualitativen und quantitativen Metriken herangezogen. Diese Metriken m¨ ussen unabh¨ angig von dem verwendeten Routingprotokoll sein. Corson & Macker (1999, S. 6) nennen folgende w¨ unschenswerte qualitative Eigenschaften eines MANET-Routingprotokolls:

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

Schleifenfreiheit: Dies ist prinzipiell eine w¨ unschenswerte Eigenschaft, um Probleme, wie z. B. Pakete, die eine willk¨ urliche 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¨ ort, manipuliert oder umgeleitet werden als die Kommunikation in Festnetzen. Daher sind ausreichende Sicherungsmaßnahmen erforderlich, um St¨ orung oder Modifikation des Protokollbetriebs zu verhindern.

Schlafperioden: Da Knoten in MANETs oft beschr¨ ankte Energieressourcen haben, k¨ onnen Knoten, um Energie zu sparen, den Versand oder Empfang von Paketen f¨ ur eine Dauer einstellen. Ein MANET-Routingprotokoll muss solche Schlafperioden ber¨ ucksichtigen k¨ onnen, ohne dass daraus allzu große Nachteile entstehen.

Unidirektionale Verbindungen: Mobile Knoten in MANETs verf¨ ugen ¨ uber unterschiedliche Sende- und Empfangseinheiten. Daher sind asymmetrische Verbindungen m¨ oglich, d. h., der Transport von Paketen muss auf unterschiedlichen Hin- und R¨ uckwegen abgewickelt werden k¨ onnen.

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

3.3 Klassifizierung von MANET-Routingprotokollen

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

FH Technikum Wien Seite 6

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

Beim DVR werden jene Daten der Netzwerktopologie aus den Routingtabellen entnommen, die ein Knoten in regelm¨ aßigen Abst¨ anden von seinen unmittelbaren Nachbarn als Kopien erh¨ alt. Das Verfahren beruht auf dem Bellman-Ford-Algorithmus, wobei die Knoten den besten Pfad ermitteln, indem sie die Metriken (z. B. Distanz oder Verz¨ ogerung) 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¨ andige Netzwerktopologie bekannt, da sie in regelm¨ aßigen Abst¨ anden Informationen ¨ uber ihre Verbindungszust¨ ande im Netzwerk flu-

ten. Dadurch k¨ onnen sie getrennt voneinander den jeweils k¨ urzesten Pfad zum Ziel mittels SPF-Algorithmus (SPF) von Dijkstra berechnen. Beim LSR werden Aktualisierungen direkt durch ¨ Anderungen in der Netzwerktopologie ausgel¨ ost. Die weitergegebenen Topolo-gieinformationsnachrichten (Link State Packets, LSPs) sind relativ klein, dadurch sind die Konvergenzzeiten bei Topologie¨ anderungen 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¨ otigt jeder Knoten teilweise oder komplette Information ¨ uber die Verbindungszust¨ ande und Netzwerktopologie. Um

diese Informationen auf dem Laufenden zu halten, m¨ ussen Knoten sie in regelm¨ aßigen Abst¨ anden, bei ¨ Anderung von Verbindungszust¨ anden oder der Netzwerktopologie aktualisieren. Der Vorteil dieses Verfahrens ist, dass Routen von der Quelle zum Ziel jederzeit verf¨ ugbar sind, nachteilig ist der relativ hohe Verbrauch von Netzwerk-Bandbreite auf-grund der ¨ Ubertragung 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¨ otigt werden. Aufgrund dieser Routenbestimmung ergibt sich eine Latenzzeit am Beginn der ¨ Ubertragung eines Nutzdatenpaketes. Der Vorteil des reaktiven Ansatzes besteht darin, dass Kontrollnachrichten nur relativ wenig Bandbreite ben¨ otigen (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-

FHTechnikum Wien Seite 7