云計算環(huán)境下的PSO可信資源調(diào)度

丁燕艷，潘 郁，程仕偉

南京工業(yè)大學 經(jīng)濟與管理學院，南京 211816

云計算環(huán)境下的PSO可信資源調(diào)度

丁燕艷，潘 郁，程仕偉

南京工業(yè)大學 經(jīng)濟與管理學院，南京 211816

1 引言

云計算是并行計算（Parallel Computing）、分布式計算（Distributed Computing）和網(wǎng)格計算（Grid Computing）的發(fā)展[1]，是這些計算機科學概念的商業(yè)實現(xiàn)。云計算能提供動態(tài)資源池、虛擬化和高可用性的下一代計算平臺的核心技術(shù)。它將計算任務分布在大量計算機構(gòu)成的資源池上，使各種應用系統(tǒng)能夠根據(jù)需要獲取計算力、存儲空間和各種軟件服務，并按照使用付費。不同于網(wǎng)格計算，云計算具有更廣泛含義的計算平臺，能夠支持非網(wǎng)格的應用。且云計算使用的是集中的資源，而網(wǎng)格計算實際上是收集分散的資源，在資源的占用上，區(qū)別于網(wǎng)格的獨占式的資源分配模式，云中的資源將被所有的用戶同時共享?？紤]云計算本身的特性及與網(wǎng)格計算的差異性，現(xiàn)有的大量針對網(wǎng)格計算的資源分配和調(diào)度的算法無法直接移植到云計算環(huán)境下。

現(xiàn)有為數(shù)不多的關(guān)于云計算環(huán)境下資源調(diào)度的文獻中，文獻[2]提出的具有雙適應度的遺傳算法（DFGA）能有效地解決云計算環(huán)境下資源的分配問題，文獻[3]提出的基于蟻群優(yōu)化（Ant Colony Optimization）的計算資源分配算法通過在Gridsim環(huán)境下的仿真分析和比較，亦證明其能在滿足云計算環(huán)境要求的前提下有效地調(diào)度資源。文獻[4]運用離散粒子群算法對云計算環(huán)境下的負載均衡問題進行研究，根據(jù)云計算環(huán)境下資源需求動態(tài)變化建立相應的資源-任務分配模型，提高了資源利用率和云計算資源的負載均衡。但這些模型中鮮有考慮到任務間的輸入輸出關(guān)系、執(zhí)行順序，策略中也很少考慮動態(tài)節(jié)點資源的可信性問題。實際上，任務的串并聯(lián)結(jié)構(gòu)在實際的操作中是非常現(xiàn)實的，且動態(tài)提供的資源的可信性無論對云計算基礎(chǔ)運營商，還是對服務運營商，都是非常關(guān)鍵的因素。因此，結(jié)合任務間的結(jié)構(gòu)關(guān)系、云計算環(huán)境下節(jié)點本身性能低、易失效的特點和資源請求表現(xiàn)出的很強的波動性，為保證動態(tài)提供的資源的可信性，又不影響資源的使用效率，本文提出了一種基于任務結(jié)構(gòu)的更加可信的資源動態(tài)調(diào)度策略。

本文首先介紹云計算環(huán)境下基于任務間串并聯(lián)結(jié)構(gòu)和輸入輸出關(guān)系的動態(tài)資源分配模型，然后在考慮了節(jié)點資源可信性的基礎(chǔ)上，提出了云計算環(huán)境下基于可信性的動態(tài)資源分配模型，最后通過Matlab進行仿真實驗，實驗結(jié)果驗證了算法的可行性，以及與其他沒有考慮節(jié)點可信性算法相比時解的質(zhì)量的優(yōu)越性。

2 問題描述

資源調(diào)度具體包括三個子問題：映射任務；給出任務調(diào)度順序；給出資源上任務的執(zhí)行順序。本文采用無環(huán)有向圖 Directed Acyclic Graph（DAG）來映射任務[5]，由G=(V，E)表示，如圖1所示。其中，每個節(jié)點V代表不同的任務T，T={T1，T2，…，Tk}表示任務T的集合。邊E代表了任務間的關(guān)聯(lián)度，即任務間是否存在輸入輸出關(guān)系。若(Tj，Tk)∈E，則用fik表示Tj產(chǎn)生數(shù)據(jù)并輸入Tk。S={S1，S2，…，Sj}表示存儲資源節(jié)點的集合，PC={PC1，PC2，…，PCj}代表計算資源節(jié)點的集合。

