混合QoS模型感知的语义Web服务组合策略

中国科学E辑:信息科学2008年第38卷第10期:1697~1716服务组合策略杨放春*,苏森,李祯北京邮电大学网络与交换技术国家重点实验室,北京100088*E-mail:[e-mail]收稿日期:2008-06-03;接受日期:2008-09-08国家重点基础研究发展计划(批准号:2003CB314806)、中国高技术研究发展计划(批准号:2006AA01Z164)、新世纪人才支持计划(批准号:NCET-05-0114)、国家自然科学基金计划(批准号:60672121)和北京市教委共建计划资助项目摘要混合QoS模型在传统模型中加入了不确定因素用来增强其语义描述能力,为解决混合QoS模型感知的语义Web服务组合问题,提出了一种基于不确定多属性决策理论的全局优化决策算法(uncertainmulti-attributedecisionmaking-basedcompositionalgorithm,UMC).该算法分为2个部分:其中UMC-Core可用于综合评估以实数型、区间型和语言型数据描述的服务质量信息;UMC-DH(distributedandheuristicframeworkforUMC)是为UMC设计的分布式与启发式相结合的算法执行框架,用来解决服务组合求解空间增大时的效率问题.仿真结果证实,相比于其他类似算法,UMC算法具有较高的运行时效率、最优解近似度和最优解成功率.关键词服务质量(QoS)语义Web服务服务组合不确定理论多属性决策理论启发式算法随着互联网行业的迅猛发展,越来越多的在线商业解决方案被构建出来.然而任何一个服务都只能满足相对单一的客户需求.服务提供商们迫切希望现有的服务能够被方便地组合成功能更加强大的增值服务,用来满足更为多样化的需求.Web服务技术使得这种设想成为可能[1].与此同时,语义网技术[2]通过提供语义描述方法为Web服务的进一步发展给予了强大的动力,使得Web服务过程能够被智能主体自治地执行,从而解放人工操作.这2种技术的结合体—语义Web服务[3]全面掀起了新一代互联网服务的革命.关于语义Web服务组合的研究是一直以来的焦点和难点问题.从概念上讲,组合过程包括任务规划、服务发现和QoS感知的服务选择过程,其主要任务分别是:基于工作流技术生成组合服务的执行路径[4~6];通过语义匹配的方法[7]为执行路径中的每个任务找到满足功能性需求的服务实例;综合评估候选方案的QoS,在满足客户QoS限制的前提下,选择出昀优的解决方案.本文主要围绕组合中的昀后一杨放春等:混合QoS模型感知的语义Web服务组合策略1698个过程进行讨论,目前与该过程相关的研究工作包括QoS聚合(根据单个服务的QoS值计算整个执行计划的总体QoS值)、语义QoS匹配[8,9](找到满足客户总体非功能需求的执行计划)和昀终决策[10~16](找到昀优的解决方案).然而,目前的QoS聚合算法和昀终决策算法都基于一个假设:所有的QoS数据必须以实数的形式明确给出.这个假设早已不能满足当今商业应用对QoS描述的需求,越来越多的学者认为这种描述方法会丧失大量有用的数据信息,对于某些QoS属性应该以不确定的形式给出以增强模型的描述能力[8,9,11].其中可采用区间型数据描述某些QoS属性(如响应时间)在某一时间段内的突发昀大值和昀小值[8,9],同时采用语言型数据描述那些不适合以具体数值表示的QoS属性[11](如可靠性).然而,目前的决策方法均不能有效地支持这种混合QoS模型.为此本文提出了一种基于不确定多属性决策理论的全局优化决策算法(uncertainmulti-attributedecisionmaking-basedcompositionalgorithm,UMC).UMC分为2个主要组成部分:UMC-Core和UMC-DH(distributedandheuristicframeworkforUMC),其中UMC-Core用于对混合QoS进行综合评估,共包括3个主要的步骤:去模糊化(将语言型表示的数据转变为实数)、决策矩阵规格化、候选方案综合评估.UMC-DH是针对解决组合算法效率难题而为UMC设计的分布式与启发式相结合的执行框架,主要包括分布式求解局部昀优解、并行结构k启发聚合和全局回溯控制策略.本文的其他贡献在于:介绍了一个用于描述混合QoS模型的本体;基于多主体系统的服务组合引擎框架,并通过仿真实验证实,相比于其他类似算法,UMC算法具有执行速度快、昀优解近似度高和昀优解成功率高的优势.本文的其他章节安排如下:在第1节介绍QoS本体;第2节讨论UMC的算法细节;第3节给出了执行UMC的组合引擎框架设计方案;第4节给出实验结果和分析;第5节介绍相关工作并与UMC进行比较;第6节总结本文并同时给出在服务组合领域中未来的研究计划.1QoS本体和混合QoS模型语义Web服务研究工作的基础在于创建领域相关的本体,用来明确地描述概念和概念之间的关系从而为参与的智能主体能够自治地完成相应任务提供必要的知识基础.联盟(worldwidewebconsortium,W3C)为此提出了Web本体语言(webontologylanguage,OWL)[17]用来对Web上的资源进行语义描述,另外提出了OWL-S(OWLserviceontology)[18]基于OWL并用来对Web服务进行语义建模.本文提出的OWL-S-QoS本体扩展自OWL-S,从而确保该本体能够与其他遵从OWL-S标准的Web服务本体进行无缝解释和融合.1.1顶层本体通常情形下,3类智能主体将会参与到QoS感知的语义Web服务组合过程中:智能客户主体、服务组合引擎和服务注册中心.智能客户主体负责转达客户需求、偏好以及完成一部分的QoS测量工作(提供反馈信息),服务组合引擎接收来自客户和服务注册中心的相关信息完成决策过程,服务注册中心负责收集来自服务提供商和客户反馈的QoS信息.为了使上述过程能够自治地执行,需要定义一个QoS顶层本体,用来描述相关的概念以达到丰富相关主体知识的目的.图1给出了该本体.中国科学E辑:信息科学2008年第38卷第10期1699图1OWL-S-QoS顶层本体图1中虚线框内的概念为OWL-S定义的顶层概念.在该本体中,根概念是QoS描述,所有的QoS属性均为此概念的子概念.QoS描述可分为不可测量的QoS和可测量的QoS两类,其中不可测量的QoS拥有其描述(关于服务组合的研究一般不考虑这种QoS,在本文下面的叙述中如果不加说明QoS均指可测量的QoS),每个QoS属性拥有一个特征,成本型和效益型是2种不同的属性特征.成本型的属性其值越小表明其质量越优,反之,效益型的属性其值越大其质量越优.另外,每个QoS属性都有其自身的度量方式,使用度量方式可以得到该属性的值,该值可为实数、区间数或语言型数据,每个QoS值还拥有与其对应的单位(链接至现有的单位本体).1.2中层本体QoS中层本体中主要定义了QoS属性,且这些属性均继承QoS描述根概念.本文提出了一种确定型和不确定型描述相结合的混合QoS模型来增强现有模型的语义描述能力.下面以5种常见的QoS属性为例加以说明(度量方法见表1).表1混合QoS模型定义示例价格(price)wsisPPP=+可用性(availability)wsr/ATn=响应时间(responsetime)wsws1ws2wsws1ws2ws[min(,,,),max(,,,)]nnTtttttt=……可靠性(reliability)ws11111111[,,],,nnnnlmulmuiiiiiiiiiiRaaaaaannnn====⎡⎤==⎢⎥⎢⎥⎣⎦∑∑∑∑声誉(reputation)()1WSrepRatingCoWSninαβ==×+×∑杨放春等:混合QoS模型感知的语义Web服务组合策略17001)价格(wsP):价格是一个服务请求者在访问服务时需要的开销.其中wsP表示访问服务的总价格,tP是货品交易(trade-off)的价格(如机票),sP是Web服务的软件(software)执行价格.例如:在一个机票预定服务中,tP将包括机票费用和快递费用等,sP为机票预订服务提供商收取的软件服务费用.此外客户可能需要额外缴纳的一些费用,如网络使用费、银行手续费等,但是这些与Web服务本身无关,因此本文给出的价格定义不考虑这些属性.2)可用性(wsA):可用性是Web服务可访问的概率.其中wsA表示服务的可用性,rT表示在一定的时间区间内该服务可用(ready)的次数,n表示在此时间段内的访问总次数.3)响应时间(wsT):响应时间表示从客户的请求消息发出到昀终服务执行结束所需的时间开销.以往,响应时间常以一定时间段内的服务访问时间的平均值进行计算[4,10,12].近来,文献[8,9,11]将区间型描述法引入到Web服务QoS描述中来,以增加QoS属性描述的准确性和显示更为丰富的QoS信息.本文使用区间型描述法定义响应时间,因为响应时间属性的本质是动态性,在不同的时间和不同的网络状况下访问同一个服务往往会有较大的响应时间差别.传统的模型会掩盖这种差别,例如:服务1和2具有相同的响应时间均值200ms,但Tws1=[100ms,350ms],Tws2=[80ms,230ms].在这种情形下,如果响应时间按照平均法进行定义,2个服务的响应时间质量没有任何区别,但是按照本文的定义可以明显看出在以往的历史中,服务2的时延表现较之服务1更为稳定(服务2的响应时间在150ms的范围内波动,而服务1的响应时间在250ms内波动),且服务2的昀大和昀小时延均优于服务1,所以可以得出服务2的响应时间在某种程度上优于服务1.在度量定义中,twsi为某次服务访问的响应时间.4)可靠性(wsR):表示Web服务正确执行其功能的能力.它是对服务质量的一个综合评判,其计算数据来自于客户访问服务后的反馈.这种反馈以往简单地被定义为精确值(如在1至10的整数中选择一个作为可靠性的值).但是这种定义方式不够严谨并不能表达客户的真实意愿,因为客户不是QoS专家,其对于某些属性的语义必定存在理解上的困难.在访问服务之后,客户对于服务的整体QoS至多有一个模糊的“感觉”,例如“较高”.从模糊理论的角度来看,在这种情形下任何一个精确的数据都不能作为客户意愿的准确表达.所以建议以语言型的数据描述服务的可靠性指标.在一次服务访问结束后,服务请求者为服务的可靠性打一个模糊的分数,该分数是集合(高,较高,一般,较低,低)中的一个元素.虽然语言型数据具有正确合理的描述能力,但是却不易计算,所以为了后续综合决策的需要将语言数据量化.常用的量化方法是将模糊打分映射为相应的三角模糊数(triangularfuzzynumber,TFN)[19],如[al,am,au].其中al,am和au分别表示三角模糊数的下界、核和上界值.三角模糊数的取值一般需要由领域专家(QoS专家和客户专家)给出.由其度量定义可看出,Rws被定义为一段时间内客户反馈(TFN)的平均值.5)声誉(WSrep):作者在以前的工作中介绍了一个改进的Web服务声誉模型—WSrep[20].WSrep集成了主观的客户打分和客观的对于QoS广告信息的可信性(credibilityofwebser-vice-CoWS)的判断(基于Bayes学习理论),用来减少恶意打分攻击带来的影响.其中α和β为平衡因子,n为一定时间段内服务访问的总次数(i表示某次访问).显而易见,在这5种服务质量属性中价格和响应时间为成本型数据,而其他3种均为效益中国科学E辑:信息科学2008年第38卷第10期1701型属性.对于QoS概念的详细介绍参见文献[4,8~11,21,22].2UMC本节介绍UMC算法的细节.先讨论服务组合的工作流模型,然后介绍UMC