张 静，贾春福，杨 挺

(1.天津工业大学工程教学实习训练中心，天津300387;2.南开大学信息技术科学学院，天津300071;3.天津大学电气与自动化工程学院，天津300072)

集成了传感器、微机电系统和网络三大技术而形成的传感器网络是一种全新的信息获取和处理技术［1－3］。在无线传感器网络中，除了少数节点需要移动以外，大部分节点都是静止的。它要求设计的算法必须具有快速收敛的特性，减少路由查找的开销，提高路由发现的性能和效率。基于最小连通支配集的路由方法是一个很好的分层路由［4－7］方法，它将路由过程简化到生成的较小的子网中。这意味着在先应式路由中只有网关节点需要维持路由信息，而在反应式路由中研究空间被简化到这个MCDS中。MCDS中的网关节点构成了高一级的虚拟骨干网，而每个网关节点在自己的簇中都起着控制中心的作用，用于路由分组和广播路由信息。明显地，这种方法的有效性很大程度上依赖于发现和维持一个MCDS及与之相应的子网的大小。不幸的是，对大部分图来说，求一个MCDS的问题属NP－C问题［8］，在实际应用中需要设计近似求解算法。目前已有的算法主要分两类，集中式算法［9－10］和分布式算法［11－17］。集中式算法要求每个节点具有整个网络的拓扑结构信息，因而不适合移动网络多变的特点，可伸缩性差。分布式算法的主要思想是通过节点之间的局部交互操作在网络中迅速构造一个虚拟骨干网。

有关连通支配集的算法，国内外已经有许多人从事这一方向的研究。……