基于萤火虫算法的无线传感器网络节点重部署策略

孙 环，陈宏滨

（桂林电子科技大学信息与通信学院，广西桂林 541004）

（*通信作者电子邮箱chbscut@guet.edu.cn）

0 引言

目前，无线传感器网络（Wireless Sensor Network，WSN）是物联网研究的热点领域之一，通过无线方式进行数据交换，在智能家居、军事勘测、远程医疗、交通等众多领域都取得了一些应用成果［1-2］。同时，在WSN 领域中，节点部署问题是主要研究之一［3-4］。合理的节点部署策略不仅可以提高网络数据传输效率和网络资源利用率，还可以根据实际应用需求的变化改变节点的数目以及状态，动态地调整网络状况。文献［5］中提出了一种基于蚁群优化算法的WSN 节点部署策略，主要针对节点的盲目连接以及网络中盲目地进行负载均衡部署，分别设计了基于组的连接机制和负载均衡部署机制，有效降低了部署成本；但该部署策略没有考虑网络的最大化覆盖问题。文献［6］中提出了一种自然启发式的离散萤火虫算法（Firefly Algorithm，FA），用于WSN 中的最佳移动数据收集，有效减少了移动距离，提高了能源效率。文献［7］中通过使用混合粒子群算法的FA 进行节点部署，实现簇头（Cluster Head，CH）的最佳定位，有效改善了网络生命周期。文献［8］中针对簇头负载不均衡问题，提出了一种非均匀密度WSN 节点的部署方案。该方案使得簇头能保持均匀的能量消耗，从而延长了网络生命周期。文献［9］中针对多种不同类型的需求提出了不同的部署策略：对于确定性和基于网格的部署问题，提出了一种基于成本的部署算法，即节点进行最短距离的连接，最小化移动距离，从而最小化部署成本；此外，针对节点的负载情况，提出了基于网络生命周期的部署算法，在负载过大的节点附近部署额外的节点，提高了网络生存周期，但该算法依赖较多的传感器节点。

文献［10］中利用改进正弦余弦算法进行节点部署优化，实验结果表明利用该算法部署的节点覆盖率优于改进粒子群优化算法和改进灰狼优算法，有效提高了网络节点覆盖率。文献［11］中提出了一种自适应节点部署算法，利用最少的传感器节点数目达到最大化网络覆盖范围目标，同时减小了节点的总移动距离。文献［12］中通过研究传感器节点数量对部署的影响，提出了一种实现覆盖最大化的部署方案；但该方案只是单一地进行传感器数量的研究，没有考虑整个网络的能耗均衡。文献［13］中研究了一种具有无参数配置的异构无线传感器节点部署算法。该算法分为两个部分：首先利用Delaunay 三角剖分方法查找出最大的覆盖空洞；然后，采用eVForce方法避开障碍物进行节点的部署。仿真结果表明，该算法的性能优于随机部署和传统的Delaunay 三角网部署，并提高了节点异构传感器网络的覆盖范围和网络生命周期。文献［14］中提出了一种基于改进FA 的移动无线传感器网络覆盖优化方案，通过快速地移动最密集区域节点的方式，使得WSN 在最短时间内达到最大覆盖范围，从而扩大了网络范围，获取了更好的无线传感器网络分布；节点的能耗均衡问题在传感器节点的部署过程中很重要，它决定了网络的运行状况，但在上述研究中并未考虑。

文献［15］中提出了一种中继节点能量感知部署方案，研究了能源丰富和能源有限两类节点的部署，通过考虑节点的能源情况，移动中继节点；该部署方案确保了可持续的覆盖，延长了网络的生命周期，但是移动节点的能耗比较大。文献［16］中利用FA来确定传感器的最佳位置，最小化传感器网络的目标覆盖和网络连接时间。文献［17］中提出了一种混沌FA 的无线传感器网络节点分布优化策略，有效地实现了网络节点的优化部署，并且具有优化效果好、稳定性好、鲁棒性强的优点。文献［18］中提出了一种基于节点能耗均衡的分区域节点重部署算法，利用虚拟力对不同区域的节点进行移动，降低移动能耗；但在节点分布过密或过疏的初始情况下，节点移动数目多且频繁，距离汇聚节点较近的节点能耗较大，缩短了网络生命周期。

