自适应混沌PSO算法在WSN覆盖优化中的应用*

赵亚梅，陆安江

（贵州大学 大数据与信息工程学院，贵州 贵阳550025）

0 引 言

无线传感器网络（WSN）可以由几个或几百个甚至上千个节点组成。这些节点被称为传感器节点，且具有传感、数据处理和通信的能力。换句话说，无线传感器网络由独立的嵌入式系统组成，可以通过传感器与其环境进行交互和信息处理，并将这些信息与邻居进行通信。因此，无线传感器网络被认为是一种经济且有前途的技术，可在军事、环境、家庭和工业等领域应用。

无线传感器网络的覆盖问题首先要面临的基本问题是无线传感网络的配置。无线传感器网络一般采用随机覆盖的方式进行撒点，节点会分布在区域的任何地方。近年来，在无线传感器网络的覆盖问题上，已经有很多学者做了大量研究。文献[1]在存在静态节点和少量可动节点的混合WSN中，将自然选择的思想与粒子群算法相结合，提出了自然选择粒子群算法。它所使用的Neyman-Pearson感知模型考虑了误警率因素，使自然选择粒子群算法更加贴合实际。文献[2]在混沌量子粒子群的基础上引入了种群分布熵和平均粒距，提出了自适应混沌量子粒子群优化算法。相比标准粒子群算法和混沌量子粒子群算法，该算法收敛更快，并提高了覆盖率，但算法耗时是混沌量子粒子群算法的2倍。文献[3]针对粒子群中会有传感器节点分布不均匀以及覆盖区域出现重复覆盖和未覆盖等的情况，提出了一种在粒子群算法中引入混沌方法的优化算法。

粒子群算法中，粒子容易陷入局部最优值无法逃脱，导致WSN的覆盖不均匀。本文将自适应混沌PSO算法应用于WSN覆盖，将能实时反映粒子群变化情况的群体进化程度和相对聚集程度控制惯性权重，以提高粒子群的自适应能力，增强寻优能力。在迭代次数增加的过程中，算法还引入了混沌策略，使部分粒子能够摆脱早熟，且用适应度方差来确定粒子群何时出现早熟现象。

1 WSN覆盖问题模型

假设WSN监测区域M是一个二维平面。将该监测区域M分割为p×l个网格点，再将网格点简化为像素点[4]。本文采用文献[5]中的二元感知模型计算无线传感器网络覆盖率。在该监测区域内，随机撒m个相同的传感器节点，每个传感器节点的感知半径是r，通信半径是R(R=2r)。传感器节点集表示为C={c1,c2,c3,…,cm}，其中第i个传感器节点为ci=(i=1,2,…,m)，传感器节点的坐标为(xi, yi)。设实验区域内像素点F的坐标为(xF, yF)，则传感器节点对像素点覆盖的概率模型为：

当一个像素点F同时被几个传感器节点覆盖时，该像素点被覆盖的概率pF取1[6]。根据式（1）得出，pF的取值只有0或1，表示像素点F是否被部署的无线传感器网络覆盖。因此，在监测区域M内，像素点被覆盖的总数为∑p×lpF。由上述可知，网络覆盖率是指像素点的覆盖面积与WSN实验区域M的比值，即：

也是无线传感器网络覆盖的目标函数。

2 粒子群优化（PSO）算法

粒子群优化（PSO）算法的基本概念是源于对鸟群觅食行为的研究。在PSO中，每个优化问题的可能解都可以想象成d维搜索空间上的一个点，这个点被称为一个粒子。每一个粒子的适应值（Fitness Value）由目标函数决定。粒子的速度决定飞行空间里的方向和距离。这个速度根据它本身的飞行经验和同伴的飞行经验进行动态调整，然后粒子们就追随当前的最优粒子在解空间中搜索。假设在n维粒子搜索空间中有m个粒子，粒子i的位置表示为xi={xi1,xi2,…,xin},{i=1,2,…,m}，粒子i以速度vi={vi1,vi2,…,vin},{i=1,2，…，m}进行飞行。在算法进化的过程中，粒子在解空间追随最优的粒子进行搜索会产生两个最优解：（1）粒子i经过的最优位置pi={pi1,pi2,…,pin}；（2）所有粒子经过的最优位置pg={pg1,pg2,…, pgn}。于是，粒子的速度和位置的更新公式为[2]：

