郭 軍

(天津醫(yī)科大學 天津 300203)

一種改進的無線傳感器網(wǎng)絡(luò)LEACH算法

郭 軍

(天津醫(yī)科大學 天津 300203)

LEACH協(xié)議是無線傳感器網(wǎng)絡(luò)協(xié)議中的經(jīng)典協(xié)議，該協(xié)議對簇首的閾值設(shè)置采取隨機方式。改進了LEACH算法簇首閾值的設(shè)置方式，除考慮隨機性以外，增加了剩余能量因素的考慮，并且剩余能量對閾值的影響根據(jù)均方值的大小自適應(yīng)變化。利用通用的計算機仿真平臺NS2對經(jīng)典LEACH算法和新算法進行仿真比較，結(jié)果表明，改進后的協(xié)議至少能夠延長網(wǎng)絡(luò)生存周期的27.5%,。

無線傳感器網(wǎng)絡(luò) 計算機仿真 LEACH算法

0 引 言

無線傳感器網(wǎng)絡(luò)最先應(yīng)用于軍事國防領(lǐng)域。隨著技術(shù)的發(fā)展，其在工業(yè)、農(nóng)業(yè)、環(huán)境保護領(lǐng)域應(yīng)用廣泛，近幾年來，在抗擊自然災害以及生物醫(yī)療領(lǐng)域也有不俗的表現(xiàn)。下一代傳感器網(wǎng)絡(luò)的發(fā)展方向是無線傳感器網(wǎng)絡(luò)。無線傳感器節(jié)點的工作環(huán)境決定了它常常使用電池提供能量，因此其工作壽命受限于電池的能量。要延長無線傳感器網(wǎng)絡(luò)的生存周期，降低通信過程中的能量損耗是一種有效的途徑。無線傳感器網(wǎng)絡(luò)有諸多協(xié)議，如LEACH(Low Energy Adaptive Clustering Hierarchy)、[1]TEEN、[2]APTEEN、[3]PEGASIS[4]等。這些協(xié)議都是聚類性(Clustering)協(xié)議，其中LEACH協(xié)議是最早提出的分層協(xié)議，其他協(xié)議都是在LEACH協(xié)議的基礎(chǔ)上發(fā)展而實現(xiàn)的。TEEN協(xié)議是一種實時性較高的協(xié)議，通過軟硬兩個閾值控制通信量來節(jié)省能量；APTEEN協(xié)議根據(jù)用戶需要和應(yīng)用類型對TEEN協(xié)議進行擴展，對協(xié)議的相關(guān)閾值和周期性重新設(shè)置，是一種混合協(xié)議。PEGASIS協(xié)議中節(jié)點降低信號的強度，使得該信號只能被鄰居節(jié)點接收到，數(shù)據(jù)交換后將數(shù)據(jù)融合，然后送往基站。國內(nèi)一些前期的研究已經(jīng)在簇首(cluster head)的選取以及數(shù)量的最優(yōu)選取、[5]路由選擇[6-7]以及數(shù)據(jù)融合[8]等方面展開。文獻[5]認為簇首的數(shù)量如果能夠滿足網(wǎng)絡(luò)內(nèi)全部節(jié)點與基站一次通信所有數(shù)據(jù)的需求，就能夠降低能耗，提高生存周期，并依此修改了簇首數(shù)目的計算公式；此外，為了解決網(wǎng)絡(luò)中有的區(qū)域簇首數(shù)量多而有的區(qū)域簇首少的問題，該文獻引入權(quán)重的概念，將整個網(wǎng)絡(luò)劃分成多個區(qū)域，考慮節(jié)點剩余能量和鏈路代價，使簇頭節(jié)點均勻分布在網(wǎng)絡(luò)中，有效減少了不必要的傳輸損耗。文獻[7]從剩余能量、節(jié)點位置、歷史貢獻3個方面考慮選擇簇首，并在簇首選擇時引入了博弈論；文獻[9]對于簇首的選取考慮了節(jié)點剩余能量和簇首節(jié)點平均能耗的影響，但是各個節(jié)點剩余能量均方差對簇頭選舉的影響并未考慮。前面的說明中可以發(fā)現(xiàn)，LEACH協(xié)議作為一種經(jīng)典協(xié)議有不少優(yōu)點，但是同時也存在需要改進的地方，比如簇首節(jié)點的數(shù)量問題、位置問題以及節(jié)點的能量分布問題。本文在LEACH協(xié)議的基礎(chǔ)上，綜合考慮隨機量選、剩余能量以及能量分布均方差這3個影響因素，對網(wǎng)絡(luò)簇首的選取提出了一種新的協(xié)議。

