logo

Journals Books
Advanced Search
Sign in Register

中文

SCIENTIA SINICA Informationis
Download PDF
SCIENTIA SINICA Informationis, Volume 46 , Issue 11 : 1527-1541(2016) https://doi.org/10.1360/N112016-00129

Clock synchronization algorithms for networked systems

Minrui FEI , Nan XIONG , Tao LI *
More info
  • ReceivedMay 17, 2016
  • AcceptedJul 21, 2016
  • PublishedNov 8, 2016
Previous Table of Contents Next
Share
Rating

Abstract

Clock synchronization is a classical topic in the field of networked systems. Real-time industrial Ethernet and wireless sensor networks are two typical kinds of networked systems that have important applications in modern industry. In industrial Ethernet, people usually adopt the IEEE 1588 clock synchronization mechanism, and in wireless sensor networks, people often employ a distributed synchronization algorithm due to limited resources, unreliable communication links, and dynamic network topologies. In recent years, along with the development of a theoretical framework of distributed multi-agent consensus, there are an increasing number of scholars in the control community who are shifting their focus to the distributed clock synchronization algorithm and its applications, and there have been key breakthroughs in the algorithm convergence theorems. Owing to their robustness, flexibility, and ease of implementation, distributed consensus clock synchronization protocols have good prospects; however, many challenging scientific problems remain. In this paper, we summarize the latest research trends on hierarchical and distributed clock synchronization algorithms, especially highlighting the representative clock synchronization algorithms based on consensus control that were proposed in the last five years, and discuss the future directions that aim at providing valuable academic references for researchers working in relevant fields.


Funded by

国家自然科学基金(61522310)

上海市科委基础研究项目(14JC1402200)

国际科技合作项目(152207 10400)


References

[1] Freris N M, Kowshik H, Kumar P R. Fundamentals of large sensor networks: connectivity, capacity, clocks and computation. Proc IEEE, 2010, 98: 1828-1846 CrossRef Google Scholar

[2] Lenzen C, Locher T, Sommer P, et al. Clock synchronization: open problems in theory and practice. In: Proceedings of the 36th Conference on Current Trends in Theory and Practice of Computer Science. Berlin: Springer, 2010. 61-70. Google Scholar

[3] Lin L, Yang C F, Ma M D, et al. Diffusion-based clock synchronization for molecular communication under inverse gaussian distribution. IEEE Sens J, 2015, 15: 4866-4874 CrossRef Google Scholar

[4] Lamport L. Time, clocks, and the ordering of events in a distributed system. Commun ACM, 1978, 21: 558-565 CrossRef Google Scholar

[5] Rhee III-K, Lee J, Kim J, et al. Clock synchronization in wireless sensor networks: an overview. Sensors, 2009, 9: 56-85 CrossRef Google Scholar

[6] Freris N M, Graham S R, Kumar P R. Fundamental limits on synchronizing clocks over networks. IEEE Trans Autom Control, 2011, 56: 1352-1364 CrossRef Google Scholar

[7] Swain A R, Hansdah R C. A model for the classification and survey of clock synchronization protocols in WSNs. Ad Hoc Netw, 2015, 27: 219-241 CrossRef Google Scholar

[8] Eidson J C. Measurement, Control and Communication Using IEEE 1588. London: Springer, 2006. Google Scholar

[9] Guruswamy A, Blum R S, Kishore S, et al. Minimax optimum estimators for phase synchronization in IEEE 1588. IEEE Trans Commun, 2015, 63: 3350-3362 CrossRef Google Scholar

[10] Guruswamy A, Blum R S, Kishore S, et al. On the optimum design of L-estimators for phase offset estimation in IEEE 1588. IEEE Trans Commun, 2015, 63: 5101-5115 CrossRef Google Scholar

[11] Giorgi G, Narduzzi C. Performance analysis of kalman-filter-based clock synchronization in IEEE 1588 networks. IEEE Trans Instrum Meas, 2011, 60: 2902-2909 CrossRef Google Scholar

[12] Giorgi G. An event-based kalman filter for clock synchronization. IEEE Trans Instrum Meas, 2015, 64: 449-457 CrossRef Google Scholar

