（计算机软件与理论专业论文）一种支持qos约束的web服务组合的研究.pdf

摘要 随着w e b 服务数量的不断激增，同一个服务会有许多w e b 服务来提供，用户需要 更有增值更丰富的服务，而不是功能单一的孤立的w e b 服务。因此，合成具有高质量 的w e b 服务将成为需要解决的焦点问题。客户将会面临这样种难题，要在成千上万 个可能的组合规划中选择或创建一个满足他们q o s 需求的规划。典型的与w e b 服务相 关的q o s 属性有执行代价，执行时间，可用性，成功执行率，声誉，使用频率等。从 ， 工程的角度来看，生成一个满足客户q o s 需求的组合规划是一个耗时的优化问题。 本文在现有w e b 服务组合的基础上，深入研究了一种支持q o s 约束的w e b 服务组 合。在综合比较了d a m l - q o s 本体和w s m o q o s 本体模型的优缺点后，对o w l - s 进 行了扩展，构建了具有语义描述能力的q o s 本体模型：o w l - s q o s 本体，该模型具有 良好的扩展性并支持多种度量方式，能更好地满足服务描述的需求，并能够实现向前兼 容。根据w e b 服务描述模型，构建了基于o w l s q o s 本体的w e b 服务发现模型，实 现了w e b 服务四级过滤三级匹配算法，该算法是一个自顶向下逐步精化的过程，不但 能够应对用户、领域的多种需求，并且还可以把虚假发布信息对服务q o s 评价影响降 低到最小。针对上述组合优化问题，提出了一个结合禁忌搜索和模拟退火技术的w c b 服务组合算法以及支持该算法的架构，该算法以一种不违反q o s 约束的优化方式把高 质量的w e b 服务自动分配给组合模式中的原子过程，并以混合的元启发式搜索为特征， 结合禁忌搜索和模拟退火技术，不但可以找到满足约束的组合规划而且还能减少搜索规 划所需的计算负担。该架构支持以用户友好方式自动生成支持q o s 约束的w e b 服务组 合规划，由一个组合代理和执行规划优化器所组成，组合代理用于发现候选的w e b 服 务，执行规划优化器用于实现提出组合算法。 在模拟环境下，通过与整数规划方法的比较，我们验证了该组合算法有很好的性能。 关键字：w e b 服务，q o s ，服务发现，服务组合 a b s t r a c t w i t ht h ei n e r e a s e m e n to fw e bs e r v i c e s ，m a n yw e bs e r v i c e sw i l lo f f e rt h es a m es e r v i c e s ， a n dt h ec l i e n t sw i l ld e m a n dm o r ev a l u e sa d d e da n di n f o r m a t i v es e r v i c e sr a t h e rt h 锄t h o s e o f f e r e db ys i n g l ea n di s o l a t e dw e bs e r v i c e s a st h er e s u l t ，t h ep r o b l e mo fs y n t h e s i z i n gw e b s e r v i c e sw i ml l i g hq u a l i t yw i l lb er a i s e da sap r o m i n e n ti s s u e t h ec l i e n t sw i l lf a c et h et r o u b l e o fc h o o s i n go rc r e a t i n gc o m p o s i t i o np l a n s ，a m o n gn u m e r o u sp o s s i b l ep l a n s ，t h a ts a t i s f ym e i r q u a l i t y - o f - s e r v i c e ( q o s ) r e q u i r e m e n t s t y p i c a lq o sp r o p e r t i e sa s s o c i a t e dw i t haw e bs e r v i c e a r ee x e c u t i o nc o s ta n dt i m e , a v a i l a b i l i t y , s u c c e s s f u le x e c u t i o nr a t e ，r e p u t a t i o n ，a n du s a g e f r e q u e n c y i ne n g i n e e r i n gp e r s p e c t i v e ，g e n e r a t i n gt h ec o m p o s i t i o np l a nt h a tf u l f i l l sac l i e n t s q o sr e q u i r e m e n t si sat i m e - c o n s u m i n go p t i m i z a t i o np r o b l e m b a s e do nt h ee x i s t i n gs e r v i c ec o m p o s i t i o n ，w e bs e r v i c ec o m p o s i t i o ns u p p o r t i n gq o s c o n s t r a i n t si ss t u d i e di nt h i sp a p e r i no r d e rt oc a r r yo u tt h es e m a n t i cd e s c r i p t i o nt oq o so f w e bs e r v i c e ，t h eo w l - si se x t e n d e d ，a n dq o so n t o l o g ym o d e lw i t ht h ea b i l i t yo fs e m a n t i c d e s c r i p t i o ni sc o n s t r u c t e db yc o m p a r i n gt h ea d v a n t a g e sa n dd i s a d v a n t a g e so fd a m l q o s o n t o l o g ya n dw s m o q o so n t o l o g ym o d e l o w l - s o o so n t o l o g ym o d e lh a sg o o d e x p a n s i b i l i t ya n ds u p p o r t sf o rav a r i e t yo fm e a s u r e m e n tm e t h o d s i tc a nm e e tt h en e e d so f s e r v i c ed e s c r i p t i o nb e t t e r , a n di si nl i n e 、i t l li n t e r n a t i o n a ln o r m sa n da c h i e v e sf o r w a r d c o m p a t i b i l i t y a no w l s q o s - b a s e do n t o l o g yw e bs e r v i c ed i s c o v e r ym o d e li sc o n s t r u c t e d ， a n dt h r e el e v e l sm a t c h i n ga l g o r i t h mo fw e bs e r v i c ei si m p l e m e n t e da c c o r d i n gt ow e bs e r v i c e d e s c r i p t i o nm o d e l t h i sa l g o r i t h mi sat o p - d o w np r o c e s sa n dr e f i n e db ys t e p s ，n o to n l ym e e t s v a r i o u sn e e d so fu s e r si ns o m ef i e l d s ，b u ta l s od e c r e a s e st h ei n f l u e n c eo ff a l s ep u b l i s h e d i n f o r m a t i o nf o rs e r v i c e s q o se v a l u a t i o nt ot h el o w e s tl e v e l f o rt h ec o m b i n a t o r i a l o p t i m i z a t i o np r o b l e m s ，aw e bs e r v i c ec o m p o s i t i o na l g o r i t h mc o m b i n e do ft a b us e a r c ha n d s i m u l a t e da n n e a l i n ga n das t r u c t u r es u p p o r t e dt h i sa l g o r i t h ma r ep r o p o s e d t h i sa l g o r i t h m a s s i g n sah i g h - q u a l i t yw e bs e r v i c et ot h ea t o m i cp r o c e s so fc o m b i n a t i o nm o d ei na n o p t i m i z a t i o na p p r o a c hw h i c hn o tv i o l a t eq o sc o n s t r a i n t s ，f e a t u r e dm i x e dm e t a - h e u r i s t i c s ，a n d c o m b i n et a b us e a r c hw i t hs i m u l a t e da n n e a l i n g i tc a nn o to n l yf i n dac o m b i n a t i o np l a n n i n gt o m e e tt h ec o n s t r a i n t s , b u ta l s or e d u c et h ec o m p u t a t i o n a lb u r d e no fs e a r c h i n gp l a n n i n g t h e a r c h i t e c t u r e s u p p o r t s t o g e n e r a t eq o s - o r i e n t e d w e bs e r v i c e c o m b i n a t i o n p l a n n i n g - 1 1 - a u t o m a t i c a l l yi nf r i e n d l yw a yt ob s e q s ，a n di t i sc o m b i n e do fac o m b i n a t i o na g e n ta n d i m p l e m e n t a t i o np l a n n i n go p t i m i z e r t h ec o m b i n a t i o na g e n ti sf o rt h ec a n d i d a t ew e b s e r v i c e s d i s c o v e r ya n dt h ee x e c u t i o np l a no p t i m i z e ri m p l e m e n t st h ep r o p o s e dc o m p o s i t i o na l g o r i t h m g o o dp e r f o r m a n c eo ft h i sc o m b i n a t i o na l g o r i t h mi sd e m o n s t r a t e d ，c o m p a r i n gw i t ht h e i n t e g e rp r o g r a m m i n ga p p r o a c hi ns i m u l a t e de n v i r o n m e n t k e yw o r d s ：w e bs e r v i c e , q o s ，s e r v i c ed i s c o v e r y , s e r v i c ec o m p o s i t i o n 一1 1 1 - 西北大学学位论文知识产权声明书 本人完全了解西北大学关于收集、保存、使用学位论文的规定。学校 有权保留并向国家有关部门或机构送交论文的复印件和电子版。本人允许 论文被查阅和借阅。本人授权西北大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存 和汇编本学位论文。同时授权中国科学技术信息研究所等机构将本学位论 文收录到中国学位论文全文数据库或其它相关数据库。 保密论文待解密后适用本声明。 学位论文作者签名：上移杨 指导教师签名：堋气( p i i 2 0 o 年石月2 多日2 。匆年多月乃日 西北大学学位论文独创性声明 本人声明：所呈交的学位论文是本人在导师指导下进行的研究工作及 取得的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，本 论文不包含其他人已经发表或撰写过的研究成果，也不包含为获得西北大 学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对 本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名：卫椐格 2 0 o 年莎月矽日 西北大学硕士学位论文 1 1 研究背景及意义 第一章绪论 w e b 服务在各个领域的广泛应用使互联网发生了质的飞跃，不仅为不同部门间的通 信和不同领域间的信息活动提供了一个基础平台，同时也使各部门、企业间的竞争加剧， 部门及企业要想在这种激烈的竞争中维持生存并不断取得进步，就必须能够对客户需求 以及外部竞争的变化做出快速而灵活的响应。如何更好地保存先前的投资，充分利用已 有资源，整合出符合用户需求的、有效的增值服务，已成为各个部门、企业迫切需要解 决的问题。为了分散和简化应用逻辑，提高w e b 服务的可重用性，单个的w e b 服务不 能过于复杂，然而现实生活中的应用一般都比较复杂，如一个旅行服务通常由订票服务、 酒店服务以及景点服务等组合而成。当单个w e b 服务所提供的有限功能不能满足用户 的需求时，就需要将多个功能简单的服务进行组合，形成功能更强大的增值服务，以满 足用户的更高需求【l 】。因此，工业界和学术界都希望能够通过组合现有的w e b 服务创造 出新的服务功能，这样既保护了各部门及企业的先前投资，又整合出了新的功能服务， 为部门和企业的发展带来了希望，这样w e b 服务的真正潜力才能发挥出来。所以，w e b 服务组合就成了解决现实中w e b 任务中b 2 b 应用问题的重要技术之一，其实现问题也 成为了工业界和学术界的重要研究内容。 随着w e b 服务技术的不断发展及其应用范围的逐步扩大，越来越多的企业和组织 陆续不断的将其业务功能和流程封装成标准的w e b 服务发布到i n t e r n e t 上，致使i n t e r n e t 上的服务数量呈现指数增长趋势。这些由w e b 服务提供者发布的w e b 服务中，不可避 免地出现大量具有相同功能但不同q o s 属性的服务，服务请求者则要从中快速地发现 满足其特定需求和q o s 约束的w e b 服务。然而，这些日益增多的w e b 服务有成千上万 种不同的组合方案可以组合出具有相同功能但不同q o s 属性的服务，如何从这些方案 中选出最优方案，是w e b 服务组合必须解决的一个关键问题，否则将影响了服务组合 应用的进一步推广。由于用户对服务组合所提的q o s 约束将成为构建整个组合流程的 全局限制，在支持q o s 约束的服务组合中，具有全局q o s 约束的服务组合占相当大的 比例；同时由于用户所关心的领域和q o s 属性不同，用户的需求( 包括功能性需求和非 功能性需求) 也随之不同，而且随着服务应用的深入和领域范围的不断扩大，与服务相 关的q o s 属性及用户需求也会不断变化和扩展。因此，只有根据用户需求的变化灵活 第一章绪论 地选择不同的服务组合方案，才有可能最大程度地提高w e b 服务应用的深度和广度。 因此，根据w e b 服务发展现状以及当前的研究与应用情况，对服务提供者和服务 请求者的q o s 进行描述，在此基础之上发现w 曲服务、匹配满足用户需求的最优服务， 并根据用户对q o s 的约束进行w 曲服务组合，是一个非常有学术价值和现实意义的问 题。 1 2 研究现状分析 支持q o s 约束的w e b 服务组合包含许多关键技术，本文主要研究以下三个方面内 容：q o s 信息描述、候选w e b 服务发现及匹配算法和支持q o s 约束的w e b 服务组合算 法及其支撑架构。 1 、q o s 信息描述 目前，对q o s 信息描述模型的研究还不是很多，研究方法和侧重点各不相同，比 较典型的有d a m l - q o s 本体模型和w s m o 0 0 s 本体模型。 文献1 2 d 0d a m l - q o s 本体模型关注的是模型整体结构的划分，它将q o s 本体分为 q o s 配置层、q o s 参数定义层和q o s 度量层三个不同的层次。该模型介绍了有关q o s 参数的定义域，并规定了度量的标准，但没有考虑到度量的方式，也没有对q o s 参数 进行详细的描述。文献 3 】中w s m o q o s 本体模型关注每个q o s 参数，详细描述了q o s 参数的每一个属性。该模型认为各个q o s 参数之间是平等的关系，没有依赖关系且每 一个度量值都是单值，因此也没有考虑到q o s 属性之间的关系，且度量方式单一，不 支持模糊值、区间型值和语言型值。 2 、候选w e b 服务发现及匹配算法 目前，国内外关于服务发现的匹配算法讨论的还是比较多的，如文献 4 6 】分别提出 不同的服务匹配算法，文献 7 提出的匹配算法，基本上都是从功能性和接口上进行匹 配，这种匹配方法的效率较低，而且本体库的规模越庞大，进行大规模搜索时消耗的时 间也就越多。文献【8 1 0 】只考虑了q o s 的数值匹配，没有考虑到q o s 参数的语义匹配和 区间匹配。还有一些主要对候选服务的q o s 参数进行简单归一化，然后进行加权排序 的非功能匹配，这些方法一定程度上考虑了服务的q o s 属性，能为请求者选择q o s 较 好的服务，但它没有考虑到不同请求者、领域对o o s 的需求会有所不同，所以难以应 对请求者的多样化需求。因此，在进行服务匹配与服务定位时，要充分考虑不同用户对 服务的不同需求，以体现w e b 服务的个性化。 2 西北大学硕士学位论文 3 、支持q o s 约束的w e b 服务组合算法及其支撑架构 在研究支持q o s 约束的w e b 服务组合内容中，有四个关键的问题： ( 1 ) 如何对一个w e b 服务的q o s 信息进行描述。q o s 信息描述是w e b 服务描述中很 关键因素，也是服务发现的基础。 ( 2 ) 如何定义一个适合组合服务的q o s 模型。q o s 模型是w - e b 服务组合研究的基础， 模型的属性是根据组合服务的特点来描述的； ( 3 ) 如何根据w e b 服务描述和已定义的q o s 模型，为组合服务选取合适的候选w e b 服务。 ( 4 ) 如何提出一个高质量、高效率的满足用户q o s 约束的w e b 服务组合算法以及支 撑该算法的实现架构。 对q o s 信息描述前面己讨论过。目前，对o o s 模型的的研究还比较多，出现了不 同的q o s 模型。z e n g 等人在文献 1 l 】中，提出了一种q o s 模型，包括执行代价、执行 时间、可靠性、有效性和信誉等5 个质量标准；文献【1 2 】提出的w e b 服务q o s 属性包 括了w e b 服务价格、执行时间、信誉度、执行成功率、可用性，它从另一面描述了w e b 服务的非功能特性。c a r d o s o 在文献 1 3 中提出了一种基于现有工作流模型的组合服务 q o s 评价模型，但是它对组合规划的q o s 评价还不够，不能满足用户的q o s 需求。虽 然现在的q o s 模型不少，但是只关注于对一般服务的质量评价，并不能客观、全面地 反映组合服务的质量。 到目前为止，对w 曲服务组合算法的研究已经很多了，文献 1 2 】提出了一个整数规 划算法来优化组合规划，然而该算法的时间复杂度却成指数增加，服务组合性能也趋于 恶化。文献 1 4 d p 范小芹根据随机型离散事件系统唯一的动态控制方法一马尔可夫决 策过程( m d p ) ，提出了随机q o s 感知的可靠w 曲服务组合算法。文献 1 5 1 6 采用了遗传 算法来减少组合时间，在一定程度上解决了服务选取问题，但是并没有注意到遗传算法 本身的特性所带来的高效性，还不能处理w e b 服务组件的各种执行方式，而且对支持该 w 曲服务组合算法的架构也没有进行讨论。张成文等在文献【1 7 中对遗传算法进行了改 进，对算法的编码方式进行了扩充，虽然提高了组合的效率，但是仍然没有考虑到算法 的适应性，只是在服务选择的层面上考虑y q o s 属性。代钰等在文献 1 8 中提出的组合 服务的方法，虽然具有很高的组合成功率，但是无法保证组合服务的可组合性，即组合 成功的服务可能无法正确运行。 3 第一章绪论 1 3 论文研究的主要内容 本文的工作主要围绕支持q o s 约束的w e b 服务组合而展开，主要研究内容及贡献 如下： ( 1 ) 提出了一种q o s 本体模型。在综合比较了d a m l q o s 本体和w s m o q o s 本体 模型的优缺点后，本文以o w l - s 为参考，对其中的s e r v i c ep r o f i l e 进行了扩展，构建 了具有语义描述功能的q o s 本体模型o w l - s q o s 本体，该模型具有良好的扩展性， 并支持多种描述q o s 属性的度量方式，能更好地满足服务描述的需求。另外， o w l - s q o s 本体是对o w l - s 服务本体的标准扩展，符合国际规范，能够实现向前兼 容。 ( 2 ) 提出了一种可扩展的多维q o s 模型，并对数值型和区间型两种不同的q o s 参数 表达方式，提出各自不同的量化方法及q o s 整体评价方法。 ( 3 ) 提出了一个基于o w l s q o s 本体的w e b 服务发现模型以及基于该模型的服务 匹配算法。首先，用户根据有关该领域的一些不太准确的相关关键词在u d d i 中搜索， 获取所需的服务；然后，将获取的服务集依次与服务基本描述进行匹配，匹配成功的服 务集再与服务功能进行匹配；最后，将与功能匹配合格的服务集进一步与具有q o s 的 非功能属性进行匹配，得到一个满足用户需求的服务集。该算法不但能够应对用户和领 域的多种需求，还可以把虚假发布信息对服务o o s 评价的影响降低到最小。 ( 4 ) 提出了一种支持q o s 约束的w 曲服务组合算法以及支持该算法的架构。该算法以 一种不违反q o s 约束的优化方式把高质量的w e b 服务分配给组合模式中的原子过程。该 算法以混合的元启发式搜索为特征，结合禁忌搜索和模拟退火技术，不但可以找到满足 约束的组合规划而且还能减少搜索规划的计算负担，禁忌列表和以概率移动到差的规划 使算法能够很快找到满足约束的规划。该算法的支撑架构支持以用户友好方式自动生成 面向q o s 的w 曲服务组合规划，由一个组合代理和执行规划优化器所组成，组合代理用 于发现候选的w 曲服务，执行规划优化器用于实现组合算法。 ( 5 ) 通过实验表明所提出的算法在支持q o s 约束的w e b 服务组合中具有良好的性能。 1 4 论文的组织结构 第一章绪论。主要介绍了本文的研究背景及意义、国内外研究现状以及本文主要 研究内容和组织结构。 4 西北大学硕士学位论文 第二章w e b 服务组合概述。主要介绍了w e b 服务组合的概念、相关技术以及的 w e b 服务组合的主要方法。 第三章q o s 描述信息与q o s 计算。首先介绍了o w l - s 本体模型、d a m l - q o s 本 体模型和w s m o q o s 本体模型这三种典型模型，以及具有语义描述功能的q o s 本体模 型o w l 广s q o s 本体；然后介绍了服务组合的基本知识、q o s 属性的概念以、单个 q o s 属性计算以及q o s 整体评价；最后介绍了组合服务的q o s 计算及目标函数设计。 第四章基于o w l - s q o s 本体的候选w c b 服务发现。首先介绍了w c b 服务描述模 型和基于q o s s q o s 本体的w e b 服务发现模型，然后介绍了基于该服务发现模型的 w e b 服务匹配算法一基本描述的匹配、i o p e 匹配和q o s 匹配，最后使用本文提出的 算法进行仿真分析，对试验结果进行分析比较。 第五章支持q o s 约束的w e b 服务组合算法及支撑架构。首先介绍了w e b 服务组 合和架构的基本思想，然后详细介绍了支持q o s 约束的w e b 服务组合算法及其支撑架 构，最后通过实验我们验证了该算法的有效性。 总结与展望，本章主要总结了本文的研究内容，并阐述了未来的研究方向。 5 第二章w e b 服务组合概述 第二章w e b 服务组合概述 2 1w e b 服务组合概念 w e b 服务组合是利用i n t c r n e t 上已有的w e b 服务，根据最终用户或增值服务开发商总 的应用需求，按照一定的规则自动选择符合要求的单个w e b 服务，从而组成满足用户需 求的服务流程，通过流程中各服务的协同来实现增值服务，以便完成用户的服务请求。 这种增值服务主要体现在新的服务满足特定需求的能力，以及可以提供更高的可用性和 q o s 保障。 w e b j 曼务的价值在于服务重用，重用的目的是使服务增值。w e b n 艮务组合是各个小粒 度的w e b 服务相互之间通信和协作来实现大粒度的服务功能；通过有效地联合各种不同 功能的w e b 服务，组合服务开发者可以解决更为复杂的问题，达到服务增值的目的。 w e b 服务组合的研究按照组合的时机可划分为两种：静态组合与动态组合。静态组 合是事先对客户的需求进行预测，以此建立对应的组合好的服务，并提供给用户直接调 用。动态组合是指在系统运行过程中选择和调用所需的组件服务，并将之组合出满足用 户需求的服务供给用户使用。此外，有些学者还从另外一个角度对其进行了划分：强制 组合和选择式服务组合。强制式服务组合要求所有的子服务必须按照特定的规则正确执 行并产生满意的结果，才能保证组合服务的正确执行；而选择式服务组合则无须这些规 则，且子服务间的依赖性较弱。 本文将w e b 服务分为原子服务、组件服务和组合服务。原子服务是不依赖于其他服 务的服务，一个不可再分解的为更细粒度的服务；组合服务是指由一个或多个原子服务 或组合服务组合而成的服务；组件服务是为组合服务提供子功能的服务。服务组合就是 将小粒度服务组合为大粒度服务以实现服务的增值，组合服务也可以参与更高层次的组 合，从而成为更高层次的组合服务的组件服务。组合服务的功能是由各个组件服务协同 完成的。因此，可以说，组合服务是所有组件服务的消费者，每个组件服务又都是组合 服务的提供者。 2 2w e b 服务组合的分类 服务流程是由若干服务组合而成的，服务流程的创建过程其实就是服务组合的过 程，因此w e b 服务组合是服务流程管理中的一个关键问题。本文主要介绍三个具有代表 6 西北大学硕士学位论文 性的服务组合方法【1 9 】：基于工作流的服务组合【2 0 2 1 ，2 2 2 3 1 、基于触规划的服务组合和基于 图搜索的服务组合【2 4 2 5 2 6 2 7 ，2 8 2 9 1 ，其中第一个实现服务流程的手工生成，后两个实现服务 流程的自动生成。 2 2 1 基于工作流的w c b 服务组合 在很多情况下，服务组合与工作流有很大相似性，也具有流程逻辑、控制流、数据 流等，但两者仍然存在一定的差异，如表2 1 所示： 表2 1 工作流与服务组合的比较 在建模语言方面，目前工作流主要采用x p d l 进行流程描述，而服务组合则大多采 用b p e l 等作为描述语言。在应用类型方面，工作流支持多样化的应用类型，如e j b 、支 撑表单和w c b 服务，而服务组合中w e b 服务是惟一的应用类型。在应用绑定方面，工作 流需要进行参数映射和静态应用绑定，而服务组合不但支持静态绑定也支持动态绑定。 在参与角色方面，工作流包括用户、角色以及组织三种类型，而组合服务则包含了服务 消费者和服务提供者两种类型。对涉及的范围而言，工作流是企业内部或跨企业的局域 网，而服务组合则是跨越多个企业的整个网络。虽然两者之间存在上述的差别，但是工 作流建模方法为服务的组合提供了良好的实现基础。 目前，有许多研究项目采用基于工作流的组合方法，例如，文献 2 0 中e f l o w 是描 述、执行以及监控服务集成的工作流平台，它是通过解释执行模型来实现服务组合的， 其系统设计和实现具有明显的工作流管理系统的特点。b p e l 4 w s 是w e b 服务商业流程 执行语言，提供了组合工作流框架，其执行过程是一种活动组合流程，主要作用是对可 执行过程和抽象过程进行建模 2 3 】，完成w e b 服务调用、数据操作、故障抛出等工作的不 同活动，从而创建出复杂的流程。 对工作流技术的长期研究和经验积累，使得基于工作流的w e b 服务组合方法易于理 解和实现，在运行环境的构造方面也具有较大的优势。但是，由于该组合方法需要大量 7 第二章w e b 服务组合概述 的人工参与，自动化程度不高。因此，服务组合的效率较低。 2 2 2 基于a i 规划的w e b 服务组合 服务组合问题的研究吸引了不少从事流程管理和面向服务计算的专家，他们认为服 务组合问题可以抽象为一个规划问题的自动求解，即给定一个初始状态和目标状态，在 一个服务集合中寻找一条从初始状态到目标状态的服务路径。目前，出现了许多基于a i 的规划的w e b 服务自动组合方法，本文重点介绍以下四种：基于情景演算的w e b 服务自 动组合、基于p d d l 的w c b 服务自动组合、基于h t n 的w c b 服务自动组合和基于定理证 明的w e b 服务自动组合。 ( 1 ) 基于情景演算的w e b 服务自动组合。 情景演算( s i t u a t i o n a lc a l c u l u s ) 是由美国斯坦福大学人工智能实验室麦卡锡于1 9 6 4 年 提出来的用于表示动作和变化的理论。情景演算的思想吸收了有穷自动机状态转移的概 念。在情境演算中，假设世界的所有动态变化是由于动作执行而产生的结果。文献 2 4 】 对基于情景演算的逻辑编程语言g o l o g 进行了扩展，通过提供可重用的高层过程和用户 约束来实现服务的自动组合。 ( 2 ) 基于p d d l 的w e b 服务自动组合 规划域定义语言( p 1a r m i n gd o m a i nd e f i n i t i o nl a n g u a g e ，p d d l ) 是d m cd c r m o t t 等提 出的用于表示规划域和问题的形式化语言【2 5 2 6 1 。该组合方法认为p d d l 与o w l s 具有很 大的相似性，相互之间可以直接映射，因此在进行服务组合时，首先把需要解决的问题 用p d d l 描述，再将o w l 广s 直接转化为p d d l 规划域的描述，然后将p d d l 作为规划器的 输入，从而进行服务的自动组合。基于p d d l 的w e b ) j 艮务自动组合不仅支持贴d a m l s 作为 服务描述语言，而且同样支持w s d l 。 ( 3 ) 基于h t n 的w e b 服务自动组合 层次任务网( h i e r a r c h i c a lt a s kn e t w o r k ，h t n ) 具有任务描述和分解、任务分派、任 务完成的能力以及约束和冲突解决机制，对复杂问题以一种高效的方式进行规划。基于 层次任务网的w c b 服务组合方法是将用户任务分解成越来越小的子任务，直到分解后的 任务是能被单个服务执行的简单任务为止。文献【2 7 通过分层任务网络规划( h t n ) 来实 现服务的自动组合，利用s h o p 2 规划器进行求解，s h o p 2 是通过h t n 方法实现w e b 服务 组合的系统。 ( 4 ) 基于定理证明的w e b 服务自动组合方法 8 西北大学硕士学位论文 定理证明是指利用谓词演算和逻辑推理来解决问题的过程。文献 2 8 r w a l d i n g e r j l 匝 过定理证明详细阐述了服务自动组合的方法，该方法是基于自动化演绎推理和程序综合 的。首先将可获得的w e b 服务和用户需求描述成与经典逻辑相关的一阶语言，然后利用 s n a r k 定理证明器来产生证明过程，证明过程就是w e b 服务组合过程的体现，最后可以 从该证明过程中将服务组合描述提取出来，这样就间接地得到了w e b 服务的组合过程。 从以上介绍的几种基于a i 规划的w c b 服务组合来看，它们都基于某种形式化方法或 者推理系统，需要对服务进行预处理和形式化转换，用户使用起来不易掌握，方法的复 杂度较高，特别是规划空间变得越大时，这类方法的复杂度会随之显著提高。目前，还 未出现真正使用基于a i 规划的w e b 服务自动组合系统。在利用a i 规划实现w e b 服务自动 组合之前，还有许多问题有待解决，如方法的复杂度、可用性，以及在服务自动组合过 程中如何考虑用户偏好、约束等。 2 2 3 基于图搜索的w e b 服务组合 在基于图搜索的服务组合方法中，用有向图表示服务注册库中服务与服务之间的关 系，服务组合的过程则转化为在对有向图的遍历中，寻找从输入到输出或者从输出到输 入的可达路径。 目前，基于图搜索的服务组合方法有些是将整个服务注册库构成的图作为搜索空 间，在搜索过程中也没有较好的机制来避免循环搜索，因此，这种组合方法在服务数量 比较多、服务间关系比较复杂时性能较低。文献 2 9 提出了一种为服务注册库中所有服 务的输出建立一个倒排索引的机制以及基于该机制的服务发现算法。虽然该方法利用倒 排索引的优势，在很大程度上缩小了搜索范围，能够快速准确地发现目标服务，但是它 没有把w e b 服务的o o s 问题考虑进去，最终只能得到满足用户基本需求的服务，而不是 最优服务。文献【3 0 1 提出了有效的w e b 服务组合策略b i t s ，该方法使用二叉树来组织w e b 服务，使组合问题转化成树的表示和遍历。尽管b i t s 能够得到最优的满足用户需求的 w e b 服务组合方案，但它仍然没有考虑到w e b 服务的q o s i h - j 题，只是把包含原子服务数 目最少的组合服务当成最优的，从本质上也无法满足用户约束。因此，构建一个有q o s 约束的w e b 服务组合成为下一个研究热点。 基于图搜索的方法提供了一种不同于a i 规划的w e b 服务自动组合的有效途径，虽然 无需过多的形式化表示方法或推理系统，在实施上比较容易，但是随着服务库中服务数 量的增多和服务之间关系的复杂化，服务关系图的构建时间将增长，开销也增多，导致 9 第二章w e b 服务组合概述 性能降低。 2 3 支持q o s 的w e b 服务组合 到目前为止，工业界和国际组织已经提出好几个不同的w e b 服务q o s 模型。例如， m m 发布的w s l a ( w c bs o r v i c l a n g u a g ea g r e e m e n t ) ，它使用本体和语义概念来定义q o s 属性，对服务提供者和用户之间的有关q o s 因素如可用性、响应时间和成功执行率等进 行了详述。当前，w 3 c 和i s o 正在努力规范q o s 属性。 w c b 服务组合的一个很重要的问题就是要能反映客户综合q o s 需求，用户的q o s 需 求通常表示为对q o s 属性的约束值，基于工作流的原子过程要解决的问题就是寻找一个 最优的组合服务同时不违反用户规定的q o s 约束。c a r d o s o 在文献 1 3 d f l 提出了一种基于 现有工作流模型的组合服务q o s 评价模型，但是它对组合规划的q o s 评价还不够，不能 满足用户的q o s 需求，用户需要一个能在众多可能的组合规划中自动挑选出满足他们需 求的组合规划，这是一个复杂的n p h a r d 的优化问题。z c n g 在文献【1 2 】中提出了一个整数 规划算法来优化组合规划，然而随着原子过程和候选w e b 服务的数目的增加，该算法的 时间复杂度成指数增加，服务组合性能也趋于恶化。文献 1 5 1 6 采用了遗传算法来减少 组合时间，但是它不能处理w e b 服务组件的各种执行方式，而且对支持该w e b 服务组合 算法的架构也没有进行讨论。 2 4 本章小结 本章主要介绍了w e b 服务组合的相关概念和技术。首先介绍了w e b 服务组合的发展、 定义；然后分别介绍了三种不同的w c b 服务组合方法t 基于工作流的服务组合、基于a i 规划的服务组合和基于图搜索的服务组合，其中第一个实现服务流程的人工生成，后两 个实现服务流程的自动生成；最后介绍了一种支持q o s 约束的w e b 服务组合。 1 0 西北大学硕士学位论文 第三章q o s 信息描述与q o s 计算 3 1o w l s 本体 o w l - s 是美国d a r p a 资助项目1 3 1 1 ，是用本体来描述w e b 服务的标记语言，其目标 是能够对一个w c b 服务进行逻辑描述。它也是一种具有显式语义的无歧义的机器可理解 的标记语言( m a r k u pl a n g u a g e ) ，可以描述w e b 服务的属性和功能。 o w l - s 由一个层次结构组成，处于最上层的是服务( s e r v i c e ) 类，包含三个属性，分 别是表示( p r e s e n t s ) 、被描述( d e s e r i b e d b y ) 和支持( s u p p o r t s ) 。三个次高层的类是服务轮廓 ( s e r v i c e p r o f l i e ) 、服务模型( s e r v i c e m o d e l ) 和服务基点( s e r v i c c g r o u n d i n g ) ，分别对应于服 务的上述三个属性，其中，服务轮廓描述服务做什么，服务模型描述服务怎么做，服务 基点描述怎样访问服务及与服务进行交互。 图3 - io w l - s 的顶层本体图 图3 1 为服务的顶层本体示意图，表明了顶层本体类之间的关系。图中，椭圆表示 o w l - s 的类，弧表示o w l s 的属性。s e r v i c e 类的实例通过属性来表示、描述和支持分 别指向服务轮廓类、服务模型类和服务基点类的实例。 o w l - sp r o f i l e 提供了一系列概念来说明服务所具有的功能，其目标是支持基于功能 的服务发现。明确的地说，o w l sp r o f i l e 允许服务提供者发布服务能做什么的广告，服 务请求者指明他们所需要的服务功能，利用o w l - sp r o f i l e s 的结构和参考o w l 中的概 念，发现过程可以为服务请求者找到满足他们要求的最优服务。 o w l - sp r o c e s s 指定了与w e b 服务交互的可能模式，共有三个过程类型原子过 程、组合过程和简单过程。其中，原子过程和组合过程会被调用。原子过程是没有内部 结构的，在服务消费者和服务提供者之间的输入输出中，它是单向交换的( 调用过程中 第三章q o s 信息描述与q o s 计算 只接收一次消息并只返回一个消息) 。组合过程包含一组由控制流和数据流相连接的分 量过程，控制流是由典型的程序语言或工作流构成，如顺序、选择和循环等；数据流描 述信息是怎样获得的。简单过程用于提供原子或组合过程的抽象视图，不能直接调用， 没有和它相关联的g r o u n d i n g ，也是单向执行的。 s e r v i c c g r o u n d i n g 主要涉及服务的具体规范，用于描述如何访问服务，指定服务访问 的协议、交换消息格式、传输端口以及寻址方式等。 3 2q o s 本体模型发展现状 3 2 1d a m l - q o s 本体 如图3 - 2 所示，d a m l - q o s 本体有三层：q o s 配置层( q o sp r o f i l el a y e r ) 主要用于q o s i e _ 配，q o s 属性定义层( q o sp r o p e r t yd e f i n i t i o nl a y e r ) 主要用于描述q o s 属性的定义域和取值 范围，q o s 度量层( m e t r