無線傳感器網(wǎng)絡(luò)LEACH路由協(xié)議研究與改進(jìn)

肖文顯,劉震,馬孝琴,郭明理

（河南科技學(xué)院,河南新鄉(xiāng)453003）

無線傳感器網(wǎng)絡(luò)由大量的節(jié)點(diǎn)構(gòu)成,節(jié)點(diǎn)間通過無線通信技術(shù)交換數(shù)據(jù).由一些傳感器的節(jié)點(diǎn)采集信息,經(jīng)過數(shù)據(jù)處理與融合,最后信息傳送給觀察者.路由協(xié)議對于一個(gè)網(wǎng)絡(luò)來說至關(guān)重要,直接影響著網(wǎng)絡(luò)的性能、效率和安全等.無線傳感器網(wǎng)絡(luò)有其自身的特點(diǎn),不同于傳統(tǒng)的網(wǎng)絡(luò),其網(wǎng)絡(luò)路由協(xié)議也呈現(xiàn)出與傳統(tǒng)網(wǎng)絡(luò)的不同,傳統(tǒng)的網(wǎng)絡(luò)路由協(xié)議無法直接應(yīng)用到無線傳感器網(wǎng)絡(luò)當(dāng)中.無線傳感器網(wǎng)絡(luò)與IP路由協(xié)議的差異主要如下：無線傳感器節(jié)點(diǎn)能量有限,在設(shè)計(jì)路由協(xié)議時(shí),把節(jié)能放在首要位置[1]；在傳輸?shù)倪^程中,遠(yuǎn)離網(wǎng)絡(luò)中心,路由協(xié)議主要面對多對一的數(shù)據(jù)流和一對多的控制流,而非傳統(tǒng)網(wǎng)絡(luò)的點(diǎn)對點(diǎn)的通信,在傳輸數(shù)據(jù)時(shí),先對數(shù)據(jù)進(jìn)行融合處理；與Ad Hoc（點(diǎn)到點(diǎn)）網(wǎng)絡(luò)相比,無線傳感器網(wǎng)絡(luò)移動(dòng)性差.

1 無線傳感器

1.1 無線傳感器網(wǎng)絡(luò)的體系結(jié)構(gòu)

無線傳感器網(wǎng)絡(luò)一般由傳感器節(jié)點(diǎn)、匯聚節(jié)點(diǎn)和管理節(jié)點(diǎn)構(gòu)成.有時(shí)也將互聯(lián)網(wǎng)、衛(wèi)星鏈路和控制臺(tái)包含在無線傳感器網(wǎng)絡(luò)當(dāng)中.匯聚節(jié)點(diǎn)將接收到的數(shù)據(jù)進(jìn)行處理和融合,通過互聯(lián)網(wǎng)或者衛(wèi)星鏈路將處理的信息傳到管理節(jié)點(diǎn)[2].匯聚節(jié)點(diǎn)兼顧數(shù)據(jù)的處理與傳輸,設(shè)計(jì)時(shí)為增強(qiáng)型傳感器節(jié)點(diǎn),有更多的能力和處理空間.管理節(jié)點(diǎn)檢測管理整個(gè)網(wǎng)絡(luò),接收匯聚節(jié)點(diǎn)傳輸?shù)男畔?并發(fā)送相關(guān)控制信息.

1.2 傳感器節(jié)點(diǎn)結(jié)構(gòu)

節(jié)點(diǎn)由能量供應(yīng)模塊、無線電通信模塊、處理器模塊和傳感器模塊4部分組成.節(jié)點(diǎn)是無線傳感器網(wǎng)絡(luò)中部署到研究區(qū)域里用于收集和轉(zhuǎn)發(fā)信息、協(xié)作完成指定任務(wù)的對象,每個(gè)節(jié)點(diǎn)用不同的ID來標(biāo)志自己[3].

1.3 分層結(jié)構(gòu)

