基于NFV的QoS多源多播蟻群優化算法

黃聞天，孫士民,2，張新潮，徐愛鑫，汪曉凡

（1.天津工業大學計算機科學與技術學院，天津 300387；2.天津市自主智能技術與系統重點實驗室，天津 300387）

0 引言

多源多播網絡即是通過一組源節點向一組目的地傳送相同內容的一種通信方式。同時，隨著網絡功能虛擬化（NFV）的快速發展與應用，大量的虛擬網絡功能節點（VNF）分布在多播網絡中，為網絡應用提供不同層級的多樣化服務。因此，多源多播網絡與網絡功能虛擬化（NFV）的結合迎來了全新的挑戰。NFV網絡要求在網絡信號傳輸到目的節點前需要按順序遍歷一些布置了虛擬網絡功能（VNF）的節點，通過這些節點上分布的網絡功能的按順序結合完成指定的網絡功能［1］。因為其將部分運算功能分布在網絡節點上，所以NFV網絡的QoS需求也越來越豐富。而QoS路由算法也能夠合理分配網絡吞吐量、優化網絡資源配置，結合所布置功能實現網絡全局資源利用率優化［2］，這使得對構建含QoS的支持網絡功能虛擬化多源多播優化網絡的研究成了當務之急。

本文將虛擬源節點算法與蟻群算法相結合，提出了一種基于蟻群優化的QoS多源多播路由算法Ant based Multi-Source Multicast Tree Construction（AQoSMMTC），可以有效地構建多源多播網絡并對其進行優化。而針對其與NFV相結合的問題，本文提出一種基于VNF節點選擇的改進的蟻群算法VNF based Multi-Source Multicast Tree Construction（VQoSMMTC）來對多源組播樹進行求解，在追求路徑代價優化的同時對VNF節點位置進行了選擇。

1 算法思路

1.1 蟻群優化算法

蟻群算法［3］是意大利學者M.Dorigo等人提出來的，通過模擬自然界螞蟻群覓食尋徑來求解相似尋優問題。主要內容為螞蟻在覓食和返巢的過程中擁有選擇最短路徑的能力，其能力來源于螞蟻會在行走的路徑上留下自己的信息素（pheromone）。信息素會隨著時間揮發，其他螞蟻對路徑上的信息素進行識別，并在行動時按照信息素濃度隨機選擇路線。路線選擇的概率與其信息素濃度成正比。較短的路線往返時間更短，往返次數更多，從而擁有較強的信息素濃度。會對覓食路徑選擇形成一種正反饋并通過這種方式挑選最佳路徑［4］。

1.2 通過蟻群優化算法解決含Qo S的多源多播問題

多源多播問題是指對給定的一組目的地和一組源構建網絡拓撲。與單源多播的最小生成樹相比，多源多播問題是旨在構造一個最小成本的森林（MCF）［5］，即眾多最小生成樹的集合，它確保每個目的節點通過林中的一條路徑只連接到一個源。這是一個NP完全問題［6］。

在多源多播網絡中，可以通過蟻群算法與虛擬源節點法［7］相結合來解決多源多播問題。首先構建一個虛擬源節點，使得其對所有源節點的距離為0，所有螞蟻都從此虛擬源節點釋放，所有螞蟻也都對此虛擬源節點返回，將源節點視為普通中繼節點。此方法的多播目標樹即可視為從虛擬源節點開始的單源多播最小斯坦納樹。其次待循環完成后將虛擬源節點摘除，留下源集合中被使用的節點就是蟻群優化后的多源多播樹。在蟻群算法尋找多播樹的過程中，對螞蟻的每一次尋路都進行一次QoS判定，自動避開不滿足要求的路徑選擇即可完成滿足QoS需求的多播樹的構建，如圖1所示。

圖1 通過添加虛擬源的蟻群算法解決多源多播問題

