基于OLSR的QoS路由新方案

基于OLSR协议及扩展的最短路径算法,提出了综合折中跳数与带宽的一种路由计算新量度。组合MPR选择算法及路由计算新量度,设计了三种新的QoS路由方案。基于在NS-2环境中对新路由方案及OLSR原始协议进行的仿真,着重分析比较了它们的时延及分组递交率性能,探讨了带宽量度用于路由计算时对这两项性能产生的影响及主要原因,结果表明新量度能有效实现跳数少与带宽大之间的折中。     

基于免疫遗传算法的多约束QoS路由选择算法

该文针对多约束Qos路由选择问题，将其转化为一个多约束赋权图最短路径问题，选择费用、带宽、时延、丢失率为Qos参数。设计了一个基于免疫遗传算法的Qos路由选择算法，该算法主要利用生物免疫机制中的抗原识别、抗原记忆和抗体的抑制、促进作用来控制收敛方向，促进快速求解。实验表明本文提出的算法具有较好的性能，大幅度地提高Qos路由选择的效率。     

基于线性函数的QoS路由预计算算法

多度量的服务质量路由(QoSR)作为下一代互联网的一个重要难题，具有NPC的复杂度．作者设计了启发式算法(LFP)使用线性函数将两个度量转化成单一函数值，进而通过多个不同线性函数实现了与服务质量请求无关的QoSR预计算方式．文章分析了线性函数对算法性能的影响，给出了服务质量约束的可行区域和不可行区域的线性函数判定方法．实验结果表明，算法使用少量均匀分布的线性函数，即可产生具有较高路由性能的QoSR路由表，在可扩展性和路由性能等方面均明显优于现有算法。     

A routing-table-based adaptive and minimal routing scheme on network-on-chip architectures

In this paper, we present a routing algorithm that combines the shortest path routing and adaptive routing schemes for NoCs. In specific, routing follows the shortest path to ensure low latency and low energy consumption. This routing scheme requires routing information be stored in a series of routing tables created at the routers along the routing path from the source to the destination. To reduce the exploration space and timing cost for selecting the routing path, a routing list and routing table for each node are created off-line. Routing table is updated on-line to reflect the dynamic change of the network status to avoid network congestion. To alleviate the high hardware implementation cost associated with the routing tables, a method to help reduce the size of the routing tables is also introduced. Compared to the existing routing algorithms, the experimental results have confirmed that the proposed algorithm has better performance in terms of routing latency and power consumption.     

无线mesh网络多路径QoS路由研究*

基于TDMA提出了一种多路径路由算法。该路由算法是利用两个节点间多条并行的路径作为一个QoS请求的路线。而这多条路径的带宽总和能够满足QoS的带宽要求。通过仿真实验结果证明了该算法相比SPR能明显提高路由的请求成功率。     

基于蚂蚁算法的QoS分布式多播路由选择

采用启发式算法中蚂蚁算法解决包含带宽、时延和最小代价约束条件在内的分布式多播路由问题,基于蚂蚁具有找到蚁巢与食物之间的最短路径原理,并在分析QoS分布式多播路由的基础上,提出了一种基于蚁群算法的QoS分布式多播路由算法,仿真实验表明了该算法是合理的和有效的。     

无线网状网服务质量路由研究

无线网状网允许系统同时使用多个正交信道,以达到提高网络性能的目的.但是干扰问题仍然存在.基于TDMA提出了一种没有干扰的系统模型.基于这种模型,一种启发式的路径带宽计算方法被提出.将这个算法和AODV路由协议相结合,可以建立一条满足服务质量的最短路由.通过仿真实验结果证明了该路由协议相比SPR能明显提高QoS路由的请求成功率.     

基于蚁群算法的QoS多播路由优化算法

蚁群算法是一种新型的随机优化算法,能有效地解决 QoS 受限的多播路由问题。基于蚂蚁具有找到蚁巢与食物之间的最短路径原理工作,并在分析多约束QoS的多播路由的基础上,提出了一种具有全局优化能力的多播路由算法(OQMRA),仿真实验表明了该算法是合理的和有效的。     

基于免疫遗传算法的多约束QoS组播路由选择方法

