考慮整體消耗代價的無線傳感器網絡分簇算法

摘 要：在LEACH協議的基礎上，研究一種無線傳感器網絡分簇算法，采用高級節點作為固定簇頭替代LEACH中的隨機簇頭選擇策略，推導出最優簇頭節點數目即所需高級節點數的計算公式及各類節點所需能量的表達式，并從網絡整體消耗代價的角度出發，通過仿真對網絡性能進行分析評價。結果表明，采用一定量的高級節點作為固定簇頭，當其節點硬件代價和電池能量代價之比a1/b超過一定值時，新算法的整體網絡代價明顯低于LEACH。

關鍵詞：無線傳感器網絡；LEACH；高級節點；簇頭；整體網絡代價

中圖分類號：TP393 文獻標識碼：B 文章編號：1004373X(2008)1818404

Clustering Algorithm for Wireless Sensor Network Considering the Total Network Cost

YU Lijuan1，TANG Zhiling2

(1.College of Information Communication，Guilin University of Electronic Technology，Guilin，541004，China;

2.College of Electronic Engineering，Guilin University of Electronic Technology，Guilin，541004，China)

Abstract：In this paper，a kind of clustering algorithm is studied on the basis of LEACH.It uses some advanced nodes as fixed cluster heads，which takes place of the scheme of selecting cluster head randomly in LEACH.Then the，formulation and expressions of optimum cluster head and initial energy of these two types nodes are deduced.Finally，the network performance is evaluated from the overall network cost point of view，the simulation and evaluation results show that the Total network costs of the new algorithm is obviously lower than LEACH.when the ratio of hardware cost and battery costa1/b is above a given value.

Keywords：wireless sensor network;LEACH;advanced node;cluster head;total network cost

1 引 言

傳感器網絡一般由分布于傳感區域的大量傳感器節點和一個或多個基站組成。節點負責收集數據，并將收集的數據傳送到基站，基站接收到數據后對數據進行處理。由于傳感器節點大量地隨機分布在傳感區域內，在傳感器節點密集的區域會產生大量的冗余數據。利用分簇的方法先將各節點的數據傳送到它們各自對應的簇頭，在簇頭進行數據融合后再將數據傳送給基站將大大減小數據傳送所需的能量，有效降低網絡的能量消耗。現有的分簇算法大多是在假定傳感器節點完全相同（即同構傳感器網絡）的條件下進行的，大都存在如下缺點:

（1） 由于簇頭節點的能量消耗遠大于其他傳感器節點，若采用相同種類的節點，簇頭節點的能量會很快被耗盡。

（2） 若頻繁地更換簇頭來維持網絡連接，周期性地選擇簇頭會又帶來更多的能量開銷，增加網絡的負擔。

本文提出一種采用高級節點充當固定簇頭的分簇算法，它增加了簇頭節點的能量，克服了現有分簇算法在這方面的缺點，避免了頻繁更換簇頭帶來的網絡開銷，減少了網絡的整體消耗代價。

2 網絡模型

本文針對如下網絡模型進行研究:該傳感器網絡由2類節點組成－普通數據采集節點(稱其為0類節點)和高級數據傳送節點(稱其為1類節點)，兩種傳感器節點具有不同的節點硬件復雜度和最大傳輸能量。數據采集節點負責網絡數據的采集工作，采用普通的傳感器節點，其硬件復雜度較低、能量較小、數據傳送節點具有較大的傳輸能量和較強的計算和控制功能，負責收集普通節點采集的數據信息，并將其加以融合處理后發送給基站，相對來講其硬件復雜度要高一些。由于數據傳送節點具有較大的能量，用其來固定地充當簇頭節點，避免頻繁更換簇頭帶來的網絡開銷。

2.1 代價模型

普通節點和高級節點的單位代價用Ci表示，借鑒文獻［1］中節點代價函數的定義:Ci=ai+bEi。其中，ai和b是依賴于節點制造過程及工藝水平的常數；ai是第i類節點的硬件代價，而b是電池能量代價方面的比例常數；Ei表示第i類節點的電池能量。則整個網絡的總代價就可表示為:

f(n1，E0，E1)=n0(a0+bE0)+n1(a1+bE1)(1)

2.2 無線傳輸能量模型

本文采用與文獻［1］相同的無線能量模型，用于計算節點在進行通信及數據處理時的能量消耗，并使用該模型分析評價無線傳感器網絡的性能。Et0=l+μ1r2(2)

Et₁=l+μ1d4(3)

Er0=Er1=l(4)

其中Et0和Er0分別表示0類節點發送和接收一個數據分組的能量消耗；Et₁和Er1分別表示1類節點發送和接收一個數據分組的能量消耗；l表示消耗在無線收發電路上的能量；μirj(i=1，2;j=2，4)表示射頻放大電路部分的能耗。

另外，假設每個數據分組長度固定，無論輸入多少個數據分組，在簇頭處均被融合為一個相同大小的數據分組，簇頭節點用于融合和處理單位分組數據的能量為Ef。

