Petri网络模型（共8篇）
Petri网络模型 篇1
摘要：移动自组织网络是由无线移动节点组成的复杂分布式通信系统。研究了移动自组织网络的入侵检测问题,对当前Ad hoc网络上的入侵行为和入侵检测技术进行了分析,论述了学习Petri网络应用于入侵检测系统中的优势,给出了一个基于学习Petri网络的入侵检测实施模型,并在网络仿真软件ns2中对其进行了评估。
关键词：移动自组网,异常入侵检测,学习Petri网
0引言
Ad hoc网络是一种无组织的对等网络,使用无线通信技术。网络中没有固定的基础设施(如基站),各节点自主连接,组成网络。相邻的节点间一般可以直接通信,共享同样的物理频段;而非相邻的节点间采用多跳的方式进行通信,即通过中间节点进行转发。这种无组织的连接方式具有极大的灵活性,很适合应用在战场、灾难救援现场等地方,因为此时网络通信不能依赖于任何基础设施,也没有节点进行集中控制。相对于有线网络,Ad hoc网络更容易受到各种攻击。这主要是因为Ad hoc网络的无中心、动态拓扑、自组织、多跳路由等特点。由于这种网络的特点和广泛应用,使得Ad hoc网络的安全问题尤为突出。
目前,Ad hoc 网络安全保障主要从路由安全、密钥管理及入侵检测系统(IDS)等三个方面来解决。入侵检测技术能有效地检测到网络攻击并作出响应,是网络安全体系中的重要组成部分。入侵检测首先需要从网络中收集信息,然后对收集的数据进行分析处理。在入侵检测系统中通常需要在计算机网络环境中的若干不同关键点同时收集网络数据信息,这样不仅可以扩大入侵检测的范围,而且可以避免单个节点的检测的不完全性,进而从多个节点协同进行检测,以发现入侵行为。这也是分布式入侵检测系统的基本出发点。Ad hoc网络是一种新型的无线网络,正处于快速的发展阶段,新型的针对Ad hoc网络的入侵和攻击可能层出不穷,建立完备的入侵特征库将是非常困难的工作。因此,我们通常采用异常入侵检测算法来检测针对Ad hoc网络的入侵行为。虽然异常入侵检测容易存在误报警率较高的问题,但是在Ad hoc网络中,通过合理设置阈值,可以将误报警率控制在可容忍的范围。在本文中,我们设计了一种基于学习Petri网的IDS模型。在该系统中,节点间通过协同机制有效地防御了恶意节点的非法入侵和异常行为。
1Ad hoc网络对入侵检测系统的需求
IDS有两个必须实现的关键需求。它们是:(1)有效性——怎样使入侵检测系统对恶意的和良性的活动正确地分类;(2)效率——怎样尽可能地使IDS在效能成本合算的方式下运行。换句话说,这两种需求本质上提出了IDS必须检测入侵到管理系统的实际的百分比,而使错误的警报比率在低成本下处于可接受的等级上。一个理想的IDS可能被希望来支持以下的几个需求:
(1) IDS不能在Ad hoc网络中引入漏洞。即IDS本身不能使结点比它现在更差;
(2) IDS必须连续不断地运行并对系统和用户保持透明;
(3) IDS必须尽可能地使用较少的系统资源来检测并防止入侵。不希望IDS在结点间需要过多的通信或运行复杂的算法;
(4) IDS必须有正确的响应并且能够容错,它必须能从系统崩溃中恢复,有希望恢复到先前的状态,并恢复崩溃前的操作;
(5) 除对入侵检测和响应外,IDS也必须抵抗破坏。它必须检测它本身并检测攻击者是否已入侵,它可以与其它入侵检测系统合作来检测入侵。
2基于学习Petri网的IDS模型
2.1学习Petri网
Petri网技术已经广泛应用于系统的建模和控制中,但是经典的Petri网并不具备学习能力。文献[2,3]提出一种类似于人类大脑的新型网络,称为学习Petri网(LPN)。该模型是普通Petri网与神经网络的结合,具有Petri网的功能分布与神经网络的学习能力。在变迁的输入弧上引入激发加权( FW),在库所中引入激发信号(FS)。激发信号随着令牌(Token)的转移而转播。激发信号的值不限于整数,于是可以实现输入到输出之间的映射。通过对激发加权的调整来实现LPN的学习功能。
2.2基于学习Petri网的IDS模型的设计
基于学习Petri网络的入侵攻击检测模型如图1所示。
2.2.1 审计数据
审计数据的选取非常关键,因为采集的数据包含或隐藏了网络入侵的行为和痕迹。充分利用系统和网络日志文件信息是检测入侵的必要条件。日志中包含发生在系统和网络上的不寻常和不期望活动的证据,这些证据可以指出有人正在入侵或已成功入侵了系统。
2.2.2 审计数据的预处理
审计数据并不能直接作为神经网络的输入量,必须经过处理转换为神经网络所能识别的数据。首先确定活动规则采用定期活动规则,时间间隔可选为一天或几小时,然后提取用户行为进行分类,统计用户在此时间间隔内活动频率作为网络输入量X1,X2,…Xn。用户行为根据检测活动分类。如检测文件存取活动,则X1,X2,…Xn可代表文件创建、读、写、删除、更新、改名等活动的频率。
2.2.3 学习Petri网的结构
学习Petri网的结构如图2所示。
学习Petri网的学习算法采用与神经网络相同的BP算法。通过对激发加权和阈值的调整使得被评价变迁的激发信号到达其目标值。从输入库所到评价变迁存在一个由令牌转移形成的局部路径,学习只发生在该路径上的激活加权和阈值上。但是在BP神经网络中学习发生在所有的权值上。通过对网络权值和阈值的局部调整来实现功能分布。
BP学习算法由正向传播和反向传播组成,整个过程描述如下:
(1) 工作信号正向传播。输入信号从输入层经中间单元,传向输出层,在输出端产生输出信号,这是工作信号的正向传播。在信号的向前传递过程中网络的权值是固定不变的,第一层神经元的状态只影响下一层神经元的状态。如果在输出层得到期望的输出,学习结束;否则,转入误差信号的反向传播。
(2) 误差信号的反向传播。网络的实际输出与期望输出之间差值即为误差信号,误差信号由输出端开始逐层向前传播,这是误差信号的反向传播。在误差信号反向传播过程中,各层神经元的权值和偏差值由误差反馈进行调节,不断减小误差信号,使网络的实际输出更接近期望输出。
2.2.4 数据分析和响应
知识库中含有已知的入侵行为特征或者安全员定义的安全策略,当它观察到由神经网络提供的行为描述与知识库中的正常行为描述有偏差时,产生报警或者警告。输出值Y1和Y2表示正常行为和异常行为的概率,t1和t2分别表示正常和异常的阈值。若:
(1) Y1=1,Y2=0,表示正常;(2) Y1=0,Y2=1,表示异常,进行异常处理;(3) Y1>Y2,Y1>t1 ,则可认为是正常,可给出必要的提示信息;(4) Yl<Y2,Yl>t2,进行报警。
3实验结果及分析
实验平台为Pentium Ⅳ 1.8 GHz,512 MB RAM,使用的操作系统是Windows 2000下Cygwin平台,网络仿真平台是ns2。仿真中,节点运动范围3000m × 3000m,网络中节点的运动方式采用随机运动模型,即每个节点在该区域内从一点向另一点运动,运动速度在零到最大速度之间随机选取,到达目标点后,停留一段时间,然后随机选择一个新的目标点和一个新的速度,向新的目标点运动,依此类推,直至仿真结束。停留时间为5s。MAC层使用802.11协议,节点传输半径为300m,链路带宽为2Mbps,数据包大小为512字节,模拟时间为200s。本文恶意节点所占的比例在10%到40%之间。学习Petri网的训练采用BP算法对所选择的特征数据进行了10000次循环。检测过程中使用了6000个预处理过的记录,其中的600个用于测试,其它用于系统的训练。在学习Petri网的完全训练和测试完成后,大量的连接权值保持稳定,可以用来进行入侵检测判断。在评估入侵检测模型时,统计被正确检测到的异常事件数量和被错误判定为异常事件的正常事件的数量,然后计算出检测率和误报警率 。检测数据中包括500个用户事件,经过实验,该检测模型的检测率可以达到90%的准确率,误报警率始终低于7.8%,属于可以容忍的范围。
4结束语
随着移动Ad hoc网络的广泛应用,其安全性变得日益重要。在Ad hoc网络环境下,提出了一种基于学习Petri网的入侵检测模型,该模型较好地解决了移动Ad hoc网络中因节点移动、无线通讯、资源受限等因素带来的安全隐患,从仿真结果分析可知,提出的入侵检测模型在很大程度上增强了Ad hoc网络的安全性能。
参考文献
[1]曾英佩,郭山清,谢立.Ad hoc网络中的入侵检测[J].计算机科学,2005.
[2]Hirasawa K,Oka S,Sakai S,et al.LearningPetri network with route control[C].Proc IEEE Int Conf Systems,Cybernetics,1995:27062711.
[3]Hirasawa K,Masanao O,Singo S,et al.Learning Petri network and its application to nonlinear system control[J].IEEE Transactions on Sys-tems,MAN,and Cybernetics-Parts B:Cybernetics,1998,28(6):781789.
[4]王京慧,李宏光.动态模糊神经网络研究[J].北京化工大学学报,2003,30(2):7881.
[5]李家春,李之棠.神经模糊入侵检测系统的研究[J].计算机工程与应用,2001,37(17):3738.
网络舆情网民参与意图模型研究 篇2
摘要：在网络舆情网民参与行为收益成本分析基础上，利用社会交换理论，重点探讨网络舆情网民参与意图影响因素，并拟定相关的测度指标和测度方法。期望通过分析模型中关键因素感知利益和感知风险之间的逻辑关系，解释和预测网络舆情网民参与行为，为企业和政府监测网民互联网行为提供帮助。
关键词：网络舆情；网民参与意图；社会交换理论
中图分类号：D9 文献标识码：A doi：10.19311/j.cnki.1672-3198.2016.07.067
1 引言
网络舆情是指网民通过互联网表达与传播以危机事件为中心的多种意见、情绪和态度等的总和。近年来，旅游危机事件、食品安全事件等频发，严重威胁到公众人身财产安全，同时微博、微信等平台上发帖、回帖和转贴等网民参与行为，在缺乏网络道德约束、社会法律规制和网络治理机制的前提下，加推了网络舆情的形成。该网民参与行为直接影响网络舆情的演化方向，若不加以科学的引导与控制，极可能引起不必要的社会风险。因此，有必要对网络舆情网民参与行为影响因素进行研究，通过了解网民为什么要参与危机事件讨论以及网民不参与危机事件讨论原因，提出网络舆情健康发展策略。
本文拟从网络舆情网民参与收益成本角度分析，提出一个适合解释网络舆情网民参与行为的模型。经典技术接受研究（技术接受模型等）已经证实“参与行为”由“参与意图”所直接决定，因此，本文将“参与意图”作为因变量来解释网民参与行为。
2 网络舆情网民参与意图收益成本分析
美国社会学家Homans首次用经济学、社会学和心理学理论从微观角度提出社会交换理论（SET）。该理论认为收益和成本是人类从事一切行为的导向，其中收益并不特指物质财富，也有可能包括精神上的奖励、享受或安慰等心理财富和获得身份、地位与声望等社会财富；成本也不特指物质财富，也可能包括体力上和时间上的消耗、放弃享受、忍受惩罚和精神压力等。我们将人类从事一切行为结果称为效用，则效用等于收益减去成本，若效用为正，则人类继续从事该行为；若效用为负，则人类终止从事该行为。
依据社会交换理论，若将网络舆情网民参与行为看作一次交换行为，则网民是否继续从事交换行为准则就是权衡获得的收益与成本。此处，将网络舆情网民参与获得收益称为感知收益，该因素驱使网络舆情网民参与；将网络舆情网民参与付出成本称为感知风险，该因素驱使网民拒绝参与网络舆情。因此，网络舆情网民参与行为准则可表示为感知收益减去感知风险。当感知收益大于感知风险时，其效用为正，网民倾向于承担风险而选择参与网络舆情，而且当这一过程可以带来持续的正效用时，网民会持续参与网络舆情，否则拒绝参与。因此，本文拟从社会交换理论的感知收益和感知风险角度对网络舆情网民参与意图影响因素进行建模。
3 网络舆情网民参与意图研究模型
网络舆情网民参与意图感知收益大致包括外部激励、享受乐趣和自我提升三个方面，感知风险包括认知成本和执行成本两个方面。其中外部激励是网络舆情网民参与意图的外在动机，而享受乐趣和自我提升则是网络舆情网民参与意图的内在动机，认知成本和执行成本可理解为网络舆情网民参与所耗费的时间、精力等。构建研究模型如图1所示，研究假设涉及感知收益（外部激励、享受乐趣、自我提升）、感知风险（认知成本、执行成本）和参与意图三类变量。
3.1 模型研究假设
外部激励是促使网络舆情网民参与行为的重要因素，其中外部激励包括经济回报、社会规范和声望等不同表现形式。经济回报体现在物质金钱奖励，还有积分、经验等，而本文主要体现虚拟社区积分和经验的返点；社会规范指个人是否采取某行为所感受到的社会压力，规范越大，压力越小，外部激励越大；声望在虚拟社区对某件时间的威望。故提出：外部激励越大，获得的收益越大。据此提出：H1：外部激励对网络舆情网民参与的感知收益具有正向影响。
享受乐趣是指用户能够从其贡献知识的行为中获得满足感，而这种满足感来源其喜欢助人。但在网络舆情网民参与研究中网民通过分享自身对某件危机事件的看法，可使别的网友了解到此事件，从而自己感到愉快和心灵的舒服。故提出：享受乐趣是指网络舆情网民参与过程中，网民通过在虚拟社区中针对某危机事件的转帖、回帖等行为使别的网友参与到此事件的讨论中，自身获得满足感。参与行为越频繁，从中享受的乐趣越多，获得的收益越大。据此我们提出：H2：享受乐趣对网络舆情网民参与的感知收益具有正向影响。
自我提升是指渴望从别的网民出得到认可，以求地位和形象的认可。但在网络舆情网民参与研究中网民通过分享自身对某件危机事件的看法，达到自我营销的目的，从而驱使着网民不断的参与到危机事件讨论中。故提出：自我提升空间越大，获得的收益越大。据此我们提出：H3：自我提升对网络舆情网民参与的感知收益具有正向影响。
认知成本是指个体从事某种行为所耗费的时间、精力、物力以及财力等。但在网络舆情网民参与研究中，网民要花很多时间和精力来了解危机事件，去学习很多东西，甚至动用自己的社会资源来解决问题。这可以看作为一种机会成本，因为如果将这一过程所耗费的时间和精力用于其它活动，也许可以获得更多的回报和收益。故提出：认知成本越大，承担的风险越大。据此我们提出：H4：认知成本对网络舆情网民参与的感知风险具有正向影响。
执行成本是指网络舆情网民参与时，他们需要将自己的观点输入到不同的平台中。而在参与网络舆情的过程中，需要耗费他们大量的时间。特别是输入速度慢的，该过程将是冗繁且费力的，有可能网民就因为输入速度慢或者说要写的事情多，太耗时，而自己又没有时间来完成而放弃参与。故提出：执行成本越大，承担的风险越大。据此我们提出：H5：执行成本对网络舆情网民参与的感知风险具有正向影响。
Davis（1989）认为使用意图是指用户使用新系统的意向强度；据此我们提出：参与意图是指网络舆情网民参与的意向强度。依据社会交换理论，用户在决定是否参与某项行为时，会进行收益成本分析，以权衡该行为的效用。感知收益因素有利于网络舆情网民参与，感知风险因素不利于网络舆情网民参与。据此我们提出：H6：感知收益对网络舆情网民参与意图具有正向影响；H7：感知风险对网络舆情网民参与意图具有负向影响。
3.2 测度指标及方法
基于上述模型和假设，实证研究方案拟采用对网络舆情用户参与行为进行问卷调查的形式获取数据，利用结构方程对模型进行验证。测度问题将拟采用Likert七分量表形式（1表示完全不同意，7表示完全同意），对每一个测度指标进行1至7分的评价，对回收的问卷进行识别，挑选合格的问卷，并进行数据的信度和效度分析。研究指标体系如表1所示。
3.3 模型探讨
所提出的研究模型主要是为了解释网络舆情网民参与行为，通过对感知收益、感知风险与网民参与意图之间的重点分析，理解影响网络舆情网民参与行为的原因。所提出的测度指标是基于网络舆情网民参与收益和成本分析，也继承了已有的研究成果，所得出的模型具备较高的解释能力。
理论模型是以Homans（1958）的SET理论为基础，以感知收益和感知风险作为直接影响因素导致最终的网民参与意图的形成，结合感知收益和感知风险具体的表现指标最终整合成为本文的研究模型。影响网络舆情网民参与行为的影响因素并非仅限于此，例如社会规范、企业或政府反应是否及时以及网民过去的行为习惯等等因素同样影响着网络舆情网民参与行为，这些因素在研究中处于间接地位，都可以归纳为模型中所提出的影响因素。理论模型简单清晰的逻辑结构更能揭示网络舆情网民参与行为过程。网络舆情相关领域广泛，在研究中应该针对不同领域有目的地选择指标体系进行分析，这样才能对网络舆情网民参与行为做出科学的解释和预测。由于网络舆情网民参与收益和成本的重要性，关注收益和成本的影响因素，能够对解释网络舆情网民参与行为给予帮助，在选择检测网民行为时也能给出有利的建议。
4 结束语
Petri网络模型 篇3
近年, 随着信息技术与互联网金融的高速发展,P2P网络信贷的兴起在世界范围内产生冲击 。 Lending Clu 2007年在美国成立, 七年间作为美国P2P网络信贷的领先企业,目前已经成功撮合40亿美元的借贷交易。 与此同时,我国P2P网络信贷成长迅速,最新出炉的中国P2P网贷指数显示, 截至2014年12月30日上午11时 , 全国P2P网贷平台共2 358家,其中活跃平台(纳入中国P2P网贷指数统计)1 680家。 众所周知,由于网络信贷的高速成长,网络信贷企业水平参差不齐。 2014全年问题企业达275家,仅2013年12月份,由于投资人撤资,行业兑付压力骤升所导致的问题企业就高达92家。 网络信贷企业失败的原因总结起来, 除了自身因素外, 绝大部分都是由于平台内部风险控制较差, 一些借款客户不能正常还款, 使得贷款坏账率过高,而平台承诺投资人的收益过高,实际的优质业务很少, 导致平台资金链断裂所致。 因此对于网络信贷公司而言,降低信贷风险迫在眉睫。
审计作为内部控制风险管理的有力武器,查错纠弊、警示预险是其功能随着网络信贷P2P日益迅速的发展企业面临的信贷风险越来越多,这需要内部审计承担更多的治理和管理职能, 对重要风险进行预警。 由于P2P网络信贷建立在互联网数据化的基础上,网络信贷风险的审计预警应当利用网络信贷业务内部外部相关因素数据进行准确评价, 将内外部风险因素传导、风险识别、预警提示等结合起来,形成量化的风险评估结果,以准确判断业务风险高低,识别风险控制重点,形成审计预警, 帮助审计人员实现事前风险控制。 基于此,本文针对信贷业务流程中的信贷风险因素,模拟各风险因素间的因果关系, 采用Petri网构建信贷风险模型,计算出各风险因素之间的传导概率, 从而量化描述风险因素的传导机制,帮助审计人员更好地管控风险传导过程。
二、文献综述
目前国内 外对于P2P网络信贷 风险的研究 主要集中在对P2P网络信贷模式的探讨。 P2P网络信贷属于微型金融领域, 陌生人通过互联网进行借贷交易, 这种模式必然存在比传统金融机构借贷模式更大的风险。 如何消除互联网环境下网络信贷风险所造成的负面影响, 已经成为微型金融领域研究的一项核心问题。沈良辉、陈莹认为,我国P2P网络信贷行业存在借款人信用信息识别难、 借款用途真实性辨别难、借款抵押担保难等问题而且网 络信贷公司沉 淀资金安全 性差,网络信贷业务领域的可控性差,线上业务量少, 自身特点导致的风险性也大。 雷舰认为,对P2P行业的监管应该采取行业自律与外部监管相结合的原则,建立统一的行业准入机制,规范行业运行机制。黄叶危、齐晓雯认为P2P网络信贷存在法律缺失 、 平台用户使用不当、 平台自身导致的风险等问题, 并认为风险管理应以信用风险控制为主, 建议建立共同信用评级系统。 由上可见, 国内外对P2P网络信贷风险的相关研究, 大多为定性研究信贷风险的相关影响因素, 或只是提出风险管理的建议, 并没有将网络信贷的风险管理与审计预警结合起来。
从理论上讲, 对金融风险的处理和控制当然是越早越好。以往,只有当借款人偿还不力时, 网络信贷企业才会采取针对性的行动, 但此时问题已经发生并恶化至不可收拾, 这种滞后处理对充满风险的信贷行业是非常不利的,会造成巨大损失,如能建立审计预警系统, 在前期就根据各笔贷款业务风险程度实施预警审计方案, 将大大降低企业风险。 审计预警系统是主动的控制防御, 根据风险相关影响因素的因果关系,系统地进行风险评估, 对高风险项目实现审计预警, 风险越高的贷款项目预警越敏感, 相应的审计措施越周密。 如控制贷款审批将不良贷款率将至最低, 调整过高的投资回报率等,以及时降低企业风险,实现企业审计风险控制。 鲁爱民、孟志青认为审计预警应在明确预警、 排警的前提下, 结合被审计单位内外部环境状况,对公司运行的重要影响因素(包括管理机制与制度执行等)进行评价,将风险识别及信息传递、 预警提示等有机结合,以保证预警系统目标的实现。 国内的预警研究往往集中在危机已经发生或者危机发生后, 且研究重点主要集中在定性研究, 如对危机应对的建议或是对风险的评估。 研究的方法也主要是分析风险相关因素的因果关系并通过图表描述, 然后通过计算或者演算寻找规律从而进行预测。 但是这类研究也存在一定的缺陷, 即仅仅着眼于因果联系在实际应用中显然不够, 还需要能够事先根据外部数据及时反应,通过定量分析,迅速得出准确的风险评价结果,有效预警。Petri网建模能够随着外界输入信息的变化作出相应的调整, 及时通过风险影响因素的因果联系,准确评价风险高低,有利于审计人员事先对P2P网络信贷风险的控制,预防信贷风险造成的危害。
三、基于Petri网的审计预警系统模型
从前人各类审计预警系统的构想中不难看出, 大多数设想都是基于工作流程创造的, 这些按照工作流程, 设想的框架都缺少系统模型。 在工作流的过程建模中, 要求所建立的模型具有较强的描述能力,建模过程简便、直观,所建立的模型易于使用,同时还要求模型易于修改和扩充, 以适应不断变化的工作环境。进一步地,模型还要求能够便于被验证, 进行性能评价。 Petri网作为一种 描述并发系统 动态行为的有力工具, 能够很好地满足上述这些要求,准确描述信贷审批流程。 基于此,本文在阐述P2P网络信贷审批过程的基础上, 根据互联网金融企业开展网络信贷业务的经验教训,突出内外部因素在审批过程中与风险的因果关系,建立风险评价指标;给出基于模糊Petri网的评价方法,为定量评价网络信贷风险提供参考手段, 为审计预警提供依据, 确保互联网金融企业网络信贷风险的控制。
(一)信贷审批审计预警系统流程
简要描述: 借款人提出申请并提交材料,将借款人材料信息传递给资格审核部门并进行审核,初审通过,传递相关信息进一步认证信息是否真实,根据获得信息进行风险评估,将评估结果传递到审计部门选择相应预警方案,在网上提供贷款, 跟踪借款人履约情况,根据履约与否相应处理 ( 详见图1)。
(二)建立互联网信贷风险审计预警模型
通过对互联网信贷风险因素的分析 , 可以看出信贷主要风险因素来自于第三方因素 、 互联网企业内部因素 、 借款人因素 、 贷款人因素等多个方面 。 并且这些风险因素之间存在着一定的关联性 。 例如 : 在第三方因素中 , 对申请人抵押物的评估结果 , 将直接影响申请人互联网信贷审批 ; 公司内部人员工作能力也会影响贷款审核情况 , 处理稍有不慎 , 都将导致信贷风险的产生 , 甚至危机网络信贷企业的生存 。 可以说 , 在信贷风险环境中 , 大部分影响因素都存在着因果关系 。 这种因果关系符合模糊Petri网应用范围 。 因此 , 本文在互联网信贷风险模型建立过程中 , 主要运用模糊Petri网相关知识对互联网信贷风险影响因素进行图形化处理 , 并利用最长路径算法得到关键影响因素 , 直观 、 简便地实现对信贷风险环境中各影响因素的定量分析评价 , 并将信贷风险量化表达 , 对高风险项目提前预警 , 起到实现审计预警的作用 。
1. 基于模糊Petri网互联网信贷风险审计预警评价模型 。 根据模糊Petri网基本原理和对互联网信贷风险环境的分析 , 可以得到基于模糊Petri网互联网信贷风险评价模型FPN。
定义FPN为一个十元数组:
FPN= (P ,T ,D ,Pre ,Post ,μ ,β ,η , λ,Mo),其中:
(1) 有限模糊 库所集P ={ p1 , p2 , … ,pn} , 代表了模 型FPN网中互联 网信贷风 险影响因 素的集合 ,即为下页图2中图形集合;有限模糊变迁集T={ t1,t2,…,tm},即图2直线段;有限命题集合D={d1,d2,…,dn} , 在模型FPN中代表各库所即信贷风险影响因素对应命题的含义; 并且在模糊Petri网中, 需满足P = D ,P和T分别为库所和变迁的非空有限 集合,D为命题的非空有限集合。
(2)Pre:P×T→{0,1} 为前向关联函数,若Pre(p,t)=1,表明pj是ti的输入库所,否则不是。 假设在FPN模型中, 当Pre(p1,t1)=1,即库所p1申请人提供资料符合变迁t1的要求时,p1是t1的输入库所, 否则p1不是t1的输入库所。
(3)Post:P×T→{0,1} 为后向关联函数,当Post(p,t)=1时,pj是ti的输出库所,否则不是ti的输出库所。 假设在FPN模型中,若Post(p2,t2)=1,即库所p2:申请人申请贷款用途条件符合变迁t2的要求, 表明p2是t2的输出库所,否则p2不是t2的输出库所。
(4)μ 是T的关联函数 ,即 μ(ti)= μi,为T→{0,1}的实数映射,表示变迁的置信度(CF),根据具体实际情况推测决定置信度的具体值;β:P→[0,1] 表示该库所对应的命题成立的真实度的值;η:P→D是一个函数,映射库所对应的命题;λ 是变迁的阈值映射,即 λ:T→[0,1]。
(5)M0:模糊Petri网的初始标识, 用托肯表示, 当库所pj命题成立时, M(pj)=1,当库所Pj命题不成立时 ,M (pj)=0。 如在FPN模型中,若库所p3: 申请人过往银行评价, 相对应的命题d3: 银行评价申请人信用低经济实力差, 若库所p3对应的命题d3成立, 则M(p3)=1,否则M(p3)=0。
2.FPN网建立的步骤 。 FPN网的构建详细过程如下:
(1)确定致因因素。 详细了解互联网信贷的特征, 分析导致最终事件发生的基本因素, 得到互联网信贷风险致因因素含义及库所表示(详见表1)。
(2)确定中间因素。 由上一步分析确定的致因因素,总结出一系列相关的信贷风险影响因素,根据相互之间的因果关系分析确定各因素在整个Petri网中位置,最终得到某互联网信贷风险中间因素含义及库所表示,见表2。
(3) 根据互联网信 贷环境的分析 和FPN中各影响因素含义及库所表示 , 得到互联网信贷风险模型中各命题含义 ( 详见表3)。
(4) 确定变迁意义 ( 见下页表4)。 建立模糊Petri网 , 从最终事件分析寻找其致因因素或相关影响因素 , 并按因果关系进行模糊Petri网绘制 。 根据模糊Petri网的基本推理规则及触发规则 , 得到各因素及命题的结构位置及相关联事件之间的逻辑关系 。 依据对模型FPN中各影响因素分析及相关命题含义总结 , 绘制出基于FPN的互联网信贷风险模型 ( 详见下页图2)。
模型FPN中的相关数据 : 在模型FPN中 , 结合对实际情况的分析 , 根据模糊Petri网的理论 , 得出模型各因素中有 数据的为p1、p2、p3、p4、p5、 p6, 这些因素的模糊发生概率可以通过相关数据及分析资料得出 , 而其他无实测或数据 、 分析资料事件的模糊发生概率可根据相关推理规则及模型计算方法得出 。
3. 模型FPN的推理规则 。
(1) 规则一 。IF dk THEN dl(CF=μi), 其中 ,dk和dl为命题 , 相对应于表1及表2模型中各命题 , 且命题dl的真实度为 β( pj) =βj。 命题之间的因果关系用变迁ti表示 , 若满足pk∈·ti,pl∈ti· 时 , 则变迁ti含义为 “ 如果库所pk的命题dk成立 , 则库所pl命题dl成立 ”。 它的置信度为 μj。 在图2基于FPN的互联网信贷风险模型中 , 当变迁t4被触发时 , 即表示合同法律责任划分不明确 , 导致承担法律风险 , 那么当变迁t4被触发后命题d17的真实度的值为 :β(p12) ×μ17(t4)。
(2) 规则二 。IF dk1AND dk2AND… AND dki THEN dl (CF =μi), 其中 :dk1, dk2,…,dl为命题 。 变迁发生后 , 真实度的命题dl=min[β(p1)(p2),…,β(pj)]×μi。 如在下页图2基于FPN的互联网信贷风险模型 中 : 库所p1、 p5、p13与p15; p14、p2、p6、p10与p15等适用于此项规则 。 当p1、 p5、p13触发变迁t1, 导致p15和d15, 而命题d15的真实度的值为min[β(p1),β(p5),β(p13)]× μ15(t1)。
(3) 规则三 。 IF dk1OR dk2OR … OR dki THEN dl (CF=μi), 其中 :dk1, dk2,…,dl为命题 。 变迁发生后 , 真实度的命题dl为max[β(p1)×μi,β(p2)× μi,…,β(pj)×μi]。 如下页图2, 当p15、 p16、p17触发各自变迁 , 各变迁置信度分别为 μ18(t7)、μ18(t8)、μ18(t9), 导致p18和d18, 而d18的真实度的值为 max[β(p15)×μ18(t7),β(p16)×μ18 (t8),β(p17)×μ18(t9)]。
(4) 规则四 。 IF dk THEN dl1AND dl2AND…AND dl(CF =μi)。 变迁发生后 , 命题dli(j =1,2,…,l) 的真实度的值为 β (pj)×μi。 如果图2基于FPN的互联网信贷风险模型有相一致的表示 , 其库所对应命题真实度的值按照该算法得出 。
4. 基于模糊Petri网互联网信贷风险模型评价方法 。 设库所pj为容易引起互联网信贷风险的关键因素 , 各关键因素由各库所对应的命题di表示 , 且其真实度的值为 β(pj), 其他任何关键因素的 发生不影响致 因因素的发 生 ,ti为变迁事件 ,μi为变迁事件发生的可能性 。 假设 : 模糊Petri网有n个库所 ,m个变迁 , 具体算法步骤如下 :
步骤一 : 令M(pj)=1,pj为致因因素对应库所 , 根据图1及表1、 表2模型 , 基于FPN的互联网信贷风险模型致因因 素对应的库所 为p1,p2, … , p11,p12, 否则M(pj)=0,j=1,2,…,m。
步骤二 : 虚设库所p0, 对全部库所pj, 若M (pj)= 1, 则在p0和pj之间虚设一 个变迁t0i, 且令t0i =p0,t0i·= pj, 且有 β (p0) =1,μ (t0i)=β (pj), λ (t0i) =β (pj)。
步骤三 :记p0为 (0,1),p0为已标记未检查的库所 。
步骤四 : 当tk满足pj∈·ti,pk∈ ti· 时 , 按照得到标记的先后顺序 , 任选一个已标记未检查的库所pj, 与其相邻的一切库所pl:
1如果 β(pj)>λ(ti), 则给库所pk标记 [pj,β(pj)], 其真实度为 β(pk)= β(pj)×μ(ti)。 在互联网信贷风险评价模型中 : 库所p1、p7, 如果 β (p1)>λ (t7), 则给库所p7标记 [p1,β (p1)], 其真实度为 β(p7)=β(p1)×μ7(t1)。
2如果 β(pj)≤λ(ti), 则库所pk不标记 。
3如果库所pk已标记 , 则比较新旧标记 中的第2个标记 (pk) 和 β (pk), 如果 (pk) <β (pk), 则保留旧标 记 ; 如果 (pk)>β(pk), 则以新标 记取代旧标记 。
步骤五 :pj成为已检查过的库所 , 重复步骤四 , 直至所有点都被检查为止 。
步骤六 : 按目标库所的第一个标记反向追踪最长路径及最长路径上的所有库所 , 则该路径上的致因因素即为引发信贷风险的关键因素 , 路径长度的含义即为导致其信贷风险因素的可能性 。
四、结束语
网络信贷风险防范已引起了社会越来越多的关注, 随着网络信贷企业日趋成熟, 而风险管理已成为网络信贷交易和整个行业发展过程中的关键所在,正确评估风险,掌握风险的特征和变动趋势, 执行审计预警系统是防范和化解风险的有效途径。 而防范信贷风险最关键的就是在信贷交易达成之前对风险做出正确的预测, 选择相应的审计预警方案。 以Petri网为工具建立的信贷风险模型可以简洁、 直观地描述各风险因素之间的关系及其对信贷运作的影响,利用模糊Petri网的推理算法可以计算得出各风险因素之间的传导概率, 将风险因素的传导规律量化表达, 帮助互联网信贷企业详细了解风险的传导过程, 有针对性地采取审计措施, 为企业更有效地预测和控制信贷风险提供新的思路。 在此基础上也可以灵活运用互联网信息技术,如数据挖掘、大数据技术将极大减少系统整理资料与评估的时间, 提高结果准确度。 这是保障信贷质量和促进行业健康持续发展的必要手段。 J
摘要：近年来,互联网金融蓬勃发展,其中网络信贷以其快捷、高收益、低门槛的特点给传统信贷带来冲击,然而网络信贷高收益背后的高风险也是显而易见的。本文针对信贷业务流程中的信贷风险因素,模拟各风险因素间的因果关系,采用Petri网构建信贷风险模型。利用模糊Petri网计算出各风险因素之间的传导概率,从而量化描述风险因素的传导机制,帮助审计人员更好地管控风险传导过程,有针对性地及时采取预防措施。
Petri网络模型 篇4
工作流技术是90年代初随业务流程重组对组织机构和运行机制重组的需要而兴起的,该技术是近年来迅速发展起来的广泛应用于过程建模、模型分析和过程管理的一项新兴技术,是实现流程执行和控制管理的一条有效途径。工作流建模就是将现实世界中的业务过程抽象出来,并用一种形式化的、计算机可处理的方式来表示,这种形式化结果就称为工作流模型[1]。到目前为止,人们提出了不少有意义、有见解的工作流模型,基于Petri网的工作流模型就是其中的一种。Petri网是一种图形化的建模工具,由于Petr网模型对带有并发性、异步性、分布性、非确定性和并行性系统的有力描述[2],使其成为具有广泛应用前景的建模工具。本文先介绍Petri网及工作流模型的四种基本结构,再利用Petri网对工作流模型运行的决定因素:控制连接、活动、转移条件、启动条件和终止条件的重新解释,实现了对元模型过程定义的映射。
2 Petri网
Petri网在1962年由德国学者C.A.Petri作为一种过程建模和分析的工具提出,它是一种图形化的描述过程的强有力工具。同时,Petri网是一种经过严格定义的数学模型,具有规范的模型语义,完全支持工作流管理联盟所定义的六种工作流原语[3],可以对业务过程进行精确定义。
经典的Petri网是一个双重有向图[4],有两类节点类型,称作库所Place和变迁Transition,这些节点通过有向弧相连;在任何时刻,库所当中包含零个或者多个标记token:相同类型的两个节点之间不允许相连。Petri网中的库所表示条件,变迁表示任务,一个任务可能对应一个或多个变迁,一个工作项对应一个就绪的变迁,一个活动对应一个变迁的实施。
3 基于Petri网的工作流模型建模
3.1 工作流元模型
工作流模型是对工作流的抽象表示,也就是对经营过程的抽象表示,需要保证流程含义的正确、数据一致性和流程的可靠性,所建立的模型不仅有正确的含义,而且还要能提供一个由分析模型到投入实际实施模型的转换接口,从而使该模型能够被企业应用到工作流管理系统中执行,为此,工作流管理联盟定义了描述工作流模型的模型,即工作流元模型。
图1所示的过程定义元模型的组成核心是活动。工作流定义与活动、工作流相关数据之间是一对多的关系,即一个工作流定义由多个活动与多个工作流相关数据组成。活动、资源、工作流相关数据、需要激活的应用程序、转换条件之间是多对多的关系。
此外,工作流实例需要某种条件才能够启动和终止,一般情况下称它们为启动活动和结束活动。
在工作流模型中,活动作为结点通过连接弧连接在一起,在这里解释成是对工作流活动转移的控制连接,通过控制连接可以定义活动执行的先后顺序。当需要决定后继活动是否能执行,而且一个活动后面有多个后继活动可以执行时,实际的路径选择就是由活动开始条件、活动终止条件和转移条件三个附加的路径选择条件决定。
现实中的工作流模型是比较复杂的,但是它都可以归结为以下四种基本结构:
1)顺序结构用来定义一系列按固定顺序串行执行的活动,由一条无分支的通路构成,如图2(a)所示。
2)循环结构用来定义需要重复执行多次的活动,其中包含“显式或分离”执行原语,如图2(b)所示。
3)并行结构用于定义没有严格执行顺序的、可同时进行的分支活动。该结构包含两个基本的工作流执行原语:“并分离”和“并汇集”。并分离触发其后继活动的并发使能,后继活动可以以异步方式执行。并汇集则实现对后继活动结束过程的同步,以保证所有后继活动都完成后才继续向前推进流程,如图2(c)所示。
4)条件结构用来定义彼此之间具有相互制约与排斥关系的分支活动。该结构也包含两个基本的工作流执行原语:“或分离”和“或汇集”。有两种或分离,分别称为“隐式或分离”和“显式或分离”,如图2(d)所示。
3.2 元模型到基本Petri网的映射
从工作流元模型的阐述中,可以看出,工作流模型的运行由路径选择、活动的启动和终止条件、控制连接的条件选择共同决定的,控制连接可以构成四种不同的选择结构,并最终形成了工作流的四种基本流程结构。因此,通过对控制连接、活动和四种选择结构建模就可以实现对工作流的建模要求。过程建模如下:
1)通过用变迁来表示活动、库所表示活动的开始状态和活动终止状态、托肯表示实例来建立工作流的Petri网模型,而且某个活动终止后的状态和另一个活动的开始条件是重合的。
2)对于过程的启动条件相连的活动,活动的开始状态也是过程的启动条件,用一个特别的库所i来表示。
3)对于过程的终止条件相连的活动,活动终止后的状态也是过程终止后的状态,用一个特别的库所o来表示。
4)或分离建模关键在于分离点的建模,可以把分离点看出活动B和活动C的共同开始状态,这个开始状态也是一个转移条件,通过它检查前面执行活动即活动A的输出数据,判断与它相连接的活动哪个符合开始条件,从而启动相应的活动。同理,活动B和活动C的终止条件也可以合并,它同时也是一个转移条件,用来汇集得到活动B或活动C的数据,决定是否启动后继活动即活动A。
5)并分离需要表达两个活动的并行运行,将处在并分离位置的活动作为分离变迁和实体变迁,即使一个对活动的映射,也将活动完成后得到的数据传递给活动A和活动B的开始状态,保证活动A和活动B的开始状态是一致的,然后决定能否执行。
6)同理,处在并汇集的活动既是一个对活动的映射,也被用来汇集活动B和活动C完成后得到的数据,将活动B和活动C的终止状态作为活动A的开始状态,由这两个状态共同决定活动A能否执行。
用上面这几个基本元素,能够定义选择路径、并行路径、顺序路径和循环路径4种基本流程结构,从而形成更为复杂的工作流程。在模型映像方面,Aalst等人通过对四种基本流程结构定义构造基于Petri网的工作流模型。但是,这种定义方式为了对或/并分离和或/并汇集建模,引入了几种具有特殊意义的库所和变迁,特别地,他们还为或分离/汇集定义了确定性和不确定性两种形式,这样就增加了模型元素,模型与元素的对应关系就比较模糊,也更难于计算机化。本文利用Petri网通过对控制连接、活动、转移条件、启动条件和终止条件的重新解释,实现了对元模型过程定义的映射。这样所得到的基本Petri网,称为工作流网(Workflow net,WF_net)。
定义:Petri网PN=(P,T,F)为工作流网当且仅当:
1)PN有一个源库所(source place)i∈P,使得*i=φ。
2)PN有一个漏库所(sink place)o∈P,使得o*=φ。
3)每个结点x∈P∪T都是属于从i到o的一条路径上。
工作流网准确地区分了活动的使能与活动的执行两种状态。被使能的活动要真正的被执行,必须具备相应的触发机制。触发机制可以理解为一种使被使能的活动进入执行状态的外部条件,通常可以分为四种类型:
l)自动触发:活动被使能的同时就被触发。这种机制一般用于那些通过应用程序来自动执行、不需要与人进行交互的自动型活动。这类活动一旦被使能,就开始执行。
2)用户触发:活动的执行通过执行者从工作流任务管理器提供的工作流任务表中选择工作项来进行触发。当执行者选中某一工作项时,此工作项开始执行,被转换为活动。
3)消息触发:由系统外部的消息(事件)来触发活动的执行。
4)时间触发:由控制时间的定时器来触发使能的活动。这对于那些需要在预定的时间或给定的时间间隔要求来执行的活动使不可缺少的。
这四种触发机制将被用于工作流网的定义之中,在每一个活动(变迁)的上方,都标有相应的记号(如图3所示),以指明该活动使通过哪种触发机制来执行的。如果模型仅用来描述活动的顺序和状态,可以不详细描述这四种触发机制。
4 结束语
作为一种图形化工具,可以把Petri网看作与数据流图和网络相似的方法来描述系统模型;作为一种数学化工具,Petri网可以建立各种状态方程、代数方程和其它描述系统行为的数学模型。因此,Petri网具有形式化语义定义、图形表达的直观性、与数学图论相支持的理论严密性等优点,特别适合工作流建模的研究和应用。本文通过对工作流的阐述,得到工作流的运行由路径选择、活动的启动和终止条件、控制连接的条件共同决定,而控制连接和活动一起可以构成四种不同的选择结构,最终形成工作流的四种基本流程结构,并以工作流的四种基本流程结构为出发点,给出了如何把它们映射成符合工作流网定义的模型的一种方法。
参考文献
[1]Workflow Management Coalition.The Workflow Reference Model.Technical Report[R].WFMC-TC00-1003.Hampshire:Workflow Man-agement Coalition,1995.
[2]范玉顺,王刚,高展.企业建模理论与方法学导论[M].北京:清大学出版社,2001:109-111.
[3]Le Hors A,L e Hegaret P,Nicol G,et a1.Document Objec Model(DOM)Level3Core Specification[EB/OL].[2004-04-07].http://www.w3.org/TR/2004/REC-DOM-Level-3-Core-20040407.
Petri网络模型 篇5
工作流就是“业务过程的部分或整体在计算机应用环境下的自动化”, 它主要解决的是“使在多个参与者之间按照某种预定义的规则传递文档、信息或任务的过程自动进行, 从而实现某个预期的业务目标, 或者促使此目标的实现”。而工作流模型是工作流执行的前提和基础, 工作流建模就是将业务过程形式化并可用计算机处理的表示方式。目前提出了各种各样的工作流建模方法, 如:有向图、语言动作理论、Petri网等[1,2,3]。
在实际应用中, 基本工作流网模型非常简单, 是不能够表达所有可能遇到的工作流程。因此, 对工作流网进行扩展, 以提高建模能力。现有的工作流扩展方法有很多, 如时间、颜色、分块、分层等[4,5,6]比较成熟的方法。
本文简要介绍了Petri网和工作流的基本概念, 给出了工作流网合理性的三个基本要求。然后提出了一种添加复位弧的扩展方法, 并给出了该方法的形式化表示方法, 同时利用可达图的有关理论对该扩展方法的合理性进行了分析。经过实例分析, 可以证明该扩展方法能提高工作流的建模能力。
1 工作流Petri网
1.1 Petri网及工作流网的相关定义
Petri网是上个世纪60年代由Carl Adam Petri提出来的。因为Petri网有着坚实严谨的数学基础、完全形式化的语义、强大的表达能力、直观的图形表示等特点, 使其成为工作流建模和分析的主要工具。Petri网的定义如下:
定义1[7]—个四元组PN= (P, T, F, M0) 是Petri网, 当且仅当:
其中P为库所的非空有限集合, T为变迁的非空有限集合;F为流关系, 它是由元素P和T组成的有序偶的集合;dom (F) ={x| (y: (x, y) ∈F}, cod (F) ={y| (x: (x, y) ∈F}, 分别为F的定义域和值域;M0:P→{0, 1, 2, …}是初始标识, 表示系统的初始状态。
工作流网是在Petri网的基础上, 针对工作流的特点对其作了一些限制, 使它能够清晰地描述工作流状态的变化。在Petri网的基础上, 工作流网的定义如下:
定义2Petri网系统PN= (P, T, F, M0) 是一个工作流网 (WF-net) [8], 充分必要条件是:
(1) 存在一个源库所i∈P, 使得.i=ф;
(2) 存在一个终止库所o∈P, 使得o.=ф;
(3) 对于每个结点x∈P∪T, x都在从i到o的一条路径上。
满足如上条件的Petri网称为WFPN (Work Flow Petri Net) 。
1.2 可达性分析
工作流网的可达性问题可描述为:给定一个工作流网和一个目标状态, 是否存在一条从初始状态M0到目标状态的合法的变迁序列;如果这个合法的变迁序列存在, 则初始状态到目标状态可达, 否则不可达。可达性分析可以检测是否存在死任务, 可以通过建立WFPN的可达图来完成检测目的。
一个简单工作流网如图1所示, 它由六个库所 (p1, p2, p3, p4, p5, p6) 和五个变迁 (t1, t2, t3, t4, t5) 组成, 图2为该工作流网的可达图。可达图[9]是一个有向图G= (V, E, R) , 其中:v∈V表示一类可达的标识;e∈E表示从一类可达标识到另一类可达标识的有向弧;R是一个转换关系, R:E→V×V。图2所示的可达图中, 有六个可达标识, 从初始状态 (1, 0, 0, 0, 0, 0) 到最终状态 (0, 0, 0, 0, 0, 1) 有三条可达路径。每条路径从初始状态都能分别达到最终状态, 并且没有孤立的状态, 所以图1的工作流网不存在死任务。
1.3 工作流网的合理性
一个正确的工作流网应该是合理的, 合理性定义如下:
定义3[8]一个工作流网WFPN= (P, T, F, M0) 是合理的, 当且仅当:
(1) 对于每一个从状态i可达的状态M, 存在一个实施序列, 使得状态M通往状态o, 形式化表示为:
(2) 状态o是从状态i可达的唯一最终状态, 且结束时其可达图中至少会有一个标记M, 使得M=o, 形式化表示为:
(3) 在 (PN, i) 中没有死变迁, 形式化表示为:
其中:表示在工作流网的可达图中从标记x有一条到标记y的可达路径。
根据这三条规定结合可达图可以用来检查工作流网是否满足合理性。其中, 第一条规定了从状态i开始, 总可能达到最终状态o中有一个token的状态;第二条规定了一个token放入终止库所o的时刻, 所有其他的库所应该是空的。这两条也称为“正确结束”。最后一条规定了从初始状态i开始不存在死变迁, 即对工作流网不存在任何作用的变迁。
2 扩展工作流网
2.1 扩展工作流网的定义
基本工作流网模型非常简单, 是不能够表达所有现实生活中可能遇到的工作流程。因此, 给出了添加复位弧的扩展方法, 这种方法能够有效提高工作流网的建模能力。复位弧的概念如图3所示, 复位弧r连接库所和变迁, 由库所指向变迁, 用带双箭头的弧表示。
定义4五元组N= (P, T, F, M0, R) 为一个带复位弧的工作流网 (RWFPN) 的充要条件是:
(1) (P, T, F, M0) 是一个基本工作流网;
(2) R:T→2P, R称为复位弧的集合;
(3) 没有复位弧连接终止库所。
如果, M (p) ≥1, 则t在标识M下有发生权, 记为M[t>。t在M发生产生新的后继标识M'的计算公式如下:
图4中包含三个库所 (p1、p2、p3) 和变迁t。图4 (a) 是一个添加了复位弧后的简单模型, 图4 (b) 是变迁t触发后的模型, 触发前后token的分布情况分别为 (1, 0, 2) 和 (0, 1, 1) 。.t为库所p1, 当p1中有token的时候变迁t就可以被触发, 并且复位弧不影响变迁t的触发。当t触发时, 复位库所p3中的两个token被移除, 同时库所p1中的token被转移到p2和p3中, 从而p2和p3中都只有一个token。
2.2 添加复位弧的工作流模型
由于许多工作流语言已经具有取消的特点, 比如:Staffware有撤销的结构、BPMN (Business Process Management Net) 有取消、补偿和错误事件等特点。但是现有的工作流网是不能够描述这些的特点。因此, 对工作流网进行了扩展, 提出了带复位弧的工作流网。
为了说明带复位弧工作流网对取消功能的描述, 可以先看一下文献[8]中举出的一个保险索赔的例子, 如图5所示。这个图的问题在于:如果两个审查中, 一个通过, 一个不通过, 则会在p4或p5中遗留一个token;如果两个审查都不通过, 则拒赔会被执行两次, 结束库所中出现两个token。这和工作流网的定义以及理赔流程的本意是不符的。1) 从结构上分析, 一个具有良好结构特性的工作流网, AND/OR—split和AND/OR—join结构应当是平衡的。也就是由一个AND—split结构初始化的两个并行流不应该由一个OR—join进行汇合;通过一个OR—split结构创建的两个选择流也不应该由一个AND—join结构进行同步。图5中的初始化变迁t1是AND—split结构, 而变迁t4是OR—join结构, 显然不是良好结构特性的工作流网。2) 从保险索赔的处理规则分析, 一个索赔申请不能通过其中任何一个审查, 就应当拒赔, 而图5中两个审查都不通过的情况下会出现拒绝赔付两次, 这就违背了保险索赔流程的本意。
针对上述问题, 对图5模型进行了改进:对于p4和p5两个库所合二为一;根据OR—split等价原则对变迁t2、t3添加了通过和不通过两个选择条件, 这样能更直观的模拟保险索赔流程。一个添加复位弧和取消功能的保险索赔模型如图6所示。有p2—p8七个库所到取消变迁t9的复位弧, 每条复位弧是相互独立的, 并且只对相连接的库所起作用。在两个审查都通过的情况下, 会在p6和p7中产生token, 从而进行赔付。要是有一个审查不通过的情况下, t8中就会包含一个token, 此时t9满足触发的条件。当t9触发的时, 消耗库所p8中的token, 同时引出了复位弧的库所中含有的token全部被移除。当两个审查都不通过的情况下, t9触发消耗一个token移除一个token, 进而在p9中产生了一个token, 如是拒赔只会执行一次, 结束库所中也只有一个token。因此, 图6中不会存在有token遗留的问题, 拒绝赔付也只会执行一次。
图6的工作流网的可达图如图7所示, 这个工作流网可能的状态用一个十元组表示 (p1, p2, …, p10) 。每个库所有相应的token数, 初始状态是 (1, 0, 0, 0, 0, 0, 0, 0, 0, 0) 只有初始库所p1中有一个token。在图7中给出的可达图代表不同的可能状态, 总共有19个可达状态, 这里每一个可达状态不一定发生。一个节点没有输出的箭头, 对应的就是结束状态, 在结束状态没有变迁可以触发。根据工作流网合理性三个充要条件, 对图7所示的可达图进行合理性分析, 分析结果如下:1) 从任意一个状态开始, 总能够到达结束状态 (0, 0, 0, 0, 0, 0, 0, 0, 0, 1) ;2) 状态 (0, 0, 0, 0, 0, 0, 0, 0, 0, 1) 是唯一的结束状态 (即状态o) , 在可达图中该状态体现为一个标记为M= (0, 0, 0, 0, 0, 0, 0, 0, 0, 1) 的结点, 且有M≥0;3) 从初始状态出发, 每个变迁都能达到就绪状态 (即每个变迁均有发生的机会, 不存在死变迁) 。基于以上三点, 图6满足工作流网合理性的要求。因此, 添加复位弧后的保险索赔模型仍然是合理的。
3 可判定性
对于一个复杂的WFPN来说, 判定合理性并不容易, 对于扩展工作流网的合理性判定性问题就更为复杂, 已经有学者提出了时间扩展的工作流网的普遍合理性是不可判定的[9]。不幸的是对于添加了复位弧的工作网的普遍合理性也是不可判定的。因此, 对于一般性的应用而言, 扩展工作流网的合理性只能针对实际模型按照合理性的三个充要条件进行一一验证 (如2.2节中的保险索赔的例子中所做的那样) 。下面定理证明了带复位弧的工作流网的普遍合理性是不可判定的。
定理:带复位弧的扩展工作流网的普遍合理性是不可判定的。
证明:一个RWFPN是合理的, 当且仅当工作流网是活的而且是有界的[8]。而RWFPN是否有界是不可判定的。
(1) 带复位弧工作流网在一定意义下可以计算多项式, 在网N[x1, …, xn]中给定多项式Q。利用带复位弧的工作流网NQ计算多项式Q。计算多项式Q就是:从输入库所p1in, …, pnin中的token的一个向量, NQ可以把这些token按照触发序列转移到输出库所p1out, …, pnout中。NQ并没有产生新的token (因此它是有界的) 。而在RWFPN中是不可能精确的按照这种方法执行, 因为存在其他的触发序列。因此, NQ应该是这样的: (1) 它不能触发超过序列的变迁; (2) 当NQ正确结束时少于序列的变迁转化, 并且在输入库所到输出库所转移的过程中会有一些token丢失。
(2) 那么如何比较两个多项式Q和R。显然, 可以检查序列是否相等, 使NQ和NR是在相同向量下触发, 如果多项式Q和R不一致, 则必然会有token丢失。
(3) 我们用一种枚举方法代替上面的方法, 列举所有的向量。在这种方法下: (1) 存在一个RWFPN模型当给出向量; (2) 当从向量时会有token丢失, i<j。联系“检查Q≠R”方法和枚举方法, 我们可以得出RWFPN具有以下潜在行为:检查序列, 计算向量v0到向量v1;检查序列, 计算向量v1到向量v2…, 这种行为是无界的。只有两个条件使它有界: (1) 这个网可找到正确的行为评估多项式和枚举元组; (2) 对于任意的i∈N, 序列真正有所不同、不会丢失token, 并且任何其他行为都是有界的。
(4) 因此, 通过给出的多项式Q和R, 我们可以构造一个不定方程Q (x1, …, xn) =R (x1, …, xn) 是无解的。因为不定方程无解, 所以RWFPN模型的有界和无界是不可判定的, 进而可知道RWFPN模型的合理性是不可判定的。
证毕。
4 结语
本文通过分析WFPN模型, 提出添加复位弧对WFPN模型进行扩展的思想, 并对添加复位弧后的保险索赔模型进行了合理性分析, 从而证明了在一般情况下扩展的有效性。文中所举实例的模型是经典的工作流模型, 从这个模型可以看出, 在添加复位弧之后能够有效提高的工作流网的建模能力。但遗憾的是, 带复位弧的工作流模型的普遍合理性是不可判定的。因此, 对于一般性的应用而言, 扩展工作流网的合理性只能针对实际模型按照合理性的三个充要条件进行一一验证。带复位弧的工作流网, 能对很多具体流程做出很好的建模, 仍是有实际意义的。添加复位弧的扩展方法, 一定程度上增加了模型的复杂性。因此, 对扩展后的模型进行简化将是进一步研究工作的重点, 从而使之更趋近工作流网建模的实际需求。
摘要：为了满足工作流模型在建模能力上的要求, 提出一种添加复位弧对工作流网进行扩展的方法, 并给出该方法的形式化表示方法。通过一个保险索赔模型, 利用可达图对该方法进行合理性分析。最后, 证明了带复位弧工作流模型的合理性是不可判定的。
关键词：Petri网,工作流,工作流网,可达图,复位弧,合理性
参考文献
[1]苑迎春, 李小平, 王茜, 等.基于逆向分层的网格工作流调度算法[J].计算机学报, 2008, 31 (2) :282-290.
[2]梁莹, 徐福缘.企业专利资源管理流程本体建模研究[J].计算机工程与应用, 2010, 46 (1) :21-27.
[3]吴绍艳.工程项目工作流的Petri网表示及模型建立[J].计算机工程与应用, 2009, 45 (30) :10-12.
[4]Jiang Hong, Ding Xiangqian.Modeling of Hierarchcal Petri Net-Based Workflow[C]//Wuhan:Control and Industrial Engineering (CCIE) , 2011:113-116.
[5]卢捍华, 闵丽娟, 王亚石.工作流主从实例处理方法及其Petri网建模[J].通信学报, 2010, 31 (1) :92-99.
[6]申利民, 隋峰, 白莲, 等.基于扩展UML活动图的工作流模型研究[J].计算机应用研究, 2009, 26 (2) :287-590.
[7]袁崇义.Petri网原理与应用[M].北京:电子工业出版社, 2005:58-66.
[8]Wilvander Aalst, Kees van Hee.Workflow management:Model, methods and systems[M].Beijing:Tsinghua Press, 2004.
Petri网络模型 篇6
工作流技术已被广泛地应用于办公自动化、业务流程重组BPR(business process reengineering)等领域[1]。工作流参考模型[2]详细描述了工作流管理系统的有关概念,定义了工作流管理系统的各个组成部分、各部分的功能及相互之间的接口,规范了各种工作流管理系统的结构。工作流管理的关键在于工作流建模,即在概念级别上给出业务过程的抽象表示。本文针对知识密集型的业务过程提出了一种新的工作流建模技术,即人员-时间Petri网。作为建模的基础,首先介绍了Petri网和时间Petri网,然后具体给出了人员-时间Petri网的定义、性质以及构建方法,并进行了应用验证。
1两种基本的建模方法
1.1Petri网模型
Petri网是工作流主要的建模方法之一。其形式化定义是:
定义1 一个Petri网是一个三元组PN=(P,T,F):
(1) P是有限个库所的集合,P={pi|pi是库所,i=1,2,…,m};
(2) T是有限个变迁的集合,T={tj|tj是变迁,j=1,2,…,n}。库所和变迁没有交集即:P∩T=Ø;
(3) F是弧的集合,F=(P×T)∪(T×P)={f|fk是指从库所到变迁或从变迁到库所的弧,k={1,2,…,s}[3]。
1.2时间Petri网模型
时间管理是研究工作流执行的时间维计划,主要涉及估计不同的活动执行延迟、避免活动过程违反时间约束以及处理时间违反约束的异常。时间管理的关键在于时间信息的有效建模。时间Petri网在对传统Petri网进行了时间扩展后,成为一个有效的建模方法,其形式化定义是:
定义2 时间Petri网TPN=(PN,D,Γ),其中:
(1) PN是传统Petri网,PN=(P,T,F);
(2) D={dj|j=1,2,…,n},dj∈R∪{0},表示完成每个变迁tj所需要的时间;
(3) Γ={(tj,τj)|j=1,2,…,n},(tj,τj)表示变迁tj的实施时刻为τj[4]。
2一种新的建模方法(人员-时间Petri网模型)
2.1人员-时间Petri网模型
工作流实质上是一个活动流和资源流并行的业务过程。资源管理是工作流管理追求的一个关键指标,可以通过对流程的管理实现资源的最佳管理。进行业务过程重组或过程优化时,不仅要考虑各个任务环节的顺序、环节的完成时间,还有保证每个环节上有效资源的可靠实现。对于活动流和资源流并行的业务过程,时间Petri网方法的时间属性只能描述活动流,不能很好地描述资源流的状况。
气象业务保障流程是活动流和资源流并行的典型业务过程。气象业务典型的保障流程是:首先,值班员要画当天的天气图,然后根据对天气图的分析做出初步预报。如果预报结果和前一天预报结论出入不大或是值班员对当天的预报结果很有把握的前提下,值班员就会发布预报。如果当天预报结论和前一天提前预报结论有较大差异或者值班员不能肯定的情况下,值班员需要通知台长、外班员以及相关专家进行会商。最后,大家把会商结果反馈给值班员,值班员根据会商结果,作出最终预报结论,并由值班员把最终预报结论存档。由此可见,气象业务保证流程的主要资源就是“人”。根据此特点,本文把资源 “人”作为一个主要要素加入时间Petri网中,提出了一种基于时间Petri网的新的工作流建模方法,即人员-时间Petri网,其形式化定义如下:
定义3 人员-时间Petri网ATPN=(PN,D,Γ,A),其中:
(1) PN,D和Γ的含义同定义2;
(2) A={aj|j=1,2,…,n},aj表示每个变迁tj所对应的完成人员。
可见,人员-时间Petri网主要包括变迁、时间和人员三种要素。人员-时间Petri网应用这三种要素和三种要素之间的关系对工作流建模。变迁和人员之间的关系主要体现在由谁(Actor)来完成这个变迁;时间和变迁的关系主要体现在什么时间、在哪个时间段内必须完成这个变迁;时间和人员的关系主要体现在人员必须在哪段时间来处理这个变迁。从而构成了一个三维的关系。
下面分析三要素的主要属性:
变迁要素属性主要包括:t.name变迁的名称;t.actor 变迁所依赖的人员;t.function 变迁的功能描述;t.start_time变迁的开始时间;t.duration变迁的持续时间。
人员要素属性主要包括: a.name人员名称;a.role人员角色(由角色信息可以看出人员的能力信息);a.email人员的联系方式;a.org人员的组织信息。
时间要素属性主要包括:d.start变迁开始时间;d.min变迁的最小时间;d.max变迁的最大时间;d.ran变迁执行消耗的随机时间。
由于人员、时间、变迁是一个整体,它们的属性具有以下关联和约束关系:
(1) d.min<=d.ran<=d.max;
(2) t.duration=F(t.function)+F(a.role)+F(d.min)+F(d.max);
(3) t.actor=F(t.function)+F(a.role);
(4) t.start_time=d.start。
其中,F说明存在一定的函数关系。
2.2人员-时间Petri网的构建方法
针对Petri网的构建要求,下面逐一给出几种基本路由的人员-时间Petri网建模的方法。假设参加组合的任务为T1和T2,Ti=(PNi,Di,Γi,Ai)。其中,PNi=(Pi,Ti,Fi);D={di};Γ={(ti,τi)};A={ai},i=1,2。
(1) 顺序执行任务
T=T1∪T2,设T=(PN,D,Γ,A),如图1所示。
(2) 选择执行任务
T=T1⨂T2,设T=(PN,D,Γ,A),如图2所示。
(3) 并行执行任务
T=T1♁T2,设T=(PN,D,Γ,A),PN=(P,T,F),如图3所示。
(4) 循环执行任务
T=nT1,设n为任务T1执行的次数,T=(PN,D,Γ,A),PN=(P,T,F),如图4所示。
2.3人员-时间Petri网模型的建模步骤
Step1 由于基于人员-时间Petri网的工作流建模过程涉及三个要素,即时间、任务和人员,因此利用此方法建模时首先要确定业务流程由哪些任务组成,哪些人参加了业务流程中活动的执行,每个人负责哪个活动,对应的活动的时间要求是什么,有哪些约束。
Step2 为用户应用的每个任务建立基本的人员-时间Petri网模型。
Step3根据流程的时间逻辑关系,建模任务之间的依赖关系,按照任务之间的逻辑定义,构建工作流过程的人员-时间Petri网模型。
Step4任务之间的关系处理完毕后,得到的人员-时间Petri网模型即为用户应用的模型,从而可以计算出整个流程的整体时间要求和人员要求。
2.4基于人员-时间Petri网的气象业务保障流程建模
以说明简单起见,假设以下的气象业务保障工作流任务:T1:值班员根据当天的天气图进行初步预报;T2:值班员发布预报;Ts:在值班员不能很好肯定天气趋势的情况下,要求进行会商;T3:台长根据天气图进行预报;T4:外班根据天气图进行预报;T5:相关专家或其他人员根据天气图进行预报;Tj:把预报结果同时传给值班员;T6:值班员根据前面的预报结果进行最终预报;T7:值班员发布预报结论;T8:值班员把当天的预报结论保存存档。按照上面的模型构建步骤可以生成气象业务保障的人员-时间Petri网模型,工作流中相对应的库所用带编号的P表示,如图5所示。
根据人员-时间Petri网的定义和性质,我们采用Java技术开发了人员-时间Petri网的建模工具,可以添加变迁、添加库所、添加弧、删除已建模元素、移动已建模元素以及各类元素属性。人员-时间Petri网模型的信息生成XML文档传给工作流引擎,驱动工作流运行。
3结束语
人员-时间Petri网比时间Petri网更适合建模以“人员”为主体的知识密集型的工作流程,它最大的特点是能够保证正确的任务在正确的时间分配给正确的人员。人员-时间Petri网能有效地解决以下三个关键问题:将工作业务流程与知识流程相集成;促使知识成果共享;对人员知识需求的不确定、知识产生的动态性进行有效处理。
参考文献
[1]范玉顺.工作流管理技术基础.北京:清华大学出版社,2001.
[2]WfMC.WorkflowManagement Coalition Terminology and Glossary.Tech-nical report.Brussels:WorkflowManagement Coalition,1996.
[3]Murata T.Petri nets:Properties,Analysis and Applications[J].Proc.IEEE,1989,77(1):541-580.
Petri网络模型 篇7
工作流是一类能够部分或全部由计算机支持或自动处理的业务过程,在这一过程中,文档、信息或任务根据一系列过程规则在不同的执行者之间进行传递或执行。[1]
工作流管理系统就是能完整地定义和管理工作流,并按计算机中预定义好的工作流逻辑规定的次序,以执行软件的方式执行工作流,从而实现过程管理和过程控制。工作流管理系统可以使企业过程流水线化;可以很好地支持流程管理和经营过程重组的实施;通过自动化手段降低业务过程的成本;加速业务过程,给客户提供快速的服务;跟踪和控制业务过程的处理;能和其它应用系统和管理企业的其它方面的资源和信息整合,共同实现组织信息管理。[2]
1 工作流与办公自动化
工作流这种对工作进行优化的思想和技术,其主要的优越性在办公自动化方面表现得尤为明显。工作流能够描述一个企业或组织业务处理活动过程的模型,通过将工作活动分解定义良好的任务、角色、规则和过程来完成工作活动。在办公自动化系统中,几乎所有的业务流程都体现工作流。例如办公自动化应用系统的核心应用——公文审批流转处理、会议管理等。每一项工作以流程的形式,由发起者(如文件起草人)发起流程,经过本部门以及其他部门的处理(如签署、会签),最终到达流程的终点(如发出文件、归档入库)。
因此,工作流管理系统在企业、政府部门、学校等单位的办公自动化项目中的应用非常广泛。国内的工作流产品,西安协同软件的SynchroFLOW作为平台广泛应用于许多单位的OA项目开发,到目前为止,已有许多成功的案例。工作流管理系统作为平台进行OA系统开发,简化了开发步骤,降低了应用开发难度,提高应用开发效率及灵活性和节约了应用开发成本。[3]
以工作流管理系统为平台的应用系统有着如下的体系结构:由两个子系统构成,一个处理业务流程的管理(工作流引擎),另一个支持特定业务过程中具体任务的执行(服务于具体任务执行的应用软件),如图1所示[4]。管理系统负责处理流程实例的后勤工作,本身不执行任务。除业务过程的结构外,管理系统没有任何具体的应用特性。这样的体系结构分离了管理和执行,管理在进行路由决策时才参考流程实例属性,案例的属性在任务执行过程中改变,它并不属于管理的范畴,因此本文的流程建模并不涉及路由选择。
工作流管理系统在OA应用中有诸多优点,但并不是尽善尽美。笔者曾参与了西北工业大学基于SynchroFLOW平台的OA项目开发,开发过程中明显感到这样的问题:当一个应用模块(指流程定义及系统要提供的完成工作项所需的功能)完成后,若需求变更,致使流程变动,则模块的修改量会很大。这是一个很困扰开发人员的问题。而事实是:企事业单位的这种业务流程是频繁变动的,这导致的问题是:在所开发的系统投入使用后,维护会经常发生,而且花销很大。本文正是对这一问题做了一些探讨,提出了一个EN网的等价类划分,应用这个工具进行流程建模可以有效地减少流程模型的变动,并且在一定程度上使得系统使用人员无需技术人员参与便可维护系统。
2 基于基本Petri网系统(EN_系统)的流程描述
Petri网在1962年被Carl Adam Petri作为一种过程建模和分析的工具提出,它是一种图形化描述过程的有力工具,有着坚实的数学基础,是完全形式化的。目前针对Petri网的分析技术和工具已得到广泛发展。
为了便于后面的讨论,下面先给出基本Petri网系统的定义。
定义1 三元组N=(S,T;F)称为有向网(directed net),简称网(net)的充分必要条件是:
(1) S∩T=ϕ; (2) S∪T≠ϕ; (3) F⊆S×T∪T×S;
(4) dom(F)∪cod(F)=S∪T。
其中dom(F)={x|∃y:(x,y)∈F},cod(F)={y|∃x:(x,y)∈F}分别为F的定义域和值域。[5]
为便于讨论,引入术语:N=(S,T;F)为网,X=S∪T为其元素集。
定义2 设x∈X为N的任一元素,记:
·x={y|(y,x)∈F}
x·={z|(x,z)∈F}
让网N中的S_元素代表条件,T_元素代表事件,F代表流关系,则N为由条件和事件组成的网,通常表示为三元组(B,E;F),其中B为条件集,E为事件集。相应地,∀e∈E,·e为e的前条件集, e·为e的后条件集。
(B,E;F)上的一个状态体现为有些条件成真,有些条件不成真。因而可以用由成真的条件组成的B的子集表示状态,通常用小写字母c表示。
定义3 设c⊆B为网(B,E;F)的一个条件集。
(1) 事件e∈E在状态c有发生权的充分必要条件是·e⊆c∧ e·∩c=ϕ。e在c有发生权的事实记为c[e>,也说c授权e发生。
(2) 若e在c有发生权,即c[e>,则e可以发生,其结果是·e中的条件不再成真, e·中的条件则成真。换言之,e在c发生的结果是将状态c变为其后继状态c′,记作c[e>c′,其中c′=(c-·e)∪ e·。[5]
定义4 四元组=(B,E;F,cin)为基本网系统的条件是:(B,E;F)为条件和事件构成的有向网,cin为网上的状态,cin⊂B。
基本网系统简称EN_系统,cin称为它的初始情态。
网(B,E;F)很容易用图形表示,通常用圆圈表示条件,方框表示事件,带箭头的线段表示流关系。使用这种方式可以很直观地描述一个工作流过程,而且这种描述无论是对开发人员还是用户都是易于理解的,因而这种图形化的工作流程模型往往成为开发人员和用户沟通的工具。图2是一个高校校务活动安排的EN_系统模型,B={star,s1,s2,s3,s4,end},E={活动申请,协调,校领导批示,最终协调,接收通知,接收反馈},F={(star,活动申请),(s1,协调),…,(接收反馈,end)},cin={star}(图中代表star的圆圈中的黑点代表条件成真)。
synchroFLOW基本上支持这样的流程模型(只要稍作改变,图2的模型便是synchroFLOW上的一个正确模型),实际上模型中的循环只被执行一次,至于怎样控制,则是属于路由决策问题,由流程实例属性决定,本文不作讨论。
这种建模方式存在着模型更改困难和维护困难的问题,这一点上文已经提及。以图2流程为例,若实际工作流程有变更,需在“校领导批示”之前加一项工作“主任批示”,则开发人员要做的工作是:修改模型,为所增事件开发计算机支持的服务并进行配置,流程测试。据笔者亲历的经验,这种修改是比较麻烦的。
正是基于这个问题的考虑,本文对这种模型进行改进、优化。
3 模型优化
本文主要讨论的是办公自动化的工作流程建模,而办公自动化中的工作流程有其自身特点,其实质是用计算机仿真这样的流程:一份文件在办公人员中传来传去,相应的人员在文件相应的地方填写上相应的内容,直到整个流程完毕。这种情形下,每一个工作项的执行所需计算机支持的服务都是类似的,即是计算机把实际工作中的文件在屏幕上展现出来,办公人员在执行工作项时可以在相应地方填入相应内容。有了这样的基础,我们考虑,在用EN_网描述的工作流模型中(统称为原有模型),可以按一定的规则合并网中的一些事件,以简化模型。原有模型中若有如图3所示的子网,因为这样的网结构最简单,本文提出用另外的一种方式描述它,即是把它合并为一个事件,并在事件上加一个整数属性以表示它所代表原有事件的个数。通过这种合并,后面我们可以看到这样会在一定程度上解决上文提出的问题。
作为基础,本文提出一个定义,并形式化地描述这种合并以及合并带来的效果。
定义5 对(B,E;F),若不存在e1,e2∈E满足:
(1) |e·1|=|·e2|=1,(| e·1|,|·e2|分别代表 e·1,·e2的势)
(2) e·1=·e2
则称(B,E;F)为已简化网。
据此定义已简化网不存在图3所示的子网。
定义6 对EN_网(B,E;F),定义函数φ:E→N(N是自然数集合),称(B,E;F,φ)为扩展EN_网。任意的EN_网(B,E;F),其对应的扩展EN_网为:(B,E;F,η)。其中η满足:∀e∈E,η(e)=1。
定理1 任意的扩展EN_网N(B,E;F,η),对其进行如下操作,得到另一扩展EN_网N1(B1,E1;F1,φ),若∃e1,e2,…,en∈E(n∈N,n>1)满足:
(1) | e·1|=|·e2|=| e·2|=…=|·en-1|=|e·n-1|=|·en|=1;
(2) e·1=·e2, e·2=·e3,…, e·n-1=·en,则从E中删除e1,e2,…,en,加入e,并令·e=·e1, e·= e·n,φ(e)=n,而其余的e∈E,φ(e)=η(e)=1。B中删除 e·1, e·2,…, e·n-1。
则N1的基网(B1,E1;F1)为已简化网。
证明N(B,E;F)经过定理中的删除操作后显然满足定义5,证毕。
据定理1,可以得知每一个EN_网都存在着一已简化网与其对应。任一EN_网N(B,E;F),经由定理1中的操作后得到的N1(B1,E1;F1,φ),N和N1提供的信息信息量是一样的,就是说,它们的描述效果是一样的,因为N1的基网为已简化网,结构比N简单,本文提出用N1来代替N描述工作流过程。
令s(N)表示所有EN_网构成的集合。
定理2s(N)上的关系R,R={(x,y)|x,y∈s(N),x,y具有相等的已简化网}(本文没有定义网的相等,参考文献[6]),R为等价关系。
证明R显然是自反的,对称的和传递的,所以R为等价关系。
定理2给出了s(N)上的一个等价类划分,实际上它描述了用已简化网描述流程的能力,已简化网可以代替它所处等价类里的任一EN_网描述流程(这种代替是通过已简化网加上不同的φ构成扩展EN_网实现的),而且这种描述效果是等价的。
相应地,本文把N1(B1,E1;F1,φ)称为已简化扩展网,这是因为其基网(B1,E1;F1)为已简化网。
由定理1,图2的校务活动安排的EN_系统模型得到其相应的已简化扩展网模型如图4所示。
图中代表事件的方框中标上的整数为φ函数值,如:φ(组合事件1)=2,(组合事件2)=2,φ(组合事件3)=2.“组合事件1”的发生相当于原有模型中事件“活动申请”和“协调”的顺序发生,同理“组合事件2”和“组合事件3”也是一样。
直观地从图4看来,已简化扩展网模型在一定程度上简化了EN_系统模型,若实际工作流程变更,在已简化扩展网模型中的修改也相对方便。和上文的情形一样,若需在“校领导批示”之前加一项工作“主任批示”,开发人员只要把φ(组合事件2)的值从2变为3即可,这即意味着组合事件2的发生代表着三个事件顺序发生。因为每个工作项的执行所需计算机提供的服务都是一样的,因此开发人员不必为新增的事件开发新的服务,这样测试遇到的问题会相应减少,整个修改工作量比原来显著减少。
因为图4所示模型不易人员理解,所以有必要同时保存图2所示模型,前者为工作流系统所支持,而后者主要供人员理解整个流程。
4 结束语
已简化扩展网模型虽然优化了EN_系统模型,但这种优化只是在定理2划分的等价类范围内,只要EN_系统模型的修改超出等价类范围(改前的模型和改后的模型不属于同一等价类),已简化扩展网模型的修改量也是很大的。而以笔者参加开发西北工业大学党政办公自动化系统的经验看,模型的变更超出等价类范围例子不多,但也存在。还有一点,已简化扩展网模型并不通用,它只适用于办公自动化流程的建模。因而下一步的工作是对解决这两个问题进行研究,期望建立一个更优的模型。
摘要：介绍了基于EN网理论进行流程描述的模型,支持这种流程建模方式的工作流管理系统使得OA系统开发变得相对容易,但是存在着实际工作流程变更引起系统修改量大的不足。提出一种流程描述的优化模型,有效地解决此问题。
关键词：Petri,工作流,EN网,OA,工作流管理系统
参考文献
[1]Workflow Management Coalition.Workflow Reference Model,TC00-1003.Brusels,Belgium:Workflow Mamagement Coalition,1995.
[2]林慧苹,范玉顺,吴澄.支持企业经营过程重组的工作流仿真技术研究[J].信息与控制,2001,30(1):11-15.
[3]SychroFLOW协同工作流管理系统(版本3.2)用户手册.
[4]Wilvan der Aalst,Kees van Hee.工作流管理——模型、方法和系统.王建民,闻立杰,等译.清华大学出版社,2004.
[5]袁崇义.Petri网原理.电子工业出版社,1998.
Petri网络模型 篇8
关键词：工作流,工作流模型,Petri网,模型验证
1 工作流模型验证的意义
应用Petri网的分析技术对工作流模型进行验证的目的是在过程设计中检验工作流的正确性,避免执行时出现异常,过程异常包括死锁、死任务和活锁等。工作流建模是开发工作流管理系统的先行任务,所以在工作流投入使用之前就要进行很好的分析验证。如果一个工作流过程定义模型在其正确性、合理性没有得到充分验证时就投入使用,在工作流管理系统运行后再去进行修改,代价将远远高于前期的修改。因此在工作流模型实际实施之前,对其进行合理性分析,探索其中可能存在的各种过程异常,可以大大降低工作流运行时停产、检查和修复的成本,具有重大的意义[1]。
2 工作流网的合理性定义
工作流网的合理性定义是[1,3]:
一个工作流网PN=(P,T,F)建模的过程是合理的,当且仅当满足下面的三个条件:
1)对于每一个状态i可达的状态M,存在一个实施序列,从状态M肘通往状态o,形式化表示为:;
2)状态o是从状态i可达的唯一最终状态,且结束时其中至少会有一个标记,形式化表示为:;
3)在(PN,i)中没有死活动(不可能执行到的活动),形式化表示为:。
其中条件一是规定了从初始库所总能到达终止库所;第二个条件规定了当托肯转移到终止库所时,其他所有库所都要是空的,也就意味这整个工作流的结束;第三个条件是规定不能有死活动,即所有的活动都能得到执行。
3 工作流网模型的合理性验证算法
在研究分析各种文献的工作流网的合理性验证理论和方法的基础上,对原有的算法进行综合改编,使算法更容易被人所理解,总结出合理性算法的基本思路和验证步骤[1,2,5]。
算法的基本思路是:根据工作流网模型建立矩阵,用矩阵表示每个活动的前后顺序;根据模型表示出每个活动的前后库所,用来确定托肯转移时的向量表示规则;从初始库所出发,根据活动的前后库所和矩阵判断后续触发的活动,并重复此工作,直到没有活动变迁可以发生;如果终状态是形如(0,0,…,1)的终止状态(此时托肯存放在最后一个库所,其余所有库所中都没有托肯存在),并且所有的活动都触发过,托肯也经历了所有的库所,这时可以说改模型是合理的、正确的,否则模型中就存在错误。
在算法中要描述出状态从(1,0,0,…)到状态(0,0,…,1)的推算过程,并且要用另一个集合表示所执行的活动,最终检查是否合理的依据就是a、状态向量是否变成(0,0,…,1);b、表示活动的集合是否包含所有的活动。算法的具体描述为:
(1)用矩阵表示各个活动之间的前后顺序,方法如下:
(2)根据矩阵构造各个活动的输入库所集合和输出库所集合,用·t表示活动t的输入库所集合,用t·表示活动t的输出库所集合。构造方法是,矩阵t列中所有为1的元素的行号的前驱库所即t的输出库所集合;t行中所有为1的元素的列标的前驱库所即t的输入库所集合;没有前驱活动的活动的输入库所集合为起始库所i,没有后续活动的活动的输出库所集合为终止库所o。
(3)构造初始条件,初始条件有一个向量和一个集合,向量P0=(1,0,0,…),具体向量的维数是库所的个数,表示托肯在第一个库所内;集合T0为空,表示没有执行任何活动。
(4)根据活动t的输入库所集合·t和输出库所集合t·,更改向量P,并把活动t添加到集合T中,并根据矩阵判断下一个活动。
(5)反复进行执行步骤(4),直到没有活动可以执行且执行一遍所有活动。
4 总结
通过矩阵列举出活动序列,说明所有的活动都处于起始库所和终止库所之间,满足了合理性条件一;由于在列举活动序列时,序列中包含了所有活动,说明没有活动是死活动,满足了合理性条件三;演算的结果中向量P={0,0,0,0,0,0,0,0,0,1},证明在工作流结束时,托肯只存在于终止库所中,其他所有的库所中均不存在托肯,满足了合理性条件二。通过以上演算,证明了模型能够满足合理性定义中的三个条件,所以可以得出结论,此工作流模型是正确、合理的。[6]
参考文献
[1]郝文,王道平.基于Petri网的工作流建模合理性验证算法[J].计算机工程与应用,2008,44(13).
[2]van der Aalst W M P.The application of Petri nets to Workflow Management[J].The Journal of Circuits,Systems,and Computers,1998,8(1).
[3]袁崇义.Petri网原理[M].北京:电子工业出版社,1998.
[4]van der Aalst,W M P.Workflow Management:Models,Methods,and Systems[M].Boston:MIT Press,2002.
[5]周福明.基于Petri网的工作流建模与正确性分析[J].计算机科学,2005,32(2).
[6]李嶒.基于Petri网的工作流模型应用研究[D].合肥:安徽大学硕士论文,2008,28-29.