自主多决策粒子群的无线传感器网络覆盖优化

李思成，魏云冰，邱永露

(1.上海工程技术大学电子电气工程学院，上海 201600；2.浙江亿安电力电子科技有限公司，浙江杭州 311300)

0 引言

无线传感器网络WSN(wireless sensor network)是一种自组织网络，在环境检测、通信调度、数据隐私保护等方面均有广泛应用。在WSN的实际应用中，网络区域覆盖是至关重要的一环，通过优化传感器网络覆盖分布，不仅能提高网络生存能力，还能减少网络构建成本[1]。

近年来，受生物学启发，群智能优化算法得到迅速发展，在WSN覆盖优化问题中有了广泛应用。文献[2]提出了一种混沌萤火虫算法的WSN节点部署策略，在相同网络覆盖的情况下，需要的WSN节点更少，但网络覆盖率仍有优化空间；文献[3]提出一种改进鲸鱼优化算法的网络覆盖优化策略，收敛速度大幅优于基本鲸鱼优化算法，但覆盖率提升有限；文献[4]将模糊粒子群算法应用到WSN覆盖优化中，具备以较少节点获取较高覆盖率的优势，但缺少增加收敛速度相关方面的优化，且最终未能给出节点数与覆盖率之间平衡点；文献[5]将改进蚁狮优化算法用于网络覆盖优化，收敛速度和覆盖率均有明显提升，但依旧存在算法易陷入且无法跳出局部收敛的问题。文献[6]提出一种使用萤火虫算法的WSN覆盖方法，改善了网络节点利用率低的问题，却仍存在节点均匀度不佳的情况。上述智能优化算法虽在无线传感器网络覆盖优化中展现出各自优势，但仍具备相应的进步空间。

粒子群算法(particle swarm optimization，PSO)作为最早出现的算法之一，其结构简单，调节参数少，易于实现，在图像、医学、电力等领域得到广泛应用。然而，基本粒子群算法性能已难以满足现代工程需求，许多学者针对现有粒子群算法的缺陷作出改进，文献[7]提出结合重开端和反向学习策略提高了PSO的收敛和突破局部最优陷阱的能力，但其初始解质量较差，导致最终结果提升有限；文献[8]通过引入Logistic混沌映射，令粒子群的初始分布质量得以提高，并在一定程度上改善粒子陷入停滞的问题，但Logistic混沌映射相对其他混沌映射优势不明显，提升效果不佳。尽管各位学者对粒子群从不同方面提出改进，但不同的改进方案均存在不同方面的缺陷，如何平衡粒子群算法各方面性能的提升成为难点。

为了实现WSN覆盖率的最大化，针对现有粒子群算法的缺陷，本文提出一种自主多决策粒子群算法(autonomous multi decision particle swarm optimization，APSO)，通过赋予粒子不同的个体和社会思维，让粒子具备自主思维，通过自我认知不断优化调整更新策略来提高算法性能，并将该算法应用到WSN节点覆盖优化中。通过对16个benchmark测试函数的优化对比，验证了APSO的有效性；并将APSO与其他算法应用于WSN覆盖优化中，对比不同算法结果以验证APSO应用价值。

1 WSN节点覆盖模型

设在某二维监测区域上随机部署N个传感器节点，则节点集可由矩阵表示，其中zi的坐标为(xi,yi)，i=1，2，…，N，每个节点感知半径为rs，通信半径为rc。本文采用布尔模型作为节点感知模型，将该区域离散为m×n个像素点，目标像素点hj的坐标为(xj,yj)，则hj与传感器节点间的距离为：

(1)

当像素点hj在节点zi的感知范围内时，感知质量为1，否则为0。数学表达式如下：

(2)

则hj在WSN中被覆盖的概率为：

(3)

因此WSN的覆盖率可以定义为：

(4)

2 基本粒子群算法

PSO算法是J. Kennedy和R. Eberhart提出的一种群智能优化算法[9]，它的灵感源于鸟类群集的社会行为，这种行为利用个体(粒子)在搜索空间中飞行来寻找问题的最优解。

粒子在迭代过程中受到它们自身最佳位置以及群体最优位置的影响，其速度和位置调整公式如下：

