余 靖，賈曉光，郝曉冰，顧 蕊，薛元錚，金順福,*

(1.燕山大學(xué) 信息科學(xué)與工程學(xué)院，河北 秦皇島 066004；2.河北省計(jì)算機(jī)虛擬技術(shù)與系統(tǒng)集成重點(diǎn)實(shí)驗(yàn)室，河北 秦皇島 066004；3.通信網(wǎng)信息傳輸與分發(fā)技術(shù)重點(diǎn)實(shí)驗(yàn)室，河北 石家莊 050081)

0 引言

隨著云計(jì)算的迅猛發(fā)展和大數(shù)據(jù)的快速增加，越來越多的用戶將數(shù)據(jù)存入云中[1-2]。然而，不充足的服務(wù)會增加用戶的時(shí)延，導(dǎo)致用戶對該云存儲服務(wù)不滿意，過剩的服務(wù)又會降低云服務(wù)提供商的盈利[3]。因此，發(fā)展云存儲用戶、合理管理云存儲資源是亟待解決的關(guān)鍵問題。

為了減少用戶的等待時(shí)間，給用戶提供更好的服務(wù)并且獲得更多的經(jīng)濟(jì)效益，通常將用戶進(jìn)行分類服務(wù)。文獻(xiàn)[4]將鐵路貨運(yùn)公司中的用戶分為一般用戶和會員用戶。會員用戶比一般用戶的定價(jià)高，接受的服務(wù)質(zhì)量也更高。文獻(xiàn)[5]研究了一個(gè)帶有兩類顧客的庫存服務(wù)系統(tǒng)。當(dāng)?shù)谝活愵櫩偷竭_(dá)系統(tǒng)時(shí)，如果有第二類正在排隊(duì)等待，系統(tǒng)會優(yōu)先滿足第一類顧客的訂單需求。文獻(xiàn)[6]分析了帶有兩類顧客的重試排隊(duì)，當(dāng)?shù)谝活愵櫩偷竭_(dá)系統(tǒng)時(shí)，如果服務(wù)器被占用，該顧客會徹底離開系統(tǒng)，當(dāng)?shù)诙愵櫩偷竭_(dá)系統(tǒng)時(shí)，如果服務(wù)器被占用，該顧客會離開服務(wù)區(qū)進(jìn)入重試區(qū)，一段時(shí)間后以概率θ再次進(jìn)入系統(tǒng)或者以概率1-θ永久離開系統(tǒng)。受以上文獻(xiàn)啟發(fā)，考慮將云存儲服務(wù)中的用戶分為兩類。

在實(shí)際生活中，經(jīng)常會遇見這種情況，當(dāng)排隊(duì)的隊(duì)伍過長時(shí)，正在排隊(duì)等待的用戶可能會產(chǎn)生不耐煩情緒，從而離開隊(duì)伍放棄服務(wù)。文獻(xiàn)[7]研究了一個(gè)具有不耐煩顧客的單服務(wù)臺排隊(duì)系統(tǒng)。當(dāng)系統(tǒng)遭受到破壞時(shí)，會經(jīng)歷一個(gè)修復(fù)機(jī)制。修復(fù)期間內(nèi)新來的顧客可以進(jìn)入系統(tǒng)，一段時(shí)間內(nèi)如果系統(tǒng)未修復(fù)完成，顧客將離開隊(duì)列永不返回。文獻(xiàn)[8]研究了一個(gè)帶有不耐煩和工作休假的M/M/1排隊(duì)系統(tǒng)。當(dāng)系統(tǒng)中沒有顧客時(shí)，服務(wù)器進(jìn)入工作休假模式。在工作休假模式下有新顧客到達(dá)時(shí)，工作休假被中斷，服務(wù)器以概率q恢復(fù)正常工作，以概率1-q繼續(xù)休假。在休假周期內(nèi)，排隊(duì)等待的顧客可能因不耐煩離開系統(tǒng)。文獻(xiàn)[9]研究了一個(gè)帶有不耐煩的M/M/2排隊(duì)系統(tǒng)。當(dāng)顧客到達(dá)系統(tǒng)時(shí)，如果兩個(gè)服務(wù)器全被占用，顧客以概率p排隊(duì)等待，以概率1-p直接離開系統(tǒng)。如果顧客的等待T時(shí)間后未開始服務(wù)，顧客將放棄等待離開系統(tǒng)。許多學(xué)者研究了帶有不耐煩行為的排隊(duì)系統(tǒng)，但是用戶的不耐煩行為在云存儲中的研究卻很少。

