期刊文献+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息

Genetic algorithm for pareto optimum-based route selection 被引量：1

Genetic algorithm for pareto optimum-based route selection
下载PDF
导出
摘要 A quality of service （QoS） or constraint-based routing selection needs to find a path subject to multiple constraints through a network. The problem of finding such a path is known as the multi-constrained path （MCP） problem, and has been proven to be NP-complete that cannot be exactly solved in a polynomial time. The NPC problem is converted into a multiobjective optimization problem with constraints to be solved with a genetic algorithm. Based on the Pareto optimum, a constrained routing computation method is proposed to generate a set of nondominated optimal routes with the genetic algorithm mechanism. The convergence and time complexity of the novel algorithm is analyzed. Experimental results show that multiobjective evolution is highly responsive and competent for the Pareto optimum-based route selection. When this method is applied to a MPLS and metropolitan-area network, it will be capable of optimizing the transmission performance. A quality of service （QoS） or constraint-based routing selection needs to find a path subject to multiple constraints through a network. The problem of finding such a path is known as the multi-constrained path （MCP） problem, and has been proven to be NP-complete that cannot be exactly solved in a polynomial time. The NPC problem is converted into a multiobjective optimization problem with constraints to be solved with a genetic algorithm. Based on the Pareto optimum, a constrained routing computation method is proposed to generate a set of nondominated optimal routes with the genetic algorithm mechanism. The convergence and time complexity of the novel algorithm is analyzed. Experimental results show that multiobjective evolution is highly responsive and competent for the Pareto optimum-based route selection. When this method is applied to a MPLS and metropolitan-area network, it will be capable of optimizing the transmission performance.
作者 Cui Xunxue Li Qin Tao Qing
机构地区 New Star Research Inst. of Applied Technology Jiangsu Key Lab of Computer Information Processing Technology
出处 《Journal of Systems Engineering and Electronics》 SCIE EI CSCD 2007年第2期360-368,共9页 系统工程与电子技术（英文版）
基金 the Natural Science Foundation of Anhui Province of China (050420212) the Excellent Youth Science and Technology Foundation of Anhui Province of China (04042069).
关键词 Route selection Multiobjective optimization Pareto optimum Multi-constrained path Genetic algorithm. Route selection, Multiobjective optimization, Pareto optimum, Multi-constrained path, Genetic algorithm.
分类号 O224 [理学—运筹学与控制论]
  • 相关文献

参考文献21

  • 1Guerin R,Peris V.Quality-of-service in packet networks:basic mechanisms and directions.Computer Networks,1999,31(3):169-179.
  • 2Chen S,Nahrstedt K.An overview of quality of service routing for next-generation high-speed networks:problems and solutions.IEEE Network,1998,12(6):64-79.
  • 3Kuipers F A.Quality of service routing in the internet:theory,complexity and algorithms.Netherlands,Delft University Press,2004.
  • 4Kuipers F,Van Mieghem P,Korkmaz T,et al.An overview of constraint-based path selection algorithms for QoS routing.IEEE Communications Magazine,2002,40(12):50-55.
  • 5Garey M R,Johnson D S.Computers and intractability:a guide to the theory of NP-completeness.New York:Freeman,1979.
  • 6Kuipers F,Korkmaz T,Krunz M,et al.Performance evaluation of constraint-based path selection algorithms.IEEE Networks,2004,18(5):16-23.
  • 7Wang Z,Crowcroft J.Quality-of-service routing for supporting multimedia applications.IEEE Journal of Selected Areas in Communications,1996,14(7):1228-1234.
  • 8Henig M I.The shortest path problem with two objective functions.European Journal of Operational Research,1985,25(2):281-291.
  • 9Van Meghem P,De Neve H,Kuipers F A.Hop-by-hop quality of service routing.Computer Networks,2001,37(3-4):407-423.
  • 10Chong E I,Maddila S,Morley S.On finding single-source single-destination k shortest paths.Journal Computing and Information,special issue ICCI'95,1995:40-47.

同被引文献25

  • 1熊焰,陈欢欢,苗付友,王行甫.一种解决组合优化问题的量子遗传算法QGA[J].电子学报,2004,32(11):1855-1858. 被引量：50
  • 2郑彦兴,田菁,窦文华.基于Pareto最优的QoS路由算法[J].软件学报,2005,16(8):1484-1489. 被引量：9
  • 3张立,王勇军.一种满足流量工程要求的动态约束路由算法[J].计算机工程,2006,32(23):129-131. 被引量：3
  • 4Knightson K, Morita N, Towle T. NGN Architecture: Generic Principles, Functional Architecture, and Implementatior[J]. Communications Magazine, 2005,43(10):9-56.
  • 5Salama H F, Reeves D S, Viniotis Y. Evaluation of Multicast Routing Algorithms for Real-Time Communication on High-Speed Networks[J]. IEEE Journal on Selected Areas in Communications, 1997,15(3) : 332-345.
  • 6Salama H F, Reeves D S, Viniotis Y. A Distributed Algorithm for Delay-Constrained Unicast Routing [J]. IEEE/ ACM Trans on Networking, 2000,8(2):239-250.
  • 7Wang Z, Crowcroft J. QoS Routing for Supporting Resource Reservation[J]. IEEE Journal on Selected Areas in Communications, 1996, 14(7):1228-1234.
  • 8Yuan X, Liu X. Heuristic Algorithm for Multi-Constrained Quality of Service Routing Problem[C]//Proc of IEEE INFOCOM'01, 2001:844-853.
  • 9Tam W Y, Lui K S, Uludag S, et al. Quality-of-Service Rouring with Path Information Aggregation[J]. Computer Networks, 2007, 51(12):3574-3594.
  • 10Alabbad S H, Woodward M E. Localized Route Selection for Traffic with Bandwidth Guarantees[J]. Simulation, 2007, 83 (3) :259-272.

引证文献1

Journal of Systems Engineering and Electronics
2007年 第2期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部