萬曙靜+浩慶波+徐巖

摘 要

QoS組播路由技術(shù)作為網(wǎng)絡(luò)多媒體信息傳輸?shù)囊环N核心技術(shù)，下一代網(wǎng)絡(luò)中的QoS組播路由的優(yōu)化算法已經(jīng)成為目前研究的一個(gè)熱點(diǎn)。針對QoS組播的網(wǎng)絡(luò)模型，提出一種適用于下一代網(wǎng)絡(luò)的組播路由算法能夠更好的滿足下一代網(wǎng)絡(luò)的QoS組播需求顯得尤為重要。本文討論了遺傳算法優(yōu)化的QoS組播路由算法，最后探討了下一代網(wǎng)絡(luò)QoS組播路由算法的研究方向。

【關(guān)鍵詞】遺傳算法 組播路由 優(yōu)化算法

1 引言

目前的QoS研究主要是在IP網(wǎng)絡(luò)中進(jìn)行的，針對資源預(yù)留和擁塞控制等方面的研究。組播技術(shù)以數(shù)據(jù)源節(jié)點(diǎn)作為根節(jié)點(diǎn)，根據(jù)各種數(shù)據(jù)傳輸約束和網(wǎng)絡(luò)結(jié)構(gòu)在多個(gè)目的節(jié)點(diǎn)間構(gòu)建一棵組播路由樹。源節(jié)點(diǎn)到多個(gè)目的節(jié)點(diǎn)的鏈路共享組播路由樹，使得各中間節(jié)點(diǎn)減少了復(fù)制信息的數(shù)量，進(jìn)而節(jié)約了對寶貴的網(wǎng)絡(luò)資源的使用。我們通常通過求解斯泰納最小樹MST來求解代價(jià)最小的組播樹，這一問題已被證明是NP完全問題。采用的方法多為啟發(fā)式，例如SPH算法，KPP算法。上述算法的精度差一些，且收斂性能不好。啟發(fā)式算法存在算法的復(fù)雜度大等問題。針對上述問題，本文提出了借助于遺傳算法來優(yōu)化組播路由算法，以提高組播路由算法的效率。

2 網(wǎng)絡(luò)模型

為更好的表述組播路由問題，引入一個(gè)有向賦權(quán)圖G=（V，E）描述計(jì)算機(jī)網(wǎng)絡(luò)，V代表節(jié)點(diǎn)集，E代表連接不同節(jié)點(diǎn)的通信鏈路集。對通信鏈路集中的每條鏈路都定義三個(gè)正實(shí)數(shù)加權(quán)值（Bij，Cij，Dij）。其中Bij表示由節(jié)點(diǎn)i到節(jié)點(diǎn)j傳送數(shù)據(jù)的帶寬，Cij則表示由節(jié)點(diǎn)i到節(jié)點(diǎn)j傳送數(shù)據(jù)的代價(jià)，即通信鏈路資源的使用狀況；Dij代表傳送數(shù)據(jù)的時(shí)延。為了簡化問題，假設(shè)節(jié)點(diǎn)i到節(jié)點(diǎn)j的邊和節(jié)點(diǎn)j到節(jié)點(diǎn)i的邊上的權(quán)值相等，因此有。為不失一般性，假設(shè)網(wǎng)絡(luò)中一對節(jié)點(diǎn)之間最多存在一條鏈路。

假設(shè)數(shù)據(jù)信息從源節(jié)點(diǎn)需要發(fā)送到一組目的節(jié)點(diǎn)。組播樹為，其中，，且T中存在通路由源節(jié)點(diǎn)到達(dá)目的節(jié)點(diǎn)。組播路由樹需要滿足如下條件：

3 基于遺傳算法優(yōu)化的組播路由算法

遺傳算法（Genetic Algorithm，GA）是由美國Michigan大學(xué)的Holland提出的，是一種模擬生物進(jìn)化過程中達(dá)爾文的“優(yōu)勝劣汰、適者生存”原則的新型優(yōu)化算法，GA已經(jīng)被證明是一種解決優(yōu)化問題的有效途徑。作為一種智能優(yōu)化方法，遺傳算法具有全局性、群體尋優(yōu)等特點(diǎn)，近年被廣泛應(yīng)用于計(jì)算組播路由問題。