假設存在5個任務T={T1，T2，…，T5}，任務間的作業(yè)先后順序如圖1中左圖所示。同時，假設有3個資源節(jié)點可供調(diào)度如圖1中右圖所示。則資源調(diào)度的目標就是在不超過截止期的前提下，充分合理地利用各種可用資源，最大限度地減少服務的開銷，使服務價值最大化。

由于云計算服務中心的大量低性能、廉價計算機集群中，節(jié)點的失效對于調(diào)度策略的性能具有較大的影響，因此在問題模型中引入了可信度的概念，即在節(jié)點分配的過程中，結(jié)合節(jié)點失效的特征，選擇可靠性較高的節(jié)點來運行作業(yè)，提高調(diào)度性能。

研究表明，節(jié)點資源的失效表現(xiàn)出很強的時間局部規(guī)律性，即在運行周期中不同的時間段內(nèi)表現(xiàn)出不同的特征，可看作是一個隨機過程，這個隨機過程符合參數(shù)β為1的韋伯分布[6]，記為W(α，β)。其中α稱為尺度參數(shù)，β稱為形狀參數(shù)，其概率密度和分布函數(shù)分別為：

當β=1時，W(α，1)就是參數(shù)為α的指數(shù)分布。

韋伯分布是可靠性中廣泛使用的連續(xù)型分布，它可以用來描述疲勞失效，真空管失效和軸承失效等壽命分布。結(jié)合式（1）、（2）易得單個節(jié)點的失效函數(shù)為：

易見，當β＞1時，r(t)是遞增的；當β＜1時，是遞減的；當

根據(jù)節(jié)點失效的特征，可以將節(jié)點失效分為三類：永久失效、間歇性失效和瞬間失效。如果某節(jié)點發(fā)生永久性失，則使用另一個新的節(jié)點代替該節(jié)點的功能，對于用戶而言相當于發(fā)生了一次節(jié)點重啟事件。而間歇失效和瞬間失效則可以通過節(jié)點的重啟來修復。因此，可以將計算機集群中節(jié)點的失效看作節(jié)點的重啟[7]。當節(jié)點系統(tǒng)運行到一定的時間門限值tmax，即節(jié)點的恢復時間，對此節(jié)點進行重啟，節(jié)點的可靠性提高。

文獻[8]也指出了云計算環(huán)境下，節(jié)點無計劃重啟的失效概率有隨運行時間先下降后上升的趨勢。這說明節(jié)點在剛剛啟動時可靠性較低，容易出故障，之后在正常運行時間超過一定值后，故障率又開始上升，節(jié)點變得越來越不可靠。

由此，根據(jù)資源節(jié)點失效的特性，得出節(jié)點正常運行的可信度函數(shù)為：

其中t是節(jié)點運行時間，根據(jù)云環(huán)境下節(jié)點運行的規(guī)律，在節(jié)點剛啟動時α＜1，其可信性隨著時間的增加而增加；當節(jié)點運行到一個穩(wěn)定的時間門限tmid后，節(jié)點的可信性隨著時間的增加而降低；當節(jié)點運行到時間門限值tmax后，節(jié)點進行重啟，α＜1。

3 建立模型

本文以服務價值最大化為目標，其中總成本Ct由兩個部分組成，一是計算資源的服務使用費Ca，另一部分為任務間數(shù)據(jù)傳輸引起的傳輸費用Cb，此項費用當且僅當任務節(jié)點間存在輸入輸出關(guān)系時產(chǎn)生。其中：

表示計算資源節(jié)點PCj上所有任務T的計算費用，wkj表示將任務Tk分配到節(jié)點PCj上的費用。

圖1 任務映射圖

