基于服务质量的动态Web服务组合方法研究

吴青林　周天宏

1(郧阳师范高等专科学校计算机科学系　湖北 十堰 442000)2(武汉商学院信息工程系　湖北 武汉 430056)



基于服务质量的动态Web服务组合方法研究

吴青林1周天宏2

1(郧阳师范高等专科学校计算机科学系湖北 十堰 442000)2(武汉商学院信息工程系湖北 武汉 430056)

摘要针对Web服务组合中权重固定、选择不灵活、性能不佳等问题，通过改进遗传算法提出一种基于服务质量的变权动态Web服务组合方法(VW-DWSC-QoS)。VW-DWSC-QoS组合方法使用变权QoS参数，引入罚函数策略，并动态调整变权因子、交叉因子和变异因子，使其实现了在较短时间内找到符合用户需求的Web服务组合。理论分析和仿真实验表明该组合方法的可行性和有效性，与传统的方法相比，其最优解具有更好的服务质量和适应度。

关键词动态Web服务QoS遗传算法变权

0引言

Web服务是面向服务的体系结构的一种实现技术，随着大数据、云计算以及软件即服务等的流行，互联网上的Web服务数量不断增加。Web服务在电子商务、教育、企业应用集成等领域发挥的作用越来越重要。作为一种新型的分布式计算模式，具有的跨平台、跨标准、跨语言特点使其受到工业界和学术界的广泛关注，同时互联网上的Web服务质量各异，单个服务功能有限，不能够最大限度地满足用户的多样化需求。在实际应用中，为了提供更合理的Web服务资源，需要基于特定的业务流程将多个Web服务组合成更大粒度的服务。因此，如何有效组合Web服务，从符合各结点功能的Web服务中选择出具体的Web服务，满足用户对服务质量多维度及不同偏好的需求，成为当前Web服务领域研究的关键问题。

1相关工作

Web服务组合是Web服务应用的关键环节，服务质量QoS参数是服务优劣的重要指标，当前基于服务质量的Web服务组合中主要采用QoS局部优化方法和全局优化方法。局部优化方法针对组合流程的单一结点选择服务，全局优化方法针对整个组合流程选择不同的服务协同工作。文献[1-3]对一组相同功能的服务，通过每个服务QoS的参数信息进行加权和排序，并将以此为选择依据分别为组合流程的每个节点逐一选择加权和最大的服务来构建目标组合服务。这种方法中各个结点选择服务是相互独立的，不能从全局角度上选择服务。文献[4,5]把组合服务的各个QoS约束参数线性加权为单目标函数并通过线性规划方法解决服务。文献[6]提出了支持QoS 的服务组合计算模型，模型中考虑了权重的风险级别。文献[7]把寻求满足多QoS属性的组合问题转化成为有向图搜索最优多约束问题。文献[8]将服务的动态选择过程看作Markov决策过程，以寻求使服务质量最优的方案。文献[9]提出了支持QoS感知的组合算法，具有支持单个Web服务和组合Web服务QoS计算的功能。

当前主要针对基于局部服务质量的Web服务组合，但基于局部服务质量的Web服务组合中各个单一服务的性能达到最优并不能保证整个服务组合的性能最优，需要整个考虑Web服务的质量。基于全局的Web服务质量的Web服务组合还不成熟，主要存在以下不足：

(1) QoS属性的赋权灵活性不够，主要采用固定权重，赋权不具有伸缩性和模糊性，当存在某服务的单一QoS属性值特别高使Web质量提升，这样的服务有可能其他QoS属性特别低不满足用户的需求，不能有效描述Web服务的质量。

(2) 其产生的解为单解，并且目标函数和约束是线性的，用户没有选择的空间。在很多情况下用户选择Web服务组合时不一定需要最优的，而是需要最符合自己要求的，从而限制了算法的应用范围。

(3) 当服务数量增多时，计算量迅速增加，使组合时间会增加，交易成功率也会下降，服务组合的性能受到一定影响。

本文针对以上问题，通过改进遗传算法提出了变权QoS全局动态Web服务组合方法(在DWSC-GA),方法中引入罚函数，利用迭代次数、动态交叉动态和变异因子等策略，实现了在较短时间内找到符合用户需求的Web服务组合方案。

2QOS属性及四种组合结构描述

(1) 原子服务QoS描述

