无线可充电传感器网络混合移动充电调度研究*

张 娜，赵传信*，陈思光，邵 星，王 杨

(1.安徽师范大学计算机与信息学院，安徽 芜湖 241002；2.南京邮电大学物联网学院，江苏 南京 210003；3.盐城工学院计算机学院，江苏 盐城 22405)

由大量的微小电子设备组成的无线传感器网络(Wireless Sensor Networks，WSNs)在环境监测、工业智能制造、智慧城市等诸多领域得到广泛应用。然而受限于电池容量，能量问题一直是限制WSN应用的难题应用的难题[1－3]。为了解决能量受限问题，研究人员设计节能路由协议[4]或网络编码[5]来降低传感器节点的能耗，或者利用能量收集器收集周围的环境能量(如电磁能、风能、光能等)，并将其转化为电能给电池充电[6]。然而节能路由等技术仅能有限延长工作时间，自然可再生资源的捕获比较困难，且获取能量并不稳定。

近年来，通过无线能量传输技术延长传感器网络寿命已经引起国内外广泛关注，可以通过静态部署无线充电器或者移动无线充电器对传感器节点进行能量补给[7－8]。静态部署无线充电器需要在网络中部署较多充电器[9]，移动充电器需要规划充电路径。在多数移动充电解决方案中，移动充电车定期进行充电巡行，并访问每个WSNs节点[10－12]。目前移动充电研究方法主要为周期性充电调度[13]和按需实时充电[14]。周期性充电在每个周期固定巡游路径对节点进行能量补给，按需充电只对发出请求的节点进行充电。周期性方案调度移动充电器定期访问节点，为了减少路径代价，移动充电器通常沿最短的哈密顿环运行[15]。

Xie等人假设充电器拥有充足的能量，移动充电器从基站出发，以确定的路径对每个传感器节点进行无线充电，然后返回基站完成一次旅行[16]。Dai等人考虑部署最小数量充电器遍历大规模传感器网络中所有节点的问题，利用启发式算法调度多个移动充电器，满足网络的充电需求[17]。Lyu等人考虑移动充电器能量有限约束下，最大化驻停时间，实际上等价于最小化行驶时间[18]。为了解决此问题提出了PSOGA算法调度移动充电器。Lin等人根据传感器节点的功率状态，以最小化充电延迟对移动定向充电器进行调度，在预定的周游路线上设计近似算法优化移动充电器的充电方向[19]。我们前面工作中采用周期性路径调度与时间分配结合优化充电调度[20－21]。周期性充电适用于业务稳定的网络，对于实时性业务，如果在一个周期调度完成后发出的充电请求可能无法及时响应，导致急需充电的节点因等待充电时间过长而能量耗尽。另外一些方案提出了按需充电，实时调度移动充电器对发出充电请求的节点补充能量[22－23]。

对于非周期性充电规划，由于传感器能量消耗的非确定性，需要根据传感器节点充电请求实时做出调整。He等人提出对充电请求先来先服务，根据充电请求的先后次序调度[24]。该调度只考虑了时间先后关系忽略了空间距离，导致充电时延增加很多。为了克服这一缺点，He等人分析了按需调度的模型，设计了最近充电工作抢占调度以满足实时性需求[25]。当新的请求节点在距离当前充电节点更近，优先插入最新的节点进入充电队列，然而距离较远的节点可能会被饿死。Tomar等人提出一种根据节点剩余能量、节点能量消耗率和节点邻域能量权重等多因素决策方案，量化节点充电调度优先级，提高充电性能[14]。Jiang等人考虑了大规模传感器网络中的充电问题，将充电补给站部署和充电路径调度联合优化，通过消减多余节点提高充电效率[26]。Dong等人对请求节点进行选择，然后采用模拟退火算法优化移动充电路径提高充电效率[27]。然而单纯以效率为目标的优化会导致较多的节点因没有被充电而饿死，从而影响到网络性能。Kaswan考虑多个周期调度节点充电，以最小充电延迟为目标建立线性优化问题，然后扩展重力搜索算法调度在不同周期调度充电器[28]。然而这种调度方案没有考虑充电效率。Wang等人在按需调度基础上考虑休眠调度，然后根据距离和节点能量状态调节优先权，调度节点充电顺序[29]。Tomar等人以最小化驻停时间为目标来提高充电效率，选择驻停点和优化充电路径[30]。Ye提出最大化网络充电效率模型，设计了在线和离线贪婪的调度策略指导充电器充电[31]。

