改进麻雀搜索算法下的WSN节点覆盖优化

WSN Node Coverage Optimization Based on Improved Sparrow Search Algorithm

摘要: 针对麻雀搜索算法(SSA)存在的种群多样性不足，容易陷入局部最优解等问题，提出一种基于自适应t分布变异的改进麻雀搜索算法(ISSA)。通过在基本麻雀算法中加入t分布型随机扰动项，将算法的迭代次数作为t分布的自由度参数，增加了算法的种群多样性，均衡了算法的全局探寻和局部开发能力。采用4种基准函数评估ISSA的性能，并将ISSA算法应用在无线传感器网络(WSN)节点的覆盖优化问题。仿真实验表明，改进的麻雀搜索算法在收敛精度和速度上有显著提升，网络覆盖率相较于对照算法有一定的提高。

Abstract: Aiming at the problems of sparrow search algorithm (SSA), such as population diversity deficiency and being easy to fall into local optimal solution, an improved sparrow search algorithm (ISSA) based on adaptive t-distribution mutation is proposed. By adding the random disturbance term of t-distribution into the basic sparrow algorithm, the iteration times of the algorithm are taken as the degree of freedom parameter of t-distribution, which increases the population diversity of the algorithm and balances the global searching and local development ability of the algorithm. Four benchmark functions are used to evaluate the performance of ISSA, and the ISSA is applied to the coverage optimization of wireless sensor network (WSN) nodes. The simulation results show that the improved sparrow search algorithm has a remarkable improvement in the convergence accuracy and speed, and the network coverage has a certain improvement compared with the comparison algorithms.

1. 引言

无线传感器网络(Wireless Sensor Networks, WSN)是一种分布式传感网络 [1]，它是由有限个具有感知和相互通信功能的传感器所组成的，具有网络布置灵活、组建方式自由、功耗低等特点。无线传感器网络覆盖优化是一个重要的问题 [2]，它直接影响着网络的性能和服务质量。

针对WSN覆盖问题，提出了多种优化方法。张景昱 [3] 等人提出了一种基于区域分割和Voronoi图的覆盖算法(RSV)，延长网络寿命，使节点能量消耗更加平均，在节点数量受限情况下，覆盖效果较佳；何庆 [4] 等人采用改进的正弦余弦(ESCA)算法对WSN节点布置进行优化，有效减少网络成本，提高了网络覆盖率。近些年来，群智能算法逐渐在WSN覆盖问题上得到应用。徐钦帅 [5] 等人采用动态权重系数和早熟收敛判断的方法对蚁狮算法进行优化，使节点分布更加均匀；张雪 [6] 等人提出基于非线性收纳因子和自适应调整策略改进的灰狼优化算法，减少了覆盖盲区。

麻雀搜索算法SSA (Sparrow Search Algorithm)是由薛建凯 [7] 等人在2020年提出的一种新型群智能算法。SSA算法模拟麻雀觅食和躲避天敌的行为，具有较好的寻优能力和搜索精度。但与其他的群智能优化算法一样，都存在着极易陷入局部最优解、种群多样性不断减少等缺陷 [8]。针对SSA算法的缺陷，本文提出了一种改进麻雀搜索算法ISSA，利用自适应t分布变异的改进策略，改善了算法种群的多样性，有效提升了算法的全局搜寻能力和局部开发性能。本文对4个基准测试函数进行仿真实验，并将改进算法应用到传感器网络节点覆盖的问题中，验证了改进麻雀搜索算法的可行性。

2. 无线传感器网络节点覆盖模型

在无线传感器网络中，现假定监测区域为一个二维平面。在该矩形区域中投放N个结构型号一致的传感器节点，节点的感知半径都设置为r。将该矩形区域离散化为数量 $m\times n$ 个像素点。传感器节点集表示为 $Q=\left\{q_1,q_2,\cdots ,q_N\right\}$，第i个传感器节点 $q_i$ 的位置坐标为 $\left(x_i,y_i\right)$。设像素点 $H_j$ 的坐标为 $\left(x_j,y_j\right)$，那么传感器节点 $q_i$ 和该像素点 $H_j$ 的间距定义为：

