Lade Inhalt...

Adaptives Clustering in Wireless-Mesh-Netzwerken

Diplomarbeit 2010 119 Seiten

Informatik - Angewandte Informatik

Leseprobe

Inhaltsverzeichnis

1 Einführung
1.1 Wireless-Mesh-Netzwerke
1.2 Clustering
1.3 Adaptive Cluster-Infrastruktur
1.3.1 Distanzadaptive Algorithmen
1.3.2 Stabilitätsorientiert und adaptiv
1.3.3 Modulare Architektur
1.4 Anwendungsbeispiel Dienstsuche
1.5 Gliederung

2 Wireless-Mesh-Netzwerke
2.1 Architektur
2.1.1 Infrastruktur-Wireless-Mesh-Netzwerk
2.1.2 Client-Wireless-Mesh-Netzwerk
2.1.3 Hybrides Wireless-Mesh-Netzwerk
2.2 Unterschiede zu MANETs
2.3 Routing
2.3.1 Klassifikation von Routingverfahren
2.3.2 Optimized Link State Routing Protocol
2.3.3 Dynamic Source Routing
2.3.4 Zone Routing Protocol
2.3.5 IEEE 802.11s
2.4 Einsatzmäglichkeiten

3 Clustering
3.1 Einfährung
3.2 Grundlagen
3.2.1 Dominating Sets
3.3 Anwendung
3.3.1 Routing
3.3.2 Service Discovery
3.3.3 Weitere Anwendungsfelder
3.4 Klassifikation von Clustering-Verfahren
3.5 Clustering-Verfahren fär Ad-Hoc-Netzwerke
3.5.1 Lowest-ID
3.5.2 Highest-Connectivity
3.5.3 CDS-Algorithmus von Wu und Li
3.5.4 Distributed Dynamic Clustering Algorithm
3.5.5 Adaptive Multi-Hop Clustering
3.5.6 Adaptives ZRP
3.5.7 Andere Ansatze
3.6 Bewertung

4 Theoretische Ausarbeitung
4.1 Motivation
4.2 Informationsaustausch
4.3 Metriken
4.3.1 Path Link Quality
4.3.2 Nachbarschaftsstabilität
4.3.3 Broadcaststabilität
4.3.4 Connection-Rating
4.3.5 Expected Transmission Count
4.3.6 Round Trip Time
4.3.7 Wahlstabilität
4.4 Clustering-Algorithmen
4.4.1 Grundlagen
4.4.2 Lowest-ID
4.4.3 Max-Score
4.4.4 Elite-Rating
4.5 Distanzadaptive Algorithmen
4.5.1 Grundlagen
4.5.2 Nachbarschaftsstabilitäaten annäahern
4.5.3 Egoistischer Algorithmus
4.5.4 Flood-Majority
4.5.5 Greedy-Expand Algorithmus

5 Praktische Ausarbeitung
5.1 Fleximsd
5.1.1 Grundlagen
5.1.2 NSI-Nachrichten
5.1.3 Nachbarschaftsverwaltung
5.1.4 Gewichtungsmetriken
5.1.5 Wahl-Architektur
5.1.6 Aktive und Passive Wahl
5.2 Relayd
5.2.1 Architektur
5.2.2 Multi-Hop DNS-SD Nachricht
5.2.3 Dienstverwaltung
5.2.4 Dienstsuche
5.2.5 Dynamic Source Routing
5.3 Realisierung der Distanzadaptierung
5.3.1 Architektur
5.3.2 Annäaherung der NSTAB-Werte
5.3.3 Nachrichtentypen
5.3.4 Anpassung der Parameter von Greedy-Expand
5.3.5 Kontinuierliche Adaptierung
5.3.6 Diskussion anderer Ansätze
5.4 Verbesserung der Wahlstabilitat
5.4.1 Score-Threshold
5.4.2 Auto-Flapping
5.5 Gateway-Bestimmung
5.5.1 Lokaler Algorithmus
5.5.2 Superknoten-zentrisch
5.6 Zusammenfassung

6 Auswertung
6.1 Testumgebung und Präsentation der Ergebnisse
6.1.1 UMIC-Testbed
6.1.2 Aufbau der Messungen
6.2 Analyse der Abhangigkeit der Maximal-Distanz
6.2.1 Durchfährung
6.2.2 Ergebnisse
6.2.3 Bewertung
6.3 Analyse der Clustering-Verfahren
6.3.1 Durchfuährung
6.3.2 Ergebnisse
6.3.3 Bewertung
6.4 Analyse des Auto-Flapping Verfahrens
6.4.1 Durchfährung
6.4.2 Ergebnisse
6.4.3 Bewertung
6.5 Analyse der distanzadaptiven Algorithmen
6.5.1 Durchfährung
6.5.2 Ergebnisse
6.5.3 Bewertung
6.6 Analyse des Greedy-Expand Algorithmus äber 24 Stunden
6.6.1 Durchfährung
6.6.2 Ergebnisse
6.6.3 Bewertung
6.7 Analyse der Cluster-Strukturen mittels Relayd
6.7.1 Durchfährung
6.7.2 Ergebnisse
6.7.3 Bewertung

7 Zusammenfassung und Ausblick
7.1 Zusammenfassung
7.2 Ausblick

Abbildungsverzeichnis

2.1 Infrastruktur-WMN

2.2 Client-WMN

2.3 Hybrid-WMN

2.4 OLSR MPR Mechanismus

2.5 ZPR Routingzonen

3.1 Netzwerkstruktur mit drei Clustern

3.2 Dominating Sets

3.3 Exemplarisches Routing in einer Cluster-Struktur

3.4 Service Discovery: Nutzung eines Verzeichnisagenten

3.5 Problematische Topologie bei Lowest-ID

3.6 Der Ripple Effect bei Lowest-ID

3.7 Cluster-Struktur mit Highest-Connectivity

3.8 Der Wu-Li CDS-Algorithmus

3.9 Die einzelnen Schritte eines Cluster-Merge in AMC

3.10 Min-Searching im adaptiven ZRP

3.11 Optimaler Bereich zwischen reaktiver und proaktiver Dominanz

3.12 Clustering mit Cliquen

4.1 Adaptives Clustering-Framework

4.2 Schematische Darstellung der Clustering-Verfahren

4.3 Cluster-Strukturen mit Lowest-ID

4.4 Gewichtung bei Max-Score mit k-distance =

4.5 Absolute Maximum-Differenz dreier Elite-Auswahlfunktionen

4.6 Egoistischer Ansatz: Gradientenverfahren

4.7 Beispiel des Greedy-Expand Algorithmus

5.1 Aufbau einer NSI-Nachricht

5.2 Fleximsd Wahl-Architektur

5.3 Filterschritt: Kombination von mehreren Candidate-Constraints

5.4 Aufbau der REGISTER-Nachricht

5.5 Aufbau der ACCEPTANCE-Nachricht

5.6 Zusammenspiel zwischen Fleximsd und Relayd sowie dem Endnutzer

5.7 Aufbau der Multi-Hop DNS-SD-Nachricht

5.8 Aufbau eines einzelnen Dienstes im Payload

5.9 Dienstsuche und -weiterleitung in Relayd

5.10 Dynamic Source Routing in Relayd

5.11 Aufbau der K-REQUEST-Nachricht

5.12 Aufbau der K-SCORE-Nachricht

5.13 Beispiel lokal ermittelter Gateway-Knoten

5.14 Beispiel per Superknoten ermittelter Gateway-Knoten

6.1 Entwicklung der Nachbarschaftsstabilitat über 24 Stunden

6.2 NSTAB-Werte für Mesh-Router

6.3 NSTAB-Werte für Mesh-Router

