短相遇接觸時間網(wǎng)絡(luò)環(huán)境中的時延容忍網(wǎng)絡(luò)路由方案

王 超

(南陽理工學院 計算機與軟件學院，河南 南陽 473004)

1 引 言

稀疏的移動自組織網(wǎng)絡(luò)是時延容忍傳輸?shù)牡湫途W(wǎng)絡(luò)環(huán)境，它不依賴固定基礎(chǔ)設(shè)施，網(wǎng)絡(luò)節(jié)點可以自由組織，可進行多跳通信.換言之，時延容忍網(wǎng)絡(luò)(Delay-tolerant Network，DTN)是一種特殊的稀疏移動自組織網(wǎng)絡(luò)，無法建立從源節(jié)點到目的節(jié)點整條路徑，具有稀疏連通、高分割率和間歇式連通特點[1].上述特點對傳感器節(jié)點間的端到端通信路徑提出了挑戰(zhàn)，所以為處理DTN移動節(jié)點的稀疏連接，通常采用存儲-轉(zhuǎn)發(fā)方案.即傳感器節(jié)點先臨時存儲消息，直至遇到合適的下一跳節(jié)點再轉(zhuǎn)發(fā)該消息.因此，選擇合適的下一跳節(jié)點成為DTN路由的重點和熱點問題[2，3].面向DTN的路由協(xié)議研究受到國內(nèi)外專家學者的廣泛關(guān)注，但是大多數(shù)DTN路由協(xié)議均是建立在有足夠相遇接觸時間(Contact Duration Time，CDT)的假設(shè)條件下，即假定在單一相遇機會內(nèi)即可一次性傳輸全部緩沖消息.然而，在DTN真實環(huán)境中的研究結(jié)果表明相遇接觸時間通常很短[4，5].基于這一事實，真實環(huán)境下的DTN路由必須處理兩個關(guān)鍵問題：1)轉(zhuǎn)發(fā)節(jié)點的選擇.即需要尋找一個合適的轉(zhuǎn)發(fā)節(jié)點，該節(jié)點需與目的節(jié)點有足夠長的相遇接觸時間，主要作用是提高消息的傳輸成功率；2)消息轉(zhuǎn)發(fā)策略.由于不是所有消息都能在一次相遇接觸機會內(nèi)完成傳輸，所以合理安排消息轉(zhuǎn)發(fā)是非常重要的.

為解決DTN在短接觸時間下的路由問題，給出一種短相遇接觸時間網(wǎng)絡(luò)環(huán)境中的時延容忍網(wǎng)絡(luò)路由方案(routing scheme for delay tolerant network in Short Contact Duration Time network environment，SCDT).所給方案的基本思想主要是：首先，計算一跳傳遞概率和兩跳傳遞概率.主要是利用相遇接觸時間、相遇頻率以及消息尺寸等網(wǎng)絡(luò)信息來計算傳遞概率.其中，一跳傳遞概率是指將所攜帶的信息直接傳遞給目的節(jié)點；兩跳傳遞概率是指當前攜帶消息的節(jié)點利用相遇節(jié)點作為中間轉(zhuǎn)發(fā)節(jié)點向目的節(jié)點傳輸消息的概率.由于兩跳傳遞概率的主要目的是為了降低傳輸成本，也即通過減少傳輸成本提高DTN網(wǎng)絡(luò)帶寬利用率，所以若是一個節(jié)點能夠遇到比當前相遇節(jié)點更合適的轉(zhuǎn)發(fā)節(jié)點，那么其應(yīng)攜帶消息直至相遇到該節(jié)點.然后，依據(jù)所計算的概率在當前接觸節(jié)點和過去接觸節(jié)點中選擇下一跳轉(zhuǎn)發(fā)節(jié)點.仿真數(shù)據(jù)分析結(jié)果表明：所給SCDT路由方案能夠有效提高消息傳遞率、降低時延和路由成本.

2 約束條件

