周 坤,李寶林,李仕偉,張剛元

(西華師范大學(xué) 計算機學(xué)院，四川 南充 637009)

?

基于梯度的分層成鏈路由協(xié)議的優(yōu)化改進

周 坤,李寶林,李仕偉,張剛元

(西華師范大學(xué) 計算機學(xué)院，四川 南充 637009)

能源的有限性制約著無線傳感器網(wǎng)絡(luò)的生命周期，而節(jié)點間的通信消耗了絕大多數(shù)能量，所以無線傳感器路由協(xié)議的設(shè)計決定著網(wǎng)絡(luò)生命周期的長短。結(jié)合LEACH和PEAGSIS協(xié)議的特點，對基于梯度的無線傳感器網(wǎng)絡(luò)做了以下幾點改進：①在簇頭的選擇算法方面，將網(wǎng)絡(luò)平均能量、包接受率和節(jié)點與基站的距離納入了算法；②簇內(nèi)成鏈階段在考慮鏈長門限值的同時增加了備用下一跳節(jié)點；③在鏈的重建設(shè)定上提出了一種能量折半的思想。經(jīng)實驗論證，算法在延長網(wǎng)絡(luò)生命周期和減少端到端數(shù)據(jù)時延方面有明顯改進。

無線傳感器網(wǎng)絡(luò)；LEACH；PEGASIS；分層成鏈；簇頭門限值

0 引 言

得益于微機電系統(tǒng)、低功耗嵌入式技術(shù)、傳感器技術(shù)與無線通信技術(shù)等的飛速發(fā)展，無線傳感器網(wǎng)絡(luò)成為了當今世界研究的熱點之一。無線傳感器網(wǎng)絡(luò)(Wireless Sensor Networks,WSNs)是由大量具有感知、通信和數(shù)據(jù)處理能力的傳感器節(jié)點組成的多跳自組織網(wǎng)絡(luò)[1]。該網(wǎng)絡(luò)通常被部署在環(huán)境惡劣的區(qū)域，用于獲取目標信息。它是通過節(jié)點間的相互合作，對監(jiān)測區(qū)域進行信息收集，然后將信息數(shù)據(jù)經(jīng)過簡單融合后發(fā)送給監(jiān)測者。無線傳感器網(wǎng)絡(luò)在軍事情報、環(huán)境監(jiān)測、醫(yī)療護理、智能家居、工業(yè)應(yīng)用、災(zāi)害預(yù)警等諸多領(lǐng)域具有良好的應(yīng)用前景。

然而，無線傳感器網(wǎng)絡(luò)自身的局限性(計算、能量、存儲等資源非常有限)，使得無線傳感器網(wǎng)絡(luò)路由設(shè)計的一個非常重要的目標就是降低節(jié)點能耗，進而提高網(wǎng)絡(luò)的壽命。傳統(tǒng)分簇算法如LEACH、PEGASIS、TEEN等[2-4]，成簇后存在簇的大小和簇頭分布不均勻的問題，導(dǎo)致節(jié)點負載不均衡，降低網(wǎng)絡(luò)的生命周期；后來的MERR[5]、AMERR[6]，通過優(yōu)化傳感器節(jié)點與SINK節(jié)點間的跳數(shù)和傳輸距離達到減少傳輸能耗的目的；文獻[7]提出了基于梯度的拓撲控制算法，結(jié)合定向擴散協(xié)議中梯度的思想，根據(jù)通信半徑把網(wǎng)絡(luò)建成一個梯度場，以減少分級簇等級和數(shù)據(jù)分組轉(zhuǎn)發(fā)跳數(shù)，進而降低時延；CLBG[8]算法結(jié)合梯度拓撲控制與PEGASIS算法，它縮減了簇內(nèi)鏈的長度，降低了因為距離增加帶來的通信開銷，同時采用梯度簇頭間成鏈傳遞數(shù)據(jù)給SINK節(jié)點，既實現(xiàn)了傳輸?shù)目煽啃杂诌M一步降低了通信開銷。

梯度場按照通信半徑把網(wǎng)絡(luò)分為不同的區(qū)域，結(jié)合PEGASIS算法，同一梯度區(qū)域內(nèi)的節(jié)點進行簇頭競爭，進而成簇。然后通過梯度間簇頭成鏈傳輸至SINK節(jié)點，這樣不僅能保證節(jié)點的通信消耗不會因為距離的增加而呈指數(shù)增加。同時，梯度間各自成鏈又能有效地均衡各節(jié)點的能耗，文獻[8]很好地證明了基于梯度的分簇成鏈算法能有效降低和均衡節(jié)點能耗。

