摘  要： 針對LEACH算法簇頭選舉方式的不足進(jìn)行了改進(jìn)，采用的方法是選舉出最優(yōu)數(shù)目的高能量簇頭集來擔(dān)任簇頭工作。仿真結(jié)果表明，改進(jìn)后的算法能夠提供更長的網(wǎng)絡(luò)生命周期和更高的網(wǎng)絡(luò)吞吐率。
關(guān)鍵詞： 無線傳感器網(wǎng)絡(luò)；LEACH算法；路由協(xié)議

    無線傳感器網(wǎng)絡(luò)WSN(Wireless Sensor Network)是由大量無處不在的、具有無線通信與計(jì)算能力的微小傳感器節(jié)點(diǎn)構(gòu)成的自組織分布式網(wǎng)絡(luò)系統(tǒng)，是能根據(jù)環(huán)境自主完成指定任務(wù)的智能系統(tǒng)[1-2]。無線傳感器網(wǎng)絡(luò)在環(huán)境惡劣、無人職守、資源受限的環(huán)境中顯示了很大的應(yīng)用價(jià)值，能夠客觀有效地獲取物理信息，具有十分廣闊的應(yīng)用前景，可應(yīng)用于軍事國防、工農(nóng)業(yè)控制、城市管理、智能家居、生物醫(yī)療、環(huán)境檢測、搶險(xiǎn)救災(zāi)、防恐反恐、危險(xiǎn)區(qū)域遠(yuǎn)程控制等諸多領(lǐng)域[3]。它以數(shù)據(jù)為中心，具有有限的計(jì)算能力、存儲(chǔ)能力、無線通信能力和電源供應(yīng)能力。如何在這樣有限的資源環(huán)境下獲取盡可能多的、有效的感知對象的特征信息，并傳輸?shù)接脩艄?jié)點(diǎn)進(jìn)行處理，是目前研究的重點(diǎn)，這些都可以歸結(jié)為傳感器網(wǎng)絡(luò)的路由問題，即一個(gè)好的路由協(xié)議應(yīng)盡可能降低能耗、延長網(wǎng)絡(luò)生存時(shí)間。
    無線傳感器網(wǎng)絡(luò)路由協(xié)議可以分為平面路由協(xié)議和分層路由協(xié)議兩種[4]。由于平面路由協(xié)議需要維護(hù)較大的路由表而占據(jù)較多的存儲(chǔ)空間，并且擴(kuò)展性差，因而并不適用于大規(guī)模網(wǎng)絡(luò)。分層路由協(xié)議可以在一定程度上彌補(bǔ)這些不足。LEACH算法是第一個(gè)被提出的具有代表性的分層路由協(xié)議，與一般的平面多跳路由算法相比，可將網(wǎng)絡(luò)生命周期延長15%，以后的各種分層路由算法都是基于LEACH改進(jìn)而來的。
