一種基于計算智能的組播路由算法

劉　杰，王　振，馮志先，杜軍平

(1. 中國電子科技集團公司第三十研究所，四川 成都 610041；2.國家國防科技工業局信息中心， 北京100039;

3.北京郵電大學 計算機學院，北京 100876)

摘　要：在通信網絡中，多約束組播通信是提高網絡運行效率和服務質量的重要途徑。一些啟發式的算法已經被用來解決多約束條件下的組播路由問題，如模擬退火算法，遺傳算法，蟻群算法和粒子群優化算法等。然而，這些算法在求解多約束組播路由問題時存在收斂速度低和計算復雜度高的問題。螢火蟲群優化(GSO)算法是一種近期在計算智能領域出現的卓越算法，它可以在一定程度上解決多約束組播樹生成過程中收斂速度低和計算復雜度高的問題。提出了一種基于GSO的多約束組播樹生成算法(GSO-MCM)。該算法可有效生成滿足多約束要求的組播路由樹。仿真結果表明提出的GSO-MCM算法在求解和收斂速度，以及網絡規模適應性方面均有良好的性能。

關鍵詞：多約束；組播路由；螢火蟲群優化；計算智能

doi:10.3969/j.issn.1002-0802.2015.06.014

一種基于計算智能的組播路由算法

劉杰1，王振2，馮志先1，杜軍平3

(1. 中國電子科技集團公司第三十研究所，四川 成都 610041；2.國家國防科技工業局信息中心， 北京100039;

3.北京郵電大學 計算機學院，北京 100876)

摘要：在通信網絡中，多約束組播通信是提高網絡運行效率和服務質量的重要途徑。一些啟發式的算法已經被用來解決多約束條件下的組播路由問題，如模擬退火算法，遺傳算法，蟻群算法和粒子群優化算法等。然而，這些算法在求解多約束組播路由問題時存在收斂速度低和計算復雜度高的問題。螢火蟲群優化(GSO)算法是一種近期在計算智能領域出現的卓越算法，它可以在一定程度上解決多約束組播樹生成過程中收斂速度低和計算復雜度高的問題。提出了一種基于GSO的多約束組播樹生成算法(GSO-MCM)。該算法可有效生成滿足多約束要求的組播路由樹。仿真結果表明提出的GSO-MCM算法在求解和收斂速度，以及網絡規模適應性方面均有良好的性能。

關鍵詞：多約束；組播路由；螢火蟲群優化；計算智能

doi:10.3969/j.issn.1002-0802.2015.06.014

收稿日期：2015-01-21；修回日期：2015-04-30Received date:2015-01-21；Revised date：2015-04-30

中圖分類號：TP393

文獻標志碼：碼：A

文章編號：號：1002-0802(2015)06-0699-06

Abstract：In communication networks, the multi-constraint multicast communication is an important way to improve the efficiency of network operation and QoS(Quality of Service). Some heuristic algorithms are applied to solving multicast routing problem under multiple constraints, such as simulated annealing, genetic algorithm, ant colony algorithm and particle swarm optimization algorithm. However, problems of low convergence rate and high computational complexity still exist in these algorithms when solving multi-constraint multicast routing problems. GSO (Glowworm Swarm Optimization) algorithm is a promising algorithm recently emerging in the area of computational intelligence, and it can overcome the above deficiencies to some extent. Meanwhile,GSO-MCM algorithm based on GSO is proposed to efficiently generate multicast routing tree and meet multi-constraint requirements. Simulation result shows that GSO-MCM algorithm enjoys good performance in solution, rate of convergence and adaptability of network size.

作者簡介：

Multicast Routing Algorithm based on Computational Intelligence

LIU Jie1,WANG Zhen2,FENG Zhi-xian1,DU Jun-ping3

(1.No.30 Institute of CETC, Chengdu Sichuan 610041,China；

2.Information Center of State Administration of Science Technology and Industry for National Defense,Beijing 100039,China;

3.School of Computer, Beijing University of Posts and Telecommunications,Beijing 100876,China)

Key words：multi-constraint, multicast routing, GSO, computational intelligence

0引言

隨著網絡和多媒體技術的飛速發展，網絡多媒體服務，如計算機會議，遠程教育，協同工作已逐漸成為互聯網活動的主流。組播通信相比于單播通信，在多點數據傳輸方面更為有效[1]。組播通信的關鍵是要建立組播路由。不同于單播通信，組播通信需要生成組播樹[2]。

