摘要：工作流是集成业务活动并使其能够自动化或半自动化完成的一类计算机协同工作技术,是计算机科学、自动制约科学、管理科学、先进制造等多学科领域共同关注与探讨的热点不足之一,其核心是通过业务流程的执行,协同网络中分布的计算资源和业务行为,并可进一步引申为对网络计算能力的挖掘。在通信、金融、保险、气象、地震、测绘、勘探、经济运转统计、科学计算、数据挖掘、经营浅析等海量数据处理或者复杂业务流程处理的工作流执行历程中,工作流执行效率是个颇受关注的普遍不足。以通信行业为例,在通信计费系统中,中等省份的月话单数量约为40亿—50亿条,每月底全省集中计费和出账工作量非常大,按照上面陈述的计算规模,在多台高性能怎么写作器计算环境中进行处理,仅仅“计费”活动需要约6小时左右,完成话单采集、话单格式化、话单查重、计费、账务处理等整个工作流程大约需要48小时左右。这一不足带来的直接影响就是工作流执行耗时过长、对IT基础设施投资的需求过大。由此,探讨提升工作流执行效率的策略,具有普遍的现实作用。P2P技术实现了计算方式以主-以式向对等式的转变,网络运用的核心以中心怎么写作器向边缘计算设备扩散,有效地解决了单点失效和负载均衡不足,大幅提升了网络的整体计算能力。充分利用P2P网络中的计算资源和计算能力,将工作流中那些运算工作量大的活动予以分解,并将其调度到优选节点上进行分布式运算,将会大幅提升可用计算资源的利用效率和工作流的整体执行效率。由此,P2P网络环境中的任务分解和调度(Task Partitioning and Schedupng, TPS)是工作流探讨的一个核心不足。P2P网络环境中的任务分解和调度不足有如下特点：①P2P网络中各节点的计算资源、通信能力、负载情况和网络拓扑结构是动态变化的；②由第一个特点决定了无法在事前准确计算每个节点的任务处理时间,由此将工作流执行时间作为任务调度目标将比较困难；③结构化的、去中心化的P2P网络节点信息的局部可视化。一种较好的解决案例是使工作流管理系统具有感知P2P网络节点上下文的能力,即探讨解决基于P2P网络节点上下文的任务分解和调度不足(ContextBased Task Partitioning and Schedupng, CB-TPS)。 CB-TPS不足可以分解为如下三个子不足：①任务分解不足,即将工作量大的、复杂的活动分解为工作量小的、简单的细粒度任务集,以达到降低单个任务运算量的目的；②任务调度不足,即把分解后的子任务分配到适当的节点上运转,以实现工作流执行效率全局最优的目标；③执行结果合成不足,即将各个子任务的执行结果进行合并,使之等价于任务分解前的工作流活动的执行结果。本论文重点探讨了去中心结构化P2P网络环境中的任务分解和调度策略,主要工作包括：1、基于P2P网络节点上下文的任务分解与调度(CB-TPS)不足求解模型。本论文将P2P网络节点上下文引入工作流管理,使工作流管理系统能够感知P2P网络环境,并根据节点上下文动态地完成任务分解和调度,以实现最优的运转效果。CB-TPS不足求解模型的基本思想是：首先通过节点上下文信息获得计算节点的计算能力和通信能力,然后据节点处理能力进行任务分解与调度。任务分解包括两种方式：基于数据划分的任务分解和基于功能划分的任务分解。利用数据划分策略进行任务分解时,首先根据获得的节点上下文信息推算节点的计算能力,然后根据节点计算能力分配与之能力匹配的任务。利用功能划分策略进行任务分解时,先利用获得的节点上下文信息测算任务处理效率,再根据测算效率分配任务。本论文第2章在引入节点上下文和工作流有穷状态自动机的基础上,定义了上下文影响权重因子和节点计算能力评价指数,给出了权重因子和节点处理能力的计算策略,建立了CB-TPS司题求解模型。2、基于功能划分的的任务分解与调度策略。基于功能划分的任务分解策略,本质上是将工作流的特定活动,按照业务逻辑进行功能细分,即将其拆分为一组偏序连接的任务子流程,其中,每个任务对应一项特定的业务功能。分解后的任务子流程调度不足,可以通过执行路径规划求解,例如列表调度、任务复制调度、遗传算法、粒子群策略、蚁群算法等。本论文第3章在定义任务分解算子的基础上,建立了一种基于工作流有穷状态自动机的任务分解策略；在定义节点处理能力评价指数的基础上,通过对蚁群算法的优化改善,建立了一种蚁群任务调度算法。实验结果表明,改善的蚁群任务调度算法,不但能够解决工作流执行时间等参数难于估算的不足,而且能提升任务调度的动态适应性。3、基于数据划分的任务分解与调度算法。基于数据划分的任务分解策略,本质上是将工作流的特定活动,根据被处理数据对象的细粒度划分,分解为一组可以并行执行的任务。数据划分的粒度越小,能够参与计算的P2P网络节点越多,工作流的效率提升效果越显著。本论文第4章在定义数据划分的横切方式和纵切方式的基础上,基于各个数据子集中的索引字段值不能有交集的划分原则,建立了一种基于数据划分的任务分解策略；在CAN网络基础上,改善了洪泛和K随机漫步资源搜索算法。实验结果表明,改善的洪泛和K随机漫步算法能够快速地完成设定数量的计算节点的搜索,并在资源搜索的同时获得候选节点的处理能力。在任务调度时,工作流管理系统首先以候选计算节点中优选一定数量的节点作为任务节点,然后根据这些节点的处理能力确定每个节点的任务分配强度,依据任务分配强度划分数据并调度到相应节点上予以处理。所有子任务执行完成后,结果合成就是将各个子任务的执行结果进行直接合并。由于在任务分解时遵循了数据分解的不相交原则,所以执行结果的直接合并与任务分解前的执行结果是等价的。本论文第4章给出了结果合成策略和等价性证明。本论文工作的革新点主要体现在：1、建立了一种基于P2P网络节点本体和工作流有穷状态自动机的任务分解与调度不足求解模型。较之键值对、标记语言等策略,本体可以更好地表达P2P网络节点上下文的语义和节点的动态变化；较之WF-Net和Petri Net,工作流有穷状态自动机可以更加灵活地表示P2P网络中的不确定事件,动态地描述工作流的动态分拆和组装历程。由此,基于节点本体和自动机的任务分解与调度不足求解模型具有良好的P2P网络环境适应性。2、提出了一种基于节点上下文和功能划分的任务调度蚁群算法。改善的蚁群算法以节点处理能力指标为启发因子,以任务执行代价的倒数作为蚂蚁经过路径所留下的信息素浓度,既体现了基于节点上下文进行任务调度的自适应特点,又可以更好地引导调度算法向处理能力强、任务执行代价低的节点倾斜,加速向最优解的收敛。3、提出了一种基于节点资源快速搜索和数据划分的任务调度策略。改善的洪泛和K随机漫步资源搜索算法,能够快速地完成设定数量的计算节点的搜索,并基于上下文完成节点处理能力的评价；数据划分的不相交原则可以保证数据子集的独立性,节点处理能力评价能够保证将任务分配到处理能力最强的节点集上,提升任务调度和执行效率。P2P网络环境中的工作流分解与调度是一个涉及面很广的探讨课题,本论文进一步的工作主要包括：1.基于上下文的P2P覆盖网构造优化探讨。P2P网络是在IP网络或者其他物理网络上的逻辑覆盖网,其拓扑与物理网络的实际拓扑并不完全匹配,造成P2P网络的路由实际上并不一定是最优的路由,可以通过上下文对逻辑覆盖网络进行优化调整,使其路由信息更加优化。2.P2P网络上工作流运转质量监督制约的优化探讨。P2P网络中的工作流所处环境复杂、多变、异构,如何实时监控工作流的运转情况,并根据节点上下文信息对其进行自适应的调度,将是保证P2P工作流稳定运转的一项重要技术。关键词：工作流论文任务分解论文任务调度论文P2P网络论文节点上下文论文自动机论文
摘要10-14
ABSTRACT14-19
第1章 绪论19-37
1.1 课题背景和作用19-22
1.2 相关工作与讨论22-32
1.2.1 P2P网络节点上下文的表示22-24
1.2.2 P2P网络资源搜索算法探讨24-29
1.2.3 任务调度策略探讨29-32
1.3 本论文的工作与革新32-35
1.3.1 本论文的工作32-34
1.3.2 本论文的革新34-35
1.4 本论文的组织35-37
第2章 基于P2P网络节点上下文的任务分解与调度模型37-53
2.1 引言37
2.2 CAN网络37-39
2.3 CAN节点上下文39-49
2.3.1 CAN节点上下文的本体描述41-44
2.3.2 节点上下文获取与管理44-47
2.3.3 基于上下文的节点处理能力评价47-49
2.4 工作流有穷状态自动机49-50
2.5 CB-TPS不足求解模型50-52
本章小结52-53
第3章 基于功能划分的任务分解与调度策略53-83
3.1 引言53
3.2 基于自动机的功能划分策略53-58
3.3 基于功能划分的任务调度蚁群算法58-66
3.3.1 业务流程的有向无环图表示59-60
3.3.2 关键路径求解算法60-61
3.3.3 任务调度蚁群算法61-64
3.3.4 参数对任务调度蚁群算法的影响64-66
3.3.5 任务调度蚁群算法复杂度浅析66
3.4 任务调度的终端适配不足66-69
3.5 实验与浅析69-76
3.5.1 任务调度效果69-72
3.5.2 终端适配效果72-76
3.6 基于自动机的工作流异常处理76-81
本章小结81-83
第4章 基于数据划分的任务分解与调度策略83-100
4.1 引言83
4.2 面向任务分解的数据划分策略83-86
4.3 基于数据划分的任务调度算法86-93
4.3.1 CAN网络中的洪泛算法87-89
4.3.2 CAN网络中的K随机漫步算法89-91
4.3.3 资源搜索算法浅析91
4.3.4 节点评价与优选91-92
4.3.5 任务分解与调度92-93
4.4 任务执行结果合成93-95
4.5 实验与浅析95-97
4.6 功能划分调度与数据划分调度的比较97-98
本章小结98-100
第5章 总结与展望100-103
5.1 本论文总结100-102
5.2 探讨展望102-103
本站原创