WRSN中多MC协同的一对多能量补充策略*

唐 拓冯 勇李英娜钱 谦付晓东

(昆明理工大学云南省计算机技术应用重点实验室，云南 昆明 650500)

物联网(Internet of Things)的飞速发展离不开无线传感网络(WSNs)提供的技术支持，无线传感器网络是现代社会应用最广泛的信息采集技术，被广泛应用于医疗健康、基础设施状态监测、智能交通、生态环境监测以及军事攻击监测等领域[1]。WSN中的传感器由于受到自身尺寸与成本的限制，通常使用电池进行供电，运行时间受限于电池的容量。得益于无线能量补充技术的发展，利用无线充电技术延长无线传感网络的生存时间已得到广泛的研究，无线可充电传感网络(Wireless Rechargeable Sensor Networks，WRSNs)正在兴起。在WRSNs中使用配备有无线移动充电设备的移动装置(Mobile Charger，MC)为传感器节点提供可靠的能量补充，能够有效减少节点的充电等待时间，成为解决传感器电池能量受限问题的有效解决方案[2-3]。由于WRSNs中的传感器节点失效会导致数据丢失、链接断开甚至网络瘫痪等严重问题，如何调度MC高效地为网络中的传感器节点补充能量是WRSNs充电策略的关键问题。

WRSNs往往布置在极端或较复杂的环境，MC接近传感器节点进行充电有一定困难且效率较低，基于磁耦合谐振充电技术的一对多充电方式允许MC在充电范围内同时对多个传感器节点进行能量补充，不仅使MC可在安全地区对传感器进行能量补充，扩展了WRSNs的应用场景，同时提高了充电效率。磁耦合谐振充电技术[4-5]是目前广泛应用于WRSNs中的能量传输技术。通过在MC和传感器上分别安装发射线圈与接收线圈，调节成相同频率，能量通过强谐振耦合在线圈之间发生传递，可在一定范围内实现一对多无线能量补充。文献[6]利用相邻的正六边形单元格平等分割网络，传感器节点被覆盖在单元格内，MC周期性移动到单元格中心位置通过磁耦合谐振充电技术来实现能量的无线传输。但是该方法未考虑MC充电成本以及距离对谐振充电能量传输的影响，算法性能较低。

随着对WRSNs的规模需求不断提高，使用单MC进行充电已无法达到网络的需求，这是由于MC无法携带足够的能量在一个充电循环中为大规模WRSN中的每个请求节点进行充电，MC在给一部分传感器节点充电后需要返回基站补充自身能量。这种方式不仅充电效率极低而且传感器节点常常由于得不到及时的能量补充而失效。此时需要部署多个MC为网络中的传感器节点充电，但是MC往往价格昂贵，出于成本考虑应使MC数量尽量少。

设计了一种高效的多MC协同充电策略，通过相交圆算法将网络中的传感器节点划分为若干个节点簇，利用最短距离原则确定各个簇的MC充电驻点，之后根据能量约束平衡条件确定网络需要的MC数量，最后通过优先级分配算法使多个MC能够协作对网络进行充电，提高充电效率与能量利用率。

本文第一节介绍了相关工作。第二节概述了网络模型与问题公式。第三节中详细描述了MTORN算法的设计步骤与理论分析。第四节通过仿真实验对比分析所提方案的性能。第五节总结全文。

1 相关工作

本部分简要介绍WRSNs中的能量补充技术。

一对一充电模式中，MC只能在同一时间给一个传感器节点充电。He等[7]提出一种最近节点优(NJNP)原则来解决充电节点的选择问题，但是该方案忽视了响应充电请求的公平性，低电量节点易失效死亡。Dai等[8]考虑了候选充电节点的选择与每个节点的充电时间，之后根据传感器接收到的能量来调度MC的移动规划，最大限度地提高网络的充电效用。文章将问题形式化为最大QoM充电和调度问题(MQCSP)，但是如何获得MQCSP的精确解却未给出较好的解决方案。

