无线传感器网络中的覆盖算法研究

论文摘要

无线传感器网络是由大量计算、通信及存储能力有限的传感器节点组成的特殊Ad-hoc网络,在军事和民用领域具有广泛的应用,是目前一个非常活跃的研究领域。覆盖问题是无线传感器网络中的一个核心问题。网络覆盖反映了网络所能提供的感知服务质量,可以使无线传感器网络的空间资源得到优化分配。节点调度和密度控制是减少能量消耗、延长网络生存时间的有效手段。本文针对无线传感器网络的覆盖问题展开了深入地研究,目标是在满足服务质量的前提下,节约节点能量,最大化网络生命周期。主要工作包括以下几个方面:（1）针对高密度、大规模的传感器网络,首先讨论了活跃节点的节点分布问题,指出了在局部小区域节点分布过于稠密和过于稀疏对传感器网络性能造成的影响。建立了传感器网络极大相似分布模型,用来量化传感器网络分组之间的节点分布均匀程度。证明了传感器网络极大相似分布问题属于NP-Hard问题,提出了两种近似求解算法,即基于分组的集中式和分布式节点调度覆盖算法,并给出了传感器网络为随机分布时,采用分组调度时平均覆盖率的理论上界值。对于合适范围的分组数,基于分组的节点调度覆盖算法能使各个组内的传感器节点较为均匀地分布在目标区域,得到的平均覆盖率接近理论上界值。（2）由于硬件成本、能耗以及误差范围等因素的限制,现有的定位技术难以满足传感器网络中覆盖算法的要求。提出了一种不依赖节点位置信息的节点调度覆盖算法LCSS。建立了参照节点和虚拟坐标的概念,并给出了选择参照节点以及生成节点虚拟坐标的方法。对于不同的传感半径、通信半径以及应用要求,给出了参照节点个数的最小临界值。分析表明当网络中存在一定个数的参照节点时,节点的虚拟坐标能够代替节点的绝对坐标,并指出了它的适用范围。理论分析和仿真实验表明,LCSS算法对节点的时钟异步有很好的鲁棒性。和其它的与节点位置无关、基于分组的覆盖方案相比,不依赖节点位置信息的节点调度覆盖算法有更好的覆盖性能,组内节点分布更加均匀。（3）对于传感器网络在军事监测等方面的应用,目标区域内若存在着盲点区域可能导致极其严重的后果,要求任意时刻传感器网络能够完全覆盖目标区域,并保证网络的连通性。在保证完全覆盖和网络连通的前提下,设计了一种基于网格的密度控制算法GDCA。仿真实验表明,和其它连通覆盖集求解算法相比,GDCA算法能够获得更小的连通覆盖集。且这种算法属于分布式算法,具有良好的扩展性,节点的传感区域可为任意凸形区域,更符合实际情况。（4）当传感器网络应用于灾难援助等领域,要求传感器网络对空间数据查询消息进行快速的回应,以帮助进行灾难救援。而快速的生成连通覆盖集是传感器网络快速回应空间数据查询消息的前提。从快速回应用户或者其他指令中心发出的空间数据查询的应用需求出发,讨论了如何快速有效的构造查询区域的连通覆盖集问题,并提出了一种基于正方形的连通覆盖集快速实现算法SFAMCCS。通过将查询区域按一定尺寸的正方形剖分,节点利用临近节点的位置及覆盖的格点等信息构造查询区域的连通覆盖集。理论分析和仿真实验表明,SFAMCCS算法通过节点协作的方式,在较短的时间内得到的连通覆盖集大小可与已有集中式算法相当,与类似的其他算法相比,在运行时间和连通覆盖集大小等方面具有更优的性能。（5）在节点不能获取准确位置信息的条件下,如何进行节点调度以满足传感器网络长时间充分均匀的覆盖目标区域并确保网络连通,是当前具有挑战性的问题。在覆盖算法LCSS的基础上,本文提出了基于虚拟坐标的节点调度方案SSVC。SSVC方案通过将传感器节点中的某一些节点划分到几个不同的分组,保证了各个分组的连通。算法分析和仿真实验表明,本文提出的方案在覆盖率、维持分组连通时额外加入到分组内的节点个数,以及网络生存时间等性能上均优于与节点位置无关的节点随机调度协议。

论文目录

