粒子群智能优化算法在无线传感器网络覆盖中的应用

甘娜

摘要：针对无线传感器网络覆盖的问题，提出一种求解无线传感器网络覆盖问题的粒子群智能优化算法。该算法在粒子群算法的基础上，对PSO算法适应度函数加入选择算子的关联。通过无线传感器网络覆盖的仿真，实验结果表明，该优化算法既克服了PSO算法陷入局部最优的不足，又提升了收敛精度。在提高传感器节点覆盖率、网络负载均衡等方面有较好的效果。

关键词：无线传感器;网络覆盖;覆盖度;PSO算法

中图分类号：TP393      文献标识码：A

文章编号：1009-3044（2022）21-0028-02

开放科学（资源服务）标识码（OSID）：

无线传感器网络覆盖是根据被监测目标或区域的分布情况，无线传感器节点间相互通信，采集和处理覆盖区域中监测对象的信息，并发送给监测者[1]。网络覆盖优化目标是要保证目标区域尽可能被网络内的节点覆盖[2]。

粒子群算法（PSO）在求解无线传感器网络覆盖问题中很难得到最优值，针对以上问题，本文在PSO算法的基础上，适应度函数中加入选择算子的关联，提出粒子群智能优化算法，求解无线传感器网络覆盖问题中传感器节点覆盖度、负载均衡等性能指标。仿真结果表明，该算法克服了PSO算法收敛精度较低、陷入局部极值的不足，证明了粒子群智能优化算法解决无线传感器网络覆盖问题的有效性。

1 无线传感器网络覆盖模型

1.1无线传感器网络覆盖模型描述