本文結(jié)合梯度場的概念，在LEACH和PEGASIS的基礎(chǔ)上，對簇頭選擇算法進行了改進；在簇內(nèi)成鏈的過程中考慮了下一跳節(jié)點的距離，同時增加了下一跳備用節(jié)點；針對PEGASIS協(xié)議每輪都重新成鏈的弊端，提出了一種能量折半思想。實驗證明通過以上改進能更好均衡節(jié)點能耗以及減少時延。

1 基礎(chǔ)概念

無線傳感器網(wǎng)絡(luò)路由協(xié)議按照網(wǎng)絡(luò)結(jié)構(gòu)可以劃分為平面結(jié)構(gòu)和層次結(jié)構(gòu)兩種類型[9]，經(jīng)典的LEACH協(xié)議就是一種低功耗自適應(yīng)集簇分層路由協(xié)議，該協(xié)議是由Heinzelman等人在2000年提出，是無線傳感網(wǎng)中第一個被提出的分簇路由協(xié)議，后面廣為人知的PEGASIS協(xié)議也是在其基礎(chǔ)上進行的改進。

1.1 LEACH路由協(xié)議

LEACH[2]協(xié)議的運行過程是先選舉簇頭，然后穩(wěn)定傳輸信息數(shù)據(jù)，一段時間后重新選擇簇頭，再穩(wěn)定傳輸信息數(shù)據(jù)，周而復(fù)始直至網(wǎng)絡(luò)結(jié)束生命周期。在這里，將每個循環(huán)稱為“輪”，由運行過程可知每輪分為簇建立階段和穩(wěn)定運行階段兩個階段。此外，在每輪的建立階段簇頭都重新選舉，簇內(nèi)成員不變。在穩(wěn)定階段簇內(nèi)節(jié)點和簇頭節(jié)點進行數(shù)據(jù)傳輸。

在簇建立階段的簇頭選舉時，每個節(jié)點隨機選擇區(qū)間(0，1)之間的一個數(shù)。若選定的數(shù)小于設(shè)定的門限閾值，則該節(jié)點成為簇頭節(jié)點。節(jié)點n的門限閾值計算公式[10]如下：

(1)

上式中,p：簇頭個數(shù)與節(jié)點總數(shù)的比值；r：進行了多少輪簇頭選舉；G：在前1/p輪中沒有被選為簇頭的節(jié)點集合。

完成簇頭選舉后，簇頭通過廣播通知整個網(wǎng)絡(luò)，網(wǎng)絡(luò)中的非簇頭節(jié)點則通過接收到的信號情況選擇從屬的簇，在普通節(jié)點發(fā)報文告知相應(yīng)簇的簇頭節(jié)點后就完成了簇的建立。在此階段中，LEACH協(xié)議為了避免多個簇頭廣播和節(jié)點間的沖突碰撞采用了基于CSMA的隨機存取機制。穩(wěn)定運行階段，傳感器節(jié)點通過基于TDMA的方式將收集到的監(jiān)測信息向簇頭進行傳輸，簇頭收到數(shù)據(jù)后，和本身信息數(shù)據(jù)進行融合處理后再發(fā)送給匯聚節(jié)點。節(jié)點運行一段時間后，網(wǎng)絡(luò)進入到下一“輪”，節(jié)點重新開始簇頭選舉。

由LEACH協(xié)議的運行過程可知：網(wǎng)絡(luò)中的簇頭一直保持著通信狀態(tài)，而簇內(nèi)的普通節(jié)點只有在簇創(chuàng)建階段與穩(wěn)定運行時被分配的時隙內(nèi)處于通信狀態(tài)。這樣讓普通節(jié)點在絕大多數(shù)時候保持待機狀態(tài)，有效地減少了普通節(jié)點的功耗開銷，延長了整個網(wǎng)絡(luò)的生命周期。但LEACH協(xié)議還存在著一些不足之處，如：①簇頭的選舉過于頻繁，增加了大量開銷；②簇內(nèi)節(jié)點直接同簇頭節(jié)點通信，增加了簇頭節(jié)點的能耗；③公式(1)這種簇頭的選舉策略，在很大程度上會導(dǎo)致網(wǎng)絡(luò)中簇頭分布不均和簇的大小有很大差別，這樣就會造成各簇頭節(jié)能耗不同，導(dǎo)致個別簇頭節(jié)點較早死亡；④簇頭節(jié)點直接和基站通信，當網(wǎng)絡(luò)存在較多簇頭節(jié)點時，不僅加速了節(jié)點的能耗，同時較多的信號之間也存在干擾，從而降低網(wǎng)絡(luò)的生存時間。

