LEACH 算法應用于礦井無線通信的路由算法研究

王越群（通信作者），高小虎，曹春梅

（江蘇商貿職業學院 電子與信息學院，江蘇南通，226000）

1 應用于礦井中的無線傳感器網絡分層路由算法

無線傳感網[1]路由算法的主要作用是優化路徑，探求初始結點和目標結點間的多跳優化路徑并將數據沿優化路徑正確傳輸[2]。其中，分層路由算法應用最為廣泛，而LEACH 作為最基礎的分層路由算法之一，也常被用來作為改進算法的基礎算法。

針對長帶狀井道的環境結構，提出LEACH-mine 算法。在LEACH 算法的蔟首選擇中，沒有重視結點電量。LEACHmine 算法將結點剩余電量作為條件，以蔟內結點的均衡電量作為比較基準，選出電量高的結點成為蔟首。限制結點多次成為蔟首，均衡電量損耗。

(1)成蔟階段，在狹長的巷道內，蔟首不必向所有區域內的普通結點發送消息，只需通知相鄰結點，邀請入蔟。以距離蔟頭的長度為基準，結點選擇距離小的蔟，發出申請信息，這樣減少蔟頭電量損耗。

(2)信息傳遞。蔟間通訊采用多跳方式將消息傳送至Sink結點。利用最小跳數路由算法，選擇電量最多且相距最遠的結點轉發信息。

算法在相同電量的基礎上，信息傳輸距離最遠，優化電量利用效率，適合遠距離傳輸的網絡結構。而在文獻[3]中，筆者提出線性拓撲和局部電量均衡的分層路由算法。蔟首選舉的過程中，不僅考量結點當前電量，還引入相對位置均衡因子，使得位于區域中央且電量較高的結點更方便成為蔟首，有效解決了巷道邊緣結點成為蔟首，卻不利于轉發消息的問題。

文獻[4]中，為了解決帶狀巷道的能耗均衡問題，筆者提出LEBUC 算法。將結點電量、結點與Sink 結點的距離、結點分布密度作為控制條件，選出符合要求的蔟首，改善礦井WSN 路由電量空洞的情況。在分蔟前，由電量模型計算出能耗最小的條件下，最優的蔟首期望個數，而后通過調整閾值，使得候選蔟首的數量大于期望的最優個數，競爭失敗的結點暫時“停工”，以減少能耗。長距離線性巷道中，靠近Sink 的結點由于大量轉發監測信息，能耗快，生命期短，因此解決此電量“空洞”的有效辦法是計算合理的蔟首競選半徑。作者改進了 EEUC 算法[5]只考慮候選蔟首與Sink 結點距離的情況，加入對結點剩余電量的考量。

2 LEACH 算法

LEACH 算法作為分蔟路由算法中最典型的算法，對WSN 路由算法的設計另辟新徑，但是礦井巷道的網絡拓撲不同于其他環境下的結構，LEACH 算法應用在礦井巷道狹窄綿長的環境中，仍存在很多的不足之處[6]。

WSN 的路由機制負責選擇信息傳遞的路徑，而傳輸的效率則決定了整個網絡的使用周期，即傳輸速率越快，電量損耗越少，網絡使用時間越長[7]。LEACH 的分蔟理論能夠適應礦井長巷道的環境結構，使得蔟內結點能夠將收集的信息統一由蔟首結點簡單處理后壓縮傳送，節省時間和電量。蔟首結點承擔預處理感知數據以及轉發數據的功能，因此，如何優化蔟首結點選擇機制顯得至關重要。傳統的LEACH分蔟算法在蔟首結點選擇機制上，考慮因素單一，面對礦井復雜多變的應用環境，性能顯得不夠穩定。

LEACH 算法是一種低功耗自適應集蔟分層型算法，從上一節的討論中，可以看出LEACH 算法作為經典分蔟機制，應用于礦井長巷道環境中，還是有很多缺陷，蔟首結點選擇的策略上隨機性太強，選擇蔟首結點的約束條件太少，無法保證最終蔟首結點自身剩余電量多，位置優越，和其他結點通信便利的優勢。位于巷道中心，剩余電量多且鄰居結點數量多的結點成為蔟首結點更利于信息的轉發和收集。

