一种交通道路限制下的充电车辆调度方案

钟萍，陈元明，杜志成，李琳，桂林

1.中南大学计算机学院，湖南长沙410083

2.湖南理工学院信息科学与工程学院，湖南岳阳414006

3.湖南交通工程学院高科技研究院，湖南衡阳421001

无线可充电传感器网络（wireless rechargeable sensor network,WRSN）由一系列具有能量收集功能的传感器节点构成，能够与能量采集技术[1-3]、无线充电技术[4-5]巧妙结合。相比于传统的无线网络，WRSN可以根据监控的环境更好地决定网络尺寸、节点部署方式及整个网络拓扑。然而，传感器节点通过电池供电但容量有限，难以为大范围网络持续供能。针对这一能量限制问题提出了能量节约[6]、能量收集[7]、无线充电[8]三种解决方案。文献[9-11]提出利用调整占空比让节点在唤醒和睡眠状态转换，以此实现能量节约。虽然该方法在一定程度上会增加网络的生命期，但仅有限延长了整个网络生命期。从能量收集角度出发，文献[12-13]提出通过给节点配置能量转换器，从周围环境中收集能量来延长网络寿命。但由于环境中的能量源不稳定，往往导致获得的能量不可靠且难以控制，此外传感器节点还需要配置体积大的能量转换器，能量收集效率很低。为克服以上不足，在传感器网络中应用了无线充电技术[14]。相比于前两种技术，该技术给节点能量补充的方式是主动的且移动充电车所携带的能量是可靠稳定的，它以一定的充电速率给节点补充能量，整个充电过程可控且可预测。因此无线充电技术可以很好地解决传感器网络中能量短缺的问题。

基于无线充电技术，研究人员通常采用移动充电车为无线传感器网络持续供能[15]。在充电车电池容量受限的情况下，不仅要考虑如何给网络中的传感器节点充电，还要移动充电车确保具有足够的能量为网络中的传感器节点供能。在实际场景中，电池容量有限的充电车因移动而消耗大量的能量，为了减少移动充电车的能量消耗且保证它能顺利返回服务站处给自身进行能量补充，移动充电车的调度问题被广泛研究。文献[16]考虑实际充电调度时充电距离与角度对充电效率的影响，通过计算移动充电车的最优充电率和最优位置来最小化充电周期。文献[17-18]提出了充电车移动受限的可充电传感器网络，考虑在无向道路约束下，调度移动充电车访问传感器节点，从而使移动消耗最小化。文献[19]考虑传感器节点的空间、时间和能量特性量化节点的调度优先级，并通过模糊逻辑使用网络的实时信息合理调度移动充电车以确保充电公平性。文献[20]考虑到实际环境下传感器节点的能量消耗率不同，将实时充电需求建模为时间窗口，并引入充电奖励指标来测量传感器充电的质量。然后采用强化学习的方法在优化移动充电车充电调度路径的同时实现充电奖励最大化。文献[21]在工业环境中设计了一种基于网格的移动充电调度算法，并根据移动充电车的充电特性设计了一种新的路由协议以实现网络的能量平衡，但这种以固定顺序访问网格交叉点就会导致充电设备调度不够灵活。以上研究从无线可充电传感器网络的实际使用特性出发，优化移动充电车的调度，但未考虑充电车辆的移动受到实际的交通道路规则约束，如车辆行驶方向。针对这个问题，本文提出一种充电车移动受限的充电调度方案（mobility constrained charging scheduling scheme,MCCS）。

本文结合实际生活场景研究无线传感器网络充电调度问题。假定网络中的传感器节点分布在城市道路上，移动充电车需要根据交通道路网络约束给节点充电。为了避免出现节点死亡现象，本文优化了电量有限的充电车辆调度路径，以缩短充电时间并延长网络生命周期。

1 系统模型

1.1 网络模型

本文采用有向图G=(V,A)作为网络模型，如图1所示。V是道路交叉路口形成的点集，V={v1,v2,···,vn}；A是城市中的道路集。有m个传感器节点分布在某些重要道路上实时检测道路状况。城市中的道路全部表示为有向边。边a=〈i,j〉表示一段道路。采用r(a)表示边a的反向边，即r(a)=〈j,i〉。假设一段道路上只放置1个传感器节点，那么m≤|A|。如果当前道路中存在传感器节点，则将这条道路称作1条任务。对于每个任务t，l(t)表示该任务长度，任务上的传感器节点需要被补充的能量记作Eneed(t)，当前传感器节点的能量记作E0(t)。