以具有精英保留的免疫遗传算法（IGAE）为基础,提出了一种新的用来求解带宽、时延、时延抖动受限,费用最小的QoS组播路由选择问题的方法。首先采用预处理机制,将网络结构中不满足带宽约束的链路去掉,利用Dijkstra第k最短路径算法建立编码空间的备选路径集;然后采用基于路径的树结构编码来随机产生初始群体,使种群中的每个个体都代表组播路由问题的一个候选解;最后利用IGAE算法对种群进行优化,最终求得满足QoS要求的组播路由。仿真实验结果表明,该算法具有较好的性能,能以较快的速度搜索到满足QoS要求的费用最小的组播树。     

多约束服务质量路由中的路径压缩算法

多约束服务质量路由是一种能够支持灵活的服务质量控制的有效方案.然而在多约束的环境下,从一个源节点到一个目的节点可能存在多条路径,因而必须相应地增大路由表容量.由于当前路由表的规模已相当庞大,尤其是在高速核心网中,因此,为了在QoS路由表中存储更少的路径信息,需要首先进行路径压缩.文章以解决最优路径压缩问题(OPR)为目标,力图在尽量减小路由表存储规模的同时使路由成功率最大化.为了实现这个目标,文中提出了两个基于贡献区域的算法:增量贡献算法和改进的增量贡献算法.这两个算法从一个大的多约束路径集合中依次计算出具有最大贡献区域的积的路径,最后得到一个小的结果路径集合.大量模拟实验表明,这两个算法能够以较低的运算复杂度获得令人满意的路由成功率.     

Online linear optimization and adaptive routing

This paper studies an online linear optimization problem generalizing the multi-armed bandit problem. Motivated primarily by the task of designing adaptive routing algorithms for overlay networks, we present two randomized online algorithms for selecting a sequence of routing paths in a network with unknown edge delays varying adversarially over time. In contrast with earlier work on this problem, we assume that the only feedback after choosing such a path is the total end-to-end delay of the selected path. We present two algorithms whose regret is sublinear in the number of trials and polynomial in the size of the network. The first of these algorithms generalizes to solve any online linear optimization problem, given an oracle for optimizing linear functions over the set of strategies; our work may thus be interpreted as a general-purpose reduction from offline to online linear optimization. A key element of this algorithm is the notion of a barycentric spanner, a special type of basis for the vector space of strategies which allows any feasible strategy to be expressed as a linear combination of basis vectors using bounded coefficients.We also present a second algorithm for the online shortest path problem, which solves the problem using a chain of online decision oracles, one at each node of the graph. This has several advantages over the online linear optimization approach. First, it is effective against an adaptive adversary, whereas our linear optimization algorithm assumes an oblivious adversary. Second, even in the case of an oblivious adversary, the second algorithm performs slightly better than the first, as measured by their additive regret.     

Loop-free constrained path computation for hop-by-hop QoS routing

We present the distributed multi-constrained routing (DMR) protocol for the computation of constrained paths for QoS routing in computer networks. DMR exploits distance vectors to construct a logical shortest multipath (LSM) for each destination with regard to a given optimization metric, from which a set of non-dominated paths are locally derived at each node. As such DMR is able to find feasible paths as well as optimize the utilization of routing resources.DMR operates in line with the hop-by-hop, connectionless routing model assumed in the IP Internet, and maintains instantaneous loop freedom. Nodes running DMR need not maintain a global view of network state (topology and resource information), and routing updates are sent only to neighboring nodes. This is in sharp contrast with all previous approaches that rely on complete or partial network state for constrained path computation, which incurs excessive communication overhead in large networks and is hard to achieve in practice.     

基于QoS的单播源路由算法研究

保证服务质量的QoS路由是网络中解决QoS问题的一项关键技术,QoS路由的主要目标是为接入的业务选择满足服务质量要求的传输路径,同时保证全网资源的有效利用。围绕度量参数选择问题、寻路问题这两个方面,给出了一个基于源地址的单播QoS次优解路由算法,并对其正确性进行了证明。     

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

