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

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

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

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

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

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

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

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

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