基于萤火虫算法的无线可充电传感器网络的充电策略

雷 蕾， 陈宏滨

(桂林电子科技大学 信息与通信学院，广西 桂林 541004)

无线传感器网络(wireless sensor networks，简称WSNs)已经得到了广泛的应用，然而，网络中每个传感器节点通常由能量有限的电池供电[1]，能源是阻碍WSNs部署的障碍之一。尽管以往的研究提出了许多节能方案[2-3]来解决能量不足这一约束，但网络寿命仍然受到固有的限制。因此，相关学者又从为传感器网络补充能源方面延长网络的生命周期，主要可以归纳为更换电池、能量搜集方法、无线能量转换。很多WSNs部署在条件恶劣的野外，更换电池[4]维护成本高。能量搜集方法对环境敏感，发电过程不可控制[5-7]。与可再生能源采集技术相比，无线能量传输技术能为无线可充电传感器网络 (wireless rechargeable sensor networks，简称WRSNs)中的传感器提供更可靠的能量供应。现有方法侧重于使用无线充电设备 (wireless charging equipment，简称WCE)，文献[8]通过WCE对传感器进行充电，这一技术能为传感器提供更加稳定的能量，文献[9-10]使用WCE联合完成充电和收集数据的任务。

近年来，日趋成熟的无线能量传输技术为解决传感器节点能耗问题带来曙光，利用WCE来补充传感器能量引起了研究者的广泛关注。文献[11]提出了一种联合网络中路由活动和充电的策略来延长传感器网络的生命周期，为网络补充能量的同时，有效提高了网络中的能量利用率。文献[12]考虑WCE周期性地在无线传感器网络中移动，并同时对多个传感器节点进行充电，通过离散化和新的线性化方法，得到了可证明的近似最优解。文献[13]指出了目前在线充电机制面临的挑战：避免待充电节点由于长时间得不到充电而失效，同时降低充电器的移动消耗，达到饥饿节点比率与充电器充电代价的平衡。文献[14]研究了无线传感器网络中的按需能量补充问题，并分析了一种简单而有效的具有抢占机制的最邻近策略(NJNP)，这种能量只考虑了空间因素，造成该策略的一些性能并不优越。但是NJNP策略为按需充电过程的性能奠定了坚实的基础，其性能在理论上得到了验证，一直作为评估更高级方案的完美基准。

对于WRSNs的充电策略，不仅要考虑WCE对传感器节点的充电顺序，而且还要规划好WCE对每个待充电节点的充电时隙。在以往研究中，均着力于固定的充电时隙，但其实每个节点的能量消耗率都具有动态性，每次迭代也具有差异性，因此动态充电时隙的必要性在整个充电过程中显而易见。文献[13-14]则是对所有请求充电的节点充电，直至节点被充满为止。

鉴于此，提出一种基于萤火虫算法的在线充电策略(JCDRE)来满足网络中节点的动态能耗需求，并设置合理的动态充电时隙。通过与2个基准非周期充电策略的仿真对比表明，本策略在性能方面优于基准方案。

1 系统模型

图1为无线可充电传感器网络模型，在一个L×L平方区域内随机部署m个节点和一个WCE。在WCE与节点是一对一充电的情况下，该充电方式保证了无线能量传输的最高效率。

图1 无线可充电传感器网络模型

1.1 节点模型

在整个WRSNs中，随机部署m个节点，N={n1,n2,…,nm}，这些节点均为同质节点，具有相同的结构和性能，位置坐标表示为S={(ai,bi),i∈1,2,…,m}。在监测环境的任务中，记无线传感器节点i在t时刻产生数据的速率为Ri(t)，在承担数据路由任务时，记无线传感器节点通过单跳的方式向基站(base station，简称BS)发送数据的速率为gi(t)。节点i均配备一个最大容量为Emax的电池，节点i的初始状态并非全部都在满荷状态，先假设各个节点均有部分程度的消耗，节点的初始能量为ei，i∈1,2,…,m。节点i在整个工作过程中，数据传输和数据感知会导致能量消耗，感知数据的过程中能耗很低，因此研究中忽略感知数据产生的能耗[15]。

在整个迭代的工作轮里，节点i一部分时间用来感知并传输数据，另一部分时间用来接收WCE的能量补给，以维持自身的生命，对于节点i可分为ti,transmit、ti,charge两个时隙，其中ti,transmit为节点i的传输数据的时间，ti,charge为节点i的补充能量时间，二者之间互不影响。

1.2 充电模型

1.2.1 基站

BS具有双重角色，既可以作为WCE的服务站，调整充电设备的充电策略以及为充电车补充电量，还可以汇集由节点发送来的所有消息，其在WRSNs中的初始坐标设为(L/2,L/2)。

