基于新型蚂蚁算法的QoSR理论及技术研究

论文摘要

网络服务质量路由（Quality of Service Routing）是计算机网络理论研究的重要领域，随着网络的发展和网络应用的快速增长，对网络路由提出了更高的要求，为解决解决在Internet网上传输语音、视频等数据时所遇到的带宽变化、数据丢失、延迟、抖动等QoS问题。本文对基于Internet网的QoSR问题的理论及技术进行研究。本文提出了一种扩展的Dijkstra算法，该算法可找到QoS参数的极限值，能解决一些QoSR问题，并对该算法进行了复杂性分析与比较。蚂蚁算法作为探索类算法在近几年逐步得到推广和应用，在研究蚂蚁算法后，本文提出了一种新型的蚂蚁算法，并保留蚂蚁算法的信息素概念，该算法对经典蚂蚁算法做了3个方面的根本改进，它们是： 1．摒弃蚂蚁算法中概率方式的转移模式，采用确定方式的转移模式； 2．摒弃一群蚂蚁的探路模式，采用一只蚂蚁的探路模式； 3．蚂蚁在探索路径时，总是沿着信息素最小的路径前进。通过实际编程和计算，证实了新型的蚂蚁算法能解决QoSR问题，能找到较优QoSR或最优QoSR。经过对该算法的分析，发现其时间复杂性与蚂蚁移动的步数成线性关系。本文在研究新型蚂蚁算法后，证明了在一个连通的有限网络中，采用该算法，蚂蚁经过有限步移动后，可到达网络中的任意一个结点。这个结论也证明了新型蚂蚁算法算法有初始的QoSR解。本文对新型蚂蚁算法的最优性、简单性、鲁棒性、收敛性、灵活性5种性能指标进行定性分析。分析结果表明该算法具有优良的性能特征。本文研究了该算法时间复杂性与蚂蚁移动步数之间的关系，得出结论是新型蚂蚁算法的计算时间开销与蚂蚁移动步数成线性关系。本文研究了蚂蚁移动步数与QoSR解的关系，得出结论是在蚂蚁移动MLog2N步后，就能寻找到较优的QoS路由，有时能寻找到最优的QoS路由。本文对该算法的时间复杂性进行定量分析，最终得到的结论是新型蚂蚁算法的时间复杂性为0（N3Log2N）。并与有关的QoSR算法的时间复杂性进行比较，结果表明该算法的时间复杂性较优。本文在研究新型蚂蚁算法理论的基础上，进一步对新型蚂蚁算法的鲁棒性进行实际计算与研究，结果证实新型蚂蚁算法具有鲁棒性。

论文目录

摘要

Abstract

第1章概述

1.1 研究的背景、目标和课题来源

1.1.1 研究的背景

1.1.2 研究的内容和目标

1.1.3 研究的课题来源

1.2 论文结构与章节内容

1.3 QoS的概念与定义

1.3.1 QoS问题的提出

1.3.2 QoS的定义

1.4 QoS的研究机构与组织

1.4.1 ISO／OSI

1.4.2 ATM论坛

1.4.3 IETF

1.5 QoS的模型与相关技术

1.5.1 综合业务模型（IntServ）

1.5.2 区分业务模型（differentiated services）

1.5.3 QoSR（QoS-based routing）

1.5.4 MPLS技术（Multi-Protocol Label Switching）

1.6 按特性的网络路由分类

1.7 小结

第2章典型的优化算法与QOSR算法

2.1 蚂蚁算法

2.1.1 蚂蚁算法简介

2.1.2 蚂蚁算法描述

2.1.3 蚂蚁算法的应用

2.2 遗传算法

2.2.1 遗传算法简介

2.2.2 遗传算法描述

2.2.3 遗传算法的应用

2.3 模拟退火算法

2.3.1 模拟退火算法简介

2.3.2 模拟退火算法描述

2.4 人工神经网络算法

2.4.1 人工神经网络算法简介

2.4.2 人工神经网络算法的应用

2.5 QoSR算法

2.5.1 多项式非启发类

2.5.2 QoS度量相关

2.5.3 探测法

2.5.4 扩展距离向量算法

2.5.5 限定QoS度量

2.5.6 路径子空间搜索

2.5.7 花费函数

2.5.8 多种QoSR算法的结合

2.6 对4种典型的优化算法用于QoSR的分析

2.7 经典蚂蚁算法用于QoSR时存在的问题

2.7.1 概率转移方式问题

2.7.2 单个参数约束问题

2.7.3 多只蚂蚁寻路问题

2.7.4 解决上述问题的初步想法

2.8 小结

第3章扩展DIJKSTRA算法与极限值

3.1 用扩展DIJKSTRA算法求解QoS极限值

3.1.1 网络图的随机生成

