Self-organizing Synchronization
and Desynchronization in Wireless Sensor Networks

Movies | Publications

The spontaneous emergence of synchronization from simple individuals has fascinated scientists for decades: thousands of pacemaker cells synchronize to create a single heartbeat, and firefly swarms synchronize their flashes to form a powerful visual beacon. One of the powerful features of these systems is that simple, decentralized node behaviors result in the whole network robustly maintaining synchronization, despite individual faults or changes in topology.

Our group is interested in how we can use inspiration from these biological systems to design simple self-organizing algorithms for sensor networks, that can easily adapt to errors, changes in topology, and changes in usage. We have shown how firefly-inspired synchronization (pulse-coupled oscillator models) can be adapted to solve different types of problems in ad-hoc wireless sensor networks.

  • We have adapted the Mirollo-Strogatz model of firefly sychronization to work on wireless sensor networks where there are message delays, clock skew, and frequent topology changes. This algorithm (RFA-sync) was implemented on the MicaZ motes and tested on the building-wide MoteLab network (SENSYS 2005). We are now investigating new types of decentralized synchronization algorithms that use the same basic principles, but converge more quickly.

  • We have also shown how one can adapt these principles to generate other useful timing patterns, such as desynchronization, where the nodes attempt to flash in a perfect round-robin so as not to interfere with their neighbors. We have used DESYNC to design a self-repairing TDMA scheme for collision-free wireless transmissions, such that the transmission schedule automatically adapts as the set of nodes changes (IPSN 2007). This TDMA scheme was demonstrated on Telos motes, where it achieves near perfect bandwidth utlization under both low and high loads. We are now investigating how the DESYNC algorithm and TDMA scheme behave in multi-hop networks, where there are close relations to problems such as graph coloring and distributed consensus.

Our group has pursued both the theoretical side (how to prove correctness/convergence) and the implementation side (using TinyOS-based motes). We collaborated with Matt Welsh's group at Harvard and Jason Redi and Prithwish Basu's group at BBN. Although we no longer work in this area, there are still many open challenges to solve.


Movies

The simulation movies were created using a Matlab-based application (by Julius Degesys) for visualizing the behavior of different pulse-coupled oscillator algorithms on multi-hop network topologies. Currently this code implements Mirollo-Strogatz, RefSync, and Desync, however you can download it and modify it to study other algorithms. Julius Degesys and Ian Rose implemented DESYNC and DESYNC-TDMA on the Telos Motes; that code is also available below. Unfortunately since the code is uite old we no longer support it.

Code

  • Matlab GUI Simulator for Sync and Desync (tar)
  • TinyOS code for Desync (tar)

Publications

  • Firefly-Inspired Sensor Network Synchronicity with Realistic Radio Effects ,
    Geoff Werner-Allen, Geetika Tewari, Ankit Patel, Matt Welsh, Radhika Nagpal, SENSYS, 2005. (pdf)

    In this paper, we developed a bio-inspired synchronization algorithm, called Reachback Firefly Algorithm (RFA-sync), where nodes operate on information 1 cycle behind in order to accomodate errors and delays. We studied this algorithm using theory and simulation, and evaluated its performance on a 30-node mote based network.

  • DESYNC: Self-Organizing Desynchronization and TDMA on Wireless Sensor Networks.
    Julius Degesys, Ian Rose, Ankit Patel, Radhika Nagpal, IPSN, 2007. (pdf)

    In this paper we showed how one can adapt biological principles for synchronization to design an algorithm for "desynchronization", i.e. periodic round-robin event timing. We used this algorithm to design an extremely simple TDMA scheme, that automatically adapts wireless slot sizes as nodes are added and removed. We showed (both theoretically, and using Telos Motes) that DESYNC-TDMA is able to achieve near perfect bandwidth utilization with no message loss, in both high and low load situations. This work focussed only on single-hop networks.

  • Desynchronization: The Theory of Self-Organizing Algorithms for Round-Robin Scheduling
    Ankit Patel, Julius Degesys, Radhika Nagpal, SASO, 2007. (pdf)
    Towards Desynchronization of Multi-hop Topologies.
    Julius Degesys and Radhika Nagpal, SASO, 2008. (pdf)

    These two papers tackle theoretical aspects of desynchronization. The first paper shows how to analyze the convergence/rate of desynchronization in single-hop networks, and discusses two distinct solutions: DESYNC and inverse-Mirollo-Strogatz. The second paper presents some initial alanysis of desynchronization and possible stable states in multi-hop networks, and discusses the relationship to graph coloring. This work is a step towards implementing a DESYNC-based self-repairing TDMA for multi-hop networks.

Related Work

See work by Scaglione's group at Cornell on synchronization for cooperative transmission in wireless networks (Hong, Scaglioni), and more recently work adapting the DESYNC protocol to new types of problems (Pagliari, Hong, Scaglioni, BodyNets, 2009). Also see work by Lucarelli and Wang (ACM SenSys 2004) on proving that the mirollo-strogatz model of fireflies synchronizes on multi-hop network topologies. Finally, see paper and book (sync) by Steven Strogatz at Cornell to get a bigger picture of the theory and widespread occurrence of decentralized synchronization.