面向新疆平原灌區的LEACH路由算法研究

池濤,汪磊

面向新疆平原灌區的LEACH路由算法研究

池濤,汪磊*

上海海洋大學信息學院, 上海 201306

已研究的無線傳感器網絡系統多使用于溫室大棚、中部平原等環境中，并采用LEACH路由算法均衡網絡能量，以達到延長網絡壽命的目的；這些網絡中節點與節點之間的距離較近、面積規模較小、每個節點能量相對充足，因此在使用LEACH路由算法時不容易出現因選取簇頭不當、節點能耗過快而產生網絡空洞等問題；但在新疆平原灌區中進行無線布網時，因硬件成本有限、地理環境復雜等各種因素的限制，導致部署出來的無線傳感器網絡是一種典型的Zig Bee廣域網，該網絡中節點與節點間距離較遠，不同節點之間傳輸信息時能量消耗過大，因此當網絡中選舉不當節點作為簇頭時會因該節點能量消耗過快而產生節點失效的問題，產生網絡空洞現象；本文針對這種現象，在面向新疆平原灌區網絡這一限制區域中，聯合節點距離、密度及剩余能量提出了一種的改進型LEACH算法，該算法針對傳統LEACH算法在隨機選取簇頭過程中的缺點，在簇頭選取過程中，首先將網絡按照終端節點與基站之間的距離等級劃分為多個區域，使得距離基站越近的節點成為簇頭的概率越大，然后通過各個區域中節點密度和剩余能量因素將適合的節點選舉為簇頭，提高網絡利用率，解決網絡空洞問題，延長網絡生命周期。采用Matlab軟件對改進算法進行仿真，實驗結果表明在節點稀疏的網絡中改進后的LEACH算法比傳統LEACH算法的網絡壽命提升了16%，且可以滿足新疆平原灌區中廣域網絡要求，減少了網絡空洞問題的產生。

LEACH路由算法; 簇頭; 廣域網; 網絡空洞

新疆是我國農業種植密集區域，因地理環境復雜，基礎網絡條件設施不全等因素的限制，直接影響了新疆農業經濟的發展。隨著近幾年無線傳感器網絡技術的發展，如何在西部農業灌區網絡中設計一套合適的低功耗路由算法已經成為當今社會的一大研究熱點。

自2000年LEACH算法被設計出來以來[1]，基于均衡無線傳感器網絡中能量消耗，延長網絡壽命的目的，國內外研究人員設計了多套改進型LEACH算法[2-7]。Heinzelman WR等人提出了一種基于簇的LEACH協議，利用簇內隨機旋轉選取簇頭來均衡網絡中能量負載，仿真結果表明，LEACH協議與傳統路由協議相比降低了能耗，網絡生命周期得到了延長[1]。Ahlawat A，Malik V等人在分析LEACH路由協議的基礎上提出了一種改進型路由協議V-LEACH，基于最小距離、最小能量和最大剩余能量等因素在每個網絡簇中選舉一個副簇頭，用于當簇頭因能量耗盡而死亡后進行取代的作用。仿真結果表明V-LEACH路由協議有效延長了網絡壽命[2]。李年瓊等人針對LEACH路由算法隨機選取簇頭節點的弊端，提出了一種基于剩余能量和位置的改進型LEACH算法，該算法將傳感器節點的節點剩余能量和幾何平均位置作為選簇的重要因素，在此基礎上選最佳簇頭[3]。顧明霞等人針對節點剩余能量的狀態，使能量高的節點盡量成為簇頭，在數據傳輸階段采用單跳和多跳結合的混合通信方式均衡簇頭和基站能量消耗[4]，仿真結果表明改進后的E_LEACH算法相比于LEACH路由算法更能均衡網絡能量。葉繼華針對在多種類型數據同時采集的異構網絡，提出一種改進型可變通周期性策略的能量均衡協議，將數據通信周期和數據采集周期分離，采用可變通周期策略來減少網絡中簇頭節點的消耗，達到平衡網絡能量的功能[5]。蔣建明等人在針對水產養殖無線傳感網絡中測量節點能耗過快、個別節點過早失效導致網絡壽命縮短等問題，聯合節點距離基站位置及剩余能量因素選取合適的簇頭節點提出了一種改進型的LEACH-C算法，該算法在LEACH算法的基礎上將生命周期延長了8%[6]。但是當前改進的LEACH路由算法多是使用于小面積的、網絡節點分布密度較大的小型網絡中，對于西部這種節點稀疏的大型廣域網絡并不適用。

