大規(guī)模無(wú)線傳感網(wǎng)絡(luò)的混合LEACH協(xié)議研究*

彭 蕾，呂敬祥*，劉秋平

（1.井岡山大學(xué)電子與信息工程學(xué)院，江西吉安343009；2.流域生態(tài)與地理環(huán)境監(jiān)測(cè)國(guó)家測(cè)繪地理信息局重點(diǎn)實(shí)驗(yàn)室，江西吉安343009）

大規(guī)模無(wú)線傳感網(wǎng)絡(luò)的混合LEACH協(xié)議研究*

彭 蕾1，2，呂敬祥1，2*，劉秋平1

（1.井岡山大學(xué)電子與信息工程學(xué)院，江西吉安343009；2.流域生態(tài)與地理環(huán)境監(jiān)測(cè)國(guó)家測(cè)繪地理信息局重點(diǎn)實(shí)驗(yàn)室，江西吉安343009）

能耗問(wèn)題已經(jīng)成為大規(guī)模無(wú)線傳感器網(wǎng)絡(luò)中的研究熱點(diǎn)，因此如何設(shè)計(jì)高能效的路由協(xié)議是當(dāng)前面臨的技術(shù)挑戰(zhàn)。為了降低傳感器節(jié)點(diǎn)的能耗，提出一種適用大規(guī)模網(wǎng)絡(luò)的基于LEACH算法的混合無(wú)線傳感網(wǎng)絡(luò)節(jié)能路由算法。首先，根據(jù)距離信息，設(shè)計(jì)一種簇成員向基站直接傳輸或者通過(guò)簇頭轉(zhuǎn)發(fā)數(shù)據(jù)的路由協(xié)議。然后，推導(dǎo)出滿足該算法的能耗條件。最后，通過(guò)MATLAB工具仿真表明與已有的LEACH協(xié)議和M-LEACH協(xié)議相比，混合路由協(xié)議能夠有效降低基站周?chē)?jié)點(diǎn)的能耗，從而延長(zhǎng)整個(gè)網(wǎng)路的生存期。

無(wú)線傳感網(wǎng)絡(luò)；混合LEACH協(xié)議；分簇；節(jié)能

無(wú)線傳感網(wǎng)通常由大量小尺寸，低功耗的集成有傳感器、數(shù)據(jù)處理單元和短距離無(wú)線通信模塊的節(jié)點(diǎn)構(gòu)成。這些節(jié)點(diǎn)能自動(dòng)感知周?chē)h(huán)境并形成自組織網(wǎng)絡(luò)，因此廣泛應(yīng)用于工業(yè)、農(nóng)業(yè)及軍事領(lǐng)域。但是在無(wú)線傳感網(wǎng)的實(shí)際應(yīng)用中仍存在一些突出問(wèn)題，其中最主要的問(wèn)題是怎么延長(zhǎng)網(wǎng)絡(luò)的生存期，即能量問(wèn)題是限制無(wú)線傳感網(wǎng)廣泛應(yīng)用的主要瓶頸之一，因此解決無(wú)線傳感網(wǎng)中的能量限制問(wèn)題，一直是國(guó)內(nèi)外學(xué)者研究的熱點(diǎn)［1-5］。目前有些學(xué)者采用新興的可再生能源如太陽(yáng)能或風(fēng)能代替結(jié)點(diǎn)的電池或者超級(jí)電容器的供電，但這些能源具備間歇性的特性給網(wǎng)絡(luò)性能帶來(lái)了缺陷。本文不以傳感網(wǎng)物理供電方式為研究對(duì)象而是在充分研究目前已存在的分簇路由協(xié)議的基礎(chǔ)上提出合理的平衡能量消耗的更高效節(jié)能路由協(xié)議，以致能提高網(wǎng)絡(luò)壽命。國(guó)內(nèi)外學(xué)者在路由協(xié)議方面開(kāi)展了大量的工作，一些有效的分簇路由協(xié)議相繼提出，如LEACH［6］，PAMAS［7］and HEED［8］。

