Self-stabilizing algorithms in wireless sensor networks

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, espe- cially 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, con- cluding 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 al- gorithms 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 pub- lishers 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 algo- rithms 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.