• 摘要
• Abstract
• 插图索引
• 附表索引
• 第1章 绪论
• 1.1 选题背景及研究意义
• 1.2 无线传感器网络概述
• 1.2.1 传感器节点特征
• 1.2.2 传感器网络特征
• 1.3 无线传感器网络的应用
• 1.3.1 军事应用
• 1.3.2 环境监测和预报系统
• 1.3.3 建筑物状态监控
• 1.3.4 医疗护理
• 1.3.5 其他方面的应用
• 1.4 主要工作及论文的组织结构
• 1.4.1 本文主要工作
• 1.4.2 论文的组织结构
• 第2章 传感器网络覆盖算法的研究现状
• 2.1 节点感知模型
• 2.2 性能评价标准
• 2.3 节点覆盖算法的分类
• 2.4 典型的覆盖算法分析
• 第3章 基于分组的分布式节点调度覆盖算法
• 3.1 引言
• 3.2 现有的工作
• 3.2.1 PEAS算法
• 3.2.2 GAF-like算法
• 3.2.3 随机调度覆盖算法
• 3.3 问题描述及分析
• 3.3.1 网络模型
• 3.3.2 问题分析
• 3.3.3 极大相似分布模型
• 3.3.4 平均覆盖率的理论值上限分析
• 3.4 极大相似分布的近似求解算法
• 3.4.1 基于分组的集中式节点调度覆盖算法
• 3.4.2 基于分组的分布式节点调度覆盖算法
• 3.5 性能评价
• 3.5.1 工作节点分布
• 3.5.2 覆盖率的变化
• 3.5.2 失效节点数量随运行时间的变化
• 3.5.3 网络生存时间
• 3.5.4 讨论
• 3.6 小结
• 第4章 不依赖节点位置信息的节点调度覆盖算法
• 4.1 引言
• 4.2 现有的工作
• 4.2.1 利用边界节点构造虚拟坐标的方法
• 4.2.2 利用三个信标节点构造虚拟坐标的方法
• 4.3 虚拟坐标及分析
• 4.3.1 参照节点和虚拟坐标的定义
• 4.3.2 虚拟坐标及分析
• 4.3.3 选择参照节点及生成虚拟坐标的方法
• 4.3.4 复杂性分析
• 4.4 不依赖节点位置信息的节点调度覆盖算法
• 4.5 性能分析
• 4.5.1 特殊分布
• 4.5.2 随机分布
• 4.5.3 时钟异步对于覆盖的影响分析
• 4.6 小结
• 第5章 基于网格的密度控制算法
• 5.1 引言
• 5.2 现有的工作
• 5.2.1 贪婪算法
• 5.2.2 CVT+MST
• 5.3 问题描述及分析
• 5.3.1 网络模型
• 5.3.2 问题描述
• 5.3.3 网格大小选择
• 5.4 基于网格的密度控制算法GDCA
• 5.4.1 基于网格的密度控制覆盖算法GCDCA
• 5.4.2 基于网格的密度控制算法GDCA
• 5.5 性能评估
• 5.5.1 在不同节点个数时连通覆盖集的大小
• 5.5.2 在不同通信范围时连通覆盖集的大小
• 5.6 小结
• 第6章 基于正方形剖分的连通覆盖集快速实现算法
• 6.1 引言
• 6.2 问题描述及分析
• 6.2.1 网络模型
• 6.2.2 问题描述及性质分析
• 6.3 基于正方形剖分的连通覆盖集快速实现算法
• 6.3.1 相关定义
• 6.3.2 算法描述
• 6.4 算法性能分析
• 6.4.1 运行时间
• 6.4.2 连通覆盖集大小
• 6.5 小结
• 第7章 基于虚拟坐标的节点调度方案
• 7.1 引言
• 7.2 现有的工作
• 7.3 基于虚拟坐标的节点调度方案
• 7.3.1 LCSS算法的连通特点
• 7.3.2 分布式连通算法
• 7.4 性能评价
• 7.4.1 覆盖率
• 7.4.2 维持分组连通时额外加入到分组内的节点个数
• 7.4.3 网络生存时间
• 7.5 小结
• 结论与展望
• 参考文献
• 致谢
• 附录A 攻读学位期间发表的学术论文目录
• 附录B 攻读学位期间参加的科研课题