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

伍新華 黃 利

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

0 引 言

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

1 LEACH協議剖析

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

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

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

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

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

2 LEACH協議改進

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

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

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

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

3 性能對比仿真及分析

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

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

表1 實驗仿真參數

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

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

圖2 LEACH-ED中隨ρ取不同值發送數據量變化情況

表2 不同ρ取值性能參數

如圖3所示,在網絡生存期的大部分時刻內, ρ取不同值時的節點所消耗的能量關系是：Energy ρ 0.2＜Energy ρ 0.6＜Energy ρ 0.5＜Energy ρ 0.8.

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

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

在ρ=0.6的設定下,分別對比仿真傳統LEACH和LEACJ-ED兩種算法的性能表現,仿真結果如圖4～6所示,形成的統計數據如表3所列.

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

圖4 節點存活個數對比仿真結果

圖5 發送數據量對比仿真結果

圖6 能量消耗對比仿真結果

表3 傳統LEACH和LEACH-ED數據對比

4 結束語

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

[1]Callaway E H.無線傳感器網絡：體系結構與協議[M].馬偉明,編譯,北京：電子工業出版社,2007.

[2]毛曉峰,楊 珉,毛迪林.無線傳感器網絡應用綜述[J].計算機應用與軟件,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]許瓊方.基于簇覆蓋的無線傳感器網絡拓撲控制算法研究[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用戶基礎[M].北京：電子工業出版社,2008.

[8]劉世華,方路平.基于 NS-2網絡模擬基礎與應用[M].北京：國防工業出版社,2008.