基于最低能耗的改進LEACH分簇算法

孫文勝+朱為佳+苗紅亮

摘要：針對LEACH（Low Energy Adaptive Clustering Hierarchy）算法中的隨機分簇和簇頭能耗不均問題，提出一種基于最低能耗的改進LEACH分簇算法MEC-LEACH（Minimum Energy Consumption based LEACH）。MEC-LEACH分簇算法通過最小化網絡能耗得出最優簇頭數，同時引入簇頭的剩余能量和簇頭距離sink節點的遠近等因素綜合選舉簇頭節點，使得剩余能量較大且距離sink較近的節點優先成為簇頭節點，進而均衡簇頭節點和網絡總的能耗。仿真實驗表明，MEC-LEACH算法相比其它改進算法可以有效降低網絡能耗，延長網絡生存時間。

關鍵詞：LEACH協議；隨機分簇；最低能耗；剩余能量；網絡生存時間DOI：10.11907/rjdk.162713中圖分類號：TP312文獻標識碼：A

文章編號：16727800（2017）004004405

0引言 無線傳感器網絡（Wireless Sensor Networks，WSN）[1]是由大量微型傳感器節點自組織和自適應形成的通信網絡，網絡內的傳感器節點自身具有感知、存儲和處理數據的能力，可以將感知數據通過無線方式發送給用戶。近年來，隨著微機電系統、片上系統、無線通信和低功耗嵌入式技術的飛速發展，WSN受到越來越多的關注，其在軍事國防、智能家居、環境監測以及醫療等領域廣泛應用。但是無線傳感器網絡的節點能量有限且不易進行實時更換，這使得如何更高效地利用有限的節點能量延長網絡壽命，成為WSN中非常重要的設計目標。 分簇的網絡結構可以方便地進行節點管理、資源分配以及負載均衡，所以分簇算法往往被用來進行優化無線傳感器網絡的能量消耗。其中最經典的分簇算法是Heinzelman等[2]提出的LEACH算法，相比于沒有分簇的網絡，LEACH算法可以延長網絡壽命15%左右。但是，由于LEACH算法采用隨機選擇簇頭機制，容易出現簇頭節點過早死亡，從而導致網絡能量消耗不均，降低了網絡性能。 針對LEACH算法的不足，很多學者提出了新的算法以改進和提高LEACH算法的性能。文獻[3]提出的LEACH-C算法采用sink節點統一管理網絡節點和分簇的策略，并且根據節點剩余能量進行簇頭選擇，有效均衡了網絡能耗，但是簇頭選擇機制只單純考慮了節點的剩余能量會導致距離sink較遠的節點成為簇頭，加重了簇頭的能耗。文獻[4]研究了LEACH-C算法，提出改進后的pLEACH算法，pLEACH采用最優簇頭思想等分圓形網絡區域，每個區域內再進行簇頭選舉，下一輪選舉簇頭時，網絡旋轉一定角度形成新的分簇區域，有效避免了簇頭節點集中在某一處的問題，但是依然存在簇頭距離sink較遠的問題。文獻[5]中的EH-LEACH算法同樣采用了最優簇頭的思想，將網絡劃分為一個個網格，每個網格為一個簇，并且選擇簇頭時考慮了節點的剩余能量，有效均衡了網絡能耗，但是該算法中最優簇頭的劃分沒有考慮網絡實時變化的因素，隨著網絡運行，最初的最優狀態可能并非最優。文獻[6]、[7]針對LEACH算法均是改進其選舉簇頭時的閾值，考慮了節點的剩余能量，而并沒有考慮最優簇頭以及簇頭距離sink的距離。文獻[8]提出的改進LEACH算法雖然選擇簇頭時考慮了節點的剩余能量以及節點位置信息，但沒有考慮網絡能耗決定的最優簇頭的影響，一定程度上增加了網絡能耗。文獻[9]提出的M-LEACH算法根據網絡能耗確定最優簇頭，選擇簇頭時基于節點的剩余能量和上一輪節點消耗的能量來進行選舉，該算法在一定程度上均衡了網絡能耗，但是確定最優簇頭時只考慮了簇頭穩定傳輸階段的能耗，并沒有考慮簇頭形成階段的能耗，以及簇頭距離sink的距離等因素，網絡能耗還可以進一步降低。 本文在以上研究的基礎上，針對LEACH算法的隨機分簇和網絡能耗不均問題提出基于最低能耗的改進LEACH分簇算法MEC-LEACH（Minimum Energy Consumption based LEACH）算法，利用最小化網絡能耗決定網絡分簇數，進而根據最優簇頭概率以及簇頭的剩余能量和簇頭距離sink的遠近來選擇簇頭節點，使得簇頭能耗更加均衡，從而降低整個網絡的能耗，延長網絡壽命。

