《Petri网原理与应用》读书笔记

1、Petri网原理与应用读书笔记1 传统 Petri 网介绍Carl Adam Petri 教授于 1962 年在博士论文用自动机理论通信中首次提出的一种自动机网状结构模型，拥有能恰当处理因果上的不存在依赖性的并行现象和表示不确定性的选择的能力，以及以系统模型用网状图形表示的方法。传统的 Petri 网是简单的过程模型，由两种节点：库所和变迁，有向弧，以及令牌等元素组成的。相关概念：（1）transition enabled（变迁的就绪）：当且仅当 transition 的每一个输入 place 都至少有一个 token 的时候，变迁就绪，可以实施。（2）transition firing（变迁

2、的实施）：变迁实施的时候它的每一个输入库所托肯减少一个，并使它的每一个输出库所的托肯增加一个。图1.1 显示了 Petri 网的基本建模，其中圆圈表示 place；矩形表示 transition；存在于 place 中用的 token 用黑点表示。用简单图形较好的表示并发、同步、因果等关系。以网图的方式简洁、直观的模拟离散事件系统。目前已得到广泛应用,有限状态机、通信协议、同步控制、生产系统、形式语言、多处理器系统等建模中。通讯协议的验证是Petri网应用最为成功的领域之一最初应用在70年代初期，由于 Petri网以形式语言作为基础，可形式化地对通信协议进行正确性验证。随着计算机网络技术和信息

3、技术的发展，对网络进行性能分析的需要，不仅出现于企业内部的生产控制的局域总线网，而且出现于光纤局域网或ATM网中。图1.1 Petri 网基本模型 由于产品开发中的竞争和革新需要，导致产品开发者面临巨大压力。在软件工程中Petri网主要用于软件系统的建模和分析，比较成熟的是加色Petri网，可以用于大型软件系统的设计、说明、仿真、确认和实现，在软件开发生命周期的各个阶段，Petri网都可以得到很好的应用。Petri网可用于Al中的知识表达和推理的形式化模型的建立，可以表达各个活动之间的各种关系，如顺序关系、与关系、或关系等，并可在模型基础上通过已知的初始状态和初始条件进行逻辑推理。柔性制造系统

4、(FMS)对于现代制造业具有重要作用，Petri网由于其自身优点，在制造系统中应用广泛，如带缓冲区的简单生产线、机床加工中心、自动生产线、柔性制造系统和及时加工系统。系统的可靠性不仅包括硬件的可靠性、也包括软件可靠性.利用随机Petri网对系统进行可靠性分析，对软件复用、软件可靠性分析。Petri 网描述系统的最基本概念是库所和变迁。库所表示系统的状态。变迁表示资源的消耗、使用及使系统状态产生的变化。变迁的发生受到系统状态的控制，即变迁发生的前置条件必须满足；变迁发生后，某些前置条件不再满足，而某些后置条件则得到满足。 库所中令牌分布决定变迁的使能（enabled）和激发（fire），变迁的激

5、发又将改变令牌的分布。以变迁激发导致令牌在库所间的流动，Petri网可以用于模拟系统的动态运行过程，反映系统的动态特性。网N=（P，T；F）构成了描述系统静态结构框架，但还不能描述系统静态结构的全貌。网论尊重资源有限的事实。实际上，变迁发生所需的资源是有 限的，库所容量也应是有限的。完整的网系统应指明资源的初始分布，规定变迁的活动原则，确定库所容量和变迁与资源数量之间的关系。2 扩展 Petri 网的研究2.1 扩展的 Petri 网在以 Petri 网为工具对特定的系统进行建模分析时，不仅要遵守严格的语义还要兼顾图形语言。用 Petri 网建立的模型可能十分的复杂，因为在一个动态的网络图中很

6、多活动都需要用一个库所、一个变迁以及连接它们的一条连接弧来表示。如果系统中处于动态过程的活动过多，利用 Petri 网对其建立模型会产生状态爆炸的现象。由于 Petri网在设计之初并没有引入层次化的建模理念，这导致了利用 Petri 网建立的工作流模型很难重复利用，难以进行有效维护，理解起来非常困难。区别于传统的面向问题的方法的面向对象方法，使得计算机能以更加类似人类的思维方式解决问题，从而直观地描述客观世界，并拥有封装性、继承性、支持软件的复用以及易于扩充等优点。在 Aalst提出的工作流网的基础上引入对象技术及细化变迁实现流程的分层建模，可以降低建模的复杂程度，提高模型的可读性和重用性。从

