基于有向无环图网格独立任务调度算法*

提出了基于有向无环图多约束网格环境下独立任务的调度模型,为其建立多约束线性规划模型,通过求解模型节点的优先级,获得网格各计算节点最优任务调度数;然后基于多约束最优任务调度方案,提出多约束带宽优先启发式算法(MCOPBHATS)和多约束计算速度优先启发式算法(MCOPCHATS)。实验结果表明,在多约束异构的网格环境下实现大量独立任务调度时, MCOPBHATS和MCOPCHATS算法的性能优于基于多约束最优任务调度方案的MinMin 算法。     

自适应组件副本选择模型及算法

提出了一个基于域的自适应副本选择模型DARSM(domain based adaptive replica selection model).该模型将组件副本划分为强一致性域和弱一致性域,域间通过一致性窗口机制进行状态同步.基于DARSM模型,给出了一种基于分区加权的自适应副本选择算法PWARS(partition-weighted based adaptive replica selection,).该算法利用动态性能度量信息来选择满足时间约束和一致性约束的组件副本集合.为了适应请求一致性约束的动态变化,还提出了一致性窗口自适应重配算法CWAR(consistency window adaptive reconfiguration).通过引入的一个一致性约束的可能性模型,该算法动态地对一致性窗口进行重配,从而实现了副本一致性的自适应控制.通过在OnceAS应用服务器集群中的原型实验及性能评价,表明该方法能够明显地提高副本选择的性能.     

基于Pareto最优的QoS路由算法

QoS路由是QoS框架中的重要组成部分,旨在寻找多约束条件下的可行路径.在解决多约束(MCP)问题时,引入了Pareto最优概念.基于此概念,提出了基于Pareto最优的QoS权重空间划分模型.在该模型中,根据路由请求与MCP问题解的关系,很容易判定路由请求是否能够被满足.在模型基础上,提出了用于解决具有两可加约束的动态权重系数路由算法PODWCA,它平均只需要运行2～3次,Dijkstra算法就能达到很高的性能.仿真结果验证了PODWCA算法的有效性.     

路径节点驱动的低代价最短路径树算法

Dijkstra算法是一个优秀的最短路径求解算法,同时也产生一棵最短路径树SPT(shortest path tree);该算法在网络计算与优化中得到了广泛的应用.为了对最短路径树进行代价优化,提出了路径节点驱动的思想.基于这种思想设计了路径节点驱动的最低代价最短路径树算法LCSPT(least-cost shortest path tree algorithm).通过LCSPT算法一个正计算节点能够最大化与当前最短路径树中的路径共享,因而进一步优化SPT树代价性能,生成高性能的SPT树.作为算法的重要组成部分,使用数学归纳法证明了算法的正确性;从理论上分析了LCSPT算法的代价性能,以及和同类算法相比如何取得最小代价性能;同时,对其时间复杂度和空间复杂度进行了分析.最后通过3个仿真实验验证了该算法在构建SPT时的正确性和其最小代价最短路径树特性.     

基于第二代Bandelet域隐马尔科夫树模型的图像分割

第二代Bandelet可以充分利用图像的内在几何正则性特点, 并能自适应获得图像的最优表示. 本文采用隐马尔可夫树(Hidden Markov tree, HMT)模型对图像的第二代Bandelet系数建模, 通过多尺度参数训练和基于上下文的最大后验概率进行图像分割. 为了评价本文方法的性能, 我们分别选择合成纹理图像、航拍图像和SAR图像进行实验, 并与小波域HMT模型分割方法(WD-HMTseg)和Contourlet域HMT模型分割方法(CHMTseg)进行比较说明算法的有效性. 实验结果表明本文方法不但在边缘准确性和区域一致性上有明显改进, 而且也降低了纹理图的错分概率.     

基于分布式协调模型的服务协作方法研究

由于服务是由彼此独立的提供商开发的,无法在开发阶段就预测到其潜在的所有交互可能,因此需要在实际协作时检查服务之间的兼容性,从而保障协作的正确性和一致性.提出了一种基于分布式协调模型的方法,以提高服务的可复用性和服务协作的灵活性.该方法通过失败等价(failure-equivalent)行为语义保持的投影规则,将协作流程转换为协作子流程,以实现分布式的成对兼容性检查,并提出基于适配的检查方法,检验服务是否可以通过适配机制满足兼容性的要求,同时给出了适配器自动生成的算法.适配机制的引入进一步降低了服务与协作环     

树型网格计算环境下的独立任务调度

任务调度是实现高性能网格计算的一个基本问题,然而,设计和实现高效的调度算法是非常具有挑战性的.讨论了在网格资源计算能力和网络通信速度异构的树型计算网格环境下,独立任务的调度问题.与实现最小化任务总的执行时间不同(该问题已被证明是NP难题),为该任务调度问题建立了整数线性规划模型,并从该线性规划模型中得到最优任务分配方案??各计算节点最优任务分配数.然后,基于最优任务分配方案,构造了两种动态的需求驱动的任务分配启发式算法:OPCHATA(optimization-based priority-computation heuristic algorithm for task allocation)和OPBHATA(optimization-basedpriority-bandwidth heuristic algorithm for task allocation).实验结果表明:在异构的树型计算网格环境下实现大量独立任务调度时,该算法的性能明显优于其他算法.     