表示任務k1輸出傳輸給任務k2產(chǎn)生的費用，其中k1≠k2，ek1，k2為DAG中邊的權(quán)重，代表任務間的數(shù)據(jù)傳輸量，dk1，k2為單位數(shù)據(jù)傳輸費用。當且僅當ek1，k2＞0時，存在Cb(j)。

上文已指出，在資源調(diào)度的過程中，節(jié)點的失效將會大大地影響調(diào)度的效率和性能。因此結(jié)合資源節(jié)點的可信性，給出了節(jié)點的可信調(diào)度策略。定義目標函數(shù)為：

其中式（8）確保了在資源分配初期，所有的任務盡可能均勻地分派到各個節(jié)點上。式（9）為節(jié)點PCj的總費用。γ，η分別為費用和可信度的權(quán)重系數(shù)，0＜γ，η＜1，且γ+η=1。

4 算法求解

粒子群算法（Particle Swarm Optimization，PSO）最早是Kennedy和Eberhart于1995年提出的，該算法是通過群體粒子間的合作與競爭產(chǎn)生集群智能指導的并行搜索算法[9-10]，用來解決傳統(tǒng)搜索方法解決不了的目標函數(shù)超曲面復雜和非線性問題。

該算法中每個優(yōu)化問題的解都被抽象成搜索空間中的一個沒有大小和質(zhì)量的“粒子”。所有的粒子都有自己在空間中的位置和一個適應值，每個粒子還有一個速度決定它們飛翔的方向，然后粒子們就追隨當前的最優(yōu)粒子在解空間中搜索。在搜索過程中，粒子通過跟蹤兩個“極值”來更新自己。第一個就是初始到當前迭代歷史中搜索產(chǎn)生的粒子本身的最優(yōu)解，即個體極值Pbest，另一個極值為整個種群中當前的最優(yōu)解，即全局極值Gbest。

在本文，因為資源調(diào)度屬NP完全問題，因此用PSO算法中的離散粒子群算法求解。具體地，定義第t次迭代時第i個粒子在m維空間的位置為其中，表示任務T1第t次迭代時選擇的資源

節(jié)點為PCi，k為總的任務數(shù)量。將目標函數(shù)值最小作為評價標準，即適應度函數(shù)為：

其中，i=(1，2，…，n)，w為慣性因子，Rand1()和Rand2()均是在（0，1）區(qū)間上獨立同分布的均勻分布隨機數(shù)。c1和c2為學習因子。以圖1為例，隨機產(chǎn)生一個初始解如圖2所示，將其映射到PSO算法中，其解的形式為[1，2，1，3，2]。

圖2 解的構(gòu)造

5 算法實現(xiàn)

鑒于本問題模型的數(shù)學結(jié)構(gòu)，設計粒子群優(yōu)化算法偽代碼如下。

（1）計算各個任務在所有節(jié)點上的服務使用費用，建立服務使用費列表

（2）建立各個節(jié)點數(shù)據(jù)傳輸費用列表

（3）建立任務間數(shù)據(jù)傳輸量表

（4）建立節(jié)點可信度列表

（5）建立任務執(zhí)行順序序表

（6）初始化PSO算法中相關(guān)參數(shù)

Repeat

掃描任務執(zhí)行順序序表，建立ready task表

%ready task存放符合任務先后執(zhí)行順序表的合法任務，且當下可以馬上為其調(diào)度資源的任務。

for所有的 ready tasks{Ti}{Ti}∈Tdo

根據(jù)PSO算法將資源{PCj}分配到任務{(diào)Ti}上

end for

%派遣所有ready task的任務

等待系統(tǒng)投票執(zhí)行

更新ready tasks列表

%為被阻塞的后續(xù)任務分配資源，將其加入ready task，并將已完成的任務從中ready task的任務集合中刪除。

根據(jù)當前任務間的負載情況更新數(shù)據(jù)傳輸列表

計算PSO相關(guān)值

until所有的任務都調(diào)度完畢

6 算法仿真與結(jié)果分析

本文采用Amazon Web Service中的Elastic Compute Cloud（EC2）和Cloud Front服務的相關(guān)費用作為云計算服務中計算和傳輸服務的費用[11]。具體任務結(jié)構(gòu)如圖1所示。其中，為了更加符合商務活動、科學活動全球化趨勢，以及凸顯數(shù)據(jù)傳輸代價的差異性，本文使任務在不同云計算服務中心間進行數(shù)據(jù)傳輸，且假設終端所在地無服務中心。

