Ad hoc 網(wǎng)絡(luò)中基于區(qū)塊鏈技術(shù)的多路徑路由算法研究

閆帥領(lǐng)，程鳳林，周林錦，陳曉軍，彭玲玲

（衡水學(xué)院數(shù)學(xué)與計(jì)算機(jī)學(xué)院 河北 衡水 053000）

0 引言

傳統(tǒng)的Ad hoc 網(wǎng)絡(luò)是一種動(dòng)態(tài)拓?fù)渚W(wǎng)絡(luò)，網(wǎng)絡(luò)內(nèi)的節(jié)點(diǎn)即數(shù)據(jù)的發(fā)送者，同時(shí)充當(dāng)著路由器和接受者的角色。 為了在Ad hoc 網(wǎng)絡(luò)內(nèi)建立穩(wěn)定高質(zhì)量的路由，很多學(xué)者進(jìn)行了一系列的研究，其中樓巧巧和趙知?jiǎng)诺龋?］提出的多跳廣播算法，綜合評價(jià)節(jié)點(diǎn)信息進(jìn)而保證了路由綜合性能的優(yōu)越性；李紅衛(wèi)和陳業(yè)程［2］考慮遠(yuǎn)海無人船的環(huán)境設(shè)計(jì)了以最短路徑為最優(yōu)選擇的組播路由算法進(jìn)而保證了數(shù)據(jù)傳輸?shù)臅r(shí)效性。 Xin 等［3］提出了一種針對飛行Ad Hoc 網(wǎng)絡(luò)的多策略路由算法，該算法具有路由毀壞后快速重建的特點(diǎn)。 以上算法在一方面體現(xiàn)了較好的優(yōu)勢，但是都存在一個(gè)顯著的缺陷。 比如樓巧巧等提出的算法過于追求綜合性能而無法保證特定條件下路由的高穩(wěn)定性和高質(zhì)量性；李紅衛(wèi)和陳業(yè)程［2］提出的算法雖然考慮了環(huán)境卻忽略了節(jié)點(diǎn)的高速移動(dòng)性，容易造成頻繁地更換路由和路由毀壞不可修復(fù)的情況；Xin 等［3］提出的算法有較好的穩(wěn)定性和高質(zhì)量，但是其對環(huán)境針對性太強(qiáng)而無法適合其他場景的推廣。 為此，本文提出的基于區(qū)塊鏈技術(shù)的多路徑QoS 路由算法一方面保證了路由的穩(wěn)定性和高質(zhì)量，同時(shí)也考慮了路由毀壞的修復(fù)和重建。

1 Ad hoc 網(wǎng)絡(luò)區(qū)域P2P 模型的建立

Ad hoc 網(wǎng)絡(luò)區(qū)域是指在網(wǎng)絡(luò)內(nèi)能夠兩兩相互通信的節(jié)點(diǎn)所組成的一個(gè)區(qū)域，而且Ad hoc 網(wǎng)絡(luò)中所有節(jié)點(diǎn)必須屬于一個(gè)區(qū)域且只能屬于一個(gè)區(qū)域，區(qū)域內(nèi)的所有節(jié)點(diǎn)地位平等，即均可與相鄰區(qū)域內(nèi)的節(jié)點(diǎn)進(jìn)行通信［4-5］。 初始化Ad hoc 網(wǎng)絡(luò)，網(wǎng)絡(luò)內(nèi)未進(jìn)入?yún)^(qū)域的節(jié)點(diǎn)間隔（T1）不定時(shí)間發(fā)起區(qū)域請求。 區(qū)域的形成有以下幾步：

（1）Ad hoc 網(wǎng)絡(luò)內(nèi)節(jié)點(diǎn)生成隨機(jī)生成大數(shù)據(jù)編號，向其鄰居節(jié)點(diǎn)發(fā)出隨機(jī)生成大數(shù)據(jù)編號的探測包，并等待鄰居節(jié)點(diǎn)返回的響應(yīng)包。

（2）節(jié)點(diǎn)收到鄰居節(jié)點(diǎn)的探測包后，首先檢查自己的區(qū)域標(biāo)記，如果已經(jīng)標(biāo)記，則忽略該探測包。 否則，返回其響應(yīng)包并同時(shí)標(biāo)記本節(jié)點(diǎn)的區(qū)域標(biāo)記為該大數(shù)據(jù)編號。

