陳建明

(浙江師范大學(xué) 數(shù)理與信息工程學(xué)院,浙江 金華 321004)

基于PBIL的綜合QoS參數(shù)組播路由*

陳建明

(浙江師范大學(xué) 數(shù)理與信息工程學(xué)院,浙江 金華 321004)

提出了一種基于PBIL(Population-Based Incremental Learning)的QoS組播路由算法，它能在綜合QoS參數(shù)約束條件下尋找代價最小的多播樹.該算法有效地結(jié)合了遺傳算法的進(jìn)化特性與競爭學(xué)習(xí)算法的特點，采用基于路徑的樹編碼結(jié)構(gòu)和基于概率的備選路徑集，在網(wǎng)絡(luò)規(guī)模較大的情況下也能得到很好的應(yīng)用.仿真實驗表明,該算法快速有效.

Steiner樹；QoS；組播；遺傳算法；PBIL算法

0引言

QoS組播路由技術(shù)是網(wǎng)絡(luò)多媒體信息傳輸?shù)年P(guān)鍵技術(shù)之一， 亦已有不少研究成果[1-2].理想的路由算法應(yīng)在滿足QoS的前提下實現(xiàn)路由代價最小.目前,學(xué)界對于多播路由問題已經(jīng)提出了多種算法，總體目標(biāo)是極小化構(gòu)造的多播樹代價.通常具有最小代價的多播樹稱為Steiner樹[3]，該問題已證明是NP完全問題[4].傳統(tǒng)的解決Steiner問題的啟發(fā)式算法,能夠在貪婪搜索的基礎(chǔ)上,在多項式時間內(nèi)找到合適的解(不是全局最優(yōu)解)，其基本原理是對于搜索過程中遇到的每一個新狀態(tài)，按估價函數(shù)計算出它的最佳代價估計值，然后選出當(dāng)時估計值的最小狀態(tài)，并從該節(jié)點開始搜索.該算法的計算速度慢，缺乏全局觀點，而且可擴(kuò)展性差，難以適應(yīng)有動態(tài)成員的大型群組.

遺傳算法作為一種智能優(yōu)化方法,具有并行搜索、群體尋優(yōu)的特點，適用于在復(fù)雜而龐大的搜索空間中尋找最優(yōu)解或次優(yōu)解，已廣泛用于解決各種具有NP難度的問題.但是，已有實踐表明,遺傳算法在實際的重組操作過程中可能會破壞個體的構(gòu)造塊,從而產(chǎn)生連鎖問題，導(dǎo)致算法逼近局部最優(yōu)或者早熟[4].

Baluja在1994年提出了基于群體的增量學(xué)習(xí)(Population-Based Increased Learning，簡稱PBIL)算法[5]，該算法集成了基于函數(shù)優(yōu)化的遺傳搜索和競爭學(xué)習(xí)2種策略，將進(jìn)化過程視為學(xué)習(xí)過程，通過競爭學(xué)習(xí)獲取的知識——學(xué)習(xí)概率(Learning Probability)指導(dǎo)后代的產(chǎn)生.這種概率是整個進(jìn)化過程的信息積累，同遺傳算法的雙親基因重組相比，用它指導(dǎo)產(chǎn)生的后代將會更優(yōu)生，因此能獲得較快的收斂速度和理想的計算結(jié)果，已在實際問題中得到應(yīng)用[6-7].

本文提出了一種基于PBIL算法的綜合QoS參數(shù)組播路由算法，該算法編碼簡單，易于實施，實驗結(jié)果也表明該算法是有效的.

1QoS組播路由模型

QoS是衡量通信網(wǎng)絡(luò)的主要指標(biāo)，它包括網(wǎng)絡(luò)的費用、距離、帶寬、時延、時延抖動、差錯率、分組丟失率及安全等.通常，路由選擇策略因網(wǎng)絡(luò)可用資源狀況和它本身對QoS要求的不同而異.針對不同的QoS要求，目前的算法主要側(cè)重于帶寬、時延、時延抖動、分組丟失率等等QoS參數(shù)約束的某個或某幾個方面，適用面較窄.為了尋找能較好地適應(yīng)QoS變化的路由算法，本文借鑒了鄒陽等[8]提出的單點路由選擇的數(shù)學(xué)模型，給出了綜合QoS參數(shù)的組播路由模型.