現有的研究表明，有很多方法可以解決無約束的組播路由問題，如Dijkstra算法和Steiner樹方法[3]。然而，這些傳統的方法卻不能解決多約束條件下的組播路由問題[4]。組播問題通常對服務質量(QoS)有著嚴格的要求，其參數包括帶寬、時延及時延抖動等。因此，如何快速建立組播路由并滿足服務質量的要求是一項重要而緊迫的研究課題。

解決多約束組播路由問題的關鍵是生成可滿足多約束條件的組播樹，但求解一棵最優組播樹已經被證明是一個NP完全問題[5]。所以，通常采用啟發式算法來求解。目前，多約束組播路由問題已經引起了廣泛的關注，許多研究人員通過使用不同的啟發式算法來解決該問題[6-7]。

目前，主要使用啟發式算法來解決多約束組播路由問題，如模擬退火算法、遺傳算法、蟻群算法、粒子群優化算法等[8-9]。然而，這些算法在求解多約束組播路由問題時存在收斂速度慢和計算復雜度高的問題[10]。螢火蟲群優化(GSO)算法[11]是一種近期在智能計算領域出現的卓越算法，與上述啟發式算法相比，它具有更快的收斂速度和較低的計算復雜度[12-14]。本文提出了一種基于GSO的多約束組播樹生成的算法(GSO-MCM)，該算法可以有效地生成組播路由樹，盡可能滿足多約束條件。

本文的貢獻包括：①提出了一種基于螢火蟲群優化算法的多約束組播樹生成算法GSO-MCM；②建立與QoS評價尺度相對應的約束條件和開銷函數(涉及時延、時延抖動、吞吐量和分組丟失率)。在提出的GSO-MCM算法中，設計了一個去除環路的功能，該功能使組播樹編碼方法具有更好的適用性。與其他啟發式算法相比，GSO-MCM算法能夠在組播樹迭代生成過程中更快地滿足網絡多約束條件。通過一個具有200個節點的網絡拓撲仿真實驗，驗證了GSO-MCM算法的有效性。

本文的結構如下：首先介紹了多約束組播路由問題的背景。然后介紹了提出的GSO-MCM算法的細節。接著給出了GSO-MCM的仿真分析。最后總結了全文，并為今后的工作提供了有價值的建議。

1GSO-MCM算法

對于建立一棵受多種約束條件限制的組播樹來說，應該花費最小的成本并達到一定的服務質量。同時，多約束條件下的網絡模型有許多參數和可用路徑，使得組播樹生成算法可能生成滿足多個QoS指標的組播路由樹。在QoS指標中，時延、延遲抖動、吞吐量和丟包率分別由Dereq、DJreq、Threq、PLRreq來表示。

建立組播路由樹的傳統解決方法是從組播源節點找到到每個目的節點的路徑集合，然后將這些路徑合并為一棵組播樹[15]。然而，上述方法效率較低且計算復雜度高。為了克服這些缺點，本文提出了一種基于螢火蟲群優化的組播路由樹生成算法。

螢火蟲群優化算法(GSO)是一種新型的群智能優化算法。該算法模擬螢火蟲的自然發光特性，通過比較目的熒光值大小的方式實現信息交換。該算法具有參數少的特點，從而使操作更簡單和穩定性更加。

(1)組播樹編碼

首先，對組播樹進行編碼來作為GSO算法搜索空間中的個體。這里，需要考慮到編碼和解碼的適用性。關鍵是要避免的組播樹中的環路。給定一棵組播樹X，具體的編碼方法如下所示：

X=(Prior1,Prior2,…,Priorn)

(1)

式中，X為一棵組播樹，Priori表示第i個節點的先驗節點。對于不屬于組播樹節點的先驗節點，統一用“0”來表示。源節點的先驗節點是其本身。

組播樹編碼方法的具體流程如下所述：

步驟1：初始化一棵空的組播樹X=(01,02,…,0n)。

步驟2：將源節點的先驗節點設置為其本身，即X=(01,02,…,Ss,…,0n)。

步驟3：從目的節點集合中隨機選擇一個目的節點作為當前節點。

步驟4：從與當前節點有連接關系的節點集合中刪除最近后繼節點。則可以生成當前節點的先驗節點集合。

步驟5：從當前節點的先驗節點集合中隨機選擇一個節點作為當前節點的一個先驗節點。然后將選擇的先驗節點設置為當前節點。

步驟6：如果當前節點的先驗節點集合為空，即為“0”，轉步驟4，否則轉步驟7。

步驟7：如果所有目的節點的先驗節點集合為空，即為“0”，轉步驟8，否則轉步驟3。

步驟8：輸出該組播樹的編碼。

