基于蚁群算法的邻域分区优化qos单播路由算法研

《基于蚁群算法的邻域分区优化qos单播路由算法研》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、基于蚁群算法的邻域分区优化QoS单播路由算法研随着网络技术的高速发展，网络的应用越来越广泛，全新的多媒体业务应运而生，对网络服务质量(QoS)的要求也更高，而传统网络所提供的服务方式已无法满足新业务的需求，设计满足新业务要求的网络控制机制和路由算法是当前的一个急待解决的问题。而现有的很多算法只对QoS一个或两个约束条件进行研究，在多种QoS约束下，这些算法具有一定的局限性。如何解决多个约束QoS路由问题，如何在满足业务要求的同时，尽量减少资源消耗，合理分配网络的流量负荷，减少阻塞率，成为新关注的热点。在解决这一问题时，路由算法的选择又

2、是其中的一个核心问题，并且带宽、延时、访问花费是决定选择该路径的关键因素。论文针对这一状况和蚁群算法在大规模问题求解过程中存在的时间性能和算法复杂度的优化问题，提出了用基于蚁群算法的邻域分区优化算法对大规模的网络进行路由选择，也就是把大规模的网络按其区域位置分解成小规模的子系统，然后应用蚁群算法进行路由选择的仿真，该方法不但改善了蚁群算法在求解大规模问题的时间性能和算法复杂度，同时也解决了传统的路径选择不使用次优路径的弊端。论文在做路径选择时，主要用了带宽、延时、访问花费来作为路径选择的参数，用蚁群算法作为路径选择算法。论文的主要工作

3、如下：一、对论文的选题背景、国内外QoS单播路由的研究现状、蚁群算法应用及研究和论文结构作概述；二、对路由原理、路由协议、路由算法、QoS路由等基本概念和原理作了系统的阐述三、对蚁群算法的原理和发展作了概述，并针对普通蚁群算法在求解大规模优化问题时面临着时间和性能的问题，把大规模优化问题进行分解为子规模优化问题，用蚁群算法进行仿真实验和结果分析。四、把改进的蚁群算法思想应用于OoS单播路由算法中，进行网络模型的构建，同时用服务质量的带宽、延时、访问花费三个参数，进行路由算法的模拟运算，寻找最佳路径，并对实验结果进分析。五、总结，对未来

4、的研究工作做出展望。作者：杨丽华学科专业：通信与信息系统授予学位：硕士学位授予单位：云南大学导师姓名：施心陵学位年度：2005语种：chi分类号：TP393关键词：路由算法  QoS单播路由  蚁群算法  邻域分区蚁群算法及其在路由优化中的应用路由算法是网络的重要组成部分，它直接影响着网络性能，而含有多约束条件的QoS路由是一个NP-C问题，传统的路由算法很难解决，因此，一些学者尝试采用不同的算法相结合或者针对问题对某些算法进行改进来解决路由优化问题。其中蚁群算法是一个行之有效的方法，针对不同的网络，它在保证服务质量的前提下能够搜索到

5、网络中的最优链路，提高了网络的传输效率。而这些研究缺乏通用的标准，如何把不同的问题归结到一个统一的框架下解决路由优化问题，如何提高寻优速度，缩短运行时间是当前的一个研究热点。1蚁群算法的定义1.1蚁群算法基本定义定义1(蚁群算法)蚁群算法(antcolonyoptimization，ACO)，又称蚂蚁算法，是一种用来在图中寻找最优路径的技术。它最早出现在1992年Dorigo[1]的博士论文里，该方法具有正反馈、分布式计算和富于建设性的贪婪启发式搜索的特点，主要用于求解组合优化问题。定义2(启发式算法)对于那些受大自然的运行规律或者面

6、向具体问题的经验、规则启发出来的方法，人们常常称之为启发式算法。现在的启发式算法也不是全部来自然的规律，也有来自人类积累的工作经验。收定义3(信息素)蚂蚁释放一种化学物质，根据环境中的这种物质蚂蚁可以找到食物和窝之间的最短路径，我们称这种物质为信息素。定义4(信息素更新)信息素更新是指路径上信息素量与蚂蚁数量的变化和时间的推移之间存在增加和消失的变化关系。每只蚂蚁走完一步或对所有n个节点的遍历完成后，要对链路上的信息进行更新。因此，定义t+n时刻在节点i到节点j的路径(i,j)上的信息量计算公式为+=1+(1)==1(2)式中：——信

7、息素挥发系数，——本次循环中节点i到节点j的路径上信息素的增量。——第k只蚂蚁在本次循环中在节点i到节点j的路径上留下的信息量。定义5(链路选择概率)信息素踪迹越浓的路径，被选中的概率越大，即路径概率选择机制。设网络G=(V,E)，这里V表示图中顶点的集合，设=

8、V

9、，E表示边的集合。蚁群优化的目的是寻找图G中起始节点Vi到目的节点Vj的最短路径，每条边e(i,j)∈E都有一个信息素变量Tij，Tij会随着迭代次数的增加而变化。Pij表示在节点i选择到节点j的概率。表示节点i处可选择的下一跳邻居节点j的集合。则蚂蚁在选择路径时会根据可

10、选每条链路上的选择概率进行选择，并在该节点根据概率分配蚂蚁。概率公式为=*(3)式中：——节点i可选的下一跳节点集合。=1(4)式中：——能见度因数，它由某种启发式算法决定。，，——3个参数，分别反映了蚂蚁在运动过程中所