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

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

直角坐标系下双环网络G(N;r,s)容错路由研究

将直角坐标系引入双环网络,通过直角坐标系,系统研究双环网络G(N;r,s)的容错路由,提出将双环网络和直角坐标系结合起来,使节点可视可控.基于直角坐标系研究双环网络G(N;r,s)的容错路由,解决多节点故障时源节点如何快速建立和目的节点之间的路由.首次提出故障节点封闭区和节点逃逸区,在此基础上提出多节点故障时容错路由最优算法,并用实例验证算法的正确性.     

IP/DWDM光因特网中的容错路由选择机制

研究了IP/DWDM光因特网中的容错路由选择机制,对动态到达的光路请求进行路由选择和波长分配,并且提供故障光路恢复能力·在考虑网络负载均衡的基础上,为光路请求进行路由选择·以减少端到端延迟为目的,提出一种启发式算法进行波长分配·针对光路上的单点/多点故障(包括链路故障、节点故障和信道故障),基于预防式和反应式容错模式,设计了四种容错路由选择机制·仿真结果表明,提出的这些机制是可行和有效的·     

一种低延迟的无虚通道No C容错路由算法

随着特征尺寸的减小,片上网络发生故障的概率显著增加.为了提高片上网络的容错能力,降低网络延迟,提出一种低延迟的无虚通道容错路由算法.该算法在转向模型的基础上,采用旁路结构,保持故障节点在固定方向上的连接,能够有效降低数据包延迟同时应对故障节点任意数量、任意分布的情况. 8×8的2D Mesh NoC的仿真结果表明,相比于参考的两种算法,本算法在单故障且通信负载为30%时,平均延迟分别降低4.35%和20.20%,且在多故障情况下同样具有较好的性能.     

一种新的点对点路由算法容错性概率分析

随着网络规模不断扩大,网络节点出现故障的可能性也随之增加,为了提高网络容错能力,增强网络的连通性能,提出了一种新的点对点路由算法,首先阐述了新算法的工作原理,然后对网络中采用和不采用新算法2种情况进行了容错性概率分析,分析表明,新路由算法可以提高网络的容错能力,增强网络稳健性.     

最小能量节点不相交多路径的自组网路由算法

为减轻节点不相交多路径路由负载和解决路径间的耦合问题,提出了一种基于定向天线的最小能量节点不相交多路径自组网路由算法(RMENDMRDA).初始时该算法应用优化波宽选择算法确定定向天线的最小扇形覆盖区域,从而节省能量消耗,在选择累计能量最小的节点不相交多路径时采用链路可靠性选择算法,以满足链路的可靠性要求.分析及模拟结果表明,该算法路由负载更小、路由发现频率更低.与源传输能量选择路由算法和节点不相交多路径路由算法相比,RMENDMRDA的数据包投递率提高了18%,路由负载降低了24%,节省能量约8%.     

能量感知多路径负载均衡路由算法

针对移动自组织网络的网络拥塞问题,基于能量感知技术并结合负载均衡和拥塞控制方法,提出了一种能量感知多路径负载均衡路由算法。该算法利用能量感知选择满足条件的节点作为路由节点,建立多条连接源节点和目的节点的有效路径;同时分析路径的跳数、节点缓冲区的占用情况,从有效路径中选出用于传输的最优路径;然后对最优路径上的节点和路径的负载情况进行建模分析,当节点能量、节点负载、路径负载到达设定的阀值,就将最优路径上的流量分流到其它路径。利用NS2仿真软件,在不同的场景下对该算法以及QMRB、SMORT进行仿真测试。仿真结果显示:提出的算法与其它路由算法相比将网络性能提升了近20%,起到了均衡负载的作用,能有效地解决网络拥塞问题。     

蜂窝网络上的虫孔容错路由算法

蜂窝网络是新近提出的并行多处理机互连网络结构.针对该网络提出了一个无故障最短路径单播路由算法,然后基于该算法使用虚拟信道技术设计了一个凸形故障容错路由算法.这2个算法都是无死锁的,容错路由算法也只使用局部信息路由报文.     

传感器网络中基于应用规则与概率的动态路由算法

针对连续数据分发型传感器网络，提出一种基于应用规则和概率的动态路由算法。算法基于节点的状态信息，与应用规则交互后周期性地构造一棵广度优先的数据汇集树形成动态路由路径。数据汇集树由初始生成树建立与生成树修补两阶段组成。算法首先将节点状态作为输入参数提供给应用规则，再由规则使用预定义公式计算出节点当前轮成为树节点的概率，形成初始树；而后在树修补阶段，通过添加一些新的普通节点为路由节点对初始树进行修补，完成树的连通覆盖。仿真结果表明，与TinyOS信标算法相比，在本文设计应用规则下的路由算法具有高数据传输率、时延短、平均能耗低的优点，能延长网络生存时间。     

超立方体中基于安全矩阵的容错路由

超立方体网络拓扑结构是多处理机系统中常见的一种.随着多处理机系统规模的增大,系统出现链路与结点故障的概率也随之增大.针对超立方体结构的容错路由设计在信息传输过程中出现迂回的情况,提出了安全矩阵(safety matrices,简称SMs)这一概念,给出了一种建立SMs的方法及其容错路由算法.n维超立方体每个结点所需的存储开销为n2个字,安全矩阵记录了局部更多的信息.与传统的路由算法相比,该算法可以避免信息在传输过程中出现迂回和死锁,使路径达到最优.     

基于零序电流有功分量的配电网接地故障定位

