基于LEACH算法的簇首均衡算法

鄭安達(dá)

摘要：針對LEACH算法中存在簇首密度分布不均衡的問題，該文提出了一種改進(jìn)的LEACH算法。該文算法通過選舉備用簇首的方式平衡簇首，首先根據(jù)簇首選舉區(qū)域內(nèi)的節(jié)點(diǎn)和簇首個數(shù)計(jì)算簇首密度以確定是否選舉備用簇首，然后通過選舉備用簇首作為下一輪簇首的方式減少網(wǎng)絡(luò)選舉簇首的輪數(shù)以及均衡網(wǎng)絡(luò)簇首分布。仿真實(shí)驗(yàn)表明，該文算法與LEACH算法相比，在延長網(wǎng)絡(luò)壽命和降低網(wǎng)絡(luò)能量消耗方面有顯著提升。

關(guān)鍵詞：無線傳感器網(wǎng)絡(luò)；LEACH算法；備用簇首；簇首選舉；網(wǎng)絡(luò)壽命

中圖分類號：TP393 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2018）04-0252-02

Cluster Head Equalization Algorithm Based on LEACH Algorithm

ZHENG An-da

（School of Information Engineering， Jiangxi University of Science and Technology， Ganzhou 341000，China）

Abstract：Aiming at the problem of the cluster head density is not balanced in LEACH algorithm，this paper proposes an improved LEACH algorithm.The algorithm first calculates the cluster head density according to the number of nodes and the number of cluster heads in the cluster head election area to determine whether to elect the standby cluster head，and reduces the number of cluster head election and the balanced network cluster head distribution by electing the standby cluster head as the next round cluster head.Simulation results show that the proposed algorithm improves the network lifetime and reduces the network energy consumption significantly compared with the LEACH algorithm.

Key words： wireless sensor networks；LEACH algorithm；spare cluster head；cluster head election；network lifetime

無線傳感器網(wǎng)絡(luò)（Wireless Sensor Network，WSN）是一種綜合了傳感器技術(shù)、無線通信技術(shù)、嵌入式、計(jì)算機(jī)技術(shù)等先進(jìn)技術(shù)的網(wǎng)絡(luò)結(jié)構(gòu)[1]，通常用于環(huán)境監(jiān)測、軍事領(lǐng)域、醫(yī)療護(hù)理、航空航天等領(lǐng)域。由于無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)體積小，通常被部署于環(huán)境復(fù)雜的地點(diǎn)，不容易更換電池，因此如何降低網(wǎng)絡(luò)的能量消耗成為國內(nèi)外科研機(jī)構(gòu)和學(xué)者研究的熱點(diǎn)[2-3]。

設(shè)計(jì)高效的路由算法是降低網(wǎng)絡(luò)能量消耗和延長網(wǎng)絡(luò)壽命的有效方法。目前主流的無線傳感器網(wǎng)絡(luò)路由算法可分為兩類，一類是分簇路由算法，另一類是平面路由算法[4]。由于平面路算法存在自組織工作復(fù)雜，無網(wǎng)絡(luò)管理節(jié)點(diǎn)等缺點(diǎn)，逐漸被分簇路由算法取代。其中LEACH算法[5]是最早被提出來的一種分簇路由算法。LEACH算法引入了輪的概念，以循環(huán)方式隨機(jī)選舉簇首，盡可能的使每個節(jié)點(diǎn)都能均衡地被選為簇首。許多路由算法都是基于LEACH算法的改進(jìn)，如LEACH-M算法[6]、Q-LEACH算法[7]、NPCHS-LEACH[8]算法等。

本文提出了一種改進(jìn)的LEACH算法，本文算法通過引入簇首密度，選舉備用簇首的方式以平衡簇首選舉，達(dá)到均衡網(wǎng)絡(luò)能量消耗和延長網(wǎng)絡(luò)壽命的目的。

1 LEACH算法

LEACH算法核心思想是引入輪的概念，通過循環(huán)方式進(jìn)行周期性選舉簇首，選舉分為兩個過程，第一個過程為簇首的選舉過程，第二個過程為數(shù)據(jù)傳輸過程，當(dāng)這兩個過程完成后作為一個周期的完成。一個周期完成后網(wǎng)絡(luò)進(jìn)入下一輪循環(huán)，網(wǎng)絡(luò)通過這種周期循環(huán)來選舉簇首，平衡網(wǎng)絡(luò)的能量消耗。

在簇首選舉過程，網(wǎng)絡(luò)中的節(jié)點(diǎn)隨機(jī)生成一個0到1的數(shù)，通過隨機(jī)數(shù)與閾值比較來判斷本輪是否成為簇首，如果該節(jié)點(diǎn)生成的隨機(jī)數(shù)小于閾值，則該節(jié)點(diǎn)被選為簇首。閾值為：

（1）

