杨 佳， 盛 欢， 许 强

(1.重庆理工大学 电气与电子工程学院，重庆 400054; 2.重庆工商大学 计算机科学与信息工程学院,重庆 400067)

0 引 言

无线可充电传感器网络(wireless rechargeable sensor networks,WRSNs)[1]由于能解决无线传感器网络(wireless sensor networks,WSNs)电池能量受限问题而受到广泛关注，采用无线充电技术 (wireless charging technique,WCT)[2]能够对网络节点及时补充能量，克服恶劣环境或人为等因素导致的节点能量不足，从而保证网络的正常运行。在实际应用中，无线移动充电设备(wireless mobile charging equipment，WCE)的能量是有限的，为了更高效地分配设备自身能量，有必要研究WCE能量受限时的充电路径规划问题。He L等人[3]提出最近优先充电算法NJNP，始终选择距离WCE最近的节点充电，很好地减少了WCE的移动耗能，但该方法忽略了WCE的充电效率问题。刘蕴娴等人[4]提出能量收益的路径规划算法MMAS-CM，总是以节点剩余能量最少的标准来选取下一个充电节点，但未考虑节点地理位置对充电顺序的重要影响。Xu J等人[5]提出使WCE总消耗值最小的节点以均衡寿命的方式充电，但该方法没有合理地估算到请求充电节点的能量阈值。蒋婵等人[6]提出综合考虑节点的位置和能量信息，在限定的路径长度下为节点补充能量的方法。Feng Y等人[7]提出以最小节点失效率为目标的路径规划算法，虽能有效地减少网络中节点的死亡数量，但没有考虑到充电节点之间的优先级问题，容易造成WCE充电路径不合理而消耗太多的移动能量，使WCE的充电利用率较低。以上研究大多数考虑了WCE的行驶能量和充电能量共用时的充电路径规划，很少综合考虑其能量分开且均受限[8]时的充电路径规划。

本文提出一种基于节点充电优先级(max-min ant system and charging node priority，MMAS-CNP)的路径规划算法，在WCE行驶距离一定时携带有限的充电容量为网络节点及时地充电，并合理地估算网络节点的能量阈值，综合考虑节点的地理位置、剩余能量和能量消耗率[9]这3个因素比较充电节点之间的优先级，从而确定节点的充电顺序，最后采用MMAS算法约束WCE的能量受限问题，以节点的充电优先级为依据选取下一个充电节点，最终WCE选择一条使节点充电优先级最高的路径来进行能量的补充。

1 系统模型

WRSN充电模型如图1所示，该网络由可充电传感器节点、基站(base station，BS)、服务站和1个WCE组成[10]。假设在方形网络区域内，剩余能量低于阈值的节点被称为“需要充电的节点”，反之为“不需充电节点”， WCE只为“需要充电的节点”充电并且根据优先级进行选择。

图1 网络充电模型

WCE在行驶过程中主要有3种工作状态[11]，分别是移动状态、充电状态和休假状态，如图2所示。

图2 WCE状态转移

2 确定节点的能量阈值

本文对网络中的节点采取按需充电的方式，只有当节点能量低于阈值时，该节点才会被选择充电，因此对能量阈值[12]的选取相当重要，阈值过大或过小均会导致网络性能不佳，故有以下具体分析。

1)WCE携带的充电容量Ec

由于WCE的能量受限，因此需保证WCE每次充电服务的节点数量不能过少也不能过多，即WCE实际充电服务的节点数量应当不大于WCE可充电服务的节点数量。因此可得

Ec/Emax×ω≤λTN

(1)

式中ω(0<ω<1)为期望的WCE能量利用率，Emax为节点的最大能量；在T时间内，网络节点数量为N，WCE对“需要充电节点”的平均到达率为λ，具体取值为

(2)

(3)

将式(2)、式(3)代入式(1)中并化简得到

(4)

2)网络的剩余能量

WCE按顺序依次为节点补充能量时，无法保证为所有节点及时充电，因此节点在充电之前的剩余能量至少要维持自身的能量消耗。

假设Tw为网络中N个节点的总等待时间；TwN为第N个节点的等待时间，由前N-1个节点的充电时间和WCE到第N个节点的移动时间构成，即

