基于網絡分區和路徑能耗的深井無線傳感器網絡多簇首路由算法*

2019-02-21 08:55:58余修武梁北孔周利興謝曉永范思柔王宇琴

中國安全生產科學技術 2019年1期

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

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

0 引言

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

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

1 系統模型

1.1 無線通信模型

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

(1)

節點B接收lbit數據所消耗的能量求解如下：

ERx(l,d)=l×Eelec

(2)

式(1)中的限值d0為：

(3)

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

圖1 網絡節點能耗情況Fig.1 Energy consumption of network nodes

1.2 深井巷道帶狀網絡分區模型

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

采用跳數泛洪方式建立網絡分區結構，其主要步驟如下：

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

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

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

消息依照這樣的規律在監測區域擴散，區域內節點隨機分布，且都能獲得對應的分區值，即全網建成了分區結構，如圖2所示。

圖2 深井巷道網絡分區結構Fig.2 Deep mine tunnel network partition structure

2 NPPEC算法

節點根據網絡分區結構獲得與自身位置對應的分區值，該值可應用于簇首競選及數據轉發過程。數據按分區值減少的方向逐跳轉發，路由按分區值增加的方向依次建立，構成帶狀網絡分區結構。該算法分為3階段：簇首競選、簇的形成、能量多路徑路由。

2.1 簇首競選

簇首競選分為主簇首競選和副簇首競選。其中，主簇首負責簇內數據的收集與融合；副簇首負責簇間數據轉發，包括轉發來自其主簇首的數據。

2.1.1 主簇首競選

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

(4)

(5)

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

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

2.1.2 副簇首選取

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

nv=(nall×k-n)×f

(6)

f=aPA{0

(7)

其中，a滿足式(8)：

a1+a2++an=1

(8)

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

同時，改進文獻[15]的簇內節點閾值公式后，進行副簇首的競選。

(9)

2.2 簇的形成

NPPEC算法主簇首的競爭半徑為R，由系統設置。則NPPEC算法成簇結構如圖3所示。

圖3 NPPEC算法成簇結構Fig.3 NPPEC algorithm cluster structure

2.3 能量多路徑路由

簇內所有節點都在其主簇首的競爭范圍內，采用單跳方式進行簇內數據傳輸可減少網絡能耗。多路徑數據轉發，指各副簇首之間的轉發過程，按分區值減小的方向傳輸，采用能量多路徑路由機制，使網絡能量更均衡地消耗。多路徑轉發過程描述如下：

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

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

3)數據從副簇首Nj發出，經副簇首Ni轉發到匯聚節點，路徑能耗值指副簇首Ni的代價值與Nj到Ni間的通信能耗之和，如式(10)所示：

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

(10)

式中：CNj,Ni指數據從副簇首Nj發出，經副簇首Ni轉發到達匯聚節點的代價；Met(Nj,Ni)表示Nj到Ni的通信能耗，計算方法如式(11)所示：

(11)

式中：eNj,Ni指Nj和Ni間直接進行數據轉發的能耗；ENi指Ni的當前能量；x，y是常量。

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

(12)

式中：hNj,Ni指數據從副簇首Nj發出，經副簇首Ni轉發到匯聚節點所需要的平均跳數；λ，μ基于實際情況設定，均大于1。

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

(13)

(14)

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

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

能量多路徑路由進行數據傳輸的流程如圖4所示。

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

3 仿真及結果分析

3.1 參數設置

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

表1 網絡仿真參數Table 1 Network simulation parameters

3.2 仿真結果分析

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

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

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

圖6 網絡節點總能耗Fig.6 Total energy consumption of network nodes

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