相關工作

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

在文獻[13]中，王貴竹等人提出了容遲網絡中基于報文質量的擁塞控制策略，主要是通過剩余TTL和報文已經復制的次數來計算報文質量，當節點緩存發生擁塞時優先丟棄質量較差的報文。在文獻[14]中JohnBurgess等人提出了Maxprop路由策略，將每個節點報文依據跳數多少分為兩組，當節點緩存滿而又要接收并存儲新的報文時，就對這些報文按照其被遞交的可能性逐個丟棄；劉期烈等人在DTN中提出基于復制率的擁塞控制算法[15]，把報文在網絡中的復制次數與報文的生成時間做比值，得到復制率，通過丟棄緩存中復制率較低的報文達到緩存優化的效果。以上對于容遲網絡中擁塞控制的研究[16,17]都是考慮報文本身的一些性質，比如剩余TTL，復制的次數等等，而沒有考慮所攜帶報文的節點與報文上標有的目的節點相遇的可能情況，文中考慮執行路由算法時有可能存在以下兩種情況：1.攜帶報文的節點很快就與該報文的目標節點相遇，但是該報文被排到了隊尾，而導致沒有將其發送成功。2.很快將要與目的節點相遇的報文雖然沒有排到隊尾，但是由于節點緩存發生擁塞，而導致將該報文丟棄。這樣的兩種情況在實際的緩存擁塞控制策略中都是不可以接受的，為了改變這種現狀，本文提出了基于馬爾可夫相遇時間間隔預測的DTN擁塞控制策略，通過馬爾可夫模型預測攜帶報文的節點與目的節點的相遇時間間隔，將預測得到的下一個時間間隔看成報文效用權值，并通過權值來確定緩存中的排隊策略和丟棄策略。

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

1.基于馬爾可夫相遇時間間隔預測模型

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

2.排隊策略

在擁塞控制策略中提出排隊策略是因為DTN中默認的傳輸模式是從隊首開始逐條報文傳送，而容遲網絡中節點之間的連接間歇性很強，很有可能在有限的相遇時間內無法傳輸完所有需要傳輸的報文，進而導致最應該投遞給相遇節點的報文因為排到了隊尾或者隊尾附近而沒有成功傳輸。本文排隊策略的制定主要從以下兩方面來考慮：第一方面，一些具有以下特性的報文應該排在緩沖區的隊首：攜帶該報文的節點有可能很快與該報文的目的節點相遇，因為這樣的報文有可能直接投遞成功。第二方面，具有較大的剩余TTL值的報文應該排在隊首，因為這樣的報文一般復制次數比較少，網絡傳染程度比較小，所以應該優先投遞，而剩余TTL較少的報文投遞成功的可能性較小，因此排在隊尾附近。綜上所述，提出了基于效用權值進行排隊的控制策略，而效用權值W的計算如（8）式（略）。式中lTTL是指報文的剩余TTL，aTTL是指報文初始化的TTL值，而pK則是基于馬爾可夫相遇時間間隔預測模型中攜帶該報文的節點與報文標識的目的節點相遇時間間隔的狀態值，如（5）式。則P值越大證明預測的相遇時間間隔越小，該報文越應該排于隊首，值越大證明該報文復制的比率越小，這樣的報文也應該優先傳送。綜上所述W值越大說明該報文的效用值越高，所以根據W值的大小進行排隊，進而得出了我們的排隊策略。