文獻[8]在改進 LEACH 算法中，通過改變結點成為蔟首結點的概率的計算方式，對閾值T(n) 引入結點電量因子和相對位置因子，提高剩余電量高且距離區域中心的較近的結點成為蔟首結點的可能性。但是并沒有考慮到蔟內結點與蔟首結點通信的情況，如果蔟首結點本身的鄰居結點個數較多，也就是與蔟首結點直接通信的結點數量較多，可減少蔟內收集數據時多次轉發而產生的電量損耗和時延。

本文主要考慮從三個方面優化蔟首結點選擇機制，將結點剩余電量、鄰居結點個數、結點距離局部區域中心的距離三個因素引入閾值和結點產生的隨機值的計算中。

(1)將結點剩余電量作為結點產生0～1 隨機值的條件因素，使得剩余電量高的結點產生的隨機值越小；

(2)在初始階段，統計鄰居結點的個數，在計算閾值T(n) 時可加入考慮，降低鄰居結點個數較少的結點成為蔟首結點的可能性；

(3)選擇距離區域中心位置近的結點作為蔟首結點，可保證通信范圍和通信質量。

3 基于LEACH 優化算法的礦井WSN 路由算法

■3.1 閾值的優化

針對礦井長直巷道結構，在礦井網絡的每個區域內蔟首結點的選擇過程中，對閾值進行優化，引入結點的相對位置因素和結點鄰居結點個數，進而優化 LEACH 算法的蔟首結點選擇機制。

■3.2 RPLA 算法描述

對WSN 模型的預設條件為以下幾點：

(1)傳感器電量有限，但類型相同。

(2)假設Sink 結點電量不受限，可以持續工作，且不能變換位置。

(3)傳感器結點隨機部署在監測區域后，位置不能變換。

(4)每個傳感器結點都可以對數據進行融合。

(5)傳感器結點可以自動調節發射功率。

(6)Sink 結點收集數據后定時向基站發送。

上述條件中假設Sink 結點是電量不受限制的傳感器結點，采用集中式控制策略執行機制[9]。機制的執行過程具有周期性，每輪執行過程包括兩個階段：成蔟階段和穩定信息傳遞階段。其中成蔟階段包括蔟首結點選擇階段、蔟首結點收集蔟內成員結點信息階段、最終蔟的形成階段；而穩定信息傳遞階段包括蔟內傳輸、蔟間傳輸。本章主要研討蔟的形成階段：

(1)初始化蔟首選舉階段

算法規定一個0-1 之間的閾值T(n)，并通過公式（1）得出結點產生的隨機值μ：

式中，Eire為結點剩余電量，E0為結點初始電量。若μ

(2)普通結點要求入蔟

蔟首結點產生后，向附近結點廣播競選成功的消息，消息中包含蔟首結點的位置和剩余電量情況，其他普通結點通過比較與本區域蔟首結點和左右相鄰兩個區域蔟首結點之間的距離，來選擇距離最近的蔟首結點，發送要求入蔟的消息，同時將自己的位置信息、剩余電量信息、ID 號以及結點的鄰居結點數量信息，壓縮發給要要求入蔟的蔟首結點。

(3)蔟首結點收集信息

蔟首結點收集蔟內成員的位置信息、剩余電量信息、結點ID 以及結點的鄰居結點數量（結點度數）信息等，將成員結點信息存儲表中。

(4)完成階段

蔟首結點設置TDMA 時隙表調度蔟內結點避免發生沖突。蔟首結點將TDMA 時隙表發送給蔟內成員，成員結點根據收到的時隙表，按照確定時隙向蔟首結點發送感知信息。

穩定傳輸階段，蔟內結點與蔟首結點采用單跳通信，在規定時間內直接將采集的數據發送給蔟首結點，在非傳輸時間內，關閉無線電設備保存電量。一段時間后，下一輪蔟首結點競選開始。蔟間通信則采用單跳直接通信方式，數據經過蔟首結點簡單的處理融合后，發送給相鄰Sink 結點。

