排队系统的Petri网建模与验证
|
摘要
系统建模、验证和系统设计方案的确认是复杂分布式系统工程设计与建设中的重要研究议题。
排队系统和我们的生活息息相关,排队论正是为了研究这类问题而发展起来的。但是排队模型缺乏系统结构和动态逻辑行为的分析能力,而且难以描述包含多种不同类型的排队过程的系统和分析系统组件间的相互联系、制约、同步等现象。而这正是Petri网的强项。如何结合这两种分析方法成为研究的热点。本文提出了一种可行的方法。
本文首先对本文理论基础:排队网理论、Petri网理论、GSPN(Generalized Stochastic Petri Net,广义随机Petri网)理论,相关的仿真工具,以及文章后面的案例背景国防部体系结构框架(Department of Defense Architecture Framework:DoDAF)进行概要的介绍。然后给出一种比较成熟的排队网与Petri网结合的分层建模分析方法。
在论文的主体部分,给出了各种排队网基本结构的对应广义随机Petri网模型,实现排队模型向GSPN模型的转化,然后详细阐述了自己提出的另一种排队网和Petri网结合方法:排队系统的GSPN分析法。并且介绍为实现该方法而开发的一种Petri网仿真工具,以及软件框架设计和关键算法实现。
给出一个具体案例,用以阐明排队系统的GSPN分析法的使用,并通过建模仿真工具进行分析,得到系统的结构分析结果。最后在总结部分和成熟的分层分析法进行比较,阐述该方法的优缺点,同时给出缺点的解决方案和后续发展方向。
Modeling, verification of system, and validation of system design are important issues of designs or developments of the complicated distributed systems.
Queueing system has a deep relationship with our lives, and queueing theory is developed for researches of this systems. But queueing model is lack of the ability to analyze the system structure and the dynamic behaviors of the queueing system, and it's hard to describe the system that contains different kinds of queueing processes, and to analyze relations, restrictions and synchronizations between system components. And that is just the strength of Petri net. So, how to combine these two theories becomes the hot issue. This paper gives a feasible method.
At first, this paper gives a general description of queueing theory, Petri net, generalized stochastic Petri net (GSPN), related simulating tools, and the Department of Defense Architecture Framework (DoDAF), which is related to the case study. Then, shows a mature method of queueing netwok-Petri net-layered modeling.
In the principal part, this paper shows the equivalent GSPN models of kinds of essential queueing models, then, detailed describes the own method: queueing system's GSPN analyze, as well as the own Petri net simulation software developed for the method.
This paper shows a case to illustrate the queueing system's GSPN analyze, and simulates it with simulation tools, then gives the result of the structure queueing analyzes. In the end, there is a compare with the layered method, followed by a conclusion of their advantages and disadvantages, as well as the solving methods and developing ways of this problem.
排队系统和我们的生活息息相关,排队论正是为了研究这类问题而发展起来的。但是排队模型缺乏系统结构和动态逻辑行为的分析能力,而且难以描述包含多种不同类型的排队过程的系统和分析系统组件间的相互联系、制约、同步等现象。而这正是Petri网的强项。如何结合这两种分析方法成为研究的热点。本文提出了一种可行的方法。
本文首先对本文理论基础:排队网理论、Petri网理论、GSPN(Generalized Stochastic Petri Net,广义随机Petri网)理论,相关的仿真工具,以及文章后面的案例背景国防部体系结构框架(Department of Defense Architecture Framework:DoDAF)进行概要的介绍。然后给出一种比较成熟的排队网与Petri网结合的分层建模分析方法。
在论文的主体部分,给出了各种排队网基本结构的对应广义随机Petri网模型,实现排队模型向GSPN模型的转化,然后详细阐述了自己提出的另一种排队网和Petri网结合方法:排队系统的GSPN分析法。并且介绍为实现该方法而开发的一种Petri网仿真工具,以及软件框架设计和关键算法实现。
给出一个具体案例,用以阐明排队系统的GSPN分析法的使用,并通过建模仿真工具进行分析,得到系统的结构分析结果。最后在总结部分和成熟的分层分析法进行比较,阐述该方法的优缺点,同时给出缺点的解决方案和后续发展方向。
Modeling, verification of system, and validation of system design are important issues of designs or developments of the complicated distributed systems.
Queueing system has a deep relationship with our lives, and queueing theory is developed for researches of this systems. But queueing model is lack of the ability to analyze the system structure and the dynamic behaviors of the queueing system, and it's hard to describe the system that contains different kinds of queueing processes, and to analyze relations, restrictions and synchronizations between system components. And that is just the strength of Petri net. So, how to combine these two theories becomes the hot issue. This paper gives a feasible method.
At first, this paper gives a general description of queueing theory, Petri net, generalized stochastic Petri net (GSPN), related simulating tools, and the Department of Defense Architecture Framework (DoDAF), which is related to the case study. Then, shows a mature method of queueing netwok-Petri net-layered modeling.
In the principal part, this paper shows the equivalent GSPN models of kinds of essential queueing models, then, detailed describes the own method: queueing system's GSPN analyze, as well as the own Petri net simulation software developed for the method.
This paper shows a case to illustrate the queueing system's GSPN analyze, and simulates it with simulation tools, then gives the result of the structure queueing analyzes. In the end, there is a compare with the layered method, followed by a conclusion of their advantages and disadvantages, as well as the solving methods and developing ways of this problem.
引文
[1] Claude Gorault,Rudiger Valk. 系统工程 Petri 网——建模、验证与应用指南.(第一版). 王生原,余鹏,霍金键译. 北京:电子工业出版社,2005. 5-20
[2] 杨新华,林健. 并行离散事件仿真及其应用研究. 计算机仿真,2001,18(2):57-59
[3] 罗利春. 排队论的局限与排队模拟的数学本质. 中国空间科学技术,1994,(6):11-16
[4] 康牧宁,胡正国,叶军. Petri 网在程序正确性证明中的应用研究. 西北工业大学学报,1996,14(1):77-81
[5] 刘黎临,董占球. 计算机网络的建模与分析. 计算机学报,1996,19(6):409-420
[6] 陈斐松,蒋馥,王意冈. Petri 网在现代企业决策机制中的应用. 上海交通大学学报,34(11):1539-1544
[7] 林闯,李雅娟,王忠民. 性能评价形式化方法的现状和发展. 电子学报,2002,30(12A):1917-1922
[8] 冯惠军,冯允成. 仿真建模与形式化. 系统工程理论与实践,1995,(6):22-28
[9] Michael P. Bienvenu, Insub Shin, and Alexander H. Levis. C4ISR Architectures: III. An Object-Oriented Approach for Architecture Design. System Engineering, 2000, 3(4): 288-312
[10] Gianfranco Balbo, Steven C. Bruell, Subbarao Ghanta. Combining Queueing Networks and Generalized Stochastic Petri Nets for Solution of Complex Models of System Behavior. IEEE Transactions on Computers, 1988, 37(10): 1251-1268
[11] 孙晓颖,王万树,高电波. 排队系统的随机 Petri 网描述与分析. 长春邮电学院学报,1995,13(2):1-6
[12] 赵文. 排队论(随机服务系统理论)概述. 天津商学院学报,1995,(2):21-29
[13] 陆传赉. 排队论. 第一版. 北京:北京邮电学院出版社,1994 年 5 月. 102-122
[14] Kurt Jensen. An Introduction to the Theoretical Aspects of Coloured Petri Nets. Lecture Notes in Computer Science, 803: 230-272
[15] 徐树维,任小金. 基本 Petri 网:模型、特性和分析方法. 焦作工学院学报,2003,22(5):402-405
[16] 林闯,李雅娟,单志广. 基于随机 Petri 网的系统性能评价. 清华大学学报(自然科学版),2003,43(4):475-479
[17] 万和平. 工作流 Petri 网模型建模与分析评价方法研究:[硕士学位论文] .保存地点:华中科技大学图书馆,2005
[18] 秦益霖,刘坤. 基于随机 Petri 网的性能与可靠性评价. 工矿自动化,2004,(3):20-22
[19] 林闯. 随机 Petri 网和系统性能评价. 第一版. 北京:清华大学出版社,2000年 1 月. 74-85
[20] 胡健生,黄金志等. Petri 网时间特性分析. 计算机工程与设计,2005,26(11):2746-2748
[21] Henderson W, Taylor P. Embedded Processes in Stochastic Petri Nets. IEEE Transactions on Software Engineering, 1991, 17(2): 108-116
[22] 张建东,高晓光,吴勇等. GSPN 的分析方法及其应用. 火力与指挥控制,2005,30(5):27-31
[23] Giovanni Chiola, Marco Ajmone Marsan, Gianfranco Balbo. Generalized Stochastic Petri Nets: A Definition at the Net Level and Its Implications. IEEE Transactions on Software Engineering, 1993, 19(2): 89-107
[24] Ammer H, Islam S. Timed Scale Decomposition of a Cass of Gneralized Stochastic Petri Net Model. IEEE Tansactions on Software Engineering, 1989, 15(6): 802-820
[25] Giovanni Chiola, Marco Ajmone Marsan, Gianfranco Balbo, et al. Generalized Stochastic Petri Nets: A Definition at the Net Level and Its Implications. IEEE Transactions on Software Engineering, 1993, 19(2):89-107
[26] 吴维敏,董利达,苏宏业等. 基于抑止弧 Petri 网的离散事件系统的监控理论综述. 浙江大学学报(工学版),2003,37(1):42-46
[27] Insub Shin, Alexander H. Levis. Performance Prediction of Networked Information Systems via Petri Nets and Queuing Nets. Systems Engineering, 2003, 6(1): 1-18
[28] DoD Architecture Framework Working Group. DoD Architecture Framework Version 1.0, Deskbook. The United States: Department of Defense, 2004
[29] DoD Architecture Framework Working Group. DoD Architecture Framework Version 1.0, Volume I: Definitions and Guidelines. The United States: Department of Defense, 2004
[30] Lee W. Wagenhals, Insub Shin, Daesik Kim, et al. C4ISR Architectures: II. A Strctured Approach for Architecture Design. System Engineering, 2000, 3(4): 248-287
[31] 修胜龙, 罗雪山, 罗爱民等. C4ISR 体系结构描述的逻辑和行为验证. 系统工程与电子技术,2005,27(2):275-279
[32] DoD Architecture Framework Working Group. DoD Architecture Framework Version 1.0, Volume II: Product Descriptions. The United States: Department of Defense, 2004
[33] 汪亚男. 基于参数化网络类的统一 Petri 网研究与应用:[硕士学位论文]. 保存地点:华中科技大学图书馆,2005
[34] 黄勇,张友良,汪惠芬等. 基于广义随机 Petri 网的可视化建模与仿真工具. 计算机集成制造系统,2004,10(8):892-897
[35] 宫蓉蓉. 基于 Petri 网的可达树与可达图的构造与算法实现. 计算机与数字工程,2006,34(1):111-113
[36] 赵巍,潘泉,戴冠中等. 时间离散随机 Petri 网及其在指挥控制系统中的应用. 西北工业大学学报,2001,19(2):304-308
[37] 林闯,曲扬,郑波等. 一种随机 Petri 网性能等价化简与分析方法. 电子学报,2002,30(11):1620-1623
[38] 方贤文、吴哲辉、倪丽娜. 基于随机 Petri 网的乘积形式解存在的一个充分条件. 系统仿真学报,2003,(8):32-55
[39] Gerard Florin, Stephane Natkin. Generalization of Queueing Network Product Form Solutions to Stochastic Petri Nets. IEEE Transactions on Software Engineering, 1991, 17(2): 99-107
[40] Gianfranco Balbo, Steven C. Bruell, and Matteo Sereno. Product Form Solution for Generalized Stochastic Petri Nets. IEEE Transactions on Software Engineering, 2002, 28(10):915 - 932
[41] Matteo Sereno, Gianfranco Balbo. Computational Algorithms for Product Form Solution Stochastic Petri Nets. IEEE Transactions on Software Engineering, 1993, 18(2): 93-109
[42] G.Balbo, S.C.Bruell, M.Sereno. On the Relations between BCMP Queueing Networks and Product Form Solution Stochastic Petri Nets. In: Proceedings of the 10th International Workshop on Petri Nets and Performance Models, 2003. 53-62
[43] Lazar A, Robertazzi. Markovian Petri Net Protocols with Product form solution. Performance Evaluation, 1991, 12: 67-77
[44] Alexander H. Levis, Lee W. Wagenhals. C4ISR Architectures I: Developing a Process for C4ISR Architecture Design. Systems Engineering, 2000, 3(4):225-247
[2] 杨新华,林健. 并行离散事件仿真及其应用研究. 计算机仿真,2001,18(2):57-59
[3] 罗利春. 排队论的局限与排队模拟的数学本质. 中国空间科学技术,1994,(6):11-16
[4] 康牧宁,胡正国,叶军. Petri 网在程序正确性证明中的应用研究. 西北工业大学学报,1996,14(1):77-81
[5] 刘黎临,董占球. 计算机网络的建模与分析. 计算机学报,1996,19(6):409-420
[6] 陈斐松,蒋馥,王意冈. Petri 网在现代企业决策机制中的应用. 上海交通大学学报,34(11):1539-1544
[7] 林闯,李雅娟,王忠民. 性能评价形式化方法的现状和发展. 电子学报,2002,30(12A):1917-1922
[8] 冯惠军,冯允成. 仿真建模与形式化. 系统工程理论与实践,1995,(6):22-28
[9] Michael P. Bienvenu, Insub Shin, and Alexander H. Levis. C4ISR Architectures: III. An Object-Oriented Approach for Architecture Design. System Engineering, 2000, 3(4): 288-312
[10] Gianfranco Balbo, Steven C. Bruell, Subbarao Ghanta. Combining Queueing Networks and Generalized Stochastic Petri Nets for Solution of Complex Models of System Behavior. IEEE Transactions on Computers, 1988, 37(10): 1251-1268
[11] 孙晓颖,王万树,高电波. 排队系统的随机 Petri 网描述与分析. 长春邮电学院学报,1995,13(2):1-6
[12] 赵文. 排队论(随机服务系统理论)概述. 天津商学院学报,1995,(2):21-29
[13] 陆传赉. 排队论. 第一版. 北京:北京邮电学院出版社,1994 年 5 月. 102-122
[14] Kurt Jensen. An Introduction to the Theoretical Aspects of Coloured Petri Nets. Lecture Notes in Computer Science, 803: 230-272
[15] 徐树维,任小金. 基本 Petri 网:模型、特性和分析方法. 焦作工学院学报,2003,22(5):402-405
[16] 林闯,李雅娟,单志广. 基于随机 Petri 网的系统性能评价. 清华大学学报(自然科学版),2003,43(4):475-479
[17] 万和平. 工作流 Petri 网模型建模与分析评价方法研究:[硕士学位论文] .保存地点:华中科技大学图书馆,2005
[18] 秦益霖,刘坤. 基于随机 Petri 网的性能与可靠性评价. 工矿自动化,2004,(3):20-22
[19] 林闯. 随机 Petri 网和系统性能评价. 第一版. 北京:清华大学出版社,2000年 1 月. 74-85
[20] 胡健生,黄金志等. Petri 网时间特性分析. 计算机工程与设计,2005,26(11):2746-2748
[21] Henderson W, Taylor P. Embedded Processes in Stochastic Petri Nets. IEEE Transactions on Software Engineering, 1991, 17(2): 108-116
[22] 张建东,高晓光,吴勇等. GSPN 的分析方法及其应用. 火力与指挥控制,2005,30(5):27-31
[23] Giovanni Chiola, Marco Ajmone Marsan, Gianfranco Balbo. Generalized Stochastic Petri Nets: A Definition at the Net Level and Its Implications. IEEE Transactions on Software Engineering, 1993, 19(2): 89-107
[24] Ammer H, Islam S. Timed Scale Decomposition of a Cass of Gneralized Stochastic Petri Net Model. IEEE Tansactions on Software Engineering, 1989, 15(6): 802-820
[25] Giovanni Chiola, Marco Ajmone Marsan, Gianfranco Balbo, et al. Generalized Stochastic Petri Nets: A Definition at the Net Level and Its Implications. IEEE Transactions on Software Engineering, 1993, 19(2):89-107
[26] 吴维敏,董利达,苏宏业等. 基于抑止弧 Petri 网的离散事件系统的监控理论综述. 浙江大学学报(工学版),2003,37(1):42-46
[27] Insub Shin, Alexander H. Levis. Performance Prediction of Networked Information Systems via Petri Nets and Queuing Nets. Systems Engineering, 2003, 6(1): 1-18
[28] DoD Architecture Framework Working Group. DoD Architecture Framework Version 1.0, Deskbook. The United States: Department of Defense, 2004
[29] DoD Architecture Framework Working Group. DoD Architecture Framework Version 1.0, Volume I: Definitions and Guidelines. The United States: Department of Defense, 2004
[30] Lee W. Wagenhals, Insub Shin, Daesik Kim, et al. C4ISR Architectures: II. A Strctured Approach for Architecture Design. System Engineering, 2000, 3(4): 248-287
[31] 修胜龙, 罗雪山, 罗爱民等. C4ISR 体系结构描述的逻辑和行为验证. 系统工程与电子技术,2005,27(2):275-279
[32] DoD Architecture Framework Working Group. DoD Architecture Framework Version 1.0, Volume II: Product Descriptions. The United States: Department of Defense, 2004
[33] 汪亚男. 基于参数化网络类的统一 Petri 网研究与应用:[硕士学位论文]. 保存地点:华中科技大学图书馆,2005
[34] 黄勇,张友良,汪惠芬等. 基于广义随机 Petri 网的可视化建模与仿真工具. 计算机集成制造系统,2004,10(8):892-897
[35] 宫蓉蓉. 基于 Petri 网的可达树与可达图的构造与算法实现. 计算机与数字工程,2006,34(1):111-113
[36] 赵巍,潘泉,戴冠中等. 时间离散随机 Petri 网及其在指挥控制系统中的应用. 西北工业大学学报,2001,19(2):304-308
[37] 林闯,曲扬,郑波等. 一种随机 Petri 网性能等价化简与分析方法. 电子学报,2002,30(11):1620-1623
[38] 方贤文、吴哲辉、倪丽娜. 基于随机 Petri 网的乘积形式解存在的一个充分条件. 系统仿真学报,2003,(8):32-55
[39] Gerard Florin, Stephane Natkin. Generalization of Queueing Network Product Form Solutions to Stochastic Petri Nets. IEEE Transactions on Software Engineering, 1991, 17(2): 99-107
[40] Gianfranco Balbo, Steven C. Bruell, and Matteo Sereno. Product Form Solution for Generalized Stochastic Petri Nets. IEEE Transactions on Software Engineering, 2002, 28(10):915 - 932
[41] Matteo Sereno, Gianfranco Balbo. Computational Algorithms for Product Form Solution Stochastic Petri Nets. IEEE Transactions on Software Engineering, 1993, 18(2): 93-109
[42] G.Balbo, S.C.Bruell, M.Sereno. On the Relations between BCMP Queueing Networks and Product Form Solution Stochastic Petri Nets. In: Proceedings of the 10th International Workshop on Petri Nets and Performance Models, 2003. 53-62
[43] Lazar A, Robertazzi. Markovian Petri Net Protocols with Product form solution. Performance Evaluation, 1991, 12: 67-77
[44] Alexander H. Levis, Lee W. Wagenhals. C4ISR Architectures I: Developing a Process for C4ISR Architecture Design. Systems Engineering, 2000, 3(4):225-247
© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号 地址：北京市海淀区学院路29号 邮编：100083 电话：办公室：(+86 10)66554848；文献借阅、咨询服务、科技查新：66554700 |