唐瑞春，邱 悅，丁香乾，李 靜

(1.中國海洋大學 信息科學與工程學院，山東 青島266100;2.海爾數(shù)字化家電國家重點實驗室，山東 青島266101)

0 引 言

在自然界中，云媒體調(diào)度服務大量存在，且傳輸過程中總是受到帶寬和計算資源的限制，降低了調(diào)度服務的滿意度。提高云媒體調(diào)度服務滿意度的方法是合理分配資源，因此云媒體資源分配技術(shù)是當今較熱門的研究課題［1-3］。文獻［1］提出了一種考慮能源參數(shù)的組合拍賣機制的資源分配模型，提高了數(shù)據(jù)中心的資源利用率。文獻［2］結(jié)合博弈理論以及擁塞控制算法提出線性的帶寬資源分配方案，提高了帶寬效用。Ye 等［3］綜合考慮服務的負載均衡博弈算法以及虛擬機的配置博弈算法來優(yōu)化數(shù)據(jù)中心的資源。以上策略雖然從云媒體服務提供者 CP(Cloud-service provider)的能源消耗角度進行資源分配，但是缺少對云媒體服務請求者 CR(Cloud-service requester)的QoS 特性支持，形成了提高CR 服務滿意度的瓶頸。因此，研究一般意義下的云媒體資源分配的整體滿意度具有重要意義。

一種常用的方法是通過滿足SLAs 協(xié)議來提高服務滿意度［4-5］。Copil 等［4］提出了一種基于粒子群優(yōu)化技術(shù)的服務等級協(xié)議，保證了資源消耗和性能之間的平衡。Son 等［5］提出了一種基于SLAs 的云計算框架，充分考慮了分布式數(shù)據(jù)中心的工作量和地理位置，合理地運用云數(shù)據(jù)中心。以上幾個策略沒有考慮資源分配的效用值，因此整體云媒體服務效用不高。

為了解決上述問題，本文綜合考慮了CR 和CP 服務雙方的QoS 支持和云媒體資源分配服務的效用值，提出了一種基于協(xié)商機制的云媒體資源分配調(diào)度算法RAANM，首先引入CP 和CR 的效用函數(shù)模型，從服務價格、服務響應時間和服務帶寬3 個方面對該模型進行了統(tǒng)一化描述，然后結(jié)合云媒體服務雙方的評價和讓步策略對云媒體資源進行協(xié)商，得到能夠提高服務效用的云媒體資源分配策略。最后給出了資源分配效用最大的協(xié)商算法。

1 目標函數(shù)的確定和研究環(huán)境

1.1 云媒體資源分配服務效用的目標函數(shù)

傳統(tǒng)的媒體資源分配調(diào)度策略采用基于QoS特性和優(yōu)化配置虛擬機的分配算法。為了提高分配的服務滿意度，很多媒體資源分配策略都引入了QoS 以及數(shù)據(jù)中心資源利用率等參數(shù)。例如文獻［6］將CPU 作為虛擬機的線性資源效用參數(shù)，使得CR 可通過動態(tài)的效用函數(shù)來獲得服務，從而獲得較高的服務滿意度以及最小的能源消耗;文獻［7］提出了基于隊列模型的優(yōu)化云媒體資源分配算法，綜合考慮了減少服務響應時間和服務資源消耗，通過提高算法的QoS 特性來獲得較高的服務滿意度。

服務效用可以描述云服務的滿意度。本文從提高云媒體服務效用的角度出發(fā)，其目標函數(shù)不再是最小化響應時間，而是最大化服務效用值，充分提高云用戶的滿意度。由于云媒體中的資源調(diào)度和傳輸需要大量的帶寬和計算資源，所以本文將云媒體任務傳輸帶寬B 作為一個重要的云媒體服務參數(shù)，結(jié)合云媒體服務價格P 和云媒體服務的響應時間RT 的效用函數(shù)，提出了云媒體服務的價格、時間塊和帶寬的效用模型。通過提高云媒體服務的效用，提高云媒體服務的滿意度，目標函數(shù)模型為:

式中:U(P，RT，B)為CP 和CR 的綜合效用函數(shù);UP(P，RT，B)、UR(P，RT，B)分別為CP 和CR效用函數(shù)，具體描述在第3 節(jié)中給出;分別為CP 和CR 所能接受的最小效用值，如果CP或CR 的效用值低于最小效用，那么此次分配失敗;ωP、ωR分別為CP 和CR 的綜合效用權(quán)值。

1.2 研究環(huán)境

圖1 云媒體資源分配框架Fig.1 Cloud media resource allocation framework

