無線傳感器網絡的LEACH協議的改進與實現

劉得兵，梁剛

（四川大學計算機學院，成都 610065）

無線傳感器網絡的LEACH協議的改進與實現

劉得兵，梁剛

（四川大學計算機學院，成都 610065）

針對LEACH協議簇頭分布不均勻和網絡能量不均衡而導致網絡生命周期短的問題，提出一種改進方法。該方法在簇頭選舉階段，引入能量因子和位置因子來平均網絡中節(jié)點的剩余能量；在數據傳輸階段，引入新的數據融合機制來降低網絡中的傳輸能耗。通過NS2仿真實驗證明，與原協議相比，改進后的協議在單位時間內網絡的平均能耗低于原來的50%，網絡的生命周期延長114%。

無線傳感器網絡；LEACH協議；簇頭選取；能量因子；位置因子

0 引言

隨著科學技術的飛速發(fā)展，人類正處于信息時代，而作為下一代互聯網中至關重要的技術——無線傳感器技術，也得到了飛躍式的發(fā)展。無線傳感器網絡（Wireless Sensor Network，WSN[1～4]）是一種全新的信息獲取平臺，能夠實時監(jiān)測和收集分布在網絡區(qū)域內的各種檢測對象的信息，然后通過無線收發(fā)裝置將這些信息傳輸給匯聚節(jié)點，以實現對指定范圍內目標的檢測與跟蹤，具有展開迅速，抗毀性強等特點，有著非常廣闊的應用前景。

近年來，隨著人們對無線傳感器網絡研究的不斷深入，使得無線傳感器網絡得到了快速發(fā)展，也產生了越來越多的實際應用。我們可以大膽地預見，將來無線傳感器網絡將無處不在，將完全融入我們的生活[4～10]。

無線傳感器網絡最突出的特點是節(jié)點能量有限且不可再生[11]，所以降低網絡能耗，延長網絡生命周期顯得尤為重要。正因為如此，路由協議成為了當前研究無線傳感器網絡的一大熱點[12～13]。與有線網絡相比，無線傳感器網絡沒有實際的物理基礎設施支持，而且網絡的工作都是無人工干預的，其通信拓撲是動態(tài)自組織的。因此，傳統(tǒng)的路由算法對無線傳感器網絡并不適用，必須結合無線傳感器網絡的特性來研究新的路由協議[1，14～16]。

低功耗自適應分層型協議（LEACH）是針對無線傳感器網絡提出的第一個分層型路由協議。它保證了網絡中每個節(jié)點都有相等的概率當選為簇頭，從而使得網絡的能量較為均勻地消耗。但是由于簇頭選舉具有很大的隨機性，不能保證簇頭的均勻分布，而且當網絡中有節(jié)點提前死亡，會造成網絡路由空洞，影響通信[12，17～19]。針對LEACH協議的不足，一些以LEACH協議為基礎的改進協議相繼被提出，如基于能量效率的閾值敏感傳感器網絡協議（Threshold Sensitive Energy Efficient Sensor Network Protocol，TEEN）[20]，PEGASIS（Power-Efficient Gathering in Sensor Information Systems）[21]，混合節(jié)能分布式聚類協議（Hybrid Energy-Efficient Distributed Clustering，HEEN）[22]等，但是這些方法仍然存在因網絡能量不均衡，簇頭分布不均勻而造成的網絡生命周期短的問題[4，17]。

本文提出了一種改進方法。首先，在簇頭選舉階段，對LEACH協議的簇頭選擇算法進行改進，從而保證算法在進行簇頭選擇時充分考慮備選節(jié)點剩余能量和其網絡中的位置兩大因素，使得剩余能量越高、越靠近最佳簇頭位置的節(jié)點當選簇頭的概率越大。其次，在數據傳輸階段，引入新的數據融合機制，減少傳輸給基站數據中的冗余信息，從而降低網絡中的傳輸能耗。通過以上改進，能平均網絡中節(jié)點的剩余能量，避免網絡中的節(jié)點過早死亡；同時也使得被選出的簇頭節(jié)點能相對均勻地分布在網絡中。最終達到降低在單位時間內網絡的平均能耗和延長網絡生命周期的效果。

