一种时延和时延抖动受约束的启发式多播路由算法

多播路由算法在组播应用中是至关重要的,对视频会议等交互式实时组播业务来说,不仅要考虑时延约束,而且要考虑时延抖动约束。本文提出了一种基于最短时延路径的时延和时延抖动约束的启发式算法,仿真结果表明该算法复杂度较低,而且性能也较好,在算法复杂度和性能之间达到了很好的折中。     

下一代网络中多约束路由算法述评

随着新业务的不断涌现,对网络QoS的需求也呈现出多样性,未来网络必然需要提供多约束的QoS路由能力.首先介绍了QoS路由及其路由策略和路由信息发布机制,并在对路由中特征值的选择和构成规则进行分析的基础上,着重讨论了当前多约束路由算法几种类型,分析了算法的性能和特点.最后,分析探讨多约束路由未来可能的研究方向.     

基于矢量映射的多约束服务质量路由计算

针对多维矢量计算多约束服务质量路由出现实际传输路径与源节点期望路径并非一致问题,研究提出矢量映射方式的多约束服务质量路由计算方法。通过数学方法和物理概念相结合的方式,从原理上阐述了新算法矢量映射的合理性,并通过算例和仿真实验方式验证,新算法只需一次性计算就可以获得源节点到各节点保持路径一致的路由。     

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

在分析了多种路由算法的基础上,设计了一种基于蚁群算法的多约束路由算法。该算法采用了非线性路径长度,通过蚂蚁的周游获得长度更短的多约束路径。仿真表明,该算法在最短路径获取和路由发现成功率方面都有高效的表现。     

一种多约束QoS多播路由算法

提出了带宽时延约束、代价最小的QoS多播路由模型,并提出了一种启发式算法求解该问题,分析了算法的复杂度。仿真试验证明,该算法是稳定有效的。它能够在满足两种约束的情况下,使多播树的代价优化。     

基于链路状态的多约束路由预计算算法

作为下一代高速网络的核心问题之一,多约束的服务质量路由(QoSR)至今尚无有效算法,为此基于线性能量函数设计了预计算算法MEFPA.该算法将每个QoS度量的重要性均匀分成若干个等级,从而在多维QoS度量空间中构造出多个均匀分布的线性能量函数;算法通过能量函数将QoS链路状态转化成单一能量值,再使用Dijkstra算法计算最小能量树,最终产生QoS路由表.文章分析了多约束下的线性能量函数对算法性能的影响,给出了判定多维空间中QoS约束的可行区域和不可行区域的方法,最后基于这些理论为多约束QoSR问题给出了预计算算法.广泛深入的实验结果表明,高可扩展性、高性能、易实现的预计算算法MEFPA是一种值得在下一代网络中考虑的路由算法.     

基于Grover搜索的多约束路由算法

寻找满足多约束条件的QoS路由是网络业务能否顺利实施的关键,在研究和分析了当前多种典型相关算法的基础上,提出了一种基于Grover量子搜索思想的多约束路由算法。算法对路径采用了非线性路径长度的度量方法,分析了Grover搜索的特点和优势,根据Grover迭代的实现过程构建了操作矩阵和概率扩散矩阵,通过选择高概率的节点进行数据转发。仿真表明,该算法在最短路径获取和路由发现成功率方面都有高效的表现。     

多加性QoS约束下的链路分离路由算法

对多个加性QoS约束下的链路分离路径问题进行了研究,针对现有算法求解结果依赖于网络结构,难以保证对任意网络都可求得可行解和最优解的问题,提出了一种与网络结构无关的多约束链路分离路径路由算法(MCLPRA,multiple constrained link-disjoint path routing algorithm).该算法基于SAMCRA,采用对解空间先分类,然后按类进行处理和搜索的方法,引入了控制搜索深度的参数,可保证对任意网络都能求得可行解.理论分析表明,MCLPRA能够在现有算法不能求解的情况下解得可行解和最优解.仿真结果显示,MCLPRA的可行解平均求解成功率明显高于现有算法且所求路径对长度也比现有算法更短.     

多约束ATM网络路由选择的改进多标号算法

面向连接的ＡＴＭ网络为保证多种用户服务质量,要连接满足一个或多个约束的同时优化网络资源,这已经被证明是ＮＰ完合问题。本文提出了一种改进的我标号算法,用于解决网络中多个约束条件下的最优径选择问题。该改进算法可以在多项式级的复杂度内找出任意近似程度的最优路径,对于一个２００个节点的具体网络,实际运算结果表明,本文所提算法的循环粢以原始多标号法的１／３以下。     

基于层次分析法和模拟退火的服务质量路由算法

作为下一代互联网的核心问题之一,多约束的服务质量路由(QoSR)用来寻找一条同时满足多个约束条件的可行路径,该问题具有NP完全的复杂度.基于模拟退火启发算法具有较高的性能,但当前研究仅适应于可加性度量.本文基于层次分析法对各种度量:可加性、可乘性及最小性度量构造判断矩阵,求解最大特征根对应的归一化特征向量作为参数构造新的能量函数,再将此能量函数应用到模拟退火中.分析结果表明,该算法不仅具有基于模拟退火的服务质量路由算法的高性能、对网络规模和约束个数都具有很好的扩展性、对QoS约束的分布状况也不敏感的优点,而且对度量类型不敏感.     

QoS路由度量参数的选择问题研究