文章針對西部農業灌區這一應用場景，在農業灌區中隨機網絡布點，采用Zig Bee和北斗相結合的方案，設計了一套基于Zig Bee技術和北斗點位技術相結合的無線傳感器網絡監測系統。針對隨機簇頭選舉過程中導致節點能量消耗過快從而導致節點失效引起的網絡空洞等問題，在傳統的LEACH算法的基礎上，結合網絡中節點位置、網絡簇中所有節點密度等因數，提出了一種改進型LEACH路由算法，提高了網絡能量有效性，延長網絡壽命。實驗證明該算法適用于大多數節點密度較低、錨節點分布稀疏的新疆農業灌區網絡中。

1 新疆廣域網絡分析

圖 1 新疆廣域網絡

如圖1所示，新疆農業灌區網絡通過Zig Bee自組織網絡將監測區域分為若干簇，網絡中節點主要分為普通節點、簇頭節點和基站；普通傳感器節點用于收集周圍參數信息，簇頭節點用于接受傳自普通節點中的信息，將簇頭節點的信息傳遞給基站，最后基站將所有的信息匯總傳遞給所需的終端;本網絡模型中，網絡節點滿足以下條件[8-10]：

1）網絡中所有節點的構造和初始能量相同，節點能量在網絡工作的過程中是不能補充的；

2）網絡中所有節點的通信半徑R是一致且已知的，且發射功率可控；

3）網絡中所有節點有唯一標識；

4）網絡中節點的位置已經通過少量的帶有北斗模塊的節點監測出來；

5）網絡中的基站能量不需要我們考慮。

與常見無線傳感器網絡的不同在于新疆農業灌區網路面積更大，且網絡中節點數目更少，導致網絡節點密度遠遠低于常規網絡，一些常規的路由算法（例如LEACH路由算法）在這種廣域網中并不能適用[11-13]。

1.1 LEACH協議分析

LEACH協議是一種基于分簇的低功耗自適應路由協議，是層次型路由協議的典型代表。該算法的核心思想：將整個網絡分為多個簇，并引入”輪”的概念，每輪可以分為粗的建立和穩定的數據傳輸階段，每次循環以隨機的方式選取簇頭節點，簇中其余節點收集附近的信息，并將信息匯集到簇頭，由簇頭將簇中所有信息進行融合傳遞給基站。簇頭融合傳遞本簇中所有信息，因此能量消耗消耗比其余節點快，該協議在每輪中將不同的節點輪轉為簇頭，這種輪轉將網絡中能量消耗均衡到每個節點，達到降低網絡能量消耗，延長網絡壽命的目的。讓網絡中節點完成輪轉，實現每個節點成為簇頭完成信息融合傳遞是該協議的重要核心所在。

圖2顯示了LEACH算法的運作過程。

圖 2 LEACH算法運行過程

在建立階段采用隨機自治的方式選取簇頭，簇頭的選取是獨立的、自治的，每個節點都有相同的概率成為簇頭。在選取過程中，每個節點產生0~1之間的隨機數，如果這個隨機數大于閾值()，則此節點為普通節點，反之，則設置為簇頭節點，簇頭節點產生后向網絡中其余節點進行廣播，普通節點接受到簇頭信息后，加入距離較近的簇頭組成的簇中；在每輪中，只要該節點擔任過簇頭，則把()設置成0，在以后的輪中不再擔任簇頭。()的公式如（1）所下：