在研究路由問題時，計算機(jī)網(wǎng)絡(luò)可表示成一個無向賦權(quán)圖G(V，E)，其中V表示節(jié)點集，E表示連接節(jié)點的通信鏈路集.對任意e∈E,設(shè)e的權(quán)值為w(w1,w2,…，wn)，其中wi(1≤i≤n)∈R是權(quán)的第i個分量的值.

在定義限制函數(shù)之前,先定義一個輔助函數(shù):Boolean(表達(dá)式),當(dāng)表達(dá)式的值為真時,其值為1;當(dāng)表達(dá)式的值為假時,其值為0.

其中:m≤n;p1,p2,…,pr為無向賦權(quán)圖G中的一條路徑;Uk∈{w1,w2,…,wn}為權(quán)的某個分量;Uk(pj)為邊pj的權(quán)的Uk分量的值;vk∈R，1≤k≤m.

限制函數(shù)L給出了QoS的一組約束，限制所搜尋的路徑上的某些指標(biāo),如延時、距離等不超過某一上限.一般情況下，限制函數(shù)由路由器根據(jù)通信任務(wù)需要、網(wǎng)絡(luò)當(dāng)前資源狀況以及網(wǎng)絡(luò)狀態(tài)給出.

考慮一個網(wǎng)絡(luò)G〈V,E〉，組播源點s∈V,組播終點集D?{V-{s}}，N為組播終點集D的大小.T(s,D)表示從源節(jié)點s到終點集D的一顆組播樹，Li是一條從源節(jié)點s到第i個終點的路徑，1≤i≤N.QoS參數(shù)路由可以歸結(jié)為發(fā)現(xiàn)一組從s到D的路徑集T，并且T滿足如下2個約束：

2QoS組播路由的PBIL算法

2.1 PBIL算法及其擴(kuò)展

設(shè)s代表解的二進(jìn)制編碼，其長度為N，第i個基因位si(1≤i≤N)的取值為0或1；p=(p1,p2,…,pN)代表一個N維的概率向量，向量中各分量表示當(dāng)前種群中的個體在對應(yīng)基因位上不同取值時的學(xué)習(xí)概率；對于二進(jìn)制編碼的情況，pi(1≤i≤N)代表第i個基因位si取值為1時的學(xué)習(xí)概率；r是算法的學(xué)習(xí)速率;PM是變異率，染色體按PM概率隨機(jī)選擇部分pi進(jìn)行調(diào)整;rm是變異速率;M是種群規(guī)模.初始概率向量iniP中學(xué)習(xí)概率pi的大小都為0.5，即各基因位上取值為0或1的機(jī)會均等.

標(biāo)準(zhǔn)PBIL算法的處理流程如下：

/* Initialize Probability VectorP*/

for (i=1;ilt;=N;i++)pi=0.5;

while(Not Termination Condition)

{

/* Sampling and Evaluation */

for (i=1;ilt;=M;i++)

{

Individual [i]=Sample (P);

Fitness [i]=Evaluate(Individual [i])

}

BestIndividual=FindBestIndividual (Fitness);

/* RevisePtowards BestIndividual*/

for (i=1;ilt;=N;i++)

pi=pi*(1.0-r)+BestIndividual*r;

/* Mutate Probability Vector */

for (i=1;ilt;=N;i++)

if (Random(0,1)lt;PM)

{

pi=pi*(1.0-rm)+Random(0 or 1) *rm;

}

}

為了適應(yīng)任意整數(shù)編碼，文獻(xiàn)[7]對二進(jìn)制PBIL算法進(jìn)行了擴(kuò)展，本文則在此基礎(chǔ)上對算法進(jìn)行了改進(jìn)：保留進(jìn)化和學(xué)習(xí)過程中產(chǎn)生的最優(yōu)個體，用最優(yōu)個體來修正學(xué)習(xí)概率，并利用它產(chǎn)生新的個體.改進(jìn)后的整數(shù)編碼的PBIL算法如下:

/* Initialize Probability VectorP*/

for (i=1;ilt;=N;i++)

for (j=1;jlt;=L;j++)

pij=1/L;

while(Not Termination Condition)

{

/* Sampling and Evaluation */

for (i=1;ilt;=M;i++)

{

Individual [i]=Sample (P);

Fitness [i]=Evaluate(Individual [i])

}

BestIndividual=FindBestIndividual (Fitness);

BestEver=(BestEvergt;BestIndividual?BestEver:BestIndividual);

/* RevisePtowards BestEver*/

for (i=1;ilt;=N;i++)

piB=piB+ε(B:bestEver);

/* Mutate Probability Vector */

for(i=1;ilt;=N;i++)

if (Random(0,1)lt;PM)

{

piB=piB*(1.0-rm)+Random(0 or 1) *rm;

}

}

其中:ε為修正常數(shù);BestEver為到當(dāng)前代為止的最優(yōu)個體;其他符號與標(biāo)準(zhǔn)PBIL算法表的意義相同.

2.2 編 碼

在利用PBIL算法求解QoS組播路由問題中，如何將問題的解轉(zhuǎn)換為編碼表達(dá)的染色體是PBIL算法的關(guān)鍵問題.文獻(xiàn)[4]采用了一維二進(jìn)制編碼機(jī)制，這種編碼模式使得算法編碼、解碼過程復(fù)雜, 并且算法的搜索空間隨網(wǎng)絡(luò)規(guī)模的增大而急劇增大，算法效率很低.為克服編碼操作帶來的負(fù)面影響,本文采用整數(shù)編碼的方式,在該算法中，給定一個源節(jié)點s和一組目的節(jié)點D={d1,d2,…，dm}，PBIL算法的染色體可由長度為m的整數(shù)隊列組成，染色體的基因是s和di之間的路徑集Qi={p1i,p2i,…,pji,…,pki}中的路徑.其中:pji為目的為i的第j條路由;k為s和di之間的路徑數(shù)，群體中的每個染色體代表一棵多播樹.由于每個節(jié)點所對應(yīng)的路徑集中的路徑(根據(jù)前N條最短路進(jìn)算法[9])可能有重復(fù)，而且重復(fù)的次數(shù)不一樣，因此為便于后面的算法實施，對用前N條短路徑算法[9]所求得的路徑,根據(jù)概率進(jìn)行選取,并填充到Qi，使|Qi|=L，1≤i≤|D|，即所有路徑集的大小相同，L的大小根據(jù)具體情況而定.

因此，PBIL算法的染色體可由一系列整數(shù)隊列組成，即基于路徑表示的編碼方法，該方法既減少了編碼空間，也省略了解碼操作.染色體、基因和路徑的關(guān)系如圖1 所示.

2.3 初始群體的選擇

群體中的每個染色體代表一棵組播樹.首先，對于每個目的節(jié)點d∈D，利用前N條最短路徑算法[9]找出源節(jié)點s到d的所有滿足限制函數(shù)L的路徑，根據(jù)概率進(jìn)行選取填充到Qi，組成路徑集，作為PBIL算法編碼空間的備選路徑集.然后分別從每個路徑集Qi中隨機(jī)選一條路由組成一棵組播樹,作為初始群體的染色體.種群規(guī)模M根據(jù)具體情況由系統(tǒng)設(shè)定.

圖1 染色體的表示

2.4 適應(yīng)度函數(shù)

PBIL算法在進(jìn)化搜索中基本不利用外部信息，僅以適應(yīng)度函數(shù)為依據(jù)，利用種群中每個個體的適應(yīng)度值進(jìn)行搜索，適應(yīng)度函數(shù)直接影響到PBIL算法的收斂速度以及能否找到最優(yōu)解.因此，適應(yīng)度函數(shù)應(yīng)能反映被選個體的性能：性能好(滿足綜合QoS參數(shù)約束)的個體適應(yīng)度大, 性能差(不滿足QoS 約束或費用較大)的個體適應(yīng)度小.本算法的適應(yīng)度函數(shù)定義為

