一種結(jié)合LEACH和PEGASIS協(xié)議的WSN的路由協(xié)議研究*

李建奇，曹斌芳，王 立*，王文虎

(1．湖南文理學(xué)院電氣與信息工程學(xué)院，湖南常德415000;2．湖南文理學(xué)院物理與電子科學(xué)學(xué)院，湖南 常 德415000)

無線傳感器網(wǎng)絡(luò)WSN(Wireless Sensor Network)是一種新型的網(wǎng)絡(luò)和計算技術(shù)，它綜合了傳感器技術(shù)、微機電系統(tǒng)、分布式信息處理技術(shù)和無線通信技術(shù)，能夠協(xié)作地實時監(jiān)測、感知和采集監(jiān)測對象的信息并對其進行處理，最后將信息傳送到用戶［1－3］。由于WSN一般采用電池供電，且更換傳感器節(jié)點不切實際，導(dǎo)致節(jié)點能量受限，因此設(shè)計優(yōu)化網(wǎng)絡(luò)的整體能耗效率，延長網(wǎng)絡(luò)壽命的路由協(xié)議是無線傳感網(wǎng)絡(luò)的一個重要研究內(nèi)容［4－5］。

本文主要討論在真實環(huán)境下，節(jié)點的分布普遍存在著因自然環(huán)境(水域)、火災(zāi)等災(zāi)難導(dǎo)致傳感器節(jié)點毀壞，或因節(jié)點故障等原因?qū)е鲁霈F(xiàn)傳感器節(jié)點未能有效布置的區(qū)域，本文把這種區(qū)域稱為洞，如圖1所示。從圖1可以很容易觀察到在A，C區(qū)域的節(jié)點的分布大致是中心集中，而B區(qū)是呈現(xiàn)環(huán)形分布。而WSN一般部署在環(huán)境惡劣的區(qū)域，基站位置也因此需遠離監(jiān)控區(qū)域。有關(guān)的文獻［3－8］均未對此進行探討，本文在LEACH協(xié)議基礎(chǔ)上提出了一種改進協(xié)議，主要思路是在簇的建立過程中，考慮簇內(nèi)的節(jié)點與簇頭之間形態(tài)，根據(jù)簇內(nèi)的特點建立簇內(nèi)路由機制采取單跳或者利用PEGASIS協(xié)議構(gòu)成鏈式通信。簇間采用多跳和單調(diào)相結(jié)合的方式通信。

圖1 網(wǎng)絡(luò)節(jié)點位置分布示意圖

1 系統(tǒng)模型

1．1 網(wǎng)絡(luò)模型

假設(shè)傳感器網(wǎng)絡(luò)中N個傳感器節(jié)點分布在M×N的區(qū)域當中，并且具有以下性質(zhì):

(1)節(jié)點一旦配置完成即保持靜止不動，也不再人工維護，每個節(jié)點結(jié)構(gòu)功能相同，并且具有相同的初始能量，所有節(jié)點都有能力與網(wǎng)關(guān)進行通信，并且具有功率控制功能;

(2)每個節(jié)點總有監(jiān)測數(shù)據(jù)需要發(fā)送;

(3)網(wǎng)關(guān)位于傳感器監(jiān)測區(qū)域以外的固定一點，網(wǎng)關(guān)能量不受限制;

(4)相鄰監(jiān)測區(qū)域內(nèi)的數(shù)據(jù)具有相關(guān)性，可以進行數(shù)據(jù)融合;

(5)每個節(jié)點都有足夠的計算能力支持不同的MAC協(xié)議和數(shù)據(jù)處理;

(6)每個節(jié)點均采用全向天線;

(7)節(jié)點之間通信鏈路是對稱的。

1．2 能量模型

