基于ARIMA和卡尔曼滤波的在线Web服务QoS预测方法

刘泽远， 杨孝宗， 舒燕君

(哈尔滨工业大学 计算机科学与技术学院， 哈尔滨 150001)

0 引 言

Web服务为面向服务的体系架构(Service-Oriented Architecture，SOA)提供了一个标准化的解决方案[1]，并在设计上成功解决了分布式计算基于标准、松耦合、协议无关的需求。随着Web服务的指数级增长，研究发现很多服务的服务质量良莠不齐，仅仅通过功能上的要求无法做出有效选择，因而需要通过服务质量(Quality of Service，QoS)的评估，来选择满足要求的Web服务。服务质量描述Web服务的非功能方面的特性，主要包括响应时间、吞吐量、故障间隔时间等指标。

在波动大、变化快的分布式Web服务环境中，Web服务的服务质量不会保持不变，而要保证Web服务满足使用者的要求，就要寻找一种有效的方法来判断Web服务在一定时间内能否满足服务质量的约束。针对这一问题，研究指出可以对QoS历史记录数据进行分析，用来预测Web服务在未来时间的QoS值。立足于这一研究角度，很多有关基于时间序列分析的Web服务QoS预测方法的研究已陆续涌现[2]，同时也证明了这一思路的设计可行性。

本文在已有研究基础上提出一种基于时间序列分析的Web服务QoS预测方法，结合了ARIMA(Auto-regressive Integrated Moving Average)与卡尔曼滤波(Kalman Filtering)技术，首先使用ARIMA模型对QoS历史记录值进行拟合，将ARIMA模型转换成状态空间模型，使用卡尔曼滤波器预测未来时间点的QoS值，在运行时每次测得的QoS值都可以对卡尔曼滤波器进行更新。该方法具有适应性高，计算复杂度低等特点，通过在公开的Web服务QoS记录数据集[2]上实施的实验可以验证该方法的准确性。

本文研究在论述上，首先探讨了该方向的相关研究工作,并分析了现有工作的优缺点；接下来给出了本文预测方法的理论基础与具体设计；然后，将该方法与经典的方法展开比较实验，并对实验结果进行分析；最后总结全文，进而展望未来的研究工作。

1 相关研究

在基于时间序列分析的Web服务的QoS预测中，目前已可见到一系列的研究工作和学术成果。Cavallo等人[2]比较了在时间序列模型中堪称代表的ARIMA模型与当前值方法、历史平均值方法以及线性回归法AR的仿真测试，结果表明ARIMA算法对异常值的容忍度较高，并且对QoS的违规有良好的预测效果，在预测结果上能够表现出相对较小的预测误差。Amin等人[3]提出结合ARIMA与广义自回归条件异方差(GARCH)模型，GARCH模型可以改善ARIMA模型中方差恒定假设的不足，更加贴近真实的Web服务QoS数据特征。Ye等人[4]考虑QoS多个属性维度之间的相关性，提出使用多元ARIMA模型、Holters-Winters指数平滑模型，并在此后的研究中，将提出的方法同VAR(向量自回归)做了比较处理，其中包括了许多基于自回归的方法，诸如AR、SETAR(自激励门限回归模型)、ARIMA以及ARMA-GARCH模型。

可以发现，将单一的统计学模型进行组合是研究Web服务QoS预测的热门趋势，单一的模型已难以满足波动大并且没有统一规律的Web服务QoS预测。而随着近年来机器学习技术的迅猛发展，已经有一些研究者开始尝试将机器学习的方法应用到Web服务QoS的预测中。Zadeh等人[5]和Senivongse等人[6]即应用ANN(人工神经网络)解决Web服务QoS预测的问题，Yang等人[7]则提出使用遗传编程的方法。Wang等人[8]提出使用长短期记忆循环神经网络模型，预测Web服务系统的可靠性。综合分析上述研究结果可知，机器学习的方法并未能在预测准确率上达到质的提升，而这些方法在执行上的复杂却已经成为将其付诸现实应用的制约因素。

在使用ARIMA模型预测Web服务的QoS时间序列的研究中经过分析发现，单纯地使用ARIMA模型不能够适应Web服务QoS数据的波动频繁、包含噪声等复杂特点，为了获得更加准确的预测效果，本文使用卡尔曼滤波对ARIMA模型的结果进行修正。卡尔曼滤波是一种最优化自回归数据处理算法(Optimal Recursive Data Processing Algorithm)[9]，其最突出的优势即在于能够从一些包含噪声的观测量估计系统的状态。卡尔曼滤波利用前一时刻的估计值和当前时刻的观测值，更新当前时刻的状态向量，利用这一特点就可以很好地弥补单一ARIMA模型在QoS时间序列预测上的不足。下面首先详述ARIMA与卡尔曼滤波相结合的理论基础，然后阐述该方法的设计过程。