然而单纯考虑实时性需求会降低整体充电效率。考虑到这两种典型方案局限性，本文针对可充电无线传感器网络存在多种类型业务的特点，设计了一种混合调度方案:首先提出了一种软时间窗约束的充电模型，综合考虑充电效率和充电时间窗约束设计合理的目标函数。整个WSNs工作期间被分为多个连续的充电周期，在每个周期内首先通过改进的人工蜂群算法优化调度派遣移动充电器对传感网中请求充电的传感器节点进行能量补给；然后针对实时充电请求，结合在线充电节点插入算法来满足节点实时请求，从而满足WSNs中不同充电业务需求，兼顾充电效率和实时性需求。

1 无线传感器网络充电问题描述

可充电无线传感器网络配置有可收集无线电波能量的接收装置，可以通过无线电接收能量，供给传感器节点使用。网络工作时间被分为多个连续的充电周期，在每个周期内分派移动充电器对传感网中发出请求的传感器节点进行补给。充电完成后，移动充电器返回到基站更换电池，过程循环直到网络任务结束。节点能量低于预定阈值时，将发送充电请求，然后该节点被放入充电池中。每个周期开始时根据充电服务池中待充电节点队列调度充电车充电。在小车充电过程中有可能新的传感器节点需要充电，这些节点通过动态算法安排进入小车充电队列，充电请求模型如图1所示。

图1 充电请求与处理流程

1.1 无线传感器网络能量消耗模型

无线可充电传感器网络是由一组分布在二维区域上传感器节点集合V和固定的汇聚节点S组成的异构传感区域。假设n个传感器节点V＝{v1，v2，v3，…，vn}随机部署在二维区域内。传感器节点采集数据经过预先设定的路由转发给汇聚节点。传感器节点通过多跳的方式将实时监测产生的感知数据传输至Sink节点或者基站，节点之间采用短距通信(如Zigbee)自组织形成网络，基站通过长程通信(如4/5G)与移动充电器通信。每个传感器节点接受和发送的数据量不同，在单位时间内传感器节点vi接受到来自其他传感器节点发来的数据为∑vj∈Ai rj，其中Ai表示经过传感器节点vi转发数据的传感器节点集合，单位时间内传感器节点vi感知的数据量为ri，传感器节点vi在单位时间内发送的数据量如式(1)所示。

根据传感器节点感知数据量与传输数据量，建立可预测的节点能耗模型[32]，设表示节点vi发送单位数据能耗，表示接受单位数据能耗，表示感知单位数据能耗，传感器节点vi在单位时间内消耗的能量ei可以表示为式(2)。

1.2 无线传感器网络充电模型

当节点剩余能量低于预警阈值则可以充电[33]，节点剩余能量低于最低阈值将处于能量耗尽状态。节点充电的时间窗集合TW＝{[st1，dt1]，…，[stn，dtn]}，其中sti表示传感器节点vi最早充电时间，dti表示传感器节点vi能量耗尽时间。移动充电器以速度sc行驶，单位能耗为p，达到节点附近以充电速率u补充能量，完成所有被调度节点充电后，充电器返回基站更换电池准备下一个周期充电。设REi(t)表示传感器节点vi在t时刻的剩余能量，充电器移动至节点附近充电，充电率u为常数，ti表示传感器节点vi的充电时间ti＝(Bi－REi)/u[33]。B为节点电池容量，设请求充电预警阈值为Bmax＝0.3 B，能量耗尽最低阈值Bmin＝0.1 B。传感器节点的剩余能量REi低于Bmax需要补充能量，若移动充电器晚于传感器节点的期望充电最迟时间dti须有相应的惩罚。根据传感器节点的剩余能量和能量消耗率可计算时间窗[rti，dti]如式(3)所示。

