重采样和天牛须协同演化粒子群的WSN覆盖控制算法

王明华，姜开武，邓贤君

(1.南华大学 超快微纳技术与激光先进制造湖南省重点实验室，湖南 衡阳 421001；2.华中科技大学 网络空间安全学院，武汉 430074；3.南华大学 核燃料循环技术与装备湖南省协同创新中心，湖南 衡阳 421001)

0 引 言

近年来，随着无线通信技术和智能传感器技术的发展，无线传感器网络(wireless sensor networks, WSN)引起了研究界和行业的极大关注[1-2]。WSN作为物联网的支撑技术之一，负责信息感知和网络终端传输[3]。传感器节点具有感知环境、与邻近节点通信和对所收集的数据进行基本计算的特性，使WSN能在复杂或对人身有害的环境中运行[4]。WSN得到广泛应用，包括健康监控、污染处理、目标跟踪、数据保护和公共安全保障等[5-9]。与此同时，WSN在网络连通性、节点利用率、网络覆盖率等方面也存在问题有待解决。不适合固定部署的复杂场景通常使用飞机空投或者其他随机方法进行部署，导致因节点分布不均而产生冗余覆盖和覆盖空洞[10]。这种随机方式将导致节点密度过高，增大节点接收、处理和转发的数据量，生成大量冗余数据，这些数据会阻塞通道并造成数据干扰，直接影响网络的可靠性[11]。同样，覆盖空洞直接影响监视的质量。为了提高WSN监控质量并提高网络可靠性、延长网络寿命，有必要确保节点部署能够有效覆盖目标区域并降低网络中节点的使用率。

文献[12]提出基于改进的人工鱼群算法，在最大程度扩大网络覆盖范围的同时降低节点利用率，解决WSN覆盖问题。文献[13]提出基于遗传算法(genetic algorithm, GA)的元启发式方法来解决最大网络生存期问题(maximum network lifetime problem, MLP)，但是没有考虑网络中冗余节点的情况。文献[14]将WSN覆盖问题归纳为整数的线性问题，提出3种近似算法解决该问题，分别为贪婪圆形节点放置(greedy round node placement, GRNP)、目标保护节点放置(target protection node placement, TPNP)和节能节点放置(energy efficient node placement, EENP)。但是，在具有较大规模的目标点时，问题会复杂得多，不能描述为整数的线性问题。文献[15]提出并行分区式粒子群算法(improved particle swarm optimization, IWPSO)解决具有特征点集的优化问题，但是也仅考虑了网络中覆盖率单一因素。文献[16]将粒子滤波中的重采样概念引入到粒子群算法(particle swarm optimization, PSO)中提出重采样粒子群算法(resampling PSO, RPSO)，该算法在优化WSN覆盖控制问题有良好的效果，但忽视了单个粒子的搜索能力。文献[17]提出天牛须粒子群算法(beetle antennae search PSO, BASPSO)解决WSN覆盖问题，但是该算法仅考虑了覆盖率因素，没有进行基准函数测试。

为提高随机部署方式下WSN的覆盖率和网络节点休眠率，降低WSN在运行时的能耗，在粒子滤波中的重采样技术和天牛须搜索的启发下，本文将重采样过程和天牛须搜索的协同演化融入粒子群优化中，提出了一种新的优化算法，称为重采样和天牛须协同演化的粒子群算法(resampling BASPSO, RBASPSO)。重采样过程与天牛须策略的协同演化既提升了搜索过程中粒子群整体多样性，也加强了粒子群中单个粒子搜索邻域的能力。在测试该算法收敛性时，使用了10个CE2005优化基准函数来进行评估，同时将该算法应用于WSN覆盖优化。WSN覆盖控制建模由网络覆盖率和节点休眠率的加权和函数构成，利用所提算法可寻求最佳节点部署方案。

1 覆盖问题描述

无线传感器网络的典型应用之一是在危险或人类不可接近的区域进行监视和收集信息，在这类情况下只能选择飞机空投等随机方式进行无线传感器的部署[18]。传感器节点部署在二维检测区域中，并且有以下特性。

1)节点的密度足够大。如果所有节点都工作，不仅可以保证覆盖的质量要求，而且具有大量的休眠节点。

2)网络中节点都具有相同的感知半径rs。