7、系统建模角度，将板材加工FMS中的活动分为三类： 以冲压和剪切为特征的冲剪操作； 冲剪后零件的折弯操作； 板料以及冲剪后零件的出入库操作。采用Petri网建模的基本步骤： 划分和定义系统内所有活动及其相互关系； 采用Petri网描述上述活动及其关系，得到系统Petri网模型。2.2 Petri网的行为特性与其它建模方法相比，Petri网的优点不仅表现在建模能力上，更主要表现在它所具有的分析能力上。Petri网具有一些专门的分析手段，对系统活性（liveness）及死锁（deadlock）进行分析，分析系统中的顺序、并发及冲突等复杂事件关系。采用可达树（reachability tree）理论分

8、析系统的有界性（boundness）与安全性（safety）等。Petri网的可达性是研究任何系统动态特性的基础,决定系统能否到达一个指定的状态。 (1)系统按照一定的流程运行，系统是否能够实现一定的状态；或者不期望的状态不出现。比如：生产调度计划的验证（按照一定的生产调度计划进行生产，一定的生产任务是否能够完成）（2）要求到达一定的状态，如何确定系统的运行轨迹（流程）。比如：生产调度，如何安排作业顺序？活性在系统中用于检测是否存在死锁。一个系统存在的一个潜在问题是死锁,为了避免死锁,系统的Petri网模型必须具有活性。（1）互斥：同时争夺唯一资源（2）占用且等待（3）无抢占（4）循环等待有界

9、性是一个非常重要的特性，它保证系统在运行过程中不会需要无限的资源。有界性反映一个库所在系统运行过程中能够获得的最大的令牌数，即所能获得的最大资源数，它与系统的初始令牌有关。在实际系统设计中，必须使网络中的每个库所在任何状态下的令牌数小于库所的容量，这样才能保证系统的正常运行。2.3 扩展 Petri 网的触发机制扩展的 Petri 网能够区别变迁的使能和变迁的实施两种不同状态。被使能的变迁如果要得以真正实施，必须满足一定的条件即具备相应的触发机制。使被使能的变迁真正实施的外部条件即为触发机制，它主要由以下 4 种类型：第一，自动触发：变迁被使能的同时触发，通常用于那些通过应用程序来自动执行、不

10、需要与人进行交互的自动型活动。第二，人工触发：活动的执行通过执行者从工作流任务管理器提供的工作流任务表中选择工作项来进行触发。当执行者选中某一工作项时，此工作项开始执行，被转换为活动。第三，消息触发：由系统外部的消息(事件)来触发，如 E-mail，EDI 消息的到来。第四，时间触发：由控制时间的定时器来触发。3 基于 Petri 网的工作流网研究作为一种良好的建模工具，如今 Petri 网已经被广泛地运用到很多方面。如数据分析、协议验证、工作流管理、工作流模式、并行程序设计、软件设计等。但是由于经典 Petri 网存在没有测试库所中零令牌的能力、模型容易变得很庞大、模型不能反映时间方面的内容

11、、不支持构造大规模模型如自顶向下或自底向上等局限性，在实际运用中需要对其进行改进。为了解决这些问题 Aalst 等人对经典 Petri 网进行了扩展和改进，定义了工作流网(Workflow net，WF-net)模型及其有效性准则，采用了任务对应变迁、状态对应库所的策略，孤立地定义了单个案例的动态行为。当用 WFN 对工作流模型进行描述时，库所用的圆圈表示条件，有两方面的作用：确保任务按正确的次序执行；用来表示案例的状态。而变迁节点用的矩形表示工作流任务。库所到变迁或变迁到库所间的弧表示任务和工作流的逻辑关联形式。库所中包含的黑点(托肯)表示工作流执行的状态。只有每个输入库所至少有一个托肯，变

12、迁才能够实施。工作流网模型中的任务包括顺序、并行、选择和循环四种路由结构。工作流执行的基本结构由这四种路由构成。这四种路由结构按照一定的方式组合可以合成工作流所有的执行结构。为方便四种路由结构的 Petri 网表示，引入与分叉、与合并、或分叉、或合并四种构造模块。与分叉和与合并的共同使用表示了一个并行执行过程，或分叉和或合并的共同使用表示了一个选择执行过程。4 Petri 网模型的化简规则化简技术也称归约技术或模型转换技术，它是以保证模型的基本特点为前提将过程模型化简到适当的程度，以方便对模型可能存在的各种冲突进行检测。对扩展 Petri 网内对象的化简，首先可以在验证合理性时将与工作流环境紧

