基于贪婪—改进果蝇算法的无线传感器网络路由协议*

徐跃州，张 欣，张 涛，李 阳

(贵州大学 大数据与信息工程学院，贵州 贵阳550025)

0 引 言

无线传感器网络(wireless sensor networks，WSNs)［1，2］是由大量、微型、廉价的传感器节点组成的一种自组织多跳的无线网络，作为物联网的支撑技术，具有广阔的发展前景。然而，由于传感器节点所携带的能量十分有限，如何有效地延长网络生存时间一直是研究的热点［3］。由于WSNs分簇协议能降低能量消耗，提高数据转发速率，得到了深入的研究。最经典的分簇协议有LEACH，HEED，EECS［4］等。传统的分簇协议没有考虑簇头节点的合理分布和能量的均衡，致使网络可能产生更多的能耗。

基于此，本文提出一种新型WSNs 路由算法CRP－FOAGA(a clustered routing protocol based on improvement of fruit fly optimization and greedy algorithm for wireless sensor networks)，该算法结合果蝇和贪婪算法的高效寻优性，对WSNs 的传统分簇路由协议进行改进。根据WSNs 簇头节点的布局和剩余能量，建立簇头节点规划的适值函数，通过改进果蝇算法优化分簇结构，利用贪婪算法实现多跳传输，降低簇头能耗，延长网络寿命。

1 算法设计

CRP－FOAGA 算法是充分利用果蝇算法和贪婪算法的动态寻优性，选择能耗最低的路径进行WSNs 与基站的数据传输。本文先对传统果蝇算法进行改进使之适用于WSNs，然后建立一种合理的适值函数，最终，提出基于贪婪—改进果蝇算法的WSNs。

1.1 改进果蝇算法

果蝇优化算法［5］(fruit fly optimization algorithm，FOA)是台湾学者潘文超从果蝇觅食行为中得到启发，提出的一种寻求全局优化的新型仿生学算法，广泛运用于求解函数极值、Z－SCORE 模型的系数调整以及各类神经网络等［6］。与其他智能算法(如蛙跳和粒子群算法)相比，算法简单、收敛速度快，且FOA 仅需调整3 个参数，算法复杂度低［7］。

然而，由于WSNs 内节点坐标值是离散和固定的，不利于果蝇算法的随机扩散寻优，传统果蝇算法的扩散迭代如式(1)

其中，X_axis，Y_axis 为当前最优分簇簇头坐标，h 为步长。

根据实际情况，改进如下:

1)在选出分簇后，簇头坐标为(X，Y)，对于该分簇中每一个簇头(x，y)，计算所有节点(包括自身)到其距离distance;

2)根据公式(2)对距离进行升序排列，并生成随机数r=unidrnd(sizepop)，sizepop 为果蝇算法种群数为

3)该簇头位置变换为

(x(index(r))，y(index(r)));

4)改进果蝇算法扩散寻优迭代式为

1.2 适值函数

假设在一个二维监测区域，传感器网络有N 个节点，根据文献［8］，对于一个边长为a 的正方形区域，最优簇头数目为

其中，εfs，εamp分别为自由空间和多径衰减下的功率放大恒参;d 为簇首到汇聚节点的距离，由此，本文选取K 个簇头节点，记为Ci，i=1，…，K，坐标为(Cxi，Cyi)，簇头节点初始能量为E0，实时能量为Ei，i=1，…，K。普通节点的坐标设为

式中 M 为对应簇头的簇内普通节点数。在改进果蝇算法每次种群扩散寻优时，计算簇头到簇内节点的欧氏距离和为

为了实现网络能量的平衡，以免节点提前死亡，每个簇头节点的能量必须考虑在适值函数中。因此，改进后的适值函数如下

其中，Dismax为该轮最大的欧氏距离和，w 为调节因子。

1.3 基于贪婪—改进果蝇算法的WSNs

改进果蝇算法应用于WSNs 算法如下:

1)初始化果蝇，种群数为sizepop，果蝇位置为(initX(t)，initY(t))，t∈(1，sizepop)，bestSmell=0。

2)根据果蝇位置和簇头节点能量计算适值函数(式(7))，求出适值最大的果蝇及其位置，如下式

3)记录当前果蝇位置和最大适值bestSmell，若

则所有果蝇飞向该位置

且

4)根据改进果蝇算法扩散寻优迭代式(3)，每个果蝇随机向四周搜寻食物。

由于自由空间无线传输的能耗为式(13)，d0=sqrt(εfs/εmp)，当d ＞d0时，采用多径衰扰模式，如式(14);当d ＜d0时，选用自由空间模式［9］，如式(15)

一般情况下，节点的间距小于d0，节点与基站的间距大于d0。为避免直接传输造成的能量严重损耗，采用基于贪婪算法的多跳方式向基站转发数据，贪婪算法是一种求最优解的简单、高效的算法，通常包含一个用以寻找最优解的迭代过程［10］。

