一种增强型麻雀搜索算法的无线传感器网络覆盖优化研究∗

王振东，汪嘉宝，李大海

(江西理工大学信息工程学院，江西 赣州 341000)

随着互联网技术，人工智能和5G技术的不断发展，物联网已经成为当下科技领域热门的研究对象。而无线传感器网络作为物联网的核心支撑技术之一，对物联网起到支撑作用。无线传感器网络WSN(Wireless Sensor Network)是由大量的静止或移动的传感器以自组织和多跳的方式构成无线网络，以协作的方式感知、采集、处理和传输网络覆盖地理区域内被感知对象的信息，并最终把这些信息发送给网络的所有者。因为无线传感器网络技术能够满足快速移动、自组织和方便快捷等需求，且无线传感器网络技术发展也日渐成熟。因此，无线传感器网络被广泛的应用到军事[1]、航空[2]、救灾[3]、环境[4]、医疗[5]、保健[6]、工业[7]、商业[8]等领域。 近年来提出的智慧交通[9]，智能家居[10]，智慧城市[11]等领域，同样取得了很大规模的应用。但是随着无线传感器网络的普及，无线传感器网络自身的不足开始被逐渐重视。尤其是网络服务质量和网络应用的稳定性方面。而对于解决这两个问题来说，覆盖优化问题又是一个必须先解决的基本问题。WSN的覆盖优化问题可描述为在规定监测区域内，保证传感器网络连通情况下的节点部署问题。为了满足覆盖要求，人们通常直接随机抛洒大量传感器节点，由于受到传感器节点电量和稳定性等性能约束，往往会造成比较大的覆盖盲区或者节点冗余现象，进而缩短网络使用寿命，降低网络可靠性，在能耗与成本上造成大量的资源浪费，因此需要对无线传感器网络中传感器节点进行自适应的调整部署，使其在监测区域分布更加均匀，覆盖率更高。从而增长网络使用寿命，提高网络可靠性。这对整个无线传感器网络具有重要的意义。

近年来，将智能优化算法应用到无线传感器覆盖问题上受到了越来越多学者的关注。胡小平等[12]提出一种基于多种策略改进灰狼优化算法，虽然较于基本灰狼优化算法来说，在覆盖优化、覆盖率和收敛速度等方面均有提升，但与其他改进智能算法相比并无法凸显出该算法的优越性；杨永健等[13]提出了一种基于改进PSO算法的传感器网络覆盖优化模型，对比其他改进粒子群算法覆盖率有所提高，但仍需完善才能实现近似覆盖；徐钦帅等[14]提出了一种改进蚁狮算法的无线传感器网络覆盖优化模型，虽然相较于不同改进的蚁狮算法有效地提高了覆盖率，但其精度及稳定性不够理想且节点有效覆盖率较低。上述研究成果表明，多种不同群体智能算法应用于WSN网络覆盖优化结果虽然较之前有所改善，但整体优化效果仍有待提高。

麻雀搜索算法[15](SSA)是由薛建凯于2020年最新提出，它通过麻雀个体搜寻食物和反捕食进行迭代寻优，具有搜索精度高，收敛速度快，稳定性好，鲁棒性强等特点。但是和其他群体智能优化算法一样，在求解复杂工程优化问题时，容易“早熟”导致收敛精度不高，且易于陷入局部最优解。

针对以上讨论问题，同时结合SSA算法，本文研究了一种增强型SSA算法的WSN覆盖优化问题。首先，考虑到非线性收敛因子能更好的平衡局部和全局搜索，以及柯西变异算子跳出局部最优的特点，本文提出一种增强型麻雀搜索算法(ESSA)。通过测试不同模态的基准测试函数，表明与其他改进智能算法相比，该算法在搜索精度、收敛速度、稳定性和避免局部最优值等方面均有明显提升。其次，针对区域覆盖难以应用几何学方法解决的问题，本文在所提出ESSA算法的基础上，应用到WSN覆盖优化中，并与其他相同场景的改进算法相比，结果表明ESSA算法有着更好的优化效果。

1 覆盖模型描述

1.1 覆盖率描述

