基于靜態分簇的LEACH算法改進研究

韓 濤，李訓銘

（河海大學 能源與電氣學院，江蘇 南京 210000）

無線傳感器網絡（Wireless Sensor Network，WSN）是由大量無處不在的、具有通信與計算能力的微小傳感器節點密集布設在無人值守的監控區域而構成的能夠根據環境自主完成指定任務的“智能”自治測控網絡系統。無線傳感器網絡的發展最初起源于戰場監測等軍事應用。而現今無線傳感器網絡被應用于很多民用領域，如環境與生態監測、健康監護、家居自動化以及交通控制等。由于WSN的網絡節點多是由電池供電，所以其路由算法要考慮高效節能，才能夠使整個網絡有著良好的生存能力。

路由是WSN的核心技術之一，好的WSN路由協議需要滿足以下四個要求：能量高效，可擴展性強，魯棒性，快速收斂性。目前WSN的路由協議按照發現策略分為主動路由和被動路由。按照網絡管理的邏輯結構劃分分為：平面結構路由，如 Gossiping[1]；分層路由，如 LEACH[2]，地理信息路由協議，如 GPSR[3]。

在眾多的無線傳感器網絡的路由協議中，LEACH協議是最為典型的一種分層路由協議，本文主要針對LEACH協議進行優化，優化的中會借鑒其他路由協議的思想。使得改進后的LEACH協議能夠更好的提高WSN的性能和適用范圍。

1 LEACH簡介及其優化

LEACH（Low Energy Adaptive Clustering Hierarchy，低功耗自適應集簇分層型協議）是由MIT的Heinzelman等人在2000年提出的最早在WSN中涉及分簇思想的路由協議算法。分簇思想相比于之前的平面路由傳輸，在高效節能方面有了很大的進步，提高了網絡存活時間，所以在該算法提出之后不斷的有其他路由協議引入或者借鑒其分簇思想。而LEACH算法作為經典算法，對它的優化和改進也在不斷的進行。

LEACH算法的基本思想是：提出“輪”（round）的概念，每一輪即是一個循環，每個循環以隨機的方式選擇簇首節點（head node），普通的節點將數據傳輸到簇首節點上，簇首節點和基站（base station）通信，分層式的設計降低了網絡能源消耗、提高了網絡整體生存時間，同時由于簇首節點是會在每一輪都會被重新選定，平衡了整個網絡的能量負載。

LEACH協議在工作的時候每輪主要分為兩個階段：周期性簇的建立階段和穩定的數據通信階段。為了減少協議開銷，穩定階段的持續時間要長于簇的建立階段。簇的建立階段主要分為4步：簇頭節點的選擇，簇頭節點的廣播，簇頭節點的建立和調度機制的生成。在此階段，傳感器節點隨機生成一個0~1之間的隨機數，并且與閾值T（n）做比較，如果小于該閾值，則該節點就會當選為簇頭。T（n）按照下列公式計算：

式中：P為節點成為簇頭節點的百分數，r為當前輪數，G為在最近的1/p輪中未當選簇頭的節點集合。簇頭節點選定后，廣播自己成為簇頭的消息，節點根據接收到的消息的強度決定加入哪個簇，并告知相應的簇頭，完成簇的建立過程。然后，簇頭節點采用TDMA的方式，為簇內成員分配傳送數據的時隙。在穩定階段，傳感器節點將采集的數據傳送到簇頭節點。簇頭節點對采集的數據進行數據融合后再將信息傳送給匯聚節點，匯聚節點將數據傳送給監控中心來進行數據的處理。穩定階段持續一段時間后，網絡重新進入簇的建立階段，進行下一輪的簇重建，不斷循環。