6.4 Entwicklung der PLQ über 24 Stunden

6.5 Cluster-Anzahl im Vergleich

6.6 Durchschnittliche Broadcast-Stabilitat

6.7 Durchschnittliche Nachbaranzahl

6.8 Durschnittliche Anzahl versendeter NSI-Nachrichten pro Knoten

6.9 Cluster-Anzahl innerhalb des Meßzeitraums im Vergleich

6.10 Entwicklung des durchschnittlichen Score-Thresholds über den Messzeitraum

6.11 Distanzadaption: Durschnittlicher NSTAB-Wert pro Mesh-Router

6.12 Distanzadaption: Konfigurierte Maximal-Distanz pro Mesh-Router

6.13 Greedy-Expand: Durchschnittliche k-Distanz

6.14 Greedy-Expand: Durchschnittlicher NSTAB-Verlauf

6.15 Vergleich von NSTAB-Wert und Nachrichtenaufwand

6.16 Greedy-Expand: Anzahl von Clustern

Tabellenverzeichnis

2.1 Vergleich zwischen Wireless-Mesh-Netzwerken und MANETs

5.1 Auto-Flapping: Beispiel geringer Streuung

5.2 Auto-Flapping: Beispiel großer Streuung

6.1 Konfigurationsparameter der 24 Stunden Messungen

6.2 Gesamtdurchschnitte der Messung pro erfasster k-Distanz

6.3 Vergleich von Max-Score, Lowest-ID und Elite-Rating bezüglich Kerndaten

6.4 Durchschnittliche Wechselhaufigkeiten im Vergleich

6.5 Durchschnittliche Kerndaten der distanzadaptiven Algorithmen

6.6 Durchschnittliche Kerndaten von Greedy-Expand im Vergleich

6.7 Vergleich der Kerndaten von Relayd anhand der Cluster-Algorithmen

KAPITEL 1

1. Einführung

Die drahtlose Kommunikation hat in den letzten Jahren einen stetig steigenden Stellen­wert im alltaglichen 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 ei­nem 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 über mehrere Sprünge (Hops) hinweg. Prominente Beispiele dieses Konzepts sind Mobile Ad-Hoc Netzwerke (MANETs, [Sar07]), welche die spontane Vernetzung von Netzwerkteilnehmern ohne grundlegende Infrastruktur erlau­ben. MANETs sind dynamisch ausgerichtet und unterliegen je nach Mobilitat der Knoten starken Topologieschwankungen, wodurch keine Qualitatgarantien der zur Verfügung ge­stellten Netzwerkleistungen gegeben werden können 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ür festinstallierte Zugangspunkte, welche oftmals an das Internet angebunden sind, wird eine stabile Netz­werktopologie geschaffen, die durch andere Teilnehmer einerseits genutzt und andererseits durch diese erweitert werden kann.

Da Wireless-Mesh-Netzwerke skalierbar sind und ihrer Grüße keine Beschrünkungen 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 ausgefuührten Algorithmus werden die Knoten des Netzwerks in logische Gruppen unter­teilt, 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. Gleich­zeitig ist die maximale Distanz, gemessen in Netzwerkspruüngen, eines einzelnen Netzwerk­teilnehmers von vornherein festgelegt und damit statisch an den zu Grund liegenden Al­gorithmus gebunden. WMNs erlauben aber durch ihren teilweise statischen Aufbau meist hochwertige Verbindungen mit dementsprechend höheren zulässigen Distanzen.

Ziel dieser Arbeit ist es, Verfahren fär effizientes Clustering in Wireless-Mesh-Netz- werken zu entwickeln, welche einerseits das stabile Grundgeräst der WMNs in Betracht ziehen und andererseits eine automatische Anpassung an sich andernde Netzwerkeigen­schaften erlauben.

1.1 Wireless-Mesh-Netzwerke

Wireless-Mesh-Netzwerke verfägen im Gegensatz zu den dynamischen Mobilen Ad-Hoc Netzwerken äber eine geplante und meist statische Grundinfrastruktur, welche mittels fe­stinstallierter Router mit verlasslicher 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 si­chergestellt, wobei in WMNs hauptsachlich 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 lo­gische Einheiten, wodurch eine Hierarchie auf der sonst unstrukturierten Netzwerktopolo­gie geschaffen wird. Hierzu wird fär jeden Cluster ein Repräsentant gewahlt, der als lokaler Koordinator der Gruppe fungiert und als Cluster-Head oder Superknoten bezeichnet wird. Typischerweise erfolgt die Kommunikation innerhalb eines selben Clusters direkt, wahrend Verbindungen zu anderen Clustern mittels designierter Vermittler-Knoten, den sogenann­ten Gateways realisiert werden. Cluster-Strukturen haben insbesondere im Bereich der Dienstsuche und der Optimierung von Routingprotokollen ihren Hauptanwendungszweck.

Die Berechnung einer guältigen Cluster-Struktur geschieht entweder zentral durch einen globalen Algorithmus, der Einsicht äber die gesamte Topologie verfägt, 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änkung der maximalen Hop-Distanz aus und das häufig auftretende Problem einer kaskadenformigen 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-Netz- werks 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 Hochstmaß an Stabilitat zu garantieren sollen Algorithmen entwickelt werden, wel­che 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.

Die Verfahren sollen so konzipiert werden, dass sie einen ersten stabilisierenden Schritt vor der eigentlichen Bildung der Cluster darstellen, wobei die Stabilität mittels einer noch zu entwickelnden Metrik gemessen werden soll. Die Verfahren wurden Neuentwicklungen darstellen, ohne vergleichbare, existierende Ansatze.

1.3.2 Stabilitätsorientiert und adaptiv

Da Wireless-Mesh-Netzwerke hauptsachlich mit dem Ziel einer langfristigen und stabilen Infrastruktur aufgebaut werden, sollen die entwickelten Cluster-Verfahren dieser Eigen­schaft höchste Prioritat zurechnen, wobei die zuvor erwahnten distanzadaptiven Verfah­ren die Grundlage hierfur bilden. Kaskadenformige Neustrukturierungen sind weitgehend zu vermeiden, genau wie haufige Superknoten-Wechsel. Gleichzeitig ist ein Hochstmaß an Flexibilitat und die Anpassung an unterschiedliche Netzwerksituation sowie Tageszeiten erwunschenswert.

1.3.3 Modulare Architektur

Basierend auf dem Clustering Unix-Dienst Fleximsd [Kre09] werden die Algorithmen im­plementiert und evaluiert. Gleichzeitig soll der Dienst angepasst werden, um ein Hochst- maß an Modularitat und Konfigurierbarkeit zu bieten, wodurch eine ideale Anpassung an unterschiedliche Netzwerktopologien moglich sein soll. Des Weiteren soll Fleximsd als grundlegender Dienst fur 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, wer­den die Algorithmen mittels einer Service-Discovery-Architektur getestet. Service Disco­very 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 ausnut­zen.

1.5 Gliederung

Der restliche Teil der Arbeit ist folgendermaßen gegliedert: In Kapitel 2 werden zunachst Wireless-Mesh-Netzwerke naher betrachtet. Neben einer Einfuhrung des Begriffs und der unterschiedlichen Infrastrukturen wird insbesondere die Abgrenzung zu MANETs erlautert. Des Weiteren werden in diesem Kapitel drei Routingprotokolle vorgestellt, welche mit drei verschiedenen Ansatze die Berechnung der Netzwerkpfade realisieren. Das Kapitel wird mit der Vorstellung einiger, typischer Anwendungsgebiete abgeschlossen.

