自动化学报
ACTA AUTOMATICA SINICA
1999年　第25卷　第5期　Vol.25 No.5 1999



一类PETRI网的时间性能简化分析1)
徐志斌　郑大钟
摘　要　实际系统的Petri网模型中加入时间因素形成TPN，在评价系统性能时，TPN的周期性具有重要意义.为降低系统的性能分析和计算的复杂性，基于分解的方法，结合结构简化分析，探讨具有同步连接时各分解子网与总网之间时间性能的关系，并给出一些典型结构的简化算法.
关键词　TPN，基本子网，周期时间，同步连接.
REDUCTION METHOD FOR TIME ANALYSIS OF A CLASS
OF PETRI NETS
XU Zhibin　ZHENG Dazhong
(Automation Department,Tsinghua University,Beijing　100084)
Abstract　In the physical system,it is necessary to add time factor into model,and cycle time is important in the performance analysis.In order to decrease complexity of analysis and computation,we propose a decomposing method with structure reduction.When there are synchronized links between subnets,the cycle time compute algorithm and reduction method of special structure are given in detail in this paper.
Key words　TPN, elementary net, cycle time, synchronized link.
1　引　言
　　由于实际系统的规模庞大，直接进行系统周期性的计算将导致计算维数灾难.文献［1］针对一类特殊C/E网，结合网的特殊结构分析和回路计算来求取系统的周期时间.文献［2］针对事件图，提出了一种逐步简化系统结构，求取系统的周期时间的方法.本文基于Petri网的分解，结合子网结构简化和子网间结构的连接分析来计算系统时间性能，并给出结构简化的方法和总网与子网间时间性能的关系.
2　基本概念
　　定义1. 一周期时间，周期时间是指网N从标识M开始，对无冲突结构的网，每一个变迁至少发生一次，最后又回到标识M所需要的最小时间；对有冲突结构的网，将其按冲突结构支路分解为无冲突结构的子网N1，…，Nk，其周期时间为各子网周期时间的最大值.
　　TPN的定义中引入时间因素的方法一般有三种：仅在变迁中加入时间；仅在位置中加入时间；同时在位置和变迁中加入时间.三种方法等效，本文取最后一种表达方法进行性能分析.为便于子网内部状态集结和结构简化时进行Token数目调整，文中设输入和输出函数取值为｛0，1｝.对于具有多重弧和自循环的Petri网，可以先采用PETRI网等价变换方法，变换为满足上述条件的子网，再利用本文所提的方法进行简化分析.
　　其余Petri网的相关定义，如节点的前集、后集、周期性、活性和有界性等参见文献［3］，TPN概念参见文献［5］.
3　结　果
　　首先讨论分解后子网的串行、F/J和并行等结构的简化，每种结构分为无托肯和有托肯两种情形讨论.结构定义参见文献［4］.
3.1　时间参数固定情形
3.1.1　简单串行结构
　　简单串行结构记为SB(P，T，I，O)，以位置到位置的结构简化为例，其简化结果如图1所示.


图1　简单串行结构的简化
　　由图1可知，位置到位置的串行结构简化成一个位置，简化后位置与原结构具有如下关系
　(1)
　(2)
对于起始节点为位置、终止节点为变迁和起始节点为变迁和终止节点为位置的串行结构可简化为一个位置p和一个变迁t,且
τ(p)=∑τp(pi),　τ(t)=∑τt(tj),　M(p)=∑M(pi).　(3)
对于起始和终止节点都是变迁的串行结构简化为一个变迁，有
　(4)
有托肯时要对与该结构相关的位置作调整.调整方法有两种，设结构起始变迁为t1，终止变迁为tn，所含托肯数为ML=∑M(pi)，则
　　1) 调整t1前集位置托肯数
　(5)
　　2) 调整tn后集位置托肯数
　(6)
　　定理1. Petri网N中的串行结构经过上述方法简化为N′，则N′保持网络N的有界性、活性、回复性和周期时间.
　　证. 证明过程略.
3.1.2　简单F/J结构
　　简单F/J结构记为F/JB(P，T，I，O)，其简化结果如图2所示.


图2　简单F/J结构的简化
由图2可知，基本组成的F/J结构简化成一个变迁，原结构支路的延迟时间和托肯数目为
　(7)
　(8)
　　结构中无托肯时，从周期时间的定义知有如下关系
　(9)
　　结构中有托肯时，要进行te1的前集位置或te2的后集位置的托肯调整，分三种情形考虑.具体处理参见文献［5］.
　　定理2. Petri网N中的F/J结构经过上述方法简化为N′，则N′保持网络N的有界性、活性、回复性和周期时间.
　　证. 由变迁发生规则易证.
3.1.3　简单并行结构
　　简单并行结构记为PB(P，T，I，O)，其简化结果见图3.


图3　简单并行结构的简化
由图3可知，并行结构简化成一个位置，结构支路满足
　(10)
　(11)
当结构中无托肯时，具有关系
　(12)
结构中有托肯时，则作如下处理
　　1) 将结构中各条支路按3.1.1节所述方法简化为相应的变迁ti,将pe2的托肯数调整；
　　2) 求出k，使得τt(tk)=MAX1≤i≤m(τ(ti));
　　3) 求出简化后位置p的延迟时间为τp(p)=τt(tk)+τp(pe1)+τp(pe2)，且M(p)=M(pe1)+M(pe2)+∑1≤k≤mML(k).
　　定理3. Petri网N中的并行结构经过上述方法简化为N′，则N′保持网络N的有界性、活性、回复性和周期时间.
　　证. 由变迁发生规则易证.
3.1.4　内环结构
　　内环结构记为IL(P，T，I，O)，其形式为：［te1］［U1≤k≤mSB(Pk,Tk,Ik,Ok)］［te2］［U1≤j≤mSB(Pj,Tj,Ij,Oj)］［te1］.首先分析简单内环结构，图4表示简单内环结构的简化结果.