1.3 基于改進蟻群算法的支持NFV多源多播路由算法（VQo SMMTC）

改進的蟻群系統算法在對信息素的設置上增加了正向信息素和反向信息素。在螞蟻進行正向搜索時遵循正向信息素，每當到達所有目標節點后再從目標節點釋放螞蟻根據反向信息素進行反向搜索直到回到虛擬源節點（反向信息素初始值與第一次正向信息素相同）。當螞蟻完成一次搜索循環后，檢查是否發現當前最佳樹（目標節點到虛擬源節點距離最短），若發現則對反向信息素進行全局更新，之后繼續進行循環直到到達終止條件。

在支持NFV的多源多播樹的構建中，由于每一組流量的傳輸都需要按順序經過一些特定的VNF節點。改進的蟻群算法在反向循環的過程中添加了VNF節點的尋找功能。在反向尋路的過程中按順序尋找VNF節點的布置位置，每尋找一個VNF功能節點則對下一步能到達的節點進行該VNF功能布置代價計算，將布置代價計入鏈路代價中，從而對傳輸代價和布置代價一同進行優化。使得每一個目的節點都有完整的VNF傳輸鏈（SFC）［8］，并且獲得基于總代價最小的優化樹，算法示意如圖2所示。

圖2 基于NFV的改進蟻群算法多源多播樹

2 算法實現

2.1 基于蟻群優化的Qo S多源多播路由算法（AQo SMMTC）

2.1.1 蟻群算法螞蟻轉移規則偽代碼

算法1螞蟻轉移規則

需求:無向圖G=（V,E）,信息素表（Phero-mone list）,開始節點N,禁忌表,q0，鄰居節點集合（P（neighber））

將禁忌表中節點從信息素表中刪除

q=rand（0,1）

if q≤q0

Target=arg max（P（neighber））

else

for neighber∈Phero-mone list

P（N,neighber）=P（neighber）/SUM（P）

if

（P（N,neighber）>R）

Target=min（neighber）

end if

end for

end if

將N加入禁忌表

Next skip=Target

start node=Next skip

輸出:Next skip

End

2.1.2 基于蟻群算法的多源多播樹構建偽代碼

算法2基于蟻群算法的多源多播樹構建

需求:無向圖G=（V,E）,信息素表,禁忌表,t目標節點集合{D},源節點集合{S},螞蟻數量M,循環次數It.

將S0加入圖G,Distance（S0,{S}）=0

for i=0:It

m=0

for Di∈{D}

for m≤M以出發節點為S0執行算法1

if Target=Di

Record［path（Di）,cost（Di）］

為path（Di）進行局部信息素更新

else back to do

end if

end for

Best_path（Di）=arg min（cost（Di））

end for

tree={path（Di）},record cost（tree）

Best_tree=arg min（cost（tree））

對Best_tree進行全局信息素更新

更新信息素表

end for

輸出:Best_tree

End

2.2 基于改進蟻群算法的支持NFV多源多播路由算法（VQo SMMTC）

2.2.1 改進的蟻群算法螞蟻轉移規則偽代碼

算法3改進的蟻群算法轉移規則

需求:無向圖G=（V,E）,信息素概率表,出發點N,禁忌表,q0，當前需要布置的VNF功能VNFnode（n），QoS標準

Start：將禁忌表中節點從信息素概率表中刪除

q=rand（0,1）

if q≤q0

Target=arg max（P（neighber））

else

for neighber∈Phero-mone list

P（N,neighber）=P（neighber）/SUM（P）

if（P（N,neighber）>R）

Target=min（neighber）

end if

end for

end if

If Target符合QoS標準且未被部署其他VNF功能

將N加入禁忌表

Next skip=Target

VNFnode（n）=Target

n-1

start node=Next skip

Else

將Target加入禁忌表

start node=N

重新開始循環

輸出:Next skip

End

2.2.2 基于改進的蟻群算法的多源多播樹構建偽代碼

