礦山環(huán)境下基于Ad Hoc網(wǎng)絡(luò)的多路徑QoS路由算法

閆帥領(lǐng)， 張蕾

(衡水學(xué)院 數(shù)學(xué)與計算機學(xué)院， 河北 衡水 053000)

0 引言

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

1 算法原理

1.1 QoS相關(guān)參數(shù)定義

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

B=min{Bij}

(1)

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

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

T=Tpro+Ttra

(2)

Tpro=Tw+Te

(3)

式中：Tpro為節(jié)點轉(zhuǎn)發(fā)數(shù)據(jù)包的時間；Ttra為節(jié)點之間傳輸數(shù)據(jù)包所用時間；Tw為數(shù)據(jù)包在隊列中的等待處理時間；Te為數(shù)據(jù)包的實際處理時間。

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

T=Te+Ttra

(4)

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

E=min{Ei}

(5)

(6)

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

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

(7)

1.2 路由建立

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

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

圖1 區(qū)塊創(chuàng)建Fig.1 Block creation

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

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

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

(5) 鄰居節(jié)點根據(jù)自身記憶路由表中的存儲容量標(biāo)志Isfull決定是否轉(zhuǎn)發(fā)EERQ，當(dāng)Isfull為0時丟棄EERQ，路由查找失敗，否則轉(zhuǎn)步驟(6)。

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

W=ω-ωHd+1,Hd

(8) 判斷鄰居節(jié)點是否為目的節(jié)點，若是轉(zhuǎn)步驟(9)，否則向鄰居節(jié)點轉(zhuǎn)發(fā)EERQ，并轉(zhuǎn)步驟(3)。

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

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

圖2 源節(jié)點區(qū)塊Fig.2 Block of source node

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

表1 多路徑中間節(jié)點的相關(guān)性數(shù)值Table 1 Correlation value of intermediate nodes in multipath

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

1.3 路由維護

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

2 算法仿真

2.1 仿真參數(shù)設(shè)置

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

2.2 仿真結(jié)果分析

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

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

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

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

圖4 誤碼率隨數(shù)據(jù)包發(fā)送速率變化情況Fig.4 Bit error rate variation with packet transmission rate

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

路徑生存能力隨節(jié)點數(shù)變化情況如圖6所示?？煽闯鯩QRA下路徑生存能力隨著節(jié)點數(shù)增多呈上升趨勢，表明節(jié)點數(shù)越多，礦山數(shù)據(jù)傳輸越可靠，主要是由于節(jié)點數(shù)增多更利于形成區(qū)塊鏈且不易斷裂。AODV，DSR算法下路徑生存能力隨著節(jié)點數(shù)增多呈下降趨勢，主要是由于較為密集的節(jié)點數(shù)會使主路徑不斷更新，進而影響數(shù)據(jù)傳輸?shù)目煽啃浴?/p>

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

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

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

3 結(jié)語

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