基于改进樽海鞘群的障碍物环境WSN节点覆盖优化

张 永,韩 睿,徐华荣,王文浩,王肖丛,孙田弋,孙御骥

(1.国网浙江省电力有限公司,浙江杭州 310000;2.国网浙江省电力有限公司电力科学研究院,浙江杭州 310000;3.南京南瑞信息通信科技有限公司,江苏南京 210000;4.山东大学微电子学院,山东济南 250000)

0 引言

无线传感器网络具备成本低、低功耗、部署灵活的优势,在智能控制、自动化工程、网络自动化等诸多领域得到了广泛应用[1]。传感器节点部署及网络覆盖是决定网络感知和通信质量的关键,直接影响网络生存时间和网络管理效率[2-3]。为了满足覆盖需求,将大量WSN节点随机抛洒于监测区域,会导致覆盖盲区、节点密度过高和冗余节点多等问题,覆盖盲区会降低区域监测质量,节点密度过高和冗余节点多则会导致过多数据转发的能耗浪费、通信拥塞、冗余数据多等问题,这些问题会降低网络可靠性和增加节点能耗。因此,优化WSN节点部署,提高监测区域覆盖率具有重要意义。

将WSN节点部署与智能优化算法结合,可以利用智能优化算法强大的随机启发式搜索机制加快节点覆盖寻优过程。文献[4]利用混合遗传与差分进化对WSN节点覆盖优化问题求解,最大化节点覆盖率。文献[5]利用虚拟力粒子群算法优化WSN覆盖后将覆盖率提升了5个百分点。文献[6]利用改进人工蜂群算法优化WSN节点部署,网络覆盖率得到了改善,但依然有较多覆盖盲区。文献[7]利用改进灰狼优化算法将WSN节点覆盖率提升了4个百分点,但仍存在分布不均匀。文献[8]利用自适应动态混沌量子粒子群算法将覆盖率优化至90%。鲸鱼优化算法[9]、果蝇算法[10]等也均应用在了WSN节点覆盖优化问题中。然而,智能算法本身也存在寻优精度上的不足,尤其容易造成搜索与精细开采过程失衡和带来局部最优的缺陷。同时,以上研究考虑的场景均是无障碍物简单环境的节点覆盖优化,未讨论监测区域内存在复杂障碍物的节点覆盖优化问题,实用性有限。

樽海鞘群算法SSA是一种新型智能优化算法[11],其结构简单、参数少,能够有效提升寻优精度,在图像分割[12]、特征选择[13]、作业调度[14]等问题上得到广泛应用。但标准SSA算法还存在着早熟收敛和求解精度低的不足。为了更好地解决障碍物环境中的WSN节点覆盖优化问题,本文将设计一种多策略融合改进樽海鞘群算法MSISSA。为了提高SSA的寻优性能,设计模糊逻辑种群角色调整机制,对领导者种群规模动态调整;设计多项式变异扰动机制对跟随者变异,增强跟随者局部随机搜索能力;设计拓扑对立学习机制生成领导者拓扑对立解,充分挖掘区域内的精英位置信息。在复杂障碍物环境下以WSN节点覆盖率最大为目标,利用改进算法优化WSN节点覆盖问题,求解节点最优部署位置。并开展实验验证改进算法的性能。

1 樽海鞘群算法SSA

樽海鞘群算法种群由领导者和跟随者组成,并组成链式结构。链首个体为领导者个体,其他个体均为跟随者个体。跟随者在领导者的牵引下搜索食物源。令N为种群规模,D为搜索空间维度,SSA中樽海鞘个体的位置信息存储于N×D的二维矩阵内,个体i可表示为Xi={xi,1,xi,2,…,xi,D},xi,j表示个体i在j维度上的位置,j=1,2,…,D。令种群的搜索目标为F,领导者的位置更新方式为

(1)

式中:[lbj,ubj]为个体在j维度上的搜索边界值;Fj为搜索目标的j维度值;x1,j(t+1)为链首领导者的j维更新位置;t为当前迭代次数;c2、c3为均匀分布随机数,c2、c3∈[0,1];c2控制移动步长,c1用于搜索算法的全局搜索与局部开发转换。

c1的定义为

(2)

式中:t为当前迭代次数;Tmax为最大迭代次数。

