基于FFO算法的QoS組播路由服務性能優化研究

崔玉勝

(閩南理工學院信息管理學院，福建石獅 362700)

0 引言

在網絡業務中，組播路由問題是組播服務過程中的核心問題,QoS組播路由問題與服務質量的好壞息息相關[1-2].QoS是一種網絡安全的有效保障機制，用于提供高質量的網絡服務.在遠程教育、網絡會議等多媒體服務背景下，網絡傳輸包括海量的視頻動畫、圖像圖形等大量數據，盡管在數據準確性和完整性的要求不及文件傳輸高，但在傳輸時的時延抖動、時延以及網絡帶寬等網絡性能方面有更高的要求[3].同時FFO算法相較于其他進化算法在求解QoS組播路由問題上具有獨特的優勢.綜上分析，本次研究提出了一種改進后的FFO算法進行QoS組播路由服務性能優化，通過對FFO算法局部搜索和全局搜索進行優化，從而對組播路由的帶寬和時延進行優化.

1 基于FFO算法及其改進的QoS組播路由模型

1.1 QoS組播路由服務性能

圖1 組播通信的數據包傳遞模式Fig.1 The Packet transfer mode of multicast communication

近年來，組播技術已經在諸多行業得到了廣泛應用，隨之而來的組播路由問題成為了學術界專家和學者的熱烈關注的話題.相較于單播路由，組播路由具有確定的組播路由路徑作為問題求解目標，其求解的核心是盡最大可能提高共用鏈路數量，降低組播數的總開銷[4-5].不同之處在于組播路由在合成組播樹時不能單純使用多條點對點最短路徑，尤其在多個QoS約束問題中，求解過程將會變得越來越復雜.組播通信能夠有效避免單播通信在需要與多目標設備進行通信時出現的網絡資源耗費過大的問題，數據包傳遞模式如圖1所示.它是通過一個數據發送端口一次性地把同樣的數據輸送至到多個數據接收端，接收端口沒有數量的要求，且同樣的數據包在網絡的一條鏈路中僅需拷貝一次[6].因此，在滿足多目標需求的同時，也極大地減少了資源耗費和網絡帶寬，提升了數據在網絡傳輸的效率.

如果出現網絡擁堵或者過載的情況，QoS將會通過可度量的參數約束來保證網絡服務質量[7-8].參數包括開銷、時延、時延抖動、帶寬、丟包率四種.QoS約束是在求解過程中，要求組播路由的時延等于或低于最高閾值、時延抖動等于或低于最高閾值、帶寬等于或高于最低帶寬閾值、丟包率等于或低于最高閾值[9-10].一般情況下，包括一種或多種可度量約束條件，此次研究討論時延和帶寬兩個約束條件.目前最常使用的求解QoS組播路由問題的方法包括遺傳算法(GA)、蟻群算法(ACO)、粒子群優化算法(PSO).

1.2 基于FFO算法及改進的組播路由數學模型

FFO算法是一種新型的進化算法，通過模擬果蠅在尋覓食物過程中的隨機嗅覺搜索以及視覺定位行為而提出的.它是目前計算公式最簡單、參數使用最少的進化算法，在神經網絡和函數等領域已經取得了突出的成績[11].其主要特點表現在以下三個方面.其一，該算法的步驟僅需要隨機嗅覺搜索以及視覺兩個步驟，具有實現簡便、參數少、容易調節等特點.而遺傳算法具有選擇、交叉、變異等環節，蟻群算法有更新局部信息和全局信息、概率選路、等階段；其二，該算法具有較高的收斂性，果蠅靈敏的隨機嗅覺搜索行為和視覺定位行為分別導致算法的局部搜索能力全局和局部搜索能力強；其三，該算法非常適用于求解QoS組播路由問題，果蠅在現實空間中尋找事物的過程與QoS組播路由問題中尋找解空間一一對應[12].該算法局部搜索為隨機嗅覺搜索和經過個體之間的信息交換，全局搜索通過個體之間的信息交換實現全局最優果蠅的視覺定位，并不斷迭代更新最優果蠅的位置，直至完成最大迭代次數和滿足目標精度[13].針對FFO算法在求解組播路由問題中存在的不足，尤其是在處理高維度的情況時的問題，本研究提出了一種改進后的FFO算法，即概率視覺定位果蠅優化算法(PVFFO).該算法的特性主要體現在以下三個方面.首先通過果蠅味道濃度判定函數尋找最優解，假定果蠅當前位置的組播樹是Tf，f表示果蠅，位置表示為Lf，cost(e)表示鏈路的開銷，e表示鏈路，則該果蠅味道濃度判定的函數為：

(1)