約束條件1.假定網(wǎng)絡(luò)中所有傳感器節(jié)點均有存儲緩沖功能，且DTN網(wǎng)絡(luò)為有限轉(zhuǎn)發(fā)帶寬.當任一傳感器節(jié)點在通信半徑內(nèi)與其他節(jié)點相遇，則該傳感器節(jié)點即能向所相遇到的這些節(jié)點轉(zhuǎn)發(fā)消息.假定節(jié)點的相遇接觸時間較短，且相遇接觸時間遠短于相遇間隔時間，其中相遇間隔時間是指節(jié)點平均每隔多長時間相遇一次，也即相遇頻率的倒數(shù).

約束條件2.所給SCDT方案服從單復(fù)本模型，即指網(wǎng)絡(luò)內(nèi)的消息在任何時刻的復(fù)本最多僅有一條.假定所需傳輸?shù)南⒊叽缦嗤覠o分割，若相遇接觸時間大于或等于消息尺寸與可能帶寬的比值，則表明消息被成功轉(zhuǎn)發(fā)，否則消息需在下次相遇機會重傳.

約束條件3.所需傳輸?shù)拿織l消息均包含一個有限時效(Time-To-Live，TTL)值，一旦當消息的TTL值失效，則即丟棄此消息.此外，相遇接觸時間和相遇間隔時間均服從指數(shù)分布，其參數(shù)分別為λ和θ.不同的兩個節(jié)點間具有不同的相遇頻率和相遇接觸時間.同時采用仿真軟件Cabspotting trace[6]進行系統(tǒng)仿真實驗來評估所給SCDT方案的性能.

3 計算傳遞概率

傳遞概率是指節(jié)點所攜帶的消息到達目的節(jié)點的可能性，與攜帶消息節(jié)點的當前位置和目的節(jié)點的通信半徑有關(guān).文獻[7]根據(jù)Random Waypoint運動模型，給出了任意時刻節(jié)點i的傳遞概率，如式(1)所示：

(1)

式中：d表示節(jié)點當前位置到目的節(jié)點的距離，R表示目的節(jié)點通信半徑.當R/d≥1時，節(jié)點i當前位置位于目的節(jié)點的通信范圍內(nèi)，此時傳輸概率為1；當R/d<1時，節(jié)點i當前位置位于目的節(jié)點的通信范圍之外，此時傳輸概率為R/d.節(jié)點主要根據(jù)其當前位置更新節(jié)點傳遞概率.所給SCDT路由方案在基于短相遇接觸時間情況下首先推導出直接一跳傳遞概率和兩跳傳遞概率.

3.1 直接一跳傳遞概率

令Yk為第k個相遇接觸時間的隨機變量，Hi為成功傳輸消息i所需的機遇接觸時間，其定義如式(2)所示.當Yk≥Hi表示消息i在第k次相遇機會成功傳輸，否則消息i需在下一個相遇機會內(nèi)重傳.

Hi=ωi/B

(2)

式中：ωi為消息i的尺寸，B為兩傳感器節(jié)點間的通信帶寬.

令Xk為第k個相遇間隔時間的隨機變量.所給SCDT路由方案假定第k個相遇接觸時間的隨機變量Xk遠遠大于第k個相遇間隔時間的隨機變量Yk，即Xk?Yk，也即假定相遇接觸時間極短，遠小于發(fā)生下一次相遇的時間間隔.

假定攜帶當前消息i的傳感器節(jié)點是s，而消息i所要到達的目的節(jié)點是d.那么消息i直至第n次相遇才成功傳輸至目的節(jié)點的概率Pi(n)，如式(3)所示：

(3)

因Xk和Yk均獨立，則式(3)可變換成式(4)：

(4)

下面通過對Pi(n)中的3項分別進行分析來計算式(4)：

(5)

(6)

(1-exp(-θs，dHi))…(1-exp(-θs，dHi))=

(1-exp(-θs，dHi))n-1

(7)

exp(-θs，dHi)

(8)

把上述式(6)-式(8)代入式(3)，則可得：

(1-exp(-θs，dHi))n-1×exp(-θs，dHi)

(9)

最后，消息i被成功傳輸?shù)母怕蔖i，如式(10)所示：

