劉金明， 仲光蘋

(1.黑龍江八一農(nóng)墾大學(xué)信息技術(shù)學(xué)院，黑龍江 大慶 163319;2.東北石油大學(xué)數(shù)學(xué)科學(xué)與技術(shù)學(xué)院，黑龍江 大慶 163318)

0 引言

多約束QoS組播路由問題實際上就是帶多個QoS約束的Steiner樹問題，是典型的NP完全問題[1]，存在大量基于蟻群算法、遺傳算法等智能搜索算法的求解方法，其中應(yīng)用最多的就是遺傳算法及其改進(jìn)算法.文獻(xiàn)[2]中Xiang等提出了基于遺傳算法來求解QoS路由問題，其算法采用的二進(jìn)制編碼方法，導(dǎo)致其搜索空間會隨著網(wǎng)絡(luò)規(guī)模的增大而急劇增大.文獻(xiàn)[3]中Wang等提出基于遺傳算法求解帶寬和時延約束費用最小組播路由問題，其算法采用樹型結(jié)構(gòu)編碼策略，算法的性能較好，但樹形編碼卻帶來了非常復(fù)雜的交叉和變異操作.文獻(xiàn)[4]中Hamdan等針對時延和時延抖動約束的費用最小組播路由問題，提出了基于整數(shù)隊列編碼策略的遺傳算法求解方法，算法的編碼方式非常簡單，且效率較高.文獻(xiàn)[5]中劉金明等提出了基于遺傳模擬退火算法求解組播路由問題的相關(guān)方法，但是只涉及了帶寬和時延兩個QoS約束條件.文獻(xiàn)[6]中，張琨等提出了基于模擬退火方法的多約束QoS組播路由算法，算法求得的組播路由樹的費用性能較好，但由于模擬退火算法自身的不足，導(dǎo)致算法的效率比較低.本文在前人研究基礎(chǔ)上，提出基于遺傳模擬退火算法的多約束QoS組播路由算法，該組播路由算法采用基于備選路徑集策略的整數(shù)隊列編碼方法，結(jié)合模擬退火算法溫度參數(shù)設(shè)計適應(yīng)度函數(shù)，并引入啟發(fā)式交叉操作策略和自適應(yīng)的交叉變異概率思想，即解決了遺傳算法容易陷入過早的收斂和進(jìn)化后期搜索效率低的問題，又克服了模擬退火算法自身進(jìn)化速度慢的缺陷.實驗仿真表明，本文提出的算法求得的組播路由樹具有良好的費用性能，且收斂速度很快.

1 QoS組播路由問題描述

組播網(wǎng)絡(luò)可用無向帶權(quán)連通圖G=(V，E)來表示，其中V為節(jié)點集，E為鏈路集，R+和R+分別表示正實數(shù)集和非負(fù)實數(shù)集.對于任意鏈路e∈E，可定義3種度量，分別為:費用函數(shù)C(e):E→R+，帶寬函數(shù)B(e):E→R+和時延函數(shù)D(e):E→R+;對于任意網(wǎng)絡(luò)節(jié)點n∈V，可定義3種度量，分別為費用函數(shù)C(n):E→R+，時延函數(shù)D(n):E→R+和包丟失率函數(shù)PL(n):V→R+.在組播網(wǎng)絡(luò)中，給定源節(jié)點s∈V，目的節(jié)點集合M?{V－{s}}，?di，dj∈M，則s和M組成的組播路由樹T(s，M)將存在下列關(guān)系:

式中，PT(s，di)為組播路由樹T(s，M)上從給定源節(jié)點s到任意目的節(jié)點di的一條路由路徑，DJ(s，M)為組播路由樹T(s，M)中的最大時延抖動值.

在組播網(wǎng)絡(luò)G=(V，E)中，給定源節(jié)點s∈V，目的節(jié)點集合M?{V－{S}}，?di∈M，設(shè)定帶寬函數(shù)B(·)∈R+，時延函數(shù)D(·)∈R+，時延抖動函數(shù)DJ(·)∈R+，包丟失率函數(shù)PL(·)∈ R+，費用函數(shù)C(·)∈R+，則多約束QoS組播路由算法求得的組播路由樹T(s，M)必須滿足如下條件:

(1)帶寬約束:B(PT(s，di))≥Bi;

(2)時延約束:D(PT(s，di))≤Di;

(3)時延抖動約束:DJ(s，M)＜DJ;

(4)包丟失率約束:PL(PT(s，di))≤PLi;

(5)費用約束:在所有滿足上述(1)～(4)條件的組播路由樹中，使C(T(s，M))最小.

