Mesh網(wǎng)絡(luò)中基于效用轉(zhuǎn)發(fā)的路由恢復(fù)算法

康巧琴，袁 丁，嚴(yán) 清，楊 霞

(四川師范大學(xué) 計算機科學(xué)學(xué)院，四川 成都 610101)

0 引 言

無線Mesh網(wǎng)絡(luò)(wireless mesh networks，WMNs)[1,2]是一種特殊的Ad Hoc網(wǎng)絡(luò)[3]，由于節(jié)點頻繁移動，內(nèi)存和能量等資源的有限，以及基于節(jié)點自身的原因，導(dǎo)致網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)不斷變化。因此，提供高質(zhì)量高效率通信的路由協(xié)議是確保網(wǎng)絡(luò)正確運行的關(guān)鍵。

WMNs路由協(xié)議的研究集中于：一方面考慮網(wǎng)絡(luò)節(jié)點的移動性，選擇最優(yōu)的備選隊列和下一跳轉(zhuǎn)發(fā)節(jié)點；另一方面當(dāng)網(wǎng)絡(luò)中的節(jié)點進(jìn)行數(shù)據(jù)交互之后，利用網(wǎng)絡(luò)編碼和機會路由以及兩者的結(jié)合使節(jié)點獲得更多數(shù)據(jù)轉(zhuǎn)發(fā)的可能性，減少不必要的開銷。在此過程中，WMNs中的節(jié)點在進(jìn)行數(shù)據(jù)轉(zhuǎn)發(fā)時，形成了WMNs特有的store-carry-and-forward通信模式。如Epidemic路由協(xié)議[4,5]，即傳染路由，該路由協(xié)議的傳遞率相對來說較高，并且傳輸時延也較小；缺點是其適應(yīng)性較差，并且傳遞較多的副本會消耗更多的網(wǎng)絡(luò)資源。Prophet路由協(xié)議[6,7]，利用節(jié)點之間的歷史相遇情況，計算每個節(jié)點傳輸數(shù)據(jù)的概率大小，選擇概率相對較大的節(jié)點作為下一跳轉(zhuǎn)發(fā)節(jié)點，減少了數(shù)據(jù)包的重傳次數(shù)，因此減少了資源的浪費，但并不適用于大部分網(wǎng)絡(luò)環(huán)境。而Spray-And-Wait路由算法[8,9]可以降低消息在網(wǎng)絡(luò)中的復(fù)制份數(shù)；但是若節(jié)點數(shù)限制在較小的移動范圍內(nèi)，或者節(jié)點之間有較強的關(guān)聯(lián)性，那么該路由協(xié)議的性能會有所下降。王博等[10]提出基于效用轉(zhuǎn)發(fā)的自適應(yīng)機會路由方案(簡稱URD)，利用節(jié)點之間歷史交互信息，計算節(jié)點的效用值并選擇效用值較大的節(jié)點作為下一跳轉(zhuǎn)發(fā)節(jié)點。優(yōu)點是提高了數(shù)據(jù)包的轉(zhuǎn)發(fā)效率，減少了資源的消耗，不足之處是較適用于理想狀態(tài)，而在實際的網(wǎng)絡(luò)環(huán)境中，由于節(jié)點不斷移動，以及節(jié)點自身資源的有限，很難保證節(jié)點之間鏈路一直連通，尤其是在數(shù)據(jù)傳輸率較高的鏈路中，當(dāng)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)發(fā)生變化時，該算法的性能有所下降。本文提出了一種基于效用轉(zhuǎn)發(fā)的路由快速恢復(fù)算法(簡稱URM)，在計算效用值[11-14]時，考慮影響效用值的各因素所占的權(quán)重不同這一特點，動態(tài)獲取權(quán)重值，從而使算法能更好適應(yīng)真實的網(wǎng)絡(luò)環(huán)境。同時綜合網(wǎng)絡(luò)時延，節(jié)點的效用值和節(jié)點對之間的跳數(shù)，選擇最優(yōu)的下一跳轉(zhuǎn)發(fā)節(jié)點，減少了時延值的增加和資源的浪費。