1LEACH算法 1.1算法流程簡述 LEACH算法采用了“輪”的方式進行簇頭的重新選擇。每一“輪”運行過程主要分為兩個階段完成，分別為簇的形成階段和穩定傳輸階段[10]。在簇的形成階段，每個傳感器節點產生一個[0～1]之間的隨機數，如果產生的隨機數小于給定的閾值T（n），該傳感器節點則廣播成為簇頭節點的消息，其它節點根據接收到成為簇頭節點消息的強弱判斷自己加入哪一個簇，并發送加入簇的請求消息至簇頭，簇頭接收普通節點的加入請求后，按照時分復用為每一個簇內的節點劃分特定的時隙，再將時隙表廣播至簇內的成員節點。簇內成員接收時隙表消息，在指定的時隙內發送數據給簇頭節點。至此，簇的形成階段完成。其中選擇簇頭時給定的閾值T（n）表達式如下：其中，p為簇頭占節點總數的比例，n為節點個數，r為當前網絡運行的輪數，G為最近輪內沒有當過簇頭的傳感器節點集合。LEACH算法中，所有簇形成后，網絡開始進入穩定傳輸階段。簇內成員節點根據簇頭分配的TDMA時隙，完成數據采集以及將數據發送給簇頭節點。如果當前節點的時隙尚未到來，節點可以暫時關閉發送數據模塊，進入睡眠狀態，需要發送數據時再打開。簇頭節點則在一輪運行時間結束前，一直處于接收數據狀態。為了防止簇間干擾，每個簇內使用唯一的CDMA擴展編碼進行通信。當簇頭完成簇內成員數據的采集后將其與自身的數據融合并統一發送給sink節點，sink節點接收所有簇頭節點的數據后再發送至用戶，接著運行下一輪的過程[11]。

1.2算法能耗模型LEACH算法能耗主要來自兩個部分，分別為節點接收數據的能耗和發送數據的能耗。其中傳感器節點發送Lbit數據的能耗如下式所示[12]：式中，Eelec為無線電收發單位比特數據能耗系數；參數εfs和εmp分別表示自由空間能耗和多徑衰落能耗中的功率放大系數；d為源節點與目的節點間的距離，d0決定了傳輸模型，如果節點傳輸距離超過d0，則傳輸能耗采用多徑衰落，能耗與距離的四次方成正比，反之則采用自由空間模型，能耗與距離的平方成正比。d0可由如下公式得到：

1.3算法不足LEACH算法采用“輪”的思想，并且產生隨機數的方式，使得所有傳感器節點成為簇頭的概率相同，可以有效均衡能量消耗。但是LEACH算法仍然存在以下不足：（1）隨機產生的簇頭節點可能出現節點剩余能量較低，由于簇頭本身需要完成更多較普通節點的任務，所以較低的能量會導致該簇頭過早死亡，同時如果距離sink節點較遠的節點成為簇頭時，遠距離的數據傳輸同樣加重了簇頭的能耗，加速了節點死亡，從而降低了網絡生存時間。（2）不同的網絡規模下，分簇的數量應根據網絡規模進行自適應調整。如果分簇過少，則會出現每個簇過大，簇內成員過多，簇頭節點無法完成過多的數據處理，造成信息傳輸效率降低。分簇過多時，簇頭節點過多，則出現網絡大部分數據傳輸都是單跳的，這樣失去傳感器網絡多跳的優勢，不能達到延長網絡壽命的目的。〖BT1〗〖STHZ〗〖WTHZ〗2MEC-LEACH算法針對以上不足，本文提出基于最低能耗改進LEACH的MEC-LEACH算法，利用最小化網絡能耗得出最優簇頭數量，然后均衡最優簇頭概率、節點剩余能量以及節點距離sink的距離來選擇簇頭節點。MEC-LEACH同樣分為簇的形成階段和穩定傳輸階段。

