Kurzfassung und Abstract

Kurzfassung

Ein mobiles Ad-hoc-Netzwerk (MANET) besteht aus mobilen Knoten, die ¨ uber Funk mitein-ander kommunizieren. Da die Netzwerke von sehr hoher Dynamik gepr¨ agt sind, verf¨ ugen sie uber keine Infrastruktur. Das bedeutet, dass sich die Knoten selbst organisieren und auch Rou¨ tingfunktionalit¨ at ¨ ubernehmen m¨ ussen. Die gr¨ oßte Herausforderung in einem solchen Netz ist das Auffinden von Pfaden zwischen den Kommunikationsendpunkten.

Ein Ansatz, dieses verteilte Routing zu bewerkstelligen, folgt dem Paradigma der Schwarmintelligenz und im Speziellen dem der sog. Ant-Colony-Optimization (ACO). Hierbei wird das kollektive Futtersuchverhalten von Ameisen nachgebildet, um einen Pfad durch ein Netzwerk zu finden.

In dieser Arbeit werden ausgew¨ ahlte MANET-Routingprotokolle (OLSR, AODV, ARA, PE-RA, SWARM) beschrieben und mittels Softwaresimulation (NS-2 Network Simulator) einem Leistungsvergleich in verschiedenen Szenarios mit variierenden Parametern unterzogen. Dabei werden die Metriken Zustellrate, Verz¨ ogerung, Durchsatz sowie das Berechnen der optimalen Route herangezogen. Es wird gezeigt, dass die schwarmintelligenzbasierten Routingprotokolle eine vergleichbare Leistung wie etablierte robuste Protokolle zeigen.

Abstract

Mobile Ad Hoc Networks (MANETs) are networks without infrastructure. These kinds of networks consist of wireless mobile nodes which are organized in an autonomous fashion. Due to the highly dynamic topology, the routing problem is a challenging one.

Several protocols based on the swarmintelligence paradigm and especially on the ant colony optimization metaheuristic have been proposed. These protocols use ant-like agents to discover and maintain paths in a MANET.

In this paper several MANET routing protocols (OLSR, AODV, ARA, PERA, SWARM) will be compared and tested with the NS-2 network simulator.

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  Mobile Ad-hoc-Netzwerke  5

3.1.1  Eigenschaften von mobilen Ad-hoc-Netzwerken  5

3.1.2  Anwendungsgebiete  6

3.2  Routing in mobilen Ad-hoc-Netzwerken  7

3.2.1  Anforderungen an MANET-Routingprotokolle  7

3.2.2  Kategorien von Ad-hoc-Routingprotokollen  8

3.3  Schwarmintelligenz  9

3.3.1  Selbstorganisation sozialer Insekten  9

3.3.2  Schwarmkommunikation  10

3.3.3  Ameisenalgorithmen  10

3.4  Fazit  13

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

4.1  OLSR  14

4.2  AODV  16

4.3  ARA  17

4.4  PERA  19

4.5  SWARM  20

4.6  Fazit  21

5  Methodik  22

5.1  Der Simulator  22

5.2  Die Simulationsumgebung  23

5.3  Das Bewegungsmodell  23

5.4  Das Kommunikationsmodell  24

5.5  Metriken  25

5.6  Implementierung der Simulation  25

6  Ergebnisse der Simulation  27

6.1  Packet Delivery Ratio  27

6.2  Average End-to-End Delay  28

6.3  Path Optimality  29

6.4  Troughput  30

7  Fazit und Ausblick  31

Abbildungs  - und Tabellenverzeichnis  32

Abk  urzungsverzeichnis  33

Literaturverzeichnis   34

FH  Technikum Wien Seite  1

1 Problem- und Aufgabenstellung

Ein mobiles Ad-hoc-Netzwerk (MANET) besteht aus einer Menge von Knoten, die ¨ uber Funk

