基于遺傳算法的QoS組播路由算法的研究與實現(xiàn).pdf

1、隨著網(wǎng)絡(luò)技術(shù)的飛速發(fā)展，各種實時和多媒體業(yè)務(wù)得到了越來越廣泛的應(yīng)用。一方面，這些業(yè)務(wù)大多采用組播來降低網(wǎng)絡(luò)負載，提高網(wǎng)絡(luò)資源的利用率；另一方面，這些業(yè)務(wù)都是一些實時性很強的業(yè)務(wù)，需要提供QoS保障。 在滿足QoS的條件下，尋找將分組發(fā)送到一個組播組中所有成員的路徑的過程稱為QoS組播路由。研究表明，QoS組播路由問題是一個NP完全問題，這使得它與傳統(tǒng)的路由過程不同，難以用經(jīng)典的最短路徑優(yōu)先算法求解。以前，許多研究都集中在采用啟發(fā)

2、式算法來求解該問題，然而由于這些算法都具有較高的時間復雜度而不能滿足實際應(yīng)用的需要。 本文采用基于遺傳算法的QoS組播路由算法來求解該問題。遺傳算法是一種新型的優(yōu)化算法，己經(jīng)廣泛應(yīng)用于解決各種具有NP難度的問題。本算法通過改進遺傳算法的結(jié)構(gòu)，使其避免陷入局部極值的能力大大增強；采用樹型結(jié)構(gòu)編碼策略，既減少了編碼空間，又省略了解碼操作；采用多點交叉，提高了交叉策略的性能；對強成長的個體進行變異操作，即能讓多個個體進行局部搜索，形成