可充电无线传感网络能量均衡路由算法

谢小军，于 浩，陶 磊，张信明

(1.国家电网安徽省电力公司 信息通信分公司， 合肥 230061； 2.中国科学技术大学 计算机科学与技术学院，合肥 230027)

可充电无线传感网络能量均衡路由算法

谢小军1，于 浩1，陶 磊2，张信明2*

(1.国家电网安徽省电力公司 信息通信分公司， 合肥 230061； 2.中国科学技术大学 计算机科学与技术学院，合肥 230027)

(*通信作者电子邮箱xinming@ustc.edu.cn)

针对可充电无线传感网络中的能量均衡路由问题，提出在稳定功率无线充电和监测数据收集网络场景下的多路径路由算法和机会路由算法，以实现网络的能量均衡。首先，通过电磁传播理论构建了无线传感节点的充电和接收功率关系模型；然后,考虑网络中无线传感节点的发送能耗和接收能耗, 基于上述充电模型将网络能量均衡的路由问题转化为网络节点运行时间的最大最小化问题，通过线性规划得到的各链路流量用以指导路由中数据流量分配；最后，考虑一种更加现实的低功耗的场景，并提出了一种基于机会路由的能量均衡路由算法。实验结果表明，与最短路径路由(SPR)和期望周期最短路由(EDC)算法相比较，所提出的两种路由算法均能有效提高采集能量的利用率和工作周期内的网络生命周期。

能量均衡路由；可充电无线传感网络；机会路由；低功耗传感网络

0 引言

无线传感器网络(Wireless Sensor Network, WSN)是由大规模的微型、智能传感器节点组成无线自组织网络系统，网络中的节点通过相互协作将监测到的数据信息传送至网关(sink)节点进行处理。无线传感网中的节点能量有限，为了提升节点的运行时间和网络寿命，为无线传感节点配备能量捕获模块和可充电电池，称为可充电无线传感节点。当可充电无线传感节点能够捕获的能量有限时，节点在能量耗尽前进行网络中的数据采样、接收和传输等正常操作，在能量耗尽后进入低功耗模式睡眠状态，此时，能量均衡路由关系到网络中节点的可运行时间，即网络生命周期，仍然是该网络中需要关注的重要问题。本文研究可充电无线传感网络能量均衡路由问题。

关于能量均衡路由，文献[1]提出了一种基于混合传输的能量均衡方法避免无线传感网中的能量空洞。混合传输指网络中节点的无线收发器具有不同传输功率。在数据收集传感网网络中，靠近sink节点的无线传感器由于接收更多的来自远处传感节点的数据会更快地耗尽能量，文献[1]提出增大远处的节点的传输功率，同时概率地选择传输的接收节点，减小离sink较近节点的通信负载，推迟能量空洞的出现，延长网络寿命。文献[2]提出一种簇规模自适应调节的能量均衡分簇路由协议，协议改进了低能耗自适应集簇分层(Low Energy Adaptive Clustering Hierarchy, LEACH)算法[3]，根据节点离汇聚点的距离、剩余能量及分布密度来构造规模不等的簇，避免了低能量节点被选为簇首，达到网络能量均衡。文献[4]提出一种基于学习自动机的能量均衡分簇算法：综合考虑节点剩余能量和节点密度,利用学习自动机与周围环境进行信息交互和动作奖惩，选择出相对较优的簇头；根据簇首与基站距离和其节点密度构造大小非均匀的簇，实现不同位置不同网络疏密程度下簇内和簇间能耗互补均衡，构造了基于簇首剩余能量、簇内节点密度和传输距离的评价函数，并运用贪婪算法选择出最优中转簇首进行多跳传输。文献[5]构造了一种全局能量优化函数，并考虑网络中节点的剩余能量情况，建立路由能耗和路由剩余能量的优化度函数来评估对目标函数的优化程度，通过构造优化度函数的评价函数来求解多目标优化问题，得到能量均衡的最优路径。

