节点轮换的传感器网络生存期优化算法

李兰英，蒋维成，周 玲，胡晓玲

(成都理工大学工程技术学院 电子信息与计算机工程系，四川 乐山 614000)

0 引 言

无线传感器常部署在野外无人值守的环境[1,2]。由于监测过程的特殊性，无线传感器常是一经部署就不再改变。受设备的限制，无线传感器自身携带的能量有限，而数据采集和通信都需要能量，这样能量就成为无线传感器网络中的珍贵资源。为了增加网络中的能量资源，无线传感器的数量和密度都要达到一定要求，以保持能量的冗余，更好发挥其功能，提高系统的可靠性，使监测顺利进行下去，减少意外因素导致的失败。有时单个无线传感器的能量无法完成对目标监测的时长，需要众多节点来实现对目标的分段监测，通过时间接力才能达到规定的时长。如区域中某密度下能量仅维持5天的监测网络，无线传感器的密度增加就可以增加监测的时间，在密度增加两倍后，监测时间可能延长到10天，大大增加了对目标的监测时长，提高了性能。这对于环境险恶、部署难度大的无线传感器网络，可以减少部署次数，节约成本。但是随着网络中无线传感器数量的增加，也增加了网络管理的难度和复杂性，如何在复杂的监测环境中安排好监测节点之间的轮换，保证任务顺利执行下去，使得对目标的监测达到规定的要求，并高效地利用能量，使得监测网络的有效期得以延长。这对无线传感器网络来说具有重要意义。

1 相关研究

无线传感器网络中常采用分簇方式对网络中的节点进行管理。文献[3]依据距离汇聚节点的远近以及节点数量进行网络分层，根据分层网络中簇头节点的位置和节点的剩余能量选择每个分层的中心节点，采用分层聚类与节点管理机制降低无线传感器网络的能耗。文献[4]根据节点剩余能量和位置信息选择簇头，均衡能量消耗，延长网络生存期。文献[5]根据传感器节点的剩余能量和位置信息等参数优化簇头选取，簇头与中继节点之间利用单跳和多跳相结合的传输形式，减少节点间的通信开销，延长网络寿命。文献[6]提出一种多跳无线传感器网络分簇算法，提高节点能量利用的效率，优化网络数据传输。群智算法被用于无线传感器网络的路由优化中[7,8]，文献[9]采用最优路径度量公式改进信息更新策略，提出了一种改进蚁群算法的无线传感器网络路由方法，来均衡节点能耗，延长网络的生命周期。文献[10]采用均匀聚类成簇的方法，各簇进行压缩的分布式数据收集，通过建立骨干树将数据传输至Sink节点，降低网络传输量，节约能耗。

这些算法针对无线传感器网络中能量的利用进行优化，使得能量的利用率提高了，但无法保证对目标的监测时间长度达到具体的要求，实现对目标的长时间监测。为此，本文提出了基于节点轮换的能量感知监测方法(energy-aware monitoring method，EAMM)，使得区域中担任监测任务的无线传感器节点能够自动进行轮换，对目标进行分段监测，实现总监测时间的极大增加，根据过去一段时间的能量消耗来对即将的能量使用进行调整，合理地规划无线传感器的能量利用，使得对目标的监测时长达到要求，尽可能地延长网络生存有效期，以求监测时长最大化。

2 网络模型和问题描述

2.1 网络模型

网络中无线传感器的个数为m，用集合N表示。假设这m个无线传感器节点 (b1,b2…bm) 均匀地随机部署在二维平面内，对于任一无线传感器i∈N(i=b1,b2…bm)，部署后位置确定，可由GPS或北斗导航系统获得其位置信息。若无线传感器i的位置表示为 (xi,yi)，监测目标的位置为 (x0,y0)，无线传感器网络具有以下性质：

(1)网络中无线传感器节点分布模型为均匀分布；

(2)各节点是同构的，具有相同的功能和初始能量，初始能量均为e0；

(3)各节点能独立工作，且都能完成相关的工作，并能根据需要实现不同状态的转换；

(4)任意节点的通信范围覆盖其所在的监测区域，并能与区域内的节点和相邻区域中的节点进行通信，这样监测数据可以一跳或多跳传送到Sink节点，且相邻节点间的通信范围均在有效通信半径之内，根据文献[11,12]的能耗模型，通信能耗较小，可以节省能量；

(5)网络内无线传感器节点部署密度达到预定要求，并存在一定冗余，以满足意外情况下目标监测能耗增多所需的要求。

2.2 问题描述

无线传感器网络根据监测质量的要求，在目标附近一定范围内选取无线传感器节点进行监测，受地理位置的影响，区域内的无线传感器对目标的监测可能存在差异，但均符合质量要求。无线传感器i所在的位置与监测质量(Q)之间存在一定的关系，用Qi=f(xi,yi) 表示。若用Tij表示无线传感器i在第j轮中对目标监测的时间长度，网络中无线传感器对目标监测的总时长由各轮次的监测时间段组成，总共有u轮次。Ei表示无线传感器i的剩余能量。设监测质量的最低要求为q0，对目标的监测时间要求达到规划值t0。监测网可以描述如下

