基于灰色馬爾科夫預測的移動多路傳輸調度算法

李 寧，衷璐潔，高 楷

（1.首都師范大學信息工程學院，北京 100048；2.北京郵電大學網絡技術研究院，北京 100876）

0 概述

隨著移動互聯網與通信技術的快速發展，5G 網絡、移動車載網絡中的新型業務需求對網絡傳輸速率及帶寬提出了更高要求［1］。為保證移動設備的連接性能，通常為其配置多個接口，以降低運行成本、簡化網絡管理并提供良好的用戶體驗。多路徑傳輸控制協議（Multi-Path Transmission Control Protocol，MPTCP）使用多路徑發送數據包，可滿足實時性、交互性與個性化的業務需求。因此，MPTCP 成為未來互聯網數據傳輸的發展趨勢之一［2］，但是通過多路徑傳輸來提高網絡性能仍存在諸多挑戰。例如，在有限的接收緩沖區和異構網絡環境中，由于網絡性能不穩定以及傳輸路徑性能差異較大等因素容易造成接收端亂序，從而引發緩沖區阻塞問題，降低網絡多路徑的傳輸性能［3］。其中，具有代表性的場景有車載移動用戶與手機移動用戶通過接入各自的異構網絡訪問互聯網時，若不對存在路徑差異和無線網絡不可靠的情況進行管控，將會導致分組頻繁亂序及數據丟失，造成數據包重傳占用鏈路資源和接收端緩沖區阻塞等問題，嚴重影響服務質量與用戶體驗［4］。

本文綜合考慮異構網絡鏈路差異、子流性能評估以及多路徑帶寬負載均衡等問題，提出一種移動多路傳輸調度算法。該算法利用前向傳輸時間（Forward Transmission Time，FTT）實現子流傳輸性能的準確預測，并依據FTT 對數據包進行分發，保障數據包到達緩沖區的時間趨近于最優子流FTT，以提高多路徑帶寬利用率與數據傳輸效率。

1 相關工作

1.1 MPTCP 數據調度

MPTCP 由IETF 提出［5］，其作為TCP 的擴展，目的是通過聚合多路徑帶寬來提高資源利用率及網絡吞吐量。數據調度算法是MPTCP 的重要組成部分，MPTCP數據調度對應用層數據流實施分段并在每個子流上進行數據傳輸，同時提供耦合擁塞控制以保障與正常TCP連接的公平性［6］。傳統的MPTCP 數據調度算法通常采用靜態和動態兩類方式。其中，靜態方式主要針對同構網絡環境，該類算法不考慮路徑的狀態特性，其是通過借助擁塞窗口對數據包進行分配。靜態方式的代表性算法有隨機調度和輪詢調度，輪詢調度（Round-Robin，RR）是一種廣泛應用于數據包分配［7］的算法，該算法對將要發送的數據段，從當前所有可用路徑中按子路徑從1～N的順序選取下一個有空余發送窗口的路徑作為本次調度的路徑選擇。靜態方式對于同構網絡的性能表現較優，但在異構網絡環境中其傳輸性能沒有單路徑傳輸更有優勢。動態方式針對靜態調度策略的不足，將路徑特性納入考慮，且每次對路徑選擇時根據各路徑的傳輸特性優先選擇傳輸質量較好的路徑進行數據傳輸［8］。其中，基于最小往返時延（Round-Trip Time，RTT）的調度算法LowRTT［9］優先選擇傳輸延遲最小的路徑作為最佳路徑，且當最佳路徑的發送窗口為0 時，再選擇傳輸時延次小的路徑作為最佳路徑。與RR 算法相比，LowRTT 算法能夠更好地緩解數據包亂序問題，但由于每次僅選用一條子流進行數據傳輸，其未能充分利用多路徑并行傳輸的優勢［10］。

1.2 灰色馬爾科夫預測模型

