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

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

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