式(1)和式(2)分别满足监测质量和时长的要求，式(3)中的tmax为理想化条件下能量所能维持的最长监测时间，追求对目标的监测时长最大化，使得监测时长尽可能趋近于tmax，网络的效益就越高。

式(4)中Si表示无线传感器i能否被选作监测节点，如果能选作监测节点，则Si=1，否则Si=0。要实现对目标监测的时间最长，区域中能够担任对目标监测的节点，它们的能量均消耗完，这样能量均在网络生存有效期内利用，能量的利用效率最高。

3 算法框架

3.1 算法设计

要对区域内的目标进行分段监测，使得满足监测质量要求的节点之间进行轮换，本文根据无线传感器的剩余能量(E)和监测质量(Q)，定义质能关系式如下

(6)

式中：β1和β2为比例系数，β1表示质能关系中监测质量所占的比例因子，β2表示质能关系中剩余能量所占的比例因子。质能关系式是选择监测节点和进行轮换的重要关系式。在轮换过程中优先选择质能关系中R值较大的节点进行监测。

从质能关系式可以得知，对于相同监测质量的两无线传感器i和j，存在Qi=Qj，而当剩余能量不同时，满足Ei

而对于相同的剩余能量条件下的两无线传感器i和j，存在Ei=Ej，而当监测质量不同时，满足Qi

由以上分析可得，根据目标所在的位置，对其周围满足监测条件的无线传感器节点集，结合各节点的剩余能量状况，自适应地进行选择，使得对目标监测所需的能量分散在众多的节点之间，通过这些无线传感器节点对目标进行时间上的分段监测，通过时间接力实现对目标监测总时长的增加。如图1所示，O点为目标所在位置，对于距离均为R1的A、B两点，首先选择能量较多的B进行监测，在B的能量消耗一定程度之后，再选择A点，而A监测一定时间后，可以选择半径为R2的C点进行监测，这样对目标的监测就可以由多个节点轮流执行，使得目标监测的能量消耗均衡化，监测时长也变成单个节点的多倍，监测时长得到大幅增加。

图1 分段监测节点

文献[13]指出无线传感器在不同的工作状态下，能耗是不相同的，无线传感器的能耗跟工作状态相关。无线传感器处于某种工作状态，就可以知道一段时间内的能量消耗。

定义1 历史能耗速率是无线传感器在某工作状态下能耗速率，与无线传感器的工作状态相关，它是根据这一工作状态下的长时间里能耗所得的结果，用H表示。

为了对能量的利用进行规划，使得监测时长达到规定的要求，本文根据感知能耗速率来调整无线传感器的能量使用。

定义2 感知能耗速率由无线传感器的历史能耗速率和实时变化速率两部分组成，采用式(7)表示

Va=δ1·H+δ2·F

(7)

式中：F为实时变化速率，δ1和δ2为比例系数，δ1表示感知能耗速率中历史能耗速率所占的比例因子，δ2表示感知能耗速率中实时变化速率所占的比例因子。

F=Vn-1-Vn-2

(8)

当Vn-1>Vn-2时，则(Tn-1,Tn)时段的能耗速率要比(Tn-2,Tn-1)时段的能耗速率要大，能量消耗是增加的趋势，感知下一个时段(Tn,Tn+1)的能耗会增大。因而实时能耗速率进行调整，在历史能耗速率的基础上增加一定的量，使得感知能耗速率的值增大。此时，由式(8)可以得知，有Vn-1-Vn-2>0，因而式(7)是在能耗速率的基础上增加一定量，是对能耗速率的加大。

当Vn-1=Vn-2时，则(Tn-1,Tn)时段的能耗速率与(Tn-2,Tn-1)时段的能耗速率是相同的，能耗消耗保持在一个稳定的水平状态，感知在下一个时段(Tn,Tn+1)也将保持当前稳定的能耗状态。此时，由式(8)可以得知，有Vn-1-Vn-2=0，因而式(7)是维持能耗速率的水平。

当Vn-1

通过以上分析，能耗速率在过去的时间里不论是增大、不变或减少，式(7)都能够很好地表达在(Tn,Tn+1)时段的能耗状态。

根据感知能耗速率的大小，对网络中能量的使用进行调整，并做好监测的轮换安排，使得对目标的监测时长达到预定的要求。设网络规划时对目标的监测能耗速率用Vp表示。

当Va

定义一个变量为盈余时间Ts，用于记录监测过程中的盈余时间，当有盈余能量时，把盈余时间进行累加。监控无线传感器的能量消耗，当能量消耗ΔE时，立即进行轮换，并记录这轮的延长时间t′s，并更新盈余时间Ts=Ts+t′s。

当Va>Vp时，感知能耗速率比规划能耗速率要大，由于感知能耗速率Va的增大，由式(7)可以得知，在(Tn,Tn+1)时段消耗的能量将比规划的能量要大，无线传感器存在能量的欠缺，欠缺能量为Ed=(Va-Vp)·(tn+1-tn)，在这种情况下对目标的监测轮换将提前进行，避免能量的过度消耗，节点提前死亡。提前轮换时间为t′d=(Va-Vp)·(tn+1-tn)/Va。

