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

中圖分類號:TN915.0-34; TP393 文獻(xiàn)標(biāo)識碼: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]是一種具有缺乏連接保證、超長傳輸延遲、間歇連通等特性的通信網(wǎng)絡(luò)。在DTN中，報文是通過網(wǎng)絡(luò)節(jié)點(diǎn)的“存儲-攜帶-轉(zhuǎn)發(fā)”來進(jìn)行傳輸?shù)?。?jié)點(diǎn)攜帶并復(fù)制報文，遇到下一跳節(jié)點(diǎn)就將報文復(fù)制轉(zhuǎn)發(fā)出去。為了保證遞交率，每個節(jié)點(diǎn)應(yīng)該盡量多地攜帶報文，這就使得節(jié)點(diǎn)緩存會很快地被占滿，從而產(chǎn)生網(wǎng)絡(luò)擁塞，遞交率反而會受到影響。

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

本文在這一思路的基礎(chǔ)上提出一種改進(jìn)機(jī)制，通過擁塞控制，進(jìn)一步提高DTN中蔓延路由協(xié)議的各種性能。

1 Epidemic路由協(xié)議

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

2 擁塞控制策略

DO丟棄策略如圖1所示。

當(dāng)發(fā)生擁塞時，面對新到來的報文，節(jié)點(diǎn)遍歷緩存，找到最老的報文，并將它丟棄，為新報文騰出空間。

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

圖1 DO示意圖

圖2 DNO示意圖

假設(shè)任意2個節(jié)點(diǎn)A，B相遇，A向B發(fā)送報文，那么使用DNO丟棄策略的擁塞控制通信過程如圖3所示。

3 仿真及結(jié)果分析

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

仿真場景設(shè)置如表1所示。

表1 仿真場景設(shè)置

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

分組數(shù)6組節(jié)點(diǎn)數(shù)126個

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

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

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

(1) DO與FIFO的比較。

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

圖3 通信過程示意圖

圖4 FIFO與DO遞交率比較

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

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

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

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

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

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

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

延遲性能也一樣，DNO介于DO與FIFO之間，并且起伏不大。DO能夠?qū)⒆罾系膱笪膩G棄，并且及時接收新報文，表現(xiàn)出最好的延遲性能;FIFO在擁塞發(fā)生時只是等待發(fā)送機(jī)會，從而使報文停留在緩存里的時間變長，網(wǎng)絡(luò)延遲較為明顯。由于DTN對于延遲是不敏感的，所以DNO是在犧牲延遲性能的基礎(chǔ)上獲得更好的遞交性能的。3種方案的延遲比較如圖7所示。

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

4 結(jié) 語

為了改善DTN中的蔓延路由協(xié)議遞交性能，本文對DO進(jìn)行了改進(jìn)，提出DNO擁塞控制方案，即在發(fā)生擁塞時，通過設(shè)置TTL門限對緩存中的報文進(jìn)行丟棄。仿真結(jié)果表明，設(shè)置不同的門限值N可以得到相應(yīng)改善的遞交率。在犧牲延遲性能的基礎(chǔ)上，能夠找到一個恰當(dāng)?shù)腘值，達(dá)到明顯改善遞交性能的目的。

參考文獻(xià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ī)會網(wǎng)絡(luò)[J].軟件學(xué)報，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.