楊永健，王 恩，杜占瑋

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

0 引 言

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

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

1 相關(guān)工作

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

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

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

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

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

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

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

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

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

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

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

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

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

本文所提出的基于馬爾可夫相遇時(shí)間間隔預(yù)測(cè)模型可以表示為（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，表示兩個(gè)節(jié)點(diǎn)最近一次相遇時(shí)間間隔為i，并且下一次相遇時(shí)間間隔為j的概率，其中numij表示前一次相遇時(shí)間間隔為i、下一次相遇時(shí)間間隔為j的次數(shù)，numi表示相遇時(shí)間間隔i一共出現(xiàn)的次數(shù)。

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

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

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

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

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

Kp中最大的數(shù)值所對(duì)應(yīng)的列，即為預(yù)測(cè)得到的下一個(gè)時(shí)間間隔的權(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)入另外一個(gè)狀態(tài)，故有：

假設(shè)某點(diǎn)和目的節(jié)點(diǎn)的相遇時(shí)間間隔序列為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，則對(duì)應(yīng)的K＝（0 0 0 0 0 0 1 0 0 0），通過(guò)式（5）得到Kp＝K×P＝（0 0 0 0 0 0 0 0 1 0），故預(yù)測(cè)下一個(gè)時(shí)間間隔的權(quán)值為9。

2.2 排隊(duì)策略

排隊(duì)策略的制定主要從以下兩方面來(lái)考慮：

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

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

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

2.3 丟棄策略

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

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

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

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

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

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

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

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

2.4 擁塞控制策略步驟

2.4.1 擁塞檢測(cè)

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

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

（2）ML＞A則直接丟棄該報(bào)文。

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

2.4.2 擁塞避免

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖8 不同傳輸速率下的平均時(shí)延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

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

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

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

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

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

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

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

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

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

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

提出了一種基于馬爾可夫相遇時(shí)間間隔預(yù)測(cè)的擁塞控制策略CCSMP，該策略包括排隊(duì)機(jī)制和丟棄機(jī)制兩部分，并將馬爾可夫模型應(yīng)用到節(jié)點(diǎn)的相遇時(shí)間間隔的預(yù)測(cè)上，通過(guò)預(yù)測(cè)值結(jié)合報(bào)文復(fù)制或者傳遞的次數(shù)和剩余TTL值來(lái)計(jì)算報(bào)文的效用權(quán)值，通過(guò)這個(gè)權(quán)值可以決定緩存中的排隊(duì)順序和丟棄方式。為了驗(yàn)證工作的有效性，在THE ONE平臺(tái)上對(duì)Epidemic和Spray and wait兩種路由協(xié)議進(jìn)行仿真，將CCSMP與DF和DO兩種擁塞控制策略進(jìn)行對(duì)比，仿真結(jié)果表明CCSMP能夠明顯地增加投遞成功率，減小平均網(wǎng)絡(luò)時(shí)延，并且在一定程度上減小了網(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é)報(bào)，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ù)測(cè)中的應(yīng)用［J］.中國(guó)衛(wèi)生統(tǒng)計(jì)，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ī)會(huì)網(wǎng)絡(luò)［J］.軟件學(xué)報(bào)，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ù)報(bào)文質(zhì)量的擁塞控制策略［J］.計(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é)報(bào)，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ì)算機(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］劉席開(kāi)，劉桂開(kāi).機(jī)會(huì)網(wǎng)絡(luò)擁塞控制的研究［J］.中南林業(yè)科技大學(xué)學(xué)報(bào)，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.