LEACH協(xié)議分簇算法的改進及效能研究

陳 檳 萬 福 尹亞蘭

(海軍指揮學院信息戰(zhàn)研究系 南京 211800)

?

LEACH協(xié)議分簇算法的改進及效能研究

陳 檳 萬 福 尹亞蘭

(海軍指揮學院信息戰(zhàn)研究系 南京 211800)

分析傳統(tǒng)的LEACH協(xié)議,針對其不足,研究了三種比較典型的簇頭選舉算法,分別基于空間位置、剩余能量和信任節(jié)點對LEACH協(xié)議進行了改進,一定程度上解決了LEACH協(xié)議存在的簇頭分布不均勻、網(wǎng)絡(luò)能量不均衡及網(wǎng)絡(luò)安全保障不可靠等問題。

低功耗自適應(yīng)集簇分層型路由協(xié)議; 簇頭選舉; 剩余能量; 信任節(jié)點

Class Number TP301

1 引言

無線傳感器網(wǎng)絡(luò)(Wireless Sensor Network,WSN)綜合了傳感器技術(shù)、嵌入式計算技術(shù)以及通信技術(shù)等,能夠協(xié)作地實時監(jiān)測、感知、采集網(wǎng)絡(luò)分布區(qū)域內(nèi)各種環(huán)境或被監(jiān)測對象的信息[5]。WSN不需要固定的網(wǎng)絡(luò)支持,具有快速展開、抗毀性強等優(yōu)點,被廣泛地應(yīng)用于國防軍事領(lǐng)域。

然而傳感器節(jié)點由電池供電,且分布區(qū)域復雜、廣闊,難以用更換電池的方式來補充能量,所以節(jié)能問題現(xiàn)已成為國內(nèi)外專家和學者研究的重點。WSN的分簇結(jié)構(gòu)中,每個簇由一個簇頭和多個簇成員組成,簇頭間形成更高一級的網(wǎng)絡(luò),數(shù)據(jù)融合在簇頭中進行,減少了傳輸?shù)臄?shù)據(jù)量,由于簇頭可隨時選舉產(chǎn)生,所以網(wǎng)絡(luò)抗毀性也更強。如何合理選舉簇頭對延長網(wǎng)絡(luò)生存期有著重要意義。

在所有分簇算法,Heinzelman等提出的低功耗自適應(yīng)集簇分層型(low energy adaptive clustering hierarch,LEACH)[1]路由協(xié)議最具代表性。文章首先分析LEACH協(xié)議,然后對目前典型的幾種LEACH改進算法進行了研究及仿真。

2 LEACH協(xié)議

LEACH協(xié)議是由Heinzelman提出應(yīng)用于無線傳感網(wǎng)絡(luò)的第一個分簇算法。

協(xié)議中,簇頭節(jié)點需承受數(shù)據(jù)融合和轉(zhuǎn)發(fā)的雙重任務(wù),能量負載較高,消耗較快。因此為了平衡網(wǎng)絡(luò)節(jié)點間的能耗,同時避免簇頭節(jié)點的過早死亡導致網(wǎng)絡(luò)拓撲結(jié)構(gòu)變化,采用了以輪為單位的周期性選取簇頭的方法。

在簇建立階段,各節(jié)點獨立進行簇頭選舉算法以確定自己是否成為簇頭節(jié)點。成為簇頭的節(jié)點向周圍節(jié)點廣播信息,其他非簇頭節(jié)點根據(jù)接收到的廣播信息的強度來選擇它所要加入的簇,并告知相應(yīng)的簇頭。在穩(wěn)定數(shù)據(jù)傳輸階段,簇成員周期性地采集數(shù)據(jù),基于時分復用(Time Dirision Multiple Access,TDMA)方式將數(shù)據(jù)發(fā)送給簇頭節(jié)點,簇頭節(jié)點在收集到所有簇成員發(fā)來的數(shù)據(jù)后,對收集到的數(shù)據(jù)進行融合,最后把結(jié)果以單跳通信方式發(fā)送給匯聚節(jié)點。簇頭節(jié)點需要完成數(shù)據(jù)融合、與匯聚節(jié)點通信等任務(wù),能量消耗較大。因此,每輪結(jié)束后都要按照上述的方法重新選擇簇頭,將整個網(wǎng)絡(luò)的能量負載平均分配到每個傳感器節(jié)點上,從而達到降低能量消耗、提高網(wǎng)絡(luò)生存時間的目的。

