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

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

0 引言

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

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

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

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

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

1.1 云存儲架構(gòu)

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

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

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

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

1.2 系統(tǒng)模型

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

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

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

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

2 模型分析和性能指標

2.1 模型分析

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

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

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

(1)

建立平衡方程

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

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

(2)

其中，

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

(3)

建立平衡方程

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

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

(4)

其中，

2.2 性能指標

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

(5)

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

(6)

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

(7)

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

(8)

由Little公式[11]可知，收費用戶平均時延ω2的表達式為

(9)

3 系統(tǒng)實驗

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

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

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

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

固定潛在用戶到達率λ1和不耐煩強度系數(shù)δ，潛在用戶平均時延ω1隨著免費服務(wù)器速率μ1的增加而減少。免費服務(wù)器速率越大，排隊等待的潛在用戶越少，潛在用戶平均時延越少。固定潛在用戶到達率λ1和免費服務(wù)器速率μ1，當(dāng)μ1較小(μ1≤5)時，潛在用戶平均時延ω1隨著不耐煩強度系數(shù)δ的增大而減少。不耐煩強度系數(shù)越大，潛在用戶的不耐煩強度越大，排隊等待的潛在用戶因為不耐煩提前離開的越多，潛在用戶的平均時延越少；當(dāng)μ1較大(μ1>5)時，潛在用戶平均時延ω1隨著不耐煩強度系數(shù)δ的增加保持不變。當(dāng)免費服務(wù)器速率足夠大時，潛在用戶幾乎不用排隊等待就可以接收服務(wù)，所以不耐煩強度系數(shù)對潛在用戶平均時延幾乎沒有影響。固定不耐煩強度系數(shù)δ和免費服務(wù)器速率μ1，當(dāng)μ1較小(μ1≤5)時，潛在用戶平均時延ω1隨著潛在用戶到達率λ1的減小而減少。因為潛在用戶到達率越小，排隊等待的潛在用戶越少，所以潛在用戶平均時延越少。當(dāng)μ1較大(μ1>5)時，潛在用戶平均時延ω1隨著潛在用戶到達率λ1的減小保持不變。當(dāng)免費服務(wù)器速率足夠大時，潛在用戶幾乎不用排隊等待就可以接收服務(wù)，所以潛在用戶到達率對潛在用戶平均時延幾乎沒有影響。

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

圖3 收費用戶平均時延的變化趨勢
Fig.3 The change trend for the average latency of chargeable users

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

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

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

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

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

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

利用數(shù)學(xué)解析的方法聯(lián)合優(yōu)化免費服務(wù)器速率和收費服務(wù)器速率很困難。智能尋優(yōu)算法為解決復(fù)雜的優(yōu)化問題提供了新思路。本文利用混沌方程[11]初始化代理位置，改進萬有引力智能尋優(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è)置每個代理的初始位置：

(μ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)表示生成一個x1×x2矩陣的函數(shù)，矩陣元素為0～1之間的隨機數(shù)%

%r=3.85表示一個混沌因子%。

Step4計算每個代理的系統(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時潛在用戶平均時延、收費用戶平均時延和云提供商的投資規(guī)模%。

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

Step6計算每個代理的重力Hi,i∈{1,2,…，N}：

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

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

Step7計算每個代理的加速度ai，i∈{1,2,…，N}：

Step8計算每個代理的速度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ì)量是一個與系統(tǒng)成本有關(guān)的函數(shù)。因代理質(zhì)量而產(chǎn)生的萬有引力牽引每個代理的位置移動。經(jīng)過多次移動，最終定位到最優(yōu)解的位置(μ1,μ2)*。

令潛在用戶到達率λ1=1，收費用戶到達率λ2=3，潛在用戶不耐煩強度系數(shù)δ=0.1。令優(yōu)化算法中代理個數(shù)N=100，最大迭代次數(shù)Imax=100，服務(wù)器速率下限down=1，服務(wù)器速率上限up=9，精度參數(shù)ε=10-6。利用改進的萬有引力尋優(yōu)算法，針對不同收費用戶數(shù)量m分別計算最小系統(tǒng)成本F(μ*1,μ*2)，并給出免費服務(wù)器和收費服務(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

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