礦體主要分布于花崗閃長斑巖侵入體與香夼組灰巖接觸帶上，共探明64個礦體，礦體呈脈狀、透鏡狀、似層狀、囊狀，主礦體向下700m仍為封閉[12]。礦化具有明顯的分帶現象，垂向上由淺部向深部，平面上由外部向內部，依次為矽卡巖鉛鋅礦帶、矽卡巖-斑巖銅硫礦帶、斑巖銅鉬礦帶。礦石主要包括矽卡巖型和絹英巖化斑巖型兩類，礦石主要呈浸染狀、細脈浸染狀、塊狀及條帶狀構造。圍巖蝕變自巖體內部向外圍蝕變類型依次為：硅化、絹云母化、鉀化→矽卡巖化→綠泥石化、綠簾石化、絹云母化、碳酸鹽化等。

：簇頭在所有節點中的比例；：選取的輪數；rmod(1/)：表示這一輪中當選為簇頭的節點的個數；：這一輪中未當選為簇頭節點的集合。

在穩定的數據通信階段，簇內其余節點將采集到的數據發送給簇頭，簇頭把其余非簇頭節點的信息融合后發送給基站，在這一過程中簇頭需要消耗大量的能量，經過一段的數據傳送后，節點進行下一輪的工作。

通過周期性隨機選取簇頭和網絡重組將網絡中消耗的能量均衡到每一個節點中達到延長網絡壽命的目的，提高網絡生存的總體時間，避免簇頭節點因消耗過快而產生網絡壽命提前結束的問題。但是LEACH算法仍然存在不足：①LEACH算法中隨機選取簇頭節點的方式會造成簇分布不合理現象，增加了某些簇頭節點的負擔，導致某些離基站較遠的簇過早因能量消耗過快導致網絡空洞等問題；②LEACH算法中每個簇內節點分布不均，增加了某些簇頭節點的能量消耗，降低網絡負載平衡。

2 LEACH路由算法的改進

在新疆平原灌區網絡中因節點隨機分布，導致傳統LEACH算法選舉出來的簇頭節點并不能最好地發揮整個網絡的功能，當某些偏遠節點當選為簇頭時容易使網絡產生網絡空洞[14,15]。改進后的LEACH路由算法節能核心思想是：對網絡中節點距離基站的位置進行劃分，增加距離基站較近位置的節點成為簇頭的概率，然后通過網絡簇中節點密度及剩余能量因子選取合適簇頭節點，則簇頭將普通節點傳遞額信息進行融合后傳遞給基站時消耗能量比遠距離簇頭傳遞信息所消耗的能量要少，使選舉出的簇頭節點能延長網絡壽命，更適用與新疆平原灌區中。改進型LEACH路由算法的簇頭選取階段優化主要分為兩步：①通過網絡節點區域劃分；②區域節點密度、能量劃分。

2.1 簇頭節點優化選舉

2.1.1 網絡節點區域劃分由于LEACH算法中對簇頭的選取是隨機的，導致簇頭集中分布不合理。本算法通過節點距離基站位置將整個網絡劃分為8個區域，如圖3所示。

圖 3 網絡區域劃分

在每個區域中固定簇頭的比例，其中區域1中代表基站，不需要設置簇頭，其余區域中簇頭按以下步驟：

1）區域理想簇頭比例：

2）每個區域中節點的數目：Q

3）區域中簇頭節點的比例：

*=C/Q(3)

采用區域節點分區的方法對節點成為簇頭的概率進行了初步劃分，對每個區域的簇頭比例進行了嚴格控制，防止了簇頭分布嚴重不均勻的問題，這樣避免了不合理簇頭的產生。

2.1.2 區域節點密度、能量劃分通過網絡節點分區的方法劃分了不同區域內簇頭節點的比例，解決了簇頭分布不合理的問題，再結合每個區域中節點能量及密度值，解決簇內節點分布不均勻、剩余能量較少的問題。

