logo

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

Clock synchronization algorithms for networked systems

More info
  • ReceivedMay 17, 2016
  • AcceptedJul 21, 2016
  • PublishedNov 8, 2016

Abstract


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