统筹资源可信度与用户满意度的分布式资源调度方法

本发明属于分布式算法技术领域，涉及统筹资源可信度与用户满 意度的分布式资源调度方法。

分布式计算系统利用了互联网上数以千百万计的闲置计算资源， 可以获得比集中式计算系统更强大的计算能力。由于其资源的海量 性、组成的异构性以及网络通信的延迟性，使得其资源调度问题成为 难点。资源的调度是指将用户提交的作业合理分配到恰当的资源以满 足用户的需求，最大化系统运行的效益。针对分布式资源调度问题， 学者提出了一系列的调度策略。文献[1]提出了一种基于蚁算法的分 布式资源调度策略预测模型，主要是为了提高分布式计算的动态性和 实时性，提高资源调度的实时性和有效性。文献[2，3]提出了基于可信 度的分布式资源调度策略，其核心在于预测资源未来时刻的负载状况 进而计算得到可信度，根据可信度来决定作业的分配。文献[4，5]提出 了基于用户总体满意度的遗传任务调度算法，该算法根据不同用户的 偏好设计了用户满意度函数，通过遗传算法来优化调度过程，从而使 得用户的总体满意度得到提升。文献[6，7]提出了一种均衡调度算法， 该算法对作业根据依赖关系计算阶位值，依据该值进行作业动态调整， 使关键作业尽早完成，减少作业之间的等待，缩短计算作业流执行时 间，结果表明，该算法对作业管理系统中投入的计算作业流的快速执 行有较强优越性。文献[8，9]对现有文献中的关于调度问题的遗传算法 进行研究和比较后，该文提出了一种基于遗传算法的任务调度方法， 在算法中设计了一种与其他算法不同的变异算子。文献[10]针对固定处 理节点分布式系统动态调控能力弱的问题，给出一种分布式系统任务 调度模型。模拟实验证明，该算法有较好的动态调控能力，能根据需 要降低处理器负载、改善任务处理延时并更合理地利用系统资源。文 献[11]提出了一种基于公平指标的任务调度负载均衡算法，推导出在多 节点条件下的任务分配方法，并在此模型下改进了基于公平指标的负 载均衡算法。文献[12]在深入研究分布式系统中负载平衡调度问题的基 础上，归纳总结了负载平衡调度的一般模型，对影响负载平衡的各个 因素进行了详细的分析。文献[13]提出了基于移动agent的分布式资源 分配策略(MADRAP)，该策略在传统的分布式资源分配策略基础上改 进了学习机制，实现了全局稳定的任务均衡负载。文献[14]研究了分布 式实时系统中的Agent调度算法，建立了分布式实时多Agent系统的 结构模型，并对其结构特点、负载能力和常用的Agent实时调度算法 分别进行了分析与论述。文献[15]讨论了在多Agent系统中多组作业的 并行调度问题，提出了调度效率的概念和多Agent相关任务均衡-压 缩调度算法(MADTBCSA)。

上述研究或侧重于资源可靠性的研究，而忽略了用户对于作业 的要求，因为现实中有的用户对于运行时间敏感，而有的用户对于 运行费用敏感，忽略用户的需求将导致用户满意度的下降；或片面 强调了用户满意度，如文献[2]中满意度的计算方式是静态的，未能考 虑到负载之后满意度的变化；或偏重于设计负荷均衡机制和Agent协 作机制，而在目标函数中未能人性化地考虑到用户的感受以及资源 的可靠性。

本发明的目的在于提供统筹资源可信度与用户满意度的分布式 资源调度方法，解决了现有的算法作业的平均返回时间高，系统运行 效率低的问题。

本发明所采用的技术方案是按照以下步骤进行：

步骤1：用户Agent：向作业响应Agent提交作业，作为资源的 消费者出现，作业申请成功时占用资源，作业完成后释放资源；

步骤2：作业响应Agent：接受用户提交的作业申请，向用户返 回作业完成结果；

