基于注意力机制和策略梯度的多MC充电调度*

王艺均，冯 勇，李英娜，付晓东，钱 谦

(昆明理工大学云南省计算机技术应用重点实验室，云南 昆明 650500)

无线传感器网络(WSN)被广泛应用于物联网的各个场景[1-2]，但由于传感器节点采用电池供电，有限的电池容量使传感器无法长时间有效工作，阻碍了WSN的大规模部署。无线能量传输[3]的迅速发展为解决WSN中节点的能量限制问题提供了新思路，使得无线可充电传感器网络(WRSN)[4]应运而生。其中配备有谐振线圈的可移动充电装置(Mobile Charger，MC)用于将能量无线传输到传感器节点，使WSN的生存时间不再受限于传感器的电池容量。理想情况下，WRSN的工作时间可以达到无限长。而在WRSN中如何高效地调度MC为节点补充能量是当前的最大挑战，受到了国内外学者的广泛研究。

为保证传感器节点长期有效地工作，要求充电方案尽可能地提高MC充电效率和降低节点失效率。在充电过程中MC的能量消耗包括三个部分:①有效能量，即为传感器节点补充的能量；②机械能，即MC移动过程的能量损耗；以及③无线传输过程的能量损耗[5]。充电效率定义为有效能量与总能量之比。其中如何减少MC移动过程的能量损耗是提高整体充电效率的关键。当传感器节点未及时得到能量补充时会因缺电而饥饿失效，从而可能造成传感器网络数据链路断开等严重后果。因此，为了提高充电效率和降低节点失效率，需要合理调度MC为整个传感器网络补充能量。对于大规模无线传感器网络，单个MC显然不能有效应对大量的充电需求，而多个MC的调度问题进一步涉及MCs之间的协调[6]。

目前的WRSN充电调度方案可以分为周期性充电策略和按需充电策略。周期性充电策略需要求出一条覆盖所有传感器节点的充电回路，MCs沿着预定轨迹周期性完成充电任务。文献[7]通过求解基于节点能耗的旅行商问题(Traveling Salesman Problems，TSP)来实现MC充电效率最大化。文献[8]在考虑MC能量有限的情况下建立以最小化MCs能耗率为优化目标的优化模型，采用混沌粒子群算法获得MCs的充电路径和充电策略。文献[9]联合考虑了充电轨迹和基站定位问题，解决了MCs充电周期与节点生存寿命不匹配的难题。但周期性充电策略无法应对节点能耗波动较大的场景，仍然存在一定局限性。

按需充电策略中传感器节点根据自身剩余能量发送充电请求，MC根据节点的实时需求执行充电任务。文献[10]考虑充电请求的影响设计了双重警告阈值来确定充电请求的调度优先级，并设计了双重抢占机制处理网络的动态特性。文献[11]综合考虑节点充电过程中的时间和空间因素，使用改进的引力搜索算法按需规划节点被服务的顺序。文献[12]提出一种基于非均匀分簇的实时充电算法，通过研究簇内节点的能量状态和充电截止时间来决定簇头的选举和轮换。文献[13]将多MCs的协调问题表述为整数线性规划，并设计了一种分解方法来求解，以最小化计算时间。为了最小化MC数量，文献[14]提出了叫做shuttling的新概念，在理论上实现了MC个数最小化。文献[15]根据节点剩余生存时间将其分组，保证每次调度只对剩余能量较低的节点进行充电。按需充电模式能更好地适应节点能耗动态变化的环境，文献[16]考虑每个MC同时向多个节点传输能量以减少充电延迟。然而现有按需充电模式下多MC的充电调度工作并没有从整体上考虑充电路径的优化，这可能带来MCs不必要移动，从而增加充电成本。

通过对现有工作的分析，可知周期性充电模式不能很好地适应节点能耗的动态特性，按需模式没有充分考虑充电路径的优化和充电策略的公平性。现有多MC充电规划研究大多仅考虑单一性能指标，并未考虑到MCs承担充电任务的均衡性，使MCs的充电任务均衡一方面可以提高MCs整体充电效率，减少MC数量；另一方面可以避免单个MC负载较重而造成节点饥饿失效的问题，提升整个网络的生存时间。并且WRSN中的充电调度被证明是NP-hard问题，对于NP-hard问题没有可用于监督学习的最优标签。目前已有的研究工作大多基于传统的优化方法，如枚举策略、近似算法和启发式算法等。传统方法对于NP-hard问题一般不容易得到满足实际需求的最优方案，很难适应复杂多变的环境，甚至把问题过于简单化。因此充电调度工作仍需进一步优化。