分簇路由協(xié)議有以下幾個(gè)優(yōu)點(diǎn)：①成員結(jié)點(diǎn)可通過(guò)休眠方式來(lái)節(jié)省能量從而達(dá)到延長(zhǎng)壽命的目標(biāo)。②容易實(shí)現(xiàn)數(shù)據(jù)融合以致能有效減少網(wǎng)絡(luò)通信量而節(jié)省能量。③不需要維護(hù)復(fù)雜的路由信息，以致不會(huì)發(fā)送大量路由控制信息?？梢钥闯?，基于分簇的路由協(xié)議不僅能使網(wǎng)絡(luò)高能效運(yùn)行而且使網(wǎng)絡(luò)傳輸數(shù)據(jù)的可靠性大大提高，其中LEACH是傳感網(wǎng)中應(yīng)用廣泛的代表性分簇協(xié)議之一。LEACH協(xié)議和平面路由現(xiàn)已相比，雖然取得了一定的成功但其缺點(diǎn)也不言而喻，仍然有待改進(jìn)。①簇頭任意選取，任意分布，因此整過(guò)網(wǎng)路所需簇頭數(shù)沒(méi)有很好的得到考慮。②低剩余能量的結(jié)點(diǎn)有等概的變成簇頭的可能，當(dāng)?shù)褪Ｓ嗄芰康慕Y(jié)點(diǎn)做簇頭時(shí)，整過(guò)簇有可能失效。③簇頭和基站之間采用單跳通信，不利于大規(guī)模無(wú)線傳感網(wǎng)。本文在深入分析LEACH分簇算法的基礎(chǔ)上提出一種高效節(jié)能的適合大規(guī)模無(wú)線傳感網(wǎng)混合多跳分簇路由協(xié)議。

1 相關(guān)工作

1.1 LEACH算法

Heinzelman首先提出的LEACH（Low Energy Adaptive Clustering Hierarchy）協(xié)議是無(wú)線傳感網(wǎng)中應(yīng)用最為廣泛的節(jié)能路由算法之一。該協(xié)議引入輪的概念，每一輪包含兩個(gè)階段：簇形成階段和簇穩(wěn)定階段。在簇成立階段，每個(gè)結(jié)點(diǎn)根據(jù)一個(gè)0到1的隨機(jī)數(shù)判斷本輪是否成為簇頭，如果隨機(jī)數(shù)小于閾值T（n），此結(jié)點(diǎn)本輪變成簇頭，閾值表達(dá)式如式（1）：

式中，p為希望成為簇頭的百分比，r為輪數(shù)，G為在上次1/p沒(méi)有被選中做簇頭的節(jié)點(diǎn)集合。簇頭選中后，根據(jù)簇頭節(jié)點(diǎn)廣播信號(hào)強(qiáng)度，所有節(jié)點(diǎn)加入相應(yīng)的簇，簇形成階段結(jié)束。在穩(wěn)定階段，簇頭按TDMA方式分配時(shí)隙給個(gè)成員，結(jié)點(diǎn)在給定的時(shí)隙向簇頭傳播數(shù)據(jù)。簇頭將收集的數(shù)據(jù)加工處理后單跳傳給基站，如圖1所示。通過(guò)簇協(xié)議整過(guò)網(wǎng)路的的能量負(fù)載能較均勻的分布到每個(gè)結(jié)點(diǎn)，因此具備較低的能量消費(fèi)，延長(zhǎng)整過(guò)網(wǎng)路的生命。

圖1 LEACH協(xié)議單跳示意圖

1.2 LEACH網(wǎng)絡(luò)能耗模型

發(fā)送k bit消息，傳輸距離為d時(shí)的能量模型如式（2）所示，其中d0如式（3）所示：

