论文部分内容阅读
近年来,无线传感器网络在许多应用领域中得到广泛部署,并表现出更多的应用潜力。节点部署和覆盖控制是无线传感器网络的基本问题,节点部署方式影响了网络的构建成本、覆盖质量、拓扑结构和路由算法,是覆盖控制问题的基础。覆盖控制则是利用网络的冗余性,通过节点调度、密度控制等手段,在保证网络覆盖性能的前提下,提高节点的能量效率,延长网络生存期的方法。本文从提高能量效率的角度,研究了包括最少节点部署和多种覆盖控制方法在内的若干问题,主要研究工作有:(1)无线传感器网络的数据传输特性使得能量消耗在空间上分布不均衡,导致节点均匀部署时网络的能量效率不高,因而本文提出和解决了最少节点部署问题,即如何部署最少的节点以满足覆盖率和网络生存期的要求。为解决上述问题,首先建立了传感器网络的能量消耗模型。在此模型下,本文分别给出了受控和随机两种情形下的节点数量/密度递减部署策略:1)节点数量递减的重叠放置。受三角点阵排列的良好特性启发,在点阵中的不同位置点上放置不同数量的节点,靠近sink的位置点放置的节点多,远离sink的位置点放置的节点少。2)密度递减部署。根据随机部署模型,估算满足覆盖率要求时的最少活跃节点密度,进而求出给定网络生存期时的每个子区域应部署的最小节点密度。总的说来,节点密度随距离变化,内层区域部署的节点密度大,外层区域部署的节点密度小。理论分析和实验仿真表明,节点数量递减的重叠放置和密度递减的随机部署比节点数均等放置和随机均匀部署所需的节点数量小,剩余能量少,节点的能量效率高。(2)由于异构节点可以提高传感器网络的生存期和可扩展性,因此针对异构网络环境,本文提出和研究了异构传感器网络的最小转发连通覆盖集(MRCSC)问题,即找到满足下面两个条件的最少活跃节点集合:1)完全覆盖任务区域。2)转发连通,每个活跃节点至少存在一条到达任一异构节点的可达路径。由于MRCSC问题是NP-难的,本文给出了两阶段的近似求解方法:1)寻找近似最小覆盖集。三角点阵排列具有节点数渐近最少的性质,但是在随机部署的网络中很难确保每次都能够在点阵的位置点上恰好找到节点,因而我们给出了限制点阵不规则性传播的条件,并以此为依据设计了分布式构建近似最小覆盖集(MSC)的算法。2)验证和增强转发连通性。为了判定集合的转发连通性,我们证明了集合转发连通的判定条件,进而又将增强转发连通问题转化为寻找转发连通树的问题。在给出的分布式算法中,通过转发连通验证、叶节点请求增强的迭代过程实现了覆盖子集的转发连通。仿真实验表明,MSC的覆盖性能与OGDC算法接近,但是无需邻居节点的角度信息。转发连通增强过程则通过增加少量节点就可以明显改善MRCSC的转发连通性能。(3)为了监测和感知连续出现的目标形成的目标流,本文提出了面向目标流的反应覆盖方法。反应覆盖方法根据目标流的特性,动态调节覆盖质量,主要思想是:目标流没有进入任务区域时,节点工作在低占空比的监视状态,以保存能量;当目标流进入任务区域时,节点被唤醒为目标流提供高质量的感知覆盖;当目标流离开后,节点又进入低能耗的监视状态。因此反应覆盖解决了如下问题:1)最小感知占空比。监视状态下,为了能够可靠地检测进入任务区域的目标流同时考虑能量效率,给出了节点感知占空比的下界。2)唤醒范围。发现目标流后,估算目标被发现前的平均移动距离,唤醒平均移动距离内的节点以提供可靠的感知覆盖,唤醒的节点数满足给定的覆盖质量要求。3)持续工作时间。为了给目标流提供不间断的感知覆盖,节点被唤醒后持续工作一段时间以等待下一个目标的到来,持续工作的时间取决于目标流的到达间隔时间。4)目标流离开的判决条件。使用假设检验方法检查目标的到达时间间隔样本值,节点可以准确判定目标流的离开,降低了目标流离开任务区域的误判率。仿真实验数据表明,目标流的覆盖质量接近于静态覆盖,但能量效率高,网络生存期达到静态覆盖的4-7倍,更适合对目标流的感知覆盖。(4)针对有向感知能力的无线传感器网络,本文研究了点目标有向多覆盖集问题,目标是找出尽可能多的有向覆盖集合。由于有向节点可以调节感知方向,因而分为两步求解有向多覆盖集问题:1)方向优化。首先提出了改进的贪婪方向优化算法(EGA),EGA选取工作方向的依据是覆盖最多还未被覆盖的目标,因而算法复杂度低,但覆盖资源分配不均。针对EGA的不足,进而又提出了公平的方向优化(EDO)算法。EDO算法中通过效用函数评估各个方向上的覆盖收益,覆盖度越低的目标其效用值越大,反之越小,因而临界目标被优先覆盖,覆盖资源被公平分配。2)节点调度。基于局部覆盖集提出了邻居感知调度(NSS)协议。NSS将节点划分为多个覆盖集,每个覆盖集轮流工作一个周期。在每个工作周期末开始竞争活跃节点,即当活跃节点判定其存在一个局部覆盖集时活跃节点在下一个工作周期内睡眠,否则继续工作,以达到节点能量均匀消耗的目的,最大化网络生存期。仿真实验表明,EGA和EDO都大大改善了目标的覆盖质量,但EDO的性能比EGA算法高了近30%。NSS的性能与集中式的Greedy-MSC算法的接近,但NSS的分布式特性使其更为实用。综上所述,本文针对能量高效的节点部署和覆盖控制问题提出了相应的解决方案,对于推进无线传感器网络的研究和实用化具有一定的理论意义和应用价值。