為此設PC1、PC2、PC3分別為Amazon位于United States East的Virginia、European Union的Ireland和Asia Pacific的Singapore。不同區(qū)域的服務費用如下：矩陣AS、BI、BO分別為任務計算服務費用、單位（TB）數(shù)據(jù)輸入和輸出費用（數(shù)據(jù)量不同費用不同），DC表示不同任務輸入輸出時數(shù)據(jù)量的變化，費用單位為美元$，數(shù)據(jù)量單位為TB，具體如下：

由于云計算的一個局部可以看作一個特殊的網(wǎng)格環(huán)境，所以本文用Cloudsim來模擬一個云計算的局部環(huán)境，并采用Matlab7.1進行仿真分析。其中，主要參數(shù)設置如下：b=5，γ=0.45，η=0.55，c1=2，c2=2。該算例選取粒子群體規(guī)模為25，迭代次數(shù)為20。機器的可靠性概率初始分布和初始解均由計算機隨機生成。執(zhí)行結(jié)果如圖3所示，圖中可以看出，算法收斂于最優(yōu)解9.897 5，證明了算法的可行性。

圖3 算法收斂情況

針對上述的算例，本文對b的取值進行了變化使得最大數(shù)據(jù)傳輸量超越了10 TB、40 TB、100 TB、150 TB四個臨界值，計算對應任務的資源調(diào)度分布情況，結(jié)果如圖4所示。圖4表明在該算法下，所有的任務都被均衡地分布在各個資源上，實現(xiàn)了資源最大化利用。從該圖中也可以看出，當數(shù)據(jù)量較小時，任務以較大概率分配到計算費用較低廉的服務節(jié)點上，但隨著數(shù)據(jù)量的上升，任務被均勻地分布到各個節(jié)點。此結(jié)果表明在數(shù)據(jù)量較小的情況下可優(yōu)先考慮可信度高且費用開銷較低的節(jié)點，數(shù)據(jù)量較大的時候可以均勻地分配任務提高完成效率。

圖4 負載分布情況

任務的成功分配率即云用戶的任務能夠在規(guī)定的期限di內(nèi)完成的完成率，定義任務的成功分配率[12]公式如下：

其中，Di表示任務Ti的完成時間。

為了更好地驗證本文提出的算法的有效性，在上述的仿真環(huán)境和參數(shù)設置下，對算例中的規(guī)模進行擴展后，將文獻[2]中提出的算法以及不考慮節(jié)點可信性的粒子群算法，與本文所提出的考慮節(jié)點資源可信性的分配算法進行失效測試比較，即比較各個算法的任務的成功分配率。

在模擬的云計算局部環(huán)境下，設置了模擬任務的任務截止期，將用戶并發(fā)數(shù)量從50增加到350，記錄其任務的成功完成情況，圖5為50次實驗的成功分配率的平均值。從圖5可看出，基于可信性的資源分配策略相對于沒有考慮可信性的資源分配策略有更高的任務成功執(zhí)行率。

圖5 任務成功分配率

7 結(jié)論

云計算環(huán)境下，面對海量信息的存儲、計算和傳輸，其提供的諸如Saas，Paas等服務卻比網(wǎng)格對基礎(chǔ)設施的要求更高，所以一個好的資源調(diào)度算法尤為重要。本文提出的基于可信性的且有作業(yè)串并聯(lián)結(jié)構(gòu)的云計算資源分配模型能較好地模擬現(xiàn)實作業(yè)，且算例測試中采用了Amazon Web Service的真實數(shù)據(jù)，結(jié)合粒子群算法求解，結(jié)果能較好地說明算法的可行性，且該模型的執(zhí)行性能明顯優(yōu)于沒有考慮節(jié)點可信性的資源分配模型，能更可靠更高效地完成云計算環(huán)境下的計算資源搜索與分配工作。

[1]Marston S，Li Z，Bandyopadhyay S.Cloud computing—the business perspective[J].Decision Support Systems，2011，51（1）：176-189.