其中，w(t)为惯性权重系数。惯性权重的大小影响算法的收敛能力。式（5）中，Tmax指最大迭代次数，t表示当前的迭代次数。式（3）中，c1是粒子自身的加速度系数，c2是全局加速度系数，r1(t)和r2(t)是0～1内的随机数，且均匀分布；vij(t+1)是粒子第t+1代的速度，vij(t)是粒子第t代的速度。式（4）中，xij(t+1)是粒子第t+1代的位置，xij(t)是粒子第t代的位置，pij(t)和pgj(t)是粒子i经过的最优位置和所有粒子经过的最优位置[7]。

从式（5）可以看出，w(t)只与最大迭代次数和此时迭代次数有关，没有反映群体进化程度和当前粒子群平均函数值与局部最优解的接近情况，会导致粒子群算法容易产生早熟现象和陷入局部最优。因此，本文提出了一种自适应混沌PSO算法在WSN覆盖中的应用，即将能实时反映粒子群变化情况的群体进化程度和相对聚集程度控制惯性权重，以提高粒子群的自适应能力，增强寻优能力。此外，在迭代次数增加的过程中，部分粒子会产生早熟现象。为此，本文引入了混沌策略，使部分粒子能够摆脱早熟，且用适应度方差来确定粒子群何时出现早熟现象。

3 自适应混沌PSO算法在WSN覆盖中的应用

本文将能实时反映粒子群变化情况的群体进化度和聚集度控制惯性权重w，以提高粒子群的自适应能力，增强群体寻优能力。此外，在迭代次数增加的过程中引入混沌策略，使部分粒子能够摆脱早熟，且用适应度方差来确定粒子群何时出现早熟。

3.1 群体进化程度和相对聚合程度

在定义群体进化程度和相对聚集程度前，假设本算法的目标函数为F，第i个粒子第k次迭代后的适应值为F()，在粒子群中第k次迭代后所有粒子的局部最优值为F()，第k次迭代时所有粒子的全局最优值为F()。

先定义的是粒子群进化到第k次后历史局部最优平均值：

粒子群进化到第k次后，所有粒子的平均适应值为：

粒子群进化到第k次后粒子的全局最优值：

3.1.1 群体进化程度

群体进化程度由全局最优值、局部最优平均值和粒子个体的最优值寻优的程度影响的。因此，用G表示迭代后的粒子群的进化程度，称为群体进化程度：

其中，g1、g2、g3为相关系数，满足g1+g2+g3=1，且g1大于g2和g3。

在式（9）中，方程式第一项反映粒子群是否得到全局最优解，当k-1代的全局最优值小于或等于第k代的全局最优值且二者的比值为1时，说明在k次迭代后粒子群没有进化，即找到了最优解或算法停滞。第二项反映了进化过程中粒子群的整体变化情况。当二者的比值为1时，找到了最优解或算法停滞。第三项反映了粒子i的进化情况。当二者的比值小于1时，粒子i找到最优解；当二者的比值等于1时，算法则趋向于停滞。

3.1.2 相对聚合程度

粒子群的局部最优值是通过当前粒子群的适应值与上一次粒子群的适应值进行对比得到的[4]。当前粒子群的所有粒子的平均适应值与局部最优值的接近程度定义为相对聚合程度J：

根据式（10）可以看出，J的取值范围是0＜J≤1。J越接近1，说明粒子越是聚集在一起。根据群体进化程度和相对聚合程度定义惯性权重wn：

其中w'是惯性权重的原值，a1、a2分别是群体进化程度和相对聚合程度的调节系数，0＜a1,a2＜ w'，且 a1+a2=1。

根据式（11），粒子群中粒子速度的更新公式变为：

3.2 混沌策略

