基于改进蛙跳算法的WSNs路由协议*

吴 清， 吴开军

(上海海洋大学 信息学院，上海 201306)

基于改进蛙跳算法的WSNs路由协议*

吴 清， 吴开军

(上海海洋大学 信息学院，上海 201306)

在分析已有的各类分簇方法后，提出了一种改进蛙跳算法的无线传感器网络(WSNs)路由协议。将模拟退火(SA)算法的Metropolis判别准则引入到蛙跳算法中，改进蛙跳算法的局部搜索能力。该协议结合传感器节点本身剩余能量和位置建立适应度函数，通过改进蛙跳算法实现适应度函数的最优求解，从而获得合适的分簇，并在簇头节点数据传输时采用新的路由方式。仿真实验表明:该方法在降低网络能耗，延长网络的生存周期方面有明显的优势。

无线传感器网络； 模拟退火； 蛙跳算法； 分簇； 生存周期

0 引 言

为了降低无线传感器网络(WSNs)中传感器节点能量消耗，提高传感器节点的利用率，许多学者对传感器节点路由算法进行了大量研究，提出了许多有效的路由协议[1]。其中，比较经典的协议有：LEACH路由协议[2～5]，EECS路由协议[6]，PEGASIS协议[7]等。LEACH协议在簇头选举时是随机产生，没有考虑簇头节点的剩余能量跟位置，可能导致部分簇头节点过早死亡，从而导致整个网络死亡[8]。

本文提出改进蛙跳算法的分簇机制，通过改进的蛙跳算法寻求最优解，对WSNs分簇进行优化，使整个传感器节点能耗均衡，延长整个网络生存周期。

1 蛙跳算法理论

混合蛙跳算法[9](SFLA)是由美国学者Eusuff和Lansey于2003年提出一种结合粒子群优化(PSO)算法和模因演化算法的优点的一种新的群体算法。该算法具有较好的通用性、灵活性、计算速度快且全局搜索能力强、易于实现等优点，SFLA已经在很多领域得到应用[10，11]。蛙跳算法是一种模仿青蛙群体寻找食物的群体协同搜索算法，设青蛙的群体规模为N，初始种群X=(X1,X2,…,Xn)，计算每个个体适应度值f(xi)，根据计算出来的适应度值大小按递减顺序排序。将整个种群划分为S个子群，每个子群中包含M只青蛙，即N=S×M，在进化过程中，X1放入第1个子群，X2放入第2个子群，Xs放入第S个子群中，Xs+1放入第1个子群，Xs+2放入第2个子群，…,直到最后一个个体放入Xs中。

在每个子群中，记录适应度值最好的个体Pb和适应度值最差的个体Pw，整个种群适应度值最好的个体Xb。在每次局部搜索更新策略中，只对Pw进行操作，提高其适应度。更新策略为

Ds=r(Pb-Pw)

(1)

Pn=Pw+Ds,-Dmax≤Ds≤Dmax

(2)

式中 r为[0,1]内的随机数，Dmax为移动最大步长。得到新个体Pn，如果适应度值大于原有个体Pw，则用Pn取代Pw成为子群新的个体；否则，用Xb代替Pb，按照式(1)、式(2)重新操作，结果若有改进，则取代Pw；如果没有改进，则随机生成一个体取代Pw。重复上面操作，直到子群达到设定的迭代次数。当所有子群局部搜索完成之后，将种群中的所有个体重新排序，划分子群，然后再进行子群局部搜索，如此反复,直到达到设定的群体进化代数为止。

2 提出新的改进协议

2.1 改进蛙跳算法的分簇

根据文献[12]可知，最优簇头数为

(3)

式中εfs为自由空间传播模型下功率放大所需要的耗能系数，εmp为多路径衰减传播模型下功率放大所需要的耗能系数，并将种群划分成Kopt个子群。在WSNs中，传感器节点剩余能量、传感器节点之间的距离都是影响分簇的重要因素，因此,适应度函数为

