改進蟻群算法的云存儲任務調度算法研究

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

（成都信息工程學院網絡工程學院，成都610225）

改進蟻群算法的云存儲任務調度算法研究

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

（成都信息工程學院網絡工程學院，成都610225）

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

云存儲；任務調度；蟻群算法

引言

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

目前，國內針對在網格計算以及云計算環境中的任務調度算法的研究較多，而單獨對云存儲系統的任務調度算法的研究比較少見。云存儲系統本身是由云計算系統衍生而來，但是由于其主要任務不同，云計算以及網格計算主要是針對計算型任務，任務可以被委派到任意的云節點中進行計算；而云存儲大多是數據傳輸的任務，因此在云存儲中，云中節點是否有用戶請求的數據決定了云存儲中的任務調度效率。雖然云存儲系統與云計算和網格計算大同小異，畢竟云存儲也是一個特殊的云系統，因此我們可以在借鑒前人的任務調度算法的同時應該做出適當的改進以適應云存儲環境的特點。

在已有的對云存儲的任務調度算法的研究中，文獻［2］引入了存在矩陣以適應云存儲的特點，但該文獻使用的是PSO任務調度算法。在PSO算法中引入存在矩陣會使其收斂效率低下，這是因為若存在矩陣中的矩陣項為0時，粒子前期的飛行計算就會被完全拋棄，浪費了時間與資源。本文研究云存儲的任務調度算法，以相對成熟且被廣泛應用的蟻群算法為算法基礎，沿用文獻［2］提出的存在矩陣，根據云存儲環境的特點對其進行改進。由于蟻群在更新信息素之前可以通過存在矩陣判斷出資源節點中是否有請求資源，因此在效率方面，蟻群算法［3-5］更加符合云存儲環境。實驗證明，改進之后的算法不僅能提高原始算法在云存儲環境中的有效解，節省大量時間；同時，改進蟻群算法在效率上也比改進PSO算法的效率要高。

1 云存儲任務調度的抽象

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

定義1 T=｛t1，t2，...tn｝代表單位時間內等待調度的任務集。n是任務數。

定義2 N=｛n1，n2，...nm｝代表云存儲環境中的資源節點集合。m是節點數。對云存儲環境來說，ni代表ni上的數據。

定義3 B代表云存儲系統的帶寬矩陣。根據定義2，云存儲環境中的資源節點數為m，則B是一個m×m的矩陣，矩陣項bij為節點i與節點j之間的帶寬。由于任意兩個節點之間的通路可能不止一條，則帶寬一般可以有多個值，這里我們取最小值即可。

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

定義5在云計算環境中，一般的適應度函數均為最短完成時間（makespan），本文延用此定義。云中的適應度函數為∶

2 蟻群算法在云存儲系統中的應用

2.1 標準蟻群算法

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

螞蟻在覓食的過程中會留下一種信息素，螞蟻利用信息素與其他螞蟻交流，找到較優路徑。假如路徑（i，j）在t時刻信息素強度為，節點i與節點j的距離為Lk，螞蟻k在路徑（i，j）上釋放的信息素強度為信息素的揮發系數為ρ，Q為常數。則該路徑上的信息素強度按下式更新∶螞蟻k在t時刻從節點i到節點j的概率為∶

當且僅當j∈allowedk，否則t）=0。其中

allowedk為螞蟻k能夠到達的節點的集合；ηij為節點i轉移到節點j的期望值，即啟發式因子；α和β分別為信息素輕度與啟發式因子的重要性。

2.2 標準蟻群算法在云計算中的應用

傳統的基于蟻群算法的云計算任務調度按照以上算法，跟據公式（2）和（4）初始化出任務調度解，判斷結束條件，若沒有結束則循環產生新的解，直至滿足結束條件。

若直接把此算法直接移植到云存儲環境中，不滿足云存儲的特殊性，即并不是每個節點都有任務所需的數據，會產生許多無效解，導致該算法在云存儲環境中的效率低下。

2.3 改進蟻群算法在云存儲中的應用

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

在改進蟻群算法中，將矩陣項eij的值賦給啟發式因子η。當eij=0，即任務i的數據在節點j中不存在，此時η=0，跳轉至j節點的概率為∶

當eij=1，即任務i的數據存在于節點中，η=1，則跳轉至j節點的概率為∶

云存儲中基于蟻群算法的任務調度算法過程如下∶

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

（2）將n個任務任意放在m個節點上；

（3）從帶寬矩陣得到bij，計算并保存本文的適應度∶d

（4）通過EM矩陣判斷資源節點是否有請求數據，若不存在，返回步驟（3），若存在，則通過公式（6）選擇節點移動，通過公式（3）對路徑上的信息素更新；

（5）NC=NC+1；

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

（7）調度完成，輸出一個d最小的任務調度向量Vi。

3實驗仿真及結果分析

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

圖1將本文提出的改進蟻群算法與文獻［2］提出的改進PSO算法以及原始蟻群算法在云存儲中的適應度的比較。仿真實驗所得到的最小適應度值即為最小執行時間（makespan）。實驗表明原始蟻群算法適應度最大，這是因為原始蟻群算法在求解中會有許多的無效解。而改進蟻群算法在云存儲中的適應度更小，即任務總執行時間更小，與預期結果相符。

圖2的對比中，改進蟻群算法在云存儲中求到最優解的迭代次數明顯比傳統的蟻群算法的迭代次數少很多，并隨任務數的增加越發明顯。改進蟻群算法的收斂速度明顯優于傳統蟻群算法。

4 結束語

本文研究了云存儲中的任務調度算法，發現云存儲中的改進PSO任務調度算法在求解任務調度解時效率不高，因此提出了基于改進蟻群算法的云存儲任務調度算法。該算法在適應云存儲環境的前提下，具有收斂更快的優勢，并通過仿真驗證了其有效性。下一步的研究是在該算法的基礎上，在螞蟻信息素更新時引入用戶的QoS需求，使調度任務能在有效完成的基礎上最大化用戶的QoS偏好。

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

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

［3］張軍'胡曉明.蟻群優化［M］.北京:清華大學出版社' 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］李宗勇'彭霞'王智學'等.基于蟻群算法的參數相關網格任務調度算法研究［J］.系統仿真學報'2007'19 (14）:3196-3199.

［6］李坤.云環境下的任務調度算法研究與實現［D］.吉林:吉林大學'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］.計算機應用'2011'31(1）:184-186.

［9］王永貴'韓瑞蓮.基于改進蟻群算法的云環境任務調度研究［J］.計算機測量與控制'2011'19(5）:1203-1211.

［10］魏東'吳良杰'佐丹'等.基于混合蟻群算法的網格任務調度［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

四川省科技支撐項目（2011GZ0195）

袁恩隆（1988-），男，四川成都人，碩士生，主要從事基于云存儲的計算機應用研究方面的研究，（E-mail）yuanenlong@hotmail.com