基于Halton序列WOA-GWO算法的WSN覆盖研究

摘 要：为解决无线传感器网络（WSN）随机部署时存在分布不均而导致覆盖率低的问题，提出一种基于Halton序列且结合鲸鱼优化算法与灰狼优化算法（WOA-GWO）的WSN覆盖优化方法。首先，将WOA算法与GWO算法融合，WOA算法在迭代前期有着更快的收敛速度，可在前期使WSN部署快速趋于成熟，而GWO算法能够实现局部寻优与全局寻优的平衡，将其用于算法迭代的中后期可保证WSN覆盖优化的整体性能；其次，使用融合随机因子的Halton序列方法对种群进行初始化，使传感器节点在初始化时的分布更加均匀，提升初始化种群质量；最后，将基于WOA的WSN覆盖优化、GWO的WSN覆盖优化、基于Halton序列WOA-GWO的WSN覆盖优化效果进行对比，验证本文所提方法的有效性。

关键词：无线传感器网络；覆盖优化；鲸鱼算法；灰狼算法；Halton序列；全局寻优

中图分类号：TP393.0 文献标识码：A 文章编号：2095-1302（2024）02-00-05

0 引 言

无线传感器网络（Wireless Sensor Network， WSN）是一种由大量微型传感器节点组成的网络系统，能够实现对环境中各种参数的实时监测和数据采集。WSN在环境监测、农业、医疗、交通等领域具有广阔的应用前景。然而，在WSN中，传感器节点分布不均匀会导致监测区域未被充分覆盖，从而影响监测数据的准确性和可靠性。因此，WSN能否充分覆盖成为WSN研究中的一个重要问题。WSN覆盖优化是指在保证所有监测区域被覆盖的情况下，尽可能减少传感器节点的数量。目前，常用的解决WSN覆盖问题的方法是优化算法，如粒子群算法[1]、蝴蝶优化算法[2]、麻雀搜索算法[3]等。然而，这些算法在优化效率、解决复杂问题等方面存在不足。一些研究表明，将新型的优化算法、改进的智能优化算法用于节点部署具有一定的价值及意义[4]。

鲸鱼优化算法（Whale Optimization Algorithm， WOA）是由Mirjalili等人于2016年提出的元启发式算法[5]，通过模拟随机或最佳个体捕食猎物的狩猎行为进行寻优。灰狼优化算法（Grey Wolf Optimizer， GWO）是Mirjalili等人于2014年提出的元启发式算法[6]，它通过模拟灰狼群体捕食行为，基于狼群群体协作机制来达到优化的目的。将两种算法单独用于WSN覆盖优化问题上，可以起到一定的优化效果，但覆盖率仍然较低。因此，在了解两种算法在解决WSN覆盖问题方面所呈现的优点与不足后，本文将两种算法结合起来，然后将结合后的WOA-GWO算法应用于WSN覆盖优化问题中，能够有效提高WSN覆盖率。

在本文所提出的算法中，首先将WOA与GWO算法结合；然后引入融合随机因子的Halton序列方法对种群进行初始化。将该算法应用于WSN覆盖优化问题中，实验结果表明，与基于WOA的WSN覆盖优化、GWO的WSN覆盖优化相比，基于Halton序列WOA-GWO的WSN覆盖优化效果更优，并且能用更少的迭代次数实现更高的覆盖率。

1 节点覆盖模型

假设无线传感器监测区域长为L，宽为W，将其划分成L×W个网格，网格中心点为监测点，监测节点的集合为M={m1， m2， m3， ...， mn}，节点mj的坐标为（xj， yj）；无线传感器节点集合定义为S={s1， s2， s3， ...， sn}，集合中任意一个传感器节点二维坐标表示为（xi， yi），N为传感器个数，R为传感器的感知半径。在监测过程中，若是监测节点与任意一个传感器节点距离不大于R，则认为该点被覆盖。无线传感器节点与监测节点之间的距离为：

