節(jié)點緩存感知的DTN 概率路由算法

鐘 贇，夏靖波，付 凱，尹 譯，李智偉

（1.空軍工程大學 信息與導航學院，陜西 西安710077；2.75150部隊，湖南 衡陽421131）

0 引 言

在容遲容斷網(wǎng)絡 （DTN）［1］中，節(jié)點分布稀疏、移動頻繁且緩存和能量有限，傳統(tǒng)的路由算法并不適用。消息的傳遞主要采用 “store－carry－forward” （存儲－攜帶－轉(zhuǎn)發(fā)）機制，通過中繼節(jié)點傳送給目的節(jié)點，常用于農(nóng)地數(shù)據(jù)收集網(wǎng)絡［2］、車載網(wǎng)絡［3］和水下網(wǎng)絡［4］等延遲較大、網(wǎng)絡拓撲多變的網(wǎng)絡環(huán)境。

目前，研究人員提出的典型DTN 路由算法包括Epidemic算法、PROPHET 算法以及Spray and Wait算法。Epidemic傳染機制算法中，每個節(jié)點都將消息副本復制給相遇節(jié)點，但由于節(jié)點能量和緩存受限，容易造成消息的大量重傳和丟棄，網(wǎng)絡開銷大［5］；PROPHET 算法根據(jù)節(jié)點運動的規(guī)律，利用歷史相遇信息預測到達目的節(jié)點的概率，將消息復制給完成數(shù)據(jù)傳遞概率更大的節(jié)點，從而限制了消息副本的數(shù)量，降低了網(wǎng)絡資源消耗［6，7］；Spray and Wait算法限制消息轉(zhuǎn)發(fā)的上限數(shù)目n，這種機制避免產(chǎn)生過多的消息，從而造成網(wǎng)絡開銷的爆發(fā)式增長［8］。

DTN 網(wǎng)絡資源受限的特性，決定了節(jié)點的緩存狀況是制約路由算法效能的關(guān)鍵因素。文獻 ［9］提出一種考慮由于節(jié)點緩存不足出現(xiàn)擁塞情況的概率路由算法，結(jié)合節(jié)點相遇概率和節(jié)點擁塞時間得到消息的遞交概率，提高了消息的遞交率，但是節(jié)點擁塞時間是動態(tài)變化的，難以實時準確統(tǒng)計；文獻 ［10］考慮了在網(wǎng)絡節(jié)點因緩存不足出現(xiàn)擁塞時，丟棄低優(yōu)先級消息以保證高優(yōu)先級消息傳輸，并沒有考慮網(wǎng)絡擁塞發(fā)生之前緩存大小的影響作用；文獻［11］為了緩解DTN 中熱點區(qū)域的擁塞狀況，定義了節(jié)點的擁塞率，依據(jù)對接觸歷史、節(jié)點預期緩存的分析，重新進行了轉(zhuǎn)發(fā)效用整合，但算法的計算復雜度較高。

針對現(xiàn)有算法的不足，本文關(guān)注節(jié)點緩存狀況對DTN路由算法的影響，設計了基于節(jié)點緩存剩余率的DTN 概率路由算法，在計算相遇概率值和消息丟棄時考慮節(jié)點緩存狀況，并在消息轉(zhuǎn)發(fā)和丟棄時設置合理閾值，避免了網(wǎng)絡擁塞造成的網(wǎng)絡性能下降，提高了消息遞交率，降低了網(wǎng)絡開銷。

1 相關(guān)工作

1.1 問題描述