上述工作主要考虑自组织网络中的能量均衡路由问题，另一些研究将能量均衡路由和无线传感节点的可充电特性结合起来考虑，如：文献[6]提出了一种移动充电模型和路由方法实现网络中节点的成功数据上传和能量均衡；文献[7]提出另一种数据收集模型，当移动sink移动到无线传感节点附近时通过单跳或多跳的方式传输数据，综合考虑了路径规划、数据路由和能量均衡问题提出了一种综合解决方案。

现有的相关工作关于能量均衡路由算法中，基于分簇的解决方案通常采用分布式算法，无法实现全局最优；同时，某些能量模型[1,5]只考虑了节点传输能耗而忽略了接收能耗；路由算法计算的是最优路径，忽视了多路径路由的可能性。针对上述模型和算法中存在的问题，本文结合考虑了一种无线能量采集场景，提出基于链路流量分配多路径路由算法和机会路由[10-11]算法，实现可充电传感网络的能量均衡，主要的工作在于：

1)在可预测的能量补充流的基础上实现能量均衡路由；

2)利用机会路由应对无线传感网络信道时变和丢失特性和其天然的负载均衡特性，达到能量均衡路由的目的；

3)使用更加精确的能量模型，考虑节点传输及接收能耗；

4)能量均衡路由算法是全局最优的。

1 网络模型与能量均衡问题

1.1 可充电无线传感器能量传播模型

本文研究的基于高压电线取电的可充电无线传感器网络中，取电、能量发射和接收装置的原理如图1所示，其中能量接收装置与距离能量发射的距离由无线充电的方式所决定。不同的无线充电方式的传输距离、功率、频率和充电效率也不相同。本文研究基于无线电波的充电方式，其有效充电距离可达数十米，适用于分布距离较大的无线传感器网络。首先研究单个取电-充电装置对于多个无线传感器节点的充电模型。在电能发射装置通过连续发射电磁波给节点无线充电的过程中，由于电磁波在空间传播时会产生衰减，这种衰减与发电装置和传感节点间的距离、传播空间环境相关。

根据电磁传播理论中的Friis传输公式，可以得到电磁波在理想空间中的传输特性。空间中任意一点处的电磁波功率P1与电磁波发射源发射功率P0的关系式如下：

P1=G1G0P0(λ/(4πd))2

(1)

其中：G1和G0分别表示接收天线和发射天线的增益；d表示接收点离发射源的距离；λ是传输的电磁波的波长。

图1 能量获取和发射装置

1.2 无线传感网络机会路由模型

机会路由是一种适用于不可靠网络的路由技术，它利用多个可能提供相似传输质量的下一跳节点，可以显著提高网络吞吐量、减少传输次数和网络能量消耗，并具有天然的负载均衡特性[10-11]。机会路由根据介质访问控制(MediumAccessControl,MAC)协议的不同实现方式也有所变化，但最关键的部分是候选集的选择。

候选集是由算法指定的有资格转发数据包的下一跳节点集合。在非低功耗场景下，由于候选集中的节点收到数据包的概率大于一个节点收到数据包的概率，因此机会路由可利用无线网络的广播特性来提高数据包投递的成功概率。在低功耗场景下，特别是节点的睡眠调度周期很长时[10]，节点很少在同一时段处于活跃状态，此时发送方通过依次单播给候选集中的节点需要传输的数据包，直到该跳传输成功为止。

1.3 可充电无线传感网络模型

假设一个基于周期性数据收集可充电无线传感网络G=(N,A,R),其中：N是所有无线传感节点的集合，包括N-1个常规节点和1个网关节点，也称为sink节点用于数据汇总和上传至互联网；A是所有节点间链路的集合，称两个无线传感节点间有一条链路当且仅当它们互相在对方的传输范围内，此时这两个节点也同时称为对方的邻居；R是电能采集和发射设备的集合。

1.4 问题

在上述模型描述的可充电无线传感器网络中，由于无线传感器的位置相对固定，在给定的各充电装置的发射功率下，各传感节点在每个观察窗口内能够采集的能量可以预测且相对稳定。在这种情况下，如果对于该数据收集的传输路径设置不当，容易造成网络中的无线传感器能量失衡。本文研究可充电无线传感网中的传输(路由)问题，以达到网络能量的均衡，其重要性体现在：