[13] Levy C, Pinchas M. Maximum likelihood estimation of clock skew in IEEE 1588 with fractional gaussian noise. Math Probl Eng, 2015, 2015: 174289. Google Scholar

[14] Exel R. Mitigation of asymmetric link delays in IEEE 1588 clock synchronization systems. IEEE Commun Lett, 2014, 18: 507-510 CrossRef Google Scholar

[15] Anyaegbu M, Wang C X, Berrie W. Dealing with packet delay variation in IEEE 1588 synchronization using a sample-mode filter. IEEE Intel Transp Syst, 2013, 5: 20-27 CrossRef Google Scholar

[16] Xu X, Xiong Z H, Sheng X J, et al. A new time synchronization method for reducing quantization error accumulation over real-time networks: theory and experiments. IEEE Trans Ind Inform, 2013, 9: 1659-1669 CrossRef Google Scholar

[17] Li D J, Wang G, Yang C J, et al. IEEE 1588 based time synchronization system for a seafloor observatory network. J Zhejiang U-SCI C, 2013, 14: 766-776 CrossRef Google Scholar

[18] Dominicis C M-D, Ferrari P, Flammini A, et al. On the use of IEEE 1588 in existing IEC 61850-based SASs: current behavior and future challenges. IEEE Trans Instrum Meas, 2011, 60: 3070-3081 CrossRef Google Scholar

[19] Noh K-L, Chaudhari Q M, Serpedin E, et al. Novel clock phase offset and skew estimation using two-way timing message exchanges for wireless sensor networks. IEEE Trans Commun, 2007, 55: 766-777 CrossRef Google Scholar

[20] Ahmad A, Zennaro D, Serpedin E, et al. A factor graph approach to clock offset estimation in wireless sensor networks. IEEE Trans Inform Theory, 2012, 58: 4244-4260 CrossRef Google Scholar

[21] Cheng K-Y, Lui K S, Wu Y-C, et al. A distributed multihop time synchronization protocol for wireless sensor networks using pairwise broadcast synchronization. IEEE Trans Wirel Commun, 2009, 8: 1764-1772 CrossRef Google Scholar

[22] Franceschelli M, Pisano A, Giua A, et al. Finite-time consensus based clock synchronization by discontinuous control. In: Proceedings of 4th IFAC Conference on Analysis and Design of Hybrid Systems, Eindhoven, 2012. 172-177. Google Scholar

[23] Fontanelli D, Macii D. Master--less time synchronization for wireless sensor networks with generic topology. \linebreak In: Proceedings of International Instrumentation and Measurement Technology Conference, Graz, 2012. 2785-2790. Google Scholar

[24] Zennaro D, Anese E D, Erseghe T, et al. Fast clock synchronization in wireless sensor networks via ADMM-based consensus. In: Proceedings of International Symposium on Modeling and Optimization of Mobile, Ad Hoc, and Wireless Networks, Princeton, 2011. 148-153. Google Scholar

[25] Wang H, Zeng H Y, Wang P. Clock skew estimation of listening nodes with clock correction upon every synchronization in wireless sensor networks. IEEE Signal Proc Lett, 2015, 22: 2440-2444 CrossRef Google Scholar

[26] Djenouri D, Merabtine N, Mekahlia F Z, et al. Fast distributed multi-hop relative time synchronization protocol and estimators for wireless sensor networks. Ad Hoc Netw, 2013, 11: 2329-2344 CrossRef Google Scholar

[27] Wang J, Zhang S, Gao D, et al. Two-hop time synchronization protocol for sensor networks. EURASIP J Wirel Comm, 2014, 39. Google Scholar

[28] Ahmad A, Zennaro D, Vangelista L, et al. A distributed algorithm for network-wide clock synchronization in wireless sensor networks. In: Proceedings of the 16th International Conference on Information Fusion, Istanbul, 2013. 1037-1043. Google Scholar

[29] Leng M, Wu Y-C. On clock synchronization algorithms for wireless sensor networks under unknown delay. IEEE Trans Veh Tech, 2010, 59: 182-190 CrossRef Google Scholar

[30] Leng M, Wu Y-C. Low-complexity maximum-likelihood estimator for clock synchronization of wireless sensor nodes under exponential delays. IEEE Trans Signal Process, 2011, 59: 4860-4870 CrossRef Google Scholar

