基于改进萤火虫算法的覆盖优化方法∗

苟平章孙现超

(西北师范大学计算机科学与工程学院，甘肃 兰州 730070)

无线传感器网络(Wireless Sensor Networks，WSNs)是由大量的传感器节点通过多跳和自组织成的无线网络。 随着嵌入式技术和无线通信技术的发展，WSNs 已被广泛应用于军事，工业和农业控制，生物医学，环境测试，救灾等领域[1]。 同时，合理的节点部署不仅可以提高网络数据传输效率和网络资源利用率，还可以根据实际应用需求动态的调整网络状况，因此，节点部署与覆盖问题是WSNs 的主要研究方向[2]。 由于传感器节点通常部署在战场或沙漠等偏远或敌对环境中，只能通过飞机投掷等随机方式进行部署，风和障碍物会影响节点的实际着陆位置，导致目标区域出现覆盖空洞[3]。 如果仅部署静态传感器节点，即使在目标区域部署大量冗余节点，覆盖质量也无法保证，而且还会造成节点浪费。 如果仅部署移动传感器节点，成本会很高。

针对上述存在的问题，可以在目标区域内同时部署静态传感器节点和移动传感器节点。 移动传感器节点能够在部署后可以移动到指定的位置，从而提高网络覆盖率，满足网络的覆盖要求。 近年来，越来越多的学者研究节点部署问题。 文献[4]提出利用Voronoi 图对网络中随机布置的传感器节点进行部署，该算法减少了冗余并去除了孤立节点，保持网络连通性。 该算法将区域划分为不同的Voronoi 单元，并部署所需的节点，从而根据Voronoi 划分将节点移动到它们的最佳位置，提高网络覆盖率。 文献[5]提出一种具有无参数配置的异构无线传感器节点部署算法，利用Delaunay 三角剖分方法查找出最大的覆盖空洞，采用eVForce 方法避开障碍物进行节点的部署，该算法的性能优于随机部署和传统的Delaunay 三角网部署，并提高了异构无线传感器网络的覆盖范围和网络生命周期。 文献[6]利用改进正弦余弦算法进行节点部署优化，利用该算法部署的节点覆盖率优于改进粒子群优化算法和改进灰狼优化算法，有效提高了网络节点覆盖率。 文献[7]提出一种基于外推人工蜂群算法的节点部署优化方法，利用该算法代入模型进行求解，获得覆盖最优的节点部署位置，覆盖率得到了一定的提高。 文献[8] 提出一种基于改进的自适应粒子群优化(Particle Swarm Optimization，PSO)算法的覆盖优化方法，克服了粒子群优化算法在优化后期容易陷入局部最优的弱点，提高了网络覆盖率。 文献[9]提出自适应混沌量子粒子群算法的移动传感器网络覆盖优化算法，弥补标准粒子群、量子粒子群的不足，覆盖性能得到提高。 文献[10]提出一种改进蚁狮算法(Mixed Strategy based Ant Lion Optimizer，MSALO)的网络覆盖优化方法，结合早熟收敛判断机制与动态混合变异方法，使算法能够有效跳出局部最优。 文献[11]提出基于改进鲸鱼优化算法的WSNs覆盖优化策略，该策略解决了随机部署移动节点时分布不均匀导致覆盖率低的问题，减少了传感器节点冗余。 文献[12] 提出一种基于布谷鸟搜索(Cuckoo Search，CS)的覆盖优化策略，与粒子群优化算法相比，减少了移动节点的数量，提高了目标区域覆盖率。 文献[13]提出一种多因素协同空洞修补优化算法，该算法考虑了虚拟修复节点与移动节点之间的距离、移动修复过程中的能耗以及待修复节点的可信度，建立虚拟修复节点和移动节点之间的皮尔逊模糊匹配关系来修复空洞，从而提高网络覆盖率。 文献[14]提出一种改进差分进化算法(Improved Differential Evolution Algorithm，IDEA)的网络节点部署优化策略，使用节点的有效覆盖率作为优化因子构造目标函数优化模型，采用混沌反向学习初始化策略，加快收敛速度、提升节点的网络覆盖率。

