Convergence analysis and accelerating design for distributed consensus time synchronization protocol in wireless sensor networks

被引：3
作者：
Li L. [1 ]
Liu Y.-P. [1 ]
Yang H.-Z. [1 ]
Wang H. [1 ]
机构：
[1] Department of Electronic Engineering, Tsinghua University
来源：
Dianzi Yu Xinxi Xuebao/Journal of Electronics and Information Technology | 2010年 / 32卷 / 09期
关键词：
Acceleration; Distributed consensus; Time synchronization; Wireless sensor networks;
D O I：
10.3724/SP.J.1146.2009.01234
中图分类号：
学科分类号：
摘要：
This paper analyzes convergence and acceleration issues of distributed consensus time synchronization protocols in wireless sensor networks. By mapping synchronization iterations to Markov domain, the upper and lower bounds of protocol convergence rate are deduced in circulant networks, which proves that the protocol convergence rate is related to node neighbor size and network size. Matlab simulation results in co-uniform regular networks and co-uniform networks indicate the same conclusion. Moreover, it is found that in co-uniform non-regular networks, the protocol convergence rate will also be affected by neighbor size distribution. So an accelerating algorithm is proposed, which improves the convergence rate of distributed consensus time synchronization protocols by adjusting neighbor size distribution. Experiment results show that in a 100-node co-uniform network, the proposed accelerating algorithm can reduce the iteration counts of the distributed consensus time synchronization protocols by 25%, without any significant variation of the average node transmission radius.
引用
收藏
页码：2045 / 2051
页数：6
相关论文
共 10 条
  • [1] Ganeriwal S., Kumar R., Srivastava M.B., Timing-sync protocol for sensor networks, Proceedings of the First International Conference on Embedded Networked Sensor Systems, pp. 138-149, (2003)
  • [2] Sommer P., Wattenhofer R., Symmetric clock synchronization in sensor networks, ACM Workshop on Real-World Wireless Sensor Networks, pp. 11-15, (2008)
  • [3] Giridhar A., Kumar P.R., Distributed clock synchronization over wireless networks: Algorithms and analysis, Proceedings of the 45th IEEE Conference on Decision and Control, pp. 4915-4920, (2006)
  • [4] Li Q., Rus D., Global clock synchronization in sensor networks, IEEE Transactions on Computers, 55, 2, pp. 214-226, (2006)
  • [5] Schenato L., Gamba G., A distributed consensus protocol for clock synchronization in wireless sensor network, 46th IEEE Conference on Decision and Control, pp. 2289-2294, (2007)
  • [6] Gang X., Kishore S., Second order distributed consensus time synchronization algorithm for wireless sensor networks, Global Telecommunications Conference, IEEE, pp. 1-5, (2008)
  • [7] Sommer P., Wattenhofer R., Gradient clock synchronization in wireless sensor networks, International Conference on Information Processing in Sensor Networks, pp. 37-48, (2009)
  • [8] Gang X., Kishore S., Performance of distributed consensus time synchronization with gaussian delay in wireless sensor networks, Wireless Communications and Networking Conference, IEEE, pp. 1-5, (2009)
  • [9] Boyd S., Diaconis P., Xiao L., Fastest mixing Markov chain on a graph, Siam Review, 46, 4, pp. 667-690, (2004)
  • [10] Kannan R., Markov chains and polynomial time algorithms, 35th Annual Symposium on Foundations of Computer Science, pp. 656-671, (1994)
1