[31] Leng M, Wu Y-C. Distributed clock synchronization for wireless sensor networks using belief propagation. IEEE Trans Signal Process, 2011, 59: 5404-5414 CrossRef Google Scholar

[32] Luo B, Cheng L, Wu Y-C. Fully distributed clock synchronization in wireless sensor networks under exponential delays. Signal Process, 2016, 125: 261-273 CrossRef Google Scholar

[33] Werner-Allen G, Tewari G, Patel A, et al. Firefly-inspired sensor network synchronicity with realistic radio effects. \linebreak In: Proceedings of the 3rd International Conference on Embedded Networked Sensor Systems, San Diego, 2005. 142-153. Google Scholar

[34] Boyd S, Ghosh A, Prabhakar B, et al. Randomized gossip algorithms. IEEE Trans Inform Theory, 2006, 52: 2508-2530 CrossRef Google Scholar

[35] Marechal N, Pierrot J-B, Gorce J-M. Fine synchronization for wireless sensor networks using gossip averaging algorithms. In: Proceedings of IEEE International Conference on Communications, Beijing, 2008. 4963-4967. Google Scholar

[36] Bae J, Moon B. Time synchronization with fast asynchronous diffusion in wireless sensor network. In: Proceedings of International Conference on Cyber-Enabled Distributed Computing and Knowledge Discovery, Zhangjiajie, 2009. 82-85. Google Scholar

[37] Du J, Wu Y-C. Distributed clock skew and offset estimation in wireless sensor networks: asynchronous algorithm and convergence analysis. IEEE Trans Wirel Commun, 2013, 12: 5908-5917 CrossRef Google Scholar

[38] Choi B J, Liang H, Shen X, et al. DCS: distributed asynchronous clock synchronization in delay tolerant networks. IEEE Trans Parall Distr, 2012, 23: 491-504 CrossRef Google Scholar

[39] Ahmed S, Xiao F, Chen T W. Asynchronous consensus-based time synchronisation in wireless sensor networks using unreliable communication links. IET Control Theory A, 2014, 8: 1083-1090 CrossRef Google Scholar

[40] Baldoni R, Corsaro A, Querzoni L, et al. Coupling-based internal clock synchronization for large-scale dynamic distributed systems. IEEE Trans Parall Distrib, 2010, 21, 5: 607-619. Google Scholar

[41] Huang G, Zomaya A Y, Delicato F C, et al. An accurate on-demand time synchronization protocol for wireless sensor networks. J Parall Distrib Commun, 2012, 72: 1332-1346 CrossRef Google Scholar

[42] Brown D R, Klein A G, Wang R. Monotonic mean-squared convergence conditions for random pairwise consensus synchronization in wireless networks. IEEE Trans Signal Process, 2015, 63: 988-1000 CrossRef Google Scholar

[43] Wu J S, Jiao L C, Ding R R. Average time synchronization in wireless sensor networks by pairwise messages. Comput Commun, 2012, 35: 221-233 CrossRef Google Scholar

[44] Stanković M S, Stanković S S, Johansson K H. Distributed time synchronization in lossy wireless sensor networks. In: Proceedings of the 3rd IFAC Workshop on Distributed Estimation and Control in Networked Systems, Santa Barbara, 2012. 25-30. Google Scholar

[45] Stanković M S, Stanković S S, Johansson K H. Distributed blind calibration in lossy sensor networks via output synchronization. IEEE Trans Autom Control, 2015, 60: 3257-3262 CrossRef Google Scholar

[46] Carli R, Chiuso A, Schenato L, et al. A PI consensus controller for networked clock synchronization. In: Proceedings of the 17th World Congress, International Federation of Automatic Control, Seoul, 2008. 17: 10289-10294. Google Scholar

[47] Kishore S, Xiong G. Analysis of distributed consensus time synchronization with gaussian delay over wireless sensor networks. EURASIP J Wirel Commun Netw, 2009, 2009: 48. Google Scholar

[48] Kishore S, Xiong G. Discrete-time second-order distributed consensus time synchronization algorithm for wireless sensor networks. EURASIP J Wirel Commun Netw, 2009, 2009: 1. Google Scholar

