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))非常接近,说明并行路由算法所能找到的尽可能多的并行路径的能力是接近最优的;并行容错路由算法容错性强,效率高.     

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

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

基于主干树的最小代价组播路由算法

提出基于主干树的最小代价组播路由算法,该算法首先在网络中找出K个代价最小的结点,然后以这K个结点形成一棵树,并称这棵为主干树,然后将不在主干树上的成员结点加入到树上,最后剪去非成员的叶结点。该算法的时间复杂度O(n^3)。该算法所构造的组播树代价略低于MPH算法和KMB算法。     

流量工程中一种权重配置动态路由选择算法

提出了一种MPLS(Multiprotocol Label Switching)网络中新的权重配置动态路由选择算法,该算法以跳数、带宽碎片要求及空闲带宽比率为权重,给到达流量合理分配带宽资源.在MPLS网络边缘实现路径选择后,使用MPLS显示路由技术即可摆脱中间结点路由算法的影响, 建立起满足各种业务QoS(Quality of Service)需求的LSP(Label Switched Path).仿真实验表明,该算法能够更好地进行流量均衡,减小网络拥塞;通过减小带宽碎片和提高带宽利用率更好地利用网络资源;同时通过改善丢包率等参数来实现一定的QoS保证.     

基于路径缓存的并发扩散式服务质量路由算法

服务质量路由算法是一种多约束多目标的优化问题，该问题属于计算复杂度完全类(NP-CompIete)问题．基于一些扩散式服务质量路由算法，提出了一种基于路径缓存的并发扩散式服务质量路由算法(PCB-CFQR)，该算法是一种分布式算法，它将资源预留、接纳控制和路由选择进行有效的结合，能同时完成多个请求的路径建立，大大提高路由算法的效率．分析和仿真结果表明，PCB-CFQR算法具有较强的稳定性和实时性，与最短最宽(WSP)路由算法相比，它无须进行路由信息的定时刷新，却具有较低的呼叫阻塞率．     

超圆环面中一种新的快速路由算法

利用环状网络到超圆环面的两种嵌入，本文给出了超圆环面的一种新的时间为常数步的路由算法．当d≥2，c≥8时，此路由算法得到的超圆环面任意两个结点间的路径长度≤D 1(D为超圆环面的直径)。     

基于蚁群算法的QoS多播路由算法

提出一种基于蚁群算法的分布式动态QoS多播路由的算法.充分考虑路径时延对多播树总代价的影响,多播树中添加符合QoS约束条件的路径,并且从多播组的目的结点出发进行搜索,该路径的路径代价在该次选中的所有迭代路径中最小,以"拉"的模式分布式地构造出多播树。实验结果表明,该算法代价性能良好,能满足多媒体网络的实时性要求.     

Ad Hoc网络多径源路由协议的实现和性能评价

针对AdHoc网络中路由协议问题,介绍了无线AdHoc网络中的一种基于动态源路由(DSR)的新型路由协议———多径源路由(MSR)的基本概念,给出了在Linux(kernel2.4.7)操作系统上完成的MSR协议实现及实现中涉及的几个关键算法.在5个结点组成的MSR实验床上做了几组实验并对实测数据进行分析.得到的性能评价结果表明,MSR协议可以为AdHoc网络结点间通信提供支持,特别是在结点处于快速运动状态下,MSR协议能够改善网络的传输质量.     

一种基于非精确状态信息的QoS单播路由改进算法

传统的QoS保障的单播路由算法都假设IP网络结点的状态信息可以被准确地获知,但实际网络存在许多因素使得状态信息非精确.所设计的改进算法是通过动态确定k优路径算法(k_shortest algorithm)中的k值,从而确保最终求得的路径相对其他算法所求得路径是更优的.因此能有效地降低了丢包率,提高了端到端延迟绑定的概率,通过网络仿真器Ns的仿真分析,结果表明了该算法的有效性.     

基于多目标规划的WSN路径动态选择算法

为解决无线传感器网络中查询的能量有效和实时性之间的矛盾,提出一种基于多目标规划理论的动态路径选择算法(MOPEH).该算法结合了最低能耗路由策略(ME)和最小跳步数路由策略(MH),运用多目标规划模型,将能量代价和传输时延同时作为路由算法的设计目标,利用深度优先搜索策略建立了节点间的所有可行路径集合,并从中选择能耗低于平均能耗的路径.根据查询要求设定网络性能函数,动态调整两项性能指标,从可行路径集合中选择满足要求的路径,得到最优解.实验证明该算法能够能量有效地处理实时查询.     

基于蚁群算法的对等网搜索算法的研究

针对传统的对等网搜索方法的不足,分析了蚁群算法的优势,提出了一种基于蚁群算法的对等网搜索方法．对等网上发起结点收到查询请求后,执行消息路由搜索算法对目标结点进行搜索,在搜索过程中根据状态转移公式寻找下一跳路径．实验结果表明,基于蚁群的对等网搜索算法能够节省路由长度并且有较高的搜索准确率．     

