朱 明,劉漫丹
(華東理工大學(xué) 信息科學(xué)與工程學(xué)院,上海 200237)
?
基于TinyOS的無線傳感器網(wǎng)絡(luò)LEACH算法的改進
朱明,劉漫丹
(華東理工大學(xué) 信息科學(xué)與工程學(xué)院,上海 200237)
LEACH協(xié)議是無線傳感器網(wǎng)絡(luò)中最流行的分簇路由協(xié)議之一。針對LEACH算法簇分布不均勻以及網(wǎng)絡(luò)能耗不均衡等問題提出了一種高效節(jié)能多跳路由算法。在簇建立階段,新算法根據(jù)網(wǎng)絡(luò)模型計算出最優(yōu)簇頭間距值,調(diào)整節(jié)點通信半徑以控制簇的大小,形成合理網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu);在數(shù)據(jù)傳輸階段,簇頭與基站之間采用多跳的通信方式,降低了節(jié)點能耗。在TinyOS操作系統(tǒng)下,使用nesC語言設(shè)計實現(xiàn)了LEACH-EEMH算法。基于TOSSIM平臺的仿真結(jié)果表明,新算法較LEACH算法在均衡網(wǎng)絡(luò)能耗、延長網(wǎng)絡(luò)壽命方面具有顯著優(yōu)勢。
TinyOS系統(tǒng);無線傳感器網(wǎng)絡(luò);路由協(xié)議;高效節(jié)能
無線傳感器網(wǎng)絡(luò)(Wireless Sensor Networks,WSN)由大量的小型傳感器節(jié)點組成,它可以實時地收集和處理各種環(huán)境和對象的信息,并通過衛(wèi)星或互聯(lián)網(wǎng)將其發(fā)送到用戶終端[1]。它使得人們能夠在任何時間、地點和環(huán)境下實現(xiàn)對物理世界的動態(tài)、智能、泛在的感知[2]。
由于節(jié)點電池能源有限,計算及存儲能力弱,它們的操作系統(tǒng)需具備耗能少且可以適應(yīng)各類應(yīng)用環(huán)境的特點,TinyOS[3]正是具備了上述特點的WSN操作系統(tǒng)。TinyOS采用組件層次結(jié)構(gòu),是一個基于事件的系統(tǒng),現(xiàn)階段大部分無線傳感器網(wǎng)絡(luò)研究項目都采用TinyOS操作系統(tǒng),TinyOS已成為WSN研究領(lǐng)域上的標(biāo)準(zhǔn)平臺。
WSN路由協(xié)議決定了網(wǎng)絡(luò)的運行效率和執(zhí)行能力,由于網(wǎng)絡(luò)資源受限,WSN路由協(xié)議算法的研究核心便是降低傳感器網(wǎng)絡(luò)的能耗,提高資源利用率,延長網(wǎng)絡(luò)壽命[4]。WSN路由協(xié)議根據(jù)網(wǎng)絡(luò)結(jié)構(gòu)可分為平面路由協(xié)議和分簇路由協(xié)議兩種類型。平面路由協(xié)議網(wǎng)絡(luò)中各節(jié)點功能相同,算法簡單,容易實現(xiàn),但是網(wǎng)絡(luò)的可擴展性小,應(yīng)用范圍較窄。常見的平面路由協(xié)議有SPIN[5]、Flooding Protocol[6]、Directed Diffusion[7]等。分簇路由協(xié)議將網(wǎng)絡(luò)劃分為“簇”,每個簇由一個簇頭和多個成員節(jié)點構(gòu)成,相比平面路由協(xié)議有較好的可擴展性,應(yīng)用范圍廣。常見的分簇路由協(xié)議有LEACH[8]、TEEN[9]、PEGASIS[10]等。
LEACH(Low Energy Adaptive Clustering Hierarchy)是WSN中具有代表性的分簇路由算法,具有低功耗自適應(yīng)的特點,LEACH的循環(huán)周期使用了“輪”的概念,一輪包括簇建立和數(shù)據(jù)傳輸階段兩個部分。簇建立階段,各節(jié)點隨機生成一個0~1間的數(shù),若該數(shù)小于閾值Tn,則此節(jié)點成為簇頭,同時廣播成為簇頭的信息。非簇頭節(jié)點根據(jù)收到簇頭廣播消息,選擇加入離自己最近的簇頭成簇。數(shù)據(jù)傳輸階段,簇成員節(jié)點將其監(jiān)測到的數(shù)據(jù)發(fā)送給簇頭節(jié)點;簇頭進行數(shù)據(jù)融合處理,然后以單跳的方式將數(shù)據(jù)發(fā)送給基站。Tn計算式如
(1)
式中:p是期望的簇頭數(shù)占網(wǎng)絡(luò)中總節(jié)點數(shù)的比例;r是當(dāng)前輪數(shù);每1/p輪為一個周期,G是最近一個周期內(nèi)沒有成為簇頭的節(jié)點集合。
LEACH提出了一種簇頭輪流當(dāng)選的機制,初步解決了負(fù)載平衡的問題,且采用分布式算法,容易實現(xiàn),但還是存在一些問題。例如LEACH采用隨機選擇簇頭的方式,不能保證簇的均勻分布,致使簇頭的能耗不均衡,網(wǎng)絡(luò)壽命縮短;且簇頭與基站采用單跳通信的方式限制了網(wǎng)絡(luò)的規(guī)模。LEACH-C[11]是LEACH的改進算法,采用集中式的分簇算法選出較優(yōu)的簇頭,使簇分布更加合理;但簇間采用單跳通信,傳輸距離過遠仍會產(chǎn)生大量能耗。
本文針對LEACH算法的不足提出了一種基于簇分布的高效節(jié)能多跳路由算法——LEACH-EEMH(EnergyEfficientMulti-Hop)。
1.1LEACH-EEMH算法的設(shè)計思想
LEACH-EEMH算法的設(shè)計思想主要體現(xiàn)在以下幾個方面:
1)根據(jù)網(wǎng)絡(luò)能耗最小的原則計算出簇頭節(jié)點之間最優(yōu)的間距值,在這個條件的約束獲得合理的簇分布,使簇較為均勻地分布在網(wǎng)絡(luò)中;2)簇頭選舉首先考慮節(jié)點的能量水平,能量多的節(jié)點當(dāng)選本輪簇頭;3)為避免頻繁的全網(wǎng)動態(tài)分簇造成大量能量開銷,只在每個周期的首輪進行整個網(wǎng)絡(luò)的動態(tài)分簇,其余時間則采用簇內(nèi)獨立的簇頭輪換機制;4)簇頭節(jié)點和基站之間采用多跳的方式進行通信,以減少網(wǎng)絡(luò)能耗,延長網(wǎng)絡(luò)壽命。
1.2能耗模型
LEACH-EEMH算法的能量模型與LEACH相同,采用一階無線電能耗模型,節(jié)點發(fā)送kbit的數(shù)據(jù)到距離d的位置,根據(jù)該模型耗能為
(2)
式中:Eelec表示發(fā)送或接收1bit數(shù)據(jù)消耗的能量;εfs和εmp分別表示自由空間模型和多路衰減模型下的功率放大損耗常數(shù)。在傳輸距離小于閾值d0時,功率放大損耗采用自由空間模型,傳輸距離大于d0時,采用多路衰減模型。節(jié)點接收和融合數(shù)據(jù)k(單位bit)消耗的能量分別為
Erx(k,d)=kEelec
(3)
Efusion(k,d)=kEDA
(4)
式中:EDA是融合1bit數(shù)據(jù)消耗的能量。
1.3最優(yōu)簇頭間距值求取
簇頭節(jié)點之間最優(yōu)的間距值是根據(jù)最優(yōu)簇頭數(shù)計算得到,下面首先計算最優(yōu)簇頭節(jié)點的個數(shù)。
假設(shè)在M×M的監(jiān)測區(qū)域內(nèi)隨機分布著n個節(jié)點,若有k個簇,那么每個簇內(nèi)平均有n/k個節(jié)點。簇頭節(jié)點的能耗主要包括接收成員節(jié)點監(jiān)測到的數(shù)據(jù)、簇內(nèi)數(shù)據(jù)融合、將整個簇的數(shù)據(jù)傳輸?shù)交具@3個部分。由于簇頭遠離基站,能量損耗可采用多路衰減模型,單個簇頭節(jié)點的能耗為
(5)
式中:l是數(shù)據(jù)包大小;dtoBS是簇頭到基站的距離。
簇成員節(jié)點的能耗主要是將監(jiān)測到的數(shù)據(jù)發(fā)送給簇頭。簇頭與成員節(jié)點之間的距離較近,采用自由空間模型,單個成員節(jié)點的能耗為
(6)
式中:dtoCH是成員節(jié)點到簇頭的距離。
簇可以看做是以簇頭為圓心的圓形區(qū)域,每個簇所覆蓋的面積平均為M2/k,其成員節(jié)點到簇頭距離的平方的期望值為