数据约束模型的相似最优校准一致性分析

数据约束模型的一致性分析是业务流程管理的重要问题。已有的方法主要单一考虑流程模型的控制流方面。但是，对于一个模型而言，考虑数据流的时候可能是不一致的，所以应该结合数据信息的影响分析业务流程模型的一致性。基于相似最优校准的概念，根据算法计算出模型与日志的简化最优校准集，以便缩减已有方法所需的数量，然后映射校准移动到模型以确定模型行为不一致的区域，并添加控制节点进一步优化模型，最后通过具体实例验证该方法的可行性。     

Streett自动机确定化工具

自动机的确定化是将非确定性自动机转换为接收相同语言的确定性自动机,是自动机理论的基本问题之一.ω自动机的确定化是诸多逻辑,如SnS, CTL*,μ演算等,判定过程的基础,同时也是解决无限博弈求解问题的关键,因此对ω自动机确定化的研究具有重要意义.主要关注一类ω自动机——Streett自动机的确定化.非确定性Streett自动机可以转换为等价的确定性Rabin或Parity自动机,在前期工作中已经分别得到了状态复杂度最优以及渐进最优算法,为了验证提出的算法的实际效果,也为了形象地展示确定化过程,开发一款支持Streett自动机确定化的工具是必要的.首先介绍4种不同的Streett确定化结构:μ-Safra tree和H-Safra tree (最优)将Streett确定化为Rabin自动机, compact Streett Safra tree和LIR-H-Safra tree (渐进最优)将Streett确定化为Parity自动机;然后,根据Streett确定化算法,基于开源工具GOAL (graphical tool for omega-automata and logics),实现...     

基于FP-Tree有效挖掘最大频繁项集

最大频繁项集的挖掘过程中,在最小支持度较小的情况下,超集检测是算法的主要耗时操作.提出了最大频繁项集挖掘算法FPMFI(frequent pattern tree for maximal frequent item set)使用基于投影进行超集检测的机制,有效地缩减了超集检测的时间.另外,算法FPMFI通过删除FP子树(conditional frequent pattern tree)的冗余信息,有效地压缩了FP子树的规模,减少了遍历的开销.分析表明,算法FPMFI具有优越性.实验比较说明,在最小支持度较小时,算法FPMFI的性能优于同类算法1倍以上.     

Conformance checking based on multi-perspective declarative process models

Process mining is a family of techniques that aim at analyzing business process execution data recorded in event logs. Conformance checking is a branch of this discipline embracing approaches for verifying whether the behavior of a process, as recorded in a log, is in line with some expected behavior provided in the form of a process model. Recently, techniques for conformance checking based on declarative specifications have been developed. Such specifications are suitable to describe processes characterized by high variability. However, an open challenge in the context of conformance checking with declarative models is the capability of supporting multi-perspective specifications. This means that declarative models used for conformance checking should not only describe the process behavior from the control flow point of view, but also from other perspectives like data or time. In this paper, we close this gap by presenting an approach for conformance checking based on MP-Declare, a multi-perspective version of the declarative process modeling language Declare. The approach has been implemented in the process mining tool ProM and has been experimented using artificial and real-life event logs.     

基于Petri网的Web服务交互行为一致性检测方法

在复杂多变且不可预知的因特网环境中,Web组合服务的实际交互行为和它本身定义的规约之间的一致性是难以确保的。为了解决这个问题,提出了一种将服务组合实例的服务交互行为Petri网模型应用于交互行为一致性检测的方法。首先,提出了一个Web服务交互行为的运行时监控框架,从行为抽象和提取方法、服务交互行为的捕获机制以及交互行为一致性运行时检测方法三方面进行了详细介绍。还详细描述了基于服务交互行为Petri网模型的一致性检测机制。最后,对一致性检测方法的负载和性能进行了充分的评估。     

Translating Grafcet specifications into Mealy machines for conformance test purposes

Conformance test is a black-box test technique aiming at checking whether an implementation conforms to its specification. Numerous results have been already obtained in this field for specifications expressed in a formal language. However, these results cannot be applied for conformance test of industrial logic controllers whose specifications are given in standardized specification languages. To contribute to solve this issue, this paper proposes a method to obtain, from a Grafcet specification, an equivalent Mealy machine, without semantics loss. This method permits to describe explicitly and formally all the states and transitions that are implicitly represented in a Grafcet model.     

Conformance checking of processes based on monitoring real behavior

