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

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

作　　者：谢嵘[1] 齐德昱[1] 李拥军[1] 钱正平[1] 

机构地区：[1]华南理工大学计算机科学与工程学院

出　　处：《计算机应用》2008年第2期342-344,共3页journal of Computer Applications

摘　　要：在无线传感器网络中,连通支配集被广泛应用于构建虚拟主干。由于求解最小连通支配集是一个NP难问题,许多近似算法被提出用于构建可用的最小连通支配集。针对当前近似算法存在的不足,我们提出了一个新的分布式近似构造算法—CDS-HG,该算法用层次图对无线传感器网络进行建模,算法用基于竞争的贪心策略从每一层选出最少的节点去支配下一层的所有节点。理论分析和模拟结果表明,CDS-HG算法产生的连通支配集是目前最小,并且其消息复杂度也是目前最低的。The Connected Dominating Set （CDS） has been widely used for efficient routing in wireless sensor networks. Ahhough 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.

关 键 词：无线传感器网络 连通支配集 分布式算法 层次图 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]