1.2 PEGASIS路由協(xié)議

PEGASIS協(xié)議[11-12]的執(zhí)行過程是，先通過貪心算法把傳感器節(jié)點組成一條鏈，設(shè)定節(jié)點只與距離它最近的鄰居節(jié)點通信，然后在每輪中只選一個節(jié)點作為簇頭(或鏈首)與基站通信。簇頭或鏈首由各個節(jié)點輪流擔當，通過點對點的方式將監(jiān)測數(shù)據(jù)傳輸至基站，在傳輸?shù)倪^程中可以對數(shù)據(jù)進行融合處理，鏈首利用“令牌”(token)控制兩端的節(jié)點將數(shù)據(jù)傳送給鏈首本身，最后由鏈首將融合后的數(shù)據(jù)直接傳輸給匯聚節(jié)點。PEGASIS協(xié)議傳輸數(shù)據(jù)過程如下圖1所示。

相較于LEACHA協(xié)議，PEGASIS協(xié)議避免了前者頻繁選舉簇頭所帶來的額外通信開銷，同時鏈式結(jié)構(gòu)在數(shù)據(jù)傳輸?shù)倪^程中可以將數(shù)據(jù)進行有效的融合處理，有效地避免了冗余數(shù)據(jù)帶來的額外通信能耗。另外，鏈式結(jié)構(gòu)使得節(jié)點間的通信基本上都是使用最小功率，避免了因距離的增加而使通信能耗呈指數(shù)級增長的情況。雖然實驗仿真表明PEGASIS協(xié)議能夠有效地提高網(wǎng)絡(luò)的能量效率和延長網(wǎng)絡(luò)的生命周期。但PEGASIS協(xié)議也有一些不足之處，如：鏈的生成算法會不可避免地導(dǎo)致長鏈的產(chǎn)生，在數(shù)據(jù)傳輸時，長鏈部分會消耗過多的能量而縮短節(jié)點的生命周期；PEGASIS采用輪流擔當鏈首的方法選舉簇頭與基站通信，會產(chǎn)生節(jié)點間能量消耗不均衡，導(dǎo)致部分離基站較遠的節(jié)點過早死亡；每輪結(jié)束后都要重新選擇簇頭然后成鏈，且當鏈上只要有一個節(jié)點死亡時，鏈就需要重新構(gòu)建，這增加了額外的通信開銷。

針對上述兩個協(xié)議的不足，結(jié)合LEACH和PEGASIS兩個協(xié)議各自的優(yōu)點，筆者在梯度模型的基礎(chǔ)上設(shè)計了一種新的能量均衡路由協(xié)議，該協(xié)議分為梯度建立、成簇階段、網(wǎng)絡(luò)成鏈階段(包括簇內(nèi)成鏈和簇間成鏈)、數(shù)據(jù)傳輸4個階段。在簇頭的選舉時采用改進的閾值設(shè)定算法；簇內(nèi)成鏈時設(shè)置距離門限和代價函數(shù)機制，能有效地避免長鏈的產(chǎn)生，同時提供能量的利用效率；數(shù)據(jù)傳輸階段采用次級節(jié)點備選結(jié)合功率控制機制減少數(shù)據(jù)傳輸?shù)臅r延，同時能有效避免因節(jié)點失效引起的鏈的重建，減少開銷。

2 網(wǎng)絡(luò)體系模型

2.1 網(wǎng)絡(luò)模型

假設(shè)無線傳感器網(wǎng)絡(luò)中共有n個節(jié)點，均勻分布在SINK節(jié)點一側(cè)長度為L的區(qū)域內(nèi)，同時具有以下特性：

1)傳感器節(jié)點部署后除非節(jié)點失效或者能量耗盡死亡，否則網(wǎng)絡(luò)的拓撲不會變化；

