基于馬爾可夫相遇時間間隔預(yù)測的擁塞控制策略

楊永健，王 恩，杜占瑋

（吉林大學(xué)計算機科學(xué)與技術(shù)學(xué)院，長春130012）

0 引 言

容遲網(wǎng)絡(luò)［1－2］泛指由于網(wǎng)絡(luò)拓撲結(jié)構(gòu)不斷變化，導(dǎo)致端到端之間沒有穩(wěn)定鏈路甚至大部分時間處于中斷狀態(tài)的一類網(wǎng)絡(luò)。2003年，F(xiàn)all［3］在國際會議SIGCOMM上提出了這一概念。傳統(tǒng)的無線網(wǎng)絡(luò)傳輸模式要求源節(jié)點和目的節(jié)點之間存在可靠的傳輸路徑，然而容遲網(wǎng)絡(luò)中由于節(jié)點的移動性和連接的間歇性導(dǎo)致傳統(tǒng)的路由算法不再適合該網(wǎng)絡(luò)環(huán)境，因此DTN中加入了新的協(xié)議層次捆綁層（bundle layer），在該層中引入了“存儲—攜帶—轉(zhuǎn)發(fā)［4］”的思想和逐跳傳輸模式來實現(xiàn)節(jié)點間的通信，為應(yīng)對容遲網(wǎng)絡(luò)高延遲、易中斷等帶來的傳輸可靠性下降問題，引入了保管傳遞（CT）機制［5］，即除非TTL到期，否則一條保管傳輸?shù)南⒃跊]找到下一跳可靠傳輸節(jié)點前不能被刪除，但是這樣很可能會導(dǎo)致網(wǎng)絡(luò)中存在大量報文副本進而造成擁塞現(xiàn)象。

本文提出了基于馬爾可夫［6－7］相遇時間間隔預(yù)測的擁塞控制策略，該策略應(yīng)用馬爾可夫模型對攜帶報文的源節(jié)點和該報文的目的節(jié)點之間的相遇時間間隔序列進行預(yù)測，在預(yù)測出緩存的報文中哪一個最有可能最早遇到其目的節(jié)點之后，通過模型將這種可能性量化，進而通過量化值結(jié)合報文剩余TTL對其進行緩存排序，提出一種新的擁塞控制方法中的排隊策略。根據(jù)報文在網(wǎng)絡(luò)中已經(jīng)復(fù)制或者傳遞的次數(shù)確定該報文已經(jīng)交付到目的節(jié)點的可能性，根據(jù)剩余TTL值確定該報文未來可能交付到目的節(jié)點的可能性，再根據(jù)馬爾可夫模型預(yù)測到的時間間隔即可確定報文下幾跳到達目的節(jié)點的可能性，結(jié)合這三種可能性確定報文在緩存中的丟棄策略［8］，最后將排隊策略和丟棄策略結(jié)合應(yīng)用到節(jié)點緩存的管理中，即得到本文所述的基于馬爾可夫相遇時間間隔預(yù)測的擁塞控制策略。

1 相關(guān)工作

目前在容遲網(wǎng)絡(luò)的研究領(lǐng)域中，更多的研究人員將重點放在路由算法的創(chuàng)新和改進上，很多研究者都會做出節(jié)點資源無限性的假設(shè)［9－10］，而沒有考慮實際中所發(fā)生的節(jié)點緩存擁塞現(xiàn)象。

現(xiàn)有的節(jié)點級擁塞控制方法主要有：①Drop Front（DF）［11］：首先丟棄緩存空間中排隊時間最長的報文；②Drop Last（DL）：首先丟棄緩存空間中最新被接收到的報文；③Drop Oldest（DO）［12］：首先丟棄緩存空間中剩余生命期（TTL）最小的報文；④Drop Youngest（DY）：首先丟棄緩存空間中剩余生命期最大的報文。其中在一些特定場景中DF和DO表現(xiàn)出比較好的性能，這是由于其主要思想是丟棄已經(jīng)在網(wǎng)絡(luò)中存活比較久的報文，這些報文的剩余生命周期一般較短，投遞到目的節(jié)點的可能性較小，因而可以將其丟棄而達到合理化利用資源的目的。

