馬 慧，李 濤

(南京郵電大學 通信與信息工程學院，江蘇 南京 210003)

0 引 言

延遲容忍網(wǎng)絡(delay tolerant network，DTN)[1]作為一種新型的網(wǎng)絡架構，有別于傳統(tǒng)的TCP/IP網(wǎng)絡，是一種間歇性連接的網(wǎng)絡，大多數(shù)情況不存在端到端的傳輸路徑。即使存在端到端的傳輸路徑，也比較容易中斷[2]。由于DTN網(wǎng)絡的間斷性連接，易中斷的特殊通信環(huán)境，傳統(tǒng)的TCP/IP協(xié)議并不適用于該網(wǎng)絡。為了更高效地傳遞消息，DTN網(wǎng)絡主要采用存儲-攜帶-轉發(fā)的機制[3]。隨著DTN網(wǎng)絡受到越來越多的關注，DTN的應用領域也越來越廣泛，如野生動物追蹤和棲息地檢測傳感器網(wǎng)絡[4]、鄉(xiāng)村通信網(wǎng)絡[5]、星際網(wǎng)絡[6-7]、激光通信[8]等。

DTN網(wǎng)絡的路由協(xié)議、節(jié)點傳輸協(xié)議和安全等方面受到了專家和學者的重視。DTN路由[9]作為DTN網(wǎng)絡研究的重要方面，面臨的主要挑戰(zhàn)是如何在時延大、誤碼率高、節(jié)點分布較稀疏和不對稱的數(shù)據(jù)速率的網(wǎng)絡中消耗更少的網(wǎng)絡資源，傳遞更多的消息。而在傳統(tǒng)的TCP/IP路由協(xié)議中，消息轉發(fā)則是一個相對較容易的任務，消息轉發(fā)給到達目的節(jié)點最短路徑上的一個鄰居節(jié)點，路徑的可靠性相對較高，傳遞成功率也相對較高。而在DTN網(wǎng)絡中，這些傳統(tǒng)的路由協(xié)議是不適用的。經(jīng)過多年的研究，國內外的專家和學者們給出了很多適合于DTN網(wǎng)絡的各具特色的路由算法。其中，比較典型的主要有：DirectDelivery[10]、Epidemic[11]、Prophet[12]和Spray-and-Wait[13]。

直接傳輸(DirectDelivery)在DTN網(wǎng)絡當中是最簡單的一種單拷貝路由方式。直接傳輸?shù)闹饕硎窃垂?jié)點持有傳輸消息，直到源節(jié)點遇到目的節(jié)點，源節(jié)點才將該消息發(fā)送給目的節(jié)點。直接傳輸?shù)闹饕秉c在于消息完全依賴于源節(jié)點和目的節(jié)點的直接相遇，由于DTN網(wǎng)絡的特殊環(huán)境導致消息的傳輸延遲較大，消息易丟失，投遞率較低。傳染路由(Epidemic)的主要原理是攜帶消息的節(jié)點將消息復制轉發(fā)給相遇的所有節(jié)點，試圖用更多的傳遞次數(shù)來換取消息的投遞成功率。

顯然，相比直接傳輸，雖然傳染路由不依賴于源節(jié)點和目的節(jié)點的直接相遇，但是由于傳染路由的傳染性，會導致網(wǎng)絡中消息過多，占用太多的系統(tǒng)資源，網(wǎng)絡開銷較大。對于Prophet路由算法，概率路由比傳染路由在算法上要復雜很多，主要是利用節(jié)點到目的節(jié)點的歷史傳遞概率來計算節(jié)點當前到目的節(jié)點的傳遞概率。當兩個節(jié)點相遇時，通過比較兩節(jié)點與目的節(jié)點的接觸概率，來決定攜帶消息的節(jié)點是否要把消息傳遞給相遇節(jié)點。Spray-and-Wait是一種基于消息拷貝的路由算法。通過控制傳遞消息副本的數(shù)量來減少報文在網(wǎng)絡當中的冗余量，同時增加了消息的傳遞成功率。

