面向无线异构传感器网络的三维覆盖研究

黄德昌 蔡芳龙 黄招娣 吴章

收稿日期：2023-09-21

基金项目：江西省自然科学基金项目（20232BAA10012）；江西省教育厅科学技术研究项目（GJJ210610）

文章编号：1005-0523（2024）03-0082-08

摘要：【目的】为达到增强无线异构传感器网络（HWSN）三维覆盖能力的目的，提出了一种基于改进蜜獾优化算法（IHBA）的无线异构传感器网络三维部署方法。【方法】首先，结合自适应果蝇优化算法，增强算法的随机搜索性，便于算法得到全局最优解，然后引入替换最差个体策略，避免适应度过低的个体占据种群位置，提高算法收敛速度，同时引入新个体提高种群多样性，避免算法个体早熟。【结果】将该算法应用于无线异构传感器网络的覆盖优化，相比标准蜜獾算法，其网络覆盖率提升18.1%。【结论】仿真结果表明，该算法收敛速度更快，可以有效提高无线异构传感器的网络覆盖能力，整个网络的节点分布也更加均匀。

关键词：无线异构传感器网络；蜜獾算法；自适应果蝇优化算法；替换最差个体策略

中图分类号：TP212.9；U495 文献标志码：A

本文引用格式：黄德昌，蔡芳龙，黄招娣，等. 面向无线异构传感器网络的三维覆盖研究[J]. 华东交通大学学报，2024，41（3）：82-89.

Research on Three-Dimensional Coverage for Wireless Heterogeneous Sensor Networks

Huang Dechang， Cai Fanglong， Huang Zhaodi， Wu Zhang

（School of Information Engineering， East China Jiaotong University， Nanchang 330013， China）

Abstract： 【Objective】In order to enhance the 3D coverage capability of wireless heterogeneous sensor networks （HWSN）， a 3D deployment method based on improved honey badger optimization algorithm （IHBA） is proposed. 【Method】Firstly， combined with the adaptive fruit fly optimization algorithm， the random search ability of the algorithm is enhanced， which is convenient for the algorithm to obtain the global optimal solution. Then， the strategy of replacing the worst individual is introduced to avoid the low adapting individual to occupy the population position and improve algorithm convergence speed. In the meantime， new individuals are introduced to improve the population diversity and avoid the individual prematurity of the algorithm. 【Result】This algorithm is applied to the coverage optimization of HWSN， and the network coverage is improved by 18.1% compared with the standard Honey Badger algorithm. 【Conclusion】The simulation results show that the algorithm converges faster， can effectively improve the network coverage capability of wireless heterogeneous sensors， and the node distribution of the whole network is more uniform.

Key words： wireless heterogeneous sensor networks （HWSN）; honey badger algorithm; adaptive fruit fly optimization algorithm; the worst individual strategy replacement

Citation format： HUANG D C， CAI F L， HUANG Z D， et al. Research on three-dimensional coverage for wireless heterogeneous sensor networks[J]. Journal of East China Jiaotong University， 2024， 41（3）： 82-89.

【研究意义】随着无线通信技术的不断发展，无线异构传感器网络（heterogeneous wireless sensor networks，HWSN）已逐渐成为全球社会生产和生活不可或缺的重要技术手段[1] 。无线异构传感器网络可应用于诸多领域，如农业生产、车辆检测、环境监测、工 业自动化、交通信号控制等领域[2-4]，是实现智慧交通、智慧城市的关键技术之一。在无线异构传感器网络应用中，如何高效地进行网络覆盖是亟须解决的问题[5-6]。

