基于时空协作的多移动充电器充电路径规划的研究*

尹 玲，谢志军

(宁波大学信息科学与工程学院，浙江 宁波 315211)

1 引言

无线充电是指利用磁共振耦合原理进行充电。移动充电器MC(Mobile Charger)配有高容量电池和发射线圈，节点则配备接收线圈，MC移动到节点附近，将自身电池输出的直流电DC(Direct Current)通过DC/AC转换器转换为交流电AC(Alternating Current)进而在接收线圈附近产生变化的振荡磁场，节点以相同的振荡频率在接收线圈上接收到交流电，再通过AC/DC转换器将其转换成为其电池充电的直流电。由于节点的能量消耗率各不相同，如何规划MC的行进路径，满足网络中所有节点实时充电的需求，并使能量利用率达到最大，是本文要解决的问题。

已经有很多研究致力于无线可充电传感器网络WRSNs(Wireless Rechargeable Sensor Networks)中MC的充电路径规划问题，一般可分为单MC充电方式[1 -3]和多MC充电方式[4 -7]。其中，文献[1]提出了MC预先行程规划与充电关联的问题；文献[2,3]研究了单MC定向充电方式的时延及成本最小化的问题。单MC充电方式实现简单，但多MC充电方式肯定能进一步提高网络性能，文献[4]设计了一种启发式算法为含有多个MC的WRSNs中节点周期性充电；文献[5]则提出了基于不均匀集群的移动充电算法，用于解决节点能耗不均衡及MC充电效率随时间变化而衰减的问题。以上工作的研究重点在于合理规划充电路径，以达到预期充电效果。还有学者提出根据节点充电请求的紧急程度来规划充电路径，文献[6,7]就结合了节点的时空特征来共同规划MC的充电路径，但制定的策略适合静态路由。现有的研究工作还没有考虑在大型WRSNs中根据节点的时空特征来实时规划路径。

本文在现有工作的基础上提出一种基于时空协作的多MC充电路径规划方案，与上述研究工作不同的是，本文方案不仅联合考虑了节点的空间位置和充电请求的时间要求，还为MC维持了一个动态队列，用于保存MC的局部充电路径，并能随时按照充电请求的紧急程度调整MC的行进路径。本文的主要创新点总结如下：

(1)为更好地解决大型WRSNs中多MC的路径规划问题，将其形式化为多目标联合优化问题。

(2)创新性地提出一种基于时空协作的多MC实时充电算法STMA(Space-Time cooperative Multi-MC charging Algorithm)，该算法联合考虑了节点空间位置和截止充电时间，并为每个MC保持一个动态队列，用于保存局部充电路由，在MC执行充电任务的同时还能获取并响应紧急节点充电请求，使得能量消耗快的节点能及时充上电。

2 相关工作

当前关于WRSNs中MC的充电路径规划的研究工作一般可细分为4类：单MC离线调度(S-off)[1 -3]、单MC在线调度(S-on)[8 -11]、多MC离线调度(M-off)[4,5,12]和多MC在线调度(M-on)[6,7,13]。离线(Off-line)调度方法指的是预先规划好MC行程，实现简单但灵活性低；在线(On-line)调度方法则侧重于为节点按需充电，以较低的充电代价达到较高的网络效用。

S-off方式指事先规划好MC的充电顺序和时间以达到理想的能量效用，如文献[1-3]中预先规划MC行程，以达到能量耗费少、充电效率高的目的；S-on方式则选择为节点按需充电，文献[8]针对按需充电架构提出一种时空调度算法，用于及时调整紧急节点的充电顺序；文献[9]则从另外一个角度考虑按需充电，通过实时控制MC的行进路径和速度来解决节点能量补充不均匀的情况；文献[10]则应用了马尔可夫决策过程来优化MC每个时间段内行进的路径和待充电的节点集；文献[11]针对节点的能量饥饿问题，提出一种在线充电调度方法。上述基于单MC的充电方式实现复杂度小，适用于小型WRSNs。

对于大型WRSNs来说，节点数量庞大、能耗率不一，单MC供电的方式难以保证所有节点实时充电的需求。M-off方式使用多个MC协同工作，以提高节点存活率和成功充电率。文献[4，5]考虑到节点能耗不均衡和充电效率随距离衰减的问题，提出了使用多个MC为长期工作的传感器节点周期性充电的调度算法；文献[12]考虑了时空约束来为MC规划充电路径，但其制定的充电策略适用于静态路由。针对以上不足，M-on方式侧重于使用多个MC为节点按需充电，如在文献[6,7]中，就结合了时间和空间要求共同决策MC的充电路径，其中文献[6]结合了节点的空间优先级和时间优先级制订了混合优先级算法——mTS(Temporal-and Spatial-collaborative charging for multiple WCVs)，但没有考虑路由的实时更新；而文献[7]提出的DAZ(Dynamic Active Zone strategy)算法则是把节点的充电请求分为紧急请求和一般请求，优先对紧急请求的节点充电，但对节点的充电时限欠缺考虑；文献[13]提出了基于遗传算法GA(Genetic Algorithm)的多MC充电调度算法，同样是在路由实时更新上欠缺考虑。