其中，Bi，Di和PLi分別對應(yīng)著目的節(jié)點 di的帶寬、時延和包丟失率約束，而DJ是整個組播路由樹的時延抖動約束.

2 多約束QoS組播路由算法

2.1 編碼及種群初始化

在組播網(wǎng)絡(luò)中，給定源節(jié)點s和目的節(jié)點集合M，基于備選路徑集的整數(shù)隊列編碼方法就是將染色體編碼成長度為m=|M|的整數(shù)隊列，每一個隊列就是染色體的一個基因，也就是從源節(jié)點到特定目的節(jié)點滿足一定約束條件的路由路徑.本文采用的具體編碼方案如下:

首先，對所有的目的節(jié)點di∈M，計算其備選路徑集.目的節(jié)點di備選路徑集的生成方法為:先對網(wǎng)絡(luò)使用帶寬約束Bi進(jìn)行簡化，再使用Dijkstra第k最短路徑算法找到從給定源節(jié)點s到特定目的節(jié)點di所有滿足時延約束Di和包丟失率約束PLi的路由路徑.設(shè)Qi為特定目的節(jié)點di的備選路徑集，則

然后，從所有的目的節(jié)點對應(yīng)的路徑集中都任選一條路由路徑作為染色體的基因，組成一棵基因個數(shù)為m的組播路由樹，作為初始種群的一個染色體.

按照上述方法生成一定數(shù)量的染色體構(gòu)成初始種群，完成種群初始化.

2.2 適應(yīng)度函數(shù)設(shè)計

適應(yīng)度函數(shù)決定了遺傳算法的搜索方向，直接影響遺傳算法的執(zhí)行時間和求解效率.多約束QoS組播路由問題實際上是帶多個約束的費用最小化問題.由于遺傳算法的編碼過程中已經(jīng)去除了帶寬、時延和包丟失率約束，因此目標(biāo)函數(shù)可以直接表示為

其中，Φ(Z)為懲罰函數(shù)，r為懲罰因子，當(dāng)組播路由樹滿足時延抖動約束時，其值為0;否則等于r(r為比較大的正實數(shù)).

結(jié)合模擬退火算法的溫度參數(shù)，可以將遺傳算法的適應(yīng)度函數(shù)定義為

式中:fmin為當(dāng)前代種群中最小目標(biāo)函數(shù)值，t為當(dāng)前代溫度值.

此適應(yīng)度函數(shù)可以使算法在進(jìn)行賭輪選擇時具有兩點好處:一是在溫度高時(組播路由算法運行早期)，可有效避免個別適應(yīng)度高的染色體充斥整個種群造成早熟;二是在溫度低時(組播路由算法運行后期)，優(yōu)良染色體具有相對更大的適應(yīng)度函數(shù)值，使其能夠更容易遺傳給下一代，加快算法的搜索速度.

結(jié)合了溫度參數(shù)的新型適應(yīng)度函數(shù)的使用，可以有效解決傳統(tǒng)遺傳算法自身存在的容易陷入過早收斂和進(jìn)化后期搜索效率低的問題.

2.3 遺傳參數(shù)設(shè)計

2.3.1 選擇操作

選擇操作采用最常用的賭輪選擇的方法，同時為保證算法能夠收斂到全局最優(yōu)解，在進(jìn)行選擇操作前先使用最優(yōu)保留策略將當(dāng)前種群中的最優(yōu)解直接復(fù)制給下一代種群.

2.3.2 交叉和變異操作

交叉概率Pc和變異概率Pm是遺傳算法設(shè)計過程中影響其搜索行為和求解性能的關(guān)鍵，直接決定了算法的收斂性能.本文采用自適應(yīng)的交叉和變異概率計算方法，其計算公式如下:

式中，k1，k2，k3，k4，k5，k6都是常數(shù)，且 k3=k1+k2，k6=k4+k5;fitmax是當(dāng)前代種群中的最大適應(yīng)度函數(shù)值，fitavg是當(dāng)前代種群的平均適應(yīng)度函數(shù)值;fiti'是兩個要進(jìn)行交叉操作的染色體中較大的適應(yīng)度函數(shù)值，fiti是要進(jìn)行變異操作的染色體的適應(yīng)度函數(shù)值.

