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

段效琛， 李英娜， 賈會(huì)玲， 趙振剛， 李 川

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

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

段效琛， 李英娜， 賈會(huì)玲， 趙振剛， 李 川

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

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

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

0 引 言

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

本文提出并實(shí)現(xiàn)了一種Hadoop分布式文件系統(tǒng)(HDFS)環(huán)境下的基于初始信息篩選的蟻群算法的副本選擇策略，經(jīng)過(guò)仿真驗(yàn)證，結(jié)果表明基于初始信息素篩選的ACO(InitPh_ACO)策略在作業(yè)執(zhí)行時(shí)間、副本讀取響應(yīng)時(shí)間和副本負(fù)載均衡性3個(gè)方面的性能均優(yōu)于ACO策略和GA策略。

1 基本原理

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

2 算法設(shè)計(jì)

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

(1)

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

本文采用ACO算法設(shè)計(jì)出一種Hadoop集群環(huán)境下的副本選擇策略，對(duì)于客戶端來(lái)說(shuō)，信息素濃度越高副本越佳。副本的信息素濃度會(huì)隨著情況的不同做出相應(yīng)的改變，變化規(guī)律如下

Tnewi=ρ·Toldi+ΔTi

(2)

當(dāng)副本的信息素濃度有所改變時(shí)，該副本被選擇的概率也會(huì)隨之增減，可利用式(3)計(jì)算每一個(gè)副本被選擇的概率

(3)

式中 Ti(t)為副本所在節(jié)點(diǎn)i的當(dāng)前信息素濃度；ηi為該節(jié)點(diǎn)的初始信息素濃度，α和β的值均設(shè)定為0.5。

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

(4)

式中 f,fmax分別為訪問(wèn)同一個(gè)數(shù)據(jù)節(jié)點(diǎn)上的相同數(shù)據(jù)副本的任務(wù)的個(gè)數(shù)和最大個(gè)數(shù)。

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

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

3 副本選擇策略仿真與評(píng)估

為了驗(yàn)證基于初始信息素篩選的ACO算法在HDFS中進(jìn)行副本選擇中的可行性和有效性，本文選用cloudsim-3.0作為仿真工具。仿真實(shí)驗(yàn)通過(guò)比較基于ACO算法的副本選擇策略、基于GA的副本選擇策略和本文提出的基于初始信息素篩選的ACO算法的副本選擇策略來(lái)驗(yàn)證InitPh_ACO策略的有效性。

云應(yīng)用程序在CloudSim 中仿真的流程如圖2所示。

圖2 CloudSim的仿真流程圖

實(shí)驗(yàn)環(huán)境模擬客戶端的訪問(wèn)請(qǐng)求是隨機(jī)的，并且有100個(gè)存儲(chǔ)能力均為90 GB的數(shù)據(jù)節(jié)點(diǎn)，網(wǎng)絡(luò)帶寬為1 000 Mbps，副本所在的數(shù)據(jù)節(jié)點(diǎn)的CPU、帶寬、內(nèi)存等資源的使用率通過(guò)隨機(jī)函數(shù)獲取，隨機(jī)函數(shù)產(chǎn)生的數(shù)據(jù)為[0，1]之間的隨機(jī)數(shù)。文件大小為128 MB。此外，數(shù)據(jù)塊大小為64 MB，且副本數(shù)目為3。

圖3所示的為本文所提出的InitPh_ACO策略與ACO策略、GA策略的作業(yè)執(zhí)行時(shí)間對(duì)比圖，作業(yè)的執(zhí)行時(shí)間為當(dāng)前作業(yè)數(shù)量下進(jìn)行100次實(shí)驗(yàn)所得的作業(yè)執(zhí)行時(shí)間的均值。

圖3 作業(yè)執(zhí)行時(shí)間對(duì)比圖

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

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

圖4 副本讀取響應(yīng)時(shí)間變化圖

從圖4可以看出，采用InitPh_ACO策略的響應(yīng)時(shí)間在讀取操作的初始階段的響應(yīng)時(shí)間略微比其他兩種策略的響應(yīng)時(shí)間低些，但隨著客戶端對(duì)副本讀取請(qǐng)求的增加，其響應(yīng)時(shí)間基本趨于穩(wěn)定，且顯著比其他兩種策略的響應(yīng)時(shí)間短。因此，在系統(tǒng)可用性方面，InitPh_ACO策略比其他兩種策略更有優(yōu)勢(shì)。