$d\left(q_i,H_j\right)=\sqrt{{\left(x_i-x_j\right)}^2+{\left(y_i-y_j\right)}^2}$ (1)

传感器节点的感知模型主要是两种：0/1 (二元)感知模型和概率感知模型。本文采用二元感知模型，传感器节点 $q_i$ 感知像素点 $H_j$ 的概率定义为：

$p\left(q_i,H_j\right)=\{\begin{array}{l}1d\left(q_i,H_j\right)\le r\\ 0d\left(q_i,H_j\right)>r\end{array}$ (2)

在该区域中，任意一个像素点 $H_j$ 能同时被多个传感器节点感知，联合感知概率定义为：

$p\left(Q,H_j\right)=1-{\displaystyle \underset{q_i\in Q}{\prod }\left[1-p\left(q_i,H_j\right)\right]}$ (3)

该区域的覆盖率R为传感器节点集Q所覆盖的像素点总数和矩形目标区域内像素点总数的比值，定义为：

$R=\frac{{\displaystyle \underset{j=1}{\overset{m\times n}{\sum }}p\left(Q,H_j\right)}}{m\times n}$ (4)

因此，把式(4)作为改进麻雀搜索算法的目标函数，即在目标监测区域范围内，利用改进的智能优化算法求解覆盖率的最大值。

3. 基本麻雀搜索算法

在自然界中，麻雀群体有着较为明确的分工合作。群体中一部分麻雀负责寻找食物，并为群体其他成员提供食物的区域和方向，剩下的麻雀成员跟随发现者进行觅食。同时，群体中一定比例的麻雀负责监视，当出现捕食者时，负责监视的麻雀会提醒整个群体躲避捕食者。

麻雀搜索算法SSA是受到麻雀觅食行为和躲避捕食行为的启发，而提出的一种新型群智能优化算法。在算法中，通过模拟麻雀来获得优化问题的解。麻雀的位置集合表示为 $X={\left[x_1,x_2,\cdots ,x_n\right]}^{\text{T}}$， $x_i=\left[x_{i,1},x_{i,2},\cdots ,x_{i,d}\right]$，其中n为麻雀的数量，d为待优化变量的维数。麻雀群体的适应度值则表示为 $F={\left[f\left(x_1\right),f\left(x_2\right),\cdots ,f\left(x_n\right)\right]}^{\text{T}}$，其中 $f\left(x_i\right)$ 为第i个麻雀个体的适应度值。在SSA中，适应度更高的麻雀个体拥有获取食物的优先权，并作为发现者引导整个群体向食物接近。发现者的位置更新定义为：

$x_{i,j}^{t+1}=\{\begin{array}{l}{x}_{i,j}^t\cdot \exp \left(\frac{-i}{\beta \cdot MaxIteration}\right)R_s<STR\\ x_{i,j}^t+Q\cdot L{R}_s\ge STR\end{array}$ (5)

式中，t为当前的迭代数， $\beta$ 为 $\left(0,\text{1}\right]$ 之间的均匀分布随机数，Q为服从正态分布的随机数，L为1 × d且元素全为1的矩阵。MaxIteration为最大迭代次数。 $R_s\in \left[0,1\right]$ 为预警数值， $STR\in \left[0.5,1\right]$ 为安全阈值。当预警值低于阈值时，发现者将进行广泛搜索的操作，以获得更高适应度值；当预警值超出阈值时，群体将调整搜索策略，向安全区域靠近。

除了发现者，群体中其余个体为加入者。加入者跟随发现者，从而获得更高的适应度值。加入者的位置更新定义为：

$x_{i,j}^{t+1}=\{\begin{array}{l}Q\cdot \exp \left(\frac{x_{worst}^t-x_{i,j}^t}{i^2}\right)i>\frac{n}{2}\\ x_{po}^{t+1}+\left|x_{i,j}^t-x_{po}^{t+1}\right|\cdot A^{+}\cdot Li\le \frac{n}{2}\end{array}$ (6)

式中， $x_{po}^{t+1}$ 为第t + 1次迭代时发现者的最佳位置， $x_{worst}^t$ 为第t次迭代种群的最差位置。 $A^{+}$ 为1 × d矩阵，矩阵元素被随机分配成1或者−1， $A^{+}=A^{\text{T}}{\left(A{A}^{\text{T}}\right)}^{-1}$。

由于麻雀群体存在来自捕食者的威胁，麻雀群体会随机选取一部分个体作为侦察者，该部分的比例为10%至20%。侦察者的位置更新定义为：

$x_{i,j}^{t+1}=\{\begin{array}{l}{x}_{best}^t+\delta \cdot \left|x_{i,j}^t-x_{best}^t\right|f_i>f_g\\ x_{i,j}^t+k\cdot \left(\frac{\left|x_{i,j}^t-x_{worst}^t\right|}{\left(f_i-f_w\right)+\epsilon }\right)f_i=f_g\end{array}$ (7)

式中， $x_{best}^t$ 为当前全局最优的位置； $\delta$ 为步长控制参数；k为步长调整系数，是 $\left[-\text{1},\text{1}\right]$ 区间内的随机数； $\epsilon$ 是最小常数，用于避免零除误差。 $f_i$ 是当前麻雀的适应度值， $f_g$ 和 $f_w$ 分别是当前全局最佳和最差适应度值。为了简化问题，当 $f_i>f_g$ 时，此时麻雀位于种群的边界位置，容易受到捕食者威胁；当 $f_i=f_g$ 时，位于群体中心的麻雀察觉到威胁，需要向其他麻雀靠近。

4. 改进的麻雀搜索算法

4.1. 自适应t分布变异

t分布的别名为学生分布 [9]，它的曲线形状与其自由度n的大小密切相关。当n的值越小时，曲线的形状越平坦，中间部分越低，曲线两侧尾端翘得越高。

$t\left(n\to \infty \right)\to N\left(0,1\right)$， $t\left(n=1\right)=C\left(0,1\right)$，其中 $N\left(0,1\right)$ 是高斯分布， $C\left(0,1\right)$ 是柯西分布，这两种分布是t分布的特殊分布，如图1。

Figure 1. t distribution curve

图1. t分布曲线图

在自适应t分布变异中，把迭代次数作为t分布的自由度参数n。对麻雀位置利用自适应t分布进行更新，定义为：

$x_i^t=x_i+x_i\cdot t\left(iteration\right)$ (8)

式中， $x_i^t$ 为变异后麻雀的位置， $x_i$ 为第i个麻雀的位置， $t\left(iteration\right)$ 是以算法迭代次数iteration作为参数自由度的t分布。式(8)是在 $x_i$ 的基础上增加了t分布型随机干扰项 $x_i\cdot t\left(iteration\right)$。

改进算法在更新麻雀位置之后，利用自适应t分布变异对麻雀位置进一步更新。随机选择麻雀个体进行二次更新，对比更新前后麻雀的适应度值，选取适应度值更优的个体。使用麻雀搜索算法的迭代次数作为自由度参数，可充分利用当前的种群信息。根据t分布的性质，前期迭代次数较小，t分布变异与柯西分布变异相近，具有较强的全局搜索能力；在算法运行后期，迭代次数较大，t分布变异与高斯分布变异类似，具有较强的局部搜索能力。该改进方式将柯西分布变异与高斯分布变异两者的优势相结合，提升了麻雀搜索算法的全局搜索能力和局部开发性能。

4.2. 改进麻雀搜索算法的实现步骤

针对麻雀搜索算法容易陷入局部最优的问题，本文提出了一种基于自适应t分布变异的改进麻雀搜索算法ISSA。在麻雀位置更新后，加入以迭代次数为自由度参数的自适应t分布变异，提升群体的多样性，使算法易于跳出局部最优解，缩短了搜索时间。

ISSA的具体步骤可总结如下：

1) 初始化ISSA算法的基本参数，包含种群数目、最大迭代次数、发现者比例、侦察者比例、分布变异概率、预警值等。

2) 计算麻雀种群个体的适应度值，进行排序。

3) 得到当前最佳适应度、最差适应度和两者分别对应的位置。

4) 按比例选取适应度优的麻雀个体作为发现者，剩下的作为加入者。随机选取麻雀个体作为侦察者。根据式(5)、式(6)和式(7)，分别更新发现者、加入者和侦察者的位置。

