基于相遇時(shí)間感知的延時(shí)容忍網(wǎng)絡(luò)路由*

吳育寶，趙明生，李星亮

（1.南京森林警察學(xué)院刑事科學(xué)技術(shù)學(xué)院，南京 210023；2.南京信息工程大學(xué)信息技術(shù)學(xué)院，南京 210023）

0 引言

延時(shí)容忍網(wǎng)絡(luò)（Delay-tolerant Networks，DTNs）是具有稀疏連通、高分割率和間歇式連通特點(diǎn)的自組織網(wǎng)絡(luò)［1-2］。這些特點(diǎn)給節(jié)點(diǎn)間的端到端通信路徑提出了挑戰(zhàn)。為了處理DTNs 內(nèi)移動(dòng)節(jié)點(diǎn)的稀疏連接，常使用攜帶-轉(zhuǎn)發(fā)算法。即由節(jié)點(diǎn)臨時(shí)存儲(chǔ)消息，直到遇到合適下一跳節(jié)點(diǎn)，再轉(zhuǎn)發(fā)此消息。因此，選擇合適的下一跳節(jié)點(diǎn)成為DTNs 路由的重要技術(shù)［3-4］。

面向DTNs 路由已受到研究人員的廣泛關(guān)注。然而，多數(shù)路由協(xié)議假定有足夠的相遇接觸時(shí)間（Contact Duration Time，CDT），進(jìn)而在單一相遇機(jī)會(huì)內(nèi)就能傳輸所有緩沖消息。近期研究表明，在DTNs的真實(shí)環(huán)境［4-5］中，CDT 通常是很短的。基于短的CDT 事實(shí)，必須處理兩個(gè)關(guān)鍵問(wèn)題。第一就是轉(zhuǎn)發(fā)節(jié)點(diǎn)選擇，即需要尋找一個(gè)合適的轉(zhuǎn)發(fā)節(jié)點(diǎn)，使得它與消息的目的節(jié)點(diǎn)具有足夠長(zhǎng)的CDT，進(jìn)而提高整個(gè)消息的傳輸成功率；其次就是消息轉(zhuǎn)發(fā)策略。由于并非所有消息能夠在單一次相遇接觸機(jī)會(huì)內(nèi)傳輸完畢，合理安排消息轉(zhuǎn)發(fā)是非常重要的。

為此，本文針對(duì)轉(zhuǎn)發(fā)節(jié)點(diǎn)選擇策略和消息轉(zhuǎn)發(fā)方案，提出一個(gè)理論框架。此框架的核心就是計(jì)算一跳和兩跳傳遞概率。利用網(wǎng)絡(luò)信息，包括CDT、相遇頻率以及消息尺寸，計(jì)算傳遞概率。其中，一跳傳遞概率是指當(dāng)前消息攜帶節(jié)點(diǎn)利用當(dāng)前相遇節(jié)點(diǎn)向目的節(jié)點(diǎn)傳輸消息的概率。而兩跳傳遞概率是利用過(guò)去相遇的、且將來(lái)能夠相遇的節(jié)點(diǎn)傳輸消息的概率。

考慮兩跳傳遞概率的目的就是減少傳輸成本，通過(guò)減少傳輸成本，提高DTNs 網(wǎng)絡(luò)帶寬利用率。如果一個(gè)節(jié)點(diǎn)可能遇到了比當(dāng)前相遇節(jié)點(diǎn)更合適的轉(zhuǎn)發(fā)節(jié)點(diǎn)，它應(yīng)當(dāng)攜帶消息直到相遇到最合適的節(jié)點(diǎn)。

為此，本文提出基于相觸接觸時(shí)間的時(shí)延容忍網(wǎng)絡(luò)路由（Contact Duration-Aware Routing，CDAR），CDAR 路由先計(jì)算一跳、兩跳傳輸概率，再依據(jù)此概率選擇下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)。在計(jì)算傳輸概率時(shí)，充分利用網(wǎng)絡(luò)信息，包括節(jié)點(diǎn)CDT、接觸頻率以及消息尺寸。實(shí)驗(yàn)數(shù)據(jù)表明，提出的CDAR 路由能夠控制時(shí)延和路由成本。

1 約束條件

