基于烟花算法的WSN按需充电与数据收集策略

牟 青, 冯 琳, 魏振春,2

(1.合肥工业大学 计算机与信息学院,安徽 合肥 230601; 2.安全关键工业测控技术教育部工程研究中心,安徽 合肥 230601)

针对无线传感器网络(wireless sensor network,WSN)中能量和存储空间受限的问题,现有的移动充电和移动数据收集解决方案有如下两类:一类是将移动充电和移动数据收集分别集成在不同的移动设备上进行能量补充和数据收集操作;另一类是将充电模块和数据收集模块集成到同一辆小车上,同时对传感器网络进行能量补充和数据收集。文献[1]中对多辆移动小车进行周期性调度的同时为传感器节点进行充电和数据收集,以尽量少的移动设备保证网络正常运行;文献[2]提出将数据收集模块和能量补充模块集成到同一辆移动设备上,系统选择能量较低的节点作为移动小车停留的锚点,移动小车对锚点处的传感器节点进行能量补充的同时,锚点附近的传感器节点通过多跳路由的方式将其采集的数据传输到移动小车的数据收集模块上，WSN中的数据通过移动小车传回基站,有效地利用了移动小车移动方便的特性,在小车为WSN中的传感器节点进行能量补充的同时完成数据收集任务。文献[3]将能量补充和移动数据收集任务分派到2辆不同的移动小车上,一辆小车作为无线充电设备来为传感器节点进行能量补充,另一辆作为移动路由设备来接收传感器设备采集的数据，这样的规划可以保证传感器节点的能量补充和数据收集任务的时效性,但是需要增加设备的数量,提高WSN中的总能耗;文献[4]将无线充电模块和数据收集模块同时集成到同一辆移动小车上,并提出通信范围内节点之间可以互相传输数据,在充电范围内每个传感器节点都能被移动设备充电,该移动设备的充电范围要小于等于传感器节点的通信范围,这样通信范围内移动设备就能够收集传感器节点产生的数据,最后WSN中收集的数据通过移动设备传回基站。该方案综合考虑了传感器节点的剩余能量和剩余存储空间,将能量和存储空间同时作为传感器节点工作状态的指标,按照网络请求和传感器节点的需求对WSN进行能量补充和数据收集规划[5-6]。

本文采用移动小车(mobile car,MC)直接到达节点处对传感器节点进行充电和数据收集[7-9]。本文将传感器节点分为工作和睡眠2种状态[10],当节点能量高于最低能量值并且剩余存储空间大于最低值时,节点处于工作状态;否则节点处于睡眠状态,要保证WSN正常工作就要避免节点进入睡眠状态。本文研究在尽可能多地降低网络能耗时,保证网络正常工作。

1 系统模型与问题描述

本文研究场景为一个二维的WSN网络，包括1个固定基站(base station,BS)、1个移动充电小车MC、n个可充电传感器节点,S={s1,s2,…,si,…,sn}，每个节点对应的能耗分别为{p1,p2,…,pi,…,pn},数据采集率分别为{q1,q2,…,qi,…,qn}。移动小车在基站时能够得到每个传感器节点的位置、电量和内存信息；通过这些信息,使用本文提出的算法小车能确定要操作的节点和小车的移动路径,然后依次移动到传感器节点位置对传感器节点进行充电和数据收集操作,WSN中MC充电与数据收集操作示意图如图1所示。

图1 WSN中MC充电与数据收集操作示意图

图1中节点与小车之间的通信通过单跳方式进行。小车根据节点位置和节点的剩余工作时间选择第t轮需要能量补充与数据收集的节点,小车对节点的能量补充与数据收集在小车到达节点时同时开始,小车对节点充电和数据收集结束离开该节点。当小车遍历完所有需要能量补充和数据收集的节点后,小车回到基站,这一轮操作结束,小车对节点的能量补充与数据收集操作进入下一轮。

1.1 确定需求节点

节点的选择是按需联合充电与数据收集、优化网络能耗的关键。因为网络中消耗的大部分能量是小车行驶过程中消耗的[11]，并且持续运行的网络中,当小车到达节点处时,节点的剩余能量和存储空间越大，小车到达此节点的频率会越高,小车的移动路径会明显增加[4，12],从而增加整个网络运行的能耗，所以在每一轮操作时选择出小车要访问的合适的节点,对整个网络来说至关重要。

基于以上分析,本文在小车选择节点方面，主要考虑节点间的距离和节点的剩余工作时间2个方面。

1.2 MC移动充电与数据收集问题描述

在选择了小车要访问的节点后,MC对需求节点的访问便决定了网络的能耗。

1.2.1 驻站时间

(1)

根据(1)式可得,在第t轮小车驻站时间结束时节点的睡眠时间为:

(2)

(3)

此时节点si的剩余能量与剩余存储空间分别为:

(4)

(5)

1.2.2MC在节点处停留时间

(6)

(7)

(8)

要保证网络正常运行，需要满足:

