Inhaltsverzeichnis

1  Einf uhrung  1

1.1  Wireless-Mesh-Netzwerke  2

1.2  Clustering  2

1.3  Adaptive Cluster-Infrastruktur  2

1.3.1  Distanzadaptive Algorithmen  2

1.3.2  Stabilit atsorientiert und adaptiv  3

1.3.3  Modulare Architektur  3

1.4  Anwendungsbeispiel Dienstsuche  3

1.5  Gliederung  3

2  Wireless-Mesh-Netzwerke  5

2.1  Architektur  5

2.1.1  Infrastruktur-Wireless-Mesh-Netzwerk  6

2.1.2  Client-Wireless-Mesh-Netzwerk  6

2.1.3  Hybrides Wireless-Mesh-Netzwerk  7

2.2  Unterschiede zu MANETs  8

2.3  Routing  8

2.3.1  Klassifikation von Routingverfahren  9

2.3.2  Optimized Link State Routing Protocol  10

2.3.3  Dynamic Source Routing  10

2.3.4  Zone Routing Protocol  12

2.3.5  IEEE 802.11s  12

2.4  Einsatzm oglichkeiten  13

3  Clustering  15

3.1  Einf uhrung  15

3.2  Grundlagen  16

3.2.1  Dominating Sets  17

3.3  Anwendung  17

3.3.1  Routing  18

3.3.2  Service Discovery  19

3.3.3  Weitere Anwendungsfelder  19

3.4  Klassifikation von Clustering-Verfahren  20

3.5  Clustering-Verfahren f ur Ad-Hoc-Netzwerke  21

3.5.1  Lowest-ID  21

3.5.2  Highest-Connectivity  23

3.5.3  CDS-Algorithmus von Wu und Li  24

v

3.6 Bewertung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

4 Theoretische Ausarbeitung 33

4.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 4.2 Informationsaustausch . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 4.3 Metriken . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

4.4 Clustering-Algorithmen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

4.5 Distanzadaptive Algorithmen . . . . . . . . . . . . . . . . . . . . . . . . . . 47

5 Praktische Ausarbeitung 55

5.1 Fleximsd . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

5.2 Relayd . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63

5.3 Realisierung der Distanzadaptierung . . . . . . . . . . . . . . . . . . . . . . 67

Inhaltsverzeichnis vii

5.3.6  Diskussion anderer Ans atze  72

5.4  Verbesserung der Wahlstabilit at  73

5.4.1  Score-Threshold  73

5.4.2  Auto-Flapping  74

5.5  Gateway-Bestimmung  76

5.5.1  Lokaler Algorithmus  76

5.5.2  Superknoten-zentrisch  77

5.6  Zusammenfassung  78

6  Auswertung  81

6.1  Testumgebung und Pr asentation der Ergebnisse  81

6.1.1  UMIC-Testbed  81

6.1.2  Aufbau der Messungen  82

6.2  Analyse der Abh angigkeit der Maximal-Distanz  82

6.2.1  Durchf uhrung  82

6.2.2  Ergebnisse  83

6.2.3  Bewertung  84

6.3  Analyse der Clustering-Verfahren  87

6.3.1  Durchf uhrung  87

6.3.2  Ergebnisse  87

6.3.3  Bewertung  88

6.4  Analyse des Auto-Flapping Verfahrens  89

6.4.1  Durchf uhrung  90

6.4.2  Ergebnisse  90

6.4.3  Bewertung  91

6.5  Analyse der distanzadaptiven Algorithmen  91

6.5.1  Durchf uhrung  91

6.5.2  Ergebnisse  92

6.5.3  Bewertung  93

6.6  Analyse des Greedy-Expand Algorithmus uber 24 Stunden  94

6.6.1  Durchf uhrung  94

6.6.2  Ergebnisse  94

6.6.3  Bewertung  95

6.7  Analyse der Cluster-Strukturen mittels Relayd  97

6.7.1  Durchf uhrung  97

6.7.2  Ergebnisse  97

6.7.3  Bewertung  98

7  Zusammenfassung und Ausblick  101

7.1  Zusammenfassung  101

7.2  Ausblick  102

viii Inhaltsverzeichnis

2.1 Infrastruktur-WMN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.2 Client-WMN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.3 Hybrid-WMN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.4 OLSR MPR Mechanismus . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.5 ZPR Routingzonen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

3.1 Netzwerkstruktur mit drei Clustern . . . . . . . . . . . . . . . . . . . . . . . 16 3.2 Dominating Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 3.3 Exemplarisches Routing in einer Cluster-Struktur . . . . . . . . . . . . . . . 19 3.4 Service Discovery: Nutzung eines Verzeichnisagenten . . . . . . . . . . . . . 20 3.5 Problematische Topologie bei Lowest-ID . . . . . . . . . . . . . . . . . . . . 22 3.6 Der Ripple Effect bei Lowest-ID . . . . . . . . . . . . . . . . . . . . . . . . 23 3.7 Cluster-Struktur mit Highest-Connectivity . . . . . . . . . . . . . . . . . . . 24 3.8 Der Wu-Li CDS-Algorithmus . . . . . . . . . . . . . . . . . . . . . . . . . . 25 3.9 Die einzelnen Schritte eines Cluster-Merge in AMC . . . . . . . . . . . . . . 28 3.10 Min-Searching im adaptiven ZRP . . . . . . . . . . . . . . . . . . . . . . . . 29 3.11 Optimaler Bereich zwischen reaktiver und proaktiver Dominanz . . . . . . . 29 3.12 Clustering mit Cliquen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

4.1 Adaptives Clustering-Framework . . . . . . . . . . . . . . . . . . . . . . . . 34 4.2 Schematische Darstellung der Clustering-Verfahren . . . . . . . . . . . . . . 43 4.3 Cluster-Strukturen mit Lowest-ID . . . . . . . . . . . . . . . . . . . . . . . 44 4.4 Gewichtung bei Max-Score mit k-distance = 3 . . . . . . . . . . . . . . . . . 46 4.5 Absolute Maximum-Differenz dreier Elite-Auswahlfunktionen . . . . . . . . 47 4.6 Egoistischer Ansatz: Gradientenverfahren . . . . . . . . . . . . . . . . . . . 51 4.7 Beispiel des Greedy-Expand Algorithmus . . . . . . . . . . . . . . . . . . . 53