13、密相关的触发机制和工作流路由去掉。对于触发机制只是简单地忽略掉就可以了，而对于工作流路由的处理要复杂一些，需要把 OR-split、OR-join、AND-split、AND-join 这样的工作流元组件还原成经典 Petri 网中普通的库所和变迁，这样新生成的模型中不再有专门的控制变迁。5 Petri 网模型的正确性分析工作流过程定义结束后，需要对其进行正确性验证，只有在证明了所建工作流模型无死锁、无死任务，是合理的、安全的之后，对其进行性能分析、仿真优化才有意义。工作流的正确性对业务过程目标的正确完成有着重要的影响。工作流模型的正确性包括两方面的含义：结构上的正确性(即工作流模型是安全的、

14、无死锁的)和语义上的正确性(即在完成业务目标上是与实际业务过程等价的)。对工作流模型的正确性分析主要指对工作流模型结构上的正确性进行分析。目前，在模型的正确性研究方面，主要有以下两种方法：可达图分析和化简。利用 Petri 网可达图分析技术分析结点较多的模型时，尤其是集成制造领域的模型，其过程会很复杂，验证所需的时间随节点个数呈指数增长会导致状态空间爆炸；而且可达图分析技术只能提供模型正确与否的结论，而无法具体地定位错误，不便辅助设计者修改模型。6 Petri 网的步语义问题Petri 网的步语义（step semantics）是一种有效的建模方法，它与顺序语义（sequence semant

15、ics）相比对实际行为的描述更为详尽，而与难以掌握的偏序技术相比更贴近实际，是顺序语义与偏序技术在实用性和表达能力上的折衷。Philippe Darondeau 等人针对步语义可能引起状态爆炸以及缺乏对行为协调有效支持两个缺点，引入了步触发策略，它限制了 Petri 网并发行为，因此改进了步语义的执行和建模特征。Matthias Jantzen 等人比较了各种变迁触发方式，定义了 Petri 网中通过步、最大步、多步和最大多步语义生成的语言；通过允许在一个多步中多次使用变迁，得到一个语言体系，弥补了带标记 Petri 网步语义所定义的语言在若干方面的缺失。7 Petri 网的合成Petri 网

16、的合成自 20 世纪 90 年代起逐渐成为本领域内一个研究热点，它探讨如何从系统的一个行为规范描述生成一个行为等价 Petri 网模型。 J. Carmona 等人提出了一个从变迁系统生成有界 Petri网的算法，这个算法基于一般域（general region）的理论将已有的 Petri 网合成算法由安全网扩展到有界网，根据这一扩展，合成算法的适用范围扩大到带有权弧的 k-阶 Petri 网。而且这个合成算法使用基于 BDD 的符合化表示方法来表达状态空间，从而有效地生成最小域，与安全网的合成方法相比，生成的网模型更简单直观。通过研究有步触发策略的 Petri 网合成方法，给出一个公理，说明

17、一个变迁系统在何种条件下能够由一个给定步进触发策略控制的 Petri 网的可达图来表示。 J.M.E.M. vander Werf 等人给出了一种基于域理论的流程发掘算法，由系统的执行日志生成 Petri 网模型。域理论起源于硬件设计控制领域，用于由行为说明构造 Petri 网。由于域理论直接应用于流程发掘会导致生成的网模型中库所个数依赖于日志规模，作者通过引入整数线性规划思想，由库所来限制网的可能触发序列，解决了这个问题。 在展示工具的论文中，也有一篇是关于 Petri 网合成的：Robin Bergenthum 等人展示了一个由场景合成 Petri 网的工具，它为基于 Petri 网的商业

18、流程工具 viptool 加入了 Petri 网合成的新特性，改写了流程建模的起点，由用户设计流程的合适场景，再根据 Petri 网合成工具生成流程模型。8 Petri 网的网展开网展开技术是一种 Petri 网的状态空间搜索方法，它通过构造网的展开图来进行各种离散事件系统的属性分析。 Robin Bergenthum 等人针对标准的基于分支进程的网展开技术包含较多冗余的缺点，提出了两种新的网展开语义，其中一个避免了同构进程的出现，另一个减少了在底层运行时同构的进程的个数。而且两种新的展开图模型仍然表达了完整的偏序行为。文中还给出两种新模型的构造算法，能够快速生成规模小得多的展开图模型。在上文