1 LEACH算法及改進

LEACH協(xié)議是一種自適應(yīng)分簇協(xié)議，利用分簇功能，整個網(wǎng)絡(luò)能夠?qū)Y源做更合理的分配，因此LEACH協(xié)議的出現(xiàn)相對于傳統(tǒng)多跳路由協(xié)議和靜態(tài)分簇協(xié)議而言，可以延長網(wǎng)絡(luò)生命周期。LEACH協(xié)議中定義一個準備階段和一個就緒階段為一輪(round)的工作時間。在準備階段，LEACH協(xié)議首先選擇簇首節(jié)點，采取的方案為隨機選取。選定簇首節(jié)點后，需要將簇首節(jié)點的信息廣播告知網(wǎng)絡(luò)內(nèi)非簇首節(jié)點。傳感器節(jié)點收到廣播信號后，就近加入廣播信號最強的簇首節(jié)點所構(gòu)建的簇群，入群前需向該群的簇首發(fā)送入群請求數(shù)據(jù)包。簇首收到節(jié)點入群請求后，需要給各個傳感器節(jié)點分配時隙，采用的分配策略為TDMA。準備階段結(jié)束后，進入就緒階段。簇首節(jié)點匯聚簇內(nèi)各傳感器節(jié)點的采集數(shù)據(jù)，所采集的數(shù)據(jù)通常具有冗余性，因此向基站傳輸匯聚數(shù)據(jù)之前常常采用數(shù)據(jù)融合技術(shù)去除數(shù)據(jù)的冗余性，減少數(shù)據(jù)傳輸量，從而達到減少能耗的目的。

LEACH協(xié)議中的網(wǎng)絡(luò)生存期是1個重要指標，為了延長該指標，采用隨機輪換簇首的方案。這是因為簇首是整個簇群與基站通信的數(shù)據(jù)匯聚點，需要消耗大量的能量來進行通信過程，如果不更換簇首，能量有限的簇首很快就會耗盡能量而死亡，采用簇首更換方案后，讓各節(jié)點都有機會充當簇首，整個生存周期中各節(jié)點的能量消耗盡量均衡，從而達到延長生命的目的。簇首選擇的具體辦法是：在每一輪的簇首選擇前，先按照公式(1)計算1個閾值T(n)，然后隨機分配0和1之間的一個數(shù)值給每一個傳感器節(jié)點，如果某個節(jié)點分配的數(shù)值小于閾值T(n)，那么該節(jié)點被選舉為簇首節(jié)點。

式中，n為整個網(wǎng)絡(luò)中依然存活的傳感器節(jié)點；p為簇首節(jié)點數(shù)目與網(wǎng)絡(luò)中所有節(jié)點數(shù)量的百分比；r為已經(jīng)完成的通信輪數(shù)；G為當前輪開始前非簇首節(jié)點的傳感器節(jié)點集合。

LEACH協(xié)議中，依靠事先設(shè)定的簇首占總節(jié)點數(shù)的比例和已成為簇首的節(jié)點數(shù)目可以很容易地計算出閾值，然后再依據(jù)隨機數(shù)和閾值的比較來產(chǎn)生簇首。各個節(jié)點剩余的能量將隨著LEACH協(xié)議運行的輪數(shù)的增加而出現(xiàn)劇烈的變化。節(jié)點間或者節(jié)點與基站間的通信距離越遠，消耗的能量越多，剩余的能量越少；如果讓剩余能量少的節(jié)點在后續(xù)的輪數(shù)中繼續(xù)充當簇首，這些簇首的能量將被快速耗盡而死亡，當網(wǎng)絡(luò)中出現(xiàn)大量的死亡節(jié)點時，整個網(wǎng)絡(luò)的正常工作將受到影響。