综合以上研究，利用启发式算法的逐步寻优特性，本文提出一种基于改进萤火虫算法的覆盖优化方法。 该方法通过在监测区域内随机部署静态节点和移动节点，对位置公式进行改进，加入权重函数，提高全局搜索能力，防止陷入局部最优；对步长因子进行改进，加快算法收敛速度。 通过改进萤火虫算法(Improved Firefly Algorithm，IFA)初步确定移动传感器节点的候选目标位置，利用目标位置优化方法确定传感器节点最佳位置，从而完成覆盖优化，同时减少节点移动距离，达到节省节点能量，延长网络生命周期的目的。

1 系统模型与术语定义

1.1 网络模型

本文的网络模型假设如下:

假设1 在无线传感器网络目标区域内部署N个传感器节点，其中包括Nm个移动传感器节点，Nn个静态传感器节点。 传感器节点集合定义为:

假设2 网络中每个传感器节点都可以通过GPS或某些位置服务知道其位置信息。

假设3 所有传感器节点具有相同的感知范围Rs和通信范围Rc，并且Rc＝2Rs。

假设4 目标区域内的移动传感器节点具有充足能量，确保其能够移动到指定位置。

1.2 能量模型

为使数据能被有效发送，采用文献[15]提出的能耗模型进行能量消耗计算，根据节点传输距离，节点部分能量在数据传输过程中进行信号放大。 节点在链路上传输kbit 数据的能耗可表示为:

式中:dmax表示该移动节点可移动最大距离，Eres为移动节点剩余能量。

1.3 感知模型

假设监测区域A是L×L的正方形区域，为方便计算和比较各算法的覆盖性能，将监测区域A网格化，分为l×l个像素点，以像素点是否在节点Si的感知半径范围内表示覆盖程度。 若像素点Hj(j＝1，2，3，…，l×l)的坐标为(xi，yi)，则Si和Hj的之间的距离可表示为:

1.4 术语定义

定义1(区域覆盖率) 区域覆盖率表示所有传感器节点感知区域的并集与目标区域总面积的比值，定义为Rarea(S):

式中:ad(S)表示传感器节点的平均移动距离，Rarea(S)为区域覆盖率。

2 覆盖优化方法

针对在目标区域内仅仅部署静态传感器节点和移动传感器节点存在的问题，本文提出一种基于改进萤火虫算法的覆盖优化方法。 该方法分为两个步骤:①对位置公式和步长因子进行改进，提高了全局搜索能力，加快算法收敛。 利用IFA 算法初步确定移动传感器节点的候选目标位置。 ②通过目标位置优化方法对第一步骤获取到的候选目标位置进行优化，从而确定移动传感器节点的最佳目标位置。 算法流程如图1 所示。

图1 IFA 算法覆盖优化流程图

2.1 IFA 覆盖优化方法

FA 算法最早由文献[16]提出，是一种模仿自然界萤火虫捕食、求偶行为的新型群体智能优化算法。 FA 算法需要的参数较少，思想比较简单且优化性能好，FA 算法在WSNs 中[17]得到广泛应用。 但也存在易陷入局部最优、算法过早收敛等问题[18]，因此本文对FA 算法进行改进，将IFA 算法应用到WSNs 覆盖优化中，利用IFA 算法初步确定移动传感器节点的候选目标位置。

FA 算法中，每个萤火虫的位置代表了一个待求问题的可行解，而萤火虫的亮度表示该萤火虫位置的适应度，亮度越高的萤火虫个体在解空间内的位置越好。 萤火虫个体之间，高亮度的萤火虫会吸引低亮度的萤火虫。 FA 算法有以下三个基本假设:①所有萤火虫无性别之分，每一只萤火虫只会被比其更亮的萤火虫所吸引。 ②萤火虫之间的吸引力与他们的亮度成正比，对于任意两个萤火虫，亮度低的萤火虫向亮度高的萤火虫移动，越靠近亮度越强，吸引力越大，即吸引力与亮度成正比。 而亮度随距离的增加而变弱，则吸引力与距离成反比。 ③萤火虫的亮度在算法里是根据待优化的目标函数值所决定的，目标函数值越好，证明其荧光亮度越高。