當網(wǎng)絡中節(jié)點緩存受限時，往往不能無限制地接受其它節(jié)點的消息轉(zhuǎn)發(fā)，而是要選擇性地進行接收。PROPHET 算法沒有采用洪泛機制進行消息轉(zhuǎn)發(fā)，而是根據(jù)節(jié)點記錄的歷史相遇消息確定是否進行轉(zhuǎn)發(fā)，能夠有效地降低網(wǎng)絡資源的消耗［6］，但還存在一定的問題。設想以下場景：節(jié)點a攜帶發(fā)往節(jié)點d的消息，節(jié)點b和c都進入了節(jié)點a的通信范圍，且兩節(jié)點的轉(zhuǎn)發(fā)概率基本相同，而節(jié)點b的緩存較大，節(jié)點c的緩存較為有限。在此種條件下，節(jié)點c可能會在以后與其它節(jié)點的接觸中出現(xiàn)擁塞，從而影響消息的轉(zhuǎn)發(fā)。PROPHET 算法單純以歷史相遇概率作為轉(zhuǎn)發(fā)依據(jù)，則a將消息轉(zhuǎn)發(fā)給b和c的概率基本相同，而沒有考慮節(jié)點緩存的影響，實際上節(jié)點b為較為理想的轉(zhuǎn)發(fā)節(jié)點。

為避免上述情況的發(fā)生，本文基于PROPHET 算法，提出一種考慮節(jié)點緩存狀況的節(jié)點緩存感知算法NBAPR（node buffer－aware probabilistic routing algorithm），該算法在計算轉(zhuǎn)發(fā)效用時引入了節(jié)點緩存的影響，在轉(zhuǎn)發(fā)消息有兩個備選轉(zhuǎn)發(fā)節(jié)點時，盡量選擇節(jié)點緩存剩余比值較高的節(jié)點進行轉(zhuǎn)發(fā)，從而減少因節(jié)點緩存不足造成的消息丟失。

1.2 節(jié)點緩存受限的網(wǎng)絡模型

DTN 中每個節(jié)點都有一個緩存單元用于存儲等待轉(zhuǎn)發(fā)的消息，各個節(jié)點的緩存大小都是有限的。每個節(jié)點的初始緩存記為Binit，節(jié)點的剩余緩存記為Bcur，節(jié)點剩余緩存率記為BE。顯然，有BE＝Bcur／Binit。

本文根據(jù)節(jié)點緩存剩余率設置節(jié)點狀態(tài)，定義節(jié)點緩存剩余率門限η1、η2，按照節(jié)點緩存占用率，將節(jié)點劃分為高緩存節(jié)點 （HBN）、中緩存節(jié)點 （MBN）和低緩存節(jié)點 （LBN），特別地，當節(jié)點的剩余緩存率為0時，則稱節(jié)點進入擁塞狀態(tài)。節(jié)點狀態(tài)的劃分規(guī)則定義為

式中：Node（i）——節(jié)點i所屬的節(jié)點類型。

2 算法描述和參數(shù)設置

2.1 轉(zhuǎn)發(fā)概率的計算

在DTN 的實際網(wǎng)絡環(huán)境中，PROPHET 算法只考慮了節(jié)點的相遇概率，而沒有考慮影響制約消息傳輸性能的節(jié)點緩存狀況。因此，本文算法在PROPHET 算法上針對更新公式和老化公式進行了改進。

首先，在更新公式中引入節(jié)點剩余緩存占比的影響，若節(jié)點的剩余緩存占比越高，則更新后概率越高，從而緩存剩余率較高的節(jié)點更有可能被選擇為消息傳輸節(jié)點。具體計算方法如下

式中：Pinit——初始概率值，BE——節(jié)點的剩余緩存占比，D——緩存剩余率對轉(zhuǎn)發(fā)概率的影響因子 （D＞1，Pinit×D＜1）。

其次，節(jié)點轉(zhuǎn)發(fā)效用的老化不僅受節(jié)點間未相遇時間間隔的影響，而且與節(jié)點的剩余緩存率有關(guān)，節(jié)點的剩余緩存率越高，則對該節(jié)點的遞交效用老化的速率也就越慢。如下式所示

式中：γ——節(jié)點轉(zhuǎn)發(fā)概率的老化因子，控制節(jié)點轉(zhuǎn)發(fā)概率老化的速度；k 是兩節(jié)點上次相遇時刻到當前時刻的時間間隔。