19、讨论模型检测时提到的论文5中，验证移动系统采用的方法就是基于网展开的模型检测技术。9 其他 Petri 网相关理论研究论文的研究对象是持续网（persistent Petri nets），它是比无冲突网（conflict-free nets）更一般的一类网模型，Eike Best 等人针对持续网早期理论引出的开放性问题进行了研究，使得构造理论更贴近于持续网。还给出了这样的结果：对于有界可逆的持续网，可达图中的环能够分解为更小的、不相交的环。这个结论缩小了网的线性代数性质与更多组合性质间的鸿沟。Kunihiko Hiraishi 基于连续 Petri 模型使用状态空间搜索方法分析了信息系统工作流

20、的性能。文中提出了一种新的连续 Petri 网路由时间连续 Petri 网 RTCPN，用于近似一般化随机 Petri 网 GSPN 的离散状态空间，并将这个新的网模型用于工作流数量性能的分析上，结果显示新模型不受工作流实例个数的限制，扩展性更强。Ryszard Janicki 等人提出了一种新的建模理论，使用商半群来进行并发的建模。10 模型检测研究Guy Edward Gallasch 等人讨论了参数化系统的模型检测问题。文章以 SWP （Stop-and-Wait）这类协议为对象，研究了带有两个无界参数的 SWP 模型检测问题。以 SWP 的着色 Petri 网 CPN 模型为基础，构造

21、了含有两个参数的代数公式来符号化地表示相应的可达图的无穷族类，然后从代数表达式生成一个参数化的有限状态自动机（FSA）来表达所有用户可观察的事件序列，再将其化简得到一个简单无参数的 FSA，最后通过比较 FSA 与表达用户期待行为的服务语言的相等性来验证 SWP 是否满足预期性质。Alexandre Hamez 等人研究了决策图的模型检测问题。状态空间的共享决策图能够缓解大规模系统的状态空间爆炸问题，但是变量的顺序以及变迁关系定义和应用方式会很大程度上影响性能。文中提出了一种分层决策图优化技术SDD（Hierarchical Set Decision Diagrams)，这个数据结构提供了一种

22、有效的编码结构化规范方法，能够应付大型系统的复杂度。SDD 的能力还包括：根据少量的用户输入来优化变迁关系的赋值，由此自动生成 Saturation（一种能有效解决决策图技术中问题的方法）；允许用户自由定义变迁关系。Kais Klai 等人设计了一个基于状态符号化观察图（symbolic observation graph，SOG）的 On-the-fly 模型检测器 MC-SOG，用于验证有穷模型上基于状态的 LTLX 性质。On-the-fly 允许只生成与验证属性相关的部分模型，符号化模型检测则是在一个使用二元决策图（Binary Decision Diagram, BDD）技术系统的紧

23、凑表示上验证属性，文中的方法结合了这两种技术，在检测过程中生成系统状态空间的抽象 SOG，其生成过程由待验证的属性指导，然后通过判断 SOG 对 LTLX 公式的满足性来验证系统。这个检测器已被实现在由 Petri 网建模的系统上。Morgan Magnin 等人研究了一种带秒表的有界 Petri 网 SwPNs（bounded Petri nets with stopwatches），提出一个符号化的方法，采用通常用于稠密时间的技术来计算带秒表的离散时间 Petri 网 SwPNs 的状态空间，用于验证系统的定时属性，并给出这个模型的 TCTL 模型检测算法。文中还证明了在特定情况下，通过简

24、单地离散化相关的稠密时间网的状态空间能够计算出一个离散时间网的状态空间。Roland Meyer 等人将基于网展开的安全 Petri 网模型检测技术应用于移动系统的验证。首先，由 Pi 演算的一个著名子集 FCP（finite control process）建模移动系统，然后将 FCP 转化为一个安全进程（safe process），进而转化为安全网，再进行基于网展开的模型检测。实验结果显示在内存消耗和运行时间方面，此方法有明显优势。11 Petri 网应用Roland Bouroulet 等人介绍了一个构架，用于描述和验证全协议的属性。此框架使得在分析协议时必须的隐式信息变成显式、结构化和