[49] Chen J M, Yu Q, Zhang Y, et al. Feedback-based clock synchronization in wireless sensor networks: a control theoretic approach. IEEE Trans Veh Tech, 2010, 59: 2963-2973 CrossRef Google Scholar

[50] Lin L, Ma S W, Ma M D. A group neighborhood average clock synchronization protocol for wireless sensor networks. Sensors, 2014, 14: 14744-14764 CrossRef Google Scholar

[51] Schenato L, Fiorentin F. Average timesynch: a consensus-based protocol for clock synchronization in wireless sensor networks. Automatica, 2011, 47: 1878-1886 CrossRef Google Scholar

[52] Seyboth G S, Allgower F. Clock synchronization over directed graphs. In: Proceedings of IEEE 52th Annual Conference on Decision and Control, Florence, 2013. 6105-6111. Google Scholar

[53] Seyboth G S, Dimarogonas D V, Johansson K H, et al. On robust synchronization of heterogeneous linear multi-agent systems with static couplings. Automatica, 2015, 53: 392-399 CrossRef Google Scholar

[54] Olfati-Saber R, Murray R M. Consensus problems in networks of agents with switching topology and time-delays. IEEE Trans Autom Control, 2004, 49: 1520-1533 CrossRef Google Scholar

[55] Zhang H T, Chen M Z Q, Stan G B. Fast consensus via predictive pinning control. IEEE Trans Circ Syst I: Regular Papers, 2011, 58: 2247-2258 CrossRef Google Scholar

[56] Chen Y, Lu J H, Lin Z L. Consensus of discrete-time multi-agent systems with transmission nonlinearity. Automatica, 2013, 49: 1768-1775 CrossRef Google Scholar

[57] Zhang H T, Chen Z Y. Consensus acceleration in a class of predictive networks. IEEE Trans Neur Net Lear, 2014, 25: 1921-1927 CrossRef Google Scholar

[58] Cheng Z M, Zhang H T, Fan M C, et al. Distributed consensus of multi-agent systems with input constraints: a model predictive control approach. IEEE Trans Circ Syst I: Regular Papers, 2015, 62: 825-834 CrossRef Google Scholar

[59] Tian Y P, Zong S H, Cao Q Q. Structural modeling and convergence analysis of consensus-based time synchronization algorithms over networks: non-topological conditions. Automatica, 2016, 64: 60-75. Google Scholar

[60] Sommer P, Wattenhofer R. Gradient clock synchronization in wireless sensor networks. In: Proceedings of the International Conference on Information Processing in Sensor Networks, San Francisco, 2009. 37-48. Google Scholar

[61] Liao C D, Barooah P. Distributed clock skew and offset estimation from relative measurements in mobile networks with Markovian switching topology. Automatica, 2013, 49: 3015-3022 CrossRef Google Scholar

[62] Maggs M K, Okeefe S G, Thiel D V. Consensus clock synchronization for wireless sensor networks. IEEE Sens J, 2012, 12: 2269-2277 CrossRef Google Scholar

[63] He J P, Cheng P, Shi L, et al. Time synchronization in WSNs: a maximum-value-based consensus approach. IEEE Trans Autom Control, 2014, 59: 660-675 CrossRef Google Scholar

[64] He J P, Cheng P, Chen J M, et al. Time synchronization for random mobile sensor networks. IEEE Trans Veh Tech, 2014, 63: 3935-3946 CrossRef Google Scholar

[65] He J P, Duan X M, Cheng P, et al. Distributed time synchronization under bounded noise in wireless sensor networks, In: Proceedings of the 53rd IEEE Conference on Decision and Control, Los Angeles, 2014. 6883-6888. Google Scholar

[66] He J P, Li H, Chen J M, et al. Study of consensus-based time synchronization in wireless sensor networks. ISA Trans, 2014, 53: 347-357 CrossRef Google Scholar

[67] He J P, Cheng P, Shi L, et al. SATS: secure average-consensus-based time synchronization in wireless sensor networks. IEEE Trans Signal Process, 2013, 61: 6387-6400 CrossRef Google Scholar

[68] He J P, Chen J M, Cheng P, et al. Secure time synchronization in wireless sensor networks: a maximum consensus-based approach. IEEE Trans Parall Distrib, 2014, 25: 1055-1065 CrossRef Google Scholar

