初始信息素篩選的蟻群優化算法在HDFS副本選擇中的研究*

段效琛， 李英娜， 賈會玲， 趙振剛， 李 川

(昆明理工大學 信息工程與自動化學院，云南 昆明 650500)

初始信息素篩選的蟻群優化算法在HDFS副本選擇中的研究*

段效琛， 李英娜， 賈會玲， 趙振剛， 李 川

(昆明理工大學 信息工程與自動化學院，云南 昆明 650500)

隨著社會信息化程度的不斷提高，各種形式的數據急劇膨脹。HDFS成為解決海量數據存儲問題的一個分布式文件系統，而副本技術是云存儲系統的關鍵。提出了一種基于初始信息素篩選的蟻群優化算法(InitPh_ACO)的副本選擇策略，通過將遺傳算法(GA)與蟻群優化算法(ACO)算法相結合，將它們進行動態銜接。提出基于初始信息素篩選的ACO算法，既克服了ACO算法初始搜索速度慢，又充分利用GA的快速隨機全局搜索能力。利用云計算仿真工具CloudSim來驗證此策略的效果，結果表明：InitPh_ACO策略在作業執行時間、副本讀取響應時間和副本負載均衡性三個方面的性能均優于基于ACO算法的副本選擇策略和基于GA的副本選擇策略。

Hadoop分布式文件系統(HDFS); 副本選擇; 初始信息素篩選; 蟻群優化算法; 遺傳算法

0 引 言

副本技術是云存儲系統中的關鍵技術，它能大大減少傳輸延遲，提高數據訪問和處理效率[1]。2012年，徐驍勇等人針對現有的副本選擇策略無法根據環境的變化選擇最合適副本這一問題，提出了一種綜合考慮網絡帶寬、節點I/O性能以及節點存儲空間等因素，基于灰色馬爾可夫鏈預測模型的副本選擇策略，以此在系統可用性和負載均衡性之間尋求一個平衡[2]。2015年，張雨等人針對云計算的編程模型框架，提出了一種融合遺傳算法(GA)與蟻群優化(ant colony optimization,ACO)算法的混合調度算法，經實驗證明，此算法是一種云計算環境下有效的任務調度算法[3]。

本文提出并實現了一種Hadoop分布式文件系統(HDFS)環境下的基于初始信息篩選的蟻群算法的副本選擇策略，經過仿真驗證，結果表明基于初始信息素篩選的ACO(InitPh_ACO)策略在作業執行時間、副本讀取響應時間和副本負載均衡性3個方面的性能均優于ACO策略和GA策略。

1 基本原理

本文將GA與ACO算法兩種算法結合使用，利用GA獲得較優解組合，然后將其用于信息素的初始化工作，最后通過ACO算法獲得最優解。這樣使其求解最優解的效率優于GA，時間效率也好于ACO算法。而GA和ACO算法的銜接時間點變得尤為重要，本文參考了一種動態銜接方法，保證GA與ACO算法能夠在最佳時間點進行銜接。具體實現方法如下：首先在GA中設定最大遺傳迭代次數Genemax和最小遺傳迭代次數Genemin；然后設定子代群體的最小進化率Genemin-impro-ratio，并在GA迭代的過程中統計子代群體的進化率；最后判斷在設置的迭代次數的范圍內，若GA連續迭代Genedie次，子代群體的進化率均小于最小進化率Genemin-impro-ratio，則表明GA在此時向最優解收斂的速度比較緩慢，此刻即是兩種算法進行銜接的最佳時機。因此，可在此時結束GA的運行，開始ACO算法的相關操作；若迭代次數達到最大遺傳迭代次數Genemax，則可在此時結束GA的運行，開始ACO算法的相關操作。

2 算法設計

GA運行終止后，獲得若干組優化解，將該算法求解出的最優解用于信息素的初始化操作。采用GA獲得了一些路徑上的信息素濃度，故這里把信息素濃度初始化為

(1)

式中 Tj(O)為初始信息素濃度，Filesize為副本大小，r為磁盤的讀取速度,TG為由遺傳算法求解出的最優解所轉換的信息素值，這里，TG=αf1(x)+(1-α)f3(x)。

本文采用ACO算法設計出一種Hadoop集群環境下的副本選擇策略，對于客戶端來說，信息素濃度越高副本越佳。副本的信息素濃度會隨著情況的不同做出相應的改變，變化規律如下

