面向地面DTN網絡的Prophet路由算法的優化與仿真*

朱人杰 谷代平 李莎莎 魏松杰 黃 炎 胡瑩熏

（南京理工大學計算機科學與工程學院 南京 210094）

1 引言

延遲容忍網絡（Delay Tolerant Networks，DTN）［1］提供了一種基于節點中繼、托管、轉發的，容遲容斷的網絡服務，最早被用于星際網絡（Interplanetary Network，IPN）中，以應對IPN中節點間歇性連接、易中斷、高誤碼率的情況。但隨著研究越來越深入，野生動物追蹤網絡、戰地網絡、鄉村網絡等等地面的挑戰網絡（Challenged Networks）場景下的DTN都成為了新的研究方向。

針對DTN網絡，研究者們提出了很多種路由算法：直接傳遞路由、基于洪泛的路由、基于概率的路由等。

直接傳遞路由，只有在攜帶消息的節點與目的節點能夠產生單跳連接時，攜帶消息的節點才會將消息傳遞給目的節點。這種路由方式消耗最少的網絡資源，全網只有一個副本，但是到達率也最低。

基于洪泛的路由，最典型的是Spray and Wait算法［2～3］、Epidemic［4］算法。Epidemic算法通過節點的接觸，無限制地將副本復制到沒有該副本的節點，最終將副本復制到目的節點，從而以巨大的資源代價完成消息的傳遞。而Spray and Wait則在Epidemic的基礎上限制了副本的數量，控制了網絡資源的浪費。

基于效用的路由。DTN路由算法的目的是讓數據包能盡快、盡可能地被目地節點接收，實現這一目的的其中一種辦法，就是將數據包轉發給更適合的中轉節點，而如何度量適合，則需要引入效用函數。最為著名的基于效用量化的路由算法是Lindgren A等提出的Prophet路由算法［5］，在Epi?demic算法的基礎上，引入了預測投遞概率作為效用函數，Bundle將僅被復制至預測投遞概率更高的節點。

基于社會性的路由?；谏鐣穆酚煽梢砸曌魇腔谛в寐酚傻难葸M。與一般的效用路由算法不同的是，社會路由算法將人類社會與DTN進行類比，以人與人之間的社會關系類比節點與節點之間的關系，利用社會學得到的社會知識進行路由選擇。典型的基于社會性的路由有Bubble Rap［6］算法。通過節點運動的社會性，優先將消息副本傳遞給與目的節點處于相同社交圈或者接近其社交圈的節點。這種算法將DTN網絡看作人的社交網絡，控制了網絡中的副本數，到達率適中。

在地面環境的DTN使用中，存在著諸如鄉村網絡、救援網絡、會議網絡、野生動物追蹤網絡等等使用環境，此類DTN網絡往往節點網絡資源有限并且節點運行不規律，難以形成群落，因此基于洪泛以及社會性的路由方法都難以適用于此類網絡。此時，基于效用的路由算法是一個好的解決方案。本文基于經典的效用量化路由算法——Prophet路由算法，在其基礎上充分考慮節點的性能差異、狀態差異，通過節點的傳輸速率、緩存區大小以及歷史平均轉發成功率，在保證傳輸性能、存儲性能的基礎上再進一步規避了Prophet路由算法的“停車場問題”［7］，從而提升了傳輸的效率以及成功率。

2 相關工作

2.1 延遲容忍網絡

2007年，由IRTF的DTNRG研究 組發 布 的 與DTN網絡體系結構相關的規范文檔RFC4838，分析了TCP/IP協議棧在受限網絡環境下失效的原因，并在此基礎上提出了區別于TCP/IP協議棧的DTN協議棧［8］，如圖1所示。

圖1 DTN協議棧

通過Bundle協議的托管重傳機制、后綁定機制，LTP協議的區分紅綠數據、紅部數據接收檢查等功能，DTN實現了消息的逐跳、容遲容斷傳輸、不基于連接的安全傳輸等功能。

雖然方案最初是面向空間網絡，但是在地面受限網絡環境，如戰場環境［9～10］、救援環境［11～12］、車聯網［13］、野生動物追蹤［14］等應用場景中，高延時、時斷時續的鏈路、高誤碼率等因素也與空間網絡十分相似，因此DTN也被在這些背景下被廣泛研究。

2.2 Prophet路由算法

Prophet路由算法由三個主要公式構成，分別為相遇概率增加公式、相遇概率衰減公式以及傳遞概率公式。針對Prophet路由算法的優化一般是對相遇概率增加公式的優化。

1）式（1）給出了Prophet原有的相遇概率的增加規律，兩個節點的每一次相遇，它們都會更新自己與對方的相遇概率，在原有基礎上進行增加：

其中P(a，b)old為a節點與b節點的原有相遇概率，Pinit∈[0，1]為初始化常量，本文中取其值為0.45。

2）兩個節點的相遇概率隨著時間的推移衰減。式（2）給出了相遇概率隨時間衰減的規律。