采用此交叉和變異概率計算方法，適應(yīng)度函數(shù)值較小的染色體計算出的交叉和變異概率都比較大，能夠加快遺傳算法的搜索速度.當(dāng)前代最優(yōu)染色體的交叉和變異概率是一個較小值，能夠使最優(yōu)染色體參與到生成下一代個體的交叉和變異操作中，進(jìn)一步加快算法的搜索速度.當(dāng)fitavg→fitmax使算法陷入問題求解的局部最優(yōu)時，適應(yīng)度函數(shù)值較大的染色體計算出的交叉和變異概率也將增大，能夠有效提高算法跳出局部最優(yōu)的能力，有效避免“早熟”.但為了防止原有解空間被完全破壞，當(dāng)|fitmax－fitavg＜ ε時，就固定Pc，Pm值.

算法的交叉操作采用相同鏈路保留的策略.其交叉策略為:按賭輪方法選擇出兩個父代染色體TM和TN，計算其交叉概率Pc，按概率Pc進(jìn)行交叉操作生成新的染色體Tc.兩個父代染色體中相同的路由路徑(優(yōu)良基因)將直接遺傳給后代染色體，對于路由路徑不同的目的節(jié)點，以di為例，計算兩個父代染色體中目的節(jié)點di對應(yīng)的路由路徑PM(s，di)和PN(s，di)的路徑費用，將路徑費用小的路由路徑(優(yōu)良基因)作為組成子代染色體從源節(jié)點s到目的節(jié)點di的基因.對兩個父代染色體TM和TN中所有具有不同路由路徑的目的節(jié)點，按上述操作生成子代染色體的基因，完成交叉操作生成一個子代染色體.

算法的變異操作采用位變異的方法.位變異的方法是:任意選取染色體中某個目的節(jié)點di對應(yīng)的路由路徑(基因)，從其對應(yīng)的備選路徑集Qi中隨機(jī)選擇一條路由路徑作為基因進(jìn)行替換.

2.4 模擬退火參數(shù)設(shè)計

2.4.1 初溫確定和退溫操作

初始溫度的設(shè)定采用t0=Kδ的形式，其中K是一個足夠大的數(shù)，且δ=是初始種群的最大和最小目標(biāo)函數(shù)值.退溫操作采用tn+1=αt的形式，其中0＜α＜1.

2.4.2 構(gòu)造鄰域解

鄰域解的構(gòu)造方法采用與變異操作類似的“路徑交換策略”.

圖1 算法收斂性能的分析

圖2 算法費用性能的分析

2.4.3 設(shè)置狀態(tài)接受函數(shù)

模擬退火算法的初始種群由遺傳算法提供，組播路由算法運行一輪次后生成的種群，再經(jīng)過一系列的遺傳操作后，將生成新的種群，這個新的種群就是組播路由算法運行每一輪次中模擬退火算法的初始種群.對該初始種群進(jìn)行基于Metropolis判別準(zhǔn)則的選擇復(fù)制后，將生成下一代種群，這個種群就組播路由算法運行一輪次后生成的新一代種群.假設(shè)為染色體i構(gòu)造了一個鄰域染色體j，i和j將基于Metropolis判別準(zhǔn)則競爭進(jìn)入下一代種群.Metropolis判別準(zhǔn)則為:令Δf=fit(Ti)－fit(Tj)，若Δf≤0，則新染色體j將被復(fù)制到下一代種群中;若Δf＞0，則生成一個隨機(jī)數(shù) r∈[0，1]，當(dāng) r＜exp(－Δf/tn)時，新染色體j仍將被復(fù)制到下一代種群中;否則，把染色體i復(fù)制到下一代種群中.

通過在Metropolis判別準(zhǔn)則中引入溫度參數(shù)，使算法在高溫時接受劣質(zhì)解的能力比較強(qiáng)，保證了種群的多樣性，避免“早熟”.而當(dāng)溫度下降時，使優(yōu)良染色體更容易遺傳給下一代，加快算法的收斂速度.

2.5 算法的終止準(zhǔn)則

2.5.1 內(nèi)部循環(huán)終止準(zhǔn)則

內(nèi)部循環(huán)終止準(zhǔn)則是算法由模擬退火部分向遺傳算法部分切換的條件，也稱為Metropolis抽樣穩(wěn)定準(zhǔn)則.本文采用基于不改變規(guī)則的控制法，在算法的模擬退火部分求解過程中，若求得的最優(yōu)解連續(xù)若干代進(jìn)化過程中保持不變，則認(rèn)為滿足了內(nèi)部循環(huán)終止條件，進(jìn)行退溫操作，并切換到遺傳算法部分進(jìn)行遺傳操作.

2.5.2 外部循環(huán)終止準(zhǔn)則

