無線傳感器網絡LEACH協議的研究改進

劉闖，陳桂芬，馬威風

（長春理工大學 電子信息工程學院，長春 130022）

無線傳感器網絡（Wireless Sensor Network，WSN）是一個整體。WSN（無線傳感器）主要工作方式：在需要監測區域安放大量的傳感器節點，傳感器節點能夠自動采集所需要信息，傳感器網絡根據采集到信息做出決策，最終為用戶提供服務。無線傳感器網絡是一種新的數據獲取的方式，因此對于傳感器的研究備受矚目［1］。但由于WSN節點成本較高，能量受限后難以后期維護，因此WSN路由協議的一個重要目的就是高效地使用節點能量，最大限度延長網絡的生存時間［2，3］。

分簇具有降低網絡能耗，拓撲管理非常方便，能量利用率高等點。除以上優點之外，其在數據融合方面也有巨大優勢［4］。LEACH［5］首先提出基于多簇結構，部分基于分簇路由算法，例如LEACH-C［6］、EEE-LEACH［7］、EMODLEACH［8］等 都 是 借 鑒LEACH分簇思想發展而來的。簇頭的隨機選擇雖然具有易實現、操作性靈活等優點，但無法合理地確定簇頭數目和區域的分布，這樣會導致節點能量消耗不均衡，造成整個網絡性能變差。研究表明，多跳在數據轉發過程中更有利于能量的節約。HEED［9］協議在簇頭和BS之間采用多跳的通信方式能更好地節約能量，但容易導致靠近BS的簇頭由于需要轉發消息到其他簇而消耗更多能量，致整個網絡中的各個區域之間能量的不平衡。對于其存在的問題，EEUC［10］算法使用非均勻分簇的方法成簇，根據距離這一變量劃分簇，網絡被劃分為不同的簇，離BS近的簇的規模小，簇頭收到成員節點數據后選擇剩余能量多且距離自己最近的簇頭多跳傳輸數據，能夠平衡整個網絡的能量消耗，延長網絡使用時間。簇的規模不同，簇間的成員節點數也有所差別，在數據傳輸階段離BS較近的簇頭，在單位時間內向BS發送數據次數較多，導致全網節點數據難以同步。

綜合考慮上述問題。對于算法改進基本思想：一是在簇頭選舉時考慮節點上一輪的能量消耗和到節點到BS的距離；二在形成簇時，節點選擇考慮了簇頭規模、能量、簇頭與BS距離，構建大小不同規模的簇來均衡區域間的能耗，同時為了解決非均勻分簇簇規模大小不一存在的步調不一致問題，采用不定長幀的結構方式，簇的成員較少的簇的幀時間間隔較大，簇的成員較多的簇的幀時間間隔較小，以此來保證單位時間內不同簇的節點傳輸的數據次數相同；三是當簇頭間距離大于設定值時，簇的內部選擇中繼節點協助傳輸數據，數據通過中繼節點和相鄰簇頭多跳傳輸到BS，進一步延長了網絡的生存時間。

1 相關模型

1.1 網絡模型

研究整個網絡分布在一個正方形區域內，隨機分布N傳感器節點，可以周期性的收集區域內數據，假設：①BS檢測區域外圍，傳感器節點和BS在安放后均不再發生位置移動；②全部節點同構并且能量有限，可以獲得本身的剩余能量，每個標識ID對應一個節點；③全部節點都能夠一跳到達BS，BS能夠與全部節點通信；④數據融合能夠減少數據量傳輸，簇頭融合單位數據消耗的能量相同；⑤節點可以通過接收到的信號強度RSSI計算信號發出者到自己的距離，同時節點不具有位置感知能力；⑥忽略外界因素對通信質量的影響，節點能夠可靠地進行周期性數據采集任務并始終有數據傳輸到BS。

1.2 能量模型

采用文獻［6］中的無線通信能耗模型，節點發送kbit的數據包到達距離為d的另一個節點，無線信號收發部分和功率放大部分是主要的能量消耗部分。其中，功率放大器的能量消耗與傳輸環境和距離密不可分，其可由自由空間和多徑傳輸兩種模式組成。發射機傳輸k比特數據所消耗能量計算公式如下式（1）所示：

其中，Eelec為能量消耗，d0為傳輸距離常數。當傳輸距離d＜d0，則采用自由空間衰落模型εfsd2；若傳輸距離d≥d0，則采用多徑衰落模型εmpd4。式（1）中的 d0=，εfs和εmp分別為射頻參數，其值中功率放大器決定。接收器件消耗的能量如式（2）：

2 LEACH-LOMUC協議

提出的LEACH-LOMUC協議采用“輪”循環工作方式，主要由簇頭選擇、簇的形成、簇間多跳路徑的構建三部分組成。準備階段中，BS向全網廣播初始化消息（包含最優數目mopt和最優通信半徑ropt），節點根據信號強度估算與BS的距離ditoBS。簇的形成階段產生不同規模的簇，由分簇結果建立簇頭間的多跳路徑，最后網絡便進入穩定的數據傳輸階段。圖1是協議的基本原理圖，簇頭與下一跳簇頭距離大于傳輸距離閾值d0時，選擇中繼節點輔助數據傳輸，圖中的節點連線代表簇間多跳傳輸路徑。

