Petri网状态空间压缩与状态可达性检索研究

代理获取

页面导航

目录
摘要
著录项
相似文献
相关主题

摘要

现代社会存在大量的技术基础设施，其本质是由网络化动态系统组成，系统的动态行为表现为资源状态的流动和迁移。Petri网作为一种形式化建模分析工具，由于其直观性和并发性特点，广泛应用于计算机、自动化、机械等科学技术领域。 Petri网分析技术中，状态空间方法是一类重要的方法。同时，状态可达性是系统最基本的动态性质，系统的许多其他性质或问题诸如死锁、监督设计等都可等价到状态可达性问题上。但是，随着系统规模的增大，状态数量呈指数增长，产生状态空间爆炸问题，从而阻碍着Petri网应用的发展。本文基于Petri网状态空间数据的形式，将数据压缩与检索领域相关方法引入到Petri网状态约简与状态可达性判定问题研究中，实现对Petri网状态空间爆炸问题的缓解及状态可达性的准确快速判定。针对状态可达图生成过程中的状态数据存储问题，提出了缓存计算可达图的算法。通过设置一定大小的缓存区，算法在可达图数据生成过程中，对产生的状态数据进行动态存储，克服了传统算法中一次性生成整个状态空间数据带来的存储困难问题。针对Petri网状态空间压缩问题，结合Petri网状态数据连续变化冗余性以及局部数据突变性，提出一种基于混合编码的状态无损压缩算法。通过对当前编码元素局部差分值的计算，判定数据局部特点。在数据突变情形下采取预测编码模式并对最后的预测残差值采用golomb编码压缩方法，而在数据平稳变化的情形下采取传统的游程编码模式。算法既能实现对状态数据的极大程度压缩还能保证压缩后状态间特征无失真。针对Petri网状态可达性判定问题，由于经过压缩编码后的各状态数据维度不同，先对状态数据长度归一化预处理，并结合局部敏感哈希算法具有海量向量数据邻近查询的优势特点，提出一种基于局部敏感哈希算法的快速状态可达性检索算法。算法将编码空间的状态数据进行哈希编码，根据状态数据间距离相似程度，将状态数据分配至不同的哈希桶中。待检索数据同样哈希映射至距离相似的哈希桶中，同时在哈希桶中查询到与之最相似的状态数据。最终，采用二次精准检索的策略，通过索引结构，返回到待检索状态和已查询到的最相似状态各自哈希编码前的数据中，通过比对实现精准的状态快速可达性检索。最后，针对通用Petri网实例模型，验证了本文提出的状态空间压缩与状态检索算法。相比较其他的压缩与检索算法，本文算法具有较高的压缩效率并且能够最终实现准确快速的状态可达性检索。

著录项

作者
徐进;
展开▼
作者单位

西安电子科技大学;

展开▼
授予单位西安电子科技大学;
学科控制工程
授予学位硕士
导师姓名任获荣,高云升;
年度 2018
页码
总页数
原文格式 PDF
正文语种中文
中图分类计算技术、计算机技术;
关键词
Petri网; 状态空间; 压缩; 可达性;

相似文献

中文文献
外文文献
专利

1. 时间自动机可达性分析中的状态空间约减技术综述 [J] . 陈铭松 ,赵建华 ,李宣东 . 计算机科学 . 2006,第006期
2. 基于部分状态空间存储的Petri网库所界求解算法 [J] . 卢委红 ,丁志军 . 应用科学学报 . 2020,第005期
3. 一种价格时间Petri网的状态空间计算 [J] . 刘显明 ,李师贤 ,李文军 . 电子学报 . 2006,第010期
4. 分布式状态空间生成的有色petri网模型 [J] . 彭小东 ,陈莘萌 . 计算机工程与应用 . 2004,第012期
5. 基于状态空间等价类的有色Petri网特性验证 [J] . 李沛武 . 计算机工程与应用 . 2003,第011期
6. 可达性与状态方程可满足性等价的两个Petri网子类 [C] . 包云霞 ,鲁法明 ,曾庆田 . 第十一届全国Petri网理论与应用学术年会 . 2007
7. 基于t-不变量的Petri网状态空间压缩算法 [A] . 王荟雯 . 2015

Petri网状态空间压缩与状态可达性检索研究

目录

摘要

著录项

相似文献

相关主题

期刊订阅