in Wireless Sensor Networks
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
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.
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
- Matlab GUI Simulator for Sync and Desync
- TinyOS code for Desync
Firefly-Inspired Sensor Network Synchronicity with Realistic Radio Effects ,
Geoff Werner-Allen, Geetika Tewari, Ankit Patel, Matt Welsh, Radhika Nagpal, SENSYS, 2005.
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.
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.
Towards Desynchronization of Multi-hop Topologies.
Julius Degesys and Radhika Nagpal, SASO, 2008.
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
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.