当前位置:主页 > 科技论文 > 自动化论文 >

蚁群算法在网络路由中的应用研究

发布时间:2018-06-11 10:29

  本文选题:QoS路由 + NP-C问题 ; 参考:《成都理工大学》2017年硕士论文


【摘要】:随着计算机网络的快速发展,网络应用也越来越多元化,网络结构也越来越复杂,人们对于网络质量的要求同时也越来越高,限制的方面也越来越多。由此产生的服务质量(Quality of Service)简称QoS,它作为衡量网络传输性能的新的指标,保障网络的QoS需求,真正的关键是选择合适的QoS路由算法。而QoS路由是一个NP-C(Non-deterministic Polynomial Complete,NP完全问题)问题,传统的算法很难解决这样的问题。网络拥塞也是当今大规模要求多媒体应用下的一个大问题,在网络路由的查找过程中容易陷入拥塞的情况出现丢失数据,甚至由于拥塞的崩溃导致网络的瘫痪。这些网络路由上的问题是当今研究的热点与难点。根据网络路由的要求,研究者们提出使用蚁群算法来解决此类问题。蚁群算法是一种群智能算法,它主要是利用蚂蚁在寻食过程中与环境之间的信息传递,实现最优路径的寻找;使用一种正反馈的机制,通过信息素的不断更新最后达到收敛于全局最优路径,这种算法具有分布式、随机性、自适应的特性,适合解决NP-C问题。因此它能很好的运用到QoS路由中,同时蚁群算法的反馈机制能够应用到寻优中,绕过网络拥塞路段,减低拥塞路段的网络负载,能够较好的解决网络拥塞的问题。本文分析网络路由和蚁群算法国内外研究和发展的现状。解析网络路由存在的相关技术如传输方式、QoS路由、路由模型、网络拥塞、路由的基本算法以及网络相关协议。深入研究蚁群算法的原理、模型、参数、实现步骤、优点和不足,蚁群算法主要是收敛速度慢、出现停滞以及局部最优化的问题。本文研究蚁群算法运用在网络路由的使用情况,分析在这些运用中主要存在的停滞和局部最优化问题,以及对网络拥塞中寻路的使用。本文对蚁群算法在网络路由中的相关应用提出相应的改进方案:(1)针对蚁群算法在网络QoS运用中存在上述问题,基本蚁群算法中加入蚁后和使用基于优化排序的蚁群系统,从而增加网络的搜索范围,和蚁群算法解的随机性,从而减少路由中的停滞现象和局部优化;(2)针对络拥塞的问题,利用基本蚁群算法改进其的状态转移概率,使用逆向的思维方式计算状态转移概率公式;使用惩罚和奖励的机制改进信息素的更新策略,从而降低拥塞的几率,提高网络的通信效率,减少丢包率,使整个网络达到一定的网络负载均衡,不会在多媒体的应用上出现数据的大量丢失。本文通过NS2仿真平台对改进蚁群算法的实验设计仿真,同时对基本蚁群算法和网络拥塞使用的Dijkstra算法的仿真,可以明确的看到在网络QoS路由中改进应用效果,从网络的时延、抖动、代价上都有所提升。而在网络拥塞中,可以明显的得出网络负载和时延、丢包、吞吐量上有所改善,在相同的迭代次数和负载下网络数据的丢失明显较少,同时不会影响数据的传输和资源的使用。
[Abstract]:With the rapid development of computer network, the network application is becoming more and more diversified, the network structure is becoming more and more complex, and the requirement of network quality is becoming higher and higher. The quality of Service (QoS), which is a new index to measure the transmission performance of the network, guarantees the QoS requirement of the network, and the real key is to select the appropriate QoS routing algorithm. QoS routing is a NP-C Non-deterministic complete problem (NP-C), which is difficult to solve by traditional algorithms. Network congestion is also a big problem under the large-scale multimedia application nowadays. It is easy to lose data in the process of network routing lookup, even because of the collapse of congestion, the network is paralyzed. These network routing problems are hot and difficult research. According to the requirements of network routing, researchers propose to use ant colony algorithm to solve such problems. Ant colony algorithm (ACA) is a group intelligent algorithm, which mainly uses the information transfer between ant and environment in the process of searching for food, and uses a positive feedback mechanism. The algorithm converges to the global optimal path through the continuous updating of pheromones. This algorithm has the characteristics of distributed, random and adaptive, and is suitable for solving the NP-C problem. Therefore, it can be well applied to QoS routing. At the same time, the feedback mechanism of ant colony algorithm can be applied to the optimization, bypass the congested section of the network, reduce the network load of the congested section, and solve the problem of network congestion. This paper analyzes the research and development of network routing and ant colony algorithm at home and abroad. Related technologies such as transport mode QoS routing, routing model, network congestion, basic routing algorithms and network related protocols are analyzed. The principle, model, parameters, implementation steps, advantages and disadvantages of ant colony algorithm are deeply studied. The main problems of ant colony algorithm are slow convergence, stagnation and local optimization. In this paper, we study the usage of ant colony algorithm in network routing, and analyze the main problems of stagnation and local optimization in these applications, as well as the use of routing in network congestion. In this paper, we put forward the corresponding improved scheme: 1) aiming at the above problems of ant colony algorithm in the application of network QoS, the basic ant colony algorithm includes ant queen and uses ant colony system based on optimized ranking. In order to increase the search range of the network and randomness of the solution of the ant colony algorithm, thus reducing the stagnation phenomenon in the routing and local optimization of the problem of congestion, the basic ant colony algorithm is used to improve its state transition probability. The formula of state transition probability is calculated in reverse thinking mode, and the mechanism of punishment and reward is used to improve the pheromone updating strategy, thus reducing the probability of congestion, improving the communication efficiency of the network, and reducing the rate of packet loss. Make the whole network to achieve a certain network load balance, there will not be a large number of data loss in multimedia applications. Through NS2 simulation platform to improve ant colony algorithm experimental design simulation, at the same time the basic ant colony algorithm and network congestion Dijkstra algorithm simulation, can clearly see in the network QoS routing improvement effect, from the network delay, Jitter, the cost has improved. In the network congestion, the network load and delay, packet loss, throughput can be improved, the network data loss is obviously less under the same iteration times and load, and the data transmission and resource usage will not be affected at the same time.
【学位授予单位】:成都理工大学
【学位级别】:硕士
【学位授予年份】:2017
【分类号】:TP18;TP393.0

