Klassische Drahtlosnetzwerke sind 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 hinweg. Prominente Beispiele dieses Konzepts sind Mobile Ad-Hoc Netzwerke (MANETs), welche die spontane Vernetzung von Netzwerkteilnehmern ohne grundlegende Infrastruktur erlauben. MANETs sind dynamisch ausgerichtet und unterliegen je nach Mobilität der Knoten starken Topologieschwankungen, wodurch keine Qualitätgarantien der zur Verfügung gestellten Netzwerkleistungen gegeben werden können und keine feste Existenzdauer des Netzwerks vorgegeben ist. Wireless-Mesh-Netzwerke (WMNs) 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 Netzwerktopologie 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öten, welche den Verwaltungsaufwand des Netzwerks reduzieren. Ein Mittel um die Netzwerktopologie hierarchisch zu strukturieren ist das sogenannte Clustering: Mittels eines lokal oder global ausgeführten 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äquat nutzen. Gleichzeitig ist die maximale Distanz, gemessen in Netzwerksprüngen, eines einzelnen Netzwerkteilnehmers von vornherein festgelegt und damit statisch an den zu Grund liegenden Algorithmus gebunden.
Ziel dieser Arbeit ist es, Verfahren für effizientes Clustering in Wireless-Mesh-Netzwerken zu entwickeln, welche einerseits das stabile Grundgerüst der WMNs in Betracht ziehen und andererseits eine automatische Anpassung an sich ändernde Netzwerkeigenschaften erlauben.
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 Ansätze
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äten annähern
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äherung 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 Wahlstabilität
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 Abhängigkeit 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. Durchfü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
Zielsetzung & Themen
Ziel dieser Arbeit ist die Entwicklung effizienter Clustering-Verfahren für Wireless-Mesh-Netzwerke, die sowohl die stabile Grundinfrastruktur dieser Netzwerke berücksichtigen als auch eine automatische Anpassung an veränderliche Netzwerkbedingungen ermöglichen.
- Entwicklung stabilitätsorientierter und adaptiver Cluster-Algorithmen
- Optimierung von Routing und Dienstsuche (Service Discovery) in hierarchisch strukturierten Netzwerken
- Implementierung einer modularen Architektur (Fleximsd) zur Cluster-Verwaltung
- Evaluation der Praxistauglichkeit der Verfahren in einer realen Testumgebung (UMIC-Testbed)
Auszug aus dem Buch
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 Hierarchie 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 Knoten eine Übersicht über das gesamte Netzwerk besitzen, um mit jedem beliebigen Knoten des Netzwerks kommunizieren zu können. Um Skalierbarkeit in einem Multihop-Netzwerk und damit einem WMN zu ermöglichen, sind hierarchische Strukturen von Nöten, die die Netzwerktopologie abstrahieren und Aufgaben, wie Routing, effizient ermöglichen [GK00].
Clustering (Häufung) ist ein solcher Prozess, der das Netzwerk in eine abstrahierte Hierarchie überführt [YC05]. Hierbei werden Knoten zu einem Cluster (Ansammlung) zusammengefasst, wodurch die Topologie des Netzwerks kompakter erscheint. Dieser Schritt kann mehrmals auf die jeweils entstandene Cluster-Struktur angewandt werden, um den gewünschten Abstraktionsgrad zu erreichen. Die aus der Cluster-Bildung induzierte Hierarchie ermöglicht die effiziente Nutzung vieler Anwendungen in Ad-Hoc-Netzwerken, wie beispielsweise hierarchisches Routing, die effiziente Nutzung eines limitierten Frequenzspektrums oder die Verbesserung von Dienstsuche-Verfahren (vgl. Abschnitt 3.3).
Zusammenfassung der Kapitel
1. Einführung: Diese Arbeit analysiert die Notwendigkeit von hierarchischen Strukturen in Wireless-Mesh-Netzwerken und definiert das Ziel, effiziente, anpassungsfähige Clustering-Verfahren zu entwickeln.
2. Wireless-Mesh-Netzwerke: Das Kapitel erläutert die Grundlagen, Architekturen (Infrastruktur-, Client-, Hybrid-WMNs) sowie Routingverfahren (OLSR, DSR, ZRP) und Abgrenzungen zu MANETs.
3. Clustering: Es werden Konzepte wie Dominating Sets vorgestellt und der aktuelle Forschungsstand von Cluster-Algorithmen in Ad-Hoc-Netzwerken sowie deren Anwendungsfelder diskutiert.
4. Theoretische Ausarbeitung: Hier werden neue Metriken für Stabilität und Verbindungsqualität sowie die darauf aufbauenden, distanzadaptiven Clustering-Algorithmen (Lowest-ID, Max-Score, Elite-Rating) theoretisch hergeleitet.
5. Praktische Ausarbeitung: Dieses Kapitel behandelt die Implementierung der entwickelten Verfahren in der Architektur Fleximsd sowie die Anwendung zur Dienstsuche mittels Relayd.
6. Auswertung: Die entwickelten Algorithmen werden anhand umfangreicher Messungen im UMIC-Testbed hinsichtlich Stabilität, Overhead und Dienstsuche-Performance evaluiert.
7. Zusammenfassung und Ausblick: Diese Kapitel fassen die erzielten Ergebnisse zusammen und geben eine Einschätzung über zukünftige Forschungsrichtungen.
Schlüsselwörter
Wireless-Mesh-Netzwerk, WMN, Clustering, Cluster-Head, Superknoten, Routing, Service Discovery, Relayd, Fleximsd, Stabilität, Netzwerktopologie, Multihop, Distanzadaption, Nachbarschaftsstabilität, Ad-Hoc-Netzwerke.
Häufig gestellte Fragen
Worum geht es in dieser Arbeit grundsätzlich?
Die Diplomarbeit befasst sich mit der Entwicklung und Evaluierung von effizienten, stabilitätsorientierten Clustering-Verfahren für Wireless-Mesh-Netzwerke, um deren Skalierbarkeit und Verwaltungsaufwand zu optimieren.
Was sind die zentralen Themenfelder?
Zentrale Themen sind die Netzwerktopologie-Strukturierung durch Clustering, die adaptive Anpassung von Distanzparametern in Mesh-Netzwerken sowie die praktische Implementierung dieser Ansätze für Anwendungen wie die Dienstsuche.
Was ist das primäre Ziel oder die Forschungsfrage?
Ziel ist es, Clustering-Algorithmen zu entwickeln, die das stabile Grundgerüst von Wireless-Mesh-Netzwerken ausnutzen und sich automatisch an dynamische Netzwerkeigenschaften anpassen, um eine hohe Stabilität bei gleichzeitig reduziertem Verwaltungsaufwand zu erreichen.
Welche wissenschaftliche Methode wird verwendet?
Die Arbeit kombiniert theoretische Analysen und mathematische Modellierungen der Algorithmen mit einer empirischen Evaluation in einem realen Testbed (UMIC-Testbed), um die Performance unter variierenden Netzbedingungen zu messen.
Was wird im Hauptteil behandelt?
Der Hauptteil umfasst die theoretische Herleitung von Metriken (z.B. Nachbarschaftsstabilität, Connection-Rating) sowie der darauf basierenden Clustering-Algorithmen, gefolgt von einer detaillierten Beschreibung der Implementierung in der Software Fleximsd.
Welche Schlüsselwörter charakterisieren die Arbeit?
Wichtige Begriffe sind Wireless-Mesh-Netzwerke, Clustering, Dienstsuche (Service Discovery), Stabilität, Adaptive Distanzierung und die Software-Plattform Fleximsd.
Wie unterscheidet sich der Elite-Rating Algorithmus von anderen Ansätzen?
Der Elite-Rating-Algorithmus legt einen besonderen Schwerpunkt auf die Verbindungsqualität zwischen Cluster-Head und Cluster-Member, indem er Connection-Rating-Werte in die Auswahl der Cluster-Kandidaten einbezieht.
Welchen Einfluss hat die Maximal-Distanz auf das Netzwerk?
Die Untersuchung zeigt, dass höhere Maximal-Distanzen die Nachbarschaftsstabilität und Konnektivität tendenziell verbessern, jedoch bei sehr hohen Werten zu einem quadratisch steigenden Nachrichtenaufwand im Netzwerk führen.
- Citation du texte
- André Stein (Auteur), 2010, Adaptives Clustering in Wireless-Mesh-Netzwerken, Munich, GRIN Verlag, https://www.grin.com/document/147213