[69] Wei N, Guo Q, Li C J, et al. An event-triggered time synchronization scheme for sensor networks. In: Proceedings of the 11th IEEE International Conference on Computational Science and Engineering, Sao Paulo, 2008. 3-7. Google Scholar

[70] Kadowaki Y, Ishii H. Event-based distributed clock synchronization for wireless sensor networks. IEEE Trans Autom Control, 2015, 60: 2266-2271 CrossRef Google Scholar

[71] Sun W, Strom E G, Brannstrom F, et al. Random broadcast based distributed consensus clock synchronization for mobile networks. IEEE Trans Wirel Commun, 2015, 14: 3378-3389 CrossRef Google Scholar

[72] Lamonaca F, Garone E, Grimaldi D, et al. Localized fine accuracy synchronization in wireless sensor network based on consensus approach. In: Proceedings of the International Instrumentation and Measurement Technology Conference, Graz, 2012. 2802-2805. Google Scholar

[73] Lamonaca F, Gasparri A, Garone E, et al. Clock synchronization in wireless sensor network with selective convergence rate for event driven measurement applications. IEEE Trans Instrum Meas, 2014, 63: 2279-2287 CrossRef Google Scholar

[74] Garone E, Gasparri A. Lamonaca F. Clock synchronization protocol for wireless sensor networks with bounded communication delays. Automatica, 2015, 59: 60-72. Google Scholar

[75] Tian Y P. LSTS: a new time synchronization protocol for networks with random communication delays. In: Proceedings of IEEE 54th Annual Conference on Decision and Control, Osaka, 2015. 7404-7409. Google Scholar

[76] Panigrahi N, Khilar P M. Optimal consensus-based clock synchronisation algorithm in wireless sensor network by selective averaging. IET Wirel Sens Syst, 2015, 5: 166-174 CrossRef Google Scholar

[77] Panigrahi N, Khilar P M. Optimal topological balancing strategy for performance optimisation of consensus-based clock synchronisation protocols in wireless sensor networks: a genetic algorithm-based approach. IET Wirel Sens Syst, 2014, 4: 213-222 CrossRef Google Scholar

[78] Panigrahi N, Khilar P M. An evolutionary based topological optimization strategy for consensus based clock synchronization protocols in wireless sensor network. Swarm Evol Comput, 2015, 22: 66-85 CrossRef Google Scholar

[79] Wu J, Zhang L Y, Bai Y, et al. Cluster-based consensus time synchronization for wireless sensor networks. IEEE Sens J, 2015, 15: 1404-1413 CrossRef Google Scholar

[80] Berger A, Pichler M, Klinglmayr J, et al. Low-complex synchronization algorithms for embedded wireless sensor networks. IEEE Trans Instrum Meas, 2015, 64: 1032-1042 CrossRef Google Scholar

[81] Carli R, Chiuso A, Schenato L, et al. Optimal synchronization for networks of noisy double integrators. IEEE Trans Autom Control, 2011, 56: 1146-1151 CrossRef Google Scholar

[82] Carli R, Zampieri S. Network clock synchronization based on the second-order linear consensus algorithm. IEEE Trans Autom Control, 2014, 59: 409-422 CrossRef Google Scholar

[83] Bolognani S, Carli R, Zampieri S. A PI consensus controller with gossip communication for clock synchronization in wireless sensors networks. In: Proceedings of the 1st IFAC Workshop on Estimation and Control of Networked Systems, Venice, 2009. 78-83. Google Scholar

[84] Carli R, Elia E D, Zampieri S. A PI controller based on asymmetric gossip communications for clocks synchronization in wireless sensors networks. In: Proceedings of the 50th IEEE Conference on Decision and Control and European Control Conference, Orlando, 2011. 7512-7517. Google Scholar

[85] Bolognani S, Carli R, Lovisari E, et al. A randomized linear algorithm for clock synchronization in multi-agent systems. IEEE Trans Autom Control, 2016, 61: 1711-1726 CrossRef Google Scholar

[86] Carli R, Giorgi G, Narduzzi C. Comparative analysis of synchronization strategies in sensor network with misbehaving clocks. In: Proceedings of International Instrumentation and Measurement Technology Conference, Graz, 2012. 2617-2622. Google Scholar

