吳 清， 吳開軍

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

基于改進蛙跳算法的WSNs路由協(xié)議*

吳 清， 吳開軍

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

在分析已有的各類分簇方法后，提出了一種改進蛙跳算法的無線傳感器網(wǎng)絡(luò)(WSNs)路由協(xié)議。將模擬退火(SA)算法的Metropolis判別準則引入到蛙跳算法中，改進蛙跳算法的局部搜索能力。該協(xié)議結(jié)合傳感器節(jié)點本身剩余能量和位置建立適應(yīng)度函數(shù)，通過改進蛙跳算法實現(xiàn)適應(yīng)度函數(shù)的最優(yōu)求解，從而獲得合適的分簇，并在簇頭節(jié)點數(shù)據(jù)傳輸時采用新的路由方式。仿真實驗表明:該方法在降低網(wǎng)絡(luò)能耗，延長網(wǎng)絡(luò)的生存周期方面有明顯的優(yōu)勢。

無線傳感器網(wǎng)絡(luò)； 模擬退火； 蛙跳算法； 分簇； 生存周期

0 引 言

為了降低無線傳感器網(wǎng)絡(luò)(WSNs)中傳感器節(jié)點能量消耗，提高傳感器節(jié)點的利用率，許多學者對傳感器節(jié)點路由算法進行了大量研究，提出了許多有效的路由協(xié)議[1]。其中，比較經(jīng)典的協(xié)議有：LEACH路由協(xié)議[2～5]，EECS路由協(xié)議[6]，PEGASIS協(xié)議[7]等。LEACH協(xié)議在簇頭選舉時是隨機產(chǎn)生，沒有考慮簇頭節(jié)點的剩余能量跟位置，可能導致部分簇頭節(jié)點過早死亡，從而導致整個網(wǎng)絡(luò)死亡[8]。

本文提出改進蛙跳算法的分簇機制，通過改進的蛙跳算法尋求最優(yōu)解，對WSNs分簇進行優(yōu)化，使整個傳感器節(jié)點能耗均衡，延長整個網(wǎng)絡(luò)生存周期。

1 蛙跳算法理論

混合蛙跳算法[9](SFLA)是由美國學者Eusuff和Lansey于2003年提出一種結(jié)合粒子群優(yōu)化(PSO)算法和模因演化算法的優(yōu)點的一種新的群體算法。該算法具有較好的通用性、靈活性、計算速度快且全局搜索能力強、易于實現(xiàn)等優(yōu)點，SFLA已經(jīng)在很多領(lǐng)域得到應(yīng)用[10，11]。蛙跳算法是一種模仿青蛙群體尋找食物的群體協(xié)同搜索算法，設(shè)青蛙的群體規(guī)模為N，初始種群X=(X1,X2,…,Xn)，計算每個個體適應(yīng)度值f(xi)，根據(jù)計算出來的適應(yīng)度值大小按遞減順序排序。將整個種群劃分為S個子群，每個子群中包含M只青蛙，即N=S×M，在進化過程中，X1放入第1個子群，X2放入第2個子群，Xs放入第S個子群中，Xs+1放入第1個子群，Xs+2放入第2個子群，…,直到最后一個個體放入Xs中。

在每個子群中，記錄適應(yīng)度值最好的個體Pb和適應(yīng)度值最差的個體Pw，整個種群適應(yīng)度值最好的個體Xb。在每次局部搜索更新策略中，只對Pw進行操作，提高其適應(yīng)度。更新策略為

Ds=r(Pb-Pw)

(1)

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

(2)

式中 r為[0,1]內(nèi)的隨機數(shù)，Dmax為移動最大步長。得到新個體Pn，如果適應(yīng)度值大于原有個體Pw，則用Pn取代Pw成為子群新的個體；否則，用Xb代替Pb，按照式(1)、式(2)重新操作，結(jié)果若有改進，則取代Pw；如果沒有改進，則隨機生成一個體取代Pw。重復上面操作，直到子群達到設(shè)定的迭代次數(shù)。當所有子群局部搜索完成之后，將種群中的所有個體重新排序，劃分子群，然后再進行子群局部搜索，如此反復,直到達到設(shè)定的群體進化代數(shù)為止。