式中，ETx-elec(k)發(fā)射端電路消耗能量，ETx-amp(k,d)將k位數(shù)據(jù)長(zhǎng)度發(fā)射距離d時(shí)能量消耗，Eelec單位能量消耗，εfs=10 pJ/（bit/m2）為自由空間模型中功率放大器能量消耗比例系數(shù)，εmp=0.001 3 pJ/（bit/m4）為多徑衰落模型中功率放大器能量消耗的比例系數(shù)。當(dāng)d?d0時(shí)是自由空間模型，否則是多徑衰落模型。接收端能量消耗如式（4）所示：

忽略LEACH數(shù)據(jù)加工能量，假設(shè)網(wǎng)絡(luò)中節(jié)點(diǎn)總數(shù)為N，網(wǎng)絡(luò)總體能耗計(jì)算公式如式（5）所示：

式中，k代表簇頭個(gè)數(shù)，L表示數(shù)據(jù)長(zhǎng)度，dBS節(jié)點(diǎn)與基站之間的距離，dj收發(fā)設(shè)備之間的距離。

2 混合LEACH路由協(xié)議

LEACH協(xié)議是一種完全分布式的層次路由協(xié)議，主要優(yōu)點(diǎn)是節(jié)點(diǎn)的自適應(yīng)性、容錯(cuò)性好。但其仍存在不足之處，主要表現(xiàn)在簇頭節(jié)點(diǎn)選取不均勻，能量損耗集中在簇頭，為此研究者提出了許多修正方法。LEACH-C［9］采用集中式簇頭選擇方式，由基站根據(jù)位置信息和剩余能量決定誰(shuí)做簇頭。這種算法使得簇頭分布更合理，但由于在結(jié)點(diǎn)和基站之間增加了額外的通信，因此有可能縮短網(wǎng)絡(luò)的生存期。F-LEACH［10］采用在每個(gè)簇中按固定方式輪流做簇頭的方式，縮減了簇形成階段的能量消費(fèi)。但是存在讓一個(gè)結(jié)點(diǎn)停留在一個(gè)離簇頭結(jié)點(diǎn)較遠(yuǎn)的簇里，增加了能量開(kāi)銷(xiāo)。E-LEACH［11］引入剩余能量，在每一輪選舉中，擁有更多剩余能量的結(jié)點(diǎn)被選做簇頭。V-LEACH［12］引入了副簇頭的概念，目的是當(dāng)簇頭死亡時(shí)確保數(shù)據(jù)的可靠傳輸。由于在大規(guī)模無(wú)線傳感網(wǎng)中，LEACH協(xié)議仍采用簇頭直接傳輸數(shù)據(jù)到基站模式，因此遠(yuǎn)離基站的簇頭消耗能量非?？欤贿m合大規(guī)模無(wú)線傳感網(wǎng)。為了解決這個(gè)問(wèn)題，學(xué)者們提出了多跳LEACH（M-LEACH）協(xié)議［13］，如圖2所示。但是這種模式容易造成基站附近節(jié)點(diǎn)能量過(guò)載而縮減網(wǎng)絡(luò)壽命。

圖2 多跳LEACH協(xié)議示意圖

本文在充分借鑒現(xiàn)有改進(jìn)算法的基礎(chǔ)上提出一種混合多跳路由協(xié)議，克服了基站附近的簇頭節(jié)點(diǎn)能量消費(fèi)過(guò)高的問(wèn)題。在提出的協(xié)議中，簇頭選出以后，基站附近的成員節(jié)點(diǎn)可以選擇傳數(shù)據(jù)包給簇頭，簇頭再直接再傳給基站或通過(guò)別的簇頭中繼，也可以直接傳給基站。不僅克服了基站附近附近節(jié)點(diǎn)生存期短的問(wèn)題，也能適應(yīng)大規(guī)模無(wú)線網(wǎng)絡(luò)。

2.1 算法描述