2)各節(jié)點結(jié)構(gòu)和功能以及初始能量相同；

3)每個節(jié)點都有與網(wǎng)關(guān)進行直接通信的能力，并且可以隨意進行功率控制；

4)基站位于監(jiān)測區(qū)域一側(cè)外固定位置，其發(fā)射功率可以人工控制，并且無能量限制；

5)相鄰節(jié)點間采集的目標數(shù)據(jù)具有相關(guān)性，支持數(shù)據(jù)融合；

6)每個節(jié)點都具有唯一標識和充分的計算能力，滿足不同MAC協(xié)議和數(shù)據(jù)處理對計算性能的要求。

2.2 能量模型

采用文獻[5]中的能量模型作為本文協(xié)議的模型，如下所示。

數(shù)據(jù)發(fā)送能耗模型：

(2)

數(shù)據(jù)接收能耗模型：

ETx(k)=Eelec×k。

(3)

數(shù)據(jù)融合能耗模型：

EGx(k)=Egather×k。

(4)

式(2)為發(fā)送數(shù)據(jù)的能耗模型，ETx(k,d)表示將kbit數(shù)據(jù)傳輸距離d時節(jié)點的能耗。根據(jù)發(fā)送節(jié)點和接收節(jié)點之間的距離遠近，又可將功率放大耗損分為自由空間模型和多路徑衰減模型。Eelec表示發(fā)射電路的耗損能量。εfs和εmp分別表示兩種信道模型下功率放大所需要的能量。

式(3)為接收kbit數(shù)據(jù)的能量耗損模型，僅由發(fā)射電路耗損引起。

式(4)為將接收到的n個節(jié)點發(fā)送過來的nkbit 數(shù)據(jù)與自身數(shù)據(jù)融合成kbit數(shù)據(jù)的能耗模型，Egather為數(shù)據(jù)融合耗損能量[13-14]。

3 路由協(xié)議的優(yōu)化

3.1 梯度建立階段

網(wǎng)絡(luò)建立之初，SINK節(jié)點以nR為通信半徑，遞增地向所覆蓋的區(qū)域發(fā)布當前梯度信息(n=1，2，……，[L/R]，R表示節(jié)點通信半徑的1/2，[L/R]是向上取整的整數(shù))[8]，節(jié)點根據(jù)收到的梯度信息，選擇最小的梯度值為自己所在梯度。如下圖2所示，傳感器接收SINK節(jié)點廣播的梯度信息。

3.2 成簇階段

梯度建立完畢后，等待一段時間，讓所有節(jié)點都明確自己梯度的同時讓各節(jié)點根據(jù)信號強弱計算到基站的距離，記為dNB。接著各節(jié)點發(fā)送NGT(Nid，Gradient，T(n))報文競爭簇頭，T(n)為簇頭門限值由下式(5)決定。根據(jù)SINK節(jié)點廣播梯度信息的過程，節(jié)點可能收到多個梯度的報文，節(jié)點A收到節(jié)點B的NGT報文后首先比較Gradient，若不等則丟棄；若相同則比較A.T(n)與B.T(n)，值大的進入休眠狀態(tài)，等待簇頭產(chǎn)生，值小的繼續(xù)廣播NGT報文競爭簇頭。節(jié)點簇頭競爭成功后，簇頭節(jié)點廣播Hello(Nid，Gradient)報文告知相鄰節(jié)點加入成簇。處于監(jiān)聽狀態(tài)的節(jié)點收到Hello報文后，馬上向簇頭發(fā)送申請入簇報文(AFJC)，簇頭收到申請報文后，回復(fù)確認報文(Re-ack)。

簇頭門限值T(n):

(5)

其中，En是節(jié)點當前的剩余能量，Einitial為節(jié)點的初始能量，Eaverage為網(wǎng)絡(luò)節(jié)點的平均能量，DNB是節(jié)點到基站的距離，PRR是節(jié)點包接收率。簇頭選舉算法優(yōu)先考慮了高剩余能量、高能量利用效率的節(jié)點，同時在節(jié)點的信道質(zhì)量和與基站距離之間做了一個折中，均衡了節(jié)點的能耗和傳輸效率。

3.3 網(wǎng)絡(luò)成鏈階段

3.3.1 簇內(nèi)成鏈