1 LEACH協議

LEACH協議[23]是一種自適應分簇拓撲算法，其核心思想是通過等概率地隨機選出簇頭節(jié)點，然后通過選出的簇頭節(jié)點來將整個網絡組織成簇結構。每個簇只有一個簇頭，簇內其他節(jié)點稱為非簇頭節(jié)點，非簇頭節(jié)點只與所在簇的簇頭節(jié)點通信。簇頭節(jié)點將簇內所有非簇頭節(jié)點的監(jiān)測數據經過數據融合處理后傳輸給Sink節(jié)點（也稱作基站）。由于簇頭節(jié)點除了要建立簇結構，還要收集并處理簇內非簇頭節(jié)點的監(jiān)測數據，因此會消耗更多能量。為了避免出現節(jié)點因長期擔任簇頭而過早耗盡自身能量而死亡，LEACH協議采用輪轉的方式來選舉簇頭節(jié)點，從而讓所有節(jié)點都有機會當選簇頭，而已擔任過簇頭的節(jié)點只有在所有節(jié)點都已擔任過簇頭后才有機會再次成為簇頭，這樣保證了網絡中節(jié)點的能量均勻消耗。

LEACH協議是按輪（rounds）周期性地執(zhí)行，每輪分為網絡的成簇階段和穩(wěn)定工作階段。在成簇階段，隨機選出簇頭節(jié)點，其他節(jié)點選擇離它最近的簇加入；在穩(wěn)定工作階段，簇頭節(jié)點收集簇內所有非簇頭節(jié)點的監(jiān)測數據，然后對其進行數據融合處理并將結果發(fā)送給基站。

（1）網絡的成簇階段

LEACH協議中的所有傳感器節(jié)點是同構的，因此所有節(jié)點的初始能量相同，為了使得網絡中節(jié)點能量消耗平衡，期望每輪選出Popt·N個簇頭節(jié)點，其中，N為網絡節(jié)點總個數，Popt為期望簇頭個數在網絡節(jié)點中所占的比例（通過大量的實驗，當Popt=5%時，網絡性能最優(yōu)[24]）。每個節(jié)點通過公式（1）計算出其閾值T（si），同時產生一個隨機數random（0＜random＜1）。當random＞T（si）時，該節(jié)點當選為簇頭。

式中，r為當前輪數，G為在最近r×mod（1/Popt）輪中沒有當選簇頭的節(jié)點集合。

當節(jié)點當選為簇頭節(jié)點后，就使用TDMA廣播ADV消息（Advertisement Message）通知其他節(jié)點自己是簇頭節(jié)點。每個非簇頭節(jié)點根據接收到的ADV消息信號的強弱來判斷自己與簇頭節(jié)點之間的距離，然后選擇最近的簇加入，并發(fā)送消息通知該簇頭，簇頭節(jié)點接收到消息后就將該節(jié)點加入自己的簇成員列表。當所有節(jié)點都加入了相應的簇，網絡的成簇階段就結束了，將進入網絡的穩(wěn)定工作階段。

（2）網絡的穩(wěn)定工作階段

簇頭節(jié)點建立一個TDMA調度來防止簇內節(jié)點在數據傳輸過程中發(fā)生沖突，簇內節(jié)點接收到簇頭節(jié)點發(fā)送的TDMA調度方案后就可以進行數據傳輸了。

TDMA調度使得每個非簇頭節(jié)點只能在指定的時間間隙內發(fā)送數據。非簇頭節(jié)點在沒有數據要傳輸時，將會進入休眠狀態(tài)以節(jié)省自身能量，而簇頭節(jié)點一直保持工作狀態(tài)來接收簇內節(jié)點的監(jiān)測數據。簇頭節(jié)點一旦接收完所有簇內節(jié)點的監(jiān)測數據，就對所接收到的所有監(jiān)測數據進行數據融合處理，然后將處理的結果傳輸給基站。

