基于QoS的Web服务选择算法综述

1、收稿日期:2010-04-13;修回日期:2010-06-04基金项目:江西省自然科学基金资助项目(2009GQS0062作者简介:李金忠(1977-,男,江西吉安人,讲师,硕士,主要研究方向为服务计算、智能算法、网格计算等;夏洁武(1969-,女(通信作者,江西泰和人,教授,硕士,主要研究方向为计算机应用技术(xiajiewujgsueducn ;唐卫东(1974-,男,江西吉安人,副教授,博士,主要研究方向为虚拟现实、智能控制;曾劲涛(1978-,男,江西南丰人,讲师,硕士,主要研究方向为服务计算、网格工作流、软件测试;王翔(1979-,男,江西吉安人,讲师,硕士,主要研究方向为计算机应用

2、;吴兰英(1980-,女,江西永丰人,讲师,硕士,主要研究方向为智能优化基于QoS 的Web 服务选择算法综述*李金忠a ,夏洁武a |,唐卫东a ,曾劲涛a,王翔b ,吴兰英a (井冈山大学a电子与信息工程学院;b工学院,江西吉安343009摘要:服务选择算法是影响组合服务的QoS 和服务组合性能高低的关键因素。针对近几年来基于QoS 的Web 服务选择算法的发展状况进行了综述,介绍和总结了当前基于QoS 的Web 服务选择问题模型,对服务选择策略进行了分类,并对当前的一些典型的基于QoS 的Web 服务选择算法进行了系统的分析和评论。最后指出了现有算法中的不足之处,展望了该领域的进一步研究

3、方向。关键词:Web 服务;服务选择算法;服务质量中图分类号:TP393文献标志码:A文章编号:1001-3695(201010-3622-06doi :103969/jissn1001-3695201010005Survey on Web services selection algorithms based on QoSLI Jin-zhong a ,XIA Jie-wu a |,TANG Wei-dong a ,ZENG Jin-tao a ,WANG Xiang b ,WU Lan-ying a(aSchool of Electronic Information Engineering

4、 ,bSchool of Engineering ,Jinggangshan University ,Ji an Jiangxi 343009,China Abstract :The algorithm of services selection is a key factor which can affect the QoS of composite service and the perform-ance of services compositionThis paper reviewed Web services selection algorithms based on QoS in

5、this field in the recentyearsFirstly ,introduced and summarized the problem and model of Web services selection ,and assorted the strategies of ser-vices selectionThen systematically analyzed and discussed a number of classic and popular algorithms of Web services selec-tion based on QoSLastly ,poin

6、ted out several drawbacks of existing algorithms and proposed some research directions of this field for the futureKey words :Web services ;services selection algorithm ;quality of service (QoS 随着Web 服务技术的迅猛发展和广泛应用,网络上出现了大量具有不同QoS 参数(如执行时间、服务费用、可用性、可靠性、安全性、声誉等的候选服务,这些候选服务具有相同功能属性和不同非功能属性。如何高效动态地把现存的

7、各种Web 服务聚合起来以形成新的满足不同用户需求的增值的复杂服务,已成为新的应用需求和研究热点1,2。基于QoS 的Web 服务选择问题是服务组合中的一个关键问题。服务选择的结果不仅直接关系到服务能否成功组合,而且对组合服务的质量有着至关重要的影响1。1基于QoS 的Web 服务选择问题模型基于QoS 的Web 服务选择问题是指如何从服务组合各抽象服务的候选服务集中分别选出一个具体服务,使得选中的这组服务能在满足用户对组合服务的所有约束的前提下,使组合服务的整体QoS 最高。目前,国内外很多学者已经从不同的角度将该问题转换为某种已知的数学问题,在此基础上构造模型以设计相应的选择算法。所转换的

8、问题归纳如下:a 整数、线性规划问题3 5。整数规划问题的可行解区域为离散点,传统方法通常采用分支定界法或分解算法等进行求解,但这些求解算法是一种确定性算法,只能获得一个惟一最优解,对小规模服务组合求解效果较佳,而当服务组合的规模较大时,其计算量相当可观,计算时间将极大地增加,甚至无法求解问题,必须寻找更为有效的求解方法。线性规划法要求目标函数和约束条件是线性的,必须将非线性的QoS 属性和约束条件的计算公式进行转换,这在一定程度上限制了算法的实用性。将Web 服务选择问题转换为整数规划或线性规划问题只是为解决该问题找到了一个可计算的数学模型,但其计算复杂度依然很高,不能满足实时的性能要求。b

9、 多选择背包问题6 9。其求解的本质就是在满足一些QoS 约束的前提下,从候选服务集中发现一个能够使总的适应函数值最大的组合服务。多选择背包涉及的约束条件种类较多,在各种变形中最为复杂。由于求解复杂度与问题涉及变量数量呈指数关系,人们已发现传统确定性寻优算法(如分支定界法难以求解规模较大的背包问题,必须找寻一些智能优化算法求解。c 多属性决策问题10 12。由于组合服务中服务QoS 的复杂性和不确定性以及用户对QoS 属性的模糊性,一方面用户难以确切地给出QoS 属性的权重信息,也难以用确切的数值来表达;另一方面由于各不同QoS 属性之间的差异,其值难以规范到统一的度量空间而准确地评估出服务的

10、综合QoS 值。而服务选择的主要依据是服务的多维QoS 参数的质量,第27卷第10期2010年10月计算机应用研究Application Research of Computers Vol27No10Oct2010为此需采用多属性决策方法,探索新的可行的量化尺度来规范不同QoS属性值以对服务质量进行客观、准确的评估。d带QoS约束的单目标组合优化问题1,5,10,13 17。是假设多个QoS属性的权值已知的情况下实现的。然而在很多现实问题中很难通过简单的线性加权求和将多个QoS目标聚合转换为单目标,难以真正做到同时优化多个QoS参数目标,且产生的优化结果为满足约束条件的目标最优单解,用户没有选

11、择的余地。e带QoS约束的多目标组合优化问题2,18 22。无须设置各QoS参数的权值,不需要用户拥有过多的领域知识,对每个QoS参数分别设置相应的目标函数。多个目标函数被同时优化并产生一组约束条件的Pareto优化解,用户可依其偏好选择最满意的解。具有一定的“柔性”,能更好地满足用户的偏好和个性化需求,能更贴切地适应实际的Web服务选择场景。基于QoS的Web服务选择所构造的模型主要有有向无环图(DAG3,23 25和包含顺序、选择、循环、并行等控制结构的工作流3,14 17,26,27等。对于DAG模型所表达组合服务的结构清晰但较单调,如不能表达含有循环、选择等结构,适应于结构简单的应用场

12、景;而工作流模型含有丰富的结构集,能表达具有选择、循环等复杂结构的组合服务实例。2基于QoS的Web服务选择策略Web服务选取的目标是根据用户对服务质量的要求选取出一组服务,使得最终的组合服务具有良好的用户满意度和服务质量28。依据服务组合中所采取的服务选择策略的不同,可将现有的Web服务选择策略分为三种,即局部最优策略、全局最优策略及混合策略。2.1局部最优策略局部最优策略的基本思想是:分别考查各个抽象服务的候选服务集,对候选服务的各个QoS参数信息进行加权和排序,并以此为依据分别从每组功能等价的候选服务中为服务组合中的每一个抽象服务选择一个满足局部约束条件限制且加权和最大的服务来构建组合服

13、务。其核心是针对组合服务中的每个抽象服务,对能够完成该服务的所有候选Web服务进行选取,找到能够实现单个抽象服务的质量最优的服务。文献10提出了一个基于多维服务质量的局部最优服务选择模型,有效地缩小全局最优服务选择的求解空间。文献26提出面向分布式环境的迭代选择算法聚合局部最优服务以适应网络环境变化。由于该算法按照组合服务逻辑执行顺序迭代的选择服务,该算法可在组合服务执行之前或者组合服务运行时执行,无须作任何更改。文献29提出基于动态偏好的服务选择算法,针对每次服务配置的最大请求效用来确定权重,并结合声明式逻辑匹配来克服随机选择服务的不足。局部最优策略由于没有考虑全局QoS约束,也没有考虑组合

14、服务中各个抽象服务之间的关系,各个抽象服务选择具体服务是相互独立的,虽所选的单个服务能满足用户需求,但依此策略生成的组合服务并不一定是全局最优的,也不一定满足用户对服务组合的全局QoS约束。它保证了在单个抽象服务上的最优,但不一定能保证全局最优。局部最优策略的优点是通用、灵活;缺点是最终解是局部最优解,没有考虑全局约束,其质量很大程度上依赖于初始解的选择。2.2全局最优策略全局最优策略的选取方法将着眼点从单个抽象服务转移到了整个组合服务,从而使得选取出的服务更接近用户对组合服务质量的要求28。它旨在使得组合服务整体的QoS满足给定的约束或达到预定的优化目标,因此具体服务的选择需要综合考虑各个具

15、体服务的聚合效果。文献2给出了一种解决服务聚合中服务动态选择QoS 全局最优化问题的实现算法。将服务动态选择全局最优化问题转换为带QoS约束的多目标服务组合优化问题,利用多目标遗传算法的智能优化原理,通过同时优化多个目标函数,最终产生一组满足约束条件的优化服务聚合流程集。文献5, 27定义五维的服务质量模型,基于整数规划论提出满足全局最优的服务选择算法。文献8在综合考虑系统负载和代价的基础上定义效用函数,并采用动态规划和Pisinger算法来选择服务使得服务聚合的端对端响应时间的效用最大化。文献11提出了一种基于不确定多属性决策理论的全局优化决策算法以解决混合QoS模型感知的语义Web服务组合

16、问题。文献12提出了一种基于模糊多属性决策理论的语义Web服务组合的全局优化选择算法来综合评估候选执行计划的异构QoS,以供客户选择出全局最优的组合方案。全局最优策略考虑了全局QoS约束,所获得的解是满足QoS约束的全局最优解,但计算复杂,尤其在动态Web环境和实时需求场景下,需寻求高效率、高性能的Web服务选择算法支持。2.3混合策略局部优化策略计算量通常少于全局优化策略,但是无法考虑全局QoS约束,往往不能得到满足用户QoS需求的选择结果;而全局优化策略可以考虑全局QoS约束,但是计算量较大,组合规模增大时,全局优化策略的计算量也随之增大。因此这两种策略都存在一定的优势和局限性,很多服务选

17、择算法不能很好地兼顾局部与全局两方面的QoS要求。混合策略融合局部与全局策略的优点,如先采用局部最优策略对每个抽象服务过滤其候选服务,再由全局最优策略从未筛选掉的候选服务集中进行服务选择。文献10先采用局部优先选择算法对候选服务效用排序,然后采用全局优先服务选择算法快速构造服务聚合链,提高了构造服务聚合链的效率以适应网络环境的不确定性。文献30提出了一种基于QoS的两阶段Web服务选择方法,先对功能相同的Web服务进行QoS排序和单个Web的选择,筛选掉大量Web服务以降低全局算法的计算量;再采用Dijkstra 算法进行最短路径的Web服务选择以选择出最优的Web服务,克服了局部优化无法考虑

18、全局QoS约束的缺陷。文献31提出了一种融合全局优化和局部选择技术的混合方法以充分利用两者的优势。该方法首先使用混合整数规划(MIP找出将全局约束融入局部约束的最优分解方式,然后使用分布式局部选择找出满足局部约束的最佳Web服务。文献32提出了一种启发式算法来优化组合服务选择,以满足用户的QoS 期望。该优化是在全局和局部两层约束下进行的,每一层提出一个数学模型及其相应的使用“凸包前沿”方法和多属性决策·3263·第10期李金忠,等:基于QoS的Web服务选择算法综述技术的启发式算法来解决Web 服务选择问题。局部搜索技术可以确保满足基于组件服务层的QoS 需求,但处理全局

19、QoS 约束时失效。另一方面,全局优化技术可以处理全局QoS 约束,但性能不佳难以适用于具有动态和实时需求的应用33。采用混合策略,通常利用局部最优策略来缩小服务聚合的求解空间,利用全局最优策略来把握整体QoS ,它所产生的解是满足局部约束和全局约束的全局QoS 最优的解,但采用该策略所设计的服务选择算法思路复杂,设计时较有难度。3基于QoS 的Web 服务选择算法基于QoS 的Web 服务选择问题是一个组合优化问题,属于NP 难问题,传统典型的基于QoS 的Web 服务选择算法主要采用穷举算法和贪婪算法。由于求最优解的穷举算法复杂度太高和求局部最优解的贪婪算法所获得的解不一定是全局最优解,必

20、须寻求有效的近似解法以求近优解。当前较流行的基于QoS 的Web 服务选择算法主要是采用启发式算法设计的选择算法,如遗传算法(genetic algorithm ,GA 、粒子群优化(par-ticle swarm optimization ,PSO 算法、蚁群优化(ant colony optimi-zation ,ACO 算法及一些融合算法等。3.1穷举算法穷举算法的思想是将所有的服务组合方案一一列举,比较它们的QoS 等非功能属性值并从中找出一个满足用户需求的最优组合服务。采用穷举算法的组合优化方法的优点是简单、直观易懂,具有准确性和全面性,能够得出所有的解,但其缺点是计算量较大,可扩展

21、性差等。假设一个服务组合方案包含n 个抽象服务,而每个抽象服务有m 个候选服务,则总的候选执行方案有m n个,即该算法的时间复杂度为O (m n。因此可以看出,随着服务组合长度以及单个抽象服务的候选服务数的增加,候选执行路径的个数呈指数级爆炸性增长。该算法以时间和内存为代价来换取所有解,所以只适应对组合服务QoS 要求较高的小规模服务选择场景,当应用于对QoS 要求不高的大规模的服务组合时却无能为力,不能够很好地满足服务选择中的复杂要求。3.2贪婪算法贪婪算法的思想是逐步给出解的各个部分,对每一抽象服务贪婪地选择其所对应的候选服务集中QoS 最好的Web 服务,但不顾及这样选择对组合服务整体Q

22、oS 的影响。其前提是:以逐步的局部最优达到最终的全局最优。但对于服务组合问题,局部最优却不一定能产生全局最优,一般得到的并不是最好的解,所以该算法的适应场景有限。贪婪算法直观、算法的时间复杂度为O (mn ,远低于穷举算法。文献34指出贪心算法仅仅作局部搜索,在执行时间上是高效的,但该算法的一个主要缺点是它不能将服务执行计划作为一个整体来优化,且仅能确保单个服务能满足用户的约束条件,而不能保证整个执行计划都满足这些约束条件。文献35提出贪婪选择算法,选择具有最佳密度值的服务,该密度值代表了该服务的所有QoS 参数的总体质量,但该算法仍然难以满足组合服务的全局约束。3.3遗传算法GA 将问题的

23、求解过程表示为染色体的优胜劣汰的过程,通过种群的迭代进化,包括选择、交叉、变异等操作对种群进行组合产生下一代个体,逐步向优化的种群进化,最终求得最适应环境的染色体,也就是问题的最优解或者近似最优解。GA 本质上是一个通过群体的迭代来不断优化的过程。采用该算法解决基于QoS 的Web 服务选择问题,主要是要依据服务组合的具体情况确定染色体的表示方式、适应度函数的计算以及交叉和变异操作等。每个染色体表示为一个可能来自不同抽象服务所选的具体服务的组合方案,由若干基因位组成。每个基因位对应服务组合中的一个抽象服务,第i 个基因位的值是第i 个抽象服务所选具体服务在其对应的候选服务集中的编号。适应度函数

24、的确定根据各个具体服务的QoS 进行计算。交叉操作是对两个染色体(即两种不同的组合方案采用某种交叉方法交换这两个染色体中某些基因位的值,从而产生两个新的染色体。而变异操作是对染色体中基因的某一位以一定概率随机变化,即用另一个可利用的具体服务替代对应的具体服务。文献2给出了一种解决服务聚合中服务动态选择QoS 全局最优化问题的实现算法。将服务动态选择全局最优化问题转换为一个带QoS 约束的多目标服务组合优化问题,利用多目标遗传算法的智能优化原理,通过同时优化多个目标函数,最终产生一组满足约束条件的优化服务聚合流程集。文献4提出了一种快速稳定的基于遗传算法的多QoS 约束服务选择算法,该算法具有运

25、算速度较快、可满足实时性要求且在问题规模扩大时具有良好的可扩展性等特点。文献19提出了一种面向Pareto 最优遗传算法的服务组合方法,采用伪二叉树法则构造满足约束条件的Pareto 最优解集合,并通过对最优解集排序以及个体相似度的计算来获得遗传算法的适应度函数,最终产生一组满足约束条件的Pareto 最优解服务集合。文献22使用带精英策略的快速非支配排序遗传算法NSGA-设计Web 服务选择方法,可找出一个Pareto 优化解集,以供用户选择其最感兴趣的均衡解。文献14提出了基于遗传算法的动态的QoS 感知Web 服务选择方法。文献36提出了一种基于二叉树编码的遗传算法,用来解决SOA 服务

26、组合中服务选择问题。文献37采用关系矩阵编码方式,设计了一种用于QoS 感知的Web 服务选择的遗传算法。文献38提出了一种基于位置矩阵QoS 感知的Web 服务组合方法。该方法使用遗传算法用位置矩阵对基因进行编码,使得该编码方式可以表示服务组合的所有组合路径和重计划信息,算法的一次执行就能完成所有路径QoS 最优的全局搜索和动态重计划功能。文献39提出了一种在Web 服务组合中基于QoS 的改进型遗传算法。该算法通过计算个体间服务质量的海明距离来实现多样性保持,通过指定服务组合的总时间限制和优良解保留策略来处理算法本身的执行时间对服务组合质量的影响。文献40研究了一种基于树型二重结构编码的遗

27、传算法用于Web 服务选择。该方法分别采用树型结构携带语法业务流程信息和二重结构编码的方式处理用户QoS 约束条件,不仅能够有效地选择出较好满足用户各种约束条件的组合服务,而且把Web 服务语法业务流程与Web 服务功能业务流程相结合,扩·4263·计算机应用研究第27卷大组合服务运行时再规划空间,为组合服务QoS异常处理提供了保障。文献16首先提出了一种树型结构的组合服务QoS计算模型,然后提出了一种基于量子遗传算法的服务选择方法,采用二维多量子比特编码染色体,并附加标志位表示多路径信息,用量子旋转门实现个体的进化。相对于传统遗传算法,基于量子遗传算法的服务选择方法能在更

28、短的时间内搜索到更好的解。运用基本的GA来设计Web服务选择算法,其优点是使用简单、通用性强、易于实现,并具有并行性和全局搜索能力;缺点是易出现早熟收敛、运行结果不稳定和收敛性差的现象。这些缺点严重影响了算法在服务组合问题上的应用,需采用一定的改进策略提高算法的收敛速度与稳定性。3.4粒子群优化算法PSO是模仿鸟类的觅食行为受到生物群体模型启发而设计的一种新的智能优化算法。该算法采用群体探索问题的解空间,首先初始化一群随机粒子,然后通过迭代方式使每个粒子向自身找到的最好位置和群体中的最佳粒子靠近,从而搜寻最优解。在每次迭代中计算每个粒子新位置的适应值,根据粒子适应值更新个体极值和全局极值,通过

29、粒子的运动方程来更新自己的速度和位置。采用PSO算法解决基于QoS的Web服务选择问题,关键是要建立粒子位置矢量与组合方案间的映射关系,解决粒子位置的表示、速度算式的确定以及适应值函数的评估等问题。每个粒子代表一个候选解,即一种组合方案,由若干个(假设有n 个具体服务以一定顺序组成。用n维来表示每个粒子的位置X i=x i1,x i2,x in。其中x ij表示第i个抽象服务选择了它所对应的候选服务集中第j个具体服务的编号。每个粒子代表的组合服务的QoS属性值就是该粒子的适应度,其适应值函数依组合服务的具体实例而定。速度和位置的更新公式取决于服务选择所采用的编码方式,即粒子位置的表示方式。文献

30、1设计了一种基于离散微粒群算法的动态Web服务选择算法,将微粒的速度定义为服务的替换操作,并提出了max、rank和seq这三种速度运算算子,定义了微粒无希望/重希望准则,将约束条件转换为算法中的参数,从而增强了算法的全局搜索能力,同时也加快了收敛速度。所提算法不依赖于候选服务的数量,保证了算法的鲁棒性。但该文通过加权法将多个QoS参数聚合在一个适应值函数中进行优化,难以体现用户对QoS的偏好和个性化需求,从某种实际意义上并没有真正解决多QoS参数的Web服务选择问题。文献18基于多目标粒子群优化算法设计了求解QoS全局最优服务选择问题的算法;通过同时优化组合路径的多个QoS参数,最终产生一组

31、满足约束条件的Pareto最优解,用户可以根据特定需要从中选择最满意解;未被选中的非劣解可以作为备选方案,在所选非劣解发生意外时启用。文献21提出了一种基于PSO的多目标优化策略,用于解决Web服务组合中基于QoS的服务选择全局最优化问题。文献41将粒子的位置、速度和加运算进行了重新定义,提出了一种基于粒子群算法的解决QoS 动态服务组合算法,该算法能快速地得到一组满足约束条件的Pareto优化的服务组合。文献17提出了一种基于离散二进制粒子群算法的Web服务推荐策略以解决Web服务的优化选择。运用PSO来设计Web服务选择算法,具有并行计算、群体寻优的特点,其优点是算法简单易实现、控制参数少

32、,并且具有记忆功能和强大的全局寻优能力,但进化后期收敛慢、局部搜索能力差、搜索精度不够高,容易陷入局部极值和参数依赖性强等缺陷。3.5蚁群优化算法ACO是一种新兴的模拟进化算法,它通过模拟蚁群在觅食过程中个体之间的信息交流与相互协作机制所体现出的寻优能力来解决现实中一些困难的优化问题。ACO通过一种正反馈方式最终找到一条最优路径:蚂蚁在觅食期间会在所经过的路径上留下不同浓度的信息素,信息素会随着时间的流逝而挥发。某一条路径走过的蚂蚁越多,留下的信息素浓度越高,使得在一定的时间内,越短的路径会被越多的蚂蚁访问,后来的蚂蚁就会以较大的几率选择信息素较浓的路径以指导自己的运动方向。采用ACO解决基于

33、QoS的Web服务选择问题,关键是要解决如何根据组合服务中各QoS参数来确定状态转移规则、信息素的更新方式和解的适应函数评估等问题。每只蚂蚁负责构建服务组合的一条路径,即代表了一种组合方案,并可能向它所选择的具体服务释放一定量的信息素。每只蚂蚁从服务组合中第一个抽象服务所对应的候选服务集中选择一个具体服务开始,每经过一次迭代,蚂蚁就向解中按抽象服务执行的先后顺序添加一个新的还没有被分配过的抽象服务所对应的候选服务集中的具体服务,且须利用信息素、启发式信息等来选择新的具体服务添加到解中。当服务组合中所有抽象服务都被蚂蚁分配了具体服务之后,一个候选的组合方案就构建了。文献6基于蚁群系统优化算法,设

34、计了信任感知的组合服务选择方法。文献20利用多目标蚁群算法提出一种基于QoS全局最优的多目标动态Web服务选择算法。其基本思路是:将全局最优动态Web服务选择问题转换为一个带QoS约束的多目标服务组合优化问题,通过多目标蚁群算法,对动态服务选择问题中的多个目标函数同时进行优化,产生一组满足约束条件的Pareto优化解,最终用户则根据自己的偏好从中进行选择。文献25给出了组合服务问题的蚁群算法模型以及求解问题算法的伪代码,为解决组合服务问题提出了一种新的思路。文献24是在文献25研究的基础上,使用改进的ACO解决Web服务组合过程中QoS优化组合问题,提出基于蚁群算法实现动态Web服务组合多目标

35、优化过程中的QoS 优化选择,用于实现用户对组合服务质量的需求。该方法根据不同Web服务的QoS属性指标,选择相应的Web服务得到Pareto最优解集合,用户根据实际需要或对目标函数的偏好,从Pareto最优解集中挑选一个或多个解作为组合服务质量问题的最优解,从而形成最后的决策方案。基于QoS的Web服务选择问题是离散优化问题,蚁群算法的生物学背景决定了它更适合求解离散空间中的组合优化问题。运用ACO来设计Web服务选择算法,其优点是具有自适应、自组织、正反馈性和协同性,具有很强的发现较好解的能力,且具有较强的鲁棒性和优良的分布并行性,易于与其他方·5263·第10期李金忠

36、,等:基于QoS的Web服务选择算法综述法相结合等,在动态环境下也表现出高度的灵活性和健壮性。但是其搜索时间较长,而且容易因为受到寻优过程中早期发现的较好解的影响而陷入局部最优解,使搜索停滞。此外,在求解多目标优化问题时,蚂蚁之间的这种信息素交流方式会使求得的解集中在解空间的某一区域内,不利于群体多样性的保持24。蚁群算法的初始化参数的选择、信息素的更新等问题都带有经验性和直觉性,需要在服务组合等应用实践中和理论上作更深入的探索。3.6融合算法近年来,融合优化策略得到了广泛的应用。由于每种算法都有其优缺点,为了能解决更大规模和更复杂的现代问题,单一的优化算法将不能满足庞大数据对算法高效率的要求

37、,需要使各种算法之间能够优势互补,以提高对复杂问题进行优化的性能和效率。因此,算法融合是提高算法优化性能的一个重要而有效的途径,其出发点是使单一算法互相取长补短,产生更好的优化性能和效率。文献15在重定义粒子群算法的位置、速度,加/减法和乘法的基础上,结合遗传算法中的交叉、变异操作,设计了基于混合粒子群的QoS 调度方法以选取满足用户QoS 要求的最佳候选服务并执行。文献42针对服务选择的特征,设计了遗传算法来解决业务质量全局最优化的服务选择方法,生成一组满足约束条件的服务组合流程集。在此遗传算法基础上,引入免疫学知识对该算法进行扩展,给出了相应的免疫遗传算法并通过实验对比为遗传算法指出了改进

38、方向。除了上述算法之外,人们还提出了很多算法以求解Web 服务选择问题。文献7提出了一种基于启发式算法的可扩展的QoS 计算方法,将Web 服务选择问题分解为若干个子优化问题,与使用线性规划方法相比,能更快速地找到近优解。文献23利用马尔可夫决策过程(MDP 设计了随机QoS 感知的可靠Web 服务组合算法。文献28提出了基于集对分析的Web 服务选取方法。文献43考虑可选服务的服务质量往往依赖于其他可选服务,提出了支持服务关联的组合服务选择方法。文献44提出了一种基于skyline 的方法,减少了将要考虑的候选服务的数量,以更高效地为Web 服务组合进行服务的选择。文献45提出了一种可满足用

39、户偏好的选择算法,用户偏好可作为QoS 标准上的权重,同时也可作为语义性定义事务需求的风险级别。文献46基于模糊线性规划技术提出了一种QoS 感知的服务选择模型,用来区分这些候选服务的差异性,以帮助服务消费者根据他们的期望和偏好来选择最合适的服务。文献34采用两阶段优化策略(构建一套可行的概念设计和实例化概念设计进行质量感知的Web 服务选择。它可以自动生成一些可行的服务执行计划,并从中选择最能满足用户需求质量的一个计划,并且提出了一种进化算法。该算法能同时进化多个可行的执行计划,并允许这些计划互相竞争,从而获得最佳计划。4结束语4.1存在的问题选取高质量同时满足用户需求的Web 服务是服务选

40、择的重要目标。当前,虽已提出了大量的基于QoS 的Web 服务选择算法,但现存的算法或多或少地存在以下一些问题:a 大部分服务选择算法是对组合服务中Web 服务的每个QoS 属性赋予一个权值,把用户的多个QoS 参数要求聚合为一个目标函数计算各服务的综合QoS 值,然后采用传统的求解整数规划的方法或单目标优化算法优化该函数从而获得全局QoS 综合最优解。但由于(a 服务实例的各个QoS 参数不可同等度量,甚至相互冲突难以统一量化,其结果不仅对权值非常敏感,而且需要用户对问题有充足的先验知识,如各参数的重要程度等,而在实际应用时往往较难准确地给出QoS 参数的权值,导致难以正常实施优化或优化效果

41、差;(b 所获得的解是满足约束条件的单目标最优解,不能实质性地解决多目标的优化问题,如同时优化组合服务中的响应时间和执行费用等。所以这在一定程度上限制了算法的实用性。b 大部分服务选择算法多关注QoS 值的计算。通过某种方法如加权法等计算多维QoS 属性的综合QoS 值并对其进行排序以评定服务的优劣,QoS 值越大的服务越优秀,服务选择的结果依赖于QoS 值的结果,没有充分考虑服务请求者的需求。但在实际应用中,QoS 值最大的服务不一定是服务请求者最需要的,与服务请求者需求最接近的服务才是应该被选择的。c 大部分服务选择算法是假定Web 服务的QoS 在组合服务执行过程中是静态不变的。而实际的

42、应用需求中,在组合服务执行过程期间,Web 服务随时可能离开或加入,其QoS 也可能在被多次访问时而下降或者在一段时间内未被访问而上升,即Web 服务是动态变化的,其QoS 是随机不确定的。结果导致在服务组合时以较大概率出现组合失败,从而影响了服务组合成功率和组合服务的质量。d 考虑信任与声誉的Web 服务选择算法较少。Web 服务提供商的信任与声誉机制比Web 服务本身更重要,对于Web 服务提供商而言,建立信任与声誉有利于选择Web 服务,这一点在Web 服务选择中提供商的信任与声誉常被忽视47。e 现有的组合服务中,各可选服务被认为是相互独立的,可选服务的服务质量独立于其他服务,而在实际

43、的面向服务应用中,可选服务的服务质量往往依赖于其他可选服务,现有组合服务选择方法无法应对这种普遍存在的场景。由于现有的组合服务选择方法缺乏对这种关联关系的考虑,使得可选服务的服务质量在关联关系出现时与其所宣称的QoS 值产生偏离,从而导致所选择的组合服务实际的QoS 有所下降,不利于组合服务在最大程度上满足服务消费者的需求43。f 现有的服务选择算法的通用性或求解效率尚不够理想48,具有容错、失效恢复等机制的Web 服务选择算法也较少。4.2展望尽管基于QoS 的Web 服务选择已取得了一些研究成果,但随着Web 服务应用的复杂性发展,仍需对其进行深入的研究:a 现有智能算法的改进及其在真实W

44、eb 环境下的适应性研究。目前,将启发式智能优化算法应用于解决Web 服务选择问题的研究成果相对较多,但在参数选择对优化解的影响及解是否分配均匀、解的质量是否逼近最优、搜索动态的终止条件等方面尚需进一步论证。并且所设计的选择算法大部分还处于仿真阶段,将所提出的选择算法应用于实际的大规模面向Web 服务系统中,以真实的Web 环境检验、测试所提算法的可·6263·计算机应用研究第27卷第 10 期 李金忠， 基于 QoS 的 Web 服务选择算法综述 等： 2008： 190199 tures Berlin： Springer， · 3627· 行性和有效

45、性， 以便对其可靠性、 适应性和性能作更深入的分 析和改进。 b） 多种算法的融合。目前， 已应用于服务选择的融合算 法的研究还比较少。吸取多个算法的优点进行算法的融合， 如 在实践中证明了算法的有效性， 是 在 PSO 中加入 ACO 思想等， 提高服务选择算法性能的一个重要途径； 还可融入一些其他 DNA 应用于组合优化领域中智能优化算法， 如免疫算法、 的、 计算、 人工神经网络等， 用于设计 Web 服务选择算法， 这方面 还有很多工作待做。 c） 探索同时多目标优化多维 QoS 属性的 Web 服务选择算 法。由于 Web 服务的各维 QoS 属性值间的可比性难以衡量和 把握， 而在

46、实际应用中所要找的最优解往往并不一定是所有 QoS 属性的最优解， 而是在满足 QoS 属性约束下的 Pareto 优化 解， 故需要寻找能同时优化多维 QoS 属性的 Web 服务选择算 法。多目标进化算法应用于 Web 服务选择是一个重要的研究 方向， 当前的研究并不多。 d） 服务选择算 法 的 自 适 应 性 研 究。网 络 环 境 的 不 断 改 服务的出现、 消亡、 更新、 服务 QoS 的变化等情况， 都可能 变， 造成已经构建的服务组合应用无法继续使用， 但停止原应用重 代价和风险， 故在 新开发或部署往往会带来无法接受的延迟、 实际应用场景中， 需要组合服务具有动态自适应的特

47、点。在服 务选择算法中融入一定的容错机制、 协商机制、 信任及声誉机 失败恢复机制和重计划选取等以适应在服务组合执行过程 制、 从而提高组合服务的健壮性、 稳定 中的 Web 服务调用异常， 性、 可靠性及其他多方面的性能等。 e） 个性化的 Web 服务选择算法研究。在一个 Web 服务 个性化是重要的， 以便所选服务满足用户的特定需 系统中， 求 47 8 YU Tao， LIN K J Service selection algorithms for Web services with end- end QoS constraintsJ Journal of Information Sy

48、stems to 2005， 2） ： 1033（ 126 and Ebusiness Management， 9 YU Tao， K J Service selection algorithms for composing complex LIN services with multiple QoS constraints C/ / Proc of International Conference on ServiceOriented Computing 2005： 130143 10 胡建强， 李涓子， 廖桂平 一种基于多维服务质量的局部最优服务 J 2010， 3） ： 526-534

49、33（ 选择模型 计算机学报， 11 杨放春， 苏森， 李祯 混合 QoS 模型感知的语义 Web 服务组合策 2008， 10） ： 169738（ 1746 略J 中国科学 F 辑： 信息科学， 12 李祯， 杨放春， 苏森 基于模糊多属性决策理论的语义 Web 服务 J 2009， 3） ： 583-596 20（ 组合算法 软件学报， 13 张童， 刘云生， 查亚兵 一种 QoS 驱动的仿真服务组合优化方法 系统仿真学报， J 2009， 16） ： 4990-4994 21（ 14 蒋哲远， 韩江洪， 王钊 动态的 QoS 感知 Web 服务选择和组合优 J 2009， 5） ： 1

50、01432（ 1025 化模型 计算机学报， 15 胡春华， 吴敏， 刘国平， 一种基于业务生成图的 Web 服务工作 等 2007， 8） ： 187018（ 1882 流构造方法J 软件学报， 16 黄伯虎， 段振华 量子遗传算法在 Web 服务选择中的应用J 西 2010， 1） ： 56-61 37（ 安电子科技大学学报： 自然科学版， 17 蔡华利， 刘鲁， 樊坤， 基于 BPSO 的 Web 服务推荐策略J 深 等 2010， 1） ： 49-55 27（ 圳大学学报： 理工版， 18 孙学胜， 曹玖新， 刘波， 基于多目标粒子群优化的服务选择算 等 2009， 4） ： 684-

51、689 39（ 法J 东南大学学报： 自然科学版， 19 胡焕耀， 董渭清， 符锐， 面向 Pareto 最优遗传算法的服务组合 等 J 2009， 12） ： 50-54 43（ 方法 西安交通大学学报， 20 方其庆， 刘庆华， 彭晓明， QoS 全局最优的多目标 Web 服务选 等 J 2009， 12） ： 4442-4445 26（ 择算法 计算机应用研究， 21 夏虹， 李增智 粒子群算法求解 Web 服务组合中基于 QoS 的服务 J 2009， 4） ： 63-67 32（ 选择 北京邮电大学学报， 22 CLARO D B， ALBERS P， HAO J Selecting

52、 Web services for optimal compositionC/ / Proc of IEEE International Conference on Web Services，Workshop on Semantic and Dynamic Web Processes 2005 23 范小芹， 蒋昌俊， 王俊丽， 随机 QoS 感知的可靠 Web 服务组合 等 软件学报， J 2009， 3） ： 546-556 20（ 24 彭晓明， 炎 祥， 兵 舰 蚁 群 算 法 在 Web 服 务 组 合 中 的 应 用 何 朱 计算机工程， J 2009， 10） ： 18235（

53、187 25 王创伟， 钱雪忠 蚁群算法在 Web 服务组合问题中的应用研究 计算机工程与设计， J 2007， 24） ： 5912-5914 28（ 26 苏森， 飞， 放 春 分 布 式 环 境 中 服 务 组 合 的 迭 代 选 择 算 法 李 杨 中国科学 F 辑： 信息科学， J 2008， 10） ： 171738（ 1732 27 YU Tao， ZHANG Yue， K J Efficient algorithms for Web services LIN selection with end- end QoS constraintsJ ACM Trans on the to

54、 Web， 2007， 1） ： 6-31 1（ 28 朱红宁， 张斌 基于 SPA 的 Web 服务选取方法J 计算机科学， 2009， 11） ： 32-35 36（ 29 LAMPARTER S， ANKOLEKAR A， STUDER R， al Preferenceet based selection of highly configurable Web servicesC/ / Proc of the 16th International Conference on World Wide Web New York： ACM Press， 2007： 10131022 30 曹利培，

55、 爱 玲， 静 基 于 QoS 的 两 阶 段 Web 服 务 选 择 方 法 李 刘 计算机工程与设计， J 2009， 3） ： 74730（ 751 31 ALRIFAI M， RISSE T Combining global optimization with local selection for efficient QoSaware service composition C/ / Proc of the 18th International Conference on World Wide Web New York： ACM Press， 2009： 881-890 （ 下转第

56、3638 页） 。所以，将用户偏好同 QoS 一起融入到服务选择过程当 中， 充分考虑用户个性化的 Web 服务选择算法， 仍是未来的研 究难点，这将会拓宽算法的适用范围。 f） 由于在实际的 Web 应用场景中， 各服务的 QoS 可能存 在关联 43， 49 关系， 支持服务关联的 Web 服务选择方法具有较 应推广之。 强的针对性和实用性， g） 将服务选择与不同服务领域特性相结合，提出新的算 法以提高选择效率与准确性。 参考文献： 1 范小芹， 蒋昌俊， 方贤文， 基于离散微粒群算法的动态 Web 服 等 2010， 1） ： 14747（ 156 务选择J 计算机研究与发展， 2 刘

57、书雷， 刘云翔， 张帆， 一种服务聚合中 QoS 全局最优服务动 等 2007， 3） ： 646-656 18（ 态选择算法J 软件学报， 3 ZENG Liangzhao， BENATALLAH B， NGU A H H， al QoSet aware middleware for Web services compositionJ IEEE Trans on Software Engineering， 2004， 5） ： 311-327 30（ 4 莫振华， 蔡鸿明， 姜丽红 基于遗传算法的多 QoS 约束服务选择 计算机应用与软件， J 2009， 3） ： 4-6 26（ 5 ZENG Liangzhao， BENATALLAH B， DUMAS M， al Quality driven et C/ / Proc of the 12th International ConfeWeb services composition rence on World Wide Web New York： ACM Press， 2003： 411-421 6 王勇， J 代桂平， 侯亚荣 信任感知的组合服务