【研究进展】近年来，为提高复杂三维地形的异构传感器网络覆盖，无线异构传感器网络的三维覆盖得到了广泛且深入的研究[7-8]。冯秀芳等[9]提出了基于虚拟力的异构节点网络覆盖增强算法，在传感器节点之间引入虚拟力来最大化网络覆盖率。刘鹏等[10]提出了一种基于自适应果蝇优化算法的分层异构无线传感器网络三维优化部署，模拟果蝇较强的随机搜索性，加快算法的搜索速度。吴仪等[11]针对异构传感器网络部署时引发的随机空洞与冗余均衡问题，提出一种空洞弧段引导下异构传感网的覆盖优化策略，实现了本地化的空洞识别和低耗适配的空洞修补。李明等[12]针对给定部署区域在不同的子区域有不同的重要性，部署的移动传感器节点具有不同可靠性、寿命、能量和移动能力的复杂条件下节点部署优化问题，提出了一种改进的微分进化算法，增强了算法的局部搜索能力，有效提高了算法覆盖性能。苟平章等[13]针对异构无线传感器网络中初始节点随机部署或节点失效产生覆盖盲区的问题，提出一种节点稳定匹配的覆盖空洞修复优化算法，利用Voronoi多边形划分确定节点覆盖盲区，使得算法收敛速度加快，匹配次数和节点移动距离减少，覆盖率提高。

【创新特色】综合现有研究，本文从算法搜索性能、跳出局部最优能力的角度进行研究，首先引入自适应果蝇算法增强算法搜索的随机性，从而提高算法前期的搜索能力；其次在算法迭代过程中进行替换最差个体操作，减少迭代种群中适应度过低的个体，从而加快了算法的收敛速度，同时引入新个体，避免算法陷入局部最优。

【关键问题】为了有效提高异构传感器网络覆盖范围，减少不必要的资源浪费，结合上述改进策略，本文提出了一种基于改进型蜜獾优化算法的无线异构传感器网络覆盖方法。该方法首先将区域覆盖率映射为适应度函数，传感器节点坐标映射为蜜獾个体的位置，并引入蜜獾算法，结合自适应果蝇优化算法、替换最差个体策略形成改进型蜜獾算法，进而优化传感器节点坐标，以提高区域网络覆盖率。

1 传感器网络模型

1.1 覆盖模型

在HWSN中，节点感知模型可分为两类：0/1感知模型和概率感知模型。其中，0/1感知模型旨在模拟一个以传感器节点为中心，r为感知半径的球形空间，当监测点位于该感知半径内时，就可以认定其已被覆盖。在三维空间中，传感器节点[si（xi，yi，zi）]与监测节点[mj（xj，yj，zi）]之间的欧氏距离为

[d（si，mj）=（xi-xj）2+（yi-yj）2+（zi-zj）2] （1）

传感器节点对监测节点的感知概率定义如下

[Pcov（si，mj）=1，0， d（si， mj）≤r  d（si， mj）>r] （2）

将所有传感器节点[sall]在目标检测环境中的区域覆盖率[Rp（sall，mj）]定义为传感器节点的覆盖体积与监测区域的空间体积[Vol]之比，如下

[Rp（sall，mj）=PcovVol] （3）

为使得覆盖率最大，所求问题可描述为

[f=max（Rp）] （4）

1.2 有效覆盖模型

讨论节点对监测区域的覆盖情况，采用一种有效覆盖率作为可靠性指标之一，网络的有效覆盖率越高，说明节点覆盖利用率越高。有效覆盖率用[Rt]表示

[Rt=RpRm] （5）

式中：[Rm]为所有传感器节点能覆盖的最大体积。

2 蜜獾算法

蜜獾算法的基础是蜜獾的智能搜索行为，蜜獾通过嗅觉发现食物的位置，并在接近食物的地方进行挖掘，以获取食物。此外，蜜獾还可以跟随导蜜鸟的指引，找到蜂巢，获得蜂蜜。Hashim等基于蜜獾寻找食物源的行为建立了标准蜜獾算法模型[14]。

2.1 种群初始化阶段

在目标区域内，对蜜獾的种群规模和个体位置随机初始化