為了克服LEACH協(xié)議的上述缺點，本文在LEACH協(xié)議的基礎(chǔ)上提出了一個新算法E-RLEACH，該算法做了如下修改：

①計算閾值時，附加考慮剩余能量對簇首選舉的影響，如公式2所示：

式中，參數(shù)n、p、r、G與公式(1)中的相同，Er-r為第r輪開始時節(jié)點剩余的能量，Er-a為第r輪開始時所有節(jié)點剩余的平均能量，α為影響因子。

②影響影子α 將隨著節(jié)點能量分布的均方差的變化而自適應(yīng)變化，如公式(3)所示：

式中，參數(shù)k為比例常數(shù)，N為r輪過后依然存活的節(jié)點數(shù)，Er-r為第r輪開始時節(jié)點i剩余的能量，Er-a為第r輪開始時所有節(jié)點剩余的平均能量。

新算法流程圖如圖1所示。

從流程圖中可以看出，公式(2)的閾值計算是本文與傳統(tǒng)LEACH算法的不同之處，在公式(2)中考慮了隨機閾值、剩余能量以及各節(jié)點剩余能量均方差的影響。

2 仿真實驗

為了驗證新算法的性能，選取了一款通用的仿真軟件NS2，[10]整個網(wǎng)絡(luò)中傳感器節(jié)點的數(shù)量為100個，簇首節(jié)點與存活節(jié)點數(shù)量的比例為5%,，基站的坐標設(shè)置在(50，175)處，在1,000×1,000的仿真平面區(qū)域內(nèi)隨機分布100個傳感器節(jié)點，配置3,J初始能量給每個傳感器節(jié)點。

網(wǎng)絡(luò)中傳感器節(jié)點存活的數(shù)量與仿真時間的關(guān)系如圖2所示。LEACH算法仿真時在130,s的時候出現(xiàn)了第1個死亡節(jié)點，而新提出的算法E-RLEACH仿真時在420,s時出現(xiàn)第1個死亡節(jié)點，第1個死亡節(jié)點出現(xiàn)的時間比LEACH算法延長了3倍多；在兩種算法的50%,網(wǎng)絡(luò)節(jié)點死亡時間對比中，LEACH算法用時310,s，E-R-LEACH算法卻把時間延長了64.5%,，達到了510,s；在整個網(wǎng)絡(luò)生存時間對比中，LEACH算法的時間為510,s，而E-R-LEACH用時650,s，整個網(wǎng)絡(luò)失效的時間延長了27.5%,。從圖2的仿真結(jié)果對比中可以發(fā)現(xiàn)，同樣的仿真條件下，E-R-LEACH算法比LEACH算法擁有更長的網(wǎng)絡(luò)生存周期。分析其中的原因，主要是剩余能量與影響因子影響了簇首的選舉，影響因子α 的定義如公式(3)所示，它的數(shù)值大小隨節(jié)點能量分布的均方差自適應(yīng)變化；當各節(jié)點能量比較相近時，能量分布的均方差小，此時α 較小，算法主要依靠隨機量選取簇首；當均方差較大時，各節(jié)點能量相差較大，若選擇能量低的網(wǎng)絡(luò)節(jié)點充當簇首，該節(jié)點很快會因為簇首通信中大量能量的消耗而死亡，因此在簇首的選舉中

圖2 存活節(jié)點數(shù)Fig.2 Number of alive nodes

務(wù)必提高能量多的節(jié)點充當簇首的概率，降低能量少的節(jié)點充當簇首的概率。

