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

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

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

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

4、出的每一步都只是使當(dāng)前的森林進(jìn)一步生長(zhǎng),螞蟻行動(dòng)的目標(biāo)就是森林中所有的樹(shù)連接成一棵樹(shù)且這棵樹(shù)包含了所有的目標(biāo)節(jié)點(diǎn)。本文分別使用SteinLabRepository中B類拓?fù)鋱D和MRSIM中的拓?fù)渖善魃傻腤axman模型作為測(cè)試的拓?fù)?仿真試驗(yàn)結(jié)果表明,算法的性能明顯優(yōu)于KMB、SPH、CDKS和傳統(tǒng)蟻群算法等生物啟發(fā)式算法。本算法在速度上與傳統(tǒng)蟻群算法、遺傳算法相比要快得多,并且在拓?fù)湟?guī)模增大時(shí),有更好的表現(xiàn)。此算法有效地解決了無(wú)約

5、束多播樹(shù)費(fèi)用最小化問(wèn)題。
　　 (2)對(duì)于多QoS約束的組播路由問(wèn)題,本文提出了一種可以分布式實(shí)現(xiàn)的蟻群優(yōu)化算法,算法考慮了多種QoS約束條件,包括帶寬、延遲、延遲抖動(dòng)和丟包率。在此算法中螞蟻行動(dòng)過(guò)程中形成的是組播樹(shù)的森林。在開(kāi)始時(shí)森林中只有源節(jié)點(diǎn)和目的節(jié)點(diǎn)。螞蟻?zhàn)叱鲆徊绞鞘股种械拿靠脴?shù)都選擇一條邊加入。若某一步結(jié)束時(shí)森林中僅剩下一棵樹(shù),則螞蟻達(dá)到目標(biāo),停止行動(dòng)。算法最為重要的一個(gè)優(yōu)點(diǎn)是可以分布式實(shí)現(xiàn)。仿真結(jié)果表明算法在尋優(yōu)能