DTN中基于時(shí)間因素的擁塞感知路由算法

良 梓 ，任哲坡 ，吳曉軍 ，

1.陜西師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院，西安 710062

2.西北工業(yè)大學(xué) 自動(dòng)化學(xué)院，西安 710072

1 引言

延遲容斷網(wǎng)絡(luò)[1]（Disruption Tolerant Network）的概念由美國國防部高級(jí)研究局DARPA在2004年提出，主要研究Internet交互式應(yīng)用協(xié)議，來解決Internet通信時(shí)連接頻繁斷開的問題。Kevin Fall等科學(xué)家在SIGCOMM會(huì)議上首次提出DTN架構(gòu)，它是一種位于區(qū)域網(wǎng)絡(luò)（各種不同類型的網(wǎng)絡(luò)，包括因特網(wǎng)）之上的覆蓋網(wǎng)，以克服受限網(wǎng)絡(luò)環(huán)境[2-4]中網(wǎng)絡(luò)斷開頻繁、延遲高和異構(gòu)性強(qiáng)[5]等問題。

在DTN網(wǎng)絡(luò)中，網(wǎng)絡(luò)節(jié)點(diǎn)的移動(dòng)性強(qiáng)且緩存資源有限，網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)呈動(dòng)態(tài)變化[6]，通常不存在一條完整的端到端路徑，這導(dǎo)致網(wǎng)絡(luò)存在傳輸延遲大，投遞效率低等問題[7]。因此，傳統(tǒng)路由協(xié)議不能在DTN網(wǎng)絡(luò)中取得理想效果，DTN路由協(xié)議的研究，對(duì)提高DTN網(wǎng)絡(luò)性能具有重要意義。

2 問題描述

目前，在DTN的研究中，路由算法主要分為單拷貝路由協(xié)議[8]和多拷貝路由協(xié)議。典型的單拷貝路由協(xié)議有Direct Delivery和First Contact，這兩種路由協(xié)議雖然網(wǎng)絡(luò)開銷小、能耗低，但報(bào)文到達(dá)信宿節(jié)點(diǎn)的延遲大、概率低，無法保障網(wǎng)絡(luò)性能。多拷貝路由協(xié)議中最具代表的路由協(xié)議有蔓延路由（Epidemic）[9]、散發(fā)等待路由（Spray and Wait）[10]和概率路由（Prophet）[11]。蔓延路由采用多副本洪泛機(jī)制傳遞報(bào)文，源節(jié)點(diǎn)對(duì)報(bào)文的下一跳節(jié)點(diǎn)的選擇不做任何限制，其缺點(diǎn)是會(huì)導(dǎo)致網(wǎng)絡(luò)中存在大量冗余副本。散發(fā)等待路由限制了轉(zhuǎn)發(fā)的報(bào)文副本數(shù)量，避免了冗余報(bào)文的傳輸，但在轉(zhuǎn)發(fā)報(bào)文時(shí)，直接將報(bào)文轉(zhuǎn)發(fā)給最先遇到的節(jié)點(diǎn)，具有一定盲目性。概率路由基于節(jié)點(diǎn)相遇的歷史信息定義轉(zhuǎn)發(fā)概率，通過轉(zhuǎn)發(fā)概率來選擇下一跳節(jié)點(diǎn)，對(duì)下一跳節(jié)點(diǎn)給定一定的限制，但轉(zhuǎn)發(fā)概率并不能完全代表報(bào)文實(shí)際遞交的概率，節(jié)點(diǎn)相遇并不一定能保證報(bào)文轉(zhuǎn)發(fā)成功。

