蟻群算法在聚合組播優(yōu)化中的應(yīng)用研究.pdf

1、伴隨著互聯(lián)網(wǎng)的蓬勃發(fā)展,IPV6和物聯(lián)網(wǎng)的實(shí)施已經(jīng)將網(wǎng)絡(luò)節(jié)點(diǎn)擴(kuò)展到生活的各個(gè)角落,而網(wǎng)絡(luò)的多點(diǎn)通信應(yīng)用離不開(kāi)組播技術(shù)的支持。
　　 在傳統(tǒng)的組播中,為每個(gè)組播組建立一棵組播樹(shù)來(lái)分發(fā)數(shù)據(jù)包,同時(shí)為這棵組播樹(shù)分配一個(gè)組播地址,組播樹(shù)上的每個(gè)路由器需要維護(hù)組播的轉(zhuǎn)發(fā)狀態(tài)。當(dāng)網(wǎng)絡(luò)中存在大量的并發(fā)組播組的時(shí)候,相應(yīng)的組播樹(shù)也會(huì)隨之急劇的增加,這些組播樹(shù)不僅降低了組播地址的查詢速度,而且維護(hù)著數(shù)量龐大的組播狀態(tài)轉(zhuǎn)發(fā)表,需要消耗大量的內(nèi)存和C

2、PU資源。在網(wǎng)絡(luò)中,組播組是動(dòng)態(tài)變化的,有組成員加入和離開(kāi)時(shí),組播樹(shù)會(huì)進(jìn)行更新,因此對(duì)于組播樹(shù)的控制和管理是一個(gè)開(kāi)銷非常大的事情。所有這些后果都來(lái)自于組播狀態(tài)的可擴(kuò)展問(wèn)題,它使得網(wǎng)絡(luò)的性能急劇下降,成為組播應(yīng)用大規(guī)模部署的重要瓶頸。
　　 針對(duì)組播狀態(tài)的可擴(kuò)展性問(wèn)題,UCLA大學(xué)網(wǎng)絡(luò)實(shí)驗(yàn)室提出了聚合組播的解決方案,該方案強(qiáng)迫具有相近形狀原始組播樹(shù)的若干個(gè)組播組共享同一棵大型組播樹(shù),這樣能夠有效減少網(wǎng)絡(luò)中組播樹(shù)的數(shù)目,減少轉(zhuǎn)發(fā)的組

3、播狀態(tài)數(shù)量,降低資源的消耗和維護(hù)和管理組播樹(shù)的開(kāi)銷。聚合組播的主要思想是在給定的帶寬浪費(fèi)閾值的約束下建立能夠覆蓋所有組播組的數(shù)目最少的聚合組播樹(shù)。已有的聚合組播優(yōu)化算法有Greedy算法和Genetic算法,為聚合組播理論的發(fā)展做出了重要的貢獻(xiàn)。
　　 本文在對(duì)已有的聚合組播優(yōu)化算法的研究基礎(chǔ)上,提出了一種基于擾動(dòng)因子的蟻群算法來(lái)減少組播樹(shù)的數(shù)目,而且為了加快蟻群的算法的收斂速度,還提出了一種蟻群算法的并行計(jì)算模式。
　　

4、 1.基于擾動(dòng)因子的蟻群算法是對(duì)蟻群系統(tǒng)和最大-最小蟻群兩種算法的改進(jìn)。在該算法中,每次循環(huán)完成之后,不僅對(duì)最優(yōu)聚合組播樹(shù)的集合進(jìn)行信息素的更新,而且也對(duì)隨機(jī)產(chǎn)生的次優(yōu)的聚合組播樹(shù)的集合進(jìn)行更新。通過(guò)引入隨機(jī)的次優(yōu)解這個(gè)干擾因子,可以增加解的多樣性,防止過(guò)早陷入局部最優(yōu)的泥淖中。
　　 仿真實(shí)驗(yàn)表明,蟻群算法的性能超過(guò)了貪心算法。貪心算法的啟發(fā)式信息過(guò)于簡(jiǎn)單,搜索的解的空間范圍狹窄,而蟻群算法使用信息素來(lái)標(biāo)記最優(yōu)解,多付出了時(shí)