无线传感器网络中面向数据采集的支配集算法与策略研究

论文摘要

无线传感器网络是由大量具有感知、数据处理和通信能力的传感器节点组成的网络,并且通过传感器节点之间的协作,实现对各种现象的监测。由于具有低功耗、低成本、智能化、分布式、自组织等特点,无线传感器网络在军事、环保、医疗、商业、灾害预测及救援等领域有着广阔的应用前景。无线传感器网络是面向数据的网络,其主要任务就是进行数据处理,包括数据的感知、采集、传输、压缩、聚合等等。传感器网络节点通常密集分布在所监测的网络区域中,并且会产生大量的数据,地理位置邻近的节点产生的数据往往具有很大的相关性,这些都给无线传感器网络的数据采集算法设计带来了很大的挑战。传感器网络节点是能量受限的,在网络中传输大量的数据必然会缩短网络的生命周期。因此,优化网络通信结构和数据冗余缩减都能显著改善网络在时延、能耗、可靠性等方面的性能。在无线传感器网络中构造虚拟主干是优化网络通信结构的一个重要手段。支配集是在无线网络中构建虚拟主干最常用的技术,很多文献提出采用连通支配集作为无线网络的虚拟主干,并设计了一些有效的算法,但这些算法都是以通用的无线网络为研究背景,因而在构造连通支配集时没有考虑无线传感器网络的特殊性,包括数据采集、冗余缩减等。本文主要研究适合在无线传感器网络中进行高效数据采集的支配集结构。树形通信结构很适合在无线传感器网络中进行消息洪泛、数据采集和数据融合,因此本文先对树形的连通支配集进行研究。一般意义上的连通支配集是基于连通网络的,为了将连通支配集的概念应用到稀疏无线传感器网络中,并且在数据采集时考虑数据的相关性,本文还对支配集的概念进行了扩展,提出了虚拟支配集、全虚拟支配集和关联支配集等概念,并根据扩展的支配集概念,设计了一系列在无线传感器网络进行高效数据采集的算法。首先,提出了一个能量高效的支配树构造算法(EEDTC)来构建一个能在传感器网络中充当虚拟主干的树形的连通支配集。EEDTC算法利用节点的κ跳邻居节点信息,具有很好的可扩展性,选取合适的κ值能实现不同的消息复杂度和时间复杂度要求,同时EEDTC算法具有很好的节能特性和能量均衡特性。在不同的网络数据采集应用背景下,该算法都表现出很好的性能；其次,为了实现从部分连通的网络中采集数据,结合虚拟支配集的概念,提出了一个基于网格分割的移动单元调度算法(GBMES),调度一个移动单元(ME)周期性地从网络中采集数据。GBMES算法在降低移动单元的行进时延和数据采集时延等方面具有很好的性能,显著降低了由于传感器网络节点的缓存溢出而产生的数据丢失。然后,为保证移动采集节点MC在稀疏传感器网络中进行高效数据采集,基于Voronoi图提出了两个算法：基于普通Voronoi图的移动采集节点调度算法(VDMCS)和基于加权Voronoi图的能量均衡数据采集算法(MWVDC)。两个算法都是通过迭代的虚拟散点插入过程生成一个全虚拟支配集,在给定的通信半径范围内,这个集合恰好能覆盖所有的传感器节点。在全虚拟支配集的基础上,VDMCS为MC构建一条最短的行进路径,MWVDC算法则对数据采集时延和网络能耗进行综合考虑,为MC构造一条优化的数据采集路径,同时保证整个网络能量消耗的均衡性。最后,结合关联支配集的概念,设计了一个基于熵评判的关联支配集构造算法(EECDS),该算法首先通过评价随机变量的熵值来判断网络节点间的数据相关性,然后在网络中分布式地构造一个关联图,最后借助关联图的信息构造一个连通关联支配集。EECDS算法能有效地缩减无线传感器网络的数据冗余,同时具有很好的能量均衡特性和可扩展性。

论文目录