[xi=lbi+r1×（ubi-lbi）] （6）

式中：[xi]为种群中第[i]个蜜獾的位置；[r1]为0～1的随机数；[lbi，ubi]分别为目标区域的下界和上界。

2.2 定义强度I

蜜獾的嗅觉强度取决于它们对猎物的注意力和距离。气味强度和运动速度成正比。猎物的气味强度用[Ii]表示为

[Ii=r2×S4πd2iS=（xi-xi+1）2di=xprey-xi] （7）

式中：[r2]为0～1的随机数；[S]为猎物集中强度；[di]为当前蜜獾与猎物的距离。

2.3 更新密度因子

密度因子[α]受迭代次数控制，当更新随着迭代次数减少，密度因子[α]也会减少随机化，来确保勘探阶段能平稳过渡到开发阶段，从而减少蜜獾觅食过程中的不确定性。计算式为

[α=C×exp-ttmax] （8）

式中：[C≥1]（一般默认为2）；[tmax]为最大迭代次数。

2.4 挖掘阶段

在挖掘阶段，蜜獾的运动轨迹类似于心脏线，其运动轨迹公式如下

[xnew=xprey+F×β×I×xprey+          F×r3×α×di×cos（2πr4）×1-cos（2πr5）] （9）

式中：[xprey]为蜜獾的全局最优位置；[r3，r4，r5]为3个0～1的不同随机数；[β]为蜜獾获取食物的能力，取值大于等于1，一般默认为6；[F]为搜索方向的变向标记，其公式如下

[F=1，-1， r6<0.5r6≥0.5] （10）

式中：[r6]为0～1的随机数，在蜜獾挖掘阶段中，蜜獾比较依赖气味强度，同时挖掘期间会受到干扰，从而导致蜜獾无法寻找到更好的位置。

2.5 采蜜阶段

蜜獾在导蜜鸟的指引下，成功地发现蜂巢的过程可用公式表达为

[xnew=xprey+F×r7×α×di] （11）

式中：[r7]为0～1的随机数；[xnew]为蜜獾个体更新后的位置；[xprey]为食物源的位置。由上式可知，蜜獾在猎物附近进行搜索。

3 改进型蜜獾算法

针对蜜獾算法在解决优化问题时存在的问题，结合果蝇优化算法、替换最差个体策略提出一种改进型蜜獾算法，替换最差蜜獾个体，保留优良蜜獾个体，同时增加蜜獾随机搜索能力，从而增强算法寻优过程的稳定性以及算法的跳出局部最优能力[15]。

3.1 结合果蝇优化算法

果蝇优化算法（fruit fly optimization algorithm，FOA）是一种较新的优化算法，它仿照果蝇觅食的行为，来优化复杂问题。FOA遵循果蝇群体智能的自组织行为；思想简单，参数少，易于实现；既利用全局随机搜索，也融入局部聚集搜索；FOA的缺点则是容易陷入局部最优，收敛速度相对较慢。

参考刘鹏等[10]提出的一种基于自适应果蝇优化算法的分层异构无线传感器网络三维优化部署方法；将其引入标准蜜獾算法的采蜜阶段当中，对于蜜獾进行更新，更新的计算公式如下

[xnew=xprey+2×sl×rand-sl] （12）

式中：[rand]为0～1之间的随机数；[sl]为果蝇飞行的自适应步长，其计算公式为[sl=0.3×α]；引入自适应步长果蝇优化算法，参数少，易于实现；步长随着迭代次数的增加而减小，满足前期全局搜索最优，后期局部聚集搜索最优的特性。

3.2 替换最差个体策略

替换最差个体是一种选择操作，它会替换种群中最差适应度的个体，以维持种群的进化质量。替换最差个体能避免适应度过低的个体占据种群位置，提高算法收敛速度，同时引入新个体提高种群多样性。替换最差个体主要思想为：找到种群中的最优适应度[max_n]以及最差适应度[min_n]，根据最优适应个体以及最差适应个体设定一个评估阈值[lim]，评估阈值计算公式如下

