基于PBIL的綜合QoS參數組播路由*

陳建明

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

基于PBIL的綜合QoS參數組播路由*

陳建明

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

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

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

0引言

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

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

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

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

1QoS組播路由模型

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

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

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

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

限制函數L給出了QoS的一組約束，限制所搜尋的路徑上的某些指標,如延時、距離等不超過某一上限.一般情況下，限制函數由路由器根據通信任務需要、網絡當前資源狀況以及網絡狀態給出.

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

2QoS組播路由的PBIL算法

2.1 PBIL算法及其擴展

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

標準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;

}

}

為了適應任意整數編碼，文獻[7]對二進制PBIL算法進行了擴展，本文則在此基礎上對算法進行了改進：保留進化和學習過程中產生的最優個體，用最優個體來修正學習概率，并利用它產生新的個體.改進后的整數編碼的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;

}

}

其中:ε為修正常數;BestEver為到當前代為止的最優個體;其他符號與標準PBIL算法表的意義相同.

2.2 編 碼

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

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

2.3 初始群體的選擇

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

圖1 染色體的表示

2.4 適應度函數

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

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

2.5 變異操作

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

2.6 進化程度的度量

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

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

).

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

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

/* 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

}

}

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

3仿真實驗

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

圖2 網絡拓撲圖

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

表1 源節點到每個目的節點的備選路徑集

注：表中上標數字為路徑出現的次數.

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

圖3 滿足綜合參數約束的最優級組播樹

種群規模248910收斂率25/5035/5044/5048/5049/50

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

4 結 論

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

[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].無線電通訊技術，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算法在遙感影像匹配中的應用[J].武漢大學學報:信息科學版，2008，33(2)：140-143.

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

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

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

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

[12]劉瑩，劉三陽.多媒體通信中帶度約束的多播路由算法[J].計算機學報，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.

(責任編輯 陶立方)

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