在云存儲中考慮同時(shí)設(shè)立多個(gè)免費(fèi)服務(wù)器和多個(gè)收費(fèi)服務(wù)器，給出一種新型的云存儲架構(gòu)。潛在用戶由免費(fèi)服務(wù)器提供存儲服務(wù)。潛在用戶在排隊(duì)過程中因?yàn)榈却龝r(shí)間過長而感到不耐煩時(shí)會放棄服務(wù)離開系統(tǒng)，堅(jiān)持等待的潛在用戶結(jié)束服務(wù)后直接離開系統(tǒng)。收費(fèi)用戶由效率更高的服務(wù)器提供存儲服務(wù)。收費(fèi)用戶源有限并且收費(fèi)用戶一旦進(jìn)入系統(tǒng)就不能離開，直到服務(wù)結(jié)束才能離開系統(tǒng)。建立一種雙隊(duì)列多服務(wù)臺排隊(duì)模型，導(dǎo)出潛在用戶和收費(fèi)用戶的平均時(shí)延的性能表達(dá)式。進(jìn)行數(shù)值實(shí)驗(yàn)和仿真實(shí)驗(yàn)，揭示系統(tǒng)性能的變化趨勢。將混沌方程用于代理的初始化中，改進(jìn)萬有引力尋優(yōu)算法，以系統(tǒng)成本為目標(biāo)函數(shù)，進(jìn)行免費(fèi)和收費(fèi)服務(wù)器速率的聯(lián)合優(yōu)化。

1 云存儲架構(gòu)及系統(tǒng)模型

1.1 云存儲架構(gòu)

隨著云計(jì)算的快速發(fā)展和大數(shù)據(jù)的快速增加，越來越多的用戶將數(shù)據(jù)存入云中，云提供商開始以提供云存儲服務(wù)盈利。為了吸引更多的用戶以獲得更大的經(jīng)濟(jì)效益，云提供商設(shè)立兩種速率不同的服務(wù)器為不同用戶提供服務(wù)。潛在用戶到達(dá)系統(tǒng)時(shí)，由速率較小的免費(fèi)服務(wù)器提供存儲服務(wù)。當(dāng)潛在用戶因等待時(shí)間過長而不耐煩時(shí)，將離開系統(tǒng)。收費(fèi)用戶由速率較大的收費(fèi)服務(wù)器提供存儲服務(wù)。由此，給出一個(gè)由免費(fèi)存儲服務(wù)和收費(fèi)存儲服務(wù)共同組成的云存儲架構(gòu)，如圖1所示。

1) 當(dāng)潛在用戶到達(dá)系統(tǒng)時(shí)，如果存在至少一個(gè)空閑的免費(fèi)服務(wù)器，則直接接受服務(wù)，否則該潛在用戶在免費(fèi)服務(wù)排隊(duì)區(qū)域中等待。排隊(duì)過程中感到不耐煩的潛在用戶會停止等待提前離開系統(tǒng)。

2) 當(dāng)收費(fèi)用戶到達(dá)系統(tǒng)時(shí)，如果存在至少一個(gè)空閑的收費(fèi)服務(wù)器，則該收費(fèi)用戶直接接受服務(wù)，否則該收費(fèi)用戶在收費(fèi)服務(wù)排隊(duì)區(qū)域中等待。所有收費(fèi)用戶結(jié)束收費(fèi)服務(wù)才會離開系統(tǒng)。

圖1 帶有免費(fèi)存儲服務(wù)和收費(fèi)存儲服務(wù)的云存儲架構(gòu)
Fig.1 Architecture of the cloud storage withfree and chargeable storage services

1.2 系統(tǒng)模型

基于融合免費(fèi)存儲服務(wù)和收費(fèi)存儲服務(wù)的云存儲架構(gòu)，考慮潛在用戶的不耐煩行為和收費(fèi)用戶源有限，建立雙隊(duì)列多服務(wù)臺排隊(duì)模型。

