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

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

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

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

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

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