Mesh网络容错单播路由算法

基于k Mesh子网连通的概念,提出一个简单的Mesh网络容错单播路由算法.该容错单播路由算法是基于局部信息的,因为路由算法在路由的过程中,只需要知道其相邻结点的信息而无需知道其他结点出错的情况.对于给定的源结点和目的结点,当路由路径扩展到每一个k Mesh子网中时,该子网均可独立地完成算法的操作而无需考虑算法在其他k Mesh子网中的操作状态.所以,路由算法是高度分布式的.容错单播路由算法的时间复杂性是最优的.模拟结果表明,路由算法所构造的路由路径长度非常接近于2个结点之间的最优路径长度.     

超立方体网络并行容错路由算法

研究了具有大量错误结点的超立方体网络中的并行容错路由算法.其步骤是首先,通过实验分析基于局部k维子立方体连通性容错模型中并行容错路由算法的容错性和效率,然后分析k=3且有多达25.0%的错误结点时并行容错路由算法的容错性和效率.研究结果表明并行路由算法所能找到的并行路径的数目最多可达到min(D(u),D(v)),至少可达到min(Dk(u),Dk(v));如果只考虑k比较小(如3,4,5等)而n比较大(如10,15,20等)的情况,则min(D(u),D(v))与min(Dk(u),Dk(v))非常接近,说明并行路由算法所能找到的尽可能多的并行路径的能力是接近最优的;并行容错路由算法容错性强,效率高.     

几乎紧优双环网的无限族和常数步最优路由算法

得到了含两个参数a和b的紧优和几乎紧优双环网的无限族,其结点数n（a,b;e）和步长s（a,b;e）均为e的二次多项式,并给出它们的常数步最优路由算法,确切地说,至多只要4次算术运算或比较即可得到网络中的源结点0到任一结点的最短路。     

基于服务质量的链路不相交路由算法

针对网络可靠性问题,提出了一种基于链路保护机制的QoS路由算法,该算法首先在图论的基础上得到任意两点间的所有路由,再过滤链路条件使其满足QoS约束,由此求出结点对间的两条链路不相交的最短相似路由,对大数据流复用及高实时性网络都起到较好的优化作用.     

组合星图中一对一容错路由算法

解决了组合星图的一对一容错路由问题.给出了故障节点不超过n-2时,无故障节点s到t的路由算法,证明了算法可以在O(n)内找到一条长度不超过D(Sn,k) 4的路P:s t,其中,D(Sn,k)是Sn,k的直径.运用列举法,推导出组合星图Sn,k中任意点p到固定点Ik的距离公式;并从图论的观点,推导出Sn,k任意2个子图之间的星边数目为(n-2)!/(n-k)!.     

WDM光网络中的RWA分析

智能光网络被认为是下一代高速广域骨干网的最具竞争力的候选方案,代表了下一代光网络的发展方向。路由选择和波长分配（RWA）是智能光网络中的一个关键技术,它是指网络某对节点间有光路建立请求时,如何寻找从源节点到目的节点的路由并在路由上分配波长。优化光通道的选路和波长分配（RWA）是网络设计的核心问题,其主要任务是寻找一条合适的光路并为之合理地分配波长,使有限的资源充分发挥作用,以提供尽可能大的通信容量。     

低开销的片上网络无关容错路由策略

现有容错路由技术大多依赖重路由的解决方案，通过绕行方式避开故障区域，导致故障周围出现流量拥塞；无关路由算法尽管降低了路由开销，但其容错能力有限。针对存在故障节点或故障链路的片上网络，在网络资源受限的情况下，提出了一种不需要提前构建绕行路径的无虚通道低开销无关容错路由策略(OFTR)。当检测到当前节点与目标节点对之间无故障时，采用FTOE-APA规则路由数据包，实现了路径选择的多样性；当检测到节点或链路故障时，根据源节点、当前节点以及目的节点的相对位置关系动态修改输出端口的优先级，使数据包可以通过最短路径转发，最大限度地减少重路由。OFTR路由策略通过改进的奇偶转向规则和动态改变输出端口的优先级既避免了网络死锁，又降低了数据包进入故障周围的概率。仿真结果表明：OFTR路由策略降低了网络平均延迟，节约了网络开销，与其它确定性容错路由算法相比，饱和吞吐率平均提高了8%以上。     

