多約束QoS組播路由優(yōu)化與仿真.pdf

1、隨著視頻會議、視頻點(diǎn)播、遠(yuǎn)程教育等分布式實(shí)時業(yè)務(wù)的廣泛應(yīng)用，作為其核心技術(shù)的QoS組播技術(shù)引起了人們的高度重視。組播是一種有效的支持多點(diǎn)通信的機(jī)制，它采用樹轉(zhuǎn)發(fā)結(jié)構(gòu)，每一個數(shù)據(jù)包只在節(jié)點(diǎn)處被復(fù)制，在每一條鏈路上只發(fā)送一次。這種方法使IP組播能有效的同時向組內(nèi)的成員發(fā)送數(shù)據(jù)，并支持大量的組播組。QoS組播是在滿足帶寬、延遲、丟包率等多個QoS約束條件下進(jìn)行的組播。QoS組播路由技術(shù)是Internet上流媒體、視頻會議等高帶寬、共享型應(yīng)用的

2、重要基礎(chǔ)。 近幾年的研究表明，組播路由算法對組播應(yīng)用的QoS保障起到了非常關(guān)鍵的作用，對QoS組播路由算法的研究已經(jīng)成為網(wǎng)絡(luò)研究領(lǐng)域中的一個非常重要研究方向。在以往的研究中，QoS組播路由問題常歸結(jié)為最小費(fèi)用的約束斯坦立樹(Steiner Tree)問題，該問題已經(jīng)被證明是一個NP-C問題，不存在多項(xiàng)式時間的解法。隨著網(wǎng)絡(luò)規(guī)模的不斷擴(kuò)大和人們對網(wǎng)絡(luò)服務(wù)質(zhì)量要求的不斷提高，研究新的基于多約束的QoS組播路由算法，以獲得良好的網(wǎng)絡(luò)服

3、務(wù)質(zhì)量和高的網(wǎng)絡(luò)資源利用率，具有十分重要的意義。 本文在對蟻群優(yōu)化算法和組播問題作深入研究的基礎(chǔ)上，提出了可以解決Ad Hoc網(wǎng)絡(luò)上的QoS組播路由問題的帶方向因子的蟻群算法、基于樹的蟻群算法及其改進(jìn)算法： (1)目前，Ad Hoc網(wǎng)絡(luò)因其優(yōu)異的特性和特殊的應(yīng)用，受到越來越廣泛的重視。本文綜合考慮了Ad Hoc網(wǎng)絡(luò)的特性、已有的GPS定位技術(shù)以及蟻群算法本身的特點(diǎn)，在此基礎(chǔ)上提出了“方向因子”這個啟發(fā)式函數(shù)，并將方向因子

4、跟蟻群算法相結(jié)合，設(shè)計(jì)了帶方向因子的蟻群算法-ACA-O(Ant Colony Algorithm considering Orientation)，用以解決Ad Hoc網(wǎng)絡(luò)上的QoS組播問題。該算法使用方向因子來誘導(dǎo)螞蟻的搜索行為，使螞蟻能更加迅速地到達(dá)目的地，從而保證搜索的快速有效性，避免陷入局部最優(yōu)解。仿真實(shí)驗(yàn)結(jié)果表明，該算法提高了執(zhí)行速度，減少了信息包的發(fā)送量，節(jié)省了能量開銷。 (2)本文提出了一種基于樹的蟻群算法---

5、ACAT(Ant Colony Algorithmbased on Tree)。與傳統(tǒng)蟻群算法的先尋找路再合成樹的模式不同，ACAT采用了以樹生長的方式直接尋找組播樹的模式。基于樹的蟻群算法簡化了尋樹的機(jī)制，算法的效率得到了提高。仿真實(shí)驗(yàn)結(jié)果表明，跟傳統(tǒng)蟻群算法相比，ACAT算法能以更快的速度收斂到近似最優(yōu)解，組成員數(shù)目越多，這種優(yōu)點(diǎn)越明顯。 (3)專門針對Ad Hoc網(wǎng)絡(luò)，我們對基于樹的蟻群算法作了改進(jìn)，在原算法基礎(chǔ)上添加了重新定義的