王貴竹等［13］提出了容遲網(wǎng)絡(luò)中基于報文質(zhì)量的擁塞控制策略，主要是通過剩余TTL和報文已經(jīng)復(fù)制的次數(shù)來計算報文質(zhì)量，當節(jié)點緩存發(fā)生擁塞時優(yōu)先丟棄質(zhì)量較差的報文。John B等［14］提出了Maxprop路由策略，將每個節(jié)點報文依據(jù)跳數(shù)多少分為兩組，當節(jié)點緩存滿而又要接收并存儲新的報文時，就對這些報文按照其被遞交的可能性逐個丟棄。劉期烈等［15］在DTN中提出基于復(fù)制率的擁塞控制算法，把報文在網(wǎng)絡(luò)中的復(fù)制次數(shù)與報文的生成時間做比值，得到復(fù)制率，通過丟棄緩存中復(fù)制率較低的報文達到緩存優(yōu)化的效果。

以上對于容遲網(wǎng)絡(luò)中擁塞控制的研究［16－17］都是考慮報文本身的一些性質(zhì)，比如剩余TTL、復(fù)制的次數(shù)等，而沒有考慮所攜帶報文的節(jié)點與報文上標有的目的節(jié)點相遇的可能情況，本文考慮執(zhí)行路由算法時有可能存在以下兩種情況：

（1）攜帶報文的節(jié)點很快就與該報文的目標節(jié)點相遇，但是該報文被排到了隊尾，而導(dǎo)致沒有將其發(fā)送成功。

（2）很快將要與目的節(jié)點相遇的報文雖然沒有排到隊尾，但是由于節(jié)點緩存發(fā)生擁塞，而導(dǎo)致將該報文丟棄。

這樣的兩種情況在實際的緩存擁塞控制策略中都是不可以接受的，為了改變這種現(xiàn)狀，本文提出了基于馬爾可夫相遇時間間隔預(yù)測的DTN擁塞控制策略，通過馬爾可夫模型預(yù)測攜帶報文的節(jié)點與目的節(jié)點的相遇時間間隔，將預(yù)測得到的下一個時間間隔看成報文效用權(quán)值，并通過權(quán)值來確定緩存中的排隊策略和丟棄策略。

2 模型預(yù)測排隊和丟棄策略

2.1 基于馬爾可夫相遇時間間隔預(yù)測模型

在某些含有興趣節(jié)點的場景中，比如校園網(wǎng)絡(luò)中學(xué)生經(jīng)常出現(xiàn)在教學(xué)樓，食堂和宿舍，這些節(jié)點間的相遇并不是偶然的，或者說節(jié)點之間相遇的時間間隔存在著一種內(nèi)在規(guī)律，因此他們可以通過馬爾可夫模型統(tǒng)計以往的時間間隔序列來預(yù)測下一個時間間隔的大致范圍，這樣就能夠盡可能準確地找到緩存中有可能最早交付的報文。

文中為了將節(jié)點間的相遇時間間隔量化，以便用于馬爾可夫模型中進行預(yù)測，在本文的實驗環(huán)境中測試了所有節(jié)點之間相遇時間間隔的分布（見圖1）。

圖1 相遇時間間隔分布Fig.1 Distribution of meeting time span

從圖1中數(shù)據(jù)可以看出節(jié)點間的時間間隔主要分布在0～2000 s，而文中需要根據(jù)時間間隔來預(yù)測節(jié)點間未來的相遇能力，較長的間隔時間對預(yù)測不會帶來很大的幫助，基于上述考慮主要對1000 s以內(nèi)的時間間隔做預(yù)測，故在馬爾可夫模型中將兩個節(jié)點相遇的時間間隔記為隨機變量X，且序列Xi滿足一種時間離散狀態(tài)離散的馬爾可夫鏈［14］，取網(wǎng)絡(luò)中的兩個節(jié)點，全程記錄兩個節(jié)點的時間間隔序列Xi，并且將按照給定范圍不失一般性地劃分為10種狀態(tài)。當0＜Xi≤100時記為狀態(tài)10，當100＜Xi≤200時記為狀態(tài)9，當200＜Xi≤300時記為狀態(tài)8，當300＜Xi≤400時記為狀態(tài)7，當400＜Xi≤500時記為狀態(tài)6，當500＜Xi≤600時記為狀態(tài)5，當600＜Xi≤700時記為狀態(tài)4，當700＜Xi≤800時記為狀態(tài)3，當800＜Xi≤900時記為狀態(tài)2，當900＜Xi時記為狀態(tài)1，故任意兩個節(jié)點的相遇情況都可以通過一個由1～10組成的狀態(tài)序列ai表示。

