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

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）