定义1 萤火虫的相对荧光亮度。式中:x′i表示一个比第i个亮度更高的萤火虫位置，rij的定义如同定义(1)，xi，xj分别代表萤火虫i，j在空间中所处的位置。 rand 是服从均匀高斯分布的随机数，α为步长因子。

2.1.1 IFA 算法

标准FA 算法在迭代后期，由于萤火虫已经逐渐移动至局部或者全局极值点附近，此时萤火虫之间的距离逐渐缩小，根据位置更新公式(11)可以得到:萤火虫之间的吸引度逐渐增大，将会使萤火虫个体的移动距离过大而无法到达或者错过最优位置，造成在极值点附近震荡的问题。 本文在标准FA 算法的基础上，引入了权重函数，此时位置更新公式变为:

式中:ωmax，ωmin分别为最大、 最小权重；t，MaxGeneration 分别为当前和最大迭代次数。

通过权重函数可以控制萤火虫以前位置信息对当前位置的影响，权重的大小决定萤火虫移动距离的大小，并提高了萤火虫算法的全局寻优和局部搜索能力。 当权值取值较大时，萤火虫当前的位置会对下一步要移动的位置有较大的影响，萤火虫间的吸引度影响相对较小，全局寻优能力增强，局部搜索能力相对减弱。 反之，萤火虫当前的位置会对下一步要移动的位置影响较小，萤火虫间的吸引度影响相对较大，全局寻优能力减弱，局部搜索能力相对增强。 因此通过调整权重函数w(t)的取值，可以使萤火虫算法在搜索前期具有较强的全局搜索能力，有助于加快全局的收敛速度，随着迭代次数的增加，权重逐渐减小，到搜索后期，局部搜索能力增强。

从萤火虫之间的吸引度公式(11)中不难发现，当两个萤火虫之间的距离很大时(rij→∞)此时吸引度β≈0，则萤火虫i进行的位置公式(11)就会近似式(14)的形式:

式中:t代表算法的当前迭代次数，a为步长因子，rand 是服从高斯分布的随机数。

从式(14)中可以看出，此时萤火虫i的位置更新与其他亮度更高的萤火虫无关。 因此在算法运行前期萤火虫种群过于分散导致有些萤火虫之间的距离过大时即(rij→∞)，这时如果步长因子α的取值过小，则处于劣势位置的萤火虫i就会按照近似公式(14)进行位置更新，而不能被处于更好位置的萤火虫j吸引，只能在自己位置周边完成局部搜索，降低了全局寻优能力。

当两个萤火虫之间的距离趋于0 时(rij→0)，吸引度β≈β0(β0一般为常数1)，此时位置移动公式(11)也会近似于式(14)的形式。 因此在算法运行后期，萤火虫间的距离即将收敛到最小时(rij→0)，且α取值过大，处于劣势位置的萤火虫i就会远离处于更好位置的萤火虫j，这样就会容易使算法产生震荡现象降低了收敛速度。

综上所述，发现步长因子α的取值在平衡全局寻优和提高收敛速度上有着至关重要的作用。 因此本文不再取固定不变的α值，而是在迭代过程中对α的值进行了动态调整。 在算法运行初期，α的值较大，有利于全局寻优；而随着迭代次数的增加，α的值逐渐减少，可以提高算法收敛速度。 步长因子α的动态调整过程如式(15)所示:

式中:upper，low 分别为搜索范围上下限。

从式(15)中可以看出，α的取值是随着迭代次数递减的，因此在算法运行初期时，α的取值较大，可以避免由于萤火虫之间距离过大只能在自己周围局部搜索的情况，提高了全局寻优能力；在算法运行后期时，α的取值会变得较小，避免了算法产生震荡的现象，有利于提高算法收敛速度。

2.1.2 基于IFA 算法的覆盖优化

