一种改进的Ad Hoc无线网络连通支配集生成方法

该文研究了Ad hoc无线网中连通支配集（CDS）的生成方法，并对CDS算法做了两个方面的改进:1）通过引入拓扑相关信息的特征矢量中心性值进行节点编号，避免节点缩减时的随机性，使节点缩减与实际网络拓扑紧密联系；2）CDS算法忽略了最大编号节点的可缩减性，为此改进了该算法并提出新规则实现最大编号节点的缩减判定。该方法解决了CDS算法在生成连通支配集时存在的完全NP难问题，而且可得到条件最优连通支配集。仿真结果验证了改进算法的优良特性。

An Improved Formation Method of Connected-Dominating Set in Ad Hoc Wireless Networks

The formation method of connected-dominating set (CDS) in ad hoc wireless network is studied and improved. There are two improvements in this paper, the first one is numbering the nodes by introducing the eigenvector center value of the network topology information, which avoids the randomness during node reduction and makes the node reduction be related to the actual network topology closely. The second one is that CDS algorithm ignores the removal of the largest numbered nodes, the improved one proposes a new rule to achieve the reduction of the maximum number nodes. Thus, the improved method solves the NP-complete problem of the CDS algorithm in formation method of connected-dominating set and achieves the conditional optimal connected-dominating set. The simulation results show the excellent characteristics of the improved method.