針對(duì)上述存在的問題，目前已有一些改進(jìn)算法。如文獻(xiàn)[12]依據(jù)節(jié)點(diǎn)之間的歷史接觸成功率獲取網(wǎng)絡(luò)狀態(tài)信息，在轉(zhuǎn)發(fā)決策時(shí)引入接觸成功率的影響，降低網(wǎng)絡(luò)開銷，文獻(xiàn)[13]采用根據(jù)節(jié)點(diǎn)能量消耗改進(jìn)轉(zhuǎn)發(fā)概率，降低傳輸延遲，文獻(xiàn)[14]根據(jù)節(jié)點(diǎn)間相遇概率對(duì)節(jié)點(diǎn)進(jìn)行分簇，提出簇間轉(zhuǎn)發(fā)算法，提高了消息投遞率。但這些算法都不能在降低網(wǎng)絡(luò)延時(shí)和開銷的同時(shí)提高網(wǎng)絡(luò)投遞率。本文從時(shí)間因素的角度進(jìn)行如下分析。首先，報(bào)文傳輸是需要一定時(shí)間的，節(jié)點(diǎn)的移動(dòng)會(huì)導(dǎo)致正在傳輸?shù)膱?bào)文中斷，所以，轉(zhuǎn)發(fā)概率還需考慮節(jié)點(diǎn)相遇持續(xù)時(shí)間對(duì)報(bào)文完整傳遞的影響。另外，時(shí)間因素對(duì)網(wǎng)絡(luò)擁塞也有一定影響，因?yàn)閷?duì)于某些數(shù)據(jù)包會(huì)存在以下兩種情況：一種是該包傳輸延時(shí)大，即節(jié)點(diǎn)間斷開持續(xù)時(shí)間長，被成功傳遞的可能性小；另一種是經(jīng)本節(jié)點(diǎn)的路徑很難達(dá)到目的地，導(dǎo)致該包跳數(shù)較多，已生存時(shí)間較長。以上兩種情況中的數(shù)據(jù)包都應(yīng)該被丟棄。因此，可以通過計(jì)算節(jié)點(diǎn)斷開持續(xù)時(shí)間、節(jié)點(diǎn)本身蘊(yùn)含的跳數(shù)值和TTL值等信息來定義一個(gè)報(bào)文保存率，在網(wǎng)絡(luò)擁塞時(shí)，通過該報(bào)文保存率衡量報(bào)文被保存的價(jià)值，以擁塞感知自適應(yīng)的方式來優(yōu)化路由算法。基于以上分析，本文結(jié)合概率路由和散發(fā)等待路由的各自優(yōu)點(diǎn)，提出基于時(shí)間因素的擁塞感知路由算法（Congestion-Aware Routing Algorithm based on time factor，CARA 路由算法）。

3 CARA路由算法

3.1 算法思想

CARA算法采用改進(jìn)的轉(zhuǎn)發(fā)概率來進(jìn)行路由選擇，以擁塞感知自適應(yīng)的方式進(jìn)行擁塞控制。主要改進(jìn)有以下三方面：

（1）報(bào)文轉(zhuǎn)發(fā)方式。CARA算法中，節(jié)點(diǎn)之間轉(zhuǎn)發(fā)報(bào)文的條件由轉(zhuǎn)發(fā)概率確定。為提高估算精準(zhǔn)度，估算傳輸概率時(shí)考慮時(shí)間因素對(duì)轉(zhuǎn)發(fā)概率的影響，優(yōu)先選擇轉(zhuǎn)發(fā)概率較高的節(jié)點(diǎn)作為中繼節(jié)點(diǎn)。

（2）報(bào)文轉(zhuǎn)發(fā)數(shù)目。報(bào)文轉(zhuǎn)發(fā)數(shù)目按照轉(zhuǎn)發(fā)概率動(dòng)態(tài)分配。節(jié)點(diǎn)轉(zhuǎn)發(fā)概率越高，獲得的報(bào)文數(shù)目也越多，反之，則獲得的報(bào)文數(shù)目越少。

（3）擁塞控制。CARA算法中，根據(jù)節(jié)點(diǎn)斷開持續(xù)時(shí)間、節(jié)點(diǎn)的跳數(shù)(Hopsm)、TTL值來定義報(bào)文保存率，衡量報(bào)文應(yīng)被保存的價(jià)值大小。在報(bào)文轉(zhuǎn)發(fā)過程中，先進(jìn)行擁塞檢測(cè)，若無擁塞，則轉(zhuǎn)發(fā)報(bào)文；若擁塞，則執(zhí)行擁塞避免，依次丟棄報(bào)文保存率小的報(bào)文，緩解擁塞，再轉(zhuǎn)發(fā)報(bào)文。

