摘要：本文在云经济模型的基础上，提出一种受用户级QoS驱动的分组调度算法。该算法基于对云QoS的属性分析，对经济云现有的DBC调度算法进行了扩展和改进。在满足任务的截止期限和预算的范围内，根据任务是否具有高网络带宽进行分组。通过把基于用户专有的QoS的需求加入到常规分组调度算法中，从而形成了一个基于网络带宽的分组调度算法。仿真结果显示：在模拟的云环境下，本文算法拥有较高的吞吐量和任务完成率。

引言

 目前大多数云计算环境下的调度和资源管理问题一般仍使用传统形式，即由调度构件如Glbous根据确定的花费函数来决定任务应在哪里执行，但这些花费函数一般都以系统为中心的，难以通过用户的QoS参数如存取价格、服务传送时间片等驱动。在经济管理模型下，不同的系统当然不会花费同样的价格来存取相同的资源。终端用户也不一定想要支付最高的价格来获得最有效的资源利用，而是有可能基于需求、价值、优先权和可供使用的预算协商一个特定的价格^[1]。此外，QoS是一个综合指标，不同应用的侧重不同，在计算密集型任务当中，QoS往往反映资源的运算速度，而在一些数据密集型的任务当中，QoS较多地表示节点之间的带宽、节点数据的质量等指标^[2]。在经济学方法中，调度决定不是静态地由单个调度实体来完成，而是由终端用户的要求直接驱动^[2]。一个常规的经济模型，一般关注的是运行应用的软件和硬件花费，而经济模型主要对最终用户的服务收取费用^[3]。在竞争的经济市场中，基于用户需求和可供使用资源的交易是主要驱动力。

 对此，本文提出了一种面向任务交易成本和截止期限的分组任务调度策略。该策略优先选取用户级具有高网络带宽要求的任务进行调度，根据交易价格和平均价格的比较将任务分成两组，在可用资源列表中对两组任务分别进行时间优化和花费优化调度。最后测试了本文算法的调度性能。

1 系统模型假设

 在竞争的经济市场中，基于用户需求和可供使用资源的交易是主要驱动力。因此，我们关注的是单个用户在云中与其它用户以及云服务提供者和资源拥有者的竞争。

 云需要合适的资源管理模型使成员有效地共享资源。本文采用计算经济模型与用户交互的管理方式，向用户的任务提供服务质量保证。云环境中的QoS有一系列的规范，包括资源响应时间、可用性、安全性、吞吐量等^[6]。本文选择在费用(Cost)，期限(Deadline)和任务执行的可靠性(Reliability)这三维QoS约束下调用有限的资源来满足不同云用户的请求。调度者和用户需求被公式化为效用函数、和，分别代表用户选择QoS选择产生的效益，根据每一个效益函数提供定量计算QoS的数学方法。调度问题可以推广为多个不同长度的任务在多个不同资源上的调度问题。同时约定：

 (1)进行调度的一组任务是互相独立，即任务之间没有通信和数据依赖^[6];

 (2) 各种资源有不同的处理能力;

 (3)一个资源在同一时刻只能处理一个任务;

 (4)一个任务不能同时在两个资源上处理;

 (5)任务一旦运行，运行该任务的资源被独占，只能等到任务完成后，再执行别的任务。

 对资源的调用要遵从市场经济模式，当云中有N个任务和M个可用资源时，网络资源调度策略在N个任务和M个资源之间进行匹配，使得既可以满足用户的要求和云资源约束，又可以使完成任务目标代价最优或近似最优^[7]。提出任务的客户端希望找到能够满足用户要求的资源使任务执行的时间最短而且价格最低^[8]。提供资源的工作端希望自己的资源能够充分利用，尽量减少空闲资源的时间，提高资源的利用率，增加自己的经济效益^[9]。

 假设某一时刻云用户向系统提交了N个任务，每个任务的长度为Li，用指令数来度量，单位为MI百万指令，截止期限Deadline以及可以支付的最大预算Budget值(由用户指定)如下表所示，任务按照长度从大到小的顺序进行排序。

 初始状态下云系统中存在的M个可用资源的处理速度以及各个资源的性能开销参数列表如下，其中Vi表示每个资源的处理速度，Ci表示资源R每百万条指令的执行开销(Cost/MI)。资源按照处理速度从大到小的顺序进行排序。新资源因为还未分配任务，所以它的任务列表为空;若某一资源的任务列表不为空，则称这个资源是旧的。将所有到达的任务分配给新资源，若此时没有新资源可用则将任务分配给旧资源。初始时刻，全部资源都是新的，把长度最大的任务T0分配给处理速度最快的资源R0，计算执行的时间和开销是否超出了用户可以承受的Deadline和Budget，如果未超过则将T0加入R0的任务列表，否则考虑下一个可用的新资源。同时将该资源从新资源列表中删除，加入旧资源列表，并将其标志为旧资源，反复进行此过程，直到全部的任务都被调度或调度失败。调度的目标是找到能够在期望的执行时间内完成工作任务、而且所付出的费用相对比较廉价的资源，即时间和费用是最优的^[10]。

 基于多QoS规划模型进行资源分配和任务调度的算法描述如下:

 (1)随时接收客户端的资源申请(客户端申请中给出了资源需求);

 (2)在每一个长度为T的时间段内开始执行以下算法步骤：

 (a)按规划进行任务刻录;

 (b)用户需求为调度范畴，进行资源调度比对;

 (c)按最佳匹配原则进行匹配;

 (d)在调度周期内确认有多少资源可以进行调度;

 (e)计入运算结果;

 (f)反馈给客户。

