Petri网发展综述

1、1. Petri网发展综述Petri网模型时CoAopetri博士于1962年提出来的，他的提出专门应用这样一类系统，即系统中国含有相互作用的并行分支。作为研究系统的一种工具，petri网理论用一个petri网作为以恶系统的模型一一系统的数学表示。从petri网的观点来看待一个系统，集中地表现为两个本原的概念，即事件和条件。事件是系统中大声地动作，条件即系统的状态。系统中的动作的发生是由系统的状态来决定的，协调的状态演变是由系统的事件来驱动的。而这些状态可以用一组条件来描述。条件满足动作即可发生，动作发生后达到下一状态，它可以揭示出被模拟的系统的结构和动态行为方面的重要信息。这些信息可以用来对

2、被模拟的系统进行估价并提出改进系统的建议。六十年代petri网的研究以孤立的网系统为对象，以分析技术和应用方法为目标，通过网论丛七十年代开始研究，主要内容为网系统的分类及各网类之间的关系，包括：并发论，同步论，网逻辑和网拓扑，八十年代petri网的研究在世界及中国有了较大的发展，近年来国内的主要研究集中在petri网的语义，公平性，活性，网运算，网化简，PN机理论等等。当今计算机技术的发展日新月异，计算机计算能力的发展促进了模拟技术的应用和发展，用一个数学模型，比如petri网来表示一个系统，然后，通过一定的算法让计算机对模型分析，就可以得到有关系统的性质。由于计算机计算的高速性和准确性，这就

3、使得对巨大，复杂人工难以胜任的系统的模拟成为可能。随着科学技术的发展出现了许多大规模的信息处理系统，如：并行程序，分布式操作系统，大规模的通信网络系统等等。由于petri网可以精确描述系统事件之间的顺序并发关系，所以它是分析并发系统的强有力的工具。Petri网的研究工作沿着两个方向发展。第一，纯petri网理论；第二，应用petri网理论。纯petri网理论是为发展应用petri网理论所需要的基本概念，技术和手段所做的研究。近年来petri网理论的研究取得了不少研究成果，如petri网的结构性质；petri网语言：随机网，颜色网；谓词变迁系统等等。有国内吴哲辉教授和美国的ToMurata教授共

4、同提出的petri网的公平性取得了十分完整的结果，对于解决网系统中两个变迁(变迁组)的发生的关系提出了理论依据。蒋昌俊教授建立了PN机理论构架，在交叠语义和偏序语义下获得反映真并发行为的文法及其PN机结构，揭示它们的计算能力及其相互关系。应用petri网理论主要从事用petri网模拟，分析和洞察系统的研究。这方面不单要求对petri网及其模拟技术有深厚的知识，而且必须对应用领域相当熟悉。结合当今技术的发展越来越多地应用到通讯系统，分布式系统，并行计算机系统及自然科学社会科学的很多方面。应用petri网理论的一个重要方面就是并发系统petri网分析工具的构造。Petri网被应用于分析和设计系统时

5、，如果系统规模较大则其对应模型必将十分复杂。人工分析显然是低效且不十分可靠的。因此，分析中若能有效地使用计算机则可十分迅速可靠的得到petri网的性质。2. Petri网Petri网是用于描述分布式系统的一种模型。它既能描述系统的结构，又能模拟系统的运行。描述系统结构的部分称为网。从形式上看，一个网就是一个没有孤立结点的有向二分图。定义1满足下列条件的三元组N=(S,T;F)称作一个网：1) ST(1.1)2) ST(1.2)3) F(ST)(TS)(1.3)4) dom(F)cod(F)ST(1.4)其中dom(F)xST|yST:(x,y)F(1.5)cod(F)xST|yST:(y,x)