对于以上种种限制，本文基于前人研究，融合周期性充电和按需充电模式的优点，在多MC充电调度的基础上联合考虑均衡MCs充电负载以及最大化MCs充电效率的问题，并引入注意力机制和强化学习中的策略梯度对充电调度问题进行求解。

本文的主要贡献如下:(1)联合考虑WRSN充电规划中MCs充电负载均衡化和MCs充电效率最大化，提出一种新的充电调度方法APCS。(2)引入注意力机制和策略梯度对充电调度问题进行求解，通过奖励反馈来评估一组充电序列的质量，为动态WRSN提供即时的全局充电方案。(3)建立仿真环境并与现有充电方案进行对比，证明了本文方案的有效性。

1 网络模型与问题定义

本节首先对WRSN网络模型和充电模型展开介绍，然后提出MCs按需充电调度问题。

1.1 网络模型

给定一个WRSN模型如图1所示，整个移动能量补给系统部署在二维平面区域内，不考虑障碍物的影响，由三类成员组成:一个基站(BS)、n个传感器节点和m个移动充电设备(MC)。其中传感器节点和基站固定不动且位置已知，基站作为最终的数据采集器不受能量限制，MCs和传感器节点电池容量有限，MC是一种具有自主移动、计算和通信能力的设备，例如智能小车或移动机器人，并带有无线能量传输装置为传感器节点补充能量，其自身可通过BS快速更换电池[17]。

图1 WRSN网络模型

以下根据三类成员描述模型假设和相关定义，表1中列出了其余部分使用的主要符号。

表1 主要参数符号

①基站设定:本文设定只有一个基站，可根据实际情况位于网络中任意合适的位置，BS负责数据的收集存储并持续为MCs补充能量。

②传感器节点设定:n个传感器节点表示为集合N＝{s1，s2，…，sn}，其根据数据采集频率和数据传输速率预测其自身剩余能量，对于每个节点si(1≤i≤n)，其能量主要用于数据的发送和接收，根据文献[18]我们采用如下能耗模型:

式中:fi，j(1≤j≤n+1)是节点si到sj的数据流，当j＝n+1时表示si到BS的数据流，ci，j表示传输数据时的功耗。

式中:di，j为节点si到sj的距离，β1表示无距离能耗系数，γ为信号衰减系数，ρ是节点接收1 kbyte/s数据的能耗，因此节点si接收数据的总功耗为:

si向其他节点发送数据的总功耗为:

因此在t时刻节点的剩余能量计算如下:

并且传感器节点的能量需求为:

③MCs设定:在WRSN区域中MCs的规格相同，并以Vm的速度移动，能耗为Em，通过远距离通信(如4G/5G通信技术)直接受基站BS调度。并可通过GPS等定位技术实时获取自身位置，MC只有在到达某个节点位置时为其单独补充能量，充电功率为qc，MC携带电池的最大容量为Em，在t时刻MCs剩余能量的计算公式为:

式中:Li，i+1为MC从当前节点移动到下一节点的距离，当MC剩余能量小于下一待充电节点能量需求与自身行驶消耗能量之和时停止为节点补充能量，从当前位置返回基站充电，与节点充电过程相比MC自身补充能量时间忽略不计。

1.2 问题定义

本文将WRSN运行时间划分为多个连续的工作周期，节点充满电后的生命周期为几周或几个月，而网络可以在几天内完成一轮电量补充。当传感器能量降至设定阈值以下时主动向基站发送充电请求消息，请求消息通过多跳方式传送到基站，MCs接受BS调度为节点补充能量。

由于各个传感器节点能耗率不同，要使MCs总移动距离最短、充电效率最高，MCs需要协作完成充电任务。首先对WRSN中的传感器节点进行合理划分，每个MC负责不同的节点。本文将充电任务的分配过程抽象为多旅行商问题(MTSP)，MCs和传感器节点分别对应于旅行商和城市。我们提出一种融合注意力机制和策略梯度的充电调度算法。旨在WRSN中传感器节点满足位置和充电器能量约束的基础上，求解最大化充电效率问题。

