最小连通支配集在无线传感器网络(Wireless Sensor Networks,WSN)中发挥着重要的作用,它可以作为一个“虚拟骨干网”从而可以减少节点的能量损耗、网络拓扑维护的开销,减轻广播风暴的影响等。构造一个最小连通支配集被证明是一个NP完全问题,并且无线传感器网络中的节点具有能量、存储和计算方面的约束,以及无线传感器网络的无中心自组织成网、多跳通信的特征,因此许多学者对在无线传感器网络中构造最小连接支配集这一问题展开了广泛而又深入的研究。作者以静态的无线传感器网络为研究目标,设计了四个近似最小连通支配集的分布式算法。算法-Ⅰ是一个完全异步并行的算法,网络中的每个节点异步并同时执行相同的算法且只根据一跳邻居的消息来决定自己是否加入连通支配集。根据最大独立集亦是一个支配集,算法-Ⅰ首先构造一个最大独立集,然后通过“信息三跳中继”结合相应的规则使其它一些节点加入最大独立集,使最大独立集连通,最终生成连通支配集。在算法-Ⅱ中,以“有效度”代替节点的度数来作为选取属于最大独立集中的支配点的标准,可以有效减少生成的连通支配集的大小。算法-Ⅰ与算法-Ⅱ构建的近似最小连通支配集的收敛时间与网络规模、拓扑结构等直接相关,存在收敛时间不可直接控制和估计等问题。因此作者设计了算法-Ⅲ。算法-Ⅲ分为两个阶段,分别为初始化阶段和状态更新阶段。通过对不同规模和拓扑结构的无线传感器网络进行计算机仿真,可以得到构造近似最小连通支配集所需的相关时间参数。在算法-Ⅳ中,作者首次提出把两个支配点之间的节点个数等效转化成带有权值的路径,从而转化成有权图,然后在这个图中找到一个最小生树来对连通支配集进行优化的思想。实验仿真结果表明,算法-Ⅳ具有非常出色的性能表现。