步骤3：作业分解分发Agent：接受作业响应Agent发送的作业， 将作业分解成可被分解的最小粒度，即子作业，并将分解后的子作业 发给作业调度Agent；

步骤4：资源搜索Agent：搜索网络中在线的资源，注册资源；

步骤5：作业调度Agent：作业调度Agent接受已经被划分为最 小粒度的子作业，通过调度算法将子作业分配到资源Agent中；

步骤6：资源Agent：在线时向资源搜索Agent发送在线消息， 选择资源搜索Agent，确定注册，接受作业调度Agent发送的作业， 完成作业，检测自身状态，向资源搜索Agent发送自身资源可信度， 当调度倾泻或者作业失败时向作业监控Agent申请移交作业；

步骤7：作业监控Agent：监控资源Agent的状态，当接到资源 Agent发送的移交作业申请时，将作业进行重新分配。

进一步，所述步骤5中的调度算法为：

设作业调度Agent中的作业Agent资源为1，2，......，m，以及资源 1，2，......，m的可信度矩阵R＝[r1，r2，......，rm]T，矩阵是资源可信度 r(t)的线性组合，以及费用矩阵C＝[c1，c2，......，cn]T，矩阵为多个费用 的线性组合，和接受的作业1，2，......，n以及作业的满意度矩阵

$S=\left[\begin{array}{cccc}{w}_{11}& w_{21}& L& w_{n1}\\ w_{12}& w_{22}& L& w_{n2}\\ L& L& L& L\\ w_{1m}& w_{2m}& L& w_{\mathrm{nm}}\end{array}\right];$

其中，wij表示第i个用户对第j个资源的满意度，wnm表示第n 个用户对第m个资源的满意度，wnm中的n和m分别表示用户作业 个数和资源个数，而wij中i和j分表表示具体的第i个用户作业和具 体的第j个资源，采用遗传算法进行计算，计算过程如下：

染体编码：

染体为一个n维的元素为整数的矢量D＝[d1，d2，L，dn]， di(i＝1～n)，为整数，表示第i个作业被分配到了第di个资源上，di 的取值范围为1～m，D矢量完全代表了当前作业1，2，......，n的分配资 源情况；

种初始化：

设置种大小popNum后，生成popNum个染体，每个染体 中的元素均为随机生成，随机数的范围位于1～m之间；

适应度函数：初始化完成之后，对种中染体的适应度进行评
估，第i个作业分配到第d_i个资源上，此时用户的满意度函数如下：

$s_{i,d_i}=w_{\mathrm{it}}\frac{1}{h_{d_i}}\frac{r_{d_i}}{r_b}+w_{\mathrm{ie}}\frac{c_b}{c_{d_i}}$

wit+wie＝1，

wit和wie分别为用户对于时间性能和经济费用的偏好程度，rj为 第j个资源的可信度，rb为分布式系统历史资源可信度均值，cj为第j 个资源对用户i的报价，cb为系统历史资源报价均值；

适应度评估函数如下：

$\mathrm{fitness}=\underset{i=1}{\overset{n}{\Sigma }}{s}_{i,d_i}.$

进一步，所述资源可信度为

r(t)＝p(t)*i(t)*h(t)*v(t)，

其中，t是时间，r(t)是资源在t时刻的可信度，其是由 p(t)、i(t)、h(t)、v(t)四部分组成的，p(t)是资源的性能函数，i(t)为资 源的可用率，h(t)为资源的在线率，v(t)为资源完成作业的成功率。

进一步，所述wit和wie取值范围为[0，1]，根据用户类型的不同， 设置不同wit和wie，对于性能优先用户，设置wit＝0.8，wie＝0.2；对于 经济优先用户，设置wit＝0.2，wie＝0.8；对于折中均衡用户，设置 wit＝0.5，wie＝0.5。

本发明的有益效果是综合提升了用户的满意度，降低了作业的平 均返回时间，提高了分布式系统的运行效率。

图1是本发明Multi-agent调度策略框架结构示意图；

图2是本发明基于资源调度策略遗传算法流程图。

