基于成本优化的多跳无线充电问题研究

祝贞阳

（杭州电子科技大学计算机学院，杭州310018)

无线传感网；无线充电；数据采集；锚点

0 引言

无线传感器网络目前应用十分广泛，例如军事、医疗、自然环境监测和野生动物生活习性观察，等等。一般情况下，传感器节点由电池供电，而电池的容量有限，随着时间的推移，传感器节点将耗尽自身的能量，这样就导致了无线传感器网络的生命周期受限。为了保证传感器网络能够持续运行，我们引进了无线充电技术的新概念，目前主流的无线充电技术主要分为三类：电感耦合、磁共振耦合和电磁波辐射技术。

第一类是电感耦合技术[1-2]，电感耦合技术优点在于安全并易于实现，它通过两个线圈间的感应就能实现能量的传递。但电感耦合技术只能用在非常短的距离间充电，而且充电器和设备间必须紧密耦合，精确对准。

第二类是磁共振耦合技术[3-10]，磁共振耦合相比电感耦合技术的初级线圈和次级线圈各多了一个电容，这样就形成了LC谐振电路，当初级线圈和次级线圈谐振频率相等形成共振时才会有能量的传输，它的缺点是不适合移动应用、充电距离有限并难以实现。

第三类是电磁波辐射技术[11-17]，电磁波辐射技术适合移动应用，是一种低功率远距离的能量传输模式。但当无线电频率（RF）太高时会导致不安全和充电效率低。

以上三种无线充电技术都能对传感器节点进行无线充电，从而保证传感器的持续运行。本文通过结合磁共振耦合技术和移动数据采集模型来最小化系统总开销，SenCar在给传感器节点充电的同时还对传感器产生的数据进行采集，以保证在传感器网络持续运行的前提下最小化系统的总开销。本文的创新之处体现在如何挑选出最佳的“锚点”，因为“锚点”的选择关系到充电损耗和SenCar的移动损耗。首先根据能量消耗和能量补充之间的关系确定好完成所有充电任务所需最少的SenCar数量。接下来再对所有选出的“锚点”求一条完整的TSP路径，并规划方案用一定数量的SenCar将路径进行划分，从而使得完成所有充电任务的系统总开销最低。

本文提出一种新的最优成本优化方案，通过设计并实现“锚点选择算法”，该算法首先将传感器节点进行聚类，分别计算每个分类中各传感器节点的平均消耗，并将平均消耗最低的节点作为“锚点”，确保选出的“锚点”能够覆盖到整个无线传感器网络。最后规划方案用适当数量的SenCar使得完成所有充电任务所需的总开销最低。

本文的主要贡献如下：

（1）根据能量消耗和能量补充之间的关系确定好完成传感器网络中所有充电任务所需的最少SenCar数量。

（2）设计并实现了一种新的“锚点选择算法”，该算法首先将传感器节点进行聚类，针对每个充电集合，分别计算各节点的平均损耗，选择平均消耗最低的节点作为“锚点”。同时为了减少能量的损耗，只考虑聚集一跳以内的传感器节点。

（3）确定好“锚点”的位置后，再对所有选出的“锚点”求一条完整的TSP路径，在完成传感器网络中所有充电任务所需总时间一定的条件下，规划方案通过使用适当数量的SenCar将路径进行划分从而使得完成所有充电任务所需的总开销最小。

（4）通过多次模拟实验验证和分析了我们提出算法的性能，实验结果表明，该算法能以一定SenCar数量的开销下最小化系统总开销。

1 相关工作

本节主要回顾了单节点无线充电和多跳无线充电技术的相关工作。

过去的研究工作大多集中在单节点无线充电，单节点无线充电只允许移动充电器一次给单个传感器节点充电，并且移动充电器需要紧挨着传感器进行充电，这样不仅导致了低充电效率以及高延迟，而且后面待充电的节点可能因为长期等待得不到能量补充而耗尽能量甚至饿死。在文献[18]中，作者解决了确定MC的最小数量以保持每个传感器节点连续工作的问题。首先，作者提出一种基于旅行商问题的贪婪算法。接下来开发了一个启发式算法以解决Tours的分配问题，并将这些Tours分配给最小数量的MC。在文献[19]中，作者提出了一个无线能量补充和无线传感器网络中基于“锚点”的移动数据采集（WerMDG）框架，通过考虑能量消耗的各种来源和能量补充的时变特性。首先确定“锚点”选择策略和访问“锚点”的序列。然后，将Wer⁃MDG问题制定为受流量，能量平衡，链路和电池容量以及移动收集器的有限逗留时间限制的网络效用最大化问题。在文献[20]中，作者提出了一种称为移动设备移动算法（MDTA）的新算法，通过使用有限数量的移动设备为传感器充电并收集数据。仿真实验结果表明，MDTA相比其他方法具有更好的性能。在文献[21]中，作者探讨了为无线传感器网络提供能量时的能量不足问题，并提出了一种饥饿避免的移动能量补给方案（SAMER），可通过计算并考虑每个充电要求的最大可容忍延迟来避免能量不足。仿真实验结果表明，SAMER方案能够有效地解决无线传感器网络中能量不足的问题，并实现高效的移动能量补充。在文献[22]中，作者提出了一种智能无线充电车（IWCV）策略，以动态可扩展的方式解决无线传感器网络的能量限制问题。IWCV策略涵盖一种智能路由策略，用于遍历传感器网络拓扑并为电池充电以延长使用寿命。