[2]華夏渝，鄭駿，胡文心.基于云計算環(huán)境的蟻群優(yōu)化計算資源分配算法[J].華東師范大學學報：自然科學版，2010（1）：127-134.

[3]李建鋒，彭艦.云計算環(huán)境下基于改進遺傳算法的任務調(diào)度算法[J].計算機應用，2011，31（1）：184-186.

[4]馮小靖，潘郁.云計算環(huán)境下的DPSO資源負載均衡算法[J].計算機工程與應用，2013，49（6）：105-108.

[5]Pandey S，Wu Linlin，Guru S M，et al.A Particle Swarm Optimization（PSO）-based heuristic for scheduling workflow applications in cloud computing environments[C]//24th IEEE International Conference on Advanced Information Networking and Applications，Australia，2010，1（1）：400-407.

[6]曹晉華.可靠性數(shù)學引論[M].北京：高等教育出版社，2006：15-16.

[7]武林平，孟丹.LUNF——基于節(jié)點失效特征的機群作業(yè)調(diào)度策略[J].計算機研究與發(fā)展，2005（6）：1000-1005.

[8]Sahoo R K，Sivasubramaniam A，Squillante M S.Failure data analysis of a large-scale heterogeneous server environment[C]//Proceedings of the DSN2004，F(xiàn)lorence，Italy，2004：772-784.

[9]陳森發(fā).復雜系統(tǒng)建模理論與方法[M].南京：東南大學出版社，2005.

[10]Zhu Hanhong，Wang Yi，Wang Kesheng，et al.Particle Swarm Optimization（PSO）for the constrained portfolio optimization problem[J].Expert Systems with Applications，2011，38（8）：10161-10169.

[11]Amazon products[EB/OL].（2011-04-29）.http：//aws.amazon. com/.

[12]Chang Guiran，Wang Chuan，Xiong Yu，et al.Efficient Nash equilibrium based cloud resource allocation by using a continuous double auction[C]//2010 InternationalConference on Computer Design and Applications，2010：194-199.

[13]劉鵬.云計算[M].北京：電子工業(yè)出版社，2010：16-56.

DING Yanyan,PAN Yu,CHENG Shiwei

School of Economics and Management,Nanjing University of Technology,Nanjing 211816,China

The resource scheduling problem in cloud computing environment is discussed.According to the characteristics of the cloud computing environment,the tasks structure and the node failure,a mathematical resource scheduling model is established.The discrete particle swarm algorithm is used to solve the problem.The simulation test example is created according to the facts of the cloud computing service operation and the verification shows that the model is rational and the algorithm is feasible and effective.

cloud computing;resource scheduling;particle swarm algorithm;creditability;Weibull distribution

對云計算環(huán)境下的資源調(diào)度問題進行了研究。針對云計算環(huán)境下資源調(diào)度的特點，結(jié)合節(jié)點失效以及任務間的網(wǎng)狀結(jié)構(gòu)特點，建立資源調(diào)度問題數(shù)學模型，運用離散粒子群算法求解該問題。針對模型特點結(jié)合云計算服務運營實情，設計算例進行仿真測試。驗證表明了所建立模型的合理性及該算法求解的可行性和有效性。

云計算；資源調(diào)度；粒子群算法；可信度；韋伯分布

A

TP393

10.3778/j.issn.1002-8331.1112-0284

DING Yanyan,PAN Yu,CHENG Shiwei.Creditable resource scheduling based on particle swarm algorithm in cloud computing.Computer Engineering and Applications,2013,49（18）：78-81.

南京市科技計劃項目（No.201007006）。

丁燕艷（1987—），女，碩士，研究方向：管理決策與人工智能；潘郁（1955—），男，教授，研究方向：計算管理與商務智能；程仕偉（1987—），男，碩士，研究方向：計算管理系統(tǒng)與人工智能。E-mail：dingyanyan77@163.com

2011-12-14

2012-04-09

1002-8331（2013）18-0078-04

CNKI出版日期：2012-05-21 http://www.cnki.net/kcms/detail/11.2127.TP.20120521.1142.056.html