学位论文 > 优秀研究生学位论文题录展示

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

作　者: 陈骏坚
导　师: 李腊元
学　校: 武汉理工大学
专　业: 机械设计及理论
关键词: 网络服务质量路由 新型蚂蚁算法 扩展Dijkstra算法 时间复杂性 算法鲁棒性
分类号: TP393.02
类　型: 博士论文
年　份: 2006年
下　载: 326次
引　用: 2次
阅　读: 论文下载
 

内容摘要


网络服务质量路由（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算法的时间复杂性进行比较，结果表明该算法的时间复杂性较优。 本文在研究新型蚂蚁算法理论的基础上，进一步对新型蚂蚁算法的鲁棒性进行实际计算与研究，结果证实新型蚂蚁算法具有鲁棒性。

全文目录


摘要  3-5
Abstract  5-12
第1章 概述  12-24
  1.1 研究的背景、目标和课题来源  12-13
    1.1.1 研究的背景  12-13
    1.1.2 研究的内容和目标  13
    1.1.3 研究的课题来源  13
  1.2 论文结构与章节内容  13-15
  1.3 QoS的概念与定义  15-16
    1.3.1 QoS问题的提出  15
    1.3.2 QoS的定义  15-16
  1.4 QoS的研究机构与组织  16-17
    1.4.1 ISO／OSI  16
    1.4.2 ATM论坛  16
    1.4.3 IETF  16-17
  1.5 QoS的模型与相关技术  17-22
    1.5.1 综合业务模型(IntServ)  17-18
    1.5.2 区分业务模型(differentiated services)  18-21
    1.5.3 QoSR(QoS-based routing)  21
    1.5.4 MPLS技术(Multi-Protocol Label Switching)  21-22
  1.6 按特性的网络路由分类  22-23
  1.7 小结  23-24
第2章 典型的优化算法与QOSR算法  24-40
  2.1 蚂蚁算法  24-26
    2.1.1 蚂蚁算法简介  24
    2.1.2 蚂蚁算法描述  24-25
    2.1.3 蚂蚁算法的应用  25-26
  2.2 遗传算法  26-27
    2.2.1 遗传算法简介  26
    2.2.2 遗传算法描述  26-27
    2.2.3 遗传算法的应用  27
  2.3 模拟退火算法  27-29
    2.3.1 模拟退火算法简介  27-28
    2.3.2 模拟退火算法描述  28-29
  2.4 人工神经网络算法  29-30
    2.4.1 人工神经网络算法简介  29
    2.4.2 人工神经网络算法的应用  29-30
  2.5 QoSR算法  30-35
    2.5.1 多项式非启发类  30-31
    2.5.2 QoS度量相关  31
    2.5.3 探测法  31-32
    2.5.4 扩展距离向量算法  32
    2.5.5 限定QoS度量  32-33
    2.5.6 路径子空间搜索  33-34
    2.5.7 花费函数  34-35
    2.5.8 多种QoSR算法的结合  35
  2.6 对4种典型的优化算法用于QoSR的分析  35-37
  2.7 经典蚂蚁算法用于QoSR时存在的问题  37-38
    2.7.1 概率转移方式问题  37
    2.7.2 单个参数约束问题  37
    2.7.3 多只蚂蚁寻路问题  37-38
    2.7.4 解决上述问题的初步想法  38
  2.8 小结  38-40
第3章 扩展DIJKSTRA算法与极限值  40-50
  3.1 用扩展DIJKSTRA算法求解QoS极限值  40-43
    3.1.1 网络图的随机生成  40
    3.1.2 网络图的QoS参数约束的极限值  40
    3.1.3 提出扩展Dijkstra算法  40-41
    3.1.4 扩展Dijkstra算法求解QoS极限值的计算结果  41-43
    3.1.5 计算结果说明  43
  3.2 扩展DIJKSTRA算法描述  43-45
    3.2.1 定义符号  43-44
    3.2.2 定义运算符  44
    3.2.3 路由参数的计算  44
    3.2.4 扩展Dijkstra算法  44-45
  3.3 用扩展DIJKSTRA算法求解QoSR问题  45-48
    3.3.1 多约束条件下的路由选择算法的改进  45-46
    3.3.2 计算实例1  46
    3.3.3 计算实例2  46-47
    3.3.4 计算实例3  47-48
  3.4 扩展DIJKSTRA算法的优缺点  48
  3.5 扩展DIJKSTRA算法的时间复杂性  48
  3.6 小结  48-50
第4章 新型蚂蚁算法的提出  50-62
  4.1 新型蚂蚁算法的设计思路  50-51
  4.2 新型蚂蚁算法描述  51-52
    4.2.1 定义符号  51
    4.2.2 新型蚂蚁算法  51-52
  4.3 新型蚂蚁算法的计算实例  52-60
    4.3.1 约束条件  52
    4.3.2 边的QoS参数  52-55
    4.3.3 路径(Path)计算结果  55
    4.3.4 延迟(Delay)计算结果  55-56
    4.3.5 抖动(Dithering)计算结果  56-57
    4.3.6 可靠性(1-Loss rate)计算结果  57-58
    4.3.7 计算结果的图形显示  58
    4.3.8 信息素与计算时间  58-59
    4.3.9 蚂蚁寻找QoSR时所走的100步路径  59-60
  4.4 新型蚂蚁算法的计算实例结果分析  60-61
  4.5 小结  61-62