1.2.2 WCE

2 问题描述

在提出和分析问题之前，首先提出一些定义：

定义1节点寿命：对于节点而言，它有一个最低能量阈值Emin，当节点的剩余能量因长期未得到补充而达到了最低阈值时，该节点的生命周期就结束。

定义2网络生命周期：对于一个WRSNs而言，当节点死亡率达到比例ε时，存活的节点无法维持网络的正常运行，此时认为达到了网络生命周期。

由上述模型可知，节点i的数据生成率为Ri(t)，发送给基站的数据率为gi(t)，传输数据的时间为ti,transmit，充电时间为ti,charge，节点i的能耗为数据感知的能量消耗和数据传输的能量消耗之和。既然忽略了感知数据所造成的能耗，那么节点i的能耗Ei1就只有传输数据所消耗的部分，即

Ei1=Pi1ti,transmit,

(1)

节点i传输数据能耗功率为

Pi1(t)=uiRi(t)=uigi(t)，

(2)

WCE为节点i充电的充电功率为U,充电时间为ti,charge，所以节点i被WCE充电的能量为

Ei,2(t)=ti,chargeU，

(3)

节点i在t时刻的剩余能量为

Ei,r(t)=ei-Ei,1(t)+Ei,2(t)，

(4)

其中ei为节点的初始能量。

为保证节点不死亡，且剩余能量不超过电池容量，有如下约束：

Emin≤Ei,r(t)≤Emax。

(5)

WCE的初始位置为BS的位置(L/2,L/2)，且其电池容量为C。WCE的能耗分为移动的能量消耗E1(t)和为节点充电的能量消耗E2(t),

(6)

3 JCDRE算法步骤

NJNP(nearest job next with preemption)和FCFS(first come first serve)是被众多研究者所认可的2种充电策略。NJNP从空间位置考虑请求充电节点的充电顺序，距离WCE最近的请求节点最先被充电；FCFS从时间角度出发，最先提出请求充电节点将会按序被充电。本研究提出一种基于萤火虫算法的充电策略JCDRE，联合考虑WCE与请求充电节点的位置远近及节点实时剩余能量的情况。

请求充电的节点i对于WCE来说都具有不同程度上的吸引力，节点i与WCE之间的距离di,W和节点的剩余能量Ei,r(t)分别为萤火虫算法的2种吸引力分力。

节点i对于WCE的吸引力为

(7)

3.1 充电请求级别

当节点i在t时刻的剩余能量达到Er1时，节点i发出一级充电请求，其发送请求给基站的内容及格式为Si=〈Di,Ei,r(t),t1(i,j),charge1〉,其中Di包含请求充电节点i的序号及位置坐标，Ei,r(t)为剩余能量，t1(i,j)为节点i第j次发送一级请求的时间，charge1为发送一级充电请求的标志，用于区别节点发送给基站的数据，存储在充电池H1中。

当节点i在t时刻的剩余能量达到Er2时，节点i发出二级充电请求，其请求的内容及格式为Si=〈Di,Ei,r(t),t2(i,j),charge2〉,其中:t2(i,j)为节点i第j次发送二级请求的时间，charge2为充电请求的标志，存储在充电池H2中。另外，记Er1=θ1Emax，Er2=θ2Emax，其中θ1>θ2。

3.2 吸引力级别

(8)

二级濒危节点的吸引力为

(9)

其中Ψ、λ1、λ2均为常数，且Ψ>1，1>λ2>λ1>0。

3.3 仿真示例

如图2所示，节点1～8的初始能量设置为E1 r(t)

图2 WCE移动轨迹图

1)WCE从基站BS出发，为节点1充满电后，下一个充电节点选择的是节点2，因为节点2的剩余能量最低，且为二级饥饿节点，剩余能量的权重因子较大，使得节点2对WCE的吸引力最大；

3.4 充电时隙

充电时隙的设置对于整个充电策略也至关重要，需要综合考虑被充电节点和待充电节点的实际情况做出策略改变，在选中下一个充电节点的序号后，使其在充电一段时间后，更新充电池H1和H2，若该节点值得继续被充电，则WCE仍在原处为该节点充电，但若有另一个节点更值得被充电，即其吸引力大于该节点，则WCE会在未给它充满的情况下离开，去下一个请求节点。这将使得等待充电的节点减小了充电延迟，同时也有效地减小了节点的死亡率。同时，对于H1和H2里的节点，它们的充电时隙也应该是不同的。H1里濒危节点的充电时隙为

(10)

H2里濒危节点的充电时隙为

(11)