(7)
此時成員節(jié)點的能耗為
(8)
每個簇的能耗為
(9)
全網(wǎng)的能耗為
(10)
式中:DtoBS表示基站到網(wǎng)絡(luò)區(qū)域中心的距離。
令Etotal的一階導(dǎo)數(shù)為零,可得使Etotal值最小的k值為
(11)
網(wǎng)絡(luò)運行中不斷會有節(jié)點因能量耗盡而死亡,因此kopt的值是變化的。
kopt個簇要覆蓋整個面積為M×M的正方形區(qū)域,簇頭均勻分布,理想的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)如圖1所示,以簇頭為圓心的圓半徑為R,整個監(jiān)測區(qū)域由kopt個小正方形所覆蓋,那么
(12)
簇的半徑R為
(13)
可得簇頭間最小間距D的值為
(14)
由式(14)可知,D會隨著kopt的變化而變化。LEACH-EEMH算法中基站每個周期(1/ p 輪)重新計算D值,然后向全網(wǎng)廣播該值。

圖1 理想的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)
1.4LEACH-EEMH算法的流程
LEACH-EEMH以輪為周期,每輪分為簇建立、簇間路由建立以及數(shù)據(jù)傳輸3個階段,數(shù)據(jù)傳輸階段與LEACH算法相同,這里詳細(xì)介紹前兩個階段。
1.4.1簇建立階段
簇建立階段分為每周期首輪簇建立和非首輪簇建立兩種情況。
1) 情況一
每周期首輪簇建立階段,在簇頭選舉之前,節(jié)點根據(jù)自己的能量水平確定一個定時時間,能量大的節(jié)點比能量小的節(jié)點時間短。
簇頭選舉工作開始,全網(wǎng)同時進入定時時間的倒計時,能量最大的節(jié)點倒計時首先結(jié)束,當(dāng)選第一個簇頭。該節(jié)點以D為通信半徑廣播簇頭消息,然后增大通信半徑向基站發(fā)送一條簇頭消息。
在定時時間內(nèi),若某個節(jié)點收到了簇頭的廣播消息,則立即結(jié)束倒計時,放棄成為簇頭節(jié)點。直到倒計時結(jié)束仍然沒有收到簇頭廣播消息的節(jié)點,宣布自己成為簇頭。
如果基站收到的簇頭消息達到了最佳簇頭數(shù)目,則停止選舉簇頭的操作。
簇頭選舉結(jié)束,簇頭節(jié)點增大通信半徑廣播簇頭消息。非簇頭節(jié)點選擇距離最近的簇頭節(jié)點作為自己的簇頭,加入該簇并向簇頭節(jié)點發(fā)送入簇消息,至此每周期的首輪簇建立階段完成。
2) 情況二
非首輪簇建立階段不進行全網(wǎng)簇重組,當(dāng)前輪的簇頭由上一輪的簇頭節(jié)點指定;上一輪的簇頭節(jié)點在數(shù)據(jù)傳輸?shù)淖詈箅A段選擇簇內(nèi)能量最大的節(jié)點作為下一輪簇頭,新簇頭廣播成為簇頭的消息,非簇頭節(jié)點入簇。
1.4.2簇間路徑建立階段
每個簇頭節(jié)點都維護著一個路由表Troute,它是根據(jù)其接收的簇頭廣播消息建立的。當(dāng)簇頭i收到簇頭j的廣播消息時,比較兩簇頭到基站的距離值dtoBS。若j的dtoBS值小于i的dtoBS值,將簇頭j加入到i的Troute中,反之則不加入。若簇頭i的dtoBS值不大于d0或其Troute為空,則選擇基站作為下一跳節(jié)點。 反之,簇頭i從其Troute中選擇距離最近的簇頭節(jié)點作為下一跳節(jié)點。
2.1總體框架
本文采用TinyOS 2.1操作系統(tǒng)和nesC語言實現(xiàn)LEACH-EEMH協(xié)議。圖2是LEACH-EEMH協(xié)議的結(jié)構(gòu)框圖,其中實線框表示模塊,每個模塊實現(xiàn)一種功能;虛線框表示配件,它表示模塊的連接關(guān)系;箭頭代表接口。箭頭上方是上層組件,箭頭下方是下層組件,上層組件通過接口調(diào)用下層組件的功能,下層組件通過接口向上層組件觸發(fā)事件。LEACH-EEMH協(xié)議采用單配件多模塊的程序模型,整個協(xié)議在一個配件LeacheemhC里實現(xiàn)。配件內(nèi)包含LeacheemhP,ClusterFormP和ClusterMultiRouteP共3個模塊。除此之外還包括TinyOS系統(tǒng)自帶的TimerMilliC,AMSenderC,AMReciverC,ActiveMessageC和RandomC等組件。路由層的功能對于上層應(yīng)用來說是不透明的,LeacheemhC組件為上層提供了與數(shù)據(jù)傳輸有關(guān)的StdControl,AMSend和Receive接口,接口的相關(guān)函數(shù)在LeacheemhP模塊里實現(xiàn)。

