基于效用最大化協(xié)商機(jī)制的云媒體資源分配算法

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

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

0 引 言

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

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

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

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

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

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

服務(wù)效用可以描述云服務(wù)的滿意度。本文從提高云媒體服務(wù)效用的角度出發(fā)，其目標(biāo)函數(shù)不再是最小化響應(yīng)時(shí)間，而是最大化服務(wù)效用值，充分提高云用戶的滿意度。由于云媒體中的資源調(diào)度和傳輸需要大量的帶寬和計(jì)算資源，所以本文將云媒體任務(wù)傳輸帶寬B 作為一個(gè)重要的云媒體服務(wù)參數(shù)，結(jié)合云媒體服務(wù)價(jià)格P 和云媒體服務(wù)的響應(yīng)時(shí)間RT 的效用函數(shù)，提出了云媒體服務(wù)的價(jià)格、時(shí)間塊和帶寬的效用模型。通過提高云媒體服務(wù)的效用，提高云媒體服務(wù)的滿意度，目標(biāo)函數(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ā)出云媒體任務(wù)請(qǐng)求并給出描述任務(wù)的協(xié)商參數(shù)，將任務(wù)提交給云媒體資源分配中心的任務(wù)調(diào)度模塊，由任務(wù)調(diào)度模塊將任務(wù)提交至任務(wù)解析模塊，從而解析任務(wù)并將任務(wù)及其協(xié)商參數(shù)提交至服務(wù)協(xié)商模塊，服務(wù)協(xié)商模塊與資源分配模塊進(jìn)行協(xié)商，利用式(1)得到最優(yōu)效用協(xié)商參數(shù)組合，執(zhí)行RAANM 協(xié)商算法得出相應(yīng)的云媒體資源組合，分配給CR。

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

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

2.1 效用函數(shù)模型

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

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

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

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

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

2.3 云媒體服務(wù)響應(yīng)時(shí)間的效用函數(shù)

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

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

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

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

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

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

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

通過改變?chǔ)豍、ωRT和ωB的值，CR 可以在協(xié)商中改變?cè)泼襟w服務(wù)P、RT 和B 所占的比重。如果UP(P)=0、URT(RT)=0 或UB(B)=0，那么總效用為0，則此次協(xié)商失敗。

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

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

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

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

RAANM 算法描述如下。

輸入:m 個(gè)云媒體任務(wù)請(qǐng)求集合R ={R1，…，Ri，…，Rm};n 個(gè)可以提供云媒體資源集合P={P1，…，Pj，…，Pn};n 個(gè)可以提供云媒體資源對(duì)應(yīng)的屬性集合Q ={Q1，…，Qj，…，Qn}，其中Qj={Pj，RTj，Bj}。

輸出:m 個(gè)云媒體任務(wù)分配的資源。

算法步驟:

4 算法分析

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

4.1 仿真參數(shù)設(shè)置

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

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

4.2 云媒體服務(wù)響應(yīng)時(shí)間分析

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

圖2 云媒體服務(wù)響應(yīng)時(shí)間比較Fig.2 Cloud media service response time comparison

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

4.3 云媒體服務(wù)效用分析

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

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

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

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

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

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

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

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

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

5 結(jié)束語

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

［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)容適應(yīng)算法及其在UPnP AV 中的應(yīng)用［J］.吉林大學(xué)學(xué)報(bào):工學(xué)版，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.