Tw=Tw1+Tw2+…+TwN

(5)

式中v为WCE的移动速度。若Tw/N为每个节点的平均等待时间，则节点在该时间内消耗的能量应当不超过能量阈值，因此有

(6)

(7)

3)单个节点的能量消耗值

当节点m的剩余能量低于阈值时，为了确保节点m的存活，应在其最大等待时间tm内保证自身的能量消耗足够，即

tm≤Eth/Rm

(8)

式中tm为WCE移动到节点m的时间，将其代入式(8)可得到

(9)

综上，能量阈值的选取公式有式(4)、式(7)和式(9)，但为了使网络性能更好，选取其中的最大值作为节点的能量阈值。

3 MMAS-CNP算法求解

3.1 确定节点的充电顺序

充电路径规划问题中最重要的是确定节点之间的充电顺序，而本文提出的MMAS-CNP算法是通过节点的充电优先级实现的，由于影响节点充电优先级的因素较多，本节将引入中间量—节点的充电适配度值来进行比较。节点m的充电适配度值越小，其充电优先级越高，那么节点m被选为下一个充电节点的概率就越大。

节点的剩余能量是影响WCE充电路径规划问题的重要因素，能量越低则表示该节点越需要充电；节点离BS越近，则表示WCE到达该节点的路径和时间越短，WCE越容易为其充电；节点的能量消耗率越大，表示其能量的消耗速度越快，在相同剩余能量条件下该节点更需要被及时充电。因此,本文综合考虑这3个因素计算节点的充电适配度值，如式(10)所示

(10)

式中fm为节点m的充电适配度值，δ,μ,φ分别为剩余能量Em,距离Dm和能量消耗率倒数R′的权重，其取值为δ=0.4,μ=0.3,φ=0.3。

充电优先级Pm=1/fm选取算法如下：

{

1)while (Ethworking status=1) do

2)Input:Em,En,Rm,Rn,Dm,Dn,Pm,Pn

3)Output: Comparison ofPm,Pn

5)Pm>Pn

8)Pm>Pn

9)elsePm

10)end if

11)elsePm

12)end if

}

3.2 WCE能量受限的路径规划

本文的充电路径以节点的最大充电优先级为目标进行规划，将能量受限问题转化为WCE最大行驶长度Lmax和充电容量Ec受限的NP-hard[13]问题，采用最大—最小蚂蚁算法进行求解，主要包括2个内容：选择下一节点的规则、信息素的更新规则[14]。具体实现过程如下：

Step 1 初始化参数。设Nc_max=400，信息素初始浓度为τmn=τmax=0.9。

Step 2 放置k只蚂蚁从基站出发，令迭代次数Nc=1，当Nc

Step 3 按照式(11)选择下一个节点n。由于蚂蚁在不同阶段有不同的状态转移规则，因此将引入一个随机数q选择节点n，其规则如下

(11)

蚂蚁k的转移概率为

(12)

Step 4 计算WCE移动到节点n的距离(dmn)与WCE为节点n充电的能量(Emax-En)。

Step 5 选定节点n后，计算此时WCE将行驶的总路径长度Ltsp与将为节点充电的总能量Etsp，判断是否同时满足Ltsp≤Lmax且Etsp≤Ec。若是，WCE选择节点n并为其充电，并在集合V中剔除该节点并更新；若否，则跳转到Step 3，重新选择下一个充电节点。其中，Ltsp和Etsp的计算公式如下

(13)

(14)

式中dn0为节点n到基站节点的距离。En为节点n的剩余能量，Emax为每个节点的最大能量。

Step 6 判断是否所有蚂蚁都完成了路径搜索,若是,跳转到Step 7，若否,则跳转至Step 3。

Step 7 记录本次迭代中节点充电优先级最高的路径，并更新这条路径的信息素。τmn的更新规则为

(15)

式中

(16)

Step 8 判断迭代次数是否达到预设次数Nc_max，若是则跳转到Step 9，否则跳转至Step 3。

Step 9 输出此次充电优先级最高的路径。

4 仿真与分析