25、形式化的信息。首先将协议代理形式化为角色，然后将角色和可能与角色交互的环境都用 SPL（Security Protocol Language）进程表示，再将其转化为高阶 Petri 网，初始标识由协议中的上下文生成。这样，Petri网的仿真与模型检测技术就能用于协议属性的分析和验证。 Lay G. Ding 等人利用 CPN 建模和分析了一个面向事务的用于在 Internet 上初始化、修改和终止多媒体会话的控制协议 SIP（Session Initiation Protocol）。文章主要分析和验证了在一个可靠传输介质上进行的INVIFE事务，为INVITE创建了一个 CPN 模型，通过 C

26、PN 的状态空间分析方法验证了 INVIEF 的常规属性，发现了一个非预期的行为，并据此对它进行了一些改动。 Kristian L. Espensen 等人应用 CPN 模型和分析工具建模和验证了一个路由协议 DYMO（Dynamic MANET On-demand）。MANET 是一个由一组移动通信设备通过无线通信建立起来的移动即时网络，而 DYMO 是 MANET 中的一个用于多跳数通信的路由协议。文中给出了 DYMO 协议的CPN 模型，并使用状态空间搜索验证协议的重要属性，对正在开发中的协议版本产生了直接影响。 Paul Fleischer 等人应用 CPN 建模和验证了一个通信协议。

27、通用访问网体系 GAN 中要用到 IPSec 协议和 Internet 核心交换协议 IKEv2 来提供访问 IP 网络的加密技术，而 GAN 规范中只粗略地描述了两种协议的使用方法，所以文中根据一个描述IPSec和IKEv2如何在连接建立过程中被使用的详细 GAN 场景，构造了一个 CPN 模型来形式化地说明和验证这个场景。 Hendrik Oberheid 等人实现了一个CPN模型来模拟空中交通控制中的潜在到达计划进程。文中首次提出一个形式化建模协调到达管理进程的方法，利用 CPN 模型提供了一种直观的方法来建模和分析顺序计划问题的综合特性，目的是研究计划编制系统的不同动态属性，并由此来优

28、化系统性能，改进系统安全。 Filippo Bonchi 等人说明了如何通过 Petri 网的行为等价性来判断服务描述的正确性与可替代性问题。具体地，文中定义了用于表示 OWL-S 描述的 Web 服务的网模型 OCPR（Open Consume-Produce-Read）网，在此基础上定义了一个适用于 OWL-S 的行为等价性概念，这样就能够回答一个服务描述是否等价于服务实现，以及一个子服务能否在不改变整个应用行为的前提下被另一个子服务替换的问题。 第一，Petri 网因其图形化与描述异步并发的能力，非常适用于通信协议的建模，而 Petri 网的多种分析方法与工具也给协议的分析和验证提供了便

29、利；第二，着色 Petri 网 CPN 作为一种高级网模型，它的状态空间分析方法和支持工具已经被广泛应用于验证通信协议、军用系统、商业流程、Web 服务应用和其他各种软件系统。12 Petri 网工具Lawrence Cabac 等人针对面向代理的软件工程AOSE工具缺少系统的全局状态监测及动态操作环境的问题，提出了两个结合 AOSE 范式与 Petri 网表达能力的 PAOSE 工具MULAN-Viewer 和 MULAN-Sniffer，用于处理在调试、监测及测试代理应用时遇到的问题。Joao Lourenco 等人提出了一个生成监测特定进程的图形化用户接口的自动化设计工具。当前对于离散事

30、件建模，特别是 Petri 网，很难找到完全支持代码生成和动画式交互的图形用户接口及 SCADA（监督、控制、数据获取系统）工具，作者针对这个问题实现了一个自动化工具，它能够自动生成一个中心化的 SCADA 系统，实现了以 Petri 网为行为模型、基于本地图形化用户接口的进程控制器执行监督和控制的机制。 Fausto Sessego 等人实现了一个开源工具 HYPENS，用于仿真离散时间、连续时间以及混合 Petri 网，它在 Matlab中开发，允许用户和设计者利用已经在 Matlab 中事先定义的功能和结构。13 Petri网会议第 29 届 Petri 网应用与理论及其他并发模型国际会议（29th International Conference on Applications and Theory of Petri Nets and Other Models of Concurrency, 简称 PETRI NETS 2008）于 2008 年 6 月 23 至 27 日在西安召开。该会是国际 Petri 网研究领域最高水平和最富影响力的学术会议，起始于 1980 年，当时称为欧洲 Pet