基于灰色马尔科夫预测的移动多路传输调度算法

李 宁，衷璐洁，高 楷

（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 预测对子流性能进行评估，并通过调整相应发送窗口大小来最小化异构网络中的传输时延差异。实验结果表明，该算法可有效解决数据包乱序问题并显著提升网络传输性能。下一步将采用个性化数据传输算法对多路传输数据调度进行优化，进一步提高网络资源利用率与网络服务质量。