基于計算智能的多播QoS路由技術(shù)研究.pdf

1、隨著群組通信特別是網(wǎng)絡(luò)視頻會議、網(wǎng)絡(luò)視頻點播、股市行情發(fā)布、遠(yuǎn)程教育等應(yīng)用大量興起,多播技術(shù)已成為支持這些應(yīng)用的重要基礎(chǔ)。由于這些實時業(yè)務(wù)對網(wǎng)絡(luò)傳輸中的時延、時延抖動、帶寬、包丟失率和代價等較為敏感,當(dāng)突發(fā)性較高的多媒體業(yè)務(wù)數(shù)據(jù)在網(wǎng)絡(luò)上傳輸時,其傳輸質(zhì)量將會受到影響,這樣就需要服務(wù)質(zhì)量(QualityofService,QoS)技術(shù)的支持,以確保實時業(yè)務(wù)的通信質(zhì)量。傳統(tǒng)的基于“最短路徑”算法的路由技術(shù)只提供“盡力而為”服務(wù),不能提供Qo

2、S保證。隨著下一代高性能網(wǎng)絡(luò)技術(shù)的不斷發(fā)展及其應(yīng)用領(lǐng)域的日益擴大,基于QoS約束的多播路由算法和協(xié)議的理論研究與實現(xiàn),已成為網(wǎng)絡(luò)研究領(lǐng)域中的重要課題。多播作為多點之間的通信服務(wù),其服務(wù)質(zhì)量問題較端對端應(yīng)用更復(fù)雜、更困難。多播QoS問題的研究包括接納控制、路由選擇、群組成員關(guān)系管理、擁塞控制、流量整形、協(xié)商機制等,而路由選擇問題是其中最關(guān)鍵的課題。多播QoS路由就是尋找滿足特定QoS約束的一棵多播樹,這已被證明是一個NP完全問題。雖然針對

3、該問題,學(xué)界已提出了不少算法,但普遍存在著算法復(fù)雜、實現(xiàn)困難、算法適應(yīng)性差、難以滿足多播應(yīng)用動態(tài)性的特點。近年來,研究人員引入計算智能算法尋求多播QoS路由問題的最優(yōu)解。但是單純采用某種計算智能算法的多播路由方案也存在局限性。特別需要指出的是,把各種不同的計算智能方法結(jié)合起來,形成優(yōu)勢互補、復(fù)合協(xié)同的集成優(yōu)化方法,已經(jīng)成為計算智能優(yōu)化技術(shù)領(lǐng)域的主流方向。本論文主要研究目的在于,深入研究多種計算智能技術(shù)進(jìn)行綜合集成的理論方法,并將其用于解

4、決多播QoS路由計算問題。本論文著重圍繞帶QoS約束的多播路由樹構(gòu)造問題進(jìn)行深入研究。針對目前多播路由樹構(gòu)造方法的不足之處,將QoS約束的多播樹構(gòu)造問題轉(zhuǎn)化為多目標(biāo)優(yōu)化問題,然后采用基于計算智能的多目標(biāo)優(yōu)化技術(shù)尋求該問題的解決方案。力爭為解決多播QoS路由綜合優(yōu)化這類復(fù)雜問題探索一條新的途徑。本論文研究內(nèi)容如下:根據(jù)多目標(biāo)優(yōu)化的思想,設(shè)計出集中式的,基于改進(jìn)遺傳算法的滿足QoS約束的靜態(tài)多播路由算法。文中提出了兩種基于進(jìn)化計算的靜態(tài)多播

5、QoS路由計算方法,分別是基于啟發(fā)式模糊遺傳算法的多播路由算法和基于種群自適應(yīng)免疫遺傳算法的多播QoS路由算法。兩種算法都采用樹形結(jié)構(gòu)編碼及高效的遺傳操作,而且是從不同的角度對傳統(tǒng)遺傳算法進(jìn)行改進(jìn),前者是在傳統(tǒng)遺傳算法中引入模糊選擇機制與禁忌搜索(TS)算子,采用禁忌搜索算子可以保證多樣化的有效搜索。而模糊選擇機制可被用來確定最優(yōu)數(shù)量的個體參與遺傳操作,可用它代替常用的賭輪選擇操作;后者則是首先采用自適應(yīng)規(guī)則,對遺傳算法的重要參數(shù)隨種群

6、進(jìn)化的需要進(jìn)行自適應(yīng)調(diào)整。然后再引入免疫算子,使得算法在保證群體多樣性的同時能夠得到Pareto最優(yōu)解。兩種算法都力圖克服單純采用遺傳算法的爬山能力差以及早熟問題。此外后者算法能更為近似地模擬自然界及生物個體競爭、繁衍和死亡的過程,具有較好的空間探索能力和局部求精能力。從而更好的改進(jìn)多目標(biāo)進(jìn)化算法的搜索性能;針對集中式多播路由算法適應(yīng)網(wǎng)絡(luò)規(guī)模的擴展性能較差和計算負(fù)荷重的局限性,本論文提出一種基于協(xié)同進(jìn)化蟻群算法的全局分布式多播QoS路由

7、計算方法。首先為各個種群分配一個目標(biāo),在這里是搜索到特定目的節(jié)點的滿足QoS約束的最優(yōu)路徑。然后采用本文設(shè)計的方法將各種群的最優(yōu)解合并為滿足QoS約束的多播樹路徑,并用Pareto最優(yōu)性準(zhǔn)則進(jìn)行評價,據(jù)此進(jìn)行信息激素的獎勵或懲罰。該算法是完全的分布式算法,具有搜索成功率高和擴展性好等特點;針對在多播成員動態(tài)變化及網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)動態(tài)變化的環(huán)境中的多播路由樹的建立和調(diào)整等問題,本文提出結(jié)合分布式和集中式特點的動態(tài)多播路由算法,在新節(jié)點加入多播

8、會話時,采用分布式的方法搜索新節(jié)點到當(dāng)前多播樹的滿足QoS約束的最優(yōu)路徑。而在成員節(jié)點離開多播會話時,則根據(jù)其對多播會話質(zhì)量的影響程度,決定是否執(zhí)行多播樹的重構(gòu)操作。與靜態(tài)多播路由算法比較,動態(tài)多播路由算法具有更好的適應(yīng)性和靈活性。本論文針對近來出現(xiàn)的應(yīng)用層多播技術(shù)也進(jìn)行了深入的分析研究。針對覆蓋網(wǎng)絡(luò)多播樹的構(gòu)建問題,本文提出了基于混沌免疫進(jìn)化算法的覆蓋網(wǎng)絡(luò)多播路由方案。通過將網(wǎng)絡(luò)層業(yè)務(wù)的均衡程度納入路由算法優(yōu)化目標(biāo),分析覆蓋網(wǎng)絡(luò)多播樹