DTN中蔓延路由協議擁塞控制方案研究

摘 要:針對在DTN中使用蔓延路由協議，受轉發節點的緩存限制，導致遞交率因網絡擁塞而下降的問題，在分析比較幾種報文丟棄策略的基礎上，提出一種改進的擁塞控制方案。當擁塞發生時，對節點緩存中超過某個TTL門限的報文進行丟棄。將改善遞交率作為主要參數，使用ONE仿真器對改進方案的性能進行仿真和比較。結果顯示，這種方案很好地實現了擁塞控制。關鍵詞:DTN; 蔓延路由; 擁塞控制; 遞交率

中圖分類號:TN915.0-34; TP393 文獻標識碼:B 文章編號:1004-373X(2010)16-0169-03

Strategy for Congestion Control of Epidemic Routing Protocal in DTN

DOU Fei， GAO Yong-zhi

(MOE Key Lab of ICSP， Anhui University， Hefei 230039， China)

Abstract:Base on the analysis and contrast of the message discard policy， an approach of the improved congestion control is proposed for overcoming the buffer limitation and decrease of the delivery ratio caused by the network congestion as the epidemic routing protocal is adopted in DTN. The messages that exceed the certain threshold of TTL in the nobe buffer memory are discarded when the congestion occurs. Taking the performance of delivery ratio as the major parameter， ONE simulator with the realistic mobility traces is adopted to simulate and contrast the improved scheme. The simulation results show that the proposed scheme does a good job for congestion control.Keywords:DTN; epidemic routing; congestion control; delivery ratio

收稿日期:2010-03-26

DTN(delay/disruption tolerant network) [1-3]是一種具有缺乏連接保證、超長傳輸延遲、間歇連通等特性的通信網絡。在DTN中，報文是通過網絡節點的“存儲-攜帶-轉發”來進行傳輸的。節點攜帶并復制報文，遇到下一跳節點就將報文復制轉發出去。為了保證遞交率，每個節點應該盡量多地攜帶報文，這就使得節點緩存會很快地被占滿，從而產生網絡擁塞，遞交率反而會受到影響。

要解決上述矛盾，就必須研究擁塞控制方案，一種很好的方案是丟棄網絡中已經成功遞交的報文復制。然而，由于DTN特殊的網絡拓撲結構、報文遞交狀態很難預測，所以只能通過猜測最可能已經成功遞交的報文，然后將它丟棄來達到釋放緩存的目的。目前的丟棄策略[4]主要有丟棄最新接收到的報文(drop last，DL)、丟棄最先接收到的報文(drop front，DF)、丟棄剩余TTL最少的報文(drop oldest，DO)、丟棄剩余TTL最大的報文(drop youngest，DY)。文獻[5]中證實，在蔓延(epidemic)路由協議[6-8]中采用DO可以獲得更好的遞交率和延遲性能。這是因為報文的TTL(time to live )剩余越少，說明這個報文在網絡存在的時間越久，那么它已經遞交的可能性最大，將這個報文的復制丟棄，以此來獲取緩存可以最小地改善總遞交率。

本文在這一思路的基礎上提出一種改進機制，通過擁塞控制，進一步提高DTN中蔓延路由協議的各種性能。

1 Epidemic路由協議

Epidemic路由協議[6-8]是一種泛洪的路由協議，當2個節點相遇時，互換彼此沒有的報文。如果網絡的帶寬和緩存等資源足夠，該協議可以保證找到到達目標節點的最短路徑，達到最小的報文遞交延遲。但由于Epidemic路由協議沒有設計分組的到達通告，當一個報文到達目的節點后，該報文的其他復本還會在節點間繼續以“接觸-感染”的方式存在并擴散。由于復制了大量的報文，并且實際緩存的受限，這樣導致的擁塞會對遞交率產生明顯影響。

2 擁塞控制策略

DO丟棄策略如圖1所示。

當發生擁塞時，面對新到來的報文，節點遍歷緩存，找到最老的報文，并將它丟棄，為新報文騰出空間。

本文在DO基礎上提出DNO(dorp N oldest)丟棄策略，即通過設定TTL門限N來對緩存中的報文進行丟棄，如圖2所示。圖2中，N=n×msgTEL(0≤n≤1，msgTTL是報文生命期)。當發生擁塞時，面對新到來的報文，節點遍歷緩存，找到TTL小于N的報文，并把它們丟棄，然后接收新報文。

圖1 DO示意圖

圖2 DNO示意圖

假設任意2個節點A，B相遇，A向B發送報文，那么使用DNO丟棄策略的擁塞控制通信過程如圖3所示。

3 仿真及結果分析

本文使用The ONE(the opportunistic network environment simulator)[9-10]仿真器對方案進行仿真。仿真是在一張真實的地圖路徑上進行的。

仿真場景設置如表1所示。

表1 仿真場景設置

場景大小4 500m×3 400 m仿真時間12 h

分組數6組節點數126個

通信距離20 m報文大小0.5~1 MB

報文傳輸速度2 Mb/s報文TTL90 min

126個節點一共分成6組，其中40個節點的組有3個，以最短路徑模式移動(shortest path map based movement)[11]，移動速度為0.5~1.5 m/s;另外6個節點以2個1組，組成3組作為擺渡節點，每個節點擁有50 MB緩存空間，以基于地圖的路由模式移動(map route movement)[11]，移動速度為7~10 m/s。