式中，TCurrent表示当前时间。移动充电器从基站出发为传感器节点补充能量，在充电完成后，返回基站，整个过程花费时间不超过一个充电周期。充电周期T的值固定，即在充电周期T内移动充电小车必须完成一轮完整的充电任务，如(4)所示。

式中，Ttravel表示移动充电器在路径上行驶消耗的时间，表示在一个周期内给传感器充电的总时间，vc表示被调度充电的节点集合。

1.3 无线传感器网络充电调度模型

在实际网络中，充电方案需要兼顾不同目标，将充电路径能量消耗代价和节点充电时间窗结合起来设计目标函数。路径上能量消耗代价可以反应整个调度方案的能量使用效率，时间窗反应了节点充电时间满足情况。具体的目标描述为:

式中，Etravel表示小车在行驶过程中的能量消耗，其计算公式为:

式中，dist表示移动充电器一个周期内行驶路径总长度，sc表示小车行驶速度，p表示小车行驶单位时间能耗，dis(vi，vj)表示点节点vi和vj之间的欧式距离。不失一般性，假设移动充电器站点为v0，一次调度路径长度计算公式为:

式中，s(i)表示节点vi在调度方案中的充电顺序。ptvi表示违反时间窗节点需要进行惩罚量，其定义为:

式中，fci表示节点开始充电时间，α表示处罚系数。ptvi越大则对应的惩罚力度越大。规划路径时尽可能减少在充电车在行驶过程的能耗Etravel，尽可能减少避免惩罚现象的发生从而尽可能为更多急需充电的节点充电。充电调度问题建立的数学模型P1为:

St:

式(9)表示最小化充电调度的目标，该目标在式(5)中定义。式(10)～式(13)是模型的约束条件，其中式(10)表示第一个节点充电开始时间，式(11)表示充电小车行驶路径的长度，它是由充电路径调度序列是s和节点坐标所决定。约束(12)表明在整个移动充电过程中不能超过一个充电周期T；约束(13)表示充电调度从需要充电的节点中选择节点进行调度，Vc表示本轮调度的充电节点集合，Vd表示充电池中节点集合。

2 移动充电器充电调度和路径规划的优化方法

为了便于规划充电调度，将网络工作期间分为若干个连续的充电调度周期，在每个充电周期内对传感器节点规划充电调度顺序。在每个充电周期开始阶段，所有电池能量在本周期低于能量预警阈值的节点向基站发出充电请求，这些节点被放到充电池中。此外一些实时性任务可能会导致节点在本周期负载过重，导致节点能量处于阈值之下会实时提出充电请求。在充电过程中发生的实时请求，可以根据充电负载情况选择是否插入到充电队列中。每个周期开始，选择充电池中节点并调度充电顺序。因为移动充电调度属于典型的TSP问题，显然属于NP问题。目前智能算法在解决NP问题上受到广泛关注，本节采用人工蜂群算法(Artificial bee colony algorithm，ABC)调度每个周期处于充电池中的节点进行充电，而在充电过程中发生的充电请求将设计动态插入法实时调度。

2.1 人工蜂群算法搜索策略

人工蜂群算法通过模拟蜂群采蜜在解空间中寻找最优解[34]。蜜源代表D维解空间中可行解集合X，第i个蜜源的位置可记为Xi＝(xi1，xi2，…，xiD)。蜂群根据分工不同，可分为雇佣蜂、观察蜂和跟随蜂。每个雇佣蜂对应一个蜜源，雇佣蜂在对应的蜜源Xi附近随机选择蜜源k，产生候选蜜源βi(Xi－Xk)，βi∈[－1，1]表示均匀分布的随机数的扰动幅度。如果候选蜜源优于雇佣蜂对应蜜源则将原蜜源替换为候选蜜源。观察蜂在蜂房中等待，根据雇佣蜂更新后的蜜源适应度，计算每个蜜源的选择概率。根据选择概率，利用轮盘赌算法选择一个蜜源k，更新蜜源候选解，如果候选蜜源优于原蜜源则替换。当雇佣蜂在一定代数后没有改进，这个可行解对应的雇佣蜂在此时就会转化为跟随蜂，随机产生一个新的有价值的蜜源。经过多轮迭代操作，蜂群搜索到的解逐渐收敛于最优解，最终输出最佳解。