本協(xié)議的節(jié)點能量消耗模型采用文獻［2］。式(1)中，d為傳輸距離，ETx(k，d)表示傳感器節(jié)點發(fā)送kbit數(shù)據(jù)通過距離d時的能耗，由發(fā)射電路耗損和功率放大耗損兩部分構(gòu)成。功率放大耗損根據(jù)發(fā)送者和接收者之間的距離分別采用自由空間模型和多路徑衰減模型。Eelec為發(fā)射電路的耗損能量。εfs和εmp分別表示兩種信道模型下功率放大所需能量。式(2)表示接收kbit數(shù)據(jù)的能量耗損，僅由電路耗損引起。式(3)為將接收到的n個節(jié)點發(fā)送過來的n·kbit數(shù)據(jù)與本身的kbit數(shù)據(jù)融合，融合成kbit數(shù)據(jù)再發(fā)送出去。

數(shù)據(jù)發(fā)送:

2 典型路由協(xié)議

在WSN體系結(jié)構(gòu)中，從網(wǎng)絡(luò)拓撲結(jié)構(gòu)的角度可以大體把它們分為兩類:平面路由協(xié)議和分簇路由協(xié)議。LEACH(Low Energy Adaptive Clustering Hierarchy)協(xié)議是由MIT的Heinzelman等在2000年提出的一種低功耗自適應(yīng)層次路由協(xié)議，很多路由協(xié)議都是基礎(chǔ)改進而來的。PEGASIS(Power-Efficient Gathering in Sensor Information Systems)協(xié)議不同于LEACH的多簇結(jié)構(gòu)，它是在傳感器節(jié)點中采用鏈式結(jié)構(gòu)進行鏈接。

LEACH協(xié)議每輪如果產(chǎn)生簇頭數(shù)較多，由于距離網(wǎng)關(guān)較遠的簇頭節(jié)點要和基站直接通信，簇頭會消耗較多能量;如果產(chǎn)生簇頭數(shù)較少，普通節(jié)點要與遠距離簇頭通信消耗較多能量。同時在選擇簇頭時，并沒有考慮簇頭剩余能量和地理位置等多種網(wǎng)絡(luò)信息，基于隨機產(chǎn)生簇頭的分簇機制可能使部分簇頭節(jié)點過早死亡，部分區(qū)域節(jié)點失去監(jiān)控，也使網(wǎng)絡(luò)總能量消耗過快［9－10］。

PEGASIS協(xié)議是形成一條鏈，數(shù)據(jù)順著鏈向上融合和傳輸?shù)?，雖然節(jié)省了能量，但卻增加了延遲，從而降低了監(jiān)控的實時性。同時WSN常應(yīng)用在惡劣的環(huán)境中，被監(jiān)測的區(qū)域分布有大量的傳感器節(jié)點，如果中間有一個節(jié)點失效，這次的數(shù)據(jù)傳輸就會失效。而在一個節(jié)點密集的區(qū)域，這意味這信息反復(fù)的在曲折傳遞，實際上增加了整體網(wǎng)絡(luò)功耗。

3 改進的路由協(xié)議

針對真實環(huán)境下存在洞的分布情況，結(jié)合LEACH和PEGASIS的特點，提出了一種新的協(xié)議，在有效降低能耗同時保證一定的實時性。協(xié)議把整個數(shù)據(jù)傳輸以輪為單位，每輪又分為簇頭的產(chǎn)生、簇內(nèi)通信的建立、簇首路由的建立和數(shù)據(jù)的穩(wěn)定傳輸階段。

3．1 簇頭的產(chǎn)生

每輪首先由網(wǎng)關(guān)發(fā)出分簇廣播啟動本輪簇頭選舉。該信息包含網(wǎng)絡(luò)中所有簇頭的剩余能量的平均值Eav(平均值Eav通過各個簇頭節(jié)點報告的各簇的平均能量計算得到)，凡是剩余能量低于Eav的節(jié)點定義為低能量節(jié)點，這類節(jié)點不參與簇頭競爭。每個節(jié)點接收該網(wǎng)關(guān)的啟動信息后，并根據(jù)接收到的信號強度，計算出自己到網(wǎng)關(guān)節(jié)點的距離，記為dnw。每個非低能量節(jié)點自身產(chǎn)生一個介于0～1之間的隨機數(shù)，將該數(shù)與門限值T(n)作比較，若該數(shù)小于T(n)則該節(jié)點將成為臨時簇頭節(jié)點，若該數(shù)大于T(n)則該節(jié)點暫時成為普通節(jié)點，門限值T(n)由式(4)決定［9］:

其中，En是節(jié)點n的當前剩余能量，Enav是上一次簇內(nèi)網(wǎng)絡(luò)節(jié)點的平均能量(可以近似視為本輪競爭范圍內(nèi)節(jié)點的平均能量)。Neighbor_num表示節(jié)點的鄰近節(jié)點數(shù)目，CH_Times表示節(jié)點在以前輪數(shù)中被選為簇頭節(jié)點的次數(shù)。簇頭選舉算法應(yīng)當優(yōu)先高剩余能量和低能量消耗功率的節(jié)點優(yōu)先當選。

簇首節(jié)點選出之后，廣播自己當選簇首的信號ADV(Advertisement Message)，周圍節(jié)點收到消息后，根據(jù)信號強度，選擇所屬簇首，然后發(fā)送一個請求加入信息，此信息除了包含簇首節(jié)點ID以及自己的ID號以外，還需要包含自己的剩余能量狀態(tài)、本節(jié)點距離簇頭的距離和本節(jié)點距離網(wǎng)關(guān)的距離［7］。

3．2 簇內(nèi)路由的建立

簇首在一定的時間內(nèi)接收到所有簇內(nèi)成員的加入請求信息后，將記錄下所有本簇內(nèi)節(jié)點到簇頭的距離。首先簇首根據(jù)網(wǎng)絡(luò)設(shè)置網(wǎng)絡(luò)標準距離(即距離網(wǎng)關(guān)的最大距離)，計算本簇首距離網(wǎng)關(guān)的距離比例，Φi=dig/dng，dig第i個簇首距離網(wǎng)關(guān)的距離，dng表示網(wǎng)絡(luò)標準距離。當Φi系數(shù)小于0．65，即該簇首距離網(wǎng)關(guān)較近，此時簇內(nèi)路由之間采取單跳通信;當Φi系數(shù)大于0．65，即簇首處于網(wǎng)絡(luò)中心點以外的區(qū)域(意味該簇首遠離網(wǎng)關(guān))，此時簇首將計算簇的分散系數(shù)ηi，分散系數(shù)描述了本簇內(nèi)各成員分散的特點。分散系數(shù)的計算如式(6)所示，通過對各簇內(nèi)節(jié)點距離簇頭與距網(wǎng)關(guān)距離之比求和，再除以簇內(nèi)節(jié)點數(shù)。離散系數(shù)根據(jù)式(2)計算測量簇內(nèi)非簇頭節(jié)點的分布程度:

dng為第n個簇內(nèi)節(jié)點至的網(wǎng)關(guān)距離，dni為第n個簇內(nèi)節(jié)點至簇頭的距離。該ηi越大反映簇內(nèi)各節(jié)點距離網(wǎng)關(guān)遠，離本簇頭的平均距離同樣遠。當該系數(shù)超過一個閾值后，簇內(nèi)直接采用單跳通信不利于節(jié)約能耗，因此將由簇頭啟動PEGASIS協(xié)議構(gòu)建簇內(nèi)路由。經(jīng)過實驗經(jīng)驗值確定，閾值選擇為0.65。當ηi分散系數(shù)小于等于0．65時，則定義該簇為常規(guī)區(qū)域，簇內(nèi)節(jié)點采用單跳方式直接和簇頭節(jié)點通信，簇頭分配好的TDMA表廣播給每個簇內(nèi)成員，同時廣播下一次簇內(nèi)將接任簇頭的下輪節(jié)點，接任節(jié)點將做好準備。接任節(jié)點根據(jù)離本輪簇頭最近進行選擇。

簇的類型通過ηi分散系數(shù)被定義為緊密簇和分散簇。當ηi分散系數(shù)小于0．65時，則定義該簇為存在空洞的分散區(qū)域，該分區(qū)采用PEGASIS協(xié)議使用貪婪法構(gòu)成鏈路，同時將簇頭的資格轉(zhuǎn)移給離網(wǎng)關(guān)最近的非低能量節(jié)點，并由新簇頭節(jié)點報告網(wǎng)關(guān)，網(wǎng)關(guān)同時將該簇頭在整個網(wǎng)絡(luò)的通信時隙上置后，避免影響整個網(wǎng)絡(luò)性能。各節(jié)點將自身的距離網(wǎng)關(guān)的信息報告簇頭。