其次是隨機嗅覺搜索的方案，拓撲結構的鏈路數量為K，鏈路的編號id表示0到K-1，假定果蠅在隨機搜索以前的位置和隨機搜索之后的位置分別為Lf=[lf,0,lf,1...lf,K-1]和，Lf'=[lf,0',lf,1'...lf,K-1'].在鏈路的編號隨機選取κ個整數，整數集合表示為Z={z1,z2,..zκ}，位置更新公式表示為

(2)

其中隨機嗅覺搜索步長參數為κ，取值在[0,K]之間，i∈{0,1,...,K-1}.該方案通過果蠅在空間維度中的位置取值進行0-1的取反操作實現隨機嗅覺搜索.最后是概率視覺方案，在進化算法的迭代過程中，當代最優解是進行優化的重要環節，假定具有當代最高味道濃度值的果蠅為fb,n，迭代次數為n，某果蠅f視覺定位之前的位置表示為Lf=[lf,0,lf,1,...lf,K-1]，最優果蠅的位置表示為Ln=[ln,0,ln,1,...ln,K-1]，概率表示為：

(3)

圖2 PVFFO算法流程圖Fig.2 PVFFO algorithm flow chart

概率序列表示為[p0,p1...,pK-1],ψ為概率視覺定位靈敏度，取值大于0，rand()表示實數區間(0,1)的隨機數.此方案以最優果蠅的位置為標準，當果蠅和最優位置不再同一個維度時，果蠅會以非常高的概率與最優位置的維度保持一致，從而起到比較好的視覺定位的效果[14-15].該算法的具體實現步驟為圖3所示.其一獲得組播服務請求的源節點、時延約束條件的閾值、網絡拓撲信息、目的節點序列、帶寬約束條件的閾值；其二，對最大迭代次數MAXGEN、果蠅的群體規模M，果蠅群體F={f1,f2,...,fM}進行初始化，初始化概率視覺定位靈敏度參數和初始狀態的隨機嗅覺搜索步長參數，初始化歷史最優果蠅，0為歷史最優果蠅的味道濃度值，迭代次數為0；其三，結合隨機嗅覺搜索步長參數進行當代全部果蠅的嗅覺搜索；其四，使用味道濃度判定函數進行當代果蠅的味道濃度值計算；其五，找出當代果蠅中的最優個體和位置，并與歷史最優濃度值進行比較，如果當代最優個體的味道濃度最大值相較于歷史最優個體的味道濃度最大值，則歷史最優個體的味道濃度值和位置被當代最優個體對應的濃度值和位置所取代；其六，結合概率視覺定位靈敏度參數進行當代全部果蠅概率視覺定位；其七，如果迭代次數小于最大迭代次數，繼續進行第三步的操作，否則對最優果蠅個體的組播樹進行輸出，停止迭代.

PVFFO算法具有概率視覺定位靈敏度參數ψ和隨機嗅覺搜索步長參數κ兩個參數.前者主要用于限制局部搜索范圍，后者主要對普通果蠅與當代最優果蠅之間距離進行控制[16].兩種不同參數對組播樹開銷的影響統計如圖4所示.兩個參數的取值變化對求解的質量有非常顯著的影響.因此，此次研究概率視覺定位靈敏度參數ψ和隨機嗅覺搜索步長參數κ分別取3.6和6.

圖3 4兩種不同參數對組播樹開銷的影響統計Fig.3 Statistics of the tree cost impact of two different parameters on multicast tree

組播請求場景主要由網絡拓撲、目的節點集、若干約束條件、組播源節點共同組成[17-18].其中節點個數、各鏈路屬性、節點個數等信息構成了網絡拓撲.研究通過MATLAB軟件生成自定義拓撲，由于篇幅有限，僅展示6種組播場景的部分信息，如表2所示,組播樹的帶寬約束閾值和時延約束閾值分別為100 Mb/s和300 ms.

表1 6種組播場景的信息統計Tab.1 Information statistics of 6 multicast scenarios

2 仿真實驗對比

此次研究在組播路由問題中求解帶寬和時延等QoS約束條件分別進行8種場景的仿真實驗，并采用新提出的PVFFO、FFO、GA、PSO、量子進化算法(QEA)、隨機蛙跳算法(SFLA)、矢量引導蟻群優化算法(VGACO)等7種進化算法進行對比分析.為了保證實驗結果的公平性，真實反映算法的性能優劣，實驗假定6種場景中每種算法運行20次，所得到數據采用平均值，每種算法的子群規模為迭代次數都設置為100次，子群的數量均為20，每一代均有20個空間解.

