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

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

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

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