基于自适应非线性因子杂草算法的WSN覆盖优化_付波.pdf

第 卷第期湖北工业大学学报 年 月 收稿日期 基金项目湖北省自然科学基金项目（）第一作者付波（），男，湖北武汉人，工学博士，湖北工业大学教授，研究方向为图像识别与能源优化 通信作者黄晓啸（），男，湖北恩施人，湖北工业大学硕士研究生，研究方向为电气工程 文章编号 （）基于自适应非线性因子杂草算法的 覆盖优化付波，黄晓啸，赵熙临，权轶，贺章擎（湖北工业大学电气与电子工程学院，湖北 武汉 ）摘要无线传感器网络（）的覆盖率与区域内的传感器节点分布密切关联，而现有传感器分布算法存在收敛速度慢、易陷入局部极值等问题。对此，提出了一种基于自适应非线性因子杂草算法（）的传感器节点分布优化方法。首先，在初始阶段，利用 序列产生偏差很小的初始点，使种群分布更均匀；其次，在种群扩散阶段，将非线性调和因子设置为根据迭代次数自适应产生，以调整搜索步长，解决算法易陷入局部最优的问题。最后，通过组标准函数测试与 覆盖优化仿真对该算法进行验证。仿真实验表明：相比于标准杂草算法，改进后的算法具有收敛速度快、覆盖率高的优点，能有效解决 覆盖优化问题。关键词 覆盖率；杂草算法；节点分布；序列；非线性调和因子 中图分类号 ；文献标识码随着科技的不断进步，无线传感器网络（）的应用范围日趋广泛，尤其在电气、航空、商业、工农业生产、医疗健康等领域有着广泛的应用。是一种分布式传感网络，其末梢是可以感知和检查外部世界的传感器，传感器节点的覆盖率决定 的工作效率。近年来，将智能算法应用于 覆盖优化问题得到了广泛关注。文献 提出改进灰狼算法优化 神经网络的无线传感器网络数据融合算法，提高了无线传感器的数据融合精度；文献 针对无线传感器节点能源有限导致负载不均衡，提出一种改进萤火虫算法优化模糊 均值的无线传感器网络路由算法；文献 将改进的麻雀搜索算法应用于无线传感器节点定位，取得了很好的效果；文献提出改进遗传算法解决了无线传感器网络节点修复不确定性问题。但这些应用于 覆盖问题的群智能算法由于本身存在缺陷，导致优化结果不是很理想。杂草优化 算 法（，）由 和 于 年提出，是一种启发式搜索算法，由于 算法简单、易于并行实现，具有全局和局部搜索能力，目前已经广泛应用于许多自然科学与工程领域，如电力市场的纳什均衡问题、电价预估、神经网络、鲁棒控制器参数整定等。同时，针对 的收敛速度和寻优策略，涌现许多改进杂草算法。范宏等利用柯西分布对算法进行空间扩散，在计算初始产生更多可行解；顿晓晗等 将杂草个体以正态分布改为混合种群多种分布产生子代个体，提高了寻优精度；张华强等 将杂草算法与粒子群算法进行结合，改善了算法跳出局部最优的能力；王子豪等 改变了传统杂草算法的适应度计算方式，提高了算法的收敛速度。为进一步提高杂草算法的收敛速度和寻优精度，作者提出了一种基于 序列初始化、根据迭代次数自适应产生非线性调和因子的改进杂草算法，仿真实验表明：本文算法不仅有更快的收敛速度，还能跳出局部极值，搜索到质量更好的最优解，能有效提高 覆盖率。覆盖优化模型假设覆盖区域为二维平面，将离散成的网格，每个网格的面积设置为，中分布着属性相同且位置不变的个传感器节点。每个节点同时具有通信半径和感知半径，且。所有传感器节点可以看成是，的集合，（，），（，），（，）为目标点的位置，则节点到目标点的距离如式（）所示：（）（）（）中传感器节点覆盖概率分布为：（，），（）式中：（）为节点的有效测量半径，、为传感器的自身参数，、为输入参数，用公式（）和公式（）定义：（）（）多个传感器共同作用的 感知概率：（）（，）（）式中：为传感器节点集合。的覆盖率为所有节点覆盖面积与总面积的比值，用公式（）表示：（）（）杂草算法（）杂草算法主要步骤如下：）种群初始化。由下式随机产生杂草：（）（，）（）其中，（，），且，为问题的维度，为种群数量，和 分别为的极大值和极小值。）生长繁殖：杂草按照式（）产生种子：（）（）式中，为杂草适应度值，为杂草个体生成的种子数。子代种子数目与适应度值呈线性关系，计算过程如图所示。图杂草繁殖种子的向下取整线性曲线）扩散阶段：在 算法中，种子按照平均值为，标准差为的正态分布，的变化公式如下：（）（）（）（）其中，为迭代次数，为标准差，为非线性调和因子，或。）竞争生存阶段：在种群扩散过程中，如果种群数量达到预设最大种群规模，则按照适应度值高低对杂草和种子进行排序，选取适应度好的前 数目个体，淘汰其余个体（图）。图竞争生存阶段示意图）停止准测：重复步骤）到），记录每一代种群中适应度最好的个体，到最大迭代次数为止，得到种群的最优解。改进的杂草算法（）基于 序列的种群初始化 算法在初始阶段会随机生成初始点，初始点分布不均匀易导致算法陷入局部极值，因此初始点的分布选择是提升 算法效率的重要环节。低偏差序列能较好地解决分布不均匀的缺陷，提高初始解质量。图、图分别是伪随机序列和低偏差序列的空间分布效果。图伪随机序列图低偏差序列从图可以看出，伪随机序列分布的点有聚集和扎堆现象，这种初始点极易让算法陷入局部极值。而低偏差序列的点在空间内呈现均匀分布，因此具有更好的寻优能力。序列属于低偏差序列的一种，由于其定义简单且能生成无穷个样本点，因此被广泛应用。它是一种为数值方法（如蒙特卡洛模拟算法）产生顶点的系列生成算法。虽然这些序列是以确定的方法算出来的，但它们的偏差很小，所以，这些点可以看成是空间内随机分布的点。利用非线性因子调整搜索步长杂草 种 子 按照 式（）分 布 在 父代周围，基本 算法中的非线性因子是一个定值，极大限制了杂草个体的全局寻优能力。将非线性因子设置成根据迭代次数自适应变化，使得迭代前期算法的标准差较大，种子分布在离父代较远的位置，迭代后期算法标准差变小，种子分布在离父代较近的位置，从而实现算法从全局到局部的搜索，避免早熟。非线性因子的变化如式（）：湖北工业大学学报 年第期 .，.（）式中：表示当前迭代次数，为最大迭代次数。算法步骤见图。图算法流程仿真实验与分析为验证本文 算法在 覆盖优化研究中的优势，选用 个国际通用 函数 进行了测试，并选择基本粒子群算法（）、基本杂草算法（）、本文算法（）进行对比分析。本次仿真实验所使用环境为：系 列，内 存 为 ，操 作 系 统 为 ，编程环境 。设置检测区域为 的二维平面，传感器覆盖节点数为 个，节点通信半径为，感知半径为。用 算法、算法、算法分别对这些节点在区域内进行覆盖优化，三种算法同时迭代 次，重复操作 次，记录下每次迭代得到的最优解。各算法参数：（，），（，），（，）。算法覆盖率对比用以上三种算法对 覆盖优化仿真。首先，仅用 序列对杂草算法进行改进，结果见表第二列，可以看出，相比于另外两种优化算法，算法对 的平均覆盖率大大提高了，比 算法高出大约，比 算法高出大约。其次，仅用非线性因子对杂草算法进行改进，见表第三列，可以看出，算法的覆盖率比 算法高出，比 算法高出。最后，用 序列和非线性因子同时改进杂草算法，见表第四列，可以看出，算法的覆盖率比 算 法 高 出 ，比 算 法 高 出 。综上所述，相比于 算法和 算法，经过 序列和非线性因子改进后的 算法能有效地提高 的覆盖率，体现了该算法的有效性。表用不同方法改进后 覆盖率算法序列 序列 另外，三种算法的传感器最终分布如图所示，不难看出，算法和 算法的传感器分布较杂乱，导致覆盖率低下；算法引入了 序列，使得传感器分布更加均匀，从而使覆盖率大大提高。图最终分布不同节点数对比试验传感器节点个数不同，对 覆盖率也会有影响。本文记录了传感器节点数为、个时各算法的覆盖率（表）。表不同节点下的覆盖率算法 覆盖率节点数 节点数 节点数 随着传感器节点数的增加，各算法的覆盖率均有提高，且 算法的覆盖率均高于 算法和 算法。另外分析各算法达到最大覆盖率时的迭代次数可知，达到最大覆盖率时的迭代次数为 次左右，而 和 在迭代 次以后才达到覆盖率最大，这表明 算法的收敛速度更快。种算法的 覆盖率随迭代次数的变化曲线见图。可见，和 分别在 次和 次时才开始收敛，而 的曲线在 次时就开始收敛，收敛速度明显更快，第 卷第期付波，等基于自适应非线性因子杂草算法的 覆盖优化加强了寻优精度。图节点数为 时的覆盖率图节点数为 时的覆盖率图节点数为 时的覆盖率算法的优越性对比选用 个 标 准 函 数 分 别 测 试 、和（表），最终结果以最大值为最优。从表中可以看出，算法得出的函数值均优于前两种算法，说明 算法得到的解质量更高，寻优精度更好。表标准函数测试结果测试函数算法对比 结束语本文针对无线传感器网络节点分布不均匀导致的覆盖率低下的问题，提出了一种基于非线性因子的改进杂草算法（），该算法在种群初始化阶段引入了一种 序列，使得初始种群分布更加均匀，提高算法全局寻优的能力；在种群扩散阶段，引入自适应非线性调和因子，使得前期种群的标准差更大，防止算法陷入局部最优。并将改进的杂草算法应用于 覆盖优化中。从仿真结果可以看出，相比于粒子群算法和杂草算法，算法能增强杂草在空间的搜索速度，提高求解精度，从而有利于提升 的覆盖率。参考文献 ，：曹轲，谭冲，刘洪，等 基于改进灰狼算法优化 神经网络的无线传感器网络数据融合算法 中国科学院大学学报，（）：余修武，秦晓坤，刘永 基于萤火虫算法优化 的 路由算 法 北 京 邮 电 大 学 学 报（自 科 版），（）：彭铎，杨雅文，高玉蔚，等基于多通信半径和麻雀搜索的节点定位算法传感技术学报，（）：苟平章，孙现超，毛刚基于改进遗传算法的覆盖空洞修复优化传感技术学报，（）：，：，：，（）：，：，：，（）：顿晓晗，周建中，曾小凡基于改进杂草算法优化的神经网络模 型 在 径 流 预 报 中 的 应 用 水 电 能 源 科 学，（）：张华强，陈传训，吕云飞，等 算法在甲烷检测中的应用中国环境科学，（）：王子豪，马俊涛，鲁军，等基于改进杂草入侵算法的阵元失效校正方法 计算机仿真，（）：艾哈迈迪，莫贾拉利混沌入侵杂草优化算法及其在混沌系统参数估计中的应用 ，（）：（下转第 页）湖北工业大学学报 年第期识别实验，网球整体识别正确率达到，表明基于颜色和网球区域特征的识别算法可以在不同场景较为精准地实现网球识别。参考文献侯宾，张文志，戴源成，等 基于 的目标物体颜色及轮 廓 的 识 别 方 法 现 代 电 子 技 术，（）：张志宝，孙微涛，罗文峰基于 空间改进的彩色图像边缘 检 测 方 法 计 算 机 与 数 字 工 程，（）：席小刚，孙浩，钟方伟，等 基于 模型和最大隶属度图像分割算法的研究 电视技术，（）：汤慧 多颜色空间融合的颜色特征提取方法及应用 长沙：中南大学，（，.，）：，：；责任编校：张众（上接第 页），（，.，）：（），（），；，：；责任编校：张岩芳湖北工业大学学报 年第期