灰色預測模型（Grey predicition Model，GM）是一種分析“部分信息已知，部分信息未知”不確定性系統問題的有效方法［11］。該模型通過累加生成方式產生新的數據序列，使用新產生的數據序列代替原始數據序列，并進一步應用微分方程求解完成新數據序列的預測。與目前主流的指數平滑、回歸分析、支持向量機及神經網絡等預測方法相比，灰色預測模型具有無需統計大量樣本數據即可解決小樣本短序列建模問題的優勢。灰色預測模型GM（1，N）是GM 的一種改進模型，該模型在保留小樣本數據預測特點的同時，增加了影響數據變化的其他因素數據，可進一步提升灰色預測模型的精度［12］。

馬爾科夫模型對隨機變化的動態系統進行預測時，它將時間序列看作一個隨機過程，通過對事物不同狀態的初始概率與狀態之間的轉移概率進行深入研究，確定事物未來狀態的變化趨勢［13］。這種模型的實質是一種建立在“狀態”“狀態轉移”概念上的動態隨機數學模型，即通過研究對象的當前時刻狀態及狀態轉移概率來判斷研究對象下一時刻的所處狀態。

考慮到灰色模型的使用對象主要是預測時間短且波動性較小的系統對象，本文提出將灰色模型與馬爾科夫模型相結合的多路傳輸數據調度機制——灰色馬爾科夫多路傳輸調度（Grey-Markov Multi-path Transmission Scheduling，GMM-TS）。用灰色模型對數據進行擬合并找出變化趨勢，然后在此基礎上與馬爾科夫模型相融合，利用其具有對隨機過程提取概率分布規律的特點，進一步提升灰色預測模型對隨機波動較大數據序列的預測準確度。

2 自適應多路傳輸數據調度機制

2.1 問題分析

在無線異構網絡中采用MPTCP 傳輸數據包時，不同類型的通信系統相融合需使用多條路徑，且傳輸過程的鏈路性能存在較大差異。傳輸性能差異將造成傳輸序列號（Transmission Sequence Number，TSN）較大的數據包先到達緩沖區，從而引起數據包亂序問題［14］，而接收端由于無法及時將緩沖區中的數據向上層應用傳輸而造成數據流傳輸時間的延長。

圖1 為異構子流的多路傳輸示例。假設子流1 的傳輸速率是子流2的3倍，TSN=1的數據包與TSN=2的數據包在同一時刻分別由子流1 和子流2 發送。當子流1 發送的TSN=1 的數據包到達接收端后提交至上層應用，繼續發送TSN=3 與TSN=4 的數據包，當TSN=3與TSN=4 的數據包到達接收端緩沖區后，暫存緩沖區并等待TSN=2 到達后按序交付應用層。在時間段T內提交到應用層的僅有TSN=1 數據包，且此時的有效吞吐量Q=1/T，而在順序傳輸的情況下Q=3/T。與此同時，由于接收端緩沖區的限制，亂序數據包會引發接收端緩沖區阻塞，致使擁塞控制機制減緩發送速率，甚至停止發送［15］。若MPTCP 分發數據時僅考慮擁塞窗口和緩沖區大小，當發送窗口小于最大報文段MSS 時，則會造成接收緩沖區中存在大量數據包碎片。由于拼接數據包會占用額外的資源，因此會加重數據包亂序。

圖1 異構子流的多路傳輸示例Fig.1 Example of multi-path transmisson of heterogeneous substreams

為緩解無線異構網絡中因鏈路差異而造成的數據包亂序及緩沖區阻塞問題，本文提出一種基于灰色系統中離散數據預測的GM（1，N）預測模型與馬爾科夫優化的自適應多路傳輸數據調度算法GMM-S。綜合考慮子流的丟包率、發送窗口大小及擁塞狀態對子流性能的影響，對未來時刻子流前向傳輸時延FTT 進行預測并進行相關路徑的性能評估，同時將其用作數據分發依據，實現傳輸數據的多子流自適應動態調整。

考慮到MPTCP 的子流傳輸性能除了受到路徑吞吐量Q、傳輸時延T、丟包率L與發送窗口S等多種因素影響外［16］，還會受到如終端與基站的距離等不確定因素的影響。為此，本文將MPTCP 子流傳輸性能的變化過程R建模為一個受多種因素影響的灰過程，具體如式（1）所示：

