（计算机应用技术专业论文）有色时间petri网与随机petri网应用研究.pdf

有色时间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 网( c t p n ) 是克服该问题的有效途径之一。多范式建模通过耦合和转换以整合不同方法建立的模型来综合利用多种形式化方法，可以全面准确地描述建模对象，可以大大的减轻仿真建模的工作量、提高整个仿真过程的效率。依据多范式建模理论，本文提出了基于规则化描述方法的c t p n 建模方法，同时发挥两种建模方法的优势，有利于全面准确地反映系统的设计内容，并以汽车车身控制系统为例为其建立模型，为复杂系统建模和模拟验证提供一定的借鉴。工作流管理技术是9 0 年代初兴起的软件技术，工作流是一个业务过程的全部或部分自动执行，为了实现工作流管理功能，我们必须将业务过程从现实世界中抽象出来，并用一种形式化方法对其进行描述，其结果称为是工作流模型。p e t r i 网作为一种图形化的数学建模工具，适合于工作流领域的建模需求，提出了基于广义随机p e t r i 网( g s p n ) 的工作流建模方法，将工作流模型映射为广义随机工作流网模型，并运用可达图法对工作流正确性和可靠性进行检查；利用g s p n 与马尔可夫链的同构关系，采用g s p n 和马尔可夫链相结合的工作流性能分析方法，为工作流性能的有效评估提供理论依据：并通过实例验证该方法的有效性。关键词：有色时间p e t r i 网；规则化描述方法；多范式建模；工作流模型；广义随机p e t r i 网r e s e a r c ho nt h eu s eo fc o l o r e dt i m e dp e t r in e ta n ds t o c h a s t i cp e t r in e ta bs t r a c tp e t r in e ti saf o r m a l ，g r a p h i c a l ，e x e e u t a b l et e c h n i q u ef o rt h es p e c i f i c a t i o na n da n a l y s i so fc o n c u r r e n t ，d i s c r e t e e v e n td y n a m i cs y s t e m s h o w e v e r , w h e nm o d e l i n gc o m p l i c a t e dc o n t r o ls y s t e m s ，b a s i cp e t r in e tm a yl e a dt ot h ep r o b l e mo fn o d en u m b e re x p l o s i o n c o l o r e dt i m e dp e t r in e t ( c t p n ) i saw a yt os o l v et h i sp r o b l e m m u l t i p a r a d i g mm o d e l i n g ，c o n c e r n e dw i t ht h ec o u p l i n go fa n dt r a n s f o r m a t i o nb e t w e e nm o d e l sd e s c r i b e di nd i f f e r e n tf o r m a l i s m s ，c a ng i v ear e p r e s e n t a t i o no fm o d e l si nd i v e r s ef o r m a l i s m s ，a td i f f e r e n tl e v e l so fa b s t r a c t i o n ，a n dt h eb e h a v i o r c o n s e r v i n gt r a n s f o r m a t i o nb e t w e e nt h ef o r m a l i s m si sd e m o n s t r a t e d s om o d e l i n go fc t p nd e r i v e df r o mr u l ed e s c r i p t i o nm e t h o d 。w h i c ht a k e sa d v a n t a g e so ft w om o d e l i n gm e t h o d s ，i sp r e s e n t e d a n da l s ot h em e t h o di si l l u s t r a t e dt h r o u g hm o d e l i n gp r o c e s so fa u t o b o d yc o n t r o ls y s t e m ，w h i c hw i l lh e l pt om o d e l ，a n a l y z ea n ds i m u l a t ef o rc o m p l i c a t e ds y s t e m s w o r k f l o wm a n a g e m e n tt e c h n i q u e sw e r ed e v e l o p e di ne a r l y19 9 0 s w o r k f l o wi st h ea u t o m a t i o no fab u s i n e s sp r o c e s si nw h o l eo rp a r t t oa c h i e v et h ef u n c t i o no fw o r k f l o wm a n a g e m e n t ，t h eb u s i n e s sp r o c e s sm u s tb ea b s t r a c t e df r o mt h er e a lw o r l da n dd e s c r i b e db yak i n do ff o r m a lm e t h o d t h er e s u l ti sw o r k f l o wm o d e l a sak i n do fg r a p h i c a la n dm a t h e m a t i c a lm o d e l i n gt o o l s ，p e t r in e ti sa p p l i c a b l et ot h em o d e l i n gr e q u i r e m e n to fw o r k f l o w am e t h o do fm o d e l i n gf o rw o r k f l o wb a s e do ng e n e r a l i z e ds t o c h a s t i cp e t r in e t ( g s p n ) i sp r o p o s e d t h ew o r k f l o wd e f i n i t i o no fw o r k f l o wm a n a g e m e n tc o a l i t i o ni sm a p p e dt og e n e r a l i z e ds t o c h a s t i cw o r k f l o wn e t t h ev a l i d i t ya n dr e l i a b i l i t yi sc h e c k e du s i n gr e a c h a b l eg r a p hm e t h o d b yu t i l i z i n gt h ee q u i v a l e n c er e l a t i o nb e t w e e ng s p na n dm a r k o vc h a i n ，am e t h o do fc o m b i n i n gg s p na n dm a r k o vc h a i ni su s e dt oa n a l y z et h ep e r f o r m a n c eo fw o r k f l o w t h ee f f e c t i v e n e s so ft h i sm e t h o di sv e r i f i e db ya na p p l i c a t i o nc a s e k e y w o r d s ：c o l o r e dt i m e dp e t r in e t ；r u l ed e s c r i p t i o nm e t h o d ；m u l t i - p a r a d i g mm o d e l i n g ；w o r k f l o wm o d e l ；g e n e r a l i z e ds t o c h a s t i cp e t r in e t插图目录图2 1p e t r i 网的图形表示9图2 2 有界p e t r i 网一11图2 3 有界p e t r i 网的可达标识图r g ( z ) 1 2图2 4 数据处理的p e t r i 网模型1 3图2 5 数据处理功能子网1 4图3 1 车身控制系统软件框架图2 1图3 2 树状层次模型2 2图3 3 规则化描述方法的规则处理过程2 6图3 4 基于规则化描述方法的p e t r i 网建模思路一2 7图3 5 夜行灯、前照灯行为关系的p e t r i 网模型2 8图3 - 6 前雨刮器行为关系的p e t r i 网模型3 0图3 7 电动玻璃窗行为关系的p e t r i 网模型3 1图4 1 工作流管理系统特性3 7图4 2 广义随机p e t r i 工作流网的4 种路由结构4 l图4 3 某印刷包装企业生产流程图4 4图4 4 图4 3 映射得到的广义随机工作流网4 4图4 5 图4 4 同构的马尔可夫链4 4表格目录表3 1 规则化描述方法和p e t r i 网建模的比较2 7表3 2 图3 5 模型中元素含义2 8表3 3 图3 - 6 模型中元素含义3 0表3 4 图3 7 模型中元素含义3 2i v独创性声明本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得金魍王些盔堂或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。、一，学位论文作者签名：j签字日期：a 一7 事；习3ln学位论文版权使用授权书本学位论文作者完全了解金目垦王些太堂有关保留、使用学位论文的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权盒壁至丝太堂可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。( 保密的学位论文在解密后适用本授权书)、_ ，学位论文作者签名：j签字日期：函时 葛学位论文作者毕业后去向：工作单位：通讯地址：导师签名：签字日期：电话：邮编：1 ) 耖硼t ，夕；3致谢本文是在导师陆阳教授的严格要求和悉心指导下完成的。在两年半的研究生学习期间，陆老师对我的学习和生活均关心备至，倾注了大量的心血，使我在各方面均有长足的进步。陆老师活跃的学术思想，渊博的知识，坚韧的毅力，忘我的工作态度，严谨的工作作风，对事物敏锐的观察力都令我钦佩不已，给我留下了深刻的印象。陆老师对我的鼓励和帮助，将使我终生受益。值此论文完成之际，谨向导师致以衷心的感谢。感谢d e c s j x 组的所有成员，小组讨论时大家的发言给了我启发和灵感；感谢我的同学杨晴晴、郭智奇以及其他实验室成员，他们在生活和学习上都给了我很大的帮助与鼓励。感谢其他老师和同学在我攻读硕士学位期间给予我无私的帮助和友情。同时，我要感谢父母和其他家人对我的支持和关爱，是他们在背后默默的支持使我能顺利的完成硕士研究生的学业。最后，真诚地感谢有关专家和学者对本文的评阅和指导。作者：丁峰2 0 0 9 年0 3 月1 1 课题研究背景及目的第一章绪论p e t r i 网是最近十几年来发展较为迅速的一种离散事件系统( d e s ：d i s c r e t ee v e n ts y s t e m ) 形式化建模方法，具有很强的描述能力。首先，作为一种图形化数学工具，它能对d e s 中的异步、并发、冲突等重要特征进行直观描述，并进行分析和研究；其次，作为一种逻辑层次的建模工具，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网模型节点过多问题的有效途径之一。复杂系统往往有多个异构系统组成，在分析和设计的各个阶段也需要不同的形式化方法来描述系统，每一种建模方法都有自身的优点和缺点、描述现实世界的不同角度。多范式建模( m u l t i p a r a d i g mm o d e l i n g ) 通过耦合和转换以整合不同方法建立的模型综合利用多种形式化方法，建模可以在不同抽象级别从不同角度描述现实世界，充分发挥每种描述方法的优势，更全面、准确地对现实世界建模弘j 。规则化描述方法( r d m ：r u l ed e s c r i p t i o nm e t h o d ) 【3j 参考智能控制分层模块化思想，结合离散事件控制系统的特点，提出一种更直观、更贴近系统本原的基于对象的分层模型。它是通过构建一条一条的逻辑规则表达式描述各对象之间的行为逻辑关系。但是规则库本身是静态的知识描述，模拟执行需要额外的控制策略，验证比较困难。p e t r i 网能够动态运行有利于模型的模拟执行和分析，具备一套严密的数学理论，各种技术有利于验证和分析。鉴于此，本文提出了基于规则化描述的有色时间p e t r i 网建模方法，同时发挥两种建模方法的优势，有利于全面准确地反映系统的设计内容。汽车车身控制系统用于对车身上诸如车灯、雨刮器、电动玻璃窗等各种器件进行方便灵活的控制，是一种典型的d e s 。传统上依靠复杂的线束来连接众多电器，成为汽车主要故障源之一，近年来在中高档汽车上正逐渐被由现场总线连接的车身控制模块所取代。其方法是把各种器件连接到分布于车身中的多个智能控制节点上，每个智能控制节点都是拥有一定计算和存储资源的嵌入式处理单元。智能控制节点通过总线连接在一起，通过智能控制节点中的软件来实现对各种器件的综合控制，也即用软件逻辑取代传统车身控制系统中的硬件逻辑，具有更好的灵活性和易维护性1 4 。如何对车身控制系统进行建模和仿真是其研究的重要内容，采用形式化方法建模和分析这类复杂实时系统可以减少设计和开发过程中的错误，提高系统运行的可靠性和安全性。但是由于没有哪一种建模方法可以说是最好的或者适合任何情况和需求的，依据多范式建模思想，以车身控制系统为例，阐述了基于规则化描述方法的c t p n 建模的优势。工作流技术是2 0 世纪9 0 年代初随业务流程重组( b p r ：b u s i n e s sp r o c e s sr e e n g i n e e r i n g ) 而兴起的，该技术可以被广泛地应用于企业的过程建模，是实现流程执行和控制管理的一条有效途径。国际工作流管理联盟( w f m c ：w o r k f l o wm a n a g e m e n tc o a l i t i o n ) 对工作流的定义：工作流是指整个或部分经营过程在计算机支持下的全自动或半自动化。工作流管理系统指的是一个能定义、创建和管理工作流的软件系统。工作流建模是工作流管理系统具有的基本功能，其主要完成对目标系统业务过程的抽象表示 5 6 】。许多工作流管理系统缺乏直观性，且不具备仿真功能，不能对工作流性能进行有效的分析。这些问题都需要有一种有效的数学化建模方法。研究人员提出过各种工作流的建模方法，如基于活动网络的工作流模型，基于语言行为理论的工作流模型，基于p e t r i 网的工作流模型等。当考虑的工作流过程较为复杂，如存在并发、冲突等情况时，采用高层次的形式描述模型p e t r i网更为实用。p e t r i 网是一种图形化的数学建模工具。一方面它可以用图形化方式来描述工作流，另一方面它的形式化分析技术可用于检查工作流的正确性和可靠性，甚至进行性能分析【7 s 】。本文的又一目的在于将随机p e t r i 网技术引入到工作流的建模当中，并利用随机p e t r i 网理论及其与马尔可夫链的同构关系来分析工作流，为工作流性能的有效评估提供理论依据，并通过实例验证该方法的有效性。印刷包装企业的生产工艺流程复杂，有胶印、凹印、丝印、柔印、凹凸、烫金和模切等多道工艺；每一道工艺都有很多不同型号的设备，设备的局限性比较大、通用性很差；包装产品的品种、规格、技术要求等变化都很大。所以包装印刷生产过程涉及许多不同的作业，不同的作业按照一定的工艺顺序交替进行。包装印刷生产系统是一个典型的动态离散事件系统，它具有d e s 特征，是事件驱动，在空间和时间上是离散的，并且是异步不确定的。本文以某印刷包装企业的生产流程为例，建立其工作流程的广义随机p e t r i工作流网模型，利用g s p n 与马尔可夫链的同构关系，得到其对应的马尔可夫链，基于马尔可夫链的稳定状态概率进行所要求的系统性能分析，得到工作流模型的时间性能和变迁利用率等指标，可以规范企业的业务流程，发现其中的不合理环节，进而对企业的业务过程进行优化重组，所建立的业务过程模型本身就2是企业非常需要的知识库和规则库。1 2 国内外研究概况p e t r i 网的概念最早是在1 9 6 2 年c a r la d a mp e t r i 的博士论文中提出来的。从l9 8 0 年召开第一次p e t r i 网理论和应用的国际研讨会以来，每年一次的国际研讨会连续不断，p e t r i 网理论和应用在不断的充实和完善。它的纵向发展表现为：从基本的条件事件网，经过位置变迁网，发展到高级网( h l p n ：h i g h l e v e lp e t r in e t s ) 。它的横向发展表现为：从没有参数的网发展到时间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 网通过引入更高层次的观念来解决这个问题。更高层次的观念包括利用复杂数据结构的托肯、利用代数表达式来代表网元素等【9 1 。高级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网有更强的模拟能力，但是它可以使网模型更加简单、清晰一些【l0 1 。多范式建模的关键问题在于如何整合不同的模型，使数据和信息能够在在不同模型间自由地流动 1 1 】，其解决方法主要有两种：其一是使用一种一般标准语言作为接口语言；其二是使用元模型为建模方法建立统一的模型。b p z e i g l e r 于1 9 7 6 年在t h e o r yo f m o d e l i n ga n ds i m u l a t i o n ) ) 中提出了d e v s( d i s c r e t ee v e n ts y s t e ms p e c i f i c a t i o n ) 理论，以规范d e s 的各种形式化建模方法，并提供各种形式化方法建模和仿真的框架【l2 1 ，使离散事件系统的模型可以与连续系统的微分方程模型一样进行数学化操作 1 3 1 。由于d e v s 支持连续的时间基、能够很好地实现分层模块化以及面向对象的思想，所以在离散事件系统建模领域很受关注。目前研究d e v s 比较活跃的团体主要有美国亚利桑那州州立大学建模仿真综合中心( a c i m s ：a r i z o n ac e n t e rf o ri n t e g r a t i v em o d e l i n ga n ds i m u l a t i o n ) 、麦吉尔大学建模、仿真和设计实验室( m s d l m o d e l i n g ，s i m u l a t i o na n dd e s i g nl a b ) 以及韩国先进科学技术学院( k a i s t ：k o r e aa d v a n c e di n s t i t u t eo fs c i e n c ea n dt e c h n o l o g y ) 等。d e v s 优势在于对系统组成结构、通信机制、时间概念的支持；劣势是它一种贫语义的系统描述、缺乏系统行为的描述【l 引。正因为如此，将自动机、p e t r i 网等在描述系统行为方面有优势的形式化方法嵌入d e v s 也是必要的。工作流技术是2 0 世纪9 0 年代兴起的，被广泛的应用于企业的过程建模。1 9 9 33年国际工作流管理联盟成立，在工作流管理系统的相关术语、体系结构及应用编程接口等方面制定了一系列标准，并给出了工作流定义，标志着工作流的研究进入相对成熟的阶段。在国外的研究成果中，比较著名的有i b m 公司a l m a d e n 研究中心研究开发的基于持久消息队列的分布式工作流管理系统一e x o t i c a f m q m 【f l o wm a r k o nm e s s a g eq u e u em a n a g e r ) 、佐治亚大学计算机系研究开发的具有自适应能力的工作流管理系统一m e t e o r ( m a n a g i n ge n d 2 t 0 2 e n do p e r a t i o n s ) 、基于分布式主动数据库技术的工作流管理系统一w i d e ( w o r k f l o wo ni n t e l l i g e n ta n dd i s t r i b u t e dd a t a b a s ee n v i r o n m e n t ) 以及基于状态与活动图的工作流管理系统一m e n t o r( m i d d l e w a r ef o re n t e r p r i s e 2 w i d ew o r k f l o wm a n a g e m e n t ) 。相对于国外工作流技术的研究和发展，我国对工作流技术的研究还处于起步阶段，自主开发的工作流产品还是一个空白，在国外的工作流产品的引进和消化方面的工作也十分欠缺。目前在国内一些大学，如清华大学、西北大学、浙江大学、上海交通大学都己开展了对工作流技术的研究工作。其中，清华大学范玉顺教授设计、开发了c i m f l o w 工作流管理系统，提出了c i m f i o w 工作流模型；史美林教授带领的课题组提出了一个基于w w w 的通用工作流管理系统：w o w w w w o r k f l o wo nth ew o r l dw i d ew e b ，并将其与传统的c s c w 技术结合起来；浙江大学研制了工作流过程描述语言w p d l ( w o r k f l o wp r o c e s sd e f i n i t i o nl a n g u a g e ) ，实现了编译制导的工作流建模支撑平台；西安协同软件公司与西北大学合作开发的s y n c h o f l o w ，作为一个过程管理平台，其流程的定义方面已经达到了业界领先的水平，基于j 2 e e 的实现，使得系统具有足够的集成能力这些都取得了良好的研究成果。工作流建模是工作流管理系统具有的基本功能，其主要完成对目标系统业务过程的抽象表示。w i n o g r a d 与f l o r e s 在语言行为理论的基础上提出了一种基于对话的工作流模型【l5 】 16 1 ，这种工作流模型是从客户方与服务方这两个角色之间的语言行为交互上对工作流过程进行定义的。p e t r i 网也被用来建立工作流模型，v a n d e ra a l s t 用有色时间p e t r i 网对活动时间固定的工作流的一些时间特性作了分析【l7 】；李建强将工作流网分解成代表事件的t - 图，通过t - 图分析了工作流模型的时间性能、资源利用率等动态特性【1 8 】；c h i o l a 和m a r s a n 在p e t r i 网理论上给出了广义随机p e t r i 网的定义【1 9 1 ；m o l l y 验证了转移触发时间服从指数分布的随机p e t r i 网和马尔可夫链具有等价关系【z o j ；w a n gj i a c u n 将这一论证推广到广义随机p e t r i 网中1 | ，为随机p e t r i 网应用于模型性能分析铺平了道路。1 3 课题研究的关键问题及解决方法( 1 ) 依据多范式建模的思想，结合规则化描述方法和p e t r i 网建模各自的特点，提出了如下建模过程：控制策略通过规则化描述方法抽象描述易得其规则4式系统，规则式系统通过编译实现可以直接生成控制程序。如果控制策略的规则式系统非常复杂，难于发现其中的冲突等不安全因素，则可以将规则式系统转化为p e t r i 网模型来验证，进而完善规则式系统。( 2 ) 根据车身控制系统的特点选择建模工具。汽车车身控制系统是规模较大的d e s ，器件的状态多样，器件之间的行为关系较复杂，规则式中存在延时因子。有色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 网合成运算得到整个系统的模型。( 3 ) 工作流模型到随机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 网为系统的性能模型提供良好的描述手段；马尔可夫链为模型的评价提供坚实的数学基础。52 1p e t r i 网基本概念第二章p e t r i 网理论基础2 1 1p e t r i 网的直观理解p e t r i 网由c a r la d a mp e t r i 于1 9 6 2 年在他的博士论文【2 2 】中提出，是理论计算机科学包括自动机模型和形式语言理论的一个分支。p e t r i 网是一种形式化模型描述方法，它用四个元素为系统建模，分别是：库所( p l a c e )变迁( t r a n s i t i o n )弧( a r e )托肯( t o k e n ) 。它用库所、变迁、弧的连接表示系统的静态功能和结构，通过变迁点火和托肯的移动描述系统的动态行为【23 1 。p e t r i 网模型是状态变迁模型，可用来描述系统中各异步成分之间的关系，同时允许同时发生多个状态变迁，也是一个并发模型。在分析系统的状态行为的技术中，p e t r i 网模型具有自然、直观、简单易懂等特点，在并行系统分析、协议的验证、自动控制等方面有广泛的应用【2 4 1 。用p e t r i 网描述的系统有一个共同的特征：系统的动态行为表现为资源( 物质资源和信息资源) 的流动。在给出p e t r i 网( p n ) 形式描述之前，通过分布式系统几个基本行为模型描述的例子，先对p e t r i 网作一个直观的说明。库所用于描述可能的系统局部状态，例如：计算机和通信系统的队列、缓冲、资源等。变迁用于描述修改系统状态的事件，例如：计算机和通信系统的信息处理发送、资源的存取等。弧通过其指向来规定局部状态和事件之间的关系：它们表述局部状态对事件的触发以及由事件所引发的局部状态的转换。在p e t r i 网模型中，托肯包含在库所中，它们在库所中的动态的变化表示系统的不同状态。如果一个库所描述一个条件，它能包含或不包含一个托肯，当一个托肯表现在这个库所中，条件为真；否则为假。如果一个库所定义一个状态，在这个库所中的托肯个数用于规定这个状态。例如：在计算机和通信系统中，托肯可以用于表示处理的信息单元、资源单元和顾客、用户等对象实体。一个p e t r i 网模型的动态行为是由它的发生规则规定的，当使用等于l 的弧权时，如果一个变迁的所有输入库所( 这些库所连接到这个变迁，弧的方向是从库所到变迁) 至少包含一个托肯，那么这个变迁可能发生( 相关联的事件发生) 。对这种情况，这个变迁称为可发生的。一个可发生的变迁导致从它所有的输入库所中清除一个托肯，在它的每个输出库所( 这些库所连接到这个变迁，弧的方向从标迁到库所) 中产生一个托肯。当使用大于l 的弧权时，在变迁的每一个输入库所中都要包含至少等于连接弧权的托肯个数，它才可以实施：这个变6迁的发生将清除在该变迁的每一个输入库所的相应的托肯个数，并在变迁的每一个输出库所产生相应的托肯个数。变迁的发生是一个原子操作，清除输入库所的托肯和在输出库所产生托肯是一个不可分割的完整操作。2 1 2p e t r i 网的形式化定义定义2 1 ：p e t r i 网( p 舯( 或者简称网)刚是一个三元组，即刚= ( 只t ，f ) ，其中：1 )p = 0 。，p ：，p 。) 为有限的库所集，刀= i 叫为库所个数：2 ) t = o 。，f 2 ，t 。) 为有限的变迁集，m = i 卅为变迁个数；3 ) p l qt = g ，即库所集合p 和变迁集合丁不相交；put 囝，即库所集合p 和变迁集合丁不同时为空；4 )f ( e x r ) up j p ) 为流关系，也即弧集合；5 ) a o m ( e ) uc o d ( f ) = p ur，即没有孤立元素。其中d o m ( f ) = x i 砂：( x ，y ) f ) ，c o a ( r ) = 抄i s x ：( j ，y ) ，) 分别为f 的定义域和值域；6 ) 集合x = p ut 是网元素的集合。定义2 2 ：前置集( p r e s e t ) 、后置集( p o s t s e t )令p n = ( p ，t ，f ) 是一个网，x = p u t 为其元素集合，且x x ，那么x 的前置集，g ) 、后置集o ( x ) 分别为，g ) = i ，工) ，) ，d g ) = dl0 ，y ) f ) 。如果墨ex ，则i ( x t ) = u ，( 工) ，d ( x i ) = uo ( x )定义2 3 - t 函e 数( c a p a c i t yf u x n e c x u 。o n ) 、标识( m a r k i n g ) 、权函数记n o = o ，1 ，2 ， ，n = 1 ，2 ，3 ， ，并以c o 表示无穷：国= 彩+ 1 = c o 1 = 国+ 国，以上定义均对p n = ( p ，t ，f ) 而言。( 1 ) k ：p _ n u 斟称为库所容量函数，容量表示每个库所存储资源的最大数量，但它不是当前的实际资源数；( 2 ) 对于给定的容量函数k ，m ：p - - n o 称为户的一个标识的条件是：砌p ：m ( p ) k ( p ) ，它表示该库所的状态，所有库所的状态综合起来反映了系统的状态；( 3 ) w ：f n 称为p 上的权函数，定义2 4 ：关联矩阵c 、s 不变量、令p a r = ( p ，t ，f ) 是一个网，令：p o s t = c + 【，f 】- 形g ，p f )p r e = c 一】= ( a ，t j )c = p o s t p r ei = 1 ，2 ，n ；n = l d ；，= 1 , 2 ，m ；m = l 纠。它用来表示资源消耗量或生产量。弘不变量c 脚称为刖的关联矩阵，其矩阵元素：7c 忉f ，t j = 矿【f ，p fj 一矿p ，t j一个n 元整数列向量x 称为p n 的一个s 不变量的充分必要条件：c x x = 0 ；一个摊元整数列向量y 称为删的一个t 不变量的充分必要条件：c rx y = 0 。定义2 5 ：p e t r i 网系统( )六元组= ( p ，t ，f ，k ，w ，眠) 构成网系统的条件是：1 )p = ( p ，t ，尸) 构成有向网，称为的基网。2 ) x ，矽，m 。分别为p 上的容量函数、权函数和初始标识( i n i t i a lm a r k i n g ) 。p e t r i 网可用一个有向二元图表示，其中含有两类节点，并用有向弧连接起来。这两类节点分别是网的库所和变迁，弧是库所和变迁组成的有序偶。p e t r i网的标准图形表示是用圆圈0 代表库所，用矩形口来表示变迁( 若变迁是瞬时的，则用i 表示) ，用黑点来表示库所中含有的托肯，从节点x 至l j y 的箭头( 有向弧) 表示有序偶( z ，y ) ( ( x ，y ) f ) 。对于弧厂f ，w ( f ) 1 时，将w ( f ) 标注在弧上。根据k 函数的取值可将p e t r i 网分为无界网和有界网。对于无界网，当一个库所的容量有限时，通常将k ( p ) 写在库所的圆圈旁边；当k ( p ) = 一时，通常省略k ( p ) 的标注。有界p e t r i 网系统的k 函数为k ：p 寸n ，当k ( p ) = 1 时，省略k ( p ) 的标注。库所p ，中托肯的数量膨0 ，) 用黑点的个数来表示。标识膨是托肯在库所中的一种分布，用一个行向量m = 瞰幻。) ，m 0 ：) ，m 。) 】来表示。2 1 3p e t r i 网变迁的发射规则定义2 6 ：变迁的使能和触发( e n a b l i n ga n df i r i n g )= ( p ，t ，f ，k ，w ，m o ) 是一个p e t r i 网系统。1 ) 一个变迁t t 在标识肘下是使能的当且仅当：v p p ，w ( p ，f ) m ( p ) k 0 ) w ( t ，p ) 。2 1 变迁t t 在标识m 下是使能的，在t i c , 发后产生一个新的后继标志m 7 ，可由下列方程给出：v pep ：m 7 ( p ) = m ( p ) 一w ( p ，f ) + 矽( f ，p ) = m ( p ) + c ，t ) ，实际上t 的触发仅对其前置集z ( x ) 、后置集o ( x ) 中的托肯数量有影响。也可用如下式表示：m 侈) =m ( p ) 一形0 ，f )m ( p ) + 形( f ，p )m 0 ) 一w b , ，f ) + 矽o ，p )m 0 )p ，( f ) ，p 芒o ( t )p d ( ) ，p 名i ( t )p ei ( t ) f ) o ( t )o t h e r w i s e3 ) 系统标识m 经过f 的触发得到新的标识m 7 ，可以表示成m t ) m 。定义2 7 ：触发序列= ( p , t ，f ，k ，w ，m o ) 是一个p e t r i 网系统。盯= m o t l m l t 2 t m 。是的一个有限触发序列当且仅当：v i ：i f 甩：m hk ) m 引叫= ，z 是仃的长度。f t 2 t n 为变迁触发序列。p lt tp 2t 2融m 2 - 1 给出的是p e t r i 网= ( p ，t ，f ，k ，w ，m 。) 的图形表示。其中：p = p 1 p 2 。p 3 。p 4 p s p 6 p 7 1t = t l ，t 2 ，t df 2 ( p 1 t o ( t 1 p 2 ) 。( t h p 4 ) ( p 2 。t 2 ) 。( t 2 p 3 ) ( p 4 t 3 ) ( p 6 t 3 ) ( t 3 p s ) ( t 3 。p 7 ) ( p 5 。t 2 ) i t 0 = pl l l t 2 、= p 2 i t 3 ) = p 4 p do a o = p 2 , p 4 夕o ( t 2 ) = p 3 o ( t 3 ) = p5 p z w ( p t 。t 1 ) = 1 w ( t l ，p 2 ) = 1 w ( p 4 t 3 ) = 2 t f ，110l000 、l 三：二。三二：j2 2p e t r i 网主要性质本节将介绍p e t r i 网的几个重要性质：可达性( r e a c h a b i l i t y ) 、活性( l i v e n e s s )和死锁( d e a d l o c k ) 、冲突( c o n f l i c t ) 、有界性( b o u n d n e s s ) 和安全性( s a f e n e s s ) 。( 1 ) 可达性l z 纠：任意给定一个标识判定它是否从初始标识出发可达的问题就是可达性问题，它是p e t r i 网中一个基本的问题，p e t r i 网的其他性质都是基于可达性讨论的。定义：设= ( p ，t ，f ，m ) 为一个p e t r i 网。如果存在t t ，使m t ) m ，则称m 为从m 直接可达。如果存在变迁序列，如和标识序列9m 。，m ：。m 。使得m t 1 ) m 。 f ：) m 2 坂一。 心则称以为从肘可达的。( 2 ) 活性与死锁：如果不论标识如何演化，一个变迁总有被激发的可能，则称该变迁是活的。如果不论标识如何演化，网内都不存在不可激发的变迁，则称该p e t r i 网是活的。一个死锁是一个标识。从该标识不再有任何变迁使能。活性和死锁的性质，是一种非结构的性质，依赖于网的初始。死锁问题是离散事件动态系统监控理论的一个重要问题，一个死锁的系统也就失去了研究的意义 2 6 1 。( 3 ) 冲突：冲突反映了系统资源的竞争状况【2 7 】，一个结构冲突指一个至少有两个变迁的变迁集合，集合中的变迁具有公共的输入库所尸。一个有效冲突指存在一个结构冲突和一个标识，在该标识下，处于结构冲突中的变迁的共同输入库所p 的托肯数少于被该标识使能的p 的输出变迁的加权数。( 4 ) 有界性与安全性【2 8 】：有界性反映的是一个库所在p e t r i 网运行过程中所能获得的最大托肯数，它与p e t r i 网的初始标识有关。一个库所p 对一个初始标识而言是有界的，如果存在一个自然数k ，使得从眠出发的所有可达标识中，尸的托肯数不大于k ，称尸为k 一有界。一个p e t r i 网，若所有的库所对螈是有界的，则该p e t r i 网对初始标识螈而言是有界的。若p e t r i 网中，所有的库所是k 一有界，贝j j p e t r i 网是后一有界的。如果正整数k = 1 ，则称该p e t r i 网是安全的。2 3p e t r i 网分析方法对于一些简单的网系统，通过运行( 或者说仿真) 可以观察出它的一些性质。但对于较复杂的系统，用观察运行的方法来确定其性质难免会挂一漏万。网论为p e t r i 网提出了一些分析方法，如可达标识图与可覆盖树，关联矩阵与状态方程，p e t r i 网语言与分析化简规则等。这些方法各自有其优点和不足之处，本节介绍常见的可达标识图与可覆盖树，关联矩阵与状态方程两种方法。2 3 1 可达标识图与可覆盖树对于有界p e t r i 网，由于其可达标识集r ( m 。) 是一个有限集，因此可以以r ( m 。) 作为定点集，以标识之间的直接可达关系为弧集，构成一个有向图。这种有向图称为p e t r i 网的可达标识图。通过一个p e t r i 网的可达标识图可以分析这个网系统的状态变化和变迁发生序列的情况，从而得知网系统的有关性质。定义2 8 可达标识图设= ( s ，t ，f ，眠) 为一个有界p e t r i 网。的可达标识图定义为一个三元组r g ( z ) = ( 尺( 眠) ，e ，p ) ，其中e = ( m f ，m ，) im i ，m ，r ( m o ) ，3 气丁：m f 气 m ，尸：e r ，尸( m f ，m f ) = t k 当且仅当m ， m ，称r ( m 。) 为r g ( e ) 的顶点集，e 为r g ( z ) 的弧集；若尸( m ，m ，) = 气，则称t l o为弧( m ，m ，) 的旁标。例如图2 2 所示有界p e t r i 网，按照定义2 8 算法，可以得出其可达标识图2 3 。当不是有界p e t r i 网时，由于尺( 眠) 是一个无限集，不可能画出的可达图。为了用有限形式表达一个有无限状态的系统运行情况，需要引入一个表示无界量的符号0 9 。c o 具有这样的性质：1 ) 对于任意正整数歼：c o n ，t o + n = 缈2 ) 国