An Algorithm for Minimal Connected Cover Set Problem in Wireless Sensor Networks
无线传感器网络最小连通覆盖集问题求解算法

降低能耗以延长网络生存时间是无线传感器网络设计中的一个重要挑战.在传感器节点高密度部署的环境中,在保证网络性能的前提下,仅将最少量的节点投入活跃工作状态,而将其余节点投入低功耗的睡眠状态,是一种节约系统能量的有效方法.如何计算同时满足"覆盖要求"(工作节点必须能够完全覆盖目标区域)和"连通性要求"(工作节点组成的通信网络必须是连通的)的最小节点集合,是一个NP难问题.设计了一种基于目标区域Voronoi划分的集中式近似算法(centralized Voronoi tessellation,简称CVT),用于计算完全覆盖目标区域所需要的近似最小节点集.当节点通信半径大于等于2倍感知半径时,CVT算法构造的节点集是连通的;当节点通信半径小于2倍感知半径时,设计了一种基于最小生成树(minimum spanning tree,简称MST)的连通算法来计算确保CVT算法构造的覆盖集连通所需的辅助节点.理论分析和实验数据表明,CVT(+MST)算法的性能在时间复杂性和连通覆盖集大小方面都优于已有的贪婪算法.