基于網(wǎng)絡(luò)分區(qū)和路徑能耗的深井無線傳感器網(wǎng)絡(luò)多簇 首路由算法*

余修武，梁北孔，周利興，謝曉永，范思柔，王宇琴，劉 琴

(1.南華大學 環(huán)境與安全工程學院，湖南 衡陽 421001；2.金屬礦山安全與健康國家重點實驗室，安徽 馬鞍山 243000)

0 引言

礦物資源消耗的增長使得淺部礦物逐步殆盡，導致地下采礦向更深水平推進[1]。深部礦井因高溫高濕、高地應力、供電線路長及人員設(shè)備密集等因素造成復合型災害事故頻發(fā)[2]，對深井開采的安全工作造成巨大威脅。由于現(xiàn)有的有線礦井安全監(jiān)測系統(tǒng)不能滿足深井的安全需求[3]，有必要把無線傳感網(wǎng)絡(luò)引入深井生產(chǎn)中。傳感器網(wǎng)絡(luò)的應用相關(guān)性強，隨著應用環(huán)境的不同，路由算法差距或許會很大，尚不存在通用的路由算法[4]，且目前適用深部礦井應用環(huán)境的路由算法較少。因此，開展深部礦井無線傳感器網(wǎng)絡(luò)路由算法的研究意義重大。

無線傳感器網(wǎng)絡(luò)是1個由大量節(jié)點構(gòu)成的，具有數(shù)據(jù)采集、融合與傳輸?shù)淖越M織網(wǎng)絡(luò)[5]。為解決無線傳感器網(wǎng)絡(luò)能耗低效及“熱區(qū)”問題，許多路由算法被提出。其中，LEACH算法[6]簇首節(jié)點的選擇是隨機的，且以單跳方式傳輸數(shù)據(jù)，會產(chǎn)生簇首節(jié)點不均勻地分布和當前能量較少的節(jié)點也成為簇首等問題；錢開國等針對路由算法中簇首節(jié)點分布不均問題提出HNDCRA[7]算法，均衡了簇首分布，但其算法的簇首競選機制未加入節(jié)點當前能量，導致部分簇首節(jié)點能量被過快地消耗；張文梅等提出改進的無線傳感器網(wǎng)絡(luò)非均勻分簇路由算法[8]，把節(jié)點當前能量引入簇首競選機制中，使簇首能量均衡地消耗，該算法一定程度上能減少并均衡節(jié)點能量消耗，但沒有對“熱區(qū)”問題提出解決方案；彭鐸等針對無線傳感網(wǎng)“熱區(qū)”問題提出EUCP[9]算法，能在一定程度上改善“熱區(qū)”問題。然而，上述路由算法多適用于典型大面積監(jiān)控領(lǐng)域，在深部礦井特殊的應用環(huán)境中，狹長的帶狀巷道使其具有局限性。為此，王偉等針對帶狀網(wǎng)“熱區(qū)”的出現(xiàn)提出CRLDB[10]算法，引入非均勻分簇概念，使用候選簇首競爭策略；劉佳針對礦井下巷道應用環(huán)境提出CHPBN[11]算法，僅分簇1次，數(shù)據(jù)多跳轉(zhuǎn)發(fā)；林啟中等提出HEED-EELD(Dual-cluster-head routing algorithm based on location information)[12]算法，以單跳距離構(gòu)建層次，采用雙簇首并將節(jié)點位置及其當前能量引入路由選擇機制。然而，以上算法大多運用非均勻分簇思想，競選簇首并以多跳方式傳輸簇間數(shù)據(jù)，但均未考慮數(shù)據(jù)傳輸過程中路徑通信代價及跳數(shù)問題。因此，本文提出1種基于網(wǎng)絡(luò)分區(qū)和路徑能耗的帶狀無線傳感器網(wǎng)絡(luò)多簇首簇路由算法(NPPEC)，算法采用跳數(shù)泛洪方式建立帶狀網(wǎng)絡(luò)分區(qū)結(jié)構(gòu)，將節(jié)點分布密度加入簇首競選機制中，通過主簇首和副簇首的分工配合，使簇首能量更均衡地消耗；依據(jù)路徑能耗、節(jié)點當前能量及位置計算路徑選擇概率，并通過控制跳數(shù)改善數(shù)據(jù)傳輸?shù)膶崟r性。

1 系統(tǒng)模型

1.1 無線通信模型

