张鹏程, 王丽艳, 吉顺慧, 李雯睿

1(河海大学 计算机与信息学院,江苏 南京 211100)

2(南京晓庄学院 信息工程学院,江苏 南京 211171)

随着Web服务技术的快速发展和应用,网络上出现很多功能相似的Web服务,在选择满足用户需求的Web服务过程中,非功能性需求往往被人们忽视[1].近几年来,作为非功能性因素的QoS逐步被人们重视[2].Web服务由Internet网络提供,因为网络环境等因素的变化而受到影响,因此,真实网络的QoS具有非线性、动态多变的特点,选择服务前提供有效的服务QoS信息显得格外重要[3,4].

目前,越来越多的研究人员开始致力于Web服务QoS预测技术,在服务功能满足用户需求的情况下,为用户选择服务或避免服务故障提供了技术支持.现有的预测模型根据预测技术可以分为基于结构方程(structural equation)的QoS预测方法[5,6]、基于相似度的QoS预测方法[7,8]、基于人工智能的QoS预测方法[9,10]和基于时间序列的QoS预测方法[11]等.

(1) 基于结构方程的QoS预测方法根据QoS的过去值分析当前值变化趋势,该方法可以分析属性的内部关系,但不能预测具体值[5].Le等人[6]根据单个属性历史信息的趋势,提出了一种 QoS定量预测法,但只能预测属性的变化情况,预测值不准确;

(2) 基于相似度的QoS预测方法是利用使用过该Web服务的用户的QoS,根据相似度预测其他未使用者或该用户使用的其他服务的QoS[12].最早由Shao等人[7,8]提出,使用协同过滤法(collaborative filtering approach),根据用户相似度预测未使用过的服务QoS.该类方法具有预测模型简单、速度快的特点,但是只能用于单一功能且任务确定的Web服务;

(3) 基于人工智能的 QoS预测方法具有很强的自适应能力和实时预测能力[9,10],能够预测复杂的非线性的QoS属性值.Liu等人[13]提出一种基于BP(back-propagation)神经网络的Web服务QoS预测方法,在训练速度、预测精度方面并不完善,大多数模型都存在训练速度慢、时效性差等缺点,并没有很好地发挥智能方法的优点.Fan等人[10]提出了一种基于遗传编程(genetic programming,简称 GP)的 QoS属性预测方法,动态预测QoS属性值,预测精度较好,但是预测步长短;

(4) 基于时间序列的QoS预测方法主要利用QoS属性的时间维序列构建模型,随时间变化预测未来QoS的属性值.该类方法最早用于经济、金融等领域[14],主要基于ARIMA(autoregressive integrated moving average)等模型[15],因为时间序列方法具有精确度相对较高、时效性强的优点,后来逐渐扩展到其他领域,但仍然存在预测周期短、随周期变长误差逐渐变大的缺点.Ye等人[16]提出了一种基于多元时间序列的QoS长期预测方法,构建了属性关系式,基于ARIMA和Holt-Winters建立长期预测模型,该方法只适用于静态预测,动态性较差.

根据上述分析,当前Web服务QoS预测方法存在问题归纳如下.QoS属性间的相互影响考虑不充分.QoS属性主要包括响应时间、吞吐量、可靠性、可用性、价格等[17].它们之间存在错综复杂的关系.例如：当响应时间变大时吞吐量变小,可扩展性对可靠性也产生影响,属性间的关系无法用准确的公式模型表示[6],自行构建的关系式往往随着数据样本的改变而发生变动,大部分只针对目标属性的历史数据预测未来值,存在 QoS属性信息不足的缺点,影响预测周期和准确性;预测步长较小,多步预测效果不好.Web服务QoS的整体发展趋势随服务提供商的策略变化具有动态多变的特性,直接利用目标属性的历史数据做多步直接预测不能保证预测的精确度.对于企业或用户长期使用的 Web服务,需要多步长预测未来 Web服务质量,因此,多步预测具有重要的研究意义;动态性差.Web服务 QoS属性值具有动态多变的特点,目前,大多数模型根据历史数据建立固定模型,没有考虑随数据的更新、动态改变模型参量,在实际预测中缺乏实用性.

