薄 玨, 喬 林, 王丹妮, 黃 峰, 許小潔

(1.國網(wǎng)遼寧省電力有限公司信息通信分公司，遼寧 沈陽 110000;2. 國網(wǎng)信通億力科技有限責(zé)任公司，福建 廈門 350003; 3. 廈門大學(xué)，福建 廈門 361005)

0 引 言

建立節(jié)點間端到端的路由是時延容忍網(wǎng)絡(luò)(Delay-tolerant Networks, DTNs)的關(guān)鍵[1-2]。DTNs具有間歇式連通、網(wǎng)絡(luò)分割嚴重等特點。這些特點給DTNs的數(shù)據(jù)傳輸提出了挑戰(zhàn)。為此, 路由成為DTNs的研究熱點[3-4]。

存儲-轉(zhuǎn)發(fā)是DTNs常采用的路由策略。當(dāng)目前沒有連通鏈路時, 數(shù)據(jù)包攜帶節(jié)點先存儲數(shù)據(jù), 直到遇見合適的轉(zhuǎn)發(fā)節(jié)點, 才將數(shù)據(jù)傳輸至該節(jié)點。然而, 在實際環(huán)境下，節(jié)點的相遇時間甚短，相遇的時間可能不足于數(shù)據(jù)的交換。

研究表明[4-5]，DTNs內(nèi)節(jié)點的相遇時間短。短的相遇時間給數(shù)據(jù)傳輸提出了挑戰(zhàn)。短的相遇時間難以在單一相遇機會內(nèi)完成數(shù)據(jù)的傳輸，需要多次相遇才能完成數(shù)據(jù)傳輸。

由于DTNs的鏈路連通時間短，靜態(tài)的路由算法無法應(yīng)用于DNTs網(wǎng)絡(luò)。在基于DTNs路由環(huán)境下，必須解決兩個問題：依據(jù)節(jié)點的相遇時間擇優(yōu)選擇轉(zhuǎn)發(fā)節(jié)點，盡量選擇相遇時間長的節(jié)點作為數(shù)據(jù)轉(zhuǎn)發(fā)節(jié)點。例如，王鵬[6]提出基于時間聚合圖的DTN網(wǎng)絡(luò)最短時延路由算法，該算法通過鏈路的連通時間計算最短路徑。并利用深度優(yōu)先算法搜索最短時延路由。

其次，盡可能單次接觸完成數(shù)據(jù)傳輸。若單次不行，需通過多次接觸完成數(shù)據(jù)的傳輸, 并需解決擁塞問題[7], 例如，鐘陳陳提出基于增強型PROPHET路由的DTN擁塞控制算法，該算法通過控制節(jié)點的緩存空間，降低算法的擁塞。因此，需要制定有效的數(shù)據(jù)轉(zhuǎn)發(fā)策略。

考慮到DNTs節(jié)點相遇的機會性，本文引用統(tǒng)計理論計算鄰居節(jié)點的接觸概率。通過網(wǎng)絡(luò)拓撲信息，相遇頻率、數(shù)據(jù)包尺寸，估計節(jié)點相遇概率。傳統(tǒng)的路由算法只計算一跳鄰居節(jié)點的概率，并沒有考慮兩跳鄰居節(jié)點的相遇概率。

計算兩跳鄰居節(jié)點的概率目的在于維護路由。當(dāng)一跳鄰居節(jié)點范圍內(nèi)沒有合適的轉(zhuǎn)發(fā)節(jié)點，就從二跳鄰居節(jié)點范圍內(nèi)選擇轉(zhuǎn)發(fā)節(jié)點。避免重新計算路由，減少成本，有利于數(shù)據(jù)的傳輸。

