（计算机软件与理论专业论文）基于qos的服务合成建模与分析.pdf

学位论文基于q o s 的服务合成建模剃分析 基于q o s 的服务合成建模与分析 计算机软件与理论 硕士生：宋华梅 指导教师：李文军副教授 摘要 基于过程的服务合成实现企业内部与企业之间的业务流程的整合f 成为目 i i 的 研究热点。独立的服务被称作组件服务，合成服务被表示为业务流程。通常，在 l n t e r n i 玎上，存在大量提供相同功能满足不同q o s 的等价服务，对这些等价 服务的选择在服务合成的过程之中是必然的。为了实现服务合成的高效、有效， 已经存在一些工作流模型的研究来建模和分析服务合成的业务流程，但是这些研 究都没有在模型中显式地表示组件服务的q o s 和基于0 0 s 的对组件服务的选择。 因此，本文提出了一个基于q o s 的工作流模型s c _ c p n 。它是一个基于着色 网的模型，用颜色集表示组件服务的q o s 和选择策略，用卫式函数( g u a r d f u n c t i o n ) 表示对组件服务的选择。c p n t o o l s 是被广泛使用的着色网编辑和模拟 工具之一。在本文中，它被用来建模合成服务，模拟组件服务的选择、绑定和执 行，同时利用这个工具提供的形式化方法分析整个业务流程的并发性质。最后， 基于s cc p n 模型，我们提出了一个计算业务流程q o s 的算法。 本文的主要贡献在于提出了基于0 0 s 的服务合成模型，在模型中显式地表示组 件服务的q o s ，选择策略以及基于( b s 的对组件服务的选择。在模型的基础上， 提出了基于用户选择策略和组件服务q o s 的服务选择算法。当存在多个满足用 户需要的组件服务时，采用了基于效用函数的加权平均算法选出具有最高值的组 件服务。 关键词：服务合成；o o s ；着色网：建模：分析 学位论文 基于o o s 的瑕务合成建模和分析 m o d e h n ga n da n a l y s i so fq o s b a s e ds e r v i c ec o m p o s i t i o n c b i 砷u t e rs 0 脚a r ea i l d1 1 啪r y n a m e ：s o l l gh 嘲e i s u p 鲫i s o r ：i jw 锄u n 蝴t ep f 0 危s s o r a b s t r a c t t h cp m c e s s _ b a s e dc o m p o s i t i o no fs e r v i c e si se m e f g i n ga sap r o m i s i n ga p p m a c ht o i i l t e g f a t eb u s m e s sa p p l i c a t i o n sw i t h 证a n da c m s so 堆a n i z a t i o n a lb o u n d a r i e s i nt h i s a p p r o a c h ，i 1 1 d j v i d u a js e r y j c e sa r en a m e dc o m p o n e n ts e n ，j c c sa 删c d m p o s i t es e r v i c e s a sb u s i i i e s sp r o c e s s u s u a l l y t h c f ea r eal a r g en u m b e ro fe q u i v a l e n ts e r v i c e st h to 骶f s i m i l a ff i l n c t i o n a l i t ya n dh a v ed j 脏r e n tq o s t h es e l e c t i o no fc o m p o n e n ts e r v j c e s s h o u l db ec a i e do u td u r i n 叠l h es e r v i c ec o m p o s 王t i 0 i no r d e rt oa s s u r ee f 丘c i c ta n de 丘e d i v ec o m p o s i t i o no fe x i s t i i l gs e r v i c e s ，t h e f ea f e s o m es t u d i e sa b o u tw o r k f 重o wm o d e lt h ee x i s t i n ga p p a c h e sh a v en o te x p l i c i l l v i n o d e lq o sa n dt h es e l e c t i o no fc o m p o n e ms e i c e s ，s ow ep i o p o s eaq o s - b a s e d w o r 煳o wm o d e ln a m e ds cc p n ，w h i c hi sac p n ( c o l o r e dp c t r in e t s ) b a s e dm o d e l t h i sm o d e lu s e sc o l o ts c t s t om o d e lt b eq o so fc o m p o n e ms e i c e sa n ds e l e c t j o n p o l i c i e s ，a n du s eg u a r df h n c l i o i l st oi n o d e l t h es e l e c t j o no fc o m p o n e ms e r v i c e s c p n 1 _ o o l si saw i d e l yu s e dt o o lf o re d n i l l ga i l ds i m u l a l i i l gc p n i nt h i sp a p e r ni su s e dt o 1 1 1 0 d e lt h ec o m p o s i t es e r v i c ea n ds i i n u l a t et h es e r v i c cs e l e c t i o n b i i l d i n ga n de x e c 叭i o n ， 粕a l y z et h cc o n c i l f r e c yq u a l i t yo ft h eb u s i i l e s sp f o c e 晒b yf o 瑚a la m l y s i sm e t h o d s t h a tt h et o o lp m v i d e s i nt h ce n d ，w ed e v e l o pa na l g o r i t h mt oc o m p u t et h eo o so ft h e b u s i l l e s s 口r o c e s sb a s e dt h cs cc p nn l o d c l n ec o n t r i b u t i o na n di n i l o v a t i o np 0 洫i l lt h i sp a p e rj st h a tw ep r o p 0 a ( ) 0 s b a s e d w o r k n o wi n o d e ll l a m e ds cc p n ，w h i c hi sac p n - b a s c d 帕d e l i tc a ne x p l i c i t l v m o d e lo o so f m p o n e ms e r v j c c s ，s e k c t i o np o l i c i e sa n dt h es e l e c t i o no fc o m p o n e m s e r v i c e s b a dt h c 脚d e lw ed e v e l o pas e l e c t i o na l g o r “h n lw h i c hu t h eu s e r s s e l e c t i o np o l i c i e sa n dt h eq o so fc o m p o n e n ts c r v i c c s w h e nt h c 阳si n o r et h a no n e s e r v i c es e i e d e d ，w cu s eu t i l i t y - b a s e dw e 远h t e da v e r 4 9 e 如n c t 幻nt os e l e c tt h c c o m p o n e ms e n ，i c cw i i ht h cn m x i m lv a l u e k e y w o r d s ：s e n ，i c ec o m p o s 弛n ；q o s ；c p n ；咖d e l i n g ；a n a l y s i s i 【 基于0 0 s 的服务合成建模与分析 己l 言 jl 口 随着经济的全球化，今天的商业组织面临的是全球化的市场竞争。为了在这样动态 的经济环境下具有更高的竞争力，商业组织之间需要去整合彼此之间的业务流程。 随着i n t e r n e t 技术的发展，电子商务的广泛接受以及面向服务架构的逐渐成熟， 服务和服务合成被逐渐应用到业务流程之中。业务流程表示为一个工作流，单个任 务用服务实现。 为了更好地实现服务的合成，下面的问题需要考虑： 如何精确地建模基于o o s 的服务合成? 如何分析合成服务的业务流程是否逻辑正确? 如何估计合成服务的0 0 s ? p e t r i 网【1 。4 1 概念诞生于2 0 世纪6 0 年代，在2 0 世纪8 0 年代取得了突破性进展，是描 述和分析并行与分布式系统的有力工具。对于用p e t r i 网建立工作流模型，分析业务 流程，w m p v a nd e r a a l s t 提出了三个理由【5 】：首先，直观的图形表示和形式化的 语义定义；其次，基于状态的而不是基于事件的过程建模；第三，丰富的分析技术。 着色网( c o l o r e dp e t r in e t s ) 1 6 】是一种高级p e t r i 网模型，它和普通p e t f i 网的关系如 同程序设计语言中的高级语言和汇编语言的关系一样。它通过对位置，托肯和变迁 加以颜色类型的标定，对变迁和弧加以条件的约束，使建模者可以更容易摒弃系统 的琐碎细节，抓住系统的本质行为特征，大大增强了对服务系统的建模能力。 基于上面的考虑，本文建立了基于q o s 的服务合成模型，将q o s 信息、选择策略 和基于o o s 的对组件服务的选择显式地表示到模型之中。这个模型是用着色网作为 基于0 0 s 的服务合成建模与分析 基础。在模型的基础上，本文给出相应的服务选择算法和业务流程q o s 计算方法。 本文的结构如下：第一部分是服务合成的介绍；第二部分是着色网的介绍；第三部 分是建立s c 一c p n 模型，并给相关的验证和分析技术；第四部分介绍工具实现， 用于计算整个业务流程的q o s ；第五部分是模型的应用，讨论三个典型的应用实例。 最后总结本文的工作及进一步的工作展望。 基于0 0 s 的服务合成建模与分析 第1 章服务合成 1 1背景 1 1 1 工作流 工作流【7 1 是从英文单词w b r l c f l o w 翻译得来的。w b r k f l o w 是由单词w b r k 和f l o w 组合得 到的词。单词w b r k 表示工作或者任务，单词f l o w 的含义是流动、流程或者流量等。 工作流的概念起源予生产组织和办公自动化领域。它是针对日常工作中具有固定程 序的活动而提出的一个概念。1 9 9 3 年工作流管理联盟( o r 如o wm a n a g e m e m c o a l n i o n ，w f m c ) 的成立标志着工作流技术开始进入相对成熟的阶段。 国际工作流管理联盟给出的工作流定义8 】：工作流是一类能够完全或者部分自动执 行的经营过程，它根据一系列过程规则、文档、信息或任务能够在不同的执行者之 间进行传递与执行。简单地看，工作流由活动和活动之问的连接关系组成。活动反 映了经营过程中的执行动作或操作，对应于经营过程中的任务；而活动之间的连接 关系则代表了经营过程的规则和业务流程。可以说，工作流技术是经营过程的计算 机实现。 工作流管理系统( w b r l 【f 】o wm a g e m e ms y s t e m ) 嘲是一个软件系统，它完成工作流 的定义和管理，并按照在计算机中预先定义好的工作流逻辑推进工作流实例的执行 和控制。它为企业的业务系统运行提供一个软件支撑环境，非常类似于在单个计算 机上的操作系统。工作流管理的最终目的是实现业务流程高效、有效地执行。过程 建立是工作流管理的主要方面，因此需要一个框架建模和分析工作流的过程。w m p 基于0 0 s 的服务合成建模与分析 v a n d e r a a l s t 在【9 】中提出了以p e t r i 网为基础的工作流网，并给出了相关的分析技术， 奠定了p e t r i 网建模工作流的基础。 工作流模型主要以下几个基本的路由结构1 8 】： ( 1 ) 顺序路由一个任务执行结束后，再执行下一个任务。 ( 2 ) 与连接 多个任务具有同一个后继任务，必须当多个前驱的任务都完成 后，才激发后继的一个任务。 ( 3 ) 或连接多个任务具有同一个后继任务，只要有一个前驱的任务完成， 就激发后继的一个任务。 ( 4 ) 与分支一个任务有多个后继的任务，当前驱的任务完成后，后继的任 务都激发。 ( 5 ) 或分支一个任务有多个后继的任务，当前驱的任务完成后，有选择地 激发一个后继的任务。或分支又可以分为隐式或分支和显式或分支。 ( 6 ) 重复路由循环地执行某一个或多个任务。 1 1 2 面向服务的体系结构 1 介绍 面向服务的体系结构( s e i c e o f i c m e d c 衄e c t u r e ，s o a ) 是一个组件模型， 它将应用程序的不同功能单元( 称为服务) 通过这些服务之间定义良好的接口和 契约联系起来。接口是采用中立的方式进行定义的，它应该独立于实现服务的硬 件平台、操作系统和编程语言。这使得构建在各种这样的系统中的服务可以以一 种统一和通用的方式进行交互。 2 体系结构 面向服务的体系结构是基于三种角色( 服务提供者、服务注册中心和服务请求者) 之间的交互1 1 1 1 。交互具体涉及到发布、查找和绑定三种操作。这些角色和操作一起 作用于服务构件：服务软件模块及其描述。服务提供者定义服务描述，并把它发布 基于o o s 的服务合成建模与分析 到服务请求者或服务注册中心。服务请求者使用查找操作从本地或服务注册中心搜 索服务描述，然后使用服务描述与服务提供者进行绑定，并调用相应的服务实现， 同它交互。下图展示了这些操作、提供这些操作的组件以及它们之间的交互。 3 服务协议栈 图1 1 面向服务的体系结构模型 实现一个完整的体系结构，需要有一系列的协议规范来支撑，下图是当前投入使用 的协议栈【1 2 j ： w s d l ( w e bs e i c e sd e s c d p t i o nh n g 岫g e ) ：是一个x m l 文档，由i b a 、i n t e l 、 i b m 利微软等开发商提出，用于w e b 服务的描述，位于服务描述层。它并不是完 整的服务描述，只包括了服务接口的原始技术描述。w s d l 是w e b 服务的接口定义 语言i d l ( i n l e 血c ed e 丘l l i t i o nl a n g u a g c ) ，本质上描述了w c b 服务的以下三个基本属 性： 服务做些什么一服务所提供的操作( 方法) 如何访问服务数据格式详情以及访问服务操作的必要协议 服务位于何处有特定协议决定的网络地址 x l a n g 【1 3 】，w s f l 【1 4 1 ，b p e l f l 5 】：是以服务为基础，表示服务之间相互调用的业务 基于o o s 的服务合成建模与分析 流程和数据依赖的业务流程建模语言。到目前为止，已经出现了不少具有一定特色 但又有不少类似之处的语言，又如w s c l 【1 6 1 ，w s a 【1 7 】，b p m l 【18 1 ，d a m l s f l 9 j 等。 x l a n g ，w s f lb p e le t c s t a t i c d m d i d i r e c t 哩，d d i w s d l s o a p x m “s c h e n m ) h 丌卫s m t p ，f t be t c 图1 2 服务的协议栈 1 2 服务合成 服务合成就是合成网络上存在的服务，产生新的服务。 1 2 1 定义 单一的服务所提供的能力有限，当我们要实现比较复杂的任务时，往往不能满足我 们的需要。因此我们需要合成存在的服务，产生新的服务，解决新的问题，这个过 程称为服务合成。合成后的服务称为复合服务；用于合成复合服务的子服务称之为 组件服务【2 0 1 。服务合成结合两方面的技术：一方面是服务的适应性和一般性，另一 方面是业务流程管理【2 1 1 。 用服务合成实现业务流程，可以缩减对新的应用程序的开发成本。网络技术的发展 基于0 0 s 的服务合成建模与分析 必将进一步促进服务合成的发展。因为圈： ( 1 ) 随着越来越多的服务部署在网络上。网络不仅仅是静态网页的聚集处， 也是许多有用服务的提供者。 ( 2 ) 服务基于标准的广r p 协议，使得可以很容易地实现服务的整合。 ( 3 ) 网络上存在的是独立的服务提供者，因此合成多个服务满足用户的需要 是必然的。 服务合成可以是静态的或者是动态的。在静态的服务合成中，组件服务在设计时被 确定，如g e o f g i a 大学的s c e t 【冽；在动态的服务合成中，组件服务在运行时被确定， 如h p 公司的e f l o w 【2 卅和s t a n f o r d 大学的s w o r d 系统f 2 5 1 。 合成服务的执行方式有集中控制模式和p e c r p e e r 模式。在集中控制模式中，存在一 个集中的调度者，拥有全局信息，如h p 公司的e f l o w 系统【2 4 】；在p e e f _ p e e r 模式中， 信息分散，组件服务之间相互交换信息，并根据自身的状态来判断是否执行，如澳 大利亚新南威尔士大学的s e 峪e r v 系统【2 6 】。 1 2 2服务合成涉及的技术 服务合成的开发和部署涉及以下几个关键技术【2 2 1表示( r e p r e s e n t a ti o n ) 如何用合适的方式去表示服务合成过程? 2分析( a n a i y s is ) 如何在合成服务运行之前保证业务流程的正确执行，不存在死锁、活锁等逻辑错误? 3查找( d is c o v e r y ) 如何去查找合适的组件服务? 人为的还是自动的? 基于0 0 s 的服务合成建模与分析 4选择( s e i e c t i o n ) 当存在多个满足相同功能，具有不同q o s 的服务时，按照什么样的标准和用什么样 的方式去选择? 5 交互性( i n t e r o p e r a b i | i t y ) 组件服务之间采用何种交互方式： p i p ea n df i l t e r s 或者t h eh u bo rs p o k et o p o l o g y 6 运行( e x e c u t i o n ) 如何用一种合适的技术去执行具体的合成服务? 7效率( e f f i c i e n c y ) 如何使合成服务高效地运行? 8 监控( m o n i t o r i n g ) 如何用一种监控技术去分析服务的执行? 1 2 3 本文的研究重点及相关的研究 服务的合成可以有不同的研究角度，如事务【2 ”，会话1 2 8 。0 1 等。本文以工作流的角度 研究服务合成。整个合成服务表示为一个业务流程。 1建模服务合成过程 目前为止，已经存在一些对服务合成模型的研究【3 1 】。在工业界已经开发了一些工作 流语言用于表为亡服务合成，如w s f l 【1 4 】，x l a n g 【1 3 1 ，b p e l 4 w s 【1 5 】，d a m l s 【1 9 1 。b p e l 4 w s 融合了w s f l 和x l a n g 的特点，已经成为业务流程建模的事实标准。但是他们都没有形 式化的语义，不能对整个合成过程进行逻辑验证【3 2 】。 已经存在了一些研究用p e t r i 网建模服务的合成。m a s s i m om e c e l l a 【3 3 1 提出了 基于0 0 s 的服务合成建模与分析 e s e r v i c e 网( e sn e t ) 和o r c h e s t r a t i o n 网( 0 一n e t ) 分别建模组件服务和合成服 务。a k s c h j m i g p 4 l 和x i a o c h u a ny i 【2 8 1 分别提出了用c g s p n ( c o l o r e dg e n e r a l i z e d s t o c h a s t i cp e t r in e t ) 和w e bs e r v i c e sp r o c e s sn e t ( w s p n ) 建模合成服务。这 四个网都是基于着色网的。用一般的p e t r i 网建模服务的合成出现在论文 3 5 3 7 中， 分别提出的是w e b 服务流程网( w e bs e r v i c e sf l o wn e t ，w s f n ) ，服务网( s e r v i c e s n e t ，s n ) 和服务资源网( s e r v i c e r e s o u r c en e t ，s r n ) 。在论文 3 8 中提出了用 p e t r i 网建模g r i d 工作流。 一些别的模型也被用来建模和分析服务合成。 3 6 提出了基于p e t r i 网的w e b 服务代 数：w e bs e r v i c ea 1 9 e b r a ， 3 9 提出了基于p e t r 网的服务建模语言：f u n s o f tn e t s 。 4 0 提出了用服务合成图( s e r v i c e sc o m p o s i t i o n sg r a p h ，s c g ) 和对应的属性图。 有向图【4 1 彤】，状态图( s t a t e c h a r t ) 【“4 “，u m l l 4 7 4 8 1 ，进程代数4 9 。5 0 l 都被用来建模服 务合成。 工作流领域已经存在大量的用p e t r i 网建模的研究9 j 1 5 ”。 2基于0 0 s 的组件服务的选择和合成服务的0 0 s 计算 涉及到服务q o s 模型的定义与表示、q o s 选择策略的定义与表示以及相应的选择 算法。 c 0 s 在网络阱5 5 1 ，实时系统【5 6 】和中间件领域【5 7 j 已经有许多的研究。目前在工作流 领域和服务合成领域，研究人员已经显示出对q o s 的兴趣。 【5 8 5 9 】提出了时间 ( t i i n e ) 、价格( c o s l ) 、可靠性( r e l i a b n i t y ) 和保真度( 削e l j t y ) 的q o s 模型，并 利用基于缩减规则的s w r ( s t o c b a s l i cw o r k f l o wr e d u c j o n 创g 硎t h m ) 算法计算工 作流和服务过程的q o s 。【6 0 】提出了一个复杂的q o s 模型，表示了服务合成工作 流的基本特点。它将o o s 分为三大类：通用的，网络服务特定的，任务特定的。 【6 1 】针对服务合成中采用的工作流模式给出了相应的q o s 聚合算法。 基于0 0 s 的服务合成建模与分析 通过上面的介绍，可以看到现有的研究没有在模型中显式地表示服务的q o s 和基 于q o s 的对组件服务的选择。因此，本文提出了一个基于q o s 的工作流模型 s cc p n 。它是一个基于着色网的模型，用颜色集建模组件服务的q o s 和选择策 略，用卫式函数建模组件服务的选择。c p n t 0 0 1 s 被用来建模合成的服务，模拟服 务的选择、绑定和执行，同时利用这个工具提供的形式化方法分析整个业务流程 的并发性质。最后，基于s c c p n 模型，我们提出了一个计算业务流程q o s 的算 法。 本文采用的q o s 模型：时间( t i i i l e ) ，价格( ( p r i c e ) ，可用性( a i l a b i l h y ) ， 可 靠性( r e l i a b i l n y ) ，声誉度( r 印u t a t i o n ) 。可以根据具体的应用，采用不同的q o s 模型。 本文采用的选择策略有：随机策略( r a n d o m ) 、轮转策略( r o u n d r 曲i n ) 、缺省策 略( d e 伍u h ) 、时间优先( e t i i i l e ) 、价格优先( e p r i c e ) 、高可用性( h a v a i l a b i l “y ) 、 高可靠性( h r e l i a b i l i t y ) 、高声誉度( h r e p u t a t i o n ) 。根据不同的q o s 模型，可以 定义不同的选择策略。 1 2 4创新之处 本文的主要贡献在于提出了基于q o s 的服务合成模型，显式地表示服务的q o s ， 选择策略以及基于q o s 的对组件服务的选择。在模型的基础上，提出了基于用户 选择策略和组件服务o o s 的服务选择算法。当存在多个满足用户需要的组件服务 时，采用基于效用函数的加权平均算法选出具有最高值的组件服务。 1 2 5本文的假设 本文假设关于合成服务的业务流程已经确定，满足业务流程中各个任务的等价服 务可以通过一个信患服务获得。 基于o d s 的服务合成建模与分析 第2 章着色网 p e t r i 网【1 】的概念是1 9 6 2 年c a r la d a mp e t r j 在他的博士论文中提出来的，随后引 起了学术界和工业界的极大关注，并使之成为研究并行分布式系统强有力的图形 数学工具。p e t r i 网以研究模型系统的结构和动态行为为目标，着眼于系统各种 状态及状态变化之间的关系。 在p e t r i 网研究与发展的过程中，其应用范围已经远远超过了计算机科学本身的 领域，成为描述离散事件动态系统的有力工具。其应用领域主要有：分布式系统、 并发和并行计算、工业制造系统、性能评价、通信协议、工作流、化学系统、逻 辑推理、形式语言、决策模型等等。 2 1 p e t r i 网 p e t r i 网系统的主要特点来自外延公理1 3 州，根据外延公理，一个变迁( 事件) 的发生完全由它的外延( 自 集和后集) 决定，与系统全局状态无关。因而p c t r i 网系统是异步并发的“自由王国”，没有主宰全局的中央控制，所以网系统的 主要应用方向是分布式系统和并发处理。 2 1 1 基本原理 1对偶原理 p e t 一网的对偶原理f 1 1 i ep n c l p ko f d 瑚m yf o r p e t r in e 埘 ( 1 ) p e t r i 网有两个互不相交的元素集合：p 元素( 尸二b 蛔研招) 和r 元素 ( 心 b m 册船) ； 基于0 0 s 的服务合成建模与分析 ( 2 ) 实际世界的实体， 元素； ( 3 ) 实际世界的实体， 元素。 如条件、位置、资源、等待池、通道等，可以解释为p 如事件、活动、语句执行、消息传递等，可以解释为r 2局部原理 p e t 一网的局部原理r r h ep d n d p l eo fh c a h t yf o rp e t r in e 哟 ( 1 ) 变迁的局部性定义为它的前集和后集的总和； ( 2 ) 一个变迁的行为完全依赖于它的局部性和它自身。 3 并发原理 p e t r i 网的并发原理盯h ep i i n d p i eo fc 蛐衄r 他n c yf o rp e t r in e t s ) 局部性互不相交的变迁可以独立发生( 并发) 。 2 1 2p e t 一网的表示 1图形表示 p e 嫡f 嘎的图形表示( t h eg m p h i c a lr e p r 刚1 t a t j o nf o r p e t r in e t s ) ( 1 ) p 元素( p - e 砌n 绷如) 的图形符号是圆圈； ( 2 ) 丁元素( p e 嗍册坫) 的图形符号是矩形； ( 3 ) 弧连接每个t 元素和它的局部性； ( 4 ) 另外，还有一些其它描述，如名字、标记( t o k c n s ) 、守卫函数( g u 缸d s f u n c t i o n ) 等。 2 代数表示 p e 喇网的代数表示f 1 1 l ea l g e b m i cr e p m s 蛐t a f o rp e t r i 唧 ( 1 ) 对每个图形描述，都有一个包含等价信息的代数描述； ( 2 ) 代数描述包括位置集、变迁集、弧集、以及其他描述信息。 2 1 3 形式化定义 1 网 定义1 一个网是一个三元组= ( p l f ) 这里 1 2 基于o o s 的服务合成建模与分析 ( 1 ) p 是位置集； ( 2 ) t 是变迁集，且p n t = a ； ( 3 ) f ( p t ) u ( t p ) 是流关系( 弧集) 。 如果p 和r 是有限的，则网是有限的。令u p u t ， 则_ = p i 化町e ，) 表示“的前集，“= p i 他一，表示h 的后集。如果吻自f ：p 芦f 厂7 f 。，称网 为纯网( p u f en c t ) 。 2p e tr i 网 定义2 一个( 带标记的) p e t r i 网是一个五元组p = ( p ，l b ，e 知) ，其中 ( 1 ) p 是位置集； ( 2 ) 丁是变迁集，且p n r = a ； ( 3 ) b ：t x p 一是向后关联函数： ( 4 ) ，r p 一是向前关联函数； ( 5 ) 蛳：p 一是初始标识。 一个标识可表示为一个l 尸l 元向量，第f 个元素表示位置a 中的标记数。如果一 个标识m 有_ 1 1 个标记在位置p f 中，有七个标记在位置a 中，则该标识可表示为 m = _ l l a + 七a ( ”+ ”是p 上多重集的加运算) 。 如果p e t r i 网是一个纯网，则完全可以用一个关联矩阵来描述p e t r i 网的静态结构。 关联矩阵c = 【c 羽，其中。口；f 如p i ) 一曰如n ) 。 2 1 4 动态行为 图形和矩阵可以表达p e t r i 网的静态特征，而p e t r i 网标识的动态演变则由变迁发 生来体现。使能( e 船b l i n g ) 和实施( f 缸i n g ) 规则都与变迁有关，使能规则表达 变迁发生的条件，实施规则定义变迁的发生。 1 使能条件 定义3 ( 吼a b h n g ) 如果v p p 丑( f ，p ) s 肘0 ) ，则称变迁f r 在标识m 下是使 基于0 0 s 的服务合成建模与分析 能的( c n a b k d ) ，用脚d 表示。若胍吩且岬) ，则称变迁和在标识肘下 是并发使能的( c o n c i l r r e m l ye m b l e d ) 。 用砌( d 表示标识m 下所有使能变迁的集合，勘( d = r rlm r ) 。用 k 吣( m 表示在标识m 下实施寸后新使能的变迁集， k w f y ( m 功= f 丁 i 坛助( m 一曰( f ，) + ，( 功) ( 罐砌( m b ( 彩) vo = 坊) 。注意一个变迁在它自己实施 后仍然使能，我们把它作为新使能变迁看待。 2 实施规则 定义4 ( n n 酌如果f 在标识m 下是使能的，那么f 可以实施并产生一个新的 后继标识m ，m 可由下面方程给出： 只凹) = 肘p ) 一b ( f ，力+ 耶，p ) 用肘【f ) m 表示从标识m 实施变迁f 到达标识m 。从实施规则可知，p e t r i 网模型 的状态变化是局部的，它仅涉及通过输入输出弧所连接的位置的状态变化，因此 p e t f i 网标识本质上是分布的。 2 1 5 性质 我们把p e t r i 网的性质分为结构( 静态) 性质和行为( 动态) 性质。结构性质 可从关联矩阵和网的结构图获得，与初始标识无关。行为性质可从网的可达图 或覆盖树获得，它依赖于初始标识。 1可达性 定义5 若存在f r ，使脚f ) m ，则称j 】l f - 从m 直接可达。如果存在变迁序列仃： f l ，“_ 1 使得一1 ，2 ，n - 1 ，都有m 盼尬小则称m 。从m l 可达。用兄，( 0 表示从标识m 可达的所有标识的集合。 2有界性 定义6 如果存在七mv j 讯三尺甄 埘，有坳p ，肘函) 蔓七，则称这个p e t r i 网是有 界的( b o u d e d ) 。 基于0 1 0 s 的服务合成建模与分析 3活性 定义7 如果v f l 蓰虱s ( f 0 ) ，都存在m j t 双帅使m f ) ，则称这个p c t r i 网 是活的( 1 i v e ) 。 4不变量 定义8 一个p 半流( p - s e m i n o w ) 是满足c t y = o 的向量y ：卜。c 是网的 关联矩阵。 p 不变量( p - i i a r j a n t ) 是指在任何标识下( 用y 加权) 的标记个数之和等于初始标 识下( 用v 加权) 的标记个数之和。如果p - s e m i n o w 覆盖所有的位置，贝对任 何可达标识，位置的标记数是有限的。 定义9 一个r 半流( f s e l l l i f l o w ) 是满足线性方程c x = o 的向量x ：卜mc 是网的关联矩阵。 丁不变量( 弘i l l v a r i a n t ) 是指从标识m 出发，经过变迁数目等于f s e m i n o w 的任何 变迁实施序列都能够返回标识m 。 可见，可达性、有界性和活性是p e t r i 网的行为性质，而p _ s e m i n o w 和s e m i 玎o w 是p e t r i 网的结构性质。 2 2 着色网 着色网( c o l o r e dp e t r in e t s ) 简称c p n ，是由k u nj e 惦e n 于1 9 7 9 年提出【6 2 侧。 它是一种高级p e t r i 网模型，它和普通p e t r i 网的关系如同程序设计语言中的高级 语言和汇编语言的关系一样。它通过对位置，托肯加以颜色类型的标定，对变迁 和弧加以条件的约束，使建模者可以更容易摒弃系统的琐碎细节，抓住系统的本 质行为特征，大大增强了对服务系统的建模能力。 2 2 1 着色网的表示 着色网结合了p e t r i 网和编程语言( s t a n d a r dm l ) 的特点，基本的p e t f i 网结构表示被 基于o o s 的服务合成建模与分析 建模系统的结构和动态行为，编程语言定义数据类型和对数据的操作。着色网提 供了模块的概念，可以实现系统的分层建模，建立大型复杂的实际模型。 着色网中基本元素的相应标识说明如下【删： ( 1 ) 每个托肯 颜色：对托肯加以区分，表示不同的资源( 如不同身份的人员，不同类 型的处理对象等) 。 ( 2 ) 每个位置 名字：用于标识不同的位置。 颜色集：说明位置内所包含的托肯的类型。每个位置只对应一种类型， 每个类型是一个颜色的集合，限定了该位置中托肯所能取的颜色的范围。和程序 设计语言相比较，就可以发现颜色集相当于程序设计语言中的类型，而托肯的颜 色则相当于变量的取值。+ 所以，有些情况下也把颜色集称为类型。 初始化标识：不同颜色托肯的初始化分布。 ( 3 ) 每个变迁 - 名字：用于标识不同的变迁。 卫式函数：表示变迁发生需要满足的条件，可以用来反映对不同颜色 的托肯进行不同的处理。 ( 4 ) 每个弧 弧表达式：表示变迁发生时，网的状态如何改变 2 2 2 着色网的形式化定义 着色网的分析是基于多重集的处理，先介绍多重集，然后介绍着色网的形式化 定义【6 6 】。 1 多重集 定义1 0 设s 为一个非空有限集，s 上的多重集伽“埘耐d w r s 或6 昭卯盯回是 一个函数m ：s - z 。多重集州也经常以荟肼o ) 。s 的形式来表示口符号s m 表示 基于o o s 的服务合成建模与分析 由所有s 上的多重集所组成的集合。一个s 上的多重集经常代表一组元素，其中 元素j s 出现l m o ) 1 次。对于m ，m ：s 。以及甩z ，满足下列运算规则： ”埘z 。萎帆o ) 幌。鹏 m - 嘲z 2 善，。) 吨( s ) ) s m ，小：当且仅当s ：b 。0 ) = 州：o ) l 川。 ，则石是死的； 3 ) 如果p m 船( f ) ，丑f j ，r 双m ) ，交臼；则x 是活的。 2 2 5 工具 已经存在大量的工具用于着色网的建模，分析和模拟。 1a l p h a s i m 工具的特点： 支持的p e t r i 网：高级网，时间p e t r i 网 组件：图形编辑器，托肯游戏，快速模拟，简单的性能评价 环境： 摹于0 0 s 的服务合成建模与分析 s u n u s 、s o i a r l s 、m sv 缅d o w sn i 主页：丝p ；f 避虹b g ! 曲魍堡缝盟d 幽! y 丝b p 殴也虹b a 叠塑f a 垃b 签蛔蜒虫! 工具描述： 钮j h 郇i n l 是基于p e t r i 网的图形化、离散事件模拟工具。它允许用户图形化地 建立p e t r i 网模型，输入数据( 时间延迟，路由规则，初始化托肯分布) ，运行模 拟和查看模拟结果。可以建立的模型有随机，时间和着色网。 模型可以被分层地建立，从底到顶或从顶到底。建模者不需要写任何代码就可以 建立满意的模型。a l p h s s i m 模型可以和外部的代码连接；代码可以使用任何 平台支持的语言。它可以自动地收集位置变化，延时，变迁激活速率和属性等相 关信息。a i j h s s i f i l 已经被运用在广泛的领域，包括军事指挥和控制，计算机 硬件系统制造系统和排队系统等。 2 d e s i g n c p n 工具的特点： 支持的p e t r i 网：高级p e t r i 网，时间p e t r i 网 组件：图形编辑器，托肯游戏，快速模拟，状态空问，简单性能分析，交 换文件格式 环境： s u n ，h p ，s i l i c o ng r a p h i c s ，l m u x 主页：堑! p ；型邋d 4 i 塑i ! a h ! d 型亟s i g n 垒“ 工具描述： d e s i g n c p n 是最早支持c p n 的工具之一，目前正在被工具c p nt o o l s 所代替。 做为一个被广泛使用的软件工具，有四个部分组成： c p n 编辑器：支持模型的构造，更改和语法检查 c p n 模拟器：支持交互式的和自动式的模拟 发生图工具：支持发生图的构造和分析 性能工具：支持模型性能分析的模拟 这四个部分可以被用来建模，模拟和分析大型的分层凹n 模型。 基于0 0 s 的服务合成建摸与分析 3 g r e a t s p n 工具的特点： 支持的p e t r i 网：高级网，随机p e t r i 网，时间p e t r i 网 组件：图形编辑器，托肯游戏，快速模拟，状态空间，缩减的状态空间，位 置不变量，变迁不变量，结构化分析，高级性能分析 环境： s u l l ，i 知u x ，s o h l r i so np ( xa n ds u n w o r k s t a t i o i l s 主页：蜒! p ；丛啦盟照m 塾豇鱼! 型= 钽a ! 避型 工具描述： g r e a t s p n 是一个软件包，用广义随机p e t r i 网和颜色的扩展网( 随机良构网) 对 分布式系统进行建模，验证和性能评价。这个工具提供了友好的框架进行时间 p e t r j 网的建模。它实现了有效的分析算法，使得它可以应用到相当复杂的系统。 4h i 0 p n t o o i 工具的特点： 支持的p e t r i 网：高级网，随机p e t “网 组件：图形编辑器，托肯游戏，状态空间，位置不变量，变迁不变量，高级 性能分析，交换文件格式 环境：s u n 主页：坠l p ；越垒：塑竖监i 塾垂匹垫丝虹呈：婪查：照q d m 丛坠d ：幽蛙 工具描述： h i q p n 1 b o l 是一个软件工具，用于声明和分析分层的组合排队p c t r i 网。分层的 组合排队p c t r i 网是排队网络和p e t r i 网的组合形式化模型。h i q p n 1 b 0 1 支持分 层建模，并进行定量的和定性的分析。这一点