miteinander kommunizieren. Knoten in einem MANET bewerkstelligen dies, indem sie sich, ohne ¨ uber eine Infrastruktur zu verf¨ ugen, selbst organisieren. MANETs sind dar¨ uber hinaus Netzwerke, die von hoher Dynamik gekennzeichnet sind, diese Netze m¨ ussen daher flexibel auf Topologie¨ anderungen reagieren.

Selbstorganisation bedeutet in einem MANET, dass die einzelnen Knoten auch Routingfunktionalit¨ at ¨ ubernehmen m¨ ussen. Aufgrund der hohen Dynamik eines MANETs ist die Routingproblematik die gr¨ oßte Herausforderung in MANETs. Da Ad-hoc-Netzwerkknoten nur direkt mit Knoten, die sich in ihrer Reichweite befinden, kommunizieren k¨ onnen, m¨ ussen sie, um weiter entfernte Knoten erreichen zu k¨ onnen, miteinander bez¨ uglich des Routings kooperieren.

Um die geforderte Knotenkooperation in einem MANET effizient gew¨ ahrleisten zu k¨ onnen, kann man sich des Vorbilds des Verhaltens sozialer Insekten, wie z. B. Bienen oder Ameisen, bedienen. In solchen Schw¨ armen wird durch das Zusammenarbeiten relativ einfacher Individuen eine komplexe Aufgabe gel¨ ost.

F¨ ur das Routing in Netzwerken ist besonders das Futtersuchverhalten von Ameisen interessant, da Ameisen sehr schnell k¨ urzeste Pfade von ihrem Nest zu einer Futterquelle finden. So wurde eine Reihe von Routingalgorithmen entwickelt, die bei der Suche des k¨ urzesten Pfades in einem Netzwerk auf diesem Schwarmintelligenz-Paradigma und im Besonderen auf der Ant-Colony-Optimization-Metaheuristik (ACO-Metaheuristik) basieren.

Im Rahmen dieser Arbeit wird untersucht, wie sich schwarmintelligenzbasierte MANET-Routingprotokolle im Vergleich mit etablierten MANET-Routingprotokollen bew¨ ahren.

FH Technikum Wien Seite 2

2 Einleitung

Ad-hoc-Netzwerke sind kabellose, mobile Netzwerke ohne Infrastruktur, die jederzeit ¨ uberall

gebildet werden k¨ onnen. Die Kommunikation in einem solchen dezentralen Netzwerk erfolgt typischerweise ¨ uber tempor¨ are Multihop-Relays, wobei einige Knoten als Router agieren, ohne dass eine fixe Infrastuktur vorhanden ist.

Diese Art von Netzen ist sehr flexibel und kann dort sinnvollen Einsatz finden, wo es nur wenig oder gar keine Kommunikationsinfrastruktur gibt, beispielsweise bei Katastropheneins¨ atzen oder milit¨ arischen Operationen.

Doch das Multihop-Routing, die willk¨ urlichen Knotenbewegungen und andere MANET-Eigenheiten bedeuten eine große Herausforderung f¨ ur das Routing - das Hauptproblem in einem Netzwerk. Dazu kommen, verglichen mit einem herk¨ ommlichen Netzwerk, weitere Einschr¨ ankungen wie z. B. begrenzte Energieressourcen oder Bandbreiten der Knoten. Es stellt sich also die Frage, wie die Routenfindung und -pflege in einer solch schwierigen Umgebung m¨ oglichst effizient gel¨ ost werden kann.

Da zumindest seit dem Jahr 1973 auf dem Gebiet der MANETs geforscht wird, gibt es bereits eine Vielzahl von Routingalgorithmen, die speziell auf die Gegebenheiten von MANETs zugeschnitten worden sind. Einige basieren auf Routingmechanismen der tradionellen kabel-gebundenen Netzwerke und versuchen, jederzeit Routinginformationen ¨ uber alle Netzknoten

zu verwalten, w¨ ahrend reaktive Ans¨ atze nur dann neue Routen zu finden versuchen, wenn ben¨ otigt.

