Abstract: Connected Dominating Set（CDS） has a wide range of application in wireless networks. The majority of existing algorithms for constructing CDS processes single node in each iteration. This paper proposes a greedy algorithm, GCDS, for dealing with multi nodes meantime, which chooses the currently smallest degree node and one or two nodes within its two-hop neighbors to decide. GCDS algorithm partitions the network nodes into dominators and dominatees, and minimizes the number of processing nodes when the rest nodes are disconnected after deleting the selected nodes. Finally, all dominators obtained are an approximate solution for MCDS. The simulation results on unit disk graphs to model wireless sensor networks show that GCDS achieves better performance in time complexity and outperforms related existing algorithms in terms of the size of CDS.

Key words: Minimum Connected Dominating Set（MCDS）, Unit Disk Graph（UDG）, greedy algorithm, Breadth-First Search（BFS）

摘要： 连通支配集（CDS）在无线网络设计中有着广泛应用，现有多数连通支配集算法每次处理一个节点。提出了一个同时处理多个节点的贪心算法（GCDS），依次选取最小度数节点以及该节点两跳内的一至两个节点为处理节点，当删除处理节点后剩余点不连通时减少处理的节点数，进而把节点分为支配点和受支配点；最终所有支配点构成一个近似最小连通支配集。在模拟无线传感器网络的单位圆盘图上的仿真结果表明，GCDS算法具有较低的时间复杂度，所得到的连通支配集大小优于已有算法。

关键词: 最小连通支配集, 单位圆盘图, 贪心算法, 广度优先搜索