基于解释Petri网的新型CPS分解方法  

New Decomposition Method for Cyber-Physical Systems Based on Interpreted Petri Nets

作　　者：陈宇浩 屠翰乾 相东明 CHEN Yuhao;TU Hanqian;XIANG Dongming(School of Computer Science and Technology,Zhejiang Sci-Tech University,Hangzhou 310018,China)

机构地区：[1]浙江理工大学计算机科学与技术学院,杭州310018

出　　处：《计算机科学》2025年第4期49-53,共5页Computer Science

基　　金：国家自然科学基金(62002328);浙江理工大学科研业务费专项资金(24232123-Y)。

摘　　要：Petri网被广泛应用于信息物理系统(Cyber-Physical Systems,CPS)的建模与分析,这些系统通常包含多个并发任务。为了简化CPS的实现过程,可将其分解成为若干独立组件。现有的CPS分解方法,如基于整数线性代数的算法,面临高时间复杂度问题;而依赖监控器的分解方法则存在较大的通信开销。为解决这些问题,综合现有分解方法的优势,提出了一种基于解释Petri网的CPS分解方法。该方法通过约束条件逐步分解网络,生成独立的状态机组件,有效缩小了模型规模。同时,提出了一种新的信号同步机制替代传统的监控器方案,显著降低了同步开销。实验结果表明,所提方法在大多数测试案例中的分解时间为O(n^(2)),远优于传统方法的指数级复杂度O(2^(n)),且生成的组件集合也更加简洁。Petri nets are widely used for the modeling and analysis of Cyber-Physical Systems(CPS),which typically involve multiple concurrent tasks.To simplify the implementation of CPS,these systems can be decomposed into several independent components.Existing CPS decomposition methods,such as algorithms based on integer linear algebra,suffer from high time complexity,while decomposition methods that rely on monitors incur significant communication overhead.To address these issues,this paper integrates the advantages of existing decomposition approaches and proposes a novel CPS decomposition method based on Interpreted Petri Nets(IPN).The proposed method incrementally decomposes the network using constraint conditions,generating independent State Machine Components(SMCs)to effectively reduce the model size.Additionally,a new signal synchronization mechanism is introduced to replace traditional monitor-based schemes,significantly reducing synchronization overhead.Experimental results demonstrate that the proposed method achieves a decomposition time complexity of O(n^(2))in most test cases,which is far superior to the exponential complexity O(2^(n))of traditional methods.Furthermore,the generated component set is more compact and efficient.

关 键 词：信息物理系统 PETRI网 状态机组件 可编程门阵列 系统分解 

分 类 号：TP306[自动化与计算机技术—计算机系统结构]