Kapitel 3 konzentriert sich auf Clustering. Nach einer ausfuhrlichen Einfuhrung in das Thema und der Verdeutlichung der typischen Rollenverteilung in Cluster-Strukturen, wer­den 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 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 Diplom­arbeit sowie die entwickelten Verfahren vorgestellt. Einführend werden grundlegende Me­triken erläutert, welche bestimmte Qualitütskriterien der Netzwerktopologie quantitativ erfassen und als Grundlage für die anschließend vorgestellten Cluster-Algorithmen dienen. Diese stellen Weiterentwicklungen vorhandener Losung dar, mit dem Fokus auf eine sta- bilitatsorientierte 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 Vorsatzen abgeschlossen.

Kapitel 5 bildet den praktischen Teil der Diplomarbeit und geht naher auf die Imple­mentierung der in der theoretischen Ausarbeitung vorgestellten Verfahren ein. Hier wird zunächst die modulare Architektur des Clustering-Diensts Fleximsd vorgestellt und die genaue Realisierung der Nachrichtentypen und Algorithmen erklart. Anschließend wird die Dienstsuche-Applikation Relayd präsentiert und die Verbindung zwischen diesem und Fleximsd hervorgehoben. Das Kapitel wird mit zwei Abschnitten zur Bestimmung von Gateway-Knoten und Verfahren zur Erhöhung der Cluster-Stabilitat abgeschlossen.

In Kapitel 6 werden einige Messungen prästentiert, welche auf dem UMIC-Testbed [Zim09] durchgeführt 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ünftige Entwicklungen gibt.

KAPITEL 2

2. Wireless-Mesh-Netzwerke

In diesem Kapitel werden die Eigenschaften und die Struktur von Wireless-Mesh-Netzwerk- en (WMN) [AWW05] genauer betrachtet. In Abschnitt 2.1 werden grundlegende Begriffe eingeführt und die unterschiedlichen Architekturen der WMNs erklärt, wahrend in Ab­schnitt 2.2 die Unterschiede zu anderen Ad-Hoc Netzwerken behandelt werden. Abschnitt 2.3 stellt beispielhaft drei, in WMNs verwendete Routingverfahren vor. Abschließend wer­den in Abschnitt 2.4 einige Einsatzmöglichkeiten 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 fahig, erlauben also den teilnehmenden Clients mit nicht direkt erreichbaren Knoten über mehrere Router hinweg zu kommunizieren. Außerdem verbessern teilnehmende Knoten die Verlasslichkeit und Konnektivität des gesamten Netzwerks, da sie sowohl Pakete weiterleiten künnen und die Ausdehnung des Netzwerks vergrüßern, als auch die Toleranz gegenuüber Ausfüallen einzelner Knoten erhoühen. Die Teilnehmer in einem WMN künnen grob in drei Kategorien unterteilt werden [Zim09]:

Backbone-Router Sie bilden den stabilen Teil des Netzwerks (engl. Backbone) und un­terliegen einer sehr geringen Mobilitüt. Neben einer verlasslichen 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-Fahigkeit der WMNs konnen Backbone-Router, die nicht an andere Netzwerke angebunden sind, Pakete anderer Teilnehmer an die Gateway-Knoten weiterleiten.

Routende Clients Diese gehoren zu der Gruppe der Clients, sind also i.d.R. beweglich, übernehmen jedoch Routingaufgaben, die vornehmlich den Backbone-Routern zu­gedacht 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 hoher- en Mobilitüt und der evtl. nicht vorhandenen, dauerhaften Stromversorgung ist die Verlässlichkeit dieser Teilnehmer im Vergleich zu den Backbone-Routern als geringer einzustufen. Ein zutreffendes Beispiel fär routende Clients sind Notebooks.

Nicht-routende Clients Sie sind lediglich Benutzer des WMN und äbernehmen keine Aufgaben. Ein nicht-routender Client verbindet sich mit einem Router, um auf das Netzwerk zugreifen zu kännen; ahnlich der Benutzung eines konventionellen WLAN Netzwerkes. Unter diese Kategorie fallen haufig Gerate, die äber eine vergleichs­weise geringe Rechenkapazität und Laufzeit verfägen, wie etwa Smart Phones oder Personal Digital Assistants (PDAs).

Zwar sind einige Knoten des Netzwerks in vielen Fällen direkt per Kabel an das Internet angeschlossen, doch wird dies nicht als Teil des Netzwerks angesehen und ein WMN als stets kabellos bezeichnet. Wahrend 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 äbernehmen moächte.

Der Aufbau eines Wireless-Mesh-Netzwerks erfordert meistens einen gewissen Plan- ungs- und Wartungsaufwand, da die Backbone-Router je nach Einsatzszenario mäoglichst optimal installiert werden mässen. Dennoch besitzen WMNs durch die Teilnahme rou- tender Clients eine dynamische Ausrichtung. Je nach Vorkommen der vorgestellten Kno­tentypen, 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 fahiges Backbone erzeugen, mit welchem sich gewoähnliche Teilnehmer verbinden koännen. Einige der Router koännen an das Internet angeschlossen werden und uäbernehmen somit die Rolle eines Internet­Gateways. Die Router fungieren hierbei als Zugangspunkte fär die Clients, wobei diese keine Aufgaben uäbernehmen und nicht zur Organisation des Netzwerks beitragen. Ein Beispiel eines Infrastruktur WMN ist in Abbildung 2.1 aufgefährt.

Dieser WMN-Typ ermöglicht eine vergleichsweise maximale Stabilitat, 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 Netz­werken: Das Netzwerk besteht nur aus routenden Clients, wobei keine feste Topologie und Zugangspunkte gegeben sind (s. Abbildung 2.2). Dadurch steigen die Rechenanforderun­gen an die Teilnehmer, da sie die zusatzlichen, organisatorischen Aufgaben, insbesondere das Routing, selbst erledigen mussen.

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

Abbildung in dieser Leseprobe nicht enthalten

2.1.3 Hybrides Wireless-Mesh-Netzwerk

Dieser Netzwerktyp stellt eine Kombination aus der in Abschnitt 2.1.1 und 2.1.2 vorge­stellten WMN-Formen dar. Einerseits wird durch fest installierte Mesh-Router ein stabiles Backbone bereitgestellt, mit welchem sich nicht-routende Clients verbinden können; ande­rerseits erhöhen teilnehmende, routende Clients die Reichweite des gesamten Netzwerks (s. Abbildung 2.3). Da diese Architektur die Variante mit der höchsten Flexibilität darstellt, wird im Folgenden eine hybride Struktur vorausgesetzt, wenn von einem Wireless-Mesh- Netzwerk gesprochen wird.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.3: Hybrid-WMN

2.2 Unterschiede zu MANETs

Wireless-Mesh-Netzwerke gehören zu der Kategorie der drahtlosen Multi-Hop Netzwer­ke; diese zeichnen sich hauptsachlich durch das Weiterleiten von Paketen mit Hilfe von Funkverbindungen öber mehrere Knoten hinweg aus. Weitere Vertreter dieser Klasse sind Mobile Ad Hoc Networks (MANETs) und Sensornetzwerke [Sar07]. MANETs sind infra­strukturlos und oftmals spontaner Natur, wobei sie eine dynamische Topologie besitzen und die räumliche Ausdehnung meistens gering ist. Sie sind besonders auf Gerate geringer Leistung ausgelegt und wegen der auftretenden, unterschiedlichen Mobilitat der Teilneh­mer, muss jeder Knoten Routingaufgaben öbernehmen, wobei die Konnektivitöt zu ande­ren Clients niemals gewahrleistet ist. Sensornetzwerke bestehen aus kleinen Sensorgeröten, die öber Multi-Hop Verbindungen aufgenommene Daten (z.B. Temperaturwerte) draht­los an einen zentralen Monitorknoten öbermitteln; auch hier ist keine feste Infrastruktur vorgegeben.

