前言：尋找寫作靈感？中文期刊網用心挑選的馬爾可夫相遇間隔預測擁塞控制策略CCSMP，希望能為您的閱讀和創作帶來靈感，歡迎大家閱讀并分享。
相關工作
目前在容遲網絡的研究領域中，更多的研究人員將重點放在路由算法的創新和改進上，很多研究者都會做出節點資源無限性的假設[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值的大小進行排隊，進而得出了我們的排隊策略。#p#分頁標題#e#
3.丟棄策略
本文認為可以依據以下三點原則制定擁塞控制中比較好的丟棄策略。(1)已經成功交付到目的節點的報文應該優先從緩存中丟棄，這里我們討論的路由協議不包含目的節點接受到報文后的ACK確認機制，所以攜帶報文的節點不知道該報文是否已經成功投遞到目的節點。(2)雖然報文沒有交付到目的節點，但是因為報文剩余的TTL較少，導致報文成功投遞的可能性非常小，這樣的報文也應該從緩存中丟棄掉。(3)雖然報文剩余的TTL較小，但是通過基于馬爾可夫相遇時間間隔預測模型預測得到的攜帶該報文的節點與該報文中標識的目的節點的下一個相遇時間間隔很小，這樣的報文可以暫時留下，有可能在很小的TTL內成功交付到目的節點。綜上所述，報文是否丟棄的依據有以下三點：報文已經交付到目的節點的可能性，報文剩余TTL數，以及基于馬爾可夫相遇時間間隔預測模型預測得到的狀態值。由此可以得到擁塞控制策略中的丟棄策略。
本文認為路由協議中報文在容遲網絡中被傳遞或復制的總次數最能反映報文已經成功交付到目的節點的可能性，報文傳播到的節點的個數越多，說明報文蔓延范圍越廣，接觸到目的節點的可能性也就越大。本文在報文的尾部加入一個字段N，用來準確地統計報文總共感染到的節點的個數，統計策略如下：每當節點之間相遇的時候，所有傳遞出去的報文在發送節點和接收節點上的N字段都加1，如果相遇的兩個節點有相同的報文，但是報文在N字段上的數值不一樣，就用數值大的報文替換掉數值小的報文，這樣一段時間以后網絡中多數報文的N字段可以反映報文感染到的節點的個數，記為M，統計流程如圖2。報文的剩余TTL值記為T。報文基于馬爾可夫相遇時間間隔預測模型預測得到的狀態值記為P。則衡量報文是否應該丟棄的報文權值D表示如（9）式：（略）M值越小說明投遞到目的節點的可能性越小，說明該報文越應該保留，剩余TTL值越大，T值越大說明該報文越應該保留，P值越大說明預測其與目的節點很快就能相遇，這樣的報文也應該保留，所以優先丟棄掉D值小的報文是合理的。其中1C2C和3C是通過實驗確定的比例因子，通過實驗分析分別設為0.5,0.3和0.2。
4.擁塞控制策略CCSMP流程
1）擁塞檢測：CCSMP的擁塞檢測主要是進行簡單的以下兩個判斷,其中LM為要接收的報文大小，L為接收節點的本地緩存剩余容量,A為接收節點本地緩存大?。?1)LM<L則沒有發生擁塞，正常傳輸報文，然后將新到的報文和緩存中原有的報文重新執行排隊策略。(2)LM>A則直接丟棄該報文。(3)A>LM≥L則發生了擁塞，進入到擁塞避免機制，進行報文的選擇性丟棄。2.4.2擁塞避免(1)本地維護一張丟棄過的報文記錄，當節點接收到要傳輸過來的報文時，優先對比報文記錄如果在其中或者節點緩存中已經有這條報文則直接丟棄新到報文，否則轉到步驟（2）。(2)執行2.3中的丟棄策略，對比緩存中已有的報文和新到的報文，計算每個報文的丟棄權值D，找出其中D值最小的報文，將其丟棄，如果丟棄這個報文之后緩存區仍然溢出，則找到D值其次小的進行丟棄，直到緩存區不再發生擁塞，轉到步驟（3）。(3)將丟棄掉的報文放入丟棄報文記錄中，并將剩余報文執行2.2節中的排隊策略。
仿真結果與分析
本文使用THEONE模擬器對提出的基于馬爾可夫相遇時間間隔預測的擁塞控制策略CCSMP進行仿真和性能評估。仿真的環境是THEONE中的默認地圖：赫爾辛基城市地圖，網絡中共存在著100個節點，分為3組，共同模擬移動的車輛，移動速度為3-7米每秒，第一組車輛移動模型采用隨機行走模型[18]，模擬一些沒有明確目的的車輛，比例占總節點數的40%，第二組車輛的移動模型中加入了興趣節點，設置的興趣參數為0.8，使這組節點中的車輛有0.8的概率向特定地點移動，用來模擬那些有特定習慣的車輛，比例占總節點數的30%，第三組車輛的移動模型采用固定路徑，移動模型為ONE模擬器中自帶的MapRouteMovement，這組節點用來模擬公交線路上的公交車，比例占總節點數的30%。節點之間的通信接口采用藍牙通信協議。具體的參數配置詳見表1。同時為了說明CCSMP的適用性，在Epidemic，Sprayandwait兩種路由協議中分別應用CCSMP，與DO和DF兩種擁塞控制對比產生實驗數據，相同場景下，分別更改緩存大小，傳輸速率（網絡帶寬），從以下四方面評估協議的性能:1.投遞概率=成功投遞到目的節點的報文數量/網絡中產生的報文總數2.平均時延=消息到達目的節點的平均時間3.負載比率（開銷比）=（利用連接成功傳遞包的次數-傳遞到目的節點的包的個數）/傳遞到目的節點的包的個數4.丟包率=TTL過期或者Buffer滿了被丟棄的報文數/產生的報文總數
仿真結果與數據分析
在表1所設的環境參數下，所有節點執行Epidemic路由方法，將緩存大小依次改為5M，10M，15M，20M，25M，30M，分別測得本文提出的CCSMP，傳統的DO以及DF三種擁塞控制策略下的投遞成功率（見圖4），網絡平均時延（見圖5），負載比率（見圖6）以及丟包率（見圖7）。其中負載比率能反映連接的使用效率，負載比率高說明更多的連接用來傳遞的數據包都沒能成功傳遞到目的節點，連接的使用效用較低。負載比率低反而說明連接的有效使用率高。其中DO策略沒有排隊機制，采用的是丟棄策略首先丟棄緩存空間中剩余生命期（TTL）最小的報文。DF同樣沒有排隊機制，采用的丟棄策略是首先丟棄緩存空間中排隊時間最長的報文。從圖4中數據得出隨著緩存大小的不斷增加，本文提出的基于馬爾可夫相遇時間間隔預測的擁塞控制策略CCSMP的投遞概率始終大于DO和DF兩種控制策略下的投遞成功率，這說明經過了CCSMP擁塞控制顯著提高了Epidemic路由算法的投遞成功率。圖5中CCSMP的網絡平均時延比另外兩種控制策略低200s左右的時間，并且隨著緩存大小的增加呈現一種穩定趨勢，這說明CCSMP擁塞控制策略在增加投遞成功率的同時也減小了網絡時延。對比圖6中3種擁塞控制策略的負載比率，負載比率高說明成功投遞的報文占報文成功傳遞總次數的比率低，進一步說明無用的數據傳輸比較多，CCSMP的負載比率明顯小于DO和DF，說明本文提出的擁塞控制策略從一定程度上也減少了網絡開銷，從圖7中數據可以看出隨著緩存大小的增加，丟包率顯著降低，但是CCSMP的丟包率一直小于另外兩種擁塞控制策略，平均小一個百分點左右。為了分析不同的傳輸速率是否會對文中提出的擁塞控制策略產生影響，實驗采用120Kbps,250Kbps,380Kbps,510Kbps,640Kbps,770Kbps6種傳輸速度作仿真，同樣是在相同的場景下對比CCSMP，DO，DF三種擁塞控制策略的投遞成功率（圖8），平均時延（圖9）以及負載比率（圖10），丟包率（圖11）。從圖8中數據經分析得出如下結論：隨著傳輸速率的增加DF和DO兩種策略的投遞成功率趨于穩定，沒有大幅度抖動，而CCSMP的投遞成功率有些許上升，并且持續處于比較高的狀態。圖9中傳輸速率的變化同樣沒有嚴重影響擁塞控制策略下的網絡時延，CCSMP的平均時延始終比其他兩種控制策略小200s左右，說明該擁塞控制協議的平均時延受傳輸速率影響不大。從圖10中可見當傳輸速率較小時，網絡的負載比率與擁塞控制協議關系不大，但是隨著傳輸速率的增長，CCSMP的負載比率明顯小于DF和DO，說明文中提出的擁塞控制協議能夠一定程度上減小網絡負載,最后從圖11中數據可以看出丟包率隨著傳輸速率的增加明顯增大，但是CCSMP相比于DF和DO兩種擁塞控制策略丟包率較小。為了說明CCSMP并不局限于Epidemic路由策略，本文在完全相同的實驗環境下，對sprayandwait路由協議下的3種擁塞控制策略同樣進行了測試，考慮到sprayandwait對報文的副本數做了控制，從一定程度上預防了擁塞的發生，所以針對sprayandwait路由算法的緩存大小設置為2M，5M，8M和10M，報文初始副本數定義為6，測得投遞成功率（圖12），網絡平均時延（見圖13），負載比率（見圖14）和丟包率（見圖15）。從圖12中數據可以看出，當緩存較小的時候CCSMP擁塞控制策略相比于DF和DO能夠增加投遞成功率，但當緩存增大到一定程度就不會再有明顯的差別，這主要是因為這種情況下緩存大小足夠承受初始報文為6的網絡報文量，擁塞發生的較少。從圖13中數據可以看出在緩存較少的情況下CCSMP有著更小的網絡時延。圖14和15中分析得出CCSMP與其他兩種擁塞控制策略相比能在一定程度上減少負載比率和丟包率。為了在sprayandwait路由算法下分析不同的傳輸速率對文中提出的擁塞控制策略產生的影響，將緩存大小設置為5M，實驗采用120Kbps,250Kbps,380Kbps,510Kbps,640Kbps,770Kbps6種傳輸速度作仿真，得到投遞成功率（圖16），平均時延（圖17）以及負載比率（圖18），丟包率（圖19）。#p#分頁標題#e#
根據圖16中的數據，在節點本地只有5M緩存的情況下CCSMP表現出了更好的投遞成功率，并且隨著傳輸速率的提升投遞成功率呈穩步上升趨勢。在圖17中CCSMP的平均時延遠小于DF和DO兩種擁塞控制策略。從圖18的數據可以看出CCSMP的負載比率隨著傳輸速度的變化沒有大幅度波動，并且處于較低的狀態，同樣在圖19中可以看出CCSMP在不同的傳輸速率下有著更小的丟包率。
結束語
本文提出了一種基于馬爾可夫相遇時間間隔預測的擁塞控制策略CCSMP，該策略包括排隊機制和丟棄機制兩部分，并將馬爾可夫模型應用到節點的相遇時間間隔的預測上，通過預測值結合報文復制或者傳遞的次數和剩余TTL值來計算報文的效用權值，通過這個權值可以決定緩存中的排隊順序和丟棄方式。為了驗證工作的有效性，在THEONE平臺上對Epidemic和Sprayandwait兩種路由協議進行仿真，將CCSMP與DF和DO兩種擁塞控制策略進行對比，仿真結果表明CCSMP能夠明顯的增加投遞成功率，減小平均網絡時延，并且在一定程度上減小了網絡負載和丟包率。（本文圖、表略）
本文作者：楊永建 王恩 杜占瑋 單位：吉林大學 計算機科學與技術學院