（1）

监测节点mj能被感知的概率为：

（2）

所有传感器对mj的联合覆盖率为：

（3）

式中：sall是测量范围内的所有传感器节点。传感器节点对整个区域的监测范围就是WSN的覆盖程度，可计算出所有监测点的监测覆盖率：

（4）

2 基本算法介绍

2.1 鲸鱼优化算法

WOA是对座头鲸的特殊搜索方法和围捕机制进行模拟的算法，其中主要包括围捕猎物、气泡网捕食、搜索猎物三个重要阶段。

（1）围捕猎物

首先，在当前种群中选取最佳种群当做目前最优解，其他个体根据最优解的位置来更新自身位置，其位置更新公式如下：

（5）

（6）

式中：t表示当前迭代次数；X（t+1）表示更新后的位置；X*（t）是目前最优解的位置向量；A和C为系数向量，计算方式

如下：

（7）

（8）

式中：a在整个迭代过程中由2线性降到0；r1和r2是[0，1]中的随机向量。

（2）气泡网捕食

捕食机制分别是包围捕食和气泡网捕食。采用气泡网捕食时，位置更新用对数螺旋方程表达：

（9）

（10）

式中：D*表示当前搜索个体与当前最优解的距离；b为螺旋形状参数；l为[-1，1]间的随机数。为了模拟鲸鱼收缩包围和螺旋更新机制，用如下公式表达：

（11）

式中：p为捕食机制概率，为[0，1]间的随机数；参数A和收敛因子a随着迭代次数增加逐渐减少，若|A|lt;1，则鲸鱼包围当前最优解。

（3）搜索猎物

随机寻找猎物是除气泡网捕食法之外的方法，当|A|≥1时，鲸鱼会随机搜索，其公式为：

（12）

（13）

式中：D为当前搜索个体与随机个体的距离；Xrand（t）为当前随机个体位置。

2.2 WOA算法流程

标准WOA算法流程如图1所示。其计算流程具体如下：

（1）设置种群数量N、最大迭代次数T，初始化位置信息。

（2）计算当前种群适应度，并保留最优位置种群。

（3）计算参数a、p和系数向量A和C。判断p是否小于0.5，是则转入步骤（4），否则采用式（9）方式进行气泡网捕食。

（4）判断|A|是否小于1，是则按照式（6）包围猎物，否则按照式（12）全局搜索猎物。

（5）位置更新结束，与先前种群个体适应度进行比较，保留较优解。

（6）判断是否满足终止条件，若满足则终止算法，否则进入下一次迭代，返回步骤（3）。

2.3 灰狼优化算法

GWO是通过模拟自然界中灰狼的领导等级和狩猎机制来实现寻优的算法，其中主要包括搜索猎物、包围猎物、攻击猎物三个重要阶段。

（1）包围猎物

灰狼在狩猎过程中，利用以下公式来更新对猎物包围的位置：

（14）

（15）

式中：X表示灰狼所处位置；t表示当前迭代次数；Xp表示猎物所在位置；D表示灰狼与猎物间的距离，计算方法为

式（15）；A和C是两个协同系数向量，计算方式如下：

（16）

（17）

式中：和是[0，1]内取值的随机向量；a为收敛因子。

（2）追捕猎物

在狩猎过程中，猎物位置Xp是未知的，因此在GWO中，认为α为最优灰狼，β为次优灰狼，δ为第三优灰狼，其余灰狼为ω。根据α、β、δ来指导ω的移动，从而实现全局最优，利用α、β、δ的位置、、来更新所有灰狼位置，公式如下：

（18）

（19）

（20）

（3）攻击猎物

灰狼攻击猎物行为被抽象成数学模型，如下式所示：

（21）

式中：a为收敛因子，它决定了A的变化，a值偏大时进行全局搜索，偏小时进行局部搜索；t为当前迭代次数；T为最大迭代次数。

