LEACH協議分簇算法的改進及效能研究

陳 檳 萬 福 尹亞蘭

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

?

LEACH協議分簇算法的改進及效能研究

陳 檳 萬 福 尹亞蘭

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

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

低功耗自適應集簇分層型路由協議; 簇頭選舉; 剩余能量; 信任節點

Class Number TP301

1 引言

無線傳感器網絡(Wireless Sensor Network,WSN)綜合了傳感器技術、嵌入式計算技術以及通信技術等,能夠協作地實時監測、感知、采集網絡分布區域內各種環境或被監測對象的信息[5]。WSN不需要固定的網絡支持,具有快速展開、抗毀性強等優點,被廣泛地應用于國防軍事領域。

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

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

2 LEACH協議

LEACH協議是由Heinzelman提出應用于無線傳感網絡的第一個分簇算法。

協議中,簇頭節點需承受數據融合和轉發的雙重任務,能量負載較高,消耗較快。因此為了平衡網絡節點間的能耗,同時避免簇頭節點的過早死亡導致網絡拓撲結構變化,采用了以輪為單位的周期性選取簇頭的方法。

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

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

(1)

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

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

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

3 基于蟻群優化的LEACH改進算法

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

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

(2)

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

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

在數據傳輸階段,為了實現多跳通信,減少遠離基站的簇頭能量消耗,使用蟻群優化去發現簇間的最優路徑。簇頭通過最優路徑去傳輸數據以此來減少能量消耗,延長網絡的生命周期。

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

LEACH算法中,剩余能量較少的節點也可能成為簇頭節點,這類節點一旦成為簇頭,能量會很快耗盡,局部網絡將會出現簇頭過早死亡的情況,造成網絡空洞。

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

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

(3)

其中r為當前的輪數,n為網絡預計要運行的輪數,En_max為節點的初始能量。

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

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

5 基于節點信任的LEACH改進算法

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

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

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

Ti=W1Ci+W2Di+W3Ei

(4)

其中,W1、W2、W3分別為通信信任、數據信任和能量信任的權重,其值應根據實際應用選取。

6 仿真分析

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

仿真結果如圖1所示。

圖1 仿真結果

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

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

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

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

7 結語

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

[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] 金光,江先亮.無線網絡技術教程——原理、應用于仿真實驗[M].北京:清華大學出版社,2011.

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

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

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

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

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

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

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

[13] 董慧慧,郭亞軍.一種基于節點多角度信任的無線傳感器網絡[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日 作者簡介:陳檳,男,碩士研究生,研究方向:數據鏈。萬福,男,副教授,碩士生導師,研究方向:信息理論與技術。尹亞蘭,女,副教授,碩士生導師,研究方向:數據鏈。

TP301

10.3969/j.issn1672-9730.2015.07.013