基于混合策略人工旅鼠算法的加权多目标三维无线传感器网络覆盖优化

《Algorithms》:Weighted Multi-Objective 3D WSN Coverage Optimization Using a Hybrid-Strategy Artificial Lemming Algorithm

【字体: 大 中 小 】 时间:2026年10月24日 来源:Algorithms 2.6

编辑推荐:

  三维无线传感器网络(3D WSNs)在实际监测场景中常面临覆盖率低、节点分布不均和障碍物干扰等问题。为解决上述问题,研究人员首先通过加权和法(weighted-sum method)将多目标覆盖优化问题转化为单目标问题,然后采用旨在提升三维环境下覆盖率、节点分

  
三维无线传感器网络(3D WSNs)在实际监测场景中常面临覆盖率低、节点分布不均和障碍物干扰等问题。为解决上述问题,研究人员首先通过加权和法(weighted-sum method)将多目标覆盖优化问题转化为单目标问题,然后采用旨在提升三维环境下覆盖率、节点分布均匀性和网络连通性的混合策略人工旅鼠算法(HS-ALA)进行求解。HS-ALA采用精英引导自适应差分变异策略(elite-guided adaptive differential mutation strategy),通过调整变异因子(mutation factor)和交叉概率(crossover probability)来增强全局探索并维持种群多样性。HS-ALA还嵌入邻域搜索算子(neighborhood search operator)以细化局部搜索精度。研究人员采用一种结合惩罚函数(penalty functions)与硬约束修复(hard constraint repair)的混合方法处理三维部署场景中的障碍物约束。在CEC2017基准测试中,HS-ALA在50维和100维下的Friedman检验均排名第一(分别为1.34和1.55)。其性能优于ALA、PSO、GWO及其他算法。在包含70个传感器节点的60 m × 60 m × 60 m仿真环境中,与原始ALA相比,HS-ALA在理想场景下将覆盖率提高了12.83个百分点,并将均匀性从0.8656提高到0.9116。在两种障碍物场景中,HS-ALA均保持较高的覆盖率和均匀性,优于所有对比算法。在所有测试场景中,网络均保持100%的全局连通性。HS-ALA在不同节点规模下也表现良好,展现出良好的鲁棒性和实用价值。
研究背景。无线传感器网络(wireless sensor networks, WSNs)已广泛应用于野火检测、军事行动、医疗健康、天气监测和智慧农业等领域。三维无线传感器网络(three-dimensional wireless sensor networks, 3D WSNs)部署较二维更困难,复杂地形、障碍和随机布设易导致覆盖重叠、感知盲区和节点分布不均,降低监测性能;三维搜索空间更大、节点交互更复杂,且覆盖、均匀性和连通性相互关联,仅优化单一目标通常不足。既有Voronoi分区、3D虚拟力、群智能及混合方法在特定场景有效,但网络规模增大和地形复杂时计算成本升高、适应性受限,且多数研究侧重覆盖,对均匀性、连通性和障碍约束验证不足。人工旅鼠算法(artificial lemming algorithm, ALA)由Xiao et al.提出,结构简单、参数少,但高维复杂问题收敛慢且易陷入局部最优,尚少用于3D WSN覆盖优化。因此研究人员提出混合策略人工旅鼠算法(hybrid-strategy artificial lemming algorithm, HS-ALA),以联合提升覆盖、均匀性和连通性并处理障碍约束。研究人员将多目标覆盖优化经加权和法(weighted-sum method)转为单目标,在ALA中引入精英引导自适应差分变异(elite-guided adaptive differential mutation)和邻域搜索算子(neighborhood search operator),以惩罚函数(penalty functions)与硬约束修复(hard constraint repair)处理障碍约束,并通过CEC2017基准和3D覆盖仿真验证。结论为HS-ALA在基准测试和3D覆盖中均表现优、保持100%全局连通、具鲁棒性和实用价值,可为资源受限3D部署提供有效方案。

