張 品，姜亞光，陳 磊

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

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

1 LEACH與GSEN算法概述

1．1 LEACH路由算法

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

初始化階段是簇頭的形成階段。每個節(jié)點決定在當前“輪”中是否成為簇頭，成為簇頭的概率是一個建議的固定值，需要根據(jù)網(wǎng)絡中節(jié)點的數(shù)目而定。在初始化階段，每一個節(jié)點從0～1中選取一個隨機數(shù)，如果這個隨機數(shù)小于這一“輪”所設定的門限值T(n)，那么這個節(jié)點就成為簇頭。隨機性確保簇頭與網(wǎng)關節(jié)點之間數(shù)據(jù)傳輸?shù)母吣芎某杀揪鶆虻胤謹偟剿袀鞲衅鞴?jié)點上。T(n)的計算公式如下所示:

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

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

1．2 GSEN路由算法

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

2 基于權值優(yōu)化的兩級簇頭選擇協(xié)議

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

2．1 算法設計過程

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

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

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

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

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

圖1 簇頭路由示意圖

2．2 無線網(wǎng)絡模型和能量公式

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

圖2 無線通信模型

根據(jù)圖2這種模式，傳感器節(jié)點發(fā)送k bit數(shù)據(jù)所消耗的能量為:

傳感器節(jié)點接收k bit數(shù)據(jù)所消耗的能量為:

其中Efs、Emp是信號放大器的放大倍數(shù)，d是發(fā)送節(jié)點和接收節(jié)點之間的距離，定義 d為β是由無線電通道決定的常量，在發(fā)送距離較近時，適用自由空間信道模型，取β=2;而當發(fā)送距離較遠時，適用多徑衰落信道模型，取β=4，也稱之為雙路徑模型。當傳輸距離大于d0時數(shù)據(jù)傳輸?shù)南南喈敶蟆?/p>

3 仿真結果分析

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

表1 仿真環(huán)境參數(shù)

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

圖3 網(wǎng)絡生存周期比較

表2 節(jié)點死亡時間比較

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

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

圖4 總能耗比較

4 結束語

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

[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]張品，徐智福，孫巖．一種新的基于簇頭優(yōu)化的WSN路由協(xié)議[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，F(xiàn)ahmy 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．