基于瞬态混沌神经网络的动态路径诱导路由技术

将最短路径问题映射到混沌神经网络提出了一种基于瞬态混沌神经网络的动态路径诱导路由技术.仿真研究表明:将混沌神经网络应用于动态路径诱导系统中求解最佳路径,总能保证网络收敛到全局最优,具有很高的搜索效率.对于单个和多个分组请求均能快速地找到最短路径.     

基于混沌神经网络的最短路径路由算法

飞速发展的计算机网络对路由算法的反应速度提出了更高的要求．神经网络作为一种新的组合优化计算工具。在网络路由方面的应用得到较大关注．与传统的采用串行执行方式的算法相比，神经网络路由算法以其固有的并行执行方式，以及潜在的硬件实施能力，将成为这一领域的有力竞争者．由此提出了一种基于混沌神经网络的最短路径路由算法．仿真结果表明，该算法能有效克服Hopfield神经网络易陷入局部最优解的缺点，并且在收敛速度方面有了很大改进．     

基于混沌控制量的QoS组播路由算法

针对具有多个不相关可加度量的QoS组播路由问题,提出基于混沌控制量的QoS组播路由算法。该算法通过对神经元的内部状态施加一个混沌控制量,可以有效控制神经网络的能量函数增加、减少或保持不变,避免陷入局部最小点。计算机仿真结果表明,该算法能根据组播应用对费用和时延的要求,快速、有效地构造组播树,与其他启发式算法相比,适用于带有较少目的结点的大规模网络。     

Mesh网络路由算法容错性的概率分析

该文基于k-Mesh子网的概念提出了两个简单的基于局部信息和分布式的Mesh网络容错路由算法，并对其容错性进行概率分析；在每个结点具有独立的出错概率的假设条件下，推导出路由算法成功返回由正确结点组成的路径的概率．该文运用严格的数学推理，证明了Mesh网络结点出错概率只要控制在1．87％以内，则对于多达几十万个结点的Mesh网络，提出的路由算法具有99％的概率确保找到正确结点组成的路径．路由算法的时间复杂性是线性的．模拟结果表明路由算法所构造的路由路径长度非常接近于两结点之间的最优路径长度．     

基于有故障区域的Mesh网络目标结点间的最短路由算法

Mesh网络是较早研究的且现在仍然是最为重要的、最有吸引力的网络模型之一。因其结构、规则简单及良好的可扩展性,易于VLSI(超大规模集成电路)的实现,网格(Mesh)网络不仅成为了许多理论研究的基础模型,而且也是许多大型多处理器并行计算机系统所采用的拓扑结构。给出了两种故障情形下的最短路由算法:1)当Mesh的行数大于等于3且列数大于等于3、出现一个矩形故障区域时,给出了任意两个无故障结点间的最短路由算法,并且计算出了路径长度；2)当Mesh的行数≥3且列数≥3、某个结点及其k跳以内的邻居结点出现故障时,给出了任意两个无故障结点间的最短路由算法,并且计算出了路径长度。     

基于软件定义网络的高故障保护率的路由保护方案

