減小簇頭邊緣化的LEACH協(xié)議的研究及改進＊

伍新華 黃 利

(武漢理工大學計算機學院 武漢 430063)

0 引 言

無線傳感器網(wǎng)絡(luò)(wireless sensor networks, WSN)是一種由大量無線傳感器節(jié)點組成的自組織多跳網(wǎng)絡(luò)[1].WSN路由協(xié)議按網(wǎng)絡(luò)的拓撲可分為平面路由協(xié)議和層次路由協(xié)議.平面路由協(xié)議需要維持較大的路由表,占據(jù)較多的存儲空間,因而并不適合在大規(guī)模網(wǎng)絡(luò)中采用,而分層路由協(xié)議卻可以在一定程度上解決這個問題[2].低功耗自適應(yīng)分簇算法(low energy adaptive clustering hierarchy,LEACH)協(xié)議是層次型路由協(xié)議的代表,比一般的平面多跳路由協(xié)議和靜態(tài)分簇算法優(yōu)越[3].但LEACH協(xié)議簇頭選取的隨機性,使簇頭位置分布不均,簇頭位于區(qū)域邊緣,故本文著重對這些問題進行研究和改進.

1 LEACH協(xié)議剖析

LEACH主要分為簇建立階段和穩(wěn)定傳輸數(shù)據(jù)階段.簇建立階段和穩(wěn)定傳輸數(shù)據(jù)階段所持續(xù)的時間總和稱為一輪(round).在簇建立階段,傳感器節(jié)點隨機生成一個(0,1)之間的隨機數(shù),并且與閾值T(n)做比較,如果小于該閾值,則該節(jié)點就會當選為簇頭.T(n)按照下列公式計算

式中：p為期望的簇頭節(jié)點占所有傳感器節(jié)點的百分比;r為當前的輪計數(shù);G為在最后的1/p輪中未成為簇頭節(jié)點的集合.

在穩(wěn)定傳輸階段,傳感器節(jié)點將采集的數(shù)據(jù)傳給簇頭節(jié)點.簇頭節(jié)點對來自所轄節(jié)點的環(huán)境數(shù)據(jù)進行融合后再將其傳送給基站,基站將數(shù)據(jù)傳送給監(jiān)控中心,由其進行數(shù)據(jù)處理.穩(wěn)定階段持續(xù)一段時間后,LEACH重新進入簇的建立階段,進行下一輪的工作,不斷循環(huán).

LEACH的簇頭選擇算法僅僅從概率角度上考慮了節(jié)點作為簇頭的公平性,而沒有把節(jié)點的能量值、簇頭邊緣化等重要因素考慮在內(nèi),這樣就導致了整個網(wǎng)絡(luò)能量消耗不均衡.因此LEACH協(xié)議在簇頭選擇階段,會出現(xiàn)2種特殊情況：(1)如不適合充當簇頭的節(jié)點僅僅依概率當選為簇頭時,結(jié)果會由于能量消耗過快而死亡,導致網(wǎng)絡(luò)生存期的縮短;(2)所選簇頭有可能會出現(xiàn)在區(qū)域的邊緣,這樣的簇頭的覆蓋面積會變小,就會出現(xiàn)簇內(nèi)節(jié)點離簇頭太遠,傳輸數(shù)據(jù)消耗的能量過多[4-5].

為解決上述問題,提出了一種改進的LEACH-ED(low energy adaptive clustering hierarchy-energy and distance)協(xié)議,在選舉簇頭時,綜合考慮了節(jié)點的當前能量和節(jié)點到中心區(qū)域的距離等因素,限制所選簇頭的邊緣化和保證節(jié)點能耗均勻化,從而能有效地延長整個WSN的壽命.

2 LEACH協(xié)議改進

根據(jù)LEACH-C思想[6],在節(jié)點初始化的時候,節(jié)點把自己的地理位置信息發(fā)送給基站,基站計算出各個節(jié)點到區(qū)域中心的最大距離,然后發(fā)送到各個節(jié)點.