其中，ξ1、ξ2为常量，且ξ1<ξ2。t1i、t2i都是与剩余能量相关的变量，剩余能量越低，被充电时间越多。

3.5 算法步骤

输入：节点数，节点的随机坐标，各节点初始化能量、动态数据率，WCE的坐标、移动速度及载能，BS的坐标。

输出：待充电节点序号及充电时隙。

1) 根据式(1)～(4)计算所有节点的剩余能量。

2) 判断是否有节点达到濒危及分别是几级濒危状态，放入对应充电池。

3) 分别计算濒危节点到WCE的距离。

4) 根据式(8)、(9)，相应地由距离和剩余能量的状况综合决定待充电节点。

5)判断被选中待充电节点的剩余能量是否能够满足WCE移动到此处，若满足，则执行步骤6)，否则，在该节点的充电池删除该节点，并返回步骤2)。

6)相应地根据式(10)、(11)得到充电时隙。

7)更新WCE坐标，并判断是否有死亡节点，其中死亡节点不再被充电。

算法流程如图3所示。

图3 算法流程

4 仿真分析

4.1 参数分析

在式(9)中，参数Ψ是针对一级濒危节点和二级濒危节点而言吸引力的差距，不包括剩余能量和距离这2种吸引力分力带来的差异。

图4为参数Ψ对于网络中节点死亡率的影响。死亡率是指WRSNs所有能量低于死亡阈值的死亡节点占所有节点的比例，且设定WRSNs规模为100个节点随机部署在100 m×100 m的范围内。从图4可看出，JCDRE充电策略明显优于基准策略NJNP、FCFS。2种基准算法从一开始就有一部分节点由于充电不及时导致能量耗尽而死亡，随后死亡率持续增高，且明显高于JCDRE充电策略。此外，当Ψ取值为2.5时，死亡率也低于Ψ取其他值的情况。因此，仿真时将参数Ψ取值为2.5。

图4 参数Ψ对死亡率的影响

4.2 仿真结果

为了更好地展现JCDRE算法与基准算法NJNP、FCFS的对比，将WRSNs中节点的初始能量进行了设定，始终使得网络在初始状态时存在5%的濒危节点，且在100 m×100 m的网络内分别部署了100、120、140、160、180、200个节点，分别进行仿真。参数设置如表1所示。

表1 参数设置

图5为不同节点数下出现首个死亡节点的时间。从图5可看出，相同环境下，随着节点数的增多，出现首个死亡节点的时间越早，因为节点数越多，单个WCE要执行的能量补充越多，导致能量最低的节点越早地因得不到能量补充而死亡，且JCDRE明显优于基准策略NJNP、FCFS，首个死亡节点的出现时间始终最迟，且在100个节点的规模中性能优势最明显。

图5 出现首个死亡节点的时间

图6为不同节点数下的网络生命周期。从图6可看出，相同环境下，随着节点数的增多，网络的生命周期变短，这因为单个WCE需要为更多节点提供能量补充，导致很多节点因长时间未得到充电而达到死亡阈值，因而更早达到网络生命周期。同时，JCDRE在此性能上较其他2种基准策略有明显优势，其网络生命周期始终大于基准策略。

图6 网络生命周期

图7为以100个节点为例的充电延迟tlatency变化趋势。从图7可看出，随着时间增大，WRSNs的充电延迟持续增加，而JCDRE的充电延迟低于基准策略，这表明JCDRE充电策略使得网络中请求充电节点尽可能早地得到能量补充，以降低因能量耗尽而达到死亡阈值的风险。

图7 充电延迟

图8为不同节点数下WRSNs在生命周期内收集到的有效数据。从图8可看出，随着节点数的增多，数据收集量并未增多，因为节点数增多会导致网络过早地进入瘫痪状态，导致有效的生命周期内无法采集到更多有效数据，且JCDRE策略收集到的有效数据量明显高于其他2种基准算法。

图8 有效数据

5 结束语

考虑到WRSNs中各个节点数据率不同，不适于周期性离线充电策略，提出了一种基于萤火虫算法的在线充电策略，以延长网络的生命周期。本充电策略联合考虑节点的实时剩余能量与节点和WCE之间的动态距离，并分别作为萤火虫算法的2种吸引力分力，综合时间和空间2个方面的因素，寻找最佳的待充电节点，并为待充电节点设定与剩余能量相关的动态充电时隙。为了尽量减少WCE连续在濒危的2个节点之间来回充电，此策略将距离导致的吸引力设置得比重较大，以减少WCE过多移动导致性能降低。仿真结果表明，本充电策略在网络生命周期、充电延迟、有效数据收集等性能上比其他2种基准充电策略都更好。