現(xiàn)有的多跳路由容易造成基站附近的節(jié)點(diǎn)耗能過(guò)多過(guò)早死亡，圖3描繪了混合多跳路由協(xié)議，基站附近的節(jié)點(diǎn)可以直接傳輸數(shù)據(jù)包到基站而不通過(guò)簇頭，遠(yuǎn)離基站的節(jié)點(diǎn)通過(guò)簇頭傳輸數(shù)據(jù)包到基站。每個(gè)節(jié)點(diǎn)能獲得到基站和簇頭距離信息，根據(jù)距離信息決定通過(guò)簇頭傳輸信息或者直接傳信息給基站。

圖3 混合多跳路由LEACH協(xié)議

2.1.1 網(wǎng)絡(luò)模型

采用的網(wǎng)絡(luò)特性如下：①所有傳感器節(jié)點(diǎn)具有同樣的初始能量。②網(wǎng)絡(luò)和基站布置好后，都靜止不動(dòng)。③基站可以在傳感器網(wǎng)絡(luò)覆蓋的區(qū)域內(nèi)。④節(jié)點(diǎn)通過(guò)信號(hào)強(qiáng)度來(lái)估計(jì)距離，節(jié)點(diǎn)能根據(jù)距離遠(yuǎn)近調(diào)節(jié)發(fā)射功率。

2.1.2 混合多跳無(wú)線網(wǎng)絡(luò)能耗模型

采用2.2節(jié)中描述的自由空間傳播無(wú)線能耗模型。另外假設(shè)簇內(nèi)成員節(jié)點(diǎn)到其簇頭的距離（dm-ch）相等；與基站直接通信的成員節(jié)點(diǎn)到基站的距離（dm-bs）相等。當(dāng)簇離基站近時(shí)，簇成員可直接發(fā)送k位信息到基站此時(shí)能量消費(fèi)滿足方程（6）。通過(guò)簇頭發(fā)送k位信息到基站時(shí)能量消費(fèi)滿足方程（7）。

如果基站附近的簇有L個(gè)成員節(jié)點(diǎn)，且直接與基站通信，總能量消費(fèi)：

當(dāng)簇頭遠(yuǎn)離基站時(shí)，成員節(jié)點(diǎn)把信息直接發(fā)給簇頭，簇頭收集完數(shù)據(jù)后發(fā)給基站，也可以通過(guò)另一個(gè)簇頭中繼之后把信息傳給基站。成員節(jié)點(diǎn)傳送數(shù)據(jù)給簇頭的能量消費(fèi)滿足式（9）：

簇頭節(jié)點(diǎn)消耗的能量由兩部分組成，接受成員節(jié)點(diǎn)消耗的能量和發(fā)送加工后的數(shù)據(jù)能量，這里忽略數(shù)據(jù)加工能量。

若每個(gè)簇有L個(gè)成員節(jié)點(diǎn)，每個(gè)成員一次發(fā)k bit信息，簇頭把收到的數(shù)據(jù)加工成k bit，因此簇頭消耗的總能量滿足式（11）：

整過(guò)簇的總能量消費(fèi)滿足（12）

將式（9），式（11）代入

2.2 判斷條件推導(dǎo)

為了決定每個(gè)成員傳輸數(shù)據(jù)給基站還是簇頭，我們比較兩者情況下的能量消耗即比較式（8）和式（13）。這里假定式（14）成立，推導(dǎo)網(wǎng)絡(luò)滿足的條件：

即

因此網(wǎng)絡(luò)滿足式（15）時(shí)成員節(jié)點(diǎn)直接傳輸信息給基站，否則成員節(jié)點(diǎn)傳輸數(shù)據(jù)給簇頭。

3 仿真結(jié)果

為了顯示所提算法的優(yōu)勢(shì)，使用Matlab進(jìn)行仿真來(lái)分析和評(píng)價(jià)算法性能。100個(gè)傳感器節(jié)點(diǎn)隨機(jī)分布在100 m×100 m區(qū)域如圖4所示，基站位于分布區(qū)域內(nèi)坐標(biāo)（50，50），所有節(jié)點(diǎn)布置好后不再移動(dòng)。模型基本的仿真參數(shù)如表1。