关键技术方法。采用加权和法构建覆盖、均匀性与连通性的适应度;在ALA中嵌入精英引导自适应差分变异、种群多样性监控和邻域搜索;以惩罚函数结合硬约束修复处理障碍、最小间距和全局连通约束,并用深度优先搜索(depth-first search, DFS)判定全局连通性;在CEC2017基准上以Friedman检验(Friedman test)和Wilcoxon符号秩检验(Wilcoxon signed-rank test,Bonferroni校正)进行统计比较;在60 m × 60 m × 60 m区域建立网格化布尔感知模型,设置理想与两种障碍场景,节点规模50–210,并开展消融实验。

4.1 基准函数测试。研究人员在CEC2017的29个函数(F1和F3–F30,排除F2)上于50维和100维比较八种算法,各独立运行30次。HS-ALA在50维和100维均于23个函数取得最佳均值;Friedman检验中均排名第一,平均秩分别为1.34和1.55;Wilcoxon符号秩检验经Bonferroni校正后(α′=0.05/7≈0.00714)显示其显著优于所有对比算法。代表函数收敛曲线表明其在单峰、多峰、混合和组合函数上总体收敛更快、最终精度更高;但在F10、F21、F22和F26等少数函数上其他算法略优。结论为HS-ALA在高维复杂搜索中具有较强优化能力和稳定性。

4.2 三维无线传感器网络覆盖优化
4.2.1 实验设置。在60 m × 60 m × 60 m区域中部署70个节点,感知半径Rs=10 m、通信半径Rc=20 m,问题维度210,种群规模50,最大迭代500次,各算法独立运行30次;比较粒子群优化(particle swarm optimization, PSO)、灰狼优化(grey wolf optimizer, GWO)、ALA、增强人工旅鼠算法(enhanced artificial lemming algorithm, EALA)、多策略改进人工旅鼠算法(multi-strategy improved artificial lemming algorithm, MsIALA)、RIME优化算法(rime optimization algorithm, RIME)和交通拥堵优化器(traffic jam optimizer, TJO),并设置理想场景与两种障碍场景,另在N=50–210下评估规模适应性。结论为该设置用于检验HS-ALA的实际覆盖优化性能。
4.2.2 灵敏度分析。在障碍场景1、70节点和30次独立运行下,先固定惩罚系数(5,5,10)比较五组目标权重,组合C(0.70,0.20,0.10)获得最高覆盖91.89%和最低标准差0.80%,均匀性0.9110居覆盖超过91%的组中第二;再固定权重比较五组惩罚系数,(1,1,2)总体最佳,覆盖92.63%、标准差0.65%、均匀性0.9113,故最终采用该权重和惩罚系数。结论为参数敏感性实验支持后续设置。
4.2.3 理想场景性能。统计比较显示HS-ALA覆盖率达88.76%,比ALA提高12.83个百分点、比EALA提高6.14个百分点,标准差0.54%最小;均匀性0.9116最佳,标准差0.52%最小;连通性0.0885,略高于ALA的0.0868,标准差0.0028较小。Wilcoxon检验表明其覆盖显著优于所有对比算法,均匀性除PSO外显著更优,连通性显著优于PSO、与RIME/GWO/ALA/EALA相当、显著低于TJO和MsIALA;广度优先搜索(breadth-first search, BFS)显示所有算法均实现100%全局连通。收敛曲线和部署概率图显示HS-ALA收敛覆盖最高、低覆盖区域最少、节点分布更均匀。结论为HS-ALA在理想场景实现三目标较好平衡。
4.2.4 障碍场景性能。两个障碍场景中障碍不阻断信号,节点不得置于障碍内;场景1覆盖92.63%,比理想场景高3.87个百分点、比EALA高6.34个百分点;场景2覆盖91.02%,比理想场景高2.26个百分点、比EALA高6.08个百分点;均匀性分别为0.9113和0.9095,均最佳;全局连通性均为100%,连通性指标分别为0.0782和0.0828。统计上HS-ALA覆盖显著优于所有算法,均匀性除PSO外显著更优,连通性显著优于PSO(场景1还优于ALA)但显著低于TJO,与其他算法无显著差异。结论为其对长方体及球体障碍形状具有适应性。
4.2.5 不同节点规模与计算成本。在理想场景和障碍场景1中,N=50–210时覆盖随N增加而提高、均匀性下降、连通性呈混合趋势;HS-ALA在所有节点规模下保持最高覆盖和均匀性,约N=100接近全覆盖,而多数其他算法约需N=210达到可比覆盖;其运行时间约为ALA的1.6–2.3倍,在N=210前随N近似线性增长且无突增。结论为HS-ALA具有良好规模适应性和节点利用效率,但计算成本较高。
4.2.6 消融研究。理想场景N=70、30次独立运行下,完整HS-ALA、去除差分进化的HS-ALA-DE和去除邻域搜索的HS-ALA-NS覆盖分别为88.76%、81.01%和78.25%,均匀性分别为0.9116、0.8816和0.8774,连通性几乎不变(0.0885、0.0887和0.0860)。结论为两个模块均贡献性能且作用互补。