下面结合附图和具体实施方式对本发明进行详细说明。

本文针对目前分布式系统资源调度存在的问题，提出了一种综 合考虑用户满意度和资源可信度的Multi-agent分布式系统资源调度 策略。该策略在目标函数中并举用户的满意度和资源的可信度，通 过将资源的可信度融合进入用户满意度函数中，再以用户满意度为 优化目标，采用遗传算法求解，可以使得调度结果最大化用户的利 益和计算的效率。将上述调度策略封装进入Agent之后，提出了一种 Multi-agent调度框架，利用Multi-agent优秀的自治性、学习力以及社 会性实现分布式资源调度。

定义资源可信度：

资源的可信度是衡量资源的处理能力和可靠度的指标。其集中反 映了该资源从当前至未来一段时间的处理能力以及可靠度。通过建立 资源的可信度模型，使得高可信度的资源被调用的几率更大，而少调 用甚至不调用低可信度的资源，可以使得资源的负载状况更均衡。资 源的可信度是动态的，是随着其性能、利用率、在线率以及完成作业 的成功率变化而变化的。在调度策略中引入资源的可信度，使得调度 是动态的，是随着资源的变化而变化的，这对于资源情况经常发生改 变的分布式系统具有重大意义。

资源的可信度定义如下：

r(t)＝p(t)*i(t)*h(t)*v(t)

其中，t是时间，r(t)是资源在t时刻的可信度，其是由 p(t)、i(t)、h(t)、v(t)四部分组成的。p(t)是资源的性能函数，反映了资源 处理作业的能力，如资源是CPU，则为CPU的主频。i(t)为资源的 可用率，和p(t)一样，体现的是资源的处理能力，如资源是CPU， 则为(1-CPU的占用率)。h(t)为资源的在线率，反映了资源的可靠 度。由于分布式系统利用的是internet上的资源，故难以预测资源在 某一时刻是上线还是离线，但可以通过统计资源的上线率来得到 h(t)，上线率越高的资源可靠程度就越高，可信度也就越大。v(t)为 资源完成作业的成功率，同样地，资源接受任务之后并非每次均能成 功完成任务，其完成任务的成功率的高低表征了可靠性的高低。

定义用户满意度：

大多数调度算法研究只侧重于优化系统运行整体指标，而忽略了 从个体角度来看的用户满意度。实际上，对于不同用户而言，其对作 业的时间性能和经济费用的偏好是不同的，如在分布式动漫渲染系统 中，用户A对渲染费用更关注，而用户B对渲染时间更关注。对于 相同用户，在不同的时刻，其对作业的时间性能和经济费用的偏好也 是不同的。当用户A面临一个紧急需求时，如果其客户C要求尽快 必须见到渲染效果，且并不在乎为此多付出的酬金，此时用户A将 更倾向于快速渲染；而当用户A面对一个非紧急需求时，如其客户D 的资金有限，要求A控制预算，且对完成时间没有硬性要求，这时 可以想象，A将更倾向于降低经济费用；当用户A面临对时间性能 和经济费用要求均衡的客户E时，不难得出A将选择折中均衡的方 案。

由此来看，对于不同的用户，需要设计针对其偏好的满意度函数， 以满足不同用户的需求，而调度策略的目标函数应考虑使得用户总体 的满意度最大化。建立用户i对其作业分配到资源j的满意度sij如 下：

$s_{\mathrm{ij}}=w_{\mathrm{it}}\frac{r_j}{r_b}+w_{\mathrm{ie}}\frac{c_b}{c_j},$

wit+wie＝1，

wit和wie分别为用户对于时间性能和经济费用的偏好程度，取值 范围为[0，1]。rj为第j个资源的可信度，rj越大，用户的满意度越大。 rb为分布式系统历史资源可信度均值。cj为第j个资源对用户i的报 价，cj越低，用户的满意度越高。cb为系统历史资源报价均值。

