基于FBM模型的自相似流量建模仿真

盧 穎 ， 裴承艷 ， 陳子辰， 康鳳舉

（1.西安工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，陜西 西安 710032；2.西北工業(yè)大學(xué) 航海工程學(xué)院，陜西 西安 710072）

網(wǎng)絡(luò)流量的研究對(duì)于改進(jìn)網(wǎng)絡(luò)結(jié)構(gòu)，提高網(wǎng)絡(luò)性能，進(jìn)行入侵檢測(cè)，提高網(wǎng)絡(luò)安全性方面等都有著重要的作用。傳統(tǒng)的業(yè)務(wù)模型大多假設(shè)基于泊松過(guò)程，即一種短程相關(guān)模型，其數(shù)學(xué)意義為：對(duì)于隨機(jī)過(guò)程x（t）的當(dāng)值與它的所有歷值都無(wú)關(guān)，這種模型簡(jiǎn)單易實(shí)現(xiàn)。上世紀(jì)90年代，Leland等人在文獻(xiàn)[1]中第一次明確提出了網(wǎng)絡(luò)流量具有自相似性，并證明了網(wǎng)絡(luò)流量的自相似性表現(xiàn)為網(wǎng)絡(luò)業(yè)務(wù)數(shù)據(jù)流在很長(zhǎng)時(shí)間范圍內(nèi)都具一種長(zhǎng)程相關(guān)性，即對(duì)于隨機(jī)過(guò)程的當(dāng)值與它的所有歷值都有關(guān)。之后，各國(guó)的研究人員對(duì)現(xiàn)有的一些網(wǎng)絡(luò)進(jìn)行觀(guān)測(cè)和分析，發(fā)現(xiàn)無(wú)論網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)、用戶(hù)數(shù)量、服務(wù)類(lèi)型如何變化，這種自相似性始終存在。本文基于FBM模型分別采用RMD和Fourier變換法進(jìn)行了流量序列的仿真生成實(shí)驗(yàn)，并利用R/S和方差時(shí)間曲線(xiàn)圖法對(duì)所產(chǎn)生的自相似序列進(jìn)行了驗(yàn)證及結(jié)果分析。

1 網(wǎng)絡(luò)流量的自相似過(guò)程的定義

考察一個(gè)協(xié)方差平穩(wěn)的統(tǒng)計(jì)過(guò)程 X={Xt：t=0，1，2，3，…}，該過(guò)程的數(shù)學(xué)期望 μ=E[Xt]為常數(shù)，方差 σ2=E[（Xt-μ）2]為有限值，自相關(guān)函數(shù) r（k）=E[（Xt-μ）（Xt+k-μ）]/σ2，k=1，2，3，…，僅與k有關(guān).其中Xt可理解為第t個(gè)單位時(shí)間里到達(dá)的網(wǎng)絡(luò)業(yè)務(wù)實(shí)體數(shù)。假定X的自相關(guān)函數(shù)有如下形式[2]：

對(duì)于每一個(gè) m=1，2，3，…，令 X（m）={Xmt：t=0，1，2，3，…}表示一個(gè)新的序列，其中 Xmk=1/m（Xkm-m+1+…+Xkm），k=1，2，3，…代表長(zhǎng)度為m的聚集過(guò)程.如是X（m）也定義了一個(gè)廣義平穩(wěn)隨機(jī)過(guò)程，r（m）（k）表示 X（m）的自相關(guān)函數(shù)。 如果對(duì)所有的 m，均有：

當(dāng)k→∞，稱(chēng)X為精確二階自相似過(guò)程，并稱(chēng)H=1-β/2為其自相似參數(shù)。

2 自相似網(wǎng)絡(luò)流量的刻畫(huà)——FBM流量模型及仿真建模

