度约束QoS组播路由遗传算法

有度约束的QoS组播路由问题在通信网络中具有重要意义。提出一种基于遗传算法的度约束组播路由算法,采用节点连接路径形式的编码方法构成一棵组播树的表示,设计了相应的具有树形结构的交叉和变异算子,以及节点度的改变算法。算法可以实现具有树形结构染色体的遗传进化。数值实验表明算法具有找到最优解的能力,特别适合于求解大规模网络有度约束的QoS组播路由问题。     

On-line multicast routing with QoS constraints in WDM networks with no wavelength converters

The rapid growth of multicast applications initiated the need to realise multicasting in Wavelength Division Multiplexing (WDM) networks in an efficient and cost-effective way. However, most of the applications need to support dynamic multicast sessions wherein the membership of the multicast group changes with time as nodes join or leave the session dynamically. In addition, with the advancements in the multimedia and other real-time group applications, the construction of multicast trees satisfying Quality of Service (QoS) requirements of the member nodes is becoming a problem of prime importance. In this paper, we deal with on-line QoS multicast routing in WDM networks. As members leave the sessions, it will be mandatory to rearrange the trees in order to save costs, at the same time accounting for the disruption caused to the ongoing transmissions because of the rearrangement. We try to effectively decrease the disruption by considering only certain portions of the multicast tree and limiting the rearrangement to only those portions. A region’s usefulness to the overall tree is judged by a novel concept of Cost-to-Service Ratio (CSR) and a region is selected for rearrangement based on its CSR value. Extensive simulation results reveal that rearrangements based on CSR can reduce the disruption to the member nodes by 20–85% compared to rearrangements based on the best known metric (Quality Factor) in the literature, for the same cost performance. We also demonstrate the cost-effectiveness of the trees generated by our on-line algorithm compared to that of static algorithm.     

基于遗传算法的无线网状网QoS多播路由算法

探讨了基于遗传算法的无线网状网QoS多播路由算法,选用边集表示方式对多播树进行编码,其空间复杂度为O(N),给出了该编码方式下的初始种群生成算法RandWalkMT,同时对传统的遗传操作进行改进使子代个体中不会产生非法多播树,从而避免了复杂的惩罚机制或多播树修复算法。实验表明该算法收敛快且性能较好。     

Genetic algorithm for finding minimal cost light-forest of multicast routing on WDM networks

Wavelength division multiplexing (WDM) is an important technique to make use of the large amount of bandwidth in optical fibers to meet the bandwidth requirements of applications. Multicast is the transmission of information from one source to multiple destinations simultaneously. Given a multicast request in a WDM network, the goal is to find a set of light-trees, the assigned wavelengths of light-trees, and construct a light-forest. In this paper, the Minimal cost multicast routing problem (MCMRP) on WDM networks with Tap-and-continue nodes is defined and studied. A new cost model which consists of thewavelength usage and communication cost is defined. The objective is to minimize the sum of the cost of used wavelengths and the communication cost of the light-forest. Specifically, the formulation for the WDM multicast routing problem is given. Because the MCMRP is NP-hard, two genetic algorithms (GAs) are proposed to solve this problem. In the proposed GAs, a path-oriented encoding chromosome is used to represent the routing paths. These routing paths are used to construct source-based light-forests to represent a feasible solution to the multicast request. Moreover, to speed up the convergence of GAs, a Farthest-first greedy heuristic algorithm is proposed and used to generate one of the initial chromosomes. Simulation results demonstrate that the proposed GAs can run efficiently.     

求解QoS组播路由问题的改进遗传算法

遗传算法是一种非常适合求解QoS组播路由问题的全局优化算法。针对算法运行初期易陷入早熟现象,运行后期收敛速度慢的不足,进行了改进,采用初始群体均衡生成法和自适应变异操作可以很好地抑制早熟现象,引入排序对适应度进行拉伸,从而加快了算法的收敛速度。在嵌入式视频监控系统上进行仿真实验,结果表明改进后的遗传算法收敛速度快,性能好,可以满足系统资源有限和实时性的要求。     

求解QoS组播路由问题的改进型量子进化算法

QoS组播路由问题是一个非线性的组合优化问题,已证明了该问题是NP完全问题。提出一种将基于量子计算原理的量子进化算法用于此类问题求解的算法,该算法对基本的量子进化算法进行改进,采用进化方程对量子门进行调整,采用量子变异阻止未成熟收敛,使之更适合于QoS组播路由的求解。仿真结果显示,该算法能快速搜索并收敛到全局（近似）最优解,且随着网络规模的增大算法保持了良好的特性,在寻优速度上与解的质量上优于其他进化算法与基本的量子进化算法。     

