基于改进蝙蝠算法的无线传感器网络覆盖增强策略.pdf

：引用格式：罗卢洋，王传基于改进蝙蝠算法的无线传感器网络覆盖增强策略无线电工程，（）：，（）：基于改进蝙蝠算法的无线传感器网络覆盖增强策略罗卢洋，王传（南宁学院 食品与质量工程学院，广西 南宁；广西昊华科技股份有限公司，广西 南宁）摘要：为解决无线传感器网络中存在的冗余节点较多及覆盖不全的问题，优化传感器节点的移动距离及网络的覆盖效率，提出了一种改进蝙蝠算法（，）的无线传感器网络覆盖增强策略。通过蜂窝网格对监控区域进行堆叠，构建节点和蜂窝网格之间的二分图模型，最小化和平衡网络重新部署期间的移动距离。基于黄金正弦方法提出一种改进的，将全局寻优和局部寻优相结合得到最优策略，对冗余节点进行删除处理，得到路径最短、平滑度最高的最优路径。在不同大小的监控区域中部署不同数量的传感器节点进行仿真实验，将所提方法与其他几种算法进行对比分析。实验结果表明，所提算法可有效提高节点分布均匀性并降低网络覆盖冗余度，网络覆盖率和节点平均移动距离均优于其他种对比算法。关键词：无线传感器网络；传感器节点；蝙蝠算法；网络覆盖；节点移动距离中图分类号：文献标志码：开放科学（资源服务）标识码（）：文 章 编 号：（），（，；，）：，（），：；引言随着无线通信的不断发展，物联网技术已逐渐成为全球社会生产和生活不可或缺的重要技术手段，对加快建设智能城市、推动产业结构调整、提升社会和公共服务能力具有重要的意义。其中，无线传感器网络（，）是物联网的重要组成部分，由许多部署在指定区域的微收稿日期：基金项目：广西重点研发项目（）；南宁市青秀区科技项目（）：（）；（）信号与信息处理 年 无线电工程 第 卷 第 期 型化、智能化和低功耗的传感器节点组成，能够协同感知、收集和处理网络覆盖区域内的所有信息，并将其发送给网络所有者。近年来，随着自动化技术、分布式信息处理技术等的发展，已被广泛应用于智能家居、环境监测、应急通信和农业生产等领域。在中，覆盖控制和节点部署是衡量网络服务质量的重要指标，它决定了传感器节点环境感知的能力，是的核心关键技术。的覆盖控制和节点部署问题本质上是使用尽可能少的传感节点来最大化指定区域的网络覆盖。但传感节点一般随机部署在目标区域，节点位置往往偏离最佳点位，从而造成节点分布不均匀，引发网络覆盖漏洞问题，影响网络服务质量。所以，对中传感器节点进行合理部署，提升覆盖能力、数据传输的可靠性，以及网络通信等服务质量，成为当前技术研究的重要方向。当前，覆盖增强主要有确定性部署和随机部署种方法。其中，确定性部署方法的传感器节点数量和位置是已知的，适用于小规模或已知环境场景中的网络覆盖部署，但是该部署方法灵活性不足。而随机部署方法是让传感器节点在目标环境中进行任意部署，适用于野外及恶劣环境中，但该方法容易造成覆盖漏洞，并产生大量冗余节点，造成能量和成本的过度浪费。为解决上述问题，国内外学者们展开了对覆盖技术的相关研究。文献提出了一种增强型麻雀搜索算法，通过降低个体局部极值点约束力跳出局部最优，从而提高网络覆盖率。文献提出了一种基于元胞自动机规则的优化方法，可通过最少数量的传感器节点覆盖网络空间，但该方法容易造成覆盖漏洞，导致在监控区域内产生冗余节点。文献提出了一种基于改进蚁狮算法的网络覆盖优化方法，结合动态混合变异方法与收敛判断机制实现局部最优，从而优化节点分布。文献提出了一种基于维诺图的覆盖增强策略，能够快速找到网络覆盖空洞并进行修复，有效提高网络覆盖率和均匀性，但该方法容易陷入局部最优解，同时其收敛速度慢、精度低。文献对水波纹算法进行了研究并提出了基于该算法的覆盖策略，能够获得约的区域覆盖率，但该方法的收敛速度较慢。因此，鉴于上述问题，本文对蝙蝠算法（，）进行了改进并基于此提出了新型覆盖增强策略。首先，通过引入黄金正弦方法，将蝙蝠种群按不同适应度进行分类，并使用全维搜索与单维搜索相结合的方式，分阶段对两种搜索方法的劣势进行互补，进而实现了算法寻优能力的提升。获得最优解后，删除中的冗余节点，从而得到最优路径。最后，在实验室中通过仿真实验对本文所提方法的可靠性和先进性进行了验证。问题描述 网络覆盖模型本文所构建的模型如图所示，在的目标区域内分布着个没有任何障碍物的传感器节点，其中为目标区域的长，为目标区域的宽。该模型主要由接收器构成控制中心，用于收集传感器的位置信息，并向传感器广播控制中心发布命令。图模型 为反映传感器节点间感知能力的不确定性和差异性，模型要考虑噪声（如白噪声或内部热噪声）、环境（如湿度或传播路径）和功率消耗对接收信号的干扰。假设所有节点均可以通过高级定位算法实现精确定位，并根据预设的路由协议将位置信息发送给控制中心。同时，假设节点的感知半径满足正态分布（，），其中表示平均感应半径，为标准偏差。评价指标网络覆盖率和移动距离是节点部署中最关键的个指标，其详细计算如下：覆盖率：为计算的覆盖率，需将监测区域划分为个网格，网格的质心与节点之信号与信息处理 间的距离表示为，则节点能够成功感知到的概率表示为（，），如式（）所示：（，），（）式中：为节点的感知半径。若网格质心一旦被任何节点感测到，则表示网格被成功覆盖，表示为。由此，可得到覆盖率的计算表达式：。（）移动距离：节点重新部署期间能量消耗主要来自节点移动和信号传输，且传感器的能量消耗是根据节点的移动距离测量的。因此，在重新部署后，令节点的总移动距离表示为，如式（）所示：，（）式中：为节点数量，为节点重新部署期间的移动距离。同时，将移动距离均匀性定义为，其数学表达如式（）所示：()槡。（）由此，可计算得到最大移动距离，如式（）所示：，。（）蜂窝网格划分对于，要在没有任何感知半径差异的情况下确定节点的最优部署，等同于找到一个堆叠效率最高的正多边形。而蜂窝网格被认为是具有最高堆叠效率的多边形，因此将蜂窝网格作为二维区域的最佳部署。为保证重新部署后节点的均匀分布，将所有节点的平均感知半径作为蜂窝网格的外接圆半径，蜂窝网格划分如图所示。从图中可以看出，所提蜂窝网格划分以监测区域中心的蜂窝网格为基准，其质心定义为，且相邻蜂窝网格之间存在如式（）式（）所示关系：槡，（）槡，（），（）。（）则蜂窝网格的质心的坐标可表示为（，槡）。图蜂窝网格划分 因此，对于给定监测区域和感应半径的，需要通过以下步骤计算所需的蜂窝网格数：由于蜂窝网格的质心与监测区域右上侧边缘的距离为（）。因此，、方向所需的最小蜂窝网格数计算如下：?。（）由于蜂窝网格的质心与监测区域的右上侧边缘的距离为（）。因此，和方向所需的最小数量蜂窝网格数计算如下：?（）?（）。（）将前两步蜂窝网格数相加，即可得到所需的最终最小蜂窝网格数，即。根据 上 述 计 算 方 法，当 监 测 区 域 大 小为 ，蜂窝网格外接圆半径 时，则最少需要个蜂窝网格，其划分效果如图所示。图 区域网格划分效果 信号与信息处理 年 无线电工程 第 卷 第 期 通过上述分析，可将覆盖增强转化为二分图匹配问题，将其节点移动到蜂窝网格质心，二分图的效率矩阵可表示为：，（）式中：，表示传感器节点到蜂窝网格质心的距离，则根据重新部署期间节点的移动距离将目标函数定义为（），其中、分别表示考虑总移动距离和移动距离均匀性的函数，其数学表达式为：，（，）槡，（）其中，约束条件如式（）所示：，。（）基于改进的覆盖增强策略 传统是对自然界中蝙蝠的飞行行为进行模仿的启发式算法。算法具体内容如下：首先，根据种群情况实现适应度函数的构建，并根据适应度函数对蝙蝠个体的适应度值进行计算；然后，比较种群中蝙蝠个体适应度值的大小，并将其中适应度值最大的蝙蝠记录为最优，依据此最优蝙蝠的个体信息（位置和速度）对种群中其他个体进行信息更新。最后，使用局部寻优方法在最优蝙蝠周围进行局部搜索，以寻得更优解，如此不断迭代算法直至获得全局最优解。式（）式（）所示为蝙蝠算法的适应度函数及位置、速度更新公式：（），（）（），（），（）式中：为蝙蝠的声波脉冲频率，、分别为声波频率最大值、最小值，取值为 ，为蝙蝠在次迭代中的飞行速度，为蝙蝠在次迭代中的位置，为全局最佳位置。在全局搜索结束后即得到一个全局最优蝙蝠，而后在此最优个体周围进一步通过局部搜索的方法进行寻优，同时通过式（）进行个体位置的更新：，（）式中：为局部寻优后的最优蝙蝠位置，为局部寻优前的最优蝙蝠位置，为次迭代中的种群平均响度，为 的随机数。蝙蝠觅食是通过声波脉冲实现的，其在飞行中发现存在猎物时会对猎物通过增加声波脉冲频率、减小响度来进行更精确的定位；此时，位置更新如式（）、式（）所示：，（）（），（）式中：为次迭代中蝙蝠的响度，为次迭代中蝙蝠的脉冲发射率，为蝙蝠的初始脉冲发射率，为调节系数。基于黄金正弦算法的 黄金正弦算法黄金正弦算法是一种新型的智能算法，其全局搜索主要是通过函数及单位圆的关系来实现；同时，通过黄金分割数来控制遍历整个空间进而实现对空间中个体的寻优；黄金正弦算法计算较为简单且其具有收敛速度快的优点。其位置更新如式（）式（）所示：（）（），（）（），（），（）式中：、分别为个体在第次和第次迭代中的位置，、分别决定个体移动的位置和方向，、，（槡）为黄金分割数，为蝙蝠个体在次迭代中的最优位置，、为算法搜索优化调节系数。种群平均位置的寻优完全依赖于最优个体的引导，因此如果全局最优个体与实际种群最优个体有着非常大的差异，那么算法会陷入局部最优，所以为了避免中最优个体的引导性错误，需要引入种群平均位置引导算法，进而最大程度避免局部最优问题。其位置更新方式如下：（），（），()，（）信号与信息处理 式中：为次迭代中的种群平均位置。分阶段融合搜索传统的搜索方法通常为全维搜索，该方法局部搜索能力强但是没考虑单维对于适应度可能存在的影响。事实上，如果使用单维搜索会导致算法搜索效率的降低和收敛速度的变慢。鉴于上述问题，综合全维搜索、单维搜索的优劣势，将二者相结合实现搜索互补，具体为每次算法迭代过程的前三分之二使用单维搜索，后三分之一使用全维搜索，其位置更新过程如下：，（）式中：为最大迭代次数，。删除冗余节点通过全局和局部搜索后得到的路径中通常仍存在冗余节点，此时为了进一步减少路径长度和提高路径的平滑度，还需要对这些冗余节点进行删除处理，如图所示。图冗余节点删除操作示意 根据图可知，冗余节点删除之前，路径为，如果将节点、节点连接之后可以避开障碍物，那么路径可行且安全，则节点为冗余节点可以删除。从节点开始，依次将其与后面的节点相连，如果可以连成无障碍直线，那么中间的节点都为冗余节点即都可以删除，如果所有连接直线均无无障碍路径，那么从节点开始继续搜索，如此操作直到路径中的最后一个节点，删除冗余节点后重新计算路径，此时可大大减少路径长度，提高平滑度。融合黄金正弦算法的为规避算法早熟问题，通过引入黄金正弦算法，提出了一种改进的，蝙蝠个体位置更新如下：（）（）。（）图为所提算法的流程。图所提算法流程 具体步骤如下：对算法的运行环境进行构建，同时对规划路径的起点和目标终端进行确定，而后初始化参数，确定问题维度、最大迭代次数、无人机可移动路径数量、初始化参数个体位置、个体速度、声波响度、个体脉冲发射率。根据适应度函数计算种群中所有个体的适应度值，记录最优的路径并保存，通过式（）计算种群的平均位置。通过式（）对种群最优个体位置进行更新，而后通过式（）、式（）更新其他个体信息。生成随机数，如果，那么分阶段以全维、单维相结合的搜索方法对全局最优路径进行进一步局部搜索，得到，如果（）（），那么。生成随机数，如果，且满足条件（）（）（），那么通过式（）、式（）更新响度、脉冲发射率。算法循环迭代，通过不断全局优化路径，不断更新直到算法迭代结束。即如果迭代达到最大迭代次数，那么对最优路径进行删除冗余节点操作，而后输出结果；如果没达到最大迭代次数，那么返回步骤继续迭代。基于改进的覆盖增强策略如上所述，可用来解决二分图的最大匹配问题，提出了基于改进的覆盖增强策略，将传感器节点和蜂窝网格的质心分别视为蝙蝠和猎物，其详细过程如下所述。确定每个节点的最佳蜂窝网格。节点在第次的最佳蜂窝网格的数学表达如式（）所示：信号与信息处理 年 无线电工程 第 卷 第 期 ，。（）如果任一节点的最佳蜂窝网格不存在冲突，则移动任务矩阵计算可表示为：，（）式中：为乘积算子，为移动指标矩阵。若某个节点的最佳蜂窝网格之间存在冲突，则将第次迭代时的冲突网格记录为热蜂窝网格集，并将对应的节点记录为冲突节点。依次将每个冲突节点更新到热蜂窝网格，并返回步骤，直到所有节点都找到不再冲突的最佳蜂窝网格。交换所有节点的移动任务。在完成第步和第步后，可以最小化节点的移动距离，为进一步平衡移动距离，基于蝙蝠的利他行为进行节点交换。其中，和分别为具有和的最佳蜂窝网格，一旦满足式（）所示条件，即可进行移动任务交换。，。（）若多个传感器节点满足的移动任务交换条件，则适应度值计算如下：，（）式中：适应度最小的节点被认为是最佳可交换节点，如图所示。从图中可以看出，和都满足的交换条件，则根据式（）计算可知，适应度值小于。因此，与交换方式一相比，交换方式二能够以更少的移动成本实现更均衡的部署，若没有节点满足交换条件，则移动任务交换结束。图移动任务交换部署结果 实验结果与分析 仿真参数的设置为了对本文算法的有效性进行验证，假设将不同数量的传感器节点随机放置在不同大小的监控区域中，分别进行仿真实验。将所提算法分别与传统、文献算法和文献算法进行对比分析，每个算法运行次，并比较最终平均结果，以避免随机性造成的误差。各算法的仿真参数设置如表所示。表仿真参数设置 参数取值监控区域 感知半径（，）节点数量网格的离散间隔 每步移动距离 鲁棒性分析通过位置更新方程对权重系数进行动态调整，获取最新位置信息。其中，动态权重系数是迭代次数的概率密度函数，当方差较大时，动态权重在迭代开始时较小，并随着迭代次数的增加而增加，从而影响算法平衡全局优化和局部优化的能力。因此，通过取不同方差值进行仿真实验，对所提方法的鲁棒性进行验证。通过次模拟实验，对不同方差的平均性能和标准性能差进行计算，计算结果表明，当方差取不同值时，所提的算法平均覆盖率在以上，最大标准差为 ，且覆盖效率的平均值和标准差的最大差异为 。而关于节点的平均移动距离，平均值的超前差范围为 ，最大标准差为 。正态分布的方差只决定了数据离中心的距离，并不影响概率密度函数的衰减特性。覆盖效率分析为验证所提方法的覆盖效率，对传统、文献算法、文献算法和所提算法的覆盖效率进行了仿真计算，测试了算法在不同节点分布密度时对环境的适应性，并针对网络覆盖率和平均移动距离等指标，设计了组仿真实验，具体情况如下。实验一：根据最优部署定理，当监测区域大小为 时，部署个传感器节点即可实现监测区域全覆盖。因此，在 的监测区域内部署了个传感器节点，传感器的初始位置如图所示。在相同的初始条件下，分别采用传统、文献算法和文献算法和所提算法对进行优化，传感器的实际移动轨迹和种算法的最终覆盖效果如图所示。信号与信息处理 图传感器的初始位置 （）传统（）文献算法（）文献算法（）所提算法图传感器的实际移动轨迹和最终覆盖效果 从图中可以看出，在相同初始条件下，当初始覆盖率为 时，传统、文献算法和文献算法 的 最 终 覆 盖 率 分 别 为、和，而所提方法达到，与初始覆盖率相比提高了，与其他种算法相比分别提高了、和。由此可知，在考虑实际移动距离和最终覆盖效果时，所提算法明显优于传统、文献 算法和文献 算法。图展示了传统、文献算法和文献算法与所提方法的各传感器节点的移动距离仿真结果。由图可知，在考虑节点移动距离时，文献 方法的性能最差，传统和文献 算法略好于文献算法，而本文所提算法明显优于其他种对比方法。图 种算法下各传感器节点移动距离 实验二：将最优部署定理计算的节点数部署到个不同大小的监控区域，其最终覆盖率与移动过程之间的关系如图所示，传感器节点的平均移动距离如图所示。（），信号与信息处理 年 无线电工程 第 卷 第 期（），（），图 种算法的覆盖率 图节点平均移动距离对比 由图可知，随着迭代次数的增加，所提方法的覆盖率急剧增加，然后逐渐趋于稳定并保持。同时，对于种不同的部署环境，所提方法的覆盖率均高于其他种算法。在 的监测区域部署个传感器节点时，所提方法的最终覆盖率达到，而传统、文献算法和文献 算 法 分 别 为、和。由图可知，在种部署环境下，所提方法传感器节点的平均移动距离均小于其他算法。当在 的监测区域部署个传感器节点时，传统、文献 算法和文献 算法的传感器节点平均移动距离分别为 、，而所提方法仅为 。与其他种算法相比，所提算法的节点平均移动距离分别减少了、。因此，基于上述分析可知，在覆盖率和节点平均移动距离方面，所提改进明显优于其他种算法。实验三：考虑部署传感器节点的实际情况，节点数量可能不是最优情况。因此，为测试所提算法的通用性，在不同大小的监控区域内投放不同数量的传感器节点进行实验，实验结果如图所示。信号与信息处理 图节点平均移动距离与节点数的关系 由图可知，文献算法的平均移动距离在个不同的监测区域中是最大的，主要是因为文献算法侧重于优化覆盖率和提高收敛速度，从而忽略了节点的移动距离。同时，当监控区域部署的节点较少时，所提算法的节点平均移动距离大于传统，当监控区域部署的节点较多时，所提算法的节点平均移动距离最小。表为所有情况下得到的最终覆盖率。由表可知，在种不同的部署环境下，如果传感器节点数量增长，那么所有算法的网络覆盖率均逐渐增加，但所提算法的覆盖率始终高于其他种算法，并且当部署的节点较少时，所提算法的覆盖优势更加突出。表不同区域大小和不同节点数量的覆盖效果 监控区域大小传感器数量 初始覆盖 所提方法传统文献 文献 结论为解决中存在的冗余节点、覆盖漏洞等问题，提高网络覆盖率，降低节点平均移动距离，提出了一种基于改进的覆盖增强策略，并通过实验验证得出以下结论：所提方法通过将全维搜索、单维搜索相结合得到的分阶段互补搜索方法，有效提高了算法局部搜索能力，从而使网络覆盖冗余更低，节点分布更均匀。在相同初始条件下，当初始覆盖率为 时，所提方法覆盖率可达到，与初始覆盖率相比提高了。信号与信息处理 年 无线电工程 第 卷 第 期 在不同部署环境下，与传统、文献算法、文献算法相比，所提方法的覆盖率和节点平均移动距离明显优于其他种算法。?参考文献许威，李春国，康嘉文，等 赋能智慧物联网技术与应用专题序言计算机科学，（）：，（）：，：田昕，魏国亮，王甘楠无线传感器网络定位综述信息与控制，（）：孙晓杰，田琳多址接入无线传感器网络覆盖控制算法研究计算机仿真，（）：宋娜，冯梦清 中基于改进粒子群算法的覆盖漏洞检测计算机应用与软件，（）：刘俊，金世尧，陈未如基于 的无线传感器网络节点部署研究无线电工程，（）：，（）：杨怡光无线传感器网络中最大集合覆盖的最优解计算机应用研究，（）：，：，：王振东，汪嘉宝，李大海一种增强型麻雀搜索算法的无线传感器网络覆盖优化研究传感技术学报，（）：，（）：徐钦帅，何庆，魏康园改进蚁狮算法的无线传感器网络覆盖优化传感技术学报，（）：，（）：王毅，神显豪，唐超尘，等基于水波优化算法的无线传感器网络覆盖研究南京理工大学学报，（）：张浩，龙道银，覃涛，等改进人工蜂群算法的覆盖连通优化计算机工程与设计，（）：李思成，魏云冰，邱永露自主多决策粒子群的无线传感器网络覆盖优化仪表技术与传感器，（）：神显豪，马雪皎，牛少华，等基于改进狮群算法的管道传感器网络覆盖优化传感技术学报，（）：作者简介罗卢洋男，（），硕士，高级工程师。主要研究方向：计算机网络应用与传感器技术。王传男，（），正高级工程师。主要研究方向：传感器技术与应用。信号与信息处理