基于加權優化選擇兩級簇頭的WSN路由協議*

張 品，姜亞光，陳 磊

(杭州電子科技大學通信工程學院，杭州310018)

無線傳感器網絡(WSN)被各國軍事部門、業界和學術界認為是21世紀最重要的技術之一，該領域的研究工作得到了極大的關注[1－2]。WSN是一種能在事先沒有構建網絡基礎設施的環境下，由傳感器節點臨時組成的一種自組織、自管理的網絡[3]。WSN節點通常使用容量有限、不可更換的電池，因此節約網絡的能量，最大限度地延長網絡生存時間成為衡量WSN的路由協議是否優越的重要標準之一。分簇路由協議在節能方面相比平面協議有著較大的優勢，因此得到了廣泛的研究。其中典型的代表為自適應聚類算法(Low Energy Adaptive Clustering Hierarchy，LEACH[4])，它的成簇思想對后來提出的很多重要分簇路由算法影響深遠;文獻[5]提出的算法首先根據節點的剩余能量來概率性地選取一些備選簇頭，然后以簇內通信代價的高低來競爭產生最終的簇頭;文獻[6]中提出的GSEN路由算法，其主要思想是簇內節點和簇頭節點都利用貪婪算法組成鏈，數據經過處理后沿著鏈傳輸信息，有效提高了網絡的生存時間。本文以LEACH與GSEN算法為基礎提出了一種新型的路由算法TL-WCA(Two Levels-Weighted Clustering Algorithm)，該算法首選通過LEACH的算法將網絡分成若干個簇，簇頭選擇考慮節點的剩余能量、度及離簇的質心的距離。簇頭選出后以最短路徑為原則，采用貪婪算法將簇頭形成一條鏈。然后以簇頭的能量不小于簇頭間的平均能量及離基站的距離最近為原則，在鏈中選出一個簇頭節點為高級簇頭，融合其它簇頭的數據后轉發給基站。該算法不僅做到了簇內節點的能量均衡同時也兼顧了簇頭之間的能量均衡，有效延長了網絡的穩定期。

1 LEACH與GSEN算法概述

1．1 LEACH路由算法

LEACH協議是MIT學者A．Chandrakasan等人為無線傳感器網絡設計的低功耗自適應聚類路由協議。該協議的特征主要有:動態的選舉簇頭、本地協調以產生簇群。LEACH定義了“輪”(Round)的概念，每一輪存在初始化階段和穩定階段兩個狀態。

初始化階段是簇頭的形成階段。每個節點決定在當前“輪”中是否成為簇頭，成為簇頭的概率是一個建議的固定值，需要根據網絡中節點的數目而定。在初始化階段，每一個節點從0～1中選取一個隨機數，如果這個隨機數小于這一“輪”所設定的門限值T(n)，那么這個節點就成為簇頭。隨機性確保簇頭與網關節點之間數據傳輸的高能耗成本均勻地分攤到所有傳感器節點上。T(n)的計算公式如下所示:

式中:p是節點成為一個簇頭的期望百分比;r為當前的輪數;G為在最后的1/p輪中還沒有成為簇頭的節點集。在第0“輪”中，即r=0時，每一個節點都有概率為p的可能性成為簇頭。在第0“輪”中成為簇頭的節點，再接下來的1/p輪中不會再成為簇頭，在經過1/p－1輪后，T值變為1，這時還沒有成為簇頭的節點就被選擇為簇頭節點;再經過1/p輪后，所有節點再次開始平等地競爭是否當選簇頭。成為簇頭的節點再向網絡廣播分簇信息，告知其他節點產生了一個新的簇頭。其他節點接收到消息后，根據信號強度來選擇它要加入的簇，并通知相應的簇頭。

與平面路由算法相比，LEACH算法可以將網絡生命周期延長30%，但是在簇頭選擇算法、簇類形成以及最優簇數的確定方面仍存在著不足。首先，成簇策略和簇頭選擇中未考慮節點的剩余能量。如果選擇了剩余能量不足的節點作為簇頭，將會加快該節點能量消耗，不能有效提高網絡的生命周期;再次，靜態地確定最優簇頭數以及簇頭所占總節點數的百分比。節點根據固定的最優簇頭K來估算成為簇頭的概率，在整個網絡運行階段，K值不再改變。由于網絡中節點數隨網絡運行而減少，K值也將變小，若采用固定的K值，必將嚴重影響網絡生命周期和穩定性;最后，在傳輸階段，采用單跳方式與基站通信，遠距離簇頭能量消耗過快，尤其不適合大型網絡或基站相對較遠的情況。

