基于克隆選擇的QoS組播路由優(yōu)化

王 莘

（西安航空學(xué)院 電氣學(xué)院，陜西 西安 710077）

基于克隆選擇的QoS組播路由優(yōu)化

王 莘

（西安航空學(xué)院 電氣學(xué)院，陜西 西安 710077）

衡量QoS組播路由主要性能指標(biāo)有延時(shí)，代價(jià)，帶寬等，本文所提出的基于遺傳算法的多約束QoS組播路由優(yōu)化算法。引入了一個(gè)綜合性能指標(biāo)Q適應(yīng)度函數(shù)，對(duì)延時(shí)、帶寬、代價(jià)這3個(gè)性能指標(biāo)進(jìn)行權(quán)衡。以減小組播樹的代價(jià)和延時(shí)，增大帶寬，提高組播的服務(wù)質(zhì)量。并對(duì)解決傳統(tǒng)算法對(duì)于存在兩組及以上的組播樹，他們的代價(jià)都是最優(yōu)的，延時(shí)和帶寬都滿足受限條件時(shí)無法選擇的問題十分有效的。

組播路由；遺傳算法；克隆選擇；適應(yīng)度函數(shù)

隨著網(wǎng)絡(luò)的發(fā)展和應(yīng)用，催生了很多新的業(yè)務(wù)類型。這些新型業(yè)務(wù)中很多基于組播技術(shù)，要求網(wǎng)絡(luò)能夠提供相應(yīng)的服務(wù)質(zhì)量（Quality of Service, QoS）控制，以滿足業(yè)務(wù)本身的特點(diǎn)和用戶的不同需求，而傳統(tǒng)的點(diǎn)對(duì)點(diǎn)技術(shù)無法提供服務(wù)質(zhì)量的保證。QoS組播路由技術(shù)依據(jù)當(dāng)前的網(wǎng)絡(luò)狀態(tài)和拓?fù)浣Y(jié)構(gòu)進(jìn)行路由選擇[1]，其目的是選擇從源節(jié)點(diǎn)到各個(gè)接收數(shù)據(jù)的目的節(jié)點(diǎn)并滿足QoS要求的路徑，同時(shí)使得由各個(gè)路徑組成的組播樹開銷最小。而求解具有多個(gè)約束條件時(shí)直接使用這種方法，就會(huì)更為困難。

遺傳算法（Genetic Algorithm, GA）是一種可有效地解決組合優(yōu)化等復(fù)雜問題的智能算法[2]，文中所使用的遺傳算法引入了一個(gè)綜合性能指標(biāo)Q適應(yīng)度函數(shù)，對(duì)延時(shí)、帶寬、代價(jià)這3個(gè)性能指標(biāo)進(jìn)行權(quán)衡。減小組播樹的延時(shí)和代價(jià)，增大帶寬，提高服務(wù)質(zhì)量[3]。并有效的解決了傳統(tǒng)的算法對(duì)于存在兩組及以上的組播樹，他們的代價(jià)都是最優(yōu)的，延時(shí)和帶寬都滿足受限條件時(shí)無法選擇的問題。從而實(shí)現(xiàn)了更精確的求解和參數(shù)的自動(dòng)化設(shè)置。

1 克隆選擇

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

2 優(yōu)化QoS組播路由的克隆算法

2.1 算法概述

對(duì)QoS組播路由影響較大的是延時(shí)、帶寬、代價(jià)是這3個(gè)性能指標(biāo)，傳統(tǒng)克隆算法在使組播樹的代價(jià)最小時(shí)，總通過滿足延時(shí)、約束帶寬的方法實(shí)現(xiàn)的?？墒窃谶@種方式的算法下，導(dǎo)致組播樹延時(shí)增大，帶寬減小。以延時(shí)和帶寬的性能下降為代價(jià)的網(wǎng)絡(luò)優(yōu)化就與現(xiàn)今網(wǎng)絡(luò)的發(fā)展相矛盾，而整個(gè)樹的整體性能往往不是最優(yōu)的，并且往往會(huì)導(dǎo)致局部最優(yōu)和不穩(wěn)定，算法過于早熟。當(dāng)網(wǎng)絡(luò)中存在了兩組或以上的組播樹，它們的代價(jià)都是最優(yōu)的，延時(shí)和帶寬都滿足受限條件，但是組播樹的延時(shí)或帶寬不同。這時(shí)傳統(tǒng)算法只是滿足延時(shí)、帶寬約束的前提下是組播樹的代價(jià)最小，而無法隨機(jī)的選擇一組組播樹得到最優(yōu)組播樹。

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

