ACES: adaptive clock estimation and synchronization using Kalman filtering

ABSTRACT

Clock synchronization across a network is essential for a large number of applications ranging from wired network measurements to data fusion in sensor networks. Earlier techniques are either limited to undesirable accuracy or rely on specific hardware characteristics that may not be available for certain systems. In this work, we examine the clock synchronization problem in resource-constrained networks such as wireless sensor networks where nodes have limited energy and bandwidth, and also lack the high accuracy oscillators or programmable network interfaces some previous protocols depend on. This paper derives a general model for clock offset and skew and demonstrates its applicability. We design efficient algorithms based on this model to achieve high synchronization accuracy given limited resources. These algorithms apply the Kalman filter to track the clock offset and skew, and adaptively adjust the synchronization interval so that the desired error bounds are achieved. We demonstrate the performance advantages of our schemes through extensive simulations obeying real-world constraints.

REFERENCES

• 1: Clock oscillator stability. Cardinal Components Inc. Applications Brief No. A.N. 1006, www.cardinalxtal.com/docs/notes.
• 2: L. Auler and R. d'Amore. Adaptive kalman filter for time synchronization over packet-switched networks (an heuristic approach). In IEEE COMSWARE, Jan. 2007.
• 3: A. Bletsas. Evaluation of kalman filtering for network time keeping. IEEE Trans. on Ultrasonics, Ferroelectrics, and Frequency Control, 52(9), Sept. 2005.
• 4: Jeremy Elson , Lewis Girod , Deborah Estrin, Fine-grained network time synchronization using reference broadcasts, ACM SIGOPS Operating Systems Review, v.36 n.SI, Winter 2002 [doi>10.1145/844128.844143]
• 5: 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]
• 6: IEEE std. 1588 - 2002 IEEE standard for a precision clock synchronization protocol for networked measurement and control systems. IEEE Std 1588-2002, pages i--144, 2002.
• 7: Ankur Jain , Edward Y. Chang, Adaptive sampling for sensor networks, Proceeedings of the 1st international workshop on Data management for sensor networks: in conjunction with VLDB 2004, August 30-30, 2004, Toronto, Canada [doi>10.1145/1052199.1052202]
• 8: R. H. Jones and F. Boadi-Boateng. Unequally spaced longitudinal data with ar(1) serial correlation. Biometrics, 47(1):161--175, 1991.
• 9: Steven M. Kay, Fundamentals of statistical signal processing: estimation theory, Prentice-Hall, Inc., Upper Saddle River, NJ, 1993
• 10: K. Kim and B.G.Lee. Kalp: A kalman filter-based adaptive clock method with low-pass prefiltering for packet networks use. IEEE Trans. on Comm., 48(7), July 2000.
• 11: Q. Li and D. Rus. Global clock synchronization in sensor networks. In IEEE INFOCOM, Mar. 2004.
• 12: 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]
• 13: D. L. Mills. Internet time synchronization: the network time protocol. IEEE Trans. on Comm., 39(10):1482--1493, Oct. 1991.
• 14: David L. Mills, Improved algorithms for synchronizing computer network clocks, IEEE/ACM Transactions on Networking (TON), v.3 n.3, p.245-254, June 1995 [doi>10.1109/90.392384]
• 15: 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
• 16: S. B. Moon, P. Skelly, and D. Towsley. Estimation and removal of clock skew from network delay measurements. In INFOCOM 1999, volume 1, pages 227--234, Mar. 1999.
• 17: Santashil PalChaudhuri , Amit Kumar Saha , David B. Johnson, Adaptive clock synchronization in sensor networks, Proceedings of the 3rd international symposium on Information processing in sensor networks, April 26-27, 2004, Berkeley, California, USA [doi>10.1145/984622.984672]
• 18: Attila Pásztor , Darryl Veitch, PC based precision timing without GPS, ACM SIGMETRICS Performance Evaluation Review, v.30 n.1, June 2002
• 19: J. Phillips and K. Kundert. Noise in mixers, oscillators, samplers, and logic: An introduction to cyclostationary noise. In IEEE CICC, pages 431--438, May 2000.
• 20: G. J. Pottie , W. J. Kaiser, Wireless integrated network sensors, Communications of the ACM, v.43 n.5, p.51-58, May 2000 [doi>10.1145/332833.332838]
• 21: 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]
• 22: M. Sichitiu and C. Veerarittiphan. Simple, accurate time synchronization for wireless sensor networks. In IEEE WCNC, 2003.
• 23: Weilian Su , Ian F. Akyildiz, Time-diffusion synchronization protocol for wireless sensor networks, IEEE/ACM Transactions on Networking (TON), v.13 n.2, p.384-397, April 2005 [doi>10.1109/TNET.2004.842228]
• 24: B. Sundararaman, U. Buy, and A. Kshemkalyani. Clock synchronization for wireless sensor networks: a survey. Ad Hoc Networks, 3(3), Feb. 2005.
• 25: Darryl Veitch , Satish Babu , Attila Pàsztor, Robust synchronization of software clocks across the internet, Proceedings of the 4th ACM SIGCOMM conference on Internet measurement, October 25-27, 2004, Taormina, Sicily, Italy [doi>10.1145/1028788.1028817]
• 26: J. R. Vig. Introduction to quartz frequency standards. Technical Report SLCET-TR-92-1 (Rev. 1), Army Research Laboratory, Oct. 1992.
• 27: L. Zhang, Z. Liu, and C. H. Xia. Clock synchronization algorithms for network measurements. In INFOCOM 2002, volume 1, pages 160--169, 2002.
• 28: D. Zhou and T. Lai. A scalable and adaptive clock synchronization protocol for ieee 802.11-based multihop ad hoc networks. In IEEE Mobile Adhoc and Sensor Systems, Nov. 2005.

INDEX TERMS

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

Additional Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.5 Model Development

General Terms:
Design, Measurement, Theory

Keywords:
Kalman filter, clock offset, clock skew, clock synchronization, resource-constrained network