RPLA 算法的核心代碼如圖1 所示。

圖1 RPLA 算法核心代碼

4 仿真與分析

■4.1 仿真環境

表1 仿真參數表

本次仿真實驗監測的區域范圍是200m×10m 的矩形區域，模擬礦井長直隧道形狀，監測區域長度長于寬度，其中隨機部署100 個結點，并將Sink 結點坐標設置為區域邊界靠近中軸線，坐標為（200，25），這樣可使結點密度適中，便于觀察結點位置和分蔟效果。結點初始電量、數據包大小和報頭大小等無線電量模型相關參數的取值與文獻[9]相同。

■4.2 仿真結果與分析

(1)基站接收數據包數量比較

圖2 給出三種算法中基站接收的數據包的數量，接收數量差異較大，很明顯改進后的RPLA 路由算法中基站接收的數據包數量遠遠超過 LEACH 算法，略優于 LEACH_ C 算法，從圖2 中可以看出，RPLA 機制接收的數據包數量高于LEACH 算法且是LEACH 算法接收數據包數量的約兩倍左右，LEACH 算法在第600 輪時不再接收數據，而LEACH_C 算法從第600 輪開始接收的數據包數量也在減少，但改進的RPLA 路由算法從開始時，接收的數據包數量就遠大于LEACH 算法，LEACH_ C 算法雖然接收數據包的數量多于LEACH 算法，但在第700 輪開始接收數據包的速度緩慢，最后結點全部失效，不再接收數據包。

圖2 基站接收數據包數量比較

RPLA 路由算法在蔟首結點選舉上考慮結點的剩余電量情況，利用單個結點剩余電量與全部結點總電量的比值作為產生的隨機數，同時重新構建閾值中結點成為蔟首結點概率的計算模型，根據實際工程背景，加入了結點相對位置和結點鄰居結點個數兩個因子，因此選舉出的蔟首結點電量相對較高且位置便于信息傳遞。

(2)存活結點個數比較

圖3 中給出了LEACH、LEACH_ C 以及 RPLA 三種算法的存活結點個數的比較，在200 輪的實驗時間之前，三種算法存活結點個數相差不大，但在實驗中后期，隨著實驗時間的增長，三種算法的能耗逐漸增多，RPLA 機制的優勢明顯，相較于其他兩種機制，RPLA 機制能耗較少，存活結點數量較多。在實驗進行到第700 輪時，改進機制的存活結點數約是LEACH_ C 機制的4.5 倍，而LEACH 算法此時的存活結點數已經為0，網絡生命周期早已經結束。

圖3 存活結點個數比較

LEACH 算法隨機選舉蔟首結點，信息傳遞能力不強，反而導致能耗更多，RPLA 機制針對LEACH 算法的不足，做出改進，蔟首結點的位置位于區域中心，可以縮短蔟內結點的信息傳遞距離，降低能耗，從而延長井下網絡使用時間。

(3)結點平均剩余電量比較

正如圖4 所示，對三種算法的實驗結果進行對比分析，在井下網絡工作的時間里，傳感器平均剩余電量的情況，實際上，反映出結點的平均能耗情況。可以看出LEACH算法中結點的平均剩余電量在第700 輪時為0，而此時LEACH-C 算法和RPLA 算法的結點平均剩余電量仍有很多，由于RPLA 算法在蔟首結點選擇時考慮到結點的相對位置和鄰居結點個數，當候選蔟首結點位于區域中心附近且鄰居結點個數較多時，蔟首結點的鄰居結點可以直接將感知數據發送給蔟首結點，縮短蔟首結點與結點之間的距離，減少能耗。

圖4 結點平均剩余電量

5 結論

本文主要對LEACH 算法的蔟首結點選舉策略進行改進，在閾值計算和結點產生的隨機值上進行改變，加入對結點剩余電量、相對位置以及結點鄰居結點個數的考慮，使得成為蔟首結點的結點具有距離區域中心近、剩余電量高、鄰居結點個數多的特點和通信便利的優勢。優化了礦井WSN 路由算法，提升整體井下網絡性能。