Seit den 1990er-Jahren existiert eine neue Gruppe von Routingalgorithmen, die, vom Schwarmintelligenz-Paradigma inspiriert, einen neuen Ansatz zur L¨ osung von verteilten Optimierungsproblemen darstellen. Hierbei bildet man das nat¨ urliche Vorbild des kollektiven Verhaltens von sozialen Tiergesellschaften, wie z. B. das Futtersuchverhalten von Ameisenkolonien, auf mathematische Probleme wie das Finden eines k¨ urzesten Pfades durch ein Netzwerk ab.

Ameisen sind in der Lage, innerhalb kurzer Zeit einen optimalen Pfad von ihrem Nest zu einer Futterquelle zu finden und zu erhalten. Schwarmintelligenz stellt also eine Grundlage dar, verteilte Optimierungsprobleme ohne das Vorhandensein einer zentralen Kontrollinstanz zu l¨ osen.

Es gibt seit einigen Jahren einige Algorithmen, die sich die Eigenschaften von futtersuchenden Ameisen zunutze machen, um mit einfachen, ameisen¨ ahnlichen Agenten die in MANETs ben¨ otigten verteilten Verfahren zur L¨ osung der Routingproblematik zu verwirklichen.

In dieser Arbeit werden ausgew¨ ahlte schwarmintelligenzbasierte Routingprotokolle (ARA, PE-RA, SWARM) und tradionelle Routingprotokolle (OLSR, AODV) n¨ aher beschieben und mittels NS-2 Netzwerk-Simulator in einer simulierten Umgebung einem Leistungsvergleich unterzogen.

Die Arbeit ist wie folgt aufgebaut:

In Kapitel 3 werden grundlegende Eigenschaften von MANETs sowie deren m¨ ogliche Anwendungsgebiete beschrieben. Danach wird genauer auf die Routingproblematik in mobilen Ad-hoc-Netzen eingeganen, es werden die Anforderungen an Routingalgorithmen benannt und eine grobe topologische Klassifikation der Protokolle wird erstellt. In Kapitel 3.3 wird dann

FH Technikum Wien Seite 3

das Schwarmintelligenz-Paradigma eingehend erl¨ autert: Ausgehend von den nat¨ urlichen Vorbildern - im Falle dieser Arbeit sind dies Ameisenkolonien - wird beschrieben, wie Selbstorganisation und Schwarmkommunikation funktionieren. Darauf aufbauend wird das Konzept der Ameisenalgorithmen vorgestellt, im Speziellen der erste Vertreter dieser Algorithmusart: Ant System (AS).

In Kapitel 4 werden jene Routingprotokolle vorgestellt und n¨ aher beschrieben, die sp¨ ater einem Leistungsvergleich unterzogen werden: OLSR als Vertreter der proaktiven Protokolle, AODV als Vertreter der reakiven Protokolle sowie die schwarmintelligenzbasierten Protokolle ARA, PERA und SWARM.

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 verwendeteten Metriken werden erl¨ autert. Das Kapitel schließt mit einer kurzen Beschreibung der konkreten Simulationsimplementierung. Die Quelltexte der eigens f¨ ur dieses Experiment erstellten Programme befinden sich im Anhang.

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

Kapitel 7 schließt die Arbeit mit einer Zusammenfassung der vorgestellten Erkenntnisse und einem kurzen Ausblick ab.

FH Technikum Wien Seite 4

3 Grundlagen

In diesem Kapitel werden kurz die Themenbereiche erl¨ autert, die die Grundlagen f¨ ur die nachfolgenden Kapitel darstellen. Zun¨ achst werden die wichtigsten Eigenschaften und Anwendungsgebiete von mobilen Ad-hoc-Netzwerken beschrieben. Danach wird dargelegt, welche Anforderungen aufgrund der speziellen Eigenschaften von mobilen Ad-hoc-Netzwerken an Routingal-gorithmen gestellt werden. Es folgt eine kurze Klassifikation der f¨ ur Ad-hoc-Netzwerke ¨ ublichen