再次，傳遞公式反映了消息遞交概率的傳遞性。當節(jié)點a、b經(jīng)常相遇，b、c兩節(jié)點也經(jīng)常相遇，則可以認為節(jié)點b是a、c的良好中繼節(jié)點，節(jié)點a、c間的概率定義如下

式中：β——轉(zhuǎn)移因子，取值范圍為 （0，1］，表示概率傳遞性對消息遞交概率的影響大小。

本文算法需要每個節(jié)點維護一個節(jié)點緩存剩余率表，用于記錄該節(jié)點可用緩存占總緩存的比值。為了便于研究，假設節(jié)點緩存剩余率表的大小相對于消息大小來說較小，并不占用緩存空間。

2.2 消息轉(zhuǎn)發(fā)策略

對于DTN 網(wǎng)絡來說，節(jié)點的緩存狀況很大程度上會影響網(wǎng)絡性能。因此，在每次進行消息轉(zhuǎn)發(fā)之前，對自身節(jié)點和對方節(jié)點的狀態(tài)檢測可以有效減少因為盲目轉(zhuǎn)發(fā)而造成低緩存節(jié)點陷入擁塞的機率，從而提高節(jié)點轉(zhuǎn)發(fā)的效率。具體的轉(zhuǎn)發(fā)策略規(guī)定如下。

（1）在自身為低緩存或中緩存節(jié)點，對方為高緩存節(jié)點時，判斷對方節(jié)點的轉(zhuǎn)發(fā)效用P（b，c）＞ρ1 是否成立，若成立，則進行轉(zhuǎn)發(fā)。ρ1 是一個非負常量，表明節(jié)點b的轉(zhuǎn)發(fā)概率必須多大時才能從低緩存節(jié)點獲得消息。設置合理的ρ1 值可以避免發(fā)送節(jié)點陷入擁塞狀態(tài)后進行消息丟棄策略后刪除消息，從而導致消息遞交率的降低，并且在一定程度上有利于緩解自身的低緩存狀況。

（2）在檢測對方節(jié)點為低緩存節(jié)點時，判斷對方節(jié)點的轉(zhuǎn)發(fā)效用P（b，c）＜ρ2 是否成立，若成立，則不進行轉(zhuǎn)發(fā)。ρ2 是一個非負常量，表明節(jié)點b的轉(zhuǎn)發(fā)概率必須多小時才拒絕接收消息。設置合理的ρ2 值可以避免消息轉(zhuǎn)發(fā)后加重對方節(jié)點的低緩存狀況，以致陷入擁塞。

（3）在其它情況下，消息進行正常轉(zhuǎn)發(fā)，按照轉(zhuǎn)發(fā)效用的相對大小決定消息是否進行轉(zhuǎn)發(fā)。

2.3 消息丟棄策略

節(jié)點的緩存資源是有限的，在緩存達到飽和狀態(tài)時，必須進行消息丟棄，以釋放緩存空間，減少不必要的資源浪費。目前，丟棄消息的策略主要包括：①DF （drop front）：丟棄緩存空間中存在時間最長的消息；②DO （drop oldest）：丟棄緩存空間中生存時間最小的消息；③DY （drop youngest）：丟棄緩存空間中生存時間最大的消息。

本文提出一種綜合考慮消息TTL和消息進入緩存時長的組合丟棄策略，定義消息生存度值

式中：RTTL——消息的TTL剩余率，TB——消息進入節(jié)點緩存的時長。消息的MSD 值越小，則消息的生存性越差，消息的緩存利用效率越低，因此在出現(xiàn)節(jié)點擁塞時優(yōu)先丟棄MSD 值最小的消息，減少剛進入節(jié)點緩存和剩余生存時間較長的消息就被刪除的可能性。

2.4 冗余副本刪除策略

