petri网原理与应用综述

摘要：本文概述了Petri网的历史、发展、研究方法及应用领域，同时介绍了Petri网的基本原理，并给出了1个计算机网络链路层数据传输协议——停等协议的Petri网模型。最后，概述了Petri网研究和应用中出现的问题，展望了Petri网的发展方向。关键字：Petri网；状态变迁模型；并发；停等协议中图法分类号：TP312ResearchSurveysofthePetriNetWUQiangDepartmentofElectronicsandInformationEngineering，HenanVocationalCollegeofAgriculture，Zhengzhou，HenanProvince451450，ChinaAbstract：Thearticlesummarizesthehistory，thedevelopment，theresearchmethods，theapplicationareasandthebasicprincipleofPetrinet，andgaveaPetrinetmodelofstop-and-waitprotocol。Meanwhile，accordingtotheproblemofPetrinetresearchandapplication，thepapergavesomeideas。Keywords：Petrinet;Statestransitionmodel;Concurrency;Stop-and-waitprotocol1。历史和发展Petri网的概念最早是在1962年CarlAdamPetri的博士论文中提出来的，后来该模型就成为理论计算机科学包括自动机模型和形式语言理论的1个分支。网论从1开始就以物理为基础，当时的理论计算机科学包括自动机模型和形式语言理论，其概念构架不适合描述物理系统，它缺少重要的并发概念。Petri网是1个状态变迁模型，可用来描述系统中各异步成分之间的关系，而且允许同时发生多个状态变迁，Petri网是1个并发模型。在分析并行系统的状态行为的技术中，Petri网模型具有自然，直观，简单易懂等特点。它是1种形式化模型描述方法，在并行模型分析，协议的验证，自动控制等方面有广泛的应用。[1]1970至1975年，MIT的计算结构研究小组积极参与Petri网的相关研究，在1975年7月在MIT举行了第1次Petri网和相关方法的研讨会。1980年召开了第1次Petri网理论和应用的国际研讨会，从此以后每年1次的国际研讨会连续不断，Petri网理论和应用的研究成果也不断涌现。随着研究的不断深入，Petri网理论也在不断地充实和完善，其抽象和描述能力也不断的朝着纵横两个方向发展。它的纵向扩展表现为：从基本的条件/事件(C/E)网，位置变迁(P/T)网，发展到谓词/变迁网和着色网等高级网。它的横向扩展表现为：从无参数的网，发展到时间Petri网和随机Petri网。[2]2。研究方法及应用Petri网模型就是1个基于图的数学形式化描述模型，用来分析离散的并发系统，或者说Petri网模型用来描述非同步的因果和非因果行为，包括并行和不确定选择。Petri网理论研究的主要内容是系统模型的行为特征，包括：可逆性(reversibility)、有界性(boundedness)、活性(liveness)、可达性(reachability)、可覆盖性(cover)、公平性(fairness)等。Petri网以研究模型的组织结构和动态行为为目标，着眼于系统中可能发生的各种状态变化及变化之间的关系。Petri网模型的主要分析方法依赖于对诸如关联矩阵、可达树、状态方程、位置不变量、变迁不变量等的研究与分析。[3]在Petri网研究与应用的发展历史中，它的应用范围已经远远超出了计算机科学的领域，成为研究离散事件动态系统的1种有用工具。如今，Petri网模型在众多方面得以应用。两个成功的应用领域是性能评价和通信协议，其他很有前景的应用领域包括分布式软件系统，分布式数据库系统，并发并行计算，柔性制造系统，多处理机系统，逻辑推理，办公自动化系统，形式语言，神经元网络和决策模型等。以协议工程形式化方法为例：协议的验证是基于对Petri网模型分析而进行的。概括地讲，协议工程形式化方法是要为协议设计的整个阶段提供规范化的指导，这包括描述(Specification)、验证(Verification)、实现(Implementation)和测试(Testing)等几个主要阶段，每1阶段都有相应的方法和技术。通过位置/变迁（P/T）网模型就可以很好的描述并分析整个系统。[3]3。Petri网的直观理解用Petri网描述的系统有1个共同的特征：系统的动态行为表现为资源(物质资源和信息资源)的流动。在提供Petri网(PN)形式描述之前，首先通过分布式系统的几个基本行为模型描述的例子对Petri网作1个直观的说明。1个Petri网的结构元素包括：库所(place)、变迁(transition)和弧(arc)。库所用于描述可能的系统局部状态，例如：计算机和通信系统的队列、缓冲、资源等。变迁用于描述修改系统状态的事件，例如：计算机和通信系统的信息处理、发送、资源的存取等。弧通过其指向来规定局部状态和事件之间的关系。在Petri网模型中，托肯包含在库所中，它们在库所中的动态的变化表示系统的不同状态。如果1个库所描述1个条件，它可以包含或不包含托肯，也可以包含多个托肯。当库所中包含托肯时，条件为真；否则为假。如果1个库所定义1个状态，在这个库所中的托肯个数用于数量化这个状态。例如：在计算机和通信系统中，托肯可以用于表示处理的信息单元、资源单元和顾客、用户等对象实体。1个Petri网模型的动态行为是由它的实施规则规定的，当使用等于1的弧权时，如果1个变迁的所有输入库所(这些库所连接到这个变迁，弧的方向是从库所到变迁)至少包含1个托肯，那么这个变迁使能(相关联的事件发生)。1个使能的变迁的触发导致从它所有的输入库所中清除1个托肯，在它的每1个输出库所(这些位置连接到这个变迁，弧的方向从变迁到位置)中产生1个托肯。当使用大于1的弧权时，在变迁的每1个输入库所中都要包含至少等于连接弧权的托肯个数，它才使能；这个变迁的触发将清除在该变迁的每1个输入库所中的相应的托肯个数，并在变迁的每1个输出库所产生相应的托肯个数。变迁的触发是1个原子操作，清除输入库所的托肯和在输出库所产生托肯是1个不可分割的完整操作。[3]4。Petri网的形式化描述4。1五元组形式化定义要使五元组PN=(P，T，F，W，M0)是1个Petri网，需要满足如下条件：N=(P，T，F)构成有向网，称为PN的基网，P={p1，p2，…，pm}是1个库所的有限集，T={t1，t2，…，tn}是1个变迁的有限集，F(P×T)∪(T×P)是表示流关系的弧的集合，W：F→{1，2，3，…}是弧上的权函数，M0：P→{0，1，2，3，…}是初始标记。1个没有给出详细初始标记的Petri网表示为N，如果给出了初始标记则表示为(N，M0)。4。2六元组形式化定义六元组PN=(P，T，F，W，K，M0)定义与五元组定义的区别在于增加了库所容量函数Ｋ。根据K函数的取值可将Petri网分为无界网和有界网，当有K取∞，六元组定义所描述的Petri网是无界网，当1个库所的容量有限时，通常将K(p)写在库所的圆圈旁边；当K(p)=∞时，通常省略K(p)的标注。有界Petri网系统的K函数为K：P→N+，当K(p)=1时，省略K(p)的标注。库所pi中托肯的数量M(pi)用黑点来表示。标识M是托肯在库所中的1种分布，用1个行向量：M=[M(p1)，M(p2)，…，M(pn)]来表示。4。3变迁规则4。3。11个变迁t要使能，它的输入库所p至少应该包含w(p，t)个托肯，其中w(p，t)是从库所p到变迁t的弧上的权函数。4。3。21个使能的变迁可能触发也可能不触发，这依赖于相关事件是否发生。4。3。31个使能的变迁1旦触发，该变迁的所有输入库所中都会被删除w(p，t)个托肯，相应地每个输出库所中将增加w(t，p)个托肯。5。停等协议的Petri网模型停等协议是1个比较简单的计算机网络链路层数据传输协议。由于每发送1个数据帧就停止等待，用0、1作数据帧的发送序号。发送结点：Step1：从主机取1个数据帧；Step2：V(s)=0，发送状态变量初始化；Step3：N(s)=V(s)，写入发送序号，将数据帧存入缓冲区；Step4：发送缓存区中的数据帧；Step5：设置超时定时器(适当的超时时间tout；Step6：等待；Step7：如果收到确认帧ACK，则从主机取出下1数据帧，V(s)=[1－V(s)]goto3；Step8：如果超时，则goto4。接收结点：Step1：V(r)=0，接收变量初始化，(接收变量：欲接收的数据帧发送序号)；Step2：等待；Step3：收到1帧，如果N(s)=V(r)，则下1步，否则丢弃该帧goto6；Step4：将收到的数据帧的数据部分送主机；Step5：V(r)=[1－V(r)]；Step6：发送确认帧ACK，goto2。以下是停等协议的Petri网模型：图1停等协议的Petri网模型图其中：p1：发方发0序号帧后的等待状态p2：发方发1序号帧后的等待状态p3：0序号帧在信道的状态p4：ACK在信道的状态p5：1序号帧在信道的状态p6：收方期望收1序号帧的等待状态p7：收方期望收0序号帧的等待状态t1：发方发0序号帧t2：发方发1序号帧t3：发方发0序号帧后超时处理t4：发方发1序号帧后超时处理t5：0序号帧在信道丢失处理t6：ACK在信道丢失处理t7：1序号帧在信道丢失处理t8：期望收1序号帧而收到0序号帧的处理t9：期望收0序号帧而收到1序号帧的处理t10：期望收0序号帧又收到0序号帧的处理t11：期望收1序号帧又收到1序号帧的处理对应的Petri网模型PN=(P，T，F，W，M0)，其中：P={p1，p2，p3，p4，p5，p6，p7}，T={t1，t2，t3，t4，t5，t6，t7，t8，t9，t10，t11}，F表示库所与变迁间弧，W表示弧上的权函数，该模型中所有弧上的权函数均为1，M0＝(P1，P3，P7)6。问题与展望Petri网易于表示系统变化发生的条件及变化发生后的系统状态，但不易表示系统中数据值的具体变化。在大型，复杂系统模型中，Petri网应用的主要困难是模型状态空间的复杂性问题，它将随实际系统规模的增大而呈指数性增长。因此，在Petri网的实际应用中，经常需要根据特定的应用环境对网模型加以修改和限制。对Petri网模型的化简技术的研究始终是Petri网研究的主题之1。目前，层次化模型技术和分块模拟逐步抽象综合技术是经常采用的方法之1；另1种方法是根据特定应用环境采用等效变换或保持某种性质的变换，以达到缩小状态空间，简化分析的目的。参考文献：[1]袁崇义，Petri网原理，电子工业出版社，1998年4月[2]林闯，随机Petri网和系统性能评价，清华大学出版社，2000年1月[3]T。Murata，PetriNets：Properties，AnalysisandApplications，ProceedingsoftheIEEE，Vol。77，No4，April，1989，pp。541-580。作者简介：吴强(1979－)，男，河南省郑州市中牟县人，助理讲师，软件设计师，本科，主要研究领域为专家系统