第5章 新型蚂蚁算法初始解的理论证明与算法性能分析  62-67
  5.1 新型蚂蚁算法可达性证明  62-63
  5.2 新型蚂蚁算法的初始解  63-64
  5.3 判别算法优劣的5个性能指标  64
  5.4 最优化定性分析  64-65
  5.5 简单性定性分析  65
  5.6 鲁棒性定性分析  65
  5.7 收敛性定性分析  65-66
  5.8 灵活性定性分析  66
  5.9 小结  66-67
第6章 新型蚂蚁算法的时间复杂性研究  67-78
  6.1 新型蚂蚁算法时间复杂性理论分析与计算  67
  6.2 连通图平均边数计算公式推导  67-69
  6.3 新型蚂蚁算法时间复杂性与蚂蚁移动步数的关系  69-71
  6.4 新型蚂蚁算法移动步数与QoSR解的关系  71-75
  6.5 新型蚂蚁算法时间复杂性定量分析与结论  75-76
  6.6 新型蚂蚁算法时间复杂性与其它相关算法的比较  76
  6.7 小结  76-78
第7章 新型蚂蚁算法的鲁棒性研究  78-81
  7.1 算法鲁棒性研究的重要性  78
  7.2 新型蚂蚁算法鲁棒性研究目的  78-79
  7.3 新型蚂蚁算法鲁棒性计算实例  79
  7.4 新型蚂蚁算法鲁棒性计算实例的结果分析  79-80
  7.5 小结  80-81
第8章 扩展DIJKSTRA算法求解QOS极限值计算实验  81-93
  8.1 QoS参数与程序代码  81-89
    8.1.1 网络边的QoS参数表示  81
    8.1.2 主程序代码  81-84
    8.1.3 延时、抖动极限值子程序代码  84-86
    8.1.4 可靠性极限值子程序代码  86-88
    8.1.5 带宽极限值子程序代码  88-89
  8.2 极限值计算结果及说明  89-92
    8.2.1 延时极限值计算结果及说明  89-90
    8.2.2 抖动极限值计算结果及说明  90-91
    8.2.3 可靠性极限值计算结果及说明  91
    8.2.4 带宽极限值计算结果及说明  91-92
  8.3 小结  92-93
第9章 新型蚂蚁算法的仿真实验  93-111
  9.1 仿真实验平台介绍  93-94
    9.1.1 仿真实验平台  93
    9.1.2 MATLAB 6软件  93-94
    9.1.3 OPNET 8软件  94
  9.2 新型蚂蚁算法搜索QOSR的仿真实验  94-100
    9.2.1 网络边的QoS参数表示及QoS约束条件  95-96
    9.2.2 计算结果的图形显示  96
    9.2.3 程序代码  96-99
    9.2.4 计算结果数据及说明  99-100
  9.3 QoSR延时、抖动、可靠性的仿真实验  100-102
    9.3.1 仿真实验实例  100
    9.3.2 收集统计量  100-101
    9.3.3 仿真结果图形  101
    9.3.4 仿真结果  101-102
    9.3.5 仿真结果小结  102
  9.4 新型蚂蚁算法时间复杂性的计算实验  102-104
    9.4.1 本实验的目的与过程  102-103
    9.4.2 部分计算实例  103-104
  9.5 新型蚂蚁算法鲁棒性的计算实验  104-109
    9.5.1 本实验的目的  104
    9.5.2 本实验的过程  104-105
    9.5.3 部分计算实例  105-109
  9.6 小结  109-111
第10章 总结与展望  111-119
  10.1 研究工作总结  111-114
  10.2 论文中主要的创新点  114-115
  10.3 展望  115-119
    10.3.1 新型蚂蚁算法可实现网络流量动态调整  115-117
    10.3.2 新型蚂蚁算法可用于WLAN网络的QOSR  117-119
博士期间发表论文与完成的科研项目和工程项目  119-121
致谢  121-122
参考文献  122-129

相似论文

  1. 机器带中断的若干延误问题研究,O223
  2. 多目标进化算法在网络QoS路由优化中的应用研究,TP393.02
  3. 基于分数阶微积分风力发电机变浆距控制方法研究,TM315
  4. 随机环境下多周期库存管理研究,F274
  5. 改进遗传算法及其在PID控制器参数优化中的应用,TP273
  6. 基于神经网络控制的船舶航迹自动舵技术,U664.82
  7. DSP模糊智能控制器在多随动系统中的应用研究,TP273.4
  8. 一类非确定型有穷自动机的极小化及时间复杂性,TP301.1
  9. 关联规则挖掘算法的研究与改进,TP311.13
  10. 优化PID控制器研究及其在热工对象控制中的应用,TK32
  11. 动态最小费用路在L_1模下的逆问题研究,O221
  12. 一种基于购买行为的非对称数字水印系统,TP309
  13. 基于AAM的人脸特征点定位方法研究,TP391.41
  14. 基于免疫遗传算法参数优化的PID控制,TM571.6
  15. 土地利用规划中的AHP-GA决策模型研究,F301
  16. 基于图像分割和小波变换的信息隐藏算法研究,TP391.41
  17. 数字水印在电子证件中的应用,TP309
  18. 多约束QoS路由算法研究,TP393.01
  19. 遗传算法研究及其在排课问题中的应用,TP18
  20. 曲线曲面的求值及降阶、等距变换的研究,TP391.41
  21. 迭代学习控制算法研究,TP181

中图分类: > 工业技术 > 自动化技术、计算机技术 > 计算技术、计算机技术 > 计算机的应用 > 计算机网络 > 一般性问题 > 计算机网络结构与设计
© 2012 www.xueweilunwen.com