改進PSO-LSSVM算法的SDN網絡流量預測模型①

龍 霏,余 錚,劉 芬,馮 浩,代蕩蕩

(國網湖北省電力有限公司 信息通信公司,武漢 430077)

1 引言

隨著互聯網規模的不斷擴大,各種接入設備和相關的數據類型也日益繁雜,傳統IP 網絡的管理方法已經無法滿足大量新型應用服務對設備快速部署與技術實時更新的需求,同時網絡管理者在面對網絡資源的合理化配置等任務時也遇到了較大的困難,這些問題都極大地增加了新技術的應用成本.軟件定義網絡SDN(Software Defined Network)技術改變了傳統IP 網絡的四層協議體系,將數據傳輸與網絡控制兩個主要環節相互解耦[1],從而使得用戶可以通過控制層提供的統一且便捷的管理工具,以全局化的視角實現對分布式網絡的集中調控,并依據自身需求靈活的配置各類網絡資源,顯著地提高了大規模網絡的運維管理水平[2].作為全類型網絡管理的關鍵依據,網絡流量的特征及變化規律同樣也成為了SDN 技術研究的熱點,因此針對IP 網絡流量預測技術進行改進,設計一款符合SDN 網絡流量特征的、精確度高的網絡流量預測模型,以幫助網絡應用開發人員更準確地分析SDN 網絡性能波動狀態和優化網絡資源配置,具有重要的理論意義和應用價值.

目前針對網絡流量進行預測的方法很多,基本可分為兩個主要類型,第1 類是以時間序列法為核心,即根據網絡流量在歷史時間序列中的變化規律預測下一個有限時間間隔內的變化趨勢,如王逸兮等人提出采用同點時間序列構建檢測模型,提高了網絡性能異常的檢出率[3],Auld 等人則設計了一套網絡流量信息的規范化預處理算法,有效地控制了預測模型的計算規模[4];葉德忠等人提出構建馬爾可夫時變模型來完成針對網絡流量信息挖掘工作,降低了預測誤差[5]等.這一類模型對于傳統IP 網絡流量的監測效果較好,但對于具備長相關性特征的SDN 網絡數據流的預測精度則不太理想[6].第2 類方法是以神經網絡等智能算法為核心構建網絡流量預測模型,如李曉方等人提出對源-目的流(OD 流)數據進行降維,并以Elman 神經網絡對低維度樣本進行訓練,從而發揮了SDN 網絡可實現精確測量數據流的優勢[7];NAREJOS 等人提出通過構建深層神經網絡的方式提高對樣本群的訓練質量,提高了預測精度,但算法的空間復雜度也大幅上升[8].神經網絡存在一些固有的缺陷,如對訓練樣本要求過高,對待有限的樣本群時,缺乏足夠的泛化能力;網絡結構無法動態調整,訓練時間過長;神經元規模可控性差,極易陷入“維數災”難題等[9].

支持向量機(SVM)作為一種基于統計學習理論的人工智能算法,具有良好的泛化能力與非線性處理能力[10],近年來在樣本群分型與模式識別領域得到廣泛的應用.如王鳴提出采用小波技術結合SVM 構建流量預測模型,良好地控制了計算規模,提升了預測模型的執行效率[11].但根據目前的研究成果來看,與傳統IP 網絡相比,SDN 網絡流量的特征呈現出更為突出的混沌性、時變性和自相似性,這使得SVM 技術必須在非線性混沌理論的輔助下,方可通過數學建模來描述復雜的網絡流量變化規律.因此本文提出采用混沌理論中的多維相空間重構技術對SDN 網絡流量數據進行預處理,構建相空間中的樣本矩陣,隨后采用改進后的粒子群算法(PSO)對最小二乘支持向量機(LSSVM)中的關鍵參數進行優化,有效的提高了LSSVM的運算效率,并構建針對網絡流量變化趨勢的預測模型,對SDN 網絡流量樣本群進行訓練.通過仿真實驗證明,該模型與其他同類模型相比,在合理控制計算復雜度的條件下,表現出了更高的預測精度和誤差控制能力.