针对上述研究中的能量空洞问题，本文综合考虑网络负载和节点能耗，提出了一种基于FA的无线传感器网络节点重部署（Node Redeployment Based on FA，NRBFA）策略。首先，建立一种节点非均匀部署的网络模型，将节点随机分布在网络中，利用k-means 算法［19］对节点进行分簇，在满足覆盖要求的情况下，筛选出冗余节点，使其进入休眠状态（此时冗余节点不进行感知和发送数据）；然后，当无线传感器网络运行一段时间后，由于簇头承担着大量的数据融合和传输任务，导致簇头的能量快速消耗，当其剩余能量消耗达到一定阈值时，即小于网络中存活的非冗余节点的剩余能量平均值的2/5时，不再进行数据传输，此时唤醒冗余节点，利用FA 移动冗余节点对网络节点进行重部署。换句话说，就是将节点的剩余能量和节点间的欧氏距离作为两个吸引力，通过计算选出吸引力最大的节点，即最佳冗余节点，去替换簇头，成为新的簇头，再进行数据传输。同时，原簇头也通过FA 寻找目标节点，即具有最大吸引力的普通节点（Normal Node，NN），然后移动到该目标节点附近，替代目标节点。最后，目标节点成为新的冗余节点（Redundant Node，RN），更新冗余节点。该部署策略最大限度地使节点能耗均衡，延长无线传感器网络的生命周期。本文的主要工作如下：

1）本文考虑了无线传感器网络中用于数据收集的能量空洞问题，其中，传感器节点传输的数据量不一致，充分利用无线传感器网络中的冗余节点。

2）为解决能量空洞问题，本文设计了一种基于FA的节点重部署策略。该策略旨在有效地移动冗余节点以进行节点重部署，而且该算法的复杂度较低。

3）通过仿真实验验证了本文NRBFA 策略能有效地缓解能量空洞问题，均衡网络能耗，延长无线传感器网络的生命周期。

1 系统模型

1.1 无线传感器网络模型

如图1 所示，无线传感器网络模型主要由汇聚节点、簇头、普通节点和冗余节点组成。其中，汇聚节点负责从簇头收集数据；普通节点感知数据，然后将数据传输给该簇相应的簇头；簇头节点负责收集、融合、转发簇内所有普通节点的数据；冗余节点负责替换簇头，并且初始时处于休眠状态。网络执行过程以网络工作轮数的形式进行，每一轮都包含数据的通信阶段。

图1 无线传感器网络模型Fig.1 Wireless sensor network model

无线传感器网络节点部署的过程如下：首先，在边长为L的正方形监测区域内，随机部署N个传感器节点，利用k-means 算法对所有传感器节点进行分簇；然后，普通节点将感知数据传输到簇内簇头，簇头将簇内所有节点的数据进行融合，并将融合后的数据传输到汇聚节点；最后，当有簇头的剩余能量达到设定的阈值时，冗余节点移动替换簇头。

受文献［11］和文献［20］的启发，为了更好地实现本文研究目标，本文中的节点位置信息都可以通过特殊方式获得。因为本文将汇聚节点设置在监测区域中心位置，若选择多跳通信方式，则距离汇聚节点近的簇头会加快能量消耗速度，节点的可移动性有利于节点初始部署后的重部署。具体的假设如下：

1）每个节点都能通过全球定位系统（Global Positioning System，GPS）或其他一些特殊定位算法［20-21］知道自己的位置，相邻节点间可以互相通信，每个传感器节点有其唯一身份标识号（Identity Document，ID）和相同的初始能量。

2）所有簇头都以单跳方式向汇聚节点发送数据，簇内普通节点也以单跳方式向自己的簇头传输数据。

3）整个网络中的节点在初始部署后都是可移动的，并且簇与簇之间不存在信息的传递。

1.2 节点关系模型

在一个边长为L的正方形内随机部署N个无线传感器节点，定义为T={T1，T2，…，TN}，其中节点Ti的位置坐标为(xi，yi)(i=1，2，…，N)，且每个节点具有相同的性能。本文为了寻找冗余节点，假设节点的感知半径为RS，节点的检测半径为r，且RS＞r。在节点Ti的检测半径内，假设存在一个冗余节点Tj，它的位置坐标为(xj，yj)，则两节点之间的欧氏距离dij的计算公式如式（1）所示：

则可以得到传感器节点Ti感知到冗余节点Tj存在的感知概率P(i，j)为：

当冗余节点Tj在传感器节点Ti的感知范围内时，感知到的概率为1；反之，感知到的概率为0。

1.3 能量消耗模型

能量消耗在无线传感器网络中占重要地位，主要体现在数据通信阶段，本文采用的能量消耗模型如下：

1）普通节点能耗。

假设节点间的通信距离为d，采用不同的能耗模式，节点i发送hbit 数据至节点j的能量损耗ET(h，d)的计算公式如式（2）所示：

