无线传感器网络改进引力搜索算法的设计与实现

万振凯，贾思禹

（1.天津工业大学 信息化中心，天津 300387；2.天津工业大学 计算机科学与技术学院，天津 300387）

无线传感器网络是一种由大量静止或移动的传感器以自组织或多跳方式构成的无线网络，用以协作地感知、采集、处理和传输网络覆盖地区内被感知对象的信息，并最终把这些信息发送给网络的所有者。传感器节点在与其邻居节点通信的过程中会不断消耗自身资源，通过提升通信效率，降低传感器节点在通信过程中的能量损耗等方式可以有效延长无线传感器网络的生命周期。为了将数据高效传输到目的地，无线传感器网络所面临的最大挑战是如何降低传感器节点在传输过程中的能量损耗以及如何提升无线传感器网络的生命周期。

近年来，对于无线传感器网络路由协议算法的研究一直是无线传感器网络研究的重点，对于无线传感器网络路由协议算法的研究产生了大量成果。文献[1]提出了一种基于优化算法的无线传感器网络路由协议，文中提出的分簇路由协议（evolutionary based clustered routing protocol，ERP）将凝聚度（cohesion）和分离误差（separation error）作为适应度函数的目标来计算适应度值，该协议有效提升了网络生命周期，并降低了网络节点在传输过程中的能量损耗，但协议中算法的稳定性较低。文献[2]提出了一种基于和声搜索（harmony search，HS）算法的分簇路由协议，该协议在实时条件下实现了无线传感器网络的路由，具有良好的网络实用性，但是当协议算法对无线传感器网络中的节点进行再分簇操作时，算法的性能出现了明显的下降。文献[3]提出了一种基于人工蜂群（artificial bee colony，ABC）算法的分簇路由协议，该协议有效提升了网络生命周期，但忽略了信道噪声及其它物理因素对协议本身产生的影响。文献[4]基于粒子群优化（particle swarm optimization，PSO）算法，提出了一种在无线传感器网络中选择簇头节点的新方法，这种方法有效降低了定位簇头节点的代价，并提升了分组传输速率，但是这种方法不能应用于异构无线传感器网络中。文献[5]提出了一种多粒子群免疫协同算法（multi-particle swarm immune cooperative algorithm，MPSICA），该算法提供了一种智能路由恢复策略，对基于簇头节点的路由使用多粒子群算法，可以有效修复网络中簇内普通节点间，以及簇间超级结点间的断接路径。仿真结果表明，基于MPSICA的网络协议可以保证高可靠通信，而MPSICA的主要缺陷在于算法通过睡眠机制调控网络的能量损耗，这个调控过程需要过多的参数值。

针对上述提出协议内算法的不足之处，为使无线传感器网络生命周期得到最大限度的延长，本文设计并实现了一种改进引力搜索算法（IMPGSA），该算法可应用于无线传感器网络协议中。改进算法首先将分数阶微积分集成到传统引力搜索算法对其进行优化，使用优化后的引力搜索算法更新簇头节点的位置，随后使用多目标适应度函数对簇头节点更新后的位置进行评估，这些目标包括距离、延迟、链路生命周期和能量。评估的目的是为了确保无线传感器网络中的簇头节点都处于当前迭代中的最优位置，从而确保了网络节点的生命周期得到延长，进而确保了无线传感器网络自身的生命周期得到延长。

1 无线传感器网络基本模型

图1为无线传感器网络模型示意图。

图1 无线传感器网络模型示意图Fig.1 A model for the w ireless sensor networks

图1所示的无线传感器网络中包含1个汇聚节点（基站）DB，h个簇头节点HC，以及大量普通节点。每一个普通节点都有唯一标识，这些节点在网络中被分组，从而形成簇，普通节点可以通过簇头机制[6-7]向簇头节点HC发送数据，每个簇头节点HC中都记录了该簇中的普通节点个数，图1所示的网络模型被划分为h个簇。汇聚节点DB用于接收网络中所有簇头节点HC发送来的数据。综上所述，簇头节点HC从所有普通节点接收数据，然后将这些数据发送到汇聚节点DB。

图1中节点间的实线连接表示无线网络覆盖范围内的直接通信。每个节点都有其最大通信范围[8]，这个范围均匀分布在参数UT和VT定义的范围内，在无线传感器网络中，汇聚节点的最优位置被定义为{0.5UT，0.5VT}，而网络中的其它节点的位置使用参数UI、VI进行定义。

