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

關(guān)鍵詞：無線傳感器網(wǎng)絡(luò)；LEACH；高級節(jié)點；簇頭；整體網(wǎng)絡(luò)代價

中圖分類號：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 引 言

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

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

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

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

2 網(wǎng)絡(luò)模型

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

2.1 代價模型

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

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

2.2 無線傳輸能量模型

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

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

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

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

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

3 算法描述及重要參數(shù)的確定

3.1 算法描述

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

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

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

3.2 最優(yōu)簇頭數(shù)的計算

在該算法中首先假定所需的高級節(jié)點（簇頭）數(shù)為n1，下面以最小化整個網(wǎng)絡(luò)代價為目的推導(dǎo)所需的最優(yōu)簇頭數(shù)n1的數(shù)學表達式。

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

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

將式(5)和式(6)代入(1)式得出整個網(wǎng)絡(luò)的總代價為：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)關(guān)于n1求導(dǎo)，從而得到使整個網(wǎng)絡(luò)總代價最小的最優(yōu)簇頭數(shù)為:n1=n0bTμ1M2π［a1+bT(l+μ2d4)］(8)4 性能分析與評價

為分析改進后的算法的性能，采用表1中的參數(shù)進行網(wǎng)絡(luò)環(huán)境設(shè)置，并與經(jīng)典的分簇算法LEACH加以對比。

表1 網(wǎng)絡(luò)環(huán)境參數(shù)表

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

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

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

考慮采用LEACH算法且具有相同節(jié)點數(shù)目(n0+n1)的同構(gòu)網(wǎng)絡(luò)，以fLEACH(a0，a1，b)表示采用LEACH算法的整個網(wǎng)絡(luò)代價，而以fNew(a0，a1，b)來表示采用改進算法的網(wǎng)絡(luò)消耗代價，用Δ表示二者之間的差值，則(由以下推導(dǎo)可得出它是關(guān)于a0，a1和b的函數(shù)):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給出最優(yōu)簇頭數(shù)n1和a1/b的關(guān)系，圖2給出在a0=a1，a0=0.5a1，a0=0.2a1三種情況下，采用LEACH和改進后兩種算法的網(wǎng)絡(luò)整體消耗代價差和a1/b的關(guān)系。

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

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

5 結(jié)論及下一步的研究工作

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

參 考 文 獻

［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］卿利，朱清新，王明文.異構(gòu)傳感器網(wǎng)絡(luò)的分布式能量有效路由協(xié)議［J］.軟件學報，2006，17(3):481489.

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

［8］昂志敏，金海紅，范之國，等.基于ZigBee的無線傳感器網(wǎng)絡(luò)節(jié)點的設(shè)計與通信實現(xiàn)\\.現(xiàn)代電子技術(shù)，2007，30（10） :4749，57.

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

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