2.4 GWO算法流程

标准GWO算法流程如图2所示。

计算流程如下：

（1）初始化参数灰狼种群，并计算a、A、C等参数。

（2）计算当前种群灰狼适应度，保留适应度最好的前三匹狼α、β、δ。

（3）根据最优的三匹狼，更新其余ω狼的位置。

（4）更新参数a、A、C。

（5）计算全部灰狼的适应度，并更新α、β、δ狼的位置及适应度。

（6）判断是否达到最大迭代次数，若达到则终止算法，否则返回步骤（3）。

3 基于Halton序列的WOA-GWO算法

本文提出的基于Halton序列的WOA-GWO算法主要由两部分组成，首先将WOA与GWO算法融合，其次将Halton序列引入种群初始化中，下文将详细介绍其具体内容。

3.1 WOA-GWO算法

将WOA应用于整体算法的迭代前期，可使寻找最优解的收敛速度更快，在短迭代周期内便达到了较为成熟的适应度值。将GWO应用在整体算法中后期迭代阶段，既可保证GWO算法阶段内前期的全局搜索，又能够保证后期的局部寻优。

通过多组实验进行对比，发现将整体迭代次数的前10%作为WOA寻优阶段，其余90%作为GWO寻优阶段能够使寻优效果达到最佳。因此，分别将两种算法应用于WOA-GWO整体迭代过程的前10%与后90%两个阶段。

3.2 Halton序列

Halton序列是由德国数学家John Halton提出的一种低差异序列[7]，即使在较高维度的数据中，也可生成均匀分布的点。对于WSN部署问题，使用Halton序列对传感器节点进行初始化，能够使数量较少的传感器节点均匀分布在固定的空间范围内，从而使其比随机分布生成的覆盖率更大，有效提升初始种群质量。图3与图4分别为二维空间内100个点的随机分布与基于Halton序列分布图像，通过比较可以发现，基于Halton序列点的分布在平面内更加均匀。因此，将Halton序列用于WSN节点位置的初始化能够具有较好的分布效果。

由于Halton序列只能保证节点以单一的方式均匀分布，而不能保证对每个个体初始化且其具有差异性，因此，为使个体具有多样性，引入小范围的随机因子对传感器节点的初始位置进行处理。随机因子r被定义为：

r=rand-0.5" " " " " " " " " " " " " " " " " " （22）

式中：rand为[0，1]间随机数，-0.5是为了使r的值有正有负，便于计算。使用随机因子r对基于Halton序列初始化的WSN节点位置进行随机扰动，丰富了种群的多样性。图5为随机扰动后的Halton序列生成的节点分布，可以看出图中各点与图4中各点具有明显差异，但其分布仍比较均匀。

3.3 算法流程

基于Halton序列的WOA-GWO算法流程如图6所示。

计算流程具体如下：

（1）初始化种群数量N、最大迭代次数T等参数，并设置当前迭代次数t=1。

（2）使用随机Halton序列对种群位置进行初始化。

（3）判断当前迭代次数是否小于总迭代次数的0.1倍，若小于则使用WOA算法更新种群位置，否则使用GWO算法更新种群位置。

（4）更新最优种群的位置。

（5）判断是否达到最大迭代次数，若达到则终止算法，否则返回步骤（3）。

4 实验仿真与分析

4.1 实验环境设置

本文在MATLABR2022a平台上对所提方法进行仿真，对其性能等进行测试。将基于Halton序列WOA-GWO的WSN覆盖效果与基于WOA的WSN覆盖和基于GWO的WSN覆盖效果进行对比。为保证算法的公平性，在实验过程中对算法设置相同参数，监测区域面积为50 m×50 m，节点数量为40个，种群规模为100个，感知半径为5 m，迭代次数设置为500。

4.2 仿真结果与分析