一对多充电模式的出现极大地提高了充电效率，更适用于大规模WRSNs中。Kurs等[4]首次提出一对多能量传输技术，允许多个接收器通过单个电源同时充电，有效地解决了单对单充电模式的可扩展性问题，并提高了整体能量传输效率。但是该方法未考虑MC充电驻点的规划，系统充电效率还有极大提高空间。文献[9]研究了在线模式下的多节点充电问题，作者提出了一个充电规划算法来最大化可充电的传感器数量，并指示充电位置，以降低MC移动能耗。但是该方法增加了节点的充电等待时间且未考虑充电的均衡性。

为了进一步提高充电效率，学者们开始研究多个MC充电的方式。在文献[10]中，作者假设所有传感器具有相同的恒定能量消耗率。通过规划MCs的路径，以找到MCs的最小数量，从而延长网络的运行时间。然而由于环境的随机性，传感器能耗往往具有较大波动性，该方法无法适应WRSNs的实际应用情况。在文献[11]中，作者提出了一种称为PushWait的调度算法，MCs不仅可以给传感器充电，还允许它们相互充电。为最大化充电效率，该算法平衡MC充电功耗与移动功耗，同时保证网络中传感器的能量充足。该方法优化了网络的能量利用率，但随着传感器节点数量的增加，所需MC的数量会急剧增加，导致成本过高。

可以看出，现有的充电策略存在对充电均衡性考虑不足以及难以得到最优解等缺陷。由于WRSNs充电优化问题的NP-Hard特性，许多启发式算法也同样面对着在网络规模较大时无法高效解决WRSN充电优化问题的挑战。

为了解决上述问题，提出了MTORN充电算法。以按需充电的模式，在WRSNs中部署多个MC通过一对多充电的方式协同为网络提供及时且稳定的能量补充。同时，引入优先级分配算法来提高动态WRSN中的充电均衡性。

2 网络模型与问题公式

2.1 网络模型

系统模型如图1所示。本文的无线可充电传感网络模型主要由三个部分组成:(1)配备有无线能量接收器的若干个传感器节点(sensor node)(S i＝S1，S2，…S n)；(2)配备有无线充电器的多个MC(M j＝M1，M2，…M m)，MC具有自主移动、计算和通信的能力；(3)基站(BS)，负责收集和处理传感器节点传输的数据，监控整个网络的状态，同时为MC补充能量。所有传感器节点随机部署在二维地图上，节点位置可以精确地确定，传感器节点在自身剩余能量下降到预先设定的阈值lr时主动地向MC发送充电请求，MC可以在区域内自由移动，MC通过无线充电的方式同时为多个传感器节点充电，并在自身电量过低时返回基站为自身补充电量。

图1 网络模型图

MC具有4种状态，分别为空闲、移动、充电和返回基站状态，如图2所示，空闲状态表示MC当前未接收到任何充电请求；移动状态说明MC已确定候选充电簇并向其移动；充电状态表示MC正在为节点簇进行充电；返回基站状态表示MC已完成充电任务或自身能量较低，返回基站补充能量。

图2 MC状态转移图

2.2 问题公式

本节描述系统中能量消耗、能量补充的模型。

2.2.1 能量消耗模型

对于每个传感器，其能量消耗主要由两部分组成:监测任务和数据传输。因此可以根据传感器节点的监测效率和数据传输率来预测各个传感器节点的功耗范围和剩余能量。节点S i(1≤i≤n)的能量消耗速率P i可表示为:

式中:j为节点S i接收数据的源节点，G j，i(t)表示节点S i接收到的信息总和，k为节点S i转发数据的目的节点，G k，i(t)表示节点S i转发的信息总和；α为信号放大器能耗率；d i，j，d i，k分别表示节点S i与节点S j，S k的距离；ρ为接收1 bit信息所消耗的能量。σ为传感器进行监测任务的能耗率，G i(t)为节点S i的监测信息总和。

节点S i在t时刻的能量消耗为:

2.2.2 能量补充模型

MC可以在其范围内的对多个传感器节点进行无线充电。对于节点S i，接收充电的功率为:

式中:d S i，MC是MC和节点S i之间的距离，P c为充电时的源功率，β为调整短距离传输的弗里斯方程参数。G S为发射增益参数，G R为接收增益参数，L P为偏振损耗，σ为整流器效率，λ为波长。

