王娟，李飛，張路橋

（成都信息工程學(xué)院 信息安全工程學(xué)院，四川 成都 610225）

1 引言

近年來，隨著云計算[1,2]技術(shù)和軟件即服務(wù)(SaaS)[3]思想的興起，云存儲成為信息存儲領(lǐng)域的一個研究熱點。云存儲系統(tǒng)的任務(wù)調(diào)度前期的研究多脫胎于數(shù)據(jù)網(wǎng)格和云計算領(lǐng)域。這些工作[4～8]的主要目的是選擇哪些響應(yīng)時間最短的副本。但是云系統(tǒng)與傳統(tǒng)網(wǎng)格最大的不同在于“一切都是服務(wù)”，更加關(guān)注服務(wù)質(zhì)量（QoS, quality of service）。既然一切都是服務(wù)，那么用戶的感受無疑是最重要的。因此，近年來的云存儲任務(wù)調(diào)度的研究熱點在于滿足系統(tǒng)QoS的要求。但是，很遺憾現(xiàn)有算法提供的QoS普遍存在2個致命缺點。

1) QoS大多是針對系統(tǒng)而言，而不是使用它的用戶。這與“以服務(wù)為中心”的宗旨相違背。如果用戶的需求得不到滿足，即便使得整個系統(tǒng)擁有最大的吞吐率，也應(yīng)該是失敗的，因為結(jié)果不被用戶認(rèn)可，系統(tǒng)的價值得不到實現(xiàn)。

2) 針對用戶提供的 QoS幾乎都是統(tǒng)一的，沒有意識到用戶的需求存在差異。這也很不符合實際情況。用戶天然存在需求的差別，提供統(tǒng)一的QoS服務(wù)不但不能滿足所有用戶的要求，而且造成了不必要的浪費(fèi)。

舉個很簡單的例子：某云存儲系統(tǒng)提供用戶各種各樣的數(shù)據(jù)。系統(tǒng)采用的調(diào)度算法以使整個系統(tǒng)的吞吐量最大為目標(biāo)，從系統(tǒng)角度看這是無可厚非的。但是用戶的QoS要求是有差異的：其中一些用戶不希望多花錢，為此寧愿降低自己的優(yōu)先級多等待一些時間；而另一些用戶，寧愿多花錢來獲得最短的響應(yīng)時間。系統(tǒng)如果不能提供滿足用戶偏好（時間或代價）的任務(wù)調(diào)度方案，先滿足了愿意等待的用戶而延遲了不愿意等待用戶的要求，顯然會造成2種用戶都不滿意。前者認(rèn)為自己多付了錢（快的響應(yīng)往往代表高的花費(fèi)），后者則覺得浪費(fèi)了自己的時間。盡管整個系統(tǒng)的吞吐率最高，資源利用率和負(fù)載均衡率都較好，但是明顯不符合現(xiàn)實情況的需要。

在云計算領(lǐng)域已有少量對QoS偏好性的探討，例如文獻(xiàn)[9]。但是，云計算和云存儲系統(tǒng)存在很大的區(qū)別，這些方法都不適合直接應(yīng)用于云存儲系統(tǒng)，需要做較大修改。云存儲系統(tǒng)與云計算的不同主要表現(xiàn)在以下兩方面。

1) 云計算的任務(wù)是計算型任務(wù)，任務(wù)可以指派到系統(tǒng)的任意節(jié)點執(zhí)行，區(qū)別僅僅在于在高效率（CPU性能高）節(jié)點上執(zhí)行時間短，而在低效率節(jié)點上執(zhí)行時間長，不會有任務(wù)不能由某個節(jié)點執(zhí)行的情況。但是云存儲的任務(wù)大多是數(shù)據(jù)傳輸任務(wù)，首要的前提就是節(jié)點有任務(wù)所需要的數(shù)據(jù)，因此某任務(wù)不能由某個節(jié)點提供數(shù)據(jù)的情況大量存在，這點導(dǎo)致很多從云計算領(lǐng)域移植的算法生成的結(jié)果對云存儲系統(tǒng)是無效的。

2) 云計算領(lǐng)域的任務(wù)之間存在先后關(guān)系，即某些任務(wù)必須等到另一些的結(jié)果后才能執(zhí)行。而云存儲系統(tǒng)的任務(wù)一般不存在這種先后關(guān)系，數(shù)據(jù)傳輸不存在必須先傳哪部分后傳哪部分。這樣使得原有云計算領(lǐng)域中的調(diào)度算法可以適當(dāng)簡化，不必考慮任務(wù)的先后關(guān)系。