圖4 100 m×100 m區(qū)域傳感器節(jié)點(diǎn)隨機(jī)分布情況

表1 仿真參數(shù)

將表1各參數(shù)值代入式（15）得：

式（16）為滿足表1仿真模型參數(shù)的判斷條件，將文中提出的算法和LEACH和M-LEACH進(jìn)行比較，分別采用節(jié)點(diǎn)壽命和能量消費(fèi)來(lái)評(píng)估網(wǎng)絡(luò)性能，網(wǎng)絡(luò)生命期仿真如圖5所示，網(wǎng)絡(luò)能量消耗如圖6所示。

圖5 網(wǎng)絡(luò)生命期分析

圖6 網(wǎng)絡(luò)能量消費(fèi)

從仿真圖可以看出，LEACH協(xié)議最早出現(xiàn)死亡節(jié)點(diǎn)，整過(guò)網(wǎng)絡(luò)也最早癱瘓。文中所提協(xié)議網(wǎng)絡(luò)能量消耗最低。

4 結(jié)論

在無(wú)線傳感網(wǎng)中，不同的應(yīng)用，不同的網(wǎng)絡(luò)規(guī)模對(duì)網(wǎng)絡(luò)的要求有很大的差別，必須針對(duì)不同網(wǎng)絡(luò)設(shè)計(jì)合理的路由協(xié)議。如在大規(guī)模無(wú)線傳感網(wǎng)中，分簇算法必須進(jìn)行多跳路由，而LEACH協(xié)議采用的單跳路由顯然不適合此種應(yīng)用場(chǎng)景。在這種需求背景下，本文描繪了一種適合大規(guī)模無(wú)線傳感網(wǎng)的混合路由算法，參照LEACH能量計(jì)算模型，推導(dǎo)了混合路由算法的計(jì)算公式，進(jìn)而得出了成員節(jié)點(diǎn)通過(guò)簇頭傳送數(shù)據(jù)還是直接傳數(shù)據(jù)給基站的條件。這種混合路由算法能有效克服基站附近節(jié)點(diǎn)能量提前耗盡而縮短整體網(wǎng)絡(luò)壽命的缺點(diǎn)。設(shè)計(jì)了LEACH，M-LEACH，和所提混合路由協(xié)議的能量消費(fèi)仿真和生命期仿真，從仿真圖可看出，和前兩種算法相比，在能量消耗上分別減少40%和20%左右，因此所混合路由協(xié)議明顯優(yōu)于上述兩種算法。需要說(shuō)明的是所提算法是在比較理想的情況下進(jìn)行仿真，即假設(shè)簇成員節(jié)點(diǎn)到簇頭的距離相等，如果簇成員是直接與基站通信，假設(shè)其到基站的距離相等，后續(xù)的將進(jìn)一步去掉這些理想條件開(kāi)展相關(guān)的工作。

［1］翟春杰，徐建閩，劉永桂.基于分區(qū)的能耗均衡路由協(xié)議［J］.傳感技術(shù)學(xué)報(bào)，2016，29（1）：80-87.

［2］陳東海，李長(zhǎng)庚.基于簇頭功能分化的無(wú)線傳感器網(wǎng)絡(luò)成簇算法［J］.傳感技術(shù)學(xué)報(bào)，2015，28（2）：244-248.

［3］Dutta R，Gupta S K，Das M.Improvement on LEACH Protocol in Wireless Sensor Networks［J］.International Journal of Computer Applications，2014，97（21）：36-40.

［4］Hoang D C，Yadav P，Kumar R，et al.Real-Time Implementation of a Harmony Search Algorithm-Based Clustering Protocol for En?ergy-Efficient Wireless Sensor Networks［J］.IEEE Transactions on Industrial Informatics，2014，10（10）：774-783.

［5］Han Z，Wu J，Zhang J，et al.A General Self-Organized Tree-Based Energy-Balance Routing Protocol for Wireless Sensor Network［J］.IEEE Transactions on Nuclear Science，2012，61（2）：1-6.

