一種結合LEACH和PEGASIS協議的WSN的路由協議研究*

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

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

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

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

圖1 網絡節點位置分布示意圖

1 系統模型

1．1 網絡模型

假設傳感器網絡中N個傳感器節點分布在M×N的區域當中，并且具有以下性質:

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

(2)每個節點總有監測數據需要發送;

(3)網關位于傳感器監測區域以外的固定一點，網關能量不受限制;

(4)相鄰監測區域內的數據具有相關性，可以進行數據融合;

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

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

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

1．2 能量模型

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

數據發送:

2 典型路由協議

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

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

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

3 改進的路由協議

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

3．1 簇頭的產生

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

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

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

3．2 簇內路由的建立

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

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

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

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

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

圖2 網絡簇頭路由拓撲結示意圖

3．4 簇間的數據傳輸階段

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

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

4 改進算法分析

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

改進的協議以延長網絡存活時間、平衡所有節點的能量消耗和提高整體網絡能耗效率為主要設計目標。定義網絡開始運行到出現指定死亡節點的輪數為WSN的生存期。文中對LEACH協議和改進后協議的節點死亡的生命周期進行了比較，結果如圖3所示。改進后協議的生存期比LEACH協議的生存期有大幅度提高，初始死亡節點出現的輪數大大延遲，網絡總數的20%和50%死亡節點的輪數也得到了改善，這主要由于降低了一些能耗較大的節點承擔簇頭的概率。由于WSN中傳感器節點隨機分布單次生命周期計算起伏較大，所以圖3中的數據是進行50次循環得到的統計平均值。可以看出改進算法大大延長網絡生存周期。

圖4是改進協議和LEACH協議生命周期的另一種比較表達方式，描述了網絡節點每100輪能量消耗之間的關系。可以清楚看出來網絡節點的單位數據量通信的能耗降低，主要是由于各簇內采用了不同協議，使得各節點合理地承擔了通信能量消耗。圖5描述了各節點的剩余能耗的方差分布圖，從該圖可以看出來，節點的剩余能耗得到了更好的均衡。其中LEACH算法可以看出來，由于沒有采用有效均衡機制，導致網絡運行到了中期出現了節點的明顯分化，各節點之間能量消耗出現較大差別，而算法依然讓個節點輪流承擔簇頭，導致節點能量差異一路上揚，出現死亡節點。而改進算法考慮到了節點的差異，能量均衡消耗，大大滯后了第一個死亡節點的出現。

圖4 網絡節點平均剩余能量每百輪消耗曲線圖

圖5 網絡節點能量方差每百輪消耗曲線圖

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

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

5 結束語

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

［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節點分類控制路由算法［J］．傳感技術學報，2011，24(7):1053－1059．

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

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

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

［9］ 鄧亞平，鄧利軍．無線傳感器網絡的能量有效加權分簇算法［J］．計算機工程與設計，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］．大連理工大學學報，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．