一種求解ＱｏＳ約束組播路由問題的遺傳算法
2007-01-01 00:00:00楊云陶筆蕾徐佳劉鳳玉
計算機應用研究 2007年2期
摘 要：針對多維QoS約束的組播路由問題，提出了一種基于遺傳算法的解決方案QCMRA-GA（GA of QoS Constraints Multicast Routing Algorithm）。該算法對經典遺傳算法的三大算子進行了重新設計，有效地克服了遺傳算法的早熟現象。對染色體進行Prufer樹型編碼，可以避免回路的產生，并根據編碼特性，進行基于葉子節點和Steiner節點的解空間壓縮，提高了算法的收斂速度。實驗表明QCMRA-GA的正確性和效率性。
關鍵詞：組播路由；QoS約束；遺傳算法；收斂性
中圖法分類號：TP393; TP301.6文獻標識碼：A
文章編號：1001—3695(2007)02—0292—04
隨著計算機網絡應用日益廣泛，視頻會議、視頻點播、遠程教學和CSCW協同計算等多媒體業務的不斷出現，通信質量要求也越來越高，QoS組播路由技術已成為網絡信息傳輸的一項關鍵技術，它可以有效地利用網絡帶寬。而基于多個不相關可加度量的QoS組播路由問題是NPC完全問題，不少學者提出了啟發式算法，如BSMA[1]，DVMA[2]，MRPMQ[3]等。但這些算法不是過于復雜，不適用于大型網絡，就是計算復雜度太高，效率不太好。1975年Holland提出了基于生物演化的遺傳算法[4]，遺傳算法便廣泛運用于解決組合優化問題，取得了許多成果。在應用遺傳算法解決QoS組播路由問題時，一般方法很容易產生回路或生成的不是一棵樹（森林、圈），一些文獻并沒有給出解決方案[5，6]，而有些需要額外的連接零散子樹的操作[7，8]使得算法過于復雜。文獻[9]提出了一種遺傳算法的解決方案，然而使用單點交叉和單點變異的遺傳操作，使得算法收斂速度不快或容易陷入局部解。
本文采用遺傳算法解決具有QoS約束的組播路由問題，提出了QCMRA-GA算法，算法中對染色體采用Prufer編碼方式，以保證組播樹中不會出現回路或森林。雙輪盤賭方式的選擇算子、自適應的交叉、變異算子和基于生物體新陳代謝的免疫算子，可以加速算法的收斂速度而不會陷入局部解，最終求得滿足QoS要求的最佳解或非劣解。
1 多QoS約束組播路由問題的網絡模型
2 QCMRA-GA算法
設組播樹中目標節點的集合為M，Steiner節點的集合為St，則基本節點集S={s}∪M。最優Steiner樹實質上是包含基本節點和Steiner節點的最小生成樹，這是個NP完全問題。求解最優Steiner樹的關鍵在于確定包含在最優Steiner樹中除基本節點集S之外的Steiner節點。為此，QCMRA-GA由兩層遺傳算法構成:外層遺傳算法用來生成包含基本節點和Steiner節點的子圖，并給出包含St∪S中所有節點且滿足QoS約束的組播樹；內層遺傳算法用于搜索各子圖中的最小生成樹。
2.1 外層遺傳算法
外層遺傳算法采用二進制串對集合V-S中的所有節點進行編碼，初始種群隨機生成，簡要描述如下：
（1）染色體編碼。采用二進制編碼，1表示該節點作為Steiner節點，0表示該節點不是Steiner節點，這樣每個二進制碼可對應由位為1的Steiner節點和基本節點構成的一個子圖。
（2）交叉與變異。交叉與變異采用染色體單點交叉與單點隨機變異的方式。
（3）適值計算。與內層遺傳算法相同。
（4）選擇。采用(μ+λ)選擇方式。
（5）終止條件。指定終止代數或在特定代數內個體沒有進化。
2.2 內層遺傳算法
內層遺傳算法是整個算法的關鍵。根據文獻[10]，具有變異概率Pm∈(0，1)，交叉概率Pc∈[0，1]，同時采用比例選擇法且在選擇前保留當前的最優解的遺傳算法可收斂到全局最優解。然而，在帶有隨機性的交叉和變異算子作用下，新產生的種群存在發生退化的可能。本文根據免疫學原理[11]，在經典遺傳算法三個算子的基礎上加入一個免疫算子，定期給當代種群接種疫苗，這樣可加快進化速度；采用Prufer樹型編碼，避免了回路和森林的干擾；在進入遺傳操作前，對隨機圖針對葉子節點和Steiner節點進行縮減，可降低算法的搜索空間；在遺傳操作上，采用雙輪盤賭的選擇機制和自適應交叉及變異算子，保護優良個體，減少優良基因遭到破壞的幾率。QoS約束組播路由內層遺傳算法描述為
（1）染色體編碼。染色體采用Prufer編碼方式[12]，使用Prufer 數編碼樹是端點編碼法中的一種。圖論中Cayley定理說明：在一個有n個節點的完全圖中有nn-2個不同的樹。Prufer對基于這類樹和n-2個數字的所有排列的集合一一對應關系給出了Cayley定理的結構化證明。這表明如果樹有n個節點，那么，其Prufer數的長度為n-2。Palmer和Kershenbaum指出，Prufer數的任意一個數字發生變化，相應的樹結構都會發生意想不到的變化[13]，因此采用Prufer編碼能夠保證種群的多樣性，避免陷入局部解。
（2）初始化種群。初始化種群主要有以下四步：
①生成網絡隨機圖。
②壓縮解空間。Prufer編碼的一個重要性質是生成樹的葉子節點肯定不會出現在Prufer數中，而Steiner節點肯定出現在Prufer數中。這樣，在初始化種群時，只需生成不含葉子節點且必定含有Steiner節點的染色體。如果判斷出p個節點是葉子節點(p
③在經過壓縮的解空間內隨機生成滿足上述要求的父代染色體群，作為初始種群。
④刪去不滿足第1節中條件（3）要求的鏈路，使圖中任意一條鏈路均滿足預定帶寬的要求，如果此時的拓撲圖成為一個非連通的網絡，則應與終端用戶協商，以確定一個合理的最小帶寬。
（3）適應度計算。對于每一個多播樹T，適應度函數定義為其代價函數的倒數，即f(T)=1C(T)=1e∈TC(e)(1)
（4）選擇機制。選擇操作采用雙輪盤賭方式。一般的遺傳算法采用輪盤賭法或(μ+λ)法，單輪盤賭選擇方法的明顯缺點是缺乏群體間競爭，使得收斂速度大大降低。(μ+λ)選擇法可以加快收斂速度，卻使得高適應度的個體受到過多保護，易陷入局部解；而采用雙輪盤賭的選擇機制，既加快了收斂速度又維持了種群中個體的多樣性，避免陷入局部解。我們分別在父代種群和子代種群中按比例用輪盤賭方法選擇一定數量的個體，將兩者合并構成下一代種群。這樣產生的種群既保持了其多樣性，又使得父代種群和子代種群中的優秀個體得到保護，有利于收斂到最優解。
（5）疫苗的提取和更新。生物體由于機體本身的新陳代謝，每天有5%的低激勵值細胞死亡，而代之以從骨髓中生成的全新細胞，而且新生成的細胞只有具有較強適應性的才能融合到免疫系統中。模擬免疫行為中細胞的這種現象，算法中找出5%高適應度的個體作為疫苗以作用于下一代群體。疫苗的初始提取是在初始群體中選擇適應度前5%的個體，每當產生新一代種群時，如果新種群中存在適應度更高的個體，則取代當前疫苗中的相應個體，這種操作稱為疫苗更新。
（6）交叉算子。在交叉操作前，提取當代種群中最優的個體，它將不參與交叉和變異操作，直接復制到下一代種群中。交叉率的確定采用文獻[14]提出的自適應交叉方法，它能根據個體適應度和種群的平均適應度動態地確定交叉概率Pc，既保護了優良個體又能使種群在解空間中充分發散。具體方法為
交叉方法采用一致交叉，即染色體位串上的每一位按相同概率進行隨機均勻交叉。一致交叉算子生成的新個體為
式中x是取值為[0，1]上符合均勻分布的隨機變量。
（7）變異算子。由于Steiner節點將肯定出現在Prufer數中，則不能對度為2的Steiner節點進行變異，否則該個體將變得無意義。Prufer數的另一個重要性質是體現了節點度的信息，即節點在Prufer數中出現的次數為該節點的度減1。那么就可以通過變異使生成樹滿足度約束的要求。其次，對不滿足時延約束的個體進行變異，使其滿足約束。變異率的確定也采用自適應變異方法，取k1=0.038 2，k2=0.061 8。
（8）接種疫苗。在當代種群中找出5%低適應度的個體，如果這些個體的適應度低于疫苗中相應個體的適應度，則按先前提取的疫苗對這些個體進行取代，使得到的個體具有較高的適應度，加快收斂速度，否則保持該個體不變。在接種疫苗后，更新疫苗，保持疫苗的優良性。
（9）終止條件。采用進化到一定的代數后終止或在特定代數內沒有更優解出現則終止。
3 QCMRA-GA算法分析
性質1 QCMRA-GA算法選擇的組播樹不存在回路和森林。由于Prufer對有n個節點的圖中所有的樹和n-2個數字的所有排列的集合一一對應關系給出了Cayley定理的結構化證明，即在Prufer數中包含且僅包含nn-2 棵樹所對應的數字排列，因此采用Prufer編碼的QCMRA-GA算法不存在回路和森林等不同于樹的結構。
性質2 QCMRA-GA算法選擇的組播樹一定是一棵Steiner樹。在QCMRA-GA算法的外層遺傳算法中，我們對網絡中除基本節點以外的節點進行編碼，構成的是一個包含基本節點和Steiner節點的子圖。由于在內層遺傳算法中，采用Prufer的編碼方式，根據性質1，QCMRA-GA算法選擇的組播樹一定是一棵Steiner樹。
性質3 QCMRA-GA算法的時間復雜度為O(G×N×L)。設G為進化代數，N為種群大小，L為染色體長度，Pc為交叉率，Pm為變異率。則選擇操作的時間復雜度為O(G×N×L)，交叉操作的時間復雜度為O(G×N×Pc)，變異操作的時間復雜度為O(G×N×Pm)，免疫操作的時間復雜度為O(G×N×0.05)。綜上可知，QCMRA-GA算法復雜度為O(G×N×L)，算法的計算復雜度主要由進化代數、種群大小和染色體長度決定。
4 仿真與性能分析
為了驗證算法的各項性能，筆者進行了仿真。試驗在P42.8GHz，內存256MB的PC機上進行，網絡模型采用經典的Waxman隨機圖模型[15]，節點之間的歐幾里德距離作為費用，節點間的連通性由連通概率P(u，v)決定，P(u，v)的值由u，v之間的距離d (u，v)決定：P(u，v)=β exp-d(u，v)Lα
其中L為節點間最大距離值，α和β是調節隨機圖特征的參數。當α增加時，長邊相對短邊的比增加；當β增加時，節點的度隨之增加。α和β為(0，1)內的數。
4.1 算法的正確性
我們首先利用Waxman隨機圖模型產生出如圖1所示的一個8節點網絡圖，圖中每條鏈路的時延均勻分布于2ms—15ms之間，帶寬均勻分布于30MB—150MB之間。每條鏈路可用一個三元組e(C，D，B)表示，其中，C表示代價，D表示時延，B表示帶寬。假如QoS協商參數Δdelay=7，Δbandwidth=100，那么QCMRA-GA共搜索到四棵滿足要求的組播樹，圖2是其中的一棵組播樹。其收斂性能如圖3所示。
4.2 算法的收斂性比較
測試算法產生組播樹的代價與運行代數的關系，并將結果與典型的基于遺傳算法的GAVCMR[16]，MCMGA[17]以及文獻[5]所述算法進行了比較。為便于比較，采用與文獻[5]相同的網絡模型和參數設置，分別取Δdelay=6和7，群體規模Npop=40，最大運行代數為500，試驗進行500次。圖4顯示的是Δdelay=6時算法的收斂性，GAVCMR、文獻[5]以及MCMGA收斂到最優解的平均進化次數分別為69次、89次和100.5次，而QCMRA-GA只需48.5次，分別提高29.7%，45.5%和51.7%。而當Δdelay=7時，圖5給出了這四種算法的收斂性比較，GAVCMR、文獻[5]以及MCMGA收斂到最優解的平均進化次數分別為160次、220次和280次，QCMRA-GA為106.7次，分別提高33.3%，51.7%和61.9%。
4.3 算法的成功率
本文測試了在不同進化代數下，算法收斂到最優解的成功率，并與文獻[5]所提算法進行了比較。采用文獻5的網絡模型，取Δdelay=6，Npop=40，Δbandwidth=100，實驗進行了500次，結果如表1所示。從表中可看出進化代數在100以內時，文獻[5]的算法成功率只有33.3%，而本文算法達到90.2%，證明本文算法的收斂速度明顯優于文獻[5]的算法。在其他進化代數情況下，本文算法的成功率也有不同程度的提高。
4.4 算法的可擴展性
為了測試QCMRA-GA在大型網絡中的性能，我們采用Waxman隨機圖模型將網絡節點數從20擴展到80，基本節點數固定為8，其余節點為候選Steiner節點，試驗進行100次，并與GA-Based[18]、MCMGA以及文獻[9]提出的算法進行了比較，結果如圖6所示。可以看出，隨網絡節點數的增加，搜索空間增大，四個算法的進化代數都增加，但本文算法的平均進化代數要明顯小于另外三種算法。
4.5 壓縮性能
由于本文算法在進入遺傳操作之前，對網絡模型進行了針對葉子節點和Steiner節點的縮減，使得進化效率大大加強。為證明該結論，我們將本算法與文獻[9]沒有進行壓縮步驟的算法進行了比較。結果如圖7所示。從圖中可以看出，在網絡節點數相同的情況下，本文算法的收斂速度要優于文獻[9]不采用縮減的算法。
5 結論
本文提出了一種求解QoS約束組播路由問題的遺傳算法QCMRA-GA，該算法主要有以下優點：①算法可以保證生成一棵Steiner樹，而不會出現回路或森林，免去了額外的連接零散子樹的操作，大大減少了計算量。②在算法進入遺傳操作前，進入縮減步驟，有力地壓縮了解空間。③采用雙輪盤賭的選擇機制，既保持了種群的多樣性，又使得父代種群和子代種群中的優秀個體得到保護，有利于收斂到最優解。④自適應交叉、變異算子和基于生物體新陳代謝的免疫算子，加快了收斂速度。仿真表明本文提出的算法簡化了操作，縮減了搜索空間，加快了收斂速度，是一種快速、有效的多QoS約束組播路由算法。
本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。
