改進(jìn)蟻群算法的云存儲任務(wù)調(diào)度算法研究

袁恩隆，李飛，唐籍濤，趙伯聽

（成都信息工程學(xué)院網(wǎng)絡(luò)工程學(xué)院，成都610225）

改進(jìn)蟻群算法的云存儲任務(wù)調(diào)度算法研究

袁恩隆，李飛，唐籍濤，趙伯聽

（成都信息工程學(xué)院網(wǎng)絡(luò)工程學(xué)院，成都610225）

由于云存儲環(huán)境與云計(jì)算環(huán)境中不同，若直接將云計(jì)算環(huán)境中的任務(wù)調(diào)度算法移植到云存儲環(huán)境中，必然會導(dǎo)致任務(wù)調(diào)度的效率下降。為解決此問題，提出了一種適用于云存儲環(huán)境中的改進(jìn)蟻群算法。改進(jìn)蟻群算法能使云計(jì)算環(huán)境的任務(wù)調(diào)度算法更符合云存儲的環(huán)境；同時(shí)，對于改進(jìn)PSO算法在引入存在矩陣時(shí)，由于數(shù)據(jù)資源不存在而造成算法前期優(yōu)化浪費(fèi)引起效率低下的問題進(jìn)行了有效解決。分析測試結(jié)果表明，提出的改進(jìn)蟻群算法在云存儲環(huán)境的任務(wù)調(diào)度算法在保障有效解的前提下能夠擁有更快的收斂速度。

云存儲；任務(wù)調(diào)度；蟻群算法

引言

近年來，隨著信息技術(shù)的普及和應(yīng)用，日積月累的數(shù)據(jù)已經(jīng)變得十分龐大，用戶對海量存儲的需求越發(fā)明顯。云存儲［1］成為了云計(jì)算后另一研究重點(diǎn)，云存儲的核心是對大量數(shù)據(jù)的存儲和管理。為了將數(shù)據(jù)安全且有效的存儲，相同的數(shù)據(jù)會存儲在許多不同的節(jié)點(diǎn)上，即產(chǎn)生許多冗余數(shù)據(jù)——副本。當(dāng)用戶向服務(wù)器提出數(shù)據(jù)請求任務(wù)時(shí)，系統(tǒng)會根據(jù)相應(yīng)的策略為用戶提供相對最優(yōu)的數(shù)據(jù)副本以及路徑，這就是任務(wù)調(diào)度。任務(wù)調(diào)度的優(yōu)劣很大程度上決定了系統(tǒng)的運(yùn)行處理效率。

目前，國內(nèi)針對在網(wǎng)格計(jì)算以及云計(jì)算環(huán)境中的任務(wù)調(diào)度算法的研究較多，而單獨(dú)對云存儲系統(tǒng)的任務(wù)調(diào)度算法的研究比較少見。云存儲系統(tǒng)本身是由云計(jì)算系統(tǒng)衍生而來，但是由于其主要任務(wù)不同，云計(jì)算以及網(wǎng)格計(jì)算主要是針對計(jì)算型任務(wù)，任務(wù)可以被委派到任意的云節(jié)點(diǎn)中進(jìn)行計(jì)算；而云存儲大多是數(shù)據(jù)傳輸?shù)娜蝿?wù)，因此在云存儲中，云中節(jié)點(diǎn)是否有用戶請求的數(shù)據(jù)決定了云存儲中的任務(wù)調(diào)度效率。雖然云存儲系統(tǒng)與云計(jì)算和網(wǎng)格計(jì)算大同小異，畢竟云存儲也是一個(gè)特殊的云系統(tǒng)，因此我們可以在借鑒前人的任務(wù)調(diào)度算法的同時(shí)應(yīng)該做出適當(dāng)?shù)母倪M(jìn)以適應(yīng)云存儲環(huán)境的特點(diǎn)。

在已有的對云存儲的任務(wù)調(diào)度算法的研究中，文獻(xiàn)［2］引入了存在矩陣以適應(yīng)云存儲的特點(diǎn)，但該文獻(xiàn)使用的是PSO任務(wù)調(diào)度算法。在PSO算法中引入存在矩陣會使其收斂效率低下，這是因?yàn)槿舸嬖诰仃囍械木仃図?xiàng)為0時(shí)，粒子前期的飛行計(jì)算就會被完全拋棄，浪費(fèi)了時(shí)間與資源。本文研究云存儲的任務(wù)調(diào)度算法，以相對成熟且被廣泛應(yīng)用的蟻群算法為算法基礎(chǔ)，沿用文獻(xiàn)［2］提出的存在矩陣，根據(jù)云存儲環(huán)境的特點(diǎn)對其進(jìn)行改進(jìn)。由于蟻群在更新信息素之前可以通過存在矩陣判斷出資源節(jié)點(diǎn)中是否有請求資源，因此在效率方面，蟻群算法［3-5］更加符合云存儲環(huán)境。實(shí)驗(yàn)證明，改進(jìn)之后的算法不僅能提高原始算法在云存儲環(huán)境中的有效解，節(jié)省大量時(shí)間；同時(shí)，改進(jìn)蟻群算法在效率上也比改進(jìn)PSO算法的效率要高。