图1 充电车移动受限的WRSN拓扑图Figure 1 WRSN topology of charger vehicle with restricted mobility

1.2 充电模型

用w辆无线移动充电车对位于路径中的传感器节点进行充电，每辆车的电池容量为Q，且车辆行驶保持恒定速度。在网络中设置一个特殊的服务站节点记作o，该节点为充电车提供电量和燃料补充。本文仅考虑具有1个仓库的场景，该场景可以扩展到多个仓库。当传感器节点的能量低于Emin时，该节点向服务站发送充电请求，服务站通过请求可以确定对应节点需要补充的能量以及该节点在网络中所处的位置。当几乎收到网络中所有节点的请求时，服务站根据节点的位置以及需求电量调度移动充电车为其进行一对一方式的充电。当充电车移动到请求节点附近时，充电开始。由于整个等待充电过程中传感器节点能量消耗较少，所以假设节点在等待时有足够的能量维持生命。

充电车辆从服务站位置开始，选择最短路径为传感器节点充电。当充电完成或电池电量不足时，移动车辆将返回服务站以补充电源和燃料。每个传感器的请求在1个周期内仅回答1次。完成充电过程后车辆电池中的剩余电量应不少于0，否则将无法满足路径上传感器节点的需求。

移动充电车的充电路径j记为pj，共有q个节点需要充电，那么pj={o,t1,t2,···,tq,o}。该路径上的需求总电量记作Ej，则且Ej≤Q。

1.3 能量模型

任务所在的有向边集合记为AR，由于1条道路上只放置1个传感器节点，那么可以得到AR⊆A。由此可以将网络中的路径分为任务边和非任务边，移动充电车对任务边进行充电，通过非任务边到达节点。将移动充电车对任务边上的传感器充电过程看作对该任务边访问的过程，那么含有q个任务的路径j中服务消耗计算如下：

路径j中移动充电车从当前任务移动到下一个任务的必要消耗计算如下：

式中：d(a,b)为任务a到任务b的最短距离。充电车沿路径j为传感器节点充电的总移动消耗为

2 问题表述

2.1 问题定义

本文在充电车辆保持恒定速度行驶的前提下求解最短充电调度路径，从而缩短充电时间并降低待充电节点的等待时间和死亡率，最终达到延长网络寿命的目的。用S表示具有移动限制的能量补充问题的解，其中S={pj|j=1,2,···,k},在这里k为充电路径的数目。采用v数组标记某任务边是否充电

初始状态所有任务的v数组值均为0，当任务ti已经被一辆充电车服务过后，该任务的v数组值设置为1。根据模型中提到的限制条件，可得

式(5)给出了目标函数和约束项。本问题的目标是最小化充电车所经过路径的总移动消耗。为了满足所提问题的限制条件，设置两个约束项：一是所有任务都只能服务一次，如果当前充电周期已服务过某任务，该任务再次发出请求时，则需要等待下一个充电周期；二是表示每条路径上充电车给该路径上的传感器节点所充的总电量不能超过充电车的电池容量Q。式(6)表示k条充电路径所产生的总移动消耗。

2.2 问题分析

本模型通过任务的长度来计算充电车辆在任务上的服务成本，即所产生的总服务成本等于整个充电周期内所服务任务的总长度。因此，在接收到传感器节点的请求之后，即可确定该充电过程中产生的服务成本。问题便转化为最小化必要消耗来实现总移动成本的最小化。在具有移动性约束的网络图中，每个充电路径都是一个以服务站为起始节点的环路。在充电调度机制的设计中，不仅需要考虑网络中的传感器节点，还应考虑节点周围的路径。因此，两个节点之间的最短路径不能简单地使用欧几里得距离，而应该通过Dijkstra算法获得。本文研究基于图论中的经典受限弧路由问题（capacitated arc routing problems，CARP）[22]，属于NP-hard问题。将充电任务形式化为遍历请求节点所在任务边，求解的问题从点覆盖转变为边覆盖。

3 MCCS算法