圖1LOMUC協議基本原理

2.1 相關工作準備階段

BS根據監測區域面積和全網節點數計算最優簇的數目mopt，采用文獻［6］中的方法，假設在M×M的區域內均勻部署N傳感器節點，運行結束后產生了m簇，m簇的整體能量消耗為ETotal，如式（3）。

對式（3）中的m求導并令導數等于0，求出mopt，然后得到最優通信半徑ropt：

2.2 LEACH-LOMUD簇頭選擇

針對LEACH協議閾值T(n)的不足，把能量和距離因素考慮進來，對公式Topt(n)進行改進，在此階段，對于每個傳感器點，使其產生一個0～1之間的隨機數，對于這個隨機數值小于閾值Topt(n)，此節點就成為候選簇頭。

其中，，p表示簇頭所占比例，r為已完成輪數，G是最近1p輪中未被選為過簇頭的集合，Erest、Eused、Eavg為上一輪剩余能量、節點在上一輪消耗的能量、簇內節點上一輪平均剩余能量。

2.3 簇的形成

候選簇頭產生后，各候選簇頭以距離常數d0廣播最終簇頭競選消息（其中包含剩余能量、到BS距離和一跳鄰居節點數）。在d0范圍內不包含有其他候選簇頭，則該節點為最終簇頭；反之，則根據公式（7）進行代價值計算并交換比較，代價值小的候選簇頭競選獲勝并廣播獲勝消息；反之，退出簇頭競選成為普通節點。普通節點依由文獻［11］改進的公式（8）選擇簇頭發送加入請求（含有剩余能量），簇頭接收到所有節點消息后，計算出簇間的平均剩余能量并采用TDMA方式向簇的成員節點發送時隙表，隨著簇頭向簇內所有成員節點廣播平均剩余能量和調度時隙表，簇的形成階段完成。

其中，α表示權重，P1=Eres(CHj)ditoCHj，，Eres(CHj)表示簇頭j的剩余能量，ditoCHj表示節點i簇頭j的距離，dCHjtoBS表示簇頭j到BS的距離，N(CHj)表示簇頭j的一跳鄰居節點數。

2.4 簇頭間通信

在簇形成后，與BS距離小于d0的簇頭直接將數據傳送至，距離大于d0的簇頭則使用多跳方式傳送數據，根據公式（9）計算代價函數Cost(CHi,CHj)值，選擇代價值最小的簇頭作為下一跳簇頭。其中，dCHitoCHj為簇頭i與j之間距離，dCHjtoBS為簇頭j與BS之間距離，Eres(CHj)為簇頭j當前剩余能量。

如果下一跳節點的簇頭已確定，若簇頭之間距離超過d0，便在距離該下一跳簇頭直線距離的中點附近選擇一個本簇內能量高且距離下一跳簇頭最近的中繼節點用于兩簇頭之間的多跳傳輸數據。中繼節點選舉公式如下式（10）。其中，dreltoCHi為中繼節點與所在簇的簇頭距離，dreltoCHj為中繼節點到下一跳簇頭的距離，Erel為中繼節點的剩余能量。

3 仿真實驗與分析

3.1 仿真實驗

對于算法驗證，通過對MATLAB建立仿真模型，對于LEACH、HEED、EB-LEACH［12］和EEUC與本LEACH-LOMUD算法進行對比。對比方式主要是網絡整體能量、網絡運行輪數、存活節點數等多項性能進行仿真分析，仿真參數見表1。

3.2 仿真實驗結果分析

算法中簇權值α值的選擇十分重要，因為α是控制普通節點加入簇，簇的區域規模大小的變量，參數選擇0.1～1進行試驗，結果如下圖2所示?？梢钥闯?，當α=0.5或α=0.6時效果最好，因此選擇α=0.6。

表1 網絡環境與參數

圖2 權值α與輪數的關系

圖3 五個協議的兩個參數（FND和HND）

由上圖3可知（死亡節點出現的輪數），能夠看出整個網絡情況，對于論數時間比較長的，說明其能量利用率高，比較小的，說明其能量利用率較低，整個網絡較差。對于那些輪數較長時間出現的，其即能量利用率就越高。圖3參數FND（第一個節點死亡參數）和HND（一半節點死亡參數）相互比較，LEACH算法的死亡節點出現在683輪后開始出現，而LEACH-LOMUC在1323輪后；1287輪之后，LEACH算法節點死亡一半，而LEACH-LOMUC在1672輪才出現這種情況。由此可見，改進算法LEACH-LOMUC不僅顯著地延長了網絡生存周期，而且死亡節點出現也晚于其他算法，這種現象表明LEACH-LOMUC能夠均衡網絡中節點的能耗。

