（计算机软件与理论专业论文）petri网若干关键技术的研究及其应用.pdf

中文摘要 中文摘要 随着计算机软件的飞速发展，提高软件开发的效率已成为一个非常重要的问 题。采用形式化开发方法，不仅可以极大地减少软件设计早期的错误，缩短开发 的总体时间，而且有利于开发人员之间的沟通，提高软件的可靠性。p e t r i 网是形 式化软件开发的重要方法之一。 p e t r i 网是一种对系统软件形式化、图形化的描述和分析工具，具有直观、易 懂和易用的优点。对于具有并发、异步、分布、并行、不确定和随机性的离散事 件动态系统，都可以利用这种工具构建模型。通过对模型的进一步分析，即可得 到有关系统静态结构和动态行为方面的信息，根据这些信息可以对要开发的系统 进行评价和改进。 本文着重研究了p e t r i 网的建模方法、分析技术及其在路由搜索算法中的应 用，列出了目前该领域有待解决的一些问题，取得的主要研究结论如下： 第一，从理论上分析了不可见任务的功能，针对相应的类别给出检测方法， 提出从日志中挖掘包含不可见任务工作流网的0 c 撑算法，该算法突破了对不可见任 务的挖掘盲区，并已作为挖掘插件实现到开源的进程挖掘框架p r o m 当中，通过 编写大量的人造日志并收集企业的实际日志，对算法进行了全面的实验评估。文 章还对建模的另一个核心环节，建模语言进行了研究。针对b p m n 目前存在较多 模糊语法的情况，提出将b p m n 转换成y a w l 语言。转换不仅可令y a w l 的分 析工具和工作流引擎为b p m n 服务，而且严格的y a w l 语义能帮助b p m n 消除 二义性，有利于b p m n 规范的进一步完善和改进。 第二，分析了目前现有的各种p e t r i 网化简方法，首次将逻辑电路中成熟的技 术应用在p e t r i 网中，提出了一种新的基于逻辑代数的化简算法，将化简单位从单 个元素扩展到无圈子网，提高了化简效率，并扩充了化简范围。本文还利用结构 理论解决了结构活网到活系统的极小标识求解算法，并对p e t r i 网的一类特殊性 质：空标识可再生性进行了求证，解决了空标识可再生网在运算中的保持条件。 这些结论在进程挖掘领域具有广阔的应用前景。 第三，提出了一种融合p 2 p 和c d n 优点的新型网络架构，将p e t r i 网技术与 蚁群算法相结合，给出了新型网络的最优选径算法。实验表明该模型及路由算法 中文摘要 具有较高的稳定性和鲁棒性。 关键词：p e t r i 网，建模，分析，算法 a b s t ra c t a b s t r a c t i th a sb e c o m eav e r yi m p o r t a n ti s s u et h a th o wt oi m p r o v et h ee f f i c i e n c yo f s o f t w a r ed e v e l o p m e n t ，a st h ec o m p u t e rs o f t w a r ep r o g r e s s e sr a p i d l y f o r m u l a t i o n t e c h n o l o g yh a st h eb e n e f i t so fr e d u c i n ge r r o r si ne a r l ys t a g eo fs o f t w a r ed e s i g n , a n d s h o r t e n i n gt h ed u r a t i o no fd e v e l o p m e n t i ta l s oh e l p st oi m p r o v et h er e l i a b i l i t yo f s o f t w a r ea n db u i l dac o m m u n i c a t i o ne n v i r o n m e n tf o rd e v e l o p e r s o n eo ft h em o s t w e l l - k n o w nf o r m u l a t i o nm e t h o d si sp e t r in e t s p e t r in e t sa r ec r u c i a lt o o l sf o rf o r m u l a t i o ns o f t w a r ea n dg r a p h i c a lr e p r e s e n t a t i o n , 谢ma d v a n t a g e so fi n t u i t i v e n e s s ，u n d e r s t a n d a b i l i t ya n du s a b i l i t yw h i c hm a k et h e m s u i t a b l ef o r t h eu s eo fm o d e l i n ga n dv e r i f y i n gd i s c r e t ee v e n ts y s t e m s 谢lc o n c u r r e n t ， a s y n c h r o n o u s ，p a r a l l e l ，u n c e r t a i n n e s sa n dr a n d o m n e s s t h ei n f o r m a t i o no fm o d e l s t r u c t u r ea n dd y n a m i cb e h a v i o rc a i lb e # y e nb yv e r i f i c a t i o na n di tc a l lb eu s e dt o p r o m o t es y s t e m t h i sd i s s e r t a t i o na i m st op r e s e n tp e t r in e t sa b i l i t i e so fm o d e l i n g , v e r i f i c a t i o n ，a n d a p p l i c a t i o ni nr o u t i n ga l g o r i t h ma n dt ot a c k l et h el i m i t a t i o n si nt h el a t e s td e v e l o p m e n t t h em a i nr e s u l t so ft h j sr e s e a r c ha r ea sf o l l o w s ： f i r s t , b a s e do nt h ef u n c t i o n a lc l a s s i f i c a t i o n so fo r d i n a r yi n v i s i b l et a s k s ，t h e 耐 a l g o r i t h mw a sp r o p o s e d ，w h i c hm a d eu s eo fs e v e r a lr e a s o n i n gm e t h o d sf o rt h e d e t e c t i o no fi n v i s i b l et a s k sa n db r o k et h eb l i n ds e c t i o ni nm i n i n gt e c h n i q u e s t o e v a l u a t et h ep r o p o s e da l g o r i t h m ，an u m b e ro fe x p e r i m e n t sw e r ei m p l e m e n t e db a s e do n a r t i f i c i a ll o g sa n dr e a l l i f el o g sf r o mc o r p o r a t i o n s am i n i n gp l u g - i ni si n t e g r a t e di n o p e n s o u r c ep r o c e s sm i n i n gf r a m e w o r kn a m e dp r o m t h i sd i s s e r t a t i o na l s of o c u s e s0 1 1 t h em o d e l i n gl a n g u a g e w ed e f i n e dat r a n s f o r m a t i o nb e t w e e nb p m na n dy a w l w h i c hc o u l dc l a d f yt h ea m b i g u o u ss y n t a x e so fb p m n a tt h es a m et i m e ，b p m n m o d e l sc a l lb ea n a l y z e db yy a w lv e r i f i c a t i o nt o o l sv i am a p p i n g t h et r a n s f o r m a t i o n b e n e f i t st h ei m p r o v e m e n to fb p m ns p e c i f i c a t i o n s e c o n d ，b ys t u d y i n gt h ev a r i o u se x i s t i n gp e t r in e t sr e d u c t i o nm e t h o d s ，an e w l o g i c a l g e b r ar e d u c t i o na l g o r i t h mb a s e d o nl o g i cc i r c u i tw a sp r o p o s e d t h er e d u c t i o n i i i a b s t r a c t o p e r a t i o nu n i tw a se x t e n d e df r o me l e m e n to b j e c tt oa c y c l i cs u b n e t t h em a j o r a d v a n t a g eo ft h i sa l g o r i t h ml i e di ng r e a t e re f f i c i e n c ya n db r o a d e rr e d u c t i o ns c o p e f u r t h e r m o r e ，s t r u c t u r a la n db e h a v i o r a lp r o s p e r i t i e so fp e t r in e t sw e r ei n v e s t i g a t e d ， e s p e c i a l l yo nl i v e n e s s ( i n c l u d i n gs t r u c t u r a ll i v e n e s s ) ap o l y n o m i a la l g o r i t h ma b o u t m i n i m a lm a r k i n go fs t r u c t u r a ll i v ep e t r in e t sw a sp r e s e n t e d i na ne m p t ym a r k i n gn e t ， i tw a sv e r i f i e dt h a tt h er e p r o d u c i b i l i t yc a nb eh e l du n d e ro p e r a t i o n s t h e s er e s u l t sc a n b eu s e di np r o c e s sm i n i n g t h i r d ，w ep r e s e n t e dan o v e lc d ni n f r a s t r u c t u r eb a s e do np 2 ei nc o m b i n a t i o n w i t hp e t r in e t sa n da n tc o l o n i e sa l g o r i t h m , t h eo p t i m i z e dp a t hr o u t i n ga l g o r i t h mw a s p r o p o s e d t h ee x p e r i m e n t a lr e s u l t sd e m o n s t r a t e dt h a tt h e n e tw a sag e n e r a ls t r u c t u r e o v e r l a yn e t w o r kw i t hh i g hs t a b i h t ya n dr o b u s t n e s s k e yw o r d s ：p e t r in e t s ，m o d e l i n g , v e r i f i c a t i o n , a l g o r i t h m i v 本论文所用到的图形列表 图1 1 图1 2 图2 1 图2 2 图2 3 图2 4 图3 1 图3 2 图3 3 图3 4 图3 5 图3 6 图3 7 图3 8 图3 9 图3 1 0 图3 1 1 图3 1 2 图3 1 3 图3 1 4 图3 1 5 图3 1 6 图3 1 7 图3 1 8 图4 1 图4 2 图4 3 本论文所用到的图形列表 利用p e t r 网模拟实际系统示意图2 论文各章节的推荐阅读顺序1 3 n 和死存在冲突15 p 处存在冲撞一16 定义2 1 5 的范例1 7 定义2 1 6 和定义2 1 7 的范例1 7 与表3 1 日志相应的p e t r i 网模型2 3 a 算法对不可见任务的挖掘。2 4 s k i p 、r e d o 、s w i t c h 类不可见任务的子结构。2 6 包含不可见任务且满足y 矽x 的结构2 7 满足约束关系的子结构2 8 冗余的虚假依赖关系2 9 利用算法硝从日志玛中所得模型炳3 2 觯算法对企业日志进行挖掘的p r o m 截图3 3 b p m n 的核心子集( c o r es u b s e t ) 3 7 b p m n 到y a w l 的简单映射4 0 多个开始、结束事件的映射4 0 a i - h o c 复合子进程的映射。4 2 信息流的映射4 4 异常处理4 5 门链路化简4 5 b p m n 2 y a w l 算法实例4 8 b p m n 2 y a w l 的结构4 9 b p m n 2 y a w l 在p r o m 中实现截图5 0 基本门电路的p e t r 网模型一5 5 几个命题的图示。5 5 定义4 3 ，4 4 的图示5 7 v i i i 本论文所用到的图形列表 图4 4 图4 5 图4 6 图4 7 图4 8 图4 9 图4 1 0 图4 1 1 图4 1 2 图4 1 3 图4 1 4 图4 1 5 图4 1 6 图4 1 7 图4 1 8 图4 1 9 图4 2 0 图4 2 1 图4 2 2 图5 1 图5 2 图5 3 图5 4 最大无圈子网，5 8 规则8 ( 1 ) 的连接图示6 0 ，经化简后的结果6 1 投诉处理进程的p e t r i 网表示及化简结果。6 3 修改计划流程的p e t r i 网表示及化简结果6 4 变迁发生序列中只有一个环6 6 变迁发生序列呈现多环路叠加p l 处有冲突6 7 变迁发生序列呈现多环路叠加p 与尸3 等价6 7 算法实例6 9 算法的关联矩阵转换7 0 定义4 1 6 的图示7 1 弘不变r 不可实现，但r 是可实现的。7 2 伊是c 1 和c 2 矩阵的拼接7 4 l ，m 的同步合成网不再是空标识可再生的。7 4 定理4 8 的图示7 6 中p 被子网替换后生成新网7 7 定理4 1 1 的图示7 8 呈现s p a g h e t t i 结构的模型局部( 完整模型的2 5 ) 8 0 g o o g l ee a r t h 上同一地形不同角度的图片8 0 基于p 2 p 的c d n 网络拓扑结构8 6 ，b 函数曲线9 3 。转换为p e t r i 模型9 6 不同网络拓扑下平均路由延迟1 0 3 表3 1一个完备的事件日志2 3 表3 2建模语言对工作流模式支持的比较3 5 表3 3活动属性的映射4 1 表3 4转换前后元素个数比较5 0 表4 1r m l c 化简技术与传统方法的比较6 5 表5 1人，b 函数参数9 3 表5 2实验曲线参数1 0 2 i x 缩略词表 缩略词表 在论文中用到的主要英文缩写及其全称列表如下： a c a s y m m e t r i cc h o i c en e t 非对称选择网 a m a c a l g o r i t h mo fm a x i m a la c y c l i cs u b s e t s最大无圈子网算法 a w l t a l g o r i t h mo fw l - n e tt h r o u g h n e s s 畅通性检测算法 b p db u s i n e s sp r o c e s sd i a g r a mb p m n 图形元素集 b p e lb u s i n e s sp r o c e s se x e c u t i o nl a n g u a g eb p e l 语言 b p m ib u s i n e s sp r o c e s sm a n a g e m e n ti n i t i a t i v e业务进程管理组织 b p m nb u s i n e s sp r o c e s sm o d e l i n gn o t a t i o nb p m n 语言 c d nc o g e n td e l i v e r yn e t w o r k内容分发网络 c ec o n d i t i o n e v e n ts y s t e m条件事件系统 c o s a c o m p u t e r u n t e r s t u t z es a c h b e a r b e i t u n g c o s a 语言 c t l c o m p u t a t i o nt r e el o g i c 计算树逻辑 d h t d i s t r i b u t e dh a s ht a b l e 分布式哈希表 d n sd o m a mn a m es y s t e m全局内容路由 d y n a m i c i r a a l g o r i t h mo f d y n a m i c - i n n e rr o u t i n g自治系统路由算法 e n e l e m e n t a r yn e ts y s t e m 基本网系统 e p ce v e n t d r i v e np r o c e s sc h a i n事件驱动进程语言 f cf r e ec h o i c en e t自由选择网 f f tf a s tf o u r i e rt r a n s f o r m快速傅立叶变换 f m sf l e x i b l em a n u f a c t u r i n gs y s t e m s柔性制造系统 f o l t lf i r s t o r d e rl i n e a rt e m p o r a ll o g i c一阶线性时态逻辑 i n s e r t p r o x ya l g o r i t h m ；o f i n s e r t p r o x y 服务器加入算法 i n s e r t t r e e a l g o r i t h mo fi n s e r t t r e e自治系统加入算法 k - m k a m a u g hm a p 卡诺图 | 6l i n kb a n d w i d t h 链路带宽 zc 矗舭c o s t链路费用 zdl i n kd e l a y链路时延 x 缩略词表 ，link f i t t e r 链路时延抖动 l f l a b e l i n gf u n c t i o n 标签函数 m gm a r k e dg r a p h 标识图 m m s em i n i m u mm e a ns q u a r ee r r o r 最小均方误差 万c珂d d ec o s t 结点费用 咒d，z d d e 如肠y 结点时延 栉， 聆d d ef i t t e r结点时延抖动 万z ，l o d e o s t结点丢失率 p l t l p r o p o s i t i o nl i n e a rt e m p o r a ll o g i c 线性时态逻辑 p tp l a c e t r a n s i t i o ns y s t e m 库所变迁系统 p 2 pp e e r t op e e r 点对点 p r o m p r o c e s sm i n i n g进程挖掘框架 p r o x y - r aa l g o r i t h mo fp r o x yr o u t i n g 服务器路由算法 q m ， q u i n em c c l u s k e yq - m 化简法 q o s q u a l i t yo fs e r v i c e 服务质量 r e d u c t i o nm e m o d sb 嬲c d 。nl o g i c rmrml c r m - 一l c 一化简方法 化间力泫 c i r c u i t s ms t a t em a c h i n e状态机 s o ns t r u c t u r e do v e r l a yn e t w o r k结构化覆盖网 s w f n e ts o u n d n e s sw o r k f l o wn e t合理工作流网 u m lu n i f i e dm o d e l i n gn o t a t i o n u m l 语言 w f n e tw o r k f l o wn e t 工作流网 w f l sw o r k f l o wl o g i cs y s t e m 工作流逻辑系统 x p d lx m lp r o c e s sd e f i n i t i o nl a n g u a g ex p d l 语言 y a w ly e ta n o t h e rw o r k f l o wl a n g u a g ey a w l 语言 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 如叩年易月，泪 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：q 幺杠导师签名：圣蔓型皿 日期：1 年6 月棚 第一章绪论 第一章绪论 本章首先阐述论文选题的目的与意义，随后介绍了国内外研究发展状况。最 后，阐述论文工作的创新之处、论文结构和内容安排。 1 1 研究背景与意义 p c t r i 网最早起源于c a r la d a mp e t r i 在19 6 2 年的博士论文 k o m m u n i k a t i o nm i t a u t o m a t e n ( 用自动机通讯) 【l 】。p e t r i 阐述了一台计算机中的两个异步分支间的通讯 理论基础，他的论文是p e t r i 网理论研究发展的奠基石。p e t r i 的论述引起了应用 数据研究( a d r ) 和麻省理工学院( m r l 0 的m a c 理论研究小组的注意，随后做了相 关的研究，这些研究主要展示了如何用p e t r i 网来模拟和分析具有并行分支的系 统。p e t r i 的开创性工作同时还引起了欧美学术界和工业界的注意，后来逐步为科 技界所接受，现在已是人们常用的一种数学工具。1 9 7 0 年至1 9 7 5 年，m i t 的计 算结构研究小组积极参与p e t r i 网相关的研究，并在m i t 举行第一次p e t r i 网和相 关方法的研讨会。从1 9 8 0 年以来，每年都要召开一次p e t r i 网理论和应用的国际 会议，p e t r i 网理论和应用的许多研究成果集中在会议论文集中。自1 9 8 5 年起， 每两年另召开一次p e t r i 网的性能模型的国际研讨会：还有关于有色p e t r i 网应用 与经验的每年一次的国际专题会议和关于p e t r i 网在工业进程中应用的b p m 国际 会议。p e t r i 网方面的论文己大量出现在各种学术年会和期刊上。 p e t r i 网理论正在被不断充实和完善。它的抽象描述能力也在不断的得到丰 富，从基本的条件事件( c e ) 网【2 】，位置变迁( p t ) 网f 3 垤【高级网( 包括谓词厂变迁网 刚和有色网【5 ，6 】) ；从没有时间参数的p e t r i 网到时间时延p e t r i 网 7 1 和随机p e t r i 网 i s 】；从一般有向弧网发展到被控p e t r i 网和混合p e t r i 网【9 1 3 】；从原子变迁到谓词变 迁和子网变迁【1 0 1 4 1 。当然，p e t r i 网描述能力的增强会在某种程度上增加p e t r i 网 的分析难度，增加对系统模型性质判断和计算的难度。因此，在实际应用中，常 常不仅需要根据特定的应用环境对网模型加以扩充，修改或限制，而且需要对 p e t r i 网模型进行化简处理或结构分析等。 到目前为止，p e t r i 网是人们公认最有效的形式化软件开发方法，特别是在目 电子科技大学博士学位论文 前广泛流行的面向对象编程环境中。在现今的软件设计过程中，人的思维深度非 常有限，某些系统，特别是比较庞大的系统，直观上我们可以得到一些信息，但 实际上这些信息也许完全错误，所以我们必须采用一种易于让人理解的形式化方 法来对系统建模并分析验证模型，从而得到正确的信息。p e t r i 网具有直观、易懂 的图形表示。此外，p e t r i 网中还有很多性质可以通过严谨的数学方法来对模型 进行分析验证，从而保证了系统的正确性。这给开发设计人员带来了极大的方便。 这一过程如图1 1 表示。 系统堡堡，p e t r i 网模型 完八厶析 完善分析 图1 1 利用p e t r i 网模拟实际系统示意图 建模是p e t r i 网作为形式化软件开发工具遇到的首要问题，特别是在现代产品 开发模式和市场环境下更显得重要。p e t r i 网的建模方法有三种【1 3 】：第一种是面向 状态的，它从一份可达状态性质的规约出发，从描述状态空间时态依赖关系的规 范入手；第二种是面向事件的，它通过同步事件以自底向上的方法组合系统模块， 从描述相互作用的协议入手，控制整个子系统中的事件流；第三种是面向对象的， 即将网作为托肯对象或向有色网中引入类的概念，设计者能够关注到对象在整个 生命周期的所有状态，以及它们之间的时态依赖关系。 面向事件的建模方法是目前最为常用的建模方法，传统的面向事件建模方法 所需知识高度分散在企业内外各类进程参与者头脑中，导致进程建模任务必须由 这些人协作完成，包括业务顾问、管理人员、领域专家、建模专家、普通员工等。 这些人往往属于不同的部门甚至不同的企业，常常使用不同的词汇描述同一进程 语义实体，对同一业务活动甚至会有根本不同的理解，这就造成了彼此间沟通和 交流的障碍。获取进程知识采取的主要交流方式则是开会讨论和调查问卷，得到 的最终模型质量与涉及人员的个人主观经验有直接关系，有时并不能反应业务过 程的真实情况。进程模型一旦建立，也并不能立即投入运行，而需要一个反复迭 代的优化过程，对模型进行不断的分析、验证和修改，以尽量确保进程模型真实 反映对应的业务过程。相关研究表明，获取和修改过程模型的精力占整个过程感 知信息系统开发时间的6 0 到8 0 t 1 5 ，1 6 1 。另外，按照设想创建的进程模型同该模 2 第一章绪论 型执行后产生的进程实例之间往往存在差异，甚至偏离实际的业务过程。由于业 务过程是复杂多变的，而业务过程所处的外部环境也在频繁改变，很难在定义进 程模型时预测进程实例执行时可能发生的所有情况，也无法囊括业务过程所有可 能的新需求。因此，过程感知信息系统在执行过程实例时，需要提供必要的异常 处理机制以提高其灵活性，来应对业务过程中各种可能的改变。当某类异常情况 在一段时间内频繁发生时，有必要对进程模型进行相应修改，使异常对应处理成 为模型中的合理成分。然而，普通员工往往只对执行业务活动有深刻的理解，对 于如何修改过程实例乃至进程模型知之甚少，而建模专家则与之恰恰相反。这时， 将再次涉及各类进程参与者之间频繁的交流和沟通，这一过程已被证实是相当耗 时，且容易引入不必要的错误。 上述都是由于对企业中现有的业务过程缺乏深入、客观的理解和刻画导致的。 与此同时，无论企业是否实施过程感知信息系统，均以某种形式存储了业务过程 中相关活动的实际执行信息，要么使用纸质材料，要么利用信息系统日志。将这 类信息按照固定格式进行收集和整理后，形成供统计分析用的事件日志。因此， 如何从描述了业务过程中活动执行情况的事件日志中自动发现客观知识这一问题 逐渐浮出水面，这一技术被称作进程挖掘。进程挖掘旨在从事件日志中挖掘出能 客观展现日志中所记案例执行顺序的过程模型，这些被发现的模型可以用来部署 支持业务过程执行的新系统，或者作为一种反馈工具，有助于审计、分析和改进 已经实施的业务过程。基于p e t r i 网的进程挖掘建模已有相当多的研究工作，但到 目前为止仍然有许多问题未得到有效解决，如不可见任务的挖掘即是极具挑战性 的问题之一。 不可见任务是指过程模型当中存在，而在事件日志中并不出现的任务。现有 的挖掘算法都假定了模型中的每个任务都至少在日志的某条轨迹中出现一次，但 并非所有模型都能满足该条件，这是由于模型当中往往存在纯粹用来路由的任务。 此外，噪声的存在使得日志中包含原始模型中并不存在的任务，这样挖掘所得模 型中也要考虑构造必要的不可见任务。再者，个别可见任务在某些日志轨迹中的 漏记，也会使得挖掘所得模型中出现不可见任务成为必然。目前，现有的进程挖 掘算法都没有考虑上述情况，故无法正确处理不可见任务。论文在建模方面的研 究重点将探索从日志中挖掘不可见任务的建模算法。 建模研究的另一个核心环节是对建模语言的选择。经典p e t r i 网兼顾了严格语 义与图形语言两个方面，具有直观与易懂的特点，使得建模人员能够比较方便地 针对模型的含义与最终用户进行交流。然而，p e t r i 网在建模上的准确性和清晰度 电子科技大学博士学位论文 是通过增加模型组成元素来实现的。这就给p e t r i 网带来了一个必然的不良影响一 一组成模型的元素数量过多，对非专业人士而言，理解一个p e t r i 网模型要比理解 活动网络图困难得多，这一问题在复杂进程上尤其突出。另一方面，p e t r i 网无法 体现数据流。尽管基于状态建模的p e t r i 网能够精确、方便地对过程的控制逻辑进 行定义，然而，在形式上一个p e t r i 网也只能体现这些内容，在这种情况下，数据 流就只能与控制流完全混合。当数据流逻辑与控制流逻辑不一致时，p e t r i 网就无 法显式地表达这种独立于控制流之外的数据流。再者，往往有的时候在进程建模 中需要用到变迁的内部状态，需要对变迁进行分解，即引入子网变迁的概念，以 建立变迁的内部精细结构，这些都是经典p e t r i 的软肋。 b p m n ( b u s i n e s sp r o c e s sm o d e l i n gn o t a t i o n ) 是由b p m i ( b u s i n e s sp r o c e s s m a n a g e m e n ti n i t i a t i v e ) 组织于2 0 0 4 年颁布一个高级建模语言的标准，该语言以 p e t r i 网为原语，在描述能力上做了进一步扩展，能够很好的解决上述经典p e t r i 网的不足。但由于b p m n 推出时间不长，规范中存在大量模糊语义，为模型的分 析带来很大的问题，这也导致了目前还没有分析工具和工作流引擎能直接支持 b p m n 。将b p m n 映射成其他具有严格形式化语义的高级语言，利用它们的分析 工具来为b p m n 服务，是值得尝试的一项工作。本文将探讨在开源的p r o m 平台 下b p m n 和y a w l 两种高级建模语言的等价转换能力。 在p e t r i 网的不断深入的研究和应用的过程中，一直存在着一个重大的的问 题，即“状态空间爆炸问题。随着科学技术的发展，实际系统越来越庞大和复 杂，网的可达状态和条件数量不断的增加，给网的分析带来了困难。有一种重要 的方法可用来降低大系统分析的复杂度，这就是系统的化简操作。所谓p e t r i 网的 化简，是指在某种性质不变的基础上，采用等效变换，以达到缩小状态空间、简 化系统分析的目的。 p e t r i 网的化简思想一直为理论界和工程界所关注，已做了大量的工作。目前 这方面的研究成果概括起来主要是基于“分而治之”的化简思路。即提出若干化 简规则，采用将网的局部结构与化简规则作逐一比对的方法完成化简，并证明按 照这些化简规则化简后的网与原网等价。显然，现有的化简技术步骤繁琐，化简 过程中的主观性和随意性较大，很难算法实现。本文将探索有别于传统化简思路， 可递归进行的化简方法。 p e t r i 网分析的状态行为特征有可达性( r e a c h a b i l i t y ) 、有界性( b o u n d e d n e s s ) 、活 性( 1 i v e n e s s ) 、活性单调性( 1 i v e n e s sm o n o t o n i c i t y ) 、家态( h o m e s t a t e ) 、包容性 ( c o n t a i n a b l e ) 、持续性( p e r s i s t e n c y ) 、空标识可再生性( r e p r o d u c i b i l i t yo f t h ee m p t y 4 第一章绪论 m a l l ( 蛐等【1 2 ，1 4 1 。其中，活性的研究尤为重要，活性反映了被描述系统的无死锁 性。对于一般的p e t r i 网系统，有关活性的判定非常困难，此类算法的复杂度往往 是指数级的，对于大一点的系统往往不实用。研究如何对网的活性进行判定的多 项式时间算法一直是研究的热点，但探索过程相当艰苦。现已证明对一些有限定 网的子类，其相应系统活性的多项式判定算法确实存在【1 7 。2 0 】。结构活的网只是在 结构上已经具备了活的必要条件，而非充分条件。如何利用已有的结果，找到一 个从结构活网到活系统的多项式时间资源分配算法是本文研究的一个重点。另外， 已有结论证明空标识可再生性与活性之间存在着某种联系【2 l 】，而不变、死锁和陷 阱 2 2 彩】这三个概念在寻找判定p e t r i 网系统活性多项式时间的算法中扮演着极其 重要的角色，寻找空标识可再生性与活性之间关联也是本文研究的一个重要方面。 本文的研究得到了国家留学基金委员会公派留学基金( n o 2 0 0 7 3 0 2 0 ) 、国家自 然科学基金( n o 6 0 4 7 3 0 3 0 ) 、四川省科学技术厅应用基础课题基金( n o 0 3 2 2 6 1 2 5 ) 以及华为高校科技基金项目( y j c b 2 0 0 6 0 5 7 f t ) 的支持。 1 2 国内外的研究状况 本节将着重介绍进程挖掘算法及高级建模语言的发展、p e t r i 网的化简分析技 术、结构理论的研究成果以及p e t r i 网在网络中的应用。从中可看出p e t r i 网作为 形式化软件开发方法的发展及趋于成熟的过程。 1 2 1 建模 进程挖掘建模思想最先由美国新墨西哥州立大学的c o o k 教授在1 9 9 5 年提出 【2 6 1 ，目标是从软件过程的事件日志中自动发现进程模型，并随之做了大量的后继 工作 2 7 - 3 1 】，作者称该技术为进程发现。算法采用有限状态自动机来表达进程模型， 能够处理并行结构和噪声。1 9 9 8 年美国i b m 艾曼登研究中心的m m 院士a g r a w a l 将其引入业务过程领域，并正式命名为进程挖掘【3 2 1 。在作者提出的算法中，进程 模型用弧上带有布尔表达式的有向图来表达，该算法能够处理并行结构和噪声。 以色列i b m 海法研究中心的p i n t e r 等人对a g r a w a l 的工作进行了扩展，利用了事 件日志中事件的开始和完成信息，从而可以显式检测任务间的并行关系【3 3 , 3 4 】。德 国乌尔姆大学的h e r b s t 等人提出的方法具有处理重名任务 的能力，作者同时开发了三个算法：m e r g e s e q 、s p l i t s e q 和s p l i t p a r ，所有这三 5 电子科技大学博士学位论文 个算法都能挖掘带有重名任务的进程模型。且前两个算法还适合顺序进程模型的 挖掘，而后者能够挖掘并发进程模型【1 5 1 6 ，3 5 - 3 7 1 。德国奥尔登堡大学的s c h i m m 教 授提出的方法【3 8 圳】与其它方法的主要不同在于该方法以获取完备且最小的进程模 型为目标，也就是要求模型能产生事件日志中记录的全部行为，但同时只能产生 最少量事件日志中未包含的行为。意大利卡拉布里亚大学的g r e c o 等人以挖掘过 程模型的层次树为目标，这些模型从不同的抽象层次描述事件日志，根节点是最 通用的模型，包含日志中所有过程实例的公共特征。叶节点代表对日志进行划分 的过程模型，根节点和叶节点之间的节点展现下一层节点的公共特征 4 2 。4 6 1 。法国 l o r i a 实验室的g a a l o u l 致力于从事件日志中发现进程模型的同时，改进模型的 事务行为，提出的算法包括如何从事件日志中挖掘工作流模式、工作流的事务行 为、活动间的事务依赖，乃至工作流恢复机制等【4 7 5 l 】。当前在进程挖掘建模领域 最活跃的团队是荷兰埃因霍温理工大学技术管理系的信息系统组，在国际知名学 者w m p v a nd e ra a l s t 的带领下，积极与国际各著名大学合作( 包括澳大利亚昆 士兰理工大学、奥地利维也纳理工大学、奥