副本的負(fù)載是指副本所在的Datanode 接收客戶端讀取請(qǐng)求的次數(shù)，每隔10 min記錄一次某個(gè)數(shù)據(jù)塊的3個(gè)副本所在的DataNode節(jié)點(diǎn)在該10 min內(nèi)的負(fù)載總量。測(cè)試2 h后，圖5、圖6、圖7分別表示采用ACO策略、GA策略、InitPh_ACO策略的副本節(jié)點(diǎn)負(fù)載變化情況。再將100個(gè)數(shù)據(jù)節(jié)點(diǎn)的負(fù)載標(biāo)準(zhǔn)差作為系統(tǒng)負(fù)載均衡性評(píng)估的標(biāo)準(zhǔn)，每個(gè)作業(yè)數(shù)量所對(duì)應(yīng)的負(fù)載標(biāo)準(zhǔn)差，是通過(guò)對(duì)100個(gè)數(shù)據(jù)節(jié)點(diǎn)進(jìn)行反復(fù)測(cè)試100次所得副本負(fù)載標(biāo)準(zhǔn)差均值，然后通過(guò)計(jì)算獲得全部的標(biāo)準(zhǔn)差均值，仿真結(jié)果如圖8所示，為截取第100～1 000次作業(yè)區(qū)間的副本負(fù)載標(biāo)準(zhǔn)差曲線。

圖5 采用ACO策略時(shí)副本負(fù)載情況

圖6 采用GA策略時(shí)副本負(fù)載情況

圖7 采用InitPh_ACO策略時(shí)副本負(fù)載情況

圖8 副本負(fù)載標(biāo)準(zhǔn)差

從圖8可以看出，采用ACO策略時(shí)副本的負(fù)載標(biāo)準(zhǔn)差在32～47.7范圍內(nèi)波動(dòng)，副本的負(fù)載標(biāo)準(zhǔn)差均值為38.216；采用GA策略時(shí)副本的負(fù)載標(biāo)準(zhǔn)差在25.0～56.0范圍內(nèi)波動(dòng)，副本負(fù)載標(biāo)準(zhǔn)差均值為42.6；而采用InitPh_ACO策略時(shí)副本的負(fù)載標(biāo)準(zhǔn)差在13.1～19.5范圍內(nèi)波動(dòng)，副本負(fù)載標(biāo)準(zhǔn)差均值為16.121。由此可見(jiàn)，采用ACO策略和GA策略時(shí)副本負(fù)載標(biāo)準(zhǔn)差均值較大，且波動(dòng)比較大，本文所提出的InitPh_ACO策略的副本標(biāo)準(zhǔn)差均值最小，且波動(dòng)范圍比較小。綜合圖5～圖7的仿真結(jié)果可知，本文提出的InitPh_ACO策略在保持副本負(fù)載均衡性方面優(yōu)于其他2種算法。

由以上3種算法的仿真結(jié)果可以看出：基于初始信息素篩選的ACO算法的副本選擇策略在作業(yè)執(zhí)行時(shí)間、系統(tǒng)可用性和負(fù)載平衡性等方面均具有顯著的優(yōu)勢(shì)。

4 結(jié) 論

本文通過(guò)對(duì)ACO算法的副本選擇策略和GA的選擇策略進(jìn)行比較分析，提出了初始信息素篩選的ACO算法的HDFS副本選擇模型。并使用云計(jì)算仿真工具CloudSim驗(yàn)證該策略的效果，仿真結(jié)果證明：ACO策略、GA策略的副本選擇性能相近，而新提出的InitPh_ACO策略在作業(yè)執(zhí)行時(shí)間、副本讀取響應(yīng)時(shí)間和副本負(fù)載均衡性三個(gè)方面的性能均優(yōu)于ACO策略和GA策略，初始信息素篩選的蟻群算法可以較為迅速地獲得最佳副本，提高了系統(tǒng)的負(fù)載均衡性，增強(qiáng)了系統(tǒng)的整體性能。

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

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

[3] 張 雨，李 芳，周 濤．云計(jì)算環(huán)境下基于遺傳蟻群算法的任務(wù)調(diào)度研究[J]．計(jì)算機(jī)工程與應(yīng)用,2014，50(6)：51-55.

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

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

[6] 左 方，何 欣．一種基于蟻群算法的云存儲(chǔ)副本動(dòng)態(tài)選擇機(jī)制研究[J]．計(jì)算機(jī)應(yīng)用研究，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] 蔣麗麗,陳國(guó)彬,張廣泉,等.基于蟻群算法優(yōu)化SA的WMN路由設(shè)計(jì)與仿真[J].傳感器與微系統(tǒng),2015,34(5):112-114,126.

[9] 柏小虎．云環(huán)境下基于用戶請(qǐng)求響應(yīng)時(shí)間的副本管理策略研究[D] ．武漢：華中科技大學(xué)，2013.

[10] 張寧寧．異構(gòu)環(huán)境下云計(jì)算數(shù)據(jù)副本動(dòng)態(tài)管理研究[D]．鄭州：鄭州大學(xué)，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

國(guó)家自然科學(xué)基金資助項(xiàng)目(51567013)

TP 391

A

1000—9787(2017)04—0031—03

段效琛(1990-)，女，碩士研究生，主要研究方向?yàn)樽儔浩骷肮饫w光柵傳感領(lǐng)域的研究。

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