為此，面向DTNs網(wǎng)絡(luò)，提出一種基于轉(zhuǎn)發(fā)概率的DTNs路由(Forwarding-probability DTN Routing, FPDR)。FPDR路由擴大選擇轉(zhuǎn)發(fā)節(jié)點的范圍，從一跳和兩跳的鄰居節(jié)點范圍內(nèi)擇優(yōu)節(jié)點，提高數(shù)據(jù)包傳遞率。仿真結(jié)果表明，提出的FPDR路由有效地提高了數(shù)據(jù)包傳遞率。

1 網(wǎng)絡(luò)模型

由于DTNs網(wǎng)絡(luò)的鏈路時間短，每個節(jié)點采用存儲-轉(zhuǎn)發(fā)策略。因此，假定每個節(jié)點具有緩存區(qū)。當(dāng)節(jié)點暫找不到轉(zhuǎn)發(fā)節(jié)點，就緩存數(shù)據(jù)，直到遇到合適的節(jié)點，才轉(zhuǎn)發(fā)數(shù)據(jù)。

考慮到網(wǎng)絡(luò)開銷，F(xiàn)PDR路由引用單復(fù)本數(shù)據(jù)模型。即只允許網(wǎng)絡(luò)內(nèi)只有一個數(shù)據(jù)復(fù)本。若節(jié)點的相遇時間不小于數(shù)據(jù)尺寸與可獲取帶寬的比值，就認為在此次相遇機會內(nèi)完成數(shù)據(jù)的傳輸。若不能完成數(shù)據(jù)傳輸，則另尋其他機會完成數(shù)據(jù)傳輸。

同時，每個網(wǎng)絡(luò)內(nèi)傳輸?shù)臄?shù)據(jù)都具有時效性。當(dāng)數(shù)據(jù)的時效過期，此數(shù)據(jù)就無效。此外，令節(jié)點相遇時間和相遇周期服從指數(shù)分布，且相應(yīng)的參數(shù)為β和t。為了表述簡單，增強可讀性，引用如表1所示的標(biāo)識號。

表1 標(biāo)識符

2 FPDR路由

FPDR路由先計算節(jié)點相遇概率，然后，再計算節(jié)點相遇概率轉(zhuǎn)發(fā)數(shù)據(jù)包。為此，先推導(dǎo)相遇概率，然后再執(zhí)行數(shù)據(jù)路由策略。

2.1 一跳鄰居節(jié)點傳遞概率

假定節(jié)點si攜帶了當(dāng)前數(shù)據(jù)Data。Data的目的節(jié)點是sd。假定數(shù)據(jù)Data經(jīng)過m次相遇接觸才能成功轉(zhuǎn)發(fā)至目的節(jié)點sd：

(1)

(2)

(3)

(4)

(5)

(6)

最終，可通過將式(4-6)代入式(1)可得一跳鄰居的數(shù)據(jù)轉(zhuǎn)發(fā)概率：

(7)

2.2 兩跳鄰居節(jié)點傳遞概率

上一節(jié)推導(dǎo)了一跳鄰居節(jié)點的數(shù)據(jù)傳遞概率。FPDR路由欲從兩跳鄰居節(jié)點中選擇數(shù)據(jù)轉(zhuǎn)發(fā)節(jié)點。因此，本節(jié)推導(dǎo)兩跳鄰居節(jié)點的數(shù)據(jù)轉(zhuǎn)發(fā)概率。

圖1 兩跳傳遞模型

為了能正確地推導(dǎo)兩跳鄰居節(jié)點的相遇概率，每個節(jié)點保存與鄰居節(jié)點相遇的概率。為此，每個節(jié)點保存四元組信息〈si,sx,ηix,Tix〉。其中sx表示節(jié)點si的鄰居節(jié)點。ηix表示節(jié)點si與節(jié)點sx相遇概率。而Tix表示時間戳。