假設(shè)免費(fèi)存儲云中有n(n=1,2,…)個(gè)免費(fèi)服務(wù)器。令潛在用戶到達(dá)免費(fèi)存儲云的時(shí)間間隔服從參數(shù)為λ1(λ1>0)的指數(shù)分布，一個(gè)潛在用戶在免費(fèi)服務(wù)器上的服務(wù)時(shí)間服從參數(shù)為μ1(μ1>0)的指數(shù)分布。潛在用戶不耐煩強(qiáng)度為αk=kδ(δ>0)，其中k為排隊(duì)隊(duì)長，此時(shí)，系統(tǒng)中共有(k+n)個(gè)潛在用戶。假設(shè)免費(fèi)存儲云的排隊(duì)區(qū)域的大小無限。免費(fèi)存儲云可以抽象為一個(gè)具有不耐煩行為的M/M/n排隊(duì)系統(tǒng)。

假設(shè)收費(fèi)存儲云中有c(c=1,2,…)個(gè)收費(fèi)服務(wù)器，收費(fèi)用戶的總數(shù)為m(m≥c)。令收費(fèi)用戶發(fā)起存儲請求的時(shí)間間隔服從參數(shù)為λ2(λ2>0)的指數(shù)分布，一個(gè)收費(fèi)用戶在收費(fèi)服務(wù)器上的服務(wù)時(shí)間服從參數(shù)為μ2(μ2>μ1)的指數(shù)分布。收費(fèi)存儲云可以抽象為一個(gè)M/M/c/m/m排隊(duì)系統(tǒng)。

綜上，本文所提出的云存儲架構(gòu)可以抽象為一個(gè)具有不耐煩行為和顧客源有限的雙隊(duì)列多服務(wù)臺的排隊(duì)系統(tǒng)。

2 模型分析和性能指標(biāo)

2.1 模型分析

令ρ1和ρ2分別表示系統(tǒng)中具有不耐煩行為的M/M/n排隊(duì)系統(tǒng)和M/M/c/m/m排隊(duì)系統(tǒng)的通信量負(fù)載[10]。ρ1和ρ2的表達(dá)式分別為

系統(tǒng)穩(wěn)態(tài)的充分必要條件是ρ1<1并且ρ2<1。

令A(yù)(t)表示在t時(shí)刻免費(fèi)存儲云中潛在用戶的個(gè)數(shù)。具有不耐煩行為的M/M/n排隊(duì)系統(tǒng)的穩(wěn)態(tài)概率分布π1i表示為

(1)

建立平衡方程

聯(lián)合歸一化條件

可得到具有不耐煩行為的M/M/n排隊(duì)系統(tǒng)的穩(wěn)態(tài)概率分布為

(2)

其中，

令B(t)表示在t時(shí)刻收費(fèi)存儲云中收費(fèi)用戶的個(gè)數(shù)。M/M/c/m/m排隊(duì)系統(tǒng)的穩(wěn)態(tài)概率分布π2i表示為

(3)

建立平衡方程

聯(lián)合歸一化條件

可得M/M/c/m/m排隊(duì)系統(tǒng)的穩(wěn)態(tài)概率分布為

(4)

其中，

2.2 性能指標(biāo)

定義潛在用戶平均時(shí)延ω1為潛在用戶從到達(dá)免費(fèi)存儲云開始到離開系統(tǒng)(因不耐煩提前離開系統(tǒng)或因服務(wù)完畢正常離開系統(tǒng))為止所經(jīng)歷的平均時(shí)間長度。如果一個(gè)潛在用戶在等待過程中沒有因?yàn)椴荒蜔╇x開系統(tǒng)，則該潛在用戶的存儲服務(wù)最終一定成功。排隊(duì)等候的潛在用戶平均數(shù)量Lq的表達(dá)式為

(5)

正在接受云存儲服務(wù)的潛在用戶平均數(shù)量Ls的表達(dá)式為

(6)

由Little公式[11]可知，潛在用戶平均時(shí)延ω1的表達(dá)式為

(7)

定義收費(fèi)用戶平均時(shí)延ω2為收費(fèi)用戶從到達(dá)收費(fèi)存儲云開始到完成服務(wù)離開系統(tǒng)止所經(jīng)歷的平均時(shí)間長度。穩(wěn)態(tài)下系統(tǒng)中收費(fèi)用戶數(shù)量的均值L2的表達(dá)式為

