云计算对完工时间最小化算法研究.docx

云计算对完工时间最小化算法研究摘要:目前对云服务供给进行的研究主要围绕任务映射展开，其中怎样将面向服务的任务分布给服务器以实现完工时间最小化成为该领域内的难点。总结后发现，未能实现完工时间最小化的重要原因是没有考虑到任务路由器传输所造成的影响，鉴于此提出一种多项式时间复杂度的启发式算法。实验结果表明，该算法的效率接近于最优解，效率较高且性能远优于当前其他算法。关键词:云服务;映射;时间;启发式算法;最优解对于云计算服务问题的研究，诸多学者从各个方面提出了对应的解决方法，实现云计算服务的效益的最大化。吴小红、王翠娥等人(2012)针对于响应时间提高这一指标，提出了DSIC机制来确保在最短的时间内显示资源成本信息，使得到达响应时间最小化的目的1。杨柳、唐卓等人(2012)对响应时间与成本消耗进行了综合考虑，在随机规划理论的基础上提出了虚拟分配的优化算法，实现资源的有效调度与分配2。景维鹏，邢乐乐等人(2013)同样采用时间与费用的双重约束条件，提出了一种改良的作业调度算法来缩短响应的时间3。从现有的研究上来看，都提出了改进算法，主要是从时间响应上来进行约束。但是却很少从路由传输这一角度出发考虑来减少时间响应。1系统模型建立数据中心与链路集合共同组成了网络图，对此假设这三个集合分别为V=D1，D2，D、链路E与G=(V，E)。数据中心的服务器并不是单一存在的，假设服务器共计有个，则可记为S=s1，s2，s。每个服务器都是×二元矩阵，可用MSD=MSDij，i=1，2，j=1，2，其中：Du与Dv之间的传输的链路(u，v)的延时假设为luv，那么链路E集合则为×的矩阵，可用ML表示，表达式如下(2)所示4。ML=luv，(u，v)E(2)在云计算服务中，当收到数据请求时，会构成任务T=T1，T2，T，并根据任务来对资源需求规模T进行估算。鉴于时间约束的云计算服务，任务资源能够用×的矩阵QT=QTki，k=1，2，i=1，2，表示，其中QTki是Ti对资源k的需求量。对此，能够在数据控制室直接确定某一时间区间内的AS与QT的容量。2问题模型构建21任务映射任务完成的约束条件:假若任务服务器映射关系为一个×的矩阵MTSij，其详细表达式如下(3)所示:该约束条件指出每一个任务都需要与服务器连接，也就是讲任务必须有服务器处理，则:对于资源容量的约束来讲，所分配的任务资源需求容量不能超过服务器所能提供的总容量，故此有如下的条件(5):在计算时间上，其实际时间ei与任务规模Ti呈正相关，对此得到约束条件(6)，其中P0为处理速度。对于等待时间来讲，这是在工作周期内因任务未完成进而造成等待时间。若未完成任务有N0个，那服务器是初始的任务状态能够用N0×矩阵MTS=MTSij，i=1，2，N0，j=1，2，表示，其表示公式如下(7)所示:知足通用性原理，任务是通过随机方式来实现公正分配，假设(j)为sj服务器上对接收任务的计算时间，那么我们能够得到(8)那么，服务器sj映射下一个任务时所需要的最大的等待时间能够如下表示:因而，服务器上的新任务Ti的预期最长周转时间i可表示为:22任务路由传输任务路由传输，首先是要确定链路能否起到任务传输的作用，能够通过引入(u，v)E来进行确认，如(11)所示5:对于任务分配来讲，其分配的服务器并不是与当前的数据中心是对应的，但是一般来讲为减少时间与消耗成本常采用同一数据中心的链路，对此能够得到(12)。通过服务器的映射矩阵MTS能够得到一个×矩阵MTD，MTD=MTS×MSD，该矩阵反映了映射关系。对于每一个任务来讲，其传输必须拥有一条传输链路，中间的数据中心需要保持数据流量的平衡性，综合考虑能够用下面(13)关系式来表达。此外，每条链路上所有任务的总流量必须在其容量范围内，即:根据每一个任务的传输延时能够得到总任务量的传输延时的大小i，即路由器传输的延时，详细如下(15)所示:考虑到云计算最重要的考核指标，任务器传输延时与传输任务的等待时间不应该超过其时间限制，对此能够得到下面约束关系式:23IPQC问题根据前面所提到的约束条件，能够将上述的建模简化为一个IPQC问题，即具有二次约束的整数规划问题，如(17):在这些约束中，式(5)和(13)是二次约束条件。IPQC问题属于NP难题，其主要解决的办法包括分解算法、割平面法以及外逼近法等等，但是这些算法运用只合适于特定的IPQC，并且在算法上存在计算冗杂，计算时间长等问题，目前没有一个有效的通用算法来进行解决。为决绝IPQC问题最有效的途径就是将其线性化，采用增加变量与约束条件的方式将函数问题转化为线性函数，进而极大地简化问题6。对此提出了启发式算法，其算法在后面具体介绍。3启发式算法设计根据前面阐述的约束问题，能够归结于两点，一个服务器装箱问题与数据流量传输管理问题，对此，根据云计算的时限指标以及其约束条件设计了两个阶段的启发式算法1与算法2，详细如下:算法1:最优拟合递增型任务映射算法输入:网络图G=(V，E)，新的任务集合T，AS，QT，MTS;输出:新任务的映射矩阵MTS1:MTS02:T'根据任务规模对所有新的任务进行递增排序3:S'根据服务器寄存的任务数量对所有服务器递增排序4:for所有TiT'，i=1，2，do5:for所有sjS'，j=1，2，do6:ifsj可知足Ti的资源要求then7:MTSij18S'根据寄存的任务数量对所有服务器再次递增排序9:break10:endif11:endfor12:endfor13:ij=1MTSij()j，i=1，2，;约束为(8)，(9)首先对其进行初始化，再根据任务的规模进行排序与存储，算法1的复杂度的为O(N)，当输入变量后就能够得到映射矩阵。在实际的云计算中，数据任务规模是非常庞大的，因而需要寻找最短的传输途径来减少时间等待与传输延时效应。对此最短途径的寻找能够利用基于整数规划的算法2来完成。将前面的映射结果作为输入的变量，在最终结果中就能够得到最优的传输途径。算法2:基于IP的途径寻找算法输入:网络图，任务集合及任务映射算法提供的1:MTDMTS×MSD2:iuv03:iuvargmini=1(u，v)ETiluviu()v，约束条件为式(12)，(13)，(14)，(16)。4性能评估41小规模网络的预期最大完工时间在小规模网络环境下三种算法的完工时间性能比拟中，如图1(a)中所示，随着任务量的不断增长，这三种方法的完工时间也同样出现增长的趋势，也就是所完工时间是与任务量的多少成正比的，同时在一样任务量的情况之下启发式算法的完工时间明显要低于其他两种算法。如图1(b)所示，链路容量变化情况下各算法之间的响应时间的发展趋势。当容量从800增长至1600时，两种阶段启发式算法所得到的完工时间呈现不断下降趋势但是下降幅度并不是很大，FFDMEM与BFDMEM这两种方法同样呈现递减的趋势，相较而言在容量一定时提出的启发式算法性能更优。如图1(c)所示，随着服务器中新旧任务概率变化时三种算法的完工时间指标变化情况。当新旧任务概率不断增加时，各算法之间的完工时间均在不断增加，造成这样的原因在于概率越大造成任务的等待时间越长进而增加了完工时间。综合不同情况下的三种算法得到的完工时间的长短来看，阶段启发式算法的时间性能明显要优于其他两种算法。42大规模网络的预期最大完工时间在大规模网络中途径寻找是关键，对此与最为常用的寻找途径的Dijkstr、SPFA算法相结合，同样来探寻任务量、流量以及新旧任务这种情况下的完工时间变化，最大完工时间之和与新任务数量间的关系图2所示。其中，图2(a)是IPPFA的任务映射启发式算法仿真图，图2(b)是DijkCAP的任务映射启发式算法仿真图，图2(c)SPFACAP的任务映射启发式算法仿真图，图2(d)BFI与最短途径寻找算法相结合仿真图。任务概率的增长而不断增加，会随着链路容量的增加而呈现出递减的趋势。仿真结果如下列图3所示。其该三种算法的完工时间的性能变化趋势与小规模网络情况下的相一致。云计算的完工时间会随着任务量以及新旧但综合这三种算法得到的最大响应时间来看，如图4所示。两阶段启发式算法的完工时间最小，性能是最优的，也就讲该算法到达了性能优化的目的。研究表明，从任务映射与路由传输两个方面进行综合性考虑来进一步缩小完工时间，到达快速响应的目的。将研究的问题简化成IPQC问题，并提出了一种多项式时间复杂度的启发式算法来进一步对问题实现线性简化。通过全面的仿真实验，证实该算法的效率接近于最优解，效率较高，且性能远优于当前其他请求响应算法，证实了两阶段启发算法在云计算中的有效性。