无线可充电传感器网络充电路径优化

俞立春， 吕红芳， 何 力， 李俊甫

(上海电机学院 电气学院， 上海 201306)

无线可充电传感器网络中，网络节点之间收集和传递数据都需要消耗能量，大部分传感器节点体积都很小，并且电池的能量密度也不高，导致节点所携带的电量有限，所以存在节点能量耗尽而停止工作，从而影响整个无线传感器网络的生命周期。目前很多学者把降低网络的维护成本，延长网络生命周期，设计快速有效的充电方式，当成保持网络节点正常运行的一项重要研究任务。文献[1]在解决无线可充电传感器网络中使充电车充电服务吞吐量最大化的问题上，采用了K-means算法来解决。文献[2]利用贪心思想有效地解决了无线可充电传感器网络中的充电车信息收集以及充电路径优化问题。文献[3]为优化无线可充电传感器网络节点在充电前的剩余能量以及充电车的充电路径的问题上作出了卓越贡献。文献[4]在研究传统网络基础上研究了基于动态请求的无线可充电传感器网络，移动充电车自身可传递和收集网络节点的充电请求信息，并独立完成充电任务。文献[5]考虑所有无线可充电传感器网络节点不因能量耗尽而停止工作的前提下，把网络节点的路由以及充电车的充电路径结合在一起，研究了无线可充电传感器网络中的通信系统以及充电调度系统的总能耗最小化问题。文献[6]研究了基于动态请求式的无线可充电传感器网络中，存在一辆携带可接收无线信号装置的充电车，具备实时的接收网络节点的充电请求命令，且可以实时动态的给出相应的充电任务策略。文献[7-8]通过无线认证感知平台(Wireless Identification and Sensing Platform,WISP)研究了无线可充电传感器网络的充电调度问题，在无线射频识别信号范围之内，充电车可以为网络节点进行充电服务。

本文研究的是无线可充电传感器网络在静态模式下，以充电车电池所携带的能量和周期作为限制条件，使充电车电池能量利用率达到最大化，建立单辆充电车的充电模型，将能量利用率最大化问题转换成最优路径的问题，提出基于精英策略的蛙跳算法对充电路径进行优化，并利用Matlab仿真工具进行仿真实验，验证算法的有效性。

1 问题描述

1.1 网络模型

将无线可充电传感器网络看成1个二维平面[9]，布置1个固定的基站S，能够收集网络中各节点的信息，有n个随机分布的传感器节点，任意两个节点之间的边看成1个树杈，1个节点可以生成多个树杈，如图1所示。

图1 无线充电传感器网络示意图

(1)

式中：Eelec为接收或发送单位数据消耗的能量；εfs为自由空间模型中功率放大器能耗参数；εmp为多路径衰减模型中功率放大器能耗参数；d0为事先设定的两种模型的传输距离的阈值。

接收k比特消耗的能量为

ERx=kEelec

(2)

则传感器节点xi的能耗为

(3)

1.2 充电模型

在无线可充电传感器网络中，所有的网络节点带有一块可充电电池作为能量接收装置[12]，其能量有限，最大存储量Gi，传感器节点在信息来回传递过程中都会消耗能量，假设Emin为节点能量的临界阈值，当节点剩余能量值降低到Emin以下时，则会向基站S发出充电请求指令M，M={xi,tri,ER,pi,Gi}，其中xi是申请需求的节点，tri是节点发送充电请求的时刻，ER是节点的剩余能量，pi是节点能耗功率，Gi是节点能量的最大存储量。当基站收到节点充电申请时，会立即派遣一辆充电车去给节点充电，直到把节点能量充满为止。若是有其他节点在当前充电过程中发出充电请求，小车会自行收集信息，依次为下一节点充电，最后回到基站补充能量，此为一个充电调度。

在保证所有申请节点不停止工作的前提下，使充电车能量利用率最大化。能量利用率最大相当于在行驶中充电车行驶路径最短，建立一个单充电车为无线可充电传感器网络的充电模型如图2所示。假设小车携带一个容量为Em的电池，可供自身行驶和为节点充电，小车可以为网络中的节点依次充电，行驶速度为vc(匀速)，为节点充电的功率为pn，行驶过程中的消耗功率为pm，由于小车自身携带的能量是有限的，所以小车最大一次的充电返程时间看作一个充电周期为T。

图2 充电模型