通过对FA 算法进行改进，防止陷入局部最优，加快搜索速度。 将改进的萤火虫算法应用到WSNs覆盖优化中，利用IFA 算法求解出移动传感器节点的候选目标位置。 该算法利用萤火虫之间的吸引力，以节点间的剩余能量和节点间的距离作为吸引力，确定移动节点的候选位置，提高网络覆盖率。 具体算法步骤如下:

Step 1 对最大迭代次数、种群数目、最大吸引度、光吸收系数等相关必要参数进行初始化；

Step 2 在目标区域内随机抛洒传感器节点，并将每个传感器节点看成一个萤火虫，从而形成萤火虫群；

Step 3 根据待优化的目标函数计算每一个传感器节点位置的适应度值并作为其绝对荧光亮度；

Step 4 每两个传感器节点进行相互比较，适应度值小的传感器节点则按照位置公式(12)进行位置更新；

Step 5 检查算法是否达到最大迭代次数，如果未达到则返回步骤3，达到则输出该迭代次数条件下最优解。

通过对FA 算法进行改进，提高其全局搜索能力，加快收敛速度。 当问题维度为D，外层迭代次数为G，标准FA 算法的时间复杂度为O(n2×G)。 本文在标准的FA 算法的基础上，对位置公式和步长因子进行改进，本文算法的时间复杂度为O[G(n×D＋n)]＝O[G(n×D)]。 因此，本文算法比标准的FA算法大大减少了时间复杂度。 利用IFA 算法初步确定移动传感器节点的位置，将基于IFA 算法的覆盖优化得到的最优解作为目标位置优化方法的输入，进一步完成覆盖优化。

2.2 目标位置优化方法

目标位置优化方法以能量优先为原则，在不减少网络覆盖率的前提下，通过减少移动传感器节点的移动距离，从而降低节点移动能量消耗，延长网络生命周期。 该方法从移动距离优化、能量优先、移动节点目标位置交换3 个方面对候选目标位置进行优化。

具体方案描述如下:

①移动距离优化。 利用IFA 算法获取到移动传感器节点的候选目标位置后，移动传感器节点将移到此位置进行覆盖优化。 如图2 所示，当传感器节点Si从P0移动到P2时，区域覆盖率Rarea(S)没有提高。 在这种情况下，覆盖质量并没有得到有效改善，此时将取消移动传感器节点Si的移动。 通过移动距离优化方法，可以减少传感器节点总的移动距离，并且节省节点能量，延长网络生命周期。

图2 移动距离优化

②能量优先原则。 假设Si的能量大于Sj的能量，d1和d2相等。 在满足约束条件1，移动节点移动距离不超过其最远移动距离dmax的前提下，假设移动传感器节点Si、Sj分别从P0和P1移动P2的位置皆可完成覆盖优化，且2 个传感器节点移动到候选目标位置后网络覆盖范围不变，则优先选择能量高的Si节点进行移动，如图3 所示。 按照能量优先方式进行移动，会延长网络生命周期，提高网络监测效率。

图3 能量优先

③移动节点目标位置交换原则。 如果2 个移动节点移动到候选目标位置后增加相同的覆盖率，那么可以交换这2 个节点的候选目标位置。 如图4(a)所示，当节点S1和S2分别移动到P1和P2后，区域覆盖率Rarea(S)增加程度相同，此时移动传感器节点S1和S2的总移动距离为d1＋d2，若按图4(b)方式交换候选目标位置之后，移动的距离为d3＋d4，显然d3＋d4

图4 位置交换原则

3 仿真实验与分析

3.1 实验环境

为了验证IFA 算法应用于WSNs 覆盖优化的可行性，在MATLAB2018 上进行仿真实验。 假设监测区域为200 m×200 m 的矩形区域，在监测区域内随机部署100 个传感器节点，其中有30 个移动传感器节点，移动传感器节点由空心圆表示。 实验中具体仿真参数如表1 所示。

表1 网络环境和参数设置

3.2 实验结果及分析

3.2.1 移动距离分析

