基于蟻群算法的網(wǎng)絡(luò)負(fù)載均衡的研究與實(shí)現(xiàn)

引言

蟻群算法(AntColonyOptimization,ACO)是模擬蟻群尋找食物的一種生物啟發(fā)式算法⑴，通過研究圖論來尋找優(yōu)化路徑。針對網(wǎng)絡(luò)資源管理中路徑負(fù)載、路由選擇、集群并行計(jì)算等研究課題，將網(wǎng)絡(luò)流量工程與蟻群算法相結(jié)合,提出基于蟻群算法的網(wǎng)絡(luò)流量負(fù)載均衡和路由選擇優(yōu)化的新方法。

流量負(fù)載均衡與路由選擇優(yōu)化，一直都是網(wǎng)絡(luò)資源優(yōu)化研究中的重要課題⑵；云網(wǎng)絡(luò)集群和分布式并行計(jì)算，是當(dāng)前網(wǎng)絡(luò)發(fā)展和研究的前沿課題。本文研究的目標(biāo)就是把海量服務(wù)請求合理地分配到現(xiàn)有網(wǎng)絡(luò)資源，避免網(wǎng)絡(luò)擁塞瓶頸，提高網(wǎng)絡(luò)服務(wù)質(zhì)量(QoS)。網(wǎng)絡(luò)流量的負(fù)載均衡如圖1所示。

1  蟻群算法概述

1.1  蟻群算法

蟻群算法是繼模擬退火算法、基因遺傳算法、禁忌搜索算法、人工神經(jīng)網(wǎng)絡(luò)算法之后的又一種搜索算法,主要應(yīng)用于復(fù)雜組合問題的搜索優(yōu)化其。該算法具有智能搜索、正反饋、全局優(yōu)化、快速求解，以及穩(wěn)健性、分布式計(jì)算、易于與其它算法結(jié)合等優(yōu)點(diǎn)。

1.2  算法基本原理

蟻群算法是通過蟻群間信息素的動態(tài)交互(即蟻群內(nèi)信息素相互增強(qiáng)，蟻群間信息素相互減弱)來建立數(shù)學(xué)模型，模擬蟻群尋找食物的一種搜索算法。

螞蟻屬于群居昆蟲，個體行為極其簡單，而群體行為卻極其復(fù)雜。一群螞蟻通過彼此之間的相互協(xié)作，能夠很容易從蟻巢出發(fā)去找到食物源，并且所經(jīng)過的路徑最短。人們通過大量的研究發(fā)現(xiàn)，螞蟻個體之間是通過在其走過的路徑上留下一種可稱之為“信息素(Pheromone)w的物質(zhì)來進(jìn)行信息傳遞。后到的螞蟻遇到信息素時，檢測出該物質(zhì)存在量的多少，并且根據(jù)信息素的濃度來指引自己前進(jìn)的方向。同時，隨著時間的推移，信息素會逐漸消減，路徑的長短和路徑上螞蟻的多少對路徑上殘余信息素的強(qiáng)度產(chǎn)生影響，反過來信息素的強(qiáng)弱又指引其它螞蟻前進(jìn)的方向。因此，路徑上走過的螞蟻越多，則后來螞蟻選擇

該路徑的概率越大，這就構(gòu)成了螞蟻群體行為表現(xiàn)出的一種信息正反饋機(jī)制螞蟻個體間就是通過這種信息交流來快速搜索到食物源。

圖1    網(wǎng)絡(luò)流量的負(fù)載均衡

蟻群從蟻巢到達(dá)食物源的過程中,外界環(huán)境是不斷變化的，如信息素的濃度、障礙物等。螞蟻覓食過程中釋放的信息素具有三點(diǎn)特性：

首先是具有揮發(fā)性，隨著時間的流逝，路徑上的信息素會逐漸減弱。

其次是具有隨機(jī)性，對下一步路徑的選擇是隨機(jī)的。

另外，就是具有啟發(fā)性,路徑上的信息素越多，被選中的概率就越高。

1.3   蟻群算法的數(shù)學(xué)模型

為了模擬螞蟻的行為，以求解N個城市的旅行商問題(TravelingSalesmanProblem,TSP)為例。已知有N個城市，尋找一條訪問兩個城市之間的最短路徑。設(shè)蟻群中螞蟻數(shù)量為m,城市/和j之間的路徑

式中，螞蟻總數(shù)m等于N個城市在t時刻螞蟻數(shù)量BiCt)之和。