5) 重新计算适应度值。

6) 如果rand < p，则根据式(8)对麻雀个体位置进行自适应t分布变异。

7) 计算变异后新位置下的麻雀个体适应度值，若优于变异前，则用变异后的个体替代之前的个体，否则保持原位置个体不变。

8) 更新种群的最优适应度值、最差适应度值和两者分别对应的位置。

9) 判断算法是否达到最大的迭代次数或者求解的精度。如果达到，则结束循环，输出寻优的结果。否则返回步骤4，继续寻优过程。

5. 仿真实验和结果分析

5.1. 基准函数优化性能测试

为了验证改进的可行性，选取4个基准函数进行数值仿真，将改进的麻雀搜索算法(ISSA)与基本麻雀搜索算法(SSA)和秃鹰算法(BES)进行比较。仿真所选择的函数名称、函数表达式及仿真参数见表1。

Table 1. Benchmark function

表1. 基准测试函数

算法的种群规模都为30，最大迭代次数为500次。每个测试函数都在相同维度下独立运行20次，记下其平均值。基准函数在各算法中的优化结果见表2。

Table 2. Comparison of benchmark function optimization results

表2. 基准函数优化结果对比

Figure 2. Three dimensional image of function F4 and convergence curve of algorithm

图2. 函数F4的三维图像及算法的收敛曲线

