曾佑仟,王 茜,张景波,崔志华
(太原科技大学 计算机科学与技术学院,太原 030024)
在过去10年的时间里,物联网技术发展迅速.同时,WSNs作为物联网的重要组成部分也得到了各领域的广泛关注[1-3].WSNs由大量的无线传感器节点通过自组织或多跳的方式组成.目前,WSNs在许多领域得到了应用.如军事监控、医疗监控系统、环境监测等[4].虽然无线传感器节点具有低功耗、低成本的特点,但由于节点体积小、自身携带的能量有限,很难维持传感器网络的长期通信.同时在某些恶劣环境下,无法更换传感器节点的电池.因此,WSNs中节点能量有限是延长网络生命周期的关键.
为了延长WSNs的生存期,许多研究者提出了许多不同的策略.一方面,一些研究者采用更高效的路由协议来提高WSNs的能量利用率[5].虽然可以节约一些能源,但不能解决能源供应问题.另一方面,一些研究者提出通过收集环境能量来延长传感器节点的寿命[6].如波浪能[7]、风能、太阳能等,这些采集技术很难为传感器节点提供稳定持续的能量,能量转化率非常低.以上两种方法在一定程度上达到了延长网络生命周期的目的.然而,他们不能从根本上解决可持续能源供应问题.随着磁共振技术[8]的出现,提出了基于磁谐振耦合技术的无线能量传输,采用单个WCV周期性地为节点[9]提供能量从而形成了WRSNs.该技术克服了延长WSNs生命周期的困难,能够为节点提供稳定、可持续的能量.近年来,WRSNs已成为研究热点.大多数研究都是基于不同数量的WCV下的单目标或多目标充电规划.其中充电规划主要分为周期性充电和按需充电.
按照固定的时间间隔并根据固定的次序为节点补给能量,这种方式被称为周期性充电.Xie等人[9]提出了一种周期性充电方案,通过优化目标使休息时间与充电周期时间之比最大化得到了最优充电路径,将充电规划问题简化成TSP问题并证明哈密顿循环就是最短充电路径.Shi[10]进一步优化了动态多跳数据路由、WCV充电路径和充电计划,使WCV整修时间与充电周期的比例最大化.Lyu等人[11]提出了利用能量受限移动无线充电设备的周期充电方案,并采用混合粒子群优化遗传算法优化对接时间比.为了提高充电效率,提出了单WCV多节点充电模式.Xie等人[12]提出了一个一对多的充电方案,并证明了其近似最优解.但是使用这种充电方法将会造成许多能量的浪费.虽然周期性充电能够在一定程度上延续WRSNs的寿命,但该方案难以满足实际的充电需求,在实际应用中会浪费大量不必要的能源.
因此,为了提高充电效率,避免上述周期性充电所存在的问题,提出了按需充电策略.只有当节点的能量达到一定需求阈值时,才被认为该节点需要充电,称为按需充电.在小规模场景下,大多数充电策略都考虑了单WCV到单节点的充电方式.Kaswan等人[13]提出了一种规划充电路径的线性规划(LP)公式和重力搜索算法.Huang等人[14]设计了一种新的路径规划方案,称为基于路径规划的蚁群系统(ACO_PP),并在蚁群算法中引入虚拟电荷节点来优化移动汽车的路径.Dong等[15]提出了一种基于需求的充电策略,改进了聚类和选择算法进行节点分组和节点选择.然后,在文献[16]中,Zhao等人提出了由充电调度和充电时间分配组成的混合模型,并通过离线算法进行优化.在文献[17]中,Wang等人提出了k-覆盖冗余节点睡眠调度算法(KRSS)和面向距离和能量的充电调度算法(DECS),通过调度多辆充电车辆来减少节点冗余,防止节点能量耗尽.虽然结果表明这些方案是有效的,但利用多辆移动充电小车解决小规模问题无疑是一种资源浪费.基于以上分析,目前大多数充电计划存在以下弊端.首先,在充电计划中,只考虑一个或两个因素作为目标函数.其次,充电规划大多采用离线方式,且只考虑单个时间窗口.未考虑充电过程中路径规划中加入低能量新节点的多时间窗问题.因此,为了解决多时间窗问题,延长WSNs的生存期,本文充分考虑了充电规划的死节点数、距离、通信延迟时间和WCV的剩余能量4个目标,建立了动态高维多目标模型.
同时为了优化动态模型,考虑采用多目标进化算法[18,19].目前多目标进化算法已经被应用于各个领域.其中,采用了一些优化算法对各种路径规划进行优化[20-22].Xia等人[23]提出了多目标模型,采用改进的遗传算法对充电路径进行优化.在充电方案模型中,本文考虑了死节点数、距离、通信延迟时间和WCV的剩余能量4个目标并提出了高维多目标动态路径规划模型.多目标优化算法虽然可以解决高维多目标问题,但最优解集的多样性和收敛性较差.因此采用高维多目标优化算法是必要的.目前,高维多目标优化算法已经得到了深入的发展和研究[24-26].许多研究人员提出了许多高效的高维多目标优化算法[27].并在标准测试集和实际应用中取得了显著的效果.得到了均衡多样性和收敛性的最优解集[28].其中常用的经典算法有:GrEA[29]、NSGA-III[30]、SPEA2[31]、1by1EA[32]等.而与其他进化算法相比,SPEA2增强了pareto前沿的选择压力,可以筛选出具备更好收敛性和多样性的解集.采用SPEA2算法对多目标模型进行优化.而该动态模型考虑了多时间窗的动态问题并且采用整数序列编码.因此,本文在SPEA2中引入环境响应机制和改进的交叉和变异方法,以获得了具有更好多样性和收敛性的最优解集.
本文综合考虑了充电规划中的4个影响因素作为优化目标,并根据充电规划的动态特性构建了动态规划模型,并采用改进的SPEA2算法优化动态模型获得最优充电路径.通过仿真实验结果证明,提出的方法能够有效的提高节点的存活率并延长WRSNs的生命周期.
自WSNs发展以来,节点能量的有限性一直是一个令人困惑的问题.解决无线传感器节点能量有限的问题是能否延长WSNs生命周期的关键.随着磁共振技术的出现,利用WCV为节点提供能量,形成了WRSNs.如何有效规划WCV的充电路径成为研究热点.许多研究人员提出了多种规划的方法,部分研究只考虑了单个时间窗的问题,而没有考虑多个时间窗的情况下的路径规划.在WCV充电过程中,节点的能量仍是周期性消耗的,并且由于节点在二维平面上与基站的距离不同,节点的能量消耗率也不同.当达到需要充电节点的能量阈值时,向WCV发送充电请求,将节点加入充电路径方案.这个动态过程如图1所示.预先规划和再规划的路线分别用实心箭头和虚线箭头表示.
图1 动态充电规划过程
因此,为适应在WCV对规划节点充电过程中,由于节点能量周期性的损耗所导致的新的需充电节点的出现而引起的环境变化,建立了动态路径规划模型,将新的节点加入到充电规划中.动态模型由路径距离、剩余能量、通信延迟时间和死亡节点数4个目标组成.一般情况下,进化算法无法直接优化实际应用模型.本文中由于模型具有动态特性,考虑在充电过程中新节点加入充电规划,这将会引起决策变量维度的变化导致最优解集发生变化.因此考虑将环境响应机制和改进的进化策略引入SPEA2中,以克服动态环境下多样性和收敛性的不足.最后利用改进的SPEA2优化动态模型,以获得最优充电路径.其中,对动态模型结构的细节和算法优化过程将在后面详细的描述.
2.1 动态模型结构
2.1.1 无线传感器节点的能量消耗公式
在无线传感器网络中,节点的主要作用是对环境变化进行监测,并将监测数据发送给基站或接收来自基站或其他人的数据.而节点的能耗会受到各种因素的影响.例如,数据的大小、传输距离、气候等.因此,在本文中考虑将数据大小和传输距离作为影响节点能耗的主要因素.并将节点的能耗分为接收数据和发送数据两部分[33].它们由公式(1)和公式(2)表示.
接收数据所消耗的能量公式(1)为:
ENrecieve=ENRbit·datac
(1)
其中ENRbit代表接收每bit控制信息数据所消耗的能量,其值为50×10-13j/bit.datac是接收控制信息的大小,值为32bits.
公式(2)表示发送数据所消耗的能量如下所示:
(2)
其中ENS代表发送每bit数据所消耗的能量,50×10-13j/bit.ENI是节点自身能量损耗率,通常设置为10×10-13j/bit.传输数据的大小表示为datas.节点与基站之间的距离用L表示且距离阈值L0设置为30m.如果节点与基站之间的距离L在距离阈值L0范围内,则节点能量消耗是正常的;反之如果超出临界值范围,则节点能量损耗将会加剧.
2.1.2 动态充电规划模型
动态模型由4个目标组成.其中,动态模型的动态性主要体现在充电过程中增加额外的新节点.首先,第1个目标是路径的总长度.目标的价值越小越好.具体如公式(3)所示:
Object1:Distance(c(t),t)=
(3)
然后,第2个目标是WCV的剩余能量.目标值越大越好.WCV的主要能源消耗是行驶消耗和充电消耗.在充电过程中,随着新节点的加入,汽车的剩余能量会减少.具体内容如式(4)～式(7)所示.
(4)
(5)
eni,t=E0-t·(ENrecieve+ENsend)
(6)
ENmove(c(t))=ECcost·Distance(c(t),t)
(7)
其中ENcar是WCV自身所携带的总能量.节点的初始能量被设定为E0.ENmove和ENcharge分别代表WCV自身行驶所消耗的能量和为节点充电所消耗的能量.在t时刻第i节点的剩余能量为eni,t,ECcost代表WCV的行驶能量消耗率.
然后第3个目标是充电过程中死亡节点的数量.为了确保延长无线传感器网络的生命周期,需要减少死节点的数量.死亡的节点越少越好.同时死节点的数量也反映了规划路径的充电效率.具体细节如公式(8)和公式(9)所示:
(8)
(9)
其中DSi代表该节点是否死亡,如果值为1,则节点死亡;反之,值为0,存活.为了计算该节点是否死亡需要用到公式(8),通过节点的损耗率以及到达该节点所需的时间来计算节点剩余能量.
最后,第4个目标是通信延迟时间.当无线传感器节点低于数据传输的能量要求,不能完成正常通信时,就会造成延迟时间.因此,具体如公式(10)和公式(11)所示:
(10)
(11)
其中DTi为第i个节点的通信延迟时间.Tmove,i表示WCV到达节点时车辆在道路上行驶的总时间.Tcharge,i表示WCV到达该节点时,向通过的节点充电所需的总时间.Tconsume,i表示节点正常通信的最大时间.如果Tmove,i+Tcharge,i-Tconsume,i的值小于等于0,则节点可以保持正常通信,直到小车到达.否则会造成通信的延误.
综上所述,本文对可充电传感器网络下的动态充电规划问题,构建高维多目标动态优化模型,具体目标如公式(12)所示:
(12)
2.2 高维多目标动态路径规划算法
进化算法已经从单一目标扩展到多目标甚至高维多目标.其中当目标个数超过3个时被定义为高维多目标优化问题,而现有的多目标算法在解决高维多目标问题时,求解精度不足且算法多样性和收敛性较差.因此,考虑采用SPEA2高维多目标优化算法求解上述动态充电模型.在SPEA2中,采用了通过利用每个个体主导的解决方案的数量和个体密度信息来提高种群选择压力的适应度分配方法,并通过传统的交叉和变异算子更新种群.然而在求解动态充电模型时,存在如下问题:
1)由于决策变量的维度,即充电节点的数量会发生变化,SPEA2无法求解决策变量维数变化的模型问题.
2)由于决策变量采用整数编码方式,SPEA2采用传统交叉和变异方式更新种群将会导致编码冗余问题.因此本文通过引入环境响应机制和改进的进化策略,提出了改进的SPEA2算法.其中环境响应机制在环境发生变化时利用历史信息寻找变化的决策空间中的最优解来解决决策变量维度变化问题(详见2.2.1节).在种群进化过程中,改进的进化策略不仅能够解决编码冗余问题,还能够为种群提供新的搜索方向避免早熟收敛,从而在保证收敛性的前提下,提高种群的多样性(详见2.2.2节).
具体算法流程如算法1伪代码所示.首先初始化种群及相关参数,并计算适应度值.然后在算法1步骤4～步骤6中执行环境响应机制.通过锦标赛选择法选出N个个体放入种群P1,并利用步骤8的改进的进化策略更新种群P1,然后合并种群并选出N个个体作为新的父代种群,迭代循环直到达到终止条件.
算法1.改进的SPEA2算法流程
输入:种群大小N,最大迭代次数tmax
输出:最优解集合Pt+1
1.初始化产生种群P0,t=0;
2.计算每个个体i的适应值Fi;
3.Whilet≤tmaxdo
4.if环境变化then
5. 采用环境响应机制;
6.endif
7. 利用适应值Fi和锦标赛选择法从P0中选出N个个体放入P1;
8. 利用改进的交叉算子和变异算子更新种群P1;
9. 合并种群R=P0∪P1′;
10.fori=1:|R|do
11. 计算种群R中每个个体i的适应值Fi′;
12.ifFi′<1then
13. 将满足条件的个体放入Pt+1中;
14.endif
15.endfor
16.if|Pt+1| 17.Pt+1=[]; 18. 选择前N个个体放入Pt+1中; 19.elseif|Pt+1|>N 20. 利用阻截算子除掉种群Pt+1中冗余的个体; 21.endif 22.t=t+1; 23.endwhile 24.returnPt+1; 2.2.1 环境响应机制 在充电过程中,由于节点能量周期性损耗,充电路径上会增加新的节点,如图2所示.为了适应环境变化,保证种群的多样性和收敛性,提出了环境响应机制. 图2 交叉算子流程 当环境发生变化时,一般算法只能重新生成新个体,浪费历史信息.因此,为了充分利用历史信息,本文提出了一个环境响应机制.当检测到环境变化时,保持环境变化前的最后一代种群,随机插入新个体.该方法可以提高新环境下种群的多样性,从而确保能找到全局最优解,避免陷入局部最优解.具体过程如算法2伪代码所示. 算法2.环境响应机制 Input:种群P={p1,p2,…,pN},种群大小N,新节点集合C={c1,c2,c3,…,cn},在每个决策变量中固定节点数量fixed(fix1,fix2,…,fixn) Output:种群P′ 1.if环境变化then 2.P′=[]; 3.fori=1:Ndo 4.forj=1:|C|do 5. 从fixi到N的范围内,随机选择一个位置; 6. 将新节点cj插入pi中并获得新的个体pi′; 7.P′=P′←pi′ 8.endfor 9.endfor 10.endif 11.returnP′; 2.2.2 改进的进化策略 在动态模型中,采用整数序列编码方法作为决策变量的编码方式.整数序列编码方法虽然解决了路径编码问题,但也提出了一个新的问题.在SPEA2中,采用真实杂交和突变的方法更新种群.然而,在本文的动态模型中,决策变量是整数序列,该序列中的数字不能是冗余的.因此,本文设计了整数交叉和变异算子.具体介绍如下: 1)基于概率的整数交叉算子 如果随机数不满足交叉概率,则跳过交叉算子.相反,如果它满足,则执行以下操作.首先,从个体中选择两个组节点,组的大小为两个节点.然后,交换两组数字的位置.最后,以节点的剩余能量作为排序的指标,并用该指标对两组节点进行排序.具体过程描述如下: 例如,{10,6,11,2,5,8,3,9,1,7,4}.首先,在尚未充电的节点中部随机选取两组节点.交换位置后,根据节点的剩余能量对节点组进行排序,获取新的充电路径.这种方法有利于快速搜索局部区域的最优解集.原理图如图2所示. 2)基于概率的整数变异算子 如果随机数不满足变异概率,则跳过变异算子.相反,如果它满足,则执行以下操作.由于充电路径为整数序列,为了保证种群的多样性,保证新节点加入时适应新环境,本文采用了头尾交换的方式,其余操作符与交叉操作符相似.具体操作如图3所示. 图3 变异算子流程 虽然种群是通过交叉和变异操作来更新的,但对某些个体来说,这两种操作有时会被跳过.这些个体是从亲本种群中选择出来的.因此,为了避免多样性的丧失和过多的重复个体,这些个体被随机再生. 本文使用数学软件MATLAB R2016b进行仿真实验.在尺寸为L×L的二维空间中构造传感器网络.无线传感器节点随机均匀分布在各节点之间,如图4所示.仿真场景如图1所示,具体参数设置如表1所示. 图4 节点在无线传感器网络中的分布 表1 参数设置 本文考虑到在WCV充电过程中,由于节点依然在周期性的通信且能量根据公式1和2周期损耗,而导致在原充电规划之外,新的需要充电的节点的产生.且每个节点的能量损耗是不同,每个周期中新加入的节点数量是随机的.因此,在本次实验中本文考虑如下3组对比实验:第1个是考虑不同进化算法与Improved SPEA2的对比,然后独立运行30次并每次独立运行保存10个周期的实验结果,计算每个周期的平均目标值,并分别从节点存活率和WCV行驶距离两个角度分析,通过对比每个周期下4个目标值分析不同算法性能.第2个是考虑在不同规模节点的情况下,分析了不同算法在不同规模下对实验结果的影响.第3个是为了证明提出的动态充电模型的有效性,考虑将动态模型与静态模型进行比较.下面将对实验结果进行详细分析. 3.2.1 性能指标 在对比实验分析中,采用死节点数作为评价充电方案效率的主要指标.为了更直观地反映充电效率,将该指标转化为节点存活率.同时,该值越大,传感器网络的生存期越长.具体变换公式如下: (13) 3.2.2 静态模型与动态模型之间的对比 为了证明动态模型的有效性,本文考虑与静态模型进行对比,并使用与动态模型相同的目标和参数.而静态模型与动态模型中没有考虑到新节点出现后的再规划过程.因此通过对比在每个周期下的目标值,如图5所示.它们表明,对于动态模型和静态模型,每个目标值在初始的第1个循环中大致相同.这是因为在初始的第1个循环中充电路径没有新增节点.但是,随着充电规划中加入新的节点,动态模型和静态模型中各目标的值可以明显区分.这是因为当在充电路径中添加新节点时,动态模型中会使用历史信息对充电路径进行动态规划,而静态模型中只有在第1个规划路径完成后才能对充电路径进行重新规划.因此,随着新节点的不断增加,动态模型与静态模型之间的性能差距也越来越明显.实验结果表明,该方法在动态模型中延长无线传感器网络的生存期和减少死亡节点方面具有较好的性能. 图5 动态模型和静态模型的性能比较 3.2.3 不同进化算法之间的对比 在对比实验分析中,本文采用了ImprovedSPEA2进化算法,并将其与GrEA、1by1EA、SGA-III进化算法进行对比.然后利用节点的平均存活率,通信延迟时间,路径距离以及WCV剩余能量来验证算法的性能.实验对比结果如图6和图7所示. 图6 对应于每个算法存活率最高的个体的4个目标值 图7 对应于每个算法路径距离最短的个体4个目标值 一方面,从无线传感器网络的角度对延长节点生命周期进行实验分析,如图6所示.在不同算法中选择每个周期中存活率最高的个体进行比较.图6(a)显示了不同算法提高节点存活率的性能.由图6(a)看出,随着需要充电的节点不断加入,ImprovedSPEA2动态规划充电路径的节点存活率不断提高.虽然GrEA与ImprovedSPEA2相比可以获得相当的存活率,但SPEA2在整个过程中比其他算法具有更高的存活率.图6(b)为通信延迟时间,当节点能量达到一定阈值时,节点将无法与基站进行数据通信.从图6(b)可以看出,在一开始,ImprovedSPEA2和GrEA具有可比性.而在第5个周期之后,ImprovedSPEA2的延迟时间相比其他算法更低.这也意味着规划的充电路径是有效的.图6(c)和图6(d)表示WCV的距离和剩余能量.由于本文是从节点生命周期延长的角度考虑问题,因此规划的路径往往会延长节点的生命周期.而多目标优化会牺牲一些其他目标来获得优选解.虽然这两个目标不能得到ImprovedSPEA2的最优解,但可以发现这两个目标的解集在可接受的范围内.因此,ImprovedSPEA2可以通过优化充电路径,有效延长无线传感器网络的生命周期,提高WCV的充电效率. 另一方面,从WCV的角度对提高能源利用率进行实验分析,如图7所示.在不同算法中选择距离最短的个体进行比较.从图7(a)可以看出,与其他算法相比,1by1EA算法可以得到距离最短的最优路径.图7(a)中最短距离的值优于图7(a)中最短距离的值.但整体生存率低于图6(a). 因此,多目标算法在选择首选解时会影响其他目标.虽然从图7(a)中,ImprovedSPEA2的趋势处于第2位,但实验结果不能从一个方面进行分析.由图7(b)、(c)、(d)可知,距离最短的个体对应的其他3个目标值,ImprovedSPEA2的生存率和延迟时间都优于其他算法,剩余能量也处于中等水平.因此,从MCV的角度使用ImprovedSPEA2也得到了不错的实验结果. 3.2.4 不同规模WRSNs下的对比 在本文中,主要考虑小规模场景下的路径规划.为了更好地证明动态模型和改进后的SPEA2的性能,采用不同规模的节点数,包括100节点、125节点、150节点、175节点、200节点、225节点、250节点.实验结果如表2所示. 表2 不同规模下的节点存活率 通过分析表2 ,初始节点存活率随着节点规模数的增加而降低.但在相同规模WRSNs下,传感器节点的存活率随着周期的迭代而增加,在第10个周期可以得到较好的存活率值.在表2中,每个循环结果的最佳值用黑色粗体标记.实验结果表明,ImprovedSPEA2可以获得较好的存活率,GrEA也可以获得与ImprovedSPEA2相差约1%的存活率.然而,最糟糕的是1by1EA,与ImprovedSPEA2的差异约为3%～5%.因此,可以利用ImprovedSPEA2来规划有效的充电路径. 为了规划有效的充电路径,延长无线传感器网络的生存期,本文设计了一个以最小化路径距离、死亡节点数量、通信延迟以及最大化WCV剩余能量为目标建立了一个高维多目标动态模型.然后,将改进的交叉和变异算子以及环境响应机制引入到SPEA2中,以适应编码模式和变化的环境.动态模型通过改进的SPEA2进行优化.通过动态模型与静态模型的对比实验结果表明,动态模型能更有效地提高无线传感器网络的生命周期.通过比较不同算法求解动态模型的结果,改进的交叉和变异算子提高了模型的多样性和收敛性.通过环境响应机制,提高了全局搜索的性能,可以更快地适应新环境.同时,为了测试模型和算法的处理能力,本文考虑在不同规模WRSNs下进行对比.最后,实验结果表明所提出的动态模型以及改进的SPEA2能够有效提高节点存活率,延长无线传感器网络的生存期.然而目前所提出的方法应用在大规模WRSNs中,单个WCV难以满足充电需求,将会导致诸多节点难以及时得到能量补给,因此在未来工作中将会考虑采用多个WCV协同充电解决大规模WRSNs问题.
3.1 仿真环境设置和实验介绍
3.2 性能对比和分析
