基于k-最短路由的mesh光网络p圈构造方法

P-cycle是mesh光网络中一种十分优秀的保护算法,圈构造算法是p圈法设计的前提.首先介绍了圈的概念及常见圈构造算法和基于k-最短路由的p圈启发式算法,提出了基于k-最短路改进metaDijkstra的圈构造算法.实验仿真表明该方案比较适合网状光网络中的圈构造.     

基于GMPLS的智能光网络路由技术研究*

在比较了ASON与传统网络的路由区别之后,提出了基于GMPLS的ASON路由体系结构,对其中关键的模块——约束路由进行了分析,重点描述了受限最短路径优先（CSPF）算法的原理与实现过程,并进行了仿真,验证了该算法在重路由选择上的有效性。     

基于最短路径的道路网络k近邻查询处理

针对基于空间道路网络的k近部查询处理,提出了分布式移动对象更新策略以有效减少服务器计算代价,利用基于内存的空间道路网络部接矩阵、最短路径矩阵结构和移动对象哈希表索引分别对道路网络无向图与移动对象进行存储管理。提出了基于最短路径度量的网络扩展搜索(SPNE)算法,以通过裁剪网络搜索空间来减少k近部查询搜索代价。实验表明,SPNE算法的性能优于传统的NE和MKNN等k近邻查询处理算法。     

基于遗传算法的最短路径路由优化算法

论述了用启发式遗传算法解决最短路径路由的优化问题.采用可变长度染色体(路由串)和它的基因(节点)应用于编码问题.交叉操作在交叉点进行部分染色体(部分路由)交换,变异操作维持种群的多样性.该算法采用简单维护操作维护好所有的不可行的染色体.交叉操作和变异操作相结合保证了最优解的搜索能力和解的全局收敛性.计算机仿真实验证明该算法快速有效,可靠性高.     

基于遗传算法的最短路径路由优化算法

论述了用启发式遗传算法解决最短路径路由的优化问题.采用可变长度染色体(路由串)和它的基因(节点)应用于编码问题.交叉操作在交叉点进行部分染色体(部分路由)交换,变异操作维持种群的多样性.该算法采用简单维护操作维护好所有的不可行的染色体.交叉操作和变异操作相结合保证了最优解的搜索能力和解的全局收敛性.计算机仿真实验证明该算法快速有效,可靠性高。     

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

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

基于遗传算法的最短路径路由优化算法

论述了用启发式遗传算法解决最短路径路由的优化问题,采用可变长度染色体(路由串)和它的基因(节点)应用于编码问题,交叉操作在交叉点进行部分染色体(部分路由)交换,变异操作维持种群的多样性.该算法采用简单维护操作维护好所有的不可行的染色体.交叉操作和变异操作相结合保证了最优解的搜索能力和解的全局收敛性.计算机仿真实验表明该算法快速有效、可靠性高.     

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

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

基于改进伊藤算法的最短路径网络路由优化算法

通过对网络路由最短路径问题进行分析,使用伊藤算法求解以费用最低为目标的路由优化问题,建立最短路径路由问题的网络结构模型。为加快伊藤算法求解费用最低路由的收敛速度,在状态转移策略中引入费用启发因子,优化漂移和波动过程,并改进路径权重更新规则。将种群交叉思想引入算法中,利用种群间的信息交流加快了算法的收敛速度并提高了寻优能力。在2-opt算子局部优化的基础上加入反转算子,避免陷入局部最优解。文中还对算法的收敛性进行了系统分析。实验结果表明,改进后的算法有效提升了收敛速度并加强了寻优能力。     

A shortest path routing algorithm using Hopfield neural network with an improved energy function

A shortest path routing algorithm using the Hopfield neural network with a modified Lyapunov function is proposed. The modified version of the Lyapunov energy function for an optimal routing problem is proposed for determining routing order for a source and multiple destinations. The proposed energy function mainly prevents the solution path from having loops and partitions. Experiments are performed on 3000 networks of up to 50 nodes with randomly selected link costs. The performance of the proposed algorithm is compared with several conventional algorithms including Ali and Kamoun's, Park and Choi's, and Ahn and Ramakrishna's algorithms in terms of the route optimality and convergence rate. The results show that the proposed algorithm outperforms conventional methods in all cases of experiments. The proposed algorithm particularly shows significant improvements on the route optimality and convergence rate over conventional algorithms when the size of the network approaches 50 nodes.     

IP Mesh网络的多约束QoS选路研究

