P2P工作流系统中的资源搜索及负载均衡优化研究

摘要

工作流是一类集成业务活动并使其能够自动化或半自动化完成的计算机支持的协同工作技术，是计算机科学、自动控制科学、管理科学和先进制造等多学科领域共同关注与研究的热点问题之一，其核心是通过业务流程，协同网络中分布的计算资源和业务行为，并可进一步引申为对网络计算能力的挖掘。
　　 基于对等计算范型构造的工作流系统称为P2P工作流系统。它将工作流模型中的逻辑关系映射到一个活动及其转移规则的集合，使活动所在节点不经过中心化工作流引擎，而直接与其逻辑前驱节点和后继节点进行通信和数据交换，从而将控制流和数据流分布到每一个任务执行节点上，并在工作流网络上展现为自组织的工作流程，体现了工作流的分布特质。P2P工作流是一种去中心化的计算模式，消除了集中式工作流系统中那些由中心化控制结构造成的性能瓶颈，为大规模业务过程协同提供了一种具有高度柔性、可扩展性和容错能力的计算技术，被认为是工作流研究和应用领域最具战略意义的方向之一。
　　 中心化工作流引擎的消除，使得对等点之间主要以自组织的方式形成工作流网络的控制结构，而支撑这种自治体制的核心即高效的对等点协同策略。因此，对等点之间的协同效率是决定P2P工作流系统性能的关键因素。在实际业务流程运行过程中，协同效率主要体现为工作流实例(Workflow Instance，WI)在系统中的运行时间。从这个角度考虑，基于最短运行时间的WI的最优执行路径规划(The Optimal Path Planning，OPP)成为了制约P2P工作流系统性能优化的关键问题。在没有调度中心且网络拓扑及参数动态变化的对等网环境中，OPP问题体现出三个明显的特点：1.网络中各节点的计算资源、负载状况、通信带宽和网络的拓扑结构动态变化；2.节点信息的局部可视化：3.执行路径的强指向性。
　　 具有上述特点的OPP问题标识了一类全新的路径规划问题，称为分布式最优路径规划问题(Distributed Optimal Path Planning，D-OPP)，即在大规模动态网络中，根据局部信息求解具有最小执行时间的全局最优路径的问题。由于D-OPP问题的局部可视性和强指向性，WI的运行时间主要由任务的执行时间(TaskExecution Time，TET)和对执行节点的搜索时间(Peer Sesearch Time，PST)构成。因此，对路径执行时间的优化问题就可以被分解为两个子问题：1.去中心化P2P工作流网络中的资源搜索问题，即对拥有所需计算资源的执行节点集合的搜索问题，以实现搜索时间最小化为目的；2.去中心化动态负载均衡问题，即在最短时间内实现去中心化的实时任务调度，以找到具有最小任务执行时间的节点，并形成优化的负载分布为目的。上述两个子问题在工作流程各个执行步中的最优解的组合，最终将拟合出D-OPP问题的全局最优解。
　　 本文重点研究了P2P工作流系统中的去中心化资源搜索和动态负载均衡的优化问题，其成果不仅使P2P工作流系统同时具备灵活的架构和优异的执行效率，而且在更普遍意义上为分布式计算资源的整合以及分布式计算模式的大范围部署提供了有力的支持。本文的主要工作包括：
　　 1.分布式最优路径规划问题(D-OPP)的形式化描述和分析。
　　 P2P工作流的主要特征在于完全分布的控制结构，可理解为工作流实例基于服务聚类，在各服务集之间依据局部逻辑约束自治的跳转过程。因此，D-OPP问题本质上具有层次性特征，包括服务集之间和服务集内部两个层次，分别对应去中心化资源搜索问题和去中心化动态负载均衡问题。本文第二章从服务聚类的角度给出了P2P工作流系统的体系结构，并在此基础上，利用Markov链对D-OPP问题进行形式化建模与分析，给出了问题最优解的总体结构，即最优的去中心化资源搜索和负载均衡算法。
　　 2.去中心化动态P2P工作流资源搜索网络研究。针对D-OPP问题的第一个子目标，研究去中心化资源搜索问题，给出具有最小搜索步数的最优解。
　　 去中心化资源搜索问题要求在没有路由中心的P2P网络环境中快速定位当前工作流程所需的服务集。对于P2P网络，结构化P2P方法较非结构化P2P方法具有更优的路由效率，因此，本文将结构化P2P的设计引入工作流系统，在P2P工作流的域间层次中，通过构建结构化P2P网络组织各服务集合，实现最优的搜索效率。本文第三章分别提出了服务寻址网络(Services Addressed Network，SAN)和基于逻辑映射码(Logic Mapping Coding，LMC)的生成图定位网络(Spanning Graph Location Network，SGLN)。SAN可看作多层CAN网络的叠加，较之当前代表性的P2P工作流网络，它有效提高了搜索效率，降低了路由带宽，获得了100％的路由精度；SGLN根据。LMC将工作流程映射为P2P网络拓扑，提供了O(1)的最优路由时间复杂度，并且没有引入任何的额外路由负载以及冗余拓扑结构，同时具有多通道的并行处理能力以及较小的空间复杂度，给出了D-OPP中去中心化资源搜索问题的最优解。本文通过算法和实例分析给出了SAN和SGLN网络的时间和空间复杂度以及构建过程，并与典型的结构化P2P网络和工作流系统进行了对比分析。
　　 3.P2P工作负载均衡网络研究。
　　 对于去中心化动态负载均衡问题的解决，有两个关键点：(1)具有能够实时表达系统负载状况的基础P2P网络；(2)构建在基础P2P网络之上的最优随机负载分配算法。工作负载均衡网络为高效的去中心化动态负载均衡，提供基础P2P网络支持，同时实现对SGLN和SAN各层子网的链接，即作为服务集合域内拓扑的组织形式。本文第四章提出一种P2P随机网络，称为工作负载均衡网络(WorkloadBalancing Network，WBN)，实现了通过随机网络拓扑映射节点的负载处理能力，当节点负载状况发生变化时网络拓扑保持稳定。大量仿真实验表明，WBN网络展现出三个特性：(1)拓扑结构的能力相关性；(2)高度的能力聚集特性；(3)独立于系统规模的小网络直径。这些特性为去中心化负载分配快速收敛到全局最优提供了直接的支持。
　　 4.去中心化动态负载均衡算法研究。针对D-OPP问题的第二个子目标，研究中心化动态负载分配问题，给出具有最小收敛步数的最优解。
　　 去中心化动态负载分配问题主要通过构造在基础P2P网络上的随机负载分配算法解决，要求：(1)在没有调度中心的P2P网络环境中实现；(2)快速收敛；(3)以大概率收敛到具有最短执行时间的最优执行节点。本文第五章基于WBN网络，提出一种启发式随机采样算法(Heuristic Randomized Sampling algorithm，HRSalgorithm)，称为WBN算法，给出了D-OPP中去中心化动态负载分配问题的最优解。在WBN网络上，WBN算法以节点负载比例为基础构造启发因子，通过始终随机采样具有更小负载比的节点，实现负载的实时分配。大量仿真实验表明WBN算法可以概率1将当前负载分配到最优执行节点上，使其获得最快的实时完成时间；而总体上形成正比于节点负载处理能力的最优负载分布，使系统在运行周期内获得最小的总负载处理时间；并且负载分配的期望采样步数，独立于系统规模和负载状态，相对稳定在4～4.5步，这一性能已逼近最优的中心化负载均衡。
　　 5.拓扑无关的非结构化路径规划算法研究。
　　 对于D-OPP问题，SGLN网络和WBN算法两者都是通过构造特定拓扑结构支持最优性能的实现，若对于任意的网络拓扑，目前已有的非结构化搜索和分配算法很难达到最优性能。因此，需要一种拓扑无关的非结构化路径规划方法作为对D-OPP问题最优解的补充，并且具有以下特点：(1)去中心化方法；(2)不需要维护特定拓扑结构；(3)具有优化的路径规划性能。路径规划实质上是将路由代价转化为其他形式的构造代价，从而从规划的角度看实现了优化。因此，在不能转化为拓扑构造代价的情况下，本文采用反向过程，即资源的主动发布过程，作为转化形式实现D-OPP问题的优化。本文第六章提出一种随机令牌发布(Randomized Token Distribution，RTD)算法，以大概率在较小随机采样步数内将令牌发布到需求程度较高的服务请求节点，实现了在不需要特征拓扑结构支持的情况下，使服务请求节点对目标节点的一步可达。本文通过大量仿真实验验证并支持了RTD算法的性能。
　　 6.分布式路径规划问题(D-OPP)的最优解。
　　 SGLN网络给出了D-OPP中去中心化资源搜索问题的最优解，WBN算法给出了D-OPP中去中心化动态负载均衡问题的最优解，两者结合给出了D-OPP最优化问题的完整解，使得从当前执行节点只需经过大约5跳就可以找到下一个最优执行节点(SGLN网络1跳，WBN网络4跳)。而SAN网络和拓扑无关的RTD算法可作为对最优解的有效补充。
　　 本文工作的创新点主要体现在：
　　 1.提出了一种称为服务寻址网络(SAN)的结构化P2P网络，支持优化的去中心化动态域间资源搜索。
　　 较已有的P2P网络，SAN可以为工作流系统提供更高的搜索效率，获得100％的路由精度，降低路由的通信带宽，适用于节点数目多且动态变化范围大的系统。
　　 2.提出了一种称为生成图定位网络(SGLN)的结构化P2P网络，给出了基于SGLN的去中心化资源搜索问题的最优解。
　　 SGLN基于LMC将工作流程映射为P2P网络拓扑，提供了O(1)的最优路由时间复杂度，没有引入任何的额外路由负载以及冗余拓扑结构，同时具有多通道的并行处理能力以及较小的空间复杂度。
　　 3.提出一种称为工作负载均衡网络(WBN)的动态随机网络，构建了一种称为WBN的启发式随机采样算法，给出了基于WBN算法的去中心化动态负载分配问题的最优解。
　　 WBN网络有效支持负载分配快速收敛到全局最优。WBN算法可以概率1在去中心化环境下将当前负载分配到最优执行节点，总体上形成正比于节点负载处理能力的最优负载分布，并且负载分配的期望采样步数，独立于系统规模及负载状态，相对稳定在4～4.5步。
　　 4.提出了一种随机令牌发布(RTD)算法，在不需要特征拓扑结构支持的情况下，给出了D-OPP问题的一个满意解。
　　 RTD算法可以较大概率，在较短期望采样步数(主要分布在5步左右)内，以一定的覆盖比例将令牌发布到需求程度较高的服务请求节点，实现了服务请求节点对最终执行节点的一步可达以及优化的负载分布。
　　 P2P工作流是一个涉及面很广的研究课题，本文进一步的工作主要包括：
　　 在线调度问题研究。当节点需要保存大量缓存数据时，在有限的存储空间中，对索引数据的选择策略可明显影响节点数据索引的效果，即在线调度问题。对于本文所有的搜索算法，可通过建立搜索对象的本地索引，提高搜索性能和系统的容错能力。
　　 物理拓扑与逻辑拓扑匹配问题研究。路由时只考虑经过的节点数量是不够的，比较理想的情况是用端到端的延迟来进行路径选择，即覆盖网与物理网络的拓扑匹配问题。对于本文所有的搜索和负载均衡算法，拓扑匹配的改进将有利于进一步提高P2P工作流系统的性能。

