A01: Modellierung

Graphbasierte Modelle gehören zum Standardrepertoire der Kommunikationssystemforschung. Sie werden oft zur abstrakten Beschreibung von Topologien eingesetzt. Unter Topologien verstehen wir dabei einerseits Geflechte aus physischen Rechnernetzknoten und Verbindungen in einem Kommunikationssystem, andererseits Geflechte aus Funktionseinheiten, die einen bestimmten Kommunikationsmechanismus realisieren, und deren logischen Verbindungen. Teilprojekt A01 konzentriert sich auf eine für MAKI sehr grundlegende Fragestellung: die verteilte und selbstorganisierende Adaption solcher Topologien. Hierfür wird die folgende systematische Herangehensweise entwickelt: Zunächst werden die betrachteten Topologien als attributierte Graphen mit zusätzlichen Integritätsbedingungen modelliert sowie die relevanten Optimierungsziele in Form von Metriken eingeführt. Anschließend werden die betrachteten Metriken zu strukturellen Eigenschaften der eingeführten Graphklasse in Beziehung gesetzt. Hierbei kommen „Graphmuster“ zum Einsatz, die Klassen von Subgraphen mit gemeinsamen strukturellen Eigenschaften charakterisieren; dabei werden unerwünschte – d.h. den betrachteten Optimierungszielen abträgliche – (Anti-)Muster und erwünschte Zielmuster unterschieden. Ein einfaches Beispiel für ein Antimuster in einer Verbindungstopologie für drahtlose Netze ist ein Dreieck, in dem eine der Kanten „länger“ ist als die beiden anderen Kanten. Diese Verbindung kann entfernt werden und die betroffenen Knoten können ihre Reichweiten energiesparend verringern.

Anschließend werden Topologieoptimierungen mit Graphtransformationsregeln spezifiziert, die sukzessive Antimuster durch Zielmuster ersetzen. Dann erfolgt sukzessive der Übergang vom zentral gesteuerten regelbasierten Umbau von Graphen hin zur verteilten selbstorganisierenden Adaption mit Hilfe Topologie-verändernder sogenannter Lokaler Algorithmen. Im Idealfall kann ein solcher Lokaler Algorithmus so eingesetzt werden, dass jedes der zugehörigen verteilten Softwaremodule nur aufgrund seiner lokalen Kenntnisse (Nachbarschaftsbeziehungen, etc.) Entscheidungen über Topologie-Änderungen trifft. Im Normalfall sind die gefundenen Anti- und Zielmuster aber zu groß, um rein lokal erkannt bzw. erzeugt zu werden. Damit sind die Lokalität eines Optimierungsalgorithmus und der Grad der Erreichung des Optimierungsziels im Allgemeinen konkurrierende Forschungsziele. Um beiden Zielen möglichst nahe zu kommen, werden die erarbeiteten und auf einem globalen Graphen operierenden Transformationen in atomare Basisoperationen dekomponiert, die sich bereits bei Motif-basierten Ansätzen für die lokale Optimierung von Kommunikationstopologien bewährt haben. Motifs kombinieren die Enumeration aller möglichen Graphmuster einer festen Größe in einem Kommunikationsgraphen mit lokal und verteilt operierenden strukturoptimierenden Algorithmen. Die Antragsteller dieses Teilprojekts besitzen die für diese Vorgehensweise notwendigen Fachkenntnisse: Das Fachgebiet von Prof. Mühlhäuser entwickelt seit Jahren erfolgreich Lokale Algorithmen zur Optimierung von Kommunikationstopologien; das Fachgebiet von Prof. Schürr besitzt die notwendigen Kenntnisse auf dem Gebiet der Graph-Transformationen. Parallel hierzu wird an der Evaluation der erzielten Forschungsergebnisse gearbeitet: Mit formalen Verifikationstechniken wird gezeigt, dass wichtige strukturelle Eigenschaften beim Topologie-Umbau erhalten bleiben. Mittels Simulation werden sowohl die generelle Wirksamkeit, als auch zahlreiche Leistungsparameter der entwickelten Ansätze untersucht und verglichen. Implementierungen erfolgen in enger Zusammenarbeit mit anderen Teilprojekten, die Mechanismen für spezifische Topologieoptimierungen erforschen. Hier werden Praxistauglichkeit und im Realbetrieb auftretende Effekte wie Mobilität und natürliche Signalstärken-Schwankungen untersucht sowie die Parameter der erstellten Simulationsmodelle kalibriert. In Phase I werden wir uns auf die Simulation von Topologieadaptionen konzentrieren. Dazu werden wir eine großangelegte Sensornetzfallstudie evaluieren. Die Simulationsmodelle dazu werden in Zusammenarbeit mit den Teilprojekten B01, B02 und C04 erstellt. Fallstudie und Simulationsmodelle stellen außerdem den wesentlichen Beitrag von A01 am MAKI-Demonstrator dar.

Dies ist auch wesentlich für die Vorbereitung auf Phase II und III. Dabei werden wir in Phase II den Forschungsschwerpunkt vom Einsatz graph-(transformations-)basierter Techniken bei der Simulation von Topologieoptimierungsalgorithmen auf Simulationsservern hin zur zur Verifikation von Eigenschaften, wie strukturelle Integrität oder Stabilität, entstehender Topologien verlagern. In Phase III wollen wir dann abschließen die verteilte Implementierung auf ressourcenbeschränkten Knoten in großen Kommunikationsnetzen untersuchen.

• Prof. Dr. rer. nat. Max Mühlhäuser
• Prof. Dr. rer. nat. Andy Schürr