圖3描述的是網(wǎng)絡(luò)節(jié)點總能耗與基站通信的數(shù)據(jù)量之間的關(guān)系。整個網(wǎng)絡(luò)的生存周期與各個節(jié)點的能耗有關(guān)，如果某個節(jié)點耗能大，那么該節(jié)點將很快失效，如果各個節(jié)點的能耗相似，那么網(wǎng)絡(luò)的生存周期將延長。而LEACH協(xié)議是個聚類協(xié)議，充當簇首的次數(shù)多，或者距離基站遠都將消耗更多的能量，為了在全網(wǎng)平衡消耗的能量，只能讓那些距離基站近的節(jié)點多充當簇首，而距離基站遠的節(jié)點減少充當簇首的概率，這樣才能使各節(jié)點的能耗相當。E-RLEACH算法在各節(jié)點剩余能量相差較大時，優(yōu)先考慮能量多的節(jié)點充當簇首，恰好平衡了各節(jié)點的能耗，延長了網(wǎng)絡(luò)周期。在各節(jié)點在擁有相同的初始能量的前提下，傳輸相同的數(shù)據(jù)量，消耗更少的能量將導致更長的網(wǎng)絡(luò)生存周期，因此從圖3中可以看出，傳輸相同的數(shù)據(jù)量，新算法E-R-LEACH所使用的能量較LEACH算法少。

圖3 數(shù)據(jù)量與耗能的關(guān)系圖Fig.3 Relation of data and energy

3 結(jié) 論

為了克服LEACH算法隨機性簇首選擇帶來的能耗問題，本文綜合考慮剩余能量的均方值與隨機性因素后提出了一種新算法：E-R-LEACH算法。該算法根據(jù)各節(jié)點剩余能量的均方值的大小自適應(yīng)地影響簇首選擇。仿真結(jié)果表明，該算法在延長網(wǎng)絡(luò)生存周期和降低節(jié)點能耗方面比傳統(tǒng)的LEACH算法具有更好的性能。■

［1］ Heinzelman W，Chandrakasan A，Balakrishnan H. An application-specific protocol architecture for wireless microsensor networks [J]. IEEE Transaction on Wireless Communications，2002(10)：660-670.

［2］ Manjeshwar A，Agrawal D P. TEEN：A routing protocol for enhanced efficiency in wireless sensor net-works[C]. Proceedings of the 15th Parallel and Distributed Processing Symposium，San Francisco：IEEE Computer Society，2001：2009-2015.

［3］ Manjeshwar A，Agarwal D P. APTEEN：A hybrid protocol for efficient routing and comprehensive information retrieval in wireless sensor networks [C]. Parallel and Distributed Processing Symposium，Proceedings International，IPDPS 2002：195-202.

［4］ Lindsey S，Raghavendra C S. PEGASIS：power efficient gathering in sensor information Systems [C]. Proceedings of IEEE Aerospace Conference，2002：1125-1130.

［5］ 王聲榮. 無線傳感器網(wǎng)絡(luò)LEACH協(xié)議的研究與改進[D]. 濟南：山東大學，2008.

［6］ 張然，覃少華. 基于LEACH的傳感器網(wǎng)絡(luò)分簇路由協(xié)議[J]. 計算機工程與設(shè)計，2012，33(4)：1333-1346.

［7］ 白巖. 基于博弈論的無線傳感器網(wǎng)絡(luò)路由協(xié)議研究[D]. 長春：吉林大學，2015.

［8］ 王振飛，余利，鄭志蘊. 基于LEACH協(xié)議的多因子可靠數(shù)據(jù)融合優(yōu)化策略[J]. 計算機科學，2014，41(11A)：162-167.

［9］ 李圣普，王小輝. 基于剩余能量的LEACH協(xié)議改進算法[J]. 計算機與數(shù)字工程，2013，41(5)：703-718.

［10］ The Network Simulator-ns-2[EB/OL]. http：//www. isi. edu/nsnam/ns/.

Improved LEACH for Wireless Sensor Network

GUO Jun
(Tianjin Medical University，Tianjin 300203，China)

LEACH protocol is a classical protocol in wireless sensor network protocols．In this paper，the selection of cluster head in LEACH algorithm was improved．Random threshold，remain energy and mean square value of remain energy were synthetically considered for cluster head selection．LEACH and new algorithm were simulated by a general simulation platform NS2．Results showed that the improved protocol could prolong the surviving period of network at least by 27.5%.

wireless sensor network；computer simulation；LEACH

TN915.04；TN92

A

1006-8945(2016)08-0046-04

2016-07-05