传感器网络中高效的最小连通支配集求解算法

在无线传感器网络中，连通支配集被广泛应用于构建虚拟主干。由于求解最小连通支配集是一个NP难问题，许多近似算法被提出用于构建可用的最小连通支配集。针对当前近似算法存在的不足，我们提出了一个新的分布式近似构造算法—CDS-HG，该算法用层次图对无线传感器网络进行建模，算法用基于竞争的贪心策略从每一层选出最少的节点去支配下一层的所有节点。理论分析和模拟结果表明，CDS-HG算法产生的连通支配集是目前最小，并且其消息复杂度也是目前最低的。

Efficient algorithm for finding minimum connected dominating set in wireless sensor networks

The Connected Dominating Set (CDS) has been widely used for efficient routing in wireless sensor networks. Although finding the Minimum Connected Dominating Set (MCDS) in an arbitrary graph is a NP-hard problem, many approximation algorithms have been proposed to construct a serviceable CDS. To address the weaknesses of these existing algorithms, we proposed a new distributed approximation algorithm, CDS-HG, to construct the CDS for wireless sensor networks. This algorithm models a wireless sensor network as a hierarchical graph, in which a competition-based greedy strategy is used to select nodes at a certain level to route messages to the next level. Formal analysis and simulation studies show that our proposed CDS-HG algorithm generates the smallest CDS while requiring the least message complexity.