根據(jù)無線傳感器網(wǎng)絡(luò)特性設(shè)計(jì)的網(wǎng)絡(luò)體系具有二維的結(jié)構(gòu),即橫向的通信協(xié)議層和縱向的管理面.通信協(xié)議層劃分為5個(gè)層,分別是物理層、鏈路層、網(wǎng)絡(luò)層、傳輸層、應(yīng)用層.網(wǎng)絡(luò)管理面分為移動(dòng)性管理、能耗管理以及任務(wù)管理.

1.4 常見無線傳感器網(wǎng)絡(luò)路由協(xié)議

無線傳感器網(wǎng)絡(luò)從路由協(xié)議的拓?fù)浣Y(jié)構(gòu)出發(fā),將路由協(xié)議分為平面型路由協(xié)議和層次型路由協(xié)議.平面路由協(xié)議包括泛洪協(xié)議和閑聊協(xié)議,SPIN（Sensor Protocols for Information via Negotiation）協(xié)議,定向擴(kuò)散協(xié)議3種；層次路由協(xié)議包括LEACH（Low Energy Adaptive Clustering Hierarchy）協(xié)議,TTDD（Two-tier Data Dissemination）協(xié)議,SPEED（實(shí)時(shí)路由）協(xié)議,GEAR（Geographical and Energy Aware Routing）協(xié)議.

2 LEACH路由協(xié)議分析與改進(jìn)

2.1 LEACH協(xié)議

LEACH協(xié)議是第一個(gè)基于分簇的層次型路由協(xié)議,與平面路由協(xié)議相比,LEACH有消耗低、網(wǎng)絡(luò)存活時(shí)間長的特點(diǎn).選擇LEACH協(xié)議為研究與改進(jìn)對象能更加深入理解層次型路由的工作過程.LEACH協(xié)議采用自組織成簇,成簇時(shí)以其策略選取一個(gè)節(jié)點(diǎn)作為簇頭節(jié)點(diǎn),在有數(shù)據(jù)傳輸時(shí),所有簇成員節(jié)點(diǎn)首先將數(shù)據(jù)發(fā)送到簇頭,簇頭接收所有簇成員數(shù)據(jù),然后對數(shù)據(jù)進(jìn)行融合后發(fā)送到遠(yuǎn)方的基站[4].

2.1.1 簇頭的選擇 LEACH協(xié)議的基本思想是將能量消耗均衡到每個(gè)節(jié)點(diǎn),以達(dá)到延長網(wǎng)絡(luò)壽命的效果.簇頭節(jié)點(diǎn)接受簇內(nèi)其它節(jié)點(diǎn)的信息,對這些信息進(jìn)行處理后發(fā)送到基站.LEACH協(xié)議采用周期性的選擇簇頭節(jié)點(diǎn)來解決簇頭節(jié)點(diǎn)能量的過快消耗,在LEACH算法中,節(jié)點(diǎn)自主決定是否成為簇頭.周期性的選擇簇頭節(jié)點(diǎn)稱為輪,每一輪都包含一個(gè)簇的建立階段和穩(wěn)定的數(shù)據(jù)傳輸階段.

在每一輪成簇的過程中,目標(biāo)是形成K個(gè)簇,算法開始給每個(gè)節(jié)點(diǎn)隨機(jī)一個(gè)0到1之間的值,用式（1）所示的函數(shù)來選擇簇頭節(jié)點(diǎn).

對于任意一個(gè)節(jié)點(diǎn)N,節(jié)點(diǎn)N產(chǎn)生一個(gè)0～1之間的隨機(jī)數(shù),如果這個(gè)數(shù)小于給定的閾值T（n）,則該節(jié)點(diǎn)N成為簇頭節(jié)點(diǎn),同時(shí),節(jié)點(diǎn)N廣播自己成為簇頭的信息.p是簇頭節(jié)點(diǎn)的比例,其值一般在4%到5%之間,其值會(huì)隨著應(yīng)用場合的變化發(fā)生變化.r是目前循環(huán)進(jìn)行的輪數(shù),比如當(dāng)前進(jìn)行的是第10輪,則r=10；G是在最近1/p輪中還未當(dāng)選過簇頭的節(jié)點(diǎn)的集合[5].在一輪的循環(huán)中,一個(gè)節(jié)點(diǎn)只能成為一個(gè)簇的簇頭.當(dāng)r=0時(shí),T（n）=p,即每個(gè)節(jié)點(diǎn)成為簇頭節(jié)點(diǎn)的概率是相同的,都為p.r的值越大,T（n）的值就越大,這樣未當(dāng)過簇頭節(jié)點(diǎn)成為簇頭的概率就越大.