(8)

由Little公式[11]可知，收費(fèi)用戶平均時(shí)延ω2的表達(dá)式為

(9)

3 系統(tǒng)實(shí)驗(yàn)

為了揭示不同系統(tǒng)參數(shù)，包括潛在用戶到達(dá)率λ1、免費(fèi)服務(wù)器速率μ1、不耐煩強(qiáng)度系數(shù)δ、收費(fèi)用戶到達(dá)率λ2、收費(fèi)服務(wù)器速率μ2及收費(fèi)用戶數(shù)量m等對云存儲系統(tǒng)的性能影響，進(jìn)行數(shù)值實(shí)驗(yàn)和仿真實(shí)驗(yàn)。

在MyEclipse平臺上基于云存儲架構(gòu)進(jìn)行仿真實(shí)驗(yàn)，在MATLAB R2010a上基于式(7)和(9)進(jìn)行數(shù)值實(shí)驗(yàn)。計(jì)算機(jī)操作系統(tǒng)為Windows 10，處理器為Intel Core i7-4790 3.60 GHz，內(nèi)存為8 GB。從圖2和圖3中可以看出理論分析結(jié)果和仿真結(jié)果吻合。

以免費(fèi)服務(wù)器數(shù)量n=6為例，圖2揭示了潛在用戶到達(dá)率λ1，免費(fèi)服務(wù)器速率μ1及不耐煩強(qiáng)度系數(shù)δ等系統(tǒng)參數(shù)對潛在用戶平均時(shí)延ω1的影響。

圖2 潛在用戶平均時(shí)延的變化趨勢
Fig.2 The change trend for the average latency of potential users

固定潛在用戶到達(dá)率λ1和不耐煩強(qiáng)度系數(shù)δ，潛在用戶平均時(shí)延ω1隨著免費(fèi)服務(wù)器速率μ1的增加而減少。免費(fèi)服務(wù)器速率越大，排隊(duì)等待的潛在用戶越少，潛在用戶平均時(shí)延越少。固定潛在用戶到達(dá)率λ1和免費(fèi)服務(wù)器速率μ1，當(dāng)μ1較小(μ1≤5)時(shí)，潛在用戶平均時(shí)延ω1隨著不耐煩強(qiáng)度系數(shù)δ的增大而減少。不耐煩強(qiáng)度系數(shù)越大，潛在用戶的不耐煩強(qiáng)度越大，排隊(duì)等待的潛在用戶因?yàn)椴荒蜔┨崆半x開的越多，潛在用戶的平均時(shí)延越少；當(dāng)μ1較大(μ1>5)時(shí)，潛在用戶平均時(shí)延ω1隨著不耐煩強(qiáng)度系數(shù)δ的增加保持不變。當(dāng)免費(fèi)服務(wù)器速率足夠大時(shí)，潛在用戶幾乎不用排隊(duì)等待就可以接收服務(wù)，所以不耐煩強(qiáng)度系數(shù)對潛在用戶平均時(shí)延幾乎沒有影響。固定不耐煩強(qiáng)度系數(shù)δ和免費(fèi)服務(wù)器速率μ1，當(dāng)μ1較小(μ1≤5)時(shí)，潛在用戶平均時(shí)延ω1隨著潛在用戶到達(dá)率λ1的減小而減少。因?yàn)闈撛谟脩舻竭_(dá)率越小，排隊(duì)等待的潛在用戶越少，所以潛在用戶平均時(shí)延越少。當(dāng)μ1較大(μ1>5)時(shí)，潛在用戶平均時(shí)延ω1隨著潛在用戶到達(dá)率λ1的減小保持不變。當(dāng)免費(fèi)服務(wù)器速率足夠大時(shí)，潛在用戶幾乎不用排隊(duì)等待就可以接收服務(wù)，所以潛在用戶到達(dá)率對潛在用戶平均時(shí)延幾乎沒有影響。

以收費(fèi)服務(wù)器數(shù)量c=4為例，圖3刻畫了收費(fèi)用戶到達(dá)率λ2，收費(fèi)服務(wù)器速率μ2及收費(fèi)用戶數(shù)量m等系統(tǒng)參數(shù)對收費(fèi)用戶平均時(shí)延ω2的影響。