在WSN中，本文假设有N个同构传感器节点，每个传感器节点都具有相同的感知半径R及通信半径R c，为保证无线传感器网络的连通性，节点的通信半径设置为大于或者等于节点感知半径的2倍。节点集合可表示为S＝{s1，s2，s3，…，s n}。监测区域节点的集合M＝{m1，m2，m3，…，mn}，(x i，y i)与(x j，y j)分别对应集合中si、m j的二维空间坐标。本文采用布尔感知模型[16](即传感器节点对位于R范围内检测区域节点的感知能力相同，因而传感器节点的感知范围是以传感器节点为圆心、以R为半径的圆盘)作为节点感知模型，只要监测区域处于节点感知半径范围则视为覆盖该节点。传感器节点与监测区域节点之间的欧氏距离为

监测点m j被节点s i感知的概率为

所有传感器节点对监测点mj的联合感知概率为:

式中:Sall为监测区域内的所有无线传感器节点。假设监测区域为矩形，面积为LWm2。为便于计算，将该矩形划分为LW个面积相等的网格，监测节点m位于网格的中心点位置。通过上式(3)计算出所有监测点的联合感知概率，累加之和即为覆盖面积。覆盖率C r可表示如下:

所求问题描述如下:

1.2 网络连通描述

网络连通为WSN的最基本要求，因此我们在保证最大覆盖率的同时要使整个网络保持连通状态。为便于计算，假设2R＝R c。建立有向图邻接矩阵Mv，其用于存储任意两节点的连通情况，根据式(6)判断是否连通，M v[i][j]＝1表示第i个节点可向第j个节点传送信息(即单向连通)，当其值为0表示不连通，再根据文献[17]的矩阵幂算法判断整个网络是否连通，矩阵S v由式(7)计算得出。

式中:n为传感器节点数目，若S v中存在元素为0，网络不连通；反之则连通。

1.3 有效覆盖率描述

文献[18]提到了节点溢出面积计算，讨论了节点辐射(感知)溢出监测区域的情况。本文据此提出一种有效覆盖率，因为溢出面积较大时，不仅浪费了节点的辐射能量，而且当节点能量耗尽后，网络将出现较大的覆盖空洞，二次部署也较麻烦。故网络的有效覆盖率越高，越能说明网络的稳定性和适应性越好。有效覆盖率用C t表示。

定义1(最大化覆盖面积) 若传感器节点的感知范围没有超出监测区域，且任意传感器节点之间无重叠部分，即传感器群感知最大面积C m。如图1所示，一个传感器节点覆盖了12个监测点，故C m＝4×12＝48。

图1 最大化覆盖面积

定义2(有效覆盖面积) 传感器节点感知范围内的监测区域面积为有效面积，用C v表示，如图2。通过计算可知有效覆盖面积为C v＝63，C m＝9×12＝108，故

图2 有效覆盖面积图

2 基本的麻雀搜索算法

在麻雀觅食的过程中，分为探索者和追随者两部分，探索者在种群中负责寻找食物并为整个麻雀种群提供觅食区域和方向，而追随者则是追随探索者的位置来获取食物。为了获得食物，麻雀通常可以采用探索者和追随者这两种行为策略进行觅食，种群中的个体会监视群体中其他个体的行为，并且该种群中的捕食者会与高食物资源的同伴争夺食物，以提高自己的捕食率。此外，当麻雀种群意识到危险时会做出反捕食行为。

在模拟实验中，我们需要使用虚拟麻雀来寻找食物。麻雀的位置可以用以下矩阵表示:

式中:n是麻雀的数量，d表示要优化的变量的维数。然后，所有麻雀的适应度值可以用以下向量表示:

式中:n表示麻雀的数量，F x中每行的值表示个体的适应值。在SSA中，具有较好适应度值的探索者在搜索过程中优先获得食物。此外，因为探索者负责寻找食物和引导整个种群的流动。所以，探索者可以在更广泛的地方寻找食物。根据规则(9)和(10)，在每次迭代过程中，探索者的位置更新如下:

式中:t代表当前迭代数，itermax是一个常数，表示最大的迭代次数，X i，j表示第i个麻雀在第j维中的位置信息。α∈(0，1)是一个随机数，R2(R2∈[0，1])和ST(ST∈[0.5，1])分别表示预警值和安全值，Q是服从正态分布的随机数，L表示一个1×d的矩阵，其中该矩阵内每个元素全部为1，当R2

