基于改进ICSA算法的P2P任务调度机制研究

摘要

随着P2P计算模式的兴起、网络带宽的增加和Internet计算能力的迅速增强，如何充分利用这些资源，在动态的P2P网络环境中构建高可扩展、高可靠、高性能的分布式计算系统，是近年来研究的热点之一。任务调度是：P2P计算中的一项关键技术，直接影响到整个系统的计算性能。任务调度是指根据一定的调度策略，把一组可并行处理的任务按规定的时序分配到系统的多个处理机节点上，以期获得较好的系统执行性能。由于该问题不能在多项式时间内求得最优解，因而被公认为一个NP完全问题。 对于NP完全问题，近年来兴起的免疫算法(Immune Algorithm，IA)是一个较好的解决方案，即在较短的时间内能找到较好的解。因此许多研究分布式系统的专家开始关注免疫算法的研究。该算法在解决大空间、非线性和全局寻优等复杂问题时具有传统方法所不具备的独特优势，使IA在任务调度问题中得到了较好的应用和较快的发展。 本文在分析克隆选择原理的基础上，引入依据克隆免疫理论设计的优化算法opt-aiNET，给出改进的免疫克隆选择算法(Immune Clonal Selection Algorithm，ICSA)。使用De Jong提出的几种不同性质的测试函数对改进的ICSA算法的收敛性能进行实验研究，并且与文献中其它方法的测试数据进行比较，实验结果验证了改进的ICSA算法具有良好的收敛性、稳定性和较强的适应性。采用正交实验法和方差分析技术，揭示了控制参数对算法局部收敛和全局收敛性能的影响，并且根据实验结果总结出参数选择的一些原则。 针对P2P系统中任务分配与调度的多种影响因素，如各节点的可调度时间、节点的性能、网络拓扑结构和节点间通信机制等，给出了基于改进的Gnutella消息的节点定位和基于免疫学习和记忆机理的空闲时间统计机制，以获取系统中节点的活动状态和性能参数，并通过给出的参数拟合机制获取最优的调度节点序列。针对P2P系统中节点的随机加入和退出的情况，给出了代理节点的选择策略。 给出基于DAG图的耦合任务的数据结构表示，并以人工免疫系统为研究背景，将改进免疫克隆选择算法(Immune Clonal Selection Algorithm，ICSA)用于任务与节点的分配。给出恰当的抗原、抗体和染色体表达方式，设计了“抗体选择”、“抗体克隆”、“抗体重组”和“抗体变异”等算子。理论分析与仿真实验均表明，本文算法的问题求解性能优于传统调度方法和己有用于任务调度的遗传算法，具有免疫记忆的特性。‘

目录

文摘

英文文摘

声明

1绪论

1.1研究课题的提出

1.1.1并行计算

1.1.2课题的提出

1.2任务调度的研究现状

1.2.1经典调度理论

1.2.2基于模拟退火的方法

1.2.3基于进化计算的方法

1.2.4其它相关工作

1.2.5现有方法的不足

1.3 P2P网络的研究

1.4人工免疫系统的研究现状

1.5本文的主要工作

1.6论文结构

2人工免疫学基础

2.1生物免疫系统的基本理论

2.1.1免疫系统的功能

2.1.2免疫系统的结构

2.1.3免疫系统克隆选择理论

2.1.4免疫网络理论

2.2人工免疫系统及其工程应用

2.2.1人工免疫及其应用

2.2.2基于免疫原理的优化算法

2.2.3进化计算

3改进的ICSA算法及其性能分析

3.1算法的理论基础

3.1.1克隆选择算法

3.1.2免疫opt-aiNET算法

3.1.3 opt-aiNET与CLONALG的不足之处

3.2算法描述

3.2.1定义

3.2.2算法操作与解释

3.3算法收敛性的实验分析

3.3.1收敛性能指标

3.3.2测试函数

3.3.3算法的收敛性测试

3.3.4算法收敛性能的统计分析

3.4参数对改进的ICSA算法收敛性能的影响

3.4.1影响改进的ICSA算法收敛性能的参数

3.4.2正交实验设计

3.4.3参数对改进的ICSA算法局部搜索性能影响分析

3.4.4参数对改进的ICSA算法全局搜索性能影响分析

3.5结论

4无结构P2P网络中的任务调度

4.1 P2P任务调度概述

4.2空闲节点集合获取策略

4.2.1基于消息机制的空闲时间获取

4.2.2空闲置信区间的求解

4.3节点性能参数选取与拟合

4.3.1性能参数选取

4.3.2参数拟合与代理节点选取

4.4算法在任务分配中的应用

4.4.1耦合任务表示

4.4.2初始抗原与抗体构造

4.4.3亲和度计算

4.4.4变异算子和疫苗机制

4.4.5克隆选择算子

4.4.6任务分配机制

4.5 P2P环境中的耦合任务调度

4.6仿真实验

4.6.1实验模拟

4.6.2结果比较与分析

结 论

参考文献

攻读硕士学位期间发表学术论文情况

致 谢