其中，Cf表示已知因素的影響部分，Uf表示未知因素的影響部分，Q，T，L，S分別表示吞吐量、傳輸時延、丟包率及發送窗口，α，β，γ，δ表示各確定因素相應的權重，xi表示影響R變化的未知因素，εi表示未知影響因素的權重，n為未知影響因素的個數。α，β，γ，δ值可通過建立GM（1，N）模型微分方程求得。

在無線異構網絡多路傳輸過程中，慢啟動階段子流的FTT 會呈現出幾何級增長趨勢，而在進入擁塞避免階段時FTT 則會大幅下降，當伴隨丟包現象的發生時，FTT 又將大幅上升［17］。一般而言，FTT 的時間序列呈現近似幾何級增長規律，同時在某些時刻存在較大波動。基于此，本文提出進一步引入馬爾科夫模型以揭示系統在不同狀態區間轉移的內在規律，并對灰色預測模型的殘差序列進行修正。

2.2 GMM-S 自適應多路傳輸數據調度方案

基于GM（1，N）的FTT 預測及馬爾科夫優化多路數據傳輸調度方案主要由基于GM（1，N）預測與馬爾科夫優化的子流性能評估模型以及數據分發調度2 個部分組成，具體構成如圖2 所示。其中，實線箭頭表示數據流，虛線箭頭表示信息流。在STPEM中首先獲取MPTCP 子流中的發送窗口、丟包率、吞吐量和前向傳輸時延數據4 組可直接獲取的已知影響因素，即選取N=4，建立GM（1，4）模型預測該子流下一時刻的FTT，之后在GM（1，4）預測基礎上實施馬爾科夫殘差修正，即根據FTT 預測值與實際值的相對誤差建立馬爾科夫殘差修正模型對GM（1，4）預測值進行修正，以完成對子流FTT 的預測，量化子流傳輸質量，且修正后的FTT 預測值越小表示該子流的傳輸性能越好。隨后，在DDS 部分根據FTT 預測值對子流進行分類，選取最短預測FTT 的子流為優秀子流。在優秀子流上根據擁塞窗口大小發送足夠多數量的數據包，而在普通子流上，則根據其與優秀子流的預測FTT 時延差，實施傳輸數據包發送數量的動態調整。

圖2 GMM-S 數據調度方案Fig.2 GMM-S data scheduling scheme

2.2.1 GM（1，4）預測模型建立

本文選取子流發送窗口S、丟包率L、吞吐量Q和前向傳輸時延FTT 作為原始預測樣本數據：

1）數據處理。令F={f1，f2，…，fn}表示MPTCP的子流集合，FTTf為子流f的前向時延，Sf為子流f的發送窗口，Lf為子流f的丟包率，Qf為子流f的吞吐量。假設當前為第t輪數據包發送，以子流f1為例，子流數據包前向傳輸時間FTTf1、發送窗口大小Sf1、子流丟包率Lf1與子流吞吐量Qf1分別如式（2）～式（5）所示：

將上述4 組數據作為原始樣本生成4 個數列，原始樣本數據矩陣X(0)為：

將X(0)通過一階累加運算來增強原始數列的規律性，弱化原始數據列的隨機性，得到更有規律的數據矩陣X(1)：

將FTT 的一階累加矩陣FTT(1)進行緊鄰均值計算，生成緊鄰均值矩陣

2）模型建立。描述FTT 多元一階線性動態微分方程模型的灰微分方程如下所示：

其中，FTT(0)(k) 表示關鍵影響因素FTT 的原始數據，稱為灰導數為FTT 一階累加數據的緊鄰均值，稱為背景值，a，bi(i=2，3，4)表示參數，且可采用最小二乘法求出待定系數a和bi的值。

對于GM（1，4）的灰微分方程，若將X(1)(k)視為連續變量，則X(1)(k)為關于時間t的函數，GM（1，4）的白化微分方程定義如下：

對式（10）進行求解，可得G M（1，4）的白化微分方程的時間響應函數如下所示

累減還原得序列FTT(0)的預測值：

基于GM（1，4）的FTT 預測算法描述如算法1 所示。其中，步驟1～步驟4 是對數據的收集與預處理，步驟5～步驟8 對預處理后的數據建立GM（1，4）模型并進行FTT 預測。

