傳感器網絡中基于非均勻分簇負載均衡路由算法

摘 要:在非均勻分簇思想的基礎上，提出了一種新的WSN多跳成簇路由算法。在該算法中，距匯聚點較近的節點直接與匯聚點通信，進一步減小了靠近匯聚點的簇規模，從而減輕了簇首負載，避免了不必要的能量消耗。仿真實驗表明，該算法能使WSN網絡負載更均衡，有助于解決能量空洞難題、延長WSN網絡總的生存時間。

關鍵詞:無線傳感器網絡; 非均勻分簇; 能量空洞; 負載均衡

中圖分類號:TP393文獻標志碼:A

文章編號:1001-3695(2009)09-3475-03

doi:10.3969/j.issn.1001-3695.2009.09.077

Novel load-balanced routing algorithm for multi-hop sensor networks

HUANG Chen， FANG Ding-yi， CHEN Xiao-jiang

(School of Information Science Technology， Northwest University， Xi’an 710127， China)

Abstract:This paper proposed a novel load-balanced uneven cluster-based routing algorithm， named LUC， in which the node near the sink which was not the cluster head will communicate with sink directly， and the cluster near the sink was much smaller than that far from it. As a result， avoided unnecessary energy consumption and reduced the load of the cluster head near the sink. Simulation experiments demonstrate that the algorithm LUC can balance the energy-consuming， and provide an efficient solution to cope with the energy hole problem and prolong the entire WSN lifetime.

Key words:wireless sensor networks(WSN); uneven clustering; energy hole; load-balanced

無線傳感器網絡是由一組傳感器節點以自組織方式構成的無線網絡，其目的是協作地感知、采集和處理網絡覆蓋的地理區域中被監測對象的信息，并發送給感興趣的觀察者[1]。傳感器網絡在軍事、環境監測、醫療護理和智能家居等方面有著廣泛的應用前景。

在傳感器網絡中，基于分簇的層次路由是一種有效的節能技術，其基本思想是將網絡節點分為簇首節點和簇內成員節點，成員節點將數據發送給簇首，簇首對數據進行融合后以多跳的簇間通信方式將數據發送給匯聚點，該技術在減少數據量的發送、降低網絡能耗的同時，帶來了如下的負載不均問題:

問題1 即使簇內節點比簇首離匯聚點更近，簇內節點仍須將數據發送給簇首，再由簇首轉發給匯聚點。如圖1，簇內節點F的簇首是E，雖然F距離sink更近，但F必須將數據發送給E，由E轉發(限于篇幅，圖1只標注少量非簇首節點)。

問題2 靠近匯聚點的簇首不僅要處理自身簇的信息，還要轉發大量其他簇的信息，負擔很重，容易過早死亡，導致網絡連通性被破壞，較遠的簇無法與匯聚點通信，即能量空洞問題。如圖1，在多跳網絡中，簇首E不僅要融合簇內數據，還要轉發簇首A、D的數據。當E失效后，就可能導致A、D等簇首無法與sink通信，網絡連通性減弱。此外，問題1中不必要的能耗開支，從一定程度上使得問題2更突出。

針對以上問題，本文提出了一種新的WSN非均勻成簇路由算法LUC(load-balanced uneven cluster-based routing algorithm)。仿真實驗表明，該算法能夠有效均衡網絡負載，對于緩和能量空洞問題有良好作用。

1 相關工作