本文所提出的基于馬爾可夫相遇時間間隔預(yù)測模型可以表示為（S，P，K），其中S是系統(tǒng)所有可能的狀態(tài)所組成的非空的狀態(tài)集，本文即為Xi劃分出的10種狀態(tài)（1～10）。P為狀態(tài)轉(zhuǎn)移矩陣，其表達式為

式中：Pij＝numij／numi，表示兩個節(jié)點最近一次相遇時間間隔為i，并且下一次相遇時間間隔為j的概率，其中numij表示前一次相遇時間間隔為i、下一次相遇時間間隔為j的次數(shù)，numi表示相遇時間間隔i一共出現(xiàn)的次數(shù)。

K為當前狀態(tài)矩陣（1行N列），其表達式為

如果當前的相遇時間間隔為k，則K中第k列的數(shù)值為1，其他列的數(shù)值為0。

本文認為一些節(jié)點之間的相遇時間間隔并不是隨機選取的，下一次的相遇時間間隔與最近一次的相遇時間間隔有關(guān)，而與之前的相遇情況無關(guān)，故根據(jù)馬爾可夫鏈的性質(zhì)：

式中：Ti為第i次相遇的時間；Xi為第i次與第i＋1次相遇間隔時間；ai為相遇時間間隔所在的狀態(tài)，區(qū)間為［1，10］。

Xi由每個節(jié)點統(tǒng)計，并且以ai的形式存儲于本地數(shù)組中。則源節(jié)點A與任意節(jié)點Bi相遇時，首先更新彼此的相遇時間間隔序列，然后查看Bi與目的節(jié)點的相遇間隔的歷史序列，通過歷史序列建立狀態(tài)轉(zhuǎn)移矩陣P，通過歷史序列的最后一個狀態(tài)確定當前狀態(tài)矩陣K（1×N），用狀態(tài)矩陣K乘以狀態(tài)轉(zhuǎn)移矩陣P，即得預(yù)測的下一個相遇時間間隔狀態(tài)矩陣Kp（1×N）（5）。

Kp中最大的數(shù)值所對應(yīng)的列，即為預(yù)測得到的下一個時間間隔的權(quán)值。

轉(zhuǎn)移矩陣中Pij表示由狀態(tài)i轉(zhuǎn)移到狀態(tài)j的概率，由于當進入狀態(tài)i之后，或者保留在狀態(tài)i，或者進入另外一個狀態(tài)，故有：

假設(shè)某點和目的節(jié)點的相遇時間間隔序列為2，1，3，2，4，5，4，1，3，2，6，7，9，8，5，10，7，則狀態(tài)轉(zhuǎn)移矩陣如式（7）所示：

在式（2）中當前狀態(tài)為7，則對應(yīng)的K＝（0 0 0 0 0 0 1 0 0 0），通過式（5）得到Kp＝K×P＝（0 0 0 0 0 0 0 0 1 0），故預(yù)測下一個時間間隔的權(quán)值為9。

2.2 排隊策略

排隊策略的制定主要從以下兩方面來考慮：

（1）一些具有以下特性的報文應(yīng)該排在緩沖區(qū)的隊首：攜帶該報文的節(jié)點有可能很快與該報文的目的節(jié)點相遇，因為這樣的報文有可能直接投遞成功。

（2）具有較大的剩余TTL值的報文應(yīng)該排在隊首，因為這樣的報文一般復(fù)制次數(shù)比較少，網(wǎng)絡(luò)傳染程度比較小，所以應(yīng)該優(yōu)先投遞，而剩余TTL較少的報文投遞成功的可能性較小，因此排在隊尾附近。綜上所述，提出了基于效用權(quán)值進行排隊的控制策略，而效用權(quán)值W 的計算式為

