對無線傳感器網絡的LEACH算法的改進研究

馬紅艷，鄒學玉

(長江大學電子信息學院，湖北 荊州 430023)

對無線傳感器網絡的LEACH算法的改進研究

馬紅艷，鄒學玉

(長江大學電子信息學院，湖北 荊州 430023)

無線傳感器網絡是一種能源受限網絡，因而降低能耗并提高網絡生存周期成為重要的研究目標。以分層路由協議LEACH為研究基礎，針對其不足，在簇首選舉、簇首對Sink節點的通信方式2方面進行改進，并利用 OPNET對LEACH算法及其改進算法進行仿真試驗。結果表明，改進算法有利于提高網絡性能，明顯延長網絡生存時間。

無線傳感器網絡；分層路由協議；LEACH協議算法；網絡生存時間

無線傳感器網絡(Wireless Sensor Networks,WSN)是由微電子機械系統、計算機、通信、自動控制和人工智能等技術發展起來的一種新型測控網絡，其具有自組織、自治、自適應等智能屬性，在軍事、醫療監測、空間探索等領域有廣泛用途[1]。無線傳感器網絡路由協議主要分為平面路由協議和分層路由協議。由于平面路由協議中網絡內各節點功能地位相同，沒有引入管理分層機制，其可擴張性小，缺乏對通信資源的優化管理，限制了網絡規模，而分層路由協議在一定程度上可解決上述問題[2]。低功耗自適應聚類路由協議LEACH是比較典型的分層路由算法，但其對簇首的選擇具有隨機性，而簇首對Sink節點采用單跳傳輸方式不能有效提高網絡生存時間[3]。為此，筆者對(Low Energy Adaptive Clustering Hierarchy，LEACH)算法進行改進以降低無線傳感器網絡功耗來延長其生命周期。

1 LEACH算法

1.1LEACH算法原理

圖1 分簇路由協議的數據傳輸流程簡圖

無線傳感器網絡的路由協議中，通常有不帶分簇的單跳路由和多跳路由協議、帶分簇的單跳路由和多跳路由協議[4-5]。在分簇路由通信協議中數據常按“輪”進行，每1輪可分2階段，即成簇階段和數據傳輸階段。圖1所示為LEACH分簇路由協議的簡單數據傳輸時間流程[6]。

在數據傳輸階段，簇首在1幀內收集簇內所有活動節點的監測數據，經簇內處理后轉發至BS節點，上述過程可重復多次，但若重復次數過多，通信協議將由動態分簇路由退化為靜態分簇路由，易于導致簇首節點能量過度消耗而死亡，因而在每1輪內，簇首一般工作1～2個幀。

在LEACH的成簇階段，簇首的選舉方法是每個傳感器節點隨機選擇0～1之間的一個值，如果選擇的值小于某個閾值T(n),那么該節點就成為簇首節點。T(n)的計算公式如下：

(1)

式中，p為網絡中簇首數量與節點總數的百分比；r為當前選舉的輪數；G為最近1/p輪不是簇首的節點集。

選定簇首節點后，通過廣播告知整個網絡。網絡中的其他節點根據接收信號的強弱決定從屬哪個簇，并通知相應的簇首節點，完成簇的建立。最后，簇首節點采用TDMA方法為簇中每個節點分配向其傳送數據的時間片。

在 LEACH的傳輸階段，傳感器節點將采集到的數據傳送到簇首節點。簇首節點對簇中所有節點采集的數據進行信息融合后再傳送給匯聚點，這是一種減小通信業務的合理模式。穩定階段持續一段時間后，網絡重新進入簇的建立階段，進行下一回合的簇重構，如此不斷循環。每個簇采用不同的CDMA代碼進行通信來減少其他簇內節點的干擾。

1.2LEACH協議的網絡模型及數據傳輸

圖2 LEACH協議及改進后的數據傳輸圖

LEACH協議的網絡模型存在如下特點：①網絡中有固定基站(sink節點),其具有充足的能源，故研究中不考慮其能耗，且具傳感器節點均較遠。②網絡中所有傳感器節點同構并具有相等的有限起始能量。③節點處于靜止狀態且總有數據需要傳輸。④節點能改變發射功率并感知其剩余節點能量。

LEACH協議數據傳輸如圖2(a)所示。由圖2(a)可知，從圖簇內節點通過一跳通信將數據傳送給簇首，簇首也通過一跳通信將聚合后的數據傳送給sink節點。

1.3LEACH算法的不足

LEACH以循環的方式隨機選取簇首，將整個網絡的能量負載平均分配到每個傳感器節點中，從而降低能源消耗，提高網絡整體生存時間。由于冗余數據被大量消除，因而在能耗方面有較好的性能。但LEACH仍有如下不足之處：①LEACH算法是由網絡中的節點自組織地形成簇，簇首是隨機產生的。由于簇首的選擇未考慮節點的剩余能量，周圍鄰節點數及已經擔任過簇首的次數會加重簇首負擔，使能耗不均。節點做簇首次數過多時，不但自身能耗大，而且會使離自身較遠的節點消耗較多能量，不利于節點能量的均衡和網絡壽命的延長。②簇首在傳輸數據時采用單跳傳輸方式，直接將數據包傳送給sink節點，距離sink較遠的簇首因此會消耗較大能量，部分簇首會過早死亡。

