无线可充电传感器网络的移动充电问题研究

刘 创，王 珺，吴 涵

(1.南京邮电大学 宽带无线通信与传感网技术教育部重点实验室，江苏 南京 210003；2.南京邮电大学 江苏省无线通信重点实验室，江苏 南京 210003)

无线可充电传感器网络的移动充电问题研究

刘 创1,2，王 珺1,2，吴 涵1,2

(1.南京邮电大学 宽带无线通信与传感网技术教育部重点实验室，江苏 南京 210003；2.南京邮电大学 江苏省无线通信重点实验室，江苏 南京 210003)

能量问题一直是无线传感器网络(Wireless Sensor Network,WSN)研究的关键之一。WSN中节点能量由容量有限电池提供，当节点能量状态较低时需要及时进行更换以确保整个网络的有效性，在复杂网络环境下人为地进行电池更换难以实现。无线传输技术的出现有效解决了这一难题。因此采用携带高电容量的移动节点，通过无线传输的方式给普通节点进行能量补充的无线可充电传感器网络(Wireless Rechargeable Sensor Network，WRSN)成为当前研究的热点。用移动电池车携带可进行无线能量传输的高能量电池装置进入传感器网络中，通过达到某一项性能的最优制定对应的移动充电策略，对低能量的节点进行能量补充。进一步的研究发展可以根据实际的网络场景，在充分考虑各项约束的提前下提出综合的最优移动充电策略。

无线传感器网络；无线能量传输；移动充电；网络生命期

1 概 述

在无线传感器网络中,传感节点的能量一般由电量有限的一次性电池来提供，这样将严重制约整个网络的持续工作时间。为了保证WSN能够尽可能长时间的正常工作，必须定期对节点电池进行更换，避免因节点失效而导致网络生命期缩短。但是对于有特殊环境要求的应用，如火山监测系统、野外科考等，人为地对传感节点电池进行定期更换变得难以实现。从WSN自身能量的节约和均衡出发，针对传感器节点、网络拓扑结构和组网方式展开研究，通过研究WSN的能量管理策略[1-2]、路由MAC层协议算法[3-4]及跨层协议[5-6](cross-layer protocol)，平衡各传感器节点间的业务量，降低节点能耗，提高WSN的生命期。但该类方案只是尽可能延长节点电池寿命，不能从本质上解决能量限制的问题。通过从自然环境中获取环保能源(如太阳能、风能、震动)以补充传感器节点的能量。Cammarano等[7]提出一种准确的太阳能和风能采集预测模型来帮助节点获取能量。Voigt等[8]提出太阳能感知路由，在路由设计中考虑了自然能量获取。但是能量采集技术的操作过高地依赖周围环境，而环境的不可控性导致实际使用的有效性较低，而且能量采集的装置体积也远比传感节点大得多。

2007年，Kurs等[9]率先阐述了通过强耦合磁共振方式进行无线能量传输(Wireless Energy Transfer，WET)的可行性，让无线传感器网络的研究进入到了一个全新的局面。

无线能量传输技术主要有三个方面的优势：

(1)不需要供电的源设备和被充电的终端设备进行有线或者是接触式连接；

(2)源设备对端设备充电时不固定方位，也不需要在可视范围；

(3)相比从环境获取能量的不可预测性，通过强耦合磁共振方式获取能量是稳定且可控的。

借助无线能量传输技术，通过能量补充设备为传感器节点定期充电是一种解决WSN能量问题的新的开源方案，实际操作以承载高容量电池车/机器人作为移动充电器(Mobile Charger，MC)定期提供能量的移动充电节点。这种方式的研究重点主要集中在充电过程决策方面，目前国内外已经取得了一些研究成果。

2 WSN网络模型

无线传感器网络中，部署着一个固定位置的基站BS/Sink(用v0表示)，N个随机均匀分布在检测区域的传感器节点，各传感节点的通信半径均为r。传感器节点的位置一旦确定，便不再改变。任意两节点间的距离在其通信半径内，则称两节点间存在链路，可直接进行通信。因此，无线传感器网络可用无向连通图G=(V,E)来表示，其中V={v0,v1,…,vN}是N个传感器节点与基站的集合，E是链路集合。节点实时地进行监测并产生感知数据，通过多跳传输的方式将数据传输至基站。传感节点不仅充当感知器，而且可能作为中间传递节点将接收到的其余节点的数据传输至邻近节点或者基站。