1 云存儲任務(wù)調(diào)度的抽象

目前國內(nèi)外所研究的任務(wù)調(diào)度［6-7］分在線模式與批處理模式。在線模式是在任務(wù)到來的第一時(shí)間就產(chǎn)生映射進(jìn)行調(diào)度；而批處理模式是將任務(wù)累計(jì)到一定數(shù)量，等映射事件發(fā)生后再開始映射搜集的任務(wù)。本文的研究是對于“批處理”模式進(jìn)行的，即在一個(gè)單位時(shí)間內(nèi)有n個(gè)新任務(wù)產(chǎn)生并等待調(diào)度。本文使用以下定義∶

定義1 T=｛t1，t2，...tn｝代表單位時(shí)間內(nèi)等待調(diào)度的任務(wù)集。n是任務(wù)數(shù)。

定義2 N=｛n1，n2，...nm｝代表云存儲環(huán)境中的資源節(jié)點(diǎn)集合。m是節(jié)點(diǎn)數(shù)。對云存儲環(huán)境來說，ni代表ni上的數(shù)據(jù)。

定義3 B代表云存儲系統(tǒng)的帶寬矩陣。根據(jù)定義2，云存儲環(huán)境中的資源節(jié)點(diǎn)數(shù)為m，則B是一個(gè)m×m的矩陣，矩陣項(xiàng)bij為節(jié)點(diǎn)i與節(jié)點(diǎn)j之間的帶寬。由于任意兩個(gè)節(jié)點(diǎn)之間的通路可能不止一條，則帶寬一般可以有多個(gè)值，這里我們?nèi)∽钚≈导纯伞?/p>

定義4用V=［v1，v2，...vn］表示任務(wù)調(diào)度向量，即一個(gè)調(diào)度方案。對云存儲系統(tǒng)來說，vi代表第i個(gè)任務(wù)的數(shù)據(jù)由vi的值代表的資源節(jié)點(diǎn)提供，該向量的長度即單位時(shí)間內(nèi)需要調(diào)度任務(wù)的總量。用F表示任務(wù)調(diào)度向量的產(chǎn)生函數(shù)。調(diào)度向量的產(chǎn)生函數(shù)是一個(gè)任務(wù)調(diào)度的靈魂，該函數(shù)的不同直接導(dǎo)致了任務(wù)調(diào)度的效率。本文取F為蟻群算法。

定義5在云計(jì)算環(huán)境中，一般的適應(yīng)度函數(shù)均為最短完成時(shí)間（makespan），本文延用此定義。云中的適應(yīng)度函數(shù)為∶

2 蟻群算法在云存儲系統(tǒng)中的應(yīng)用

2.1 標(biāo)準(zhǔn)蟻群算法

蟻群算法（ACO）具有正反饋以及較強(qiáng)的魯棒性等特點(diǎn)，主要用于解決不同的組合優(yōu)化的問題。通過信息素的累積和更新收斂于最優(yōu)路徑，最終得到全局最優(yōu)解。

螞蟻在覓食的過程中會留下一種信息素，螞蟻利用信息素與其他螞蟻交流，找到較優(yōu)路徑。假如路徑（i，j）在t時(shí)刻信息素強(qiáng)度為，節(jié)點(diǎn)i與節(jié)點(diǎn)j的距離為Lk，螞蟻k在路徑（i，j）上釋放的信息素強(qiáng)度為信息素的揮發(fā)系數(shù)為ρ，Q為常數(shù)。則該路徑上的信息素強(qiáng)度按下式更新∶螞蟻k在t時(shí)刻從節(jié)點(diǎn)i到節(jié)點(diǎn)j的概率為∶

當(dāng)且僅當(dāng)j∈allowedk，否則t）=0。其中

allowedk為螞蟻k能夠到達(dá)的節(jié)點(diǎn)的集合；ηij為節(jié)點(diǎn)i轉(zhuǎn)移到節(jié)點(diǎn)j的期望值，即啟發(fā)式因子；α和β分別為信息素輕度與啟發(fā)式因子的重要性。

2.2 標(biāo)準(zhǔn)蟻群算法在云計(jì)算中的應(yīng)用

