度约束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 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约束的多播路由问题具有NP完全的复杂度。基于延时、延时抖动、带宽、丢包率等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.     

传感网络中基于位置信息的分布式多播路由算法

提出了一个传感网络中基于位置信息的成簇思想,并基于该思想给出了一种传感网络中基于位置信息的分布式多播路由算法.该算法首先利用相邻节点的位置信息分布式成簇,然后各簇头利用蚂蚁算法分布式地找到一条具有最短总跳数的到目的节点组的实际路径.最后,由簇头负责收集本簇内的传感信息,并在对这些信息进行汇聚处理后,沿找到的最优路径将汇聚数据分别发送到各目的节点.理论分析和仿真结果表明,该算法能有效地节约能量,具有较好的路由性能.     

A cross-layer optimization based integrated routing and grooming algorithm for green multi-granularity transport networks

With the development of IP networks and intelligent optical switch networks, the backbone network tends to be a multi-granularity transport one. In a multi-granularity transport network (MTN), due to the rapid growth of various applications, the scale and complexity of network devices are significantly enhanced. Meanwhile, to deal with bursty IP traffic, the network devices need to provide continuous services along with excessive power consumption. It has attracted wide attention from both academic and industrial communities to build a power-efficient MTN. In this paper, we design an effective node structure for MTN. Considering the power savings on both IP and optical transport layers, we propose a mathematical model to achieve a cross-layer optimization objective for power-efficient MTN. Since this optimization problem is NP-hard (Hasan et al. (2010)  [11]) and heuristic or intelligent optimization algorithms have been successfully applied to solve such kinds of problems in many engineering domains (Huang et al. (2011)  [13], Li et al. (2011)  [17] and Dong et al. (2011)  [5]), a G  reen integrated R$R$outing and Grooming algorithm based on Biogeography-Based Optimization (Simon (2008)  [23]) (GRG_BBO) is also presented. The simulation results demonstrate that, compared with the other BBO based and state-of-the-art power saving approaches, GRG_BBO improves the power savings at a rate between 2%–15% whilst the high-level multi-user QoS (Quality of Services) satisfaction degree (MQSD) is guaranteed. GRG_BBO is therefore an effective technique to build a power-efficient MTN.     

基于蚁群算法WDM网络故障恢复路由研究

蚁群故障恢复算法是一种新颖的模拟进化算法.该算法基于群以正反馈作为首要的搜索机制,为复杂的组合优化问题提供了一种新方法.本文在传统蚁群算法的选择策略,本地搜索,以及信息更新三方面做出改进.改进后的算法用于解决渡分复用光网络中不同故障条件下的优化恢复路由问题.通过对一个典型网络CHINANET的数值仿真,证明了蚁群故障恢复算法在WDM网络中故障恢复路由的可行性.     

NGI尺度收缩混沌变异QoS组播路由算法

IP／DWDM光Internet是下一代互联网主要组网技术之一,服务质量组播路由算法是其一个研究热点,已经证明它是NP完全的。为此设计了一种非NP类算法,基于尺度收缩混沌变异进化算法,构造一棵带宽,延迟,延迟抖动和出错率受限且费用优化的QoS组播路由树,兼顾网络负载均衡。仿真研究表明,该算法是可行和有效的,较好地克服了传统遗传算法的早熟和收敛性差的问题。     

基于自适应混沌遗传算法的QoS组播路由

经典遗传算法在解决QoS组播路由问题时存在易发生早熟现象、进化后期搜索效率低以及收敛后稳定性差等不足,为此,在遗传算法中引入混沌优化以及自适应调整交叉与变异概率两个改良措施。仿真实验表明,改良后的算法性能优良,在收敛速度、最优解的质量以及收敛后稳定性等方面有很大的提高。     

基于克隆遗传的QoS多播路由优化模型