原子服务质量描述是多维的, 本文定义q(s) = {q1(s),q2(s),…,qn(s)}表示服务s的n维质量属性值，其中qk(s)表示服务s的第k个属性值,服务质量属性值可以从服务提供者、历史交易情况或用户等多方面获取。本文选择响应时间、成本、可靠性、信誉度作为原子服务QoS属性。

(2) 服务组合描述

服务组合是将较小的细粒度服务组合成粗粒度服务，其可以包括原子服务也可以嵌套包括其他组合服务。组合服务的服务质量属性通过原子服务的服务质量聚合形成，本文定义q(cs)={q1(cs),q2(cs),…,qn(cs)}表示组合服务n维质量属性值，其中qk(cs)表示组合服务s的第k个属性值。组合服务流程是一个基于Web服力的的工作流，大部分组合流程可以由串联模型、并列模型、选择模型和循环模型组合而成[10-12]。表1给出了四种组合模型结构相应用QOS模型计算表达式。

表1　组合服务QoS属性计算方法

3服务预处理

3.1服务属性的归一化处理

Web服务的QoS属性的计量单位和取值范围不具有可比性,有些属性取值越大,其性能就越低,属于负属性,例如响应时间；另外一些属性取值越大,表示其性能越高,例如可用性。并且其不同属性之间数值相差巨大。因此在考虑其不同的QoS属性进行组合时应该对其服质进行归一化处理,将其转化成无量纲的值,将其范围都限定在[0-1]之间。为了使各种QoS属性统一,本文采用式(1)和式(2)分别对增量型和减量型参数进行归一化[13,14]。

(1)

(2)

3.2权重获取

如果用户能够明确指定Web服务权重，则直接获得权重，如果用户对权重用自然语言描述，可以参照表2的数据，通过对应关系将其转化为固定权值[15,16]。

表2　自然语言描述与模糊集数据对照

3.3变权处理

针对在服务选择过程中存在某单一属性值很高导致综合属性变高，却因为其他属性很低无法满足用户要求的问题，本文通过变权向量解决这一问题，基本思路是影响QoS属性的权重根据其取值范围做一定的变化，以使每个属性更好体现在组合服务中的作用。

(3)

L的取值根据应用要求决定。通过式(3)变权向量进行加权综合计算Web服务质量时，可以有效降低因个别QoS属性值相差较大的Web服务的质量值，从而更好地反映服务的质量属性。容易证明，变化后的权重向量仍然满足归一性。

4基于服务质量的动态Web服务组合方法(VW-DWSC-QoS)

该方法基于改进遗传算法实现，遗传算法GA (Genetic Algorithm)首先由Holland教授在上世纪七十年代提出[17]，模拟自然界生物进化过程与机制求解极值问题的一类自组织、自适应搜索算法，具有较强的鲁棒性和通用优化能力，广泛地应用于求解复杂的非线性和多维空间寻优问题。

第一步染色体编码

本文采用关系矩阵方式对染色体编码，该方式能够很好地反映组合服务的相互关系。关系矩阵主对角线上的元素表示遗传算法染色体的基因位，与Web服务组合的工作任务相对应，非对角线元素表示组合服务任务之间的关系，染色体编码如图1所示。

图1染色体矩阵编码

染色体编码反映了组合Web服务中包括的任务及其关系，对角线元素Bii=1表示组合服务包含该任务，Bii=0表示组合服务没有包括该任务。非对角线元素BIJ为任务关系位，如果BIJ=1，表示在组合服务中任务i与任务j相邻，并位于其直接前方。染色体编码通过矩阵主对角线的元素排列实现，组合服务集合中选出部分编码用为遗传算法的初始群即为种群，各类遗传操作针对矩阵对角线的元素实现。

第二步初始化群体

根据Web服务所能完成的原子处理任务分类，产生初始Web服务群体p=(p1,p2,…,p3)，pn为Web服务种群规模大小，根据经验或者是专家提供的建议得出，这里取pn=100。

第三步计算个体适应度

Web服务用户一般会对资源服务的选择提出响应时间、使用成本等方面的要求或限制。本文适应度函数通过罚函数法将限制条件与目标函数综合在一起实现，可以通过下式实现：

(4)

式(1)中的Rjmax表示第j个约束条件的最大值，Rj min表示第j个约束条件的最小值,n表示用户提出的约束条件的个数，λ是罚函数系数，属于经验值。Pj表示一个Qj或者多个Qj组合的运算值，ΔPi通过下式表示：

(5)

第四步选择