Ttj(t)表示t時刻在i?j路徑&頊殘留的信息量。初始時刻，在各條路徑上的信息量相等，設(shè)烏(0)=C(C為常數(shù)，初始化時通常取為0)。螞蟻Kfe=1,2,…)在運(yùn)動過程中，根據(jù)各路徑上的信息量濃度大小決定轉(zhuǎn)移方向，t時刻螞蟻&由位置/轉(zhuǎn)移到j(luò)的概率P$(t)：

式中，rejected；.={k}表示螞蟻k已經(jīng)走過，下一步不會途經(jīng)的城市集合，即禁忌表;allowed*={N—k}表示螞蟻方還沒有走過,下一步可能會途徑的城市集合，即候選表-rejectedjs)表示禁忌表中的第s個元素；烏(t)表示螞蟻后在t時刻在城市i到j(luò)的路徑上捕獲的信息素強(qiáng)度，其大小可由路徑上殘留的信息素、當(dāng)前螞蟻k釋放的信息素和信息素本身揮發(fā)剩余量綜合確定;入”1)表示螞蟻后在t時刻由城市/到j(luò)的期望程度(亦稱可見度)，其值可根據(jù)某種啟發(fā)式算法確定。當(dāng)相。)>0時，表示鄰域，處的螞蟻京在t時刻按概率P§(t)移至鄰域j的可能性；當(dāng)Ai;(t)<0時，鄰域/處的螞蟻及做鄰域搜索,其搜索半徑為r(此值可由實(shí)驗(yàn)得出)；a,/3分別表示螞蟻在運(yùn)動過程中所積累的信息及啟發(fā)式因子在螞蟻選擇路徑中所起的不同作用，它們是控制信息素強(qiáng)度與可見度相對重要性的參數(shù)?？梢?，轉(zhuǎn)移概率是期望程度(即可見度)和信息素強(qiáng)度的綜合權(quán)衡的結(jié)果。

人工蟻群系統(tǒng)與真實(shí)螞蟻系統(tǒng)不同，為了使人工蟻群系統(tǒng)更加智能與高效，還需使其具有一定的記憶功能，用rejected*O=1,2,…)記錄螞蟻k目前已途經(jīng)過的城市。但是隨著時間的慢慢推移，先前釋放留下的信息素濃度會逐漸揮發(fā)消逝。設(shè)信息素濃度的保留系數(shù)為p(0<p<1)，它體現(xiàn)了信息素強(qiáng)度的頻繁性和持久性;而1—p表示信息素的消逝程度。經(jīng)過時間間隔，螞蟻完成一次循環(huán)搜索，路徑上信息素濃度可按下式計(jì)算：

式中，△在表示螞蟻k在本次循環(huán)時間間隔內(nèi)，在路徑eg邊上留下的新增信息素量;而爲(wèi)"函)表示全部螞蟻m={1,2,…}在本次循環(huán)時間間隔內(nèi)，在路徑邊上留下的信息素濃度之和；q(t十△[)表示i-j路徑上信息素濃度的總和，其中△者可表示為：

式中，n表示螞蟻k在本次循環(huán)中所漫游的城市數(shù)目(n≤N)。

綜上所述，式(1)?式(6)中出現(xiàn)的a，B，p,Q等參數(shù)根據(jù)實(shí)際用途與領(lǐng)域，用試驗(yàn)的方法確定g(t),烏表達(dá)式可根據(jù)具體問題而定。由于上述過程是一個遞推過程，易在計(jì)算機(jī)上編程實(shí)現(xiàn),其停止條件可以用固定循環(huán)次數(shù)或者當(dāng)進(jìn)化趨勢不明顯時停止。

2  基于蟻群算法的網(wǎng)絡(luò)負(fù)載均衡

2.1  數(shù)學(xué)建模的基本思想

通過模擬蟻群釋放出的信息素這個紐帶,可以抽象出表1所列的模型假設(shè)。

表1    蟻群算法的假設(shè)模型

2.2  蟻群算法的設(shè)計(jì)原理

假設(shè)各節(jié)點(diǎn)間的初始信息素強(qiáng)度都相等，將m只螞蟻置于m個源節(jié)點(diǎn)。

初始時刻，m只螞蟻位于加個源節(jié)點(diǎn)，N個節(jié)點(diǎn)的信息素強(qiáng)度相同。

每次循環(huán)前，檢驗(yàn)是否滿足終止條件。如果滿足終止條件，則停止移動;如果不滿足終止條件，則按照下列的轉(zhuǎn)移規(guī)則進(jìn)行移動。

在剩余未走過的節(jié)點(diǎn)集合中，隨機(jī)選擇一個路由節(jié)點(diǎn),按照轉(zhuǎn)移概率和轉(zhuǎn)移規(guī)則進(jìn)行移動，直到完成一次搜索結(jié)束。