多约束QoS路由算法一直是研究重点和难点,是一个有待解决的NP完全问题。针对IP Mesh网络的特点,设计出相应的完全图,并且推出了n个节点的完全图路径总数目公式。提出了一种CBFS_MCP算法,首先用Dijsktra最短路径算法对节点和边进行删减,将完全图简化,再在简化图上用类BFS算法通过“约束条件夹逼”和不断剪枝,寻找一条从起点s到终点t的符合两个约束条件的可行路径。实验结果表明CBFS_MCP算法有着良好的算法性能。     

一种面向城市复杂路网最短路径提取的定向收敛算法*

为提高城市复杂路网最短路径提取的效率,针对路网数据量大、结构密集等特点,研究了路网节点之间最短路径的分布特征,通过引入收敛点方式,设计并实现了一种面向复杂路网最短路径快速提取的定向收敛算法。为检验该算法的有效性,利用某城市道路交通网络进行了实验和分析,并与Dijsktra算法、A*算法等比较,证实了该算法能够提高路径搜索效率,且随着城市路网规模的扩大定向收敛算法的高效性将愈加明显。     

基于树形拓扑的无线Mesh网络路由协议研究

研究和分析了无线Mesh网络路由协议及其特点,提出了无线Mesh网络路由协议设计原则.遵循这些原则,充分利用Mesh网络全相连的优点构建出树形逻辑拓扑结构,该拓扑结构能满足无线Mesh网络业务特点的要求.在该拓扑树基础上设计了一种基于树形拓扑的无线Mesh网络路由协议(TTRP),该协议采用无开销的源地址学习方式构建路由相关表项,快速链路切换和路由重定向机制大大提高了TTRP路由协议的健壮性和网络的抗毁性.网络仿真结果表明了该路由协议的可行性.     

基于优先队列的时变网络最短路径算法

提出了基于优先队列的时变网络最短路径算法,能克服传统最短路径算法难以对时变网络求解最短路径的缺陷。提出的时间窗选择策略能够在算法求解过程中为节点选择合适的时间窗以降低路径长度,从而求得精确解。进一步地,算法使用了优先队列组织节点集合以提高计算效率。在随机生成的网络数据以及美国道路数据上的实验表明,基于优先队列的时变网络最短路径算法与经典方法相比,不仅能够求得精确解,运算速度也有所提高。     

A survey of routing algorithm for mesh Network-on-Chip

With the rapid development of semiconductor industry, the number of cores integrated on chip increases quickly, which brings tough challenges such as bandwidth, scalability and power into on-chip interconnection. Under such background, Network-on-Chip (NoC) is proposed and gradually replacing the traditional on-chip interconnections such as sharing bus and crossbar. For the convenience of physical layout, mesh is the most used topology in NoC design. Routing algorithm, which decides the paths of packets, has significant impact on the latency and throughput of network. Thus routing algorithm plays a vital role in a wellperformed network. This study mainly focuses on the routing algorithms of mesh NoC. By whether taking network information into consideration in routing decision, routing algorithms of NoC can be roughly classified into oblivious routing and adaptive routing. Oblivious routing costs less without adaptiveness while adaptive routing is on the contrary. To combine the advantages of oblivious and adaptive routing algorithm, half-adaptive algorithms were proposed. In this paper, the concepts, taxonomy and features of routing algorithms of NoC are introduced. Then the importance of routing algorithms in mesh NoC is highlighted, and representative routing algorithms with respective features are reviewed and summarized. Finally, we try to shed light upon the future work of NoC routing algorithms.     

基于QoS的光网络路由选择算法的研究

满足数据业务QoS是网络发展的必然要求,现行数据疏导技术更多考虑是提高带宽利用率,对QoS中其他指标如时延、丢包、吞吐量等研究甚少。提出了基于QoS的路由算法是在现有理论基础上综合考虑了QoS的其他指标。算法测试结果表明,主/备用LSP的路由选择更好地满足了数据业务的传输需求。     

多域光网络中应用混合拓扑聚合的分段保护算法

研究了多域光网络中的路由保护问题;为了克服多域光网络中可扩展性约束,提出了一种混合拓扑聚合方法。该方法结合了全连通和生成树拓扑聚合的优点,在网络中需要存储和发布的链路状态信息与聚合信息反映实际物理拓扑的精确性之间进行了折中;然后在此混合拓扑聚合方法的基础上,提出了一种基于查询机制的多域分段保护算法。仿真表明,相比传统的多域保护算法,该算法阻塞率低,可扩展性好。     

基于矩阵运算的公交查询高效算法

目前绝大多数公交查询算法是基于最短路径查找算法的改进,但最短路径算法本质上不适合公交线路的查询。定义一种新型的直达矩阵,并提出两种新的矩阵运算。在此基础上,建立起了一种基于矩阵运算的高效公交查询算法。对算法进行分析后,引入了一些重要的改进。最后在计算机中把提出的算法应用到实际数据,取得了理想的效果。