Adaptives Clustering in Wireless-Mesh-Netzwerken

Diplomarbeit , 2010 , 119 Seiten , Note: 1.0

Informatik - Angewandte Informatik

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 und Themenschwerpunkte

Diese Diplomarbeit beschäftigt sich mit dem Einsatz adaptiver Clustering-Techniken in Wireless-Mesh-Netzwerken. Das Ziel ist die Entwicklung einer stabilen und effizienten Cluster-Infrastruktur, die sich dynamisch an sich ändernde Netzwerkbedingungen anpassen kann.

• Adaptive Cluster-Infrastrukturen in Wireless-Mesh-Netzwerken
• Distanzadaptive Algorithmen zur Optimierung der Cluster-Bildung
• Verbesserung der Stabilität und Zuverlässigkeit von Cluster-Strukturen
• Praktische Implementierung und Evaluierung der entwickelten Ansätze
• Anwendung der Cluster-Technologie in der Dienstsuche und Routing-Optimierung

Zusammenfassung der Kapitel

• Kapitel 1 führt in die Thematik der Wireless-Mesh-Netzwerke und die Problematik der Cluster-Bildung ein. Es werden die wichtigsten Konzepte und Herausforderungen im Zusammenhang mit adaptiven Cluster-Infrastrukturen vorgestellt.
• Kapitel 2 befasst sich mit der Architektur von Wireless-Mesh-Netzwerken, ihren verschiedenen Arten und den Unterschieden zu Mobile Ad-hoc Networks (MANETs). Es werden verschiedene Routing-Protokolle und deren Einsatzmöglichkeiten in Wireless-Mesh-Netzwerken diskutiert.
• Kapitel 3 liefert eine Einführung in die Grundlagen des Clusterings und seine Anwendung in verschiedenen Bereichen. Es werden verschiedene Clustering-Verfahren für Ad-Hoc-Netzwerke vorgestellt und ihre Eigenschaften und Einsatzmöglichkeiten diskutiert.
• Kapitel 4 befasst sich mit der theoretischen Ausarbeitung von Metriken zur Bewertung der Stabilität und Effizienz von Cluster-Strukturen. Es werden verschiedene Clustering-Algorithmen und Distanzadaptive Algorithmen vorgestellt und analysiert.
• Kapitel 5 präsentiert die praktische Ausarbeitung der entwickelten Ansätze. Es werden die Implementierungen der entwickelten Clustering- und Distanzadaptiven Algorithmen in den Prototypen Fleximsd und Relayd beschrieben.

Schlüsselwörter

Wireless-Mesh-Netzwerke, Clustering, adaptive Cluster-Infrastrukturen, Distanzadaptive Algorithmen, Stabilität, Zuverlässigkeit, Dienstsuche, Routing, Prototypen, Fleximsd, Relayd, UMIC-Testbed

• Hochschule: Rheinisch-Westfälische Technische Hochschule Aachen
• Note: 1.0
• Autor: André Stein (Autor:in)
• Erscheinungsjahr: 2010
• Seiten: 119
• Katalognummer: V147213
• ISBN (eBook): 9783640583027
• ISBN (Buch): 9783640583485
• Sprache: Deutsch
• Schlagworte: informatik, wireless-mesh-netzwerk, ad-hoc-netzwerk, clustering, praktische informatik