趙芳芳，高媛

(中北大學 電子與計算機科學技術學院，山西 太原，030051)

0 引言

無線傳感器網(wǎng)絡(Wireless Sensor Networks,WSN)[1]可應用于軍事、商業(yè)、醫(yī)療救護、環(huán)境監(jiān)測等諸多領域，目前已成為計算機和通信領域中的研究熱點之一。

無線傳感器網(wǎng)絡是由大量的微小節(jié)點通過無線通信技術組成的自組織網(wǎng)絡。傳感器節(jié)點依靠電池供給能量，而又不能對數(shù)量眾多的節(jié)點更換電池，因此網(wǎng)絡生命周期就成為了無線傳感器網(wǎng)絡的關鍵性能指標之一。在目前的研究中，分簇算法被認為是進行高效的能量管理、延長網(wǎng)絡生命周期的最有效的途徑之一。本文對經(jīng)典的無線傳感器網(wǎng)絡分簇協(xié)議LEACH（低功耗自適應分簇協(xié)議）[2]進行了深入的研究，簇的形成方法是LEACH協(xié)議研究的主要內容，而簇頭選擇算法又是簇形成的核心，在LEACH協(xié)議中簇頭選擇算法不能做到最優(yōu)，無法保證簇頭處于恰當?shù)奈恢?，這導致簇頭過早耗盡能量，縮短了網(wǎng)絡的生命周期[3]。針對LEACH協(xié)議中簇頭選擇算法存在的不足，本文提出了改進的協(xié)議。

1 LEACH協(xié)議

1.1 LEACH協(xié)議算法

LEACH算法是一種周期性執(zhí)行的低功耗自適應分簇拓撲算法[4]，在運行過程中,通過不斷隨機選取簇首達到能耗均勻分布的目的。LEACH定義了“輪”(round)的概念，每一輪分為兩個階段:簇的建立階段和穩(wěn)定工作階段。在簇的建立階段,首先需要選舉簇首節(jié)點，簇首節(jié)點的選取是由每個節(jié)點自主決定的。對于每個節(jié)點n產(chǎn)生一個0~1的隨機數(shù)，如果該隨機數(shù)小于閾值T(n)，則節(jié)點當選為本輪簇首。T(n)定義如下:

式中:p為簇首節(jié)點占總節(jié)點數(shù)的百分比； r為當前的簇首選舉輪數(shù)；G為過去輪中未當選簇首的節(jié)點集。在r=0時,節(jié)點以p的概率選取簇首；對于在前r(r<1/p)輪之內當過簇首的節(jié)點取消其再次當選的資格，從而保證其他節(jié)點以相同的概率當選簇首。當分簇過程完成后便可以進行數(shù)據(jù)的傳輸,進入穩(wěn)定工作階段。

1.2 LEACH協(xié)議的優(yōu)缺點

LEACH協(xié)議具有很多優(yōu)點，比如分層的簇型結構、本地數(shù)據(jù)聯(lián)合處理和簇頭節(jié)點動態(tài)分配，特別是在處理具有高度相關性的數(shù)據(jù)時，由于數(shù)據(jù)融合力度大，冗余數(shù)據(jù)被大量消除，因此在能耗方面性能較好，但LEACH仍有不足之處：

(1) 在LEACH算法中,分布式簇首選取機制能夠均勻網(wǎng)絡中節(jié)點能耗,但隨機選取的簇首節(jié)點無法保證簇頭節(jié)點在空間上均勻分布，在某些情況下，算法所選擇的簇頭節(jié)點可能集中在某一個小范圍之內，使得一部分成員節(jié)點無法加入任何簇或者成員節(jié)點與簇頭節(jié)點進行數(shù)據(jù)傳輸時消耗過多的能量[5-6]。

(2) LEACH算法假定所有節(jié)點都能直接與Sink節(jié)點進行通信，這顯然限制了LEACH算法在較大區(qū)域內無線傳感器網(wǎng)絡的應用。