1 效用轉(zhuǎn)發(fā)模型

1.1 模型假設(shè)

通常意義上的WMNs模型很難用以往的G=(V,>E)的形式來表示，其中V是網(wǎng)絡(luò)中節(jié)點的集合，E為邊集。節(jié)點的高速移動性，導(dǎo)致網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)不斷變化，節(jié)點與節(jié)點之間邊的連接不夠穩(wěn)定。隨著節(jié)點之間不斷進(jìn)行數(shù)據(jù)交互，節(jié)點之間存在著某種特定且相對穩(wěn)定的社會關(guān)系和極強的規(guī)律性，而找到這樣的關(guān)系，對于路由協(xié)議的研究很有幫助。為了便于形象的描述本文的研究過程和分析，將做出如下的假設(shè)：

(1)G=(V,>E)為網(wǎng)絡(luò)的拓?fù)鋱D，由N個節(jié)點構(gòu)成，其中V為網(wǎng)絡(luò)中的節(jié)點集合，E為定義在節(jié)點之間邊的集合。

(2)節(jié)點u,v∈V，當(dāng)節(jié)點u，v之間進(jìn)行數(shù)據(jù)傳輸時，鏈路eu,v∈E是雙向的。在復(fù)雜的網(wǎng)絡(luò)拓?fù)鋱D中，由于網(wǎng)絡(luò)環(huán)境的不同，在不同的時刻，鏈路eu,v處于不穩(wěn)定狀態(tài)，隨時可能不連通。

(3)網(wǎng)絡(luò)拓?fù)溆啥鄠€節(jié)點組成，分為不同的簇塊，每個簇塊有各自的割點和割邊，刪除了割點或者割邊，網(wǎng)絡(luò)拓?fù)鋭t分為若干個不同的小的簇塊。

(4)每個節(jié)點的緩存空間大小是一樣的，每個簇塊內(nèi)節(jié)點分配的個數(shù)也一樣。

1.2 模型的定義

圖1至圖3是某時刻的部分網(wǎng)絡(luò)拓?fù)鋱D，由4個簇塊組成，其中節(jié)點3，5，9，B分別作為各簇塊的割點，邊3-B，3-5，5-9和B-9作為簇塊之間的割邊。此時節(jié)點S要與節(jié)點D取得通信，則需要經(jīng)過多個簇塊，經(jīng)過多個節(jié)點的轉(zhuǎn)發(fā)。那么在節(jié)點不斷移動的情況下，下一跳轉(zhuǎn)發(fā)節(jié)點的選擇至關(guān)重要。

圖1 t1時刻

圖2 t2時刻

圖3 t3時刻

顯然，節(jié)點S和D之間沒有直接的連通通道。為了選擇合適的轉(zhuǎn)發(fā)節(jié)點，首先節(jié)點S在其所在的簇塊中，會將數(shù)據(jù)分組轉(zhuǎn)發(fā)給節(jié)點3，再將數(shù)據(jù)發(fā)送給節(jié)點B或節(jié)點5，最后將數(shù)據(jù)轉(zhuǎn)發(fā)給節(jié)點9，選擇節(jié)點3，5，9和B的原因是這些節(jié)點作為簇塊的割點。但是當(dāng)前存在兩個問題：

第一，由于網(wǎng)絡(luò)中的節(jié)點在不斷地移動，各個簇塊中節(jié)點的位置不一定一直保持在原本的簇塊中，很有可能移動到其它的簇塊。比如以下的情況：

第一種情況。如圖2所示，節(jié)點3在第一個簇塊中時，若其將數(shù)據(jù)發(fā)送給位于第二個簇塊中的節(jié)點B，此時節(jié)點3移動到第二個簇塊中。這種情況下，對于下一步數(shù)據(jù)的轉(zhuǎn)發(fā)沒有很大影響，節(jié)點B將數(shù)據(jù)轉(zhuǎn)發(fā)給節(jié)點9即可，再將數(shù)據(jù)直接轉(zhuǎn)發(fā)給同一個簇塊的節(jié)點D，本次數(shù)據(jù)的第一次傳輸完成，此過程體現(xiàn)了機會網(wǎng)絡(luò)中的“存儲—攜帶—轉(zhuǎn)發(fā)”機制[15]，如圖4所示。

