基于改進(jìn)蟻群算法的負(fù)載均衡機(jī)制的研究*

于 爽劉從軍，2

（1.江蘇科技大學(xué)計(jì)算機(jī)學(xué)院 鎮(zhèn)江 212003）（2.江蘇科大匯峰科技有限公司 鎮(zhèn)江 212003）

1 引言

網(wǎng)絡(luò)負(fù)載均衡是保證網(wǎng)絡(luò)系統(tǒng)正常運(yùn)行的的重要技術(shù)手段，隨著互聯(lián)網(wǎng)和大數(shù)據(jù)的不斷增長(zhǎng)，用戶對(duì)網(wǎng)絡(luò)的訪問(wèn)量急劇上升［1］，面對(duì)大用戶、高并發(fā)和海量數(shù)據(jù)請(qǐng)求，網(wǎng)絡(luò)負(fù)載能力亟待提升，設(shè)計(jì)一個(gè)靈活的動(dòng)態(tài)負(fù)載均衡機(jī)制去解決任務(wù)分配問(wèn)題，可大大提高系統(tǒng)業(yè)務(wù)執(zhí)行效率［2］，解決大量并發(fā)訪問(wèn)服務(wù)請(qǐng)求，為用戶提供更好的訪問(wèn)質(zhì)量。

負(fù)載均衡技術(shù)的核心是負(fù)載均衡算法，目前對(duì)負(fù)載均衡算法優(yōu)化的研究是其主流方向，負(fù)載均衡算法可分為靜態(tài)和動(dòng)態(tài)兩類［3］。其中前者包括優(yōu)先權(quán)、輪詢等，主要是基于服務(wù)器容量進(jìn)行分配，該算法實(shí)現(xiàn)簡(jiǎn)單，復(fù)雜度低，不需考慮節(jié)點(diǎn)狀態(tài)和網(wǎng)絡(luò)狀況，可靠性好，但缺點(diǎn)是不能很好的均衡不同節(jié)點(diǎn)的處理性能和適應(yīng)網(wǎng)絡(luò)的變化，易導(dǎo)致高性能設(shè)備空閑而底性能設(shè)備擁塞的情況，因此其靈活性較差。而動(dòng)態(tài)負(fù)載均衡算法可通過(guò)定期收集系統(tǒng)參數(shù)實(shí)現(xiàn)對(duì)調(diào)度策略的動(dòng)態(tài)調(diào)整［4］，從而實(shí)現(xiàn)較好的負(fù)載均衡質(zhì)量。常見(jiàn)的有一致性哈希算法、預(yù)測(cè)法等。目前也有學(xué)者將生物優(yōu)化算法如蟻群算法、遺傳算法等加入到負(fù)載均衡計(jì)算中，并取得了不錯(cuò)的效果。本文通過(guò)對(duì)基本蟻群算法進(jìn)行改進(jìn)，克服其自身的不足實(shí)現(xiàn)負(fù)載均衡性能的提高。

2 傳統(tǒng)蟻群算法

蟻群算法（AOC）是一種通過(guò)模仿螞蟻覓食行為而提出的生物組合優(yōu)化算法。在尋找食物的過(guò)程中螞蟻之間會(huì)通過(guò)一種叫做信息素的化學(xué)物質(zhì)傳遞食物信息，路徑越短，釋放的信息素濃度越高，該路徑便會(huì)吸引更多的螞蟻聚集，由此而找到覓食的最優(yōu)路徑［5］。ACO算法具并發(fā)性、正反饋性、可與其他算法結(jié)合等優(yōu)點(diǎn)，因而常用來(lái)解決多種目標(biāo)下的尋優(yōu)問(wèn)題［6］。

其基本求解過(guò)程如下：

1）算法初始化：對(duì)蟻群的啟發(fā)信息、迭代次數(shù)、螞蟻數(shù)、節(jié)點(diǎn)數(shù)和信息素、進(jìn)行初始化設(shè)置。信息素濃度用τij(t)來(lái)表示，初始時(shí)為固定值，啟發(fā)信息用ηij表示，他與dij的關(guān)系為：，其中dij表示節(jié)點(diǎn)i到j(luò)的路徑長(zhǎng)度。