为解决上述问题,本文提出一种新颖的基于多元时间序列的 Web服务 QoS预测方法,简称 MulA-LMRBF(multiple step forecasting with advertisement-levenberg marquardt radial basis function).一方面,对于用户长期使用的 Web服务,从长远角度预测服务质量;另一方面,单元时间序列包含的非线性系统信息较少,适合短期单步预测稳定且功能简单的服务.多元时间序列中包含较多的QoS信息,相空间(phase space)重构后比单元时间序列包含更多的系统动态信息,因此采用多元时间序列实现QoS动态多步预测.总体来说,本文贡献主要包括如下4个方面.

(1) 针对问题1),考虑QoS属性间存在复杂的联系,采用相空间重构方法,将时间序列上每个QoS属性历史数据映射到一个动力系统中,近似恢复序列原来的多维非线性系统.重构后的时间序列包含更多QoS属性动态信息,属性之间的关联可以通过非线性系统描述,使预测更具动态性和准确性;

(2) 针对问题2),因为短期 QoS广告数据(advertisement data)是根据服务未来的趋势发布,代表当前 QoS属性值的走向.将模拟生成的短期服务提供商的QoS广告数据加入到预测数据集中,辅助实现多步预测,提高预测精度;

(3) 针对问题3),利用LM算法改进的RBF神经网络模型(LMRBF)[18,19]实现动态预测,该模型以黑盒模式描述输入变量与预测变量之间的复杂关系,利用LM最优化算法训练权值,提高运算效率,但是迭代训练权值的运算不够优化.本文进一步优化LMRBF方法,减小了时间开销和空间开销,相对准确地预测属性值.针对QoS动态多变的特点,每采集一新样本动态更新神经网络的参数值,实现动态预测;

(4) 在提出方法的基础上,利用开源数据集和自测数据实现相关实验.实验验证了相空间重构和广告数据对预测的影响以及 MulA-LMRBF方法在多步动态预测中的有效性,与其他方法比较,在预测准确度方面有明显提高.

本文第1节介绍方法运用的背景知识和相关的理论基础.第2节介绍本文提出的预测方法MulA-LMRBF.第3节给出实验设计和结果分析.第4节对本文工作加以总结和展望.

1 预备知识

1.1 相空间重构

非线性时间序列可以看做由确定的非线性系统产生的,相空间是描述系统运动和演变最有力的工具之一,可以表示动力系统中所有可能的状态,其中每个状态具有对应的相位空间点,从而刻画了一个点随时间变化的情况.目前,很多研究人员选择相空间重构(phase-space reconstruction)处理非线性时间序列,近似恢复序列构成的动力系统.相空间重构最早是由Takens[20]提出,相空间重构定理认为：系统中任意变量的发展都是由与之相互作用的其他变量决定的,相关变量的信息隐含在其他变量的发展过程中,当选择的嵌入维恰当时就可以重构序列的原系统[18,21].

样本个数为N,属性个数为M的多元时间序列表示为X={X1,X2,…,Xi,…,XN},其中,i∈{1,2,…,N}.多元时间序列X的每个数据样本代表每个时间点的值,表示为Xi=[xi,1,xi,2,…,xi,j,…,xi,M],其中,j∈{1,2,…,M},j表示第j个属性,Xi表示第i个时间点的样本数据,xi,j表示第i个时间点第j个属性的值.

其中,mj表示第j个属性的嵌入维数,τj表示第j个属性的延迟时间.

1.1.1 平均位移法

平均位移法[22]是同时考虑嵌入维数和延迟时间的相空间重构方法,思想是：通过引入平均位移(AD),给每个属性一个假设嵌入维数m,求延迟时间τ.平均位移的求解公式为

即：随机给某一属性赋值嵌入维数m,求对应的〈Sm(τj)〉.原始的平均位移法原则是：当〈Sm(τj)〉的增长斜率第 1次降为初始值的 40%时,对应的点为所求的延迟时间.本文采用前人改进的平均位移法[23],即：随着τj值增加,〈Sm(τj)〉的第 1个峰值点对应的τj就是所求的延迟时间.

1.2 LM算法