基于遗传算法的WSN谣传路由的改进

谣传算法是一种基于数据查询的无线传感器网络路由机制,它通过事件agent和查询agent形成的路径交叉生成一个路由,该算法存在着路径非最优化问题。为此,提出了一种基于遗传算法的谣传路由协议,它由谣传算法生成多条路径,利用遗传算法对此多条路径进行操作,将能量消耗作为评价指标,生成最优的路径。仿真表明,此算法能有效的降低节点的能量消耗,极大的延长了网络的生存时间。     

一种快速的近似最小代价多播路由算法MCTH

提出一种快速近似最小代价多播种由算法。算法通过动态调整结点与当前躜上树的代价值,依次选择和当前路由树有最小代价的结点来逐步生成总体代价小的多播路由树。Ｍｉｎｉｍｕｍ Ｃｏｓｔ Ｐａｔｈ Ｈｅｕｒｉｓｔｉｃ （ＭＰＨ）是一个性能很好的Ｓｔｅｉｎｅｒ对近似算法,算法分析和实验比较得出,本文的算法与ＭＰＨ有相同的性能,但复杂性更低,并且建立路由时仅需了解相邻结点之间链路的代价信息。     

楼宇三维路径模型的自动生成算法

提出了一种楼宇三维路径的自动生成算法.该算法首先使用图像细化算法及特征点提取算法建立单层楼的通道路径,并将房间等楼层实体作为结点连接到通道路径上,从而建立好单层楼的路径图;然后利用楼梯结点和电梯结点将相邻的楼层路径图相互连接起来,生成完整的楼宇三维路径模型.该路径模型是由弧和结点结构组成的带权图结构,可以应用于智能导航、楼宇自动控制、紧急情况的人员疏散及楼宇安全等领域.     

移动自组织网中MP-QAODV协议的研究与性能评估

为了在移动自组织网络中提高数据包路由的可靠性以及效率,研究了在移动自组织网中一种基于QoS(quality of service)的改进路由协议。该协议基于一种路径长度限制的路径稳定的路由算法,该算法用一种确定性的最优权值约束算法,通过一般化方法,把确定性算法转换成多项式复杂程度的非确定性算法;最后引入QoS的判定因子实例化算法而形成,结合对MP-QAODV(multi path-quality of ad hoc on-demand distance vector routing)路由协议数据包、路由机制的分析与设计,利用NS2设定移动自组织网仿真环境参数,仿真结果表明,该算法是一种能满足QoS需求的路由策略。通过与同类路由协议的比较,该路由协议具有提高现有网络性能的特点,为实时大流量业务提供了有效的通信服务保障。     

多可加性条件下的端点到端点QoS路由算法

基于QoS的路由是QoS中最关键的功能组件之一.从本质上看,QoS路由就是端点到端点的带结点条件和边条件限制的最短路径问题,这种问题是NP完全的.作者研究了可加性条件限制的QoS路由模型和路由算法,分析了可加性条件的性质并得到了其对路由长度限制的定理,为多个可加性条件的QoS路由问题建立了一个一般性的数学模型;最后根据此模型,提出了一种新的启发式求解算法.在算法中,采用限制条件的可加性进行搜索剪枝,从而使新算法在实际应用中更有效;该算法的时间复杂度为o(1gm+n×(1+d1+d2+…+d00)).应用结果表明,由于采用搜索剪枝,该算法在实际应用中具有时间复杂度减小、运行速度加快等特点.     

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

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

无线自组织网络基于洪泛控制的动态路由协议FCDR

针对无线自组织网络现有按需路由协议在路由维护时需要采用全网洪泛广播路由请求消息而导致大量额外开销的缺点,提出了一种无线自组织网络基于洪泛控制的动态路由协议FCDR.FCDR的主要思想是控制洪泛机制的使用范围,减少路由的维护开销,并使失效路由得到快速恢复.文中描述了FCDR协议的实现过程并对路由维护时消息传递的有效性进行了分析.分析表明：通过广播路由请求消息建立路由的情况下,消息传递的有效性将随着源结点和目的结点之间路径长度的增加而急剧下降,相比之下,FCDR具有更好的有效性且其优势随着源结点和目的结点之间路径长度增加而更为显著.     

基于关键结点和遗传操作的最小代价组播算法

提出了基于关键结点的最小代价组播路由算法,算法利用整数规划的思想在网络中找出k个代价最小的结点;通过特定策略将这k个结点构成一棵树,然后采用遗传操作将不在树上的成员结点加入到树上,最后剪去非成员的叶结点形成最小代价组播树.该算法可靠性高,能够有效满足实时应用的需求.