2.2 移动充电路径规划的人工蜂群编码设计

无线传感器网络工作时，如果某个周期有较多的传感器节点请求充电或者请求充电的节点位置距离较远时，可能导致该充电周期内无法满足所有请求充电节点的需求。为此需要选择部分节点在当前周期充电，其余节点放入下一个充电周期充电。在每个充电周期内对已选择的充电节点，进行充电调度及路径规划。假设有N个节点参与调度，充电调度可以表示为N个节点序列，因此每个待充电节点可以用分配N－1的充电次序，在对于当前所有请求充电的节点设置一个标志位tagi(取值0或1，1表示该节点需要在当前周期内完成充电操作，0则表示该节点需要放入下一个充电周期充电)，N个充电节点的蜜源编码如图2所示。

图2 一个蜜源编码示意

假设基站收到2号、4号、5号、8号、10号、13号节点提出的充电请求，某一充电方案设置的每一个节点的标志位依次为:1、0、1、1、0、1，对应的充电序列为:4、6、2、3、1、5；可知本充电周期选择的节点次序是5号、8号、2号、13号四个传感器。图2的编码方案可将节点选择和充电路径同时编入。一个蜜源编码相当于一个完整的解决方案，其中优秀的解决方案具有更优的适应度，本文适应度可以表示为－f，f在式(5)中定义。

2.3 改进的人工蜂群算法

基本人工蜂群算法只能求解函数优化问题，而充电调度是典型的整数优化问题，为此提出改进人工蜂群算法(Improve artificial bee colony algorithm，IABC)。改进之处主要体现在蜜源初始化和蜂群对蜜源的更新。蜜源包含选择标志和充电序列两个部分，选择标志采用0/1布尔变量表示对应的节点是否在本轮充电，对于每个节点的tagi进行初始化如式(14)所示。

式中，rand()表示一个0～1上的随机数，sigmoid(x)的定义如式(15)所示。

式中，x表示任意一个实数，取值范围是(－∞，＋∞)，因而sigmoid(x)的范围处于(0，1)。通过式(14)，可以对编码中的每个节点独立执行tag初始化。充电序列在初始化时随机生成不同的序号排列。不同于基本蜂群算法只需要简单的将每一维变量初始化在上下界即可，充电调度的充电序列优化需要在初始化时随机生成不同排列。针对每个蜜源独立进行初始化可以得到初始化的蜜源种群。

由图2编码可知，蜜源种群更新需要整体上对调度排列和标志进行更新操作。为此引入进化算法的交叉和变异操作，结合交叉变异的原则，对基本人工蜂群算法探索过程进行相应的改进。在搜索过程中，对选择的路径提出新的交换机制实现了信息共享和交流，从而提高全局搜索能力使具有更优的多样性。具体执行流程如下。

①交叉操作:选取单点交叉，即随机选择交叉段，然后将父代个体在相同位置上进行交叉替换，如父代个体A(0，1，0，1，1，0｜1，2，3，4，5，6)和个体B(0，0，1，1，1，1｜6，1，3，2，5，4)。采用单点交叉生成两个子代为C1(0，1，0，1，1，1｜1，2，3，2，5，4)和C2(0，0，1，1，1，0｜6，1，3，4，5，6)，生成子代充电调度序列出现冲突现象，C1中2重复，C2中6重复，对于出现的冲突可采用冲突消解方法，可见，二者交换的基因段为254和456，保持此段不变，对于C1，第一个冲突基因为2，取得2在交换段C1中的位置(4)，将交换段外冲突基因替换为C2中相应位置的基因，即4。多次执行替换直到没有冲突即可。

