基于改进黏菌算法的无线传感器网络覆盖

贾鹤鸣，施宇铖，刘俊良，力尚龙，饶洪华

（三明学院 信息工程学院，福建 三明 365004）

无线传感器网络（Wireless Sensor Network, WSN）是在监测区域内部署拥有感知信息能力和通信能力的传感器节点， 通过自组织形成一种大规模分布式网络，实现对监测区域内声音、温度等数据的采集，把采集到的信息发至管理中心，最后服务于用户。目前，无线传感器网络已广泛应用于医疗、工业和军事等领域［1-3］。

在无线传感器网络中， 网络覆盖率决定了网络的性能。为了实现网络覆盖率的最大化，通常先将监控区域分成多个单元格， 再计算每个单元格的边界点是否被覆盖， 最后统计被覆盖的点并计算监测区域的网络覆盖率。如何部署移动节点，避免节点分布不均匀以及降低部署成本等都是实现无线传感器网络节点优化部署的重要课题。

近年来， 一些学者对无线传感器网络节点优化部署问题进行了深入而广泛的研究。 李守玉等［4］利用改进的平衡优化器算法， 通过加入环绕反向学习和circle 混沌映射等对平衡器算法进行了改进，降低了部署成本，提高了网络监测质量。 张微微等［5］提出了能优化传感器网络节点覆盖的改进人工鱼群算法，利用Map/Reduce 工作机制解决了无线传感器网络节点部署存在的问题。 刘宽等［6］分析了WSN 感知节点的抽象化模型， 用数学方法论证了实现感知范围全覆盖的算法， 使用六边形网格划分法对确定的平面区域中节点进行了全覆盖部署， 实现了节点覆盖效率的最大化。

2020 年，LI S. M.等提出了一种新型群体智能优化算法，即黏菌算法（Slime Mould Algorithm, SMA）［7］，通过建立粗细不一的食物网模拟了黏菌的捕食行为。 此算法具有较强的全局探索能力，已广泛应用于优化应用领域。 唐雄［8］利用改进SMA 研究了网络入侵问题，已取得了令人满意的结果。 针对黏菌算法在无线传感器网络覆盖上存在的不足， 我们提出了一种改进的黏菌算法。 首先，对参数p 进行了改进，更好地平衡了局部搜索的能力和全局搜索的能力，借助混沌精英突变策略［9］提高算法的寻优能力；其次，将改进的黏菌算法与其他优化算法进行对比实验，得出ISMA 具有更好的寻优能力，能有效减少节点冗余，提高无线传感器网络的覆盖率的结论。

1 传感器网络节点覆盖模型

假设监控区域是一个长方形， 其长为L， 宽为W，面积为S=L×W。在监控区域里随机部署n 个传感器节点，这n 个节点构成的集合［10］为

每个节点的感知半径都为R，通信半径都为r。

为计算上的方便，把监控区域离散为L×W 个大小相等的单元点， 每个单元点代表所要监控的目标点，其集合为

图1 节点感知模型

2 黏菌算法基本原理

黏菌算法是基于黏菌觅食行为的一种优化算法。 在觅食过程中， 黏菌发现食物时会发生振荡收缩。 另外，在多个食物源之间，会形成粗细不一的静脉网络，静脉网络的粗细与食物源的质量有关。而黏菌在获取食物时，仍有可能对未知区域进行搜索。黏菌的行为主要有3 种，即接近食物、包裹食物和获取食物［7］。

2.1 接近食物

黏菌在发现食物时，会发生收缩，其收缩模式可描述为

2.2 包裹食物

根据上述分析，黏菌位置的更新可表示为

2.3 获取食物

黏菌依靠生物振荡器产生的波改变静脉中的细胞质流动，使其处于食物浓度较高的位置。为了模拟黏菌具体静脉宽度的变化， 我们使用W、vb 和vc 描述黏菌的行为。通过模拟黏菌的振荡频率，使黏菌找到优质食物时可更快地接近食物。 当食物浓度较低时，黏菌接近食物的速度较慢，可以提高黏菌选择最佳食物源的效率。 vb 在［-a, a］内并且随着迭代次数的增加逐渐接近零。 vc 在［-1, 1］之间振荡，最终趋于零。vb 和vc 之间的协同作用模拟了黏菌的选择行为。 为了找到更好的食物来源，黏菌会分离一些有机物，用于探索其他领域，以试图找到更高质量的食物。

3 改进黏菌算法

3.1 参数p 的改进

在SMA 中，参数p 决定了黏菌的探索和开发能力，由式（6）可知，当最优个体与其他个体的适应度大于4 时，p 的取值接近1，使用公式（11）更新黏菌的位置。 对于WSN 覆盖问题，最优个体的适应度与其他个体的适应度相差较小， 容易陷入局部最优而无法寻找到更优的解。为了使开发和探索更加平衡，对p 进行重构，其表达式为

3.2 混沌精英突变策略

在原始SMA 中，种群的位置需要通过最优位置和随机位置引导， 虽然这种算法有利于增大候选解跳出局部最优的可能性， 但随机数的不确定性导致SMA 的收敛速度变慢。 为了改善算法依靠随机位置和最优位置的问题，提高算法的收敛速度，本文考虑到混沌序列的随机性、遍历性和整体稳定的特点，对最优解进行混沌精英突变，具体实现过程如下。