1 LEACH算法分析
    LEACH協(xié)議分為兩個(gè)階段，即簇建立階段和數(shù)據(jù)傳輸階段，為了使能耗最少化，數(shù)據(jù)傳輸階段持續(xù)的時(shí)間要比簇建立階段長，兩個(gè)階段所持續(xù)的時(shí)間總和稱為一輪[5-6]。為平衡網(wǎng)絡(luò)各節(jié)點(diǎn)的能耗，簇頭是周期性按輪隨機(jī)選舉的，每輪選舉方法是：各節(jié)點(diǎn)產(chǎn)生一個(gè)[0，1]之間的隨機(jī)數(shù)，如果該數(shù)小于T(n)，則該節(jié)點(diǎn)為簇頭。T(n)的計(jì)算公式如下：
   
    式中，p是網(wǎng)絡(luò)中簇頭數(shù)與總節(jié)點(diǎn)數(shù)的百分比，r是當(dāng)前的選舉輪數(shù)，G是最近1/p輪不是簇頭的節(jié)點(diǎn)集。成為簇頭的節(jié)點(diǎn)在無線信道中廣播這一消息，其余節(jié)點(diǎn)選擇加入信號(hào)最強(qiáng)的簇頭。節(jié)點(diǎn)通過一跳通信將數(shù)據(jù)傳送給簇頭，簇頭也通過一跳通信將聚合后的數(shù)據(jù)傳送給點(diǎn)，該協(xié)議采用隨機(jī)選舉簇頭的方式避免簇頭過分消耗能量，提高了網(wǎng)絡(luò)生存時(shí)間。
    但是這種隨機(jī)選擇簇頭的策略必將引起簇頭分布的不均勻，每個(gè)簇的成員數(shù)量也相差很大，再加上各個(gè)簇頭到基站的距離不同，所以在每輪結(jié)束后，節(jié)點(diǎn)的能量消耗差異很大。由于LEACH算法在進(jìn)行簇頭選舉時(shí)沒有考慮節(jié)點(diǎn)的能量，所以有可能能量低的節(jié)點(diǎn)擔(dān)任簇頭。這樣，簇頭結(jié)點(diǎn)很可能在一輪結(jié)束前就因?yàn)槟芰肯耐甓劳觯勾貎?nèi)成員的數(shù)據(jù)在很長時(shí)間內(nèi)不能傳送到基站，出現(xiàn)監(jiān)測漏洞。為了彌補(bǔ)這些不足，本文在LEACH的基礎(chǔ)上對簇頭選舉算法進(jìn)行了改進(jìn)，提出了具有最優(yōu)數(shù)目的高能量簇頭集算法ONCHL(Leach with the Optimum Number of Cluster Heads)。
2 LEACH改進(jìn)后的ONCHL算法
    在LEACH算法隨機(jī)選舉出簇頭集的基礎(chǔ)上，ONCHL算法再根據(jù)所形成的簇的大小(用簇內(nèi)節(jié)點(diǎn)的數(shù)量來衡量)及節(jié)點(diǎn)能量選擇出簇內(nèi)具有最優(yōu)數(shù)目的高能量簇頭集合，簇內(nèi)數(shù)據(jù)的收集融合轉(zhuǎn)發(fā)由這些高能量簇頭節(jié)點(diǎn)共同承擔(dān)。這就在很大程度上均衡了網(wǎng)絡(luò)的能量消耗，有利于延長網(wǎng)絡(luò)的生命周期。
2.1 改進(jìn)的簇頭選舉算法
    由于網(wǎng)絡(luò)中簇頭數(shù)的多少將直接影響網(wǎng)絡(luò)的性能，將應(yīng)用分簇算法的最優(yōu)簇頭數(shù)理論[7]來對LEACH算法進(jìn)行改進(jìn)。最優(yōu)簇頭數(shù)Kopt：

    在傳感器節(jié)點(diǎn)分布均勻的情況下，每個(gè)傳感器所占用的面積S=M/N。由基站將這一信息廣播給網(wǎng)絡(luò)中的每一個(gè)節(jié)點(diǎn)。
    首先，根據(jù)LEACH算法生成初始簇頭，成為簇頭的節(jié)點(diǎn)廣播成為簇頭的信息，未成為簇頭的節(jié)點(diǎn)根據(jù)接收到廣播信號(hào)的強(qiáng)弱來決定加入哪個(gè)簇，并且將自己的能量信息發(fā)送給該簇簇頭。簇頭節(jié)點(diǎn)根據(jù)其成員個(gè)數(shù)n得到該簇所在區(qū)域的大小m：m=n×S，再將n和m代入公式(1)得到本簇應(yīng)該具有的最優(yōu)簇頭數(shù)Ncu。簇頭將各成員節(jié)點(diǎn)的能量(包括自身能量)做比較，選擇出能量最大的前Ncu個(gè)節(jié)點(diǎn)來共同擔(dān)任該簇的簇頭，并給這Ncu個(gè)簇頭分配作息時(shí)間，使它們輪流擔(dān)任簇內(nèi)數(shù)據(jù)的聚合和轉(zhuǎn)發(fā)任務(wù)。當(dāng)一個(gè)簇頭節(jié)點(diǎn)處于工作狀態(tài)時(shí)，其他的Ncu-1個(gè)簇頭節(jié)點(diǎn)休眠。
    由Ncu個(gè)簇頭來分擔(dān)原來一個(gè)簇頭的工作量，避免了單個(gè)簇頭因工作量過大能量消耗快而很早死亡的情況發(fā)生。雖然網(wǎng)絡(luò)在開始時(shí)采用LEACH的簇頭選舉算法產(chǎn)生初始簇頭，但最終由簇內(nèi)能量最大的Ncu個(gè)節(jié)點(diǎn)來充當(dāng)簇頭，這就均衡了網(wǎng)絡(luò)的能量消耗，延長了網(wǎng)絡(luò)的生命周期。
