一種基于LEACH的無線傳感器網(wǎng)絡(luò)路由算法及仿真

蘇儉華,劉宇紅,徐躍州

(貴州大學電子信息學院,貴州貴陽550025)

一種基于LEACH的無線傳感器網(wǎng)絡(luò)路由算法及仿真

蘇儉華,劉宇紅,徐躍州

(貴州大學電子信息學院,貴州貴陽550025)

在低功耗自適應(yīng)分簇(LEACH,Low Energy Adaptive Clustering Hierarch)算法中,由于每一輪循環(huán)都要重新構(gòu)造簇,距離較遠的簇頭節(jié)點可能會因長距離發(fā)送數(shù)據(jù)而過早耗盡自身能量,能量較低的節(jié)點當選為簇頭節(jié)點時將會加速該節(jié)點的死亡,影響整個網(wǎng)絡(luò)的生命周期。針對LEACH算法分簇機制中存在的不足,提出了一種改進的路由算法。仿真結(jié)果表明,改進算法通過考慮節(jié)點的剩余能量與固定分簇的方法,有效的改善了網(wǎng)絡(luò)能量均衡,提高了網(wǎng)絡(luò)生存時間。

無線傳感器網(wǎng)絡(luò) 分簇路由算法 網(wǎng)絡(luò)生存時間

0 引 言

無線傳感器網(wǎng)絡(luò)[1-3](WSN)是一種低功耗、低成本、低速率的無線通信網(wǎng)絡(luò),它由眾多傳感器節(jié)點以自組織方式組成,借助節(jié)點內(nèi)置的傳感器測量采集所在周邊環(huán)境中我們感興趣的物質(zhì)現(xiàn)象的信息。并通過數(shù)據(jù)處理單元對采集信息進行處理,獲得詳盡準確的信息,最后將這些信息發(fā)送到需要它們的處理節(jié)點。用戶通過終端的管理和分析軟件來觀測網(wǎng)絡(luò)的運行狀況,并且可以對網(wǎng)絡(luò)中的各個節(jié)點進行管理和監(jiān)控。

根據(jù)無線傳感器網(wǎng)絡(luò)自身的優(yōu)勢和特點,它在惡劣環(huán)境、無人區(qū)、資源受限等場景中具有得天獨厚的應(yīng)用價值,能夠客觀有效的獲取物理信息,具有十分廣闊的應(yīng)用前景,可應(yīng)用于軍事國防、工農(nóng)業(yè)控制、目標跟蹤、智能家居、醫(yī)療健康、環(huán)境監(jiān)測、防恐反恐、危險區(qū)域遠程控制等諸多領(lǐng)域[4]。由于無線傳感器網(wǎng)絡(luò)節(jié)點的能力限制,以及節(jié)點能量無法補給的特點,因此設(shè)計一套有效的路由算法來提高能量效率是十分重要的[5]。

從網(wǎng)絡(luò)邏輯結(jié)構(gòu)角度可以將無線傳感器網(wǎng)絡(luò)路由算法分為平面路由和分簇路由。鑒于分簇路由算法具有良好的可擴展性,適用于大規(guī)模的WSN中,現(xiàn)研究主要重點集中在分簇路由算法上,而低功耗自適應(yīng)分簇(LEACH)算法是比較成熟且具有代表性的層次路由算法。分簇路由算法中簇頭節(jié)點的產(chǎn)生方式一直是人們研究的重點和熱點,其中典型的有集中控制類算法LEACH-C[6],基本思想是全網(wǎng)節(jié)點直接與基站進行信息交互,基站根據(jù)得到的各個節(jié)點信息,然后結(jié)合全局信息來選擇最優(yōu)的簇頭節(jié)點,但是由于各個節(jié)點每次都要與基站進行交互,這樣額外增加了不少能量消耗;在文獻[7]中李成岳等人提出的LEACH-T算法則是將簇頭的產(chǎn)生依靠定時器產(chǎn)生一個隨機時間間隔,擁有最短的時間間隔的節(jié)點將有更大概率成為簇頭節(jié)點,該算法還將每輪簇頭的個數(shù)固定在最優(yōu)簇頭數(shù),有效的均衡了整個網(wǎng)絡(luò)的能量,但是由于加入一個定時器,每輪簇頭競選時定時器產(chǎn)生的能耗也不容忽視且在硬件上實現(xiàn)增加了工藝的復雜性。

1 LEACH算法概述