各節(jié)點接收到簇頭發(fā)送的Hello報文后，根據(jù)信號強度計算與簇頭的距離dNC，然后發(fā)送確認消息AFJC(包括入簇節(jié)點的id，dNC)申請入簇,簇頭收到AFJC報文后，比較節(jié)點距離，確定端節(jié)點。和PEGASIS方法一樣，也是從最遠的節(jié)點開始建鏈。為了防止長鏈的生成，采用文獻[7]的方法設(shè)定一個距離門限dthreshold，節(jié)點v與節(jié)點v+1間的鏈路距離用dv表示。如果dv大于dthreshold則這條鏈路為長鏈。假設(shè)已有i個節(jié)點加入鏈，距離門限dthreshold定義：

(6)

其中μ是用戶自定義的系數(shù)。

假設(shè)節(jié)點i+1與節(jié)點i最近，節(jié)點i+2與節(jié)點i次近，先將節(jié)點i+1和節(jié)點i之間的距離dv與距離門限dthreshold進行比較：如果前者小于后者，那么節(jié)點i+1直接與節(jié)點i相連，然后將節(jié)點i+2和i節(jié)點之間的距離dv+1與dthreshold比較，若dv+1小于dthreshold，那么將節(jié)點i+2記錄在節(jié)點i下一跳節(jié)點備選表中；如果dv大于dthreshold，則表示節(jié)點i+1與節(jié)點i鏈接將形成長鏈，它們不能直接相連，節(jié)點i+1繼續(xù)從鏈上找出距離自己最近的節(jié)點j，此時若節(jié)點i+1與節(jié)點j之間的距離小于距離門限dthreshold，則節(jié)點i+1與節(jié)點j直接相連，若大于dthreshold，則長鏈不可避免，節(jié)點i+1直接與節(jié)點i相連。建鏈方法具體實現(xiàn)如圖3所示。由文獻[15]中依據(jù)上述成鏈方法得到如圖4的鏈。

從圖中可以看出該建鏈方法組成的鏈是具有多分支的鏈，距離門限的設(shè)置能夠有效避免相鄰節(jié)點間長鏈的生成，從而節(jié)約節(jié)點能耗。同時距離門限值也是根據(jù)節(jié)點情況動態(tài)改變。但此方法同PEGASIS協(xié)議一樣，鏈上任何一個節(jié)點死亡都將重新建鏈，作者在此基礎(chǔ)上提出了在門限值范圍內(nèi)的下一跳節(jié)點次級備用節(jié)點i+2，當下一跳節(jié)點i+1失效時，當前END節(jié)點首先查看自身下一跳節(jié)點備用表，若有備用節(jié)點i+2，則節(jié)點i直接與節(jié)點i+2相連。若沒有，則重新成鏈。在一定程度上減少了重新成鏈的開銷。

3.3.2 簇間成鏈

由于是以通信半徑1/2建立的梯度。所以簇頭節(jié)點以正常功率廣播簇頭成鏈報文時相鄰兩梯度值的簇頭節(jié)點必定能收到。簇頭節(jié)點根據(jù)接收到的梯度值大小信息，按照貪婪算法從大到小依次連接。最后，梯度值最小的的簇頭直接與基站通信。

3.4 數(shù)據(jù)傳輸階段

本文算法數(shù)據(jù)的傳輸與PEGASIS協(xié)議相似[16]，每輪數(shù)據(jù)的收集都是由基站發(fā)送信標(Beacon)觸發(fā)，簇頭接收到信號后，在簇間鏈向下傳播的同時，簇頭節(jié)點生成控制令牌(token)發(fā)送到端節(jié)點，然后從端節(jié)點啟動數(shù)據(jù)的傳輸。端節(jié)點將數(shù)據(jù)沿著token來的方向傳遞給下一跳節(jié)點，下一跳節(jié)點收到數(shù)據(jù)后，將其與自身產(chǎn)生的數(shù)據(jù)進行處理融合，然后繼續(xù)向下發(fā)送。當數(shù)據(jù)傳輸?shù)酱仡^后，簇頭節(jié)點將數(shù)據(jù)沿著簇間鏈向基站的方向傳輸，下一跳簇頭同樣要對接收數(shù)據(jù)進行處理融合。最終，當數(shù)據(jù)發(fā)送到遠端的基站時標志著完成了一輪數(shù)據(jù)的傳輸過程。數(shù)據(jù)傳輸流程如圖5所示。

