基于改進(jìn)蟻群優(yōu)化的組播路由算法研究.pdf

1、隨著網(wǎng)絡(luò)技術(shù)的飛速發(fā)展，網(wǎng)絡(luò)通信帶寬和處理能力的不斷提高，各種寬帶網(wǎng)絡(luò)多媒體應(yīng)用層出不窮，如視頻點(diǎn)播、視頻會(huì)議、網(wǎng)絡(luò)電話、交互式游戲、遠(yuǎn)程教育、分布式多媒體數(shù)據(jù)庫等，這些應(yīng)用對帶寬、延時(shí)、延時(shí)抖動(dòng)、丟包率、費(fèi)用等較為敏感，需要QoS(服務(wù)質(zhì)量)的保證。當(dāng)前Internet發(fā)展迅速，節(jié)點(diǎn)數(shù)成指數(shù)級增長，而且網(wǎng)絡(luò)傳輸正在向大容量、高速化、多媒體化方向發(fā)展，傳統(tǒng)的“盡力而為”的服務(wù)已經(jīng)不能滿足這些新興業(yè)務(wù)提出的要求。
　　 組播是一種

2、有效的支持多點(diǎn)通信的機(jī)制，可以將同一信息從源節(jié)點(diǎn)傳送到網(wǎng)絡(luò)中多個(gè)目的節(jié)點(diǎn)(不一定是網(wǎng)絡(luò)中所有結(jié)點(diǎn))。由于組播樹中路由器的復(fù)制和轉(zhuǎn)發(fā)，相對于單播傳輸方式，組播發(fā)送數(shù)據(jù)流到一組目的節(jié)點(diǎn)源節(jié)點(diǎn)只需產(chǎn)生發(fā)送一份數(shù)據(jù)流，因而組播技術(shù)具有緩解網(wǎng)絡(luò)傳輸瓶頸和減輕主機(jī)處理壓力的特點(diǎn)，有效提高傳輸效率，得到了廣泛的應(yīng)用。組播問題的關(guān)鍵是確定組播路由，QoS組播路由就是尋找一棵滿足特定QoS約束的組播樹，這已被證明是一個(gè)NP完全問題，用常規(guī)的方法難以求解，

3、因而需要應(yīng)用到啟發(fā)式算法。蟻群算法作為一種新型的模擬進(jìn)化算法，具有穩(wěn)健性、正反饋、本質(zhì)上的并行性、易于與其他算法相結(jié)合等特點(diǎn)，是解決多QoS約束組播路由問題的一種較好的啟發(fā)式算法。
　　 本文首先列舉了現(xiàn)有的組播路由協(xié)議及算法的分類，分析了幾種經(jīng)典QoS路由算法，提出組播路由研究中仍存在的問題。接著介紹了蟻群算法的基本原理和算法的數(shù)學(xué)模型，通過對Oliver30城市的TSP問題實(shí)驗(yàn)分析了蟻群算法中各參數(shù)對算法性能的影響。針對蟻群

4、算法收斂速度慢和容易局部收斂的問題，對蟻群算法進(jìn)行了優(yōu)化，提出參數(shù)按算法迭代結(jié)果自適應(yīng)調(diào)整；修改基本蟻群算法中信息素的更新規(guī)則，使得每輪搜索后信息素的增量能更好地反映解的質(zhì)量以加快收斂；對所選的下一節(jié)點(diǎn)進(jìn)行判定，防止源節(jié)點(diǎn)到目的節(jié)點(diǎn)子圖中形成環(huán)路；考慮到蟻群種類差異和行為差異，引入具有多行為的混合螞蟻來擴(kuò)大解搜索空間等改進(jìn)策略。
　　 最后將改進(jìn)蟻群算法應(yīng)用于QoS組播路由問題，并對其進(jìn)行仿真實(shí)驗(yàn)，結(jié)果表明算法的可行性和有效性。