图4　简单内环结构的简化


图5　不能简化的内环结构
　　设简单内环结构关联节点为te1,te2，两条基本路径位置为变迁为｛pk,0,pk,1,…,pk,nk｝，｛tk,1,tk,2,…,tk,nk-1｝，则其自身的延迟时间和内环结构所含托肯数及内环的循环时间为
TL=τt(te1)+τt(te2)+∑｛∑τp(pi,k)+∑τt(ti,k)｝，　(13)
ML=∑∑0≤k≤nkMp(pi,k),　(14)
πL=TL/ML.　(15)
对于te1,te2中至少有一个与其它结构的关联仅为输出弧或输入弧的情形，设te2仅有输出弧，则结构简化为变迁t，且
τt(t)=τt(te1)+τt(te2)+∑τp(p1,k)+∑τt(t1,k),　(16)
　(17)
　(18)
π(N)=max｛π(N′),πL｝.　(19)
te1,te2都有输入弧和输出弧与其它结构关联 的情形，可用反证法证明一般不能简化为一个变迁.具体证明参见文献［5］.
　　定理4. Petri网N中的内环结构经过上述方法简化为N′，则N′保持网络N的有界性、活性、回复性和周期时间.
　　证. 由变迁发生规则证明.
3.2　时间参数摄动情形
　　下面类似分析时间参数摄动时各基本结构的简化方法.设变迁延迟时间为区间量，记为：DT(t)∈［tmin,tmax］；同理，位置延迟时间记为：DT(p)∈［pmin,pmax］，则周期时间亦为摄动量，即π(N)∈［πmin(N),πmax(N)］.对上述结果进行如下修正即可：1) 位置的托肯数目分布采用时间参数固定时的求解方法；2) 简化后的变迁和位置及回路的延迟时间，其计算方法同参数固定时的计算，只是在求解区间上下界时分别用变迁和位置的延迟时间的最小值和最大值代入求解；3) 在简化并行结构和F/J结构时，条件的判断亦必须用变迁和位置的最大值最小值代入进行不同情形的判断.
3.3　基本子网的简化
　　复杂结构和基本子网的定义见文献［5］.基本子网由简单串行结构、并行结构和F/J结构递归组成，因此其简化分析方法可以采用分布分层简化方法实现，主要过程如下：1) 将原网N根据前述简化计算和分析方法将简单结构简化；2) 求出简化后网N′的时间指标和新状态，即简化后形成的变迁或位置的延迟时间和相关的位置的标识调整；3) 重复上述两步直至网N不可进一步简化为止；4) 设简化后网为N″，则由前述简化方法可知N″中无简单串行支路和简单并行支路，再根据回路计算网N″求出基本总网的周期时间π.
3.4　具有同步连接的总网性能简化分析
　　同步连接概念参见文献［4］，下面给出周期时间的计算关系.
　　定理5. 设子网N1,N2,…Nn通过同步连接形成的网N对应的有向图G中无回路，设子网Nk的周期时间为π(k)，则总网的周期时间π=max1≤k≤n｛π(k)｝.
　　证. 由周期时间的定义和回路计算方法易证.
　　定理6. 设子网N1,N2,…,Nn通过同步连接形成的网N对应的有向图G中有回路，设子网Nk的周期时间为π(k),则总网的周期时间π=max｛max1≤k≤n｛π(k)｝,max1≤k≤m｛πL(k1)、πL(k2)｝｝,其中m为针对不同连接的子网回路数，πL(k1)，πL(k2)为第k条回路的两个不同基本回路的周期时间.
　　证. 文献［5］中给出了本文结果的一个应用，限于篇幅，证明略.
4　结　论
　　本文针对大规模网的时间性能分析问题，采用基于内部网络状态集结和外部典型结构分解结合的方法进行分析，可以大大减小分析的计算复杂性.文中讨论了几种基本结构的简化方法，并对仅有同步连接的子网，给出了周期时间的计算方法.对于一般的网络结构，也可采用上述方法进行初步的简化，然后对简化后的网络进行计算，亦能减小计算复杂性.
1) 国家自然科学基金(69684001)和国家攀登计划资助项目.
作者简介：徐志斌　男，1970年生.1993年在清华大学自动化系本科毕业后直读本系控制理论及应用专业博士学位.研究方向为DEDS的分析和控制，Petri网的应用.
　　　　　郑大钟　男，1935年生.现为清华大学自动化系教授、博士生导师、《自动化学报》副主编.研究领域为线性系统理论，大系统分散控制，控制系统的鲁棒性，DEDS，混合动态系统等.
作者单位：清华大学自动化系　北京　100084
参考文献
1　Freedman P.Time,Petri nets,and Robotics.IEEE Trans.Robotics and Automation,1991,7(4),417－433
2　Zhou M C.Reduction of Timed Marked Graphs and Its Applications to Manufacturing Systems.IEEE Int.Conf.on Robotics and Automation, 1994
3　Reisig W.Petri Nets:an Introduction,Springer Verlag,1982
4　徐志斌，郑大钟.同步连接Petri网的性能保持分析.1996年CCC会议，青岛，1996
5　徐志斌.一类DEDS的性能和行为分析：Petri网方法［博士论文］.北京：清华大学，1997
收稿日期：1996-10-07
修稿日期：1998-05-15