每一輪數(shù)據(jù)傳輸完成后，基站都會對Data中各節(jié)點捎帶的節(jié)點信息表NIS(Nid，Gradient，dNB，PRR，En)進行分析，當簇頭節(jié)點當前能量En為剛當選簇頭時能量的1/2時，或簇頭節(jié)點能量低于一輪通信必需能量時發(fā)起簇頭重選操作，這時由基站根據(jù)節(jié)點信息表NIS直接計算得出各梯度簇頭，然后廣播簇頭信息，各節(jié)點根據(jù)梯度值加入簇。另外當基站在一定時間未收到某簇頭發(fā)來的Data時，則認為此簇頭節(jié)點失效，將立即重新啟動該簇的鏈頭選舉過程。

4 實驗仿真及分析

本文采用MATLAB軟件仿真，從網(wǎng)絡(luò)生存周期和數(shù)據(jù)傳輸時延兩方面比較改進算法與LEACH算法、PEGASIS算法和文獻[7]中的CLBG算法。在100m×100m的傳感區(qū)域內(nèi)布置100個傳感器節(jié)點，假設(shè)節(jié)點不知其地理位置且隨機分布，節(jié)點可根據(jù)需求調(diào)節(jié)通信功率，其他實驗參數(shù)如下表。

表1 實驗參數(shù)設(shè)置

本次實驗距離門限參數(shù)μ取1.5，同時由于隨機因素對仿真結(jié)果的影響，所以對四種協(xié)議各循環(huán)計算100次取統(tǒng)計數(shù)據(jù)平均值，得到如下實驗結(jié)果。

從實驗結(jié)果得，LEACH、PEGASIS、CLBG、改進算法四個算法第一節(jié)點死亡的時間依次為683輪、780輪、817輪、855輪，節(jié)點全部死亡時間分別為1 289輪、1 330輪、1 496輪、1 572輪?？傻卯擶SN網(wǎng)絡(luò)中有1%、100%節(jié)點死亡時，本文算法的通信輪數(shù)相對于LEACH算法分別延長了25.1%、21.9%，相對于PEGASIS協(xié)議分別延長了9.6%、18.2%。相對于CLBG協(xié)議分別延長了4.6%、5.1%。

通過仿真計算四種算法中每輪通信數(shù)據(jù)端到端的時延來驗證本文算法對傳輸時延的改進情況。結(jié)果如下圖：

由實驗結(jié)果可得，當網(wǎng)絡(luò)中節(jié)點存活數(shù)較多時，改進算法數(shù)據(jù)傳輸時延明顯低于其他三種算法；隨著節(jié)點的死亡，四種算法的數(shù)據(jù)傳輸端到端時延都逐漸減少，改進算法雖無LEACH與PEGASIS算法減少得多，但時延仍然低于后兩者。

5 結(jié) 論

本文算法結(jié)合梯度場的概念，在吸取LEACH算法與PEGASIS算法優(yōu)點的同時，優(yōu)化了簇頭的選擇算法，在一定程度上減少了簇頭的頻繁更換和整個傳感網(wǎng)節(jié)點能量不均衡問題。此外，在成鏈階段設(shè)置鏈長門限值與增加備用下一跳節(jié)點，避免了PEGASIS算法中的產(chǎn)生長鏈問題和節(jié)點因意外死亡而重新成鏈的時延問題。由實驗結(jié)果可得，改進算法更能降低網(wǎng)絡(luò)中節(jié)點的能耗，延長網(wǎng)絡(luò)的生命周期，采用分層成鏈，簇內(nèi)成鏈，簇頭成鏈的方式傳遞節(jié)點數(shù)據(jù)，有效減少了數(shù)據(jù)的傳輸時延。

[1] 徐 佳.無線傳感器網(wǎng)絡(luò)路由協(xié)議的研究[D].杭州：中國計量學(xué)院,2013.

[2] HEINZELMAN W R,CHANDRAKASAN A,BALAKRISHNAN H.Energy-efficient communication protocol for wireless sensor networks[C]// Hawaii International Conference on System Sciences.2000:8020.

[3] LINDSY S,RAGHAVENDRA C.PEGAS IS:Power-efficient gathering in sensor information systems[C]//Proceedings of the IEE E Aerospace Conference’02.Montana,2002:1125-1130.