算法4基于NFV的改進蟻群算法多源多播樹構建方法

需求:無向圖G=（V,E）,正向信息素表，反向信息素表，禁忌表,目標節點集合{D},源節點集{S},螞蟻數量M,最大循環次數It.

將S0添加入圖G中,Distance（S0,{S}）=0

for i=0:It

m=0

for m≤M從S0開始根據算法1進行循環

if Target=Di

記錄［path（Di,Cost（Di）］

對path（Di）進行局部信息素更新

else back to do

end if

end for

for m≤M=從{Di}開始根據反向信息素表及算法3進行循環

if Target=S0

記錄［path（Di）,Cost（Di）］

對path（Di）進行局部信息素更新

else back to do

end if

end for

Best_path（Di）=arg min（Cost（Di））

tree={path（Di）}］

end for

計算樹的代價Cost（tree）

Best_tree=arg min（Cost（tree））

進行全局信息素更新

更新反向信息素概率表

end for

輸出:最佳樹，VNF節點位置

end

3 實驗與仿真

本實驗采用Matlab仿真工具對AQoSMMTC算法與VQoSMMTC進行模擬仿真，并且測試性能與分析數據與MMForest路由算法［9］、MCF路由算法［5］進行實驗對比。由于上述算法采用的機制、原理各不相同，為確保實驗的準確性、完整性，將仿真實驗設置為采用同一傳統樹形網絡拓撲結構、相同的節點鏈路參數，網絡節點分布范圍為10000×10000，節點數量為100個，鄰居節點距離為200，所有實驗所用節點均從此100個節點中挑選。

對QoS約束條件設定為帶寬（bandwidth）=100，時延（delay）=80 ms，丟包率（packet_loss_rate）=0.05。在試驗前對網絡中所有鄰居節點間鏈路QoS屬性使用偽隨機算法進行設置，確保不滿足要求鏈路出現概率小于等于1%。

3.1 不同網絡規模下構建的多源多播樹總代價

本次實驗對不同網絡規模下多源多播樹的總代價進行對比，設置源數量為5，網絡規模即節點數由23到73。

實驗結果如圖3所示，AQoSMMCT算法專注于最優樹的尋找，所以其結果優于其他對比算法。而VQoSMMCT算法則在構建多播樹的同時對VNF節點進行尋找，故其總代價略大于AQoSMMCT算法與MMForest算法基本持平。

圖3 不同網絡規模下多播樹的代價

3.2 給定最優樹下算法成功率

根據先前網絡規則構建一個簡單VNF功能網絡，并添加干擾節點構建一個網絡規模為20的測試網絡，該網絡的最佳多播樹如圖4所示。

圖4 已標出最佳多播樹的測試網絡

使用結合RMTC［9］的MMForest算法［6］和VQoSMMTC算法對該網絡求解。對比所得到的結果是否于最佳多播樹相等，從而確定算法的成功與否。本次實驗采取不同的最大迭代次數進行對比，每一組進行100次獨立實驗，成功得到最佳多播樹的次數即為算法的成功率，如圖5所示。

圖5 不同迭代次數下算法的成功率

從實驗結果不難看出，VQoSMMTC算法的成功率明顯優于結合RMTC的MMForest算法，隨著最大迭代次數的增加，算法的成功率趨于穩定。

4 結語

本文基于蟻群算法和虛擬源節點算法提出了基于蟻群優化的QoS多源多播路由算法。為了解決傳統的多播路由算法與NFV邊緣計算等網絡功能部署方法相結合的問題，提出了支持NFV的QoS多源多播路由算法。實驗結果表明，在含QoS的多源多播樹的構建上本文提出的兩種多源多播算法均可成功構建符合QoS需求的多源多播樹，并且樹的總代價優于許多已有的多源多播樹構建算法。并且在對VNF節點布置的計算上能結合節點功能與網絡狀況構建多源多播樹。