基于粒子间距调整改进PSO算法

冯 颖，高文华，康 琳

(太原科技大学 电子信息工程学院，太原 030024)

无线传感器网络( Wireless Sensor Networks， WSN)是各种具有相同功能或者不同功能的传感器聚集在一起协同工作，传感器通过自己的方式自组建立连接，而且维护在一个被测区域框架内[1]。用于传感和存储从动态环境收集到的数据信息。这些节点可以部署在任何所需要的领域，用于检测或监视某些特殊事件等[2]。

为了减少规模成本，有效的收集数据。WSN能否对所监测的区域进行严格有效的监控，以及WSN能否收集和转发所需的信息，是WSN中需要解决的最基本的问题[3]。用有限的传感器节点尽可能大范围的去覆盖特定区域的问题就转化成如何能求得覆盖率的最大值问题。因此，覆盖率是评估WSN网络质量的关键参数，也是其应用在场景中的重要需求。

关于通过各种不同的智能算法，把WSN覆盖作为优化目标的研究有许多。文献[4]是对PSO中保持原来速度权重系数和认识因子进行了调整。文献[5]Lu等人利用具有吸引和排斥的动物觅食策略，提出了一种吸引和排斥相结合的PSO(CAR-PSO).有效的克服了过早收敛的问题。文献[6]Kundu等人通过引入一种新的微扰策略来提高PSO算法的性能。文献[7]是将粒子群的进化和聚合程度引入到惯性权重ω中，产生了随着粒子聚合程度不断变化的动态惯性权重。以区域覆盖率最大做为目标函数，更新节点的位置从而达到最大区域覆盖率。相比基本PSO覆盖率稍有提高，但仍然存在节点分布不均匀等；文献[8]将权重系数的和认识因子分别调整为线性递减和递增形式以及利用正弦函数来使惯性权重变化；文献[9]和文献[10]分别是应用改进的离散果蝇算法和在人工鱼群算法来找出最优的覆盖方案，与之前几种PSO算法相比，它的覆盖率稍有提高，节点分布比较均匀，但是仍然有节点越界或者由于重叠而覆盖不到的问题。文献[10]针对分布时节点越过边界区域和粒子多样性减弱，提出寻优能力增强型越界免疫的PSO，达到了寻优速度快，降低了停止在局部最优的可能。该算法的有效覆盖率能达到96%以上，而且鲁棒性也较好。文献[11]采用人工鱼群算法与PSO结合的算法运用到WSN的覆盖中，使达到覆盖最大化且节点均匀分布。文献[12]和[13]将混沌理论与与粒子群算法相结合提高了WSN的有效覆盖率。文献[14]和[15]进行了灰狼算法和PSO相结合，弥补了两种算法的缺陷对网络覆盖质量有了一定的提高。文献[16]提出了一种寻优能力增强型越界免疫粒子群算法(OAEBI-PSO)通过对越界的粒子进行处理是覆盖率得到了提高。通过学习研究，相对于其他算法，PSO的流程不繁琐复杂，需要调节的参数少，而且易于与其他算法并行实现。

之前的研究都有效的提高WSN覆盖率，但是在寻优过程中仍然存在粒子越界、重叠、运动速度下降或出现停止不动等，失去多样性的问题，这就造成了探求最优粒子的性能的大大减退。

所以针对上述问题，本文通过在算法寻优过程中加入粒子间距离调整，对粒子间的距离超出所限定的最大阈值，进行间距调整。其次，在算法中将粒子探索轨迹进行细化来增添单个体粒子的多样性，探索性能从而得到增强。 进行MATLAB仿真实验，得出APS-PSO部署的覆盖率较高，同时求解的节点均匀度也较小。APS-PSO算法能够更好结合WSN覆盖数学模型，达到较好的优化效果。进行50次Mote-Carlo实验后可以得出算法有较好的稳定性。

1 WSN覆盖数学模型

1.1 传感节点的物理模型

本文用到的是二元感知模型。其定义为：假设在区域A上获取信息，s为区域上的某个传感器节点，只要在以s为圆心，Rs为半径的圆内的数据均能被s所感知到。Z为任意被监测目标点，当Z到节点S的间隔d小于半径Rs，则S一定能感知到目标Z，概率为1；反之，概率为0[17].

实际上，区域块中的信息是通过多个传感器同时合作来监测的。所以就需要求出这些节点能够监测到目标的联合概率。那么，某个目标z被全部传感器同时感知到的概率是[18]：