3．3 簇間多跳路由的形成

簇建立之后，每個簇首廣播一個非持續(xù)性強度信號，信號中還要包含自身的ID，每個簇首接收到其它簇首廣播的強度信號，確定出模擬距離信息并記錄下來，然后所有簇首節(jié)點把這些模擬距離信息發(fā)送給基站，同時還要發(fā)送自己的剩余能量狀況并捎帶發(fā)送本簇的平均剩余能量。站接收到這些信息后采用文獻［8］算法，規(guī)劃出全網(wǎng)鏈路拓撲，同時記錄下剩余能量不足的簇首。接下來把網(wǎng)絡(luò)鏈路數(shù)據(jù)結(jié)構(gòu)廣播給所有簇首節(jié)點。這樣簇首間的主干網(wǎng)絡(luò)形成。簇間的鏈路多跳路由如圖2所示。

圖2 網(wǎng)絡(luò)簇頭路由拓撲結(jié)示意圖

3．4 簇間的數(shù)據(jù)傳輸階段

簇間數(shù)據(jù)傳輸與LEACH中的方法是類似的，每個簇內(nèi)節(jié)點根據(jù)TDMA表，在自己的時隙內(nèi)向簇首傳輸數(shù)據(jù)。簇首接收完簇內(nèi)成員的數(shù)據(jù)并進行融合后，根據(jù)開始向沿鏈路向網(wǎng)關(guān)傳輸，每個簇首節(jié)點接收到上一級節(jié)點的數(shù)據(jù)后進行數(shù)據(jù)融合，然后再發(fā)送給下一跳節(jié)點。需要注意的是，發(fā)送節(jié)點每發(fā)送出數(shù)據(jù)后并不立即清除該數(shù)據(jù)，而是存儲一定的時間，接收數(shù)據(jù)的簇首一旦接收到上級節(jié)點的數(shù)據(jù)立即返回一個已接收信號，發(fā)送節(jié)點收到后再把已發(fā)數(shù)據(jù)清除，如果在一段時間內(nèi)沒有接收到反饋信號，則表明該數(shù)據(jù)發(fā)送丟失，則重發(fā)一次，如果還是發(fā)送不成功，則把該數(shù)據(jù)發(fā)送給鏈路表中的下一跳簇首節(jié)點。在這個過程中，每個接收節(jié)點同樣設(shè)置一個定時器，如果長時間接收不到上一級簇首節(jié)點的數(shù)據(jù)，則不再等待，而是直接把自己的數(shù)據(jù)向下一跳節(jié)點傳輸［10－12］。

數(shù)據(jù)傳輸一段時間后，基站選擇一個新的簇首節(jié)點作為鏈首與自己直接通信，同時根據(jù)記錄下來的能量匱乏節(jié)點信息，避開這些節(jié)點充當鏈首，以均衡負載。網(wǎng)絡(luò)主干路由依據(jù)這個新的鏈首再進行一段數(shù)據(jù)傳輸。當所有簇首(除了能量匱乏節(jié)點)充當過鏈首之后，整個數(shù)據(jù)傳輸將進入新的一輪，進行簇的建立、簇首間路由的建立和數(shù)據(jù)傳輸階段，循環(huán)往復(fù)。

4 改進算法分析

