基于混合遺傳算法的多約束QoS組播算法的研究.pdf

1、近些年來，由于互聯(lián)網(wǎng)技術的迅猛發(fā)展以及通信網(wǎng)絡帶寬和處理能力的大幅提高，使得網(wǎng)絡能夠提供形式多樣的多媒體業(yè)務，同時也使得支持“點對多點”或“多點對多點”的組播通信方式成為網(wǎng)絡支持多媒體業(yè)務的必要形式。組播路由作為多媒體網(wǎng)絡的核心技術，其研究范圍包括路由協(xié)議、路由策略、路由算法等多個方面，而組播問題的關鍵在于組播路由的確定，所以尋找簡單、高效、健壯的組播路由算法一直是網(wǎng)絡界致力研究但未完全解決的問題。
　　許多分布式的多媒體應用對延

2、時、延時抖動、帶寬以及包丟失率有不同的要求，而帶有多個QoS約束參數(shù)的QoS組播路由問題屬于NP完全問題。對于QoS組播路由問題的研究大都集中在采用啟發(fā)式算法進行求解，然而由于這些算法要么具有較高的時間復雜度而不能滿足實際應用的需求，要么算法早熟收斂，陷入局部，不能求出全局最優(yōu)解。因此，基于多約束QoS的組播路由算法的研究成為網(wǎng)絡研究領域的重要內(nèi)容和熱點問題。
　　遺傳算法是一種全局優(yōu)化搜索算法，具有簡單通用，魯棒性強和并行處理以

3、及應用范圍廣等顯著特點，其缺點是容易早熟，陷入局部最優(yōu)解，后期爬山能力弱。模擬退火算法是一種局部搜索能力極強的全局搜索算法，它采用Metropolis準則從而能夠跳出局部達到全局最優(yōu)解，其主要缺點是解的質量與求解時間長短之間的矛盾。本文正是在總結了這兩種算法的優(yōu)缺點的基礎上提出了一種新型的混合遺傳算法。首先，采用基于備選路徑集的整數(shù)隊列編碼機制有效減少了編解碼的工作量，并針對遺傳算法的局限性，對適應度函數(shù)進行了調整，實施最優(yōu)保留策略，應

4、用啟發(fā)式交叉和變異策略。其次，用模擬退火算法對遺傳操作的子代個體進行優(yōu)化，采用“路徑交換”策略在可行解范圍內(nèi)構造鄰域解集，避免了搜索區(qū)域的擴大和計算時間的增加，加快了算法的收斂速度。最后，利用海明算子提高算法對解空間的覆蓋度，利用入侵算子保證種群的健壯性，利用重升溫算子強化算法的局部搜索能力。
　　本文中，在參考Salama模型基礎上利用K均值聚類算法保證節(jié)點分布接近真實情況，設計了一種簡單有效的網(wǎng)絡仿真環(huán)境，對提出的算法進行仿真