5.1 Aufbau einer NSI-Nachricht . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 5.2 Fleximsd Wahl-Architektur . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 5.3 Filterschritt: Kombination von mehreren Candidate-Constraints . . . . . . . 61 5.4 Aufbau der REGISTER-Nachricht . . . . . . . . . . . . . . . . . . . . . . . . . 62 5.5 Aufbau der ACCEPTANCE-Nachricht . . . . . . . . . . . . . . . . . . . . . . . 62 5.6 Zusammenspiel zwischen Fleximsd und Relayd sowie dem Endnutzer . . . . 64 5.7 Aufbau der Multi-Hop DNS-SD-Nachricht . . . . . . . . . . . . . . . . . . . 64 5.8 Aufbau eines einzelnen Dienstes im Payload . . . . . . . . . . . . . . . . . . 65 5.9 Dienstsuche und -weiterleitung in Relayd . . . . . . . . . . . . . . . . . . . 67 5.10 Dynamic Source Routing in Relayd . . . . . . . . . . . . . . . . . . . . . . . 68 5.11 Aufbau der K-REQUEST-Nachricht . . . . . . . . . . . . . . . . . . . . . . . . 70

ix

x Abbildungsverzeichnis

5.12 Aufbau der K-SCORE-Nachricht . . . . . . . . . . . . . . . . . . . . . . . . . 71 5.13 Beispiel lokal ermittelter Gateway-Knoten . . . . . . . . . . . . . . . . . . . 77 5.14 Beispiel per Superknoten ermittelter Gateway-Knoten . . . . . . . . . . . . 78

6.1 Entwicklung der Nachbarschaftsstabilit¨ at ¨ uber 24 Stunden . . . . . . . . . . 84

6.2 NSTAB-Werte f¨ ur Mesh-Router 8 . . . . . . . . . . . . . . . . . . . . . . . . 84 6.3 NSTAB-Werte f¨ ur Mesh-Router 38 . . . . . . . . . . . . . . . . . . . . . . . 84 6.4 Entwicklung der PLQ ¨ uber 24 Stunden . . . . . . . . . . . . . . . . . . . . . 84

6.5 Cluster-Anzahl im Vergleich . . . . . . . . . . . . . . . . . . . . . . . . . . . 84 6.6 Durchschnittliche Broadcast-Stabilit¨ at . . . . . . . . . . . . . . . . . . . . . 85 6.7 Durchschnittliche Nachbaranzahl . . . . . . . . . . . . . . . . . . . . . . . . 85 6.8 Durschnittliche Anzahl versendeter NSI-Nachrichten pro Knoten . . . . . . 85 6.9 Cluster-Anzahl innerhalb des Meßzeitraums im Vergleich . . . . . . . . . . . 88 6.10 Entwicklung des durchschnittlichen Score-Thresholds ¨ uber den Messzeitraum 90

6.11 Distanzadaption: Durschnittlicher NSTAB-Wert pro Mesh-Router . . . . . . 92 6.12 Distanzadaption: Konfigurierte Maximal-Distanz pro Mesh-Router . . . . . 93 6.13 Greedy-Expand: Durchschnittliche k-Distanz . . . . . . . . . . . . . . . . . 95 6.14 Greedy-Expand: Durchschnittlicher NSTAB-Verlauf . . . . . . . . . . . . . 95 6.15 Vergleich von NSTAB-Wert und Nachrichtenaufwand . . . . . . . . . . . . . 95 6.16 Greedy-Expand: Anzahl von Clustern . . . . . . . . . . . . . . . . . . . . . 95

Tabellenverzeichnis   

2.1  Vergleich zwischen Wireless-Mesh-Netzwerken und MANETs  8

5.1  Auto-Flapping: Beispiel geringer Streuung  76

5.2  Auto-Flapping: Beispiel großer Streuung  76

6.1  Konfigurationsparameter der 24 Stunden Messungen  83

6.2  Gesamtdurchschnitte der Messung pro erfasster k-Distanz  83

6.3  Vergleich von Max-Score, Lowest-ID und Elite-Rating bez uglich Kerndaten  88

6.4  Durchschnittliche Wechselh aufigkeiten im Vergleich  91

6.5  Durchschnittliche Kerndaten der distanzadaptiven Algorithmen  92

6.6  Durchschnittliche Kerndaten von Greedy-Expand im Vergleich  96

6.7  Vergleich der Kerndaten von Relayd anhand der Cluster-Algorithmen  98

xi

xii Tabellenverzeichnis

Die drahtlose Kommunikation hat in den letzten Jahren einen stetig steigenden Stellenwert im allt¨ aglichen Gebrauch gewonnen. Neben Laptops werden zunehmend Mobiltelefone und sogenannte Smart Phones mit einem Funkadapter ausgestattet. In einem klassischen Drahtlosnetzwerk erfolgt die Kommunikation der Teilnehmer durch die Verbindung zu einem fest definierten Zugangspunkt, wodurch meist eine statische Sterntopologie realisiert wird. Die Netzwerke sind somit nicht dynamisch ausgerichtet und bei steigender Anzahl der Teilnehmer wenig skalierbar. Abhilfe schaffen hier drahtlose Multi-Hop Netzwerke: Anstelle eines zentralen Koordinators bilden die Teilnehmer selbst das Netzwerk durch das Weiterleiten von Datenpaketen ¨ uber mehrere Spr¨ unge (Hops) hinweg. Prominente

Beispiele dieses Konzepts sind Mobile Ad-Hoc Netzwerke (MANETs, [Sar07]), welche die spontane Vernetzung von Netzwerkteilnehmern ohne grundlegende Infrastruktur erlauben. MANETs sind dynamisch ausgerichtet und unterliegen je nach Mobilit¨ at der Knoten starken Topologieschwankungen, wodurch keine Qualit¨ atgarantien der zur Verf¨ ugung gestellten Netzwerkleistungen gegeben werden k¨ onnen und keine feste Existenzdauer des Netzwerks vorgegeben ist. Wireless-Mesh-Netzwerke (WMNs, [AWW05]) sind ebenfalls Vertreter der Multi-Hop Netzwerke mit dem Fokus auf einer stabilen Grundinfrastruktur und einer langfristigen Ausrichtung. Mittels meist geplanter Standorte f¨ ur festinstallierte Zugangspunkte, welche oftmals an das Internet angebunden sind, wird eine stabile Netzwerktopologie geschaffen, die durch andere Teilnehmer einerseits genutzt und andererseits durch diese erweitert werden kann.