定义一个变量为欠缺时间Td，用于记录监测过程中的欠缺时间，当有欠缺能量时，把欠缺时间进行累加。监控无线传感器的能量消耗，当能量消耗ΔE时，立即进行轮换，并记录这轮的欠缺时间t′d，并更新欠缺时间Td=Td+t′d。

当Va=Vp时，感知能耗速率与规划能耗速率相匹配，能量恰好被利用完。此时，不存在盈余时间，也没有欠缺时间。

对网络中的盈余时间和欠缺时间进行比较，当Ts≥Td时，盈余时间不小于欠缺时间，对目标的监测时间将大于或等于规划时长，能够完成预期目的，无线传感器网络能够完成规划要求。

当Ts

3.2 性能分析

本文的EAMM算法构建质能关系式，对目标进行轮换监测。本文对算法的性能进行了仿真实验。在60×60 m2的区域中均匀随机地投放50个无线传感器，目标周围一定范围内的无线传感器可以对目标进行有效的监测。目标所在位置为图中“*”标记处，如图2所示。

图2 投放50个节点

在图2所示的结果中共有4个节点对目标进行分段监测，在图中使用方框标记出来，这些节点轮换执行监测任务，4个节点分段监测的时长将最大增加到单个节点监测时长的4倍。

图3是同样的区域中投放70个无线传感器结果，区域中无线传感器的密度增大，对目标进行有效监测的无线传感器数量也将增加，在图3中共有6个节点对目标进行分段监测，这样就可能最大增加到单个节点时长6倍。表明EAMM算法使得监测时长极大地增加了，并且根据目标的位置选择区域内的合适的节点进行监测，并能够自适应地安排这些节点进行轮换，实现对目标的长时间监测。

图3 投放70个节点

4 仿真结果

为了检验EAMM算法的性能，采用Matlab仿真软件对Leach算法和本文的EAMM算法进行了比较实验。为了模拟网络环境的多样性，测试不同环境下的网络性能，做了不同参数的实验。

(1)目标监测时长比较

相同的能量条件下，对目标的监测时间越长，算法的性能越高，能量的利用效率也就越有效。在100×100 m2的区域中分别投放100个、180个、240个无线传感器，两算法在这3种环境下的结果如图4所示。图中横坐标表示的是区域中投放无线传感器的数量。纵轴表示的是轮次，是网络中对目标的监测时间长度。

图4 监测时长

从图4可以看出，EAMM算法在这3种情况下对目标的监测时长都要比Leach算法要长，并且在区域中无线传感器密度增加时，EAMM算法的优势更加明显。这主要是因为Leach算法只是采取简单的分簇机制对簇内节点进行管理，可能出现较多节点对目标的重复监测，浪费了能量，从而缩短对目标的监测时间，这在无线传感器的密度增大时更加严重。而EAMM算法中对目标监测进行了有效管理，安排好了这些节点监测时段之间的轮换，并对能量的使用进行调整，使得监测时长得到增加，因而EAMM算法中对目标的监测时长优势比较明显。

(2)节点死亡数比较

无线传感器在监测和通信的过程中不断地消耗能量，随着能量的减少，无线传感器将因能量的耗尽而死亡。网络中的无线传感器死亡时间出现得越早，数量越多，越不利于对目标的监测和数据收集。两算法的节点死亡数结果如图5所示。

图5 死亡数

从图5可以看出EAMM算法节点出现死亡的时间比Leach算法要迟，并且在相同的时间里死亡的无线传感器数量要少得多。EAMM算法根据质能关系式在监测节点之间进行轮换，把监测的能量分散在众多的节点之间，有利于能量的均衡化，避免节点能耗过多，提前死亡，因而EAMM算法节点死亡的出现时间要迟，死亡数量也要少。

(3)网络生存期比较

无线传感器节点的存活数量越多，时间越长，网络生存期也就越长，能够采集数据并传送到基站的时间也就越长。两算法中无线传感器节点存活数如图6所示。

图6 存活数

从图6可以看出，在相同的时间里，EAMM算法中无线传感器节点存活数量均比Leach算法要多，因而EAMM算法的网络生存期比Leach算法要长。这主要是EAMM算法中存在对能量消耗的规划利用，当对目标的监测能耗速率过快时，启用冗余节点的能量帮助完成监测，从而避免了节点的能耗过大，节点可以存活的时间就更长。因此，EAMM算法中节点的存活数要多，网络生存期也就越长。

5 结束语

能量是无线传感器网络中的珍贵资源，特别是那些能够对目标进行有效监测的节点能量。为了实现对目标监测时长的最大化，根据无线传感器工作状态下的能量消耗的历史水平状况和实时能耗，构建监测过程能量感知的消耗模式，对网络中的能量进行调整。构建任务监测过程进行节点轮换的质能关系式，对目标的监测自适应地进行轮换，通过多节点的时间接力来完成对目标的长时间监测，使得监测时长尽可能地延长。仿真结果表明，本文构建的监测过程能耗感知的模型，无线传感器在监测过程中能够对能量的使用进行调整和节点之间的轮换，达到或超过规划的时长。