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

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

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

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

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

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