（计算数学专业论文）基于qos的服务发现与服务组合研究.pdf

摘要 面向服务的计算是松耦合、开放异构环境中分布应用的通用计算模 型，w e b 服务是近年来提出的面向服务的新型体系结构。伴随着网络 信息的持续快速发展，w e b 服务资源越来越丰富，w e b 服务的应用所 跨越的领域越来越广泛。大规模的u d d i 注册中心存在于各个自治域 中，实现w e b 服务的搜索发现、集成、分类将会如同w e b 网页搜索 一样变得具有挑战性。由于w e b 服务数量的爆炸性增长，网络服务虚 拟社区中存在大量的功能重叠或相同的w e b 服务，如何利用 q o s ( q u a l i t yo fs e r v i c e ) 属性选择广告服务是w e b 服务组合实用化的关 键技术之一。因此在分布、异构和自治松耦合计算环境中，需要有效 的服务组合方法优化服务组合流程，保障w e b 服务组合的质量。 本文研究了w e b 环境下，如何跨多u d d i 的服务搜索发现，如何 按照服务提供者的需求提供有质量保障的应用。以此提出了跨多 u d d i 注册中心的服务管理框架和资源管理构件w e b j e tr e p o s i t o r y b u i l d e r ，提出了服务搜索发现策略。并基于服务管理框架提出了一个 基于q o s 的w e b 服务发现与组合架构w e b j e t ，实现服务的发布、管 理、发现、组合前的预先优化与运行时容错。 针对用户偏好的是否确定性，提出了区间判断矩阵的q o s 属性权 重计算方法和自动修正判断矩阵的权重计算方法。为实现服务组合时 的全局优化，提出了一种o 1 启发式方法，并在不同的运行环境下与 整数规划的分支定界方法和遗传算法进行了对比，验证了o 1 启发式 方法优越性。现在的服务组合优化模型很少考虑现代供应链管理中的 服务的动态商业联盟的场景，本文提出了支持供应链管理的非线性的 服务组合优化模型，给出了遗传算法优化策略，实验表明服务联盟模 型及其求解策略对服务组合模型是有用的。 关键词：q o s ，服务搜索，o 1 规划，遗传算法，服务组合，服务联盟 a b s t r a c t s e r v i c e o b j e c t e dc o m p u t i n gi s au s u a l c o m p u t i n gm o d e lt h a t i s a p p l y i n g i nt h el o o s e c o u p l e d ，o p e na n dd i s t r i b u t e dh e t e r o g e n e o u s e n v i r o n m e n t ，a n dw e bs e r v i c ei san e ws e r v i c e o b j e c t e da r c h i t e c t u r ei n t h er e c e n ty e a r s w i t ht h er a p i dd e v e l o p m e n to ft h ei n t e m e ti n f o r m a t i o n ， t h er e s o u r c e so fw e bs e r v i c eb e c o m em o r ea n dm o r e e n r i c h i n g ， m e a n w h i l et h ea p p l i c a t i o n sa c r o s sd i f f e r e n tf i e l d so ft h ew e bs e r v i c e b e c o m ew i d ei n c r e a s i n g l y l o t so fu d d ir e g i s t r i e se x i s ti na u t o n o m o u s d o m a i n ，s ot h a tr e a l i z ew e bs e r v i c e s s e a r c h ，d i s c o v e r y ，i n t e g r a t i o n ，a n d c l a s s i f i c a t i o n ，w h i c hw i l lb e c o m ea sc h a l l e n g e da sw e bp a g e ss e a r c h f o r t h es a k eo fe x p l o s i v ei n c r e a s eo ft h en u m b e ro ft h ew e bs e r v i c e s ，al a r g e n u m b e ro fw e bs e r v i c e sw i t hs i m i l a rf u n c t i o ne x i s ti nt h ei n t e m e ts e r v i c e v i r t u a lc o m m u n i t y ，s oh o wt ou t i l i z eq o s ( q u a l i t yo fs e r v i c e ) a t t r i b u t i o n s t os e l e c ta d v e r t i s i n gs e r v i c e si so n eo fk e yt e c h n o l o g i e so fw e bs e r v i c e c o m p o s i t i o n 。i na l l ，i nt h ed i s t r i b u t e d ，i s o m e r o u sa n da u t o n o m o u s - c o u p l e d e n v i r o n m e n t ，t h eq u a l i t yg u a r a n t e eo fw e bs e r v i c ec o m p o s i t i o nh a s a f f e c t e dt h em e t h o d so ft h ew e bs e r v i c ec o m p o s i t i o np r i m a r i l y t w om a i np r o b l e m sh a v eb e e nt a c k l e du n d e rt h ec i r c u m s t a n c eo f w e b o n ei sh o wt os e a r c ha n dd i s c o v e rw e bs e r v i c e sa c r o s sm u l t i p l e u d d i ，a n dt h eo t h e ri sh o wt op r o v i d et h ea p p l i c a t i o n s 谢t l lq u a l i t y g u a r a n t e ea c c o r d i n gt ot h ep r o v i d e r s r e q u i r e m e n t s a i m i n ga tt h ea b o v e p r o b l e m s ，s e r v i c em a n a g e m e n tf r a m e w o r ka n dr e s o u r c em a n a g e m e n t c o m p o n e n t - - w e b j e tr e p o s i t o r yb u i l d e r ( a c r o s sm u l t i p l eu d d i ) h a sb e e n p r o p o s e d a tt h es a m et i m et h es t r a t e g yo fh o wt os e a r c ha n dd i s c o v e r s e r v i c e sh a sb e e na l s op u tf o r w a r d o nt h eb a s i so ft h ef r a m e w o r k ，a q o s - b a s e d a r c h i t e c t u r e o fw e bs e r v i c e d i s c o v e r y a n d c o m p o s i t i o n w w e b j e th a sb e e nb r o u g h tf o r w a r d a n dw e b j e ti sd e s i g n e d f o rp u b l i c a t i o n ，m a n a g e m e n t ，d i s c o v e r yo ft h es e r v i c e s ，o p t i m i z a t i o np r i o r t ot h ec o m p o s i t i o na n df a u l t t o l e r a n c ea tt h er u n n i n gt i m e p o i n t i n ga tt h eu n c e r t a i n t y0 1 n o to ft h eu s e r s p r e f e r e n c e s ，b a s e d s e l f - a d j u s t i n gj u d g r n e n tm a t r i x a n dt h ei n t e r v a lj u d g m e n tm a t r i x ，t h e m e t h o dc o m p u t i n gt h eq o sa t t r i b u t i o nw e i g h t sh a sb e e np r o p o s e d t o r e a l i z et h eg l o b a lo p t i m i z a t i o no fw e bs e r v i c ec o m p o s i t i o n ，a0 - 1 h e u r i s t i ca l g o r i t h mh a sb e e ni m p l e m e n t e d a d d i t i o n a l l y , c o m p a r e d 谢n l t h eb r a n c hb o u n d i n gm e t h o do fi n t e g e rp r o g r a m m i n ga n dg a s ( g e n e a l g o r i t h m s ) u n d e rt h ed i f f e r e n tr u n n i n ge n v i r o n m e n t s ，t h ea d v a n t a g e so f o 一1h e u r i s t i ca l g o r i t h mh a v eb e e nv e r i f i e d c u r r e n t l y , l i t t l eo p t i m i z a t i o n m o d e l so fw e bs e r v i c ec o m p o s i t i o na l l o wf o rd y n a m i cc o m m e r c ea l l i a n c e o ft h es e r v i c e si nt h em a n a g e m e n to ft h es u p p l yc h a i n s t oi m p r o v et h e d i s a d v a n t a g e s ，n o n l i n e a ro p t i m i z a t i o nm o d e lo fw e bs e r v i c ec o m p o s i t i o n s u p p o r t i n gs u p p l yc h a i nm a n a g e m e n th a sb e e np u tf o r w a r d ，a sw e l l ，t h e o p t i m i z a t i o ns t r a t e g y f o rg a sh a sb e e nb r o u g h tf o r w a r d a tl a s t , p r a c t i c a b i l i t yo f t h es e r v i c ea l l i a n c em o d e l sh a sb e e np r o v e dt h r o u g hs o m e e x p e r i m e n t s k e y w o r d ：q o s ，s e r v i c es e a r c h ，0 1p r o g r a m m i n g ，g a s ，s e r v i c e c o m p o s i t i o n ，s e r v i c ea l l i a n c e i i i 附录3 学位论文原创性声明与版权使用授权书 湖南师范大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究工作所取得的成果。除文中已经注明引用的内容外，本论 文不含任何其他个人或集体已经发表或撰写过的作品成果。对本文的 研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人 完全意识到本声明的法律结果由本人承担。 学位论文作者签名：两留屏冲7 年7 1 月，l 日 f 7 湖南师范大学学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定， 同意学校保留并向国家有关部门或机构送交论文的复印件和电子版， 允许论文被查阅和借阅。本人授权湖南师范大学可以将本学位论文的 全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存和汇编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密眦 ( 请在以上相应方框内打“ ”) 作者签名：万鲤牟日期：埘吵年f 月乙日 导师签名：南吞u 乌日期：口哆年，月沈日 基于q o s 的服务发现与服务组合研究 1 1 研究背景 第一章绪论 面向服务的计算 1 】是松耦合、开放异构环境中分布应用的通用计 算模型，w e b 服务是近年来提出的面向服务的新型体系结构 2 ，它在 现有的各种异构平台基础上构筑一个通用的与平台无关、语言无关的 软件层，具有软件虚拟化、体系结构松耦合化、结构动态构造化 3 特点。以x m l 为基础和核心的w e b 服务是一种部署在w e b 上的自包 含、自描述、模块化的应用，它通过u d d i ，w s d l ，s o a p 等协议在 w e b 上被描述、发布、查找以及调用【4 】。 伴随着网络信息的持续快速发展，w e b 服务资源越来越丰富，w e b 服务的应用所跨越的领域越来越广泛，致使网络和系统平台中出现了 资源过载。出于安全、服务质量等问题考虑，在不同网络服务虚拟社 区，服务提供者都会将自己的w e b 服务发布不同的共有的、私有或半 私有的u d d i 注册中心中 5 】。大规模的u d d i 注册中心存在于各个自 治域中，如何有效的搜索发现、管理、分类这些w e b 服务将会如同 w 曲网页搜索一样变得具有挑战性。 在面向服务的分布、异构和自治松耦合计算环境中，w e b 服务组 合的质量保证已是服务组合方法优劣的重要影响因素。未解决的服务 质量( q o s ) f 司题会导致重要的事务性应用程序遭受无法接受的性能下 降 6 】。在网络服务虚拟社区存在大量的功能重叠或相同的w e b 服务 7 】，在服务组合之前，需要对服务组合进行局部或全局优化，采用何 种优化算法与策略对保障w e b 服务组合的质量起到了决定性的作用。 在服务组合时，往往需要考虑商业策略或更多的因素，建立怎样的计 算模型，采用的何种计算方法来更快、更优的实现高质量的服务组合 也将是一个关键的问题。 硕士学位论文 1 2 研究现状 1 2 1 基于u d d i 的服务发现的研究 服务注册是w r e b 服务的分类和目录的基础。现有的w r e b 服务注册信 息的存储有u d d i ，e b x m l 2 1 等方法。u d d i 注册中心采用目录的方 式存储服务提供者发布的w - e b 服务的服务信息及其商业信，n 8 。u d d i 是由m i c r o s o f t ，i b m ，a r i b a 9 兴起构建的，且被数百计其他企业所认 可，是现行的服务发布与注册的唯一工业标准。u d d i 资源库是使用基 于关键字的搜索方法来分享它的体系的，且支持层次化分类。u d d i 除了搜索能力的局限外，其他的最大的局限和缺点是现有的u d d i 标 准。这些局限包括： 1 ) u d d i 仅用于w e b 服务发现； 2 ) u d d i 注册是自愿的且其风险是被动的； 3 ) u d d i 不能为其含有的信息的有效性和质量提供任何保证； 4 ) u d d i 和当前的w e b 是断开的； 5 ) u d d i 不能为注册的w e b 服务提供服务质量( q o s ) 的度量，这 能为客户选择合适的、b 服务提供有益的信息； 。 6 ) u d d i 未能很明确的定义服务提供者能广告定价模型； 7 ) u d d i 即不能维持也不能提供任何w e b 服务生命周期信息。 尽管u d d i 具有只支持一维搜索且基于布尔模型的关键字查询技术 的缺点，但是现阶段它仍是服务发布与注册的首选。现有服务发现的 研究大都是在标准的u d d i 上展开的 1 0 ，1 1 ，1 2 】。 根据服务拓扑结构的不同，服务发现的方法可以分为三种类型：( 1 ) 集中式方法；( 2 ) 分散式方法；( 3 ) 混合式方法 1 3 】。许多的研究者致力 于集中式的u d d i 注册中心 1 4 ，1 5 ，1 6 】上的服务发现的研究。集中式方 法中，所有的服务都使用统一的u d d i 注册表，任何服务都需要向该注 册中心注册才能被别人检索、共享。集中式方法中服务种类多，数量 基于q o s 的服务发现与服务组合研究 大，可提供更好的查全率，但当服务数量急剧增加时，会遇到与中心 式系统相关联的问题，如单点失效，性能瓶颈等。分散式方法允许有 多个本地注册中心，本地的服务只需要在本地注册。分散式的u d d i 注册中心额外的增加了有效查询w e b 服务的复杂性，但降低了本地注 册中心的复杂性。当新的操作系统、构件、a p i s 被安装内置的功能或 工具来使得组织或企业能在内网或外网上发布他们自己的u d d i 注册 中心时，分散式的u d d i 注册中心会变得越来越实际【l o 】。分散式的 u d d i 注册中心不提供统一的服务注册。混合式方法是前面两种方法的 结合，从而兼具两者的优缺点。 其他的研究注重于服务发现方法的研究，文【2 0 】在p 2 p 框架基础来 进行服务发现和排序，文 2 7 ，2 8 ，6 0 提供了一个基于w e b 服务声誉的概 念性模型，文 2 9 】提出了基于关键字的搜索引擎来查找w e b j 艮务。然 而这些方法都仅给出有限的搜索方法集( i e 根据业务命名，业务位置 来搜索，e t c ) 并试图应用传统的i r 技术，这是不能适用于服务发现的， 因w e b 服务通常包含或提供非常简要的文本描述，不利于文档检索。 而通常w e b 服务的结构是复杂的且只提供很小部分的文档。 1 - 2 2 支持多u d d i 的服务发现的架构研究 集中式的u d d i 策略显然已经不能满足现在的需要，因此现在有一 些学者开始研究关于m u l t i u d d i 注册中心的服务发现问题。文【5 ，1 9 ，2 0 】 注重于由多个公有私有的注册中心来构成的注册联盟，并基于 m e t e o r - s 提升其发现方法。m e t e o r - s 提供了发现机制，在联盟注 册中心的基础上发布w e b 服务，但是这个方案未能进一步很清楚的提 出搜索技术，而这个恰恰是定位合适的业务组件的本质所在。m w s d i 架构要求多个u d d i 注册中心要保证数据一致性，而要实时保证数据副 本间的一致性的开销是非常大的。更进一步的，拥有联盟注册中心的 环境潜在的使得提供的策略不一致，这将对实际的导向性查询产生很 硕士学位论文 大的影响。更有甚者，联盟注册环境中执行服务发现操作时，因结构 的冗余，将增加额外的处理时间，使得在执行时间上的性能变得很差。 文 1 1 ，1 7 ，18 】基于现有的规范与协议提出了w e bs e r v i c e s r e p o s i t o r yb u i l d e r ( w s r b ) 架构，提出的w e b 服务爬虫引擎w s c e g 邕主 动的访问u d d i 注册中心，将w e b 服务资源和描述文档聚合到w e b 服务 存储库中。w s c e 能便利于w e b 服务参考信息、资源、描述文档的聚 合并提供一个定义良好的可用的且关于如何发现w e b 服务访问模式。 w s c e 方便的建立w e b 服务搜索引擎，且服务提供者将能看到这些服 务，同时客户将有适当的工具来实行高级的搜索查询。这将为客户端 提供一个标准的、统一的访问点来获得分布式的u d d i 的w e b 服务，较 临时手工的访问各大u d d i 注册中心的来收集w e b 服务信息的策略获 得了很快的查询响应时间。但是未能提出更精确的服务质量生命周期 的管理方法，也未提出合理的服务匹配分类方法，同时其设计的爬虫 搜索策略在搜索完服务信息后仍将保留每个服务对应一个爬虫进程， 这样会是对各u d d i 注册中心的一个性能上的巨大考验，长时间加重其 性能负荷。 1 2 3w e b 服务的q o s 模型研究 从最广泛接受的观点上来看，软件的非功能性属性应该包括以下方 面：性能、可重用性、可维护性、安全性、可靠性和可用性。其他的 非功能性属性还有可修改性、可移植性、灵活性、可扩展性和适应性 等 2 2 】。w e b 服务的q o s 是由其构件服务的q o s 所决定的，而且还受 通讯链接的影响，所以q o s 应该从服务请求者的立场来描述与测试。 文 2 3 1 中把q o s 分为以下四种类型： 运行时相关的服务质量属性 伸缩性( s c a l a b i l i t y ) 、容量( c a p a c i t y ) 、响应时间( r e s p o n s et i m e ) 、延 迟( l a t e n c y ) 、吞吐率( t h r o u g h p u t ) 、可靠性( r e l i a b i l i t y ) 、可用性 基于q o s 的服务发现与服务组合研究 ( a v a i l a b i l i t y ) 、鲁棒性灵活性( r o b u s t n e s s f l e x i b i l i t y ) 、异常处理 ( e x c e p t i o nh a n d l i n g ) 和准确性( a c c u r a c y ) 事务支持( t r a n s a c t i o ns u p p o r t ) 相关的服务质量属性 事务完整性( t r a n s a c t i o ni n t e g r i t y ) 配置管理( c o n f i g u r a t i o nm a n a g e m e n t ) 和开销( c o s 0 相关服务质 量属性 规范性( r e g u l a t o r y ) ，对标准的支持( s u p p o r ts t a n d a r d ) ，稳定性变更 周期( s t a b i l i t y c h a n g ec y c l e ) ，开销( c o s t ) 和完整性( c o m p l e t e n e s s ) 安全( s e c u r i t y ) 相关的服务质量属性 身份验证( a u t h e n t i c a t i o n ) 、授权( a u t h o r i z a t i o n ) 、保密性 ( c o n f i d e n t i a l i t y ) 、可记账性( a c c o u n t a b i l i t y ) 、可追踪性( t r a c e a b i l i t y ) 、 可审计性( a u d i t a b i l i t y ) 、数据加密程度( d a t ae n c r y p t i o n ) 和不可否认性 ( n o n r e p u d i a t i o n ) 在文献【2 4 】中，作者根据质量度量的值的特征及其获取方式将w e b 服务的服务质量因子分成静态、统计和动态三种类型： 静态因子( s t a t i cf a c t o r s ) 它们不经常发生变化，如w e b 服务的规范。l 生( r e g u l a t o r y ) 和安全性 ( s e c u r i t y ) 。 动态因子( d y n a m i cf a c t o r s ) 它们反映了那些随着特定环境( 如网络负载) 的变化而改变的服务 质量信息，包括服务可用性( s e r v i c ea v a i l a b i l i t y ) ，网络可用。i 生( n e t w o r k a v a i l a b i l i t y ) 和执行时间( e x e c u t i o nd u r a t i o n ) 统计因子( s t a t i s t i c a lf a c t o r s ) 它们根据服务的统计数据计算得到，包括服务可靠性( s e r v i c e r e l i a b i l i t y ) ，网络可靠性( n e 铆o r kr e l i a b i l i t y ) ，执行可靠性( e x e c u t i o n r e l i a b i l i t y ) 和信誉度( r e p u t a t i o n ) 针对如此之多的服务质量，有些服务质量带有很大的主观性，比如 环境的q o s ，它可能依赖于i s p 提供商的网络环境和用户终端接收的 硕士学位论文 速度。为此，本文中主要针对系统通用级的q o s 标准，采用一个可扩 展的w e b 服务q o s 模型，采用的q o s 标准有【7 ，2 5 - ( 1 ) 执行价格 e x e c u t i o np r i c e ；( 2 ) 执行的响应时间e x e c u t i o nd u r a t i o nt i m e ； ( 3 ) 可 靠性r e l i a b i l i t y ；( 4 ) 可用性a v a i l a b i l i t y 。 1 2 4 支持q o s 的服务发现与服务组合研究 服务发现是一种对服务组合的候选服务集合进行构造的过程，服务 发现所选择服务的质量的好坏对服务组合的结果将产生直接的影响。 考虑q o s 的服务发现与服务组合的选择算法的优化是服务计算领域 研究热点。 文【2 3 在u d d i v 2 0 1 3 1 的基础上实现了一种基于q o s 的服务发现 模型，在原有的s o a 架构的基础上加入了w e bs e r v i c eq o sc e r t i f i e r 模块，并给出q o s 属性的分类与定义。文 2 7 ，3 0 ，31 ，3 3 都是在服务发 现阶段考虑w e b 服务的单个或多个q o s 属性，加入新的组件对服务 进行过滤，将符合要求的w e b 服务纳入w e b 服务候选集合中，将下 一步的将要进行服务组合的集合优选，降低服务组合的复杂性。文 1 8 】 在提出的w s r b 架构中考虑服务质量，以一种开发而透明的方式考虑 w e b 服务的q o s 属性，如响应时间、流通量、可用性、可达性、价格 等属性，使得客户端能根据q o s 偏好来选择w e b 服务。 w e b 服务组合的质量保证已是服务组合方法优劣的重要影响因素。 未解决的q o s 问题会导致重要的事务性应用程序遭受无法接受的性 能下降【6 。w e b 服务组合中一般有两种服务选择方法，分别叫做局部 最优策略和全局计划策略【7 】。 局部最优策略通常采用多属性决策 3 4 】方法设计候选服务打分机 制，为每个活动的候选服务集合的w e b 服务进行排序，从而选择排序 最靠前的w e b 服务执行当前活动。一般而言，每个活动的候选服务的 数目并不大，因此基于多属性决策的方法是有效的。这方面的已有的 基于q o s 的服务发现与服务组合研究 研究工作有【7 ，3 5 等。 现在研究的全局计划策略所采用的方法主要分为三类：精确求解方 法 7 ，3 6 ，3 7 】、随机与演化方法 3 8 ，3 9 ，4 0 ，4 1 ，4 2 ，4 9 】、启发式方法 3 5 ，4 3 ，4 4 ，4 5 。 文献 7 ，3 6 提出了采用整线性规划方法求取组合服务综合质量最优 的方案。两个工作都要需要将目标函数和约束线性化。文 7 】主要考虑 执行价格、响应时间、可用性、可靠性和声誉五维服务质量属性，可 用性、可靠性和声誉的聚集函数是非线性化的，因此采用对数法则将 乘法的聚集函数线性化。作者认为他的模型可扩展处理任何其他类似 的属性。文 3 6 提出了处理更一般的约束标准，比如服务依赖和用户 偏好。然而，这两者都需要依赖商用的规划工具包，其整数规划求解 方法都是采用分支定界算法来求解，这是一个n - p 难的算法，因此其 求解效率与服务组合的规模和候选服务集合的大小直接相关，在有着 大量w e b 服务的动态实时场景下，算法的效率不能实用。 文 3 7 贝j j 综合考虑了系统负载状况和价格开销，定义了相应的效用 函数，在满足组合服务的响应时间约束条件下寻求效用的最大化，其 求解思路是将问题转化为“多选择背包问题”，并使用p i s i n g e r 算法 4 6 】 求解多选择背包问题；另一种求解思路是将问题转化为带约束最短路 径问题，提出了受约束的b e l l m a n f o r d 算法( c b f 4 7 ) 和受约束最短路 径算法( c s p ) 解这个问题。文 3 7 】解决的是单个约束的服务组合优化问 题，在此基础上，作者在文献畔 中提出了可以处理多个约束的服务 组合优化方法。其求解思路是在问题建模为多维多选择0 1 背包问题 ( m u l t i d i m e n s i o nm u l t i c h o i c e0 1k n a p s a c kp r o b l e m ，m m k p ) i ；- 题， m m k p 是n p 难的 4 8 】，其算法的效率也是有待斟酌的。 3 8 ，3 9 ，4 0 ，4 9 采用遗传算法解决服务组合优化问题。 3 9 ，4 0 试验结 果显示遗传算法比线性整数规划在候选服务集合和服务组合任务数规 模增大时表现了较好性能和可缩放性。除了组合的方法，他们也提出 了一个重计划算法计算q o s 估计值和在运行时测量到的q o s 值的偏 硕士学位论文 差。当偏差高于阈值时，算法触发重计划过程。金海等 2 8 】面向服务 网格提出一种基于模拟退火的算法求解使得组合服务性价比最高的组 合方案。 【3 5 ，4 3 基于相对执行概率讨论组合服务q o s 的聚合规则研究了组 合服务q o s 的计算方法，针对结构化流程模型，提出归约树作为结构 相关的多维q o s 聚合模型。之后针对满足多维质量约束的组合方案搜 索问题，提出基于归约树的基本搜索算法m s c se x 和启发搜索算法 m s c sh e u ，并进行算法复杂度分析与全面的实验模拟；基于用户偏 好以评价组合方案的综合质量，提出启发式算法p m c s ch e u 求解组 合方案综合质量优化问题，并通过模拟实验测试算法的性能与开销。 实验表明，m c s ch e u 算法与p m c s ch e u 算法利用简单而有效的 启发信息能够快速寻找到满足优化目标的可行解和近优解，其实际复 杂度接近于线性。 文1 4 5 1 采用启发式方法：首先服务组合问题用混合整数规划公式描 述，求解该公式的松弛线性规划解；接着，采用回溯算法有效地求解 原来的非松弛解，进一步采用辅助的元策略改进启发式方法。比较了 启发式方法与线性整数规划的性能，仿真结果表明启发式方法在求得 最优解的同时，执行效率也是极为优秀的，但是，其测试结果只给出 满足用户约束为6 8 以下的测试数据。 1 2 1 5 基于商业相关信息的w e b 服务组合研究 供应链管理是当前管理领域中流行的焦点，所谓供应链，就是供应 商、生产商、分销商、零售商、运输商等一系列企业组成的价值增值 链。基于w e bs e r v i c e s 技术的供应链是由很多企业提供的广告服务共 同组成，它们之间的联系形式也不再是单纯的“链 的形式，而是复 杂的“供应网络”( 虚拟企业) 。供应链管理实现了物流与信息流的高 效集成，而基于w e bs e r v i c e s 的服务组合平台也实现了各跨企业的广 基于q o s 的服务发现与服务组合研究 告服务的协同商务( c o l l a b o r a t i v ec o l l l l t l e r c e ) 。现有的基于q o s 的服务 组合方法大都未考虑服务提供商间的商业联盟关系，因而不能应用于 现代供应链所形成的服务组合场景。文献 4 9 ，5 0 提出了w e bs e r v i c e s 组合管理框架，在进行全局最优组合时提出了服务联盟相关的概念， 但是没有给出具体的模型和方案。文献 5 1 】提出了支持组合服务选取 的q o s 模型的层次结构，并建立了基于组合服务的商业实体关联度和 统计关联度的组合服务选取模型，但是没有明确的给出基于商业实体 关联度的计算方法。而这些文献的研究还是远远不能满足基于供应链 管理的服务相关问题。 1 3 存在的问题 针对以上研究现状的分析，w e b 服务发现领域和支持q o s 属性的 w e b 服务组合领域的研究存在如下问题： ( 1 ) 在服务发现领域，基于多u d d i 的服务发现问题是一个比较新 颖且有挑战性的问题，如何搜索监控各u d d i 上有用的服务信息及这 些服务信息实现基于q o s 生命周期的管理架构研究不够。文 1 1 ，1 7 ，1 8 给这个领域的研究提供了很好的方法，但w s c e 所设计爬虫策略将会 造成u d d i 注册中心的负荷过载，以致出现性能瓶颈问题。现有的文 献大多对u d d i 上的服务信息挖掘、查找与分类的研究不够系统。实 际上在u d d i 中能通过w e b 服务各阶段的变化能获得极其有用的信 息，加入q o s 信息后能实现w e b 服务生命周期的管理。现有的文献 大多未考虑很好韵方案这个问题。 ( 2 ) 在服务组合的预先优化阶段，大多数全局计划策略的研究在优 化算法的通用性或求解效率不够理想，且各文献中q o s 属性的权重都 是作者直接赋值的，这是不能真实地反映用户偏好及历史数据的客观 性。例如文献 7 ，3 6 是使用整数规划进行求解，需要依赖商用的规划工 具包，而且其求解效率与与服务组合的规模和候选服务集合的大小直 硕士学位论文 接相关，在有着大量w e b 服务的动态实时场景下，算法的效率有所下 降。随机与演化方法在全局优化上取得很明显的成绩，但是其本身是 非确定性算法；其求解效率也不能达到最优。已有的启发式方法可靠 性和复杂度很多没有得到分析与验证。 ( 3 ) 现有的基于q o s 的服务组合方法大都未考虑服务提供商间的商 业联盟关系，因而不能应用于现代供应链所形成的服务组合场景。现 在仅 4 9 ，5 0 ，5l 】等文献涉及到服务相关问题，且未能建立合理的数学模 型来求解服务相关这类问题。这远远的不能满足基于动态联盟的供应 链管理的需求，从而使得w r e b 服务在电子商务领域的应用大打折扣。 1 4 本文工作 针对以上w e b 服务发现与组合研究中基于q o s 的生命周期管理及 跨多u d d i 注册中心的服务发现和服务组合的研究不足，本文提出了 跨多u d d i 注册中心的服务管理框架和资源管理构件w e b j e t r e p o s i t o r yb u i l d e r ，并在此基础上提出了基于q o s 的w e b 服务发现与 组合架构w e b j e t 。针对服务组合预先优化的算法低效性，研究并对比 各种算法提出o 1 启发式方法解决全局优化问题。考虑服务联盟场景， 为实现现代供应链式的自动化管理与组合，提出了新的模型，并采用 遗传算法来计算全局优化组合流程。本文主要的工作是： ( 1 ) 提出了跨多u d d i 注册中心的服务管理框架和资源管理构件 w e b j e tr e p o s i t o r yb u i l d e r ，提出各模块的详细设计。为避免服务爬虫 对u d d i 注册中心造成性能瓶颈，采用主从服务爬虫策略来搜索与监 控各u d d i 上的服务。 ( 2 ) 提出了支持q o s 管理的w e b 服务发现与组合架构w e b j e t ，给 出与w e b 服务的发布、管理、发现、组合前的预先优化与运行时容错 相关的各模块的功能设计。 ( 3 ) 针对服务请求者q o s 属性偏好的不确定性情况，构造区间判断 1 0 基于o o s 的服务发现与服务组合研究 矩阵，然后提出了一种近似逼近算法将区间判断矩阵近似逼近到点数 判断矩阵，这时的数字判断矩阵能通过一般的层次分析一次性计算出 满足服务请求者偏好的q o s 属性权重；针对服务请求者q o s 属性偏 好是确定性的情况，构造数字判断矩阵，采用自动修正判断矩阵的层 次分析法计算q o s 的权重。 ( 4 ) 服务组合优化问题的原模型是一个0 1 整数规划问题，这是一 个n p 难。本文提出了一种0 1 启发式方法，在不同的运行环境下对 比分支定界方法和遗传算法来验证0 - 1 启发式方法的有效性，并给出 了o 1 启发式方法在数据光滑场景下的时间复杂度。 ( 5 ) 基于商业联盟场景，提出了支持供应链管理的服务组合优化模 型，采用遗传算法实现组合的优化求解，通过实验验证模型的有效性。 1 5 论文结构 - 本文共分为六章： 第一章，绪论，主要介绍课题的背景、研究现状、本课题的研究内 容与目标、及论文的组织情况。 第二章，给出w e b 服务质量的属性定义和扩展的w s d l 的s c h e m a 描述。提出了跨多u d d i 注册中心的服务管理框架和资源管理构件 w e b j e tr e p o s i t o r yb u i l d e r ，提出各模块的详细设计。 第三章，提出了支持q o s 生命周期管理管理的w e b 服务发现与组 合架构w e b j e t ，给出与w e b 服务的发布、管理、发现、组合前的预 先优化与运行时容错相关的各模块的功能设计。 第四章，提出了根据服务请求者偏好的是否确定性分别采用区间判 断矩阵近似逼近数字判断矩阵近似算法和自动修正判断矩阵的层次分 析法计算q o s 偏好权重，并给出了实例分析。提出了服务组合优化模 ：型，给出了o 1 启发式全局求解方法，并通过模拟实验与o 1 整数规 划的分支定界方法和遗传算法进行运算时间、适应值等优化效果的对 硕士学位论文 比。 第五章，考虑服务联盟的现代供应链服务组合场景，提出了全局优 化的数学模型，并采用遗传算法求解最优服务组合。通过模拟实验验 证了模型的有效性。 第六章，总结与展望。 基于q o s 的服务发现与服务组合研究 第二章跨多u d d i 注册中心的w e b 服务资源管理框架 伴随着网络信息的持续快速发展和w r e b 服务的快速应用，w r e b 服务 资源越来越丰富，w r e b 服务的应用所跨越的领域越来越广泛。出于安 全、服务质量等问题考虑，在不同网络服务虚拟社区，服务提供者都 会将自己的w 曲服务发布在自己所属自治域中公有的、私有或半私有 的u d d i 注册中心中【5 】。大规模的u d d i 注册中心存在于各个自治域 中，如何有效的搜索发现、整合、分类这些w e b 服务将会如同w e b 网 页搜索一样变得具有挑战性。许多的研究者致力于集中式的u d d i 注册 中。l , 1 4 ，1 5 ，1 6 上的服务发现的研究。但当服务数量急剧增加时，会遇 到与中心式系统相关联的问题，如单点失效，性能瓶颈等。分散式的 u d d i 注册中心额外的增加了有效查询w e b 服务的复杂性，但不提供统 一的服务注册。因此混合式方法是前面两种方法的折中方案，从而兼 具两者的优缺点。现有的u d d i 不能提供信息的有效性和服务质量保 证，不能提供任何服务生命周期信息。同时现有的s o a 架构也不提供 基于商业联盟信息的服务组合，从而不能实现现代供应链的优化管理。 因此我们在现有u d d i 注册中心机制下，在发布w s d l 文档时增加q o s 信息和商业联盟信息。服务注册是w e b 服务的分类和目录的基础，为 消除分散式的u d d i 注册中心服务注册的语义不一致性，为每个客户端 提供统一的发布交互界面，在u d d i 注册中心中采用统一的服务分类方 法。基于多u d d i 注册中心，我f f j w e b j e t 上设计了新的w e b j e t r e p o s