论文部分内容阅读
随着网络应用和探索的日益多样化,网络正被迫满足各种流量需求,并具有明确且关键的服务质量(Quality of Service,QoS)要求。QoS是网络通信的前提,而服务质量路由是保障QoS的重要部分之一,其在很大程度上直接影响着网络的性能。服务质量路由问题作为一种典型的多约束路由问题,主要是在多约束条件下找出源节点和目的节点之间的一条最优路径,该问题的解决需要依靠一种切实可行的路由算法来支持。本文根据现有多约束路由算法中的传统路由算法和基于蚁群算法的路由算法现状,提出了两种新的路由算法DAG_DMCOP和DAG_IACS。针对现有传统路由算法存在时间复杂度高、成功率低等缺点,借鉴有向无环图(Directed Acyclic Graph,DAG)思想和指标赋权法理论,提出了一种新的基于DAG和Dijkstra的多约束优化路由算法DAG_DMCOP。该算法分两部分:(1)剪枝策略。求出源节点到其余节点的满足多约束要求的全部路径,将网络拓扑图简化为DAG图。(2)搜索策略。引入链路综合代价函数,使用指标赋权法中的G1法和标准离差法以及拓扑图中的邻居节点集对多约束条件(带宽、时延、时延抖动、费用等QoS度量参数)进行自适应权重调整,然后利用Dijkstra算法在剪枝之后的DAG图上寻找满足多约束要求的最优路径。大量实验数据表明该算法能快速找到满足多约束要求的最优路径,有着较低的时间复杂度和较高的成功率。该算法简单易扩展,适用于较大规模的多约束路由网络,是一种解决多约束路由问题的高效的新算法。在上述算法的基础上,对DAG_DMCOP算法中的搜索策略使用蚁群系统(Ant Colony System,ACS)进行研究。针对基于蚁群算法的路由算法以及ACS算法存在的收敛速度慢、易陷入局部最优等问题,对ACS算法进行改进:将不可到达目的节点的中间节点的相连链路全部剪枝,避免蚂蚁对无效链路再次访问,缩小全局搜索范围;利用全局最优路径、迭代最优路径以及迭代最差路径三者之间的关系动态调整全局信息素更新规则,加快算法的收敛速度;给网络拓扑图中的每条链路增加一个代表蚂蚁访问链路状况的参数,并使用该参数以及多种选择策略共同对状态转移规则进行调整,扩大局部搜索范围,改善局部最优问题。将DAG_DMCOP算法的剪枝策略和改进ACS算法进行融合,提出了一种基于DAG和改进ACS的多约束优化路由算法DAG_IACS。大量实验数据表明该算法能够缩小全局搜索范围同时扩大局部搜索范围,有着较好地收敛速度和寻优能力,并且成功率也更高一些。另外,该算法对网络规模以及约束条件也有一定的扩展性。