一种跨组织业务流程死锁检测方法
|
摘要
跨组织的业务协作日趋频繁和紧密,由于参与组织具有分布性、局部自治性等特点以及组织间的协作关系的动态性、开放性、不确定性等特点,业务流程中含有相当部分的动态流程。一个结构合理且正确的业务流程模型是组织间顺利协作的重要保证。若不能尽早发现流程模型的错误,可能会带来重大的损失甚至需要付出很大的修复代价。因此,对跨组织业务流程模型进行验证是非常有必要的,而死锁检测是验证中非常重要的方面。尽管目前流程死锁检测已经取得了一定的研究成果,但相关的死锁检测方法都没有考虑运行时跨组织流程结构动态变化情境的死锁检测问题。
针对上述问题,本文在角色网络模型和面向死锁检测的流程约简规则的基础上,结合有向无环图(DAG)和Pi演算,提出了一种面向跨组织业务流程的死锁检测方法。本文所做工作主要包括：
(1)在角色网络模型和有向无环图(DAG)的基础上,提出了扩展的有向无环图(eDAG)。eDAG将角色网络模型突出行为主体的决策和适于动态业务流程的控制的能力与DAG显性描述业务流程的能力结合在一起,可以显性描述跨组织业务流程,特别是动态流程的结构。
(2)在已有的部分约简规则的基础上,基于eDAG,考虑流程中的动态流程,提出了支持动态流程的扩展约简规则。
(3)基于上述研究成果,结合Pi演算及其验证工具移动工作台MWB (Mobility Workbench),提出了一个跨组织业务流程死锁检测方法,以实现动态跨组织业务流程的死锁检测。
(4)在电子政务、电子商务以及应急管理领域,对所提出的死锁检测方法进行了实例验证。
相关研究在理论上补充和完善了现有死锁检测方法,且在电子政务,电子商务以及应急管理等领域的跨组织业务流程管理方面具有较为广阔的应用前景。
The business collaborations of organizations are much more frequent and close than before. There is considerable number of dynamic business processes in business process due to the participating organizations'distribution, local autonomy and the openness, the dynamic and uncertainty characteristics of cross-organizational collaborative relationships. A reasonable and correct business process model is important for collaboration between the organizations smoothly.
Business process modeling is very complex and error-prone. If the error of the process model can not be found early, it may lead to significant losses even need to pay great repair costs. Therefore, the effective validation of the process model is very necessary and deadlock detection is a quite important aspect for the validation. Although, there have been research works on deadlock detection methods for business processes and have got considerable achievement, the deadlock detection methods do not consider the deadlock detection under the context of the dynamic changes of the process structure at run time.
In response to these problems above, combined with to the acyclic graph(DAG) and Pi calculus, a deadlock detection method oriented cross-organizational business process is proposed based on Role Network Model and the process reduction rules for deadlock detection. The main contents in this paper are as follows:
(1) On the basis of the Role Network Model and directed acyclic graph (DAG), the extended directed acyclic graph (eDAG) is proposed to better describe the process side for cross-organizational business processes, especially the dynamic process structure.
(2) Considering the dynamic processes, the extended reduction rules are proposed supporting the dynamic processes on the basis of the part existing process reduction rules.
(3) Based on the researches above and combined with the Mobility Workbench, a deadlock detection method for the cross-organizational business process is proposed to achieve the deadlock detection for dynamic process.
(4) The deadlock detection method is validated through three case studies in E-government. E-commerce, as well as the emergency management respectively.
The related researches supplement and improve the existing deadlock detection methods in theory, and the researches have broad application prospects in the field of e-govemment, e-commerce, and the emergency management and other cross-organizational business process management aspects.
针对上述问题,本文在角色网络模型和面向死锁检测的流程约简规则的基础上,结合有向无环图(DAG)和Pi演算,提出了一种面向跨组织业务流程的死锁检测方法。本文所做工作主要包括：
(1)在角色网络模型和有向无环图(DAG)的基础上,提出了扩展的有向无环图(eDAG)。eDAG将角色网络模型突出行为主体的决策和适于动态业务流程的控制的能力与DAG显性描述业务流程的能力结合在一起,可以显性描述跨组织业务流程,特别是动态流程的结构。
(2)在已有的部分约简规则的基础上,基于eDAG,考虑流程中的动态流程,提出了支持动态流程的扩展约简规则。
(3)基于上述研究成果,结合Pi演算及其验证工具移动工作台MWB (Mobility Workbench),提出了一个跨组织业务流程死锁检测方法,以实现动态跨组织业务流程的死锁检测。
(4)在电子政务、电子商务以及应急管理领域,对所提出的死锁检测方法进行了实例验证。
相关研究在理论上补充和完善了现有死锁检测方法,且在电子政务,电子商务以及应急管理等领域的跨组织业务流程管理方面具有较为广阔的应用前景。
The business collaborations of organizations are much more frequent and close than before. There is considerable number of dynamic business processes in business process due to the participating organizations'distribution, local autonomy and the openness, the dynamic and uncertainty characteristics of cross-organizational collaborative relationships. A reasonable and correct business process model is important for collaboration between the organizations smoothly.
Business process modeling is very complex and error-prone. If the error of the process model can not be found early, it may lead to significant losses even need to pay great repair costs. Therefore, the effective validation of the process model is very necessary and deadlock detection is a quite important aspect for the validation. Although, there have been research works on deadlock detection methods for business processes and have got considerable achievement, the deadlock detection methods do not consider the deadlock detection under the context of the dynamic changes of the process structure at run time.
In response to these problems above, combined with to the acyclic graph(DAG) and Pi calculus, a deadlock detection method oriented cross-organizational business process is proposed based on Role Network Model and the process reduction rules for deadlock detection. The main contents in this paper are as follows:
(1) On the basis of the Role Network Model and directed acyclic graph (DAG), the extended directed acyclic graph (eDAG) is proposed to better describe the process side for cross-organizational business processes, especially the dynamic process structure.
(2) Considering the dynamic processes, the extended reduction rules are proposed supporting the dynamic processes on the basis of the part existing process reduction rules.
(3) Based on the researches above and combined with the Mobility Workbench, a deadlock detection method for the cross-organizational business process is proposed to achieve the deadlock detection for dynamic process.
(4) The deadlock detection method is validated through three case studies in E-government. E-commerce, as well as the emergency management respectively.
The related researches supplement and improve the existing deadlock detection methods in theory, and the researches have broad application prospects in the field of e-govemment, e-commerce, and the emergency management and other cross-organizational business process management aspects.
引文
[1]van der Aalst, W. M. P., M. Weske, and D. Grunbauer. Case handling:a new paradigm for business process support[j],. Data & Knowledge Engineering.2005,53(2):129-162.
[2]Ling H, Zhou J B. Research on Workflow Process Structure Verification[C]. Beijing: Proceedings of IEEE International Conference on e-Business Engineering,2005.
[3]王金朋.工作流建模方法及模型验证方法的研究[D].秦皇岛：燕山大学信息科学与工程学院,2009.
[4]谭支鹏.基于角色的工作流模型及其应用[J].小型微型计算机系统,2003,24(6)：1064-1066.
[5]李永亮.基于EFSM模型的软件故障检测与一致性测试生成研究[D].长沙：湖南大学计算机与通信学院,2009.
[6]胡海洋,吕建,马晓星,陶先平.面向对象范型体系结构中构件行为相容性研究[J].Journal of Software,2006,6(17):1276-1286.
[7]潘敏学,李倩,李宣东.死锁检测工具的能力分析与综合应用[J]. Journal of Frontiers of Computer Science and Technology,2010,2:153-164.
[8]李红臣,史美林,陈信祥.工作流系统中的业务过程描述及分析[J].计算机研究与发展,2001,38(7)：798-804.
[9]宋艳,高春鸣.基于移动工作台的BPEL4WS的死锁验证[J].计算机工程,2007,33(1):92-94,97.
[10]Li Zhang, Fei Xu, Zhiwei Yu. A Workflow Verification Method Based on Calculus[C]. First Joint IEEE/IFIP Symposium on Theoretical Aspects of Software Engineering (TASF.'07), 2007:188-196.
[11]B.F. van Dongen, J. Mendling, W. M.P. van der Aalst. Structural Patterns for Soundness of Business Process Models[C]. In EDOC'06:Proceedings of the 10th IEEE International Enterprise Distributed Object Computing Conference (KDOC'06),2006:116128.
[12]Ahmed Awad, Frank Puhlmann. Structural Detection of Deadlocks in Business Process Model s[C]. In Proceedings of the 11th Int'1 Conference on Business Infomat ion Systems ({BIS} 2008),2008:239-250.
[13]1. Tan, D Zheng, Q Gu, D Chen. The deadlock analysis of workflow model based on Petri Net[J]. Computer Science,2006,33(7):111-114.
[14]W.M. P vander Alast. Verification of Workflow Nets[C]. Proceeding of 18th Internal ion Conference, ICATPN'97, Toulouse, France,1997:327.
[15]Wang Jianliang, Xia Zhiwei, Yanan D. A Method for Soundness Verifical ion of Workflow Model Based on Petri-net[C]. Proceedings of the 4th International Conference on Computer Science and Education, Nanning, China,2009:880883
[16]周建涛,史美林,叶新铭.一种基于Petri网化简的工作流过程语义验证方法[J].软件学报,2005,16(7)：1242-1251.
[17]刘惠义,吴继锋,曾晓勤基于图规约法的TCPN工作流网模型的验证方法[J].系统仿真学报,2006,18(10)：2976-2983.
[18]Wenjie Sha, Li Zhang, Yahui Lu. Deadlock-free Solution in Collaborative Workflow Environment[C]. In Proceedings of the 2009 Fifth International Conference on Next Generation Web Services Practices,2009.
[19]Baoyi Wang, Shaomin Zhang, Qiaoli Xue. The Analysis on Grid Workf low's Deadlock by Petri Nets[C]. In proceedings of the 7th World Congress on Intelligent Control and Automation, pp.5432-5437,2008.
[20]赵磊,钱乐秋,赵文耘. 基于状态空间的工作流模型验证[J].计算机工程与应,2004,40(10)：220-222.
[21]Q Hu, C Xing, J Yang, Y LI. Business process modeling and verification of coordinated examination and approve system based on PI-calculus[J]. Application Research ofComputers,2007,24(12)：47-50.
[22]WASIM SADIQ, MARIA E. ORLOWSKA. Analyzing process models using graph reduction techniques[J]. Information Systems,2000,25(2):117-134.
[23]Hao Lin, Zhibiao Zhao, Hongchen Li, Zhiguo Chen. A Novel Graph Reduction Algorithm to Identify Structural Conflicts[C]. In proceedings of the 35th Annual Hawaii International Conference on System Sciences,2002.
[24]吴志燕.图形化工作流建模其正确性验证方法[D].南京：南京理工大学,2008.
[25]Han Shengju, Wang Ning, Yu Miao. Research on Role-Network Model for E-Government Affairs[j]. International Conference on Information Technology:Coding and Computing, 2005:438-442,
[26]Xin Ye, Xingkai Yang, Liming Zhu, Ning Wang, Jiangnan Qiu. Research of Government Horizon Business Integration Management System Based on HRNM and Agent[C]. Proceedings The 2006 IEEE/WIC/ACM International Conference on Web Intelligence and Intelligent Agent Technology Workshops,2006:558-561.
[27]叶鑫.基于角色网络理论的行政审批系统模型及其应用研究[D].大连：大连理工大学管理学院,2005.
[28]马俊锋.面向跨组织业务协作的角色网络模型研究[D].大连：大连理工大学管理与经济学部,2010.
[29]MilnerR, Par row J, Walker D. A calculus of mobi le processes, part I/II[J]. Information and Computation.1992,100(10):1-77.
[30]张静,王海洋,崔立真.基于Pi演算的跨组织工作流建模研究[J].计算机研究与发展,2007,44(7)：1243-1251.
[31]Johannes Borgstrom, Andrew D.Gordon, Andrew Phillips. A Chart Semantics for the Pi-Calculus[J]. Electronic Notes in Theoretical Computer Science,2008,194(2):3-29.
[32]Daniele Varacca, Nobuko Yoshida. Probabilistic π-Calculus and Event Structures[J]. Electronic Notes in Theoretical Computer Science,2007,190(3):147-166.
[33]Alan Jeffrey and Julian Rathke. Full abstraction for polymorphic Pi-calculus[J]. Theoretical Computer Science,2008,390(2):171-196.
[34]Naoki Kobayashi. A Type System for Lock-Free Processes[J]. Information and Computation, 2002,177 (2):122-159.
[35]Roberto M. Amadio. A synchronous Pi-calculus[J]. Information and Computation.2007, 205 (7):1470-1490.
[36]韩婷婷,陈韬略,颜锋等.同步和异步π演算的表达能力研究[J].高技术通讯,2005,15(8)：18-22.
[37]Roberto Lucchi, Manuel Mazzara. A pi-calculus based semantics for WS-BPEL[J]. The Journal of Logic and Algebraic Programming,2007,70(1):96-118.
[38]Claus Pahl. A Formal Composition and Interaction Model for a Web Component Platform[J]. Electronic Notes in Theoretical Computer Science,2002,66(4):1-15.
[39]陆汝钤.面向agent的需求分析[D].北京：中科院数学所,1999.
[40]焦文品,史忠植.形式化多主体系统中的交互及交互协议[J].软件学报,2001,12(08)：1177-1182.
[41]Chopra, A. K. Singh, M. P. Commitments for flex ible business processes. Autonomous Agents and Multiagent Systems[C],2004. AAMAS 2004. Proceedings of the Third International Joint Conference on.2004,3:1362-1363.
[42]王飞.基于Petri-Net与Pi-Calculus的BPM模型的研究与实现[D].合肥:中国科学技术大学2004.
[43]Shuailiang Ma, Li Zhang, Jimei He. Towards Formalization and Verification of Unified Business Process Model Based on Pi Calculus[C]. Proceeding of the Sixth Internation Conference on Software Engineering Research, Management and Application, Prague, Czech Republic,2008:93-101
[44]薛岗.基于Pi-演算的业务流程形式化建模研究[D].昆明：云南大学，2006.
[45]Lin Hui-Min. A verification tool for value-passing process algebras [J]. IFIP Transactions C-16:Protocol Specification, Testing and Verification,1993:79-92.
[46]牛光新.面向政务流程分析的角色网络模型研究[D].大连:大连理工大学管理学院,2008.
[47]B. Victor and P. Moller. The Mobility Workbench-a tool for the pi-calculus[C]. In D. Dill, editor, Proceedings of CAV'94, Lecture Notes in Computer Science. Springer-Verlag,1994.
[48]M. Dam. Model checking mobile processes[C]. In E. Best, editor, CON-CUR'93,4th Intl. Conference on Concurrency Theory, volume 715 of Lecture Notes in Computer Science,1993.
[49]Victor B., MollerF. The mobility workbench:A tool for the Pi-calculus[C]. Proceedings of the 6th International Conference on Computer Aided Verification,1994:428-440.
[50]Jianqiang Li, Yushun Fan. Reseach of Petri Net based workflow model reduction methods[J]. Information and control,2001,30(6):492-497.
[51]Lishu Fei, Qing Gu, Daoxu, Chen. A Process Definition Model and its Verification Analysis[J]. Computer Science,2004,31(1):145-151.
[52]Baoyan Song, Juying Wang, Ge Yu. Verification Method for Process Model Based on Graph-Spreading and Graph-Reduction[J]. Mini-Micro Systems,2005,26(6):1073-1078.
[53]Lida Xu, Huimin Liu, Song Wang and Kanliang Wang. Modeling and Analysis Techniques for cross-organizational workflow system[J]. Systems Research and Behavioral Science, 2009,3:367-389.
[2]Ling H, Zhou J B. Research on Workflow Process Structure Verification[C]. Beijing: Proceedings of IEEE International Conference on e-Business Engineering,2005.
[3]王金朋.工作流建模方法及模型验证方法的研究[D].秦皇岛：燕山大学信息科学与工程学院,2009.
[4]谭支鹏.基于角色的工作流模型及其应用[J].小型微型计算机系统,2003,24(6)：1064-1066.
[5]李永亮.基于EFSM模型的软件故障检测与一致性测试生成研究[D].长沙：湖南大学计算机与通信学院,2009.
[6]胡海洋,吕建,马晓星,陶先平.面向对象范型体系结构中构件行为相容性研究[J].Journal of Software,2006,6(17):1276-1286.
[7]潘敏学,李倩,李宣东.死锁检测工具的能力分析与综合应用[J]. Journal of Frontiers of Computer Science and Technology,2010,2:153-164.
[8]李红臣,史美林,陈信祥.工作流系统中的业务过程描述及分析[J].计算机研究与发展,2001,38(7)：798-804.
[9]宋艳,高春鸣.基于移动工作台的BPEL4WS的死锁验证[J].计算机工程,2007,33(1):92-94,97.
[10]Li Zhang, Fei Xu, Zhiwei Yu. A Workflow Verification Method Based on Calculus[C]. First Joint IEEE/IFIP Symposium on Theoretical Aspects of Software Engineering (TASF.'07), 2007:188-196.
[11]B.F. van Dongen, J. Mendling, W. M.P. van der Aalst. Structural Patterns for Soundness of Business Process Models[C]. In EDOC'06:Proceedings of the 10th IEEE International Enterprise Distributed Object Computing Conference (KDOC'06),2006:116128.
[12]Ahmed Awad, Frank Puhlmann. Structural Detection of Deadlocks in Business Process Model s[C]. In Proceedings of the 11th Int'1 Conference on Business Infomat ion Systems ({BIS} 2008),2008:239-250.
[13]1. Tan, D Zheng, Q Gu, D Chen. The deadlock analysis of workflow model based on Petri Net[J]. Computer Science,2006,33(7):111-114.
[14]W.M. P vander Alast. Verification of Workflow Nets[C]. Proceeding of 18th Internal ion Conference, ICATPN'97, Toulouse, France,1997:327.
[15]Wang Jianliang, Xia Zhiwei, Yanan D. A Method for Soundness Verifical ion of Workflow Model Based on Petri-net[C]. Proceedings of the 4th International Conference on Computer Science and Education, Nanning, China,2009:880883
[16]周建涛,史美林,叶新铭.一种基于Petri网化简的工作流过程语义验证方法[J].软件学报,2005,16(7)：1242-1251.
[17]刘惠义,吴继锋,曾晓勤基于图规约法的TCPN工作流网模型的验证方法[J].系统仿真学报,2006,18(10)：2976-2983.
[18]Wenjie Sha, Li Zhang, Yahui Lu. Deadlock-free Solution in Collaborative Workflow Environment[C]. In Proceedings of the 2009 Fifth International Conference on Next Generation Web Services Practices,2009.
[19]Baoyi Wang, Shaomin Zhang, Qiaoli Xue. The Analysis on Grid Workf low's Deadlock by Petri Nets[C]. In proceedings of the 7th World Congress on Intelligent Control and Automation, pp.5432-5437,2008.
[20]赵磊,钱乐秋,赵文耘. 基于状态空间的工作流模型验证[J].计算机工程与应,2004,40(10)：220-222.
[21]Q Hu, C Xing, J Yang, Y LI. Business process modeling and verification of coordinated examination and approve system based on PI-calculus[J]. Application Research ofComputers,2007,24(12)：47-50.
[22]WASIM SADIQ, MARIA E. ORLOWSKA. Analyzing process models using graph reduction techniques[J]. Information Systems,2000,25(2):117-134.
[23]Hao Lin, Zhibiao Zhao, Hongchen Li, Zhiguo Chen. A Novel Graph Reduction Algorithm to Identify Structural Conflicts[C]. In proceedings of the 35th Annual Hawaii International Conference on System Sciences,2002.
[24]吴志燕.图形化工作流建模其正确性验证方法[D].南京：南京理工大学,2008.
[25]Han Shengju, Wang Ning, Yu Miao. Research on Role-Network Model for E-Government Affairs[j]. International Conference on Information Technology:Coding and Computing, 2005:438-442,
[26]Xin Ye, Xingkai Yang, Liming Zhu, Ning Wang, Jiangnan Qiu. Research of Government Horizon Business Integration Management System Based on HRNM and Agent[C]. Proceedings The 2006 IEEE/WIC/ACM International Conference on Web Intelligence and Intelligent Agent Technology Workshops,2006:558-561.
[27]叶鑫.基于角色网络理论的行政审批系统模型及其应用研究[D].大连：大连理工大学管理学院,2005.
[28]马俊锋.面向跨组织业务协作的角色网络模型研究[D].大连：大连理工大学管理与经济学部,2010.
[29]MilnerR, Par row J, Walker D. A calculus of mobi le processes, part I/II[J]. Information and Computation.1992,100(10):1-77.
[30]张静,王海洋,崔立真.基于Pi演算的跨组织工作流建模研究[J].计算机研究与发展,2007,44(7)：1243-1251.
[31]Johannes Borgstrom, Andrew D.Gordon, Andrew Phillips. A Chart Semantics for the Pi-Calculus[J]. Electronic Notes in Theoretical Computer Science,2008,194(2):3-29.
[32]Daniele Varacca, Nobuko Yoshida. Probabilistic π-Calculus and Event Structures[J]. Electronic Notes in Theoretical Computer Science,2007,190(3):147-166.
[33]Alan Jeffrey and Julian Rathke. Full abstraction for polymorphic Pi-calculus[J]. Theoretical Computer Science,2008,390(2):171-196.
[34]Naoki Kobayashi. A Type System for Lock-Free Processes[J]. Information and Computation, 2002,177 (2):122-159.
[35]Roberto M. Amadio. A synchronous Pi-calculus[J]. Information and Computation.2007, 205 (7):1470-1490.
[36]韩婷婷,陈韬略,颜锋等.同步和异步π演算的表达能力研究[J].高技术通讯,2005,15(8)：18-22.
[37]Roberto Lucchi, Manuel Mazzara. A pi-calculus based semantics for WS-BPEL[J]. The Journal of Logic and Algebraic Programming,2007,70(1):96-118.
[38]Claus Pahl. A Formal Composition and Interaction Model for a Web Component Platform[J]. Electronic Notes in Theoretical Computer Science,2002,66(4):1-15.
[39]陆汝钤.面向agent的需求分析[D].北京：中科院数学所,1999.
[40]焦文品,史忠植.形式化多主体系统中的交互及交互协议[J].软件学报,2001,12(08)：1177-1182.
[41]Chopra, A. K. Singh, M. P. Commitments for flex ible business processes. Autonomous Agents and Multiagent Systems[C],2004. AAMAS 2004. Proceedings of the Third International Joint Conference on.2004,3:1362-1363.
[42]王飞.基于Petri-Net与Pi-Calculus的BPM模型的研究与实现[D].合肥:中国科学技术大学2004.
[43]Shuailiang Ma, Li Zhang, Jimei He. Towards Formalization and Verification of Unified Business Process Model Based on Pi Calculus[C]. Proceeding of the Sixth Internation Conference on Software Engineering Research, Management and Application, Prague, Czech Republic,2008:93-101
[44]薛岗.基于Pi-演算的业务流程形式化建模研究[D].昆明：云南大学，2006.
[45]Lin Hui-Min. A verification tool for value-passing process algebras [J]. IFIP Transactions C-16:Protocol Specification, Testing and Verification,1993:79-92.
[46]牛光新.面向政务流程分析的角色网络模型研究[D].大连:大连理工大学管理学院,2008.
[47]B. Victor and P. Moller. The Mobility Workbench-a tool for the pi-calculus[C]. In D. Dill, editor, Proceedings of CAV'94, Lecture Notes in Computer Science. Springer-Verlag,1994.
[48]M. Dam. Model checking mobile processes[C]. In E. Best, editor, CON-CUR'93,4th Intl. Conference on Concurrency Theory, volume 715 of Lecture Notes in Computer Science,1993.
[49]Victor B., MollerF. The mobility workbench:A tool for the Pi-calculus[C]. Proceedings of the 6th International Conference on Computer Aided Verification,1994:428-440.
[50]Jianqiang Li, Yushun Fan. Reseach of Petri Net based workflow model reduction methods[J]. Information and control,2001,30(6):492-497.
[51]Lishu Fei, Qing Gu, Daoxu, Chen. A Process Definition Model and its Verification Analysis[J]. Computer Science,2004,31(1):145-151.
[52]Baoyan Song, Juying Wang, Ge Yu. Verification Method for Process Model Based on Graph-Spreading and Graph-Reduction[J]. Mini-Micro Systems,2005,26(6):1073-1078.
[53]Lida Xu, Huimin Liu, Song Wang and Kanliang Wang. Modeling and Analysis Techniques for cross-organizational workflow system[J]. Systems Research and Behavioral Science, 2009,3:367-389.