(19)中华 人民共和国 国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202111174665.0 (22)申请日 2021.10.09 (71)申请人 昆明理工大 学 地址 650093 云南省昆明市五华区学府路 253号 (72)发明人 冯勇　王艺均　李英娜　张晶　 (74)专利代理 机构 昆明明润知识产权代理事务 所(普通合伙) 53215 代理人 马海红 (51)Int.Cl. G06F 30/27(2020.01) G06N 3/04(2006.01) G06N 3/08(2006.01) G06Q 10/06(2012.01) G06Q 50/06(2012.01)G06F 111/06(2020.01) (54)发明名称 一种基于图神经网络和强化学习的WRSN充 电调度方法 (57)摘要 本发明涉及一种基于图神经网络和强化学 习的WRSN充电调度方法， 属于利用无线充电技术 延长无线传感器网络生存周期的研究领域。 大规 模WRSN中单个可移动充电器(MC)显然不能应对 繁重的充电任务， 而常规的多MC充电调度方案中 MCs能量利用率低下且各个MC的充电负载不均 衡， 制约了整个网络的充电效率。 本发明将WRSN 中的多MC充电调度问题建模为多目标优化问题， 并将传感器节点分配问题建模为多旅行商问题 (MTSP)。 提出了一种基于图神经网络和强化学习 的充电调度方法(GRCS)， 建立了多MC协同的充电 模型， 并采用强化学习训练模型从而为充电调度 问题生成近似最优解。 本发明在提高MCs能量利 用率的同时均衡各个MC的充电负载， 在延长网络 生存时间的同时显著提高了充电效率。 权利要求书3页 说明书8页 附图4页 CN 113887138 A 2022.01.04 CN 113887138 A 1.一种基于图神经网络和强化学习的WRSN充电调度方法， 其特 征在于， 包括以下步骤： Step1： 构建无线可充电传感器网络模型， 整个移动能量补给系统部署在二维平面区域 内， 不考虑障碍物的影响， 由三类成员组成： 一个基站BS、 n个传感器节点和m个移动充电设 备MC， 其中传感器节点和 基站固定不动且位置已知， 基站作为最终的数据采集器不受能量 限制， MC和传感器节点电池容 量有限， 其自身可通过BS快速更 换电池； 在WRSN中的MC规格相同初始时位于BS， 速度为vm/s， 可在WRSN区域内自由移动， 能耗为 qmJ/m， 通过远距离通信直接受基站BS调度， 并可通过GPS定位技术实时获取自身位置， MC只 有在到达某个节点位置时为其单独补充能量， 充电功率为qc/w， MC携带电池的最大容量为 EmJ； Step2： 在延长网络生存时间的前提下以最大化充电效率和均衡MC之间的充电负载为 目标将多M C充电调度建模为多目标优化问题； Step3： 基于图神经网络和强化学习设计一种称为GRCS的高效移动能量补充框架， 提出 最短充电回路生成算法， 求解Step2中的多目标优化 问题， 其工作流程为： 首先对WRSN中所 有传感器节点进行划分， 每个MC负责相应的节点， 将传感器节点的划分过程抽象为多旅行 商问题MTSP， 求得m条最短哈密顿回路， 每个MC负责一条充电回路， 回路中的节点能量低于 设定阈值时发送充电请求， 在每个充电周期中MC严格按照短哈密顿回路中的顺序删除能量 充足的节 点， 为待充电节点生 成最优充电序列， MC按照最优充电序列为节点补 充能量， 如此 循环工作， 以保障网络的持续 运行。 2.根据权利要求1所述的基于图神经网络和强化学习的WRSN充电调度方法， 其特征在 于： 在充电过程MC的能量消耗包括三个部分： (1)有效能量， 即传感器节点获取到的能量； (2)机械能， 即MC移动过程的能量损耗； 以及(3)无线传输过程的能量损耗， 所述Step2中充 电效率为有效能量与总能量之比， 充电调度方法可用M C充电效率进行评估。 3.根据权利要求1所述的基于图神经网络和强化学习的WRSN充电调度方法， 其特征在 于： Step2中M C的充电负载定义 为每个MC负责充电的传感器节点的数量。 4.根据权利要求1所述的基于图神经网络和强化学习的WRSN充电调度方法， 其特征在 于： 所述Step3中， GRCS的工作过程具体为： 首先将WRSN运行时间划分为多个连续的充电周期， 节点实时检查自身当前剩余能量 当 低于阈值Eth时向BS发送充电请求， 请求消息表示为 其中id 是传感器的唯一标识， 是当前剩余能量， r为节点能耗 率， ts是当前时间戳， 对于传感器 节点i， 其能耗pi(t)、 当前剩余能量 阳能耗率r计算如下： 其中t表示当前充电回合， ρ 是节点接收1kbps数据的能耗， fi， j是节点xi到xj的数据流， 1 ≤j≤n+1， 当j＝n+1时表示xi到BS的数据流， ci， j表示传输数据时的功耗， α 是一个比例因子 用于调整ri对实时能耗的敏感程度， Δ用于将时间划分为 连续的周期， [ri]是上一充电周期权　利　要　求　书 1/3 页 2 CN 113887138 A 2的能耗率， 请求消息通过多跳无线传输被传送到基站， 在每个充电周期开始时MCs接受BS调 度为节点补充能量； 对于整个WRSN的充电调度， 首先为m个MC划分充电任务， 以BS为起点为传感器集合N＝ {s1， s2，…sn}划分m个最短哈密顿回路， 即充电回路， 将构建充电回路的过程抽象为多旅行 商问题MTSP， 每个MC负责一条充电回路中的传感器节点， 在每条充电回路中按顺序为节点 重新编号， 一条充电回路可以表示为ChargingCircuit1＝BS， n1， n2，…， n8， 其中n1， n2，…， n8 表示按照最短哈密顿回路中顺序重新标号的传感器节点， 每 个MC负责一条充电回路； 上一充电周期内节点发送的充电请求Q存储在充电服务池P中， 在当前周期开始前每个 MC根据服务池中的请求信息为自身规划充电序列， MC从BS出发按照充电回路中的节 点顺序 构建最优充电序列， 并依次访问待 充电节点， 如此循环工作。 5.根据权利要求1所述的基于图神经网络和强化学习的WRSN充电调度方法， 其特征在 于： 所述Step3中， 最优充电序列定义为： MC从BS出发遍历所有待充电节点至少一次后并返 回BS的最短路径， 从最短充电回路中删除任意x个节 点得到具有N ‑x个节点组成的最短充电 路径， 即最短充电回路的子路径也是最短充电回路， 0 ≤x＜n。 6.根据权利要求1所述的基于图神经网络和强化学习的WRSN充电调度方法， 其特征在 于： 所述Step3中， 最短充电回路生成算法的具体步骤为： Step6.1： 将为MC分配传感器节点的过程定义在图G中， 其定义为节点和边的集合， 传感 器为节点， 传感器节点之间的路径为 边； Step6.2： 使用图神经网络对Step6.1的过程进行优化， 通过图嵌入将图中高维稠密矩 阵映射为低维稠 密向量， 采用组合消息传递神经网络CMPNN框架， 通过相 邻连接节 点的消息 传递为每个传感器节点i， i∈{1， 2， …n}计算p维特征嵌入fi， 在基于CMP NN框架的图神经 网 络中， 节点嵌入的更新过程如下： fit+1为更新的节点嵌入， 其中relu为线性整流函数relu(z)＝max{0， z}应用于其输入元 素， N(i)表 示节点i所有的相邻节 点， θe为所有边的共享参数， θ1， θ2为所有节 点的共享参数， fit， 为上一步中节点 i， j的特征嵌入； Step6.3： 分布式策略网络的设计分为两个阶段： 在第一个阶段， 每个MC通过使用全局 信息和图中的节点嵌入， 独立构建自己的嵌入， 第二个阶段， 每个节点根据全局嵌入为自身 分配一个M C； 除BS以外的所有节点只能由一个MC访问， 而BS则由所有MC访问， 采用注意力机制计算 节点对于编号为a， a∈{1， 2， …， m}的MC， 即MCa的重要性， 注意力机制中三个固定参数qa， kai， vai计算如下： 其中dk和dv为key和value的维度， θak和θav为神经网络参数， 用于将嵌入映射到dk维， fc 为上下文嵌入， fip是节点i的p维特征嵌入， p为节点嵌入的维度， 然后计算MCa关联的query权　利　要　求　书 2/3 页 3 CN 113887138 A 3