其中，?是正實系數(shù)，對于組播樹中的相同鏈路，其鏈路費用只計算1次.

2.5 變異操作

變異操作是一種基本操作，它在染色體上自發(fā)地產(chǎn)生隨機(jī)的變化.在PBIL算法中，變異操作可以提供初始種群中不含有的基因，或找回選擇過程中丟失的基因，為種群提供新的內(nèi)容.變異操作以一個較小的隨機(jī)概率改變個體字符串上的某些位，與種群的大小無關(guān).變異操作本身是一種局部隨機(jī)搜索，使PBIL算法具有局部的隨機(jī)搜索能力；同時使得PBIL算法保持種群的多樣性，以防止出現(xiàn)非成熟收斂.本文中，變異操作采用基本位變異[10]的方法，以變異概率PM隨機(jī)指定的某一位或某幾位基因位上的基因值隨機(jī)地選擇相應(yīng)的路徑集Qi中一個新的值進(jìn)行替換.

2.6 進(jìn)化程度的度量

基本PBIL 算法的終止條件是根據(jù)經(jīng)驗直接規(guī)定一個最大進(jìn)化代數(shù)，這是進(jìn)化計算中最簡單也是最常用的方法.但是對于不同類型和不同規(guī)模的問題而言，算法的收斂速度存在極大的差異，單憑經(jīng)驗很難確定合理的最大代數(shù)，更無法確切地判斷算法進(jìn)化的程度.通過對PBIL 算法進(jìn)化過程的分析可知，隨著進(jìn)化程度的逐步深入，各基因位上學(xué)習(xí)概率的大小從相同的初始值分別向0或1逼近.因此，衡量算法進(jìn)化程度等同于衡量各基因位上學(xué)習(xí)概率的分散程度，這就啟發(fā)我們可以根據(jù)進(jìn)化過程中各基因位上學(xué)習(xí)概率的取值變化來定量地評價算法當(dāng)前進(jìn)化的程度.

目前已有學(xué)者[7]提出,采用系統(tǒng)信息熵來度量學(xué)習(xí)概率的分散程度，以此估計算法進(jìn)化的程度.根據(jù)信息論的觀點，一個離散的隨機(jī)變量X代表一個單符號離散信源，離散信源的不確定性可采用信息熵E(X)來度量.結(jié)合PBIL算法給出它的描述：設(shè)個體有N個基因位，每個基因位上有L個允許的取值，Pij代表在基因位i上取第j個值的學(xué)習(xí)概率，則用于評價PBIL算法進(jìn)化程度的信息熵計算公式為

).

在進(jìn)化的初始階段，基因位上各取值的學(xué)習(xí)概率相等，此時pi=1/L，且系統(tǒng)熵值最大，即Emax=Eini=NlnL.隨著PBIL算法進(jìn)化的不斷進(jìn)行，各基因位的學(xué)習(xí)概率從最初的1/L分別向0或1靠近，系統(tǒng)的熵值E也從初始的iniE不斷減小，到最終趨于0.由此可見，PBIL算法的進(jìn)化過程也是系統(tǒng)熵值逐步下降的過程，通過系統(tǒng)的信息熵可以合理、準(zhǔn)確地估計算法的進(jìn)化程度.

上面討論了算法的各組成部分,下面給出其完整程序描述:

/* BestEver is the best solution overall all the generation;numVertices is the number of nodes in graphG;Nis the number of nodes inD; */

PBIL_QoSMCR(G(V,E),s,D)

{

for (i=1;ilt;=N;i++)

Qi={p1i,…,pji,…,pki};/*use the shortest path Dijkstra algorithm to find all pathes that satisfy the QoS metric from the source node to destination nodes */

//Initizations

for (i=1;ilt;=N;i++)

for (j=1;jlt;=L;j++)

pij=1/L;

while (Egt;0)

{

for (i=1;ilt;=M;i++)

{

Individual [i]=Sample(P);

Fitness[i]=Evaluate(Individual[i]);

}

BestIndividual=FindBestIndividual(Fitness);

BestEver= (BestEvergt;BestIndividual?

BestEver:BestIndividual);

//Update the Probability Vector

piB=piB+ε(B:BestEver)

//Mutate the Probability Vector

if (Random(0,1)lt;PM)

pi=pi*(1.0-rm)+Random[0,1]*rm;

Caculate(E);//caculate the entropyE

}

}