具体算法为:

1)计算各个簇头至Sink 节点的距离D，放入集合A 中，进行降序排序:A=［Dmax，D2，…，Dmin］;

2)根据Dmax对应的簇头节点c 的位置，计算其与集合A中其他值对应簇头的最短距离dmin，若A 中无其他值，则dmin为无穷大;

3)若dmin＜Dmax，则簇头c 将数据转发给该最短距离的簇头;否则，转发给Sink;

4)从集合A 中剔除簇头c，并进行降序排列;

5)重复步骤(2)～(4)，直至集合A 为空集。

2 仿真结果

为了验证CRP－FOAGA 算法的有效性，利用Matlab 进行仿真分析。设WSNs 中节点总数为100 个，监测区域为100 m×100 m，Sink 节点位置为(－50，50)m。网络模型为:

1)Sink 节点固定，计算力强且能量供应充足;

2)节点能获取自身位置信息，并发送给Sink;

3)传感器节点能量有限，位置固定，不能移动;

4)节点均有唯一编号，随机分布于监测域内。

算法参数如表1。

表1 算法参数Tab 1 Algorithm parameters

图1、图2 为仿真任意时刻LEACH 与CRP－FOAGA 算法的分簇和路由情况比较图，可以看出CRP－FOAGA 算法的分簇和路由更加合理，能显著的降低网络能耗。

图1 LEACH 算法分簇与路由情况Fig 1 Clustering and routing of LEACH algortithm

图2 CRP-FOAGA 算法分簇与路由情况Fig 2 Clustering and routing of CRP-FOAGA algorithm

传感器网络节点寿命和网络剩余能量如图3、图4，从图3 可以看出:CRP－FOAGA 算法节点的寿命要远高于LEACH 算法，其首个节点和50%节点死亡的时间分别延长41%和17%;从图4 可以看出:CRP－FOAGA 算法的网络剩余能量的减少速度要明显小于LEACH 算法。这说明CRPFOAGA 算法在分簇时的果蝇算法寻优和利用贪婪算法进行多跳转发在每一轮中降低了节点能耗，减缓网络能量消耗的速度，从而延长网络生命周期。

图5 给出了不同w 值对应的节点寿命。可以看出:增大w 值可以延长网络的生存时间，但却提前网络簇头节点的死亡时间。这是由于在式(7)中增大w 值节省了网络能耗而牺牲了系统的可靠性。

图3 节点寿命比较Fig 3 Comparison of node lifetime

图4 网络剩余能量比较Fig 4 Comparison of remained energy of networks

图5 不同w 值的节点寿命Fig 5 Node lifetime of different w value

3 结束语

本文针对WSNs 的分簇方法和多跳传输问题，提出了一种基于贪婪和改进果蝇算法的新型网络路由协议CRPFOAGA。首先，根据节点位置和剩余能量定义了簇头选择的适值函数，同时，利用改进果蝇算法对该适值函数进行快速求解，并利用贪婪算法实现簇头节点的多跳传输。通过Matlab 仿真得出:相对于传统路由算法，CRP－FOAGA 算法合理规划了簇头节点分布，降低网络能耗，提升了网络的寿命，具有更好的性能。

［1］ Liu A F，Wu X Y，Chen Z G，et al.Research on the energy hole problem based on unequal cluster－radius for wireless sensor networks［J］.Computer Communications，2010，33(3):302－321.

［2］ Kalis A，Kanatas A G，Efthymoglou G P.A cooperative beam forming solution for eliminating multi－hop communications in wireless sensor networks［J］.IEEE Journal on Selected Areas in Communications，2010，28(7):1055－1062.

［3］ 陈良银，王金磊，张靖宇，等.低占空比WSNs 中一种节点休眠调度算法［J］.软件学报，2014，25(3):631－641.

［4］ 陈志军，李 明.基于免疫退火的WSNs 簇首节点选择方法研究［J］.重庆师范大学学报，2014，31(2):72－76.

［5］ 潘文超.应用果蝇优化算法优化广义回归神经网络进行企业经营绩效评估［J］.太原理工大学学报，2011，29(4):1－5.

［6］ 程 慧，刘成忠，基于混沌映射的混合果蝇优化算法［J］.计算机工程，2013，39(5):218－221.

［7］ 韩俊英，刘成忠，自适应变异的果蝇优化算法［J］.计算机应用研究，2013，30(9):2641－2644.

［8］ 郭 剑，孙力娟，王汝传.基于最佳簇数的无线传感器网络粒子群分簇协议［J］.南京邮电大学学报，2010，30(2):36－40.

［9］ 胡 静，沈连丰，宋铁成，等.新的无线传感器网络分簇算法［J］.通信学报，2008，29(7):20－26.

［10］汪鲁才，张 健.无线传感器网络的多跳路由协议［J］.传感器与微系统，2013，32(8):14－17.