基于拓扑序列归约的Web服务组合QoS度量算法

考虑有向无环图 (DAG)描述的组合服务模型,提出了一种新的组合服务QoS度量方法--基于拓扑序列归约的Web服务QoS度量方法（QCMTSR）。其借鉴迭代归约度量方法中的基本结构及QoS计算公式,定义了DAG图中的两类基本结构,串归约结构和并归约结构,并给出了两种基本结构的QoS属性计算公式;通过逐步归约DAG图拓扑序列中的每个节点,直至最后一个节点的QoS属性值就是组合服务的各QoS属性的度量结果。从理论上证明了QCMTSR算法适用于所有DAG描述的组合服务,并实验证明QCMTSR算法对可靠性和可用性能够更准确的度量。     

MTS自动事务一致性仿真测试

MTS（Microsoft Transaction Server：微软事务服务器）是Microsoft基于组件的三层C／S（Client/Server:客户机／服务器）结构的核心部件。虽然它提供了自动事务管理机制,但由于应用系统中组件之间相互关系复杂,所以设计开发人员很难在设计阶段恰当地处理组件事务特征的一致性。文中提出了组件事务特征一致性测试的仿真算法,并通过具体实例说明该算法的有效性。     

异构分布式系统中一种新型主副版本调度算法

针对异构分布式系统中处理器数量相对较少时优先级约束条件带来的副版本调度易失败问题，提出一种新型高可靠性主副版本调度算法（HRPB）。任务模型以有向无环图（DAG）表示，该算法共计调度主、副两个版本的任务。在任务优先级排序阶段，根据任务执行时间及截止时限来制定新指标平均最晚开始时间（ALST）进行排序；在任务处理器分配阶段，采取多一重备份策略以解决处理器数量相对较少时优先级约束条件带来的副版本调度易失败问题，并且改进了副版本调度时的可靠性指标计算方法。通过随机生成DAG图进行算法仿真测试，实验结果表明，HRPB比eFRD具有更优的副版本调度成功率、更高的系统可靠性。     

网格任务调度方法研究

网格计算中的关键问题之一是计算任务在各个资源之间的调度。提出了基于量子遗传算法（QGA）的网格任务调度算法,以减少调度时间为主要目标,增加资源利用率为次要目标。该算法采用量子比特间接编码的方式,通过有向无环图（DAG）来描述子任务间的依赖关系,根据深度值来给子任务的执行顺序进行排序。仿真结果显示,无论是任务完成时间还是资源利用率,此方法都明显优于基于遗传算法（GA）的网格调度算法。     

一种媒体流穿越NAT的算法设计与实现

基于交互式连通建立草案协议,综合运用网络地址转换（NAT）会话穿越工具和中继穿越工具,设计一个媒体流穿越NAT的算法实例。使用请求/应答交互方式,探索通信双方NAT拓扑部署,通过排序算法找到并选择一条最优的传输路径。在Linux下进行编程测试,能使媒体流较好地穿越不同拓扑部署的NAT。     

混合自适应粒子群工作流调度优化算法

针对具有截止期的云工作流完成时间与执行成本冲突的问题,提出一种混合自适应粒子群工作流调度优化算法（HAPSO）。首先,基于截止期建立有向无环图（DAG）云工作流调度模型;然后,通过范数理想点与自适应权重的结合,将DAG调度模型转化为权衡DAG完成时间和执行成本的多目标优化问题;最后,在粒子群优化（PSO）算法的基础上引入自适应惯性权重、自适应学习因子、花朵授粉算法的概率切换机制、萤火虫算法（FA）和粒子越界处理方法,从而平衡粒子群的全局搜索与局部搜索能力,进而求解DAG完成时间与执行成本的目标优化问题。实验中对比分析了PSO、惯性权重粒子群算法（WPSO）、蚁群算法（ACO）和HAPSO的优化结果。实验结果表明,HAPSO在权衡工作流（30～300任务数）完成时间与执行成本的多目标函数值上降低了40.9%～81.1%,HAPSO在工作流截止期约束下有效权衡了完成时间与执行成本。此外,HAPSO在减少完成时间或降低执行成本的单目标上也有较好的效果,验证了HAPSO的普适性。     

利用遗传算法改进DAG绘制的方法

DAG图（Directed Acyclic Graph）广泛应用于数据库建模、工程设计等领域。DAG图一般用矩阵来存储,能够将矩阵存储的DAG图正确、美观地画出来,使得DAG图更直观,清晰,方便各种问题的分析和处理。DAG图的绘制包含分层、最小化边交叉数和删除哑结点。提出了基于遗传算法的分层和最小化边交叉数的方法和删除哑结点的启发式算法。实例结果表明提出的方法能有效解决DAG图绘制中的交叉点问题。     

Modelica建模软件中拓扑排序相关算法研究

为了提高现有OpenModelica软件对DAE系统的预处理模块中求强连通分量与拓扑排序部分的性能,提出了基于Kosaraju算法实现的策略.阐述了Modelica软件的实现原理,叙述了拓扑排序相关算法在其中的重要性,分析了现有Modelica 软件中使用的求强连通分量与拓扑排序部分的算法,比较了Tarjan算法的实现方案与Kosaraju算法实现方案.对两种方案进行了比较和分析结果,表明了Kosaraju算法方案的可行性和有效性.     

基于属性度的属性排序算法