采用無線通信模型First order radio model[13]獲取某節(jié)點發(fā)送和接收數(shù)據(jù)包的能量消耗值。假設(shè)從節(jié)點A發(fā)送lbit的數(shù)據(jù)到節(jié)點B，A和B之間的距離為d，則其能量消耗值求解如下：

(1)

節(jié)點B接收lbit數(shù)據(jù)所消耗的能量求解如下：

ERx(l,d)=l×Eelec

(2)

式(1)中的限值d0為：

(3)

式中：Eelec表示節(jié)點發(fā)送或接收1 bit數(shù)據(jù)的能量消耗值；εfs表示在自由空間模型下1 bit數(shù)據(jù)的能耗；εamp表示在多路徑模型下發(fā)送1 bit數(shù)據(jù)的能耗；d0表示通信距離限值;d小于d0時，r=2；當d大于或等于d0時，r=4。傳感器節(jié)點有傳感器模塊、處理器模塊及無線通信模塊，其中無線通信模塊消耗了絕大部分能量，如圖1所示。

圖1 網(wǎng)絡(luò)節(jié)點能耗情況Fig.1 Energy consumption of network nodes

1.2 深井巷道帶狀網(wǎng)絡(luò)分區(qū)模型

節(jié)點布置在深井巷道里面，區(qū)域長度L一般遠大于寬度W，構(gòu)成帶狀無線傳感網(wǎng)。假設(shè)有nall個節(jié)點組成此網(wǎng)絡(luò)，第i個節(jié)點為Si，則節(jié)點集S={S1,S2,,Snall}。此帶狀網(wǎng)絡(luò)存在如下特點：①網(wǎng)絡(luò)中所有節(jié)點均已完成定位算法，位置坐標已知，忽略定位誤差對路由算法的影響；②除了匯聚節(jié)點的能量不受限制之外，其余節(jié)點能量有限并存在相同屬性及功能；③因節(jié)點的無線通信模塊消耗了大部分能量，忽略其余模塊的能耗；④普通節(jié)點數(shù)據(jù)傳播延遲遠小于數(shù)據(jù)采集周期，不會造成網(wǎng)絡(luò)擁堵；⑤因深井環(huán)境復雜多變，節(jié)點能根據(jù)實際情況調(diào)節(jié)信號發(fā)射強度；⑥信息接收節(jié)點能基于接收信號強度計算與發(fā)射節(jié)點之間的距離。

采用跳數(shù)泛洪方式建立網(wǎng)絡(luò)分區(qū)結(jié)構(gòu)，其主要步驟如下：

1)匯聚節(jié)點廣播1個初始消息PA給其鄰居節(jié)點，初值為0。

2)收到該PA信號的節(jié)點就將自己的分區(qū)值設(shè)置為PA+ 1，接著該節(jié)點將自身分區(qū)值PA(PA=PA+1)再廣播給其鄰居節(jié)點。

3) 收到新PA消息的節(jié)點再把自己的分區(qū)值設(shè)置為PA+1，因為可能會收到來自前1分區(qū)多個節(jié)點的PA值，這里規(guī)定PA值只設(shè)置1次。

消息依照這樣的規(guī)律在監(jiān)測區(qū)域擴散，區(qū)域內(nèi)節(jié)點隨機分布，且都能獲得對應的分區(qū)值，即全網(wǎng)建成了分區(qū)結(jié)構(gòu)，如圖2所示。

圖2 深井巷道網(wǎng)絡(luò)分區(qū)結(jié)構(gòu)Fig.2 Deep mine tunnel network partition structure

2 NPPEC算法

節(jié)點根據(jù)網(wǎng)絡(luò)分區(qū)結(jié)構(gòu)獲得與自身位置對應的分區(qū)值，該值可應用于簇首競選及數(shù)據(jù)轉(zhuǎn)發(fā)過程。數(shù)據(jù)按分區(qū)值減少的方向逐跳轉(zhuǎn)發(fā)，路由按分區(qū)值增加的方向依次建立，構(gòu)成帶狀網(wǎng)絡(luò)分區(qū)結(jié)構(gòu)。該算法分為3階段：簇首競選、簇的形成、能量多路徑路由。

2.1 簇首競選

簇首競選分為主簇首競選和副簇首競選。其中，主簇首負責簇內(nèi)數(shù)據(jù)的收集與融合；副簇首負責簇間數(shù)據(jù)轉(zhuǎn)發(fā)，包括轉(zhuǎn)發(fā)來自其主簇首的數(shù)據(jù)。

2.1.1 主簇首競選

