Fine-grained network time synchronization using reference broadcasts

ABSTRACT

Recent advances in miniaturization and low-cost, low-power design have led to active research in large-scale networks of small, wireless, low-power sensors and actuators. Time synchronization is critical in sensor networks for diverse purposes including sensor data fusion, coordinated actuation, and power-efficient duty cycling. Though the clock accuracy and precision requirements are often stricter than in traditional distributed systems, strict energy constraints limit the resources available to meet these goals.We present Reference-Broadcast Synchronization, a scheme in which nodes send reference beacons to their neighbors using physical-layer broadcasts. A reference broadcast does not contain an explicit timestamp; instead, receivers use its arrival time as a point of reference for comparing their clocks. In this paper, we use measurements from two wireless implementations to show that removing the sender's nondeterminism from the critical path in this way produces high-precision clock agreement (1.85 ± 1.28μsec, using off-the-shelf 802.11 wireless Ethernet), while using minimal energy. We also describe a novel algorithm that uses this same broadcast property to federate clocks across broadcast domains with a slow decay in precision (3.68 ± 2.57μsec after 4 hops). RBS can be used without external references, forming a precise relative timescale, or can maintain microsecond-level synchronization to an external timescale such as UTC. We show a significant improvement over the Network Time Protocol (NTP) under similar conditions.

REFERENCES

