Web服务具有跨平台、异构、松散耦合等特点,逐渐发展成为互联网上一种重要的分布式计算模式。实际应用中,为满足用户复杂的需求,通常需要基于特定的业务流程模型,动态发现已存在的Web服务,并组装成一个更大粒度的服务,以实现完整的业务逻辑。在Web环境中,不同的服务提供方提供了大量功能相同或相似而QoS指标(如执行时间、价格等)不同的Web服务,如何能够动态地从中选择既满足功能需求,也满足用户全局QoS约束的服务进行组合已经成为一个亟待解决的问题。对于有QoS保障的服务选择问题已经有了很多研究成果^{[ 1, 2, 3]}。但是大部分工作都使用历史日志的期望来近似实际的QoS值,并将其作为确定值在UDDI上发布。虽然假设QoS是确定的数值可以简化计算工作,但在实际应用中却有很大的限制。例如,任何服务调用的响应时间都依赖于这样一个非确定性的因素,即同一时刻调用的任务数,显然,任务数越多,服务调用的响应时间就越长,同时,响应时间还会受到网络状态的影响。正是由于Web服务实际执行环境中的诸多不确定性因素共同影响着Web服务,从而导致其QoS不可避免地会产生变化。因此,在研究Web服务选择问题时,充分考虑QoS的不确定性有着重要的现实意义。

文献^{[ 4]}考虑到影响服务QoS度量的不确定因素,将Web服务的各项QoS指标定义为一系列随机变量,并利用随机变量的数学期望和方差来度量各属性,基于马尔科夫决策过程设计了随机QoS感知的可靠Web服务组合算法。文献^{[ 5]}提出了Web服务QoS的概率模型,将QoS指标建模为离散型随机变量,每个QoS指标的概率密度函数指明了QoS取某些特定值的概率,同时,给出了基于样本空间消减的QoS聚合算法,采用启发式贪心方法搜索组合方案。目前,就研究不确定问题而言,概率模型^{[ 6]}和模糊模型^{[ 7]}是处理该类问题的两种较为常用的模型,但无论是随机过程的分布函数,还是模糊数学的隶属函数往往都不易确定,因此有些学者试图使用非概率理论解决不确定问题,区间分析方法^{[ 8, 9, 10]}是近年得到较快发展的一种处理不确定问题的方法,它利用区间描述不确定性参数,符合人的思维习惯,表示形式简单,无需太多的先验知识,因此在不确定性建模方面具有较好的方便性和经济性。近年来,也有学者基于区间型的QoS讨论服务组合和选择问题。文献^{[ 11]}针对复杂多样的商业QoS建模需求,设计了支持数值型、不确定型(区间型、模糊型)数据的QoS模型,提出了基于模糊多属性决策理论的服务组合决策算法。

本文考虑到Web服务的QoS指标难以精确测量以及用户的QoS需求往往难以准确表达的问题,提出采用区间数形式对这些不确定信息进行建模,并在此基础上,引入用户满意度对组合服务进行综合评价,采用改进的粒子群算法寻找最优解,并通过实验验证了方法的可行性和有效性。

Web服务组合的过程从概念上可以分为四个阶段:定义、发现、选择和生成。定义阶段由业务专家对组合服务业务过程进行建模,业务过程模型中通常包含若干个任务节点(称为抽象服务);发现阶段按照组合服务中的各个任务的要求,查找和匹配合适的服务(称为具体服务),由于Internet上存在着大量功能相同或者近似的服务,因此对于同一个任务,往往可能发现多个服务,这些服务虽然在功能上是可替换的,但是通常具有不同的QoS水平,这些服务构成了每个抽象服务的候选服务集;选择阶段根据用户的QoS需求,为每个抽象服务从候选的服务集中选择合适的服务进行组合(如图1所示),该阶段是关系到整个Web服务组合是否能够成功的关键阶段,也是Web服务组合领域的一个研究重点;生成阶段的任务是在已选择的服务组件的基础上,自动生成带详细描述信息的服务组合方案。

图1

Fig.1

	Figure Option ViewDownloadNew Window
	图1 Web服务选择Fig.1 Web service selection

对于包含n个抽象服务的组合服务CWS={WS₁,WS₂,…,WS_n},每个抽象服务有一个由具体服务构成的候选服务集合WS_i={ws_i1,ws_i2,…,ws_im}。本文采用区间数形式定义服务的QoS指标,下面给出区间数的定义。

定义1 设R为实数域,称闭区间[x ^l,x ^u]为区间数,记作 ,其中x ^l,x ^u分别为区间数的下界和上界,x ^l,x ^u∈R,x ^l≤x ^u,特别地,当x ^l=x ^u时, 就退化为确定数。

Web服务的QoS模型见定义2。

定义2 一个Web服务ws的QoS模型形式化地定义为

式中4个元素分别表示服务价格、执行时间、服务可用性和执行的可靠性,各指标的意义详见文献^{[ 11]}。

定义2中,由于服务价格由服务提供者指定,通常是固定的,为了处理方便,本文将价格表示为上下界相等的特殊的区间数,而其他3项QoS指标的值在实际执行环境中是随机变化的,本文将这些随机变化的QoS指标表示为一个可动态自适应调整的区间。由于各QoS指标对应的随机变量所服从的分布未知,这里采用样本的性质对总体进行估计^{[ 4]},对服务ws的最近n次执行所得的某项QoS指标值的样本为:q₁,q₂,…,q_n,利用矩估计得到其数学期望和方差分别如公式(1)和(2)所示。

(1)

(2)