（3）過一個(gè)固定周期T2（T2＞T1），節(jié)點(diǎn)收到鄰居節(jié)點(diǎn)返回的響應(yīng)包，則做標(biāo)記確認(rèn)，否則，撤銷區(qū)域標(biāo)記。

圖1 為區(qū)域化的Ad hoc 網(wǎng)絡(luò)示意圖。 在圖1 中整個(gè)Ad hoc 網(wǎng)絡(luò)被劃分成了4 個(gè)區(qū)域，分別為區(qū)域1、區(qū)域2、區(qū)域3、區(qū)域4，在每一個(gè)區(qū)域內(nèi)節(jié)點(diǎn)與節(jié)點(diǎn)之間均可直接進(jìn)行通信，且相鄰區(qū)域內(nèi)的節(jié)點(diǎn)可相互通信。

圖1 區(qū)域化的Ad hoc 網(wǎng)絡(luò)

2 基于區(qū)塊鏈技術(shù)的多路徑路由算法

2.1 路徑生存活力

節(jié)點(diǎn)生存活力是該節(jié)點(diǎn)正常情況下的持續(xù)工作的時(shí)間，該值主要由節(jié)點(diǎn)的移動(dòng)性、連通性和通信距離三個(gè)主要因素決定。 用Eid表示，它是通過該節(jié)點(diǎn)具有最小的連通度β 和電池消耗剩余α 的計(jì)算獲得，可以表示為式（1）所示：

式（1）中μ為一個(gè)平衡因子，根據(jù)節(jié)點(diǎn)的移動(dòng)速度決定，移動(dòng)速度越快該值就越小，反之越大。 在分母加1 是為了防止節(jié)點(diǎn)的β為0 所導(dǎo)致的公式無效情況。β的值為該節(jié)點(diǎn)能量覆蓋下的節(jié)點(diǎn)數(shù)量，如圖2 所示，A 與B 兩個(gè)節(jié)點(diǎn)在節(jié)點(diǎn)C 的能量覆蓋下，而節(jié)點(diǎn)D、E、F 由于距離原因無法與節(jié)點(diǎn)C 進(jìn)行通信，所以節(jié)點(diǎn)C 的連通度β為2。α為節(jié)點(diǎn)的原始滿能量，隨著時(shí)間的推移其能量值不斷減少，所覆蓋的通信半徑也在縮小，那么覆蓋的節(jié)點(diǎn)數(shù)隨之減少，故變化不大。 所以此值能從一定程度上反映節(jié)點(diǎn)的可持續(xù)工作時(shí)間，進(jìn)而可以推理出整個(gè)路徑的生存活力。

圖2 節(jié)點(diǎn)的連通度例圖

路徑的生存活力是本路徑所能存在的最長時(shí)間的參考值E。 E 為路徑中節(jié)點(diǎn)生存活力最小值，則如式（2）所示：

2.2 QoS 參數(shù)計(jì)算

路徑的生存能力反映了路徑的可用性能，生存能力較大的路徑更具有優(yōu)越可用性。 它主要可由時(shí)間延時(shí)，可用帶寬和路徑生存活力來決定。 令路徑的生存能力為M，則M 可以表示為式（3）所示：

式（3）中γ、ξ、δ為調(diào)和系數(shù)，τ為路由生存能力的平衡因子，根據(jù)路徑中數(shù)據(jù)包的探測情況而自行設(shè)定。Bandwidth、T、E分別代表路徑的帶寬，時(shí)間延時(shí)和路徑生存活力，而Bandwidth_B、T_B、E_B分別表示路徑的帶寬，時(shí)間延時(shí)和路徑生存活力的估計(jì)標(biāo)準(zhǔn)值，該值可根據(jù)實(shí)際情況進(jìn)行估計(jì)。

2.3 路由的建立