節(jié)點si先計算與中間節(jié)點sx相遇所消耗時間，進而計算相遇概率。據(jù)此，對式(1)進行修改。使其包含節(jié)點si與節(jié)點sx相遇概率、中間節(jié)點sx與目的節(jié)點sd的相遇概率。假定節(jié)點si通過第n次接觸才將數(shù)據(jù)Data傳輸至中間節(jié)點sx。中間節(jié)點再經(jīng)過m次接觸才能將數(shù)據(jù)傳輸至目的節(jié)點sd。

首先，先計算數(shù)據(jù)Data在到達目的節(jié)點sd前，數(shù)據(jù)Data未過期的概率：

(8)

再利用逐項積分，對式(8)進行處理：

(9)

其中N=2,β1=λs,?、β=λ?,d、a1=n和a2=m。令A(yù)表示式(9)中的積分項。再推導(dǎo)節(jié)點si在n-1前未能將數(shù)據(jù)Data傳輸至中間節(jié)點sx的概率和中間節(jié)點sx在m-1次接觸未能將數(shù)據(jù)Data傳輸至目的節(jié)點sd的概率：

(10)

最后，數(shù)據(jù)Data在節(jié)點s與中間節(jié)點?的n次相遇以及中間節(jié)點?與目的節(jié)點d的m次相遇時，被成功傳輸?shù)母怕剩?/p>

(-θ?,dHData)=exp(-θs,?HData-θ?,dHData)

(11)

最后，推導(dǎo)節(jié)點si將數(shù)據(jù)Data傳輸至目的節(jié)點sd的概率：

(12)

最終，依據(jù)式(10-12)計算節(jié)點si將數(shù)據(jù)Data成功傳輸至目的節(jié)點sd的概率：

(13)

2.3 數(shù)據(jù)傳輸策略

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

數(shù)據(jù)傳輸?shù)恼麄€流程如圖2所示。首先，每個節(jié)點先向鄰居節(jié)點傳輸自己的鄰居節(jié)點集。然后，數(shù)據(jù)攜帶節(jié)點si先依式(7)計算一跳鄰居節(jié)點的數(shù)據(jù)傳輸概率，鄰居節(jié)點再向鄰居節(jié)點傳輸自己的一跳鄰居概率，且令Ps和P?i分別表示這兩個概率。

然后，再從鄰居節(jié)點中選擇具有最大轉(zhuǎn)發(fā)概率P?的節(jié)點，同時，判斷Ps與P?的大小。若滿足Ps>Pυ，則數(shù)據(jù)攜帶節(jié)點si就不轉(zhuǎn)發(fā)數(shù)據(jù)Data。反之，若不滿足，數(shù)據(jù)攜帶節(jié)點si就從二跳鄰居節(jié)點尋找最優(yōu)節(jié)點，并計算式(13)計算概率。若未能尋找到合適的轉(zhuǎn)發(fā)節(jié)點，數(shù)據(jù)攜帶節(jié)點si就存儲該數(shù)據(jù)。

3 性能分析

3.1 仿真環(huán)境

為了更發(fā)地分析FPDR路由性能，通過ONE 1.5.1軟件[9]建立仿真平臺。引用沈陽出租車的行跡文件，由交通部提供出租車的移動數(shù)據(jù)。將出租車作為節(jié)點。每個節(jié)點最多能緩存5個數(shù)據(jù)，每個數(shù)據(jù)尺寸為1 MB。

同時，選用文獻的[8]提出的染路由(Epidemic Routing, EPR)、文獻[9]提出的概率路由(Probabilistic Routing, PBR)、文獻[10]提出的基于社會網(wǎng)絡(luò)轉(zhuǎn)發(fā)的路由(Social-based Forwarding Routing, SFR)作為參照。并對比分析它們的數(shù)據(jù)包傳遞率、數(shù)據(jù)端到端傳輸時延以及數(shù)據(jù)被傳輸?shù)拇螖?shù)這三個性能。

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

3.2.1實驗一

本次實驗分析數(shù)據(jù)包的傳遞率。圖3顯示了數(shù)據(jù)包傳遞率隨數(shù)據(jù)的有效時期的變化情況。

