最宽不相交多路径均衡路由算法的改进及其分析

针对最宽不相交路径(WDP)算法计算每个可行路径工作量大而且非常耗时——计算n条路径需要耗费O(n3)次迭代的问题,为了减少算法的复杂度和缩短计算候选路径的时间,提出了一种通过减少可行路径集的数量和限制计算迭代次数的改进算法,该算法使用具有可用带宽的可行路径集的子集代替所有可行路径来计算候选路径。性能分析表明:改进后的算法和最初的WDP算法相比具有较快的收敛速度和较低的计算复杂度,对于给定的通信流量能够提升网络性能。     

基于MANET接入Internet的负载均衡机制及其算法

在MANET接入Internet的网络环境中,由于移动节点集中使用某些位置上的网关来实现接入,造成这些网关的负载增加,性能下降.为了能够均衡利用网关及各移动节点,提出了一种新的利用动态网关和多径技术实现MANET接入Internet负载均衡的路由机制.该机制使用多路径进行传输,并在多个候选路径之间按一定的比例均衡分配通信流量;同时,在选择网关时尽量选择低负载的网关,均衡网关的负载.仿真分析结果表明:该算法能有效降低分组的平均传输延迟并提高网络的吞吐率.     

星座网络关键链路代价增量路由算法

全球通信业务量大且分布不均衡的客观因素,使得卫星网络资源利用率较低的问题日趋严重。为了解决这个问题,提出了一种面向星座网络的关键链路路由算法。该算法在业务统计模型下,以传播时延和当前链路负载状态为链路代价选出候选路径。在此基础上引入关键链路的概念并建立关键链路代价增量预测模型,最终从候选路径中选择代价增量最小的为最优路由。算法还采用拥塞控制策略发现拥塞,减轻拥塞链路的负载,选择重新设计部分业务的路由。实验结果表明,算法在平均路径阻塞概率、吞吐率、路径时延以及负载均衡方面均有较好的提升;在满足时延要求的前提下,能够有效地分配网络资源,提高网络利用率,是一种较好的卫星网络路由算法。     

基于离散粒子群的SDN动态流调度算法

针对数据中心网络中流量路径分配不合理、易导致大流冲突的问题,提出一种基于离散粒子群的软件定义网络(SDN)流量调度算法.该算法重定义粒子群内部的寻解过程,以最优化网络性能为目标,动态地为数据中心的流量分配最优路径,以减少大流量冲突;并引入Metropolis设计多元化最优调度方案,确保数据中心流量的合理调度.与其他流量调度算法进行对比验证的实验结果表明,该算法提升了网络质量,降低了大流时延,实现了更好的负载均衡.     

改进的Logit随机路径选择模型及其算法实现

在交通分配问题中，路径出行成本是与流量相关的函数，使用Logit随机路径选择模型进行配流计算会带来一定的误差，而随机均衡配流模型及算法都比较复杂，模型的应用受到一定的限制。因此对Logit随机路径选择模型进行了改进，并用逐次分配算法成功实现求解，还对求解结果进行了对比分析。改进后的模型同原模型相比，简单直观、假设合理、易于求解，同时考虑了出行成本与流量的关系，对于交通拥挤的配流问题同样适用，因而具有广泛的应用前景。     

DHT的分层结构多出口选择问题研究

为了提高系统可靠性和查询效率,提出了具有多管理节点(出口节点)的DHT分层模型,并给出了3种查询算法:最短路径选择算法、基于热土豆模型的最小化组内流量算法和出口节点负载均衡选择算法。通过仿真实验对3种算法在查询效率、流量分析和负载均衡3个维度进行了分析比较,基于热土豆模型的最小化组内流量算法具有最高的查询效率,但是负载均衡性能最差,出口节点负载均衡选择算法具有最好的负载平衡性,但查询效率最低,最短路径算法性能则介于上述两种算法之间。同时对传统分层结构所采用的随机查询算法与基于热土豆模型的最小化组内流量和最短路径查询算法进行了性能对比。     

基于流量工程的网络改进算法