基于量子遗传算法的QoS多播路由算法

QoS多播路由算法的核心问题就是建立满足QoS约束的多播树,它是计算机网络中著名的受约束最小Steiner树问题,是一个NP完全问题。量子遗传算法是基于量子计算理论的新型遗传算法,基于量子遗传算法的基本原理,提出了QoS约束的多播路由算法（QoSMR-QGA）,并详细介绍了QoSMR-QGA算法的实现过程。仿真实验表明,该算法具有较好的算法收敛性和多播路由成功率。     

基于一种新的蚁群算法的QoS组播路由问题的研究

在解决QoS（Quality of Service）组播路由问题上,针对蚁群算法缺点,提出了一种融合量子粒子群算法（QPSO）思想的多行为蚁群算法。该算法采用QPSO作为前期搜索,根据各粒子历史最优值来初始化路径信息素浓度,后期利用多行为蚁群算法来优化路径。仿真结果表明：该算法寻优能力强,可靠性高,是解决QoS组播路由问题的有效方法。     

QoS based multicast routing algorithms for real time applications

In recent years, there has been a lot of interest in providing real-time multimedia services like digital audio and video over packet-switched networks such as Internet and ATM. These services require certain quality of service (QoS) from the network. The routing algorithm should take QoS factor for an application into account while selecting the most suitable route for the application. In this paper, we introduce a new routing metric and use it with two different heuristics to compute the multicast tree for guaranteed QoS applications that need firm end-to-end delay bound. We then compare the performance of our algorithms with the other proposed QoS-based routing algorithms. Simulations were run over a number of random networks to measure the performance of different algorithms. We studied routing algorithms along with resource reservation and admission control to measure the call throughput over a number of random networks. Simulation results show that our algorithms give a much better performance in terms of call throughput over other proposed schemes.     

Valiant load-balanced robust routing algorithm for multi-granularity connection requests in traffic-grooming WDM mesh networks

The paper considers the problem of establishing robust routes for multi-granularity connection requests in traffic-grooming WDM mesh networks and proposes a novel Valiant load-balanced robust routing scheme for the hose uncertain model. Our objective is to minimize the total network cost when construct the stable virtual topology that assure robust routing for all possible multi-granularity connection requests under the hose model. Since the optimization problem is shown to be NP-complete, two heuristic algorithms are proposed and evaluated. Finally we compare the traffic throughput of the virtual topology by Valiant load-balanced robust routing scheme with that of the traditional traffic-grooming algorithm under the same total network cost by computer simulation.     

一种基于可用带宽的QoS多播路由算法

设计一个加权最大可用带宽多播树求解模型,将可用带宽作为主度量并同时兼顾时延、时延抖动和包丢失率3个QoS约束构建多播树.各QoS度量的重要性可根据实际的服务需求灵活调整,算法具有多项式复杂度,并通过仿真证明其有效性.     

用遗传算法求解最优QoS 划分与路由问题*

未来的通信网将充分支持各种QoS业务,QoS划分与路由问题研究针对QoS业务的最优化问题.首次提出了求解最优QoS划分和路由问题的遗传算法.该算法以K条最短路径来代替全网最优路径,大大加快了算法的运行速度.仿真结果证明了该算法的合理性和有效性.     

Ad Hoc网络中基于遗传蚁群算法的QoS多播路由算法

利用遗传算法的快速全局搜索能力和蚁群算法的正反馈收敛机制,把蚁群算法和遗传算法融合起来,提出了一种遗传蚁群算法（GAAC）来解决Ad Hoc网络中QoS路由问题。首先利用遗传算法生成信息素分布,然后用蚁群算法求精解,优势互补,期望获得优化性能和时间性能的双赢。并针对算法应用于Ad Hoc网络QoS路由普遍产生的拥塞问题,采用拥塞回避的策略,从而实现网络业务流负载均衡。仿真表明该算法比其它单一采用蚁群算法进行路由选择更适合于动态Ad Hoc网络环境。     

MANET中基于遗传算法的QoS多播路由协议

随着多媒体业务的普及,如何为MANET多播路由提供QoS保障成为研究热点。提出了一种带宽和时延受限的QoS多播路由协议,它利用遗传算法搜索满足QoS要求的最优多播树。仿真结果表明该协议收敛速度快,寻径成功率高,它为移动网络中具有QoS保障的多播通信提供了一种有效途径。     