在對(duì)網(wǎng)絡(luò)業(yè)務(wù)流量建模中，要求用盡量少的參數(shù)來(lái)對(duì)實(shí)際網(wǎng)絡(luò)的通信流量建模，另外就是要求產(chǎn)生的合成數(shù)據(jù)序列要顯示與測(cè)量數(shù)據(jù)的相似的特征。常用的自相似數(shù)學(xué)模型中，分形布朗運(yùn)動(dòng)FBM是一種較為方便的流量模型。該模型是基于分形高斯噪聲FGN（Fractal Gaussian Noise）過(guò)程的，是FGN的一個(gè)增量過(guò)程[3]。

仿真實(shí)驗(yàn)中分別采用隨機(jī)中點(diǎn)置位法和離散Fourier變換法對(duì)FBM模型進(jìn)行建模研究，從而產(chǎn)生分形高斯噪聲的業(yè)務(wù)量。并對(duì)不同的自相似系數(shù)，不同的算法生成的網(wǎng)絡(luò)流量序列進(jìn)行對(duì)比，從而分析各自的性能。

2.1 隨機(jī)中點(diǎn)置位法（RMD）

隨機(jī)中點(diǎn)置位法（RMD法）利用逐漸子分區(qū)間方法產(chǎn)生模擬序列。該方法最大的優(yōu)點(diǎn)在于快速。算法原理：先細(xì)分時(shí)間間隔[0，T]，然后通過(guò)求左右兩點(diǎn)的算術(shù)平均值，迭代地獲得中點(diǎn)的數(shù)值，并加上一個(gè)偏移量?；贛ATLAB仿真平臺(tái)編寫(xiě)RMD算法步驟如下[4-5]：

原始業(yè)務(wù)流數(shù)據(jù)經(jīng)過(guò)偽隨機(jī)序列的加權(quán)迭代操作，生成前臺(tái)序列，對(duì)前臺(tái)序列進(jìn)行性能分析，不斷地調(diào)整模型參數(shù)，使得前臺(tái)序列的性能與原始序列相匹配，并形成最終的RMD模型。

1）采用MATLAB中M語(yǔ)言中的random（）生成一個(gè)均值為 0，方差為 1 的偽隨機(jī)序列 G=G（n）（n=1，2，3…2m）作為原始序列；

4）迭代運(yùn)算后的前臺(tái)序列在數(shù)學(xué)上分析起來(lái)比較困難，所以對(duì)其進(jìn)行余弦修正，SY=cos（X），最后得到生成的序列SY（n）（n=1，2，3，…2m）。

2.2 Fourier變換法

Fourier變換法是通過(guò)對(duì)分形高斯噪聲的頻譜進(jìn)行Fourier變換獲得業(yè)務(wù)數(shù)據(jù)，有很高的準(zhǔn)確性，其基本思路是：產(chǎn)生一個(gè)頻譜，然后對(duì)這個(gè)頻譜進(jìn)行快速Fourier逆變換。

基于matlab仿真平臺(tái)編寫(xiě)快速Fourier逆變換法算法步驟如下[6]：

3 自相似序列生成實(shí)驗(yàn)及分析

3.1 自相似序列的生成

分別采用RMD算法和Fourier變換法，基于MATLAB軟件進(jìn)行仿真，設(shè)定自相似參數(shù)為0.7，0.8，0.9時(shí)生成序列長(zhǎng)度為 8 192的自相似序列，圖1（a）為 H=0.9時(shí)的 RMD算法生成結(jié)果，（b）為H=0.9時(shí)的Fourier變換法生成結(jié)果。

圖1 RMD算法和Fourier變換法的自相似序列生成結(jié)果Fig.1 Self-similar sequence generated by RMD algorithm and Fourier algorithm

3.2 自相似過(guò)程中常用的參數(shù)估計(jì)法

常用自相似參數(shù)估計(jì)方法有：方差時(shí)間曲線(xiàn)圖法、絕對(duì)值法、R/S方法、周期圖法等[7]，本文采用R/S法和方差時(shí)間曲線(xiàn)圖法對(duì)生成序列的自相似性進(jìn)行檢驗(yàn)。

1）R/S 方法

2）方差時(shí)間曲線(xiàn)圖法

