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

鄭安達

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

關鍵詞：無線傳感器網絡；LEACH算法；備用簇首；簇首選舉；網絡壽命

中圖分類號：TP393 文獻標識碼：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

無線傳感器網絡（Wireless Sensor Network，WSN）是一種綜合了傳感器技術、無線通信技術、嵌入式、計算機技術等先進技術的網絡結構[1]，通常用于環境監測、軍事領域、醫療護理、航空航天等領域。由于無線傳感器網絡節點體積小，通常被部署于環境復雜的地點，不容易更換電池，因此如何降低網絡的能量消耗成為國內外科研機構和學者研究的熱點[2-3]。

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

本文提出了一種改進的LEACH算法，本文算法通過引入簇首密度，選舉備用簇首的方式以平衡簇首選舉，達到均衡網絡能量消耗和延長網絡壽命的目的。

1 LEACH算法

LEACH算法核心思想是引入輪的概念，通過循環方式進行周期性選舉簇首，選舉分為兩個過程，第一個過程為簇首的選舉過程，第二個過程為數據傳輸過程，當這兩個過程完成后作為一個周期的完成。一個周期完成后網絡進入下一輪循環，網絡通過這種周期循環來選舉簇首，平衡網絡的能量消耗。

在簇首選舉過程，網絡中的節點隨機生成一個0到1的數，通過隨機數與閾值比較來判斷本輪是否成為簇首，如果該節點生成的隨機數小于閾值，則該節點被選為簇首。閾值為：

（1）

式中為簇首百分比，為目前進行的輪數，為最后輪中沒有被選為簇首的節點集合。沒有被選中的的節點根據簇首的廣播信號強度大小決定加入的簇，并發送入簇請求。簇首收到入簇請求后建立路由列表，并將路由列表發送給列表中的節點。

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

2 LEACH算法的改進

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

2.1 簇首選舉

為保證網絡簇首選舉合理分配，在簇首選舉過程中，網絡中的節點首先根據式（1）選舉簇首，節點通過隨機產生0到1之間的數字與閾值比較，如果小于閾值，則被選為簇首。簇首選舉完成后對自身轉發范圍內的簇首密度進行密度計算。計算式為：

（2）

式中為轉發范圍內節點的總數，為簇首轉發范圍內簇首總數，當簇首密度且時，本文算法認為簇首密度過大，對簇首進行均衡，從多余簇首中選舉備用簇首。

在選舉備用簇首時，源簇首首先向轉發范圍內的鄰居簇首發送請求，鄰居簇首收到請求反饋本簇首的剩余能量信息，源簇首在收到剩余能量后對能量大小進行對比，并將能量較大的簇首選為備用簇首，將備用簇首的信息發送給路由列表內的所有節點和簇首。當本周期結束后，該區域不再進行簇首選舉，此時備用簇首開始工作并作為下一周期簇首。

2.2 數據傳輸

網絡數據傳輸過程與LEACH算法數據傳輸過程類似，簇內節點通過TDMA時間列表向簇首發送數據。簇首在向基站發送數據之前先偵聽信道，當信道空閑時，該簇首開始發送數據，否則該簇首等待并繼續偵聽，直到偵聽到信道空閑，如此重復該過程。數據傳輸階段完成數據的采集和傳送，簇頭完成對節點數據的接收、數據的融合并通過簇首之間的數據傳送轉發給基站。

2.3 能量模型

傳感器節點主要由收發器、處理器、傳感單元、供電單元等四個部分組成，傳感器節點的能量消耗主要集中在該四個組成部分。收發器用來進行節點之間或者節點與基站之間的通信，是數據傳輸的主要部分，處理器用于節點的管理、數據的融合和處理等功能，傳感單元用于獲取周圍環境信息。供電單元主要為該節點提供能量，并對電源進行管理。節點消耗的總能量為

（3）

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

3 仿真實驗與分析

本文使用MATLAB對LEACH算法和本分算法分別進行仿真。在無線傳感器網絡中隨機分布100個傳感器節點，分布在大小在100m×100m的區域內，如圖1所示，基站設置在坐標為（50，50）位置。實驗中以橫軸輪數表示時間，縱軸作為參考指標，實驗時間為1800輪。

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

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

4 結束語

本文針對無線傳感器網絡路由算法LEACH算法存在簇首

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

參考文獻：

[1] 李建中，高宏.無線傳感器網絡的研究進展[J].計算機研究與發展，2008，45（1）：1-15.

[2] 向鳳紅，孔慶平， 毛劍琳，等.基于ZigBee的低功耗無線傳感器網絡改進協議[J].傳感器與微系統，2017，36（3）：33-35.

[3] ZHANG Jing，LIU Yanheng，ZHANG Jindong，等.無線傳感器網絡簇半徑自適應調整策略[J].吉林大學學報：工學版，2016，46（3）：876-883.

[4] 沈波，張世永，鐘亦平.無線傳感器網絡分簇路由協議[J].軟件學報，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協議的簇頭多跳（LEACH-M）改進算法[J].計算機工程與應用， 2009，45（34）：107-109.

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

[8] 王靈矯，彭志強，李哲濤，等.基于權重的NPCHS-Leach協議簇頭選取策略優化研究[J].傳感技術學報，2015（12）：1846-1852.