無線傳感器網絡LEACH路由協議的改進算法

周志強 劉森 王允臣

摘 要:針對無線傳感器網絡簇頭節點選取難、網絡生存周期短、能量消耗大等問題,本文在傳統的LEACH算法基礎上,設計了E-LEACH算法,E-LEACH算法引入了能量閾值的概念。能量閾值是判斷該節點是否可以作為簇頭節點的先決條件,同時引入距離因子的概念,在每輪選取簇頭時,都會考慮到和基站的距離。仿真實驗表明,該算法有效的降低了網絡能耗,延長了節點的生命時間。

關鍵詞:無線傳感器網絡LEACH節點生存周期能量

中圖分類號:TP3 文獻標識碼:A 文章編號:1672-3791(2012)06(b)-0015-02

近年來,由于無線技術、計算機技術與傳感器技術的迅猛發展和快速融合,無線傳感器網絡應運而生。無線傳感器網絡技術作為一種新型網絡技術受到研究者的普遍重視和廣泛研究[1]。

但傳感器網絡也有一些固有的缺點如:能量利用率低、生存周期短、抗干擾能力差。而通過良好的分簇算法不僅可以減少傳感器節點的能耗,還可以降低通訊干擾、提高MAC協議和路由協議的效率。因此,提出一個高效穩定合理的算法便成為迫切需要解決的問題[2]。本文在LEACH算法的基礎上,綜合考慮了各個節點的剩余能量,提出了一種更為高效、更為合理的低開銷自適應分層的E-LEACH算法。

1LEACH算法分析

LEACH協議是由Wendi等人提出的,其基本思想是:提出了“輪(round)”的概念,通過每一輪的循環隨機選擇簇頭節點,然后再對簇頭節點進行輪換,從而達到平衡和降低能耗、延長網絡的生存周期的目的。在LEACH協議中,每一輪由兩部分構成。第一部分是構建簇階段,第二部分為穩定工作階段。

在實際的無線傳感器網絡中,經過多輪選舉后,各個節點的剩余能量將會有很大的不同,靠近簇頭的節點剩余的能量多,而遠離簇頭的節點剩余的能量少。但是在傳統的LEACH算法中,所有的節點成為簇首節點的概率是相同的。因此,若在以后的多輪數據傳播中都選取遠離基站的節點做簇頭,則該節點的能量將很快被耗盡,最終成為失效節點。過多的失效節點將導致整個網絡的癱瘓。

另外,在傳統的LEACH算法中,每一輪的初始化階段,節點根據接收到簇頭節的廣播信號的強弱,選擇要加入的簇。但是,這種方案不一定是最優的方案。A、B、C為選擇出來的簇首節點,D為基站,E為非簇首節點。顯然節點E距離A、C的距離均比距離B的距離近,但若E要將數據傳到基站D,最優的簇頭卻應選B。因為不論是選C還是選A,整個網絡消耗的能量都大于B路徑。

2LEACH改進算法

針對LEACH算法的不足之處,本文設計了E-LEACH算法,在很大程度上解決了上述問題。E-LEACH算法構建簇時經過了兩次選擇。第一次選擇選出符合能量條件和距離極小條件的節點集合,第二次選擇才是真正的簇頭選擇階段,在該集合中隨機選出符合要求的簇頭節點。

首先,E-LEACH算法引入了能量閾值的概念。能量閾值是判斷該節點是否可以作為簇頭節點的先決條件。能量閾值的計算公式:

(1)

式中E(r)為第r輪的能量閾值,K為能量閾值因子,p為期望的簇頭節點占所有有效節點的百分比,Er為第r輪循環網絡中隨機選取的有效節點的能量總和,m為第r輪中簇頭節點總數。在每一輪簇頭選擇前,將每個符合簇頭條件的節點能量與能量閾值相比,若節點能量小于能量閾值則將該節點從簇頭候選節點中剔除[3～5]。

其次,E-LEACH算法引入了距離因子:

(2)

其中d m為監測區內節點到基站的最大距離,d(i)為節點i到基站的距離。有了距離因子,在每輪選取簇頭節點將數據向基站傳送時,都會考慮距離代價。從而選擇出數據傳輸距離最小的路徑。

經過第一次的選擇,我們可以得到一個簇頭候選集合Q。

(3)

Q是在1/p輪中未成為簇頭并且能量大于能量閾值的節點集合。非簇頭節點選擇加入簇時,也會參照能量閾值及距離因子,選出能量損耗最小的傳輸路徑[6]。

4仿真與實驗分析

本方案使用MATLAB仿真。在仿真時K取0.75,傳感器節點隨機的分布在1000×1000的平面區域內。傳感器節點數為1000個,各個節點初始能量為3J,基站坐標為(50,750),數據包大小為20bytes。LEACH算法與E-LEACH算法存活節點的數量隨時間的變化情況。LEACH算法與E-LEACH算法傳輸數據量與能耗的關系。

由此次實驗的仿真可以看出在初始節點數相同條件下,隨時間的推移,采用LEACH算法的無線傳感器網絡節點存活數明顯低于采用E-LEACH算法的無線傳感器網絡。而且在傳送相同數據量的條件下,E-LEACH算法消耗的能量要更少。

5結語

本文以傳統的LEACH算法為基礎,考慮了每一輪中各個節點剩余能量不一致問題,以及所選路徑并非最節能路徑的問題。提出了能量閾值及距離因子的概念,通過能量閾值及距離因子確定優選簇頭集合,再在此基礎上選擇出簇頭節點。通過這種簇頭選擇優化算法,實現了延長網絡生存周期,提高節點能量利用率的目的。

參考文獻

[1] AKYILDIZ I F,WEILIANS, SANKARASUBRAMANIAMY.A survey on sensor networks [J]. IEEE Communications Magazine,2002.

[2] Akkaya K,Younis M.Asurvey on routing protocols for wirelesssensor networks[J].AdHocNetworks,2005.

[3] 孫利民,李建中,陳渝,等.無線傳感器網絡[M].清華大學出版社,2005.

[4] 江冰,吳元忠,謝冬梅.無線傳感器網絡節點自定位算法的研究[J].傳感技術學報,2007.

[5] SICHITIU M L.Cross-layer scheduling for power efficiency in wire-less sensor networks[A].Proceedings of IEEE INFOCOM 2004[C].Hong Kong, China,2004.

[6] 葉馳,孫利民,廖勇.傳感器網絡的能量管理[J].計算機工程與應用,2004.