(5)

(6)

惯性权重w关系着算法的全局平衡与局部搜索能力。为了提升算法性能，Y. Shi提出一种线性递减惯性权重策略[10]，表达式如下：

(7)

式中：wmax为w的最大值，wmax=0.9；wmin为最小值，wmin=0.4；t为当前迭代次数；T为最大迭代次数。

在PSO算法中，学习因子c1、c2的动态调整是赋予粒子不同思维的一种方式，良好的学习策略是提高算法性能的重要手段。

3 自主多决策粒子群算法(APSO)

3.1 精英混沌映射

在群智能优化算法中，初始种群的质量关系到算法的收敛速度和寻优精度[11]，所以许多学者在优化问题中使用混沌，在保证种群的多样性的同时，还能改善算法全局搜索能力[12]。Tent映射[13]和Logistic映射[14]是最常见的混沌模型，常用来初始化种群。图1为Logistic映射、Tent映射以及Bernoulli映射[15]生成值的频率图。

(a)Logistic映射

(b)Tent映射

(c)Bernoulli映射图1 映射生成值频率对比图

由图1可知，Logistic映射在[0,0.1]和[0.9,1]的取值概率较大，Tent映射会形成高低起伏的不均匀状态。相较于前两者，Bernoulli映射遍历更均匀，是更好选择，其表达式如下：

(8)

式中：k为混沌迭代次数；zk+1为第k+1次映射值；λ一般取0.4。

但是单一的Bernoulli混沌映射在面临多种群复杂优化问题时会存在适应性差，混沌行为不连续，从而导致映射遍历度下降的问题[16]，针对这一情况，本文提出一种混沌精英映射。这种映射由Bernoulli映射与Logistic映射耦合构成，是一种多维度混沌，在保持原有的历遍性的同时大幅改善混沌行为不连续的情况[17]，定义表达式如下：

(9)

式中γ的取值范围为(0，4]。

式(9)产生的混沌序列再依照式(10)映射到解的搜索空间内：

xid=xL+(xU-xL)·zid

(10)

式中：xid为粒子i在第d维的位置；xU和xL分别为xid取值的上下限；zid为式(9)产生的粒子i在第d维的值。

3.2 具有自主多决策思维的粒子群算法

在采用群体智能算法求解最优化问题中，比较理想的方法通常分为两个阶段：

(1)在算法迭代初期个体分散在整个搜索空间；

(2)在迭代后期利用收集到的信息收敛到全局最小值。

在PSO中，通过微调参数和，即可平衡这2个阶段，以快速的收敛速度找到全局极值。本文引入3种学习因子(ST1，ST2，ST3)更新策略[18-20]，随机赋予粒子自主多决策思维：

ST1的表达式为：

c1=c1max-(c1max-c1min)(t/T)

(11)

c2=c2min+(c2max-c2min)(t/T)

(12)

式中：t为当前迭代次数；T为最大迭代次数；c1max和c1min分别为c1的初值和终值；c2max和c2min分别为c2的终止和初值。

ST2的表达式为：

c1=c1max-(c1max-c1min)(t/T)2

(13)

c2=c2min+(c2max-c2min)(t/T)2

(14)

ST3的表达式为：

(15)

(16)

当c1max=c2max=2，c1min=c2min=0.5，T=500时，ST1～ST3的图像如图2所示。

图2 多决策学习因子示意图

由图2可知，3组曲线具有不同的初始斜率和曲率，这表明粒子将按照3种不同的思维调整自身飞行速度。在ST1中，曲线的斜率不随迭代次数变化，这表明，粒子自我认知能力下降的速度与社会认知能力上升的速度相同；在迭代中点t=250处两者达到相等，此时它们受到自身及群体影响的程度相同。在ST2中，粒子的自我认知能力下降缓慢，在迭代前中期粒子具有更强的自我认知能力，受到自身影响更大，粒子更善于通过了解自身的不足来调整飞行速度。在ST3中，粒子的社会认知能力迅速上升，在迭代前期自我认知能力较强，而在随后的更长时间里，粒子具有更强的社会认知能力，更容易被社会所影响，它们更多的通过寻找自身与其他粒子的差距来调节飞行速度。