在上述研究的基礎上，文中給出了基于節(jié)點的歷史吞吐率的Prophet路由策略，并對其進行了仿真。

1 Prophet路由

Prophet是一種基于概率的路由協(xié)議。Prophet路由認為，節(jié)點的移動并不是盲目的和隨機的，而是遵循一定的規(guī)律。當一個節(jié)點在某一時刻遇到另一個節(jié)點，那么這兩個節(jié)點可能在之后的一段時間內還可能以某一概率相遇。所以在Prophet路由算法中，每個節(jié)點都會維護一張轉發(fā)概率表，當一個攜帶節(jié)點遇到另一個節(jié)點，節(jié)點并不是盲目地將消息轉發(fā)給相遇節(jié)點，而是通過概率轉發(fā)表來預先估計節(jié)點到達目的節(jié)點的傳送預測概率，通過比較概率值來決定是否要把消息傳遞給相遇節(jié)點。

在Prophet路由中，一個主要的性能指標是P(a,b)∈[0,1]，它表示節(jié)點A能夠傳輸消息到節(jié)點B的預測概率。當節(jié)點A和節(jié)點C相遇時，兩個節(jié)點相互交換各自的預測向量，用來決定是否要把消息傳輸給相遇節(jié)點。其中，預測向量包含了節(jié)點到達其他所有節(jié)點的傳遞概率預測信息。也就是當攜帶消息的節(jié)點A和節(jié)點C相遇時，通過預測概率判斷節(jié)點A和節(jié)點C與目的節(jié)點B的接觸概率，如果節(jié)點C傳輸消息到達目的節(jié)點B的預測概率大于節(jié)點A傳輸消息到達目的節(jié)點B的預測概率時，節(jié)點A將會把消息傳輸給節(jié)點C。

傳遞概率的計算過程主要包括三個步驟:

(1)當兩個節(jié)點相遇時，更新節(jié)點的預測向量。相遇越頻繁的節(jié)點，傳遞的可能性越高，如式1所示。

P(a,b)=P(a,b)old+(1-P(a,b)old)×Pinit

(1)

其中，Pinit∈[0,1]是初始化常數(shù)，通常取值為0.98；P(a,b)old表示節(jié)點a和節(jié)點b上一狀態(tài)的相遇概率。

(2)當兩個節(jié)點長時間沒有相遇，那么，兩個節(jié)點的傳遞概率就會降低。所以隨著時間的推移，兩節(jié)點的傳遞概率不斷減少。式2描述了兩節(jié)點的傳遞概率隨時間的變化關系。

P(a,b)=P(a,b)old×γk

(2)

其中，γ是一個時間老化常數(shù)，在[0,1)間取值;k是本次距離上次更新的時間間隔。

(3)考慮到節(jié)點的傳遞性，設想下面一種情況:如果節(jié)點A經(jīng)常遇到節(jié)點B，節(jié)點B經(jīng)常遇到節(jié)點C，那么，有理由相信節(jié)點A和節(jié)點C的相遇概率也應該較高一些。根據(jù)式3可以計算出節(jié)點A和節(jié)點C之間的傳遞概率。

P(a,c)=P(a,c)old+(1-P(a,c)old)×

P(a,b)×P(b,c)×β

(3)

其中，β是一個放大常數(shù)，決定了節(jié)點的傳遞性對節(jié)點的傳遞概率將產(chǎn)生多大的影響。

2 改進的Prophet路由算法(Enhanced Prophet，E-Prophet)

DTN網(wǎng)絡特殊的網(wǎng)絡環(huán)境使得節(jié)點的性能受到很大的影響。網(wǎng)絡中節(jié)點的能量、帶寬和自身緩存等的限制可能會導致節(jié)點不能成功地把消息傳遞給目的節(jié)點。而節(jié)點的歷史吞吐率在一定程度上反映了一個節(jié)點性能的好壞。所以文中考慮了節(jié)點自身的歷史吞吐率[14]對節(jié)點消息轉發(fā)概率的影響，在原有Prophet路由的基礎上做出改進。把節(jié)點的歷史吞吐率定義為：一個節(jié)點在當前時間之前所成功傳輸消息的數(shù)據(jù)總和與該節(jié)點作為中繼節(jié)點接收到的消息和該節(jié)點自身產(chǎn)生的消息的數(shù)據(jù)總和的比值。

