计算最短路径树Dijkstra算法的改进

针对用于网络寻径表刷新的OSPF路由选择协议中使用的计算最短路径树的Dijkstra算法在网络应用中的不足，提出了一种改进算法，用以计算边和节点上都有代价的图的最短路径树，以更全面刻画网络状态，找到更合理的最短路径树，通过对同一个网络自治系统最短路径树的计算，比较了改进Dijkstra算法和Dijkstra算法的差别，结果表明改进Dijkstra算法能够更加全面地刻画网络状态，找出的最短路径树更为合理。     

计算机网络路由算法的理论与进展

为了解大型网络的路由算法的理论基础和研究动向,分析计算机网络模型和网络拓扑的特点,得出运筹学中的图论、排队论和动态规划理论是路由计算的基础。图论中最短路径树的理论是路由算法的重要理论。排队论中的M/M/1/K和M/M/m排队是比较接近网络实际的延迟计算模型。按照动态规划思想进行路由计算的方法,比枚举算法计算量小且能够获得最佳路径。静态路由算法是动态路由算法的基础,为了提高动态路由算法的实用性,网络动态信息检测技术和新网络模型研究将是今后一个时期的研究热点问题。     

适用于WDM全光网的自适应路由与波长分配算法

对波分复用(WDM)全光网中的动态路由与波长分配问题进行了深入的研究,并提出了最小通道权重优先（MPWF）自适应路由与波长分配算法. MPWF设计了新的链路权重计算方法,通过整理当前链路状态和通道长度信息为业务计算路由. MPWF算法的设计既适用于波长变换网络,也适用于波长选择网络. 仿真结果显示,与一些文献中提出的自适应路由与波长分配算法相比,MPWF算法可提高网络资源的利用效率,降低业务的阻塞概率.     

一种网络编码的多播路由算法

提出一种基于网络编码的新多播路由算法,该算法借助Dijkstra约简网络搜索源节点到各接收节点的路径族,并在搜索过程中考虑不同路径族之间链路的共享,以降低带宽资源消耗,改善链路负载均衡,提高了网络性能．仿真验证了算法的有效性,而且其性能逼近基于网络编码的最小费用多播算法．最后,数学分析表明该算法节约了40％左右的计算量．     

运用HTC解决延迟容忍网络路由问题

针对传统最短路径算法不适用于延迟容忍网络(DTN)路由选择以及DTN路由选择的特性,提出了一种基于跳数、权值随时间变化(HTC)的最短路径算法. 该算法的设计不仅考虑到节点间空间因素,还考虑了无线链路的时间因素和该算法的复杂度与正确性. 仿真结果表明,与现有的最早接触(FC)路由算法以及最小预期时延（MED）路由算法相比,此算法可更有效地得到DTN中时延最短的路径.     

偏转路由的网络故障处理技术

提出了一种新的偏转路由方案，以解决现有偏转路由方案不能处理节点故障以及存在路由环路的问题。在分析网络故障对最短路径树结构影响的基础上，通过采用新型计算备份最短路径树的算法以及相应的重路由策略，实现对链路和节点故障的快速处理，同时保证备份路由不存在路由环路。实验结果表明，本方案提供的预备路由接近重新计算得到的最佳路由，因此具有较好的性能。     

卫星网络最短路径路由机制的仿真分析与评估

卫星网络中特殊的通信环境和特性为高效路由算法的设计带来了挑战,针对其中最优的最短路径路由机制的选择问题,提出了基于专家判断法的路由机制评估模型,包括指标体系的选择、权重设定、归一化等步骤.以距离矢量、链路状态和混合机制这3种机制在GEO网络中的性能比较为例,使用OPNET展开仿真实验获取路由指标,实验结果显示距离矢量机制更适合于网络拓扑结构较简单的场合,而链路状态机制则更适合于网络规模较大、拓扑结构复杂的场合.混合机制的整体性能最佳,但需要占用大量网络资源,所以适用于相对稳定的卫星网络.     