1) 传输、接收数据包所消耗的能量与从无线电波中采集的能量均衡。如果消耗的能量速率大于采集能量速率，那么节点将会在有限的时间内死亡；反之，节点的能量将会一直处于电池容量上限，浪费了充电设备所发射的能量。

2) 网络中各无线传感节点之间的能量均衡。

如果上述条件无法满足，则考虑如何最小化节点间的能量净消耗速率，延长网络的生存周期。

2 能量均衡分析模型和路由算法

根据1.1节的充电损耗模型式(1)，假设网络内的每个无线传感节点i在同一时刻只能由同一个充电设备为其充电，并令i在每个周期t内选择对其充电功率最大的为其充电。记传感节点i和充电发射装置r间的距离为di,k，则i在时段t内的充电功率可通过式(2)推导得到：

(2)

即节点i转发的流量是自身产生的流量和转发其他节点的流量之和。其数据流速率的形式为：

(3)

其中候选中继集合Si代表i转发数据的邻居节点集合。数据流量均衡模型如图2所示。

图2 数据流量均衡模型

本文假设无线传感节点以低功耗和频率采集监测数据，故忽略不计节点的数据采集功耗，则在t内i的能量消耗速率为：

(4)

(5)

(6)

易知问题一是一个关于变量qji(t)具有等式约束条件的max-min线性规划(LinearProgramming,LP)问题，求解问题一可以利用Matlab中现有的线性规划工具fminimax。

3 低功耗传感网能量均衡

在无线传感网络中，为了进一步降低网络能耗、延长网络生存周期，通常采用低功耗MAC协议使得节点在非活跃状态关闭无线收发器以减少不必要的空闲侦听能耗。在可充电传感网中，节点采用低功耗协议能够在相同的情况下相比不采用低功耗协议的场景减少充电频率。本章研究在可充电低功耗传感网中的能量均衡路由问题。

3.1 低功耗模式和机会路由

现有研究表明，传感节点在无线通信模块发送、接收、空闲、休眠状态中平均消耗的能量占总耗能的80%以上[8]。低功耗模式指无线传感节点能够在空闲时段关闭无线通信模块，进入睡眠模式，故低功耗模式在数据传输非密集型的无线传感网中能够显著减少网络能量消耗。节点只能够在活跃的状态下发送、接收或监听到数据包。周期性睡眠调度是指节点周期性、定时地睡眠、醒来，在这种睡眠调度机制下睡眠时间和调度周期的比值称为节点低功耗模式的占空比。

在占空比较低的情况下，节点同时醒来的概率很低，发送方为了成功传输数据包，需要持续发送引言包直到一个接收方醒来并回复确认包(ACKnowledgement,ACK)。如果发送方只选择一个下一跳节点，那么当该接收节点的一个活跃周期结束，发送方需要等待一个调度周期发送剩余的数据包，在不可靠链路传感网中甚至需要等待多个调度周期，增加了端到端时延。机会路由允许一个发送方选择一个邻居候选集而不只是一个下一跳以转发数据包，在低占空比情景下，候选集中的节点依次醒来，发送方按照其醒来次序分别传送数据包直到发送成功为止。

3.2 能量均衡候选集选择

机会路由能够有效降低等待延时，减少成功传输一个数据包所需的传输次数。参照第2章的算法，本文尝试利用流量分配以实现能量均衡路由，然而低功耗传感网中睡眠调度和机会路由带来的挑战在于，当一个发送方的候选节点集确定后，经过该发送方的数据流的分配也同时确定，这与候选集中节点的醒来次序、发送方到候选集中各节点的链路质量相关。因此本文研究在无法实现最优能量均衡的路由策略情况下，如何为网络中的每个节点确定转发候选集以达到较优的网络均衡。

首先考虑发送方需要发送一个数据包的情况，在流量分配策略中考虑多个数据包的情况。发送方s的转发候选集按其醒来次序递增排序记为集合fS={n1,n2,…,nK}，到候选集节点的链路质量分别记为p1,p2,…,pK，则最终候选集中第i个节点的理论期望转发概率为：