在无线传感器网络中，每个节点拥有初始能量G0，但节点通常以电池供电，具有能量不可再生性。本文所提出的节点能量模型可描述为，任意普通节点发送到簇头节点的数据包，在节点间数据包发送的过程中，每个数据包的能量损失遵循可用空间与多路径衰减模型[9]，存在于每个传感器节点中的硬件发送器与接收器也同样会导致能量损失，硬件发送器产生的能量损失可以由其内部的无线发射电路以及功率放大器所消耗的能量计算得到，而硬件接收器只需要计算其内部的无线接收电路所消耗的能量即可计算出其产生的能量损失。当一个普通节点发送一个大小为Ks的数据包时，普通节点的能量损耗可表示如下：

式中：Gfs和Gpa表示可用空间与多路径衰减模型所产生的能量损失；Gele为由传感器节点内部电路所产生的能量损失。

产生的原因可能是多方面的，例如调制过程、数字编码过程、放大器自身等等。因此内部电路能量损失可表示为

式中：Gtxr代表硬件发射器所产生的能量损失；GDA代表数据收集时所产生的能量损失；Gpa定义了硬件发射器的多路径放大系数表示普通节点与簇头节点之间的距离。

初始时，每个簇头节点会接收到其簇内普通节点发送来的数据包，此时的能量值将会被更新，随后簇头节点将数据包发送到汇聚节点。当簇头节点从任意传感器节点接收到Ks字节数据的数据包时，簇头节点的能量损耗可表示为

当普通节点发送一个大小为Ks的数据包到簇头节点后，每个传感器节点的能量值都会在发送或接收每Ks字节的数据后被更新。因此，普通节点的能量值被更新为Gb+1（DxN），随后，簇头节点接收到Ks字节的数据，其能量值被更新为Gb+1（DxC），其中

这个节点间数据传输的过程会一直持续到每个节点都变成死节点为止。当一个节点的能量值小于0时，一般认为该节点是一个死节点。

2 引力搜索算法基本原理

2009年，引力搜索算法被首次提出[10]，这种种群优化算法基于牛顿第二定律与万有引力定律，该算法主要利用粒子间的万有引力定律对粒子的运动进行优化，从而搜索到最优解。粒子间的引力与粒子的质量成正比，与粒子的间距成反比。引力搜索算法首先初始化各参数及种群位置，然后计算适应度值、计算粒子的惯性质量以及每个粒子在每个方向上的引力、加速度，计算结束后更新每个粒子的位置、适应度值和全局最优解，若达到最优解则输出，否则进入下一轮迭代。

引力搜索算法的基本流程如图2所示。

图2 引力搜索算法流程图Fig.2 Flowchart of gravitational search algorithm

3 改进引力搜索算法

引力搜索算法本身存在一定的缺陷，例如收敛速度较慢、计算量较大等[11]，因此本文通过引入分数阶微积分理论对引力搜索算法进行了优化，改进引力搜索算法的基本流程如图3所示。

图3 改进引力搜索算法流程图Fig.3 Flowchart of improved gravitational search algorithm

改进算法首先对待处理的粒子进行初始化，然后使用引力搜索算法计算粒子间的引力及加速度，计算结束后使用分数阶微积分方法为下轮迭代更新粒子的位置并使用多目标适应度函数来计算适应度值[12]，随后改进算法将持续更新每个粒子的位置直到所有簇头节点的位置达到当前最优为止。

3.1 初始化

引力搜索算法首先在N个粒子中寻找簇头节点，每个粒子的位置被随机初始化为

3.2 计算引力和加速度

在某一时间点e两个粒子之间会产生引力，该时间点粒子j作用在粒子i上的引力可表示为：

式中：maj表示粒子j的主动引力质量；mpi表示粒子i的被动引力质量；g（e）表示在时间点e时的引力常数；σ是一个很小的常数表示第j个粒子在第r个簇中的位置表示第i个粒子在第r个簇中的位置；E（ije）表示粒子i和粒子j之间的欧氏距离，两个粒子之间的欧式距离一般可表示为：

在r方向上作用在粒子i上的引力之和是网络中所有其它粒子作用在该粒子上引力的随机加权和，这个合力一般可表示为：

式中：randj是一个0到1之间的随机数表示粒子j作用在粒子i上的引力。根据牛顿第二定律，粒子i在时间点e的加速度可表示为：

式中：mii表示粒子i的惯性质量。该粒子在下一时间点的速度应为当前时间点速度的一小部分与其加速度之和，因此下一时间点该粒子的速度可表示为：

式中：randi是一个0到1之间的随机数表示粒子i在时间点e时的速度则表示该粒子在该时间点的加速度。

3.3 应用分数阶微积分方法