式中為簇首百分比，為目前進(jìn)行的輪數(shù)，為最后輪中沒有被選為簇首的節(jié)點(diǎn)集合。沒有被選中的的節(jié)點(diǎn)根據(jù)簇首的廣播信號強(qiáng)度大小決定加入的簇，并發(fā)送入簇請求。簇首收到入簇請求后建立路由列表，并將路由列表發(fā)送給列表中的節(jié)點(diǎn)。

LEACH算法可以使網(wǎng)絡(luò)中的節(jié)點(diǎn)盡可能平等地被選為簇首，平衡網(wǎng)絡(luò)能量消耗，防止在選舉中某些節(jié)點(diǎn)成為簇首的次數(shù)過多或者過少而影響網(wǎng)絡(luò)的穩(wěn)定性，但是該算法也存在一些不足。由于LEACH算法的簇首選舉在生成0到1之間的數(shù)字時(shí)是隨機(jī)的，會出現(xiàn)簇首密度過大的情況，簇頭密度過大導(dǎo)致網(wǎng)絡(luò)能量不必要的消耗，增加網(wǎng)絡(luò)能量消耗，導(dǎo)致網(wǎng)絡(luò)過快死亡。

2 LEACH算法的改進(jìn)

本文針對LEACH算法中存在簇首密度不均衡的問題進(jìn)行了改進(jìn)，引入簇首密度因素，對簇首密度過大的區(qū)域采用選舉備用簇首的策略，減少簇首選舉的輪數(shù)和均衡簇首密度，從而降低網(wǎng)絡(luò)能量的消耗。改進(jìn)后的算法運(yùn)行周期和LEACH算法一樣，也分為兩個過程，包括簇的選舉過程和數(shù)據(jù)傳輸過程。

2.1 簇首選舉

為保證網(wǎng)絡(luò)簇首選舉合理分配，在簇首選舉過程中，網(wǎng)絡(luò)中的節(jié)點(diǎn)首先根據(jù)式（1）選舉簇首，節(jié)點(diǎn)通過隨機(jī)產(chǎn)生0到1之間的數(shù)字與閾值比較，如果小于閾值，則被選為簇首。簇首選舉完成后對自身轉(zhuǎn)發(fā)范圍內(nèi)的簇首密度進(jìn)行密度計(jì)算。計(jì)算式為：

（2）

式中為轉(zhuǎn)發(fā)范圍內(nèi)節(jié)點(diǎn)的總數(shù)，為簇首轉(zhuǎn)發(fā)范圍內(nèi)簇首總數(shù)，當(dāng)簇首密度且時(shí)，本文算法認(rèn)為簇首密度過大，對簇首進(jìn)行均衡，從多余簇首中選舉備用簇首。

在選舉備用簇首時(shí)，源簇首首先向轉(zhuǎn)發(fā)范圍內(nèi)的鄰居簇首發(fā)送請求，鄰居簇首收到請求反饋本簇首的剩余能量信息，源簇首在收到剩余能量后對能量大小進(jìn)行對比，并將能量較大的簇首選為備用簇首，將備用簇首的信息發(fā)送給路由列表內(nèi)的所有節(jié)點(diǎn)和簇首。當(dāng)本周期結(jié)束后，該區(qū)域不再進(jìn)行簇首選舉，此時(shí)備用簇首開始工作并作為下一周期簇首。

2.2 數(shù)據(jù)傳輸

網(wǎng)絡(luò)數(shù)據(jù)傳輸過程與LEACH算法數(shù)據(jù)傳輸過程類似，簇內(nèi)節(jié)點(diǎn)通過TDMA時(shí)間列表向簇首發(fā)送數(shù)據(jù)。簇首在向基站發(fā)送數(shù)據(jù)之前先偵聽信道，當(dāng)信道空閑時(shí)，該簇首開始發(fā)送數(shù)據(jù)，否則該簇首等待并繼續(xù)偵聽，直到偵聽到信道空閑，如此重復(fù)該過程。數(shù)據(jù)傳輸階段完成數(shù)據(jù)的采集和傳送，簇頭完成對節(jié)點(diǎn)數(shù)據(jù)的接收、數(shù)據(jù)的融合并通過簇首之間的數(shù)據(jù)傳送轉(zhuǎn)發(fā)給基站。

2.3 能量模型

傳感器節(jié)點(diǎn)主要由收發(fā)器、處理器、傳感單元、供電單元等四個部分組成，傳感器節(jié)點(diǎn)的能量消耗主要集中在該四個組成部分。收發(fā)器用來進(jìn)行節(jié)點(diǎn)之間或者節(jié)點(diǎn)與基站之間的通信，是數(shù)據(jù)傳輸?shù)闹饕糠?，處理器用于?jié)點(diǎn)的管理、數(shù)據(jù)的融合和處理等功能，傳感單元用于獲取周圍環(huán)境信息。供電單元主要為該節(jié)點(diǎn)提供能量，并對電源進(jìn)行管理。節(jié)點(diǎn)消耗的總能量為