[lim=（max_n-min_n）×0.2+min_n] （13）

若种群中的个体适应度小于评估阈值，则判定为需要被替换的个体，替换方式则是用最优个体的位置替换该个体的位置，用最优个体的适应度值替换该个体的适应度值。

3.3 IHBA实现流程

IHBA算法实现流程如下。

Step 1 设置种群数N，蜜獾个体数目[n]，最大迭代次数[tmax]，目标区域上下界[ub]和[lb]，蜜獾获取食物能力[β]等参数，并初始化蜜獾种群；

Step 2 计算蜜獾个体的适应度 ，确定食物源；

Step 3 开始迭代，随机生成一个概率r，概率大于0.5进入Step 4，否则跳转到Step 5；

Step 4 进入蜜獾挖掘阶段，用式（9）更新蜜獾个体位置；

Step 5 采用自适应果蝇优化算法的搜索方式，用式（12）更新蜜獾个体位置；

Step 6 对种群所有个体的适应度进行评估，选出最优个体适应度以及最差个体适应度，根据最优适应度以及最差适应度设定评估阈值：若蜜獾个体的适应度低于评估阈值，则判定为需要被替换个体，用最优个体的位置以及适应度值替换该个体的位置以及适应度值；

Step 7 计算蜜獾个体适应度，更新食物源位置及其适应度；

Step 8 判断是否达到最大迭代次数，若满足条件则输出最优解，程序结束，反之跳转到Step 3。

3.4 IHBA流程图

图1所示为IHBA实现的流程图，其实现流程与3.3节中的步骤一致，概括了IHBA算法从种群初始化到输出最优解的过程。

4 仿真及对比分析

为了验证IHBA对无线异构传感器网络覆盖的有效性，将无线异构传感器节点位置映射为蜜獾个体位置，无线异构传感器网络节点覆盖率映射为适应度；并选择与基本的HBA算法和粒子群算法在MATLAB R2019a的环境中进行无线异构传感器网络优化对比，通用实验参数一致。参与对比的算法有HBA、PSO（粒子群优化算法）。实验评价指标为无线传感器覆盖率、有效覆盖率以及算法运行时间。

4.1 仿真实验

4.1.1 目标区域为20×20×20覆盖优化对比

本组实验采用两种不同感知半径的传感器进行仿真，感知半径分别为3，5 m，其数量分别选取30，10，在不考虑间隙误差情况以及覆盖模型形状的情况下，本组参数的异构传感器恰好能够完全监测空间，具体实验参数如表1所示。图2，图3，图4分别为HBA、PSO与IHBA的节点分布对比，图5所示为IHBA与HBA、PSO的覆盖率收敛情况对比。表2展示了不同算法的覆盖率优化结果，其中包括HBA、IHBA、PSO。

图中红色球体表示半径为5 m的传感器节点覆盖空间，蓝色表示半径为3 m的传感器节点覆盖空间；通过观察，IHBA优化后，节点位置分布更均匀、排列更整齐；HBA以及PSO优化后的节点覆盖盲点较多，冗余性更高。

从图5可以看出，PSO较早地获得了局部最优解，并没有获得全局最优解；HBA前期更新迭代慢，搜索速度较慢，并且没有获取到全局最优解；相比前两种方法，IHBA的效果更好，自适应果蝇算法的引入增强了算法搜索的随机性，从而增强了算法前期搜索能力。在算法迭代中替换最差个体，减少迭代种群中适应度过低的个体，从而提高了算法的收敛速度；同时引入新个体，避免了算法陷入局部最优，算法中后期覆盖率缓慢增长，也说明IHBA能够跳出局部最优，找到更优的全局解。