【参考文献】

相关期刊论文 前10条

1 王文国;樊丽娟;刘洋;;改进的蚁群算法与网络QoS组播路由研究[J];通信技术;2016年12期

2 洪文圳;李冬睿;沈阳;;基于蚁群优化的高性能拥塞控制路由机制[J];量子电子学报;2016年05期

3 刘晓飞;;计算机网络拥塞控制算法综述[J];铜仁学院学报;2016年04期

4 邱泽敏;;一种蚁群算法优化的高效防拥塞QoS路由算法[J];计算机仿真;2015年10期

5 武玉坤;;改进蚁群算法在WMN拥塞控制中的应用[J];电脑知识与技术;2015年07期

6 姚艳;;一种最大最小蚂蚁系统的改进算法[J];数学的实践与认识;2014年15期

7 周德荣;夏龄;舒涛;田关伟;;NS2网络协议虚拟仿真实验平台研究[J];实验技术与管理;2014年03期

8 卢来;;有关计算机网络的路由研究[J];计算机光盘软件与应用;2012年12期

9 杨晓敏;王春红;李萍;;基于蚁群算法的QoS组播路由问题研究[J];系统仿真技术;2012年02期

10 万博;卢昱;陈立云;申吉红;;基于改进蚁群算法的拥塞规避QoS路由算法[J];计算机工程;2011年20期

相关硕士学位论文 前10条

1 刘洋;基于改进蚁群算法的有线网络路由QoS研究[D];曲阜师范大学;2016年

2 刘建芳;蚁群算法的研究及其应用[D];重庆大学;2015年

3 宋悦;蚁群算法在路由优化中的应用研究[D];北京交通大学;2015年

4 王健安;基于蚁群优化算法的分布式多约束Qos路由算法研究[D];长春理工大学;2014年

5 吴海红;认知网络中的蚁群路由算法研究[D];电子科技大学;2011年

6 邵志学;基于蚁群算法的QoS路由研究[D];沈阳航空航天大学;2011年

7 陈莹;基于蚁群算法的QoS网络路由的研究与设计[D];武汉理工大学;2010年

8 顾家智;蚁群优化算法及其在组播路由中的应用研究[D];上海交通大学;2009年

9 杨洁;基于信息素强度的蚁群算法及其应用研究[D];湖南大学;2009年

10 解英文;基于蚁群算法的网络路由算法[D];山东大学;2009年



本文编号:2004930

资料下载
论文发表

本文链接:https://www.wllwen.com/kejilunwen/zidonghuakongzhilunwen/2004930.html


Copyright(c)文论论文网All Rights Reserved | 网站地图 |

版权申明:资料由用户86129***提供,本站仅收录摘要或目录,作者需要删除请E-mail邮箱bigeng88@qq.com