定义一：感知模型。假设传感器节点[Si0

传感器节点[Si]感知范围：

[RSi=x-xi2+y-yi2]                              （1）

其中[RSi≤ri]。

定义二：邻居节点。传感器节点[Si]的通信范围是以[rj]为通信半径的圆。当两个传感器节点的距离小于或等于节点的[rj]时，这两个节点互为邻居节点。

传感器节点[Si]的邻居节点为：

[NSi=xi-xj2+yi-yj2]                             （2）

其中[RSi≤rj]。

定义三：覆盖率。

网络监测区域覆盖率：

[Npk=1n1≤i≤n1-1≤i≤n1-xi-xj2+yi-yj2]      （3）

1.2 无线传感器网络覆盖目标约束函数

1.2.1 覆盖度目标约束函数

当传感器节点正确地覆盖监测区域，网络才能够顺利获取监测的数据，完成监测任务[3]。覆盖率[Np]为监测区域内所有节点覆盖的面积与监测区域面积之比，覆盖率优化问题的目标函数的定义如下：

[Np=Npkm×n]                          （4）

1.2.2网络性能分析目标约束函数

负载均衡关系到是否可以合理分配传感器节点源，提升网络的监测能力和质量[4]，提升传感器节点的利用率。因此，负载均衡也是无线传感器网络覆盖中重要的优化目标。优化需求可以转化为目标约束函数，如下：

[factor=1-Si-averageSilastSi+averageSilast]                        （5）

其中，[averageSilast]表示传感器节点[Si]在上一次迭代中的平均执行时间。

传感器节点的负载均衡因子factor越高，则传感器节点的综合能力越强。

负载均衡目标函数如下：

[load_balance=n/i=1mj=1nSim]                           （6）

其中，[i=1nj=1mSi]表示完成任务集所需的执行时间。由式（6）可知，[load_balance]的值越大，则传感器节点利用率越高，负载越均匀。

2  粒子群智能优化算法

2.1标准粒子群算法

假设搜索空间为[d]维，粒子总数为[n]，粒子[i]在时刻[t（t>0）]在搜索空间中所处的位置为[Xidt]，粒子在搜索空间中运动速度为[Vidt]，代表飞行的方向和速度[5-6]。在搜索过程中，粒子[i]（[1≤i≤n]）按公式（7）（8）來更新其速度和位置：

[Xidt=Xidt+Vidt]                    （8）

其中[C1]、[C2]为粒子的学习因子，表示粒子对个体经验与群体经验的依赖程度，[w]是惯性权重，[t]为迭代次数，[r1]、[r2]为均匀分布在区间[0，1]上的随机数。

飞行历史中粒子的个体最优位置为[Pidt]，整个种群中所找到的全局最优位置[Pgdt]为所有粒子的[Pidt]中的极值，通过公式（9）（10）更新个体最优[Pidt]和全局最优[Pgdt]，向最优位置搜索移动。

[Pgdt=argminPidtfPidt]                  （10）

2.2粒子群智能优化算法

为了克服PSO算法求解无线传感器网络覆盖问题，陷入局部极值及收敛精度较低等缺点[7-8]，本文设计了一种粒子群智能优化算法，对PSO算法适应度函数加入选择算子的关联，以提升算法的收敛精度，克服PSO算法易陷入局部最优的不足。算法改进和优化主要体现在两个方面：

第一，为避免过早陷入局部最优的问题，采用实数编码的方式，产生一群更适应问题环境的种群;

第二，为避免收敛精度较低的问题，对适应度函数中引入选择算子，选择适应度值较好的粒子，进行更精细的局部搜索，获取问题的最优解。

通过改进后的公式（11）选择适应度值最优的粒子：

式中[Pgdt]为下一代种群的个体，[Vgdt]是目前为止最优个体，[Ogdt-1]是目前为止适应值较好的个体。

3 算法流程

Step1：编码。优化数值，产生一群更适应问题环境的种群。

实数编码方式如下：

[ρ=12nt=1n2tbi]                               （12）

其中[ρ]为编码实数，[n]为二进制编码位数，[bi]为第[i]位的二进制值。

Step2：产生初始种群。设置搜索空间为[D]维，粒子的数量为[M]，设置最大迭代次数，搜索最优解;其中第[i]个粒子位置[χ]，第[i]个粒子的飞行速度[υ]，获取学习因子[c1]，[c2]，[c3]和惯性权重[ω];

Step3：对粒子的优化问题进行求解。初始化粒子群，粒子数量变量取值范围内随机初始化粒子的速度和初始位置，根据粒子速度和位置函数（7）（8）算出粒子所经历的最好位置;

Step4：评价粒子群中每个粒子的适应度值，找出各个粒子的适应度最佳值和群体适应度最佳值。根据覆盖率适应度函数（11）算出粒子的适应度最佳值，更新各个粒子的速度与位置，算出粒子各自的适应度值;继续下一次迭代，而适应度值低的粒子被舍弃;

Step5：根据问题的目标函数更新粒子适应度值，更新个体最优位置和领域内的最优位置;

Step6：将种群最优粒子组成一个群体，进入下一次迭代，更新局部最优解和全局最优解;

Step7：将粒子群中最优粒子组成一个群体，判断是否最大迭代次数？条件为真，则输出最优值，算法结束。条件为假，则转到Step 4，进行下一次迭代。

4  数值仿真与性能分析

本文将PSO算法与粒子群优化算法在无线传感器网络覆盖中的应用进行仿真实验结果对比。实验使用式（4）和式（6）作为算法中所需要评价的目标函数，通过Matlab仿真平台来模拟无线传感器网络覆盖过程，评价传感器节点覆盖度、负载均衡程度等指标。

本实验假设监测区域[30×30m]、传感器节点数目为40的情况下，进行无线传感器网络覆盖优化。粒子群优化算法参数设置如下：设定粒子群的初始规模为250，主群最小规模限制为50，粒子维度5，学习因子0.5～2.5，惯性权重0.4～1.0，最大迭代次数200。

无线传感器网络覆盖优化方案中，在不同传感器节点数目的情况下，从图1可以看出，在传感器节点覆盖度方面，粒子群智能算法优于PSO算法。

从图2可以分析出，粒子群智能算法传感器节点的负载均衡程度高于PSO算法。该算法克服了陷入局部最优解，具有较好的全局搜索能力。

5  结论

本文将粒子群智能算法应用到无线传感器网络覆盖优化问题中，设计了一种粒子群智能优化算法，对PSO算法适应度函数加入选择算子的关联，利用感知模型，以区域覆盖率和负载均衡程度为目标函数，算法收敛精度高，克服PSO算法易陷入局部最优的不足，提高传感器网络覆盖的质量和效果，优化无线传感器网络性能。

参考文献：

[1]范兴刚，杨静静，王恒.一种无线传感器网络的概率覆盖增强算法[J].软件学报，2016，27（2）：418-431.

[2] 周杰.基于进化算法的大规模无线传感器网络覆盖关键技术研究[D].北京：北京邮电大学，2015.

[3] 神显豪，李军，奈何.感知受限的移动传感器节点扫描覆盖优化算法[J].计算机应用，2017，37（1）：60-64，102.

[4] 王伟，朱娟娟，万家山，等.基于混沌量子粒子群算法的无线传感器网络覆盖优化[J].传感技术学报，2016，29（2）：290-296.

[5] 马发民，张林，王锦彪.粒子群算法的改进及其在优化函数中的应用[J].计算机与数字工程，2017，45（7）：1252-1255，1293.

[6] 林诗洁，董晨，陈明志，等.新型群智能优化算法综述[J].计算机工程与应用，2018，54（12）：1-9.

[7] 吴定会，高聪，纪志成.混合粒子群算法在微电网经济优化运行的应用[J].控制理论与应用，2018，35（4）：457-467.

[8] Arora S，Singh H，Sharma M，et al.A new hybrid algorithm based on grey wolf optimization and crow search algorithm for unconstrained function optimization and feature selection[J].IEEE Access，2019，7：26343-26361.

【通聯编辑：唐一东】