任务关键系统的时间约束验证与最优路径分析

doi:10.19678/j.issn.1000-3428.0046855

计算机工程 ›› 2018, Vol. 44 ›› Issue (5): 60-65,77. doi: 10.19678/j.issn.1000-3428.0046855

任务关键系统的时间约束验证与最优路径分析

陈莹¹,孙晓波¹,邢建春 ¹,杨启亮^1,2

1.解放军理工大学国防工程学院,南京 210007; 2.南京大学计算机软件新技术国家重点实验室,南京 210093

收稿日期:2017-04-18 出版日期:2018-05-15 发布日期:2018-05-15
作者简介:陈莹(1991—),女,硕士研究生,主研方向为任务关键系统建模与分析;孙晓波,硕士研究生;邢建春,教授、博士生导师;杨启亮,副教授。
基金资助:
国家自然科学基金“基于声表面波的埋入式钢筋锈蚀传感器研究”(51505499);江苏省自然科学基金“面向开放环境的软件模糊自适应运行机理与构造方法”(BK20151451)。

Time Constraint Verification and Optimal Path Analysis of Mission Critical System

CHEN Ying¹,SUN Xiaobo¹,XING Jianchun¹,YANG Qiliang^1,2

1.College of Defense Engineering,PLA University of Science and Technology,Nanjing 210007,China; 2.State Key Laboratory for Novel Software Technology,Nanjing University,Nanjing 210093,China

Received:2017-04-18 Online:2018-05-15 Published:2018-05-15

摘要/Abstract

摘要： 针对任务关键系统工作流中对时间验证不够完善的问题,提出一种新的工作流建模和时间验证方法。基于库所含时间因素的着色时间Petri工作流网,将系统中的任务划分为关键任务和非关键任务,对不满足时间约束的活动进行管理,在完成最终任务的前提下,尽可能多地执行工作流中的非关键任务,从而减少时间资源的浪费。在此基础上,将工作流中活动的时间约束转化为数学约束问题,并运用MATLAB对模型进行分析,最终得出工作流中的最优路径。对军港岸基保障信息系统案例进行分析,结果表明,该方法具有一定的可行性和实用性。

关键词: Web服务组合, 任务关键系统, 时间验证, 最优路径, 着色时间Petri网

Abstract: Time verification is inadequate in workflows of Mission Critical System(MCS).To solve this problem,a new workflow modeling and time verification approach is proposed.Firstly,this approach divides the system tasks into mission critical ones and non-mission critical ones based on Place Containing the Time factor colored Petri-Workflow Net(PCTP-WFN),this can manage the activities which cannot meet the time constraint,and can execute non-mission critical tasks as many as possible on the premise of finishing the final tasks,which can thereby eliminate much wasted time in the MCS.Secondly,this approach transforms the time constraint of workflow activities into mathematical constraint,then uses MATLAB to analyze the models,and gets the optimal path finally.The example analysis of the shore-based facility security information system show that,the proposed approach is feasible and practicable.

Key words: Web service composition, Mission Critical System(MCS), time verification, optimal path, Colored Time Petri Net(CTPN)

中图分类号:

TP311.5

陈莹,孙晓波,邢建春,杨启亮. 任务关键系统的时间约束验证与最优路径分析[J]. 计算机工程, 2018, 44(5): 60-65,77.

CHEN Ying,SUN Xiaobo,XING Jianchun,YANG Qiliang. Time Constraint Verification and Optimal Path Analysis of Mission Critical System[J]. Computer Engineering, 2018, 44(5): 60-65,77.

https://www.ecice06.com/CN/Y2018/V44/I5/60

参考文献