追随者的位置更新描述如下:

式中:X P是目前探索者所占据的最优位置，Xworse则表示当前全局最差的位置，A表示一个1×d的矩阵，其中每个元素随机赋值为1或－1，并且A＋＝AT(AAT)－1。当i>n/2时，这表明，适应度值较低的第i个追随者获得很少食物，处于十分饥饿的状态，此时需要飞往其他地方觅食，以获得更多的能量。

当意识到危险时，麻雀种群会做出反捕食行为，其数学表达式如下:

式中:Xbest是当前的全局最优位置。β作为步长控制参数，是服从均值为0，方差为1的正态分布的随机数。K∈[－1，1]是一个随机数，f i则是当前麻雀个体的适应度值，f g和f w分别是当前全局最佳和最差的适应度值，ε是最小的常数，以避免分母出现零。

为简单起见，当f i>f g表示此时的麻雀正处于种群的边缘，极其容易受到捕食者的攻击。f i＝f g时，这表明处于种群中间的麻雀意识到了危险，需要靠近其他的麻雀以此尽量减少它们被捕食的风险。K表示麻雀移动的方向同时也是步长控制参数。

3 一种增强型麻雀搜索算法

3.1 非线性收敛因子

在SSA中，探索者的比例因子pd是一个固定值，其值为0.2，这与算法的早期和后期策略相同，因此不灵活，容易导致算法收敛速度慢。为了提高算法的搜索效率，本文提出了一个收敛因子∝来约束原比例因子。图3描绘了收敛因子，其数学描述如下:

图3 非线性收敛因子

T是最大迭代次数，t是当前迭代次数。如图3所示，∝的值从1非线性减小到0，在迭代的早期，∝值较大，即探索者个数较多，有利于全局优化搜索，加快算法的收敛速度。在迭代的后期，∝值较小，即探索者个数较少，集中于理论最优值附近，有利于局部寻优，从而提高解的精度。

3.2 柯西变异算子

柯西高斯变异算子[19]，可以很大程度上提高算法全局勘探能力，收敛精度以及稳定度。比如近年来柯西逆累积分布改进的鲸鱼优化算法[20]，基于柯西变异的蚁狮优化算法[21]均得到了良好的优化效果。

柯西分布如下:

柯西分布从峰值向两侧下降相对平缓，麻雀个体受局部的极值点约束力在柯西变异后下降，并且柯西分布的峰值相对较小，麻雀个体在变异后会花费相对较少的时间来搜索相邻区间，把更多的时间放在搜寻全局最优值上，使得增强的麻雀搜索算法在寻找全局的最优值方面具有很好的调节能力。利用上述柯西分布特点对麻雀搜索算法进行优化改进，在探索者的状态上引入服从柯西分布的随机向量，公式如下:

式中:x′为初始位置x的更新位置，Cauchy(0，1)是τ＝1时的标准柯西随机分布；参数γ是用来表示柯西分布变异强度，公式如下:

式中:f(x)为当前探索者个体适应度值，worst为当前种群最差适应值，T为最大迭代次数，参数θ为控制柯西变异强度的系数。

3.3 一种新颖的越界处理方法

大多数情况下，研究者们对于种群个体的越界行为处理的很简单，直接把位于搜索区域之外的个体重定位到距离目标区域最近的边界域，即区域边界。这样处理虽然简单，但是无意中降低了个体的差异性，使得种群无法更好的进行的全局寻优。因此，本文提出一种新颖的越界处理方法，公式如下:

公式如其中x′为越界个体x的更新位置，lb为搜索区域下界，ub为搜索区域上界，μ为0～1之间的随机数，σ为介于0～1之间的越界处理因子。

增强型麻雀搜索算法流程如下。

①设置参数:最大迭代次数Tmax、麻雀种群数量pop、意识到危险的麻雀数量SD。

②初始化麻雀种群位置，计算各个体适应度值并进行排序，找出最佳个体和最差个体，然后按照比例确定探索者数量。

③每次迭代时计算非线性收敛因子∝，以∝为探索者比例确定探索者数量，然后使用式(11)更新探索者位置，实现探索者进行食物的全局搜索，并且进行越界处理。

