基于改进蝙蝠算法的WSNs覆盖优化策略

姚引娣，杨 轩，刘武英，廖焕敏，胡珊珊，付子坤

(1.西安邮电大学 通信与信息工程学院,陕西 西安 710121；2.西安邮电大学 学报编辑部,陕西 西安 710121；3.西安邮电大学 电子工程学院，陕西 西安 710121)

无线传感器网络(Wireless Sensors Networks,WSNs)是由大量微小的具有计算处理、感知和无线通信能力的传感器节点组成的自组织网络[1]。目前，WSNs被广泛应用在军事[2]和民用[3]等领域。无线传感器网络节点对目标区域的覆盖是WSNs中的关键问题，为了满足覆盖要求，往往采用随机部署的方式，导致部分区域出现覆盖盲区或者覆盖冗余，降低覆盖质量。因此，需要对传感器网络节点重新部署调整，通过控制调整移动节点在网络中的分布，修复覆盖空洞，提升WSNs覆盖率。

近年来，群体智能被广泛应用在WSNs覆盖问题中。文献[4]提出一种虚拟力导向粒子群的无线传感器覆盖优化算法，在粒子群位置更新公式中引入了虚拟力权重，提升了算法的收敛速度与搜索能力，但存在易陷入局部最优等缺点。文献[5]通过判断Voronoi图顶点与传感器节点之间的关系构造虚拟力，再将虚拟力扰动和布谷鸟搜索结合进行覆盖优化，有效提高了网络覆盖率并降低了节点移动距离。混合策略改进蚁狮算法的网络覆盖优化算法[6]，取得了较好的覆盖效果，但节点覆盖效率及稳定性不足。文献[7]提出的基于外推人工蜂群算法的节点部署优化方法，与原人工蜂群算法相比，表现出更快的寻优速度，但覆盖率仍需改善。上述方法应用在WSNs覆盖优化中，都存在网络收敛速度慢、网络覆盖率低等问题。

为了有效降低节点的冗余度，提升网络覆盖率，拟提出一种自适应虚拟力导向蝙蝠算法(Adaptive Virtual Force-guided Bat Algorithm,AVFBA)的WSNs覆盖优化策略。将虚拟力中的最大移动距离设计为指数衰减函数，算法自适应调整步长，加快网络收敛速度。随后，在原蝙蝠算法的基础上加入莱维飞行策略扰动更新最优蝙蝠的位置。利用自适应虚拟力导向改进的蝙蝠算法，增强全局搜索和跳出局部极值的能力。最后，将AVFBA应用到WSNs覆盖优化中，以期使网络收敛速度更快，传感器节点分布更均匀。

1 覆盖问题模型及蝙蝠算法

1.1 覆盖模型

假设监测区域为二维平面，且为正方形，将其划分为L×M个网格点，并在该区域部署N个传感器，每个传感器都具有相同的感知半径Ks和通信半径Kc。为了保证网络能够正常通信，Kc设置为大于或等于Ks的2倍，则节点集合表示为S={s1,s2,…,sN}。假设在监测区域的某个节点si的位置坐标为(xi,yi)，目标节点zj的坐标为(xj,yj)，则Si与zj之间距离表达式为

(1)

采用布尔模型[8]作为节点感知模型，即目标处于节点的感知范围就可以被成功感知。用p(si,zj)表示节点si对zj的感知质量，当节点zj的位置位于节点si的感知范围内时，则感知质量为1；否则节点si对zj的感知质量为0，数学表达式为

(2)

任一目标都有可能会被多个传感器协同探测，则目标点的感知概率为

(3)

该监测区的覆盖率体现覆盖质量，为所有传感器节点覆盖的目标点数除以该区域总的点数，定义为

(4)

节点的覆盖效率体现网络节点的冗余度，覆盖效率越大，表示节点的分布越均匀，冗余程度较低。覆盖效率为网络中所有节点覆盖的监测区域面积与所有节点总的感知范围面积的比值，计算表达式为

(5)

1.2 蝙蝠算法