LEACH協議中采取分簇的分層設計思想，同時簇首節點在接收到普通節點的數據后會對數據信息進行融合，減少了數據量同時也節約了能量。簇首節點隨機選取，平衡了能量負載，延長了整個網絡的生命周期。LEACH算法本身也存在很多問題，首先由于簇首節點選取的隨機性會導致在整個區域內簇首節點分布不均勻，普通節點在選取所要加入簇的時候按照就近原則，會出現極大簇和極小簇的情況，能量消耗不平衡；其次選取簇首節點的時候并未考慮剩余能量，會導致部分剩余能量少的節點被選為簇首節點而過早死去，最后簇首節點每輪都要重新選取，普通節點也要再次選擇要加入的簇，過于頻繁會造成相當大的能量損耗。

2 歷史改進

LEACH算法是層次型路由協議中最經典的代表，是無線傳感器網絡中提出的最早基于分簇的路由協議，對其后的路由設計和改進有很大的影響，對它的改進也一直沒有間斷。對LEACH算法改進的本質在于3點：一個是平衡能量負載，因為LEACH算法的前提條件是每個節點擁有的能量是相同的，因此平衡能量負載能使得整個網絡中的能量合理配置，提高系統級能量使用率；另一個盡量減小數據傳輸過程中的能量消耗，按照能量消耗模型，參考能量消耗和距離以及數據量之間的關系，采用單跳和多跳結合多種傳輸方式；第3個就是數據融合，由于相近的傳感器節點獲取的數據有一部分或者大部分重復的，因此在傳播的簇首時進行數據融合，減小數據傳輸量，也可以有效減小傳感器網絡中能量消耗，從而延長網絡壽命，也在一定程度上提高了整個網絡的質量。由以上3點我們可以看到，對LEACH算法的改進是基于能量模型來進行的。自LEACH提出以來，對其改進主要有以下幾個方面。

簇首選取方面的優化：加入剩余能量的考慮，使得部分剩余能量較小的節點免于或者減小被選為簇首節點的概率[4]。改進選取簇首節點的方式，加入時間因子[5]；使簇首節點分布均勻，如HEED[6]算法。重新計算最優簇首個數[7]；靜態分配簇首節點[8]等。

平衡簇首負載的優化：平衡簇中普通節點個數，避免過多的節點同時選擇一個簇首[9]等。

3 改進后的LEACH算法

根據LEACH算法的特點和不足，學習了歷來其他研究者的改進思想，本文將在以下幾個方面進行改進：首先基站根據網絡節點分布情況，將節點按照最優簇個數分成占節點總數4%-6%（仿真中選擇5%）的簇，簇按照地理空間分布，接著根據簇內節點信息來選擇簇首，首輪簇首選擇之后，簇內節點會根據自己的信息來形成一個（0~1）之間的隨機數，在下一輪簇首選擇時，最大的會自動升級為簇首。在通信過程中采用單跳與多跳相結合接力通訊思想，根據節點的位置和剩余能量來選擇接力節點，接力通訊分為簇間接力以及簇和基站中間加入中轉的接力。

3.1 網絡模型與能量模型

3.1.1 網絡模型

改進算法的網絡模型和LEACH算法基本類似：

1）網絡中有固定的基站，并且遠離傳感器節點，能夠足夠大，不需要考慮其能量消耗。

2）傳感器節點的類型相同，具有相同的初始能量，并且能量是有限的，每個節點具有一個獨一無二的ID。

3）傳感器節點隨機分布，但是位置固定，并且基站知道每個節點的位置和ID。

4）節點可以感知自己的剩余能量，并且能夠改變發射功率。

3.1.2 能量模型

改進算法的能量模型采用LEACH算法的能量模型:

1） 無線通訊中發送（ETx-elec）和接收（ERx-elec）相同大小的數據所消耗的能量是相同的。即為：

無線通訊中信號傳輸增益為

2）發送一個k位數據到距離為d的地方，接收和發送的能量如下：

接收：

根據d和接近中心的距離 d0的關系，ERx-amp（k，d）分為自由空間模型（Free Space，fs）和多徑衰減模型（Multipath， mp）[10]：

其中εfs和εmp是常數，由發射距離和接收誤碼率等因素決定。d0是決定何種模型的閾值：

其中，L是系統功耗因子，ht是發送天線高度，hr是接收天線高度，λ是載波波長。

3.2 簇的形成

