基于克隆選擇的QoS組播路由優化

王 莘

（西安航空學院 電氣學院，陜西 西安 710077）

基于克隆選擇的QoS組播路由優化

王 莘

（西安航空學院 電氣學院，陜西 西安 710077）

衡量QoS組播路由主要性能指標有延時，代價，帶寬等，本文所提出的基于遺傳算法的多約束QoS組播路由優化算法。引入了一個綜合性能指標Q適應度函數，對延時、帶寬、代價這3個性能指標進行權衡。以減小組播樹的代價和延時，增大帶寬，提高組播的服務質量。并對解決傳統算法對于存在兩組及以上的組播樹，他們的代價都是最優的，延時和帶寬都滿足受限條件時無法選擇的問題十分有效的。

組播路由；遺傳算法；克隆選擇；適應度函數

隨著網絡的發展和應用，催生了很多新的業務類型。這些新型業務中很多基于組播技術，要求網絡能夠提供相應的服務質量（Quality of Service, QoS）控制，以滿足業務本身的特點和用戶的不同需求，而傳統的點對點技術無法提供服務質量的保證。QoS組播路由技術依據當前的網絡狀態和拓撲結構進行路由選擇[1]，其目的是選擇從源節點到各個接收數據的目的節點并滿足QoS要求的路徑，同時使得由各個路徑組成的組播樹開銷最小。而求解具有多個約束條件時直接使用這種方法，就會更為困難。

遺傳算法（Genetic Algorithm, GA）是一種可有效地解決組合優化等復雜問題的智能算法[2]，文中所使用的遺傳算法引入了一個綜合性能指標Q適應度函數，對延時、帶寬、代價這3個性能指標進行權衡。減小組播樹的延時和代價，增大帶寬，提高服務質量[3]。并有效的解決了傳統的算法對于存在兩組及以上的組播樹，他們的代價都是最優的，延時和帶寬都滿足受限條件時無法選擇的問題。從而實現了更精確的求解和參數的自動化設置。

1 克隆選擇

克隆選擇是生物免疫系統的重要學說。其基本原理是通過細胞對抗原的識別，來選擇并保留下來那些能過識別抗原的細胞，同時對這些細胞進行擴增，而那些不能識別抗原的細胞則不選擇也不擴增。在成長的克隆中，免疫系統是自適應的，同時也呈現出一種變異機制，在對抗體特意編碼的基因中產生極高頻率的點變異[4]。這種機制與改進抗原一起所進行的選擇具有極高的親和力匹配。同時要能夠識別所有的抗原，受控群體和指令系統要具有多樣性。

2 優化QoS組播路由的克隆算法

2.1 算法概述

對QoS組播路由影響較大的是延時、帶寬、代價是這3個性能指標，傳統克隆算法在使組播樹的代價最小時，總通過滿足延時、約束帶寬的方法實現的。可是在這種方式的算法下，導致組播樹延時增大，帶寬減小。以延時和帶寬的性能下降為代價的網絡優化就與現今網絡的發展相矛盾，而整個樹的整體性能往往不是最優的，并且往往會導致局部最優和不穩定，算法過于早熟。當網絡中存在了兩組或以上的組播樹，它們的代價都是最優的，延時和帶寬都滿足受限條件，但是組播樹的延時或帶寬不同。這時傳統算法只是滿足延時、帶寬約束的前提下是組播樹的代價最小，而無法隨機的選擇一組組播樹得到最優組播樹。

這對這種情況，本文提出了基于改進克隆策略的整體優化主播路由算法。該算法在原克隆算法滿足延時約束的條件基礎上，引入了一個綜合性能指標Q適應度函數，Q=B/(D×C)取代原克隆算法只以代價C作為適應度函數，對延時、帶寬、代價這3個性能指標進行權衡。以減小組播樹的代價和延時，增大帶寬，提高組播的服務質量。并對解決傳統算法對于存在兩組及以上的組播樹，他們的代價都是最優的[5]，延時和帶寬都滿足受限條件時無法選擇的問題十分有效的。

同時該算法引進了基因優化操作，對二代抗體群p[t+1]基因優化操作。即對個體內部的所有源節點到目的節點所選擇的的路徑進行親和度計算，每組源節點和目的節點只保留一個最有路徑，這樣大大提高了收斂速度。

2.2 算法步驟

S1：備選路徑集的選擇：確定源節點a和目的節點bj(bj∈N)，利用深度優化搜索找出滿足約束條件的路徑，將搜索的所有路徑組成多播組端接點bj的備選路徑集PT（a，bj）。

S2：初始抗體群的產生：對備選路徑集PT（a，bj），如其中有nbj（bj∈N）備選路徑，共選N次，按選取的自然順序將取得的這N組數據組成向量，記作Ab[r] ，則此向量就是初始抗體。把上述操作進行M次，就可得到一初始抗體群p[1]。

S3：親和度計算：在優先滿足延時條件下，定義親和度函數f = Q 、Q=B/(D×C)其中

整體考慮組播路由綜合性能，因為帶寬越大、延時和代價越小，則Q值越大、組播綜合性能越優。保留Q值最大的前5項的組播樹，組成抗體群p[t]。