[4] RAGHUNANDAN G H,LAKSHAMI B N.A comparative analysis of routing techniques for wireless sensor networks[C]//Proceedings of National Conference on Innovations in Emerging Technology,2011:17-22.

[5] ZIMMERLING M,DARGIE W,Reason J M.Energy-efficient routing in linear wireless sensor network[C]//Proceedings of the IEEE International Conference on Mobile Ad-hoc and Sensor Systems,2007:1-3.

[6] ZIMMERLING M,DARGIE W,Reason J M.Localized power-aware routing in linear wireless sensor network[C]//Proceedings of the 2nd ACM International Conference on Context-Awareness for Self-Managing Systems,2008:24-33.

[7] 段 磊.無線傳感器網(wǎng)絡(luò)基于梯度的分級簇算法研究[D].鄭州：鄭州大學(xué),2009.

[8] 范曉輝,王延年,鄭曉慶.鏈狀線型WSN中基于梯度的分簇成鏈算法[J].計算機應(yīng)用與軟件,2014,31(6):111-115.

[9] 胡 鋼,謝冬梅,吳元忠.無線傳感器網(wǎng)絡(luò)路由協(xié)議LEACH的研究與改進[J].傳感技術(shù)學(xué)報,2007,20(6):1391-1396

[10] 盧先領(lǐng),王瑩瑩,王洪斌,等.無線傳感器網(wǎng)絡(luò)能量均衡的非均勻分簇算法[J].計算機科學(xué),2013,40(5):78-81.

[11] 王 鎮(zhèn).無線傳感器網(wǎng)絡(luò)分簇路由協(xié)議綜述[J].電腦知識與技術(shù),2011,07(8):1788-1793.

[12] JARRY A,LEONE P,POWELL O,et al.An optimal data propagation algorithm for maximizing the lifespan of sensor networks[C]// IEEE International Conference on Distributed Computing in Sensor Systems.Springer-Verlag,2006:405-421.

[13] 李建奇,曹斌芳,王 立,等.一種結(jié)合LEACH 和PEGASIS 協(xié)議的WSN的路由協(xié)議研究[J].傳感技術(shù)學(xué)報,2012,25(2):263-267.

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

[15] 余勇昌,韋 崗.無線傳感器網(wǎng)絡(luò)中基于PEGASIS協(xié)議的改進算法[J].電子學(xué)報,2008,36(7):1309-1313.

[16] 李文峰,沈連豐,胡 靜.傳感器網(wǎng)絡(luò)簇間通信自適應(yīng)節(jié)能路由優(yōu)化算法[J].通信學(xué)報,2012，(3):10-19.

The Optimization and Improvement of Hierarchical Chain’s Routing Protocol Based on Gradient

ZHOU Kun,LI Baolin,LI Shiwei,ZHANG Gangyuan

(College of Computer Science,China West Normal University,Nanchong Sichuan 637009,China)

The life cycle of wireless sensor network is limited by the limitation of energy,and the communication between nodes consumes a large amount of energy,so the design of wireless sensor routing protocol determines the length of the network life cycle.In this paper,according to the characteristics of LEACH and PEAGSIS protocol,the following improvements have been made to the wireless sensor network based on gradient:① in the aspect of cluster heads selection algorithm,the average energy of the network,the packet acceptance rate and the distance between node and base station are incorporated into the algorithm;② chain threshold restriction value are taken into consideration and the alternate next-hop node is increased at the stage of cluster endogenetic chain;③ the thought of a kind of energy binary phase is proposed in the reconstruction of the chain set.The experiments demonstrated that the algorithm can prolong the network life cycle and reduce the end-to-end delay of data significantly.

wireless sensor network;LEACH;PEGASIS;hierarchical chain;cluster head threshold

1673-5072(2016)04-0472-07

2016-03-17

四川省科技廳支撐項目(2013SZ0056，2014SZ0104)

周 坤(1989—)，男，四川遂寧人，碩士研究生，主要從事物聯(lián)網(wǎng)應(yīng)用技術(shù)研究。E-mail:846240787@qq.com

李寶林(1976—)，男，安徽太湖人，博士，副教授，碩士生導(dǎo)師，主要從事物聯(lián)網(wǎng)應(yīng)用技術(shù)與大數(shù)據(jù)分析研究。 E-mail: scu_lbl@sina.com

TP393

A

10.16246/j.issn.1673-5072.2016.04.020