基于扩展领域搜索的模因算法MAENS[23]是求解CARP问题的经典方案，它是由遗传算法和局部搜索算法组成的。但该算法求解效率有限且局部搜索率恒定。为此，本文提出MCCS充电调度算法从优化初始解和增加突变算子两方面对MAENS算法进行改进。

3.1 充电调度算法

MCCS结合了遗传算法和局部搜索算法，它不是一种精确的充电调度机制，而是通过搜索获得近似最优解。该算法由3个子算法组成：种群初始化、遗传算法、局部搜索算法。在获得任务集后即可确定原始种群的大小并生成初始可行解。然后用遗传算法和局部搜索算法来提高解的质量，主要分为2个步骤：第一步，选择2个个体作为亲本并通过序列交叉算子对这些亲本进行杂交以生成新的后代，然后在本地搜索后代；第二步，在本地搜索后对新后代进行突变以产生新个体，并在2个个体中选择消耗更低的个体。如果种群中没有克隆解则将其添加到种群中，否则将直接执行下一次迭代。种群中最好的个体是最后一次迭代所得到的最终解决方案。算法的过程如下：

3.2 突变算子

MAENS在遗传算法中使用恒定的局部搜索率来获得个体，这导致一些性能较差的个体陷入局部最优。针对这一问题，MCCS中加入了突变算子。它对搜索获得的解进行突变产生的新解与当前最优解比较，从而获得最优解。

突变算子的实现集中在两个问题上。首先，需要获得将要进行突变的元素位置，该元素的位置根据当前个体的路径数量和参数p共同求得。在本算子中，参数p是提前设置好的，为了不失一般性，我们对该参数进行了广泛的实验，最终获得最优值。其次，需要对执行扰动后的元素再次排序获得新的可行解。值得注意的是，在再排序的过程中应保持获得最小消耗，否则该解不具备同局部最优解竞争的机会。算法的过程如下：

3.3 路径分解算子

由于初始路径的值可以直接影响所获得的最终结果和收敛速度，为了使得到的充电路径中总移动消耗更少并提高搜索效率，本文提出了路径分解算子对初始解进行优化。路径分解算子对当前获得的每条路径进行扫描并分解，获得相应的任务序列。再将这些任务序列重新划分为多个子路径，计算每条子路径的最小消耗值。最后将分解后的路径按照最小消耗原则对已经生成的路径进行排序。算法的过程如下：

4 实验

本文利用C++编程语言实现所提出的MCCS算法，并在仿真实验中与MAENS[23]算法的性能进行对比，以此评估本算法的有效性。

实验采用文献[24]生成的EGL数据集，按图中路径的数目分为小型网络和中型网络，其中小型网络内包含77个节点，中型网络节点数目为140。在2种规模的网络中均进行了测试，分别比较任务边的数目和充电车数量不同时，两种算法的平均移动消耗和鲁棒性。为不失一般性，对每个实例进行了至少30次独立实验。仿真过程的参数配置如表1所示。

表1 参数设置Table 1 Parameter setting

4.1 平均移动消耗对比

平均移动消耗是测试充电机制性能的一个重要指标，它的大小可以直观地反映调度算法的优劣。本节所考虑的平均移动消耗是指，每个案例在运行30次过程中车辆移动消耗的平均值，平均移动消耗越小对应调度算法的性能就越好。小型网络实例对应的平均移动消耗比较结果如图2所示，中型网络实例对应的比较结果如图3所示。

图2 小型网络下平均移动消耗对比Figure 2 Comparison of average mobile cost in the small network

图3 中型网络下平均移动消耗对比Figure 3 Comparison of average mobile cost in the medium network

在两种网络情境下，MCCS和MEANS算法的表现相似。图2(a)和图3(a)表示在不同任务数量下平均移动消耗的变化。由于任务数量的增加，充电车需要移动经过的道路更多，从而导致移动消耗的增加。但在MCCS算法下的平均移动消耗均低于MAENS算法，且在MCCS算法中任务数量递增导致移动消耗增加的速率明显较低。图2(b)和图3(b)表示在不同充电车数量下平均移动消耗的变化。在任务数量相同时，移动充电车数量的改变对MAENS算法的最优结果影响较大，且MCCS算法的移动消耗明显小于MAENS算法产生的移动消耗。

造成以上情况的原因是：初始化后，路径分解算子将初始解优化并进行临界值控制，从而加速了收敛；同时在对解空间本地搜索时，突变算子突破了局部最优解，获得了具有更小消耗的路径结果，因此MCCS算法可以有效地减少充电车的移动损耗。