自相似過(guò)程m的重聚集時(shí)間序列X＜m＞，其方差服從：Var（x＜m＞）=m-β·Var（x）。 其中，Hurst參數(shù)滿(mǎn)足：H=1-（β/2），且 0＜β＜1。 給上述等式兩邊求對(duì)數(shù)可得：log[Var（X＜m＞）]=log[Var（X）]-β log（m）。 只需將 log[Var（X＜m＞）]與 m 的關(guān)系在對(duì)數(shù)坐標(biāo)系中畫(huà)出來(lái)，并通過(guò)線(xiàn)性擬合所得一斜率為-β的直線(xiàn)，若斜率在-1與0之間，則滿(mǎn)足自相似性[8-9]，即可間接計(jì)算Hurst參數(shù)。

3.3 生成序列的自相似性檢測(cè)

對(duì)RMD算法生成的隨機(jī)序列利用R/S方法和方差時(shí)間曲線(xiàn)圖法進(jìn)行Hurst參數(shù)估計(jì)。分別檢測(cè)的是RMD算法指定H值為0.7，0.8和0.9時(shí)生成序列的自相似參數(shù)H值。

1）基于R/S方法的流量自相似性估計(jì)

根據(jù)R/S方法，如圖2，在檢測(cè)結(jié)果生成的散點(diǎn)圖中兩條虛線(xiàn)分別表示斜率為1以及斜率為0.5的直線(xiàn)。圖中有很多散點(diǎn)通過(guò)線(xiàn)性擬合可得一條直線(xiàn)，該直線(xiàn)的斜率即Hurst參數(shù)，其值在0.5到1之間，具體數(shù)據(jù)如表1。H為算法指定理論值，H′為檢測(cè)H值。為了更好地檢驗(yàn)估測(cè)值與理論值的匹配程度，可以用相對(duì)誤差的大小來(lái)表示，即ΔH=（H′-H）/H。

圖2 R/S方法檢測(cè)3個(gè)序列樣本所得到的散點(diǎn)圖Fig.2 Scatters of three sample sequence generated by R/S detected algorithm

圖3 方差時(shí)間曲線(xiàn)圖法檢測(cè)3個(gè)序列樣本所得到的散點(diǎn)圖Fig.3 Scatters of three sample sequence generated by R/S test algorithm

表1 自相似序列的R/S檢測(cè)結(jié)果（RMD算法）Tab.1 Test results of self-similar sequence generated by R/S algorithm（RMD algorithm）

表2 自相似序列的R/S檢測(cè)結(jié)果（Fourier變換法）Tab.2 Test results of self-similar sequence generated by R/S algorithm（Fourier algorithm）

2）基于方差時(shí)間曲線(xiàn)圖法的流量自相似性估計(jì)

在測(cè)量結(jié)果生成的散點(diǎn)圖3中，有一條斜率為-1的直線(xiàn)。 另外一條是 log[Var（X＜m＞）]與 m 的 log-log 曲線(xiàn)關(guān)系經(jīng)過(guò)線(xiàn)性擬合后所得的直線(xiàn)，其斜率滿(mǎn)足-1到0之間，記擬合后的直線(xiàn)斜率為β，且β與H滿(mǎn)足：H=1+0.5β。由方差時(shí)間曲線(xiàn)圖法原理可知仿真結(jié)果滿(mǎn)足自相似性。

從表1和表2中可以看出，得到的H′值與原自相似流的理論H值基本上匹配，其相對(duì)誤差ΔH較小，從而證明了仿真算法的正確性。通過(guò)對(duì)RMD和Fourier變換法所生成的自相似序列進(jìn)行比較，可以得出：RMD算法沒(méi)有復(fù)雜的函數(shù)參與計(jì)算，計(jì)算流程清晰，速度快，而且簡(jiǎn)便易行，能快速地生成自相似序列，但Fourier變換法的生成序列準(zhǔn)確性相對(duì)較高。RMD算法和Fourier變換法可以直接選擇能夠影響生成序列的自相似特性的變量值；但由于RMD算法是通過(guò)不斷的分割間隔產(chǎn)生樣本數(shù)據(jù)序列，生成的序列是在兩個(gè)端點(diǎn)范圍內(nèi)的，所以選擇哪個(gè)端點(diǎn)作為起始分割的端點(diǎn)，對(duì)最終產(chǎn)生的數(shù)據(jù)序列的自相似特性是有影響的，可能會(huì)給后來(lái)的自相似性參數(shù)估測(cè)帶來(lái)不穩(wěn)定性。

