Teilprojekt A4
From GRK-Wiki
zum übergeordneten Forschungsbereich
Contents |
Partitionierungen in selbstorganisierenden Netzen
Eine Vorkonfiguration der Knoten vor ihrer Einbindung in eine bestehende selbstorganisierende Netzkonfiguration ist im Allgemeinen nicht erforderlich – das Routing der Nachrichten wird verteilt gelöst. Die wissenschaftlich-technische Herausforderung besteht darin, einen temporären oder permanenten Ausfall von Knoten durch andere Knoten zu kompensieren, um die Netzfunktionalität erhalten zu können. Die Forschung konzentriert sich dabei auf das Problem, Schwachstellen der selbstorganisierenden Netze zu vermeiden und die Konnektivität des Netzes zu sichern. Eine nicht gewünschte Netzwerkpartitionierung kann verschiedene Gründe haben: Herunterfahren eines Gerätes, Ausfall der Stromversorgung, Umstellung/Bewegung eines Knotens oder physikalische Zerstörung von Knoten (z. B. beim Erdbeben). Geschieht dies, so gibt es ernste Probleme im Hinblick auf die gewünschte Netzfunktionalität: Knoten aus verschiedenen Teilen des Netzes können nicht mehr miteinander kommunizieren, die Qualität aller Dienste im Netz ist reduziert oder Dienste können sogar ganz ausfallen. Wenn die Dichte der Knoten im Beobachtungsgebiet zu niedrig ausfällt, ist es sogar möglich, dass das Netz seine volle Konnektivität nie wieder erlangen kann. Das schlechteste Szenario besteht darin, dass ein Netz mit geringer Knotendichte durch eine Reihe von Partitionierungen in eine nicht verbundene Menge von Netzen aus je einem Knoten zerfällt.
Stand des Wissens
Probleme der Vorhersage von Partitionierungen und der Wiederherstellung der Konnektivität in selbstorganisierenden Netzen werden in der Forschung noch wenig betrachtet. Meist wird angenommen, dass ein partitioniertes Netz seine Konnektivität von selbst wieder erlangt. Dies funktioniert nur, wenn die Dichte der Knoten hoch genug ist. Aktuell wird das Partitionierungsproblem mit verschiedenen Ansätzen bearbeitet, die auf Grundlage von Vorhersageverfahren funktionieren. Jedoch haben die meisten von ihnen Probleme hinsichtlich der Skalierbarkeit, benötigen zentralisierte Lösungen, globales Wissen über das Netz, fluten das Netz intensiv. Hauspie u. a. [1] schlagen ein Modell vor, in dem alle nicht zusammenhängenden Pfade zwischen Quelle und Ziel erzeugt werden und dann die Robustheit der Pfade anhand der Ausfallwahrscheinlichkeit der einzelnen Verbindungen berechnet wird. Das Modell erfordert globales Wissen über die Topologie des Netzes. Goyal and Caffery [2] benutzen ein Modell, in das Wissen über die Lokalisierung einfließt und in dem kritische (hinsichtlich der Netzfunktionalität wichtige) Wege im Netz mithilfe einer Tiefensuche ermittelt werden. Die Knoten des Netzes benötigen nur Informationen über ihre jeweiligen Nachbarn und müssen den Tiefensuchbaum periodisch berechnen, womit das Netz auch dann geflutet wird, wenn dafür keine Notwendigkeit besteht. Ou u.a. führen in [3] Hilfsknoten ein, die benutzt werden, um kritische Verbindungen zu unterstützen und damit Partitionierungen zu vermeiden. Die Autoren benutzen drei einfache Modelle mit vordefinierten Bewegungen der Knoten (statische Hilfsknoten, sich zufällig bewegende Hilfsknoten und sich kreisförmig bewegende Knoten) und ein Modell, in dem den Hilfsknoten Informationen über die Lokalisierung zur Verfügung stehen und so den Netzverkehr beobachten und sich dorthin bewegen, wo der Netzverkehr beeinflusst werden kann. Der Nachteil dieser Methode ist, dass die Hilfsknoten nicht nach Bedarf agieren, sondern sich nach vordefinierten Mustern bewegen. Ferner ist eine signifikante Verbesserung der Leistung des Netzes nur dann zu beobachten, wenn die Anzahl der Hilfsknoten an die Anzahl der unabhängigen Knoten heranreicht, was den Ansatz unpraktisch und teuer macht.
Vorarbeiten der beteiligten Forscher
Als ein Ausgangspunkt für das Dissertationsvorhaben werden neue Modelle für MANETs aus der Forschung von M. Malek eingebracht [4]. Umfangreiche Erfahrungen auf dem Gebiet großer selbstorganisierender Netze existieren in der Arbeitsgruppe Systemarchitektur durch das Berlin Roof Net-Projekt [5] sowie durch Projekte im Forschungslabor der Firma NEC in Princeton/USA, bei dem J.- P. Redlich bis zu seiner Berufung im Sommer 2004 als Department Head tätig war [6], [7]. In den Arbeiten von M. Malek wird ein selbstorganisierendes Netz als ein Graph in der euklidischen Ebene definiert, wobei die Knoten Netzknoten und die Kanten Kommunikationsverbindungen modellieren. In [8] wird beschrieben, wie jeder Knoten mit Hilfe eines Zweiphasen-Algorithmus eine Vorhersage von Partitionierungen berechnen kann. Wenn zwei Knoten zu dem Schluss kommen, dass die Verbindung zwischen ihnen zusammenbricht (die Wahrscheinlichkeit überschreitet einen bestimmten Schwellwert), lösen sie eine Replikation von Daten aus, um ein Weiterarbeiten der Netzeinzelteile zu ermöglichen.
Geplante Arbeiten
Um eine verlässliche selbstorganisierende Kommunikationsinfrastruktur zu erstellen, müssen Problem der Diagnose, der Partitionierung und des Wiederaufbau des Netzes behandelt werden. Partitionierungen müssen wenigstens vorhergesagt, besser aber vermieden werden. Wenn eine Verbindung im Netz kritisch ist, sollten die Knoten im Netz speziell gestaltet werden. Kann die Vermeidung von Partitionierungen nicht garantiert werden, dann soll das Modell eine Abschätzung der Wahrscheinlichkeit dafür liefern, dass das Netz zerfällt, so dass bei Bedarf redundante Routing-Pfade etabliert werden können.
Referenzen
[1] M. Hauspie, D. Simplot, J. Carle: Partition detection in ad-hoc networks using multiple disjoint paths set. In: Proc. of the 1st Int. Workshop on Objects Models and Multimedia Technologies (OMMT), Geneva, Switzerland, 2003.
[2] D. Goyal, J. Carery Jr: Partitioning avoidance in mobile ad hoc networks using network survivability concepts. In: International Symposium on Computer and Communications (ISCC), Sicily, 2002.
[3] C. Ou., K. Ssu, H. C.Jiau: Connecting network partitions with location-assisted forwarding nodes in mobile ad hoc environments. In: Proc. of the 10th IEEE Pacific Rim International Symposium on Dependable Computing (PRDC ‘04), Papeete, Tahiti, 2004.
[4] N. Milanovic, M. Malek. A. Davidson, V. Milutinovic: Routing and Security in Mobile Ad Hoc Networks. IEEE Computer, February 2004.
[5] Berlin Roof Net Projekt. http://sarwiki.informatik.hu-berlin.de/BerlinRoofNet.
[6] Z. Haas, J. P. Redlich: SOSAETI- Self-Organizing, Secure, wireless Access nETwork Infrastructure. NEC-Internal REPORT, Report No: 2004-L010, March 2004.
[7] R. D. Gitlin, J. P. Redlich, E. Shim: Secure Candidate Access Router Discovery. NEC-Internal REPORT, Report No: 2002-C032, July 2002.
[8] B. Milic, N. Milanovic, M. Malek: Prediction of partitioning in location-aware mobile ad hoc networks. In Hawaii International Conference on System Sciences (HICSS-38), USA, 2005.