④使用式(12)更新追随者位置，使得跟随者不断地靠近探索者位置。

⑤如果预警者发现潜在危险，则使用式(13)快速离开危险位置，寻找更为安全的食物源。

⑥在麻雀搜索食物之后，对麻雀个体适应度值进行大小排序。

⑦判断该算法是否到达最优迭代次数，若到达，则获得最佳食物位置，否则转至步骤③。

⑧在进入循环迭代后，当麻雀种群中相邻两次迭代的最优值相同时，我们认为算法陷入局部最优，此时使用式(16)变异种群，跳出局部最优。

3.4 增强型麻雀搜索算法时间复杂度分析

假设算法最大迭代次数为T，种群规模为N，优化问题的维数为D。在SSA算法中，初始化种群，其时间复杂度为O(ND)。每一次迭代需要完成以下步骤，先计算种群的适应度值并找出种群中最优个体，其时间复杂度为O(N)，之后麻雀个体更新位置，其时间复杂度为O(N)，故一次迭代的时间复杂度为O(N＋N)。总的时间复杂度为O[T(N＋N)＋ND]，即O(TN)。相比于SSA，ESSA增加了非线性收敛因子和柯西变异算子，仍属于麻雀个体更新位置的操作，并没有增加额外的时间复杂度，故ESSA总的时间复杂度和SSA一致。

3.5 基于ESSA算法的覆盖优化步骤

①设置传感器的组数(种群大小)N，每组传感器节点数目(维数)D以及监测区域的范围。

②初始化N组传感器节点的位置和半径，即I s，随机选择一组I1为第一代解。

③根据式(4)求出每组传感器部署方案的覆盖率，最优解为当前最大覆盖率对应的传感器节点按部署方案。

④将ESSA算法用于优化每组部署方案的覆盖率，若节点位置处在监测区域外，则利用式(18)将节点重定位到合理的区域内，算法结束后将会得到覆盖率最大的一组传感器节点部署方案I2。

⑤按照传感器覆盖率大小排序并根据式(7)判断网络是否连通，若不连通则选择次优方案，直至找到第一组连通的部署方案。

4 仿真实验与分析

为了验证混合策略的有效性，选取了四个基准函数进行数值仿真，并与基本的SSA算法和其他改进算法进行对比，其中实验参数与其他文献对应的参数一致。参与对比的算法如表1所示，实验采用的4个基准测试函数详细信息如表2所示，其中F1为单模态基准测试函数，F2为多模态基准函数，F3，F4为固定维多模态基准函数。

表1 对比算法

表2 基准测试函数

4.1 基准函数优化性能测试

对于所有算法，都使用了种群大小和最大迭代次数分别为30个和100次，并且单独运行30次，实验结果取平均值进行比较，比较结果如表3所示。

表3 基准函数优化结果对比

从表3和图4可以看出，ESSA算法较其他算法均取得了更好的收敛结果，对于单模态基准测试函数F1，该算法虽然在前20代最优值差于ML-ALO算法，但在最终结果上较其他五种算法至少提高了2个数量级，且在算法稳定性上也更稳定。对于多模态基准测试函数F2，因为多峰函数包含许多局部最优值，其数量随问题规模呈指数增长，因此，如果以评估优化算法的探索能力为目的，这类测试问题就变得非常有用。根据表中实验结果来看，ESSA算法最优值优于DACQPSO算法，近乎是其他四种对比算法最优值的两倍。这表明ESSA具有很好的勘探能力。这是由于ESSA算法中的综合探索机制导致该算法走向全局最优。对于固定维多模态基准函数F3，F4，ESSA在收敛速度和寻优精度上都明显由于其他五种算法，且在迭代前期的探索性和迭代后期的开发性都优于其他五种算法，这表明ESSA在保证探索能力的同时也能充分保证开发能力，还能保持较高的种群差异性。

图4 优化测试函数收敛曲线对比

综上所述，ESSA对4个基准测试函数的寻优性能有明显的提升，且稳定性好，鲁棒性强。同时ESSA的收敛速度也明显优于其他五种算法，且实时性表现良好。由此证明了ESSA算法改进的可行性和优越性。

4.2 WSN覆盖优化

4.2.1 实验设置