4.3 讨论。基准测试表明,邻域搜索有利于单峰函数精细搜索,精英引导自适应差分变异通过动态调整变异因子和交叉概率增强全局探索、保持多样性,使多峰、混合和组合函数上保持稳定;但无单一算法在所有函数占优。3D覆盖方面,多数已有研究仅优化覆盖或限于二维,该研究在三维联合优化覆盖、均匀性和连通性;障碍场景覆盖提高主要因障碍不计入覆盖评估、有效监测体积缩小且节点被限制于自由空间,HS-ALA在仅长方体及长方体加球体障碍下均保持最佳,说明对障碍形状不敏感;全局连通约束使所有算法均达100%连通,HS-ALA中等连通性是减少冗余重叠、平衡三目标的折中;节点规模增大使覆盖提高、均匀性下降、连通性混合,HS-ALA可用更少节点达到相近覆盖;运行时间增加主要来自差分变异每代额外适应度评估,渐近复杂度与ALA同阶,成对距离和DFS检查呈二次增长,可能在大网络中成为瓶颈,空间索引、并行评估或增量更新可缓解。局限包括障碍不阻断信号、加权和无Pareto前沿且未与NSGA-II比较;未来将加入视线检查、能耗、地形和受限部署区约束,并采用Pareto方法。

研究结论(译文)。该研究提出混合策略人工旅鼠算法(HS-ALA),以在保持节点分布均匀和良好连通性的同时提高覆盖率。HS-ALA在ALA基础上加入精英引导自适应差分变异和邻域搜索,增强全局探索、维持种群多样性并提高局部精度,从而平衡探索与开发。研究人员在50维和100维CEC2017上测试HS-ALA,并将其应用于60 m × 60 m × 60 m空间的三维WSN覆盖优化;实验涵盖理想场景、两个障碍场景及50–210的节点规模。(1) 在CEC2017上,HS-ALA在50维和100维的Friedman平均秩分别为1.34和1.55,排名第一,经Bonferroni校正后显著优于对比算法(padj<0.001)。(2) 在理想场景中,其覆盖率达88.76%、均匀性达0.9116,均为所有算法最佳。(3) 在障碍场景中,场景1覆盖率达92.63%、均匀性达0.9113,场景2覆盖率达91.02%、均匀性达0.9095,仍为最佳,显示对不同障碍形状的良好适应性。(4) 在不同节点规模下,其保持最佳覆盖和均匀性,显示良好可扩展性。总之,HS-ALA通过加权和目标联合优化覆盖、均匀性和连通性,在保持100%全局连通的同时取得最佳覆盖和均匀性,提供了一种有效部署方案。
相关新闻
生物通微信公众号
微信
新浪微博

热点排行

    今日动态 | 人才市场 | 新技术专栏 | 中国科学人 | 云展台 | BioHot | 云讲堂直播 | 会展中心 | 特价专栏 | 技术快讯 | 免费试用

    版权所有 生物通

    Copyright© eBiotrade.com, All Rights Reserved

    联系信箱:

    粤ICP备09063491号