標(biāo)準(zhǔn)Dijkstra[11]算法的時間復(fù)雜度為O(N2),這里使用改進(jìn)后的前N條最短路徑算法[9].文獻(xiàn)[9]的算法復(fù)雜度為O(N3)，但是通常來說，QoS路由矩陣都很稀疏，所以采用最小優(yōu)先級隊列,此時時間復(fù)雜度為O(N2lgN).對于后面的遺傳算法，假設(shè)進(jìn)化代數(shù)為G，則時間復(fù)雜度為O(G*M).所以整個算法的關(guān)鍵在于前N條最短路徑算法的結(jié)果是否足夠優(yōu)良，使得遺傳算法能夠在找到足夠優(yōu)的解的情況下快速收斂.

3仿真實驗

仿真實驗采用劉瑩等[12]的例子，網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)如圖2 所示，節(jié)點隨機(jī)編號為1到10之間的數(shù)字，節(jié)點之間的綜合QoS費用在邊上標(biāo)出.實驗時進(jìn)行了簡化處理，假設(shè)源節(jié)點和目的節(jié)點之間的路徑都滿足限制函數(shù)L(因為可以對網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)先進(jìn)行精簡處理，使其都滿足限制函數(shù)L，這一步驟對實驗結(jié)果不會產(chǎn)生影響).在仿真實驗中，選源節(jié)點s為節(jié)點1、目的節(jié)點集D={4,6,7,8},做隨機(jī)實驗.

圖2 網(wǎng)絡(luò)拓?fù)鋱D

利用前N條最短路徑算法[9],計算出源節(jié)點到各目的節(jié)點之間的備選路徑集(L=5)，結(jié)果如表1所示.

表1 源節(jié)點到每個目的節(jié)點的備選路徑集

注：表中上標(biāo)數(shù)字為路徑出現(xiàn)的次數(shù).

在仿真實驗中，對PBIL算法參數(shù)，如種群規(guī)模、修正常數(shù)、終止條件、變異速率、選取多組值進(jìn)行實驗.結(jié)果發(fā)現(xiàn)：在相同條件下，種群規(guī)模越大，收斂率越高，最后趨于穩(wěn)定(收斂時的代數(shù)和種群規(guī)模無關(guān))；修正常數(shù)越小，收斂率越高，收斂時的代數(shù)也越大；變異率和變異速率的選取對算法避免早熟起決定性作用.表2、表3給出了2組不同參數(shù)下50次進(jìn)化的收斂率，第1組的修正常數(shù)ε取0.01，終止條件δ≤8%Eini，變異率PM取0.01，變異速率rm取0.001;第2組的修正常數(shù)ε取0.007，終止條件和變異率、變異速率不變.分別對種群規(guī)模取2，4，8，9，10進(jìn)行50次實驗，記錄了在滿足終止條件下，不同規(guī)模的種群在50次試驗中找到最優(yōu)解的次數(shù).實驗1在滿足終止條件下平均迭代80次，實驗2平均迭代113次，但是一般都在前4代就能找到最優(yōu)解，圖3是滿足綜合參數(shù)約束的最優(yōu)組播樹.

圖3 滿足綜合參數(shù)約束的最優(yōu)級組播樹

種群規(guī)模248910收斂率25/5035/5044/5048/5049/50

表3 ε=0.007,δ≤8%Eini下50次進(jìn)化的收斂率

4 結(jié) 論