蝙蝠算法(Bat Algorithm,BA)是一种群体智能算法，由Yang等[9]于2010年提出，具有模型简单、收敛速度快等优势，其在解决优化问题上明显优于粒子群等经典算法。BA算法已应用到如机器人路径规划[10]、故障诊断[11]、微电网优化[12]及神经网络模型[13]等领域。BA的主要原理是模拟BA捕食猎物回声定位，蝙蝠觅食时发出声波，当声波碰到猎物或者障碍物返回，蝙蝠接收到声波即可定位。当蝙蝠与猎物距离越来越小，蝙蝠会增大脉冲发射频度，响度则逐渐变小。BA的基本步骤如下。

(6)

(7)

(8)

步骤3进行局部搜索，位置更新为

x*(t+1)=x*(t)+εAt

(9)

其中：ε∈[-1,1]，At表示所有蝙蝠在t时刻的平均响度。

步骤4当蝙蝠离猎物越来越近时，响度逐渐变小，但发射频度会逐渐变大，则更新响度和发射频度，其计算表达式分别为

(10)

(11)

但是，将BA应用在无线传感器网络覆盖中，还存在易陷入局部最优以及收敛速度慢等问题，覆盖效果不佳。

2 改进的蝙蝠算法

在算法迭代中，群体智能算法包括BA等，后期会出现收敛速度较慢、易陷入局部最优解等问题。BA的局部位置利用最优蝙蝠进行更新，受到当前最好位置的影响，导致全局搜索能力不强，易陷入局部最优致使算法“早熟”。

针对上述问题，将利用虚拟力导向策略、莱维飞行扰动策略对BA进行改进，提升算法的收敛速度、全局搜索能力和跳出局部极值的能力，避免出现“早熟”现象。

2.1 虚拟力导向策略

(12)

其中：φχ、φζ分别为虚拟引力、斥力参数；dth为设定的距离阈值；θij为两节点的方向夹角。

(13)

在VFA中，Umax一般设定为固定值，导致网络无法快速收敛。因此，将Umax设定为指数衰减函数，在算法迭代过程中算法自适应调整步长，加快网络收敛速度，其计算表达式为

(14)

其中，ω为指数衰减常数，取值范围为(0,1]。选取ω=0.1，Umax随着算法迭代逐渐减小，能缓解传感器震荡现象产生的影响，并减少了节点的无效移动[16]。

2.2 莱维飞行扰动策略

利用莱维飞行算法的随机游走性能，提升BA跳出局部最优的能力，改善其易陷入局部最优的问题。将莱维飞行算法融入到BA局部位置更新中，增加算法的寻优性能，避免过早陷入“早熟”[17-18]。

莱维飞行是一种特殊的游走策略，其能够增强信息的交互，避免搜索陷入局部最优。莱维飞行的随机搜索路径的表达式为

(15)

其中：β为参数，其取值范围为0<β<2，一般取1.5；参数μ、ρ服从正态分布，表示为

(16)

其中，

(17)

在BA局部位置更新中只依靠最优蝙蝠的位置和平均响度，下一代最有蝙蝠的位置更新容易受到上一代最优蝙蝠的影响，失去种群多样性。因此，在蝙蝠局部位置更新中加入莱维飞行，其计算表达式为

(18)

2.3 基于虚拟力导向BA的覆盖优化策略

在大小为L×M的覆盖区域中，随机部署N个传感器节点，每一种蝙蝠代表一种覆盖方案，蝙蝠的种群数量为n。初始化所有蝙蝠的位置，以覆盖率为优化目标，使得目标监测区域的覆盖率最大化，即求得最佳蝙蝠的位置，使得Rv最大。将所提的虚拟力导向策略、莱维飞行扰动策略组合为WSNs覆盖优化策略，称为基于AVFBA的WSNs覆盖优化策略,AVFBA流程如图1所示。

图1 AVFBA流程

基于AVFBA的WSNs覆盖优化策略的具体步骤如下。

步骤1初始化网络参数，包括种群规模n，维度D,蝙蝠的速度vi和位置xi。设置发射脉冲频率最小值fmin、最大值fmax，初始响度Ai和脉冲频度ri，以及最大迭代次数Tmax，节点移动的最大距离Umax，并设置目标函数f(x)。

步骤3通过式(6)更新脉冲频率，并利用式(7)、式(8)和式(13)分别更新蝙蝠速度、位置。

步骤6判断是否满足终止条件，即达到最大终止条件，最大迭代次数或满足适应度值为最优覆盖率的要求。如果满足，则停止迭代，输出最优解；若不满足，则转至步骤3，直到满足条件。

3 实验分析

3.1 仿真环境设置