式中：TTLl是指報文的剩余TTL；TTLa是指報文初始化的TTL值，而Kp則是基于馬爾可夫相遇時間間隔預(yù)測模型中攜帶該報文的節(jié)點與報文標識的目的節(jié)點相遇時間間隔的狀態(tài)值，如式（5）。P值越大證明預(yù)測的相遇時間間隔越小，該報文越應(yīng)該排于隊首，TTLl／TTLa值越大證明該報文復(fù)制的比率越小，這樣的報文也應(yīng)該優(yōu)先傳送。綜上所述W 值越大說明該報文的效用值越高，所以根據(jù)W 值的大小進行排隊即為我們的排隊策略。

2.3 丟棄策略

制定擁塞控制丟棄策略的原則：

（1）已經(jīng)成功交付到目的節(jié)點的報文應(yīng)該優(yōu)先從緩存中丟棄，本文討論的路由協(xié)議不包含目的節(jié)點接受到報文后的ACK確認機制，所以攜帶報文的節(jié)點不知道該報文是否已經(jīng)成功投遞到目的節(jié)點。

（2）雖然報文沒有交付到目的節(jié)點，但是因為報文剩余的TTL較少，導(dǎo)致報文成功投遞的可能性非常小，這樣的報文也應(yīng)該從緩存中丟棄掉。

（3）雖然報文剩余的TTL較小，但是通過基于馬爾可夫相遇時間間隔預(yù)測模型預(yù)測得到的攜帶該報文的節(jié)點與該報文中標識的目的節(jié)點的下一個相遇時間間隔很小，這樣的報文可以暫時留下，有可能在很小的TTL內(nèi)成功交付到目的節(jié)點。

本文認為路由協(xié)議中報文在容遲網(wǎng)絡(luò)中被傳遞或復(fù)制的總次數(shù)最能反映報文已經(jīng)成功交付到目的節(jié)點的可能性，報文傳播到的節(jié)點的個數(shù)越多，說明報文蔓延范圍越廣，接觸到目的節(jié)點的可能性也就越大。本文在報文的尾部加入一個字段N，用來準確地統(tǒng)計報文總共感染到的節(jié)點的個數(shù)，統(tǒng)計策略如下：每當節(jié)點之間相遇的時候，所有傳遞出去的報文在發(fā)送節(jié)點和接收節(jié)點上的N字段都加1，如果相遇的兩個節(jié)點有相同的報文，但是報文在N字段上的數(shù)值不一樣，就用數(shù)值大的報文替換掉數(shù)值小的報文，這樣一段時間以后網(wǎng)絡(luò)中多數(shù)報文的N字段可以反映報文感染到的節(jié)點的個數(shù)，記為M，統(tǒng)計流程如圖2所示。

圖2 N的統(tǒng)計過程圖Fig.2 Statistical process figure of N

報文的剩余TTL值記為T。報文基于馬爾可夫相遇時間間隔預(yù)測模型預(yù)測得到的狀態(tài)值記為P。則衡量報文是否應(yīng)該丟棄的報文權(quán)值D可表示為

M值越小說明投遞到目的節(jié)點的可能性越小，該報文越應(yīng)該保留；剩余TTL值越大，T值越大說明該報文越應(yīng)該保留；P值越大說明預(yù)測其與目的節(jié)點很快就能相遇，這樣的報文也應(yīng)該保留，所以優(yōu)先丟棄掉D值小的報文是合理的。其中C1、C2和C3是通過實驗確定的比例因子，通過實驗分析分別設(shè)為0.5，0.3和0.2。

2.4 擁塞控制策略步驟

2.4.1 擁塞檢測

CCSMP的擁塞檢測主要是進行以下兩個簡單的判斷，其中ML為要接收的報文大小，L為接收節(jié)點的本地緩存剩余容量，A為接收節(jié)點本地緩存大小：

（1）ML＜L則沒有發(fā)生擁塞，正常傳輸報文，然后將新到的報文和緩存中原有的報文重新執(zhí)行排隊策略。

