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

郭 軍

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

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

郭 軍

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

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

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

0 引 言

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

1 LEACH算法及改進(jìn)

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

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

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

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

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

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

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

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

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

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

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

2 仿真實(shí)驗(yàn)

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

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

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

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

圖3描述的是網(wǎng)絡(luò)節(jié)點(diǎn)總能耗與基站通信的數(shù)據(jù)量之間的關(guān)系。整個(gè)網(wǎng)絡(luò)的生存周期與各個(gè)節(jié)點(diǎn)的能耗有關(guān)，如果某個(gè)節(jié)點(diǎn)耗能大，那么該節(jié)點(diǎn)將很快失效，如果各個(gè)節(jié)點(diǎn)的能耗相似，那么網(wǎng)絡(luò)的生存周期將延長(zhǎng)。而LEACH協(xié)議是個(gè)聚類協(xié)議，充當(dāng)簇首的次數(shù)多，或者距離基站遠(yuǎn)都將消耗更多的能量，為了在全網(wǎng)平衡消耗的能量，只能讓那些距離基站近的節(jié)點(diǎn)多充當(dāng)簇首，而距離基站遠(yuǎn)的節(jié)點(diǎn)減少充當(dāng)簇首的概率，這樣才能使各節(jié)點(diǎn)的能耗相當(dāng)。E-RLEACH算法在各節(jié)點(diǎn)剩余能量相差較大時(shí)，優(yōu)先考慮能量多的節(jié)點(diǎn)充當(dāng)簇首，恰好平衡了各節(jié)點(diǎn)的能耗，延長(zhǎng)了網(wǎng)絡(luò)周期。在各節(jié)點(diǎn)在擁有相同的初始能量的前提下，傳輸相同的數(shù)據(jù)量，消耗更少的能量將導(dǎo)致更長(zhǎng)的網(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算法隨機(jī)性簇首選擇帶來的能耗問題，本文綜合考慮剩余能量的均方值與隨機(jī)性因素后提出了一種新算法：E-R-LEACH算法。該算法根據(jù)各節(jié)點(diǎn)剩余能量的均方值的大小自適應(yīng)地影響簇首選擇。仿真結(jié)果表明，該算法在延長(zhǎng)網(wǎng)絡(luò)生存周期和降低節(jié)點(diǎn)能耗方面比傳統(tǒng)的LEACH算法具有更好的性能?！?/p>

［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é)議的研究與改進(jìn)[D]. 濟(jì)南：山東大學(xué)，2008.

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

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

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

［9］ 李圣普，王小輝. 基于剩余能量的LEACH協(xié)議改進(jìn)算法[J]. 計(jì)算機(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