(7)

即s到前i-1个接收方的数据传输都没成功并在第i个节点处成功传输。然而在实际环境中，传感节点的时钟并不同步，随着时间增加，时钟之间可能产生漂移。当时间足够长时，可以将固定周期调度的各节点间的邻居发现时延近似为随机均匀分布，此时，候选集中第i个节点的期望被选中的概率只与发送方到自己的链路质量相关[9]，有：

(8)

考虑经过s的流量为Qs，则在s的转发候选集策略为fs的情况下，根据式(4)，其候选集中第i个节点ni的期望流量为：

Qni=P(i)·Qs

(9)

此时将问题一转化为一个最优求解问题：如何在可充电无线传感网络的每个周期中为每一个节点i选择一个最优转发候选集fi(t)，以实现机会路由下的最优网络能量均衡。形式化地表示该问题为问题二：

(10)

在问题二中，与求解问题一最大的不同在于问题二中的流量分配是由机会路由下的候选集选择、节点醒来时间和优先级考虑下的流量期望决定，而不是确定的多径路由分配。这种不确定性是由机会路由的属性所决定的。与第2章同理，使用LP可以解决该问题。

4 实验结果与分析

4.1 实验设置

本节中采用以Matlab为平台的仿真实验验证能量均衡路由协议在普通可充电传感网中和低功耗可充电传感网中的效果，在500m×500m的场地中随机布置n-1个可充电无线传感节点，网关节点位于坐标(0,0)，采用自由空间传播损耗模型模拟不可靠链路。考虑一种一对一的简单充电场景：每个充电设备位于平均高度h=20 m的高压电线上以恒定功率在每个周期为各传感节点提供能量，能量获取由式(2)计算得出。数据包传输和接收单位数据包能耗计算式分别为erx=eR和etx=eT+εamp·dα。在低功耗场景下设置节点的调度周期和占空比分别为1s和50%。实验的具体参数设置参考表1。本文提出的能量均衡路由协议和低功耗场景下的分别记为能量均衡路由(EnergyBalancedRouting,EBR)和低功耗能量均衡路由(EBRforLowpowerWSN,EBR-L)，设置的实验对比对象分别为最短路径路由(ShortestPathRouting,SPR)和期望周期最短路由(ExpectedDuty-Cycledwakeupsminimalrouting,EDC)[9]。在SPR中，节点选择以节点剩余能量占电池最大电量比重倒数为基准(metric)的到达网关节点的最短路径，以实现能量均衡路由；在EDC中，考虑了低功耗和机会路由的影响，选择期望时延最小的候选集。

表1 实验参数

4.2 评价标准

本文以归一化网络生命周期为评价标准评估路由以网络能量均衡为目标的策略好坏，归一化网络生命周期定义为网络中所有节点的平均工作时长和总周期长度的比值(不计充电周期)，以图3为例具体解释：节点i在第一个观察周期[0,t]的前1/3充电，电量从0升至E0，随后进行数据传输、转发操作，在t1时间消耗完能量，提前结束了工作周期；在第二个观察周期中，i获得了E1能量并消耗了E1-E2能量，在此周期结束时仍有电量剩余。则i在前两个周期的归一化网络生命周期为(t1-t/3+2t/3)/(4t/3)。

图3 节点i的电池能量周期

图4描述了网络的平均归一化生命周期随着节点数目的变化，随着节点数目的增加，EBR和SPR的归一化生命周期都表现出递减趋势，这是由于节点数目的增加导致了距离网关节点更近的节点增加了更多的转发任务，导致这些节点的每个周期内工作周期减少，进而降低了网络的平均生命周期。EBR的归一化生命周期总是优于SPR，因为SPR虽然选择能量剩余多的节点作为转发节点，在一定程度上缓解了网络负载不均衡，但是EBR更多地考虑了多个转发节点的负载分配对于网络均衡的影响而不仅仅是单个下一跳，故EBR能够实现更好的能量均衡。