按照上述参数进行仿真实验，图7～图12为仿真结果。图7为传感器节点随机初始化的覆盖图，图8为基于随机Halton序列的节点初始化覆盖图，图9为基于WOA的WSN仿真覆盖图，图10为基于GWO的WSN仿真覆盖图，图11为基于Halton序列的WOA-GWO仿真覆盖图，图12为三种算法在各迭代次数中最高覆盖率的变化曲线。

从图7和图8的对比可以看出，相对于传感器节点随机部署，基于随机Halton序列可使节点在初始化时使得传感器节点分布更加均匀，具有更高的覆盖率。通过图9～图11的对比可以看出，基于WOA的WSN覆盖优化与基于GWO的WSN覆盖优化都使传感器节点的覆盖率得到了一定提升，但仍存在一些覆盖盲区，而基于Halton序列的WOA-GWO覆盖优化后，传感器节点分布更加均匀，覆盖率也高于前两种方法。

从图12可以对比出三种算法在WSN覆盖优化过程的覆盖率变化曲线。基于WOA的WSN覆盖优化在前30次迭代中，收敛速度明显优于GWO算法，然后收敛速度趋于平缓，偶尔会提高覆盖率，最终覆盖率达到86.44%；基于GWO算法的WSN覆盖优化在整个迭代过程中覆盖率不断提升，并且最终覆盖率较高，达到了96.68%；基于Halton序列的WOA-GWO覆盖优化综合了两种算法的优点，并且基于Halton序列对种群进行初始化，使其在迭代最初便处于较高的覆盖率，而且既能够保持前期快速收敛，也能够保证算法迭代全程中不断寻优，最终覆盖率达到97.88%。相对于前两种WSN覆盖优化算法，该算法能够实现更高的覆盖率。

5 结 语

本文针对无线传感器网络覆盖优化问题，融合鲸鱼优化算法和灰狼优化算法，并引入Halton序列对种群进行初始化，提出一种基于Halton序列的WOA-GWO算法，然后将其应用于无线传感器网络覆盖优化中。通过仿真实验将本文所提算法与基于WOA的WSN覆盖优化、基于GWO的WSN覆盖优化进行对比分析。仿真结果表明，本文所提算法在WSN覆盖优化问题上具有更强的覆盖优化性能，优化后WSN的覆盖率更高。

注：本文通讯作者为冯锋。

参考文献

[1] KENNEDY J，RUSSELL E. Particle swarm optimization [C]// Proceedings of ICNN'95-international conference on neural networks. IEEE，1995.

[2] ARORA S，SINGH S. Butterfly optimization algorithm：a novel approach for global optimization [J]. Soft computing，2019，23：715-734.

[3] XUE J，SHEN B. A novel swarm intelligence optimization approach：sparrow search algorithm [J]. Systems science amp; control engineering，2020，8（1）：22-34.

[4]张孟健，汪敏，王霄，等.混合粒子群-蝴蝶算法的WSN节点部署研究[J].计算机工程与科学，2022，44（6）：1013-1022.

[5] MIRJALILI S，LEWIS A. The whale optimization algorithm [J]. Advances in engineering software，2016，95：51-67.

[6] MIRJALILI S，MIRJALILI S M，LEWIS A. Grey wolf optimizer [J]. Advances in engineering software，2014，69：46-61.

[7] HALTON J H. On the efficiency of certain quasi-random sequences of points in evaluating multi-dimensional integrals [J]. Numerische mathematik，1960，2：84-90.

[8]刘紫娟，田文艳.鲸鱼算法的优化[J].物联网技术，2021，11（1）：42-46.

[9]黄冬民，潘泉，梁新华.基于随机化Halton序列的粒子滤波算法研究[J].计算机应用研究，2011，28（1）：91-94.

[10]高敏，刘海荣，朱燕飞.基于改进灰狼优化算法的WSN覆盖优化[J].上海师范大学学报（自然科学版），2023，66（2）：256-263.