傳統(tǒng)的PROPHET 路由算法是多副本路由算法，節(jié)點將消息轉(zhuǎn)發(fā)后將繼續(xù)保存該消息副本直至節(jié)點緩存達到飽和，然后節(jié)點對緩存內(nèi)的消息進行相應的丟棄策略，這種緩存管理機制勢必會造成緩存資源的浪費。節(jié)點將消息轉(zhuǎn)發(fā)后，合理地刪除保存在自身緩存中的消息副本，能夠充分利用節(jié)點的緩存資源，減小網(wǎng)絡資源的消耗。本文算法設置副本刪除閾值Pth，當更新后的轉(zhuǎn)發(fā)概率P（b，c）＞Pth時，認為節(jié)點b將消息轉(zhuǎn)發(fā)至目的節(jié)點的概率較大，a無需再進行消息的保存。

2.5 參數(shù)D的設置

參數(shù)D 為節(jié)點緩存剩余率對轉(zhuǎn)發(fā)概率的影響因子，當節(jié)點的剩余緩存比較多時，即BE趨近于1，緩存對轉(zhuǎn)發(fā)概率的影響較小，則D 的取值應該相應較?。环粗?，節(jié)點緩存對轉(zhuǎn)發(fā)概率的影響較大，則D 的取值應該相應較大。本文近似認為D 的取值與節(jié)點緩存剩余率成線性關(guān)系，D 值定義如下

其中，Dinit＝1，代表通信進入初始階段，各節(jié)點剩余緩存率接近于1，轉(zhuǎn)發(fā)概率更新公式退化為經(jīng)典PROPHET 算法中的公式，顯然有D＞1，Pinit×D＝1－ （1－Pinit）×BE＜1。

3 仿真實驗與結(jié)果分析

本文采用ONE 仿真平臺［12］，它是基于Java開發(fā)的，可以實現(xiàn)節(jié)點移動模型、路由算法的可配置圖形化仿真，并可以提供結(jié)果報告和分析模型；使用OpenJUMP軟件繪制WKT 格式的節(jié)點運動地圖文件，模擬了空中信息網(wǎng)絡飛行節(jié)點的運動路徑。

3.1 仿真場景構(gòu)建

仿真場景的設置對實驗結(jié)果的影響是顯著的，本文采取的仿真區(qū)域大小為2000×2000 m，模擬了實際通信環(huán)境。包含24個節(jié)點，共分為3組，其中臨近空間飛行節(jié)點10個，高空飛行節(jié)點9個，低空飛行節(jié)點5個，均采用基于地圖路線的移動模型，各組節(jié)點按照其功能特點設置對應的通信范圍和移動速度。設置仿真時間為12h，消息生成間隔時間為60s，消息大小為0.5 MB。表1為本文算法的參數(shù)配置，其它算法采用默認配置。

表1 本文算法參數(shù)

3.2 性能指標

（1）消息遞交率：衡量DTN 網(wǎng)絡性能的主要指標包括消息遞交率、網(wǎng)絡開銷和平均時延，DTN 路由設計的目的就是最大化消息遞交率，最小化平均時延和網(wǎng)絡開銷。消息遞交率是其中最重要的指標，消息遞交率定義為

式中：Nt——網(wǎng)絡中產(chǎn)生的消息總數(shù)，Nr——網(wǎng)絡中被目的節(jié)點成功接收的消息總數(shù)。

（2）網(wǎng)絡開銷：網(wǎng)絡開銷是指網(wǎng)絡中未被中繼節(jié)點轉(zhuǎn)發(fā)到目的節(jié)點的消息數(shù)目與成功被轉(zhuǎn)發(fā)到目的節(jié)點消息數(shù)目的比值。網(wǎng)絡開銷定義為

式中：Np——中繼的消息數(shù)量，Nr——成功遞交的消息數(shù)量。

（3）平均時延：平均時延是指所有被目的節(jié)點成功接收的消息從源節(jié)點發(fā)送至目的節(jié)點所花費的平均時間。平均時延定義為

式中：Ti，t——第i個消息由源節(jié)點發(fā)送的時間，Ti，r——第i個消息被目的節(jié)點接收的時間，n——所有被遞交的消息數(shù)。

3.3 實驗結(jié)果分析