节点接收hbit 数据的能量消耗ER(h)的计算公式如（3）所示：

其中：d0为距离阈值；Eelec是发送/接收1 bit 数据的能量消耗。εfs表示当d≤d0时，自由空间中发送电路的放大系数，其值设为12 pJ/（bit·m-2）；εamp表示当d＞d0时，多径信道中发送电路的放大系数，其值设为0.001 2 pJ/（bit·m-2）；节点在感知过程中消耗的能量忽略不计。

2）簇头节点能耗。

簇头（CH）的能耗ECH主要由三部分组成：接收数据能耗Er、融合数据能耗Ef和发送数据能耗Es。根据文献［22］中设定的簇头数据融合率并结合本文无线传感器网络模型，进行大量实验后，有以下规定：

1）簇头的融合率rf为0.8；

2）当簇头接收h0bit数据的能耗Er表示为h0Eelec；

3）融合本簇内h0bit数据的能耗Ef表示为h0ef，其中，ef为融合1 bit数据能耗；

4）发送h0bit 数据到距离为dCH⁃BS的基站的能耗Es计算公式如式（4）所示：

因此，在本簇内CHi（簇头i）的能耗ECHi公式如式（5）所示：

3）冗余节点能耗。

节点移动的能量损耗Emove为：

其中：e为单位距离内节点移动的能耗，其值为5× 10-5J/m；dx为节点移动距离。

2 问题描述

本章描述传感器网络中节点重部署的原因。首先，给出以下定义：

定义1生命周期。当网络中死亡节点数目达到网络节点总数目的10%时，表示该网络生命周期结束。

定义2死亡率。网络中死亡节点数目与节点数目N的比值。

定义3冗余节点的集合R：R=｛R1，R2，…，Rx｝，且R∈T。

在无线传感器网络中，由于节点能量有限且难以进行补充或替换、多对一通信等特点，容易产生能量空洞现象，导致节点能量消耗不均衡。在无线传感器网络初始部署阶段，大量的传感器节点在初始阶段被随机部署在监测区域，不可避免地会产生重叠区域，从而会造成能量的浪费而且产生大量冗余数据，占用有限的网络带宽。随着网络的运行，簇头不断收集数据，能量消耗过快，将无法承担数据接收和转发的任务，网络将停止运行，严重影响了网络的生命周期。因此，如何通过节点重部署来均衡节点能耗，以最大限度地延长网络生命周期是一个值得研究的问题。

将N个传感器节点随机部署在监测区域中，每个节点传输的数据量m是随机的。首先，本文在初始部署过程中引入冗余节点，在避免重复收集数据的情况下，减少了节点的能耗。然后，在网络运行过程中，当簇头达到数据承载极限、剩余能量达到一定阈值时，利用FA进行节点移动。具体方法是以节点的剩余能量和节点间的欧氏距离为FA 中的两个吸引力，找出最佳冗余节点。最后，最佳冗余节点移动替换簇头，原簇头替代目标节点，目标节点变为冗余节点，更新冗余节点。利用节点能耗均衡来衡量传感器网络的生命周期，有效地延长了无线传感器网络的生命周期。

本文的目标函数是最小化所有簇头剩余能量的标准差，以均衡网络能耗，表示如式（7）所示：

其中：NCH为簇头数目；Eres(CHi)为簇头的剩余能量。

其中：Eres_max（CH）表示簇头剩余的最大能量；NRN为冗余节点数目。

3 NRBFA描述

3.1 萤火虫算法

萤火虫算法（FA）是一种启发式算法，有以下三个基本假设：

1）所有萤火虫都是无性别之分，每一只萤火虫只会被比其更亮的萤火虫所吸引。

2）萤火虫之间的吸引力与它们的亮度成正比，对于任意两个萤火虫，亮度低的萤火虫向亮度高的萤火虫移动，越靠近亮度越强，吸引力越大，即吸引力与亮度成正比，而亮度随距离的增加而变弱，则吸引力与距离成反比。

3）萤火虫的亮度由目标函数决定［23］。

3.2 NRBFA步骤

本文提出了一种基于FA 的无线传感器节点重部署策略NRBFA 来解决节点能耗不均衡问题，该策略的具体描述如下：

