基于改进GM（1，1）模型-马尔科夫残差修正的网络性能预测*

孙明玮齐玉东王晓虹

（1.海军航空大学 烟台 264001）（2.中国人民解放军第107医院 烟台 264001）

1 引言

网络性能参数的准确预测在计算机网络的设计和管理、拥塞控制和动态带宽分配等领域具有十分重要的作用。要完成这项工作，建立精确的预测模型尤为重要。这对于网络性能的准确分析与预测、拥塞管理、提高网络服务质量等方面具有十分重要的价值。

目前关于网络性能预测的研究已经取得一定成果。邵雪梅［1］等通过分析校园网网络流量的现状及特点，利用RBF神经网络对网络流量进行预测，虽然预测精度较高，适合描述流量的不稳定性，但是训练神经网络需要大量的历史数据支撑，并且计算量较大，实时建模有一定的难度；刘宗磊［2］等将时间序列模型与灰色预测模型的结果作为输入，建立基于RBF神经网络模型的组合预测模型，但是该模型对于处理具有波动性、周期性等特征的数据精度有待提高；李捷［3］等通过构建卡尔曼滤波和小波分析混合的流量预测算法，对网络流量的线性部分和非线性部分进行预测，该方法虽然具有实时性，但是缺乏对网络流量的长期预测；唐万梅［4］结合灰色预测模型与支持向量机二者的优点，构造出灰色支持向量机预测预测模型，但是该模型适用于处理具有规律的原始数据序列，对于网络性能数据而言，其变化并无规律可言。

针对以上研究的不足，本文拟建立一个基于马尔科夫残差修正的改进GM（1，1）模型的网络性能预测方法。该方法首先采用移动窗口最小二乘多项式平滑算法对实验数据进行平滑处理，然后将处理后的数据应用于灰色GM（1，1）预测模型中，并采用马尔科夫残差修正模型对预测结果进行修改以提高预测精度。

2 改进的灰色残差修正预测模型

2.1 灰色GM（1，1）预测模型

灰色预测模型（Gray ForecastModel）［5］是通过少量的、不完全的信息建立数学模型并做出预测的一种方法。当应用运筹学的思想解决实际问题、指定发展战略和政策、进行重大问题的决策时，该模型根据客观事物过去和现在的发展规律，借助于科学的方法对其未来的发展趋势和状况进行描述和分析，并形成科学的假设和判断。灰色预测模型所需要的建模信息量少，运算方便，建模精度较高，在各种预测领域中都有广泛的应用，是处理小样本预测问题的有效工具。

灰色GM（1，1）预测模型的实质是对原始数据作一次累加处理，使生成的数据具有一定的规律，再通过建立一阶线性微分方程，求得拟合曲线方程，用来对系统进行预测［6］。

设原始非零数据序列为X(0)={x(0)(1)，x(0)(2)，…，x(0)(n)}，X(0)的一阶累加序列（1-AGO序列）为

称Z(1)为X(1)的紧邻均值生成序列（也称为背景构造值），记为

其中：

将式（3）得到的向量a^带入到一阶线性微分方程中求得拟合曲线方程为

对x^(1)(t+1)作一次累减生成，即得灰色GM（1，1）预测模型为

2.2 灰色GM（1，1）预测模型改进

虽然传统灰色GM（1，1）预测模型中经过一次累加生成后的数据序列呈现严格的指数增长趋势，可以有效保证数据的拟合度，但是若原始数据序列出现较大的波动时，一次累加生成后数据序列的增长趋势将呈现不平滑现象，此时预测误差较大。为了减小误差，需要对传统灰色GM（1，1）预测模型的原始数据序列做平滑处理。

本文采用移动窗口最小二乘多项式平滑算法（Savitzky-Golay Smoothing）进行数据平滑处理。Savitzky-Golay Smoothing算法［7～9］最初于1964年由Savitzky和Golay二人提出，主要用于对数据流的平滑降噪处理，如今在图像处理领域中得到较为广泛使用，该算法是一种基于最小二乘法的局部拟合方法，从数据流的起点开始，在事先确定的平滑窗口内对数据流进行平滑处理，通过向后滑动平滑窗口直到数据流的终点为止，其最大的特点就是在平滑数据的同时保证数据流的形状、宽度、变化趋势不变。

假设原始数据序列为X，确定平滑窗口大小为m（通常情况下选择奇数，本文选择m=7），多项式最高阶次数为n（这里选择n=3）。移动窗口最小二乘多项式平滑算法就是利用中心数据点与前三个数据点和后三个数据点进行最小二乘拟合，每一个数据点可以表示为不同的多项式结果，从而利用7个数据点组成含有n+1个未知数，m个方程的方程组：

结合线性代数中的矩阵理论知识，该方程组可表示成如下矩阵形式：

根据最小二乘法得到b的解析解b*：

进而得到方程组中各未知数的最小二乘解为

将上述计算结果带入式（6）中可以求出平滑后的数据点：

从结果表达式中可以发现，得到的结果其实是该平滑窗口内部各点的线性组合，即新的数据序列由平滑窗口内各点进行加权计算而得。采用移动窗口最小二乘多项式平滑算法进行数据平滑处理，既增加了当前数据的权重，又避免造成数据的剧烈波动。

2.3 残差修正模型

若使用原始数据序列建立的预测模型检验不能满足要求时，需要对建立的模型进行残差修正。假设通过改进灰色GM（1，1）模型计算后的残差序列为