選舉時,節(jié)點產(chǎn)生一個0～1之間的隨機數(shù),與事先定義好的閾值T(n)進行比較,若隨機數(shù)小于閾值,則判斷為簇頭節(jié)點,T(n)的公式[2]為

(1)

其中,p是網(wǎng)絡(luò)中簇頭節(jié)點的比例;r為當前輪數(shù);G是在最近1/p輪中沒有當選過簇頭的節(jié)點集合;n是指傳感節(jié)點的數(shù)量。這樣能保證在1/p輪中所有節(jié)點會且僅會當選簇頭節(jié)點一次。

該算法確實延長了網(wǎng)絡(luò)的生命周期,不過,LEACH算法也存在一些缺點:可能會出現(xiàn)部分簇頭相距過近或部分區(qū)域的節(jié)點離簇頭太遠的情況,大大增加了節(jié)點的傳輸能耗;簇頭節(jié)點隨機產(chǎn)生,可能導致一小部分簇頭節(jié)點的負擔過重,引起該節(jié)點的能量過早耗盡;沒有考慮節(jié)點的信任值,因而無法避免惡意節(jié)點當選為簇頭節(jié)點,從而對WSN的安全構(gòu)成威脅等。

針對以上問題,國內(nèi)外專家學者提出了眾多LEACH算法的改進方案,下面研究其中幾種典型方案。

3 基于蟻群優(yōu)化的LEACH改進算法

為了解決簇頭節(jié)點分布不均勻問題,岳麗穎等提出了一種基于蟻群優(yōu)化的改進LEACH協(xié)議[6],改進后的算法也分為兩個階段:簇的形成階段和穩(wěn)定的數(shù)據(jù)傳輸階段。

為了使簇頭節(jié)點分布盡量均勻,引入一個量值d,兩個簇頭節(jié)點之間的距離不能小于該值,d的計算公式如式(2):

(2)

其中,x、y分別是傳感器網(wǎng)絡(luò)區(qū)域的長和寬,π的值是3.14,k是傳感器網(wǎng)絡(luò)簇頭節(jié)點的數(shù)目,α是在(1,2)之間的常數(shù),這里把它的值選為1.7。

在簇形成階段,節(jié)點先產(chǎn)生一個隨機時間t,來取代LEACH協(xié)議中的隨機數(shù)。每個節(jié)點內(nèi)部都有一個定時時鐘,當該時鐘到達時間t時,將會判斷該節(jié)點是否當選過簇頭。如果它之前當選過簇頭,就不再參與簇頭節(jié)點的競爭;如果沒有當選過,它將會判斷接收到的簇頭廣播消息的數(shù)量是否小于k,如果不小于k,則說明簇頭數(shù)量已滿,在該輪它將不能成為簇頭節(jié)點,否則,將判斷它到現(xiàn)存其他簇頭節(jié)點之間的距離是否大于d。在簇頭選擇過程中,簇頭節(jié)點將會向網(wǎng)絡(luò)中其他節(jié)點廣播它成為簇頭節(jié)點的消息,其他節(jié)點接收到該廣播消息后,將會根據(jù)該消息的信號強度計算其到簇頭之間的距離,并記錄其最小值。如果該最小值比d大,該節(jié)點將會成為簇頭,否則就成為普通節(jié)點。簇頭確定以后,其他節(jié)點根據(jù)接收到的信號強度來決定從屬的簇,并且通知相應(yīng)的簇頭。這樣簇就形成了。

