基于改进遗传算法的网格任务调度.研究

《基于改进遗传算法的网格任务调度.研究》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

摘要Keywords:Grid;Taskscheduling;DNAgeneticalgorithm;convergence;Grid-Sim;{III{万方数据 目录目录摘要IAbstractII第一章绪论11.1研究背景与意义...............................11.2任务调度算法的研究现状.........................31.3主要研究工作................................41.4论文结构...................................4第二章网格环境下的任务调度62.1网格概述...................................62.2网格的体系结构...............................72.3网格任务调度的特点和目标........................122.4网格任务调度的原理............................132.4.1任务调度的定义...........................142.4.2NP完全问题.............................142.4.3网格任务调度策略与过程......................152.5现有任务调度算法介绍与分析.......................162.6本章小结...................................18第三章遗传算法193.1遗传算法的发展与特点...........................193.2遗传算法基本原理与基本流程.......................203.3遗传算法的理论基础............................213.3.1模式定理...............................213.3.2隐含并行性.............................233.3.3积木块假设.............................233.3.4遗传算法的收敛性.........................233.4遗传算法操作设计与参数选择.......................243.5本章小结...................................29第四章基于改进遗传算法的网格任务调度设计304.1基于DAG图的网格任务调度策略.....................304.2基于改进的DNAGA网格任务调度算法设计...............314.2.1染色体编码.............................32{IV{万方数据 目录4.2.2初始种群生成............................344.2.3适应度函数.............................354.2.4遗传操作...............................354.2.5改进的快速收敛方法........................394.2.6遗传算法结束条件.........................424.3本章小结...................................42第五章仿真实验及分析435.1网格仿真及常见工具............................435.2GridSim网格模拟器.............................445.2.1GridSim体系结构与实体模型...................445.2.2GridSim仿真的步骤与软件的安装.................465.3仿真模块设计................................475.4实验结果与分析...............................505.5本章小结...................................56第六章总结与展望576.1本文的工作和成果.............................576.2未来展望...................................57参考文献59致谢64作者在攻读硕士期间主要研究成果65{V{万方数据 目录{VI{万方数据 第一章绪论第一章绪论x1.1研究背景与意义随着人类探索自然的深度、广度不断拓展，迫切需要功能更强、速度更快的计算机系统来处理和解决所遇到的问题。尽管超级计算机的能力在不断地增长，仍然有许多局限性。一方面，超级计算机造价极高，通常只有一些国家级的部门，才有能力配置这样的设备；另一方面，某些应用对计算的要求非常高，即使是现在最大的超级计算机也无法提供它们所需的资源。因此，网格计算(GridComputing)[1¡4]就成为当今计算机科学领域最新兴起的一项有很高学术价值和应用价值的研究课题。网格技术其核心思想是“整个因特网就是一台计算机”。网格的提出将从根本上改变人们对计算的看法，因为网格提供的是与以往根本不同的计算方式。网格的意义就如同互联网改变了人们传统的通信方式和通信手段一样，它将改变人们传统的计算方式和计算手段，网格技术将为人们提供更强大、更方便、更高级的问题求解手段。在网格计算中，任务管理、任务调度和资源管理是网格必须具备的三个基本功能。用户通过向网格系统提交计算任务来共享网格资源，网格调度程序再按照某种策略把这些任务分配给合适的资源。任务调度是网格计算中一个至关重要的问题，其算法将直接影响到网格环境中任务执行的效率以至成败。但由于网格的新特性，使得必须研究新的算法来解决一些新出现的问题，如调度问题的NP安全性，资源的异构性以及资源分配决策的并行性和分布性等。这对传统的调度算法提出了新的挑战。传统的并行计算调度算法主要是调度一个应用程序的子任务到并行的计算机，主要目的是减少计算时间；而对于网格环境，调度算法关心的主要问题是调度来自不同用户的应用流到可用的计算资源上，从而最大限度地让网格系统得到最大的使用，它追求的是调度的高吞吐率。具体的目标包括:最优跨度(OptimalMakespan)、服务质量Qos[5](Qualityofservice)，负载均衡(LoadBalancing)、经济原则(EconomicPrinciples)等。然而由于网格计算任务调度面临的是一个NP完全问题，至今没有找到有效算法，而指数型算法对解决规模较大的问题又十分困难，以求近似最优解为目的的启发性算法自然就受到了极大的重视。而遗传算法因其自组织、自适应、自学习性和并行性等特点而非常适宜解决网格任务调度问题。虽然研究人员在网格任务调度领域进行了许多的研究，也取得了一些成果，但是要解决网格环境的任务调度问题还需要进行大量的研究工作。网格作为一种建立在互联网上的新一代基础设施，目前网格计算处于快速发展期，很多正在开发的相关网格调度项目。下面是一些具有代表性的系统。中国国家网格[6](ChinaNationalGrid)是2005年12月21日开通的，是一个计算资源共享、数据共享以及协同工作的环境，已经开发了资源环境、科学研究、服务业和制造业四个领域的应用网格，由国家863计划重大专项支持，是聚合了高性能计算和事务处理能力的新一代信息基础设施的试验床。通过资源共享、协同工作和服务机{1{万方数据 第一章绪论制、有效支持科学研究，资源环境、先进制造和信息服务等应用。中国国家网格环境构成与主要设备包括北京中科院主结点（联想深腾6800）、上海超算中心主结点（曙光4000A）、北京清华结点（清华探索3号集群计算机）、北京应用物理结点（银河计算机）、西安结点（曙光3000）、合肥结点（HPIntegritySuperdome）、长沙结点（银河计算机）以及香港结点（集群计算机）。中国教育科研网格(chinaGrid)：教育部"211工程"公共服务体系建设的重大专项。中国教育科研网格由国内12所大学首批参与，配合网络计算机的使用，把在CERNET上自治的分布异构的海量信息资源集成起来，实现CERNET环境下资源的有效共享。消除信息孤岛，提供有效的服务，形成高水平低成本的计算机服务平台。Globus[7]是美国多家研究机构的合作项目，Globus的核心是一个工具集，包括一组执行基本服务的组件。Globus提供了调度组件作为其工具集的一部分，但没有提供具体的调度策略，依赖高层调度器执行任务调度，很多调度器中间件如Nimrod-G、AppleS和Condor都是基于Globus服务开发的。Globus是一个典型的分层网格体系，高层的服务可以调用低层的核心服务来开发。它的重点在于分级式的集合网格组件和服务，鼓励了使用低级的服务来开发高级的服务。Condor[8]是美国威斯康星大学开发的一个高吞吐量的计算环境，可管理分属于不同机构的大量PC机、工作站以及集群，以利用闲散CPU周期著名。Condor可以被认为是具有平面组织的计算网格。它使用了具有混合命名空间的可扩展体系。它不支持QoS，信息存储在不使用X.500/LDAP(LightweightDirectoryAccessProtocol)技术的网络目录中。资源发现是通过集中式的发布查询请求来实现的，因而属于集中式的调度程序。Netsolve[9]是一种基于客户-代理-服务器结构的服务网格，由代理执行信息存储与维护、资源发现和资源调度，客户端支持C、FORTRAN、METLAB和网页应用程序。2003年，Spooner在沃里克大学首次提出了TITAN，认为基于该体系结构可以通过遗传算法得到最优调度[10]。国外重要网格应用研究项目还有:美国NASA网格IPG（InformationPowerGrid）[11]，欧洲数据网格DATAGrid[12]，全球信息网格GIG[13]，美国NSF网格TeraGrid[14]，等等。可见，网格计算的应用已经引起了世界各国的高度重视。网格在实际应用方面已经展现出它超强的能力，并取得了一些成果：2007年9月，欧洲和亚洲研究人员共同协作将横跨45个国家的4万多台电脑联合起来组成网格。这个称之为EGEE（EnablingGridsforE-science）的计算机网格，将数万台普通电脑组成一个超大型超级计算机，他们正利用EGEE寻找能够抑制流感病毒活性的新型分子，使用EGEE，已经发现了大约200个可能成为对抗禽流感的药物分子。在匈牙利布达佩斯举行的EGEE2007会议上，EGEE应用于对抗禽流感的成功例子。据称，计算机网格在探明新药潜力方面的生产力水平提高超过6000%，筛选成功率高达6%%，而使用传统药物发现方法的典型成功率则仅为约0.1%%[15]。2008年3月18日出版的《美国化学会志》（JACS）[16]上发表了在英国国家网格计{2{万方数据 第一章绪论算(computinggrid)平台和美国TeraGrid系统的帮助下，伦敦大学学院(UCL)科学家有望揭示地球早期生命起源之谜的报道[17]。计算网格系统模拟形成在热液喷口附近的高温和高压环境，这将显示DNA分子植入分层矿石后所表现的稳定性，以及接触矿石和处于热降解作用下所形成的保护状态。x1.2任务调度算法的研究现状作为计算网格关键技术之一的任务调度算法，历来都受到国内外网格研究者的重视和关注。它与传统的分布式系统的主要区别在于它具有广域性、异构性、动态性三个特点，它主要应用于解决规模庞大、计算复杂、需要使用多种异构资源的计算问题，因此以前针对传统的分布式计算的调度方法已经不适用于网格环境中的任务调度。在传统的并行和分布式调度问题中，所涉及的计算资源是同构的，因此不必关心资源所具有的属性以及资源能否满足用户所提交的任务的需要，而且，计算资源通常在地理上是集中的，因此不用关心系统在运行过程中通信所花费的开销。网格任务调度的目的就是将“合适”的任务分配到“合适”的资源上去运行。网格的出现，对分布式任务调度研究提出了新的挑战。围绕着网格计算中的任务调度算法，一般来说有静态和动态的调度算法。静态调度算法是指所有的任务－机器映射策略在执行任务调度前就已经全部确定；动态调度算法是指一些任务－机器映射策略在执行任务调度期间根据实际情况进行确定。静态调度算法是网格计算中最早被研究的算法。相对较为简单[18]、调度算法运行开销低、对数据的依赖性小。常见的静态调度算法有：Min-min、Max-min、A*、Duplex、OLE、MET、蚂蚁算法、GA、借鉴市场经济原理的效益函数启发式任务调度算法等。此外还有一些算法思路比较新颖:两阶段（2-Phase）调度策略[19]:将一个计算任务的计算范围依次划分为LAN间和LAN内两个阶段，并分别在LAN间阶段和LAN内阶段设立全局的、集中的任务调度者，以负责制定该阶段的任务调度方案和监督任务执行情况。但是，由于仅用涉及LAN的两层结构来刻画计算网格是不准确的，所以，2-Phase调度策略还不能很好地描述计算网格的调度，需要更深入的扩展。基于市场供求关系的调度算法[20]:仿照日用品买卖市场调控策略来对计算资源进行优化组合。计算资源的“价格”被设定为介于资源的需求和提供之间，当计算资源的“价格”确定后，对它们的分配过程就按照“先来先服务”的原则进行，统一地由调度者进行调度。基于市场供求关系的调度算法利用经济学理论进行调度策略的分析，为其他调度算法提供了新颖的思路。在众多静态调度算法中，启发性智能化方法将是网格计算任务调度的一个重要研究领域。在本论文中将采用遗传算法来设计网格任务调度策略。研究者们也提出了一些动态算法。对于自适应任务调度算法，国内代表性的研究成果有参数扫描应用的自适应调度算法、HowU网格自适应调度模型等最新的算法，国{3{万方数据 第一章绪论外的如美国伊利诺斯工业学院提出的GHS（GridHarvestService）自适应调度模型。到目前为止，人们提出了很多网格系统的调度技术和算法。但是在网格计算环境中，已有的任何调度模型、策略、调度目标函数和算法都不可能适宜一切应用和环境；同一套调度机制在不同的条件下其表现性能不一定相同，因此，该领域的研究还有待进一步发展和完善。网格任务调度存在的问题主要是：（1）现有的各种网格任务调度方案很难满足资源提供者和用户对网格用户对网格环境的不同需求的矛盾；（2）为网格调度设计了各种各样的启发式算法，目前的研究还处于模拟仿真阶段，还需要在理论和实践中不断完善。（3）缺乏真实的网格测试环境来准确验证改进的算法的性能收获。x1.3主要研究工作网格技术将所有可用于共享的资源通过网络连接起来，并为各种复杂的计算任务提供资源服务。用户通过向网格系统提交计算任务来共享网格资源，网格调度程序再按照某种策略把这些任务在任务约束条件如网络带宽，资源节点性能等的基础上，采用适合于网格计算环境的任务调度算法，从而向用户提供最优性能。本文的主要工作如下:(l)介绍网格的相关概念和基本原理，总结网格的特点及其体系结构等基本知识和研究的背景，阐述网格计算的发展现状和现有的应用情况。(2)分析网格任务调度的原理和特点，将遗传算法应用于网格任务调度。针对遗传算法可能出现的早熟收敛等缺点，提出了一种改进算法DNA遗传算法(DNA-GA)。该方法中染色体编码采用DNA编码，在标准遗传算法选择、交换、变异基础上还引入倒位操作算子，并且增加了新的基因级操作(算子)：轮转算子，从而更加符合生物进化的规律。另外，本文提出了一种改进的快速收敛的方法。通过调整标准遗传算法结构，增加了对染色体的分割与重组操作，使标准遗传算法能快速收敛。(3)在GridSim网格仿真环境下，针对改进的遗传算法的网格任务调度进行了详细的仿真实验，并对实验结果进行了分析。x1.4论文结构第一章为绪论，介绍本文的选题背景、研究意义和研究方法，并给出论文的组织结构。第二章为网格计算的基础知识，介绍网格的基本概念和特点，并详细描述网格的体系结构，然后介绍目前国际上最有影响的网格计算项目GLOBUS。同时还介绍了网格任务调度的基本知识，分析任务调度的特点，研究网格任务调度的原理和调度过程，并介绍和分析了现有任务调度算法。{4{万方数据 第一章绪论第三章介绍了遗传算法的理论知识，遗传算法的基本思想和流程，遗传算法的数学理论基础，以及编码方式，适应度函数和三种基本的遗传操作等内容。第四章为基于改进遗传算法的网格任务调度算法的设计，内容包括:计算模型的建立，在DNA遗传算法下染色体设计，初始种群生成，选择、交叉和变异操作以及倒位、轮换操作。另外介绍相对快速收敛方法．第五章为仿真试验，介绍GridSim仿真包使用方法，并通过试验设定遗传算法的参数，比较分析算法性能。第六章为结束语，总结本文的工作，提出不足之处，并指出亟待解决的一些问题，并对进一步的研究进行展望。{5{万方数据 第二章网格环境下的任务调度第二章网格环境下的任务调度x2.1网格概述网格[21]是继万维网之后出现的一种新型网络平台，目的是为用户提供一种全面共享各种资源的基础设施。网格就是一个集成为一台巨大的超级计算机，它可以实现全球范围的计算资源、存储资源、数据资源、信息资源、知识资源、专家资源、设备资源，甚至是人才资源等各种相关的广泛分布的资源的全面共享。基于网格的问题求解就是网格计算(GridComputing)。以上给出的网格和网格计算的概念是广义的定义。狭义的网格一般被称为计算网格(ComputationalGrid)，即主要用于解决科学与工程计算问题的网格。全球网格研究的领军人物、美国阿岗(Argonne)国家实验室的资深科学家、美国Globus项目的领导人IanFoster曾这样描述网格:“网格是构筑在互联网上的一组新兴技术，它将高速互联网、高性能计算机、大型数据库、传感器、远程设备等融为一体，为科技人员和普通老百姓提供更多的资源、功能和交互性。互联网主要为人们提供电子邮件、网页浏览等通信功能，而网格功能则更多更强，让人们透明地使用计算、存储等其他资源。”2002年7月，IanFoster提出了限定网格必须同时满足的三个条件[22]:(1)在非集中控制的环境中协同使用资源。网格整合各种资源，协调各种使用者，这些资源和使用者在不同控制域中，否则，只能算本地管理系统而非网格。(2)使用标准的、开放的和通用的协议和接口。网格建立在多功能的协议和界面之上，这些协议和界面解决认证，授权，资源发现和资源存取等基本问题。否则，只算一个具体应用系统而非网格。(3)提供非平凡的服务质量。网格允许它的资源被协调使用，以得到多种服务质量，满足不同使用者需求。使得联合系统的功效比其各部分的功效总和要大得多。这三个条件非常严格，像P2P，SUNGridEngine，Condor等都被排除在网格之外。RandyBramley认为网格提供的计算能力是以前所无法得到的，而且也是不能够通过其它的方式得到的。网格概念的核心就是突破了以往强加在计算资源之上的种种限制，使人们可以以一种全新的更自由、更方便的方式使用计算资源，解决更复杂的问题。最重要的一点就是网格打破了传统的共享或协作方面的限制，以前对资源的共享往往停留在数据文件传输的层次，而网格资源的共享允许对其它的资源进行直接的控制，而且共享资源的各方在协作时可以以多种方式更广泛地交流信息，充分利用网格提供的各种功能。网格使得共享与协作的方式和方法更广泛了，而且为这种合作提供了各种控制策略与手段，可以根据需要，动态地与不同的组织与个人建立各种级别的工作关系。网格技术研究范围迅速扩大，根据求解问题的特点可以分为:计算网格(ComputationalGrid)、数据网格(DataGrid)，信息网格(Information{6{万方数据 第二章网格环境下的任务调度Grid)、知识网格(KnowledgeGrid)、语义网(SemanticGrid)、访问网格(AccessGrid)等方向，其应用层面也大大扩展。按照IanFoster和Globus项目组的观点，目前应用领域目主要有5类：分布式超级计算、分布式仪器系统、数据密集型计算、远程沉浸和信息集成等。一般而言网格计算系统具有以下几个特征：1.分布性：分布性是网格的一个最主要的特点。各种设备与资源，是分布在地理位置不同的多个地方，这些资源的类型复杂，规模较大，跨越的地理范围较广。这就决定了网格的计算一定是分布式计算而不是集中式计算。分布是网格硬件在物理上的特征，而共享是在网格软件支持下实现的逻辑上的特征。2.系统的异构性：构成网格计算系统的超级计算机有多种类型，不同类型的超级计算机在体系结构、操作系统及应用软件等多个层次上具有不同的结构。3.结构的不可预测性：网格计算系统由于其地域分布和系统的复杂使其整体结构经常发生变化，这与一般的局域网系统和单机的结构不同。4.自治性与管理的多重性：网格上的资源首先是属于某个组织或者个人的，因此网格资源的拥有者对该资源拥有最高级别的管理权限，网格允许资源拥有者对他的资源有自主的管理能力，这就是网格的自治性。由于构成网格计算系统的超级计算机资源通常属于不同的机构或组织并且使用不同的安全机制，因此需要各个机构或组织共同参与解决多级管理域的问题。因此网格的管理具有多重性，一方面它运行网格资源拥有者对网格资源具有自主性的管理，另一方面又要求网格资源接受网格的统一管理。x2.2网格的体系结构网格体系结构就是关于如何建造网格的技术[23]。它给出了网格的基本组成与功能，描述了网格各组成部分的关系，刻画了支持网格有效运转的机制。到目前为止，比较重要的网格体系结构有三个:IanFoster等提出的5层沙漏体系结构，结合WebService的开放网格体系结构OGSA，以及可以看作是OGSA的进一步发展的WSRF规范。本文主要介绍OGSA和WSRF。OGSA2002年在加拿大多伦多进行的第4届全球网格论坛(GGF)会议上，Globus倡议了一个全新的网格标准(OGSA)。开放网格服务体系结构(OpenGridServicesArchitec-ture，OGSA)[24]将Globus标准和商业的Web服务标准相结合，把资源统一以网格服务的形式提供给外界使用。GlobalToolkit3(GT3)是OGSA标准的第一个主要实现。OGSA架构如图2.1所示{7{万方数据 第二章网格环境下的任务调度图2.1OGSA结构图如果说五层沙漏结构是以“协议”为中心的“协议结构”，那么OGSA就是以“服务”为中心的“服务结构”。这里的服务是指具有特定功能的网络化实体。在OGSA框架中，将一切都抽象为服务，包括计算机、程序、数据、仪器设备等。这种抽象将资源、信息、数据等统一起来，十分有利于通过统一的标准接口来管理和使用网格。OGSA结合WebService提出了网格服务，用于解决服务的发现、动态服务的创建、服务生命周期的管理等与临时服务有关的问题[25]。1.物理和逻辑资源层.资源的概念是OGSA以及通常意义上的网格计算的中心部分。资源并不仅限于处理器。它们通过虚拟化和聚合物理层的资源来提供额外的功能。通用的中间件，比如文件系统、数据库管理系统、目录和工作流管理系统，在物理层之上提供这些抽象服务。2.Web服务层这里有一条重要的OGSA原则:所有网格资源(包括逻辑的与物理的)都被建模为服务。OGSI(OpenGridServicesInfrastructure)规范定义了建立在标准Web服务技术之上的网格服务。OGSI利用诸如XML与WSDL这样的Web描述语言，为所有网格资源指定标准的接口、行为与交互。OGSI进一步扩展了Web服务的定义，提供了动态的、有状态的和可管理的Web服务的能力，这在对网格资源进行建模时都是必需的。{8{万方数据 第二章网格环境下的任务调度3.基于OGSA架构的网格服务层Web服务层及其OGSI扩展为上层提供了基础设施：基于OGSA架构的网格服务。目前GGF正在致力于在诸如程序执行、数据服务和核心服务等领域中定义基于网格架构的服务。随着这些新架构的服务开始出现，OGSA将变成更加有用的面向服务的体系结构(ServiceOrientedArchitecture,SOA)。4.网格应用程序层OGSA的诞生，标志着网格不仅仅局限于科学计算领域，还能够对各种商业应用进行广泛的、基础性的网格环境的支持，实现更方便的信息共享和互操作，从而对商业模式、人员的工作方式和生活方式产生深远的影响。它致力于实现以下目标：跨分布式异构平台管理资源；交付无缝的服务质量；为自治管理解决方案提供公共基础；定义开放的、已公布的接口;利用行业标准的集成技术。WSRF随着网格的应用领域扩展，2004年1月，在美国旧金山召开的GlobusWORLD2004会议，就Globus的下一步发展方向进行了探讨，由Argonne实验室和IBM联合提出了WSRF(WebServiceResourceFramework)的概念。图2.2OGSA与WSRF的关系WSRF是在Grid网格技术和Web技术发展到今天的结合产物，其意味着网格和Web能在共同的基础上前进。WSRF针对OGSI的缺陷，提出了用无状态“stateless”服务来控制有状态“stateful”的资源。其架构提供了表示有状态资源的状态的方法，并且在Web服务和有状态资源之间建立起编码关系，称之为“隐含的资源模型”，使用的是常规的Web服务技术，特别是XML、WSDL和WS-Addressing。OGSI和WSRF关心如何处理有状态资源。然而，虽然这两种方法用的是不同的建模方式:一个是Gridservice，而另一个则是WS-Resource，但是其提供本质相同的功能，用语义上相似的WSDL接口定义。Gridservice和WS-Resource可以用同样的方法创建、访问、检测，以及销毁。这两种方法在概念上的主要区别在于WSRF用不同的结构为有状态资源和Web服务建{9{万方数据 第二章网格环境下的任务调度模，而OGSI则用同样的结构将有状态资源建模为支持GridServicePortType的Web服务。因此，严格来讲，WSRF比OGSI更具有表达能力，因为其允许Web服务和相关的有状态资源存在多对多的关系。这样就使得Grid技术更加适用于服务网格。Web服务资源(WS-Resource)结构是表示有状态资源和Web服务之间的关系的方法。Web服务资源框架是一组被提议的Web服务规范，它根据特定的消息交换和相关的XML定义来定义Web服务资源方法的描述。这些规范使程序员可以声明和实现Web服务和一个或者多个有状态的资源之间的关联。它们描述了定义资源状态的视图以及将它与Web服务描述相关联来形成Web服务资源的总的类型定义的方法。它们也描述了如何通过Web服务接口来访问Web服务资源的状态，并且定义了与Web服务资源分组和寻址相关的机制。图2.3WS-Resource结构示意图Web服务资源框架具有五个技术规范，它们根据特定的Web服务消息交换和相关的XML定义来定义了Web服务资源方法的标准化描述，包括：1.WS-ResourceLifetimeWeb服务资源的析构机制。包括消息交换，它使请求者可以立即地或者通过使用基于时间调度的资源终止机制来销毁Web服务资源。2.WS-ResourcePropertiesWeb服务资源的定义，以及用于检索、更改和删除Web服务资源特性的机制。3.WS-RenewableReferences使用在端点引用变成无效的时候所需要的用来检索更新版本的策略信息对于Web服务寻址(WS-Addressing)端点引用的约定的修饰。4.WS-ServiceGroup{10{万方数据 第二章网格环境下的任务调度连接异构的通过引用(by-reference)的服务集合的接口。5.WS-BaseFaults当Web服务消息交换中返回错误的时候所使用的基本错误。GLOBUSGLOBUS项目是目前国际上最有影响的与网格计算相关的项目之一，是美国国家实验室Argonne的研发项目。它发起于九十年代中期，其最初的目的是希望把美国境内的各个高性能计算中心通过高性能网络连接起来，方便美国的大学和研究机构使用，提高高性能计算机的使用效率。随着对GLOBUS项目的深入研究，针对它的目标也进一步扩展，希望通过GLOBUS项目可方便对地理上分布的研究人员建立虚拟组织，进行跨学科的虚拟合作。目前，GLOBUS项目把在商业计算领域中WebService技术融合在一起，希望不仅仅局限于科学计算领域，而且能够对各种商业应用进行广泛的、基础性的网格环境支持，实现更方便的信息共享和互操作，从而对商业模式、人的工作方式和生活方式产生深远的影响。GLOBUS系统中一个关键的元素就是GLOBUS工具包[26]，它定义了构建计算网格的基本服务和能力。工具箱由一系列组件构成来实现基本服务，如安全，资源定位，资源管理，数据管理，资源预定以及通信。从总体上讲，GLOBUS工具包的实现主要有四方面的内容：(1)网格安全，这是网格计算环境正常运行的保证，GLOBUS主要是结合目前成熟的分布式安全技术，并进行一定的扩展，以适合网格计算环境的特点;(2)网格信息获取与分布，在网格计算环境中如何发布资源信息，如何查询、检索资源信息是有效使用各种资源的前提条件;(3)网格资源管理，由于网格环境中的资源主要分布在广域网环境中，采用目前常用的局域网资源管理技术不能有效地对其进行管理，为此GLOBUS在局域网资源管理之上实现了更高层次的资源管理技术，在信息服务的支持下，可有效地支持广域范围内的资源管理;(4)网格远程数据传输，实现广域网环境下的高速、可靠的数据传输和实现对应用程序基本透明的远程文件I/0访问是GLOBUS考虑的重要内容。针对上述四个方面的内容GLOBUS项目实现的有以下主要组成部分：1.网格安全基础设施-GridSecurityinfrastructire(GSI)：GSI负责在广域网络下的安全认证和加密通信，提供单点登录功能、远地身份鉴别功能、数据传输加密功能等，提供了基于GSI协议的GenerieSecurityServicesAPI(GSS－API)接口。它是保证网格计算环境安全性的核心部分。2.GLOBUS资源分配管理[27]-GLOBUSResourceAllocationManage:(GRAM)：GRAM负责远程应用的资源请求处理、远程任务调度处理、远程任务管理等工作，负责对ResourceSpeci¯cationLanguage(RSL)信息的解析和处理工作，是网格计算环境中的任务执行中心。3.元计算目录服务-MetacomputingDirectoryService(MDS)：{11{万方数据 第二章网格环境下的任务调度MDS主要完成对网格计算环境中信息的发现、注册、查询、修改等工作，提供对网格计算环境的一个真实、实时的动态反映。MDS由两个组件构成，GIIS(GridIndexIn-formationService)和GRIS(GridResourceInformationService)。MDS遵循push和pull协议来分布资源。高层次的协议如资源代理可以通过使用LDAP协议查询MDS来发现资源。4.网格FTP服务[28]-GridFTP：GridFTP是一个高性能、安全、可靠的数据传输协议，并针对高带宽的广域网络环境进行了优化。具有支持第三方传输、断点续传、并行传输、与GSI结合的安全认证、缓存等特性。GLOBUS工具包的源码向公众开放，遵循GLOBUSToolkitPublicLicense(GTPL)协议，任何人都可以从网站上下载源代码并进行研究和改进。目前，GLOBUS工具包已在NASA网格(NASAIPG)、欧洲数据网格(DataGrid)、美国国家技术网格(NTG)等众多项目中得到应用。x2.3网格任务调度的特点和目标网格是一个基于广域网构建的分布式计算系统。在传统的并行和分布式调度问题中，所设计的计算资源是同构的，因此不必关心资源所具有的属性以及资源能否满足用户所提交的任务的需要，而且计算资源通常在地理上是集中的，因此不用关心系统在运行过程中通信所花费的开销。而网格的任务调度是网格的核心部分，它的重要性显而易见，无论是特定任务的执行性能，如时间、费用等，还是整个系统的吞吐率、资源利用率都受到任务调度质量的决定性影响。网格的调度同时又是极其复杂的问题，因为网格中包含大量异构资源，而且资源动态变化，多个任务引起资源竞争，如何充分利用网格中计算资源进行高效率合理地使用是调度的研究范畴，任务调度问题一直以来都是计算网格技术的关键技术和难点，对它的研究在基础理论和系统开发等方面都具有很大意义。网格计算任务调度系统具有以下几个特点[29]:1.任务调度必须具有可扩展性。网格系统初期的规模较小，随着网格资源的不断加入，系统的规模也必将随之扩大。因此，在网格资源规模不断扩大、应用不断增长的情况下，网格系统的任务调度必须具有可扩展性，不致降低网格系统的性能。2.任务调度是面向异构平台的。由于网格系统是由地理上分布的各类资源组成，资源分布在全世界，它们是异构的，可能运行在各种操作系统下。可能是超级计算机或者工作站或者机群系统、大型存储设备、数据库或其他设备。因此网格系统中的任务调度必须是面向异构平台的。3.任务调度能够动态自适应。网格中的资源不但是异构的而且网格的结构总是不停地改变:有的资源出现了故{12{万方数据 第二章网格环境下的任务调度障，有的新资源要加入到网格中，有些资源重新开始工作等。任务调度能够动态自适应这些变化。4.任务调度是大规模的、非集中式的。由于网格系统其资源跨越多个管理域，规模庞大，要实现一种全局的统一集中的任务调度管理是根本不可能的。因此，网格的任务调度必须以分布、并行方式进行任务的管理与调度。任务调度系统的主要目标就是要对用户提交的任务实现最优调度，并设法提高网格系统的总体吞吐率。具体的目标包括：最优跨度（OptimalMakespan）、服务质量QoS(QualityofService)、负载均衡(LoadBalancing)、经济原则(EconomicPrinci-ples)等⑴最优跨度。跨度是一个最主要的、最常见的目标.Makespan指的是调度的长度，即从第一个任务开始运行到最后一个任务运行完毕所经历的时间。跨度越短说明调度策略越好。⑵服务质量。网格系统要为用户提供计算和存储服务时，用户对资源需求情况是通过QoS形式反映出来的，任务管理与调度系统在进行分配调度任务时，保障网格应用的服务质量是完全应当的。⑶负载均衡。在开发并行和分布计算应用时，负载平衡是一个关键问题，网格系统更进一步扩展了这个问题。⑷经济原则。网格环境中的资源归属于不同的组织，都有各自的资源管理机制和政策。根据现实生活中的市场经济原则，不同资源的使用费用也应是不相同的。市场经济驱动的资源管理与任务调度必须使消费双方（资源使用者和资源提供者）互惠互利，才能使网格系统长久地发展下去。x2.4网格任务调度的原理在网格环境下，针对一个任务，从网格系统中发现可满足该任务资源需求的可用资源集。由于满足该条件的计算资源可能不止一个，但是该任务在这些资源上执行所获得的性能、付出的代价可能不一样，同样都是满足条件的资源，但是提供给使用者的质量会存在差异。任务调度首先要根据任务的需求，选择满足条件的资源，然后从满足条件的资源当中根据主要因素和选择策略选择一个更加合适的资源分配该任务。任务获得满足条件的资源后，可以在该资源上运行，并处在资源本地的任务管理机制的管理之下，任务在资源上运行结束之后，把占用的资源还给网格管理机构，网格任务管理模块把任务执行的结果和相关信息告诉任务的提交者，从而实现计算网格共享地理上分布的资源协同完成某个任务的目标。{13{万方数据 第二章网格环境下的任务调度x2.4.1任务调度的定义任务调度的相关定义如下[30]：在有m个处理单元和任务图G=(T,E)之上的调度是一个函数f，f将每个任务以某个特定的开始时间映射到某个处理单元。从形式上，一个调度可描述为：f:T!f1;2;L;mg£[0;1](2-4-1)如果存在，v∈T，f(v)=(i,t)，则表示任务v被调度到处理单元Pi上，且从时间t开始执行。函数f可以表示成如下定义的Gantt图。Gantt图用于直观地表示所有任务的开始时间和完成时间。在一个Gantt图中，有一个分布系统的处理单元表，对于表中每个处理单元都有一个任务分配表，即将分配到这个处理单元的所有任务按执行时间排列成表，其中包括开始时间和结束时间，分别用ST(tj,pi)和FT(tj,pi)表示。实际上，Gantt图是一个四元表：Gantt(pi,tj,ST(tj,pi),FT(tj,pi))其中，pi(i=1,2,⋯m)为处理单元；tj(j=1,2,⋯n)为分配到pi上的任务；ST(tj,pi)为tj在pi上的开始时间；FT(tj,pi)为tj在pi上的结束时间；一个任务调度系统的最大调度长度SL（ScheduleLength）定义为所有处理机pi中的XmaxfFT(tj;pi)g(2-4-2)ij调度的目标就是要将任务适当分配到处理机并协调任务之间的执行顺序，使得并行执行时满足并行任务之间的优先约束关系，而且SL最小。任务调度问题的最常见的目标函数就是完成时间ω（makespan）。基本上每个调度算法都需要估计系统中每个任务所需要的执行时间T可以把执行时间T分成两部分Tn和Tc。这里，Tn是经过网络发送数据到计算机m的时间加上从计算机上接受结果的时间，Tc是在计算机m上计算所用的时间。x2.4.2NP完全问题如果一个判定性问题的复杂度是该问题一个实例的规模n的多项式函数，则我们说这种可以在多项式时间内解决的判定性问题属于P类问题。P类问题就是所有复杂度为多项式时间的问题的集合。然而有些问题很难找到多项式时间的算法（或许根本不存在），比如找出无向图中的哈密尔顿回路问题，但是我们发现如果给了我们该问题的一个答案，我们可以在多项式时间内判断这个答案是否正确。比如说对于哈密尔顿回路问题，给一个任意的回{14{万方数据 第二章网格环境下的任务调度路，我们很容易判断它是否是哈密尔顿回路（只要看是不是所有的顶点都在回路中就可以了）。这种可以在多项式时间内验证一个解是否正确的问题称为NP问题。对于一个判定性问题，如果任何一个其它的NP问题都可以在多项式时间内等价地转化为该问题，则该问题称为“NP-hard问题”。如果一个判定性问题是NP问题，同时又是NP-hard问题，则该问题称为NP完全问题[31]（NPC问题）。对于任务调度，除少数小规模问题存在P算法外，大量调度问题属于NP问题，国际数学界研究NP问题的历史开始于20世纪70年代。1971年，Cook找到了第一个NP完全问题，寻求标准布尔方程解的问题(S问题)，开创了NP完全问题研究的历史。到目前为止，大约有几千个问题已被证明是NP完全问题。在网格计算中，当网格中有N个任务和能够满足N个任务的M个资源时，运用一个合适的任务调度策略可以在N个任务和M个资源之间进行匹配，使得总任务的完成时间最小以及资源得到充分利用。定义Fi为任务i的最后完成时间(即FT(v,p))，定义跨度时，则调度任务就是在2m个可能的资源子集空间中寻找最优集合使得跨度FmaxP和Fi最小。可见，网格计算的任务调度也是一个NP完全问题，至今没有找到可以精确求得最优解的多项式时间算法，由于指数型算法对解决规模较大的问题又十分困难，以求近似最优解为目的的启发性算法自然就受到了极大的重视，其中遗传算法是比较适合此类问题解决的算法。在本文中设计遗传算法适应度函数的规则为:当染色体makespan值越小，其适应度值就显著增加，染色体就越有可能被选出.这样在本文实验中,遗传算法相对收敛的时候所选定的染色体适应度值就最大,故对应的染色体的makespan值最小,任务完成时间最短。因此根据此时染色体编码所对应的资源在处理器分配及执行顺序方案最优,从而达到网格任务调度优化的目的。x2.4.3网格任务调度策略与过程Nimrod-G，AppLeS和Condor-G等都是目前应用较广泛的网格任务调度器，但他们都基于特定的调度策略，适用于特定情况的任务调度。Globus任务调度方法基本是轮循方式的；Nimrod-G采用应用程序级的基于微观经济模型的调度方法，适用于各个资源的定价机制都很完整的情况；App1eS采用应用程序级的调度方法，用网络气象服务监测资源性能的动态改变情况作为任务调度的依据，信息维护代价较高，且要求各节点间的连接都具有监测机制；Condor-G要求每个资源代理周期性广播其可提供的服务，客户代理广播其需求，匹配器执行集中式的任务到资源之间的匹配调度。可见，各种调度策略各有优缺点，在各种网格系统中都有不同的组合使用。在网格环境中，资源的多样性和不稳定性较传统分布式计算环境更明显，用户的应用需求也更加多种多样，能够适应所有网格资源结构的调度模式，将不得不考虑各种情形的折衷。一个典型的网格任务调度至少应包括作业提交、收集可用资源静态信息、资源预约、资源动态信息查询、制订调度计划和资源初始化以及作业运行时监控几个过程[32]:{15{万方数据 第二章网格环境下的任务调度1.作业提交用户作业的执行通常会涉及到分布式数据、网络资源、存储资源和软件资源等，这些资源需求可以通过脚本语言描述（如RSL）提交给网格调度系统。作业需求描述脚本包含了必要的信息足以判断资源是否能够满足需求。作业描述脚本应该包含三个方面的信息，一是作业本身的属性，如可以分成几个部分，相互之间的关系，一般被并行化理论抽象为DAG图的形式；第二是作业的约束条件，如作业完成的时间限制，服务质量等，可能还有在网格经济模型中的"费用"，"代价"的概念；第三是对实际静态资源的需求，如要求程序运行的操作系统，最小的内存要求、网络带宽等的要求。2.收集可用资源静态信息网格调度系统负责为用户提交的“需求清单”找到合适的资源，包括为作业进行资源调度、资源预约。这一过程主要是发现潜在资源的静态信息，即为用户的作业需求找到匹配的资源组合。调度器收到用户作业的需求报告后将其中的内容解析出来，之后，网格调度系统通过网格信息服务收集网络上可用的网格资源。此时，调度系统仅仅进行简单匹配，关不判断这些资源是否处于可用状态。3.资源预选资源预约的任务就是进一步筛选，使得只有一部分合适的资源能够进一步的进行匹配。这一过程可以通过许多启发式原则进行自动筛选或者在用户的干预下进行。4.资源动态信息查询作业运行时调度系统需要收集当前的资源信息并依次进行资源使用情况的预测。如当前资源是否是可用状态，否则预测什么时候可用。如果当前考查的资源不满足条件，则需要返回上一步对候选的下一个资源组合进行考查。5.制订调度计划和资源预约初始化这一步骤需要用到一些评价模型来决定资源组合，制订调度策略，发出资源预约请求，当某一个资源预约过程失败，那么调度器会选择后备的服务继续这一预约过程。6.作业运行时监控复杂的作业运行时间一般比较长，用户应该有权利在任务提交后到执行完毕的时间内查询任务的运行状态。监控服务负责的另一个职责是在作业运行满足一定条件时调度其它服务引起作业的下一个流程。x2.5现有任务调度算法介绍与分析由上面分析得知网格计算的任务调度是一个NP完全问题。近几年来，人们提出了很多启发性智能化算法，诸如神经网络、模拟退火、禁忌搜索、遗传算法、蚂蚁算法等，它们毫无争议地成为解决网格调度问题的锐利工具。下面简单介绍几种任务调度算法：禁忌搜索算法(TabooSearch或TabooSearch简称TS)的思想最早由GLOVER提出，它是对局部邻域搜索的一种扩展，是一种全局逐步寻优算法。组合优化禁忌搜索算{16{万方数据 第二章网格环境下的任务调度法可简单描述如下：算法首先确定一个初始可行解X，X可以从一个启发式算法获得或在可行解集合中任意选择：生成x的所有邻域，从中选择n个(一般取5个)最优的解，来定义可行解x的邻域移动集n(x)，从邻域移动中挑选一个最优的能改进当前解x的移动New(x)，再从新解x开始，重复搜索。如果邻域移动中只接受比当前解x好的解，搜索就可能陷入循环的危险。为避免陷入循环和局部最优，构造一个短期循环记忆表-禁忌表(TabuList)，禁忌表中存放刚刚进行过的一个邻域移动，这些移动称作为禁忌移动(TabuMove)。对于当前的移动，在以后的m次(一般取3次)循环内是禁止的，以避免回到原先的解，m次以后释放该移动。需要注意的是，由于当前的禁忌对象对应状态可能是最优选择，因此在算法中设置判断，若禁忌对象对应的适配值比最优状态值还要好，则无视禁忌属性而仍采纳其为当前选择，也就是所谓的藐视准则。模拟退火算法(SimulatedAnnealing，SA)[33]是1953年由Metropolis等人提出的，是基于退火物理过程(也就是低能晶体状固体的热量获得过程)的搜索方法。固体融化时会升高温度，如果温度是慢慢升高的，融化了的固体其颗粒会在局部排列，处于一个"稳定"的状态，而固体处于热量平衡状态，这是一个最佳状态。类似地，热量平衡是最优的任务一机器映射，温度是映射的总完成时间，温度的变化的过程就是映射变化的过程。如果下一个温度更高，那么就是一个更差的映射，下一个状态被接受的概率服从指数分布。接受一个"坏"的状态可能局部不是最优但是从全局考虑却是较优的。在模拟退火算法中，每两个温度之间的状态点是无关的。从理论上说，任何一个温度的马氏链都可逐渐达到平稳分布。即从一个状态到另一个状态随着迭代步数的增加渐渐不依赖于起点状态且在每一个状态的概率服从平稳分布。这种特性可以用来克服遗传算法中因为过于强调两代之间的进化关系而导致最优解遗失的缺点。蚁群算法ACA(AntColonyAlgorithm)[34][35]是近些年新出现的一种仿生类优化算法。1991年，意大利学者M.Dorigo等人提出蚁群算法由于该算法具有并行性、鲁棒性等优良品质，并且在求解TSP问题、调度问题和分配问题上有良好的效果，引起了众多学者的关注。蚁群算法是受到对真实蚁群行为研究的启发而提出的。生物学研究表明一群互相协作的蚂蚁能够找到食物源和蚁巢之间的最短路径，而单只蚂蚁则不能。蚂蚁个体之间是通过一种称之为信息素的物质进行信息传递的。蚂蚁在行进的途中会根据信息素的浓度选择路径，即路径上的信息素浓度越大，则蚂蚁选择该路径的概率也就越高。信息素会随时间的推移而挥发，同时蚂蚁在行进的过程中也会不断地分泌新的信息素，蚂蚁很少选择的路径上的信息素浓度会越来越低，而蚂蚁经常选择的路径上的信息素浓度则越来越高，并指导蚂蚁搜索到一条从蚁穴到食物源的最短路径。研究表明，将蚂蚁的搜索行为集中到最优解的附近可以提高解的质量和收敛速度，从而改进算法的性能，那么调度程序就能非常简单、快速地获得预测结果。但这种搜索方式会使早熟收敛行为更容易发生。除了上述调度算法之外，人们还提出了很多异构系统的启发调度算法，有不少论文试图把这些算法用于网格环境。有人提出了一个扩展的Su®erage，叫XSu®erage，可在网格环境中调度参数扫描应用[36]。Takefusa等人提出了一个期限调度策略，可适用{17{万方数据 第二章网格环境下的任务调度于多客户多服务器(MultiClientMultiserver)方式，并增加了能够改进算法性能的负载纠错(LoadCorrection)和退却(Fallback)机制[37]。SubrammaniV等提出了利用不同站点多同时请求的分布调度算法[38]。HeymannESenar等人提出了主人－工人(Masterworker)应用的调度策略，该策略能动态地检测任务的执行时间，并利用这个信息去动态地调整工人的数量，从而取得一个理想的工效[39]。x2.6本章小结本章介绍了网格的基本概念、特点及其体系结构，同时还介绍分析了网格任务调度相关的基本知识，研究了网格调度的概念和特点，网格任务调度原理和策略，分析了网格任务调度的过程，以及介绍了现有的网格调度算法，并且根据网格计算的任务调度也是一个NP完全问题这一理论分析结果，提出使用遗传算法来解决此问题。{18{万方数据 第三章遗传算法第三章遗传算法x3.1遗传算法的发展与特点生物的进化是一个奇妙的优化过程，它通过选择淘汰、突然变异、基因遗传等规律产生适应环境变化的优良物种。遗传算法是根据生物进化思想而启发得出的一种全局优化算法。在上世纪50、60年代，有几位计算机科学家独立进行了“人工进化系统”的研究，他们是利用进化的思想对实际的工程问题进行优化。这些研究形成了遗传算法的雏形。遗传算法的概念最早是由J.D.Bagley在1967年提出的，而开始遗传算法的理论和方法的系统性研究是1975年，这一开创性工作是由美国Michigan大学的J.H.Holland所实行。他将该算法用于自然和人工系统的自适应行为的研究中，并于1975年出版了其开创性著作《AdaptationinNaturalandArti¯cialSystem》[40]，该书详细阐述了遗传算法的理论，为其奠定了数学基础，发展了一套模拟生物自适应的理论，从而宣告了遗传算法的正式诞生。为了不至于混淆，我们把Holland所提出的算法称为标准遗传算法。1975年，DeJong基于遗传算法的思想在计算机上进行了大量的纯数值函数优化计算实验，树立了遗传算法的工作框架，得到了一些重要且具有指导意义的结论。Goldberg在1989年出版了《GeneticAlgorithminsearchoptimizationandMachineLeaning》一书，该书系统总结了遗传算法的主要研究成果，全面完整地论述了遗传算法的基本原理及其应用。1991年，Oavis出版了《HandbookofGeneticAlgorithm》一书，介绍了遗传算法在科学计算、工程技术和社会经济中的大量实例。1992年，Koza将遗传算法应用于计算机程序的优化设计及自动生成，提出了遗传编程(GeneticProgram-ming，GP)的概念[41]。从1985年在美国卡耐基·梅隆大学召开的第一届国际遗传算法会议到1997年5月IEEE的TransactionsonEvolutionaryComputation创刊，遗传算法作为具有系统优化、适应和学习的高性能计算建模方法的研究渐趋成熟。遗传算法由于其思想简单、易于实现以及表现出来的鲁棒性，得到了许多应用，在优化和搜索、智能控制、模式识别以及人工生命等领域均获得了令人鼓舞的成就。特别是对于那些传统搜索算法难以解决的复杂的和非线性的问题尤其适用。近年来，对于遗传算法的改进也有很多学者进行了大量研究。遗传算法具有许多十分独特的特点，主要有以下几个方面[43]：⑴遗传算法处理的对象不是参数本身，而是对参数进行了编码的个体，这使得遗传算法具有广泛地应用领域。⑵许多传统的搜索方法都是单点搜索算法，而单点搜索算法对多峰分布的搜索空间通常会陷入局部的单峰最优值，遗传算法采用同时处理群体中多个个体的方法，可以并行地爬过多个峰，减少陷入局部最优解的风险，故具有较好的全局搜索能力。⑶在标准的遗传算法中，基本上不用搜索空间的知识或其它辅助信息（如梯度值等），仅用适应度函数来评估个体，并在此基础上进行遗传操作，这一特点也使遗传{19{万方数据 第三章遗传算法算法的应用领域大大扩展。⑷遗传算法不采用确定性规则，而是采用概率规则指导它的搜索方向，这样看似盲目的搜索，实际上有明确的搜索方向。x3.2遗传算法基本原理与基本流程遗传算法和传统的搜索算法不同，遗传算法是从代表问题可能潜在解集的一个种群（population，即一组随机产生的初始解）开始搜索过程。而每一个种群则由一定数目的个体（individual）组成。种群中的每个个体是问题的一个解，称为染色体((Chromosome)，它经过基因（gene）编码（coding）而成。在遗传算法中最重要的概念是染色体，在生物学中染色体作为遗传物质的主要载体，其内部表现是某种基因组合，它决定了个体的形状的外部表现，如黑头发的特征是由染色体中控制这一特征的某种基因组合决定的。在遗传算法当中染色体通常是一串数据(或数组)，用来作为优化问题的解的代码，其本身不一定是解。初始种群产生之后，按照适者生存和优胜劣汰的原则，这些染色体在后续迭代中不断进化。在每一代中用适应度函数(Fitness)来测量染色体的好坏。生成的下一代染色体称为后代(O®spring)，后代是由前一代染色体通过交叉(Crossover)或者变异(Mutation)运算形成的。新一代形成中，根据适值的大小选择部分后代，淘汰部分后代，从而保持种群大小是常数，适值高的染色体被选中的概率较高，适值低的染色体被选中的概率较低。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境，经过若干代之后，末代种群中的最优个体经过解码（decoding），可以作为问题近似最优解。以下是一些有重要意义的相关生物学术语[42]：染色体(chromosome)生物细胞中含有的一种微小的丝状化合物。它是遗传物质的主要载体，由基因组成。遗传因子(gene)是控制生物性状的遗传物质的功能单位和结构单位，复数个基因就是染色体。基因座(locus)遗传基因在染色体中所占的位置。个体(individual)指染色体带有特征的实体。种群(population)染色体带有特征的个体的集合称为种群。种群规模(populationsize)群体中个体的数目称为种群大小。遗传算法是一个以适应度函数为依据，通过对群体个体施加遗传操作，实现群体内个体结构重组的迭代处理过程。它的基本步骤[44;45;46;47]如下：(1)编码在用遗传算法求解问题时，首先进行编码。将问题的解以适合于遗传算法求解的形式进行编码，称为遗传算法的表示。而交叉、变异等操作是与编码的形式有关的。因此在对问题进行编码时，要考虑到交叉和变异问题。(2)初始种群的生成{20{万方数据 第三章遗传算法产生初始种群是在求解之前，在解的备选空间中选择若干个体组成初始种群，通常产生初始种群采用的是随机法。(3)适应度评价检测根据生物进化"适者生存"的原则，需要对每个个体适应环境的能力进行刻画，从而引入适应值，适应度值是遗传算法在群体进化过程中用到的唯一的信息，它为如何进行复制给出了定量的描述。适应度函数通过计算个体的适应度，来比较个体的适应度。(4)选择种群中的个体在进行交叉之前，要进行选择。选择的目的是获得优的个体作为父代，进行下一步的交叉。选择的依据是个体的适应度，适应度值高的个体被选中的可能性大，适应度低的个体被选中的概率小。适应度高的个体可能被多次复制，而适应度低的个体可能一次也未被选中。(5)交叉交叉也称为交配，即将两个父代个体的编码串的部分基因进行交换，产生新的个体。交叉是模拟生物的繁殖活动。交叉是种群遗传算法中的重要算子，是种群产生新个体的主要手段。(6)变异变异操作首先在种群中随机选择一个个体，对于选中的个体按照一定的概率随机改变结构中的某个值，即对种群中的每一个个体，以某一概率改变某一个或某一些基因座上的值为其他的基因。同生物界一样，遗传算法中发生变异的概率很低。变异为新个体的产生提供了机会。(7)终止条件判断终止条件判断是指在什么情况下认为算法找到了最优解，从而可以终止算法。由于通常用遗传算法解决具体问题时，并不知道最优解是什么，也不知道其最优解的目标函数值，因而需要通过算法终止，并获得最优解。标准遗传算法的流程图如图3.1所示。x3.3遗传算法的理论基础遗传算法模拟生物的进化机理，但是这种进化机理本身只是对生物进化现象的说明，并没有逻辑必然性。人们试图从理论上对遗传算法加以解释，其中最著名的是模式定理。模式定理基于特定的编码和基因操作准则，从数学分析的角度提供了遗传算法的运行机理的解释，从而构成了遗传算法的理论基础。同时，依据模式定理，研究者证明了遗传算法的隐含并行性[48]。x3.3.1模式定理Holland[49]的模式定理作为描述遗传算法动力学机理的基本定理，奠定了遗传算法的数学基础。{21{万方数据 第三章遗传算法随机产生N个个体构成初始种群P(0),令k=0种群P(k)中各个个体进行评估Y算法条件是否满足输出优化结果N令m=0执行选择操作,从父代种群选择二个体对选中个体执交叉概率大于ε?行交叉产生二Y个临时个体N将选中父代个体作为临时个体对二临时个体以变异概率Pm进行变异产生的二个新的个体并放入P(k+1),令m=m+1Y判断mk¤N显然改进的算法在产生同样个数的子染色体时能大大减少其适应度的计算量，并且段重新组合后又不致于减少搜索空间的大小。因而能加快收敛过程并能找到目标解。2.算法实现本文DAG图4.1有8个任务，则染色体总长度为16，其中分配字串和调度字串长各为8。假设分割长度L＝4，则每个染色体可以生成k＝4个染色体段。所有染色体根据适应度值由大到小进行排序。例如，假设有染色体CHR1：TTTjTTTjTTCjTTCjTTTjTTTjTTCjTTCjTTTjTTCjTTAjTTGjTCTjTCCjTCAjTCG染色体CHR2：TTTjTTCjTTTjTTCjTTTjTTCjTTCjTTTjTTTjTTCjTTGjTTAjTCCjTCTjTCAjTCG则染色体CHR1可分为以下四个段：C11：TTTjTTTjTTCjTTCC21：TTTjTTTjTTCjTTCC31：TTTjTTCjTTAjTTGC41：TCTjTCCjTCAjTCG染色体CHR2可分为以下四个段：C12：TTTjTTCjTTTjTTCC22：TTTjTTCjTTCjTTTC32：TTTjTTCjTTGjTTAC42：TCCjTCTjTCAjTCG其中段群体为PU1＝｛C11，C12，⋯⋯，C1n｝；PU2＝｛C21，C22，⋯⋯，C2n｝⋯⋯PUk＝｛Ck1，Ck2，⋯⋯，Ckn｝然后分别找出第i(i=1,2,⋯,K)段群体中第g+1代中最优染色体段。不妨以i=3为例。因为i=3，则i=1，2的段群体第g+1代中最优染色体段已经找出且为C11，C21。i=4的段群体第g代中最优染色体段已经找出且为C41。现在需将PU3＝｛C31，C32⋯⋯C3n｝中每个染色体段按照公式进行适应度值计算。找出N个中最大的一个命名为C31，其余按照适应度值大小对染色体段排序。计算出所有染色体段第g+1代，然后拼接成完整的染色体。{41{万方数据 第四章基于改进遗传算法的网格任务调度设计x4.2.6遗传算法结束条件遗传算法的迭代停止条件目前还没有定论。在网格环境中，适应度的最优解并不清楚，次优解适应度下限也很难确定。本文判断是否达到最大遗传代数，如果满足，则停止计算，输出统计数据。x4.3本章小结本章对基于DAG图的任务调度策略进行分析，并建立网格任务调度系统模型。然后针对遗传算法早期收敛等缺点，提出改进的DNAGA调度算法，并根据算法流程设计实现方式。染色体的编码采用混合的间接编码模式，先按一维分离编码方式根据任务调度的特点编码，然后转换为DNA编码这一特殊的编码方式来实现。种群的初始化时，采用基于调度子串合法性判断的初始种群生成方法来生成。适应度函数的设计充分考虑必须符合的要求，能更好地区分染色体的优劣。选择、交叉、变异等遗传算子的实现充分考虑到网格任务调度和DNA编码的特点，并实现了新增的基因级的遗传操作：倒位操作和轮转操作。最后还针对传统的遗传算法搜索空间大、计算量重，使用一种改进的快速收敛的方法来计算适应度值。我们将在下一章对本章提出的改进算法进行验证。{42{万方数据 第五章仿真实验及分析第五章仿真实验及分析x5.1网格仿真及常见工具在真实的网格环境中有效地实现任务调度是网格研究的最终目标，但是就目前情况来看，使用仿真工具分析模型和算法是非常重要的。网络仿真是一个很有用的网络研究技术，它以系统理论、形式化理论、随机过程和统计学理论优化理论为基础。随着网络新技术的不断出现和数据网络的日趋复杂，对网络仿真技术的需求必将越来越迫切，网络仿真的应用也将越来越广泛，网络仿真技术己成为研究、规划、设计网络不可缺少的工具。网络仿真技术是一种通过建立网络设备、链路和协议模型，并模拟网络流量的传输，从而获取网络设计或优化所需要的网络性能数据的仿真技术。网格模拟器的出现，给出了一个可行的模拟环境。目前网格调度仿真工具主要有：1.SimGridSimGrid[57]为模拟异构的分布式环境下的分布应用而提供了一系列的核心函数。它的基础模拟环境是分布式计算平台，能够模拟网络拓扑结构、资源、任务的处理等。SimGrid提供了相当多的函数，使得模拟具有很大的灵活性，但整个过程显得比较繁琐和复杂，需要用户有一定的经验。2.GridsimGridsim为网格有效资源分配技术的研究提供一个模拟环境。它的基础模拟环境是网格计算平台，主要是市场经济的网格计算平台。它能够模拟异构且分布全球的资源、简单的网络、资源的查找、任务的虚拟处理等。而采用面向对象技术构建，整个框架比较清晰。3.MicrogridMicrogrid[58]是为了研究网格资源管理而提供的一个虚拟的网格基础设施。它是建立在Globus平台上的，因此它的基础仿真环境是利用Globus工具包建立起来的网格环境。很好地仿真了资源的行为、网络、任务的处理、资源发现等。仿真结果接近实际，但需要用Globus构造实际的网格任务，因此适用于实际系统开发过程中对调度算法的仿真评测。4.BricksBricks[59]的研究集中在计算网络全局计算系统调度策略模拟上，重点在模拟多用户多服务器回家资源分配策略。本论文采用Gridsim模拟器进行仿真实验。{43{万方数据 第五章仿真实验及分析x5.2GridSim网格模拟器GridSim[60]最初是由澳大利亚墨尔本大学的RajkumarBuyya于2001年发布的一个基于Java语言开发的网格仿真工具，它可用于对集群、对等计算和网格等分布式计算环境[61]中的调度算法进行建模和仿真。GridSim是基于SimJava基础开发的模拟器。它的核心部分GridSimCore、GridSim都是SimEntity的子类。GridSim是基本开发包，包含网格基本要素的模拟表达。通讯以及线程管理的基本功能由GridSimCore实现，它是GridSim的父类，管理了模拟任务、资源以及动态信息。SimJava提供丰富的函数库以支持模拟网格环境中的异构资源(时间共享和空间共享)、用户、应用程序、用户代理和调度器。网格资源、用户和用户代理被视为不同的实体，它们通过消息事件(输入和输出)来进行通信。除了通过手工编程来实现模拟外，GridSim还提供了一套图形接口工具VisualModeler(VM)帮助用户配置网格环境并产生相应的代码。仿真结束后，用户可以调用GridSim中的GridStatistics的库函数来收集各种模拟的统计资料。GridSimToolKit没有明确定义应用程序模型，对于各种类型的任务和应用程序，不同的网格拓扑，以及对调度算法的设计和评估等问题，都是由用户自行解决的。因此，GridSimToolKits存在二次开发的问题。x5.2.1GridSim体系结构与实体模型GridSim作为网格的模拟环境，能够模拟异构且分布于全球的资源、简单的网络、资源的查找、任务的虚拟处理等。体系结构如图5.1：Application，User,GridScenario’sInputandResultsApplicationResourceUserGrid...OutputConfigurationConfigurationRequirementsScenarioGridResourceBrokersorSchedulersGridSimTookitApplicationInformationJobResourceStatisticsModelingServicesManagementApplicationResourceModelingandSimulation(withTimeandSpacesharedSchedulers)SingleCPUSMPsClustersLoadPatternNetworkReservationBasicDiscreteEventSimulationinfrastuctureSimJavaDistuibutedSimJavaVirtualMachine（Java，Cjvm,RM）PCsWorkstationsSMPsClustersDistributeResources图5.1Gridsim平台和组件的体系结构{44{万方数据 第五章仿真实验及分析第一层，JAVA接口和Java虚拟机（JVM）,JVM支持单个或多处理器，包括集群。第二层，利用第一层提供的接口，建立基本的离散事件基础结构，比较流行的是SimJava。第三层，包括核心网格实体模拟{资源，信息服务等，应用程序模型，统一访问接口，应用模拟原语，和建立更高层次实体的框架。主要利用第二层的离散事件服务模拟系统实体。第四层，模拟资源聚集，网格ResourceBroker或Scheduler。第五层，不同情境下的资源和应用建模，利用第三层和第四层提供的服务，评估调度，资源管理策略，算法。在进行仿真期间，Gridsim建立一系列的多线程实体，每个实体都并行的在各自线程中运行。每个实体行为的仿真实现都是通过自身的body()方法实现的。基于Gridsim的仿真包括有用户，代理，资源，以及信息服务实体。(l)用户实体：每个用户实体都代表一个网格用户。由用户来定义一个或多个任务。每个用户具有以下特征如:任务的执行时间，描述任务的参数数量；调度优化的策略；时区；任务的截止时间和预算等。(2)代理实体：BrokerR1R2R3任务接收资源查询UserNetwork调度原则Gridlet分发Gridlet接收GIS图5.2Broker资源代理的基本构架每个用户实体直接与代理打交道。用户的任务首先提交到代理，代理再根据用户定义的调度策略，对参数化的任务进行调度。图5.2为Broker代理实体基本构架。Broker主要由用户实体(UserEntity)、实验台(Experiment)、Broker、资源(BrokerResource)构成。其中用户实体和Broker是GridSim的子类，具有Body方法。实验台是对用户提交任务的封装。用户实体代表网格用户，在Body中向网格提交封装请求任务的实验台实例，并等待返回。Broker完成与网格核心的交互。它在Body方法中向GIS请求资源，并将获得的资源保存在Broker资源中。Broker资源维护相对应资源的动态信息，包括资源属性等等。{45{万方数据 第五章仿真实验及分析(3)资源实体：每个资源实体都代表一个网格资源；每个资源可以包含多个处理器数量；每个资源的处理成本可以不一样；每个资源具有不同的处理速度；资源的速度和任务执行的时间通过MIPS(MillionInstructionsperSecond)进行描述。(4)网格信息服务实体：网格信息服务实体提供资源注册服务和对可用资源的列表进行跟踪。代理通过对网格信息服务实体的查询获得资源配置和状态的信息。x5.2.2GridSim仿真的步骤与软件的安装利用GridSim进行网格仿真实验的一般步骤：1.初始化仿真进行仿真的第一步都是要对Gridsim包进行初始化，否则会出现运行时错误。GridSim.init(numuser,calendar,trace°ag,excludefrom¯le,excludefromprocessing,reportname);其中的参数分别表示:：建立的用户实体的数量，仿真开始的时间，是否对Gridsim进行跟踪的标志位，在统计中需要排除的文件列表的字符串数组，不需要写入文件的处理过程的字符串数组，和一个报告实体名字。执行完此语句自动产生四个实体对象:GridsimRandom，Gridstatistics，Gridlnformationservice，和Gridsimshutdown。2.创建用户具体实现步骤为：(1)创建任务在GridSim系统里，需要调度的任务由Gridlet对象表示。必须创建任务对象GridletGridletgridlet1=newGridlet(id,length,¯lesize,outputsize);//创建Gridlet建立任务所使用的Gridiet包中，包含了相关任务的所有信息和任务执行管理的具体细节，比如用Ml表示的任务长度，输入和输出文件的大小，以及任务所有者的id。(2)创建用户列表ResoureeUserListuserList=newResoureeUserList()；用户与任务的分配：在分别创建好用户列表和任务列表后，就可以将任务分配到个人，这可以通过在任务列表中通过对每个任务分配一个用户id获得。具体实现的语句为：((Gridlet)list.get(i)).setUserID(id);3.创建资源在GridSim系统里，一个网格资源由一个或者多个机器(Machine)组成，而一个机器又是由一个或者多个PE(ProcessingElementsorCPUs)组成。创建的PE要放到PEList(处理器列表)里去，而PEList又需加入到Machine里去。PE1=newPE(id,capability);//创建处理器对象PEListpelist=newPEList();//创建处理器列表对象Pelist.add(PE1);//将处理器加入列表{46{万方数据 第五章仿真实验及分析创建计算机：Machinemachine1=newMachine(id,pelist);//创建计算机列表创建资源：GridResourcegridres=newGridResource(name,bandrate,seed,resCon¯g,peak-Load,o®PeakLoad,holidayLoad,Weekends,Holidays)//创建网格资源。4.编写自定义的调度策略继承GridSim对象，在body()方法力编写调度算法。classmyGAGRIDSIMextendsGridSimf......Publicvoidbody()//调度算法g5.启动模拟在任务资源都设置后通过调用GridSim.startGridSim()函数就可以进行Gridsim的仿真。6.结束时输出任务完成情况PrivatestaticvoidprintGridletList(GridletListlist)本实验采用gridsimtoolkit-4.1版本的软件包，需要JavaSDK1.5或以上版本。下载安装好JavaSDK并配置好对应的环境变量，然后下载GridsimToolki压缩包，直接解压即可。编译运行Gridsim时，操作如下(以运行自带的实例程序为例)：(1)进入实例程序文件夹InUnixorLinux:cd$GRIDSIM/examples/Example01InWindows:cd%GRIDSIM%nexamplesnExample01(2)编译Java源程序InUnixorLinux:javac-classpath$GRIDSIM/jars/gridsim.jar:.Example1.javaInWindows:javac-classpath%GRIDSIM%njarsngridsim.jar;.Example1.java注意：在Windows环境下为分号加点号再空格加文件名．(3)运行JavaClass文件InUnixorLinux:java-classpath$GRIDSIM/jars/gridsim.jar:.Example1InWindows:java-classpath%GRIDSIM%njarsngridsim.jar;.Example1注意：在Windows环境下为分号加点号再空格加文件名．说明：$GRIDSIM或%GRIDSIM%是GridSimToolkit的安装路径x5.3仿真模块设计在基于DNAGA调度算法下，本文设计了以下模块来建立网格系统模型，并能根{47{万方数据 第五章仿真实验及分析据不同场景和参数来评估调度算法的性能。（1）MainGridSim模块：完成仿真模拟系统的实现，并对各个模块之间进行调用，并且创建用户，资源等基本信息。（2）GUIGA模块：负责使用图形化用户界面来输入遗传算法的基本参数。（3）DNAGAChromosome模块：由于遗传算法的所有操作都是围绕染色体个体进行的，所以，在本论文改进遗传算法的实现中为染色体个体单独定义了一个模块来实现几乎所有与染色体有关的操作．例如初始种群的生成，染色体的选择，适应度函数的计算，染色体的交叉操作，变异操作，倒位操作和轮换操作。程序主要内容如下：publicclassDNAGAChromosomefpublicListinitChromosome(intPOPSIZE)f⋯⋯//按照个体生成规则，生成初始种群gpublicdouble¯tnesscalculate(string[]chromosome)f⋯⋯//计算适应度函数gpublicvoidcrossoverPopulation(Chromosomech1，Chromosomech2)f⋯⋯//交叉操作gpublicvoidmutation(Chromosomech)f⋯⋯//变异操作gpublicvoidreverse(Chromosomech)f⋯⋯//倒位操作gpublicvoidround(Chromosomech)f⋯⋯//轮转操作g⋯⋯{48{万方数据 第五章仿真实验及分析g（4）DNAGA模块：此模块为改进遗传算法的主程序，按照改进遗传调度算法流程实现网格任务调度，在执行遗传调度算法的各步骤时以调用DNAGAChromosome模块里的各方法接口。DNAGA模块序主体如下：publicclassDNAGAfintMAXGEN;//定义最大遗传代数intPOPSIZE;//定义种群数目doublePC;//定义交叉概率doublePM;//定义变异概率doublePR=0.5;//定义轮转概率doublePV=0.5;//定义倒转概率double¯tness;//定义适应度值......publicvoidMYGA()f//初始化染色体种群Chromosomechros=newChromosome();Listcl=chros.initChromosome(intPOPSIZE);......while(gen·MAXGEN)//当前代数小于最大代数时执行f......//进行遗传操作并调用各个遗传操作函数......for(i=1;i·k;i++)//按照长度L，可以把每个染色体分为k段，则k为段群体数目.freplace(chromosomenewchr);//计算新产生的2m个子染色体(2m¿N)的段适应度值，替换PUi中段适应度值小的2m个染色体;for(j=1;j·POPSIZE;j++)//POPSIZE为种群数目f......segment¯tness(chromosome);........gg//endforg//endwhileg//endMYGAg//endclass{49{万方数据 第五章仿真实验及分析x5.4实验结果与分析本节将对基于改进的DNAGA算法的网格任务调度在模拟器中进行实验，并给出实验结果，同时对结果进行算法性能分析。本实验采用GridSimToolkit-4.1版本的软件包，Java2SDK1.5，操作系统为WINDOWSXP，ProfessionalSP2，CPU:IntelPentium43.06GHz，内存为1.00GB。本文仿真实验基本流程如下图5.3所示：开始获得DAG作业图和信息资源初始化Gridsim模拟器采用改进遗传算法进行任务调度把任务映射到相应的资源求出完成时间等参数值并记录下来结束图5.3仿真实验基本流程动态建立生成任务DAG比较复杂，因此本文实验预先建立静态的DAG，使用相同的DAG可以更好的进行算法的比较。本文给出由100个子任务和500个子任务负载组成的二个DAG图进行测试。并且二个遗传调度算法在每次实验中观察点处的任务完成makespan值都被记录下来。因为遗传算法是一种随机搜索算法，每一次运行的结果都不相同。为了消除遗传算法随机性的影响，更好的反应算法性能，实验曲线结果图中的每个数据都经过15次测试取得的平均值。对于实验终结条件，本文设定为达到最大遗传代数就终止。并且认为如果算法连续50代没有出现显著的更优解，即可认为算法基本收敛。在进行仿真实验前需要设置参数，主要为网格任务调度参数和遗传算法参数。对于网格任务调度，实验测试模拟5个不同属性、配置、能力的计算资源，每个计算资源都有自己不同的处理器个数，资源的处理器能力用MIPS来描述，并且这5个用于测试的资源是不同的地区。本文创建10个用户，每个用户10个作业和50个作业，对应100个子任务和500个子任务负载组成的DAG图，每个作业长度创建为1000MI。计算资源实验参数如下图5.4：{50{万方数据 第五章仿真实验及分析图5.4网格资源的参数对于遗传算法的参数，标准遗传算法GA需要设置最大遗传代数(MaxGEN)，种群大小(PopSize)，交叉概率(Pc)和变异概率(Pm)等参数。遗传算法的参数设置如下图5.5：图5.5遗传算法的参数由于DNA遗传算法增加了倒位和轮转操作，所以基本参数与标准遗传算法相同的基础上，添加了倒位操作概率Pv=0.5和轮转概率Pr=0.5。遗传算法基本参数通过GUI界面输入如下图5.6所示。图5.6参数输入界面(1)图5.7和图5.8所示的算法性能曲线，表示在任务数为100和任务数为500时在5个{51{万方数据 第五章仿真实验及分析计算资源节点上进行任务分配的仿真结果。算法性能曲线显示标准遗传算法和改进的DNAGA算法在不同的进化代数时任务完成时间(makespan)值。由图5.7和5.8可知，与标准遗传算法相比，基于改进DNAGA的任务调度算法在算法基本收敛的时候，任务完成时间所得到的值更小，即能获得更优解，说明改进后的DNAGA比标准遗传算法更具有全局搜索性。而且改进后的DNAGA在相对收敛时所需要的进化代数也比标准遗传算法要少，说明在进行遗传进化时，改进的DNAGA算法所增加的基因级遗传操作－倒位操作和轮转操作增强了种群的多样性，使得任务完成时间更快的向最优解靠近。图5.7在任务数为100时GA与改进的DNAGA算法任务完成时间对比曲线图5.8在任务数为500时GA与改进的DNAGA算法任务完成时间对比曲线{52{万方数据 第五章仿真实验及分析(2)图5.9所示为标准遗传算法和改进的DNAGA算法网格任务调度系统仿真平台上运行时间比较图，该图是在任务数为100和任务数为500时在5个计算资源节点上进行任务分配的仿真结果。图5.9标准GA与改进的DNAGA在任务数不同情况下系统运行时间由图5.9可知，标准遗传算法与基于改进的DNAGA任务调度算法的系统运行时间，一方面随着任务数的增加而计算资源不变的情况下，即从任务数为100增加到任务数为500时，系统运行的总时间会急剧的增加。这是因为随着任务数的增加，任务之间的关联和通讯变的更为复杂，从而处理的时间也需要更多；另一方面，在相同任务的条件下，基于改进的DNAGA任务调度算法所需要的运行时间总比标准遗传算法的运行时间要多，而且随着任务数的增加改进DNAGA调度算法运行时间的增长更快。这主要是因为改进的DNAGA任务调度算法增加了二个遗传操作，而且还需要进行DNA编码和解码，这样比标准遗传算法更为复杂，从而增加了系统运行时间，而且随着任务数的增加，执行倒位和轮转操作的染色体串的长度大大加长，从而进一步增加了系统运行的时间。(3)由于基于遗传算法的网格任务调度涉及到网格任务的参数和遗传算法的参数，本文将针对参数对系统的影响进行研究。下图5.10为调整网格任务中计算资源的个数后在Gridsim网格仿真平台下得到的仿真结果。其中T表示相对收敛时任务完成时间，G表示相对收敛时的代数。由图5.10可知，当任务数不变增加计算资源节点时，任务完成时间是下降，并且取得最优解的遗传进化代数也相应的减少。这是因为增加计算资源后提高了系统并发处理的能力，网格任务完成时间必然下降。而且在相同情况下基于改进DNAGA调度算法的任务完成时间要比标准遗传算法的少，表明改进DNAGA具有明显的优势。另一方面，当计算资源数不变而增加任务个数的时候，任务完成时间上升。最后，我们发现在每种情况下，改进的DNAGA基本收敛代数总是要比标准遗传算法的要小，也表明改进的DNAGA的收敛速度要快于标准遗传算法，这是因为在相同条件下，改进{53{万方数据 第五章仿真实验及分析图5.10标准GA与改进的DNAGA在不同任务数和资源数下性能比较的DNAGA每次可以产生更多类型的染色体，加快了收敛速度。(4)对相对快速收敛改进的方法与标准遗传算法在收敛速度方面进行比较。本文在GridSim仿真平台中，创建10个用户，每个用户10个作业，对应子任务负载100组成的DAG图，每个作业长度创建为1000MI;计算资源数为5，每个计算资源都有自己的处理器。遗传算法参数相同：最大遗传代数(MaxGEN)为400，种群大小(PopSize)为80，交叉概率(Pc)为0.5，变异概率(Pm)为0.01。图5.11为使用标准遗传算法和改进的遗传算法适应度值随运行时间变化情况：图5.11采用改进的方法的适应度变化曲线图5.11最下一条曲线为使用标准遗传算法(即K=1的情况)解决网格任务问题的适应度随时间变化曲线，中间和上面的二条都为使用改进的遗传算法时的适应度随运行时间变化曲线，其中上面的曲线为K=8的情况下适应度随运行时间的变化，中间的曲线为K=4的情况下适应度随运行时间的变化曲线。从图5.11的对比可以看出：在取相同遗传算法参数的条件下，标准遗传算法适应度随运行时间增长的比较缓慢，而改进的遗传算法能比标准遗传算法能够在较短的时间内使适应度值迅速增加，从而极大加快了收敛速度。而且从图5.11可以发现：同样使用{54{万方数据 第五章仿真实验及分析改进的遗传算法，当K的值增加的时候适应度值增加的更快，即收敛的速度变得更快。(5)图5.12所示为标准遗传算法和改进的DNAGA算法在相对收敛的情况下网格任务调度完成时间比较图，该图是在任务数为100和任务数为500时在5个计算资源节点上进行任务分配的仿真结果。图5.12GA与改进的DNAGA算法在相对收敛时网格任务调度完成时间对比曲线从图5.12的对比可以看出：在取相同遗传算法参数的条件下，无论是任务数为100还是任务数为500,标准遗传算法得到的网格任务调度时间都比较长，而改进的遗传算法能比标准遗传算法能够获得更短的网格任务调度时间。所以从图5.12可以发现：使用本文的改进方法后，对网格任务调度的主要指标:网格任务调度完成时间有比较明显的缩短,从而提高了网格任务调度的效率。(6)图5.13所示为对相对快速收敛改进的方法与标准遗传算法在相对收敛时所花费仿真时间方面进行比较。本文在GridSim仿真平台中，创建10个用户，每个用户10个作业，对应子任务负载100组成的DAG图，每个作业长度创建为1000MI;计算资源数为5，每个计算资源都有自己的处理器。遗传算法参数相同：最大遗传代数(MaxGEN)为400，种群大小(PopSize)为80，交叉概率(Pc)为0.5，变异概率(Pm)为0.01。图5.13最左一条为使用标准遗传算法(即K=1的情况)在相对收敛时的网格任务仿真时间，中间和右面的二条都为使用改进的遗传算法在相对收敛时的网格任务仿真时间，其中右面的为K=8的情况下网格任务仿真时间，中间的为K=4的情况下网格任务仿真时间。从图5.13的对比可以看出：在取相同遗传算法参数，任务数为100且资源数为5的条件下,标准遗传算法(即K=1的情况)在相对收敛时所需要的仿真时间比较长，而改进的遗传算法能比标准遗传算法能够获得更短仿真时间时间。而且从图5.13可以发现：同{55{万方数据 第五章仿真实验及分析图5.13在资源数为5时GA与改进的DNAGA算法在相对收敛时仿真时间对比曲线样使用改进的遗传算法，当K的值增加的时候仿真时间缩短的更快，即仿真的速度变得更快，从而可以大大提高网格任务调度系统的运行速度。x5.5本章小结本章首先对本文将要使用的网格仿真模拟器Gridsim的体系结构和主要的实体作了相关介绍，接着对本论文的算法实验环境进行了描述，随后介绍了改进的DNAGA算法的模块实现，最后进行仿真实验。实验表明改进的DNAGA网格任务调度策略在任务完成时间上比标准遗传算法更短；在遗传基本收敛的情况下，遗传收敛代数更小；在相同运行时间情况下，收敛速度比标准遗传算法有很大的提高。因此提高了网格任务调度的效率，提升了整个网格系统的性能。{56{万方数据 第六章总结与展望第六章总结与展望x6.1本文的工作和成果网格计算是将分布的计算机组织起来协同解决复杂的科学与工程计算问题，以满足益增长的计算需求。互联网的指数增长，超级计算机广泛使用以及配件的低耗费都将使网格的来临进一步变为现实。任务调度是网格计算中一个至关重要的问题，其算法将直接影响到网格环境中任务执行的效率以至成败。本文在广泛阅读国内外关于网格计算和遗传算法的文献后，归纳了网格环境和遗传算法的特点，对网格中的任务调度算法进行改进，主要的工作体现在以下的几个方面：首先，系统介绍了网格计算与任务调度的相关概念，突出了网格环境下研究任务调度算法的重要性；详细阐述了网格任务调度的特点、任务的模型以及调度算法的研究现状。然后，基于基本遗传算法原理提出了一种适合于网格计算环境的改进的DNA遗传算法，并将其作为网格任务调度技术的核心策略来更合理的调度网格资源。其中染色体采用DNA编码，除了标准遗传算法的选择、交换、变异算子外，还引入倒位操作算子，并且增加了新的基因级操作(算子)：轮转算子，使之更符合生物进化规律，更适合遗传算法。这样既保持种群多样性，有效避免早熟收敛出现，又增强了全局搜索的能力。另外，本文提出了一种改进的快速收敛的方法。通过调整标准遗传算法结构，增加了对染色体的分割与重组操作，使标准遗传算法能快速收敛。最后，本文通过网格模拟器对网格任务调度技术进行模拟，并设计基于图形界面的遗传算法参数输入功能，对实验结果进行分析。x6.2未来展望由于网格计算是刚刚兴起的广域网络计算研究领域，许多研究模型和算法都还带有实验性质，非常不成熟。虽然国内外已取得一些研究成果，但仍存在大量的研究课题。本文总结了目前网格项目里使用的任务调度算法，根据网格的特点，设计了基于改进的DNA遗传算法的网格任务调度策略，在此基础上，下一步的工作主要包括：首先，本文提出的相关模型、算法和机制都是从对计算网格任务调度策略改进的角度出发的。但是在验证时，由于实验室环境和其他方面的限制，该算法采用仿真工具测试，构建在一个虚拟的网格环境中，因此实验数据以及对这些数据的分析、评估在真实网格环境中会有偏差。所以，后续的研究搭建实际的网格平台，并在其基础上展开实验来验证改进的遗传调度算法是否满足用户的需求，并针对不足进一步完善。其次，本文在算法设计中力图考虑一般网格调度特性，但是由于网格任务调度是一个极其复杂的系统，因此我们定义的任务特性，主要侧重考虑了子任务在资源上的{57{万方数据 第六章总结与展望执行时间等关键因素。实际网格中任务特性应该包括更多的网络因素，例如资源负载率、资源稳定性等。另外，本文算法侧重最优化调度时间和收敛代数上，没有考虑容错机制以及服务质量、网络安全等因素。因此，在今后的工作中应该添加更多的影响因素，使之更符合实际网格的工作环境。总之，尽管现在的研究工作充满了困难，但是作者坚信随着网络的快速发展，下一代网络必然会对人们的生活方式产生更深的影响。因而本文的研究方向是正确，研究工作是有意义的。{58{万方数据 参考文献参考文献[1]SandraJeanV.Chua,PaulEchevarria,JoseMariMendoza,Rene-RusselleSantos,StanleyTan,BayanihanComputing.NET:GridComputingwithXMLWebSer-vice[C],Proceedingofthe2ndIEEE/ACMInternationalSymposiumonClusterCom-putingandtheGrid(CCGRID'02),2002IEEE[2]WolfgangGentzsch.GridComputing,AVendor'sVision[C],Proceedingofthe2ndIEEE/ACMInternationalSymposiumonClusterComputingandtheGrid(CCGRID'02),2002IEEE.[3]M.Revett,I.Boyd,C.Stephens."Networkcomputing:atutorialreview"[J].Elec-tronics&CommunicationEngineeringJournal,February2001,13(1):5-15[4]MingXu."E®ectiveInternetGridComputingforIndustrialUsers"[J].IEEE,2001,34-40[5]HEXiaoshan，Xian-HeSun，GregorVonLaszewski.QoSGuidedMin-minHeuristicforGridTaskScheduling[J].JournalofComputerScience&Technology，2003.5:442-451.[6]刘恕．中国国家网格正式开通[J]．科技日报，2005年12月12日．[7]I.FosterandC.Kesselman.Globus:AMetacomputingInfrastructureToolkit[J].InternationalJournalofSupercomputerApplications.USA:SagePublications,199711(2).115-128[8]Frey,J.,Tannenbaum,T.,Livny,M.,Foster,I.,Tuecke,S.Condor-G:acomputa-tionmanagementagentformulti-institutionalgrids[C].HighPerformanceDistributedComputing,2001.Pages:55-63[9]Dongarra,J.Netsolveanditsapplication.NetworkComputingandApplica-tions,2001.NCA2001[C].IEEEInternationalSymposiumon,8-10Oct.2001.Pages:21-21[10]SpoonerDP,JarvisSA.LocalGridSchedulingTechniquesusingPerformancePredi-tion[J],IEEEProceedings-ComputersandDigitalTechniques,2003,150(2):87-96[11]W.E.Johnston,D.Gannon,B.Nitzberg.GridsasProductionComputingEnvi-ronments:TheEngineeringAspectsofNASA'sInformationPowerGrid[C].EighthIEEEInternationalSymposiumonHighPerformanceDistributedComputing,RedondoBeach,CA,Aug.1999[12]R.Buyya,H.Stockingeretal.Economicmodelsforresourcemanagementandschedul-inginGridcomputing[J].TheJournalofConcurrencyandComputation:PracticeandExperience(CCPE)SpecialissueonGridcomputingenvironments,2002.{59{万方数据 参考文献[13]JohnP.Stenbit.MovingPowertotheEdge[M].CHIPS-TheDepartmentoftheNavyInformationTechnologyMagazine,Volume21,Issue3,Summer2003.[14]CatlettC.ThephilosophyofTeraGrid:buildinganopen,extensible,distributedTeraS-calefacility[C].ClusterComputingandtheGrid2ndIEEE/ACMInternationalSym-posiumCCGRID2002,21-24May2002.Pages:5-5.[15]http://www.stdaily.com/gb/stdaily/2007-10/13/content729893.htm.[16]10.1021/ja077679s,Mary-AnnThyveetil,PeterV.Coveney,H.ChrisGreenwell,andJamesL.Suter[M].《美国化学会志》(JACS)2008.3[17]http://www.sciencetimes.com.cn/htmlpaper/2008321161561431530.html.[18]ArmstrongR,HensgenD,KiddT.TheRelativePerformanceofVariousMappingAlgo-rithmisIndependentofSizableVarianceinRun-timePredictions[A].In:Proceedingsofthe7thHeterogeneousComputingWorkshop(HCW'98)[C].USA:IEEEComputerSoci-etyPress,1998,79-87.[19]HongtuChen,MaheswaranM.DistributedDynamicSchedulingofCompositeTasksonGridComputingSystem[A],In:ProceedingsoftheInternationalParallelandDis-tributedProcessingSymposium(IPDPS'02)[C],2002.88-97.[20]SubramoniamK,MaheswaranM,ToulouseM.TowardsaMicro-EconomicModelforRe-sourceAllocationinGridComputingSystems[A],In:Proceedingsofthe2002IEEECanadianConferenceonElectrical&ComputerEngineering[C],Manitoba:IEEEPress,2002,2,782-785.[21]徐志伟,冯百明,李伟《.网格计算技术》[M].北京：电子工业出版社，2004年,6-8页.[22]FosterI.whatistheGrid?AThreePointCheeklist[M].GridToday，July22，2002，3-4.[23]贾明非,董渭清,桂小林,白雪柏.网格资源管理系统模型研究[J].微电子学与计算机,2003,3:36-40.[24]郝泳涛,方丁,林琳,等，基于OGSI的网格计算研究综述[J].计算机应用研究,2005,18(04):18-20.[25]清华大学高性能所网格研究组,《以服务为中心的网格体系结构》2002.[26]JoshyJoseph，CraigFellenstei.网格计算[M].战晓苏、张少华译.北京:清华大学出版社,2005.1:55-164.[27]SinggG,BharathiS,ChervenakA,etal.AMetadataCatalogServiceforDataIn-tensiveApplicationsProceedingofSupercomputing2003(SCZO03)[J].Chicago:IEEEPress.2003:45-49{60{万方数据 参考文献[28]LeeJ,GunterD,TierneyB,etal.AppliedTechniquesforHighBandwidthDataTrans-fersAcrossWideAreaNetworks[J].ProceedingofInternationalConferenceonCom-putinginHighEnergyandNuclearPhysics.Beijing:2001:168-175[29]罗红,幕德俊,邓智群.网格计算中任务调度研究综述[J].计算机应用研究,2005，22(5):16-19.[30]Frey,J.,Tannenbaum,T.,Livny,M.,Foster,I.,Tuecke,S.Condor-G:acomputationmanagementagentformulti-institutionalgrids[J].HighPerformanceDistributedComputing,2001.Pages:55-63[31]DAVIDS.JOHNSON.TheNP-CompletenessColumn[J].AT&TLabs-Research,FlorhamPark,NewJersey.ACMTransactionsonAlgorithms,Vol.1,No.1,July2005,pp.160-176[32]Maozhenl,MarkBaker网格计算核心技术[M].王相林，张善卿，王景丽译.北京:清华大学出版社，2006.12:165-172.[33]LeongH.w.WongD.E.,LiuC.L.ASimulatedAnnealingChannelRouter[J].ProcIEEEInternational.ConferenceonComputer-AidedDesign，SantaClara，CANovem-ber1985，226-229[34]MarcoDorigo,VittorioManiezzo,AlbertoColomi.AntSystemOptimizationbyaColonyofcooperatingAgents[J].IEEETRANSACTIONSSYSTEMMANANDCYBER-NETICSPARTBCYBERNETICS,1996,26(1):1-13[35]DorigoM.,G.DiCaro&L.M.Gambardella.AntAlgorithmsforDiscreteOptimization[J].Arti¯cialLife,1999,S(2):137-172[36]CasanovaHLegrand，AZagorodnov，DBerman.HeuristicsforSchedulingParameterSweepApplicationsinGridEnvironments[C].Proceedingsofthe9thHeterogeneousComputingWorkshop，IEEE，LosAlmaitos，2000.3492363.[37]Takefusa，ACasanova，etal.AStudyofDeadlineschedulingforClient-SevrersystemsontheComputationalGrid[C].Proceedingsofthe10thIEEEInternationalSymposiumonHighPerformanceDistributedComputing，IEEE，LosAlmaitos，2001.4062415.[38]SubrammaniV，etal.DistributedJobSchedulingonComputationalGridsUsingMul-tipleSimultaneousRequests[C].Proceedingsofthe1lthIEEEInternationalSymposiumonHighPerformanceDistributedComputing，IEEE，LosAlmaitos，2002.3592367.[39]HeymannESenar，MALuque，etal.AdaptiveSchedulingforMasterworkerAppli-cationsontheComputationalGrid[M].SpringerVerlagHeidelberg，2000.[40]J.H.Holland,AdaptationinNaturalandArti¯cialSystems[M],UniversityofMichiganPress.AnnArbor,Ml，1975{61{万方数据 参考文献[41]HansenP，MladenovicN.Variableneighborhoodsearch:Principlesandapplications[J].EuropeanJournalofOperationalResearch.2001，130:449-467[42]王小平，曹立明.遗传算法-理论、应用与软件实现[M].西安:西安交通大学出版社，2002.[43]张国良等.遗传算法及其应用[M].北京人民邮电出版社,1996.[44]GoldbergD.E.GeneticAlgorithmsinSearchOptimizationandMachineLeaning[M].Addison-Wesley，1989.[45]MitchellM.AnIntroductiontoGeneticAlgorithms[M].Cambrige，MA:TheMITPress，1996.[46]WhitleyLD.FoundationsofGeneticAlgorithms2[M].SanMateo，CA:MorganKau-¯mann,1993.[47]WhitleyID，VoseMD.FoundationsofGeneticAlgorithms3[M].SanMateo，CA:MorganKau¯mann,1995[48]张文修,梁怡.遗传算法的数学基础[M].第二版.西安:西安交通大学出版社，2003:80-120[49]席裕庚,柴天佑等.遗传算法综述[J].控制理论与应用，1996，13(6):697-708[50]BookerLB，GoldbergDE，HollandJH.Classi¯erSystemsandGeneticAlgorithms[J].Arti¯cialIntelligence，1989，40:135-282[51]KozaJ.RGeneticProgrammingontheProgrammingofComputersbyMeansofNat-uralSelection[M].MITPress，1992[52]WYoa，B.Linad,J.You.GeneticSchedulingonMinimalProcessingElementsintheGrid[J]，LNCS2557，Springer-Verlag，Berlin，(2002)465-476.[53]钟求喜.网络计算中任务分配与调度的遗传算法研究[D]，博士.长沙:国防科技大学，2000.[54]ADLEMANL.MolecularComputationofSolutiontoCombinatorialProb-lems[J].Science，1994，266(11)：1021-1024[55]丁永生,邵世煌,任立红.DNA计算与软计算[M]．北京：科学出版社，2002．45-47[56]贺晓丽,基于遗传算法的分布式系统任务调度问题研究[D].青岛大学硕士论文，2003[57]HenriCasanova.SimGrid:AToolkitfortheSimulationofApplicationScheduling[C].ProceedingsoftheFirstIEEE/ACMInternationalSymposiumonClusterComputingandtheGrid,pp.430-437,2001{62{万方数据 参考文献[58]HSong,JLiuetal.TheMicroGrid:aScienti¯cToolforModelingComputationalGrid[J].Scienti¯cProgramming,2000;8(3),127-141.[59]AtsukoTakefusa.Bricks:APerformanceEvaluationSystemforSchedulingAlgorithmsontheGrids[J].JSPSWorkshoponAppliedInformationTechnologyforScience,2001.[60]BuyyaR,MurshedM.GridSim:AToolkitfortheModelingandSimula-tionofDistributedResourceManagementandSchedulingforGridComput-ing[J].TheJournalofConcurrencyandComputation:PracticeandExperi-ence,WileyPress,2002,14(13-15):1175-1220[61]GranvillLZ，DaroseDM，PanissonA，eta1．Managingcomputenetworksusingpeer-to-peertechnologies[J]．IEEECommunicationsMagazine，2005，43：62-68.{63{万方数据 致谢致谢在硕士研究生学习即将结束之际，向三年中给我许多帮助的老师同学们表示衷心的感谢。首先要由衷的感谢我的导师黄文明副教授。在专业学习方面，从选题到开题给我很多启发性的指导;从学术论文到毕业论文，在内容格式等方面都进行了详细的修改。并提出许多建设性的意见并指出不足。在科研方面，每当遇到难以解决的难题，黄老师都能提出合理可行的解决方案。黄老师待人真诚，思维活跃，乐观豁达，在学习生活上给我细心的关怀，让我能在舒适的环境中工作学习，在此衷心感谢导师!同时，还要真诚感谢读研期间各位任课老师们，你们的辛勤劳动为我以后的学习研究打下了基础。感谢与我一起学习的各位同学们:黄斌、陈庆全、兰静、殷波、崔亚楠、黎勇、张敏等。在生活当中相互关心，照顾;在学习当中相互启发，鼓励。这求学的三年是我人生中十分难忘的日子。同时也还感谢彭希为、肖朝霞、李美瑾、黄松发、李元旺等师弟师妹谨以此文献给我敬爱的亲人们，你们二十多年来始终如一对我的支持，理解和鼓励使我走到了现在。感谢高燕，在我研究生学习期间对我的生活和精神上给予了无私的照顾和安慰，使我专心学业。最后，感谢在百忙当中评审论文的各位老师，你们辛苦了!{64{万方数据 作者在攻读硕士期间主要研究成果作者在攻读硕士期间主要研究成果A.参与的科研项目：1.负责2008年广西研究生教育创新项目《基于网格的数字化校园关键技术的研究》；2.承担桂林市自来水公司管网科工程管理系统开发．B.发表的论文：1.张阳,黄文明,兰静.一种基于改进遗传算法的网格任务调度策略[J].《计算机系统应用》(核心期刊),2009年7月；2.兰静,黄文明,张阳.网格调度中具有价格激励的改进蚁群算法的研究[J].《计算机系统应用》，2009年3月；3.兰静,黄文明,张阳.基于改进蚁群算法的网格资源调度研究[J].《北京邮电大学学报》，2009年4月；C.获得的奖励：1.2006-2007年度桂林电子科技大学优秀研究生奖学金；2.2007-2008年度桂林电子科技大学优秀研究生奖学金；3.2008-2009年度桂林电子科技大学优秀研究生奖学金；{65{万方数据