2）轉(zhuǎn)移概率的計(jì)算：螞蟻在節(jié)點(diǎn)間移動(dòng)時(shí)，會(huì)根據(jù)節(jié)點(diǎn)的轉(zhuǎn)移概率來(lái)決定下一步的移動(dòng)位置，轉(zhuǎn)移概率公式為

式中，α代表信息素因子，β代表啟發(fā)期望因子，allowedk表示允許訪問(wèn)的節(jié)點(diǎn)。

3）信息素更新：為了對(duì)路徑信息進(jìn)行不斷的篩選，蟻群算法中引入了信息素?fù)]發(fā)因子ρ（0＜ρ＜1），當(dāng)螞蟻完成一次循環(huán)后，需要對(duì)路徑上的信息素按照如下公式進(jìn)行更新［7］：

4）終止條件：循環(huán)次數(shù)達(dá)到預(yù)設(shè)值，則停止，輸出最優(yōu)解。

3 蟻群算法求解負(fù)載均衡問(wèn)題

服務(wù)端的負(fù)載均衡實(shí)質(zhì)是一個(gè)任務(wù)調(diào)度問(wèn)題，指在用戶QoS約束條件下，將請(qǐng)求任務(wù)合理地分配給服務(wù)器去執(zhí)行，并達(dá)到最短化任務(wù)完成時(shí)間和最優(yōu)化系統(tǒng)性能。可用如下調(diào)度模型表示。

圖1 任務(wù)調(diào)度過(guò)程

將M個(gè)任務(wù)分配到N個(gè)服務(wù)器上去執(zhí)行獲得最佳分配方案。則基于蟻群算法的任務(wù)調(diào)度實(shí)質(zhì)是找到M×N個(gè)節(jié)點(diǎn)的最短路徑，這個(gè)最短路徑基于任務(wù)完成時(shí)間和負(fù)載均衡度。

為衡量路徑是否最短，需設(shè)定一個(gè)目標(biāo)函數(shù)來(lái)計(jì)算路徑目標(biāo)值，為信息素更新做鋪墊。將m個(gè)任務(wù)分配給n個(gè)服務(wù)器，因每個(gè)服務(wù)器資源參數(shù)不同，任務(wù)需求也不同，為形成目標(biāo)函數(shù)，以Cij作為任務(wù)Ti在服務(wù)器Sj上的完成時(shí)間，可使用式（3）計(jì)算所有任務(wù)的完成時(shí)間：

其中，Eij為Mj上完成第i個(gè)人物的預(yù)期時(shí)間，Wj為服務(wù)器Sj的任務(wù)等待時(shí)間。

服務(wù)集群中所有任務(wù)的最大完工時(shí)間可表示為

其中，k為分配給服務(wù)器j的任務(wù)量。

負(fù)載的目標(biāo)是在最小響應(yīng)時(shí)間下實(shí)現(xiàn)最大資源利用率，基于此，將目標(biāo)函數(shù)定義為［8～9］

4 改進(jìn)蟻群算法

傳統(tǒng)蟻群算法在求解過(guò)程中也具有一定的局限性，一是算法初期，由于信息素初始值相同，選擇下一個(gè)節(jié)點(diǎn)時(shí)傾向于隨機(jī)選擇。雖然隨機(jī)選擇能探索更大的任務(wù)空間，有助于找到潛在的全局最優(yōu)解，但是需要較長(zhǎng)時(shí)間才能發(fā)揮正反饋的作用，因而開(kāi)始時(shí)算法的進(jìn)化能力較低。二是到了算法后期，由于ACO算法的正反饋?zhàn)饔玫脑鰪?qiáng)，螞蟻選擇方式的隨機(jī)性減小，雖然加快了收斂進(jìn)程，但容易使算法產(chǎn)生局部最優(yōu)解。針對(duì)以上缺點(diǎn)，本文采用如下方法對(duì)算法進(jìn)行改進(jìn)。

4.1 信息素初始化方式的改進(jìn)