外部循環(huán)終止準(zhǔn)則是整個組播路由算法的終止準(zhǔn)則.本文采用循環(huán)總數(shù)控制法和基于不改變規(guī)則的控制法相結(jié)合的方法.即當(dāng)算法達(dá)到外部循環(huán)總次數(shù)時，認(rèn)為達(dá)到了外部循環(huán)終止條件;或者算法還沒有達(dá)到設(shè)定的循環(huán)總次數(shù)，但在一定迭代次數(shù)內(nèi)沒有改變當(dāng)前最優(yōu)解時，也認(rèn)為達(dá)到了外部循環(huán)終止條件.

3 仿真實驗

本文在VC++6.0編程環(huán)境下對提出的算法進(jìn)行了仿真.在仿真實驗中，為了仿真方便，將QoS組播路由問題進(jìn)行簡化，只考慮鏈路的時延和費用兩個度量屬性，鏈路的帶寬，節(jié)點的費用、時延、包丟失率度量屬性都被忽略掉了，相應(yīng)的QoS約束條件也進(jìn)行了簡化，只保留時延和時延抖動兩個約束條件.由本文的編碼方案可知，采用簡化后的度量屬性和約束條件不會影響算法仿真的準(zhǔn)確性.

通過仿真實驗，主要對提出的多約束QoS組播路由算法的兩點性能進(jìn)行分析:一是對算法的收斂性能進(jìn)行分析;二是對算法求得的組播路由樹的費用性能進(jìn)行分析.

在仿真實驗中，將文獻(xiàn)[4]中提出的基于遺傳算法的時延及時延抖動約束組播路由算法，文獻(xiàn)[6]中提出的基于模擬退火算法的多約束QoS組播路由算法與本文提出的算法在性能和效率上進(jìn)行了比較.因為上述三個算法所采用的策略不同，所以本文使用CPU執(zhí)行時間來對算法的收斂性能進(jìn)行分析測試.

圖1展示了本文算法與文獻(xiàn)[4]算法、文獻(xiàn)[6]算法在執(zhí)行時間上的比較結(jié)果.而圖2則展示了在不同網(wǎng)絡(luò)節(jié)點數(shù)情況下，本文算法與文獻(xiàn)[4]算法、文獻(xiàn)[6]算法在計算出的組播路由樹費用性能上的比較結(jié)果.從圖1和圖2不難看出，本文提出的基于遺傳模擬退火算法的多約束QoS路由算法在計算性能和求解效率上具有明顯的優(yōu)勢.

4 結(jié)論

本文針對多約束QoS組播路由問題求解的復(fù)雜性，提出了一種新型全局智能優(yōu)化算法——遺傳模擬退火算法，并提出了基于遺傳模擬退火算法的多約束QoS組播路由算法.該算法通過采用基于備選路徑集的整數(shù)隊列路徑編碼方案來簡化編解碼操作，結(jié)合溫度參數(shù)來設(shè)計適應(yīng)度函數(shù)，即避免了早熟，又加快了進(jìn)化后期的搜索能力，引入啟發(fā)式交叉操作和自適應(yīng)的交叉變異概率思想提高算法的計算效率，通過Metropolis判別準(zhǔn)則來保證算法的全局收斂性.通過仿真實驗證明，該算法具有收斂速度快，穩(wěn)定性強(qiáng)，費用性能良好的特點，能夠滿足當(dāng)前多媒體網(wǎng)絡(luò)在QoS方面的各種需求.

[1]Stefan Vob.Steiner’s Problem in Graphs:Heuristic Methods[J].Discrete Applied Mathematics，1992，40(1):45 －72.

[2]F.Xiang，L.Junzhou，W.Jieyi，et al.QoS Routing Based on Genetic Algorithm[J].Computer Communications，1999，22(15):1394－1399.

[3]Wang Zhengying，Shi Bingxin，Zhao Erdun.Bandwidth－ delay－constrained Least Cost Multicast Routing Based on Heuristic Genetic Algorithm[J].Computer Communications，2001，24(7):685－692.

[4]M.Hamdan，M.E.El－ Hawary.Multicast Routing with Delay and Delay Variation Constraints Using Genetic Algorithm[J].Proceedings of the Canadian Conference on Electrical and Computer Engineering，2004，4:2363 －2366.

[5]劉金明，王娜，劉勇.基于遺傳模擬退火算法的QoS組播路由問題求解[J].佳木斯大學(xué)學(xué)報(自然科學(xué)版)，2008，26(4):535－538.

[6]張琨，王珩，劉玉風(fēng).一種基于模擬退火方法的多約束QoS組播路由算法[J].計算機(jī)科學(xué)，2005，32(5):41 －45.