圖4 節(jié)點間數(shù)據(jù)包的收發(fā)流程

第二種情況。如圖3所示，假如節(jié)點B和節(jié)點9移動至第三個簇塊中，節(jié)點A移動至第四個簇塊中，此時第四個簇塊沒有割點，而節(jié)點B在第三個簇塊中。節(jié)點B若要將數(shù)據(jù)轉(zhuǎn)發(fā)給目的節(jié)點，則需要重新尋找轉(zhuǎn)發(fā)節(jié)點，那么找到合適的轉(zhuǎn)發(fā)節(jié)點成為重點。

第二，利用簇塊之間的割點作為轉(zhuǎn)發(fā)節(jié)點，除了可以在某種程度上提高數(shù)據(jù)的轉(zhuǎn)發(fā)效率之外。一方面因為割點頻繁轉(zhuǎn)發(fā)數(shù)據(jù)，容易導(dǎo)致網(wǎng)絡(luò)擁塞，數(shù)據(jù)分組的丟失以及傳輸次數(shù)的增加；另一方面由于割點自身資源有限，導(dǎo)致其失效也極有可能。

綜上，利用節(jié)點之間數(shù)據(jù)轉(zhuǎn)發(fā)的歷史信息，從多角度定義節(jié)點與節(jié)點之間的效用值，并且結(jié)合時延開銷以及節(jié)點之間跳數(shù)的計算，選擇備選隊列以及最佳下一跳轉(zhuǎn)發(fā)節(jié)點。給出以下定義請參見文獻(xiàn)[10]。

定義1節(jié)點中心度，表示為CE(m)。

定義2節(jié)點頻繁度，表示為FP(m,n)。

定義3節(jié)點親密度，表示為CP(m,n)。

定義4節(jié)點新近度，表示為RP(m,n)。

定義5節(jié)點關(guān)聯(lián)度，表示為AP(m,n)。

定義6節(jié)點相似度，表示為Sim(m,n)。

定義7節(jié)點移動連通度，表示為MC(m)。

1.3 效用值各權(quán)重的確定

基于節(jié)點之間數(shù)據(jù)交互的歷史數(shù)據(jù)，令當(dāng)前時刻節(jié)點m到達(dá)目的節(jié)點d的總體效用值U(m,>d)[10]的具體計算公式如下

U(m,d)=αAP(m,d)+βSim(m,d)+γ(CE(m)+MC(m))

(1)

上述公式中的α、β和γ是權(quán)重因子，并且α+β+γ=1。由于網(wǎng)絡(luò)不斷變化，惡意交互行為的存在，以及網(wǎng)絡(luò)自身因素帶來較大的誤差率，所以在不同時刻效用值的各參數(shù)所占的權(quán)重不同。顯然，0≤U(m,>d)≤1。當(dāng)節(jié)點與節(jié)點之間第一次通信時，由于各節(jié)點之間沒有數(shù)據(jù)交互的歷史信息，節(jié)點結(jié)合自身簇塊內(nèi)的中心度計算各自的效用值，即α=β=0，γ=1；隨著節(jié)點之間不斷通信，增加關(guān)聯(lián)度的計算；一段時間過后，節(jié)點之間的通信有了一定的規(guī)律，節(jié)點的利用率也更大，形成更有效的通信數(shù)據(jù)，增加節(jié)點的相似度和移動連通度的計算。此外，考慮受到節(jié)點自身網(wǎng)絡(luò)資源以及網(wǎng)絡(luò)拓?fù)鋭討B(tài)變化等因素的影響，設(shè)置無法正常工作的節(jié)點效用值為0。

