SPORT:一种面向基三分层互连网络的最短路径路由算法

针对基三分层互连网络(THIN)中已有编码方法和路由算法不能应用于非平衡构造THIN的问题,提出一种既适合表示平衡构造THIN又适合表示非平衡构造THIN的编码方法,并基于该编码方法提出一种最短路径路由算法SPORT. 该算法采用源路由方式,可以在源节点计算目的节点的最短路径. 使用Noxim片上网络模拟器搭建了仿真实验平台,并将SPORT算法与已有的DDRA算法及Min-DDRA算法进行了比较,实验结果表明,SPORT算法具有较小的通信延迟. 此外,还研究了局域性对THIN和2D-mesh两种网络通信延迟的影响,实验结果表明,对局域性特征明显的程序负载,THIN的通信延迟要低于2D-mesh.      

一种新型片上网络拓扑结构及其自适应路由算法

由于片上网络的拓扑结构和路由算法直接影响片上网络的传输延迟和传输效率,提出了一种新的片上网络拓扑结构——半环形网格结构(H-annular Mesh).它以2D-Mesh拓扑结构为基础,由顶角节点向中心节点引入连线构成半环形的网格结构,充分结合了2D-Torus拓扑结构的优点.并针对H-annular Mesh拓扑结构,提出了HAA-XY自适应路由算法.仿真结果表明,基于H-annular Mesh拓扑结构和HAAXY路由算法的片上网络,能够有效地减少网络传输延迟,并可实现多方向及多节点的数据并行通信.     

最短路径自适应路由的路径条数及可缓冲的数据包数目

在采用最短路径自适应路由方案的片上网络中,从源节点到目的节点具有多条可能的路径,采用最短路径有助于提高片上网络的效率。片上网络每一级路由器都能缓冲一定量的数据包,从源节点到目的节点的距离越远、路径数目越多,可缓冲的数据包数目越多。处理单元(Processing Element, PE)间数据传输需要的流量控制数据包越少,数据传输的效率越高。本文提出从源节点到目的节点可缓冲数据包数目的两种计算方法,并通过计算机搜索和仿真进行了验证。研究结果有助于提升对采用最短路径自适应路由的片上网络的行为的认识,从而设计更好的PE间数据传输方案。     

空间信息网络的改进路由算法研究

研究了空间信息网络的拓扑结构和路由特点,对网络的里间链路长度和覆盖性能进行了分析。针对空间信息网络的特．最对现有算法进行了改进,并加入一些优化措施。从而形成一种新的适用于空间信息网络应用的动态路由算法,谊算法能够找出任意两颗卫星间通信的最佳路径集合,同时能够在链路质量容许的情况下,尽量避免通信链路切换的发生,从而较大地提高了系统性能。通过仿真和分析表明谊算法提高了系统性能,降低了切换概率,增加了链路的可靠性,且相对付出的链路代价较小。     

多核处理器核间互连的新型互连网络

提出了一种用于片上核间互连的新型互连网络--基三分层互连网络. 该网络具有明显的层次性和对称性以及良好的扩展性. 与2-D Mesh相比,在网络规模不大时,基三分层互连网络更适用于构建片上核间的通信网络. 仿真结果表明,该网络具有较低的平均通信延迟和较高的平均吞吐率.     

一种基于2D-mesh的片上网络无死锁容错路由算法

为解决片上网络中的永久性故障问题,提出一种基于2D-mesh拓扑结构的无死锁容错路由算法.定义了新的故障块生成规则,减小了故障节点的区域和受影响的健康节点数目,设计了一种故障节点探测和绕道路径生成算法,通过递归式消息传递实现了故障块区域的建立和绕道路径列表的生成.在绕道容错路由算法中,采用部分路由表与路由规则相结合的方法,通过在报头中加入绕道路径列表的方式引导报文绕过故障区域.结果表明,与现有算法相比,所提出的容错路由算法在随机均衡负载和热点负载2种情况下的延时都有所降低.     

一种新的片上网络拥塞感知容错路由算法

提出一个有效的路由通道选择机制,实现了基于片上网络(networks on chips,NoC)的拥塞感知的自适应容错路由算法(congestion-aware adaptive fault-tolerant routing algorithm,CAFR).该算法基于Up*/Down*路由算法得出源节点到目的节点每条路径的转向概率,再根据每条链路的两端路由器剩余内存时隙得出一个加权链路,最后由每条路径权重值和其路径的转向概率计算出源地址到目的地址各条路径的总权重值.实验结果表明,在无故障条件下,该算法的平均延迟和平均吞吐率都能维持较好水平.在故障条件下,该算法相对其他算法在吞吐量衰减方面有很大改善,尤其在故障率达到20%时,该算法吞吐量只有44.32%的衰减,而其他有容错性能的算法衰减达到48%~70%.     

无线网络中一种智能路由算法