以上兩點不同提醒大家，現(xiàn)有從傳統(tǒng)云計算領(lǐng)域移植的算法應(yīng)該考慮這兩大不同，做出改進(jìn)以適應(yīng)云存儲環(huán)境的特點。例如：云計算中占據(jù)重要地位的CPU的計算能力等參數(shù)將不再起主導(dǎo)作用，而帶寬、網(wǎng)絡(luò)延遲等性能成為任務(wù)調(diào)度的重要參考。

由于任務(wù)調(diào)度是一個NP問題，因而以粒子群優(yōu)化(PSO, partical swarm optimization)算法為代表的啟發(fā)式算法近年來在云任務(wù)調(diào)度領(lǐng)域受到關(guān)注，取得了不錯的系統(tǒng)吞吐率。本文就利用PSO算法解決帶偏好的云存儲任務(wù)調(diào)度問題進(jìn)行研究，對PSO怎樣解決偏好不同、解決的效果和原因進(jìn)行實驗和分析。

2 云存儲系統(tǒng)任務(wù)調(diào)度抽象

為了描述方便，先對云存儲中的任務(wù)調(diào)度進(jìn)行抽象。

1) 用R={r1,r2,…,ri, …,rm}表示m個資源，其中，ri表示第i個資源，i∈1,2,…,m。

2) 用J={j1,j2, …,ji, …,jn}表示n個任務(wù)，其中，ji表示第i個任務(wù)，i∈1,2,…,n。

云存儲系統(tǒng)任務(wù)調(diào)度的目標(biāo)就是在適應(yīng)度函數(shù)的指引下找到最符合目標(biāo)函數(shù)的調(diào)度方案。這里的適應(yīng)度函數(shù)可以簡單指任務(wù)完成時間，也可以是使用資源的代價、可靠性等。而目標(biāo)函數(shù)則只有 2種：一種是取適應(yīng)度函數(shù)的最大值，另一種是取適應(yīng)度函數(shù)的最小值。很多情況下，通過改變適應(yīng)度函數(shù)的定義，目標(biāo)函數(shù)可以相互轉(zhuǎn)換。例如：取任務(wù)完成時間為適應(yīng)度函數(shù)，一般的目標(biāo)函數(shù)就是取完成時間的最小值。這個定義等同于取任務(wù)完成時間的倒數(shù)為適應(yīng)度函數(shù)，而目標(biāo)函數(shù)取該倒數(shù)的最小值。因此，本文不設(shè)專門的目標(biāo)函數(shù)，只使用適應(yīng)度函數(shù)F，目標(biāo)就是取使得F最小的調(diào)度方案。

已有的研究已經(jīng)證明多因素下的任務(wù)調(diào)度是一個NP難題，沒有最優(yōu)解，只能通過啟發(fā)式算法尋找比較優(yōu)化的解[10]。當(dāng)前常用的啟發(fā)式算法中，粒子群優(yōu)化算法以其算法簡單、計算方便、求解速度快受到任務(wù)調(diào)度研究者的重視[11]。下面研究如何改進(jìn)PSO算法以感知用戶偏好差異。

3 適應(yīng)用戶QoS偏好的PSO云存儲任務(wù)調(diào)度

本節(jié)先介紹 PSO算法及其應(yīng)用到云存儲系統(tǒng)中的編碼方式，進(jìn)而從解空間、適應(yīng)度等方面對現(xiàn)有云計算中的PSO調(diào)度算法進(jìn)行改進(jìn)，首先保證不產(chǎn)生對云存儲系統(tǒng)來說無意義的解；其次，修改適應(yīng)度函數(shù)定義來感知用戶偏好。

3.1 標(biāo)準(zhǔn)粒子群算法簡介

PSO[12]是一種基于種群搜索策略的自適應(yīng)隨機(jī)優(yōu)化算法。在基本粒子群算法中，生物的個體被抽象為沒有質(zhì)量和體積的粒子，生物群體被抽象為由e個粒子組成的群體。粒子i代表優(yōu)化問題在D維搜索空間中可能的解，表示為位置矢量Xi= (x1,x2,…,xN)，位置可以通過飛行速度矢量更新Vi= (v1,v2,…,vN)。每個粒子都有一個由目標(biāo)函數(shù)決定的適應(yīng)值(fitness value)，并且知道自己到目前為止發(fā)現(xiàn)的最好位置(pbest)和現(xiàn)在的位置Xi。這個可以看作是粒子自己的飛行經(jīng)驗。除此之外，每個粒子還知道到目前為止整個群體中所有粒子發(fā)現(xiàn)的最好位置(gbest)(gbest是pbest中的最好值)。這個可以看作是粒子同伴的經(jīng)驗。粒子就是通過自己的經(jīng)驗和同伴中最好的經(jīng)驗來決定下一步的運(yùn)動。

