ACS算法求解多约束QoS路由问题

谭明佳

(1.武汉大学 计算机学院，湖北 武汉 430079;2.湖北民族学院 信息工程学院，湖北 恩施 445000)

QoS(Quality of Service)路由已成为解决QoS问题的一项关键技术，也是当今网络技术领域内的一个研究热点[1].在进行QoS路由计算时，主要考虑时延、带宽、费用、数据丢失率、时延抖动等特征参数[2].Wang Z等[3]证明了如果QoS路由计算中包含两个以上特征参数时，它就是一个NP-C问题.

ACO(Ant Colony Optimization)元启发式算法是多种蚂蚁算法的一个共同框架，称为ACO算法[4]，是由Dorige等于1999年提出的，包括蚂蚁系统(Ant System，AS)、蚁群系统(Ant Colony System，ACS)、最大-最小蚂蚁系统(MAX-MIN ant system，MMAS)等.ACO算法是一种智能优化算法，用于易于表达但难于求解的离散优化问题，使用agent(人工蚂蚁)群的协作来求解最优解.

ACO算法中的agent实际上代表的是一个随机构造解的过程，在构造解的过程中通过不断地向部分解中添加符合定义的解，从而构造出一个完整的解，因此，ACO算法可以应用到任何能够定义构造性启发式的组合优化问题中，而问题的关键在于如何把某个问题描述成可以被agent用来构造解的表达方式.

相关的研究表明，如果求解的问题能够抽象为在一个无向图中寻找最优路径，ACO算法就能够求出满足给定约束条件的最优路径，从而完成对该问题的求解，因此ACO算法非常适合求解多约束条件QoS路由选择问题.

目前已有的研究成果基本上是先通过修剪不满足QoS需求的边、瓶颈约束条件等，对网络拓扑结构进行预处理，简化网络拓扑结构来进行求解，而且仿真实验的网络规模较小，没有充分考虑算法执行的效率和路由器的处理能力.实际上对于多约束QoS路由计算问题，只需要找出满足约束条件的路径即可[7]，这样还可以进行负载均衡，避免所有的数据包都走同一条路径，造成网络拥塞.

1 ACS算法

ACO算法的执行过程可以被看作是agent在图G=(V,E,T)上的随机移动，其中V为图G顶点的集合，E为图G边的集合，T为信息素向量，τ(r,s)表示顶点r到顶点s的边(r,s)上的信息素.

ACS算法是Gambardella等[4]在1997年提出的，其思想来源于AS算法，但使用了在AS中未出现的新机制，以进一步获得更高的性能.

ACS算法描述如下[4,5]：

输入：一个组合优化问题(S,f,Ω)，S为候选解的集合，f为目标函数，Ω为约束条件的集合.

输出：至今最优解sbest

(1)初始化信息素向量T，即τ(r,s)=τ0>0，∀(r,s)∈E；将m只agent随机地放到n个顶点上.

(2)sbest←null.将至今最优解变量sbest置空，用于在构造解的过程中保存构造的至今最优解.

while(算法终止条件未满足)do

fori=1 tomdo

(3)每只agent构造解s.

位于顶点r的agentk根据伪随机比例规则选择顶点s作为下一个访问的顶点，直到构造完成一个可行解为止.其状态概率转移公式为：

(1)

(2)

(4)if (f(s)≤f(sbest)) or (sbest==null)thensbest←s.

end for

(5)根据sbest更新信息素向量T.

对信息素向量进行局部更新：在构造解的过程中，agent每经过一条边(r,s)，都将立即按式(3)更新该边上的信息素：

τ(r,s)←(1-ξ)×τ(r,s)+ξ×τ0

(3)

对信息素向量进行全局更新：只有一只agent(至今最优agent)被允许在每一次迭代之后释放信息素.信息素向量的全局更新规则为：

τ(r,s)←(1-ρ)×τ(r,s)+ρ×Δτbest(r,s)，∀(r,s)∈sbest

(4)

在ACS算法中，无论是信息素挥发还是信息素释放，都只在构成至今最优解sbest的边上执行.

end while

2 多约束QoS路由计算

设无向赋权图G=(V,E)表示一个计算机网络的拓扑结构，其中V是图G的顶点(如路由器，交换机等交换设备)组成的非空集合，E是图G的边组成的非空集合，每一条边表示相邻两顶点间的通信链路.根据实际应用，顶点和边上都会有一个或多个特征值.

定义1 称顶点序列P(V1,V2,…,Vm)为顶点V1到Vm的一条长度为m的路径[6]，其中∀Vi∈V,1≤i≤m，且∀(Vi-1,Vi)∈E,2≤i≤m.

多约束QoS路由计算即是求出一条从信源s∈V到信宿d∈V的路径P(s,…,d)，使得该路径满足具体业务的服务质量要求.

2.1 多约束QoS路由的数学模型