設想下面一種情況，一個節(jié)點攜帶消息，試圖在網(wǎng)絡中傳遞該消息給目的節(jié)點，當前節(jié)點遇到一個中繼節(jié)點時，假設在Prophet路由算法當中經(jīng)過計算得知，該節(jié)點和相遇的中繼節(jié)點傳遞該消息到目的節(jié)點的概率相同，但是如果相遇的中繼節(jié)點的歷史吞吐率比當前節(jié)點的歷史吞吐率大，那么有理由相信歷史吞吐率較高的相遇節(jié)點應該要比歷史吞吐率相對較低的當前節(jié)點擁有更高的傳遞概率，所以當前節(jié)點應該把消息傳遞給相遇節(jié)點。文中就是在此假設的基礎上，把節(jié)點的歷史吞吐率作為Prophet路由算法的一個影響因子，通過改進Prophet路由算法，使得消息的傳遞效率比之前要提高一些。

具體實現(xiàn)是：在每一個節(jié)點當中記錄該節(jié)點在當前時間之前成功轉發(fā)的所有消息數(shù)據(jù)大小與該節(jié)點作為中繼節(jié)點接收到的所有消息數(shù)據(jù)大小和節(jié)點產(chǎn)生的所有消息數(shù)據(jù)大小的比值，即節(jié)點的歷史吞吐率。把計算出的歷史吞吐率這一性能指標作為一個增長因子加入式1。

節(jié)點作為中繼節(jié)點接收到的消息的計算公式為：

(4)

當節(jié)點作為一個中繼節(jié)點成功接收到一個消息時，獲取該消息的大小，并計算在當前時間之前該節(jié)點接收到的所有消息的數(shù)據(jù)總和。Received{mi.getsize()}表示在當前時間之前收到的一個消息的數(shù)據(jù)大小；n1表示當前時間之前該節(jié)點成功接收到的消息總數(shù)。

節(jié)點作為源節(jié)點產(chǎn)生的消息的計算公式為：

(5)

當節(jié)點產(chǎn)生一個消息時，獲取該消息的數(shù)據(jù)大小，并計算在當前時間之前該節(jié)點產(chǎn)生的所有消息的數(shù)據(jù)總和。Created{mi.getsize()}表示該節(jié)點在當前時間之前產(chǎn)生的一個消息的數(shù)據(jù)大小；n2表示當前時間之前該節(jié)點產(chǎn)生的所有消息總數(shù)。

節(jié)點成功傳輸?shù)南⒌挠嬎愎綖椋?/p>

(6)

當節(jié)點成功傳送了一個消息時，獲取該消息的大小，并計算當前時間之前該消息成功傳送的所有消息的數(shù)據(jù)總和。Transferred{mi.getsize()}表示該節(jié)點在當前時間之前成功傳送的一個消息的數(shù)據(jù)大小；n3表示當前時間之前該節(jié)點成功傳輸?shù)乃邢⒌目倲?shù)。

所以節(jié)點的歷史吞吐率的計算公式為：

(7)

式1改進后為：

P(a,b)=P(a,b)old+(1-P(a,b)old)×

Pinit×α

(8)

其中

α=(1+HtHt)/2

(9)

其中，Ht表示節(jié)點的歷史吞吐率。由于Ht≤1,所以1+HtHt≤2，(1+HtHt)/2≤1,由此保證了P(a,b)≤1。當該節(jié)點未成功傳送消息時，式8將退化為式1。