本文针对现有工作的不足，结合时间和空间的要求，考虑了充电路由的实时更新，设计了一种基于时空协作的多MC充电路径规划方案。仿真结果表明，本文提出的方案和目前最新的研究工作相比，具有更高的能量利用率和节点存活率，并在队列长度和充电时延方面也有较好的表现，可以很好地扩展到大型WRSNs。

3 系统架构

本节首先介绍所提方案的网络模型，并给出问题描述和解决方案。

图1所示的WRSN由大量固定位置的无线可充电节点、多个MC和1个基站BS(Base Station)组成。节点、MC和BS都装备有GPS模块，其中节点和MC配备了容量有限的电池，假设BS具有无限的能量，且位置由人为指定。各节点负责监测环境、收集信息，并与BS保持通信；BS负责数据融合与处理；MC能够准确定位节点和BS，以完成无线充电任务。

Figure 1 WRSN model with 3 MCs图1 含有3个MC的WRSN模型

3.1 问题描述

本文将上述具有实时性要求的WRSN中的多MC充电路径规划问题描述如下：在一个含有若干随机部署的无线可充电节点、1个BS和多个MC的WRSN中，各节点以不同速率消耗自身能量，并在能量低于阈值的时候发出充电请求，由BS负责接收并根据节点所处位置，将充电请求分配到对应区域内MC的充电队列中排队。MC从BS出发，根据充电请求的紧急程度依次为各个节点补充能量，并在自身能量不足时返回BS。

本文方案的设计目标是为每个MC寻找一条最佳的充电路径，使得能量消耗快的节点的充电请求能被提前响应，并最大可能保证整个网络的节点存活率和能量利用率最高，同时保持较短的充电队列长度和充电时延。

3.2 解决方案

为解决上述多个目标联合优化问题，本文首先建立一个多目标优化模型，并针对目标函数给出约束条件；然后通过将网络划分为多个簇，研究单个簇内多目标的最优实现，进而提出有效的充电算法。

首先建立如下多目标优化模型：

(1)能量目标。

由于MC电池容量有限，且一旦出发，只有当能量不足时才能返回BS充电，因此要合理运用有限的能量，使得能量利用率η最高：

(1)

其中，EN是节点的总电池容量，EC是MC为节点充电而损耗的能量，EM是MC行驶过程所损耗的能量，EMC是MC的总电池容量。EN、EMC可事先指定，而EC和EM可按式(2)计算：

(2)

其中，N是节点总数，q是节点从MC获取能量的速率，(EN-ei)/q则表示节点xi从开始充电到完成充电的时间，ei是节点xi的当前剩余能量，d是MC行驶的距离，EM是MC以速度v行驶距离d所耗费的能量。

(2)存活率目标。

对于整个WRSN来说，每个节点都发挥着各自的作用，因此要保证节点存活率δ最高：

maxδ=Nlive/N

(3)

其中，Nlive是正常工作的活节点数。

从根本上来说，能量目标和存活率目标都是为了延长网络的生命周期、最大化网络效用。因此，本文将上述多目标优化问题加权转化为单目标优化问题：

(4)

其中，α和β是加权因子，分别表示能量目标和存活率目标对于总体目标的权重。由于较高的能量利用率代表了更多的能量用于为节点充电，更少的能量用于MC移动，而MC移动较少的路径就能将更多的能量提供给节点充电，其实这2个目标是正相关的关系，难以区分哪一个目标对整体目标影响更大。因此，本文取α=β=0.5，把式(4)扩大2倍得到如式(3)所示的目标函数：

(5)

式(5)中的待求量可由式(2)和式(3)求出，确定目标函数后，考虑到能量消耗与能量补充的平衡，有如式(6)所示的能量约束：

EC+EM+γ≤EMC

(6)

其中，γ是MC与BS交换信息所耗费的能量，可忽略不计。

另外，还要保证给节点充电的时间大于MC移动的时间，因此有如式(7)所示的时间约束：

(7)

其中，dxi,xi+1指的是MC从当前充电节点xi处移动到下一目标节点xi+1处的欧氏距离，v是MC的行驶速度,ti为第i个节点充电所用时间。

再结合节点正常工作时的能量要求，得到如式(8)所示的约束条件：

(8)

