WSN中LEACH協議的改進與研究

摘要：針對無線感測器網路LEACH（Low Energy Adaptive Clustering Hierarchy）協議中簇頭隨機選取造成網路能耗過快的問題，提出改進的LEACH-ED演算法。改進後的演算法在簇頭選取時考慮了節點剩餘能量以及到基站的距離，使剩餘能量高、距離基站近的節點優先當選為簇頭。理論分析及模擬結果表明，綜合考慮到節點剩餘能量和到基站距離的LEACH-ED演算法，相較LEACH演算法，系統整體耗能減小，網路生命周期延長60%，對於可靠性有特殊要求的應用場合具有一定的實用價值。

正文內容：

0　引　言

隨著感測器技術、嵌入式計算技術、微電子技術和無線通信技術的日趨成熟，無線感測器網路（Wireless Sensor Networks，WSN）[1]應運而生，並廣泛應用于軍事、環境參數監測與採集、智能家居、溫室大棚等領域[2]。無線感測器網路是由數量眾多、體積微小、僅電池供電的感測器節點組成，並以自組織方式互相協同工作的分散式感知網路。由於感測器節點能量有限且大多部署在電池不易更換的環境中，因此如何均衡網路能耗、最大程度延長網路生命周期成為首要問題[3]。路由協議作為延長網路生命最有效的方式之一[4]，受到國內外研究人員的廣泛關注。研究表明，層次型路由協議相比較於平面路由，解決了其建立、維護路由開銷大、信息冗餘大、數據傳輸跳數多、網路規模小的問題。而LEACH[5]協議是層次型路由協議最具代表性的。所以，後續的一系列協議都是對LEACH協議某種程度的改進[6]。

相較於一般的平面多跳路由協議和靜態分層演算法，LEACH協議可以將網路周期延長15%[7]，但尚存在不足，主要體現在：

①LEACH協議假定所有的節點都可以與匯聚節點直接通信，因此該協議無法在大規模WSN中應用[8]；

②在簇頭的競選階段沒有考慮當選為簇頭的節點可能剩餘的能量較低，大大縮短了網路的生命周期[9]；

③沒有考慮簇頭的位置，選出的簇頭可能集中在某一個區域，導致一些普通節點周圍沒有任何簇頭節點。

本文針對無線感測器網路LEACH（Low Energy Adaptive Clustering Hierarchy）演算法中簇頭隨機選取造成網路能耗過快、網路生命周期變短的問題，提出一種基於節點剩餘能量和距離基站距離[10]的簇頭選取演算法（LEACH-ED）。實驗驗證結果表明，綜合考慮節點剩餘能量和到基站距離的LEACH-ED演算法，相比較於基本的LEACH演算法，系統的整體耗能減小，網路生命周期延長60%，且網路的擴展性能更好。

1　LEACH協議概述

LEACH是最早提出的分簇路由協議，奠定了分簇路由協議的基本思想。在運行過程中，它不斷執行簇的重構過程。重構過程以「輪」為單位[11]，分為兩個階段：簇的建立階段和數據傳輸的穩定階段。為了節省網路開銷，穩定階段的持續時間要大於建立階段持續的時間。簇的建立階段主要包括簇頭節點的選擇、簇頭節點的廣播、簇頭節點的建立和調度機制的生成；數據傳輸穩定階段主要負責數據的融合和傳輸。在所有數據傳輸完成後，新的一輪開始，網路需要重新選擇簇頭。

1.1　簇形成過程

1.1.1　簇頭的選擇

每一個感測器節點產生一個（0，1）之間的隨機數，然後與式（1）生成的閾值T（n） 進行比較。如果節點產生的隨機數小於T（n） ，則此節點可能當選為簇頭。如果最終當選簇頭，則將當選為簇頭的消息廣播告知網路其他節點。

式中，p 為簇首的比例，r 表示網路當前運行的輪數，G 表示在最後的1/p 輪中還沒有成為簇首節點的集合。在r=0 時，每個節點都以P 的概率成為簇頭，經過1/p-1 輪後閾值變為1。

1.1.2　簇的建立

