基于LEACH協議的鏈式簇頭節能路由算法

米守防

(大連民族學院計算機科學與工程學院，遼寧大連116605)

無線傳感器網絡(Wireless Sensor Network，WSN)是由部署在監測區域內大量的智能微型傳感器節點組成，通過無線通信方式形成的一個多跳的、自組織的網絡系統［1-3］。其目的是協作地感知、采集和處理網絡覆蓋區域中被感知對象的信息，并發送給觀察者。作為一種全新的信息獲取和處理技術，無線傳感器網絡已在軍事、環境科學、醫療護理、智能家居和其他領域得到廣泛應用。

傳感器節點是微型電子設備，體積微小，通常攜帶能量十分有限的電池。由于無線傳感器網絡部署區域環境復雜，有些區域甚至人員不能到達［3］，而且傳感器節點個數多，所以傳感器節點通過更換電池的方式來補給能量變得非常困難。如何合理利用傳感器節點有限的能量延長網絡生命周期是傳感器網絡協議設計所面臨的首要問題［4］。將傳感器節點組織成簇的形式有效的減少能量消耗，許多能量高效的路由協議都是在基于分簇(clustering)的路由基礎上進行設計的［5］。

分簇技術是一種節省能耗十分有效的網絡拓撲控制技術，所謂“分簇技術”就是將節點劃分成許多組，稱為簇，每個簇都有一個簇頭和許多簇成員節點。網絡定期的進行分簇，由簇頭節點管理

整個簇，對簇成員節點感知的數據進行融合后再傳輸給匯聚節點［6］。分簇算法具有拓撲管理方便、能量利用高效、數據融合簡單等優點，是當前重點研究的路由技術。其中比較有代表性的分簇路由協議是Heinzelman等人在2000年聯合提出低功耗自適應分簇層次路由協議(low energy adaptive clustering hierarchy，LEACH)［7-8］。

1 LEACH協議分析

1.1 LEACH協議概述

LEACH協議是第一個基于多簇結構的路由協議，其基本思想是將網絡劃分為不同的簇，通過等概率周期性的選擇簇頭，將整個網絡的能量負載相對均衡的分配到每個傳感器節點，從而達到減少網絡能量消耗、延長網絡生命周期的目的。其中，簇頭的選擇是依據網絡中所需要的簇頭節點總數和迄今為止每個階段已成為簇頭的次數來決定的。LEACH定義了“輪”(Round)的概念，其運行分為兩個階段:簇建立階段和穩定數據通信階段。

在簇建立階段，LEACH協議隨機選擇一個傳感器節點作為簇頭，在每輪簇的組織階段，每個節點都生成一個介于0和1之間的隨機數n，如果該隨機數小于閥值T(n)，則該節點成為簇頭。閥值T(n)按公式(1)計算。

其中，p是簇頭在所有節點中所占的百分比，r為選舉輪數，r mod(1/p)代表這一輪循環中當選過簇頭的節點個數，G是這一輪循環中未當選過簇頭的節點集合。在第0輪中，即r=0時，每一個節點都有概率為p的可能性成為簇頭。

在第0輪中成為簇頭的節點，在接下來的1/p輪中不會再成為簇頭，在經過1/p-1輪后，T值變為1，這時還沒有成為簇頭的節點就被選擇為簇類節點;在經過1/p輪后，所有節點再次開始平等地競爭是否當選簇頭［9］。

節點當選簇頭后，發布通知消息告知其他節點自己是簇頭。非簇頭節點根據自己與簇頭之間的距離來選擇加入哪個簇，并告知該簇頭。當簇頭接收到所有的加入信息后，就產生一個TDMA定時消息，并且通知該簇內所有節點。為了避免附近簇的信號干擾，簇頭可以決定本簇中所有節點的CDMA編碼。這個用于當前階段的CDMA編碼連同TDMA定時一起發送。當簇內節點收到這個消息后，他們就會在各自的時間槽內發送數據。經過一段時間的數據傳輸，簇頭節點收齊簇內節點發送的數據后，運行數據融合算法來處理數據，并將結果直接發送給匯聚節點。

1.2 LEACH協議存在的問題

