论文部分内容阅读
无线传感器网络作为进化计算中崭新的一章,已经被证明了对诸多的领域,如国防安全、监控、环境监测、农业、以及医疗,起到了巨大的推动作用。由于它在物理世界以及数字世界之间的交互能力,无线传感器网络可以帮助人们有效的收集信息,并执行用户制定的策略或命令。这个特性在实时监控的应用场景如建筑物防火或者敌对区域监控中显得特别的重要。在这些应用环境中,传感器网络是一种用来监控远距离或者有敌意物理目标的行之有效的手段。而通常的情况下,不仅仅是对这些物理目标进行监控,由于物理目标重要程度的不同,他们有不同的Quality of Service (QoS)需求,也即,不同的目标可能需要不同的传感质量,如监控节点的数量,数据采集率等。由于传感器节点是由电池供电,因此节能的问题就显得非常重要,如果在保证覆盖需求的情况下延长网络的使用寿命是本论文主要的研究方向。
在前人的工作中,有很多是针对目标监控这个应用场景,他们或者是使用了启发式算法来求解,这样造成了算法的性能难以衡量毕竟对解出来的结果没有保证;或者是通过松弛一些实际的限定来降低问题的复杂度,从而进行求解。这样的情况下,对某些问题实用的特定算法对其他的变种问题就难以应用,算法不具有普适性。据目前调研的结果,在这些问题上都没有相关的问题给出理论上的实际进步。为了填补这方面研究的空白,本文试图构建一个普适性的优化框架,可以被应用到目前已知存在的一系列的目标监控问题中。这个优化框架由以下几个方面组成,1)对传感器网络中有QoS需求的静态目标的覆盖策略这一部分中,探讨了无线传感器网络中的有QoS需求的静态目标的覆盖问题,也即,不同的目标可能需要不同的传感质量,如监控节点的数量,数据采集率等。由于这个问题内在的复杂度(被证明为NP完全问题),前人的工作基本都集中在提出启发式算法,由于缺乏理论的界限及比较的基准,这些算法的性能难以保证。
为了填补这方面的空白,首先通过对覆盖需求的松弛,即从每个时刻至少被K个节点覆盖松弛到平均被K个节点覆盖,利用线性优化进行建模,建立了一个生命周期的理论上界。这个理论上界的意义在与提供了一个比较的基准。一个基于列生产算法的策略被提出来寻找一个可行的调度时间表,这个时间表定义为从哪个时刻到哪个时刻,哪些节点负责哪些目标的监控。大量的实验数据验证了算法的有效性,也即取得的有效解与理论最优值之间的距离很小。
2)对传感器网络中有路由需求的静态目标的覆盖策略在这一部分中,考虑了在异构无线传感器中的目标覆盖问题,其中不同的目标需要被运行在不同取样率下的不同种类的节点所覆盖。优化的目的在与延伸网络的生命周期,同时要保证相异的覆盖需求,即不同的目标可能需要不同数目的,不同种类的,运行于不同采样率的节点。这是个特别困难的问题,由于需要同时的考虑目标覆盖与数据路由问题。
为了克服这两种因素带来的复合复杂度,建立了一个优化模型。这个普适的模型允许目标的覆盖需求在不同层面上的变异。不但如此,它还抽象了不同的节点数据传输模型。进一步的,为了有效的求解这个覆盖的优化模型,在列生产算法的基础上进行了进一步的优化工作。主要的想法在与:一列相对于一个可行解;在每次的迭代中寻找一个拥有当前最优生命周期的解,并且判断是否为最优解,如果不是,则继续在最优可能获得最优解得局部解空间搜寻。为了加速迭代的收敛速度,通过一个随机算法来寻找初始的可行解。通过大量的实验,系统的对可能影响网络生命周期的因素,如取样率,传输能量模型,通讯半径,传感半径等,实际对网络的影响。并揭示了一系列有趣的现象。
3)对传感器网络中有局部覆盖需求的静态目标的覆盖策略在这一部分工作中,考察了有局部覆盖需求的监控网络中,如何最优化网络的生命周期。提出了一个新的局部覆盖模型:目标其实并不需要在任何时刻都被某一个或者多个节点所覆盖,因为这会导致网络的生命周期被某些瓶颈节点所制约。相对的,局部的覆盖,如80%的时间内都有被覆盖,就已经可以满足覆盖的要求。在这个模型下,首先探讨了前人工作所采用的方法:通过将节点划分为相交的子集,每个时刻有且只有一个子集被激活,任何这样的单个子集可以满足覆盖需求。以这样的子集为调度的目标建立优化调度算法。这种方法的缺陷在与非常高的计算复杂度已经没有性能保障。
展示了在新的覆盖模型下,如何在多项式时间内得到局部覆盖问题的最优解。首先建立了一个线性优化模型,这个模型只参考某个节点覆盖某个目标的总的时间,这样就可以建立起网络生命周期的理论上界。基于这个上界,建立了一个节点调度策略以寻求一个最有的时间表可以达到这个上界。给出了算法的有效性的理论证明。
将提出的算法与被广泛使用的列生产算法想比较,发现提出的算法在计算时间,以及结果上要大大优于列生产算法。通过设计一些新的实验,考察了不同的网络变量,如局部覆盖需求变量,网络中节点的数目、目标的数目、传感半径,对生命周期的影响,由此揭示了一些内在的规律。
4)对传感器网络中的动态目标的跟踪策略为了有效的对无线传感器网络监测区域中出现的运动目标节点,一种新的预测模型被提出,在综合目标在当前时刻前的信息如移动方向,移动速度的基础上,预测目标未来可能出现的局域(Potential future area,PFA)。并且提出了一种相应的通讯协议,以保证基站与传感器节点之间的稳定的,实时的数据传输。核心算法在于:在一个PFA中只激活一个传感器节点以节约能量,这个策略可以显著的延长网络的寿命。通过理论分析与模拟实验,提出的算法在其他相似算法比较中在能量消耗,通讯带宽需求等方面胜出。