【作者】 潘晏涛；

【导师】 卢锡城；

【作者基本信息】 国防科学技术大学 ， 计算机科学与技术， 2006， 博士

【摘要】 无线传感器网络是当今网络技术的一个研究热点。传感器节点集成了微传感器、微控制器和无线通信模块,具有体积小、功耗低、价格低廉和无线通信等优势。传感器节点可以随机部署、自组成网,完成对环境数据的自动化采集、处理和传输。无线传感器网络连接了信息世界和现实世界,提高了人们对物理世界的认识能力,有广阔的发展前景。能源受限是无线传感器网络的一个突出特点。针对无线传感器网络的研究必须充分考虑节能性。节能的目标是延长网络的生存时间。由于通信能耗占传感器节点总能耗的绝大部分,设计节能的通信协议是延长无线传感器网络生存时间的一个重要途径。生存时间优化和休眠调度分别从不同角度对通信能耗进行了优化。其中,生存时间优化解决的是网络中有数据传输时如何均衡各节点能耗的问题,而休眠调度解决的是如何安排没有数据采集和传输任务的节点休眠以降低空闲能耗的问题。两者可以联合使用以提高网络的生存时间。无线传感器网络中的主要流量是传感器节点到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】 Wireless sensor network is considered a promising infrastructure to change the physical environment, and hence our life in this environment. It has been an active research area in the past few years. Wireless sensor networks are presumed to be deployed using battery-powered stationary sensor nodes equipped with sensing, computing and wireless communicating modules. In a broad range of potential applications, inexpensive sensors can be embedded into buildings or scattered into spaces to collect, process and send out relevant information for various civilian or military purposes.Since sensors have significant power constraints, and the radio transceiver typically consumes more energy than any other hardware component onboard a sensor node, design of energy efficient communication algorithms is of great importance. For prolonging system lifetime by reducing the energy consumed by communications, various algorithms have been proposed. They can be categorized into two families: lifetime maximization and sleeping scheduling. Lifetime maximization problem focuses on how to balance the energy consumption of data transmission so that the system lifetime that the first“die-out”node lives could be prolonged as much as possible. However, sleeping scheduling focuses on how to force as many as possible nodes to go to sleep so that the energy consumed by idle listening could be conserved. A promising perspective on combining lifetime maximization and sleeping scheduling should be taken to prolong system lifetime.The data flow in a sensor network is very different from data flow in an ordinary network, and therefore the common protocols used in the Internet or Manet paradigm are inadequate to handle. Such special data flow poses novel challenges and also chances in designing efficient routing algorithms in sensor networks. That is to perform global optimization in traffic planning to prolong system lifetime as much as possible.We abstract a kind of multi-source-to-multi-sink communication lifetime maximization problem of non-power-controllable sensor networks into a kind of one-source-to-one-sink single-commodity flow maximization problem on a directed graph with arc and vertex capacities. Based on this model, three polynomial-time algorithms VABA, FAT and ADALM are presented to estimate whether a sensor network can live a given lifetime or not. Through binary search, these algorithms can find out the maximum lifetime and the best traffic planning under a given precision.Precious sensor node battery power can be saved by power control measures that can dynamically adjust the radio transmission range of a sensor node. Therefore we extend VABA to I-VABA in order to handle the lifetime maximization problem of power-controllable sensor networks. In particular, a heuristic algorithm AOC is presented to perform circle flow adjustment when I-VABA is blocked so that additional flow augmentations could be achieved. Compared with other heuristic algorithms, AOC achieves a higher or a similar approximation ratio but uses a much fewer run time.In sensor networks, the communication cost is often several orders of magnitude higher than the computation cost. So in-network data aggregation is considered an effective technique for energy conservation. In addition, QoS constraints are also important for providing congestion-free and latency-bounded data transmission service. We formulize such kind of lifetime maximization problem with considering data aggregation and QoS constraints as non-linear programming and propose a genetic algorithm GAMSN to solve it. GAMSN takes unit-flow-rate paths as genes and constructs a chromosome for each source node by a set of unit paths that originated from it. In particular, a parameter named“PREC”is set to serve the purpose of control the number of genes of a chromosome and hence the precision in which GAMSN could approximate the maximum lifetime. This approach has a reasonable time complexity and performs well in experiments.However, a major drawback of GAMSN is the additional individual diversity overhead resulted from increased PREC. With the increase of individual diversity, much greater population size is needed to ensure that there are some good individuals in a randomly generated initial population. Therefore, the increase of individual diversity will adversely impact the algorithm effectiveness. We propose a diversity-controllable genetic algorithm DCGA as an improvement of GAMSN to address this problem. DCGA uses two methods to control the individual diversity. The first is to control the number of genes in a chromosome through parameter PREC. The second is to control the type of genes by limiting the hop counts of randomly generated unit paths. DCGA gains remarkable performance improvement under high PREC by diversity control.Compared with a kind of algorithms which use multi-commodity approximate methods to solve programming problems, DCGA can also achieve a high approximation ratio but has lower time complexity. Compared with a kind of heuristic algorithms, DCGA achieves a higher approximation ratio with a little increased order of computations. To the best of our knowledge, GAMSN and it diversity-controllable improvement DCGA are the first algorithms that can solve multi-commodity lifetime maximization problems of power-controllable sensor networks with data aggregation and QoS constraints.Synchronized periodic duty cycling of the sensor nodes is suggested to minimize the energy consumption of idle listening. Each node follows a periodic cycle of active/sleep radio states. During the sleep period, the radio is completely turned off, and during the active period, the radio is turned on and all generated data is send to the sink. So the important problem is to reduce the length of active period as much as possible. In sensor networks with data aggregation, an intermediate node must to wait for all incoming data to arrive before it can perform data aggregation and send the aggregated data to the downstream nodes. If an upstream node decides to send it outgoing data to another node firstly, the current node has to wait for it and put off its data aggregation and out sending. Consequently, all nodes that wait for incoming data from the current node have to put off their process as the same. Such kind of wait results in significant delay and prolong the time that is needed to send all data generated in a periodic of active/sleep cycle to the sink. Therefore it is very important to schedule the transmission order on each node to reduce the wait time and consequently the length of active period. We call this traffic scheduling and propose a heuristic algorithm named PYTMS based on the adjustments on critical paths. It can reduce the active period remarkably.更多还原