(9)

(10)

(11)

MC同时对节点进行能量补充和数据收集操作,当节点的剩余能量和剩余存储空间都达到其补充的上限阈值时,MC对节点的操作结束。如果有一方先达到上限阈值而另外一方没有达到上限阈值,那么先达到上限阈值的一方停止能量补充(或数据收集)。数据收集时间为:

(12)

能量补充时间为:

(13)

其中，Ef为节点能量的上限阈值。

MC在节点处的停留时间为:

(14)

(15)

(16)

1.2.3 节点的剩余能量与存储空间

当小车在这一轮中对所有被选择要操作的节点进行能量补充和数据收集结束回到基站后,小车开始进行下一轮的数据收集和能量补充操作。

(17)

(18)

要保证网络正常运行，需要满足节点在此段时间内的睡眠时间为0,即

(19)

此时由(17)式、(18)式可以得到节点剩余能量和节点的剩余存储空间分别为:

(20)

(21)

(22)

要保证网络正常运行，需要满足节点在此段时间内的睡眠时间为0,即

(23)

(24)

(25)

这一轮花费的总时间为小车在路上行驶的时间,即小车在每个需要能量补充和数据收集的节点处停留的时间和小车在基站停留时间的总和。这一轮花费的总时间mt为:

(26)

1.3 优化目标

本文的优化问题OPT-1为通过合理调度MC,在保证网络正常运行的前提下,最小化MC单位能耗,即

(27)

s.t.(3)式、(9)式、(19)式、(23)式。

2 算法设计

根据本文建立的WSN充电与数据收集模型和提出的最小化WSN生命周期内每一轮的MC单位能耗的优化目标,本节给出了用来控制MC单位能耗的需求节点判定方案和MC移动路径规划策略,并给出具体的算法步骤。

2.1 节点选择算法

本文采取的是MC对传感器节点进行按需充电和数据收集的操作,因此在每一轮要确定一部分在本轮中需要被小车进行能量补充与数据收集的节点。本文提出一种根据节点剩余能量和存储空间以及节点到基站距离来求要被选择的节点的算法,对这一轮要操作的节点进行选择。根据节点的位置信息和剩余工作时间,按照本文提出的基于能量需求和数据收集(energy requirement and data collection)的节点选择(select),S-ERDC算法进行分类。S-ERDC算法是基于K均值聚类算法的节点选择算法,两点之间的距离用加权距离来表示,即

di,j=

(28)

其中,di,j为根据节点si(Xi,Yi)、sj(Xj,Yj)的欧式距离和剩余工作时间计算所得的加权距离。根据这个加权后的距离来选择要被操作的节点,α为加权系数，α∈[0,1)。当α取值为0时，表示在不考虑距离的情况下对节点进行能量补充与数据收集操作。本文中α取0.5。此算法可以通过减少小车的移动距离,来降低网络能量。

采用本文的方法对节点进行分簇时需要给出初始质心,本文以基站s0和到基站加权距离最远的点sfar作为初始质心。质心计算公式为:

(29)

其中:ci为要计算的第i个簇的质心;Ci为第i个簇;mi为第i个簇中节点的个数;x为传感器节点到质心的加权距离。

节点选择算法是为了确定网络中在每一轮需要被操作的节点,算法步骤如下。

算法1 S-ERDC算法。

(2) 按照(28)式根据节点剩余能量和存储空间以及到基站的距离计算所有节点间的加权距离。

(3) 将基站和到基站加权距离最远的点作为2个簇头。每个节点到基站的距离为di,0,到基站距离最远节点的距离为d0,far=find(maxdi,0),到基站距离最远的节点为sfar。

(4) 得到质心:c1=s0,c2=sfar。

(5) 将每个节点按照其到质心的加权距离,指派到最近的质心,形成C1、C22个簇。

(6) 根据(29)式重新计算每个簇的质心c1、c2,直到质心不发生改变。

(7) 重复步骤(5)、步骤(6)。

2.2 基于烟花算法的MC节点访问调度算法

在得到需要被访问的节点后,MC从基站出发遍历所有需要访问的节点,然后回到基站。合理规划MC移动路径能够有效地降低MC在移动过程中消耗的能量,这部分消耗能量是网络消耗总能量的重要组成部分。本文中MC的路径规划问题本质上是一个NP-C问题,本文采用改进烟花算法,即差分进化烟花(differential evolution fireworks,DEFW)算法来求解,首先通过烟花爆炸产生火花,然后对爆炸产生的火花进行差分变异操作,得到差分火花,最后在烟花、火花和差分火花中选出下一代种群。因为DEFW算法是在原始烟花算法的基础上进行改进的,所以本文对改进的火花差分变异操作进行分析。

