摘  要： 要想用Petri网对系统进行有效的模拟和分析，就必须先建立起可靠准确的Petri网模型，目前很少有文献专门研究Petri网对系统的建模问题。对此，提出了基于系统行为序列的Petri网自动建模方法。该方法将系统所有行为序列组合为正规语言表达式，对于不同的系统，给出标注函数（即变迁和系统行为的映射关系），就可以建立起系统的Petri网模型。给出了电话呼叫业务建立用户Petri网模型的一个实例。该方法形式化强、通用性好，建立的模型标准规范，并且可实现机器自动建模，在目前的系统建模研究方面取得了进展。

　　关键词： 恰当终结的标准Petri网；系统行为序列；正规表达式；建模

0 引言

　　Petri网是一种系统模拟与系统分析的工具，采用Petri网对系统分析的文献很多，但在Petri网模型建立方面，大多文献是通过对系统的理解凭借个人经验手工建立Petri网模型[1-2]。人工建立系统的Petri网模型，特别是复杂系统的Petri网模型，不仅效率低，而且其准确性也值得商榷，因此系统的Petri建模方法是一个非常值得研究的问题。

　　目前用Petri网对各类系统建模方面主要有以下研究成果。参考文献[3]、[4]提出了使用Petri网子网为系统建模的方法，参考文献[5]、[6]给出了对并行程序建立Petri网模型的方法。上述的各类建模方法很大程度上减少了建模过程的重复性工作，提高了效率，并且使得模型有一定的规范性，但还存在一定问题：（1）各类系统有自己的基本模块，建模方法不通用，如无法将并行程序的建模方法应用于柔性制造系统中；（2）虽然采用模块化方法提高了效率，但建模方法不太灵活，很多系统的动态行为很复杂（如通信协议），不能或不易总结出其基本行为模块的Petri网模型；（3）各个模块组合的过程仍然需要人工干预，建模过程难以让计算机自动实现。

　　通过以上分析，本文提出了一种灵活性高、通用性强、严格、规范的Petri网自动建模方法。该方法的基本思想是：对于待建模的系统，先总结出该系统所有的行为，系统所有的行为序列可以组合为一个语言的表达式。对于不同的系统，只要给出其行为序列表达式，就可以构造一个带有标注的Petri网，使该Petri网产生的语言就是系统行为序列表达式。因此，这种方法建立的模型就可以真实准确地模拟系统的运行。

　　各类需要模拟的系统，其行为往往是有限的，系统的行为序列表达式也就限定在正规语言范围内，本文的建模方法是在正规语言范围内讨论的。值得一提的是，本文在正规表达式中引入了并发算子“//”，该方法也就自然地解决了系统并发行为的建模。

1 基本概念和术语

　　这里仅给出与本文相关的基本概念，关于Petri网的原理请参阅参考文献[7]、[8]。

　　定义1[7] 设N=（P，T；G，M0，，h，F）为一个标准Petri网，其中（P，T；G，M0）为一个Petri网，撞为有限字母表，h：T-?撞为标注函数，F为终止状态集。

　　定义2p∈P-{pf}：M（p）=0，则称N为恰当终结的标准Petri网。

　　定义3[7，8] 若N为一个恰当终结的标准Petri网，（h可带有ε-空标注）为恰当终结的标准Petri网产生的语言。

　　定理1[9] 恰当终结的标准Petri网产生的语言为正规语言。

　　定理2[9] 若L1和L2可以由恰当终结的标准Petri网产生，则L1○L2、L1∪L2、L1*、L1//L2都可以由恰当终结的标准Petri网产生。

　　定理3[9] 正规语言都可以由恰当终结的标准Petri网产生。

　　证明：由定理1、2可知，任给一个正规语言表达式都可以构造出一个产生该正规语言的恰当终结的标准Petri网。关于连接运算“○”、选择（并）运算“∪”、Kleene闭包运算“*”、并行运算“//”的Petri网模型构造方法参阅参考文献[9]。

2 系统行为序列表达式的Petri网建模方法

　　根据定理1、2、3可知，任给一个正规语言的表达式，都可以方便地构造出产生该表达式的Petri网模型。在对被模拟的系统建模时，首先根据系统的文本说明或特性给出系统的各种行为序列，可以给每个行为（或者说系统事件）起一个名字，这样就相当于得到系统的行为序列表达式，如果该表达式是一个正规表达式就可以直接构造出Petri网模型。系统行为序列表达式的Petri网建模具体方法如下：

