摘  要： 針對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)是由大量無處不在的,、具有無線通信與計算能力的微小傳感器節(jié)點構(gòu)成的自組織分布式網(wǎng)絡(luò)系統(tǒng),，是能根據(jù)環(huán)境自主完成指定任務(wù)的智能系統(tǒng)[1-2]。無線傳感器網(wǎng)絡(luò)在環(huán)境惡劣,、無人職守,、資源受限的環(huán)境中顯示了很大的應(yīng)用價值，能夠客觀有效地獲取物理信息,，具有十分廣闊的應(yīng)用前景,，可應(yīng)用于軍事國防、工農(nóng)業(yè)控制,、城市管理,、智能家居、生物醫(yī)療,、環(huán)境檢測,、搶險救災(zāi)、防恐反恐,、危險區(qū)域遠(yuǎn)程控制等諸多領(lǐng)域[3],。它以數(shù)據(jù)為中心，具有有限的計算能力,、存儲能力,、無線通信能力和電源供應(yīng)能力,。如何在這樣有限的資源環(huán)境下獲取盡可能多的、有效的感知對象的特征信息,，并傳輸?shù)接脩艄?jié)點進(jìn)行處理,，是目前研究的重點，這些都可以歸結(jié)為傳感器網(wǎng)絡(luò)的路由問題,，即一個好的路由協(xié)議應(yīng)盡可能降低能耗,、延長網(wǎng)絡(luò)生存時間。
    無線傳感器網(wǎng)絡(luò)路由協(xié)議可以分為平面路由協(xié)議和分層路由協(xié)議兩種[4],。由于平面路由協(xié)議需要維護(hù)較大的路由表而占據(jù)較多的存儲空間,，并且擴(kuò)展性差，因而并不適用于大規(guī)模網(wǎng)絡(luò),。分層路由協(xié)議可以在一定程度上彌補(bǔ)這些不足,。LEACH算法是第一個被提出的具有代表性的分層路由協(xié)議，與一般的平面多跳路由算法相比,，可將網(wǎng)絡(luò)生命周期延長15%,，以后的各種分層路由算法都是基于LEACH改進(jìn)而來的。
1 LEACH算法分析
    LEACH協(xié)議分為兩個階段,，即簇建立階段和數(shù)據(jù)傳輸階段,，為了使能耗最少化，數(shù)據(jù)傳輸階段持續(xù)的時間要比簇建立階段長,，兩個階段所持續(xù)的時間總和稱為一輪[5-6],。為平衡網(wǎng)絡(luò)各節(jié)點的能耗，簇頭是周期性按輪隨機(jī)選舉的,，每輪選舉方法是：各節(jié)點產(chǎn)生一個[0,，1]之間的隨機(jī)數(shù)，如果該數(shù)小于T(n),，則該節(jié)點為簇頭,。T(n)的計算公式如下：
   
    式中，p是網(wǎng)絡(luò)中簇頭數(shù)與總節(jié)點數(shù)的百分比,，r是當(dāng)前的選舉輪數(shù),，G是最近1/p輪不是簇頭的節(jié)點集。成為簇頭的節(jié)點在無線信道中廣播這一消息,，其余節(jié)點選擇加入信號最強(qiáng)的簇頭,。節(jié)點通過一跳通信將數(shù)據(jù)傳送給簇頭，簇頭也通過一跳通信將聚合后的數(shù)據(jù)傳送給點,，該協(xié)議采用隨機(jī)選舉簇頭的方式避免簇頭過分消耗能量,，提高了網(wǎng)絡(luò)生存時間。
    但是這種隨機(jī)選擇簇頭的策略必將引起簇頭分布的不均勻，每個簇的成員數(shù)量也相差很大,，再加上各個簇頭到基站的距離不同,，所以在每輪結(jié)束后，節(jié)點的能量消耗差異很大,。由于LEACH算法在進(jìn)行簇頭選舉時沒有考慮節(jié)點的能量,，所以有可能能量低的節(jié)點擔(dān)任簇頭。這樣,，簇頭結(jié)點很可能在一輪結(jié)束前就因為能量消耗完而死亡,，使簇內(nèi)成員的數(shù)據(jù)在很長時間內(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é)點的數(shù)量來衡量)及節(jié)點能量選擇出簇內(nèi)具有最優(yōu)數(shù)目的高能量簇頭集合,，簇內(nèi)數(shù)據(jù)的收集融合轉(zhuǎn)發(fā)由這些高能量簇頭節(jié)點共同承擔(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é)點分布均勻的情況下,，每個傳感器所占用的面積S=M/N,。由基站將這一信息廣播給網(wǎng)絡(luò)中的每一個節(jié)點。
    首先,，根據(jù)LEACH算法生成初始簇頭,，成為簇頭的節(jié)點廣播成為簇頭的信息，未成為簇頭的節(jié)點根據(jù)接收到廣播信號的強(qiáng)弱來決定加入哪個簇,，并且將自己的能量信息發(fā)送給該簇簇頭,。簇頭節(jié)點根據(jù)其成員個數(shù)n得到該簇所在區(qū)域的大小m：m=n×S，再將n和m代入公式(1)得到本簇應(yīng)該具有的最優(yōu)簇頭數(shù)Ncu,。簇頭將各成員節(jié)點的能量(包括自身能量)做比較,，選擇出能量最大的前Ncu個節(jié)點來共同擔(dān)任該簇的簇頭，并給這Ncu個簇頭分配作息時間,，使它們輪流擔(dān)任簇內(nèi)數(shù)據(jù)的聚合和轉(zhuǎn)發(fā)任務(wù),。當(dāng)一個簇頭節(jié)點處于工作狀態(tài)時，其他的Ncu-1個簇頭節(jié)點休眠,。
    由Ncu個簇頭來分擔(dān)原來一個簇頭的工作量,，避免了單個簇頭因工作量過大能量消耗快而很早死亡的情況發(fā)生。雖然網(wǎng)絡(luò)在開始時采用LEACH的簇頭選舉算法產(chǎn)生初始簇頭，但最終由簇內(nèi)能量最大的Ncu個節(jié)點來充當(dāng)簇頭,，這就均衡了網(wǎng)絡(luò)的能量消耗,，延長了網(wǎng)絡(luò)的生命周期。
