论文部分内容阅读
随着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)用于任务与节点的分配。给出恰当的抗原、抗体和染色体表达方式,设计了“抗体选择”、“抗体克隆”、“抗体重组”和“抗体变异”等算子。理论分析与仿真实验均表明,本文算法的问题求解性能优于传统调度方法和已有用于任务调度的遗传算法,具有免疫记忆的特性。