路由建立的過程是一種由源節(jié)點(diǎn)發(fā)起的通過請求／應(yīng)答的方式［6］。 首先將網(wǎng)絡(luò)區(qū)域化，區(qū)域中的節(jié)點(diǎn)周期性地根據(jù)其QoS 約束競爭主節(jié)點(diǎn)和副節(jié)點(diǎn)；然后將網(wǎng)絡(luò)中區(qū)域中的主副節(jié)點(diǎn)以區(qū)塊的形式不斷上鏈以形成并行區(qū)塊鏈。該過程的最終目的是尋找兩條以目的節(jié)點(diǎn)為終點(diǎn)的穩(wěn)定且高質(zhì)量的路由。 當(dāng)源節(jié)點(diǎn)需要向目的節(jié)點(diǎn)發(fā)送數(shù)據(jù)且源節(jié)點(diǎn)又無到目的節(jié)點(diǎn)的路由時(shí)，源節(jié)點(diǎn)便創(chuàng)建創(chuàng)世區(qū)塊。 如下圖3 所示。 以尋找到達(dá)目的節(jié)點(diǎn)的鏈表。 接著源節(jié)點(diǎn)按照其默克爾樹（Merkle tree）向其臨界點(diǎn)發(fā)送探測包EERQ，從而開啟了目的節(jié)點(diǎn)尋找的過程。

源節(jié)點(diǎn)收到鄰居節(jié)點(diǎn)的正常確認(rèn)包后，檢查其時(shí)間延遲是否在合理的時(shí)間之內(nèi)以及該節(jié)點(diǎn)的最大輸出帶寬是否在合適的區(qū)間，在相鄰本區(qū)域內(nèi)尋找主節(jié)點(diǎn)和備選節(jié)點(diǎn)，區(qū)域內(nèi)的其他節(jié)點(diǎn)作為主副節(jié)點(diǎn)的備用節(jié)點(diǎn)，且周期性地根據(jù)QoS 約束條件競爭替換主副節(jié)點(diǎn)。 一個(gè)區(qū)域視為一個(gè)區(qū)塊，區(qū)塊內(nèi)的節(jié)點(diǎn)通過競爭主節(jié)點(diǎn)獲得該區(qū)塊的優(yōu)先上鏈權(quán)。 而區(qū)域內(nèi)主節(jié)點(diǎn)的性能指標(biāo)為該區(qū)塊與其他區(qū)塊競爭上璉的依據(jù)。 路徑形成的過程為區(qū)塊鏈形成的過程，一旦該區(qū)塊上鏈即為該區(qū)域的主節(jié)點(diǎn)被選為通信路徑中的一個(gè)節(jié)點(diǎn)，而該節(jié)點(diǎn)在通信的過程中會(huì)由于其主節(jié)點(diǎn)地位的喪失而由本區(qū)域內(nèi)的其他節(jié)點(diǎn)進(jìn)行替代，進(jìn)而保證了該數(shù)據(jù)通信線路的穩(wěn)定性。 以圖2 中節(jié)點(diǎn)1 與節(jié)點(diǎn)10 進(jìn)行通信，則路由區(qū)塊鏈形成過程如下：

①區(qū)域1 內(nèi)節(jié)點(diǎn)1 作為源節(jié)點(diǎn)，由源節(jié)點(diǎn)創(chuàng)建原始區(qū)塊。

②由區(qū)域1 的鄰居區(qū)域2 內(nèi)節(jié)點(diǎn)區(qū)塊競爭第一次上鏈，由式（3）計(jì)算節(jié)點(diǎn)的QoS 約束值，然后按照其結(jié)果值按照降序進(jìn)行排序，具有更大QoS 約束值的節(jié)點(diǎn)擔(dān)任本區(qū)域的主節(jié)點(diǎn)，次小值為副節(jié)點(diǎn)，其他節(jié)點(diǎn)均為備選節(jié)點(diǎn)。主節(jié)點(diǎn)獲得優(yōu)先上鏈區(qū)塊。

③按照②所示過程完成其他區(qū)域內(nèi)節(jié)點(diǎn)區(qū)塊的上鏈。整個(gè)路由區(qū)塊鏈形成結(jié)果如圖4 所示。

圖4 路由區(qū)塊鏈

如圖5 所示，節(jié)點(diǎn)1 與節(jié)點(diǎn)10 之間形成的路徑依次為：

圖5 數(shù)據(jù)投包率隨速度變化情況

第一條路徑：節(jié)點(diǎn)1→節(jié)點(diǎn)3→節(jié)點(diǎn)4→節(jié)點(diǎn)10

第二條路徑：節(jié)點(diǎn)1→節(jié)點(diǎn)3→節(jié)點(diǎn)8→節(jié)點(diǎn)10

第三條路徑：節(jié)點(diǎn)1→節(jié)點(diǎn)6→節(jié)點(diǎn)4→節(jié)點(diǎn)10

第四條路徑：節(jié)點(diǎn)1→節(jié)點(diǎn)6→節(jié)點(diǎn)8→節(jié)點(diǎn)10