2 理论基础

ARIMA模型与卡尔曼滤波相结合的关键就是将ARIMA模型转换成状态空间模型，再使用卡尔曼滤波对状态进行预测与更新。一个ARIMA(p,d,q)模型经d阶差分就可得到ARMA(p,q)模型，数学公式可表述如下：

(1)

其中，Zt为t时刻观测值；at为t时刻预测值与观测值的误差；φi、θj为模型参数。设m=max{p,q}，令φi=0(i>p)，θj=0(j>q)，那么公式(1)也可以表示为：

(2)

设B为延迟算子，可将公式(2)变化为：

φ(B)Zt=θ(B)at

(3)

接下来，要将式(3)转换为Zt=ψ(B)at的形式，令ψ(B)=θ(B)/φ(B)，其中ψ(B)=(ψ0+ψ1B+…+ψmBm+…)，ψ0=1。根据延迟算子B的每一项系数相等，可以得出：

-θm=-φmΨ0-φm-1Ψ1-…-φ1Ψm-1+Ψm

(4)

化简公式(4)，就会得到ψm的数学运算公式可见如下：

(5)

由此，可以将Zt+m-i=ψ(B)at+m-i表达式展开为如下形式：

Zt+m-i=at+m-i+Ψ1at+m-1+Ψ2at+m-i-2+…

(6)

Zt+m-i|t=Ψm-iat+Ψm-i+1at-1+Ψm-i+2at-2+…

(7)

Zt+m-i|t-1=Ψm-i+1at-1+Ψm-i+2at-2+…

(8)

由公式(7)、(8)可得：

Zt+m-i|t=Zt+m-i|t-1+Ψm-iat

(9)

令状态向量St=(Zt|t-1,Zt+1|t-1,...,Zt+m-1|t-1)T，观测值Zt=Zt|t-1+at，观测方程即可表示为：

Zt=[1,0,…,0]St+at

(10)

根据公式(5)、(9)可推得状态转移方程为：

St+1=FSt+Gat

(11)

其中，F、G的运算可使用如下数学公式：

(12)

综上就是模型ARMA(p,q)转移到状态空间模型的推导过程，在得到状态空间模型后，就可转入卡尔曼滤波的应用设计的研究。

3 方法设计

如图 1所示，本文提出的Web服务QoS预测方法主要分为2个模块，分别是：ARIMA模型的确立和卡尔曼滤波器的更新。总地来说，根据QoS历史数据进行ARIMA建模，根据第2节的方法将其转换为状态空间模型，在运行时获得新的QoS观测值后，对状态向量进行更新，再将卡尔曼滤波的预测值作为最后的预测结果。对此内容，本节将给出阐释分述如下。

图1 预测方法概览

3.1 ARIMA模型建立

(1)白噪声检测。如果一个时间序列是纯随机的，此时就没有必要再利用ARIMA方法继续接下来的操作，因其并不适用于该方法。若一个时间序列纯由白噪声构成，那么在理论上其各阶自相关系数(Auto-Correlation Function，ACF)均为0，基于这一点即可判断时间序列是否为纯随机。

(2)稳定性检测。最简单的判断时间序列稳定性的方法就是通过肉眼观察样本的二维曲线图得出结论；当然也有其它的方法。理论上可证明平稳的时间序列通常会具有短期相关性，随着延迟增加，序列的自相关系数很快会降低至0，根据这一点就能判断时间序列的平稳性。如果序列非平稳，则引入逐次差分，直至得到平稳序列，即将ARIMA模型转化成ARMA模型。

(3)定阶。得到平稳的时间序列后，需进一步判断序列是否满足自回归(AR)、滑动平均(MA)。识别方法是序列的自相关系数(ACF)和偏自相关系数(Partial Auto-Correlation Function，PACF)。若ACF曲线衰减的同时、PACF曲线截断，则AR模型适用；若ACF曲线截断的同时、PACF曲线衰减，MA模型适用。根据ACF的拖尾特征、PACF的截尾特征，可以确定对应的阶数p、q。

(4)模型参数拟合与检验。模型的阶数确定后，模型参数个数也确定了。需要拟合出其它参数，即φi(i=1,2,...,p)、θj(j=1,2,...,q)，文献[10]给出使用极大似然估计法进行参数拟合的完整计算步骤。对于模型的检验环节，就需要检验模型是否具有统计意义，即检验是否对时间序列提取足够充分的信息。理论上推导可知，如果模型信息提取充分，残差序列即为白噪声。