2 改進后的LEACH協(xié)議

針對LEACH路由協(xié)議的上述缺點，本文對簇頭選擇算法進行了改進，以平衡總的能量消耗、延長網(wǎng)絡的存活時間為主要設計目標，提出了一種改進的LEACH路由協(xié)議。

在簇頭選擇階段，LEACH協(xié)議是在整個區(qū)域中隨機地選擇簇頭，這種方式簡單，但是無法保證簇頭節(jié)點在空間上的均勻分布，在某些情況下，算法所選擇的簇頭節(jié)點可能集中在某一個小范圍之內，使得一部分成員節(jié)點無法加入任何簇或者與簇頭節(jié)點進行數(shù)據(jù)傳輸時消耗過多的能量。改進后的協(xié)議充分考慮了簇頭節(jié)點在空間上的分布，首先將整個網(wǎng)絡劃分成若干個小的區(qū)域，如圖1所示。

圖1 區(qū)域的劃分

根據(jù)網(wǎng)絡的大小、節(jié)點的傳輸范圍和節(jié)點的分布密度決定區(qū)域的半徑R。在標志為ZONE0的第1個區(qū)域中，傳感器節(jié)點與Sink節(jié)點的距離小于區(qū)域半徑R。在標志為ZONE1的第2個區(qū)域中，傳感器節(jié)點與Sink節(jié)點的距離大于R，但小于2R。依此類推，在標志為ZONEi的第i個區(qū)域中，傳感器節(jié)點與Sink節(jié)點的距離大于i×R，但是小于(i+1)×R。最后一個區(qū)域包含了超過上一個區(qū)域范圍的所有剩余節(jié)點。因此，區(qū)域的總數(shù)為：

其中，N_ZONE為網(wǎng)絡中區(qū)域的個數(shù)；NETWORK_ RANGE為網(wǎng)絡的大小。

區(qū)域劃分完后，Sink節(jié)點廣播區(qū)域信息給每一個傳感器節(jié)點，使它們知道自己屬于哪個區(qū)域。每個區(qū)域中的簇頭數(shù)目是根據(jù)每個區(qū)域的面積決定的。在ZONE0中由于包含Sink節(jié)點，因此不需要為該區(qū)域分配簇頭節(jié)點。在ZONE1中，僅僅為它分配一個簇頭節(jié)點。在ZONE2中，簇頭的數(shù)目根據(jù)ZONE2區(qū)域的面積決定。如果ZONE2的區(qū)域面積是ZONE1的2倍，那么ZONE2應該有2個簇頭。每個區(qū)域中的簇頭數(shù)目為：

其中，N_Chi為區(qū)域ZONEi中的簇頭數(shù)目。在區(qū)域范圍內隨機選擇指定數(shù)目的簇頭，可使簇頭的分布更加均勻。

3 仿真實驗及分析

3.1 仿真模型

實驗中以NS-2 (Network SimulatorVersion-2) 作為仿真平臺[7]，版本為2.28。，目前LEACH原協(xié)議仿真代碼包mit.tar.gz可以從互聯(lián)網(wǎng)上獲得，腳本文件中對網(wǎng)絡的一些設置參數(shù)如表1所示[8]。

表1 仿真參數(shù)

為了簡化實驗進程，本仿真實驗進行的參數(shù)設定為：在100×100的方形區(qū)域內，隨機分布100個節(jié)點，Sink節(jié)點位于(15,15)處，數(shù)據(jù)包的大小為2 000 bit，簇頭的數(shù)據(jù)壓縮率為0.7，即有2 000 bit數(shù)據(jù)發(fā)送到簇頭，經(jīng)簇頭處理之后，將1 400 bit傳給簇頭中繼。區(qū)域的半徑R設置為20 m。節(jié)點的初始能量為2J，數(shù)據(jù)融合消耗的能量為5 nJ/bit/message，傳輸?shù)哪芰繛?0 nJ/bit。

