无线传感器网络中的连通支配集求解算法

Connected Dominating Set Algorithm of Wireless Sensor Network

连通支配集在无线传感器网络中有着重要的作用,通过对连通支配集的深入分析得到了关于连通支配集的一个新特性,即最小连通支配集是图的一棵包含最多叶子节点的生成树中的非叶子节点的集合。根据这个结论设计了一种全新的连通支配集求解算法,即通过建立一棵含叶子节点较多的生成树来寻找一个较小的连通支配集。仿真实验表明,新算法较前人的算法有明显的改进。

Connected Dominating Set （CDS） plays an important role in Wireless sensor network.An important conclusion was got through analysis of CDS,which is the smallest CDS of a simple connected graph is the non-leaf nodes of a spanning tree with most leaf nodes.A new CDS algorithm was designed according to this conclusion.Simulations showed that the new algorithm could achieve better performance than others.