无线传感器网络生存时间优化问题研究

论文摘要

无线传感器网络是当今网络技术的一个研究热点。传感器节点集成了微传感器、微控制器和无线通信模块,具有体积小、功耗低、价格低廉和无线通信等优势。传感器节点可以随机部署、自组成网,完成对环境数据的自动化采集、处理和传输。无线传感器网络连接了信息世界和现实世界,提高了人们对物理世界的认识能力,有广阔的发展前景。能源受限是无线传感器网络的一个突出特点。针对无线传感器网络的研究必须充分考虑节能性。节能的目标是延长网络的生存时间。由于通信能耗占传感器节点总能耗的绝大部分,设计节能的通信协议是延长无线传感器网络生存时间的一个重要途径。生存时间优化和休眠调度分别从不同角度对通信能耗进行了优化。其中,生存时间优化解决的是网络中有数据传输时如何均衡各节点能耗的问题,而休眠调度解决的是如何安排没有数据采集和传输任务的节点休眠以降低空闲能耗的问题。两者可以联合使用以提高网络的生存时间。无线传感器网络中的主要流量是传感器节点到sink节点的数据汇集流。而且中间节点可能在传输过程中进行数据聚合,这和传统网络有很大不同。流量的汇集性特点为通信协议的设计提出了新的要求,同时也为生存时间的全局优化提供了机会。生存时间优化就是在给定节点的初始能量、数据产生速度和链路传输代价等约束的情况下,寻求流量或流速在网络上的最佳分配方案以使网络生存时间最大化。根据是否考虑数据聚合、节点是否具有发射功率控制能力、是否考虑接收功耗、是否考虑多种物流、路由结构是否动态可变,以及所针对的通信类型和所采用的生存时间定义,生存时间优化有多种不同的问题模型和不同的求解难度。本文首先针对发射功率不可控的单物流传感器网络上的单播生存时间优化问题从网络流的角度进行建模。把多到一或多到多的单物流无线传感器网络中,数据汇集流所引发的生存时间优化问题转化为点弧权网络上单源单汇的最大流问题。在对这一问题进行分析的基础上,给出两个复杂度不同的集中式算法VABA和FAT,以及一个分布式算法ADALM。它们都属于判定性算法,能够在多项式时间内判断一个传感器网络的最大生存时间能否达到给定的数值。使用判定性算法结合生存时间上限通过折半查找能够以所需精度逼近最大生存时间和最佳传输方案。在此基础上把网络流模型扩展到发射功率可控的无线传感器网络上。将VABA扩展为I-VABA算法,并提出以圈流调整将不可增广的阻塞流转化为同等流量下的理想流以便进一步增广。据此提出基于圈流调整的启发式网络流算法AOC。比较其它启发式算法,AOC的近似度更高或基本持平,但运算时间却大大降低,对网络规模的扩展性更强。接着考虑更为复杂的情况——研究带有功率控制、数据聚合和QoS要求的多约束条件下的生存时间优化问题。首先使用非线性规划对问题进行描述,然后给出一个遗传算法GAMSN。GAMSN算法以携带单位流速的源目的路径作为基因,以一组源自相同节点的基因组成染色体,并进而构成个体。染色体所含的基因数由对应源节点的数据产生速度决定,个体所含的染色体数由源节点数决定。染色体的长度决定了一个源节点所能用来进行流速均衡的单位路径数量,从而限制了算法所能达到的精度。因此设置参数PREC与源节点数据产生速度共同控制染色体的长度和算法求解的精度。GAMSN通过流速编码避免了个体突破能量约束的情况,可以实现精度可控的求解,并在实验中表现出了良好的性能。然而基本的GAMSN算法在实际应用中存在个体多样性随精度提高而快速增大,导致随机产生的初始群体平均适应度下降,进而影响群体进化速度的问题。针对这一问题提出改进算法DCGA,即多样性可控的遗传算法。DCGA通过控制染色体所含的基因数量和基因种类实现多样性可控的递进求解。对比GAMSN,改进算法DCGA所能达到的求解精度明显提高。和一类直接对规划问题进行近似求解的算法相比,DCGA算法的优势在于同样可以达到较高的近似度,但复杂度更低。和普通启发式算法相比,DCGA算法以较小的复杂度增幅换取了较大的近似度改进。更重要的是现有算法尚不能处理功率可控、延迟和吞吐率受限的多传感器网络上无穷或比例聚合条件下的数据汇集流生存时间优化问题,而DCGA算法则能较好地解决该问题。在上述对生存时间优化问题研究的基础上,提出当无线传感器网络中的数据传输总量较小的时候,应该使用同步休眠调度作为生存时间优化的补充,以进一步提高网络的生存时间。特别地,针对带有数据聚合的无线传感器网络,生存时间优化只解决了流量或流速在链路上的分配问题,而没有解决流量的调度问题。而不佳的流量调度会影响系统的可休眠时间。我们对流量调度问题进行了建模,提出了一个基于关键路径的启发式算法PYTMS。实验表明PYTMS算法显著缩短了系统所需的活跃周期长度,从而降低了相应的空闲能耗,有利于延长网络的生存时间。