LEACH[8](Low Energy Adaptive Clustering Hierarchy)算法是由MIT的Heinzelman等人提出的,它是一種為無線傳感器網(wǎng)絡(luò)設(shè)計的低功耗自適應(yīng)聚類路由協(xié)議,是一種典型的層次路由協(xié)議。LEACH算法的基本思想是:減少與基站直接通信的節(jié)點個數(shù),等概率隨機性周期地選取網(wǎng)絡(luò)的簇頭節(jié)點,將整個網(wǎng)絡(luò)的能耗均衡到各個節(jié)點上去,以此來降低全網(wǎng)的能耗,達到延長網(wǎng)絡(luò)生存時間的目的。仿真表明, LEACH算法相較于一般的平面多跳路由協(xié)議,將網(wǎng)絡(luò)生命周期提高了15%。

LEACH算法提出‘輪'的概念來描述簇的建立過程。每輪分為兩個階段:簇的建立和穩(wěn)定傳輸階段,且穩(wěn)定傳輸階段的持續(xù)時間要大于簇的建立時間。簇的建立過程可以分為4個階段:簇頭節(jié)點的選擇、簇頭節(jié)點的廣播、簇頭節(jié)點的建立和調(diào)度機制的生成。

LEACH算法簇頭的選舉過程是:節(jié)點產(chǎn)生一個大于0小于1的隨機數(shù),如果這個隨機數(shù)小于設(shè)定的閾值T(n),那么這個節(jié)點成為簇頭階段。T(n)的計算公式如下:

其中:P是簇頭節(jié)點的百分比;r是已經(jīng)完成的輪數(shù);G是1/P輪中沒有成為簇頭的節(jié)點集合;mod是求模運算。

LEACH算法是讓網(wǎng)絡(luò)中的節(jié)點自組織地形成簇,簇頭是隨機產(chǎn)生的。由于簇頭的選擇沒有考慮剩余能量,若選擇剩余能量小的節(jié)點做為簇頭,則簇頭節(jié)點會過早的死亡,當簇頭節(jié)點失效時簇內(nèi)的節(jié)點就停止數(shù)據(jù)發(fā)送,直到下輪簇頭的重新選舉。簇頭節(jié)點的過早死亡,降低了網(wǎng)絡(luò)的生存時間,影響整個網(wǎng)絡(luò)性能。

2 改進算法

2.1 傳送節(jié)點的選擇

改進算法首先將目標區(qū)域以sink節(jié)點為圓心劃分為K個半徑為等差的子區(qū)域,然后將離sink節(jié)點最近的子區(qū)域標記為傳送區(qū)域,在該區(qū)域?qū)⑦x取一個節(jié)點作為傳送節(jié)點,在融合了各簇頭節(jié)點的數(shù)據(jù)后轉(zhuǎn)發(fā)給sink節(jié)點。傳送節(jié)點選擇條件為:Ds＜Do+,ΔS為等差半徑。

當傳送節(jié)點能量低于某一閾值時,重新選擇一個能量較高的節(jié)點作為傳送節(jié)點。一旦當選為傳送節(jié)點,該節(jié)點將不再參與競選簇頭節(jié)點以及不再申請加入到其他簇內(nèi),可避免數(shù)據(jù)重復傳送融合產(chǎn)生的能量開銷。

當簇頭節(jié)點離基站較遠時,要以較大的功率發(fā)送數(shù)據(jù),將導致簇頭節(jié)點能量快速消耗,不利于網(wǎng)絡(luò)能量的均衡。傳送節(jié)點的出現(xiàn)避免了簇頭節(jié)點直接與sink節(jié)點聯(lián)系,降低了簇頭節(jié)點過早死亡的概率,均衡了全網(wǎng)能量分布。

2.2 簇頭選舉

在選擇簇頭時,將節(jié)點的剩余能量和節(jié)點充當簇頭節(jié)點的次數(shù)綜合考慮進去。簇頭節(jié)點的選擇先從目標區(qū)域開始,隨著時間的推移簇頭選舉范圍以r為長度逐步往兩側(cè)擴展。x為目標ΔS區(qū)域的邊界長,n為等差半徑的子區(qū)域數(shù)。調(diào)整后簇頭閾值計算方法:

其中,P是節(jié)點成為簇頭節(jié)點的百分比;r是當前輪數(shù);G是節(jié)點落在區(qū)域內(nèi)過去1/P輪中沒有當選為簇頭節(jié)點的集合;Ec為當前節(jié)點剩余能量;E0為節(jié)點的初始能量,CH_Times為節(jié)點在以前回合中充當簇頭的次數(shù)。

2.3 簇的形成

