王盛明，盧秉亮，孔宇菲

(1.沈陽航空職業(yè)技術(shù)學院，沈陽 110034;2.沈陽航空航天大學計算機學院，沈陽 110136;3.沈陽航空航天大學圖書館，沈陽 110136)

1 引言

QoS算法計算出最能滿足服務(wù)質(zhì)量要求的最短路徑，負載均衡算法［1－6］用于計算受到多個約束條件限制的路由，同時還要滿足網(wǎng)絡(luò)性能的要求，達到優(yōu)化網(wǎng)絡(luò)資源使用的目的?；谪撦d均衡策略在路由時同時考慮網(wǎng)絡(luò)的拓撲結(jié)構(gòu)，所以該算法有可能選取一條路徑較長但負載較輕的通路，這要好于選取路徑最短但負載較重的通路，它可以使得業(yè)務(wù)流更均勻地分布在整個網(wǎng)絡(luò)內(nèi)。

文獻［1－6］中的算法有效緩解了最短路由上的擁塞。但考慮到網(wǎng)絡(luò)中數(shù)據(jù)流的到達是隨機的，假設(shè)先到的低速率數(shù)據(jù)流占據(jù)大容量鏈路，而后到的高速率數(shù)據(jù)流因各條路由上的空閑容量均不滿足其帶寬要求而無法得到服務(wù)，因而造成了吞吐率及網(wǎng)絡(luò)資源利用率的降低。

造成這種局限性的最根本原因是由于這些負載均衡算法都是靜態(tài)的，一條路由一旦建立，是不會被其它路由搶占資源的，也不會自動重選路由到更合適的新路由。而在某些情況下，如果一條路由能夠主動將其所承載的數(shù)據(jù)流重選到另一條路由上去，就能使該數(shù)據(jù)流原先所在的路由上原本較小的空閑容量變成較大的空閑容量，供給一個高帶寬要求的數(shù)據(jù)流使用，既能保證原先數(shù)據(jù)流傳輸不被中斷，又能增大網(wǎng)絡(luò)吞吐率和提高網(wǎng)絡(luò)資源的利用率。

由此，提出了蟻群算法實現(xiàn)MPLS(多協(xié)議標簽交換)網(wǎng)絡(luò)負載均衡，增大網(wǎng)絡(luò)吞吐率和提高網(wǎng)絡(luò)資源的利用率。

2 負載均衡模型

用G=(V，E，C)抽象描述網(wǎng)絡(luò)拓撲。V是網(wǎng)絡(luò)節(jié)點集合，E是網(wǎng)絡(luò)鏈路集合，參數(shù)C則是E和V的容量和其它一些約束條件限制。用集合K表示網(wǎng)絡(luò)中的LSP(標簽交換路徑)請求。對任意k∈K，用三元組(sk，tk，lk)表示，其中 sk，tk分別為入口節(jié)點和出口節(jié)點，lk表示(sk，tk)業(yè)務(wù)流的帶寬需求。kij表示 LSPk是否經(jīng)由鏈路(i，j)，(i，j)∈E，hk為LSPk的跳數(shù)限制。優(yōu)化的目標是使最大鏈路利用率最小化，這樣可以使業(yè)務(wù)流向相對輕載的鏈路轉(zhuǎn)移，使得由于流量分布不均衡造成擁塞的可能性降到最低［4］。另一方面，在最大鏈路利用率最小化的同時，相應(yīng)鏈路的剩余帶寬得到最大化，因而網(wǎng)絡(luò)對將來到達的連接請求具有更高的接納能力，而不需要對已存在的連接進行重新路由。

如果在很長一段時間內(nèi)只有少數(shù)幾個低速率數(shù)據(jù)流在發(fā)送，則網(wǎng)絡(luò)中的大容量鏈路可能長時間處于空閑狀態(tài)。同時由于分配給數(shù)據(jù)流的空閑容量與其帶寬要求非常接近，所以這些算法不能很好地適應(yīng)數(shù)據(jù)流的突發(fā)性，有可能由于一段時間內(nèi)數(shù)據(jù)流突發(fā)速率很高而丟包。

3 蟻群算法

3.1 應(yīng)用蟻群算法進行聚類的原理［7］

蟻群聚類算法是將聚類數(shù)據(jù)隨機散布到一個二維網(wǎng)格中，模仿n個虛擬螞蟻在二維網(wǎng)格內(nèi)對聚類數(shù)據(jù)的搬動?？蛰d的螞蟻遇到一個聚類數(shù)據(jù)時計算拾起數(shù)據(jù)概率，滿足拾起條件時拾起數(shù)據(jù)并隨機運動;滿載螞蟻走到新的位置時計算所背負數(shù)據(jù)與周圍數(shù)據(jù)的相似性，滿足條件時放下數(shù)據(jù)然后繼續(xù)移動。重復上述數(shù)據(jù)搬運過程，實現(xiàn)相似數(shù)據(jù)的聚集。

給定一路由(信息素)X，把每個路由Xj(j=1，2，...，N)看作是一只螞蟻，根據(jù)上述特征進行特征提取，則可將每個路由提取為特征的二維向量，最優(yōu)路由就是這些具有不同特征的信息素尋找各自類別的過程。設(shè)任意一信息素Xi與Xj的相似度即兩者之間的距離為dij，采用歐氏距離計算公式則如下式所示:

上式中m為螞蟻信息素的特征維數(shù)，這里m為2，p是加權(quán)因子，根據(jù)信息素特征各分量影響聚類的程度確定。通過利用啟發(fā)式引導函數(shù)可反映信息素之間的相似度，啟發(fā)函數(shù)越大，信息素歸于相同特征聚類的概率就越大。啟發(fā)式引導函數(shù)如式(2)所示:

各路徑上的信息素計算公式為:

其中r為設(shè)置的一閾值，當反應(yīng)兩信息素之間的距離dij小于設(shè)置的閾值時，則螞蟻在這條路徑上的信息激素為1，否則螞蟻在該條路徑上的信息激素為0。

對于任意一信息素(螞蟻)Xi選擇轉(zhuǎn)移到Xj的轉(zhuǎn)移概率為:

其中ηij(t)是啟發(fā)式引導函數(shù)，τij為螞蟻在路徑上的信息素，α，β分別是信息素聚類過程中啟發(fā)式引導函數(shù)ηij(t)和路徑上積累的信息素函數(shù)τij對路徑選擇的影響因子。S={Xs|dis≤r，s=1，2，...，N}為每個螞蟻(信息素)的可行路徑集合，s為所有的可選路徑。

隨著螞蟻的不斷移動，各路徑上的信息素量會發(fā)生變化。經(jīng)過一次循環(huán)，各路徑上的信息量可根據(jù)下式進行調(diào)整:

其中，ρ為信息素揮發(fā)系數(shù)，則1－ρ表示信息素殘留因子，為了防止信息素的無限累積，ρ的取值范圍為(0，1);Vτij為本次循環(huán)中路徑信息素增量，由下式計算得出:

其中Q為一大于0的整數(shù)，dkj為像素之間的距離(相似度)。

3.2 蟻群算法的流程［7］

下面給出的蟻群算法流程如下:

(1)初始化 α，β，r，Q，ρ等參數(shù)，并設(shè)置循環(huán)次數(shù)nc;

(2)根據(jù)原始路由設(shè)置初始聚類中心，并根據(jù)二階微分值將聚類中心劃分為邊緣、目標和中間三類。

(3)計算網(wǎng)絡(luò)中每個信息素點(節(jié)點)與聚類中心的相似度函數(shù)，啟發(fā)式引導函數(shù)。

(4)開始聚類，對每個信息素與可行聚類中心進行轉(zhuǎn)移概率選擇計算，選取概率最大的聚類中心進行聚類。

(5)一次蟻群聚類后，更新信息激素，根據(jù)所得到的聚類個數(shù)，計算各類的聚類中心，計算類間與類間距離，當類間與類間距離之差小于閾值時，合并兩類，更新聚類中心的特征值。

(6)判斷循環(huán)次數(shù)，若循環(huán)次數(shù)大于nc，停止運行，否則轉(zhuǎn)步驟(4)繼續(xù)執(zhí)行。

4 仿真實驗及結(jié)果分析

以圖1所示的網(wǎng)絡(luò)為例，假設(shè)數(shù)據(jù)源發(fā)送的順序是Src3在第0.1s開始發(fā)送、Src2在第2.0s開始發(fā)送、Src1在第4.0s開始發(fā)送，應(yīng)用網(wǎng)絡(luò)仿真軟件NS2.26對原有的負載均衡路由算法與本文所提出的負載均衡蟻群聚類算法進行仿真分析，如圖2所示。

負載均衡路由算法見仿真結(jié)果1，負載均衡蟻群聚類算法見仿真結(jié)果2，從在第4.0s到第6.0s之間，網(wǎng)絡(luò)資源利用率接近于100%。但在第0.1s到第4.0s之間，Src1尚未發(fā)送數(shù)據(jù)包，網(wǎng)絡(luò)資源利用率限制在60%以下。

圖1 網(wǎng)絡(luò)拓撲結(jié)構(gòu)圖

圖2 負載均衡路由算法和蟻群算法

負載均衡蟻群聚類算法在0.2s～2.2s時間內(nèi)利用率略高于負載均衡路由算法(DLB)，DLB在2s～4s時間內(nèi)在0.6附近波動，負載均衡蟻群聚類算法在2.2s～5s時間內(nèi)達到了0.8，在5s以后就達到了100%，原因在于蟻群聚類算法完成最后結(jié)果需要的時間比負載均衡路由算法長，總體上，負載均衡蟻群聚類算法優(yōu)于負載均衡路由算法。

5 結(jié)束語

負載均衡蟻群聚類算法能不同程度的緩解最短路由上的擁塞問題，其性能優(yōu)于靜態(tài)負載均衡算法和動態(tài)負載均衡算法。本文僅研究了無優(yōu)先級情況下的負載均衡算法，在多優(yōu)先級情況下的負載均衡算法尚待進一步研究。

［1］杜永波，李毓麟.MPLS的帶優(yōu)先級的負載均衡算法研究［J］.計算機工程與應(yīng)用，2003(34):165－166.

［2］蔣國明，魏仰蘇，孟兆航.MPLS的基于最小干涉的負載均衡算法研究［J］.計算機工程與設(shè)計，2007(2):371 －372，476.

［3］張中山，隆克平，程時端.MPLS業(yè)務(wù)量工程中負載均衡算法的研究［J］.北京郵電大學學報，2001(3):46－50.

［4］賈艷萍，孟相如，麻海園，郝自建.基于MPLS流量工程的多路徑約束負載均衡方法［J］.計算機應(yīng)用，2007(3):522－524.

［5］劉紅，白棟，丁煒.應(yīng)用于MPLS網(wǎng)絡(luò)負載均衡的啟發(fā)式自適應(yīng)遺傳算法［J］.通信學報，2003(10):39－45.

［6］王紅梅，趙政，趙增華.基于延遲的MPLS網(wǎng)絡(luò)流級多徑負載平衡［J］.計算機應(yīng)用，2004(3):4 －5，12.

［7］Sim K M，Sun W H.Ant colony optimization for routing and load － balancing:Survey and new directions［J］.IEEE，2003，33(5):33 －41.