算法1基于GM（1，4）的FTT 預測

2.2.2 馬爾科夫殘差修正

表1 殘差狀態劃分結果Table 1 Residual state partition results

1）建立狀態轉移概率矩陣。由狀態Ei轉移到狀態Ej的次數為ni→j，以狀態Ei為起點轉向另一個狀態的次數為Ni，則狀態Ei轉移到狀態Ej的狀態轉移概率為：

根據式（14）構建狀態轉移概率矩陣P為：

2）計算預測值。建立狀態轉移概率矩陣P后，假設t時刻對象處于Ei狀態，若P中的第i行滿足maxPi=pij，則認為下一時刻Ei最有可能轉移到Ej狀態，并取Ej狀態區間[θj，θj+1]的中位數作為n+1 時刻的預測值。

對大國的不信任和防范是吳努政府的另一個基本心理，這是緬甸中立不結盟外交取向形成的重要原因。對于大國，吳努直言：他們都是為了自己的利益而不是其他人利益而行事的，所以不要讓緬甸成為他們的傀儡，也絕不能完全相信他們，把緬甸的命運交到他們手里。[86]1957年，緬甸副總理吳巴瑞、吳覺迎在北京與毛澤東的會談中，解釋說緬甸害怕大國“是十分自然的，因為從歷史上看大國總是欺侮小國。緬甸處在大國之間”。[87]

根據狀態轉移矩陣P對進行修正，并獲得最終預測值：

其中，Epmax表示在狀態轉移矩陣中，t時刻狀態Ei根據最大轉移概率maxPi轉移到狀態Ej的誤差區間步長。

算法2 給出了GM（1，4）FTT 預測值馬爾科夫修正算法的描述，其中步驟1 與步驟2 負責建立狀態轉移矩陣，步驟3～步驟7 通過狀態轉移矩陣修正灰色模型FTT 預測值，步驟8 對狀態轉移矩陣進行更新。

算法2GM（1，4）FTT 預測值馬爾科夫修正

2.2.3 基于FTTF′的數據包分發算法

為減少緩存阻塞帶來的負面影響，本文在子流上通過前向傳輸時延預測值評估該子流的性能，并動態設定傳輸數據量。根據GM-Markov 模型所求得的前向傳輸時延預測值FTT′對子流進行分類。將最小FTT′min的路徑選作優秀子流，記作fi，其他子流標記為普通子流。對于優秀子流fi，數據包分發方法［18］為：

其中，cwndi表示子流fi的擁塞窗口，C為發送緩沖區的待發送數據包。

為使數據包按序到達接收端，減小傳輸時間差異，則定義為普通子流并按下式發送數據：

若Sj≤0，則該子流不傳輸數據。這樣的發送窗口大小動態調節方式，可使子流前向傳輸時延趨近于最優子流前向時延，從而減小路徑間傳輸時延差異，解決由傳輸時延差異帶來的數據包亂序、緩存阻塞及傳輸性能下降等問題。

算法3 給出了GMM-S 數據包分發算法。其中，步驟1 先獲取FTT 預測值，步驟2～步驟5 實現在優秀子流上發送數據包，步驟6～步驟13 實現在普通子流上數據包的發送。

算法3GMM-S 數據包分發

3 實驗設置與分析

3.1 仿真環境設置

仿真實驗環境基于Ubuntu16.04，64 位操作系統，使用NS 工具建立網絡拓撲，NS 版本為3.29 并添加了MPTCP 模塊［19］。網絡測試拓撲如圖3 所示。

圖3 異構無線網絡測試拓撲Fig.3 Heterogeneous wireless network test topology

為模擬真實無線環境，在每條路徑上設置分組丟失模型來模擬分布式分組丟失。路徑A 使用LTE蜂窩網絡，設置4 Mb/s 的接入帶寬。考慮到LTE 在大范圍內相對穩定［20］，丟包率設置為固定值0.01。路徑B 使用公共WiFi 網絡，設置10 Mb/s 的接入帶寬，路徑丟包率設置為0～1.0。無線異構網絡拓撲的具體參數配置如表2 所示。實驗在NS-3.29 仿真平臺下，以傳輸數據量、重傳次數、亂序塊大小/個數與吞吐量等參數作為主要指標，同時選取RR 算法及LowRTT 算法作為傳輸性能的比較對象。