［6］Li H，Liu J.Double Cluster Based Energy Efficient Routing Proto?col for Wireless Sensor Network［J］.International Journal of Wire?less Information Networks，2016：1-9.

［7］Singh S，Raghavendra C S.PAMAS-Power Aware Multi-Access Protocol With Signalling for Ad Hoc Networks［C］//In Acm Com?munications Review，1999：5-26.

［8］Mardini W，Yassein M B，Khamayseh Y，et al.Rotated Hybrid，Ener?gy-Efficient and Distributed（R-HEED）Clustering Protocol in WSN［J］.WseasTransactionsonCommunications，2014，13：275-290.

［9］Heinzelman W B，Chandrakasan A P，Balakrishnan H.An Appli?cation-Specific Protocol Architecture for Wireless Microsensor Networks［J］.IEEE Transactions on Wireless Communications，2002，1（4）：660-670.

［10］Heinzelman W B.An Application-Specific Protocol Architecture for Wireless Microsensor Networks［D］.Ph.D.Dissertation Massa?chusetts Institute of Technology，2000.

［11］Fan X，Song Y.Improvement on LEACH Protocol of Wireless Sen?sor Network［C］//Sensor Technologies and Applications，2007.Sensor Comm 2007.International Conference on.IEEE，2007：260-264.

［12］Ma X W，Yu X.Improvement on LEACH Protocol of Wireless Sen?sor Network［J］.Applied Mechanics&Materials，2013，347-350：260-264.

［13］Mhatre V，Rosenberg C.Homogeneous vs Heterogeneous Clus?tered Sensor Networks：a Comparative Study［C］//Communica?tions，2004 IEEE International Conference on.IEEE，2004（6）：3646-3651.

彭 蕾（1983-），女，江西吉安人，畢業(yè)于澳大利亞臥龍崗大學(xué)，講師博士研究生，主要研究方向?yàn)闊o(wú)線傳感網(wǎng)絡(luò)與物聯(lián)網(wǎng)penglei@jgsu.edu.cn；

呂敬祥（1977-），男，講師，博士研究生，主要研究方向?yàn)闊o(wú)線傳感網(wǎng)路由協(xié)議及數(shù)據(jù)融合，ljingxiang2013@163.com。

Research on Hybrid LEACH Protocol for Large Scale Wireless Sensor Networks*

PENG Lei1，2，Lü Jingxiang1，2*，LIU Qiuping1
（1.Faculty of Electronics and Information Engineering，Jing Gang Shan University，Jiangxi Province，Ji’an Jiangxi 343009，China；2.Key laboratory of watershed Ecology and Geographical Environment Monitoring，National Administration of Surveying，Mapping and Geoinformation，Jiangxi Province，Ji’an Jiangxi 343009，China）

In large scale wireless sensor networks，how to reduce energy consumption is the most important techni?cal challenge.Therefore，the design of energy-efficient routing protocol has become a hot research topic.In order to reduce the energy consumption of sensor nodes，based on the LEACH algorithm，this paper proposes a hybrid wire?less sensor network energy saving routing algorithm which is suitable for large scale wireless sensor networks.First?ly，according to distance information，a routing algorithm was designed，in which a cluster member can transmit data to the base station via cluster head or can directly transmit data to the base station.Then the condition that the meth?od must satisfy is derived from the energy consumption.Simulation results obtained by MATLAB show that，com?pared with the existing LEACH protocol and M-LEACH protocol，the hybrid routing protocol can effectively im?prove the life of the nodes around the base station，and thus prolong the lifetime of the whole network.

wireless sensor networks；hybrid LEACH；cluster-based；energy-efficiency

TP393

A

1004-1699（2016）11-1737-05

EEACC：6150P 10.3969/j.issn.1004-1699.2016.11.018

項(xiàng)目來(lái)源：江西省自然科學(xué)基金項(xiàng)目（20122BAB211039）

2016-03-22 修改日期：2016-07-07