选择方法采用精英个体优选策略，根据适应度函数判断当前适应度最好的Web服务组合，将适应度最好的Web服务组合筛选出不进行遗传操作，而将该个体替换本代遗传操作后产生的适应度最低的Web服务组合，经过精英个体优选策略实现了父代中最优的Web服务组合遗传到下一代，而最劣的Web服务组合直接淘汰，有效地保证了遗传Web服务组合的质量。

第五步交叉和变异

根据其Web服务组合个体适应度数值选择合适的交叉概率和变异概率，在个体遗传过程中根据适应度数值大小的变化动态调节交叉概率和变异概率的数值，这样每个个体能够动态适应遗传环境。在染色体遗传过程中，设群体中具有较低适应度个体的交叉概率为Pc0,具有最高个体适应度个体的交叉概率为Pcl(其中Pcl

(6)

(7)

第六步终止

本算法的结束条件根据最大迭代次数法则来决定，推荐Web服务组合个体适应度最大的解作为最终解。满足以下终止条件之一即可结束进化过程：(1) 出现适应度为零的Web服务种群；(2) 出现适应度值达到满足用户需求的个体；(3) 群体中的最优个体已经没有明显的进化效果；(4) 进化代数已经达到算法设定的代数。

5DWSC-GA算法分析

本文提出的算法VW-DWSC-QoS算法，对部分单QoS属性值较高的Web服务对象，使用了QoS变权处理，并在组合过程中引入罚函数策略，动态调整变权因子、交叉因子和变异因子，使其实现了在较短时间内找到符合用户需求的Web服务组合，理论分析，优点主要体现在以下方面：

(1) 该模型中，首先将不同纲量的QoS参数转化成[0 1]之间的参数，便于加权处理，并对单一QoS属性作变权处理，其QoS属性的权重根据其取值范围做一定的变化，使得每个属性更好地体现在组合服务中的作用。

(2) 适应度函数通过罚函数法将限制条件与目标函数综合在一起实现，使个体适应度动态适应服务环境变化。

(3) 在遗传过程中根据适应度的变化自动调节交叉概率和变异概率的数值,这样每个个体具有自适应环境的能力。

(4) 关系矩阵方式对染色体编码，该方式既能反映服务的组合并系，还能体现任务路径信息的编码方式。

6仿真实验

仿真实验的计算机配置是Pentium 3500 MH处理器，2 GB内存，操作系统为win7系统，Matlab8.1软件。由于当前没有成熟的Web服务合测试集，本实验指定服务模型，根据服务模型将目标任务分解为5个子任务，5个子任务所对应的候选服务范围为5到60，从每个子任务中选择一个候选服务进行组合，以完成用户目标任务。设每个候选服务的QoS属性分别为响应时间(t)，成本(c)，可靠性(av)，信誉度(rep)，依3.2节权重获取方式，设其权重为(0.3,0.3,0.2,0.2),群体规模取50，最大迭代次数取150。分别设Pc0=0.68 ，Pcl=0.26，Pm0=0.42，Pml=0.19，经组合方法获取最优组合。将从以下两个方面进行性能比较：

1) 整数规划算法和本文VW-DWSC-QoS算法组合时间变化：

当每个任务的候选服务较少时，Integer Planning Algorithm比VW-DWSC-QoS算法具有一定的优势，但随着候选服务的逐渐增加，Integer Planning Algorithm花费的时间增加较快，而本文提出的VW-DWSC-QoS算法所需时间没有太明显的增加，表现出较为明显的优势。如图2所示。

图2　任务完成时间比较

2) 本文VW-DWSC-QoS算法与固定权重算法相比

实验中的流程结构采用顺序结构实现，当每个结点的候选服务数增加时，服务组合成功率具有下降的趋势，将VW-DWSC-QoS算法与固定权重算法相比，VW-DWSC-QoS算法组合成功率变化比较平缓，具有更高的组合成功率。如图3所示。

图3　任务交易成功率比较

从以上两次实验对比中可以看出本文提出的VW-DWSC-QoS算法使Web服务在组合时间和组合成功率上都有一定的进步，具有一定的实用价值。

7结语

Web服务组合在面向服务体系结构软件中的重要问题，将现有的服务组合成功能更强大的服务，能够更好地增强Web服务价值。本文在相关研究的基础上，提出的QoS感知的动态适应Web服务组合，考虑了服务的动态适应性，使其服务组合更能真实地反映Web服务的特点，提高了组合的质量和效率，更好地满足了用户对Web服务的需求。

