TU Darmstadt / ULB / TUprints

Correct-by-Construction Development of Dynamic Topology Control Algorithms

Speith, Roland (2018)
Correct-by-Construction Development of Dynamic Topology Control Algorithms.
Technische Universität Darmstadt
Ph.D. Thesis, Primary publication

[img]
Preview
2019-03-14_Speith_Roland - Text
2019-03-14_Speith_Roland.pdf - Accepted Version
Copyright Information: CC BY-SA 4.0 International - Creative Commons, Attribution ShareAlike.

Download (10MB) | Preview
Item Type: Ph.D. Thesis
Type of entry: Primary publication
Title: Correct-by-Construction Development of Dynamic Topology Control Algorithms
Language: English
Referees: Schürr, Prof. Andy ; Giese, Prof. Holger
Date: 30 November 2018
Place of Publication: Darmstadt
Date of oral examination: 14 March 2019
Abstract:

Wireless devices are influencing our everyday lives today and will even more so in the future. A wireless sensor network (WSN) consists of dozens to hundreds of small, cheap, battery-powered, resource-constrained sensor devices (motes) that cooperate to serve a common purpose. These networks are applied in safety- and security-critical areas (e.g., e-health, intrusion detection). The topology of such a system is an attributed graph consisting of nodes representing the devices and edges representing the communication links between devices. Topology control (TC) improves the energy consumption behavior of a WSN by blocking costly links. This allows a mote to reduce its transmission power. A TC algorithm must fulfill important consistency properties (e.g., that the resulting topology is connected). The traditional development process for TC algorithms only considers consistency properties during the initial specification phase. The actual implementation is carried out manually, which is error prone and time consuming. Thus, it is difficult to verify that the implementation fulfills the required consistency properties. The problem becomes even more severe if the development process is iterative. Additionally, many TC algorithms are batch algorithms, which process the entire topology, irrespective of the extent of the topology modifications since the last execution. Therefore, dynamic TC is desirable, which reacts to change events of the topology.

In this thesis, we propose a model-driven correct-by-construction methodology for developing dynamic TC algorithms. We model local consistency properties using graph constraints and global consistency properties using second-order logic. Graph transformation rules capture the different types of topology modifications. To specify the control flow of a TC algorithm, we employ the programmed graph transformation language story-driven modeling. We presume that local consistency properties jointly imply the global consistency properties. We ensure the fulfillment of the local consistency properties by synthesizing weakest preconditions for each rule. The synthesized preconditions prohibit the application of a rule if and only if the application would lead to a violation of a consistency property. Still, this restriction is infeasible for topology modifications that need to be executed in any case. Therefore, as a major contribution of this thesis, we propose the anticipation loop synthesis algorithm, which transforms the synthesized preconditions into routines that anticipate all violations of these preconditions. This algorithm also enables the correct-by-construction runtime reconfiguration of adaptive WSNs. We provide tooling for both common evaluation steps. Cobolt allows to evaluate the specified TC algorithms rapidly using the network simulator Simonstrator. cMoflon generates embedded C code for hardware testbeds that build on the sensor operating system Contiki.

Alternative Abstract:
Alternative AbstractLanguage

Drahtlos kommunizierende Geräte sind ein wesentlicher Bestandteil der zunehmenden Digitalisierung unserer Gesellschaft. Ein drahtloses Sensornetzwerk (engl. Wireless Sensor Network, WSN) umfasst eine Vielzahl günstiger, kleiner, batteriebetriebener Sensoren, die gemeinschaftlich einem Ziel dienen (z.B. in einer e-Health-Anwendung). Die Topologie eines WSNs ist ein attributierter Graph, dessen Knoten die Geräte und dessen Kanten deren Kommunikationsverbindungen darstellen. Topologiekontrolle (engl. Topology Control, TC) reduziert den Energieverbrauch eines WSN, indem bestimmte physische Nachbarn eines Geräts ausgeblendet werden, wodurch sich dessen Sendeleistung reduzieren lässt. Der Topologiekontrollalgorithmus muss dabei wesentliche Konsistenzeigenschaften erhalten (z.B. den Zusammenhang des Topologie). Ungeachtet ihrer großen Bedeutung werden Konsistenzeigenschaften in der traditionellen Entwicklung von TC-Algorithmen nur in der anfänglichen Spezifikationsphase betrachtet. Die anschließende Implementierung des TC-Algorithmus wird von Hand durchgeführt und ist damit fehleranfällig und zeitaufwändig. Es ist schwierig nachzuweisen, dass die Implementierung die geforderten Konsistenzeigenschaften erfüllt, insbesondere da TC-Algorithmen typischerweise iterativ entwickelt werden. Die bestehenden Batch-TC-Algorithmen verarbeiten jeweils die gesamte Topologie ohne Wissen aus vorherigen Ausführungen zu nutzen. Daher ist es wünschenswert dynamische TC-Algorithmen zu entwicklen, die inkrementell auf Ereignisse reagieren.

In dieser Arbeit stellen wir eine modellbasierte Entwicklungsmethodik für garantiert korrekte dynamische TC-Algorithmen vor. Wir modellieren lokale Konsistenzeigenschaften mittels Graph-Constraints, globale Konsistenzeigenschaften mittels Prädikatenlogik zweiter Stufe sowie die möglichen Änderungen der Topologie und deren Kontrollfluss mittels programmierter Graphtransformationsregeln. Unter der Annahme, dass die lokalen Konsistenzbedingungen gemeinsam die globalen Konsistenzbedingungen implizieren, können wir mithilfe bestehender statischer Analysetechniken Vorbedingungen für die Graphtransformationsregeln synthetisieren, die sicherstellen, dass die modifizierten Regeln die Konsistenzbedingungen erhalten. Die resultierende Einschränkung ist für diejenigen Regeln, die das Umweltverhalten beschreiben, jedoch nicht zulässig. Wir stellen daher einen Algorithmus vor, der jede synthetisierte Vorbedingung systematisch in eine Antizipationsschleife überführt, welche alle unvermeidlichen Verletzungen der entsprechenden Vorbedingungen auflöst. Wir zeigen, dass sich dieser neuartige Algorithmus auch für die Rekonfiguration von adaptiven WSNs eignet. Um dem Nutzer unseres Ansatzes eine schnelle Erprobung eines entwickelten TC-Algorithmus zu ermöglichen, bieten wir Werkzeuge zur Evaluation im Netzwerksimulator (Cobolt) und Hardware-Testbed (cMoflon) an.

German
URN: urn:nbn:de:tuda-tuprints-85627
Classification DDC: 000 Generalities, computers, information > 004 Computer science
Divisions: 18 Department of Electrical Engineering and Information Technology > Institute of Computer Engineering > Real-Time Systems
DFG-Collaborative Research Centres (incl. Transregio) > Collaborative Research Centres > CRC 1053: MAKI – Multi-Mechanisms Adaptation for the Future Internet > A: Construction Methodology > Subproject A1: Modelling
Date Deposited: 04 Apr 2019 12:19
Last Modified: 09 Jul 2020 02:33
URI: https://tuprints.ulb.tu-darmstadt.de/id/eprint/8562
PPN: 447207822
Export:
Actions (login required)
View Item View Item