PSO的初始化為一群隨機(jī)粒子(隨機(jī)解)。然后通過迭代找到最優(yōu)解。在每一次的迭代中，粒子通過跟蹤2個“極值”(pbest,gbest)來更新自己。在找到這2個最優(yōu)值后，粒子通過下面的公式來更新自己的速度和位置。

在式(1)和式(2)中，i=1,2,…,m,m是該群體中粒子的總數(shù)，Vi是粒子的速度；pbest和gbest如前定義；rand()是介于（0，1）之間的隨機(jī)數(shù)；Xi是粒子的當(dāng)前位置。c1和c2是學(xué)習(xí)因子，通常取c1=c2=2。在每一維，粒子都有一個最大限制速度Vmax，如果某一維的速度超過設(shè)定的Vmax，那么這一維的速度就被限定為Vmax(Vmax＞0)。

1998年Shi等[13]對前面的式(2)進(jìn)行了修正。引入慣性權(quán)重因子，如式(3)所示。

其中，w為非負(fù)，稱為慣性因子。式(3)和式(4)被視為標(biāo)準(zhǔn)PSO算法。w值較大，全局尋優(yōu)能力強(qiáng)，局部尋優(yōu)能力弱；w值較小，反之w值較大。

3.2 編碼策略

很顯然以上算法適合求解實數(shù)問題，但對離散化的任務(wù)調(diào)度不能直接應(yīng)用。需要進(jìn)行轉(zhuǎn)化，一般方法是進(jìn)行編碼。對云存儲系統(tǒng)來說，一個編碼就代表一個任務(wù)調(diào)度序列。出于描述方便采用十進(jìn)制編碼，假設(shè)有m個資源，n個任務(wù)，用Code=e1e2…ei…en表示任務(wù)調(diào)度向量，即一個調(diào)度方案。對云存儲系統(tǒng)來說，ei代表第i個任務(wù)的數(shù)據(jù)由ei的值代表的資源節(jié)點提供，而該向量的長度即是單位時間內(nèi)要調(diào)度任務(wù)的總量n。例如，某任務(wù)調(diào)度向量為[2, 4, 3, 4, 1, 5, 6]，這個向量的長度是7，代表該單位時間需要調(diào)度的任務(wù)數(shù)為7。序號1的位置上的值是2，代表任務(wù)1的數(shù)據(jù)由系統(tǒng)的2號節(jié)點提供。以此類推，任務(wù)2和4的數(shù)據(jù)由節(jié)點4提供；任務(wù)3的數(shù)據(jù)由節(jié)點3提供；任務(wù)5的數(shù)據(jù)由節(jié)點1提供；任務(wù)6的數(shù)據(jù)由節(jié)點5提供；任務(wù)7的數(shù)據(jù)由節(jié)點6提供。

3.3 限制解空間

傳統(tǒng)云計算領(lǐng)域的PSO算法，初始解和解的更新都是整個解空間，即云計算任務(wù)可以調(diào)度到任何一個節(jié)點計算。但是如引言中所述，在云存儲系統(tǒng)中，由于任務(wù)資源只在特定節(jié)點存儲，因此任務(wù)不能被調(diào)度到任意節(jié)點執(zhí)行，即云存儲中的解必然是受限制的。

針對這個問題，引入存在矩陣(EM, exist matrix)[14]來指示任務(wù)和資源節(jié)點間的對應(yīng)關(guān)系。EM是一個n×m的矩陣，n是調(diào)度任務(wù)數(shù)目，m是系統(tǒng)資源節(jié)點數(shù)目。矩陣的項eij代表節(jié)點j是否有i任務(wù)的數(shù)據(jù)，有則為1，無則為0。該矩陣可以從云存儲系統(tǒng)的資源列表中生成。資源列表記錄了數(shù)據(jù)塊 ID和存放的資源節(jié)點的對應(yīng)關(guān)系，為了保證數(shù)據(jù)的安全，數(shù)據(jù)塊往往被冗余存儲在多個資源節(jié)點上，因此，存在矩陣中代表任務(wù)的一行中會存在多個1的情況，對應(yīng)的列數(shù)就是該擁有任務(wù)數(shù)據(jù)的節(jié)點ID。

在存在矩陣的限制下，對傳統(tǒng)云計算中基于PSO的任務(wù)調(diào)度算法做以下3點改進(jìn)。

1) PSO的初始化解不再隨機(jī)產(chǎn)生，而是根據(jù)存在矩陣生成；生成算法簡單來說是先從EM中獲取每行值為1的序號，然后從這些序號中隨機(jī)選擇一個作為該行代表任務(wù)的解，n個任務(wù)的解構(gòu)成一個任務(wù)調(diào)度解V。

