无线传感器网络的目标监控.pdf

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