NRBFA 策略利用萤火虫之间的吸引力，以节点的剩余能量和节点间的距离作为吸引力，使得冗余节点向需要被替换的簇头方向移动，同时被替换后的原簇头向目标节点移动，实现冗余节点的移动和更新。该策略最小化簇头剩余能量的标准差，使得网络负载和节点能耗均衡。此外，该算法具有较强的局部搜索能力，可以在一个较小的区域内找到最优解，操作方便，实现简单，参数较少；且从图2 算法流程图分析可知，本文NRBFA 的时间复杂度为O（TNlogN），复杂性较低。其中：T为最大迭代次数，N为节点数目。因此，利用FA来优化节点位置，可以更好地提高网络能量效率，延长网络的生命周期。

具体算法步骤如下：

步骤1 节点随机分布在监测区内，然后利用k-means 算法对传感器节点进行分簇，选出冗余节点，冗余节点一开始处于睡眠状态，不进行任何通信，不消耗能量。

步骤2 计算出每个簇头到达基站的距离dCH-BS以及每个簇内普通节点到CH的距离dNN-CH。

步骤3 计算出冗余节点到簇头的距离dRN-CH以及剩余能量，并进行排序。

步骤4 当簇头的剩余能量小于其设定的能量阈值时，通过FA选择最佳冗余节点RNbest，然后移动RNbest去替换簇头；原簇头也利用FA 找到目标节点，向目标节点移动，此时目标节点成为新的冗余节点。

步骤4.1 在运用FA 移动冗余节点和簇头时，簇头与普通节点间的吸引力F(I1)以及簇头与冗余节点间的吸引力F(I2)分别表示为：

式（9）中：I0为萤火虫个体自身的无衰减的发光亮度，即最大的发光亮度；F（I）表示为节点间的吸引力，即为适应度函数，进行节点替换时，选择适应度函数最好的节点进行移动；dij为节点i到节点j的距离。在本文中，节点间的吸引力由节点的剩余能量和节点间的欧氏距离组成。式（10）～（11）中：γ为光强吸收系数，其值设为1，用来表示萤火虫的发光亮度与距离成反比的关系；Eres_TN为目标节点的剩余能量；Eres_RN为冗余节点的剩余能量；dCH_TN为簇头到目标节点的距离；dRN_CH为冗余节点到簇头的距离，在计算过程中都将剩余能量和距离进行了归一化。λ1和λ2是权重系数，为常数，分别表示为冗余节点更新萤火虫系数和冗余节点替换簇头萤火虫系数。

步骤4.2 节点进行移动后的位置更新公式如式（12）所示：

节点间的吸引度β可表示为：

其中：xi和xj分别代表节点i和j在搜索空间中的位置；α 为［0，1］上的常数，设为0.5；rand为［0，1］上服从均匀分布的随机因子；β0为萤火虫在光源处的最大吸引度，设为1。

步骤4.3 当簇头节点能量耗尽，冗余节点替换簇头节点进行工作，但此时不再寻找目标节点，即冗余节点不再更新，若网络中没有冗余节点可以替换簇头，则网络生命周期结束。

步骤5 节点替换后，若在网络生命周期内，则继续收集数据，迭代次数加1；反之，网络生命结束。

所提出的NRBFA策略的算法流程如图2所示。

图2 NRBFA策略的算法流程Fig.2 Algorithm flowchart of NRBFA strategy

4 仿真与结果分析

本文仿真在Matlab R2014a 环境下运行。在仿真实验中，分别测试50、100、150、200个传感器节点在网络规模为100 m的正方形区域范围内进行节点重部署后的网络性能表现。基站位于网络中心，利用k-means 算法进行分簇，簇的个数为6，各节点的初始能量都为1 J，每个节点采集数据量在1 000～2 000 bit 内随机产生，收发电路处理1 bit 的数据能耗Eelec为50 × 10-9J，簇头融合1 bit 的数据能耗为50 × 10-9J，权重系数λ1和λ2都取0.5。将文献［18］中的节点部署策略作为基准方案，它是基于虚拟力的分区域节点重部署方案VFA（Virtual Force Algorithm），该方案将圆形区域均匀划分为6 个相等的扇形区域，节点基于虚拟力进行移动。本文为了在同一环境下进行比较，现将圆形区域等价于边长为100 m 的正方形区域中，将本文算法与基于虚拟力的节点部署算法在不同部署范围内的节点能耗均衡以及网络生命周期进行比较。