1．2 GSEN路由算法

在PEGASIS和LEACH協議的基礎上，Nahida等人結合了兩種協議的優點提出了基于簇的傳感器路由網絡(Group-based Sensor Network，GSEN)路由方案，在成簇階段，利用LEACH協議將網絡中的節點組成幾個簇，簇內節點根據貪婪算法組成鏈，鏈中的節點通過數據融合沿著鏈傳輸信息到簇頭，簇頭間又形成高一級的鏈，該鏈又選出一個簇頭，將整個網絡的數據融合后轉發給基站。與LEACH不同的是，GSEN每5輪重新組成簇和鏈，而每輪都隨機選出一個簇頭擔當鏈頭，因此該算法沒有考慮節點的剩余能量、節點位置、鄰居節點、鏈頭能量消耗過快等因素。

2 基于權值優化的兩級簇頭選擇協議

該協議的基本思想基于多權值優化選取簇頭，兩級簇頭融合網絡數據。在簇的建立階段采用兩個步驟，首選通過LEACH的算法將網絡分成若干個簇，簇頭選擇考慮節點的剩余能量、度及離簇的質心的距離。然后以距離最近為原則采用貪婪算法將簇頭組成一條鏈，以簇頭的能量不小于簇頭間的平均能量及離基站的距離最近為原則，在鏈中選出一個簇頭節點為高級簇頭，鏈上的每個節點發送信息給最近的節點，且每個節點將數據融合后，通過hop-by-hop的方式發送給高級簇頭節點，該節點將信息融合后發送給基站，其中初級簇頭每五輪重新選擇一次簇頭。由于高級簇頭節點耗能更大每一輪都要重新選擇簇頭。該算法不僅做到了簇內節點的能量均衡同時也兼顧了簇頭之間的能量均衡，有效延長了網絡的穩定期。

2．1 算法設計過程

2．1．1 初級簇頭的選擇

分簇路由協議中，簇頭的選擇將至關重要，一種好的簇頭選舉方法將有效平衡WSN負載，延長網絡的生存周期。TL-WCA在初級簇頭選擇過程中，每個節點都要產生一個0到1之間的隨機數，與相應的閾值T(n)進行比較，若該隨機數小于閾值T(n)，則當選為簇頭，反之則為非簇頭節點。接下來在已經劃分好的簇中重新選擇簇頭。簇頭的選擇以節點的剩余能量E，節點離質心的距離D和節點的度偏差Δ作為計算權值的參數。根據不同的應用環境，選取適當的加權系數ωj，在節點能量不小于簇內平均節點能量的前提下計算出每個節點的最終權值，為節點成為簇頭的依據。給出的權值計算方法如下:

其中，Ei=(S(i)·EO－S(i)·E)/S(i)·EO，表示節點消耗的能量與初始能量的比值，S(i)·EO為節點的初始能量，S(i)·E對應節點的剩余能量。Di=S(i)·d/D·max，表示節點到簇內質心的距離 S(i)·d與簇內節點到質心的最大距離 D·max的比值。Dav(xav，yav)為簇內質心的坐標，表示節點度的偏差，其中Δ0為節點的度(鄰居數)，在計算時取鄰居中非簇頭的節點數，δ為預設的簇規模，可以根據環境作出調整。Eg為是節點能量大于Eav的節點集合，加權系數ωj要求滿足，即必須是歸一化的，ωj可根據環境調整。當然節點的參數包括很多例如數據傳輸的差錯率，本文沒有提到的參數默認為0，即忽略這個參數。通過計算比較Wi選出簇頭。

2．1．2 高級簇頭的選擇

LEACH中每個簇頭匯集簇內節點的信息并進行融合后發送到遠程基站，而新的TL-WCA協議中通過改進簇頭信息的傳輸方式來節省能耗。如圖1所示，TL-WCA算法以最短路徑原則采用貪婪算法將簇頭形成一條鏈，成鏈后以簇頭的能量不小于簇頭間的平均能量及離基站的距離最近為原則，選出一個簇頭節點為高級簇頭，每個簇頭節點發送信息給最近的簇頭節點，且每個簇頭節點將數據融合后，通過hop-byhop的方式發送給高級簇頭節點，該節點將信息融合后發送給基站(Sink節點)。當過高級簇頭的節點不再當選高級簇頭，均衡了簇頭間的能量。