(1)

其中n为区域范围中要布置的节点数量，psi是目标Z被第i个节点感知到的概率。

1.2 适应度函数

(2)

2 基于粒子间距调整改进的PSO算法

2.1 PSO算法

粒子群优化算法(PSO)是鸟群中每一只鸟通过自身所得到的信息和其他鸟群得到的信息来更新速度和位置，每只鸟都代表的一个解，通过不停地位置更新和比较来找出那个最优的解。

速度更新公式：

v(i+1)=ω·v(i)+ζ·c1·(p(i)-x(i))+

η·c2·(g(i)-x(i))

(3)

位置更新公式：

x(i+1)=x(i)+v(i+1)

(4)

2.1 PSO算法的改进

2.1.1 惯性权重系数ω

PSO中的惯性权重系数ω的意义是调节PSO的收敛速度和均衡个体的搜寻精度，较大的ω有较好的全局搜索，而较小的ω则更有助于更精确的搜索，因此对ω进行了改进：

(5)

t为当前迭代次数，itermax为最大迭代次数，r∈rand(0，1)；在迭代初始时，ω是趋于ωmax，收敛变快，后期ω趋于ωmin，缩小搜索范围，收敛速度随之也变慢性权重调整PSO(W-PSO)相比基本PSO有较好的收敛性。

2.1.2 粒子间距调整

在粒子寻优的过程中，粒子总会出现越过区域边界或者粒子相撞等情况，这样粒子的多样性会减少，从而搜索能力也会减弱[10]。之前的论文提出过处理粒子越界问题，在粒子超出区域界线时，取此维度的边界值；第一种解决方法是粒子在当前维度的速度大小不改变，方向取相反方向；第二种解决办法是将这些超出边界的粒子淘汰，这些粒子既没有代入到适应度函数中计算，也不参与比较和更新[11]。这三种方法随着迭代增加，会造成多样性丢失。

本文引入调整两两粒子间距来增添多样性。粒子更新过程中可能会出现越过界或叠加，所以需要采取以下措施将叠化粒子分离开。设定粒子之间最小距离为Δd，当粒子之间距离小于Δd，同一维数对应的两个粒子过于靠近。进行粒子间距调整。即：

(6)

2.1.3 增强粒子探寻能力

在迭代后期，由于速度变慢或者趋近于零，所以算法的求解能力会减弱。此时，粒子速度接近于零，只能在最优的那个粒子周围移动，其余的粒子也会汇聚在局部最优的周围。而且在整个聚集过程中，不会出现其他更优的点。存在无法跳出局部最优的可能。在更新粒子时，每个粒子会预先有p(1，2，…，m)个虚拟的前进方向，即粒子向m个方向前进后记录适应值，然后再回到原来的位置。对这m个位置进行求解[16]。求得的解与此时的最佳值对比，如果优于当下的最优解，则这个解作为一个待选值。粒子的更新方程如下：

(7)

其中p代表第p个试探的方向，step为步长，step∈(0，1).

(8)

(9)

其中，rand0，rand1，rand2∈(0，1)，M为步长，L为监测范围的长度，G是网格粒度。i为当下的迭代值，分子为i+1可以使M的取值更小，搜寻的区域能够更加精细；而且rand1是考虑了粒子在搜索过程中的随机性。M取值随着i的变化而改变，呈线性的关系。从而提高了算法收敛速度；也抑制算法过早地陷入局部收敛，在后期缩短步长M来加强局部搜索能力，有利于精细搜索，寻找更优解。提出的方法不仅改善了方向的集中指向性，而且也优化了步长的选取策略，避免了不必要的搜索，从而提高了节点利用率。

2.2 基于粒子间距调整改进PSO算法步骤

基于粒子间距调整改进PSO算法的过程如下：

(1)初始化种群参数；

(2)适应度值检测；

(3)全局最优和局部最优更新；

(4)如果达到itermax，则结束，否则进行下一步；

(5)粒子速度和位置更新；

(6)判断两两粒子间距，若小于Δd，调整粒子位置；

(7)将粒子当前位置代入到式(8)中可产生m个位置，将m个位置代入到目标函数，比较这m个值和当下的最优解，筛选出更优的解；

(8)转入步骤3，继续运行。

