无线传感器网络目标覆盖的研究.pdf

摘要 摘要 无线传感器网络作为进化计算体系新的研究热点，已经在诸多的领域，如 国防安全、环境监控、农业、以及医疗等方面，起到了巨大的推动作用。得益 于它在物理世界与数字世界之间的交互能力，无线传感器网络可以帮助人们有 效的观测目标、收集信息，并执行用户制定的策略或命令。此特性标示着在目 标监测的应用场景如森林环境监测或者敌对区域监控中，传感器网络有着巨大 应用前景。然而，有鉴于此类系统的复杂度，其核心问题：目标覆盖，没有得 到很好的解决，缺乏深度的理论分析。这阻碍了传感器网络在监测系统中的有 效应用。为了填补这方面研究的空白，本文将构建一个普适性的优化框架，以 理论上的深度研究为基础，建立一系列实际有效的节能算法，从而加速传感器网 络在实际应用中的发展。具体而言，本文的研究工作包括如下内容： (1)针对同构无线传感器网络中的静止目标覆盖问题，提出了两项理论研究 成果。第一项成果为：借由松弛技术，建立了基于线性优化模型的网络生命周 期上界优化方程。此成果的意义在于提供了有效的算法性能比较基准，为发展 高效算法，建立了理论基础。第二项成果为基于列生产的有效算法，克服了前 人文献所提贪心算法、启发式算法没有性能保障的缺陷。 具体而言，本章首先通过对覆盖需求的松弛，基于线性优化模型对问题进 行了数学建模，从而建立了多项式时间复杂度的生命周期上界优化方程。这个 上界的意义在与提供了算法性能比较的基准。为了克服覆盖问题的内在复杂度， 本章提出了一个基于列生产的有效算法。算法的核心思想在于“分治与“迭 代”，也即，将复杂的原问题分割为相对简单的两个关联子问题，通过迭代循环 求解子问题来逼近最优值。理论的分析证实了算法的有效性，而试验结果进一 步证实了，相较于前人文献中的启发式算法与贪心算法，本章提出的算法在迭 代次数、求解时间、算法性能上，都有了显著的提升。 更重要的，本章展示了所提理论的可扩展性与普适性：针对不同的目标覆 盖问题，通过简单调节优化框架中的细节，产生有针对性的有效算法。 (2)针对异构无线传感器网络中静态目标的实时覆盖问题，设计了基于跨层 优化的数学建模，并在此基础上，提出了基于列生产的有效算法。为了探寻不 同的网络参数，如节点个数、目标个数、覆盖需求、传输半径、传感半径等， 对网络生命周期的影响，本章设计了大量的试验。试验的结果揭示了一系列现 象与规律，对实际建立监测、覆盖系统有着积极的指导作用。 具体而言，本章考虑了在异构无线传感器中的目标实时覆盖问题，其中不 同的目标需要被运行在不同取样率下的不同种类的节点所覆盖。优化的目的在 I 摘要 与延伸网络的生命周期，同时要保证相异的覆盖需求，即不同的目标可能需要 不同数目的，不同种类的，运行于不同采样率的节点。由于需要同时的考虑目 标覆盖与数据路由问题，问题的复杂度较高。 为了克服这两种因素带来的复合复杂度，本章建立了一个联合优化模型。 这个普适的优化模型允许目标的覆盖需求在不同层面上的变异。不但如此，它 还抽象了不同类型节点的数据传输模型。进一步的，为了有效的求解这个覆盖 优化模型，对基础的列生产算法进行了进一步的优化。主要的想法在与：一列 相对于一个可行解；在每次的迭代中寻找一个拥有当前最优生命周期的解，并 且判断是否为最优解，如果不是，则继续在最有可能获得最优解的非整型解空 间搜寻。为了加速迭代的收敛速度，提出了一个随机算法来寻找初始的可行解。 通过大量的实验，系统的考察了对可能影响网络生命周期的因素，如取样率、 传输能量模型、通讯半径、传感半径等，实际对网络的影响。并揭示了一系列 有趣的现象与规律，对实际建立监测、覆盖系统有着积极的指导作用。 (3)提出了无线传感器网络中静态目标的非整型覆盖问题，并利用此新覆盖 模型，设计了多项式时间复杂度的最优算法，填补了理论研究的空白。通过理 论分析与试验验证，证实了该算法在计算时间复杂度、算法性能上都显著由于 前人文献中的启发式算法。为了方便将该算法应用到实际系统中，本章提出了 该算法的分布式版本，并详细说明了实际实现的框架及细节。 具体而言，通过对实际监控系统模型的抽象，本章提出了一个新的非整型 覆盖模型：目标其实并不需要在任何时刻都被某一个或者多个节