P2P环境下多目标任务调度策略研究

论文摘要

随着P2P计算模式的兴起、网络带宽的增加和Internet计算能力的迅速增强,如何充分利用这些资源,在动态的P2P网络环境中构建高可扩展、高可靠、高性能的分布式计算系统,是近年来研究的热点之一。任务调度是P2P计算中的一项关键技术,直接影响到整个系统的计算性能。任务调度是指根据一定的调度策略,把一组可并行处理的任务按规定的时序分配到系统的多个处理机结点上,以期获得较好的系统执行性能。为了达到任务调度负载均衡和更有效的利用P2P网络资源的目的,提出了基于相似度的任务调度算法。通过计算现行任务与历史任务之间的相似度,来确定能够直接调度的结点;通过计算任务需求资源与结点可提供资源的相似度并利用传输时间因素对其进行修正,来获取满足任务需求的有序结点集合。实验结果表明,基于相似度的任务调度算法能够有效地减少任务调度过程中的“颠簸”现象,更好达到负载均衡和有效利用资源的目的。P2P环境的特点决定了其任务调度是受多个因素制约的。通过考虑任务执行时间、结点间的通信时间和任务调度费用等因素,提出了多目标约束的并行任务调度策略。首先提出了多目标任务调度的数学模型,利用任务需求与结点性能之间的关系来定义各目标的需求关系矩阵,然后利用隶属度函数将各个关系矩阵转化为模糊矩阵,并根据每个目标对最终目标的不同影响来确定各目标在最终决策中所占的比率,从而将多目标转化为单目标任务调度模型。实验结果表明,基于多目标约束的任务调度模型较传统的方法更能优化任务调度的性能。为了更好满足不同用户对服务质量的要求,提出了任务划分调度模型。首先将任务分为实时任务与非实时任务,然后根据任务调度的特点以及所存在的任务类型,利用排队理论分别描述了两种不同的任务调度模型。实验分析了引入本章任务调度模型后对不同算法的影响,表明了进行任务划分和引入排队机制的有效性。

论文目录

• 摘要
• Abstract
• 1 绪论
• 1.1 P2P网络的研究
• 1.1.1 P2P网络研究的意义
• 1.1.2 P2P网络结构
• 1.1.3 P2P网络技术的应用
• 1.2 研究课题的提出
• 1.2.1 并行计算
• 1.2.2 课题的提出
• 1.3 常见任务调度模式及调度算法介绍
• 1.3.1 经典调度理论
• 1.3.2 常见的任务调度模式
• 1.3.3 任务调度算法分类
• 1.4 论文的主要工作
• 1.5 论文的组织结构
• 2 任务调度及调度算法研究
• 2.1 任务调度的特点
• 2.2 任务调度的目标
• 2.3 任务调度研究现状
• 2.3.1 任务调度算法研究现状
• 2.3.2 任务调度模型研究现状
• 3 基于相似度的任务调度策略
• 3.1 问题的提出
• 3.2 相关知识介绍
• 3.2.1 向量空间模型
• 3.2.2 相似度
• 3.3 任务描述与任务集合划分
• 3.4 任务调度结点的获取策略
• 3.4.1 基于任务相似度的结点获取
• 3.4.2 基于资源相似度的结点获取
• 3.5 任务调度策略
• 3.6 实验结果及结果分析
• 3.7 小结
• 4 多目标约束的并行任务调度策略
• 4.1 问题的提出
• 4.2 相关知识介绍
• 4.2.1 隶属度
• 4.2.2 匈牙利算法
• 4.2.3 线性规划理论
• 4.3 任务调度的数学模型
• 4.3.1 任务调度描述
• 4.3.2 数学模型
• 4.4 目标转化
• 4.5 算法描述
• 4.6 实验及结果分析
• 4.7 小结
• 5 基于排队理论任务调度模型
• 5.1 问题的提出
• 5.2 相关知识介绍
• 5.2.1 排队系统的组成
• 5.2.2 排队论中的理论分布
• 5.3 任务调度问题描述
• 5.3.1 实时任务调度方式
• 5.3.2 非实时任务调度方式
• 5.4 任务调度模型
• 5.4.1 实时任务调度模型
• 5.4.2 非实时任务调度模型
• 5.4.3 混合任务调度模型
• 5.4.4 任务模型中的调度算法
• 5.5 实验及结果分析
• 5.6 小结
• 结论
• 参考文献
• 攻读硕士学位期间发表学术论文情况
• 致谢