如前所述，整个充电调度的目标是最大化充电效率和最小化节点失效率。本文需要解决的问题如下:①为MCs划分合理的充电路径，尽可能使充电效率最高。②均衡每个MC的充电负载，最小化MTSP中的最长子路径，高效调度MC，减少节点失效率。

2 多MC按需充电策略

在本文设置的传感器网络中有m个MC共同协作完成充电任务，在初始阶段MCs位于BS，当服务池中存在待充电节点时MC将为其规划充电路径。每个MC采用点对点充电模式，即同时只能为一个传感器节点充电且每个传感器节点在一轮充电调度中仅被充电一次。本节对多MC按需充电调度策略进行分步骤详细介绍。

2.1 构建充电回路

对于整个WRSN的充电调度，首先构建充电回路为MCs划分充电任务，使得MCs能够覆盖所有传感器。以BS为起点为传感器节点集合N＝{s1，s2，…sn}划分m个最短哈密顿回路，每个MC负责一条回路中的传感器节点，在每条充电回路中按顺序为节点重新编号。

图2显示了WRSN其中一条充电回路，其可以表示为Charging Circuit1＝BS，n1，n2，…，n8每个MC负责一条充电回路。构建这样m条充电回路的问题为多旅行商问题(MTSP)。

图2 传感器划分-以一个MC为例

对于编号为k的MC对应的充电规划来说，在t＝0时刻MCk从BS出发，遍历一系列传感器节点，形成集合，其中，nk为MCk一轮充电的传感器个数。在充电完成后MC沿充电路径回到BS为自身补充能量.设Rk为MCk对应的一次充电回路，ski为该充电回路中的传感器节点，均表示为基站BS。

MCk在充电回路k中的总移动距离为:

假设MCk到达充电回路中的传感器节点ski后立即为其补充能量至Emax。则MCk为节点ski的充电时间为:

则MCk在充电回路中执行一轮充电任务所花费的时间为:

如图3所示，在每个充电周期中各个MC服务的充电回路不同，完成一轮充电任务的时间也不同。最先完成充电任务的MC与最后完成的时间差为:

图3 多MC充电调度

为了最大化MCs能量利用率的同时均衡MC之间的充电负载，构建充电回路的优化目标为:

式中:目标值f1表示MCk在一次充电回合中移动能量损耗与总能量消耗之比，即充电效率。f2表示MCs执行充电任务花费的时间的方差，用来衡量MC之间充电负载的均衡性。

2.2 充电序列规划

上一充电周期内节点发送的充电请求Q存储在充电服务池P中，在当前周期开始前每个MC根据服务池中的请求信息为自身规划充电序列，MC从BS出发按照充电回路中的节点顺序依次访问待充电节点。

定义1最优充电序列为MC从BS出发遍历所有待充电节点至少一次后并返回BS的最短路径。

引理1根据文献[19]的证明，从最短充电回路中删除任意n(0≤n＜N)个节点得到具有N-n个节点组成的最短充电路径，即最短充电回路的子路径也是最短充电回路。

在一轮充电回合中以图4为例，删除不需要充电的节点重新构造最优充电序列。MC按顺序为待充电节点{n1，n5，n6，n8}进行能量补充。

图4 充电序列重新规划-以一个MC为例

3 基于注意力机制和策略梯度的求解框架

本文在研究WRSN中多MC协同充电调度的问题中，构建一种基于注意力机制与分布式策略网络组成的体系结构，从而为MCs的充电调度生成近似最优的解决方案，并引入策略梯度训练模型。首先将为MCs分配传感器节点的过程定义在图G中，策略首先总结图G的状态，然后将每个传感器节点分配到指定的MC，通过这种方式将多MC充电调度问题转化为m个单MC调度问题，为每个MC构建充电回路。首先利用图神经网络嵌入图G，然后设计一组分布式策略网络进行传感器节点到MC的分配。本节对求解框架展开详细介绍。

3.1 图嵌入