本文改進與LEACH算法及以往算法相比，在簇的周期性建立階段順序有所改動，會在簇首選取之前就先確定簇的大小及簇內節點，然后在改簇內再選擇簇首節點。改進后簇形成過程是：首先，基站獲取每個節點的位置信息，根據節點的密度和位置將整個網絡分成節點總數4%~6%的區域 （仿真中采用5%），每個區域內擁有網絡節點18~22個。簇分好之后在一段時間內將不再重新分簇，直到某個簇內的擁有最大剩余能量的節點的能量低于整個網絡中平均節點能量，將進行新一輪的簇區域選取，保證每個簇內都有可以承擔數據傳輸到基站的節點。

3.3 簇首選取和輪換

在分簇完成之后，由于節點同構且具有相同的初始能量，所以每個節點當選為簇首節點的概率相同，在簇內采用隨機方式選取簇首節點，通過基站來確定該簇內的簇首節點，然后發送廣播給簇內的普通節點，普通節點根據接收到的信息來和簇首節點進行數據傳輸。數據傳輸方式和LEACH算法相同，簇首節點為子節點分配TDMA時隙，子節點在自己的時隙內進行數據傳輸，其余時間通訊模塊則進入sleep狀態，等待下次被喚醒。普通節點發送信息包含自己的ID和剩余能量，簇首節點將接受到的數據進行融合后發送給基站。基站接收到信息之后，根據剩余能量和位置信息來生成一個輪換因子μ，它由下式決定：

式中ke和ks是常數，由能量消耗決定。Elast表示節點的剩余能量，d是節點到基站的距離。在下一輪的簇首選取中，簇內輪換因子最大的可以直接升級成為簇首節點。輪換因子的確定并不介意某個節點在上一輪中已經擔任過簇首節點，因為考慮了剩余能量，如果一個節點的剩余能量遠多于簇內的其他節點，在擔任一次簇首之后，仍然是所在簇內剩余能量最大的，會繼續擔任簇首節點。從而達到簇內能量負載的平衡。避免一些雖然沒有擔任過簇首節點，但是本身剩余能量較低的節點擔任簇首節點。

3.4 簇間通訊與多跳接力通信

從能量模型中我們可以看到，當數據傳輸距離過大時，能量消耗會急劇增加，并且超過了數據接收，因此，雖然數據接收也是一筆不小的消耗，但是在進行超遠距離通訊時選擇多跳接力通訊仍能減少數據傳輸的能量消耗。本文對LEACH算法的數據傳輸模式進行兩方面的改進：第一個方面是多跳與單跳結合的數據傳輸方式，這個在以前的LEACH算法改進中也有見到，本文與以前有所不同的是，并不會總是選擇距離基站較近的簇首擔任下一跳的節點，而是在較近的區域選擇一批具有較大剩余能量的節點進行多跳，并且會計算成本，只有接力通訊方式總成本比直接通訊消耗減少超過一定比例時才選擇多跳，這個比例是與K的有關，K由下面的式子決定：

其中，Ef-last是備選多跳點區域內的的平均剩余能量，Eb-last是距離節點較遠的節點平均剩余能量。由于簇分布選擇的固定簇大小一樣，因此簇首直接與基站進行數據傳輸時，距離較遠簇能量消耗要比距離較近簇大。多跳接力時，距離基站較近的節點會被選為下一跳的節點，則會增加距離基站較近的節點的能耗。因此，在數據通訊時，基站將根據剩余能量進行對比，在降低系統級能耗與平衡各個節點能耗之間選擇一個平衡，則可以最大限度延長網絡整體的壽命。

除了上述改進，為了進一步拓展網絡的適用范圍，考慮到無線傳感器網絡可能安裝在距離基站較遠的地方，可以在進行超遠距離數據傳輸時，在基站與網絡間設置中轉，中轉采用外接電源供電，負責基站與傳感器網絡之間的數據轉傳。根據具體的情況，還可以使用多級接力通訊。

4 算法仿真及分析

本文仿真選擇NS2來對LEACH極其改進進行仿真對比。文中的仿真環境是WindowsXP+cygwin+NS-2.27。