2 對LEACH算法的改進

針對LEACH算法的不足，可以在簇首選擇及簇間數據傳輸2方面進行改進(見圖2(b))，以平衡總的能量消耗來延長網絡生存壽命。

2.1簇首的選擇

由于LEACH的簇首競爭門限引起了區域性能量消耗不均衡等問題，因而可以充分考慮節點剩余能量、節點臨近數目(通信半徑內節點)及節點有未充當簇首的次數，根據文獻[7]，將式(1)改進如下：

(2)

式中，Ecurrent表示節點的當前能量；Emax表示節點的初始能量；Nx表示節點在最近連續幾輪中未充當簇首節點的次數；Nneighbor表示節點的鄰居節點的數目。

改進算法中除閾值算法不同外，簇首選擇的其他過程與LEACH算法相同。

2.2簇間數據傳輸

在進行簇間數據傳輸時，簇首收到所屬成員的傳感數據后先做初步的數據融合，然后將新的融合數據通過多跳算法發往基站。

傳感器節點總能量消耗E與距離d的關系為[8]：

E(d)=kdα+γ

(3)

式中，k=wΔt,w為系數常量，Δt為數據包發送的時間；γ為額外功率消耗，是不隨距離d變化的常數，在不依賴于距離變化的任何功率消耗都可以加到γ上去。

圖3 簇首中繼節點選擇圖

由于傳感節點的能量消耗與通信距離成指數關系，當中繼節點i(0

假設簇首與基站的傳輸距離小于自由空間傳播與多徑傳播的臨界距離，由式(3)可得簇首與基站直接通信的能耗：

(4)

式中，d0為簇首0到基站的距離。

假設傳感器節點額外功率消耗γ相同，當通過簇首i中繼通信后，簇首0的通信能耗為：

(5)

式中，ci為簇首節點0到簇首節點i的距離；di為簇首節點i到基站的距離。

由于能量消耗主要涉及無線通信鏈路，而γ在整個節點能耗中所占的比例很小，若忽略γ，則：

(6)

在圖3中，當中繼節點處于以基站和簇首節點0的連線為直徑的圓O上時，通過中繼節點消耗的能量等同于簇首節點直接傳輸的能量消耗。由平面幾何知識證明如下不等式成立，即：

(7)

由此可得：

(8)

即：

E1(d1,c1)

(9)

圖4 中繼節點選擇流程圖

3 仿真試驗

為了評價改進算法的性能，利用網絡仿真工具OPNET對相同狀態下的LEACH算法和改進算法在網絡生存時間方面進行仿真比較，使用的網絡模型配置如下，在200m×200m的平面區域使用500個無線傳感器節點和1個固定位置的sink節點，且sink節點遠離該感知區域。每個無線傳感器節點的初始能源為2J，數據包大小為500byte,元數據大小為25byte。簇首節點剩余能量比較圖如圖5所示。由圖5可知，在相同時間內使用改進算法的簇首能耗比使用LEACH算法的簇首能耗要低。網絡生存時間比較圖如圖6所示。由圖6可知，在簇首數相同時，使用改進算法的網絡生存時間比使用LEACH算法的網絡生存時間更長。

圖5 簇首節點剩余能量比較圖 圖6 網絡生存時間比較圖

4 結 語

闡述了LEACH算法的基本原理，針對該算法的不足，在簇首選擇及簇間數據傳輸2方面進行改進。改進簇首選擇機制可平衡節點的剩余能量，采用單跳與多跳相結合的簇間數據傳輸方式可平衡每個簇間的能量消耗。因此，對LEACH算法的改進有利于提高網絡性能，明顯延長網絡生存時間。

[1]于海斌，曾鵬.智能無線傳感器網絡系統[M].北京：科技出版社，2006.

[2] 李善倉，張克旺.無線傳感器網絡原理與應用[M].北京：機械工業出版社，2008.

[3] Heinzelman W,Chandrakasan A, Balakrishman H. An application-specific protocol architecture for wireless micro-sensor networks [J]. Wireless Communications,2002,1:660-670 .

[4] Kalaki J N,Kamal A E. Routing techniques in wireless sensor networks: A Survey [J]. Wireless communications 2004，11:6-28.

[5] Younis O, Fahmy S. HEED: A Hybrid, energy-efficient, distributed clustering approach for Ad Hoc sensor networks [J]. Transactions on mobile computing，2004，3:366-379.

[6] 顧明霞.無線傳感器網絡的LEACH算法改進與仿真研究[J].計算機仿真，2010,27(9)：139-185.

[7] Handy M J, Haase M D.Timmermann low energy adaptive clustering hierarchy with deterministic cluster-head selection[J]. Mobile and wireless communications networks,2002,9:368-372.

[8] 姜華，王沛.無線傳感網絡中的OPNET仿真模型的研究[J].計算機工程，2007，33(4)：73-78.

[編輯] 李啟棟

10.3969/j.issn.1673-1409.2011.08.030

TP751

A

1673-1409(2011)08-0094-04