計(jì)及客戶等待時(shí)間的云計(jì)算效益模型

馬 浩 陶 鵬 李 鵬 劉林青 趙 佩

1(國網(wǎng)河北省電力有限公司營銷服務(wù)中心 河北 石家莊 050000) 2(國網(wǎng)河北省電力有限公司 河北 石家莊 050000)

0 引 言

作為與信息、軟件和互聯(lián)網(wǎng)相關(guān)的服務(wù),云計(jì)算集成了大量資源和服務(wù),并將其交付到互聯(lián)網(wǎng)上?？蛻艨梢愿鶕?jù)需要獲得這些資源和服務(wù),而無須考慮硬件的維護(hù)和管理。由于其卓越的特性,可以提高客戶工作的效率和體驗(yàn),并減少大量的設(shè)備開支和人力支出。而云服務(wù)供應(yīng)商為了維持云計(jì)算的運(yùn)行,將按使用付費(fèi)的定價(jià)模型向客戶收取必要的費(fèi)用[1]。

通常,根據(jù)不同參與者的目的,可以將云計(jì)算環(huán)境視為三層結(jié)構(gòu),它由基礎(chǔ)結(jié)構(gòu)提供者、云服務(wù)提供者和客戶組成?；A(chǔ)設(shè)施提供商維護(hù)物理設(shè)備,并通過采用虛擬化技術(shù)將其用于構(gòu)建動(dòng)態(tài)資源池。云服務(wù)供應(yīng)商從基礎(chǔ)設(shè)施提供商那里租用資源,并相應(yīng)地支付租賃費(fèi)用,同時(shí),他們構(gòu)建了用于向客戶提供服務(wù)的云計(jì)算平臺(tái)。客戶根據(jù)自身的需求在平臺(tái)上搜尋解決方案,并根據(jù)數(shù)量和質(zhì)量對(duì)提供的服務(wù)收費(fèi)。作為基礎(chǔ)設(shè)施提供商和客戶之間的鏈接,云服務(wù)供應(yīng)商非常重要[2]。此外,效益是云計(jì)算平臺(tái)正常運(yùn)行的基礎(chǔ),它包括來自客戶的收入和基礎(chǔ)設(shè)施提供商的成本。

研究人員對(duì)市場(chǎng)需求、云計(jì)算平臺(tái)中的參數(shù)配置、定價(jià)方式等眾多影響云服務(wù)供應(yīng)商效益的因素進(jìn)行了研究?？紤]到以客戶為導(dǎo)向的服務(wù)需求是云計(jì)算管理機(jī)制的基礎(chǔ),此外,服務(wù)質(zhì)量和服務(wù)價(jià)格是客戶最關(guān)心的問題,因此,在所有這些因素中,云計(jì)算平臺(tái)中參數(shù)的最佳配置和定價(jià)模型是最重要的[3]。但是,高質(zhì)量的服務(wù)始終會(huì)給云服務(wù)供應(yīng)商帶來高昂的成本,這將迫使他們提高服務(wù)價(jià)格以賺取效益,相反,低廉的服務(wù)價(jià)格會(huì)導(dǎo)致服務(wù)質(zhì)量下降。因此,對(duì)于云服務(wù)供應(yīng)商而言,解決增加服務(wù)質(zhì)量和降低服務(wù)價(jià)格之間的權(quán)衡以最大化效益至關(guān)重要。文獻(xiàn)[4]研究了在云計(jì)算環(huán)境中實(shí)現(xiàn)效益最大化的最佳多服務(wù)器配置問題,服務(wù)器的數(shù)量和執(zhí)行速度被視為確定多服務(wù)器系統(tǒng)配置的基本特征。但是,這些方法很少關(guān)注單一多服務(wù)器系統(tǒng)中的效益最大化方案,只能采用這種方法來滿足一種服務(wù)請(qǐng)求。