3)检测区域远大于节点覆盖范围，以致于可忽略边界效应。

1.1 传感器覆盖模型

在本文的研究中，传感器节点部署于二维检测区域，传感器覆盖模型选择经典布尔感知模型。布尔感知模型的机理如下：在节点Si的覆盖圆中，所有目标点的监视概率为1，而圆外点监视概率为0。设节点Si的坐标为(xi,yi)，传感器感测半径是rs，网络任意目标点(x,y)被感知的概率为

(1)

(1)式中：x和y为网络中目标点位置坐标。

1.2 网络覆盖模型

为有效评估WSN的覆盖，将感兴趣区域分为网格形式，表示为G(c,r)，其中c和r分别代表网格行和列的数量。在评估覆盖率时，网格被转换成点。如果某个节点没有覆盖任务，则设置为睡眠状态，以减少能量消耗，直到该节点有覆盖任务为止。只有当节点有覆盖任务时，才将其设置为活动状态。无线传感器网络覆盖模型描述如下：以网格中心点为目标点，将监测区域分散到c×rm*n网格中。

定义节点Si覆盖点的概率为Pi，这个概率只有1或者0两种情况。网络中目标点(x,y)(x,y)被节点集S覆盖的公式为

(2)

WSN覆盖示意图如图1所示。

图1中，“1”表示该网格被覆盖，“0”则意味是覆盖空洞。图1中标记为1的数量有13个，则覆盖率为52%。

将感兴趣区域目标点进行编号，假设有10 000个目标点，则每个点被覆盖的概率为

(3)

此时，传感器网络的覆盖率FCOV也可表示为

(4)

休眠传感器的函数可以表示为

(5)

(5)式中：na是有覆盖任务的节点数；n是部署的节点总数。

本文优化目标是在最大限度扩大网络覆盖范围的同时增大网络节点休眠率，以达到延长网络生命周期和减少能量消耗的目的，目标函数采用线性加权法将函数FCOV与节点休眠率FRE结合[16]。

Ffit=αFCOV+βFRE

(6)

(6)式中，α和β是函数FCOV和FRE的权重，且α+β=1，其默认取值为α=0.8，β=0.2。

2 重采样和天牛须协同演化粒子群算法

2.1 PSO的原始版本

PSO是一种群体智能优化算法。单个粒子i由当前位置xi、先前的最佳位置pi和速度vi等3个D维变量组成，其中D是搜索空间的维数[19]。在每次迭代中，可以将当前位置xi视为当前问题的解决方案，并且到目前为止的最佳解决方案存储在pi中。该算法通过调整vi来更新粒子速度和位置。

vi(t+1)=wvi(t)+c1r1[pi-xi(t)]+

c2r2[pg-xi(t)]

(7)

xi(t+1)=xi(t)+vi(t+1)

(8)

(7)—(8)式中：w是惯性权重；r1和r2是生成的独立随机数；c1和c2为加速度系数，决定个人最佳pi和邻域最佳pg方向上的随机力的大小。

使PSO搜索更加稳定的方式有两种：1)选择适当的w以及c1和c2；2)设置一个较大的vmax值约束粒子速度。然而惯性权重w不能平衡全局勘探和局部开采，而且求解一个最佳vmax比较困难。因此，为更好地平衡全局勘探和局部开采的愿望并降低vmax的重要性，本文采用Clerc收缩因子γ对速度更新公式改写为[20]

vi(t+1)=γ{vi(t)+c1r1[pi-xi(t)]+

c2r2[pg-xi(t)]}

(9)

(10)

(10)式中，ρ=c1+c2>4。当采用Clerc收缩法时，通常将设ρ为4.1，c1=c2=2.05，收缩因子γ约为0.729 84。采用Clerc收缩后的粒子能在不使用vmax的情况下收敛，其效果类似于惯性权重的效果，导致群体行为最终被限制在包含最知名解的可行搜索空间的小区域内。

PSO搜索性能较差，主要表现在两个方面：①在迭代计算中粒子会朝着一个局部最优值附近聚集，如果没有外界干扰，粒子将陷入一个较差质量的谷底始终不能逃逸；②粒子位置更新导致粒子一直在最优解附近搜索，无法搜索到它的邻域。本文所提RBASPSO算法的重采样与天牛须协同演化过程主要解决这两个问题。