（3）

式中為收發(fā)單元消耗的能量，為處理器消耗的能量，為傳感單元消耗的能量，為供電單元消耗的能量。

3 仿真實(shí)驗(yàn)與分析

本文使用MATLAB對LEACH算法和本分算法分別進(jìn)行仿真。在無線傳感器網(wǎng)絡(luò)中隨機(jī)分布100個傳感器節(jié)點(diǎn)，分布在大小在100m×100m的區(qū)域內(nèi)，如圖1所示，基站設(shè)置在坐標(biāo)為（50，50）位置。實(shí)驗(yàn)中以橫軸輪數(shù)表示時(shí)間，縱軸作為參考指標(biāo)，實(shí)驗(yàn)時(shí)間為1800輪。

圖2比較了LEACH算法和本文算法的節(jié)點(diǎn)生命周期，從圖中可以看出LEACH算法第1個死亡時(shí)間和最后一個節(jié)點(diǎn)死亡的時(shí)間分別在1000輪和1500輪，本文算法第一個節(jié)點(diǎn)和最后一個節(jié)點(diǎn)死亡的時(shí)間分別為1025輪和1780輪之后。通過數(shù)據(jù)可以看出，本文算法在延長網(wǎng)絡(luò)節(jié)點(diǎn)生命周期方面有一定提升。

圖3比較了兩種算法在能量均衡方面的的性能，網(wǎng)絡(luò)能量隨著仿真時(shí)間的增加，能量消耗的差距逐漸增大。當(dāng)仿真時(shí)間達(dá)到1500輪時(shí)，LEACH算法中的網(wǎng)絡(luò)能量基本耗盡，而本文算法的能量耗盡時(shí)間為1780輪，從圖3中可以看出，本文算法在節(jié)省網(wǎng)絡(luò)能量消耗方面有一定的提升，同時(shí)也證明了該算法在延長網(wǎng)絡(luò)方面的可行性。

4 結(jié)束語

本文針對無線傳感器網(wǎng)絡(luò)路由算法LEACH算法存在簇首

密度不均衡的問題，提出了一種改進(jìn)的備選簇首的算法。該算法在密度較大的區(qū)域選舉出剩余能量較多的節(jié)點(diǎn)作為備用簇首，當(dāng)該區(qū)域簇首完成一個周期后不再進(jìn)行下一輪的選舉，而是使用備用簇首作為下一輪的簇首，從而減少節(jié)點(diǎn)選舉輪數(shù)，均衡網(wǎng)絡(luò)能量消耗。仿真結(jié)果表明，與LEACH算法相比，該算法在延長網(wǎng)絡(luò)壽命，節(jié)省網(wǎng)絡(luò)能量方面有一定的提升。

參考文獻(xiàn)：

[1] 李建中，高宏.無線傳感器網(wǎng)絡(luò)的研究進(jìn)展[J].計(jì)算機(jī)研究與發(fā)展，2008，45（1）：1-15.

[2] 向鳳紅，孔慶平， 毛劍琳，等.基于ZigBee的低功耗無線傳感器網(wǎng)絡(luò)改進(jìn)協(xié)議[J].傳感器與微系統(tǒng)，2017，36（3）：33-35.

[3] ZHANG Jing，LIU Yanheng，ZHANG Jindong，等.無線傳感器網(wǎng)絡(luò)簇半徑自適應(yīng)調(diào)整策略[J].吉林大學(xué)學(xué)報(bào)：工學(xué)版，2016，46（3）：876-883.

[4] 沈波，張世永，鐘亦平.無線傳感器網(wǎng)絡(luò)分簇路由協(xié)議[J].軟件學(xué)報(bào)，2006，17（7）：1588-1600.

[5] Heinzelman W R，Chandrakasan A，Balakrishnan H.Energy-Efficient Communication Protocol for Wireless Microsensor Networks[C]//Hawaii International Conference on System Sciences.IEEE Computer Society，2000：8020.

[6] 胡艷華，張建軍.LEACH協(xié)議的簇頭多跳（LEACH-M）改進(jìn)算法[J].計(jì)算機(jī)工程與應(yīng)用， 2009，45（34）：107-109.

[7] 王東東，崔寶同.基于非均勻分簇多跳通信的改進(jìn)Q—Leach研究[J].計(jì)算機(jī)技術(shù)與發(fā)展，2015（2）：212-215.

[8] 王靈矯，彭志強(qiáng)，李哲濤，等.基于權(quán)重的NPCHS-Leach協(xié)議簇頭選取策略優(yōu)化研究[J].傳感技術(shù)學(xué)報(bào)，2015（12）：1846-1852.