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

孫文勝+朱為佳+苗紅亮

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

關(guān)鍵詞：LEACH協(xié)議；隨機分簇；最低能耗；剩余能量；網(wǎng)絡(luò)生存時間DOI：10.11907/rjdk.162713中圖分類號：TP312文獻標識碼：A

文章編號：16727800（2017）004004405

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

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

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

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

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

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

3仿真結(jié)果與分析

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

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

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

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

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

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

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

參考文獻：[1]李曉維.無線傳感器網(wǎng)絡(luò)技術(shù)[M].北京：北京理工大學(xué)出版社，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的改進路由協(xié)議[J].軟件導(dǎo)刊，2015（3）：114116.

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

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

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

[10]〖ZK（#〗鄭增威，吳朝暉.若干無線傳感器網(wǎng)絡(luò)路由協(xié)議比較研究[J].計算機工程與設(shè)計，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]劉明，龔海剛，毛鶯池，等.高效節(jié)能的傳感器網(wǎng)絡(luò)數(shù)據(jù)收集和聚合協(xié)議[J].軟件學(xué)報，2005，16（12）：21062116.

（責(zé)任編輯：陳福時）