多节点部分充电模型下的充电调度优化_刘景祥.pdf

2023，59（6）网络、通信与安全无线传感器网络广泛应用于不同工业场景中，例如环境监测、丛林火灾监测、军事侦查等1-3。由于传感器通常由锂电池供能且电池中存储的能量有限，持续的数据传感不可避免会导致传感器能量耗尽，成为网络性能的瓶颈。随着无线充电技术的不断发展，将无线充电技术嵌入到传感器网络中，通过部署一辆或多辆移动充电车给能量临界的传感器进行无线能量传输4，为现有的无线传感器网络应用提供有效的无线电力解决方案。近年来移动充电车对传感器的充电调度引起了广泛的关注。大部分文献研究采用完全充电模型5-8，即移动充电车在网络中当前充电位置对充电范围内单个或多个传感器都充满电后再移动到下一个充电位置。如图1所示，由于无线能量传输过程存在能量衰减4，相同能量需求下传感器v2比v1花费更多时间充满电。当移动充电车移动到传感器v3处充电时，由于v1已被充满电而不再充电。为了提升充电效率并缩短传感器的死亡时间，最新的文献研究采用部分充电模型9-11，即移动充电车无需一次性给充电范围内的传感器都充满电，而经过多次部分充电直到每个传感器充满电。如图2所示，移动充电车先给传感器v1和v2同时充电，此时v1和v2充部分电。然后移动到v3位置给v2和v3充满电，此时v2第二次充电。最终回到v1位置给v1充满电，此时v1第二次充电。多节点部分充电模型下的充电调度优化刘景祥，徐文政四川大学 计算机学院，成都 610065摘要：在无线可充电传感器网络中，针对移动充电车采用多节点部分充电模型在充电调度过程中往复行驶，导致充电时间增加的问题进行了研究。提出一种新颖的多节点部分充电模型，从全局优化移动充电车在每个充电位置的充电时间，保证每个能量临界的传感器被充满电。同时提出AlgMinTime算法进行路径规划，确定移动充电车的充电环路以及对应位置的充电时间，使得环路上总充电调度时间最小化。最终通过仿真实验评估所提出算法的性能。实验结果表明，所提算法的充电调度平均环路时间相较于SOTA算法缩短9.8%。关键词：无线传感器网络；多节点充电；部分充电；充电调度；路径规划文献标志码：A中图分类号：TP393doi：10.3778/j.issn.1002-8331.2111-0410Optimization of Charging Scheduling Under Multi-Node Partial Charging ModelLIU Jingxiang,XU WenzhengSchool of Computer Science,Sichuan University,Chengdu 610065,ChinaAbstract：In the wireless rechargeable sensor network,the mobile charger adopts the multi-node partial charging modelto reciprocate during the charging scheduling process,which leads to the increase of the charging duration.For this rea-son,this paper proposes a novel multi-node partial charging model,which globally optimizes the charging duration of thecharger at each charging position,ensuring that each energy-critical sensor is fully charged.Meanwhile,the AlgMinTimealgorithm is designed for path planning to determine the charging tour of the charger and the charging duration corre-sponding to the charging position,such that the total charging scheduling duration in the tour is minimized.Finally,theperformance of the proposed algorithm is evaluated through simulation experiments.Experimental results show that theaverage tour duration of charging scheduling by the proposed algorithm is 9.8%shorter than that of the SOTA algorithm.Key words：wireless sensor network;multi-node charging;partial charging;charging scheduling;path planning基金项目：四川省重点研发计划（2020YFG0089，22ZDYF3599，2020YFG0304）；四川省科技厅项目（2017GZDZX0003）。作者简介：刘景祥（1996），男，硕士研究生，CCF学生会员，研究方向为无线传感器网络，E-mail：；徐文政（1985），男，博士，副研究员，研究方向为物联网、近似算法。收稿日期：2021-11-22修回日期：2022-02-18文章编号：1002-8331（2023）06-0251-07Computer Engineering and Applications计算机工程与应用251Computer Engineering and Applications计算机工程与应用2023，59（6）在实际应用中，移动充电车采用部分充电模型按照单位充电能量或单位充电时间对传感器进行充电，这会导致移动充电车在充电调度过程中频繁往复行驶，使得充电调度时间增加。为了提高充电效率，本文提出一种新颖的多节点部分充电模型，其从全局优化确定移动充电车的充电位置和在每个充电位置的充电时间，确保每个充电位置只停留一次，继而提出有效的算法AlgMinTime为移动充电车规划充电环路，使得充电调度过程总充电时间最小化。仿真实验结果表明本文所提算法的性能优于SOTA算法。1系统模型1.1网络模型假设二维空间中部署一个大规模的无线可充电传感器网络Gs=(Vs,Es)，该网络包含ns个位置固定的传感器Vs=v1,v2,vns，其中vi=(xi,yi)。每个传感器的坐标是已知的，对于任意两个传感器在彼此的通信范围内，则两个传感器之间存在边(vi,vj)Es。此外，网络中包含一个收集传感器数据的基站，每个传感器的传感数据沿着给定的路由直接或通过多跳中继发送到基站，例如沿着具有最小能量消耗的路由12。每个传感器viVs消耗其能量用于数据传感、接收和转发。令bi(t)表示时刻t下传感器vi的数据传感速率，根据网络中的数据路由，计算得到传感器vi的数据接收速率bRxi(t)和数据转发速率bTxi(t)，其中bTxi(t)=bi(t)+bRxi(t)。传感器采用真实能量消耗模型13，获得传感器的能量消耗速率i(t)。1.2充电模型假设每个传感器viVs由有限容量Bi的可充电电池供电。令REi(t)表示时刻t下传感器vi的剩余能量，则剩余存活时间li(t)=REi(t)/i(t)。当li(t)低于给定的阈值lc时，传感器发送充电请求REQi=到基站，其中Bi-REi(t)表示传感器vi的能量需求。并将网络中剩余存活时间li(t)lc的传感器纳入待充电传感器集合Vc中，即Vc=vi|viVs,li(t)lc，n=|Vc。为了维持传感器网络Gs的长期运转，假设在基站位置处部署一辆移动充电车，基站接收到充电请求后，将派遣该移动充电车对Vc中的传感器进行无线充电，并为其规划充电路径。理想情况下，移动充电车可以停留在网络中任意位置为范围内的传感器充电，无限的候选充电位置使得充电车的路径规划不可解。因此本文考虑将每个待充电传感器viVc所在位置si作为候选充电位置，则候选充电位置集合S可以表示为S=s1,s2,sn。本文提出一种新颖的多节点部分充电模型，当移动充电车停留在网络中的候选充电位置sjS时，其最大能量辐射范围内的传感器集合N(sj)可以同时被充电，其中N(sj)=vi|viVc,d(vi,sj)。在能量传输过程中，能量传输效率随着传输距离d(vi,sj)增加而衰减，传感器的能量接收功率Pr(vi,sj)如下表示：Pr(vi,sj)=|(d(vi,sj)+)2Pt,d(vi,sj)0,d(vi,sj)（1）式中，和为两个常量，Pt为输出功率。同时，移动充电车无需一次性给充电范围所有传感器充满电，而经过多次部分充电直到每个传感器都充满电。不同于最新的多节点部分充电模型10-11，充电车可能在同一个充电位置停留多次，本文提出全局优化确定移动充电车的v1v2v3移动充电车传感器充电路径充电范围v1v2v3（a）移动充电车在传感器v1处对v1和v2充满电（b）移动充电车在传感器v3处对v3充满电图1完全充电模型Fig.1Full charging model移动充电车传感器充电路径充电范围v1v2v3v1v2v3v1v2v3（a）移动充电车在传感器v1处给v1和v2充电（b）移动充电车在传感器v3处给v2和v3充满电（c）移动充电车回到传感器v1处给v1充满电图2部分充电模型Fig.2Partial charging model2522023，59（6）充电位置以及每个充电位置对应的充电时间j，在保证每个待充电传感器viVc都充满电的情况下，每个充电位置只会停留一次，避免移动充电车在网络中往复行驶，以有效提升网络的充电效率。如图3所示，充电车无需返回传感器v1位置进行充电，从而缩短充电调度时间。相关符号描述如表1所示。1.3问题定义在大规模传感器网络中，移动充电车在网络中的充电调度时间直接影响着网络性能。若充电调度时间越长，则会导致网络中大量传感器能量耗尽而无法工作。反之，若充电调度时间越短，由于越少传感器能量耗尽，网络性能则越好。假设移动充电车的充电环路表示为C=，其中移动充电车从基站r出发，移动到s1位置充电时长为1，然后移动到s2位置充电时长为2，最终回到基站r补充能量。如果每个待充电传感器都充满电，则环路C是可行的。即满足约束条件如下：j=1mPr(vi,sj)jBi-REi,viVc（2）环路C的充电调度时间包含两个部分：充电位置的充电时间和充电位置之间的行驶时间。本文首先将致力于研究充电时间最小化问题，通过全局计算环路C上每个充电位置分配的最小充电时间，从而确定移动充电车的充电位置以及对应的充电时间，然后移动充电车在充电位置之间将沿着最短充电路径行驶，从而最小化环路C上所需的总充电调度时间。2AlgMinTime算法2.1问题分析已知待充电传感器集合Vc和候选充电位置集合S，其中n=|Vc=|S。针对每个候选充电位置sjS分配充电时间j，使得总充电时间j=1nj最小化。该最小化问题需满足以下约束：（1）每个待充电传感器viVc从不同位置sjN(vi)进行部分充电，收到总能量不低于其能量需求Bi-REi。（2）移动充电车不在候选充电位置sjS停留时，对应充电时间j=0；反之，由于最大能量辐射范围内的传感器集合N(sj)可以被同时充电，则在该位置的最大充电时间是将范围内每个传感器viN(sj)都充满电，即maxj=maxviN(sj)Bi-REiPr(vi,sj)。因此，充电时间最小化问题定义如下：minj=1nj（3）约束条件：sjN(vi)Pr(vi,sj)jBi-REi,viVc（4）0jmaxj,sjS（5）可以发现，该问题归约为线性规划问题，其中式（3）表示决策变量构成的线性目标函数，式（4）