论文部分内容阅读
信息时代的来临已经使Internet成为一个重要的、无处不在的基础设施,与此同时,随着分布式多媒体应用需求的不断增长,以及Internet上商业化应用的飞速发展,对网络性能和服务质量提出了更高的要求。但是“尽力而为(best-effort)”服务仍是目前Internet中主要的一种服务类别,所有分组在网络中被同等对待,缺少有效的管理,局部的拥塞经常发生,导致网络性能下降、应用的分组丢失和数据抖动。如何提高IP网络的服务质量(Quality of Service, QoS),已经成为众多国际组织、网络设备制造商和业务提供者研究和应用开发的焦点问题。路由选择是IP网络运行的核心问题,合理高效的路由选择方式不仅可以保障全网的正常运行,还能够提高网络的接通率。而将Internet的接通率提高,既可以尽量避免交换机不堪重负甚至崩溃的情况,又能降低网络的运营成本。提高网络的接通率相当大的程度上依赖于路由选择策略的改变。随着Internet规模的扩大,IP网络的动态路由选择问题变得越来越重要。QoS路由是实现服务质量的重要手段,这方面的研究一直是IP网络研究领域的一个热点。本文的研究工作主要集中在对IP网络中的QoS路由算法的研究上。在遗传算法和蚁群算法的基础上,提出了两个改进的有效、实用的QoS路由算法。取得的主要成果如下:( 1 )针对多QoS约束的路由问题,设计了一种基于可回溯遗传算法的QoS路由算法(QoS routing algorithm based on the Genetic Algorithm with Backtracking Strategy, GABS)。在遗传进化过程中引入“非自然进化方法”——回溯机制,人为地对染色体的遗传操作进行一定的干预。在进化过程中设立回溯检查点,探察有无陷入局部最优解,一旦发现则及时补救,将进化过程回溯到上一个检查点,以此为依据人为地对种群施加一定的影响,改善了遗传算法中未成熟收敛的难题。若整个进化过程中不出现回溯,则退化为传统的遗传算法。通过和传统的遗传算法的比较,进一步说明了算法的有效性。( 2 )针对多QoS约束的路由问题,借鉴遗传算法和蚁群算法,设计了一种基于遗传算法和蚁群算法融合的QoS路由算法(QoS routing algorithm according to the combination of the Genetic Algorithm and Ant Colony Algorithm, GAACO_QoS)。算法首先利用遗传算法生成若干组优化解,将其转换成蚁群算法的信息素初值;然后利用蚁群算法来求取满足QoS约束的最优解(或非劣解)。算法中设置了遗传算法控制函数CG,在给定的遗传迭代次数范围内,通过CG值的变化动态地控制遗传算法的迭代次数,当CG的值连续若干次都相等时就退出遗传算法,转去执行蚁群算法,进而确保遗传算法和蚁群算法在适当时机融合。算法既克服了遗传算法和蚁群算法的缺点,又保留了它们各自的优点。通过和遗传算法以及蚁群算法的比较,进一步说明了算法的有效性。