QoS约束下的链路分离路径问题研究

研究了QoS约束下的链路分离路径问题,建立了2种QoS约束下的链路分离优化路径问题的模型。首先证明无向图的不具备端到端QoS约束的链路分离路径问题可以转化为其链路分裂图的对应问题,而具备端到端QoS约束的相应问题则无法进行类似转换。同时证明2种QoS约束下的链路分离优化路径问题都属于NP完全问题,最后对其近似算法进行研究并对算法进行比较测试。

多加性QoS约束下的链路分离路由算法

对多个加性QoS约束下的链路分离路径问题进行了研究,针对现有算法求解结果依赖于网络结构,难以保证对任意网络都可求得可行解和最优解的问题,提出了一种与网络结构无关的多约束链路分离路径路由算法(MCLPRA,multiple constrained link-disjoint path routing algorithm)。该算法基于SAMCRA,采用对解空间先分类,然后按类进行处理和搜索的方法,引入了控制搜索深度的参数,可保证对任意网络都能求得可行解。理论分析表明,MCLPRA能够在现有算法不能求解的情况下解得可行解和最优解。仿真结果显示,MCLPRA的可行解平均求解成功率明显高于现有算法且所求路径对长度也比现有算法更短。

多约束最短链路分离路径精确算法

在通信的源和目的间寻找两条(主用和备用)链路分离的QoS路径是提供可靠QoS路由的重要途径.现有求解多约束链路分离路径对(multi-constrained link-disjoint path pair,简称MCLPP)的算法难以保证求得存在于任意网络中的可行解和最优解.为解决这一问题,分析了MCLPP问题最优解的性质,提出了精确算法的设计原则,在此基础上给出了求解MCLPP问题的精确算法(link-disjoint optimal multi-constrained paths algorithm,简称LIDOMPA算法),可对任意网络求解客观存在的多约束最短链路分离路径对.为了降低算法的复杂性,引入了候选最优解、紧缩的约束向量和结构化的路径支配3种关键方法,在保障算法精确性的同时,有效地降低了LIDOMPA的搜索空间.大量的实验结果表明,LIDOMPA的求解能力优于现有算法,同时可以实现较低的算法执行时间开销.

SDN架构下的链路分离路径算法的研究

软件定义网络(SDN)是一种新型网络架构。在SDN架构中控制层能够从数据层获得网络的吞吐量、连通性和流量的全局视图,并且能够细粒度地对流量进行控制。链路分离多路径算法在生存网络、QoS感知通信网络和SDN控制网络中有很重要的研究价值。针对SDN环境下网络的可靠性和负载均衡优化问题,改进Dijkstra算法并且与分离路径算法相结合,实现SDN下对流量的灵活控制。在SDN环境下对链路分离路径算法进行仿真验证,证明路径分离算法的有效性。实验结果表明,算法既均衡了路径之间的负载,又提高了网络的可靠性。

Ad Hoc网络基于路由协议的拥塞控制

AdHoc网络随着网络负荷的增加,局部的拥塞是导致网络性能大幅下降。采用修改的AODV路由协议,结合链路层的分析,提出了一种节点负载分流的方法。该方法结合了AdHoc网络的特点,采用网络层和链路层相互协作,均衡网络流量,提高了网络的整体性能。仿真结果表明,该改进在不同拓扑变化频率和不同节点密度情况下均明显提高了网络吞吐率,改善了网络拥塞。

无线Mesh网络链路非相关多径发现算法

非相关路径的使用对于提高网络性能有极其重要的作用,但当前无线Mesh网络的路由协议都不支持链路非相关多径的寻找.在分析DSR协议不足的基础上,提出了一种基于DSR改进的链路非相关多径寻找算法EDSR(enhancedDSR).其核心思想是在DSR路由寻找完成后,利用网络节点的路由缓存发现和寻找源节点与目的节点间的链路非相关路径.通过非相关路径的使用,提高网络吞吐率,从而达到提高网络性能的目的.仿真结果表明,EDSR算法能以较少的代价获取非相关路径,提高网络性能.

一种改进的链路独立的MANET网络路由协议

MANET网络具有高速移动以及频繁的链路失败等特点,这将导致吞吐率降低以及很高的端到端时延.为减少由于此类原因的路由发现次数以及开销,我们使用多径路由来提供备选路径.论文提出一种基于AOMDV的改进链路独立多径路由协议.通过仿真表明改进后的LD-AOMDV在节点移动速度较高时数据包投递率、端到端平均时延、归一化路由开销等方面都明显优于AOMDV.

WIA-PA中基于DSDV的多路径路由协议研究

应用于工业的无线网络有着强实时性和高可靠性的要求,路由协议是WIA-PA网络的关键技术。基于DSDV的多路径路由协议,它采用了基于链路稳定性的路由选择标准和节点不相交路径策略,选择一条最高稳定性的路由传输数据,确定次稳定性、不相交路径作为备份路由。与DSDV相比,多路径算法在网络的稳定性和数据传输的性能上有了显著的提高。

多约束最短链路不相交路径的启发式算法

为求解多约束最短链路不相交路径(MCSDP(k))问题,提出了一种启发式的整数规划方法:FHABIP,并给出了算法搜索方案。根据问题的整数线性约束集合具有的结构特点,利用拉格朗日乘子把整数线性约束集合中的复杂约束引入到目标函数中,导出具有约束系数矩阵是全幺模矩阵特点的整数线性规划问题,从而使这类问题能用单纯形法容易求解。MCSDP(k)在求解线性规划问题的迭代过程中很容易地被求出。算法实验结果表明该算法快速有效。

一种基于生存时间的Ad hoc网络不相交多路径路由算法