同時(shí)該算法引進(jìn)了基因優(yōu)化操作，對(duì)二代抗體群p[t+1]基因優(yōu)化操作。即對(duì)個(gè)體內(nèi)部的所有源節(jié)點(diǎn)到目的節(jié)點(diǎn)所選擇的的路徑進(jìn)行親和度計(jì)算，每組源節(jié)點(diǎn)和目的節(jié)點(diǎn)只保留一個(gè)最有路徑，這樣大大提高了收斂速度。

2.2 算法步驟

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

S2：初始抗體群的產(chǎn)生：對(duì)備選路徑集PT（a，bj），如其中有nbj（bj∈N）備選路徑，共選N次，按選取的自然順序?qū)⑷〉玫倪@N組數(shù)據(jù)組成向量，記作Ab[r] ，則此向量就是初始抗體。把上述操作進(jìn)行M次，就可得到一初始抗體群p[1]。

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

整體考慮組播路由綜合性能，因?yàn)閹捲酱蟆⒀訒r(shí)和代價(jià)越小，則Q值越大、組播綜合性能越優(yōu)。保留Q值最大的前5項(xiàng)的組播樹，組成抗體群p[t]。

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

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

S5：基因優(yōu)化：對(duì)二代抗體群p[t+1]基因優(yōu)化操作。即對(duì)個(gè)體內(nèi)部的所有源節(jié)點(diǎn)到目的節(jié)點(diǎn)所選擇的的路徑進(jìn)行親和度計(jì)算，每組源節(jié)點(diǎn)和目的節(jié)點(diǎn)只保留一個(gè)最有路徑。

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

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

S8：判斷最優(yōu)個(gè)體：若新一代群體中存在最優(yōu)個(gè)體，則終止運(yùn)算；否則，t = t+1轉(zhuǎn)到S4。

2.3 仿真結(jié)果及分析

本文算法采用MWaxman提出的方法[6]，所使用的網(wǎng)絡(luò)拓?fù)鋱D如圖1所示，延時(shí)、帶寬、代價(jià)由（D,B,C）表示，源節(jié)點(diǎn)為1，目的節(jié)點(diǎn)為2、3、5、8。

圖1 節(jié)點(diǎn)網(wǎng)絡(luò)拓?fù)銯ig. 1 Node network topology

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

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

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

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

3 結(jié) 論

仿真結(jié)果表明算法通過設(shè)計(jì)適應(yīng)度函數(shù)Q，并結(jié)合交叉、變異的克隆原理對(duì)組播路由進(jìn)行優(yōu)化，可使程序運(yùn)行更為簡(jiǎn)潔，提高了效率，其收斂度明顯有較大提高，運(yùn)行可靠，大大改善了QoS組播路由[7]的服務(wù)質(zhì)量。

[1] 胡虹雨,畢軍,陸慧梅.大規(guī)模組播路由中組播相關(guān)信息聚集問題研究[J].清華大學(xué)學(xué)報(bào),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] 張銀浦.遺傳算法在組播路由優(yōu)化中的應(yīng)用[J].河北科技大學(xué)學(xué)報(bào),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] 劉維群，李元臣.一種滿足時(shí)延和時(shí)延差約束的組播路由算法[J].計(jì)算機(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] 劉國聯(lián),何煉.一種用于優(yōu)化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ìn)克隆策略的整體優(yōu)化組播路由算法[J].電子技術(shù)應(yīng)用,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] 丁文. 基于免疫多目標(biāo)優(yōu)化的網(wǎng)絡(luò)組播路由選擇[J].計(jì)算機(jī)應(yīng)用研究,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] 張啟明.無線網(wǎng)絡(luò)中一種高QoS保證的路由協(xié)議研究[J].現(xiàn)代電子技術(shù),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 稿件編號(hào)：201306198

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