對(duì)于串聯(lián)結(jié)構(gòu)下的多級(jí)多服務(wù)器隊(duì)列系統(tǒng),每個(gè)系統(tǒng)都被視為M/M/m排隊(duì)模型,每個(gè)階段可以在唯一的多服務(wù)器系統(tǒng)中服務(wù)一種類型的服務(wù)請(qǐng)求,該請(qǐng)求對(duì)應(yīng)于客戶發(fā)布的子任務(wù)。對(duì)于耐心有限的客戶,云服務(wù)供應(yīng)商應(yīng)在云計(jì)算平臺(tái)中配置參數(shù),以盡可能滿足客戶的需求,但是,由于能源支出和租金成本的增長,成本也會(huì)增加。因此,如何優(yōu)化配置參數(shù)以在截止時(shí)間約束下最大化效益是一個(gè)重要的問題。此問題包括三個(gè)子問題:如何按照序列結(jié)構(gòu)對(duì)多級(jí)多服務(wù)器隊(duì)列系統(tǒng)進(jìn)行建模;如何確定客戶在多級(jí)多服務(wù)器隊(duì)列系統(tǒng)中等待的總時(shí)間;如何通過在截止時(shí)間約束下配置云計(jì)算平臺(tái)來實(shí)現(xiàn)效益的最大化。

在考慮多級(jí)多服務(wù)器系統(tǒng)中的效益最大化問題時(shí),相關(guān)研究主要集中在具有并行結(jié)構(gòu)的多服務(wù)器系統(tǒng)上。文獻(xiàn)[5]考慮了具有多條并行生產(chǎn)線的制造系統(tǒng)中的生產(chǎn)設(shè)計(jì)和調(diào)度問題,并通過適當(dāng)配置一些參數(shù)(例如建議的生產(chǎn)率、生產(chǎn)時(shí)間間隔等),提出了效益最大化方案。文獻(xiàn)[6]解決了相同的并行機(jī)器調(diào)度問題,其中包含工作截止時(shí)間和機(jī)器資格約束,以最大限度地減少總的工作完成時(shí)間。由于在這些方法中多級(jí)多服務(wù)器系統(tǒng)以并行結(jié)構(gòu)排列,可以同時(shí)滿足多種類型的服務(wù)請(qǐng)求。但是,他們忽略了所有服務(wù)請(qǐng)求(子任務(wù))之間的內(nèi)部關(guān)系,導(dǎo)致必須成功滿足某些服務(wù)請(qǐng)求(子任務(wù))才能滿足客戶發(fā)布的任務(wù)。因此,研究串聯(lián)結(jié)構(gòu)的多級(jí)多服務(wù)器排隊(duì)系統(tǒng)中的效益最大化問題至關(guān)重要。在考慮具有多階段排隊(duì)系統(tǒng)時(shí),文獻(xiàn)[7]分析了具有不同服務(wù)時(shí)間分布的異構(gòu)服務(wù)的兩個(gè)階段,這些階段受到隨機(jī)故障和帶有一般休假期的強(qiáng)制性服務(wù)器休假的影響。討論了隊(duì)列中的平均客戶數(shù)和平均等待時(shí)間。文獻(xiàn)[8]研究了一個(gè)多階段隊(duì)列系統(tǒng),該系統(tǒng)具有一定數(shù)量的獨(dú)立并行服務(wù)器,并且在所有或某些階段都具有多個(gè)隊(duì)列,并提供了一種有效的方法來管理隊(duì)列,從而在不增加成本的情況下最大化客戶滿意度。所有這些方法主要集中在解決一個(gè)階段中具有單個(gè)服務(wù)器的隊(duì)列系統(tǒng)中的問題,而較少集中于一個(gè)階段中包含多個(gè)服務(wù)器的情況。

由此本文提出計(jì)及等待時(shí)長的云計(jì)算效益模型,考慮以串聯(lián)結(jié)構(gòu)排列的多級(jí)多服務(wù)器隊(duì)列系統(tǒng),分析每級(jí)多服務(wù)器系統(tǒng)中云服務(wù)供應(yīng)商的收入和成本模型,并建立效益最大化模型。根據(jù)客戶可以等待的最大容忍度,在截止期限約束下定義效益最大化問題,并采用啟發(fā)式算法來求解這一模型,從而實(shí)現(xiàn)效益最大化和客戶等待時(shí)間的多目標(biāo)優(yōu)化。通過算例仿真,分析了效益和已執(zhí)行服務(wù)請(qǐng)求的百分比隨期限和服務(wù)請(qǐng)求到達(dá)率的增加而變化。

1 數(shù)學(xué)模型

1.1 云計(jì)算架構(gòu)

為了研究云計(jì)算環(huán)境中服務(wù)和應(yīng)用程序的供求關(guān)系,需要考慮服務(wù)器提供商、云服務(wù)供應(yīng)商和客戶的行為特征。對(duì)于服務(wù)器提供商,他們采用虛擬化技術(shù)來聚合各種IT資源(計(jì)算、網(wǎng)絡(luò)、存儲(chǔ)等),并將其提供給遠(yuǎn)程互聯(lián)網(wǎng)客戶的需求。此外,此類IT資源具有可伸縮性,因此可以根據(jù)客戶的需求進(jìn)行調(diào)整。典型的情況是服務(wù)器的數(shù)量和執(zhí)行速度,這對(duì)于不同的應(yīng)用程序是可變的。