S4：克隆：設原抗體群p[t]為一X×Y維矩陣，那么對其進行的克隆操作可表示為：

其中In=X，這樣所組成的就是二代的抗體群p[t+1]。

S5：基因優化：對二代抗體群p[t+1]基因優化操作。即對個體內部的所有源節點到目的節點所選擇的的路徑進行親和度計算，每組源節點和目的節點只保留一個最有路徑。

S6：克隆交叉：采用隨機按位交叉，對二代抗體群p[t+1]進行交叉換位，隨機產生L組組播樹，并在其隨機位上按照交叉概率進行交換。

S7：遺傳變異：同樣采用隨機按位交叉，對二代抗體群p[t+1]進行變異操作，隨機選取一整數值R∈[0，ni-1]，按照變異概率取代pi×j[t]=Ab[r]，(i＜X，j＜Y，r[1，M])上的原有值。

S8：判斷最優個體：若新一代群體中存在最優個體，則終止運算；否則，t = t+1轉到S4。

2.3 仿真結果及分析

本文算法采用MWaxman提出的方法[6]，所使用的網絡拓撲圖如圖1所示，延時、帶寬、代價由（D,B,C）表示，源節點為1，目的節點為2、3、5、8。

圖1 節點網絡拓撲Fig. 1 Node network topology

當帶寬約束的B=70，延時D≤45，時。首先進行預處理，去掉不滿足要求的3-7、5-6兩條鏈路。則生成的路徑集如表1所示。

使用matlab編寫該算法程序并運行，結果如圖2所示，算法在第一代就收斂了，大大提高了其收斂速度。得出的最優組播樹為[{1,2},{1,2,5},{1,4,3},{1,2,5,7,8}]，Q=0.108 6。

圖2 Q值隨代數變化曲線Fig. 2 Curve of Q value change with algebra

表1 備選路徑集Tab.1 Alternative path set

3 結 論

仿真結果表明算法通過設計適應度函數Q，并結合交叉、變異的克隆原理對組播路由進行優化，可使程序運行更為簡潔，提高了效率，其收斂度明顯有較大提高，運行可靠，大大改善了QoS組播路由[7]的服務質量。

[1] 胡虹雨,畢軍,陸慧梅.大規模組播路由中組播相關信息聚集問題研究[J].清華大學學報,2011(12):1800-1807.

HU Hong-yu,BI Jun,LU Hui-mei.Aggregation of multicastrelated information in large scale multicast routing[J].Journal of Tsinghua University,2011(12):1800-1807.

[2] 張銀浦.遺傳算法在組播路由優化中的應用[J].河北科技大學學報,2011(3):261-264.

ZHANG Yin-pu.Application of gencetic algorithm to of multicast routing[J].Journal of Hebei University Of Science and Technology,2011(3):261-264.

[3] 劉維群，李元臣.一種滿足時延和時延差約束的組播路由算法[J].計算機工程 ,2012(14):102-105.

LIU Wei-qun，LI Yuan-chen.Multicast routing algorithm satisfying delay and delay defference constraint[J].Computer Engineering,2014(14):102-105.

[4] 劉國聯,何煉.一種用于優化QoS組播路由的克隆算法[J].科技信息,2012(32):55-56.

LIU Guo-lian,HE Lian.A clone of optimization algorithm for QoS multicast routing[J]. Science & Technology Information,2012(32):55-56.

[5] 黃小鳳,王煉紅.基于改進克隆策略的整體優化組播路由算法[J].電子技術應用,2009(9):119-121,125.

HUANG Xiao-feng,WANG Lian-hong.Whole optimization multicast routing algorithm based on improved clonal strategy[J].Application of Electronic Technique,2009(9):119-121,125.

[6] 丁文. 基于免疫多目標優化的網絡組播路由選擇[J].計算機應用研究,2012(4):1477-1479.

DING Wen. Multicast routing selection based on multi-object immune alogrithm[J].Application Research of Computers,2012(4):1477-1479.

[7] 張啟明.無線網絡中一種高QoS保證的路由協議研究[J].現代電子技術,2012(21):78-82.

ZHANG Qi-ming. Research of a high QoS guarantee of routing protocol in the wireless network[J].Modern Electronics Technique,2012(21):78-82.

QoS multicast routing optimization based on clonal selection

WANG Xin
（College of Electrical Engineering, Xi'an Aeronautical University, Xi'an 710077, China）

Influence of QoS multicast routing is the larger delay, bandwidth, at the expense of performance indicators,this paper presents an optimization algorithm for multiple constrained QoS multicast routing based on genetic algorithm.Introduce a comprehensive performance index of Q fitness function, to weigh in on time delay, bandwidth, at the expense of the three performance indicators. The cost of delay is small, the multicast tree bandwidth, improve the multicast service quality. And effective solution to the traditional algorithm for the existence of two group and multicast tree above, their price is the best, do not choose to delay and bandwidth can satisfy the constrained conditions of the problem.

multicast routing; genetic algorithm; colonal selection; fitness function

TN919

A

1674-6236(2014)03-0083-02

2013–06–28 稿件編號：201306198

王 莘(1983—)，男，陜西西安人，碩士研究生，助教。研究方向：電力電子控制。