(4)

式中 α,β为权重因子，且α+β=1。Ecur为传感器节点本身剩余能量，E0为传感器节点初始能量，dmax为种群中所有个体到基站的最大距离。d(n,BS)为传感器节点n到基站的距离。

改进的蛙跳算法分簇步骤如下：

1)初始化种群中的个体，根据式(4)计算每个个体的适应度函数值，并按照降序排序，根据Kopt划分子群个数，并记录每个子群最优个体Xibest和最差个体Xiworst以及种群的最优个体Xgbest，设初始温度为T0

3)如果达到子群内循环迭代次数，对这个子群进行合并，重新计算每个个体适应度函数值进行降序排序，并划分新的子群，再进行模拟退火的降温操作。

4)看是否满足结束条件，如果满足条件，返回结果；否则,返回第2步重新操作。

采用改进蛙跳算法进行分簇的流程图如图1所示。

图1 改进蛙跳算法分簇流程图Fig 1 Cluster flow chart of improved SFLA

2.2 数据传输路由协议

LEACH协议在数据传输阶段，采用簇头节点直接与基站通信，如果簇头节点距离基站比较远，传输数据时簇头节点耗能比较大，因此，采用单跳与多跳路由协议[13]相结合进行数据传输很有必要。具体过程如下：

1)定义距离阈值dlim it，计算簇头节点n到基站节点的距离d，如果d小于阈值dlim it，簇头节点n直接与基站节点通信，完成数据传输。

2)若簇头节点n到基站的距离d大于dlim it，该簇头节点n向整个网络传播信息，当簇头节点j收到簇头节点n数据包时，对它们到基站的距离dn,dj进行判断。如果dn大于dj，将簇头节点j加入簇头节点n的邻居节点中,并终止广播。对于每个簇头节点，若它的邻居簇头表中含有路由簇头，则将数据直接发送给路由簇头;若没有邻居簇头，则将数据发送给邻居簇头，并循环路由。

3 仿真与结果分析

采用Matlab对文中改进蛙跳算法的WSNs路由协议进行仿真和评价。监测区域的WSNs参数设置如下：区域大小为100 m×100 m,基站坐标为(100，250)m，初始能量为0.5 J，多路衰减模型的功率放大系数为10 pJ·bit-1·m-2，自由空间模型的功率放大系数为0.001 3 pJ·bit-1·m-2，发送、接收消耗能量为50 nJ·bit-1，数据包大小为4 000 bit，数据融合消耗能量为5 nJ·bit-1，光吸引强度系数为1.0，步长因子为2。

为了验证本文算法的有效性，对LEACH、本文算法进行仿真。首先利用改进的蛙跳算法对网络进行分簇，然后再通过单跳与多跳相结合的路由算法建立簇头节点到基站的路由。

文中算法的各个参数初始化，种群规模N为100，子群规模数M为5，全局信息交换次数G为8，子群局部搜索次数P为25，初始温度T0为20，降温系数a为0.9，终止温度Tmin为5，函数权重系数α，β分别为0.55和0.45。

3.1 网络生存周期对比

仿真得到的传感器死亡节点随仿真时间变化曲线如图2所示。

图2 传感器死亡节点随时间变化曲线Fig 2 Curve of sensor dead nodes varies with time

从图2中可以看出:LEACH和本文算法对应的第一个传感器节点死亡时间分别为94 s和134 s，最后一个传感器节点死亡时间分别为259 s和317 s。本文算法相对于LEACH，网络生存周期提高了42.56 %,且从图上曲线可以看出，本文算法能量消耗均衡，节点死亡速度慢。

3.2 基站接收数据对比

从图3中可以看出:从基站接收数据总量来看，本文算法相对于LEACH有较好的提高。这主要由于本文方法对网络进行了合理的分簇，在数据传输阶段使用的单跳与多跳相结合的路由，这样保证了网络具有较长的生存周期的同时，使得基站节点可以接收较多簇头节点传输过来的数据。

