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

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

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

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

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

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