Selforganizing 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 selforganizing algorithms for
sensor networks, that can easily adapt to errors, changes in topology,
and changes in usage. We have shown how fireflyinspired
synchronization (pulsecoupled oscillator models) can be adapted to
solve different types of problems in adhoc wireless sensor networks.

We have adapted the MirolloStrogatz model of firefly sychronization to work on wireless sensor
networks where there are message delays, clock skew, and frequent
topology changes. This algorithm (RFAsync) was implemented on the
MicaZ motes and tested on the buildingwide 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 roundrobin so as not to interfere with their
neighbors. We have used DESYNC to design a selfrepairing TDMA scheme
for collisionfree 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 multihop 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
TinyOSbased 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
Matlabbased application (by Julius Degesys) for visualizing the
behavior of different pulsecoupled oscillator algorithms on multihop
network topologies. Currently this code implements MirolloStrogatz,
RefSync, and Desync, however you can download it and modify it to
study other algorithms. Julius Degesys and Ian Rose implemented DESYNC
and DESYNCTDMA 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

FireflyInspired Sensor Network Synchronicity with Realistic Radio Effects ,
Geoff WernerAllen, Geetika Tewari, Ankit Patel, Matt Welsh, Radhika Nagpal, SENSYS, 2005.
(pdf)
In this paper, we developed a bioinspired synchronization
algorithm, called Reachback Firefly Algorithm (RFAsync), 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 30node mote based network.

DESYNC: SelfOrganizing 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 roundrobin 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 DESYNCTDMA is able to achieve near
perfect bandwidth utilization with no message loss, in both high and
low load situations. This work focussed only on singlehop networks.

Desynchronization: The Theory of SelfOrganizing Algorithms for RoundRobin Scheduling
Ankit Patel, Julius Degesys, Radhika Nagpal, SASO, 2007.
(pdf)
Towards Desynchronization of Multihop 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 singlehop networks, and
discusses two distinct solutions: DESYNC and
inverseMirolloStrogatz. The second paper presents some initial
alanysis of desynchronization and possible stable states in multihop
networks, and discusses the relationship to graph coloring. This work
is a step towards implementing a DESYNCbased selfrepairing TDMA for
multihop 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 mirollostrogatz model of fireflies
synchronizes on multihop 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.