2) 在根據(jù)式(3)和式(4)產(chǎn)生新的解時，先不進(jìn)行適應(yīng)度的計算和比較，先進(jìn)行存在性檢測，即產(chǎn)生的新解是否符合存在矩陣，如果不符合則另外產(chǎn)生一個解直到滿足存在矩陣，之后再進(jìn)入適應(yīng)性檢測。

3) 在算法陷入局部最優(yōu)時，同樣從存在矩陣EM中產(chǎn)生新的解，而不是像傳統(tǒng)算法一樣隨機(jī)在整個解空間產(chǎn)生新解。

3.4 用戶QoS偏好適應(yīng)

從前面標(biāo)準(zhǔn)PSO流程可以看出，決定PSO解優(yōu)劣程度的是其目標(biāo)函數(shù)和由目標(biāo)函數(shù)決定的適應(yīng)度。為了適應(yīng)不同的用戶QoS需求的差異，下面對PSO的適應(yīng)度定義進(jìn)行改進(jìn)，加入對云存儲系統(tǒng)非常重要的QoS因素，并對這些因素進(jìn)行分類，用權(quán)重因子來指示這些因素的重要程度，即可以通過權(quán)重因子的調(diào)節(jié)來達(dá)到適應(yīng)不同用戶不同 QoS偏好的作用。

3.4.1 云存儲中的QoS因素歸納與效用函數(shù)定義

1) 云存儲中常見的QoS因素

適應(yīng)度函數(shù)F由多個約束因素決定，這些約束因素就是決定任務(wù)調(diào)度QoS的因素。根據(jù)現(xiàn)有研究[1～9,15,16]和自身經(jīng)驗，總結(jié)出以下主要影響因素。

si代表任務(wù)i所需要傳輸?shù)臄?shù)據(jù)量的大?。╯ize，單位：Megabyte）。

bij代表任務(wù)i的請求者和資源j之間的帶寬(bandwith，單位：Mbit/s，如果有多個帶寬值取最小值)。

以上二者的商其實就是任務(wù)i由資源j提供時要耗費(fèi)的傳輸時間tij。無論對云計算還是云存儲系統(tǒng)。一般時間以秒為單位。

cj代表使用資源j所花費(fèi)的代價，例如，使用服務(wù)器的代價明顯和使用一般的主機(jī)是不同的，中心節(jié)點使用的代價和邊緣節(jié)點使用代價也肯定是有差異的。各個節(jié)點的代價構(gòu)成了代價向量C= [c1,c2,…,cm]。

lj代表資源j在本調(diào)度周期前的負(fù)載（CPU負(fù)載、內(nèi)存負(fù)載、數(shù)據(jù)存儲負(fù)載等或者是綜合）。各個節(jié)點的負(fù)載構(gòu)成了負(fù)載向量L=[l1,l2, …,lm]。

dij代表任務(wù)i的請求者和資源j之間的網(wǎng)絡(luò)延遲（可以通過歷史數(shù)據(jù)預(yù)測，包括等待時間、預(yù)熱時間等），一般來說以秒為單位。各個節(jié)點的延遲量構(gòu)成了代價向量D=[d1,d2, …,dm]。

qj代表資源j的質(zhì)量，對于云存儲系統(tǒng)來說，主要考慮該資源節(jié)點的故障率，各個節(jié)點的質(zhì)量評價構(gòu)成了質(zhì)量向量Q= [q1,q2, …,qm]。

IOj代表資源j的IO并發(fā)數(shù)，該數(shù)目有上限，超過的話，服務(wù)器對新到的請求會拒絕。

2) QoS效用函數(shù)

由于各個QoS要求的物理意義不完全相同，計量單位也不一定相同，從而使得QoS值的量綱和數(shù)量級可能不同。需要利用 QoS 效用函數(shù)將每個候選資源節(jié)點的QoS屬性映射到一個實數(shù)值，通過該值對每個候選節(jié)點進(jìn)行評估和比較，以便選擇到滿足 QoS 約束的資源節(jié)點。

本文采用的效用函數(shù)是歸一化函數(shù)，其構(gòu)造方法是，將候選節(jié)點某QoS屬性與其對應(yīng)的最大值或最小值進(jìn)行比較，從而將多個QoS屬性值進(jìn)行歸一化處理(范圍在0～1)，使其轉(zhuǎn)化到一個綜合衡量的實數(shù)值(獨(dú)立于每個具體屬性的單位或范圍)，如下所示。

當(dāng)qi是效益型屬性，效益型的屬性值越大，表明屬性質(zhì)量越優(yōu)。

