基于簇頭協作的LEACH-C路由策略研究

天津工業大學電氣工程與自動化學院 楊振偉 郭利進

引言

隨著計算機和通信技術的快速發展，WSN(無線傳感器網絡:Wireless Sensor Network)正受到了前所未有的關注和重視[1]。由若干個具備感知、計算和通信能力的節點構成，WSN技術現在已被廣泛應用于氣象監測、環境監測、深海導航及軍事監視等生活的各類領域[2,3]，為確保這些持續性具體監測和數據動態跟蹤，WSN工作時間必須要在一定程度上盡可能延長。另一方面，WSN中的成員節點在數據無線傳輸通信、信息的分析處理、信號傳輸帶寬、電池電量供給以及存儲空間等方面都受到了限制，傳統路由協議無法直接應用于當前的無線傳感器網絡。因此，一個優良的路由協議應當涵蓋低能耗的數據傳輸路徑，良好的可擴展性、強大的魯棒性、良好的容錯性、良好的穩定性和低延遲性等特征。所以，設計一個高穩定性、強魯棒性、低能耗的特定路由協議對無線傳感器網絡的進一步發展意義相當重大[4]。

1 LEACH相關協議

LEACH（低能量自適應聚類層次:Low Energy Adaptive Clustering Hierarchy）協議是一種典型的自適應聚類路由協議，其以數據為中心利用單層簇路由[5]。LEACH協議簇頭選舉策略及其單跳數據傳輸也存在一定的弊端，這些弊端對網絡性能的影響不可小覷。近些年，基于LEACH路由協議的不斷研究與改進，已然然成效顯著。文獻[6]中提到了LEACH路由協議中簇頭選舉機制的改進，當前一輪的簇頭達到一定條件時，再重新選舉簇頭，這樣便減少了每輪簇頭選舉所帶來的能量消耗。文獻[7]中展示了一種多跳式的路由協議，基本原理是讓距離較遠的節點先選擇一個離自己位置最近的節點進行數據的轉發，相較于與終端直接通信，距離大大縮短。文獻[8]提出在節點分完簇后，接下來在每一個簇內，根據節點之間的相互距離和數據相似度再次進行分組，并在每一個分組內重新選取一個代表節點，其任務是將數據發送給簇頭。文獻[9]根據能量分布和節點位置信息，引入了代價函數進行簇頭的選舉，其中，能量更高和位置更優的節點會優先當選為簇頭，這樣，各個節點的工作任務分配會更加合理。文獻[10]采用了一些綜合性較強的概率公式來定義閾值函數，使網絡負載更加均衡，有效增加WSN的生命周期。

上述基于LEACH的改進算法不同程度上降低了網絡能耗，但依然存在很多明顯的缺陷，如WSN網絡中的簇頭分布具有很大的隨機性；簇成員的加入僅僅考慮成員節點與簇頭的距離，沒有考慮該簇頭的能量；另外，一個簇內只有一個簇頭，簇頭由于需要完成信息處理與路由而需消耗較大的能量。所有這些不足導致WSN能耗消耗不均衡，大大影響網絡的正常工作時間。

2 改進的算法

2.1 算法描述

本文算法的主要研究思想是研究如何分擔WSN簇頭的網絡能耗，均勻網絡簇頭分布，優化網絡分簇，均衡全局能耗，延長系統有效工作時間。為了彌補傳統的LEACH協議存在WSN中簇頭分布不均勻和節點能量消耗過于集中等缺陷，本文采用一種改進的LEACH路由算法，即基于主次簇頭協作的LEACH路由算法LEACH-C(LEACH-Cooperative)。主要在如下幾個方面進行改進：

（1）簇頭選取過程：在LEACH簇頭選取的基礎上，進一步根據距離與能量因素進行次簇頭的選擇，也即實現同一個簇的雙簇頭選擇（收集處理和發送分開），有效緩解LEACH算法中簇頭分布不均、能量消耗過快的不足。

（2）簇的創建過程：在傳統LEACH路由算法中簇成員的確定是以與“準簇頭”距離的因素來確定加入規則，但是這樣容易造成整個監測區域簇的分布不均勻，進而導致采集信息高度的相關性和冗余性。在本文提出的LEACH-C路由協議中，利用成員節點與主次簇頭（具體為主次簇頭之間的虛擬坐標）之間的距離選擇加入不同的簇，能夠有效克服能耗消耗過于集中的缺陷，為了避免采集信息的冗余性和進一步降低系統能耗，采用臨近距離內休眠機制。

（3）特殊節點處理：無線傳感器網絡節點部署的隨機性，可能造成個別區域節點分布嚴重不均勻，存在游離節點即在參考距離內沒有歸屬任何一個簇，基于此，本文也提出了游離節點的主次協作傳輸或選擇加入最近的簇的規則進行信息的采集與路由。