為了體現(xiàn)效用值計算的主觀性，在確定3個權(quán)重系數(shù)時，由于中心度用于描述一個簇塊內(nèi)節(jié)點之間的聯(lián)通程度，不能說明簇塊之間節(jié)點的聯(lián)通性；關(guān)聯(lián)度描述需要進(jìn)行數(shù)據(jù)交互的節(jié)點之間的聯(lián)通程度，而并未說明沒有進(jìn)行數(shù)據(jù)交互的節(jié)點之間的聯(lián)通程度，因此無法完整地體現(xiàn)網(wǎng)絡(luò)的穩(wěn)定性能；移動連通度描述網(wǎng)絡(luò)動態(tài)變化的程度，增加或者減少的節(jié)點越多，說明節(jié)點轉(zhuǎn)發(fā)數(shù)據(jù)的可能性越大，但網(wǎng)絡(luò)的穩(wěn)定性越不好；而相似度描述兩個節(jié)點之間通信的公有鄰居節(jié)點集，相似度越高，則說明節(jié)點進(jìn)行下一次數(shù)據(jù)傳輸經(jīng)過公有節(jié)點的概率越大。

綜上，相似度不僅描述了節(jié)點的社會屬性[16,17]，而且能逐漸區(qū)分出節(jié)點之間相互合作性能的高低，以及節(jié)點之間通信鏈路穩(wěn)定性能的高低，從而在效用值的計算中，相似度對效用值的貢獻(xiàn)相對較大。在不同的情況下，節(jié)點之間的接觸頻率和連接時間各不相同，節(jié)點會偏重不同的社會屬性度量和效用值。為了使計算的結(jié)果更加符合實際的網(wǎng)絡(luò)環(huán)境，考慮假設(shè)β=1/3，然后利用不同節(jié)點對中心度，移動連通度和關(guān)聯(lián)度的偏重程度來動態(tài)確定α和γ。具體計算過程如下

α=AP(m,d)*(1-β)/AP(m,d)+(CE(m)+MC(m))

(2)

γ=(CE(m)+MC(m))*(1-β)/AP(m,d)+ (CE(m)+MC(m))

(3)

2 URM路由算法

在WMNs網(wǎng)絡(luò)中，根據(jù)節(jié)點之間的歷史交互信息，實時收集節(jié)點的移動情況并且更新節(jié)點本地的數(shù)據(jù)信息，結(jié)合節(jié)點自身緩存中的數(shù)據(jù)，從而計算各節(jié)點的效用值和時延值。URM路由算法包括3個部分：節(jié)點本地緩存的更新，節(jié)點的效用值、時延值的計算以及數(shù)據(jù)分組的轉(zhuǎn)發(fā)。

第一個部分，節(jié)點本地緩存的更新。節(jié)點第一次通信，需要向所有鄰居節(jié)點廣播Hello數(shù)據(jù)包，在有效的TTL時間內(nèi)，如果收到鄰居節(jié)點的Response包，那么說明該鄰居節(jié)點是有效的；同時在Response包中，包括鄰居節(jié)點的私有信息，當(dāng)前節(jié)點就將鄰居節(jié)點的信息添加到自己的本地緩存中；若不是第一次通信，則當(dāng)鄰居節(jié)點位置發(fā)生改變時，當(dāng)前節(jié)點需要更新鄰居節(jié)點的位置信息。在下次轉(zhuǎn)發(fā)數(shù)據(jù)時，直接查找當(dāng)前節(jié)點的本地緩存，減少不必要的時延開銷。因此在當(dāng)前節(jié)點收到的數(shù)據(jù)包中，鄰居節(jié)點私有信息的獲取，將成為當(dāng)前節(jié)點進(jìn)行第一次的通信最主要的依據(jù)。

