LEACH 算法應(yīng)用于礦井無線通信的路由算法研究

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

（江蘇商貿(mào)職業(yè)學院 電子與信息學院，江蘇南通，226000）

1 應(yīng)用于礦井中的無線傳感器網(wǎng)絡(luò)分層路由算法

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

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

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

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

算法在相同電量的基礎(chǔ)上，信息傳輸距離最遠，優(yōu)化電量利用效率，適合遠距離傳輸?shù)木W(wǎng)絡(luò)結(jié)構(gòu)。而在文獻[3]中，筆者提出線性拓撲和局部電量均衡的分層路由算法。蔟首選舉的過程中，不僅考量結(jié)點當前電量，還引入相對位置均衡因子，使得位于區(qū)域中央且電量較高的結(jié)點更方便成為蔟首，有效解決了巷道邊緣結(jié)點成為蔟首，卻不利于轉(zhuǎn)發(fā)消息的問題。

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

2 LEACH 算法

LEACH 算法作為分蔟路由算法中最典型的算法，對WSN 路由算法的設(shè)計另辟新徑，但是礦井巷道的網(wǎng)絡(luò)拓撲不同于其他環(huán)境下的結(jié)構(gòu)，LEACH 算法應(yīng)用在礦井巷道狹窄綿長的環(huán)境中，仍存在很多的不足之處[6]。

WSN 的路由機制負責選擇信息傳遞的路徑，而傳輸?shù)男蕜t決定了整個網(wǎng)絡(luò)的使用周期，即傳輸速率越快，電量損耗越少，網(wǎng)絡(luò)使用時間越長[7]。LEACH 的分蔟理論能夠適應(yīng)礦井長巷道的環(huán)境結(jié)構(gòu)，使得蔟內(nèi)結(jié)點能夠?qū)⑹占男畔⒔y(tǒng)一由蔟首結(jié)點簡單處理后壓縮傳送，節(jié)省時間和電量。蔟首結(jié)點承擔預(yù)處理感知數(shù)據(jù)以及轉(zhuǎn)發(fā)數(shù)據(jù)的功能，因此，如何優(yōu)化蔟首結(jié)點選擇機制顯得至關(guān)重要。傳統(tǒng)的LEACH分蔟算法在蔟首結(jié)點選擇機制上，考慮因素單一，面對礦井復(fù)雜多變的應(yīng)用環(huán)境，性能顯得不夠穩(wěn)定。

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

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

本文主要考慮從三個方面優(yōu)化蔟首結(jié)點選擇機制，將結(jié)點剩余電量、鄰居結(jié)點個數(shù)、結(jié)點距離局部區(qū)域中心的距離三個因素引入閾值和結(jié)點產(chǎn)生的隨機值的計算中。

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

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

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

3 基于LEACH 優(yōu)化算法的礦井WSN 路由算法

■3.1 閾值的優(yōu)化

針對礦井長直巷道結(jié)構(gòu)，在礦井網(wǎng)絡(luò)的每個區(qū)域內(nèi)蔟首結(jié)點的選擇過程中，對閾值進行優(yōu)化，引入結(jié)點的相對位置因素和結(jié)點鄰居結(jié)點個數(shù)，進而優(yōu)化 LEACH 算法的蔟首結(jié)點選擇機制。

■3.2 RPLA 算法描述

對WSN 模型的預(yù)設(shè)條件為以下幾點：

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

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

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

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

(5)傳感器結(jié)點可以自動調(diào)節(jié)發(fā)射功率。

(6)Sink 結(jié)點收集數(shù)據(jù)后定時向基站發(fā)送。

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

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

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

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

(2)普通結(jié)點要求入蔟

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

(3)蔟首結(jié)點收集信息

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

(4)完成階段

蔟首結(jié)點設(shè)置TDMA 時隙表調(diào)度蔟內(nèi)結(jié)點避免發(fā)生沖突。蔟首結(jié)點將TDMA 時隙表發(fā)送給蔟內(nèi)成員，成員結(jié)點根據(jù)收到的時隙表，按照確定時隙向蔟首結(jié)點發(fā)送感知信息。

穩(wěn)定傳輸階段，蔟內(nèi)結(jié)點與蔟首結(jié)點采用單跳通信，在規(guī)定時間內(nèi)直接將采集的數(shù)據(jù)發(fā)送給蔟首結(jié)點，在非傳輸時間內(nèi)，關(guān)閉無線電設(shè)備保存電量。一段時間后，下一輪蔟首結(jié)點競選開始。蔟間通信則采用單跳直接通信方式，數(shù)據(jù)經(jīng)過蔟首結(jié)點簡單的處理融合后，發(fā)送給相鄰Sink 結(jié)點。

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

圖1 RPLA 算法核心代碼

4 仿真與分析

■4.1 仿真環(huán)境

表1 仿真參數(shù)表

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

■4.2 仿真結(jié)果與分析

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

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

圖2 基站接收數(shù)據(jù)包數(shù)量比較

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

(2)存活結(jié)點個數(shù)比較

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

圖3 存活結(jié)點個數(shù)比較

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

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

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

圖4 結(jié)點平均剩余電量

5 結(jié)論

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