4 結(jié)束語(yǔ)

網(wǎng)絡(luò)流量的自相似性決定了網(wǎng)絡(luò)的行為特征，只有基于自相似的建模才能準(zhǔn)確描述網(wǎng)絡(luò)的實(shí)際情況。文中基于FBM模型分別采用RMD和Fourier變換法進(jìn)行了流量序列的產(chǎn)生，并利用R/S和方差時(shí)間曲線(xiàn)圖法對(duì)所產(chǎn)生的自相似序列進(jìn)行了驗(yàn)證，表明了所仿真算法的正確性。此外還對(duì)兩種方法在自相似序列生成的精度，產(chǎn)生速度和計(jì)算復(fù)雜性方面進(jìn)行了比較。

[1]Leland W E，aqqu M S，Willinger W，et a1.On the selfsimilar nature of Ethernet traffic（extended version）[J].IEEE/ACM Transactions on Networking，1994，2（1）：115.

[2]Lee Y H，Kassam S A.Generalized median filtering and related nonlinear filtering techniques[J].IEEE Transactions on A-coustica，Speech，Signal Processing，1985，33（3）：672-683.

[3]Mandelbort B B，Van N J.Fractional brownian motions，factional noises and applications[J].SIAM Review；1968，10（4）：422-437.

[4]朱效穩(wěn)，譚獻(xiàn)海，陳柏秀.基于多FBM的網(wǎng)絡(luò)流量建模研究[J].鐵路計(jì)算機(jī)應(yīng)用，2009， 18（6）：10-13.

ZHU Xiao-wen， TAN Xian-hai， CHEN Bai-xiu.Research on modeling of network traffic based on（MK）-FBM[J].Railway Computer Application， 2009， 18（6）：10-13.

[5]李林峰，裘正定.自相似網(wǎng)絡(luò)流量的Hurst指數(shù)的迭代估計(jì)算法[J].電子與信息學(xué)報(bào)，2006，Vol.28（12）：136-158.

LI Lin-feng，QIU Zheng-ding.An iterative method to estimate hurst index of self-similar network traffic[J].Journal of Electronics&Information Technology，2006，28（12）：136-158.

[6]徐明偉，仝愛(ài)軍.基于自相似模型的網(wǎng)絡(luò)性能測(cè)試[J].計(jì)算機(jī)工程與應(yīng)用，2002， 38（5）：56-59.

XU Ming-wei，TONG Ai-jun.Network performance testing based on self-similar modeling[J].Computer Engineering and Applications， 2002， 38（5）：56-59.

[7]傅雷揚(yáng)，王汝傳，王海艷，等.R/S方法求解網(wǎng)絡(luò)流量自相似參數(shù)的實(shí)現(xiàn)與應(yīng)用[J].南京航空航天大學(xué)學(xué)報(bào)，2007，39（3）：358-362.

FU Lei-yang， WANG Ru-chuan， WANG Hai-yan， et al.Implementation and application of computing self-similar parameter by R/S approach to analyze network traffic[J].Transactions of Nanjing University of Aeronautics amp；Astronautics，2007，39（3）：358-362.

[8]王新.自相似網(wǎng)絡(luò)流量的建模與預(yù)測(cè)[D].北京：清華大學(xué)，2003.

[9]王西鋒，高嶺，張曉孿.自相似網(wǎng)絡(luò)流量預(yù)測(cè)的分析和研究[J].計(jì)算機(jī)技術(shù)與發(fā)展，2007，17（11）：42-45.

WANG Xi-feng， GAO Ling，ZHANG Xiao-luan.Analysis and research on self-similarnetwork traffic forecast[J].Computer Technology and Development，2007，17（11）：42-45.