3.3 交替扰动策略

PSO具备优异的全局搜索能力，但是局部搜索能力较差，算法迭代至后期极易陷入局部收敛[21]，许多学者会通过高斯变异、柯西变异等方式打破局部收敛，增加算法全期多样性。柯西变异分布具有两端分布较长，中间概率密度大的特点，相较于高斯变异，柯西变异搜索步长宽阔，能产生更大的扰动[22-23]。但由文献[24]可知,若将柯西变异与另一扰动策略糅合并交替执行，可进一步提高算法寻优性能。为改善PSO易局部收敛的情况，本文提出一种由柯西变异与反向学习融合的交替扰动策略。

若将反向学习引入PSO中，则是在每次迭代得到当前解的基础上，求出反向解，再通过贪婪算子保存所有解中的最优进入下一次迭代。公式如下：

(17)

(18)

接着引入柯西变异算子干扰全局最优粒子，促使粒子跳出限制继续搜索。公式如下：

x′=gbesti+gbesti·cauchy(0，1)

(19)

式中：x′为扰动后最优粒子的位置；cauchy(0,1)为标准柯西分布，其随机变量生成公式为η=tan[(ξ-0.5)π]。

在上述2种策略中，首先通过反向学习求得最优解的反向解，扩大寻优搜索范围。然后再通过柯西变异对最优解进行扰动，打破PSO陷入局部收敛的情况。至于2种策略如何选择，则通过选择概率Ps决定[25]，定义如下式：

(20)

式中θ通常取值为1/20。

通过比较随机数rand∈(0,1)与选择概率Ps的大小决定当前扰动策略，若Ps>rand，则使用反向学习扰动最优结果，若Ps

4 覆盖优化策略

采用APSO对WSN节点位置进行优化，旨在最大化监测区域覆盖率。即求得这些节点的最优位置，使得适应度函数Rcov最大。算法中每个粒子代表一种覆盖分布，将节点位置寻优过程抽象为粒子在空间中寻找最优解的过程，算法流程如图3。

图3 APSO覆盖优化流程图

具体步骤如下：

步骤1：初始化传感器节点数，感知半径，监测区域边长等，初始化算法的种群数量，采用精英混沌映射初始化粒子位置，随机生成初始粒子速度。

步骤2：以Rcov为目标函数，计算所有粒子适应度值，将个体最优位置存储到pbest，将全局最优位置存储到gbest。

步骤3：按式(7)更新惯性权重w。

步骤4：随机选择学习策略，按ST1～ST3中一种方式更新自我学习因子c1和社会学习因子c2。

步骤5：按式(5)、式(6)更新速度和位置。

步骤6：计算适应度值并更新个体与全局最优。

步骤7：按照式(20)更新Ps，比较Ps与随机生成数rand大小。

步骤8：若Ps>rand，利用式(17)、式(18)对全局最优粒子进行反向学习扰动。反之，利用式(19)进行柯西干扰。按照贪婪法则更新最优粒子。

步骤9：重复步骤3～步骤7，直到满足结束条件，输出最优覆盖率和节点部署的位置坐标。

5 仿真实验

5.1 典型测试函数实验

为了证明APSO的性能强度佳，在MATLAB 2020a中分别采用PSO、IPSO1、IPSO2、IPOS3和APSO对表1所示的测试函数求解，16个测试函数均为benchmark函数[26]，其中函数f1～f7用以证明算法的寻优精度，函数f8～f16可以检验算法全局搜索能力和打破局部收敛能力。在测试中，各算法的参数设置如表2所示，其中，所有算法的w按照式(7)线性递减，除PSO外，所有算法按式(17)～式(20)进行交替扰动，APSO按式(9)、式(10)进行初始化。初始化种群规模为40，最大迭代次数为500，每种算法独立运行30次，统计30次实验的平均值和标准差。

表1 测试函数

表2 算法参数设置

5.1.1 收敛精度比较