傳統(tǒng)蟻群算法中信息素采用均勻化方式初始，操作簡(jiǎn)單但易導(dǎo)致算法初期陷入盲目搜索，進(jìn)化效率不高，為提高算法前期進(jìn)化率，許多學(xué)者對(duì)信息素初始化方式進(jìn)行了改進(jìn)。研究發(fā)現(xiàn)遺傳算法（GA）具有較強(qiáng)的搜索能力，算法初期將遺傳算法加入到蟻群算法中，可有效的提高ACO算法的進(jìn)化速率。圖2為兩種算法的進(jìn)化率隨時(shí)間的變化曲線。

圖2 遺傳算法與蟻群算法的進(jìn)化率-時(shí)間曲線

從圖中可以看出，蟻群算法初期進(jìn)化率較低，但隨著時(shí)間的推移，其正反饋?zhàn)饔冒l(fā)揮后，其進(jìn)化率急劇上升，并且上升到一定水平后保持相對(duì)穩(wěn)定。GA算法在前期搜索能力較高，其進(jìn)化率也較高，但隨著時(shí)間的推移，相較于蟻群算法，其沒(méi)有一種有效的反饋機(jī)制，后期收斂速度變慢，進(jìn)化率也隨之降低，并降低到一定水平后趨于相對(duì)穩(wěn)定。因而，本文將遺傳算法引入到蟻群算法，將遺傳算法進(jìn)化得到的較優(yōu)解作為蟻群算法的初始信息素以加快算法初期的進(jìn)化速率［10］。

4.2 轉(zhuǎn)移概率的確定

前面我們解決了傳統(tǒng)蟻群算法初期收斂速度慢的問(wèn)題，當(dāng)算法進(jìn)行到一定程度后隨著正反饋機(jī)制發(fā)揮作用，或者當(dāng)問(wèn)題規(guī)模較大時(shí)，按照概率選擇公式訪問(wèn)節(jié)點(diǎn)的方式，使得螞蟻選擇節(jié)點(diǎn)的隨機(jī)性減小，算法易產(chǎn)生局部最優(yōu)解。因此，要對(duì)概率選擇公式進(jìn)行優(yōu)化，本文采取偽隨機(jī)比例規(guī)則增加轉(zhuǎn)移概率公式的隨機(jī)性［11］。具體如下：

4.3 啟發(fā)信息的改進(jìn)

求解過(guò)程中為防止出現(xiàn)負(fù)載不均衡的現(xiàn)象，造成資源浪費(fèi)，加入一個(gè)負(fù)載均衡因子去調(diào)節(jié)任務(wù)分配。其計(jì)算公式為

其中，Ej代表服務(wù)器Sj的總完工時(shí)間，Eavg代表n臺(tái)服務(wù)器的平均完工時(shí)間。由公式可以看出，Loadj與Ej成反比，隨著Ej的增加而減小。

由螞蟻的概率轉(zhuǎn)移公式可知，螞蟻在選擇下一個(gè)節(jié)點(diǎn)時(shí)受啟發(fā)信息和信息素濃度的影響，傳統(tǒng)ACO算法中，啟發(fā)函數(shù)ηij與路徑間距dij成反比，但在求解負(fù)載均衡問(wèn)題時(shí)，啟發(fā)信息通常與服務(wù)器預(yù)計(jì)執(zhí)行時(shí)間Eij成反比［12］。將負(fù)載因子加入到啟發(fā)信息中，實(shí)現(xiàn)對(duì)啟發(fā)信息的進(jìn)一步優(yōu)化，平衡服務(wù)器負(fù)載，計(jì)算公式為

4.4 改進(jìn)后的算法流程

遺傳算法：

1）編碼：實(shí)數(shù)編碼，以提高GA算法的求解精度。

2）計(jì)算個(gè)體適應(yīng)度函數(shù)：適應(yīng)度函數(shù)的設(shè)計(jì)直接影響GA算法的求解質(zhì)量，馬克沃茨均值-方差組合模型是用于解決金融投資的合理配置，平衡收益和風(fēng)險(xiǎn)的一種預(yù)測(cè)模型［13］，其公式為

圖3 改進(jìn)遺傳-蟻群算法的流程圖

其中，負(fù)載均衡中對(duì)任務(wù)的調(diào)度分配與上述模型類似，即在均衡任務(wù)分配時(shí)達(dá)到服務(wù)器響應(yīng)時(shí)間最小而資源利用率最大。因而利用此模型作為適應(yīng)度函數(shù)，可在約束范圍內(nèi)進(jìn)行計(jì)算，實(shí)現(xiàn)負(fù)載目標(biāo)。

3）終止條件判斷：終止條件判斷有三個(gè)，滿足其中任意一個(gè)即可停止進(jìn)化，輸出最優(yōu)解。（1）達(dá)到最大進(jìn)化次數(shù)；（2）個(gè)體或種群的適應(yīng)度相對(duì)穩(wěn)定；（3）個(gè)體適應(yīng)度值達(dá)到設(shè)定閾值。

4）遺傳操作：對(duì)未達(dá)到終止條件的種群，按照預(yù)設(shè)值執(zhí)行選擇、交叉、變異操作［14～15］。

蟻群算法：

1）初始化信息素：用遺傳算法求得的解去初始蟻群算法的信息素。

2）計(jì)算轉(zhuǎn)移概率：采用偽隨機(jī)比例規(guī)則結(jié)合公式（1）選擇下一節(jié)點(diǎn)。

3）計(jì)算每只螞蟻完成一次搜索任務(wù)的路徑長(zhǎng)度。

4）更新信息素濃度：根據(jù)式（2）對(duì)信息素濃度進(jìn)行更新。

5）完成迭代，輸出最優(yōu)解［16］。

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

為驗(yàn)證本文算法的優(yōu)越性，選用OPNET仿真平臺(tái)，分別對(duì)輪詢法（RR）、傳統(tǒng)蟻群算法（AOC）和本文算法三種算法的負(fù)載性能進(jìn)行了實(shí)驗(yàn)對(duì)比，相應(yīng)的算法參數(shù)設(shè)置如下表所示。

表1 遺傳算法參數(shù)

表2 蟻群算法參數(shù)

本實(shí)驗(yàn)主要對(duì)集群平均響應(yīng)時(shí)間和節(jié)點(diǎn)利用率進(jìn)行了對(duì)比測(cè)試，實(shí)驗(yàn)結(jié)果如圖所示。

圖4顯示了在任務(wù)數(shù)不同的情況下，三種算法對(duì)應(yīng)的服務(wù)器平均響應(yīng)時(shí)間，如圖，當(dāng)任務(wù)數(shù)增加時(shí)，平均響應(yīng)時(shí)間也相應(yīng)的增加，其中輪詢算法的響應(yīng)時(shí)間最長(zhǎng)，改進(jìn)的蟻群算法響應(yīng)時(shí)間最短。因此，本文中改進(jìn)的蟻群算法在負(fù)載均衡方面有效縮短了服務(wù)器處理請(qǐng)求的平均響應(yīng)時(shí)間。

圖4 平均響應(yīng)時(shí)間對(duì)比

根據(jù)圖5所示，隨著任務(wù)數(shù)的增加，本文算法的節(jié)點(diǎn)利用率也隨之上升，且總體節(jié)點(diǎn)利用率高于其它兩種算法，說(shuō)明本文設(shè)計(jì)的蟻群優(yōu)化算法提高了并發(fā)任務(wù)的調(diào)度效率。

圖5 平均節(jié)點(diǎn)利用率對(duì)比

6 結(jié)語(yǔ)

本文通過(guò)對(duì)傳統(tǒng)蟻群算法進(jìn)行改進(jìn)，提出了一種改進(jìn)的蟻群算法來(lái)實(shí)現(xiàn)網(wǎng)絡(luò)負(fù)載均衡，首先采用遺傳算法解決蟻群算法前期收斂慢的問(wèn)題，然后在算法后期加入偽隨機(jī)序列防止算法早熟，并對(duì)啟發(fā)信息進(jìn)行了優(yōu)化。通過(guò)仿真軟件，分別采用GA、ACO、本文算法進(jìn)行實(shí)驗(yàn)仿真，結(jié)果表明本文算法有效的縮短了響應(yīng)時(shí)間提高了節(jié)點(diǎn)利用率，使得整個(gè)集群負(fù)載更加平衡。