本文利用MATLAB軟件將改進算法(NEW＆P)與LEACH算法和PEGASIS算法進行了仿真比較，分別從網(wǎng)絡(luò)生存周期和數(shù)據(jù)傳輸時延兩方面來評價改進算法的性能。在傳感區(qū)域為100 m×100 m的空間內(nèi)有100個傳感器節(jié)點，在區(qū)域內(nèi)隨機的產(chǎn)生2個10 m×10 m空洞區(qū)域，該區(qū)域不設(shè)置節(jié)點。LEACH協(xié)議中假設(shè)節(jié)點不知其地理位置，且節(jié)點隨機分布，本文采用LEACH協(xié)議中原有的參數(shù)來仿真。改進協(xié)議主要是與LEACH進行比較，本文采用MATLAB對LEACH協(xié)議和改進算法進行了仿真和比較，其中基站位置被固定為(0 m，0 m)，因為往往實際應(yīng)用中要求網(wǎng)關(guān)遠離監(jiān)控區(qū)域，所以如此設(shè)定。節(jié)點初始能量為 0．5 J，Eelec=50 nJ/bit，εfs=10 pJ/(bit·m－2)，εamp=0．0013 pJ/(bit·m－4)，數(shù)據(jù)融合EGX=5 nJ/(bit·signal－1)，仿真最大輪數(shù)為 9999 輪。為了便于對比，消除一些隨機因素影響，現(xiàn)對兩個算法各仿真50次，對數(shù)據(jù)取統(tǒng)計平均值。

改進的協(xié)議以延長網(wǎng)絡(luò)存活時間、平衡所有節(jié)點的能量消耗和提高整體網(wǎng)絡(luò)能耗效率為主要設(shè)計目標。定義網(wǎng)絡(luò)開始運行到出現(xiàn)指定死亡節(jié)點的輪數(shù)為WSN的生存期。文中對LEACH協(xié)議和改進后協(xié)議的節(jié)點死亡的生命周期進行了比較，結(jié)果如圖3所示。改進后協(xié)議的生存期比LEACH協(xié)議的生存期有大幅度提高，初始死亡節(jié)點出現(xiàn)的輪數(shù)大大延遲，網(wǎng)絡(luò)總數(shù)的20%和50%死亡節(jié)點的輪數(shù)也得到了改善，這主要由于降低了一些能耗較大的節(jié)點承擔簇頭的概率。由于WSN中傳感器節(jié)點隨機分布單次生命周期計算起伏較大，所以圖3中的數(shù)據(jù)是進行50次循環(huán)得到的統(tǒng)計平均值?？梢钥闯龈倪M算法大大延長網(wǎng)絡(luò)生存周期。

圖4是改進協(xié)議和LEACH協(xié)議生命周期的另一種比較表達方式，描述了網(wǎng)絡(luò)節(jié)點每100輪能量消耗之間的關(guān)系?？梢郧宄闯鰜砭W(wǎng)絡(luò)節(jié)點的單位數(shù)據(jù)量通信的能耗降低，主要是由于各簇內(nèi)采用了不同協(xié)議，使得各節(jié)點合理地承擔了通信能量消耗。圖5描述了各節(jié)點的剩余能耗的方差分布圖，從該圖可以看出來，節(jié)點的剩余能耗得到了更好的均衡。其中LEACH算法可以看出來，由于沒有采用有效均衡機制，導(dǎo)致網(wǎng)絡(luò)運行到了中期出現(xiàn)了節(jié)點的明顯分化，各節(jié)點之間能量消耗出現(xiàn)較大差別，而算法依然讓個節(jié)點輪流承擔簇頭，導(dǎo)致節(jié)點能量差異一路上揚，出現(xiàn)死亡節(jié)點。而改進算法考慮到了節(jié)點的差異，能量均衡消耗，大大滯后了第一個死亡節(jié)點的出現(xiàn)。

圖4 網(wǎng)絡(luò)節(jié)點平均剩余能量每百輪消耗曲線圖

圖5 網(wǎng)絡(luò)節(jié)點能量方差每百輪消耗曲線圖

在經(jīng)典的LEACH協(xié)議中，每個節(jié)點選擇所屬簇首的時候只是考慮了與簇首的距離，而沒有考慮簇首的剩余能量情況。這可能導(dǎo)致當選簇首的低能量節(jié)點快速死亡，進而縮短整個網(wǎng)絡(luò)的生命周期。改進算法在簇建立階段，通過能量比較和尋找替代簇首，均衡了能量消耗。同時新增的能量比較算法很簡單，TDMA的計算分配與LEACH相比基本不增加能量開銷，故整體上增加的延遲與能耗開銷很小。

