【摘要】：無線Mesh網(wǎng)絡(luò)是一種能為用戶提供寬帶連接服務(wù)的多跳自組織、自配置網(wǎng)絡(luò)。隨著網(wǎng)絡(luò)不斷發(fā)展和用戶需求的提高，用戶希望網(wǎng)絡(luò)能提供具有服務(wù)質(zhì)量(Quality of Service, QoS)保障的業(yè)務(wù)。而多QoS約束下的路由是NP-難問題，傳統(tǒng)算法不能很好地解決該問題。蟻群算法(AntColony Optimization, ACO)是一種能行之有效地處理多約束優(yōu)化問題的算法，本文研究蟻群算法并將其應(yīng)用于無線Mesh網(wǎng)絡(luò)多約束QoS路由問題。主要從如下兩方面展開： 1.研究現(xiàn)有的蟻群算法應(yīng)用于網(wǎng)絡(luò)QoS路由問題的方式，在分析其優(yōu)缺點(diǎn)的基礎(chǔ)上，結(jié)合非常具有前景的無線Mesh網(wǎng)絡(luò)混合結(jié)構(gòu)特征，提出一種差異度蟻群多約束QoS路由算法IARQM。該算法綜合考慮所發(fā)現(xiàn)路徑的差異度來更新信息素，能有效避免信息素局部堆積導(dǎo)致的搜索能力下降。同時，考慮到信息素對尋徑的重要作用，算法提供緩存恢復(fù)機(jī)制，為暫時失效節(jié)點(diǎn)保留已積累的信息素，提高算法健壯性。并采用尋徑時傾向于更為穩(wěn)定的路由器節(jié)點(diǎn)的方法，進(jìn)一步保證網(wǎng)絡(luò)的穩(wěn)定性。論文實現(xiàn)了IARQM算法，并進(jìn)行了仿真實驗，結(jié)果表明該算法具有較好的性能和QoS保障能力。 2.一般無線Mesh網(wǎng)絡(luò)中采用單徑路由協(xié)議，但單徑路由協(xié)議存在可能造成網(wǎng)絡(luò)負(fù)載不平衡、節(jié)點(diǎn)擁塞發(fā)生等不足，因此，在研究現(xiàn)有基于蟻群算法的多徑路由基礎(chǔ)上，提出一種并行攝動導(dǎo)向性蟻群多徑路由算法PGARQ。PGARQ為了更好地生成節(jié)點(diǎn)關(guān)聯(lián)度低的多條路徑，，在算法中引入并行處理，利用并行節(jié)點(diǎn)的高速計算和處理能力并行地生成路徑；同時，針對蟻群算法容易陷入局部最優(yōu)解，結(jié)合導(dǎo)向性局部搜索算法改進(jìn)，并設(shè)計一種攝動方式進(jìn)一步優(yōu)化算法求解結(jié)果。實驗結(jié)果表明，PGARQ能較快地生成節(jié)點(diǎn)之間不相關(guān)的路徑，提高計算精度和減少計算時間，較好地保證了網(wǎng)絡(luò)QoS。
[Abstract]:Wireless Mesh network is a kind of multi-hop self-organizing and self-configuring network which can provide broadband connection service to users. With the continuous development of the network and the improvement of users' needs, users hope that the network can provide services with quality of service (Quality of Service, QoS). However, routing with multi-QoS constraints is a difficult problem for NP-, and the traditional algorithm can not solve the problem very well. Ant colony algorithm (AntColony Optimization, ACO) is an effective algorithm to deal with multi-constrained optimization problems. In this paper, ant colony algorithm is studied and applied to multi-constrained QoS routing problem in wireless Mesh networks. Mainly from the following two aspects: 1. Based on the analysis of the advantages and disadvantages of ant colony algorithm (ACA) applied to network QoS routing problems, a new ant colony multiple constrained QoS routing algorithm (IARQM.) is proposed, which is based on the promising hybrid structure of wireless Mesh networks. The algorithm takes into account the difference degree of the paths found to update the pheromone, which can effectively avoid the decrease of the searching ability caused by the local accumulation of the pheromone. At the same time, considering the important role of pheromone in routing, the algorithm provides a buffer recovery mechanism to retain the accumulated pheromones for temporary failure nodes and improve the robustness of the algorithm. In order to ensure the stability of the network, we adopt the method of routing which tends to be more stable router nodes. The IARQM algorithm is implemented in this paper, and the simulation results show that the algorithm has good performance and QoS guarantee ability. 2. In general, single-path routing protocol is used in wireless Mesh networks, but single-path routing protocol may cause network load imbalance, node congestion and so on. Therefore, on the basis of researching the existing multi-path routing based on ant colony algorithm (ACA), A parallel perturbed oriented ant colony multipath routing algorithm (PGARQ.PGARQ) is proposed in order to generate multi-paths with low correlation degree of nodes. Parallel processing is introduced into the algorithm and parallel paths are generated by using the high-speed computing and processing ability of parallel nodes. At the same time, the ant colony algorithm is easy to fall into the local optimal solution, combined with the directed local search algorithm improvement, and designed a perturbation way to further optimize the algorithm to solve the results. The experimental results show that PGARQ can quickly generate unrelated paths between nodes, improve computational accuracy and reduce computing time, thus ensuring the network QoS. better.
【學(xué)位授予單位】：南京航空航天大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2014
【分類號】：TP393.09;TP18

【參考文獻(xiàn)】

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

1 王小明;安小明;;具有能量和位置意識基于ACO的WSN路由算法[J];電子學(xué)報;2010年08期

2 程希;沈建華;;一種基于改進(jìn)蟻群算法的光網(wǎng)絡(luò)波長路由分配算法[J];電子與信息學(xué)報;2012年03期

3 王征應(yīng),石冰心;基于啟發(fā)式遺傳算法的QoS組播路由問題求解[J];計算機(jī)學(xué)報;2001年01期

4 王雪;王晟;馬俊杰;;無線傳感網(wǎng)絡(luò)移動節(jié)點(diǎn)位置并行微粒群優(yōu)化策略[J];計算機(jī)學(xué)報;2007年04期

5 秦勇;肖文俊;黃翰;梁本來;趙成貴;魏文紅;;一種基于QoS度量的Pareto并行路由尋優(yōu)方法[J];計算機(jī)學(xué)報;2009年03期

6 邢立寧;陳英武;;基于混合蟻群優(yōu)化的衛(wèi)星地面站系統(tǒng)任務(wù)調(diào)度方法[J];自動化學(xué)報;2008年04期

7 曹嘯;王汝傳;黃海平;孫力娟;肖甫;;無線多媒體傳感器網(wǎng)絡(luò)視頻流多路徑路由算法[J];軟件學(xué)報;2012年01期

8 宋超;劉明;龔海剛;陳貴海;王曉敏;;基于分布式實時信息的車載網(wǎng)絡(luò)路由協(xié)議[J];軟件學(xué)報;2011年03期

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

1 石勝林;基于無線Mesh網(wǎng)QoS關(guān)鍵技術(shù)研究[D];華中科技大學(xué);2011年

本文編號：2466416