首先将图定义为节点和边的集合，为了解决图数据难以高效输入机器学习算法的问题，通过图嵌入将图中高维稠密矩阵映射为低维稠密向量。根据文献[20]我们采用组合消息传递神经网络(Combined Message Passing Neural Network，CMPNN)框架，通过相邻连接节点的消息传递为每个传感器节点u计算p维特征嵌入fu。在基于CMPNN框架的图神经网络中，节点嵌入的更新过程如下:

式中:relu(z)＝max{0，z}应用于其输入元素，N(u)表示节点u所有的相邻节点，θe为所有边的共享参数，θ1，θ2为所有节点的共享参数。

3.2 注意力机制

结合注意力机制[21]的分布式策略网络能够分析嵌入的图，之后由策略梯度做出为MC分配不同传感器节点的决策。策略网络的设计分为两个阶段，第一个阶段中每个MC使用全局信息和图中节点嵌入构造自身嵌入。第二个阶段，采用注意力机制进行MC嵌入和节点的分配，每个节点使用全局嵌入为自身分配一个MC，并使用策略梯度对分配模型进行训练。

图5 注意力机制模型

式中dk和dv为key和value的维度，然后计算MCa关联的query与所有节点的匹配程度:

对于注意力权重wai∈[0，1]:

由权重wai构造MC嵌入:

对于将MC分配给节点i的策略过程，我们首先计算每个MC对于节点i的相关度。对于MCa:

式中:d′k是新keys的维度；θak′和θaq′为神经网络参数，用于将嵌入映射到d′k维。在求出u′ai后，使用tanh将结果限制在[-C，C](C＝10)，从而求出impai。

每个节点都必须分配到一个MC，其对该节点的相关度决定哪个MC访问该节点，通过Softmax函数对相关度进行归一化，得到MC访问某个节点的概率。

据统计，核电站人因失误类型可分为5类[13]：1) 未发现报警或征兆；2) 对事故征兆或时间判断失误；3) 操作失误；4) 工作人员交流差错；5) 组织管理不当。其中第1类失误与操作界面设计的优劣有着直接的关系，故本文从第1类失误类型出发,将其作为出错因子，建立基于报警发现的评价体系。

算法1为传感器节点到MC的分配过程，其中path是为MC分配的充电回路，f是节点特征，m和n分别为传感器节点和MC数量。在开始时保存节点分配的集合D为空，即未给任何节点分配MC，执行算法1将为D赋值，通过OR-tools计算最长子路径的长度作为奖励值。

算法1 节点分配

3.3 策略梯度

本文将为MCs分配传感器节点的过程抽象为Markov过程，具体而言，在求解时通过参数为θ的网络模型选择下一个加入充电回路的传感器节点，最终生成充电回路path。为了评估模型中的参数θ，采用策略梯度进行训练使得预期奖励最大化。

分布式策略网络将根据已分配路径path做出决策，在分配过程中传感器节点具有以下两种状态:

状态1:传感器节点已被分配给MC。

状态2:传感器节点尚未被分配。

例如，当前对应于MCa的策略网络，在一个节点被分配到MCa时，该节点输入到策略网络的特征为(1，0)；若当前节点被分配给其他MC，则特征为(0，1)；节点未被分配时特征为(0，0)。

式中:θ*表示最优策略，D是训练集；λ为分配给MCa的节点；Rλ是分配λ后获得的奖励；πθ是赋值在θ上的分布:

为了达成该训练目标，本文采用策略梯度算法对参数θ进行训练，求得最优策略θ*，即在完成节点到MC分配的同时，最小化MC的最长充电子回路，在完成传感器节点到MC分配过程的同时，使得每个MC的充电负载尽可能达到均衡。训练过程中使用OR-tools快速计算一组较小规模的TSP，并返回所有MC的最大行程长度的负数作为任务的奖励。

在完成节点到MC的分配后，每个MC负责相应的传感器节点，此时求解m条充电回路的问题被简化为若干个与MC相关的TSP。本文采用Google的优化工具OR-tools求解与每个MC相关的TSP。在完成m条充电回路的划分后按照2.2节的充电序列规划方法为节点进行按需能量补充。

算法2 策略梯度

4 仿真与性能分析