Da Wireless-Mesh-Netzwerke skalierbar sind und ihrer Gr¨ oße keine Beschr¨ ankungen gesetzt werden sollen, sind hierarchische Strukturen von N¨ oten, welche den Verwaltungs-aufwand des Netzwerks reduzieren. Es wurde belegt, dass der Nachrichtenaufwand einer Routenbestimmung oder einer Dienstsuche in einem unstrukturierten WMN quadratisch mit der Gesamtanzahl der Teilnehmer steigt [BR02]. Ein Mittel um die Netzwerktopologie hierarchisch zu strukturieren ist das sogenannte Clustering: Mittels eines lokal oder global ausgef¨ uhrten Algorithmus werden die Knoten des Netzwerks in logische Gruppen unterteilt, welche die Cluster bilden und eine effiziente Verwaltung der gebildeten Strukturen erlauben. Es existieren eine Vielzahl von verschiedenen Cluster-Algorithmen, welche aber meistens auf die eher instabilen und dynamischen Topologien von MANETs ausgerichtet sind und die vorhandene stabile Infrastruktur von WMNs nicht ad¨ aquat nutzen. Gleichzeitig ist die maximale Distanz, gemessen in Netzwerkspr¨ ungen, eines einzelnen Netzwerkteilnehmers von vornherein festgelegt und damit statisch an den zu Grund liegenden Al-gorithmus gebunden. WMNs erlauben aber durch ihren teilweise statischen Aufbau meist

1

2 Kapitel 1. Einf¨ uhrung

hochwertige Verbindungen mit dementsprechend h¨ oheren zul¨ assigen Distanzen. Ziel dieser Arbeit ist es, Verfahren f¨ ur effizientes Clustering in Wireless-Mesh-Netzwerken zu entwickeln, welche einerseits das stabile Grundger¨ ust der WMNs in Betracht ziehen und andererseits eine automatische Anpassung an sich ¨ andernde Netzwerkeigenschaften erlauben.

1.1 Wireless-Mesh-Netzwerke

Wireless-Mesh-Netzwerke verf¨ ugen im Gegensatz zu den dynamischen Mobilen Ad-Hoc Netzwerken ¨ uber eine geplante und meist statische Grundinfrastruktur, welche mittels festinstallierter Router mit verl¨ asslicher Stromversorgung realisiert wird. Diese sind oftmals an andere Netzwerke oder an das Internet angebunden und stellen somit Gateways dar. Durch den Einsatz eines Routingprotokolls wird die Kommunikation der Teilnehmer sichergestellt, wobei in WMNs haupts¨ achlich proaktive Protokolle wie das Optimized Link State Routing Protocol (OLSR, [CJ03]) zum Einsatz kommen.

1.2 Clustering

Clustering [YC05] bezeichnet in Ad-Hoc Netzwerken das Gruppieren der Teilnehmer in logische Einheiten, wodurch eine Hierarchie auf der sonst unstrukturierten Netzwerktopologie geschaffen wird. Hierzu wird f¨ ur jeden Cluster ein Repr¨ asentant gew¨ ahlt, der als lokaler Koordinator der Gruppe fungiert und als Cluster-Head oder Superknoten bezeichnet wird. Typischerweise erfolgt die Kommunikation innerhalb eines selben Clusters direkt, w¨ ahrend Verbindungen zu anderen Clustern mittels designierter Vermittler-Knoten, den sogenannten Gateways realisiert werden. Cluster-Strukturen haben insbesondere im Bereich der Dienstsuche und der Optimierung von Routingprotokollen ihren Hauptanwendungszweck. Die Berechnung einer g¨ ultigen Cluster-Struktur geschieht entweder zentral durch einen globalen Algorithmus, der Einsicht ¨ uber die gesamte Topologie verf¨ ugt, oder durch die lo-

kale, verteilte Anpassung der zugewiesenen Rollen auf jedem teilnehmenden Knoten. Eine Vielzahl von Clustering-Algorithmen wurden entwickelt, wobei diese mehrheitlich auf MA-NETs fokussiert sind. Die vorhandenen Clustering-Verfahren zeichnen sich insbesondere durch eine Beschr¨ ankung der maximalen Hop-Distanz aus und das h¨ aufig auftretende Problem einer kaskadenf¨ ormigen Neustrukturierung der Cluster, welches als Ripple-Effect bezeichnet wird.

1.3 Adaptive Cluster-Infrastruktur

Da die existierenden Cluster-Verfahren die stabilen Strukturen eines Wireless-Mesh-Netzwerks nur unzureichend in Betracht ziehen, sollen im Laufe dieser Diplomarbeit Verfahren entwickelt werden, welche einerseits die Vorteile bereits bestehender L¨ osungen ausnutzen und andererseits auf die Eigenschaften eines WMNs zugeschnitten sind.

1.3.1 Distanzadaptive Algorithmen

Um ein H¨ ochstmaß an Stabilit¨ at zu garantieren sollen Algorithmen entwickelt werden, welche die maximale Distanz jeden Knotens an die momentane Netzwerksituation anpassen. Hierdurch soll zum Einen eine stabile Grundtopologie des Netzwerks erzeugt werden und zum Anderen die einheitliche Festlegung dieses Parameters redundant gemacht werden.

1.4. Anwendungsbeispiel Dienstsuche 3

Die Verfahren sollen so konzipiert werden, dass sie einen ersten stabilisierenden Schritt vor der eigentlichen Bildung der Cluster darstellen, wobei die Stabilit¨ at mittels einer noch zu entwickelnden Metrik gemessen werden soll. Die Verfahren w¨ urden Neuentwicklungen darstellen, ohne vergleichbare, existierende Ans¨ atze.

1.3.2 Stabilit¨ atsorientiert und adaptiv

Da Wireless-Mesh-Netzwerke haupts¨ achlich mit dem Ziel einer langfristigen und stabilen Infrastruktur aufgebaut werden, sollen die entwickelten Cluster-Verfahren dieser Eigenschaft h¨ ochste Priorit¨ at zurechnen, wobei die zuvor erw¨ ahnten distanzadaptiven Verfahren die Grundlage hierf¨ ur bilden. Kaskadenf¨ ormige Neustrukturierungen sind weitgehend zu vermeiden, genau wie h¨ aufige Superknoten-Wechsel. Gleichzeitig ist ein H¨ ochstmaß an Flexibilit¨ at und die Anpassung an unterschiedliche Netzwerksituation sowie Tageszeiten erw¨ unschenswert.

1.3.3 Modulare Architektur

Basierend auf dem Clustering Unix-Dienst Fleximsd [Kre09] werden die Algorithmen implementiert und evaluiert. Gleichzeitig soll der Dienst angepasst werden, um ein H¨ ochstmaß an Modularit¨ at und Konfigurierbarkeit zu bieten, wodurch eine ideale Anpassung an unterschiedliche Netzwerktopologien m¨ oglich sein soll. Des Weiteren soll Fleximsd als grundlegender Dienst f¨ ur weitere Anwendungen fungieren, welche auf Cluster-Strukturen basieren. Hierdurch soll eine modulare und erweiterbare Architektur geschaffen werden.

1.4 Anwendungsbeispiel Dienstsuche