对于爆炸产生的火花,一般只是产生在烟花的周围,这样不断迭代容易使得种群陷入局部最优解。本文对烟花爆炸产生的火花进行差分变异,保证产生的火花的多样性。火花差分变异是对烟花爆炸产生的所有火花进行差分变异操作,其中差分变异是将2个个体的差向量作为第3个个体的随机变化源,将差向量加权后按照一定的规则与第3个个体求和从而产生变异个体。本文中将一次迭代中产生火花的最优值作为需要变异的个体,产生的火花依次交替作为随机变异源,如第1个火花与第2个火花作为变异源与本体结合产生第1个变异个体,第2个火花与第3个火花作为变异源与本体结合产生第2个变异个体,依此类推可以产生和火花数目相同的变异个体。火花差分变异过程为:

(30)

其中:X为第g次迭代产生的火花数目;xi,g为第g次迭代产生的第i个火花;xbest,g为第g次迭代产生的最优火花作为的变异本体;F为加权系数;vi,g为第g次迭代中产生的第i个变异火花。

以二维空间为例说明二维向量中火花差分变异过程,如图2所示。图2中:xbest为变异本体;x1、x2为第1个、第2个火花;v1为通过(29)式计算得到的第1个差分变异火花。

图2 二维向量火花差分变异

MC行驶路径规划算法是本文核心算法。本文所设计的DEFW算法结合了烟花算法和差分进化算法,具体操作步骤如下。

算法2 DEFW算法。

输出:f。

(2) 烟花算法种群和参数初始化。

(3) 当i≤I时,对初始种群进行烟花爆炸操作产生n个火花。

(4) 计算每个火花的适应度值f。

(5) 根据(29)式对火花进行差分变异操作得到差分火花。

(6) 计算差分火花的适应度值f。

(7) 对烟花个体进行高斯变异操作。

(8) 根据烟花,火花和差分火花的适应度值f选择下一代的初始种群。

(9) 迭代次数完成得到目标函数的最终解f。

3 仿真与分析

对本文提出的模型和使用的算法进行实验仿真,并给出实验分析。实验所采用软硬件系统为i7-8700cup、8 GiB内存、Matlab2017b仿真软件和Windows10操作系统。

实验参数为在200 m×200 m的区域,随机分布20个节点,节点能量为100 kJ,存储空间为2 GiB,开始充电阈值为1 000 mA·h,开始数据收集阈值为400 Mibit,MC行驶速度及功耗分别为5 m/s、45 J/s。MC充电功率为7.5 W,MC对节点的数据收集速率为1.4 Mibit/s,传感器节点的数据传输功耗为3.5 W。

3.1 不同算法收敛情况比较

(1) 实验1。本实验分别采用DEFW算法、原始烟花算法(fireworks algorithm,FWA)、遗传算法(genetic algorithm,GA),迭代100次求得解的情况。首先生成一组数据:在实验设定区域内随机产生20个均匀分布的传感器节点，节点的能量消耗功率pi为[0.3,0.6]之间的随机数(单位为W),节点数据采集速率qi为[100,200]之间的随机数,单位为kibit/s;然后分别采用DEFW、FWA、GA算法对其进行调度并记录其迭代过程中的目标值,以观察3种算法的收敛性。DEFW、FWA、GA算法求解的MC单位能耗随迭代次数变化情况如图3所示。从图3可以看出,DEFW、FWA、GA算法求解一轮充电和数据收集操作路径时,DEFW算法收敛效果更好。

(2) 实验2。为了防止实验1具有偶然性,本实验采用实验1中的方法随机产生20组数据,然后对每一组数据分别采用DEFW、FWA、GA算法对其进行调度并得到最终的目标值求解结果。最终20组数据分别使用DEFW、FWA、GA算法求解的MC单位能耗对比如图4所示。

图4 20组数据使用3种算法求解的MC单位能耗对比

从图4可以看出,对20组不同数据分别使用DEFW、FWA、GA算法,DEFW算法求解目标值得到的平均MC单位能耗最低。

3.2 不同调度算法下网络能耗

本实验为了验证同一个WSN中采用DEFW算法在持续多轮对MC进行调度时MC单位能耗变化情况。首先采用实验1中的方法产生一组实验数据,然后分别使用DEFW、FWA、GA算法对其进行40轮的充电与数据收集调度,并求出每一轮的目标值ft。DEFW、FWA、GA算法对MC进行40轮的能量补充与数据收集调度下,MC单位能耗的变化情况对比如图5所示。

图5 3种算法调度下网络运行40轮MC单位能耗对比

从图5可以看出,第4轮操作之后使用DEFW算法的MC调度可以使得MC单位能耗明显低于使用FWA、GA算法调度得到的结果。

4 结 论

在WSN中传感器节点能量和存储空间受限情况下,如何保证传感器节点在正常工作的同时,降低整个网络的能耗是近年来WSN 领域研究的重点。本文通过S-ERDC算法来根据当前网络需求选择需要操作的节点,然后通过DEFW算法求解MC对节点的最优访问路径。仿真结果显示,本文提出的策略可以有效地解决WSN中能量与存储空间不足的问题,并且与FWA、GA算法相比能够明显降低传感器网络的能耗。