由表2可以看出，相较于SSA算法和BES算法，ISSA算法在各个基准函数均得到了更好的收敛结果。特别是函数F1，ISSA算法取得了其理论最优解。对于多峰函数F4，ISSA算法的寻优结果与其理论最优解相当接近。以基准测试函数F4为例，由图2可以看出，ISSA算法的收敛速度和精度都是三者中最佳的。仿真表明，自适应t分布变异改进策略具有可行性。该策略极大地提高了算法的全局搜寻和跳出局部最优的能力，有效提升了收敛精度。

5.2. 在不同传感器网络节点数量下的覆盖率比较

为了检验ISSA算法对无线传感器网络WSN节点覆盖的优化性能，在指定监测区域内，对智能优化算法在规定数量传感器节点下的覆盖率进行比较。上文提到的区域的覆盖率R即为智能优化算法的目标函数，利用式(4)可计算种群的适应度。仿真基于2.20 GHz CPU、8 GB内存的PC机和Matlab2017软件。仿真的参数设置见表3。

Table 3. Simulation parameter setting

表3. 仿真参数设置

实验分别在覆盖节点数量为20、25、30、35、40、45、50、55、60、65、70的条件下使用ISSA算法、SSA算法和BES算法进行30次仿真，记录下平均值。每次实验中，除覆盖节点之外的其他参数保持不变。算法在不同节点数量下的覆盖率如图3。

Figure 3. Line graph of coverage varying with the number of nodes

图3. 覆盖率随节点数量变化折线图

由图3可以看出，在覆盖节点相同的情况下，ISSA算法下的无线传感器网络覆盖率均高于对照算法。当节点数量为65时，ISSA算法对应的覆盖率已超过95%，高于另外两者。说明改进的麻雀搜索算法ISSA在一定程度上提高了算法的寻优性能和跳出局部最优的能力，无线传感器网络节点覆盖率得到了提升，具有实际效用。

6. 结论

本文在基本麻雀搜索算法的基础上，提出了一种改进的麻雀搜索算法。利用自适应t分布变异策略，对种群进行位置的更新扰动，使麻雀种群的多样性得到提高，有效整合了算法的全局搜索和局部开发能力。通过基准函数测试和无线传感器网络节点覆盖的仿真实验，从实验结果中可以看出，相较于对照算法，改进的麻雀搜索算法在节点覆盖率、收敛精度和收敛速度上都得到了提升，验证了改进算法的可行性。

基金项目

天津市科技计划项目(19JCTPJC54800)。