礦山環境下基于Ad Hoc網絡的多路徑QoS路由算法

閆帥領， 張蕾

(衡水學院 數學與計算機學院， 河北 衡水 053000)

0 引言

在復雜的礦山環境中數據安全、可靠傳輸困難。目前，針對數據傳輸已開展很多研究。文獻[1]將數據先傳遞到數據中心，再通過數據中心分發。文獻[2]以C/S(Client-Server，服務器-客戶機)工作模式搭建數據傳輸架構，利用專用線路傳輸圖像數據。文獻[3-5]引入云計算以遏制無線數據傳輸對環境的依賴，確保數據傳輸的可靠性。文獻[6]借鑒AODV(Ad Hoc On-Demand Distance Vector Routing，無線自組網按需平面距離向量路由)協議的思想，通過無線傳感器網絡轉發實現數據傳輸。文獻[7]通過分組頭壓縮的改進型DSR(Dynamic Source Routing，動態源路由)算法優化無線網移動通信數據傳輸性能。然而，文獻[1-2]為有線數據傳輸，在礦山特殊環境下不易鋪設線路且施工費用高，另外受天氣影響線路容易產生破壞，導致數據傳輸失敗。文獻[3-5]通過云計算勢必會增加數據處理時間，影響數據傳輸的實時性。文獻[6-7]基于簡單協議生成的路由算法更適用于礦山環境，但文獻[6]未考慮數據傳輸過程中中間節點破壞的情況，文獻[7]以最短路徑作為路由選擇標準，均未解決數據傳輸的準確性問題。因此，本文提出了一種礦山環境下基于Ad Hoc網絡的多路徑QoS路由算法(Multipath QoS Routing Algorithm，MQRA)。該算法在路由建立過程中引入區塊鏈，可防止數據被篡改；通過QoS約束得到多條可用路徑，再根據不同級別標準尋找數據傳輸主路徑和備選路徑，可避免數據丟失。

1 算法原理

1.1 QoS相關參數定義

(1) 路由路徑帶寬。路由路徑帶寬是指整個路由路徑中所有相鄰節點的最小帶寬。

B=min{Bij}

(1)

式中：B為路由路徑帶寬；Bij為路由中相鄰節點i，j(i，j=1，2，…，n，n為網絡中節點數，i≠j)之間的通信鏈路帶寬。

(2) 路徑時間延遲。數據包從源節點到達目的節點所需時間為路徑時間延遲。令網絡中所有節點具有相同的處理能力和信道帶寬，且所用的無線信道是對稱的，路由請求探測包、目的節點的響應包及數據包的大小相等，則路徑時間延遲為

T=Tpro+Ttra

(2)

Tpro=Tw+Te

(3)

式中：Tpro為節點轉發數據包的時間；Ttra為節點之間傳輸數據包所用時間；Tw為數據包在隊列中的等待處理時間；Te為數據包的實際處理時間。

由于數據包在隊列中的等待處理時間很短，可忽略不計,所以根據式(2)和式(3)可得

T=Te+Ttra

(4)

(3) 路徑生存活力。路徑生存活力是指路徑中節點最小存活時間。

E=min{Ei}

(5)

(6)

式中：E為路徑生存活力；Ei為路徑中節點i存活時間；θ為節點能源；ω為節點連通度；α為節點存活的平衡因子。

(4)路徑生存能力。路徑生存能力反映了路徑的可用性，主要由路由路徑帶寬、路徑時間延遲和路徑生存活力決定。

(7)

1.2 路由建立

礦山環境下的路由建立是一種由源節點發起的通過中間轉發設備到達目的節點的過程。首先將源節點、中間節點及目的節點封裝為獨立的區塊，然后利用請求/應答方式將各個區塊進行有效連接，最后形成1條由源節點到目的節點的區塊鏈。路由建立具體步驟如下。

(1) 節點通過周期性地向鄰居節點廣播探測包EERQ而逐漸形成穩定的區塊，如圖1所示。Pre-point為上一節點地址，由于源節點為創世節點而不存在上一節點，所以源節點的Pre-point設置為null；Merkle tree保存源節點的鄰居節點；ID為本節點地址。

圖1 區塊創建Fig.1 Block creation

(2) 源節點向鄰居節點發送EERQ(含無限大初始路徑生存活力)，并設置有效時間域τ。當傳輸過程中EERQ的時間延遲Tζ大于τ，則EERQ將由于尋找路徑的時間延遲過長而失效。