仿真实验使用Python语言搭配Pytorch框架模拟WRSN的能量补充过程，并与不同的充电方案进行对比验证APCS的性能。我们根据对实际应用场景的考虑和大量现有文献的参考，相关实验默认参数的设置如表2所示。在实际充电调度中，WRSN中需要MC的数量受多种因素影响，包括传感器节点数量、传感器节点能耗率、MC电池容量和MC充电效率等多种因素。我们在实验中设定MC的数量m＝5，传感器节点数量n＝50，75，100，125，150，175，200，来模拟小规模传感器网络和大规模传感器网络中的充电调度，并在(0，1)2的区域内随机生成n个传感器节点的坐标作为训练数据。以此来验证所提方案的有效性。

表2 实验默认参数

对比算法设置为遗传算法(Genetic Algorithm，GA)、贪婪算法(Greedy Algorithm，GA)、典型的单MC按需充电方案Nearest-Job-Next with Preemption(NJNP)[22]和多MC方案Distance and Energy-Oriented Charging Scheduling(DECS)[23]。

遗传算法:采用遗传算法求解多MC充电回路划分过程。

NJNP:MC选择空间上最近的传感器节点作为下一个要充电的传感器。

DECS:综合考虑节点剩余能量和节点与MC之间距离，在协作模式下为MCs规划最短充电路径。

4.1 充电子回路长度

评估各个MC充电负载是否均衡的一个指标为最长充电子回路的长度。为了评估该指标，我们在不同的学习率下对模型进行27 000次迭代，进而验证学习率对APCS算法的影响，实验结果如图6所示。

从图6可以看出，学习率为5e-5时取得了较快的收敛速度，但结果并未达到最佳。学习率为1e-5时APCS在10 000次迭代后开始收敛，取得了更好的效果。最长充电子回路越短，说明WRSN中各个充电子回路长度越均衡，每个充电周期内ΔTk越小，即各个MC之间充电负载越均衡。

图6 最长充电子回路

4.2 对比仿真

节点失效率定义为能量耗尽的失效节点数与所有请求充电的节点数之比，节点失效率是评价充电策略性能的重要指标之一，失效节点比率越小，说明充电策略效率越高，对待充电节点的响应越公平。

分析图7(a)可得，随着网络规模的增加，五种充电策略的节点失效率都呈现增大趋势。这是由于请求节点数量的增加，MC对待充电节点的响应变慢从而导致来不及得到能量补充的节点饥饿失效。但本文提出的充电方案APCS中的节点失效率始终低于其他四种方案，在节点数量为200时，APCS的结果比GA、Greedy、NJNP和DECS充电方案分别降低了33.3%、70%、61.5%、39.3%。

如图7(b)所示，实验表明在Eth为0.6-0.7Es时节点失效率最低，在超过0.7Es时失效率上升，这是由于Eth过高导致请求充电的节点数量大大增加，MC无法及时响应所有待充电节点。在Eth为0.3-0.8Es之间的APCS都取得了比其他方法更好的效果。

图7 不同情况下的节点失效率

每个MC的充电效率定义为传感器节点获得的能量与总能量之比。提高充电效率的一种有效途径是减少能量补充过程中消耗的机械能，即MC移动能耗。如图8(a)所示，随着节点数量的增加，五种充电方法的MC平均移动距离都呈现增大趋势，但APCS始终优于其余方法。从图8(b)可以看出，在阈值Eth的变化下APCS同样取得了比其余方法更好的结果。在Eth大于0.7Es时MC移动距离增加是由于阈值过大请求充电节点数量太多导致MC更频繁的移动。

图8 不同情况下的MC平均移动距离

5 结论

本文针对大规模WRSN中单个MC服务能力不足和多MC调度中充电负载不均衡的问题，研究了多MC充电调度优化问题。提出了融合注意力机制和强化学习中策略梯度的充电调度方案APCS。首先APCS以提高充电效率、减少节点失效率为目标，采用注意力机制和策略梯度完成传感器节点到MC的分配，每个MC负责相应的传感器节点，再通过OR-tools求解与每个MC相关的TSP，为其规划充电路径。在仿真实验中，我们通过分析最长充电子回路的长度、节点失效率和MC平均移动距离来评估所提方法的性能。大量仿真结果表明，APCS能够显著降低节点失效比率并提高充电效率。