假定DTNs 網(wǎng)絡(luò)具有有限轉(zhuǎn)發(fā)帶寬，且每個(gè)節(jié)點(diǎn)具有存儲(chǔ)緩沖功能。當(dāng)節(jié)點(diǎn)在通信范圍內(nèi)與其他節(jié)點(diǎn)相遇，節(jié)點(diǎn)就能夠向這些節(jié)點(diǎn)轉(zhuǎn)發(fā)消息。此外，假定節(jié)點(diǎn)的CDT 較短，并且CDT 遠(yuǎn)短于相遇間隔時(shí)間，其中相遇間隔時(shí)間是指相遇頻率的倒數(shù)，即平均每隔多長(zhǎng)時(shí)間相遇一次。

CDAR 路由遵循單復(fù)本（Single-Copy）模型，即在任何時(shí)刻，網(wǎng)絡(luò)內(nèi)消息復(fù)本最多只有一條。假定消息具有相同尺寸，且無(wú)分割。如果CDT 大于或等于消息尺寸與可能帶寬的比值，則認(rèn)為消息被成功傳輸。否則，消息需要在下一個(gè)相遇機(jī)會(huì)內(nèi)再重傳。

此外，每條消息具有有限時(shí)效（Time-To-Live，TTL）值。一旦TTL 過(guò)期，就丟失此消息。同時(shí)，CDT和相遇間隔時(shí)間服從指數(shù)分布，且參數(shù)分別為和θ。不同的兩個(gè)節(jié)點(diǎn)間具有不同的相遇頻率和CDT。本文引用Cabspotting trace［6］作為系統(tǒng)仿真軟件，評(píng)估CDAR 路由性能。

2 CDT 模型

基于短的CDT 的事實(shí)下，先推導(dǎo)一跳和兩跳傳遞概率。估計(jì)相遇間隔率和CDT 的時(shí)長(zhǎng)率θ。在基于推導(dǎo)的傳遞概率F，設(shè)置下一跳節(jié)點(diǎn)的選擇策略和消息轉(zhuǎn)發(fā)方案。

2.1 一跳傳遞概率

當(dāng)Yk≥Hi時(shí)，表示消息i 已在第k 個(gè)相遇機(jī)會(huì)內(nèi)成功傳輸。否則，消息i 需要在下一個(gè)相遇機(jī)會(huì)內(nèi)重傳，其中，Yk表示在第k 個(gè)相遇的接觸時(shí)間的隨機(jī)變量，而Hi是成功傳輸消息i 的所需要的機(jī)遇接觸時(shí)間，且Hi的定義如式（1）所示：

其中，ωi表示消息i 的尺寸；B 表示兩個(gè)節(jié)點(diǎn)間的通信帶寬。

此外，用Xk表示第k 個(gè)相遇間隔時(shí)間的隨機(jī)變量。假定Xk遠(yuǎn)大于Yk，即Xk>>Yk，這說(shuō)明CDT 甚短，遠(yuǎn)小于發(fā)生下一次相遇的時(shí)間間隔。

假定當(dāng)前消息的攜帶節(jié)點(diǎn)為s，消息i 的目的節(jié)點(diǎn)為d。消息i 直到第n 次相遇才成功傳輸至目的節(jié)點(diǎn)的概率為Pi（n），其可表述為：

由于Xk與Yk是獨(dú)立的，式（2）可轉(zhuǎn)換為：

接下來(lái)，分析Pi（n）中的3 項(xiàng)，進(jìn)而對(duì)式（3）進(jìn)行計(jì)算。

最后，將式（5）～式（7）代入式（2）可得：

因此，成功傳輸消息i 的概率可表示為：

2.2 兩跳傳遞概率

兩跳傳遞概率是指消息i 由當(dāng)前攜帶節(jié)點(diǎn)s 通過(guò)中間節(jié)點(diǎn)? 間接傳輸至目的節(jié)點(diǎn)d，如圖1 所示。為了計(jì)算此概率，節(jié)點(diǎn)s 需要獲取兩個(gè)關(guān)鍵消息。

圖1 兩跳傳遞模型