6、F(1.6).(1.(2) 指出，S和T是两个不相交的集合(一般情况下可假定它们为有限集)，它们是网N的基本元素集。S的元素称为库所，T的元素集称为变迁，F是网N的流关系。用图形来表示一个网时，把一个S元画成一个小圆圈，一个T元画成一个小矩形。对x,yST,若(x,y)F,则从x到y画一条有向边。(1.3)式指出，有向边只存在于小圆圈和小矩形.之间，任意两个小圆圈或者小矩形之间都没有有向边连接。(1.4)式指出，一个网中不应有孤立结点。定义2设N=(S,T;F)为一个网。对于xST,记xy|yST(y,x)F(1.7).x.y|yST(x,y)F(1.8).称.x为x的前集或输入集，x.为x的

7、后集或输出集。称.xx.为元素x的外延。显然，一个库所的外延是变迁集T的一个子集，一个变迁的外延是库所集S的一个子集。对xST,x的外延xx.都不可能是空集(否则x就是一个孤立结点了)。2 .并发与冲突3 .Petri网的动态性质3.1 可达性、可逆性和可覆盖性可达性是petri网的最基本的动态性质，其余各种性质都要通过可达性来定义。.定义1设(S,T;F,M)为一个petri网。如果存在.t，使.MtM,则称M为从M直接可达的。如果存在变迁序列t1,t2,tk和标识序列M1,M2,Mk使得Mt1M1t2M2,Mk1tkMk(3.1)则称Mk为从M可达的。从M可达的一切标识的集合记为R(M)。

8、约定MR(M)。定义2设(S,T;F,M0)为一个petri网，MR(M0)。如果M,R(M),都有MR(M,),则称M为的一个可返回标识。定义3设(S,T;F,M0)为一个petri网。如果的初始标识M0是一个可返回标识，则称为可逆网系统。Petri网的可逆性反映系统的可回复性。易知，如果(S,T;F,M0)不是一个可逆网系统，但存在MR(M0)是一个可返回标识，那么把初始标识换为M,得到的，(S,T;F,M)便是一个可逆网系统。定义4设(S,T；F,Mo)为一个petri网，M为网N=(S,T;F)的一个标识，若M，R(M)使得MM，,则称M为的一个可覆盖标识。如果M1M2,则tT:M1t

9、M2t。可见，如果Mt>,而且M是的一个可覆盖标识，则中MRM),使得M,t。也就是说，中存在着一个变迁序列导致变迁t的发生。这就是研究petri网的可覆盖性的意义所在。3.2 有界性和安全性对于Petri网，不管是理论上还是应用上，有界性和安全性都具有基木的重要性。对给定初始标识即初始“托肯”分布Mo的一个Petri网(S,T;F,M0),称此Petri网为k有界的，如果对任意可达状态标识MR(M0)和任意位置节点s,相应于状态标识M卜的Petri网，位置节点s中的“托肯”数满足M(s)k,其中K为有限正整数。直观上，有界性意味着，Petri网(S,T;F,M0)在其所有可能的状态标识

10、即“托肯”分布下，网的各位置节点中的“托肯”数必为有界的。对于给定的初始标识即初始“托肯”分布M0的一个Petri网(S,T;F,M0),称此Petri网是安全的，如果对任一可达状态标识MR(M0)和任一位置节点s,相应于状态标识M下的Petri网，位置节点s中的“托肯”数满足M(s)1。实际上，对于Petri网(S,T;F,M0),安全性是一种最为苛刻的有界性，即属于“1一有界性”。3.3 活性在很多情况下，活性对于DEDS是一个所要求的理想性质。对于给定初始标识即初始“托肯”分布Mo的一个Petri网(S,T;F,M0),称其一个变迁节点t是活的，如果对由初始“托肯”分布M0可达的任一状态

11、标识MR(M0),都可找到一个发射序列，在由此导出的新“托肯”分布M，下可使此变迁节点t为使能。对于给定即初始“托肯”分布M0的一个Petri网(S,T;F,M0),称此Petri网是活的，如果其每一个变迁节点都是活的。3.4 死锁对于DEDS勺模型Petri网，死锁及其相关的特性阱都是需要力求避免的两个特性，这一点需要通过合理设计系统的结构来保证。对于给定初始标识即初始“托肯”分布M0的一个Petri网(S,T;F,M0),称其一个变迁节点t为死锁，如果对由如果对由初始“托肯”分布M0可达的任一“托肯”分布MR(M0)下，此变迁节点t都是不使能即不具有发射权的。从结构上看，一个死锁变迁节点t

12、具有这样的特点，即对其所连接的一组位置节点，位置的输入必定也为位置的输出，从而形成死锁。对一个Petri网(S,T；F,MO),如果其某个变迁节点的输入位置中包含死锁且未含“托肯”，那么其某个变迁节点将永远是非使能的即永远是不具有发射权的。对于给定初始标识即初始“托肯”分布M0,的一个Petri网(S,T;F,M0),称其一个位置节点是阱，如果此位置的输出必定同时也是其输入。对于阱的一组位置节点，如果位置中已经分布有“托肯”，那么在任何后续可达的状态标识即“托肯”分布下，这些位置节点中都必始终含有“托肯”。4分层颜色petri网当系统复杂到一定程度，利用普通Petri网模拟系统就会使之变得十分