针对计算机网络规模滞后、服务类型单一和服务质量没有保证等问题,将网络规划(网络改进)与流量工程作为有机整体为网络业务流量提供QoS服务,并在此基础上提出基于流量工程的新型网络改进算法.算法运用构造Harafy图和网络扩充启发式算法保证拓扑约束,基于多QoS约束路由算法满足流量工程约束;并使用改进遗传算法策略全局寻求改进费用最小网终及容量分配.仿真结果表明:算法实现最小化新增链路,使改进后拓扑仅略大于理想拓扑(Harary拓扑),88%的流量通过少跳数传输,且各链路带宽分配均匀(均方差σ=1.1).从而使算法在满足各网络约束的同时能够有效地均衡网络负载,避免链路拥塞,提高网络运行性能.     

基于可替换路径对的多用户均衡交通分配算法

针对多用户均衡交通分配问题，依据多用户均衡条件，给出了该问题的变分不等式模型和间隙函数。利用可替换路径对的概念，设计了基于可替换路径对的多用户均衡交通分配算法。在大规模交通网络上，对比分析了提出的交通分配算法、外梯度算法、基于用户的对角化算法和基于起点的对角化算法等的性能。数值结果表明，提出的基于可替换路径对的交通分配算法在求解精度、算法效率以及稳定性等方面都显著优于其他算法。     

非对称网络容量约束用户均衡交通分配仿真算法

针对非对称网络路段容量约束交通均衡分配模型计算困难,设计了一种带路段容量约束的用户均衡交通分配仿真算法。在算法迭代过程中,将按全有全无法在当前最短路上分配流量与前一轮迭代所得到的流量加权组合,各O-D对的组合系数依Logit模型来确定;并不断自适应调节路段排队延误因子和误差因子来模拟实际路段行驶时间,使路段流量逐步低于路段容量,从而达到广义用户均衡,克服了容量约束均衡分配计算量大及Logit随机分配法要求枚举所有路径的困难。随后证明了算法的收敛性,并对一个小型路网进行了数值试验。     

交通分配起点算法的实证研究

以交通网络为对象,研究求解均衡网络模型的起点算法原理及其实际应用.起点算法是一种基于路径树的交通网络流量分配方法,它按照交通分布起点把交通分配问题分解成若干个子过程.若干个子过程在网络空间的叠加,形成交通网络流量.在每个子过程中,在具有同一起点的若干起终点对之间,所有路径满足Wardrop原则.在比较不同收敛标准的基础上,提出最大-最小路径费用差作为起点算法的收敛准则.选用国内外不同规模的5个城市交通网络数据,对起点算法进行测试,结果表明,起点算法具有很好的稳定性,能够满足任何给定的精度要求.采用最大-最小路径费用差作为起点算法的收敛标准,能够真实反映起点算法的卓越性能,精确表现交通网络均衡原则.     

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

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

A Routing Algorithm for Risk.Scanning Agents Using Ant Colony Algorithm in P2P Network

This paper describes a routing algorithm for risk scanning agents using ant colony algorithm in P2P（peerto peer） network. Every peer in the P2P network is capable of updating its routing table in a real-time way, which enables agents to dynamically and automatically select, according to current traffic condition of the network, the global optimal traversal path. An adjusting mechanism is given to adjust the routing table when peers join or leave. By means of exchanging pheromone intensity of part of paths, the algorithm provides agents with more choices as to which one to move and avoids prematurely reaching local optimal path. And parameters of the algorithm are determined by lots of simulation testing. And we also compare with other routing algorithms in unstructured P2P network in the end.     

一种基于遗传算法的组播路由选择方法

提出了一种基于遗传算法的组播路由选择方法·该方法首先寻找所有满足时延限制条件的路径,组成备选路径集,然后以代价最小为优化准则,在备选路径集中采用遗传算法求解最优解·为保证算法的收敛速度快,遗传算法的交叉操作使用了相同链路保留的方法·最后,进行了仿真实验,并与其他算法做了比较·实验表明,该算法收敛速度快,可靠性高,能够满足多媒体网络对实时性的要求·尤其是在网络规模较大时,本算法可大大减小路由计算时间·     

基于延时状态统计的分布式QoS路由算法