以文獻[4]的閾值公式為基礎(chǔ)，將節(jié)點當前能量、節(jié)點分布密度以及節(jié)點到匯聚節(jié)點的距離引入該閾值公式中，如式(4)所示。

(4)

(5)

式中：n表示第r輪中沒有擔任主簇首的某1節(jié)點；T(n)表示節(jié)點n的閾值；P指主簇首在全網(wǎng)節(jié)點中所占比例，P=n/nall；r是選舉輪數(shù)；rmod(1/P)指第r輪中擔任過主簇首節(jié)點的個數(shù)；G是第r輪中沒有擔任過主簇首的節(jié)點集合；α,β,γ是參數(shù)，且α+β+γ=1；Ecur是在第r輪中某節(jié)點的當前能量值，該值在式(4)中影響較大；Et表示第r輪網(wǎng)絡(luò)能量總和；di指節(jié)點到匯聚節(jié)點的距離；dave指第r輪中所有存活節(jié)點到匯聚節(jié)點的平均距離；dmax指第r輪中范圍的最大距離值；Qn指節(jié)點分布密度，第r輪初始階段，以R為半徑的范圍中，節(jié)點進行信息交互并采集存活節(jié)點信息，由此可得Nei(n)a；Na表示網(wǎng)絡(luò)存活節(jié)點數(shù)量，由匯聚節(jié)點獲取并向全網(wǎng)廣播。節(jié)點隨機產(chǎn)生1個0～1范圍內(nèi)的數(shù)，當該數(shù)值小于T(n)時，節(jié)點成為候選主簇首；候選主簇首向同1分區(qū)內(nèi)的所有節(jié)點廣播其當前能量信息，并將自身的當前能量與同1分區(qū)其余候選主簇首的當前能量相比較，假如該候選主簇首的當前能量比同分區(qū)的其余任1候選主簇首的當前能量都要大，則該候選主簇首當選該分區(qū)的主簇首，反之則競選失敗。最后，當選分區(qū)主簇首的節(jié)點向整個分區(qū)內(nèi)的所有節(jié)點廣播其競選成功的消息。

該閾值公式的理論依據(jù)論述如下：首先，節(jié)點當前能量是主簇首競選機制中的重要因素，如果競選主簇首時不考慮節(jié)點當前能量，則可能發(fā)生當前能量過少的節(jié)點擔任主簇首的情況，會導致部分節(jié)點因能耗過快而失效，節(jié)點當前能量越高，成為主簇首的概率就應越高；相反，節(jié)點當前能量越低，被選舉為主簇首節(jié)點的概率也就越低。其次，在深部礦井中，各工作區(qū)域的環(huán)境及功能存在差異，節(jié)點分布密度是不同的，節(jié)點分布密度大的區(qū)域，增加其節(jié)點擔任主簇首的概率；反之，節(jié)點分布密度小的區(qū)域，減少其節(jié)點成為主簇首的概率。最后，從能耗角度來說，節(jié)點到匯聚節(jié)點的距離對主簇首競選有直接關(guān)聯(lián)，如果距匯聚節(jié)點較遠的節(jié)點成為主簇首，網(wǎng)絡(luò)的能耗就會比距匯聚節(jié)點較近的節(jié)點更大，假如網(wǎng)絡(luò)中經(jīng)常出現(xiàn)這種情況，則會使網(wǎng)絡(luò)生命周期更早地結(jié)束。

2.1.2 副簇首選取

文獻[14]論證了簇首節(jié)點數(shù)量占比k為5%左右時，網(wǎng)絡(luò)的能量消耗最為理想。在主簇首競爭范圍內(nèi)，基于能量情況選取副簇首。首先，計算某簇所需副簇首的數(shù)量，計算方法如下：

nv=(nall×k-n)×f

(6)