3 算法描述及重要參數的確定

3.1 算法描述

本文只是改進LEACH的隨機簇頭選擇算法，采用高能量的高級節點來充當固定簇頭，以避免頻繁更換簇頭帶來的網絡開銷，合理減少網絡的整體消耗代價。其余工作過程與LEACH基本相同。

在最初的網絡配置階段，首先根據網絡規模、普通節點數等信息確定所需的高級節點(即簇頭)數，然后再結合網絡規模和覆蓋度等因素確定這些高級節點在網絡中的位置。確定簇頭節點及其相應位置以后，作為簇頭的高級節點就向周圍所有節點廣播自己是簇頭這一消息，而普通節點根據接收到的信息來判斷其與簇頭之間的距離，并選擇加入相距最近的簇。節點選定它所要加入的簇后，便向該簇頭發送信息告知其加入;簇頭在收到成員節點的請求加入信息后，為其簇內的成員節點制定數據發送時隙(TDMA Schedule)并向其成員節點廣播此調度，成員節點在收到時隙調度后便完成了組簇。該簇一旦形成，在以后的過程中就不再改變。簇形成以后，數據的傳輸便可開始，此時網絡進入穩定傳輸階段。在穩定傳輸階段，成員節點持續采集監測數據，并在為其分配的時隙中使用合適的發送功率將數據傳與簇首;在不發送數據時隙，成員節點可進入休眠狀態以節約能量。當接收完來自所有成員節點的數據后，簇頭對數據進行必要的聚合處理，然后直接發送到基站。

和LEACH一樣，本算法的工作過程也按“輪”進行，并定義網絡中節點完成一次完整的數據傳輸至基站稱為是一輪。由于簇頭節點要負責數據的融合并將其傳送至較遠的基站，所以其能耗較大，另外距離簇頭較遠的普通成員節點也會比簇頭附近的節點在傳送數據時消耗更多的能量，而導致過早的死亡，在這種情況下，要想保證所有節點在同一時間死亡是不太可能的。這里就盡量使對網絡生命周期有著決定性影響的簇頭節點和同一簇中距離簇頭最遠的節點的存活時間保持一致。為此，限制網絡生命周期為T輪來考慮整個網絡的消耗代價，亦即簇頭節點和同一簇中距離簇頭最遠的節點的存活時間均為T輪。

3.2 最優簇頭數的計算

在該算法中首先假定所需的高級節點（簇頭）數為n1，下面以最小化整個網絡代價為目的推導所需的最優簇頭數n1的數學表達式。

假設在M×M正方形區域隨機布置n0個能量為E0的普通節點，且節點一旦放置好就不再移動，基站位于距區域中心較遠的d處。那么對應n1個簇頭節點，平均每個簇中有成員節點的個數為n0/n1，采用第2.2節中的無線能量模型，為了保證網絡生周期至少為T輪，則每個作為簇頭的高級節點的初始能量應為：E1=T［(n0/n1)(l+Ef)+l+μ2d4］(5)

整個區域大小為M×M，則平均每個簇覆蓋M2/n1的區域，若假設每個簇覆蓋是圓形區域，則區域半徑為M/n1π。考慮簇中距離簇頭最遠的節點，即距簇頭距離為M/n1π的節點可得到，要保證至少T個周期，每個普通節點所需的初始能量為:E0=T［l+μ1(M/n1π)2］(6)

將式(5)和式(6)代入(1)式得出整個網絡的總代價為：f(n1，E0，E1)=n0a0+n1a1+n1bT［(n0/n1)·

(l+Ef)+l+μ2d4］+n0bT(l+μ1M2/n1π)(7)

對f(n1，E0，E1)關于n1求導，從而得到使整個網絡總代價最小的最優簇頭數為:n1=n0bTμ1M2π［a1+bT(l+μ2d4)］(8)4 性能分析與評價

為分析改進后的算法的性能，采用表1中的參數進行網絡環境設置，并與經典的分簇算法LEACH加以對比。

表1 網絡環境參數表

節點數目n0100區域大小100 m×100 m與基站的距離d125 m每個數據分組的長度525 b/sl0.21 mJμ142 nJ/m2μ25.46 pJ/m4Ef0.021 mJ

根據文獻［2］，采用LEACH算法的最優簇頭數k和為保證T輪的網絡生命周期，每個節點所需的初始能量E分別為:k=n02πμ1μ2Md2(9)

E=T(2l+Ef+kμ2d4n0+μ1M22πk)(10)

考慮采用LEACH算法且具有相同節點數目(n0+n1)的同構網絡，以fLEACH(a0，a1，b)表示采用LEACH算法的整個網絡代價，而以fNew(a0，a1，b)來表示采用改進算法的網絡消耗代價，用Δ表示二者之間的差值，則(由以下推導可得出它是關于a0，a1和b的函數):fLEACH(a0，a1，b)=(n0+n1)(a1+bE)(11)

fNew(a0，a1，b)=n0(a0+bE0)+n1(a1+bE1)(12)