对监测区域为200 m×200 m 矩形区域进行仿真实验，迭代次数设置为300 次。 研究IFA 算法与文献[10]中的MS-ALO 算法，以及文献[9]PSO 算法的平均移动距离与移动节点数量的关系。 将三种算法分别进行300 次独立实验后取平均值，得到如图5 所示的实验结果。 分析图5 可知，三种算法都随着移动节点比例的增加而增加，但IFA 算法的平均移动距离比其他两种算法有明显的优势，同时节省节点能量，延长网络生命周期。

图5 平均移动距离与节点比例的关系

3.2.2 网络覆盖优化分析

将IFA 算法与文献[12]中的CS 算法，以及FA算法作比较，图6 分别为三种算法在相同条件下经过多次实验得到的网络覆盖率与迭代次数的柱状图。 分析图6 可知，三种算法的网络覆盖率都随着迭代次数的增加不断提升。 IFA 算法可以将区域覆盖率从最初的37%优化到94.95%，提高了57.95%，而CS 算法和FA 算法分别提高了54.6%和52.51%。IFA 算法与CS 算法和FA 算法相比，分别提升了3.35%和5.44%，将IFA 算法用于WSNs 覆盖优化中具有更好的覆盖效果；另外，由图6 可知，IFA 算法在迭代次数达到150 次时，可以达到94.95%的覆盖率，而其他两种算法分别在200 次和250 次才达到最优的覆盖效果，因此IFA 算法具有更好的收敛性。

图6 网络覆盖优化迭代柱状图

3.2.3 能耗及结果优化分析

将IFA 算法与文献[9]PSO 算法、文献[12]CS算法、文献[14]IDEA 算法作比较。 图7 分别为四种算法在相同条件下经过多次实验得到的能耗与迭代次数的关系图。 分析图7 可知，四种算法的总能耗都随着迭代次数的增加不断提升，但IFA 算法相比其他三种算法所消耗的能量少。 从仿真结果可知，IFA 算法在迭代250 次以后，网络总能耗还是趋于增加的趋势。 而IDEA 算法和CS 算法在迭代250次后、PSO 算法在迭代200 次后，网络总能耗就不再增加，此时网络已经不能正常工作。 由此可知，将IFA 算法应用于WSNs 覆盖优化中，具有更长的生命周期。

图7 网络总能耗与迭代次数的关系

为验证该方法的可行性，分别对该方法的2 个步骤的优化结果进行仿真实验，结果如图8～图12所示。

图8 为随机部署在目标区域的节点位置分布图，图9～图11 分别为迭代100 次、200 次和IFA 算法优化后的节点位置分布图，图12 为经过目标位置优化后移动传感器节点的最佳位置。 分析图8～图11的变化可知，目标区域的空洞逐渐减少，网络的覆盖率在增加。 从图11 到图12 的变化可知，对候选目标位置进行优化，得到移动传感器节点的最佳位置，覆盖率也进一步得到提高。 减少非必要节点的移动，节省能量。

图8 初始节点位置分布图

图9 迭代100 次节点分布图

图10 迭代200 次节点分布图

图11 IFA 算法优化后节点分布图

图12 目标位置优化

分析实验结果表明，本文利用IFA 算法可以初步确定移动传感器节点的位置，然后再经过目标位置优化方法确定最佳位置是可行的。 通过对图12进行覆盖面积计算，网络覆盖率可以达到94.95%，实现比较好的覆盖优化。 同时使用目标优化方法可以减少节点移动距离，节省节点能量，延长网络生命周期。

4 总结

针对在无线传感器网络监测区域内仅仅部署静态传感器节点和移动传感器节点存在的问题，本文提出一种基于改进萤火虫算法的覆盖空洞优化方法，将静态传感器节点和动态传感器节点随机部署在目标区域内，对位置公式和步长因子进行改进，提高全局寻优能力，加快搜索速度。 通过IFA 算法初步确定移动传感器节点的位置，然后通过目标位置优化方法对初步位置进行优化，最终确定最佳的位置。 仿真实验表明，该方案是可行的，可以很好的确定移动传感器节点的最佳位置，从而完成覆盖优化。