考虑到单节点无线充电在充电模式上的缺陷，后人在此基础上提出了多跳无线充电技术的新概念，它允许移动充电器同时给多个传感器节点充电，并能够实现能量之间的互换。相比于单节点无线充电，多跳无线充电具有更高的充电效率以及扩展性。但目前针对无线可充电传感器网络中的多跳无线充电技术研究相对还比较少，主要集中在文献[23-26]作了相关研究。在文献[23]中，作者提出了一个采用谐振中继器进行多跳无线充电的新框架。他们构建了基于磁共振耦合技术下的能耗模型，并计算了多跳无线充电效率。然后，他们通过能量消耗和能量补充之间的关系近似估算出完成所有充电任务所需SenCar的数量。接下来将该问题转化为一个双目标优化问题，并提出一个两步近似算法解决这个问题以最小化系统总开销。最后，他们还提出一个后期优化算法以进一步降低系统总开销。在文献[24]中，作者在考虑节点能量需求，传输过程中产生的能量损失以及充电器容量限制的条件下，提出了一个优化模型来确定最小充电器的数量以完成所有充电任务。在文献[25]中，作者提出了一种高效节能的移动多跳充电策略。通过引入基于最优中心点的轮询点选择算法，为移动充电器构建了每个分区的最佳捕获点。并且在每个分区中，采用多跳无线充电的方式为这些节点补充能量。通过联合优化移动路径，中继路由和充电时间，开发了一个充电效率函数来分析能效。在文献[26]中，作者旨在克服无线传感器网络中的能量限制，介绍了三种多跳无线能量传输技术，并且推导出它们各自的能量传输效率。

2 模型和假设

我们提出的模型中基站位于无线传感器网络的中心，SenCar停靠在基站的附近。传感器节点随机部署在无线可充电传感器网络中，SenCar给“锚点”补充能量，SenCar自身携带充电器和数据采集装置，SenCar在给“锚点”充电的同时还对数据进行采集，并将采集到的数据交给基站，而“锚点”获得能量补充后再对请求充电的传感器节点进行充电。SenCar从基站出发，按照“锚点”提前规划好的路径有序地对“锚点”进行充电，直到“锚点”覆盖完整个无线传感器网络。模型中我们假设充电过程中将所有传感器节点的电池都充满。无线传感器网络的网络模型图如图1所示。

图1 网络模型图

数据采集模型：

数据采集过程中涉及到能量消耗，本文的研究工作中只考虑移动数据采集，周围的传感器节点将产生的数据量传送到“锚点”位置，SenCar在给“锚点”充电的同时还对各传感器产生的数据进行移动采集。传感器传送/接收1比特数据的能量消耗为：

其中，e0表示传感器用于感知、编码和调制的能耗，e1表示每比特数据的损失系数，dr表示传输距离，α表示路径损耗系数（通常取2到4），λ表示传感器节点单位时间产生的数据量。移动数据采集局部模型如图2所示。

能量传递模型：

本文考虑磁共振耦合技术下的能量传递模型，能量传递的过程中涉及到能量损耗。计算多跳无线充电效率是本文的关键，文献[1]中采用磁共振耦合模型下的无线充电技术计算多跳无线充电效率η见表1所示。

图2 移动数据采集模型

表1 多跳无线充电效率

由表1可见，随着跳数的增加，无线充电效率逐渐降低，同时随着传感器节点之间距离的增加，无线充电效率也逐渐降低，但随着距离的增加，无线充电效率衰减的比较厉害。因此，多跳无线充电效率与跳数和传感器节点之间的距离相关，而且后续的模拟实验需要用到相关参数。