针对QoS组播路由问题的特点,采用固定长度的基因编码方式并利用克隆算子扩大遗传算法的种群规模,设计了自适应交叉算子和变异算子控制染色体的生成,从而有效保持群体的多样性,有利于算法寻找到全局的最优解.实验结果表明,经过改进的遗传算法具有良好的运行速度和收敛性,能有效解决QoS组播路由的问题,对于求解多目标节点的情况具有良好的效果.     

Multi-robot navigation based QoS routing in self-organizing networks

The technical development drives the future networks to become large-scale, heterogeneous, and dynamic. Bio-inspired networking can help reduce the time-space complexity of the complex network. Due to the good features such as self-organization and self-management, self-organizing network (SON) will most probably be a priority choice for the next generation network. In this paper, a swarm intelligence based Quality of Service (QoS) routing protocol is proposed for SON. The inaccurate routing and QoS information is described with fuzzy mathematics whilst the utilities of both the user and the network service provider are considered by applying game theory. Based on the multi-robot navigation algorithm, the protocol is able to search a routing path which can satisfy the user QoS requirements and achieve the Pareto optimal utilities of the user and the network service provider under Nash equilibrium. The proposed protocol is implemented and evaluated by extensive simulation experiments. The results show that it beats both other swarm intelligence based routing protocols and the traditional Dijkstra algorithm based routing protocol. The searched routing paths support the win–win effect for both the user and the network service provider.     

SoMR: A scalable distributed QoS multicast routing protocol

Many Internet multicast applications such as teleconferencing and remote diagnosis have Quality-of-Service (QoS) requirements. The requirements can be additive (end-to-end delay), multiplicative (loss rate), or of a bottleneck nature (bandwidth). Given such diverse requirements, it is a challenging task to build QoS-constrained multicast trees in a large network where no global network state is available. This paper proposes a scalable QoS multicast routing protocol (SoMR) that supports all three QoS requirement types. SoMR is scalable due to small communication overhead. It achieves favorable tradeoff between routing performance and routing overhead by carefully selecting the network sub-graph in which it searches for a path that can support the QoS requirements. The scope of search is automatically tuned based on the current network conditions. An early-warning mechanism helps detect and route around the long-delay paths in the network. The operations of SoMR are completely decentralized. They rely only on the local state stored at each router.     

A multipopulation parallel genetic simulated annealing-based QoS routing and wavelength assignment integration algorithm for multicast in optical networks

In this paper, we propose an integrated Quality of Service (QoS) routing algorithm for optical networks. Given a QoS multicast request and the delay interval specified by users, the proposed algorithm can find a flexible-QoS-based cost suboptimal routing tree. The algorithm first constructs the multicast tree based on the multipopulation parallel genetic simulated annealing algorithm, and then assigns wavelengths to the tree based on the wavelength graph. In the algorithm, routing and wavelength assignment are integrated into a single process. For routing, the objective is to find a cost suboptimal multicast tree. For wavelength assignment, the objective is to minimize the delay of the multicast tree, which is achieved by minimizing the number of wavelength conversion. Thus both the cost of multicast tree and the user QoS satisfaction degree can approach the optimal. Our algorithm also considers load balance. Simulation results show that the proposed algorithm is feasible and effective. We also discuss the practical realization mechanisms of the algorithm.     

一种新的混沌蚁群算法及其在QoS组播路由优化问题中的应用

基于QoS的组播路由问题是通过发现具有某种相关性能约束的最佳组播树,来更好地利用网络资源以支持应用的QoS需求,作为以QoS为中心的网络体系结构中不可缺少的组成部分,目前已成为网络研究领域的重要内容和热点问题.针对多约束条件下的QoS组播路由问题,提出一种新的混沌蚁群算法.该算法基于传统的蚁群算法所存在的不足,利用混沌优化算法对蚁群算法的运行参数进行动态地优化选择,自适应地改进了全局搜索能力和收敛性.仿真实验结果表明,混沌蚁群算法比该文提到的遗传算法及蚁群算法在解决多约束组播路由问题上具有更好的性能.