基于L E A C H協議的無線傳感器網絡路由算法的改進與仿真

趙芳芳，高媛

(中北大學 電子與計算機科學技術學院，山西 太原，030051)

0 引言

無線傳感器網絡(Wireless Sensor Networks,WSN)[1]可應用于軍事、商業、醫療救護、環境監測等諸多領域，目前已成為計算機和通信領域中的研究熱點之一。

無線傳感器網絡是由大量的微小節點通過無線通信技術組成的自組織網絡。傳感器節點依靠電池供給能量，而又不能對數量眾多的節點更換電池，因此網絡生命周期就成為了無線傳感器網絡的關鍵性能指標之一。在目前的研究中，分簇算法被認為是進行高效的能量管理、延長網絡生命周期的最有效的途徑之一。本文對經典的無線傳感器網絡分簇協議LEACH（低功耗自適應分簇協議）[2]進行了深入的研究，簇的形成方法是LEACH協議研究的主要內容，而簇頭選擇算法又是簇形成的核心，在LEACH協議中簇頭選擇算法不能做到最優，無法保證簇頭處于恰當的位置，這導致簇頭過早耗盡能量，縮短了網絡的生命周期[3]。針對LEACH協議中簇頭選擇算法存在的不足，本文提出了改進的協議。

1 LEACH協議

1.1 LEACH協議算法

LEACH算法是一種周期性執行的低功耗自適應分簇拓撲算法[4]，在運行過程中,通過不斷隨機選取簇首達到能耗均勻分布的目的。LEACH定義了“輪”(round)的概念，每一輪分為兩個階段:簇的建立階段和穩定工作階段。在簇的建立階段,首先需要選舉簇首節點，簇首節點的選取是由每個節點自主決定的。對于每個節點n產生一個0~1的隨機數，如果該隨機數小于閾值T(n)，則節點當選為本輪簇首。T(n)定義如下:

式中:p為簇首節點占總節點數的百分比； r為當前的簇首選舉輪數；G為過去輪中未當選簇首的節點集。在r=0時,節點以p的概率選取簇首；對于在前r(r<1/p)輪之內當過簇首的節點取消其再次當選的資格，從而保證其他節點以相同的概率當選簇首。當分簇過程完成后便可以進行數據的傳輸,進入穩定工作階段。

1.2 LEACH協議的優缺點

LEACH協議具有很多優點，比如分層的簇型結構、本地數據聯合處理和簇頭節點動態分配，特別是在處理具有高度相關性的數據時，由于數據融合力度大，冗余數據被大量消除，因此在能耗方面性能較好，但LEACH仍有不足之處：

(1) 在LEACH算法中,分布式簇首選取機制能夠均勻網絡中節點能耗,但隨機選取的簇首節點無法保證簇頭節點在空間上均勻分布，在某些情況下，算法所選擇的簇頭節點可能集中在某一個小范圍之內，使得一部分成員節點無法加入任何簇或者成員節點與簇頭節點進行數據傳輸時消耗過多的能量[5-6]。

(2) LEACH算法假定所有節點都能直接與Sink節點進行通信，這顯然限制了LEACH算法在較大區域內無線傳感器網絡的應用。

2 改進后的LEACH協議

針對LEACH路由協議的上述缺點，本文對簇頭選擇算法進行了改進，以平衡總的能量消耗、延長網絡的存活時間為主要設計目標，提出了一種改進的LEACH路由協議。

在簇頭選擇階段，LEACH協議是在整個區域中隨機地選擇簇頭，這種方式簡單，但是無法保證簇頭節點在空間上的均勻分布，在某些情況下，算法所選擇的簇頭節點可能集中在某一個小范圍之內，使得一部分成員節點無法加入任何簇或者與簇頭節點進行數據傳輸時消耗過多的能量。改進后的協議充分考慮了簇頭節點在空間上的分布，首先將整個網絡劃分成若干個小的區域，如圖1所示。

圖1 區域的劃分

根據網絡的大小、節點的傳輸范圍和節點的分布密度決定區域的半徑R。在標志為ZONE0的第1個區域中，傳感器節點與Sink節點的距離小于區域半徑R。在標志為ZONE1的第2個區域中，傳感器節點與Sink節點的距離大于R，但小于2R。依此類推，在標志為ZONEi的第i個區域中，傳感器節點與Sink節點的距離大于i×R，但是小于(i+1)×R。最后一個區域包含了超過上一個區域范圍的所有剩余節點。因此，區域的總數為：

其中，N_ZONE為網絡中區域的個數；NETWORK_ RANGE為網絡的大小。