（2）ML＞A則直接丟棄該報文。

（3）A＞ML≥L則發(fā)生了擁塞，進入到擁塞避免機制，進行報文的選擇性丟棄。

2.4.2 擁塞避免

（1）本地維護一張丟棄過的報文記錄，當節(jié)點接收到傳輸過來的報文時，優(yōu)先對比報文記錄，如果在其中或者節(jié)點緩存中已經(jīng)有這條報文，則直接丟棄新到報文，否則轉(zhuǎn)到步驟（2）。

（2）執(zhí)行2.3節(jié)中的丟棄策略，對比緩存中已有的報文和新到的報文，計算每個報文的丟棄權(quán)值D，找出其中D值最小的報文，將其丟棄，如果丟棄這個報文之后緩存區(qū)仍然溢出，則找到D值其次小的進行丟棄，直到緩存區(qū)不再發(fā)生擁塞，轉(zhuǎn)到步驟（3）。

（3）將丟棄掉的報文放入丟棄報文記錄中，并將剩余報文執(zhí)行2.2節(jié)中的排隊策略。

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

本文使用THE ONE模擬器對提出的基于馬爾可夫相遇時間間隔預(yù)測的擁塞控制策略CCSMP進行仿真和性能評估。仿真的環(huán)境是THE ONE中默認的赫爾辛基城市地圖，網(wǎng)絡(luò)中共存在100個節(jié)點，分為3組，共同模擬移動的車輛，移動速度為3～7 m／s，第一組車輛移動模型采用隨機行走模型［18］，模擬一些沒有明確目的的車輛，比例占總節(jié)點數(shù)的40%；第二組車輛的移動模型中加入了興趣節(jié)點，設(shè)置的興趣參數(shù)為0.8，使這組節(jié)點中的車輛有0.8的概率向特定地點移動，用來模擬那些有特定習(xí)慣的車輛，比例占總節(jié)點數(shù)的30%；第三組車輛的移動模型采用固定路徑，移動模型為ONE模擬器中自帶的Map RouteMovement，這組節(jié)點用來模擬公交線路上的公交車，比例占總節(jié)點數(shù)的30%。節(jié)點之間的通信接口采用藍牙通信協(xié)議。具體的參數(shù)配置詳見表1。

表1 仿真參數(shù)列表Table 1 List of simulation parameters

同時為了說明CCSMP的適用性，在Epidemic，Spray and wait兩種路由協(xié)議中分別應(yīng)用CCSMP，與DO和DF兩種擁塞控制對比產(chǎn)生實驗數(shù)據(jù)，相同場景下，分別更改緩存大小，傳輸速率（網(wǎng)絡(luò)帶寬），從以下4方面評估協(xié)議的性能：

（1）投遞概率＝成功投遞到目的節(jié)點的報文數(shù)量／網(wǎng)絡(luò)中產(chǎn)生的報文總數(shù)；

（2）平均時延＝消息到達目的節(jié)點的平均時間；

（3）負載比率（開銷比）＝（利用連接成功傳遞包的次數(shù)－傳遞到目的節(jié)點的包的個數(shù)）／傳遞到目的節(jié)點的包的個數(shù)；

（4）丟包率＝TTL（過期或者Buffer滿了被丟棄的報文數(shù)／產(chǎn)生的報文總數(shù)）。

在表1所設(shè)的環(huán)境參數(shù)下，所有節(jié)點執(zhí)行Epidemic路由方法，將緩存大小依次改為5、10、15、20、25、30 MB，分別測得本文提出的CCSMP，傳統(tǒng)的DO以及DF三種擁塞控制策略下的投遞成功率（見圖3），網(wǎng)絡(luò)平均時延（見圖4），負載比率（見圖5）以及丟包率（見圖6）。其中負載比率能反映連接的使用效率，負載比率高說明更多的連接用來傳遞的數(shù)據(jù)包都沒能成功傳遞到目的節(jié)點，連接的使用效用較低。負載比率低反而說明連接的有效使用率高。其中DO策略沒有排隊機制，采用的是丟棄策略，首先丟棄緩存空間中剩余生命期（TTL）最小的報文。DF同樣沒有排隊機制，采用的丟棄策略是首先丟棄緩存空間中排隊時間最長的報文。