2.2 ONCHL算法執(zhí)行過程
    ONCHL算法執(zhí)行過程如下：
    (1)基站廣播包含S的數(shù)據(jù)包,，網(wǎng)絡(luò)中的所有節(jié)點提取并保存S信息,，并通過接收信號強(qiáng)度獲得到基站的距離dtoBS。
    (2)通過LEACH算法形成初始簇頭,，簇頭結(jié)點廣播成為簇頭的消息,，未形成簇頭的節(jié)點根據(jù)接收到信號的強(qiáng)弱選擇加入一個簇，并將自己的能量信息發(fā)送給所加入簇的簇頭,。
    (3)簇頭根據(jù)接收到的能量信息的個數(shù)得到簇內(nèi)成員數(shù)n,，再通過簡單計算得到本簇所占區(qū)域的大小m=n×S。應(yīng)用公式(2)得到本簇應(yīng)該具有的最優(yōu)簇頭數(shù)Ncu：
   
    (4)簇頭結(jié)點將本簇各成員的節(jié)點能量以及自身能量做比較,，選擇出能量最大前Ncu個節(jié)來共同擔(dān)任本簇簇頭,，并為這些簇頭節(jié)點安排作息時間表(即工作時隙)。初始簇頭將這個簇頭以及其工作時隙發(fā)送給簇內(nèi)所有的其他節(jié)點,。同時初始簇頭為簇內(nèi)普通節(jié)點分配工作時隙并將結(jié)果廣播給本簇其他節(jié)點,。由于初始簇頭節(jié)點的能量不一定在能量最大的前Ncu之列，當(dāng)初始簇頭節(jié)點能量較小時就退出而成為普通節(jié)點,，反之則繼續(xù)擔(dān)任簇頭工作,。
    (5)簇內(nèi)普通節(jié)點按照時分復(fù)用(TDMA)時隙向簇頭發(fā)送數(shù)據(jù)。成為簇頭的Ncu個節(jié)點就在其工作時隙內(nèi)將簇成員發(fā)送來的數(shù)進(jìn)行融合并發(fā)送給基站,。
    (6)當(dāng)其中的一個簇頭因消耗大量能量而不能將數(shù)據(jù)傳送到基站時,，就宣告一輪工作結(jié)束，并在本簇內(nèi)啟動新一輪簇建立過程,。
3 算法仿真及結(jié)果分析
    通過仿真實驗在網(wǎng)絡(luò)生命周期和網(wǎng)絡(luò)吞吐率方面對LEACH算法和改進(jìn)后的ONCHL算法進(jìn)行了比較,。其中，將網(wǎng)絡(luò)生命周期定義為從網(wǎng)絡(luò)運行到網(wǎng)絡(luò)中所有節(jié)點都死亡的時間,；網(wǎng)絡(luò)吞吐率定義為基站接收到的數(shù)據(jù)量,。

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

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

    以上實驗結(jié)果表明,，ONCHL算法與LEACH算法相比,，無論在延長網(wǎng)絡(luò)生命周期還是在提高網(wǎng)絡(luò)吞吐率方面都更好，這主要是因為ONCHL算法在網(wǎng)絡(luò)中形成了最優(yōu)有數(shù)目的高能量簇頭集,，能更加均衡地將能量負(fù)載分配到每個節(jié)點,。
    本文提出了LEACH算法的改進(jìn)算法——ONCHL算法。ONCHL算法在LEACH算法的基礎(chǔ)上,，選舉出具有最優(yōu)數(shù)目的簇頭集,，并在簇頭選舉中考慮了節(jié)點的當(dāng)前能量。仿真結(jié)果表明,，ONCHL算法具有更長的網(wǎng)絡(luò)生命周期和更高的網(wǎng)絡(luò)吞吐量,。
參考文獻(xiàn)
[1] 任豐原，黃海寧,，林闖.無線傳感器網(wǎng)絡(luò)[J].軟件學(xué)報，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é)報,，2006,，1(1):17-21.
[5] 胡剛，謝冬梅,，吳元中.無線傳感器網(wǎng)絡(luò)路由協(xié)議LEACH的研究與改進(jìn)[J].傳感技術(shù)學(xué)報:自然科學(xué)版,，2007，20(6):1391-1396.
[6] 劉守軍.無線傳感器網(wǎng)絡(luò)LEACH算法的研究[J].武漢理工大學(xué)學(xué)報，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.