针对无线移动Ad hoc网络的节点具有移动性和能量限制等问题,提出了一种根据网络动态拓扑结构和节点能量来进行多路由选择的混合式路由算法PEMP-OLSR。该算法以改进的链路状态路由算法为基础,通过在网络拓扑构造过程中引入链路和节点生存时间等参数来提高所选路径的稳定性,同时通过设定影响链路和节点权重的迭代因子来提高多条路径的不相交性,以提高此并行多路径算法的传输效率。通过大量仿真实验结果表明,该算法能有效地提高所选择的多条路径的稳定性和不相交性。

WDM网络中的光层组播保护

组播应用主要是一些带宽密集型的业务,而光网络又能够提供巨大的带宽。随着光通信技术的发展,在光层实现组播已经成为光网络研究的热点之一。主要讨论了在光层实现对组播业务的保护,对现有的保护方案进行了分类和比较研究,最后讨论了有待进一步研究的问题。

机动突击中的自组网多路径路由技术

随着作战样式的变化和武器装备的变革,装甲车辆机动突击作战中协同控制的重要性不断增强,对网络通信的各项性能指标提出了更高要求,而自组织网络所具备的一些优良特性能够较好地适应这一需求。在网络通信中,稳定性是衡量网络路由性能的重要因素。机动突击作战中,车辆移动、障碍物阻挡等因素将导致网络拓扑变化迅速,给路由稳定性带来严重影响,极大地降低了网络通信质量。基于AODV协议,设计并仿真了一种链路不相交的多路径被动式路由协议,以路由回复消息中携带的路由信息为基础,实现两条不相交链路作为通信路由并互为备份。仿真结果表明,该协议在数据包到达率及平均时延方面较AODV协议均有一定提高。

一类带有纽结分支的边—不交链图

为进一步探讨边—不交链图的分类,研究其中至少有一个链的分支是非平凡纽结的情形,给出了带有纽结分支的边—不交链图的定义。在给出内在纽结图H0的基础上,利用其与边组成的图形成完全图K7,并采用该方法构造出一类带有纽结分支的边—不交链图H(43)。分析点扩张对H(43)的作用,得到了点扩张的图变换不保持带有纽结分支的边—不交链图的性质这一结论。

能量感知的无线传感器网络多路径路由研究

针对现有多路径路由协议AOMDV的不足,提出了适用于无线传感器网络的能量感知多路径路由协议IMEA。IMEA在建立链路不相关的多路径时能优先建立节点不相关的多路径,在主路径失效时能优先选择与主路径共用节点最少的作为次优路径,而能量感知的路径选择策略能均衡网络中节点的能量消耗,实现数据传输路径的低能耗。对IMEA进行了仿真实验,结果表明IMEA有效延长了网络的生存时间。

网状WDM网中支持区分可靠性的共享通路保护算法

光纤链路由于共享了某些物理资源(如光缆、管道、通路等),因此存在一定的故障相关性,术语“共享风险链路组(SRLG)”就是用于描述链路之间的这种风险共享关系的。SRLG分离成为保护设计的重要约束。该文研究了支持区分可靠性的SRLG分离共享通路保护设计问题。结合SRLG条件故障概率的概念,提出了部分SRLG分离的共享保护算法PSD-SPP(PartialSRLG-DisjointShared-PathProtection),有效地解决了SRLG分离约束下的区分可靠性设计问题。仿真结果表明该算法既满足了用户的区分可靠要求,又能有效利用资源。

智力玩具九连环研究

经考证指出中国智力玩具九连环在先秦时代已经发明;探讨九连环的结构、操作特点、源流、上下环充分必要条件及其计数函数;介绍西方数学家Cardan G(1501-1576),Wallis J(1616-1703)和Lucas F EA(1842-1891)所取得的相关成果.

无线Mesh网络多路径路由协议的研究

L2MPM路由协议工作在第2层,属于多经路由中的备份路由,但并未考虑主路经与备份路径之间存在链路相交的问题,降低了网络的容错能力。因此,在L2MPM协议的基础上,提出了LD-L2MPM路由协议。该协议通过采用链路不相交策略,在Hello包中添加第一跳和最后一跳字段来确保所选的两条路径是链路不相交。仿真结果表明,与原有协议相比,数据包投递率提高约6%,平均端到端时延降低约5%。

基于服务质量的链路不相交路由算法

针对网络可靠性问题,提出了一种基于链路保护机制的QoS路由算法,该算法首先在图论的基础上得到任意两点间的所有路由,再过滤链路条件使其满足QoS约束,由此求出结点对间的两条链路不相交的最短相似路由,对大数据流复用及高实时性网络都起到较好的优化作用.

节点约束型链路分离算法

针对节点约束型链路分离问题中的两条链路需经过各自必经点集的特点,提出一种以遗传算法和迪杰斯特拉算法为基础的节点约束型链路分离算法。通过改进的遗传算法得到较优的必经点序列,利用带有禁忌搜索的迪杰斯特拉最短距离算法求必经点对之间的无环最短路径,采用禁忌边的方式保证路径间重边最少。得到起点到终点之间的两条受必经点约束的路径,路径内无环路、路径间重边最少。大量模拟仿真实验结果表明了该算法的有效性和可行性。

链路分离路径算法研究

传统的QoS路由算法只在源节点和目的节点之间提供一条QoS路径,这一做法已不能满足在网络连接出现故障时保持业务持续不间断地进行这一要求。分离路径算法试图在源节点和目的节点之间寻找满足一定QoS约束的分离路径(链路分离或节点分离),一条主用路径,另一条备用路径。当主用路径出现故障时,将其承载的业务流转换到备用路径上,从而实现快速的业务恢复。因此,分离路径算法研究有很重要的实用价值。