1)設置剩余能量限制條件

每個區域中節點參與簇頭的選舉時剩余能量e需要滿足以下條件：

avr：整塊網絡區域中存活節點的平均能量；：每塊區域中存活節點的數目。

表示區域中每個存活的節點只有在剩余能量大于avr的時候才能有條件當選為該簇的簇頭節點。避免了在傳統LEACH算法中能量過少的節點成為簇頭，加快節點死亡的突出問題。

2)設置節點密度限制條件

注：*為（3）中*;

算法工作流程如圖4所示。

圖4 改進算法流程圖

通過*()可知，普通節點對最近簇頭和基站位置進行比較，判斷將信息直接傳遞給基站還是簇頭；當離基站距離越近的區域內簇頭節點的比例越高，節點的周圍節點數目越多時，節點成為簇頭的概率得到提升，反之則成為簇頭節點的概率越低。該改進后的LEACH算法有效解決了西部平原灌區網絡中簇內節點分布不均勻、簇頭節點分布不均和網絡空洞的問題，能有效使用于西部農業中。

3 仿真及結果分析

為了評價改進后LEACH算法的性能，利用MATLAB工具對本文的改進型LEACH算法和傳統LEACH算法進行比較。選取面積為400 m*400 m大小區域，在該區域內隨機布置N個節點，基站坐標為（0 m,0 m），簇頭的比例占整個網絡節點的10%，每個節點的傳感半徑為40 m，節點初始能量為0=0.5 J，自由空間信道模型的能耗參數?=10 PJ/bit/m2,多路信道衰減信道模型參數?=0.0013 PJ（bit*m4，最大循環次數rmax=500。

仿真實驗中以不同節點密度下LEACH算法和改進后LEACH算法中節點存活時間為指標評判算法對整體網絡性能的影響。

圖 5 節點存活率比較圖（50個節點）

圖 6 節點存活率比較圖(100個節點)

圖 7 節點存活率比較圖（150個節點）

如圖5、6、7所示，分別為50個節點、100個節點、150個節點在400 m*400 m的區域中節點死亡率，每圖左邊為LEACH算法，右圖為改進后的LEACH算法，一般情況下，整體網絡中80%節點死亡后，說明該網絡已經死亡；實驗結果證明，在節點密度為0.0003個/m2的網絡中改進后LEACH算法比傳統LEACH算法存活率提高了16%；在節點密度為0.0006個/m2的網絡中改進后LEACH算法比傳統LEACH算法存活率提高了19%；在節點密度為0.0003個/m2的網絡中改進后LEACH算法比傳統LEACH算法存活率提高了24%；因此在節點稀疏的新疆平原區域可以使用改進后的LEACH算法，以達到延長網絡壽命，減少網絡空洞的作用。

4 結語

路由算法的研究對無線傳感器網絡在新疆平原區域中的應用有著重要的意義，它的性能直接影響著在實際應用中的實用性。本文在常規的LEACH路由算法的基礎上，采用新型的簇頭選舉策略來保證整體網絡中節點能量均衡，進一步延長了網絡壽命。實驗表明，改進型的LEACH路由算法在實際中延長了網絡整體壽命，在一定程度上避免了網絡空洞的產生。

[1] Heinzelman WR, Chandrakasan A, Balakrishnan H. Energy-efficient communication protocol for wireless sensor networks[C]// Hawaii International Conference on System Sciences, IEEE Computer Society, 2000:8020

[2] Ahlawat A, Malik V. An Extended Vice-Cluster Selection Approach to Improve V Leach Protocol in WSN[C]// Third International Conference on Advanced Computing & Communication Technologies, IEEE Computer Society, 2013:236-240

[3] 李年瓊,黃宏光,李鵬.基于剩余能量和位置的LEACH改進算法[J].計算機工程,2012,38(24):70-73,77