第五條路徑：節(jié)點(diǎn)1→節(jié)點(diǎn)5→節(jié)點(diǎn)4→節(jié)點(diǎn)10

第六條路徑：節(jié)點(diǎn)1→節(jié)點(diǎn)5→節(jié)點(diǎn)8→節(jié)點(diǎn)10

考慮到QoS 約束問題，路由最大可能地由主副節(jié)點(diǎn)所構(gòu)成，備選節(jié)點(diǎn)可在周期內(nèi)競爭成為主副節(jié)點(diǎn)以保證主副節(jié)點(diǎn)的性能優(yōu)越性。 在圖4 中，節(jié)點(diǎn)3 為區(qū)域2 的主節(jié)點(diǎn)，節(jié)點(diǎn)4 為區(qū)域3 的主節(jié)點(diǎn)。 節(jié)點(diǎn)1 與節(jié)點(diǎn)10 的數(shù)據(jù)傳輸需要經(jīng)過節(jié)點(diǎn)3 和節(jié)點(diǎn)4 的數(shù)據(jù)轉(zhuǎn)發(fā)方可完成，所以上述第一條路徑為最優(yōu)路徑。 但是當(dāng)節(jié)點(diǎn)3 或者節(jié)點(diǎn)4由于移動(dòng)或者能源耗盡等原因失去數(shù)據(jù)轉(zhuǎn)發(fā)能力時(shí)，其對應(yīng)的副節(jié)點(diǎn)便代替其主節(jié)點(diǎn)的功能，所以上述第二、三、四條路徑為最優(yōu)路徑的備選路徑。 故實(shí)際采用的路徑是前四條路徑。

3 仿真實(shí)驗(yàn)

本次仿真采用NS-3 網(wǎng)絡(luò)仿真環(huán)境，部署在虛擬機(jī)上。 并采用多次實(shí)驗(yàn)最后采用排除極值并對正常結(jié)果值平均的辦法進(jìn)行。

網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)是一個(gè)節(jié)點(diǎn)隨機(jī)分布在1 000 m×1 000 m 的平面矩形區(qū)域的網(wǎng)絡(luò)模型，移動(dòng)節(jié)點(diǎn)速度為50 m／s 到100 m／s。 MAC 層采用IEEE 802.11，采用恒定比特率（constant bit rate，CBR）數(shù)據(jù)流，仿真時(shí)間為900 s，其中節(jié)點(diǎn)最大停留時(shí)間變化范圍是0 s、40 s、80 s、120 s、160 s。 節(jié)點(diǎn)數(shù)在對BMQR 和AODV 協(xié)議進(jìn)行模擬性能評估時(shí)，主要考慮移動(dòng)節(jié)點(diǎn)的數(shù)據(jù)報(bào)文投遞率PDF（Packet delivery fraction）的性能參數(shù)。

圖5 為網(wǎng)絡(luò)中所有節(jié)點(diǎn)均為正常節(jié)點(diǎn)的情況下，數(shù)據(jù)包投包率延時(shí)隨速度變化情況。 由圖可知，本文所提出的算法在節(jié)點(diǎn)移動(dòng)速度較AODV 算法表現(xiàn)更優(yōu)，主要原因在于由于EMQR 算法在數(shù)據(jù)的傳輸過程中確保多條路徑工作，具有更加穩(wěn)定的路由。 而AODV 協(xié)議由于不斷重新進(jìn)行路由的建立，無法確保數(shù)據(jù)包的正確投遞。

4 結(jié)語

本文提出的多路徑QoS 路由算法將區(qū)塊鏈技術(shù)與Ad hoc 網(wǎng)絡(luò)很好地進(jìn)行了融合，通過區(qū)域內(nèi)節(jié)點(diǎn)間的競爭機(jī)制自動(dòng)確定路由節(jié)點(diǎn)的選擇，很大程度上保證了路由中節(jié)點(diǎn)的穩(wěn)定性。 仿真實(shí)驗(yàn)中通過與AODV 協(xié)議的對比，可發(fā)現(xiàn)本文提出的算法在節(jié)點(diǎn)移動(dòng)的環(huán)境中，展示出了巨大的優(yōu)勢。 但是由于區(qū)塊鏈技術(shù)的融入，需要進(jìn)行不斷的QoS約束值的計(jì)算，故本算法存在控制開銷較大的問題，以后針對該問題將繼續(xù)展開研究。