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

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

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

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

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

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

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

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

算法在相同電量的基礎(chǔ)上，信息傳輸距離最遠(yuǎn)，優(yōu)化電量利用效率，適合遠(yuǎn)距離傳輸?shù)木W(wǎng)絡(luò)結(jié)構(gòu)。而在文獻(xiàn)[3]中，筆者提出線性拓?fù)浜途植侩娏烤獾姆謱勇酚伤惴ā］走x舉的過程中，不僅考量結(jié)點(diǎn)當(dāng)前電量，還引入相對(duì)位置均衡因子，使得位于區(qū)域中央且電量較高的結(jié)點(diǎn)更方便成為蔟首，有效解決了巷道邊緣結(jié)點(diǎn)成為蔟首，卻不利于轉(zhuǎn)發(fā)消息的問題。

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

2 LEACH 算法

LEACH 算法作為分蔟路由算法中最典型的算法，對(duì)WSN 路由算法的設(shè)計(jì)另辟新徑，但是礦井巷道的網(wǎng)絡(luò)拓?fù)洳煌谄渌h(huán)境下的結(jié)構(gòu)，LEACH 算法應(yīng)用在礦井巷道狹窄綿長(zhǎng)的環(huán)境中，仍存在很多的不足之處[6]。

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

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

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

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

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

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

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

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

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

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

■3.2 RPLA 算法描述

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

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

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

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

(4)每個(gè)傳感器結(jié)點(diǎn)都可以對(duì)數(shù)據(jù)進(jìn)行融合。

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

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

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

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

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

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

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

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

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

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

(4)完成階段

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

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

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

圖1 RPLA 算法核心代碼

4 仿真與分析

■4.1 仿真環(huán)境

表1 仿真參數(shù)表

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

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

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

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

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

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

(2)存活結(jié)點(diǎn)個(gè)數(shù)比較

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

圖3 存活結(jié)點(diǎn)個(gè)數(shù)比較

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

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

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

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

5 結(jié)論

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