從圖3中數(shù)據(jù)得出隨著緩存大小的不斷增加，本文提出的基于馬爾可夫相遇時間間隔預(yù)測的擁塞控制策略CCSMP的投遞概率始終大于DO和DF兩種控制策略下的投遞成功率，這說明經(jīng)過了CCSMP擁塞控制顯著提高了Epidemic路由算法的投遞成功率。圖4中CCSMP的網(wǎng)絡(luò)平均時延比另外兩種控制策略低200 s左右的時間，并且隨著緩存大小的增加呈現(xiàn)一種穩(wěn)定趨勢，這說明CCSMP擁塞控制策略在增加投遞成功率的同時也減小了網(wǎng)絡(luò)時延。對比圖5中3種擁塞控制策略的負載比率，負載比率高說明成功投遞的報文占報文成功傳遞總次數(shù)的比率低，進一步說明無用的數(shù)據(jù)傳輸比較多，CCSMP的負載比率明顯小于DO和DF，說明本文提出的擁塞控制策略從一定程度上也減少了網(wǎng)絡(luò)開銷。從圖6中數(shù)據(jù)可以看出：隨著緩存大小的增加，丟包率顯著降低，但是CCSMP的丟包率一直小于另外兩種擁塞控制策略，平均小10%左右。

圖3 不同緩存下的投遞成功率Fig.3 Delivery ratio of different cache

圖4 不同緩存下的平均時延Fig.4 Delay of different cache

圖5 不同緩存下的負載比率Fig.5 Overhead of different cache

圖6 不同緩存下的丟包率Fig.6 Drop rate of different cache

為了分析不同的傳輸速率是否會對文中提出的擁塞控制策略產(chǎn)生影響，實驗采用120、250、380、510、640、770 kbit／s 6種傳輸速度作仿真，在相同的場景下對比CCSMP、DO、DF三種擁塞控制策略的投遞成功率（見圖7）、平均時延（見圖8）以及負載比率（見圖9）和丟包率（見圖10）。

圖7 不同傳輸速率下的投遞成功率Fig.7 Delivery ratio of different transmit speed

由圖7可知，隨著傳輸速率的增加DF和DO兩種策略的投遞成功率趨于穩(wěn)定，沒有大幅度抖動，而CCSMP的投遞成功率有些許上升，并且持續(xù)處于比較高的狀態(tài)。圖8中傳輸速率的變化同樣沒有嚴重影響擁塞控制策略下的網(wǎng)絡(luò)時延，CCSMP的平均時延始終比其他兩種控制策略小200 s左右，說明該擁塞控制協(xié)議的平均時延受傳輸速率影響不大。從圖9中可見當傳輸速率較小時，網(wǎng)絡(luò)的負載比率與擁塞控制協(xié)議關(guān)系不大，但是隨著傳輸速率的增長，CCSMP的負載比率明顯小于DF和DO，說明文中提出的擁塞控制協(xié)議能夠一定程度上減小網(wǎng)絡(luò)負載，最后從圖10中數(shù)據(jù)可以看出丟包率隨著傳輸速率的增加明顯增大，但是CCSMP相比于DF和DO兩種擁塞控制策略丟包率較小。

圖8 不同傳輸速率下的平均時延Fig.8 Delay of different transmit speed

圖9 不同傳輸速率下的負載比率Fig.9 Overhead of different transmit speed

圖10 不同傳輸速率下的丟包率Fig.10 Drop rate of different transmit speed

為了說明CCSMP并不局限于Epidemic路由策略，本文在完全相同的實驗環(huán)境下，對Spray and wait路由協(xié)議下的3種擁塞控制策略同樣進行了測試，考慮到Sspray and wait對報文的副本數(shù)做了控制，從一定程度上預(yù)防了擁塞的發(fā)生，所以針對Spray and wait路由算法的緩存大小設(shè)置為2、5、8、10 M，報文初始副本數(shù)定義為6，測得投遞成功率（見圖11），網(wǎng)絡(luò)平均時延（見圖12），負載比率（見圖13）和丟包率（見圖14）。