• 1: I. F. Akyildiz , W. Su , Y. Sankarasubramaniam , E. Cayirci, Wireless sensor networks: a survey, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.38 n.4, p.393-422, 15 March 2002 [doi>10.1016/S1389-1286(01)00302-4]
• 2: G. Asada, M. Dong, T.S. Lin, F. Newberg, G. Pottie, W.J. Kaiser, and H.O. Marcy. Wireless Integrated Network Sensors: Low Power Systems on a Chip. In Proceedings of the European Solid State Circuits Conference, 1998.
• 3: R.E. Beehler. Time/frequency services of the U.S. National Bureau of Standards and some alternatives for future improvement. Journal of Electronics and Telecommunications Engineers, 27:389--402, Jan 1981.
• 4: Alberto Cerpa , Jeremy Elson , Michael Hamilton , Jerry Zhao , Deborah Estrin , Lewis Girod, Habitat monitoring: application driver for wireless communications technology, Workshop on Data communication in Latin America and the Caribbean, p.20-41, April 2001, San Jose, Costa Rica [doi>10.1145/371626.371720]
• 5: Flaviu Cristian. Probabilistic clock synchronization. Distributed Computing, 3:146--158, 1989.
• 6: Jeremy Elson , Deborah Estrin, Time Synchronization for Wireless Sensor Networks, Proceedings of the 15th International Parallel & Distributed Processing Symposium, p.186, April 23-27, 2001
• 7: Saurabh Ganefiwal, Ram Kumar, Sachin Adlaldaa, and Mani B. Srivastava. Network-wide Time Synchrinization in Sensor Networks. Technical report, University of California, Dept. of Electrical Engineering, 2002.
• 8: Lewis Girod, Vladimir Bychkovskiy, Jeremy Elson, and Deborah Estrin. Locating tiny sensors in time and space: A case study. In In Proceedings of the International Conference on Computer Design (ICCD 2002), Freiburg, Germany, September 2002. http://lecs.cs.ucla.edu/Publications.
• 9: Lewis Girod and Deborah Estrin. Robust range estimation using acoustic and multimodal sensing. In Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2001), March 2001.
• 10: R. Gusella , S. Zatti, The Accuracy of the Clock Synchronization Achieved by TEMPO in Berkeley UNIX 4.3BSD, IEEE Transactions on Software Engineering, v.15 n.7, p.847-853, July 1989 [doi>10.1109/32.29484]
• 11: Jason Hill and David Culler. A wireless embedded sensor architecture for system-level optimization. Technical report, U.C. Berkeley, 2001.
• 12: 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
• 13: Chalermek Intanagonwiwat , Ramesh Govindan , Deborah Estrin, Directed diffusion: a scalable and robust communication paradigm for sensor networks, Proceedings of the 6th annual international conference on Mobile computing and networking, p.56-67, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345920]
• 14: ISO/IEC. IEEE 802.11 Standard. IEEE Standard for Information Technology, ISO/IEC 8802-11:1999(E), 1999.
• 15: 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]
• 16: Elliott D. Kaplan, editor. Understanding GPS: Principles and Applications. Artech House, 1996.
• 17: H. Kopetz and W. Schwabl. Global time in distributed real-time systems. Technical Report 15/89, Technische Universität Wien, 1989.
• 18: Leslie Lamport, Time, clocks, and the ordering of events in a distributed system, Communications of the ACM, v.21 n.7, p.558-565, July 1978 [doi>10.1145/359545.359563]
• 19: Cheng Liao , Margaret Martonosi , Douglas W. Clark, Experience with an adaptive globally-synchronizing clock algorithm, Proceedings of the eleventh annual ACM symposium on Parallel algorithms and architectures, p.106-114, June 27-30, 1999, Saint Malo, France [doi>10.1145/305619.305631]
• 20: J. Mannermaa, K. Kalliomaki, T. Mansten, and S. Turunen. Timing performance of various GPS receivers. In Proceedings of the 1999 Joint Meeting of the European Frequency and Time Forum and the IEEE International Frequency Control Symposium, pages 287--290, April 1999.
• 21: Steven McCanne and Van Jacobson. The BSD packet filter: A new architecture for user-level packet capture. In USENIX Association, editor, Proceedings of the Winter 1993 USENIX Conference: January 25--29, 1993, San Diego, California, USA, pages 259--269, Berkeley, CA, USA, Winter 1993. USENIX.
• 22: William Merrill, Lewis Girod, Jeremy Elson, Kathy Sohrabi, Fredric Newberg, and William Kaiser. Autonomous Position Location in Distributed, Embedded, Wireless Systems. In Proceedings of IEEE CAS Workshop on Wireless Communications and Networking, Pasadena, CA, September 2002. http://www.sensoria.com/publications.html.
• 23: Robert M. Metcalfe , David R. Boggs, Ethernet: distributed packet switching for local computer networks, Communications of the ACM, v.26 n.1, p.90-95, Jan. 1983 [doi>10.1145/357980.358015]
• 24: David L. Mills. Internet Time Synchronization: The Network Time Protocol. In Zhonghua Yang and T. Anthony Marsland, editors, Global States and Time in Distributed Systems. IEEE Computer Society Press, 1994.
• 25: David L. Mills, Precision synchronization of computer network clocks, ACM SIGCOMM Computer Communication Review, v.24 n.2, p.28-43, April 1994 [doi>10.1145/185595.185651]
• 26: David L. Mills, Adaptive hybrid clock discipline algorithm for the network time protocol, IEEE/ACM Transactions on Networking (TON), v.6 n.5, p.505-514, Oct. 1998 [doi>10.1109/90.731182]
• 27: Michael Mock , Reiner Frings , Edgar Nett , Spiro Trikaliotis, Continuous Clock Synchronization in Wireless Real-Time Applications, Proceedings of the 19th IEEE Symposium on Reliable Distributed Systems (SRDS'00), p.125, October 16-18, 2000
• 28: Kay Römer, Time synchronization in ad hoc networks, Proceedings of the 2nd ACM international symposium on Mobile ad hoc networking & computing, October 04-05, 2001, Long Beach, CA, USA [doi>10.1145/501436.501440]
• 29: I. Rubin. Message Delays in FDMA and TDMA Communication Channels. IEEE Trans. Communin., COM27(5):769--777, May 1979.
• 30: T. K. Srikanth , Sam Toueg, Optimal clock synchronization, Journal of the ACM (JACM), v.34 n.3, p.626-645, July 1987 [doi>10.1145/28869.28876]
• 31: Paulo Veríssimo and Luis Rodrigues. A posteriori agreement for fault-tolerant clock synchronization on broadcast networks. In Dhiraj K. Pradhan, editor, Proceedings of the 22nd Annual International Symposium on Fault-Tolerant Computing (FTCS '92), page 85, Boston, MA, July 1992. IEEE Computer Society Press.
• 32: Paulo Veríssimo, Luis Rodrigues, and Antonio Casimiro. Cesiumspray: a precise and accurate global time service for large-scale systems. Tech. Rep. NAV-TR-97-0001, Universidade de Lisboa, 1997.
• 33: John R. Vig. Introduction to Quartz Frequency Standards. Technical Report SLCET-TR-92-1, Army Research Laboratory, Electronics and Power Sources Directorate, October 1992. Available at http://www.ieee-uffc.org/freqcontrol/quartz/vig/vigtoc.htm.
• 34: H. Wang, L. Yip, D. Maniezzo, J.C. Chen, R.E. Hudson, J.Elson, and K.Yao. A Wireless Time-Synchronized COTS Sensor Platform Part II-Applications to Beamforming. In Proceedings of IEEE CAS Workshop on Wireless Communications and Networking, Pasadena, CA, September 2002. http://lecs.cs.ucla.edu/Publications.
• 35: K. Yao, R.E. Hudson, C.W. Reed, D. Chen, and F. Lorenzelli. Blind beamforming on a randomly distributed sensor array system. IEEE Journal of Selected Areas in Communications, 16(8):1555--1567, Oct 1998.

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.4 Communications Management
          Subjects: Network communication

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication
      C.2.4 Distributed Systems

  D. Software
  D.4 OPERATING SYSTEMS
      D.4.8 Performance

General Terms:
Design, Performance