圖1 簇頭路由示意圖

2．2 無線網絡模型和能量公式

對WSN網絡模型假設如下:節點始終有數據發送，相鄰節點信息高度相關;基站固定，且有無限能量供應。節點能量有限，具有功率控制和定位功能，所有節點都不移動。在LEACH路由算法中，使用的能量消耗公式是一階無線電模式[7]，如圖2所示。

圖2 無線通信模型

根據圖2這種模式，傳感器節點發送k bit數據所消耗的能量為:

傳感器節點接收k bit數據所消耗的能量為:

其中Efs、Emp是信號放大器的放大倍數，d是發送節點和接收節點之間的距離，定義 d為β是由無線電通道決定的常量，在發送距離較近時，適用自由空間信道模型，取β=2;而當發送距離較遠時，適用多徑衰落信道模型，取β=4，也稱之為雙路徑模型。當傳輸距離大于d0時數據傳輸的消耗相當大。

3 仿真結果分析

實驗采用MATLAB7．0進行仿真，模擬實現了LEACH，GSEN，LEACH-C及其新的 TL-WCA協議，并進行了性能比較。仿真場景如下:100個節點隨機分布在100 m×100 m的區域中，基站位于(50，175)。節點初始能量為0．5 J，當能量低于0時，視為死亡，假設轉發過程中無數據丟失，數據融合率為100%。ω1，ω2，ω3的值分別是 0．5，0．3，0．2。根據文獻[8]，最優簇頭數K值的計算公式為，N為網絡中節點總數;M為正方形區域邊長;Efs為自由空間放大倍數;Emp為多徑衰減信道信號放大倍數;d2為簇頭距基站的距離。結合本文所提出的網絡應用環境推算出K的取值范圍，然后在仿真軟件中進行能耗分析，找出使網絡能耗最小的K值，即為最優簇頭數。進而根據網絡中的節點總數得出簇頭在所有節點中所占的百分比p，采用該方法并結合本文的實際網絡環境確定p為0．05。其它仿真環境參數如表1所示。

表1 仿真環境參數

圖3給出了 TL-WCA與 LEACH、GSEN、LEACH-C路由協議的網絡生存周期比較，以仿真輪數代表網絡運行時間，觀察它與剩余存活的節點數的關系 LEACH，GSEN，LEACH-C，TL-WCA 協議的第一個節點死亡時間(FND)分別為 712，1040，1175，1678;LEACH，GSEN，LEACH-C，TL-WCA 協議的半數節點死亡時間(HND)分別為901，1116，1631，1909;LEACH，GSEN，LEACH-C，TL-WCA 協議的最后一個節點死亡時間(LND)分別為1235，1222，2023，2107。可以看到 TL-WCA協議無論是FND、HND還是 LND都比其它三種協議長。TLWCA的首節點死亡時間比LEACH調高了135%，比GSEN調高了61%，比LEACH-C提高了43%;半數節點死亡時間比LEACH調高了111%，比GSEN提高了71%，比LEACH-C提高了17%;最后節點死亡時間比 LEACH提高了71%，比 GSEN提高了72%比LEACH-C提高了4%。可見，新算法由于在選舉初級簇頭時充分考慮到了簇頭的多個權值，高級簇頭又考慮到節點的剩余能量及位置，從而使網絡分簇、數據傳輸更加合理，這樣節點在通信時有效節省了能量，進而延長網絡的生命周期。為便于對比，消除一些偶然性，現對算法仿真10次，分別取統計平均值，表2給出了TL-WCA與GSEN，LEACH-C算法統計結果。

圖3 網絡生存周期比較

表2 節點死亡時間比較

在WSN中，穩定期[9]一般指的是從仿真開始到第一個節點死亡的時間為止，穩定期越長，該網絡的性能越好，因為一旦出現節點死亡，網絡就變的不穩定，數據傳輸也就出現不可靠。不穩定期是指從出現第一個節點死亡的時間到最后一個節點死亡的時間為止，不穩定期的長短表明了網絡的收斂性，不穩定期越長，收斂性越差，反之越好。在無線傳感器網絡中要求算法具有快速的收斂性。GSEN，LEACH-C，TL-WCA的穩定期分別為1 023輪，1 157輪，1 655輪，不穩定期分別為207輪，875輪，445輪。可以看出，TL-WCA的穩定期在三種算法中最長，而不穩定期要比LEACH-C短，但比GSEN的長。相比較而言，TL-WCA比其它兩種算法的網絡性能好，但是在快速收斂性方面GSEN優于TL-WCA。從圖中還可以看出，TL-WCA的后一半節點死亡較快，因此更符合WSN個別節點死亡并不影響網絡整體性能，但當大部分節點都已失效，網絡的存在就毫無意義。