當攜帶消息的節(jié)點遇到一個中繼節(jié)點，在攜帶消息的節(jié)點到目的節(jié)點的傳遞概率和中繼節(jié)點到目的節(jié)點的傳遞概率相同的情況下，當中繼節(jié)點的歷史吞吐率比當前攜帶消息的節(jié)點的歷史吞吐率大時，由式8可知，由該中繼節(jié)點傳送成功的概率大于自身節(jié)點直接傳送的概率，那么攜帶消息的節(jié)點應該把消息傳遞給相遇的中繼節(jié)點，經(jīng)由該中繼節(jié)點把消息傳送到目的節(jié)點。通過仿真可以看出，改進后的概率路由算法相比原始的概率路由算法在消息的遞交率、傳輸時延和開銷率都有所提高。

3 仿 真

3.1 仿真環(huán)境設置

文中采用one仿真[15-16]平臺來評估Prophet路由和E-Prophet路由的性能。one是基于Java語言開發(fā)的專用于仿真DTN路由的一款仿真工具。仿真采用one自帶的赫爾辛基市的地圖。區(qū)域大小為4 500 m×3 400 m。在區(qū)域中放置了126個節(jié)點，這些節(jié)點被分為6組。其中第一組和第三組為行人，每一組包含40個節(jié)點，共80個節(jié)點，移動速度范圍為0.5～1.5 m/s，節(jié)點緩存大小為5 MB，移動模型為基于地圖最短路徑移動；第二組為出租車，含有40個節(jié)點，移動速度范圍為2.7～13.9 m/s，節(jié)點緩存大小為5 MB，移動模型為基于地圖最短路徑移動；第四組、第五組和第六組為有軌電車，每一組包含2個節(jié)點，總共6個節(jié)點，移動速度范圍為7～10 m/s，緩存大小為50 MB，移動模型為基于地圖的固定路徑移動；消息產(chǎn)生的時間間隔設置為25～35 s；消息的大小設置為350～500 k；節(jié)點采用藍牙設備進行傳輸，其傳輸范圍為10 m，傳輸速度為250 Kbit/s。當緩沖區(qū)已滿時，節(jié)點不會再接收新消息，直到一些舊的消息從緩沖區(qū)被刪除。

3.2 網(wǎng)絡性能指標

在DTN中，為了能夠更好地評判路由的好壞，往往采用一些合理的性能指標對不同的路由進行性能評估。文中主要采用消息遞交率、網(wǎng)絡開銷率和平均時延來評價Prophet路由和E-Prophet路由的性能。

(1)消息遞交率。定義為DTN網(wǎng)絡中成功遞交的消息數(shù)和總的消息投遞數(shù)的比值。路由的作用就是要把一個消息送達目的節(jié)點，所以遞交率是一個很重要的性能指標。

Delivery_rate=Delivered/Created

(10)

其中，Delivery_rate表示消息的遞交率；Delivered表示DTN網(wǎng)絡中成功傳遞到目的節(jié)點的消息總數(shù)；Created表示在源節(jié)點生成的所有消息總數(shù)。

(2)網(wǎng)絡開銷率。定義為沒有被成功投遞到目的節(jié)點的消息與被成功投遞到目的節(jié)點的消息數(shù)量的比值。此參數(shù)用來評價成功傳輸消息而要額外傳遞的消息的概率。該參數(shù)越小，網(wǎng)絡開銷越小。

(11)

其中，Overhead_ratio表示網(wǎng)絡的開銷率；Relayed表示網(wǎng)絡中沒有被成功投遞到目的節(jié)點的消息總數(shù)；Delivered表示網(wǎng)絡中被成功投遞到目的節(jié)點的消息數(shù)量的比值。

(3)平均時延。定義為所有成功遞交的消息從源節(jié)點到目的節(jié)點花費的平均時間。平均時延越小，表示節(jié)點從源節(jié)點到目的節(jié)點所花費的時間越少。在DTN網(wǎng)絡中，這是一個很重要的參數(shù)。

(12)