2 基于混沌理論的相空間重構

相空間重構理論由Takens 等人提出,該理論將多維狀態空間中任一點的變化規律視為與之產生關聯的其它點變化的綜合影響,因此可構建相對時間序列.該序列中的任一點在起始時間點上的值設為基值,而在空間中其他延遲坐標點上的值則作為新維來處理.隨著起始時間點的推移,不斷構建出新的子序列,就可通過監測空間中各個時間點變化規律的方式,完整的構建出系統的動態模型[12].

假設混沌時間序列為x={x|xi,i=1,2,3,···,N},N為時間序列長度,采用時延τ和嵌入維m將其重構,可得到:

設系統動力學維數為d,Takens 同樣證明了若嵌入維m能夠滿足m≥2d+1,則該模型與原系統可視為在拓撲意義上等價.雖然Takens 在其證明過程中給出了嵌入維的計算方法,但其前提是時間序列無限長,且樣本空間處于無干擾的理想狀態,這顯然與網絡流量的特征不符[13],因此本文提出采用C-C 方法對m和τ這兩個關鍵參數進行選取,按照以上設定,可將嵌入序列的關聯積分通過式(2)表達:

由此可將檢驗統計量表達為:

對上式進行分塊平均,可得到:

當N→∞時,可將上式簡化為:

當處于時間序列無限長且各元素之間不相關的理想條件下時,若m和τ為定值,則對于?r,均有S2(m,r,τ)=0成立.但對于網絡流量的樣本空間而言,其時間序列長度必然是有限的,且元素之間存在復雜的關聯,因此S2(m,r,τ)～τ明顯呈現出了時延的自相關性,按照混沌理論求解相空間中最佳時延 τd的方法,可知:

確定了最佳重構時延τ后,即可逆向推導得到嵌入維m的最佳值,并完成時間序列在多維相空間中的重構.

3 基于改進PSO 算法的LSSVM的優化

3.1 最小二乘支持向量機LSSVM

支持向量機(SVM)具有良好的泛化能力,但對于一個新的樣本群進行訓練時,其計算復雜度高成為了一個很難克服的問題,這就導致了當面對以時間序列構建的大規模SDN 網絡流量樣本群時,SVM的執行效率會大幅降低,從而嚴重地影響了預測模型的實時性能[14].Este A 等人提出采用最小二乘法對SVM 進行改進,引入誤差平方和替代SVM中的損失函數,通過非線性映射函數φ(x)將低維空間中的平面分類問題轉化為高維空間的線性方程組求解問題,從而有效地降低了原算法的復雜度[15].

對于一個記錄了輸入量xi和輸出量yi的網絡流量樣本群D={(xi,yi)|i=1,2,···,n},使用φ(x)構建最小二乘支持向量機(LSSVM)的回歸函數:

式中,w表示高維特征空間采用的權值向量,b為預設的偏置常數.

參照支持向量機理論,可采用式(9)中列出的回歸模型求解上述回歸函數,有:

該模型使用的正則化方法非常有助于提高模型的泛化能力,γ為正則化參數,ei為輸出量與回歸函數結果間的誤差.再引入Lagrange 函數將式(9)轉化更易求解的對偶空間優化模型:

式中,αi∈R為Lagrange 乘子.經過多類函數的對比分析后,選取RBF 函數為LSSVM的核函數,設其函數寬度為σ,可將其表達為:

對式(10)中的L(w,b,η,α)求偏導,消除其它待求變量,并引入式(11)核函數,可最終將其簡化為針對αi和b的求解函數:

3.2 基于改進PSO 算法的參數尋優

LSSVM 模型的擬合能力主要依賴正則化參數γ和核函數寬度值σ的選取質量,其中γ影響了模型的擬合精度與泛化能力,σ則直接決定了模型的計算量與執行效率[16,17].目前通常采用的選取方法有網絡搜索算法和遺傳算法等,前者的計算規模龐大,算法實時性差,后者則容易陷入局部極值陷阱問題,本文提出采用改進粒子群算法實現對LSSVM 模型參數(γ,σ)的組合優化,取得了較好的參數尋優質量.