［1］王涛.任务关键系统的软件行为建模与检测技术研究［D］.秦皇岛:燕山大学,2014.
［2］李琳,赵国生.基于Agent的可生存系统认知单元结构模型［J］.哈尔滨师范大学自然科学学报,2013,29(6):25-28.
［3］HINZ S,SCHMIDT K,STAHL C.Transforming BPEL to Petri nets［C］//Proceedings of the 3rd International Conference on Business Process Management.Berlin,Germany:Springer,2005:220-235.
［4］MONAKOVA G,KOPP O,LEYMANN F.Improving control flow verification in a business process using an extended Petri net［EB/OL］.［2017-03-25］.http://www.ceur-ws.org/Vol-438/paper15.pdf.
［5］FERRARA A.Web services:a process algebra approach［C］//Proceedings of the 2nd International Conference on Service Oriented Computing.New York,USA:ACM Press,2004:242-251.
［6］FOSTER H,UCHITEL S,MAGEE J,et al.Model-based verification of Web service compositions［C］//Proceedings of the 18th IEEE International Conference on Automated Software Engineering.Washington D.C.,USA:IEEE Press,2003:152-161.
［7］BREUGEL F V,KOSHKINA M,BREUGEL F V,et al. Models and verification of BPEL［EB/OL］.［2017-03-26］.http://www.cse.yorku.ca/~franck/research/drafts/tutorial.pdf.
［8］MARJANOVIC O.Dynamic verification of temporal constraints in production workflows［C］//Proceedings of the Australasian Database Conference.Washington D.C.,USA:IEEE Computer Society,2000:341-342.
［9］BETTINI B C,WANG X S,JAJODIA S.Temporal reasoning in workflow systems［J］.Distributed and Parallel Databases,2002,11(3):269-306.
［10］AALST W M,HOFSTEDE A H.Verification of workflow task structures:a Petri-net-baset approach［J］.Information Systems,2000,25(1):43-69.
［11］AALST W M.Process-aware information systems:lessons to be learned from process mining［C］//Proceedings of Transactions on Petri Nets and Other Models of Concurrency II.Berlin,Germany:Springer,2009:1-26.
［12］李丹,陈启璋,刘强.一种基于Petri网的时间工作流模型的研究与验证［J］.计算机工程,2007,33(7):78-80.
［13］罗智勇,汪鹏,尤波,等.逆向归约时间约束工作流准确率优化调度［J］.北京邮电大学学报(自然科学版),2017,40(1):99-104.
［14］LI Huifang,FAN Yushun.Workflow model analysis based on time constraint Petri nets［J］.Journal of Software,2004,15(1):17-26.
(下转第77页) (上接第65页) ［15］谭冠政,肖如健.基于Petri网的工作流时间动态预测及验证［J］.计算机测量与控制,2007,15(12):1801-1803.
［16］MERLIN P M.A study of the recoverability of computing systems［D］.Berkeley,USA:University of California,1974.
［17］林闯.随机Petri网和系统性能评价［M］.北京:清华大学出版社,2005.
［18］JUAN E Y T,TSAI J J P,MURATA T,et al.Reduction methods for real-time systems using delay time Petri nets［J］.IEEE Transactions on Software Engineering,2001,27(5):422-448.
［19］PEDRYCZ W,CAMARGO H.Fuzzy timed Petri nets［J］.Fuzzy Sets and Systems,2003,140(2):301-330.
［20］陈琨,韩燕波.基于Petri网的Web服务组合时间验证分析［J］.计算机工程与设计,2007,28(20):4938-4942.
［21］TANG X F.A Petri net-based semantic Web service automatic composition method［J］.Journal of Software,2007,18(12):2991-3000.
［22］朱连章,张乐伟,刘璐璐.基于赋时分层着色Petri网的以太网系统建模［J］.计算机工程与科学,2008,30(11):5-8.
［23］EDER J,PANAGOS E,POZEWAUNIG H,et al.Time management in workflow systems［M］.Berlin,Germany:Springer,2001:265-280.
［24］YANG Q,CHUANG L,WANG J Y.Linear temporal inference of workflow management systems based on timed Petri nets models［C］//Proceedings of the 1st International Conference on Engineering and Deployment of Cooperative Information Systems.Berlin,Germany:Springer,2002:30-44.
［25］TANG D,LIU D N.Method of reachability analysis in HTPN based workflow model［J］.Computer Integrated Manufacturing Systems,2006,12(4):487-493.
［26］SALIMIFARD K,WRIGHT M.Petri net-based modelling of workflow systems:an overview［J］.European Journal of Operational Research,2001,134(3):664-676.
［27］郭智奇.Petri网在井下机车调度中的建模与仿真［D］.合肥:合肥工业大学,2007.
［28］CHEN J,YANG Y.Temporal dependency based checkpoint selection for dynamic verification of fixed-time constraints in grid workflow systems［C］//Proceedings of International Conference on Software Engineering.New York,USA:ACM Press,2008:141-150.
［29］TSAI J J P,YANG S J,CHANG Y H.Timing constraint Petri nets and their application to schedulability analysis of real-time system specifications［J］.IEEE Transactions on Software Engineering,1995,21(1):32-49.
［30］杨启亮,李决龙,邢建春,等.需求自感知的军港岸基保障物联网系统［J］.国防科技,2014,35(2):56-62.