組播樹編碼方法的流程圖如圖1所示。

圖1組播樹編碼方法的流程

(2)組播樹的合并

在傳統的GSO算法中，螢火蟲i移動到螢火蟲j是依據下式完成的：

(2)

式中，i表示要發生位置移動的個體，j表示按照概率大小選擇的熒光素值高的個體，即個體i逐漸靠近的目標個體，s表示移動步長，xi(t)表示個體i移動前的位置，xi(t+1)表示個體i移動后的位置。

在多約束條件下QoS組播樹生成過程中，我們對式(2)進行改造，使其能適應組播樹的生成。在GSO-MCM中，螢火蟲i移動到螢火蟲j依據下式完成：

Xi(t+1)=Xi(t)⊕Xj(t)

(3)

式中，算子⊕定義如下：組播樹xi(t)和xj(t)合并為一棵新的組播樹。但是在合并過程中可能會產生環路。為了消除這些環路，新生成的組播樹需要利用前面提出的組播樹編碼方法再編碼一次。具體偽代碼如下：

fori=1 to length(E) //E 表示目標節點集合

current= E(i);

while current≠S //當前節點不等于源節點

if(count_prior(E(i))>1) // count_prior表示先驗節點的數量

current=random_select(E(i)); //隨機選擇一個先驗節點作為當前節點

else

current= prior(E(i));

end

end

end

經過上述去環路處理后，新生成的組播樹xi(t+1)就可以去除環路。

(3)GSO-MCM的動態決策范圍和鄰居點集合

為了解決多約束條件下的組播路由問題，還需要對GSO算法的動態決策范圍和鄰居點集合進行改造。

關于動態決策范圍，由于在組播樹中動態決策范圍rs是固定的。所以在GSO-MCM中不用進行rs的更新。此外，GSO-MCM中rs的度量單位不是一般的距離，而是組播樹個體之間的相似度。該相似度定義為組播樹個體之間相同先驗節點的數量。一般情況下，rs的大小被設定為全網絡范圍的一半。

關于個體的鄰居點定義如下：

Ni(t)={j:same(xj(t),xi(t))>rs;li(t)

(4)

式(4)中，lj(t)表示個體j的熒光素值，li(t)表示個體i的熒光素值，式(4)所示個體i的鄰居點j的含義是i和j之間的相似度大于rs，且個體j的熒光素值要高于個體i的熒光素值。

(4)GSO-MCM算法的具體流程

步驟1：初始化階段。

輸入針對不同業務類型的網絡拓撲結構G。在路由優化目標函數的可行域內隨機設置N個螢火蟲個體。這些螢火蟲個體擁有相同的初始熒光素值l0和相同的初始動態決策域值r0。初始化移動步長s，鄰居點數量閾值nt，熒光素消失率ρ，熒光素更新率γ，螢火蟲感應范圍rs，最大迭代次數t，以及組播樹路由優化中的約束條件Dereq、DJreq、Threq、PLRreq。

步驟2：預探測階段。

不滿足組播樹丟包率約束條件的節點將會被刪掉，與這些節點相連的邊也會被刪掉。同時，不滿足時延、時延抖動和吞吐量的邊也會被刪掉。

步驟3：更新螢火蟲i的熒光素值。

步驟4：搜索螢火蟲i的鄰居。

步驟5：決定螢火蟲i的移動方向。

步驟6：更新螢火蟲i的位置。

步驟7：若達到了給定的精度或達到了算法迭代的次數，則算法停止。否則轉入步驟3。

GSO-MCM算法的流程圖如圖2所示。

圖2　組播樹編碼方法的流程

多約束組播樹生成算法的時間復雜度如下。假定目的地節點的數目是n，以及鏈接的數量是v。在組播樹編碼步驟中，時間復雜度為O(nv2)。在組播樹合并步驟中，重新編碼需要消除環路，所以復雜度為O(nv2)。它還需要將邊加入到組播樹中，這樣網絡中的所有節點都被訪問，所以時間復雜度為O(v)。在迭代過程中，假設迭代次數為k。因此，整個生成過程的時間復雜度為O(knv2+kv)。

2仿真結果和分析

本文提出的算法通過Visual C++ 6.0實現，仿真實驗運行在配置有英特爾雙核2 GHz、2 GB內存和Windows XP操作系統的機器上。在實驗中使用的網絡拓撲是根據文獻[16]的方法隨機產生的。本文使用一個包含200個節點的拓撲結構。組播組目的節點的比例介于10%和30%。最大端到端時延設置為120 ms，延遲抖動設置為60 ms，運行程序100次，得到仿真實驗的平均結果。

在仿真實驗部分，使用收斂速度和組播樹的開銷作為評價標準。收斂速度包含兩個部分：收斂時間和收斂概率。組播樹開銷是4個約束條件(Dereq,DJreq,Threq,PLRreq))的組合。組播樹開銷的計算式如下：

