陳 檳 萬 福 尹亞蘭

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

?

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

陳 檳 萬 福 尹亞蘭

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

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

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

Class Number TP301

1 引言

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

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

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

2 LEACH協(xié)議

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

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

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

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

(1)

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

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

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

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

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

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

(2)

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

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

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

4 基于剩余能量的LEACH改進(jìn)算法

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

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

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

(3)

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

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

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

5 基于節(jié)點(diǎn)信任的LEACH改進(jìn)算法

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

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

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

Ti=W1Ci+W2Di+W3Ei

(4)

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

6 仿真分析

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

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

圖1 仿真結(jié)果

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

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

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

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

7 結(jié)語

本文對LEACH協(xié)議進(jìn)行了分析,并研究了幾種該協(xié)議的改進(jìn)算法,闡述了它們各自的特點(diǎn)和約束條件,最后仿真比較得出了各算法對原協(xié)議的改進(jìn)效果。總之,無線傳感器網(wǎng)絡(luò)由于它的諸多優(yōu)點(diǎn),在軍事上的應(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)用于仿真實(shí)驗(yàn)[M].北京:清華大學(xué)出版社,2011.

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

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

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

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

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

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

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

[13] 董慧慧,郭亞軍.一種基于節(jié)點(diǎn)多角度信任的無線傳感器網(wǎng)絡(luò)[J].計(jì)算機(jī)科學(xué),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ù)鏈。萬福,男,副教授,碩士生導(dǎo)師,研究方向:信息理論與技術(shù)。尹亞蘭,女,副教授,碩士生導(dǎo)師,研究方向:數(shù)據(jù)鏈。

TP301

10.3969/j.issn1672-9730.2015.07.013