相關(guān)工作

目前在容遲網(wǎng)絡(luò)的研究領(lǐng)域中，更多的研究人員將重點(diǎn)放在路由算法的創(chuàng)新和改進(jìn)上，很多研究者都會(huì)做出節(jié)點(diǎn)資源無限性的假設(shè)[9,10]，而沒有考慮實(shí)際中所發(fā)生的節(jié)點(diǎn)緩存擁塞現(xiàn)象。現(xiàn)有的節(jié)點(diǎn)級(jí)擁塞控制方法主要有：(1)DropFront（DF）[11]：首先丟棄緩存空間中排隊(duì)時(shí)間最長的報(bào)文。(2)DropLast（DL）：首先丟棄緩存空間中最新被接收到的報(bào)文(3)DropOldest（DO）[12]：首先丟棄緩存空間中剩余生命期（TTL）最小的報(bào)文。(4)DropYoungest（DY）：首先丟棄緩存空間中剩余生命期最大的報(bào)文。其中在一些特定場景中DF和DO表現(xiàn)出比較好的性能，這是由于其主要思想是丟棄已經(jīng)在網(wǎng)絡(luò)中存活比較久的報(bào)文，這些報(bào)文的剩余生命周期一般較短，投遞到目的節(jié)點(diǎn)的可能性較小因而可以將其丟棄而達(dá)到合理化利用資源的目的。

在文獻(xiàn)[13]中，王貴竹等人提出了容遲網(wǎng)絡(luò)中基于報(bào)文質(zhì)量的擁塞控制策略，主要是通過剩余TTL和報(bào)文已經(jīng)復(fù)制的次數(shù)來計(jì)算報(bào)文質(zhì)量，當(dāng)節(jié)點(diǎn)緩存發(fā)生擁塞時(shí)優(yōu)先丟棄質(zhì)量較差的報(bào)文。在文獻(xiàn)[14]中JohnBurgess等人提出了Maxprop路由策略，將每個(gè)節(jié)點(diǎn)報(bào)文依據(jù)跳數(shù)多少分為兩組，當(dāng)節(jié)點(diǎn)緩存滿而又要接收并存儲(chǔ)新的報(bào)文時(shí)，就對(duì)這些報(bào)文按照其被遞交的可能性逐個(gè)丟棄；劉期烈等人在DTN中提出基于復(fù)制率的擁塞控制算法[15]，把報(bào)文在網(wǎng)絡(luò)中的復(fù)制次數(shù)與報(bào)文的生成時(shí)間做比值，得到復(fù)制率，通過丟棄緩存中復(fù)制率較低的報(bào)文達(dá)到緩存優(yōu)化的效果。以上對(duì)于容遲網(wǎng)絡(luò)中擁塞控制的研究[16,17]都是考慮報(bào)文本身的一些性質(zhì)，比如剩余TTL，復(fù)制的次數(shù)等等，而沒有考慮所攜帶報(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)致沒有將其發(fā)送成功。2.很快將要與目的節(jié)點(diǎn)相遇的報(bào)文雖然沒有排到隊(duì)尾，但是由于節(jié)點(diǎn)緩存發(fā)生擁塞，而導(dǎo)致將該報(bào)文丟棄。這樣的兩種情況在實(shí)際的緩存擁塞控制策略中都是不可以接受的，為了改變這種現(xiàn)狀，本文提出了基于馬爾可夫相遇時(shí)間間隔預(yù)測的DTN擁塞控制策略，通過馬爾可夫模型預(yù)測攜帶報(bào)文的節(jié)點(diǎn)與目的節(jié)點(diǎn)的相遇時(shí)間間隔，將預(yù)測得到的下一個(gè)時(shí)間間隔看成報(bào)文效用權(quán)值，并通過權(quán)值來確定緩存中的排隊(duì)策略和丟棄策略。

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

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