圖2 LEACH-EEMH結(jié)構(gòu)框圖
2.2主要功能模塊
LEACH-EEMH算法的主要功能模塊是LeacheemhP,ClusterFormP和ClusterMultiRouteP模塊,其中LeacheemhP模塊是其他兩個模塊的管理者,對外界提供開放的功能接口。ClusterFormP是簇建立模塊,ClusterMultiRouteP是簇間多跳路徑建立模塊。
1)LeacheemhP模塊
LeacheemhP是LEACH-EEMH協(xié)議的核心處理模塊。LeacheemhP模塊通過調(diào)用AMControl接口控制無線通信模塊ActiveMessageC的開啟與關(guān)閉,調(diào)用CFControl接口控制ClusterFormP模塊完成簇的建立,調(diào)用CMRControl接口控制ClusterMultiRouteP模塊建立簇間多跳路徑。簇間多跳路徑建立完成后,LeacheemhP向上觸發(fā)RouteFormDone事件,開始數(shù)據(jù)傳輸。LeacheemhP模塊向上層提供了StdControl和AMSend和Receive接口。StdControl是標(biāo)準(zhǔn)控制接口,能夠控制路由層功能的開啟和關(guān)閉。AMSend是主動消息發(fā)送接口,AMSend在其發(fā)送命令里指定了AM目標(biāo)地址,它的實質(zhì)是經(jīng)過路由層的多跳傳輸后到達該目標(biāo),LEACH-EEMH協(xié)議的目標(biāo)地址是基站。Receive是消息接收接口,提供了接收到消息時觸發(fā)的事件函數(shù),當(dāng)基站接收到消息包時會觸發(fā)Receive接口的事件。
2)ClusterFormP模塊
ClusterFormP是簇建立模塊,負(fù)責(zé)完成簇頭的選舉、簇的形成和維護等工作。向上層提供了CFControl接口,用于控制簇建立的開始與結(jié)束,獲得簇的信息等。ClusterFormP模塊調(diào)用AMSenderC組件的AMSend接口和AMReceiveC組件的Receive接口完成簇內(nèi)路由和數(shù)據(jù)消息包的發(fā)送與接收,調(diào)用TimerMilliC組件的Timer接口完成與定時器有關(guān)的操作,調(diào)用RandomC組件的Random接口獲得簇頭選舉時需要的隨機數(shù)。
3)ClusterMultiRouteP模塊
ClusterMultiRouteP是簇間多跳路徑建立模塊,負(fù)責(zé)建立簇頭與匯聚節(jié)點之間的多跳路徑,完成路由的選擇工作。向上層提供了CMRControl接口,用于控制簇間多跳路徑建立的開始與結(jié)束,獲得路由信息等。ClusterMultiRouteP模塊調(diào)用AMSenderC組件的AMSend接口和AMReceiveC組件的Receive接口來完成簇間路由和數(shù)據(jù)消息包的發(fā)送與接收,調(diào)用TimerMilliC組件的Timer接口完成一系列與定時器有關(guān)的操作。
3.1參數(shù)設(shè)置
本文選用TinyOS操作系統(tǒng)自帶的仿真工具TOSSIM(TinyOS simulator)[12]對LEACH-EEMH算法進行仿真,TOSSIM可以支持大規(guī)模的網(wǎng)絡(luò)仿真。100個節(jié)點隨機分布在100 m×100 m區(qū)域內(nèi),基站的坐標(biāo)為(50,175),其他參數(shù)如表1所示。
表1仿真參數(shù)