粒子群算法(PSO)針對群體內的每個粒子的位置與速度進行跟蹤和調整,從而實現對整個群體的優化效果[18].假設采用d維向量對以上兩種狀態分別進行描述,則有zi=(zi1,zi2,···,zid),vi=(vi1,vi2,···,vid),而經過調整后得到該粒子最佳位置記為pi=(pi1,pi2,···,pid),最終整個群體的最佳位置記為ps=(ps1,ps2,···,psd).在PSO 算法的k輪迭代過程中,對群體中的每個粒子均采用式(13)進行狀態參數的調整.

式中,ω為慣性權重,c1和c2為PSO 算法采用的學習因子,用以調節個體粒子的變化量對群體狀態造成的影響,r1和r2是為了避免算法陷入局部最優而設定的隨機數.傳統方法設定ω、c1和c2多是根據歷史數據驗算求得,之后定期調整更新,這導致尋得的參數往往滯后于網絡流量的變化現狀,因此本文提出采用自適應方法,在算法執行過程中,動態的調整粒子搜索性能,從而提高算法的擬合度,首先ω的計算方法為:

式中,f為當前粒子個體的適應度,fmin和favg分別為整個群體中適應度的最小值和平均值.c1和c2的最佳取值則與迭代次數k密切相關,并隨著k的增加而分別呈現出遞增和遞減趨勢,因此可采用針對k的單調函數來完成每一輪次c1和c2的動態調整.

式中,Kmax為設定的最大迭代次數.在改進PSO算法執行的每個輪次,均自適應的采用以上方法確定ω、c1和c2,從而可完成對LSSVM 參數組合(γ,σ)的尋優工作.

對參數尋優效果進行分析,首先,根據式(13)可以看出,c1和c2兩個學習因子屬于加速參數類型,決定了個體粒子分別向個體最佳位置pi與 群體最佳位置ps的移動速度,顯然,過高的c1會使得粒子個體快速掠過pi所在區域,繼而導致粒子適應度的大幅波動,并最終使尋得的參數偏離最優解[19];當c1不斷減小時,算法漏掉最佳位置的概率也隨之降低,但與此同時,算法的收斂過程也會相應的延長,導致優化效率的下降.c2則相反,由于群體最佳位置ps的相對固定特征,使得較大的c2會導致算法在確定粒子移動方向時耗費過多資源,而較小的c2又 會降低粒子抵達ps區域的速度,增加算法收斂時間.改進后的算法在引入了動態調節機制之后,c1隨著迭代次數的增加而減小,確保粒子個體能夠捕捉到個體最佳位置,而c2在算法執行的初期取較小值,在快速確定了ps的方向后,c2隨迭代次數不斷增大,有效提高算法的收斂性能.

慣性權重參數ω的作用是幫助粒子個體構建全局搜索能力,對ω進行合理的調節,將有效的影響算法在全局搜索和局部搜索兩方面側重傾向[20],若式(13)中缺少了第一項 ωvid,則算法將只能搜索有限范圍,其結果往往會出現局部最優問題;若式(13)中去除與c1和c2相關的后兩項,則此時粒子以初速度v0開始移動.對ω的作用進行獨立分析,可分為以下3 種情況:

1)ω=1,此時粒子將保持初速度,以原方向做勻速移動;

2)0<ω<1,此時粒子速度會從初速度開始,隨著ω的減小而迅速降低至0;

3)ω>1,則粒子的速度不斷增大,直至達到最大速度vmax.