将最优解的位置向量从解空间降维映射到区间［-1, 1］，即可得混沌变量

3.3 基于改进黏菌算法的WSN 覆盖实现步骤

综上所述，我们提出一种改进的黏菌算法，通过对参数p 的改进，使开发和探索的能力更加平衡。 通过引入混沌精英突变策略避免算法对最优解过度依赖，提高算法的寻优能力。

对于WSN 覆盖问题，最优个体的适应度与其他个体的适应度相差较小， 容易陷入局部最优而无法寻找到更优的解， 而改进后的黏菌算法能解决该问题。 利用ISMA 求解WSN 节点部署的优化流程如图2 所示。

图2 利用ISMA 求解WSN 节点部署的优化流程

利用ISMA 求最优覆盖率的步骤表示如下：

步骤1：初始化参数，将黏菌种群的规模设定为N，空间维度为dim，最大迭代次数为Tmax，对参数z 赋值。

步骤2：初始化种群，将黏菌种群随机分布在空间中，并设置初始迭代次数t 为1。

步骤3：通过式（1）～（4）计算种群个体的WSN覆盖率，并按覆盖率的大小排序，记录最优覆盖率的个体位置。

步骤4：根据式（8）更新权重W。

步骤5：在［0, 1］内产生一个随机数r，并与z 比较。 如果r＜z,就利用式（10）更新黏菌个体位置，否则，继续在［0, 1］内生成一个随机数r1。 比较r1是否小于由式（13）得出的p，如果是，就利用式（11）更新黏菌个体的位置，否则利用式（12）更新黏菌个体的位置。

步骤6：利用式（14）、式（15）和式（17）求出变量φ（t）和H，再利用式（16）求出更新后的位置X*，计算更新后位置所对应的覆盖率。 与原位置的覆盖率进行比较，如果比原先覆盖率大，就替换原来位置及对应的覆盖率。

步骤7： 判断迭代次数t 是否达到最大迭代次数，如果达到迭代次数，就输出全局最优值并结束运算，否则，进行下一次迭代。

4 仿真实验与分析

将ISMA 与改进灰狼算法 （Improved Grey Wolf Optimization, IGWO）［12］、 改 进 的 粒 子 群 优 化 算 法（Particle Swarm Optimization, PSO-H）［13］、改进鲸鱼优化算法（Improved Whale Optimization Algorithm, IWOA）［14］及原始SMA 进行比较。 实验软件为MATLAB R2021b。

4.1 与原始SMA 对比

为了比较原始SMA 和优化ISMA 的计算效果，我们设计了3 组实验， 实验种群的规模为30， 最大迭代次数为500，其他所需参数如表1 所示。

表1 实验分组及参数设置

表2 给出SMA 和ISMA 在每个组下的覆盖率。图3 给出了该环境下SMA 和ISMA 的优化节点分布，图4、图5 和图6 分别给出了该环境下每个组的WSN 覆盖率随迭代次数的变化情况。

图3 SMA 和ISMA 在每一组下的优化节点分布

图5 组2 的WSN 覆盖率随迭代次数的变化情况

图6 组3 的WSN 覆盖率随迭代次数的变化情况

表2 SMA 与ISMA 的覆盖率对比

从表2 可以看出， 在第1 组、 第2 组和第3 组中，ISMA 的优化覆盖率比SMA 分别高出15.08%、11.76%和8.02%。 从图3、图4、图5 和图6 可以看出：在探索全局最优解方面，ISMA 比SMA 更容易跳出局部最优， 得到更佳的覆盖率；ISMA 的节点分布比SMA 的均匀。

4.2 与SMA 及其他算法的对比

假设监测区域为20 m×20 m 的正方形平面，种群规模为30，传感器节点个数为24，感知半径为2.5 m，通信半径为5 m，最大迭代次数为500。在该环境下，将ISMA 与PSO-H、IWOA、IGWO、SMA 进行对比，结果见表3。 从表3 可以看出，由ISMA 得出的WSN 覆盖率分别比其他算法高出了0.117 5%、0.080 0%、0.062 5%和0.182 %。这说明ISMA 能有效提高WSN覆盖率。

表3 各算法覆盖率对比

图7 给出了该环境下ISMA 与其他算法的WSN覆盖率随迭代次数的变化情况， 图8 给出了该环境下ISMA 与其他算法的优化节点分布。 从图7 和图8可以看出，ISMA 的WSN 覆盖率高于其他算法，优化节点分布也比其他算法更均匀。

图7 WSN 覆盖率随迭代次数变化折线图

图8 各算法优化节点分布

5 结束语

为了实现最大化无线传感器网络覆盖， 我们首先引入了改进的黏菌算法， 并在原始黏菌算法的基础上通过更改参数p 平衡了局部搜索能力和全局搜索能力；其次引入了混沌精英突变策略，通过择优选择保留了最好的位置；最后通过仿真实验得出了ISMA能有效提高WSN 覆盖率， 使节点分布更均匀的结论。 ISMA 的运用不但减少了节点数量，而且降低了部署成本。