②变异操作:变异操作是增加蜜源多样性的关键操作。对执行性变异操作的蜜源，随机选择标志位tagi修改为tagi＝1－tagi，然后随机选择充电序列两个位置进行交换操作，变异生成蜜源不会产生序列冲突。

改进的人工蜂群算法中雇佣蜂随机从种群中选择蜜源进行交叉变异操作，可以有效扩大算法搜索空间，有利于增加蜜源多样性。观察蜂根据轮盘赌选择蜜源，优质蜜源更有机会参加下一代交叉变异，即性能较优的充电规划方案有更高的概率参与下一代进化操作。跟随蜂则在充电规划方案陷入局部解时跳出局部解。基于人工蜂群算法架构，结合进化算法，给出改进蜂群算法过程如下:

根据算法1可知，行7－行17的复杂度是O(SN×V)，它是行6－行19的循环体，故算法复杂度为O(Maxcycle×SN×V)，这是一个多项式时间复杂度算法。考虑到在网络中一个周期充电节点数量一般规模有限，多项式复杂度算法可以在期望时间内完成按需充电节点的调度。

算法1 改进的人工蜂群无线充电调度算法(IABC)

3 动态插入充电调度

无线传感网工作过程中，可能会遇到新的业务请求导致节点能耗增加过快，同时转发路径上的节点也可能会低于预警阈值。这种实时充电需求难以提前预知，为此需要在充电过程中考虑是否插入节点到充电队列中。如图3所示，经过人工蜂群算法调度的序列为v0→…→vi→vi＋1→…→vj－1→vj＋2→v0，此时有新的节点j和j＋1需要插入到剩下的充电队列中，通过贪婪算法选择到合适的位置进行节点插入操作，结果如图3右边所示。

图3 插入节点的充电路径

在尚未执行充电的待充电队列中选择插入新节点的位置，需要考虑满足时间和容量的约束，并使得新的充电队列方案目标函数仍保持最优。如图4所示，在每个充电周期中，设置动态小周期Δt，实时检测未在充电池中的传感器节点能量是否低于充电阈值。如果有传感器节点能量低于充电阈值，则加入充电池，通过贪婪算法选择合适的位置进行节点插入操作。

图4 动态插入充电调度

传感器节点m添加到充电路径P后增加的目标函数值可表示为式(16)。

P代表尚未执行充电的已调度队列，传感器节点m表示被添加的紧急节点，在P队列首位和中间任一位置，选择最小Δf(P，m)且满足式(12)约束条件。将带充电节点插入到该位置，完成新节点的动态插入。如果没有可行插入位置，则放弃在本周期对该节点进行充电。

算法2 动态充电队列插入算法(Dynamic Insert Algorithm，DIA)

4:从Vuc取出vcur，将m插入到当前节点vcur位置前；5:根据式(12)计算m插入Vuc中后，节点的充电时间。6:if(约束(12)满足)7:计算当前插入当前候选节点的目标函数f(Pi，m)8:else 9:此条充电路径不可行；10:end if 11:移动到Vuc中下一个节点位置；12:end while 13:if(可行的充电路径)14:输出适应度最佳min f(Pi，m)的充电队列L；15:else 16:return 0；17:end if

不失一般性，假设尚未充电节点数量为K，寻找插入点需要循环O(K)，检查约束是否满足需要O(N)，因此算法时间复杂度为O(KN)。在每个充电周期中，动态插入算法在移动充电车开始工作以后运行，与IABC算法相结合工作。

4 仿真实验与分析

4.1 实验设置参数

为了验证算法的可行性和有效性，设置不同网络规模的实验环境。随机部署40～200不等数量的传感器节点，节点路径预先确定，移动充电器补给基地位于区域中心位置。节点业务分周期性和实时性业务两种，周期性业务以固定速率采集数据向汇聚节点发送数据，实时业务按概率在每个周期随机产生新的业务(每个周期＜3个节点)。设充电周期为T＝8 000 s；小车携带足够的电池能量；每个传感器节点初始能量不同，传感器能耗参数参考CC2430[16]。每个周期开始时通过调度算法对放在充电池中的节点进行选择和调度。