针对上述提出的多目标优化模型，本文设计了一个两步走充电策略，目标是使得式(5)的值最大：

(1)使用改进的聚类算法公平地划分网络为多个簇，每个簇放置1个MC用于处理簇内的充电请求，有利于平衡每个MC的充电负载，极大减少了用于移动消耗的能量，并使得MC的充电队列维持在一个较低的水平。

(2)对单个簇研究多目标的最优实现，提出一种基于时空协作的多MC实时充电算法STMA。其主要思想是BS为每个MC维持一个动态队列实时接收节点的充电请求，MC结合节点的空间位置和截止充电时间要求来决策行进路径，并且每完成一个节点的充电任务，MC都要从BS处获取更新的路由信息，及时调整充电路径。这种实时的按需充电的策略使得能量消耗快的节点的充电请求能够被提前响应，提高了节点的存活率；并且BS维持的动态队列有利于MC及时调整充电路径，满足了节点实时充电的要求，缩短了队列长度和充电时延。

4 基于改进的聚类算法实现均匀分簇

众所周知，K-means聚类算法实现简单，聚类效果好，但其聚类结果与初始质心的选择有关，完全随机地选择往往会导致聚类结果陷入局部最优且算法收敛慢，因此本文选择K-means++算法来优化初始质心的选择[14]：

步骤1从给定的数据点集合中随机选择一个点作为第1个聚类中心。

步骤2对于数据点集合中的每一个点xi，计算它与已知聚类中心的欧氏距离：

D(xi)=argmin‖xi-κj‖2,j=1,2,…,M

(9)

其中，κj为第j个聚类中心，M为聚类数。

步骤3选择下一个数据点作为新的聚类中心，选择的原则是：D(xi)较大的点被选取成为新聚类中心的概率较大。

步骤4重复步骤2和步骤3，直到选择出M个聚类中心。

步骤5利用选出的M个聚类中心作为质心再运行K-means算法。

选择了M个聚类中心后，就要将剩下的每个数据点按照与聚类中心的距离分配给这M个簇。K-means算法的目标函数为：

(10)

其中，Cj表示第j个簇，κCj表示簇Cj的中心点，‖x-κCj‖2表示簇Cj中的数据点x和对应的中心点κCj之间的欧氏距离。

至此，可以得到大小不一的多个簇，为平衡各个MC的负载，使得任意一个MC不至于过载而导致网络性能变差，接下来实现均匀分簇,具体步骤如下所示：

步骤1找到需要重新分配节点的簇。

根据数据点总数N和指定的簇数M，可求得每个簇中应包含的数据点数R：

R=N/M

(11)

找出数据点数大于R的簇Cmore和数据点数小于R的簇Cless，对应的簇中心分别是κCmore和κCless。

步骤2对于簇Cmore中的每个数据点xi，计算：

dxi,xCless=min(dxi,xCmore-dxi,xCless)

(12)

其中，dxi,xCmore表示数据点xi与簇中心κCmore之间的欧氏距离，dxi,xCless表示数据点xi与簇中心κCless之间的欧氏距离。找出dxi,xCmore-dxi,xCless最小值对应的数据点xi加入簇Cless中，直到各个簇的数据点数相等。

根据上述均匀分簇的思想，将WRSN中的节点作为数据点代入，即可得到节点数均匀的K个簇。

5 基于时空协作的多MC实时充电算法(STMA)

将WRSN公平分簇后，每个簇内放置1个MC以响应来自该簇内节点的充电请求，然后由BS按照节点的截止充电时间为MC创建局部充电路由，并为每个MC维护一个动态队列。图2给出了单个簇内，从节点发出充电请求，到MC响应这些请求的简单示例。

Figure 2 MC charging example in a single cluster图2 单个簇内MC充电示例

最开始，MC停留在BS中，节点在自身电量低于阈值ε(ε=EN·30%)时，即产生充电请求Request并转发至BS，充电请求包含自身当前位置Pi(x,y)和截止充电时间Di：

Request=(Pi(x,y),Di)

(13)

Di的计算如式(14)所示：

Di=ei/si

(14)

其中，si是节点xi消耗能量的速率。

BS在接收到Request后，按照Di的大小存入对应MC的充电队列中，D-表示较小的充电截止时间，D+表示较大的充电截止时间。BS根据收到的Request为MC创建局部路由，MC在开始一次新的充电任务前都会等待一个响应时间τ，以期望BS做出更为有效的路由决策。MC从队列首部取出一个Request，首先计算最早到达该节点的时间Tr，并与节点的Di比较，再决定是否前往充电：

(15)

如果MC计算发现来不及赶在Di到期前到达该节点，则应转发至相邻MC请求帮助，判断是否为相邻MC可通过计算2个簇中心的距离distance是否是所有簇间距离最短的：