跟随者的位置更新方式为

(3)

式中:xi,j(t)、xi,j(t+1)分别为个体i(i≥2)在j维度上的原位置和更新位置;xi-1,j(t)为相邻个体的j维位置。

2 多策略融合改进樽海鞘群算法MSISSA

2.1 基于模糊逻辑的种群角色调整

SSA算法中,领导者代表着种群的优势群体,但算法迭代搜索过程中,领导者的樽海鞘种群规模是维持不变的。然而,算法迭代早期,较大规模领导者有利于SSA算法进行更充分的全局搜索,加快算法的收敛速度;而到了算法迭代后期,应更侧重于局部开发,此时领导者规模应该随之减少,以便于SSA算法进行精细开发,提高算法的收敛精度。

为了对领导者种群规模进行动态的自适应调整,MSISSA算法引入一种基于模糊推理系统的领导者个体数量占比非线性更新机制。模糊推理系统是以模糊逻辑为理论基础,实现多输入变量与单输出变量间复杂非线性映射关系的方法,其结构如图1所示。定义领导者占比因子的模糊推理系统的2个输入变量为种群多样性φ和算法迭代阶段κ。其中,种群多样性φ表示每个樽海鞘个体与当前最优解个体间的欧氏距离,定义为

图1 模糊推理系统

(4)

式中:N为种群规模;D为搜索维度;xi,j(t)为迭代t时个体i在维度j上的位置;xbest,j(t)为当前迭代最优解的j维度位置。

由此可见,种群多样性φ能够描述种群个体在搜索空间内分布的分散程度。个体间距离越大,则个体位置相对越分散,其种群多样性也越好;反之,个体间距离越小,种群越趋于集中,种群多样性也越差。

迭代阶段κ表示算法当前迭代次数与最大迭代次数之比,定义为

κ=t/Tmax

(5)

式中Tmax为算法的最大迭代次数。

输入变量种群多样性φ和迭代阶段κ在模糊推理系统中的隶属度函数设计如图2所示。

(a)输入变量为迭代阶段

种群多样性φ以3个隶属度函数分为Low、Medium和High 3种状态,迭代阶段κ以3个隶属度函数分为Early、Medium和Late 3种状态。为了对领导者占比因子进行精确输出,如图2(c)所示,将其以5个隶属度函数分为Very_Small、Small、Medium、Big和Very_Big 5个阶段。

为了实现模糊推理系统中对领导者占比因子的精确输出,还需要设计合理的模糊规则。SSA算法迭代前期,领导者规模可以偏大,以求更充分的全局搜索;而随着迭代进行,领导者规模应逐步减小,使算法侧重于精细开发。同时,还应考虑种群多样性对领导者占比因子的影响。当种群多样性较差时,表明此时个体趋向聚集,此时应增加领导者占比提高算法的全局搜索能力;当种群多样性较好时,则可适当减小领导者占比。综上,设计表1所示模糊推理系统的模糊规则。

表1 模糊规则

结合表1所示的模糊规则,经过去模糊化即可得到模糊推理系统实现的输出领导者占比因子,如图2(d)所示。可见,在不同种群多样性和算法迭代阶段状态下,领导者占比因子会进行自适应动态调整,使得算法在迭代前后期以不同能力的搜索和开发性能进行目标搜索。

2.2 多项式变异扰动

SSA算法的迭代后期,种群个体会逐步趋近于当前迭代中搜索到的最优解。若该最优解为局部最优解,势必导致算法得到局部最优。为此,MSISSA算法引入一种多项式变异算子作用于跟随者种群,使SSA算法具备一定的局部随机搜索能力,在迭代后期加速算法向最优解收敛的同时,使种群维持一定多样性,避免生成局部最优解。多项式变异表达式为:

xk+1=xk+δ·(uk-lk)

(6)

(7)

式中:lk、uk分别为搜索区间的下限值和上限值;xk、xk+1分别为原个体位置和变异后个体位置;δ为多项式变异算子;μ为随机量μ∈[0,1];ηm为分布指数;且:

(8)

