（计算机科学与技术专业论文）基于改进遗传算法的支持qos的语义web服务选择.pdf

北京邮电大学硕士论文摘要 基于改进遗传算法的支持q o s 的 语义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 服务 组合的过程更智能化，组合结果也更精确。 目前网络上w e b 服务数量正以惊人的速度增长，存在众多可以完成相同或相 似功能的w e b 服务，而这些服务具有不同的非功能属性，即服务质量( q o s ) ， 如服务价格、执行时间、服务可用性、执行的可靠性等因素。因此在服务组合过 程中，如何基于服务的q o s 选择最符合用户需求的w e b 服务便成为了亟待解决 的问题。 本文对基于改进遗传算法的支持q o s 的语义w e b 服务选择进行了深入研究。 提出了一套q o s 本体设计模式，改进并扩展了语义w e b 服务描述语言o w l - s ， 基于此q o s 设计，本文提出了一种新型的服务选择算法，即改进的遗传算法。 此改进的遗传算法以服务的q o s 作为从一系列备选服务中选取最优服务的评价 参数，建立一个评价服务优劣的适应度函数，并将此函数值作为寻优的评价标准； 此算法采用关系矩阵编码方式，该矩阵具有表示多种类型服务组合的能力，同时 也解决了多个路径用同一种编码方式同时表示的问题：同时此算法采用并行的自 适应策略，进一步地提高了算法的效率以及收敛性、稳定性。 本文对改进的遗传算法进行实现，并且基于此算法设计并实现了服务选择原 型系统。测试说明使用此算法是相当有效的，采用此算法进行服务选择，可以缩 减选择时间，提高选择效率，同时也可保证选择最优结果的稳定性。 关键词语义w e b ：w e b 服务；服务选择；q o s ；遗传算法 北京邮电大学硕士论文 s e m a n t i c 胍bs e r v i c es e l e c t i o nb a s e do n i m p r o v e dg e n e t i ca l g o r i t h ms u p p o s i n gq o s a b s t r a c t a san e wd i s t r i b u t e dc o m p u t i n gm o d e l ，w e bs e r v i c eh a sg o t t e nt h ee x t r e m e a t t e n t i o no fa c a d e m ea n db u s i n e s sg r o u p s w e bs e r v i c ei sa l le s p e c i a lk i n d0 f a p p l i c a t i o nd e p l o y e do nt h ei n t e r n e t ，w h i c hf o l l o w sc e r t a i nt e c h n i c a ls p e c i f i c a t i o n s a n da c h i e v e sc e r t a i ni n t e n t i o n s i tp r o v i d e sa l le f f e c t i v es o l u t i o no ft h ed a t aa n d s e r v i c ei n t e g r a t i o n h o w e v e r , a t o m i cw e bs e r v i c ec a l lo n l yp r o v i d es i m p l ef u n c t i o n ， w h i c hc a n n o ts a t i s f yt h ec o m p l e xr e q u i r e m e n to fc o n s u m e r s s os e r v i c ec o m p o s i t i o n h a sb e e nr a i s e dt os o l v et h i sp r o b l e m t h ec o m p o s i t ew e bs e r v i c ei sm a d eo ft h ew e b s e r v i c ec o m p o n e n t sa n dt h ea t o m i cw e bs e r v i c e s ，a n di to f f e r sas i m p l ew a yf o rt h e c r e a t i o no fc o m p l e xa p p l i c a t i o n s t h er e c e n ts e r v i c ec o m p o s i t i o nm e t h o dl a c k st h e s e m a n t i ci n f o r m a t i o no fs e r v i c e s t h e r e f o r e t h e r ea r el e s si n t e l l i g e n ta n da u t o m a t i c c a p a b i l i t i e si nt h ep r o c e s s t e c h n i q u eo fs e m a n t i cw e bi si n t r o d u c e di no r d e rt o i m p r o v et h ev e r a c i t ya n de 伍c i e n c yo ft h es e r v i c ec o m p o s i t i o na n dm e e tt h e i n c r e a s i n gr e q u i r e m e n t so fc o n s u m e r s i tb r i n g sm o r ei n t e l l i g e n tp r o c e s sa n dm o r e a c c u r a t er e s u l to fs e r v i c ec o m p o s t i o nt h a tp u ts e m a n t i ci n f oi n t ot h ew e bs e r v i c e a tp r e s e n t ，t h eq u a n t i t yo ft h ew e bs e r v i c e si si n c r e a s i n gr a p i d l y h o w e v e rm a n y d i f f e r e n ts e r v i c e sw h i c hc a l ls a t i s f yt h ec u s t o m e r s f u n c t i o n a lr e q u i r e m e n t sh a v e d i f f e r e n tq u a l i t i e s ，s u c ha sp r i c e ，t i m e ，r e l i a b i l i t ya n dr e p u t a t i o n a c c o r d i n g l y , w em u s t f i n do u taw e bs e r v i c es e l e c t i o nm o d e lt os a t i s f y i n gt h eg l o b a ic o n s t r a i n t sb a s e do nt h e q u a l i t i e so fs e r v i c e s( q o s ) t h er e s e a r c hi sb a s e do nt h ep r o g r a mp i s o m w a r e ap 2 p b a s e di n t e l l i g e n t s e r v i c eo r i e n t e dm i d d l e w a r e w ei n v e s t i g a t et h ek e yt e c h n o l o g yo ft h es e m a n t i cw e b s e r v i c ea n db r i n gf o r w a r daq o so n t o l o g ym o d e l ，w h i c hi m p r o v e sa n de x t e n d st h e s e m a n t i cw e bs e r v i c ed e s c r i p t i o nl a n g u a g e0 w l - s b a s e do nt h i sq o sm o d e l ，an e w s e r v i c es e l e c t i o na l g o r i t h mi s b r o u g h to u t i m p r o v e dg e n e t i ca l g o r i t h m t h i s a l g o r i t h ms e tu paf i t n e s sf u n c t i o nb a s e do nq o st oe s t i m a t et h eq u a l i t i e so ft h e s e r v i c e s i ti n c l u d e sas p e c i a lr e l a t i o nm a t r i xc o d i n gs c h e m eo fc h r o m o s o m e st h a tc a n e x p r e s sa l lc o m p o s i t ep a t h ss i m u l t a n e o u s l y , w h i c hc a nn o tb e e x p r e s s e d s i m u l t a n e o u s l yb yt h eo n ed i m e n s i o nc o d i n gs c h e m e t h ea l g o r i t h mc a nr u no n l y o n c et os e l e c tt h eb e s tp a t hb e c a u s eo ft h i sm a t r i xc o d i n gs c h e m e ，w h i l eo t h e ro n e d i m e n s i o nc o d i n gs c h e m ea l g r o t h m sm u s tr u nf o rs e v e r a lt i m e s a i s op a r a l l e la n d a d a p t i v ep o l i c i e s a r e a d o p t e di n t h ea l g o r i t h m ，w h i c h i m p r o v e st h ee f f i c i e n c y , a s t r i n g e n c ya n ds t a b i l i t yo ft h ea l g o r i t h m a tt h ee n do ft h ep a p e r , e x p e r i m e n t so nq o s a w a r ew e bs e r v i c e ss e l e c t i o ns h o w t h a tt h ei m p r o v e dg e n e t i ca l g o r i t h mw i t ht h i sm a t r i xc o d i n gs c h e m ea n da d a p t i v e 北京邮电火学硕上论文a b s t r a c t p a r a l l e lp o l i c yi sv e r ye f f e c t i v e i tr e d u c e st h et o t a lt i m eo ft h es e l e c t i o np r o c e s s ， i m p r o v e st h es e l e c t i o ne f f i c i e n c ya n da l s o e n s u r e st h es t a b i l i t yo ft h es e l e c t i o nt o a d o p tt h i sa l g o r i t h m k e yw o r d ss e m a n t i cw e b ；w e bs e r v i c e ；s e r v i c es e l e c t i o n ；q o s a w a r e ；g e n e t i c a l g o r i t h m 北京邮电大学硕上论文 声明 独创性( 或创新性) 声明 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或其他 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名： 丕驾压日期：塑! 三：三2 ： 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即： 研究生在校攻读学位期间论文工作的知识产权单位属北京邮电大学。学校有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借 阅；学校可以公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它 复制手段保存、汇编学位论文。( 保密的学位论文在解密后遵守此规定) 保密论文注释：本学位论文属于保密在一年解密后适用本授权书。非保密论 文注释：本学位论文不属于保密范围，适用本授权书。 本人签名：南整：日期：迎呈：垒三1 ： 导师签名：盔盈 日期：力翌星：主：2 z 北京邮电大学硕士论文 第1 章 第1 章绪论 本章引出本文的研究背景，介绍语义w e b 服务的产生、w e b 服务组合以及服 务选择等基本概念，阐述语义w e b 服务以及服务选择的相关研究，第三节将介 绍本文的研究重点，最后介绍本文的组织结构和主要内容。 1 1 研究背景 w e b 服务作为一种新兴的分布式计算模型，近年来得到了学术界以及工业界 的极大关注。w e b 服务是自包含的、模块化的应用程序，可以在网络中被描述、 发布、查找以及调用；是基于网络的、分布式的模块化组件，它执行特定的任务， 遵守具体的技术规范，因而能与其他兼容的组件进行互操作；是由企业发布的能 完成其特别业务需求的在线应用服务，其他企业和应用软件能够通过i n t e r n e t 访 问并使用这些应用服务。w e b 服务是一种部署在w e b 上的对象，它们具有对象 技术所承诺的所有优点。同时，w e b 服务建立在以x m l 为主的、开放的w e b 规 范技术基础上，因此具有比任何现有的对象技术更好的开放性，是建立可互操作 的分布式应用的新平台。 随着w e b 服务技术的日益成熟，越来越多的稳定易用w e b 服务共享在网络 上。但单个的w e b 服务能够提供的功能有限，为了更加充分地利用共享的w e b 服务，有必要将共享的w e b 服务组合起来，提供更为强大的服务功能，并加快 系统开发的速度，快速满足用户需求。组合服务则是将多个w e b 服务通过某种 机制协同工作，来实现一个应用目标，满足用户的特定需求，包括企业应用的集 成。w e b 服务在i n t e r n e t 上提供了与平台和网络无关的操作，一个用户( 服务请 求者) 可以在服务注册中心查找它需要使用的服务，然后从查找结果中选择合适 的服务来使用。当一个用户的服务需求不能被任何可用的服务满足时，通过组合 已有的w e b 服务有可能提供用户所需的服务。 但是，现有的组合服务由于缺乏对w e b 服务的语义信息的描述，从而导致 其智能化以及自动化程度不高，无论在精确度、查全率还是性能上都无法满足人 们日益增长的需求。将语义w e b 技术引入w e b 服务便可以在一定程度上解决w e b 服务的这个问题。 语义w e b 是由w w w 的创始人t i mb e m e r s l e e 在2 0 0 1 年正式提出的l l j ， 它是对w e b 本质的变革，它的主要任务是使数据能被计算机自动的处理和理解， 其最终目标是让计算机可以在这些海量信息中找到人所需要的任何信息，从而将 w e b 中现存的信息发展成一个巨大的全球信息库、知识库。它研究的主要目的就 是扩展当前的w e b ，使得网络中的信息具有语义，能够被计算机理解，便于人和 计算机之间的交互与合作，其研究重点就是如何把信息表示为计算机能够理解和 北京邮电大学硕士论文第1 章 处理的形式，即带有语义。t i mb e r n e r s l e e 给出了语义w e b 中的层次结构关系， 它主要基于x m l 和r d f r d f s ，并在此之上构建本体和逻辑推理规则，以完成 基于语义的知识表示和推理，从而能够为计算机所理解和处理。利用语义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 服务应用在深度和广度上的发展。 因此，对基于非功能属性的w e b 服务选择的深入研究，不仅具有重要的理 论意义，还具有重大的实用价值，它是w e b 服务研究领域中的一个重要的研究 分支。 1 2 研究现状 1 2 1 语义w e b 服务研究现状 目前语义w e b 服务的研究机构及进展如下1 2 j ： ( 1 ) d a m l ( d a r p a a g e n tm a r k u pl a n g u a g e ) 项目，开始于2 0 0 0 年8 月， 主要标准有d a m l + o i l 和d a m l - s ，其中d a m l - s 从1 0 版本后改称o w l - s 。 ( 2 ) w 3 c 制定了一系列的语义网技术规范，与语义w e b 服务相关的主要 有x m l 、r d f 、o w l 、s e m a n t i cw e b 和w e bs e r v i c e s 。 w 3 c 成立的语义w e b 服务兴趣小组( s e m a n t i cw e bs e r v i c e si n t e r e s tg r o u p ) 提出一系列标准，主要有：o w l w e bo n t o l o g yl a n g u a g ef o rs e r v i c e s ( o w l - s ) 、 w e bs e r v i c em o d e l i n go n t o l o g y ( w s m o ) 、s e m a n t i cw e bs e r v i c e sf r a m e w o r k ( s w s f ) 以及w e bs e r v i c es e m a n t i c s w s d l - s 。其中，o w l - s 是由d a m l 发 布的，s w s f 是由d a m l 的语义w e b 服务语言委员会提交而来，w s m o 是由 w s m o 工作小组( e s s iw s m ow o r k i n gg r o u p ) 的成员向w 3 c 提供并授权的， w s d l - s 是由i b m 和佐治亚大学向w 3 c 提交的。 w 3 c 成立的w e b 服务语义框架工作组( w 3 cw o r k s h o po nf r a m e w o r k sf o r s e m a n t i c si nw e bs e r v i c e s ) ，主要对语义网背景技术、w e b 服务背景技术、注册 2 北京邮电人学硕士论文第1 章 库、分类表和搜索机制、推理语言、w e b 服务本体、w e b 服务编排和商业流程等 均进行了研究并制定相应规范。 ( 3 ) 佐治亚大学大规模分布式信息系统测试室( l s d i sl a b ) 的m e t e o r s 项目，该项目致力于为一些标准扩展语义w e b 技术，以实现更大的动态性和可 伸缩性。m e t e o r s 研究人员与i b m 合作，向w 3 c 提交了w s d l 厂s 。 ( 4 ) 国内各大高校以及组织也对语义w e b 进行了深入研究，如清华只知识 工程研究室的s e w s i p ( s e m a n t i cb a s e dw e bs e r v i c e si n t e g r a t i o ni np 2 p ) 项目以 及中科院软件所的语义w e b 技术与本体项目。 此外，还有欧盟i s t 项目中的s w w s ( s e m a n t i cw e be n a b l e dw e bs e r v i c e s ) 子项目和i r s ( i n t e r n e tr e a s o n i n gs e r v i c e ) 语义w e b 服务框架等项目。除了学 术界，业界技术厂商如i b m 、s u n 、m i c r o s o f t 等都对其表示了密切关注，纷纷加 入到语义w e b 服务的研究和开发中。 1 2 2w e b 服务选择研究现状 目前对于w e b 服务选择主要采用的是基于服务质量( q o s ) 的服务选择方法， 在基于q o s 的服务选择中，有基于q o s 语义的【孓5 1 ，也有基于q o s 属性计算的1 6 - 1 们， 而q o s 属性计算方法可以很好满足用户对组合服务的全局限制，所以q o s 属性 计算方法在服务选择方法中占有相当比例。 显然，基于全局q o s 限制从大量组合w e b 服务中选出最优服务属于组合优 化范畴，主要有以下几种解决方法： ( 1 ) 穷举算法 6 - s l 此算法非常直接，将所有的服务组合路径进行一一列举，比较它们的q o s 等非功能属性值并从中选出最优。使用此方法一定会产生最佳解决方案，只是以 时间和内存为代价。假设一条组合路径中有k 个任务，第i 个任务的候选服务有 l ( i ) 个，则此算法时间复杂度为： k o ( 几l ( i ) ) 冬f 可见对于服务选择此类n p 难问题【9 1 ，采用穷尽计算的组合优化方法存在计 算量相对较大的弊端，其内存以及时间的耗费会随着问题空间的增加而快速增 长。所以此算法不能够很好地满足服务选择中的复杂要求。 ( 2 ) 线性规划算法 针对穷举算法计算量过大以及不实际的缺点，文献1 1 1 1 提出了一种基于线性 规划的方法，此方法可用来选择一个最优解决方案，且不产生所有可能的解决方 案。 此算法要求目标函数和约束条件均为线性的，通过调整一些变量的值求出最 3 北京邮电大学硕士论文第1 章 大( 小) 化目标函数值。为了保证约束条件等为线性，该算法则必须在服务质量 属性的计算上作比较繁琐的处理，这样导致了约束条件的含义有所转换，同时增 加了求解复杂度。此外，此算法只能够处理只有一个执行路径的情况，若存在多 条路径，则需运行多次。并且此算法只能够处理执行路径中只有一种组合模型( 顺 序) 的情况，若存在其他情形的路径( 如选择、循环等) ，需要采用其他算法来 对这些路径进行变换，将这些复杂的路径最终递归为顺序型路径，这样增加了算 法的计算量，同时也大大增加了算法的复杂度。 ( 3 ) 模拟退火算法 模拟退火算法【l 捌( s i m u l a t e da n n e a l i n g ，简称s a ) 的思想最早由m e t r o p o l i s 等( 1 9 5 3 ) 提出，1 9 8 3 年硒r k p a t r i c k 等将其用于组合组合优化问题。此算法核 心在于模仿热力学中液体的冻结或金属溶液的冷却与退火过程。 在规模相对较小的情况下，只要模拟过程足够充分，此算法可以概率1 收敛 到全局最优解，但当问题规模增大时，使用此算法找到最优解的概率随之减小， 找到最优解的可能性也变小。且模拟退火算法收敛速度慢，特别是在最优点附近 时尤为明显。对于多路径寻找多目标最优这类目标函数难于计算的复杂问题，要 使退火过程模拟得很充分，每一冷却步的状态分布平衡需耗费很长的时间，从而 算法的运行时间较长。并且此算法属于单点寻优，对存在多个最优解的问题并不 具有优势，而实际寻找最优路径时很有可能存在多路径最优情况，所以此算法不 能够满足服务选择中的效率要求。 ( 4 ) 遗传算法 与上述算法相比较，遗传算法更适合于解决此类n p 难问题1 1 3 j ，已有的相应 遗传算法被提出【叽加j 。 目前已提出的遗传算法虽然在一定程度上解决了服务选择问题，但它们都未 从遗传算法的组成上综合研究适于w e b 服务选择的遗传算法，而遗传算法的各 组成部分的综合设计会对遗传算法产生很大影响【1 4 l ，尤其编码方式、适应度、遗 传因子是遗传算法的重要组成部分，会直接影响遗传算法的收敛性、效果，只有 根据问题的特殊性进行算法设计，遗传算法才能得出更优解。编码方式是遗传算 法的基础，不同问题应采用不同的编码技术，基于q o s 服务选择的编码方式不 仅要反映w e b 服务组合情况，也要反映组合路径信息。目前解决w e b 服务选择 的遗传算法都采用一维编码方式，不能很好满足具有多路径特征的w e b 服务选 择的需要，无法同时表示概率型、顺序型、并发型等多种服务组合类型【1 5 j ，并且 无法通过简单的方法在编码上表示动态重计划及w e b 服务循环路径等情况。因 此，为克服上述存在的问题，为避免遗传算法陷入“早熟 ，需要设计一种新型 的编码方式。同时，合理设计遗传算法也可以有效解决遗传算法的“早熟”问题， 4 北京邮电大学硕士论文 第1 章 而个体或种群多样性控制是解决“早熟问题的一个方向【1 甜训。另外，遗传算法 具有收敛速度慢、运行结果不稳定的特点，这些都严重影响了算法在服务组合问 题上的应用，需采用一定的策略提高算法的收敛速度与稳定性。 基于以上的分析，作者提出了一个解决全局q o s 需求的服务选择策略，该 策略核心为改进的遗传算法，它完成通过改进的遗传算法选择最优组合的功能， 具有多路径表达能力以及多种组合类型表达能力。 1 3 主要研究工作介绍 本文的研究工作主要是在语义w e b 服务及服务选择相关技术研究的基础上， 研究服务选择算法，解决现存服务选择算法的效率低、寻优性差以及只能同时表 示单路径的问题，并基于此设计、实现服务选择模块。 本文作者硕士研究生期间，主要从事以下两个课题的研究： 1 基于p 2 p 的面向智能服务的中间件( p i s o m w a r e ) 系统服务选择模块的 研究开发工作，本课题内容属8 6 3 课题研究。 本课题研究期间的主要工作有： ( 1 ) 研究语义w e b 服务。研究了w e b 服务以及语义w e b ，深入研究服务选 择部分，包括服务选择在w e b 服务整体框架中的位置及作用、w e b 服务选择相关 技术。 ( 2 ) 研究遗传算法、模拟退火算法等多种解决n - p 难问题算法，并进行实 现。通过最终的测试，验证了算法在服务选择过程中的实际可用性。 ( 3 ) 在项目进展过程中参与完成的文档有：项目综述、( p i s o m w a r e 服 务选择需求分析文档、遗传算法总结、p l s o m w a r e 服务选择接口说明文档、 p i s o m w a r e 服务选择详细设计文档、p i s o m w a r e 服务选择测试文档、 p i s o m w a f c 服务选择技术方案。 2 i m s ( i p 多媒体子系统) 媒体资源控制实体( m r f c ) 以及归属用户服务 器( h s s ) 的研究开发工作，本课题研究内容属信息产业部电子信息产业发展基 金项目“3 g 核心网i p 多媒体子系统”。 本课题研究期间主要工作有t ( 1 ) 深入学习i m s 相关最新标准，尤其是m r f c 以及h s s 相关标准。从 标准中提取需求，完成m r f c 的设计、实现以及测试，完成h s s 的实现以及测 试。通过最终的测试，验证了系统的实际可用性。 ( 2 ) 在项目进展中完成的主要文档有： 3 g 核心网i p 多媒体子系统m r f c 软件需求规格说明书、媒体服务器调研文档、m r f c 模块概要设计文档、 m r f c 模块详细设计文档。 1 4 论文结构和主要内容 北京邮电大学硕士论文第1 章 本文研究的主要内容是服务选择，包括语义w e b 服务选择基础知识的学习以 及选择算法的学习、分析研究。论文共包括七章，除结束语之外，其他章节内容 如下： 第1 章绪论 本章主要介绍w e b 服务、语义w e b 的产生背景及各个组织机构对其研究 的进展状况，介绍本文作者研究生期间的研究工作，并给出本论文的组 织结构。 第2 章语义w e b 服务相关技术 本章主要介绍w e b 服务以及语义w e b 的主要思想，包括体系结构、特性、 功能以及优缺点，并对本体描述语言o w l - s 进行介绍。 第3 章w e b 服务的q o s 技术 本章阐述w e b 服务中的服务质量问题( q o s ) ，提出w e b 服务组合流中的 q o s 模型，并介绍本文建立的作为o w l - s 规范补充的q o s 本体模型。 第4 章改进的遗传算法 本章主要对传统的简单遗传算法进行介绍，包括遗传算法基本知识、优 缺点等，并详细阐述本文提出的改进遗传算法，论述此算法的优点。 第5 章设计与实现 本章综述p i s o m w a r e 系统整体结构设计，并将重点介绍服务选择模块 的作用、地位以及模块的设计、实现。 第6 章测试结果及分析 本章主要对算法以及服务选择模块进行测试，利用测试数据，分析服务 选择算法性能指标，包含算法运行效率、寻优性、收敛性以及稳定性分 析。 1 5 本章小结 本章介绍了语义w e b 服务以及服务选择的研究背景，给出了当前服务选择国 内外研究现状，叙述了作者研究生期间的主要研究内容以及完成的工作，清晰地 列出了本文的结构。 6 北京邮电大学硕士论文第2 章 第2 章语义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 服务作一个介绍。 2 1w e b 服务 2 1 1w e b 服务基本架构 如图2 - 1 所示，w e b 服务基本架构由3 个参与者和3 个基本操作构成。 图2 - 1w e b 服务基本架构 3 个参与者分别为： ( 1 ) 服务请求者( s e r v i c er e q u e s t e r ) 是一个应用程序，一个软件模块或需要服务的另一种服务，它发起对注册中 心中服务的查询，通过传输绑定服务，并执行服务功能，服务使用者根据接口契 约来执行服务。此角色可以由浏览器来担当，由人或由无用户界面的程序( 如另 外一个w e b 服务) 来控制它。 ( 2 ) 服务提供者( s e r v i c ep r o v i d e r ) 是一个可通过网络寻址的实体，负责使用w e b 服务描述语言来描述和定义那 些可以通过编程来访问的应用程序的功能，在服务注册中心中发布这些信息，使 其可以被其他应用访问、接收和处理。 ( 3 ) 服务注册中心( s e r v i c eb r o k e r ) 是服务发现的支持者，是可搜索的服务描述注册中心，包含一个可用服务的 存储库，并允许感兴趣的服务使用者查找服务提供者接口。服务提供者发布他们 的服务描述，服务请求者发现服务并获得服务的信息。 w e b 服务体系结构中每个实体都扮演着服务提供者、使用者和注册中心这三 种角色中的某一种( 或多种) 。 7 北京邮电大学硕十论文 第2 章 3 个基本操作包括： ( 1 ) 发布( p u b l i s h ) 服务提供者为了使自己的服务可访问，需要向服务注册中心发布服务描述以 使服务使用者发现和调用它。 ( 2 ) 发现( f i n d ) 在查找操作中，服务请求者定位服务，查询服务注册中心来找到满足其需求 的服务。 ( 3 ) 绑定和调用( b i n d ) 检索完服务描述之后，服务使用者根据服务描述信息中的绑定细节来定位、 联系和调用服务。 上述w e b 服务的工作原理为：服务提供者将其服务发布到服务注册中心的 一个目录上，当服务请求者需要调用该服务时，它首先利用服务注册中心提供的 目录去搜索该服务，得到如何调用该服务的信息，然后根据这些信息去调用服务 提供者发布的服务。当服务请求者从服务注册中心得到调用所需服务的信息之 后，通信是在服务请求者和提供者之间直接进行，无须再经过服务注册中心。 2 1 2w e b 服务协议栈 要以一种互操作的方式执行发布、发现和绑定这三个操作，必须有一个包含 每一层标准的w e b 服务协议栈。图2 2 展示了一个概念性w e b 服务协议栈1 2 0 - 2 1 1 。 上层建立在下层的功能之上，垂直的条表示在协议栈的每一层中必须满足的需 求，左边的文本则表示协议栈的那一层所应用的标准技术。 w s f l u d d i u d d i w s d l s o a p h r r p 、f 1 1 p 、e m a i l 、m q 、i i o p 等 服务流程 服务发现 服务发布 安 全 服务描述 基y - x m l 的消息传递 网络 图2 2w e b 服务协议栈 w e b 服务协议栈基础是网络层，w e b j 艮务要被服务请求者调用，就必须通过 网络访问。因特网上可供访问的w e b h 艮务必须使用普遍部署的网络协议，而h t r p 则凭借其普遍性，成为因特网上可用的w e b j 艮务真j 下的标准网络协议。通过图2 - 2 可看出，w e b 服务还支持同曙、s m t p 、m q ( 消息队列) 、i i o p ( 因特网o r b 间 协议) 上的远程方法调用( r e m o t em e t h o di n v o c a t i o n ，r m i ) 、e m a i l 等，应使用 哪种网络协议和应用程序的具体需求有关。 8 北京邮电大学硕士论文第2 章 1 、s o a p s o a p ( s i m p l eo b j e c t a c c e s sp r o t o c o l ，简单对象访问协议) ，是一个基于x m l 的，用于在分布式环境下对象之间进行通信所用的协议，它使相互分离的应用程 序实现互操作。 s o a p 的目的是为了使分布于网上的各个系统之间能够进行数据传输。当一 个应用程序与一个w e b 服务进行通信的时候，s o a p 消息是这两个系统之间交换 数据的最常用的方式。一个发送给w e b 服务的s o a p 消息会调用此服务所提供的 一个方法，也就是该消息请求w e b j 艮务执行一个特定任务。然后w e b j 艮务使用 s o a p 消息中所包含的信息执行其功能；如有必要，w e b j 艮务还会通过另一个 s o a p 消息返回结果。 作为一个基于x m l 的通信协议，s o a p 包含一组标准化的x m 蜞式。这些模 式定义了一种通过网络传送x m l 消息的格式，其中包括消息可包含的数据有哪 些类型，以及消息必须以何种方式组织，以使另一端的服务器能够正确解释它。 s q 廿被置于因特网协议( 如h t r p ) 之上，能被用来在w e b 和其他网络上传输数 据。使用h t r i 使w e b 服务可以穿越防火墙进行通信，因为大多数防火墙可以接 收h i t p 服务请求。 在s o a p 消息框架中，消息封装了传送给w e b 服务的信息和从w c b 服务送出的 信息。s o a p 消息没有提供编程指令，而是向w e b h 艮务服务器规定了应调用哪个 操作。由于s o a p 本身是可扩展的，因此可以支持附件、安全、路由信息和交易 等特性。当组织丌始要部署高度安全可靠的w e b , 服务时，s o a p 的可扩展性将会 变得更加重要。 2 、w s d l w s d l ( w e bs e r v i c ed e s c r i p t i o nl a n g u a g e ， w e b , q 曼务描述语言) ，是一个描 述w e n 艮务功能的协议，是由微软和i b m 联合开发的。 w 曲服务是一种部署在w e b 上的对象，需要对该对象的调用通信以某种结构 化的方式( 即x m l ) 进行描述，这也是w e b j 艮务及时装配的基本保证。w s d l 正 是这样一种描述语言，它定义了一套基于x m l 的语法，用来将w e b j 艮务描述为能 够进行消息交换的服务访问点的集合，从而满足了这种应用需求。 w s d l 文档将w e b j 艮务定义为服务访问点或端口的集合。w 曲服务的w s d l 文 档把服务访问点和消息的抽象定义与具体的服务部署和数据格式的绑定分离开 来，因此可以对抽象定义进行重用。w s d l 文档中的消息是指对数据的抽象描述， 而端口类型是指操作的抽象集合，端口类型使用的具体协议和数据格式规范构成 了一个绑定，将w e b 访问地址与可再次使用的绑定相关联来定义一个端口，而端 口的集合则定义为服务。在一个w s d l 文档中，定义w e b 服务一般使用下列元素： 9 北京邮电大学硕士论文第2 章 ( 1 ) t y p e s ( 类型) ：数据类型定义容器，提供了用于描述交换消息的数据类 型定义，它使用某种类型系统( 一般使用x m l s c h e m a 中的类型，o p x s d ) 。 ( 2 ) m e s s a g e ( 消息) ：消息数据结构的抽象类型化定义，消息包括多个逻 辑部分，每一部分与某种类型系统中的一个定义相关。消息使用t y p e s 所定义的 类型来定义整个消息的数据结构。 ( 3 ) o p e r a t i o n ( 操作) ：对服务中所支持的操作的抽象描述。一般来说，单 个o p e r a t i o n 描述了一个访问入口的请求响应消息对。 ( 4 ) p o r t t y p e ( 端1 2 1 类型) ：具有定义了服务访问入口的类型，即是传入传 出消息的模式及其格式。一个p o r t t y p e 口- 包含若干个操作，而一个操作则是访 问入口支持的一种类型的调用。在w s d l 中支持四种访问入口调用的模式：单请 求、单响应、请求响应及响应请求。p o r t t y p e 的定义中可能会引起一个或多个 消息，作为请求或响应消息的格式。 ( 5 ) b i n d i n g ( 绑定) ：特定端口类型的具体协议和数据格式规范的绑定，是 由端口类型定义的操作和消息制定具体的协议和数据格式规范的结合。定义了 p o r t t y p e 与某一种具体的网络传输协议或消息传输协议绑定，从这一层开始，描 述的内容就与具体服务的部署相关了，比如可以将p o r t t y p e 与s o a p h t r p 绑定， 也可以将p o r t t y p e 与m i m e s m t p 相绑定。 ( 6 ) p o r t ( 端口) ：协议数据格式绑定与具体w e b 访问地址组合的单个服务 访问点，它指出了用于绑定的地址，因此定义了单个通信终端。 ( 7 ) s e r v i c e ( 服务) ：相关服务访问点的集合，其描述的是一个具体被部署 的w e b 服务所提供的所有访问入口的细节，一个s e r v i c e 往往会包含多个服务访问 入口，每个服务访问入口都是用一个p o r t 元素来描述。 t y p e s 、m e s s a g e 、o p e r a t i o n 和p o r