基于蚂蚁算法的QoS路由算法研究

摘要

随着Imemet的飞速发展，IP网络不但在规模而且在用户数量方面都得到了巨大增长，同时新的多媒体业务也越来越普遍，QoS路由问题已经成为Imemet发展中最具有挑战性的、最为活跃的研究领域之一。QoS受限路由问题是NP完全问题，用常规方法难以获得满意的结果。智能技术具有自适应、自学习和推理等功能，在一些问题上能够得到比常规方法更好的效果，目前已在通信、电子等诸多领域中得到广泛应用。 00S路由的任务就是在网络中寻找一条路径，它能够满足带宽、时延、时延抖动和费用的限制。人们尝试着采用蚂蚁算法来寻找路由，获得了满意的结果。但是，这种算法也存在一些缺陷，如：需要较长的搜索时间，蚂蚁算法的复杂度可以反映这一点；容易出现停滞现象，即搜索进行到一定程度后，所有个体所发现的解完全一致，不能对解空间进一步进行搜索，不利于发现更好的解。 在研究传统的蚂蚁算法的优点及其缺点，提出了一种新的QoS路由算法。 算法通过蚂蚁泛滥来寻找路由，蚂蚁携带着所经路径的信息。算法的关键是利用蚂蚁所经节点来控制泛滥的规模：所有中间节点只复制和泛滥到达它的最优的一只蚂蚁。这样，通过约束条件下的穷举搜索，最后一定可以找到源节点和目的节点间的满足QoS要求的路由。 算法充分考虑了部分链路出现拥塞的情况。每当拥塞出现，从源节点和目的节点两边逐渐增大搜索范围重新寻路，并尽量利用源路由有用信息，加快算法收敛。这样，通过加快二次寻路速度的办法，实现了拥塞链路上的数据改道和分流，减少了网络振荡。 通过算法理论分析和仿真实验，算法达到了设计目的，具有思路直观、算法收敛快、拥塞应对能力强的优点。

目录

文摘

英文文摘

独创性声明及学位论文版权使用授权书

1绪论

1.1课题背景

1.2国内外概况

1.3课题主要研究工作

2传统蚂蚁算法分析

2.1蚂蚁特性研究

2.2早期基本蚂蚁算法的实现

2.3基本蚂蚁算法的实验研究及优缺点分析

2.4蚁群算法和最值蚂蚁算法

2.5蚁群算法的优缺点及实现难点分析

2.6本章小结

3改进蚂蚁算法的QoS路由算法

3.1 QoS多约束路由算法

3.2早期基本蚂蚁算法解决多约束QoS路由问题

3.3对基于基本蚂蚁算法的QoS路由的改进

3.4改进蚂蚁算法对QoS路由的拥塞规避

3.5改进蚂蚁算法主要步骤

3.6仿真实验结果分析

3.7本章小结

4结论

4.1已完成的工作

4.2今后工作

致 谢

参考文献