區域劃分完后，Sink節點廣播區域信息給每一個傳感器節點，使它們知道自己屬于哪個區域。每個區域中的簇頭數目是根據每個區域的面積決定的。在ZONE0中由于包含Sink節點，因此不需要為該區域分配簇頭節點。在ZONE1中，僅僅為它分配一個簇頭節點。在ZONE2中，簇頭的數目根據ZONE2區域的面積決定。如果ZONE2的區域面積是ZONE1的2倍，那么ZONE2應該有2個簇頭。每個區域中的簇頭數目為：

其中，N_Chi為區域ZONEi中的簇頭數目。在區域范圍內隨機選擇指定數目的簇頭，可使簇頭的分布更加均勻。

3 仿真實驗及分析

3.1 仿真模型

實驗中以NS-2 (Network SimulatorVersion-2) 作為仿真平臺[7]，版本為2.28。，目前LEACH原協議仿真代碼包mit.tar.gz可以從互聯網上獲得，腳本文件中對網絡的一些設置參數如表1所示[8]。

表1 仿真參數

為了簡化實驗進程，本仿真實驗進行的參數設定為：在100×100的方形區域內，隨機分布100個節點，Sink節點位于(15,15)處，數據包的大小為2 000 bit，簇頭的數據壓縮率為0.7，即有2 000 bit數據發送到簇頭，經簇頭處理之后，將1 400 bit傳給簇頭中繼。區域的半徑R設置為20 m。節點的初始能量為2J，數據融合消耗的能量為5 nJ/bit/message，傳輸的能量為50 nJ/bit。

3.2 性能指標

在實驗中，對于無線傳感器網絡的仿真，根據不同的要求需要不同的指標參數，改進的協議是以平衡所有節點總的能量消耗、延長網絡的存活時間為主要設計目標，因此，從以下2個指標衡量改進后協議的性能：

(1)節點總的消耗能量：不同時刻所有節點消耗能量的總和。

(2)網絡的存活時間：LEACH協議中假設節點不知其地理位置，且節點隨機部署，為保證采集數據的精確性，選擇從網絡開始運行到第1個死亡節點出現的時間為網絡的生存期(FND)。

3.3 仿真結果分析

圖2所示的是改進前后LEACH協議在生命期結束時的能量消耗，改進后協議的能量消耗比改進前的減少21.46%。

圖2 能量消耗對比

假設節點總能量的一部分專門為傳感器供能，考察傳感器耗能對改進前后協議運行的影響如圖3所示，考察指標為網絡的生存期，其中0代表不考慮傳感器耗能的情況。

圖3 網絡生存期對比

圖3顯示當傳感器耗能小于0.9 J(占總能量45%)時，協議的改進使網絡生存期增加明顯，0.9 J~1.2 J(占總能量60%)之間時生存期增加不多，而當傳感器耗能增加為總能量的60%以及更多時，協議的改進對網絡生存期的增加已經沒有效果。這說明單純從通信協議的角度為網絡節能是在傳感器耗能在一定范圍時才起作用的，因此，在實際應用中降低網絡的功耗還必須要結合所采用的傳感器的耗能情況來設計節能措施。

由實驗可知，無論是網絡的存活時間還是所有節點總的能量消耗，改進后的協議都優于原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] Heinzelman W R,Chandrakasan A,Balakrishnan H.Energy-efficient Communication Protocol for Wireless Microsensor Networks[C]//Proc.of HICSS’00.Los Alamitos,CA,USA:IEEE Press,2000.

[3] Mhater V,Rosenberg C.Homogeneous VS Heterogeneous Clustered Sensor Networks: A Comparative Study[C]//Proc.of IEEE Intel Conference on Communications.[S.l.]:IEEE Press,2004.

[4] Heinzelman W R,Chandrakasan A,Balakrishnan H. A application-specific protocol architecturefor wireless sensor networks [J]. IEEE Transactions on Wireless Communications, 2002,1(4):660-670.

[5] Zhou Z, Zhou S, Cui S,et al. Energy-efficient cooperative communication in a clustered wireless sensor network [J]. IEEE Transactions on Vehicular Technology, 2008,57(6):3618-3628.

[6] 樂世成,王培康.無線傳感器網絡中的節能路由算法[J].計算機工程,2008,34(7):113-117.

[7] 徐雷鳴,龐博,趙耀.NS與網絡模擬[M].北京:人民郵電出版社,2008.

[8] Varadhan F K.The NS Manual[Z].(2007-04-03).http:// www.isi.edunsnam/ns/ns-documentation.