(3) 鄰居節點收到EERQ后，開啟處理數據包定時器并檢查是否為初次收到該包，若是則回復正常確認包CEERP(主要包含EERQ的時間延遲Tζ和路由路徑帶寬B)并提出節點上鏈要求，否則轉步驟(5)。

(4) 節點收到鄰居節點的正常確認包CEERP后，檢查Tζ是否大于τ，若是則丟棄CEERP，否則判斷鄰居節點的路由路徑帶寬B是否在常規區間，若是則同意鄰居節點上鏈，否則拒絕鄰居節點上鏈,并對鄰居節點的可疑性進行定時檢測。

(5) 鄰居節點根據自身記憶路由表中的存儲容量標志Isfull決定是否轉發EERQ，當Isfull為0時丟棄EERQ，路由查找失敗，否則轉步驟(6)。

(6) 鄰居節點根據式(6)計算自身的存活時間Ei，并將計算結果同探測包EERQ中的路徑生存活力E進行比較，如果Ei

W=ω-ωHd+1,Hd

(8) 判斷鄰居節點是否為目的節點，若是轉步驟(9)，否則向鄰居節點轉發EERQ，并轉步驟(3)。

(9) 目的節點按照區塊鏈路徑向源節點傳輸公鑰信息，源節點通過目的節點的公鑰對所需傳輸信息進行加密。

路由查找成功后，源節點區塊內保存了所有源節點到目的節點的節點檢索過程。假設源節點為S，目的節點為D，節點2和節點6為惡意節點，節點4和節點8為不滿足QoS約束條件節點，源節點區塊如圖2所示。

圖2 源節點區塊Fig.2 Block of source node

由圖2可知，在惡意節點和不滿足QoS約束條件節點處將不再進行路徑探測，即節點2、節點4、節點6和節點8均失去了區塊鏈的連接。最終得到3條可用路徑，分別為R1：S—1—7—11—D，R2：S—1—7—12—13—D和R3：S—3—9—14—D。將這3條路徑以到達的先后次序記錄在源節點的記憶路由表中，計算中間節點的相關性數值，見表1。

表1 多路徑中間節點的相關性數值Table 1 Correlation value of intermediate nodes in multipath

以中間節點的相關性數值之和作為第一路徑選擇標準，相關性數值之和越小，表明路徑相關性越小。以路徑長度作為第二路徑選擇標準，路徑越短，鏈路越穩定，網絡的控制開銷越小。以路徑形成先后順序為第三路徑選擇標準，越早形成的路徑對應的時間延遲越小。R1路徑最先形成且需要經過3個中間節點；R2路徑在R1路徑之后形成，R2路徑中存在4個中間節點且前2個與R1重復(重復則相關性數值加1)；最后形成的R3路徑與R1，R2路徑的中間節點均不相同。因此選擇路徑相關性小、鏈路穩定、時間延遲小的R1，R3作為路由路徑，其中R1為數據傳輸主路徑，R3為數據傳輸備選路徑。

1.3 路由維護

在礦山環境下使用Ad Hoc網絡對信息傳輸盡管有多條QoS路徑保證[8-10]，但仍可能由于中間節點移動、帶寬不足、傳輸超時等原因使鏈路連接失敗[11-14]。因此，本文主要從3個方面對路由進行維護：① 由于在初次路由查找過程中采用了區塊鏈思想，所以每個中間節點均保留其鄰居節點的信息，可通過查詢路徑出現斷裂處的上一個節點的路由表，使用相鄰節點替代，進而恢復路由。② 備選路徑并不是在主路徑失效后啟用，而是在主路徑的可靠性評估下降到一定程度后即可啟用。③ 在源節點處重新發起路由查找。

2 算法仿真

2.1 仿真參數設置

采用NS-3網絡模擬礦山環境，從誤碼率和路徑生存能力2個方面對MQRA與經典的AODV算法和DSR算法進行對比。設置節點數為10～100個，隨機分布在1 000 m×1 000 m范圍內，節點通信范圍為50 m，節點移動速度為0～16 m/s，數據包發送速率為0～35個/s，仿真時間為900 s。模擬礦山網絡中存在至少1個女巫攻擊節點，當節點數達30個后加入1個能源受限節點、達40個后加入1個黑洞節點、達50個后加入1個DoS攻擊節點。