　　（1）根据待建模系统的性质或是文本说明，给出系统所有的行为，为每个行为起一个恰当的名称。

　　（2）给出系统各种可能的行为序列，构建系统行为序列的表达式。

　　（3）对系统行为序列表达式合并化简，使其形式尽量简单。

　　（4）利用定理3对化简后的系统行为序列表达式构造Petri网模型。

　　（5）给出网模型中库所、变迁在被模拟系统中的实际含义。

　　（6）验证与修改（如果需要）。给出网模型的可达图，得到变迁发生序列H（?滓），将H（?滓）与步骤（2）中的行为序列进行比较，若一致，说明网模型正确；否则，修改网模型。

3 基于系统行为序列的Petri网建模方法的机器自动实现

　　首先要了解正规表达式关于连接“○”、并“∪”、闭包“*”、并行“//”运算的运算规则，即：

　　（1）运算优先级为：；

　　（2）从左向右运算；

　　（3）先括号内，后括号外。

　　具体优先关系如表1所示。

　　算法1 系统序列表达式转化为Petri网模型的算符优先算法

　　输入：被模拟系统行为序列的正规表达式E

　　输出：产生语言L（E）的恰当终结的标准Petri网模型即被建模系统的Petri网模型

　　FUNC Regular_transition_exp to Petri net

　　INISTACK（OPTR）；PUSH（OPTR，“#”）；INISTACK（OPND）；

　　Read（w）；{read a character from expression E}

　　While NOT（（w=“#”）AND（GETTOP（OPTR）=“#”））Do

　　IF w NOT  IN op THEN

　　[PUSH（OPND，w）；Create（net w）；]

　　ELSE CASE precede（GETTOP（OPTR），w）OF

　　“<”：[PUSH（OPTR，w）；read（w）]；

　　“=”：[x：=POP（OPTR）；read（w）]；

