《petri网原理与应用综述》由会员分享，可在线阅读，更多相关《petri网原理与应用综述（7页珍藏版）》请在金锄头文库上搜索。
1、petripetri 网原理与应用综述网原理与应用综述摘 要：本文概述了 Petri 网的历史、发展、研究方法及应用领域，同时介绍了 Petri 网的基本原理，并给出了 1 个计算机网络链路层数据传输协议停等协议的 Petri 网模型。最后，概述了 Petri网研究和应用中出现的问题，展望了 Petri 网的发展方向。关键字：Petri 网；状态变迁模型；并发；停等协议中图法分类号：TP312Research Surveys of the Petri NetWU Qiang Department of Electronics and Information Engineering，Henan
2、Vocational College of Agriculture，Zhengzhou，Henan Province 451450，ChinaAbstract： The article summarizes the history， the development， the research methods， the application areas and the basic principle of Petri net， and gave a Petri net model of stop-and-wait protocol。 Meanwhile， according to the pr
3、oblem of Petri net research and application， the paper gave some ideas。Key words： Petri net; States transition model; Concurrency; Stop-and-wait protocol1。历史和发展Petri 网的概念最早是在 1962 年 Carl Adam Petri 的博士论文中提出来的，后来该模型就成为理论计算机科学包括自动机模型和形式语言理论的 1 个分支。网论从 1 开始就以物理为基础，当时的理论计算机科学包括自动机模型和形式语言理论，其概念构架不适合描述物理系
4、统，它缺少重要的并发概念。Petri 网是 1 个状态变迁模型，可用来描述系统中各异步成分之间的关系，而且允许同时发生多个状态变迁，Petri 网是 1 个并发模型。在分析并行系统的状态行为的技术中，Petri 网模型具有自然，直观，简单易懂等特点。它是 1 种形式化模型描述方法，在并行模型分析，协议的验证，自动控制等方面有广泛的应用。11970 至 1975 年，MIT 的计算结构研究小组积极参与 Petri 网的相关研究，在 1975 年 7 月在 MIT 举行了第 1 次 Petri 网和相关方法的研讨会。1980 年召开了第 1 次 Petri 网理论和应用的国际研讨会，从此以后每年
5、1 次的国际研讨会连续不断，Petri 网理论和应用的研究成果也不断涌现。随着研究的不断深入，Petri 网理论也在不断地充实和完善，其抽象和描述能力也不断的朝着纵横两个方向发展。它的纵向扩展表现为：从基本的条件/事件(C/E)网，位置变迁(P/T)网，发展到谓词/变迁网和着色网等高级网。它的横向扩展表现为：从无参数的网，发展到时间 Petri 网和随机 Petri 网。22。研究方法及应用Petri 网模型就是 1 个基于图的数学形式化描述模型，用来分析离散的并发系统，或者说 Petri 网模型用来描述非同步的因果和非因果行为，包括并行和不确定选择。Petri 网理论研究的主要内容是系统模型
6、的行为特征，包括：可逆性(reversibility)、有界性(boundedness)、活性(liveness)、可达性(reachability)、可覆盖性(cover)、公平性(fairness)等。Petri 网以研究模型的组织结构和动态行为为目标，着眼于系统中可能发生的各种状态变化及变化之间的关系。Petri 网模型的主要分析方法依赖于对诸如关联矩阵、可达树、状态方程、位置不变量、变迁不变量等的研究与分析。3在 Petri 网研究与应用的发展历史中，它的应用范围已经远远超出了计算机科学的领域，成为研究离散事件动态系统的 1 种有用工具。如今，Petri 网模型在众多方面得以应用。两个
7、成功的应用领域是性能评价和通信协议，其他很有前景的应用领域包括分布式软件系统，分布式数据库系统，并发并行计算，柔性制造系统，多处理机系统，逻辑推理，办公自动化系统，形式语言，神经元网络和决策模型等。以协议工程形式化方法为例：协议的验证是基于对 Petri网模型分析而进行的。概括地讲，协议工程形式化方法是要为协议设计的整个阶段提供规范化的指导，这包括描述(Specification)、验证(Verification)、实现(Implementation)和测试(Testing)等几个主要阶段，每 1 阶段都有相应的方法和技术。通过位置/变迁（P/T）网模型就可以很好的描述并分析整个系统。33。P
8、etri 网的直观理解用 Petri 网描述的系统有 1 个共同的特征：系统的动态行为表现为资源(物质资源和信息资源)的流动。在提供 Petri 网(PN)形式描 述之前，首先通过分布式系统的几个基本行为模型描述的例子对Petri 网作 1 个直观的说明。1 个 Petri 网的结构元素包括：库所(place)、变迁(transition)和弧(arc)。库所用于描述可能的系统局部状态，例如：计算机和通信系统的队列、缓冲、资源等。变迁用于描述修改系统状态的事件，例如：计算机和通信系统的信息处理、发送、资源的存取等。弧通过其指向来规定局部状态和事件之间的关系。在 Petri 网模型中，托肯包含在
9、库所中，它们在库所中的动态的变化表示系统的不同状态。如果 1 个库所描述 1 个条件，它可以包含或不包含托肯，也可以包含多个托肯。当库所中包含托肯时，条件为真；否则为假。如果 1 个库所定义 1 个状态，在这个库所中的托肯个数用于数量化这个状态。例如：在计算机和通信系统中，托肯可以用于表示处理的信息单元、资源单元和顾客、用户等对象实体。1 个 Petri 网模型的动态行为是由它的实施规则规定的，当使用等于 1 的弧权时，如果 1 个变迁的所有输入库所(这些库所连接到 这个变迁，弧的方向是从库所到变迁)至少包含 1 个托肯，那么这个变迁使能(相关联的事件发生)。1 个使能的变迁的触发导致从它所有
10、的输入库所中清除 1 个托肯，在它的每 1 个输出库所(这些位置连接到这个变迁，弧的方向从变迁到位置)中产生 1 个托肯。当使用大于 1 的弧权时，在变迁的每 1 个输入库所中都要包含至少等于连接弧权的托肯个数，它才使能；这个变迁的触发将清除在该变迁的每1 个输入库所中的相应的托肯个数，并在变迁的每 1 个输出库所产生相应的托肯个数。变迁的触发是 1 个原子操作，清除输入库所的托肯和在输出库所产生托肯是 1 个不可分割的完整操作。34。Petri 网的形式化描述4。1 五元组形式化定义要使五元组 PN=(P，T，F，W，M0)是 1 个 Petri 网，需要满足如下条件：N=(P，T，F)构成
11、有向网，称为 PN 的基网，P=p1，p2，pm是 1 个库所的有限集，T=t1，t2，tn是 1 个变迁的有限集，F (PT)(TP)是表示流关系的弧的集合，W：F1，2，3，是弧上的权函数，M0：P0，1，2，3，是初始标记。1 个没有给出详细初始标记的 Petri 网表示为 N，如果给出了初始标记则表示为(N，M0)。4。2 六元组形式化定义六元组 PN=(P，T，F，W，K，M0)定义与五元组定义的区别在于增加了库所容量函数。根据 K 函数的取值可将 Petri 网分为无界网和有界网，当有 K 取，六元组定义所描述的 Petri 网是无界网，当 1 个库所的容量有限时，通常将 K(p)
12、写在库所的圆圈旁边；当K(p)=时，通常省略 K(p)的标注。有界 Petri 网系统的 K 函数为K：PN+，当 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 旦触发，该变迁的所有输入
13、库所中都会被删除 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)=1V(s
14、) goto 3；Step8：如果超时，则 goto 4。接收结点：Step1：V(r)=0， 接收变量初始化，(接收变量：欲接收的数据帧发送序号)；Step2：等待；Step3：收到 1 帧，如果 N(s)=V(r)， 则下 1 步，否则丢弃该帧 goto 6；Step4：将收到的数据帧的数据部分送主机；Step5：V(r)=1V(r)；Step6：发送确认帧 ACK， goto 2。以下是停等协议的 Petri 网模型：图 1 停等协议的 Petri 网模型图其中：p1：发方 发 0 序号帧后的等待状态p2：发方 发 1 序号帧后的等待状态p3：0 序号帧在信道的状态p4：ACK 在信道的
15、状态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
16、 ， 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 网原