4.3 结果分析

图5描述了低功耗场景下的网络平均归一化生命周期随着节点数目的变化，与图4相似呈递减趋势。EBR-L优于EDC的原因是后者更多地考虑了时延而非能量均衡。值得注意的是，与图4相比，EBR-L的归一化生命周期均优于EBR，这是因为EBR的场景从广义上来说是多路径路由而不是机会路由，而在低功耗的机会路由下，EBR-L在没有任务时可以进入休眠状态，从而节约了空闲侦听的能量。

图4 归一化生命周期随节点数目变化

图 5 低功耗场景归一化生命周期随节点数目变化

对比图4～5，可以发现EBR比EBR-L在相同的配置下具有更长的网络生命周期，这是因为首先本文在实验中只考虑收发数据包的能耗，其次从信息论角度考虑，EBR使用全局网络信息进行优化，而EBR-L是分布式的路由算法，前者比后者拥有更多的信息故更优。

考虑两种算法的复杂度，EBR采用线性规划算法，时间复杂度为n的多项式级别；EBR-L在前者的基础上增加了关于转发候选集的约束条件，搜索空间大于EBR，但仍为n的多项式级别时间复杂度。

5 结语

为解决可充电无线传感网络中的能量均衡路由问题，分别针对非低功耗场景和低功耗场景，本文提出基于多路径路由和机会路由的路由协议。前者根据充电速率、自身电池剩余电量、接收和发送数据包的单位能耗等信息，通过全网的线性规划为每个参与转发的节点的候选集规划链路流量；后者为每个转发者选择一个能耗最优的候选集，在机会路由框架下延长网络寿命。实验结果表明，提出的两种路由算法能够有效地实现网络均衡。接下来将针对复杂移动场景下的可充电无线传感网络的路由问题进行研究。

)

[1] 夏先进,李士宁,张羽,等.一维传感网中混合数据传输的能量均衡[J].软件学报,2015,26(8):1983-2006.(XIAXJ,LISN,ZHANGY,etal.Energybalanceofmixeddatatransmissionin1Dsensornetworks[J].JournalofSoftware, 2015, 26(8): 1983-2006.)

[2] 吴华君,张自力,李卫.一种适用于煤矿井下无线传感网的能量均衡路由协议[J].计算机科学,2011,38(4):145-150.(WUHJ,ZHANGZL,LIW.Energy-balancedroutingprotocolforwirelesssensornetworksincoalmine[J].ComputerScience, 2011, 38(4): 145-150.)

[3]HEINZELMANWR,CHANDRAKASANA,BALAKRISHNANH.Energy-efficientcommunicationprotocolforwirelessmicrosensornetworks[C]//HICSS’00:Proceedingsofthe33rdHawaiiInternationalConferenceonSystemSciences.Washington,DC:IEEEComputerSociety, 2000: 8020.

[4] 曹立志,陈莹.基于学习自动机的无线传感网能量均衡分簇算法[J].传感技术学报,2013,26(11):1590-1596.(CAOLZ,CHENY.Energybalancedclusteringalgorithmbasedonlearningautomataforwirelesssensornetwork[J].ChineseJournalofSensorsandActuators, 2013, 26(11): 1590-1596.)

[5] 米志超,周建江.一种能量均衡的无线传感网络生命期优化算法[J].系统工程与电子技术,2008,30(12):2477-2480.(MIZC,ZHOUJJ.Energy-balancedoptimizationalgorithmformaximizingnetworklifetimeinwirelesssensornetworks[J].SystemsEngineeringandElectronics, 2008, 30(12): 2477-2480.)

[6]ANGELOPOULOSCM,NIKOLETSEASS,RAPTISTP,etal.Efficientenergymanagementinwirelessrechargeablesensornetworks[C]//MSWiM’12:Proceedingsofthe15thACMInternationalConferenceonModeling,AnalysisandSimulationofWirelessandMobileSystems.NewYork:ACM, 2012: 309-316.