　　“>”：[theta：=POP（OPTR）；

　　IF theta=“*”THEN [c=POP（OPND）；

　　s：=c*；PUSH（OPND，s）；Unite（net c）]

　　ELSE[b：=POP（OPND）；a：=POP（OPND）；

　　s：=operate（a，theta，b）；PUSH（OPND，s）；

　　Unite（net a，theta，net b）]

　　ENDC（end case）；

　　RETURN（GETTOP（OPND），net GETTOP（OPND））

　　ENDF；{exp_reduced}

　　该算法可以实现机器对系统自动建立Petri网模型。

4 基于行为序列表达式的Petri网建模方法实例

　　本节给出基于协议实体行为序列表达式的Petri网建模方法的一个实例，对电信系统的电话呼叫业务建立用户Petri网模型，模拟用户打电话的过程。

　　4.1 电话呼叫系统简介

　　系统的模型如图1所示。

　　（1）用户：用户可以发起或接受呼叫，即要么是呼叫者要么是被叫者，如果是呼叫者，可以拿起电话并播出号码；如果是被叫者，当铃声响起，可以接通电话。不管是呼叫者还是被叫者，用户可以随时挂断电话。

　　（2）电话：也可以称为终端，是用户和网络的接口，使用终端，用户可以拨出或接入呼叫。

　　（3）网络：由交换机和线路组成，交换机控制两个用户之间连接的建立和释放以及管理线路。

　　4.2电话呼叫系统的用户Petri网模型

　　系统行为序列表达式的Petri网建模方法如下。

　　（1）总结电话呼叫系统中用户行为。

　　（2）给出在电话呼叫系统中用户所有可能的行为序列，构建系统行为序列的表达式。

　　呼叫者所有可能的行为序列如下：①拿起话筒，挂机。②拿起话筒，拨号，挂机。③拿起话筒，拨号，建立连接，双方通话，挂机。第三种情况是通话双方正常的通话过程，第二种情况可能是被叫方占线，第一种情况可能是呼叫者不想呼叫被叫方了。再来考虑被呼叫者的所有可能行为：④拿起话筒，双方通话，挂机。综上所述，电话呼叫系统中用户所有可能的行为序列如下：

　　①PickUp○HangUp

　　②PickUp○Dail○HangUp

　　③PickUp○Dail○Connect○Talk*○HangUp

　　④PickUp○Talk*○HangUp

　　（3）对系统行为序列表达式合并化简，使其形式尽量简单。

　　显然，步骤（2）中得出的4个式子是正规表达式，所以电话呼叫系统中用户所有可能的行为序列表示为：

　　PickUp○HangUp＋PickUp○Dail○HangUp＋PickUp

　　○Dail○Connect○Talk*○HangUp+PickUp○Talk*○HangUp（1）

　　根据正规表达式的运算性质，将式（1）化简，得：

　　PickUp○（HangUp＋Dail（HangUp＋Connect○Talk*○HangUp））+PickUp○Talk*○HangUp（2）

　　式（2）中没有合并步骤（2）中的④，这是因为①、②、③是呼叫者的行为，④是被呼叫者的行为，不合并④中的PickUp可以使模型更清楚地表达各自的行为。

　　（4）利用定理3和算法1对化简后的系统行为序列表达式构造Petri网模型，如图2所示。

　　（5）给出网模型中库所、变迁在被模拟系统中的实际含义，如表2所示。

　　（6）给出用户网模型Nuser的可达图，验证网模型的正确性。

　　从图2可以看出，从初始状态M0到终止状态M4有4条路径，即：

　　它们对应的变迁发生序列为：这与步骤（2）中总结的用户行为序列是一致的，这说明图2电话呼叫系统的用户Petri网模型是正确的。

5 结论

　　目前专门研究Petri网系统建模特别是自动化建模的文献很少。本文在分析现有的方法后，提出了基于系统行为序列的Petri网自动建模方法。该方法灵活性高、通用性强、严格、规范，同以往的方法相比，具有以下优势：

　　（1）该方法具有严格的理论依据，建模过程标准规范。在描述系统行为时采用正规表达式，在建模过程中网模型始终保持恰当终结的标准Petri网，每一步都采用正规表达式的连接运算“?莓”、并运算“∪”、Kleene闭包运算“*”、并行运算“//”等标准算子。这使得建模过程可以采用递归的方法实现，最终构造出的系统Petri网模型仍符合恰当终结的标准Petri网。

　　（2）该建模方法通用性较强，可以应用于较多领域，如程序验证、协议验证、柔性制造系统、离散事件模型、Web服务组合等。对于不同的系统只要给出系统行为和Petri变迁的对应关系（即h：T-?撞标注函数），均可以采用该方法建立Petri网模型。

　　（3）该方法形式化很强，构造出的系统Petri网模型简单准确，因而可以实现机器对系统的自动建模。文中并给出了易于机器自动实现的建模算法。

　　综上所述，本文提出的方法在目前的系统建模研究方面取得了进展，有较好的理论和实际应用价值。

　　参考文献

　　[1] 王燕，李华，周建涛.基于Petri网的移动IPSec快速切换的建模与分析[J].计算机研究与发展，2012，49（1）：82-88.

　　[2] 刘继承，张爱茹，李征鸿.基于Petri网的文件审批系统工作流建模[J].微型机与应用，2013，32（2）：77-80.

　　[3] 苏桂平，孙莎.一种基于有色Petri网的安全协议分析方法研究[J].微型机与应用，2011，30（15）：1-3.

　　[4] 郝东，蒋昌俊，林琳.基于Petri网与GA算法的FMS调度优化[J].计算机学报，2005，28（2）：202-208.

　　[5] Zhang Peng， Qi Mei. Modeling parallel MPI programs in Petri nets[C]. Instrumentation， Measurement， Circuits and Systems Advances in Intelligent and Soft Computing， Berlin： Springer， 2012，127：829-836.

　　[6] 崔焕庆，吴哲辉.并行程序Petri网模型的结构性质[J].计算机研究与发展，2007，44（12）：2130-2135.

　　[7] 吴哲辉.Petri网导论[M].北京：机械工业出版社，2006.

　　[8] 袁崇义.Petri网原理与应用[M].北京：电子工业出版社，2005.

　　[9] 范昊，吴哲辉.正规表达式与恰当终结的标准Petri网[J].计算机工程，2007，33（17）：13-17.