2.2 仿真結果分析

在固定節點移動速度(10 m/s)的條件下，數據傳輸誤碼率隨網絡中節點數變化情況如圖3所示?？煽闯鯩QRA下誤碼率隨著節點數增多先增大后平緩減小。這主要是由于隨著節點數增多，網絡中惡意節點增加，而區塊鏈在構建時會出現控制包受到攻擊而失效的情況，所以誤碼率偏大；一旦區塊鏈網絡形成，數據傳輸進入穩定時期，數據將會得到較好的保護，出現的誤碼主要來源于對最初探測包的攻擊，因此誤碼率持續減小。AODV，DSR算法由于未對傳輸的數據包進行保護，所以整體上隨著惡意節點增多，會引起較多的數據包丟失，造成誤碼率增大。

圖3 誤碼率隨節點數變化情況Fig.3 Bit error rate variation with the number of nodes

網絡中存在50個常規節點和4個惡意節點的條件下，誤碼率隨數據包發送速率變化情況如圖4所示?？煽闯鯩QRA下誤碼率隨著數據包發送速率提高呈逐漸減小趨勢。主要原因為在最初的路由建立過程中，數據進行了區塊封裝操作，而在該過程中當數據包發送速率較慢則會出現較多的控制包被攻擊而丟失的情況；隨著數據包發送速率提高，區塊鏈的校驗功能變得完備，對數據包的保護能力提高，誤碼率不斷減小。AODV，DSR算法下誤碼率最初由于數據包發送速率較慢出現了短暫減小，主要是由于惡意節點此時并未開始對數據包進行碰撞攻擊，但當數據包發送速率較高時，傳輸的數據包必然會遭遇惡意節點攻擊，且沒有數據防護措施，造成誤碼率增大。

誤碼率隨節點移動速度變化情況如圖5所示?？煽闯鯩QRA下誤碼率隨著節點移動速度增大先增大再減小，主要原因在于節點移動速度較小時出現了2條路徑同時斷裂的情況，造成較多數據包丟失，而之后隨著節點移動速度增大，可快速恢復2條到達目的節點的路徑。AODV，DSR算法下誤碼率明顯偏大，主要因為數據包在傳輸過程中受路徑斷裂及惡意節點攻擊影響而大量丟失，并且隨著節點移動速度越大，數據包丟失越嚴重。

圖4 誤碼率隨數據包發送速率變化情況Fig.4 Bit error rate variation with packet transmission rate

圖5 誤碼率隨節點移動速度變化情況Fig.5 Bit error rate variation with node movement speed

路徑生存能力隨節點數變化情況如圖6所示。可看出MQRA下路徑生存能力隨著節點數增多呈上升趨勢，表明節點數越多，礦山數據傳輸越可靠，主要是由于節點數增多更利于形成區塊鏈且不易斷裂。AODV，DSR算法下路徑生存能力隨著節點數增多呈下降趨勢，主要是由于較為密集的節點數會使主路徑不斷更新，進而影響數據傳輸的可靠性。

圖6 路徑生存能力隨節點數變化情況Fig.6 Path viability variation with the number of nodes

路徑生存能力隨數據包發送速率變化情況如圖7所示。可看出3種算法下路徑生存能力隨著數據包發送速率增加均有所下降，這是由于較快的數據包發送速率導致數據包傳輸不及時。但MQRA下路徑生存能力與AODV，DSR算法下相比下降較為緩慢，主要原因在于區塊鏈的使用確保了路徑的可持續性，在路徑建立初期便排除了可能出問題的節點。

圖7 路徑生存能力隨數據包發送速率變化情況Fig.7 Path viability variation with packet transmission rate

3 結語

MQRA引入了區塊鏈思想:首先對節點進行區塊化封裝，使各節點利用Merkle tree維護其鄰居節點；然后根據鄰居節點的時間延遲和存活時間更新路徑生存活力并進行區塊連接；最后依次以中間節點相關性數值之和、路徑長度、路徑形成先后順序作為路徑選擇標準，篩選數據傳輸主路徑和備選路徑。仿真結果表明，在不同的節點數、數據包發送速率、節點移動速度情況下，該算法相比AODV，DSR算法具有較低的誤碼率和較好的路徑生存能力，可有效保證數據傳輸的完整性和準確性。