[7]MAOSB,CHEUNGMH,WONGVWS.Jointenergyallocationforsensingandtransmissioninrechargeablewirelesssensornetworks[J].IEEETransactionsonVehicularTechnology, 2014, 63(6): 2862-2875.

[8] 杜欣.WSN低功耗算法在电力系统中的应用[J].电力系统通信,2012,33(4):62-66.(DUX.ApplicationofWSNtechnologybasedlow-powerconsumptionalgorithmsinpowersystem[J].TelecommunicationsforElectricPowerSystem, 2012, 33(4): 62-66.)

[9]GHADIMIE,LANDSIEDELO,SOLDATIP,etal.Opportunisticroutinginlowduty-cyclewirelesssensornetworks[J].ACMTransactionsonSensorNetworks, 2014, 10(4):ArticleNo. 67.

[10]GUY,HET.Dynamicswitching-baseddataforwardingforlowduty-cyclewirelesssensornetworks[J].IEEETransactionsonMobileComputing, 2011, 10(12): 1741-1754.

[11] 赵灿明,李祝红,闫凡,等.电力通信网络中负载均衡的路由协议[J].计算机应用,2016,36(11):3028-3032.(ZHAOCM,LIZH,YANF,etal.Loadbalancedroutingprotocolinelectricpowercommunicationnetworks[J].JournalofComputerApplication, 2016, 36(11): 3028-3032.)

ThisworkispartiallysupportedbytheNationalNaturalScienceFoundationofChina(61379130, 61672485).

XIE Xiaojun, born in 1975, M. S., engineer. His research interests include electric power communication system.

YU Hao, born in 1975, M. S., engineer. His research interests include electric power communication system.

TAO Lei, born in 1992, Ph. D. candidate. His research interests include wireless network, smart grid.

ZHANG Xinming, born in 1964. Ph. D., professor. His research interests include wireless network, smart grid.

Energy-balanced routing algorithm in rechargeable wireless sensor networks

XIE Xiaojun1, YU Hao1, TAO Lei2, ZHANG Xinming2*

(1.DivisionofInformationCommunication,StateGridAnhuiElectricPowerCompany,HefeiAnhui230061,China; 2.SchoolofComputerScienceandTechnology,UniversityofScienceandTechnologyofChina,HefeiAnhui230027,China)

Aiming at energy-balanced routing problem in rechargeable Wireless Sensor Network (WSN), a new multi-path routing algorithm and an opportunistic routing algorithm were proposed in the scenario of wireless charging with stable power and monitoring data collection network, so as to achieve the energy balance of the network. Firstly, the relationship model between the charging power and the receiving power of wireless sensor nodes was constructed by the theory of electromagnetic propagation. Then, considering the sending and receiving energy consumptions of wireless sensor nodes in the network, the energy-balanced routing problem was transformed into the max-min optimization lifetime problem of the network nodes. The link traffic obtained by the linear programming was used to guide the data flow allocation in the routing. Finally, considering a more realistic scenario of low power WSN, an energy-balanced routing algorithm based on opportunistic routing was proposed. The experimental results show that, compared with the Shortest Path Routing (SPR) and Expected Duty-Cycled wakeups minimal routing (EDC) algorithms, the proposed two routing algorithms can effectively improve the utilization ratio of the energy collection and the network lifetime in the working period.

energy-balanced routing; rechargeable Wireless Sensor Network (WSN); opportunistic routing; low power sensor network

2016- 11- 17;

2017- 02- 04。 基金项目:国家自然科学基金资助项目(61379130,61672485)。

谢小军(1975—)，男，安徽泾县人，工程师，硕士，主要研究方向：电力通信系统； 于浩(1975—)，男，安徽临泉人，工程师，硕士，主要研究方向：电力通信系统； 陶磊(1992—)，男，安徽和县人，博士研究生，主要研究方向：无线网络、智能电网； 张信明(1964—)，男，安徽天长人，教授，博士，CCF高级会员，主要研究方向：无线网络、智能电网。

1001- 9081(2017)06- 1545- 05

10.11772/j.issn.1001- 9081.2017.06.1545

TP393.03

A