轉(zhuǎn)移到下一個節(jié)點(diǎn)后，如果此節(jié)點(diǎn)為目標(biāo)節(jié)點(diǎn)，則顯示訪問成功,返回請求服務(wù)信息;如果此節(jié)點(diǎn)為源節(jié)點(diǎn)，則重新初始化,按步驟(3)進(jìn)行。

按照信息調(diào)整規(guī)則，在本次搜索結(jié)束后，對各節(jié)點(diǎn)間的信息素進(jìn)行更新調(diào)整，為下一次的轉(zhuǎn)移做準(zhǔn)備。

重復(fù)步驟(2),如滿足終止條件，則終止搜索，標(biāo)記顯示搜索路徑與搜索時間；如果不滿足終止條件，則重復(fù)步驟(3)?(5),直到滿足終止條件為止*。

圖2所示是根據(jù)蟻群算法設(shè)計(jì)的基本流程圖。

2.3  基于蟻群算法實(shí)現(xiàn)負(fù)載均衡的編程設(shè)計(jì)

蟻群算法是對自然界螞蟻覓食過程的抽象，通過建立數(shù)學(xué)模型，在電腦上模擬實(shí)現(xiàn)。事實(shí)上，每只螞蟻并不需要知道整個世界的信息，它們只需要關(guān)心自身附近很小范圍內(nèi)的信息，根據(jù)捕獲的局部信息，利用幾條簡單的規(guī)則進(jìn)行判斷與決策。這樣，在蟻群這個集體里,復(fù)雜性的行為就會凸現(xiàn)出來，抽象成簡單規(guī)則。蟻群算法的設(shè)計(jì)就是把復(fù)雜問題抽象成簡單的數(shù)學(xué)模型,抽象設(shè)計(jì)遵循以下六條規(guī)則：

圖2    蟻群算法的基本流程

2.3.1  搜索范圍

螞蟻觀察的范圍為一個抽象的方格世界,螞蟻轉(zhuǎn)移參數(shù)為速度半徑(初始化為3),這樣螞蟻觀察到的范圍就是一個3X3的方格世界，轉(zhuǎn)移到下一個路由節(jié)點(diǎn)的距離在這個范圍之內(nèi)。

2.3.2  環(huán)境變化

螞蟻所在的環(huán)境在電腦模擬中是一個虛擬的世界,其中有障礙物、有別的螞蟻、還有信息素。信息素有兩種，一種是找到食物灑下的食物信息素，另一種是找到蟻巢后螞蟻灑下的蟻巢信息素。每只螞蟻都僅能感知它范圍之內(nèi)(3X3)的鄰近區(qū)域。同時，隨著時間的流逝，環(huán)境讓信息素以一定的速率逐漸消減。

2.3.3  覓食規(guī)則

每只螞蟻在能感知的范圍內(nèi)尋找是否有食物，如果有就直接過去;否則看路徑上是否有信息素，比較哪一點(diǎn)的信息素強(qiáng)度最大，螞蟻就朝哪個方向轉(zhuǎn)移;同時螞蟻也會以小概率犯錯誤，即并不是每次都理想地往信息素最多的節(jié)點(diǎn)移動。螞蟻找窩的規(guī)則和上面一樣，不同的是僅對窩的信息素做出反應(yīng)，而對食物信息素沒反應(yīng)。

2.3.4  轉(zhuǎn)移規(guī)則

螞蟻都朝向信息素最多的方向轉(zhuǎn)移，當(dāng)周圍沒有信息素指引時，它會繼續(xù)自己原來的軌跡，慣性地移動下去。同時，螞蟻在運(yùn)動的方向上也會有一個隨機(jī)的小擾動。為了預(yù)防螞蟻原地轉(zhuǎn)圈，它會記住自己的歷史軌跡，盡量避開已走過的節(jié)點(diǎn)，從而遍歷新節(jié)點(diǎn)。

2.3.5  避障規(guī)則

如果螞蟻要移動的方向有障礙物擋住，它會隨機(jī)地選擇一個其它方向，并且在信息素強(qiáng)弱的指引下做出智能判斷和選擇。

2.3.6  釋放信息素規(guī)則

螞蟻在剛找到食物或蟻巢時會散發(fā)更多的信息素,并隨著它走遠(yuǎn)的距離，釋放出的信息素會越來越少;隨著時間的流逝，殘留的信息素也會慢慢消失。

基于蟻群算法原理,在計(jì)算機(jī)上編程模擬實(shí)現(xiàn)：最大信息素:螞蟻初始時擁有的信息素總量。

消失的速度：隨著時間的流逝，路徑上的信息素慢慢揮發(fā)、消減的速度。