4.2 算法鲁棒性对比

算法鲁棒性[25]是衡量充电机制运行过程是否健壮的指标之一，它反映了在一定的参数改变时，维持其算法某些特性的能力。本实验通过运行30次所得结果的标准差来反映算法的稳定特性，探讨当任务数量和移动充电车数量两个参数发生变化时，算法稳定特性的变化情况，以此来对比算法的鲁棒性。在不同的参数影响下，所得结果的浮动范围越小，相对应的该充电调度机制的鲁棒性也就越强。与平均能量消耗的比较相同，我们利用小型网络实例和中型网络实例来分别比较这两种充电机制的鲁棒性。

小型网络实例中的算法鲁棒性比较如图4所示，其中最大浮动范围已在图中用坐标标出。随着任务数量的增加，移动消耗的标准差也在增加，但MCCS算法的标准差浮动范围较小，浮动范围为[131.73，244.83]，比MAENS表现平稳。移动充电车的数量对MCCS算法的鲁棒性没有显著影响，其偏差浮动基本在60左右。相比之下，MAENS算法的标准差浮动范围较大，稳定特性受到明显影响。图5比较了中型网络实例中的算法鲁棒性，可以看到两种算法的鲁棒性明显受到网络大小的影响，算法的标准差浮动范围比小型网络大。这是由于随着网络大小的增大，求解空间也在不断扩大，从而影响稳定特性。从图中还可以看出，MCCS算法最终结果的标准差浮动在不同的任务数量时比MAENS算法小，而当改变移动车辆数量时，MAENS算法所得的浮动范围略小于MCCS算法。其原因在于，在中型网络中突变算子获得更优解的可能性增大，从而导致解之间的偏差加大，造成标准差浮动较大的情况。

图4 小型网络下算法鲁棒性对比Figure 4 Comparison of algorithm robustness in the small network

图5 中型网络下算法鲁棒性对比Figure 5 Comparison of algorithm robustness in the medium network

总体来说，MCCS算法比MAENS算法的鲁棒性更强。这是因为在MCCS算法中，个体在获得初始解后做了分解再组优化，在较好的初始解的基础上进行迭代，最终结果的下限受到约束，因而每个解之间的间距也就比较小，MCCS算法所得结果比较稳定，相对于采用随机初始解的MAENS算法，鲁棒性就得到了保证。

4.3 变异概率对算法的影响

突变算子作为遗传算法中不可或缺的一部分，保证了种群多样性，同时可以避免由于交叉导致的局部收敛。为了验证变异概率对算法的影响，本文分别在小型网络和中型网络中，递增变异概率，观察算法迭代中的优化比率的变化情况。其中，优化比率=（初始解−最终解）/初始解。

表2展示了不同变异概率下MEANS算法和MCCS算法的优化比率。可以看到，在小型网络和中型网络中，随着变异概率的增大优化比率总体呈现上升态势，而变异概率越大，优化比率增长越缓慢。当出现变异概率为1的极端情况时，最终解的优化比率在小型网络中出现了下降的情况。相比之下，MCCS算法的优化比率更高。这是因为，变异概率的增大为解空间的多样性提供了更多可能，同时也增大了获得更优解的可能性，由此造成了优化比率的上升趋势。突变优化对解的优化包括正负两个方向：正向优化时将所得解扩充至当前解空间；负向优化时则忽略所得解。而当变异概率增长到一定程度时，突变所产生的负向优化的可能性增大，从而导致优化比率增长缓慢甚至出现下降。此外，MCCS算法的突变算子保证了所得解的额外变异，是在原正向突变解上的优化，因此MCCS算法的优化比率会比较高。

表2 变异概率对结果的影响Table 2 Effect of mutation probability on results

5 结语

本文考虑了实际情况下无线传感器网络的充电调度优化问题，提出了一种移动受限按需充电调度方案。该方案结合了遗传算法和局部搜索算法探索最佳充电路径，且用路径分解算子来改善种群中的路径和加速算法收敛。为了进一步提高局部搜索效率，本文提出了一种突变算子。仿真实验结果证明了MCCS算法的优化效果，可见本文所提机制在平均移动能耗和算法鲁棒性方面表现出色。