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.
- I. F. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci. Wireless Sensor Networks: A Survey. Computer Networks, 38(4):393--422, March 2002.]] Google ScholarDigital Library
- 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.]]Google Scholar
- 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.]]Google Scholar
- Alberto Cerpa, Jeremy Elson, Deborah Estrin, Lewis Girod, Michael Hamilton, and Jerry Zhao. Habitat monitoring: Application driver for wireless communications technology. In Proceedings of the 2001 ACM SIGCOMM Workshop on Data Communications in Latin America and the Caribbean, April 2001. Available at http://www.isi.edu/scadds/papers/CostaRica-oct0l-final.ps.]] Google ScholarDigital Library
- Flaviu Cristian. Probabilistic clock synchronization. Distributed Computing, 3:146--158, 1989.]]Google ScholarDigital Library
- Jeremy Elson and Deborah Estrin. Time synchronization for wireless sensor networks. In Proceedings of the 15th International Parallel and Distributed Processing Symposium (IPDPS-01). IEEE Computer Society, April 23--27 2001.]] Google ScholarDigital Library
- 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.]]Google Scholar
- 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.]]Google ScholarDigital Library
- 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.]]Google ScholarCross Ref
- R. Gusell and S. Zatti. The accuracy of clock synchronization achieved by TEMPO in Berkeley UNIX 4.3 BSD. IEEE Transactions on Software Engineering, 15:847--853, 1989.]] Google ScholarDigital Library
- Jason Hill and David Culler. A wireless embedded sensor architecture for system-level optimization. Technical report, U.C. Berkeley, 2001.]]Google Scholar
- Jason Hill, Robert Szewczyk, Alec Woo, Seth Hollar, David Culler, and Kristofer Pister. System architecture directions for networked sensors. In Proceedings of the Ninth International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS-IX), pages 93--104, Cambridge, MA, USA, November 2000. ACM.]] Google ScholarDigital Library
- Chalermek Intanagonwiwat, Ramesh Govindan, and Deborah Estrin. Directed diffusion: A scalable and robust communication paradigm for sensor networks. In Proceedings of the Sixth Annual International Conference on Mobile Computing and Networking, pages 56--67, Boston, MA, August 2000. ACM Press.]] Google ScholarDigital Library
- ISO/IEC. IEEE 802.11 Standard. IEEE Standard for Information Technology, ISO/IEC 8802-11:1999(E), 1999.]]Google Scholar
- J.M. Kahn, R.H. Katz, and K.S.J. Pister. Next century challenges: mobile networking for Smart Dust. In Proceedings of the fifth annual ACM/IEEE international conference on Mobile computing and networking, pages 271--278, 1999.]] Google ScholarDigital Library
- Elliott D. Kaplan, editor. Understanding GPS: Principles and Applications. Artech House, 1996.]]Google Scholar
- H. Kopetz and W. Schwabl. Global time in distributed real-time systems. Technical Report 15/89, Technische Universität Wien, 1989.]]Google Scholar
- Leslie Lamport. Time, clocks, and the ordering of events in a distributed system. Communications of the ACM, 21(7):558--65, 1978.]] Google ScholarDigital Library
- Cheng Liao, Margaret Martonosi, and Douglas W. Clark. Experience with an adaptive globally-synchronizing clock algorithm. In Eleventh Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA '99), pages 106--114, New York, June 1999.]] Google ScholarDigital Library
- 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.]]Google ScholarCross Ref
- 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.]] Google ScholarDigital Library
- 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.]]Google Scholar
- R. M. Metcalfe and D. R. Boggs. Ethernet: Distributed packet switching for local computer networks. Communications of the ACM, 26(1):90--95, January 1983.]] Google ScholarDigital Library
- 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.]]Google Scholar
- David L. Mills. Precision synchronization of cmputer network clocks. ACM Computer Comm. Review, 24(2):28--43, April 1994.]] Google ScholarDigital Library
- David L. Mills. Adaptive hybrid clock discipline algorithm for the network time protocol. IEEE/ACM Transactions on Networking, 6(5):505--514, October 1998.]] Google ScholarDigital Library
- M. Mock, R. Frings, E. Nett, and S. Trikaliotis. Continuous clock synchronization in wireless real-time applications. In The 19th IEEE Symposium on Reliable Distributed Systems (SRDS'00), pages 125--133, Washington - Brussels - Tokyo, October 2000. IEEE.]] Google ScholarDigital Library
- Kay Römer. Time synchronization in ad hoc networks. In Proceedings of MobiHoc 2001, Long Beach, CA, Oct 2001.]] Google ScholarDigital Library
- I. Rubin. Message Delays in FDMA and TDMA Communication Channels. IEEE Trans. Communin., COM27(5):769--777, May 1979.]]Google ScholarCross Ref
- T. K. Srikanth and Sam Toueg. Optimal clock synchronization. J-ACM, 34(3):626--645, July 1987.]] Google ScholarDigital Library
- 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.]]Google Scholar
- 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.]]Google Scholar
- 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.]]Google Scholar
- 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.]]Google Scholar
- 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.]]Google ScholarDigital Library
Index Terms
- Fine-grained network time synchronization using reference broadcasts
Recommendations
Fine-grained network time synchronization using reference broadcasts
OSDI '02: Proceedings of the 5th symposium on Operating systems design and implementation (Copyright restrictions prevent ACM from being able to make the PDFs for this conference available for downloading)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 ...
Gradient Clock Synchronization Using Reference Broadcasts
OPODIS '09: Proceedings of the 13th International Conference on Principles of Distributed SystemsReference-Broadcast Synchronization (RBS) is a technique that allows a set of receivers in a broadcast network to accurately estimate each others' clock values. RBS provides a relative time-frame for conversion between the local clocks of different ...
Reference interpolation protocol for time synchronization in wireless sensor networks
UIC'07: Proceedings of the 4th international conference on Ubiquitous Intelligence and ComputingAdvance in processor, memory and wireless communication technique have led to an increase of economical and small wireless sensor nodes. To provide the right responses quickly for the diverse events, wireless sensor nodes have cooperation with together. ...
Comments