當(dāng)qi是成本型屬性，成本型的屬性值越小,表明屬性質(zhì)量越優(yōu)。

其中，minqi和maxqi分別表示在服務(wù)組QoS屬性q的最小值和最大值。

3.4.2 QoS偏好感知的適應(yīng)度定義

定義以下的適應(yīng)度函數(shù)fij，代表任務(wù)i由資源j執(zhí)行的適應(yīng)度為

因素的性質(zhì)各有不同，大致包括時間、代價、和質(zhì)量 3大方面。例如，文件大小si除以帶寬bij就是時間；費(fèi)用cj、負(fù)載lj屬于代價衡量范圍，而網(wǎng)絡(luò)延遲dij、網(wǎng)絡(luò)節(jié)點的質(zhì)量qj、服務(wù)器IO數(shù)是否充足可以看作是服務(wù)質(zhì)量衡量范疇。因此，適應(yīng)度函數(shù)可以被化為3大部分，由各自的因子協(xié)調(diào)重要性，λt、λc和λr分別被稱為時間因子、代價因子和可靠性因子。它們值的大小反映了對時間、代價和質(zhì)量的重視程度。

該權(quán)重和適應(yīng)度權(quán)重（λt、λc和λr）設(shè)定本文采用優(yōu)序判定法，減少主觀判斷。首先構(gòu)建判斷尺度，重要程度判斷尺度用1、2、3、4、5五級表示，數(shù)字越大，表明重要性越大。當(dāng)2個屬性對比時，如果一個屬性重要性為5，則另一屬性重要性為0；如果一個屬性為3，則另一個屬性為2。

該適應(yīng)度函數(shù)定義具有以下優(yōu)點。

1) 具有很好的可擴(kuò)展性：本文所總結(jié)的因素僅僅是針對云存儲系統(tǒng)而言比較重要的一部分。在計算網(wǎng)格或其他系統(tǒng)中，還會有其他一些因素。當(dāng)需要的時候，這些因素可以融入已有框架中，加入時間、代價或可靠性部分。需要的時候現(xiàn)有的因子也可以被剔除。即僅僅需要根據(jù)實際情況對適應(yīng)度函數(shù)f做相應(yīng)修改，其他部分不變，就可以滿足不同系統(tǒng)的需要。

2) 具有偏好適應(yīng)性：可以根據(jù)各因子的調(diào)整，滿足不同偏好的要求。例如，某些用戶對數(shù)據(jù)的傳輸時間并不看重，它們寧愿用更多的等待時間來換取更低的服務(wù)費(fèi)用。對這類任務(wù)調(diào)高代價因子、調(diào)低時間因子能獲得更加有針對性的調(diào)度方案。

3.4.3 用戶QoS偏好感知算法流程

1) 任務(wù)優(yōu)先度決定因子設(shè)定值

前文提到 QoS可以歸為3類，任務(wù)對QoS偏好的組合，根據(jù)對用戶的調(diào)查（主要是詢問了本校網(wǎng)絡(luò)專業(yè) 10級的學(xué)生）主要可以分為以下5類。

最高級為同時看重質(zhì)量和時間的任務(wù)，如此高要求代價上就不能要求太多，等級標(biāo)記為 5（組合中三方面同時要求的情況實際中不允許，而學(xué)生們對得到高效有質(zhì)量保證的服務(wù)必須付出的代價也有共識）。其次，對質(zhì)量、時間、代價其一做要求，其中，由于時間要求比較緊迫，設(shè)定等級為 4；要求質(zhì)量的等級設(shè)定為 3；僅僅對代價有要求的設(shè)定為 2（要求少花錢，那么對效率和質(zhì)量就不能有太高要求，這類劃分也受到被詢問學(xué)生的贊同）。最后，沒有要求的被設(shè)置為等級1。

用1～5代表不同的程度，根據(jù)等級設(shè)定時間因子、代價因子和可靠性因子的取值。例如，設(shè)定等級5代表用戶希望任務(wù)耗時短、可靠性高、不計代價，那么時間和可靠性因子則設(shè)為高值，代價因子設(shè)為低值；等級2則代表用戶希望代價越低越好，不計較消耗的時間和可靠性，對應(yīng)時間和可靠性因子則設(shè)為低值，代價因子設(shè)為高值。等級1比較特殊，沒有要求，這里視為對代價有最高要求。不同于等級 2，雖然對代價看重但對時間和質(zhì)量還有一定的期待。等級1代價取1，其他因素取0。

對于因子的具體取值，本文采用優(yōu)序?qū)Ρ确ㄟM(jìn)行設(shè)定，能夠一定程度上減弱用戶和系統(tǒng)管理員的主觀影響，具體如下。