2 LEACH協議的改進

2.1 簇頭選舉改進方案

（1）能量因子Erate

LEACH協議在簇頭選舉保證了每個節(jié)點都有機會成為簇頭，但是未將節(jié)點當前能量考慮進去，很有可能使得能量非常小的節(jié)點當選為該輪的簇頭。這樣就可能出現簇頭無法完成對該簇的正常管理，或者無法對接收到的數據進行綜合分析處理，從而造成該簇內的通信無法正常進行。針對這一問題，在改進的簇頭選舉算法中，通過引入能量因子實現將節(jié)點的當前能量作為簇頭選舉的一個因素。

能量因子Erate的計算式如（2）式所示：

式中，E0為節(jié)點的初始能量值，Ecur為節(jié)點的當前能量值，Eaver為當前網絡中節(jié)點的平均能量值。

（2）位置因子Drate

LEACH協議在簇頭選舉過程中也沒考慮節(jié)點的位置，有可能出現所選出的簇頭節(jié)點過于集中或者過于分散，從而使得簇內節(jié)點與簇頭節(jié)點之間或者簇頭節(jié)點與基站節(jié)點之間的傳輸能耗過大，這樣就會造成節(jié)點能量的極大浪費。針對這種情況，在改進的簇頭選舉算法中，通過引入位置因子實現將節(jié)點的位置作為簇頭選舉的一個因素。

如圖1所示，為了便于說明位置因子的定義，首先將研究的無線傳感器網絡的拓撲區(qū)域虛擬成一個能覆蓋所有節(jié)點的正方形區(qū)域，其邊長記作len_topo，A點的坐標為（min_x，min_y），len_topo可由公式（3）求得，其中min_x、max_x表示所有傳感器節(jié)點（不包括Sink節(jié)點）的坐標中最小和最大的橫坐標，min_y、max_y表示所有傳感器節(jié)點（不包括Sink節(jié)點）的坐標中最小和最大的縱坐標。

圖1 位置因子說明圖

將該正方形區(qū)域分為四個大小相等的小正方形區(qū)域，這四個正方形區(qū)域的中心點稱為最佳簇頭位置。若被選簇頭的位置是在最佳簇頭位置的附近，這樣簇頭將較為均勻地分布在網絡中。也就是被選簇頭的節(jié)點離其所在區(qū)域的中心點距離越小，最終所有的簇頭將會較為均勻地分布在網絡中。通過公式（4）給出位置因子的定義，其中radius表示小正方形區(qū)域的外接圓的半徑，mdsi表示節(jié)點si到其所在區(qū)域中心點的距離，mdaver表示所有節(jié)點到其所在區(qū)域中心點的平均距離。

表1 關鍵點坐標值

由此，可以得到節(jié)點si的映射距離（即Ostd和si'之間的距離）的計算公式如公式（6）。

（3）改進的簇頭選舉算法

改進的簇頭選舉算法并不改變原協議的簇頭選舉流程，只是在計算節(jié)點的閾值時將節(jié)點的當前能量和位置通過能量因子和位置因子加入到計算中來，因此對于節(jié)點si將采用公式（7）來計算其閾值：

式中，Popt為期望簇頭個數在網絡節(jié)點中所占的比例，r為當前輪數，G為在最近r×mod（1/Popt）輪中沒有當選簇頭的節(jié)點集合，Erate為節(jié)點的能量因子，Drate為節(jié)點的位置因子。