(10)

3.2 兩跳傳遞概率

兩跳傳遞概率是指由攜帶當前消息i的傳感器節(jié)點s通過中間節(jié)點?間接傳輸至目的節(jié)點d，如圖1所示.

圖1 兩跳傳遞模型Fig.1 Two-hop transfer model

為計算兩跳傳遞概率，傳感器節(jié)點s需計算兩個關(guān)鍵數(shù)據(jù)：1)需要計算傳感器節(jié)點s與中間節(jié)點相遇所消耗的時間.需要注意的是，與傳感器節(jié)點s相遇的中間節(jié)點必須是之前相遇過的，對于之前與傳感器節(jié)點s從未相遇過的節(jié)點，則無法計算出這一時間;2)需要計算中間節(jié)點與目的節(jié)點間的相遇率.這一數(shù)據(jù)的計算需通過網(wǎng)絡(luò)全局狀態(tài)信息交互，所以各傳感器節(jié)點需保存與其相遇節(jié)點的清單，具體的清單保存格式如式(11)所示：

(11)

式中：inter-contactrateλij為傳感器節(jié)點i和j間的相遇率，timestamp為傳感器節(jié)點i和j相遇率更新的時刻.

把中間節(jié)點融入傳遞概率的計算，則須相應(yīng)的修改式(3)，應(yīng)不僅包含節(jié)點s和中間節(jié)點?的相遇接觸時間和相遇間隔時間，同時也要包含中間節(jié)點?和目的節(jié)點d的相遇接觸時間和相遇間隔時間.假定節(jié)點s經(jīng)過n次相遇把消息i傳輸?shù)街虚g節(jié)點?，然后從?又經(jīng)過m次相遇把消息i傳輸?shù)侥康墓?jié)點d.因此，節(jié)點s通過中間節(jié)點?把消息i傳輸?shù)侥康墓?jié)點d時沒有過期的概率如式(12)所示：

(12)

然后根據(jù)逐項積分理論[9]計算式(12)，如式(13)所示：

(13)

式中：N=2，β1=λs，?，β=λ?，d，a1=n，a2=m.

節(jié)點s經(jīng)過n-1次相遇把消息i傳輸?shù)街虚g節(jié)點?以及中間節(jié)點?經(jīng)過m-1次相遇把消息i傳輸?shù)侥康墓?jié)點d失敗的傳遞概率計算如式(14)所示：

(1-exp(-θs，?Hi))n-1·(1-exp(-θs，dHi))m-1

(14)

節(jié)點s經(jīng)過n次相遇把消息i傳輸?shù)街虚g節(jié)點?以及中間節(jié)點?經(jīng)過m次相遇把消息i傳輸?shù)侥康墓?jié)點d成功的傳遞概率計算如式(15)所示：

=exp(-θs，?Hi-θ?，dHi)

(15)

根據(jù)式(13)-式(15)，則能計算出節(jié)點s經(jīng)過n次相遇把消息i傳輸?shù)街虚g節(jié)點?，然后中間節(jié)點?經(jīng)過m次相遇把消息i傳輸?shù)侥康墓?jié)點d成功的傳遞概率Pi(n，m)，如式(16)所示：

Pi(n，m)=A·(1-exp(-θs，?Hi)n-1)(1-exp(-θ?，dHi))m-1

·exp(-θs，?Hi-θ?，dHi)

(16)

因此，節(jié)點s把消息i經(jīng)過兩跳成功傳輸?shù)侥康墓?jié)點d的概率Pi如式(17)所示：

(17)

4 選擇下一跳路由

所給SCDT路由方案的關(guān)鍵步驟主要是如何選擇下一跳轉(zhuǎn)發(fā)節(jié)點.假定與源節(jié)點(攜帶消息節(jié)點)s相遇的節(jié)點集為V={?1，?2，…，?n}，但該節(jié)點集不包含目的節(jié)點，即?i≠d.若節(jié)點集包含目的節(jié)點，則表明源節(jié)點s已與目的節(jié)點d相遇，直接就能向其轉(zhuǎn)發(fā)所攜帶的消息.首先，交互節(jié)點的相遇節(jié)點集，然后根據(jù)式(10)分別單獨計算源節(jié)點s和鄰居節(jié)點?i的一跳傳輸概率，并記為Ps和P?i，最后每個?i向s傳遞其各自一跳傳輸概率P?i.