[4] 顧明霞.一種新的基于LEACH的WSN路由算法[J].計算機仿真,2011,28(8):129-133

[5] 葉繼華,王文,江愛文.一種基于LEACH的異構WSN能量均衡成簇協議[J].傳感技術學報,2015,28(12):1853-1860

[6] 蔣建明,史國棟,李正明,等.基于無線傳感器網絡的節能型水產養殖自動監控系統[J].農業工程學報,2013,29(13):166-174

[7] 葉繼華,王文,江愛文.一種基于LEACH的異構WSN能量均衡成簇協議[J].傳感技術學報,2015(12):1853-1860

[8] 周潔,石志東,張震,等.WSN中一種基于LEACH協議的改進算法[J].上海大學學報:自然科學版,2013,19(2):116-119

[9] 馬建樂,楊軍.基于位置和剩余能量的局部集中式LEACH算法研究[J].傳感技術學報,2013(8):1147-1151

[10] 廖明華,張華,王東.基于LEACH協議的簇頭選舉改進算法[J].計算機工程,2011,37(7):112-114

[11] 嚴斌亨,陳任秋,劉軍.能量優化的無線傳感器網絡LEACH算法[J].傳感器與微系統,2016,35(7):120-122

[12] 譚軍.簇首選擇改進的LEACH無線傳感器路由協議[J].計算機應用與軟件,2015(6):171-173

[13] Ran G, Zhang HZ, Gong SL. Improving on LEACH Protocol of Wireless Sensor Networks Using Fuzzy Logic[J]. Journal of Information & Computational Science, 2010,7(3):767-775

[14] Godbole V. FCA-An Approach On LEACH Protocol Of Wireless Sensor Networks Using Fuzzy Logic[J]. International Journal of Computer Communications and Networks(IJCCN), 2013,2(3):1-13

[15] Banimelhem O, Taqieddin E, Awad F,. Fuzzy Logic-Based Cluster Heads Percentage Calculation for Improving the Performance of the LEACH Protocol[J]. International Journal of Fuzzy System Applications, 2015,4(4):100-118

Study on LEACH Routing Algorithm for Xinjiang Plain Irrigation Area

CHI Tao, WANG Lei*

201306,

With the wide use of wireless sensor networks in agricultural areas, the LEACH routing algorithm is often used to balance the energy of the network in the agricultural region,to achieve the purpose of prolonging network life;In these networks, the distance between the node and the node is very close, the network area is very small and the energy of each node is relatively sufficient, therefore, it is not easy to generate the network hole problem caused by the irrational network holes caused by randomly selected cluster heads when using the LEACH routing algorithm; but the wireless distribution network in Xinjiang plain irrigation area, various factors such as hardware cost and special geographic environment are considered. So that the deployed wireless sensor network is a typical ZigBee wide area network. In this network, the distance between nodes is far from the nodes, therefore, cluster heads can't be randomly selected in the network. If the improper nodes are selected as cluster heads, the energy consumption of nodes will be too fast, resulting in node failure and network cavitation. In view of this phenomenon, this paper proposes an improved LEACH algorithm based on node distance and node density, the algorithm for the traditional LEACH algorithm in randomly selected cluster head in the process of the shortcomings in the cluster head selection process, considering the residual energy of node and the network node location and node density, as far as possible to select higher residual energy in a network node density is high in the area from the base station node distance as the cluster head to Improve network utilization, solve the problem of network hole and prolong the life cycle of network.

LEACH routing algorithm; cluster head;wide area network; network cavity

TP302.1

A

1000-2324(2019)04-0675-06

2018-05-07

2018-08-12

國家自然科學基金(61561027);上海市自然科學基金(16ZR1415100)

池濤(1976-),博士/博士后,副教授,研究方向為嵌入式系統及農業物聯網. E-mail:tchi@shou.edu.cn

Author for correspondence. E-mail:907861285@qq.com