2 基于多维云用户驱动QoS网络资源调度

 在一个三维的QoS模型空间中对此调度问题进行研究。模型空间由运行费用(C)，截止期限(D)和可靠性(R)构成。其中C代表花费Cost，执行云任务时的花费包括处理计算资源和网络(传输带宽)资源的花费;D代表截止期限Deadline：处理云任务的全部时间;R代表可靠性Reliability：完成任务的概率。

 云任务i可以使用资源代理j的计算资源：(表示资源的处理时间)，如果j的计算能力为Cj，则相应的资源分配约束条件为 。i执的时间上限。任务代理i支付给计算资源代理j的报酬为，那么代表了第j个计算资源代理完成所有任务获得的全部报酬。

 考虑模型的效益函数，第一维效益函数，是和费用有关的：

(1)

：资源预算，是i为获得计算资源付出的总代价;表示第一维QoS的权重。

 第二维QoS效益函数是和执行时间有关的：

(2)

T_i是i的执行截止时间;b_in是完成第n个工作需要的计算资源数量;D代表延迟时间;代表分配到第二维QoS的权重;

 第三维效益函数代表调度的可靠性：

  (3)

 g：在截止期限内完成调度的任务数，f：在截止期限内总共提交的任务数。

 任务的效用函数是这三部分的加权函数：

(4)

 整个系统的效用函数

(5)

 网络资源调度者的目标是在QoS约束下为i进行资源分配，最大化系统效益并满足：

(6)

 在经济模型下最大化任务代理获得的效用，使用拉格朗日数学方法求得多维QoS约束的网络资源调度问题的最优解：在时间期限内，最优化任务代理：

(7)

 在资源市场上，计算资源作为资源供应者，考虑到任务代理愿意付出的代价，试图最大化它们的收益：。这样，云资源供应者的最优化问题可被公式化为，且

 由以上对QoS进行量化的效益函数表达式可知，完成时间和花费QoS是负QoS参数，其它属性的QoS参数是正QoS参数。所谓的负QoS参数是指QoS值越大，其效益函数值越小，正QoS参数是指QoS值越大，其效益函数值越大，见图1。

 再利用拉格朗日乘数法求解在多QoS约束条件下的最优解，构造以下的辅助函数：