3 WSN移动充电模型

无线传感器网络中，传感节点携带有存储容量有限且有无线能量接收装置的可充电电池，节点的最大存储能量为Emax，能量低于Emin时节点将失效。为了确保WSN中的节点都能够维持有效的电量水平从而持续进行工作，提出在网络中引入移动的充电设备，根据整个网络节点能量状态，控制充电设备的移动和充电行为，及时为低能量的节点补充能量。一般采用移动电池车(也称移动充电器MC)，以恒定速度V运动到亟需充电的节点附近，并通过WET方式为一定范围内的一个或者多个节点进行无线充电。节点接收到的能量多少取决于MC充电时的输出功率以及MC与节点的距离(传输效率)。移动设备携带的能量至多为B，既要提供自身的移动，又需传输至网络节点。最初移动电池车携带满能量从其维护站出发，根据网络的能量状态制定不同的充电策略。为了确保整个充电过程的持续性，移动电池车必须在其携带的能量低于零之前回到维护站，进行自身能量的补充。根据网络规模大小、节点部署密度和移动充电设备携带总能量的多少，可有效选取多个移动充电器，以便能及时对网络中所有的低能量传感节点进行能量补充。

图1 WSN的移动充电模型

为了确保整个网络能持续有效地进行监测，必须根据网络的各种约束情况制定合理的移动充电方案，及时做出最佳的充电决策，对节点进行能量补给。当出现多个任务冲突时要进行合理的调度，使得网络性能受到的影响最小。现有的研究工作都致力于构建合理的充电模型和调度方案，以最大限度地利用能量资源，最好地保证网络的性能。

4 移动充电方案的研究

在传感器网络中采用移动充电设备，通过无线传输的方式为节点进行能量补充，能有效解决传统的节点电池更换不及时造成的失效问题。现有的研究方案都是以优化单一目标，如驻站时间比、吞吐量等等，构造充电方案的非线性抽象模型或者规约到经典问题进行求解。对不同的优化目标，充电模型也不一样，下文出现的移动充电节点均是指移动充电设备。接下来将从单移动节点的周期性遍历充电、不考虑数据路由的移动节点的充电、多移动节点的充电和移动充电节点兼具收集数据四个方面进行对比研究。

4.1 单移动节点的周期性充电方案

在周期性场景中，均以最大化驻站空闲时间比为目标，移动充电设备均从服务站(即维护站)出发，完成充电活动后回到服务站。

4.1.1 时不变充电方案

时不变是指传感器节点单位时间收发数据流量不随时间而改变。文献[10]最先提出对网络中所有节点进行固定周期T的遍历充电模型。如图2所示，移动无线充电设备(WirelessChargingVehicle，WCV)从服务站出发，依次为网络中所有节点进行点对点的无线充电，最终又回到服务站。

图2 周期性遍历节点模型

充电周期定义为：

(1)

其中：TP为WCV在一轮充电中移动消耗的总时间；Ti为任意节点i的充电时间；Tvac表示驻站空闲时间，即在服务站休整自补给的时间，研究目标是最大化驻站时间比Tvac/T。

(2)

则节点i单位时间的能量消耗pi为：

(3)

其中：ρ为接收单位数据的能耗；Cij为节点i发送单位数据至节点j的能耗；CiB为单位数据直接传送至基站的能耗(Cij与CiB均与距离有关)。

普通节点的最大电池容量均为Emax，电量低于Emin时节点失效。为了使网络中所有的节点都能正常工作，在任意时刻t节点的剩余能量ei(t)≥Emin，即：

Emax-(T-Ti)·pi≥Emin(i∈N)

(4)

为了保持节点工作的持续性及周期性，必须满足在一个周期中节点能量消耗等于其在每个周期中的充电量，即：

T·pi=Ti·U(i∈N)

(5)

初始时刻节点的能量均Emax，为了达到第一可持续周期之前，必须要构建周期性场景，即初始过渡周期。稳定后的周期性充电均是第一可持续周期的重复。文献[10]有效证明了最大化移动充电器的驻站空闲时间就是使移动时间尽可能少，从而得出遍历所有节点的路径最短问题其实就是经典的TSP问题，因此式(1)可转化为