現有的分簇路由算法可以分為集中式和分布式兩類。在集中式的路由算法中，匯聚點完成對網絡的分簇等管理任務，如LEACH-C[2]、PEGASIS[3] 、BCDCP[4]等，雖然集中式的算法可以改善簇首分布，但匯聚點需要知道全網絡節點的信息，而網絡的拓撲隨著時間不斷變化，導致維護全網節點的信息代價太高，同時影響了網絡的擴展性。Heinzelman等人[5]提出的LEACH算法是一個早期的分布式路由算法，該算法以輪為單位，每一輪分為成簇和數據傳輸兩個階段。在成簇階段，少數節點以一定概率隨機成為簇首;在數據傳輸階段，簇首將簇內節點的數據進行融合后按單跳方式直接發送給匯聚點。簇首單跳通信方式雖然簡單方便，但限制了網絡的規模，不利于擴展。 文獻[6]對LEACH算法的閾值進行了改進，并采用了簇首多跳通信方式，延長了網絡生存時間。Heed[7]算法將節點最大剩余能量和平均最小可達能量作為選擇簇首的參數，使網絡的能量均衡消耗，簇首的分布更合理，但由于簇首選舉采用迭代的方式，增大了通信開銷。文獻[8]首次證明了在同構的多跳無線傳感器網絡中，如果節點持續性地向匯聚點發送數據，能量空洞問題不可避免。Soro等人[9]首次提出用非均勻簇分簇算法緩和能量空洞問題的思想，建立了一個以匯聚點為圓心的同心圓通信模型，內圓環內的節點接近匯聚點，形成的簇規模比外圓環小，減輕了靠近匯聚點的簇首負擔。但該模型是異構的，簇首節點比一般節點性能更高，需要事先計算位置，人工部署，因此擴展性和可維護性受到影響。文獻[10]提出的算法將監測區域被鄰居節點覆蓋的冗余節點作為臨時簇首，作用是轉發其他簇的信息，減少簇首能耗。但該算法需要維護網絡的覆蓋情況，通信開銷較大。李成法等人[11]提出了一種新的非均勻分簇路由算法EEUC。該算法利用非均勻的成簇半徑，使得靠近匯聚點的簇成員數目相對減少，并且在簇首選擇路由下一跳時，考慮了候選節點剩余能量和候選節點相對于匯聚點的位置，有效平衡了簇首能耗，延長了網絡的存活時間。本文在借鑒文獻[11]中非均勻分簇方法的基礎上，提出了LUC算法，與其不同的是距離匯聚點較近的節點將直接與它通信，并且由匯聚點為這些節點安排數據的發送順序，防止信道沖突。通過該方法減少匯聚點附近的簇首負載，使其盡可能多地轉發其他簇首的信息，強化網絡連通性，從而達到均衡網絡負載，延長網絡生存時間的目的。

2 LUC算法

2.1 網絡模型

本文所研究的WSN網絡模型假設如下:

a)所有節點隨機均勻地分布于一個矩形區域內，匯聚點在區域外側。

b)所有節點與匯聚點均保持靜止，并無法補充能量。

c)所有節點均同構，具有惟一ID，并具有數據融合功能。

d)節點鏈路對稱，發射功率可控，根據接收到的信號強度可近似計算出與發送方的距離。

e)簇首占節點總數的百分比為P，對于每個節點令最大通信半徑為Rmax，到匯聚點的距離為ds，下一跳為nextHop;對于簇首，成簇半徑為Rc。

本文采用與文獻[2]相同的傳輸能量消耗模型，數據發送能量消耗由發射電路損耗和功率放大損耗兩個部分組成:

ETX(l，d)=l(Eelec+εfsd2)d

其中:l表示發送的比特數;d表示發送距離;εfs與εmp分別為不同距離范圍內功率放大所需的能量;d0 為判斷采用自由空間模型或多路徑衰減模型的臨界點。數據接收消耗的能量為ERX(l)=lEelec。

2.2 算法描述

LUC類似于LEACH算法，以輪為單位，每一輪分為成簇和數據傳送階段。下面以圖1為例，詳細說明LUC算法:

a)Sink節點向全網廣播hello消息，所有節點根據接收到的信號強度近似計算出ds，如果ds≤c*Rmax，將該節點標記為一類節點，置nextHop為sink，并向sink發送ID包;若ds>c*Rmax，將該節點標記為二類節點。如圖1，C、E、F、G為一類節點，A、B、D、H、I為二類節點。

b)Sink根據收到的ID包，為一類節點確定發送數據的時間片順序，向其發送TDMASchedule包。

c)計算閾值T=P/{1-P×[r mod(1/p)]}*Ecurrent/Eaverage。

其中:Ecurrent是節點當前的剩余能量;Eaverage是自身與鄰居節點的平均能量。通過隨機數μ與T進行比較，確定簇首。在圖1中，A、C、D、E即為簇首。其中C、E為一類簇首，成簇半徑Rc=mRmax。A、D為二類簇首，成簇半徑Rc=(1/2)Rmax 。

d)所有簇首以Rc為通信半徑廣播advise消息包，節點B收到由A、D發送的advise包后向兩者剩余能量較大的節點發送join包，加入該簇。節點F雖然收到advise包，但由于它是一類節點，不加入任何簇，直接與sink通信。

e)由于節點G、H、I沒有收到任何advise包，它們將各自的T值翻倍，直到自身成為簇首或收到advise包。假設G、I成為簇首，廣播advise包，但是由于G.Rc