Δ=fLEACH(a0，a1，b)－fNew(a0，a1，b)

=n0(a0－a1)+(k－n1+n1n0)bTμ2d4+

n1bT(l+Ef)+(n0+n12πk－n0n1π)bTμ1M2(13)

圖1給出最優簇頭數n1和a1/b的關系，圖2給出在a0=a1，a0=0.5a1，a0=0.2a1三種情況下，采用LEACH和改進后兩種算法的網絡整體消耗代價差和a1/b的關系。

從圖1中可看出，在給定的網絡環境下，n1隨a1/b的值變化很小，幾乎保持恒定，因此取n1=3。在圖2中，橫軸(即圖中虛線)下方的曲線表示Δ<0，也就是采用改進算法的代價大于LEACH算法;反之，橫軸上方的部分則說明采用LEACH算法的代價大于改進算法。并且Δ的值隨著a1/b的增加而呈線性增長。這是因為 LEACH中所有節點是同構的，需要同等復雜的硬件代價。隨著節點硬件復雜度的提高，整個網絡的消耗代價也相應增加;而改進算法的只有極少數高級節點的復雜度高，大多數節點仍是普通節點并不需要很高的復雜度。因此高級節點復雜度的提高對網絡整體消耗代價的影響并不是很大，所以Δ值隨a1/b的增加而增加。而呈線性增長的原因則是:雖然n1也是關于a1和b的函數，但在給定的網絡環境下，n1幾乎保持恒定，所以根據式(13)可得出Δ是關于a1的線性函數。綜上，采用兩種算法帶來的網絡整體代價差值隨a1/b增加的線性增長。

圖1 最優簇頭數n1與a1/b關系圖圖2 兩種算法網絡整體代價差與a1/b關系圖當a0=a1時，Δ的值位于x軸下方并一直保持恒定，改進算法網絡整體代價總是大于LEACH算法，即采用改進算法的性能劣于LEACH算法。特別地在a0=a1=0時，LEACH的性能優于改進算法，是由于在這種情況下，節點的硬件代價并不影響網絡的整體代價，而LEACH算法的簇首輪換機制保證了整個網絡能量消耗的相對均衡。在其他a0=m*a1(0

5 結論及下一步的研究工作

基于對網絡整體消耗代價的考慮，本文研究一種用于二級異構網絡的分簇算法。它比較類似于靜態分簇算法，即簇頭節點一旦確定，就不再更換，不同的是該算法采用具有較高復雜度和較多能量的高級節點;需要根據普通節點數量和網絡環境參數再來確定所需的高級節點數。文中給出采用高級節點作為固定簇頭的分簇基本思想，對其工作過程進行描述，推導出最優簇頭數和各類節點所需能量的表達式，并對其整體代價消耗進行分析，結果表明，采用一定量的高級節點作為固定簇頭，當其a1/b超過一定值時，新算法的整體網絡代價明顯低于LEACH。但是對固定簇頭節點在網絡中如何放置考慮不夠;另外，由于作為簇頭的高級節點雖只占網絡節點的極少部分，但在整個網絡的通信過程中起著至關重要的作用，一旦這些節點失效，整個網絡將停止工作，因此采用改進算法后網絡的健壯性不是很好。如何布置簇頭節點使其合理分布以及整個網絡的健壯性問題將是下一步的研究工作。

參 考 文 獻

［1］Mhatre V P，Rosenberg C，Kofman D，et al.A Minimum Cost Heterogeneous Sensor Network with a Lifetime Constraint［J］.IEEE Transaction on Mobile Computing，2005，4(1):415.

［2］Heinzelman W R，Chandrakasan A，Balakrishnan H.An ApplicationSpecific ProtocolDrchitecture for Wireless Microsensor Networks［J］.IEEE Transaction on Wireless Communications，2002，1(4):660670.

［3］Akyildiz I F，Su W，SankarsubramaniamY，et al.Wireless Sensor Networks:A Survey［J］.Computer Networks，2002，38:393422.

［4］Heinzelman，Wendi B，Anantha P Chandrakasan，Hari Balakrishnan.Energy Efficient Communication Protocols forWireless Microsensor Networks［ C］.Paper Presented at the Proceedings of t he Hawaii International Conference on System Sciences，January，2000.

［5］Mhatre V，Rosenberg C.Design Guidelines for Wireless Sensor Networks:Communication，Clustering and Aggregation［J］.Adhoc Networks Journal，Elsevier Science，2004，2(1):4563.

［6］卿利，朱清新，王明文.異構傳感器網絡的分布式能量有效路由協議［J］.軟件學報，2006，17(3):481489.

［7］孫利民，李建忠，陳渝，等.無線傳感器網絡［M］.北京：清華大學出版社，2005.

［8］昂志敏，金海紅，范之國，等.基于ZigBee的無線傳感器網絡節點的設計與通信實現\\.現代電子技術，2007，30（10） :4749，57.

作者簡介 于立娟 女，1979年出生，桂林電子科技大學讀碩士研究生。主要研究方向為無線傳感器網絡協議。

注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文