2.1.2 簇建立階段 LEACH協(xié)議中定義了以“輪”（round）為單位進(jìn)行循環(huán).每一輪又包含兩個(gè)階段,即建立階段和穩(wěn)定階段.節(jié)點(diǎn)利用公式（1）進(jìn)行計(jì)算.通過設(shè)定的閾值T（n）,判斷自己是否成為簇頭節(jié)點(diǎn).一旦一個(gè)節(jié)點(diǎn)成為了簇頭節(jié)點(diǎn),就需要向網(wǎng)絡(luò)中的其余節(jié)點(diǎn)廣播自己成為簇頭的消息.

當(dāng)一個(gè)節(jié)點(diǎn)成為簇頭節(jié)點(diǎn)之后,向周圍節(jié)點(diǎn)發(fā)送簇頭廣播信息表明自己是簇頭節(jié)點(diǎn),在此期間一直等待其它節(jié)點(diǎn)的回應(yīng),等待其它節(jié)點(diǎn)的加入.非簇頭節(jié)點(diǎn)可能接受到多個(gè)簇頭節(jié)點(diǎn)的信息,最終選擇加入哪個(gè)簇的是根據(jù)能量的大小來決定.

2.1.3 簇穩(wěn)定階段 簇建立階段完成后進(jìn)入到穩(wěn)定階段,此階段主要完成數(shù)據(jù)的傳輸.如果傳感器節(jié)點(diǎn)總是有數(shù)據(jù)要發(fā)送,當(dāng)時(shí)間輪到自己發(fā)送數(shù)據(jù)時(shí),成員節(jié)點(diǎn)會(huì)把數(shù)據(jù)發(fā)送給簇頭節(jié)點(diǎn).在發(fā)送階段,各成員節(jié)點(diǎn)一直關(guān)閉自己的無線通訊模塊直到自己的時(shí)隙到來才打開模塊以節(jié)約能量.但是簇頭節(jié)點(diǎn)需要接收簇內(nèi)其它節(jié)點(diǎn)的信息,所以簇頭節(jié)點(diǎn)的收發(fā)器需要一直打開,故簇頭節(jié)點(diǎn)的能量消耗較它節(jié)點(diǎn)要快.

2.2 LEACH協(xié)議能量模型

在LEACH協(xié)議中使用的是第一順序無線電模型,其能量模型如圖1所示.

圖1 能量模型

此模型包含了發(fā)送數(shù)據(jù)時(shí)候的消耗和接收數(shù)據(jù)時(shí)候的消耗.發(fā)送數(shù)據(jù)的消耗包括射頻電路和信號(hào)放大器的能耗,接收節(jié)點(diǎn)的能耗為接收電路的能耗.其中,Eelec表示1 bit數(shù)據(jù)在發(fā)送或接收過程中所消耗的能量.ζfriss-amp是信號(hào)放大器的系數(shù).功率放大器的能耗根據(jù)發(fā)送方和接收方之間距離的遠(yuǎn)近可以采用Friss自由空間模型和多路徑衰減模型.Friss自由空間模型中,路徑損耗指數(shù)為2,即d2功率損耗；多路徑衰減模型中,路徑損耗指數(shù)為4,即d4功率損耗[6].假定信道是對稱的,即節(jié)點(diǎn)A向節(jié)點(diǎn)B發(fā)送數(shù)據(jù)的能耗與反向消耗的能量完全相同.根據(jù)圖1所示的模型,發(fā)送L bit數(shù)據(jù)所消耗的能量如式（2）所示：

