Robust self-organizing pulse synchronization in wireless sensor networks

Abstract

Die enormen Fortschritte verschiedenster Technologien erfordern und ermöglichen es, dass komplizierte Architekturen in kleinere und lose gekoppelte Einheiten zerlegt werden, welche überschaubarer und kontrollierbarer sind. Ein sinnvoller Austausch und Vergleich von Beobachtungen unter diesen Einheiten erfordert die Übereinstimmung der lokalen Zeit aller Einheiten mit einer systemweiten gemeinsamen Zeitbasis. Dies ist auch eine wichtige Voraussetzung für die Implementierung von Fehlertoleranz durch Replikation und gilt neben verdrahteten verteilten Systemen ebenso für drahtlose Sensornetzwerke.<br />Zusätzlich haben Knoten innerhalb von drahtlosen Sensornetzwerken hohe Anforderungen an die effiziente Nutzung von Ressourcen und benötigen folglich ein energieeffizientes Kommunikationsprotokoll. Dies wird für gewöhnlich durch synchronisierte Schlaf-Wach-Phasen erreicht. Als Folge ist Uhrensynchronisation eine unabdingbare Notwendigkeit in nahezu allen verteilten Systemen um Komponierbarkeit, Zuverlässigkeit und zeitliche Koordination zu erreichen.<br />Diese Arbeit basiert auf einen allgemein bekannten, fehlertoleranten, verteilten Uhrensynchronisationsalgorithmus, welcher für die Anwendung in drahtlosen Sensornetzwerken modifiziert und erweitert wurde. Der modifizierte Algorithmus verbindet die Vorteile zweier unterschiedlicher Ansätze, sodass schlussendlich Selbststabilisierung in fehlerfreien Netzwerken und eine hohe Synchronisationsgenauigkeit in fehlerbehaftete Netzwerken in der Anwesenheit von maximal f<n/5 Byzantinische Knoten erreicht werden kann.<br />Selbststabilisierung im generellen Sinne beschreibt dabei die Eigenschaft eines Systems, sich selbst aus einem beliebigem Ausgangszustand in einen definierten Endzustand, also die Synchronisation aller Einheiten, zu versetzen. Der Algorithmus funktioniert weiters auch in unstrukturierten Multi-hop Netzwerken durch Ausnützung der hohen Redundanz der Kommunikationsverbindungen.<br />Verschiedenste Simulationsergebnisse in Bezug auf unterschiedliche Netzwerktopologien werden diskutiert und zeigen, dass eine annehmbare Konvergenzzeit und eine hohe netzwerkweite Synchronisationsgenauigkeit bei gleichzeitig niedriger Nachrichtenkomplexität und großen zeitlichen Verzögerungen der Nachrichtenübertragungen erreicht werden kann.<br />

Tremendous advance in technology requires and allows us to build complex architectures by decomposing it into smaller manageable and loosely coupled components. The meaningful exchange and comparison of observations among these components then requires a system wide agreement on a common notion of time. This is, for example, an important issue in the case fault tolerance is implemented by replication. Whereas many wired distributed systems provide enough capabilities in order to achieve agreement, Wireless Sensor Networks demand much higher standards of the available energy resources and consequently necessitate an energy-efficient communication protocol. This is usually achieved by synchronized sleep-wakeup schedules. As a consequence, clock synchronization in complex distributed systems is inevitable to provide composability, dependability, and temporal coordination.<br />This thesis presents a well-studied and simple fault-tolerant distributed clock synchronization algorithm which was modified for the use in sensor networks and extended in order to be self-stabilizing, i.e., independent of the initial configuration, all devices eventually become synchronized. In other words, the presented approach combines the advantage of two different synchronization algorithms. In detail, whereas the convergence to a synchronized system state is ensured in the fault-free case, synchronicity is maintained even in the presence of at most f<n/5 Byzantine nodes. The algorithm also works in unstructured multi-hop networks by exploiting the existence of redundant communication links. Several simulation results with respect to different network topologies are presented and promise an improved network-wide synchronization precision, an acceptable convergence time, energy efficiency through a low message complexity, and robustness against different kinds of faults.