對(duì)于云服務(wù)供應(yīng)商,他們致力于在服務(wù)器提供商和客戶之間建立渠道,從而使客戶無須關(guān)注服務(wù)請(qǐng)求的具體實(shí)施細(xì)節(jié)。實(shí)際上,云服務(wù)供應(yīng)商從基礎(chǔ)設(shè)施提供商那里租用資源,并構(gòu)建云計(jì)算平臺(tái)以向客戶提供服務(wù)。對(duì)于客戶,他們將服務(wù)請(qǐng)求提交給云服務(wù)供應(yīng)商,并根據(jù)指定的服務(wù)級(jí)別協(xié)議為所提供的服務(wù)付費(fèi)。

1.2 多級(jí)多服務(wù)器隊(duì)列系統(tǒng)模型

通常,當(dāng)客戶發(fā)布任務(wù)時(shí),可以始終將其分為多個(gè)子任務(wù),并且這些子任務(wù)的執(zhí)行順序應(yīng)遵循連續(xù)的邏輯關(guān)系。本文假設(shè)每個(gè)子任務(wù)對(duì)應(yīng)一種服務(wù)請(qǐng)求,可以在唯一的多服務(wù)器系統(tǒng)中進(jìn)行服務(wù)。在此基礎(chǔ)上,我們考慮一個(gè)云計(jì)算平臺(tái),多級(jí)多服務(wù)器隊(duì)列系統(tǒng)由nM/M/m排隊(duì)模型組成,它們以串聯(lián)結(jié)構(gòu)排列。對(duì)于每級(jí)多服務(wù)器系統(tǒng)Si,它具有速度為si的多臺(tái)服務(wù)器,其中i=1,2,…,n。一旦客戶發(fā)布任務(wù),則當(dāng)某些服務(wù)器可用時(shí),第一個(gè)子任務(wù)(或第一類服務(wù)請(qǐng)求)將立即在第一級(jí)多服務(wù)器系統(tǒng)中得到服務(wù)。當(dāng)完成第一階段時(shí),在第一階段之后的多服務(wù)器系統(tǒng)將在隨后的階段中依次服務(wù)于后者的子任務(wù)(服務(wù)請(qǐng)求)。不失一般性地,我們將多級(jí)多服務(wù)器隊(duì)列系統(tǒng)視為簡(jiǎn)化形式,其中此類系統(tǒng)只有兩個(gè)級(jí),即n=2,而這種簡(jiǎn)化形式可以很容易地推廣到一般情況。

(1)

(2)

由于兩級(jí)多服務(wù)器系統(tǒng)是按串聯(lián)結(jié)構(gòu)排列的,因此只有在第一級(jí)中服務(wù)第一類服務(wù)請(qǐng)求時(shí),客戶才能將第二類服務(wù)請(qǐng)求發(fā)送到后者中的多服務(wù)器系統(tǒng)。那么我們可以發(fā)現(xiàn)第一級(jí)多服務(wù)器系統(tǒng)的起飛時(shí)間等于第二級(jí)多服務(wù)器系統(tǒng)的起飛時(shí)間,因此,可以認(rèn)為后階段服務(wù)請(qǐng)求的到達(dá)率等于前階段服務(wù)請(qǐng)求的平均服務(wù)率,據(jù)此將平均服務(wù)費(fèi)率描述為期望形式,如式(3)所示。

(3)

實(shí)際上,可以發(fā)現(xiàn)平均服務(wù)速率也等于同一階段的到達(dá)速率。給定條件ρ1<1以確保隊(duì)列系統(tǒng)的遍歷性,從長遠(yuǎn)來看,無須等待就可以響應(yīng)第一級(jí)多服務(wù)器系統(tǒng)的傳入服務(wù)請(qǐng)求。但是,這樣的點(diǎn)在很小的時(shí)間間隔內(nèi)是不正確的,這導(dǎo)致傳入的服務(wù)請(qǐng)求本質(zhì)上是一種隨機(jī)流,這可能導(dǎo)致偶爾的流量突發(fā)暫時(shí)使服務(wù)器不堪重負(fù)。在此基礎(chǔ)上,當(dāng)多服務(wù)器系統(tǒng)中的所有服務(wù)器都被執(zhí)行的服務(wù)請(qǐng)求占用時(shí),則新到達(dá)的服務(wù)請(qǐng)求必須在等待隊(duì)列中等待。在這種情況下,將其概率表示如下:

(4)

令Wi為第i類服務(wù)請(qǐng)求的等待時(shí)間,相應(yīng)的概率分布函數(shù)可以描述如下[8]:

(5)

u(t)是脈沖函數(shù):

(6)

令z→∞,則有:

(7)

1.3 效益模型

在本文中,我們選擇等待時(shí)間來表示服務(wù)質(zhì)量的差異,對(duì)于第一和第二多服務(wù)器系統(tǒng)中服務(wù)請(qǐng)求的服務(wù)收費(fèi)函數(shù)定義如下:

(8)

(9)

式中:a1、a2是常數(shù),代表每單位服務(wù)的服務(wù)費(fèi)用;D是服務(wù)請(qǐng)求可以等待的最大可允許時(shí)間。

本文中假定當(dāng)?shù)却龝r(shí)間不超過最大值時(shí),云服務(wù)供應(yīng)商向客戶收取一定的費(fèi)用。對(duì)于給定的兩階段多服務(wù)器系統(tǒng),可以將這種假設(shè)分為三種情況。首先,如果在前臺(tái)花費(fèi)的第一類服務(wù)請(qǐng)求的等待時(shí)間超過了最后期限,那么即使他們的服務(wù)請(qǐng)求沒有得到服務(wù),客戶也將離開兩階段多服務(wù)器系統(tǒng),并且他們當(dāng)然不應(yīng)該為它們付費(fèi)。其次,如果在截止期限內(nèi)滿足了第一類服務(wù)請(qǐng)求,而總等待時(shí)間超過了,那么即使第二類服務(wù)請(qǐng)求尚未得到滿足,客戶也將離開第二臺(tái)多服務(wù)器系統(tǒng)。在這種情況下,他們將只為第一類服務(wù)請(qǐng)求付費(fèi)。最后,如果總等待時(shí)間超過了期限,則客戶發(fā)布的任務(wù)成功完成,則客戶將為這兩種服務(wù)請(qǐng)求付費(fèi)。基于式(8)和式(9),多服務(wù)器系統(tǒng)S1和S2中對(duì)服務(wù)請(qǐng)求的預(yù)期費(fèi)用分別為:

(10)

(11)

式中:FW1(D)和FW(D)表示分別可在第一階段和第二階段內(nèi)服務(wù)的服務(wù)請(qǐng)求的百分比。

由于截止時(shí)間的限制,第一種類型的服務(wù)請(qǐng)求只能在前階段提供服務(wù),這將導(dǎo)致到達(dá)后階段的服務(wù)請(qǐng)求到達(dá)率下降。因此,當(dāng)服務(wù)請(qǐng)求進(jìn)入多服務(wù)器系統(tǒng)S1時(shí),到達(dá)率為λ1,但是當(dāng)服務(wù)請(qǐng)求進(jìn)入多服務(wù)器系統(tǒng)S2時(shí),到達(dá)率變?yōu)镕W1(D)λ2,原因是在截止時(shí)間D之前多服務(wù)器系統(tǒng)S1中只能處理百分之FW1(D)的傳入服務(wù)請(qǐng)求,而其余的將不提供服務(wù)而離開。因此,由云服務(wù)供應(yīng)商在多服務(wù)器系統(tǒng)S1和S2中獲得的總收入可表示為:

(12)

(13)

1.4 成本模型

服務(wù)提供商的成本包括兩個(gè)主要部分,即基礎(chǔ)設(shè)施租賃成本和能源消耗的公用事業(yè)成本?；A(chǔ)設(shè)施提供商維護(hù)大量的服務(wù)器以供租賃,云服務(wù)供應(yīng)商根據(jù)要求對(duì)其進(jìn)行租賃并支付相應(yīng)的租賃費(fèi)用。假設(shè)每單位時(shí)間一臺(tái)服務(wù)器的租用價(jià)格為β,則具有mi臺(tái)服務(wù)器系統(tǒng)的服務(wù)器租用價(jià)格為miβ。作為服務(wù)提供商成本的另一部分,能源消耗的公用事業(yè)成本由電價(jià)和能源消耗量組成。本文采用如下動(dòng)態(tài)功率模型[9]:

Pd=NswCLV2f

(14)

式中:Nsw是每個(gè)時(shí)鐘周期的平均柵極開關(guān)因子;CL是負(fù)載電容;V是電源電壓;f是時(shí)鐘頻率。在理想情況下,對(duì)于某個(gè)常數(shù)0<φ≤1,電源電壓V與時(shí)鐘頻率f之間的關(guān)系可以描述為V∝fφ。服務(wù)器的執(zhí)行速度si與時(shí)鐘頻率f呈線性比例,即si∝f,因此動(dòng)態(tài)功率模型可以轉(zhuǎn)化為Pd∝NswCLs(2φ+1)i,為簡(jiǎn)單起見,假設(shè)Pd=bNswCLs(2φ+1)i=ξsαi,其中:ξ=bNswCL;α=2φ+1;b為常數(shù)。本文設(shè)置NswCL=7,b=1.345 6,φ=0.5。由此可得α=2,ξ=9.419 2。

除了動(dòng)態(tài)功耗之外,服務(wù)器空閑時(shí)也會(huì)消耗靜態(tài)功率,假設(shè)能源價(jià)格為每瓦特δ,則多服務(wù)器系統(tǒng)每單位時(shí)間的總成本可描述為:

(15)

1.5 問題描述

云服務(wù)供應(yīng)商從基礎(chǔ)設(shè)施提供商處租用服務(wù)器并支付費(fèi)用,同時(shí),它們根據(jù)需要向客戶提供服務(wù)并獲得收入。從以上分析可以看出,客戶可以忍受的最大等待時(shí)間對(duì)每級(jí)多服務(wù)器系統(tǒng)中云服務(wù)供應(yīng)商的成本模型和收益模型都有影響。因此,對(duì)于由多級(jí)多服務(wù)器隊(duì)列系統(tǒng)組成的云計(jì)算平臺(tái),必須研究一種適當(dāng)?shù)姆椒ㄒ栽诮刂蛊谙藜s束下最大化云服務(wù)供應(yīng)商的總效益。云服務(wù)供應(yīng)商的總效益分別由多服務(wù)器系統(tǒng)S1和S2中獲得的每個(gè)部分組成。在本文中,我們致力于優(yōu)化租賃服務(wù)器的數(shù)量m,并優(yōu)化執(zhí)行速度,從而獲得最佳收益。

G(m1,m2,s1,s2)=G1(m1,s1)+G2(m1,m2,s1,s2)

(16)

注意G1僅由S1本身的特性決定,而G2由S1和S2的特性共同決定,由于在后階段執(zhí)行第二種服務(wù)請(qǐng)求要比在前階段執(zhí)行第一類服務(wù)請(qǐng)求滯后,因此第二臺(tái)多服務(wù)器系統(tǒng)中的參數(shù)與獲得的效益無關(guān),但是由于第二種服務(wù)請(qǐng)求的執(zhí)行受到第一類服務(wù)請(qǐng)求的等待時(shí)間的影響,因此,該點(diǎn)不能正確地相反。在前階段花費(fèi)的等待時(shí)間越多,在后階段花費(fèi)的等待時(shí)間就越少,這將導(dǎo)致第二級(jí)多服務(wù)器系統(tǒng)獲得的效益下降,反之亦然,由此云服務(wù)供應(yīng)商的總效益可以描述如下:

G(m1,m2,s1,s2)=ε1-C1+ε2-C2

(17)

2 求解算法

本節(jié)提出一種啟發(fā)式算法,以找到m1、s1和m2、s2的最佳組合方案。首先,在多服務(wù)器系統(tǒng)S1中分析了效益G1與m1以及s1之間的關(guān)系,并采用梯度下降算法來配置最優(yōu)服務(wù)器參數(shù)以獲得最優(yōu)效益。其次,根據(jù)前階段獲得的服務(wù)器參數(shù),分析了效益G2與m2以及s2之間的關(guān)系,并建立了一個(gè)具有約束的最優(yōu)模型,以同時(shí)最大化G2和FW(D)。

2.1 第一級(jí)服務(wù)器系統(tǒng)效益最大化

2.1.1規(guī)模最優(yōu)

為了在S1中獲得最大效益,首先討論服務(wù)器數(shù)量m1對(duì)G1的影響,G1對(duì)m1的偏導(dǎo)數(shù)為:

(18)

(19)

(20)

