基于多目标遗传算法的多播服务质量路由优化

互联网不断增长的多媒体应用引发人们研究如何满足这些应用的服务质量(QoS)约束，并导致提出了一些基于服务质量的体系结构．目前网络中多主机之间的多播通信一般需要严格的多个QoS保证．首先将满足不同约束的多播路由选择过程转化为一个多目标优化问题，然后使用一种基于多目标遗传算法的新型多播树计算方法，同时优化时延、丢包率和带宽利用率等不同的参数．实验结果表明，该方法能在有限进化代数内产生一组有效的非劣多播路由解，结合多目标优化的遗传算法克服了单目标路由优化的缺陷．     

基于自适应蚁群算法的多受限网络QoS路由优化

高速多媒体网络中的路由问题是有QoS约束的路由问题，多受限的路由问题是一个NP-完全问题。该文提出了一种解决多受限QoS路由问题的自适应蚁群算法。该算法采用基于目标函数值的信息素分配策略和根据目标函数值自适应调整蚂蚁的搜索行为，从而保证搜索的快速有效性，使多受限QoS路由优化问题得到很好地解决。     

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

多约束的QoS路由问题是NP完全问题.量子遗传算法是基于量子计算理论的新遗传算法,具有种群多样性、收敛速度快和全局寻优的特点.将量子遗传算法引入多约束QoS路由计算,提出了一种基于量子遗传算法的QoS路由算法,给出了算法实现的方法和具体流程.实验结果表明,通过该算法得到的QoS路由不但能满足QoS约束要求,同时可以均衡链路负载,减少路由拥塞.     

多QoS参数约束的选播路由算法的研究

选播是Ipv6中的一种标准通讯模型。本文研究多QoS参数约束的选播路由问题，建立了一种带有多个QoS参数约束的选播通信服务模型，设计实现了相应的多路选播路由算法。网络仿真实验结果表明，该算法是有效且切实可行的，它能同时满足多个QoS的约束条件，具有较好的求解效果，改善了网络服务质量。     

微粒群算法在网络QoS路由优化中的应用

网络路由优化问题是指在一个网络中,要求在某些约束条件下找出从源节点到宿节点之间某种含义之下的最佳路径。本文通过网络数学模型的提取得知网络QoS路由问题其实质是一个多目标约束优化问题,并将近年来兴起的微粒群算法应用到网络QoS路由优化中,仿真结果表明算法的可行性和有效性。     

基于混合遗传算法的多播路由多目标优化

互联网不断增长的多媒体应用引发人们研究如何满足这些应用的服务质量(QoS)约束.目前网络中多主机之间的多播通信一般需要严格的多个QoS保证,文中描述了一种适应于研究多播QoS路由多目标优化的网络模型,在此基础上提出了基于遗传算法和禁忌搜索混合策略的,具有多目标的多播路由QoS优化方法,以克服遗传算法的爬山能力差以及不成熟收敛等问题.此外还采用了改进的多播树编码方法及高效的遗传操作,同时还优化时延、丢包率和带宽利用率等不同的参数.实验结果表明,该算法为多播路由QoS多目标优化问题的求解提供了一种有效的新途径.     

多约束QoS组播路由优化算法研究

不确定网络性能参数下的多约束QoS组播路由优化已成为安全组播领域的一个重要研究课题，也是下一代Internet和高性能网络亟待解决的难题。多约束QoS组播路由优化是NP一完全的多目标优化问题。本文概括了多约束QoS组播路由需求，然后重点讨论多约束QoS组播路由优化的约束树算法和智能算法，最后探讨了多约束QoS组播路由将来的一些主要研究方向。     

基于遗传算法的QoS选播流路由优化算法

选播是一种网络通信服务,在视频流点播等领域发挥重要作用。该文提出QoS选播流路由优化的问题模型,给出选播流路由端到端时延、服务器负载、网络流量等优化目标和QoS约束的遗传算法表达式,说明了算法求解的关键步骤和实现过程。实验结果表明,该算法在满足QoS约束的前提下可以实现选播路由的多目标组合优化。     