各算法的测试结果如表3所示，由寻优结果可知，相较于其他3种改进后的PSO，APSO在16个基准测试函数上的收敛速度更快，寻优精度更高，稳定性更强，不易陷入局部收敛，表现出良好的寻优性能。

表3 典型测试函数优化结果对比

5.1.2 收敛曲线对比分析

图4为测试函数在16种算法下的9幅典型的收敛曲线图，结合图4与表3，可以看出对于函数f1～f16，APSO在寻优精度上明显优于其他4种算法。接下来针对APSO的寻优精度和收敛速度等性能进行分析。

(a)f1

(b)f2

(c)f3

(d)f4

(e)f5

(f)f7

(g)f9

(h)f10

(i)f11图4 测试函数迭代曲线

首先，从f1曲线图可知，APSO在迭代到150次时陷入局部收敛，但继续迭代120次后打破最优，最终结果精度比PSO计算所得结果精度有104数级的提升。此外，在函数f1、f2、f5、f7、f9的迭代曲线图中，IPSO1、IPSO2、IPSO3的结果精度相较PSO均有不同程度的提升，验证了引入多种学习思维的必要性。

其次，对于函数f1～f16，APSO在寻优精度上明显优于其他4种算法。虽然APSO在f2、f5函数中在迭代初期就陷入最优，但其最终结果精度相较其他4种算法都有着101～103数级的提升，表明APSO经过精英混沌映射初始化在迭代初期就有着较高的种群多样性。

最后在函数f7，f9，f10，f11的迭代图中可以看到，PSO极易陷入局部最优从而导致结果精度较差。在f7中，IPSO1、IPSO2、IPSO3能在一定程度上打破局部最优且效果较为明显，但在f9、f10中，这3种改进算法提升有限，甚至在f11中表现出负作用。说明了采用某种单一的学习策略改进的PSO在特定函数上能表现出良好的寻优性能，但其无法适应其他特征函数的求解。而APSO在这4种函数的迭代全周期均表现良好，不仅收敛速度快，还能持续突破局部收敛，证实了交替扰动策略的重要性，令APSO在迭代寻优过程中不失种群多样性。

综上所述，16个测试函数的实验证明了拥有自主思维的APSO相对PSO寻优性能提升明显，且稳定性好，表现出强大的竞争力。反映了APSO在面对不同优化问题时，能够表现出良好的适应性。

5.2 网络覆盖优化实验

为了验证APSO应用于WSN覆盖优化的性能，在MATLAB 2020a中分别将标准PSO、APSO与文献[5]中的改进蚁狮算法(improved ant lion algorithm,MS-ALO)和文献[6]中的萤火虫算法(firefly algorithm,FA)进行对比实验，实验参数依照其他文献格式设置。

其中与萤火虫算法对比实验是将PSO、APSO、FA共同运算对比结果。与改进蚁狮算法对比试验是将PSO、APSO按照文献[5]中的参数运算，结果与文献[5]提供的数据进行对比。

5.2.1 与萤火虫算法对比

在50 m×50 m的二维监测区域中进行仿真，设置感知半径rs=5 m，通信半径rc=10 m，各算法种群规模为40，最大迭代次数为100。其中PSO和APSO参数与表2相同，FA参数设置与文献[6]中相同。

为保证客观性，每种算法独立进行20次覆盖优化实验。图5为节点数N=30时，各算法的迭代曲线，图6为N=30时优化后节点分布图，表4为N=30时随机抛洒、PSO、FA和APSO的覆盖优化结果。

图5 N=30覆盖优化迭代曲线

(a)随机抛洒

(b)FA优化

(c)PSO优化

(d)APSO优化图6 N=30节点部署

表4 N=30优化结果对比 %

由图6和表4可知，APSO相比FA、PSO、随机抛洒的覆盖率分别提升1.69%、6.96%、30.45%，有效改善传感器节点分布不均匀，覆盖盲区大的缺点。由图5可知，APSO迭代初期覆盖率与PSO相仿，但在迭代30次后，APSO覆盖率与PSO覆盖率差距逐步扩大，说明APSO在优化网络覆盖时具有较快的收敛速度、较高的计算精度。