表1 网络和节点参数设置

此外在充电过程中，若新的传感器节点因能量低于充电阈值发出充电请求，在满足本充电周期约束条件的情况下插入后继充电调度队列，其余节点放回充电池，分配至下一个充电周期。在这里将设置不同的传感器网络规模场景，并依次进行测试与比较。

为了衡量算法的性能，将本文所提出的方案IABC＋DIA算法与EDF算法[26]和近似算法[33]进行比较，为了简洁，下文中IABC表示IABC＋DIA方案。EDF算法采用基本先来先服务策略调度，无法满足的节点直接放到下一个周期；近似算法采用贪婪策略选择节点调度，其他节点放到后继周期充电。设置四种不同规模的传感器网络，传感器节点随机初始电量，每个传感器节点能耗与网络拓扑结构有关。在不同规模场景下，比较三种算法并从饥饿节点个数、充电路径的长度，充电周期总能耗等几个指标来衡量不同算法的性能。饥饿的节点个数表示不能在达到最低阈值前补充能量节点数量，充电路径长度表示一次充电小车移动路径和，充电总能耗表示每个周期充电器在移动与充电上消耗的总能量，充电效率表示每个周期充电过程中对传感器节点充电的总能量占移动充电器在充电和行驶消耗总能量的百分比。IABC算法参数设置为种群规模NP＝100(雇佣蜂数量＋观察蜂数量)，交叉率80%，变异率2%，limit值为20代，循环周期为500次。

4.2 实验结果与分析

4.2.1 不同算法同一调度周期结果比较

首先比较三种算法在同一充电周期充电路径，充电路径是充电车移动的轨迹。如图5表示的是传感器节点数量为5(a)～5(c)的场景下第18周期充电节点的选择和充电规划路径。图5(a)表示的是EDF算法的路径规划。图5(b)表示的是近似算法的路径规划。图5(c)表示的是IABC算法的路径规划。图5(d)～5(f)表示的是传感器节点的个数为200的场景第8周期，移动充电器对需要充电传感器节点的选择及路径规划。图5(d)～5(f)表示的路径分别是EDF算法、近似算法和IABC算法在第8周期规划的结果三种算法规划的路径。通过图中观察可知，EDF算法完全按照节点能量耗尽时间先后顺序充电，充电车移动路径没有规律；近似算法与IABC充电路径考虑到了路径代价，但是受到充电节点时间窗要求限制，充电路径并不是完全以路径最短为标准。

图5 两种网络规模下同一周期的不同算法规划路径比较

进一步增加节点规模为90和120个节点的网络，分别对不同算法在同一周期内对充电结果的各性能参数对比，结果如表2所示。

表2 三种算法特定周期性能比较

通过四种不同场景比较，可以发现IABC能够获得更短的路径长度，EDF算法调度路径长度最长，是IABC算法的2.01到4.47倍，近似算法调度路径长度是IABC算法的1.54到2.55倍。IABC饥饿节点的数量少于两种对比算法，其中EDF算法饥饿节点数量最多，是IABC算法的2.13到4.38倍。近似算法饥饿节点数量是IABC算法的1到2倍。从实验可以看出，EDF虽然在周期内为传感器节点补充了更多的能量，但是路径长度过长，导致整体的充电效率低下；而近似算法虽然充电效率有所提高，但给传感器节点补充能量总数相对减少了，同时没有充分考虑节点能量较少的节点；IABC算法整体优化，减少路径消耗的同时尽最大可能为更多节点的补充能量。

4.2.2 不同算法多个调度周期性能比较