3.1.2 网络图的QoS参数约束的极限值

3.1.3 提出扩展Dijkstra算法

3.1.4 扩展Dijkstra算法求解QoS极限值的计算结果

3.1.5 计算结果说明

3.2 扩展DIJKSTRA算法描述

3.2.1 定义符号

3.2.2 定义运算符

3.2.3 路由参数的计算

3.2.4 扩展Dijkstra算法

3.3 用扩展DIJKSTRA算法求解QoSR问题

3.3.1 多约束条件下的路由选择算法的改进

3.3.2 计算实例1

3.3.3 计算实例2

3.3.4 计算实例3

3.4 扩展DIJKSTRA算法的优缺点

3.5 扩展DIJKSTRA算法的时间复杂性

3.6 小结

第4章新型蚂蚁算法的提出

4.1 新型蚂蚁算法的设计思路

4.2 新型蚂蚁算法描述

4.2.1 定义符号

4.2.2 新型蚂蚁算法

4.3 新型蚂蚁算法的计算实例

4.3.1 约束条件

4.3.2 边的QoS参数

4.3.3 路径（Path）计算结果

4.3.4 延迟（Delay）计算结果

4.3.5 抖动（Dithering）计算结果

4.3.6 可靠性（1-Loss rate）计算结果

4.3.7 计算结果的图形显示

4.3.8 信息素与计算时间

4.3.9 蚂蚁寻找QoSR时所走的100步路径

4.4 新型蚂蚁算法的计算实例结果分析

4.5 小结

第5章新型蚂蚁算法初始解的理论证明与算法性能分析

5.1 新型蚂蚁算法可达性证明

5.2 新型蚂蚁算法的初始解

5.3 判别算法优劣的5个性能指标

5.4 最优化定性分析

5.5 简单性定性分析

5.6 鲁棒性定性分析

5.7 收敛性定性分析

5.8 灵活性定性分析

5.9 小结

第6章新型蚂蚁算法的时间复杂性研究

6.1 新型蚂蚁算法时间复杂性理论分析与计算

6.2 连通图平均边数计算公式推导

6.3 新型蚂蚁算法时间复杂性与蚂蚁移动步数的关系

6.4 新型蚂蚁算法移动步数与QoSR解的关系

6.5 新型蚂蚁算法时间复杂性定量分析与结论

6.6 新型蚂蚁算法时间复杂性与其它相关算法的比较

6.7 小结

第7章新型蚂蚁算法的鲁棒性研究

7.1 算法鲁棒性研究的重要性

7.2 新型蚂蚁算法鲁棒性研究目的

7.3 新型蚂蚁算法鲁棒性计算实例

7.4 新型蚂蚁算法鲁棒性计算实例的结果分析

7.5 小结

第8章扩展DIJKSTRA算法求解QOS极限值计算实验

8.1 QoS参数与程序代码

8.1.1 网络边的QoS参数表示

8.1.2 主程序代码

8.1.3 延时、抖动极限值子程序代码

8.1.4 可靠性极限值子程序代码

8.1.5 带宽极限值子程序代码

8.2 极限值计算结果及说明

8.2.1 延时极限值计算结果及说明

8.2.2 抖动极限值计算结果及说明

8.2.3 可靠性极限值计算结果及说明

8.2.4 带宽极限值计算结果及说明

8.3 小结

第9章新型蚂蚁算法的仿真实验

9.1 仿真实验平台介绍

9.1.1 仿真实验平台

9.1.2 MATLAB 6软件

9.1.3 OPNET 8软件

9.2 新型蚂蚁算法搜索QOSR的仿真实验

9.2.1 网络边的QoS参数表示及QoS约束条件

9.2.2 计算结果的图形显示

9.2.3 程序代码

9.2.4 计算结果数据及说明

9.3 QoSR延时、抖动、可靠性的仿真实验

9.3.1 仿真实验实例

9.3.2 收集统计量

9.3.3 仿真结果图形

9.3.4 仿真结果

9.3.5 仿真结果小结

9.4 新型蚂蚁算法时间复杂性的计算实验

9.4.1 本实验的目的与过程

9.4.2 部分计算实例

9.5 新型蚂蚁算法鲁棒性的计算实验

9.5.1 本实验的目的

9.5.2 本实验的过程

9.5.3 部分计算实例

9.6 小结

第10章总结与展望

10.1 研究工作总结

10.2 论文中主要的创新点

10.3 展望

10.3.1 新型蚂蚁算法可实现网络流量动态调整

10.3.2 新型蚂蚁算法可用于WLAN网络的QOSR

博士期间发表论文与完成的科研项目和工程项目

致谢

参考文献

基于新型蚂蚁算法的QoSR理论及技术研究

论文摘要

论文目录

相关论文文献

猜你喜欢