第二個部分，節(jié)點的效用值、時延值的計算。在數(shù)據(jù)包的轉(zhuǎn)發(fā)過程中，主要包括兩個部分，一是備選隊列的選擇，一是下一跳轉(zhuǎn)發(fā)節(jié)點的選擇。本文主要考慮3個方面：節(jié)點轉(zhuǎn)發(fā)數(shù)據(jù)的時延值，效用值以及跳數(shù)的計算。其中，時延值的計算包括節(jié)點在等待通信鏈路處于空閑狀態(tài)的時間，鏈路處于擁擠狀態(tài)的時間以及節(jié)點在進(jìn)行通信時的預(yù)熱時間。在本地緩存中，節(jié)點會記錄當(dāng)前節(jié)點與其它節(jié)點之間的跳數(shù)，如果兩個消息的跳數(shù)都小于或者大于閾值，則選擇跳數(shù)較小的節(jié)點作為轉(zhuǎn)發(fā)節(jié)點；若其中一個的跳數(shù)小于閾值，另一個的跳數(shù)大于閾值，則選擇跳數(shù)小于閾值的節(jié)點。

如算法1所示，在計算節(jié)點之間的效用值時，由于在不同時刻下節(jié)點的位置和通信情況不同，所以節(jié)點參數(shù)的取值是一個動態(tài)變量。利用本地緩存中的數(shù)據(jù)，動態(tài)計算參數(shù)的值，使之更符合實際情況。

算法1：UtilityComputing Algorithm

//計算節(jié)點m與鄰居節(jié)點d之間的效用值

(1)if 節(jié)點之間首次通信,節(jié)點m沒有與節(jié)點d的歷史交互信息

(2)//計算節(jié)點的中心度

(3)節(jié)點m利用其所在的簇塊中與其它節(jié)點的聯(lián)通程度計算節(jié)點的中心度CE(m)

(4)在周期時間T內(nèi),節(jié)點獲取當(dāng)前簇塊內(nèi)的歷史信息

(5)if 沒有與節(jié)點d相關(guān)的數(shù)據(jù)交互信息 then

(6){

(7) AP(m,>d)←0

(8) Sim(m,>d)←0

(9) MC(m,>d)←0

(10)}

(11)else 節(jié)點m有與節(jié)點d的歷史數(shù)據(jù)交互信息

(12){

(13) //(1)計算節(jié)點m和d之間的關(guān)聯(lián)度[10]

(14) 獲取節(jié)點m與節(jié)點d最近一次建立連接的時間，計算節(jié)點m和節(jié)點d的關(guān)聯(lián)度AP(m,>d)

(15) AP(m,>d)←FP(m,>d)+CP(m,>d)+RP(m,>d)

(16) //(2)計算節(jié)點m與d的移動連通度

(17) 獲取本地緩存中該周期時間T內(nèi),鄰居節(jié)點表的數(shù)據(jù),計算節(jié)點m與節(jié)點d的移動連通度MC(m)

(18) //(3)計算節(jié)點m與d的相似度

(19) 獲取本地緩存中節(jié)點m與節(jié)點d的公有鄰居節(jié)點集,得出公有鄰居節(jié)點數(shù),計算節(jié)點m與節(jié)點d的相似度Sim(m,>d)

(20) //(4)計算節(jié)點的效用值U(m,>d)

(21) if 節(jié)點m與節(jié)點d之間是第一次通信

(22) {

(23) U(m,>d)←CE(m)

(24) }

(25) else

(26) {

(27) 令β=1/3

(28) 利用上述計算的節(jié)點的關(guān)聯(lián)度,中心度和移動連通度,計算α和γ

(29)α←AP(m,d)*(1-β)/AP(m,d)+(CE(m)+MC(m))

(30)γ←(CE(m)+MC(m))*(1-β)/AP(m,d)+(CE(m)+MC(m))

(31) U(m,d)←αAP(m,d)+βSim(m,d)+γ(CE(m,d)+MC(m,d))

(32) end if

(33) }

(34) end if

(35) }

第三個部分，數(shù)據(jù)分組的轉(zhuǎn)發(fā)。首先利用節(jié)點之間的跳數(shù)和效用值來選擇備選隊列，再利用節(jié)點數(shù)據(jù)轉(zhuǎn)發(fā)的時延值、效用值和跳數(shù)選擇下一跳轉(zhuǎn)發(fā)節(jié)點。具體如算法2所示：

算法2：DataForwarding Algorithm