然后，令P?=max(P?1，P?2，…，P?k)，同時s應(yīng)判斷Ps是否大于P?.若存在Ps>P?，則表明源節(jié)點s不轉(zhuǎn)發(fā)所攜帶的消息，而是將消息存到緩存區(qū)；若存在Ps

圖2 消息轉(zhuǎn)發(fā)流程Fig.2 Message forwarding process

最后，令Pr=max(Pr1，Pr2，…，Prm).若存在P?>Pr，那么源節(jié)點s即可把其所攜帶的消息轉(zhuǎn)發(fā)到具有最大傳輸概率P?的當前鄰居節(jié)點?，接著?利用相同的策略把消息傳輸?shù)侥康墓?jié)點d.

綜上，源節(jié)點s選擇下一跳轉(zhuǎn)發(fā)節(jié)點F*的策略主要是從當前的一跳鄰居節(jié)點和當前未相遇但之前相遇過的二跳鄰居節(jié)點中尋找轉(zhuǎn)發(fā)概率最大的節(jié)點.整個消息轉(zhuǎn)發(fā)流程如圖2所示.

圖3 消息轉(zhuǎn)發(fā)示例Fig.3 Example of message forwarding

圖3的消息轉(zhuǎn)發(fā)示例演示了下一跳轉(zhuǎn)發(fā)消息的過程.節(jié)點s先計算一跳傳遞概率Ps，然后計算出當前一跳鄰居節(jié)點傳遞概率P?1.若存在Ps≥P?1，那么就再計算二跳傳遞概率Pr1.取P?1=max(Ps，Pr1，P?1)，節(jié)點?1即為下一跳轉(zhuǎn)發(fā)節(jié)點.

5 仿真性能分析

所給SCDT路由方案采用ONE 1.5.1[10]機會網(wǎng)絡(luò)仿真器進行仿真，并采用Cabspotting trace進行性能評估，其中Cabspotting包括533輛出租車的跟蹤文件.假定每個節(jié)點都有一定的緩沖容量，且在緩沖區(qū)初始存儲了5條尺寸為2MB的消息，全部消息均有相同的TTL值.每次仿真獨立重復(fù)20次，取平均值作最終的仿真結(jié)果.

為更好地評估所給SCDT路由方案性能，采用Epidemic[11]、PROPHET[12]、MEED[13]與BubbleRap[14]4種路由方案作為參照，主要比較消息傳遞率、平均時延與路由成本性能.其中消息傳遞率指成功傳輸?shù)南?shù)與總消息數(shù)之比；平均時延指消息從源節(jié)點傳輸?shù)侥康墓?jié)點所需的平均時間；路由成本指消息傳輸?shù)侥康墓?jié)點被轉(zhuǎn)發(fā)的次數(shù).

5.1 消息傳遞率

圖4給出了隨著消息時效變化，所給SCDT路由方案Epidemic、PROPHET、MEED和BubbleRap方案的消息傳遞率比較.由圖4可以看出，Epidemic路由方案的消息傳遞率最高，但這種高傳遞率是以較高的網(wǎng)絡(luò)資源為代價.當消息時效為14天時，所給SCDT路由方案的平均消息傳遞率是74%，分別比PROPHET、MEED與BubbleRap路由方案的平均消息傳遞率提高了10%、12%與13%.所給SCDT路由方案具有較高的消息傳遞率，主要是因為所給SCDT路由方案通過計算一跳傳遞概率和二跳傳遞概率，然后選擇傳輸概率最大的節(jié)點作為下一跳轉(zhuǎn)發(fā)節(jié)點，從而獲得了較高的消息傳遞率.

圖4 消息傳遞率隨TTL增加的變化情況Fig.4 Change of message delivery rate with the increase of TTL