2.1簇的形成階段 2.1.1最優簇頭數量本文根據最小化網絡能耗來計算最優簇頭數，其中網絡能耗由簇的形成階段能耗與穩定傳輸階段能耗組成。假設在M×M的網絡區域內均勻分布n個傳感器節點，網絡分成k個簇，每個簇由一個簇頭節點和SX（nkSX）-1個普通節點組成。網絡傳輸能耗模型與LEACH算法相同，設傳輸數據為Lbit。在簇的形成階段，網絡的主要能耗來自3個部分，分別為：節點宣告成為簇頭消息的能耗、普通節點加入簇內以及簇頭分配TDMA時隙的能耗。其中簇頭節點的主要能耗包含：開始廣播簇頭消息的能耗、接收簇內節點加入簇的能耗和廣播TDMA時隙的能耗。根據公式（2）可以得出該階段簇頭的總能耗為：式中，d為簇頭廣播的距離，因為全網廣播，所以采用多徑衰落傳輸模型。dtoCH為簇內節點到簇頭的距離。在該階段簇內普通節點的能耗主要包含：接收簇頭廣播消息的能耗、發送加入簇的消息能耗和接收TDMA時隙的能耗。所以得到的能耗如下：穩定傳輸階段，主要能耗來源于簇頭數據收集和普通節點數據采集，以及簇頭數據融合和發送數據給sink節點。其中簇頭節點在穩定傳輸的每一幀能耗為：接收感知數據的能耗、融合數據的能耗以及發送數據至sink節點的能耗。所以可以得到總能耗為如下公式所示：其中，EDA為簇頭融合單位比特數據的能耗，dtoBS為簇頭到sink的距離，本文假設sink距離較遠，采用多徑傳輸。簇內普通節點在穩定傳輸階段每一幀能耗主要來自發送數據給簇頭節點，可以得出所有普通節點在穩定傳輸階段的能耗如下：

2.2穩定傳輸階段在穩定傳輸階段，簇內成員節點根據自身的TDMA時隙，在指定時間內發送自身感知數據以及自身ID和當前剩余能量給簇頭節點，簇頭收集完簇內成員的剩余能量以及成員的數據信息后，再將融合后的數據進一步發送至sink節點，sink節點根據最新的全網剩余能量可以計算出當前的最佳分簇和最優簇頭概率，選擇新一輪簇頭時，再將該信息廣播至全網。其它節點再根據自身能量選舉簇頭，以進入新的一輪網絡循環運行。綜上，MEC-LEACH算法的流程如圖1所示。

3仿真結果與分析

3.1仿真環境與參數設定為了驗證MEC-LEACH算法的有效性，本文采用Matlab仿真平臺對本文算法與文獻[5]EH-LEACH算法以及文獻[9]中的改進LEACH算法進行了仿真和對比。分別從網絡生存時間、網絡總能耗以及sink接收數據量等方面進行分析和比較。實驗網絡環境假設為：在100m100m的正方形區域內均勻分布100個傳感器節點，節點均為同構的且具有GPS定位裝置。Sink節點位于網絡外固定位置。表1為實驗參數設定。3.2實驗結果分析

3.2.1權重因子λ取值〖JP2〗MEC-LEACH算法簇頭節點選擇時需要考慮節點的剩余能量以及簇頭距離sink的遠近占簇頭選舉的比重，所以實驗中分別對權重因子取不同值分析其對網絡壽命以及網絡能耗的影響，從而確定一個最優值。由式（16）中λ取值范圍，分別對權重因子取值：0、0.1、0.2、0.3、0.4、0.5、0.6、0.7、0.8、0.9、1.0。實驗結果如圖2、圖3所示。

可以看出，隨著權重因子λ的增加，網絡的存活時間逐漸延長，網絡能耗逐漸降低，當λ=0.6時，網絡總能耗最低并且網絡存活時間最長。此后λ逐漸增大，網絡存活時間下降而網絡能耗也隨之增加，可見權重因子取值0.6時，即選擇簇頭時節點的剩余能量占比60%，簇頭與sink的距離占比40%時，網絡性能相對最佳，壽命更長。下面分別對當λ取值0.6時，本文MEC-LEACH算法與其它的改進LEACH算法進行算法性能比較。3.2.2網絡生存時間網絡生存時間直接關系到網絡性能好壞，本文借助統計網絡內每隔一段時間存活的節點數目來衡量網絡生存時間長短。3種算法的網絡生存時間如圖4所示。