进一步比较三种算法在连续多个工作周期的性能差异，分别从路径长度，饥饿节点数量和充电效率三个方面进行比较。首先比较充电路径的长度，如图6表示的是移动小车不同周期行驶的路径长度。图6(a)～(d)分别表示40、90、120和200个节点的不同周期路径长度的比较。随着传感器节点数目的增多，请求的传感器节点相继增多，从而使得充电器行驶的路径长度逐渐增大。EDF算法和近似算法的波动幅度相似，IABC算法充电的路径长度波动幅度比较低。在四种场景下，EDF算法的平均路径长度为IABC算法的2.03～2.95倍，近似算法的平均路径长度为IABC算法的1.53～2.30倍。随着节点数量的增加，不同算法规划的充电路径长度都有所增长。从图中可以看出，不同算法之间的差距并不是随节点规模扩大而线性增加。节点数目为90个时，不同算法之间的差距最大，EDF算法的平均路径长度是IABC算法的2.95倍，近似算法的平均路径长度是IABC算法的2.30倍。在不同规模的传感器网络下，由于网络动态性，部分周期IABC算法调度的路径长度不一定最短，但是平均充电路径行驶的距离显著低于两个对比算法，说明IABC算法在优化路径方面具有优势。

图6 多个充电周期内充电小车行驶路径长度

其次比较不同充电周期总能耗，如图7分别表示的是不同周期三种算法下总能耗的比较。如图7(a)～(d)分别表示部署40、90、120和200个节点的场景下，三种算法的总耗能。可以看出随着节点规模的扩大，三种算法的总能耗都有所升高。在传感器数量较小的情况下，IABC在少数周期的总能耗会大于另外两种算法，但随着传感器节点增多，IABC算法的总能耗相对较优。在4种场景IABC算法平均充电总能耗为EDF算法的67.37%～87.89%，为近似算法的47.33%～83.90%。IABC算法的总能耗相对较优的原因是在行驶路径过程中，与其他两个算法相比行驶的路径较短，从而行驶能耗较少。

图7 多个充电周期内总能耗

再次比较饥饿节点个数。为保证节点可以得到及时供电，每个充电节点设置时间窗，尽可能避免节点违反时间窗受到惩罚。分别对比四种场景下，在每个充电周期中三种算法饥饿节点个数，从而比较算法的有效性。图8(a)～(d)分别表示40、90、120和200个节点不同周期中饥饿节点数目。由图看出在每个充电周期中，随着请求节点数量增加，饥饿的节点数目也随之增加。EDF算法下，饥饿的节点个数相对较多。IABC算法平均饥饿节点数目为EDF算法的22.50%～29.68%，为近似算法的46.46%～71.05%。显然，IABC算法饥饿节点的个数在三个算法中最少。EDF算法根据传感器节点的响应先后，并不考虑路径长度，造成饥饿节点个数最多。近似算法虽然考虑了充电效率，但是基于贪婪的策略容易限于局部最优。同时可以看出，随着节点数目增多，IABC饥饿节点数目波动较小，而另两种算法波动较大。总体而言，通过多个连续周期比较可以发现，IABC算法可以有效优化充电路径，降低能耗成本，提高了充电效率。

图8 多个充电周期内饥饿节点数目

4.2.3 不同网络参数对算法性能评估

为了衡量不同网络参数对算法的影响，在同一规模下配置不同参数，比较不同参数值对充电路径长度、充电周期总能耗及饥饿节点数目的影响。

为合理设置目标函数中惩罚系数中的参数α，在同样规模的实验环境下，利用本文所提出的方案IABC算法进行实验。如图9(a)表示的是传感器节点数量为120的场景下，设置不同参数α，每周期产生饥饿节点的数目。如图9(b)表示的是传感器节点数量为120的场景下，设置不同参数α，每周期移动充电器所消耗的总能量。

根据以上实验结果，当参数α设置为0.01时，惩罚系数最为合理。此时每周期产生的饥饿节点数目较为均衡且总体低于参数α为0.001、0.005、0.05、0.1时每周期产生的饥饿节点数目。传感器节点得到了有效及时的能量补充。同时，图9(b)显示当参数α设置为0.01时，多个周期的充电总能耗总体低于参数α设置为其他数值时，充电效果较好。所以，本文实验均在惩罚系数中参数α为0.01的基础上进行。

图9 不同参数α对饥饿节点的影响