(8)

 令，就可以得到最优化任务代理问题的最优解，表示任务代理在约束时间条件下为了最大化系统效益应该付出的价值;

 再来考虑对资源代理的优化：且，求约束条件下的最优解，构造拉格朗日函数：

(9)

 令，可以求得计算资源代理优化问题的最优解，表示计算资源代理作为资源供应者，为了最大化它的收入希望分配给任务代理的的单元个数。

3 仿真实验

3.1 仿真参数设置

u 本文采用NS2仿真平台进行仿真实验，详细仿真结果如表2所示。

3.2 实验结果对比

 图 2、图3显示了本文算法与DBC算法在完成任务效率上的比较。依图2可知，满足要求的任务个数随着deadline的增加而增加，但DBC算法的deadline增加到2400以后，完成的任务个数保持在一个数值不再增加，这是因为完成的任务已经用完了用户提供的budget，增加deadline的值对任务的完成数没有影响，这符合计算经济网格中的交易原则;在期限固定的情况下，随着预算的增加，对于任务的完成情况，本文都比传统DBC优化算法有一些提高，说明本文算法提高了截止期限内的任务完成率(任务的可靠性)。由图3可知，满足要求的任务个数随着budget的增加而增加，但是本文算法的提升速度更快，这是由于本文算法采用拉格朗日计算方式，在Dealine固定的时候，能够更有效地提高资源调度效率，从而在一定截止时间内完成的任务数更多。

4 结束语

 本文对基于经济模型的云网络资源调度问题进行了详细的介绍，分析了使用经济原则和交易议价的优点，认为它能够更好地适应现代网格的发展。在对网格传统的调度算法进行研究的基础上，根据现代网格基于市场经济模型进行资源管理的特点，提出了一种基于多维云用户驱动QoS网络资源调度算法。通过合适的分组机制有效地降低了经济代价，具有一定的部署价值。

参考文献：

 [1]Gounder V, Prakash R, Abu-Amara H. Micheline data miming: date and techniques[C]. Wireless Communications and Systems, 2014: 1-6

 [2]胡自林,徐云, 毛涛. 基于效益最优的云网络资源调度. 计算机工程与应用, 2014, 7: 69-70

 [3]Ngai EWT,Hu Y.The application of data mining techniques in financial fraud detection :A classification framework and an academic review of literature[J]. Decision Support System, 2011, 50(3):559-569

 [4]Thelwall ,Wilkinson D.Data mining emotion in social network communication:Gender differences in MySpace[J].Journal of the American Society for Information Society for Information Science and Technology, 2010, 61(1):190-199

 [5]lcala-Fdez J.KEEL Data-Mining Software Tool:Data Set Repositoty ,Integration of Algorithms and Experimental Analysis Framework[J].Journal of Multiple -Valued Logic $Soft Computing,2011,12(17):204-209

 [6]Bal M.Rough Sets Theory as Symbolic Data Mining Method:An Application on Complete Decision Table[J].information Sciences Letters,2013,2(1):111-116.

 [7]Yang K,Shahabi C.An efficient k nearest neighbor search for multivariate time series[M].Information and Computation,2013: 65-98

 [8]JolliffeD, Tran T, Nguyen T. Data mining network coding [J]. IEEE Trans. on Vehicular Technology, 2009, 58(2): 914-925

 [9]Ester P, Sander S.A key efficient way of data mining techniques[C]. Michine and Systems，2014.:74-79

 [10]Foster I, Kesselman C. Globus: A Metacomputing Infrastructure Toolkit. Intl J. Supercomputer Applications.1997, 11(2):115 - 128

 [11]LEE W.A data mining framework for constructing features and models for instrusion detection systems[D]. New York Computer Science Department of Columbia University，2012: 33-76

 12]Wang W,Yang J. A statistical information grid approach to spatial data mining[C]. Proc Int Conf Very Large Databases，1997:186-195