Average TimeSynch: a consensus-based protocol for clock synchronization in wireless sensor networks. (English) Zbl 1223.68022

Schenato, Luca; Fiorentin, Federico

Automatica 47, No. 9, 1878-1886 (2011).

Summary: This paper describes a new consensus-based protocol, referred to as Average TimeSync (ATS), for synchronizing the clocks of a wireless sensor network. This algorithm is based on a cascade of two consensus algorithms, whose main task is to average local information. The proposed algorithm has the advantage of being totally distributed, asynchronous, robust to packet drop and sensor node failure, and it is adaptive to time-varying clock drifts and changes of the communication topology. In particular, a rigorous proof of convergence to global synchronization is provided in the absence of process and measurement noise and of communication delay. Moreover, its effectiveness is shown through a number of experiments performed on a real wireless sensor network.

MSC:

68M14	Distributed systems
68M10	Network design and communication in computer systems

Keywords:

consensus; time synchronization; drift compensation; networked systems; node failure

References:

[3]	Cao, M.; Morse, A. S.; Anderson, B. D.O., Reaching a consensus in a dynamically changing environment: A graphical approach, SIAM Journal on Control and Optimization, 47, 2, 575-600 (2008) · Zbl 1157.93514
[7]	Fagnani, F.; Zampieri, S., Randomized consensus algorithms over large scale networks, IEEE Journal on Selected Areas in Communications, 26, 4, 634-649 (2008)
[8]	Faizulkhakov, Ya. R., Time synchronization methods for wireless sensor networks: A survey, Programming and Computing Software, 33, 4, 214-226 (2007) · Zbl 1138.68318
[11]	Garin, F.; Schenato, L., A survey on distributed estimation and control applications using linear consensus algorithms, (Networked control systems, lecture notes in control and information sciences, vol. 406 (2011), Springer-Verlag: Springer-Verlag London), 75-107 · Zbl 1216.93097
[14]	Knorn, F.; Stanojevic, R.; Corless, M.; Shorten, R., A framework for decentralised feedbackconnectivity control with application to sensor networks, International Journal of Control, 82, 11, 20952114 (2009) · Zbl 1175.93004
[15]	Li, Q.; Rus, D., Global clock synchronization in sensor networks, IEEE Transactions on Computers, 55, 2, 214-226 (2006)
[17]	Moreau, L., Stability of multiagent systems with time-dependent communication links, IEEE Transactions on Automatic Control, 50, 2, 169-182 (2005) · Zbl 1365.93268
[18]	Moreau, L., Stability of continuous-time distributed consensus algorithms, Proceedings of IEEE Conference on Decision and Control (CDC’04), 4, December, 3998-4003 (2004)
[19]	Olfati Saber, R.; Fax, J. A.; Murray, R. M., Consensus and cooperation in multi-agent networked systems, Proceedings of IEEE, 95, 1, 215-233 (2007) · Zbl 1376.68138
[22]	Seneta, E., Non-negative matrices and Markov chains (2006), John Wiley & Sons, Inc., Springer · Zbl 1099.60004
[23]	Simeone, O.; Spagnolini, U., Distributed time synchronization in wireless sensor networks with coupled discrete-time oscillators, EURASIP Journal on Wireless Communications and Networking (2007)
[24]	Simeone, O.; Spagnolini, U.; Bar-Ness, Y.; Strogatz, S. H., Distributed synchronization in wireless networks, IEEE Signal Processing Magazine, 25, 5, 81-97 (2008)
[25]	Sivrikaya, F.; Yener, B., Time synchronization in sensor networks: A survey, IEEE Network, 18, 45-50 (2004)
[28]	Sundararaman, B.; Buyand, U.; Kshemkalyani, A. D., Clock synchronization for wireless sensor networks: A survey, Ad Hoc Networks, 3, 3, 281-323 (2005)
[32]	Willems, J. C., Lyapunov functions for diagonally dominant systems, Automatica, 12, 5, 519-523 (1976) · Zbl 0345.93040