LEACH-C的詳細流程如圖1所示。基于分簇路由方式的無線傳感網絡，簇頭選取和確定在無線傳統中起著至關重要的作用。如表1所示，WSN各成員節點都擁有并維護一份屬于自身的路由屬性表。路由表中，網絡節點被唯一編號，并用字段ID表示，該字段在網絡初始化時被隨機標記；Alive表示網絡節點狀態是否存活，“0”和“1”分別表示消亡和存活；Sleep表示網絡節點是否為休眠狀態，“0”和“1”分別表示休眠和活躍；Head-1字段代表WSN節點是否成為主簇頭，其中0(1)代表“否”或“是”，在WSN初始化階段，Head-1字段都默認為“0”；同樣，Head-2字段代表WSN節點是否成為協作簇頭即次簇頭，其中0(1)代表“否”或“是”，在WSN初始化階段，Head-2字段都默認為“0”；表2-1中的Active-1和Active-2字段代表WSN節點是否參與主簇頭或者次簇頭的選取，“0”代表該成員在本輪簇頭（主簇頭和次簇頭）選舉過程沒有當選，或沒有收到簇頭(包括次簇頭)的廣播信息，或收到至少兩個簇頭(包括對應的次簇頭)的廣播信息，則節點標記為網絡中的游離節點。“1”字段表示節點當選為主或次簇頭，或在給定距離范圍內僅收到一個簇頭廣播消息，該字段的初始默認值為“0”；字段Cluster表示該WSN成員節點是否已經成功加入網絡中的某個簇，取值為“1”（已入簇）或者“0”（未入簇），該字段初始值標記為“0”。該改進協議LEACH-C路由屬性表是在WSN剛開始初始化時被植入對應初始值，同時在WSN的簇創建過程和穩定過程中被讀取和改寫。

圖1 LEACH-C路由協議流程圖

表1 WSN成員節點路由屬性表

2.2 協作簇頭的確定

為避免LEACH能量消耗過快以及簇頭節點分布集中,本路由算法兼顧主簇頭和次簇頭剩余能量和相對距離,相對位置等因素,基于局部集中法則選取“簇頭對”,對于擁有成員個數為N的WSN,預設“簇頭對”節點占整個WSN網絡節點的比例為P，WSN系統初始化后，基站為網絡中的節點分配分簇參考距離Rre1

字段Active-1為“0”的節點首先產生隨機小數，當小于預先設定的閾值（公式2-1）時，則該節點當選為候選主簇頭；首先當選候選主簇頭節點則為第一個主簇頭，隨即該節點廣播消息并且將其Head-1的屬性置為“1”。同時，“主簇頭”根據Rre22=，通過廣播為其周圍網絡節點發放對應次簇頭選擇參考距離Rre2。Active-2字段為“0”的網絡節點根據接收的廣播信息確定是否成為次節點，當“準次簇頭”接收到主簇頭的廣播信息后加權自身剩余能量因素啟動定時器，首先定時完成的節點廣播消息確定為次簇頭節點，同時將自身Head-2屬性值設置為“1”。進一步，基站記錄下網絡中的已經產生的“簇頭對”數目，在Rre1內的節點接收到消息后將其Active-1和Active-2字段屬性值設置為1，該節點本輪將不再參與主簇頭或者次簇頭的競選。依照這樣的過程，依次產生其他“簇頭對”，由BS控制WSN網絡中本輪產生“簇頭對”個數。當“簇頭對”個數達到P*N后，本輪“簇頭對”選取結束。

公式（2-1）和公式(2-2)中的各個參數具體含義為：S表示監測區域WSN的面積，N為WSN中節點數目，P表示WSN中簇頭節點的所占百分比，M為分塊距離參考參數，一般選擇為2-5，具體為當主簇頭節點與基站較遠的時候，M選擇較小值，此處考慮是簇與基站較遠，需要較遠次簇頭進行信息路由。

2.3 LEACH-C簇的形成規則

在“簇頭對”的確定過程中遵循每個“簇頭對”節點的參考（本章采用的是主次節點中間坐標為簇的虛擬中心坐標）范圍內不再產生其他“簇頭對”。這樣WSN網絡中就有可能存在部分非簇頭成員節點在給定的參考半徑Rre1內沒有“簇頭對”，或者在參考范圍內存在多個“簇頭對”，此成員節點稱為游離節點，如圖2所示。路由屬性表中字段Active-1和字段Active-2屬性值為1的非簇頭節點，此時應根據公式（2-3）計算參數最小的d值，參考距離內最近的距離“簇頭對”入簇；而對于字段Active-x（字段Active-1和字段Active-2）的屬性值為0的非簇頭節點，在該階段根據公式(2-3)分別計算各自入簇閾值Tclu，選擇計算閾值Tclu最大的主簇頭節點入簇，即選擇距離較短、剩余能量較高的主簇頭節點入簇。

圖2 LEACH-C中的節點入簇示意圖