Um den Nutzen der Cluster-Verfahren an einer praxisnahen Anwendung zu evaluieren, werden die Algorithmen mittels einer Service-Discovery-Architektur getestet. Service Discovery oder Dienstsuche bezeichnet das Suchen und Auffinden von bereitgestellten Diensten wie Druckern oder FTP-Diensten im Netzwerk. Hierzu soll die Dienstsuche-Applikation Relayd mittels einer Kopplung an Fleximsd die vorhandenen Cluster-Strukturen ausnutzen.

1.5 Gliederung

Der restliche Teil der Arbeit ist folgendermaßen gegliedert: In Kapitel 2 werden zun¨ achst Wireless-Mesh-Netzwerke n¨ aher betrachtet. Neben einer Einf¨ uhrung des Begriffs und der unterschiedlichen Infrastrukturen wird insbesondere die Abgrenzung zu MANETs erl¨ autert. Des Weiteren werden in diesem Kapitel drei Routingprotokolle vorgestellt, welche mit drei verschiedenen Ans¨ atze die Berechnung der Netzwerkpfade realisieren. Das Kapitel wird mit der Vorstellung einiger, typischer Anwendungsgebiete abgeschlossen. Kapitel 3 konzentriert sich auf Clustering. Nach einer ausf¨ uhrlichen Einf¨ uhrung in das Thema und der Verdeutlichung der typischen Rollenverteilung in Cluster-Strukturen, werden die einzelnen Varianten der Dominating Sets vorgestellt, welche eine mathematisches Beschreibung von Cluster-Strukturen erlauben. Um einen Einblick in den bisherigen For-schungsstand von Cluster-Algorithmen zu gewinnen, werden sechs Verfahren vorgestellt, welche mit unterschiedlichen Ausrichtungen und Methoden Cluster-Strukturen verteilt er- mitteln. Des Weiteren werden typische Anwendungsfelder von Clusterings betrachtet und

4 Kapitel 1. Einf¨ uhrung

zum Schluss des Kapitels eine Bewertung der vorgestellten Verfahren in Hinblick auf die Erfordernisse der zu entwickelnden, angepassten Algorithmen vorgestellt. In der theoretischen Ausarbeitung in Kapitel 4 werden die Grundlagen der Diplomarbeit sowie die entwickelten Verfahren vorgestellt. Einf¨ uhrend werden grundlegende Metriken erl¨ autert, welche bestimmte Qualit¨ atskriterien der Netzwerktopologie quantitativ erfassen und als Grundlage f¨ ur die anschließend vorgestellten Cluster-Algorithmen dienen. Diese stellen Weiterentwicklungen vorhandener L¨ osung dar, mit dem Fokus auf eine stabilit¨ atsorientierte und damit an WMNs angepasste Erzeugung von Clustern. Das Kapitel wird mit der Vorstellung drei im Laufe der Diplomarbeit entwickelter distanzadaptiver Algorithmen mit unterschiedlichen, algorithmischen Vors¨ atzen abgeschlossen. Kapitel 5 bildet den praktischen Teil der Diplomarbeit und geht n¨ aher auf die Implementierung der in der theoretischen Ausarbeitung vorgestellten Verfahren ein. Hier wird zun¨ achst die modulare Architektur des Clustering-Diensts Fleximsd vorgestellt und die genaue Realisierung der Nachrichtentypen und Algorithmen erkl¨ art. Anschließend wird die Dienstsuche-Applikation Relayd pr¨ asentiert und die Verbindung zwischen diesem und Fleximsd hervorgehoben. Das Kapitel wird mit zwei Abschnitten zur Bestimmung von Gateway-Knoten und Verfahren zur Erh¨ ohung der Cluster-Stabilit¨ at abgeschlossen. In Kapitel 6 werden einige Messungen pr¨ astentiert, welche auf dem UMIC-Testbed [Zim09] durchgef¨ uhrt wurden. Die Testreihen konzentrieren sich hierbei auf verschiedene Aspekte der entwickelten Verfahren und evaluieren die Praxistauglichkeit der Algorithmen. Die Arbeit wird mit Kapitel 7 abgeschlossen, welches als Zusammenfassung der Arbeit dient und einen Ausblick auf zuk¨ unftige Entwicklungen gibt.

In diesem Kapitel werden die Eigenschaften und die Struktur von Wireless-Mesh-Netzwerken (WMN ) [AWW05] genauer betrachtet. In Abschnitt 2.1 werden grundlegende Begriffe eingef¨ uhrt und die unterschiedlichen Architekturen der WMNs erkl¨ art, w¨ ahrend in Abschnitt 2.2 die Unterschiede zu anderen Ad-Hoc Netzwerken behandelt werden. Abschnitt 2.3 stellt beispielhaft drei, in WMNs verwendete Routingverfahren vor. Abschließend werden in Abschnitt 2.4 einige Einsatzm¨ oglichkeiten dieses Netzwerktyps aufgezeigt.

2.1 Architektur

Wireless-Mesh-Netzwerke sind selbstorganisierende, drahtlose Netzwerke bestehend aus Routern und Clients. Im Gegensatz zu einem konventionellen Drahtlosnetzwerk existiert kein zentraler Zugsangspunkt (Access Point), sondern die Router bilden durch Verwendung eines einheitlichen Routingprotokolls im gesamten Netzwerk ein vermaschtes Netz, welches die Kommunikation zwischen allen Teilnehmern des gesamten Mesh-Netzwerks erlaubt. WMNs sind Multi-Hop f¨ ahig, erlauben also den teilnehmenden Clients mit nicht direkt erreichbaren Knoten ¨ uber mehrere Router hinweg zu kommunizieren. Außerdem verbessern teilnehmende Knoten die Verl¨ asslichkeit und Konnektivit¨ at des gesamten Netzwerks, da sie sowohl Pakete weiterleiten k¨ onnen und die Ausdehnung des Netzwerks vergr¨ oßern, als auch die Toleranz gegen¨ uber Ausf¨ allen einzelner Knoten erh¨ ohen. Die Teilnehmer in einem WMN k¨ onnen grob in drei Kategorien unterteilt werden [Zim09]:

Backbone-Router Sie bilden den stabilen Teil des Netzwerks (engl. Backbone) und unterliegen einer sehr geringen Mobilit¨ at. Neben einer verl¨ asslichen Stromversorgung und einer festen Installation sind sie oftmals mit vorhandener Kabelinfrastruktur z.B. an das Internet angebunden, in welchem Fall sie als Gateway-Router bezeichnet werden. Mit Hilfe der Multi-Hop-F¨ ahigkeit der WMNs k¨ onnen Backbone-Router, die nicht an andere Netzwerke angebunden sind, Pakete anderer Teilnehmer an die Gateway-Knoten weiterleiten.