其中時間老化常數γ∈(0，1)，k是當前距離上次相遇的時間間隔。

3）雖然DTN中的路由算法是逐跳計算的路由算法，但是依然需要考慮消息的傳遞概率。如果節點a需要傳遞消息給節點b，當它遇到經常與節點b相遇的節點c，將節點c作為中繼節點是一個好的選擇。式（3）說明了節點的傳遞概率是如何影響相遇概率的。

其中傳遞常量β∈(0，1)，決定了傳遞概率對相遇概率的影響的大小。

3 基于節點差異的Prophet-BSAS路由算法

3.1 算法改進邏輯

Prophet路由算法進行下一跳節點路由判斷的基準在于P（A，destination）與P（B，destination）的比較，即A節點與目標節點相遇的預測概率和B節點與目標節點相遇的預測概率的比較。當攜帶消息的節點A與節點B相遇，節點B能夠將數據包的傳輸到目標節點的概率高于A，則A將數據包的副本傳輸給節點B。

但是不同于空間DTN網絡，這些新的應用領域已經發生了極大的變化，同時也產生了許多新的挑戰。與空間DTN相比，新的應用場景通常節點運動不規律、軌跡難以預測，信息產生不均勻且信息量較大，節點種類更加多樣、性能差異較大。即便是具有相同相遇概率的節點，它們的性能差異與各自當前的狀態差異也會造成傳輸成功率的巨大差異，所以只是簡單通過相遇次數計算相遇概率的Prophet算法有很多其他可以考慮的因素，可以在保證可靠性的同時提升傳輸的效率與成功率。

首先，考慮到各節點本身帶寬資源、傳輸能力的差別，通過將節點傳輸峰值速率加入考量范疇，可以優先選擇傳輸速率更快的節點，提升傳輸的效率。在有限的接觸次數與接觸時間內，將節點緩存的數據最多地傳輸到更優節點。

其次，考慮節點的緩存區大小，優先選擇剩余緩存區大的節點，從而防止因為緩存區充滿導致的消息丟失。

最后，是節點數據平均轉發成功率的考慮。Prophet算法在進行下一跳節點的選擇時，考慮的僅僅是下一跳節點與目標節點的相遇次數，忽略了相遇之后，節點之間連接維系的時間、連接的穩定性。在地面網絡中，各個節點的性能、運動參數往往更為復雜，所以經常出現一些“偽優質”節點，這類節點可能雖然經常接觸到可傳輸的下一跳節點，但是由于接觸時間短、CPU性能差等原因，傳輸的成功率卻很低，也就是前文所提到的“停車場問題”。而將節點數據平均轉發成功率加入考慮，可以盡可能地去規避這樣的“偽優質”節點。

3.2 算法整體流程

如圖2所示，當攜帶消息的節點A在運動過程中遭遇一個新的節點B，節點A將通過以下流程決定是將消息轉發給節點B還是繼續運動，等待更優質的節點。

圖2 判斷流程圖

3.3 具體改進

1）節點傳輸速率的處理。要將節點傳輸峰值速率加入到P(a，b)的考量中，需要對峰值速率V進行歸一化處理，本文中使用線性函數歸一化處理峰值速率。

其中Vmin是傳輸速度的最低值，停止發送時速度最低，所以Vmin為0。Vmax為節點自身能達到的數據傳輸上限，它通常由節點CPU性能、網口速率等因素中的短板決定。

2）節點剩余緩存區的計算。各個節點將節點剩余緩存區的容量進行歸一化處理，在歸一化后得到變量MbufferNorm，該變量與節點剩余緩存區容量成正比。MbufferNorm越大的節點，越容易被選擇為下一跳節點。

其中Mrest剩余緩存區的大小，單位為MB。這里MbufferNorm∈[0，1)。

3）節點數據平均轉發成功率的計算。節點需要進行處理的數據總量與成功轉發的數據總量的統計，即進入節點的數據包的數據總量與節點自己產生的數據包的數據總量之和以及成功轉發的數據總量：

m.getsize()表示獲取數據包的大小，n、m、p分別表示截至目前時間，節點接收到的數據包總數，節點產生的數據包總數以及成功轉發的數據包總數。在得到這兩個數據后，計算本節點平均轉發成功率。

4）在得到這些數據之后，我們可以將節點的傳輸速率、節點中消息的平均排隊時間以及節點數據包轉發的歷史成功率的計算加入到相遇概率P(a，b)的計算中，對式（1）優化：其中變量μ∈[0，1]，且滿足Pinit+μ∈[0，1]。本文中μ的值取為0.4。

4 仿真實驗

4.1 仿真環境

實驗使用的仿真工具為ONE-1.5.1。仿真采用的數據集是INFOCOM06數據集，INFOCOM06數據集是在2006年巴薩羅納INFOCOM會議上收集的，數據集包含了各節點在會議期間的連接信息。節點包括了17個布置在整個區域內的設備，3個長期放置在電梯內的設備以及78個由參會的人員攜帶的設備。具體參數如表1所示。