列文伯格-马夸尔特法(Levenberg-Marquardt,简称 LM)[24]是一种使用广泛的最优化方法,是牛顿法(Newton's method)和梯度下降法(gradient descent)的折中,通过迭代调整未知变量,求解二阶函数f(W)的最优值,具有收敛速度快的优点.

令W为L个变量组成的向量,W=[w1,w2,…,wi,…,wL].求解最优值的过程中,作用于向量W的最优调整量ΔW的计算公式为ΔW=(H+λI)-1g,其中,H为多元函数f(W)二阶偏导构成的Hessian矩阵,可以表示为

I为与H同维的单位矩阵,λ为正则系数,g为函数的梯度向量.为了化简由Hessian矩阵计算带来的复杂性,采用近似二阶偏导,忽略二阶以上的导数项代替二阶偏导[25].假设二阶函数f(W)的优化由如下代价函数产生：

dt表示真实值,g(Xt,W)是dt的逼近函数,那么f(W)的近似二阶偏导数项可以表示为

其中,i∈{1,2,…,L},j∈{1,2,…,L},N是训练样本个数.在迭代训练的过程中,除了每次计算权值调整量ΔW以外,也为正则系数λ分配足够大的值,保证H+λI正定,尽快收敛到最优解[25].

1.3 RBF神经网络

RBF神经网络由Moody和Darken根据人体大脑皮层的感知区域特点提出的一种前馈型神经网络,网络结构如图1所示,通常包括输入层、隐含层和输出层[26].其中,第1层输入层由感知神经元组成,将输入向量X引入神经网络,其中,X=[X1,X2,…,Xi,…,Xn],n表示输入层神经元个数;第2层隐含层把输入向量从低维映射到高维,实现高维曲线拟合,通常隐含层激励函数选择径向基函数φ(X);最后一层是输出层,将隐含层的输出进行线性加权组合作为最终输出值,记为Y.

当输入样本为n时,输入层节点数为n(n⊆N*),隐层节点个数为L,采用单输出,即输出层节点个数为1.

2 一种基于多元时间序列的Web Service QoS预测方法

本文从多元时间序列的角度分析QoS数据,提出一种动态Web服务QoS预测方法MulA-LMRBF,着重于多属性的数据分析和神经网络模型的改进,流程描述如图2所示.

用户或企业需要长期使用的Web服务可能由于动态的Internet网络变化产生短期或周期性的QoS变化,甚至发生服务故障,需要从长远角度预测服务的 QoS,为用户选择 Web服务提供真实可靠的服务质量数据.MulA-LMRBF方法充分利用QoS属性的历史数据信息并动态预测未来属性的具体值,主要概括为3个步骤.

· QoS data collection and processing：确定QoS属性个数,选择QoS属性完备的样本作为实验数据.收集的数据包括历史数据和短期广告数据,分别对两部分数据进行预处理,历史数据处理包括数据噪声处理、尺度变换和相空间重构,广告数据仅尺度变换,从而形成综合的QoS数据序列;

· Model training：设定隐层节点个数等初始化参数,通过最优化训练样本的误差函数f(W),采用改进方法训练神经网络隐含层和输出层间的权值W,进一步优化W的更新计算过程,达到高效训练的效果;

· QoS dynamic forecasting：当训练样本满足误差函数f(W)的阈值要求时训练结束,获取下一条新样本,对其预处理并保存预测结果.为实现动态预测,计算其εk和βk,调整一次权值W.

2.1 数据收集和预处理

数据主要来自公开数据集和自测数据[16,27],分别对历史数据和广告数据两部分进行预处理,具体由以下步骤组成.

(1) 历史数据(QoS history data)噪声处理

QoS历史数据含有大量噪声,噪声会随时间演化和后续计算造成精度损失,并且相空间重构时间序列模型对数据噪声很敏感,含噪声数据会严重影响预测准确度,因此采用非线性小波变换阈值去噪法(nolinear wavelet transform threshold denoising approach)[28-30]处理QoS历史数据.

(2) 数据尺度变换(scale transformation)

神经网络输入变量在[0,1]或[-1,1]时,网络运算效果较好[9],因此对数据进行尺度变换处理,将 QoS属性历史数据和QoS广告数据都控制在[0,1]之间.尺度变换公式为

其中,i∈{1,2,…,N},j∈{1,2,…,M},x·,j是 QoS 第j个属性的所有值,(x·,j)max是x·,j的最大值,(x·,j)min是x·,j的最小值.

(3) 历史数据相空间重构模型(phase-space reconstruction)

QoS历史数据相空间重构,首先采用平均位移法确定重构的嵌入维数m和延迟时间τ,m从[1,30]取值,用公式(1)计算每个QoS属性的m对应的〈Sm(τj)〉,取〈Sm(τj)〉到达第1个峰值对应的τ.然后均衡多个属性的m对应的τ值,选择所有属性的m对应τ达到平稳状态区间之内的值作为相空间重构的嵌入维数和延迟时间.

其中,i∈{1,2,…,N},相空间重构时选择的数据样本个数为N,属性个数为M,分别为每个属性计算合适的m和τ.例如,假设某一Web服务的响应时间(response time,简称RT)的嵌入维数为2,延迟时间为1,可靠性(reliability,简称R)的嵌入维数为2,延迟时间为2,在t时刻去噪和尺度变换后的数据Qt为Qt=[RTt,Rt],Qt相空间重构后为[RTt,RTt-1,RTt-2,Rt,Rt-2,Rt-4].重构后的Qt′充分利用历史数据样本,近似恢复RT和R属性共同的原数据关系系统,比原数据Qt包含更多QoS属性的动态信息,因此我们将相空间重构后的历史数据用于QoS的动态多步预测.

Qt′=

(4) QoS综合数据序列(QoS integrated data serirs)

2.2 LM算法改进的RBF神经网络预测模型

LM算法改进的RBF神经网络主要利用LM算法的最优化思想,训练网络隐含层与输出层权值W.QoS综合数据序列的数据作为输入,隐含层节点个数固定不变,输出层节点个数为 1,因此隐含层与输出层权值最优时,网络的实际输出值与真实值最接近.我们利用 LMRBF网络的优点并进一步改进,实现高效训练和动态预测的目标,提高预测精度.

RBF神经网络模型[31]的输入为Xi,输出为Yi,隐含层激励函数选择高斯函数,其公式为

其中,i∈{1,2,…,N},N表示样本个数,k∈{1,2,…,L},L表示隐含层节点数,φ(r)为隐含层激励函数;Ck为RBF神经网络隐含层中心,σk为第k个隐层节点的扩展常数,其求解公式为

dk是第k个隐层节点与其他隐层节点的最小距离,k和t∈{1,2,…,L},t∈{1,2,…,L},λ是重叠系数,σk是第k个隐层节点的扩展常数.RBF神经网络输出层公式为

其中,i∈{1,2,…,N},W是隐含层与输出层的权值向量,W=[w1,w2,...,wL]T,Yi为输出层函数,wk为第k个隐层节点与输出节点之间的权值.

(1) 模型训练阶段(model training)

模型训练的目的是满足误差函数f(W)尽可能小,直到预测精度满足阈值条件.当不满足阈值条件时,迭代更新W的值,使得f(W)达到阈值δ的要求.即f(W)＞δ时,更新权值W.误差函数f(W)的计算公式为

其中,Ti表示样本真实值,Yi表示RBF神经网络的实际输出值,si表示第i个样本的预测误差,则N个训练样本的预测值与真实值的误差矩阵S=[s1,s2,…,si,…,sN].

利用LM算法训练RBF权值W的过程,见算法1,训练样本训练时,W迭代更新的公式为

即：通过每次迭代调整神经网络权值,使网络输出值最大程度接近数据真实值.公式(13)中,权值W的调整量ΔW利用近似二阶导数JTJ代替原来复杂的Hessian矩阵计算,f(W)的Jacobian矩阵J为

正则化系数μ的取值在LM算法优化未知参量的过程中起决定性的作用,第n次迭代训练,如果f(W)值大于第n-1 次迭代f(W)的值,参数值μ=μ×a(μ＞0,a＞1);否则μ=μ/a,并更新权值W.

虽然采用 LM 算法改进 RBF神经网络训练权值可以快速地收敛到最优解,分析迭代更新公式(12)～公式(14)可知：计算权值调整量ΔW需要耗费复杂的开销,矩阵J需要存储所有训练样本的神经网络输出函数,进而才能计算JTJ和JTS,因此,优化网络训练的主要工作集中到Jacobian矩阵的存储以及与它相关的矩阵计算.Wang等人采用LM算法改进ELM神经网络[18],通过公式改进,进一步优化了预测模型.本文启发性地从Jacobian矩阵和相关矩阵计算等方面优化MulA-LMRBF动态预测模型：

矩阵J是由全部训练样本输出函数相关的偏导项构成的,因此需要所有训练样本经过一次模型计算才可以进行权值调整.我们将预处理后的N个训练样本分为db(data block,db≥1)长度的若干段,当样本量达到db时,计算一次误差函数f(W)的值并判断f(W)的阈值条件：满足条件,则代表本段样本训练结束;否则继续迭代,直到f(W)≤δ.训练阶段重复执行上述步骤,每次判断新db个样本的f(W)是否满足阈值条件,直到全部训练样本训练结束.

权值调整量过程中,计算JTJ的时间复杂度为O(n3),JTS的时间复杂度为O(n2),空间复杂度为O(n2).进一步简化计算,Jacobian矩阵中的偏导项∂(si)/∂wj进一步化简为

因此,矩阵J可以化简为Γ的形式：

可以看出,Γ是由神经网络隐含层的输出函数构成,每行代表一条样本经过网络模型的隐含层输出.

采用化简矩阵Γ计算权值调整量ΔW,根据Γ矩阵的特点,依次化简JTJ和JTS的计算.

a) 首先优化计算JTJ,可以用如下公式表示：