A QoS multicast routing protocol for dynamic group topology

Multicast routing is establishing a tree which is rooted from the source node and contains all the multicast destinations. A multicast routing tree with multiple QoS constraints may be the tree in which the delay, delay-jitter, packet-loss and bandwidth should satisfy the pre-specified bounds. This paper discusses the multicast routing problem with multiple QoS constraints, which may deal with the delay, delay-jitter, bandwidth and packet-loss metrics, and describes a network model for researching the routing problem. It presents a QoS multicast routing protocol with dynamic group topology (QMRPD). The QMRPD attempts to significantly reduce the overhead of constructing a multicast tree with multiple QoS constraints. In MPRMQ, a multicast group member can join or leave a multicast session dynamically, which should not disrupt the multicast tree. It also attempts to minimize overall cost of the tree, and satisfy the multiple QoS constraints and least cost's (or lower cost) requirements. In this paper, the proof of correctness and complexity analysis of the QMRPD are also given. Simulation results show that QMRPD is an available approach to multicast routing decision with dynamic group topology.     

一种基于种族分类进化的QoS异构组播路由机制

随着新型网络应用的大量涌现,传统的网络技术已无法满足当前应用在带宽、延迟及出错率等方面的需求,IP over DWDM光互联网以其独特性能优势成为研究热点。基于种族分类进化算法,提出了一种IP over DWDM光互联网服务质量QoS异构组播路由机制。具体地,利用概率论方法处理网络状态参数信息的不确定性;引入模糊数学方法,确定用户对QoS的需求并提供柔性QoS支持;综合考虑网络提供方和用户方的利益,设计公平的带宽定价方法。仿真结果表明,该路由机制获得了良好的综合性能指标,可以有效地解决IP over DWDM光互联网中的柔性QoS异构组播路由选择问题。     

基于蚁群遗传算法的QoS多播路由研究*

为解决多播路由中的QoS约束问题,不仅研究了QoS多播路由中的带宽、时延﹑时延抖动和包丢失率等约束问题,还重点分析了路径开销问题,从而提出一种基于蚁群遗传算法的多播路由算法。该算法将遗传算法与蚁群算法结合起来,对多播树群体进行编码、选择、杂交和变异等遗传操作,同时利用蚁群算法的信息素正反馈求解,充分发挥两者的优势,从而更快更好地产生出既满足服务质量保障（QoS）又具有最小路径开销的多播树。仿真实验证明了该算法具有更高的运行效率和更好的收敛性。     

A method for least-cost QoS multicast routing based on genetic simulated annealing algorithm

A method for least-cost QoS multicast routing based on genetic simulated annealing algorithm (NGSA) is presented. Genetic algorithm and simulated annealing algorithm are combined to improve the computing performance in this method. The chromosomes of the multicast tree are represented by tree structure coding to save the time of conversion between encoding space and solution space. A new population initialization method is used to make sure that every chromosome in initial population is reasonable multicast tree without loops. The adaptive crossover probability is used to improve the evolutionary efficiency. The simulation results show that this method has high speed of convergence and search capability. And the problem of least-cost QoS multicast routing is solved effectively.     

基于混合遗传算法的QoS多播路由算法

具有多QoS约束的多播路由问题具有NP完全的复杂度。基于延时、延时抖动、带宽、丢包率等QoS约束,描述了一种适应于研究QoS多播路由的网络模型,提出了基于遗传算法和禁忌搜索混合策略的具有多QoS约束的多播路由算法。该算法充分利用了遗传算法和禁忌搜索的优点。克服了遗传算法在求解多QoS约束多播路由问题中的爬山能力差以及不成熟收敛等问题。仿真实验结果表明,该算法为多QoS约束多播路由问题的求解提供了一种有效的新途径。     

基于QPSO的QoS组播路由算法

对带宽、延时、延时抖动约束最小代价的QoS组播路由问题进行了研究，提出一种基于量子行为微粒群优化（QPSO）算法来设计路由优化算法。该算法采用一种节点序列编码方案，将路由优化问题转化成一种准连续优化问题，并采用罚函数处理约束条件。应用QPSO算法求解QoS组播路由问题的算例，并与遗传算法和改进后的遗传算法进行比较。计算机仿真实验证明，该算法可以更有效地求得QoS组播路由问题的优化解，可靠性较高。