基于果蠅優化算法的礦井WSN路由協議研究

王越群，湯麗娟

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

1 緒論

礦井工作環境在不斷變化，地面和井下的良好溝通需要依賴持續穩定地從井下接收有效可靠的信息，如巷道中自然因素信息（煤塵、風速等）、礦工信息等數據，事故發生時，地面工作人員才能做出準確地判斷和決定，確保礦工生命安全[1]。無線傳感網便于擴展，十分符合礦井井下的工作環境，既能確保感測消息的及時傳送，又便于網絡布置[2]。因此，WSN也被更多地使用在礦井行業中。

WSN（Wireless Sensor Network）作為一種分布式自組織的實時性網絡，在礦井行業中主要被應用于井下的人員定位，井下環境數據的采集以及安全監控[3]，這些應用都需要信息及時可靠地傳輸。針對國內礦井環境，為保證無線網絡的可靠性，對設計井下無線網絡的路由機制或相關改進機制卻并不多。因此，設計一個高性能的WSN路由協議，對礦井作業十分重要[4]。

2 無線傳感器網絡路由協議

■2.1 礦井WSN路由協議分析

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

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

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

（2）數據傳輸。簇間通訊采用多跳方式將消息傳送至Sink節點。利用最小跳數路由算法，選擇能量最多且相距最遠的節點轉發信息。

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

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

煤礦巷道深長，網絡設計有特殊性，且存在諸多問題，在礦井巷道環境下使用層次路由如LEACH算法的挑戰和有待調整的地方有如下幾點:

(1)協議沒有將候選簇首的剩余能量作為條件因素之一。

(2)簇首的選舉是隨機產生的，由于人員的移動導致節點分布隨機且不均勻，因此簇的范圍大小也就不均勻，容易造成小范圍內有多個簇，某些偏遠位置只有一個大范圍的簇存在，這樣不利于數據的傳輸。

(3)在窄長巷道中，Sink周圍的簇頭傳送自身的融合消息同時，也要負責轉發其他簇頭的消息，能耗負擔過重，容易失效，出現路由“空洞”，改變網絡結構，降低網絡功效。

■2.2 基于能耗均衡的層次路由算法分析

最初的層次路由算法，以LEACH協議最為經典。LEACH算法的分簇機制中，以“輪”為時間單位，在每一輪中，選舉出符合條件的簇首，從公式（1）中可以看出，能否成為簇首主要取決于網絡中簇首數量的比例。

其中，P是簇頭節點數占總節點數的比例；r是已經過的輪數；G是在前1/P輪中沒有充當簇頭節點的集合。

LEACH- mine算法在選舉簇首時，加入了節點剩余能量這一條件，優化了LEACH算法隨機選舉簇首的問題。而線性拓撲和局部能量均衡的分簇路由協議（ LEACHTLLEB），簇首的條件還加入了節點位置信息，在巷道的狹長網絡拓撲結構下，邊緣節點避免成為簇首，有利于信息的轉發。但以上兩種優化算法都沒有改善礦井無線網絡中路由“空洞”問題。 PCEB-MS路由協議（DPCA算法）則通過控制節點功率調節成簇范圍大小，解決路由空洞問題。SOCRP協議以簇首間“局部協商”策略，緩解了數據傳輸的“重疊”問題。

■2.3 礦井WSN路由協議存在的問題

WSN分布在礦井的狹長帶狀空間中，復雜的環境狀況和具有特殊性的空間結構都讓礦井 WSN路由協議的設計具有一些特殊性和挑戰[9]：

（1）能耗不均

單跳通信的傳輸方式已經無法適應礦井巷道的結構特點，若按傳統方式將 Sink節點安置在巷道通風口處，那遠離巷道口的節點由于巷道幾十米甚至數百米的傳輸距離，普通節點無法負荷超長距離的傳輸，所以節點必須通過中間節點轉發數據才能將有效信息傳回到Sink節點，距離Sink節點較近的節點由于多次充當“數據中繼站”，能量負擔遠大于其他節點。因此，多跳方式也存在能量負載不均衡的問題。

（2）數據延遲

長距離的多跳傳輸，距離較遠的節點傳輸數據經歷的跳數越多，引發數據延遲問題。因此，多跳路由機制的關鍵問題是如何實現跳數與鏈路的能耗平衡。

（3）數據傳輸的可靠性和精度

礦井條件惡劣，無線電信號的傳輸會受到嚴重干擾，但是由于礦井對于地下的安全性要求較高，所以對感知數據的精確度也有較高的要求，礦井 WSN路由協議的有一大挑戰就是確保惡劣條件下數據傳輸的可靠性和精度。

（4）可擴展性

隨著節點的失效死亡以及工作面的掘進帶來的新的節點的投入，網絡路由機制的設計要有足夠的可擴展性，網絡的性能不能隨著規模的增大而降低[10]。

■2.4 果蠅優化算法