为解决数字化环境下中性点经消弧线圈并、串电阻接地系统的单相接地故障区段定位问题,对此类系统中出现单相接地故障时电网内全部线路首端保护装置可测得的零序电流进行了分析,并给出了零序电流有功分量的一般分布规律.在此基础上结合配电网故障定位的一般矩阵算法,提出了基于零序电流有功分量的配电网单相接地故障区段定位算法,并遵循IEC61850标准创建了故障定位算法的逻辑节点与逻辑设备,为小电流接地故障定位系统的设备模型建立提供了参考.基于PSCAD/EMTDC软件的配网典型故障仿真结果验证了单相接地故障定位算法的准确性.     

有容量约束车辆路径问题的蒙特卡洛模拟算法

带容量约束的车辆路径问题是一个NP-hard问题,针对此问题将蒙特卡洛模拟方法与流行的节省算法结合,提出Flag-MCS-CWS算法,该方法通过对CWS算法得到的节省序列进行蒙特卡洛模拟,适用于不同节点数、不同车辆载重量的车辆路径问题.在标准数据集测试,相比当前最优解有平均0.75%的改进,为车辆路径问题提供了更加有效的解决方案.     

BGP网络故障模型与检测算法

BGP网络故障严重影响自治系统间的网络性能,根据Internet中观测点获得的BGP路由信息,描述域间路由系统的BGP网络模型,建立BGP故障事件模型,为BGP网络的拓扑变化提供一种简明的描述方式.根据高度时间相关性的BGP路由事件触发的网络拓扑变化,提出查找故障链路的近似算法.提出的BGP网络故障查找模型和算法能够比较准确地检测Internet域间路由系统中的路由异常事件.     

被动测试中的错误诊断算法

介绍了被动测试的有限状态机模型、错误模型和错误检测算法，给出了单个错误的诊断算法并分析了其时间复杂度，将所提出的算法推广到对多个错误的诊断，以在路由协议OSPF(Open Shortest Path First)的接口有限状态机上做的模拟实验为例来说明算法的有效性．     

考虑节点能量消耗的无线传感网络平衡路由算法设计

传统方法设计无线传感网络路由中,往往忽略了节点的能量消耗以及不同节点能耗的差异性,导致出现节点分布不均匀、路由平衡度较差、整体开销成本较大、能耗高等问题.为此,提出了考虑节点能量消耗的无线传感网络平衡路由算法.构建节点能耗模型,建立无线传感网络梯度和传感器节点之间的信息素,结合蚁群算法求解整体能耗模型,实现无线传感网络...     

Fault-tolerant routing algorithm for network-on-chip based on dynamic XY routing

In order to ensure the reliability of network-on-chip (NoC) under faulty circumstance, a dynamic fault tolerant routing algorithm is proposed. This algorithm can implement detour routing when there are both static and dynamic permanent faults in the network. That means the packet is able to move around the faults to the destination with a non-minimum path. In addition, the multi-level congestion control mechanism gives the algorithm the ability to distribute the load over the whole network and to avoid hotspots around the faults. Simulation results demonstrate the advantage of the proposed routing algorithm in terms of average packet latency and packet loss rate compared with negative-first routing algorithm and DyAD routing algorithm in the presence of permanent faults. For the proposed algorithm, it can get much less average packet latency and lead to less than 20% packet loss rate. Biography: LI Xiaohui (1982–), male, Ph.D. candidate, research direction: SoC design Methodology, NoC design.     

基于反向路由的Zigbee网络本地修复机制改进

针对当前ZigBee网络链路故障修复机制时延长和数据分组丢失的缺陷,提出了一种改进的Zigbee网络本地修复算法(ILRA-AODVjr)。通过空闲路由节点反向路由机制,向邻居节点广播一个具有两跳生命周期反向路由构建报文S-RREQ,为空闲节点产生多个备用局部路由,增加网络中节点有效路由数量,提高网络发现路由速度,缩短网络局部故障修复时间。仿真结果表明,改进的Zigbee网络本地修复算法,有效减少了网络故障修复响应时间,延长网络生命周期,减轻了网络拥塞和延迟。     

二维网格计算机上容错的虫孔组播路由算法

提出了一个决定型的和一个自适应型的二维网格上容错的虫孔组播路由算法，所提出的算法用于路径的组播路由模型，而不是在网络中找出哈密尔顿路径和欧拉路径，所提出算法的无死锁性依赖于目标地址集的顺序和故障处理机周围的路由路径的选取，它容许一个故障处理机模型。     

基于移动预测的集群组网分簇路由协议

针对无人机集群组网中拓扑结构更新快、网络通信效率低的问题,提出了基于移动预测的分簇算法MPC,并提出了一种分簇路由协议MPC-R。灰色-WNN联合预测模型的基础上,通过将预测结果运用在方向、速度、位置评价因子上,得出移动状态评价因子。综合计算移动因子和链路保持时间进行簇头选择,路由协议簇间采用被动路由发现机制,簇内采用主动路由发现机制。通过仿真,对预测准确性、分簇算法、路由协议进行验证,结果表明:WNN提高了预测的准确性,分组投递率提高了3%～4%。该分簇算法延长了簇头持续时间和平均链路保持时间,能够提高分簇稳定性。相应的路由协议与其他同类协议相比降低了端到端时延,提高了数据包分组投递率和路由性能。     

适于物流配送车辆导航路径规划的遗传算法研究

本文主要针对物流配送车辆导航本身的特点,分别对遗传算法的初始种群产生方法,交叉方法,变异方法进行了改进,并实现了遗传算法中参数的自适应调整,提出相应的改进型遗传算法。实验结果表明,本文提出的自适应遗传算法能快速有效地解决物流配送中的点到点型路径规划,能满足物流配送车辆导航实时性的要求,是适于物流配送的有效算法。