(1)獲取節(jié)點本地緩存的數(shù)據(jù)，包括節(jié)點在等待通信鏈路的時間，鏈路處于擁擠狀態(tài)的時間和節(jié)點間通信之前的預(yù)熱時間。

(2)計算節(jié)點總的時延值

總的時延值=等待通信鏈路的時間+鏈路處于擁擠狀態(tài)的時間+節(jié)點通信之前的預(yù)熱時間

(3)按照節(jié)點的跳數(shù)和效用值對鄰居節(jié)點進(jìn)行排序

(4)比較節(jié)點的時延值、效用值和跳數(shù)的大小。

(5)在當(dāng)前的鄰居節(jié)點的隊列中，綜合3個因素，選擇最優(yōu)的節(jié)點作為下一跳轉(zhuǎn)發(fā)節(jié)點。

3 仿真實驗與分析

3.1 仿真環(huán)境的建立

本文使用ONE仿真(opportunistic network environment simulator)[18]模擬系統(tǒng)作為本次模擬的實驗平臺。ONE是芬蘭赫爾辛基大學(xué)用Java編寫的開源軟件，是一個機會網(wǎng)絡(luò)環(huán)境模擬器，現(xiàn)在最多的將其應(yīng)用于時延容忍網(wǎng)絡(luò)模擬網(wǎng)絡(luò)的真實工作情況。

基于以上的實驗環(huán)境，做出平臺中的某些參數(shù)的假設(shè)，見表1。

表1 實驗平臺的參數(shù)設(shè)置

3.2 實驗參數(shù)

對于實驗中所用到的對比參數(shù)：節(jié)點的平均占用率、節(jié)點之間轉(zhuǎn)發(fā)數(shù)據(jù)的平均跳數(shù)、端到端的平均時延、節(jié)點預(yù)測數(shù)據(jù)包傳遞的可能性以及數(shù)據(jù)分組收發(fā)的成功率，進(jìn)行如下的說明：

(1)平均緩存占用率(average node cache utilization)：節(jié)點所利用的緩存大小與總的緩存空間之間的平均比值；

(2)數(shù)據(jù)轉(zhuǎn)發(fā)的平均跳數(shù)(average hot count)：節(jié)點之間保持?jǐn)?shù)據(jù)交互的平均跳數(shù)，跳數(shù)越少，說明當(dāng)前節(jié)點所對應(yīng)的鄰居節(jié)點作為下一跳的幾率更大，并且所花的時間越少；

(3)端到端的平均時延[10](average end-to-end delay)：節(jié)點之間通信的平均時間；

(4)數(shù)據(jù)包轉(zhuǎn)發(fā)的平均可能性(average probability of packet forwarding)：預(yù)測節(jié)點作為下一跳轉(zhuǎn)發(fā)節(jié)點傳輸數(shù)據(jù)的可能性；

(5)數(shù)據(jù)包收發(fā)的平均成功率(the transceiver success rate of data packets)：發(fā)送的數(shù)據(jù)包的數(shù)量和接收到的數(shù)據(jù)包數(shù)量的比例。

3.3 仿真實驗結(jié)果分析

3.3.1 不同路由協(xié)議的對比

本文選擇隨機路徑移動模型(random waypoint movement modal，RWP)作為節(jié)點的移動方式，并進(jìn)行對比分析：

(1)平均緩存占用率

