A01: Modeling

Graph-based models belong to the standard set of “tools” of the communication system research community. They are – among other things – often used for the abstract description of topologies with the term “topology” being interpreted in two different ways: On one hand a topology is a communication network that consists of physical nodes (computers, smart¬phones, … ) as well as of the communication channels between them. On the other hand a topology is a network of functional units, which realize a specific communication mechanism, including the logical links between them.

Subproject A01 has a focus on the following fundamental research challenge of MAKI: the systematic development of distributed and self-organizing adaptation mechanisms for communication system topologies as introduced above. For this purpose the following process is developed:

• First of all, studied topologies are modeled as attributed graphs with additional integrity constraints and optimization goals in mind; optimization goals are defined in the form of communication-system-specific metrics.

• Then, correlations between these metrics and structural properties of the above introduced classes of graphs are studied. For this purpose graph patterns are defined, which characterize classes of subgraphs with common structural properties; a distinction is made between undesirable anti-patterns and desirable (goal) patterns from the point of view of the developed topology optimization process. A simple example of an anti-pattern is a wireless communication system subtopology that is a triangle, where one of the involved edges is considerably “longer” than the other edges. This connection can be removed, i.e. the involved nodes may reduce their signal range accordingly and thus reduce their energy consumption.

• Afterwards, topology optimization steps are specified in the form of graph transformation rules, which successively identify unwanted anti-patterns and replace them by appropriate desirable (goal) patterns. These graph-transformations may be used for the simulation-based validation of new optimization strategies as well as for the formal verification of integrity constraint preservation properties of the thus developed adaptation algorithms.

• Finally, the rule-based adaptation algorithms, which rely on the assumption of a central topology graph database and a central coordination instance, are step by step translated into so-called “Local Algorithms”.

In the ideal case Local Algorithms running on the nodes of a communication system can be developed, which are able to identify and trigger useful topology adaptations using only local knowledge of these nodes. Unfortunately, identified anti- and goal-patterns are often way too big to be recognizable using the local knowledge of a single network node only. Therefore, the degree of locality of the studied topology adaptation algorithms and the degree of fulfillment of selected optimization goals contradict each other in the general case.

In order to resolve this conflict between locality and optimality of distributed topology adaptation algorithms the following approach is used: Sequential graph transformations, which operate on a global graph data structure, are decomposed into atomic graph matching and rewriting operations that have already proven their usefulness in the context of Motif-based approaches for the distributed optimization of communication system topologies. Motifs combine the idea to enumerate, recognize, and rate all (occurrences of) all possible classes of subgraphs of a fixed size in a topology with local and distributed topology-structure-optimizing algorithms.

The development process sketched above for distributed topology adaptation mechanisms involves the following aspects:

• Formal verification techniques are used to prove that the developed optimization algorithms preserve critical structural topology graph properties.

• Prototypes of simulation tools are developed combining network simulators with graph transformation execution engines to study the effectiveness of specified topology adaptation mechanisms and the impact of certain design decisions onto selected performance parameters of a regarded class of communication networks.

• Implementations and experiments are conducted in close cooperation with other subprojects that have a focus on topology optimization techniques, too.

It is the overall aim of the above listed evaluation and validation activities to study the suitability of the developed approach in real world scenarios taking aspects like mobility of nodes, standard variations of signal strength, and calibration of parameters into account. For this purpose Phase I of subproject A01 has a focus on simulation of topology adaptations of wireless sensor networks. The simulation models needed for that purpose are developed in close cooperation with subprojects B01, B02, and C04. The resulting case study and simulation models are the core contribution of A01 to the MAKI demonstrator.

The A01 case study and the above mentioned related evaluation efforts are essential for the planning process of Phase II and III of the overall MAKI project. In Phase II, subproject A01 will move its focus from the validation of topology optimization algorithms by means of graph-transformation-based technologies on a simulation server cluster to the formal verification of communication system topology properties like structural integrity or stability. In Phase III, we are planning to study the model-based development of distributed implementations of topology adaptation algorithms on resource-constrained nodes that are part of huge communication system networks.

The principal investigators of subproject A01 possess complementary research profiles that are critical for the above outlined research agenda: the research group of Prof. Mühlhäuser is among other things well-known for the development of Local Algorithms that are used for the optimization of communication topologies. The research group of Prof. Schürr on the other hand has the required experiences in the domain of graph transformations.

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