當簇頭選定之后,簇頭采用非持續(xù)CSMA(Carrier-sense Multiple Access)MAC協(xié)議向全網(wǎng)廣播自己成為簇頭的消息。其他普通節(jié)點在接收到各簇頭的廣播消息后,根據(jù)接收到的消息強度來決定加入某個簇頭。并給簇頭發(fā)送一個請求加入消息,消息中包含節(jié)點自身ID和剩余能量以及簇頭ID號。簇頭根據(jù)接收到的請求加入消息確定簇成員數(shù),以此來為每個簇成員分配一個時隙,各成員節(jié)點只在相應(yīng)的時隙內(nèi)進行數(shù)據(jù)傳輸,在其他時間內(nèi)進入休眠狀態(tài),減少能量開銷。

2.4 數(shù)據(jù)傳輸

當簇形成后,節(jié)點將采集到的數(shù)據(jù)發(fā)送給簇頭,簇頭進行數(shù)據(jù)融合后再與傳送節(jié)點通信,而不是直接與sink節(jié)點進行通信。原因是在單跳的通信方式中,若簇頭距離sink節(jié)點過遠,則將損耗較大功率發(fā)送數(shù)據(jù)不利于簇頭的能量均衡。選擇距離較近的傳送節(jié)點轉(zhuǎn)發(fā)保存了簇頭的能量。

3 仿真結(jié)果分析

文中采用MATLAB軟件對LEACH算法及改進后的算法(LEACH-S)進行仿真、分析和比較。由于實際應(yīng)用環(huán)境中節(jié)點很難絕對平均分布,在此將選擇100個節(jié)點隨機分布于檢測區(qū)域中,節(jié)點分布圖如圖1所示,仿真環(huán)境參數(shù)設(shè)置如表1所示。

圖1 節(jié)點分布Fig.1 Node distribution

表1 仿真環(huán)境參數(shù)設(shè)置Table 1 Parameter settings of simulation environment

文中采用網(wǎng)絡(luò)存活節(jié)點數(shù)和剩余節(jié)點總能量兩個方面對比LEACH和新算法。為避免偶然性,對網(wǎng)絡(luò)仿真數(shù)據(jù)采用多次求平均的方法來繪制效果圖。網(wǎng)絡(luò)總能耗隨時間變化圖,如圖2所示。可以看出新算法的總能耗低于LEACH算法,這是由于優(yōu)化了簇頭的位置,采用了傳送節(jié)點來與基站發(fā)送數(shù)據(jù)的方式,有效的節(jié)省了簇頭的能量,均衡了全網(wǎng)的總能耗。

圖2 網(wǎng)絡(luò)節(jié)點剩余總能量隨工作輪數(shù)變化Fig.2 Total remaining energy of network nodes changing as the working rounds

如圖3所示,為網(wǎng)絡(luò)存活節(jié)點數(shù)隨時間變化圖。在仿真實驗中,若節(jié)點的剩余能量小于0則認為該節(jié)點死亡。據(jù)仿真結(jié)果,LEACH算法在612輪時第一個節(jié)點死亡,改進后的算法則是在940輪時出現(xiàn)節(jié)點死亡;比LEACH提高了53.6%。

圖3 節(jié)點存活個數(shù)隨工作輪數(shù)變化Fig.3 Number of survival nodes changing as the working rounds

表2給出了2種算法就網(wǎng)絡(luò)中第一個節(jié)點死亡時間FND、50%節(jié)點死亡時間HND和70%節(jié)點死亡時間MND的對比。可以看出LEACH-S算法第一個節(jié)點死亡時間遠晚于LEACH算法半數(shù)節(jié)點死亡時間,當網(wǎng)絡(luò)中大部分節(jié)點死亡時,網(wǎng)絡(luò)監(jiān)測就失去了意義,網(wǎng)絡(luò)生命周期實質(zhì)上相當于結(jié)束。

表2 節(jié)點死亡時間比較Table 2 Dead time of nodes

4 結(jié) 語

文中對傳統(tǒng)LEACH路由算法進行了分析,提出了簇頭選擇問題、能耗不均問題。針對LEACH算法的不足之處做了改進,并對新算法進行了仿真分析,

分析結(jié)果表明改進后的LEACH-S在延長網(wǎng)絡(luò)節(jié)點的生存周期、均衡網(wǎng)絡(luò)節(jié)點的能量消耗方面有明顯改善,有效的延長了網(wǎng)絡(luò)的生存時間,保證了有更多的節(jié)點同時監(jiān)測、采集數(shù)據(jù),提高了網(wǎng)絡(luò)性能。

