The flooding time synchronization protocol

ABSTRACT

Wireless sensor network applications, similarly to other distributed systems, often require a scalable time synchronization service enabling data consistency and coordination. This paper describes the Flooding Time Synchronization Protocol (FTSP), especially tailored for applications requiring stringent precision on resource limited wireless platforms. The proposed time synchronization protocol uses low communication bandwidth and it is robust against node and link failures. The FTSP achieves its robustness by utilizing periodic flooding of synchronization messages, and implicit dynamic topology update. The unique high precision performance is reached by utilizing MAC-layer time-stamping and comprehensive error compensation including clock skew estimation. The sources of delays and uncertainties in message transmission are analyzed in detail and techniques are presented to mitigate their effects. The FTSP was implemented on the Berkeley Mica2 platform and evaluated in a 60-node, multi-hop setup. The average per-hop synchronization error was in the one microsecond range, which is markedly better than that of the existing RBS and TPSN algorithms.

REFERENCES

• 1: Jeremy Eric Elson , Deborah L. Estrin, Time synchronization in wireless sensor networks, 2003
• 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 L. Hill , David E. Culler, Mica: A Wireless Platform for Deeply Embedded Networks, IEEE Micro, v.22 n.6, p.12-24, November 2002 [doi>10.1109/MM.2002.1134340]
• 5: Horauer, M. et. al. PSynUTC - Evaluation of a High Precision Time Synchronization Prototype System for Ethernet LANs. 34th Annual Precise Time and Time Interval Meeting (PTTI), December 2002.
• 6: J. M. Kahn , R. H. Katz , K. S. J. Pister, Next century challenges: mobile networking for “Smart Dust”, Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking, p.271-278, August 15-19, 1999, Seattle, Washington, United States [doi>10.1145/313451.313558]
• 7: H. Kopetz , W. Ochsenreiter, Clock synchronization in distributed real-time systems, IEEE Transactions on Computers, v.36 n.8, p.933-940, Aug. 1987 [doi>10.1109/TC.1987.5009516]
• 8: Kopetz, H., and Schwabl, W. Global time in distributed real-time systems. Technical Report 15/89, Technische Universitat Wien, 1989.
• 9: Alan Mainwaring , David Culler , Joseph Polastre , Robert Szewczyk , John Anderson, Wireless sensor networks for habitat monitoring, Proceedings of the 1st ACM international workshop on Wireless sensor networks and applications, September 28-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570738.570751]
• 10: Miklos Maroti , Gyula Simon , Akos Ledeczi , Janos Sztipanovits, Shooter Localization in Urban Terrain, Computer, v.37 n.8, p.60-61, August 2004 [doi>10.1109/MC.2004.104]
• 11: Mills, D. L. Internet Time Synchronization: The Network Time Protocol. IEEE Transactions on Communications COM 39 no. 10, p. 1482--1493, October 1991.
• 12: Loren Schwiebert , Sandeep K.S. Gupta , Jennifer Weinmann, Research challenges in wireless networks of biomedical sensors, Proceedings of the 7th annual international conference on Mobile computing and networking, p.151-165, July 2001, Rome, Italy [doi>10.1145/381677.381692]
• 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: Mani Srivastava , Richard Muntz , Miodrag Potkonjak, Smart kindergarten: sensor-based wireless networks for smart developmental problem-solving enviroments, Proceedings of the 7th annual international conference on Mobile computing and networking, p.132-138, July 2001, Rome, Italy [doi>10.1145/381677.381690]
• 15: Yang, H., and Sikdar, B. A Protocol for Tracking Mobile Targets using Sensor Networks. IEEE Workshop on Sensor Network Protocols and Applications, May 2003.
• 16: Alec Woo , David E. Culler, A transmission control scheme for media access in sensor networks, Proceedings of the 7th annual international conference on Mobile computing and networking, p.221-235, July 2001, Rome, Italy [doi>10.1145/381677.381699]
• 17: TinyOS, http://webs.cs.berkeley.edu/tos/
• 18: http://cvs.sourceforge.net/viewcvs.py/tinyos/minitasks/02/vu/tos/lib/TimeSync/
• 19: Mica2 and Mica2Dot: http://www.xbow.com/Products/Wireless_Sensor_Networks.htm

INDEX TERMS

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

General Terms:
Algorithms, Design, Experimentation, Performance, Reliability

Keywords:
clock drift, clock synchronization, multi-hop, sensor networks, time synchronization