由表2可知，IHBA进行500次迭代优化后，相比基本HBA，PSO覆盖率分别提高18.1%，15.1%；有效覆盖率与覆盖率相差较小，说明优化后的节点利用率较高，节点冗余较少；在引入改进策略后，IHBA与HBA的算法运行时间相近，可见引入改进策略后并未明显拖慢算法效率。

4.1.2 目标区域为50×50×50覆盖优化对比

本组实验采用感知半径分别为5，8 m的传感器进行仿真，其数量分别选取55，45，在不考虑间隙误差情况以及覆盖模型形状的情况下，该组参数的异构传感器恰好能够完全监测空间，具体实验参数如表3所示。

图6，图7，图8分别为HBA优化节点分布图，PSO优化节点分布图以及IHBA优化节点分布图，图中红色球体表示半径为8 m的传感器节点覆盖空间，其余均表示半径为5 m的传感器节点覆盖空间。通过仿真效果图可知，IHBA优化后，节点位置分布更均匀，覆盖盲点少；HBA以及PSO优化后的节点分布散乱，覆盖冗余性较高。

从图9可以看出，在将目标空间增大、节点数量规模增加后，PSO，HBA均出现前期更新迭代慢，搜索速度较慢，并且没有获取到全局最优解的情况；相比之下，IHBA依旧能够进行较快地搜索，这表明结合的自适应果蝇算法在规模增大的情况下依旧具备较强的搜索随机性，从而增强了算法的搜索能力。在算法迭代中替换最差个体，避免迭代种群中适应度过低的个体占据过多的位置，加快了算法的收敛速度，同时引入新个体，增强了算法跳出局部最优能力，算法中后期覆盖率缓慢增长，也说明IHBA具备跳出局部最优的能力，继而寻找到全局最优解。

由表4可知，IHBA进行500次迭代优化后，覆盖率相比基本HBA、PSO分别提高了17.5%、16.6%；覆盖率与有效覆盖率接近，表明节点利用率较高，覆盖重叠区域较少；IHBA与HBA的算法运行时间相近，说明引入改进策略后并未明显拖慢算法效率。可见IHBA在无线异构传感器网络覆盖应用中具备有效性和可行性。

4.2 仿真结果分析

从以上仿真实验可以得出，改进型蜜獾算法具有良好的收敛速度、较强的探索性和跳出局部最优的能力，自适应果蝇算法的引入增强了算法搜索的随机性，从而增强了算法前期搜索能力；在算法迭代中进行替换最差个体操作，减少迭代种群中适应度过低的个体，从而提高了算法的收敛速度，同时引入新个体，避免了算法陷入局部最优。将该算法应用到HWSN的覆盖优化问题中，能够有效提高异构网络覆盖范围，减少不必要的节点部署，从而节省覆盖所需的资源和成本。

5 结论

针对无线异构传感器网络覆盖优化问题，本文提出了一种改进型蜜獾算法优化异构传感器节点网络的覆盖。通过结合自适应果蝇优化算法，以及引入替换最差个体策略，对标准蜜獾算法进行改进，通过仿真分析，得出以下结论。

1） 引入改进策略后，有效地增强了算法的搜索性能和收敛速度。

2） 将其应用在无线异构传感器网络中，异构网络覆盖率得到较好地提升。

3） 未来工作可以考虑无线异构网络节点连通度、通信质量以及节点能耗等。

参考文献：

[1]   YAKUBU A W， ALHASSAN A B， SALIFU A M. An enhanced clustering method for extending sensing lifetime of wireless sensor network[J]. Earthline Journal of Mathematical Sciences， 2021， 8（1）： 67-82.

[2]   WANG J， GUO H Y. Virtual force field coverage algorithms for wireless sensor networks in water environments[J]. International Journal of Sensor Networks， 2020， 32（3）： 174-181.

[3]   SAADI N， BOUNCEUR A， EULER R， et al. Maximum lifetime target coverage in wireless sensor networks[J]. Wireless Personal Communications， 2020， 111（3）： 1525-1543.

