《环境下基于时间和可靠性的调度策略.pdf》由会员分享，可在线阅读，更多相关《环境下基于时间和可靠性的调度策略.pdf（6页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第33卷第9期2016年9月计算机应用研究Application Research of ComputersV0133 No9Sep2016云计算环境下基于时间和可靠性的调度策略余盛季，魏恺明，李强，郭迅(电子科技大学计算机科学与工程学院，成都610000)摘要：云计算中，调度策略对于用户任务的运行和服务提供方均有很大的影响，直接影响到云平台的运行效果。针对传统任务调度算法难以适用于云计算环境这一问题进行了研究，采用由星型结构演化而成的多代理模型，给出了多代理模型的体系结构，然后针对多代理系统，提出了基于服务时间和可靠性为优化目标的任务调度策略，并采用模拟退火算法进行求解。最后进行了仿真实验，
2、实验结果表明提出的调度策略是高效的。关键词：多代理系统；调度策略；服务时间；服务可靠性；多目标优化中图分类号：TP393 文献标志码：A 文章编号：10013695(2016)09267306doi：103969jissn1001-3695201609025Task scheduling strategy based on service time andreliability in cloud computingYu Shensi，Wei Kaiming，Li Qiang，Guo Xun(School of Computer ScienceEngineering，University of
3、Electronic Science&Technology of China，Chengdu 610000，China)Abstract：In cloud computing，task scheduling strategy has a great impact on the operating results of the userS task and theservice providerS profitTherefore，it has a direct impact on the cloud computing platformTo solve the problem that the
4、traditional task schedding algorithms could not suitable for cloud computing，this paper proposed a task scheduling strategyFirstly，based on multi-agent system(MAS)extended from star structure，it described the multiagent system structureThen，it put forword a scheduling strategy considering the servic
5、e time and reliability as optimization targets，and employed asimulated annealing algorithm to solve the optimization problemFinally，simulation experiments show the efficiency of theproposed scheduling strategyKey words：muhi-agent system；scheduling strategy；service time；service reliability；multiobjec
6、tive optimization当今分布式计算技术的发展日新月异，社会网络已经步入大规模网络时代，大多现实的系统往往异常复杂、庞大，并且呈现出分布式的特点。与此同时，科研和商业任务的计算量也变得越来越庞大，这就导致单个计算系统因为个体拥有的知识、计算资源以及视图的有限，不足以胜任当前网络环境下大数据量任务。而多agent系统(MAS)联合多个计算节点，共同执行计算任务的特性，使得大任务的高效快速处理成为了可能。MAS合理运用了对复杂问题分而治之的方法，将众多节点的计算能力进行组合运用，使大数据量任务最终能够快速可靠地完成。20世纪70年代，agent的概念首先出现在人工智能领域。随后，多名研
7、究者给出了agent的定义：Wooldrige等人旧。用几种方式给出了agent的定义；ShohamH o提出agent是由信念、目标、能力以及义务组成，agent是一个精神实体。多agent系统联合众多节点的计算能力，可以成功执行大数据量任务。但是，为了使任务执行更加高效，调度策略的选择就显得至关重要。调度策略对于用户任务的运行和服务提供方的收益均有很大影响，它直接影响到云平台的运行效果。目前，已经存在许多任务调度策略的研究，经典的启发式调度算法有MinMin、MaxMin、Sufferage等，主要以执行时间为算法评价指标。随着更多应用在云计算环境中的部署和执行，以任务可靠性为中心的任务调
8、度技术成为国内外的研究热点。阎朝坤等人。4 o分析了网格计算环境下面向可靠性一费用优化的任务调度模型，提出了基于CRO的优化调度算法。王朋51分析了云计算环境下的任务调度策略，提出了一种改进的多因素组合的任务调度算法。王莉等人旧。根据网格环境下任务的时间相关性特点，对传统的蚁群算法进行了改进，提出了一种快速任务调度算法。刘莉等人o针对异构集群下高效节能的任务调度算法进行了研究，提出了一种基于复制的任务调度算法。谢丽霞等人8。在分析现有云计算调度模式的基础上，提出了分层调度策略。Xiang等人一。提出了基于服务利润最大化的任务调度策略。Levitin等人。1 0提出了基于服务时间最短的任务调度策
9、略。本文在云计算环境下，采用多agent系统处理用户任务，并对任务调度策略进行研究。1任务调度模型下文首先介绍多agent系统模型结构，然后介绍单个agent的内部结构以及全局agent和执行agent的功能，最后介绍不同agent之间的通信。收稿日期：20150515；修回日期：20150701作者简介：余盛季(1980)，男，重庆大足人，讲师，博士研究生，主要研究方向为云计算(sjyuuestceducn)；魏恺明(1994)，男，宁夏银川人主要研究方向为系统优化；李强(1988一)，男，安徽宿州人，硕士，主要研究方向为多agent系统、可靠性等；郭迅(1973)，女，重庆人，高级工程师。
10、硕士，主要研究方向为系统建模及优化万方数据2674 计算机应用研究 第33卷11 多agent系统模型多agent系统的概念出现至今，已经有多种系统模型被提出。比如Bonnell等人于1995年提出了一种基于智能自治agent结构的分布式计算系统模型。本文在Meng等人21提出的系统模型基础之上进行研究，这个模型将多agent技术与星型网格计算系统相结合，采用全局agent和执行agent对整个网络进行分治，系统模型整体采用了三层树型拓扑结构。多agent系统模型结构如图1所示。l 多：【系统模7删结构12单个agent结构Agent是一种具有智能特性的控制实体，它接收到外界信息以后，会根据已
11、有的控制逻辑、知识以及规则对这些信息进行处理，随后将处理结果转发出去n 3|。为了增加系统的容错性和可靠性，本文在agent中设计了智能控制回路，它作为agent的核心部分存在。从功能上，多agent体系中定义了两种agent，全局agent和执行agent。它们的结构基本相同，唯一区别在于感知模块。Agent结构如图2所示。智能控制回路如图2中虚线所圈部分。a削l 1感知模块卜厂_1规则库IIagent 任 一任务分析模块卜_ 代飞务 理 通I聊t 分 监 信配 控一 模模 模 块块 一结果收集模块卜 块l j1一agenll可提交队列l I任务缓冲区l图2 Agent结构图下面是agent
12、中各模块的具体描述。a)通信模块。该模块是智能控制回路(MAAC)同外部环境进行通信的接口，它定义两方的通信标准。b)代理监控模块。主要有四个功能：(a)负责整个系统同外部环境间的所有通信；(b)负责将外部收到的任务信息经过一定的处理(安全处理，如解密等)交付给任务分析模块；(C)负责可提交队列和不可提交队列的操作；(d)负责接收结果收集模块传过来的结果。c)任务缓冲区。用来缓存外部环境发过来的任务信息，以避免外界大量信息同时来临所造成的来不及处理事件。此处采取同步方式，向缓冲区存入一个信息和从缓冲区读取一个信息是互斥进行的，从而保证了缓冲区中的内容是正确有效的。d)规则库。该部分定义了age
13、nt之间通信的消息和任务的数据格式。e)感知模块。全局agent和执行agent的功能有所不同，将在下一节详细介绍。f)任务分析模块。该模块负责将上一级传来的数据、规则库和agent感知模块中的信息融合在一起，按照固定的格式组成消息，即消息生成器。g)任务分配模块。该模块是消息在执行agent和全局agent之间传递的中间处理模块。它具备两个功能：(a)将上一级任务分析模块传过来的消息进行加密处理并设置相关的权限，然后再向其执行agent集群发送任务广播报文，通知它们新任务的相关信息；(b)解密执行agent发过来的处理结果，并把它传给结果收集模块。h)结果收集模块。该模块将任务分配模块传递过
14、来的任务处理结果送入可提交队列，并通知代理监控模块向外部环境发送处理结果。i)可提交队列。用来存储任务执行后的结果，以避免多个任务同时处理完成时造成的全局agent来不及处理事件。此处也是采取同步方式，结果收集模块向其入队与代理监控模块从其出队是互斥的，以保证处理结果的正确性和有效性。13全局agent和执行agent全局agent负责从外部环境接受任务，并将任务经过分析后组成任务广播，在它所属的执行agent中广播。其结构如图2所示。全局agent通过agent感知模块获得执行agent的信息，以此确定对执行agent的任务分配。执行agent结构也如图2所示。其负责响应全局agent发出的
15、任务广播，在接收任务后为其管理的计算节点分配任务，待计算节点执行完任务返回结果后，向全局agent报告任务执行结果。执行agent通过计算节点感知模块获取计算节点的信息，并下发任务。全局agent和执行agent，它们的结构基本相同，唯一区别在于感知模块：a)全局agent感知模块。它负责收集本全局agent所属的所有执行agent信息，并将这些信息存储。b)执行agent感知模块。其任务是收集本执行agent所属的所有计算节点信息，并将这些信息存储在该模块的存储部分。这些信息主要包括计算节点的处理速度和故障率、计算节点同执行agent之间通信信道的数据传输率和故障率等。14 Agent间通信
16、通信是多agent系统中最重要的部分。各agent间的任务分配、数据传递、结果反馈等重要的消息传递都是靠通信来完成。系统中除全局agent在下发任务时会采用广播和应答形式，其他的消息传递都采用点对点形式。全局agent接收外界计算任务后，多agent系统开始工作，各agent间通信流程如下：a)全局agent接收到任务的第一时问就会对其分析，分析完成后将任务的需求等相关信息组成一个任务消息，然后将消息在它的执行agent集群中广播。b)每一个有效执行agent在接收到广播的消息后，根据自身的能力和状态以投标作为应答，用于表明它可以完成该任务的意图和能力。c)全局agent在规定的时间内接收到所
17、有投标申请后，根据一定标准抉择出最佳投标执行agent，然后将任务分配给其执行。d)执行agent在得到最后执行结果后，将执行结果上报给万方数据第9期 余盛季，等：云计算环境下基于时间和可靠性的调度策略 2675全局agent。2 基于服务时间和可靠性的任务调度策略一个完整的系统，除了结构的设计以外，控制调度策略是另一个不可或缺的部分。控制调度策略就像人脑一样，控制协调着整个机体的运行。它的效率决定着系统能否快速完成相关任务。本文将建立基于服务时间和服务可靠性的调度策略，系统将借助于它进行最优调度策略的选择。系统对任务的划分以及计算节点的分配策略如图3所示。执行agent在收到全局agent发
18、出的任务后，会对任务的特性(任务的计算复杂度、任务输入数据块的数据量、任务输出数据块的数据量等)和执行agent中计算节点的参数特征(计算节点的处理速度、计算节点的故障率、数据通信信道的速度、数据通信信道的故障率等)进行分析，然后把任务合理划分成一系列EB(执行块)模块，并把它们分配给合适的计算节点进行执行。广_l执,行agentI一图3 计算节点分配和任务划分策略图21 相关假设首先，对系统模型提出一些假设，以便于推导计算。a)计算节点接收到执行agent的任务，便马上开始执行，完成后，立刻将结果返回给执行agent。b)计算节点在一定时间内拥有恒定的故障率以及处理速度，且计算节点之间发生故
19、障是相互独立的，与外部环境无关。c)通信信道拥有恒定的传输速度以及故障率，且信道之间发生故障是相互独立的，与外部环境无关。d)EB中的子任务按顺序执行，且子任务的执行时间与计算节点处理速度成反比，与其复杂度成正比。e)数据在计算节点与执行agent间的传输时间与数据量成正比，与信道传输速度成反比。f)通信信道与计算节点的故障率是恒定的(热备份模型)，与是否处于负载状态无关，且它们之间发生故障是相互独立的。g)系统中执行agent绝对可靠，其处理任务(划分EB、将EB发送给计算节点、收取计算节点执行结果、集成计算节点的执行结果并把最终结果发送给全局agent)所花时间与计算节点执行任务的执行时间
20、相比可忽略不计。h)全局agent绝对可靠，其执行时间可忽略不计。22服务时间和服务可靠性已知用户提交给全局agent的任务为中，执行agent将这个任务划分成可单独执行的m个子任务，然后将这些子任务划分成h个EB模块，一个EB模块至少包含1个子任务，将EB模块定义为or。，它们互不相交，则得到式(1)：hU盯。=西，盯nak=o i#k (1)21EB划分好之后，将这些子任务分配给计算节点处理。已知有g(g)个计算节点，若将计算节点集定义为力，把计算节点集划分成h个互不相交的计算节点子集山。(与之前划分好的EB集合一一对应)。于是得到式(2)：Uw。=12，。nq=o ij (2)21由前所
21、述可知，任意一个EB。由一个子任务的序列or。构成。已知c，代表计算节点执行子任务j的时间复杂度，因此得到执行一个EB的时间复杂度公式：C。三01 jo-i (3)每个子任务j需要一个输入数据集曰，子任务处理后的输出数据量为0，则子任务集EB的数据输入集合为u曰，。由此可知要处理一个EB，从执行节点传输到计算节点的数据量为Xlfl(xU曰，)，J，代表子任务z的数据量，n代表EB。输入数据集合的大小。因此一个计算节点完成一个EB任务(从接收数据到输出结果)，执行agent与计算节点问的数据传输总量为Di= ()+ (“u弓) (4)_lOjlori 善1IxIx 1 E口，其中，n代表EBi中
22、子任务的数量。计算节点或通信信道执行过程中可能出现故障，这样可以认为EB任务集在节点执行的时间为无穷大，因此EBi计算节点J完成时间f。由两种可能取值组成：i=；i=+导EBi被计算节点J成功执行 r 51【zi=m otherwise，EB。被计算节点j执行失败其中，辑代表节点J的处理速度，s，代表通信信道的传输速度。当给定计算节点J与信道之间的恒定故障率后，可以得到EB被成功执行的概率：n(fI，=；i)=e一1，+咿d (6)假设任意一个任务集EB。被分配给一个计算节点集。，计算节点集之间不共享计算节点，这种情况下，单个EB。执行成功所花时间为0。=min(ti) (7)当所有子任务(包
23、括最慢的那个)都完成后，整个任务就结束了，所以整个任务的完成时间为最慢完成的那个子任务的执行时间。由此可知整体任务完成时间公式为耻l戮9w。2lm“axmi。n(。) (8)通用生成函数技术(UGF)“，也被称做M函数，它可以非常明确地表达出节点的性能状态以及概率，可快速地由单个节点的通用生成函数得到整个系统的性能通用生成函数。这里先对完成时间进行求解。首先运用通用生成函数技术计算单个EB的完成时间。当EB。被分配给单个计算节点J时，完成时间的概率密度函数如下：吨，小：)=毋(；F)zF+1一pj(；口)=。 (9)其中：屯表示EB。由计算节点，执行的完成时间，由式(5)可得到。p，(；。)表
24、示EBi被成功执行的概率，由式(6)得到。现在考虑一般情况，EB。被分配给一个计算节点集。假设计算节点集为皑=kl一，k。，1ng，则其完成时间的概率密度函数可由以下递推方式求出：It引kl,吲(：)2Ui,l klz)黜州k2 z)“叫kl,k2,k31。=Ui,札吲2傺3“ (10)叱H(2)引kl,-(。)引忆。(z)Q“引kn(z)万方数据2676 计算机应用研究 第33卷得到计算单个EB的完成时间概率密度函数后就可根据它导出执行整个任务的完成时间概率密度函数。因计算节点相互独立，所以每个计算节点对于EB任务的计算是同时进行的，因此整个任务的完成时间取决于执行时间最长的那个EB任务。下
25、面由递推方式可求出最终任务完成时间的概率密度函数：ul(z)=1。(一血r)接受s作为新的当前解。f)如果满足终止条件则输出当前解作为最优解，结束程序。终止条件通常取为连续若干个新解都没有被接受时终止算法。g)r逐渐减少，且弘加，然后转步骤b)。通过模拟退火算法可以求出最长服务时间和最低服务可靠性两种需求下的最优任务划分和资源分配方式。(11) 3仿真实验与分析Uh(z)=Uh一1(：)OUh(：)最终，得到“函数巩(z)的形式如下：，U(z)=五Q产叩 (12)其中：，和Q，分别表示整个任务完成的时间和相应时间完成任务的概率，当0，=时表示任务执行失败。当得到了每一个EB。的时间f。概率分布
26、后，就得到了整个任务的执行时间9的概率分布(通过非连续的变量的概率密度函数)。其形式为(9r，QI)，O，F，其中r是的第厂个取值，Q1=Pr(=of)，F是的所有可能取值的个数。那么，平均服务时间形和服务可靠性R公式即为F形2舌唧Q，ol。(13)，尺2磊Q，1 哆。 (14)23调度策略根据用户对任务的不同需求，需要选择不同的策略。这里分别对用户给定最长服务时间和最低服务可靠性两个需求进行研究。当用户对服务时间有要求时，会给定最长服务时间o+，此时的约束条件就是平均服务时间形小于等于用户给定的最长服务时间0+，执行agent的调度策略就是在保证平均服务时间形0+的情况下，找到最佳的任务划分
27、和资源分配方式，使服务可靠性R最高。当用户对服务可靠性有要求时，会给定一个最低可靠性值R。，此时的约束条件就是服务可靠性R大于等于给定的最低可靠性R一，执行agent的调度策略就是在保证服务可靠性月月。的情况下，找到最佳的任务划分、资源分配方式，使平均服务时间矽最短。24调度策略的求解调度策略已经在上一节中给出，根据调度策略得出的结果是一种最优的任务划分和资源分配方式。而这类最优值求解问题实则是一类组合优化问题，在此使用模拟退火算法5进行最优策略的选取。模拟退火算法一般是从某一个较高的初温开始，伴随着温度参数不断下降并且结合概率的突跳特性在整个解空间中很随机地寻找满足目标函数全局最优的解，同时
28、它还可以在局部的最优解概率性地跳出来并且逐渐趋于全局最优解。模拟退火算法可以分解为解空间、目标函数和初始解三部分。模拟退火算法的计算过程如下：a)初始化：初始温度r(充分大)，初始解状态5(是算法迭代的起点)，每个r值的迭代次数。b)对k=1，L执行步骤e)一f)。e)产生新解S。d)计算增量At=C(S)一c(s)，其中c(s)为评价函数。e)若At0则接受Js作为新的当前解，否则以概率exp31 给定最长服务时间需求在本原则中，外部用户的要求是给定了一个最长的执行时间，即外部用户把执行时间放在了最重要的位置。这时候执行agent的调度策略就是在满足一定的情况下使整个执行agent系统的可靠
29、性R(0)达到最高。311一个执行agent假设只有第一个执行agent有效。本文基于前面的公式利用模拟退火算法对该优化模型进行求解。这里分别给出最短的执行时间为200、300、400。即要求执行agent的最终执行时间不能超过上面的数字。最终的任务划分和计算节点的分配如表1所示。表1 第一个agent中不同最短执行时间下任务划分和计算节点的分配计算节点序号o+】 2 3 4 5 6 7 8 9与表1对应的各个最短时间下的最大和最小时间以及相应的可靠性如表2所示。表2第一个agent中不同最短执行时间下服务的执行时间和可靠性从上面两个表的结果中可以看出，给定了不同的0+，那么就会得到不同的任务
30、和计算节点的分配，这些分配下并不一定是全局最优的分配解，只是相对的全局最优解。当给定的0+越来越大的时候，执行agent就越来越倾向于把更多的子任务放置在同一个EB中，即越大EB的个数就越少，而这时系统的可靠性就越高，这是因为同一个EB会有更多的计算节点冗余地执行它，这样就大大增加了可靠性。相反，给定的0 4越小，执行agent就越倾向于划分更多的EB并把这些EB平均分配给计算节点集，这样就会导致执行时间更短，但是任务的可靠性就会更低，这是因为冗余执行一个EB的计算节点的数目比较少。312三个执行agent全局agent在下发任务广播报文的时候除了一些必须的任务信息，也会向有效地执行agent
31、下发类似0+这种外部用户的任务执行要求。而执行agent会根据这些信息对任务在本执行agent上的执行时间和可靠性作出估计并写入投标信息2i量i兰79二!”i量824。Lo8=：蛐蛐58“舶25阳猢瑚啪万方数据第9期 余盛季，等：云计算环境下基于时间和可靠性的调度策略 2677中，全局agent在接受到各个执行agent的投标请求后，会根据它们投标请求中给出的R(0+)来判断使用哪个执行agent执行任务，即会选择R(0+)最大的那个执行任务。表3和4中给出的就是第二、三个执行agent在不同0的任务的划分和计算节点的分配。表3第二个执行agent中任务划分和计算节点的分配计算节点序号8+1
32、2 3 4 5 6 7 8 9 102 4 5 7 8 9 l 4 5 7 8 9 ll 2 3 4 5 6 7 8 9 1 6 7 8 91 2 4 2 4 5 8 9 5 8 9与表1、3和4对应的执行agent各个最短时间下的最大和最小时问以及相应的可靠性如表5所示。表5 不同最短执行时间下服务的执行时问和可靠性表5中给出的就是全局agent下属的三个执行agent在接到全局agent的任务广播时发出的投标请求中的投标信息的一部分。这里的时间和可靠性并不一定是全局最优的解，只是相对全局最优的解。从表中给出的数据可以看出，当最短执行时间设置为200的时候，每一个执行agent给出的执行时间
33、和可靠性的估计值都是不一样的。因为该任务是基于给定最短执行时间，要求可靠性最高的原则，所以只要时间满足低于200就可以了，全局agent不会比较它们给出的执行时问谁最短，因此全局agent会从这三个执行agent中选取处可靠性最高的那一个即第二个执行agent，它的可靠性在0=200的时候为0802，这样第二个执行agent在投标0=200的任务的时候成功。同理，0。=300的时候，第三个执行agent中标成功，其可靠性为0920，0=400的时候第一个执行agent中标成功，其可靠性为0966。在选定了执行agent后，全局agent就会给相应的执行agent发送中标成功消息，这时候执行ag
34、ent就会根据上一步的任务划分和计算节点的规划开始执行任务。32给定最低服务可靠性需求在本原则中，给定了一个最低的可靠性要求R一，即把可靠性放在了最重要的位置。这时候对任务的划分和计算节点的分配就要在满足任务执行的可靠性在不低于尺。；。的情况下使得整体任务执行的期望时间矽达到最低。321 一个执行agent在第一个执行agent中，分别设定R血的值为070、080和090。即要求任务的可靠性程度要分别不低于上面的数字。根据本原则，得到任务的划分和计算节点的分配结果如表6所示。表6第一个agent中任务划分和计算节点的分配计算节点序号R。i。1 2 3 4 5 6 7 8 907 6 7 9 2
35、 2 5 4 8 3 l 6 7 9 6 7 908 5 5 3 9 3 9 1 2 4 6 8 1 7 3 909 4 7 4 7 4 7 1 1 5 6 8 9 l 2 3 2 3与表6中任务划分和计算节点的分配对应的最短执行时间、最大执行时间、可靠性以及执行时间的期望值如表7所示。表7 第一个agent中最大最小执行时间、可靠性及执行时间期望从表6和7中得出的结果中分析得出。对于给定的不同尺，第一个执行agent会对任务的划分和计算节点的分配有着不同的结果。随着尺一的增大，执行时间的期望值形也越来越大。尺增大就意味着同一个EB会分配给更多的计算节点冗余执行，而与此同时单个EB里面所包含的
36、子任务的个数也会相应增加，这样就导致每一个EB里面的计算复杂度和输入输出数据量增加，最终导致执行时间增加。相反，尺。的值越小，单个EB里面所包含的子任务的个数就越少，而这些EB就会越倾向于分配给不同的计算节点执行。322三个执行agent当三个执行agent同时有效的时候，全局agent就会根据执行agent给出的投标数据来选择一个执行agent来执行该任务。三个执行agent的投标信息如表8和9所示。表8第二个执行agent中任务划分和计算节点的分配尺一j燮兰一l 2 3 4 5 6 7 807 6 l 8 8 2 9 3 l 4 5 708 2 6 l 4 5 9 3 7 8 3 7 8
37、3 7 8 l 3 7 8O9 2 3 7 I 4 5 8 9 4 5 8 9 l 6 l 2 3 7表9第三个执行agent中任务划分和计算节点的分配尺。一塑塑壁呈一1 2 3 4 5 6 7 8 9 lO与表6、8和9中任务划分和计算节点的分配对应的最短执行时间、最大执行时间、可靠性以及执行时间的期望值如表lO所示。当全局agent向三个执行agent发布任务消息后，执行agent就会根据任务信息给出投标数据，全局agent就会根据这些投标数据选择执行agent执行任务。当给定的R。值为070时，可以看出三个执行agent的执行时间期望矽都不相同，这时候全局agent就会选择形最小的执行a
38、gent执行该任务。从表10中可以看出，这时会选择第一个执行agent执行，其W=121231。同理，尺为080和090时，会分别选取第三个和。卯23。嚣瑚姗栅8”46。3M。黑3舶6”73”万方数据2678 计算机应用研究 第33卷第二个执行agent执行该任务。表lO不同最低可靠性下服务的执行时间、可靠性以及期望4结束语本文在研究传统任务调度算法的基础上，使用一种可扩展的由星型结构演化而成的多代理模型，提出了一种云计算环境下基于可靠性和服务时间的任务调度策略。仿真实验论证了本文所提出的调度策略是高效的。目前在这个领域的研究中，基于单一维度(即只考虑一种条件，如执行时间最短)的调度策略研究已
39、有很多，而基于多维度的研究将成为今后的热点。参考文献：1Holland J HAdaptation in natural and artificial systems：an introduetory analysis with applications to biology，control，and artificial intelligenceMS1：U Michigan Press，19752Wooldridge M，Jennings N RIntelligent agents：theory and practiceJThe Knowledge Engineering Review，1995
40、，10(2)：115-1523Shoham YAgentoriented programmingJArtificial Intelligence，1993，60(1)：51924阎朝坤，胡志刚，李玺，等面向可靠性费用优化的网格任务调度模型及算法研究J计算机科学，2013，40(3)：1361415王朋云计算环境下任务调度策略研究J计算机与现代化，2013(7)：22256王莉，窦曼，刘宗田，等一种快速网格任务调度策略J计算机科学，2007，34(6)：128-1307刘莉，姜明华异构集群下的任务调度算法研究J计算机应用研究，2014，31(1)：80一848谢丽霞，严焱心云计算环境下的服务调度
41、和资源调度研究J计算机应用研究，2015，32(2)：5285359Xiang Yanping，Fan Huijuan，Levitin GMaximal profit service taskpartition and distribution in computer gridJComputersIndustrial Engineering，2013，64(1)：153-16110Levitin G，Dai YuanshunOptimal service task partition and distribution in酣d system with star topologyJReliabi
42、lity EngineeringSystem Safety，2008，93(1)：15215911Bonnell D N，Pieard M W，Tatarinov K LSystem for monitoring andmanaging computer resources and applications across a distributedcomputing environment using an intelligent autonomous agent arehitecture：USPatent 5，655，081P1997080512Meng Sa，Xiang Yanping，Y
43、u ShengjiAn agentbased approach formulti performance optimization in grid computingJApplied Me-chanics and Materials2013，321：2339234213Genesereth M R，Software agentsJCommunications of ACM，1994，37(7)：485314Levitin GThe universal generating function in reliability analysis andoptimizationMBerlin：Sprin
44、ger，200615Bouleimen K，Lecocq HA new efficient simulated annealing algorithm for the resourceconstrained project scheduling problem and itsmuhiple mode versionJEuropean Journal of Operational Research，2003，149(2)：268281(上接第2636页)参考文献：1Jain A K，Murty M N，Flynn P JData clustering：a reviewJACM Computing
45、 Surveys，1999，31(3)：2643232Khan S S，Ahmad ACluster center initialization algorithm for Kmeans clusteringJPatlem Recognition LetIers，2004，25(11)：129313023雷小峰，谢昆青，林帆，等一种基于K-means局部最优性的高效聚类算法J软件学报，2008，19(7)：168316924张健沛，杨悦，杨静，等基于最优划分的Kme811s初始聚类中心选取算法J系统仿真学报，2009，21(9)：258625895翟东海，鱼江，高飞，等最大距离法选取初始簇中心
46、的Kmeans文本聚类算法的研究J计算机应用研究，2014，31(3)：713715，7196Redmond S J，Heneghan CA method for initialising the Kmeansclustering algorithm using kdtreesJPatIem Recognition Let-ters，2007，28(8)：9659737Huang ZhexueExtensions to the K-means algorithm for clusteringlarge data sets with categorical valuesJData Mining
47、and Know-ledge Discovery，1998，2(3)：2833048Sun Ying，Zhu Qiuming，Chen ZhengxinAn iterative initialpointsrefinement algorithm for categorical data clusteringJPaRem Recognition LeHers，2002，23(7)：8758849Mitra P，Murthy C APal S KDensitybased multiscale data COUdensationJIEEE Trans on Pattem Analysis and M
48、achine Intelligence，2002，24(6)：73474710Khan S S，Ahmad ACluster center initialization for categorical datausing multiple attribute clusteringcProe of the 3rd MultiClustWorkshop：Discovering，Summarizing and Using Multiple ClusteringsNew York：ACM Press2012：3101 1Wu Shu，Jiang Qingshan，Huang J zA new initialization method forclustering categori