基于效用最大化协商机制的云媒体资源分配算法

唐瑞春，邱 悦，丁香乾，李 静

(1.中国海洋大学 信息科学与工程学院，山东 青岛266100;2.海尔数字化家电国家重点实验室，山东 青岛266101)

0 引 言

在自然界中，云媒体调度服务大量存在，且传输过程中总是受到带宽和计算资源的限制，降低了调度服务的满意度。提高云媒体调度服务满意度的方法是合理分配资源，因此云媒体资源分配技术是当今较热门的研究课题［1-3］。文献［1］提出了一种考虑能源参数的组合拍卖机制的资源分配模型，提高了数据中心的资源利用率。文献［2］结合博弈理论以及拥塞控制算法提出线性的带宽资源分配方案，提高了带宽效用。Ye 等［3］综合考虑服务的负载均衡博弈算法以及虚拟机的配置博弈算法来优化数据中心的资源。以上策略虽然从云媒体服务提供者 CP(Cloud-service provider)的能源消耗角度进行资源分配，但是缺少对云媒体服务请求者 CR(Cloud-service requester)的QoS 特性支持，形成了提高CR 服务满意度的瓶颈。因此，研究一般意义下的云媒体资源分配的整体满意度具有重要意义。

一种常用的方法是通过满足SLAs 协议来提高服务满意度［4-5］。Copil 等［4］提出了一种基于粒子群优化技术的服务等级协议，保证了资源消耗和性能之间的平衡。Son 等［5］提出了一种基于SLAs 的云计算框架，充分考虑了分布式数据中心的工作量和地理位置，合理地运用云数据中心。以上几个策略没有考虑资源分配的效用值，因此整体云媒体服务效用不高。

为了解决上述问题，本文综合考虑了CR 和CP 服务双方的QoS 支持和云媒体资源分配服务的效用值，提出了一种基于协商机制的云媒体资源分配调度算法RAANM，首先引入CP 和CR 的效用函数模型，从服务价格、服务响应时间和服务带宽3 个方面对该模型进行了统一化描述，然后结合云媒体服务双方的评价和让步策略对云媒体资源进行协商，得到能够提高服务效用的云媒体资源分配策略。最后给出了资源分配效用最大的协商算法。

1 目标函数的确定和研究环境

1.1 云媒体资源分配服务效用的目标函数

传统的媒体资源分配调度策略采用基于QoS特性和优化配置虚拟机的分配算法。为了提高分配的服务满意度，很多媒体资源分配策略都引入了QoS 以及数据中心资源利用率等参数。例如文献［6］将CPU 作为虚拟机的线性资源效用参数，使得CR 可通过动态的效用函数来获得服务，从而获得较高的服务满意度以及最小的能源消耗;文献［7］提出了基于队列模型的优化云媒体资源分配算法，综合考虑了减少服务响应时间和服务资源消耗，通过提高算法的QoS 特性来获得较高的服务满意度。

服务效用可以描述云服务的满意度。本文从提高云媒体服务效用的角度出发，其目标函数不再是最小化响应时间，而是最大化服务效用值，充分提高云用户的满意度。由于云媒体中的资源调度和传输需要大量的带宽和计算资源，所以本文将云媒体任务传输带宽B 作为一个重要的云媒体服务参数，结合云媒体服务价格P 和云媒体服务的响应时间RT 的效用函数，提出了云媒体服务的价格、时间块和带宽的效用模型。通过提高云媒体服务的效用，提高云媒体服务的满意度，目标函数模型为:

式中:U(P，RT，B)为CP 和CR 的综合效用函数;UP(P，RT，B)、UR(P，RT，B)分别为CP 和CR效用函数，具体描述在第3 节中给出;分别为CP 和CR 所能接受的最小效用值，如果CP或CR 的效用值低于最小效用，那么此次分配失败;ωP、ωR分别为CP 和CR 的综合效用权值。

1.2 研究环境

图1 云媒体资源分配框架Fig.1 Cloud media resource allocation framework

如图1 所示，首先CR 发出云媒体任务请求并给出描述任务的协商参数，将任务提交给云媒体资源分配中心的任务调度模块，由任务调度模块将任务提交至任务解析模块，从而解析任务并将任务及其协商参数提交至服务协商模块，服务协商模块与资源分配模块进行协商，利用式(1)得到最优效用协商参数组合，执行RAANM 协商算法得出相应的云媒体资源组合，分配给CR。

2 基于云媒体特性的效用函数

