优化理论与方法
全局及个性化web服务组合可信度的动态规划评估方法
摘要：随着Internet的快速发展,web服务作为一种软件构造形式其应用越来越广泛。单个web服务无法满足日益复杂的用户需求,web服务组合有效地解决了这个问题。然而,随着功能相似的web服务实例的不断出现,如何选择可信的web服务组合成为了人们关注的热点。服务选择依赖于web服务组合的评估结果,因此,本文主要从web服务组合着手,对其可信性进行研究,提供一种可信web服务组合评估方法。：针对web服务组合的全局及个性化问题,提出了基于全局的个性化web服务组合可信评估方法。从全局角度动态地调整评估模型;同时引入用户业务关注度来描述原子web服务对服务组合可信性的影响程度;结合前文的度量及评估方法,构建一个全局的个性化服务组合可信评估模型;并分析了模型的相关应用,给出了改进的动态规划模型。
关键字：web服务组合可信评价；全局个性化；动态规划；
0.引言
随着软件系统规模的日趋复杂，运行环境的不断开放，软件的可信性要求日益增加，可信软件成为了研究的热点。据《中国互联网发展状况统计报告》统计显示，截至2014年12月底，我国网民数量突破8亿，全年新增网民5580万。互联网普及率较上年底提升4个百分点，达到38。3%。因此，随着Internet 的广泛应用和网络技术的快速发展，面向服务的软件体系结构（SOA）作为一种新型的网络化软件应用模式已经被工业界和学术界广为接受。同时，网民对互联网电子商务类应用稳步发展，网络购物、网上支付、网上银行和在线旅游预订等应用的用户规模全面增长。因而，对web服务的可信性要求更高。单个web服务的功能有限，往往难以满足复杂的业务需求，只有通过对已有web服务进行组合，才能真正发挥其潜力。在现有的web服务基础上，通过服务组装或者Mashup方式生成新web服务作为一种新型的软件构造方式，已成为近年的研究热点之一。web服务组合并不是多个原子web服务的简单累加，各原子web服务之间有着较强的联系。因此对web服务组合的可信需求更高。目前大量的研究工作着重于如何实现原子web服务间的有效组合，对服务组合的可信评估研究较少。如今，随着web服务资源快速发展，出现了大量功能相同或相似的web服务，对web服务组合而言，选择可信的web服务变得越来越难。在大量的功能相似的原子web服务中，如何选出一组可信的web服务组合，成为了人们关注的热点问题。本文将从web服务组合着手，对其可信性进行研究，旨在提供一种可信web服务组合评估方法，为web服务组合的选择提供依据。web服务组合的可信度主要包括以下三个部分：
1）基于领域本体的web服务可信度量模型。
2）基于偏好推荐的原子web服务可信评估方法。
3）基于全局的个性化web服务组合可信评估方法。
研究思路：
本文主要研究基于全局的个性化web服务组合的可信评估方法，其研究思路可以大致如下：基于领域本体的web服务可信度和基于偏好推荐的原子web 服务可信评估方法。针对web服务组合的四种基本组合结构模式，主要研究如
何从全局角度动态地调整评估模型；同时引入用户业务关注度来表达原子web 服务对服务组合可信性的影响程度（从用户角度）；应用动态规划的方法构建一个全局的个性化web服务组合可信评估模型，最后给出一个代表性的数值算例。
文章结构布局：
1节将主要介绍几种不同的服务组合模式，并对进行分析，引入基于全局的问题，并给出一种解决方法；2节将主要介绍如何构建一个全局的个性化服务组合评估模型，并根据用户的业务关注度，获得各原子web服务对服务组合的可信性影响权重，进而获得可信评估值。3节将主要介绍如何应用此模型，并给出了一个最优服务组合选择方法（动态规划模型）。
1.基于组合全局的调整策略
基于全局的评估策略，是指从全局角度计算服务组合的可信评估值。目前已有的全局评估模型，基本都是采用原子服务属性值汇总，再加权评估的方式，没有考虑到组合服务的业务逻辑关系（服务组合模式）。在本节的全局策略中，将充分考虑服务组合方式对服务组合可信性的影响，为可信web服务组合评估提供一种更可信的全局策略。首先，介绍基本的服务组合模式；接着，分析不同模式的影响；最后，给出考虑全局的调整方法。服务组合流程可以被定义为一组相互关系的任务（或业务），这些任务具有各种不同的功能，并通过原子服务完成。在常见的服务组合应用中，原子web服务通过一定的组合模式构成服务组合。研究者提供了多种原子web服务组合模式，提WS4BPEL支持多种组合模式。但实质上都可以分解为顺序模式、分支模式、并行模式和循环模式的有限递归嵌套，因此本文仅讨论这4中模式。
1）顺序模式相当于程序结构中的顺序结构，服务组合中的服务根据业务被分解为多个阶段。每个服务按顺序依次完成其业务功能。
2）分支结构相当于程序结构中的分支结构，多个分支中根据一定的判断条件选择一条分支执行。在计算该模式下的属性值时，由于无法判断具体运行那条，一般采用统计方式估算，即根据可能执行的概率计算平均值。
3）并行模式相当于程序结构中的并行结构，多条分支同时进行。一般用于为下一阶段的业务准备多个初始条件。这些任务之间相互独立，全部完成后，才能进入下一阶段。
4）循环模式相当于程序结构中的循环结构，一条路径被重复循环地执行次。可以看作顺序模式的一个复合结构，即把这条路径展开Z次执行。在进行可信评估时，需要考虑执行的次数。
由上面四种结构组合出来的服务组合网络有多种形式，如何从中识别出关键的路线成了研究的关键步骤；关键路径：服务组合业务流程中执行时间最长的那一条路径。关键路径上的业务称为关键任务，其他任务称为非关键任务。其中关键路径的识别问题类似求解最短路径问题（目标函数转化为最大），可采用E.W. Dijkstra提出的T、P标号算法或L.R.Ford提出的Ford算法。
2．基于全局的个性化web服务组合可信评估模型
2.1构建评价模型步骤
目前大部分关于服务组合评估的研究中，基本都是采用的全局一致化的评
