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

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

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

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

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