13、复杂，系统分析往往会出现状态爆炸的问题。虽然在Petri网用于大系统的分析问题上已经有不少研究成果2,3,4,但是减少节点、简化模型仍然是建模的首要任务。进一步分析矿井馈电系统，可以得到它实际是由很多相互作用的子系统和子模块单元组成的系统，因此可以利用分层CPN对其进行建模。分层CPN通过引入复杂变迁从复杂的主Petri网中划分出很多子网对系统进行建模，它用复杂变迁替代可以从主CPN中分离的子网。分离出去的子网在原来的主CPN中留下的位置由一个等价的复杂变迁代替，简化了主CPN,并且使得模型具有层次化的特点56。4.1分层颜色petri网的定义分层CPNI入了CPN网和复杂变迁的概念，使整个P

14、etri网变得层次化和结构化。下面给出有关分层CPN的几个定义7,8：csocSi定义1没有输入弧的库所称为源库所记为P没有输出弧的库所称为阱库所记为P。定义2颜色Petri子网CPN的表达式为F?T,Ii,O),M,其中：PPsoPisiPn,其中：pjps|s1,2,.,m是CPNi内部库所的集合； Psopso|tktitk,psoi是CPNi源库所的集合； Pisipstktips,tkii是CPNi阱库所的集合；TiTk|k1,2,.,n是子网CPNi内部变迁的集合:Ci=Ci(p),Ci(t),其中，C(p)是与子网CPNi中每个库所有关的色彩集，C(t)是与子网CPNi中每个变迁

15、有关的色彩集；(4) Ij,Oj是CPNi的输入和输出函数；(5) m0是子网CPNi中的初始托肯集。定义3复杂变迁t是CPN网的等价替代物。复杂变迁d的输入输出库所分别相当于子网的源库所P：0和阱库所PS定义4分层CPN(HierarchyColouredPetriNet,HCPN)的表达式为(B,D,PT,I,O,M),其中B是一组有限CPN?网CPNi的集合，bPNi|i1,2,m；T是一组有限的复杂变迁di的集合，Tt“i1,2,m;PTT是一组有限的端口变迁集合；I,O是CPN的输入和输出函数；Mo是子网CPNi中的初始托肯集。5petri网研究离散事件动态系统的优缺点Petri网主

16、要的优点是能够处理并发、同步、异步、并行、非确定性等用一般方法难以解决的实际现象。它有简单的、定义良好的语法和语义，能够对一个系统的不同抽象层次进行描述。作为一个图形化的工具，与流图、方块图和网络等形象化的图形一样，petri网模型直观并且易于理解。作为一种基于实体的工具，相对成熟的数学基础，研究者能够根据状态和代数方程进行阐明，并且进一步描述其他数学模型管理系统行为。与传统的连续变量控制系统相比，离散事件系统不管是在运行机制和系统模型上，还是在分析方法和控制手段上，都有着明显和重要的区别。在离散事件系统中，对系统行为进程起决定作用的是一系列离散事件，而不是连续变量；系统所遵循的是复杂的人为规

17、则，而不是物理学定律。简单地说，离散事件系统是由离散事件驱动，并由离散事件按照一定运行规则相互作用，来导致状态演化的一类动态系统。系统的特点是：时间和空间上的离散性、异步性(即：事件驱动)、并发性和不确定性。离散事件控制系统(DECS除了具有DES的基本特征外，还具有自身的一些特点。DECS的输入输出均为多维变量，其对象状态空间是一个多维多状态空间。DECS的这些特点决定了对其进行建模和设计的复杂性，主要体现为“维数灾”问题和“建模难”问题。尽管petri网理论具有很多优点，作为一个模型语言，它仍然需要继续发展。Petri网在研究离散事件动态系统时，主要有以下两个方面的不足：“维数灾”问题：示例六层单部电梯控制系统的状态空间楼层电梯位置梯内请求楼层请求(上)楼层请求(下)6VVV5VVVV4VVVV3VVVV2VVVV71V7V7V7状态集Q=F*H*(I1*6)*(U1*U5)*(D2*D6)其中H=(up,rest,down)系统的状态数为：|Q|=6*3*26*25*25=1179648存在的问题二：“建模难”问题?现有的各类DES模型，其分