以上3 種情況均會對算法造成極大的干擾,粒子個體將會出現加速度恒定和移動方向固定等問題,因此當失去了加速參數c1和c2帶來的調節效果后,單純依賴慣性權重ω是無法實現對參數的可靠尋優的.若單獨保留c1項,則算法過程等價于多個粒子個體的獨立搜索,參數尋優性能將大幅度下降;若單獨保留c2項,則算法僅具備群體搜索模式,雖然可開辟新的解空間,但對復雜度稍高的問題,算法很容易收斂于局部極值,從而造成較大的偏差.針對以上分析,本文提出在ω的設定范圍內,采用自適應算法實現對ω的動態調節目標,既在算法執行的初期有效地促進了全局搜索能力,提高了收斂速度,又在后期保障了局部搜索性能,改善了算法收斂精度,對于LSSVM 關鍵參數γ,σ的尋優工作起到了顯著的改進效果.

4 SDN 網絡流量預測模型的構建與仿真

4.1 預測模型的構建與算法流程設計

在引入了改進PSO 算法之后,采用實數編碼將(γ,σ)組成一個粒子,隨后結合式(9)至式(12)的推導過程,構建出優化后的預測模型,如式(16)所示:

適應度函數取預測值與真實值之間的誤差總和,即:

其中,yi為當前樣本預測值,而為對應樣本的真實值.算法流程如圖1所示.

圖1 預測算法執行流程

對算法各主要環節描述如下:

Step 1.采集SDN 網絡流量歷史數據,構建時間序列的樣本群,并采用C-C 算法獲取最佳的嵌入維和重構時延,在此基礎上完成對原樣本群的相空間重構,得到規范化的數據序列;

Step 2.對PSO 算法執行初始化操作,確定樣本群規模、迭代輪次數、粒子初始狀態(位置zi、速度vi)、個體最佳位置pi、群體最佳位置pg以及ω、c1和c2等關鍵參數的初值,完成參數尋優的準備工作;

Step 3.將(γ,σ)參數組成粒子個體,并采用隨機取值法構建初代粒子群體;

Step 4.根據式(17)計算群體中粒子個體的適應度,調整本輪次中ω、c1和c2的取值,根據式(13)更新個體粒子的zi與vi,產生本輪次的粒子群體,并計算出新群體的pi和pg;

Step 5.依據適應度值判斷參數尋優目標是否完成,若達要求則將本輪次尋得的最優粒子取出,按照實數編碼規則解析出對應的(γ,σ)作為LSSVM的優化參數,否則返回Step 4,進入下一輪次的迭代訓練;

Step 6.利用求得的參數和重構的訓練樣本對LSSVM進行求解,構建網絡流量預測模型,并使用驗證樣本群進行對照分析,輸出最終的預測結果.

4.2 實驗設計與結果分析

在數據樣本的選擇上,采用在美國Abilene 網絡上采集到的真實數據展開仿真實驗分析.該數據集匯聚了一個包括30 條鏈路在內的SDN-IP 混合網絡中的流量信息,其中SDN-OD 流46 條,IP-OD 流為108 條,數據采樣周期為5 min,選擇其中1000 條流量數據,前800 條數據作為訓練樣本群,后200 條作為驗證樣本群,其中部分樣本信息如圖2所示.

圖2 實驗流量數據樣本

本次仿真實驗共分為兩組,分別為1 步預測仿真和3 步預測仿真.首先對樣本群進行相空間重構,采用CC 法對流量樣本進行處理,求得最優的重構時延τ=2,嵌入維m=10,完成重構后將前800 條樣本輸入LSSVM訓練,并采用改進PSO 算法進行參數尋優.得到最優參數為:γ=102.83,σ=1.35,最終構建針對SDN 網絡流量的預測模型.在經過前800 條樣本的訓練后,對后200 條驗證樣本進行預測對比,其中1 步預測實驗結果如圖3所示.