根据契比雪夫不等式,置信度为λ的某QoS指标的置信区间为, ],本文将该置信区间作为各随机QoS指标的估计区间。假设服务被调用,其某项QoS指标的实际执行结果不在估计区间范围内,则根据最近n次的执行结果重新估计E(Q)和D(Q),从而使服务ws的各项QoS指标值的区间能够随着执行环境各因素的变化而动态地自适应更新。

以上QoS指标中,服务可用性和执行的可靠性是效益型QoS指标,即指标值越高;质量越高,而服务价格和执行时间是成本型指标,即指标值越低,质量越高。

考虑到实际应用中用户的QoS需求难以准确表达的情况,本文将QoS需求也表示为区间数形式,定义如下。

定义3 用户对Web服务的QoS需求形式化地定义为

前4个元素依次代表用户对服务价格、执行时间、服务可用性和执行的可靠性的需求区间,后4个元素分别是以上各QoS指标的权重,代表了这些指标对用户的相对重要性,0≤ω_i≤1, 。以服务价格为例,价格区间[reqC ^l,reqC ^u]表示用户最高可承受数额为reqC ^u的费用,如果费用能够控制在reqC ^l或以下则满意,即reqC ^u是用户费用控制的最低要求,reqC ^l是用户费用控制的目标。

QoS感知的Web服务选择要求为每个任务节点选择一个合适的服务,形成一个可执行的组合服务能够在满足用户最低QoS需求的前提下,尽可能达到用户提出的QoS需求目标。

实验分为两个部分。第一部分,比较采用本文的自适应区间型QoS模型与采用确定值型QoS模型对Web服务组合成功率的影响,服务组合成功率指组合服务计划成功运行的数量占服务请求数量的百分比。第二部分,比较采用与未采用动态边界策略的PSO算法(称为SPSO算法)的性能。实验在含有6个任务节点的组合服务流程上进行,实验运行环境为Intel Pentium双核(2.2GHz)处理器,2 G内存,采用Matlab7.4.0编写仿真程序。

首先,通过实验对基于自适应区间型与确定值型QoS模型的服务组合的成功率进行比较,其中,确定值型的QoS取历史日志的期望。实验为每个任务节点随机生成10~60个候选服务,各候选服务的执行时间、可用性和执行的可靠性参数在给定的范围内随机波动。实验中,置信度λ取0.05,公式(3)~(6)中的δ取0.01,各QoS指标的权重均取0.25。对每个任务节点的候选服务数从10递增到60的情况分别进行了实验,每种情况下的组合成功率取运行100次的平均值,实验结果如图2所示。

图2

Fig.2

	Figure Option ViewDownloadNew Window
	图2 组合成功率的比较Fig.2 Comparison of composition success rates

从图2可见,对于不同规模的候选服务,基于自适应区间型QoS模型的组合成功率明显高于确定值型的。这是由于本文的QoS指标度量采用了自适应、动态调整的策略,使QoS接近真实情况,区间的采用也使得服务选择可以基于模糊的方式进行,从而在一定程度上提高了组合成功率。

第二部分实验旨在比较DBPSO和SPSO的性能。为便于比较,本部分实验首先采用穷举法找到全局极值f _{g_best},此外,为保证算法比较的客观性,实验让各算法从问题空间相同的位置出发寻找最优解。这里使用算法综合性能指标(Algorithm comprehensive performance index,ACPI)衡量算法的性能,ACPI的计算式如下:

(23)

式中:f _{g_avg}是算法重复执行n次的平均适应值,f₀是整个迭代过程中的最劣值,即迭代开始时全局最优值;(f _{g_avg}-f₀)/(f _{g_best}-f₀)用于衡量所得解的质量,该值越大表明所得的解越接近全局极值,算法的寻优能力越强;c _{g_best}是算法重复执行n次发现极值所用的总次数;t _{g_best}是算法重复执行n次发现极值所用的总迭代代数;u和v分别是c _{g_best}与t _{g_best}重要程度的影响因子,显然,算法发现最优解的次数越多,所用的迭代代数越少,则算法越优。

实验中,两种比较算法除了与动态边界策略相关的参数外,其他参数均取相同的值,采用的主要参数取值为:c_b=0.03,o_b=0.1,ε=1×10^-5,u=2.0,v=1.0,其中,c_b,o_b和ε的取值是通过在本实验开始前进行的参数取值实验中获得的最佳参数集中取得;u和v的取值表明实验更加关注算法的寻优能力;其他参数参见文献^{[ 20]}。实验中,种群规模为20,好邻居个数为3,最大进化代数为500。各算法的ACPI取实验运行150次的平均值,实验结果如图3所示。

图3

Fig.3

	Figure Option ViewDownloadNew Window
	图3 综合性能指标ACPI的比较Fig.3 Comparison of ACPI

从图3可见,在不同规模的解空间中,DBPSO总是能够获得比SPSO高的综合性能,平均ACPI较SPSO高14.44%。

图4所示为在每个任务节点有40个候选服务的情况下,粒子群适应值的进化收敛曲线。虽然DBPSO收敛代数略高于SPSO,但是相比于SPSO,DBPSO能够获得较高的收敛精度。

图4

Fig.4

	Figure Option ViewDownloadNew Window
	图4 适应值收敛曲线Fig.4 Convergence curve

提出了一种支持不确定信息的Web服务选择方法。该方法对Web服务的QoS模型进行了扩展,支持区间型不确定QoS指标的定义,采用自适应、动态调整策略对QoS指标区间进行度量;考虑到人类思维的模糊性,用户QoS需求也建模为区间数形式;在此基础上,提出基于用户满意度的组合方案评价方法;在PSO算法中引入动态边界调整策略,采取改进的粒子群算法寻找最优组合方案。仿真实验从组合成功率和服务选择算法综合性能两个方面验证了本文所提方法的有效性和可行性。