仿真实验均采用MATLAB仿真软件，设置WSNs各参数相同，并且每个算法运行50次以上，取其平均值保证公平性。采用BA、VFA和VFPSO作为对比算法，分析AVFBA算法的覆盖率性能指标，各算法的参数设置如表1所示。

表1 各算法参数设置

3.2 仿真结果及分析

3.2.1 覆盖率

仿真区域为100 m×100 m，对应节点数量N分别为25、30和35时的覆盖率，如图2(a)～2(c)所示。从图2可以看出，随着迭代次数的增加，AVFBA覆盖率先急速上升，随后趋于平稳，最终达到稳定。以N=30为例，AVFBA在迭代40次之后就已经收敛，而BA、VFPSO在57次、86次才逐渐收敛，分别提前了17次和46次。在覆盖率方面，相较于BA、VFA和节点随机抛洒等部署策略，覆盖率分别提升了1.75%、5.86%和35.39%。对比结果表明，与BA、VFA、VFPSO算法相比，AVFBA算法收敛速度更快，网络覆盖率优势明显。

图2 各算法覆盖率对比

为了体现算法在不同环境下的适应性，采用不同的区域大小和节点数量，并设置WSNs各参数均相同，以及每个算法运行50次以上，取其平均值保证公平性。当节点数量变多时，3种群体智能算法都不同程度上陷入局部最优，导致网络覆盖率下降。尤其是当区域大小为100 m×100 m、N=25和区域大小400 m×400 m、N=400对比时，AVFBA覆盖率仅下降1.88%，而VFPSO、BA分别下降6.25%、17.73%。这是因为AVFBA加入了自适应虚拟力和莱维飞行，增强了跳出局部最优的能力。仅当区域大小为400 m×400 m、节点数量N=400时，AVFBA覆盖率低于VFA。在其余不同区域大小和节点数量情况下，AVFBA网络覆盖率均大于其他3种算法，表明AVFBA适应性强。各算法覆盖率对比情况如表2所示。

表2 各算法覆盖率对比

当仿真区域大小为100 m×100 m，N=30时，4种算法覆盖部署如图3所示。图3(a)～图3(d)分别为执行BA、VFA、AVFBA和VFPSO后的节点分布与覆盖部署效果。其中：X表示覆盖区域的长；Y表示覆盖区域的宽。

图3 4种算法覆盖部署

从图3中可以明显看出，BA和VFPSO覆盖图有较多的覆盖冗余，这是由于BA和粒子群算法易陷入局部最优，导致覆盖率无法持续增长。而VFA覆盖图的覆盖盲区较大，则是因为原虚拟力算法将迭代步长设置为固定步长，无法自适应调整步长，导致算法产生较差的覆盖效果。AVFBA由于加入了莱维飞行策略和虚拟力导向策略，增强了全局搜索和跳出局部极值的能力，覆盖部署图中节点分布更加均匀，覆盖漏洞较小，取得了很好的覆盖效果。

3.2.2 覆盖效率

为了进一步检验算法在不同数量的网络节点情况下的性能，以及验证是否能有效降低节点冗余度，对各算法的覆盖效率进行了测试。

算法的覆盖效率越高，说明覆盖冗余较小，节点分布更加均匀，部署的成本更低。仿真实验采用的区域大小面积为100 m×100 m，节点数量N分别为25、30和35，实验结果如图4所示。

图4 节点覆盖效率对比

由图4可以看出，在相同的区域内，随着节点数量增多，节点覆盖效率都在逐渐降低，表示覆盖冗余在不断增加。但在3种不同的节点数量情况下，AVFBA的覆盖效率均优于其他3种算法，表明AVFBA的覆盖性能更优。

4 结语

为了提升网络覆盖率，优化WSNs节点布局，提出了一种基于自适应虚拟力导向蝙蝠算法的WSNs覆盖优化策略。通过将虚拟力的节点最大移动距离设计为指数衰减函数，并将自适应虚拟力应用在蝙蝠全局位置更新时引导蝙蝠位置，加快收敛速度，提升网络覆盖率。再加入莱维飞行扰动策略产生局部新解，增强算法跳出局部最优的能力。仿真结果表明，AVFBA相比BA、VFA、VFPSO，网络收敛速度更快，其覆盖率更高，优化了WSNs的网络布局，降低了节点冗余度。