基于Pareto最优的多约束QoS路由算法研究

摘要

近年来，由于IP网络独立于上层应用和下层承载网的通用特性，构建以IP技术为基础的融合网络成为下一代高速宽带网络的基础。同时，日益丰富的各种网络业务对带宽、延迟、延迟抖动和分组丢失率等性能参数有不同需求，因此要求网络能对各种不同业务加以区分，并根据用户要求分配资源提供不同服务质量（QoS）。IP QoS研究框架中的QoS路由问题，特别是基于多个度量约束构建的多约束OoS路由问题，因其可更精确地反映实际路由选择过程成为业界研究热点。多约束QoS路由问题的研究重点在于解决其中的NP完全问题，可通过将其转化为多目标优化问题（MOOP）解决。利用Pareto最优化理论，通过搜索Pareto最优点完成QoS度量空间划分，从而通过路由请求信息判断路径可行性，得出满足多约束条件的可行解。
　　 本文通过分析线性搜索和非线性搜索的几何意义，提出了一种基于Dijkstra算法搜索Pareto最优点的方法，将线性搜索与非线性搜索、预计算与在线计算相结合的QoS路由算法：线性预计算非线性在线计算路由算法（LPNOA算法）。LPNOA算法在线性预计算阶段选取最佳线性搜索方向，在非线性在线计算阶段定义一种新的非线性路径代价函数。本文在仿真平台上实现了LPNOA算法，并分别从算法复杂度、响应速度和路径搜索成功率等性能方面，与现有同样基于Pareto最优的QoS度量空间的划分进行求解的PODWCA算法进行了仿真比较。仿真验证LPNOA算法在同等计算复杂度下剩余NP完全区域面积所占比例比PODWCA算法低10％～15％，且响应速度略高于PODWCA算法，算法成功率最多比PODWCA算法高0.6％。
　　 随着网络规模的扩大和复杂化，精确网络状态信息的获取越来越难，而非精确的动态网络参数可能导致网络性能极度恶化。本文提出了一种基于非精确网络状态信息的预计算与在线计算结合的QoS路由算法（POCQRA—INSI算法）。该算法采用蚁群算法作为基本搜索算法，分为预计算和在线计算阶段，不同阶段对信息素进行不同定义。本文通过对LPNOA算法在动态网络中的算法性能进行仿真比较，验证了动态网络参数的非精确性对算法性能产生的负面影响，LPNOA算法在动态网络中路径搜索成功率比一般网络环境的情况降低约4％左右，搜索效率降低约15％左右，而POCQRA—INSI算法却基本保持在一般网络环境下的情况。
　　 另外，本文还研究了基于带宽代理的接纳控制机制，完成了四种接纳控制算法的仿真建模，并选取接纳率、网络利用率和平均等待时间作为算法性能的评价指标进行仿真比较。
　　 文章最后概括的总结了所取得的研究成果，并对进一步深入研究QoS路由算法的研究方向进行了展望。

目录

文摘

英文文摘

第一章 绪论

1.1 课题背景及研究意义

1.1.1 QoS概述

1.1.2 QoS的主要研究内容

1.1.3 QoS路由的研究意义及研究现状

1.1.4 DiffServ网络架构中的接纳控制机制

1.2 研究内容及所做工作

1.3 论文的组织结构

第二章 多约束QoS路由技术

2.1 QoS路由的基本问题

2.1.1 QoS路由的网络模型

2.1.2 QoS的度量

2.1.3 QoS路由中基本问题的分类

2.1.4三类NP完全问题

2.2 基于Pareto最优的QoS度量空间的划分

2.2.1 Pareto最优化理论及其应用

2.2.2 基于Pareto最优的QoS度量空间划分

2.3 几种QoS路由研究方法

2.3.1 线性搜索与非线性搜索

2.3.2 预计算与在线计算

2.4 本章小结

第三章 一般网络环境中的QoS路由算法研究

3.1 算法基础

3.1.1 两加性度量约束QoS路由问题的特性分析

3.1.2 当前算法存在问题及解决方法

3.2 LPNOA算法的设计与实现

3.2.LPNOA算法的基本流程

3.2.2 预计算阶段的算法设计

3.2.3 在线计算阶段的算法设计

3.3 LPNOA算法的仿真分析

3.3.1 仿真设计

3.3.2 算法的计算复杂度分析

3.3.3 算法的响应速度分析

3.3.4 算法的路径搜索成功率分析

3.4 本章小结

第四章 基于动态网络参数的QoS路由算法研究

4.1 研究背景

4.1.1 动态网络中网络参数的非精确性

4.1.2 蚁群算法简介

4.2 基于概率的两加性度量QoS路由问题建模

4.3 POCQRA—INSI算法的设计与实现

4.3.1 POCORA—INSI算法的基本流程

4.3.2 预计算阶段的具体设计

4.3.3 在线计算阶段的具体设计

4.4 POCQRA—INSI算法的仿真分析

4.4.1 仿真设计

4.4.2 算法的路径搜索成功率分析

4.4.3 算法受动态网络参数的影响分析

4.5 本章小结

第五章 QoS接纳控制机制的仿真研究

5.1 基于带宽代理的接纳控制机制

5.1.1 带宽代理(BB)的功能结构

5.1.2 集中式和分层BB的结构

5.1.3 BB进行接纳控制的基本工作流程

5.2 QoS接纳控制算法的设计

5.2.1 算法中的基本功能实体

5.2.2 SAC算法的消息处理流程

5.2.3 四种算法的流程设计

5.2.4 算法的具体实现

5.3 QoS接纳控制算法的仿真设计

5.3.1 仿真场景设置及网络参数

5.3.2 仿真结果分析

5.4 本章小结

第六章 全文总结与展望

6.1 研究工作总结

6.2 研究展望

参考文献

附录

致谢

攻读学位期间发表的学术论文