2.2 ONCHL算法執(zhí)行過程
    ONCHL算法執(zhí)行過程如下：
    (1)基站廣播包含S的數(shù)據(jù)包，網(wǎng)絡(luò)中的所有節(jié)點(diǎn)提取并保存S信息，并通過接收信號(hào)強(qiáng)度獲得到基站的距離dtoBS。
    (2)通過LEACH算法形成初始簇頭，簇頭結(jié)點(diǎn)廣播成為簇頭的消息，未形成簇頭的節(jié)點(diǎn)根據(jù)接收到信號(hào)的強(qiáng)弱選擇加入一個(gè)簇，并將自己的能量信息發(fā)送給所加入簇的簇頭。
    (3)簇頭根據(jù)接收到的能量信息的個(gè)數(shù)得到簇內(nèi)成員數(shù)n，再通過簡單計(jì)算得到本簇所占區(qū)域的大小m=n×S。應(yīng)用公式(2)得到本簇應(yīng)該具有的最優(yōu)簇頭數(shù)Ncu：
   
    (4)簇頭結(jié)點(diǎn)將本簇各成員的節(jié)點(diǎn)能量以及自身能量做比較，選擇出能量最大前Ncu個(gè)節(jié)來共同擔(dān)任本簇簇頭，并為這些簇頭節(jié)點(diǎn)安排作息時(shí)間表(即工作時(shí)隙)。初始簇頭將這個(gè)簇頭以及其工作時(shí)隙發(fā)送給簇內(nèi)所有的其他節(jié)點(diǎn)。同時(shí)初始簇頭為簇內(nèi)普通節(jié)點(diǎn)分配工作時(shí)隙并將結(jié)果廣播給本簇其他節(jié)點(diǎn)。由于初始簇頭節(jié)點(diǎn)的能量不一定在能量最大的前Ncu之列，當(dāng)初始簇頭節(jié)點(diǎn)能量較小時(shí)就退出而成為普通節(jié)點(diǎn)，反之則繼續(xù)擔(dān)任簇頭工作。
    (5)簇內(nèi)普通節(jié)點(diǎn)按照時(shí)分復(fù)用(TDMA)時(shí)隙向簇頭發(fā)送數(shù)據(jù)。成為簇頭的Ncu個(gè)節(jié)點(diǎn)就在其工作時(shí)隙內(nèi)將簇成員發(fā)送來的數(shù)進(jìn)行融合并發(fā)送給基站。
    (6)當(dāng)其中的一個(gè)簇頭因消耗大量能量而不能將數(shù)據(jù)傳送到基站時(shí)，就宣告一輪工作結(jié)束，并在本簇內(nèi)啟動(dòng)新一輪簇建立過程。