新的簇頭選舉算法不僅保證了每個節(jié)點都有機會成為簇頭，也對參與簇頭選舉的節(jié)點的剩余能量和位置進行了篩選。通過公式（7）可以看出，只有當Erate× Drate＞1時，對該節(jié)點當選簇頭起促進作用，當Erate×Drate＜1時，對該節(jié)點當選簇頭起阻礙作用。改進后的協議使得當前能量越大，離最佳簇頭位置越近的節(jié)點當選簇頭的概率越大。從而達到均衡網絡節(jié)點剩余能量，使得簇頭能相對均勻地分布在網絡中的目的。

2.2 數據通信改進方案

在簇頭選舉完畢，簇的建立已經完成的情況下，開始數據通信穩(wěn)定階段。此階段的數據融合在原協議中是由簇頭節(jié)點擔當的，這樣簇頭不僅要承擔簇管理的任務，還要承擔該簇中的數據處理工作，這樣會使得簇頭節(jié)點的能量消耗過大。現在通過引入文獻[19]中的數據融合方案來對其進行改進，以便分擔簇頭節(jié)點的負擔，減少它的能耗，進一步均衡網絡節(jié)點的剩余能量。

改進方法中，在簇內重新選擇一個除簇頭節(jié)點外能量最大的節(jié)點（又稱為數據簇頭）來擔當本簇內的數據融合工作。數據簇頭負責接收簇內節(jié)點發(fā)送過來的監(jiān)測數據，并去除其中的冗余信息，然后將經過數據融合處理的數據發(fā)送給基站。基站會接收數據簇頭發(fā)送來的監(jiān)測數據，并且當有新的監(jiān)測任務時，基站會將其分配給簇頭節(jié)點，再由簇頭節(jié)點分配給簇內節(jié)點。這樣在一個簇內就有兩個領導，一個是簇頭節(jié)點，除了負責簇的構建工作之外，還會將基站分配的監(jiān)測任務向下傳達給簇內節(jié)點；另一個是數據簇頭節(jié)點，負責收集簇內節(jié)點的監(jiān)測數據，并對其進行數據融合處理，然后向上發(fā)送給基站。這樣能均衡簇頭節(jié)點的能量消耗，從而達到平衡網絡中節(jié)點的剩余能量的目的。

2.3 改進后協議的流程圖

采用改進后的簇頭選舉算法和數據融合機制的協議的流程圖如圖2所示。

在簇建立階段，根據改進的簇頭選舉算法選出網絡中的簇頭節(jié)點，節(jié)點當選簇頭后就會向全網發(fā)布其當選簇頭的消息，非簇頭節(jié)點會根據接收到的消息信號的強弱來選擇離它最近的簇加入。當所有節(jié)點都加入了相應的簇，就結束成簇階段，網絡將進入穩(wěn)定工作階段。

在穩(wěn)定工作階段，當有新的監(jiān)測任務時，簇頭節(jié)點會喚醒處于休眠狀態(tài)的簇內節(jié)點，并向其分配監(jiān)測任務。簇內節(jié)點會根據監(jiān)測任務收集數據，然后將數據發(fā)送給簇內的數據簇頭節(jié)點，完成了監(jiān)測任務的簇內節(jié)點會進入休眠狀態(tài)。數據簇頭會將接收到的所有數據進行數據融合，然后發(fā)送給基站。

圖2 改進后協議的流程圖

3 仿真實驗結果

100個傳感器節(jié)點隨機分布在100m×100m的范圍內，基站坐標?。?0，175），節(jié)點的初始能量相同，且為2J。同時取min_x=min_y=0，len_topo=100。采用NS2網絡仿真工具[25]對LEACH協議和改進后的協議進行了仿真實現，仿真結果如下（文中的仿真結果是100次隨機實驗結果的平均值）。

3.1 網絡生存周期對比

網絡生存周期對比圖如圖3所示，該圖中細的曲線代表的是LEACH協議的節(jié)點生存周期，粗的曲線代表的是改進后的協議的節(jié)點生存周期。從圖中可以看出，改進后的協議網絡的生命周期延長了，原有協議大約在480s的時候，網絡節(jié)點整體死亡；而改進后的協議大約在1030s的時候，網絡節(jié)點才整體死亡，網絡的生命周期延長了1倍。