结合多项式变异的扰动方式具体为:算法迭代开始后,从算法第11次迭代开始,若种群连续10代搜索的最优解适应度均未发生更新,此时可视为算法得到局部最优解而无法跳离,需要利用多项式变异算子对跟随者种群个体进行扰动,增加种群多样性,拓展种群的搜索范围,从而增加算法跳离局部最优解的概率。个体变异公式为

xi,j(t+1)=xi,j(t)+δ·(xub-x1b)

(9)

式中:xi,j(t)、xi,j(t+1)分别原位置和更新位置;xlb、xub分别为搜索区间的下限值和上限值。

2.3 拓扑对立学习策略

拓扑对立学习TOBL[15]是一种基于对立学习OBL的增强优化策略,能够显著提升算法的搜索能力。对立学习仅生成一个与原始个体完全反向的对立个体,而拓扑对立学习可生成2D个备选个体。

令在D维空间内一个点xi=(xi,1,xi,2,...,xi,j,…,xi,D),其拓扑对立点Ti=(Ti,1,Ti,2,…,Ti,j,…,Ti,D),定义为

(10)

式中:xbest,j为当前迭代最优解的j维度位置;oi,j为对立点i的j维度位置,定义为

oi,j=lbj+ubj-xi,j,j=1,2,…,D

(11)

式中lbj、ubj分别为搜索空间的下限值和上限值。

为了提高SSA算法的寻优能力,MSISSA算法引入拓扑对立学习机制,在樽海鞘种群更新位置之后,先利用式(11)生成每个个体的对立点,再比较最优解与该对立点以及原个体间的曼哈顿距离。若对立点位置与最优解距离最小,则表明该对立点为个体的拓扑对立点。如图3所示为三维空间内一个种群个体潜在的拓扑对立点位置。

图3 三维空间拓扑对立点分布

计算个体的拓扑对立点是为了得到适应度最优的个体,以使得种群对搜索空间进行更充分的全局搜索,进而提高算法的寻优效率。计算个体的拓扑对立点后,对其适应度进行评估,若其适应度优于原个体位置,则进行交换。择优交换方式为

(12)

式中:f(xi(t))、f(Ti(t))分别为原个体及其拓扑对立点的适应度值;xi′(t+1)为择优交换后的解。

图4为MSISSA算法的执行流程。

图4 MSISSA算法流程

3 基于障碍物环境的WSN节点覆盖优化

3.1 WSN节点覆盖模型描述

在二维平面区域S=L×W内部署若干WSN节点,区域内存在若干个障碍物,且整个待监测区域被离散化为L×W个像素点。令WSN节点集合N={n1,n2,…,nk},k为WSN节点数量,障碍物集合O={o1,i,o2,i,…,oj,i},j为障碍物数量,i为障碍物类型。令(xk,yk)为WSN节点nk的坐标,其感知半径为r,通信半径为R,且R=2r。选用概率感知模型决定区域内某个像素点是否能被WSN节点所覆盖。令待检测点g的坐标为(xg,yg),则WSN节点nk对g点的感知概率为

(13)

式中:d(nk,g)为WSN节点nk与目标点g间的欧氏距离;re为WSN节点在障碍物环境下感知能力的不确定性度量值,0

图5为WSN节点的感知模型,区域g1内的目标点被WSN节点nk感知的概率为100%,区域g3以外目标点确定无法被nk所感知,区域g2内的目标点的感知概率则由感知因子λ、β决定,感知概率为0～100%。

图5 感知模型

d(nk,g)以欧氏距离方式定义为

(14)

由于一个目标点可以同时被多个WSN节点所覆盖,可将整个WSN的联合感知概率定义为

(15)

式中p(nk,g)为传感节点nk对点g的感知概率。

则整个区域的覆盖率为

(16)

式中L、W表示待监测区域的长度和宽度。

3.2 避障设计

复杂环境中一般在待监测区域内存在障碍物的限制,若WSN节点部署位置落入障碍物区域,则需要对节点进行移动重部署。WSN节点部署过程中需要针对目标函数设计避开障碍物的覆盖优化策略。为了避免选择不合适的约束条件而导致WSN节点部署中出现聚集性,从而导致区域覆盖率降低,本文设计一种基于人工势场虚拟斥力场策略对WSN节点位置进行重新部署。建立如图6所示WSN节点部署的障碍物模型,实际障碍物包含于圆形中,障碍物大小决定圆半径ro的大小,且圆的范围也是斥力场存在的区域。WSN节点与障碍物间的距离简化为与圆心oi的距离,若节点落入圆内,便受到障碍物的斥力作用,并沿着斥力方向移动相应斥力大小的距离,从而达到让WSN节点避开障碍物的目的。来自障碍物的斥力大小定义为