(6)

最终问题转化为在约束公式(2)-(6)下求最大化驻站时间比。通过引入辅助变量并松弛约束条件，最终将周期性充电问题转化成线性规划问题，利用求解工具求得了近似最优解。

在文献[11]中，WCV可以同时为多个节点进行充电，其可充电范围为D(表示传感节点在充电时的功率接收速率不低于门限值时与WCV的最大距离)，并以基站为中心将整个网络区域划分成边长为D的正六边形小区，如图3所示。WCV周期性地遍历访问所有存在节点的小区中心位置，给区内所有节点同时进行充电至满。显然，当WCV在小区中心进行充电服务时，小区内的节点能量达到Emax的时间是不同的，先充电至饱和的节点会在该状态持续一段时间，直到区内其余节点能量都被充到Emax。

图3 周期性的小区充电网络模型

文献[10-11]假定单位时间节点收发数据量都保持恒定，没有考虑网络的动态特性，也没有对移动设备的电容量进行限制，因为WCV所携带的能量不可能是无限的。此外，讨论的都是网络规模较小的情况，对网络规模较大时，仅由一个WCV为所有节点进行周期性遍历的充电方案是不现实的，因为节点的充电时间和WCV移动的时间都将大大增加，可能会导致不到一个周期就有节点会死亡。

4.1.2 时变充电方案

文献[12]中的网络与充电模型同文献[10]，不同于文献[10-11]中假设的节点单位时间接收和发送的数据在整个充电过程中都保持不变，文献[12]研究的是节点接收和发送的数据随时间变化的周期性遍历网络节点的充电方案，即时变充电场景。因此有：

(7)

此时，单位时间节点的能量消耗也随时间改变：

(8)

其网络模型与充电模型同文献[10]，最终问题转化为连续时变优化问题，求解时将一般充电周期中WCE(WirelessChargingEquipment)工作状态分成三类：行走状态、充电状态和驻站状态。WCE与节点交互的N次充电活动分别对应N个阶段，而WCE与节点无交互的行走或驻站成为N+1阶段，形成离散N+1阶段模型来求解优化问题。

文献[13]的周期性充电场景中，WCE不仅作为能量补给设备，同时兼任数据采集设备，在数据路由的时变特性基础上，研究网络动态拓扑问题。传感数据经过多跳方式传输至BS或WCE。WCE在为节点充电的同时从该节点处获取数据信息，将充电节点看成是数据采集子网的簇头，由于WCE是遍历网络中所有节点，因此簇头节点是动态变化的，子网络的划分也是不固定的，也就是动态拓扑情形。

文献[13]有效利用了WCE移动的优势，让其承担一部分数据采集工作，从而避免充电节点或其临近节点因多跳传输至基站而消耗更多的能量，而且遍历所有节点充电也就是所有节点均会担任子网簇头节点，可以有效均衡能耗。但是由于WCE在网络中移动和充电耗时较长，相比起直接传输至基站的那部分数据，WCE接收的数据带回到维护站会有较大的延迟，不适用于有实时性要求的网络。此外，文献[12-13]都没有对移动设备所携带的能量加以限制。

4.2 未考虑数据路由的单移动节点充电方案

文献[10-13]在制定充电方案的同时，充分考虑了感知数据产生并进行数据传输的能量消耗过程，而文献[14]在未考虑该过程的情况下，研究在不同约束下分别获得最大化充电吞吐量的单一优化充电方案。

文献[14]提出了以最大化充电吞吐量为目标的充电策略，充电吞吐量是指在一次充电活动中被充电的节点个数。限制移动充电器MC(Mobile Charger)在网络中进行一轮充电的时间限制为T(即T时间内必须重返基站)，由于时间限制可能来不及给所有节点进行能量补充，所以必须找到在这个时间里能够为普通节点进行充电的节点数目尽可能多的充电策略。当节点的剩余能量低于门限值时，向BS/MC发送充电请求，BS根据网络状态派遣MC(从BS出发)对发送充电请求的节点进行点对点充电，当MC在进行充电时，仍会接收到新的充电请求，MC给每个节点充电时间固定为C。网络模型用带权重的有向图G(V,E)表示，发送充电请求的节点队列Qc，被充电的节点集合Vc。该问题是NP难的，可以通过一个经典的问题——定向运动问题归约得到，其定义如下：