2 提出新的改進協(xié)議

2.1 改進蛙跳算法的分簇

根據(jù)文獻[12]可知，最優(yōu)簇頭數(shù)為

(3)

式中εfs為自由空間傳播模型下功率放大所需要的耗能系數(shù)，εmp為多路徑衰減傳播模型下功率放大所需要的耗能系數(shù)，并將種群劃分成Kopt個子群。在WSNs中，傳感器節(jié)點剩余能量、傳感器節(jié)點之間的距離都是影響分簇的重要因素，因此,適應(yīng)度函數(shù)為

(4)

式中 α,β為權(quán)重因子，且α+β=1。Ecur為傳感器節(jié)點本身剩余能量，E0為傳感器節(jié)點初始能量，dmax為種群中所有個體到基站的最大距離。d(n,BS)為傳感器節(jié)點n到基站的距離。

改進的蛙跳算法分簇步驟如下：

1)初始化種群中的個體，根據(jù)式(4)計算每個個體的適應(yīng)度函數(shù)值，并按照降序排序，根據(jù)Kopt劃分子群個數(shù)，并記錄每個子群最優(yōu)個體Xibest和最差個體Xiworst以及種群的最優(yōu)個體Xgbest，設(shè)初始溫度為T0

3)如果達到子群內(nèi)循環(huán)迭代次數(shù)，對這個子群進行合并，重新計算每個個體適應(yīng)度函數(shù)值進行降序排序，并劃分新的子群，再進行模擬退火的降溫操作。

4)看是否滿足結(jié)束條件，如果滿足條件，返回結(jié)果；否則,返回第2步重新操作。

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

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

2.2 數(shù)據(jù)傳輸路由協(xié)議

LEACH協(xié)議在數(shù)據(jù)傳輸階段，采用簇頭節(jié)點直接與基站通信，如果簇頭節(jié)點距離基站比較遠，傳輸數(shù)據(jù)時簇頭節(jié)點耗能比較大，因此，采用單跳與多跳路由協(xié)議[13]相結(jié)合進行數(shù)據(jù)傳輸很有必要。具體過程如下：

1)定義距離閾值dlim it，計算簇頭節(jié)點n到基站節(jié)點的距離d，如果d小于閾值dlim it，簇頭節(jié)點n直接與基站節(jié)點通信，完成數(shù)據(jù)傳輸。

2)若簇頭節(jié)點n到基站的距離d大于dlim it，該簇頭節(jié)點n向整個網(wǎng)絡(luò)傳播信息，當簇頭節(jié)點j收到簇頭節(jié)點n數(shù)據(jù)包時，對它們到基站的距離dn,dj進行判斷。如果dn大于dj，將簇頭節(jié)點j加入簇頭節(jié)點n的鄰居節(jié)點中,并終止廣播。對于每個簇頭節(jié)點，若它的鄰居簇頭表中含有路由簇頭，則將數(shù)據(jù)直接發(fā)送給路由簇頭;若沒有鄰居簇頭，則將數(shù)據(jù)發(fā)送給鄰居簇頭，并循環(huán)路由。

3 仿真與結(jié)果分析

采用Matlab對文中改進蛙跳算法的WSNs路由協(xié)議進行仿真和評價。監(jiān)測區(qū)域的WSNs參數(shù)設(shè)置如下：區(qū)域大小為100 m×100 m,基站坐標為(100，250)m，初始能量為0.5 J，多路衰減模型的功率放大系數(shù)為10 pJ·bit-1·m-2，自由空間模型的功率放大系數(shù)為0.001 3 pJ·bit-1·m-2，發(fā)送、接收消耗能量為50 nJ·bit-1，數(shù)據(jù)包大小為4 000 bit，數(shù)據(jù)融合消耗能量為5 nJ·bit-1，光吸引強度系數(shù)為1.0，步長因子為2。

為了驗證本文算法的有效性，對LEACH、本文算法進行仿真。首先利用改進的蛙跳算法對網(wǎng)絡(luò)進行分簇，然后再通過單跳與多跳相結(jié)合的路由算法建立簇頭節(jié)點到基站的路由。