2.2 重采样过程

为有效解决粒子群算法在迭代过程中粒子多样性问题，在引入粒子滤波的重采样时将权重值极低的粒子重采样为高质量的新粒子，以提高算法搜索精度，同时消除不必要的搜索时间。如果在迭代过程中满足重采样的标准，则执行重采样过程，引入重采样的标准是粒子聚集度(particle aggregation degree, PAD)是否大于临界值。

(11)

(12)

(11)—(12)式中：N是粒子数；D是问题的维数；DISi表示粒子i到中心坐标的距离；xij表示第i粒子的第j维位置；yj是中心点j维的中心坐标值，在搜索空间中随机生成。PAD表征了粒子种群多样性。PAD值越低，粒子分布越分散，种群多样性越好。

当粒子聚集度大于临界值，即PAD>PADt时，需要对粒子群进行重采样。假定优化问题的函数满足高斯分布，此时粒子i的权重值为

(13)

(13)式中：qi是i赋予粒子的权重值；F(x)是适应度函数；pg代表当前的全局最优值；σ是F(xi)-pg的样本方差。

然后归一化qi, 粒子i的单位权重值为

(14)

粒子权重值qt的门限值qt为

(15)

对每个粒子，如果qi

(16)

(17)

xi(t+1)=xi(t)*+λ

(18)

(19)

(18)—(19)式中：x(i)*表示当前的最优解；norm(u,μ)是具有均值u和方差μ的高斯随机数。

2.3 天牛须搜索过程

为了提高粒子群中单个粒子的邻域搜索能力从而提高整体搜索能力，引入天牛须搜索。对于一个D维空间的优化问题，用xl表示左边须坐标值，xr表示右边须坐标值，x表示天牛质心坐标，d0表示触角间距。天牛质心朝向是问题D维中的任意方向，因而天牛两触角的朝向也是在D维中任意的，可以产生一个随机向量dir=rands(D,1)来表示它。

计算左右两触角的适应度值为

Fleft=f(xl)

(20)

Fright=f(xr)

(21)

x=x-step×dir×sign(Fleft-Fright)

(22)

(22)式中：步长step的初始值为step=c×d0,c是常数；step随算法运行轮数更新，step=step×τ，τ为天牛须步长的收敛因子。

天牛须策略使粒子在移动过程中，会对下一步的左右方向进行预判，加强粒子邻域搜索能力，从而有效避免粒子陷入局部最优解。

2.4 算法执行过程

重采样技术和BAS过程的协同演化中，首先，对粒子群进行聚集度检测。在聚集度过高时采用重采样技术与BAS的协同演化，将当前粒子权重值过小的粒子重采样并使用天牛须搜索确定当前粒子的最优位置。其次，为了减少不必要的计算量，在PAD满足要求时仅需采用天牛须搜索确定天牛(粒子)的更新。需注意的是，采用BAS更新粒子位置的前提是所更新的位置优于原来的位置。最后，依据粒子群的速度和位置的更新完成迭代工作。

由于RBASPSO中每个粒子都是WSN覆盖问题的一个解决方案，而每个粒子携带有N个节点信息。用xi(t)表示粒子i在第t次迭代时的节点位置信息的集合，即xi=(xi1,yi1,xi2,yi2,…,xiN,yiN)。xi(t)中各元素依次代表节点1到N的横纵坐标，它所经历的最好位置为pbest=max(pi1,pi2,…,piN)，而所有粒子经历的最好位置为gbest。

算法在执行时，每轮都将选择具有最大目标函数值的覆盖方案，通过该方案来收集节点位置信息，将网络中有覆盖任务的节点设置为工作状态，没有任务的节点设置为睡眠状态。RBASPSO算法寻求最佳部署方案的过程如下。

步骤1参数设置。如种群规模、问题维度、天牛须长度等，初始化种群位置和速度。

步骤2计算当前粒子群聚集度PAD。如果PAD大于阈值PADt，则进入下一步；反之进入步骤6。

步骤3计算每个粒子的权重值qi并归一化为Qi与权重值的平均值qt进行比较，如果Qi

步骤4根据(16)—(17)式重采样该粒子，赋予新的位置量和速度信息。

