基于蟻群算法的組播路由優(yōu)化與仿真.pdf

1、Internet網(wǎng)絡(luò)傳輸和處理能力的大幅提高使得基于網(wǎng)絡(luò)的應(yīng)用越來越多,如遠程教學、視頻會議、數(shù)據(jù)分發(fā)和網(wǎng)絡(luò)游戲等網(wǎng)絡(luò)多媒體應(yīng)用。這些多媒體應(yīng)用有著數(shù)據(jù)量大、時延要求高、持續(xù)時間長等特點,需要采用不同于傳統(tǒng)單播和廣播機制的轉(zhuǎn)發(fā)技術(shù)及服務(wù)質(zhì)量(QualityofService,簡稱QoS)保證機制來實現(xiàn),組播技術(shù)正是解決這個問題的理想方案。組播(Multicast)是一種有效的支持多點通信的機制,一般指的是一個或多個源節(jié)點向多個目的節(jié)點發(fā)

2、送信息的通信方式。它是指在IP網(wǎng)絡(luò)中將數(shù)據(jù)包以盡力傳送(best-effort)的形式發(fā)送到網(wǎng)絡(luò)中的某個確定節(jié)點子集,這個子集稱為組播組(MulticastGroup)。QOS是網(wǎng)絡(luò)在傳輸業(yè)務(wù)流時,業(yè)務(wù)流對網(wǎng)絡(luò)服務(wù)的需求的集合,其中業(yè)務(wù)流是指與特定QoS相關(guān)的從源到目的地的分組流。IETF已經(jīng)提出了多種服務(wù)模型和機制來滿足各種QoS組播的需求。實時應(yīng)用往往會對延時,延時抖動,帶寬,丟失率,業(yè)務(wù)代價等多個參數(shù)同時提出性能要求。這些參數(shù)相互

3、獨立時,選擇滿足多個參數(shù)限制的最優(yōu)組播路由就成為NP完全問題。
　　 本文在對組播問題和蟻群優(yōu)化算法作深入研究的基礎(chǔ)上,提出了可以解決組播路由問題的生長森林的蟻群優(yōu)化算法和可以分布式實現(xiàn)的蟻群優(yōu)化算法:
　　 (1)針對多播樹費用最小化問題,即Steiner樹問題,它是指使用樹最優(yōu)化函數(shù)構(gòu)建最優(yōu)的多播樹,本文提出一種可以解決Steiner樹問題的新的蟻群算法,生長森林的蟻群優(yōu)化算法。螞蟻行動過程中形成的是森林,每只螞蟻走

4、出的每一步都只是使當前的森林進一步生長,螞蟻行動的目標就是森林中所有的樹連接成一棵樹且這棵樹包含了所有的目標節(jié)點。本文分別使用SteinLabRepository中B類拓撲圖和MRSIM中的拓撲生成器生成的Waxman模型作為測試的拓撲,仿真試驗結(jié)果表明,算法的性能明顯優(yōu)于KMB、SPH、CDKS和傳統(tǒng)蟻群算法等生物啟發(fā)式算法。本算法在速度上與傳統(tǒng)蟻群算法、遺傳算法相比要快得多,并且在拓撲規(guī)模增大時,有更好的表現(xiàn)。此算法有效地解決了無約

5、束多播樹費用最小化問題。
　　 (2)對于多QoS約束的組播路由問題,本文提出了一種可以分布式實現(xiàn)的蟻群優(yōu)化算法,算法考慮了多種QoS約束條件,包括帶寬、延遲、延遲抖動和丟包率。在此算法中螞蟻行動過程中形成的是組播樹的森林。在開始時森林中只有源節(jié)點和目的節(jié)點。螞蟻走出一步是使森林中的每棵樹都選擇一條邊加入。若某一步結(jié)束時森林中僅剩下一棵樹,則螞蟻達到目標,停止行動。算法最為重要的一個優(yōu)點是可以分布式實現(xiàn)。仿真結(jié)果表明算法在尋優(yōu)能