f)簇首A、I向簇內成員發送TDMASchedule包，而簇首C、D、E、G由于沒有簇內成員不發送(假設A的剩余能量高于D，B加入簇A)。

g)節點B、H按照TDMASchedule包上的順序將數據發送給各自的簇首A、I，F按照匯聚點發送過來的TDMASchedule順序將數據直接發送給匯聚點。

h)簇首A、C、D、E、G、I以Rmax為通信半徑發送rout包，二類簇首根據收到的rout包選取距離匯聚點最近的鄰居簇首為下一跳(一類簇首的下一跳為匯聚點)。A、D的下一跳為E，I的下一跳為G。簇首將收到的簇內信息進行融合后轉發給下一跳。一類簇首E將A、D發送過來的數據與自身數據進行融合后將數據發送給sink，G類似于E。

至此，網絡第一輪數據傳輸完畢，從第二輪開始，將直接從c)執行，a)和b)只在算法初始化時執行。

2.3 算法分析

性質1 LUC算法的復雜度為O(n)。

證明 在算法初始化時，簇首發送的數據包為advise、TDMASchedule、rout三個，非簇首發送的數據包為一個ID包或join包，網絡共有N*P個簇首，N*(1-P)個非簇首，故整個網絡第一輪發送的數據包開銷為3*N*P+N*(1-P)=N(2P+1);從第二輪開始，一類節點中的非簇首節點不用再發送ID包，此時整個網絡的數據包開銷小于N(2P+1)。綜上，算法的復雜度為O(n)，證畢。

性質2 在節點密度足夠的情況下，LUC算法能保證簇間的連通性。

證明 當簇間不能通信時，由于Rmax≥2Rc，兩簇之間會有部分節點收不到advise包，根據算法中的e)可知，通過不斷將閾值翻倍，這些節點中會有部分節點形成新的簇首，保證簇間能通信，證畢。

下面分析算法中參數c、m對網絡能耗的影響。

對于c，由于一類節點直接與匯聚點通信，0<c≤1。當c=1時，生成的一類節點最多，能直接與匯聚點通信的節點均為一類節點，滿足條件(4/5)Rmax≤ds≤Rmax的節點占一類節點總數的36%，它們距離匯聚點較遠，直接與匯聚點通信能耗較大。當c=0.5時，生成的一類節點僅占能直接與匯聚點通信節點的25%，因此，當c=1或c=0.5時，算法節能效果不明顯;當c=0.8時，生成的一類節點占能直接與匯聚點通信節點的64%，并且距離匯聚點不是很遠，所以在實驗過程中c=0.8。

對于m，由于一類簇首成簇規模小于二類簇首，0<m<1/2。在此范圍內m越大，形成的簇規模越大，越接近于均勻分簇，生成的簇數量越少，而簇數量過少會導致簇首負擔過大，網絡負載不均衡，連通性變弱，容易出現能量空洞問題;m越小，形成的簇規模越小，生成的簇首越多，而簇數量過多會導致數據融合效果不明顯，發送的數據包劇增，能耗相應增加，縮短網絡生存時間。在下一章的仿真實驗中會給出m取不同值的網絡能耗情況。本文只是初步分析了參數c和m，關于用理論化的方法優化這兩個參數還在進一步研究。

3 仿真實驗與分析

仿真環境采用NS2，實驗先研究參數m對本算法的影響，再從能耗和節點存活數量兩方面來比較LUC算法與LEACH、EEUC算法的性能。本文對區域面積S=100×100 m2、節點總數N=100和區域面積S=150×150 m2、節點總數N=200的場景進行了仿真。在仿真過程中，每個節點的初始能量均為2 J，最大通信半徑Rmax=60 m。

圖2給出了N=100、m取不同值時網絡的能耗情況，橫坐標表示時間，縱坐標表示網絡能耗。從圖中可以看出m=0.15對應的曲線能耗最高，這是由于生成的簇過多，數據發送量增大所導致的。m=0.25與m=0.4對應的曲線比較接近，雖然在前620 s左右的時間中，m=0.4對應的曲線圖能耗比m=0.25的小，這主要是因為m=0.4時生成的簇首少，數據融合效果比m=0.25好，但是簇首負載比較重，在620 s以后，不少負載過重的簇首節點開始死亡，網絡連通性變弱，網絡能耗高于m=0.25時的情況。因此在實驗過程中m=0.25。

