无线传感器网络分布式一致时间同步协议的收敛分析及加速设计
doi: 10.3724/SP.J.1146.2009.01234
Convergence Analysis and Accelerating Design for Distributed Consensus Time Synchronization Protocol in Wireless Sensor Networks
-
摘要: 该文研究了基于分布式一致的无线传感器网络时间同步协议的收敛和加速问题。通过将其同步迭代过程映射到马尔可夫链的状态转移过程，推导出了分布式一致时间同步协议在循环网中的收敛速度与节点邻居数和网络规模有关。Matlab仿真实验表明该结论对类均匀规则网和类均匀网也是正确的。此外，对于类均匀网，邻居数分布也会影响协议的收敛速度。因此该文提出了基于改变网络邻居数分布的加速算法来提高分布式一致时间同步协议的收敛速度。规模为100个节点的类均匀网络实验结果表明，该文提出的加速算法在没有显著改变节点平均传输半径的情况下可使分布式一致时间同步协议的收敛迭代次数降低约25%。Abstract: 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.
-
Key words:
- Wireless sensor networks /
- Distributed consensus /
- Time synchronization /
- Acceleration
-
Ganeriwal S, Kumar R, and Srivastava M B. Timing-sync protocol for sensor networks. Proceedings of the First International Conference on Embedded Networked Sensor Systems, Los Angeles, CA, USA, 2003: 138-149.[2]Sommer P and Wattenhofer R. Symmetric clock synchronization in sensor networks. ACM Workshop on Real-World Wireless Sensor Networks, Glasgow, Scotland, 2008: 11-15.[3]Giridhar A and Kumar P R. Distributed clock synchronization over wireless networks: algorithms and analysis. Proceedings of the 45th IEEE Conference on Decision and Control, San Diego, USA, 2006: 4915-4920.[4]Li Q, Rus D. Global clock synchronization in sensor networks[J].IEEE Transactions on Computers.2006, 55(2):214-226[5]Schenato L and Gamba G. A distributed consensus protocol for clock synchronization in wireless sensor network. 46th IEEE Conference on Decision and Control, New Orleans, LA, USA, 2007: 2289-2294.[6]Gang X and Kishore S. Second order distributed consensus time synchronization algorithm for wireless sensor networks. Global Telecommunications Conference, IEEE, New Orleans, LA, USA, 2008: 1-5.[7]Sommer P and Wattenhofer R. Gradient clock synchronization in wireless sensor networks. International Conference on Information Processing in Sensor Networks, San Francisco, USA, 2009: 37-48.Gang X and Kishore S. Performance of distributed consensus time synchronization with gaussian delay in wireless sensor networks.Wireless Communications and Networking Conference, IEEE, Budapest, Hungary, 2009: 1-5.[8]Boyd S, Diaconis P, and Xiao L. Fastest mixing Markov chain on a graph[J].Siam Review.2004, 46(4):667-690[9]Kannan R. Markov chains and polynomial time algorithms. 35th Annual Symposium on Foundations of Computer Science, Santa Fe, New Mexico, USA, 1994: 656-671. -
计量
- 文章访问数: 3506
- HTML全文浏览量: 83
- PDF下载量: 905
- 被引次数: 0
下载:
