袁赫潞,溫長吉,2,吳建雙,朱允剛,于合龍,2

(1.吉林農(nóng)業(yè)大學(xué) 信息技術(shù)學(xué)院,長春 130118;2.吉林省精準(zhǔn)農(nóng)業(yè)與大數(shù)據(jù)工程研究中心,長春 130118;3.吉林大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,長春 130012)

信息時代,云計(jì)算技術(shù)能實(shí)現(xiàn)其強(qiáng)大的資源配置功能,其核心技術(shù)是通過負(fù)載均衡策略層收集量化信息,并根據(jù)負(fù)載均衡策略完成分配任務(wù).在目前的拓?fù)渚W(wǎng)絡(luò)下,負(fù)載均衡提供了一種廉價且透明有效的方法,擴(kuò)展網(wǎng)絡(luò)設(shè)備和服務(wù)器的帶寬、增加吞吐量、加強(qiáng)網(wǎng)絡(luò)數(shù)據(jù)處理能力、提高網(wǎng)絡(luò)的靈活性和可用性.

早期集中式負(fù)載均衡方法具有部署簡單、高效且平臺易維護(hù)的特點(diǎn)[1].但當(dāng)面對高峰用戶訪問量和任務(wù)數(shù)量過多時,中心管理服務(wù)器將會面臨單點(diǎn)失效的瓶頸[2].針對上述問題,分布式負(fù)載均衡具有不設(shè)中心控制服務(wù)器,即每個服務(wù)器都參與任務(wù)調(diào)度和分配,因此具有較好的拓展性.分布式負(fù)載均衡如何優(yōu)化平臺資源配置,提升資源能耗利用率是研究的關(guān)鍵問題之一,代表性工作包括傳統(tǒng)優(yōu)化調(diào)度模型和基于群智能算法.Bittencourt等[3]提出了一種基于博弈論的分布式負(fù)載均衡算法,網(wǎng)絡(luò)服務(wù)器之間通過博弈相互轉(zhuǎn)嫁負(fù)載使自己的負(fù)載最小化,從而使系統(tǒng)達(dá)到均衡實(shí)現(xiàn)最優(yōu)的負(fù)載均衡；文獻(xiàn)[4]提出了一種優(yōu)化配置模型,該模型通過計(jì)算不同工作負(fù)載下關(guān)于服務(wù)器的功耗運(yùn)行動態(tài)優(yōu)化管理,進(jìn)而有效減少基礎(chǔ)資源的能源消耗并增加能源的應(yīng)用效率；文獻(xiàn)[5]提出了通過WiFi接入點(diǎn)把卸載任務(wù)給云的一種節(jié)能調(diào)度模型,在總完工時間的約束下得到了最少設(shè)備的消耗；文獻(xiàn)[6]提出了一種引入局部搜索算子提高搜索能力和加速收斂速度的改進(jìn)遺傳算法模型,實(shí)現(xiàn)了節(jié)能任務(wù)調(diào)度;文獻(xiàn)[7]提出了利用人工蜂群算法解決負(fù)載均衡問題,并設(shè)計(jì)了新的問題模型；Kechagiopoulos等[8]提出了基于粒子群優(yōu)化算法；Nayeem等[9]提出了基于精英策略的遺傳算法負(fù)載均衡設(shè)計(jì)方案.

珊瑚礁優(yōu)化(coral reef optimization,CRO)算法[10]是一種模擬珊瑚蟲群體行為和珊瑚礁組成的智能優(yōu)化算法,通過珊瑚蟲種群的繁殖、競爭、淘汰等環(huán)節(jié)實(shí)現(xiàn)優(yōu)化.珊瑚礁優(yōu)化算法中的有性和無性繁殖,以及毀滅機(jī)制實(shí)現(xiàn)信息的種群間共享機(jī)制,增強(qiáng)全局搜索能力.文獻(xiàn)[11]運(yùn)用珊瑚礁優(yōu)化算法得到了較客觀的效果.針對無線接入網(wǎng)的分布問題,文獻(xiàn)[12]證明了珊瑚礁優(yōu)化算法在實(shí)際應(yīng)用中具有較強(qiáng)解決問題的能力.但目前基本珊瑚礁優(yōu)化算法仍存在缺陷,如在繁殖過程中種群多樣性受限,搜索精度偏低,易陷入局部最優(yōu)解等.針對上述問題,本文提出一種改進(jìn)的珊瑚礁優(yōu)化算法----遺傳珊瑚礁優(yōu)化算法(cenetic algorithm and coral reef optimization,GACRO),即在珊瑚蟲的每次進(jìn)化過程中,將遺傳算法中的交叉和變異算子引入到珊瑚礁優(yōu)化算法的種群進(jìn)化迭代中,在保留基本珊瑚礁優(yōu)化算法中每個珊瑚蟲信息共享機(jī)制的同時,有效提升全局搜索能力,增加種群多樣性,提升算法的優(yōu)化性能,避免算法過早陷入局部最優(yōu)的問題,并將改進(jìn)的遺傳珊瑚礁優(yōu)化算法應(yīng)用于負(fù)載均衡中.

1 相關(guān)理論及問題描述

1.1 算法簡介

遺傳算法(GA)是模擬生物進(jìn)化論中自然選擇和遺傳學(xué)機(jī)理的生物進(jìn)化過程計(jì)算模型,其通過對問題所屬解空間中的解向量進(jìn)行編碼,利用生成的染色體建立初始種群,通過選擇、交叉和變異等操作從適應(yīng)度函數(shù)中選出優(yōu)秀個體,進(jìn)而實(shí)現(xiàn)問題尋優(yōu).

珊瑚礁優(yōu)化算法(CRO)是一種模擬珊瑚蟲群體行為和珊瑚礁組成的智能優(yōu)化算法.珊瑚蟲種群的進(jìn)化行為分為繁殖、競爭、淘汰等階段.繁殖行為又可分為外部有性繁殖、內(nèi)部有性繁殖和無性繁殖.首先將珊瑚礁記為Am×n,外部有性繁殖概率記為Pb,內(nèi)部有性繁殖概率記為1-Pb,死亡概率記為Pd,無性繁殖概率記為Pa,且Pa=Pd[13]；然后進(jìn)行外部有性繁殖和內(nèi)部有性繁殖,若在迭代次數(shù)(步長K)內(nèi)未被選擇則會被釋放到水中,根據(jù)適應(yīng)度函數(shù)對計(jì)算珊瑚蟲的健康值進(jìn)行排序并進(jìn)行幼蟲安置；進(jìn)行無性繁殖時,在礁上所有的珊瑚蟲都會通過健康值進(jìn)行水平排序,根據(jù)概率Pa進(jìn)行復(fù)制并再次排序,若礁上存在一些不健康的珊瑚蟲則為死亡概率.一系列操作完成則表示一次迭代完成,若符合算法的終止條件則輸出,若不符合算法的終止條件則需進(jìn)行第二次迭代,直至滿足算法的終止條件為止,輸出最優(yōu)解.珊瑚礁優(yōu)化算法流程如圖1所示.

圖1 珊瑚礁優(yōu)化算法流程Fig.1 Flow chart of CRO algorithm

1.2 遺傳珊瑚礁優(yōu)化算法

1.2.1 算法設(shè)計(jì) 遺傳珊瑚礁優(yōu)化算法基本思想為: 在每次種群進(jìn)化過程中,由基本珊瑚礁優(yōu)化算法進(jìn)化獲得的珊瑚蟲種群并不直接進(jìn)入下一次迭代操作,而是在進(jìn)入下一次迭代前對種群中的每個珊瑚蟲進(jìn)行選擇、變異和交叉等一系列操作后得到新的種群.設(shè)第t代種群記為S1,依次進(jìn)行珊瑚礁有性繁殖,判斷K步內(nèi)是否選擇到雙親,如果無雙親則進(jìn)行內(nèi)部有性繁殖,在K步長內(nèi)選擇母珊瑚蟲,否則將其釋放到水中.之后對幼蟲進(jìn)行安置,通過適應(yīng)度函數(shù)計(jì)算健康值,再進(jìn)行無性繁殖,對健康值高低進(jìn)行排序,此時進(jìn)行遺傳算法中的選擇、交叉、變異操作,形成種群S2,再對新種群S2進(jìn)行幼蟲安置,判斷是否為最優(yōu)值進(jìn)行輸入,否則將進(jìn)入毀滅機(jī)制.遺傳珊瑚礁優(yōu)化算法執(zhí)行步驟如下：

1) 初始化GACRO算法的各參數(shù)，初始化種群S1；

2) 種群S1進(jìn)行外部有性繁殖,根據(jù)概率Pb選擇雙親；

3) 若K步長內(nèi)選擇雙親,則執(zhí)行步驟6),K步長內(nèi)未選擇雙親,則執(zhí)行步驟4)；

4) 內(nèi)部有性繁殖,根據(jù)概率(1-Pb)選擇母珊瑚蟲；

5) 若K步長內(nèi)選擇母珊瑚蟲，則執(zhí)行步驟6),K步長內(nèi)未選擇母珊瑚蟲則將其釋放到水中；

6) 進(jìn)行幼蟲安置,根據(jù)適應(yīng)度函數(shù)計(jì)算健康值并進(jìn)行排序；

7) 無性繁殖,根據(jù)概率Pd進(jìn)行復(fù)制,并重復(fù)步驟8)進(jìn)行幼蟲安置,形成種群S2；

8) 利用遺傳算法對新珊瑚蟲種群進(jìn)行選擇操作,選擇操作后的珊瑚蟲種群S2中的珊瑚蟲xi,被選中概率為P(xi),在S2中選出一個珊瑚蟲進(jìn)行復(fù)制操作,共進(jìn)行M次,復(fù)制產(chǎn)生的M個珊瑚蟲成為種群S3；

9) 利用遺傳算法對種群S3進(jìn)行交叉操作,交叉概率為Pc,在種群S3中隨機(jī)選出c個珊瑚蟲進(jìn)行交叉操作,通過交叉操作隨機(jī)交換兩個珊瑚蟲某些基因,產(chǎn)生新基因組合,用S4替代S3；

10) 利用遺傳算法對S4進(jìn)行變異操作,確定變異數(shù)m,在種群S4中隨機(jī)選取m個珊瑚蟲變異,新的種群S5代替S4,成為新一代種群；

11) 重復(fù)步驟6),根據(jù)健康值進(jìn)行排序；

12) 判斷是否為最優(yōu)值,若不是則將進(jìn)入毀滅機(jī)制；

13) 輸出最優(yōu)值.

1.2.2 適應(yīng)度函數(shù)設(shè)計(jì) 云環(huán)境中擁有計(jì)算資源、存儲資源和帶寬等資源,用戶可根據(jù)自己的需求,對不同資源進(jìn)行申請和計(jì)費(fèi).由于系統(tǒng)對各種資源的管理和使用方式不同,因此本文將所有的服務(wù)器都視為計(jì)算服務(wù)器進(jìn)行處理.在負(fù)載均衡策略針對大量并發(fā)請求任務(wù)進(jìn)行分配時,負(fù)載調(diào)度機(jī)制通過最小化響應(yīng)時間及服務(wù)器最大化利用率實(shí)現(xiàn)負(fù)載均衡,優(yōu)化資源配置及效率.

適應(yīng)度函數(shù)設(shè)計(jì)原則如下：設(shè)定任務(wù)數(shù)量、服務(wù)器數(shù)量和計(jì)算能力(每臺服務(wù)器計(jì)算能力相同)為已知,使用矩陣表示每個任務(wù)在每個服務(wù)器上的預(yù)計(jì)花費(fèi)時間(expect time to complete,ETC).ETCij表示第i個任務(wù)在第j個服務(wù)器上花費(fèi)的時間,設(shè)任務(wù)的數(shù)量為m,服務(wù)器的數(shù)量為n,則

(1)

因?yàn)樗腥蝿?wù)大小和服務(wù)器的計(jì)算能力己知,因此可計(jì)算出所有任務(wù)執(zhí)行的總時間.設(shè)服務(wù)器j上所有任務(wù)組成的集合為Cj,則服務(wù)器j執(zhí)行完所有任務(wù)所需的時間為

(2)

花費(fèi)的總時間為

totalTime=maxCij,

(3)

基于時間的適應(yīng)度函數(shù)為

(4)

1.2.3 問題描述 為解決云計(jì)算環(huán)境中服務(wù)器負(fù)載均衡的問題,需要合適的方式將服務(wù)器與任務(wù)的關(guān)系映射到一起,通過編碼的方式確定種群中個體的算法表現(xiàn)形式,每個經(jīng)過編碼后得到的數(shù)組表示一個任務(wù)在服務(wù)器上的分配方案.對每個任務(wù)和服務(wù)器進(jìn)行唯一性標(biāo)記,經(jīng)過編碼得到的數(shù)組長度由任務(wù)總數(shù)確定,數(shù)組中每個元素對應(yīng)的值則為任務(wù)對應(yīng)的服務(wù)器編號.利用云計(jì)算的特征,本文對每個云計(jì)算中的子任務(wù)所需占用的服務(wù)器進(jìn)行編碼,子任務(wù)的數(shù)量決定了編碼的長度,將編碼與云任務(wù)分配相對應(yīng),采用服務(wù)器—任務(wù)的間接編碼方式.設(shè)有3個任務(wù),4臺云計(jì)算服務(wù)器,其中任務(wù)1和2分別由3個子任務(wù),任務(wù)3有4個子任務(wù),共計(jì)10個子任務(wù),此時珊瑚礁優(yōu)化算法編碼列于表1.由表1可見,CRO算法編碼序列為{4,1,2,3,2,1,4,2,1,3},對該序列進(jìn)行解碼，結(jié)果列于表2.

表1 珊瑚礁優(yōu)化算法編碼

表2 珊瑚礁優(yōu)化算法解碼

由表2可見,子任務(wù){(diào)2,6,9}分配給1號服務(wù)器,{3,5,8}分配給2號服務(wù)器,{4,10}分配給3號服務(wù)器,{1,7}分配給4號服務(wù)器.一個珊瑚蟲對應(yīng)一個任務(wù)集分配策略,則CRO算法編碼序列為{4,1,2,3,2,1,4,2,1,3},與一個任務(wù)對應(yīng)服務(wù)器的分配方案相對應(yīng).服務(wù)器j上執(zhí)行完所分配的任務(wù)集所用時間F(j)及執(zhí)行完所有任務(wù)的總時間Completetime分別為

(5)

其中：L(j)表示初始負(fù)載；task表示任務(wù)總數(shù)分配到j(luò)上；R(i,j)表示任務(wù)i在服務(wù)器j上的執(zhí)行時間；N表示服務(wù)器總數(shù).

1.3 評價指標(biāo)

假設(shè)一批小任務(wù)由若干大任務(wù)分解組成,且子任務(wù)劃分?jǐn)?shù)量相同,再假設(shè)任務(wù)數(shù)量超過服務(wù)器數(shù)量多倍.用M表示任務(wù)總數(shù),Ti表示第i個子任務(wù),N表示服務(wù)器數(shù)量,VMj表示第j個服務(wù)器,則第j個服務(wù)器完成系統(tǒng)交付的所有子任務(wù)時間為

(6)

其中：Time(Ti,VMj)表示子任務(wù)Ti在服務(wù)器VMj上的執(zhí)行時間；m表示分配到VMj上的子任務(wù)數(shù)量.所有服務(wù)器執(zhí)行任務(wù)所用的最長時間定義為總?cè)蝿?wù)執(zhí)行時間評價函數(shù),即completeTime=max{vmTime(VMj)},j∈[1,N].負(fù)載均衡度DLB評價函數(shù)為

(7)

DBL值越接近1負(fù)載均衡度越高,即每個服務(wù)器完成任務(wù)所用的時間與總?cè)蝿?wù)完成時間越接近表示負(fù)載越均衡.

2 實(shí)驗(yàn)結(jié)果與分析

2.1 實(shí)驗(yàn)參數(shù)初始化

珊瑚礁優(yōu)化算法種群多樣性受限,因此需引入遺傳算法的交叉和變異操作增加種群多樣性,避免陷入局部最優(yōu).交叉概率函數(shù)為

(8)

其中:fmax表示種群最大適應(yīng)度值;favg表示群體平均適應(yīng)度值；f′表示較大的適應(yīng)度值在兩個交叉?zhèn)€體中.如果f′>favg,則交叉概率Pc變小,避免適應(yīng)度值大的個體統(tǒng)治群體,出現(xiàn)陷入局部最優(yōu)解的問題,設(shè)k1=0.36;如果f′

2.2 CloudSim云計(jì)算仿真工具

CloudSim云計(jì)算仿真工具是一種云計(jì)算仿真軟件[15],以GridSim模型為基礎(chǔ)進(jìn)一步發(fā)展得到了CloudSim,支持云計(jì)算的資源管理和調(diào)度模擬,本文在CloudSim3.0中對數(shù)據(jù)中心(Datacenter)、虛擬(VM)以及云任務(wù)(Cloudlet)的環(huán)境參數(shù)進(jìn)行配置,見表3.

表3 CloudSim3.0環(huán)境參數(shù)配置

注：MI表示百萬條指令.

2.3 實(shí)驗(yàn)結(jié)果與分析

下面將本文提出的珊瑚礁遺傳算法(CROGA)與遺傳算法(GA)[13]、珊瑚礁優(yōu)化算法(CRO)[16]、蟻群算法(ACO)[17]、蜂群算法(ABC)[18]、遺傳退火融合算法(GASA)[19-20]、狼群算法(WA)[21]、蛙跳算法(SFLA)的負(fù)載均衡在Cloudsim仿真模擬實(shí)驗(yàn)平臺中實(shí)現(xiàn).基于服務(wù)器負(fù)載率最大值和機(jī)電負(fù)載標(biāo)準(zhǔn)差兩方面進(jìn)行對比.采用服務(wù)器負(fù)載率最大值和服務(wù)器負(fù)載率標(biāo)準(zhǔn)差對負(fù)載均衡度進(jìn)行評價,其中迭代次數(shù)可證明改進(jìn)算法的有效性.重復(fù)執(zhí)行每項(xiàng)實(shí)驗(yàn)10次,最后取實(shí)驗(yàn)結(jié)果的平均值.

假設(shè)測試參數(shù)為：測試任務(wù)數(shù)量1 000個；群體M=20；迭代次數(shù)T=35；交叉因子C=0.5；變異因子D=0.7；珊瑚礁大小為Am×n;外部有性繁殖概率Pb=0.8；內(nèi)部有性繁殖概率1-Pb=0.2;無性繁殖概率Pa=0.3;死亡概率Pd=Pa=0.3.測試函數(shù)定義為適應(yīng)度函數(shù).

2.3.1 算法的有效性分析 下面針對上述8種算法在任務(wù)數(shù)量由25逐漸增加到250的過程中,對最優(yōu)解所需的迭代次數(shù)進(jìn)行比較，不同算法迭代次數(shù)的對比結(jié)果列于表4.由表4可見：當(dāng)任務(wù)數(shù)量增加時,迭代次數(shù)持續(xù)遞增；在任務(wù)數(shù)量相同的情況下,遺傳算法和蜂群算法的迭代次數(shù)與其他算法相比最多；當(dāng)任務(wù)數(shù)量等于或小于75時,本文提出的遺傳珊瑚礁優(yōu)化算法與其他幾種算法在迭代次數(shù)方面相差不多；當(dāng)任務(wù)數(shù)量逐漸增多且大于75時,遺傳珊瑚礁優(yōu)化算法體現(xiàn)出優(yōu)勢,所需的迭代次數(shù)相比于其他算法更少.表明在運(yùn)行效率上,遺傳珊瑚礁優(yōu)化算法優(yōu)于其他算法,證明了改進(jìn)遺傳珊瑚礁優(yōu)化算法的有效性.

表4 不同算法迭代次數(shù)對比

2.3.2 評價算法的負(fù)載均衡度 服務(wù)器執(zhí)行任務(wù)分配不均衡是導(dǎo)致系統(tǒng)功耗成本過高的一個主要原因.表5列出了不同算法服務(wù)器負(fù)載率最大值對比結(jié)果.由表5可見,當(dāng)任務(wù)數(shù)量逐漸增多時,8種算法的服務(wù)器負(fù)載率最大值均增大,但本文提出的遺傳珊瑚礁優(yōu)化算法服務(wù)器的負(fù)載率最大值始終比其他算法小,并且任務(wù)數(shù)量50～300時負(fù)載率均低于60%,表明本文提出的遺傳珊瑚礁優(yōu)化算法任務(wù)分配更合理.

表5 不同算法服務(wù)器負(fù)載率(%)最大值對比

綜上所述,本文將遺傳算法的選擇、交叉和變異操作引入到基本珊瑚礁優(yōu)化算法中,提出了一種基于遺傳算法環(huán)境下的遺傳珊瑚礁優(yōu)化算法,能將遺傳算法中的遺傳選擇操作更大地優(yōu)化,有效增加了種群的多樣性,增強(qiáng)了算法的全局搜索能力,提高了網(wǎng)絡(luò)資源利用率,明顯改善了網(wǎng)絡(luò)負(fù)載不均衡的情況.