b) 然后类比上述优化JTS的计算：

其中,εk是第k个样本对应的隐含层输出向量,sk表示第k个样本的预测误差.

算法1. LM算法改进的RBF神经网络.

初始化：f(W)=0,εk=0,βk=0;db,L,μ,向量W,S随机赋值;

输出：更新后的权值W.

1.f(W1)=f(W); //f(W1) isf(W) in the last iteration

2. Calculateεkandβk;

3.Whencount=dbdo

4. Calculatef(W),W;

5.whilef(W)＞δdo

6.f(W2)=f(W); //f(W2) isf(W) in the this iteration

7. CalculateΔW;

8.iff(W2)＞f(W1)

9.μ=a*μ; //μis the regularization coefficient

10.else

11.μ=μ/a;

12. UpdateW,W=W+ΔW;

13. Calculatef(W);

14.end while

(2) 动态预测(QoS dynamic forecasting)

本文采用LM算法改进RBF神经网络训练权值W,在时间复杂度、权值调整量计算等方面有明显改进.模型动态预测阶段,延续训练阶段采用改进算法训练权值的思想,输入新数据动态更新权值W.每次权值调整过程中,正则化系数μ不断调整的作用在于：当μ趋近于0时,方法近似于训练速度快的高斯牛顿法,权值调整量ΔW调整地缓慢;当μ取值很大时,方法近似于梯度下降法,ΔW调整幅度大,每迭代成功一步,μ值减小并逐步回归到高斯牛顿法.

