一种随机Petri网性能等价化简与分析方法  

An Approach to Performance Equivalent Simplification and Analysis of Stochastic Petri Nets

作　　者：林闯[1] 曲扬[1] 郑波[1] 田立勤[1] 

机构地区：[1]清华大学计算机科学与技术系,北京100084

出　　处：《电子学报》2002年第11期1620-1623,共4页Acta Electronica Sinica

基　　金：国家自然科学基金项目 (No 60 1 730 1 2 ;90 1 0 4 0 0 2 ) ;国家重点基础研究发展规划 (973计划 )项目 (G1 9990 32 70 7) ;国家高技术研究发展计划 (863计划 )课题 (No 2 0 0 1AA1 1 2 0 80 ) ;清华大学信息学院 985基础创新研究基金

摘　　要：随机Petri网模型是系统性能评价的有力工具 ,但其状态空间随模型规模的增长而指数性增长的问题限制了其对复杂和大规模系统模型的性能数量分析能力 .因此 ,在对模型进行分析之前 ,先对其进行适当的性能等价化简 ,是一种更为可行的分析方法 .本文首先讨论了一类随机Petri网 -基本随机Petri网 (ESPN)的性能等价分析方法 ,这类随机Petri网由顺序、并行、选择和循环等四种基本结构及其组合构成 .作者推导出这四种基本结构的性能等价公式 ,并运用自底向上逐步综合替代的分层分析方法 ,给出这类随机Petri网模型的性能等价化简分析方法 ,该方法的复杂性随模型增长而线性增长 ,有效解决了其性能数量分析问题 .然后 ,讨论了两种非基本结构到基本结构的转换规则 ,使得复杂的随机Petri网模型也可能转换为ESPN模型 。Stochastic Petri Net (SPN) are a powerful modeling and analyzing tool for system performance evaluation.But the problem of state space's explosion of SPN limits its ability to analyze complex and large scale systems.So it is more feasible to simplify SPN model on the basis of performance equivalence before analyzing it.In this paper,the authors define a class of SPN Elementary SPN (ESPN) which is composed of four elementary subnets including sequence subnet,parallel subnet,choice subnet and iteration subnet,and propose a group of performance equivalence formulas for the four elementary subnets,as well as a method of performance equivalence simplification and analysis for ESPN with linear time complexity.In addition,two transforming rules are put forward to transform non elementary subnets into combined elementary subnets such that the proposed algorithm can be used in analysis of more general SPN.

关 键 词：随机PETRI网 性能等价 SPN 状态空间爆炸 

分 类 号：O643.22[理学—物理化学] TP30[理学—化学]