假定节点j请求dj的能量，那么节点i需要为节点j提供dj/ηij的能量，对于节点i和节点k的无线充电效率ηik=ηijηjk。能量传递的局部模型如图3所示。

图3 能量传递模型

3 问题的形式化定义

问题描述：

在一个随机部署了N个传感器节点的无线传感器网络中（N尽量超过一个SenCar的服务能力），每个传感器节点单位时间内的数据产生率是确定的。给定完成整个无线传感器网络中所有充电任务（将全部传感器节点充满电）的总时间T，T要求小于给定的阈值Y。结合考虑SenCar的使用成本，如何规划方案在使用适当数量SenCar的条件下使得完成这些充电任务所需的系统总开销最小，且保证每个传感器节点都不会饿死。

表2 符号描述

根据上述符号定义，我们可以将该问题转化成如下的优化问题。

对于给定完成整个无线传感器网络中所有充电任务所需的总时间T（不考虑移动数据采集的时间），默认将所有传感器节点的电池充满。

目标函数：

其中：

式（1）代表多跳能量传递过程中的充电成本；式（2）代表SenCar的移动成本；式（3）代表SenCar的使用成本。

约束条件：

上述约束条件中，（4）、（5）规定了 SenCar移动路径的连通；（6）规定了所有传感器节点都被唯一的“锚点”充电；（7）确保节点的充电效率大于效率阈值；（8）确保节点归属于某一锚点；（9）表示SenCar用于充电的总能量；（10）表示SenCar k的移动和充电所需的总时间；（11）表示完成整个无线传感器网络中所有充电任务所需的总时间；（12）表示完成整个无线传感器网络中所有充电任务所需的总时间小于阈值Y；（13）表示SenCar需要为传感器提供的总能量加上SenCar的移动损耗之和不能超过SenCar的充电容量；（14）表示xijk,yia,zik取值为0或1。

4 理论分析

本节主要理论分析了SenCar在移动数据采集过程中的能量消耗以及在能量传递过程中的能量补充，并根据能量消耗和能量补充之间的关系确定完成无线传感器网络中所有充电任务所需的最少SenCar数量。

（1）能量消耗

根据目前数据采集的研究现状，本文只考虑Sen⁃Car的移动数据采集。首先，我们分析SenCar在移动数据采集过程中产生的能量消耗，由于SenCar的移动轨迹具有不确定性，因此很难分析出这个过程中的能耗，根据文献，我们可以近似得到m个SenCar在移动数据采集过程中的能量消耗，记为Es。

其中，l代表跳数，λ代表传感器节点单位时间内的数据产生率，N代表传感器节点数量，ec代表传送或接收一个数据包的能量消耗。

（2）能量补充

确定好m个SenCar在移动数据采集过程中产生的能耗后，接下来需要估算出为无线传感器网络补充的能量，以达到能量消耗与能量补充之间的平衡。我们假设m个SenCar的总充电率为Re。

根据式（16）可以看出，多跳无线充电相比于单节点无线充电具有更好的扩展性。其中，Cb代表传感器节点的电池容量，β代表电池容量的阈值，rmax代表最大充电范围，ρ代表传感器节点的分布密度，SenCar的最长移动时间Tl=2Rc/v（Rc代表感应场的半径，v代表SenCar的移动速度），Tr代表将传感器电池从0到充满所需的时间。

（3）确定最少SenCar数量

理论分析好SenCar在移动数据采集过程中的能量消耗和能量补充后，再根据两者之间的能量平衡关系，得出需要为无线传感器网络补充的能量至少要等于SenCar在移动数据采集过程中消耗的能量。因此，我们让E≤R，结合式（15）和式（16）可以得到：

根据式（17）可以看出，针对固定大小的感应场半径，SenCar的使用数量与传感器节点的数量无关，因此这个特性允许在未发生额外的开销下提高无线传感器网络的扩展性。

5 方案规划

本节我们设计了一套无线可充电传感器网络中多跳无线充电结合移动数据采集模型的成本优化方案。首先，我们提出“锚点”选择算法并确定好“锚点”的位置，然后对所有选出的“锚点”求一条完整的TSP路径，接下来再将TSP路径进行划分，并将其分配给相应数量的SenCar。

（1）“锚点”选择算法

我们首先介绍提出的“锚点”选择算法，该算法基于能量请求来获取“锚点”集合，本章节中“锚点”的选择至关重要，因为“锚点”的选择关系到充电损耗和SenCar的移动损耗，这样会间接影响到系统的总开销。“锚点”选择方案的示意图如图4所示。

图4 “锚点”选择算法