Routende Clients Diese geh¨ oren zu der Gruppe der Clients, sind also i.d.R. beweglich, ¨ ubernehmen jedoch Routingaufgaben, die vornehmlich den Backbone-Routern zugedacht sind. Hierdurch erweitern die routenden Clients das gesamte Netzwerk und ¨ ahneln wegen ihres spontanen und dynamischen Charakters den in Abschnitt 2.2 beschriebenen Mobile Ad Hoc Networks (MANETs) [MCA02]. Aufgrund der h¨ oheren Mobilit¨ at und der evtl. nicht vorhandenen, dauerhaften Stromversorgung ist die

5

Nicht-routende Clients Sie sind lediglich Benutzer des WMN und ¨

Zwar sind einige Knoten des Netzwerks in vielen F¨ allen direkt per Kabel an das Internet angeschlossen, doch wird dies nicht als Teil des Netzwerks angesehen und ein WMN als stets kabellos bezeichnet. W¨ ahrend die Kategorie der Backbone-Router und Gateways klar durch ihre Aufgaben abgegrenzt ist, ist die Einteilung in routende und nicht-routende Clients fließend. So kann jeder teilnehmende Knoten selbst entscheiden, inwiefern er an der Organisation des Netzwerks beteiligt sein will und ob er Routingaufgaben ¨ ubernehmen m¨ ochte.

Der Aufbau eines Wireless-Mesh-Netzwerks erfordert meistens einen gewissen Planungs- und Wartungsaufwand, da die Backbone-Router je nach Einsatzszenario m¨ oglichst optimal installiert werden m¨ ussen. Dennoch besitzen WMNs durch die Teilnahme routender Clients eine dynamische Ausrichtung. Je nach Vorkommen der vorgestellten Knotentypen, werden WMNs in Infrastruktur-, Client- oder Hybrid-Wireless-Mesh-Netzwerke eingeteilt, welche im Folgenden genauer betrachtet werden.

2.1.1 Infrastruktur-Wireless-Mesh-Netzwerk

Ein Infrastruktur-WMN besteht ausschließlich aus Backbone-Routern und nicht-routenden Clients, wobei die Router ein selbst-organisierendes, Multi-Hop f¨ ahiges Backbone erzeugen, mit welchem sich gew¨ ohnliche Teilnehmer verbinden k¨ onnen. Einige der Router k¨ onnen an das Internet angeschlossen werden und ¨ ubernehmen somit die Rolle eines Internet-Gateways. Die Router fungieren hierbei als Zugangspunkte f¨ ur die Clients, wobei diese keine Aufgaben ¨ ubernehmen und nicht zur Organisation des Netzwerks beitragen. Ein Beispiel eines Infrastruktur WMN ist in Abbildung 2.1 aufgef¨ uhrt. Dieser WMN-Typ erm¨ oglicht eine vergleichsweise maximale Stabilit¨ at, da nur die meist fest installierten Backbone-Router an der Organisation des Netzwerks beteiligt sind und die Erreichbarkeit des Netzwerks nicht durch die verbundenen Clients beeinflusst wird.

2.1.2 Client-Wireless-Mesh-Netzwerk

Client-WMNs ¨ ahneln in ihrer Funktion den in Abschnitt 2.2 beschriebenen Ad-Hoc Netzwerken: Das Netzwerk besteht nur aus routenden Clients, wobei keine feste Topologie und Zugangspunkte gegeben sind (s. Abbildung 2.2). Dadurch steigen die Rechenanforderungen an die Teilnehmer, da sie die zus¨ atzlichen, organisatorischen Aufgaben, insbesondere das Routing, selbst erledigen m¨ ussen.

Client-WMNs sind meistens weitaus weniger stabil als Infrastruktur-Wireless-Mesh-Netzwerke, erlauben aber eine spontane, planungsfreie Einrichtung ohne zus¨ atzliche In- stallation von Mesh-Routern.

2.1. Architektur 7

Abbildung 2.1: Infrastruktur-WMN Abbildung 2.2: Client-WMN

2.1.3 Hybrides Wireless-Mesh-Netzwerk

Dieser Netzwerktyp stellt eine Kombination aus der in Abschnitt 2.1.1 und 2.1.2 vorgestellten WMN-Formen dar. Einerseits wird durch fest installierte Mesh-Router ein stabiles Backbone bereitgestellt, mit welchem sich nicht-routende Clients verbinden k¨ onnen; andererseits erh¨ ohen teilnehmende, routende Clients die Reichweite des gesamten Netzwerks (s. Abbildung 2.3). Da diese Architektur die Variante mit der h¨ ochsten Flexibilit¨ at darstellt, wird im Folgenden eine hybride Struktur vorausgesetzt, wenn von einem Wireless-Mesh-Netzwerk gesprochen wird.

8 Kapitel 2. Wireless-Mesh-Netzwerke

2.2 Unterschiede zu MANETs

Wireless-Mesh-Netzwerke geh¨ oren zu der Kategorie der drahtlosen Multi-Hop Netzwerke; diese zeichnen sich haupts¨ achlich durch das Weiterleiten von Paketen mit Hilfe von Funkverbindungen ¨ uber mehrere Knoten hinweg aus. Weitere Vertreter dieser Klasse sind Mobile Ad Hoc Networks (MANETs) und Sensornetzwerke [Sar07]. MANETs sind infrastrukturlos und oftmals spontaner Natur, wobei sie eine dynamische Topologie besitzen und die r¨ aumliche Ausdehnung meistens gering ist. Sie sind besonders auf Ger¨ ate geringer Leistung ausgelegt und wegen der auftretenden, unterschiedlichen Mobilit¨ at der Teilnehmer, muss jeder Knoten Routingaufgaben ¨ ubernehmen, wobei die Konnektivit¨ at zu ande-

ren Clients niemals gew¨ ahrleistet ist. Sensornetzwerke bestehen aus kleinen Sensorger¨ aten, die ¨ uber Multi-Hop Verbindungen aufgenommene Daten (z.B. Temperaturwerte) drahtlos an einen zentralen Monitorknoten ¨ ubermitteln; auch hier ist keine feste Infrastruktur vorgegeben.

Der Hauptunterschied zwischen WMNs und MANETs bzw. anderen Ad-Hoc Netzwerken ist, dass WMNs eher statisch ausgerichtet sind und ¨ uber eine sich nur langsam ¨ andernde Topologie verf¨ ugen, da die Backbone-Router meistens fest installiert sind [ZLH06]. MANETs unterliegen schnellen Topologie¨ anderungen und wegen ihres oftmals kurzlebigen Auftretens erlauben sie keine qualitativ hochwertigen Verbindungen, wie es in Wireless-Mesh-Netzwerken m¨ oglich ist. Gleichzeitig bedeutet dies, dass der Planungs-und Wartungsaufwand f¨ ur WMNs weitaus h¨ oher ist, da zun¨ achst eine Grundinfrastruktur geschaffen werden muss.