在靜態(tài)的網絡中，當失效的節(jié)點數量超過30%時，網絡的性能就會變得非常差[26]，因此我們把網絡從開始到失效節(jié)點數量不超過30%的這段時間稱為網絡的最佳生命周期。從圖3中，可以看出，網絡的最佳生命周期從改進前的390s延長到了改進后的880s，提高了接近1.25倍。

圖3 網絡生存時間對比圖

3.2 網絡能耗對比

網絡能量消耗如圖4所示，圖中上面細的曲線代表原有的LEACH協議，下面的粗的曲線代表改進后的協議。從圖中可以看出，改進后的協議在網絡能耗方面明顯優(yōu)于原有的協議，這表明對LEACH協議的改進達到了均衡網絡能量，降低單個節(jié)點在單位時間內的能耗的目的。

但是改進后的協議在560s～600s這段時間，能量消耗過大，造成這種情況的原因可能有以下兩方面：①節(jié)點的動態(tài)分簇，形成的簇頭節(jié)點過多，在數據通信過程中發(fā)生碰撞，造成能量消耗過大。②該時間段沒有節(jié)點當選為簇頭，這樣網絡中的所有節(jié)點就不得不將其收集到的數據直接傳輸給基站，從而造成了網絡傳輸能耗過大。

圖4 網絡能耗對比圖

4 結語

本文在分析LEACH協議算法缺點的基礎上，對原有的算法進行了改進。在簇頭選舉階段，結合節(jié)點的當前能量和位置進行簇頭選舉。在數據傳輸階段，將原本由簇頭節(jié)點承擔的數據融合工作轉交給簇內除簇頭之外的最大能量的節(jié)點。通過以上兩方面的改進，新協議不僅降低了網絡能耗，還平衡了網絡中節(jié)點的剩余能量，從而延長了網絡的生命周期。但是原協議中就存在的某些時間段簇頭數量過多或者沒有節(jié)點當選簇頭的問題仍然沒有解決，如何解決該問題將是進一步研究的重點。

[1] Akyildiz IF，Wei LS，Sankarasubramaniam Y，Cayirci E.A Survey on Sensor Networks[J].Communications Magazine，IEEE，Volume: 40，Issue:8，2002，8:102～114

[2] AkyildizW.S，Y..Sanakarasubramaniam Y，et al.Wireless Sensor Networks:A Survey[J].Computer Networks，2002，38（4）:393～422

[3] David E C，Wei H.Wireless Sensor Networks[J].Communications of ACM，2004，47（6）:30～33

[4] 黃海平，沙超，蔣凌云等.無線傳感器網絡技術及其應用[M].北京：人民郵電出版社，2012

[5] 任豐原，黃海寧，林闖.無線傳感器網絡[J].軟件學報.2003，14（7）:1282～1291

[6]于海斌，曾鵬.智能無線傳感器網絡系統(tǒng)[M].北京：科學出版社，2006

[7] 劉君華.智能傳感器系統(tǒng)[M].第二版.西安：西安電子科技大學出版社，2010

[8] Atzori L，Lera A，Morabito G.The Internet of Things:A Survey[J].Computer Networks，2010，31（5）:1～19

[9] Welbourne E，Battle L，Cole G，et al.Building the Internet of Things Using RFID:the RFID Ecosystem Experience[J].IEEE Internet Computering，2009，13（3）：48～55

[10] Broll G，Rukzio E，Paolucci M，et al.PERCI:Pervasive Service Interaction with the Internet of Things[J].IEEE Internet Computing，2009，13（6）:74～81

[11] CHENG Chitsun，CHI K T，FRANCISC M L.A Delay-Aware Data Collection Network Structure for Wireless Sensor Networks[J]. IEEE Journal，2011，11（3）:699～710

