（计算机软件与理论专业论文）面向用户需求的组合web服务发现.pdf

摘要 摘要 近年来，随着电子商务和i n t e m e t 的不断发展，w e b 服务已经成为最具有生 命力的w e b 应用集成技术之一。对w e b 服务的相关的研究也得到顺利开展。具 体来说，研究者们从w e b 服务的抽象和描述、服务语义和语义级互操作、服务 社区化、服务组合、服务验证和测试、服务的有效管理和组织、服务的选取、匹 配和替换算法、服务质量等方面对w e b 服务展开了研究，并已取得了一定的成 果。然而在现实的很多应用中，单个服务可能难以满足现在面向服务应用的需求， 作为一个解决方法，由不同的服务所提供的功能做组合的一个新型的服务可能满 足这样的需求，如此搜索构造这样新型服务的过程就被称作为组合w e b 服务的 发现。本文在前人研究的基础上，对面向用户请求的组合w e b 服务发现的问题 进行了深入的探讨和研究，提出了基于与或树求解的组合w e b 服务发现模型， 并设计了最优w e b 组合服务发现算法、全部w e b 组合服务发现算法、t o p k 优 组合服务发现算法，这些组合算法都高效实时处理的特性，具有较高的实用价值， 这些特性都通过实验进行了验证。 本文的主要贡献包括： ( 1 ) 本文设计了一个同与或树同构的二叉树结构，在此数据结构基础上把组 合服务发现的问题转化成为了树求解遍历的问题。设计了专门用于寻找组合服务 调用中间结点的前驱条件集的策略，并且通过理论和实验来证明了这个策略的高 效性。 ( 2 ) 提出了面向用户请求的，基于与或树求解的e n t i r e w s s t s 和 o p t i m a l w s s t 算法，分别用于求解全部服务组合，最优服务组合的问题。在此 期间，为了提高效率我们还做了相应的优化策略。基于这两个算法，我们实现了 能够回答用户请求的组合w e b 服务发现的系统b i t s ，并且进行了系列的实验 来验证系统中所实现的算法的性能。另外本系统还在i c e b e 2 0 0 5 服务组合大赛 上获得了冠军。 ( 3 ) 有时候单个的最优组合w e b 服务不能满足用户要求，获取全部组合w e b 服务所消耗的时间又是用户不可以容忍的。于是，在扩展前两个求最优和全部组 合w e b 服务算法的基础上，同时考虑服务质量的因数，我们设计了两个求前k 个 较优组合w e b 服务的算法，c o m p l e t e w s c b t 和w s c b t * 算法。其中 c o m p l e t e w s c b t 算法是直接从e n t i r e 。w s s t s 演变过来的算法，能够准确的找到前 k 个最优的组合，e b 服务，但是效率较低。另一方面，w s c b t * 算法是一个基于启 摘要 发式规则的算法，虽然找到的是近似的前k 个最优组合w e b 服务，但通过实验证 明该近似度相当的高，足以满足用户的需求，并且拥有很高的效率。在此基础上 我们扩展了原来的b i t s 系统，扩展版的系统b i t s 2 可以支持面向用户请求的t o p k 组合w e b l t 务的发现。 本文提出的基于与或树求解，面向用户请求的组合w e b 服务发现的各项技 术，在w e b 服务管理技术研究中尚属首次。研究成果不仅具有较高的理论指导 价值还有很强的实际应用价值。 关键字：w e b 服务发现，组合w e b 服务 分类号：t p 3 l a b s w a e t a b s t r a c t a st h ed e v e l o p m e n to f e - c o m m e r c ea n dt h ei n t e m e t , w e bs e r v i c eb e c o m e so b eo f t h em o s tp r o m i s i n gw e b - b a s e da p p l i c a t i o n si n t e g r a t i n gt e c h n o l o g yi nr e c e n ty e a r s m u c hr e s e a r c hw o r kh a sb e e nd o n ei nr e l e v a n ta r e a so fw e bs e r v i c e s ，i n c l u d i n gt h e a b s t r a c t i o na n dd e s c r i p t i o no fw e bs e r v i c e s ，s e m a n t i c so fw e bs e r v i c e sa n d m t e r o p e r a t i o no f w e bs e r v i c e so ns e m a n t i cl e v e l ，c o m m n n i t yo f w e bs e r v i c e s ，s e r v i c e c o m p o s r i o n ，s e r v i c ev e r i f i c a t i o na n dt e s t i n g ，e f f e c t i v em a n a g e m e n ta n do r g a n i z a t i o n o f w e bs e r v i c e s ，s e r v i c es e l e c t i o n , m a t c h m a k i n ga n da l t e r n a t ea l g o r i t h m sa n dq o se r e b a s e do nt h i sr e s e a r c h ，i nt h i sp a p e r , w eg i v ed e e p l ys t u d ya n dd i s c u s s i o nu p o nt h e p r o b l e mo fd i s c o v e r yo fc o m p o s i t ew e bs e r v i c e s w eh a v ep r o p o s e da l g o r i t h m st o r e s o l v et h eo p t i m a lo n ep r o b l e m ，t h ec o m p l e t ec o m p o s i t i o nc a n d i d a t e s p r o b l e ma n d t h et o p kc o m p o s i t i o nc a n d i d a t e s p r o b l e m w ev e r i f yt h ee f f e e t i v e n e s sa n de f f i c i e n c y o f o u ra p p r o a c hb ye x p e r i m e n t st h ec o n t r i b u t i o n so f t h i st h e s i si n c l u d e ： ias u c c i n c t b i n a r y t r e e a p p r o a c h i s p r o p o s e d ，w h i c he n a b l e s s e r v i c e c o m p o s i t i o np r o b l e mt o b et r a n s f o r m e di n t oat r e er e p r e s e n t a t i o na n dt r a v e r s a l p r o b l e ma ne f f i c i e n ts t r a t e g yf o rf i n d i n gp r e c o n d i t i o n sf o re a c hi n t e r n a ln o d ei nt h e i n v o c a t i o nt r e e si sd e s i g n e dt h e o r e t i c a la n a l y s i sa n de x t e n s i v ee x p e r i m e n t sa r e c o n d u c t e dt ov e r i f yt h ee f f i c i e n c yo f t h ep r o p o s e ds t r a t e g y 2t h eb i t ss y s t e mi sd e s g i n e dt or e s o l v et h ec o m p o s i t ew e bs e r v i c er e t r i e v a l p r o b l e m i nb i t s ，e f f i c i e n ts e a r c hs t r a t e g i e sa n do p t i m i z a t i o nt e c h n i q u e sa r e d e v e l o p e df o rd i s c o v e r yo fc o m p o s i t ew e bs e r v i c e s t h eo p t i m a lo n ep r o b l e m ， c o m p l e t ec o m p o s i t i o nc a n d i d a t e s p r o b l e ma r ea l lr e s o l v e di nt h i ss y s t e me x t e n s i v e e x p e r i m e n t sa r ec o n d u c t e da n dt h ee x p e r i m e n t a lr e s u l t ss h o wt h ee f f i c i e n c ya n d e f f e c t i v e n e s so ft h ep r o p o s e da p p r o a c h t h er e s u l t sh a v ea l s ob e e nc o n f i r m e db yt h e f a c tt h a tb i t sh a sw o nt h ec h a m p i o n s h i po ft h ei c e b e 0 5w e bs e r v i c ec o n t e s t i n s p i r e db yi e e ee l e c t r o n i cc o m m e r c ei n s t i t u t e 3s o m e t i m e so n l yt h eo p t i m a lc o m p o s i t ew e bs e r v i c ec a nn o ts a t i s f yu s e r s r e q u i r e m e n ta n dt h et i m et of i n dt h ee n t i r eo n e si sn o ta c c e c p t a b l ei no r d e rt or e s o l v e s u c h p r o b l e mw ed e v e l o pt w ot o p kc o m p o s i t ew e bs e r v i c e sa l g o r i t h m s 1 1 1 e c o m p l e t e - w s c b ta l g o r i t h mi sas t r a 【g h f f o r w a r do n e ，w h i l ew s c b t * i sa ne f f i c i e n t a p p r o a c ht a k i n gq o sa n dh e u r i s t i cr u l e si n t oa c c o u n tf o rd x s c o v e r yo ft o p - k 1 i i a b s u a e t c o m p o s i t ew e bs e r v i c e st h ee x p e r i m e n t a lr e s u l t ss h o wt h a tt h ew s c b t * a p p r o a c hi s e f f i c i e n ta n d s u b s t a n t i a l l yi m p r o v et h ep e r f o r m a n c e o v e rt h e s t r a i g h t f o r w a r d c o m p l e t e w s c b ta l g o r i t h mb a s e do nt h ea b o v et e c h n i q u e s ，w ee x t e n dt h eb i t s s y s t e m t oan e wv e r s i o n ，n a m e db i fw h i c hc a l l s u p p o r td i s c o v e r yo ft o p & c o m p o s i t ew e b s e r v i c e se f f i c i e n t l ya n de f f e c t i v e l y o u rm e t h o do f d i s c o v e r yo f c o m p o s i t ew e bs e r v i c e st o w a r d su s e r s r e q u e s ti st h e f i r s tt i m ef o rs e r v i c em a n a g e m e n tb ye x p l o i t i n gt h eu n d e r l y i n gs e m a n t i c so fw e b s e r v i c e sw i t hs o l u t i o nt r e em o d e lb o t ht h e o r e t i c a la n a l y s i sa n de x p e r i m e n t a lr e s u l t s s h o wt h ep r o p o s e dm e t h o d sa r ee f f i c i e n ta n de f f e c t i v ei ns e r v i c em a n a g e m e n ta n d r e t r i e v a lo u rr e s e a r c hh a sg r e a ti m p o r t a n c eb o mi nt h e o r e t i c a la n da p p l i e da r e a k e y w o r d s ：w e bs e r v i c ed i s c o v e r y , c o m p o s i t ew e b s e r v i c e 论文独创性声明 本论文是我个人在导师指导下进行的研究工作及取得的研究成果论文中 除了特别加以标注和致谢的地方外不包含其他人或其它机构已经发表或撰写 过的研究成果其他同志对本研究的启发和所做的贡献均已在论文中作了明确 的声明并表示了谢意 作者签名 论文使用授权声明 本人完全了解复旦大学有关保留、使用学位论文的规定即：学校有权保 留送交论文的复印件。允许论文被查阅和借阅：学校可以公布沿丈：的生赢：磊帘 分内容可以采用影印、缩印或其它复制手段保存论文保密的论文在解密后 遵守此规定 作者签名：盔：口2 惶导师肇名因缝日瓤写丛、 第一章绪论 1 1 本文的研究背景 第一章绪论 随着s o a ( s e r v i c e o r i e n t e d a r c h i t e c t u r e ) 技术的的发展，w e b 服务在电子商务 行业中的应用变得越来越多，推动了电子商务的服务模式从b 2 c ( b u s i n e s s t o - c u s t o m e r ) 模式发展到b 2 b ( b u s i n e s s t o b u s i n e s s ) 模式转变的进 程。同时b 2 b 的服务模式，在技术上从过去的简单的w e b 信息发布发展到i n t e m e t 范围内的数据共享和信息集成上来。这样，就要求i n t e m e t 上的商业应用系统， 拥有快速性、有效性和可靠性等特性。在这背景下应运而生的w e b 服务技术， 作为一种新型的分布式计算模型，已逐渐成为w e b 上数据和信息集成的有效手 段。在展开的讨论本文所研究的问题前，我们先对w e b 服务，以及相关的研究 情况进行介绍。 1 1 1w e b 服务简介 w e b 服务就是通过w e b 接口提供的某些功能程序段。通过标准的i n t e m e t 标 准协议或规范可以很容易地访问这些功能。换句话说，w e b 服务就是可以通过 u r l 访问的资源，这些资源可以通过编程方式向客户返回信息。 w e b 服务就像一个封装了一定功能的黑盒子，用户可以重用而不用关心它是 如何实现的。w e b 服务定义了良好的接口，这些接口描述了它所提供的服务，用 户可以通过这些接口来调用w e b 服务提供的功能。这样开发者便可以通过把远 程服务、本地服务、和用户代码合在一起来创建应用程序。图11 显示了使用 w e b 服务应用程序的一般模型。 第一章绪论 f i g u r el 1w e bs e r v i c eb a s e da p p l i c t i o nm o d e l 图1 1 使用w e b 服务的应用程序的模型 从图l ，1 可以看出，用户可以在多种不同类型的应用程序中通过i n t e m e t 标准 协议来访问w e b 服务。这些w e b 服务可以位于不同的物理位置，并且可以在不 同的系统中实现，它们的功能通过接口来调用。这允许并支持基于w e b 服务的 应用程序变得松敌耦合、面向组件。w e b 服务可以单独或同其它w e b 服务一起 用于实现复杂的聚集或商业交易。 1 1 2 需要w e b 服务的原因 w e b 服务有个显著的优势，那就是我们可以很轻松地适应它的变化和更新， 有一个标准可以让w e b 服务描述它们自己，所以w e b 服务地变化可以很容易地 传播到w e b 服务客户端。然而，w e b 服务带来了好处远远不止这些： ( 1 ) 平台的无关性 w e b 服务最强大的特性就是使用可扩展标示语言支持的跨平台的兼容性，任 何类型的设备，只要能连入i n t e m e t ，便可以轻松地访问w e b 服务。 ( 2 ) 通用的通用通道 w e b 服务的运行是以i n t e m e t 作为其通信机制的。i n t e r n e t 建立在诸如t c p i p 和h t t p 这些开放的、标准的通信协议之上，整个i n t e m e t 普遍支持这些既定协 议。将i n t e r n e t 作为通信通道可以获得最高级别的访问和可用性。 f 3 ) 企业的互操作性 近年来，企业对企业的电子商务( b 2 b ) 在通讯与应用开发方面得到了发展。 这些类型的应用程序包括合并或把现有的业务系统与贸易合作伙伴和供应商相 结合。w e b 服务允许通过x m l 和h 1 t r p 这两个既简单又易用的协议来完成这一 第一章绪论 过程。 ( 4 ) 功能复用 开发人员能够利用外部厂商已经实现的功能，这意味着开发人员不必创建基 础结构和支撑服务就可以集中精力针对问题提供最好的业务解决方案。 ( 5 ) 拓展业务 通过使用w e b 服务访问内部系统的方式，企业允许消费者以更加集成化的方 式和以用户为中心的方式访问它们。同时w e b 服务也能够用来拓展贸易伙伴关 系，通过将供应链与w e b 服务提供商集成在一起，可以使业务过程能够动态的 而且灵活的变换需求。 ( 6 ) 服务器的中立性 开发w e b 服务所使用的程序设计语言和服务软件是没有关系的。w e b 服务所 在的服务器可以运行u n i x 、w i n d o w s 2 0 0 0 、l i n u x ，或者其他任意的操作系统， 在w e b 服务幕后执行的软件可以用j a v a 、c 针、c # ，或任何其他编程语言编写 的。 ( 7 ) 安全的通信 w e b 服务像所有的w e b 应用程序一样安全。保护在线商业站点使用的技术也 同样用于保护和验证w e b 服务的身份。 1 1 3 使用w e b 服务的时机 分布式架构的世界可以分为两个主要的区域：内部世界和外部世界。内部世 界关系到一个组织如何在它的内部网络中部署应用程序。外部世界关系到一个企 业如何将它的应用程序和业务过程与外部组织集成。 在分布式架构的内部世界中，当需要扩展现有的应用程序，或同新购并的组 织集成时，w e b 服务的介入可以打消我们对异构系统融合的忧虑：然而，在内部 世界其主要的问题就是性能，在设备兼容性高的场合，使用现有的技术如 m i e r o s o f t 的d c o m 或j a v a 的同等技术可以获得更好的结果，由于本地通信是在 已知的端点之间进行的，所以没有必要使用w e b 服务平台中立的优点。 在分布式架构的外部世界，使用w e b 服务则可以把各种功能综合起来，实现 企业间的无缝集成，从而简化的业务关系。然而在外部世界中，我们关心的主要 是安全问题。m i c r o s o f t 的d c o m 或j a v a 的同等技术可以提供更安全的框架，而 且沿用已久，又很多省力的工具和一大堆文档可以使用。 当然，最后的决定往往取决于进行分布式应用开发人员的经验。 第一章绪论 1 1 4w e b 服务的前景 可编程的w e b 的基本思想是，开发人员可以通过集成服务和功能( 在i n t e m e t 上由w e b 服务所提供) 的方式来创建完整的系统。“任何系统、任何数据和任何 格式”将是“可编程w e b ”的宗旨。这样使开发人员将能够将精力集中在手边的 业务上，而且不必花费大量的时间去编写基础结构和通信代码，企业集成和利用 外部专门技术的性能将使开发企业解决方案的效率更高，并使最终用户能使用更 加无缝集成的服务。 1 2w e b 服务研究现状 在w e b 服务技术的研究方面，主要经过了协议制定，如何应用，如何发现服 务，如何组合服务等阶段。在这项技术刚出来的时候，很多组织( 如w 3 c 、w s i 等) 和国际知名的软件企业( 如m m 、b e a 、h p 、m i c r o s o f t 等) 都致力于相关 技术标准制定。发展到现阶段以x m l 为基础的w s d l c m r + 0 6 、s o a p u r l e 和u d d i u r l c 三大标准已经发展成熟并成功应用到w e b 服务中。为了提高 w e b 服务技术为整合第三方组件的能力，使w e b 服务极大地加速了商业应用的 开发，并且提高了软件的模块化、灵活性和可配置性 b c p + 0 5 。诸如i b m ， m i c m s o f i ，b o r l a n d ，b e a 等公司都对自己的主打开发平台提供了对w e b 服务的 支持，如i b mw e b s p h e r e 、m i c r o s o f i n e t 、j b u i l d e r ，b e aw e b l o g i c 等都提供了 对w e b 服务发布的支持。这些主流的开发平台对w e b 服务技术的支持加速了 w e b 服务在商业应用上的应用。 而w e b 服务的普及度的大大提高，造成w e b 服务数量和所支持业务类型也 越来越多在这种环境下。要使w e b 服务满足不断增长的应用需求，就对w e b 服务管理提出了新的要求 - b 1 0 0 2 。除了要提供一个开放、安全的环境来支持服 务提供者按可编程的方式描述业务和服务之外，如何让用户能够在具有海量w e b 服务的注册中心快速高效的找到自己想要用的w e b 服务成为一个难题，这项技 术称为服务检索或称服务发现。w e b 服务发现与传统的信息检索有很多相似之 处，但是由于要考虑到服务调用接口匹配，服务相似性，被调用服务稳定性等问 题，所以w e b 服务的发现具有更高的复杂性，现阶段的实现技术还不成熟。主 要的应用还是以在u d d i 上人工的发现，这样所选择服务的稳定性，准确性基本 依赖于选择服务人员对服务的认知水平，另外其选择的过程是非常耗时的，不能 满足现阶段w e b 服务快速集成的要求。另外很多时候，单个的服务不能完全满 第一章绪论 足用户的要求，此时，就希望能够把w e b 服务所表示的商业逻辑进行组合以满 足用户的要求。在这一小节中我们将就与本文最相关的w e b 服务发现和服务组 合技术方面已有的一些工作进行一些讨论。 1 2 1w e b 服务发现 服务发现的目的是为了在i n t e r n e t 上找到能够满足用户当前需求的可以重用 的模块。在这一方面，目前最流行的是w 3 c 所制定的u d d i u r l c ，这是一个 基于框架浏览的手动发现服务的方式。此种方式要求用户有较好的专业查找能 力，其效率较低，查找的准确率较低。针对上述情况，文献 b h l 0 2 提出了一 种基于语义w e b 的服务发现技术，该技术将w e b 服务通过索引建立到过程本体 上 e s a + 0 4 ( p r o c e s so n t o l o g i e s ) ，将服务的功能作为过程模型( p r o c e s s m o d e l ) 来定义过程本体。这样，服务的查找和发现的过程就转化为将过程模型中的过程 本体与查询中所用到的过程本体相匹配的过程。和u d d i 技术相比，这种技术借 助了本体的语义描述能力，所以具有较高的查准率，查全率，但检索结果直接依 赖于服务的过程本体的定义，有较大的局限性。 近年来p 2 p 技术高速发展由于该技术能够把计算分布到不同的p e e r ，这样 就减轻了单个p e e r 的负担，当被搜索的数据具有海量的特点的时候，基于p 2 p 环境的搜索具有一定的优势。于是出现了较多基于p 2 p 环境的服务发现技术，如 c j y + 0 2 ，s p 0 4 ，s s k + 0 2 ，w s 0 3 。其中 w s 0 3 所提出是一种用于p 2 p 环 境中的服务发现协议g s d ( g r o u p b a s e dd i s t r i b u t e ds e r v i c ed i s c o v e r yp r o t o c 0 1 ) 。 在p 2 p 环境下服务按照“类一子类”的层次关系进行分组存放，对于服务的请求， 只需将它发送到语义相关的服务分组( g r o u p ) 上，如此在并发的服务查询请求 的环境下，该协议有较高的承受负载的能力。在基于p 2 p 环境下服务发现的其他 工作中，文献 s p 0 4 从服务的功能和行为的角度对p 2 p 环境下的w e b 服务发 现进行了研究；文献 s s k + 0 2 考虑基于p 2 p 的关键字索引的服务发现；而 c j y + 0 2 1 着力于从基于本体的超立方体p 2 p 系统的角度来实现w e b 服务的发现。 另外，也有些研究工作将服务的发现转变为寻找一个相似的服务的问题。这 样的情况主要用在替代服务的应用环境，也即是当用户现在正在使用的w e b 服 务下线的时候，如果希望能够立刻有新的类似的功能来完成想要完成的任务，那 么如何寻找一个与原来的服务类似的服务就是此处问题的关键。在文献 d h m + 0 4 中，作者采用传统信息检索与结构匹配相结合的方式，通过计算候 选服务与参照服务相似性，找到与参照服务最相似的一个。在系统w o o g l e w o o g l 通过类似挖掘关联规则的算法，将w e b 服务的参数名称聚类到相应 第一章绪论 的概念中，实现w e b 服务的相似性检索。在我们前期研究工作 p i j w z 0 5 中，我 们提出了提出在服务格上检索w e b 服务( 包括替代w e b 服务) 方法，并用实验 进行了验证。通过研究服务格中各结点( 形式概念) 之间的关系，提出了通过服 务格检索w e b 服务的技术和相关算法。除此，我们还对替代w e b 服务及其检索 方法进行了专门的研究，提出了通过服务格检索替代w e b 服务的算法和实现技 术。 总之，w e b 服务发现的研究目标是服务发现的高效率和自动化，上述的研究 工作从结合语义方面，考虑分布式查询方面，替代服务查询方面来解决这个方向 上的问题。但如何用d a m l d a m l 0 1 1 描述服务，如何将语义w e b ，本体论和语 义推理应用到w e b 服务的查找和匹配中是有待进步研究的课题。但在目前， 实际应用中的w e b 服务描述信息中多数是没有加入语义信息的，从这个意义上 说，要高效地发现w e b 服务必须有效地挖掘出服务间潜在语义联系。 1 2 2w e b 服务组合 w e b 服务组合是一个非常具有挑战性的研究题目，很多的科研人员都参与其 中，并提出了各种各样的服务组合模型，和服务组合的方法。此处我们将对过去 关于这个方面的研究工作做一个简单的介绍。 首先，我们将要讨论用于服务组合得模型，这个是所有的服务组合技术的核 心。w e b 服务组合作为分布式计算重要的一块，很多用在分布式应用的模型都可 以用在这个上面，比如工作流模型，这是一个特别强调流模型和数据模型的一种 模型 l r s 0 2 1 。应用在语义网络上面的本体模型，是另外一个可用在w e b 服务的 模型【b h l 0 1j ，并且本体语言可以表示出服务组合的模块的模型 m s z 0 1 ， m v 1 0 3 1 ，些自动的组合方式就是基于这个模型的。除此外，还有些其他的模型， 比如进程代数模型，, z g 算子 r m 9 3 ，z c c 0 4 模型，和p e t r ig 目 k e z c 0 4 模型。 其次，在建立了组合的模型以后，组合的策略也是非常的重要的。组合的策 略按照是否需要手工处理可以彼分为两大类：人工的服务组合，自动的服务组合。 前面一种方法，通过人工的方式构造出服务的组合，而后一种方式按照某种原理 或者规则自动的生成服务的组合来。考虑到服务选择的时机，组合可以被分为静 态的组合和动态的组合。前一个在服务设计的时候进行绑定，而后者是在执行的 时候实时的绑定。按照不同的模型，我们按照如下的情况讨论不同的策略。 基于工作流的服务组合模型。数据传输流被定义成工作流模型。以前的些 相关的工作包括，如何实现w e b 服务组合的模块化和标准化，如何使得w e b 服 务组合能够随着动态的环境自动的调整。在所有的工作当中，i b m ，m i c r o s o f t ，b e a 第一章绪论 等公司在2 0 0 2 年提出的b p e l 4 w s ( b u s i n e s s p r o c e s s e x e c u t i o n l a n g u a g e f o r w e b s e r v i c e s ) l r s 0 2 】是最流行的一种方式。b p e l 4 w s 解决了描述服务中操作的调 用协作关系的问题，除了传统的服务的操作闻的调度和逻辑关系，b p e l 4 w s 也 可以表示商业服务间的依赖关系。另外在2 0 0 1 年，h p 公司发布了e - f l o w 【c s 0 1 】 服务组合系统，该系统中提供了服务表现，构造和管理的功能。e - f l o w 的主要 贡献是提出了一个自适应的服务组合模型，使得服务组合能够随着动态的环境自 动的变化。 基于语义模型的组合。语义w e b 服务的研究主要集中在两个方面。第一，设 计一个机器可读的语言来表现w e bs e r v i c e 的内容，函数功能，结构，性质等等 比如o w l st o w l 0 1 】，w s m o r k l 0 4 】和w s d l s w s d l 0 4 。另一方面，提 出一个基于语义w e b 的强大的系统。斯坦福大学的m i l m i t h 提出了s w s f 【m m 0 3 】 ( s e m a n t i cw e bs e r v i c ef r a m e w o r k ) 系统框架结构，在这个框架中依赖三方代理和 知识库的力量实现了w e bs e r v i c e 的自动发现和自动计算还有自动的组合。基于 d a m l - s a b h 0 2 i 的结构和代理可以区别服务的限制还有通过d a m l 所体现出 来的倾向。如此可以借助本体知识的基础上，自动的组合服务来满足用户的查询 请。乔治大学的l s d i s 实验室提出了个基于w s d l s 的语义组合系统 m e t e o r - s 【t r 0 3 i v s s 0 4 1 。w s d l s 是w s d l 的扩展版本，它扩展了服务操作， 消息输入和消息输出。m e t e o r - s 把这样的语义信息插入到u d d i 的描述中，提出 了语义活动模板的概念，并且用本体来标识服务请求。当接收到用户的请求的时 候，系统自动将选择服务并构造出服务组合流，最后组合的结果将以b p e l 文档 的形式来呈现。 基于组件模型的组合。这些工作主要集中关注组合关系中组件的粒度问题。 一个服务自身是由一个小粒度的组件所构成的。斯坦福大学的w s i g 研究小组所 提出的s w o r d p f 0 2 系统就是其中的一个例子，它可以根据用户的需求快速的 构造出新的复杂的组合服务。s w o r d 系统所采用的模型是e r 模型的一个变种， 其中每个服务都被看作为一个实体，而组合关系就转化为实体问的调用关系。 s w o r d 系统依靠规则引擎来实现服务组合，输入输出参数对应了规则中的条件 和结论。s w o r d 比较简单高效，但是很难在公开的w e b 服务环境中使用。 1 3 本文研究目标和成果 在l2 小节中提到已有的一些服务发现的研究成果，都只能找到单个w e b 服务，而用户的请求具有多变性，往往在一个w e b 服务集中虽然不存在这样的 7 第一章绪论 单个w e b 服务可以满足用户需求，却存在将多个服务的组合，他们可以满足用 户的需求。利用上述服务发现技术不能实现对这些服务组合的搜索。另外，还有 一些支持服务发现的搜索引擎技术 u r l g ，u r l h , w o o g l e 】，如w o o g l e ，。这些 服务搜索引擎也只能返回满足查询要求的单个服务。如果在w e b 服务库中不存 在单个的服务可以满足查询要求时，用户通常会收到查找不到满足要求的w e b 服务的消息。也就是说，即使在w e b 服务集中存在多个服务的组合可以满足用 户的需求，这些搜索引擎技术同样也不能发现这些组合。综上所述，为了找到那 些满足用户需求的组合w e b 服务，完全有必要研究出一些w e b 服务组合快速发 现的方法，但直到目前，这一研究工作开展的还很少。 基于服务发现系统的功能弱势，我们考虑到了利用组合服务来扩充服务发现 的结果。现在的服务组合系统主要有：基于工作流的服务组合模型的，比如 b p e l 4 w sfl r s 0 2 ，e f l o w c s 0 1 】服务组合系统；基于语义的服务组合系统， 比如s w s f 【m m 0 3 】，m e t e o r - s 【t r 0 3 【v s s 0 4 。但是在基于工作流的服务组合 模型中，服务组合基本是手工或者半手工的在组合动态的调用前把服务组合的计 划实施好，其实时性较差，难以满足实时动态的组合服务请求。而基于语义的组 合服务系统框架中要么依赖三方代理和知识库的力量实现了w e bs e r v i c e 的自动 发现和自动计算，还有自动的组合，对知识库的依赖性较强，对现有系统的扩充 要求较大难以推广；要么把这样的语义信息插入到u d d i 的描述中，提出了语义 活动模板的概念，并且用本体来标识服务请求，但更加的适用于小环境中，扩充 性较差。这样的工作都在不同程度上利用了w e b 服务的语义，它们对有语义描 述的w e b 服务是适用的。但当前实际应用中，占领主导地位的还是基于w s d l 、 s o a p 及u d d i 协议的w e b 服务。因此，在基于语义的w e b 服务规范没有被广 泛应用之前，采用上述服务组合方法并不适合发现潜在的组合w e b 服务。 本文从s o a p 消息层来考虑的w e b 服务组合，这样有效地保证了组合结果的 可实现性。在对w e b 服务特征进行深入研究的基础上，提出了一个支持w e b 服 务组合的快速搜索方法。利用这个方法可以高效地搜索满足查询要求的w e b 服 务组合而不只是单个w e b 服务。这样可以很好地弥补了以前服务搜索方法中， 只考虑单个服务而忽略了组合服务的缺点。与本文同期出现的面向服务请求的快 速组合服务搜索的工作中，也有类似于本文的考虑角度来处理w e b 组合服务的。 其中最有代表性的是宾夕法尼亚大学的b f * 算法 s b e l 0 5 。在这篇文章中，提 出了一个基于启发式规则的搜索方法来获得次优的服务组合解决方案。该方法运 用b l o o mf i l t e r s 来实现快速的参数包含关系检查。这个启发式的方法基于这样的 思想，“那些相对具有更高的贡献的服务将会先被访问到，如此可以更快的达到 最终的目标。这篇文章构造服务的顺序是从用户的输入请求到输出请求。在每一 第一章绪论 步中，它根据启发式规则来选择一个w e b 服务。虽然这是一个比较高效的方法， 但是该方法不够健壮。首先，该方法生成的服务组合结果中，原子服务间的依赖 关系并不清晰。其次，对于该文中的启发式规则，可能会遇到一些恶性的情况将 无法处理。当所有的服务的h f n ) ( h e u r i s t i cv a l u e ) 相同的时候，换句话说，没有一 个服务对目标查询输出有贡献的时候，此时启发式规则失效，最终导致下一个的 服务选择是随机的。如果服务集的数量巨大，那么这样的情况出现的概率将会增 大， 最终的服务组合的结果将是不理想的。 基于上述论述，本文的主要研究内容：充分利用现有的w e b 服务描述信息 c e r e q 。二恰_ 嚣怒黪”6 。d y ”。1 。o 。“净”n t r 甜。9 r i “哪恰。 。tlastt e p r i c e o u t p u t 嚣鬈鬈o a y ”引“m = ”删。n 础蹦。e r e s u l t ”4 ” 一 m yt f s ts e r v i c e 瓣黜鬣磷葛粉嚣i 黜；赋蹴瓣“s 峰 勰e f i g u r e26e x a m p l eo f w s d ld o c u m e n t 图2 6 w s d l 文档实例 第二章基础知识 2 1 5u d d i 协议 u d d i 的全称是u n i v e r s a ld e s c r i p t m n ，d i s c o v e r y ，a n di m e g r a t i o n ( 通用描述、 发现和集成) ，由u d d io r g 进行维护。意图在于组织可以把自己连同它提供的服 务，以及在哪里可以使用这些服务的细节在u d d i 目录中注册。可以通过u d d i 注册表搜索提供w e b 服务的企业，并构建自己的代理。 u d d i 规范本身是一套利用x m l 描述的w e b 服务的规则，也是一种通过互 联网来注册和发现这些描述的方法。该规范还包括了一种以编程方式访问u d d i 数据的方法，既可以在注册表中插入数据，又可以从中获取信息。 u d d i 注册表本身就是一个w e b 服务，所以，可以在设计时或运行时通过调 用和使用这些服务来与u d d i 进行交互，以发现有关服务的技术数据。这允许把 u d d i 于应用程序紧密地集成在一起。u d d i 注册表所提供的信息包含三个部分： ( 1 )白页( w h i t ep a g e ) ：其中包含有关w e b 服务的一般信息，例如w e b 服 务的u r l 和公司的名称、地址等。 ( 2 )黄页( y e l l o wp a g e ) ：其中包括基于标准分类法的分类系统，比如 m i c r o s o f t 所属的类型为“n a i c s ( = 1 8 美工业分类系统) ：s o f t w a r e p u b l i s h e r ”。 ( 3 )绿页( g r e e np a g e ) ：其中包括有关企业所提供的w e b 服务的技术信息， 它是发现潜在w e b 服务的关键部分。这部分列出了发现w e b 服务的所 有公共接口和发现机制。 u d d i 的数据结构设计得非常灵活，可以表示很大范围得公司得情况，而且 注册表中得相关信息也非常容易。公司、服务、技术信息或服务规范等不同方面 得信息都被分开存储，并且可以通过唯一标识符或键的方式访问。当第一次把信 息存储到u d d i 注册表中时，u d d i 将给它分配唯一的标识符，这些标识符以后 可以用作关键字来访问特定的数据实例。 u d d i 中包含五种基本的数据结构，每一种都使用一个x m l 元素来表示： ( i )b u s i n e s s e n t i t y 元素中包含公司及其提供的服务的描述性信息。 ( 2