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

楊永健，王 恩，杜占瑋

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

0 引 言

容遲網(wǎng)絡(luò)［1－2］泛指由于網(wǎng)絡(luò)拓?fù)浣Y(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é)點(diǎn)和目的節(jié)點(diǎn)之間存在可靠的傳輸路徑，然而容遲網(wǎng)絡(luò)中由于節(jié)點(diǎn)的移動性和連接的間歇性導(dǎo)致傳統(tǒng)的路由算法不再適合該網(wǎng)絡(luò)環(huán)境，因此DTN中加入了新的協(xié)議層次捆綁層（bundle layer），在該層中引入了“存儲—攜帶—轉(zhuǎn)發(fā)［4］”的思想和逐跳傳輸模式來實現(xiàn)節(jié)點(diǎn)間的通信，為應(yīng)對容遲網(wǎng)絡(luò)高延遲、易中斷等帶來的傳輸可靠性下降問題，引入了保管傳遞（CT）機(jī)制［5］，即除非TTL到期，否則一條保管傳輸?shù)南⒃跊]找到下一跳可靠傳輸節(jié)點(diǎn)前不能被刪除，但是這樣很可能會導(dǎo)致網(wǎng)絡(luò)中存在大量報文副本進(jìn)而造成擁塞現(xiàn)象。

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

1 相關(guān)工作

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

現(xiàn)有的節(jié)點(diǎn)級擁塞控制方法主要有：①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é)點(diǎn)的可能性較小，因而可以將其丟棄而達(dá)到合理化利用資源的目的。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Xi由每個節(jié)點(diǎn)統(tǒng)計，并且以ai的形式存儲于本地數(shù)組中。則源節(jié)點(diǎn)A與任意節(jié)點(diǎn)Bi相遇時，首先更新彼此的相遇時間間隔序列，然后查看Bi與目的節(jié)點(diǎn)的相遇間隔的歷史序列，通過歷史序列建立狀態(tài)轉(zhuǎn)移矩陣P，通過歷史序列的最后一個狀態(tài)確定當(dāng)前狀態(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的概率，由于當(dāng)進(jìn)入狀態(tài)i之后，或者保留在狀態(tài)i，或者進(jìn)入另外一個狀態(tài)，故有：

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

在式（2）中當(dāng)前狀態(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é)點(diǎn)有可能很快與該報文的目的節(jié)點(diǎn)相遇，因為這樣的報文有可能直接投遞成功。

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

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

2.3 丟棄策略

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

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

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

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

本文認(rèn)為路由協(xié)議中報文在容遲網(wǎng)絡(luò)中被傳遞或復(fù)制的總次數(shù)最能反映報文已經(jīng)成功交付到目的節(jié)點(diǎn)的可能性，報文傳播到的節(jié)點(diǎn)的個數(shù)越多，說明報文蔓延范圍越廣，接觸到目的節(jié)點(diǎn)的可能性也就越大。本文在報文的尾部加入一個字段N，用來準(zhǔn)確地統(tǒng)計報文總共感染到的節(jié)點(diǎn)的個數(shù)，統(tǒng)計策略如下：每當(dāng)節(jié)點(diǎn)之間相遇的時候，所有傳遞出去的報文在發(fā)送節(jié)點(diǎn)和接收節(jié)點(diǎn)上的N字段都加1，如果相遇的兩個節(jié)點(diǎn)有相同的報文，但是報文在N字段上的數(shù)值不一樣，就用數(shù)值大的報文替換掉數(shù)值小的報文，這樣一段時間以后網(wǎng)絡(luò)中多數(shù)報文的N字段可以反映報文感染到的節(jié)點(diǎn)的個數(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é)點(diǎn)的可能性越小，該報文越應(yīng)該保留；剩余TTL值越大，T值越大說明該報文越應(yīng)該保留；P值越大說明預(yù)測其與目的節(jié)點(diǎn)很快就能相遇，這樣的報文也應(yīng)該保留，所以優(yōu)先丟棄掉D值小的報文是合理的。其中C1、C2和C3是通過實驗確定的比例因子，通過實驗分析分別設(shè)為0.5，0.3和0.2。

2.4 擁塞控制策略步驟

2.4.1 擁塞檢測

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

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

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

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

2.4.2 擁塞避免

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

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

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

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

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

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

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

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

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

從圖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種擁塞控制策略的負(fù)載比率，負(fù)載比率高說明成功投遞的報文占報文成功傳遞總次數(shù)的比率低，進(jìn)一步說明無用的數(shù)據(jù)傳輸比較多，CCSMP的負(fù)載比率明顯小于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 不同緩存下的負(fù)載比率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）以及負(fù)載比率（見圖9）和丟包率（見圖10）。

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

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

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

圖9 不同傳輸速率下的負(fù)載比率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種擁塞控制策略同樣進(jìn)行了測試，考慮到Sspray and wait對報文的副本數(shù)做了控制，從一定程度上預(yù)防了擁塞的發(fā)生，所以針對Spray and wait路由算法的緩存大小設(shè)置為2、5、8、10 M，報文初始副本數(shù)定義為6，測得投遞成功率（見圖11），網(wǎng)絡(luò)平均時延（見圖12），負(fù)載比率（見圖13）和丟包率（見圖14）。

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

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

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

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

圖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）以及負(fù)載比率（見圖17）和丟包率（見圖18）。

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

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

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

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

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

4 結(jié)束語

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

［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］熊永平，孫利民，牛建偉.機(jī)會網(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］.計算機(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ìn)展［J］.計算機(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］劉席開，劉桂開.機(jī)會網(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.