算法1“锚点”选择算法

Input:Recharging node setN,charging setSi,ener⁃gy demanddi,charging efficiency of nodej.

Output:Set of anchorsAand resultant subsetsB.

1.whileB≠Ndo

4.A←A∪k,B←B∪Sk,Si←Si-B,∀ik∈N.

5.end while

（2）成本优化策略

①确定TSP路径

如图4所示，在一个随机部署了N个传感器节点的无线传感器网络中，基站位于无线传感器网络的中心，SenCar停靠在基站的附近。为了选出合适的“锚点”，我们首先定义集合A和B用来记录“锚点”和“锚点”所覆盖的传感器集合，然后将传感器节点进行聚类，得到充电集合Si，针对每个充电集合，分别计算各传感器节点的平均损耗，并选择平均损耗最低的节点作为“锚点”。如果B包含在充电节点集合N中的所有传感器节点，那么算法将终止。否则，继续在剩余平均损耗最低的节点中找到下一个集合，直到覆盖完所有的传感器节点。“锚点”选择算法的伪代码如下所示。

选择并确定好“锚点”的位置后，接下来再通过旅行商算法对所有选出的“锚点”求一条完整的TSP路径，SenCar从基站出发，沿着TSP路径的位置有序地对“锚点”进行充电，直到挑选出的“锚点”覆盖到整个无线传感器网络。假设有网络模型如图5所示。

如图5所示，基站位于无线传感器网络的中心，SenCar停靠在基站的附近，绿色的节点代表普通传感器节点，红色的节点代表“锚点”。SenCar从基站出发，经过每个“锚点”的位置，图5中“锚点”的TSP路径就是对所有“锚点”求得完整的一条哈密顿回路。

图5 “锚点”的TSP路径

确定好“锚点”的TSP路径后，考虑到当无线可充电传感器网络的覆盖区域足够大时，而SenCar的电池容量有限，那么一个SenCar无法满足所有传感器节点的充电请求，因此，此时需要对整个Tours进行划分，这个过程中我们结合考虑SenCar的电池容量，SenCar的移动成本以及多跳充电成本，从而将充电路线进行划分以分配给m个SenCar。假设SenCar的充电路线被分割为k个tours路径，其中k取决于SenCar的充电容量。我们假设让cmax代表从任何节点到基站路径上的最大能量开销，cr代表使用一个SenCar在一个完整路径r上产生的能量成本。

如图6所示，确定好“锚点”的TSP路径后，接下来对“锚点”的TSP路径进行划分，根据SenCar的服务能力，将分割好的TSP路径分配给一定数量的SenCar。每个SenCar都沿着对应TSP路径的位置有序地对“锚点”进行充电。路径划分算法的伪代码如下所示。

算法2路径划分算法

Input:Set of anchorsA,SenCarsM,energy de⁃manddiof nodei,charging efficiency of nodej,ηj,iwhen SenCar is ati.Set of SenCars’initial locationsI,capacityCh,base station b,max energy cost traveling on an edgecmax.

Output:Recharge sequencerjfor SenCar j’s tour.

图6 划分TSP路径

接下来我们需要对系统的总开销进行优化。首先，我们使用加权平均法将多跳能量传递过程中的充电成本和SenCar的移动成本以及SenCar的使用成本构建成一个单目标优化问题，F=w1(FC+FM)+w2FS，如果w2＞w1，那么我们认为更关心SenCar的使用成本，如果w1＞w2，那么我们认为更关心充电成本和Sen⁃Car的移动成本。如果增加SenCar的使用数量后，那么SenCar的使用成本将增加，若此时充电成本和Sen⁃Car移动成本减少的量大于增加SenCar数量的使用成本，那么我们将多使用SenCar数量以降低系统总开销。否则，不考虑增加SenCar的数量来优化系统总成本。我们让∂fm代表增加SenCar数量后SenCar移动成本的变化，∂fc代表增加SenCar数量后多跳能量传递过程中充电成本的变化，∂fs代表增加SenCar数量后Sen⁃Car使用成本的变化，然后让 ΔF=w1(∂fm+∂fc)+w2∂fs，如果ΔF＜0，那么此时系统的总开销降低了。该成本优化算法的伪代码如下所示。

算法3成本优化算法

Input:Recharge sequencea1,a2,…als,set of an⁃chorsAs,energy demanddiof node i,charging efficien⁃cy of j,ηj,iif SenCar is at i,moving costci,jon edge(i,j),time feasibility mark at anchorx←0,objective weightsw1,w2,charging setSafor all anchors.

