基于FFO算法的QoS組播路由服務(wù)性能優(yōu)化研究

崔玉勝

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

0 引言

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

1 基于FFO算法及其改進(jìn)的QoS組播路由模型

1.1 QoS組播路由服務(wù)性能

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

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

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

1.2 基于FFO算法及改進(jìn)的組播路由數(shù)學(xué)模型

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

(1)

其次是隨機(jī)嗅覺(jué)搜索的方案，拓?fù)浣Y(jié)構(gòu)的鏈路數(shù)量為K，鏈路的編號(hào)id表示0到K-1，假定果蠅在隨機(jī)搜索以前的位置和隨機(jī)搜索之后的位置分別為L(zhǎng)f=[lf,0,lf,1...lf,K-1]和，Lf'=[lf,0',lf,1'...lf,K-1'].在鏈路的編號(hào)隨機(jī)選取κ個(gè)整數(shù)，整數(shù)集合表示為Z={z1,z2,..zκ}，位置更新公式表示為

(2)

其中隨機(jī)嗅覺(jué)搜索步長(zhǎng)參數(shù)為κ，取值在[0,K]之間，i∈{0,1,...,K-1}.該方案通過(guò)果蠅在空間維度中的位置取值進(jìn)行0-1的取反操作實(shí)現(xiàn)隨機(jī)嗅覺(jué)搜索.最后是概率視覺(jué)方案，在進(jìn)化算法的迭代過(guò)程中，當(dāng)代最優(yōu)解是進(jìn)行優(yōu)化的重要環(huán)節(jié)，假定具有當(dāng)代最高味道濃度值的果蠅為fb,n，迭代次數(shù)為n，某果蠅f視覺(jué)定位之前的位置表示為L(zhǎng)f=[lf,0,lf,1,...lf,K-1]，最優(yōu)果蠅的位置表示為L(zhǎng)n=[ln,0,ln,1,...ln,K-1]，概率表示為：

(3)

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

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

PVFFO算法具有概率視覺(jué)定位靈敏度參數(shù)ψ和隨機(jī)嗅覺(jué)搜索步長(zhǎng)參數(shù)κ兩個(gè)參數(shù).前者主要用于限制局部搜索范圍，后者主要對(duì)普通果蠅與當(dāng)代最優(yōu)果蠅之間距離進(jìn)行控制[16].兩種不同參數(shù)對(duì)組播樹(shù)開(kāi)銷(xiāo)的影響統(tǒng)計(jì)如圖4所示.兩個(gè)參數(shù)的取值變化對(duì)求解的質(zhì)量有非常顯著的影響.因此，此次研究概率視覺(jué)定位靈敏度參數(shù)ψ和隨機(jī)嗅覺(jué)搜索步長(zhǎng)參數(shù)κ分別取3.6和6.

圖3 4兩種不同參數(shù)對(duì)組播樹(shù)開(kāi)銷(xiāo)的影響統(tǒng)計(jì)Fig.3 Statistics of the tree cost impact of two different parameters on multicast tree

組播請(qǐng)求場(chǎng)景主要由網(wǎng)絡(luò)拓?fù)?、目的?jié)點(diǎn)集、若干約束條件、組播源節(jié)點(diǎn)共同組成[17-18].其中節(jié)點(diǎn)個(gè)數(shù)、各鏈路屬性、節(jié)點(diǎn)個(gè)數(shù)等信息構(gòu)成了網(wǎng)絡(luò)拓?fù)?研究通過(guò)MATLAB軟件生成自定義拓?fù)?，由于篇幅有限，僅展示6種組播場(chǎng)景的部分信息，如表2所示,組播樹(shù)的帶寬約束閾值和時(shí)延約束閾值分別為100 Mb/s和300 ms.

表1 6種組播場(chǎng)景的信息統(tǒng)計(jì)Tab.1 Information statistics of 6 multicast scenarios

2 仿真實(shí)驗(yàn)對(duì)比

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

實(shí)驗(yàn)引入t檢驗(yàn)進(jìn)行統(tǒng)計(jì)和分析，檢測(cè)兩組組播樹(shù)開(kāi)銷(xiāo)，組播樹(shù)的開(kāi)銷(xiāo)在均值的上下進(jìn)行波動(dòng)，滿足正態(tài)分布規(guī)律.兩組組播樹(shù)的開(kāi)銷(xiāo)存在明顯的區(qū)別，符號(hào)+表示前一組算法開(kāi)銷(xiāo)相對(duì)較小，求解算法的性能更佳，符號(hào)-表示后一組算法開(kāi)銷(xiāo)相對(duì)較小，求解算法的解的質(zhì)量更佳.兩組組播樹(shù)的開(kāi)銷(xiāo)沒(méi)有明顯的區(qū)別，用～表示，兩組算法的解質(zhì)量一致.PVFFO算法和其他六種進(jìn)化算法的t檢測(cè)統(tǒng)計(jì)如表2所示.可以看出，PVOFF算法相較于其他六種算法，除在VGACO算法的個(gè)別場(chǎng)景之外，求解的質(zhì)量均明顯優(yōu)于其他算法.

圖4 7種算法在6種不同場(chǎng)景的收斂統(tǒng)計(jì)結(jié)果Fig.4 Statistical results of convergence of 7 algorithms in 6 different scenarios

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

圖5 7種算法在6種場(chǎng)景中的平均運(yùn)行 時(shí)間和標(biāo)準(zhǔn)差統(tǒng)計(jì)Fig.5 Average running time and standard deviation statistics of the 7 algorithms in 6 scenarios

7種算法在6種場(chǎng)景中的20次運(yùn)行的平均運(yùn)行時(shí)間和標(biāo)準(zhǔn)差為下圖5所示,結(jié)合圖5可以看出，針對(duì)平均運(yùn)行時(shí)間，在6種不同的場(chǎng)景中，和其他六種算法相比，PVFFO算法的平均的運(yùn)行時(shí)間相差不多.而VGACO算法的運(yùn)行時(shí)間最長(zhǎng).平均運(yùn)行時(shí)間最短的算法是遺傳算法，大約是PVFFO算法平均運(yùn)行時(shí)間的一半，但是相差最大僅在1s左右，如果通過(guò)更高性能的機(jī)器進(jìn)行檢驗(yàn)，兩種算法的運(yùn)行時(shí)間的差異將會(huì)變小.在場(chǎng)景6中，VGAFFO算法的運(yùn)行時(shí)間最長(zhǎng)約為14 s，而其余六種算法的的運(yùn)行時(shí)間均在2 s左右.同時(shí)相較于遺傳算法，PVFFO算法收斂速度相對(duì)更快，且解的質(zhì)量更高.標(biāo)準(zhǔn)差結(jié)果表明，PVFFO算法的標(biāo)準(zhǔn)差明顯小于其他算法，綜合分析，PVFFO算法實(shí)用性和穩(wěn)定性更強(qiáng).

圖6 7種算法在6種場(chǎng)景的Box-plot統(tǒng)計(jì)結(jié)果Fig.6 Box-plot statistical results of 7 algorithms in 6 scenarios

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

3 結(jié)論

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