參數(shù)含義參數(shù)值Einit節(jié)點初始能量2JEelec單位數(shù)據(jù)發(fā)送/接收能耗50nJ/bitεfs自由空間系數(shù)10(pJ·bit-1·m-2)εmp多路衰減系數(shù)0.0013(pJ·bit-1·m-4)EDA簇頭數(shù)據(jù)融合能耗5nJ/bitd0信道模型距離閾值87mpdata數(shù)據(jù)包長度4000bit
3.2結(jié)果與分析
本文采用網(wǎng)絡(luò)生存時間和負(fù)載平衡程度這兩個性能評價指標(biāo),對比LEACH-EEMH,LEACH-C和LEACH算法,仿真結(jié)果如圖3、圖4所示。

圖3 網(wǎng)絡(luò)生存時間仿真結(jié)果

圖4 網(wǎng)絡(luò)負(fù)載平衡因子仿真結(jié)果
由圖3可知, LEACH算法第一個節(jié)點死亡的時間約是240輪,最后一個節(jié)點死亡的時間約為510輪;LEACH-C算法第一個節(jié)點死亡的時間約是290輪,最后一個節(jié)點死亡的時間約為560輪;LEACH-EEMH算法第一個節(jié)點死亡的時間約是300輪,最后一個節(jié)點死亡的時間約為610輪。經(jīng)計算得到,LEACH-C第一個節(jié)點死亡時間比LEACH延長了21%,網(wǎng)絡(luò)生存時間比LEACH延長了9.8%;而LEACH-EEMH的一個節(jié)點死亡時間比LEACH延長了25%,網(wǎng)絡(luò)生存時間比LEACH延長了20%。LEACH-EEMH算法的網(wǎng)絡(luò)生存周期明顯高于LEACH和LEACH-C算法,因此LEACH-EEMH算法在減少網(wǎng)絡(luò)能耗,延長網(wǎng)絡(luò)生存時間方面具有較好的性能。
圖4對比了3種算法的負(fù)載平衡程度,負(fù)載平衡因子越大,網(wǎng)絡(luò)的負(fù)載平衡度越好,網(wǎng)絡(luò)壽命越長。從圖4可知,LEACH的負(fù)載平衡因子最大值約為0.023 5,最小值約為0.012 5;LEACH-C的負(fù)載平衡因子最大值約為0.025 5,最小值約為0.019 5;LEACH-EEMH的負(fù)載平衡因子最大值約為0.028 0,最小值約為0.022 5,且波動較小。表明LEACH-EEMH在平衡網(wǎng)絡(luò)負(fù)載方面具有較好的性能,這是因為LEACH-EEMH算法的簇頭數(shù)量最優(yōu),且設(shè)置了簇頭的最小間距使簇頭分布較為均勻,更好地均衡了網(wǎng)絡(luò)負(fù)載。
本文選取經(jīng)典的LEACH路由算法作為研究原型,針對其不足提出了LEACH-EEMH算法,并將該算法在TinyOS操作系統(tǒng)上實現(xiàn)。TOSSIM仿真結(jié)果表明LEACH-EEMH算法能有效節(jié)省能量,均衡網(wǎng)絡(luò)負(fù)載,延長網(wǎng)絡(luò)生存周期。但LEACH-EEMH算法也有不足之處,該協(xié)議在設(shè)計時著重考慮能耗問題,忽略了時延、丟包率、安全因素等情況,今后還需對此做進一步的研究。
[1]YICK J,MUKHERJEE B,GHOSAL D. Wireless sensor network survey[J]. Computer networks,2008,52(12):2292-2330.
[2]孫利民.無線傳感器網(wǎng)絡(luò)[M].北京:清華大學(xué)出版社有限公司,2005.
[3]LEVIS P,MADDEN S,POLASTRE J,et al. TinyOS:an operating system for sensor networks[M]. Ambient intelligence:Springer Berlin Heidelberg,2005.
[4]XIANGNING F,YULIN S. Improvement on LEACH protocol of wireless sensor network[C]// International Conference on Sensor Technologies and Applications. [S.l.]:IEEE,2007:260-264.
[5]KULIK J,HEINZELMAN W,BALAKRISHNAN H. Negotiation-based protocols for disseminating information in wireless sensor networks[J].Wireless networks,2002,8(2/3):169-185.
[6]FARIVAR R,F(xiàn)AZELI M,MIREMADI S G. Directed flooding:a fault-tolerant routing protocol for wireless sensor networks[C]// Proceedings of Systems communications. [S.l.]:IEEE,2005:395-399.
[7]INTANAGONWIWAT C,GOVINDAN R,ESTRIN D,et al. Directed diffusion for wireless sensor networking[J]. IEEE/ACM transactions on networking,2003,11(1):2-16.
[8]鄒虹,彭國龍.一種基于 LEACH 改進的均勻分簇路由算法[J].電視技術(shù),2013,37(3):133-136.
[9]MANJESHWAR A,AGRAWAL D. TEEN:a protocol for enhanced efficiency in WSNs[C]//Proc. the First International Workshop on Parallel and Distributed Computing Issues in Wireless Networks and Mobile Computing. [S.l.]:IEEE,2001:2009-2015.
[10]JUNG S M,HAN Y J,CHUNG T M. The concentric clustering scheme for efficient energy consumption in the PEGASIS[C]// Proc. the 9th International Conference on Advanced Communication Technology. [S.l.]:IEEE,2007:260-265.
[11]HEINZELMAN W B,CHANDRAKASAN A P,BALAKRISHNAN H. An application-specific protocol architecture for wireless microsensor networks[J]. IEEE transactions on wireless communications,2002,1(4):660-670.
[12]LEVIS P,LEE N,WELSH M,et al. TOSSIM:accurate and scalable simulation of entire TinyOS applications[C]//Proceedings of the 1st international conference on Embedded networked sensor systems. [S.l.]:ACM,2003:126-137.
朱明(1990— ),女,碩士生,主研無線傳感器網(wǎng)絡(luò);
劉漫丹(1973— ),女,教授,博士生導(dǎo)師,主要研究方向為無線傳感器網(wǎng)絡(luò)、智能優(yōu)化計算等。
責(zé)任編輯:許盈
Improvement of LEACH algorithm based on TinyOS for wireless sensor network
ZHU Ming, LIU Mandan
(SchoolofInformationScienceandEngineering,EastChinaUniversityofScienceandTechnology,Shanghai200237,China)
LEACH protocol is one of the most popular clustering routing protocols in wireless sensor networks. To deal with the unbalanced clustering and energy consumption problems exist of LEACH algorithm, an energy efficient multi-hop routing algorithm is proposed. In the clustering stage, the new algorithm calculates the optimal cluster head distance value, adjust the node communication radius to control the size of the cluster, thus forming a reasonable network topology structure. In the stage of data stable transmission, a multi-hop communication mode is adopted between the cluster head and the base station to reduce the energy cost. Based on TinyOS system, LEACH-EEMH is designed and realized with the language nesC. Simulations in TOSSIM platform reveal that, in contrast with LEACH, the new algorithm has obvious advantages in balancing the network energy consumption and prolonging the network lifetime.
TinyOS system; wireless sensor network; routing protocol; energy efficient
TP393
ADOI:10.16280/j.videoe.2016.10.015
中央高校基本科研業(yè)務(wù)費專項(WH1213010)
2015-12-31
文獻引用格式:朱明,劉漫丹. 基于TinyOS的無線傳感器網(wǎng)絡(luò)LEACH算法的改進[J].電視技術(shù),2016,40(10):71-76.
ZHU M,LIU M D. Improvement of LEACH algorithm based on TinyOS for wireless sensor network[J].Video engineering,2016,40(10):71-76.