在引力搜索算法中，当一个粒子的质量较大时，会导致其在搜索空间中的移动速度降低，从而导致算法性能的下降。本文所提出的改进算法将分数阶微积分方法应用到引力搜索算法中来解决这一问题。分数阶微积分主要利用分数阶导数来简化算法的实现并提供更好的粒子更新方式[13-15]。简而言之，分数阶微积分主要用于为下轮迭代更新粒子的位置。因此下一时间点该粒子的位置可表示为：

式中：离散导数的阶数α可以被推广为0到1之间的任意一个实数，因此式（17）又可以被改写为：

3.4 适应度函数评估位置

在本文所提出的改进算法中，引力质量和惯性质量是通过引力搜索算法计算得来的[16-17]。改进算法在网络中不断进行迭代以更新簇头节点的最优位置，在每轮迭代的过程中，将能量、距离、延迟和链路生命周期作为多种目标，使用适应度函数来评估更新后的簇头节点位置是否为当前最优，从而将多种因素对网络生命周期的影响尽可能减小，适应度函数计算适应度值的过程可表示为：

式中：所有簇内节点数目的最大值用于计算延迟，h表示普通节点的总数。

式中：Lxn表示第x个普通节点和第n个簇头节点之间的链路。该链路上两个节点之间的链路生命周期可表示为：

式中：Ps表示第x个节点的数据发送速率；Pr表示该节点的数据接收速率；R表示传输范围；T表示一个常量值。

3.5 输出最优解

通过分数阶微积分理论更新粒子位置后，下一轮迭代中的粒子质量也需要使用粒子的适应度值进行更新，粒子质量可表示为：

式中：fit（ie）表示粒子i在时间点e时的适应度值；bes（e）和wo（re）分别表示在时间点e时的最佳适应度值和最差适应度值，当作为极小化问题计算时，这2种适应度值可表示为：

当作为极大化问题计算时，这2种适应度值又可表示为：

他慢腾腾地登上一个小丘，看了看周围的地形。既没有树木，也没有小树丛，什么都没有，只看到一望无际的灰色苔藓，偶尔有点灰色的岩石，几片灰色的小湖，几条灰色的小溪，算是一点变化点缀。天空是灰色的。没有太阳，也没有太阳的影子。他不知道哪儿是北方，他已经忘掉了昨天晚上他是怎样取道走到这里的。不过他并没有迷失方向。

通过使用适应度函数，可以求得每个粒子的适应度值。随后，更新粒子位置的过程会一直持续到簇头节点达到当前最优位置为止，算法1给出了改进算法的伪代码。

算法1改进多目标引力搜索算法

输入：HC，Max C（最大迭代次数）

输出：bes（e）（最优簇头节点）

1：Begin

2：随机初始化节点位置Pi

3：P（ie-2）=P（ie）

4：P（ie-1）=P（ie）

6：选择最优粒子位置

7：While（e＜MaxC）

8：For每一个粒子

9：采用分数阶微积分理论生成解P（ie+1）

10：为每个解计算适应度值

11：End For

12：If任意一个节点不可达

13：用一个解替换这个节点

14：End If

15：保存最优粒子位置

16：P（ie-2）=P（ie-1）

17：P（ie-1）=P（ie）

18：P（ie）=P（ie+1）

19：e=e+1

20：End W hile

21：End

3.6 计算能量损耗

一旦确定了当前最优簇头节点位置后，数据包将会由普通节点发送至簇头节点。根据硬件发送器与接收器之间的距离，节点的能量损耗可以通过第1部分中所描述的网络节点能量模型计算得出。因此，每个节点的能量值将会在收发大小为KS的数据包后进行更新，数据包的收发将会持续到节点变成死节点为止。

4 仿真分析

在仿真分析环节中，仿真实验的硬件环境为：CPU：Intel Core i5 6400 2.7 GHz；内存：4GB；操作系统：Windows 10×64；软件平台：MATLAB R2012；仿真实验参数如表1所示。

表1 仿真实验参数Tab.1 P arameters of simulation

为了分析改进算法的性能，通过与3种现存算法（ABC[18，19，20]、GSA、MPSICA）进行比较，并从存活节点数目和网络能量两方面对改进算法的性能进行了分析。

仿真实验中所有节点的网络能量均符合第1部分中定义的网络节点能量模型，实验过程中的每一轮迭代表示算法对无线传感器网络中所有簇头节点的一次位置及能量更新。对比实验采用4种算法（本文改进算法和3种现存算法）对无线传感器网络迭代一定的轮数后，通过对网络内存活节点数目和网络能量的比较分析说明改进算法相较于3种现存算法而言是如何高效延长网络生命周期的。

4.1 影响网络生命周期的因素

一般情况下，无线传感器网络中的节点能量变为0时，认为该节点为死节点，当节点数量小于10%时，认为网络不能继续工作。