为了提高充电效率和网络生存时间，我们需要尽可能增大簇内每个节点的能量接收功率P S i。

3 MTORN策略设计与实现

3.1 MC充电驻点的位置确定

当MC的充电范围为R时，MC能够通过无线能量传输给以MC为圆心，半径为R的范围内多个传感器节点充电。为MC确定充电驻点目的在于使MC在每个充电驻点能够同时为更多的传感器节点充电。驻点位置的确定分两步实现，第一步通过相交圆算法对节点进行分簇，第二步根据最短距离原则确定各个簇的充电驻点。相交圆驻点选择算法具体步骤如图3所示。

图3 相交圆驻点选择算法示例图

相交圆驻点选择算法:对于一组传感器节点S＝{S1，S2，…，Sn1}，给定每个传感器节点S i(1≤i≤n1)都有一个以S i为圆心，半径为R(MC充电范围半径)的圆，由此可以得到一组相应的圆集合C(｜C｜＝｜N｜)。如果两个或多个圆存在公共交集区域，具有上述特点的传感器节点可划分为一个簇。这个公共交集区域，就是充电驻点的可选部署区域。例如Ci与圆C j以及Ck相交，则三个节点S i、S j、Sk的重叠区域表示为Aijk，将Aijk中所有的坐标点放入一个集合VTijk＝{VT1，VT2，…，VTn2}，充电驻点的位置Pm便从VTijk中选择。

由于无线充电功率随着距离增大而减小，因此采用驻点与簇内各节点总距离最短原则确定驻点位置。假设P m，VTm，S i，S j，S k的二维坐标为(x P m，y P m)，(x Tm，y Tm)，(x Si，y Si)，(x Sj，y Sj)，(x Sk，y S k)，其中(1≤m≤n2，1≤i，j，k≤n1)。可以得到下式:

根据上式可以得到距离簇内各个传感器节点总距离最短的驻点二维坐标位置。

确定MC的充电驻点位置之后，将传感器节点i，j，k加入簇C m中。按照该方法可将整个网络划分为若干个节点簇。对于孤立节点(即与其他节点圆没有公共交集区域的节点)MC需要对其单独充电。

3.2 确定最优MC数量

本节的目标为确定能够满足网络电量需求的最优MC数量。MC价格高昂，在区域中部署过多的MC不符合现实要求，同时MC面临无线充电技术本身的能量损耗以及移动产生的能量损耗问题。因此网络中部署的MC需要使网络整体能耗保持平衡，即m个MC输出的能量要维持自身移动能耗同时满足网络的能量需求。根据以上约束建立能耗平衡约束条件:

假设在一个范围固定的WRSN中，随机部署有n个传感器节点，节点按3.1的方法被划分为L个节点簇，C i表示第i个部署有节点的簇，网络中有m个可以响应充电请求的MC，MC为节点充电的效率为P S i。MC在两个节点簇之间移动的距离为:

式中:L代表节点簇的个数，d C i，C j代表两个节点簇中心之间的欧氏距离，d代表充电簇中心之间的平均欧式距离。假设MC在网络中两个节点簇之间的移动距离为d，则m个MC总的的移动能耗为:

式中:P T代表MC移动能耗率。当网络中所有发起充电请求的节点能量需要被充满时，网络的能量需求为:

ESN为传感器节点的电池容量，E0为发起充电请求的电量阈值，P S i为节点接收充电的功率，n q为网络中发起充电请求的传感器节点个数。

m个MC能补充的电量为:

EMC为MC电池容量，ETH为能够维持MC返回基站补充能量的电量阈值，m为MC个数。

综上，为使网络的整体能耗保持平衡，需满足:

即:

对上式两边同乘m，移项可得:

转化为一元二次等式求解，由于EMC-ETH＞0，因此式(11)相应的数学模型是开口向上且过零点的抛物线，易知一元二次等式的两个解分别为0和m，0不符合要求应被舍弃，确定另一个根m的边界值向上取整即可得到网络最优的MC个数。

3.3 多MC协同充电算法

本节的目标为处理多MC充电系统的协同合作关系。本文引入簇的优先级分配充电算法，多个MC接收充电请求，并每隔T时间检查服务池内的充电请求信息集合，这些信息主要包括簇中节点的剩余能量R s以及簇的充电驻点位置。