5.2 平均時延

圖5給出了隨著消息時效變化，所給SCDT路由方案Epidemic、PROPHET、MEED與BubbleRap方案的平均時延比較.由圖5可以看出，Epidemic路由方案的平均時延最低，這主要是由于Epidemic路由方案采用泛洪策略決策路由，使得其建立路由的時間大為縮短.盡管所給SCDT路由方案的平均時延高于Epidemic路由方案的平均時延，然而與PROPHET、MEED和BubbleRap路由方案相比，其平均時延分別降低了5%、10%與12%.所給SCDT路由方案之所以有較高的平均時延，這主要是因為所給SCDT路由方案考慮了DTN網(wǎng)絡(luò)節(jié)點相遇接觸時間短的實際情況，通過計算源節(jié)點的相遇節(jié)點集合中消息的傳遞概率，在相遇節(jié)點集合中選擇最大傳遞概率的節(jié)點轉(zhuǎn)發(fā)消息，優(yōu)化了轉(zhuǎn)發(fā)節(jié)點選擇的方案，有效降低了消息傳輸?shù)钠骄鶗r延.

圖5 平均時延隨TTL增加的變化情況Fig.5 Change of average time delay with the increase of TTL

5.3 路由成本

圖6給出了隨著消息時效變化，所給SCDT路由方案Epidemic、PROPHET、MEED與BubbleRap方案的路由成本比較.由圖6可以看出，Epidemic路由方案具有最高的路由成本，同時結(jié)合圖4與圖5可以發(fā)現(xiàn)Epidemic路由方案是以高路由成本為代價來換取低時延與高消息傳遞率.而且由圖6也可以看出，所給SCDT路由方案具有最低的路由成本，與PROPHET、MEED和BubbleRap路由方案相比，其路由成本分別下降了14%、19%與23%.所給SCDT路由方案之所以有較低的路由成本，這主要是因為所給SCDT路由方案通過計算當前和之前相遇節(jié)點的傳遞概率，并據(jù)此優(yōu)化轉(zhuǎn)發(fā)節(jié)點選擇的方案，有效減少了消息被轉(zhuǎn)發(fā)的次數(shù)，從而降低了路由成本.

圖6 平均路由成本隨TTL增加的變化情況Fig.6 Change of average routing cost with the increase of TTL

根據(jù)圖4-圖6的仿真結(jié)果，可以看出所給SCDT路由方案在消息傳遞率、平均時延與路由成本方面的性能均較好.雖然所給SCDT路由方案的消息傳遞率與平均時延性能劣于Epidemic路由方案，然而其能夠比Epidemic路由方案更有效地控制路由成本，而與PROPHET、MEED與BubbleRap路由方案相比，所給SCDT路由方案不僅具有較低的路由成本，同時具有高消息傳遞率與低平均時延.

6 結(jié) 語

針對時延容忍網(wǎng)絡(luò)在真實環(huán)境中的相遇接觸時間通常很短這一事實，文中給出了一種短相遇接觸時間網(wǎng)絡(luò)環(huán)境中的時延容忍網(wǎng)絡(luò)路由方案.所給路由方案利用相遇接觸時間、相遇頻率以及消息尺寸等網(wǎng)絡(luò)信息首先計算一跳傳遞概率和兩跳傳遞概率，然后根據(jù)推導出的傳遞概率選擇下一跳轉(zhuǎn)發(fā)節(jié)點.仿真性能分析表明，所給SCDT路由方案能夠在保持較低的路由成本下，有效提高時延容忍網(wǎng)絡(luò)路由的消息傳遞率，同時具有較低的平均時延.因此，所給SCDT路由方案能夠較好地應(yīng)用于真實的延容忍網(wǎng)絡(luò)路由中，具有較好地實際應(yīng)用價值.下一步的研究工作主要是打算在冪次分布、對數(shù)正態(tài)分布和超指數(shù)分布推導出選擇轉(zhuǎn)發(fā)節(jié)點的規(guī)則公式，并結(jié)合緩沖區(qū)管理策略優(yōu)化路由方案.