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.

• SYNC: We 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 also investigated other types of decentralized synchronization algorithms that use the same basic principles, but converge more quickly.

• DESYNC: We have also shown how one can adapt these principles to generate another useful timing pattern -- desynchronization -- where the nodes attempt to flash in a perfect round-robin pattern so as not to interfere with their neighbors. We have used DESYNC to design a self-repairing TDMA scheme for collision-free wireless transmissions, where 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 conducted preliminary studies on 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 old group at Harvard and Jason Redi/Prithwish Basu's group at BBN. Prior to that, Nagpal also worked Bachrach/Shrobe at MIT on localization in wireless sensor networks. 

Although we no longer work in this area, there are still many open challenges to solve. For more recent work, see work by Anna Scaglione's group at Cornell on synchronization/desync in wireless networks (e.g. Pagliari, Hong, Scaglioni, BodyNets, 2009). Also closely related is 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 papers and book SYNC by Steven Strogatz at Cornell to get a bigger picture of the theory and widespread occurrence of decentralized synchronization.