软件定义网络(Software Defined Network, SDN)以其强大的可编程性和集中控制的优势得到了学术界的广泛关注。现有的SDN设备在执行报文转发时仍然使用最短路径协议，当最短路径中的结点发生故障时，网络仍然需要重新收敛，在此期间报文可能会被丢弃，进而无法传递至目的结点，给实时性应用的流畅性造成了冲击，影响用户体验。学术界普遍采用路由保护的方案来应对网络故障，现有的路由保护方案存在以下两个方面的问题：(1)故障保护率低；(2)当网络出现故障时，备份路径可能会出现路由环路。为了解决上述两个问题，首先提出了备份下一跳计算规则；然后基于此规则设计了一种软件定义网络下的高故障保护率的路由保护算法(Routing Protection Algorithm with High Failure Protection Ratio, RPAHFPR),该算法融合了路径生成算法(Path Generation Algorithm, PGA)、旁支优先算法(Side Branch First Algorithm, SBF)和环路规避算法(Loop Avoidance Algorithm, L...     

Ad Hoc网络机会路由协议转发候选集算法的研究

应用于无线Ad Hoc网络中的机会路由,结点转发候选集的选取通常是基于最短路径期望传输次数,没有充分考虑无线网络结点进行数据转发的广播特性。以多路径期望传输次数为路由量度,提出一种最优转发候选集算法MCET。实现对无线网络中除了目的结点以外的所有结点选取考虑多路径转发期望值的转发候选集,并在按照结点选取的顺序依次优先排列优先级。仿真结果表明,比较于传统的基于最短路径期望传输次数的机会路由,应用了最优转发候选集算法的机会路由明显减少了数据的平均传输次数,增加了数据报文的成功传输率。     

具有大量错误结点的超立方体网络中的单播路由算法的设计与分析

本文讨论具有大量错误结点的超立方体网络中的单播路由算法，假定Hn是一个局部3－维子立方体连通的n-维超立方体网络并且每一个基本的3－维子立方体中分别最多有1个和2个错误结点，本文提出的单播路由算法能够在线性时间找到路径长度分别为源结点和目的结点之间大约1．5倍和2倍海明距离的次优路径，我们提出的单播路由算法只需要结点知道其邻结点的状态，而无需知道整个网络信息，也就是说，该算法是基于局部信息的，因而该算法具有很强的实际意义。     

基于自适应蚂蚁算法的动态最优路由选择

蚂蚁算法具有很强的随机性和自适应性，基于蚂蚁圈模型和MMAS模型构造的自适应蚂蚁算法，将网络的容量限制、流量变化和最短距离结合起来讨论，通过在找到的最短路径上设置障碍物来模拟网络拥塞，找到源结点→目的结点的多条最优路由序列，以便在实际中实时地、自适应地进行动态路由选择。     

一个针对洗牌交换网的最优路由算法

洗牌交换网是最流行的互连网之一,然而,它的缺点之一便是最短路由算法,最短路由算法,通常也称为最优路由算法,能保证报文在任意一对结点之间沿着最短路径传送。针对包含2^n个结点的洗牌交换网,文中给出了一个O（n^2)时间复杂度的最短路由算法。该算法还可以很容易地适用于立方体连接圈（CCC）,且所得到的算法比已有的CCC路由算法要简单得多。     

MulRoGA: A Multicast Routing Genetic Algorithm approach considering multiple objectives

We solve a multicast routing problem by means of a genetic algorithm (GA) without using multicast trees. The source-destination routes need to fulfill two conflicting objectives: maximization of the common links and minimization of the route sizes. The proposed GA can be characterized by its representation of network links and routes in a variable size multi-chromosome problem; local viability restrictions in order to generate the initial population and define variation operators; selection operators in order to choose the most promising individuals thus preserving diversity, and the fitness function in order to handle the conflicting multiple objectives. The proposed model is called a Multicast Routing Genetic Algorithm (MulRoGA). The model was tested on the 33-node European GéANT WAN network backbone and three other networks (66-node, 100-node and 200-node) randomly generated using the Waxman model on a network topology generator BRITE. On considering each network, a number of solutions were found for changes in the size and node members of the multicast groups, and the source node. The results of the MulRoGA operation suggest a consistent and robust performance in the various cases including comparisons with the methods of unicast shortest path routing, shortest path tree routing (SPT), and simulated annealing (SA) heuristic.     

A distributed shortest path algorithm for a planar network

An algorithm is presented for finding a single source shortest path tree in a planar undirected distributed network with nonnegative edge costs. The number of messages used by the algorithm is O(n^5/3) on an n-node network. Distributed algorithms are also presented for finding a breath-first spanning tree in general network, for finding a shortest path tree in a general network, for finding a separator of a planar network, and for finding a division of a planar network.     

基于加权标识S-图的最短路径研究

为解决智能交通系统中交通运输网络分析和最短路径问题,提出加权标识S-图最短路径算法。根据Petri网基本原理和加权S-图的特点,给出交通网络加权S-图的网模型。阐述加权标识S-图最短路径的基本原理、求解加权标识S-图的最短路径定理及证明。通过交通运输网络示例和实验对算法进行验证,对比分析算法性能。结果表明,加权标识S-图最短路径算法能够更有效地求解交通网络最短路径。     