為了方便研討最短路徑問題，礦井網絡路由可以用帶權值的圖來表示，可以表示為G(N,B)，N表示礦井網絡中的節點數量，B表示通信節點間的通路，Cij表示通路(i,j)的權值,C=C[ij]表示權值矩陣，S,D分別表示源節點和目標節點，Iij表示每個通路的鏈接，定義如下:

如果Iij=1，Ijk=1，則Iik=1，網絡中求最短路徑的問題可以轉化為求目標函數最小值的優化問題，目標函數可表示如下：

■2.5 適應度函數

在路由網絡中，因為會用到鄰居節點來轉發數據，因此鄰居節點的剩余能量因素也要作為優化需要考慮的條件之一。Er、Erb、Erave分別代表節點的剩余能量、鄰居節點的平均剩余能量和節點的平均剩余能量。這樣，單個節點的能量便可由公式（4）表示[11]:能量可分別由：

其中，α，β表示平衡因子，令0＜β＜α，表示更注重節點的剩余能量情況。

公式（5）中，fn(i= 1,2,3,...,n)分別對應路徑中第i個節點的能量平衡值，節點的能量平衡比如公式（6）所示：

節點能量安全平衡比Vsafe=ε，0<ε<0.3。Vsafe是節點能量相較于全網能量比值的安全值，假若節點的能量過低即V＜Vsafe，那么該節點進入保護狀態，不再采集數據和轉發數據。若ε取的值較小時，網絡的初始能量與能耗成反比；反之，取大值。

已知Numnb（i=1,...,n）表示第i個節點的鄰居節點個數，簇內路由選擇考慮節點鄰居節點個數多的節點，在其中優先選擇能量代價較小的節點且鄰居節點數較多的節點作為下一跳轉發節點，保證整體選擇最優路徑，因此用單個節點的鄰居節點數倒數來表征。

在保證節點數量最少的條件下，優化的最短路徑應滿足公式（8）[12]：

利用鄰居節點個數和節點剩余能量代價構造適應度函數，如公式（9）所示：

在開始時刻產生一定數量的果蠅個體，計算每個個體的fitness，比較出最小值，迭代更新果蠅集體的位置和方向，fitness最小值對應的節點，就是對應最佳路徑上的節點。

圖1

■2.6 MRP-FOA算法思想

MRP-FOA算法的設計思路是：簇首節點選舉過程以節點剩余能量和全網能量的比值產生節點隨機數，與閾值比較，平衡全網節點的剩余能量；由于簇間通信鄰居節點承擔轉發的功能，將節點的鄰居節點個數引入作為“度數”平衡因子，利用節點鄰居節點個數確定出最終簇首節點；簇首節點位置應盡量滿足距離區域中心距離最近的要求，由此將節點與區域中心的距離作為相對位置衡量因子引入閾值計算中；穩定傳輸數據時，簇內節點與簇首節點通信，采用多跳與單跳結合的方式，如果簇首節點與節點距離很近，屬于鄰居節點，那么節點直接將數據發送給簇首節點，若相距較遠，則根據FOA_C算法找到的最優路徑依靠其他節點的多跳轉發，將數據發送出去。

3 仿真與分析

仿真參數如表1所示。基于果蠅優化算法的分簇路由協議仿真結果分析如下：

表1 仿真參數表

（1）可靠性比較

圖2中可以看出MRP-FOA協議中基站接收數據包最穩定且數量最多，這是因為本文在設計網絡模型時考慮到礦井巷道監測的獨特性，因此采用等分區間設置多個Sink節點，縮短簇首節點與Sink節點間的距離。

圖2 數據包接收率

(2)死亡節點數量比較

圖3中可以明顯看出失效節點數量隨時間的變化趨勢，MRP-FOA協議死亡節點數量最少，網絡生命周期持續最長（實驗設定90%節點死亡時間為網絡生命周期）。

圖3 死亡節點數量

4 結論

本文優化了簇間通信機制，在簇內普通節點到簇首的路徑選擇上，通過改變步長優化果蠅算法的收斂速度，同時結合簇內節點到簇首歐式距離以及節點能量創造適應度函數，利用改進的果蠅優化算法FOA_C得到簇內節點到簇首的最短路徑，使得穩定傳輸階段，簇內數據信息收集時，節點能耗降低，進而達到整體網絡能耗降低的效果。

無線傳感網在礦井方面的使用已經引起廣泛地關注和討論，本文大量調研了關于礦井無線傳感網層次路由算法的相關研究，針對煤礦井下網絡的特殊結構和層次路由協議的不同應用，進行深入分析和對比各算法的優勢和不足之處，層次路由算法將散落在窄長巷道的傳感器節點分簇，便于這種特殊拓撲結構的網絡構造，針對不同的問題，如能耗、時延等各協議給出了相應的改進策略，但大多是以高能耗為代價，減少時延和保障通信質量，或是為降低時延而增加網絡帶寬的開銷。