LEACH分簇協議按照一定概率隨機選擇簇頭，簇頭將簇內數據在本地數據融合后再轉發給匯聚節點，減少了實際需要傳輸的數據量，降低了大部分節點的能量消耗;通過簇頭更換機制去均衡負載耗能，從而延長網絡的生存周期。但該協議并未從全局的角度考慮節能，具體有以下幾點。

(1)隨機選舉出來的簇頭概率相同，意味著少能量或者位置偏遠的節點都有可能成為簇頭。由于簇頭節點要與匯聚節點直接通信，簇頭會消耗較多的能量。

(2)隨機選舉的簇頭，簇頭需負擔的簇內節點數不同，個別簇內節點相對較多的簇頭負擔過重，導致這個網絡的負載不均衡。

(3)在選擇簇頭時，并未考慮簇頭的剩余能量，可能某個節點成為簇頭后，剩余能量不夠本輪的通信使用，必然會導致該簇頭的能量迅速耗盡而至死亡，整個被監測區域出現盲區。

簇頭和匯聚節點通信采用單跳通信，會導致距離匯聚節點較遠的簇頭較早死亡，引起網絡拓撲變化影響網絡壽命。

2 基于LEACH協議的鏈式簇頭節能路由算法

2.1 鏈式簇頭節能路由協議

針對LEACH協議的上述缺點，本文在簇頭和匯聚節點數據傳輸階段進行了改進。以平衡總的能量消耗、延長網絡的存活時間為主要設計目標，提出了一種改進的LEACH路由協議。在數據傳輸階段，LEACH協議采用的是單個簇頭直接傳輸給匯聚節點的方式，這種方式簡單，但是對簇頭來講，能量消耗相對很大，尤其不適用于匯聚節點相對較遠和大型網絡的情況。對于簇頭和匯聚節點數據傳輸方式的改進，首先考慮的是實現簇頭之間的多跳數據通信，通過選擇其他簇頭中繼，使數據傳送的距離最小，以減少遠離匯聚點的簇頭能量消耗，進而延長網絡的生存時間。因此，改進后的協議采用了簇頭之間進行多跳傳輸的方式，具體如下:考慮每輪選舉出的簇頭剩余能量和簇頭與匯聚節點間距離等因素，將簇頭節點按照公式(2)所計算出值連接成鏈，在鏈中選取TCH(i)值最小的節點作為鏈首，值最大作為鏈尾(領導節點)直接與匯聚節點通信，通過數據融合，既能減少了需要傳輸的數據量，減少能量消耗，又能保證節點能量不會很快耗盡，而影響數據的采集。

其中，TCH(i)為簇頭i權值，Er(i)為簇頭i的剩余能量，Sd(i)為簇頭i與匯聚節點之間的距離，為常量。

本文采用文獻［10］中簡單的能量消耗模型，在傳輸k比特信息經過距離d的過程中，發送端能量消耗為

其中，Eelec表示發射電路能量消耗;εfs和 εmp為功率放大器所消耗的能量。節點接收k比特的數據所消耗的能量為

將l個長度為k比特的數據包融合所消耗的能量為

其中，EDA為處理1比特數據需要的能量損耗。

2.2 算法描述

算法也是按輪進行運作，每輪由簇的建立和穩定數據傳輸兩個階段組成。簇建立階段采用LEACH構建階段的簇頭選擇和成簇方式選擇簇頭并成簇，簇頭選舉出來以后，向全網發送廣播消息，節點比較收到廣播的強度選擇要加入的簇，并告知簇頭。簇頭為簇內節點創建TDMA時隙表，簇內節點按照時隙表向簇頭發送數據。簇頭接收數據并融合成一個數據包，同時受令牌(Token)控制，然后根據各簇頭的自身情況確定Sd、d0和Er的值，依據公式(2)計算出TCH，并按照TCH的大小進行成鏈。使數據包順著這個鏈向領導節點傳送，領導節點將接收的數據融合成一個數據包發送給匯聚節點。改進后的算法流程如圖1。

圖1 改進后算法流程圖

3 仿真實驗與分析

本文采用的網絡模型如下:傳感器節點隨機分布在一個正方形區域內;傳感器節點同構，具有全網唯一的id號，能量受限，節點靜止;匯聚節點固定;無線發射功率可調。使用Matlab7對LEACH協議和本文算法進行仿真，模擬參數見表1。