由圖1中所繪制的特征關(guān)系圖可以發(fā)現(xiàn)其為減函數(shù),因此可采用二分法來獲得最優(yōu)的m1值。計(jì)算得到不同λ1取值下的m1分別為1.991 1、2.337 5、2.681 8、3.024 7,相應(yīng)的效益G1為27.621、33.312、39.007、44.707。

圖1 效益G1隨m1和λ1變化曲線

可以看出,當(dāng)m1較低時(shí),云服務(wù)供應(yīng)商只能從S1中獲得極低的效益,甚至是負(fù)效益,這是因?yàn)榉?wù)請(qǐng)求的等待時(shí)間非常長,導(dǎo)致在截止時(shí)間D僅有很少的需求被響應(yīng)。隨著服務(wù)器數(shù)量的增長,越來越多的服務(wù)器允許在截止時(shí)間之前滿足越來越多的服務(wù)請(qǐng)求,從而增加了收入和效益。當(dāng)FW1(D)等于1時(shí),收入達(dá)到最大值,但是隨著m1的進(jìn)一步增加,服務(wù)器數(shù)量超過了執(zhí)行服務(wù)請(qǐng)求所需的最大數(shù)量,成本將繼續(xù)增長,導(dǎo)致效益下降。

2.1.2速度最優(yōu)

同樣地,為了獲得速度最優(yōu)的配置方案,令G1對(duì)s1求偏導(dǎo)數(shù):

(21)

(22)

(23)

由圖2可以發(fā)現(xiàn)其特征關(guān)系也為遞減函數(shù),采用標(biāo)準(zhǔn)的二等分法求得不同λ1取值下的最優(yōu)s1分別為0.201 44、0.235 78、0.269 87、0.303 79,相應(yīng)的效益G1為-0.064 63、13.766、27.408和40.862。

圖2 效益G1隨s1和λ1變化曲線

可以看出,當(dāng)s1較低時(shí),云服務(wù)供應(yīng)商只能在S1中獲得極低的效益,甚至是負(fù)效益,這是因?yàn)槊繂挝粫r(shí)間只能滿足很少的服務(wù)請(qǐng)求,而其余的服務(wù)請(qǐng)求則由于過多而偏離了系統(tǒng)。隨著s1的增加,每單位時(shí)間可以滿足越來越多的服務(wù)請(qǐng)求,這將為云服務(wù)供應(yīng)商帶來越來越多的收入和效益。此外,當(dāng)FW1(D)等于1時(shí),收入達(dá)到最大值,但是成本將繼續(xù)增長,隨著s1進(jìn)一步增加,這將導(dǎo)致效益下降。這是因?yàn)榉?wù)器的執(zhí)行速度超過了執(zhí)行服務(wù)請(qǐng)求所需的最大速度。

2.1.3規(guī)模和速度最優(yōu)

根據(jù)前面的分析,可以合理地認(rèn)為m1和s1的影響都可以導(dǎo)致最優(yōu)效益的增量比前面小節(jié)中討論的更高。因此,我們的目標(biāo)是找到m1和s1的最佳組合,以使效益G1最大化。圖3顯示了效益G1的表面作為m1和s1的函數(shù),其中λ1= 5.99。由于曲面是凸面的,我們采用梯度下降算法求出m1和s1,使得式(24)所示的G1(m1,s1)的梯度等于0,從而獲得了最優(yōu)的收益。

圖3 效益G1隨s1和m1變化曲線

請(qǐng)注意,由于使用了梯度下降算法來解決最小化問題,因此在應(yīng)使ProfitG1最大化的同時(shí),我們將G1(m1,s1)乘以-1作為目標(biāo)梯度下降算法的功能。此外,為了加快算法的收斂速度,采用了Arjimo搜索方法來自動(dòng)調(diào)整步長[37]。所得最優(yōu)效益為G1= 55.706 6,其中m1= 7.559和s1=0.936 8。通過對(duì)λ1= 4.99、6.99、7.99的情況進(jìn)行相同的綜合,最優(yōu)效益分別為G1= 46.286 0、63.918 4、75.354 8,其中:m1=5.931 2、5.9784、8.909 8,s1=0.987 6、1.322 3、1.003 8。

2.2 第二級(jí)服務(wù)器系統(tǒng)效益最大化

通過選擇適當(dāng)?shù)膍1和s1,可以在第一級(jí)多服務(wù)器系統(tǒng)中獲得最佳效益G1。在此基礎(chǔ)上,我們進(jìn)一步找尋最優(yōu)的m2和s2,以使第二級(jí)多服務(wù)器系統(tǒng)中的效益G2最大化。