为了进一步验证APSO优化传感器网络覆盖的可行性，改变节点数量，对比3种算法的优化结果。得到如图7所示的迭代曲线对比图和表5所示的网络平均覆盖率数据。

(a)N=35

(b)N=40图7 N=35～40优化迭代曲线对比

表5 N=35～60时网络平均覆盖率 %

由表5可知，在不同节点数量下，采用随机抛洒节点部署策略，覆盖率较低，存在大量冗余节点和覆盖漏洞。采用PSO优化的网络覆盖率得到较大提高，但仍存在较多的冗余节点，且节点数达到40后，覆盖率几乎不随节点数增长而增加。而采用APSO算法部署后的网络覆盖率均要高于其他策略，较大程度减小了覆盖漏洞。

另外，在图5、图7所示迭代优化过程中，APSO算法在迭代30次后的覆盖率均高于PSO和FA的寻优结果，优化效果提升明显，验证了该算法在WSN覆盖优化中的可行性。

最后，从表4和表5中的数据中可以看出：随着节点数量增加，网络节点的覆盖率均得到较大提升，且采用群智能算法优化后的覆盖率远高于直接进行随机抛洒产生的覆盖率。但PSO在不同节点数量下的覆盖优化效果欠佳，而APSO的覆盖率分别在节点数为35、40、45、50时比PSO高6.30%、3.47%、6.03%、6.15%，比FA高1.86%、1.28%、2.26%、2.09%。在相同节点数量下，APSO优化后的覆盖率最高，说明APSO全局搜索能力更强，在同等条件下节点利用率更高，网络覆盖效果更好。

5.2.2 与改进蚁狮算法对比

对比改进蚁狮算法的实验场景为100 m×100 m的二维监测区域，设置感知半径rs=7 m，通信半径rc=14 m，像素点数为101×101，各算法种群规模为40，迭代次数为100，PSO、APSO参数仍参照表2。

为保证实验客观性，每种算法独立进行20次覆盖优化实验。图8为节点数量N=60时，PSO、APSO优化后节点分布图，图9为节点数量N=60时，PSO和APSO的覆盖优化迭代曲线，表6为PSO和APSO的覆盖优化结果。

(a)APSO优化

(b)PSO优化图8 N=60节点部署

图9 N=60时覆盖迭代优化曲线

表6 N=50～80时网络平均覆盖率 %

由图8和表6可知，同等实验环境下，APSO优化覆盖率分别在N=50,60,70,80时比MS-ALO高0.96%、0.34%、4.08%、1.09%，比PSO高4.11%、5.09%、9.17%、6.77%。验证了APSO具备更优异的运算性能。

此外，从图9可以看出PSO在50次迭代左右便陷入局部最优，APSO不仅收敛速度优于PSO，且不易陷入局部最优，表明引入交替扰动策略可打破收敛，进一步提高算法的收敛精度。

6 结束语

本文针对WSN中随机节点部署方法覆盖盲区大、节点利用率低的问题，提出一种自主粒子群算法的传感器网络覆盖优化策略。该算法在传统算法基础上，采用精英混沌映射初始化种群位置，增加种群多样性，提高全局搜索能力；其次，引入3种学习因子更新策略，赋予粒子不同于种群的自主学习思维，平衡算法的全局和局部搜索能力；然后，引入交替扰动策略对最优粒子进行扰动，提高粒子跳出局部最优的能力。在MATLAB 2020a中采用4个典型测试函数进行测试后，得出以下结论：

(1)在16个benchmark测试函数实验中，函数f1～f7表明APSO的收敛速度和计算精度远优于PSO，函数f8～f16表明APSO打破局部最优能力强，面对不同的优化问题均表现出良好的适应性。同时，APSO对比PSO，证实了精英混沌映射的重要性，对比IPSO1、IPSO2、IPSO3的数据结果，验证了自主学习思维与交替扰动策略的重要性。

(2)在WSN覆盖实验中，APSO优化后的覆盖率在不同节点数下，比PSO高2.26%～9.17%，比FA高1.26%～2.26%，比MS-ALO高0.34%～4.08%。表明APSO适应性强，能够快速有效提升网络覆盖率，增加节点部署性价比。