为了使模型动态长期地预测 QoS属性值,训练样本达到数量要求,训练结束后,当采集到一条在线数据时,首先进行Step 1的步骤处理,形成QoS综合数据序列;经过Step 3调整模型输出值作为预测结果;为实现模型参数更新,将新数据组成样本对,转向Step 2,计算该样本的εk和βk,计算最新的db个样本的误差函数f(W),判断阈值条件,当不满足时,根据误差函数f(W)的增减情况调整参数μ以及权值W.随着在线数据的实时采集,模型参数不断更新,适应动态、非线性的QoS预测要求,从而提高了预测的准确性.

3 实 验

3.1 实验设置

本文实验数据主要有5个部分：第1部分(Sourceforge)(https：//sourceforge.net/projects/qosmonitoring/files/)、第 2 部分(http：//www.datatang.com/data/15932)和第 3 部分数据(http：//www.datatang.com/data/15938)来源于开源数据集,第 4部分是笔者采用公开方法(https：//www.ibm.com/developerworks/library/ws-quality/)收集的数据,第五部分是短期QoS广告数据.上述数据集,除第3部分采用响应时间(response time,简称RT)、吞吐量(throughput,简称 T)、可靠性(reliability,简称 R)和可用性(availability,简称 A)这 4个属性,其他数据集主要包含响应时间和吞吐量这两个 QoS属性,利用多属性数据预测未来响应时间.实验环境为 Intel(R) Core(TM) i5-4200U CPU@1.60GHz,4.00GB RAM,Windows 7,matlab 7.11.

其中第1部分数据的采集时间是每天8：00～17：00,连续每15分钟记录一次Web服务的响应时间和吞吐量,共4个Web服务,取每个Web的连续2 000条数据实验.以其中一个服务RMB Instant Quotation为例分析实验过程和结果,如图3(a)所示,为RMB数据的曲线图.第2部分主要来自142台分布式计算机的4 532个真实Web服务的QoS数据,选择部分Web服务的数据实验.第3部分是来自150台分布式计算机,100个Web服务的监控采集结果,除响应时间和数据量等信息外,还包括服务的HTTP信息,反映服务当前可用情况,本实验根据HTTP信息、访问服务失败次数和服务失效时间,模拟QoS可靠性和可用性.第4部分为作者采集的数据,选择多个的Web服务ID,每个服务采集时间间隔为10分钟,每个ID记录了2 000多个样本,选择MobileCode为例进行实验,原数据如图3(b)所示.由于本文选择的Web服务QoS属性数据大部分都是早期采集的,未提供广告数据,所以第五部分数据主要通过模拟生成QoS的响应时间广告数据,根据QoS属性呈现非线性、动态的特点以及Web服务呈现的间断性优化的趋势,在原数据的曲线图上,以一天为周期添加若干趋势线,与真实数据的拟合度控制在50%～70%.

实验通过均方根误差(the root mean square error,简称RMSE)分析实验,更直观地比较不同方法的预测结果：

其中,Yi为第i个预测值,Ti为第i个真实值,N为样本数量.RMSE表示预测相对误差的大小,反映预测的稳定性.

3.2 实验过程

希望通过实验证明使用相空间方法构建属性关系、采用广告数据提高了多步预测的准确度,验证 QoS多元时间序列适合多步、中长期动态预测,通过对比实验阐明该预测模型的准确性.

从数据集中选择若干Web数据实验后,本文分别介绍基于单元时间序列LMRBF预测方法(S-LMRBF)、基于多元时间序列相空间重构的LMRBF预测方法(Mul-LMRBF)、基于多元时间序列相空间重构和带广告数据的LMRBF预测方法(MulA-LMRBF)这3组实验,通过对比观察相空间重构和广告数据对多元多步预测的影响,验证多元时间序列在多步、中长期动态预测时,比单元时间序列预测精度高.与传统静态RBF神经网络预测方法[26,31]和ARMA预测方法[32]比较,证明本方法在精确度、动态多步预测方面的优势.简单步骤描述如下.

(1) 将QoS历史数据的多元时间序列进行处理,减少噪声并变换数据尺度,数据处理后扰动性减小.如图4所示,为RMB和MobileCode处理后的结果;

(2) 对预处理数据进行相空间重构,利用平均位移法同时考虑m和τ,计算m在[1,40]范围内的每个m对应的τ,如图5(a)和图5(b)所示：随着m的增加,重构相空间满足的τ整体呈减小趋势.如图5(a),RMB数据的m为[1,3]时,τ的波动较大,重构的相空间处于不稳定状态;当m＞10时,一方面相空间重构耗费样本量过多,约耗费40%～50%的样本,另一方面,不同属性的m-τ图的值不稳定,因此RMB数据从[4,8]范围内选择嵌入维数.

(3) 选择步长η(η≥1),则样本表示为{Xi,Ti+η},i∈{1,2,…,N},建立预测模型进行模型训练,当达到训练样本数量时,动态预测未来属性值.当数据采集及时的情况下,本方法支持Web服务QoS动态在线预测,若数据采集频度很低或出现大比例缺失数据,动态预测无法正常进行.另外,本方法现在仅限于一定阈值范围内的多步预测,当η超过范围时,不能达到预测精度要求;同时,当η很短时,数据进行相空间重构的优势不明显.因此,实验总结平均最佳多元时间序列预测步长的适用范围为[2,8].

3.3 实验结果分析

3.3.1 相空间重构和广告数据对预测影响

为证明相空间重构对动态多步预测的影响以及广告数据对预测精度的影响,通过若干组实验分析验证.以RBM数据为例,取1 000组训练样本,300个测试样本,m在[3,8]范围取值,分别做单步和多步预测实验.如图6所示,截取不同相空间重构下单步预测结果和RMSE的对比,实验的RMSE采用归一化数据计算.

图6(a)为单步预测结果,可以看出S-LMRBF预测结果拟合度较高,说明QoS单元时间序列的信息可以实现单步预测.图6(b)为单步预测的RMSE,m在[3,17]范围内的取值分别代表不同m对应的相空间重构情况.从图中可以看出：单步预测时,Mul-LMRBF的误差值略大于S-LMRBF,MulA-LMRBF比Mul-LMRBF的预测误差值小,大于S-LMRBF预测误差.说明当预测步长较短时,相空间重构和广告数据对预测准确性影响不大.

如图7所示为不同相空间重构条件下,多步预测的对比实验结果.m=4,6,8分别进行步长为 3和 5的预测,从 6个对比结果中看出：步长增加,预测误差都会增加,但多元 MulA-LMRBF和 Mul-LMRBF预测结果比单元S-LMRBF预测结果的拟合好.取不同相空间重构参数值,预测结果也不同,当重构维数m取值在m-τ曲线稳定的范围内时,预测结果具有较高拟合度.因此,相空间重构参数要综合考虑m和τ两个参数,取参数值共同稳定的范围.MulA-LMRBF的拟合结果优于Mul-LMRBF,广告数据进一步提高了预测精度,因此,采用服务提供商提供的相对真实可靠的广告数据进行QoS多步预测会进一步提高预测精度.

3.3.2 多元对预测步长的影响

通过相空间重构和广告数据的实验,充分证明恰当的相空间和广告数据能提高多步预测精度.以相空间重构m在[3,10]范围内的值为例,通过实验调整步长,观察随步长增加单元(S-LMRBF)、无广告多元(Mul-LMRBF)、带广告多元(MulA-LMRBF)这3种预测的均方根误差RMSE变化情况.从数据集中选择若干个完整的Web服务QoS数据分别进行对比实验,实验证明：多步预测时,MulA-LMRBF的RMSE值最小,Mul-LMRBF和MulALMRBF多步预测的RMSE普遍优于S-LMRBF单元预测结果.

图8是RMB数据300个测试样本的多步预测RMSE示例.当Step＜3时,S-LMRBF的RMSE值明显低于Mul-LMRBF和 MulA-LMRBF的值,说明小步长范围内,单元时间序列可实现较高精度预测.Step≥3,所有预测的MulA-LMRBF明显优于其他预测的RMSE,其中,m=4时,Mul-LMRBF优于S-LMRBF;m=6时,Step在[3,9]及大于10范围内Mul-LMRBF小于S-LMRBF的RMSE.因此,加入广告的MulA-LMRBF一直比未加入广告数据Mul-LMRBF预测结果的RMSE小.

如图9所示是自己采集的MobileCode数据预测RMSE对比图,选择m-τ曲线平稳范围内的相空间重构参数.以m=5为例,RMSE随步长变大呈增长趋势,当步长大于1时,Mul-LMRBF和MulA-LMRBF的预测RMSE总体上优于S-LMRBF,多元Mul-LMRBF在[2,5]步长范围内小于单元S-LMRBF的RMSE值.

从第2组数据堂数据中选择258组QoS数据完整的Web服务进行实验,统计m在[3,10]范围内不同步长取值的RMSE值.如图10为m=4时,258组实验的平均RMSE.

如图 10所示,当Step在[3,7]范围时,带广告的多元 MulA-LMRBF预测误差明显优于 Mul-LMRBF和S-LMRBF,与S-LMRBF相比,MulA-LMRBF的RMSE平均减小19%,多元Mul-LMRBF比S-LMRBF平均降低了16%.说明多元时间序列更适合多步长预测,可靠的广告数据会提高预测的准确度.根据实验统计,模型的平均最佳多步预测步长范围是[2,8].

3.3.3 对比实验

对比传统 RBF神经网络模型、ARMA模型和本文提出的 MulA-LMRBF预测模型,步长分别取 1,3和 5,分析预测值和实际值的拟合情况以及预测的均方根误差RMSE.

以RMB数据集为例,首先用S-LMRBF单步预测结果对比传统RBF神经网络、ARMA单元单步预测结果,如图11(a);然后,用m=6对应的Mul-LMRBF多步预测结果对比传统方法预测结果,如图11(b),多步预测的RBF和ARMA都采用响应时间和吞吐量两属性的历史数据.S-LMRBF和MulA-LMRBF分别对应不同步长预测值.

表1为RMB数据预测结果的RMSE,综合分析都优于RBF和ARMA的预测结果.表2为MobileCode数据300个样本点的对比实验RMSE统计值,步长分别取1,3,5,多元取m=6进行相空间重构.从表中可以看出：相比其他方法,MulA-LMRBF和S-LMRBF的RMSE值都比较小,具有更好的预测精度.

Table 1 Comparison of RMSE for RMB data forecasting results表1 RMB数据预测结果RMSE指标比较

Table 2 Comparison of RMSE for MobileCode data forecasting results表2 MobileCode数据预测结果RMSE指标比较

为进一步验证方法的通用性,将方法应用在数据集2收集到的258个完整的包含响应时间(response time,简称RT)和吞吐量(throughput,简称T)的Web服务数据,表3为预测结果的平均RMSE.通过对比实验,进一步证明了 MulA-LMRBF和 S-LMRBF的 RMSE值最小,特别是在多步长预测时,MulA-LMRBF要明显优于S-LMRBF.因此进一步证明了本文提出的MulA-LMRBF预测精度优于传统的RBF和ARMA方法,并且在动态和多步预测时,具有更好的预测效果.

Table 3 Comparison of RMSE for 258 Web services data average forecasting results表3 第2组Web预测平均RMSE指标比较

表4为第3部分数据集中ClientIP=128.83.122.179的平均RMSE结果,第3部分数据集采用4个QoS属性,比较平均RMSE可以看出当Step=3和5时,MulA-LMRBF的预测结果明显优于单元时间序列S-LMRBF.整体比较,本文改进算法MulA-LMRBF的预测RMSE比传统方法大约降低了50%,比S-LMRBF降低了20%左右.

Table 4 Comparison of RMSE for the third data set average forecasting results表4 数据堂数据集的平均RMSE指标比较

4 结论与未来工作

现有的Web服务QoS预测方法存在预测周期短、动态能力差、属性之间相互影响考虑不足等问题,针对上述问题,本文提出了一种基于多元时间序列的QoS预测方法 MulA-LMRBF.首先,该方法考虑多个QoS属性之间的关系,采用相空间重构描述并恢复各个属性值在时间变化中存在的非线性、动态系统,刻画属性间存在的关联;然后,利用服务广告数据近似表示属性值的未来趋势,将历史数据和广告数据共同组成预测的综合数据序列,实现多步长周期预测;为了改善原RBF神经网络模型训练计算过程并实现动态预测,最后采用LM算法优化RBF神经网络模型,随着在线样本采集,模型参数更新.

在未来的工作中,将重点考虑以下几个问题.一是现有的计算相空间重构嵌入维数和延迟时间的方法并不完善,目前运用的平均位移法可以提高预测的准确性,但参数未证实最优,相空间重构一直存在很大的研究挑战,参数值的选择一直是研究热点,后期进一步研究综合考虑嵌入维数和延迟时间的方法;二是本方法只选择网络权值为动态参数,动态性还不够完备,隐层节点个数等方面未考虑.本文从时间序列数据分析和预测方面研究QoS预测,现实网络中,需要Web服务数据实时收集、数据分析和处理、动态预测模型等更完备的系统支持,今后可更全面地研究;三是目前只考虑响应时间和吞吐量两个QoS属性预测响应时间,后期会进一步改进模型,可同时预测多个QoS属性值.