根据用户类型的不同，可以设置不同wit和wie。如对于性能优先 用户，可以设置wit＝0.8，wie＝0.2；对于经济优先用户，设置 wit＝0.2，wie＝0.8；对于折中均衡用户，设置wit＝0.5，wie＝0.5。

采用Multi-agent调度策略进行分析：

人工智能技术的一个重要分支即是Multi-agent技术。Agent即代 理，是指一个能在特定环境下连续、自发地实现功能，并且与相关 Agent和进程相互沟通联系的软件实体。Agent具有自主性，能够在 没有人或者其他Agent干预下完成其大部分功能，控制其内部状态。 Agent的另外一个重要属性就是其社会能力，其能够主动和其他Agent 进行交互，以达成目标。Agent还具备一定的学习能力，能够自适应 地随着环境而做出改变。Multi-agent系统是指由多个Agent组成的系 统。它可以解决依靠单个Agent难以解决的复杂问题。多个Agent之 间通过竞争、协调与合作来共同求解问题。传统的调度方法，如分支 定界法、动态规划、启发式图搜索算法等，虽然在数学上很完美，但 是由于对真实环境作出了大量的简化，使得其难以适应复杂的生产环 境，同时方法单一也导致了其适用范围的局限性。基于Multi-agent 技术的调度策略可以克服上述算法的种种缺点，由于其依靠的是分布 式Agent的集智能效应，使得对复杂问题的模拟和处理能力十分优 秀，同时兼具强大的自适应能力，在不同环境下能够自适应地改变自 身状态、学习相关知识，达到预期的调度效果，具有十分显著的鲁棒 性。

本发明Multi-agent调度策略，整体框架如图1所示。包含以下几 种Agent：

●用户Agent：向作业响应Agent提交作业，作为资源的消费者出现。 作业申请成功时占用资源，作业完成后释放资源。

●作业响应Agent：属于分布式系统和用户交接的中间层，接受用 户提交的作业申请，向用户返回作业完成结果。

●作业分解分发Agent：接受作业响应Agent发送的作业，将作业分 解成可被分解的最小粒度，即子作业，并将分解后的子作业发给 作业调度Agent。

●资源搜索Agent：搜索网络中在线的资源，注册资源。

●作业调度Agent：作业调度Agent接受已经被划分为最小粒度的子 作业，选择调度算法，将子作业分配到资源Agent中去。

●资源Agent：在线时向资源搜索Agent发送在线消息，选择资源搜 索Agent，确定注册。接受作业调度Agent发送的作业，完成作业。 检测自身状态，向资源搜索Agent发送自身资源可信度。当调度 倾泻或者作业失败时向作业监控Agent申请移交作业。

●作业监控Agent：监控资源Agent的状态，当接到资源Agent发送 的移交作业申请时，将作业进行重新分配。

其中的调度算法为：采用遗传算法的作业资源调度策略；

作业资源调度策略被封装在作业调度Agent之中的作业Agent资 源1，2，......，m，其中资源指的是比如CPU、内存等。以及资源 1，2，......，m的可信度矩阵R＝[r1，r2，......，rm]T，矩阵是步骤1中的多 个r(t)的线性组合。以及费用矩阵C＝[c1，c2，......，cn]T，矩阵为多个费 用的线性组合，和接受的作业1，2，......，n以及作业的满意度矩阵

$S=\left[\begin{array}{cccc}{w}_{11}& w_{21}& L& w_{n1}\\ w_{12}& w_{22}& L& w_{n2}\\ L& L& L& L\\ w_{1m}& w_{2m}& L& w_{\mathrm{nm}}\end{array}\right];$

该矩阵值将作为遗传算法的重要参数，以构成遗传算法的满意度函 数，其中，wij表示第i个用户对第j个资源的满意度。

wnm表示第n个用户对第m个资源的满意度。wnm中的n和m分 别表示用户作业个数和资源个数，而wij中i和j分表表示具体的第 i个用户作业和具体的第j个资源。