表2 異構無線網絡拓撲的參數配置Table 2 Parameter configuration of heterogeneous wireless network topology

3.2 實驗結果及分析

表3 給出了GMM-S、RR 及LowRTT 三種調度算法的傳輸時間、傳輸數據總量、傳輸次數、重傳次數、重傳占比及最大重傳數據段等數據。

表3 3 種數據調度算法的數據傳輸結果Table 3 Data transmission results of three data scheduling algorithms

相較于RR 和LowRTT 算法，本文提出的GMM-S算法在獲得更高吞吐量的同時有效減少了重傳次數。這主要是因為GMM-S 基于GM（1，N）和馬爾科夫優化的子流性能評估模型更有效地完成路徑質量的準確評價，實現子流數據包發送的自適應動態調整。

3.2.1 GM（1，N）-Markov 預測誤差分析

圖4 給出本文實驗設置下從第44 次數據包傳輸開始后采用GM（1，4）-Markov 算法預測的最小FTT子流與實際最小FTT 子流的對比數據。在第1 次～第43 次數據包傳輸過程中，Subflow_3 是WiFi 鏈路的主子流且有較高的帶寬，在不產生丟包時該子流具有最小FTT，在GM（1，4）-Markov 預測算法狀態轉移概率矩陣中，Subflow_3 表現出最大的矩陣元素值。此后，即從第44 次開始，GM（1，4）-Markov 算法在綜合分析擁塞窗口、吞吐量及丟包情況的基礎上選出具有最小FTT 的Subflow_1。在第47 次數據包傳輸時，GM（1，4）-Markov 算法給出了最小FTT 子流為子流3 的預判，但由于此時實際傳輸子流仍為子流1，因此出現預測值與實際值不一致的情形，即產生誤差。從第48 次數據包傳輸開始至第59 次數據包傳輸，實際最小FTT 子流為Subflow_3。類似的誤差產生情形還發生在第67 次數據包傳輸。在隨后的數據包傳輸過程中，由于Markov 殘差修正算法的作用，誤差得以不斷修正，GM（1，4）-Markov 算法預測精度不斷提高，且總誤差控制在1.8%左右。

圖4 GM（1，N）-Markov 算法預測最小FTT 子流效果Fig.4 Effect of GM（1，N）-Markov algorithm on predicting the minimum FTT subflow

3.2.2 數據包亂序分析

圖5 給出了應用GMM-S、RR、LowRTT 三種數據調度算法在無線異構網絡中傳輸過程中出現的數據塊亂序情況。從圖5 可以看出：在50 s～100 s 的時間間隔內，RR 算法共發生199 次亂序，最大亂序塊大小為27 000 bit；LowRTT 算法共發生749 次亂序，最大亂序塊大小為29 000 bit；而GMM-S 算法共發生176 次亂序，最大亂序塊大小為16 000 bit。總體而言，GMM-S 相比RR 和LowRTT 所產生的亂序塊更少且亂序數據塊也更小。這主要是由于GMM-S 實現了路徑質量的實時評估，并在數據分發時根據子流預測FTT 自適應地分發數據包，盡可能地保障數據包按序到達所導致的，GMM-S 不僅明顯減少了數據包亂序的發生次數，同時也降低了亂序程度。

圖5 3 種數據調度算法的亂序到達結果對比Fig.5 Comparison of out-of-order arrival resuts of three data scheduling algorithms

3.2.3 數據發送到達結果分析