节点的能量受通信节点间距离的影响，节点间的距离越大，能量损耗就越严重，网络内通信大多集中在普通节点与簇头节点之间，因此，通过更新簇头节点的位置，使其与自身普通节点之间的距离最优，便可降低能量损耗，从而延长无线传感器网络的生命周期。

更新簇头节点位置操作产生的延迟也应足够小，该延迟与节点消耗的能量成正比，因此，降低更新簇头节点位置操作的延迟，也可有效延长无线传感器网络的生命周期。

在每个簇中，链路普遍存在于普通节点与其对应的簇头节点之间，链路生命周期表示了每个簇的最大传输时长，链路生命周期越长，无线传感器网络的生命周期就越长。

基于对影响网络生命周期因素的分析，本文在2 000轮迭代后通过将每种算法对应的4个适应度参数值（能量、距离、延迟和链路生命周期）进行对比，对改进算法的性能进行了深入分析。

4.2 改进算法性能分析

图4为存活节点数目变化图。

图4 存活节点数目变化图Fig.4 Comparative performance based on number of alive nodes

图4（a）描述了仿真实验中存活节点数目随改进算法迭代轮数变化的关系图，初始状态下的100个普通节点在前1 259轮迭代中能保持全部存活，而在后741轮迭代中，网络内存活节点数目逐渐降低至0。图4（b）描述了对比实验中存活节点数目随4种算法迭代轮数变化的关系图，对比实验将本文所提出的改进算法与3种现存算法进行比较，在第1 100轮迭代时，ABC、GSA、MPSICA这3种算法中的存活节点数目分别为69、15、73，而本文所提出的改进算法仍能保持100个节点全部存活。一般情况下，当网络中节点数目小于10%时，认为网络不能继续工作，对应本文的仿真实验，当网络中存活节点数目仅剩10个时，改进算法的迭代轮数达到1 937轮，相比于ABC、GSA、MPSICA这3种算法的1 749轮、1 582轮和1 713轮，可见改进算法将网络生命周期分别提升了10.7%、22.4%和13.1%。

图5为网络能量变化图。

图5 网络能量变化图Fig.5 Com parative performance based on network energy

图5（a）描述了仿真实验中网络能量随改进算法迭代轮数变化的关系图，在改进算法第一轮迭代时网络能量的最大值为0.548 8，随着迭代继续，网络能量逐渐衰减，在第500轮迭代时，网络能量衰减至0.378 4，在第1350轮迭代时，网络能量衰减至0.106 8。图5（b）描述了对比实验中网络能量随4种算法迭代轮数变化的关系图，对比实验将本文所提出的改进算法与3种现存算法进行比较，在第750轮迭代时，ABC、GSA、MPICA这3种算法的剩余能量分别为0.242 4、0.139 4、0.212 7，而本文所提出的改进算法的剩余能量可以达到0.306 8。在第1 500轮迭代时，ABC、GSA、MPSICA这3种算法的剩余能量分别为0.036 1、0.033 3、0.040 1，而本文所提出的改进算法的剩余能量可以保持在0.071 2。因此可得出结论，本文提出的改进算法可以使网络在相对较长的时间内获得较高的网络能量，有助于在网络节点间高效传输数据，从而有效延长了网络生命周期。

4.3 适应度参数值比较分析

这一小节就4个适应度参数值（能量、距离、延迟、链路生命周期）方面将本文提出的改进算法与3种现存算法进行比较。当4种算法均迭代2 000轮后，每种算法对应的4个适应度参数值如下表2所示。

表2 算法与适应度参数值对照表Tab.2 Comparative fitness parameters of the methods

由表2可见，在能量方面，本文提出的改进算法可以使适应度参数值达到0.041 6，相对于3种现存算法而言，达到了一个较高值。在距离、延迟和链路生命周期等方面改进算法所得到的适应度参数值同样优于3种现存算法。通过表2可知，本文提出的改进算法在适应度参数值方面优于现存算法，表现出更好的性能。

5 结论

本文所提出的改进引力搜索算法（IMPGSA）可应用于无线传感器网络协议中，用于在网络中不断更新簇头节点的位置，从而有效的延长了网络生命周期。该算法通过将分数阶微积分理论集成到引力搜索算法中来优化引力搜索算法，使用这种改进算法来迭代地更新簇头节点的位置，然后将更新后的簇头节点位置以多目标适应函数计算适应度值，这些目标包括能量、距离、延迟和链路生命周期。仿真结果表明，本文提出的改进算法与人工蜂群算法（ABC），引力搜索算法（GSA）和粒子群免疫协同算法（MPSICA）相比，网络生命周期分别提高了10.7%、22.4%和13.1%。