一种新型的自路由多播容错网络

提出一种新的自路由多播的多路径多级互连网络MRCBN,实现自路由并发多播的同时兼顾容错．该网络硬件代价较小,构造规范简单,路由易于实现．在该网络的基础上提出一种新的自路由多播实现方案,将网络分成多播分解子网和置换子网两个部分,通过对多播目标地址预处理后,多播分解子网实现满足一定条件的多播分解,置换子网实现分解后的置换,路由的时间复杂度为O（log2 N）．另外,由于链路数目的增加,为多播路由提供了冗余路径,达到了容错的目的．     

超立方体网络广播容错路由算法

研究了具有大量错误结点的超立方体网络中的广播容错路由算法.假定Hn是一个局部3维子立方体连通的n维超立方体网络,并且每一个基本的3维子立方体中分别最多有1个和2个错误结点,从理论上证明了在最坏情况下基于shouting广播通信模式的广播容错路由算法分别经过最多1.5(n-1)和2(n-1)时间步,就可以将源结点的信息广播到Hn中的所有正确结点中;通过实验验证了在均匀和独立的错误结点分布情况下广播时间步的上界实际上只有n+1,支持了理论分析结果.     

无向图中严格第三短路问题的多项式时间算法

给定一个无向图G=（V,E;w;s,t）,其中s,t是2个固定顶点,w：E→R^＋是边的长度函数．最短路是指所有路中长度最小者,次短路是指长度比最短路严格大的所有路中的最小者,严格第三短路是指长度比次短路严格大的所有路中的最小者．对正权重无向图中严格第三短路问题给出一个O（n^4）多项式时间算法．     

无线传感器网络自适应拥塞控制的路由算法分析

无线传感器网络中节点的覆盖范围有限,因而采用多跳路由传输方式.无线自组网中的多跳路由是由普通节点协作完成的,选择不同的转发节点,会对网络的信息传输产生不同的影响.对不同路由(洪泛路由、最短路径等)算法下的网络自适应拥塞控制进行了分析,研究了不同路由算法下的网络性能和拥塞控制效果.根据节点跳数与缓存占用的关系,提出一种基于节点跳数和缓存占用的性能函数的改进最短路径算法,算法选取使性能函数值最小的节点作为转发节点.最后,通过实验比较了最短路径算法与改进路由算法的网络性能,发现改进路由算法相比最短路径算法,具有较好的网络性能和服务质量.     

基于霍普费尔德神经网络法的ATM计算机通信网络中虚通路的拓扑优化

为了求解ATM计算机通信网络中虚通路的拓扑优化问题，提出了一种基于霍普费尔德神经网络的虚通路拓扑优化算法，给出了神经网络的能量函数及其神经元的动态方程，通过大量的计算机仿真实验，获得了选择系统参数的经验公式，确定出虚通路的拓扑优化问题的系统参数，所得结果能够以较快的速度收敛到具有很高稳定性和有效性的最优解和近优解，并且与传统的最短路径路由法和最小负载路由法比较，本算法所得解的质量更好．这些研究结果对于解决宽带综合业务数字网及其他工程系统中大量出现的复杂优化问题具有重要的理论价值和广阔的应用前景．     

基于软件定义网络的多路径路由算法性能研究

基于不相交多路径的路由方案在负载平衡、容错等方面具有明显优势,但存在计算复杂度高的缺点,故对应的分布式算法难以在网络中大规模部署.通过分析软件定义网络的特点,论证了在其网络中部署不相交路径路由方案的可行性.其次,基于网络流的性质与不相交路径的图论性质,设计并实现了计算不相交路径的算法.最后,通过一系列基于不同网络模型的对比实验,验证所提算法较传统最短单条路径路由算法具有更佳的负载均衡.实验结果表明,该算法的性能与网络中链路能承受的负载极限阈值有关.     