为了充分验证ESSA算法对WSN节点覆盖的优化性能，选取基本SSA算法和不同文献中的4种改进算法做对比，参考文献及对比算法如表1所示。此外，几种对比算法仿真实验的参数均一致。且为使实验更具说服力，每种对比算法的仿真实验独立运行30次，取平均覆盖率进行对比。需要注意的是对于改进蚁狮算法(ML-ALO)的覆盖优化实验数据来自文献[14]。

4.2.2 监测区域为20×20覆盖优化对比

实验参数设置如表4所示，表5给出了ESSA算法、SSA算法、DACQPSO算法、IGWO算法、IWOA算法和MS-ALO算法的平均覆盖率优化结果对比。图5和图6分别为ESSA算法、SSA算法、DACQPSO算法、IGWO算法、IWOA算法优化后该区域节点分布图和收敛曲线图。

图5 优化后节点分布图

表4 参数设置

表5 覆盖率优化结果对比

从图6可以清晰的看出基本SSA算法在第50代左右覆盖率达到90%左右，虽然在前50代中取得了最好的网络覆盖率，但此后一直陷入了局部最优。而DACQPSO算法相比与ESSA算法来说虽然网络覆盖率都在稳步提高，但是ESSA算法提升的速率更快，且在130代左右就达到了DACQPSO算法的最大网络覆盖率，相比于DACQPSO算法快了370代。IGWO算法虽然有最高的初始覆盖率81.5%，但此后一直未跳出局部最优。IWOA算法覆盖率有所提高但收敛速度过慢，在后350代覆盖率只提升了不到3%。这说明ESSA可以很好地平衡勘探开发阶段，这种能力来自于非线性收敛因子对生产者的数量随着迭代次数而减小使全局搜索和局部搜索更为平衡合理。

图6 覆盖优化收敛曲线

由表5可以看出，在相同的实验参数下，ESSA算法运行三十次所得的平均覆盖率相比DACQPSO算法和基本的SSA算法分别提高了9.1%和4.6%，较于IGWO算法和IWOA算法提高均超过10%。虽然MS-ALO算法覆盖率达到第二高的93.46%，高于DACQPSO算法但仍少于ESSA算法的96.25%覆盖率。

同时从图5可以看出相比于基本SSA算法和四种改进的对比算法优化效果较差，且易出现覆盖空洞的问题，ESSA算法优化后的节点分布更加均匀，节点冗余更少，无线网络覆盖范围更加广泛。

4.2.3 监测区域为50×50覆盖优化对比

实验参数设置如表6所示，表7给出了ESSA算法、SSA算法、DACQPSO算法、IGWO算法、IWOA算法、MS-ALO算法的平均覆盖率优化结果对比。图7和图8分别为ESSA算法、SSA算法、DACQPSO算法、IGWO算法、IWOA算法优化后该区域节点分布图和收敛曲线图。

表6 参数设置

由表7可知，ESSA算法进行30次覆盖优化的平均覆盖率相比基本SSA算法、DACQPSO算法、IGWO算法、IWOA算法分别提高了4.92%、10.16%、12.92%和10.35%。由图7所示分布节点中可以看出DACQPSO算法、IGWO算法和IWOA算法优化后的区域节点覆盖盲区较大，而ESSA算法优化后节点分布更加均匀，极大改善了这三种改进算法节点冗余的现象。表7中MS-ALO算法的覆盖率高达96.45%，超出ESSA算法2.77%。但是在文献[14]中有40个传感器节点，多出本实验5个。因此通过式(8)计算有效覆盖率可知，ESSA算法的有效覆盖率为85.24%，MS-ALO算法的有效覆盖率为76.79%，ESSA算法有效覆盖率更高。这表明柯西变异算子能有效提高算法的全局勘探能力，但本文提出的控制柯西分布变异强度的因子更加合理，且综合机制优于MS-ALO算法。

表7 覆盖率优化结果对比

图7 优化后节点分布图