[1]	杨敏, 张玲华. WSN中基于区域感知的改进AODV路由协议[J]. 计算机工程, 2023, 49(8): 130-136.
[2]	刘蒙蒙, 牛保宁, 杨茸. 关键词最优路径查询的分段拓展算法[J]. 计算机工程, 2022, 48(6): 79-88.
[3]	荆霞, 周子韬, 王永利. 针对复杂多环网络拓扑的路由改进算法[J]. 计算机工程, 2022, 48(3): 154-161.
[4]	张鹏举, 贾永辉, 陈文亮. 基于多特征实体消歧的中文知识图谱问答[J]. 计算机工程, 2022, 48(2): 47-54.
[5]	刘庆周, 吴锋. 多智能体路径规划研究进展[J]. 计算机工程, 2020, 46(4): 1-10.
[6]	谭文安, 吴嘉凯. 基于改进花朵授粉算法的Web服务组合优化[J]. 计算机工程, 2020, 46(12): 67-72.
[7]	陈莹,邢建春,杨启亮,张孝鹏. 时间约束下任务关键系统的可调度性分析[J]. 计算机工程, 2018, 44(12): 115-119,128.
[8]	李靖,乔蕊,刘志中. 结合对策论与多目标MILP的Web服务组合调度问题求解[J]. 计算机工程, 2016, 42(1): 11-17.
[9]	朱琪,张会福,杨宇波,杨泉清. 基于减法聚类的合并最优路径层次聚类算法[J]. 计算机工程, 2015, 41(6): 178-182,187.
[10]	张诗悦,吴建德,王晓东,范玉刚,冷婷婷. 一种能耗均衡的无线传感器网络分簇路由算法[J]. 计算机工程, 2014, 40(8): 6-9.
[11]	李昌志,付晓东,田强,王威,夏永滢. 面向成本最小化的组合服务可靠性优化分配[J]. 计算机工程, 2014, 40(8): 253-258,263.
[12]	刘华鹏，刘胜全，刘艳，张华楠，李鹏. 基于主体和QoS的语义Web服务组合方法[J]. 计算机工程, 2013, 39(10): 227-231.
[13]	王曦, 张斌, 杨艳, 王娜. 基于IBAS的SAML路径验证协议[J]. 计算机工程, 2012, 38(10): 18-21.
[14]	李敬贤, 厉小润. 求解震后最优路径的改进Dijkstra算法[J]. 计算机工程, 2012, 38(06): 271-272.
[15]	王成良, 冯欣. 基于目标递进的Web服务组合方法[J]. 计算机工程, 2011, 37(6): 52-54.

选择文件类型/文献管理软件名称

选择包含的内容

任务关键系统的时间约束验证与最优路径分析

Time Constraint Verification and Optimal Path Analysis of Mission Critical System

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

模态框（Modal）标题

选择文件类型/文献管理软件名称

选择包含的内容

任务关键系统的时间约束验证与最优路径分析

Time Constraint Verification and Optimal Path Analysis of Mission Critical System

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价