无线移动Ad Hoc网络的路由技术研究

无线移动Ad Hoc网络(MANET)作为可移动分布式多跳无线网络，没有预先确定的网络拓扑或网络基础设施以及集中控制。为了在如此的网络中促进通信，路由技术主要用于在节点之间发现路径。AdHoc网络路由协议的主要目的是在网络拓扑的动态变化下任意两个节点之间建立一个使得通信总费用和带宽耗费最少的正确和有效的通信路径。本文论述无线Ad Hoc网络的特性、问题和技术，并通过不同的标准对存在的一些路由协议进行分类和比较。     

传感器网络分布式能量平衡路由

提出一种分布式能量平衡路由算法,该算法根据邻接点的能量和状态信息达到各个节点能耗的平均.对能耗过大的节点采取保护措施,汇聚节点sink在广播兴趣阶段形成一棵广播树,各个节点距sink节点的远近不同即在广播树中处于不同的层次,从而传播网络中的任一节点就有父节点、兄弟节点和子孙节点,使得所选路径为距sink节点最短即路径最短能量平衡路由,节点感知各层次节点情况就可以根据其能量信息来重选路径.分析和仿真结果表明,这种路由方法计算简单,所需信息传输量小,可有效提高网络的生命期.     

具有不可靠链路的通信网最佳可靠路由的确定

研究了对给定拓扑结构的通信网在假定节点完全可靠而边存在随机破坏的情况下,通过计算点对间的路由概率确定最佳可靠路由的两种算法———邻接矩阵算法和动态路由算法－ 邻接矩阵算法通过构造网络的邻接矩阵及一些相关矩阵,利用深度优先搜索的方法找到点对间的所有路由,进而计算各路由的概率并由此确定最佳可靠路由－ 动态路由算法则给出了在链路失效后,按照最短路径原则由失效链路的起始点重新构造最佳可靠路由的方法－ 图１,参５－     

无线Ad Hoc多径路由性能分析

Ad Hoc无线网络环境下的多径路由是近来研究的热点之一.在DSDV路由协议的基础上,沿用传统路由协议中的最短路径准则,提出一种新的多径路由算法.算法通过建立一个多径路由表结构,实现多径扩展,并从理论上推导出特定仿真环境下路径的选择条数.最后分别对DSDV及其改进的多径路由协议进行仿真,结果表明多径路由算法以一定的路由开销为代价,有效地改善了网络的递交率及吞吐量性能.     

网络最短路的提速问题

网络最短路提速问题起源于交通运输、计算机信息传输等领域,具有重要的理论和实际应用意义.对一般网络来说,该问题是NP-完全的.对(0,1)-提速问题的指定路线的提速问题两种情况分别进行了研究,证明了(0,1)-提速问题是NP-完全的、一般网络在指定路线情形下的提速问题是多项式可解的,给出了单源多汇网络G中提速问题的O(nm log n)算法.     

最短路径子图

在大型网络中两节点之间的最短路径常常不止一条,而且在带限制条件的路径选择等应用上,常常需要找出多条最优或近优的路径.一些经典的单源最短路径算法,如Dijkstra算法,能找出一条从起始点到目的点的最短路径,但并不能求解两点之间的所有最短路径.本文给出了最短路径子图的概念,用于存储图中两节点之间所有最短路径信息,能够节约存储空间.并给出了最短路径子图构造算法SPSG,其时间复杂度为O(n e),比同类算法时间复杂度更低.随机网络模型的仿真结果表明:SPSG算法效率更高.     

一种基于联合频谱分配技术的认知网络路由协议

认知无线网络中,由于不同认知节点可用频道的差异和频繁的变化,使得传统的无线路由算法无法在认知无线网络中工作.本文提出了一种基于频道可用率和路径累计时延的路由机制,既保证了数据的投递率,又降低了数据投递延迟.实验表明,该机制在一级网络干扰频繁和链路质量多变的环境下具有更好的路由性能.