以任務(wù)優(yōu)先級為5時的各因子值設(shè)定優(yōu)序?qū)Ρ葹槔?/p>

表1 基于優(yōu)序判定法的因子值設(shè)定（當(dāng)任務(wù)優(yōu)先級為5時）

當(dāng)任務(wù)為其他優(yōu)先級時的設(shè)定方法以此類推，最終的設(shè)定值如表2所示。

表2 任務(wù)優(yōu)先級對應(yīng)的各因子取值

于是，一個等待調(diào)度的任務(wù)實際上包含2個維度的數(shù)據(jù)（數(shù)據(jù)量大小s，任務(wù)優(yōu)先級p）。計算適應(yīng)度時，根據(jù)p取3個因子的值。

而代價向量C= [c1,c2,…,cm]是一個預(yù)定義的向量，序號代表系統(tǒng)節(jié)點的編號，即c1代表節(jié)點1的使用代價。代價的程度值是系統(tǒng)的管理人員根據(jù)節(jié)點本身的配置花費(fèi)、能耗花費(fèi)等評估而得。

適應(yīng)度計算還需要l、d、q等值，可以實時從系統(tǒng)節(jié)點日志記錄中獲取，與代價類似構(gòu)成負(fù)載向量L、延遲向量D、質(zhì)量向量Q等。再根據(jù)定義和式(5)、式(6)計算需要的歸一化值。本文的實驗系統(tǒng)設(shè)計并實現(xiàn)有專門記錄和計算這些值的模塊，隨著調(diào)度的進(jìn)行，各項值會按當(dāng)前值與記錄的最大最小值進(jìn)行更新。

以上的計算是針對某一個確定解的，即任務(wù)在某個具體的節(jié)點執(zhí)行已經(jīng)確定，則以上各項值都可以獲取到。最后比較所得所有解的適應(yīng)度值，取最小適應(yīng)度對應(yīng)的解為最終確定解。

2) 算法流程

依照以上定義和改進(jìn)，適應(yīng)用戶 QoS偏好的PSO云存儲任務(wù)調(diào)度算法流程示意如圖1所示。限于篇幅標(biāo)準(zhǔn)PSO流程省略，僅僅突出了改進(jìn)之處。

圖1 帶QoS偏好感知的PSO任務(wù)調(diào)度

4 實驗與分析

為了分析本文所提偏好感知任務(wù)調(diào)度算法的有效性，設(shè)計并用 MATLAB實現(xiàn)了一個云存儲偏好感知仿真平臺，模擬云存儲從提交任務(wù)請求到調(diào)度指定節(jié)點提供任務(wù)資源的過程。仿真平臺由3大模塊組成，其中，模擬條件生成模塊負(fù)責(zé)模擬云存儲系統(tǒng)的各種條件，包括網(wǎng)絡(luò)的帶寬、網(wǎng)絡(luò)線路的延遲、節(jié)點的負(fù)載、節(jié)點故障、節(jié)點的 IO并發(fā)數(shù)等；資源定位模塊負(fù)責(zé)根據(jù)任務(wù)需求和系統(tǒng)本身的資源記錄表實時生成資源存在矩陣EM；任務(wù)調(diào)度模塊則負(fù)責(zé)根據(jù)本文的算法對任務(wù)進(jìn)行調(diào)度。

實驗統(tǒng)一設(shè)置最大迭代次數(shù)為100次，為避免干擾導(dǎo)致的某些個別情況，每個實驗重復(fù)進(jìn)行 10次，每次實驗記錄“運(yùn)行時間”、“迭代次數(shù)”等參數(shù)以待對比。運(yùn)行時間就是指算法從開始接受輸入需要調(diào)度的任務(wù)向量開始，到最后輸出一個可以接受的調(diào)度序列的時間。迭代次數(shù)記錄的是最后輸出的調(diào)度序列是第幾次迭代產(chǎn)生的，這個值可以考察算法的收斂速度。偏好適應(yīng)率則是考察生成的調(diào)度序列多大程度上滿足了用戶的偏好。

下面就傳統(tǒng) PSO算法和改進(jìn)后的帶偏好感知的PSO算法對偏好感知的具體效果進(jìn)行考察（都有存在矩陣限制）。隨機(jī)生成的Task向量自帶對QoS因素的要求（代價、時間、質(zhì)量），對應(yīng)的值在0～1之間。調(diào)度結(jié)果提供節(jié)點的對應(yīng)值大于或等于要求則視為滿足了用戶QoS要求，反之視為不滿足。用一個偏好評價函數(shù)進(jìn)行自動檢查，給出任務(wù)偏好滿意百分比，計算方法如下