在欧氏平面给定n个节点，标号从1到n，每个节点都有个分数(score)，找到一条以1为起点、n为终点的最大分数路径，路径长度预算(或者持续时间)不大于给定值。

带时间窗的定向运动问题：给定有向弧权重图G=(V',A',l')，l'(u,v)表示弧长(u,v)∈A'，任意节点v'∈V'有一个时间窗[R(v'),D(v')]，其中R(v')≤D(v')表示访问节点v'的时刻必须位于这个区间。任意两个节点s,t∈V'有整数预算值B>0，找到一条s-t游走长度至多为B但是覆盖的顶点数最多的路径。

对于该问题，可利用已有的迭代贪婪算法求解。文献[15]证明了移动充电的离线充电方案可以从带时间窗的定向运动问题归约得到。方法如下：

将任一个发送充电请求的节点v∈V分裂成两个端点v',v″，将该节点v的充电时间转化为l(v',v″)=C，对v'与v″的时间约束分别为[ri,T],[ri+C,T](ri是节点i发送充电请求的时刻)，构建基站与其余节点(若其他节点进行了分裂，则用时间窗更小的那个端点)到v'的弧，同时从v″到基站和其余节点(进行了分裂，则用时间窗较大的端点)的弧。

显然，离线充电方案转化成了带时间窗的定向运动问题，只是运动的起点和终点均为基站，文中提出了猜测充电序列中间节点的方式，迭代地进行求解。

文献[14]考虑了节点的异构特性，即每个节点的能耗速率不同且维持各自的值不变，由于充电的请求提前知道，但不可能在一轮充电中满足所有请求，算法是最大化充电吞吐量，而没有考虑节点剩余生存时间，有可能造成达到最大的充电吐吞量的路径没有覆盖剩余时间最少的节点的情形。另外，由于节点充电时的剩余能量不可能是相同的，因此充电时间不可能是常数C。

4.3 协作式充电方案

文献[15-16]开始研究有多个移动充电器时的协作式调度充电方案。不同于文献[10-14]，协作式充电对MC的能量进行了限定。文献[15]中首次提出MC不仅可以为传感节点充电，还可与其他MC互相充电。移动充电器从基站携带满电量出发，对网络节点进行充电后，最终回到BS进行能量补给，准备下一轮的充电，研究基于一维线性部署网络。N个传感节点的电池容量均为b，任意节点i单位时间耗电量为ri且保持不变，则节点的再充电周期为τi=b/ri。将网络的调度周期定义为所有的传感器节点都被充满电的两个连续的时间点之间的间隔。目标是最大化MC给网络中所有节点总的充电量Epayload与MC自身移动耗能Eoverhead的比值：

ration=Epayload/Eoverhead

在节点能耗速率一致，MC的个数为k的情况下，Zhang等用实例证明在移动节点数目固定、总能量一致的情况下，移动充电器之间相互协作的充电方式相对于无协作的方式覆盖充电的节点更多[15]。如图4(a)所示：每个节点充电量由一个MC提供，且移动充电器MCi给Li+1到Li之间的节点充电，MCi在Li给MCi-1,MCi-2,…,MC1充满电，MCi刚好有足够的能量返回BS。Zhang等针对协作式充电方式提出了PushWait算法(见图4(b))：MCi给Li+1到Li之间的节点充电，且MCi在Li给MCi-1,MCi-2,…,MC1充满电，然后在Li等待其他i-1个MC都回到Li，再平均分配自己的能量给所有的MC(包括自身)，确保所有的MC都能返回BS。MCi在Li+1充满电，最后返回到Li+1能量刚好为0。在相同条件下，PushWait算法的协作式充电方式是最优的。

(a)协同方式

(b)PushWait方式

文献[15]虽然有效地考虑了MC的能量限制，但是忽略了充电时间，实际也并未考虑MC移动时间与节点充电量及节点能量消耗量之间的具体联系。此外，没有考虑传输的能量损耗，而且仅考虑了单一的线性一维网络场景。在文献[15]的研究成果基础上，文献[16]中充电模型突破1-D的约束，研究2-D网络并充分考虑了能量传输时的损耗以及节点不同的再充电周期，结合单约束情形下各个子算法的优势，提出了综合性能最佳的HηClusterCharing(β)算法。