参考文献

[1] Benatallah B,Dumas M.Declarative composition and peer-to-peer provisioning of dynamic Web services[C]//Proc of the 18 the International Conference on Data Engineering.San Jose:IEEE Computer Society,2002:297-308.

[2] Liangzhao Zeng,Boualem Benatallah.QoS Aware Middleware for Web Services Composition[J].IEEE Transactions on Software Enginneering,2004,30(5):311-327.

[3] Grafen P,Aberer K.Cross-low:cross-organizationl workflow management in dynamic virtual ebteroruses[J].Internional Journal of Computer Systems Science & Engineering,2000,15(5):277-290.

[4] Jorge C,Amit S.Quality of service for workflows and Web service processes[J].Joumal of Web Semantics,2004,1(3):281-338.

[5] 何必壮,徐哲,吴峰.基于IHE的动态语义Web服务组合研究[J].计算机应用与软件,2012,29(10):156-157.

[6] Joyce EI Haddad,Maude manouvrier.Dos-driven Selection of Web Services for Transactional Composition[C]//IEEE international Conference on web services,2008:653-660.

[7] Liu Qing,Zhang ShIlong.Web services composition with QoS bound based on simulated annealing algorithm[J].Journal of Southeast University(English Edition),2008,24(3):308-311.

[8] Prashant Doshi,Richard Goodwin.Dyanmic workflow composition using Markov decision processes.International[J].Journal of Web services research.Jan-March,2005,2(1):1-17.

[9] Megha Mohabey,Narahari Y.A combinatorial procurement auction for Qos aware web swevices compositon[C]//Proceedings of the 3rd annual IEEE Confercence on automation science and engineering Scottsdale,2007:716-721.

[10] Dong yuanyuan,Ni Hong,Deng haojiang.Service selection strategy offering global optimal quality of service[J].Journal of Chinese Computer System,2011,32(3):455-459.

[11] Mohammad Alrifai,Dimitrios Skoutas,Thomas Risse.Selecting skyline services for QoS-based Web service composition[C]//Poceedings of International World Wide Web Conference.ACM,2010:11-20.

[12] 代钰,杨雷,张斌.支持组合服务选取的QoS模型及优化求解[J].计算机学报,2009,29(7):1167-1178.

[13] 刘华鹏,刘胜全.基于主体和QoS的语义Web服务组合方法[J].计算机工程,2013,39(10):227-231.

[14] 何炎祥,吴钊.动态Web服务组合关键技术与性能分析[M].清华大学出版社,2011:6-78.

[15] 武云鹏,包卫东.服务组合系统研究综述[J].计算机科学,2011,38(9):1-4.

[16] 康国胜,刘建勋,唐明董.QoS全局最优动态Web服务选择算法[J].小型微型计算机系统,2013(1):73-76.

[17] 杨溢龙,王伟茹.基于遗传算法Web服务组合的一般过程[J].计算机数字与工程,2012,40(7):13-15.

RESEARCH ON QUALITY OF SERVICE-BASED DYNAMIC WEB SERVICE COMPOSITION METHOD

Wu Qinglin1Zhou Tianhong2

1(DepartmentofComputerScience,YunyangTeachers’College,Shiyan442000,Hubei,China)2(DepartmentofInformationEngineering,WuhanCommercialInstitute,Wuhan430056,Hubei,China)

AbstractFor the problems in Web service composition such as the fixed weight, inflexible choice and poor performance, etc., we put forward a quality of service-based variable weight dynamic Web service composition method (VW-DWSC-QoS) by the improved genetic algorithm. The VW-DWSC-QoS method uses the variable weight QoS parameters, introduces the penalty function strategy, and dynamic adjusts the variable weight factor, crossover and mutation factor, these makes it good in finding the Web service compositions meeting users need within a relatively short period. Theoretical analysis and simulation experiments all show the feasibility and effectiveness of this method, and compared with the traditional method, its optimal solution has better quality of service and fitness.

KeywordsDynamicWeb serviceQuality of serviceGenetic algorithmVariable weight

收稿日期：2015-01-03。湖北省教育厅重点科研项目(D201450 01)。吴青林，副教授，主研领域：Web服务，信息管理。周天宏，教授。

中图分类号TP393

文献标识码A

DOI:10.3969/j.issn.1000-386x.2016.05.006