APS-PSO算法是在粒子间距调整和粒子搜索能力两个方向上做出改进，在调整粒子间距的基础上，又通过从不同方向添加虚构粒子来增加粒子特性，从而提高算法性能。

3 仿真分析

对PSO、W-PSO、寻优能力增强型越界免疫PSO(OAEBI-PSO)和APS—PSO进行了Matlab仿真，对比了算法的分布情况、覆盖率、均匀度，APS-PSO的覆盖率、均匀度和稳定性都比PSO和W-PSO算法更优。参数设置如表1.

表1 仿真参数表

图1为30个传感器通过基本PSO算法部署在100 m*100 m的目标域内。图2为进行W-PSO算法后节点的分布情况，因为对惯性权重做出来了改进，所以经过W-PSO算法后的分布情况比基本PSO算法的节点分布稍有所提高，但是不明显。传感器节点的聚集情况仍然较高，空洞也很明显。图3为通过OAEBI-PSO算法优化后的节点分布情况，显然覆盖效果得到了提升，但是仍然存在覆盖空洞、不均匀等问题。图4为进行APS-PSO算法后的节点分布图。显然节点叠加情况有所减少，提高了节点利用率，节点分布比基本PSO算法和W-PSO算法后的分布较均匀，更好覆盖了目标区域避免了能量的浪费。

图1 PSO节点位置分布Fig.1 PSO node position distribution

图2 W-PSO节点位置分布Fig.2 W-PSO node position distribution

图3 OAEBI-PSO节点位置分布Fig.3 W-PSO node position distribution

图4 APS-PSO节点位置分布Fig.4 APS-PSO node position distribution

计算节点间标准差越小，均匀度越好，证明覆盖的质量就好。图5明显可以观察到，APS-PSO的标准差是最低的，即节点分布最均匀，降低了节点冗余，从而提高了节点在监测区域的覆盖。

图5 节点分布均匀性Fig.5 Uniformity of node distribution

图6是基本PSO、W-PSO、OAEBI-PSO和APS-PSO四种算法随迭代次数改变覆盖率曲线的变化。W-PSO覆盖率相比PSO提升并不明显，只升高了0.68%.40次迭代后算法趋于收敛。与PSO算法相比，W-PSO加快了收敛。OAEBI-PSO算法覆盖值与前两种算法对比OAEBI-PSO的寻优能力增强。从图3可以看出节点仍然分布不均匀。APS-PSO比OAEBI-PSO、基本PSO和W-PSO具有较高的区域覆盖率，APS-PSO可达到99%以上，有效的增强个体多样性，可以跳脱出局部最优。APS-PSO的最大覆盖率PSO提高了4.27%，比W-PSO提高了3.59%.比OAEBI-PSO提高了1.57%.

图6 随迭代次数覆盖率的改变Fig.6 The coverage varies with the number iterations

表2给出了各个算法随着迭代次数增加相应的覆盖率的变动，表2和图6可以观察出，PSO和W-PSO在求解后期覆盖率几乎不变。在后期，PSO和W-PSO可能出现了局部收敛，W-PSO在ω上做出了改进，虽然加快的算法收敛但仍然没有避免粒子早熟。OAEBI-PSO算法寻优能力有了显著提高，但收敛慢，覆盖率还有待进一步提高。本文的APS-PSO算法收敛快，寻求解的能力有所提升，也没用过早的陷入局部最优。

表2 覆盖率被迭代次数所影响结果

为了进一步分析基本PSO、W-PSO、OAEBI-PSO和APS-PSO四种算法的有效性和稳定性，图7给出了四种算法通过50次蒙特卡罗实验后的得出的覆盖率曲线。观察到APS-PSO的稳定性较好。通过APS-PSO所能获得的覆盖率也大多分布在95%以上。相比另外三种算法有较好的有效性和稳定性。

4 结论

WSN中覆盖优化的改善能够提高网络的覆盖率，使传感器得到充分的利用，使耗能更加均衡，从而有效的监测到或传递目标区域内的各项数据。论文采用覆盖率和节点使用率作为目标函数，在基本PSO算法基础上，通过调整粒子间距和增强粒子搜索能力对算法做出了改进，在添加自身个体和种群多样性同时，改善节点叠化情况，抑制陷入局部最优，从而来提高算法解的质量。也有效缩减了成本，节约资源，提升了WSN的覆盖质量。在实际工作中可以更好的去跳出局部最优，使节点覆盖更加均匀，从而用更少的节点来覆盖监测区域。