连通支配集算法及其改进

Improved Connected Dominating Set Algorithm

无线传感器网络中通常利用连通支配集以形成虚拟骨干网进行分层次的路由。分析现有的几种去冗余分布式连通支配集构造算法,针对它们冗余度大,计算复杂,提出了一种改进的连通支配集构造算法,利用节点的度以及编号构成的集合取代节点编号作为节点的权值,采用DRN算法的节点覆盖思想,并扩展为当遇到闭合环路的情况下,采用保留闭合环路中权值大的节点去冗余的方法,在保证整个网络连通的情况下减少了连通支配集节点的总数。最后通过Matlab仿真分析,证明了算法的有效性。

Connected dominating set can be used to form a virtual backbone for the hierarchical routing in the wireless sensor network. Characteristics of the existing distributed algorithms are analysed,according to problems of the huge redundancy degree and complication of the computing,an enhancement algorithm based on DRN is proposed, which keeps the big weight node in the close circle to delete the redundant gateway nodes. The simulation on the Matlab shows that the new algorithm has better performance than some others.