本文提出了一種基于PBIL算法的綜合QoS參數(shù)的組播路由算法，該算法摒棄了傳統(tǒng)遺傳算法復(fù)雜的重組過程，避免了在重組過程中可能會破壞個體的構(gòu)造塊而產(chǎn)生連鎖問題，以致算法逼近局部最優(yōu)或早熟[13].引入了競爭學(xué)習(xí)的機(jī)制，以概率矩陣的方式通過采樣產(chǎn)生下一代群體，并保留了到當(dāng)前代為止的最優(yōu)個體，然后選擇最優(yōu)個體對概率矩陣進(jìn)行更新，直至最后收斂.仿真結(jié)果表明，該算法實施簡單，收斂速度顯著提高，并能以較大概率收斂到最優(yōu)解.另外，該算法還有以下特點：基于路徑的樹結(jié)構(gòu)編碼，簡化了編碼操作，省略了復(fù)雜的編碼解碼過程.因此，該算法在網(wǎng)絡(luò)規(guī)模較大時仍能得到很好的應(yīng)用.但是，由于采用了綜合QoS參數(shù)約束，特別是在網(wǎng)絡(luò)情況比較復(fù)雜的情況下，恰當(dāng)?shù)臋?quán)值變換函數(shù)很難給出.

[1]Li Layuan,Li Chunlin.A Multicast Routing Protocol with Multiple QoS Constraints[M]//Chapin L.Communication Systems:The State of the Art.Norwell:Kluwer AcademicPublisher Group,2002:181-198.

[2]包海潔，盧輝斌，欒慶林.基于遺傳算法的QoS組播路由算法的改進(jìn)[J].無線電通訊技術(shù)，2008，34(4)：1-3.

[3]Winter P.Steiner problem in networks:a survey[J].Networks，1987，17(2):129-167.

[4]Karp R M.Complexity of Computer Computations[M].New York:Plenum Press，1972:85-103.

[5]Baluja S.Population-Based Incremental Learning:A Method for Integrating Genetic Search Based Function Optimization and Competitive Learning[R].Pittsburgh:Carnegie Mellon University,1994.

[6]Hoehfeld M，Rudolph G.Towards a Theory of Population-Based Incremental Learning[C]//Proceedings of the 4th IEEE Conference on Evolutionary Computation.Piscataway NJ:IEEE Press,1997:1-5.

[7]李二森，郭海濤，張保明，等.PBIL算法在遙感影像匹配中的應(yīng)用[J].武漢大學(xué)學(xué)報:信息科學(xué)版，2008，33(2)：140-143.

[8]鄒陽，寧卓，許道云,等.面向QoS的路由數(shù)學(xué)模型及求解[J].貴州大學(xué)學(xué)報:自然科學(xué)版，2000，17(4)：258-263.

[9]柴登峰，張登榮.前N條最短路徑問題的算法及應(yīng)用[J].浙江大學(xué)學(xué)報:工學(xué)版，2002，36(5)：531-534.

[10]周明，孫樹棟.遺傳算法及應(yīng)用[M].北京：國防工業(yè)出版社，1999.

[11]Thomas H C,Charles E L,Ronald L R.Introduction to Algorithms[M].Cambridge;MA:MIT Press,1990.

[12]劉瑩，劉三陽.多媒體通信中帶度約束的多播路由算法[J].計算機(jī)學(xué)報，2001，24(4)：367-372.

[13]Harik G R,Goldberg D E.Learning Linkage[M]//Belew R K,Vose M D.Foundations of Genetic Algorithms.San Francisco:Morgan Kaufmann Publishers Inc,1997:247-262.

(責(zé)任編輯 陶立方)

TheQoSmulticastroutingalgorithmbasedonPBIL

CHEN Jianming

(CollegeofMathematics,PhysicsandInformationEngineering,ZhejiangNormalUniversity,JinhuaZhejiang321004,China)

A new QoS multicast routing optimization algorithm was proposed based on PBIL algorithm which would help to find a low-cost multicast routing tree with integrated QoS parameter constraint. The PBIL algorithm combined genetic algorithm and competitive learning effectively and would be efficient in large scale networks by tree structure coding scheme based on path and prepared path set based on probability. Verified simulation showed this algorithm with efficiency and effectiveness.

Steiner tree; Quality of Service; group broadcast; genetic algorithm; Population-Based Incremental Learning algorithm

1001-5051(2010)01-0070-05

2009-11-09

浙江省科技廳科研項目(2009C31118)

陳建明(1957-)，男，浙江諸暨人，副教授.研究方向：信息安全.

TP391

A