基于时延和能耗的Ad hoc网络路由选择算法

为了减少网络能量消耗,优化网络性能,在网络节点MAC层发射功率可控条件下,提出了一种基于平均分组时延与分组能量消耗乘积最小的路由路径选择算法.该算法根据链路平均分组时延和分组能量消耗情况来进行路由路径选择.仿真表明,该算法可以动态调整网络路由路径,使所选路径的平均分组时延与分组能量消耗乘积达到最小,从而达到减少网络能量消耗及降低网络分组时延目的.     

基于SDN的一体化融合网络路由调度机制

为了解决一体化融合网络动态接入设备出现的通信波动、流量负载均衡以及鲁棒性差等问题,结合软件定义网络（SDN）技术, 优化了基于主客观的精准成本模型,将指标阈值型G1法作为主观赋权法,将标准离差法作为客观赋权法,使用乘法集成法对主观法和客观法计算出的权值进行成本整合,给出了最终的链路成本。提出了一体化融合网络多路径选择算法,把优化后的成本组合运用到多路径迪杰斯特拉（Dijkstra）变种算法中,得到传输链路及组合成本。提出了一体化融合网络联邦路由拓扑和策略,使不同网络可以选择符合自身特征的多条路径并按比例转发。研究结果表明,所提方案优化了差异化路径选择和流量调度,增加了链路带宽利用率并减小了网络传输时延。     

基于带宽和延时度量的QOSPF改进路由算法

针对开放最短路径优先(OSPF)服务质量(QoS)扩展(QOSPF)算法中预剪枝高延时链路后仅考虑带宽度量计算路由,提出考虑带宽和延时度量的QOSPF改进(BD QOSPF)路由算法,为应用流寻找满足其QoS请求(带宽约束、延时最小或延时约束)的可行路径. 该算法保持QOSPF的算法复杂度,并支持逐跳和显式路由,比较可用带宽和延时度量预计算路由表,处理等资源、等开销路径和重路由阻塞流. 仿真结果表明,BD QOSPF可提高QoS流路由成功率,降低流路径延时和节省带宽资源;其重路由策略对于改善流阻塞性能是有效的,但要付出随流负荷增长的重路由开销.     

一种非对称OBS网络中的路由算法

针对现有光突发交换网络采用一步预约协议，在非对称网络中．容易造成链路负载的不均衡，加大突发阻塞概率，提出了一种基于概率的路由算法，根据网络拓扑和结点对间的业务量强度。为每一个源宿对在各个链路上指定权值，结点将根据权值按概率为到达的突发选择输出链路．用一个非线性规划模型描述链路的权值设置问题．与现有路由算法相比．该算法可有效地减小突发阻塞概率．     

一种新的动态QoS多播路由启发式算法

为了满足多播业务的实时性要求、提高网络资源利用率，提出一种新的时延受限动态多播路由算法。该算法充分考虑路径时延对多播树总代价的影响，利用前k条最短路径方法和路径选择函数来生成多播树。算法可以在满足时延约束的情况下，快速地找到性能较好的多播树，同时可以根据网络节点的加入或退出请求来更新多播树，实现对多播树的动态维护。实验结果表明，该算法代价性能良好、能够满足多媒体网络的实时性要求。     

一种新的动态QoS多播路由启发式算法

为了满足多播业务的实时性要求、提高网络资源利用率，提出一种新的时延受限动态多播路由算法。该算法充分考虑路径时延对多播树总代价的影响，利用前k条最短路径方法和路径选择函数来生成多播树。算法可以在满足时延约束的情况下，快速地找到性能较好的多播树，同时可以根据网络节点的加入或退出请求来更新多播树，实现对多播树的动态维护。实验结果表明，该算法代价性能良好、能够满足多媒体网络的实时性要求。     

用遗传算法求解网络最短路效率