觀察圖3(a)中預測結果跟蹤曲線可以發現,在1 步預測仿真實驗中,基于改進PSO-LSSVM的預測模型表現出了良好的預測精度,各預測值與真實值擬合程度高,預測結果跟蹤曲線與真實流量變化曲線基本重合,證明該模型很好地模擬了SDN 網絡流量所具備的周期性和非線性變化特征,具有可靠的泛化性能;從圖3(b)中可以看出,預測結果的偏差十分穩定,且均在狹小范圍內波動.在200 次的預測結果與真實數據的比對中,167 次預測結果的相對誤差小于6 MB,其中更有94 次相對誤差小于2 MB,而誤差超過8 MB 僅有9 次,且所有預測誤差均在10 MB 以內,預測結果表現出了良好的精確性和穩定性.

圖3 SDN 網絡流量1 步預測實驗結果

網絡流量預測模型需要真實反映網絡流量變化規律,其預測精度越高、提前量越大,模型應用價值就越高.1 步預測僅能對時間序列中下一個臨近點的流量進行預測,并不能客觀的驗證模型的預測性能[21],為了進一步考察本模型在網絡流量多步預測方面的表現,設計了3 步預測仿真實驗,其結果如圖4所示.

觀察圖4(a)可以發現,在增加了預測提前量之后,模型對SDN 網絡流量變化的擬合性能有了一定程度的下降,且圖4(b)中的預測偏差也有所增大,但預測質量整體上仍處于良好水平,其中154 次預測相對誤差在20 MB以內,僅有4 次超過40 MB,其中1 次達到了最高的50.13 MB.從整體來看,誤差波動范圍穩定,基本控制在10%以內,預測曲線與實際流量曲線的波動方向吻合,能夠在實際應用過程中對網絡流量監控工作提供可靠的參考.

圖4 SDN 網絡流量3 步預測實驗結果

為了對比分析預測模型的運行質量,同時選取了BP 神經網絡(BPNN)、自回歸滑動平均(ARIMA)和基于遺傳算法的最小二乘支持向量機(GA-LSSVM)三種預測模型參與實驗,并選取相對平均誤差(MPAE)和均方根誤差(RMSE)兩種指標對預測結果進行評價,其計算公式分別為:

使用以上3 種網絡流量預測模型對同組樣本進行預測,并將統計結果與本文提出的改進PSO-LSSVM模型的預測結果進行對比分析,其統計結果如表1所示.

表1 多模型預測結果統計信息

對比4 種模型對SDN 網絡流量的預測統計數據可以看出,相較于BPNN 模型和ARIME 模型,改進后的PSO-LSSVM 模型在1 步與3 步預測仿真實驗中表現出明顯優勢,其預測結果的擬合精度和誤差控制水平均大幅領先,這也證明了基于最小二乘向量機LSSVM技術構建的預測模型具有更好的泛化性能,尤其適合針對大規模樣本群體的分析與處理場合;而與采用了同類型技術的GA-LSSVM 模型相比,本模型1 步預測的質量依舊明顯領先于前者,這說明改進后的PSO 算法對慣性權重和學習因子實施自適應動態調節后,顯著地提高了粒子的全局搜索能力,更有效的避免了局部極值問題,從而獲得了比遺傳算法更加突出的參數尋優效果.在3 步預測仿真實驗中,本模型表現出的優勢雖有所減少,但仍要優于GA-LSSVM 模型,這表明隨著預測步數(即預測提前量)的增加,SDN 網絡流量的非線性和時變特征對模型構成的干擾效應會持續放大,從而導致所有模型的預測質量均會下降,彼此之間的表現差異也會相對縮小,這一規律在其余兩種模型的預測結果中也得到了充分的體現.

5 結束語

本文針對SDN 網絡流量預測問題展開研究,首先提出對SDN 網絡流量時間序列進行混沌處理,實現在多維相空間中的重構,減少了網絡流量的復雜性特征對預測模型造成的負面影響;隨后采用自適應方法對PSO 算法中的慣性權重及學習因子進行動態調整,顯著改善了該算法的參數尋優能力,并將其引入到LSSVM中,最終構建出SDN 網絡流量預測模型.通過仿真實驗證明,該模型與其他3 種經典預測模型相比,在預測精度和誤差控制等方面具有明顯的優勢,應用前景十分廣泛.