形式概念分析是一种从形式背景进行数据分析和规则提取的强有力工具。属性拓扑作为一种新型的形式背景表示方法,直观地描述了属性之间的关联。利用属性拓扑可以更方便直观地计算形式概念和概念格。经过对现有属性拓扑的算法与流程的研究,分析了现有属性排序算法的特异性和层次局限性,通过结合度的概念,提出了一种属性衡量的新方式--属性度,并提出了基于属性度的属性排序算法。这种排序算法得到的结果更加灵活,消除了属性排序的层次局限性,对父属性的查找有明显的优势,为基于属性拓扑中的属性排序方法提供了指引方向。     

拓扑排序和强连通算法在源代码分析中的应用

缺少文档的开源项目和文档不完整的开源项目,分析其源代码是了解其运行机理的主要方法,本文提出一种基于函数分析顺序的分析方法,并且提出构建函数分析顺序的过程。过程为首先使用强连通算法消除函数递归调用,得到一些组件,再用拓扑排序对组件和组件内部的各函数节点排序,得到一个分层链表,该链表包含各函数的调用顺序和分析顺序,再用一种展开算法将分层链表展开,最终得到源代码中的函数分析顺序。     

Topological sorts on DAGs

In this article, we will study the topological sorts of two directed acyclic graphs (DAGs) and the associated properties. More specifically, we will study under what conditions a certain single (or some, or every) topological sort(s) of a DAG can be extended into the topological sort(s) of another DAG. We first give the necessary and sufficient conditions for the problems. We then indicate that these problems are solvable either in linear time cost or in the same time cost as to compute the transitive closure.     

动态拓扑排序途径的XForms表单自动计算研究

XForms被称为下一代的Web表单,XForms中的模型表达了实例数据项间的计算依赖,计算依赖是一个有向无环图,通过动态拓扑排序算法能够维护有向无环图的拓扑顺序,从而实现XForms表单自动重新计算.该算法解决了数据项增加、减少或数据项间计算依赖的增加、减少后需要全部重新计算问题,提高了XForms计算引擎的效率.     

基于Petri网的网格数据库查询计划模型的映射转换

网格数据库中主要采用基于有向无环图（DAG）的查询计划建模方式，该方法由于不考虑子查询与节点的数据关系，因而对子查询在节点的优化调度方面支持不足。对查询计划提出了基于Petri网的形式化描述模型NSN，通过扩展子查询与节点以及子查询之间的数据关联关系的描述，对子查询的优化调度提供更大的支持；进一步给出了从DAG模型到NSN模型的转换规则和转换算法，实现了查询计划从DAG到NSN模型的转换，最后通过实验验证了NSN模型对子查询在节点中的分派调度的优越性。     

一种基于HASH变换的循环散列分档排序算法

在数据排序问题中,各种分段快速排序算法[3～11]只有对特定的数据分布类型或者符合ΔM相似文献   

一种新的基于邻接矩阵的拓扑排序算法

为了降低基于邻接矩阵的拓扑排序算法的复杂性，将单顶点算法框架扩展成集合算法框架，给出一些便于进行拓扑排序的有向无环图的性质。在此基础上，定义了适合进行弧删除操作和无前驱顶点判断的邻接矩阵运算，给出了有向弧邻接矩阵的存储方案，最终提出了一种时间和空间复杂度都比较低的拓扑排序算法。     

基于模拟退火算法的改进主/副版本调度算法

针对异构分布式系统中面向任务优先级约束的调度问题,提出一种基于模拟退火算法的改进主/副版本调度算法SAPB。任务模型以有向无环图DAG表示,该算法共计调度主、副2个版本的任务。在任务优先级排序阶段,采取HEFT的任务排序方法,避免了eFRD等主/副版本调度算法中任务模型描述的局限性问题;在任务处理器分配阶段,采取模拟退火算法搜索满足截止时限条件下具有更高可靠性的调度结果,并且采取多一重备份策略以解决处理器数量相对较少时任务优先级约束带来的副版本调度易失败问题。最后,通过随机生成的DAG图进行仿真实验,结果表明,相比eFRD等算法SAPB具有更优的副版本可调度性和更高的系统可靠性。     

网络拓扑发现算法的设计与实现研究

传统的拓扑发现算法是基于SNMP协议的,能够很好的发现网络主拓扑,但是对于子网却往往出现发现不完整的情况.针对这一个问题,本文提出了基于ICMP(Internet Control Messages Protocol,网间控制报文协议)协议的方法,来得到完整的子网结构.     

网络拓扑发现算法的设计与实现研究

传统的拓扑发现算法是基于SNMP协议的,能够很好的发现网络主拓扑,但是对于子网却往往出现发现不完整的情况。针对这一个问题,本文提出了基于ICMP（Internet Control Messages Protocol,网间控制报文协议）协议的方法,来得到完整的子网结构。     

基于对应比较图的Fabric排序机制优化

针对HLF (Hyperledger Fabric)区块链系统在排序阶段中存在的缺陷,提出了一种基于对应比较图的图排序优化方案.利用对应比较图具有相关不变性质的图合并过程以及其算法运行时间短的特点,设计了一种基于交易重要度的拓扑算法,旨在减少由于默认的顺序排序而导致的序列化冲突问题.通过实验与分析,表明该方案有效解决了原始方案的序列化冲突问题,减少了系统中无效事务的比例,提升了系统交易效率,节省了大量的计算与存储资源.