3 算法仿真及結(jié)果分析
    通過仿真實(shí)驗(yàn)在網(wǎng)絡(luò)生命周期和網(wǎng)絡(luò)吞吐率方面對LEACH算法和改進(jìn)后的ONCHL算法進(jìn)行了比較。其中，將網(wǎng)絡(luò)生命周期定義為從網(wǎng)絡(luò)運(yùn)行到網(wǎng)絡(luò)中所有節(jié)點(diǎn)都死亡的時(shí)間；網(wǎng)絡(luò)吞吐率定義為基站接收到的數(shù)據(jù)量。

    (1)網(wǎng)絡(luò)生命周期的比較
    圖1為LEACH算法和ONCHL算法網(wǎng)絡(luò)生命周期的比較圖?？梢钥闯觯琌NCHL算法的節(jié)點(diǎn)生存時(shí)間相對LEACH有所提高，第一個(gè)節(jié)點(diǎn)死亡的時(shí)間延長了大約22%，整個(gè)網(wǎng)絡(luò)的生命周期延長了大約35%。由此可見，ONCHL算法能更加均衡地消耗網(wǎng)絡(luò)的能量，避免了低能量節(jié)點(diǎn)過早死亡，有效延長了網(wǎng)絡(luò)的生命周期。

    (2)網(wǎng)絡(luò)吞吐量的比較
    基站接收數(shù)據(jù)量隨網(wǎng)絡(luò)能耗的變化如圖2所示。在相同的能耗下，與LEACH算法相比，改進(jìn)后的ONCHL算法能夠傳遞更多的數(shù)據(jù)，說明ONCHL算法具有較高的能量使用效率。這是因?yàn)镺NCHL算法采用了具有最優(yōu)簇頭數(shù)的成簇方式，有效地提高了網(wǎng)絡(luò)的能量使用效率。

    以上實(shí)驗(yàn)結(jié)果表明，ONCHL算法與LEACH算法相比，無論在延長網(wǎng)絡(luò)生命周期還是在提高網(wǎng)絡(luò)吞吐率方面都更好，這主要是因?yàn)镺NCHL算法在網(wǎng)絡(luò)中形成了最優(yōu)有數(shù)目的高能量簇頭集，能更加均衡地將能量負(fù)載分配到每個(gè)節(jié)點(diǎn)。
    本文提出了LEACH算法的改進(jìn)算法——ONCHL算法。ONCHL算法在LEACH算法的基礎(chǔ)上，選舉出具有最優(yōu)數(shù)目的簇頭集，并在簇頭選舉中考慮了節(jié)點(diǎn)的當(dāng)前能量。仿真結(jié)果表明，ONCHL算法具有更長的網(wǎng)絡(luò)生命周期和更高的網(wǎng)絡(luò)吞吐量。
參考文獻(xiàn)
[1] 任豐原，黃海寧，林闖.無線傳感器網(wǎng)絡(luò)[J].軟件學(xué)報(bào)，2003，14(7):1282-1291.
[2] 孫利民，李建中，陳渝，等.無線傳感器網(wǎng)絡(luò)[M].北京:清華大學(xué)出版社，2005.
[3] AKYILDIZI F， SU W， SANKARASUBRAMANIAM Y， et al. Wireless sensor networks: a survey[J]. Computer Networks， 2002，38(4):393-422.
[4] 李莉，溫向明，董樹松.無線傳感器網(wǎng)絡(luò)路由協(xié)議的研究與展望[J].中國電子科學(xué)研究院學(xué)報(bào)，2006，1(1):17-21.
[5] 胡剛，謝冬梅，吳元中.無線傳感器網(wǎng)絡(luò)路由協(xié)議LEACH的研究與改進(jìn)[J].傳感技術(shù)學(xué)報(bào):自然科學(xué)版，2007，20(6):1391-1396.
[6] 劉守軍.無線傳感器網(wǎng)絡(luò)LEACH算法的研究[J].武漢理工大學(xué)學(xué)報(bào)，2007，29(10):43-45.
[7] HEINZELMAN W R， CHANDRAKASAN A， BALAKR ISHNAN H. An application-specific protocol architecture for wireless micro sensor networks[J]. IEEE Transactions on Wireless Communications， 2002，1(4):660-670.