Der Hauptunterschied zwischen WMNs und MANETs bzw. anderen Ad-Hoc Netz­werken ist, dass WMNs eher statisch ausgerichtet sind und öber eine sich nur lang­sam aöndernde Topologie verfuögen, da die Backbone-Router meistens fest installiert sind [ZLH06]. MANETs unterliegen schnellen Topologieanderungen 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ör WMNs weitaus hoher ist, da zunachst 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 allge­meine Variante dieser Netzwerkform betrachtet werden kann. In Tabelle 2.1 werden die wichtigsten Unterschiede zwischen WMNs und MANETs zusammengefasst.

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 2.1: Vergleich zwischen Wireless-Mesh-Netzwerken und MANETs

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ör Ad-Hoc Netzwerke entwickelten Routingalgorithmen sind häufig uneingeschränkt in Wireless-Mesh-Netzwerken anwendbar, wobei im Folgenden för 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äsentiert, welches die Routingverfahren auf die MAC 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ührt zu der Unterteilung in proaktive, reaktive und hybride Routingverfahren.

Ein proaktives Routingprotokoll versucht zu jedem Zeitpunkt Routen zu jedem an­deren Knoten im Netzwerk bereitstellen zu künnen. Diese Verfahren werden auch als Table-Driven bezeichnet und berechnen neue Routen jeweils durch das periodische Ver­senden von Statusnachrichten. Letzteres ist für den Erhalt aktueller Routen erforderlich, da WMNs, oder allgemein Ad-Hoc Netzwerke, keine zuverlassigen Verbindungen garan­tieren und Funkverbindungen abbrechen oder Teilnehmer das Netzwerk wieder verlassen können. Andererseits können durch Topologieanderungen neue oder verbesserte Routen entstehen.

Ein Nachteil dieses Verfahrens ist, dass durch das kontinuierliche Versenden von Status­paketen ein erhohter Datenverkehr im Netzwerk entsteht. Je nach Dynamik des Netzwerks kann aber das Intervall der Statusnachrichten angepasst werden; so ware es von Vorteil in einem stabilen Netzwerk ein hüoheres Intervall zu wüahlen, da die Wahrscheinlichkeit einer Topologieanderung gering ist. Dagegen sollte in dynamischen Netzwerken das Aktualisie­rungsintervall kurz gehalten werden, um zu verhindern, dass berechnete Routen unguültig werden.

Vorteil eines proaktiven Routingprotokoll ist, dass zu jedem Zeitpunkt verzoügerungs- frei eine Route zu jedem anderen Client des Netzwerks zur Verfügung steht, sofern diese Route auch physisch existiert. Diese Klasse der Routingverfahren ist insbesondere für Netz­werke geeignet, die eine geringe Latenzzeit fordern und deren Prioritat auf der schnellen Verfügbarkeit aller Routen liegt. Das in Abschnitt 2.3.2 vorgestellte Optimized Link State Routing (OLSR) Protokoll [CJ03] zählt zu den proaktiven Ansatzen.

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 mochte, wird ver­sucht eine Route zu diesem zu berechnen. Als Resultat wird entweder die gefundene Route zurückgegeben oder ein Fehler erzeugt, falls der Zielknoten nicht erreicht werden konnte.

