QoS路由算法及在PTN网管中应用研究
|
摘要
随着时代的发展和科学技术的推动,通信网络也不断的向前发展。在经历了PDH和SDH传送网络之后,通信网正向着PTN传送网的发展。PTN传送网是以分组IP为内核的传送网络,是下一代的传送网络。为了管理PTN传送网,PTN网络管理系统是必不可少的。
在PTN网络中,所有的业务都承载在PW上,在确定了业务的源端点和目的端点后,根据相应的QoS约束寻找合适的PW称为寻找路由。由于网络和相关业务的复杂性,自动路由就成为必然。而寻找带QoS约束的路由问题是一个NP-难问题,在解决此类问题时,常规的方法难以满足要求,解决该类问题的方法一般是采用智能启发式算法,如遗传算法,蚁群算法等。
本文主要研究了遗传算法和蚁群算法,在分析了遗传和蚁群算法的优缺点之后,结合两者的优点提出了一种基于蚁群的混合算法。并将该算法用于解决QoS路由问题,具体所做的工作包括如下几个方面：
1.介绍了课题背景,PTN技术的发展现状和PTN网管的相关情况,并详细的介绍了QoS路由模型。
2.分析了该PTN网管系统的架构及系统中的关键技术,介绍了在该系统中业务的创建流程。详细说明了自动路由和人工路由的优缺点,提出了自动的路由的必要性,以自动路由为本文的研究点。
3.在解决QoS自动路由时,分析了遗传算法和蚁群算法的原理,流程以及在QoS路由问题中的应用。在深刻理解算法的优缺点基础上,提出了一种以蚁群算法为基础的混合算法,该算法先利用遗传算法的全局寻优能力和快速性,生成初始解,然后利用部分解来初始化蚁群信息素,并利用蚁群算法生成最终解。
4.利用实验仿真来验证算法的有效性,实验仿真表明该算法在求精方面优于遗传和蚁群算法,在时间性能上,优于蚁群算法,该算法是有效的。并将该算法应用于实际的PTN网管中,用于创建业务时自动路由的寻找。
根据实验仿真和最后在实际应用中表明,该混合算法比基本遗传算法和蚁群算法有着更良好的效果,是一种效果良好的算法。
With the development of the times and promotion of science and technology, the communication networks continue to move forward. Experienced in the PDH and SDH transmission network, the communication network is toward the development of transmission network of PTN. PTN transmission network based on IP as its core, is the next generation of transmission network. In order to manage PTN transmission network, network management system is essential.
In PTN network, all business is carrying on the PW, after determined the source endpoint and purpose endpoint of the business, according to the corresponding authored QoS constraint find suitable PW called looking for routing. Due to the complexity of the network and related business, automatic routing is inevitable. In search of the routing problem with QoS constraint is a NP-hard problem. to solve such problems conventional method can not satisfy the requirements of this problem and solving methods are generally using intelligent heuristic algorithm, such as genetic algorithm, the ant colony algorithm, etc.
This paper mainly studies the genetic algorithm and the ant colony algorithm genetic,after analyzing the advantages and disadvantages of the two algorithms, then the proposed hybrid algorithm combining with the advantages of both which based on ant colony. And the algorithm is used to solve a QoS routing problem, specific work done including the following aspects:
1. Introduced the subject of background, and PTN technology development status and related network management, then detial the QoS routing model.
2. Analyzes the structure and framework of PTN element management system and the key technology which are introduced in the creation of the system of business process. Detail the automatic routing and artificially routing advantages and disadvantages, puts forward the necessity of automatic routing for this paper, and take automatic routing as the research points.
3. When in solving the QoS automatic routing, analyzed the genetic algorithm and the principle of ant colony algorithm, process and the application in the QoS routing problem. after profound understanding its advantages and disadvantages of the two algorithms, was presented based on ant colony algorithm based on hybrid algorithm, this algorithm by using the genetic algorithm first the global optimization ability and quickness, initial solution, then uses part of the solution to initialize ant colony pheromones, and use the ant colony algorithm generated eventually solutions.
4. Use experimental simulation to verify the efficiency of the algorithm, experimental results show that this algorithm in refinement aspects due to genetic and ant colony algorithm. in time performance, better than ant colony algorithm, this algorithm is effective. And the algorithm was applied to the actual PTN net, used to create business automatic routing search.
According to the simulation results and in practical application shows that the hybrid algorithm has better effect than the basic genetic algorithm and the ant colony algorithm, it is a kind of good method.
在PTN网络中,所有的业务都承载在PW上,在确定了业务的源端点和目的端点后,根据相应的QoS约束寻找合适的PW称为寻找路由。由于网络和相关业务的复杂性,自动路由就成为必然。而寻找带QoS约束的路由问题是一个NP-难问题,在解决此类问题时,常规的方法难以满足要求,解决该类问题的方法一般是采用智能启发式算法,如遗传算法,蚁群算法等。
本文主要研究了遗传算法和蚁群算法,在分析了遗传和蚁群算法的优缺点之后,结合两者的优点提出了一种基于蚁群的混合算法。并将该算法用于解决QoS路由问题,具体所做的工作包括如下几个方面：
1.介绍了课题背景,PTN技术的发展现状和PTN网管的相关情况,并详细的介绍了QoS路由模型。
2.分析了该PTN网管系统的架构及系统中的关键技术,介绍了在该系统中业务的创建流程。详细说明了自动路由和人工路由的优缺点,提出了自动的路由的必要性,以自动路由为本文的研究点。
3.在解决QoS自动路由时,分析了遗传算法和蚁群算法的原理,流程以及在QoS路由问题中的应用。在深刻理解算法的优缺点基础上,提出了一种以蚁群算法为基础的混合算法,该算法先利用遗传算法的全局寻优能力和快速性,生成初始解,然后利用部分解来初始化蚁群信息素,并利用蚁群算法生成最终解。
4.利用实验仿真来验证算法的有效性,实验仿真表明该算法在求精方面优于遗传和蚁群算法,在时间性能上,优于蚁群算法,该算法是有效的。并将该算法应用于实际的PTN网管中,用于创建业务时自动路由的寻找。
根据实验仿真和最后在实际应用中表明,该混合算法比基本遗传算法和蚁群算法有着更良好的效果,是一种效果良好的算法。
With the development of the times and promotion of science and technology, the communication networks continue to move forward. Experienced in the PDH and SDH transmission network, the communication network is toward the development of transmission network of PTN. PTN transmission network based on IP as its core, is the next generation of transmission network. In order to manage PTN transmission network, network management system is essential.
In PTN network, all business is carrying on the PW, after determined the source endpoint and purpose endpoint of the business, according to the corresponding authored QoS constraint find suitable PW called looking for routing. Due to the complexity of the network and related business, automatic routing is inevitable. In search of the routing problem with QoS constraint is a NP-hard problem. to solve such problems conventional method can not satisfy the requirements of this problem and solving methods are generally using intelligent heuristic algorithm, such as genetic algorithm, the ant colony algorithm, etc.
This paper mainly studies the genetic algorithm and the ant colony algorithm genetic,after analyzing the advantages and disadvantages of the two algorithms, then the proposed hybrid algorithm combining with the advantages of both which based on ant colony. And the algorithm is used to solve a QoS routing problem, specific work done including the following aspects:
1. Introduced the subject of background, and PTN technology development status and related network management, then detial the QoS routing model.
2. Analyzes the structure and framework of PTN element management system and the key technology which are introduced in the creation of the system of business process. Detail the automatic routing and artificially routing advantages and disadvantages, puts forward the necessity of automatic routing for this paper, and take automatic routing as the research points.
3. When in solving the QoS automatic routing, analyzed the genetic algorithm and the principle of ant colony algorithm, process and the application in the QoS routing problem. after profound understanding its advantages and disadvantages of the two algorithms, was presented based on ant colony algorithm based on hybrid algorithm, this algorithm by using the genetic algorithm first the global optimization ability and quickness, initial solution, then uses part of the solution to initialize ant colony pheromones, and use the ant colony algorithm generated eventually solutions.
4. Use experimental simulation to verify the efficiency of the algorithm, experimental results show that this algorithm in refinement aspects due to genetic and ant colony algorithm. in time performance, better than ant colony algorithm, this algorithm is effective. And the algorithm was applied to the actual PTN net, used to create business automatic routing search.
According to the simulation results and in practical application shows that the hybrid algorithm has better effect than the basic genetic algorithm and the ant colony algorithm, it is a kind of good method.
引文
[1]Emelianov, S.G.; Atakishchev, O.I.; Zakharov, I.S.;et al.Basic characteristics of high-rate multiplexing systems with time compression of channels according to ITU-T recommendations part 1. Basic characteristics of multiplexing systems of the first level of plesiochronous digital hierarchy[J], Telecommunications and Radio Engineering,2005.64 (3):195-202
[2]Wright, T.C. Deployment strategy for transmission networks based on the synchronous digital hierarchy, British Telecommunications Engineering,1990.9:109-111
[3]Ferguson, S.P..Synchronous digital hierarchy [J].IEE Colloquium,1994.14(1):21-25
[4]刘锐,陈君.PTN建设中的问题分析[J].邮电设计技术,2009.6：10-12
[5]Han, Sunan, O'Connor, Don, Yue, William; Havala, Paul, Next-generation Packet-based Transport Networks economic study [J],2006 Optical Fiber Communication Conference, 2006
[6]Graber, Harald; Hernandez-Valencia, Enrique; Heinmueller, Bernd, Optical/packet transport convergence [J], Bell Labs Technical Journal,2006.11:143-158
[7]刘平心,宋杰,谢妮娜.PTN及电信级以太网在电力系统通信中的应用[J].电力系统通信.2010.31(211)：25-27
[8]S. Sahni,T.Gonzalez. P-complete approximation problems. Journal of the ACM, 1976.23:555-565
[9]赵妮英,曹玲.分组传送网中伪线仿真技术研究[J].2009通信理论与技术新发展,2009：558-565
[10]Yuan, X.; Liu, X. Heuristic algorithms for multi-constrained quality of service routing[J], Proceedings-IEEE INFOCOM,2001. (2):844-853
[11]Oliveira, M.; Melo, B.; Quadros, G.; Monteiro, E., Quality of service routing in the differentiated services framework [J].Proceedings of SPIE-The International Society for Optical Engineering,2001.4211:256-263
[12]记竹亮,戴连奎.一种基于时延信息的多QoS快速自适应路由算法[J].电路与系统学报,2004.9(4)：142-145
[13]胡中功,李静.群智能算法的研究进展[J].控制理论与应用,2008.27(2)：13-15
[14]Androulakis, I.P.; Venkatasubramanian, V., Genetic algorithmic framework for process design and optimization [J], Computers and Chemical Engineering,,1991,15(4):217-228
[15]Costamaqna. Euqenio;Fanni Alessandra;Giacinto,Giorgio. Simulated annealing algorithm for the optimization of communication networks [J]. Conference Proceedings of the International Symposium on Signals,1995:405-408
[16]Zhong, Shi-Quan; Du, Gang.Open vehicle routing problem based on kernel route tabu search algorithm [J].Jisuanji Jicheng Zhizao Xitong/Computer Integrated Manufacturing Systems,,2007.13 (4):827-832
[17]chang,Cheng-Hsin,Shang,Neng-Chou,Wu,Cho-Sen,Chen-Chern-hwa,Predicting peak pressures from computed CFD data and artificial neural networks algorithm [J], Journal of the Chinese Institute of Engineers,2008.31(1):95-103
[18]BELLJE, MCMULLEN P R. Ant colony algorithm based immunity algorithm for TSP [J]. Chinese Journal of Sensors and Actuators,,2006,19(2):504-507
[19]Xu, Gang; Qu, Jin-Ping; Yang, Zhi-Tao.Improved adaptive particle swarm optimization algorithm[j], Huanan Ligong Daxue Xuebao/Journal of South China University of Technology,2008.36(9):6-10
[20]李慧明,许新勇.PTN技术与应用[J].中国新通信,2010.3：9-13
[21]卢成均.缓存机制机器在数据存取层中的应用模型研究[J].计算机应用于软件,2008.25(12)：172-175
[22]陆荣幸,郁洲,阮勇良等.J2EE平台上MVC设计模式的研究与实现[J].计算机应用研究,2003：144-201
[23]周明,孙树栋.遗传算法原理及应用[M].北京,国防工业出版社,1999.6
[24]徐雁飞,莘海琼.遗传算法的应用及研究分析[J].电脑学习,2010.(3)：113-115
[25]陈建安,郭大伟,徐乃平等.遗传算法理论研究综述[J].西安电子科技大学学报,1998.25(3)：363-368
[26]孙宝林,李腊元.基于遗传算法的带宽-时延约束多播路由优化算法[J].计算机工程与应用,2004.11：30-33
[27]王春水,肖学柱,陈汉明.遗传算法的应用举例[J].计算机仿真,2005.22(6)：155-158
[28]曹建文.遗传算法收敛性问题研究[J].中南林业科技大学学报,2008.28(3)：163-167
[29]董建民,周明全,耿国华等.基于遗传算法的QoS的路由算法[J].西北大学学报,2005.35(4)：383-387
[30]何小燕,费翔,罗军舟等.Internet中的一种基于遗传算法的QoS路由选择策略[J].计算机学报,2000,23(11)：1171-1178
[31]王征应,石冰心,赵尔敦.QoS组播路由的启发式遗传算法[J].电子学报,2001,29(2)：253-256
[32]项宝卫,应建健.蚁群算法研究综述[J].台州学院学报,2007.29(3)：6-10
[33]张军 胡晓梅 罗旭耀等译.蚁群优化[M],清华大学出版社,2007.1
[34]杨华江,陈岩,沈林成.基于改进蚁群算法的多约束QoS路由方法[J].计算机应用与软件,2008,25(5):15-18
[35]李勇段正澄.动态蚁群算法求解TSP问题[J].计算机工程与应用,2003.17：103-108
[36]岐世峰,李艳华,梅大成.蚁群算法在QoS单播路由中的应用研究[J].电子科技大学学报,2010,39(2)：271-274
[37]曹建国,陶亮.改进型量子蚁群算法求解QoS单播路由[J].计算机工程与应用,2010.46(18)：116-118
[38]杨华江,陈岩,沈林成.基于改进蚁群算法的多约束QoS路由方法[J].计算机应用与软件,2008.25(5)：15-18
[39]B.M. Waxman. Routing of Multipoint Connections. IEEE JSAC.1988 6(9):1617-1622.
[40]蒋冬初,林亚平.遗传算法在求解函数优化中的最优化参数研究[J].计算机工程与科学,2005.27(10)：50-53
[41]吴春明,陈治,姜明.蚁群算法中系统初始化及系统参数的研究[J].电子学报,2006.34(8)：243-247
[42]叶志伟,郑肇葆.蚁群算法中参数α、β、p设置的研究--以TSP问题为例[J].武汉大学学报,2004.7 29(7)：597-601
[2]Wright, T.C. Deployment strategy for transmission networks based on the synchronous digital hierarchy, British Telecommunications Engineering,1990.9:109-111
[3]Ferguson, S.P..Synchronous digital hierarchy [J].IEE Colloquium,1994.14(1):21-25
[4]刘锐,陈君.PTN建设中的问题分析[J].邮电设计技术,2009.6：10-12
[5]Han, Sunan, O'Connor, Don, Yue, William; Havala, Paul, Next-generation Packet-based Transport Networks economic study [J],2006 Optical Fiber Communication Conference, 2006
[6]Graber, Harald; Hernandez-Valencia, Enrique; Heinmueller, Bernd, Optical/packet transport convergence [J], Bell Labs Technical Journal,2006.11:143-158
[7]刘平心,宋杰,谢妮娜.PTN及电信级以太网在电力系统通信中的应用[J].电力系统通信.2010.31(211)：25-27
[8]S. Sahni,T.Gonzalez. P-complete approximation problems. Journal of the ACM, 1976.23:555-565
[9]赵妮英,曹玲.分组传送网中伪线仿真技术研究[J].2009通信理论与技术新发展,2009：558-565
[10]Yuan, X.; Liu, X. Heuristic algorithms for multi-constrained quality of service routing[J], Proceedings-IEEE INFOCOM,2001. (2):844-853
[11]Oliveira, M.; Melo, B.; Quadros, G.; Monteiro, E., Quality of service routing in the differentiated services framework [J].Proceedings of SPIE-The International Society for Optical Engineering,2001.4211:256-263
[12]记竹亮,戴连奎.一种基于时延信息的多QoS快速自适应路由算法[J].电路与系统学报,2004.9(4)：142-145
[13]胡中功,李静.群智能算法的研究进展[J].控制理论与应用,2008.27(2)：13-15
[14]Androulakis, I.P.; Venkatasubramanian, V., Genetic algorithmic framework for process design and optimization [J], Computers and Chemical Engineering,,1991,15(4):217-228
[15]Costamaqna. Euqenio;Fanni Alessandra;Giacinto,Giorgio. Simulated annealing algorithm for the optimization of communication networks [J]. Conference Proceedings of the International Symposium on Signals,1995:405-408
[16]Zhong, Shi-Quan; Du, Gang.Open vehicle routing problem based on kernel route tabu search algorithm [J].Jisuanji Jicheng Zhizao Xitong/Computer Integrated Manufacturing Systems,,2007.13 (4):827-832
[17]chang,Cheng-Hsin,Shang,Neng-Chou,Wu,Cho-Sen,Chen-Chern-hwa,Predicting peak pressures from computed CFD data and artificial neural networks algorithm [J], Journal of the Chinese Institute of Engineers,2008.31(1):95-103
[18]BELLJE, MCMULLEN P R. Ant colony algorithm based immunity algorithm for TSP [J]. Chinese Journal of Sensors and Actuators,,2006,19(2):504-507
[19]Xu, Gang; Qu, Jin-Ping; Yang, Zhi-Tao.Improved adaptive particle swarm optimization algorithm[j], Huanan Ligong Daxue Xuebao/Journal of South China University of Technology,2008.36(9):6-10
[20]李慧明,许新勇.PTN技术与应用[J].中国新通信,2010.3：9-13
[21]卢成均.缓存机制机器在数据存取层中的应用模型研究[J].计算机应用于软件,2008.25(12)：172-175
[22]陆荣幸,郁洲,阮勇良等.J2EE平台上MVC设计模式的研究与实现[J].计算机应用研究,2003：144-201
[23]周明,孙树栋.遗传算法原理及应用[M].北京,国防工业出版社,1999.6
[24]徐雁飞,莘海琼.遗传算法的应用及研究分析[J].电脑学习,2010.(3)：113-115
[25]陈建安,郭大伟,徐乃平等.遗传算法理论研究综述[J].西安电子科技大学学报,1998.25(3)：363-368
[26]孙宝林,李腊元.基于遗传算法的带宽-时延约束多播路由优化算法[J].计算机工程与应用,2004.11：30-33
[27]王春水,肖学柱,陈汉明.遗传算法的应用举例[J].计算机仿真,2005.22(6)：155-158
[28]曹建文.遗传算法收敛性问题研究[J].中南林业科技大学学报,2008.28(3)：163-167
[29]董建民,周明全,耿国华等.基于遗传算法的QoS的路由算法[J].西北大学学报,2005.35(4)：383-387
[30]何小燕,费翔,罗军舟等.Internet中的一种基于遗传算法的QoS路由选择策略[J].计算机学报,2000,23(11)：1171-1178
[31]王征应,石冰心,赵尔敦.QoS组播路由的启发式遗传算法[J].电子学报,2001,29(2)：253-256
[32]项宝卫,应建健.蚁群算法研究综述[J].台州学院学报,2007.29(3)：6-10
[33]张军 胡晓梅 罗旭耀等译.蚁群优化[M],清华大学出版社,2007.1
[34]杨华江,陈岩,沈林成.基于改进蚁群算法的多约束QoS路由方法[J].计算机应用与软件,2008,25(5):15-18
[35]李勇段正澄.动态蚁群算法求解TSP问题[J].计算机工程与应用,2003.17：103-108
[36]岐世峰,李艳华,梅大成.蚁群算法在QoS单播路由中的应用研究[J].电子科技大学学报,2010,39(2)：271-274
[37]曹建国,陶亮.改进型量子蚁群算法求解QoS单播路由[J].计算机工程与应用,2010.46(18)：116-118
[38]杨华江,陈岩,沈林成.基于改进蚁群算法的多约束QoS路由方法[J].计算机应用与软件,2008.25(5)：15-18
[39]B.M. Waxman. Routing of Multipoint Connections. IEEE JSAC.1988 6(9):1617-1622.
[40]蒋冬初,林亚平.遗传算法在求解函数优化中的最优化参数研究[J].计算机工程与科学,2005.27(10)：50-53
[41]吴春明,陈治,姜明.蚁群算法中系统初始化及系统参数的研究[J].电子学报,2006.34(8)：243-247
[42]叶志伟,郑肇葆.蚁群算法中参数α、β、p设置的研究--以TSP问题为例[J].武汉大学学报,2004.7 29(7)：597-601