（计算机应用技术专业论文）基于qos的动态web服务组合中服务选取问题的研究.pdf

东北大学硕士学位论文 摘要 基于0 0 $ 的动态w e b 服务组合中服务选取问题的研究 摘要 随着对w e b 服务研究的不断深入，能够提供增值功能的组合w e b 服务得到了广 泛的重视。服务组合通过动态的合成已有的w e b 服务，无需重构整个服务组合，能够 很好的适应i n t e r n e t 环境年n ：l k 务领域的多变性和动态性，为企业间的业务合成提供了 无限的可能。然而，随着w e b 服务的流行，w e b 服务的数量与日俱增，如何能够在大 量的能够实现相同功能的w e b 服务中，选取出一组服务，使得所组合出的服务具有最 好的质量、最高的用户满意度成为目前研究的一个热点，本文将对这一问题进行研究。 本文提出了一个服务组合选取问题的解决方案，并将这个选取问题归结为4 个子 问题：服务选取的标准一- e 务质量q o s 模型；对于单个w e b 服务的选取：对于组 合服务的简单形式一一单一管道路径组合服务的选取：对于复杂路径组合服务的选取。 针对于服务质量评估标准q o s 模型，本文分析了目前的2 种q o s 模型的优缺点， 并在此基础上，提出了一个客观的、公平的，能够反映组合服务真实质量的q o s 模型。 该模型除了将目前已有的q o s 模型普遍采用的服务层和业务层服务属性作为影响服 务性能的主要因素同时，通过揭示组合服务的可组合性直接影响了组合服务被调用 的成功率这一规律，将服务问的关联度作为衡量组合服务质量的重要指标。实验表明， 这一模型是选取出质量良好的、用户满意度高的组合服务的基础。 在对组合w e b 服务中基于q o s 的单个w e b 服务选取问题的研究巾，本文将其归 结为一个服务匹配问题，并且分析了2 种基本的匹配方法：基于关键字的匹配和基于 本体的匹配。 在研究基于q o s 的单一管道路径组合服务的选取问题中，本文将这类问题归结为 一个最短路径问题。进而，提出了基于xq o s 的组合服务选取的基本方法。同时，通 过实验，讨论了不同的q o s 模型在组合服务选取中的适用范围。 在对基于q o s 的复杂路径组合服务选取问题的研究过程中，提出了一种基于 xo o s 进行复杂路径组合服务选取时所采用的剪枝方法。实验表明，这个方法具有较 好的时间效率并且能够保证所选取出的组合服务的质量。 关键词：w e b 服务；组合w e b 服务iw e b 服务质量( q o s ) ：服务选取；服务匹配 东北大学硕士学位论文 a b t r a c t s t u d yo nk e yt e c h n i q u e sf o rq o s d r i v e nd y n a m i cs e l e c t i o no f c o m p o s i t ew e bs e r v i c e s a b s t r a c t w i t ht h ed e v e l o p m e n to fw e bs e r v i c e s ，c o m p o s i t ew e bs e r i v e sw h i c hc a np r o v i d e v a l u e a d d e df u n c t i o n sh a v er e c e i v e dal o to fa t t e n t i o n s c o m p o s i t ew e bs e r v i c e sa r eak i n d o fw e bs e r v i c e sw h i c hc o m b i n ea v a i l a b l es e r v i c e sb a s e do nc e r t a i nb u s i n e s sl o g i ci no r d e r t om a k et h ec o m p o s e do n ea c h i e v em o r ep o w e r f u la n dm o r ec o m p l e t eb u s i n e s sf u n c t i o n s t h e s ec o m p o s i t ew e bs e r v i c e sa r ec h a r m i n gf o rt h e i rv e r s a t i l ea n da g i l ec o m p o s i t i o na n d a d a p t a b l i l i t y f o r d y n a m i cc h a n g i n g e n v i r o n m e n to fi n t e m e t ，t h a ti s t o s a y , s u c h c o m p o s i t i o n s h a v ec r e a t e d u n p r e c e d e n t e do p p o r t u n i t i e s f o rb u s i n e s st ob u s s i n e s s i n t e g c m t i o n h o w e v e r , w i t ht h e - p r e v a i l i n go fw e bs e r v i c e s , t h en u m b e ro fs e r v i c e so nt h e i n t e m e th a sb e e nl a r g e ra n dl a r g e r h o wt os e l e c tas e to fs e r v i c e sa m o n gl a r g eb o d yo f s e r v i c e sw i t ht h es a m ef u n c t i o ni no r d e rt om a k et h ec o m p o s i t ew e bs e r v i c e sa c h i e v e b e t t e rp e r f o r m a n c ei sah o ti s s u ew h i c hi sar e s e a r c ha r e ai nt h i sp a p er i no r d e rt os t u d yo nt h i si s s u ee f f e c t i v e l y , t h i sp a p e ri l l u s t r a t e st h e g e n e t i cp r o c e s so f c o m p o s i t ew e bs e r v i c e ss e l e c t i o n ，a n dm o r e o v e r ，d i v i d e st h i sp r o b l e mi n t o4s u b - p r o b l e m s ： t h ec r i t e r i af o rs e l e c t i o n q o s ；s i n g l es e r v i c es e l e c t i o n ；t h e p i p l e l i n ep a t hc o m p o s i t e s e r v i c es e l e l c t i o n ；t h ec o m p l e xp a t hc o m p o s i t es e r v i c es e l e c t i o n i nt h es t u d yo fq o s ，t h i sp a p e ra n a l y z e sc u r r e n tq o sm o d e l s a d v a n t a g e sa n d d i s a d v a n t a g e s ，b a s e do nw h i c hp r o p o s e sa no b j e c t i v e ，f a i rq o sm o d e lw h i c hc a nr e f l e c tt h e c o m p o s i t es e r v i c e s q o sr o u n d l y t h i sm o d e lc o m p a r e dt of o r m e ro n e s ，n o to n l ye m b o d i e s t h es e r v i c el e v e lq o sa n dd o m a i nl e v e lq o s ，b u ta l s o ，t h r o u 【g hc o n c l u d i n gt h a tt h e c o m p o s a b i l i t yo fs e r v i c e sc a na f f e c tt h es u c c e s sr a t eo fi n v o c a t i o no fc o m p o s i t es e r v i c e s ， r e g a r d e d t h er e l a t i o n d e g r e eb e t w e e ns e r v i c e s a sa n i m p o r t a n tq o s f a t t e nt h e e x p e r i m e n t a t i o ns h o w st h a tt h i sm o d e lp l a y sa l li m p o r t a n tr o l e i n s e l e c t i n gt h em o s t q u a l i f i e dw e bs e r v i c e sc o m p o s i t i o n i nr e s o l v i n gq o s d r i v e ns i n g l es e r v i c es e l e c t i o ni nt h ew e bs e r v i c e sc o m p o s i t i o n ，t h i s p a p e rh a sm a p p e ds u c hp r o b l e mi n t oas e r v i c em a t c h m a k i n gp r o b l e ma n da n a l y z e dt w o b a s i cm a t c h m a k i n ga p p r o a c h e s ：k e y w o r dm a t c h m a k i n ga n do n t o l o g ym a t c h m a k i n g 1 1 1 东北大学硕士学位论文 a b t r a c t i nt h es t u d yo fq o s d r i v e ns e l e c t i o no fp i p e l i n ep a t hc o m p o s i t es e r v i c e ，a f t e r a n a l y z i n ge x i s t i n g s e l e c t i o na p p r o a c h e s ，t h i sp a e rv i e w st h i sp r o b l e ma sas h o r tp a t h p r o b l e mb a s e do nw h i c h ，p r o p o s e ss o m eb a s i ca p p r o a c h e sf o rx _ q o s - d r i v e ns e l e c t i o n m e a n t h n e ，t h r o u g he x p e r i m e n t a t i o n s ，, i sp a p e ra l s od i s c u s s e si s s u e s a b o u ti nw h i c h s i t u a t i o na d o p t i n gw h i c hq o st os e l e c t i o n i nt h es t u d yo f ，q o s d r i v e nt s e l e c t i o no fc o m p l e xp a t hc o m p o s i t es e r v i c e ，t h i sp a p e r a n a l y z e ss o m eb a s i ca p p r o a c h e so ft h i si s s u e ，a n dp r o p o s e sa l la p p r o a c hf o rx _ q o s d r i v e n s e l e c t i o no fc o m p l e xp a t hc o m p o s i t es e r v i c ew h i c hb a s e do nt h ec o n c e p to fp a t hp r u n i n g t h ee x p e r i m e n t a t i o n ss h o wt h a t ，a p p r o a c h e so fx _ q o s - d r i v e na p p r o a c h e sh a v eb e r e r r u n t i m ee f f e c t i v e n e s sa n dc a na s s u r et h eq u a l i t yo fc o m p o s i t ew e bs e r v i c e sw h i c hc a nn o t b ea c h i e y e db yo t h e r s k e y w o r d s ：w e bs e r v i c e s ；c o m p o s i t ew e bs e r v i c e s ；q u a l i t yo fw e bs e r v i c e s ( q o s ) ；w e b s e r v i c e ss e l e c t i o n ；w e bs e r v i c e sm a t c h m a k i n g - l v 独创性声明 本人声明所呈交的学位论文是在导师的指导下完成的。论文巾取得 的研究成果除加以标注和致谢的地方外，不包含其他人己经发表或撰写过 的研究成果，也不包括本人为获得其他学位而使用过的材料。与我一同工 作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示 谢意。 、i 、 於、觇 学位论文作者签名：功诫、f 学位论文版权使用授权书 本学位论文作者和指导教师完全了解东北大学有关保留、使用学位论 文的规定：即学校有权保留并向国家有关部门或机构送交论文的复印件和 磁盘，允许论文被查阅和借阅。本人同意东北大学可以将学位论文的全部 或部分内容编入有关数据库进行检索、交流。 学位论文作者签套： 弋、 f 砸 签字日期：妒；、 请在下方签名；否则视为不同意。) 导师签 签字日期：巩一 东北大学硕士学住论文 第一章引言 1 1 研究背景 第一章引言 1 1 1w e b 服务和组合w e b 服务的意义 w e b 服务是_ 一种自包含、自描述、模块化的程序，它吸取了分布式计算、g r i d 计算和x m l t l l 等各种技术的优点，通过采用w s d l l2 1 、u d d i 3 1 、和s o a p t 4 1 等基于 x m l 的标准和协议，解决了分布式计算以及代码与数据重用等问题j 具有高度的互 操作性、跨平台性和松耦合等特点，引起了世界范围内学术界和工业界的极大兴趣。 简单的说，w e b 服务是“一次发布、到处可用”的新型i n t e m e t 组件，支持服务复 用和组合，对提高网络软件生产率和产品质量具有重要意义陋1 。目前：存在于i n t e m e t 上的w e b 服务的恸j 予有很多，比如，在线订货k 在线交付、实时新闻服务等等。用 户可以通过i n t e m e t 方便的找到希望的服务，= 并且以。种透明的方式调用它。 但是。单个的w 曲。服务往往不能实现用户的目标。；比如说，一个“旅行计划” 服务，它就需要集成机票预定、旅店预定叫租车等参个服务。；这时就需要对已有的 单个w e b 服务进行组合，以得到具有增值意义的组合服务。在【6 1 1 巾也已经提到 w e b 服务组合是实现企业间协作的重要形式，它通过将i t i t e m e t 上的已有的相对简 单的w e b 服务按_ 定的业务流程逻辑合成起来以构成复杂的服务组合，从而提供更 强大更完整的商业功能。通过合成已有的w e b 服务，就无须重构单一的复杂服务， 为企业节省了大量的人力和物力资源。同时，当这种组合能够动态的进行时，无疑 将很好的适应i n t e m e t 环境下的服务的多变性和动态性；使企业不被局限于单一固 定的合作伙伴一同时也能够使彳导组合出的服务具有很好的可靠性。而这个动态的服 务组合中一个重要的内容就是要动态的进行服务的选取，t 使得选取出的服务所进行 的服务组合具有很好的适应性租良好的质量一。 1 1 2 动态服务选取茬服务组合中的地位 动态服务组合的最终目标是通过动态的、实时的服务选取使得所包含的服务能 够正确的运行、实现用户对组合服务的质量上的要求。像止面所提到的那样，动态 服务组合通过在运行期进行服务的绑定最大限度的确保了组合服务的可用性。需要 东北大学硕士学位论文第一章引言 强凋的是动态服务组合这种质量的保证是通过服务选取而进行的。动态服务选取就 足要在运行期对提供相同功能的服务进行选择，从而使得最终的组合服务具有良好 的适应性、可运行性，总的说来，使得组合服务具有好的质量。可以这样说，服务 选取是提供满足用户要求的、高质量的组合服务的关键，没有一个好的服务选取， 就无法保证服务组合的正确运行，更无法保证这个服务组合是满足用户要求的高质 量的服务。 一个好的服务选取能够实现用户对组合的个性化要求、能够得到高质量的组合 服务，。使得服务以用户希望的运行。t 好韵服务选取必然不是随意进行的，它必然地 要遵循某一种标准，体现这种个性化的要求i 表现这种质量品质i 采用某种商效的 选取算法，使得得到的最终的组合服务能够满足用户l 的需求；能够以一种正确的方 式运行。这也就是本文接下来要讨论的动态服务选取的关键问题。 1 2 动态服务选取的关键问题 动态服务选取问题是服务组合中的一个关键问题，它的成功与否决定着最终的 服务组合的正确运行。服务选取伺题首先要解决的问题是采用什么样的标准来进行 服务选取；其次，如何将这样一个标准应用到服务选取的进程中使得组合服务具有 好的质量。接下来，”本文从这两个方面详细讨论了服务选玻的这两个关键问题。 1 2 1 服务的质量评价模型o o $ 服务选取必然要遵循菜| 种标准进行，这个标准需要体现用户对w e b 服务的非功 能性的属性要求，需要反映组合服务的质量品质，如何建立这样一个标准是影响组 合服务质量好坏的关键。 q o s 是一个可以衡量服务质量的广泛的概念，它包含了一系列的像费用、运行 时间、可用性；信誉度、可靠性等这样的非功能属性1 1 2 】，它能够体现服务满足用户 需求的程度。q o s 可以作为服务选取的标准，、这是因为；首先；q o s 可以体现服务 的质量，因为它本身就是个可以衡量服务质量的概念；其次，q o s ：可以体现用户 对服务的满意程度，因为通过对服务的各个q o s 因素的衡量，可必反映出服务的质 量等级；再次，q o s 可以反映用户对服务质量的个性化要求，通过对某个质量因素 的特定的要求，：能够得到满足用户对这个质量的需求；最后，利用q o s 进行服务选 取在现实中是可行的，：【r 3 - 1 5 】都是利用q o s 进行服务选取的成功范例。 尽管利用q o s 进行动态服务选取是可行的，但是目前构建一个合适的、有效的 东北大学顾士学位论丈 第一章引言 强调的是动态服务组合这种质量的保证是通过服务选取而进行的。动态服务选取就 是要在运行期对提供相同功能的服务进行选择，从而使得展终的组合服务具有良好 的适应性、可运行性，总的说来，使得组合服务具有好的质量。可以这样说，服务 选取是提供满足用户要求的、高质量的组合服务的关键，没有一个好的服务选取， 就无法保证服务组合的正确运行，更无法保证这个服务组合是满足用户要求的高质 量的服务。 一个好的服务选取能够实现用户对组合的个性化要求、能够得到高质量的组台 服务，使得假务以用户希望的遮行。好的服务选取必然不是随意进行的，它必然地 要遵循某一种标准，体现这种个性化的要求_ ：表现这种质量品质i 采用某种高效的 选取算法，使得得到的壤终的组合服务能够满足俐声的需求：_ 能够以一种正确的方 式运行。这也就是本文接下来要讨论的动态服务选取的关键伺题。 1 2 动态服务选取的关键问题 动态服务选取恂题是服务组台中的一个失键问题，它的成功与否决定着最终的 服务组合的正确运行。服务选取4 问题首先要解抉的问题是采用什么样的标准来进行 服务选取：其次，如何将这样。个标准应用到服务选取的进程中使得组合服务具有 好的质量。接下来，。- 本文从这两个方面洋细讨论了服务选取的这两个关键惘题。 1 2 1 服务的质量评价模型1 2 0 8 nr ! l 服务选取必然饕遵循某种标准进行，这个标准需要体现用户对w e b 服务的非功 能性的属性要求，需要反映组合根务的质量品质，如何建立这样一个标准是影响组 合服务质量好坏的关键。 - = r 。 q o s 是一个可以衡量服务质量的卢泛的概念，它包含了一系列的像费用、运行 时间、可用性；信誉度、可靠性等这样的非功能属性i ” ，它能够体现服务满足用户 需求的程度。q o s 可以作为服务选取的标准，、这是囱为i 首先i ；q o s 可以体现服务 的质量，因为它本身就是一个可以衡量服务惯量的概念；。其次，q o s ：可以体现用户 对服务的满意程度，因为通过对服务的各个_ q o s 因嚣舯衡量k 可，呸反映出服务的质 量等级：再次，q o s 可以反映用户对服务质量的个性化要求，通过对某个质量因素 的特定的要求，能够得到满足埔户对这个质量的需求；最后，利用q o s 进行服务选 取在现实中是可行的，； 1 3 - 1 5 都是利用q o s 进行服务选取的成功范例。 尽管利用q o s 进行动态服务选取是可行的，但是目前构建一个合适的、有效的 尽管利用q o s 进行动态服务选取是可行的，但是目前构建一个合适的、有效的 东北大学硕士学位论文第一章引言 强凋的是动态服务组合这种质量的保证是通过服务选取而进行的。动态服务选取就 足要在运行期对提供相同功能的服务进行选择，从而使得最终的组合服务具有良好 的适应性、可运行性，总的说来，使得组合服务具有好的质量。可以这样说，服务 选取是提供满足用户要求的、高质量的组合服务的关键，没有一个好的服务选取， 就无法保证服务组合的正确运行，更无法保证这个服务组合是满足用户要求的高质 量的服务。 一个好的服务选取能够实现用户对组合的个性化要求、能够得到高质量的组合 服务，。使得服务以用户希望的运行。t 好韵服务选取必然不是随意进行的，它必然地 要遵循某一种标准，体现这种个性化的要求i 表现这种质量品质i 采用某种商效的 选取算法，使得得到的最终的组合服务能够满足用户l 的需求；能够以一种正确的方 式运行。这也就是本文接下来要讨论的动态服务选取的关键问题。 1 2 动态服务选取的关键问题 动态服务选取问题是服务组合中的一个关键问题，它的成功与否决定着最终的 服务组合的正确运行。服务选取伺题首先要解决的问题是采用什么样的标准来进行 服务选取；其次，如何将这样一个标准应用到服务选取的进程中使得组合服务具有 好的质量。接下来，”本文从这两个方面详细讨论了服务选玻的这两个关键问题。 1 2 1 服务的质量评价模型o o $ 服务选取必然要遵循菜| 种标准进行，这个标准需要体现用户对w e b 服务的非功 能性的属性要求，需要反映组合服务的质量品质，如何建立这样一个标准是影响组 合服务质量好坏的关键。 q o s 是一个可以衡量服务质量的广泛的概念，它包含了一系列的像费用、运行 时间、可用性；信誉度、可靠性等这样的非功能属性1 1 2 】，它能够体现服务满足用户 需求的程度。q o s 可以作为服务选取的标准，、这是因为；首先；q o s 可以体现服务 的质量，因为它本身就是个可以衡量服务质量的概念；其次，q o s ：可以体现用户 对服务的满意程度，因为通过对服务的各个q o s 因素的衡量，可必反映出服务的质 量等级；再次，q o s 可以反映用户对服务质量的个性化要求，通过对某个质量因素 的特定的要求，：能够得到满足用户对这个质量的需求；最后，利用q o s 进行服务选 取在现实中是可行的，：【r 3 - 1 5 】都是利用q o s 进行服务选取的成功范例。 尽管利用q o s 进行动态服务选取是可行的，但是目前构建一个合适的、有效的 东北大学硕士学位论文第一章引言 q o s 服务质量评估模型仍然存在着一系列的问题。首先，q o s 衡量的是服务的质量， 这个服务的质量既应包括组合服务中单个服务的质量也应包括组合服务的质量，但 是目前对于组合服务的q o s 的研究较少；其次，既然是组合服务，这旱就存在着组 合服务与单个服务间对质量要求的不同，比如说，组合服务中服务间的可组合性也 是影响组合服务质量的重要因素。然而，目前大多数的对于组合服务的q o s 的研究 仅仅处于将组合服务也看成是一类服务的层次上，并没有考虑到组合服务的特性以 及这种特性对于质量模型的要求，尽管有些研究1 7 】也提出了将服务间的关联度作 为衡量服务质量的因素但是由于它们都仅仅考虑了一个最简单的情况，即只是前后 相连的两个服务间的关联度，同样无法将它们应用到组合服务4 选取的普遍情况中： 最后，目前的大多数的q o s 模型都仅仅考虑了服务层阿质量因素，比如说费用、运 行时间等，忽略了与w e b 服务领域相关的服务质量，、即业务层的质量，比如说服务 的地理位置等等。 针对于这样一个问题，本文在对目前的服务质量评估模型q o s 进行研究后，在 第3 节提出了个服务质量评估模型一一xq o s 。这个模型的意义在于它不但考虑 了单个服务的t q o s , 同时也考虑了组合的q b s ；不但考虑了组合的q o s ，同时根据 组合服务的特性，设计了一些组合服务的质量度量指标：而且，本文所考虑的q o s 不单单考虑了服务层对服务质量的要求，同时考虑了业务层对服务质量的要求，将 用户可能的对服务的质量要求都考虑了其中。一实验表明，。利用本文所提出的q o s 模 型进行服务选取时，组合服务具有良好的适应性：可运行性和曩组合性。 1 2 2 服务选取的算法 服务质量评估模型q o s 可以用来衡量一个服务的质量；但是如何将这样一个模 型应用于选取当中是服务选取的根本问题。i 接下来，本文将讨论这个问题；即讨论 应该采用什么样的算法来进行服务的选取。好的q o s 是服务魄取问题的基石，好的 选取算法就是服务选取问题的灵魂。一个好的选取算1 法可以使得选取具有高的效率、 选取出的服务具有好的质量选取的结果具有理想的用户满意度：在对基于q o s 进 行服务选取问题的研究中，r 根据用户对服务质量要求粒度的不同，本文将分别讨论 两类选取算法：组合服务中单个服务的选取算法和组合服务的选取算法。 1 2 2 1 组合服务中单个服务：的1 选取算法 动态的服务组合方式是在设计期制定出组合的流程，明确其中的任务及任务间 的关系；在运行期进行服务的选取与绑定。如果用户对某一个任务而不是整个流程 东北大学硕士学住论文 第一章引言 或部分流程的质量有要求，那么根据这个要求所进行的服务选取就是组合服务中单 个服务的选取。这个对单个服务的选取是通过对服务的质量因素的值与所要求的值 进行比较进行的，换旬话说，这个单个服务的选取算法是个基于q o s 的服务匹配 算法。目前，基于服务匹配的研究有很多，基于本体i j8 。2 0 】的匹配由于它能够克服服 务异构性所带来的匹配查全率低、查准率! 差等缺点，被广泛的应用于服务匹配问 题中。 1 2 2 2 组合服务的选取算法 组合服务选取的目标是要根据用户对组合服务质量的要求，选取出_ 组服务使 得最终的组合服务县有最好的用户满意度、良好韵质量。对于定性的质量因素，可 以将这种对质量的要求固化到组合，w e b 服务的单个服务中，比如，要求组合服务的 所在地必须是北京，这里也就隐含的说明组合中的单个服务的所在地都必须是北京。 这时通过单个服务的选取算法就可以得到一系列的满足要求的单个服务，换句话说， 这些服务所组合出韵服务也必然的满足这种质量要求。对于定量的质量因素，通过 对组合中的所有可能的服务的质量因素值的计算，判断组合后的服务能否满足所要 求的质量。对于基于定量的质量因素进行组合服务选取的算法主要可以采用两种方 式：一是基于局部优化的选取算法；一是募于全局优化的选取算法。 基于局部优化的选取算法的核心是对于组合中的每个任务，、对能够完成该任务 的所有的服务迸行基币质量因素的选取，：找到能够实浸单个钰务的质量最优的服务。 这种方法的着眼点仅仅在于组合中的单个任务，而不考虑任务间的联系。然而，在 实际情况中，基于局部优化选取出的组合服务不一定是全局最优的服务组合，而且 往往不能够满足用户对组合服务的整体质量的要求。这是因为，首先：用户对于服 务的质量要求因素可能有多介，如果不考虑全局服务选取，只着眼于单个服务就会 导致所选出的服务很难或不能满足全局的要求。比如，用户要求整个服务组合的运 行时问小于5 秒“费用小于2 0 美元。倘若组合服务中所有备选服务的费用都很小， 那么此时对单个服务费用的过度约康就是没有必要的一而在局部选取中由于没有考 虑整个组合服务中各个服务的情况疗i 因而。利用l 这种方法在进行基予两个或两个以 上质量因素的选取过程中，会导致不能找到用户满意度最好的组合服务的情况。其 次，在上面我们已经提到，在组合中_ 个非常重要的质量因素是服务间的关联度， 即服务间的可组合性，这个质量因素内在的要求选取中需要考虑服务以及服务间的 关联情况，显然，这时仅仅利用这种局部的选取策略是困难的。因丽，从这两个方 面看，利用局部优化的选取算法选取出的组合服务由于它将组合硬性的拆分，仅仅 东北大学硕士学位论文 第一章引言 关注于单个服务，而导致了它的低效用。针对于这样几个原因，目前学术界都强调 基于全局优化策略的服务选取，这种方法使得选取不再仅仅关注于单个服务本身而 是着眼于整个服务。 基于全局优化的选取算法将着眼点从单个服务转移到了整个组合服务，从而使 得选取出的服务更接近用户对组合服务质量的要求。 然而由于目前的q o s 模型在评价组合服务的质量时，都是将评价单一管道路径 组合服务的质量作为基础，然后基于它，再对复杂路径的服务组合的质量进行评估。 因此，这个基于q o s 的组合服务的选取就被分成2 个部分：一是对于单一管道路径 组合服务的选取；二是对于复杂路径组合服务的选取。对于单一管道路径组合服务 的选取问题可以将其归结为一个最短路径问题：而对于复杂路径组合服务的选取问 题通常的作法是通过关键路径方法i 13 i 或者路径拆分【2 2 ，2 3 1 方法进行。日前，基于全局 优化算法进行服务选取的例子有很多，比p h i l 3 】中就采用了整数规划的方法进行基 于全局优化的组合服务的选取；同时 2 4 1 将人工智能中的遗传算法运用到了服务的 选取中并取得了成功。 尽管这些方法在基于全局优化的选取问题上都取得了一定的成功。但是不可忽 略的是，它们都没有将服务间的关联因素考虑其中，这样组合出的服务可能由于服 务问无法进行交互而不可用，导致组合服务调用的失败。同时，我们注意到无论是 现有的关键路径方法还是路径拆分方法都会使得选出的组合服务有质量的损耗。因 此，本文提f b 了基于xq o s 的组合服务选取，使得组合服务的质量损耗降为最低， 提高选取的效率，优化组合服务的质量。 1 3 文章研究的内容和文章结构 为了实现高质量的服务组合，本文针对于基于q o s 的动态w e b 服务组合中服 务选取的关键问题进行了研究。主要包括服务选取问题的标准一一质量评估模型 q o s 和基于q o s 的服务选取的算法等，提 n 了相应的解决方法，并得到了一些重要 的结论。 全文一共分六章。 第一章为引言部分，主要介绍了w e b 服务、组合w e b 服务及服务组合动态选 取的研究意义与价值，并且针对于基于q o s 的动态w e b 服务组合巾服务选取总结 了其中的关键问题，对于每个关键问题介绍了相关的研究现状、存在的问题，提出 了本文研究的内容。 东北大学硕士学位论文第一章引言 第二章介绍了w e b 服务组合过程中的相关问题，比如w e b 服务和组合w e b 服 务的定义、服务组合的基本过程及服务选取在组合过程中的一般流程、以及本文在 进行服务性能评估的实验方案，这一部分是本文的一个研究基础。 第三章研究了服务动态选取中的第一个关键问题也是服务选取问题的基 石一一服务质量评估模型。文中总结了目前常用的两种服务质量评估模型的现状及 存在的问题，并基于这些问题提出了xq o s 模型。 第四章研究了服务选取中单个服务的选取算法。文中首先将这个选取问题归结 为一个服务匹配问题，并且分别总结了两种基本的服务匹配方法：基于关键字和基 于本体的匹配，分析了这两种方法的现状及存在的问题。 第五章研究了服务动态选取中单一管道路径组合服务选取算法。文中通过对目 前已有的或基于基本的q o s 进行服务选取，或基于基本的xq o s 进行服务选取问 题的剖析，通过实验对比了这些方法的效率与效用，并提出了基于x q o s 进行组合 服务选取的算法。 第六章研究了服务动态选取中复杂路径组合服务选取算法。文中通过剥目前的 复杂路径服务组合选取算法的研究，分析了这些算法存在的问题，并提出了基于路 径剪枝的选取算法。 第七章总结全文。给出了本文的主要贡献，根据本文的研究问题得出了一些结 论，同时介绍了下步要做的工作。 东北大学硕士学位论文 第二章基于o o s 的动态w e b 服务组合选取问题的相关问题 第二章基于q o s 的动态w e b 服务组合选取的 相关问题 为了有效的研究基于q o s 的动态w e b 服务组合选取问题，本章将介绍一些有关 服务选取的相关问题，包括：w e b 服务和组合w e b 服务的定义；服务组合的一般过程： 服务选取的几个重要的子问题；以及为有效研究服务选取进行实验分析的实验方案。 2 1w e b 服务和组合w e b 服务 2 1 1w e b 服务 w e b 服务是一种新型的w e b 应用程序。w 3 c w e bs e r v i c e s a r c h i t e c t u r e 小组为w e b 服务的定义是：“w e b 服务是由u r i 标识的软件应用程序，其接口和绑定可以通过x m l 构件进行定义、描述和发现，w e b 服务支持通过基于因特网的协议使用基于x m l 的 消息与其他软件应用程序直接进行交互”1 2 5 1 。为了有效地研究q o s 驱动的动态w e b 服务组合选取问题，本文假设一个w e b 服务只包含一个操作，按照w 3 c 的定义，它 可以形式化的定义为： i 定义2 1 】w e b 服务( 阡研 一个w 曲服务可以定义为这样一个三元组：w s = 。其中，s 是基本捕述， 即服务名称和文本描述；c 是服务功能描述，即对服务的行为描述，包括服务的接口、 前嚣条件和后置条件：o 是对服务的非功能属性的描述，即服务的质量因素。 这罩，q 可以由一个n 元组定义为：q = ，其中，9 是关于服务的 不同的质量因素，如服务花费、响应时间等等，它从不同的角度反映了服务的性能， 本文将在第3 部分着重讨论它。目前，大多数的w 曲服务描述语言都自发的遵循 ，比如q w s d l 5 1 、o w l s f 2 6 l 等等。 例2 1 l w e b 服务的例子 对于一个预定机票服务( b o o k a i r t i c k e t s e r v i c e ) 它的基本描述s ：s e r v i c e n a m e ：b o o k a i r t i c k e t s e r v i c e s e r v i c e d i s c r i p t i o n ：o r d e r i n ga i rt i c k e t sf r o mf l i g h tc o m p m w 东北大学硕士学位论文第二章基于q o s 的动态w e b 服务组合选取问题的相关问题 s e r v l c e p r o v l d e r ：n o r t h e a s t e r nu n i v e r s i t y 它的功能描述c ：p a r a m e t e r ：本文将在定义2 2 中给出具体的形式 p r e c o n d i t i o n ：m o n e y p u t p o s t c o n d i t i o n ：b o o k e d t i c k e t 它的非功能属性q ：我们将在第3 部分详细讨论。 i 定义2 2 jw e b 服务接口( p a r a m e t e r ) w e b 服务是通过消息来进行数据的交互、进行服务的调用的，这种服务之问进行交互 的消息，本文定义为w e b 服务的接口。它可以由这样一个二元组来表示：p a r a m e t e r = q 0 。其中， ( 1 ) - 是服务的输入参数集合，= j 。厶毛，j 。) ；0 是服务的输出参数集合，p 一 0 ，0 2 , 0 3 , 一二仉) ； ( 2 ) v f 。i ，j 严 膨zd ，其中，是参数，。的意义，7 1 是参数j 。的类型，是参数j 的单位； ( 3 ) v 。0 ，o k = 肛z b ，其中，是参数o k 的意义，是参数0 的类型，是参数0 。 的单位。 i 例2 2 l 关于w e b 服务接口的例子 对于上面的例子 p a r a m e l e r = ，其中 ，= i l ，i 2 ，0 = 1 0 l ，0 2 ： i = ，f 2 = o i = ，0 2 = 2 1 2 组合w e b 服务 i n t e r n e t 作为无所不在的连接和通信工具为企业组织同它们的合作伙伴和客户交 互提供了新的契机，w e b 服务的出现在这一方向上迈出了重要的一步。它的出现改变 了商业合作伙伴之间及其客户之间的协助方式，使企业能够通过服务合成来共享资源、 自动化商业流程。所谓组合w e b 服务，是把i n t e m e t 上已有的相对简单的w e b 服务按 照一定的业务流程逻辑合成起来以构成复杂的复合服务，从而提供更强大更完整的商 业功能。为了有效的说明动态服务组合中的服务选取问题，本文按照以下的方式定义 一个服务组合，并且引进初始虚拟服务和终止虚拟服务一一两个逻辑上存在的、物理 ，卜不存在的服务，来标志着一个组合服务逻辑上的开始和结束，这里分别用w s o 和 东北大学硕士学位论文 第二章基于o o s 的动态w e b 服务组合选取问题的相关问题 w s + ，来表示。 l 定义2 3 l 组合w e b 服务( c w s ) 和服务组件( w s o 一个服务组合c w s 可以形式化的定义为：c w s = ，这里： i 灯= 服务序歹0 w s o ，w s ，哦，w s , ，w s , + 小而且服务序列巾的服务不是孤立的， 而足具有控制逻辑关系c r 和数据逻辑关系d r ； = 服务问所具有的控制逻辑关系的集合，控制逻辑关系的定义见定义2 4 ； 舢= 服务间所具有的数据逻辑关系的集合，数据逻辑关系的定义见定义2 5 ； l 例2 3 l 组合w e b 服务和服务组件的例子 本文举一个名为“旅行计划”的组合w e b 服务的例子，它可以用一个图来表示( 图2 1 ) 。 这样一个组合服务是由服务序y u w s o w s l ，w s ：，w s j ，w s 4 ，w s 5 ，w s n ，w s 7 】组成的，它表示 在预定机票和订旅馆的同时可以搜索景点，而且景点可以反复的搜索直到找到一个满 意的为止；之后，要计算景点和旅店的距离，如果这个距离大于某个值，就雇用 ；租 车，否则雇用自行车。 h k e r m m i p a r e m 一一t d co 品勰一。黜。 图2 1 组合w e b 服务的图形表示 f i g 2 1c w se x p r e s s e db yac h a r t l 定义2 4 l 服务间的控制逻辑关系( c r ) 服务间的控制逻辑关系是服务间在控制逻辑上的关系，标志了服务间的执行逻辑，对 于组合服务中的任意两个服务w s i 和玎毪，如果它们之间存在以下的4 种关系，则称 它们之间具有控制逻辑关系c o n t r o l r e l a t i o n ( w s j ，嘞) ： 顺序关系( s e q u e n c er e l a t i o n ) 对于服务w s i 和w s j ，如果执行完w s i 后就执行 w s j ，则w s j 和w s j 之间是顺序关系，表示为c o n t r o l r e l a t i o n ( w s i ；w s j ) ，同时 称服务嘲是w s j 的直接控制前驱服务，也可以称踊是w s i 的直接控制后继 服务； 分支关系( f o r kr e l a t i o n ) 对于服务w s i 和w s j ，如果根据前面的执行结果，或 东北大学硕士学位论文第二章基