圖11 不同緩存下的投遞成功率Fig.11 Delivery ratio of different cache

圖12 不同緩存下的平均時延Fig.12 Delay of different cache

圖13 不同緩存下的負載比率Fig.13 Overhead of different cache

從圖11中數(shù)據(jù)可以看出，當緩存較小的時候CCSMP擁塞控制策略相比于DF和DO能夠增加投遞成功率，但當緩存增大到一定程度就不會再有明顯的差別，這主要是因為這種情況下緩存大小足夠承受初始報文為6的網(wǎng)絡(luò)報文量，擁塞發(fā)生的較少。從圖12中數(shù)據(jù)可以看出在緩存較少的情況下CCSMP有著更小的網(wǎng)絡(luò)時延。分析圖13和14可知CCSMP與其他兩種擁塞控制策略相比能在一定程度上減少負載比率和丟包率。

圖14 不同緩存下的丟包率Fig.14 Drop rate of different cache

為了在Spray and wait路由算法下分析不同的傳輸速率對文中提出的擁塞控制策略產(chǎn)生的影響，將緩存大小設(shè)置為5 MB，實驗采用120、250、380、510、640、770 kbit／s 6種傳輸速度作仿真，得到投遞成功率（見圖15）、平均時延（見圖16）以及負載比率（見圖17）和丟包率（見圖18）。

圖15 不同傳輸速率下的投遞成功率Fig.15 Delivery ratio of different transmit speed

圖16 不同傳輸速率下的平均時延Fig.16 Delay of different transmit speed

根據(jù)圖15中的數(shù)據(jù)，在節(jié)點本地只有5 MB緩存的情況下CCSMP表現(xiàn)出了更好的投遞成功率，并且隨著傳輸速率的提升投遞成功率呈穩(wěn)步上升趨勢。在圖16中CCSMP的平均時延遠小于DF和DO兩種擁塞控制策略。從圖17的數(shù)據(jù)可以看出CCSMP的負載比率隨著傳輸速度的變化沒有大幅度波動，并且處于較低的狀態(tài)，同樣在圖18中可以看出CCSMP在不同的傳輸速率下有著更小的丟包率。

圖17 不同傳輸速率下的負載比率Fig.17 Overhead of different transmit speed

圖18 不同傳輸速率下的丟包率Fig.18 Drop rate of different transmit speed

4 結(jié)束語

提出了一種基于馬爾可夫相遇時間間隔預(yù)測的擁塞控制策略CCSMP，該策略包括排隊機制和丟棄機制兩部分，并將馬爾可夫模型應(yīng)用到節(jié)點的相遇時間間隔的預(yù)測上，通過預(yù)測值結(jié)合報文復(fù)制或者傳遞的次數(shù)和剩余TTL值來計算報文的效用權(quán)值，通過這個權(quán)值可以決定緩存中的排隊順序和丟棄方式。為了驗證工作的有效性，在THE ONE平臺上對Epidemic和Spray and wait兩種路由協(xié)議進行仿真，將CCSMP與DF和DO兩種擁塞控制策略進行對比，仿真結(jié)果表明CCSMP能夠明顯地增加投遞成功率，減小平均網(wǎng)絡(luò)時延，并且在一定程度上減小了網(wǎng)絡(luò)負載和丟包率。

［1］Burleigh S，Hooke A，Torgerson L，et al.Delay tolerant networking：An approach to interplanetary internet［J］.IEEE Communications Magazine，2003，41（6）：128-136.

［2］Akyildiz I，Su W，Sankarasubramaniam Y，et al.A survey on sensor networks［J］.IEEE Communications Magazine，2002，40（8）：102-114.

［3］Fall K.A delay-tolerant network architecture for challenged Internets［C］∥Proc Conf Appl Technol Architecture Protocols For Computer Commun，Karlsruhe，Germany，2003：27-34.

［4］Cao Jian-nong，Zhang Yang，Xie Li.Consistency of cooperative caching in mobile peer-to-peer systems over MANET［J］.International Journal of Parallel，Emergent and Distributed Systems，2006，21（3）：151-168.

