王盛明，卢秉亮，孔宇菲

(1.沈阳航空职业技术学院，沈阳 110034;2.沈阳航空航天大学计算机学院，沈阳 110136;3.沈阳航空航天大学图书馆，沈阳 110136)

1 引言

QoS算法计算出最能满足服务质量要求的最短路径，负载均衡算法［1－6］用于计算受到多个约束条件限制的路由，同时还要满足网络性能的要求，达到优化网络资源使用的目的。基于负载均衡策略在路由时同时考虑网络的拓扑结构，所以该算法有可能选取一条路径较长但负载较轻的通路，这要好于选取路径最短但负载较重的通路，它可以使得业务流更均匀地分布在整个网络内。

文献［1－6］中的算法有效缓解了最短路由上的拥塞。但考虑到网络中数据流的到达是随机的，假设先到的低速率数据流占据大容量链路，而后到的高速率数据流因各条路由上的空闲容量均不满足其带宽要求而无法得到服务，因而造成了吞吐率及网络资源利用率的降低。

造成这种局限性的最根本原因是由于这些负载均衡算法都是静态的，一条路由一旦建立，是不会被其它路由抢占资源的，也不会自动重选路由到更合适的新路由。而在某些情况下，如果一条路由能够主动将其所承载的数据流重选到另一条路由上去，就能使该数据流原先所在的路由上原本较小的空闲容量变成较大的空闲容量，供给一个高带宽要求的数据流使用，既能保证原先数据流传输不被中断，又能增大网络吞吐率和提高网络资源的利用率。

由此，提出了蚁群算法实现MPLS(多协议标签交换)网络负载均衡，增大网络吞吐率和提高网络资源的利用率。

2 负载均衡模型

用G=(V，E，C)抽象描述网络拓扑。V是网络节点集合，E是网络链路集合，参数C则是E和V的容量和其它一些约束条件限制。用集合K表示网络中的LSP(标签交换路径)请求。对任意k∈K，用三元组(sk，tk，lk)表示，其中 sk，tk分别为入口节点和出口节点，lk表示(sk，tk)业务流的带宽需求。kij表示 LSPk是否经由链路(i，j)，(i，j)∈E，hk为LSPk的跳数限制。优化的目标是使最大链路利用率最小化，这样可以使业务流向相对轻载的链路转移，使得由于流量分布不均衡造成拥塞的可能性降到最低［4］。另一方面，在最大链路利用率最小化的同时，相应链路的剩余带宽得到最大化，因而网络对将来到达的连接请求具有更高的接纳能力，而不需要对已存在的连接进行重新路由。

如果在很长一段时间内只有少数几个低速率数据流在发送，则网络中的大容量链路可能长时间处于空闲状态。同时由于分配给数据流的空闲容量与其带宽要求非常接近，所以这些算法不能很好地适应数据流的突发性，有可能由于一段时间内数据流突发速率很高而丢包。

3 蚁群算法

3.1 应用蚁群算法进行聚类的原理［7］

蚁群聚类算法是将聚类数据随机散布到一个二维网格中，模仿n个虚拟蚂蚁在二维网格内对聚类数据的搬动。空载的蚂蚁遇到一个聚类数据时计算拾起数据概率，满足拾起条件时拾起数据并随机运动;满载蚂蚁走到新的位置时计算所背负数据与周围数据的相似性，满足条件时放下数据然后继续移动。重复上述数据搬运过程，实现相似数据的聚集。

给定一路由(信息素)X，把每个路由Xj(j=1，2，...，N)看作是一只蚂蚁，根据上述特征进行特征提取，则可将每个路由提取为特征的二维向量，最优路由就是这些具有不同特征的信息素寻找各自类别的过程。设任意一信息素Xi与Xj的相似度即两者之间的距离为dij，采用欧氏距离计算公式则如下式所示:

上式中m为蚂蚁信息素的特征维数，这里m为2，p是加权因子，根据信息素特征各分量影响聚类的程度确定。通过利用启发式引导函数可反映信息素之间的相似度，启发函数越大，信息素归于相同特征聚类的概率就越大。启发式引导函数如式(2)所示:

各路径上的信息素计算公式为:

其中r为设置的一阈值，当反应两信息素之间的距离dij小于设置的阈值时，则蚂蚁在这条路径上的信息激素为1，否则蚂蚁在该条路径上的信息激素为0。

对于任意一信息素(蚂蚁)Xi选择转移到Xj的转移概率为:

其中ηij(t)是启发式引导函数，τij为蚂蚁在路径上的信息素，α，β分别是信息素聚类过程中启发式引导函数ηij(t)和路径上积累的信息素函数τij对路径选择的影响因子。S={Xs|dis≤r，s=1，2，...，N}为每个蚂蚁(信息素)的可行路径集合，s为所有的可选路径。

随着蚂蚁的不断移动，各路径上的信息素量会发生变化。经过一次循环，各路径上的信息量可根据下式进行调整:

其中，ρ为信息素挥发系数，则1－ρ表示信息素残留因子，为了防止信息素的无限累积，ρ的取值范围为(0，1);Vτij为本次循环中路径信息素增量，由下式计算得出:

其中Q为一大于0的整数，dkj为像素之间的距离(相似度)。

3.2 蚁群算法的流程［7］

下面给出的蚁群算法流程如下:

(1)初始化 α，β，r，Q，ρ等参数，并设置循环次数nc;

(2)根据原始路由设置初始聚类中心，并根据二阶微分值将聚类中心划分为边缘、目标和中间三类。

(3)计算网络中每个信息素点(节点)与聚类中心的相似度函数，启发式引导函数。

(4)开始聚类，对每个信息素与可行聚类中心进行转移概率选择计算，选取概率最大的聚类中心进行聚类。

(5)一次蚁群聚类后，更新信息激素，根据所得到的聚类个数，计算各类的聚类中心，计算类间与类间距离，当类间与类间距离之差小于阈值时，合并两类，更新聚类中心的特征值。

(6)判断循环次数，若循环次数大于nc，停止运行，否则转步骤(4)继续执行。

4 仿真实验及结果分析

以图1所示的网络为例，假设数据源发送的顺序是Src3在第0.1s开始发送、Src2在第2.0s开始发送、Src1在第4.0s开始发送，应用网络仿真软件NS2.26对原有的负载均衡路由算法与本文所提出的负载均衡蚁群聚类算法进行仿真分析，如图2所示。

负载均衡路由算法见仿真结果1，负载均衡蚁群聚类算法见仿真结果2，从在第4.0s到第6.0s之间，网络资源利用率接近于100%。但在第0.1s到第4.0s之间，Src1尚未发送数据包，网络资源利用率限制在60%以下。

图1 网络拓扑结构图

图2 负载均衡路由算法和蚁群算法

负载均衡蚁群聚类算法在0.2s～2.2s时间内利用率略高于负载均衡路由算法(DLB)，DLB在2s～4s时间内在0.6附近波动，负载均衡蚁群聚类算法在2.2s～5s时间内达到了0.8，在5s以后就达到了100%，原因在于蚁群聚类算法完成最后结果需要的时间比负载均衡路由算法长，总体上，负载均衡蚁群聚类算法优于负载均衡路由算法。

5 结束语

负载均衡蚁群聚类算法能不同程度的缓解最短路由上的拥塞问题，其性能优于静态负载均衡算法和动态负载均衡算法。本文仅研究了无优先级情况下的负载均衡算法，在多优先级情况下的负载均衡算法尚待进一步研究。

［1］杜永波，李毓麟.MPLS的带优先级的负载均衡算法研究［J］.计算机工程与应用，2003(34):165－166.

［2］蒋国明，魏仰苏，孟兆航.MPLS的基于最小干涉的负载均衡算法研究［J］.计算机工程与设计，2007(2):371 －372，476.

［3］张中山，隆克平，程时端.MPLS业务量工程中负载均衡算法的研究［J］.北京邮电大学学报，2001(3):46－50.

［4］贾艳萍，孟相如，麻海园，郝自建.基于MPLS流量工程的多路径约束负载均衡方法［J］.计算机应用，2007(3):522－524.

［5］刘红，白栋，丁炜.应用于MPLS网络负载均衡的启发式自适应遗传算法［J］.通信学报，2003(10):39－45.

［6］王红梅，赵政，赵增华.基于延迟的MPLS网络流级多径负载平衡［J］.计算机应用，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.