不失一般性，假定相邻两顶点间最多仅有一条边.对于从信源S∈V到信宿D∈V的路径P(s,…,d)，路径P的特征值可表示为：

路径带宽B(P)=min(BL(l),l∈E1)，其中BL∶E→R+∪{0}为边的可用带宽；

设Bω,Dω,Cω,Lω,Jω分别表示一个路由请求ω的QoS要求的带宽、时延、费用、丢包率和时延抖动约束，则具体约束条件为：

B(P)≥Bω，D(P)≤Dω，C(P)≤Cω，L(P)≤Lω，J(p)≤Jω.

由于不同路由请求对网络服务质量的要求不同，因此各特征值的重要程度也不一样[6]，针对具体路由请求给各特征值赋予不同的权值，设权重向量为：

W=(wb,wd,wc,wl,wj)，且wb+wd+wc+wl+wj=1

对于多约束QoS路由问题，由于各特征值的量化标准不一致，在数值上会出现较大的差异，为此建立式(5)所示的函数，对各特征值进行归一化处理.

(5)

其中：A为常数，对不同特征参数分别取(B(P),Dω,Cω,Lω,Jω).

令F(P)=(F1,F2,F3,F4,F5)T

其中：F1=f(B(P)-Bω)，F2=f(Dω-D(P))，F3=f(Cω-C(P))，F4=f(Lω-L(P))，F5=f(Jω-J(P))

则：多约束QoS路由的数学模型为：maxF=W•F(P)

说明，如果F1、F2、F3、F4、F5中有一个为负数，此时F为负，则这条路径是不能接受的.

2.2 仿真实验

利用上述分析结果，采用ACS算法，用C语言编写程序进行仿真实验.实验用的网络拓扑结构如图1所示[8]，有20个顶点，37条边，网络结构模型中各边的属性参数用三元组(时延，带宽，费用)来描述.为了简化编写程序和实验初值的设置，本文没有考虑网络顶点的特征参数约束.

Agent的数据结构定义为：

structure single_ant

begin

integer tour_F //保存agent路径的F值

integer tour[n] //保存agent(部分)路径

integer visited[n] //标识agent已经访问过的顶点

end

single_ant ant[m] //定义m只agent

integer best //至今最优路径的agent标识符

使用所求的F值对信息素向量的全局更新，只有至今最优agent被更新：

inputbest //读入最优agent的标识符

F←0.1/ant[best].tour_F //读取最优agent的F值

for i=1 to n do

j←ant[best].tour[i]

h←ant[best].tour[i+1]

τ[j][h]←(1-ρ)×τ[j][h]+ρ×F

τ[h][j]←τ[j][h] //信息素矩阵是对称的

end-for

假设对于QoS路由请求(1，20)、(1，18)、(1，19)、(4，15)、(5，15)、(5，16)、(9，10)，其约束条件设置为Bω=60，Dω=100，Cω=100.ACS算法中参数设置为：m=10，ξ=0.1，ρ=0.1，τ0=0.32，q0=0.9，最大迭代次数NcMax=20，带宽权重w1=0.2，时延权重w2=0.65，费用权重w3=0.15.对于QoS路由请求(1，20)，求解过程的进化曲线如图2所示.

图1 网络拓扑及其参数

图2 求解过程的进化曲线

仿真计算的结果如表1所示.

表1 多约束QoS路由优化仿真计算的结果

3 结语

ACS算法求解多约束QoS路由选择的问题，目的是在最短的时间找到满足特征约束条件的可行解，同时减少路由器的计算量，实验证明这种思想是可行的和有效的.利用ACO算法求解实际问题的关键在于ACO算法与实际问题的切入点以及算法的改进策略方面.

[1]段海滨.蚁群算法原理及其应用[M].北京:科学出版社，2005：1-447.

[2]杨华江,陈岩,沈林成.基于改进蚁群算法的多约束QoS路由方法[J].计算机应用与软件,2008,25(5):15-17.

[3]Wang Z,Crowcroft J.Quality of service routing for supporting multimedia applications[J].IEEE Journal on Selected Areas in Communications,1996,14(7):1 228-1 234.

[4]Macro Dorigo,Thomas Stützle.蚁群优化[M].张军,译.北京:清华大学出版社,2007：1-298.

[5]黄翰,郝志峰,吴春国,等.蚁群算法的收敛速度分析[J].计算机学报,2007,30(8):1 344-1 353.

[6]陈岩,杨华江,沈林成.基于再励学习蚁群算法的多约束QoS路由方法[J].计算机科学,2007,34(5):25-27.

[7]王宇,许都,王宏,等.一个效率可观的启发式多约束QoS路由算法[J].计算机应用研究,2008,25(2):345-347.

[8]刘萍,高飞,杨云.基于遗传算法和蚁群算法融合的QoS路由算法[J].计算机应用研究,2007,25(9):224-226.