梁 潇
摘 要：结合多约束QoS组播路由的特点，应用一种自适应蚁群优化算法解决组播路由问题。考虑到实际通信中链路利用率对网络的影响，将网络中链路的带宽转化为链路的代价问题，并在蚁群算法中根据蚂蚁所选路径的代价进行信息素更新，增加了信息素调整的自适应性，同时加快了算法的收敛速度,使得组播路由算法在考虑网络QoS约束的基础上进一步贴合实际网络的需求。
关键词：QoS;蚁群算法;自适应;链路利用率
中图分类号：TN919文献标识码：B
文章编号：1004-373X(2009)05-017-03
Multi-constrained QoS Multicast Routing Algorithm Based on Adaptive Ant Colony Algorithm
LIANG Xiao
(Computer Science and Technology School,Wuhan University of Technology,Wuhan,430070,China)
Abstract：This paper unifies the characteristics of multi-constrained QoS multicast routing problem,by using an improved adaptive ant colony optimization algorithm to solve multicast routing problem.In real network communications,by considering the link utilization influence transforms bandwidth of link into cost problems.According to the cost of the way which ants choose to updating pheromone,increase the adaptability of pheromone updating,then improve convergence ability of algorithm.Cause the multicast routing algorithm in considering the QoS constraints of network on the basis of further conforms to actual network demands.
Keywords：QoS;ant colony algorithm;adaptive;link utilization
0 引 言
随着高速网络技术的发展，与多媒体相关的实时业务应用大量兴起［1］，而有效的组播路由［2］是实现多媒体通信的关键技术。传统的组播通信大多采用“尽力而为”，没有很好地考虑服务质量QoS (Quality of Service)［3］。随着网络的发展，多媒体通信对网络的服务质量QoS提出了越来越高的要求，QoS组播路由问题应运而生。QoS组播路由问题是指在分布的网络中寻找最优路径［4］,要求从源节点出发,历经所有的目的节点,找到一条满足网络路由中延时、带宽、丢包率等约束条件且花费最小的网络路径。Wang Z 等学者已经证明了包含两个及以上约束条件的QoS网络路由是一个NP完全问题［5］。
蚁群算法(Ant Colony Algorithm,ACA)是上世纪90年代意大利学者 M．Dorigo和V．Maniezzo等人通过模拟自然界蚂蚁寻径的行为提出的一种全新启发式算法，它被广泛用于解决各种NP完全问题［6］。现利用一种基于自适应蚁群优化算法，提出考虑网络链路利用率的QoS多约束条件下组播路由解决方法。
1 基本蚁群算法
蚁群算法是一种新近发展起来的、模拟蚂蚁群体觅食行为的仿生优化算法。蚂蚁在寻找食物的运动过程中，能在其经过的路径上分泌一定数量具有气味的称为信息素的物质进行信息传递，并指导自己的运动方向。某一路径上走过的蚂蚁越多，此路径上蚂蚁留下的信息素轨迹也越多，则后来蚂蚁选择该路径的概率也越大，从而更增加了该路径被选择的可能性。同时，路径上的信息素也会随着时间的流逝而不断地挥发，这种机制所得蚂蚁不完全受过去经验的约束，有利于蚂蚁向新的路径搜索。随着时间的推移，蚂蚁就会找到由蚁巢到食物源的最优路径。该算法采用了正反馈并行自催化机制，具有较强的鲁棒性、优良的分布式计算机制、易于与其他方面结合等优点。
蚁群算法利用随机策略，使得进化速度较慢，收敛速度不理想；利用正反馈强化性能较好的解，但导致当前不被选用的路径，往后被选用的概率越来越小，使算法在某些局部最优解附近徘徊，出现停滞现象，而且挥发系数ρ的存在会使那些从未搜索到的路径上的信息素量逐渐减少到0，从而降低算法的全局搜索能力。若ρ过大，会使以前搜索过的路径被再次选择的可能性过大，影响算法的全局搜索能力，易于陷入局部最优解；若ρ过小，虽然可以提高算法的全局搜索能力，但会使算法的收敛速度降低。1996年Gambardella和Dorigo提出了一种修正的蚁群算法(ACS)［7］，该算法对信息素的更新策略作了相应的改进，即使用：
(1) 局部信息更新，蚂蚁从城市i转移到城市j后，路径上的信息素按式(1)进行更新：
τ璱j(t+1)=(1－ξ)τ璱j(t)+ξτ璷
(1)
式中：ξ∈(0,1)，τ璷为常数。
采用局部信息更新策略减小了已选择过的路径再次被选择的概率，提高了算法的全局搜索能力。
(2) 全局信息更新，针对全局最优解所属边按式(2)进行信息素更新：
τ璱j(t+n)=(1－ρ)τ璱j(t)+ρΔτ琯b璱j(t)，ρ∈(0,1)
(2)
式中:Δτ琯b璱j(t)=1/L㻅b;L㻅b为当前全局最优解的路径长度。采用全局信息更新策略，增强了全局最优解路径上的信息素，加强了算法的正反馈作用，从而加快算法的收敛速度。
2 QoS网络路由模型
2.1 QoS组播路由问题的基本概念和网络模型定义
就组播路由而言，网络通常表示成一个带权图G=(V，E)，其中V代表节点集合;E代表网络中双向链路集合,关联每条链路的参数就是该链路的QoS度量。在此，E表示网络中双向链路的集合［8］；S为源节点，S∈V；M∈{V－{S}}为目的节点集，S，M组成组播树T(s,M)。对于任一链路e∈E，可定义某些属性：延时函数：delay(e):E∈R+；费用函数cost(e):E∈R+；带宽函数bandwidth(e):E∈R+。对于任一网络节点n∈V，定义某些属性：延迟函数delay(n):V∈R+；费用函数cost(n):V∈R+，由此存在如下关系：
delay(p璗(s,t))=∑e∈p璗(s,t)delay(e)+∑n∈p璗(s,t)delay(n)(3)
cost(T(s,M))=∑e∈T(s,M)cost(e)+∑n∈T(s,M)cost(n)
(4)
bandwidth(p璗(s,t))=min{bandwidth(e),e∈p璗(s,t)}
(5)
式中:p璗(s,t)为组播树T(s,M)上源点s到终点t的路径。
QoS组播路由问题是要寻找一颗组播树T(s,M)满足：
延时约束：
delay(p璗(s,t)) (6) 带宽约束： bandwidth(p璗(s,t))>B (7) 式中：B表示带宽约束;D玺表示延时约束。 费用函数(目标函数)可描述为在所有满足条件的组播树中，cost(T(s,M))最小。 2.2 网络负载和链路利用率 为考虑链路利用率的情况,将链路代价定义为［9］： cost(e)=Xbandwidth(e), X=108 (8) E中的每条边对应网络中的一条链路e璱,j,其中i表示上游路由器;j表示下游路由器。e璱,j具有三个属性：Maximum Bandwidth(MB)，Reserved Bandwidth(RB),Unreserved Bandwidth(UB)。因此有对任意e∈E，鯩B(i,j),RB(i,j)和UB(i,j)，并且MB(i,j)=RB(i,j)+UB(i,j)。在式(8)的基础上,定义式(9),用来计算图G中每条链路的代价。 cost(e)=XMB(i,j),RB(i,j)=0XUB(i,j),RB(i,j)≠0且UB(i,j)≠0∞,RB(i,j)≠0且UB(i,j)=0 (9) 由式(9)可知,剩余带宽越大,链路代价越小;反之,链路代价越大。 3 自适应蚁群算法的QoS组播问题实现 3.1 适应度函数 适应度函数是蚁群进行路径选择的依据，也就是蚂蚁从初始路径集Ω璱中选择第j条路径的概率： f(p璲)=phe瑸璲(s,D璱)∑p璱∈Ω璱phe瑸璱(s,D璱) (10) 式中: phe瑸璲(s,D璱)是路径p璲(s,D璱)上的分泌物强度，它表明某条路径上的分泌物强度越大，该路径被选中的概率也就越大。初始状态时各条路径上的分泌物强度相同。 3.2 蚂蚁的信息素调整 蚂蚁寻找路径时，按以下规则进行信息素调整： (1) 对蚂蚁所经过的路径进行分泌物强度调整。其中a是常量参数;cost(e)为该路径的代价;phe瑸璱(s,D璱)为源节点S到目的节点D璱的路径上的分泌物强度。调整后,有: phe瑸璱(s,D璱)=phe瑸璱(s,D璱)+acost(e) (11) 上述公式与文献［10］不同，信息素的调整不是固定值，而是根据所选择路径的代价来调整的，并且路径代价受带宽影响，是根据链路利用率来确定的。增加信息调整的自适应性，同时也加快了收敛速度。 (2) 当蚂蚁都走完一条路径时，对所有路径进行分泌物挥发调整。其中ρ是挥发度;Δ为各条路径上的初始信息强度。 phe瑸璱(s,D璱)=(1－ρ)*phe瑸璱(s,D璱),phe瑸璱(s,D璱)>0.05Δ D璱∈D 0,其他 (12) (3) 当蚂蚁都找到所有目的节点，组成一颗组播树时，再按式(13)进行信息素调整，即: phe瑸璱(s,D璱)=phe瑸璱(s,D璱)+Bcost(T) (13) 式中:B为常量参数;cost(T)为该组播树的代价;p璱(s,D璱)是被选路径。 3.3 算法步骤 Step 1：生成初始路径集。找出从源节点S到每个目的节点D璱∈D (i=1,2,…,m)满足延时约束的有效路径，并组成初始路径集Ω璱。 Step 2：初始化α,β,B,ANTn和初始集中各条路径上的信息强度Δ。 Step 3：从源节点发出ANTn只蚂蚁，按式(10)计算路径集Ω璱中每条路径的适应度，每只蚂蚁再按赌轮旋转规则从中选择一条路径，再按式(11)进行分泌物强度调整。 Step 4：当每只蚂蚁都完成一条路径选择后，按式(12)进行分泌物挥发性调整。 Step 5：重复执行Step 3和Step 4，直到蚂蚁找到所有目的节点的路径，每只蚂蚁寻找到的路径各组成一颗组播树。计算各组播树的代价(相同链路的代价只计算一次)，判断是否大多数蚂蚁收敛于同一组播树，如果是，则该组播树为最优路径，退出程序；否则，用代价最小的组播树替代代价最大的组播树，转执行Step 6。 Step 6：蚂蚁按原路返回，并按式(13)调整返回路径上的分泌物强度，再转Step 3执行。 4 实验仿真和算法分析 本文采用改进的Waxman网络拓扑仿真模型［11］,利用Matlab 7.0进行仿真，其特点是每对节点之间按概率p(u,v)=βexp(－d(u,v)/2an)相连，其中d(u,v)为u,v两节点之间的距离，并且按照Salama和Reeves在Waxman基础上的网络生成算法使平均节点度达到指定值。参数α,β分别控制网络中长边和短边的比例以及边的密度，n为网络节点个数。参数的选取如表1所示。表2列出了30个节点的网络仿真试验中，两种不同算法在不同延时约束条件下的组播树代价。每次试验分别进行20次，其中代价值分别是20次试验得到的平均值。从表2容易看出，算法IAAC比算法AAC在相同延时条件下生成组播树的代价要小。图1描述了两种算法在30个网络节点的网络仿真中，组播树的代价随迭代次数的变化情况。从图中可以看出，IAAC算法在收敛速度上要优于AAC算法，并且在最优组播树的代价上也要优于AAC算法。图2显示了两种算法在随着网络节点数变化时，组播树代价的变化情况。随着网络节点数的增加，IAAC算法所得最优组播树的代价低于AAC算法所得最优组播树的代价，并且最优组播树的代价增加比AAC算法得到最优组播树代价的增加速度要慢。通过仿真试验，本文改进的自适应蚁群算法能以更快的收敛速度得到最优组播树，并且最优组播树的代价相对原有自适应蚁群算法要更优。 表1 蚁群算法参数选取 αβQρn 0.20.31000.530 表2 30个网络节点运行20次的延时与代价的关系 202428333640 AAC365359358355350346 IAAC355348347345342330 图1 组播树代价与迭代次数 图2 组播树代价与网络节点数 5 结 语 本文提出了一种应用自适应蚁群算法并结合实际网络的链路利用率的多约束QoS组播路由算法。将链路利用和网络负载考虑到组播路由中，使得网络路由问题的研究更符合实际网络的需求。在运用自适应蚁群时，结合信息素更新的特点，将链路代价考虑到其中，使得信息调整的自适应性加强，同时收敛速度得到改善。 参考文献 ［1］Chockler G V,et al.Group Communication Specifications:A Comprehensive Study［J］.ACM Computing Surveys,2001,33(4):1-43. ［2］Wang B,Hou C J.A Survey on Multicast Routing and Its QoS Extensions:Problems,Algorithms and Protocols［J］.IEEE Network Magazine,2000,14(1):22-36.
［3］Xiao X P,Ni L M.Internet QoS:the Big Picture［J］.IEEE Network Magazine,1999,13(2):1-13.
［4］邹德莉,郝应光.基于非精确状态信息的QoS组播路由算法［J］.微电子学与计算机,2006,23(9):66-72.
［5］Wang Zheng,Crowcroft J.Quality of Service Routing forSupporting Multimedia Applications［J］.IEEE Journal on Selected Areas in Communications,1996,14(7):1 228-1 234.
［6］Dorigo M,Maniezzo V,Colorni A.Ant System:Optimization by a Colony Cooperating Agents［J］.IEEE Trans.on Systems,Man,and Cybernetics-bart B:Cybernetics,1996,26(1):29-41.
［7］李昌兵.基于计算智能的多播QoS路由技术研究.重庆:重庆大学,2007.
［8］王应征，石冰心.基于遗传算法的时延受限代价最小组播路由选择方法.通信学报，2002，23(3)：112-117.
［9］Cisco.OSPF Design Guide［EB/OL］.http://www.cisco.com/warp/public/104/1.html,2004-02.
［10］李生红，刘泽民.基于蚁群算法的组播路由调度方法.计算机工程，2001,27(4):63-65.
［11］Waxman B M.Routing of Multiple Connections.IEEE Journal on Selected Area in Communications,1986，6(9)：1 622-1 671.
［12］田炳丽，刘常波，解贵新.旋转货架拣选作业优化的交叉蚁群算法求解.现代电子技术,2008,31(12):59-61.
作者简介
梁 潇 女，1983年出生，湖北监利人，硕士研究生。主要研究方向为智能计算。
军 事 通 信
冯 正等：多线程串口通信技术在GPS导航中的应用