簇頭選舉過程完成後，成為簇頭的節點廣播自己成為簇頭的消息到整個網路。該消息主要包括簇頭的ID、位置等。普通節點根據接收到消息的強弱選擇強度最大的簇，並向對應的簇頭返回消息，確保加入距離自身最近的簇頭。簇頭根據簇內包括的節點個數，採用TDMA方式為簇中每個節點分配向其傳輸數據的時間點。

在數據傳輸穩定階段，簇內節點根據簇頭分配的數據傳輸時間點，定時喚醒。此時，向簇頭傳輸數據，其餘時間處於休眠狀態，以便降低耗能。整個過程中，簇頭始終處於開啟狀態，以接收本簇成員的數據。將本簇成員數據和自身採集的數據融合後，簇頭採用載波偵聽同步CSMA的方式，將融合後的數據發送到匯聚節點，避免了簇頭同時向匯聚節點發送數據時的阻塞現象。所有簇首完成數據傳送後，新的一輪開始，網路重新進入簇建立階段。

1.2　網路能耗模型

LEACH演算法的能耗模型定義為：

ETx 是發送k 比特數據、傳輸距離d 的能耗，ERx 則是接收k 比特數據的能耗，Eelec 是收發1 bit數據電路消耗的能量，表示自由空間放大器傳播損耗，表示多徑衰減放大器傳輸損耗，d0 為常數且

。

2　LEACH協議改進演算法

2.1　改進演算法網路模型

改進後的演算法採用的無線通信模型與LEACH協議一致，感測器節點隨機分布在已知區域內，普通感測節點能夠感知、採集數據並發送給簇頭節點，簇頭節點融合、整理後發送給匯聚節點。在設計演算法時，同時做以下假設：

①感測器節點初始能量相同且有限；

②感測器節點和匯聚節點位置確定後，在剩餘網路周期內不再移動；

③節點在發送能量時，能夠自動調整發射功率以節省能量；

④匯聚節點位於已知區域外。

2.2　改進演算法描述

LEACH-ED基於LEACH協議，考慮加入剩餘能量和到匯聚節點的距離因素後提出的新演算法，其中新演算法在簇的建立、穩定數據傳輸階段與最基本的LEACH演算法相同，最主要的區別體現在簇頭選擇和更新過程。思想如下：首先計算基於存活節點數的最佳簇頭個數，假設在當前網路中有Nr 個節點存活且隨機分布在MxM 的區域內，這塊區域被平分為K 個簇，此時每個簇中含有的節點個數為Nr/K （包含一個簇頭節點和Nr/K-1 個普通節點），則最佳簇頭的個數就等於所分成的簇數。根據節點的能耗模型，簇頭傳輸l bit的數據所消耗的能量為：

每一個簇成員節點消耗的能量為：

則每一個簇收發l bit的數據時所消耗的最大能耗是：

一幀中，所有的Nr 個節點消耗的總能量為：

設sink節點的坐標為(x0,y0) ，當前節點的坐標為(xi,yi) ，則當前節點到sink節點的距離為：

每個簇所佔據的面積約為，假設是一個簇頭節點位於簇的中間且密度為的任意形狀的區域。根據節點的通信半徑，則普通節點到簇頭節點的距離為：

對式（9）進行極坐標變換。令、，其中，代入得：

將式（8）、式（10）代入式（6），然後再代入式（7），可得整個網路的總能耗為：

要使整個網路的能耗最低，將Etotal 對K 求導並讓其等於零，可得到理想的簇頭數：

改進後的演算法將某一節點的剩餘能量與網路平均能量的比值作為考慮因素，使剩餘能量最大的節點能夠優先競選選為簇頭。選用當前節點到sink節點距離與所有活著的節點到sink節點較近的節點優先被選舉為簇頭。改進後的T(n) 為：

其中且，同時有：

通過綜合考慮節點的剩餘能量與網路的平均能量的比值、到節點到匯聚節點的距離與節點的匯聚節點的距離的比值，可以使剩餘能量大、距離匯聚節點近的節點優先競選成為簇頭，從而使網路的能耗更加均衡，延長網路的生命周期。

3　模擬分析

為了驗證LEACH-ED演算法性能是否高於LEACH演算法，選擇MATLAB平台，在100 m×100 m的網路區域內隨機分布100個節點進行模擬。分別從網路節點存活數、死亡數、數據包接收數等方面，對改進後的演算法性能進行評價，參數設置見表1。