效用函数描述了用户对于所获得的服务在一定衡量单位下的满意度［8］。本文根据SLAs 协议结合媒体特性给出基于云媒体特性的效用函数。其中SLAs 是一种服务保证，它定义了一组QoS参数集合，并可以描述服务策略。由于媒体服务请求需要支付一定的代价，适中的服务价格可以很好地反映出云媒体服务的效用。同时，媒体服务(如媒体的实时播放，视频的同步播放等)对时间具有很高的要求，因此云媒体服务具有一定的时效性［9-10］，合理的响应时间会反映出云媒体服务较高的效用。此外，媒体的传输需要大量的带宽，适中的带宽会提高云媒体服务的效用。因此，把对云媒体服务的价格、响应时间和带宽作为所考虑的QoS 参数集合，通过计算每个参数的效用函数来获得云媒体服务的综合效用函数，进而提高云媒体服务效用。

2.1 效用函数模型

将QoS 参数集合表示成Q={P，RT，B}，CR对于Q 中每个参数的效用函数可以用如下模型表示:

CP 对于Q 中每个参数的效用函数可以用如下模型表示:

2.2 云媒体服务价格的效用函数

CR 偏好于每一次请求云媒体服务使用最低的价格，CR 的云媒体服务价格效用函数URP(P)在式(2)中给出，CR 的最佳期望价格和最差期望价格分别对应式(2)中的IXR和RXR。

而CP 偏好于每一次提供的服务获得最多的收益，CP 的云媒体服务价格效用函数UPP(P)在式(3)中给出，CP 的初始价格和保留价格分别对应式(3)中的IXP和RXP。

2.3 云媒体服务响应时间的效用函数

CR 偏好于每一次请求云媒体服务响应时间最小，CR 的云媒体服务响应时间的效用函数在式(2)中给出，CR 的最佳期望响应时间和最差响应时间分别对应式(2)中的IXR和RXR。

2.4 云媒体服务带宽的效用函数

CR 获得带宽B 的云媒体服务资源所获得的效用函数为:

式中:IBR、RBR分别代表CR 对于云媒体服务的最高期望带宽和最低期望带宽;i 根据结果设置。

将式(2)代入式(4)中得到CR 的带宽效用函数为:

2.5 云媒体服务综合效用函数

用ωP、ωRT和ωB分别表示云媒体服务P，RT和B 的效用权值，ωP+ωRT+ωB=1，则对于CR或CP，其总效用函数为:

通过改变ωP、ωRT和ωB的值，CR 可以在协商中改变云媒体服务P、RT 和B 所占的比重。如果UP(P)=0、URT(RT)=0 或UB(B)=0，那么总效用为0，则此次协商失败。

3 基于协商机制的资源分配算法RAANM

在图1 中CR 通过第2 节中得出的云媒体资源综合效用函数计算出云媒体服务双方的效用值，进而服务协商模块的云媒体任务协商参数对CP 的云媒体资源进行评价(通过计算效用值)，如果求解出满足CR 请求云媒体服务的最大效用值，则协商成功，资源分配模块分配资源。若，则检查CR 的云媒体任务请求是否超时，如果超时则协商失败，如果没有超时，则执行让步策略，让步步长为［11］:

式中:t、τ 分别表示协商次数(最大协商次数)和截止时间;λ 为对让步速率控制的参数，下一次CR 请求云媒体服务期望效用值为:

进行让步策略后，再次对云媒体资源进行协商。

RAANM 算法描述如下。

输入:m 个云媒体任务请求集合R ={R1，…，Ri，…，Rm};n 个可以提供云媒体资源集合P={P1，…，Pj，…，Pn};n 个可以提供云媒体资源对应的属性集合Q ={Q1，…，Qj，…，Qn}，其中Qj={Pj，RTj，Bj}。

输出:m 个云媒体任务分配的资源。

算法步骤:

4 算法分析

采用CloudSim 云仿真平台，利用云媒体任务请求参数和云媒体资源的协商属性作为输入，评估RAANM 算 法、贪 婪 分 配 GA［12］(Greedy allocation)算法以及随机分配 RA(Random allocation)算法的性能。

4.1 仿真参数设置

分别将云媒体请求任务数目由100 增至700对算法进行评价，其中云媒体请求任务的属性参数由系统在一定范围内随机生成，生成的随机数满足以下条件:式中:Se、So分别对应云媒体请求任务的作业可执行文件的大小和作业执行后需要传输的结果文件大小;α 为相应系数，通过对α 的设置可以反映云媒体服务P、B 和RT 之间的关系。

云媒体资源属性首先划分不同等级，分别对应不同的价格、响应时间和带宽的范围，参数设置满足式(9)，其他参数设置如下:

4.2 云媒体服务响应时间分析

服务的执行时间可以评价整个云媒体资源分配的性能，因此对云媒体服务的执行时间进行了性能分析。执行时间定义为，分别将云媒体任务请求数量由100 增至700。采用响应时间、传输带宽作为云媒体资源分配的参数，并对参数的效用值进行最大化选择，因此可以获得较短的服务响应时间，仿真结果如图2 所示。