图6 障碍物内WSN节点的移动方向

(17)

式中:Fno为WSN节点与障碍物间的斥力大小,斥力用于控制WSN节点避障的移动距离;d(ni,oicenter)为WSN节点与障碍物的间距;ro为障碍物斥力的有效作用范围,即圆半径。

图6(b)中,当障碍物周围存在部署区域边界A时,为了避免WSN节点移动超过边界,向边界方向移动的节点会按斥力反方向移动,斥力大小定义为

Fno′=2ro-Fno

(18)

3.3 基于MSISSA算法的WSN节点覆盖优化

MSISSA算法的优化目标是在特定的障碍物环境下待监测平面区域S=L×W内,求解WSN节点的最优部署坐标,使式(16)的区域覆盖率Rcov达到最大。将WSN节点覆盖优化问题定义为区域覆盖率Rcov为目标函数的高维矢量寻优问题,将WSN节点位置的寻优过程抽象为MSISSA算法中樽海鞘群的搜索行为,算法最优解即为WSN节点的部署坐标。将MSISSA算法中樽海鞘个体位置表示为WSN节点的一个覆盖分布,个体位置维度为WSN节点数的2倍。基于MSISSA算法的WSN节点覆盖优化具体步骤为:

输入:监测区域大小S=L×M、WSN节点数k、节点感知半径r、通信半径R、障碍物数量与类型,MSISSA算法参数:种群规模N、迭代最大次数Tmax、个体搜索区间[lb,ub](对应监测区域大小);

输出:WSN节点部署位置及最优覆盖率Rcov。

步骤1:设置监测区域S及障碍物数量、类型及位置,初始化MSISSA算法的参数;

步骤2:根据式(16)计算种群个体适应度,确定最优解;

步骤3:初始化算法迭代次数t=1;

步骤4:利用式(4)、式(5)分别计算模糊系统的2个输入变量:种群多样性diversity和迭代阶段iter,调用模糊逻辑计算樽海鞘领导者种群的占比因子;

步骤5:利用式(1)更新领导者位置;

步骤6:利用式(3)更新跟随者位置,并利用式(9)进行跟随者个体变异;

步骤7:利用式(10)、式(11)计算领导者的拓扑对立学习位置,再根据式(12)择优交换;

步骤8:更新种群全局最优解;

步骤9:更新算法迭代次数t=t+1;

步骤10:判断算法是否迭代终止。若未终止,返回步骤4执行;否则,算法终止,输出全局最优解,得到WSN节点部署坐标并计算最优覆盖率Rcov。

4 实验分析

设置WSN节点的部署区域大小为S=100 m×100 m,待部署WSN节点数为28个,节点感知半径为12 m,分布障碍物为5个,障碍物类型设置为菱形和三角形,包括4个三角形障碍物和1个菱形障碍物,三角形障碍物分布于矩形区域边角处,菱形障碍物处于区域中央,其具体分布如图7。设置MSISSA算法的种群规模为20,最大迭代次数为500。引入标准樽海鞘群算法SSA、改进灰狼优化算法IGWO[7]以及改进鲸鱼优化算法IWOA[9]进行性能的对比分析。

图7 障碍物分布区域

图8为4种算法在障碍物环境下的WSN节点部署结果。圆内实心点为WSN节点部署的坐标位置,圆形区域为相应WSN节点的覆盖区域。可以看到,SSA算法的节点覆盖存在明显的覆盖盲区和覆盖冗余,WSN节点部署均匀性较差,算法搜索精度不足。IGWO和IWOA算法经过搜索机制的优化后,比SSA算法的节点覆盖更加均匀,但依然存在较多的覆盖盲区。MSISSA算法相比3种对比算法,WSN节点位置分布更加均匀,覆盖冗余更少,证明综合改进机制有效可行。

(a)SSA

