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

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

0 引言

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

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

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

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

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

1.1 云存儲架構

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

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

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

圖1 帶有免費存儲服務和收費存儲服務的云存儲架構
Fig.1 Architecture of the cloud storage withfree and chargeable storage services

1.2 系統(tǒng)模型

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

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

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

綜上，本文所提出的云存儲架構可以抽象為一個具有不耐煩行為和顧客源有限的雙隊列多服務臺的排隊系統(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(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)或因服務完畢正常離開系統(tǒng))為止所經(jīng)歷的平均時間長度。如果一個潛在用戶在等待過程中沒有因為不耐煩離開系統(tǒng)，則該潛在用戶的存儲服務最終一定成功。排隊等候的潛在用戶平均數(shù)量Lq的表達式為

(5)

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

(6)

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

(7)

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

(8)

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

(9)

3 系統(tǒng)實驗

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Step3利用混沌方程設置每個代理的初始位置：

(μ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分別表示服務器速率為(μ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)成本有關的函數(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，服務器速率下限down=1，服務器速率上限up=9，精度參數(shù)ε=10-6。利用改進的萬有引力尋優(yōu)算法，針對不同收費用戶數(shù)量m分別計算最小系統(tǒng)成本F(μ*1,μ*2)，并給出免費服務器和收費服務器速率的優(yōu)化組合(μ*1,μ*2)。系統(tǒng)優(yōu)化結果如表1所示。

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

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

5 結論

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