仿真實驗首先對比了NBAPR、PROPHET 和Epidemic這3種算法下網(wǎng)絡性能指標受消息生存時間 （TTL）影響的情況，然后對比了3種算法在不同鏈路帶寬下的性能差異。

3.3.1 消息生存時間因素

圖1和圖2顯示，隨著消息生存時間的增大，網(wǎng)絡中的消息數(shù)目越來越多，包括節(jié)點緩存在內(nèi)的大量網(wǎng)絡資源被占用，網(wǎng)絡開銷隨之漸增，消息的傳遞效率相應降低。Epidemic算法性能最差，說明在資源受限的真實場景中，洪泛式的轉(zhuǎn)發(fā)算法并不能取得良好的效果；NBAPR 算法在進行消息轉(zhuǎn)發(fā)時，引入了節(jié)點緩存狀況的影響，調(diào)整了消息丟棄策略和副本刪除策略，很好地控制了消息的復制數(shù)目，提升了節(jié)點緩存的利用效率，從而實現(xiàn)了網(wǎng)絡開銷的下降和消息遞交率的提高；PROPHET 算法在消息遞交率上略優(yōu)于Epidemic算法，在網(wǎng)絡開銷上介于Epidemic和NBAPR 算法之間。

圖1 TTL對遞交率的影響

圖2 TTL對網(wǎng)絡開銷的影響

圖3顯示，隨著消息生存時間的增大，3種算法的平均時延總體上呈現(xiàn)增長態(tài)勢。由于Epidemic算法采用洪泛機制，容易使網(wǎng)絡陷入擁塞，所以平均時延增長較快；NBAPR算法在進行消息轉(zhuǎn)發(fā)時，在對中繼節(jié)點的選擇上條件更加苛刻，從而導致了NBAPR 算法的平均時延要大于PROPHET 算法；PROPHET 算法在消息生存時間大于2h時，平均時延變化不大，趨于穩(wěn)定。

圖3 TTL對平均時延的影響

3.3.2 鏈路帶寬因素

圖4描述了此場景下的消息遞交率變化情況。NBAPR算法比PROPHET 算法平均提升了14.7%，且隨著鏈路帶寬的提高有逐漸擴大的趨勢；當帶寬在2 Mbps－5 Mbps區(qū)間內(nèi)時，Epidemic算法的消息遞交率高于PROPHET 算法，但當帶寬達到6 Mbps左右時，PROPHET 算法的遞交率出現(xiàn)了躍升。

圖4 鏈路帶寬對交付率的影響

圖5顯示，NBAPR 算法在網(wǎng)絡開銷方面同樣表現(xiàn)最好，比PROPHET 算法平均提升了44%，且隨著鏈路帶寬的提高，NBAPR 算法的網(wǎng)絡開銷下降趨勢較為明顯；Epidemic算法在網(wǎng)絡開銷方面的性能則遠遜于NBAPR 和PROPHET 算法。

在平均時延方面，圖6顯示了3種路由算法的平均時延均隨著鏈路帶寬的增大而減小。在網(wǎng)絡資源有限的條件下，Epidemic算法的平均時延較大；NBAPR 算法受鏈路帶寬影響較大，鏈路帶寬在2 Mbps－4 Mbps時，平均時延出現(xiàn)陡降，隨后平均時延趨于穩(wěn)定，與PROPHET 算法接近；PROPHET 算法的平均時延受鏈路帶寬的影響不像另外兩種算法大，總體上較為穩(wěn)定。

圖5 鏈路帶寬對網(wǎng)絡開銷的影響

圖6 鏈路帶寬對平均時延的影響

4 結(jié)束語

DTN 網(wǎng)絡環(huán)境苛刻，其網(wǎng)絡資源受限的特性給設計合理高效的路由協(xié)議帶來了極大的挑戰(zhàn)，如何充分考慮節(jié)點能量、緩存等網(wǎng)絡資源狀況，以較少的網(wǎng)絡資源消耗實現(xiàn)較高的網(wǎng)絡性能，是DTN 路由協(xié)議設計的重要方向。