一个ad hoc网络是一个多跳无线网络，网络中的节点互相通信而不依赖于预先架设的固定基础设施，这种动态网络的最重要特点是寻找在通常情况下很好执行的路由算法。基于“簇”的算法是最有效的算法，目前，创建和维持“簇”通常是基于启发式方法。MWIS是一个分布式算法用于在一个无线网络拓扑图中确定最大权独立集算法，而划分网络节点为“簇”的问题可以很容易简化为寻找最大权力集问题。基于MWIS，我们提出了寻找一个最大向量权独立集算法MVWIS并且通过MATLIB进行了仿真实验。     

空间信息网络的改进路由算法研究

研究了空间信息网络的拓扑结构和路由特点,对网络的星间链路长度和覆盖性能进行了分析。针对空间信息网络的特点对现有算法进行了改进,并加入一些优化措施,从而形成一种新的适用于空间信息网络应用的动态路由算法,该算法能够找出任意两颗卫星间通信的最佳路径集合,同时能够在链路质量容许的情况下,尽量避免通信链路切换的发生,从而较大地提高了系统性能。通过仿真和分析表明该算法提高了系统性能,降低了切换概率,增加了链路的可靠性,且相对付出的链路代价较小。     

一种求解最短路径路由的遗传优化算法

将可变长度染色体——路由串和它的基因——节点应用于编码问题,交叉操作,在交叉点进行部分染色体（路由串）交换,变异操作,以维持种群的多样性。使用该算法进行简单操作,可以维护好所有不可行的染色体;交叉操作和变异操作相结合,能保证最优解的搜索能力和解的全局收敛性。实验结果证明,该算法收敛快,可靠性高。     

消息传递型片上多核系统的设计

基于消息传递的编程模型设计了一款片上多核系统,该系统在4SymboltB@4的2D mesh片上网络中集成了16个小型RISC处理器,这些处理器各自使用一个可配置的私有SRAM用于指令和数据的存储,而处理器间的数据包通信则通过虫孔交换的路由器及网络接口实现.此外,在软件层面实现了基本的数据传输与进程同步接口,并采用SPMD并行模式设计了3个应用案例,以对该系统进行验证和性能分析.仿真及FPGA测试结果表明,对于整数矩阵乘法、浮点FFT计算以及基于灰度图像的模板匹配问题,该多核系统的并行加速比最高可分别达到7.6,10.5和15.9.     

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

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

基于队列的处理器亲和机制及在网络转发中的应用

提出一种新的基于多报文队列的处理器亲和机制,与传统基于网络接口的亲和机制相比,消除了多处理器对共享资源的竞争,优化了处理器的CACHE行为,降低了互斥锁的影响范围,能够有效提升多核处理器系统的网络转发处理能力.试验结果显示,在复杂网络环境下,基于队列的亲和机制报文转发性能较传统基于接口的亲和机制提高了1.8倍.     

基于拥塞避免的卫星网络路由算法

提出一种基于低轨道和静止轨道星座的双层网络新路由算法, 利用低轨道卫星及其星间链路构成的网状拓扑对星上路由进行计算, 并通过拥塞避免和数据包分类机制进行优化, 解决了卫星网络中由于业务流量大而导致的网络拥塞问题. 仿真结果表明, 该方法降低了网络平均端到端的时延和平均丢包率, 从而提高了网络性能.     

声传感器网络路由协议设计

声传感器网络是一种有效的情报侦察手段,路由协议是其关键技术之一.介绍了声传感器节点的组成,对路由协议的网络环境做出了假设,提出了路由协议的架构和机制.     

基于阶梯式拓扑结构的WSN半动态路由算法

针对全动态路由算法随着网络规模的增大其拓扑管理能耗剧增的不足,提出一种半动态路由算法.该算法创建了以簇为基本单元的阶梯式网络拓扑模型,根据无线信道传输模型确定簇的覆盖并建立簇到基站的多跳梯度场,在梯度场中采用有序、定向的数据传送方式,实现信息以链路最短的距离向基站汇聚,并在簇内创建了一套簇头轮转机制,以实现簇内能耗平衡.对该算法能耗的定量分析和具体场景的仿真结果表明,该算法大大减少了拓扑管理和数据传送过程中的通信能耗,尤其是随着网络规模的增大,与LEACH算法相比具有明显的节能效果.     

离散萤火虫算法在车载网的应用

车载自组织网(Vehicular ad hoc network,VANET)是移动自组织网络之一,具有节点变动迅速、拓扑结构灵活、通信能力要求较高的特点。为提高车载自组织网络的可靠性,实现数据的安全共享和快速交互,将离散萤火虫(DFA)算法应用求解车载网络中具有服务质量约束的多播路由问题。根据VANET的路由特点,将该问题转化为延迟成本最小化约束优化问题,并将车载网络路径时延转化为萤火虫的荧光素值,然后将该算法用4个实例进行测试,并与Dijkstra最短路径算法、粒子群优化算法进行比较。研究结果表明:离散萤火虫算法性能更佳,可有效解决VANET中Steiner minimum tree(SMT)问题,成功取得最优路径。该算法在一定程度上稳定了网络拓扑结构,能够实时更新节点信息。