Time Synchronization for Large Scale Wireless Sensor Networks Based on Multi-Broadcast Gossip Algorithm

Abstract:

A scheme of time synchronization for large scale wireless sensor networks based on multi-broadcast gossip algorithm is proposed in this paper. It is allowed multiple nodes can broadcast their time information simultaneously. In order to avoid communication collisions and receiving confusion, according to graph theory the distance between any two broadcasting nodes is restricted as 3. It is proved for convergence performance of this scheme by using stochastic matrix theory. The performance for this scheme is discussed. The computer simulations are given to test and verify the theoretical analysis.

• Periodical: Advanced Materials Research (Volumes 846-847)
• Pages: 526-530
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.846-847.526
• Online since: November 2013
• Authors: Chao Shi*, Hong Bing Qiu, Yun Yi Wang
• Keywords: Gossip Algorithm, Multi-Broadcast, Time Synchronization, Wireless Sensor Network (WSN)

References

[1] O. Simeone, U. Spagnolini, Y. Bar-Ness, and Steven H. Strogatz. Distributed synchronization in wireless networks [J]. IEEE Signal Processing Magazine, 2008, 25(5): 81-97.

DOI: 10.1109/msp.2008.926661

[2] S. Ganeriwal, R. Kumar, M.B. Srivastava. Timing sync protocol for sensor networks [C]. First International Conference on Embedded Network Sensor Systems, 2003, 138-149.

DOI: 10.1145/958491.958508

[3] M. Maroti, B. Kusy, G. Simon, and A. Ldeczi. The flooding time synchronization protocol [C]. 2nd International Conference on Embedded Networked Sensor Systems, 2004: 39-49.

DOI: 10.1145/1031495.1031501

[4] J. Elson, L. Girod, and D. Estrin. Fine-grained network time synchronization using reference broadcasts[C]. 5th symposium on Operating Systems Design and Implementation, 2002: 147-163.

DOI: 10.1145/1060289.1060304

[5] A.G. Dimakis, S. Kar, J. Moura, M.G. Rabbat, and A. Scaglione. Gossip algorithms for distributed signal processing [J]. Proceeding of the IEEE, 2010, 98(88): 1847-1864.

DOI: 10.1109/jproc.2010.2052531

[6] J. Liu, S. Mou, A.S. Morse, B.D.O. Anderdson, and C. Yu. Deterministic gossiping [J]. Proceeding of the IEEE, 2011, 99(9): 1505-1524.

[7] J. Wu, L. Jiao, R. Ding. Average time synchronization in wireless sensor networks by pairwise messages [J]. Computer Communications, 2012, 35(2): 221-233.

DOI: 10.1016/j.comcom.2011.09.007

[8] L. Schenato and F. Fiorentin. Average TimeSynch: A consensus-based protocol for clock synchronization in wireless sensor networks [J]. Automatics, 2011, 47(9): 1878-1886.

DOI: 10.1016/j.automatica.2011.06.012

[9] Shi chao, Qiu Hong-bing, Chen Dong-hua, and Li Xiao-yan. A simple distributed time synchronization scheme for wireless sensor networks [J]. Journal of Xidian University, 2013, 40(1): 116-125.

[10] M. Franceschelli, A. Giua, and C. Seatzu. Distributed averaging in Sensor Networks Based on Broadcast Gossip Algorithm [J]. IEEE Sensors Journal, 2011, 11(3): 808-817.

DOI: 10.1109/jsen.2010.2064295

[11] R.A. Horn, C.R. Johnson. Matrix Analysis [M]. Cambridge University Press, Cambridge, (1985).

[12] M.K. Maggs, S.G. O'Keefe, and D.V. Thiel. Consensus Clock Synchronization for Wireless Sensor Networks [J]. IEEE Sensors Journal, 2012, 12(6): 2269-2277.

DOI: 10.1109/jsen.2011.2182045