表1 仿真參數

為了更好地分析實驗結果，本文首先分析了infocom06數據集連接個數隨時間的變化，結果如圖3所示，在白天，整個網絡中的連接數較多，在進入夜間后，網絡中的連接數變少。

圖3 網絡中連接數

4.2 評估指標

本文選用以下四種指標對路由方法性能進行測試：數據到達率、網絡開銷比、傳輸平均時延與平均跳數。

數據到達率Psuc：成功到達的數據總量與所有節點產生的數據總量的比值，計算公式如下：

其中Dsuc表示成功到達的數據量，Dgen表示所有節點產生的數據總量。

網絡開銷比POverheadRatio：沒有被成功投遞到目標節點的消息數據總量與成功投遞到目標節點的消息數據總量之差，與成功投遞到目標節點的數據總量的比值，用來衡量為了成功傳遞消息而需要進行額外傳遞消息的概率。

其中Drelay表示網絡中被轉發的數據總量。

傳輸平均時延Tavg：被成功遞交的消息從產生到被成功遞交所用的平均時間，計算公式如下：

其中Tx，a表示第x個成功遞交的數據包的到達時間，Tx，gen表示第x個成功遞交的數據包的生成時間。

平均跳數CHopAvg：消息從源節點到目標節點所經歷的平均跳數，計算公式如下：

其中Ck，hop表示第k個到達目的節點的數據包經歷的跳數。

4.3 仿真結果

4.3.1 遞交成功率

圖4 給出了在不同仿真時間內，五種不同的路由協議的遞交成功率，由于數據集在開始記錄的1小時之后才開始收到節點的連接信息，所以仿真也在1h之后開始記錄結果。從圖中可以看到，在遞交成功率方面，Prophet-BSAS在幾乎所有時間內都優于其他路由協議。

圖4 遞交成功率

使得Prophet-BSAS具有較高的遞交成功率的主要原因是，Prophet-BSAS考慮了節點的性能差異，優先考慮了傳輸速率較高、數據傳輸成功率較高的節點，在得到傳輸機會時，可以較好地將數據包進行轉發；選擇緩存區充足的節點，在沒有傳輸機會或者傳輸中斷時，可以將數據存儲、等待下一次轉發，不易發生數據的丟失。

4.3.2 網絡開銷比

圖5 給出了在不同仿真時間內，五種路由協議的網絡開銷比的比較。Spray and Wait路由協議雖然已經人為控制了網絡中的副本總數，但是副本總數的控制與遞交成功率的沖突使得Spray and Wait的網絡開銷比不能控制在低水準?；谏缃坏腂ubble rap與基于機會的Prophet網絡開銷比較為接近，而Prophet-BSAS在網絡開銷比方面展示了極佳性能。

圖5 網絡開銷比

主要原因是在地面DTN網絡環境中，更為全面的篩選條件在選取優質節點作為下一跳節點的同時，有效控制了網絡中副本的數量。

4.3.3 平均時延

如圖6所示，雖然由于在建立連接之后、傳輸消息之前，基于相遇概率的路由算法需要進行節點之間相遇概率的交換，所以天然地會使得傳輸時延有所提高，但是由于Prophet-BSAS選擇的節點綜合性能更為優質，傳輸速率較高、重傳次數較少，所以Prophet-BSAS在有一定的連接時間保障的前提下，可以很好地傳輸大量數據。從圖中可見，在平均時延方面比Prophet-BSAS比Prophet降低了1700s左右。

圖6 平均時延

4.3.4 平均跳數

圖7 給出了五種路由協議在平均跳數方面的比較，由于Prophet-BSAS選取的節點傳輸速率較高、緩存區容量充足，不容易發生數據包傳輸中途失敗，需要重傳的情況；同時，對于傳輸成功率低的偽優質節點的過濾，也使得傳輸更加高效。三者綜合，Prophet-BSAS能更準確地選擇出更好的下一跳，從而降低了傳輸的平均跳數。Prophet-BSAS的平均跳數在2.5跳左右，優于Prophet的3跳以及Bubble Rap的3.5跳。

圖7 平均跳數

5 結語

本文從地面DTN網絡的實際情況出發，分析了其與空間DTN網絡的主要差異——節點的性能與狀態更為復雜多樣，進而在Prophet路由協議的基礎上，針對會影響傳輸的性能與成功率的三點進行了優化。優先選擇傳輸成功率高的節點，使得在短暫的連接時間中，可以傳輸盡可能多的數據。優先選擇緩存區充足的節點，使得在沒有傳輸機會或者傳輸中斷時，有充足的空間緩存數據，降低數據的丟失概率。優先選擇平均轉發成功率高的節點，規避雖然有較高的相遇概率但是傳輸性能較差的節點。最后通過ONE仿真，將改進的路由算法與其他算法進行了性能對比，證明了改進后的方案提高了遞交成功率，降低了網絡開銷比與平均跳數。