协作式的充电方式提出移动充电器可以互相充电，并没有实际的理论作指导。在同一充电时刻，一个充电器可能同时给不同组的节点进行能量补充，没有考虑到充电器到达不同节点经过的路程不一样，所花费的时间不一样。同样也忽略了充电时间，没有考虑数据路由对节点能量消耗带来的影响。

4.4 移动设备兼具数据收集的方案

文献[17]采用称之为SenCar的兼具移动充电和数据收集的多功能移动设备，既充当数据收集器又充当充电器，网络所有的数据都经过SenCar传回静态基站，模型如图5所示。

图5 集合移动能量补充和移动数据收集模型

移动节点在网络中预先用离线算法，在SenCar进行一轮充电活动移动的总距离不超过给定值Ltsp的约束下选定的停留点(anchorpoint，特定的节点位置)进行充电服务，并确定停留点的访问顺序。在停留点进行充电的同时，SenCar收集l跳范围内的节点数据(l的选择会影响传感节点的能量消耗速率，必须确保所有的停留点能覆盖网络所有的传感节点)。Guo等[17]在充电时变过程、节点间存在链路时的链路容量的约束以及SenCar在网络中充电的总时间不超过定值T的条件下，试图找到最优的数据产生和上传速率，每个节点最佳的数据传输的路径安排方案，以及移动收集器在每个停留点的最佳停留时间，并提出一个分布式的自适应解决方案，使得整个网络的有效性最大。

利用SenCar进行数据收集相比文献[10-12]的直接多跳传输至基站的方式，能够节约更多的能量，有效避免了固定基站的周围节点能量过度消耗而死亡的危险，但是SenCar收集数据的延迟会增加，不适合于对实时性要求较高的网络，另外在选择停留点时考虑离线算法，不能很好地代表整个网络的实时情况。

5 结束语

无线传输技术的出现开创了WSN网络研究的新局面，通过在WSN中引入移动充电节点进行无线的能量补充，有效解决了WSN的节点能量限制的问题，目前的研究也取得了一定的成果。

文中对现有的移动充电策略研究工作，从多个角度出发进行了分类对比分析。针对当前研究在松优化条件下只考虑某单一性能最优的局限，进一步的研究工作可从以下几个方面展开：

(1)已有的研究大多基于离线的方式，在MC从出发去充电时就已经计算好了移动的路径和经过的节点，可以考虑在线请求情况，及时地对低能量节点进行充电。

(2)综合考虑多方面的约束因子：如节点的异构特性，MC的能量限制，接收、发送和产生数据的能量耗消，通信开销，MC的运动时间以及充电时间等等，更加接近真实的网络环境。

(3)构建通用的充电策略架构：可以根据网络规模选定参与充电的节点数是单个还是多个，以怎样的方式充，是在线还是离线，是适合移动基站绑定还是固定基站，是同时充电还是在充电的同时兼具收集数据。充分考虑网络对实时性的要求以及网络属性，选择相应的最佳方案。

[1]WangQ,YangW.Energyconsumptionmodelforpowermanagementinwirelesssensornetworks[C]//Procof4thannualIEEEcommunicationssocietyconferenceonsensor,meshandadhoccommunicationsandnetworks.[s.l.]:IEEE,2007:142-151.

[2]SalvadoriF,deCamposM,SausenPS,etal.Monitoringinindustrialsystemsusingwirelesssensornetworkwithdynamicpowermanagement[J].IEEETransactionsonInstrumentationandMeasurement,2009,58(9):3104-3111.

[3] 杨 宁,田 辉,黄 平,等.基于博弈理论的无线传感器网络分布式节能路由算法[J].电子与信息学报,2008,30(5):1230-1233.

[4]SazakN,ErturkI,KoklukayaE,etal.AnenergyefficientMACprotocolforclusterbasedeventdrivenWSNapplications[C]//Procofinternationalconferenceonsoftware,telecommunicationsandcomputernetworks.[s.l.]:[s.n.],2010:76-81.

[5]AkyildizIF,VuranMC,AkanOB.Across-layerprotocolforwirelesssensornetworks[C]//Procof40thannualconferenceoninformationsciencesandsystems.[s.l.]:[s.n.],2006:1102-1107.