Many companies have adopted Process-aware Information Systems (PAIS) to support their business processes in some form. On the one hand these systems typically log events (e.g., in transaction logs or audit trails) related to the actual business process executions. On the other hand explicit process models describing how the business process should (or is expected to) be executed are frequently available. Together with the data recorded in the log, this situation raises the interesting question “Do the model and the log conform to each other?”. Conformance checking, also referred to as conformance analysis, aims at the detection of inconsistencies between a process model and its corresponding execution log, and their quantification by the formation of metrics. This paper proposes an incremental approach to check the conformance of a process model and an event log. First of all, the fitness between the log and the model is measured (i.e., “Does the observed process comply with the control flow specified by the process model?”). Second, the appropriateness of the model can be analyzed with respect to the log (i.e., “Does the model describe the observed process in a suitable way?”). Appropriateness can be evaluated from both a structural and a behavioral perspective. To operationalize the ideas presented in this paper a Conformance Checker has been implemented within the ProM framework, and it has been evaluated using artificial and real-life event logs.     

基于协议集成测试系统的IP v4协议一致性测试

TCP/IP协议实现的一致性测试是保证Internet网络设备之间互连与互操作的基础.该文基于协议集成测试环境进行了IP（Internet protocol）协议一致性测试研究和实际测试,并针对IP端系统和中继系统分别采用了分布式和远程横断式测试法,设计生成了IP一致性测试集.并且已将IP协议的一致性测试应用到路由器的开发和研制过程中.     

基于TTCN的ICMPv6的一致性测试

基于TTCN的协议的一致性测试是保证协议实现正确的重要方法.在介绍ICMPv6协议和TTCN标准的基础上,构建了一种基于TTCN标准的一致性测试系统.介绍了该测试系统的架构与工作原理,同时给出了ICMPv6一致性测试的方法和步骤,并在测试平台上执行了测试套.     

基于Artifact快照序列的行为一致性检测方法

Artifact行为的一致性检测,是在流程建模、运行之后亟待解决的关键问题之一.针对现有一致性检测技术忽略数据操作方面检测的问题,提出了一种基于Artifact快照序列的行为一致性检测方法.首先,利用全序Artifact快照序列定义了Artifact的行为模式,该行为模式不仅体现了服务的运行轨迹,也描述出了Artifact数据属性赋值的状态变化;然后,将Artifact行为一致性检测问题转换为语言可判定问题,证明了该问题是一个可判定问题,该过程中,设计一台判定该语言的图灵机作为一致性验证模型,该模型不仅检测了Artifact生命周期中服务路径的一致性,同时也检测了生命周期中Artifact属性赋值的正确性;进一步地,利用服务-快照关联矩阵的等价转换,给出了行为一致性量化指标中确切度的精确计算方法;最后,通过实例分析及实验对所提出的方法进行了验证.     

基于数据影响的业务流程一致性检查方法

近年来,业务流程的精确管理受到越来越多的关注,作为业务流程管理内容之一的一致性检查技术正变得越来越重要。现有的一致性检查技术主要从模型的控制流角度出发,并未考虑业务流程中的数据或数据的变化对业务流程产生的影响,为此提出了一种基于数据影响的业务流程一致性检查方法。首先,通过业务流程建模符号（business process modeling notation,BPMN）模型中数据和行为之间的依赖关系来分析数据对偏差活动预期行为的影响,进而获取偏差活动的预期行为集;其次,通过在BPMN模型中引入决策模型和符号（decision model and notation,DMN）决策表来充分捕获当前实例执行的数据上下文与行为上下文之间的关系,以区分有效数据更改和异常数据更改,找到偏差活动的有效预期行为集。最后,通过设计数据对偏差活动影响的各类成本函数提出了有效一致性检查方法。实验结果表明,相比已有工作,该方法在进行业务流程一致性检查时提高了业务流程的一致性,可以成功捕获偏差活动作出反应的适应行为,使得业务流程在复杂多变的环境下表现得更加准确、合理。     

基于模糊决策过程的模糊计算树逻辑模型检测

针对由数据表述产生的不确定性模糊系统的模型检测问题,给出模糊计算树逻辑模型检测算法。首先,引入模糊决策过程作为此类系统的模型,其最大特点是在迁移过程中对动作的不确定性选择和状态表述的模糊性。然后,在模糊决策过程基础上,给出模糊计算树逻辑的语法和语义。最后,给出模糊计算树逻辑模型检测算法,该算法是将模糊计算树逻辑模型检测问题转换为模糊矩阵的合成运算,其优势是时间复杂度低、计算过程较为简洁。     

表示层协议一致性测试的研究与实现

表示层协议是ＯＳＩ高层协议的一部分。文中介绍协议一致性测试的研究现状、测试过程及基本测试方法,分析表示层协议一致性测试需求;采用抽象语法表示（ＡＳＮ．１）与树表格式（ＴＴＣＮ）相结合的形式化描述语法,设计实现了表示层协议核心部分一致性测试系统及测试集;测试系统通过了对ＩＳＯＤＥ软件表示层协议实现的一致性测试。表示层协议一致性测试系统,是协议一致性测试系统（ＰＣＴＳ）的一个子系统。这个子系统的功能实