圖4 生命周期對比

圖5 剩余總能量對比

圖4與圖5是五種算法網絡生命周期和剩余總能量的比較，從圖中可以看出，LEACH-LOMUC的生命周期最長且剩余能量最多，EEUC第二，LEACH最差。在生命周期方面，LEACH-LOMUC比LEACH延長一半，相較于EEUC，其生命周期延長了約13%，HEED和EB-LEACH的生命周期分別延長了約50%和40%；網絡剩余總能量方面，LEACH-LOMUC明顯優于LEACH、HEED、EB-LEACH和EEUC。

對于產生上述現象的主要原因如下，LEACH協議簇與匯聚節點之間以單跳方式直接通信，生命周期短并且能量消耗最大；HEED算法與LEACH不同（在競爭機制），對于簇頭選擇參考剩余能量，能夠選出更好的網絡分布。但是與EB-LEACH相比，其多次迭代生成的簇消耗過多能量。EB-LEACH算法對于簇頭選擇加入了能量閾值約束條件，性能較LEACH和HEED有所優勢，但缺點也十分明顯，其僅僅能均衡簇頭區域的能量分布，不能使得整個網絡能量消耗平衡。EEUC采用非均勻分簇方法使網絡中形成大小不等的簇，解決了熱點問題，采用多跳方法，節省能耗，使得其網絡生存時間較LEACH、HEED和EB-LEACH明顯延長。

LEACH-LOMUC和EEUC一樣也采用非均勻分簇和多跳數據傳輸方式節省網絡中通信能量消耗。不同于EEUC的是，LEACH-LOMUC在閾值上引入了上一輪節點的能量消耗因素和距離因素，使得能量大且離BS近的節點有更大的可能成為簇頭；節點在選擇加入簇頭時考慮了簇頭的規模和負載問題，節點選擇簇內未飽和的簇頭加入；在簇間多跳通信時，簇頭間距離大于設定值時選擇中繼節點輔助簇頭間數據傳輸，節省簇頭的能量，使得網絡每輪剩余能量有所增加，整個網絡能量平衡。所以LEACH-LOMUC的生命周期優于其他四種算法。

4 結論

對于現有無線傳感器網絡路由算法及其存在的問題，根據非均勻分簇的思想，提出了基于LEACH路由協議的改進協議LEACH-LOMUC。改進協議基本思想是簇頭的選舉考慮了節點上一輪的能量消耗和到節點到BS的距離；成簇時，考慮簇的規模、能量、簇頭與BS之間的距離，同時在時間片中引入休眠過程來解決非均勻分簇簇規模大小不一存在的步調不一致問題；最后對于簇頭間通信距離過大時引入中繼節點輔助數據傳輸，數據通過中繼節點和相鄰簇頭傳輸到BS。通過實驗對比結果表明：與LEACH、HEED、EB-LEACH和EEUC算法相較可以發現，算法能量均衡，生命周期延長。

參考文獻

［1］ 黃庭輝，伊凱，王玉良.基于非均勻分簇的無線傳感器網絡分層路由協議［J］.計算機應用，2017，23（13）20-24.

［2］ 石閃，施偉斌，朱蓓.一種針對無線傳感器網絡LEACH協議的改進算法［J］.電子科技，2017，32（10）：100-103.

［3］ 潘峰.基于能量的無線傳感器網絡分簇算法研究［J］.計算機仿真，2011，28（3）：159-162.

［4］ 賈云龍.無線傳感器網絡的非均勻分簇路由協議研究［J］.計算機應用，2014，24（7）：86-89.

［5］ Hzelman WR，Chandrakasan A，Balakrishnan H.Energy-Efficient Communication Protocol for Wireless Microsensor Networks［C］.Proceedings of the 2000 IEEE International Conference on System Sciences,2000.

［6］ Heinzelman WR，Chandrakasan A，Balakrishnan H.An Application-specific ProtocolArchitecture for Wireless Microsensor Networks［J］.IEEE Transactionson WirelessCommunications，2002，1（4）：660-670.

［7］ Bharti A，Devi C，Bhatia V.Enhanced Energy EfficientLEACH （EEE-LEACH） Algorithm Using MIMO for Wireless Sensor Network［C］.IEEE International Conference on Computational Intelligence&Computing Research,2016.

［8］ 張涌逸.無線傳感器網絡中非線性非均勻分簇路由研究［J］.無線互聯科技，2017，（4）：54-57.

［9］ 從立剛，楊華民，王楊惠，等.一種DTN網絡擺渡點存儲分配方案研究［J］.長春理工大學學報：自然科學版，2017，40（3）：117-122.

［10］ 孫超，彭力，唐波等.基于環的能耗均衡分簇路由算法［J］.計算機應用研究，2017，15（1）：27-36.

［11］ 江禹生，李萍，馬超.一種能量高效的無線傳感器網絡拓撲控制算法［J］.傳感器與微系統，2014，33（2）：146-149.