Algorithmen. Den letzten Teil dieses Kapitels bildet das Thema Schwarmintelligenz: Behandelt werden relevante Bereiche wie die Selbstorganisation sozialer Insekten und die Kommunikation innerhalb eines Schwarmes sowie Ameisenalgorithmen - als der konkrete Teilbereich der Schwarmintelligenz, der die Grundlage f¨ ur die zu untersuchenden schwarmintelligenzbasierten Routingprotokolle in dieser Arbeit darstellt.

3.1 Mobile Ad-hoc-Netzwerke

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 MA-NET ist ein autonomes System 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 Netzen verbunden sein (Corson & Macker 1999, S. 3).

3.1.1 Eigenschaften von mobilen Ad-hoc-Netzwerken

In der Literatur werden Ad-hoc-Netzwerke meist nach der Art, wie Knoten miteinander kommunizieren (single-hop oder multihop), unterschieden. Eine weitere Unterscheidung wird in flache oder hierarchische Netze vorgenommen (Perkins 2001, S. 43).

Bei Single-hop-Netzwerken befinden sich die Knoten in direkter Reichweite, d. h., zwei Knoten k¨ onnen direkt miteinander kommunizieren, ohne dass der Kommunikationsverkehr ¨ uber

andere Knoten weitergeleitet werden muss. In einem mobilen Multihop-Netzwerk hingegen muss der Kommunikationsverkehr zwischen einem Quell- und Zielknoten ¨ uber Zwischenknoten weitergeleitet werden. Weil die einzelnen Knoten mobil sind, ist die Netztopologie st¨ andigen Ver¨ anderungen ausgesetzt.

Da die Multihop-Topologie die vorherrschende Topologie in MANETs ist, wird im weiteren Verlauf dieser Arbeit nur noch auf mobile Multihop-Ad-hoc-Netzwerke eingegangen.

MANETs haben nach Corson & Macker (1999, S. 3f) folgende herausragende 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, und das Routing hat typischerweise Multihop-Charakter.

FH Technikum Wien Seite 5

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 meist niedriger als der maximal m¨ ogliche Wert einer Radiowellen- ¨ Ubertragung. Das 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. Aus diesem Grund ist die Optimierung des Energieverbrauchs dieser Knoten das wichtigste Designkriterium.

Eingeschr¨ ankte physische Sicherheit: Drahtlose Netzwerke sind prinzipiell 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.

3.1.2 Anwendungsgebiete

Die wichtigsten Anwendungsgebiete von MANETs sind generell Bereiche, in denen keine entsprechende Infrastruktur zur Verf¨ ugung steht und Netzwerke unterschiedlicher Gr¨ oße schnell und dynamisch konfiguriert werden m¨ ussen. MANETs k¨ onnen nach Perkins (2001, S. 8-14) u. a. in folgenden Bereichen Anwendung finden:

Mobile Konferenz: Wenn sich die Benutzer von mobilen Computern außerhalb ihrer normalen B¨ uroumgebung treffen, fehlt oft die n¨ otige Netzwerkinfrastruktur, um eine Zusammenarbeit zu erm¨ oglichen. Daher ist der Aufbau von Ad-hoc-Netzen zur Zusammenarbeit von Benutzern, die mobile Computer haben, sogar dann notwendig, wenn die Internetinfrastruktur schon vorhanden ist.

Heimnetzwerk: Wenn ein Benutzer einen mobilen Computer sowohl im B¨ uro als auch zu Hause verwendet, ist es m¨ oglicherweise bequemer, zu Hause ein Ad-hoc-Netzwerk aufzubauen, um die IP-Adressen f¨ ur den mobilen Computer nicht oft ¨ andern zu m¨ ussen.

Katastrophensituationen: Typischerweise brechen die meisten auf drahtgebundenen Netzen basierenden Kommunikationsinfrastrukturen in Katastrophengebieten zusammen. Deswegen k¨ onnen sich Rettungsteams nicht auf eine vorhandene Kommunikationsinfrastruktur verlassen, sondern m¨ ussen diese selbst errichten. Hier ist meist keine exakte Planung im Voraus m¨ oglich und die Errichtung eines Kommunikationsnetzes muss sehr schnell und zuverl¨ assig geschehen.