[1]李曉維,徐勇軍,任豐原.無線傳感器網(wǎng)絡(luò)技術(shù)[M].北京:北京理工大學出版社,2007:24-25. LI Xiao-wei,XU Yong-jun,REN Feng-yuan.Wireless Sensor Network Technology[M].Beijing:Beijing Institute of Technology Press,2007:24-25.

[2]胡鋼,朱佳奇,陳世志.無線傳感器網(wǎng)絡(luò)簇間節(jié)能路由算法[J].通信技術(shù),2009,42(11):134-137. HU Gang,ZHU Qi-jia,CHEN Shi-zhi.Study on Power-Scant Cluster-Level Routing Algorithm of WSNBased on Clustered Network[J].Communications Technology, 2009,11(42):134-137.

[3]高偉,胡艷軍.WSN中一種基于LEACH的協(xié)同通信算法的研究[J].通信技術(shù),2010,43(10):81-83. GAO Wei,HU Yan-jun.A Cooperative Communication Algorithm Bsaed on LEACH in WSN[J].Communications Technology,2010,43(10):81-83.

[4]AKYILDIZ F,SU W,SANKARASUBRAMANIAM Y. Wireless Sensor Networks:A survey[J].Computer Networks,2002,38(04):393-422.

[5]張偉華,李臘元,張劉敏,等.無線傳感器網(wǎng)絡(luò)LEACH協(xié)議能耗均衡改進[J].傳感技術(shù)學報,2008,11(21): 1918-1922. ZHANG Wei-hua,LI La-yuan,ZHANG Liu-min,etc. TheImprovement of LEACH Protocal Energy Balance in Wireless Sensor Networks[J].ChineseJournalofSensorsandActuators,2008,11(21):1918-1922.

[6]HEINZELMAN R W,CHANDRAKASAN A,BALKRISHNAN H.An Application-Specific Protocol Architectures for Wireless Microsensor Networks[D].IEEE Transaction on Wireless Communication,2002,1(4):660-670.

[7]李成岳,申鉉京,陳海鵬,等.無線傳感器網(wǎng)絡(luò)中LEACH路由算法的研究與改進[J].傳感技術(shù)學報, 2010,8(23):1163-1167. LI Cheng-yue,SHEN Xuan-jing,CHEN Hai-peng,ect. Research and Improvement of LEACH Routing Algorithm in Wireless Sensor Networks[J].ChineseJournalofSensorsandActuators,2010,8(23):1163-1167.

[8]WendiRabinerHeinzelman,AnanthaChandrakasan, HariBalakrishnan.Energy Efficient Communication Protocol for Wireless MicrosensorNetworks[C]//Proceedings of the 33rd Hawaii International Conference on System Sciences.Washington D C:IEEE Computer Society Press,2000:3005-3014.

蘇儉華(1989—),女,碩士研究生,主要研究方向為無線傳感器網(wǎng)絡(luò)、嵌入式通信系統(tǒng);

SU Jian Hua(1989-),female,graduate student,majoring in wireless sensor networks, embedded communications systems.

劉宇紅(1963—),男,教授,碩士生導師,主要研究方向為信號與信息處理、寬帶無線通信、語音與圖像處理、DSP與嵌入式微處理器的應(yīng)用研究、人工神經(jīng)網(wǎng)絡(luò)與模糊邏輯及智能化儀器和儀表的研究與開發(fā);

LIU Yu-hong(1963-),male,professor,master tutor,majoring signal and information processing,broadband wireless communications,voice and image processing,application of DSP and embedded microprocessors,artificial neural networks and fuzzy logic and intelligent instruments.

徐躍州(1990—),男,碩士研究生,主要研究方向為無線傳感器網(wǎng)絡(luò)、無線通信技術(shù)。

XU Yue-zhou(1990-),male,graduate student,majoring in wireless sensor networks and wireless communication technology.

A Routing Algorithm and Simulation of WSN based on LEACH

SU Jian-hua,LIU Yu-hong,XU Yue-zhou
(College of Electronics and Information,Guizhou University,Guiyang Guizhou 550025,China)

LEACH algorithm is the typical layered routing protocol of WSN,as it reconstructed clusters each loop,the distant cluster head nodes could be out of work easily owing to long-distance-sending data.When the distant node is selected to the cluster head one,it could accelerate the death of the nodes,disrupting the network life cycle.Aiming at the defect of the LEACH algorithm clustering mechanism,a kind of improved routing algorithm is proposed.Experimental result indicates that with the residual energy of node and fixed clustering,the equipoise of network energy could be improved,and the network lifetime increased.

wireless sensor networks;cluster-based routing algorithm;network lifetime

TP393

A

1002-0802(2014)01-0060-04

10.3969/j.issn.1002-0802.2014.01.012