Dennoch erlauben WMNs die dynamische Erweiterung des Netzwerks um routende Knoten und in [AWW05] werden die in Abschnitt 2.1.2 beschriebenen Client-WMNs als eine Form von MANETs bezeichnet, wonach ein Wireless-Mesh-Netzwerk als eine allgemeine Variante dieser Netzwerkform betrachtet werden kann. In Tabelle 2.1 werden die wichtigsten Unterschiede zwischen WMNs und MANETs zusammengefasst.

2.3 Routing

Ohne aktiviertes Routing kann ein WMN-Teilnehmer nur mit den Knoten des Netzwerks kommunizieren, die sich in seiner Funkreichweite befinden. Aus diesem Grund ist der Einsatz eines Routingprotokolls unerl¨ asslich, um Routen zu allen Knoten im Netzwerk aufzubauen. Jene werden entweder als proaktiv, reaktiv oder hybrid klassifiziert [HXG02]. Die Mehrzahl, der f¨ ur Ad-Hoc Netzwerke entwickelten Routingalgorithmen sind h¨ aufig uneingeschr¨ ankt in Wireless-Mesh-Netzwerken anwendbar, wobei im Folgenden f¨ ur jeden Ansatz beispielhaft ein Routingprotokoll vorgestellt wird. Diese arbeiten auf der Trans-portschicht (Schicht 3) des ISO/OSI Schichtenmodells [Zim80]. Anschließend werden die Ideen des IEEE 802.11s Standards pr¨ asentiert, welches die Routingverfahren auf die MAC

2.3. Routing 9

Ebene (ISO/OSI Schicht 2) verlagert.

2.3.1 Klassifikation von Routingverfahren

Eine bekannte Methode Routingprotokolle in Ad-Hoc Netzwerken zu unterscheiden, ist die Untersuchung von der Verteilung der Nachrichten und von der Wartung von Routen innerhalb des Netzwerks. Dies f¨ uhrt zu der Unterteilung in proaktive, reaktive und hybride Routingverfahren.

Ein proaktives Routingprotokoll versucht zu jedem Zeitpunkt Routen zu jedem anderen Knoten im Netzwerk bereitstellen zu k¨ onnen. Diese Verfahren werden auch als Table-Driven bezeichnet und berechnen neue Routen jeweils durch das periodische Versenden von Statusnachrichten. Letzteres ist f¨ ur den Erhalt aktueller Routen erforderlich, da WMNs, oder allgemein Ad-Hoc Netzwerke, keine zuverl¨ assigen Verbindungen garantieren und Funkverbindungen abbrechen oder Teilnehmer das Netzwerk wieder verlassen k¨ onnen. Andererseits k¨ onnen durch Topologie¨ anderungen neue oder verbesserte Routen entstehen.

Ein Nachteil dieses Verfahrens ist, dass durch das kontinuierliche Versenden von Statuspaketen ein erh¨ ohter Datenverkehr im Netzwerk entsteht. Je nach Dynamik des Netzwerks kann aber das Intervall der Statusnachrichten angepasst werden; so w¨ are es von Vorteil in einem stabilen Netzwerk ein h¨ oheres Intervall zu w¨ ahlen, da die Wahrscheinlichkeit einer Topologie¨ anderung gering ist. Dagegen sollte in dynamischen Netzwerken das Aktualisierungsintervall kurz gehalten werden, um zu verhindern, dass berechnete Routen ung¨ ultig werden.

Vorteil eines proaktiven Routingprotokoll ist, dass zu jedem Zeitpunkt verz¨ ogerungsfrei eine Route zu jedem anderen Client des Netzwerks zur Verf¨ ugung steht, sofern diese Route auch physisch existiert. Diese Klasse der Routingverfahren ist insbesondere f¨ ur Netzwerke geeignet, die eine geringe Latenzzeit fordern und deren Priorit¨ at auf der schnellen Verf¨ ugbarkeit aller Routen liegt. Das in Abschnitt 2.3.2 vorgestellte Optimized Link State Routing (OLSR) Protokoll [CJ03] z¨ ahlt zu den proaktiven Ans¨ atzen. Reaktive Routingprotokolle werden auch als On-Demand Verfahren bezeichnet, da die Routen nicht periodisch berechnet werden, sondern nur wenn eine Verbindung hergestellt wird. Sobald ein Knoten sich mit einem anderen Teilnehmer verbinden m¨ ochte, wird versucht eine Route zu diesem zu berechnen. Als Resultat wird entweder die gefundene Route zur¨ uckgegeben oder ein Fehler erzeugt, falls der Zielknoten nicht erreicht werden konnte. Nachteil der reaktiven Routingalgorithmen ist die Verz¨ ogerungszeit, die auftritt sobald eine Verbindung hergestellt wird. Da zun¨ achst die gew¨ unschte Route berechnet werden muss, kann der Empf¨ angerknoten nicht sofort erreicht werden. Vorteil reaktiver Verfahren ist, dass Datenverkehr nur dann entsteht, wenn auch eine Verbindung zu einem anderen Client hergestellt wird. Dies f¨ uhrt zu einer besseren Skalierbarkeit und einer effektiveren Routenberechnung in dynamischen und mobilen Netzwerken wie den MANETs. Da sich in solchen Netzwerken die Topologie oft und schnell ¨ andert, k¨ onnen reaktive Protokolle bei jedem Verbindungsversuch die zu diesem Zeitpunkt jeweils optimale Route berechnen. Proaktive Verfahren dagegen laufen in dynamischen Netzwerken Gefahr veraltete Routen gespeichert zu haben, falls das Aktualisierungsintervall zu groß gew¨ ahlt wurde. Abschnitt 2.3.3 stellt Dynamic Source Routing (DSR) [JM96] als Beispiel eines reaktiven Protokolls vor.

Hybride Protokolle wie das Zone Routing Protocol (ZRP, Abschnitt 2.3.4) [Haa97] versuchen proaktives und reaktives Routing miteinander zu verbinden, und somit Vorteile

10 Kapitel 2. Wireless-Mesh-Netzwerke

beider Verfahren miteinandern zu kombinieren und die negativen Einfl¨ usse zu limitieren. Insbesondere versuchen sie sich Hierarchien im Netzwerk effizient zu Nutze zu machen.

2.3.2 Optimized Link State Routing Protocol

Als proaktives Protokoll versucht OLSR jederzeit Routen zu allen Knoten des Netzwerks zu berechnen. Dabei werden alle Nachrichten mittels Broadcast versendet, d.h. es werden durch eine Nachricht alle Knoten informiert, die sich in der direkten Nachbarschaft des Senders befinden und physisch erreichbar sind. Um den durch Broadcast und das Weiterleiten der Pakete resultierenden, erh¨ ohten Datenverkehr zu reduzieren, verwendet OLSR das Konzept der Multipoint Relays (MPRs). Jeder Knoten w¨ ahlt aus seinen direkt erreichbaren, symmetrischen Nachbarn ¹ eine Menge an MPRs aus, welche ausschließlich Nachrichten des Knotens weiterleiten d¨ urfen (s. Abbildung 2.4). Das Protokoll besteht aus vier verschiedenen Nachrichtentypen:

