基于改進蟻群算法的QoS組播路由問題研究.pdf

1、蟻群算法是基于螞蟻群體覓食過程中，具有找到蟻穴與食物源之間最短路徑的能力，這一生物學行為發(fā)展起來的一種群智能優(yōu)化方法。它最初用于解決旅行商(TSP)問題，具有自適應性、魯棒性及本質(zhì)上的并行性等許多特點。該算法的出現(xiàn)引起了學者們的巨大關注，在過去的短短十余年時間內(nèi)，蟻群算法已經(jīng)在組合優(yōu)化、函數(shù)優(yōu)化、系統(tǒng)辨識、網(wǎng)絡路由、機器人路徑規(guī)劃、數(shù)據(jù)挖掘以及大規(guī)模集成電路的綜合布線設計等領域獲得了廣泛的應用，并取得了較好的效果。 組播路由問題

2、是隨著互聯(lián)網(wǎng)的迅猛發(fā)展衍生出的系列問題之一，隨著群組通信特別是網(wǎng)絡視頻會議、網(wǎng)絡視頻點播、股市行情發(fā)布、遠程教育等應用大量興起，組播技術已成為支持這些應用的重要基礎。由于這些實時業(yè)務對網(wǎng)絡傳輸中的時延、帶寬、代價等較為敏感，當突發(fā)性較高的多媒體業(yè)務數(shù)據(jù)在網(wǎng)絡上傳輸時，其傳輸質(zhì)量將會受到影響，這樣就需要服務質(zhì)量技術的支持，以確保實時業(yè)務的通信質(zhì)量。傳統(tǒng)“盡力而為”服務，不能滿足網(wǎng)絡用戶的需求。組播QoS路由就是尋找滿足特定QoS約束的一棵

3、組播樹，這已被證明是一個NP完全問題。雖然針對該問題，學術界已提出了不少算法，但普遍存在著算法復雜、實現(xiàn)困難、算法適應性差、難以滿足組播應用的需求等特點。因而需要運用到啟發(fā)式算法。 本文首先總結(jié)了現(xiàn)有的組播路由協(xié)議及算法分類，分析QoS度量以及QoS組播路由問題的模型和分類。列舉了蟻群算法的研究進展、思想起源和優(yōu)缺點，給出了基于蟻群算法的QoS組播路由算法的描述和步驟并進行分析。隨后，在此基礎上結(jié)合模擬退火算法的特點：在搜索最優(yōu)

4、解的過程中，以一定的概率接受劣解。將模擬退火算法思想與蟻群算法相結(jié)合，生成基于模擬退火思想的逆向螞蟻。逆向螞蟻在選擇路徑時，按照信息素濃度高的路徑被選中的概率小的規(guī)則。因此在探討基于模擬退火思想的逆向蟻群算法解決QoS組播路由問題時，通過在算法初期引入逆向螞蟻以增強搜索的隨機性，增加搜索的遍歷性，避免算法過早收斂進入停滯狀態(tài)，陷入局部最優(yōu)。隨著迭代的進行，逐漸減少逆向螞蟻數(shù)量，從而加快算法的收斂速度。 通過應用改進的Waxman