在數(shù)據(jù)傳輸階段,為了實現(xiàn)多跳通信,減少遠離基站的簇頭能量消耗,使用蟻群優(yōu)化去發(fā)現(xiàn)簇間的最優(yōu)路徑。簇頭通過最優(yōu)路徑去傳輸數(shù)據(jù)以此來減少能量消耗,延長網(wǎng)絡(luò)的生命周期。

4 基于剩余能量的LEACH改進算法

LEACH算法中,剩余能量較少的節(jié)點也可能成為簇頭節(jié)點,這類節(jié)點一旦成為簇頭,能量會很快耗盡,局部網(wǎng)絡(luò)將會出現(xiàn)簇頭過早死亡的情況,造成網(wǎng)絡(luò)空洞。

增加能量閾值這一約束條件可解決該問題。改進算法分為簇頭粗選和簇頭調(diào)整兩個階段。

粗選階段,網(wǎng)絡(luò)中各節(jié)點能量先與能量閾值Eth進行比較,當節(jié)點的剩余能量大于能量閾值時,該節(jié)點當選為候選簇頭,能量閾值的計算公式[7]如式(3):

(3)

其中r為當前的輪數(shù),n為網(wǎng)絡(luò)預計要運行的輪數(shù),En_max為節(jié)點的初始能量。

接著就是簇頭調(diào)整過程,候選簇頭向其通信范圍內(nèi)的其他節(jié)點發(fā)送廣播,廣播中包含著該候選簇頭的剩余能量和ID號等信息,每個侯選簇頭節(jié)點根據(jù)收到的廣播報文構(gòu)建自己的鄰居簇頭表,該表包括鄰居節(jié)點ID、鄰居節(jié)點剩余能量、被選作為簇頭的次數(shù)、是否是鄰居節(jié)點四個數(shù)據(jù)。最后通過比較每個候選簇頭的權(quán)重,選擇權(quán)重最大的當選簇頭。非簇頭節(jié)點則根據(jù)周圍簇頭節(jié)點的權(quán)重,選出權(quán)重最大的作為自己的簇頭。

此過程中,通過引入能量閾值,有效地防止了能量低的節(jié)點成為簇頭,避免了因為簇頭死亡造成的數(shù)據(jù)丟失以及網(wǎng)絡(luò)空洞,使網(wǎng)絡(luò)能量得到均衡的利用,顯著地延長了網(wǎng)絡(luò)的生命周期。

5 基于節(jié)點信任的LEACH改進算法

LEACH協(xié)議沒有考慮節(jié)點的信任值,因而無法避免惡意節(jié)點當選為簇頭節(jié)點,從而對WSN的安全構(gòu)成威脅。加入信任值計算來改進LEACH算法能有效改善此問題,思路如下:

首先根據(jù)LEACH協(xié)議進行第一輪簇頭選舉,簇內(nèi)各節(jié)點根據(jù)自身作為計算各自的信任值,在第一輪周期結(jié)束時,各節(jié)點將信任值和ID號發(fā)送給簇頭節(jié)點,簇頭節(jié)點收集各節(jié)點所發(fā)信息匯總后一起發(fā)給基站,然后基站計算各節(jié)點本輪的信任值和上輪信任值的差值,當差值達到一定程度時,判斷該節(jié)點是惡意節(jié)點,將其從網(wǎng)絡(luò)中剔除,剩余的節(jié)點再根據(jù)LEACH協(xié)議選取簇頭,這樣就避免了惡意節(jié)點的影響。

信任值的計算可從三方面考慮:節(jié)點的通信信任、數(shù)據(jù)信任及能量信任。分別計算節(jié)點i的通信信任值Ci、數(shù)據(jù)信任值Di和能量信任值Ei,其中能量信任值是考慮節(jié)點剩余能量得出的一個參數(shù)。然后計算節(jié)點的綜合信任值Ti[9],計算公式如式(4):