首先，定義節(jié)點(diǎn)s 與中間節(jié)點(diǎn)相遇所耗的時(shí)間，即與中間節(jié)點(diǎn)相遇所經(jīng)歷的時(shí)間。顯然，對(duì)于節(jié)點(diǎn)s而言，若需獲取與中間節(jié)點(diǎn)所耗的時(shí)間，此中間節(jié)點(diǎn)一定是先前相遇過(guò)的［10］。對(duì)于先前從未相遇過(guò)的節(jié)點(diǎn)，是無(wú)法計(jì)算此時(shí)間的。其次，就是中間節(jié)點(diǎn)與目的節(jié)點(diǎn)間的相遇率（Inter-contact rate）。獲取此項(xiàng)信息，需要網(wǎng)絡(luò)全局狀態(tài)信息的交互。為此，每個(gè)節(jié)點(diǎn)保存與其相遇節(jié)點(diǎn)的清單，格式如式（10）所示：

將中間節(jié)點(diǎn)融入傳遞概率后，需對(duì)式（2）進(jìn)行修改，使其分別包含節(jié)點(diǎn)s 與中間節(jié)點(diǎn)? 和中間節(jié)點(diǎn)? 與目的節(jié)點(diǎn)d 的CDT 和相遇間隔時(shí)間。假定消息i 通過(guò)第n 次相遇，節(jié)點(diǎn)s 將消息傳輸至目的節(jié)點(diǎn)?，而再通過(guò)第m 次相遇，將消息從? 傳輸至d。因此，消息i 在傳輸至目的節(jié)點(diǎn)d 前，消息未過(guò)期的概率如式（11）所示：

再引用文獻(xiàn)［9］的逐項(xiàng)積分理論，計(jì)算式（11），可得：

接下來(lái)，計(jì)算消息i 在節(jié)點(diǎn)s 與中間節(jié)點(diǎn)? 的n-1 次相遇以及中間節(jié)點(diǎn)? 與目的節(jié)點(diǎn)d 的m-1次相遇時(shí)，傳輸失敗的概率，如式（13）所示：

最后，消息i 在節(jié)點(diǎn)s 與中間節(jié)點(diǎn)? 的n 次相遇以及中間節(jié)點(diǎn)? 與目的節(jié)點(diǎn)d 的m 次相遇時(shí)，能成功傳輸?shù)母怕剩?/p>

結(jié)合式（12）～式（14），可計(jì)算消息i 在節(jié)點(diǎn)s 與中間節(jié)點(diǎn)? 的n 次相遇以及中間節(jié)點(diǎn)? 與目的節(jié)點(diǎn)d 的m 次相遇時(shí)，才被成功傳輸?shù)母怕蕿镻i（n，m），其可表示為：

最后，通過(guò)兩跳成功傳輸消息i 的傳遞概率：

3 CDAR 路由

CDAR 路由的關(guān)鍵在于下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)的選擇。本小節(jié)分析下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)的選擇過(guò)程。CDAR路由引用單復(fù)本模型，即在任何時(shí)刻，只允許一個(gè)消息復(fù)本。

先交互節(jié)點(diǎn)的相遇節(jié)點(diǎn)集。交互完后，源節(jié)點(diǎn)s和鄰居節(jié)點(diǎn)?i單獨(dú)依據(jù)式（9）計(jì)算一跳傳輸概率，分別表示為Ps和。然后，每個(gè)?i向源節(jié)點(diǎn)傳遞自己一跳傳輸概率。

圖2 消息轉(zhuǎn)發(fā)流程

圖3 消息轉(zhuǎn)發(fā)示例

圖3 示例說(shuō)明了下一跳轉(zhuǎn)發(fā)消息的過(guò)程。節(jié)點(diǎn)s 先計(jì)算一跳傳輸概率Ps和當(dāng)前一跳鄰居節(jié)點(diǎn)傳輸概率P?1。然后，判斷兩個(gè)概率。如果，就繼續(xù)計(jì)算二跳傳輸概率。由于，節(jié)點(diǎn)成為一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)。

4 性能分析

4.1 仿真環(huán)境

本文利用機(jī)會(huì)網(wǎng)絡(luò)仿真器ONE 1.5.1［11］建立仿真軟件，并引用Cabspotting trace。Cabspotting 含有了536 出租車的跟蹤文件。假定每個(gè)節(jié)點(diǎn)有一定的緩沖容量。每個(gè)節(jié)點(diǎn)在緩沖區(qū)里初始存了5 條消息，每條消息尺寸2 MB。此外，每條消息有相同的TTL值。每次實(shí)驗(yàn)獨(dú)立重復(fù)20 次，取平均值作最終的實(shí)驗(yàn)數(shù)據(jù)。