在某些含有興趣節(jié)點(diǎn)的場景中，比如校園網(wǎng)絡(luò)中學(xué)生經(jīng)常出現(xiàn)在教學(xué)樓，食堂和宿舍，這些節(jié)點(diǎn)間的相遇并不是偶然的，或者說節(jié)點(diǎn)之間相遇的時(shí)間間隔存在著一種內(nèi)在規(guī)律，因此他們可以通過馬爾可夫模型統(tǒng)計(jì)以往的時(shí)間間隔序列來預(yù)測下一個(gè)時(shí)間間隔的大致范圍，這樣就能夠盡可能準(zhǔn)確的找到緩存中有可能最早交付的報(bào)文。文中為了將節(jié)點(diǎn)間的相遇時(shí)間間隔量化，以便用于馬爾可夫模型中進(jìn)行預(yù)測，進(jìn)而在本文的實(shí)驗(yàn)環(huán)境中測試了所有節(jié)點(diǎn)之間相遇時(shí)間間隔的分布(圖1)。從圖1中數(shù)據(jù)可以看出節(jié)點(diǎn)間的時(shí)間間隔主要分布在0-2000秒之間，而文中需要根據(jù)時(shí)間間隔來預(yù)測節(jié)點(diǎn)間未來的相遇能力，較長的間隔時(shí)間對(duì)預(yù)測不會(huì)帶來很大的幫助，基于上述考慮主要對(duì)1000秒以內(nèi)的時(shí)間間隔做預(yù)測，故在馬爾可夫模型中將兩個(gè)節(jié)點(diǎn)相遇的時(shí)間間隔記為隨機(jī)變量X，且序列iX滿足一種時(shí)間離散狀態(tài)離散的馬爾可夫鏈[14]，取網(wǎng)絡(luò)中的兩個(gè)節(jié)點(diǎn)，全程記錄兩個(gè)節(jié)點(diǎn)的時(shí)間間隔序列iX，并且將iX按照給定范圍不失一般性地劃分為10種狀態(tài)。當(dāng)0＜iX?100時(shí)記為狀態(tài)10，當(dāng)100＜iX?200時(shí)記為狀態(tài)9，當(dāng)200＜iX?300時(shí)記為狀態(tài)8，當(dāng)300＜iX?400時(shí)記為狀態(tài)7，當(dāng)400＜iX?500時(shí)記為狀態(tài)6，當(dāng)500＜iX?600時(shí)記為狀態(tài)5，當(dāng)600＜iX?700時(shí)記為狀態(tài)4，當(dāng)700＜iX?800時(shí)記為狀態(tài)3，當(dāng)800＜iX?900時(shí)記為狀態(tài)2,當(dāng)900＜iX時(shí)記為狀態(tài)1，故任意兩個(gè)節(jié)點(diǎn)的相遇情況都可以通過一個(gè)由1-10組成的狀態(tài)序列ia表示。本文所提出的基于馬爾可夫相遇時(shí)間間隔預(yù)測模型可以表示為(S，P，K)，其中S是系統(tǒng)所有可能的狀態(tài)所組成的非空的狀態(tài)集，本文即為iX劃分出的10種狀態(tài)(1-10)。P為狀態(tài)轉(zhuǎn)移矩陣，見（3）式，其中ijijiPnum/num，表示兩個(gè)節(jié)點(diǎn)最近一次相遇時(shí)間間隔為i并且下一次相遇時(shí)間間隔為j的概率，其中ijnum表示前一次相遇時(shí)間間隔為i下一次相遇時(shí)間間隔為j的次數(shù)，inum表示相遇時(shí)間間隔i一共出現(xiàn)的次數(shù)。K為當(dāng)前狀態(tài)矩陣（1行N列），表示為（4）式，如果當(dāng)前的相遇時(shí)間間隔為k，則K中第k列的數(shù)值為1，其他列的數(shù)值為0。本文認(rèn)為一些節(jié)點(diǎn)之間的相遇時(shí)間間隔并不是隨機(jī)選取的，下一次的相遇時(shí)間間隔與最近一次的相遇時(shí)間間隔有關(guān)，而與之前的相遇情況無關(guān)，故根據(jù)馬爾可夫鏈的性質(zhì)：（略）式中iT表示第i次相遇的時(shí)間，iX表示第i次與第i+1次相遇間隔時(shí)間，ia表示相遇時(shí)間間隔所在的狀態(tài)，區(qū)間為[1,10]。iX由每個(gè)節(jié)點(diǎn)統(tǒng)計(jì)，并且以的形式存儲(chǔ)于本地?cái)?shù)組中。則源節(jié)點(diǎn)A與任意節(jié)點(diǎn)iB相遇時(shí)，首先更新彼此的相遇時(shí)間間隔序列，然后查看iB與目的節(jié)點(diǎn)的相遇間隔的歷史序列，通過歷史序列建立狀態(tài)轉(zhuǎn)移矩陣P，通過歷史序列的最后一個(gè)狀態(tài)確定當(dāng)前狀態(tài)矩陣K(1×N)，用狀態(tài)矩陣K乘以狀態(tài)轉(zhuǎn)移矩陣P，即得預(yù)測的下一個(gè)相遇時(shí)間間隔狀態(tài)矩陣pK(1×N)（5）。pK中最大的數(shù)值所對(duì)應(yīng)的列，即為預(yù)測得到的下一個(gè)時(shí)間間隔的權(quán)值。轉(zhuǎn)移矩陣中ijP表示由狀態(tài)i轉(zhuǎn)移到狀態(tài)j的概率，由于當(dāng)進(jìn)入狀態(tài)i之后，或者保留在狀態(tài)i或者進(jìn)入另外一個(gè)狀態(tài)，故有（6）式。假設(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）式。在（4）中當(dāng)前狀態(tài)為7，則對(duì)應(yīng)的K(0000001000)，通過（5）式得到KKP(0000000010)p故預(yù)測下一個(gè)時(shí)間間隔的權(quán)值為9。

2.排隊(duì)策略

在擁塞控制策略中提出排隊(duì)策略是因?yàn)镈TN中默認(rèn)的傳輸模式是從隊(duì)首開始逐條報(bào)文傳送，而容遲網(wǎng)絡(luò)中節(jié)點(diǎn)之間的連接間歇性很強(qiáng)，很有可能在有限的相遇時(shí)間內(nèi)無法傳輸完所有需要傳輸?shù)膱?bào)文，進(jìn)而導(dǎo)致最應(yīng)該投遞給相遇節(jié)點(diǎn)的報(bào)文因?yàn)榕诺搅岁?duì)尾或者隊(duì)尾附近而沒有成功傳輸。本文排隊(duì)策略的制定主要從以下兩方面來考慮：第一方面，一些具有以下特性的報(bào)文應(yīng)該排在緩沖區(qū)的隊(duì)首：攜帶該報(bào)文的節(jié)點(diǎn)有可能很快與該報(bào)文的目的節(jié)點(diǎn)相遇，因?yàn)檫@樣的報(bào)文有可能直接投遞成功。第二方面，具有較大的剩余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ì)算如（8）式（略）。式中l(wèi)TTL是指報(bào)文的剩余TTL，aTTL是指報(bào)文初始化的TTL值，而pK則是基于馬爾可夫相遇時(shí)間間隔預(yù)測模型中攜帶該報(bào)文的節(jié)點(diǎn)與報(bào)文標(biāo)識(shí)的目的節(jié)點(diǎn)相遇時(shí)間間隔的狀態(tài)值，如（5）式。則P值越大證明預(yù)測的相遇時(shí)間間隔越小，該報(bào)文越應(yīng)該排于隊(duì)首，值越大證明該報(bào)文復(fù)制的比率越小，這樣的報(bào)文也應(yīng)該優(yōu)先傳送。綜上所述W值越大說明該報(bào)文的效用值越高，所以根據(jù)W值的大小進(jìn)行排隊(duì)，進(jìn)而得出了我們的排隊(duì)策略。