劉金明， 仲光蘋

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

0 引言

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

1 QoS組播路由問題描述

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

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

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

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

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

(3)時(shí)延抖動(dòng)約束:DJ(s，M)＜DJ;

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

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

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

2 多約束QoS組播路由算法

2.1 編碼及種群初始化

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

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

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

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

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

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

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

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

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

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

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

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

2.3.1 選擇操作

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

2.3.2 交叉和變異操作

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

式中，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'是兩個(gè)要進(jìn)行交叉操作的染色體中較大的適應(yīng)度函數(shù)值，fiti是要進(jìn)行變異操作的染色體的適應(yīng)度函數(shù)值.

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

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

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

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

2.4.1 初溫確定和退溫操作

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

2.4.2 構(gòu)造鄰域解

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

圖1 算法收斂性能的分析

圖2 算法費(fèi)用性能的分析

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

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

通過在Metropolis判別準(zhǔn)則中引入溫度參數(shù)，使算法在高溫時(shí)接受劣質(zhì)解的能力比較強(qiáng)，保證了種群的多樣性，避免“早熟”.而當(dāng)溫度下降時(shí)，使優(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)則是整個(gè)組播路由算法的終止準(zhǔn)則.本文采用循環(huán)總數(shù)控制法和基于不改變規(guī)則的控制法相結(jié)合的方法.即當(dāng)算法達(dá)到外部循環(huán)總次數(shù)時(shí)，認(rèn)為達(dá)到了外部循環(huán)終止條件;或者算法還沒有達(dá)到設(shè)定的循環(huán)總次數(shù)，但在一定迭代次數(shù)內(nèi)沒有改變當(dāng)前最優(yōu)解時(shí)，也認(rèn)為達(dá)到了外部循環(huán)終止條件.

3 仿真實(shí)驗(yàn)

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

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

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

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

4 結(jié)論

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

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