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

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

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

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

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