由于该残差序列中元素的符号有正有负，因此对残差序列进行修正之前需要对其进行正化处理，即：

对正化残差序列建立改进灰色GM（1，1）预测模型，并利用最小二乘法得到ε(0)(t+1)′的残差预测值为

进而得到：

其中，残差系数σ(t)是由残差的正负值决定。但是，当t＞n时，σ(t)的取值不确定。此时，引入马尔科夫过程。

马尔科夫预测模型在数据预测方面呈现出精度高、泛化能力强、适用范围广等特点，克服了传统模型需要大量历史数据的缺点，只需要从数据序列中找出内在规律，通过建立相关模型进行预测［10～11］。马尔科夫预测模型描述的是一个随机时间序列的动态变化过程，它认为在事物的发展过程中，从一种状态转变到另一种状态是具有转移概率的，而这种转移概率可根据历史数据推算出来，适用于处理随机波动性较大的数据序列［12］。若第t时刻模型的残差值为正数，记状态值为1；若为负数，记状态值为0。将残差值从状态i转移到状态j的概率记为一步转移概率P，且一步转移概率P可用下式来估计：

其中：Mi表示残差值为状态i的次数；Mij表示残差值从状态i转变到状态j的次数，定义向量

1表示状态值为1（+）的概率，s(0)

2表示状态值为0（-）的概率，经过n′步转移之后的状态概率为其中Rn′表示由Pij的值构成的n′步转移矩阵。因此，根据向量s(n′)中元素的大小关系确定第n+n′时刻的残差符号为

综上所述，利用马尔科夫残差模型修正改进灰色GM（1，1）模型公式为

3 模型合理性检验

灰色GM（1，1）模型的精度检验通常采用后验差检验C和小概率频率检验P。其中：

这里Dε表示残差序列的标准差，D0表示原始数据序列的标准差，εˉ表示残差序列的均值。表1表示的是不同检验值结果对应的精度等级，通过计算改进前与改进后的后验差值和小概率频率值鉴定模型的精度等级，从而验证改进后模型的合理性。

表1 模型精度检验值

4 改进灰色GM（1，1）预测模型在网络性能预测中应用

为验证本文提出的基于马尔科夫残差修正的改进灰色GM（1，1）模型的正确性和可靠性，本文选择QWS数据集，并通过有效性和吞吐量扩展出互操作性和扩展性两条属性［13］，表2为截取的部分实验数据。

从表2数据可知，由于个别属性的数据序列（如响应时间、吞吐量、延迟）值域范围较大，因而存在较大的波动，为了提高模型拟合精度，需要在做一次累加生成之前，对原始数据进行预处理。

表2 实验数据

4.1 数据预处理

以响应时间数据为例，记历史数据序列为

首先对原始数据序列作一次累加生成，消除原始数据上下振荡的趋势，记一次累加生成数据序列为

随后对一次累加生成数据序列作对数变换：

最终以对数变换序列作为原始数据序列。

4.2 建立灰色GM（1，1）模型

利用式（1）～（5）对原始数据序列进行预测，得到采用传统灰色GM（1，1）模型方法预测计算公式为

接下来对传统灰色GM（1，1）模型进行改进：

1）首先利用移动窗口最小二乘多项式平滑算法对一次累加生成得数据序列进行数据平滑处理，本文选用平滑窗口为7，最高阶次数为3的移动窗口最小二乘多项式平滑算法得到平滑序列为

2）将平滑后的数据放入预测公式中，计算预测值与真实值的残差序列，并利用残差修正模型得到残差预测公式：

3）计算马尔科夫残差修正模型

通过对比残差值与残差预测值确定状态转移过程为011100。由此得到转移矩阵为

将t=7作为初始状态，根据式（17）～（18）确定后续时刻得残差符号，进而得到经马尔科夫残差修正模型修正后的预测值。本文将t=1～7的数据作为模型的拟合数据，将t=8～11的数据作为模型的预测检验数据。表3为传统灰色GM（1，1）模型与改进后的灰色GM（1，1）模型预测值对比表。从表3可以看到，传统灰色GM（1，1）模型得到的预测结果不理想，预测值与真实值间的相对误差较大，整个模型的后验差为0.7223<0.80，小概率误差为0.7143>0.70，精度等级为三级，很难取得良好的预测效果。而采用改进的灰色GM（1，1）模型通过数据平滑处理，将实验数据转化为适合灰色预测模型的形式，同时采用马尔科夫残差修正模型修正预测结果，最终得到的平均相对误差为2.832%，后验差为0.0513<0.35，小概率误差为1>0.95，精度等级为一级，有效地减小了预测值与实际值间的误差，提高了拟合精度。

表3 响应时间预测值对比表

利用本文提出的预测方法对其他指标的数据进行预测，预测结果见表4所示，从表4中可以看到预测结果可以较为精确反映现实情况下各指标的变化规律。

表4 各指标预测值

5 结语

针对传统灰色GM（1，1）预测模型拟合精度不高的问题，本文从修正原始数据的方向出发，提出一种基于马尔科夫残差修正的改进灰色GM（1，1）预测模型。通过数据验证，改进后的预测模型对于波动情况较大的数据分析具有良好的实用价值，模型的预测精度明显优于传统灰色GM（1，1）预测模型，从而有效地提高了预测结果的准确性，为准确预测网络性能提供一种科学有效的方法。