計算機網(wǎng)絡(luò)中的多QoS約束組播路由算法.pdf

1、QoS組播路由是給定一個源節(jié)點s，一組目的節(jié)點集D，一系列QoS限制條件C，以及可能的優(yōu)化目標(biāo)，尋找滿足C的覆蓋s和D中所有節(jié)點的最好的有效樹，這是一個NP完全問題。 當(dāng)前多數(shù)QoS組播路由研究集中在下面的幾個問題：帶寬受限組播路由：延遲受限組播路由；延遲受限最小代價組播路由；時延一時延抖動受限組播路由。求解該類問題是一個NP完全問題，不存在確定型多項式復(fù)雜性解法。目前都采用啟發(fā)式算法來解決，當(dāng)前提出的啟發(fā)式算法十分復(fù)雜而難以求

2、解，該類問題是學(xué)術(shù)界的研究熱點。 本文提出了用正交試驗，找出蟻群算法各個參數(shù)最佳組合。從蟻群搜索最短路徑的機理看到，算法中有關(guān)參數(shù)的不同選擇對蟻群算法的性能有至關(guān)重要的影響，但其選取的方法和原則，目前尚沒有理論上的依據(jù)，通常都是根據(jù)經(jīng)驗而定。本文通過一系列的對比實驗研究，來探討蟻群算法中參數(shù)的最佳設(shè)定原則。首先，讓一個參數(shù)變化其他參數(shù)不變，進行仿真實驗，找出這個參數(shù)最佳值范圍；然后，各個參數(shù)在其最佳值范圍內(nèi)，選取若干個值，進行正

3、交試驗，找出最佳組合。 本文提出了一種新的改進蟻群算法，通過構(gòu)建確定性選路概率函數(shù)和基于交叉變異的變異操作，加速算法的收斂速度；對信息素實行多個獨立OoS約束的懲罰性更新策略，使算法滿足用戶的OoS要求；考慮到網(wǎng)絡(luò)實際應(yīng)用，算法設(shè)計中引進了基于鏈路利用率的負載均衡和擁塞規(guī)避重路由策略，提高算法的魯棒性。實驗表明，應(yīng)用這種改進型蟻群算法于多播路由問題，可以得到比現(xiàn)有啟發(fā)式算法更好的結(jié)果。 本文同時提出將改進的蟻群算法和免疫