3.2 路由過程

3.2.1 改進(jìn)的轉(zhuǎn)發(fā)概率

概率路由是根據(jù)節(jié)點(diǎn)歷史相遇信息來預(yù)測(cè)節(jié)點(diǎn)移動(dòng)方式，在節(jié)點(diǎn)相遇時(shí)，交換擁有相遇概率信息的摘要矢量，然后選擇下一跳轉(zhuǎn)發(fā)的節(jié)點(diǎn)[10]。本文將該算法進(jìn)行改進(jìn)，考慮節(jié)點(diǎn)相遇持續(xù)時(shí)間對(duì)轉(zhuǎn)發(fā)概率的影響，通過分析兩個(gè)節(jié)點(diǎn)建立連接的方式，定義需要提取的時(shí)間參數(shù)。

定義1（相遇時(shí)間）節(jié)點(diǎn)A和B在0時(shí)刻從初始位置開始移動(dòng)，它們第一次到達(dá)對(duì)方通信范圍內(nèi)所需要的時(shí)間。

Sa(t)表示節(jié)點(diǎn)a在t時(shí)刻在網(wǎng)絡(luò)中的位置，K是節(jié)點(diǎn)通信范圍。

定義2（相遇持續(xù)時(shí)間）節(jié)點(diǎn)A和B最初在信息通信范圍之外，假設(shè)在0時(shí)刻，到達(dá)對(duì)方的通信范圍內(nèi)，這兩個(gè)節(jié)點(diǎn)在移出通信范圍之前保持聯(lián)系的時(shí)間為相遇持續(xù)時(shí)間。

定義3（相遇間隔時(shí)刻）在0時(shí)刻節(jié)點(diǎn)A和B在對(duì)方通信范圍之內(nèi)，在t1時(shí)刻移出通信范圍，定義相遇間隔時(shí)刻為t1。

定義4（斷開持續(xù)時(shí)間）A和B兩節(jié)點(diǎn)再次到達(dá)對(duì)方通信范圍需要的時(shí)間。

改進(jìn)的轉(zhuǎn)發(fā)概率變化公式分三種：概率更新公式、衰減公式和傳遞公式。

（1）概率更新公式：

（2）概率衰減公式：

（3）概率傳遞公式：

按照上述轉(zhuǎn)發(fā)概率的變化，節(jié)點(diǎn)維護(hù)一張轉(zhuǎn)發(fā)概率表，根據(jù)此表選擇下一跳節(jié)點(diǎn)。

3.2.2 散發(fā)階段

（1）S（源節(jié)點(diǎn)）要發(fā)送消息到目的節(jié)點(diǎn)R，S初始化報(bào)文拷貝數(shù)L(L＞1)。

（2）S（或中繼節(jié)點(diǎn)A）與中繼節(jié)點(diǎn)B相遇時(shí)，更新各自摘要矢量并計(jì)算轉(zhuǎn)發(fā)概率，PSR（S到達(dá)目的節(jié)點(diǎn)R的概率）＜PBR（B到達(dá)R的概率），則S將報(bào)文轉(zhuǎn)發(fā)給B，如果PSR≥PBR，則不轉(zhuǎn)發(fā)，繼續(xù)尋找下一節(jié)點(diǎn)。

（3）S報(bào)文數(shù)目為L，轉(zhuǎn)發(fā)給節(jié)點(diǎn)B的報(bào)文數(shù)目為L′，若L＞1，L′=PSR?L。

（4）判斷是否發(fā)生擁塞，如擁塞，則進(jìn)行擁塞避免，如無擁塞，數(shù)據(jù)發(fā)送成功。

3.2.3 等待階段

