Firefly-inspired sensor network synchronicity with realistic radio effects

ABSTRACT

Synchronicity is a useful abstraction in many sensor network applications. Communication scheduling, coordinated duty cycling, and time synchronization can make use of a synchronicity primitive that achieves a tight alignment of individual nodes' firing phases. In this paper we present the Reachback Firefly Algorithm (RFA), a decentralized synchronicity algorithm implemented on TinyOS-based motes. Our algorithm is based on a mathematical model that describes how fireflies and neurons spontaneously synchronize. Previous work has assumed idealized nodes and not considered realistic effects of sensor network communication, such as message delays and loss. Our algorithm accounts for these effects by allowing nodes to use delayed information from the past to adjust the future firing phase. We present an evaluation of RFA that proceeds on three fronts. First, we prove the convergence of our algorithm in simple cases and predict the effect of parameter choices. Second, we leverage the TinyOS simulator to investigate the effects of varying parameter choice and network topology. Finally, we present results obtained on an indoor sensor network testbed demonstrating that our algorithm can synchronize sensor network devices to within 100 μsec on a real multi-hop topology with links of varying quality.

REFERENCES

• 1: Center for Information Technology Research in the Interest of Society. Smart buildings admit their faults. http://www.citris.berkeley.edu/applications/disaster_response/smartbuil%dings.html, 2002.
• 2: Jeremy Elson , Lewis Girod , Deborah Estrin, Fine-grained network time synchronization using reference broadcasts, Proceedings of the 5th symposium on Operating systems design and implementation

  Due to copyright restrictions we are not able to make the PDFs for this conference available for downloading

  , December 09-11, 2002, Boston, Massachusetts [doi>10.1145/1060289.1060304]
• 3: Saurabh Ganeriwal , Ram Kumar , Mani B. Srivastava, Timing-sync protocol for sensor networks, Proceedings of the 1st international conference on Embedded networked sensor systems, November 05-07, 2003, Los Angeles, California, USA [doi>10.1145/958491.958508]
• 4: Jason Hill , Robert Szewczyk , Alec Woo , Seth Hollar , David Culler , Kristofer Pister, System architecture directions for networked sensors, Proceedings of the ninth international conference on Architectural support for programming languages and operating systems, p.93-104, November 2000, Cambridge, Massachusetts, United States
• 5: Y. Hong, L. Cheow, and A. Scaglione. A simple method to reach detection consensus in massively distributed sensor networks. In IEEE Intl Symposium on Information Theory, ISIT'04, June 2004.
• 6: Y. Hong and A. Scaglione. Time synchronization with pulse-coupled oscillators for uwb wireless ad hoc networks. In IEEE Conf. on Ultra Wideband Systems and Technologies, Nov 2003.
• 7: Philip Levis , Nelson Lee , Matt Welsh , David Culler, TOSSIM: accurate and scalable simulation of entire tinyOS applications, Proceedings of the 1st international conference on Embedded networked sensor systems, November 05-07, 2003, Los Angeles, California, USA [doi>10.1145/958491.958506]
• 8: Dennis Lucarelli , I-Jeng Wang, Decentralized synchronization protocols with nearest neighbor communication, Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA [doi>10.1145/1031495.1031503]
• 9: Miklós Maróti , Branislav Kusy , Gyula Simon , Ákos Lédeczi, The flooding time synchronization protocol, Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA [doi>10.1145/1031495.1031501]
• 10: Renato E. Mirollo , Steven H. Strogatz, Synchronization of pulse-coupled biological oscillators, SIAM Journal on Applied Mathematics, v.50 n.6, p.1645-1662, Dec. 1990 [doi>10.1137/0150098]
• 11: C. S. Peskin. Mathematical Aspects of Heart Physiology. New York University, New York, 1975.
• 12: Curt Schurgers , Vlasios Tsiatsis , Saurabh Ganeriwal , Mani Srivastava, Topology management for sensor networks: exploiting latency and density, Proceedings of the 3rd ACM international symposium on Mobile ad hoc networking & computing, June 09-11, 2002, Lausanne, Switzerland [doi>10.1145/513800.513817]
• 13: Gyula Simon , Miklós Maróti , Ákos Lédeczi , György Balogh , Branislav Kusy , András Nádas , Gábor Pap , János Sallai , Ken Frampton, Sensor network-based countersniper system, Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA [doi>10.1145/1031495.1031497]
• 14: N. Wakamiya and M. Murata. Scalable and robust scheme for data fusion in sensor networks. In Intl Workshop on Biologically Inspired Approaches to Advanced Information Technology, Jan 2004.
• 15: G. Werner-Allen, J. Johnson, M. Ruiz, J. Lees, and M. Welsh. Monitoring volcanic eruptions with a wireless sensor network. In Proc. European Workshop on Wireless Sensor Networks (EWSN'05), Jan 2005.
• 16: G. Werner-Allen, P. Swieskowski, and M. Welsh. MoteLab : A wireless sensor network testbed. In Proc. IPSN'05, Special Track on Platform Tools and Design Methods (SPOTS), April 2005.
• 17: I. Wokoma , I. Liabotis , O. Prnjat , L. Sacks , I. Marshall, A Weakly Coupled Adaptive Gossip Protocol for Application Level Active Networks, Proceedings of the 3rd International Workshop on Policies for Distributed Systems and Networks (POLICY'02), p.244, June 05-07, 2002
• 18: W. Ye, J. Heidemann, and D. Estrin. An energy-efficient MAC protocol for wireless sensor networks. In Proc. IEEE INFOCOM '02, June 2002.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS

General Terms:
Algorithms, Design, Experimentation, Theory

Keywords:
biologically inspired algorithms, pulse-coupled oscillators, synchronization, wireless sensor networks