图2 云媒体服务响应时间比较Fig.2 Cloud media service response time comparison

图2 说明了云媒体服务开始时，任务请求较少，资源较为充足，3 种算法的响应时间基本相同，但随着任务请求的增加，RAANM 算法表现出良好的稳定性，而且响应时间要优于其他两种算法。

4.3 云媒体服务效用分析

云媒体服务的效用值可以反映出云媒体的服务满意度，将云媒体任务请求数量从100 增至700 对云媒体服务的效用值进行性能分析。RAANM 算法通过对参数的效用计算，得出最大化的云媒体资源分配效用，因此可以获得很好的云媒体服务效用值，仿真结果如表1 所示。

表1 云媒体服务效用值比较Table 1 Cloud media services utility value comparison

表1 表明了随着云媒体任务请求数量的增加，RAANM 算法的云媒体服务平均效用值高于其他两种算法，因此可以更好地满足SLAs 协议，从而提高云媒体服务的满意度。

4.4 对RAANM 协商参数不同权重值的性能分析

分别对云媒体服务的P、RT 和B 参数的权重值进行设置，结果如表2 所示。

表2 不同的云媒体服务权重值Table 2 Different weights of cloud media services

图3 和表3 分别表示对于不同权重值的RAANM 算法，云媒体服务的响应时间和效用值。图3 表示了当对响应时间的权重加大，云媒体服务的响应时间随之减小。表3 表明对协商参数权值改变，RAANM 算法的总效用值仍然比较稳定。从而说明了RAANM 算法的稳定性。

图3 对于不同协商参数权重值的云媒体服务响应时间比较Fig.3 Negotiation parameters for different weights cloud media service response time comparison

表3 对于不同协商参数权重值的云媒体服务效用值比较Table 3 Negotiation parameters for different weights cloud media service utility value comparison

5 结束语

提出了一种基于协商机制的资源分配调度算法RAANM。通过协商策略进行云媒体的资源分配，从而获得较高的服务效用值，进而可以更好地满足SLAs 协议，实现较高的服务等级，提高云媒体服务的满意度。

［1］Huu T T，Tham C K.An auction-based resource allocation model for green cloud computing［C］∥2013 IEEE International Conference on Cloud Engineering，Redwood City，CA，2013:269-278.

［2］Wang L J，Meng M Q H.A game theoretical bandwidth allocation mechanism for cloud robotics［C］∥2012 10th World Congress on Intelligent Control and Automation，Beijing，2012:3828-3833.

［3］Ye D S，Chen J H.Non-cooperative games on multi-dimensional resource allocation［J］.Future Generation Computer Systems，2013，29(6):1345-1352.

［4］Copil G，Moldovan D，Salomie I.Cloud SLA negotiation for energy saving-A particle swarm optimization approach［C］∥2012 IEEE 8th International Conference on Intelligent Computer Communication and Processing，Cluj-Napoca，2012:289-296.

［5］Son S，Jung G，Jun S C.An SLA-based cloud computing that facilitates resource allocation in the distributed data centers of a cloud provider［J］.Journal of Supercomputing，2013，64(2):606-637.

［6］Minarolli D，Freisleben B.Utility-based resource allocation for virtual machines in Cloud computing［C］∥2011 IEEE Symposium on Computers and Communications，Kerkyra，2011:410-417.

［7］Nan X，He Y，Guan L.Optimal resource allocation for multimedia cloud based on queuing model［C］∥13th International Workshop on Multimedia Signal Processing，Hangzhou，2011:1-6.

［8］Li S Y，Yang D，Qin Y J，et al.Network cross-layer mapping based on utility maximization［J］.Journal of Software，2011，22(8):1855-1871.

［9］Hong Bo-hai，Tang Rui-chun，Zhai Yi-li，et al.A resources allocation algorithm based on media task QoS in cloud computing［C］∥The 4th IEEE International Conference on Software Engineering and Service Sciences，Beijing，2013:841-844.

［10］唐瑞春，冯骁，丁香乾，等.基于上下文感知的内容适应算法及其在UPnP AV 中的应用［J］.吉林大学学报:工学版，2014，44(5):1441-1446.Tang Rui-chun，Feng Xiao，Ding Xiang-qian，et al.Contest-based content adaptation algorithm and its application in UPnP AV［J］.Journal of Jilin University(Engineering and Technology Edition)，2014，44(5):1441-1446.

［11］Son S，Sim K M.A price-and-time-slot-negotiation mechanism for cloud service reservations［J］.IEEE Transactions on Systems，Man，and Cybernetics，Part B:Cybernetics，2012，42(3):713-728.

［12］Ma L，Lu Y M，Zhang F WA，et al.Dynamic task scheduling in cloud computing based on greedy strategy［C］∥Trustworthy Computing and Services，Beijing，China，2013:156-162.