其次分析传感器节点数据率r对性能影响。如图10(a)表示不同节点数据率r，同周期中充电行驶路径的比较。如图10(b)表示不同节点数据率r下，同一周期中充电总能耗的比较。如图10(c)表示不同节点数据率r下，同一周期中饥饿节点数目的比较。可以看出，节点数据率r＝2 000 bit/s时，充电小车行驶路径、充电周期总能耗以及饥饿节点数目，普遍低于r＝3 000 bit/s时，饥饿节点数目平均从0.55个增加到5.25个。r＝3 000 bit/s时充电小车行驶路径、充电周期总能耗以及饥饿节点数目也普遍低于r＝4 000 bit/s时，特别是饥饿节点数目平均从5.25个增加到7.95个。节点数据率r的增高对充电小车行驶路径、充电周期总能耗以及饥饿节点数目有负面影响。这是由于节点能耗由传感器感知和传输的数据量决定，当数据率增加时，节点能耗增加，从而导致充电需求也相应增加。

图10 传感器节点数据率对充电性能的影响

再次分析充电小车行驶速度sc对IABC算法性能影响，在行驶路径长度相同的情况下，小车行驶速度sc决定了小车行驶的时间，从而影响小车在行驶过程中所消耗的能量及充电周期中实际的充电时间。图11(a)表示不同小车行驶速度下充电行驶路径的比较，随行驶速度增加，sc＝2 m/s平均路径长度为1 105.90 m，sc＝8 m/s平均路径长度为1 042.35 m和sc＝20 m/s平均路径长度为772.55 m。图11(b)表示不同小车行驶速度下充电总能耗的比较，sc＝2 m/s平均总能耗为10 076.85 J，sc＝8 m/s平均总能耗为为8 907.45 J和sc＝20 m/s平均总能耗为7 644.00 J。图11(c)表示不同小车行驶速度饥饿节点数目的比较，平均饥饿节点数目分别为7.85个、5.25个和4.15个。可以看出，随着小车行驶速度值的增大，充电小车行驶路径、充电周期总能耗以及饥饿节点数目等普遍降低。这是由于小车加快行驶速度，可以节约充电时间，在一个周期充电节点数量得以增加，从而减少后继周期充电压力。

图11 充电小车行驶速度对充电性能的影响

再次分析充电速率对充电性能的影响。充电速率分别设置为u＝8 J/s，u＝18 J/s和u＝30 J/s。图12(a)表示不同充电速率充电行驶路径的比较，随充电速度增加，平均充电路径从u＝8 J/s时1 151.35 m降到u＝18 J/s时1 042.35 m和u＝30 J/s时511.95 m。如图12(b)表示不同u充电总能耗的比较，u＝8 J/s时平均充电总能耗为8 860.55 J，u＝18 J/s时平均充电总能耗为8 907.45 J和u＝30 J/s时平均充电总能耗为5 793.80 J。充电速率u的取值对充电能量有一定的影响且波动幅度在一定的范围，原因在于充电的速率越快，充电时间越小，消耗的能量也相对减少。图12(c)表示不同充电速率下饥饿节点数目的比较，在三种充电速度下，饥饿的节点平均数量分别为5.6个、5.25个和2.85个。充电速率的取值对饥饿节点数目有一定的影响，但波动幅度在一定的范围，主要由于充电的速率越快，充电时间越小，可以满足更多充电节点的充电需求。

图12 充电速率对充电性能的影响

5 总结

能量补给是有效延长传感器网络生命期的关键技术之一，无线能量补给已经成为潜在的有效方法。通过将周期性和按需调度相结合，文中设计了一种面向混合业务的混合调度算法。通过仿真实验比较，在充电路径、充电总能耗和饥饿节点数目方面显著优于对比算法。在饥饿节点数目的关键指标上，在四种不同场景中所提混合算法平均优于EDF算法4.11倍和近似算法1.87倍。在另外两个指标上也优于对比算法，显示所提出的算法具有较好性能，适合无线可充电传感器网络充电调度。当网络规模更大时，单个小车可能无法满足充电需求，从而导致饥饿节点显著增加，下一步将要考虑大规模网络中多充电器的混合调度算法。