ζfriss-amp和ζtwo-ray-amp與所使用的傳輸放大模型有關(guān),dc表示一個(gè)距離的常數(shù),dc可以用式（3）表示：

其中,Ls表示系統(tǒng)能耗,與傳輸無關(guān).ht是發(fā)射天線的高度,ht是接收天線的高度,是載波信號(hào)的波長.

從上述幾個(gè)公式分析可得,距離d小于閾值時(shí),節(jié)點(diǎn)發(fā)送數(shù)據(jù)的能耗與距離d2成正比,大于時(shí)與距離d4成正比.

故傳輸距離為d,接受L bit數(shù)據(jù)接收方消耗的能量為：

2.3 LEACH協(xié)議的缺點(diǎn)

LEACH協(xié)議雖然具有很多優(yōu)點(diǎn),但也存在一些缺憾,主要表現(xiàn)在以下幾個(gè)方面.

2.3.1 簇頭選擇不夠理想 LEACH協(xié)議采用隨機(jī)的方式產(chǎn)生簇頭,缺少約束力,沒有將節(jié)點(diǎn)的剩余能量作為參考系數(shù)來選擇簇頭.

2.3.2 簇頭的分布不夠均衡 LEACH協(xié)議采用完全隨機(jī)的方式產(chǎn)生簇頭節(jié)點(diǎn),其地理位置的分布不能達(dá)到最優(yōu),有可能產(chǎn)生不合理的分布.

2.3.3 單跳通信的不合理 LEACH協(xié)議在通信的過程中采用單跳的通信方式,這極大限制了網(wǎng)絡(luò)的規(guī)模.

2.4 LEACH-improved協(xié)議

無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)能量有限,為了延長整個(gè)網(wǎng)絡(luò)的存活時(shí)間,在設(shè)計(jì)路由協(xié)議時(shí)把節(jié)能放在重要的考慮位置.LEACH協(xié)議表現(xiàn)在在選擇簇頭節(jié)點(diǎn)時(shí)沒有將節(jié)點(diǎn)的剩余能量考慮在內(nèi),可能選擇剩余能量較少的節(jié)點(diǎn)作為簇頭節(jié)點(diǎn)；其次簇頭節(jié)點(diǎn)的分布不均衡,有些區(qū)域簇頭分布過少,降低了網(wǎng)絡(luò)的存活時(shí)間；通信采用單跳的方式[7],由能耗模型,遠(yuǎn)離基站的節(jié)點(diǎn)能量消耗的急劇增大.基于LEACH協(xié)議存在的問題,本文提出了LEACH協(xié)議的改進(jìn)協(xié)議LEACH-improved協(xié)議.

LEACH-improved協(xié)議針對LEACH協(xié)議存在的問題,從兩個(gè)方面對LEACH協(xié)議進(jìn)行了改進(jìn).

2.4.1 簇頭節(jié)點(diǎn)的選擇 LEACH-improved協(xié)議在選取簇頭時(shí),增加對節(jié)點(diǎn)剩余能量的檢測,或者在簇內(nèi)選取剩余能量較多的節(jié)點(diǎn)擔(dān)任簇頭節(jié)點(diǎn),以延長網(wǎng)絡(luò)的使用時(shí)間[8].用Ecurrent表示節(jié)點(diǎn)的當(dāng)前能量,Eorigin表示節(jié)點(diǎn)的初始能量,LEACH-improved協(xié)議增大當(dāng)前能量較高的節(jié)點(diǎn)成為簇頭的概率,以延長網(wǎng)絡(luò)的存活時(shí)間.改進(jìn)后簇頭的選擇公式為如式（5）所示