需要說明的是，IO并發(fā)數(shù)對質(zhì)量的影響，已有并發(fā)數(shù)多并不一定就比已有并發(fā)數(shù)少的服務(wù)器提供更差的服務(wù)，這點在實驗時表現(xiàn)出對調(diào)度評價的影響并不符合實際。更多情況下要考慮剩余并發(fā)數(shù)的多少。因此，將 IO改為剩余并發(fā)數(shù)，即從成本型改為效益型，值越大越好。調(diào)度模塊為某節(jié)點調(diào)度一個任務(wù)后，更新節(jié)點的各項值，對 IO來說減少了一個并發(fā)數(shù)。

對比結(jié)果如表3所示，可以看到，傳統(tǒng)PSO對有偏好要求的任務(wù)是完全沒辦法滿足的，平均只有22%的滿足率，全憑運(yùn)氣。而本文改進(jìn)的PSO算法偏好滿足率上升 40%達(dá)到了 60%。說明改進(jìn)后的PSO算法確實帶有一定的偏好感知能力。但是距離預(yù)計80%以上的偏好滿足率還有一定差距。

開始以為是因子設(shè)置問題，但是無論怎么調(diào)整因子的值，實驗的偏好滿足率都只有約50%～70%。后來發(fā)現(xiàn)，問題不在于因子值，以上優(yōu)序判定的因子已經(jīng)比較合適。真正的原因是各個等級任務(wù)所占百分比。實驗?zāi)M是一般的金字塔型的任務(wù)分布，即高等級的任務(wù)比例比較小，大量的是低級任務(wù)的情況，中間等級的任務(wù)中等數(shù)量，這也是一般系統(tǒng)的任務(wù)分布。第3.4.2節(jié)設(shè)計的感知偏好的適應(yīng)度具有對單個任務(wù)QoS感知識別的能力。但是PSO算法的選擇是對總體QoS的評估。于是出現(xiàn)了占80%以上的優(yōu)先級只有1、2的任務(wù)的偏好左右了總體QoS偏好，導(dǎo)致整體偏好滿意率不高。這50%～70%被滿足的任務(wù)大部分是占有率高的低級任務(wù)。這種情況在筆者調(diào)整了各個等級任務(wù)的分布百分比后有所改善，特別當(dāng)各等級任務(wù)所占百分比相同的情況下，占有率對整體偏好影響達(dá)到最小，偏好滿足率基本在 80%以上。但是這種情況在現(xiàn)實中是很少的。大量存在的其實是表 3代表的金字塔型的任務(wù)分布。因此，這次實驗說明對于偏好不同且分布相差大的任務(wù)調(diào)度其實不適合用PSO算法進(jìn)行整體調(diào)度。

表3 帶偏好感知的PSO云存儲調(diào)度算法

最后，筆者把這些任務(wù)按優(yōu)先級進(jìn)行分級調(diào)度（按優(yōu)先級先后順序調(diào)度），即將3.4.3節(jié)算法里的“任務(wù)矩陣”按優(yōu)先級先后輸入，高優(yōu)先級完成后，再進(jìn)行低優(yōu)先級的調(diào)度，其余不變，得到了90%～100%的偏好滿足率如表4所示。雖然總體滿意率較高，但是優(yōu)先級低的滿意率居然高于優(yōu)先級高的。分析發(fā)現(xiàn)原因在于：由于是按優(yōu)先級從高到底順序調(diào)度，優(yōu)秀的資源優(yōu)先調(diào)度給了優(yōu)先級較高的任務(wù)。但是資源總是比任務(wù)少，高優(yōu)先級的任務(wù)意味著高資源要求，在總體資源受限的情況下，無法完全滿足高優(yōu)先級任務(wù)。而低優(yōu)先級任務(wù)唯一的就是代價要求，因此在其他任務(wù)將代價高的資源先占用的情況下反而可以保證其代價低的要求，因而其滿足率最高。

表4 分級的帶偏好感知的PSO云存儲調(diào)度算法

因而算法流程改變?yōu)閳D2所示按優(yōu)先級先后調(diào)度，調(diào)度算法內(nèi)部流程不變，輸入改為按任務(wù)優(yōu)先級順序輸入。不建議并發(fā)調(diào)度，因為并發(fā)過程優(yōu)秀資源可能被低級任務(wù)占用。

圖2 分級的帶偏好感知的PSO調(diào)度

5 結(jié)束語