圖3 數(shù)據(jù)傳遞率

從圖3可知，數(shù)據(jù)的有效期越高，數(shù)據(jù)包傳遞率越高。原因在于：數(shù)據(jù)的有效期越高，數(shù)據(jù)包的生存時間越長，留給傳輸數(shù)據(jù)的時間越多，這有利于數(shù)據(jù)包的傳遞。反之，若數(shù)據(jù)有效期越短，數(shù)據(jù)包的生存時間也越短。數(shù)據(jù)還未成功傳輸至目的節(jié)點，數(shù)據(jù)可能就失效。

此外，從圖3可知，EPR路由的數(shù)據(jù)包傳遞率最高，原因在于：EPR路由引用傳染思想傳遞數(shù)據(jù)。該策略是以網(wǎng)絡(luò)資源為代價，提高數(shù)據(jù)包傳遞率。盡管FPDR路由的數(shù)據(jù)包傳遞率低于EPR路由，但是其高于PBR、SFR路由。這說明FPDR路由利用通過推導(dǎo)數(shù)據(jù)傳輸概率，擇優(yōu)選擇轉(zhuǎn)發(fā)節(jié)點，能夠提高數(shù)據(jù)包傳遞率。

3.2.2實驗二

本次實驗分析FPDR的數(shù)據(jù)傳輸?shù)亩说蕉藗鬏敃r延，如圖4所示。

圖4 端到端傳輸時延

從圖4可知，EPR路由具有最低時延。這與EPR路由策略相關(guān)。該路由策略引用泛洪策略傳遞數(shù)據(jù)，能夠使數(shù)據(jù)包快速地傳輸至目的節(jié)點。因此，EPR路由的時延最低。

此外，相比于PBR、SFR路由，提出的FPDR路由的端到端傳輸時延得到有效地控制，且分別比PBR和SFR路由下降了約5%和12%。

3.2.3實驗三

本次實驗分析每個數(shù)據(jù)包轉(zhuǎn)發(fā)的平均次數(shù)。平均轉(zhuǎn)發(fā)的次數(shù)越少，數(shù)據(jù)傳輸效率越高。圖5分析了FPDR路由、EPR路由、PBR和SFR路由的每條數(shù)據(jù)包的轉(zhuǎn)發(fā)次數(shù)。

圖5 數(shù)據(jù)包轉(zhuǎn)發(fā)的次數(shù)

從圖5可知，EPR路由的數(shù)據(jù)包轉(zhuǎn)發(fā)次數(shù)最高。原因在于：EPR路由是通過泛洪策略轉(zhuǎn)發(fā)數(shù)據(jù)包，產(chǎn)生了大量的冗余數(shù)據(jù)包。盡管EPR路由的數(shù)據(jù)包傳遞率高(圖3)、傳輸時延低(圖4)，但是EPR路由的網(wǎng)絡(luò)開銷大。在節(jié)點密集環(huán)境，也容易形成泛洪風(fēng)暴。

此外，相比于PBR和SFR路由外，F(xiàn)PDR路由轉(zhuǎn)發(fā)次數(shù)最低，且分別比PRB和SFR路由下降了約23%和14%。

4 結(jié) 語

針對DTNs的數(shù)據(jù)傳輸問題，提出基于轉(zhuǎn)發(fā)概率的時延容忍網(wǎng)絡(luò)路由FPDR。FPDR路由通過計算相鄰節(jié)點間的相遇時間，推導(dǎo)數(shù)據(jù)轉(zhuǎn)發(fā)概率，并依據(jù)轉(zhuǎn)發(fā)概率擇優(yōu)選擇轉(zhuǎn)發(fā)節(jié)點，再建立穩(wěn)定路由。仿真結(jié)果表明，提出的FPDR路由能夠有效地提高數(shù)據(jù)包傳遞率，并減少轉(zhuǎn)發(fā)次數(shù)。