为提高求解大型网络最短路问题(SP)的效率,采用遗传算法求解。应用可变长编码提高算法运行效率,通过构造杂交、变异算子,以其提供的一种全局搜索能力来提高解的质量及加快种群收敛速度,从而提高运算效率。因杂交及变异而产生的不可行解,则通过一个简单的修复函数,将其修复为可行解,并使它们加入遗传运算且保持种群的多样性,使遗传算法能更高效的运行。通过对大型网络最短路问题的数值实验,在同一网络中,遗传算法的运行时间明显少于Dijkstra算法,求解效率优于Dijkstra算法。     

Adaptive Agent Model with Hybrid Routing Selection Strategy for Improving the Road-Network Congestion Problem

This paper proposes an adaptive agent model with a hybrid routing selection strategy for studying the road-network congestion problem. We focus on improving those severely congested links. Firstly, a multi-agent system is built, where each agent stands for a vehicle, and it makes its routing selection by considering the shortest path and the minimum congested degree of the target link simultaneously. The agent-based model captures the nonlinear feedback between vehicle routing behaviors and road-network congestion status. Secondly, a hybrid routing selection strategy is provided, which guides the vehicle routes adapting to the real-time road-network congestion status. On this basis, we execute simulation experiments and compare the simulation results of network congestion distribution, by Floyd agent with shortest path strategy and our proposed adaptive agent with hybrid strategy. The simulation results show that our proposed model has reduced the congestion degree of those seriously congested links of road-network. Finally, we execute our model on a real road map. The results finds that those seriously congested roads have some common features such as located at the road junction or near the unique road connecting two areas. And, the results also show an effectiveness of our model on reduction of those seriously congested links in this actual road network. Such a bottom-up congestion control approach with a hybrid congestion optimization perspective will have its significance for actual traffic congestion control.     

一种新的通信网络动态路由算法

针对通信网络中的路由问题,提出了一种虚令牌动态路由算法,并用Ｈｏｐｆｉｅｄｌ神经网络实现该算法。该Ｈｏｐｆｉｅｌｄ神经网络,其神经元之间的连接强度固定不变,通信网络的物理逻路值和呼叫请求被反映到神经元的偏置电流中,地用硬件实现。同时,当通信网络中的业务量发生变化时,算法能够自动调整最短路径与负载均衡之间的关系,计算机仿真结果表明,该算法能接入更多的网络连接。     

认知视角下能量感知的ZigBee网络树型路由优化算法

为解决ZigBee Cluster-Tree路由算法路径选择不优的问题,提出了一种能量感知的ZigBee树型路由EZTR(Energy-Aware ZigBee tree routing)算法.该算法利用每个节点感知的地址信息,按照ZigBee网络树型结构计算下一跳邻居节点到目的节点之间的跳数可避免网络的环路效应,通过引入认知概念,在跳数集合中选出最短路径以降低跳数.在ZigBee网络节点能量的感知过程中,当所选路径存在低能量节点时,及时启用备用节点,从而避免节点因能量过度消耗成为失效节点.NS2(Network simulator version 2)仿真实验表明,EZTR算法可提高网络分组递交率,有效减少节点转发跳数和平均网络延时,减小网络整体能耗,为提高网络的实时性和延长网络生命周期提供理论支持.     

RBLCP：一种覆盖网络的QoS路由改进算法

针对传统IPQoS路由算法不能满足覆盖网络的服务需求的问题，提出了一种通用覆盖网络下的QoS路由算法--资源均衡最小代价路径(RBLCP)算法.该算法从覆盖链路带宽和覆盖服务节点处理能力受限的角度出发，寻找一条既满足QoS要求又保证网络资源均衡的路由.对该算法的QoS满意率、覆盖链路带宽的均衡性以及节点处理能力的均衡性进行了性能仿真.结果表明，与改进的最短路径算法和成比例的带宽最小路径算法相比，RBLCP算法具有更好的QoS满意率，在对网络资源尤其是稀缺资源的均衡方面也有良好的性能.