馬紅艷，鄒學(xué)玉

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

對無線傳感器網(wǎng)絡(luò)的LEACH算法的改進研究

馬紅艷，鄒學(xué)玉

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

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

無線傳感器網(wǎng)絡(luò)；分層路由協(xié)議；LEACH協(xié)議算法；網(wǎng)絡(luò)生存時間

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

1 LEACH算法

1.1LEACH算法原理

圖1 分簇路由協(xié)議的數(shù)據(jù)傳輸流程簡圖

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

在數(shù)據(jù)傳輸階段，簇首在1幀內(nèi)收集簇內(nèi)所有活動節(jié)點的監(jiān)測數(shù)據(jù)，經(jīng)簇內(nèi)處理后轉(zhuǎn)發(fā)至BS節(jié)點，上述過程可重復(fù)多次，但若重復(fù)次數(shù)過多，通信協(xié)議將由動態(tài)分簇路由退化為靜態(tài)分簇路由，易于導(dǎo)致簇首節(jié)點能量過度消耗而死亡，因而在每1輪內(nèi)，簇首一般工作1～2個幀。

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

(1)

式中，p為網(wǎng)絡(luò)中簇首數(shù)量與節(jié)點總數(shù)的百分比；r為當(dāng)前選舉的輪數(shù)；G為最近1/p輪不是簇首的節(jié)點集。

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

在 LEACH的傳輸階段，傳感器節(jié)點將采集到的數(shù)據(jù)傳送到簇首節(jié)點。簇首節(jié)點對簇中所有節(jié)點采集的數(shù)據(jù)進行信息融合后再傳送給匯聚點，這是一種減小通信業(yè)務(wù)的合理模式。穩(wěn)定階段持續(xù)一段時間后，網(wǎng)絡(luò)重新進入簇的建立階段，進行下一回合的簇重構(gòu)，如此不斷循環(huán)。每個簇采用不同的CDMA代碼進行通信來減少其他簇內(nèi)節(jié)點的干擾。

1.2LEACH協(xié)議的網(wǎng)絡(luò)模型及數(shù)據(jù)傳輸

圖2 LEACH協(xié)議及改進后的數(shù)據(jù)傳輸圖

LEACH協(xié)議的網(wǎng)絡(luò)模型存在如下特點：①網(wǎng)絡(luò)中有固定基站(sink節(jié)點),其具有充足的能源，故研究中不考慮其能耗，且具傳感器節(jié)點均較遠。②網(wǎng)絡(luò)中所有傳感器節(jié)點同構(gòu)并具有相等的有限起始能量。③節(jié)點處于靜止?fàn)顟B(tài)且總有數(shù)據(jù)需要傳輸。④節(jié)點能改變發(fā)射功率并感知其剩余節(jié)點能量。

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

1.3LEACH算法的不足

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

2 對LEACH算法的改進

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

2.1簇首的選擇

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

(2)

式中，Ecurrent表示節(jié)點的當(dāng)前能量；Emax表示節(jié)點的初始能量；Nx表示節(jié)點在最近連續(xù)幾輪中未充當(dāng)簇首節(jié)點的次數(shù)；Nneighbor表示節(jié)點的鄰居節(jié)點的數(shù)目。

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

2.2簇間數(shù)據(jù)傳輸

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

傳感器節(jié)點總能量消耗E與距離d的關(guān)系為[8]：

E(d)=kdα+γ

(3)

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

圖3 簇首中繼節(jié)點選擇圖

由于傳感節(jié)點的能量消耗與通信距離成指數(shù)關(guān)系，當(dāng)中繼節(jié)點i(0

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

(4)

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

假設(shè)傳感器節(jié)點額外功率消耗γ相同，當(dāng)通過簇首i中繼通信后，簇首0的通信能耗為：

(5)

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

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

(6)

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

(7)

由此可得：

(8)

即：

E1(d1,c1)

(9)

圖4 中繼節(jié)點選擇流程圖

3 仿真試驗

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

圖5 簇首節(jié)點剩余能量比較圖 圖6 網(wǎng)絡(luò)生存時間比較圖

4 結(jié) 語

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

[1]于海斌，曾鵬.智能無線傳感器網(wǎng)絡(luò)系統(tǒng)[M].北京：科技出版社，2006.

[2] 李善倉，張克旺.無線傳感器網(wǎng)絡(luò)原理與應(yīng)用[M].北京：機械工業(yè)出版社，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] 顧明霞.無線傳感器網(wǎng)絡(luò)的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] 姜華，王沛.無線傳感網(wǎng)絡(luò)中的OPNET仿真模型的研究[J].計算機工程，2007，33(4)：73-78.

[編輯] 李啟棟

10.3969/j.issn.1673-1409.2011.08.030

TP751

A

1673-1409(2011)08-0094-04