考虑在静态模式下的传感器网络中，经常出现部分传感器节点由于未及时充电，而暂停工作，影响网络的稳定性。因此,本文考虑在基站收到部分节点充电申请，小车再为这些节点充电，在小车能量有限的情况下，给予所需节点最大化充电，同时选择最优路径，使得充电车能量利用率最高。

1.3 最大化能量利用率公式化

将传感器网络看成一个赋予权值的无向树图Z=(X,Y)，充电车的电池总能量Em，静态模式下，要使充电车的能量利用率最大化问题就是求解一条最优的充电路径Dc问题，小车所充过电的节点的集合为Vc(Vc∈V)，小车根据充电路线逐次为节点充电，最后回到基站补充能量，并使得充电车电池的能量利用率达到最大，且充电车给节点所充的总能量和小车行驶所需要的能量之和不能超过小车自身携带的电池能量,则该问题优化目标为

(4)

约束条件为

en(c)+Ec≤Em

(5)

式中：en(c)为充电过程中所有节点所充能量的总和；Ec为充电车在给节点充电过程中行驶所消耗的总能量。

eni=Gi-ER

(6)

式中：eni为单个节点需要充的能量。

(7)

(8)

一次充电往返过程的时间限制在周期T以内

(9)

式中:eni/pn为充电车为节点xi充电的时间。

节点不会因为能量用尽而失效，所以有

tri≤ti≤tdi

(10)

式中：ti为小车开始给节点xi充电的时刻。

tdi节点在能量耗尽前小车为节点开始充电的最大时间

tdi=tri+ER/pi

(11)

所充电的节点集合应该属于整个传感器节点的集合为

Vc⊆V

(12)

根据以上的约束条件来求出一条最优路径，而一般多约束条件求解充电车最优充电路径问题都是较难的旅行商问题(Travelling Salesman Problem，TSP)[13]。因此,本文基于精英策略的蛙跳算法求解出一条最优的路径。

2 算法概述

2.1 蛙跳算法

蛙跳算法[14-16](Shuffled Frog Leaping Algorithm，SFLA)是一种模拟青蛙觅食行为的过程，通过群体之间的相互合作与竞争，来实现群体进化的目的。以函数的最小值为例来说明SFLA的基本步骤，设群体青蛙的种群规模为M，并且在D维空间中第i个个体的坐标假设为:xi=(xi1,xi2,…,xiD),计算个体的适应值。接着从大到小依次排列，然后把整个种群划分为G个局部子群，每个局部子群里面有N只青蛙，种群规模表示M=G×N,在降序排列的过程中，平均分配排列好的个体到G个局部子群中去，在指定的局部迭代数Ne内完成搜索，若满足全局最大迭代次数，则完成此次的搜索，输出全局最优值，否则将全部青蛙混合重新计算。

2.1 算法的改进策略

在传统SFLA中，局部子群的最差青蛙只会向局部子群最优的青蛙学习，本文为了使最差的青蛙也向周围的较好的青蛙学习，提高了搜索速度，并且在学习的过程中保证了自身的不退化。因此,本文引入了精英策略，即改进的蛙跳算法(Accelerated Shuffled Frog Leaping Algorithm ，ACSFLA)，表示为

D(t)=η·rand()·[Xb(t)-Xw(t)]

(13)

式中：D(t)为更新的步长;η为变异算子;rand()为[0,1]之间的随机数；Xb(t)为局部子群里最优适应解;

(14)

(15)

rmax为最差青蛙到本组较好青蛙的搜索距离；θ为(0°,360°)之间的随机数。

针对SFLA进化过程中，全局最优的青蛙几乎不进化的问题，并且大量的实验表明在进化过程中，全局最优的地位会保持很多代，使算法的寻优速度变慢，且易出现早熟的现象。因此,本文在进化过程中，引入了Minkowski距离，使全局最优的青蛙不仅向局部子群最优青蛙学习，也向局部子群除了最差青蛙以外的其他青蛙学习，并且在学习过程中会向着多个方向，保证最优青蛙的质量，同时加快了寻优速度:

Xg(t)=c·rand()·M(Xg(t),Xi(t))

(16)

式中：Xg(t)为全局最优解;c为更新的权值,c为[0,1]的随机数，是全局最优青蛙向局部子群中其他青蛙和局部子群中最优青蛙的学习因子；Xi(t)为局部子群内最优青蛙和局部子群内除了最差青蛙以外的青蛙。

2.2 算法求解路径流程