[12] 李輝，彭珍瑞，董海棠.一種LEACH協議的改進方法[J].電子科技，2014，27（5）:172～178

[13] 俞黎陽.無線傳感器網絡網格狀分簇路由協議和數據融合算法的研究[D].上海：華東師范大學博士學位論文，2008

[14] Estrin D，Govindan R，Heidemann J，et al.Next Century Challenges:Scalable Coordination in Sensor Network.In:Proceedings of the 5th ACM/IEEE International Conference on Mobile Computing and Networking.Seattle:IEEE Computer Society，1999（6）:263～270

[15] 馬祖長，孫怡寧，梅濤.無線傳感器網絡綜述[J].通信學報，2004，25（4）:114～124

[16] 史美林，英春.自組網路由協議綜述[J].通信學報，2001，22（11）：93～103

[17] 王振飛，紀越峰.基于能量均衡策略的無線傳感器網絡LEACH協議改進[J].東南大學學報（自然科學版），2008，38 Sup（I）:262～270

[18] 王偉超，代增全，徐啟建.LEACH協議簇頭選擇算法的改進[J].無線電工程，2010，40（3）:1～3

[19] 韋宏利，方玉杰.LEACH協議算法改進及仿真[J].西安工業(yè)大學學報，2010，30（6）:570～573

[20] Manjeshwar，A，Agrawal D P.TEEN:A Protocol for Enhanced Efficient in Wireless Sensor Networks[C].In:Int'l Proc.of the 15th Parallel and Distributed Processing Symp.San Francisco:IEEE Computer Society，2001:2009～2015

[21] Liu T，Li.FPower-Efficient Clustering Routing Protocol Based on Applications inWireless Sensor Network[C].Proceedings 5th International Conference onWireless Communications.Networking and Mobile Computering，WiCOM 2009，2009

[22] Younis O，Fahmy S.HEED:A Hybrid Energy-Efficient Distributed Clustering Approach for Ad Hoc Sensor Neteorks[J].IEEE Trans. On Mobile Computing，2004，3（4）:660

[23] Heinzelman W，Chandrakasan A，Balakrishnan H.Energy Efficient Communication Protocol for Wireless Microsensor Networks.In: Proceedings of the 33rd Hawaii International Conference on System Sciences.Maui:IEEEComputer Society，2000.3005-3014

[24] Ahlswede R，CaiN，Li SY R，etal.Network Information Flow[J].IEEE Trans.On Inf.Theory，2000，46（4）:1204～1216

[25] 徐雷鳴，龐博，趙耀編著.NS與網絡模擬[M].北京：人民郵電出版社，2003，11

[26] 陳良銀，王金磊，張靖宇，王強，劉燕，殷鋒，羅謙.低占空比WSN中一種節(jié)點休眠調度算法.軟件學報，2014，，25（3）:631～641

Improvement and Implementation of LEACH Protocol for Wireless Sensor Networks

LIU De-bing，LIANG Gang
（College of Computer Science，Sichuan University，Chengdu 610065）

Aims at the problem of LEACH protocol which exists the uneven distribution of clusterheads and imbalance in energy leading to the short network lifetime.Puts forward an improved method,introduces the energy factor and location factor to average the residual energy of each node during the selection of clusterheads.And introduces a new data fusion mechanism to reduce the energy consumption for transmission during the data transmission.Comparing with the original LEACH by NS2 simulation,it shows that the average energy consumption in unit time of the improved one is lower than 50%,the lifetime is extended 114%.

Wireless Sensor Networks;LEACH Protocol;Select Cluster-Heads;Energy Factor;Location Factor

1007-1423（2015）06-0003-07

10.3969/j.issn.1007-1423.2015.06.001

劉得兵（1989-），男，安徽安慶人，碩士研究生，研究方向為網絡信息安全

梁剛，男，碩士生導師，研究方向為網絡安全與智能計算

2015-01-22

2015-02-10