Tnewi=ρ·Toldi+ΔTi

(2)

當副本的信息素濃度有所改變時，該副本被選擇的概率也會隨之增減，可利用式(3)計算每一個副本被選擇的概率

(3)

式中 Ti(t)為副本所在節點i的當前信息素濃度；ηi為該節點的初始信息素濃度，α和β的值均設定為0.5。

為了使副本節點的負載情況保持平衡，這里將式(3)計算出的選擇概率與該副本所在節點的負載完成率進行結合運算，使得每次被選中的副本節點不一定是選擇概率最大的節點

(4)

式中 f,fmax分別為訪問同一個數據節點上的相同數據副本的任務的個數和最大個數。

基于初始信息素篩選的ACO算法的副本選擇流程圖如圖1所示。

圖1 基于初始信息素篩選的ACO算法的副本選擇流程圖

3 副本選擇策略仿真與評估

為了驗證基于初始信息素篩選的ACO算法在HDFS中進行副本選擇中的可行性和有效性，本文選用cloudsim-3.0作為仿真工具。仿真實驗通過比較基于ACO算法的副本選擇策略、基于GA的副本選擇策略和本文提出的基于初始信息素篩選的ACO算法的副本選擇策略來驗證InitPh_ACO策略的有效性。

云應用程序在CloudSim 中仿真的流程如圖2所示。

圖2 CloudSim的仿真流程圖

實驗環境模擬客戶端的訪問請求是隨機的，并且有100個存儲能力均為90 GB的數據節點，網絡帶寬為1 000 Mbps，副本所在的數據節點的CPU、帶寬、內存等資源的使用率通過隨機函數獲取，隨機函數產生的數據為[0，1]之間的隨機數。文件大小為128 MB。此外，數據塊大小為64 MB，且副本數目為3。

圖3所示的為本文所提出的InitPh_ACO策略與ACO策略、GA策略的作業執行時間對比圖，作業的執行時間為當前作業數量下進行100次實驗所得的作業執行時間的均值。

圖3 作業執行時間對比圖

從圖3中可以看出，本文所提出的InitPh_ACO策略在作業執行時間上都優于其他兩種副本選擇策略，故本文所提出的InitPh_ACO策略在作業執行時間上性能更佳。

圖4為某一客戶端在本文所提出的InitPh_ACO策略、ACO策略和GA策略的副本讀取響應時間方面的變化圖。

圖4 副本讀取響應時間變化圖

從圖4可以看出，采用InitPh_ACO策略的響應時間在讀取操作的初始階段的響應時間略微比其他兩種策略的響應時間低些，但隨著客戶端對副本讀取請求的增加，其響應時間基本趨于穩定，且顯著比其他兩種策略的響應時間短。因此，在系統可用性方面，InitPh_ACO策略比其他兩種策略更有優勢。

副本的負載是指副本所在的Datanode 接收客戶端讀取請求的次數，每隔10 min記錄一次某個數據塊的3個副本所在的DataNode節點在該10 min內的負載總量。測試2 h后，圖5、圖6、圖7分別表示采用ACO策略、GA策略、InitPh_ACO策略的副本節點負載變化情況。再將100個數據節點的負載標準差作為系統負載均衡性評估的標準，每個作業數量所對應的負載標準差，是通過對100個數據節點進行反復測試100次所得副本負載標準差均值，然后通過計算獲得全部的標準差均值，仿真結果如圖8所示，為截取第100～1 000次作業區間的副本負載標準差曲線。

圖5 采用ACO策略時副本負載情況

圖6 采用GA策略時副本負載情況

圖7 采用InitPh_ACO策略時副本負載情況

圖8 副本負載標準差

從圖8可以看出，采用ACO策略時副本的負載標準差在32～47.7范圍內波動，副本的負載標準差均值為38.216；采用GA策略時副本的負載標準差在25.0～56.0范圍內波動，副本負載標準差均值為42.6；而采用InitPh_ACO策略時副本的負載標準差在13.1～19.5范圍內波動，副本負載標準差均值為16.121。由此可見，采用ACO策略和GA策略時副本負載標準差均值較大，且波動比較大，本文所提出的InitPh_ACO策略的副本標準差均值最小，且波動范圍比較小。綜合圖5～圖7的仿真結果可知，本文提出的InitPh_ACO策略在保持副本負載均衡性方面優于其他2種算法。