文中算法的各個參數(shù)初始化，種群規(guī)模N為100，子群規(guī)模數(shù)M為5，全局信息交換次數(shù)G為8，子群局部搜索次數(shù)P為25，初始溫度T0為20，降溫系數(shù)a為0.9，終止溫度Tmin為5，函數(shù)權(quán)重系數(shù)α，β分別為0.55和0.45。

3.1 網(wǎng)絡(luò)生存周期對比

仿真得到的傳感器死亡節(jié)點隨仿真時間變化曲線如圖2所示。

圖2 傳感器死亡節(jié)點隨時間變化曲線Fig 2 Curve of sensor dead nodes varies with time

從圖2中可以看出:LEACH和本文算法對應(yīng)的第一個傳感器節(jié)點死亡時間分別為94 s和134 s，最后一個傳感器節(jié)點死亡時間分別為259 s和317 s。本文算法相對于LEACH，網(wǎng)絡(luò)生存周期提高了42.56 %,且從圖上曲線可以看出，本文算法能量消耗均衡，節(jié)點死亡速度慢。

3.2 基站接收數(shù)據(jù)對比

從圖3中可以看出:從基站接收數(shù)據(jù)總量來看，本文算法相對于LEACH有較好的提高。這主要由于本文方法對網(wǎng)絡(luò)進行了合理的分簇，在數(shù)據(jù)傳輸階段使用的單跳與多跳相結(jié)合的路由，這樣保證了網(wǎng)絡(luò)具有較長的生存周期的同時，使得基站節(jié)點可以接收較多簇頭節(jié)點傳輸過來的數(shù)據(jù)。

[1] 鐘 智,樊曉平,羅大庸,等.一種基于網(wǎng)格的無線傳感器網(wǎng)絡(luò)分簇路由協(xié)議[J].傳感器與微系統(tǒng),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] 宋 文.無線傳感器網(wǎng)絡(luò)技術(shù)與應(yīng)用 [M].北京:電子工業(yè)出版社,2007.

[4] 孫利民,李建中,陳 渝.無線傳感器網(wǎng)絡(luò)[M].北京:清華大學出版社,2005.

[5] 任豐原,黃海寧,林 闖.無線傳感器網(wǎng)絡(luò)[J].軟件學報,2003,14(7):1282-1291.

[6] 陳志軍,李 明.基于免疫退火的WSNs簇首節(jié)點選擇方法研究[J].重慶師范大學學報：自然科學版,2014(2):72-76.

[7] 劉偉強,蔣 華,王 鑫.無線傳感器網(wǎng)絡(luò)中PEGASIS協(xié)議的研究與改進[J].傳感技術(shù)學報,2013(12):1764-1769.

[8] 朱光輝,張修如,劉衛(wèi)彪.無線傳感器網(wǎng)絡(luò)中能量有效的加權(quán)分簇算法[J].傳感器與微系統(tǒng),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īng)網(wǎng)絡(luò)離散混合蛙跳算法的多用戶檢測[J].計算機工程,2009,19:184-186.

[11] 楊祖元,徐 姣,羅 兵,等.基于SFLA-FCM聚類的城市交通狀態(tài)判別研究[J].計算機應(yīng)用研究,2010(5):1743-1745.

[12] 郭 劍,孫力娟,王汝傳.基于最佳簇數(shù)的無線傳感器網(wǎng)絡(luò)粒子群分簇協(xié)議[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 結(jié)束語

本文采用改進的蛙跳算法，通過迭代找到最優(yōu)解進行網(wǎng)絡(luò)分簇，由于蛙跳算法在迭代過程中可能會過早陷入局部最優(yōu)解，會造成找到的最優(yōu)解不準確，故在子群局部搜索過程中引入模擬退火算法的Metropolis判別準則，防止算法

過早收斂陷入局部最優(yōu)。在數(shù)據(jù)傳輸階段采用單跳與多跳相結(jié)合的路由，仿真結(jié)果表明:本文算法在一定程度上可以有效延長網(wǎng)絡(luò)生存周期，提高基站接收數(shù)據(jù)總量。

吳 清(1990-)，男，安徽阜陽人，碩士研究生，主要研究領(lǐng)域為無線傳感器網(wǎng)絡(luò)、Hadoop與數(shù)據(jù)挖掘。