Output:Total system cost F and the number of in⁃creased SenCar k.

3.if increase k SenCars then

7.ifΔF＜0then

8.The total system cost is reduced.

9.Find minimum total system costFand the number of increased SenCar k.

10.end if

11.end if

12.end while

6 实验模拟和分析

本节在Eclipse平台上分别对上述提出的算法进行模拟实验。本节主要模拟了不同感应场半径和最大充电范围对SenCar数量的影响，不同SenCar数量对SenCar移动成本的影响以及不同SenCar数量对系统总开销的影响。

（1）实验参数设置

实验假定传感器节点随机抛洒在无线传感器网络中，我们假设传感器节点的数量为N=50，SenCar的数量从2个增加到8个。相关参数设置如表3所示。

表3 实验参数设置

实验参数设置好后，根据表3和模拟结果，可以估计出效率超过30%的有效充电范围为rmax=3m。此时将所有参数代入式（17）中，得到m≥1.48，也就是说使用2个SenCar基本上就能满足所有传感器的能量需求。

（2）不同感应场半径和最大充电范围对SenCar数量的影响

我们首先研究了不同感应场半径和最大充电范围对SenCar数量的影响，通过理论分析结果可以得到不同感应场半径和最大充电范围下所需最少的SenCar数量，假设感应场半径从25m增加到50m，最大充电范围从2m增加到4m。理论分析结果如图7所示。

图7描述了不同感应场半径以及最大充电范围下所需的最少SenCar数量，如图7（a）所示，随着感应场半径的增加，所需的最少SenCar数量均逐渐增加，但最大充电范围为2m相比3m变化更明显。而如图7（b）所示，随着最大充电范围的增加，所需的最少Sen⁃Car数量均逐渐减少，但感应场半径为30m相比25m下降的更明显。由此可见，完成无线传感器网络中所有充电任务所需最少的SenCar数量与感应场半径以及最大充电范围有关。

图7

图8 不同SenCar数量下SenCar移动成本的变化

图9 不同SenCar数量下系统总成本的变化

（3）不同SenCar数量下SenCar移动成本的变化

接下来我们着重研究不同SenCar数量对SenCar移动成本的影响，通过模拟实验得到不同SenCar数量在SenCar单位距离移动消耗已知条件下SenCar移动成本的变化情况，假设SenCar数量从2个增加到8个，SenCar单位距离的移动消耗取值为12J/m和24J/m。模拟实验结果如图8所示。

图8描述了不同SenCar数量下SenCar移动成本随SenCar单位距离移动消耗取值不同的变化情况，由图可见，随着SenCar使用数量的增加，SenCar的移动成本均逐渐下降，因为随着SenCar数量的增加，SenCar的移动路径变短，因而移动成本也随之降低了。

（4）不同SenCar数量下系统总成本的变化

最后，我们还研究了不同SenCar数量对系统总成本的影响，通过模拟实验得到不同SenCar数量在Sen⁃Car单位距离移动消耗已知的条件下系统总成本的变化情况，假设SenCar数量从2个增加到8个，SenCar单位距离的移动损耗取值为12J/m和24J/m。模拟实验结果如图9所示。

图9描述了不同SenCar数量下系统总成本随SenCar单位距离移动消耗取值不同的变化情况，由图可见，当SenCar单位距离移动消耗为12J/m时，随着SenCar数量的增加，系统总成本也逐渐升高。当Sen⁃Car单位距离移动消耗为24J/m时，随着SenCar数量的增加，系统总成本呈一定波动趋势。由图可见，当SenCar数量为2时，系统的总成本最小。

7 结语

本文通过结合无线可充电传感器网络中的多跳无线充电技术和移动数据采集模型，提出一个新的最优成本优化方案。首先，根据能量消耗和能量补充之间的关系可以近似得到完成所有充电任务所需最少的SenCar数量。接下来将传感器节点进行聚类，针对每个充电集合，分别求出各节点的平均损耗，优先选择平均损耗最低的节点作为“锚点”，且SenCar在给“锚点”充电的同时还对各传感器节点产生的数据进行移动采集。然后对所有选出的“锚点”求一条完整的TSP路径，再根据SenCar的电池容量，SenCar的移动成本和多跳能量传递过程中的充电成本将充电路线进行划分并分配给一定数量的SenCar，保证每条路径都在一个SenCar的服务范围内，从而得到完成所有充电任务所需的总成本。最后，我们对提出的算法进行模拟实验，实验结果表明，该策略在满足一定时间约束下，使用适当数量的SenCar可以使得完成所有充电任务的总开销最低。