移动卫星网络中的最短路径算法研究

移动卫星网络的拓扑时变性对其最短路径求解带来新的问题。文章利用提出的移动卫星网络模型,证明了基于传统网络的最短路径算法在移动卫星网络中使用存在局限性,提出了一种适用于移动卫星网络的最短路径求解方法和优化算法,并进行了仿真验证。     

A hill-jump algorithm of Hopfield neural network for shortest path problem in communication network

In this paper, we present a hill-jump algorithm of the Hopfield neural network for the shortest path problem in communication networks, where the goal is to find the shortest path from a starting node to an ending node. The method is intended to provide a near-optimum parallel algorithm for solving the shortest path problem. To do this, first the method uses the Hopfield neural network to get a path. Because the neural network always falls into a local minimum, the found path is usually not a shortest path. To search the shortest path, the method then helps the neural network jump from local minima of energy function by using another neural network built from a part of energy function of the problem. The method is tested through simulating some randomly generated communication networks, with the simulation results showing that the solution found by the proposed method is superior to that of the best existing neural network based algorithm.     

A Routing Algorithm with Candidate Shortest Path

An improved algorithm based on the next node routing principle is proposed in this paper.In this algorithm there is a column added to the classical routing table, in which the candidateshortest distance to the destination node is the entry. When a link fails, the new shortest path inthe nodes connected directly with the failure link can be found immediately (it is just thecandidate shortest path before failure). For all other nodes in which routing tables should bechanged, the required number of control messages and time for convergence are also less thanTajibnapis' algorithm and Predecessor algorithm. The message looping problem does not existin duplex loop networks and is radically improved in mesh networks. These statements areproved by the analysis and simulation in this paper. From the simulation results of a 30-nodemesh network, when one link goes down, the total number of control messages generatedduring convergence with this algorithm on the average is about 30% of Tajibnapis' algorithm.The iterations required is 50% of Tajibnapis' algorithm. The memory space required andcomputation complexity in nodes are almost the same as the two algorithms mentioned aboveand the algorithm implementation is as easy as well.     

分布式系统中的数据邮递QoS模型

传统单播网络传输一般采用Dijkstra最短路径算法建立点到点的最小路径计算。针对此,改进Dijkstra算法,提出一种平衡网络负载的服务质量路由模型,解决分布式数据库系统中数据动态、实时交换路由的问题。实验结果表明,该模型具有较好的稳定性,能避免网络拥塞。     

The shortest path problem with discrete fuzzy arc lengths

In the past, the fuzzy shortest path problem in a network has attracted attention from many researchers for its importance to various applications. In this paper, we propose a new algorithm to deal with the fuzzy shortest path problem. It is composed of fuzzy shortest path length procedure and similarity measure. The former is presented to determine the fuzzy shortest path length from source node to the destination node in the network, and the latter is used to measure the similarity degree between fuzzy length sets. This algorithm not only can yield shortest length but also can offer the actual shortest path to decision makers. An illustrative example is also included to demonstrate our proposed algorithm.     

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

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

双重并行环境下最短路径的研究

并行问题和最短路径问题已成为一个热点研究课题,传统的最短路径算法已不能满足数据爆炸式增长的处理需求,尤其当网络规模很大时,所需的计算时间和存储空间也大大的增加;MapReduce模型的出现,带来了一种新的解决方法来解决最短路径;GPU具有强大的并行计算能力和存储带宽,与CPU相比具有明显的优势;通过研究MapReduce模型和GPU执行过程的分析,指出单独基于MapReduce模型的最短路径并行方法存在的问题,降低了系统的性能;论文的创新点是结合MapReduce和GPU形成双并行模型,并行预处理数据,针对最短路径中的数据传输和同步开销,增加数据动态处理器;最后实验从并行算法的性能评价指标平均加速比进行比较,结果表明,双重并行环境下的最短路径的计算,提高了加速比。