无线可充电传感器网络(WRSN)[1]是无线传感器网络的自然扩展，即引入移动充电设备(MC)对无线传感器进行近距离充电．WRSN解决了传感器无法补充能量的问题，但受地理环境和能量限制等客观物理因素干扰，MC无法对传感器及时充电，导致传感器失效死亡，网络生命周期也随之严重缩短，因此须合理考虑网络中MC的充电策略．针对WRSN中的充电策略问题，文献[2]以传感器功率大小对网络中所有待充电节点进行聚类划分，设计了基于TSP问题的求解算法；文献[3]提出一种联合充电方案并制定针对MC往返基站两种情况下的调度策略；文献[4]设计了充电基站的部署算法和最小化MC数量的路径规划算法；文献[5]提出一种充电束模型，通过考虑相邻待充电节点的位置关系优化充电路径；文献[6]提出一种局部能量充电模型，优化了传感器节点的充电分配策略．由于以上研究大多是在理想环境下优化充电路径，没有在有限的能量资源与多充电周期条件下考虑整体的充电策略，因此未能充分利用有限的能量资源．本研究在传感器网络能耗分布不均的情况下，将多周期充电问题形式化表达为多目标优化问题，考虑在最大化MC充电效率的同时最小化节点死亡个数，从注意力机制[7]的核心思想出发，设计出一种在线充电路径规划策略．相较于文献[8]，实验证明所提出的算法可充分降低节点死亡率，提高MC充电效率并且延长网络的工作周期．1 问题描述与定义1.1　网络模型与数学描述如图1所示，WRSN部署在一个物理空间中进行感知任务，传感器节点随机分布在该感知区域中，基站(BS)位于地理位置中心处，负责实时收集传感数据及对MC进行蓄电．MC通过磁耦合谐振技术对传感器进行一对一充电，并在能量不足的情况下返回基站进行重新蓄电，待蓄电完成后循环开始下一轮充电任务．10.13245/j.hust.210217.F001图1无线可充电传感器网络模型1.2　网络能耗模型1.2.1　传感器能耗模型设网络中传感器节点的规模为N，以集合S={s1,s2,…,sn}表示，dj,k为节点sj与sk之间的欧式距离，节点间使用多跳无线通信技术转发数据，其通信半径固定为r．当充电任务开始时，各传感器节点的剩余电量均为固定值Emax，由于多跳无线通信原因，S中不同传感器节点的电量消耗功率差异较大，本研究参考文献[9-10]中的通信能耗模型，将传感器的运行状态分为工作状态与睡眠状态．当传感器处于工作状态时，假设节点sj每单位时间向r范围内的所有节点转发L的感知数据，则该节点的功率为pjc=L∑k∈Nj≠kdj,k(dj,kεamp+εs)+pf    (dj,k≤r),式中：εamp为传输放大器系数；εs为距离相关项系数；pf为接收其他传感器充电请求的监听功率．令传感器节点的最小剩余电量为Emin，则当Emin=μEmax时转为睡眠状态，其中μ为阈值系数．此时传感器关闭数据接收模块，发送包含位置和电量信息的充电请求，请求数据将传输至最近的传感器节点sk．因此传感器的睡眠状态功率为pjs=G(εamp+εs)dj,k2    (dj,k≤r),式中G为节点sj单位时间发送的请求数据．1.2.2　移动充电设备能耗模型MC会在接收到首个充电请求后从基站出发，在充电过程中始终以速度v匀速行驶，并按照给定的充电路径依次为传感器节点充电，定义EMC为MC可携带的最大电池容量，Em与Ec分别为MC移动能耗与充电能耗，em为MC行驶单位距离所消耗的电量，ec为MC单位时间内的充电能耗．1.2.3　充电效率与节点死亡率定义充电任务的总时间为Tmax，充电效率为η，则η为在Tmax内MC充电能耗Ec与行驶能耗Em之比．当MC无法及时为某个传感器节点进行充电而导致其能量耗尽时，视为该节点临时死亡[11]．定义节点死亡率为ζ，表示在时间到达Tmax后网络中节点死亡总数与传感器总数的比值，nd为充电任务结束后网络中临时死亡节点个数，则有：η=Ec/(Ec+Em);ζ=nd/N．1.3　多充电周期下的问题定义通过引入η和ζ，问题可完整定义为：在时间Tmax范围内，如何求解出最佳的MC充电路径集合Q，从而满足网络模型中η最大化与ζ最小化的要求．在真实环境中MC能量受限，须要多次往返基站进行蓄电补充，将MC执行一次往返充电的过程作为一轮充电周期，设MC在Tmax内的往返次数为变量u，则可将Tmax分解为集合T={T1，T2,…,Tu}，令Ti表示第i轮充电周期的时长，则有∑i=1uTi=Tmax．(1)定义队列Ci，将第i轮充电周期中所有被充电的传感器节点添加至Ci中．为体现第i轮充电周期内各节点被MC充电的先后顺序，将队列Ci中各元素下标用索引变量进行映射，则有{scψ∈Ci|Ci⊆S}，其中传感器节点scψ为队列Ci中的变量元素，cψ为该节点在Ci中的索引，例如当Ci中的第1和2位元素分别为s3和s7时，则索引变量c1=3，c2=7．定义第i轮充电周期下的充电路径为集合qi，为拟合真实充电场景，要求集合qi中的首尾均为基站，将基站定义为节点s0，则有qi={s0,{Ci},s0}，根据式(1)可知Q={q1,q2,⋯,qu}．定义dcψ-1,cψi为Ci中的传感器节点scψ与上一被充电节点之间的距离，变量m为第i轮周期中被充电的节点个数，则MC在该周期中的充电路径长度为L(qi)=∑ψ=2mdcψ-1,cψi+d0,c1i+dcm,0i．另外，若使MC能够在第i轮充电周期结束后返回基站，则EMC应始终大于等于该轮的充电能耗Eci和移动能耗Emi之和，其中Emi=L(qi)em，则有EMC≥Eci+Emi    (i≤u)．(2)定义tcψd为节点scψ从电量Emax到0所维持的时间，则有tcψd=[pcψs(Emax-Emin)+pcψcEmin]/(pcψcpcψs)，(3)式中pcψc与pcψs分别为节点scψ的工作状态和睡眠状态功率．设τcψi为第i轮充电周期中MC到达传感器节点scψ的时刻，其中0≤τcψ i≤Ti，定义节点scψ在τcψi时刻的剩余电量为Ecψi(τcψi)，则有τcψi=1v∑j=2ψdcj-1,cji+d0,c1i+1ec∑j=1ψ(Emax-Ecji(τcji))．(4)设l为节点scψ最近一次被充电时所在的充电周期次数，该值可从当前集合Q中求出，即逆向遍历Q直至找出首次包含scψ节点所在的队列Cl，该队列的下标即为所求l值，若scψ∉Q，则l=0．定义节点scψ前次至本次被充电的时间间隔为tl,icψ，则有tl,icψ=∑j=0i-1Tj+τcψi    (l=0);∑j=li-1Tj+τcψi-τcψl    (l≠0). (5)为保证队列Ci中的节点scψ在MC到达之前不死亡，tl,icψ应满足tl,icψtcψd．(6)综上，对于WRSN内任意一个传感器节点sj，根据式(3)求得维持时间tjd后，该节点在τcψi时刻的剩余电量为Eji(τcψi)=Emax-tl,icψpjc    (tl,icψ[(1-μ)Emax]/pjc);pjs(tjd-tl,icψ)    (tjdtl,icψ≥[(1-μ)Emax]/pjc)0    (tl,icψ≥tjd).; (7)定义变量xj,ki={0,1}(sj,sk∈S)，当xj,ki=1时，表示两个传感器节点sj与sk均在MC的第i轮充电节点路径qi中，且MC对sj与sk的充电次序前后紧邻；当xj,ki=0时，表示传感器节点sj与sk并未在该轮充电周期中被充电．定义变量yj,ki(sj,sk∈S)，当yj,ki=0时，表示MC从传感器节点sj处移动至下一目标节点sk进行充电，且传感器节点sk在τki时刻的剩余能量Eki(τki)恒大于零；当yj,ki=1时，表示MC从节点sj处移动至节点sk的过程中，sk的剩余电量会被耗尽．因此yj,ki满足条件yj,ki=1    (Eki(τki)=0);0    (Eki(τki)0). (8)通过引入变量xj,ki与yj,ki，式(2)可替换为EMC≥∑j=0n∑k=0n[xj,kidj,kiem+(1-yj,ki)(Emax-Eki(τki)]. (9)综上所述，对于多充电周期下的充电规划问题，其目标函数可定义为：minQf(Q)=ζ,η-1=f1(xj,ki),f2(yj,ki)；(10)f1(xj,ki)=∑i=1u∑j=0nxj,kidj,k;f2(yj,ki)=∑i=1u∑j=0nyj,ki,s.t.式(1)、(6)、(8)、(9)j≠k    (j,k=0,1,2,…,n)；∑j=1nx0,ji=∑k=1nxk,0i=1    (i=1,2,…,u)；(11)xj,ki+xk,ji≤1    (j,k=1,2,…,n,i=1,2,…,u)；(12)∑j=1nxj,ki=∑j=1nxk,ji≤1    (k=1,2,...,n)．(13)式(11)保证MC在充电周期开始时从基站出发并在充电任务结束后返回基站，式(12)表示MC的充电路径中无重复回路，式(13)确保在单轮充电周期中每个传感器节点最多只允许被充电一次．2 基于注意力机制的充电规划策略针对上述多目标问题的求解办法，由于传统的加权求和法或分量排序法等算法难以在多个充电周期的约束条件下求出问题的近似最优解，因此须进一步设计求解策略以充分满足WRSN中能耗与时限等多项约束条件．2.1　多目标模型的处理使用主要目标法将多目标优化问题转化为单目标优化问题，以最大化MC充电效率为优化目标．其他约束条件不变，将式(10)中最小化节点死亡率的目标函数转化为约束条件ζ=∑i=1uf2(yj,ki)=∑i=1u∑j=0n∑k=0nyj,ki≤D0, (14)式中D0为死亡节点成本．通过以上转换将该问题转变为单目标优化问题．2.2　传感器节点选择算法注意力机制本质上是将网络内不同的客观属性赋予不同的权重，在算法中引入注意力机制可在一定程度上提高算法的表达能力，加强算法对有效信息的关注．本研究提出一种利用注意力机制的待充电节点动态选择算法，通过判断节点在充电任务中的重要性程度，选择最佳的待充电节点，算法具体内容如下．在第i轮充电周期中，MC将依次遍历传感器节点并计算该节点对于充电任务的重要性程度，即确定属性中的各项权重后进行加权求和．由充电任务的特性可知：充电效率与待充电传感器节点至MC之间的距离及该节点的剩余电量有关，定义当前MC所在节点为sj，当前时刻为τji，sk为网络中另一节点，则可将dj,ki和在τji时刻节点sk的剩余电量Eki(τji)作为衡量节点sk重要性程度的特征变量，在使用线性比例变化法将特征变量标准化后，节点sk的重要性程度表达式为I(sk)=dj,ki/dmax+(Emax-Eki(τji))/Emax, (15)式中dmax为网络中两个相距最远节点之间的距离．为使算法满足式(14)中的约束条件，即保证WRSN中传感器节点的死亡个数不超过D0，进一步改进重要性程度表达式，使算法可以根据当前时刻下的网络情况动态改变各项属性的权重系数，因此将式(15)扩展为I(sk)=(λ-β)(dj,ki/dmax)+β(Emax-Eki(τji))/Emax，(16)式中：β=D(τji)/D0，D(τji)为在τji时刻网络中死亡节点的个数；λ为距离特征的权重系数．由式(16)可知：当传感器节点的死亡数量增多时，传感器电量属性的权重增加，而距离属性所占的权重降低．当D(τji)=D0时，MC将选择当前电量最低的节点作为下一充电目标，以满足式(14)中的约束条件．2.3　在线路径优化算法对于多周期充电规划问题，由于传感器节点的剩余电量在各轮充电周期中均有差异，因此设计了一种在线路径优化策略(AMCO)，通过增加备选充电节点集合，实时剔除网络中的不可达节点，以进一步筛选出最佳的待充电节点集合．该算法的主要步骤如下．步骤1 确定死亡节点成本D0．步骤2 确定待充电节点队列Ci和备选节点集合Ci*．a. 根据式(3)求出网络中各传感器节点的死亡时限tkd(k=1,2,…,n)；将所有节点按tkd从小到大的顺序依次放入队列Ci中．b. 删除不可达节点：将基站节点s0分别插入队列Ci的列头和列尾，并根据Ci中节点的顺序遍历．对于任意节点scψ∈Ci，根据式(4)和(5)分别求出MC到达scψ的时刻τcψi与时间间隔tl,icψ，若tl,icψ≥tcψd，则视scψ为不可达节点，将该节点从Ci中移除．定义集合Q，将不可达节点添加至集合Q中．c. 计算队列Ci下的移动能耗Emi，若Emi≥EMC，则证明MC的电量无法满足该条路径下的移动能耗，删除Ci中倒数第二个节点，并重新计算Emi直至EmiEMC．将队列Ci以外的节点放入集合Ci*中．上述操作保证了在当前充电顺序的路径下Ci中各节点电量恒大于0．步骤3 确定Ci中各节点的重要性程度．定义变量τcuri为当前时刻，scur和Ecuri分别为τcuri时刻下的被充电节点和MC已消耗的电量，当每轮充电任务开始时，Ecuri=τcuri=0．a. MC遍历队列Ci，对于任意节点scψ∈Ci，通过式(7)和(16)分别计算出scψ在τcuri时刻的Eji(τcuri)与该节点重要性程度I(scψ)，选择I(scψ)值最高的节点sck∈Ci作为下一充电目标．b. 通过式(4)和(5)分别计算τcki与tl,ick，使用式(6)中约束条件进行判断，若tl,icktckd，则将节点sck作为下一充电目标，更新scur=sck，τcuri=τcki，Ecuri=Eji(τcuri)+Emi；若tl,ick≥tckd，则表明节点sck会在该轮充电周期内死亡，同样视sck为不可达节点，将其移除队列Ci并添加至集合D中，更新式(16)中的β值．c. 重复执行步骤a和b直至完全筛选出队列Ci中所有节点．步骤4 判断MC返回条件．MC对Ci中各节点充电完成后，将立刻判断EMC是否满足式(9)中的约束条件，若在τcuri时刻有EMCEcuri+dmaxem+Emax，则证明MC有足够电量继续进行充电任务，此时选择备选集合Ci*中的节点作为下一目标，并继续执行步骤3；同理，设dcur,0i为MC当前位置与基站之间的距离，若在时刻τcuri有Ecuri+dcur,0iem≤EMC≤Ecuri+dmaxem+Emax，则MC将停止充电任务并返回基站进行蓄电，至此第i轮充电周期完成．将本轮中所有被充电的节点按顺序添加至集合qi中，计算网络中所有节点的剩余电量，将电量为0的节点添加至集合D中，同时更新式(16)中的β权重．步骤5 待MC在基站蓄电完毕，下一轮充电周期开始，i值加1．为保证式(1)中的约束条件，循环执行步骤3～5，直至在第u轮周期中累计总时间到达Tmax，充电任务结束，在D0条件下的集合Q={q1,q2,…,qu}即为优化后的充电路径．3 实验结果与分析使用python编程语言仿真无线传感器网络模型．实验设计为：在500 m×500 m的正方形区域内以随机分布的方式部署若干个传感器节点，基站设立在该区域的中心处，设定参数Emax=1 kJ，EMC=30 kJ，em=3 J/m，ec=200 J/s，μ=0.1，L=10 Kb/s，G=4 Kb/s，εs=100 nJ/(bit∙m)，εamp=2 nJ/(bit∙m2)，pf=100 mJ/s，r=100 m，v=8 m/s，λ=0.3．实验过程中使用AMCO算法求解多周期下的完整充电路径.3.1　死亡节点成本对充电效率的影响比较了在6次充电服务周期中不同死亡节点成本D0对MC的充电效率的影响．从图2可知：自第三次充电周期开始，由于MC自身电量有限，因此使得个别位置偏远或功率较大的传感器因无法被及时充电而死亡．随着网络中节点死亡个数增多，重要性程度函数中的β值将逐渐增大，MC的充电效率会随D0值的减少而逐渐上升．对比同一D0值下的充电效率，由于传感器节点的电量消耗与时间成正比，因此在每轮充电周期中，MC会相较于上一轮充电周期传输更多的电量，进而使其充电效率随时间增高．在D0较小的情况下，MC减少了对传感器的充电频率，移动能耗相对减少，同时也增加更多的充电能耗，因此提高了充电效率．在D0较大的情况下，MC在充电过程中往往更偏向于对距离较近的传感器进行充电，但此类传感器因充电时间间隔较小，仍保留较多的电量，因此充电效率较低．10.13245/j.hust.210217.F002图2MC充电效率与D0之间的关系3.2　性能指标对比与分析将AMCO算法与先来先服务(FCFS)及NJNP算法[8]进行比较．NJNP算法中MC把相对距离最近的传感器作为目标节点，进行可抢占式优先的充电服务，而FCFS算法中MC始终优先将网络中能量最低的节点作为下一充电目标，即忽略无线传感器节点中的距离属性．定义σ为任务结束后网络内剩余工作节点的平均剩余电量，该指标可衡量不同策略下WRSN的工作寿命长短，σ值越大越能够保证WRSN在尽可能长的周期内维持稳定工作．图3分别给出了三种算法在Tmax=2 200  s且传感器规模为50，60，70，80，90，100的情况下各项性能指标差异．从图3(a)可知：AMCO算法相较于其他两种算法表现更佳．与NJNP算法相比，AMCO算法在多个传感器节点距离同等或近似相等的情况下总会选择出集合中电量最低的节点作为下一充电目标，充电效率提高了2.4%．从图3(b)可知：对于网络中的传感器节点的死亡率，AMCO算法与NJNP算法及FCFS算法相比分别降低了36%与69%，这是因为注意力机制可以动态改变传感器电量属性对于充电优先级的权重大小，所以在每轮充电周期内，MC可以始终优先为电量较低且距自身位置较近的节点进行充电．图3(c)可知：AMCO算法可以使网络中传感器的平均电量保持在最大电量的56%左右，相对于NJNP算法与FCFS算法分别提高了13.9%与40.3%．在充电任务后期，网络中会出现更多的死亡节点，而AMCO算法会在该类节点能量耗尽之前进行实时判断，并将其视为不可达节点进行提前筛选与剔除，提高了网络的总体电量．NJNP算法与FCFS算法会被此类传感器节点干扰，导致MC产生额外的充电能耗与移动能耗，同时增加了无效的充电任务时间，使得更多传感器节点失效死亡．10.13245/j.hust.210217.F003图3各策略的性能对比研究结果表明：该充电规划策略与主流算法相比，其充电效率可提升2.4%，网络中节点死亡率可降低36%，因此本研究所提策略能够在提高充电效率的同时进一步降低传感器的死亡率，从而延长WRSN的工作寿命．10.13245/j.hust.210217.F004