2.2.1規(guī)模最優(yōu)

為了在S2中獲得最大效益,首先討論服務(wù)器數(shù)量m2對(duì)G2的影響。由于G2是m1、m2和s1、s2的函數(shù),在2.1節(jié)中獲得了最優(yōu)m1、s1,進(jìn)一步采用偏導(dǎo)數(shù)來找到最優(yōu)m2:

(25)

(26)

在給定s2和λ1的情況下,效益G2與m1的關(guān)系曲線如圖4所示。采用二分法來獲得最優(yōu)的m1,以使G2最大化,得到m1的最優(yōu)值分別為1.768、2.132、2.426、2.766,相應(yīng)的效益G2分別為27.869 0、33.803 1、39.232 5、44.915 7。

圖4 效益G2隨m1和λ1變化曲線

2.2.2速度最優(yōu)

現(xiàn)在考慮執(zhí)行速度s2對(duì)G2的影響,G2相對(duì)于s2的偏導(dǎo)數(shù)為:

(28)

(29)

在m2和λ1確定下,效益G2隨s2的變化曲線如圖5所示。對(duì)于λ1為 4.99、5.99、6.99,通過二分法得到s2的最優(yōu)值分別為0.361 5、0.439 7、0.489 1、0.557 2,相應(yīng)的效益G2分別為32.835 0、46.081 4、58.071 2、70.286 6。

圖5 效益G2隨s2和λ1變化曲線

2.2.3規(guī)模和速度最優(yōu)

對(duì)于云服務(wù)供應(yīng)商而言,在考慮效益的同時(shí),當(dāng)客戶對(duì)服務(wù)質(zhì)量感到滿意時(shí),他們更有可能向其他客戶推薦云計(jì)算平臺(tái),那么這些潛在客戶將為云服務(wù)供應(yīng)商帶來更多的效益。但是,如果客戶不滿意,他們不太可能向其他客戶推薦云計(jì)算平臺(tái),那么云服務(wù)供應(yīng)商獲得的相應(yīng)效益將會(huì)減少。本文選擇多階段多服務(wù)器隊(duì)列系統(tǒng)中客戶的總等待時(shí)間來衡量客戶滿意度。當(dāng)?shù)却龝r(shí)間超過最后期限D(zhuǎn)時(shí),客戶會(huì)感到不滿意,反之亦然。因此,為了在盡可能增加截止時(shí)間內(nèi)服務(wù)客戶數(shù)量的前提下,最大化總效益,本文所構(gòu)建的云計(jì)算效益模型如下:

minf1(X)=-ε2+C2

f2(X)=1-FW(D)

(31)

式中:X=[m2,s2]。本文中采用NSGA-II來求解這一多目標(biāo)規(guī)劃問題。

所得非支配解作為優(yōu)化問題的帕累托解集,以其中一個(gè)最優(yōu)解為例,f1(X)= -57.1,f2(X)=0.001 97,求得最大收益為57.1,并且在截止時(shí)間D內(nèi)響應(yīng)了99.8%的服務(wù)請(qǐng)求。

2.3 一般的n級(jí)多服務(wù)器隊(duì)列系統(tǒng)

以上內(nèi)容充分討論了具有兩階段多服務(wù)器隊(duì)列系統(tǒng)的效益最大化方案在云計(jì)算平臺(tái)上的應(yīng)用,由此可進(jìn)一步擴(kuò)展到具有n級(jí)多服務(wù)器隊(duì)列系統(tǒng)的一般情況。由上述內(nèi)容,科研發(fā)現(xiàn)每級(jí)服務(wù)器系統(tǒng)的效益僅取決于當(dāng)前系統(tǒng)和之前系統(tǒng)的參數(shù),而不取決于之后系統(tǒng)。因?yàn)闊o論客戶處于什么等待階段,一旦他們的總等待時(shí)間超過了最后期限,即使他們的任務(wù)尚未完全執(zhí)行,他們也會(huì)離開多階段多服務(wù)器隊(duì)列系統(tǒng)。因此,無須為未滿足的服務(wù)請(qǐng)求(子任務(wù))付費(fèi),那么也無須分析在相應(yīng)的多服務(wù)器系統(tǒng)中獲得的效益。

3 結(jié)果分析

