（计算机科学与技术专业论文）基于工作流的web服务组合建模研究.pdf

r e s e a r c ho nm o d e l i n gw e bs e r v i c e sc o m p o s i t i o nb a s e do nw o r k f l o wm a s t e rd e g r e ec a n d i d a t e ：s u p e r v i s o r ：x i a nl i up r o f j i a n h u al is c h o o lo fi n f o r m a t i o ns c i e n c ea n de n g i n e e r i n gc e n t r a ls o u t hu n i v e r s i t yc h a n g s h ah u n a np r c h i n a原创性声明本人声明，所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了论文中特多l , j ) j n 以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得中南大学或其他单位的学位或证书而使用过的材料。与我共同工作的同志对本研究所作的贡献均己在论文中作了明确的说明。作者签名：日期：鲨! ：年月二日学位论文版权使用授权书本人了解中南大学有关保留、使用学位论文的规定，即：学校有权保留学位论文并根据国家或湖南省有关部门规定送交学位论文，允许学位论文被查阅和借阅；学校可以公布学位论文的全部或部分内容，可以采用复印、缩印或其它手段保存学位论文。同时授权中国科学技术信息研究所将本学位论文收录到中国学位论文全文数据库，并通过网络向社会公众提供信息服务。日期：递年上月三日摘要w e b 服务的出现代表了分布式计算的新要求，较好地解决了异构应用之间及松散耦合环境下的互操作和集成问题。随着w e b 服务的发展与应用，w e b 服务组合技术成为w e b 服务研究的关键问题。业务流程执行语言( b u s i n e s sp r o c e s se x e c u t i o nl a n g u a g e ，b p e l ) 作为执行过程定义的标准，由于商业逻辑的复杂性，使用b p e l 流程组合w e b 服务容易出错，因此，需要采用有效的方法来建模、分析、验证b p e l 流程，从而保证业务流程的正确高效运行。本文在同步p e t r i 网的基础上引入了一些有色p e t r i 的概念，针对b p e l的特点，在不改变同步p e t r i 网的基本性质的前提下对同步p e t r i 网作了一些扩展，提出了一种更适合b p e l 建模的s p n n e t 模型。该模型简洁紧凑，可理解性好。同时给出了b p e l 与s p n n e t 模型的转换规则，并给出了相互转换的算法。为了进一步简化模型，提出了一种基于结构相似性的化简算法。文中给出了基于s p n n e t 模型的服务组合合理性验证和性能分析方法。在合理性验证上，利用已有的化简规则并且扩展了2 个规则进行化简来验证b p e l 流程的结构合理性，同时在普通p e t r i 网可达图的基础上给出了此模型的可达图合理性分析方法。在性能评估上，结合马尔可夫链方法，详细给出了排队论和等价化简方法相结合的性能评估方法。最后，设计了基于s p n n e t 建模工具的总体框架，并结合开源系统 f i r e w o r k f l o w ，初步实现了基于s p n - n e t 的建模工具。文中给出了模型的动态描述，完成了几个结构性b p e l 流程文档向s p n n e t 的转换示例，并且给出了测试结果，最后结合实例对流程进行了单步动态模拟。本文主要是对基于工作流的w e b 服务组合建模进行了相关研究，提出了一个更适合b p e l 建模的模型s p n n e t ，基本上解决了建模技术中的主要问题，对于推进基于工作流w e b 服务组合技术的研究具有一定的价值。关键词p e t r i 网，w e b 服务组合，业务流程执行语言，模型验证，性能分析a b s t r a c tw e bs e r v i c er e p r e s e n t st h el a t e s tr e q u e s to fd i s t r i b u t e dc o m p u t a t i o n ，i th a ss o l v e dt h ep r o b l e mo fi n t e r o p e r a t i o na n di n t e g r a t i o ni ni s o m e r o u sa p p l i c a t i o n s w i t ht h ed e v e l o p m e n ta n dw i d e l ya p p l i c a t i o no fw e bs e r v i c e s ，w e bs e r v i c e sc o m p o s i t i o nt e c h n o l o g yh a sb e c o m et h ek e yp r o b l e mo fw e bs e r v i c e ss t u d y b u s i n e s sp r o c e s se x e c u t i o nl a n g u a g ea st h es t a n d a r do ft h ep r o c e s sd e f i n i t i o n ，d u et ot h ec o m p l e x i t yo fb u s i n e s sl o g i c ，u s i n gb e p lt od e s c r i b et h ec o m p l e xb u s i n e s sp r o c e s si se r r o r - p r o n e ，t h e r e f o r e ，t oe n s u r eb u s i n e s sp r o c e s s e sr u nc o r r e c t l ya n de f f i c i e n t l y , w es h o u l da d o p te f f e c t i v em e t h o d st om o d e l i n g ，a n a l y z e ，v e r i f yb p e lp r o c e s s i nt h i sp a p e r ，f o rb p e lf e a t u r e s ，b a s e do ns y n c h r o n i z e dp e t r in e tt h e o r ya n dw i t h o u tc h a n g i n gt h eb a s i cc h a r a c t e ro ft h es y n c h r o n i z e dp e t r in e t ，i ti n t r o d u c e ss o m ec o n c e p t so fc o l o r e dp e t r in e t ，e x t e n d st h es y n c h r o n i z e dp e t r in e ti ns o m et e r m sa n dp r o p o s e sam o d e ls p n n e t , w h i c hi sm o r es u i t a b l ef o rm o d e l i n gb p e l t h i sm o d e li ss i m p l e ，c o m p a c ta n dg o o di n t e l l i g i b i l i t y t h e nt h eb p e la n ds p n - n e tm o d e lt r a n s f o r m a t i o nr u l e sa n dm u t u a lt r a n s f o r m a t i o na l g o r i t h mw e r eg i v e n t of u r t h e rs i m p l i f yt h em o d e l ，i tp r o p o s e sa na l g o r i t h mb a s e do ns i m i l a rs t r u c t u r e t h ep a p e rg i v e sav e r i f i c a t i o no ft h es o u n d n e s sa n dp e r f o r m a n c ea n a l y s i so ft h i sw e bs e r v i c e sc o m p o s i t i o nm o d e lb a s e do ns p n n e t i nt h ev e r i f i c a t i o no ft h es o u n d n e s s ，i tu s e so ft h ee x i s t i n gr e d u c t i o nr u l e sa n de x t e n d st w or u l e st os i m p l i f ya n dv e r i f yt h es o u n d n e s so fb p e lp r o c e s s a l s o ，b a s e do nt h eg e n e r a lp e t r in e tr e a c h a b l eg r a p h ，i tg i v e sar e a c h a b l eg r a p ha n a l y s i sf o rt h i sm o d e l i nt h ep e r f o r m a n c ee v a l u a t i o n ，c o m b i n e dw i t ham a r k o vc h a i nm e t h o d ，ap e r f o r m a n c ee v a l u a t i o nm e t h o db yu s i n gq u e u i n gt h e o r yc o m b i n a t i o nw i t ht h em e t h o do fe q u i v a l e n ts i m p l i f i c a t i o ni sg i v e ni nd e t a i l f i n a l l y , as y s t e mf r a m e w o r ko fm o d e l i n gt o o lw h i c hi sb a s e do ns p n n e ti sd e s i g n e d i tc o m b i n e sw i t ha no p e ns o u r c es o f t w a r e【f i r e w o r k f l o w 】a n dg i v e sai n i t i a li m p l e m e n t a t i o no fm o d e l i n gt o o lo nu s i n gs p n n e t t h ed y n a m i cd e s c r i p t i o no ft h em o d e li sg i v e n a n dt h e ni tc o m p l e t e ss e v e r a le x a m p l e st h a ts t r u c t u r a lb p e lp r o c e s sd o c u m e n t sc o n v e r s i o nt ot h es p n n e t , a n dg i v e st h et e s tr e s u l t s a tl a s t ，as i n g l e s t e pd y n a m i cs i m u l a t i o nf o ra ne x a m p l ei sg i v e n t h i sp a p e rf o c u s e so nt h er e s e a r c ho fm o d e l i n gw e bs e r v l c e sc o m p o s i t i o nb a s e do nw o r k f l o w , p u t t i n gf o r w a r dam o d e ls p n - n e t ，w h i c hi sm o r es u i t a b l ef o rm o d e l i n gb e p l b a s i c a l l ys o l v e dt h em a i np r o b l e m si nm o d e l i n g ，i th a sac e r t a i nv a l u ef o rp r o m o t i n gt h ew e bs e r v i c ec o m p o s i t i o nb a s e do nw o r k f l o wt e c h n o l o g y k e y w o r d sp e t r in e t ，w e bs e r v i c e sc o m p o s i t i o n ，b p e l ，m o d e lv a l i d a t i n g ，p e r f o r m a n c ea n a l y s i si i i目录第一章绪论11 1引言11 1 1研究背景l1 1 2问题的提出21 2研究现状31 2 1u m l 活动图建模31 2 2基于状态机理论的w e b 服务组合建模及验证31 2 3基于进程代数的w e b 服务组合建模及验证一31 2 4基于p e t r i 网的w e b 服务组合建模及验证41 3四种方法比较51 4本文研究内容51 5论文组织6第二章p e t r i 网与b p e l 相关技术研究。82 1p e t r i 网82 1 1基本p e t r i 网理论82 1 2有色p e t r i 网l03 2 5b p e l 到模型的转换2 63 3模型的进一步简化2 73 4本章小结2 9第四章基于s p n - n e t 模型的服务组合合理性验证和性能分析3 04 1合理性验证3 04 1 1基于化简的方法。3 l4 1 2化简示例。3 54 1 3可达图的验证3 74 1 4可达图分析示例。3 94 2性能分析3 94 2 1马尔可夫链分析方法4 04 2 2排队论结合等价化简分析4 04 2 3 性能等价化简举例及仿真4 34 3本章小结。4 5第五章建模工具的初步实现与仿真4 65 1系统总体流程4 65 2系统的总体设计4 75 2 1总体设计图4 75 2 2s p n - n e t 模型类图4 95 3s p n - n e t 模型的动态描述5 05 3 1同步器( 库所) 动态执行描述5 05 3 2活动( 变迁) 动态执行描述5 15 4b p e l 结构到s p n n e t 模型转换及仿真实例5l5 4 1w h i l e 循环：。5 15 4 2综合示例5 35 5实例单步动态仿真5 55 6本章小结5 5第六章总结与展望：5 76 1工作总结5 76 2研究展望5 7参考文献5 9致谢6 4攻读学位期间主要的研究成果一6 5v硕十学位论文第一章绪论1 1 引言1 1 1 研究背景第一章绪论弟一早珀t 匕w e b 服务是一种跨网络的松散耦合的特定功能组件，利用统一的协议与规范，通过w e b 发布、查找和调用可以使使用不同语言编写的、运行在不同平台上的应用程序相互调用。w 曲服务采用面向服务( s e r v i c eo r i e n t e d a r c h i t e c t u r e ，s o a ) 的体系结构，如图1 1 所示。该体系结构中有服务提供者、服务请求者和服务注册中心三种角色，通过三个基本操作：发布、查找和调用来相互作用。服务提供者向服务注册中心发布服务，服务请求者通过服务注册中心查找要申请的服务，获取w s d l 并绑定到服务上。在w e b 服务体系结构中，w e b 服务各模块之间和模块内部消息都是以x m l 格式传递，它们使用w s d l 来描述服务，使用u d d i ( u n i v e r s a ld e s c r i p t i o nd i s c o v e r ya n di n t e g r a t i o n ) 来发布和查找服务，s o a p 消息则用来执行服务调用。图i 1 面向服务体系结构为了最大限度地发挥w e b 服务的功能，需要将各个功能分散的w 曲服务组合起来，使其具有更强的的功能从而实现企业协同工作，这就是w e b 服务组合。现有的w e b 服务组合研究采用的服务组合方法主要可以分为两种，即基于工作流的服务组合和基于智能规划( a ip l a n n i n g ) 的自动服务组合。目前，就服务组合的发展来看，基于智能规划的自动w e b 服务组合方法本身是一个十分复杂的过程，这一方法主要还是处于理论研究阶段。基于工作流的服务组合方法其主要思想是首先由业务人员建立适合具体应用需求的通用服务组合模型，在调用组合流程时，服务组合引擎自动把硕十学位论文第一章绪论抽象模型映射到具体的服务上，从而形成具有某种特定功能的服务链。由于工作流技术研究现阶段已经比较成熟，将w e b 服务和工作流相结合，可以发挥两者的长处，是一个很具有潜力的研究领域。因此基于工作流的服务组合方法也是目前比较通用可行的服务组合方法。现有的许多服务组合流程描述语言如b p e l i 、w s f l t 2 1 、x l a n g f 3 1 等也都是基于业务流程的方法来实现服务组合的，业务流程执行语言b p e l ( b u s i n e s sp r o c e s se x e c u t i o nl a n g u a g e ) 现在已经成为组合w e b 服务和管理业务流程执行的标准。因此本文采用b p e l 作为组合流程的描述语言，基于工作流技术进行服务组合研究。由于业务流程的复杂性，使用b p e l 流程组合w e b 服务容易出错，因此，需要采用形式化的方法来建模、验证b p e l 流程，从而保证业务流程的正确运行以及实时监控。同时，普通建模者也更愿意使用图形化建模，因此，研究如何将图形化的形式化语言来建模b p e l 流程是十分有意义的。1 1 2 问题的提出通过服务组合可实现更加复杂功能，但如何使用户容易上手使用，如何保证组合的流程不会在运行中出现问题，如何保证组合的流程可实现预期的需求。这些要解决的问题转换为更具体的表达，主要概括为以下三点：( 1 ) 组合流程开发平台比较缺乏。w - e b 服务组合很多还是以编辑文件的方式来进行开发，这使得组合流程开发的工作难度大而且容易出错。( 2 ) 臣t j 使有图形化的建模，但是这些模型要么缺乏形式化语义，要么就是模型过于复杂庞大，用户难于理解。( 3 ) 流程验证与预分析问题。无论是通过服务组合平台开发或是手动编写程序的方式，都有可能发生组合流程设计上的问题，例如：死锁等，这些问题只有在组合流程实际执行时才会出现。另外对流程的执行不能做相应的预测，比如吞吐量和执行速率等方蕊。缺乏在流程正式运行前进行实例模拟仿真。所以需要研究的问题可以归纳为以下两点：( 1 ) 运用图形化工具对w e b 服务组合建模，然后进行组合流程验证分析，发现其结构错误，通过反馈给用户修改确定没有错误然后再转换成合格的b p e l 流程描述文件，同时还能进行b p e l 流程的实例跟踪，从而保证业务流程的正确运行。同时能对流程的吞吐量和执行速率等性能指标作相应的预测，以保证执行效率。( 2 ) 尽量使得模型简洁紧凑，容易理解，而且模型能具有较好的形式化表示和直观的图形化界面。2硕士学位论文第一章绪论1 2 研究现状基于工作流的w e b 服务组合这个问题，已经有大量的研究者进行了广泛和深入的研究。他们对w e b 服务组合建模语言、服务组合执行、服务组合验证等方面进行了研究，启动了很多相关研究项目和产品开发。在国内外相关研究项目及平台方面，服务组合基于工作流方法进行服务组合平台和产品的开发，例如u cb e r k e l e y 的n i n j a t l 0 1 ，澳大利亚n e ws o u t hw a l e s 大学的s e l f s e r v ! 1 2 】，h p 实验室的e f l o w 系统【1 4 】和美国斯坦福大学的s w o r d i ”】开发工具集等，以及已经产品化的微软b i z t a l ks e r v e r 【埔j 企业应用集成服务平台。目前，国内外研究针对的业务流程组合建模及验证问题主要集中在以下几个方面：基于u m l 活动图建模；然而一般都以形式化语言为基础，使用最多的是采用p e 仃i网、自动机理论和进程代数这三种形式化方法来验证。1 2 1u m l 活动图建模文献【2 0 】【2 1 】中提出了一种方法，用u m l 活动图作为w e b 服务组合工具。该方法利用扩展的标准u m l 来描述w e b 服务组合，为w e b 服务组合提供了图形化的描述方式，独立于具体w e b 服务组合描述语言，如b p e l ，以及流程的引擎，文中还介绍了运用u m l 模型转换组件，将u m l 活动图转换成b p e l 的相关规范。但是以u m l活动图为模型来描述服务组合，缺乏w e b 服务组合j 下确性验证的形式化基础。1 2 2 基于状态机理论的w e b 服务组合建模及验证基于自动机的w e b 服务组合的建模与验证有不少研究成果。文献【7 】f 1 8 】给出一套技术和工具( 卫式自动机、p r o m e l a 语言、s p i n 模型验证工具) 以及一个完整的系统分析和验证方法，通过把b p e l 转换成卫式自动机，进而转换成p r o m e l a 语言，作为模型验证工具s p i n 的输入，从而验证服务组合流程的正确性。文献【1 9 】为了简化组合服务验证，提出一种基于扩展有限自动机验证w e b 组合服务的方法，该方法不但可以检测组合服务运行过程是否有逻辑错误，还可以验证组合w e b 服务是否满足用户需求。文献 2 2 1 提出了一种基于扩展的有限自动机的模型b v m 模型来表达应用程序的语义，然后运用模型检测方法进行形式化验证，以上方法在设计阶段能有效地发现并排除错误。1 2 3 基于进程代数的w e b 服务组合建模及验证进程代数作为进程间互相作用的基本手段，所以很适合用来描述和验证分布式的硕十学位论文第一章绪论松耦合系统。其中就有使用p i 演算和b p e 演算来描述和验证w e b 服务组合的。p i 演算不仅可以传递变量和值，还具有建立新通道的能力，而且p i 演算在设计阶段有助于描述系统的交互行为，建立后，则可利用p i 演算来推演其行为，同时验证模型的正确性。文献f 6 1 和文献 8 】各自利用p i 演算发展了一个针对服务组合的形式化方法，文献 6 】中基于p i 演算对w e b 服务及其组合进行形式化描述和建模，分析了p i 演算应用于w e b 服务组合需要解决的问题，讨论了p i 演算与w e b 服务协议栈的对应关系，说明了利用p i 演算建立w e b 服务组合模型的规则，指出了如何寻找代理和通道，最后建立了一个实际的模型，并利用形式化工具对建立的组合模型是否正确以及是否满足需求进行了验证。文献1 2 3 1 d p 引入了基于b e p l 的b p e 演算。使用p a c 工具( p r o c e s sa l g e b r ac o m p i l e r ) 和c w b - n c 工具( c o n c u r r e n c yw o r k b e n c ho f t h en e wc e n t u r y ) 来建模和验证组合流程。b p e 演算包含了b p e l 的结构化流程，b p e 演算作为p a c 的输入，其输出作为c w b 的输入，从而验证w e b 服务组合，但是该方法不独立于w e b 服务组合描述语言，具有一定的局限性。1 2 4 基于p e t r i 网的w e b 服务组合建模及验证p e t r i 网具有直观的图形表示方式和丰富的形式化语义，能够自然地描述并发、同步和资源竞争等系统特性，适合描述w e b 服务的动态行为，比较适合建模w e b 服务组合并验证w r e b 服务的运行状态。文献 2 2 1 给出了一个面向服务的分布式系统的设计与分析框架。该框架的基础是一个基于颜色p e t r i 网的服务规范模型w s p n e t ( n ，o ，s ) ，该服务规范模型适应于描述服务组合和对话协议，同时也支持协议的合并。它还可以对组合进行形式化分析：利用颜色p e t r i 网的完全发生图来验证组合实例的正确性；为新建的组合服务自动导出对话协议。该框架包括一个支持组合模型建模和分析的工具集，且支持包括有复杂对话协议的伙伴服务的服务组合。文献 2 8 1 提出使用扩充的p e t r i 网w f 网来验证流程是否有死任务和流程的正确完成性。文献【5 1 利用c s p 对w e b 服务组合进行建模，并给出了b p e l 结构转换为c s p 元素的相关规则，同时介绍了相关的模型分析、验证方法。文献【9 【2 7 】主要是利用有色p e t r i 网来设计和验证w 曲服务组合，介绍了w 曲服务组合的p e t r i 网建模过程，用两个库所和一个变迁表示一个w e b 服务，第一个库所用来接受w e b 服务的输入，变迁代表绑定的w e b 服务操作，第二个库所用来输出服务产生的结果。一个流程可以转换到一个对等的c p n 模型，然后用c p n 工具分析，检验组合的正确性。4硕士学位论文第一章绪论文献【l7 】采用有色p e t r i 网对w e b 服务组合进行建模，给出了组合流程的代数形式及动态描述，最后用c p nt o o l s 创建了一个服务组合实例。但该文没有给出着色p e t r i网与服务组合描述语言之间的转换规则。文献【1 1 】把b p e l 转换到层次有色网，再利用c p n 工具验证。文献【1 3 】提供了比较完整地从b p e l 控制流到p e t r i 网的映射。文献【2 4 】提出了一种p n 2 b p e l 的模型转化方法，将一个活且有界的p e t r i 网中的每一个组件都用一个简单任务来替换的替换操作。文献 2 5 】和文献 4 】采用同步p e t r i 网，提出了分层建模和验证的思想，将b p e l流程分为逻辑层和语义层，并分别建立形式化模型和验证方法，这样不仅能保证对流程正确地建模，而且能降低建模和验证的复杂度。1 3 四种方法比较上面介绍了u m l 活动图建模，自动机理论、进程代数和p e t r i 网三种形式化方法来对w e b 服务组合进行建模以及验证的研究现状。一个好的模型不仅要为用户容易理解，更重要的是要能被计算机理解，所以下面主要从形式化验证能力和图形化表示来进行比较这四种方法。u m l 活动图普通用户所掌握和理解，但是缺乏形式描述。进程代数表达能力强，为w e b 服务组合验证提供了良好的理论基础，但是进程代数比较抽象，图形表达能力比较弱。自动机理论对w e b 服务组合进行建模图形表达能力强，但在服务流程规模变大的情况下，使得建模很不直观。采用p e t r i 网对w e b 服务组合进行建模比较直观，而且p e t r i 网有很好的形式化描述能力和分析手段，虽然p e t r i 网在组合流程规模变大的情况下也会引起状态空间爆炸，但是目前p e t r i 网研究方面出现了许多高级p e t r i 网，比如同步p e t r i 网，分层p e t r i 网，有色p e t r i 网，这些高级p e t r i 网在一定的程度上解决了流程规模变大而引起状态空间爆炸的问题。所以本文将在同步p e t r i 网，有色p e t r i 网等高级p e t r i 网的基础上建立更加适合w e b 服务组合的工作流模型。1 4 本文研究内容本文需要深入的研究同步p e t r i 网和着色p e t r i 网，以及对b p e l 做详细的分析研究，然后提出了一种模型，并以b p e l 作为模型的描述语言，且给出b p e l 与模型的映射规则和转换算法，对基于此模型的组合流程进行结构合理性验证和性能评估，在此基础上设计系统的总体框架并结合一个丌源的系统，对模型进行初步实现与b p e l流程仿真。本文将要研究的工作如下：( 1 ) 对同步p e t r i 网和着色p e t r i 网，b p e l 进行较详细的分析和研究。5硕七学位论文第一章绪论( 2 ) 提出一种模型。介绍基于p e t r i 网，同步p e t r i 网和着色p e t r i 网对b p e l 建模的不足之处，在同步p e t r i 网和着色p e t r i 网的基础上提出一种更适合b e p l 建模的工作流模型。( 3 ) b p e l 与模型的转换。将具体介绍b p e l 中各种类型的活动( 包括基本活动和结构活动) 与所提出的模型映射规则，主要是结构的识别与b p e l 文件的生成以及b p e l 文件到s p n - n e t 模型的转换。针对大部分基于p e t r i 网模型对b p e l 建模都会具有模型复杂的缺点，提出一种基于结构相似性算法进一步简化模型流程的规模。( 4 ) 对组合流程进行合理性分析：利用相关文献中提出的规则，并且扩展2 个规则进行化简来验证b p e l 流程的结构合理性；同时在普通p e t r i 网可达图的基础上给出此模型的可达图分析方法。对组合流程进行性能评估：介绍用马尔可夫链方法进行性能评估；详细给出排队论和等价化简的方法相结合的性能评估方法，并且通过仿真工具e x s p e c t 验证方法可行性。( 5 ) 建模工具的实现与b p e l 流程仿真。设计基于s p n - n e t 建模工具的总体框架，并将在一个开源软件的基础上，根据文中的模型对开源软件进行相应的扩展，利用它进行建模，实现b p e l 到模型的转换，然后对模型进行模拟仿真，观察模型中的动态变化。1 5 论文组织本文共分为六章，其中：第一章绪论。介绍了论文的研究背景，概括主要工作和相关研究领域的研究现状。第二章p e t r i 网与b p e l 相关技术研究。简单介绍了p e t r i 网，同步p e t r i 网，有色p e t r i 网，对b p e l 作了相应的介绍与研究。第三章服务组合模型s p n n e t 模型以及与b p e l 的映射。提出一种更适合b e p l 建模的s p n - n e t 工作流模型，通过比较，得出此模型具有更简洁紧凑，逻辑清晰等优点。给出了b p e l 与模型的转换规则以及相互转换算法。接着提出一种算法进一步简化了模型流程的规模。第四章基于s p n - n e t 模型的服务组合流程合理性分析验证和性能分析。首先用化筒的方法进行化简来验证b p e l 流程的畅通性，接着给出一种改进p e t r i 的可达图算法来验证其合理性。简单介绍了用马尔可夫链方法进行性能评估，接着详细给出了排队论和等价化简方法相结合的性能评估方法。第五章建模工具的初步实现与仿真。主要是在分析一个开源系统的基础，根据本文描述的模型对此丌源系统进行了相应的扩展，然后利用它进行建模，初步实现了6硕十学位论文第章绪论文章中所提的模型，然后对模型进行模拟仿真，观察模型中动态变化( 主要是模型中t o k e n 分布与流转) 。第六章总结与展望。总结本文的研究成果，指出仍存在的问题及进一步研究的方向。7硕士学位论文第二章p e t r i 网与b p e l 相关技术研究2 1p e t r i 网第二章p e t ri 网与b p e l 相关技术研究p e t r i 网【2 9 1 是1 9 6 2 年由德国学者c a r l a d a m p e l x i 在他的博士论文中首次提出，在此基础上，而后很多学者对其进行了研究与扩展，目前p e t r i 网已经有多种形式，如有色p e t r i 网、时间p e t r i 网、随机p e t r i 网，在很多领域得到了广泛的应用。p e t r i 网是一种可用网状图形表示的系统模型，既有形式化的描述又有图形化的表示，借助p e t a l 网分析方法和技术既可用于流程结构分析，又可用于流程动态的行为分析，是硕十学位论文第二章p e t r i 网与b p e l 相关技术研究变迁t t 成为使能的当且仅当：v p t ：m ( p ) l ，记做m t ，其中，m ( p )表示在状态m 下库所p 中t o k e n 的个数；在m 下变迁t 可以使能，使能后得到后继状态m ，则当p e t t 时，m ( p ) = m ( p ) + l ；当p c t - t 时，m ( p ) ：m ( p ) 1 ，其他情况状态不改变。规则表明变迁t 称可使能的当且仅当t 的每个输入库所都包含至少一个t o k e n ；表明如果变迁t 使能，那么t 从每个输入库所p 中消耗一个t o k e n ，并为每个输出库所p 产生一个t o k e n 。p e t r i 网由库所，变迁和弧线组成，一般用圆圈表示库所，用矩形表示变迁，用黑点表示t o k e n ，p e t r i 网的状态用库所中t o k e n 的分布来描述。如图2 1 所示。图2 - 1p e t r i 网示例在p e t r i 网的基础上，a a l s t 提出tt 作流网( w o r k f l o w n e t ，w f n e t ) 的概念。定义2 - 3 ( w f n e t ) t 3 0 1 1 3 1 l ：一个p e t r i 网p n = p ，t ，f ，m o 是w f - n e t 当且仅当它满足如下两个条件：( 1 ) 存在两个特殊位置i 和o ，位置i 表示起点，位置o 表示终点；( 2 ) 如果在t 中增加条件变迁t 幸，并在f 中增加元素( o ，t 木) 和( t 誊，i ) 得到p n * ，则p n * 是强连通的。p e t r i 网的分析方法主要是针对其结构进行分析，常用的分析方法有以下几种【2 9 】f 5 3 】：( 1 ) 化简：在保证网系统基本性质不变的情况下进行化简，以简化流程的复杂性。( 2 ) 可达图方法：是一种非常有效而且常用的分析方法，将p e t r i 网运行的所有可达状态以图的形式表示出来，从可达图上很容易得出流程的有界性、活性等性质。但是它也有缺点，对与复杂的业务流程，会造成存储空间和时间开销太高。( 3 ) 矩阵方程求解：通过对矩阵的秩、p 不变量、不变量等计算，可以发现其周期性等性能，从而分析p e t r i 网的互斥、死锁等情况。( 4 ) 结构分析方法：通常用网的关联矩阵及其相关的齐次方程表示进行分析。p e t r i 网的相关概念、定理和性质文献 2 9 】【3 0 】【3 l 】还有很多，本文不再一一列举。9硕士学1 i ；7 ：论文第二章p e t r i 网与b p e l 相关技术研究2 1 2 有色p e t r i 网普通p e t r i 网中的t o k e n 没有实际的含义，对变迁的使能条件的定义比较简单，不利于对复杂系统的模拟。于是，就有提出了有色p e t r ii 网( c o l o r e dp e t r in e t s ，c p n ) 3 2 1 。c p n 是较为成熟的高级p e t r i 网。c p n 在基本p e t r i 网的基础上对t o k e n 进行了颜色扩展，将库所中的t o k e n 着色。着色既能实例的特点，又能丰富模型的含义，这也是目前c p n 成为应用主流模型的原因之一。t o k e n 由于其值不同而具有不同的颜色，这样一个库所中就可以包含几个不同颜色的t o e k n 。要使变迁能够使能，必须前置库所中的存在那一类颜色t o k e n ，若满足变迁使能条件，则变迁被激发，产生新的t o k e n 送到变迁的后置库所中。在c p n 的形式化定义中，本文用b 表示布尔型，用v a t s 表示变量集，用t y p e ( v a r s ) 表示类型集 t y p e ( v ) lv e v a r s 。定义2 - 4 设c p n 表示有色p e t r i 网( c o l o r e dp e t r in e t s ，c p n ) ，c p n = ( e ，p ，t ，a ，n ，c ，g ，e ，i ) ，其中【3 2 】【3 3 l ：o ) e 是一个非空的类型有限集，称为颜色集( c o l o rs e t ) 。( 2 ) p 是一个库所的有限集。( 3 ) t 是一个变迁的有限集。( 4 ) a 是一个弧的有限集，满足p n t = p n a = a n t - 巾。( 5 ) n 是一个节点( n o d e ) 函数，定义为从a 到p tut x p 。( 6 ) c 是一个颜色函数，定义为从p 到。( 7 ) g 是一个哨( g u a r d ) 函数，定义为从t 到表达式的映射，满足vt t ：【t y p e ( g ( t ) ) = bat y p e ( v a r ( g ( t ) ) ) o( 8 ) e 是一个弧表达式函数，定义为从a 到表达式的映射，满足v a a ：【t y p e ( e ( a ) ) = c ( p ) m s x t y p e ( v a r ( e ( a ) ) ) 】，其中p 是n ( a ) 的库所，c ( p ) m s 是库所p的颜色集上的多重集。( 9 ) l 是一个初始化函数，其实就是t o k e n 中赋予的颜色初始值，满足v p e p ：【t y p e ( i ( p ) ) 2 c ( p ) m s 】。定义2 5 设m 表示一个多重集1 3 2 1 【3 3 】，m 是非空集合s 上的函数m 【s n 】。非负整数m ( s ) e n 是元素s 在多重集m 中出现的次数。通常将多重集表示为：y 嚣m ( s ) s 。其实就是一个可以存在重复数据的集合。我们用s m s 来表示集合s 上的所有有限多重集所组成的集合。为定义绑定，首先引入一个概念【3 2 1 【3 3 1 ：v t et ：v a r ( t ) = vlv v a r ( g ( t ) ) v 了a a ( t ) ：v ev 砥e ( a ) ) ) ；定义2 - 6 ( 变迁绑定) 1 3 2 1 1 3 3 1v a r ( t ) 是变迁t 的变量集，表示该变迁t 的哨函数以及与变迁相关联的弧表达式中的变量集合，v a r ( t ) 的一个绑定b ：对每个变量v i 赋l o硕十学位论文第二章p e t r i 网与b p e l 相关技术研究值，记作b ( v i ) ，则b = b ( v o ，b ( v n ) ) 。g ( t ) 表示绑定b 中的哨函数g ( t ) 的求值。定义2 7 ( 步骤) 就是使c p n 系统从一个状态到达另一个状态的变迁的多重集合。为了进行形式化验证，下面将定义可达图。可达图是一个有向图，是一个从初始状态出发可到达的所有状态组成，每个节点表示一个可达状态，每条有向弧用可到达下一状态的行为变迁绑定，下面给出可达图的形式化定义。定义2 - 8 ( 可达图) 1 5 3 】【蚓c p n 的可达图，是一个有向图o g = ( v ，a ，n ) ，其中：( 1 ) v = 【m 0 ，v 是从状态m 0 出发可到达的所有状态的集合。( 2 ) a = ( m 1 ，b ，m 2 ) v b e x vim i 【b m 2 ) 。( 3 ) v a = ( m i ，b ，m 2 ) a ：n ( a ) = ( m l ，m 2 ) 。可达图对每个可达状态都有一个相应的节点，对发生的每一步都有一个相应的弧，弧上带有相应的变迁绑定元素，为了方便直观直接用相应的变迁表示，不带输出弧的节点称为叶子节点。2 1 3 同步p e t r i 网定义2 - 9 ( 同步器( s y n c h r o n i z e r ) ) 1 4 1 3 4 1 ：如图2 - 2 所示，同步器p = ( t 1 ，t 2 ，( a l ，a 2 ) ) 中，t i = p ，t 2 = p ，k ( p ) = a l x a 2 ，i 鱼i i t l i - - m l ，l 亚si t 2 1 - - m 2 ，a l 是t 1 中发生的变迁的个数，a 2 是t 2 中发生的变迁的个数，w ( t i ，p ) = a 2 ，w ( p ，t 2 ) = a l ，其中t le t l ，t 2t 2 。其中，同步器p 只有在m ( p ) = k ( p ) 时才能同步授权给t 2 中变迁，m ( p ) 表示状态m 下，p 中的t o k e n 数。图2 - 2 同步器定义2 1 0 ( 同步网( s y i u e t ) 【4 l 【3 4 ) ：加权有向图w n = ( p ，t ；f ，k ，w ) 称为同步网，简称s y n _ n e t ，如果( p ，t ；f ) 为有限有向网，而且同时满足以下条件：( 1 ) v t t ：t 痧 t 矽( 2 ) v p p ：( p 矽人p 矽) ：p = ( t i ，t 2 ，( a l ，a 2 ) )( 3 ) i p i p = 矽) i - 1( 4 ) f + n ( f - i ) + = 即没有循环( 5 ) v p ：( p = c vp = 矽) = ，k ( p ) = lav t p ：w ( t ，p ) = 1 v t p ：w ( p ，t ) = 1硕士学位论文第二章p e t r i 网与b p e l 相关技术研究( 6 ) v t