Computer Science ›› 2015, Vol. 42 ›› Issue (12): 184-188.

Previous Articles     Next Articles

Regional Diffusion Mechanism Based Time Synchronization Algorithm for Wireless Sensor Networks

WANG Tao   

  • Online:2018-11-14 Published:2018-11-14

Abstract: This paper analyzed convergence issues of distributed time synchronization algorithm in wireless sensor networks,and proposed a regional diffusion mechanism based time synchronization algorithm.The algorithm is made up by two phases.The first phase proposes a spokesmen information exchange algorithm (SIE) for time synchronization within the region,based on the optimal foraging theory (OFT) and the principles of the highest yields.In the second phase, the spokesperson is chosen for the regional to do synchronization between regions according to the time offset,at the same time the synchronization process is mapped to a Markov chain,and a Markov chain based spokesperson acce-lerated algorithm (MarSAA) is proposed to accelerate convergence.Theoretical analysis and experimental results show that the proposed algorithm has better time complexity,and the performance is better than the traditional network-wide time synchronization algorithm,and the two-stage algorithm can also run in parallel.

Key words: Wireless sensor networks,Time synchronization,Distributed,Bio-heuristic calculation

[1] Sichitiu M L,Veerarittiphan C.Simple,Accurate Time Synchronization for Wireless Sensor Networks[C]∥Proc IEEE Wireless Communications and Networking Conference.2003
[2] Awerbuch B.A new distributed depth first search algorithm[J].Inf Proc.Lett.,1985(20):147-150
[3] Elson J,Girod L,Estrin D.Fine-Grained Network Time Synchronization using Reference Broadcasts[C]∥Proc 5th Symposium on Operating Systems Design and Implementation.Boston,MA,2002
[4] PalChaudhuri S,Saha A K,Johnson D B.Adaptive Clock Synchronization in Sensor Networks[C]∥Proc 3rd International Symposium on Information Processing in Sensor Networks.Berkeley,California,2004:340-348
[5] Mills D L.Internet time synchronization:the network time protocol [J].IEEE Transactions on Communications,1991,39(10):1482-1493
[6] Ta J.Global Positioning System [D].California State University,2011
[7] Sommer P,Wattenhofer R.Symmetric clock synchronization in sensor networks[C]∥ACM Workshop on Real-World Wireless Sensor Networks.Glasgow,Scotland,2008:11-15
[8] MacArthur R H,Pianka E R.On optimal use of a patchy environment [J].American Naturalist,1966,100(196):603-609
[9] Ping S.Delay measurement time synchronization for wirelesssensor networks [R].Intel Research Berkeley Lab,2003
[10] Maróti M,Kusy B,Simon G,et al.The flooding time synchronization protocol[C]∥Proceedings of the 2nd International Conference on Embedded Networked Sensor Systems.ACM,2004:39-49
[11] Simon G,Maroti M,Ledeczi A,et al.Sensor network-basedcountersniper system[C]∥Proceedings of the 2nd International Conference on Embedded Networked Sensor Systems.ACM,2004:1-12
[12] Basescu C,Cachin C,Eyal I,et al.Robust data sharing with key-value stores[C]∥2012 42nd Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN).IEEE,2012:1-12
[13] Huang D J,Teng W C,Yang K T.Secured flooding time synchronization protocol with moderator [J].International Journal of Communication Systems,2013,26(9):1092-1115
[14] Elson J,Girod L,Estrin D.Fine-grained network time synchronization using reference broadcasts [J].ACM SIGOPS Opera-ting Systems Review,2002,36(SI):147-163
[15] Solis R,Borkar V S,Kumar P R.A new distributed time synchronization protocol for multihop wireless networks[C]∥2006 45th IEEE Conference on Decision and Control.IEEE,2006:2734-2739
[16] Gang X,Kishore S.Performance of distributed consensus time synchronization with gaussian delay in wireless sensor networks[C]∥Wireless Communications and Networking Conference.IEEE,Budapest,Hungary,2009:1-5
[17] 刘强,黄小红,冷甦鹏,等.一种面向物联网的无线传感器优化部署策略[J].中国通信,2011,8(8):111-120 Liu Qiang,Huang Xiao-hong,Leng Su-peng, et al.Deploymentstrategy of wireless sensor networks for Internet of Things [J].China Communications,2011,8(8):111-120
[18] Giridhar A,Kumar P R.The spatial smoothing method of clock synchronization in wireless networks [M]∥Theoretical Aspects of Distributed Computing in Sensor Networks.Springer Berlin Heidelberg,2011:227-256
[19] Huang F W,Zhou X,Chen C.Multi-level feedback based time synchronization algorithm for wireless sensor networks [J].Journal on Communications,2009,30(3):13
[20] Xiong G,Kishore S.Performance of distributed consensus time synchronization with gaussian delay in wireless sensor networks[C]∥IEEE Wireless Communications and Networking Confe-rence,2009(WCNC 2009).IEEE,2009:1-5
[21] Lerman K,Galstyan A.Mathematical model of foraging in agroup of robots:Effect of interference [J].Autonomous Robots,2002,13(2):127-141
[22] Pini G,Brutschy A,Birattari M,et al.Interference reductionthrough task partitioning in a robotic swarm[C]∥Sixth International Conference on Informatics in Control,Automation and Robotics(ICINCO).2009:52-59
[23] Pianka E R.Evolutionary ecology(7th Edition)[M].Harper and Row,New York,2011:350-356
[24] Lin S C,Rezek Z,Braun D,et al.On the Utility and Economization of Unretouched Flakes:The Effects of Exterior Platform Angle and Platform Depth[J].American Antiquity,2013,78(4):724-745
[25] Mommer L,van Ruijven J,Jansen C,et al.Interactive effects of nutrient heterogeneity and competition:implications for root fora-ging theory?[J].Functional Ecology,2012,26(1):66-73
[26] Kerkez B,Pister K.Adaptive Time Synchronization and Fre-quency Channel Hopping for Wireless Sensor Networks[D].EECS Department,University of California,Berkeley,2012
[27] Ni J,Tan B,Srikant R.Q-csma:Queue-length-based csma/ca algorithms for achieving maximum throughput and low delay in wireless networks[J].IEEE/ACM Transactions on Networking,2012,20(3):825-836
[28] Bhakta P,Miracle S,Randall D,et al.Mixing Times of Markov Chains for Self-Organizing Lists and Biased Permutations[C]∥SODA.2013:1-15
[29] Kwok T C,Lau L C,Lee Y T,et al.Improved Cheeger’s inequa-lity:analysis of spectral partitioning algorithms through higher order spectral gap[C]∥Proceedings of the 45th Annual ACM Symposium on Symposium on Theory of Computing.ACM,2013:11-20
[30] Haran M,Tierney L.On automating markov chain monte carlo for a class of spatial models [J].Bayesian Analysis,2012,5(4):99-125

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!