針對第一種出現(xiàn)的特殊情況,考慮單個節(jié)點的能量消耗比例,在計算閾值的公式中加入節(jié)點的當前能量 Ecurrent和初始能量 Etotal,對于能量消耗比例大的節(jié)點,減小T(n)的值,降低成為簇頭的概率;相反,對于能量消耗比例小的節(jié)點,增大T(n)的值,增大成為簇頭的概率.其閾值T(n)計算如式(2)所示.

針對第二種特殊情況,在計算閾值的公式中加入節(jié)點到區(qū)域中心的距離,可使所選取的簇頭節(jié)點的覆蓋面積盡量最大化,讓簇頭盡量往區(qū)域的中心靠攏,就能縮短數(shù)據(jù)傳輸?shù)木嚯x.改進后的LEACH協(xié)議的簇頭選舉閾值T(n)計算如式(3)所示.

式中：ρ為常量參數(shù),表示節(jié)點的能耗比例和距離比例在T(n)中所占的比重;dmax為邊緣節(jié)點到區(qū)域中心的最大距離;d為節(jié)點到區(qū)域中心的距離.

3 性能對比仿真及分析

在 Linux[7]平臺下,利用 NS-2[8]軟件對LEACH、LEACH-ED協(xié)議進行仿真、分析和比較.仿真中的參數(shù)選擇如表1所列,所有的仿真實驗進行50次,取這些仿真數(shù)據(jù)的平均值形成本文的仿真結(jié)果圖.

在不考慮其他不可預知的破壞因素前提下,在節(jié)點初始個數(shù)為100的前提下,當傳感器網(wǎng)絡(luò)中存活的節(jié)點少于20個,就認為該網(wǎng)絡(luò)失效.

表1 實驗仿真參數(shù)

設(shè)出現(xiàn)第一個死亡節(jié)點的時刻為T1、節(jié)點個數(shù)小于20的時刻為T20、網(wǎng)絡(luò)生存期內(nèi)節(jié)點發(fā)送給基站的數(shù)據(jù)量為Data、所有節(jié)點在相同時刻消耗的能量總和為Energy等,因它們是衡量WSN系統(tǒng)生存周期的重要參數(shù),故本文從T1,T20,Data和Energy 4個參數(shù)上來仿真比較LEACH算法與LEACH-ED算法.首先研究LEACH-ED算法中的簇頭當選權(quán)值ρ的取值對上述參數(shù)的影響.其仿真結(jié)果如圖1,2所示,對比分析這些實驗數(shù)據(jù),形成的統(tǒng)計數(shù)據(jù)如表2所列.

圖1 LEACH-ED中隨ρ取不同值節(jié)點存活個數(shù)變化情況(因前面0～340 s基本相同,故截斷)

圖2 LEACH-ED中隨ρ取不同值發(fā)送數(shù)據(jù)量變化情況

表2 不同ρ取值性能參數(shù)

如圖3所示,在網(wǎng)絡(luò)生存期的大部分時刻內(nèi), ρ取不同值時的節(jié)點所消耗的能量關(guān)系是：Energy ρ 0.2＜Energy ρ 0.6＜Energy ρ 0.5＜Energy ρ 0.8.

圖3 LEACH-ED中隨ρ取不同值能量消耗變化情況

分析統(tǒng)計依照上述方法所得到的仿真實驗數(shù)據(jù),可以得出當ρ=0.6時可兼顧 T1,T20,Data和Energy等性能參數(shù),即能盡量地推遲第一個失效節(jié)點的出現(xiàn)、有效地延長網(wǎng)絡(luò)的整體存活時間、較大地提高發(fā)送給基站的數(shù)據(jù)量和減少網(wǎng)絡(luò)節(jié)點的能量消耗,從而獲得較佳的WSN性能.