為了更好地評(píng)估CDAR 性能，選擇Epidemic 路由［12］、PROPHET［13］、BubbleRap［14］和MEED［15］作為參照。PROPHET 算法利用向目的節(jié)點(diǎn)傳輸概率信息選擇轉(zhuǎn)發(fā)節(jié)點(diǎn)。而傳遞概率是依據(jù)歷史相遇數(shù)據(jù)計(jì)算。BubbleRap 算法是基于社區(qū)的路由算法，其利用社區(qū)中心度轉(zhuǎn)發(fā)算法。MEED 算法是從傳輸時(shí)延角度選擇路由，并通過(guò)觀察歷史相遇數(shù)據(jù)估計(jì)傳輸時(shí)延，再用傳輸時(shí)延最短的鏈路組建路由。

同時(shí)，分析消息傳遞率、平均時(shí)延和平均成本性能。消息傳遞率是指成功傳輸?shù)南?shù)與總的消息數(shù)之比；平均時(shí)延是指每條消息從源節(jié)點(diǎn)傳輸至目的節(jié)點(diǎn)的所耗的平均時(shí)間。平均成本是指每條消息傳輸至目的節(jié)點(diǎn)所被轉(zhuǎn)發(fā)的次數(shù)。

4.2 數(shù)據(jù)分析

首先分析消息傳遞率。實(shí)驗(yàn)數(shù)據(jù)如圖4 所示。正如預(yù)期的那樣，Epidemic 路由具有最高的消息傳遞率，這是以高的網(wǎng)絡(luò)資源為代價(jià)的。而提出的CDAR路由的平均消息傳遞率為74 %，比PROPHET、MEED 和BubbleRap 的消息傳遞率平均分別提高了10%、12%和13%。

圖4 消息傳遞率

圖5 平均時(shí)延隨TTL的變化情況

CDAR 路由之所以有較高的消息傳遞率，原因在于：首先，CDAR 路由考慮了CDT 短的事實(shí)，并優(yōu)化轉(zhuǎn)發(fā)節(jié)點(diǎn)選擇方案，其次，CDAR 路由利用一跳和二跳傳遞概率，選擇下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)。注意到Bub bleRap 路由的消息傳遞率最低，只有61%。

然后，分析了平均時(shí)延，實(shí)驗(yàn)數(shù)據(jù)如圖5 所示。從圖5 可知，Epidemic 路由仍具有最低時(shí)延，原因在于：Epidemic 路由采用泛洪策略決策路由，縮短了建立路由時(shí)間。盡管CDAR 路由的平均時(shí)延低于Epidemic路由，但它比PROPHET、MEED 和BubbleRap 路由的平均時(shí)延分別降低了5%、10%和12%。

最后，分析了路由成本，如圖6 所示。從圖6 可知，Epidemic 路由的路由成本最高，結(jié)合圖4 和圖5發(fā)現(xiàn)，Epidemic 路由是以高的路由成本換取低時(shí)延和高的消息傳遞率。而提出的CDAR 路由的路由成本最低，比BubbleRap、MEED 和PROPHET 路由的成本分別下降了14%、19%和23%。

結(jié)合圖4～圖6 實(shí)驗(yàn)數(shù)據(jù)可知，CDAR 路由在消息傳遞率、平均時(shí)延和路由成本方面均具有較好的性能。盡管它的消息傳遞率和平均時(shí)延性能劣于Epidemic 路由，但是它有效地控制路由成本，并且也獲取了較高的消息傳遞率和低的平均時(shí)延。

圖6 平均路由成本隨TTL 的變化情況

5 結(jié)論

本文提出了基于CDT 的時(shí)延容忍網(wǎng)絡(luò)路由CDAR。CDAR 路由利用消息傳遞的接觸時(shí)間限制選擇轉(zhuǎn)發(fā)節(jié)點(diǎn)。依據(jù)CDT、相遇間隔時(shí)間的指數(shù)分布，推導(dǎo)一跳和兩跳傳輸概率。再依據(jù)這些概率數(shù)據(jù)選擇下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)。實(shí)驗(yàn)數(shù)據(jù)表明，提出的CDAR 路由有效地提高了路由性能。