如圖1 所示，首先CR 發(fā)出云媒體任務請求并給出描述任務的協(xié)商參數(shù)，將任務提交給云媒體資源分配中心的任務調(diào)度模塊，由任務調(diào)度模塊將任務提交至任務解析模塊，從而解析任務并將任務及其協(xié)商參數(shù)提交至服務協(xié)商模塊，服務協(xié)商模塊與資源分配模塊進行協(xié)商，利用式(1)得到最優(yōu)效用協(xié)商參數(shù)組合，執(zhí)行RAANM 協(xié)商算法得出相應的云媒體資源組合，分配給CR。

2 基于云媒體特性的效用函數(shù)

效用函數(shù)描述了用戶對于所獲得的服務在一定衡量單位下的滿意度［8］。本文根據(jù)SLAs 協(xié)議結(jié)合媒體特性給出基于云媒體特性的效用函數(shù)。其中SLAs 是一種服務保證，它定義了一組QoS參數(shù)集合，并可以描述服務策略。由于媒體服務請求需要支付一定的代價，適中的服務價格可以很好地反映出云媒體服務的效用。同時，媒體服務(如媒體的實時播放，視頻的同步播放等)對時間具有很高的要求，因此云媒體服務具有一定的時效性［9-10］，合理的響應時間會反映出云媒體服務較高的效用。此外，媒體的傳輸需要大量的帶寬，適中的帶寬會提高云媒體服務的效用。因此，把對云媒體服務的價格、響應時間和帶寬作為所考慮的QoS 參數(shù)集合，通過計算每個參數(shù)的效用函數(shù)來獲得云媒體服務的綜合效用函數(shù)，進而提高云媒體服務效用。

2.1 效用函數(shù)模型

將QoS 參數(shù)集合表示成Q={P，RT，B}，CR對于Q 中每個參數(shù)的效用函數(shù)可以用如下模型表示:

CP 對于Q 中每個參數(shù)的效用函數(shù)可以用如下模型表示:

2.2 云媒體服務價格的效用函數(shù)

CR 偏好于每一次請求云媒體服務使用最低的價格，CR 的云媒體服務價格效用函數(shù)URP(P)在式(2)中給出，CR 的最佳期望價格和最差期望價格分別對應式(2)中的IXR和RXR。

而CP 偏好于每一次提供的服務獲得最多的收益，CP 的云媒體服務價格效用函數(shù)UPP(P)在式(3)中給出，CP 的初始價格和保留價格分別對應式(3)中的IXP和RXP。

2.3 云媒體服務響應時間的效用函數(shù)

CR 偏好于每一次請求云媒體服務響應時間最小，CR 的云媒體服務響應時間的效用函數(shù)在式(2)中給出，CR 的最佳期望響應時間和最差響應時間分別對應式(2)中的IXR和RXR。

2.4 云媒體服務帶寬的效用函數(shù)

CR 獲得帶寬B 的云媒體服務資源所獲得的效用函數(shù)為:

式中:IBR、RBR分別代表CR 對于云媒體服務的最高期望帶寬和最低期望帶寬;i 根據(jù)結(jié)果設置。

將式(2)代入式(4)中得到CR 的帶寬效用函數(shù)為:

2.5 云媒體服務綜合效用函數(shù)

用ωP、ωRT和ωB分別表示云媒體服務P，RT和B 的效用權(quán)值，ωP+ωRT+ωB=1，則對于CR或CP，其總效用函數(shù)為:

通過改變ωP、ωRT和ωB的值，CR 可以在協(xié)商中改變云媒體服務P、RT 和B 所占的比重。如果UP(P)=0、URT(RT)=0 或UB(B)=0，那么總效用為0，則此次協(xié)商失敗。

3 基于協(xié)商機制的資源分配算法RAANM

在圖1 中CR 通過第2 節(jié)中得出的云媒體資源綜合效用函數(shù)計算出云媒體服務雙方的效用值，進而服務協(xié)商模塊的云媒體任務協(xié)商參數(shù)對CP 的云媒體資源進行評價(通過計算效用值)，如果求解出滿足CR 請求云媒體服務的最大效用值，則協(xié)商成功，資源分配模塊分配資源。若，則檢查CR 的云媒體任務請求是否超時，如果超時則協(xié)商失敗，如果沒有超時，則執(zhí)行讓步策略，讓步步長為［11］:

式中:t、τ 分別表示協(xié)商次數(shù)(最大協(xié)商次數(shù))和截止時間;λ 為對讓步速率控制的參數(shù)，下一次CR 請求云媒體服務期望效用值為:

進行讓步策略后，再次對云媒體資源進行協(xié)商。

RAANM 算法描述如下。