本文對云存儲任務(wù)調(diào)度進(jìn)行建模，總結(jié)并歸納出云存儲任務(wù)QoS要求主要有3個方面，即時間、代價和質(zhì)量，每個方面又包含若干具體因素。修改PSO算法的適應(yīng)度定義，用權(quán)重因子調(diào)節(jié)對不同QoS偏好的要求。實驗表明，通過對適應(yīng)度的修改，確實可以使得PSO調(diào)度具備一定的偏好感知能力。但是，由于PSO是整體評價算法，則在各優(yōu)先級任務(wù)分布差異較大的情況下，占有率較高的任務(wù)的QoS偏好會掩蓋其他占有率較低的任務(wù)的偏好，影響這些任務(wù)的偏好滿足率。解決方案是按優(yōu)先級分別調(diào)度這些任務(wù)。

總體來說，本文最大的發(fā)現(xiàn)是對于任務(wù)分布不均的系統(tǒng)，不適宜用PSO進(jìn)行有偏好感知的整體調(diào)度，一定要進(jìn)行分級的調(diào)度。本文將PSO算法引入云存儲領(lǐng)域并進(jìn)行偏好感知的一些經(jīng)驗，特別是不成功的經(jīng)驗希望能給后來者以參考。

[1] HAYES B. Cloud computing[J]. Communications of the ACM, 2008,51(7):9-11.

[2] LIN G , DASMALCHI G, ZHU J. Cloud computing and IT as a service:opportunities and challenges[A]. Proceedings of 2008 IEEE International Conference on Web Services[C]. Beijing, China, 2008.5.

[3] NAMJOSHI J, GUPTE A. Service oriented architecture for cloud based travel reservation software as a service[A]. Proceedings of the 2009 IEEE International Conference on Cloud Computing(CLOUD'09)[C].Bangalore, India, 2009.147-150.

[4] VAZHKUDAI S, TUECKE S, FOSTER I. Replica selection in the globus data grid[A]. Proceedings the First IEEE/ACM International Symposium on Cluster Computing and the Grid[C]. Brisbane, Qld, 2001.106-113.

[5] VAZHKUDAI S, SCHOPF J M, FOSTER I. Predicting the performance of wide area data transfers[A]. Proceedings of International Parallel and Distributed Processing Symposium, Marriott Marina[C]. Fort Lauderdale, FL, USA, 2002.34-43.

[6] CHANG R S, CHEN P H. Complete and fragmented replica selection and retrieval in data grids[J]. Future Generation Computer Systems,2007, 23(4): 536-546.

[7] RAHMAN R M, ALHAJJ R, BARKER K. Replica selection strategies in data grid[J]. Journal of Parallel and Distributed Computing, 2008,68(12): 1561-1574.

[8] JIN J, ROTHROCK L, MCDERMOTT P L,et al. Using the analytic hierarchy process to examine judgment consistency in a complex multi-attribute task[J]. IEEE Transactions on Systems, Man and Cybernetics, Part A: Systems and Humans, 2010, 40(5): 1105-1115.

[9] 熊潤群, 羅軍舟, 宋愛波等. 云計算環(huán)境下QoS偏好感知的副本選擇策略[J]. 通信學(xué)報, 2011, 32(7):94-102.XIONG R Q, LUO J Z, SONG A B,et al. QoS preference-aware replica selection strategy in cloud computing[J]. Journal on Communications,2011,32(7):94-102.

[10] MA T H, YAN Q Q, LIU W J,et al. Grid task scheduling: algorithm review[J]. The Institution of Electronics and Telecommunication Engineers, 2011, 28(2):158-167.

[11] CHEN R M, WANG C M. Project scheduling heuristics-based standard PSO for task-resource assignment in heterogeneous grid[J].Hindawi Publishing Corporation Abstract and Applied Analysis, 2011,2011:1-20.

[12] KENNEDY J, EBERHART R C. Particle swam optimization[A].Preceedings of the IEEE International Conference on Neural Networks,Path[C]. Australia, 1995.1942-1948.

[13] SHI Y H, RUSSELL E B. A modified particle swarm optimizer[A].Proceedings of IEEE International Conference on Evolutionary Computation[C]. Anchorage, AK, 1998.69-73.

[14] 王娟, 李飛, 張路橋. 限制解空間的 PSO 云存儲任務(wù)調(diào)度算法[J].計算機(jī)應(yīng)用研究, 2013,30(1):127-129.WANG J, LI F, ZHANG L Q. Task scheduling algorithm in cloud storage system using PSO with limited solution domain[J]. Application Research of Computers, 2013, 30(1):127-129.

[15] HE X S, SUN X H, GREGOR V L. QoS guided min-min heuristic for grid task scheduling[J]. Journal of Computer Science and Technology,2003, 18(4):442-451.

[16] CHAUHAN S S, JOSHI R C. QoS guided heuristic algorithms for grid task scheduling[J]. International Journal of Computer Applications,2010, 2(9):24-31.