Ti=W1Ci+W2Di+W3Ei

(4)

其中,W1、W2、W3分別為通信信任、數(shù)據(jù)信任和能量信任的權(quán)重,其值應(yīng)根據(jù)實際應(yīng)用選取。

6 仿真分析

用Matlab進行仿真,分析各算法延長網(wǎng)絡(luò)壽命的效能。網(wǎng)絡(luò)節(jié)點數(shù)設(shè)置為100個,隨機分布在100*100的區(qū)域內(nèi),基站節(jié)點設(shè)置在(100,100)的位置,節(jié)點一旦分布就不再移動。節(jié)點初始能量為2J,發(fā)送和接收數(shù)據(jù)的能量損耗為50nJ/bit,數(shù)據(jù)融合的能耗為5nJ/bit,數(shù)據(jù)包的大小為2000bit,若節(jié)點能量降為0則宣布該節(jié)點死亡。綜合信任值計算中的各信任值權(quán)重均等。簇頭節(jié)點占5%,網(wǎng)絡(luò)最大運行輪數(shù)為600輪,每隔20輪取統(tǒng)計一次剩余節(jié)點數(shù)。

仿真結(jié)果如圖1所示。

圖1 仿真結(jié)果

仿真結(jié)果圖顯示了本文四種算法隨著網(wǎng)絡(luò)運行輪數(shù)(時間)的變化,節(jié)點的剩余情況。

LEACH算法在第120輪開始出現(xiàn)節(jié)點的死亡,而蟻群優(yōu)化算法和剩余能量算法分別在第200輪和第260輪才出現(xiàn)節(jié)點的損失。設(shè)50%及以上節(jié)點存活,網(wǎng)絡(luò)才可以正常運行,蟻群優(yōu)化算法和剩余能量算法的正常運行輪數(shù)分別比LEACH算法高了44%和62%。再看網(wǎng)絡(luò)壽命,即節(jié)點全部死亡的運行輪數(shù),蟻群優(yōu)化算法是480輪,剩余能量優(yōu)化是440輪,也分別高出了未改進算法20%和16%。

這兩種改進算法分別將節(jié)點剩余能量和節(jié)點分布作為選舉簇頭的考慮因素,均衡了網(wǎng)絡(luò)中的能量分布,從而延長了網(wǎng)絡(luò)壽命和正常工作時間。選取剩余能量大的節(jié)點當選簇頭,使得節(jié)點死亡時間大大推遲。但是剩余能量優(yōu)化算法在簇頭調(diào)整過程中,節(jié)點建立的鄰居簇頭表含組組數(shù)據(jù)信息,節(jié)點間的通信量為蟻群優(yōu)化算法的四倍,造成額外的能量消耗,而蟻群優(yōu)化利用多跳路由來傳輸數(shù)據(jù),每次傳輸距離相對較短,能量消耗也較小,所以從蟻群優(yōu)化算法的網(wǎng)絡(luò)壽命更長,高出剩余能量優(yōu)化9%。

基于信任節(jié)點的算法從第80輪開始就有節(jié)點損失,早于未改進的算法,這是在算法執(zhí)行過程中發(fā)現(xiàn)了不可信任的節(jié)點并將其及時剔除出網(wǎng)絡(luò)的結(jié)果。另外算法中也考慮了剩余能量的因素,盡管由于不可信節(jié)點在前期的逐漸剔除,網(wǎng)絡(luò)正常工作時間是幾種算法中最短的,但其網(wǎng)絡(luò)壽命較未改進算法也有10%的提升。不過它對網(wǎng)絡(luò)的最大幫助還是通信質(zhì)量及數(shù)據(jù)可信度上的顯著提高。可根據(jù)具體案例的要求來調(diào)整各參數(shù)的權(quán)重,比如在已知通信質(zhì)量較高、無其他數(shù)據(jù)干擾的網(wǎng)絡(luò)中可適當提高能量信任值的比重。

