无线传感器网络目标覆盖问题研究

论文摘要

无线传感器网络(WSN)早已成为进化计算体系研究的热点,对如国防安全、环境监测、智能家居、农业及医疗等诸多领域起到很大的推动作用。基于无线传感器网络(WSN)能够很好的联络物理与数字世界,它帮助人们更有效的观测目标、采集信息,进而执行制定的策略。这标示无线传感器网络在如森林火灾或战场环境等许多目标监控的情形中有着很大的发展应用潜力。但鉴于对这一类系统的复杂度及最重要的目标覆盖问题尚未很好的解决,并且很少有深层次的理论研究,这都阻碍了无线传感器网络在实际应用中的推进。本论文针对这方面研究的不足建立普遍适用的优化模型,并且进一步进行理论分析,提出实际有效的节能算法,推进无线传感器网络在实际中的应用。本文的具体的研究内容：(1)针对同构无线传感器网络静止目标覆盖问题,提出借由松弛及基于列生成算法两个理论。前者建立了以线性优化为基础的网络生命周期的上界方程,此理论为有效算法的性能比较建立了基准。基于分治迭代思想的列生成算法克服了前人所提贪心及启发式算法无性能保障的不足。重要的是,所提理论具有普适性,即对不同的覆盖问题只需调整优化框架中的某些细节,就可以产生有效的算法。(2)针对异构无线传感器网络中有路由需求的静止目标覆盖问题,重点解决在保持对不同种类、不同需求的目标覆盖情况下,如何通过对路由的调度最优化网络的生命周期。在对问题进行数学建模后,提出改进的列生成算法,它把基于列生成的算法与可取得较好初始可行基加快收敛速度的随机选择算法结合起来,并且改进算法终止条件进一步加速收敛,进而求得最优解。实验探究和分析了网络参数(如初始可行基、通讯半径、传感半径等)对网络生命周期的影响,验证了算法的有效性,该算法可对建立实际的系统提供指导。(3)提出目标非整型覆盖问题,并建立新的覆盖模型。新的非整型覆盖模型：目标其实并不需要在任一时刻都被覆盖,若这样,网络的瓶颈目标将大大限制生命周期,相对地,非整型覆盖,如80%的时间内被覆盖,就可以满足覆盖要求。基于新的覆盖模型设计了最优节点分配算法。通过实验验证了该算法相比于列生成算法在计算时间及性能参数等方面都有明显优势。

论文目录

• 致谢
• 摘要
• Abstract
• 1 绪论
• 1.1 研究背景与意义
• 1.2 国内外研究概况
• 1.3 研究内容
• 1.4 研究方案与目的
• 1.5 论文结构
• 1.6 本章小结
• 2 静止目标覆盖问题
• 2.1 引言
• 2.2 问题描述
• 2.3 网络生命周期上界
• 2.3.1 松弛MINLP得到生命周期上界
• 2.3.2 松弛覆盖需求得到生命周期上界
• 2.3.3 两种上界间的联系
• 2.4 列生成算法
• 2.4.1 初始可行基
• 2.4.2 分治
• 2.4.3 子问题优化
• 2.5 实验探究
• 2.5.1 算法性能验证
• 2.5.2 CG算法与前人算法的比较
• 2.5.3 网络参数对生命周期的影响
• 2.6 本章小结
• 3 异构WSN中目标覆盖算法设计
• 3.1 引言
• 3.2 问题描述
• 3.3 问题建模
• 3.3.1 工作组
• 3.3.2 问题的数学建模
• 3.4 列生成算法
• 3.4.1 随机算法
• 3.4.2 主问题与子问题
• 3.4.3 改进终止条件
• 3.5 实验探究
• 3.5.1 实验设置
• 3.5.2 实验结果及分析
• 3.6 本章小结
• 4 静止目标的非整型覆盖算法研究
• 4.1 引言
• 4.2 非整型覆盖问题
• 4.2.1 问题描述
• 4.2.2 系统及问题建模
• 4.3 节点分配最优算法
• 4.3.1 算法设计
• 4.3.2 算法演示及分析
• 4.4 实验探究
• 4.4.1 节点分配最优算法与列生成算法的比较
• 4.4.2 非整型覆盖需求及瓶颈目标对网络生命周期的影响
• 4.4.3 不同网络参数对网络生命周期的影响
• 4.5 本章小结
• 5 总结与展望
• 5.1 全文总结
• 5.2 展望
• 参考文献
• 作者简历
• 学位论文数据集