第3卷第4期 智能系统学报 Vol 3 Ng 4 2008年8月 CAA I Transactions on Intelligent Systems Aug 2008 AntNet的多路径QoS路由算法研究 朱尚明，高大启 华东理工大学信息科学与工程学院，上海200237) 摘要：以AnNεt算法为基础，介绍了蚁群网络路由的问题模型和数据结构，通过引入QoS约束机制，提出了一种基 于AnNet的多路径QoS路由算法.该算法采用具有带宽和时延QoS约束的新规则进行节点选择，并利用改进的节点 信息更新规则以及根据路由表中概率值随机地选择相邻节点转发数据包.性能分析和模拟结果显示，基于AnNεt的 多路径Qo$路由算法具有较快的收敛速度和较好的鲁棒性，能够自适应网络状态的动态变化，同时考虑了QoS约束 和负载平衡问题」 关键词：蚂蚁网络；多路径路由；QoS服务质量约束 中图分类号：TP393文献标识码：A文章编号：1673-4785(2008)04034906 A multipa th QoS routing algorithm ba sed on Ant Net ZHU Shangm ing,GAO Da-qi (School of nfomation Science and Engineering.East China University of Science and Technobgy,Shanghai 200237,China) Abstract:This paper exam ines a mathematical model and data structure or a multipath QoS routing algorithm based on the AnNet algorithm The proposed algorithm selects nodes with a new rule considering both bandwidth and tme-delay QoS constraints Then it transfers data packets using the mproved updating rule for nodal infomation and random ly chooses neighboring nodes to transfer data packets according to probabilities in the routing table Per fomance analysis and siulation results show that the multpath QoS routing algorithm based on AnNet converges faster and is more robust than other algorithms It can automatically adapt to dynam ic variations in netork status while taking into account QoS constraints and bad balancing Keywords:AnNet multpath routing QoS;constraint on service quality 蚁群(ant colny,AC)算法是由意大利学者M 适应路由.实验表明，AnNet路由算法和其他路由 Dorigo?等人于20世纪90年代初提出的一种新型的 算法（如OSPF、SPF等）相比具有一定的优势).本 模拟进化算法).蚁群算法从生物学和仿生学角 文将以AnNet算法为基础，介绍蚁群网络路由的问 度出发，模拟蚂蚁从蚁巢寻找到食物源的最优路径 题模型和数据结构，对其进行改进，引入Qo$约束 的自然行为，通过由候选解组成的群体的进化过程 机制，提出一种基于AnNet的多路径QoS路由算 来寻求最优解」 法，并对其性能进行分析 蚁群算法作为一种求解复杂组合优化问题的计 算智能方法，可以用于求解网络路由问题，近年来国 1问题模型和数据结构 内外学者先后提出了很多方案31，其中以GDi 11问题模型 Cao和M.Dorigo提出的蚂蚁网络(AnNet)为典型 AnNet本质上是一个基于移动Agent的系统， 代表B).AnNet算法通过2类基于移动A gent的前 算法中构造了2类结构基本相同的人工蚂蚁：前行 行蚂蚁和后行蚂蚁共同合作，动态地达到网络的自 蚂蚁Fan和后行蚂蚁Bmt其中Fn表示从源节点到 目的节点的人工蚂蚁，在其向目的节点前进的过程 收稿日期：200708-20 基金项目：因家自然科学基金资助项目(60373073). 中收集信息；Bm表示从目的节点返回源节点的人工 通信作者：朱尚明.Email zhusn@ecust edu cn 蚂蚁，在返回途中根据F收集的信息进行路由表 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net第 3卷第 4期 智 能 系 统 学 报 Vol. 3 №. 4 2008年 8月 CAA I Transactions on Intelligent System s Aug. 2008 AntNet的多路径 QoS路由算法研究 朱尚明 , 高大启 (华东理工大学 信息科学与工程学院 , 上海 200237) 摘 要 :以 AntNet算法为基础 ,介绍了蚁群网络路由的问题模型和数据结构 ,通过引入 QoS约束机制 ,提出了一种基 于 AntNet的多路径 QoS路由算法. 该算法采用具有带宽和时延 QoS约束的新规则进行节点选择 ,并利用改进的节点 信息更新规则以及根据路由表中概率值随机地选择相邻节点转发数据包. 性能分析和模拟结果显示 ,基于 AntNet的 多路径 QoS路由算法具有较快的收敛速度和较好的鲁棒性 ,能够自适应网络状态的动态变化 ,同时考虑了 QoS约束 和负载平衡问题. 关键词 :蚂蚁网络 ;多路径路由 ; QoS;服务质量约束 中图分类号 : TP393 文献标识码 : A 文章编号 : 167324785 (2008) 0420349206 A multipath QoS routing algor ithm based on Ant Net ZHU Shang2m ing, GAO Da2qi (School of Information Science and Engineering, East China University of Science and Technology, Shanghai 200237, China) Abstract: This paper exam ines a mathematicalmodel and data structure for a multipath QoS routing algorithm based on the AntNet algorithm. The p roposed algorithm selects nodes with a new rule considering both bandwidth and time2delay QoS constraints. Then it transfers data packets using the imp roved updating rule for nodal information and random ly chooses neighboring nodes to transfer data packets according to p robabilities in the routing table. Per2 formance analysis and simulation results show that the multipath QoS routing algorithm based on AntNet converges faster and is more robust than other algorithm s. It can automatically adap t to dynam ic variations in network status while taking into account QoS constraints and load balancing. Keywords:AntNet; multipath routing; QoS; constraint on service quality 收稿日期 : 2007208220. 基金项目 :国家自然科学基金资助项目 (60373073). 通信作者 :朱尚明. E2mail: zhusm@ecust. edu. cn. 蚁群 ( ant colony, AC)算法是由意大利学者 M. Dorigo等人于 20世纪 90年代初提出的一种新型的 模拟进化算法 [ 122 ] . 蚁群算法从生物学和仿生学角 度出发 ,模拟蚂蚁从蚁巢寻找到食物源的最优路径 的自然行为 ,通过由候选解组成的群体的进化过程 来寻求最优解. 蚁群算法作为一种求解复杂组合优化问题的计 算智能方法 ,可以用于求解网络路由问题 ,近年来国 内外学者先后提出了很多方案 [ 3210 ] ,其中以 G. D i Caro和 M. Dorigo提出的蚂蚁网络 (AntNet)为典型 代表 [ 3 ] . AntNet算法通过 2类基于移动 Agent的前 行蚂蚁和后行蚂蚁共同合作 ,动态地达到网络的自 适应路由. 实验表明 , AntNet路由算法和其他路由 算法 (如 OSPF、SPF等 )相比具有一定的优势 [ 4 ] . 本 文将以 AntNet算法为基础 ,介绍蚁群网络路由的问 题模型和数据结构 ,对其进行改进 ,引入 QoS约束 机制 ,提出一种基于 AntNet的多路径 QoS路由算 法 ,并对其性能进行分析. 1 问题模型和数据结构 1. 1 问题模型 AntNet本质上是一个基于移动 Agent的系统 , 算法中构造了 2类结构基本相同的人工蚂蚁 :前行 蚂蚁 Fant和后行蚂蚁 Bant . 其中 Fant表示从源节点到 目的节点的人工蚂蚁 ,在其向目的节点前进的过程 中收集信息; Bant表示从目的节点返回源节点的人工 蚂蚁 ,在返回途中根据 Fant收集的信息进行路由表