[1] 钟 智,樊晓平,罗大庸,等.一种基于网格的无线传感器网络分簇路由协议[J].传感器与微系统,2011,30(12):18-20，24.

[2] Heinzelman W,Chandrakasan A,Balakrishnan H.An application-specific protocol architecture for wireless microsensor network-s[J].IEEE Transactions on Wireless Communications,2002,1(4):660- 670.

[3] 宋 文.无线传感器网络技术与应用 [M].北京:电子工业出版社,2007.

[4] 孙利民,李建中,陈 渝.无线传感器网络[M].北京:清华大学出版社,2005.

[5] 任丰原,黄海宁,林 闯.无线传感器网络[J].软件学报,2003,14(7):1282-1291.

[6] 陈志军,李 明.基于免疫退火的WSNs簇首节点选择方法研究[J].重庆师范大学学报：自然科学版,2014(2):72-76.

[7] 刘伟强,蒋 华,王 鑫.无线传感器网络中PEGASIS协议的研究与改进[J].传感技术学报,2013(12):1764-1769.

[8] 朱光辉,张修如,刘卫彪.无线传感器网络中能量有效的加权分簇算法[J].传感器与微系统,2007,26(12):102-105.

[9] Elbeltagi E,Hegazy T,Grierson D.Comparison among five evolutionary-based optimization algorithms[J].Advanced Engineering Informatics,2005,19(1):43-53.

[10] 岳克强,赵知劲,赵治栋.基于神经网络离散混合蛙跳算法的多用户检测[J].计算机工程,2009,19:184-186.

[11] 杨祖元,徐 姣,罗 兵,等.基于SFLA-FCM聚类的城市交通状态判别研究[J].计算机应用研究,2010(5):1743-1745.

[12] 郭 剑,孙力娟,王汝传.基于最佳簇数的无线传感器网络粒子群分簇协议[J].南京邮电大学学报：自然科学版,2010(2):36-40.

[13] Hooman Ghaffarzadeh.Two-phase data traffic optimization of wireless sensor networks for prolonging network lifetime[J].Wireless Networks,2014,20:671-679.

WSNs routing protocol based on improved leapfrog algorithm*

WU Qing， WU Kai-jun

(College of Information Technology,Shanghai Ocean University,Shanghai 201306,China)

After analyzing existing various clusters methods,a wireless sensor networks(WSNs)routing protocol based on improved leapfrog algorithm is proposed.Metropolis discriminant criterion of the simulated annealing algorithm is introduced into the leapfrog algorithm,improve local search ability of leapfrog algorithm.The protocol combines residual energy and position of sensor node to establish fitness function,to achieve the optimal solution of fitness function by improving the leapfrog algorithm,so as to obtain appropriate cluster,and adopt new routing mode in data transmission of cluster head node.Simulation experiment shows that the method has obvious advantage in reducing network energy consumption and prolonging life cycle of network.

wireless sensor networks(WSNs); simulated annealing(SA); leap frog algorithm; cluster; life cycle

by base station

10.13873/J.1000—9787(2016)07—0126—03

2015—10—29

上海市科委科研计划重点支撑资助项目(1251050200)

TP 391

A

1000—9787(2016)07—0126—03

4 结束语

本文采用改进的蛙跳算法，通过迭代找到最优解进行网络分簇，由于蛙跳算法在迭代过程中可能会过早陷入局部最优解，会造成找到的最优解不准确，故在子群局部搜索过程中引入模拟退火算法的Metropolis判别准则，防止算法

过早收敛陷入局部最优。在数据传输阶段采用单跳与多跳相结合的路由，仿真结果表明:本文算法在一定程度上可以有效延长网络生存周期，提高基站接收数据总量。

吴 清(1990-)，男，安徽阜阳人，硕士研究生，主要研究领域为无线传感器网络、Hadoop与数据挖掘。