郑 婵，尹 令，孙世新

(1.电子科技大学计算机学院，成都610054;2.华南农业大学信息学院，广州510642)

无线传感器网络是由大量具有感知、数据处理和通信能力的传感器节点组成的网络，具有低功耗、低成本、智能化、分布式、自组织等特点，在军事、环保、医疗、商业、农业、灾害预测及救援等领域都有着广阔的应用前景。由于没有类似蜂窝通信中基站的骨干基础，且受到传感器无线收发装置传输半径和节点能量的限制，多数的节点之间都不能直接进行通信，只能通过若干中间节点形成的虚拟骨干网进行多跳交换数据和通信。在无线传感器网络中构造虚拟骨干网是优化网络结构的一个重要手段，而构建虚拟骨干网最常用的技术就是计算网络的连通支配集CDS(Connected Dominating Set)。CDS中的支配节点构成高一级的骨干节点控制着全网的路由、维护和管理。在单位圆盘图UDG(Unit Disk Graph)的网络模型中构造最小连通支配集MCDS(Minimum CDS)早已被证明是NP完全问题［1］，在节点具有中等规模以上(一般节点数量大于40)时，只能构造近似的最小连通支配集。近十年来，关于构造最小连通支配集已经有较为深入而成熟的研究，研究学者们提出了各种算法来构造近似的最小连通支配集［2］。

随着无线传感器网络规模的增大和密集程度的增加，采用近似的最小连通支配集算法获得的支配集节点数目依然较大。为了解决这一问题，很多学者［3-8］提出d-hop连通支配集(d-hop CDS)来大大减少支配集节点数量。d-hop CDS指的是受支配节点和支配节点之间的跳数最多可达d跳。……