• 摘要
• ABSTRACT
• 目录
• 第一章 绪论
• 1.1 无线传感器网络
• 1.1.1 特征与应用
• 1.1.1.1 特征
• 1.1.1.2 应用
• 1.1.2 研究现状
• 1.1.2.1 研究领域分类
• 1.1.2.2 关键技术
• 1.2 问题的提出
• 1.2.1 背景
• 1.2.2 研究内容与创新点
• 1.2.2.1 主要研究内容
• 1.2.2.2 创新点
• 1.3 本文的组织结构
• 1.4 课题来源
• 第二章 相关理论基础
• 2.1 图论
• 2.1.1 图与单位圆图
• 2.1.2 支配集
• 2.1.3 独立集
• 2.2 计算几何
• 2.2.1 Voronoi图
• 2.2.2 Delaunay三角剖分
• 2.2.3 加权Voronoi图
• 2.3 信息论
• 2.3.1 信息熵
• 2.3.2 微分熵
• 2.4 本章小结
• 第三章 无线传感器网络中的连通支配集构造算法
• 3.1 相关研究
• 3.2 网络模型
• 3.3 算法思路
• 3.4 算法描述
• 3.4.1 邻居发现阶段
• 3.4.2 标记阶段
• 3.4.3 连通阶段
• 3.5 算法特性分析
• 3.5.1 算法复杂度
• 3.5.1.1 特殊情况下的算法复杂度分析
• 3.5.1.2 一般情况下的算法复杂度分析
• 3.5.2 算法近似比
• 3.5.3 算法的能量消耗特性
• 3.6 性能评价
• 3.6.1 网络的能量消耗和生命周期
• 3.6.1.1 构造连通支配集的能量消耗
• 3.6.1.2 在两种通信模式下构造连通支配集的能量消耗
• 3.6.2 连通支配集的大小
• 3.6.3 算法近似比
• 3.6.4 算法消息复杂度
• 3.7 本章小结
• 第四章 部分连通无线传感器网络中的虚拟支配集策略
• 4.1 相关研究
• 4.2 网络模型
• 4.3 虚拟支配集
• 4.4 问题定义
• 4.5 算法实现
• 4.5.1 网格分割
• 4.5.2 行进路径设计
• 4.5.2.1 区域间路径设计
• 4.5.2.2 区域内路径设计
• 4.5.3 数据采集方法设计
• 4.5.3.1 构建本地虚拟支配树
• 4.5.3.2 网格内数据融合
• 4.5.3.3 查询转发和数据采集
• 4.6 性能评价
• 4.6.1 仿真模型
• 4.6.2 ME运动速率的影响
• 4.6.3 网格大小的影响
• 4.6.4 数据传输速率的影响
• 4.6.5 网络节点缓存大小的影响
• 4.6.6 网络节点采样速率的影响
• 4.7 本章小结
• 第五章 稀疏无线传感器网络中的全虚拟支配集策略
• 5.1 相关研究
• 5.2 网络模型
• 5.3 全虚拟支配集
• 5.4 VDMCS算法
• 5.4.1 问题定义
• 5.4.2 算法实现
• 5.4.2.1 全虚拟支配集的构建
• 5.4.2.2 移动采集节点调度
• 5.4.3 性能评价
• 5.4.3.1 全虚拟支配集构造算法的性能
• 5.4.3.2 sVDMCS算法和PlainMCS算法的比较分析
• 5.5 MWVDC算法
• 5.5.1 问题定义
• 5.5.2 算法实现
• 5.5.2.1 加权Voronoi映射节点集的构建
• 5.5.2.2 数据采集路径
• 5.5.3 性能评价
• 5.5.3.1 节点数量对全虚拟支配集大小的影响
• 5.5.3.2 节点数量对数据采集路径长度的影响
• 5.5.3.3 传感器节点平均能量消耗
• 5.5.3.4 数据采集时延
• 5.5.3.5 能量消耗的均衡性
• 5.5.3.6 覆盖系数λ的影响
• 5.6 本章小结
• 第六章 密集无线传感器网络中的关联支配集构造算法
• 6.1 相关研究
• 6.2 关联支配集
• 6.3 网络模型
• 6.4 问题定义
• 6.5 算法描述
• 6.5.1 k跳邻居发现
• 6.5.2 生成关联图
• 6.5.3 构造连通关联支配集
• 6.6 性能评价
• 6.6.1 协方差矩阵参数分析
• 6.6.2 连通关联支配集的大小
• 6.6.3 各项参数对关联支配集大小的影响
• 6.6.3.1 误差系数μ的影响
• 6.6.3.2 微分熵步长值△的影响
• 6.6.4 算法的能耗特性
• 6.6.4.1 平均能量消耗
• 6.6.4.2 能量均衡特性
• 6.7 本章小结
• 第七章 总结和展望
• 7.1 全文总结
• 7.2 工作展望
• 参考文献
• 致谢
• 攻读博士学位期间撰写的论文和参加科研情况
• 作者简介