HELLO-Nachrichten enthalten alle, dem sendenden Knoten bekannten Nachbarn und werden periodisch mit den direkten Nachbarn ausgetauscht, also jenen, die mit einem Sprung (Hop) erreichbar sind. Dadurch sind dem Knoten alle Nachbarn bekannt, die maximal zwei Hops entfernt sind. Zus¨ atzlich sind Informationen im Paket enthalten, ob die Verbindungen untereinander symmetrisch sind, wodurch sich die Menge der MPRs berechnen l¨ asst.

Topology Control (TC) Nachrichten werden nur von den gew¨ ahlten MPRs versendet und mit der maximalen Hopdistanz von 255 im ganzen Netzwerk verteilt. Diese enthalten mindestens die Verbindungen der Knoten zu ihren jeweils gew¨ ahlten MPRs. Jeder Knoten

empf¨ angt die TC Nachrichten und erh¨ alt somit eine ¨ Ubersicht ¨ uber eine angen¨ aherte

Topologie des gesamten Netzwerks, wodurch sich m¨ oglichst optimale Routen zu jedem Knoten im Netzwerk berechnen lassen. OLSR bezeichnet solche Routen als optimal, welche die k¨ urzeste Hopanzahl zwischen den Knoten aufweisen.

Um mehrere Netzwerkadapter zu unterst¨ utzen, spezifiziert OLSR die Multiple Interface Description (MID) Nachrichten. Neben der Adresse des designierten Hauptadapters werden alle bekannten Adapteradressen mit Hilfe des MPR-Mechanismus ¨ uber das gesamte Netzwerk verteilt. So k¨ onnen Routen mittels der Zuordnung der Hauptadresse auch zu den Nebenadaptern berechnet werden.

Host and Network Association (HNA) Nachrichten enthalten Netzwerkmaske undadresse anderer, angebundener Netzwerke. Sie werden von OLSR im Netzwerk verteilt und erlauben es anderen Teilnehmern Routen in diese Netzwerke zu berechnen, wobei die Absender dieser Nachrichten dann die Rolle von Gateway-Knoten ¨ ubernehmen.

OLSR wurde im Rahmen des UniK OLSR Daemon [TLGP09] implementiert, welcher erfolgreich den Betrieb eines ¨ offentlichen WMNs u.a. in Berlin gew¨ ahrleistet ² . Der Daemon ist modular durch Plugins erweiterbar und erlaubt die Implementierung eigener Nachrichten.

2.3.3 Dynamic Source Routing

Dynamic Source Routing (DSR) ist ein reaktives Protokoll, dass auf dem source routing Algorithmus basiert. Hierbei enth¨ alt jedes gesendete Paket alle n¨ otigen Routinginformationen, um das Ziel zu erreichen. Gleichzeitig speichert jeder Knoten Informationen ¨ uber

¹ Zwischen symmetrischen Nachbarn besteht eine bidirektionale Verbindung, d.h. es k¨ onnen beide Knoten sowohl empfangen als auch senden.

² Das Netzwerk wird von der allgemeinn¨ utzigen Organisation Freifunk Initiative [Fre09] verwaltet.

2.3. Routing 11

(a) Broadcast an alle Knoten des Netz-werks

Abbildung 2.4: OLSR MPR Mechanismus

“gelernte” Routen zwischen, um das Verfahren insgesamt zu beschleunigen. Das Protokoll besteht aus zwei Phasen, der Routen Suche und der Routen Reparatur.

Falls ein Teilnehmer eine Verbindung zu einem anderen Knoten herstellen m¨ ochte, ¨ uberpr¨ uft dieser zun¨ achst, ob sich eine Route zu dem gew¨ unschten Ziel im Zwischenspeicher befindet. Falls ja, werden die Routinginformationen dem Paket hinzugef¨ ugt und versendet. Falls keine Route bekannt ist, wird ein route request (Routenanfrage, RREQ) via Broadcast versendet, wobei jedes Paket eindeutig durch Sender, Empf¨ anger und einer Identifikationsnummer zugeordnet werden kann. Jeder Empf¨ anger ¨ uberpr¨ uft zun¨ achst, ob

eine Route zum Zielknoten bekannt ist und erstellt eine route reply (Antwort, RREP) Paket, falls dies zutrifft. Diese enth¨ alt die Adressen aller Zwischennoten, wodurch eine Route gekennzeichnet wird. Wenn keine Route im Zwischenspeicher gefunden wurde, wird die Adresse des eigenen Knotens der Routenanfrage angeh¨ angt und an die direkten Nachbarn weitergeleitet. Erreicht die Routenanfrage den Zielknoten, wird ein Antwort Paket mit umgekehrter Reihenfolge der passierten Knoten zur¨ uckgesendet. Zur Limitierung des Datenverkehrs werden nur Routenanfragen bearbeitet, die bisher noch nicht gesehen wurden und die nicht die eigene Adresse enthalten. Im Fall, dass der Zielknoten nicht erreicht werden kann, wird ein ROUTE ERROR Paket an den Sender zur¨ uckgeschickt und die Routen Reparatur Phase wird angestoßen, wobei jeder passierte Zwischenknoten den nicht erreichbaren Knoten aus seinem Zwischenspeicher l¨ oscht.

Im Vergleich zu dem reaktiven Ad Hoc On-demand Distance Vector Routing (AODV ) [PBR99], das einen ¨ ahnlichen Ansatz zur Routenfindung verwendet, ben¨ otigt DSR keine Routingtabellen, da alle Routinginformationen im Datenpaket selbst gespeichert sind. Dies kann unter Umst¨ anden zu einem großen Overhead f¨ uhren, der sich proportional zur Pfadl¨ ange verh¨ alt und insbesondere negativ bei Verwendung des IPv6 [DH98] Protokolls auff¨ allt. DSR eignet sich insbesondere f¨ ur Netzwerke geringer Mobilit¨ at und geringer Anzahl an Knoten mit beschr¨ ankter Rechenkapazit¨ at [DPR00].

Eine um Qualit¨ atsmetriken erweiterte Implementierung von DSR ist im MicroSoft Research Mesh Connectivity Layer (MCL) [Mic09] realisiert, welches ein transparentes Routingprotokoll f¨ ur das Windows XP Betriebssystem bereitstellt.

Abbildung 2.5: Routingzonen der Gr¨ oße 1 aus Sicht des Knotens “A”: B,C,D sind Peripherieknoten, E liegt in der Routingzone von C.