本文采用MATLAB R2016a软件进行仿真检验与性能分析，为了验证本文提出的MMAS-CNP算法的可行性和有效性，将其与经典的NJNP[3]和MMAS-CM算法[4]对比分析。将100个节点随机布撒在200 m的方形区域内，其他参数设置：基站/服务站位置为(100,100)m，节点最大能量Emax为10 J，能量阈值Eth为0.4Emax，WCE充电容量Ec为5 000 J，WCE行驶长度Lmax为250 m，WCE移动速度v为5 m/s，WCE充电效率h为200 mJ/s，WCE的移动能耗Δc为4 mJ/s，期待的能量利用率ω为0.8。

4.1 技术评估指标

本文将通过充电节点的失效率和网络寿命这两个指标来实现：1)充电节点的失效率：是指由于WCE来不及充电而导致节点失效死亡的数量与需要充电节点的数量之比。充电节点的失效率越小，则表示节点的充电顺序安排得越好;2)网络寿命：是指网络从开始运转到充电节点的失效率达到一定值时，网络停止工作的时间。网络寿命越长，则表示充电路径规划得越合理。

4.2 仿真结果分析

WRSN充电路径规划的问题研究中， WCE对节点的充电效率和网络的节点数量对充电路径都有一定的影响。若WCE对节点充电的效率越高，则说明在单位时间内WCE为节点补充的能量越多，WCE充电速率越快，节点完成充电的时间越短。若网络中节点数量越多，则说明需要充电的节点数量也越多，WCE的充电负担就越重，那么WCE来不及为节点充电而死亡的节点数量越多，充电路径就越不合理。

4.2.1 WCE的充电效率

将WCE对节点的充电效率从[100,300]mJ/s进行调试，其他参数保持不变，分析网络性能的变化情况如图3(a)和图3(b)所示。

图3 不同充电效果的影响

如图3(a)所示，随着WCE充电效率的增大，3种路径规划算法的充电节点失效率均在降低，而MMAS-CNP算法与其他两种算法相比，充电节点的失效率都是最低的，这是由于在节点的充电顺序选取中，合理地考虑了节点的剩余能量和能量消耗率对充电顺序的影响，使得剩余能量越低、能量消耗越快的节点优先被选择充电。随着WCE的充电效率越高，WCE完成充电的节点数量越多，充电节点的失效率也随之降低。当充电效率达到175 mJ/s之后，充电节点的失效率的下降趋势比较平缓，这是由于WCE此时已经能满足大部分节点的充电需求，当充电效率达到225 mJ/s时，充电节点的失效率接近于0。如图3(b)所示，3种算法的网络寿命都随着WCE充电效率的增大而升高，而MMAS-CNP算法由于充电节点失效率降低，WCE能为更多存活的节点补充能量而延长了网络寿命。

4.2.2 节点的数量

将网络的节点数量从[25,200]进行调试，其他参数保持不变，分析网络性能的变化情况如图4所示。

图4 不同网络节点数量的影响

如图4(a)所示，节点数量较少时，WCE的充电任务比较简单，能为全部需要充电的节点补充能量，因此充电节点的失效率很低。当节点数量在75～200范围内，MMAS-CNP的节点失效率最低，这是因为节点数量越多，需要被充电的节点数量就越多，因此,节点的充电顺序很重要，而MMAS-CNP算法优先考虑了节点所能等待的时间和地理位置，使得那些急需充电和距离较近的节点能及时得到WCE的充电服务，从而降低了充电节点的失效率。如图4(b)所示，若网络节点的数量越多，则表示需要充电的节点越多，此时WCE的充电负担越沉重，而每一次WCE所充电的节点能量是一定的，因此,WCE会更加来不及为节点充电而导致节点死亡个数增多，从而导致网络失效而停止工作，网络寿命则越短。

5 结束语

为了规划一条合理的充电路径，本文在确定节点的能量阈值后，考虑到节点充电优先级对充电顺序的影响，分别对节点的剩余能量、地理位置和能量消耗率赋予相应的权值并计算比较，最后在WCE最大行驶长度和一定的充电容量下运用最大最小蚂蚁算法进行路径规划。该方法降低了充电节点的失效率，提高了网络寿命，但网络规模更大时，单个WCE将无法完成所有的充电任务，因此，需要考虑多个WCE为网络节点补充能量的情况。