推荐新闻

当前位置:[首页] > 行业核心 >

行业核心

Petri网可达图的仿真理解

来源: http://redguia.com 发布时间:2021-09-22

  Petri网基础知识 错误!未定义书签。221 发展背景 错误!未定义书签。222 研究工具及其应用 错误!未定义书签。3 23 Petri 网的基本结构 错误!未定义书签。3 24 Petri 网的概念定义 错误!未定义书签。4 241 网和网的图形表示 错误!未定义书签。4242 网系统的概念 错误!未定义书签。4243 网系统分类 错误!未定义书签。5244 可达标识集的定义 错误!未定义书签。5245 系统模型的行为特征 错误!未定义书签。6246 Petri 网模型的主要分析方法 Petri网可达性的判别 错误!未定义书签。731 状态方程判别法 错误!未定义书签。832 Petri 网可达图判别可达性 具体事例分析错误!未定义书签。11 41 事例数据验证 错误!未定义书签。12412 可达图仿真判别 错误!未定义书签。13413 状态方程判别 错误!未定义书签。1442 验证结果分析 错误!未定义书签。15参考文献 错误!未定义书签。16鲁东大学本科毕业设计 Petri网可达图的仿真分析 要:Petri网是目前用于描述离散事件动态系统的最广泛的模型之一。本文通过分析 Petri 网的基本定义,研究了 Petri 网可达性的判别方法。本文重点分析了状态方程法和可达 图判别法,采用这两种方法对Petri 网可达性进行理论研究。其中,可达图判别法是以状态方 程法为代数基础来判别可达性的。在仿真部分,本文以可达图为主要工具,完成可达性的算 法设计应用、程序设计,进一步分析了Petri 网可达性的判别准则。最后,给出可达图的有关 特性及仿真流程,同时用Matlab 软件进行仿真,结合具体实例检验程序算法的正确性。 关键词:Petri 网;可达图;状态方程 Analysis ReachabilityGraph Petrinets Wang Xiaoxiao Electrical Engineering Automation,School ElectricalEngineering Abstract: Petri nets discreteevent dynamic systems mostwidely used models paperanalyzes basicdefinition Petrinets discriminatedmethod Petrinets paperanalysis stateequation reachabilitygraph discriminant method twomethods Petrinets theoretically Between them, reachabilitygraph discriminant method views state equation basicAlgebra determinereachability simulationpart, paperuses reachabilitygraph mainmethod reachabilityalgorithm design, programming furtheranalysis discriminatedmethod Petrinets Finally, simulationprocess reachabilitygraph Matlabsoftware programalgorithm combined specificexamples Key words: Petri net; reachability graph; state equation 引言Petri 网起源于1962 年Carl Adam Petri(德国)的博士论文。网论从一开始就以 鲁东大学本科毕业设计 物理为基础,当时的理论计算机科学包括自动机模型和形式语言理论,其概念构架不适合描述物理系统,它缺少重要的并发概念 Petri网是一个状态变迁模型,可用来描述系统中各异步成分之间的关系,同时允 许同时发生多个状态变迁,也是一个并发模型。当时的计划是要用一种兼容物理和计 算机科学两者的语言和概念构架来形式化描述制约通信进程的所有“自然法则” 如今,Petri网模型在众多方面得以应用。两个成功的应用领域是性能评价和通信协议, 其他很有前景的应用领域包括分布式软件系统,分布式数据库系统,并发并行计算, 柔性制造系统,多处理机系统,逻辑推理,办公自动化系统,形式语言,神经元网络 和决策模型等 而且,许多系统都可以转化为Petri 网模型来分析研究,它能恰当地表达各种可 能发生的动作变迁之间的相互作用。但是模型本身是有局限性的,必须进一步对被模 拟的系统进行分析。由于实际系统的 Petri 网模型一般是结构有界和不变式覆盖的, 而且这些不变式中有托肯,因此,本文中的网如无特别说明都指有界不变式覆盖网 作为一种资源网模型,应用系统中许多被人们所关心的现实问题都可以通过对Petri 网相应的性质考查来得到。这些性质同 Petri 网所模拟的实际系统某些方面的性 质有密切的联系。例如活性、安全性、有界性、可达性、守恒性、覆盖性以及可逆性。 要研究这些性质必须借助一些工具来完成,例如可达树、可达图、矩阵状态方程等。 其中,可达性就是研究系统可能达到的状态和状态间的关系,状态和状态之间是 用变迁连接的。Petri 网系统最基本的行为性质是可达性,除了可达性,还有可逆性、 有界性、活性、可覆盖性、公平性等,这些行为特征的研究都可转化为可达性的研究。 可达性决定着系统是否具有活性,能否达到一个特定的状态,以保证整个系统的安全 性。本文则主要通过可达图来分析研究 Petri 网的可达性,用该模型可达性的判别方 法来设计算法程序。利用状态方程法作为可达图判别法的代数基础,通过研究状态方 程解的问题来判定系统的可达性,预测系统的死锁,来实现实例数据在仿真软件及其 编辑完善的程序里的仿真分析。 Petri网基础知识 21 发展背景 从1962 年Carl Adam Petri(德国)的博士论文发表以来,Petri 网就得到了广泛 的应用与发展。1970 至1975 年,MIT 的计算结构研究小组积极参与Petri 网的相关研 究,在1975 月在MIT举行第一次Petri 网和相关方法的研讨会。从1980 年召开 第一次Petri 网理论和应用的国际研讨会以来,每年一次的国际研讨会连续不断,Petri 网理论和应用的研究成果也不断涌现,到1987 年已有2074 篇重要的相关论文发表 随着研究的不断深入,Petri网理论也在不断地充实和完善,其抽象和描述能力也 不断的朝着横向纵向发展。它的纵向扩展表现为:从基本的条件事件CE网,位置 变迁PT网,发展到谓词变迁网和着色网等高级网。它的横向扩展表现为:从无参 数的网,发展到时间Petri 网和随机Petri 22研究工具及其应用 Petri 网模型就是一个基于图的数学形式化描述模型,用来分析离散的并发系统, 或者说 Petri 网模型用来描述非同步的因果和非因果行为,包括并行和不确定选择。 Petri 网理论研究的主要内容是系统模型的行为特征,包括:可逆性reversibility、有 界性boundedness、活性liveness、可达性reachability、可覆盖性cover、公平性 fairness等。Petri 网以研究模型的组织结构和动态行为为目标,着眼于系统中可能发 生的各种状态变化及变化之间的关系。Petri 网模型的主要分析方法依赖于对诸如关联 矩阵、可达树、状态方程、位置不变量、变迁不变量等的研究与分析 在Petri网研究与应用的发展历史中,它的应用范围已经远远超出了计算机科学 的领域,成为研究离散事件动态系统的一种有用工具。以协议工程形式化方法为例: 协议的验证是基于对Petri 网模型分析而进行的。概括地讲,协议工程形式化方法是 要为协议设计的整个阶段提供规范化的指导,这包括描述Specification、验证 Verification、实现Implementation和测试Testing等几个主要阶段,每一阶段都有相 应的方法和技术。通过位置变迁(PT)网模型就可以很好的描述并分析整个系统 23Petri 网的基本结构 用Petri 网描述的系统有一个共同的特征:系统的动态行为表现为资源物质资源 和信息资源的流动。如果笼统地说:符合自然规律的模型就可以实现,不符合自然 规律的模型就不能实现,不会有人反对。但是这种大实话对实践没有什么指导作用。 Petri 网模型所体现的基本观点是与自然规律相关的若干具体而又被许多系统模型忽 视的东西。正是这些东西构成了Petri 网的物理基础,产生了Petri 网理论。如果没有 称为通用网论的理论部分,Petri 网也就失去了存在的价值,因为 Petri 网无意在众多 的系统模型中增加一个平凡的一员 。下面先介绍一下Petri网的基本结构。 Petri 网的结构元素包括:库所place、变迁transition 、弧arc、托肯token。 库所是用来表示状态的元素,就像用于描述程序系统的程序设计语言的变量一样。变 迁是用来表示变化的元素,就像程序系统中的赋值语句。弧是用来连接状态元素和变 化元素的,指明了状态到变迁之间的关系和触发的程度。托肯是用来表示库所中的资 源的,当变迁触发时对应的库所中的托肯数就会发生变化,就像车间流水线上的工件。 Petri网模型中,托肯包含在库所中,它们在库所中的动态的变化表示系统的 不同状态。当一个库所描述一个条件时,它能包含或不包含一个托肯,当一个标记表 现在这个库所中,条件为真;否则为假。当一个库所定义一个状态时,在这个库所中 的托肯个数用于规定这个状态。例如:在计算机和通信系统中,标记可以用于表示处 理的信息单元、资源单元和顾客、用户等对象实体 一个Petri网模型的动态行为是由它的点火规则规定的,当使用等于1 的弧权时, 如果一个变迁的所有输入库所这些库所连接到这个变迁,弧的方向是从库所到变迁 至少包含一个托肯,那么这个变迁可能触发相关联的事件发生。对这种情况,这个 变迁称为可发生的。一个可触发的变迁导致从它所有的输入库所中清除一个托肯,在 它的每一个输出库所这些库所连接到这个变迁,弧的方向从标迁到库所中产生一个 鲁东大学本科毕业设计 托肯。当使用大于1的弧权时,在变迁的每一个输入库所中都要包含至少等于连接弧 权的托肯个数,它才可以发生;这个变迁的触发,将清除在该变迁的每一个输入库所 的相应的托肯个数,并在变迁的每一个输出位置产生相应的托肯个数。变迁的实施是 一个原子操作,清除输入库所的托肯和在输出库所产生托肯是一个不可分割的完整操 24Petri 网的概念定义 本节的目的是把上一节的概念形式化。 241 网和网的图形表示 定义 2-1: 三元组N=S, 称为有向网directednet的充分必要条件是: 为流关系flowrelation。库所集和变迁集是有向网的基本成分, 流关系是从它们构造出来的,所以在 之间用;隔开。库所和变迁是两类 不同的元素,所以S 表示网中至少有一个元素。每一个库所代表一种资源,资源的流动由流关系规定,所以变迁只能与库所有直接关系:F S),不参与任何变迁的资源表现为孤立的库所,不引起资源流动的变迁表现为孤立的T 元素,domF 242网系统的概念 有向网是系统的结构框架,就像高楼的地基,系统中流动的资源就活动在这个框 架上。从网到网系统的过程必需指明资源的初始分布,规定框架上的活动规则,即库 所的容量和变迁与资源之间的数量关系 。以下定义均对有向网N而言。 定义2-2: {}称为N的容量函数(capacity function) 称为N的一个标识(marking)的条件是: 称为N上的权函数,对x,y ,现在,我们开始以此说明为基础定义Petri网系统。由此可以看 出,Petri 网模型尊重资源有限的事实,所以代表资源分布的标识 只能为每个库所指定有限多个资源。库所的容量也是有限的,按定义允许有些库所的容量为,这只 鲁东大学本科毕业设计 定义2-3:六元组 构成Petri网系统的条件: 依次为N上的容量函数,权函数和初始标识initial marking。 以上的是 Petri 网系统从结构到资源的静态特征。下面给出变迁发生的条件和结 果,网系统的动态规律称为变迁规则 一个变迁tT在M下是可发生的sS: 在标识M下是可发生的,那么t可以发生并产生一个新的后继标 系统标识M经过t的触发得到新的标识M,可以表示成M[t M或者M Petri网按照发生规则,对使能的变迁执行触发,可以反映出被模拟系统动态特性 定义2-5:发生序列 M0是一个PT系统, 是的一个有限发生序列i, 是一个有限的PT系统,标识M是由M 可达的当且仅当存在一个变迁触发序列,使得M 243网系统分类 C.A.Petri1962 年使用的系统模型实际上是K 的网系统,70年代 AHolt 把这种系统称为Petri 网,于是Petri 网由此得名 这时每个S元只有“有token”和“无token”两种状态,可理解为只有“真”和 “不真” 两种状态的布尔变量。网论中把这种 元称为条件,与条件关联的变迁称为事件。这种由条件和事件构成的网系统称为EN 系统条件事件网。 这是传统上称为Petri网系统,又称为PT 3)K,W为任意函数这种系统通常称为PT 系统,本文将主要以PT 网基础研究系统的可达性。 244 可达标识集的定义 许多应用问题都关心系统可能的状态,可达标识集是解决这类问题的关键。可达 鲁东大学本科毕业设计 标识集是Petri 网任何可能发生序列所能进入的全部状态的集合。Petri 网可达性的分 析对于协议验证十分必要,因为用 Petri 网模拟协议的正确性的许多问题都可转化为 可达性问题。PT 系统的若干重要性质可以用可达标识集来定义 由以上定义可得:定理2-1: 定义2-8:可达树首先定义一记号:对于所有nN,n;n+ 系统。的可达树是由标识(标记值可能由 表示)为结点构成的树,其弧度由T 元素标注。可达树由下列递归算法构成 算法1:PT系统可达树构造 1)根结点r由M0 标注。 2)一个标注M 的结点 是可实施的或者在从r 的路上存在一个结点yx,但结点y也是由M标注的。 3)如果一个标注M的结点x 不是一个叶结点,那么对于所有tT 使得在M下可 实施的t 实施而产生一个新的结点y,且在从x 结点标注的标识M 可由 其他如果 一个PT系统有界,指的是它所有的元素都是有界的,很自然它的可达树也是有 M0)是一个有限的PT系统, 的可达图是由标识标记 值可能由表示为结点的图,其弧线由T 元素标注。可达图有下列算法构成 算法2:可达图构成1)两个可达树的结点是等价的当且仅当它们有相同的标注M。 2)可达图的结点是它的可达树结点的等价类。从结点Y 到结点Z 的弧线系统模型的行为特征 k,就说是有界PT 系统,或k_为界PT_系统。 Petri 网模型的有界性是指网中任何位置的标记数是有界的,无界的 Petri 网模型 表示相应的协议层上有无限多的标记数,这样的协议显然是很不公平的。k 安全系统,k是这种系统的界 若所有tT都是活的,就说系统Σ 是活的。Petri 网具有活性表明该协议是无死锁 的。有些系统的界有时不易或无法确定,但可以证明其存在性,这时也可以笼统的说 该系统是有界的。定义中的M为从 有发生权。T的活性要求它在任何可达标识M 均有潜在的发生权,即有限步即可获得的发生权 3)Petri网模型的可覆盖性:在一个PT 系统中,标识M称为可覆盖的,当且仅 当系统可达集中存在标识M′,使得对系统中任一位置P,M′P 4)Petri网模型的可逆性:在一个PT 系统中,若对于所有的M ,都有从M可达到M 246Petri 网模型的主要分析方法 定义2-10: 关联矩阵和不变量 的关联矩阵,当且仅当cij 叫作的一个 S-不变量当且仅当 的转置矩阵。3)一个m 元整数列向量y 叫作 的一个T-不变量当且仅当 假定m元非负整数行向量是的变迁实施计数向量,亦即的第i 元素表示变迁 由上述定义知,在关联矩阵中,1表示有向弧由库所指向变迁,也就是说这个 库所是变迁的输入库所,变迁的输入库所即在1 所在的行,则只要1 所在的行对应 的库所有托肯即可触发变迁 于是有下面定理:定理2-2: 一个n 维向量X 的一个S不变量当且仅当 定理2-3: 鲁东大学本科毕业设计 的初始标识)和一个变迁实施序列从M回到M,亦即,MM,的实施计数向量等于X Petri网可达性的判别 Petri 网可达性的判别方法众多,有覆盖树图、可达图、综合判定法、库所不变式 法、关键约束可达判定法、状态方程法等,本文用最为传统的状态方程法和直观的可 达图来判别系统模型的可达性。虽然状态方程法有一定的局限性,不能很好地解决变 迁发射序列和变迁发射向量之间多对一的关系,即使求解出变迁的发射向量,也并不 意味着两个标识之间就一定存在着变迁发射序列(因为某些发射向量对于网系统而言 实际是不可行的)。需要利用关联矩阵来验证变迁发射向量是否能够发生来筛除伪标 识,这里不讨论伪标识的问题,故本文所出现的变迁向量均是可实现的。本文可达图 简单、直观,但是当系统规模较大或可达集为无限集时就难以求解。但是这两种方法 逻辑简单、算法复杂度底、运算易于执行,并且结合可达图的仿线Petri 网可达图判别可达性 由定义2-9 知,如果一个标识出现在可达图中,它当然是可达的,如果一个标识 不能被可达图中的某个标识所覆盖,它肯定是不可达的。可达图能很好地判断活性问 题,反应在可达图中,只要该图存在叶子节点,那么这个 Petri 网就是不活的。这样 就产生了死锁。下面给出可达图的构造算法,由于复杂系统可能造成 Petri 网状态空 间的爆炸,所以本文只针对较小的子网进行分析。 给出几个可达图常用的定义: 定义3-1:死标识 一个标识M t,即在此标识下任何一个变迁都不能触发。 定义3-2:终止节点:在可达图中,对应的死标识的节点。 定义3-3:重复节点:在可达图中,该节点的标识与已有节点的标识重复或包含 在已有的标识集合。 下面给出可达图构造算法的基本思想 设当前标识为M,对于每一个在当前标识下使能的变迁 进行触发,对得到的标识M′进行如下的判断处理: M′大于(或小于)已有的可达图中的某个标识,则判断M′是否按照相应弧 上的权值递增(或递减),若是,则将 M′与已有标识抽象成一类标识,递增的相应 分量表示成‘权值*n’的形式; 鲁东大学本科毕业设计 若M′不同于任何已有的标识,则M′为一新的可达标识,绘制M到M′的弧即可。3算法直到没有任何一个变迁使能或没有任何一个使能变迁可产生新的可达标识 为止。 构造Petri 网的可达图算法 M′=Mk处理重复节点 node(M)node(Mk); else Mk)处理大于节点 bigger();flse smaller();else {create(M′);处理新增节点 nodeM eachM’piMkpi: (M′(pi)%wt,pi=0)aMkpi中不含n: M′pi=wt,pi*n; Mkpi= wt,pi*n; M′pi=Mkpi; node(M)=node(Mk); else{create(M′); node(M)= node(M′); 鲁东大学本科毕业设计10 smaller() eachM′pi M′pi=M′pi; b*if(Mkpi M′pi=Mkpi; create(M′′);node(M)= node(M′′); createnode(M′); node(M)=node(M′); 注:%表示取余操作32 状态方程判别法 定理 2-4: 给定 ,其中C为关联矩阵。如果MRM ,则存在的T_向量U,使得: 上式称为Petri网的状态方程。在给出Petri 可以快速对标识的可达性做出判定,即给定一个Petri网和标识M 、M,如果所求的变迁发射向量U的解是小于0 的,则可以判定标识M 对于 来说是可达的,因为某些变迁发射向量对于网系统来说是不可行的。除非变迁发射向量U 能够发生,所以 在本文中未经说明的变迁发射向量U 均能发生 小于0的,则说明M对于网系统来说是不可达的;否则,可达。 本文用Matlab 编写程序,完整的程序如下: C=[-1 -1-1 -1-1]; M1=M-M0;C1=[C;M1]; 鲁东大学本科毕业设计 11 [m,n]=sizeC; a=rankC1; b=rankC; fprintf‘方程有唯一解,U。’U=CM1 else fprintf‘方程有无穷多解,可达’ end else fprintf‘方程无解,不可达’ end 状态方程判别法的算法流程图31: 开始 给定参考输入 关联矩阵C,初始标识M0等的输入 状态方程有解否? 不可达 可达 是否唯一? 图31算法流程图 具体事例分析我们以两个 42所示和,分析这两个系统的可达 图并对该系统进行仿真分析。 鲁东大学本科毕业设计 12 T6 P3 P5 T5 P1 P2 T3 T2 T4 P4 T1 图41 系统P1 T1 P2 T2 T3 P4 P3 T4 T5 P5 P6 T6 图42 系统41 事例数据验证 这两个Petri 网均是有界的系统模型,其第一个例子和第二个例子的关联矩阵C1、 C2 如下所示。 鲁东大学本科毕业设计13 412可达图仿真判别 第一个系统的初始标识M 01 [1,0,0,0,0]时,按照可达图的绘制规则画出系统的可达图为图43 所示的图形,此时系统可达图没有叶子节点,且经过T 能到达M1 M0图43 系统’的可达图第二个系统的初始标识为M 02 [1,0,0,0,0,0]时,按照可达图的绘制规则画出系统的可达图为图44 所示的图形,此可达图也没有叶子节点,经过T1、T2、T3 到达M2 鲁东大学本科毕业设计14 T4T5 T6T1 T3 M0 图44 系统’’的可达图413 状态方程判别 将第一个系统的关联矩阵C1,初始标识M 01 [0,0,0,1,1],输入程序,运行的结果如下图45所示。由运行结果知,可达图 判别的结果和状态方程的判别结果相同。当初始状态为M 01 [0,0,1,0,0]时,运行结果如图46所示。 图45 程序结果图 图46 程序结果图 将第二个系统的关联矩阵C2,初始标识M 02 [1,0,0,0,0,0],目的标识M2 [0,0,0,1,1,0],输入程序,运行的结果如下图47所示。由运行结果知, 可达图判别的结果和状态方程的判别结果相同。当初始状态为M 02 鲁东大学本科毕业设计15

· 友情链接

网站地图 XML地图 txt地图 TAG标签

电话:86-0773-60406884 邮箱:673427525@KHISI.net

地址:云南省宣威市祁连路大寺沟桥西2号  技术支持:大阳城集团网站(http://redguia.com)

redguia.com 大阳城集团网站