其完成的任务是将接受的作业1，2，......，n分别分配到资源 1，2，......，m。由于调度问题属于NP问题，采用传统算法往往难以 得到全局最优解。遗传算法以其优异的全局寻优能力脱颖于众多调度 算法。染体编码、种初始化、遗传操作、适应度评估。

算法的流程如图2所示：

1)染体编码

染体为一个n维的元素为整数的矢量D＝[d1，d2，L，dn]。 di(i＝1～n)，为整数，表示第i个作业被分配到了第di个资源上。di 的取值范围为1～m。可见，D矢量完全代表了当前作业1，2，......，n的 分配资源情况。

D＝[d1，d2，L，dn]，di(i＝1～n)，di为整数，个数是n个，取值范围 为1～m，正好表达了n个用户作业分别分配到m个资源上；本发明 中的用户和用户作业含义相同，用户的满意度是通过用户作业的满意 度来体现的。

种初始化：

设置种大小popNum后，算法将进行随机初始化，生成popNum 个染体，每个染体中的元素均为随机生成，随机数的范围位于 1～m之间。

2)适应度评估

初始化完成之后，需要对种中染体的适应度进行评估。设计 合理的适应度函数是遗传算法的关键，因为适应度诱导了种的进化 方向，不当的适应度函数可能导致种收敛解与最优解得较大偏差。

如步骤2中对满意度的阐述，第i个作业分配到第d_i个资源上，导
致此时用户的满意度如下：

$s_{i,d_i}=w_{\mathrm{it}}\frac{r_{d_i}}{r_b}+w_{\mathrm{ie}}\frac{c_b}{c_{d_i}}$

资源可信度矩阵R和费用矩阵C作为满意度函数矩阵的一部
分，把资源可信度融入到用户满意度的函数中，来构遗传算法(用于
资源调度)中最核心的部分，即满意度函数。

由于同一资源可能分配到多个作业，导致实际上多个作业分享同
一资源的可信度。因此根据每个资源分配到的作业数量，需要对用户
的满意度函数作出调整。令资源d_i同时分配到的作业数量是得到
修正的用户满意度函数如下：

$s_{i,d_i}=w_{\mathrm{it}}\frac{1}{h_{d_i}}\frac{r_{d_i}}{r_b}+w_{\mathrm{ie}}\frac{c_b}{c_{d_i}}$

适应度评估函数如下：

$\mathrm{fitness}=\underset{i=1}{\overset{n}{\Sigma }}{s}_{i,d_i}$

3)遗传操作：

首先进行选择，选择是指依据一定的原则和偏好，从染体种 中选出个体进行繁殖，通常的原则是适应度越高的个体被选择的机会 越大，本文采用的是基于赌的选择机制，即将个体适应度占总体 适应度的比例作为个体被选中的概率。

杂交是选择出两个或者多个染体后，随机选中染体中的某个 位点，将之分为两段，把两个染体的前后段互换，以产生两个新一 代的个体。

变异是以变异率为概率重新随机生成一条染体上的的某些位 码。恰当的变异率可以增强算法的全局寻优能力，但过大则会导致算 法难以收敛。本遗传算法的杂交采用单点杂交，如上面蓝部分文字 的陈述，算例中的交叉概率均取Pc＝0.6。变异采用常规的变异方法， 变异概率取Pc＝0.1，变异后仍然生成一个新的个体，同没有变异的个 体一起，参与到下一轮的优胜劣汰中。

下面列举具体实施例对本发明进行说明。

实施例1：基于JACK agent语言，实现了Multi-agent分布式调 度策略的仿真。提交的作业种类和数量如表1所示。

表1 作业种类和数量

由表1可知，根据作业运行基准时间(基准时间设为在主频 1GHZ的CPU中运行的时间)长短，作业类型分为简单、中等和困 难三类。每类作业中，用户的组成又各有不同。如在简单作业类型中， 70％的作业为经济优先，性能优先和均衡类型则各占15％。这是由于 简单作业完成快速，运行时间短，因此用户更偏向对其经济性有要求。 在中等作业类型中，性能优先、经济优先、均衡类型近似各占1/3。 最后，对于困难作业，由于其运行时间较长，用户更关注其性能，因 此性能优先作业占70％，其他两类各占15％。