PEGASIS理論上的性能是非常好的，但是會帶來較大的滯后性，特別隨著監(jiān)控區(qū)域的擴大，不利于系統(tǒng)實時性滿足，同時個別節(jié)點的失效，會導(dǎo)致數(shù)據(jù)采集的整體失敗。改進算法利用PEGASIS比較適合稀疏網(wǎng)絡(luò)的特性，將鏈路策略在局部特殊區(qū)域，不僅有效的降低了能耗，而且保證了必要的實時性。從傳輸速度而言，可以很直觀地分析到改進算法比PEGASIS協(xié)議較優(yōu)。

5 結(jié)束語

針對真實環(huán)境下節(jié)點分布的不均勻特點，在分析LEACH和PEGASIS優(yōu)缺點的基礎(chǔ)上，把兩者結(jié)合起來提出了一種改進路由協(xié)議。新的協(xié)議在成簇階段加入一個機制用來實現(xiàn)高能量節(jié)點替代低能量節(jié)點擔任簇首，避免低能量節(jié)點過早死亡，成簇的路由協(xié)議根據(jù)簇的分散特性采用不同的簇類通信方式;在簇間形成一個單跳和多跳結(jié)合路由協(xié)議用來實現(xiàn)數(shù)據(jù)融合和轉(zhuǎn)發(fā)，同時加入一種可靠傳輸?shù)臋C制。理論分析和仿真結(jié)果一致表明改進的算法能有效減少節(jié)點能量消耗，降低節(jié)點死亡速度，有效延長網(wǎng)絡(luò)生命周期。

［1］ Zhao F，Guibas L J．Wireless Sensor Networks:An Information Processing Approach［M］．Morgan Kaufman，2004:7－10．

［2］ Heinzelman W，Chandrakasan A，Balakrisham H．Energy-Efficient Communication Protocol for Wireless Microsensor Networks［C］//Proceedings of the 33rd Annual Hawaii Int’l Conf．on System Sciences．［S．l．］:IEEE Computer Society，2000:3005－3014．

［3］ Ye W，Heidermann J，Estrin D．An Energy-Efficient MAC Protocol for Wireless Sensor Networks［C］//Proceedings of the IEEE INFOCOM，2002，3:1567－1576．

［4］ Heinzelman W B，Chandrakasan A P，Balakrisham H．An Application-Specific Protocol Architecture for Wireless Microsensor Networks［J］．IEEE Transactions on Wireless Communication，2002，1(4):660－670．

［5］ 劉群，白全煒，曾憲華，等．能量感知的WSN節(jié)點分類控制路由算法［J］．傳感技術(shù)學(xué)報，2011，24(7):1053－1059．

［6］ 楊銀堂，高翔，柴常春，等．一種WSN中的能耗優(yōu)化動態(tài)路由算法［J］．西安電子科技大學(xué)學(xué)報，2010，37(5):776－782．

［7］ 朱丁丁，金心宇，張昱．基于能量優(yōu)先分簇算法的WSN分層路由協(xié)議［J］．傳感技術(shù)學(xué)報，2009，22(4):579－585．

［8］ 張震，閆連山，潘煒．基于LEACH和PEGASIS的簇頭成鏈可靠路由協(xié)議研究［J］．傳感技術(shù)學(xué)報，2010，23(8):1173－1178．

［9］ 鄧亞平，鄧利軍．無線傳感器網(wǎng)絡(luò)的能量有效加權(quán)分簇算法［J］．計算機工程與設(shè)計，2011(4):1216－1219，1215．

［10］ LUO H，LUO J，DASSK．Adaptive Datafusion for Energy Efficient Routing in Wireless Sensor Networks［J］．IEEE Transactions on Computers，2006，55(10):1286－1299．

［11］王洪玉，劉爽．WSN中基于融合代價和傳輸代價的分簇算法［J］．大連理工大學(xué)學(xué)報，2010，50(4):591－596．

［12］ Holt B，Doherty L，Brewer E．Flexible Power Scheduling for Sensor Networks［C］//Proceedings of the IEEE/ACM 3rdInternational Symposium on Information Processing in SensorNetworks，(IPSN)，2004，205－214．