演算ps移花接木教程

收稿日期:2006-10-24;修返日期:2006-12-07基金项目:国家自然科学基金资助项目(60473078);北京市科技计划资助项目(Z0004029040811)作者简介:胡庆成(1977-),男,安徽濉溪人,硕士研究生,主要研究方向为电子政务、业务流程建模、模型检测、工作流等(hqc04@mails.
tsing-hua.
edu.
cn);邢春晓(1967-),男,教授,博士,主要研究方向为电子政务、数字图书馆、个性服务等;杨吉江(1968-),男,副教授,博士,主要研究方向为电子政务、企业建模等;李益民(1978-),男,湖南桃源人,硕士研究生,主要研究方向为软件工程、流程建模等.
基于PI-演算的网上并联审批业务流程建模及验证*胡庆成,邢春晓,杨吉江,李益民(清华大学计算机科学与技术系,北京100084)摘要:首次将进程代数PI-演算理论引入电子政务流程建模中,对电子政务研究中的热点、难点,即网上并联审批流程进行了形式化建模,并对所建立的模型进行了验证,确保了模型的正确性和可行性,极大地降低了项目实施投资风险.
关键词:电子政务;流程建模;模型验证;PI-演算;进程中图分类号:TP393.
09文献标志码:A文章编号:1001-3695(2007)12-0047-04BusinessprocessmodelingandverificationofcoordinatedexaminationandapprovesystembasedonPI-calculusHUQing-cheng,XINGChun-xiao,YANGJi-jiang,LIYi-min(Dept.
ofComputerScience&Technology,TsinghuaUniversity,Beijing100084,China)Abstract:ThispaperintroducedthePI-calculustheorytothefieldofprocessmodelingforthefirsttime,andcreatedanaccu-rateprocessmodelforcoordinatedexaminationandapprovesystembymeansofPI-calculustheory.
Finally,verifiedthisprocessmodelwiththemethodbasedonPI-calculustheory.
Andtheresultoftheverificationprovedthattheprocessmodelwasapplicableandefficientforcoordinatedexaminationandapprovesystem.
Keywords:e-government;processmodeling;modelverification;PI-calculus;process0引言近年来,世界各国在提倡和推进信息化战略中都把电子政务作为首要任务.
推进政府部门办公自动化、网络化、电子化已是大势所趋.
国内各级政府都在大力推进信息化建设.
政府的组织形态也正由职能型向服务型转变[1];政府的行政业务正由传统的方式向信息化方向转变.
中国政府的电子政务经过前期的投资建设已经具备了一定的硬件设施和软件环境.
但是政府各部门之间联合审批事项数据始终不能共享,这使得数据共享和协同工作成为我国电子政务发展过程中要解决的关键问题.
行政许可法的颁布给基于业务流程为核心驱动的跨部门联合行政审批带来了挑战和契机,跨组织、跨部门、跨区域的网上关联审批成为了目前研究的热点和难点.
网上并联审批是应用Web技术,把分布在不同部门、不同区域的已有、将有的政府信息资源迅速整合成为一种没有(或很少有)时间和空间的制约,以信息通信手段实现政府跨部门协作和统一审批的信息系统.
要实施网上并联审批系统第一步工作是根据应用要求设计业务流程,也称为流程建模.
要完成网上并联审批的电子化和网络化,准确地构建电子政府的业务模型是十分关键的一步.
流程建模合理与否决定政务项目的成败.
前期用于政府业务建模的技术有工作流图、UML[2]、Petri网、BPMS等.
UML是面向对象开发中的一种通用而又统一的图形化模型语言.
UML建模形式简单易懂,但缺乏形式化语义基础,模型检测性差.
工作流技术(workflow)早期主要用于描述工业及办公自动化,对工作过程约束条性太强,灵活性较差,较适用于一些相关规范、稳定不变的业务流程.
即使工作流管理联盟全新定义了工作流[3,4],但是大规模过程操作中隐含着错误[5].
Petri网技术具于丰富的语义定义、坚实的数学理论和直观的图形化界面,是目前构建工作流模型较为理想的建模方法[6,7].
但对于复杂系统的流程模型描述有一定的局限性[8].
BPM[9,10]被Smith、Fingar称为业务流程管理的第三次浪潮.
它是一种以规范化的构造端到端,以持续提高组织业务绩效为目的的卓越业务流程管理方法.
BPM的关键是将业务流程计算机模型化、标准化,将业务流程与业务应用相分离.
BPM的技术实现被称为业务流程管理系统(BPMS).
BPMS[11]的技术基础是工作流管理系统(WfMS)、企业应用集成(EAI)、电子商务等.
BPMS的理论基础是进程代数PI-演算[12~15].
PI-演算比传统工作流模型更加灵活、理论性更强,能描述复杂系统,支持结构变化的动态系统,提供安全控制,支持信息的异步并发性,将计算机的计算和通信两种基本功能进行统一,从而能协调分布式业务流程.
本文首次引入进程代数PI-演算理论到电子政务建模中,对复杂的、动态变化的、并发运行的网上并联审批系统进行了形式化建模,并对所建模型的合理性、可行性进行了分析验证;第24卷第12期2007年12月计算机应用研究ApplicationResearchofComputersVol.
24No.
12Dec.
2007确保了模型的正确性,避免了模型实施过程发现错误的修改周期长、代价大等缺陷,确保了政府部门项目的成功率,极大地降低了政府项目投资风险.
1PI-演算介绍PI-演算是R.
Milner等人在CCS[16]基础上的传名演算,可描述通信拓扑结构动态变化的分布式通信系统.
其独特之处在于允许进程之间传送和接收通道名,并且可以输入和输出局部名.
因此它不仅非常简洁,而且具有很强的表达能力.
在PI-演算中仅包含两类实体,一类是名字,通常理解为通道名;另一类是进程(流程),用来描述实际的业务流程应用系统.
进程间是通过名字进行交互的.
PI-演算与CCS、CSP等进程演算的主要区别是其交互的内容只包括名字.
其中通道、变量、数据、参数值等统称为名字.
这使PI更加简单通用.
1.
1PI的语法定义设N为名字集合[14,15],用x,y,z等小写字母表示名字集合上的名字;进程标志符用A,B,C等大写字母表示.
进程表达式用P,Q,R等大写字母表示.
进程表达式为以下几种方式之一:a)0表示空进程,没有任何行为.
b)前缀表达式α.
P,表示在完成动作α后执行P进程.
α主要完成三类动作为输入动作;xy.
P为输出动作,τ.
P为空动作.
其中为输入动作表示在端口x上接收任意名字z,然后执行进程为输出动作表示在端口x上发送名字y,然后执行进程P;τ.
P为空动作或哑前缀.
一般来说,τ表示内部进程通信活动,进程以外是不可见的.
c)选择进程表达式.
∑i∈IPi表示非确定性选择.
其中,索引集I为有限集.
I=0表示为空进程,即没有活动的进程.
如果P1+P2表示选择执行P1或P2进程.
d)并发合成表达式.
E1|E2表示可以并行执行或通过共享(通信)名进行交互.
e)约束进程表达式.
表示出现在元组x中的名字的作用域限定在进程P上,即外部动作被禁止,但是对于通过进程通道的内部通信是允许的.
f)匹配进程表达式.
[x=y]P表示仅当x与y是同名时,进程P可执行;否则为空进程.
g)进程标志符1,x2,…,xn)(或对每个进程标志符来说,必须有其定义1,x2,…,xn)∷=P.
其中x1,x2,…,xn是P中的自由名.
h)重复表达式.
!
P表示P的无穷次复制.
进程表达式可由如下BNF规则给出:P∷=0|||P1+P2|P|Q||[x=y]P|1,x2,…,xn)1.
2PI-演算中流程交互的结构PI-演算过程(流程)结构是流程活动实体通过通道端口与其他过程实体进行通信.
过程实体通过请求(request)作为输出,响应答复(reply)作为输入.
业务流程整个过程都是由过程实体输入、输出组成.
类似于IDEF[14]业务流程过程.
一个简单的交互模式图形表示如图1所示.
简单的交互模式形式化表达形式为Client(request,reply)=…request…reply….
一个连续交互流程形式为:Client(open,close,request,reply)=open.
request1.
reply1…requestn.
replyn.
close.
0.
图2是一个简单的PI-演算流程交互动作.
P进程沿着通道发出消息,Q进程从通道接收消息.
因PI-演算中通道名与动作名作为一个含义使用.
整个流程过程是动作y发出消息,理解为P进程沿通道y发出消息,而Q进程在同一通道y上接收消息.
图1简单的交互模式图2PI-演算流程图2PI-演算对网上并联审批系统建模目前,政府部门的业务主要分为单体型审批和并联型审批.
单体型审批指政府部门,如委办局,能够相对独立地对某项业务进行审批,而不涉及其他委办局.
并联型审批综合解决政府部门行政功能的局限性、地域的分散性、审批项目的多样性以及组织机构的非永久性等问题,并赋予其信息流通的快捷性和方便性,以使政府审批工作高效、稳定、公开,从而达到有利于改善投资环境,推动审批制度改革,方便法人、企事业办事,更好地体现服务性政府.
2.
1以企业设立为主体的并联审批业务流程即使相对简单的审批流程也可能包含复杂的交互过程.
网上并联审批的重点和难点是企业设立审批业务流程.
本文以企业设立网上并联审批流程系统为例,应用PI-演算对整个业务流程建立模型.
企业设立主要是以工商系统为业务驱动主线,"工商受理,抄告相关,并联审批,限期完成".
主要过程是企业申办人员提交相应的数据信息向工商系统提出企业设立申请;工商系统对企业名称预核准,有前置审批部门,先抄告前置审批部门审批.
当企业申办人员提供的数据信息及前置部门审核结果都符合条件时,由工商系统反馈接收企业登记注册申办请求,并根据业务流程同时并发地抄告给相关后置部门,如国税、地税、社保等部门.
各后置审批部门如国税部门审核办理后,将审批最终结果通知企业申办人员,如图3所示.
图3企业设立流程图2.
2建立企业设立的并联审批模型研究重点是应用PI-演算对并联审批流程建模及对其所建模型进行验证.
为了方便对整个并联审批过程进行简化,抽取·84·计算机应用研究第24卷动作(action)P进程(process)Q通道(channel)端口(port)requestreply10统计登记统计局9地税税务登记地税局1申请企业设立申请人4国有资产产权登记财政局8国税税务登记国税局11社保登记劳社局2企业名称预核准工商局5企业登记注册工商局6印章备案登记公安局7组织机构代码登记质监局名称预先核准通知书13办理结果申请人12国有资产产权登记财政局占有利用国有资产占有利用国有资产占有利用国有资产占有利用国有资产营业执照副本原件单位公章占有利用国有资产3前置审批前置审批单位:x(y).
P;x(z/y).
PP;x(y);x(y).
P:x(y)(vx)PA(x)),A(xA(x(vx).
P(x)y.
Px(y).
PA(x具有不同审批功能及代表性强的部分,省略了部分部门内部的流程及部分细节问题.
其逻辑结构如图4所示.
Request:企业申办人员向工商系统提出企业设立的申请(Req);AskInfo:工商系统要求提交企业设立相关的信息(Ask);MoreInfo:企业申办人员根据工商要求提交详细的信息,如公司名称、经营范围、法人代表、公司章程、公司地址、股东人员等与并联审批相关的信息(MInfo);CorrelationInfo:工商系统将数据信息抄告给相关的前置审批系统(CoInfo);CoReply:前置审批系统将审批结果信息反馈给工商系统(CoRe);Refusal:工商系统审核基本情况,如条件不符合将拒绝企业设立,并反馈给企业申办人员(Ref);Accept:工商系统接收到企业申办人员完整信息及正确的相关前置信息,符合申办条件,反馈接收办理请求.
ShareInfo:工商系统将符合设立条件的基础信息共享,并行或串行发给相关部门,如后置系统—国税系统(ShInfo);Shreply:国税系统接收到企业设立前提共享信息,反馈接收信息(Shre);Confirmation:国税系统向企业申办人员发出审核成功信息(Com);ComReply:企业申办人员领取最终的企业设立申办结果(ComRe).
2.
3应用PI-演算形式化描述并联审批模型PI-演算正是表述这种复杂业务流程信息交互的有效方式.
它可以清楚地表示出业务流程中信息传递行为.
但是将业务逻辑流程映射成PI-演算表达式时,需要将过程进行形式化抽象,但形式化建模过程需注意以下问题:抽象出业务流程中的参与进程;识别进程中使用的交互通信通道有哪些.
根据PI-演算相关语义定义及语法规则,将上述业务逻辑图抽象映射成PI-演算模型,如图5所示.
其中:x为申办人与工商系统之间的通道;z为前置审批系统与工商系统的通道;y为工商系统与国税系统(后置系统)的通道;w为国税系统与申办人的通道.
图4企业设立简化流程图图5PI-演算模型描述图与企业申办人员相关的通道及交互信息参数表示为u=Req,Ask,MInfo,Acc,Ref,Com,ComRe}.
以企业申办人员为主的进程在与其他进程通信交互的过程形式化表示如下:User(u)=x.
〈Req〉.
x(msg).
[msg=Ask]x.
〈MInfo〉x(msg2)([msg2=Ref]User(u)+[msg2=Acc]w(msg3).
[msg3=Com]w〈Com-Re〉.
User(u))类似地,建立前置审批系统、工商系统和国税系统流程相互交互模型如下:设前置审批系统:p=,CoInfo,CoRe},PrSystem(=y(msg).
[msg=CoInfo]y〈ReCo〉;工商系统:c={x,y,z,Req,Ask,MInfo,Ref,Acc,CoInfo,CoRe,ShInfo,ShRe},Coordinator(c)=x(msg).
[msg=Req]x〈Ask〉.
x(msg1).
[msg1=MInfo](x〈Ref〉.
Coordinator(c)+x〈Acc〉.
z〈CoInfo〉.
z(msg2)[msg2=CoRe].
y〈ShInfo〉.
y(ShRe).
Coordinator(c));国税系统:b={y,w,ShInfo,ShRe,Com,ComRE},PostSystem(b)=y(msg).
[msg=ShInfo].
y〈ShRe〉.
w〈Com〉.
w(msg1)[msg1=ComRe].
PostSystem(b).
可以看出,应用进程代数PI-演算可以充分、精确地形式化描述出企业设立的整个实际交互过程;进程及通道信息传递过程清晰.
3应用PI-演算验证网上并联审批模型应用形式化建模分析方法的目标是协助系统建模设计和逻辑验证.
PI-演算理论作为一种强大和成熟的形式化进程演算方法,可以详尽地描述动态交互的网上并联审批业务流程,利用PI-演算来推理整个系统的交互过程行为,验证所建模型的正确性、准确性、可行性等,从而能发现模型系统行为中的死锁性、活锁性、同步性、对等性等.
可支持PI-演算验证的工具有可执行的PIEPI、传值进程代数工具VPAM、JACK工具集、基于PI的语言PICT.
本文采用移动工作台(mobilityworkbench,MWB).
它是针对PI-演算开发的一个自动验证工具,可对用PI-演算、通信系统演算CCS描述的移动并发系统进行分析与验证.
MWB首先在瑞典的Uppsala大学计算机系开发.
MWB用标准ML语言设计,可在Windows、Linux等系统下的NewJerseySML编译环境中运行.
本文验证的软件环境是WindowsXP,StandardMLofNewJerseyv110.
57版,MWB'99版.
3.
1PI-演算形式化建模表达形式对应MWB编码为方便将PI-演算公式输入MWB系统,需将通常的PI-演算公式作一些相应表现形式的转换,如表1[11]所示.
表1PI-演算与工具MWB表达对照表MWB信息PI信息说明MWB信息PI信息说明^v约束tτ内部动作00空进程a(nlist)a.
(\nlist)输入前缀′aa输出动作′a〈nlist〉a.
[nlist]输出前缀3.
2验证所建模型根据规范将部分PI描述转换为MWB语法形式.
例如,对并联审批流程中企业申办人员向工商系统申请企业设立这个过程.
其中:为申办人为工商系统;x为申办人U与工商系统A之间的连接通道;a为Req;b为Ask;c为MInfo;d为Acc;e为Ref.
对于以企业申办人为主动进程来说,过程是企业申办人员在通道x上向工商系统提出申请,工商系统要求相关数据信息,申办人提供相应的数据信息,工商系统反馈给申办人符合条件接收申请或不符合拒绝办理.
它们通信交互的整个过程的表达形式如下:申办人员所对应的交互过程为agent=′x〈a〉′x〈c〉+;工商系统对应的交互过程为agent=′x〈b〉′x〈d〉+′x〈e〉;申办人与工商系统的整体通信交互过程为P=U|A.
根据以上描述,应用PI-演算对业务模型交互验证部分结·94·第12期胡庆成,等:基于PI-演算的网上并联审批业务流程建模及验证前置审批系统requestaskInfomoreInfoacceptrefusal工商系统correlationInfo国税系统shareInfoshreplycoReply企业申办人员wcomReply前置系统preSystem工商系统coordinator申办人user国税系统postSystemconfirmation{yp){x,w,.
A(x,a,b,c,d,e)).
A(x,a,b,c,d,e).
x(c).
(x(a).
A(x,a,b,c,d,e)x(e).
U(x,a,b,c,d,e)).
(x(d).
U(x,a,b,c,d,e).
x(b).
U(x,a,b,c,d,e);A(x,a,b,c,d,e)U(x,a,b,c,d,e)果如下:Themobilityworkbench(MWB'99,version4.
136,builtSunJul1613:00:512006)MWB>agentU(x,a,b,c,d,e)=′x〈a〉.
x(b).
′x〈c〉.
(x(d).
U(x,a,b,c,d,e)+x(e).
U(x,a,b,c,d,e))MWB>agentA(x,a,b,c,d,e)=x(a).
′x〈b〉.
x(c).
(′x〈d〉.
A(x,a,b,c,d,e)+′x〈e〉.
A(x,a,b,c,d,e))MWB>agentP=U|AMWB>deadlocksPNodeadlocksfound.
MWB>stepP……用死锁检验命令deadlocks检验流程P是否有死锁.
结果是没有死锁.
用交互模拟step命令运行流程P.
结果是流程P的每一步运行过程,如申办人与工商系统的通道是什么及通道上的信息是什么等.
这有利于分析、检查整个流程的每一步交互是否按设计过程在运行,等等.
在应用PI-演算理论对网上并联审批业务流程所建模型验证及推理过程、跟踪分析、检验业务流程中,发现了描述过程中不合理部分,修正后使模型更具有合理性、实用性,确保了项目的可行性,从而避免了模型实施后错误修改周期长、代价大等缺陷,极大地降低了政府项目投资风险,提高了项目的成功率.
4结束语政府网上并联审批业务流程系统是电子政务研究的热点方向.
本文首次把PI-演算理论引入到电子政府中来,为政府业务系统长远建设发展作了初步的探索.
PI-演算对政府网上并联审批业务流程的信息交互进行了精确的抽象描述,并对整个业务流程进行了验证,政府投资的风险大大降低了.
它为政府跨部门、跨区域信息交互提供了新的思路和方法.
下一步工作中,以PI-演算为理论基础开发业务流程图形化管理软件,将实现图形化描述与进程代数验证自动双向转换.
应用PI-演算等互模、强互模、弱互模、观察互模等理论,近一步分析及优化业务流程,从而推动电子政务的发展.
参考文献:[1]孟庆国,樊博.
电子政务理论与实践[M].
北京:清华大学出版社,2006.
[2]徐宝文,周毓明,卢红敏.
UML与软件建模[M].
北京:清华大学出版社,2006.
[3]GEORGAKOPOLOUSD,HORNICKM,SHETHA.
Anoverviewofworkflowmanagement:fromprocessmodelingtoworkflowautomationinfrastructure[J].
DistributedandParallelDatabases,1995,3(2):119-153.
[4]WorkflowManagementCoalition.
Workflowmanagementcoalitionter-minologyandglossary,WfMC-TC-1011[S].
Brussels:WfMC,1996.
[5]AALSTW.
FindingcontrolflowerrorsusingPetri-net-basetechniques[M]//AALSTW,DESELJ,OBERWEISA.
Businessprocessmangement:models,techniques,andempiricalstudies.
Berlin:Springer-Verlag,2000:161-183.
[6]李红臣,史美林.
工作流模型及其形式化描述[J].
计算机学报,2003,26(11):1456-1463.
[7]AALSTWvander.
HEEKvan.
工作流管理模型、方法和系统[M].
王建民,闻立杰,等译.
北京:清华大学出版社,2004.
[8]AALSTWMPvander.
PI-calculusversusPetrinets:letuseat"humblepie",ratherthanfurtherinflatethe"PIhype"[J].
BPTrends,2005,3(5):1-11.
[9]SMITHH,FINGARP.
Businessprocessmanagement:thethirdwave[M].
Tampa:Meghan-KifferPress,2003:1-312.
[10]SMITHH.
Businessprocessmanagement-thethirdwave:businessprocessmodelinglanguage(BPML)anditsPI-calculusfoundations[J].
InformationandSoftwareTechnology,2003,45:1065-1069.
[11]SMITHH,FINGARP.
WorkflowisjustaPIprocess[EB/OL].
(2004-01).
http:www.
bptrends.
com.
[12]MILNERR.
Communicatingandmobilesystems:theπ-calculus[M].
Cambridge:CambridgeUniversityPress,1999:1-161.
[13]MILNERR.
Thepolyadicπ-calculus:atutorial[M]//Logicandalge-braofspecification.
Berlin:Springer-Verlag,1993:1-50.
[14]SANGIORGID,WALKERD.
Theπ-calculus:atheoryofmobileprocesses[M].
Cambridge:CambridgeUniversityPress,2001:1-580.
[15]MILNERR,PARROWJ,WALKERD.
Acalculusofmobileproces-sesⅠ,Ⅱ[J].
InfComput,1992,100(1):1-40,41-77.
[16]MILNERR.
Communicationandconcurrency[M].
EnglewoodCliffs,NJ:PrenticeHallInternational,1989:1-260.
[17]陈禹六.
IDEF建模分析和设计方法[M].
北京:清华大学出版社,1999.
(上接46页)optimization[C]//Procofthe4thInternationalWorkshoponAntColonyOptimizationandSwarmIntelligence.
Brussels,Bel-gium:Springer-Verlag,2004:300-301.
[4]PEIJian,HANJia-wei,MAORun-ying.
Closet:anefficientalgo-rithmforminingfrequentcloseditemsets[C]//ProcoftheACMSIG-MODWorkshoponResearchIssuesinDataMiningandKnowledgeDiscovery.
Dallas,Texas:ACMPress,2000:21-30.
[5]ALUPOAEIS,KATKOORIS.
Antcolonysystemapplicationtomac-rocelloverlapremoval[J].
IEEETransonVeryLargeScaleInte-gration(VLSI)Systems,2004,12(10):1118-1122.
[6]GóMEZJF,KHODRHM,DeOLIVEIRAPM,etal.
Antcolonysystemalgorithmfortheplanningofprimarydistributioncircuits[J].
IEEETransonPowerSystem,2004,19(2):996-1003.
[7]HOLLANDJH.
Geneticalgorithmsinsearch,optimization,andma-chinelearning[M].
AnnArbor:MichiganPress,1975:1-57.
[8]MICHALEWICZZ.
Geneticalgorithms+datastructure=evolutionaryprograms[M].
NewYork:Springer-Verlag,1994:211-238.
[9]COLORNIA,DORIGOM,MANIEZZOV.
Distributedoptimizationbyantcolonies[C]//Procofthe1stEuropeanConferenceonArtifi-cialLife.
London:MITPress,1991:134-142.
[10]STüTZLET,HOOSHH.
Themax-minantsystemandlocalsearchforthetravelingsalesmanproblem[C]//ProcofIEEEInternationalConferenceonEvolutionaryComputation.
Piscataway:IEEEPress,1997:309-314.
[11]STüTZLET,HOOSHH.
Max-minantsystem[J].
FutureGenera-tionComputerSystem,2000,16(8):889-914.
[12]LINS.
Computersolutionstothetravelingsalesmanproblem[J].
BellSystemJournal,1965,44(10):2245-2269.
·05·计算机应用研究第24卷