上述任务并非同一时间释放给Multi-agent系统，而是在1小时 的时间里随机释放给Multi-agent系统。

设置Multi-agent系统中资源Agent的数目为10。资源Agent的 组成如表2所示：

表2 资源agent组成

  主频/Hz 运行时间

Agent 1～3 500M 基准运行时间*2

Agent 4～7 1G 基准运行时间

Agent 8～10 2G 基准运行时间/2

将本算法与随机调度算法与最小负载调度算法进行比较。得到平 均响应时间与用户满意度如表3所示：

表3 平均响应时间及用户满意度对比

由上述结果可知，Multi-agent的平均响应时间和用户总体满意度 均要优于随机调度算法和最小负载调度算法，其中用户总体满意度显 著优于另外两种算法。

本发明的有益效果是本发明建立了综合考虑用户满意度和资源 可信度的评估模型，依据此模型设计了基于遗传算法的资源调度策 略，并提出以Multi-agent为框架的分布式系统资源调度系统架构。 综合提升了用户的满意度，降低了作业的平均返回时间，提高了分布 式系统的运行效率。

以上所述仅是对本发明的较佳实施方式而已，并非对本发明作任 何形式上的限制，凡是依据本发明的技术实质对以上实施方式所做的 任何简单修改，等同变化与修饰，均属于本发明技术方案的范围内。

索引目录：

[1]周文俊，曹健.基于预测及蚁算法的云计算资源调度策略[J].计算机仿真，2012，29(9)：239-242.

[2]M ITZENMACH ER M.The power of two choices in randomized load balancing[J]IEEE Transactions on  Parallel and Distributed Systems，2001，12(10)：1094-1104.

[3]徐炜民，蔡欣欢，沈文枫，支凤麟.基于可信度的分布式资源调度系统[J].上海大学学报(自然科学 版)，2009，15(1)：77～80

[4]DAH LIN M.Interpreting stale load info rma tion[J].IEEE Transactions on Para llel and D istributed  Systems，2000，11(10)：1033-1047.

[5]王晓光，王永滨，杨晓刚.基于用户总体满意度的遗传任务调度算法[J].中国传媒大学学 报，2010，17(3)：53～56

[6]Glatard T，Montagnat J，Lingrand D，et al.Flexible and efficient workflow deployment of data-intensive  applications on grids with MOTEUR.International Journal of High Performance Computing Applications.2008

[7]汤小春，李洪华.分布式系统中计算作业流的均衡调度算法[J].计算机工程，2010，36(19)：78～80

[8]TStutzle，M Dorigo.A short convergence p roof for a class of antcolony optimization algorithms[J].IEEE  Transactions on Evolutionary Computation，2002，6(4)：358-365.

[9]孙俊，须文波.一种基于遗传算法的分布式系统的任务调度[J].计算机工程与应 用，2003，39(21)：105～106，121

[10]梁根，秦勇，郭小雪，梁活民.基于动态多处理节点的分布式系统任务调度[J].计算机工 程，2009，35(9)：31～33，3

[11]梁根，郭小雪，秦勇.基于公平调度算法的分布式系统负载均衡研究[J].计算机工程与设 计，2008，29(6)：1362～1364

[12]张衡，陈超，曾磊.P2P网络中移动agent的搜索资源分配研究[J].西南师范大学学报(自然科学版)， 2010.35(1)：164-167.

[13]张笑语，李立新.基于移动Agent的分布式资源分配策略[J].电子科技大学学报(自然科学 版)，2007，36(6)：1393～1395

[14]夏洪山，许峰.分布式实时系统中的多Agent调度[J].南京航空航天大学学报，2004，36(3)：302～307.

[15]陶剑文，王凤儒.一种优化的多Agent相关任务并行调度算法[J].计算机应用，2007，27(3)：756～758.