Nachteil der reaktiven Routingalgorithmen ist die Verzogerungszeit, die auftritt sobald eine Verbindung hergestellt wird. Da zunachst die gewünschte Route berechnet werden muss, kann der Empfangerknoten 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ührt zu einer besseren Skalier- barkeit und einer effektiveren Routenberechnung in dynamischen und mobilen Netzwerken wie den MANETs. Da sich in solchen Netzwerken die Topologie oft und schnell üandert, koünnen reaktive Protokolle bei jedem Verbindungsversuch die zu diesem Zeitpunkt jeweils optimale Route berechnen. Proaktive Verfahren dagegen laufen in dynamischen Netzwer­ken Gefahr veraltete Routen gespeichert zu haben, falls das Aktualisierungsintervall zu groß gewahlt 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 beider Verfahren miteinandern zu kombinieren und die negativen Einflüsse 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 wer­den 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öhten Datenverkehr zu reduzieren, verwendet OLSR das Konzept der Multipoint Relays (MPRs). Jeder Knoten wahlt aus seinen direkt erreichbaren, symmetrischen Nachbarn[1] eine Menge an MPRs aus, welche ausschließlich Nachrichten des Knotens weiterleiten dürfen (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 ma­ximal zwei Hops entfernt sind. Zusatzlich sind Informationen im Paket enthalten, ob die Verbindungen untereinander symmetrisch sind, wodurch sich die Menge der MPRs be­rechnen lasst.

Topology Control (TC) Nachrichten werden nur von den gewühlten 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üngt die TC Nachrichten und erhült somit eine Übersicht über eine angenaherte Topologie des gesamten Netzwerks, wodurch sich moglichst optimale Routen zu jedem Knoten im Netzwerk berechnen lassen. OLSR bezeichnet solche Routen als optimal, welche die kürzeste Hopanzahl zwischen den Knoten aufweisen.

Um mehrere Netzwerkadapter zu unterstützen, spezifiziert OLSR die Multiple Inter­face Description (MID) Nachrichten. Neben der Adresse des designierten Hauptadapters werden alle bekannten Adapteradressen mit Hilfe des MPR-Mechanismus über das gesam­te Netzwerk verteilt. So künnen Routen mittels der Zuordnung der Hauptadresse auch zu den Nebenadaptern berechnet werden.

Host and Network Association (HNA) Nachrichten enthalten Netzwerkmaske und - adresse 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 übernehmen.

OLSR wurde im Rahmen des UniK OLSR Daemon [TLGP09] implementiert, wel­cher erfolgreich den Betrieb eines offentlichen WMNs u.a. in Berlin gewährleistet[2]. 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 enthalt jedes gesendete Paket alle notigen Routinginforma­tionen, um das Ziel zu erreichen. Gleichzeitig speichert jeder Knoten Informationen über

Abbildung in dieser Leseprobe nicht enthalten

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 mochte, überprüft dieser zunächst, ob sich eine Route zu dem gewünschten Ziel im Zwischen­speicher befindet. Falls ja, werden die Routinginformationen dem Paket hinzugefügt und versendet. Falls keine Route bekannt ist, wird ein route request (Routenanfrage, RREQ) via Broadcast versendet, wobei jedes Paket eindeutig durch Sender, Empfanger und einer Identifikationsnummer zugeordnet werden kann. Jeder Empfanger überprüft zunächst, ob eine Route zum Zielknoten bekannt ist und erstellt eine route reply (Antwort, RREP) Pa­ket, falls dies zutrifft. Diese enthalt 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üngt und an die direkten Nachbarn weitergeleitet. Erreicht die Routenanfrage den Zielknoten, wird ein Antwort Paket mit umgekehrter Reihenfolge der passierten Knoten zurückgesendet. Zur Limitierung des Da­tenverkehrs 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ückgeschickt und die Rou­ten Reparatur Phase wird angestoßen, wobei jeder passierte Zwischenknoten den nicht erreichbaren Knoten aus seinem Zwischenspeicher lüscht.

Im Vergleich zu dem reaktiven Ad Hoc On-demand Distance Vector Routing (AODV) [PBR99], das einen ahnlichen Ansatz zur Routenfindung verwendet, benötigt DSR kei­ne Routingtabellen, da alle Routinginformationen im Datenpaket selbst gespeichert sind. Dies kann unter Umstünden zu einem großen Overhead führen, der sich proportional zur Pfadlünge verhült und insbesondere negativ bei Verwendung des IPv6 [DH98] Protokolls auffüllt. DSR eignet sich insbesondere für Netzwerke geringer Mobilitat und geringer An­zahl an Knoten mit beschrankter Rechenkapazitüt [DPR00].

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

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.5: Routingzonen der Große 1 aus Sicht des Knotens “A”: B,C,D sind Peri­pherieknoten, Eliegt in der Routingzone von C.

2.3.4 Zone Routing Protocol

Das hybride Zone Routing Protocol (ZRP) ist für mobile Ad-Hoc Netzwerke konzipiert worden und versucht den Overhead proaktiver Routingprotokolle zu minimieren bei gleich­zeitiger Verringerung der Latenzzeiten eines reaktiven Protokolls. Im ZRP wird das Netz­werk 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 betragt. Die Knoten, die genau d Hops von N entfernt sind, werden als Peripherieknoten bezeichnet (s. Abbildung 2.5).

Anhand dieser Unterteilung werden verschiedene Routingansatze implementiert: In­nerhalb einer Routingzone wird ein proaktives Intra-zone Routing Protokoll (IARP) ein­gesetzt, wührend für Datenverkehr außerhalb der Routingzone, also zwischen den Rou­tingzonen, 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ührten DSR Protokoll: zunachst werden die Peripherieknoten angefragt, welche entweder die gewünschte, zwischengespei­cherte Route zuruückliefern 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ühren kann. Vorteil ist, dass Routen innerhalb der eigenen Routingzone sofort verfuügbar sind und, dass das Berechnen neuer Routen bei Netzwerkanderungen nur zwischen zwei Routingzonen geschieht, was die Effizi­enz des Routingverfahrens erhöht. 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üngigen Standard zur Einrichtung von WMNs zu etablieren. Die bisher vorgestellten Routingverfahren arbeiten auf der Transportschicht (Schicht 3) des ISO OSI Schichtenmodells, wührend IEEE 802.11s eine Verlagerung der Routingfunktionalitüt auf 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 Routingproto­koll mit einem proaktiven, Baum-basierten Protokoll kombiniert. Das reaktive Protokoll wird eingesetzt, um den mobilen Teil des Netzwerks verwalten zu können, wahrend das proaktive Protokoll verwendet wird, falls das Netzwerk über designierte, fest installierte Knoten (Mesh Portals) verfügt.

Zwar konnen durch die Verlagerung der Routingfunktionen auf die MAC Ebene ein we­niger 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üß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ür das Linux Betriebssy­stem an.

2.4 Einsatzmöglichkeiten

Im Gegensatz zu herkommlichen Kabelnetzwerken, konnen WMNs relativ schnell instal­liert werden, streben aber einen vergleichbaren Benutzungskomfort an. Da die Einsatzge­biete dieser Netzwerke sehr weit gefasst sind, wird im Folgenden beispielhaft nur auf einige Wenige eingegangen [AWW05]:

Breitband Heimnetzwerke Herkommliche Drahtlosnetzwerke konnen oftmals nicht al­le Bereiche eines Heimnetzwerks abdecken, weswegen hier die Installation von meh­reren Mesh-Routern sinnvoll ist. Durch die Benutzung eines einheitlichen Routing­protokolls koünnen die drahtlosen Router kostenguünstig zu einem Mesh Netzwerk zusammengeschlossen werden, wobei die Netzwerklast insgesamt verringert werden kann, da der gesamte Datenverkehr nicht über einen zentralen Router geleitet werden muss, sondern auf alle Router verteilt wird.

Notfallsituationen In Katastrophenszenarien (Brande, Unfülle usw.) ist es oft notig, schnell eine solide Kommunikationsplattform aufzubauen. Da eine Netzwerkinfra­struktur im Vorhinein nicht planbar ist, sind gerade WMNs durch ihre Dynamik zuügig installierbar. So koünnten, 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ührt womoglich zu einem Komplettausfall des betroffenen Büros. Durch die Redundanz eines WMNs kann hier die Toleranz gegenüber Ausfallen verbessert werden. Auch profitiert das gesamte Netzwerk von der Installation einer zusüatzlichen, externen Leitung, da die Gesamtkapazitüat durch die Multihop-Faühigkeit 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.

Abbildung in dieser Leseprobe nicht enthalten

KAPITEL 3

3. Clustering

Nachdem in diesem Kapitel zunächst der Begriff Clustering eingeführt wird, werden dar­aufhin die relevanten Grundlagen betrachtet (Abschnitt 3.1 und 3.2). In Abschnitt 3.3 und 3.4 werden typische Anwendungsfelder von Clustering-Verfahren aufgezeigt und mögli­che Richtlinien zur Klassifikation der Methoden vorgestellt. Anschließend werden in Ab­schnitt 3.5 ausgewahlte Cluster-Algorithmen für Ad-Hoc Netzwerke eingeführt, welche in Abschnitt 3.6 zusammengefasst und auf eine mügliche Übertragbarkeit auf WMNs hin analysiert werden.

3.1 Einführung

Die Skalierbarkeit des Internets ist durch den hierarchischen Aufbau der IP-Adressen gewührleistet, deren Informationen dazu verwendet werden ein Paket zu seinem Ziel zu leiten. In Multihop-Netzwerken künnen diese nicht als alleiniges Mittel eine effiziente Hier­archie bereitstellen, da jene keine geografische Zuordnung der Adressen zu ihren jeweiligen Teilnehmern erlauben. In einer unstrukturierten, funkbasierten Netzwerktopologie steigt der Verwaltungsaufwand quadratisch mit der Anzahl der Teilnehmer und mit zunehmender Grüße des Netzwerks nimmt der Anteil des Verwaltungsoverheads stark zu [BR02]. In einer solchen unstrukturierten Topolgie, mitunter auch als “flach” bezeichnet, muss jeder Kno­ten eine Übersicht über das gesamte Netzwerk besitzen, um mit jedem beliebigen Knoten des Netzwerks kommunizieren zu konnen. Üm Skalierbarkeit in einem Multihop-Netzwerk und damit einem WMN zu ermoüglichen, sind hierarchische Strukturen von Nüoten, die die Netzwerktopologie abstrahieren und Aufgaben, wie Routing, effizient ermüglichen [GK00].

Clustering (Haufung) ist ein solcher Prozess, der das Netzwerk in eine abstrahierte Hierarchie überführt [YC05]. Hierbei werden Knoten zu einem Cluster (Ansammlung) zu­sammengefasst, wodurch die Topologie des Netzwerks kompakter erscheint. Dieser Schritt kann mehrmals auf die jeweils entstandene Cluster-Struktur angewandt werden, um den gewuünschten Abstraktionsgrad zu erreichen. Die aus der Cluster-Bildung induzierte Hier­archie ermüoglicht die effiziente Nutzung vieler Anwendungen in Ad-Hoc-Netzwerken, wie beispielsweise hierarchisches Routing, die effiziente Nutzung eines limitierten Frequenz­spektrums oder die Verbesserung von Dienstsuche-Verfahren (vgl. Abschnitt 3.3).

3.2 Grundlagen

Das Clustering-Problem kann anhand eines ungerichteten Graphen G = (V,, E) forma­lisiert werden: Die Knotenmenge V bezeichnet die Teilnehmer des Netzwerks und die Kanten aus der Menge E entsprechen den möglichen Kommunikationswegen, wobei verein­facht angenommen wird, dass stets bidirektionale Verbindungen bestehen. Ein Clustering- Verfahren unterteilt V in eine Menge von, nicht notwendigerweise disjunkten Teilmengen [Abbildung in dieser Leseprobe nicht enthalten] wobei [Abbildung in dieser Leseprobe nicht enthalten] gilt und jede Untermenge V einen zusammenhangenden Teilgraph von G induziert. Letztere konnen durch die Einteilung der Knoten überlappen. Die Teilmengen der Knoten bilden die einzelnen Cluster und typischerweise wird ein Kno­ten als Reprüsentant eines Clusters gewahlt, welcher als Cluster-Head1 (CH) bezeichnet wird [CLL04]. Ein Cluster besteht somit aus einem CH und den Knoten des Netzwerks, die diesen gewüahlt haben.

Abgesehen von dem Cluster-Head, der als lokaler Koordinator des Clusters fungiert, existieren zwei weitere Funktionen in einem Cluster: Cluster-Member und Cluster-Gateway. Cluster-Gateways sind Knoten, die nicht den Status eines CHs tragen, aber Verbindun­gen zu mindestens zwei verschiedenen Cluster-Heads haben und somit eine Inter-Cluster­Kommunikation erlauben. Cluster-Member sind jene Knoten, die lediglich den Status eines Mitglieds in einem Clusters besitzen (s. Abbildung 3.1).

Als offene Nachbarschaft N[Abbildung in dieser Leseprobe nicht enthalten] eines Knotens v in einem Graph G wird die Menge bezeichnet, die alle Knoten enthült, welche zu v adjazent sind. Mittels einer Distanzfunk­tion dist[Abbildung in dieser Leseprobe nicht enthalten] für alle Knoten [Abbildung in dieser Leseprobe nicht enthalten] lasst sich die offene Nachbarschaft mit [Abbildung in dieser Leseprobe nicht enthalten] formalisieren. dist[Abbildung in dieser Leseprobe nicht enthalten] bezeichnet die minimale Lünge aller Pfade zwischen zwei Knoten u und v. Die geschlossene Nachbarschaft N[Abbildung in dieser Leseprobe nicht enthalten] eines Kno­tens v ist mit [Abbildung in dieser Leseprobe nicht enthalten] definiert. Die offene k-Nachbarschaft von v enthalt die Knoten die bezüglich der Distanzfunktion dist nicht weiter als k entfernt sind, al­so [Abbildung in dieser Leseprobe nicht enthalten]. Der Grad eines Knotens [Abbildung in dieser Leseprobe nicht enthalten] ist als [Abbildung in dieser Leseprobe nicht enthalten] definiert und der k-Grad als [Abbildung in dieser Leseprobe nicht enthalten].

Alternative Bezeichnungen in der Literatur sind Cluster-Leader, Supernode oder Superknoten.

3.2.1 Dominating Sets

Eine Cluster-Struktur lasst sich mit Hilfe der Dominating Set (Dominierende Menge, DS) Notation beschreiben: ein Dominating Set eines Graphen G = (V, E) ist eine Teilmenge S [Abbildung in dieser Leseprobe nicht enthalten] V, sodass jeder Knoten entweder in S enthalten oder zu einem Element aus S ad­jazent ist (s. Abbildung 3.2(a)) [HHS98]. Die Elemente aus S werden als dominierende Knoten bezeichnet, während die Menge V [Abbildung in dieser Leseprobe nicht enthalten] S die dominierten Knoten enthalt. Die do­minierenden Knoten kännen als Cluster-Heads aufgefasst werden, wahrend die jeweiligen Nachbarschaften dieser Knoten die einzelnen Cluster bilden. Durch die Eigenschaften ei­nes Dominating Set ergibt sich im Fall einer Übertragung auf ein Funknetzwerk, dass ein dominierter Knoten einen Teilnehmer der dominierenden Menge mit maximal einem Hop erreichen kann.

Eine verallgemeinerte Form einer dominierenden Menge stellt das k-Distance Domi­nating Set (k-DDS) dar, welches von dominierten Knoten nicht fordert direkt adjazent zu einem Element der dominierenden Menge zu sein, sondern eine maximale Distanz von k zu einem dominierenden Knoten erlaubt. Formal gilt damit fär jeden Knoten v eines Graphen G mit einem k-DDS S, dass entweder [Abbildung in dieser Leseprobe nicht enthalten] oder [Abbildung in dieser Leseprobe nicht enthalten] : dist[Abbildung in dieser Leseprobe nicht enthalten] < k gilt. Gleichbedeutend formuliert ist eine Menge [Abbildung in dieser Leseprobe nicht enthalten] ein k-DSS genau dann wenn, jeder Kno­ten des Graph in der geschlossenen Nachbarschaft Nk(u) eines beliebigen Knoten u € S enthalten ist.

Ein Dominating Set S ist genau dann unabhängig, wenn keine zwei Elemente der domi­nierenden Menge adjazent zueinander sind. Ein Connected Dominating Set (CDS) fordert zusäatzlich, dass alle Knoten einer dominierende Menge S C G direkt adjazent zueinander sind, sprich der induzierte Teilgraph der Menge, mit (S) bezeichnet, zusammenhangend ist (s. Abbildung 3.2(b)).

Fär jede Teilmenge S C V wird der schwach induzierte Teilgraph (S)w mit (S)w = (N[S],E n (N[S] x S)) definiert. Dieser enthalt somit alle Knoten aus S mitsamt Nach­barn und alle Kanten aus dem Ürsprungsgraph, die mindestens einen Endpunkt in S besitzen. Eine Teilmenge S der Knoten im Graph wird als Weakly-Connected Dominating Set bezeichnet, falls S einerseits eine dominierende Menge ist und andererseits der schwach induzierte Teilgraph (S)w zusammenhangend ist.

Jede Menge S = V erfällt trivialerweise die Bedingung eines DS, weswegen das ei­gentlich relevante Problem ist, eine dominierende Menge minimaler Große zu berechnen. Übertragen auf ein Funknetzwerk bedeutet dies, eine Cluster-Struktur mit einer kleinst- mäoglichen Anzahl von Cluster-Heads zu finden, um ein mäoglichst kompaktes, abstrahiertes Netzwerk zu berechnen. Das Problem ein minimales DS zu bestimmen ist NP-vollstäandig, genauso wie das Minimum abgeleiteter Varianten zu berechnen und ist somit nicht fär jeden beliebigen Graph in polynomieller Zeit lösbar. Daher sind, um mäglichst nahe am Optimum liegende dominierende Mengen zu berechnen, annähernde Algorithmen und Heu­ristiken notwendig [HHS98].

3.3 Anwendung

In diesem Abschnitt werden exemplarisch einige Anwendungsfelder aufgezeigt, die von einer hierarchischen Cluster-Struktur profitieren käonnen. Grundsäatzlich ist ein gutes Clu­stering vorteilhaft fär alle Verfahren in Multihop-Netzwerken, welche auch mit großer Anzahl von Teilnehmern skalierbar sein sollen.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3.2: Dominating Sets

3.3.1 Routing

Die in Abschnitt 2.3 vorgestellten proaktiven und reaktiven Routingprotokolle bieten kei­ne gute Skalierbarkeit in großen Multihop-Netzwerken: Proaktive Routingprotokolle haben eine Komplexität von O(n2), wobei n die Anzahl der Teilnehmer des Netzwerks bezeichnet [BR02]. Zu jedem Knoten des Netzwerks muss eine Route bereitgestellt werden, wodurch der Berechnungsaufwand mit der Anzahl der Knoten steigt, und gleichzeitig der Speicher­bedarf erhöht wird [Bet03]. Es werden keine Hierarchien im Netzwerk ausgenutzt; von außen betrachtet handelt es sich um eine flache Topologie. Reaktive Protokolle senden Broadcast Nachrichten um den Zielknoten zu finden und verursachen dadurch ein “Fluten” des Netzwerks, was insbesondere die Skalierbarkeit in großen Netzwerken beeinträachtigt [LBRP03].

Clustering bietet die Mäglichkeit eines hierarchischen Routings: In einer Cluster-Struk­tur werden Routinginformationen nur zwischen Cluster-Heads und Cluster-Gateways aus­getauscht [LCWG97]. Die Gateway-Knoten äbernehmen die Inter-Cluster-Kommunikation, also das Routing zwischen zwei verschiedenen Clustern. Wahrend in flachen Topologien Routen mit ihren jeweiligen Spruängen gekennzeichnet werden, sind Routen in hierarchi­schen Cluster-Strukturen durch ihre Cluster-Spränge gekennzeichnet [BR02]. Durch die gebildete Hierarchie betreffen lokale Topologieanderungen nur den jeweiligen Cluster und wirken sich nicht negativ auf das gesamte Netzwerk aus [Bet03]. Gleichzeitig ermäglicht ein in Cluster eingeteiltes Netzwerk robustere Routen, da mehrere, redundante Verbindungen zwischen einzelnen Clustern bereitgestellt werden kännen [BR02]. Die Toleranz gegenäber lokalen Verbindungsabbrächen und Topologieänderungen wird erhoht.

In Abbildung 3.3 ist ein Beispiel eines hierarchischen Routings angegeben. Knoten S mochte eine Verbindung zu dem Teilnehmer D herstellen, wobei ein flaches Routingverfah­ren beispielsweise die Route [Abbildung in dieser Leseprobe nicht enthalten] vorschlägt. In einer Cluster­Struktur wie im Beispiel dargestellt, ergibt sich die Route [Abbildung in dieser Leseprobe nicht enthalten]. Vorteil Letzterer ist, dass bei einem Ausfall der Verbindung [Abbildung in dieser Leseprobe nicht enthalten] ein Cluster-basierter Routingalgorithmus die Mäoglichkeit häatte, eine Verbindung mit Hilfe der redundanten

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3.3: Exemplarisches Routing in einer Cluster-Struktur

Pfade über G2 und G3 herzustellen. Ein hierarchieloses Routingverfahren wäre gezwun­gen, zunächst eine neue Route zu berechnen.

3.3.2 Service Discovery

Service Discovery bzw. Dienstsuche ist ein Verfahren, um im Netzwerk bereitgestellte Dienste, wie beispielsweise Software oder angeschlossene Geräte, zu finden [EE06]. Das klassische Modell einer Service-Discovery-Architektur unterteilt die teilnehmenden Kno­ten in drei Kategorien: Die Benutzeragenten (User Agents) suchen nach Diensten im Netz­werk, wahrend Dienstagenten Letztere anbieten. Verzeichnisagenten sammeln Informatio­nen über vorhandene Dienste und stellen diese zur Verfügung; Dienstagenten registrieren sich hierzu bei einem verfügbaren Verzeichnisagenten. Typischerweise können die Teil­nehmer mehrere dieser Rollen gleichzeitig übernehmen. In einem beispielhaften Service- Discovery-Prozess sendet ein Benutzeragent eine spezifische Dienstanfrage an einen Ver­zeichnisagenten, welcher mit ihm bekannten, von Dienstagenten bereitgestellten Diensten antwortet (s. Abbildung 3.4).

Eine Moglichkeit die Effizienz von Service Discovery Prozessen in einem Multihop­Netzwerk zu verbessern, stellt die Verwendung einer vorhandenen Cluster-Struktur dar. In [LZL+02] wird eine mogliche Anwendung eines Netzwerk-Clustering beschrieben: Im ersten Schritt wird ein Virtual Backbone (VB) aufgebaut, welches aus der Menge der Cluster-Heads im Netzwerk besteht. Alle Anfragen und Registraturnachrichten werden nur zwischen den Mitgliedern des VBs ausgetauscht. Ein Cluster-Head wird hierbei auto­matisch auch Verzeichnisagent. Des Weiteren wurde in [KK09] ein Connected Dominating Set basiertes Protokoll für Service Discovery entwickelt, welches auf die Eigenschaften von WMNs zugeschnitten ist und die Effizienz der Dienstsuche stark verbessert.

3.3.3 Weitere Anwendungsfelder

Eine weitere Einsatzmüoglichkeit einer Cluster-Struktur ist die verbesserte Nutzung von Frequenspektren innerhalb eines Funknetzwerks: Um Interferenzen im Netzwerk zu ver­meiden, die durch die Verwendung desselben Funkkanals auftreten, konnen den Clustern unterschiedliche Frequenzen, beziehungsweise verschiedene Kommunikationskanale, zuge-

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3.4: Service Discovery: Nutzung eines Verzeichnisagenten

wiesen werden, sofern die Cluster nicht benachbart sind [CLW03]. Hierdurch wird eine bessere räumliche Ausnutzung der vorhandenen Funkressourcen erreicht und die System­kapazität insgesamt erhäht [GT97].

Ein in Cluster unterteiltes Netzwerk kann zudem dazu verwendet werden, den einzelnen Teilnehmern hierarchische Adressen zuzuweisen [CLL04]. Abhängig von der Zugehörigkeit zu einem Cluster werden hierarchische Adressen konstruiert, die ahnlich der IP-Adressen eine strukturierte Lokalisierung des Teilnehmers erlauben. Zusäatzlich kann eine gegebe­ne Cluster-Struktur rekursiv in ein äbergeordnetes Clustering äberfährt werden, bis die gewuänschte Abstraktionsebene erreicht ist.

3.4 Klassifikation von Clustering-Verfahren

Es gibt keine einheitlichen Richtlinien zur Kategorisierung von Clustering-Verfahren, wes­halb im Folgenden einige mägliche Unterscheidungskriterien aufgefährt werden [YC05]:

Zentralisiert oder Dezentral Eine Cluster-Struktur kann einerseits mit Hilfe eines zen­tralen Koordinators erzeugt werden, welcher mit Informationen äber die gesamte To­pologie des Netzwerks die einzelnen Cluster bildet. Andererseits kann die Berechnung der Cluster durch einen verteilten und damit dezentralen Algorithmus ausgefährt werden, wobei jeder Teilnehmer des Netzwerks mit ausschließlich lokalen Informa­tionen entscheidet, welche Rolle er äbernimmt oder welchem Cluster er angehärt.

Cluster-Head-basiert Der Großteil der vorhandenen Cluster-Verfahren beruht auf der in den vorherigen Abschnitten vorgestellten Rollenverteilung, welche sich auf der zentralen Rolle eines designierten Cluster-Heads stätzt. Dennoch existieren Verfah­ren, die auf einen lokalen Koordinator verzichten und eine Netzwerkhierarchie ohne Hinzunahme eines hähergestellten Knotens bilden (vgl. Abschnitt 3.5.7).

Zielorientiert In [YC05] werden Clustering-Algorithmen fär MANETs (vgl. Abschnitt 2.2) entsprechend ihrer Zielvorgabe klassifiziert. Als Kategorien werden beispiels­weise Dominating Set basierte Verfahren genannt. Die Verfahren werden aber auch dadurch zusammengefasst, dass sie geringen Aufwand zur Beibehaltung einer gülti­ gen Cluster-Struktur aufwenden, oder besonders auf eine energieeffiziente Nutzung der Ressourcen zielen.

3.5 Clustering-Verfahren für Ad-Hoc-Netzwerke

In Ad-Hoc-Netzwerken existieren eine Vielzahl von Clustering-Ansatzen, wobei stets ver­schiedene Schwerpunkte gesetzt sind und bestimmte Anwendungsbereiche priorisiert wer­den. Je nach Netzwerktopolgie werden unterschiedliche Resultate produziert und die Eig­nung eines bestimmten Verfahrens auf jede Nutzungssituation kann in keinem Fall gewahr­leistet werden. Im Folgenden wird eine Auswahl verschiedener Clustering-Algorithmen naher betrachtet, wobei die Einschränkung auf rein verteilten Algorithmen liegt, wel­che dezentral arbeiten und auf einen globalen Koordinator verzichten. In Hinblick auf eine adaptive Anwendung der Verfahren hat dies den Vorteil, dass keine organisatorische Grundinfrastruktur vorausgesetzt werden muss.

3.5.1 Lowest-ID

Der Lowest-ID Algorithmus wurde als eines der ersten Clustering-Verfahren insbesondere in Hinblick auf eine Wiederverwendbarkeit der Frequenzspektren für Multihop-Netzwerke entwickelt [GT97]. In einem Code Division Multiple Access (CDMA) basierten Netzwerk wird jedem Cluster ein einheitlicher Code zugewiesen, welcher zur Kommunikation der Mitglieder genutzt wird. Der Algorithmus ist verteilt realisiert, benötigt somit nur loka­les Wissen, ohne die Hinzunahme eines zentralen Koordinators, der die Cluster-Struktur aufbaut. Vorausgesetzt wird, dass jedem Knoten im Netzwerk eine eindeutige ID2 zuge­wiesen ist und alle Teilnehmer über Informationen verfügen, welche Knoten sich in ihrer direkten Nachbarschaft befinden, also solche, die mit einem Sprung erreichbar sind. Diese Informationen werden periodisch unter allen direkten Nachbarn ausgetauscht.

Lowest-ID beruht darauf, Cluster-Heads und Gateway-Knoten zu bestimmen, wobei jeder Knoten in periodischen Abstüanden anhand folgender Regeln bestimmt, welche Rolle ihm zugeteilt wird:

- Ein Knoten, der die niedrigste ID im Vergleich zu seinen Nachbarn besitzt, über­nimmt die Rolle eines Cluster-Heads.
- Falls der Knoten nicht selbst die niedrigste ID seiner geschlossenen Nachbarschaft besitzt, so wüahlt er jenen Knoten zum Cluster-Head, welcher durch den niedrigsten ID-Wert identifiziert wird, sofern dieser seine Rolle als Cluster-Head nicht aufgibt. Letzterer Fall tritt ein, wenn dieser seine Rolle als Cluster-Head verliert, weil ein Knoten mit nochmals kleinerer ID in seiner Nachbarschaft existiert.
- Ein Knoten, der in seiner Nachbarschaft mindestens zwei Cluster-Heads sieht, uüber- nimmt die Rolle eines Gateway-Knotens.
- Falls keiner der obigen Füalle eintritt, handelt es sich um einen normalen Knoten, also ein Cluster-Member.
Durch die Rollenverteilung der Knoten ergeben sich folgende Eigenschaften des Netz­werks: Zum Einen sind zwei Cluster-Heads niemals miteinander verbunden und damit in[3]

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3.5: Problematische Topologie bei Lowest-ID

direkter Nachbarschaft. Zum Anderen liegen höchstens zwei Sprünge zwischen einem Paar beliebiger Knoten eines selben Clusters, da jeder Knoten direkt mit seinem gewahlten Cluster-Head verbunden ist. In [CNSGS02] wurde gezeigt, dass der Lowest-ID Algorith­mus in einigen Netzwerktopologien Knoten ohne assoziiertem Cluster-Head generiert: In der Beispieltopologie in Abbildung 3.5 gehoren die Knoten 4, 5 und 6 keinem Cluster an, da die Regeln des Algorithmus verletzt werden würden, falls einer dieser Teilnehmer die Rolle eines Cluster-Heads Übernahme.

Aus diesem Grund wurde in [LG97] eine erweiterte Variante von Lowest-ID[4] vorge­stellt: Der verteilte Algorithmus wird durch jene Knoten initiiert, welche die niedrigste ID innerhalb ihrer Nachbarschaft besitzen. Diese erzeugen einen neuen Cluster, indem sie sich selbst als Cluster-Head deklarieren und diese Entscheidung ihren direkten Nachbarn mit­teilen, welche einen deklarierten Cluster-Head mit der jeweils niedrigsten ID wühlen. Falls in der Nachbarschaft eines Knoten v kein Teilnehmer mit niedrigerer ID einen Cluster ge­bildet hat, nimmt v selbst den Status eines Cluster-Heads an und teilt diese Entscheidung mit. Dieses Verfahren wird so lange ausgeführt, bis alle Knoten einem Cluster angehoren oder selbst Cluster-Head geworden sind. Die Komplexitat gemessen an Kommunikations­runden betrügt maximal O(\V|), wobei \V| die Anzahl an Netzwerkknoten bezeichnet.

In der vorgestellten, erweiterten Variante wird sichergestellt, dass jeder Knoten einem Cluster angehort, also direkt mit einem Cluster-Head verbunden ist. Dennoch besteht keine Verbindung zwischen zwei beliebigen CHs des Netzwerks. Hieraus resultiert, dass die, durch den Lowest-ID Algorithmus erzeugte Menge an Cluster-Heads, ein in Abschnitt 3.2.1 beschriebenes unabhüngiges Dominating Set bilden.

Da die Knoten im Netzwerk unabhüngig voneinander, in regelmüßigen Abstünden die obengenannten Regeln anwenden, koünnen Topologieüanderungen zu einer Neustrukturie­rung der Cluster führen. In Abbildung 3.6(a) wurden mittels der erweiterten Lowest-ID Variante Cluster gebildet: Durch das Auftreten des Knotens mit der ID 1 und der dadurch resultierenden Regelanpassung müssen die Knoten 3 und 5 ihre Rolle als Cluster-Head aufgeben (s. Abbildung 3.6(b)). Dieser Effekt wird Ripple-Effect genannt [YC05] und be­zeichnet das kaskadenfüormige Neuwüahlen von Cluster-Heads, woraus eine komplette Neu­strukturierung des gesamten Clusterings resultieren kann.

Zwar erzeugt der Lowest-ID Algorithmus Cluster-Strukturen mit relativ hoher Stabi- litat bezüglich der Anzahl an Cluster-Head Wechseln [GT97], doch werden die Cluster- Heads nur abhangig des statischen ID Parameters gewahlt. Die Konnektivitüt oder andere Maßstabe für die Eignung des Knotens als Cluster-Head werden nicht betrachtet.

[...]


[1] Zwischen symmetrischen Nachbarn besteht eine bidirektionale Verbindung, d.h. es können beide Kno­ten sowohl empfangen als auch senden.

[2] Das Netzwerk wird von der allgemeinnützigen Organisation Freifunk Initiative [Fre09] verwaltet.

[3] Bei der ID kann es sich beispielweise um die IP-Adresse des Teilnehmers handeln.

[4] Aufgrund der Tatsache, dass der vorgestellte Algorithmus eine Erweiterung der Ursprungsversion dar­stellt, wird im Folgenden diese Variante angenommen, falls Lowest-ID erwähnt wird.

Details

Seiten
119
Jahr
2010
ISBN (eBook)
9783640583027
ISBN (Buch)
9783640583485
Dateigröße
1.8 MB
Sprache
Deutsch
Katalognummer
v147213
Institution / Hochschule
Rheinisch-Westfälische Technische Hochschule Aachen
Note
1.0
Schlagworte
informatik wireless-mesh-netzwerk ad-hoc-netzwerk clustering praktische informatik

Autor

Teilen

Zurück

Titel: Adaptives Clustering in Wireless-Mesh-Netzwerken