初始时MC的状态设为空闲，并位于网络的中心位置。当接收到节点的充电请求时MC会更新服务池，并计算相应簇的优先级ψ(C m)。ψ(C m)表示簇C m的充电优先级，反映了该节点簇需要充电的紧迫程度，是MC进行充电决策的重要依据。其计算公式如下:

式中:Eresidual为簇C m内所有传感器节点的平均剩余能量，Nrequest为发起充电请求的节点个数，N C m为簇C m内的所有节点个数。推导过程如下:

ωN为节点因子，与簇内发起充电请求的节点数量有关。簇内发起充电请求的节点数量Nrequest越多，簇内节点的平均剩余能量Eresidual越低，与MC的距离越近，簇的优先级越高。即簇的优先级与节点因子成正相关，与距离因子和能量因子成负相关，从而有:

综合式(13)～式(16)可得式(12)。

在MTORN中，为了保证网络的充电均衡性，收到充电请求超过其服务能力的MC可以向当前充电可用性较大(即相对空闲)的MC发送帮助消息，将充电任务分配给网络中的其他MC。接下来给出MC当前充电可用性的定义以及计算公式:

式中:E j为移动充电器m j的剩余能量，ωn为MC的任务因子，N j表示移动充电器m j接收到的充电请求数量，N r为网络中所有的充电请求数。在某一时间，MC需要处理的充电请求较少，与簇的距离较近，自身剩余能量较大，则该MC的充电可用性也较大。即MC的充电可用性与任务因子ωn和距离因子ωd成负相关，与能量因子ωe成负相关，因此可以得到:

式中:ωse为能量因子，表示簇内平均剩余能量。

综合式(18)、(19)可得式(17)。通过对充电任务的合理分配，不仅可以均衡网络中MC的能耗，还可以避免网络中节点因电量过低而失效。

多MC协同充电算法伪代码如算法1所示。

算法1 输入参数:执行3.1得到的充电簇c1，c2…cn，多个MC输出结果:各个MC的充电序列

1. 初始化MC参数{ωN，ωe，ωd}2. for all MC i do 3. if MC接收到充电请求then 4. add充电请求into S 5. 计算簇的D(Ci，mj)min以及E residual＝E1＋E2＋…＋EN 6. 计算簇优先级ψ(Cm)7. ψ(C m)max簇为候选充电簇8. else //MC无法处理过多的充电请求9. 计算其他MC的U(mj)10. 向U(m j)较大的MC发送帮助消息11. 由U(mj)较大的MC处理对应优先级较高的充电任务12. end if 13.end for

3.4 充电序列规划

充电序列规划的目标就是根据所得到的节点簇的优先级来决定MC的充电路线(即确定的充电次序)，使多个MC给节点簇补充能量时尽可能地减少自身移动能耗，用有限的能量为传感器补充更多的能量。从而减少失效节点数量、MC移动距离，提高充电均衡性，延长网络生命周期，。

当一个MC接收到多个充电请求时，首先将充电请求放入自身的充电服务池中，之后对充电请求进行解析并计算其所在节点簇的优先级。最后MC将各自要处理的充电请求与其对应的优先级保存在充电序列S q中，每次从序列中选取优先级最大的节点簇C m作为候选充电簇，之后各个MC前往不同节点簇的充电驻点通过无线能量传输对簇中所有节点进行充电。多MC充电序列规划结果如图4所示。

图4 多MC协同充电序列规划示例图

3.5 算法描述

本文提出的MTORN算法具体流程如图5所示。

图5 算法框架图

总之，MTORN策略主要通过以下3个步骤达到多个MC协同对网络进行充电的目标:首先，MTORN通过相交圆算法对网络中的传感器节点进行分簇，再利用最短距离原则为各个充电簇设置最优的充电驻点；其次，根据网络的能耗以及MC自身移动能耗合理估计网络需要的MC数量，部署最优数量的MC为多MC协同充电策略提供了基础；最后，MC在接收到充电请求后根据节点簇的平均剩余能量以及距离划分出请求簇的优先级，每次选择候选充电簇时，均选择优先级最高的节点簇，以最小化网络中由于电量较低而失效的节点数量。另外，当某个MC的充电任务超过其服务能力时，可以向其他相对空闲的MC发送帮助信息，提高充电的均衡性。

