凌 飞，吴振华

(南昌航空大学软件学院，南昌 330063)

集成了传感器、微机电系统和网络三大技术的无线传感器网络(Wireless Sensor Networks，WSN)，近年来受到人们的广泛关注［1－2］。WSN是一种大规模、无线、自组织、多跳、无基础设施支持的网络，其中节点成本较低、体积较小，具有传感、数据处理和短距离无线通信等功能，大部分节点不移动，被随意撒布在监测区域内，在军事国防、环境科学、医疗健康、空间探索以及商业应用等领域具有广阔的应用前景［3－4］。为了提高广播效率、节能等，最小连通支配集(Minimum Connected Dominating Set，MCDS)被广泛应用于形成虚拟骨干网的分层路由协议。然而在一个图中求解MCDS是一个NP难问题，在实际应用中通常只能采用近似求解算法。

有关MCDS的构造算法，目前主要分为两类:集中式算法［5－6］和分布式算法［7－13］。集中式算法要求把整个网络的拓扑信息集中到某个中心节点，而这将需要花费极大的通信代价和出现局部节点通信量过大的问题，因而不适用于WSN，但获得的连通支配集(Connected Dominating Set，CDS)通常比分布式的小，这是因为集中式算法拥有整个网络的拓扑信息。文献［5］提出了一种集中式算法，其主要思想是把最大度的节点作为根节点开始构建一棵树，树包含图中所有节点，树的叶子节点为非支配点，非叶子节点为支配点。该算法时间复杂度高。文献［6］在文献［5］的基础上证明了MCDS是图的一棵包含最多叶子节点的生成树的非叶子节点集合，根据这个结论设计了一种新的构造MCDS的算法。分布式算法只需要知道当前节点的局部信息，各个节点独立地计算自己的连接情况，具有较强的自组织能力。……