其中，Latency_avg表示消息的平均時延；tid表示消息i被目的節(jié)點接收到的時間；tis表示消息i在源節(jié)點生成的時間；n表示被目的節(jié)點成功接收到的消息的總數(shù)目。

3.3 仿真結果

采用one對在DTN網(wǎng)絡中常用的Prophet路由和改進的E-Prophet路由進行了仿真和比較。兩種路由協(xié)議在DTN中的消息遞交率、開銷率、傳輸時延三種性能指標的變化趨勢如圖1～3所示。

由圖1可以看出，隨著仿真時間的增加，兩種協(xié)議的遞交率也在增加。仿真剛開始時，節(jié)點的吞吐率并沒有顯現(xiàn)出來，這可能是因為仿真剛開始時各節(jié)點的性能差異并未顯現(xiàn)出來。隨著仿真時間的增加，各節(jié)點的性能差別逐漸顯現(xiàn)，節(jié)點的歷史吞吐率在一定程度上反映了一個節(jié)點在性能上的優(yōu)劣，所以改進的Prophet路由表現(xiàn)了比未考慮節(jié)點吞吐率更好的性能。

圖1 兩種路由的消息遞交率

圖2 兩種路由的開銷率

圖3 兩種路由的平均時延

由圖2可以看出，隨著仿真時間的增加，兩種協(xié)議的網(wǎng)絡開銷都在不斷增加。E-Prophet的網(wǎng)絡開銷增加相比Prophet要慢。由公式可以看出，吞吐率大的節(jié)點相對概率也會高，從而路由將選擇出節(jié)點性能相對更好的節(jié)點來傳輸消息，所以E-Prophet路由相對普通的Prophet所需要的網(wǎng)絡開銷更少。

由圖3可以看出，仿真開始時，E-Prophet路由的平均時延并沒有表現(xiàn)出很好的性能，這可能是因為首先由于路由當中加入了對節(jié)點吞吐率的判斷，攜帶消息的節(jié)點在選擇中繼節(jié)點時需要計算中繼節(jié)點的吞吐率，所以會導致一定的時間開銷。然后，在仿真開始時節(jié)點之間的吞吐率性能差異不大，根據(jù)節(jié)點的吞吐率不能很好地判斷出節(jié)點的優(yōu)劣。但是隨著時間的增加，各節(jié)點的吞吐率差異逐漸增大，節(jié)點的吞吐率可以在一定程度上反映一個節(jié)點的優(yōu)劣，所以消息到達目的節(jié)點的時延會相對減少。平均來講，隨著仿真時間的增加，改進的E-Prophet的平均時延會比傳統(tǒng)Prophet路由的平均時延要小。

E-Prophet路由考慮到了網(wǎng)絡節(jié)點的歷史吞吐率對消息傳輸概率的影響，通過改進Prophet路由算法提高了消息的傳遞成功率。仿真結果表明，E-Prophet路由在遞交率、網(wǎng)絡開銷和平均時延上表現(xiàn)出了比Prophet更好的性能。

4 結束語

由于DTN中節(jié)點的特殊性及所處的特殊網(wǎng)絡環(huán)境，節(jié)點的性能會對節(jié)點成功傳遞消息產(chǎn)生很大的影響。因此考慮節(jié)點性能對消息傳輸?shù)挠绊懯鞘直匾摹Ｍㄟ^改進DTN網(wǎng)絡原有的Prophet路由改善了節(jié)點傳輸消息的成功概率、開銷率等。仿真實驗表明，與原有的Prophet路由相比較，改進后的E-Prophet路由在遞交率、網(wǎng)絡開銷和平均時延三方面都有了一定的改進。但是由于DTN網(wǎng)絡的不穩(wěn)定性，導致距離當前時間很遠的節(jié)點性能對當前節(jié)點性能的參考價值不是很大，所以該方法也具有一定的不準確性。因此下一步的研究工作是根據(jù)時間分段來優(yōu)化該路由策略，弱化距離當前時間很長的節(jié)點性能對當前節(jié)點性能的影響，以達到更好的路由效果。