（1）判斷散發(fā)階段是否與信宿節(jié)點(diǎn)相遇，若遇到，則遞交報(bào)文，終止傳輸；若沒遇到，按上述方式選擇中繼節(jié)點(diǎn)，繼續(xù)散發(fā)報(bào)文。

（2）隨著報(bào)文的散發(fā)，報(bào)文副本數(shù)減小。若當(dāng)前中繼節(jié)點(diǎn)上該報(bào)文副本數(shù)為1，則進(jìn)行（3），若副本數(shù)不為1，繼續(xù)散發(fā)，進(jìn)行（2）。

（3）不再散發(fā)報(bào)文，直到該節(jié)點(diǎn)遇到信宿節(jié)點(diǎn)時(shí)才遞交，即轉(zhuǎn)為直接傳輸模式。

（4）判斷是否發(fā)生擁塞，如擁塞，則進(jìn)行擁塞避免，如無擁塞，數(shù)據(jù)發(fā)送成功。

3.2.4 擁塞檢測(cè)及避免

定義5（報(bào)文保存率）反映報(bào)文應(yīng)被保存的價(jià)值大小。

報(bào)文保存率見公式（9）：

其中，公式（9）中w1，w2為權(quán)重系數(shù)，Qm為報(bào)文m的質(zhì)量，Zm為報(bào)文m的生存時(shí)間分量。公式（10）中N表示全網(wǎng)節(jié)點(diǎn)數(shù)，Hopsm表示報(bào)文m的轉(zhuǎn)發(fā)次數(shù)，即跳數(shù)。公式（11）中TTL為報(bào)文m的生存時(shí)間，δab為斷開持續(xù)時(shí)間，可由公式（3）、（4）求出。由公式可見，Hopsm越大，TTL越小，δab越大，Pm越小，報(bào)文保存率越小，可被成功投遞的可能性就越小。當(dāng)網(wǎng)絡(luò)擁塞時(shí)，丟棄報(bào)文保存率小的報(bào)文緩解擁塞。

擁塞策略流程如圖1所示。

圖1 擁塞策略流程

4 仿真及性能分析

4.1 仿真參數(shù)

為了檢驗(yàn)CARA算法的有效性，本文采用離散事件模擬器ONE[15]（Opportunity Networking Environment）對(duì)CARA算法進(jìn)行仿真。本文采用ONE中自帶的芬蘭首都赫爾辛基（Helsinki）地圖[16]，仿真場(chǎng)景大小為4 500 m×3 400 m。仿真網(wǎng)絡(luò)共126個(gè)節(jié)點(diǎn)，分為6組，第一、三組為行人節(jié)點(diǎn)，第二組為出租車節(jié)點(diǎn)，第四、五、六組為有軌電車節(jié)點(diǎn)，具體如表1所示。消息大小為350 kB，傳輸速率250 kB/s，仿真時(shí)間20 h，數(shù)據(jù)包產(chǎn)生間隔時(shí)間30～40 s，采用基于地圖路徑方式[17-18]移動(dòng)。實(shí)驗(yàn)仿真參數(shù)見表1。

表1 實(shí)驗(yàn)仿真參數(shù)

4.2 仿真結(jié)果及分析

為了全面驗(yàn)證CARA算法，本文通過仿真實(shí)驗(yàn)，將Prophet算法、二分散發(fā)等待路由（BSW）算法、Epidemic算法、CS-DTN[14]同CARA算法相比較，分析在報(bào)文遞交率、平均延遲及網(wǎng)絡(luò)開銷率三方面[19-20]隨時(shí)間的變化情況。

（1）報(bào)文遞交率

報(bào)文遞交率可以衡量路由算法對(duì)報(bào)文的傳遞能力，其定義如下。