为了克服网络状态的不准确性给服务质量(QoS)路由机制带来的负面影响,针对延时约束最小代价(DCLC)路由问题,提出了一种基于延时状态统计的分布式路由算法(DSS-DRA)。根据延时状态的稳定性程度预测路径状态的不准确性,并结合概率选路,为到来业务探测寻找满足其QoS要求的DCLC路径。仿真及其分析表明,DSS-DRA能够较好地容忍不准确的网络状态信息,在路由性能以及DCLC问题的解决能力方面具有较为明显的优势,同时与泛洪探测等方法相比,可以较好地减小探测开销,而与最小延时等算法相比,当网络重载时,能够以略微增加的开销为代价换取较大的性能改进。     

基于延时状态统计的分布式QoS路由算法

为了克服网络状态的不准确性给服务质量(QoS)路由机制带来的负面影响,针对延时约束最小代价(DCLC)路由问题,提出一种基于延时状态统计的分布式路由算法(DSS-DRA)。根据延时状态的稳定性程度预测路径状态的不准确性,并结合概率选路,为到来业务探测寻找满足其QoS要求的DCLC路径。仿真及其分析表明:DSS-DRA能够较好地容忍不准确的网络状态信息,在路由性能以及DCLC问题的解决能力方面具有较为明显的优势;同时,与泛洪探测等方法相比,可以较好地减小探测开销,而与最小延时等算法相比,当网络重载时,能够以略微增加的开销为代价换取较大的性能改进。     

基于QoS的网络路由模拟器设计与实现

基于网络连接流参数和链路信息,QoS路由算法能够选择合适传输路径以满足应用性能的要求和优化网络资源,仅驻通过数学方法测试路由算法性能是不够的,而且在算法设计过程中,许多参数都需要通过模拟实验获得,本介绍了基于QoS网络路由模拟器的设计与实现方法,该模拟器可以测试不同路由算法性能,并可提供不同路由算法性能参数的比较。     

关于实际构造最大带宽路径算法的研究

以往的研究中 ,已经提出了利用修改Dijkstra算法或修改Bellman -Ford算法来构建最大带宽路径 .本文证明可以使用修改的Kruskal算法来构建最大带宽路径 ,并且演示了该算法比前面提出的算法更为简单、灵活、快速且易于实现 .     

容迟容断网络中基于拓扑的双时隙路由算法

在公交车载网络等类型的容迟容断网络中,可以依靠全部或者部分网络拓扑信息进行路由计算.提出一种基于拓扑信息的双时隙路由算法.该算法将网络周期离散为时隙,计算路由时,采用当前时隙和下一时隙(即双时隙)内均有效的路径作为候选路径,从而保证多数业务在链路失效前完成转发.以传输延时和延时抖动率为依据,从当前和下一时隙内均有效的路径中优选路径,以容忍可预测的链路中断;通过提供备用路径,以容忍不可预测的链路中断,保证传输的可靠性和稳定性.对上述算法进行了仿真实现和性能分析,结果表明,该算法能容忍链路中断,报文递交率较高,平均传输延时较低.     

无线网状网中多并发流路由结合调度的组合方案

为解决无线网状网中多条路径同时传送引起的干扰冲突和资源竞争问题,提出了依托信道分层方法的组合式路由结合调度的方案:首先,给出了路径发现的可行方案,并基于网状网的可用资源提出一种路径选择判据——资源可获得度;然后,确定了多条路径可并发传输的信道分配方案;最后,开发了结合路由、信道分配、调度的组合优化调度方案(COSS算法),以启发式的方法找到每个时隙下尽可能多的可兼容路径,实现可兼容路径的组合优化调度.为验证COSS算法的性能,在不同网络资源配置、多种流量请求下进行仿真实验.实验结果表明:(1)COSS算法在吞吐量、传输延迟、传输完成时间方面有较好的表现;(2)与AODV路由协议相比,COSS算法有效地提高了吞吐量.     

一种带路径约束的多商品流网络设计问题及其禁忌算法

多商品流网络设计问题在实际中有很广阔的应用背景,然而在多商品流模型中,有些实际应用问题对运送商品的路径提出了额外要求,如时间、可行性等．在此,将考虑一种带路径约束的多商品流网络设计问题,并借助改进单纯形法、列生成和最短路径算法为提出的模型构造一种禁忌(tabu search)算法,最后给出该算法的计算实验结果．