傳統(tǒng)的基于蟻群算法的云計(jì)算任務(wù)調(diào)度按照以上算法，跟據(jù)公式（2）和（4）初始化出任務(wù)調(diào)度解，判斷結(jié)束條件，若沒有結(jié)束則循環(huán)產(chǎn)生新的解，直至滿足結(jié)束條件。

若直接把此算法直接移植到云存儲環(huán)境中，不滿足云存儲的特殊性，即并不是每個(gè)節(jié)點(diǎn)都有任務(wù)所需的數(shù)據(jù)，會產(chǎn)生許多無效解，導(dǎo)致該算法在云存儲環(huán)境中的效率低下。

2.3 改進(jìn)蟻群算法在云存儲中的應(yīng)用

針對云存儲環(huán)境的特殊性，由于存在有些節(jié)點(diǎn)不能為任務(wù)提供數(shù)據(jù)資源，本文借鑒文獻(xiàn)［2］提出的存在矩陣（existmatrix，EM）來反映任務(wù)與資源節(jié)點(diǎn)之間的對應(yīng)關(guān)系。矩陣中的項(xiàng)代表任務(wù)i的數(shù)據(jù)在資源節(jié)點(diǎn)j中是否存在，若存在則為1，否則為0。該存在矩陣可以從云存儲的資源列表中生成。為了有效地解決PSO算法在重新產(chǎn)生解時(shí)浪費(fèi)該算法前期的優(yōu)化工作的問題，改進(jìn)蟻群算法結(jié)合其自身的特點(diǎn)，對資源節(jié)點(diǎn)內(nèi)資源是否存在的判斷放在螞蟻對下個(gè)節(jié)點(diǎn)的選擇之前，即首先判斷是否有資源，若資源不存在，則直接返回上一步，只有在資源存在的情況下才會再繼續(xù)執(zhí)行算法的跳轉(zhuǎn)部分。

在改進(jìn)蟻群算法中，將矩陣項(xiàng)eij的值賦給啟發(fā)式因子η。當(dāng)eij=0，即任務(wù)i的數(shù)據(jù)在節(jié)點(diǎn)j中不存在，此時(shí)η=0，跳轉(zhuǎn)至j節(jié)點(diǎn)的概率為∶

當(dāng)eij=1，即任務(wù)i的數(shù)據(jù)存在于節(jié)點(diǎn)中，η=1，則跳轉(zhuǎn)至j節(jié)點(diǎn)的概率為∶

云存儲中基于蟻群算法的任務(wù)調(diào)度算法過程如下∶

（1）初始化信息素的值、初始化EM矩陣、初始化帶寬b，迭代次數(shù)NC=0，設(shè)置最大迭代次數(shù)Nmax；

（2）將n個(gè)任務(wù)任意放在m個(gè)節(jié)點(diǎn)上；

（3）從帶寬矩陣得到bij，計(jì)算并保存本文的適應(yīng)度∶d

（4）通過EM矩陣判斷資源節(jié)點(diǎn)是否有請求數(shù)據(jù)，若不存在，返回步驟（3），若存在，則通過公式（6）選擇節(jié)點(diǎn)移動(dòng)，通過公式（3）對路徑上的信息素更新；

（5）NC=NC+1；

（6）若NC＜Nmax，則跳至步驟（3），若NC＜Nmax，則繼續(xù)；

（7）調(diào)度完成，輸出一個(gè)d最小的任務(wù)調(diào)度向量Vi。

3實(shí)驗(yàn)仿真及結(jié)果分析

為了驗(yàn)證算法的有效性，使用云仿真工具CloudSim進(jìn)行試驗(yàn)。在實(shí)驗(yàn)中，帶寬矩陣以及存在矩陣均由計(jì)算機(jī)隨機(jī)產(chǎn)生，并設(shè)置最大迭代次數(shù)Nmax為100，資源節(jié)點(diǎn)數(shù)量為10，初始信息素的值為5，信息素增值為1。仿真為任務(wù)數(shù)按照20、40、60、80、100遞增的情況下，依次實(shí)驗(yàn)。為避免多因素干擾，將每個(gè)實(shí)驗(yàn)執(zhí)行20次并取其均值，分析算法的性能（圖1）。

圖1將本文提出的改進(jìn)蟻群算法與文獻(xiàn)［2］提出的改進(jìn)PSO算法以及原始蟻群算法在云存儲中的適應(yīng)度的比較。仿真實(shí)驗(yàn)所得到的最小適應(yīng)度值即為最小執(zhí)行時(shí)間（makespan）。實(shí)驗(yàn)表明原始蟻群算法適應(yīng)度最大，這是因?yàn)樵枷伻核惴ㄔ谇蠼庵袝性S多的無效解。而改進(jìn)蟻群算法在云存儲中的適應(yīng)度更小，即任務(wù)總執(zhí)行時(shí)間更小，與預(yù)期結(jié)果相符。