輸入:m 個云媒體任務請求集合R ={R1，…，Ri，…，Rm};n 個可以提供云媒體資源集合P={P1，…，Pj，…，Pn};n 個可以提供云媒體資源對應的屬性集合Q ={Q1，…，Qj，…，Qn}，其中Qj={Pj，RTj，Bj}。

輸出:m 個云媒體任務分配的資源。

算法步驟:

4 算法分析

采用CloudSim 云仿真平臺，利用云媒體任務請求參數(shù)和云媒體資源的協(xié)商屬性作為輸入，評估RAANM 算 法、貪 婪 分 配 GA［12］(Greedy allocation)算法以及隨機分配 RA(Random allocation)算法的性能。

4.1 仿真參數(shù)設置

分別將云媒體請求任務數(shù)目由100 增至700對算法進行評價，其中云媒體請求任務的屬性參數(shù)由系統(tǒng)在一定范圍內(nèi)隨機生成，生成的隨機數(shù)滿足以下條件:式中:Se、So分別對應云媒體請求任務的作業(yè)可執(zhí)行文件的大小和作業(yè)執(zhí)行后需要傳輸?shù)慕Y(jié)果文件大小;α 為相應系數(shù)，通過對α 的設置可以反映云媒體服務P、B 和RT 之間的關系。

云媒體資源屬性首先劃分不同等級，分別對應不同的價格、響應時間和帶寬的范圍，參數(shù)設置滿足式(9)，其他參數(shù)設置如下:

4.2 云媒體服務響應時間分析

服務的執(zhí)行時間可以評價整個云媒體資源分配的性能，因此對云媒體服務的執(zhí)行時間進行了性能分析。執(zhí)行時間定義為，分別將云媒體任務請求數(shù)量由100 增至700。采用響應時間、傳輸帶寬作為云媒體資源分配的參數(shù)，并對參數(shù)的效用值進行最大化選擇，因此可以獲得較短的服務響應時間，仿真結(jié)果如圖2 所示。

圖2 云媒體服務響應時間比較Fig.2 Cloud media service response time comparison

圖2 說明了云媒體服務開始時，任務請求較少，資源較為充足，3 種算法的響應時間基本相同，但隨著任務請求的增加，RAANM 算法表現(xiàn)出良好的穩(wěn)定性，而且響應時間要優(yōu)于其他兩種算法。

4.3 云媒體服務效用分析

云媒體服務的效用值可以反映出云媒體的服務滿意度，將云媒體任務請求數(shù)量從100 增至700 對云媒體服務的效用值進行性能分析。RAANM 算法通過對參數(shù)的效用計算，得出最大化的云媒體資源分配效用，因此可以獲得很好的云媒體服務效用值，仿真結(jié)果如表1 所示。

表1 云媒體服務效用值比較Table 1 Cloud media services utility value comparison

表1 表明了隨著云媒體任務請求數(shù)量的增加，RAANM 算法的云媒體服務平均效用值高于其他兩種算法，因此可以更好地滿足SLAs 協(xié)議，從而提高云媒體服務的滿意度。

4.4 對RAANM 協(xié)商參數(shù)不同權(quán)重值的性能分析

分別對云媒體服務的P、RT 和B 參數(shù)的權(quán)重值進行設置，結(jié)果如表2 所示。

表2 不同的云媒體服務權(quán)重值Table 2 Different weights of cloud media services

圖3 和表3 分別表示對于不同權(quán)重值的RAANM 算法，云媒體服務的響應時間和效用值。圖3 表示了當對響應時間的權(quán)重加大，云媒體服務的響應時間隨之減小。表3 表明對協(xié)商參數(shù)權(quán)值改變，RAANM 算法的總效用值仍然比較穩(wěn)定。從而說明了RAANM 算法的穩(wěn)定性。

圖3 對于不同協(xié)商參數(shù)權(quán)重值的云媒體服務響應時間比較Fig.3 Negotiation parameters for different weights cloud media service response time comparison

表3 對于不同協(xié)商參數(shù)權(quán)重值的云媒體服務效用值比較Table 3 Negotiation parameters for different weights cloud media service utility value comparison

5 結(jié)束語

提出了一種基于協(xié)商機制的資源分配調(diào)度算法RAANM。通過協(xié)商策略進行云媒體的資源分配，從而獲得較高的服務效用值，進而可以更好地滿足SLAs 協(xié)議，實現(xiàn)較高的服務等級，提高云媒體服務的滿意度。

［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，F(xiàn)reisleben 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］唐瑞春，馮驍，丁香乾，等.基于上下文感知的內(nèi)容適應算法及其在UPnP AV 中的應用［J］.吉林大學學報:工學版，2014，44(5):1441-1446.Tang Rui-chun，F(xiàn)eng 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.