實(shí)驗(yàn)結(jié)果如圖2所示。從圖2中可以看出，Epidemic算法在起始階段遞交率高，增加速度快，但到10 000 s之后，開始逐漸降低，這是由于Epidemic算法的洪泛機(jī)制易使網(wǎng)絡(luò)擁塞所致。圖中還可以看出，CARA算法比Prophet算法、CS-DTN算法的遞交率都有了明顯提高，這是由于本文在Prophet算法的基礎(chǔ)上考慮了節(jié)點(diǎn)持續(xù)連接時(shí)間對(duì)遞交概率的影響，同時(shí)，擁塞感知策略丟棄了節(jié)點(diǎn)緩存中保存率小的報(bào)文，使到達(dá)目的節(jié)點(diǎn)可能性高的報(bào)文得以保存和轉(zhuǎn)發(fā)，從而提高了全網(wǎng)報(bào)文遞交率。

圖2 遞交率隨時(shí)間的變化

（2）平均延遲

平均延遲用來衡量算法的性能，其定義如下。

實(shí)驗(yàn)結(jié)果如圖3所示。從圖3中可以看出，Epidemic算法的平均延遲開始較低，但隨時(shí)間的增加延遲逐漸增大，這是因?yàn)镋pidemic算法的洪泛機(jī)制導(dǎo)致節(jié)點(diǎn)處報(bào)文擁塞無法遞交，而使得延遲增大。Prophet算法、CS-DTN算法同CARA算法相比，CARA算法延遲要小于前兩個(gè)算法。這是因?yàn)镃ARA算法限制了對(duì)中繼節(jié)點(diǎn)的選擇，使報(bào)文轉(zhuǎn)發(fā)概率不會(huì)隨節(jié)點(diǎn)之間相遇頻率的增加而增加，所以延遲逐漸增加，但隨著時(shí)間的增加，這種增加的趨勢(shì)逐漸減小，平均延時(shí)趨于穩(wěn)定。這是由于CARA算法中采用擁塞感知機(jī)制，拋棄那些持續(xù)斷開時(shí)間很長的報(bào)文，使得全網(wǎng)平均延遲變小。

（3）開銷率

開銷率可以用來衡量路由算法的總體傳輸性能，其定義如下。

實(shí)驗(yàn)結(jié)果如圖4所示。從圖4中看出，Epidemic算法開銷最大，這是因?yàn)镋pidemic算法的洪泛機(jī)制使報(bào)文遞交效用低，所以開銷大。BSW算法在源端限制報(bào)文拷貝數(shù)，所以其開銷率小且穩(wěn)定。從圖4中可以看出，CS-DTN算法比BSW算法的開銷大，這是因?yàn)镃S-DTN算法中，消息不斷地向中心性高的節(jié)點(diǎn)累計(jì)，簇間的轉(zhuǎn)發(fā)導(dǎo)致開銷大。而CARA算法開銷最小，這是因?yàn)镃ARA算法合理地丟棄冗余報(bào)文，增大了成功遞交數(shù)據(jù)包數(shù)量，減小了網(wǎng)絡(luò)中冗余報(bào)文的存儲(chǔ)和轉(zhuǎn)發(fā)，進(jìn)而減小網(wǎng)絡(luò)開銷。

圖4 開銷率隨時(shí)間的變化

5 結(jié)語

本文分析了時(shí)間因素對(duì)路由選擇和網(wǎng)絡(luò)擁塞的影響，提出了一種基于時(shí)間因素的擁塞感知路由算法CARA。考慮節(jié)點(diǎn)相遇持續(xù)時(shí)間對(duì)報(bào)文完整傳遞的影響，改進(jìn)了傳統(tǒng)概率路由的轉(zhuǎn)發(fā)概率，根據(jù)改進(jìn)的轉(zhuǎn)發(fā)概率動(dòng)態(tài)分配轉(zhuǎn)發(fā)報(bào)文，同時(shí)定義報(bào)文保存率來衡量報(bào)文的保存價(jià)值，以擁塞感知的方式實(shí)現(xiàn)擁塞控制的優(yōu)化。實(shí)驗(yàn)表明，與其他算法相比，CARA算法在降低網(wǎng)絡(luò)延遲和開銷，提高網(wǎng)絡(luò)投遞率上，優(yōu)越性明顯。