2.4.2 多跳路徑傳輸 LEACH-improved協(xié)議加入簇間路由策略,簇頭負(fù)責(zé)收集簇內(nèi)成員節(jié)點(diǎn)采集的數(shù)據(jù),對數(shù)據(jù)進(jìn)行融合計(jì)算,然后通過多跳路由方式將融合數(shù)據(jù)發(fā)送到基站.本文假設(shè)數(shù)據(jù)冗余度有限,來自不同簇的數(shù)據(jù)無法進(jìn)一步數(shù)據(jù)融合,中繼簇頭節(jié)點(diǎn)只簡單轉(zhuǎn)發(fā)來自其它正式簇頭的數(shù)據(jù).把網(wǎng)絡(luò)中成為簇頭節(jié)點(diǎn)的節(jié)點(diǎn)記為Ci,Ci與基站之間的距離記為d（Ci,BS）,多跳的過程如下：簇頭節(jié)點(diǎn)以半徑d向周圍廣播自身消息,消息包含其節(jié)點(diǎn)ID、能量Ei、簇頭與基站之間距離d（Ci,BS）.這樣得到簇頭節(jié)點(diǎn)Ci相鄰的簇頭節(jié)點(diǎn)集合為SCi={Cj,...,Ck},這里設(shè)該簇頭的中繼簇頭集合為SCv={Cv|Cv∈SCi&d（Cv,BS）≤d（Ci,BS）},如果SCv為空,則簇頭節(jié)點(diǎn)直接傳送融合數(shù)據(jù)到基站,否則在集合SCv中選擇能量值最大的簇頭節(jié)點(diǎn),如果能量剩余值最大的節(jié)點(diǎn)是唯一的,則將該節(jié)點(diǎn)作為下一跳路由節(jié)點(diǎn),否則在多個(gè)能量值最大的簇頭節(jié)點(diǎn)中選擇距離基站最近的簇頭節(jié)點(diǎn)作為下一跳路由節(jié)點(diǎn).

3 仿真

3.1 仿真參數(shù)設(shè)置

在模擬實(shí)驗(yàn)中,選取100個(gè)節(jié)點(diǎn)分布在100 m×100 m的區(qū)域內(nèi),圖2是節(jié)點(diǎn)分布圖.

圖2 100個(gè)節(jié)點(diǎn)分布

其他參數(shù)設(shè)置見表1所示.

表1 仿真實(shí)驗(yàn)參數(shù)

實(shí)驗(yàn)的運(yùn)行環(huán)境為Windows xp,運(yùn)行的工具為Cygwin,NS2的版本為ns-allinone-2.27.

3.2 協(xié)議仿真對比

對LEACH-improved協(xié)議和LEACH協(xié)議的對此主要從節(jié)點(diǎn)數(shù)據(jù)傳送總量和節(jié)點(diǎn)的生存時(shí)間兩個(gè)方面進(jìn)行對比分析.

3.2.1 數(shù)據(jù)傳送總量仿真分析 數(shù)據(jù)傳輸總量既是節(jié)點(diǎn)傳送給基站的總的數(shù)據(jù)量.圖3顯示了改進(jìn)后LEACH-improved協(xié)議和的原協(xié)議在試驗(yàn)中消耗的能量與基站接受到的總數(shù)據(jù)量的關(guān)系曲線.從圖中顯示出,協(xié)議LEACH-improved在消耗相同能量的情況下,基站接受到的總數(shù)據(jù)量要多.這顯示了LEACH-improved較原協(xié)議有了一個(gè)提升空間,從圖3可以看出,當(dāng)消耗相同能量80時(shí),LEACH-improved協(xié)議多接受了6 000的數(shù)據(jù)量,當(dāng)消耗都是100時(shí),LEACH-improved協(xié)議接受的數(shù)據(jù)量比LEACH協(xié)議多7 000,這說明了LEACH-improved協(xié)議提高了總的數(shù)據(jù)接收量,這主要是因?yàn)楦倪M(jìn)的協(xié)議能量的消耗比較平均,使整個(gè)網(wǎng)絡(luò)的生存時(shí)間得到提高,數(shù)據(jù)傳輸更加高效.

圖3 數(shù)據(jù)發(fā)送量