3.1 基于免疫編碼、初始種群的產(chǎn)生

遺傳算法的首要問題是將問題由問題空間向遺傳算法空間進(jìn)行轉(zhuǎn)換。往往通過編碼的方式完成該轉(zhuǎn)換。通常采用樹結(jié)構(gòu)的編碼方式，即使用一棵樹來表示一個(gè)染色體。對于給定一個(gè)源節(jié)點(diǎn)s和一組目的節(jié)點(diǎn)，則群體中的每個(gè)染色體都表示一棵組播路由樹，初始的種群是隨機(jī)生成的。

3.3 選擇、交叉、變異

遺傳算法通過選擇、交叉和變異三種方式實(shí)現(xiàn)父代到子代的進(jìn)化過程。選擇是從群體中選取適應(yīng)度好的個(gè)體進(jìn)行保留，淘汰適應(yīng)度差的個(gè)體。選擇操作通常采用輪盤賭算法實(shí)現(xiàn)，其操作過程如下：首先計(jì)算群體中每個(gè)個(gè)體的適應(yīng)度，適應(yīng)度是由適應(yīng)度函數(shù)計(jì)算得出，然后按照適應(yīng)度的大小將個(gè)體進(jìn)行排序，選取適度值大的個(gè)體做父本。群體中所有個(gè)體被選擇的概率與其適度值成正比，即個(gè)體的適度值越大則被選取的概率也就越大。則每個(gè)個(gè)體i被選擇的概率為：，其中NPOP為種群的大小。

自然界進(jìn)化的核心是基因的重組，而交叉則是體現(xiàn)基因重組的重要方式。通過交叉操作使得遺傳算法的搜索能力提高。交叉操作的頻率取決于交叉概率，交叉概率越大能夠越快地收斂到最優(yōu)解區(qū)域，但過高的交叉頻率則會導(dǎo)致過早收斂，交叉概率的一般取值范圍在0.4-0.9。

子代的變異也是基因重組的一種重要方式。遺傳算法中，新個(gè)體的產(chǎn)生是通過變異操作得到的。變異概率的取值受染色體長度、種群大小等因素的影響。變異概率通常的取值范圍在0.01-0.1。

4 總結(jié)展望

遺傳算法能有效解決QoS組播路由問題，得到了廣泛的應(yīng)用和研究。遺傳算法的特點(diǎn)：

（1）實(shí)現(xiàn)問題空間向遺傳空間的映射，能夠進(jìn)行全局范圍的搜索且與問題領(lǐng)域無關(guān)；

（2）在群體的層次進(jìn)行搜索，具有并行性；

（3）搜索個(gè)體的優(yōu)劣使用用戶定義的評價(jià)函數(shù)評價(jià)，過程簡單，可進(jìn)行多值比較，魯棒性強(qiáng)；

（4）父代到子代的進(jìn)化過程中使用概率機(jī)制迭代，具有隨機(jī)性。經(jīng)實(shí)踐和理論證明，在一定條件下遺傳算法總是以概率1收斂于問題的最優(yōu)解。

多目標(biāo)優(yōu)化問題借助于進(jìn)化算法能夠得到有效的解決。因此，進(jìn)化算法對于優(yōu)化QoS組播路由算法將有著重要的意義。QoS組播路由優(yōu)化算法的深入研究，將會促進(jìn)下一代網(wǎng)絡(luò)的發(fā)展，具有廣泛、深遠(yuǎn)的意義。

參考文獻(xiàn)

[1]林闖，單志廣，任豐原著.計(jì)算機(jī)網(wǎng)絡(luò)的服務(wù)質(zhì)量（QoS）[M].北京：清華大學(xué)出版社，2004，4：186-205.

[2]Roy A，Das S K.QM2RP：a QoS-based mobile multicast routing protocol using multi-objective genetic algorithm[J].Wireless Networks，2004，10（03）：271-286.

作者單位

曲阜師范大學(xué)網(wǎng)絡(luò)信息中心 山東省曲阜市 273165endprint