(1) DO與FIFO的比較。

在仿真中，當檢測不到滿足門限值的報文時，就采用FIFO(first in first out)模式進行丟棄。這里給出網絡采用FIFO丟棄方案時的遞交率，并與DO進行比較。從圖4 可以看出，兩者遞交率的大小和變化趨勢基本相同。不管是采用DO，還是采用FIFO，當擁塞發生時，報文遞交率依然受到明顯的影響。這是因為即使丟棄了最老或者最先到達的報文也只能騰出有限的緩存空間，只能緩解擁塞，并不能很好地控制擁塞。當擁塞繼續存在時，就需要一種更好的機制來加以調節。

圖3 通信過程示意圖

圖4 FIFO與DO遞交率比較

(2) 不同N取值時的DNO。

首先比較圖4和圖5很容易發現，當N取0.1時，DNO表現出與DO有相似的遞交性能，也就是說沒有達到理想的擁塞控制效果;當N取值不斷變大時，在擁塞發生段，報文遞交率也隨之不斷增加;直到N=0.9時，幾乎不再受擁塞的影響，遞交率達到最大值。這說明，擁塞發生時，通過TTL的選擇來大量丟棄網絡中存在時間相對較長的報文，在較老報文可能已經成功遞交的前提下丟棄它們的復制，為新報文騰出緩存空間，能夠很好地控制擁塞，有效地改善整個網絡的遞交性能。

(3) DNO與FIFO和DO的比較。

下面再來看DNO在開銷和延遲方面的性能。

如圖6所示，在擁塞段DO的開銷比FIFO的大，隨著擁塞程度的加劇表現得越明顯。這是因為開銷主要來自報文的轉發。DO每次丟棄最老的報文，接收新的報文，并且繼續轉發緩存里的報文，所以仍然需要很大的開銷;而FIFO在發生擁塞時停止接收新報文，等待緩存里面的報文發送出去騰出空間，然后再接收新報文，這樣轉發次數不多，所以開銷相對不大。因而DNO介于兩者之間，并且表現得很平穩。

圖5 不同N取值時的DNO遞交率比較

圖6 3種丟棄方案的開銷比較

延遲性能也一樣，DNO介于DO與FIFO之間，并且起伏不大。DO能夠將最老的報文丟棄，并且及時接收新報文，表現出最好的延遲性能;FIFO在擁塞發生時只是等待發送機會，從而使報文停留在緩存里的時間變長，網絡延遲較為明顯。由于DTN對于延遲是不敏感的，所以DNO是在犧牲延遲性能的基礎上獲得更好的遞交性能的。3種方案的延遲比較如圖7所示。

圖7 3種丟棄方案的延遲比較

4 結 語

為了改善DTN中的蔓延路由協議遞交性能，本文對DO進行了改進，提出DNO擁塞控制方案，即在發生擁塞時，通過設置TTL門限對緩存中的報文進行丟棄。仿真結果表明，設置不同的門限值N可以得到相應改善的遞交率。在犧牲延遲性能的基礎上，能夠找到一個恰當的N值，達到明顯改善遞交性能的目的。

參考文獻

[1]FALL A. A delay-tolerant network architecture for cha-llenged Internet[M]//Proc. of the 2003 Conference on Applications.[S.l.]: SIGCOMM， 2003.

[2]熊永平，孫利民，牛建偉，等.機會網絡[J].軟件學報，2009，20(1):124-137.

[3]AKYILDIZ I F， AKAN B， CHEN C， et al. InterPlaNetary Internet: state-of-the-art and research challenges[J]. Computer Networks， 2003，43(2):75-112.

[4]KRIFA A， BARAKAT C， SPYROPOULOS T. Optimal buffer management policies for delay tolerant networks[C]//proceeding of IEEE SECON. [S.l.]: SECON， 2008: 51-57.

[5]LINDGREN A， PHANSE K S. Evaluation of queuing policies and forwarding strategies for routing in intermittently connected networks[C]//Proc. of IEEE COMSWARE. [S.l.]: IEEE， 2006: 1141-1148.

[6]BECKER V D. Epidemic routing for partially connected ad hoc networks[R]. NC: Department of Computer Science， Duke University， 2000.

[7]RAMANATHAN R， HANSEN R， BASU P， et al. Prioritized epidemic routing for opportunistic networks[C]//Proc. of the 1st Int′l MobiSys Workshop on Mobile Opportunistic Networking. San Juan: ACM， 2007: 62-66.

[8]JINDAL A， PSOUNIS K. Performance analysis of epidemic routing under contention[C]//Proc. of the 2006 Int′l Conf. on Wireless Communications and Mobile Computing. Vancouver: ACM， 2006: 539-544.

[9]TKK/COMNET.Project page of the ONE simulator[EB/OL].[2008-04-11].http//www.netlab.tkk.fi/tutkimus/dtn/theone.

[10]KER¨ANENA， OTTJ. Increasing reality for DTN protocol simulations[R]. Helsinki: Helsinki University of Technology， 2007.

[11]KERANEN T K Ari， OTT Jorg. The one simulator for dtn protocol evaluation[M].Rome: SIMUTools， 2009.