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