基于遺傳算法的QoS組播路由問題研究.pdf

1、隨著Internet的飛速發(fā)展,涌現(xiàn)出許多新型的通信需求,如視頻點(diǎn)播、多媒體會議、遠(yuǎn)程教學(xué)等.這類應(yīng)用一般涉及多個用戶,需要網(wǎng)絡(luò)提供組播(Multicast)支持,并且保證服務(wù)質(zhì)量(QoS:Quality of Service).QoS組播路由是實(shí)現(xiàn)這類應(yīng)用的關(guān)鍵技術(shù)之一,因而成為研究熱點(diǎn),其目標(biāo)是尋找一棵連接源節(jié)點(diǎn)和多個目的節(jié)點(diǎn)的組播樹,使得樹的代價最小并且滿足各種QoS需求.QoS組播路由問題的求解方法包括啟發(fā)式算法和遺傳算法(GA

2、:Genetic Algorithm),該文主要研究了遺傳算法在組播路由問題中的應(yīng)用.遺傳算法是一種全局尋優(yōu)技術(shù),適合于在復(fù)雜而龐大的搜索空間中尋找最優(yōu)解,它原理簡單,易于并行,廣泛用于許多NP難題求解的領(lǐng)域.因此,遺傳算法為QoS組播路由問題的求解提供了新的途徑.針對時延受限的組播路由問題,該文提出了一種基于路徑編碼的改進(jìn)的遺傳算法,設(shè)定了有效的指數(shù)定標(biāo)技術(shù)和自適應(yīng)的變異策略,克服了早熟收斂.仿真試驗(yàn)表明,改進(jìn)的遺傳算法能夠以較少的遺

3、傳代數(shù)獲得代價較低且滿足時延約束的組播樹,具有較好的費(fèi)用性能和時間性能,能夠滿足實(shí)際應(yīng)用的要求.該文還將正交試驗(yàn)設(shè)計方法與遺傳算法相結(jié)合,提出了一種求解時延受限組播路由問題的正交遺傳算法.正交遺傳算法的優(yōu)點(diǎn)在于利用正交表的均勻分散性合理安排交叉方案,使得交叉算子在遺傳空間內(nèi)執(zhí)行的搜索更具有代表性,更容易發(fā)現(xiàn)性能優(yōu)良的個體,從而提高收斂速度.仿真試驗(yàn)對正交遺傳算法和改進(jìn)的遺傳算法進(jìn)行了比較,發(fā)現(xiàn)采用兩種算法求得的最優(yōu)組播樹的性能十分接近,