[1]Fall K.A delay tolerant network architecture for challenged Internets[C]//SIGCOMM，2003：27-34.

[2]Nichols R A，Hammons A R.DTN-based free-space optical and directional RF networks[C]//Military Communications Conference，2008：1-6.

[3]Luo Peien，Huang Hongyu，Li Minglu，et al.Performance evaluation of vehicular DTN routing under realistic mobility models[C]//Wireless Communications and Networking Conference.Las Vegas，NV：[s.n.]，2008：2206-2211.

[4]Chan C Y M，Motani M.An integrated energy efficient data retrieval protocol for underwater delay tolerant net-works[C]//IEEE Oceans.Washington DC：IEEE，2007：1-6.

[5]樊秀梅，單志廣，張寶賢，等.容遲網(wǎng)絡(luò)體系結(jié)構(gòu)及其關(guān)鍵技術(shù)研究[J].電子學(xué)報(bào)，2008，36（1）：161-170.

[6]Daly E M，Hahr M.The challenges of disconnected delay tolerant MANETs[J].Ad Hoc Networks，2010，8：241-250.

[7]Whitbeck J，Conan V.HYMAD：hybrid DTN-MANET routing for dense and highly dynamic wireless networks[C]//IEEE WoWMoM Workshop on Autonomic and Opportunistic Communications，2010.

[8]Jain S，F(xiàn)all K，Patra R.Routing in a delay tolerant network[C]//Proceedings of the 2004 Conference on Applications，Technologies，Architectures，and Protocols for Computer Communications，NewYork，2004：145-158.

[9]Vahdat A，Becker D.Epidemic routing for partially connected ad hoc networks[R].San Diego：University of Carolina，2000.

[10]Spyropoulos T，Psounis K，Raghavendra C.Spray and wait，an efficient routing scheme for intermittently connected mobile networks[C]//WDTN’05，2005：252-259.

[11]Lindgreny A，Doria A，Schelen O.Probabilistic routing in intermittentlyconnectednetworks[J].ACM SIGMOBILE Mobile Computing and Communications Review，2003，7（3）：19-20.

[12]付凱，夏靖波，尹波.DTN中一種網(wǎng)絡(luò)狀態(tài)感知的概率路由算法[J].小型微型計(jì)算機(jī)系統(tǒng)，2013，34（1）：145-149.

[13]劉唐，彭艦，楊進(jìn).異構(gòu)延遲容忍移動(dòng)傳感器網(wǎng)絡(luò)中基于轉(zhuǎn)發(fā)概率的數(shù)據(jù)傳輸[J].軟件學(xué)報(bào)，2013，24（2）：215-229.

[14]張振京，金志剛，舒炎泰.基于節(jié)點(diǎn)運(yùn)動(dòng)預(yù)測(cè)的社會(huì)性DTN高效路由[J].計(jì)算機(jī)學(xué)報(bào)，2013，36（3）：626-635.

[15]TKK/COMNET.Project page of the ONE simulator[EB/OL].[2012-12-11].http：//www.netlab.tkk.fi/tutkimus/dtn/theone.

[16]Keranen A，Ott J，Karkkainen T.The ONE simulator for DTN protocol evaluation[C]//Proceedings of the 2nd International Conference on Simulation Tools and Techniques，2009：1-10.

[17]Keranen A，Ott J.Increasing reality for DTN protocol simulations[R].[S.l.]：Networking Laboratory，Helsinki University of Technology，2007.

[18]Peng Min.Research on mobility model and routing in delay tolerant network[D].Hefei：University of Science and Technology of China，2010.

[19]Ahmed S，Kanhere S.Cluster-based forwarding in delay tolerant public transport networks[C]//Proceedings of the 32nd IEEE Conference on Local Computer Networks，2007：625-634.

[20]Li Yun，Chen Xinjian，Liu Qilie，et al.A novel congestion controlstrategy in delay tolerantnetworks[C]//IEEE 2010 2nd International Conference on Future Networks，China，2010：233-237.