基于核心路由器的蚂蚁算法研究与应用
摘要
随着Internet日益广泛的应用，其规模也越来越大，通信流量也迅速增长，这就迫使其传输平台向更高的通信带宽方向发展。因此，建设高速度，高宽带的骨干网就显得十分必要。
合理高效的路由选择方式不仅可以保障全网的正常运行，还能够提高网络的接通率，而将Internet网的接通率提高，既可以尽量避免交换机不堪重负甚至崩溃的情况，又能降低网络的运营成本。提高网络的接通率相当大的程度上依赖于路由选择策略的改变。因此，TCP／IP网的动态路由选择问题变得越来越重要。蚂蚁算法能够有效地选择一条最优路径，但忽视了实际网络中的另外一个问题：最优路径一旦形成，所有的数据都从最优路径传输，这样一来，处于该路径上的路由器，尤其是在骨干网络中心节点(即多条路径交汇处)的路由器将承受巨大的数据传输量，因而很容易造成“瓶颈”现象。目前采用的一个办法是在骨干网络中心节点处设置交换容量达到或超过千兆比特级的，具有高密度高速端口的核心路由器来扩展带宽和提高数据传送速度以达到解决骨干网络中心节点处的数据拥塞的目的。但这样大大提高了网络成本，并且无法解决最优路径上非核心路由器(又名接入路由器)上的数据拥塞问题。
根据上述问题，本文提出一种对蚂蚁算法的改进方法—基于核心路由器的蚂蚁算法：在骨干网络的各核心路由器上相互发送蚂蚁寻找各核心路由器之间的最优路径，这样可比传统蚂蚁算法通过让“蚂蚁”周游整个网络后来寻找最优路径要快很多。另一方面，该算法通过对最优路径上，在各个核心路由器之间的非核心路由器设置上下限两个阈值。当某个非核心路由器A上的数据流量达到上限阈值时表明该路由器即将处于拥塞。这时，它邻近的核心路由器将A看成是一个“障碍物”，利用蚂蚁算法能够绕过障碍物寻找最优路径的特点，可以在这两个核心路由器之间重新寻找一条不包括路由器A在内的“次优”路径。这样后续的数据将从“次优”路径传输以达到对A路由器进行分流。经过一段时间分流后，当数据流量下降到下限阈值时，就可以重新启动原最优路径，从而达到了既分流又采用最优路径传输的目的。
With the widely application in internet, its scale has become larger and larger, and its flow increased quickly too, it is forced to develop its transmission to high bandwidth. So the construction of network with high speed and wide bandwidth becomes essential.
The reasonability and high efficiency in routing can not only guarantees the net works well, but also can increase the rate of connection. In this way, it can avoid collapsing because of unbearable heavy burden in swiches but also can decrease the cost of the network. Increasing the rate of connection in network largely depend on the methods of routing. Therefore, the dynamic routing method in TCP/IP network is becoming more and more important. The ant algorithm can choose a superior path availably, but another problem that neglected in actual network is that, once the superior path is formed, all dates will be delivered from this path, in this case, the router on this path, especially the router in center node of the network (several paths hands over to remit a place) will bear the enormous data delivering. As a result, the "bottle-neck" phenomenon formed easily. Currently, a method to solve this problem is to establishes a core router in center node of the network, which has the commutation capacity attains or over thousand MBits and has super-speed port. While it is larger increasing the network costs, and can't resolve the data jam of non-core router in superior path.
In this case, this paper presents an improvement ant algorithm which based on the core routers: on each core router, sending ants to look for the superior path mutually between each other, it will be much quicker than the traditional ant algorithm which is looking for the superior path by pass the whole network. On the other hand, in the superior path, the algorithm se two values on non-core routers to avoid jam of data when the non-core router A is becoming jam, the near core-router treat A as a " stumbling block", so it will choose another second superior path which is not including A, in this way, the data is share by the second superior path. When the value reduced, it will choose the first superior path again. As a result, this algorithm can not only find the superior path, but also avoid jam of flow.
合理高效的路由选择方式不仅可以保障全网的正常运行，还能够提高网络的接通率，而将Internet网的接通率提高，既可以尽量避免交换机不堪重负甚至崩溃的情况，又能降低网络的运营成本。提高网络的接通率相当大的程度上依赖于路由选择策略的改变。因此，TCP／IP网的动态路由选择问题变得越来越重要。蚂蚁算法能够有效地选择一条最优路径，但忽视了实际网络中的另外一个问题：最优路径一旦形成，所有的数据都从最优路径传输，这样一来，处于该路径上的路由器，尤其是在骨干网络中心节点(即多条路径交汇处)的路由器将承受巨大的数据传输量，因而很容易造成“瓶颈”现象。目前采用的一个办法是在骨干网络中心节点处设置交换容量达到或超过千兆比特级的，具有高密度高速端口的核心路由器来扩展带宽和提高数据传送速度以达到解决骨干网络中心节点处的数据拥塞的目的。但这样大大提高了网络成本，并且无法解决最优路径上非核心路由器(又名接入路由器)上的数据拥塞问题。
根据上述问题，本文提出一种对蚂蚁算法的改进方法—基于核心路由器的蚂蚁算法：在骨干网络的各核心路由器上相互发送蚂蚁寻找各核心路由器之间的最优路径，这样可比传统蚂蚁算法通过让“蚂蚁”周游整个网络后来寻找最优路径要快很多。另一方面，该算法通过对最优路径上，在各个核心路由器之间的非核心路由器设置上下限两个阈值。当某个非核心路由器A上的数据流量达到上限阈值时表明该路由器即将处于拥塞。这时，它邻近的核心路由器将A看成是一个“障碍物”，利用蚂蚁算法能够绕过障碍物寻找最优路径的特点，可以在这两个核心路由器之间重新寻找一条不包括路由器A在内的“次优”路径。这样后续的数据将从“次优”路径传输以达到对A路由器进行分流。经过一段时间分流后，当数据流量下降到下限阈值时，就可以重新启动原最优路径，从而达到了既分流又采用最优路径传输的目的。
With the widely application in internet, its scale has become larger and larger, and its flow increased quickly too, it is forced to develop its transmission to high bandwidth. So the construction of network with high speed and wide bandwidth becomes essential.
The reasonability and high efficiency in routing can not only guarantees the net works well, but also can increase the rate of connection. In this way, it can avoid collapsing because of unbearable heavy burden in swiches but also can decrease the cost of the network. Increasing the rate of connection in network largely depend on the methods of routing. Therefore, the dynamic routing method in TCP/IP network is becoming more and more important. The ant algorithm can choose a superior path availably, but another problem that neglected in actual network is that, once the superior path is formed, all dates will be delivered from this path, in this case, the router on this path, especially the router in center node of the network (several paths hands over to remit a place) will bear the enormous data delivering. As a result, the "bottle-neck" phenomenon formed easily. Currently, a method to solve this problem is to establishes a core router in center node of the network, which has the commutation capacity attains or over thousand MBits and has super-speed port. While it is larger increasing the network costs, and can't resolve the data jam of non-core router in superior path.
In this case, this paper presents an improvement ant algorithm which based on the core routers: on each core router, sending ants to look for the superior path mutually between each other, it will be much quicker than the traditional ant algorithm which is looking for the superior path by pass the whole network. On the other hand, in the superior path, the algorithm se two values on non-core routers to avoid jam of data when the non-core router A is becoming jam, the near core-router treat A as a " stumbling block", so it will choose another second superior path which is not including A, in this way, the data is share by the second superior path. When the value reduced, it will choose the first superior path again. As a result, this algorithm can not only find the superior path, but also avoid jam of flow.
引文
[1] 李苏剑，常志明．MRP系统下的物流管理．企业物流，2000，6
[2] 顾军华，侯向丹等．基于蚂蚁算法的QoS组播路由问题求解．河北工业大学学报，2002，4
[3] 马良．瓶颈TSP的蚂蚁系统优化．计算机工程，2001，9
[4] 王征应，石冰心．基于启发式遗传算法的QoS组播路由问题求解．计算机学报，2002．6
[5] 马良，蒋馥．多目标旅行售货员问题的蚂蚁算法求解．系统工程理论方法应用，1998，41(14)
[6] ZhangSu-Bing, ShiGuo-Ying, LiuZe-Min, ZhouZheng. QoSRouting basedon antalgorithm. Journal of Circuitsand Sys-tems, 2000, 5(1): 1-5(inChinese)(张素兵，石国英，刘泽民，周正．基于蚂蚁算法的OoS路由)
[7] 李生红，刘泽民，周正等．ATM网上基于蚂蚁算法的VC路由选择方法．通信学报，2001，1
[8] 张素兵，刘泽民．ATM业务控制中的一种新的神经网络方法．北京：北京邮电大学学报，2001，6
[9] 李腊元，李春林．多OoS约束的多播路由协议．软件学报，2004，15(2)
[10] 王征应，石冰心．基于启发式遗传算法的QoS组播路由问题求解．计算机学报，2001，24(1)
[11] 吕国英，刘泽民，周正．基于蚂蚁算法的分布式QoS路由选择算法．通信学报，2001，22(9)
[12] 张素兵，刘泽民．基于蚂蚁算法的延时受限分布式多播路由研究．通信学报，2001，22(3)
[13] Bertsimas. DJ, Simchi-Le A new generation of vechile routing research: Robust Alogrithtns. Addressing Uncertaint). Operations Res. 1996. 44(2): 286-304
[14] 袁庆达，杜文，周再铃．带软时间窗的混和车队车辆路线问题的模型和算法研究，计算机学报，2002，4(1)
[15] 蔡延光，钱积新，孙优贤．带时间窗的多重运输调度问题的自适应Tabu Search算法．系统工程理论与实践，2002，12
[16] 胡祥培，许智超，杨德礼．智能运筹学与动态系统实时优化控制．管理科学学报，2002，8(3)
[17] 李军，车辆调度问题的分派启发式算法，系统工程理论与实践，1999，1
[18] 高培旺，唐忠旺．目标等值面切割定界法与割平面法组合求解整数规划．管理科学学报，2003，4
[19] 蒲在毅，任建军．用标号实现单源最短路径问题的迪杰斯特(dijkstra)算法．四川师范学院学报(自然科学版)2003，3
[20] Hiroshi KISE, Mingzhe LU, Guiyan H U, Tan LI, Heuristics for Improving Operational Perfomance of Permutation Circulation-type vehicle Routing System, Journal of Xia men University(Natural Sc-ience), Vol 4t
[21] 陈晓伟，张悟移，耿继武．节约法在配送线路选择与应用．昆明理工大学学报(理工版)，2003，4
[22] 蔡延光，钱积新，孙优贤．带时间窗的多重运输调度问题的自适应Tabu Search算法．系统工程理论与实践，2000，12
[23] 蔡延光，钱积新，孙优贤．多重运输调度问题的分枝定界算法及界限估计．系统工程与电子技术，1998，4
[24] 蔡延光，钱积新，孙优贤．多重运输调度问题的模拟退火算法．系统工程理论与实践，1998，10
[25] DEMENULEMEESTER LL. APOR E G, LOUEAUX F1. Optimal sequencing of skip collections anddeliveries [J], Journal of the Operations Raerch Society, 1997, (1): 57-64
[26] 王会云．论物流系统化的基本方法．物流技术，2000，2
[27] 吴卫．基于多项服务质量的组播．电子技术应用，2000，266(8)
[28] 苏一旦，李桂．电子商务物流管理信息系统中的最优(佳)径算法研究．计算机工程与应用，2002，8
[29] Koksalan M, Sural H, Kirca O. A location-distribution application for a beer company[J]. Europen Journalof Operational Reseatch, 1995, 80: 60-24
[30] 忻斌建，汪镭，吴启迪．蚂蚁算法的研究现状和应用及蚂蚁智能体的硬件实现．同济大学学报，2002，1
[31] Dorgom M, Bonabeau E, Therauiaz Ant Algorithm and stigmergy[J]. Future Generation ComputerSystems, 2000, 16(6): 851-871
[32] Dorigo 1, Caro G D, Gambardeia L. MI. Antalgorithms for discrete of mization[J]. Artificial Life, 1999, 5(2): 137-72
[33] AGNETIS A. Planning the routing mix in FASs to minimize total transportation time [J], International Jotunalof Flexible Manufacturing Systems, 1996, (2): 131-157.
[34] 白国仲，毛经中．C指派问题．系统工程理论与实践，2003，3
[35] 张纪会，徐心和．带遗忘因子的蚁群算法．系统仿真学报，2000，2
[36] 宋华，胡左浩．现代物流与供应链管理，北京：经济管理出版社，2001，5
[37] Li Layuan, Li Chunlin A Heuristic Algorithm for QoS Multicast Routing, Journal of System Engineeringand Electronics, Vol,13, No,4, 2002, pp, 73-78
[38] 梅绍祖．INTERNET与电子商务和物流，物流技术，1998，3
[39] 马良．离散系统优化的蚂蚁算法研究．上海交通大学管理学院，1999，3
[40] 张维明．信息系统建模技术与应用．北京：电子工业出版社，1997，4
[41] 朗茂祥．物流配送车辆调度问题的模型和算法研究．北方交通大学学报，2002．5
[42] 吴自库，刘国柱．配送问题的数学模型及近似算法．青岛化工学院学报 1998，19
[43] 陆锋，基于层次空间推理的交通网络行车最优路径算法．武汉测绘大学学报，2000，18
[44] AGNETIS A Planning the routing as to minimize total transportation time [J], International Journal of Flexible Manufacturing Systems, 1996, 4
[45] Barcia P; Jornsten K, Imporved Langrangean Decompostion: An Application to the Generalized Assignment Problem. Europen Jouranl of Operational Reserch, 1996, 4
[46] 高洪深．决策支持系统理论方法案例．北京：清华大学出版社，1996，2
[47] 孙劲光．背包问题算法设计及分析．辽宁工程技术大学学报(自然科学版)2002，4
[48] 李娟，方平，周明．一种求解背包问题的混和遗传算法．南昌航空工业学院学报，1998，3
[49] 李士勇，陈永强，蚁群算法及其应用[M]，哈尔滨工业大学出版社，2004年
[50] Min H, Jayararn an Raesh Srivastava R. Combined location problem: a synthesis and future research directions,Eourpean Journal of Operational Research, 1998,108
[2] 顾军华，侯向丹等．基于蚂蚁算法的QoS组播路由问题求解．河北工业大学学报，2002，4
[3] 马良．瓶颈TSP的蚂蚁系统优化．计算机工程，2001，9
[4] 王征应，石冰心．基于启发式遗传算法的QoS组播路由问题求解．计算机学报，2002．6
[5] 马良，蒋馥．多目标旅行售货员问题的蚂蚁算法求解．系统工程理论方法应用，1998，41(14)
[6] ZhangSu-Bing, ShiGuo-Ying, LiuZe-Min, ZhouZheng. QoSRouting basedon antalgorithm. Journal of Circuitsand Sys-tems, 2000, 5(1): 1-5(inChinese)(张素兵，石国英，刘泽民，周正．基于蚂蚁算法的OoS路由)
[7] 李生红，刘泽民，周正等．ATM网上基于蚂蚁算法的VC路由选择方法．通信学报，2001，1
[8] 张素兵，刘泽民．ATM业务控制中的一种新的神经网络方法．北京：北京邮电大学学报，2001，6
[9] 李腊元，李春林．多OoS约束的多播路由协议．软件学报，2004，15(2)
[10] 王征应，石冰心．基于启发式遗传算法的QoS组播路由问题求解．计算机学报，2001，24(1)
[11] 吕国英，刘泽民，周正．基于蚂蚁算法的分布式QoS路由选择算法．通信学报，2001，22(9)
[12] 张素兵，刘泽民．基于蚂蚁算法的延时受限分布式多播路由研究．通信学报，2001，22(3)
[13] Bertsimas. DJ, Simchi-Le A new generation of vechile routing research: Robust Alogrithtns. Addressing Uncertaint). Operations Res. 1996. 44(2): 286-304
[14] 袁庆达，杜文，周再铃．带软时间窗的混和车队车辆路线问题的模型和算法研究，计算机学报，2002，4(1)
[15] 蔡延光，钱积新，孙优贤．带时间窗的多重运输调度问题的自适应Tabu Search算法．系统工程理论与实践，2002，12
[16] 胡祥培，许智超，杨德礼．智能运筹学与动态系统实时优化控制．管理科学学报，2002，8(3)
[17] 李军，车辆调度问题的分派启发式算法，系统工程理论与实践，1999，1
[18] 高培旺，唐忠旺．目标等值面切割定界法与割平面法组合求解整数规划．管理科学学报，2003，4
[19] 蒲在毅，任建军．用标号实现单源最短路径问题的迪杰斯特(dijkstra)算法．四川师范学院学报(自然科学版)2003，3
[20] Hiroshi KISE, Mingzhe LU, Guiyan H U, Tan LI, Heuristics for Improving Operational Perfomance of Permutation Circulation-type vehicle Routing System, Journal of Xia men University(Natural Sc-ience), Vol 4t
[21] 陈晓伟，张悟移，耿继武．节约法在配送线路选择与应用．昆明理工大学学报(理工版)，2003，4
[22] 蔡延光，钱积新，孙优贤．带时间窗的多重运输调度问题的自适应Tabu Search算法．系统工程理论与实践，2000，12
[23] 蔡延光，钱积新，孙优贤．多重运输调度问题的分枝定界算法及界限估计．系统工程与电子技术，1998，4
[24] 蔡延光，钱积新，孙优贤．多重运输调度问题的模拟退火算法．系统工程理论与实践，1998，10
[25] DEMENULEMEESTER LL. APOR E G, LOUEAUX F1. Optimal sequencing of skip collections anddeliveries [J], Journal of the Operations Raerch Society, 1997, (1): 57-64
[26] 王会云．论物流系统化的基本方法．物流技术，2000，2
[27] 吴卫．基于多项服务质量的组播．电子技术应用，2000，266(8)
[28] 苏一旦，李桂．电子商务物流管理信息系统中的最优(佳)径算法研究．计算机工程与应用，2002，8
[29] Koksalan M, Sural H, Kirca O. A location-distribution application for a beer company[J]. Europen Journalof Operational Reseatch, 1995, 80: 60-24
[30] 忻斌建，汪镭，吴启迪．蚂蚁算法的研究现状和应用及蚂蚁智能体的硬件实现．同济大学学报，2002，1
[31] Dorgom M, Bonabeau E, Therauiaz Ant Algorithm and stigmergy[J]. Future Generation ComputerSystems, 2000, 16(6): 851-871
[32] Dorigo 1, Caro G D, Gambardeia L. MI. Antalgorithms for discrete of mization[J]. Artificial Life, 1999, 5(2): 137-72
[33] AGNETIS A. Planning the routing mix in FASs to minimize total transportation time [J], International Jotunalof Flexible Manufacturing Systems, 1996, (2): 131-157.
[34] 白国仲，毛经中．C指派问题．系统工程理论与实践，2003，3
[35] 张纪会，徐心和．带遗忘因子的蚁群算法．系统仿真学报，2000，2
[36] 宋华，胡左浩．现代物流与供应链管理，北京：经济管理出版社，2001，5
[37] Li Layuan, Li Chunlin A Heuristic Algorithm for QoS Multicast Routing, Journal of System Engineeringand Electronics, Vol,13, No,4, 2002, pp, 73-78
[38] 梅绍祖．INTERNET与电子商务和物流，物流技术，1998，3
[39] 马良．离散系统优化的蚂蚁算法研究．上海交通大学管理学院，1999，3
[40] 张维明．信息系统建模技术与应用．北京：电子工业出版社，1997，4
[41] 朗茂祥．物流配送车辆调度问题的模型和算法研究．北方交通大学学报，2002．5
[42] 吴自库，刘国柱．配送问题的数学模型及近似算法．青岛化工学院学报 1998，19
[43] 陆锋，基于层次空间推理的交通网络行车最优路径算法．武汉测绘大学学报，2000，18
[44] AGNETIS A Planning the routing as to minimize total transportation time [J], International Journal of Flexible Manufacturing Systems, 1996, 4
[45] Barcia P; Jornsten K, Imporved Langrangean Decompostion: An Application to the Generalized Assignment Problem. Europen Jouranl of Operational Reserch, 1996, 4
[46] 高洪深．决策支持系统理论方法案例．北京：清华大学出版社，1996，2
[47] 孙劲光．背包问题算法设计及分析．辽宁工程技术大学学报(自然科学版)2002，4
[48] 李娟，方平，周明．一种求解背包问题的混和遗传算法．南昌航空工业学院学报，1998，3
[49] 李士勇，陈永强，蚁群算法及其应用[M]，哈尔滨工业大学出版社，2004年
[50] Min H, Jayararn an Raesh Srivastava R. Combined location problem: a synthesis and future research directions,Eourpean Journal of Operational Research, 1998,108