圖2的對比中，改進(jìn)蟻群算法在云存儲中求到最優(yōu)解的迭代次數(shù)明顯比傳統(tǒng)的蟻群算法的迭代次數(shù)少很多，并隨任務(wù)數(shù)的增加越發(fā)明顯。改進(jìn)蟻群算法的收斂速度明顯優(yōu)于傳統(tǒng)蟻群算法。

4 結(jié)束語

本文研究了云存儲中的任務(wù)調(diào)度算法，發(fā)現(xiàn)云存儲中的改進(jìn)PSO任務(wù)調(diào)度算法在求解任務(wù)調(diào)度解時(shí)效率不高，因此提出了基于改進(jìn)蟻群算法的云存儲任務(wù)調(diào)度算法。該算法在適應(yīng)云存儲環(huán)境的前提下，具有收斂更快的優(yōu)勢，并通過仿真驗(yàn)證了其有效性。下一步的研究是在該算法的基礎(chǔ)上，在螞蟻信息素更新時(shí)引入用戶的QoS需求，使調(diào)度任務(wù)能在有效完成的基礎(chǔ)上最大化用戶的QoS偏好。

［1］Hayes B.Cloud computing［J］.Communications of the ACM'2008'51(7）:9-11.

［2］王娟'李飛'張路橋.限制解空間的PSO云存儲任務(wù)調(diào)度算法［J］.計(jì)算機(jī)應(yīng)用研究'2013'30(1）:127-130.

［3］張軍'胡曉明.蟻群優(yōu)化［M］.北京:清華大學(xué)出版社' 2007.

［4］Dorigo M'Caro G D.The ant colony optimizationmetaheuristic［C］//Corne D'Dorigo M'Glover F.New Ideas in Optimization.London:McGraw Hill'1999:11-32.

［5］李宗勇'彭霞'王智學(xué)'等.基于蟻群算法的參數(shù)相關(guān)網(wǎng)格任務(wù)調(diào)度算法研究［J］.系統(tǒng)仿真學(xué)報(bào)'2007'19 (14）:3196-3199.

［6］李坤.云環(huán)境下的任務(wù)調(diào)度算法研究與實(shí)現(xiàn)［D］.吉林:吉林大學(xué)'2012.

［7］Martino V D'M ililottiM.Scheduling in A Grid Computing Environment Using Genetic A lgorithms［C］//Proceedings of International Parallel and Distributed Processing Symposium'Florida'April 15-19'2002:235-239.

［8］李建鋒'彭艦.云計(jì)算環(huán)境下基于改進(jìn)遺傳算法的任務(wù)調(diào)度算法［J］.計(jì)算機(jī)應(yīng)用'2011'31(1）:184-186.

［9］王永貴'韓瑞蓮.基于改進(jìn)蟻群算法的云環(huán)境任務(wù)調(diào)度研究［J］.計(jì)算機(jī)測量與控制'2011'19(5）:1203-1211.

［10］魏東'吳良杰'佐丹'等.基于混合蟻群算法的網(wǎng)格任務(wù)調(diào)度［J］.計(jì)算機(jī)工程'2010'36(3）:215-217.

Research on Task Schedule Algorithm of Cloud Storage Based on Improved Ant Colony Algorithm

YUAN Enlong，LIFei，TANG Jitao，ZHAO Boting
（College of Network Engineering，Chengdu University of Information Technology，Chengdu 610225，China）

Due to the different between the cloud storage environment and the cloud computing environment，directly transplanting task scheduling which used in cloud computing to the cloud storage environmentwill inevitably lead to a decline in the efficiency of task scheduling.To solve this problem，an improved ant colony algorithm which is applicable to cloud storage environment is proposed.This improved ant colony algorithm ismore suitable for cloud storage environment.At the same time，there is no data resourceswhen the improved PSO algorithm is introduced inmatrix，so that awaste of early optimizing of the algorithm is produced，which causes a problem that the efficiency is very low，the problem is solved effectively. Analysis of test results shows that the improved ant colony algorithm propsed in the clord storage environment task scheduling algorithm has faster convergence rate under the premise to guarantee efficient solutions.

cloud storage；tasks scheduling；ant colony algorithm

TP393

A

1673-1549（2014）01-0041-04

10.11863/j.suse.2014.01.11

2013-09-05

四川省科技支撐項(xiàng)目（2011GZ0195）

袁恩?。?988-），男，四川成都人，碩士生，主要從事基于云存儲的計(jì)算機(jī)應(yīng)用研究方面的研究，（E-mail）yuanenlong@hotmail.com