基于吞吐率的Prophet路由在DTN中的應用

馬 慧，李 濤

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

0 引 言

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

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

直接傳輸(DirectDelivery)在DTN網絡當中是最簡單的一種單拷貝路由方式。直接傳輸的主要原理是源節點持有傳輸消息，直到源節點遇到目的節點，源節點才將該消息發送給目的節點。直接傳輸的主要缺點在于消息完全依賴于源節點和目的節點的直接相遇，由于DTN網絡的特殊環境導致消息的傳輸延遲較大，消息易丟失，投遞率較低。傳染路由(Epidemic)的主要原理是攜帶消息的節點將消息復制轉發給相遇的所有節點，試圖用更多的傳遞次數來換取消息的投遞成功率。

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

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

1 Prophet路由

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

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

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

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

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

(1)

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

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

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

(2)

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

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

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

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

(3)

其中，β是一個放大常數，決定了節點的傳遞性對節點的傳遞概率將產生多大的影響。

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

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

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

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

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

(4)

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

節點作為源節點產生的消息的計算公式為：

(5)

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

節點成功傳輸的消息的計算公式為：

(6)

當節點成功傳送了一個消息時，獲取該消息的大小，并計算當前時間之前該消息成功傳送的所有消息的數據總和。Transferred{mi.getsize()}表示該節點在當前時間之前成功傳送的一個消息的數據大小；n3表示當前時間之前該節點成功傳輸的所有消息的總數。

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

(7)

式1改進后為：

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

Pinit×α

(8)

其中

α=(1+HtHt)/2

(9)

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

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

3 仿 真

3.1 仿真環境設置

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

3.2 網絡性能指標

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

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

Delivery_rate=Delivered/Created

(10)

其中，Delivery_rate表示消息的遞交率；Delivered表示DTN網絡中成功傳遞到目的節點的消息總數；Created表示在源節點生成的所有消息總數。

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

(11)

其中，Overhead_ratio表示網絡的開銷率；Relayed表示網絡中沒有被成功投遞到目的節點的消息總數；Delivered表示網絡中被成功投遞到目的節點的消息數量的比值。

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

(12)

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

3.3 仿真結果

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

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

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

圖2 兩種路由的開銷率

圖3 兩種路由的平均時延

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

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

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

4 結束語

由于DTN中節點的特殊性及所處的特殊網絡環境，節點的性能會對節點成功傳遞消息產生很大的影響。因此考慮節點性能對消息傳輸的影響是十分必要的。通過改進DTN網絡原有的Prophet路由改善了節點傳輸消息的成功概率、開銷率等。仿真實驗表明，與原有的Prophet路由相比較，改進后的E-Prophet路由在遞交率、網絡開銷和平均時延三方面都有了一定的改進。但是由于DTN網絡的不穩定性，導致距離當前時間很遠的節點性能對當前節點性能的參考價值不是很大，所以該方法也具有一定的不準確性。因此下一步的研究工作是根據時間分段來優化該路由策略，弱化距離當前時間很長的節點性能對當前節點性能的影響，以達到更好的路由效果。