在實驗中，本文通過設置隨機丟包率來模擬無線異構網絡的不確定性，在傳輸過程中丟包的發生會引發重傳。圖6 給出了GMM-S、RR、LowRTT 三種算法數據發送到達結果對比。在理想狀態下，按序傳輸數據包且接收端按序接收，TSN 隨時間變化的圖像應為單調平穩遞增的圖像，但重傳的發生會因為反復傳輸而使圖像出現水平線段。從圖6 可以看出：RR 在95.5 s 時發生了一次重傳，持續時間為0.2 s；LowRTT 在95.6 s時發生了一次重傳，持續時間為0.2 s；GMM-S 則是在95.8 s 時發生了一次重傳，持續時間為0.1 s。GMM-S 的重傳持續時間最少。此外，在數據傳輸過程中，若發生亂序或發送數據包過大的情況會導致緩沖區阻塞，致使發送端數據包停發，在圖像中表現為中斷現象。在圖6 中，95 s～97 s 的時間段內，RR 產生了4 次明顯中斷，LowRTT 產生了5 次明顯中斷，而GMM-S 僅產生2 次明顯中斷，且中斷時間遠小于RR 和LowRTT，這表明GMM-S工作時接收端數據接收更為平穩。

圖6 3 種數據調度算法的數據發送到達結果對比Fig.6 Comparison of data transmission and arrival results of three data scheduling algorithms

3.2.4 吞吐量

有效吞吐量（Effective Throughput，ET）［21］定義為單位時間t內由傳輸層送達應用層的數據量（Application lauer Data，AD），即：

在圖7 中，RR 的有效吞吐量波動區間約為0.1，LowRTT 有效吞吐量波動區間約為0.15，而GMM-S波動區間僅為0.01，且持續穩定在10.06 Kb/s～10.07 Kb/s 之間。在95 s～96 s 時間段內RR、LowRTT及GMM-S 均發生了重傳，有效吞吐量發生了下降，但由于GMM-S 的自適應數據包分發機制會在產生丟包的子流上動態分配較少的數據包，因此GMM-S的有效吞吐量在重傳發生時未受到嚴重影響。

圖7 3 種數據調度算法的有效吞吐量對比Fig.7 Comparison of effective throughput variation of three data scheduling algorithms

3.2.5 服務質量評估

在實際應用場景中，較大的端到端時延會嚴重影響實時傳輸的服務質量。比如在實時視頻傳輸服務中，若因為發送率波動較大引起應用層數據接收時間間隔增大，用戶會感受到明顯的視頻卡頓或中斷。圖8 給出了90 s～100 s 時間段內數據發送速率的變化情況。從圖8 可以看出，L ow RT T 在97 s 時發送速率存在大幅增加的現象，這是因為在95 s～96 s期間發生了數據包亂序現象，在97 s 時緩沖區中的亂序數據包順序交付給應用層，此時的擁塞窗口增大，發送窗口因而變大，LowRTT 的發送速率出現明顯上升。而在GMM-S 中，每條子流維護各自的擁塞窗口，數據分發調度綜合考慮子流的傳輸性能為子流分發合理大小的數據包，因此不會出現LowRTT發送速率大幅波動的情形。

圖8 3 種數據調度算法的發送速率對比Fig.8 Comparison of transmission rate of three data scheduling algorithms

圖9給出了應用層數據接收時間間隔的分布數據，應用層接收時間間隔分布以平均值±95%的置信區間來反映。從圖9 可以看出：RR 的應用層數據接收時間間隔主要分布在1.18E7 ns～1.2E7 ns之間；LowRTT 的應用層數據接收時間間隔主要分布在1.16E7 ns～1.18E7 ns 之間；而GMM-S 的應用層數據接收時間間隔則主要分布在1.11E7 ns～1.13E7 ns 之間，范圍明顯小于RR和LowRTT。這表明GMM-S可提供更穩定的應用層數據傳送，為網絡傳輸服務質量及良好的用戶體驗提供保障。

圖9 應用層數據接收時間間隔分布Fig.9 Distribution of application layer data receiving interval

4 結束語

本文提出一種基于GM（1，N）前向傳輸時延預測與馬爾科夫優化的自適應多路傳輸數據調度算法GMM-S，該算法綜合考慮子流中吞吐量、丟包率及發送窗口等因素對傳輸時延的影響，采用FTT 預測對子流性能進行評估，并通過調整相應發送窗口大小來最小化異構網絡中的傳輸時延差異。實驗結果表明，該算法可有效解決數據包亂序問題并顯著提升網絡傳輸性能。下一步將采用個性化數據傳輸算法對多路傳輸數據調度進行優化，進一步提高網絡資源利用率與網絡服務質量。