具有局部和全局QoS约束的Web服务选择

提出一种具有局部和全局QoS约束的Web服务选择算法.将基于QoS的Web服务选择问题建模为带QoS约束的多目标组合优化问题,使用局部QoS约束过滤不满足约束条件的候选服务,通过归档式多目标模拟退火(AMOSA)算法同时优化多个QoS目标函数以产生一组Pareto优化解,利用全局QoS约束筛选出满足约束条件的Pareto最优解集.实验结果证明了该算法的有效性.     

基于QPSO的QoS组播路由算法

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

基于磷虾群算法的无线传感器网络QoS任播路由算法

无线传感器网络多约束QoS任播路由问题是一个NP难题,提出一种基于磷虾群算法的优化策略来解决该路由问题.该算法采用适应度函数和全局最优个体位置更新方法来寻找无线传感器网络中满足多QoS约束的最优任播路由,并加入遗传繁殖机制中的交叉与变异操作以加快优化速度.实验验证了该算法的有效性,实验数据表明相比较粒子群优化算法,该算法在算法效率和可扩展性性能上具有较好的性能;具有较快的收敛速度,从而适用于对路由选择有时延敏感的网络.     

基于多约束QoS问题的启发式算法

由于多媒体通信的需要,QoS路由技术已成为通信网络中研究的热点。通常情况下,在网络中寻找同时满足多个独立加性约束条件的路由是一个NP完全问题。本文探讨了多约束条件下的路径选择(MCP)问题,通过将MCP问题转化为离散化的动态网络,得到了一个性能更好的启发式QoS路由算法,复杂度从O(Tmn)降低为O(Tm),其中m、n分别是节点数和边数,T是算法定义的正整数,并在理论上证明了算法的正确性。最后给出实验举例,并通过与现有算法性能比较,表明改进的启发式算法能快速、有效地解决MCP问题,且适用于大规模的网络系统。     

QoS路由中一种有效的多受限优化路径选择算法

1 引言目前,人们正期待着宽带集成服务网来支持各种各样的满足不同QoS要求的多媒体应用。在宽带体系结构的设计中的一个关键问题就是如何提供资源来满足每次连接的需求。毫无疑问,有效的QoS路由方案的建立是这种体系结构中的一个重要组成部分。的确,QoS路由已经成为许多研究的主题。人们已经认识到一个有效的QoS路由方案的建立给我们带来了许多挑战。在算法上,QoS路由带来的一个的挑战就是需要迅速地找到一条可行路径使它满足一组限制条件同时获得较高的网络资源利用率。一般而言,QoS路由是一个复杂的问题。首先,网络电话和分布式游戏等分布式应用在延迟、延迟抖动、丢失率和带宽等方面有许多不同的QoS限制。多个限制经常使得路由问题更加复杂。例如,寻找一条具有两个独立路径限制的可行路径是NP难的。其次,将来的集成服务网很可能既要传输QoS数据流又要传输尽力而为的数据,     

基于多目标规划的QoS路由选择的数学模型及优化算法

QoS路由选择是一个基于多约束条件的优化问题。 QoS路由选择应该满足业务的QoS需求和尽可能充分利用网络资源两方面的要求。该文从这两方面的要求出发，给出了QoS参数和网络资源利用率的数学描述，建立了QoS路由选择的多目标规划模型，根据该模型，给出了算法。并用仿真实验来验证所提出的模型和算法的有效性。     

The cost optimal solution of the multi-constrained multicast routing problem

In this paper, we define the cost optimal solution of the multi-constrained multicast routing problem. This problem consists in finding a multicast structure that spans a source node and a set of destinations with respect to a set of constraints, while minimizing a cost function. This optimization is particularly interesting for multicast network communications that require Quality of Service (QoS) guarantees. Finding such a structure that satisfies the set of constraints is an NP-hard problem. To solve the addressed routing problem, most of the proposed algorithms focus on multicast trees. In some cases, the optimal spanning structure (i.e. the optimal multicast route) is neither a tree nor a set of trees nor a set of optimal QoS paths. The main result of our study is the exact identification of this optimal solution. We demonstrate that the optimal connected partial spanning structure that solves the multi-constrained multicast routing problem always corresponds to a hierarchy, a recently proposed generalization of the tree concept. We define the directed partial minimum spanning hierarchies as optimal solutions for the multi-constrained multicast routing problem and analyze their relevant properties. To our knowledge, our paper is the first study that exactly describes the cost optimal solution of this NP-hard problem.     