混沌对初值具有敏感性、随机性、遍历性等特征。在算法迭代次数增加的过程中，部分粒子会产生早熟现象。因此，引入混沌策略进行混沌扰动，使部分粒子能够摆脱早熟，并用适应度方差来判断粒子何时出现早熟。本文采用的混沌方程为典型的Logistic方程，表达式为：

式中，u为控制参数。当u=4时，0≤z≤1，Logistic方程处于完全混沌状态。

根据式（13）在算法迭代次数增加的过程中部分粒子会产生早熟现象时，粒子的位置按下式更新：

式中xmin是边界的最小限定值，xmax是边界的最大限定值，zi+1则是由式（13）所决定的，x(t+1)是指粒子t+1代的位置。

3.3 判断早熟收敛策略

在算法迭代次数增加的过程中，判断部分粒子是否会产生早熟现象时，本文采用群体适应度方差的策略，公式如下：

式中，m是粒子群中的所有粒子数；Fi是第i个粒子的适应值；Favg是当前粒子群的平均适应值；群体适应度方差σ2反映粒子群的收敛状态。σ2越小，说明粒子群越趋于收敛。

4 WSN覆盖优化算法步骤

根据第2节对算法参数的设置，本文算法的具体步骤如下：

（1）初始化粒子群中粒子的个数、速度、全局最优解和局部最优解；

（2）根据式（2）求出粒子群的覆盖率；

（3）根据式（5）、式（12）更新粒子的位置和速度；

（4）计算新的覆盖率，若粒子的覆盖率优于自身历史最优覆盖率，用该粒子的覆盖率代替个体最优覆盖率；

（5）对于每个粒子来说，若粒子适应值优于自身历史最优值，则用该粒子位置代替个体最优值；

（6）计算粒子群的群体适应度方差σ2的值，与群体适应度方差比较，如果小于阈值，则执行步骤（7），否则正常执行步骤（8）；

（7）根据式（14），帮助部分粒子摆脱早熟现象；

（8）判断当前迭代数是否小于等于最大迭代数，若满足，则执行步骤（2）；

（9）输出覆盖率。

5 实验仿真

5.1 实验环境

本文的仿真实验平台是MATLAB 2012b，以展示本文设计的自适应混沌PSO算法在WSN覆盖中的效果图。为了验证自适应混沌PSO算法能有效提高无线传感器网络的覆盖率，实验参数设置每一个节点的感知半径为5 m，通信半径为10 m，群体适应度方差的策略的阈值取为0.003 5，参数g1=0.2、g2=0.2、g3=0.6、a1=a2=0.5，在实验环境里迭代次数最大为300，实验区域是边长为50 m的正方形，此区域内放置了50个传感器。

5.2 实验结果的分析

本算法与文献[8]中基本PSO算法和混沌PSO算法相比较，设置相同的实验环境，得出如图1所示的本算法节点覆盖图和如表1所示的三种算法所得到的覆盖率比较。

根据图1可以看出，经过本文算法优化后，无线传感器网络分布得更加均匀，优于基本PSO算法和混沌PSO算法，说明引入群体进化程度和相对聚合程度、混沌策略能帮助PSO算法摆脱局部最优值，最终获得全局最优值。

根据表1可以看出，本文算法在WSN中的覆盖率获得了有效提高，比基本PSO算法的覆盖率提高了9%，比混沌PSO算法的覆盖率提高了5%。

图1 节点覆盖情况

表1 本文算法与其他算法覆盖率的比较

6 结 语

对于粒子群算法容易产生早熟现象和陷入局部最优的问题，本文提出了一种自适应混沌PSO算法。算法在WSN覆盖中的应用，是将能实时反映粒子群变化情况的群体进化程度和相对聚集程度控制惯性权重，以提高粒子群的自适应能力，增强寻优能力。此外，在迭代次数增加的过程中，部分粒子会产生早熟现象。因此，引入混沌策略进行混沌扰动，使部分粒子能够摆脱早熟，并用适应度方差来判断粒子何时出现早熟。实验表明，所提算法比基本PSO算法和混沌PSO算法能有效提高WSN的覆盖率。