圖3 收費(fèi)用戶平均時(shí)延的變化趨勢
Fig.3 The change trend for the average latency of chargeable users

固定收費(fèi)用戶到達(dá)率λ2和收費(fèi)用戶數(shù)量m，收費(fèi)用戶平均時(shí)延ω2隨著收費(fèi)服務(wù)器速率μ2的增加而減少。收費(fèi)服務(wù)器速率越大，排隊(duì)等待的收費(fèi)用戶越少，收費(fèi)用戶平均時(shí)延越小。固定收費(fèi)服務(wù)器速率μ2和收費(fèi)用戶數(shù)量m，收費(fèi)用戶平均時(shí)延ω2隨著收費(fèi)用戶到達(dá)率λ2的增加而增加。收費(fèi)用戶到達(dá)率越大，排隊(duì)等待的收費(fèi)用戶越多，收費(fèi)用戶平均時(shí)延越多。固定收費(fèi)用戶到達(dá)率λ2和收費(fèi)服務(wù)器速率μ2，收費(fèi)用戶平均時(shí)延ω2隨著收費(fèi)用戶數(shù)量m的增加而增加。系統(tǒng)中收費(fèi)用戶基數(shù)越大，意味著進(jìn)行存儲服務(wù)的收費(fèi)用戶增加，造成排隊(duì)等待的收費(fèi)用戶增加，收費(fèi)用戶的平均時(shí)延因此變大。

4 系統(tǒng)優(yōu)化

一般來講，服務(wù)器的購置費(fèi)用越高，服務(wù)器的服務(wù)能力越強(qiáng)。本文關(guān)注服務(wù)能力中的存儲速率。假設(shè)β1和β2分別表示用于免費(fèi)服務(wù)器和收費(fèi)服務(wù)器的投入與服務(wù)速率相關(guān)的系數(shù)，云提供商的投資規(guī)模近似表示為

當(dāng)云提供商的投資規(guī)模Z固定時(shí)，增大免費(fèi)服務(wù)器速率M1，就要降低收費(fèi)服務(wù)器速率M2，反之亦然。另一方面，服務(wù)器速率M1和M2越大，潛在用戶和收費(fèi)用戶的平均時(shí)延ω1和ω2越小，用戶對云存儲的QoS (Quality of Service)越滿意。但是，服務(wù)器速率M1和M2的增加勢必會使云提供商的投資規(guī)模Z加大，這是云提供商不愿意的。顯然，不同用戶的平均時(shí)延之間、用戶時(shí)延與云提供商的投資規(guī)模之間存在折中關(guān)系。

為了合理配置服務(wù)器速率，均衡潛在用戶、收費(fèi)用戶和云提供商三者之間的利益，建立系統(tǒng)的成本函數(shù)：

其中，f1、f2和f3分別為潛在用戶平均時(shí)延、收費(fèi)用戶平均時(shí)延和云提供商的投資規(guī)模對系統(tǒng)成本的影響因子。

利用數(shù)學(xué)解析的方法聯(lián)合優(yōu)化免費(fèi)服務(wù)器速率和收費(fèi)服務(wù)器速率很困難。智能尋優(yōu)算法為解決復(fù)雜的優(yōu)化問題提供了新思路。本文利用混沌方程[11]初始化代理位置，改進(jìn)萬有引力智能尋優(yōu)算法[12]，旨在加快優(yōu)化過程。該算法的主要步驟如下。

Step1初始化代理數(shù)量N，最大迭代次數(shù)Imax，當(dāng)前迭代次數(shù)I=1，服務(wù)器速率上限up，服務(wù)器速率下限down。

Step2初始化代理速度V(μ1,μ2)i,i∈{1,2,…，N}:

V(μ1,μ2)i=0。

Step3利用混沌方程設(shè)置每個(gè)代理的初始位置：

(μ1,μ2)1=rand(2，1)，

fori=2∶2N

(μ1,μ2)i=r×(μ1,μ2)i-1×(1-(μ1,μ2)i-1)

end

fori=1∶2N

(μ1,μ2)i=(μ1,μ2)i×(up-down)+dowm

end

