Gerry Siegemund

Abstract: This article presents a middleware that provides a communication and data dissemination infrastructure suitable for the operation environment of the Internet of Things (IoT). The middleware realizes the channel-based publish/subscribe paradigm that has been identified as a valid means to asynchronously disseminate data in IoT applications. The novelty lies in the routing algorithm PSVR that greatly reduces the path lengths to deliver publications and its suitability for scenarios with a high subfluctuation rate. The middleware is self-stabilizing and eventually provides safety and liveness properties such as the guaranteed delivery of all published messages to all subscribers and the correct handling of subscriptions and unsubscriptions, while no error occurs. The evaluation of the middleware, based on simulations and a real deployment, shows that it has a low memory footprint and scales well with the number of nodes.

Abstract: The loose coupling and the inherent scalability make publish/subscribe systems an ideal candidate for event-driven services for wireless networks using low power protocols such as IEEE 802.15.4. This work introduces a distributed algorithm to build and maintain a routing structure for such networks.The algorithm dynamically maintains a multicast tree for each node. While previous work focused on minimizing these trees we aim to keep the effort to maintain them in case of fluctuations of subscribers low. The multicast trees are implicitly defined by a novel structure called augmented virtual ring. The main contribution is a distributed algorithm to build and maintain this augmented virtual ring. Maintenance operations after sub-and unsubscriptions require message exchange in a limited region only. We compare the average lengths of the constructed forwarding paths with an almost ideal approach. As a result of independent interest we present a distributed algorithm using messages of size O(logn) for constructing virtual rings of graphs that are on average shorter than rings based on depth first search.

Abstract: The presented dissertation focuses on the applicability of self-stabilizing algorithms in systems using wireless communication. Especially wireless sensor networks (WSN) which use low power radios that are prone to message loss and corruption. Furthermore, temporary node failures (e.g., due to exhausted batteries) are common sources of nonconformances. Thus, distributed algorithms, middleware systems, and applications have to respond to these faults. A typical approach is to foresee such error situations and program routines to react to them. Algorithms defined in a self-stabilizing manner (SSA) on the other hand always converge to a defined system state and remain in it while no fault occurs. Hence, the anticipation of error situations is no longer a necessity. Entities in a distributed system (nodes) share certain informations among their neighborhood (adjacent nodes) and react following the distinct routine of the used SSA. To this day self-stabilization is primarily a theoretical approach, well studied concerning, e.g., the bounds of execution steps. Profound practical evaluation, especially in the presents of rapidly changing neighbor states, as common in WSNs, is still an open issue. This work firstly establishes necessities to use SSAs in the wireless domain, concluding that a certain degree of forced stability concerning a nodes neighborhood is vital. Nevertheless, such a topology control cannot be rigid, e.g., by using a fixed predefined setup, because node additions or removals cannot be supported. Hence, a topology control algorithm (TCA) is introduced, generating a trade-off between forced stability and agility. Using this TCA as a cornerstone, multiple SSAs are evaluated, and high level algorithms are developed, culminating in a publish/subscribe middleware defined in a self-stabilizing fashion. The publish/subscribe system relies on a self-stabilizing spanning tree algorithm and a novel self-stabilizing virtual ring algorithm. Further- more, the publication routing uses shortcuts in the virtual ring, decreasing routing paths in the process. The presented algorithms are evaluated using simulations employing realistic radio models, as well as implementation on sensor node hardware with low power radios, low computation power, and restricted memory. The novel publish/subscribe system is executable on such limited hardware, uses less messages to deliver data to publishers than a comparable tree-based approach, due to the mentioned shortcuts, and scales well with the network size. It achieves a compromise between the size and maintenance effort for routing tables and the length of routing paths. Concluding, the dissertation provides an incentive to use self-stabilization algorithms in wireless sensor network applications. As shown, even high level systems like a publish/subscribe middleware can be realized with this inherently fault-tolerant approach.