錯誤概率：螞蟻?zhàn)龀鲆苿舆x擇，不僅需要根據(jù)信息素強(qiáng)度的大小，而且自身也有一個隨機(jī)的小擾動，錯誤概率越大，表示螞蟻越有獨(dú)立性與創(chuàng)新性。

速度半徑：螞蟻一次搜索過程中轉(zhuǎn)移的最大距離，也就是螞蟻能感知的最大范圍。

記憶能力：記錄螞蟻剛剛走過的路由節(jié)點(diǎn)信息，這樣能夠避免螞蟻原地轉(zhuǎn)圈、避免重復(fù)。

初始時，螞蟻從蟻巢出發(fā)，尋找食物，找到食物后再返回蟻巢，蟻群遇到路障后的轉(zhuǎn)移規(guī)則如圖3所示。

圖3    螞蟻遇到路障的轉(zhuǎn)移規(guī)則

由圖3可見，當(dāng)無路障時，螞蟻根據(jù)路徑上信息素濃度和自身隨機(jī)的移動規(guī)則，繼續(xù)轉(zhuǎn)移；

遇到單路障時，螞蟻根據(jù)信息素濃度大小和隨機(jī)選擇綜合確定，繞過路障繼續(xù)轉(zhuǎn)移。

而當(dāng)遇到多個路障時，螞蟻?zhàn)裱瓎温氛弦?guī)則，然后繞過路障繼續(xù)轉(zhuǎn)移。

人工蟻群和自然界蟻群的相似之處在于,兩者優(yōu)先選擇的都是含“信息素”濃度較大的路徑，選擇路徑時會有一個小擾動，這樣在較短的路徑上會聚集較多的信息素。

2.4  基于蟻群算法實(shí)現(xiàn)負(fù)載均衡的編程設(shè)計(jì)流程圖蟻群算法實(shí)現(xiàn)負(fù)載均衡的編程設(shè)計(jì)流程圖如圖4所示。

Start

圖4    用蟻群算法實(shí)現(xiàn)負(fù)載均衡的程序流程圖

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

3.1  單服務(wù)器下基于蟻群算法的網(wǎng)絡(luò)路由選擇基于蟻群算法的基本原理可用C語言在計(jì)算機(jī)上編程，以模擬網(wǎng)絡(luò)環(huán)境。

圖5所示是基于蟻群算法的單服務(wù)器下的網(wǎng)絡(luò)路由選擇方法，圖5中的內(nèi)容描述如表2所列。

表2    單服務(wù)器下的網(wǎng)絡(luò)路由選擇

圖5(a)：開始1s時，蟻群都集中于蟻巢H及其附近區(qū)域，即將進(jìn)行食物路徑的遍歷搜索。

圖5(b)：14s后，正在進(jìn)行路徑遍歷搜索，搜索

2012年/第2期物聯(lián)網(wǎng)技術(shù)61\

達(dá)到食物目標(biāo)節(jié)點(diǎn)的最優(yōu)路徑。

圖5(c)：42s后，已經(jīng)基本完成遍歷搜索，并在全局范圍內(nèi)找到了最優(yōu)路徑。

圖5    單服務(wù)器下的網(wǎng)絡(luò)路由選擇

上述實(shí)驗(yàn)結(jié)果表明，蟻群算法具有智能搜索、全局優(yōu)化的特性，利用正反饋機(jī)制可以快速地尋找到最優(yōu)路徑。

3.2  多服務(wù)器下基于蟻群算法實(shí)現(xiàn)流量負(fù)載均衡

基于蟻群算法來實(shí)現(xiàn)多服務(wù)器的網(wǎng)絡(luò)負(fù)載流量均衡的研究實(shí)驗(yàn)結(jié)果如圖6所示。圖中的內(nèi)容描述如表3所列。

圖6    多服務(wù)器下的流量負(fù)載均衡

表3    多服務(wù)器下的負(fù)載均衡選擇

圖6(a)：開始1s時，蟻群都集中于蟻巢H及其附近區(qū)域，即將進(jìn)行食物路徑的遍歷搜索。

圖6(b)：19s后，正在進(jìn)行遍歷搜索時，螞蟻首先搜索到最近的食物，并根據(jù)螞蟻的需求與食物本身的多少，綜合考慮后做出是否需要尋找下一處食物的抉擇。

圖6(c)：33s后，由于紅色的食物不能滿足螞蟻的需求，即分擔(dān)過載(標(biāo)記成f),于是螞蟻需要尋找下一處的服務(wù)器(即白色食物F),以達(dá)到負(fù)載均衡。