圖4所示的是LEACH協議、GSEN協議和TLWCA協議的網絡能耗的比較。仿真圖中橫坐標表示網絡工作的輪數，縱坐標表示當前輪中整個網絡中所有節點所消耗的能量。可見，在相同環境下，LEACH協議和GSEN協議所消耗的能量都要大于TL-WCA協議，因此能夠有效延長網絡的生存時間。具體來說，比如有100個節點隨機分布在一個區域中，每個節點的能量相同，初始值都為0．5 J，則網絡中所有節點的總能量為50 J。以第一個節點死亡的時間為基準，如果采用LEACH算法，此時消耗的總能量為37．369 1 J，而在該時間時對應的GSEN算法和TL-WCA算法，此時的能耗分別為29．726 3 J和18．089 7 J，如果以第一個節點死亡時間為網絡的生命周期，則在這一網絡生命周期內能量消耗分別降低了21．6%和51%，由此發現，TL-WCA協議在能量節省上具有極大的優越性。從圖中還可以看出TL-WCA斜率最小，其次是 GSEN，最大的是LEACH，這說明TL-WCA中節點每輪消耗的能量都比LEACH和GSEN協議少。TL-WCA協議能夠使得簇內節點能耗均勻，而且簇頭之間的能耗也均勻，而LEACH的簇內節點能耗與簇首位置分布數目相關，當簇首均勻時簇內節點能耗均衡，反之不均衡，因此每輪的性能十分不穩定，這從圖中曲線也可以看出。

圖4 總能耗比較

4 結束語

本文分析了LEACH和GSEN兩種路由協議，在兩種算法的基礎上提出了一種新的路由協議TLWCA。通過仿真結果表明，新的協議無論是在網絡的第一個節點死亡時間還是最后一個節點死亡時間上都比LEACH，GSEN，LEACH-C有較大的改善，做到了普通節點之間、簇頭之間的能量均衡，有效延長網絡的生存周期。

[1]Sung Y，Tong L．A New Metric for Routing in Multi-Hop Wireless Senior Networks for Detection of Correlated Random Fields[C]//Newark:Military Communications Conference，2005:2327 －2332．

[2]Lindsey S，Raghavendra C S．Pegasis:Power Efficient Gathering in Sensor Information Systems[C]//Proc of the IEEE Aerospace Conf San Francisco:IEEE Computer Society，2002:1 －6．

[3]張品，徐智福，孫巖．一種新的基于簇頭優化的WSN路由協議[J]．傳感技術學報，2009，7(22):1013 －1017。

[4]Heinzelman W，Chandrakasan A，Balakrishnan．Energy Efficient Communication Protocol for Wireless Microsensor Networks[J]．IEEE Computer society，2002:3005 －3014．

[5]Younis O，Fahmy S．Heed:A Hybrid，Energy Efficient，Distributed Clustering Approach for Ad Hoc Sensor Networks[J]．IEEE Transactions on Mobile Computing，2004，3(4):660 －669．

[6]Tabassum N，Ahsanul Haque AKM，Urano Y．Gsen:An Efficient Energy Consumption Routing Scheme for Wireless Sensor Network[C]//Proceeding of IEEE International Conference on Systems and International Conference on Mobile Communication and Learning Technologies，2006:117 －112．

[7]Heinzelman W，Chandrakasan A，Balakrishnan．Energy Efficient Communication Protocol for Wireless Microsensor Networks[J]．IEEE Computer society，2002:3005 －3014．

[8]Heinzelman W，Chandrakasan A，Hari Balakrishnan．An Application-Specific Protocol Architecture for Wireless Microsensor Networks[J]．IEEE Trans on Wireless Communications，2002，1(4):660 －670．

[9]Smaragdakis G，Matta I，Bestavros A．Sep:A Stable Election Protocol for Clustered Heterogeneous Wireless Sensor Networks[C]//Proc of the 2nd international Workshop on SANPA 2004．Massachusetts，US，2004:1 －11．