[4]   MOHAMMAD M， OZDEMIR S. Towards coverage-aware fuzzy logic-based faulty node detection in heterogeneous wireless sensor networks[J]. Wireless Personal Communications， 2020， 111（1）： 581-610.

[5]   GOU P， GUO B， GUO M， et al. VKECE-3D： Energy-efficient coverage enhancement in three-dimensional heterogeneous wireless sensor networks based on 3D-voronoi and K-means algorithm[J]. Sensors， 2023， 23（2）： 573.

[6]   ZENG C， QIN T， TAN W， et al. Coverage optimization of heterogeneous wireless sensor network based on improved wild horse optimizer[J]. Biomimetics， 2023， 8（1）： 70.

[7]   DAO T K， CHU S C， NGUYEN T T， et al. An optimal WSN node coverage based on enhanced archimedes optimization algorithm[J]. Entropy， 2022， 24（8）： 1018.

[8]   TOLOUEIASHTIAN M， GOLSORKHTABARAMIRI M， RAD S Y B. An improved whale optimization algorithm solving the point coverage problem in wireless sensor networks[J]. Telecommunication Systems， 2022， 79（3）： 417-436.

[9]   冯秀芳， 关志艳， 全欣娜. 基于虚拟力的异构节点网络覆盖增强算法[J]. 计算机工程， 2009， 35（5）： 103-105.

FENG X F， GUAN Z， QUAN X N. Coverage-enhancing algorithm for non-isomorphic node network based on virtual force[J]. Computer Engineering， 2009， 35（5）： 103-105.

[10] 刘鹏， 孟欣， 唐苏琼， 等. 基于自适应果蝇优化算法的分层异构无线异构传感器网络三维优化部署[J]. 传感技术学报， 2020， 33（7）： 1033-1040.

LIU P， MENG X， TANG S， et al. Optimization on 3D deployment of hierarchical heterogeneous wireless sensor networks： An adaptive FOA approach[J]. Chinese Journal of Sensors and Actuators， 2020， 33（7）： 1033-1040.

[11] 吴仪， 秦宁宁. 空洞弧段引导下异构传感网的覆盖优化策略[J]. 传感技术学报， 2021， 34 （4）： 531-538.

WU Y， QIN N N. Coverage optimization strategy of heterogeneous sensor network guided by hollow arc[J]. Chinese Journal of Sensors and Actuators， 2021， 34 （4）： 531-538.

[12] 李明， 胡江平. 复杂条件下移动异构无线传感器网络覆盖算法[J]. 传感器与微系统， 2019， 38 （12）： 124-127.

LI M， HU J P， et al. Coverage algorithm for mobile heterogeneous WSNs under complex conditions[J]. Transducer and Microsystem Technologies ， 2019， 38 （12）： 124-127.

[13] 苟平章， 毛刚， 李凤珍， 等. 异构WSNs中节点稳定匹配的覆盖空洞修复优化算法[J]. 传感技术学报， 2019， 32 （6）： 908-914.

GOU P Z， MAO G， LI F Z， et al. Optimized algorithm for recovering coverage holes in heterogeneous wireless sensor networks with node stable matching[J]. Chinese Journal of Sensors and Actuators， 2019， 32 （6）： 908-914.

[14] HASHIM F A， HOUSSEIN E H， HUSSAIN K， et al. Honey badger algorithm： New metaheuristic algorithm for solving optimization problems[J]. Mathematics and Computers in Simulation， 2022（192）： 84-110.

[15] DAO T K， NGUYEN T D， NGUYEN V T. An improved honey badger algorithm for coverage optimization in wireless sensor network[J]. Journal of Internet Technology， 2023， 24（2）： 363-377.

通信作者：黄德昌（1983—），男，硕士，高级实验师，研究方向为物联网、机器学习。E-mail： 2777@ecjtu.edu.cn。