由以上3種算法的仿真結果可以看出：基于初始信息素篩選的ACO算法的副本選擇策略在作業執行時間、系統可用性和負載平衡性等方面均具有顯著的優勢。

4 結 論

本文通過對ACO算法的副本選擇策略和GA的選擇策略進行比較分析，提出了初始信息素篩選的ACO算法的HDFS副本選擇模型。并使用云計算仿真工具CloudSim驗證該策略的效果，仿真結果證明：ACO策略、GA策略的副本選擇性能相近，而新提出的InitPh_ACO策略在作業執行時間、副本讀取響應時間和副本負載均衡性三個方面的性能均優于ACO策略和GA策略，初始信息素篩選的蟻群算法可以較為迅速地獲得最佳副本，提高了系統的負載均衡性，增強了系統的整體性能。

[1] 張繼平．云存儲解析[M]．北京：人民郵電出版社，2013.

[2] 徐驍勇，潘 郁，丁燕艷．基于灰色馬爾可夫鏈預測模型的HDFS云存儲副本選擇策略[J] ．計算機應用， 2012，31(A02)：39-42.

[3] 張 雨，李 芳，周 濤．云計算環境下基于遺傳蟻群算法的任務調度研究[J]．計算機工程與應用,2014，50(6)：51-55.

[4] 多傳感器數據融合技術研究進展[J].傳感器與微系統,2010,29(3):5-8,12.

[5] 樊寬剛,么曉康,蘇建華，等.基于蟻群算法的WSNs節點有障環境中部署優化研究[J].傳感器與微系統,2015,34(5):29-32,37.

[6] 左 方，何 欣．一種基于蟻群算法的云存儲副本動態選擇機制研究[J]．計算機應用研究，2015，32(11)：3368-3370，3374.

[7] Zhong H，Zhang Z，Zhang X．A dynamic replica management strategy based on data grid[C]∥The 9th International Confe-rence on Grid and Cooperative Computing,Najing，China：IEEE，2010:18-23.

[8] 蔣麗麗,陳國彬,張廣泉,等.基于蟻群算法優化SA的WMN路由設計與仿真[J].傳感器與微系統,2015,34(5):112-114,126.

[9] 柏小虎．云環境下基于用戶請求響應時間的副本管理策略研究[D] ．武漢：華中科技大學，2013.

[10] 張寧寧．異構環境下云計算數據副本動態管理研究[D]．鄭州：鄭州大學，2013.

Research on ACO algorithm initial pheromone screening in HDFS copy selection*

DUAN Xiao-chen, LI Ying-na, JIA Hui-ling, ZHAO Zhen-gang, LI Chuan

(Faculty of Information Engineering and Automation,Kunming University of Science and Technology,Kunming 650500,China)

With the degree of social information continues to improve,various forms of data expand rapidly.Hadoop distributed file system(HDFS)has become a distributed file system solving mass data storage problem,and a copy of the technical is the key of cloud storage system.Present a copy selection strategy foundation on ant colony optimization algorithm based on initial pheromone screening(InitPh_ACO)strategy,by combining genetic algorithm (GA) and ant colony algorithm,link them dynamically and propose ant colony algorithm based on initial screening of pheromone.This algorithm not only overcome shortage of slow initial search of ant colony algorithm,and make full use of fast stochastic global search capability of GA.Using cloud computing simulation tools CloudSim to verify the effect of this strategy,the results show that InitPh_ACO strategy are prior to the selection strategy replica ACO strategy algorithm and a copy of the selection strategy based on GA policy in three aspects of performance which are job execution time,response time and the copy of load balancing.

hadoop distributed file system(HDFS); replica selection; initial pheromone screening; ant colony optimization(ACO)algorithm； genetic algorithm(GA)

10.13873/J.1000—9787(2017)04—0031—03

2016—04—28

國家自然科學基金資助項目(51567013)

TP 391

A

1000—9787(2017)04—0031—03

段效琛(1990-)，女，碩士研究生，主要研究方向為變壓器及光纖光柵傳感領域的研究。

李 川(1971-)，男，通訊作者，教授，博士生導師，從事光纖Bragg光柵傳感器的應用研究工作,E—mail:boatriver@eyou,com。