论文目录

• 目录
• 摘要
• Abstract
• 第一章 绪论
• 1.1 研究背景
• 1.1.1 无线传感器网络的基本概念
• 1.1.2 无线传感器网络的基本特点
• 1.1.3 无线传感器网络的主要应用
• 1.2 研究内容和研究现状
• 1.2.1 研究内容
• 1.2.2 研究现状
• 1.3 论文的主要贡献
• 1.4 论文的组织结构
• 第二章 生存时间优化问题的研究现状和相关工作
• 2.1 研究现状
• 2.1.1 生存时间优化问题的内涵
• 2.1.2 生存时间的度量方法
• 2.1.3 生存时间优化问题的分类
• 2.1.4 生存时间优化问题的复杂性
• 2.1.5 生存时间优化涉及的其它问题
• 2.1.6 生存时间优化问题和相关研究的联系和区别
• 2.2 相关工作
• 第三章 基本生存时间优化问题的建模
• 3.1 求解最大生存时间的上限
• 3.1.1 观察和抽象
• 3.1.2 生存时间上限
• 3.1.3 进一步分析
• 3.2 基本生存时间优化问题的网络流模型
• 3.2.1 模型概述
• 3.2.2 模型的求解
• 第四章 基本生存时间优化问题的求解
• 4.1 点弧联合双向调整算法VABA
• 4.1.1 VABA 算法要点
• 4.1.2 VABA 算法描述
• 4.1.3 VABA 算法小结
• 4.2 快速流量规划算法FAT
• 4.2.1 FAT 算法要点
• 4.2.2 FAT 算法描述
• 4.2.3 FAT 算法小结
• 4.3 分布式异步生存时间最大化算法ADALM
• 4.3.1 ADALM 算法要点
• 4.3.2 ADALM 算法的集中式框架
• 4.3.3 ADALM 算法的分布式实现
• 4.3.4 ADALM 算法的复杂度分析
• 4.4 小结
• 第五章 发射功率可控的无线传感器网络上生存时间优化问题的网络流模型和求解
• 5.1 网络流模型的扩展
• 5.2 扩展模型的求解
• 5.3 启发式算法AOC
• 第六章 带QoS 约束、功率控制和数据聚合的多传感器网络上生存时间优化问题的求解
• 6.1 引言
• 6.2 问题的形式化
• 6.3 遗传算法GAMSN
• 6.3.1 编码方案的选择
• 6.3.2 遗传操作的设计
• 6.3.3 算法参数的确定
• 6.3.4 算法性能的初步分析
• 6.4 扩展GAMSN 解决带有QoS 约束和数据聚合的生存时间优化问题
• 6.4.1 算法的扩展
• 6.4.2 扩展算法上的实验
• 6.4.3 算法的复杂度分析
• 第七章 多样性可控的遗传算法DCGA
• 7.1 基本算法GAMSN 存在的问题
• 7.1.1 理论分析
• 7.1.2 实验检验
• 7.2 多样性可控的遗传算法DCGA
• 7.2.1 DCGA 算法思想
• 7.2.2 DCGA 算法要点
• 7.2.3 较GAMSN 算法的性能改进
• 7.3 DCGA 算法的性能评价
• 7.4 小结
• 第八章 无线传感器网络上的流量调度优化
• 8.1 流量调度问题的提出
• 8.2 流量调度优化问题的形式化
• 8.3 流量调度优化的一个启发式算法PYTMS
• 第九章 结束语
• 9.1 论文工作的总结
• 9.2 下一步的工作
• 致谢
• 参考文献
• 作者在学期间发表的学术论文