在一定的環境下，LEACH-ED演算法隨著運行輪數的增加，網路中死亡節點數目與存活節點數目的變化如圖1、圖2所示。其中，LEACH演算法在2 000輪時出現了大面積死亡，而LEACH-ED演算法大面積死亡的時間是3 200輪；在網路生命周期上，LEACH-ED演算法比LEACH延長了60%。LEACH存活的數目在2 100輪全部死亡，而LEACH-ED存活的時間達到了4 100輪。所以，改進演算法提高了節點的存活率，延長了網路壽命。

圖3為基站收到的數據包數與工作輪數的關係變化曲線。可以看出，相比LEACH演算法，改進後的LEACH—ED演算法在相同的輪數下接收的數據包數大大提升，提高了網路的工作效率。

圖4為簇頭數與工作輪數的關係變化曲線。從圖4可以看出，在相同的輪數下，改進的演算法簇頭數更多，簇頭分布更加均勻，均衡了網路能耗。

圖5為不同LEACH協議的網路能耗測試結果。從圖5可知，隨著輪數不斷增加，兩種LEACH協議的網路總能耗逐漸增加；但對於LEACH協議，LEACH-ED協議的能耗增加更為緩慢，節能效果明顯。

4　結　語

本文對無線感測器分簇路由演算法LEACH進行改進，提出了改進後的路由協議——LEACH-ED。在簇頭競爭階段，LEACH-ED對影響簇頭選舉的閾值進行改進，改進後的閾值綜合考慮了節點的剩餘能量、到基站的距離，使改進後的簇頭選舉更加合理，簇頭分布更加均勻，有效減少了簇頭選舉能耗。模擬結果表明，相比較於LEACH協議，LEACH-ED有效均衡了網路的能量負載，使節點的存活率更高，延長了網路的生命周期。

參考文獻：

[1] 趙麗霞,紀松波.無線感測器網路在智能交通中的應用[J].物聯網技術,2012,2(06):25-27.

[2] 孫利民,李建中,陳渝等.無線感測器網路[M].北京:清華出版社,2005:1-25.

[3] KATIYAR V,CHAND N,GAUTAM,et al.Improvement in LEACH Protocol for Large-scale Wireless Sensor Networks[C].Proceeding of the 2011 Emerging Trends in Electrical and Computer Technology Piscataway,2011:1070-1075.

[4] 石為人,柏盪,高鵬等.無線感測器網路簇頭半徑自適應調節路由演算法[J].儀器儀錶報,2012(02):1779-1785.

[5] 王臻躍.基於LEACH的改進路由演算法[J].軟體導刊,2015(03):114-116.

WANG Zhen-yue.Improved Routing Algorithm based on LEACH[J].Software Guide,2015(03):114-116.

[6] 吳標,余劍.基於節點剩餘能量的分時分簇LEACH改進演算法[J].火力與指揮控制,2016(10):84-88,93.

[7] Nayebi A,Sarbazi-Azad H.Performance Modeling of the LEACH Protocol for Mobile Wireless Sensor Networks[J].J. Parallel Distrib. Comput.,2011(02):4.

[8] Heinzelman W R.Energy-Efficient Communication Protocol for Wireless Microsensor Networks[C].Proceedings of the 33rd Ha-waii International Conference On System Sciences,IEEE Computer Society,2000.

[9] 潘霞,於宏毅,張霞.一種基於LEACH的能耗均衡分簇演算法[J].電路與系統學報,2012,17(01):75-80.

[10]李建坡,鍾鑫鑫,徐純.無線感測器網路動態節點定位演算法綜述[J].東北電力大學學報,2015(35):52-58.

[11]過文亮,施惠昌.一種新型的自適應最佳簇首分簇演算法[J].微計算機信息,2009,25(02):183-184.

作者：張　浩，趙建平

單位：曲阜師範大學 物理工程學院，山東 曲阜 273165

作者簡介：張　浩，男，碩士，主要研究方向為無線感測器網路、無線通信技術；

趙建平，男，學士，教授，主要研究方向為無線通信技術。

本文刊登在《通信技術》2018年第2期（轉載請註明出處，否則禁止轉載）

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！