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

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

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

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

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