表1 模擬參數列表

為了更好的對比改進后協議的性能，在實驗中分別的LEACH協議和改進后的協議進行了仿真。如圖2給出了兩種算法死亡節點數隨時間變化對比，從圖中可以看出本文算法相比原來的LEACH算法，在首個節點到最后一個節點死亡的時間方面要延遲很多，整個網絡的生存周期也延長了很多，本算法更有效使用能量，提高了網絡壽命。

圖2 2種協議死亡節點個數隨時間變化比較

圖3給出了兩種算法數據傳輸隨時間變化對比，從圖中可以本算法隨著數據頻率的降低，傳輸數據量(可靠性)整體上有所提升。從實驗過程分析可看，本算法保障了簇頭之間的連通性，這是提高傳輸可靠性的最重要因素。

圖3 2種協議數據傳輸隨時間變化比較

圖4給出了兩種算法隨時間變化網絡能量消耗比較，由圖中可以看出本算法的能耗明顯低于LEACH算法，這是因為在LEACH算法中所有簇頭都向匯聚節點發送消息，這將消耗大量的能量，而本文算法將簇頭連接成鏈，然后簇頭采用令牌傳輸機制將數據傳輸給領導節點，領導節點融合數據并發送給匯聚節點。這樣減少了各個簇頭同時向匯聚節點發送數據而產生的能量，有效的延長了網絡的生命周期。

圖4 2種協議網絡能量消耗隨時間變化比較

從圖3和圖4可以觀察到，兩種算法在數據傳輸輪次相同既有效數據傳輸量相同的情況下，網絡的能耗越少意味著算法更節約能量，網絡的生存時間越長。而隨著輪次的增加，網絡消耗相同的情況，網絡有效數據傳輸量越多意味著網絡的負載能力強，生命周期也長。采用本算法比LEACH算法更加節約能量。

4 結語

本文提出了一種基于LEACH協議的鏈式簇頭節能路由算法，核心思想就是在簇頭和匯聚節點數據傳輸階段進行了改進。根據簇頭的剩余能量和簇頭與匯聚節點間距離等因素，將簇頭節點連接成鏈，根據規則計算出的值最小的節點作為鏈首，值最大作為鏈尾(領導節點)直接與匯聚節點通信，通過數據融合，既能減少了需要傳輸的數據量，減少能量消耗，又能保證節點能量不會很快耗盡，而影響數據的采集。實驗證明新算法節約了網絡的能量消耗，提高了數據傳輸的可靠性，延長了整個網絡生命周期。

［1］AKYILDIZ I F，SU W，SANKARASUBRAMANIAM Y，et al.Wireless sensor networks:a survey［J］.Computer Networks，2002，38(4):393-422.

［2］王文光，劉士興，謝武軍.無線傳感器網絡概述［J］.合肥工業大學學報:自然科學版，2010，33(9):1416-1419.

［3］孫利民，李建中，陳渝.無線傳感器網絡［M］.北京:清華大學出版社，2005.

［4］齊迎迎，禹繼國，王楠楠.無線傳感器網絡的節能分布式分簇算法［J］.計算機工程，2011，37(3):83-86.

［5］劉瓊，成運.一種無線傳感器網絡分簇路由算法研究［J］.現代電子技術，2010，33(10):162-164.

［6］周新蓮.基于分簇技術的移動無線傳感器網絡數據收集協議研究［D］.長沙:中南大學，2010.

［7］HEINZELMAN W E.Energy-efficient communication protocol for wireless microsensor networks［C］//Proceedings of the 33rd Annual Hawaii International Conference on，2000:3005-3014.

［8］HEINZELMAN W R，CHANDRAKASAN A.And Hari balakrishnan Energy-Efficient communication protocol for wireless microsensor networks［C］//Proceedings of the 33rd Annual Hawaii International Conference on Jan 4-7 2000，2000:10.

［9］張品，徐智福，孫巖.一種新的基于簇頭優化的WSN路由協議［J］.傳感技術學報，2009，22(7):1013-1017.

［10］HEINZELMAN W E.An application-specific protocol architecture for wireless microsensor networks［J］.Ieee Transactions on Wireless Communications，2002，1(4):660-670.