图9为算法覆盖率收敛曲线。可以看出,SSA较快进入收敛状态,但得到的是局部最优解,覆盖率较低,且至算法迭代结束也无法跳离局部最优处。IGWO和IWOA迭代前期覆盖率均上升较快,然后进入局部最优解处,但在迭代若干次后,在算法迭代中后期均有跳离局部最优解的特征,表明针对算法的改进策略能够一定程度提高寻优精度,但覆盖率还有提升空间。MSISSA得到了最高的覆盖率,且迭代初期已经获得更好的种群分布,算法通过拓扑对立学习机制择优保留优质个体,充分挖掘了区域内的精英位置信息,增加了每次迭代搜索得到更高覆盖率的可能。此外,MSISSA的收敛曲线始终处于更加平衡的状态,这表明引入模糊逻辑系统对领导者樽海鞘个体占比的自适应调整能够保证优势群体领导者的搜索与开发水平的均衡。同时,MSISSA迭代的中后期虽有一段时间的局部收敛和搜索停滞,但最后还是能够跳离局部最优解,得到更高的覆盖率,这表明多项式变异机制下的局部随机搜索能力,能够较好避免生成局部最优。

图9 覆盖率收敛曲线

图10是WSN节点数变化对覆盖率的影响曲线。设置WSN节点范围为[16,32],递增步长为4。可以看出,随着WSN节点数的增加,覆盖率稳步上升,这是由于更多的节点部署可以增加降低覆盖盲区的概率。但覆盖率递增速率上,MSISSA算法在增加WSN节点数后覆盖率明显增长更快。并且在相同WSN节点下,算法覆盖率最高,这表明MSISSA算法具有更高的寻优精度,能够在障碍物复杂环境中实现对WSN节点的覆盖优化。

图10 不同节点数下的覆盖率

图11选择展示SSA和MSISSA算法的WSN节点覆盖下,利用Prim算法得到的节点组网结果。传感器网络中需要重点关注节点间的通信距离和数据汇聚,可以看到,MSISSA算法的组网结果中,WSN节点的通信距离分布比较均匀,这有利于节省WSN节点的数据传输能耗。此外,从组网结果看,承担数据聚合的汇聚节点没有大量集中在区域的中间位置,而是更多地分布在靠近区域边界的区域,这样有利于避免数据汇聚的长距离传送,降低节点的长距离传输能耗。WSN节点更均匀的分布可以有效增强通信网络的可靠性,降低节点数据传输耗能,最终延长WSN的有效工作时间。SSA算法中WSN节点覆盖的均匀性明显差于MSISSA算法,导致部分通信距离较长,而部分节点又过于密集,不利于节点间数据传输能耗节省。

WSN网络的目标是通过部署的传感节点收集数据,并自组网络进行信息传输。传感器节点一般以电池供电,节点位置则直接影响着数据的传输距离。结合传感器节点的能耗模型,本部分观测4种算法进行节点部署后的网络生存时间。在自组网络中运行分簇协议LEACH,图12是协议运行100轮后传感器节点的存活率。出现第一个节点能量耗尽的顺序是SSA、IGWO、IWOA和MSISSA。依据传感器节点的能耗模型可知,节点能耗主要集中在数据传输能耗,因此,当节点覆盖均匀性差,部分区域冗余节点多,会导致数据重复传输多,快速消耗节点能源。同时,覆盖空洞区域则需要多次远距离中继传输,同样会加速节点能源消耗。MSISSA的节点优化覆盖结果避免了过多的远距离传输和近距离冗余传输,有效节省了传感节点的能耗,延长WSN网络的生存时间。

图12 传感器网络生存时间

5 结束语

WSN节点部署容易造成覆盖冗余和覆盖空白的不足,本文提出了一种障碍物环境中基于多策略融合改进樽海鞘群算法的WSN节点覆盖优化策略。为了提高樽海鞘群算法的寻优性能,引入模糊逻辑种群角色调整机制、多项式变异扰动机制及拓扑对立学习机制对算法全局搜索与局部开发间的平衡、局部随机搜索能力及精英位置信息挖掘进行了改进,然后利用改进樽海鞘群算法求解障碍物环境WSN节点覆盖优化问题,以网络覆盖率最大为目标,迭代搜索节点部署的最优位置。实验结果表明改进算法能够有效提高节点覆盖率,减少覆盖冗余,优化节点均匀分布。