一种基于PETRI网的挖掘WS-CDL编排并行性的方法

摘要

本发明属于服务计算范式下的Web服务组合技术领域且公开了一种基于PETRI网的挖掘WS-CDL编排并行性的方法，1、基于PETRI网挖掘WS-CDL编排并行性的方法，按照以下步骤进行：步骤1，以WS-CDL编排作为输入文件，使用PETRI网对其进行描述，将其转换为基于PETRI网定义的编排。步骤2，从迹等价的角度，检验上述基于PETRI网定义的编排与WS-CDL编排间是否满足迹等价，若不满足，则视为步骤1的转换不成功，并返回步骤1对转换生成的PETRI网进行修改；若满足，则视为步骤1的转换成功，可进行步骤3；步骤3，对PETRI网定义的编排进行控制流关系和交互关系分析，计算依赖关系，构造依赖图，以寻找编排中可能的并行交互。

主权项

一种基于PETRI网的挖掘WS‑CDL编排并行性的方法，其特征在于，基于PETRI网挖掘WS‑CDL编排并行性的方法，按照以下步骤进行：步骤1，以WS‑CDL编排作为输入文件，使用PETRI网对其进行描述，将其转换为基于PETRI网定义的编排。步骤2，从迹等价的角度，检验上述基于PETRI网定义的编排与WS‑CDL编排间是否满足迹等价，若不满足，则视为步骤1的转换不成功，并返回步骤1对转换生成的PETRI网进行修改；若满足，则视为步骤1的转换成功，可进行步骤3；步骤3，对PETRI网定义的编排进行控制流关系和交互关系分析，计算依赖关系，构造依赖图，以寻找编排中可能的并行交互；步骤4，基于上述依赖图，重构PETRI网，使其串行的交互变为并行的交互，提高编排的效率。进一步的，所述步骤1中，由PETRI网构造器实现，包括分层转换和PETRI网的扁平化。进一步的，所述分层转换用于将WS‑CDL编排对应的层次树状结构转换为具有层次结构的PETRI网，其过程如下：1)采用宽度优先算法对WS‑CDL编排对应的层次树状结构进行扫描，将标记、和视为非叶子节点，并转换为PETRI网中的细化变迁，将标记视为叶子节点，并转换为PETRI中的原子变迁；2)将树状结构顶层内部非叶子节点和叶子节点间从左至右的全序关系转换为PETRI网中细化变迁和原子变迁间的顺序关系；3)树状结构最顶层内部最左非叶子节点或叶子节点所对应的细化变迁或原子变迁前增加一个开始库所，使之与该细化变迁或原子变迁相连，最右非叶子节点或叶子节点所对应的细化变迁或原子变迁后增加一个结束库所，使之与该细化变迁或原子变迁相连；4)建立树状结构上下层(顶层和次顶层)间的映射关系，若上层非叶子节点为标记或为标记或为标记，则下层建立与之对应的顺序结构子网或选择结构子网或并发结构子网，并建立子网与细化变迁间的对应关系；5)递归调用上述步骤2)、3)和4)转换树状结构的每个层，直至该层只有叶子节点结束；6)在开始库所中添加1个托肯。进一步的，所述PETRI网的扁平化用于将具有层次结构的PETRI网转换为平面(不具有层次结构)PETRI网，其过程如下：1)将上层细化变迁及其前集间的流关系，赋予给下层对应子网的开始变迁(细化变迁或原子变迁)；2)将上层细化变迁及其后集间的流关系，赋予给下层对应子网的结束变迁(细化变迁或原子变迁)；3)递归调用上述步骤1)和2)，直至具有层次结构的PETRI网中该层没有下层结构。进一步的，所述步骤2中，由转换检验器实现，包括：生成消息序列和迹(trace)比较。进一步的，所述生成消息序列用于从WS‑CDL编排中按控制流关系提取消息的发送和接受序列，其过程如下：1)采用深度优先算法对WS‑CDL编排对应的层次树状结构进行扫描，以标记…作为原子交互单元，从其内部的标记和中提取消息的发送动作和接收动作；2)将标记间从左至右间的控制流关系转换为消息动作间的前后关系。进一步的，所述迹比较用于从将上述生成的消息序列同PETRI网点火生成的变迁序列进行比较，其过程如下：1)在点火规则的指导下，将步骤1中生成的PETRI网，记录其开始库所到结束库所间的所有变迁点火序列；2)若该变迁点火序列同上述消息序列相同，则视为满足迹等价，反之，则不满。进一步的，所述步骤3中，由依赖图构造器实现，包括：控制流关系及交互关性分析和生成依赖图。进一步的，所述控制流关系及交互关性分析用于对PETRI网变迁间的依赖关系进行分析，其过程如下：1)计算PETRI网变迁间的控制流关系，对任意两个变迁t1和t2，若满足：t1的后集与t2的前集的交不为空，则t1和t2视为控制流相关，反之，则不满足控制相关；2)计算PETRI网变迁间的交互关系，对任意两个具有控制相关的变迁t1和t2，若满足：t2的发送者是t1的发送者或接收者，则t1和t2视为交互相关，反之，则不满组交互相关；3)对任意两个变迁t1和t2，若满足：t1和t2间既满足控制流关系又满足交互依赖关系，则t1和t2视为依赖相关，反之，则不满足依赖相关；进一步的，所述生成依赖图的目的是使用图直观表示PETRI网变迁间的依赖关系，其过程如下：基于上述的依赖关系，以变迁作为节点，以依赖关系中的元素为弧，生成依赖图。进一步的，所述步骤4中，由PETRI网重构器实现，用于将上述生成的依赖图转换为一个PETRI网，其过程如下：1)依赖图中相邻两个节点v1和v2，若的v1出度为1及v2的入度为1，则将v1和v2转换为PETRI网的变迁t1和t2，且t1和t2间满足顺序关系；2)依赖图中相邻三个节点v1、v2和v3，若的v1出度为2及v2和v3的入度为1，则将v1、v2和v3转换为PETRI网的变迁t1、t2和t3，且t1与t2间、t1与t3间满足顺序关系，t2和t3间满足选择关系；3)2)依赖图中相邻三个节点v1、v2和v3，若的v3入度为2及v1和v2的出度为1，则将v1、v2和v3转换为PETRI网的变迁t1、t2和t3，且t1与t3间、t2与t3间满足顺序关系，t1和t2间满足选择关系。