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

來源：互聯(lián)網(wǎng)   發(fā)布日期：2011-09-18 20:07:01   瀏覽：10104次  

蟻群算法是基于螞蟻群體覓食過程中，具有找到蟻穴與食物源之間最短路徑的能力，這一生物學(xué)行為發(fā)展起來的一種群智能優(yōu)化方法。它最初用于解決旅行商(tsp)問題，具有自適應(yīng)性、魯棒性及本質(zhì)上的并行性等許多特點(diǎn)。該算法的出現(xiàn)引起了學(xué)者們的巨大關(guān)注，在過去的短短十余年時(shí)間內(nèi)，蟻群算法已經(jīng)在組合優(yōu)化、函數(shù)優(yōu)化、系統(tǒng)辨識(shí)、網(wǎng)絡(luò)路由、機(jī)器人路徑規(guī)劃、數(shù)據(jù)挖掘以及大規(guī)模集成電路的綜合布線設(shè)計(jì)等領(lǐng)域獲得了廣泛的應(yīng)用，并取得了較好的效果。 組播路由問題是隨著互聯(lián)網(wǎng)的迅猛發(fā)展衍生出的系列問題之一，隨著群組通信特別是網(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ù)，不能滿足網(wǎng)絡(luò)用戶的需求。組播qos路由就是尋找滿足特定qos約束的一棵組播樹，這已被證明是一個(gè)np完全問題。雖然針對(duì)該問題，學(xué)術(shù)界已提出了不少算法，但普遍存在著算法復(fù)雜、實(shí)現(xiàn)困難、算法適應(yīng)性差、難以滿足組播應(yīng)用的需求等特點(diǎn)。因而需要運(yùn)用到啟發(fā)式算法。 本文首先總結(jié)了現(xiàn)有的組播路由協(xié)議及算法分類，分析qos度量以及qos組播路由問題的模型和分類。列舉了蟻群算法的研究進(jìn)展、思想起源和優(yōu)缺點(diǎn)，給出了基于蟻群算法的qos組播路由算法的描述和步驟并進(jìn)行分析。隨后，在此基礎(chǔ)上結(jié)合模擬退火算法的特點(diǎn)：在搜索最優(yōu)解的過程中，以一定的概率接受劣解。將模擬退火算法思想與蟻群算法相結(jié)合，生成基于模擬退火思想的逆向螞蟻。逆向螞蟻在選擇路徑時(shí)，按照信息素濃度高的路徑被選中的概率小的規(guī)則。因此在探討基于模擬退火思想的逆向蟻群算法解決qos組播路由問題時(shí)，通過在算法初期引入逆向螞蟻以增強(qiáng)搜索的隨機(jī)性，增加搜索的遍歷性，避免算法過早收斂進(jìn)入停滯狀態(tài)，陷入局部最優(yōu)。隨著迭代的進(jìn)行，逐漸減少逆向螞蟻數(shù)量，從而加快算法的收斂速度。 通過應(yīng)用改進(jìn)的waxman隨機(jī)網(wǎng)絡(luò)生成方法，生成了仿真隨機(jī)網(wǎng)絡(luò)，并對(duì)基于模擬退火思想的逆向蟻群算法和基于常規(guī)蟻群算法的qos組播路由問題進(jìn)行仿真實(shí)驗(yàn)，將兩種算法產(chǎn)生的結(jié)果進(jìn)行對(duì)比，分析得出：逆向蟻群算法在收斂性、穩(wěn)定性、魯棒性和網(wǎng)絡(luò)性能代價(jià)等方面都有較好的效果。最后，對(duì)qos組播路由算法的研究提出了一些建議。

贊助本站