3.2.2 節(jié)點(diǎn)生存時(shí)間仿真分析 節(jié)點(diǎn)的存活時(shí)間對無線傳感器網(wǎng)絡(luò)是一個(gè)重要的參數(shù),存活時(shí)間的長短直接決定網(wǎng)絡(luò)的性能和整個(gè)網(wǎng)絡(luò)的生存時(shí)間.圖4顯示了網(wǎng)絡(luò)中存活的節(jié)點(diǎn)數(shù)隨時(shí)間變化的曲線.橫坐標(biāo)表示的時(shí)間,縱坐標(biāo)表示節(jié)點(diǎn)的存活個(gè)數(shù).從圖中可以看出,LEACH協(xié)議在215 ms時(shí)開始出現(xiàn)節(jié)點(diǎn)死亡,而LEACH-improve在275 ms才出現(xiàn)節(jié)點(diǎn)的死亡現(xiàn)象,節(jié)點(diǎn)開始死亡的時(shí)間推移了不少,這說明了LEACH-improve協(xié)議延長了節(jié)點(diǎn)的生存時(shí)間,在同樣的時(shí)間里,節(jié)點(diǎn)的能耗更低,該圖說明了LEACH-improved協(xié)議的確降低了節(jié)點(diǎn)的能耗,使節(jié)點(diǎn)的能量消耗更加均衡,延長了單個(gè)節(jié)點(diǎn)的存活時(shí)間,從而使整個(gè)網(wǎng)絡(luò)的性能得到提升.

圖4 節(jié)點(diǎn)生存時(shí)間

4 總結(jié)

通過對LEACH協(xié)議的簇頭選擇和簇的穩(wěn)定傳輸階段進(jìn)行了詳細(xì)分析,并對LEACH協(xié)議在運(yùn)行過程中所遵循的能耗模型進(jìn)行了說明,指出了LEACH協(xié)議存在的缺點(diǎn)：在簇頭選擇的過程中沒有考慮到剩余節(jié)點(diǎn)的能量,在傳輸?shù)倪^程中,采用單跳的方式進(jìn)行通信,并在此基礎(chǔ)上提出了改進(jìn)協(xié)議LEACH-improved協(xié)議.通過仿真實(shí)驗(yàn)可以得出改進(jìn)的LEACH-improved協(xié)議可以增加總的數(shù)據(jù)傳輸量和延長節(jié)點(diǎn)的存活時(shí)間,改善了網(wǎng)絡(luò)的生存環(huán)境,使網(wǎng)絡(luò)的性能得到了提升.

[1]孫利民,李建中,陳渝,等.無線傳感器網(wǎng)絡(luò)[M].北京：清華大學(xué)出版社,2005.

[2]潘巨龍,聞?dòng)?無線傳感器網(wǎng)絡(luò)的異構(gòu)性研究[J].航空計(jì)算技術(shù),2007,37（2）：124-126,130.

[3]馬祖長,孫怡寧,梅濤.無線傳感器網(wǎng)絡(luò)綜述[J].通信學(xué)報(bào),2004,25（4）：114-124.

[4]李建中,李金寶,石勝飛.傳感器網(wǎng)絡(luò)及其數(shù)據(jù)管理的概念、問題與進(jìn)展[J].軟件學(xué)報(bào),2003,14（10）：1717-1727.

[5]于海斌,曾鵬,梁韡.智能無線傳感器網(wǎng)絡(luò)系統(tǒng)[M].北京：科學(xué)出版社,2006.

[6]Wu X B,Chen G,Das S K.On the energy hole problem of non-uniform node distribution in wireless sensor networks[J].IEEE MASS,2006：180-187.

[7]石高濤,廖明宏.傳感器網(wǎng)絡(luò)中具有負(fù)載平衡的移動(dòng)協(xié)助數(shù)據(jù)收集模式[J].軟件學(xué)報(bào),2007,18（9）：2235-2244.

[8]吳光斌,梁長垠.無線傳感器網(wǎng)絡(luò)能量有效性的研究[J].傳感器技術(shù),2004,23（7）：74-76,80.