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

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

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

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

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