f=aPA{0

(7)

其中，a滿足式(8)：

a1+a2++an=1

(8)

式中：nv表示某簇副簇首的數(shù)量；nall表示全網(wǎng)節(jié)點總數(shù)量；k指簇首在全網(wǎng)節(jié)點中所占比例；n表示分簇數(shù)量，即主簇首數(shù)量，等于最大分區(qū)值；f是以PA為因變量的函數(shù)，表示越靠近匯聚節(jié)點的簇，其副簇首數(shù)量越多，數(shù)據(jù)轉(zhuǎn)發(fā)能力越強，能在一定程度上解決“熱區(qū)”問題。

同時，改進文獻[15]的簇內(nèi)節(jié)點閾值公式后，進行副簇首的競選。

(9)

2.2 簇的形成

NPPEC算法主簇首的競爭半徑為R，由系統(tǒng)設(shè)置。則NPPEC算法成簇結(jié)構(gòu)如圖3所示。

圖3 NPPEC算法成簇結(jié)構(gòu)Fig.3 NPPEC algorithm cluster structure

2.3 能量多路徑路由

簇內(nèi)所有節(jié)點都在其主簇首的競爭范圍內(nèi)，采用單跳方式進行簇內(nèi)數(shù)據(jù)傳輸可減少網(wǎng)絡(luò)能耗。多路徑數(shù)據(jù)轉(zhuǎn)發(fā)，指各副簇首之間的轉(zhuǎn)發(fā)過程，按分區(qū)值減小的方向傳輸，采用能量多路徑路由機制，使網(wǎng)絡(luò)能量更均衡地消耗。多路徑轉(zhuǎn)發(fā)過程描述如下：

1)NPPEC算法成簇結(jié)構(gòu)建立完成后，各簇的副簇首節(jié)點按分區(qū)值增加的方向逐層建立路由，其中建立消息包括1個代價域和1個跳數(shù)域，分別指消息發(fā)出節(jié)點到匯聚節(jié)點的能量信息和跳數(shù)信息，2者初始值都設(shè)為0。

2)副簇首Ni發(fā)送路徑建立消息給鄰居副簇首Nj，當在Nj位于源節(jié)點和Ni之間時，副簇首Nj才轉(zhuǎn)發(fā)此消息，否則不轉(zhuǎn)發(fā)。

3)數(shù)據(jù)從副簇首Nj發(fā)出，經(jīng)副簇首Ni轉(zhuǎn)發(fā)到匯聚節(jié)點，路徑能耗值指副簇首Ni的代價值與Nj到Ni間的通信能耗之和，如式(10)所示：

CNj,Ni=Ct(Ni)+Met(Nj,Ni)

(10)

式中：CNj,Ni指數(shù)據(jù)從副簇首Nj發(fā)出，經(jīng)副簇首Ni轉(zhuǎn)發(fā)到達匯聚節(jié)點的代價；Met(Nj,Ni)表示Nj到Ni的通信能耗，計算方法如式(11)所示：

(11)

式中：eNj,Ni指Nj和Ni間直接進行數(shù)據(jù)轉(zhuǎn)發(fā)的能耗；ENi指Ni的當前能量；x，y是常量。

4)根據(jù)式(12)，符合條件的鄰居副簇首被選進副簇首Nj的路由表FTj內(nèi)。

(12)

式中：hNj,Ni指數(shù)據(jù)從副簇首Nj發(fā)出，經(jīng)副簇首Ni轉(zhuǎn)發(fā)到匯聚節(jié)點所需要的平均跳數(shù)；λ，μ基于實際情況設(shè)定，均大于1。

5)根據(jù)式(13)和(14)計算FTj內(nèi)的副簇首被選為下1跳的概率。

(13)

(14)

式中：PNj,Ni指FTj內(nèi)的副簇首被選作下1跳的概率；YNj,Ni是以副簇首Nj當前能量及到匯聚節(jié)點距離為因變量的函數(shù)；Er是第r輪中能量總和；ENj為副簇首Nj的當前能量；dNi,s，dNj,s分別為副簇首Ni到匯聚節(jié)點的距離以及相鄰副簇首Nj到匯聚節(jié)點的距離；dNj,Ni為副簇首Nj與相鄰副簇首Ni的間距；ω1，ω2為參數(shù)控制因子。

6)路由表FTj中的某1節(jié)點，被副簇首Nj依據(jù)概率選出，并接收來自Nj的數(shù)據(jù)。

能量多路徑路由進行數(shù)據(jù)傳輸?shù)牧鞒倘鐖D4所示。

圖4 能量多路徑路由過程Fig.4 Energy multi-path routing process

3 仿真及結(jié)果分析

3.1 參數(shù)設(shè)置

模擬深部礦井巷道應用環(huán)境，運用MATLAB軟件對NPPEC算法、經(jīng)典的LEACH算法和近年來新提出的HEED-EELD算法進行仿真比較。仿真參數(shù)如表1所示。

表1 網(wǎng)絡(luò)仿真參數(shù)Table 1 Network simulation parameters

3.2 仿真結(jié)果分析