圖3和4顯示了當N=100時，隨著時間的增長，網絡能耗與節點存活數量情況。從圖中可以看出，由于LEACH算法采用簇首直接與匯聚點通信方式，并且簇首選舉時沒有考慮節點的能量和相對位置等因素，能耗最大，節點死亡速度最快，生存時間也最短。EEUC算法通過在一定范圍內選取剩余能量最大的節點作為簇首，嚴格控制簇首數量，并且簇間采用多跳通信方式，故能耗顯著減少，節點死亡速度大幅度降低。LUC算法相比于EEUC算法，靠近匯聚點的簇首能耗更小，在均衡網絡負載的同時，通信開銷也有所減少，因此能耗最低。同時無論以第一個節點死亡的時間還是最后一個節點的死亡時間作為網絡生存時間的判斷標準，LUC算法都是最優的。

圖5和6顯示了N=200時的網絡能耗和節點存活數量情況，從圖中不僅可以看出LUC算法性能最好，而且可以發現當網絡規模更大時，LUC算法優勢更明顯。

從實驗結果來看，LUC算法具有以下優點:a)算法盡可能地減少了靠近匯聚點的簇首能耗，均衡了網絡負載;b)匯聚點只在網絡初始化時參與算法計算，算法通信開銷較少，節省了網絡能耗;c)相比于LEACH和EEUC算法，LUC算法更適合于大規模網絡。

4 結束語

本文在分析已有的分簇路由算法的基礎上提出了LUC算法。該算法在借鑒非均勻分簇的思想上，對于靠近匯聚點的節點直接與匯聚點通信并由其管理，對于距離匯聚點較遠的節點采用分布式的隨機選舉簇首方式由簇首管理，很大程度上減少了靠近匯聚點的簇首能耗。通過仿真表明，LUC算法能有效均衡網絡負載，延長了網絡生存時間，相比于LEACH和EEUC算法，更適合于大型網絡的部署，具有廣泛的適用性。下一步研究工作將針對不同規模和不同密度的WSN，從理論上給出參數c和Rc的最優計算模型。

參考文獻:

[1]LI Jian-zhong. Concepts， issues and advance of sensor networks and data management of sensor networks[J]. Journal of Software， 2003， 14(10):1717-1727.

[2]HEINZELMAN W， CHANDRAKASAN A， BALAKRISHNAN H. An application-specific protocol architecture for wireless microsensor networks[J]. IEEE Trans on Wireless Communications， 2002，1(4): 660-670.

[3]LINDSEY S， RAGHAVENDRA C， SIVALINGAM K M. Data gathering algorithms in sensor networks using energy metrics[J]. IEEE Trans on Parallel and Distributed Systems，2002，13(9): 924-935.

[4]MURUGANATHAN S D， MA D C F， BHASIN R I， et al. A centra-lized energy-efficient routing protocol for wireless sensor networks[J]. IEEE Communications Magazine， 2005， 43(8): 8-13.

[5]HEINZELMAN W， CHANDRAKASAN A， BALAKRISHMAN H. Energy efficient communication protocol for wireless microsensor networks[C]//Proc of the 33rd Hawaii International Conference on System Sciences. Maui: IEEE Computer Society， 2000.

[6]CHUNG S， LEE B， LI Ji-long， et al. A novel cluster-header selection method in wireless sensor networks[C]//Proc of the 8th Conference on WSEAS International Conference on Evolutionary Computing. 2007.

[7]YOUNIS O， FAHMY S H. A hybrid， energy efficient， distributed clustering approach for Ad hoc sensor networks [J]. IEEE Trans on Mobile Computing， 2004，3(4):660-669.

[8]OLARIU S， STOJMENOVIC I. Design guidelines for maximizing lifetime and avoiding energy holes in sensor networks with uniform distribution and uniform reporting[C]//Proc of IEEE INFOCOM. Barcelona:[s.n]， 2006:1-12.

[9]SORO S， HEINZELMAN W. Prolonging the lifetime of wireless sensor networks via unequal clustering[C]//Proc of the 5th International Workshop on Algorithms for Wireless， Mobile. Denver: Ad hoc and Sensor Networks， 2005.

[10]ISRAR N， AWAN I. Coverage based intercluster communication for load balancing in wireless sensor networks[C]//Proc of the 21st International Conference on Advanced Information Networking and Applications Workshops. 2007:923-928.

[11]李成法，陳貴海，葉懋，等. 一種基于非均勻分簇的無線傳感器網絡路由協議[J].計算機學報，2007，30(1):27-36.