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

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

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

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