distance=min(dκCj-1,κCj),1

(16)

BS持续接收节点的Request并按照其Di将其加入队列中，当收到较小Di值的Request时，意味着对应节点的能量即将耗尽，需要紧急充电，这种紧急节点的Request就被插入到队列的首部，使得MC能够尽快处理这些紧急请求。MC完成队列中所有待充电节点的充电任务，并且还没有收到新的Request时，就停留在最后一个充电节点处，等待新的Request。当MC发现自身电量即将低于从当前位置返回BS所需能量时，就返回基站为自己充电，期间收到的Request则转发给相邻MC，请求代为完成充电任务。图3使用流程图的形式展示了上述的MC路径规划过程。

Figure 3 Flow chart of MC path planning process图3 MC路径规划过程流程图

6 仿真与结果分析

本文使用Python语言来仿真所提的基于时空协作的多MC充电路径规划算法，并将仿真结果分别与mTS算法[6]、DAZ算法[7]和遗传算法GA[15]的结果进行比较，mTS算法与DAZ算法是目前最新且效果最好的关于大型WRSNs中多MC充电路径规划的算法，虽也考虑了节点的时空特征规划路径，但在路由实时更新和充电时限方面欠缺考虑，而GA算法则是经典的多MC路径规划算法，都具有强烈的对比性。本文仿真了500个节点随机部署在大小为200×200 m2的传感区域中，表1所示为由改进的聚类算法将WRSNs分为3,4,5个簇的情况，表2所示为实验参数的设置情况。

图4展示了MC数量为3时，本文所提的STMA算法与 mTS算法、DAZ算法和GA算法的节点存活率对比。可见采用STMA算法的节点在前180 min全部存活，随着程序运行虽有部分节点死亡，但还是保持了97%以上的节点存活率。相比之下，mTS和DAZ的性能相对GA算法虽有较大提升，但最终的存活率在93%左右，而不考虑充电紧急程度的GA算法不仅节点存活率下降较快，且最终存活率下降到了90%以下。

Table 1 Divided cluster size and the number of corresponding nodes表1 划分的簇大小和对应节点数

Table 2 Experimental parameter settings表2 实验参数设置

Figure 4 Comparison of node survival rate图4 节点存活率对比

图5描述了当MC数量分别为3，4和5时，STMA算法分别与mTS、DAZ和GA算法的能量利用率对比。可见随着MC数量的增加，能量利用率也会有小幅提升，这是因为当MC数量增加时，对于单个MC来说，用于移动的能量减少了，但MC的数量增加，总的用于移动的能量也增加了；MC数量为5时，STMA相对于mTS、DAZ和GA算法的能量利用率分别提升了7%，11%和14%，可见在相同MC数量的情况下，本文算法具有最高的能量利用率。图6是MC数量为3时，在算法运行过程中，MC中队列长度的变化情况，可见STMA算法具有较低水平的队列长度。图7则分别对比了MC数量分别为3,4和5时，STMA算法与mTS、DAZ和GA算法的平均队列长度，随着MC数量的增加，几种算法的平均队列长度都明显缩短了，其中STMA算法在MC数量为3时已经有较好的表现，当增加MC数量时，平均队列长度下降程度相较其他算法较小，说明在较少MC数量的情况下，本文算法也有较好的表现。

Figure 5 Comparison of energy utilization图5 能量利用率对比

Figure 6 Comparison of queue length 图6 队列长度对比

Figure 7 Comparison of average queue length图7 平均队列长度对比

图8还给出了随着算法运行，MC旅行路径的距离变化情况，旅行路径距离越小，用于MC移动的能量越少，意味着处理同样大小区域的充电请求，本文算法能更有效地满足节点需求，且充电时延更小，这对于有实时性要求的WRSNs来说，就大大减少了节点因充电不及时而陷入休眠的情况。

Figure 8 Comparison of MC travel path length图8 MC旅行路径长度对比

7 结束语

本文针对节点的实时充电需求，研究了基于时空协作的多MC充电路径规划方案。所提方案的创新之处在于联合考虑了节点的空间位置和截止充电时间，来决策MC的充电路径，并由此提出一种基于时空协作的多MC实时充电算法(STMA)。该算法规定一开始基站为MC创建的是局部路径，而不是静态固定策略，有利于当新的充电请求到达时，及时根据新请求的紧急程度，动态调整MC的充电路径。与其他几种先进充电算法的仿真结果对比表明，本文算法在节点存活率、能量利用率和队列长度等性能指标上表现突出，可以胜任大型WRSNs的实时充电工作。对于未来的研究方向，希望能够沿用机器学习的思想，利用以往的充电请求数据作为数据集，加以预测模型，预测未来的充电路径。