隨機地選取10輪實驗數(shù)據(jù)，比較3種算法的簇首在單輪周期中的能耗情況，如圖5所示。依據(jù)圖5，NPPEC算法和HEED-EELD算法單輪簇首的能耗比LEACH算法低，前2者采用多跳通信方式，而LEACH則使用單跳方式傳輸數(shù)據(jù)，這表明多跳通信比單跳通信更能降低網(wǎng)絡(luò)能耗。此外，可觀察到NPPEC算法比HEED-EELD算法單輪簇首的能耗更低，且波動幅度更小，這是因為NPPEC算法在主簇首競選中考慮了節(jié)點分布密度，并把簇首數(shù)量控制在全網(wǎng)節(jié)點的5%左右，能有效降低和均衡網(wǎng)絡(luò)簇首的能耗。

圖5 單輪簇首消耗總能量Fig.5 Total energy consumption of Single-cycle cluster head

圖6比較了3種算法的網(wǎng)絡(luò)能耗的總和隨網(wǎng)絡(luò)運行輪數(shù)的增長而上升的情況。由表1可知，該帶狀網(wǎng)絡(luò)的總能量為200 J。觀察圖6發(fā)現(xiàn)，LEACH的總能耗相比較其他2個算法更早穩(wěn)定在某數(shù)值，說明網(wǎng)絡(luò)因部分節(jié)點死亡而喪失了數(shù)據(jù)傳輸能力，此時輪數(shù)約為498輪；其次是HEED-EELD，約為751輪；最后才是NPPEC，約為900輪。在498輪時，LEACH算法構(gòu)建的網(wǎng)絡(luò)能耗為63 J，HEED-EELD算法為55 J，NPPEC算法為50 J。此時，NPPEC比LEACH、HEED-EELD的能量消耗分別減少了20.63%和9.09%。相比其他2種算法，NPPEC算法能更高效地運用有限能量。這是因為該算法副簇首的競選充分考慮了節(jié)點能量因素和距離因素，同時在數(shù)據(jù)收集傳輸階段，主、副簇首高效配合，并依據(jù)路徑通信代價優(yōu)化傳輸路徑。仿真數(shù)據(jù)說明，NPPEC算法能較好地提高網(wǎng)絡(luò)的能量效率。

圖6 網(wǎng)絡(luò)節(jié)點總能耗Fig.6 Total energy consumption of network nodes

網(wǎng)絡(luò)不穩(wěn)定期指從網(wǎng)絡(luò)第1個節(jié)點死亡到整個網(wǎng)絡(luò)失效的時間段，其值越小網(wǎng)絡(luò)能耗的均衡性越好。圖7對比了3種算法的存活節(jié)點數(shù)量隨網(wǎng)絡(luò)運行輪數(shù)增長而減少的情況，觀察圖7可知，LEACH算法網(wǎng)絡(luò)的第1個節(jié)點能量殆盡的輪數(shù)約為48輪，HEED-EELD算法約為350輪，NPPEC算法約為531輪；另外，LEACH算法在整個網(wǎng)絡(luò)失效時的輪數(shù)約為498輪，HEED-EELD算法約為751輪，NPPEC算法約為900輪。經(jīng)計算，LEACH算法的不穩(wěn)定周期約為450輪，HEED-EELD算法約為401輪，NPPEC算法約為369輪；所以NPPEC算法的網(wǎng)絡(luò)能耗均衡性更好。此外，NPPEC算法網(wǎng)絡(luò)失效時間較LEACH算法和HEED-EELD算法分別延遲了80.72% 和19.84%，NPPEC算法使全網(wǎng)能量更均衡地被消耗。

圖7 網(wǎng)絡(luò)節(jié)點存活數(shù)量Fig.7 The number of alive network nodes

4 結(jié)論

1)針對深井無線傳感網(wǎng)因節(jié)點能量受限導致網(wǎng)絡(luò)生存時間短與多跳傳輸引起的“熱區(qū)”問題，提出1種基于分區(qū)和能量多路徑的帶狀無線傳感器網(wǎng)絡(luò)多簇首路由算法(NPPEC)。

2)NPPEC算法面向深井帶狀環(huán)境，采用多簇首算法改善“熱區(qū)”問題；將能量多路徑路由思想應用到非均勻分簇算法中，控制路徑通信代價和路徑跳數(shù)，降低網(wǎng)絡(luò)能耗。

3)經(jīng)仿真比較，NPPEC算法網(wǎng)絡(luò)生存時間約為LEACH算法的1.807 2倍、HEED-EELD算法的1.198 4倍，網(wǎng)絡(luò)能量更均衡地被消耗，“熱區(qū)”問題得到改善，網(wǎng)絡(luò)壽命也得以延長。