在ρ=0.6的設(shè)定下,分別對比仿真?zhèn)鹘y(tǒng)LEACH和LEACJ-ED兩種算法的性能表現(xiàn),仿真結(jié)果如圖4～6所示,形成的統(tǒng)計數(shù)據(jù)如表3所列.

由表3得知,傳統(tǒng)LEACH協(xié)議在380 s時節(jié)點開始死亡,在570 s時,整個網(wǎng)絡(luò)死亡,在570 s時,向基站發(fā)送了 1 451 811 byte的數(shù)據(jù); LEACH-ED協(xié)議在420 s時節(jié)點開始死亡,在690 s時整個網(wǎng)絡(luò)死亡,在690 s時,向基站發(fā)送了2 001 432 byte的數(shù)據(jù);由圖6可知,在很大一部分時間,傳統(tǒng)LEACH協(xié)議在某個時刻的能量消耗比LEACH-ED要多.仿真結(jié)果說明改進后的協(xié)議比LEACH協(xié)議在網(wǎng)絡(luò)能量消耗、發(fā)送數(shù)據(jù)、生存壽命等方面有較好的改善.

圖4 節(jié)點存活個數(shù)對比仿真結(jié)果

圖5 發(fā)送數(shù)據(jù)量對比仿真結(jié)果

圖6 能量消耗對比仿真結(jié)果

表3 傳統(tǒng)LEACH和LEACH-ED數(shù)據(jù)對比

4 結(jié)束語

本文綜合考慮了無線傳感器網(wǎng)絡(luò)中節(jié)點的剩余能量和到中心區(qū)域的距離約束條件,使得網(wǎng)絡(luò)中剩余能量較多的節(jié)點有更大的概率成為簇頭,也使得簇頭不會出現(xiàn)在區(qū)域的邊緣,從而使得簇頭能覆蓋更大的面積.通過對改進前和改進后的協(xié)議所進行的大量仿真及結(jié)果分析(見表3),可以得出：改進的LEACH-ED協(xié)議較LEACH,均衡了網(wǎng)絡(luò)中節(jié)點的能量消耗,延緩了節(jié)點的死亡時間(開始死亡的時間為420 s,較LEACH晚40 s,即10.53%),有效地延長了整個WSN的生存壽命(較LEACH延長120 s,即21.05%).希望本文的研究思路及結(jié)果對研發(fā)適用性廣、性能穩(wěn)定高效的WSN協(xié)議有所幫助.

[1]Callaway E H.無線傳感器網(wǎng)絡(luò)：體系結(jié)構(gòu)與協(xié)議[M].馬偉明,編譯,北京：電子工業(yè)出版社,2007.

[2]毛曉峰,楊 珉,毛迪林.無線傳感器網(wǎng)絡(luò)應(yīng)用綜述[J].計算機應(yīng)用與軟件,2008,25(3)：179-181.

[3]Heinzelman W,Chandrakasan A,Balakrishnan H. Energy-efficient communication protocol for wireless microsensor networks[C]//In proceeding of the 33rd Annual Hawaii Int＇l Conf.on System Sciences.Maui：IEEE ComputerSociety,2000：3005-3014.

[4]許瓊方.基于簇覆蓋的無線傳感器網(wǎng)絡(luò)拓撲控制算法研究[D].湖南：湖南大學計算機系,2007.

[5]李 輝,李臘元,李方云.一種基于低能量的雙簇首WSN路由算法[J].武漢理工大學學報：交通科學與工程版,2009,33(3)：450-453.

[6]Heinzelman W,Chandrakasan A,Balakrishnan H. An application-specific protocol architecture for wireless mi-crosensor networks[J].IEEE T ransactions on Wireless Communications,2002,1(4)：660-670.

[7]紅帽軟件(北京)有限公司 .Red Hat Linux用戶基礎(chǔ)[M].北京：電子工業(yè)出版社,2008.

[8]劉世華,方路平.基于 NS-2網(wǎng)絡(luò)模擬基礎(chǔ)與應(yīng)用[M].北京：國防工業(yè)出版社,2008.