本文選題：QoS路由 + NP-C問題�。� 參考：《成都理工大學(xué)》2017年碩士論文

【摘要】：隨著計算機網(wǎng)絡(luò)的快速發(fā)展,網(wǎng)絡(luò)應(yīng)用也越來越多元化,網(wǎng)絡(luò)結(jié)構(gòu)也越來越復(fù)雜,人們對于網(wǎng)絡(luò)質(zhì)量的要求同時也越來越高,限制的方面也越來越多。由此產(chǎn)生的服務(wù)質(zhì)量(Quality of Service)簡稱QoS,它作為衡量網(wǎng)絡(luò)傳輸性能的新的指標,保障網(wǎng)絡(luò)的QoS需求,真正的關(guān)鍵是選擇合適的QoS路由算法。而QoS路由是一個NP-C(Non-deterministic Polynomial Complete,NP完全問題)問題,傳統(tǒng)的算法很難解決這樣的問題。網(wǎng)絡(luò)擁塞也是當(dāng)今大規(guī)模要求多媒體應(yīng)用下的一個大問題,在網(wǎng)絡(luò)路由的查找過程中容易陷入擁塞的情況出現(xiàn)丟失數(shù)據(jù),甚至由于擁塞的崩潰導(dǎo)致網(wǎng)絡(luò)的癱瘓。這些網(wǎng)絡(luò)路由上的問題是當(dāng)今研究的熱點與難點。根據(jù)網(wǎng)絡(luò)路由的要求,研究者們提出使用蟻群算法來解決此類問題。蟻群算法是一種群智能算法,它主要是利用螞蟻在尋食過程中與環(huán)境之間的信息傳遞,實現(xiàn)最優(yōu)路徑的尋找;使用一種正反饋的機制,通過信息素的不斷更新最后達到收斂于全局最優(yōu)路徑,這種算法具有分布式、隨機性、自適應(yīng)的特性,適合解決NP-C問題。因此它能很好的運用到QoS路由中,同時蟻群算法的反饋機制能夠應(yīng)用到尋優(yōu)中,繞過網(wǎng)絡(luò)擁塞路段,減低擁塞路段的網(wǎng)絡(luò)負載,能夠較好的解決網(wǎng)絡(luò)擁塞的問題。本文分析網(wǎng)絡(luò)路由和蟻群算法國內(nèi)外研究和發(fā)展的現(xiàn)狀。解析網(wǎng)絡(luò)路由存在的相關(guān)技術(shù)如傳輸方式、QoS路由、路由模型、網(wǎng)絡(luò)擁塞、路由的基本算法以及網(wǎng)絡(luò)相關(guān)協(xié)議。深入研究蟻群算法的原理、模型、參數(shù)、實現(xiàn)步驟、優(yōu)點和不足,蟻群算法主要是收斂速度慢、出現(xiàn)停滯以及局部最優(yōu)化的問題。本文研究蟻群算法運用在網(wǎng)絡(luò)路由的使用情況,分析在這些運用中主要存在的停滯和局部最優(yōu)化問題,以及對網(wǎng)絡(luò)擁塞中尋路的使用。本文對蟻群算法在網(wǎng)絡(luò)路由中的相關(guān)應(yīng)用提出相應(yīng)的改進方案:(1)針對蟻群算法在網(wǎng)絡(luò)QoS運用中存在上述問題,基本蟻群算法中加入蟻后和使用基于優(yōu)化排序的蟻群系統(tǒng),從而增加網(wǎng)絡(luò)的搜索范圍,和蟻群算法解的隨機性,從而減少路由中的停滯現(xiàn)象和局部優(yōu)化;(2)針對絡(luò)擁塞的問題,利用基本蟻群算法改進其的狀態(tài)轉(zhuǎn)移概率,使用逆向的思維方式計算狀態(tài)轉(zhuǎn)移概率公式;使用懲罰和獎勵的機制改進信息素的更新策略,從而降低擁塞的幾率,提高網(wǎng)絡(luò)的通信效率,減少丟包率,使整個網(wǎng)絡(luò)達到一定的網(wǎng)絡(luò)負載均衡,不會在多媒體的應(yīng)用上出現(xiàn)數(shù)據(jù)的大量丟失。本文通過NS2仿真平臺對改進蟻群算法的實驗設(shè)計仿真,同時對基本蟻群算法和網(wǎng)絡(luò)擁塞使用的Dijkstra算法的仿真,可以明確的看到在網(wǎng)絡(luò)QoS路由中改進應(yīng)用效果,從網(wǎng)絡(luò)的時延、抖動、代價上都有所提升。而在網(wǎng)絡(luò)擁塞中,可以明顯的得出網(wǎng)絡(luò)負載和時延、丟包、吞吐量上有所改善,在相同的迭代次數(shù)和負載下網(wǎng)絡(luò)數(shù)據(jù)的丟失明顯較少,同時不會影響數(shù)據(jù)的傳輸和資源的使用。
[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.
【學(xué)位授予單位】：成都理工大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2017
【分類號】：TP18;TP393.0

【參考文獻】

相關(guān)期刊論文 前10條

1 王文國;樊麗娟;劉洋;;改進的蟻群算法與網(wǎng)絡(luò)QoS組播路由研究[J];通信技術(shù);2016年12期

2 洪文圳;李冬睿;沈陽;;基于蟻群優(yōu)化的高性能擁塞控制路由機制[J];量子電子學(xué)報;2016年05期

3 劉曉飛;;計算機網(wǎng)絡(luò)擁塞控制算法綜述[J];銅仁學(xué)院學(xué)報;2016年04期

4 邱澤敏;;一種蟻群算法優(yōu)化的高效防擁塞QoS路由算法[J];計算機仿真;2015年10期

5 武玉坤;;改進蟻群算法在WMN擁塞控制中的應(yīng)用[J];電腦知識與技術(shù);2015年07期

6 姚艷;;一種最大最小螞蟻系統(tǒng)的改進算法[J];數(shù)學(xué)的實踐與認識;2014年15期

7 周德榮;夏齡;舒濤;田關(guān)偉;;NS2網(wǎng)絡(luò)協(xié)議虛擬仿真實驗平臺研究[J];實驗技術(shù)與管理;2014年03期

8 盧來;;有關(guān)計算機網(wǎng)絡(luò)的路由研究[J];計算機光盤軟件與應(yīng)用;2012年12期

9 楊曉敏;王春紅;李萍;;基于蟻群算法的QoS組播路由問題研究[J];系統(tǒng)仿真技術(shù);2012年02期

10 萬博;盧昱;陳立云;申吉紅;;基于改進蟻群算法的擁塞規(guī)避QoS路由算法[J];計算機工程;2011年20期

相關(guān)碩士學(xué)位論文 前10條

1 劉洋;基于改進蟻群算法的有線網(wǎng)絡(luò)路由QoS研究[D];曲阜師范大學(xué);2016年

2 劉建芳;蟻群算法的研究及其應(yīng)用[D];重慶大學(xué);2015年

3 宋悅;蟻群算法在路由優(yōu)化中的應(yīng)用研究[D];北京交通大學(xué);2015年

4 王健安;基于蟻群優(yōu)化算法的分布式多約束Qos路由算法研究[D];長春理工大學(xué);2014年

5 吳海紅;認知網(wǎng)絡(luò)中的蟻群路由算法研究[D];電子科技大學(xué);2011年

6 邵志學(xué);基于蟻群算法的QoS路由研究[D];沈陽航空航天大學(xué);2011年

7 陳瑩;基于蟻群算法的QoS網(wǎng)絡(luò)路由的研究與設(shè)計[D];武漢理工大學(xué);2010年

8 顧家智;蟻群優(yōu)化算法及其在組播路由中的應(yīng)用研究[D];上海交通大學(xué);2009年

9 楊潔;基于信息素強度的蟻群算法及其應(yīng)用研究[D];湖南大學(xué);2009年

10 解英文;基于蟻群算法的網(wǎng)絡(luò)路由算法[D];山東大學(xué);2009年

，

本文編號：2004930