Complexity and design of QoS routing algorithms in wireless mesh networks

Quality of service (QoS) provisioning in wireless mesh networks (WMNs) is an open issue to support emerging multimedia services. In this paper, we study the problem of QoS provisioning in terms of end-to-end bandwidth allocation in WMNs. It is challenging due to interferences in the networks. We consider widely used interference models and show that except a few special cases, the problem of finding a feasible path is NP-complete under the models. We propose a k-shortest path based algorithmic framework to solve this problem. We also consider the problem of optimizing network performance by on-line dynamic routing, and adapt commonly used conventional QoS routing metrics to be used in WMNs. We find the optimal solutions for these problems through formulating them as optimization models. A model is developed to check the existence of a feasible path and another to find the optimal path for a demand; moreover, an on-line optimal QoS routing algorithm is developed. Comparing the algorithms implemented by the proposed framework with the optimization models shows that our solution can find existing feasible paths with high probability, efficiently optimizes path lengths, and has a comparable performance to the optimal QoS routing algorithm. Furthermore, our results show that contrary to wireline networks, minimizing resource consumption should be preferred over load distribution even in lightly loaded WMNs.     

DPA:一种动态环境下QoS单播路由算法

目前Internet网络环境下,网络参数的随时变化容易造成路由过期,从而使提供的QoS路由无效,为此提出了一种适合参数动态变化的单播QoS路由算法(DPA),该算法在路径代价随时间不断变化的情况下能够自主地选择最优路由节点,解决多约束QoS单播路由选择不精确的问题.实验表明,本路由算法自适应性和扩展性较好,同时在路由选择方面比传统的路由算法能够提供更好的QoS路由.     

Precomputation for intra-domain QoS routing

Quality-of-service routing (QoSR), seeking to find a feasible path with multiple constraints, is an NP-complete problem. We propose a novel precomputation approach to multi-constrained intra-domain QoS routing (PMCP). It is assumed that a router maintains the link state information of the entire domain. PMCP cares each QoS weight to several degrees, and computes a number of QoS coefficients uniformly distributed in the multi-dimensional QoS metric space. Based on each coefficient, a linear QoS function is constructed to convert the multiple QoS metrics to a single QoS value. We then create a shortest path tree with respect to the QoS value by Dijkstra’s algorithm. Finally, according to the multiple coefficients, different shortest path trees are calculated to compose the QoS routing table. We analyze linear QoS functions in the QoS metric space, and give a mathematical model to determine the feasibility of a QoS request in the space. After PMCP is introduced, we analyze its computational complexity and present a method of QoS routing table lookup. Extensive simulations evaluate the performance of the proposed algorithm and present a comparative study.     

一种基于非线性长度的多约束路由算法*

满足多个约束的QoS路由问题已经被证明是NP完全问题。在分析了多种路由算法的基础上,设计了一种高效的多约束路由算法。该算法采用非线性路径长度计算方法。为提高算法的成功率,在节点的松弛过程中设计了节点动态路径长度计算,允许节点作多次松弛。为提高算法的执行效率,在节点正向松弛和反向估计过程中引入了受控路径的思想,使算法得到了优化。大量仿真表明,该算法在最短路径获取和路由发现成功率方面都有高效的表现。     

基于遗传模拟退火算法的多约束QOS组播路由优化算法

组播路由问题在计算机网络中是著名的Steiner树问题,是NP完全问题.通过考虑组播通信服务质量需求与网络资源约束,研究了基于服务质量的组播路由选择算法问题,首次提出了一个基于遗传算法和模拟退火算法的多约束组播路由优化算法,该算法在满足带宽、延时、延时抖动及包丢失率约束条件下寻找代价最小的组播树.