根據(jù)第2節(jié)的分析,我們發(fā)現(xiàn)截止時(shí)間內(nèi)服務(wù)請(qǐng)求的百分比不僅受m1、m2和s1、s2的影響,而且還受服務(wù)請(qǐng)求到達(dá)率λ1和截止時(shí)間D的影響。在我們的第一組模擬中,分析了在不同到達(dá)率下,截止時(shí)間內(nèi)服務(wù)請(qǐng)求的百分比和總效益隨截止時(shí)間的增加而變化的情況,相應(yīng)的結(jié)果如圖6和圖7所示。對(duì)于λ1分別為4.99、5.99、6.99、7.99的多級(jí)多服務(wù)器隊(duì)列系統(tǒng),截止時(shí)間內(nèi)服務(wù)的服務(wù)請(qǐng)求百分比和總效益都隨截止時(shí)間而增加。這是因?yàn)殡S著截止時(shí)間的增加,可以滿足更多的服務(wù)請(qǐng)求,這將給云服務(wù)供應(yīng)商帶來更多的收入。此外,隨著λ1的減少,總效益減少,而在固定期限內(nèi),在期限內(nèi)提供服務(wù)的請(qǐng)求百分比增加。當(dāng)服務(wù)請(qǐng)求的到達(dá)率較低時(shí),服務(wù)器在多級(jí)多服務(wù)器隊(duì)列系統(tǒng)中僅承受很少的壓力,因此新的服務(wù)請(qǐng)求將會(huì)在很大程度上有效減少等待時(shí)間以滿足截止期限的約束。

圖6 截止時(shí)間約束下已執(zhí)行服務(wù)請(qǐng)求的完成率

圖7 最佳效益與截止時(shí)間

在第二組模擬中,分析了在不同的期限內(nèi),期限內(nèi)服務(wù)請(qǐng)求的百分比和總效益隨服務(wù)請(qǐng)求到達(dá)率的增加而變化,相應(yīng)的結(jié)果如圖8和圖9所示。對(duì)于D為1、4、7、10的多級(jí)多服務(wù)器隊(duì)列系統(tǒng),總效益增加λ1,而服務(wù)請(qǐng)求的百分比在截止時(shí)間之內(nèi)則朝相反的方向變化。請(qǐng)注意,對(duì)于D為4、7、10,總效益的變化和在截止時(shí)間之前提供的服務(wù)請(qǐng)求的百分比彼此接近。而對(duì)于D為1,這種變化具有顯著差異。這是因?yàn)樵谇耙环N情況下,最后期限足夠長,幾乎不能滿足所有服務(wù)請(qǐng)求;而在后一種情況下,這樣的期限太短,無法滿足足夠的服務(wù)請(qǐng)求。因此,在后一種情況下,在截止時(shí)間之前提供服務(wù)的總效益和服務(wù)請(qǐng)求的百分比都遠(yuǎn)小于在前一種情況下獲得的效益。此外,當(dāng)D為1時(shí),隨著λ1進(jìn)一步增加,總效益反而減少,這是因?yàn)槭杖氲脑黾硬蛔阋詮浹a(bǔ)成本的增加,因此,在這種情況下,應(yīng)該在效益的最大化與在截止時(shí)間之前提供的服務(wù)請(qǐng)求的百分比之間進(jìn)行權(quán)衡。

圖8 已執(zhí)行服務(wù)請(qǐng)求的完成率隨λ1變化特性

圖9 最優(yōu)效益隨λ1變化特性

4 結(jié) 語

本文研究在考慮客戶等待時(shí)長的基礎(chǔ)上,實(shí)現(xiàn)云服務(wù)供應(yīng)商的效益最大化?？紤]到每個(gè)任務(wù)可以通過連續(xù)的執(zhí)行關(guān)系分為多個(gè)子任務(wù),采用多級(jí)多服務(wù)器隊(duì)列系統(tǒng)組成云服務(wù)平臺(tái),每個(gè)系統(tǒng)在每一階段只為唯一類型的服務(wù)請(qǐng)求提供服務(wù)。在此基礎(chǔ)上,由于最大化云服務(wù)供應(yīng)商的效益與最小化由于過多等待時(shí)間而造成的客戶損失之間存在矛盾,本文構(gòu)建了多目標(biāo)優(yōu)化模型并進(jìn)行求解。最后,通過算例仿真分析了本文方法所得最優(yōu)方案的性能,結(jié)果表明,本文方案的動(dòng)態(tài)特性隨著客戶等待期限和服務(wù)請(qǐng)求到達(dá)率的增加而增加。