2.3.4 Zone Routing Protocol

Das hybride Zone Routing Protocol (ZRP) ist f¨ ur mobile Ad-Hoc Netzwerke konzipiert worden und versucht den Overhead proaktiver Routingprotokolle zu minimieren bei gleichzeitiger Verringerung der Latenzzeiten eines reaktiven Protokolls. Im ZRP wird das Netzwerk mittels einer festgelegten Distanz d zwischen den mobilen Knoten in Routingzonen unterteilt. Die Routingzone eines Knotens N besteht aus allen Knoten, deren Distanz zu N gemessen in Hops kleiner gleich d betr¨ agt. Die Knoten, die genau d Hops von N entfernt sind, werden als Peripherieknoten bezeichnet (s. Abbildung 2.5). Anhand dieser Unterteilung werden verschiedene Routingans¨ atze implementiert: Innerhalb einer Routingzone wird ein proaktives Intra-zone Routing Protokoll (IARP ) eingesetzt, w¨ ahrend f¨ ur Datenverkehr außerhalb der Routingzone, also zwischen den Routingzonen, ein reaktives Inter-zone Routing Protokoll (IERP ) verwendet wird. Durch das proaktive IARP sind alle Knoten einer selben Routingzone sofort erreichbar, wobei hier nahezu jedes beliebige proaktive Protokoll verwendet werden kann. Routen zu außerhalb der eigenen Routingzone liegenden Knoten werden reaktiv mit Hilfe des IERP berechnet. Die Funktionsweise gleicht dem in Abschnitt 2.3.3 eingef¨ uhrten DSR Protokoll: zun¨ achst werden die Peripherieknoten angefragt, welche entweder die gew¨ unschte, zwischengespeicherte Route zur¨ uckliefern oder der Routenanfrage ihre eigene Adresse anh¨ angen und diese wiederum an ihre eigenen Peripherieknoten weiterleiten.

Nachteil des Verfahrens ist die Einteilung in Routingzonen, was insbesondere in sehr mobilen und dynamischen Netzwerken zu Problemen f¨ uhren kann. Vorteil ist, dass Routen innerhalb der eigenen Routingzone sofort verf¨ ugbar sind und, dass das Berechnen neuer Routen bei Netzwerk¨ anderungen nur zwischen zwei Routingzonen geschieht, was die Effizienz des Routingverfahrens erh¨ oht. Eine Implementierung kann in [Hel05] gefunden werden.

2.3.5 IEEE 802.11s

Die noch nicht angenommene Teilspezifikation IEEE 802.11s [HMZ ⁺ 07] hat zum Ziel einen herstellerunabh¨ angigen Standard zur Einrichtung von WMNs zu etablieren. Die bisher vorgestellten Routingverfahren arbeiten auf der Transportschicht (Schicht 3) des ISO OSI Schichtenmodells, w¨ ahrend IEEE 802.11s eine Verlagerung der Routingfunktionalit¨ at auf

2.4. Einsatzm¨ oglichkeiten 13

die 2. Schicht, der MAC Schicht, vorsieht.

Im Standard vorgesehen ist die Verwendung eines Hybrid Wireless Mesh Protocol (HWMP), das ein, an AODV (s. Abschnitt 2.3.3) angelehntes, reaktives Routingprotokoll mit einem proaktiven, Baum-basierten Protokoll kombiniert. Das reaktive Protokoll wird eingesetzt, um den mobilen Teil des Netzwerks verwalten zu k¨ onnen, w¨ ahrend das proaktive Protokoll verwendet wird, falls das Netzwerk ¨ uber designierte, fest installierte Knoten (Mesh Portals) verf¨ ugt.

Zwar k¨ onnen durch die Verlagerung der Routingfunktionen auf die MAC Ebene ein weniger berechnungsintensives Verfahren und ein einfacher und transparenter Aufbau eines WMNs erwartet werden, doch muss der MAC Header modifiziert und erweitert werden, was einerseits die Paketgr¨ oße negativ beeinflusst und andererseits spezielle Hardware er-fordert. Alternativ muss das Betriebssystem angepasst werden. Das open80211s [Ope09] Projekt strebt eine quelloffene Implementation des Standards f¨ ur das Linux Betriebssystem an.

2.4 Einsatzm¨ oglichkeiten

Im Gegensatz zu herk¨ ommlichen Kabelnetzwerken, k¨ onnen WMNs relativ schnell installiert werden, streben aber einen vergleichbaren Benutzungskomfort an. Da die Einsatzgebiete dieser Netzwerke sehr weit gefasst sind, wird im Folgenden beispielhaft nur auf einige Wenige eingegangen [AWW05]:

Breitband Heimnetzwerke Herk¨ ommliche Drahtlosnetzwerke k¨ onnen oftmals nicht alle Bereiche eines Heimnetzwerks abdecken, weswegen hier die Installation von mehreren Mesh-Routern sinnvoll ist. Durch die Benutzung eines einheitlichen Routingprotokolls k¨ onnen die drahtlosen Router kosteng¨ unstig zu einem Mesh Netzwerk zusammengeschlossen werden, wobei die Netzwerklast insgesamt verringert werden kann, da der gesamte Datenverkehr nicht ¨ uber einen zentralen Router geleitet werden muss, sondern auf alle Router verteilt wird.

Notfallsituationen In Katastrophenszenarien (Br¨ ande, Unf¨ alle usw.) ist es oft n¨ otig, schnell eine solide Kommunikationsplattform aufzubauen. Da eine Netzwerkinfrastruktur im Vorhinein nicht planbar ist, sind gerade WMNs durch ihre Dynamik z¨ ugig installierbar. So k¨ onnten, auf den Einsatzfahrzeugen der Helfer installierte Router, sofort bei Eintreffen eine grundlegende Kommunikation sicherstellen.

Firmennetzwerke Obwohl in vielen Firmen drahtlose Zugangspunkte existieren, sind diese nicht miteinander vernetzt und der Ausfall eines Routers f¨ uhrt wom¨ oglich zu einem Komplettausfall des betroffenen B¨ uros. Durch die Redundanz eines WMNs kann hier die Toleranz gegen¨ uber Ausf¨ allen verbessert werden. Auch profitiert das gesamte Netzwerk von der Installation einer zus¨ atzlichen, externen Leitung, da die Gesamtkapazit¨ at durch die Multihop-F¨ ahigkeit eines WMNs erh¨ oht wird und nicht nur jene eines lokalen Knotenpunktes. Dies spart insbesondere Kosten und erleichtert den Ausbau der Netzwerkinfrastruktur bei Vergr¨ oßerung der Firma.

14 Kapitel 2. Wireless-Mesh-Netzwerke