3.2 卡尔曼滤波预测

卡尔曼滤波分为时间更新方程和状态更新方程。在Web服务的QoS预测中，结合ARMA(p,q)转化的状态空间方程，设St|t为时刻t基于先验信息得到的状态估计，卡尔曼滤波时间更新方程的公式表达详见如下：

St+1|t=FSt|t

(13)

Pt+1|t=FPt|tFT+GQGT

(14)

其中，Pt|t是时刻t预测误差的后验协方差矩阵；Pt+1|t是时刻t+1预测误差的先验协方差矩阵；Q为过程噪声的协方差矩阵。状态转移矩阵F将St|t转换为St+1|t，将Pt|t转换为Pt+1|t。t+1时刻QoS预测值根据状态向量St+1|t可由如下公式计算得出：

Zt+1|t=HSt+1|t

(15)

得到观测值Zt+1，可以对St+1|t+1、Pt+1|t+1做出更新，卡尔曼滤波的状态更新方程如式(16)所示：

St+1|t+1=St+1|t+Pt+1|tHT[HPt+1|tHT+R]-1(Zt+1-Zt+1|t)

(16)

Pt+1|t+1=Pt+1|t-Pt+1|tHT[HPt+1|tHT+R]-1HPt+1|t

(17)

其中，Pt+1|tHT[HPt+1|tHT+R]-1就是卡尔曼增益矩阵，通过最小化预测误差的后验协方差矩阵计算得出，计算结果决定了状态向量受到观测值的影响程度。

在实际操作中，输入初始状态S0|0和P0|0，然后计算Z1|0和V1|0。当得到观测值Z1后，使用更新方程计算S1|1和P1|1，将其作为下一次循环的初始状态。值得一提的是，输入任意的初始值S0|0和P0|0，初始值对后面预测值的影响会随着t的增加而变得越来越小，因为状态转移矩阵F的特征值均小于1，也就是说，随着t的增加，卡尔曼滤波器保证了初始值对后面结果的影响将逐步趋近于0。

4 实验

本节将验证研发提出的预测方法的实际效果。实验数据采用Cavallo公开发布的数据集[2]，选取了XML Daily Fact的服务，该数据记录了2006年7月～11月对该服务每隔1 h调用一次的QoS值记录，包括响应时间、可用性等。本次测试实验拟对实践中最常用的响应时间属性进行分析，选取了连续400个时刻的记录作为实验数据。为了削减异常值对模型的影响，对实验数据中高于3 000 ms的值(这些值相比样本个数非常少)设为正常数据的均值。

首先是使用单一的ARIMA模型的预测效果，绘制后即如图 2所示。

图2 ARIMA预测值与实际值

使用本文提出的预测方法，结合ARIMA模型与卡尔曼滤波的预测效果则如图 3所示。

图3 卡尔曼滤波预测值与实际值

从图2、图3中可以直观地看出，本文的预测方法的预测结果更加接近真实值，对波动情形的反应更为及时，在下一时刻就能做出调整与修正。为了更加客观地展现本文预测方法的准确率，对2种预测方法的预测结果与实际值的误差进行统计。本文计算了预测结果与实际值的均方根误差(Root Mean Squared Error，RMSE)，均方根误差的数学定义可表示如下：

(18)

基于单一的ARIMA模型预测结果,均方根误差为216.862 6;基于本文预测方法,预测结果的均方根误差为200.673 3，预测效果整体提升了7.47%。

5 结束语

准确地预测Web服务的QoS，能够为服务提供者有效地降低服务质量违规的风险，而且也能够帮助服务使用者在使用时间内调取到服务质量稳定的服务。故而，本文研发设计了一种基于时间序列分析的Web服务预测方法，并在公开的数据集上进行实验，验证了该方法的有效性。实验结果表明，相比传统的单一ARIMA模型预测方法，本文方法能够自适应地实现对QoS波动的预测，进而及时发出QoS违规的预警。

Web服务的QoS相对其它领域的时间序列有其本身的特点，由于业务复杂程度不一、网络环境波动大的影响，要更加准确地预测Web服务的QoS值就势必还有很多的工作需要成为当下的关键研究课题。后续工作将主要着重于如下方面：

(1)时间序列的噪声。噪声会对序列本身信息的挖掘产生影响，而去噪方法的选择也将涉及多方面的因素考证，因此为Web服务的QoS序列进行合理去噪，将会是未来的研究热点。

(2)QoS各属性的相关性。单变量的预测方法更加难以抵抗噪声对预测结果的影响，如何挖掘多个属性之间的相关性，提高预测准确率，则亟待后续的深入系统研究。