步骤5将每个粒子看作天牛，按(22)式进行天牛须搜索。如果搜索位置优于之前位置，则保留；反之，不更新粒子位置信息。

步骤6根据(8)—(9)式更新粒子的速度和位置信息。

步骤7计算当前粒子适应度值，更新pbest和gbest。

步骤8判断是否满足终止条件。不满足，返回步骤2；否则，结束并输出最大值和gbest。

2.5 收敛性测试和算法时间复杂度分析

2.5.1 收敛性测试

将求解的问题分为单峰问题和复杂多峰问题，从有效性和效率的角度来检验RBASPSO算法的性能，基准函数如表1所示。表1中f1和f2是简单单峰问题；f3和f4是低维多峰问题；f5-f10是具有大量复杂极小值的复杂多峰问题。基准函数的最优值、可行范围和设置的初始范围如表2所示，基准函数测试结果如表3所示。

表1 基准函数列表Tab.1 Benchmark functions

表2 基准函数参数Tab.2 Parameters of the benchmark function

表3的数据为各算法在迭代寻优10 000次所得。在处理f1和f2这样的简单单峰问题时，不会有被困在低质量峰值的潜在威胁，所提算法的收敛性比PSO提高了1～8个数量级不等，比只使用单个策略的RPSO和BASPSO算法提高了1～5个数量级，如图2所示。由于函数f3和f4只有两个变量，且搜索空间相对较小，各算法都能快速搜索到最优值，算法没有改进空间，故这里不展示函数f3和f4的搜索过程。

图2 函数f1和f2收敛性Fig.2 Convergence of f1and f2

对于多峰问题，从表3中f5-f10的结果可以看出，在处理多峰优化问题时，RBASPSO算法的收敛精度有明显的优势；在处理复杂多峰优化问题时，RBASPSO算法比BASPSO、RPSO和PSO算法的收敛速度和精度均有明显提升，其中搜索精度提升1～8个数量级不等，如图3所示。以函数f9为例，RBASPSO算法比RPSO和BASPSO算法搜索精度分别提升1个和4个数量级。这是由于搜索空间存在一些狭窄的间隙，粒子容易陷入质量低的谷底不能逃出，而重采样技术和天牛须搜索都提高了粒子逃逸谷底的能力。

图3 函数f5-f10的收敛性Fig.3 Convergence of f5-f10

表3 收敛性测试结果Tab.3 Results of convergence test

通过对这两类问题的测试和分析可得出这样的结论：RBASPSO算法能提高处理简单单峰问题的能力，在处理复杂而且高维的多峰优化问题上优于RPSO和BASPSO算法。

2.5.2 算法时间复杂度分析

显而易见，PSO的时间复杂度最低，但是收敛精度和速度的性能最差；RBASPSO算法引入重采样技术和天牛须搜索，增加了算法时间复杂度，但是极大增强了算法的收敛速度和收敛精度。

3 WSN仿真实验及分析

将监测区域设置为100×100 m，节点感知半径rs为9 m；分析不同节点数量下，适应度函数Ffit、覆盖率FCOV和休眠率FRE的变化情况。随机部署40个静态传感器节点，然后持续递增20个传感器，一直增加到120，分析不同节点数量下优化结果的差异性。先对优化过程中传感器的状态进行分析，再对适应度函数以及网络覆盖率和节点休眠率进行对比。

3.1 传感器节点的状态

网络中传感器的状态在具有最佳节点部署方案中求得。随着迭代次数增加，传感器节点的重合次数减少而覆盖率逐渐增加，最终收敛到最大值。图4展示了RBASPSO算法在不同迭代次数时传感器节点的状态。图4中，传感器数量为60，t为迭代次数。图5展示了不同算法在迭代100次时传感器节点的状态，也就是算法所搜索到的最大目标函数值时对应的节点状态以及覆盖率情况，图5中传感器数量为100。

图4 RBASPSO算法在不同迭代次数时传感器节点的状态Fig.4 State of the sensor node at different iterations of RBASPSO algorithm

图5 不同算法在迭代100次时传感器节点的状态Fig.5 State of sensor nodes when different algorithms are iterated 100 times