由圖5可知，隨著仿真時間的增加，5種協(xié)議的節(jié)點緩存占用率都在不斷增加。比較而言，URD和URM協(xié)議的緩存占用率相對較低，并且URM的節(jié)點緩存占用率的增加相對趨于平穩(wěn)。Epidemic和Spray-And-Wait協(xié)議相對較高，前者以洪泛的方式，只要有機會，就將數(shù)據(jù)轉(zhuǎn)發(fā)給鄰居節(jié)點，因此產(chǎn)生太多消息副本，占用了較大的存儲空間；而后者則是折半將數(shù)據(jù)發(fā)送給鄰居節(jié)點，緩存占用率相比Epidemic較低。Prophet、URD和URM協(xié)議都是利用了節(jié)點之間數(shù)據(jù)交互的歷史信息，緩存占用率相對較低。Prophet協(xié)議是以計算節(jié)點投遞數(shù)據(jù)的概率，選擇概率較高的節(jié)點發(fā)送數(shù)據(jù)；URD協(xié)議是計算節(jié)點的效用值，選擇效用值較大的節(jié)點發(fā)送數(shù)據(jù)；而URM協(xié)議綜合節(jié)點的效用值、時延和跳數(shù)，選擇最優(yōu)的節(jié)點轉(zhuǎn)發(fā)數(shù)據(jù)，從而URM的緩存占用率最小。此外，在RWP移動模式下，節(jié)點隨機移動，每隔一定的時間，節(jié)點更新本地緩存中鄰居節(jié)點的信息，包括節(jié)點的效用值、時延值和跳數(shù)等，因此URM的節(jié)點緩存占用率增加趨于平穩(wěn)。

圖5 5種協(xié)議的緩存占用率

(2)數(shù)據(jù)傳輸?shù)钠骄鴶?shù)、轉(zhuǎn)發(fā)的可能性、收發(fā)成功概率、端到端的平均時延

由圖6表示數(shù)據(jù)傳輸?shù)钠骄鴶?shù)、轉(zhuǎn)發(fā)的可能性、收發(fā)成功概率、端到端的平均時延可知，對于平均跳數(shù)，URM和URD協(xié)議相比于其它協(xié)議較少，并且兩者相近。Epidemic采用洪泛機制，將數(shù)據(jù)轉(zhuǎn)發(fā)給所有節(jié)點，當(dāng)一個節(jié)點獲得數(shù)據(jù)，依次轉(zhuǎn)發(fā)給下一個節(jié)點，因此跳數(shù)最高。而URM和URD協(xié)議的收斂性主要是基于鄰居節(jié)點的效用值，通過移動連通度和相似度可知網(wǎng)絡(luò)的聯(lián)通性能和節(jié)點之間合作性能的高低，從而在不受到局部性影響的RWP移動模型下，節(jié)點之間的跳數(shù)相對較低。Prophet和Spray-And-Wait協(xié)議居于中間。

圖6 平均跳數(shù)、轉(zhuǎn)發(fā)的可能性、成功概率、平均時延

對于數(shù)據(jù)傳輸?shù)目赡苄院统晒Ω怕?，由于?jié)點隨機選擇移動方向、速度和目的地，導(dǎo)致節(jié)點相遇概率低，消息的傳輸總數(shù)較少，并且使得大多數(shù)消息在TTL生存時間內(nèi)未到達(dá)目的地而被丟棄，因此傳輸?shù)目赡苄院统晒Ω怕瘦^低。而URD和URM在轉(zhuǎn)發(fā)數(shù)據(jù)包時，利用節(jié)點本地緩存的歷史數(shù)據(jù)計算節(jié)點的效用值，有效地預(yù)測了節(jié)點間相遇的可能性，因此稍高于其它3種協(xié)議。而URM利用動態(tài)獲取影響效用值的參數(shù)來計算效用值，更接近于真實的網(wǎng)絡(luò)，所以稍高于URD協(xié)議。

對于數(shù)據(jù)傳輸?shù)钠骄鶗r延，由于場景中節(jié)點比較密集，并且在RWP移動模型下，節(jié)點相遇的概率較低，因此對于多拷貝方式的Prophet、Epidemic和Spray-And-Wait來說，每次傳輸數(shù)據(jù)時，都需要通過更多次數(shù)據(jù)的拷貝，增加了時延開銷。而URD和URM協(xié)議基于歷史信息來預(yù)測節(jié)點之間相遇的可能性，以及計算移動連通度和相似度時，更容易看出網(wǎng)絡(luò)的聯(lián)通性和節(jié)點之間的相互協(xié)作性能的高低，因此在一定程度上大大減少了時延開銷。其中URM根據(jù)歷史信息動態(tài)計算效用值，使結(jié)果更貼近于實際，所以較低于URD協(xié)議。

