工作流是集成业务活动并使其能够自动化或半自动化完成的一类计算机协同工作技术,是计算机科学、自动控制科学、管理科学、先进制造等多学科领域共同关注与研究的热点问题之一,其核心是通过业务流程的执行,协同网络中分布的计算资源和业务行为,并可进一步引申为对网络计算能力的挖掘。在通信、金融、保险、气象、地震、测绘、勘探、经济运行统计、科学计算、数据挖掘、经营分析等海量数据处理或者复杂业务流程处理的工作流执行过程中,工作流执行效率是个颇受关注的普遍问题。以通信行业为例,在通信计费系统中,中等省份的月话单数量约为40亿—50亿条,每月底全省集中计费和出账工作量非常大,按照上述计算规模,在多台高性能服务器计算环境中进行处理,仅仅“计费”活动需要约6小时左右,完成话单采集、话单格式化、话单查重、计费、账务处理等整个工作流程大约需要48小时左右。这一问题带来的直接影响就是工作流执行耗时过长、对IT基础设施投资的需求过大。因此,研究提高工作流执行效率的方法,具有普遍的现实意义。P2P技术实现了计算模式从主-从式向对等式的转变,网络应用的核心从中心服务器向边缘计算设备扩散,有效地解决了单点失效和负载均衡问题,大幅提升了网络的整体计算能力。充分利用P2P网络中的计算资源和计算能力,将工作流中那些运算工作量大的活动予以分解,并将其调度到优选节点上进行分布式运算,将会大幅提升可用计算资源的利用效率和工作流的整体执行效率。因此,P2P网络环境中的任务分解和调度(Task Partitioning and Scheduling, TPS)是工作流研究的一个核心问题。P2P网络环境中的任务分解和调度问题有如下特点：①P2P网络中各节点的计算资源、通信能力、负载状况和网络拓扑结构是动态变化的；②由第一个特点决定了无法在事前准确计算每个节点的任务处理时间,因此将工作流执行时间作为任务调度目标将比较困难；③结构化的、去中心化的P2P网络节点信息的局部可视化。一种较好的解决方案是使工作流管理系统具有感知P2P网络节点上下文的能力,即研究解决基于P2P网络节点上下文的任务分解和调度问题(ContextBased Task Partitioning and Scheduling, 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工作流稳定运行的一项重要技术。