Personal Area Network (PAN) und Bluetooth: Hier wird auf sehr begrenztem Raum ein Netzwerk geschaffen, das aus Knoten besteht, die eng mit einer einzigen Person verbunden sind. Diese Ger¨ ate k¨ onnen beispielsweise am G¨ urtel der Person befestigt sein oder in

FH Technikum Wien Seite 6

der Handtasche transportiert werden. Diese Ger¨ ate m¨ ussen untereinander kommunizieren k¨ onnen, solange sie vom Benutzer ben¨ otigt werden. Mobilit¨ at wird ein entscheidendes Kriterium, wenn Interaktionen zwischen mehreren PANs erw¨ unscht sind. Bluetooth bietet eine drahtlose Schnittstelle, ¨ uber die sowohl mobile Kleinger¨ ate wie Mobiltelefone

und pers¨ onliche digitale Assistenten (PDAs) als auch Computer und Peripherieger¨ ate miteinander kommunizieren k¨ onnen. Hauptzweck von Bluetooth ist das Ersetzen von Kabelverbindungen zwischen solchen Ger¨ aten.

Eingebettete Computeranwendungen: Durch die fortschreitende Miniaturisierung von elektronischen Gegenst¨ anden sollen zuk¨ unftig verschiedenste Alltagsgegenst¨ ande mit eigener Rechenleistung ausgestattet sein, Sensoren besitzen und mit anderen Gegenst¨ anden kommunizieren, wobei sie sich nahtlos und unsichtbar zum Ziel der Unterst¨ utzung des Menschen in die Umwelt einf¨ ugen. Computer im Sinne dieses Ubiquitous Computing kommunizieren meist ¨ uber ein mobiles Ad-hoc-Netz.

Sensor Dust: Ein Sensornetz besteht aus einer großen Anzahl von Sensorknoten - winzigen, drahtlos kommunizierenden Computern -, die in einem Ad-hoc-Netz zusammenarbeiten, um ihre Umgebung mittels Sensoren zu ¨ uberwachen. Solche Sensornetze k¨ onnen beispielsweise detaillierte Informationen ¨ uber Terrain- oder Umweltver¨ anderungen be-

reitstellen. Eine weitere Einsatzm¨ oglichkeit sind milit¨ arische Anwendungen.

Fahrzeugkommunikation: Ein sog. Vehicular Ad-hoc-Network (VANET) ist ein spezielles MANET, das die direkte Kommunikation zwischen Fahrzeugen erm¨ oglicht. Dadurch k¨ onnen etwa Fahrzeugsicherheit und -komfort entscheidend verbessert werden. So kann z. B. die Kommunikation zwischen Fahrzeugen dazu benutzt werden, um aktive Sicherheitsservices, wie etwa Bremswarnungen, Kollisionswarnungen, aktuelle Verkehrs- und Wetterinformationen oder aktive Navigationssysteme, zu realisieren (Rybicki, Scheuermann, Kiess, Lochert, Fallahi & Mauve 2007, S. 215).

3.2 Routing in mobilen Ad-hoc-Netzwerken

Wie bereits gezeigt worden ist, sind Verbindungen zwischen Knoten in MANETs von hoher Dynamik und Zuf¨ alligkeit gekennzeichnet. Die einzelnen Knoten m¨ ussen daher selbst Routerfunktionen ¨ ubernehmen, sich also um Routenfindung und -pflege k¨ ummern.

Das Ziel eines Routingalgorithmus als Teil der Netzwerkschicht-Software eines Netzknotens ist es, aufgrund gewisser Metriken (z. B. Hop-Anzahl, Bandbreite, Verz¨ ogerung, Zuverl¨ assigkeit, Energieverbrauch) zu entscheiden, ¨ uber welchen Pfad Pakete an ein bestimmtes Ziel gelangen sollen.

3.2.1 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 vom verwendeten Routingprotokoll sein. Corson & Macker (1999, S. 6f) nennen folgende

FH Technikum Wien Seite 7