［5］Fall K，Hong W，Madden S.Custody transfer for reliable delivery in delay tolerant networks［EB／OL］.［2010-03-28］.http：／／www.dtnrg.org／papers／custody-xfer-tr.pdf.

［6］張文柱，孫勇發(fā)，王炫.基于馬爾科夫決策的容遲網(wǎng)絡(luò)路由算法［J］.西安電子科技大學(xué)學(xué)報，2011，38（2）：18-22.

Zhang Wen-zhu，Sun Yong-fa，Wang Xuan.Study of the DTN routing algorithm based on the Markov decision［J］.Journal of Xidian University，2011，38（2）：18-22.

［7］鄧甦，李曉毅.馬爾科夫鏈在呼吸道傳染病預(yù)測中的應(yīng)用［J］.中國衛(wèi)生統(tǒng)計，2011（6）：615-616.

Deng Su，Li Xiao-yi.Markov chain in the prediction of respiratory infectious diseases［J］.Chinese Journal of Health Statistics，2011（6）：615-616.

［8］Krifa A，Baraka C，Spyropoulos T.Optimal buffer management policies for delay tolerant networks［C］∥The 5th Annual IEEE Communications Society Conference on Sensor，Mesh and Ad Hoc Communications and Networks，IEEE，2008：260-268.

［9］熊永平，孫利民，牛建偉.機會網(wǎng)絡(luò)［J］.軟件學(xué)報，2009，20（1）：127-134.

Xiong Yong－ping，Sun Li-min，Niu Jian-wei.Opportunistic networks［J］.Journal of Software，2009，20（1）：127-134.

［10］Ramanathan R，Hansen R，Basu P，et al.Priori-tized epidemic routing for opportunistic networks［C］∥International Conference on Mobile Systems，Applications and Services，Proceedings of the 1st International MobiSys Workshop on Mobile Opportunistic Networking，2007，11（11）：62-66.

［11］Pawelczak P，Venkatesha Prasad R，Xia L，et al. Cognitive radio emergency networks-requirements and design［C］∥New Frontiers in Dynamic Spectrum Access Networks，IEEE，2005：601-606.

［12］Lindgren A，Phanse K S.Evaluation of queueing policies and forwarding strategies for routing in intermittently connected networks［C］∥Communication System Software and Middleware，2006：1-10.

［13］王貴竹，徐正歡，李曉峰.DTN中依據(jù)報文質(zhì)量的擁塞控制策略［J］.計算機工程與應(yīng)用，2012，48（9）：74-77.

Wang Gui-zhu，Xu Zheng-huan，Li Xiao-feng.Congestion control strategy based on quality of message in DTN［J］.Computer Engineering and Applications，2012，48（9）：74-77.

［14］John B，Brian G，David J.Maxprop：Routing for vehicle-based disruption-tolerant networks［C］∥INFOCOM，2006：1-11.

［15］劉期烈，潘英俊.延遲容忍網(wǎng)絡(luò)中基于復(fù)制率的擁塞控制算法［J］.北京郵電大學(xué)學(xué)報，2010，33（4）：88-92.

Liu Qi-lie，Pan Ying－jun.Congestion control strategy based on copy rate in DTN［J］.Journal of Beijing University of Post and Telecommunications，2010，33（4）：88-92.

［16］陶勇，龔正虎.DTN擁塞控制研究進展［J］.計算機應(yīng)用研究，2010，27（10）：3605-3611.

Tao Yong，Gong Zheng-hu.Survey on congestion control for DTN［J］.Application Research of Computers，2010，27（10）：3605-3611.

［17］劉席開，劉桂開.機會網(wǎng)絡(luò)擁塞控制的研究［J］.中南林業(yè)科技大學(xué)學(xué)報，2012，32（8）：159-165.

Liu Xi-kai，Liu Gui-kai.Study on congestion control for opportunistic network［J］.Journal of Central South University of Forestry ＆Technology，2012，32（8）：159-165.

［18］Broch J，Maltz D A，Johnson D B，et al.A performance comparison of multi-hop wireless ad hoc network routing protocols［C］∥Proceedings of the 4th Annual ACM／IEEE International Conference on Mobile Computing and Networking，ACM，1998：85-97.