传感器网络虚拟骨干构造算法及时钟同步应用

An Algorithm for Virtual Backbone Construction in Sensor Network and its Application in Time Synchronization

通过构造虚拟骨干可以大幅度降低无线传感器网络的广播开销和路由协议的复杂度。本文基于连通支配集,提出了一种虚拟骨干分布式构造算法,其最终尺寸、构造过程中的计算复杂度都优于现有算法。并结合虚拟骨干对Su Ping等学者提出的DMTS时钟同步算法进行了改进,降低其同步通信开销60%左右。

Broadcasting overhead and the complexity of routing protocol can be greatly reduced through backbone construction in wireless sensor network. We propose a distributed backbone construction algorithm based on Connected Dominating Set （CDS）, and it outperforms the existing algorithm in the size of constructed CDS and the computation complexity. Then we make a modification of Su Ping＇s DMTS time synchronization algorithm based on the backbone, which reduces its communication overhead about 60%.