(5)

在仿真實驗及實際應用中，熒光素值與開銷函數值呈反比例關系，其計算式如下：

li=1/cost(t)

(6)

GSO-MCM算法的參數設置如表1所示。

表1　GSO-MCM算法的參數設置

本文將GSO-MCM與本領域著名的幾種算法進行比較，如基于粒子群優化的組播(PSO)、基于模擬退火的組播(SA)、基于多目標蟻群的組播(MOACS)、基于最大最小蟻群的組播(MMS)和基于樹的蟻群優化(NACO)等[1]。圖3顯示了不同網絡拓撲規模下上述各算法的收斂時間的比較結果。

圖3不同拓撲規模下各算法收斂時間的比較

從圖3 中可以看出GSO-MCM具有最佳的收斂時間。但是，當網絡節點的規模很小的時候，相比較算法的收斂時間的差異都很小。節點數量越多，GSO-MCM算法比其他算法的收斂時間越好。可能的原因是：①NACO、PSO、SA、MOACS和MMS算法對一些特殊的組播組節點有特殊的規則，且在初始階段會花費大量時間；②在發現從源節點到每個目的節點的路徑之后，有一個路徑合并的操作，這將導致NACO、PSO、SA、MOACS和MMS算法的收斂時間過高；③拓撲規模的增加，使得NACO、PSO、SA、MOACS和MMS算法在算法收斂上可能會花費更多的時間，因為為了找到從源節點到目的節點的路徑，需要訪問更多的網絡節點。

通過實驗發現，不僅是拓撲規模，目的地節點的數目也要影響算法的性能。為了測試這種影響，在仿真實驗中選擇具有200個節點的拓撲結構中的2%到 30%的節點作為組播組成員。圖4顯示了不同比例的組播組成員節點組播樹開銷的結果比較。

圖4　不同組播組成員比例的組播樹開銷比較

從圖4中可以看出當組播組節點的比例為4%以下時，GSO-MCM算法的開銷與其他相比較的算法性能相近。然而，隨著組播組節點的比例增大到4%以上后，GSO-MCM算法的性能大幅提高。這是由于當組播組節點的比例很小時，組播樹可能近似從源節點到每個目的節點的單播路由。因此，當組播組節點的比例為4%以下時NACO、PSO、SA、MOACS和MMS算法的性能也很好。然而，當組播組節點的比例增加時，與其他算法相比GSO-MCM算法可以快速改善組播樹的開銷性能。

在時間復雜度比較方面，PSO、SA、MOACS和MMS算法的時間復雜度為O(nv3)， NACO算法的時間復雜度為O(nv2)[1]。這表明，本文提出的GSO-MCM算法具有比PSO、SA、MOACS和MMS算法更好的時間復雜度和與NACO算法相同的時間復雜度。

在仿真實驗設置中，每個鏈路的時延測量值是0 ms和30 ms。時延約束被設置為300 ms和時延抖動設置為70 ms。圖5表明當迭代的最大次數變化時平均收斂概率的差異。從圖5中可以看出，對于該實驗設置的具有200個節點的網絡拓撲來說，迭代的次數在15以下時算法就可以收斂。也就是說，當迭代次數的最大值被設置為15時，算法的收斂概率是1。

圖5　迭代次數變化時平均收斂概率的差異

在仿真實驗中還考慮了網絡拓撲規模和迭代次數之間的關系。經過反復實驗，GSO-MCM算法的平均迭代次數為12。仿真結果如圖6所示。從圖6中可以看出盡管GSO-MCM算法能夠收斂，但迭代次數會隨著拓撲規模的增長而增長，同時迭代次數的平均值趨向于以線性的方式增加。

圖6網絡拓撲規模和迭代次數的關系

3結語

本文提出了一種基于GSO的多約束組播樹生成算法(GSO-MCM)。該算法通過將螢火蟲群優化算法進行改造，使其適用于多約束條件下的組播樹生成過程，并通過組播樹合并和環路消除等方式提高組播樹的生成性能。通過與一些其他著名的基于智能計算的啟發式的組播樹生成算法在收斂時間、網絡拓撲規模、組播組節點比例等指標下進行比較，來驗證該算法的有效性。仿真結果表明本文提出的GSO-MCM算法在搜索速度和有效性方面有著明顯的性能優勢。進一步，對于下一代網絡的組播路由協議來說[17]，該算法在實用性和適應性方面均有著巨大的潛力。