研究了一类通信网络中源节点到目的节点的多约束QoS多播路由选择问题,提出了一种解决此类问题的算法.该算法将带宽、时延、丢失率等QoS参数作为约束条件,用基于最短路径算法构造路径选择函数,并依照该函数修正被选路径,使其满足多约束条件.仿真结果表明该算法有较好的性能和较小的时间复杂度,可以方便地推广到多个QoS参数的情况.     

基于累积竞争神经网络的多约束路由算法

针对无约束最优路径问题，提出累积竞争神经网络模型及其搜索算法，该算法具有高度并行性、能获得最优解、结构简单等特点．以QoS路由选择为例，将算法推广到多约束路由问题．实验结果表明，对于大多数多约束QoS问题，在与相应最短路径上节点数目相当的迭代次数内，该算法能找到问题的满意解甚至最优解．     

一种基于稀疏矩阵的求路径集的新算法

最短路径dijkstra算法只能适用于一个QoS参数,而对于多个QoS参数的综合考虑,只能采用遗传算法来优化,提出求编码空间路径集的一种新算法,采用稀疏矩阵存储图的邻接关系,随机选取路径。此算法具有存储空间少、时间复杂度小、不需对网络拓扑做任何修改的优点。     

On supporting high-throughput routing metrics in on-demand routing protocols for multi-hop wireless networks

Researchers have proposed routing metrics other than hop count, such as ETX (expected transmission count) and ETT (expected transmission time), to find routes with high throughput. These metrics are inherently suitable to be used in source routing protocols such as DSR, because link state information needs to be collected for the calculation of the shortest path. In this paper, we propose an efficient and generalized approach called accumulated path metric (APM) for supporting high-throughput metrics (HTMs) in on-demand routing protocols. One advantage of APM is that it is able to find the shortest path, in terms of a particular metric, without collecting topology information and without running a shortest-path algorithm. This will significantly simplify the existing design of supporting HTMs in DSR. We present a proof of the correctness of APM. Moreover, we address the problem of duplicate RREQ (route request) transmissions with existing HTM schemes and present a broadcast ordering (BO) technique to suppress unnecessary RREQ transmissions. We study the performance of APM and BO in both AODV and DSR, and the results verify the effectiveness of the proposed approaches.     

Highly responsive and efficient QoS routing using pre- and on-demand computations along with a new normal measure

Multi-constrained path (MCP) selection is one of the great challenges that QoS routing (QoSR) faces. To address it in an efficient and highly responsive manner, we propose a new QoSR algorithm, namely NM_MCP (normal measure-based multiple constrained path). Using the Dijkstra’s algorithm with respect to each link metric, NM_MCP pre-computes k primary paths in advance, where k is the number of link weights. When a routing request arrives, NM_MCP executes a modified version of the Dijkstra’s algorithm using a newly proposed, normal-measure-based nonlinear cost function. Extensive simulations show that NM_MCP achieves higher success rate in finding feasible paths with less computational cost than existing algorithms. To further improve the performance, we incorporate Pareto and nonlinear look-ahead mechanisms into the algorithm.     

基于遗传算法的非精确信息组播约束路由研究

为求解基于非精确网络状态信息和弹性QoS需求约束的组播约束路由问题,提出了一种自适应的组播遗传算法.通过分析具有非精确度量参数的组播路径满足弹性QoS需求的概率,建立了基于概率法的组播约束路由模型.以种群多样性作为种群进化的度量指标,对进化过程中最大交叉率和最大变异率进行宏观调整;采用优势交叉变异法,在每次进化时,微调各个体的交叉率和变异率.仿真实验结果表明,该算法简单易操作,具有较高的收敛速度,能在一定程度上提高路由请求成功率.     

A dynamic fault-tolerant message routing algorithm for double-loop networks

Message routing is a fundamental function of a network, and fault-tolerance is an important tool to ensure the quality of service of a network. Assume that the network contains at most one faulty element and the algorithm does not know the faulty element in advance. We present an optimal fault-tolerant message routing algorithm for double-loop networks. We show that sending at most two messages with different routing strategies can ensure that one of the messages will be sent through a shortest path that avoids the faulty element. At each vertex, for any destination, the algorithm needs only constant time and space to determine the next vertex to which the message is to be sent.