基于蚁群优化算法的数据包路由技术研究
|
摘要
随着当前网络所要处理的实时业务的不断增多,网络能够提供的服务质量问题越来越多地受到人们的关注。路由问题作为网络数据传输的重要方面,它性能的好坏直接关系到整个网络的性能。对于包含延迟、延迟抖动、带宽、丢包率和最小花费等约束条件在内的服务质量(QoS)路由问题的研究逐渐成为网络技术研究领域需要探索的主要方向。目前,对于QoS路由问题主要采用如蚁群算法等的启发式算法进行求解。蚁群算法以其优良的适应性,较强的可移植性,本质并行性,易于与其它算法结合等优点在解决各种复杂的NP完全问题方面挥发了重要作用。
论文通过对基本蚁群算法的深入研究,提出了一种改进的动态自适应蚁群算法(DAAO),并对如何应用它来解决QoS组播路由问题做出了详尽的分析和设计,最后通过将真实的网络拓扑结构抽象成无向带权连通图,对问题的求解过程进行了仿真。仿真结果表明该算法能够正确、有效的求解QoS路由问题。
In the current network, with the increase of real-time business which needs to be deal with, network quality of service problems are concerned increasingly. As an important aspect of network data transmission, routing problem is directly related to overall network. Good routing can improve the performance of network, and vice versa. The study of quality of service (QoS) routing problem that include of delay, delay jitter, bandwidth, packet loss rate and minimum cost and other constraints, has becomes the main direction of network technology research. At present, mainly use the heuristic algorithm, thus as ant colony algorithm to solve the QoS routing problem. Ant colony algorithm play an important role in solving complex NP-complete problems by it's the advantages of excellent adaptability, strong portability, the nature of parallelism, easy-to-combining with other algorithms.
In this paper, I proposed an algorithm named dynamic self-adaptive ant colony algorithm (DAAO) by in-depth study of basic ant colony algorithm, and the article has made a detailed analysis and design on how to use it to solve the QoS multicast routing problem, and simulated the problem solving process by abstracted the real network topology into a weighted undirected connected graph. The simulation results show that the algorithm is correct, and effective for solving QoS routing problem.
论文通过对基本蚁群算法的深入研究,提出了一种改进的动态自适应蚁群算法(DAAO),并对如何应用它来解决QoS组播路由问题做出了详尽的分析和设计,最后通过将真实的网络拓扑结构抽象成无向带权连通图,对问题的求解过程进行了仿真。仿真结果表明该算法能够正确、有效的求解QoS路由问题。
In the current network, with the increase of real-time business which needs to be deal with, network quality of service problems are concerned increasingly. As an important aspect of network data transmission, routing problem is directly related to overall network. Good routing can improve the performance of network, and vice versa. The study of quality of service (QoS) routing problem that include of delay, delay jitter, bandwidth, packet loss rate and minimum cost and other constraints, has becomes the main direction of network technology research. At present, mainly use the heuristic algorithm, thus as ant colony algorithm to solve the QoS routing problem. Ant colony algorithm play an important role in solving complex NP-complete problems by it's the advantages of excellent adaptability, strong portability, the nature of parallelism, easy-to-combining with other algorithms.
In this paper, I proposed an algorithm named dynamic self-adaptive ant colony algorithm (DAAO) by in-depth study of basic ant colony algorithm, and the article has made a detailed analysis and design on how to use it to solve the QoS multicast routing problem, and simulated the problem solving process by abstracted the real network topology into a weighted undirected connected graph. The simulation results show that the algorithm is correct, and effective for solving QoS routing problem.
引文
[1]E.Crawley,R.Nair,B.Rajagopalan,and H.Sandick.A Framework for QoS-based Routing in the Internet[S].RFC no.2386,Internet RFC,Aug.1998
[2]Dorigo M,Luca Maria Gambardella.Ant Colony System:A Cooperative Learning Approach to the Traveling Salesman Problem[J].IEEE Transactions on Evolutionary Computation,1997,1(1):53-66
[3]屈建伟.QoS多播路由算法及仿真研究[D].武汉:武汉理工大学,2005
[4]Bin Wang and Jennifer C.Hou.Multicast Routing and Its QoS Extension:Problems,Algorithms,and Protocols[J].IEEE Network,2000,1:22-36
[5]Bonabean E,Dorigo M,Theraulaz G.Inspiration of optimization from social insect behavior[J].Nature,2000,406(6):39-42
[6]Stuetzle T.Hoos H H.The Max-min Ant System and Local Search for the Traveling Salesman Problem.NJ:IEEE Press.1997.309-314
[7]胡娟,王常青.韩伟等.蚁群算法及其实现方法研究.计算机仿真.第21卷第7期2004年7月
[8]吴启迪.汪雷.智能蚁群算法及其应用[M].上海科技教育出版社,2004:83-84
[9]Singh G.Das S,Gosavi S V.Pujar S.Ant Colony Algorithms for Steiner Trees:an Application to Routing in Sensor Networks,2004
[10]刘小梅,张君静.蚁群优化算法基本原理及其应用.西部探矿工程.2008.10:240-243
[11]Gambardella L M.Dorigo M.Solving Symmetric and Asymmetric TSP by Ant Colonies.1996
[12]Marco Dorigo,Mauro Birattari,and Thomas Stiitzle.Ant,Colony Optimization:Artificial Ants as a Computational Intelligence Technique[J].IEEE Computational Intelligence Magazine,2006,11:28-39
[13]封国剑,范俊峰,高随祥.基于改进蚁群优化算法的分布式多播路由算法.计算机工程.第32卷第3期2006年2月.
[14]李领治,郑洪源,丁秋林.一种基于改进蚁群算法的选播路由算法.电子与信息学报.第29卷第2期2007年2月
[15]谢铎,周井泉.基于蚁群算法的QoS最佳路由选择问题的研究.计算机工程与应用.2007,43(3)
[16]高尚,杨静宇.最短路的蚁群算法收敛性分析.科学技术与工程.第6卷第3期2006年2月
[17]Duan H B.Ant colony algorithms:theory and applications[M].Beijing:Science Press,2005
[18]柯良军,冯祖仁,冯远静.有限级信息素蚁群算法[J].自动化学报.2006,32(2):296-303
[19]王健,刘衍珩,朱建启.全局自适应蚁群优化算法.小型微型计算机系统.Vol.29 No.6 2008
[20]Shtovba S D Ant algorithms:theory and applications 2005(4)
[21]Xiao Xipeng.Internet QoS,A Big Picture,M].IEEE Network,March 1999,13(12):8-189
[22]陈岩,杨华江,朱华勇等.基于配队蚁群算法的QoS组播路由方法.系统仿真学报.Vol.20No.5 Mar.2008
[23]孙力娟,王汝传.基于蚁群算法和遗传算法融合的QoS组播路由问题求解.电子学报.Vol34 No.8 Aug.2006
[24]马立肖,赵占芳,王楠等.一种基于蚁群系统的多约束QoS路由模型.网络与通信.1008-0570(2007)01-3-0133-03
[25]Kwang Mong,Sim Weng,Hong Sun.Ant colony optimization for routing and load-balancing:survey and new directions[J].IEEE Trans on systems,man and cybernetics-part A:systems and humans,2003,33(5):560-572
[26]刘先锋,舒林,陈松乔等.基于QoS约束的多播路由研究.计算机工程与应用.2005,2
[27]朱冬梅,盛建瓴.通信网络中QoS多播路由技术研究.华北科技学院学报.第5卷第2期2008年4月
[28]陈礼青,福泰,陶拯.多约束QoS组播路由优化算法研究[J].计算机与数字工程.2006,34(12):11.14
[29]屈建伟,李腊元.一种混合蚂蚁算法及其在QoS多播路由中的应用[J].武汉理工大学学报.2005,29(6):932-935
[30]王庆美.蚁群算法及其在QoS组播路由中的应用研究:[硕士学位论文].成都:电子科技大学,2009
[31](意)多里戈(Marco Dorigo),(德)Thomas Stutzle著,张军等译.蚁群优化[M].北京:清华大学出版社,2005
[32]李士勇.蚁群算法及其应用.[M]哈尔滨工业大学出版社,2004.9
[33]段海滨.蚁群算法原理及其应用.[M]科学出版社,2005.12
[34]刘彦鹏.蚁群优化算法的理论研究及其应用:[博士学位论文].杭州:浙江大学,2008
[35]杨亚南.蚁群算法参数优化及其应用:[硕士学位论文].南京:南京理工大学,2008
[36]高尚,汤可宗,静宇.一种新的基于混合蚁群算法的聚类方法[J].微电子学与计算机.2006,23(12):38-40
[37]王晰.基于QOS约束的组播路由算法研究;[博士学位论文].南京:浙南京理工大学,2004
[38]王志广.基于QoS约束组播路由算法及协议研究:[硕士学位论文].石家庄:河北工业大学,2006
[39]王征应,石冰心.基于启发式遗传算法的QoS组播路由问题求解[J].计算机学报.2001,24(1):55-61
[40]王建新,裴慧民.基于IP的QoS体系结构及路由策略研究.电信快报.2001,(10)
[41]汤可宗,江新姿,张磊等.一种求解旅行商问题的改进蚁群算法.东华理工学院学报.Vol.30 No.4 Dec.2007
[2]Dorigo M,Luca Maria Gambardella.Ant Colony System:A Cooperative Learning Approach to the Traveling Salesman Problem[J].IEEE Transactions on Evolutionary Computation,1997,1(1):53-66
[3]屈建伟.QoS多播路由算法及仿真研究[D].武汉:武汉理工大学,2005
[4]Bin Wang and Jennifer C.Hou.Multicast Routing and Its QoS Extension:Problems,Algorithms,and Protocols[J].IEEE Network,2000,1:22-36
[5]Bonabean E,Dorigo M,Theraulaz G.Inspiration of optimization from social insect behavior[J].Nature,2000,406(6):39-42
[6]Stuetzle T.Hoos H H.The Max-min Ant System and Local Search for the Traveling Salesman Problem.NJ:IEEE Press.1997.309-314
[7]胡娟,王常青.韩伟等.蚁群算法及其实现方法研究.计算机仿真.第21卷第7期2004年7月
[8]吴启迪.汪雷.智能蚁群算法及其应用[M].上海科技教育出版社,2004:83-84
[9]Singh G.Das S,Gosavi S V.Pujar S.Ant Colony Algorithms for Steiner Trees:an Application to Routing in Sensor Networks,2004
[10]刘小梅,张君静.蚁群优化算法基本原理及其应用.西部探矿工程.2008.10:240-243
[11]Gambardella L M.Dorigo M.Solving Symmetric and Asymmetric TSP by Ant Colonies.1996
[12]Marco Dorigo,Mauro Birattari,and Thomas Stiitzle.Ant,Colony Optimization:Artificial Ants as a Computational Intelligence Technique[J].IEEE Computational Intelligence Magazine,2006,11:28-39
[13]封国剑,范俊峰,高随祥.基于改进蚁群优化算法的分布式多播路由算法.计算机工程.第32卷第3期2006年2月.
[14]李领治,郑洪源,丁秋林.一种基于改进蚁群算法的选播路由算法.电子与信息学报.第29卷第2期2007年2月
[15]谢铎,周井泉.基于蚁群算法的QoS最佳路由选择问题的研究.计算机工程与应用.2007,43(3)
[16]高尚,杨静宇.最短路的蚁群算法收敛性分析.科学技术与工程.第6卷第3期2006年2月
[17]Duan H B.Ant colony algorithms:theory and applications[M].Beijing:Science Press,2005
[18]柯良军,冯祖仁,冯远静.有限级信息素蚁群算法[J].自动化学报.2006,32(2):296-303
[19]王健,刘衍珩,朱建启.全局自适应蚁群优化算法.小型微型计算机系统.Vol.29 No.6 2008
[20]Shtovba S D Ant algorithms:theory and applications 2005(4)
[21]Xiao Xipeng.Internet QoS,A Big Picture,M].IEEE Network,March 1999,13(12):8-189
[22]陈岩,杨华江,朱华勇等.基于配队蚁群算法的QoS组播路由方法.系统仿真学报.Vol.20No.5 Mar.2008
[23]孙力娟,王汝传.基于蚁群算法和遗传算法融合的QoS组播路由问题求解.电子学报.Vol34 No.8 Aug.2006
[24]马立肖,赵占芳,王楠等.一种基于蚁群系统的多约束QoS路由模型.网络与通信.1008-0570(2007)01-3-0133-03
[25]Kwang Mong,Sim Weng,Hong Sun.Ant colony optimization for routing and load-balancing:survey and new directions[J].IEEE Trans on systems,man and cybernetics-part A:systems and humans,2003,33(5):560-572
[26]刘先锋,舒林,陈松乔等.基于QoS约束的多播路由研究.计算机工程与应用.2005,2
[27]朱冬梅,盛建瓴.通信网络中QoS多播路由技术研究.华北科技学院学报.第5卷第2期2008年4月
[28]陈礼青,福泰,陶拯.多约束QoS组播路由优化算法研究[J].计算机与数字工程.2006,34(12):11.14
[29]屈建伟,李腊元.一种混合蚂蚁算法及其在QoS多播路由中的应用[J].武汉理工大学学报.2005,29(6):932-935
[30]王庆美.蚁群算法及其在QoS组播路由中的应用研究:[硕士学位论文].成都:电子科技大学,2009
[31](意)多里戈(Marco Dorigo),(德)Thomas Stutzle著,张军等译.蚁群优化[M].北京:清华大学出版社,2005
[32]李士勇.蚁群算法及其应用.[M]哈尔滨工业大学出版社,2004.9
[33]段海滨.蚁群算法原理及其应用.[M]科学出版社,2005.12
[34]刘彦鹏.蚁群优化算法的理论研究及其应用:[博士学位论文].杭州:浙江大学,2008
[35]杨亚南.蚁群算法参数优化及其应用:[硕士学位论文].南京:南京理工大学,2008
[36]高尚,汤可宗,静宇.一种新的基于混合蚁群算法的聚类方法[J].微电子学与计算机.2006,23(12):38-40
[37]王晰.基于QOS约束的组播路由算法研究;[博士学位论文].南京:浙南京理工大学,2004
[38]王志广.基于QoS约束组播路由算法及协议研究:[硕士学位论文].石家庄:河北工业大学,2006
[39]王征应,石冰心.基于启发式遗传算法的QoS组播路由问题求解[J].计算机学报.2001,24(1):55-61
[40]王建新,裴慧民.基于IP的QoS体系结构及路由策略研究.电信快报.2001,(10)
[41]汤可宗,江新姿,张磊等.一种求解旅行商问题的改进蚁群算法.东华理工学院学报.Vol.30 No.4 Dec.2007