3.2 性能指標

在實驗中，對于無線傳感器網(wǎng)絡的仿真，根據(jù)不同的要求需要不同的指標參數(shù)，改進的協(xié)議是以平衡所有節(jié)點總的能量消耗、延長網(wǎng)絡的存活時間為主要設計目標，因此，從以下2個指標衡量改進后協(xié)議的性能：

(1)節(jié)點總的消耗能量：不同時刻所有節(jié)點消耗能量的總和。

(2)網(wǎng)絡的存活時間：LEACH協(xié)議中假設節(jié)點不知其地理位置，且節(jié)點隨機部署，為保證采集數(shù)據(jù)的精確性，選擇從網(wǎng)絡開始運行到第1個死亡節(jié)點出現(xiàn)的時間為網(wǎng)絡的生存期(FND)。

3.3 仿真結果分析

圖2所示的是改進前后LEACH協(xié)議在生命期結束時的能量消耗，改進后協(xié)議的能量消耗比改進前的減少21.46%。

圖2 能量消耗對比

假設節(jié)點總能量的一部分專門為傳感器供能，考察傳感器耗能對改進前后協(xié)議運行的影響如圖3所示，考察指標為網(wǎng)絡的生存期，其中0代表不考慮傳感器耗能的情況。

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

圖3顯示當傳感器耗能小于0.9 J(占總能量45%)時，協(xié)議的改進使網(wǎng)絡生存期增加明顯，0.9 J~1.2 J(占總能量60%)之間時生存期增加不多，而當傳感器耗能增加為總能量的60%以及更多時，協(xié)議的改進對網(wǎng)絡生存期的增加已經(jīng)沒有效果。這說明單純從通信協(xié)議的角度為網(wǎng)絡節(jié)能是在傳感器耗能在一定范圍時才起作用的，因此，在實際應用中降低網(wǎng)絡的功耗還必須要結合所采用的傳感器的耗能情況來設計節(jié)能措施。

由實驗可知，無論是網(wǎng)絡的存活時間還是所有節(jié)點總的能量消耗，改進后的協(xié)議都優(yōu)于原LEACH協(xié)議。這說明在改進協(xié)議中，區(qū)域范圍內進行簇頭選擇使得簇頭節(jié)點在網(wǎng)絡中的分布更加均勻，成員節(jié)點與簇頭節(jié)點的通信將消耗更少的能量，延長了網(wǎng)絡的存活時間。

[1] Akyildiz I F,Su W,Sankarasubramaniam Y,et al.Wireless Sensor Networks:A Survey[J].Computer Networks,2002,38(4):393-422.

[2] Heinzelman W R,Chandrakasan A,Balakrishnan H.Energy-efficient Communication Protocol for Wireless Microsensor Networks[C]//Proc.of HICSS’00.Los Alamitos,CA,USA:IEEE Press,2000.

[3] Mhater V,Rosenberg C.Homogeneous VS Heterogeneous Clustered Sensor Networks: A Comparative Study[C]//Proc.of IEEE Intel Conference on Communications.[S.l.]:IEEE Press,2004.

[4] Heinzelman W R,Chandrakasan A,Balakrishnan H. A application-specific protocol architecturefor wireless sensor networks [J]. IEEE Transactions on Wireless Communications, 2002,1(4):660-670.

[5] Zhou Z, Zhou S, Cui S,et al. Energy-efficient cooperative communication in a clustered wireless sensor network [J]. IEEE Transactions on Vehicular Technology, 2008,57(6):3618-3628.

[6] 樂世成,王培康.無線傳感器網(wǎng)絡中的節(jié)能路由算法[J].計算機工程,2008,34(7):113-117.

[7] 徐雷鳴,龐博,趙耀.NS與網(wǎng)絡模擬[M].北京:人民郵電出版社,2008.

[8] Varadhan F K.The NS Manual[Z].(2007-04-03).http:// www.isi.edunsnam/ns/ns-documentation.