表1 實驗仿真參數Tab.1 Simulation parameters

圖1 兩種算法存活點比較Fig.1 The comparison of survival point between two algorithms

在NS2平臺上對兩種算法進行仿真，使用gnuplot繪制兩種算法的節點存活情況，從圖中可以看出，改進后的算法（leach-zj）第一個死亡節點時間大約是在 350s，而leach第一個死亡節點是在130s，改進后的第一個死亡節點時間是leach算法的2.7倍。整個網絡的存活時間是leach算法的一倍左右。所以優化后的算法與leach算法相比，具有更好的網絡性能，延長了網絡的生命周期。

5 結束語

文中對LEACH的改進相對于原算法性能更優，通過動態和靜態簇頭選取相結合的方式，降低了簇首選取過程中的能量消耗，參考節點分布信息來設置每個簇的位置和簇內節點數，并且根據距基站的距離和剩余能量來選取簇頭，使得簇首分布較傳統分布更為均勻，并且平衡了能量負載，不僅有效避免個別節點提前死亡，也使得整體能量消耗有了一定程度的減少，提高了網絡的生存能力。

[1]Haas Z，Halpen J， Li L.Gossip-Based ad hoc routing.IEEE/ACM Transactions on Networking，Piscataway [J].IEEE Press，2006:479-491.

[2]Heinzelman W，Chandrakasam A，Balakrishnan H.Energy efficient communication protocol for wireless microsenser[C]//Proceeding of the 33rd Hawaii International Conference on System Sciences，2000.

[3]Karp B，Kung H.GPSR:Greedy Perimeter Stateless Routing for Wireless Networks.Proceedings of the 6th Annual International Conference on Mobile Computing and Networking[C].Boston，USA，2000:243-254

[4]呂濤，朱清新，張路橋.一種基于LEACH協議的改進算法[J].電子學報，2011，39（6）：1045-1049.LV Tao，ZHU Qing-xin，ZHANG Lu-qiao，et al.An improved LEACH algorithm in wireless sensor network[J].Acta Electronica sinica，2011，39（6）：1045-1049.

[5]李成岳，申鉉京，陳海鵬，等.無線傳感器網絡中LEACH路由算法的研究與改進[J].傳感技術學報，2010，23（8）：1163-1167.LI Cheng-yue，SHEN Xuan-jing，CHEN Hai-peng，et al.Research and improvement of LEACH routing algorithm for wireless sensor networks[J].Chinese Journal of Sensors and Actuators，2010，23（8）：1163-1167.

[6]Younis，S Fahamy.Distributed clustering in ad-hoc sensor networks:A hybrid.energy-efficient approach[J].IEEE Infocom，2004（1）:629-640.

[7]蔣陽，孫柳林，敖文鈞，等.WSN中LEACH路由協議簇頭數優化研究[J].計算機應用研究，2010，27（11），4251-4253 JANG Yang，SUN Liu-lin，AO Wen-jun，et al.Research on optimal cluster-head number of LEACH routing protocol for WSN[J].Application Research of Computers.2010，27（11），4251-4253.

[8]趙秀蘭，許秀蘭，李克清.基于LEACH協議的差異化分簇路由算法[J].計算機應用研究，2013，30（3）：866-868.ZHAO Xiu-lan，XU Xiu-lan，LI Ke-qing.LEACH-based protocol difference of cluster-based routing algorithm[J].Application Research of Computers，2013，30（3）：866-868.

[9]張強，盧瀟，崔曉臣.基于能量高效的無線傳感器網絡LEACH協議改進[J].計算機工程與設計，2011，32（2）：427-429.ZHANG Qiang，LU Xiao，CUI Xiao-chen.Improvement of low energy adaptive clustering hierarchy routing protocol based on energy-efficient for wireless sensor network[J].Computer Engineering and Design，2011，32（2）：427-429.

[10]Heinzelman W B，et al.An application-specific protocol architecture for wireless microsensor networks[J].IEEE Trans on Wireless Communications，2002，1（4）:660-670.