图3 展示了网络总能耗随网络工作轮数的变化趋势。在计算网络总能耗的过程中，节点传输数据所消耗的能量占主要部分，网络的总能耗随网络工作轮数的增加呈增长的趋势；并且，网络中部署的节点数目越多，节点所传输的数据越多，网络的总能耗就越大。在网络运行的前203 轮内，在VFA 的部署方案中，由于部分节点一开始就进行区间移动，而在本文的部署策略中，只有当簇头的剩余能量大于设定的阈值时，网络中没有节点进行移动，并且冗余节点处于睡眠状态，不进行感知和传输数据，不消耗能量，导致VFA 方案中的网络总能耗比本文的NRBFA 策略的总能耗大。但在203 轮之后，基于VFA 的部署方案中，节点数目为200 的网络总能耗不再变化，此时网络已经不能工作，节点数目分别为50、100、150 的网络也在315轮后能耗全部停止增加，而本文算法却在500轮之后的网络总能耗还是趋于增长的趋势。图3 体现了NRBFA 策略要优于VFA 方案，具有更长的网络生命周期和更高的网络能量效率。

图4 是网络总传输数据量随着网络工作轮数的变化。在50、100、150、200个节点部署范围内，由于NRBFA策略中存在冗余节点，基于VFA 的部署方案一开始传输的数据量要比NRBFA 策略多，但随着网络运行轮数的不断增加，VFA 中的网络在315 轮基本不能工作，之后就没有传输数据，而本文方案在500 轮之后网络总传输数据量还呈增长趋势，总的数据传输量远远多于VFA方案。

图3 VFA与NRBFA的网络总能耗随轮数的变化情况Fig.3 Total energy consumption of network of VFA and NRBFA changes with number of rounds

图4 VFA与NRBFA的网络总传输数据量随轮数的变化情况Fig.4 Total amount of data transmitted on network of VFA and NRBFA changes with number of rounds

图5 是不同部署范围下的网络生命周期变化情况。由图5 可知，随着网络部署的节点数目增加，由于网络中的主要能耗来源于网络的节点的数据传输，节点数目越多，传输的数据越多，消耗的能量越大，网络生命周期总体为下降趋势。当网络中部署50 个节点时，两个方案的生命周期都是最长的，分别为3 585 轮和315 轮，随着节点数目的增加，网络生命周期相应地缩短。NRBFA 策略和VFA 方案相比，在相同的部署范围内，本文的部署策略效果更好，网络生命周期远远长于VFA方案对应的网络生命周期。

图5 VFA与NRBFA在不同部署范围的网络生命周期对比Fig.5 Network lifetime comparison of VFA and NRBFA under different deployment scopes

图6 显示不同部署范围下的节点能耗均衡状况。由于每一轮节点传输的数据量是在1 000～2 000 bit 范围内随机产生的，网络出现首个死亡节点的轮数和总轮数可能会有一定差异，本文以最终保存的数据为准。由图6 可知，随着网络部署节点数目的增加，本文部署策略的首个节点死亡轮数到网络死亡轮数之差变化曲线呈增长的趋势，波动范围较小，在20轮以内；而VFA 方案中波动范围较大，在200轮左右。从而可以得出，本文的部署策略在节点能耗均衡方面较VFA 方案效果好，节点能耗也更均衡。

图6 VFA与NRBFA在不同部署范围的节点能耗均衡对比Fig.6 Node energy consumption balance comparison of VFA and NRBFA under different deployment scopes

本文的实验数据主要是从数据量、网络能耗以及网络生命周期来进行说明的。本文的仿真结果表明，NRBFA 策略在数据收集、缓解能量空洞问题以及延长网络生命周期方面优于VFA 方案。该策略在兼顾网络能耗均衡的同时，也保证了数据的有效收集，且在不同节点部署范围内，同样有效地均衡了节点能耗，缓解了能量空洞问题，延长了网络生命周期。

5 结语

在网络运行过程中，由于无线传感器网络节点的能量有限，难以补充或更改，故节点部署是无线传感器网络中均衡节点能耗、延长网络生命周期的主要问题之一。针对网络中节点能耗不均衡问题，本文提出了一种基于萤火虫算法（FA）的节点重部署策略NRBFA，考虑到无线传感网络进行一段时间的数据采集后，簇头负载过大，能量急剧消耗，当其剩余能量达到设定阈值时，不再具备担任簇头和转发数据的能力。此时，基于FA 进行节点重部署，以节点的剩余能量和节点间的距离为吸引力判定指标，冗余节点移动替换簇头，原簇头寻找目标节点，更新冗余节点，以最小化网络簇头剩余能量的标准差，使网络能耗更均衡。仿真结果表明，在不同部署范围内，相较基于VFA的节点部署方案，本文提出的NRBFA策略使得节点能耗更均衡，网络生命周期更长且复杂度更低。此外，下一步考虑各集群的数据量不均匀，引入冗余节点，进行集群的拆分，改变集群的规模，使簇的数据量相对平衡。