圖6(d)：44s后，螞蟻在紅色食物F(f)和白色食物F等多處食物處尋找食物，以滿足自身的需求，緩解單一食物處的需求壓力，從而達(dá)到了負(fù)載均衡訪問。

3.3  實(shí)驗(yàn)結(jié)果分析與研究結(jié)論

為了提升訪問的效率和速度，可以提出設(shè)置多臺服務(wù)訪問終端，并作鏡像處理,如此就可以在地理位置、訪問時間、服務(wù)質(zhì)量等方面,使訪問得到極大的優(yōu)化與改善。實(shí)現(xiàn)網(wǎng)絡(luò)流量負(fù)載均衡的方法有多種，但是從當(dāng)前的應(yīng)用技術(shù)和實(shí)際實(shí)施看，采取在不同的地理位置配置多臺服務(wù)終端設(shè)備來實(shí)現(xiàn)服務(wù)請求的及時響應(yīng)是主流技術(shù)。因此,本文從這個角度出發(fā)，采用C語言在計(jì)算機(jī)上編程模擬實(shí)現(xiàn)了網(wǎng)絡(luò)環(huán)境下的網(wǎng)絡(luò)流量負(fù)載均衡的研究與實(shí)現(xiàn)，并取得了良好的實(shí)驗(yàn)效果。

通過對實(shí)驗(yàn)結(jié)果的分析表明，蟻群算法具有智能搜索、全局優(yōu)化、穩(wěn)健性與正反饋等優(yōu)點(diǎn)，能夠在較短的時間內(nèi)尋找到最優(yōu)路由，使服務(wù)請求得到最快的服務(wù)響應(yīng)。

3.4  實(shí)驗(yàn)的改善方法及其研究擴(kuò)展

本實(shí)驗(yàn)采取在不同的地理位置，配置多臺服務(wù)終端，從硬件角度考慮，設(shè)計(jì)并實(shí)現(xiàn)了網(wǎng)絡(luò)服務(wù)請求的及時響應(yīng),并取得了良好的實(shí)驗(yàn)效果。

本實(shí)驗(yàn)從軟件的角度考慮,充分利用蟻群算法正反饋的特性，對一臺或多臺服務(wù)器訪問，選擇較為合適的路徑，同樣也達(dá)到網(wǎng)絡(luò)流量負(fù)載均衡的良好效果。

4  蟻群算法的發(fā)展前景

多年來世界各地研究工作者對蟻群算法也進(jìn)行了精心研究和應(yīng)用開發(fā),該算法已被大量應(yīng)用于網(wǎng)絡(luò)路由選擇、機(jī)器人協(xié)作求解、分布式集群計(jì)算、大規(guī)模數(shù)據(jù)挖掘等前沿領(lǐng)域。

以蟻群算法為代表的群智能已成為當(dāng)今分布式

人工智能研究的一個熱點(diǎn)，許多源于蜂群和蟻群模型設(shè)計(jì)的算法已越來越多地被應(yīng)用于企業(yè)的運(yùn)轉(zhuǎn)模式的研究。英國電信公司和美國世界通信公司以電子螞蟻為基礎(chǔ)，對新的電信網(wǎng)絡(luò)管理方法進(jìn)行了試驗(yàn),群智能還被應(yīng)用于工廠生產(chǎn)計(jì)劃的制定和運(yùn)輸部門的后勤管理，美國通用汽車公司、法國液氣公司、荷蘭公路交通部和美國一些移民事務(wù)機(jī)構(gòu)也都采用這種技術(shù)來改善其運(yùn)轉(zhuǎn)機(jī)能。鑒于群智能廣闊的應(yīng)用前景,美國和歐盟均于近幾年開始出資資助基于群智能模擬的相關(guān)研究項(xiàng)目，并在一些院校開設(shè)群體智能的相關(guān)課程。在國內(nèi)，國家自然科學(xué)基金“十五”期間學(xué)科交叉類優(yōu)先資助領(lǐng)域中的認(rèn)知科學(xué)及其信息處理的研究內(nèi)容中也明確列出了群智能領(lǐng)域的進(jìn)化、自適應(yīng)與現(xiàn)場認(rèn)知主題。

5  結(jié)語

目前,蟻群算法在啟發(fā)式方法范疇內(nèi)已逐漸成為一個獨(dú)立的分支,在有關(guān)國際會議上多次作為專題加以討論。隨著研究的深入，蟻群算法將廣泛應(yīng)用于網(wǎng)絡(luò)路由選擇、分布式計(jì)算和搜索組合優(yōu)化，展現(xiàn)出勃勃生機(jī)和廣闊的發(fā)展前景。