目录

文摘

英文文摘

TABLE OF CONTENTS

第一章 绪论

1.1 课题背景和意义

1.2 国内外研究现状与分析

1.2.1 P2P工作流路径规划策略研究

1.2.2 P2P网络资源搜索算法研究

1.2.3 P2P网络负载均衡算法研究

1.3 本文的工作与创新

1.3.1 本文的工作

1.3.2 本文的创新

1.4 本文的组织

第二章 基于服务聚类的D-OPP问题形式化描述

2.1 引言

2.2 基于服务聚类的P2PT作流系统结构

2.2.1 工作流程映射

2.2.2 工作流程发布

2.2.3 P2P定位网络

2.3 Markov链

2.3.1 无记忆特性及转移概率

2.3.2 绝对分布及平稳分布

2.3.3 收敛特性

2.4 D-OPP问题形式化描述

本章小结

第三章 去中心化动态P2P工作流资源搜索网络

3.1 引言

3.2 服务寻址网络

3.2.1 SAN拓扑结构

3.2.2 SAN路由算法及分析

3.2.3 SAN系统动态维护

3.2.4 SAN实例

3.3 生成图定位网络

3.3.1 逻辑映射编码

3.3.2 SGLN拓扑生成

3.3.3 SGLN路由算法及分析

3.3.4 SGLN系统动态维护