7 結(jié)語

本文對LEACH協(xié)議進行了分析,并研究了幾種該協(xié)議的改進算法,闡述了它們各自的特點和約束條件,最后仿真比較得出了各算法對原協(xié)議的改進效果。總之,無線傳感器網(wǎng)絡(luò)由于它的諸多優(yōu)點,在軍事上的應(yīng)用將會日益廣泛,但是如何解決它存在的一些技術(shù)問題,將值得人們繼續(xù)深入研究。

[1] Heinzalman WR, Chandrakasan A, Balakrishman H. An Application-Specific Protocol Architecture for Wireless Microsensor Networks[J]. IEEE Transactions on Wireless Communications,2002,1(4):660-670.

[2] Heinzelman WR, Chandrakasan A, Balakrisham H. Energy-efficient Communication Protocol for Wireless Microsensor Networks[C]//Proceeding of the 33rdAnnual Hawaii Intl Conf. on System Sciences. Maui: Ieee Computer Society,2000:3005-3014.

[3] Heinzalman WR, Kulik J, Balakrishman H. Adaptive Protocols for Information Dissemination in Wireless Sensor Networking[M]. New York, USA: ACM press,2001:174-185.

[4] Hewish M. Little brother is watching you: unattended groundsensors[J]. Defense Review,2001,34(6):46-52.

[5] 金光,江先亮.無線網(wǎng)絡(luò)技術(shù)教程——原理、應(yīng)用于仿真實驗[M].北京:清華大學出版社,2011.

[6] 岳麗穎,戴明月.一種基于蟻群優(yōu)化的分簇路由算法[J].信息技術(shù),2014,2(1):60-72.

[7] 王偉超,代增全,徐啟建.LEACH協(xié)議簇頭選擇算法的改進[J].無線電工程,2010,40(3):1-3.

[8] 周治平,王亭,張明亮.傳感器網(wǎng)絡(luò)中一種能量有效的簇頭選擇機制[J].計算機工程與應(yīng)用,2012,48(8):105-108.

[9] 白林林,嚴斌宇,羅敬文,等.基于節(jié)點信任的LEACH協(xié)議簇頭選舉改進算法[J].四川大學學報(工程科學版),2012,44(6):219-223.

[10] 張浩,李臘元.基于LEACH協(xié)議的能耗均衡路由算法[J].計算機工程,2014,37(7):91-111.

[11] 王偉龍,馬滿福.基于信任機制的一種無線傳感器網(wǎng)絡(luò)簇頭選舉算法[J].計算機應(yīng)用,2012,32(10):2696-2699.

[12] 李輝,彭珍瑞,蕫海棠.一種LEACH協(xié)議的改進方法[J].電子科技,2014,27(5):172-178.

[13] 董慧慧,郭亞軍.一種基于節(jié)點多角度信任的無線傳感器網(wǎng)絡(luò)[J].計算機科學,2009,36(9):43-45.

Improvement and Efficiency Research of LEACH Protocol Distribution Clustering Algorithm

CHEN Bin WAN Fu YIN Yalan

(Department of Information Warfare, Navy Command College, Nanjing 211800)

Traditional LEACH is analyzed. In views of its shortcomings, three typical cluster head election algorithms are studied. LEACH protocol is improved based on the spatial position, the residual energy and the trust node, also problems occurring in LEACH protocol such as uneven distribution of head nodes, imbalance of network energy and unreliability of network security are solved.

LEACH protocol, the choice of cluster head election, residual energy, trust node

2015年1月7日,

2015年2月26日 作者簡介:陳檳,男,碩士研究生,研究方向:數(shù)據(jù)鏈。萬福,男,副教授,碩士生導師,研究方向:信息理論與技術(shù)。尹亞蘭,女,副教授,碩士生導師,研究方向:數(shù)據(jù)鏈。

TP301

10.3969/j.issn1672-9730.2015.07.013