參考文獻：

[1]Avokh A,Mirjalily G. Load-Balanced Multicast Tree Routing in Multi-Channel Multi-Radio Wireless Mesh Networks Using a New Cost Function [J]. Wireless Personal Communications, 2013, 69(1): 75-106.

[2]LI F, FANG Y, HU F, et al. Load-Aware Multicast Routing in Multi-Radio Multi-Channel Wireless Mesh Networks [J]. Computer Networks,2011,55(9):2150-2167.

[3]ZHAO L, Al-Dubai A Y, MIN G. GLBM: A New QoS Aware Multicast Scheme for Wireless Mesh Networks [J]. Journal of Systems and Software, 2010, 8(3): 1318-1326.

[4]Lim S, Ko Y, Kim C, et al. Design and Implementation of Multicasting in Multi-Channel Multi-Interface Wireless Mesh Networks [J]. Wireless Networks, 2011, 17(4): 955-992.

[5]Kakhbod A, Teneketzis D. An Efficient Game Form for Multi-Rate Multicast Service Provisioning [J]. IEEE Journalon Selected Areas in Communications, 2012, 30(11): 2093-2104.

[6]Koutsonikolas D, HU Y C, WANG C C. Pacifier: High-Throughput, Reliable Multicast Without Cryingbabies in Wireless Mesh Networks [J]. IEEE/ACM Transactions on Networking, 2012, 20(5): 1375-1388.

[7]Galvez J J, Ruiz P M, Skarmeta A F G. Responsive On-Line Gateway Load-Balancing for Wireless Mesh Networks [J]. Ad Hoc Networks, 2012, 10(1): 46-61.

[8]CHENG H, YANG S. Joint QoS Multicast Routing and Channel Assignment in Multi-Radio Multi-Channel Wireless Mesh Networks Using Intelligent Computational Methods [J]. Applied Soft Computing, 2011, 11(2): 1953-1964.

[9]Jahanshahi M, Dehghan M, Meybodi M R. A Mathematical Formulation for Joint Channel Assignment and Multicast Routing in Multi-Channel Multi-Radio Wireless Mesh Networks [J]. Journal of Network and Computer Applications, 2011,34(6):1869-1882.

[10]TU W, Sreenan C J, CHOU C T, et al. Resource-Aware Video Multicasting via Access Gateways in Wireless Mesh Networks [J]. IEEE Transactions on Mobile Computing, 2012, 11(6): 881-895.

[11]Krishnanand K N. Glowworm Swarm Optimization: A Multimodal Function Optimization Paradigm with Applications to Multiple Signal Source Localization Tasks[D]. Department of Aerospace Engineering, Indian Institute of Science,2007.

[12]Jangha Kang, Kyungchul Park, Sungsoo Park. Optimal Multicast Route Packing [J]. European Journal of Operational Research, 2009(196): 351-359.

[13]Krishnanand K N, Ghose D. Glowworm Swarm Optimization for Multimodal Search Spaces [J]. Handbook of Swarm Intelligence, 2010(1): 451-467.

[14]Krishnanand K N, Ghose D. Glowworm Swarm Optimization: A New method for Optimizing Intelligence Multi-modal Functions [J]. International Journal of Computational Studies, 2009, 1(1):93-119.

[15]ZENG G, WANG B, DING Y, et al. Efficient Multicast Algorithms for Multi-Channel Wireless Mesh Networks [J]. IEEE Transactions on Parallel and Distributed Systems, 2010, 21(1): 86-99.

[16]Ansari N, Cheng G, Wang N. Routing-Oriented Update Scheme (ROSE) for Link State Updating [J]. IEEE Transactions on Communications, 2008(56): 948-956.

[17]李紀舟, 路璐, 郭利民. 空間互聯網技術發展現狀及趨勢[J]. 通信技術, 2015，47(01):1-7.

LI Ji-zhou, LU Lu, GUO Li-min. Technology Development Review and Trend of Space Internet. Communications Technology, 2015，47(01):1-7.

劉杰(1984—)，男，博士，工程師，主要研究方向為機器學習、智能通信技術；

王振(1982—)，男，碩士，工程師，主要研究方向為信息管理與信息系統；

馮志先(1981—)，男，碩士，工程師，主要研究方向為戰術通信網絡、軟件工程；

杜軍平(1963—)，女，博士，教授，博導，主要研究方向為計算機應用、人工智能理論與技術。