[87] Yildirim K S, Carli R, Schenato L. Adaptive control-based clock synchronization in wireless sensor networks. \linebreak In: Proceedings of European Control Conference, Linz, 2015. 2806-2811. Google Scholar

[88] Gurcan O, Yildirim K S. Self-organizing time synchronization of wireless sensor networks with adaptive value trackers. In: Proceedings of the 7th IEEE International Conference on Self-Adaptive and Self-Organizing Systems, Philadelphia, 2013. 91-100. Google Scholar

[89] Yildirim K S, Carli R, Schenato L. Proportional-integral clock synchronization in wireless sensor networks. arXiv:1410.8176. Google Scholar

[90] Yildirim K S. Gradient descent algorithm inspired adaptive time synchronization in wireless sensor networks. IEEE Sens J, 2016, 16: 5463-5470 CrossRef Google Scholar

[91] Mallada E, Tang A. Distributed clock synchronization: joint frequency and phase consensus. In: Proceedings of the 50th IEEE Conference on Decision and Control and European Control Conference, Orlando, 2011. 6742-6747. Google Scholar

[92] Mallada E, Meng X, Hack M, et al. Skewless network clock synchronization without discontinuity: convergence and performance. IEEE ACM Trans Netw, 2015, 23: 1619-1633 CrossRef Google Scholar

[93] Chen Z P, Li D Q, Huang Y R, et al. Event-triggered communication for time synchronization in WSNs. Neurocomputing, 2016, 177: 416-426 CrossRef Google Scholar

[94] Li J, Mechitov K A, Kim R E, et al. Efficient time synchronization for structural health monitoring using wireless smart sensor networks. Struct Control Hlth, 2016, 23: 470-486 CrossRef Google Scholar

[95] Zhe Y, He L, Cai L, et al. Temperature-assisted clock synchronization and self-calibration for sensor networks. IEEE Trans Wirel Commun, 2014, 13: 3419-3429 CrossRef Google Scholar

[96] Veitch D, Ridoux J, Korada S B. Robust synchronization of absolute and difference clocks over networks. IEEE ACM Trans Netw, 2009, 17: 417-430 CrossRef Google Scholar

[97] Fagiolini A, Martini S, Bicchi A. Set-valued consensus for distributed clock synchronization. In: Proceedings of IEEE International Conference on Automation Science and Engineering, Bangalore, 2009. 116-121. Google Scholar

[98] Li Q, Rus D. Global clock synchronization in sensor networks. IEEE Trans Comput, 2006, 55: 214-226 CrossRef Google Scholar

[99] Li C Y, Wang Y, Hurfin M. Clock synchronization in mobile Ad Hoc networks based on an iterative approximate byzantine consensus protocol. In: Proceedings of IEEE 28th International Conference on Advanced Information Networking and Applications, Victoria, 2014. 210-217. Google Scholar

[100] Levine J. An algorithm for synchronizing a clock when the data are received over a network with an unstable delay. IEEE Trans Ultrason Ferroelectr Freq Control, 2016, 63: 561-570 CrossRef Google Scholar

[101] Leva A, Terraneo F, Rinaldi T, et al. High-precision low-power wireless nodes' synchronization via decentralized control. IEEE Trans Contr Syst Tech, 2016, 24: 1279-1293 CrossRef Google Scholar

[102] Li Z J, Chen W W, Li M, et al. Incorporating energy heterogeneity into sensor network time synchronization. IEEE Trans Parall Distrib, 2015, 26: 163-173 CrossRef Google Scholar

[103] Derogarian F, Ferreira J C, Tavares V M-G. A precise and hardware-efficient time synchronization method for wearable wired networks. IEEE Sens J, 2016, 16: 1460-1470 CrossRef Google Scholar

[104] Du X J, Guizani M, Xiao Y, et al. Secure and efficient time synchronization in heterogeneous sensor networks. IEEE Trans Veh Tech, 2008, 57: 2387-2394 CrossRef Google Scholar

[105] Dong W, Liu X J. Robust and secure time-synchronization against sybil attacks for sensor networks. IEEE Trans Ind Inform, 2015, 11: 1482-1491 CrossRef Google Scholar