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

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

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

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

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

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

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

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

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