无线传感器网络覆盖控制技术研究

论文摘要

无线传感器网络是集信息获取、处理和传输为一体的网络,在工业、农业、军事、环境监控、生物医疗、城市管理和抢险救灾等领域有着非常广泛的应用前景。覆盖控制是无线传感器网络服务质量QoS的基本问题,其目的是通过在网络中分布传感器节点感知监测区域或目标对象,以达到信息获取的完整性和有效性。覆盖控制决定了传感器网络对物理世界的监测性能,是推动传感器网络从理论走向实用的必经之路。然而,传感器网络能量受限、规模大、动态性强,给覆盖控制的研究带来了巨大的挑战。此外,传感器网络与应用密切相关,新的应用场景层出不穷,覆盖控制的新问题不断涌现并亟待解决。传感器节点的感知模型直接决定了其覆盖范围和监测能力,是覆盖控制的研究基础。由于传感器节点的信息获取与应用直接相关,不同类型的节点有不同的感知能力。而已有的研究工作大都局限于圆盘感知模型,对实际应用中节点感知模型多样性的支持较弱。同时,已有工作大都利用静止传感器进行覆盖控制,但是随着移动传感器的发展,在一些新的应用场景中,利用移动节点解决覆盖控制问题具有更大的优势。本文致力于研究新型感知模型的覆盖控制问题,同时发掘新的应用场景,研究支持移动传感器的覆盖控制算法。本文分别从静止和移动场景入手,以不同的感知模型为主线展开研究。在静态网络中,本文首先针对有向感知模型,研究了随机部署网络中的覆盖增强问题。本文证明了调度传感器工作方向使覆盖区域最大的问题（MDAC）是NP完全问题,进而提出了一种分布式贪心算法DGreedy求解MDAC问题。DGreedy使得每个传感器都选择与其他传感器重叠最少的方向,即工作在额外覆盖区域最大的方向上。在此基础上,利用局部迭代计算的可能覆盖贡献比反映网络拓扑信息,提出了一个增强的算法PGreedy,让覆盖贡献最大的节点优先选择工作方向。模拟结果表明,PGreedy算法显著增强了有向传感器网络的覆盖区域,减少了覆盖盲区,从而优化了网络的服务质量。除了有向感知模型,本文进一步针对实际使用的传感器的感知能力,提出一种全新的点感知模型,完善感知模型的种类。本文利用具有点感知能力的传感器监控可扩散事件。只有事件扩散到某个传感器节点所处位置时,该事件才能被检测到。基于Voronoi图和Delaunay三角剖分,利用网络所能监控的事件半径对网络的事件监控能力进行了分析和证明。在此基础上分别设计了相应的集中式算法和分布式算法来确定网络的监控能力。最后为了确定事件的发生源头,根据各个节点检测到事件的时间,推导事件发源地离各个节点的距离远近。进而利用二分平面法设计了一个实用可行的事件发源地定位算法。理论证明和模拟实验验证了算法的正确性和有效性。在移动网络中,本文在点感知模型基础上进一步研究了周期性的目标监控问题。首先证明了最少移动节点的扫视覆盖问题（MSSC）是NP难的。然后本文假设所有目标具有相同的扫视周期,提出了近似比为2+ε和集中式算法CSWEEP。进一步扩展到MSSC问题的一般情况,设计了近似比为3的集中式算法GSWEEP。最后为了实用性和可扩展性,设计了分布式算法DSWEEP,每个传感器根据其获知的其它节点移动轨迹,独立实时地决定其移动路径。模拟结果表明,DSWEEP利用较少的节点能够满足大规模目标的扫视覆盖需求,显著降低了资源消耗,并且保证了网络的覆盖能力。为了进一步充分利用移动节点的优势,本文以圆盘感知模型为例研究了移动网络的部署问题。随机部署传感器网络时,为保证栅栏覆盖需要部署大量节点,造成了不必要的浪费。本文利用移动节点的再部署能力减少节点浪费。首先形式化定义了最小能耗节点再部署问题（MEBC）,提出集中式栅栏覆盖算法CBarrier求解MEBC问题。CBarrier集中式地计算所有传感器重部署后的位置,使得所有节点的移动路径之和最短。为了适应大规模网络,本文进一步提出虚拟力模型,在此基础上设计了分布式算法DBarrier,利用虚拟力来重新部署传感器。模拟结果表明,本文所提算法能够显著减少需要的传感器数量,同时提高了网络部署的灵活性和可靠性。综上所述,本文以完善感知模型和增强覆盖能力为目标,研究了新型感知模型的覆盖控制问题和支持移动节点的覆盖控制算法,对于推进无线传感器网络覆盖控制的研究和实用化具有一定的理论意义和应用价值。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 无线传感器网络概述
• 1.1.1 基本概念和特点
• 1.1.2 主要应用
• 1.1.3 研究内容
• 1.1.4 研究现状
• 1.2 无线传感器网络的覆盖控制
• 1.2.1 覆盖控制的研究意义
• 1.2.2 覆盖控制面临的挑战
• 1.2.3 现有工作的不足
• 1.3 本文研究内容
• 1.4 本文组织结构
• 第二章 相关研究
• 2.1 覆盖相关问题
• 2.1.1 计算几何覆盖问题
• 2.1.2 机器人覆盖问题
• 2.2 传感器感知模型
• 2.2.1 圆盘感知模型
• 2.2.2 概率感知模型
• 2.2.3 有向感知模型
• 2.3 覆盖控制问题分类
• 2.3.1 覆盖对象分类
• 2.3.2 部署方式分类
• 2.3.3 节点可移动性分类
• 2.4 覆盖控制研究现状
• 2.4.1 区域覆盖
• 2.4.1.1 覆盖分析
• 2.4.1.2 覆盖优化
• 2.4.1.3 节点调度
• 2.4.1.4 连通覆盖
• 2.4.2 移动目标覆盖
• 2.4.2.1 穿越覆盖
• 2.4.2.2 栅栏覆盖
• 2.4.3 固定目标覆盖
• 2.4.3.1 节点调度
• 2.4.3.2 连通覆盖
• 2.5 小结
• 第三章 有向传感器区域覆盖
• 3.1 引言
• 3.2 最大有向区域覆盖问题（MDAC）
• 3.2.1 定义和符号
• 3.2.2 MDAC问题
• 3.2.3 整数线性规划形式
• 3.3 分布式贪心算法（DGreedy）
• 3.3.1 定义和假设
• 3.3.2 DGreedy算法
• 3.4 分布式概率增强的贪心算法（PGreedy）
• 3.4.1 概率迭代过程
• 3.4.2 PGreedy算法
• 3.5 实验结果分析
• 3.5.1 概率迭代过程的收敛
• 3.5.2 性能比较
• 3.6 小结
• 第四章 基于点感知模型的事件监控
• 4.1 引言
• 4.2 网络模型
• 4.3 Voronoi图和Delaunay三角形
• 4.4 网络监控半径
• 4.4.1 监控半径定理
• 4.4.2 集中式算法
• 4.4.3 分布式算法
• 4.5 事件发源地定位
• 4.6 实验结果分析
• 4.7 小结
• 第五章 移动传感器扫视覆盖
• 5.1 引言
• 5.2 旅行商问题
• 5.3.1 扫视覆盖
• 5.3.2 问题复杂性
• 5.3.3 CSWEEP算法
• 5.3.4 GSWEEP算法
• 5.3.5 扫视覆盖的非局部性
• 5.4 DSWEEP算法
• 5.4.1 假设
• 5.4.2 传染交换
• 5.4.3 下一个POI决策
• 5.4.4 DSWEEP状态转换图
• 5.5 实验结果分析
• 5.5.1 实验参数
• 5.5.2 覆盖效果
• 5.5.3 所需传感器个数
• 5.6 小结
• 第六章 移动传感器栅栏覆盖
• 6.1 引言
• 6.2 最少能耗栅栏覆盖再部署问题（MEBC）
• 6.2.1 栅栏覆盖部署
• 6.2.2 MEBC问题
• 6.2.3 CBarrier算法
• 6.3 分布式栅栏覆盖算法DBarrier
• 6.3.1 虚拟力模型
• 6.3.2 DBarrier算法描述
• 6.4 实验结果分析
• 6.5 小结
• 第七章 结束语
• 7.1 工作总结
• 7.2 研究展望
• 致谢
• 攻读博士学位期间撰写的主要论文
• 攻读博士学位期间参加的主要科研工作
• 参考文献