王娟，李飛，張路橋

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

1 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

云存儲(chǔ)系統(tǒng)任務(wù)調(diào)度的目標(biāo)就是在適應(yīng)度函數(shù)的指引下找到最符合目標(biāo)函數(shù)的調(diào)度方案。這里的適應(yīng)度函數(shù)可以簡(jiǎn)單指任務(wù)完成時(shí)間，也可以是使用資源的代價(jià)、可靠性等。而目標(biāo)函數(shù)則只有 2種：一種是取適應(yīng)度函數(shù)的最大值，另一種是取適應(yīng)度函數(shù)的最小值。很多情況下，通過(guò)改變適應(yīng)度函數(shù)的定義，目標(biāo)函數(shù)可以相互轉(zhuǎn)換。例如：取任務(wù)完成時(shí)間為適應(yīng)度函數(shù)，一般的目標(biāo)函數(shù)就是取完成時(shí)間的最小值。這個(gè)定義等同于取任務(wù)完成時(shí)間的倒數(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)度是一個(gè)NP難題，沒(méi)有最優(yōu)解，只能通過(guò)啟發(fā)式算法尋找比較優(yōu)化的解[10]。當(dāng)前常用的啟發(fā)式算法中，粒子群優(yōu)化算法以其算法簡(jiǎn)單、計(jì)算方便、求解速度快受到任務(wù)調(diào)度研究者的重視[11]。下面研究如何改進(jìn)PSO算法以感知用戶偏好差異。

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

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

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

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

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

在式(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。在每一維，粒子都有一個(gè)最大限制速度Vmax，如果某一維的速度超過(guò)設(shè)定的Vmax，那么這一維的速度就被限定為Vmax(Vmax＞0)。

1998年Shi等[13]對(duì)前面的式(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í)數(shù)問(wèn)題，但對(duì)離散化的任務(wù)調(diào)度不能直接應(yīng)用。需要進(jìn)行轉(zhuǎn)化，一般方法是進(jìn)行編碼。對(duì)云存儲(chǔ)系統(tǒng)來(lái)說(shuō)，一個(gè)編碼就代表一個(gè)任務(wù)調(diào)度序列。出于描述方便采用十進(jìn)制編碼，假設(shè)有m個(gè)資源，n個(gè)任務(wù)，用Code=e1e2…ei…en表示任務(wù)調(diào)度向量，即一個(gè)調(diào)度方案。對(duì)云存儲(chǔ)系統(tǒng)來(lái)說(shuō)，ei代表第i個(gè)任務(wù)的數(shù)據(jù)由ei的值代表的資源節(jié)點(diǎn)提供，而該向量的長(zhǎng)度即是單位時(shí)間內(nèi)要調(diào)度任務(wù)的總量n。例如，某任務(wù)調(diào)度向量為[2, 4, 3, 4, 1, 5, 6]，這個(gè)向量的長(zhǎng)度是7，代表該單位時(shí)間需要調(diào)度的任務(wù)數(shù)為7。序號(hào)1的位置上的值是2，代表任務(wù)1的數(shù)據(jù)由系統(tǒng)的2號(hào)節(jié)點(diǎn)提供。以此類推，任務(wù)2和4的數(shù)據(jù)由節(jié)點(diǎn)4提供；任務(wù)3的數(shù)據(jù)由節(jié)點(diǎn)3提供；任務(wù)5的數(shù)據(jù)由節(jié)點(diǎn)1提供；任務(wù)6的數(shù)據(jù)由節(jié)點(diǎn)5提供；任務(wù)7的數(shù)據(jù)由節(jié)點(diǎn)6提供。

3.3 限制解空間

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

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

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

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

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

3) 在算法陷入局部最優(yōu)時(shí)，同樣從存在矩陣EM中產(chǎn)生新的解，而不是像傳統(tǒng)算法一樣隨機(jī)在整個(gè)解空間產(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需求的差異，下面對(duì)PSO的適應(yīng)度定義進(jìn)行改進(jìn)，加入對(duì)云存儲(chǔ)系統(tǒng)非常重要的QoS因素，并對(duì)這些因素進(jìn)行分類，用權(quán)重因子來(lái)指示這些因素的重要程度，即可以通過(guò)權(quán)重因子的調(diào)節(jié)來(lái)達(dá)到適應(yīng)不同用戶不同 QoS偏好的作用。

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

1) 云存儲(chǔ)中常見(jiàn)的QoS因素

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

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

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

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

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

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

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

qj代表資源j的質(zhì)量，對(duì)于云存儲(chǔ)系統(tǒng)來(lái)說(shuō)，主要考慮該資源節(jié)點(diǎn)的故障率，各個(gè)節(jié)點(diǎn)的質(zhì)量評(píng)價(jià)構(gòu)成了質(zhì)量向量Q= [q1,q2, …,qm]。

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

2) QoS效用函數(shù)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2) 算法流程

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

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

4 實(shí)驗(yàn)與分析

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)束語(yǔ)

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

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

[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] 熊潤(rùn)群, 羅軍舟, 宋愛(ài)波等. 云計(jì)算環(huán)境下QoS偏好感知的副本選擇策略[J]. 通信學(xué)報(bào), 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 云存儲(chǔ)任務(wù)調(diào)度算法[J].計(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.