4 仿真

本文构建了一个无线可充电传感器网络仿真环境，建立100 m×100 m的区域，并随机部署50个～300个传感器，MC在自身电量不足时回到基站处补充自身能量。实验仿真参数如表1所示。

表1 仿真参数

文使用Python实现了MTORN算法，并与HCCA[12]算法和Cellular[6]算法进行性能对比和评估。HCCA算法是一种WRSN混合聚类充电算法(HCCA)，采用分层聚类和K-means聚类实现位置和能量感知，之后将充电行为形式化为任务，通过任务分割算法HCCA-TS调度MC进行充电。Cellular算法利用相邻的正六边形单元格平等分割网络，MC周期性移动到单元格中心位置对范围内节点进行充电。

4.1 移动成本

本组实验讨论各算法在不同节点数量和MC电池容量下的MC平均移动成本情况，移动成本是MC移动的总路程。如图6(a)所示，随着节点数量的增多，三种算法的MC移动成本均增加，这是因为随着节点数量增加，充电请求会增加，MC需消耗更多能量移动，从而使得移动成本增加。可以看出MTORN方案的移动成本始终低于其他两种方案。图6(b)可以看出MC的移动成本随电池容量的增大而增加，这是因为更大的电池容量会使MC在一个充电周期内的移动时间延长，从而可以进行更多的移动。

图6 移动成本对比

4.2 节点死亡率

节点死亡率表示未及时得到能量补充而失效的节点占总节点的百分比。如图7(a)所示，节点失效率随着节点数量的增多而呈升高趋势，这是由于节点数量增多时，向MC发送的充电请求也会增多，超过MC的服务能力时，死亡节点数量将会增加。可以看出本文提出的MTORN方案的节点死亡率要低于HCCA和Cellular算法，这是由于本策略提出一种优先级充电算法，MC会优先选择剩余电量较低的节点进行充电，极大地避免了节点失效死亡。图7(b)所示，MC电池容量较大时，MC可以在一个充电轮次中为更多节点补充能量，因此MC电池容量越大，节点死亡率越低。

图7 节点死亡率对比

4.3 网络生存时间

网络生存时间指WRSN从开始运行到结束的时间，当网络中失效节点达到设定的阈值时，剩余的节点不足以组成连通的网络，网络停止运行并计算生存时间。由图8(a)可以看出，三种算法的网络生存时间随着节点数量的增加而降低。原因是节点数较高超过了MC的服务能力，MC无法满足所有充电请求，使得失效节点数量增加，最终导致了网络生存时间降低。在图8(b)中，由于MC电池容量的增大能有效减少节点死亡率，因此网络生存时间也相应延长。可以看到HCCA和Cellular算法的网络生存时间始终低于MTORN。

图8 网络生存时间对比

4.4 MC数量

本组实验讨论不同MC数量下的MC充电成本以及节点死亡率。如图9(a)所示，MC数量增加，各个MC的移动成本相应降低。这是因为当MC数量增加时，多个MC可以协作完成充电任务，减少了移动开销。在图9(b)中，随着MC数量增加，节点死亡率降低，这是因为当MC数量增加时，每个MC能共同处理更多的充电任务，更及时地为节点充电，因此节点死亡率下降。

图9 MC数量变化情况

5 总结

本文提出了一种WRSNs中多MC协同的一对多充电策略，适用于具有密集节点的大规模WRSNs。本文目标为，使多个MC在一对多充电方式下，协作完成对WRSNs的能量补充，最大化充电效率，降低节点死亡率。本文首先通过相交圆算法将WRSN中的传感器节点划分为若干个簇，利用最短距离原则确定各个簇的充电驻点位置。再通过能量约束平衡条件确定网络需要的MC数量，之后MC根据簇的平均剩余能量和距离划分优先级，每个MC根据优先级前往不同的簇并对簇内多个传感器节点同时进行充电。仿真实验结果表明，与现有的一对多充电方案相比，MTORN方案能够有效降低节点死亡率与MC移动成本，延长网络生存时间。