具有服务质量保证的QoS路由技术是为具有QoS要求的多媒体等网络业务提供有保证的网络服务的核心要素。QoS路由技术由路由选择算法以及用于反映网络状态的路由度量参数的选择、获取与更新两部分内容组成。正确选取合适的度量参数是减小寻路开销，得到简单、具有扩展性的选路算法并获得满足业务要求的QoS路由的前提与基础。本对QoS路由所需要的度量参数的基本性质、选取方法等问题进行了较全面的分析讨论，并简要介绍了度量信息更新的基本策略。     

基于距离向量深度的多约束路径选择算法

 为各种应用提供不同的服务质量(Quality of Service,QoS)保证是下一代高速网络面临的一个重要难题,而服务质量路由(Quality of Service routing,QoSR)则是其中的一项核心技术.本文针对不精确状态信息下的多约束QoSR问题,建立了一种用于求解此类多约束QoSR问题的临界点模型,提出了一种基于距离向量深度的多约束QoS路径选择算法(MCPSA),该算法以已有的QoS路由预计算算法为基础,设法选择一条能够最大程度适应不精确网络状态信息的路径,理论分析表明该算法具有一定的优势.最后,结合已有的路由预计算算法进行了大量的仿真试验,结果表明MCPSA具有很强的问题求解能力,能够有效克服路由状态信息的不确定性.     

一类基于源路由的多约束实时组播路由优化控制算法

随着Internet网络的不断发展,它将成为未来网络服务的平台,而未来网络服务的种类又是多种多样的,既有传统的尽量服务(Best-Effort Service)应用,又有对网络服务质量 [1](QoS:Quality of Service)有着特殊需求的应用.本文探讨了如何在网络层路由这一层面进行QoS组播路由支持的问题.目前,已有许多组播QoS路由算法提出,在QoS路由性能、网络资源使用效率以及路由吞吐率等方面取得了许多好的成果.针对这些QoS路由算法中存在的一些问题,提出了一种组播QoS路由算法.实验结果表明:该算法在适应网络拓扑结构、网络规模、对称/非对称链路负载等方面,与其它QoS路由算法相比,在算法性能上有了一定的改进.     

动态QoS多播路由协议

本文主要研讨了具有QoS约束的动态多播路由问题.文中描述了一种适用于QoS多播路由的网络模型,提出了一种动态QoS多播路由协议(DQMRP),该协议能操作在单播路由协议的顶层,它只要求网络链路(或节点)的局部状态信息,不需要维护全局状态信息.DQMRP可有效地减少构造一棵多播树的开销,多播组成员可动态地加入／退出多播会晤.该协议可搜索多条可行树枝,并能选择一条最优(或近优)树枝将新成员连接到多播树.文中给出了DQMRP的正确性证明和复杂性分析,并通过仿真实验验证了该协议的可用性和有效性.     

性能可调的启发式多约束路由算法

作为下一代互联网的核心问题之一,多约束的服务质量路由(QoSR)用来寻找一条同时满足多个约束条件的可行路径.由于QoSR具有NPC的复杂度,为此我们结合线性、非线性能量函数将多个Qos度量转化成单一能量值,设计了可调节的启发式算法BFS_MCP.该算法将深度可调的广度优先搜索策略引入传统Dijkstra算法中,使它能够随路由器CPU负载和实际网络规模而实时调节算法的运行时间,因而BFS-MCP算法具有广泛的适应性.此外,广泛深入的实验结果表明,广度优先的搜索策略能够极大地提高算法性能.     

一种高速通信网络中多限制路由选择的新方法

对Hopfield神经网络(HNN)模型提出了一个新的能量函数,用以解决多限制路由(MCP)问题。提出利用寻找一个函数的最小问题代替多个约束限制条件,避免了多个限制条件中需要仔细选择多个参数的困难。对6节点和20节点的计算机模拟表明,采用新的能量函数的HNN的收敛速率在10^-3s量级,考虑到硬件实现,这种神经网络可以用于实时的多限路由选择。     

多播路由算法MPH的时间复杂度研究

多播通信是从一个源点同时向网络中的多个成员发送分组的通信服务,一个最小代价的多播路由算法是NP完全的,在时间敏感的应用中其运行时间是一个关键问题.MPH(Minimum Path Cost Heuristic)算法是一个著名的启发式最小代价多播路由算法,本文对该算法进行了理论分析和证明,并做了广泛的仿真实验,结果表明其时间复杂度是O(m²n)而不是过去文献中所给出的O(m²n+e).     

Simulated Annealing Based Multi-constrained QoS Routing in Mobile ad hoc Networks

Multi-constrained quality-of-service routing (QoSR) is to find a feasible path that satisfies multiple constraints simultaneously, which is a big challenge for mobile ad hoc networks (MANETs) where the topology may change constantly. It has been proved that such a problem is NP-complete. Heuristic algorithms with polynomial and pseudo-polynomial-time complexities are often used to deal with this problem. However, existing solutions, most of which suffered either from excessive computational complexities or from low performance were proposed only for wired networks and cannot be used directly in wireless MANETs. In this paper a novel QoS routing algorithm based on Simulated Annealing (SA_RA) is proposed. This algorithm first uses an energy function to translate multiple QoS weights into a single mixed metric and then seeks to find a feasible path by simulated annealing. The paper outlines simulated annealing algorithm and analyzes the problems met when we apply it to QoSR in MANETs. Theoretical analysis and experiment results demonstrate that the proposed method is an effective approximation algorithms showing better performance than the other pertinent algorithm in seeking the (approximate) optimal configuration within a period of polynomial time.