[6]VuranMC,AkyildizIF.XLP:across-layerprotocolforefficientcommunicationinwirelesssensornetworks[J].IEEETransactionsonMobileComputing,2010,9(11):1578-1591.

[7]CammaranoA,PetrioliC,SpenzaD.Pro-energy:anovelenergypredictionmodelforsolarandwindenergy-harvestingwirelesssensornetworks[C]//ProcofIEEE9thinternationalconferenceonmobileadhocandsensorsystems.[s.l.]:IEEE,2012:75-83.

[8]VoigtT,RitterH,SchillerJ.Utilizingsolarpowerinwirelesssensornetworks[C]//Proceedingsof28thannualIEEEinternationalconferenceonlocalcomputernetworks.[s.l.]:IEEE,2003:416-422.

[9]KursA,KaralisA,MoffattR,etal.Wirelesspowertransferviastronglycoupledmagneticresonances[J].Science,2007,317(5834):83-86.

[10]ShiYi,XieLiguang,HouYT,etal.Onrenewablesensornetworkswithwirelessenergytransfer[C]//ProceedingsofIEEE.Shanghai:IEEE,2011:1350-1358.

[11]XieL,ShiY,HouYT,etal.Onrenewablesensornetworkswithwirelessenergytransfer:themulti-nodecase[C]//Procof9thannualIEEEcommunicationssocietyconferenceonsensor,meshandadhoccommunicationsandnetworks.[s.l.]:IEEE,2012:10-18.

[12] 韩江洪，丁 煦，石 雷,等.无线传感器网络时变充电和动态数据路由算法研究[J].通信学报，2012，33(12)：1-10.

[13] 丁 煦，韩江洪，石 雷,等.可充电无线传感器网络动态拓扑问题研究[J].通信学报，2015，36(1):129-141.

[14]RenXiaojiang,LiangWeifa,XuWenzheng.Maximizingchargingthroughputinrechargeablesensornetworks[C]//Procof23rdinternationalconferenceoncomputercommunicationandnetworks.Shanghai:IEEE,2014:1-8.

[15]ZhangS,WuJ,LuS.Collaborativemobilechargingforsensornetworks[C]//ProcofIEEE9thinternationalconferenceonmobileadhocandsensorsystems.[s.l.]:IEEE,2012:84-92.

[16]ZhangS,WuJ,LuS.Collaborativemobilecharging[J].IEEETransactionsonComputers,2013,64(3):654-667.

[17]GuoSongtao,WangCong,YangYuanyuan.Jointmobiledatagatheringandenergyprovisioninginwirelessrechargeablesensornetworks[J].IEEETransactionsonMobileComputing,2014,13(12):2836-2852.

Research on Mobile Charging Issues on Wireless Rechargeable Sensor Networks

LIU Chuang1,2，WANG Jun1,2，WU Han1,2

(1.Key Lab of Broadband Wireless Communication and Sensor Network Technology of MOE,NJUPT,Nanjing 210003,China;2.Jiangsu Key Lab of Wireless Communication of NJUPT,Nanjing 210003,China)

Energy is a key issue in wireless sensor networks.The energy of nodes is provided by limited battery energy.It is necessary to replace battery to make sure the availability of networks when the node nearly uses up its power.But the location of nodes is unreachable on complicated network environment.As a newly emerged technology,wireless transfer effectively addresses this problem.Therefore,it focuses on adopting a mobile node with high capacity of energy and using wireless transfer technique to recharge low energy nodes on WRSN.A mobile vehicle is used to carry the fully charged battery with high capacity,which can recharge general nodes by wireless energy transfer,and most charging strategies only achieve the optimal with a certain goal.Aiming at the limitation of traditional charging strategies,future research and development should be based on the real network environment,taking multiple constrains into consideration,then coming up with the comprehensive optimal mobile charging solution.

WSN;wireless energy transfer;mobile charging;network lifetime

2015-06-16

2015-09-17

时间：2016-02-18

国家自然科学基金资助项目(61401234)

刘 创(1990-)，女，硕士研究生，研究方向为无线传感器网络；王 珺，副教授，研究方向为宽带网络技术、传感器网络以及网络安全。

http://www.cnki.net/kcms/detail/61.1450.TP.20160218.1634.046.html

TP393

A

1673-629X(2016)03-0162-06

10.3969/j.issn.1673-629X.2016.03.038