基于遺傳模擬退火算法的QoS組播路由研究.pdf

1、隨著Internet的發(fā)展，多媒體通信和分布式環(huán)境下的協(xié)同工作等應(yīng)用促進(jìn)了組播通信的發(fā)展。組播問(wèn)題的關(guān)鍵在于組播路由的確定，即尋找簡(jiǎn)單、高效、健壯的組播路由算法。組播路由算法主要是用來(lái)建立一棵性能良好的組播樹(shù)，并使它能夠滿足各種業(yè)務(wù)的服務(wù)質(zhì)量(QoS)需求。QoS組播路由帶有多個(gè)QoS約束參數(shù)，而這種約束條件下的QoS組播路由問(wèn)題屬于NP完全問(wèn)題。對(duì)于QoS組播路由問(wèn)題的研究大都集中在采用啟發(fā)式算法進(jìn)行求解，然而由于這些算法都具有較高的

2、時(shí)間復(fù)雜度而不能滿足實(shí)際應(yīng)用的需求。本文針對(duì)遺傳算法的局限性，將遺傳算法與模擬退火算法相結(jié)合提出了一種新型的遺傳模擬退火算法，利用該遺傳模擬退火算法作為求解QoS組播路由問(wèn)題的優(yōu)化算法，主要研究了三類(lèi)典型的QoS組播路由問(wèn)題。 首先，針對(duì)遺傳算法的局限性，對(duì)適應(yīng)度函數(shù)進(jìn)行調(diào)整，實(shí)施最優(yōu)保留策略，改進(jìn)了交叉和變異操作，并結(jié)合模擬退火算法，提出了一種基于遺傳模擬退火算法的時(shí)延約束費(fèi)用最小組播路由選擇方法。 其次，提出了一種時(shí)

3、延及時(shí)延差約束組播路由算法，該方法采用基于備選路徑集的整數(shù)隊(duì)列編碼機(jī)制，應(yīng)用啟發(fā)式交叉和變異策略，用模擬退火算法對(duì)遺傳操作的子代個(gè)體進(jìn)行優(yōu)化，加快算法收斂速度。 最后，對(duì)帶寬、時(shí)延、時(shí)延抖動(dòng)和包丟失率約束費(fèi)用最小組播路由問(wèn)題進(jìn)行了研究，定義了研究組播路由問(wèn)題的網(wǎng)絡(luò)模型，提出了一種基于遺傳模擬退火算法的多約束QoS組播路由算法。 仿真實(shí)驗(yàn)表明，上述三種組播路由算法收斂速度快，具有較好的性能，能夠滿足多媒體網(wǎng)絡(luò)對(duì)相應(yīng)QoS的