可以看出，3種算法中，本文分簇算法最遲出現死亡節點并且網絡生存時間最長，大約為1600s，相比EH-LEACH算法1200s和文獻[9]的算法1350s，分別提升了約33%和19%。這主要因為，EH-LEACH算法和文獻[9]的算法均沒有考慮網絡實時變化導致最優簇頭的變化，導致網絡分簇不均，簇頭節點能耗不均衡。文獻[9]雖然相比EH-LEACH算法在選擇簇頭時考慮了簇頭上一輪消耗的能量，但沒有考慮最優分簇以及簇頭距離sink的遠近，所以其相比EH-LEACH算法，網絡生存時間提升并不明顯，仍然沒有本文的分簇算法生存時間長。3.2.3網絡能耗網絡系統總的能量消耗，可以衡量系統性能好壞以及網絡能量消耗均衡性。3種算法對應的網絡總能耗如圖5所示。從圖5可以看出，3種算法中，本文分簇算法網絡總能耗最少，其次是文獻[9]算法，EH-LEACH算法能耗最多。EH-LEACH算法中網絡簇頭個數始終不變，這樣導致網絡運行后期，有的簇內可能剩下的都是剩余能量較低的節點，加劇了節點死亡，增加了網絡能耗。文獻[9]同樣沒有考慮網絡運行過程中簇頭數變化的影響，同時簇頭選擇時沒有考慮簇頭距離sink的遠近，距離sink較遠的簇頭能耗增加，導致其網絡總能耗的增加。本文分簇算法由最小化網絡能耗得到最優簇頭，以及選擇簇頭時綜合考慮節點剩余能量和簇頭距離sink的遠近，可以有效降低和均衡網絡能耗。

3.2.4sink接收數據量通過對sink接收數據量分析，可以直觀顯示出網絡的傳輸效率，進而衡量網絡性能的好壞。3種算法的sink接收數據量如圖6所示。

從圖6可以看出，由于其它兩種算法選擇簇頭節點時均沒有考慮簇頭距離sink 的遠近因素，可能會出現距離sink較遠的節點成為簇頭節點，這樣增加了簇頭發送數據的能耗，以及發送數據的時間。所以相同時間內，EH-LEACH算法和文獻[9]算法sink接收數據量均沒有本文分簇算法多。此外，由于能耗不均，導致網絡生存時間降低，相同時間內，本文分簇算法存活節點更多，發送數據越多，sink節點接收的數據也越多。網絡運行至1600s左右時，本文分簇算法中sink共接收約203 000數據包，相比EH-LEACH算法（約137 000）和文獻[9]的算法（約CM152 000），分別提升了48%和34%。

4結語 本文在分析LEACH算法的基礎上，針對其隨機分簇和簇頭能耗不均的問題，通過最小化網絡能耗來得到最優的分簇個數。在簇頭節點選擇上，考慮了最優簇頭概率、簇頭節點的剩余能量以及簇頭與sink節點間的距離，使得剩余能量較高、距離sink較近的節點更容易成為簇頭節點。仿真實驗表明，相比其它的改進LEACH算法，本文提出的MEC-LEACH算法可以有效延長網絡生存時間，降低和均衡網絡能耗，提高網絡sink節點接收數據量，進而提升網絡性能。

參考文獻：[1]李曉維.無線傳感器網絡技術[M].北京：北京理工大學出版社，2007.

[2]HEINZELMAN，RABINER W，CHANDRAKASAN，et al.Energyefficient communication protocol for wireless microsensor networks[J].Adhoc & Sensor Wireless Networks，2000（18）：1520.

[3]HEINZELMAN W B，CHANDRAKASAN A P，BALAKRISHNAN H.An applicationspecific protocol architecture for wireless microsensor networks[J].IEEE Transactions on Wireless Communications，2002，1（4）：660670.

[4]GOU H，YOO Y.An energy balancing LEACH algorithm for wireless sensor networks[C].International Conference on Information Technology：New Generations，Itng 2010，Las Vegas，Nevada，Usa，2010：822827.

[5]PITHVA B，PATTANI K，CHRISTIAN A.Optimization of leach protocol in wireless sensor network[J].International Journal of Computer Applications，2014，93（12）：9758887.[6]王臻躍.基于LEACH的改進路由協議[J].軟件導刊，2015（3）：114116.

[7]吳標，余劍，易仁杰.基于節點剩余能量的分時分簇LEACH改進算法[J].火力與指揮控制，2016，41（10）.

[8]余成波，鄧順華，方軍，等.基于節點位置與剩余能量的LEACH協議優化[J].傳感器與微系統，2016，35（5）：139141.

[9]譚軍.簇首選擇改進的 LEACH 無線傳感器路由協議[J].計算機應用與軟件，2015（6）：171173.

[10]〖ZK（#〗鄭增威，吳朝暉.若干無線傳感器網絡路由協議比較研究[J].計算機工程與設計，2003，24（9）：2831.

[11]GIRGIRI A，AMINUBABA M，ALI L G，et al.Minimising energy consumption in wireless sensor network by enhancement of LEACH protocol[J].International Journal of Computer Science & Management Studies，2015.

[12]劉明，龔海剛，毛鶯池，等.高效節能的傳感器網絡數據收集和聚合協議[J].軟件學報，2005，16（12）：21062116.

（責任編輯：陳福時）