本文結(jié)合PROPHET 算法，綜合考慮節(jié)點緩存狀況和歷史相遇信息計算節(jié)點轉(zhuǎn)發(fā)效用，合理設置消息轉(zhuǎn)發(fā)策略中的遞交閾值控制消息的復制；同時，在緩存管理策略和冗余副本刪除策略也做出對應的優(yōu)化。在網(wǎng)絡性能評估中，本文算法在消息遞交率和網(wǎng)絡開銷兩個性能指標上得到了較大提升，同時網(wǎng)絡的平均延遲也控制在較好水平。下一步的研究重點是如何設置更加科學合理的遞交閾值，實現(xiàn)算法在不同環(huán)境中性能提升的普適性。

［1］SU Jinshu，HU Qiaolin，ZHAO Baokang，et al.Routing techniques on delay／diaruption tolerant networks［J］.Journal of Software，2010，21 （1）：119－131 （in Chinese）.［蘇金樹，胡喬林，趙寶康，等.容延容斷網(wǎng)絡路由技術(shù) ［J］.軟件學報，2010，21 （1）：119－131.］

［2］Ochiai H，Ishizuka H，Kawakami Y，et al.A dtn－based sensor data gathering for agricultural applications［J］.IEEE Sensors Journal，2011，11 （11）：2861－2868.

［3］Li Xu，Shu Wei，Li Minglu，et al.DTN routing in vehicular sensor networks［C］／／Proceedings of IEEE Global Telecommunications Conference.New Orleans，USA：IEEE，2009：1－5.

［4］Guo Z，Wang B，Cui J H.Prediction assisted single－copy routing in underwater delay tolerant networks ［C］／／Proc of IEEE Globecom.Piscataway，NJ：IEEE，2010：1－6.

［5］Voyiatzis A.A survey of delay and diarupion tolerant networking applications［J］.Journal of Internet Engineering，2012，5 （1）：331－344.

［6］Huang T，Lee C，Chen L.PRoPHET ＋：An adaptive PRoPHET－based routing protocol for opportunistic network［C］／／Proceedings of 24th International Conference on Advanced Information Networking and Applications.Piscataway：IEEE，2010：112－119.

［7］Karvo J，Ott J.Time scales and delay－tolerant routing protocols［C］／／Proceedings of the Third ACM Workshop on Challenged Networks，2008：33－40.

［8］Huang W，Zhang S，Zhou W.Spray and Wait routing based on position prediction in opportunistic networks ［C］／／Proceedings of 3rd International Conference on Computer Research and Development.Shanghai：IEEE，2011：232－236.

［9］SONG Xin，HU Yong，WANG Bingting.Probabilistic routing algorithm based on node congestion in DTN ［J］.Application Research of Computers，2012，29 （4）：1493－1496 （in Chinese）.［宋鑫，胡勇，王炳庭.一種考慮節(jié)點擁塞情況的DTN 概率路由算法［J］.計算機應用研究，2012，29 （4）：1493－1496.］

［10］WANG Guizhu，XU Zhenghuan，LI Xiaofeng.Congestion control strategy based on quality of message in DTN ［J］.Computer Engineering and Applications，2012，48 （9）：74－77 （in Chinese）. ［王貴竹，徐正歡，李曉峰.DTN 中依據(jù)報文質(zhì)量的擁塞控制策略 ［J］.計算機工程與應用，2012，48 （9）：74－77.］

［11］REN Shanshan，XU Futian，SUI Jingqi.Congestion perception forwarding algorithm in DTN ［J］.Computer Engineering and Design，2012，33 （8）：2961－2965 （in Chinese）.［任姍姍，徐夫田，隋敬麒.DTN 中的擁塞感知轉(zhuǎn)發(fā)算法［J］.計算機工程與設計，2012，33 （8）：2961－2965.］

［12］Ari Kernen，Jrg Ott，Teemu Krkkinen.The ONE simulator for DTN protocol evaluation ［C］／／Proceeding of the 2nd International Conference on Simulation Tools and Techniques.Rome，Italy：ACM Press，2009：1－10.