假设事先知道所有提出申请的网络节点的位置、距离和能量等信息，让小车在能量约束的条件下，陆续给需要的节点充电，最后能够回到基站，且将充电车的行驶时间控制在T以内，使得充电车的电池利用率最大化。通过改进的蛙跳算法对充电路径进行优化，其算法步骤如下。

(1) 初始化n个网络节点坐标，计算各个节点之间的距离，生成距离矩阵。

(2) 设置算法参数，产生初始种群，将种群中的每个青蛙个体看成一条遍历的路径。

(3) 对于每个个体青蛙的好坏程度用适应度函数值来评价，本文中将充电车的遍历路径长度当作适应度函数值。

(4) 计算局部最优值和最差值，调整最差值，将最差青蛙向其他种群最优青蛙学习，根据式(14)～(15)对个体进行更新。

(5) 局部达到预定的迭代次数之后，输出局部最优值，并与其他种群中的局部最优值进行对比。达到全局迭代次数之后，输出最优值，从而得到一条最优的路径。

算法程序流程如图3所示。

3 实验结果与分析

3.1 实验环境

本文设计的无线可充电传感器网络规模为100 m×100 m，在此区域内随机分布40～200个传感器节点，基站S位于网络中心(50,50)。网络中有一辆移动充电车，充电车电池总能量为50 kJ，周期值为1 000 s，充电车的行驶速度为3 m/s，充电车的充电效率为10 J/s，小车行驶平均消耗的功率为5 J/s，每一个节点最大的能量值为300 J，节点的Emin=80 J，发送数据能量消耗100 nJ/bit，接受数据能量消耗100 nJ/bit。

图3 程序流程图

根据以上设置的参数，进行仿真实验。仿真实验在win10系统、intel酷睿系列的CPU;8 GB内存、500 GB硬盘的电脑上的MATLAB 2014b下仿真，以SFLA和ACSFLA作对比。除此之外，再与蚁群算法[17](Ant Colony Optimization, ACO)比较。ACO是一种模仿蚂蚁在觅食过程中的行为，其算法思想为在充电车选择充电节点的过程中，任意选择一条路径并留下信息素，信息素的浓度越高，蚂蚁选择这条路径概率也越大，如此反复从而选择出最优的路径，是较早的路径优化智能算法。

3.2 性能指标

针对ACSFLA，本文采用两个标准来验证算法的有效性，其中一个为本文的优化目标，另外一个为能量利用率。

在一次充电过程中，充电车对节点充电的总能量与充电过程中所消耗的总能量之比即能量利率用为

Δ=en(c)/[Ec+en(c)]

(17)

3.3 仿真结果分析

通过对网络节点的点位随机分布，对40～200节点区域进行多次仿真实验。为了让求解的最优值更加有效性，取多组优化后最优值的平均值。以下为仿真结果分析。

图4为节点数的40～200时SFLA,ACO和ACSFLA优化后的路径距离曲线图， 从曲线变化上面来看，在节点数量少的时候，SFLA和ACSFLA表现都很优越，但在节点数增大，明显看出SFLA所求得结果并不是很理想，当节点数增加到140个之后，SFLA求解的充电路径最长，而ACSFLA求解的路径一直都比其他两种要短。

图4 优化后充电路径曲线图

图5为SFLA与ACSFLA在节点数为40～200时充电车能量利用率的变化曲线。从图中可以直观看出，随着传感器节点的增加，充电车能够为更多的节点提供充电服务。因此,充电车能量利用率也不断的变高。

图5 能量利用率变化曲线

在节点数很少时，ACO优化后的充电车的利用率最低，随着节点数量增加，曲线变化逐渐趋近于ACSFLA。120节点和200节点3种算法的优化后的能量利用率比较见表1。在节点数增加到120时，ACSFLA相较于SFLA能量利用率提升了3.1%，而ACO优化结果依然不理想。当节点数增加到200时，ACSFLA相较于ACO的能量利用率提高了7.1%，而此时SFLA能量利用率最低，这是由于SFLA后期时，陷入了局部最优，导致寻优的精度不高。而ACSFLA优化后的能量利用率始终比其他两种算法高。综上所述，验证了本文改进算法的有效性。

表1 3种算法优化后的能量利用率比较

4 结 语

本文研究了无线可充电传感器网络中充电调度问题，针对实际情况，考虑到充电车携带的能量有限，在研究过程中将充电车的电池能量利用率转换成求解最短路径，利用ACSFLA对其进行优化。在小规模网络中，用SFLA,ACO和ACSFLA进行仿真，结果表明，通过ACSFLA得到的路径最短，能量利用率最高。