公式（2-3）中各參數表示含義分別為：參數d表示當前節點到“簇頭對”中間節點的距離，dmax表示任意兩成員節點的最大距離，Einit表示網絡節點能量初始值，Ecur則表示節點剩余能量。

傳統的LEACH路由協議中，由于簇頭直接路由信息至基站，這樣就會導致遠離基站的簇在信息路由階段消耗大量的能量，進而導致WSN網絡的能量消耗過快，且網絡能量消耗不均衡，導致WSN的有效監測時間較短。基于此，在此改進的LEACH-C協議中，主簇頭負責與簇內普通成員節點進行通信，即搜集普通成員節點采集的信息：降低節點信息的冗余度同時節省節點能量，LEACH-C路由協議在簇內部讓低能量節點輪流進入休眠，進而有效延長網絡有效工作時間。在此改進的LEACH-C協議中，WSN中的次簇頭節點主要負責與主簇頭節點以及WSN網絡中的基站節點進行通信，當主簇頭離基站較遠時，為了有效提高系統的能量均衡和網絡生存周期，次簇頭的參考距離中的M參數一般取較小值，也即確保次簇頭與主簇頭之間距離較大以期與基站距離較近，這樣可有效彌補由于該簇與基站距離遠傳輸信息消耗的能量大的缺陷。

3 LEACH-C仿真分析

針對WSN仿真平臺Atos-SensorSim進行實驗分析提出的LEACH-C路由協議，將本章提出的LEACH-C路由協議與傳統的LEACH路由協議進行仿真分析。參數具體設置如：在500m*200m監測范圍中隨機分布200個網絡節點。基站坐標位于網絡中心，即（250,100）位置的WSN，本實驗參數如表2

表2 LEACH-C參數的配置表

3.1 WSN的生命周期分析

首先分析WSN中存活節點數目與分簇輪數之間的關系，為比較本章所提的協作簇頭路由算法，即LEACH-C協議的性能特征，圖3中畫出了傳統的LEACH路由協議所對應的曲線。

圖3 網絡存活節點數與輪數之間關系

根據圖3可得出如下的結論：（1）所提的LEACH-C協作簇頭路由算法顯著提高了WSN中節點的存活率，即在本參數設置條件下，傳統的LEACH路由協議在第22輪左右時，WSN系統開始出現消亡節點，但改進的算法LEACH-C出現消亡節點大約在82輪；（2）分簇輪數為300之前，傳統的LEACH路由算法的節點存活率大約在50%，也即網絡有一半左右節點開始不能正常工作，而本文所提出改進的協作簇頭路由協議LEACH-C路由協議節點存活率高于60%，整體網絡中正常工作的節點存活率平均提高了10%以上。基于以上分析，可看出當基站位于隨機分布WSN網絡中心處，所提的改進算法，LEACH-C路由協議能大大提高了WSN網絡節點存活率，有效延長了網絡有效工作時間。

3.2 LEACH-C網絡能耗分析

圖4進一步分析WSN網絡總能量消耗與分簇輪數之間的關系，為便于比較分析，在此也畫出了傳統的LEACH路由協議對應的關系圖。

從圖4顯示結果可以看出，所提的新算法LEACH-C在網絡能耗的統計上低于傳統的LEACH路由算法。在設置的具體仿真環境場景中，傳統的LEACH路由協議在輪數18輪左右時，網絡能耗大約是2000J，而此時的LEACH-C的網絡能耗只有800左右。進一步分析可以發現，隨著運行輪數的增加，所提的LEACH-C路由算法性能優勢更加明顯，也即隨著輪數增加(持續到80輪左右)LEACH-C的能量消耗優相對于傳統的LEACH差距更加擴大，進一步說明所提算法的優越性。在輪數250以后，相較于LEACH算法，改進的LEACH-C算法相對傳統的LEACH路由算法，網絡能量消耗大約節省920J。根據以上分析可知，所提基于簇頭協作的路由算法LEACH-C協議通過分攤網絡簇頭負載，有效均衡網絡簇頭節點的負載分配，進一步降低了WSN網絡總能量消耗。

4 結語

本文首先詳細分析和討論經典的WSN分簇路由協議——LEACH路由協議。總結LEACH路由協議的不足：網絡中的能量消耗不均衡、網絡中的節點局部負載過大、網絡中釆集的數據具有很高的冗余度和相關度、簇頭選擇方式不合理、特殊節點沒有充分考慮等等。在此基礎上提出了一種改進的分層路由算法：基于協作簇頭的LEACH-C路由協議。在主簇頭選定的情況下根據相對距離與剩余能量進行次簇頭的選擇，系統中每個節點維護自身路由屬性表，WSN中的節點根據距離和能量兩個因素選擇入簇；在信息傳輸階段，采用休眠機制和遠距離簇頭路由方式進一步降低系統能耗；最后通過仿真分析得到LEACH-C相對于傳統的LEACH協議能夠有效延長網絡工作時間，均衡網絡負載。