从图8可以看出在收敛速度上ESSA算法在不断的向最优值靠近，最终覆盖率达到93.68%，SSA算法在运行至50代时节点覆盖率达到82%，之后的300代一直陷入局部最优，直到350代后才跳出局部最优，最后达到88.76%的节点覆盖率，不如ESSA算法。相较于ESSA算法，DACQPSO算法、IGWO算法、IWOA算法收敛速度太慢，经过500次迭代后覆盖率增长均低于10%，ESSA算法随机部署时节点覆盖率只有最低的36.92%，在500次迭代后增长了56.76%。远远优于对比算法。这表明ESSA算法在保证探索能力的同时也能充分保证开发能力，还能保持较大的种群差异性。

图8 覆盖优化收敛曲线

4.2.4 监测区域为100×100覆盖优化对比

实验参数设置如表8所示，表9给出了ESSA算法、SSA算法、DACQPSO算法、IGWO算法、IWOA算法、MS-ALO算法的平均覆盖率优化结果对比。图9和图10分别为ESSA算法、SSA算法、DACQPSO算法、IGWO算法、IWOA算法优化后该区域节点分布图和收敛曲线图。由表9可知，ESSA算法进行30次覆盖优化的平均覆盖率相比于基本SSA算法、DACQPSO算法、IGWO算法、IWOA算法分别提高了3.29%、10.68%、6.67%、7.32%，具有更好的覆盖效果。由图9所示分布节点中可以看出基本SSA算法优化后的区域节点冗余较多，DACQPSO算法、IGWO算法、IWOA算法优化后的区域节点覆盖盲区较大，而ESSA算法优化后节点分布均匀，冗余较少。

表8 参数设置

表9 覆盖率优化结果对比

图9 优化后节点分布图

另外从图10可以看出在收敛速度上，ESSA算法在不断的向最优值靠近，最终覆盖率达到96.2%，SSA算法在运行至50代时节点覆盖率达到89%，之后运行的100代一直陷入局部最优，直到150代后跳出局部最优，最后只达到92.91%的节点覆盖率，不如ESSA算法。IWOA算法虽然在后面200代覆盖率增长最多，但在迭代结束只达到了88.88%的覆盖率。IGWO算法收敛速度太慢，在随机部署时就达到五种对比算法里最高覆盖率80.01%，但经过500次迭代后只增长了9.3%。ESSA算法在500次迭代后增长了21%左右，收敛速度远远优于其他四种对比算法。对于MS-ALO算法来说，虽然覆盖率只有71.63%，但是在监测面积，传感器节点数量相同的情况下，它的感知半径为7，本实验感知半径为10。所以通过式(8)计算有效覆盖率可知，ESSA算法的有效覆盖率率为76.59%，MS-ALO算法的有效覆盖率为71.63%，低于ESSA算法。

上述三个仿真实验结果表明，增强型的麻雀搜索算法具有适应性强，收敛速度快，跳出局部最优能力强等特点。将ESSA算法应用到无线传感网络节点部署优化问题，能够快速有效的提升网络覆盖率，减少覆盖盲区，降低覆盖成本。

5 结束语

针对无线传感器网络覆盖率最大化的问题，本文提出了一种增强型的麻雀搜索算法实现传感器节点的覆盖优化。该算法模拟了麻雀的觅食和反捕食行为之后加入了非线性收敛因子，增强了算法的全局探索和局部开发的平衡能力，柯西变异算子改善了算法易陷入局部最优的问题。然后通过不同形态基准函数的优化求解，并与基本麻雀搜索算法和其他改进智能算法相比较，验证了该算法在搜索精度、收敛速度和稳定性等方面与其他算法相比具有很强的竞争力。

将ESSA算法进一步应用到无线传感器网络覆盖优化问题中，并选取了基本麻雀搜索算法和4种改进的智能算法，在相同条件下进行对比试验。实验结果表明基于ESSA的WSN覆盖优化算法取得的平均覆盖率均优于同条件下其他对比算法，通过节点分布图来看ESSA算法优化后的节点分布更加均匀，覆盖盲区更小，且节点冗余更少。通过对比覆盖优化收敛曲线，更验证了ESSA算法对收敛速度的有效提升。因此可以说本文提出的算法能够很好地提高无线传感器网络的覆盖率，直接节省了网络覆盖所花费的成本。然而，如何保证在较高覆盖率的情况下进一步延长无线传感器网络生存寿命，更大限度的节省网络覆盖所花费的成本，将是ESSA算法下一步需要解决的问题。