%rand(x1,x2)表示生成一個(gè)x1×x2矩陣的函數(shù)，矩陣元素為0～1之間的隨機(jī)數(shù)%

%r=3.85表示一個(gè)混沌因子%。

Step4計(jì)算每個(gè)代理的系統(tǒng)成本F(μ1,μ2)i,i∈{1,2,…，N}：

F(μ1,μ2)i=f1×ω1(μ1,μ2)i+f2×ω2(μ1,μ2)i+f3×Z(μ1,μ2)i

%ω1(μ1,μ2)i、ω2(μ1,μ2)i和Z(μ1,μ2)i分別表示服務(wù)器速率為(μ1,μ2)i時(shí)潛在用戶平均時(shí)延、收費(fèi)用戶平均時(shí)延和云提供商的投資規(guī)模%。

Step5計(jì)算每個(gè)代理的慣性質(zhì)量Mi,i∈{1,2,…，N}：

Step6計(jì)算每個(gè)代理的重力Hi,i∈{1,2,…，N}：

%G表示萬有引力常數(shù)%

%rand表示一個(gè)0～1之間的隨機(jī)數(shù)%。

Step7計(jì)算每個(gè)代理的加速度ai，i∈{1,2,…，N}：

Step8計(jì)算每個(gè)代理的速度V(μ1,μ2)i并且更新其位置(μ1,μ2)i,i∈{1,2,…，N}：

V(μ1,μ2)i=rand(2,N)×V(μ1,μ2)i-1+αi，
(μ1,μ2)i=(μ1,μ2)i+V(μ1,μ2)i。

Step10輸出(μ1,μ2)*和F(μ1,μ2)*。

在該智能算法中，代理的質(zhì)量是一個(gè)與系統(tǒng)成本有關(guān)的函數(shù)。因代理質(zhì)量而產(chǎn)生的萬有引力牽引每個(gè)代理的位置移動。經(jīng)過多次移動，最終定位到最優(yōu)解的位置(μ1,μ2)*。

令潛在用戶到達(dá)率λ1=1，收費(fèi)用戶到達(dá)率λ2=3，潛在用戶不耐煩強(qiáng)度系數(shù)δ=0.1。令優(yōu)化算法中代理個(gè)數(shù)N=100，最大迭代次數(shù)Imax=100，服務(wù)器速率下限down=1，服務(wù)器速率上限up=9，精度參數(shù)ε=10-6。利用改進(jìn)的萬有引力尋優(yōu)算法，針對不同收費(fèi)用戶數(shù)量m分別計(jì)算最小系統(tǒng)成本F(μ*1,μ*2)，并給出免費(fèi)服務(wù)器和收費(fèi)服務(wù)器速率的優(yōu)化組合(μ*1,μ*2)。系統(tǒng)優(yōu)化結(jié)果如表1所示。

表1 系統(tǒng)優(yōu)化數(shù)值結(jié)果
Tab.1 Numerical results for the system optimization

收費(fèi)用戶數(shù)量免費(fèi)服務(wù)器和收費(fèi)服務(wù)器速率的最優(yōu)組合最小系統(tǒng)成本60(5.3267,6.3369)0.338070(5.3691,6.9649)0.357680(5.5005,7.0257)0.3758

5 結(jié)論

提高用戶QoS并減小云提供商投資規(guī)模，合理分配云存儲資源是云存儲應(yīng)用中的一個(gè)不容忽視的問題。本文融合免費(fèi)服務(wù)和收費(fèi)服務(wù)提出了一種新型云存儲架構(gòu)?？紤]潛在用戶的不耐煩行為和收費(fèi)用戶源有限，建立了一個(gè)雙隊(duì)列多服務(wù)臺排隊(duì)系統(tǒng)，給出了潛在用戶平均時(shí)延和收費(fèi)用戶平均時(shí)延等性能指標(biāo)。進(jìn)行數(shù)值實(shí)驗(yàn)和仿真實(shí)驗(yàn)，揭示了不同用戶的平均時(shí)延、用戶時(shí)延和云提供商投資規(guī)模之間的折中關(guān)系。建立系統(tǒng)成本函數(shù)，改進(jìn)萬有引力尋優(yōu)算法，給出了免費(fèi)服務(wù)器速率和收費(fèi)服務(wù)器速率的聯(lián)合優(yōu)化方案。