基于遺傳算法優化的QoS組播路由算法

萬曙靜+浩慶波+徐巖

摘 要

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

【關鍵詞】遺傳算法 組播路由 優化算法

1 引言

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

2 網絡模型

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

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

3 基于遺傳算法優化的組播路由算法

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

3.1 基于免疫編碼、初始種群的產生

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

3.3 選擇、交叉、變異

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

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

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

4 總結展望

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

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

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

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

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

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

參考文獻

[1]林闖，單志廣，任豐原著.計算機網絡的服務質量（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.

作者單位

曲阜師范大學網絡信息中心 山東省曲阜市 273165endprint