實驗引入t檢驗進行統計和分析，檢測兩組組播樹開銷，組播樹的開銷在均值的上下進行波動，滿足正態分布規律.兩組組播樹的開銷存在明顯的區別，符號+表示前一組算法開銷相對較小，求解算法的性能更佳，符號-表示后一組算法開銷相對較小，求解算法的解的質量更佳.兩組組播樹的開銷沒有明顯的區別，用～表示，兩組算法的解質量一致.PVFFO算法和其他六種進化算法的t檢測統計如表2所示.可以看出，PVOFF算法相較于其他六種算法，除在VGACO算法的個別場景之外，求解的質量均明顯優于其他算法.

圖4 7種算法在6種不同場景的收斂統計結果Fig.4 Statistical results of convergence of 7 algorithms in 6 different scenarios

收斂統計是指歷史平均最優開銷和迭代代數的次數關系的曲線.6種不同場景中7種算法收斂統計結果分別如下圖4(a)、4(b)、4(c)、4(d)、4(e)、4(f)所示.依據收斂結果可以看出，7種進化算法在迭代次數為100時，平均歷史組播樹的開銷值都趨向穩定.除了在場景6中，VGACO算法收斂在更高質量的解，其余5種場景中PVFFO算法均比其他算法收斂在更高質量的解.同時，在迭代進行到30代左右時，PVFFO算法仍然持續尋找高質量的解，而其他6種進化算法已經進行收斂最優解，且迭代次數的增加，PVFFO算法能夠找到高質量的解.如圖4(f)所示，PVFFO算法在迭代次數為80代時收斂至最優解，相應的組播開銷為145.GA、FFO、PSO、SFLA、VGAFFO五種算法在迭代次數為30時均收斂達到最優解，再此后迭代過程中不需再尋找最優解.GEA算法在迭代次數為100時還未收斂至最優解.這表明該算法由于概率視覺定位方案的引入，具有非常高的全局搜索能力.

圖5 7種算法在6種場景中的平均運行 時間和標準差統計Fig.5 Average running time and standard deviation statistics of the 7 algorithms in 6 scenarios

7種算法在6種場景中的20次運行的平均運行時間和標準差為下圖5所示,結合圖5可以看出，針對平均運行時間，在6種不同的場景中，和其他六種算法相比，PVFFO算法的平均的運行時間相差不多.而VGACO算法的運行時間最長.平均運行時間最短的算法是遺傳算法，大約是PVFFO算法平均運行時間的一半，但是相差最大僅在1s左右，如果通過更高性能的機器進行檢驗，兩種算法的運行時間的差異將會變小.在場景6中，VGAFFO算法的運行時間最長約為14 s，而其余六種算法的的運行時間均在2 s左右.同時相較于遺傳算法，PVFFO算法收斂速度相對更快，且解的質量更高.標準差結果表明，PVFFO算法的標準差明顯小于其他算法，綜合分析，PVFFO算法實用性和穩定性更強.

圖6 7種算法在6種場景的Box-plot統計結果Fig.6 Box-plot statistical results of 7 algorithms in 6 scenarios

本研究為了更直觀反應不同算法的分布情況，采用箱線圖進行觀察.7種算法在六種不同場景的開銷的箱線圖分別如圖6(a)、6(b)、6(c)、6(d)、6(e)、6(f)所示，簡寫成Box-plot統計.從圖中可以看出，PVFFO算法在大多數的場景中的非異常數據區域和數據箱方塊相對較小，該算法的數據非常集中.從圖6(f)可以看出，PVFFO算法在該場景中產生異常數據最少且數據較為集中，但相較于其他六種算法，PVFFO算法具有明顯的優勢.中位數由高到低的排序依次為GA、PSO、FFO、QEA、SFLA、VGACO、PVFFO.PVFFO算法在個別場景中的異常數據較多，這也是因為數據過于集中，但與正常數據相比，其數量較小.

3 結論

組播業務被大量應用于網絡服務并給消費者給來諸多的益處，如何計算QoS組播路由問題中最優解是當今相關專家和學者挑戰性的話題.此次研究在分析QoS組播路由的服務性能和FFO算法的前提下，提出了一種基于FFO算法的QoS組播路由性能優化模型，通過隨機嗅覺搜索和概率視覺靈敏性定位兩種方案型優化.實驗通過對比7種進化算法在六種不同場景中的收斂速度和運行時間以及求解質量，得出了PVFFO算法的有效性和準確性.相較于FFO、GA、PSO、QEA、SFLA、VGACO,PVFFO算法具有非常高的全局搜索能力，具有極高的收斂于最優解的能力，且最優解的質量明顯由于其他進化算法.除VGACO算法在少數場景中優于PCFFO算法.此次研究在場景的選擇上不具有廣泛性，這是下一步研究的方向.