3.3.2 網(wǎng)絡(luò)中節(jié)點的移動方式不同

本文利用4種不同的移動模型來進(jìn)行模擬，分別是Random Walk(隨機移動模型)、Shortest Path Map Based Movement(基于地圖的最短路徑移動模型)、Map Based Movement(基于地圖的移動模型)、Car Movement(汽車移動模型)。為了更加說明算法的有效性，以下通過消息傳輸?shù)钠骄鶗r延和數(shù)據(jù)包收發(fā)的平均成功率來進(jìn)行描述：

由圖7表示不同移動模型下基于URM算法，數(shù)據(jù)包收發(fā)的平均成功率和平均時延值，圖8表示不同移動模型下不同路由協(xié)議的平均時延值可知，基于不同的移動模型下，URM路由算法無論是在哪種移動模型下，與上述節(jié)點之間數(shù)據(jù)包收發(fā)的平均成功率的數(shù)據(jù)分析圖相比，可以看出URM的數(shù)據(jù)包收發(fā)的平均成功率都是較大的。說明在不同的網(wǎng)絡(luò)環(huán)境下，基于節(jié)點間通信的歷史數(shù)據(jù)，動態(tài)計算效用值，在一定程度上減小了誤差，URM協(xié)議對實際網(wǎng)絡(luò)環(huán)境的適應(yīng)性，相對于其它幾種協(xié)議來說較好?；诓煌囊苿幽Ｐ?，對比于上述節(jié)點之間進(jìn)行數(shù)據(jù)轉(zhuǎn)發(fā)的平均時延值的數(shù)據(jù)分析圖，可以看出URM路由算法的平均時延值較小。URM路由算法的時延主要是在節(jié)點之間進(jìn)行數(shù)據(jù)轉(zhuǎn)發(fā)的過程中消耗的，而由于選擇同一節(jié)點作為下一跳轉(zhuǎn)發(fā)節(jié)點的概率更大，因此消耗的時間減少。此外，由于不需要獲取新的節(jié)點的數(shù)據(jù)信息，減少了獲取信息的時延值。因此總體上相較于其它路由協(xié)議，URM路由算法的時延值最小。

圖7 不同移動模型下基于URM算法，成功率和時延值

圖8 不同移動模型下不同路由協(xié)議的平均時延值

4 結(jié)束語

為了解決無線Mesh網(wǎng)絡(luò)由于節(jié)點的不斷移動，存在網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)動態(tài)變化、數(shù)據(jù)轉(zhuǎn)發(fā)時延增加、網(wǎng)絡(luò)資源浪費的問題，根據(jù)當(dāng)前效用轉(zhuǎn)發(fā)的路由算法較適用于理想狀態(tài)的問題，提出基于效用轉(zhuǎn)發(fā)的路由快速恢復(fù)算法，利用節(jié)點間的歷史交互數(shù)據(jù)，動態(tài)獲取在不同網(wǎng)絡(luò)環(huán)境下，影響效用值的各因素所占權(quán)重值，從而使算法能更好適應(yīng)真實的網(wǎng)絡(luò)環(huán)境。同時綜合網(wǎng)絡(luò)時延，節(jié)點效用值和節(jié)點間跳數(shù)，選擇最優(yōu)的下一跳轉(zhuǎn)發(fā)節(jié)點，減少網(wǎng)絡(luò)中不必要的時延增加和資源浪費。ONE仿真結(jié)果表明，該算法能夠判斷網(wǎng)絡(luò)穩(wěn)定性能的高低，提高數(shù)據(jù)包的轉(zhuǎn)發(fā)效率，減少網(wǎng)絡(luò)恢復(fù)的時延開銷，從而提升網(wǎng)絡(luò)的性能。在未來的工作中，將考慮通過結(jié)合網(wǎng)絡(luò)編碼和機會路由選擇更合適的轉(zhuǎn)發(fā)節(jié)點，進(jìn)一步優(yōu)化該協(xié)議的性能。