3.3.5 SGLN实例分析

本章小结

第四章 P2P工作负载均衡网络

4.1 引言

4.2 WBN拓扑构造

4.3 WBN拓扑分析

4.3.1 平稳分布

4.3.2 收敛速度

4.3.3 期望度数

4.3.4 几点结论

4.4 WBN拓扑仿真及结论

4.4.1 期望度数及度分布

4.4.2 网络直径

4.4.3 聚集系数

本章小结

第五章 去中心化启发式动态负载均衡算法

5.1 引言

5.2 吸收态Markov链

5.3 启发式随机采样算法设计

5.3.1 启发因子

5.3.2 启发式随机采样算法

5.4 HRS算法分析

5.4.1 最优负载分配策略

5.4.2 吸收概率

5.4.3 吸收步数

5.5 WBN算法分析

5.6 WBN算法仿真及结论

5.6.1 吸收概率

5.6.2 负载分布

5.6.3 最优性比较

5.6.4 吸收步数

本章小结

第六章 拓扑无关的随机令牌发布算法

6.1 引言

6.2 随机令牌发布算法

6.2.1 RTD算法设计

6.2.2 令牌维护

6.3 RTD算法仿真

6.3.1 吸收概率

6.3.2 吸收步数

本章小结

第七章 总结与展望

7.1 本文总结

7.2 研究展望

参考文献

致谢

攻读学位期间发表的主要学术论文

攻读学位期间参与科研项目情况

攻读学位期间获得奖励情况

学位论文评阅及答辩情况

附录 英文论文