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

萬曙靜+浩慶波+徐巖

摘 要

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

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

1 引言

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

2 網(wǎng)絡模型

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

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

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

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

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

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

3.3 選擇、交叉、變異

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

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

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

4 總結展望

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

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

（2）在群體的層次進行搜索，具有并行性；

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

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

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

參考文獻

[1]林闖，單志廣，任豐原著.計算機網(wǎng)絡的服務質(zhì)量（QoS）[M].北京：清華大學出版社，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.

作者單位

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