由图4可见，在迭代100次时，网络覆盖率对比迭代1次、30次和50次分别提升了约9.423%、2.153%和0.858%。同时也可以发现，算法在迭代1～30次时，收敛速度很快；而在迭代到30～50次时，收敛速度有所减少；到50～100次时，收敛速度明显减缓。

由图5可见，迭代100次时，RBASPSO算法在覆盖率方面比PSO、RPSO和BASPSO算法分别提升了约3.33%、3.232%和2.474%；覆盖率更大，节点分布更均匀，网络布局也更合理。

3.2 适应度函数的变化

图6展示了目标函数Ffit的最大值随节点数量变化的关系。由图6可见，RBASPSO算法在节点数为40时Ffit值约为0.59，随着节点数目的增加，Ffit的最大值也随之增加；在节点数目为120时，Ffit的最大值增加到约为0.889。显然，在不同节点数量下本文方法均优于其他算法。

图6 适应度函数与节点数的关系Fig.6 Relationship between fitness function and the number of nodes

图7展示了4种不同节点数时不同算法的收敛性能。从图7可以看出，RBASPSO算法在提升目标函数值上明显更优，在节点数为80时尤其如此。对比其它3个算法，RBASPSO算法目标函数值提升了3.256%以上。收敛速度方面，各算法都是在迭代计算1～40时搜索性能更好；RPSO和BASPSO算法在迭代40之后收敛速度趋于平缓，甚至停滞不前。显然，重采样和天牛须协同演化增强了RBASPSO算法的搜索性能，使得该算法在迭代1～40次时具有更高的收敛精度；在迭代40次之后依然有往更优值搜索的趋势。

图7 不同节点数的收敛情况Fig.7 Convergence of fitness function at different numbers of nodes

3.3 WSN覆盖指标分析

3.3.1 网络覆盖率

评估网络性能时，最重要的指标是覆盖率。网络覆盖率和节点休眠率都在最大目标函数值求得。

图8展示了网络覆盖率与节点数的关系。从图8可见，RBASPSO算法在各个节点数量下的最大覆盖率都更高。在节点数为40时覆盖率比BASPSO、RPSO和PSO分别提升了4.2%、6.7%和7.1%。随着传感器数量的增加，该算法覆盖率比次优的BASPSO算法在节点数为60、80、100和120时分别提升了2.6%、2.9%、2.2%和1.1%。由此可知，在节点密度较小时，覆盖率提升较快；在节点密度很大时，覆盖率的提升逐渐趋缓。

图8 覆盖率与节点数的关系Fig.8 Relationship between coverage and number of nodes

图9展示了不同节点数量下函数FCOV随迭代次数增加的收敛情况。图9列举了4种不同节点数的覆盖率收敛情况。由图9可见，RBASPSO算法的收敛速度和精度明显更优。

图9 不同节点数时覆盖率的收敛情况Fig.9 Convergence of coverage rate under different number of nodes

以节点数40为例，4个算法中，RBASPSO算法收敛速度和精度最优，BASPSO算法次优。对比BASPSO和RPSO算法，RBASPSO算法在覆盖率方面提升了约3.27%和6.67%。

3.3.2 节点休眠率

WSN在满足覆盖率要求的同时，也要保证网络中有休眠节点以供随时替换失效的节点。图10展示了节点休眠率与节点数的关系。

图10 休眠率与节点数的关系Fig.10 Relationship between sleep rate and number of nodes

由图10可见，节点数量为60和70时，网络节点休眠率比较低并且所提算法比其它3个算法稍差一点。这是由于区域中传感器数量较少，RBASPSO算法在完成高覆盖率时牺牲了部分传感器数量。随着节点数量的增加，RBASPSO算法下的节点休眠率随之增加并且优于BASPSO和RPSO。在节点数量为80时，本文算法比这两个算法在休眠率方面提升了0.84%到4.42%。

4 结 论

本文围绕WSN的覆盖率和节点休眠率两个关键问题，提出基于重采样技术和天牛须协同演化的粒子群算法。该算法解决了PSO在搜索过程中粒子多样性不足和个体的搜索能力较差的问题，有效提升了算法搜索性能。基准函数测试和WSN实验结果证明，本文算法能有效处理单峰和复杂多峰优化问题，提高网络覆盖率和节点休眠率，延长网络生命周期，从而获得更优的节点部署方案。