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

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

（1.西安工業大學 計算機科學與工程學院，陜西 西安 710032；2.西北工業大學 航海工程學院，陜西 西安 710072）

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

1 網絡流量的自相似過程的定義

考察一個協方差平穩的統計過程 X={Xt：t=0，1，2，3，…}，該過程的數學期望 μ=E[Xt]為常數，方差 σ2=E[（Xt-μ）2]為有限值，自相關函數 r（k）=E[（Xt-μ）（Xt+k-μ）]/σ2，k=1，2，3，…，僅與k有關.其中Xt可理解為第t個單位時間里到達的網絡業務實體數。假定X的自相關函數有如下形式[2]：

對于每一個 m=1，2，3，…，令 X（m）={Xmt：t=0，1，2，3，…}表示一個新的序列，其中 Xmk=1/m（Xkm-m+1+…+Xkm），k=1，2，3，…代表長度為m的聚集過程.如是X（m）也定義了一個廣義平穩隨機過程，r（m）（k）表示 X（m）的自相關函數。 如果對所有的 m，均有：

當k→∞，稱X為精確二階自相似過程，并稱H=1-β/2為其自相似參數。

2 自相似網絡流量的刻畫——FBM流量模型及仿真建模

在對網絡業務流量建模中，要求用盡量少的參數來對實際網絡的通信流量建模，另外就是要求產生的合成數據序列要顯示與測量數據的相似的特征。常用的自相似數學模型中，分形布朗運動FBM是一種較為方便的流量模型。該模型是基于分形高斯噪聲FGN（Fractal Gaussian Noise）過程的，是FGN的一個增量過程[3]。

仿真實驗中分別采用隨機中點置位法和離散Fourier變換法對FBM模型進行建模研究，從而產生分形高斯噪聲的業務量。并對不同的自相似系數，不同的算法生成的網絡流量序列進行對比，從而分析各自的性能。

2.1 隨機中點置位法（RMD）

隨機中點置位法（RMD法）利用逐漸子分區間方法產生模擬序列。該方法最大的優點在于快速。算法原理：先細分時間間隔[0，T]，然后通過求左右兩點的算術平均值，迭代地獲得中點的數值，并加上一個偏移量。基于MATLAB仿真平臺編寫RMD算法步驟如下[4-5]：

原始業務流數據經過偽隨機序列的加權迭代操作，生成前臺序列，對前臺序列進行性能分析，不斷地調整模型參數，使得前臺序列的性能與原始序列相匹配，并形成最終的RMD模型。

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

4）迭代運算后的前臺序列在數學上分析起來比較困難，所以對其進行余弦修正，SY=cos（X），最后得到生成的序列SY（n）（n=1，2，3，…2m）。

2.2 Fourier變換法

Fourier變換法是通過對分形高斯噪聲的頻譜進行Fourier變換獲得業務數據，有很高的準確性，其基本思路是：產生一個頻譜，然后對這個頻譜進行快速Fourier逆變換。

基于matlab仿真平臺編寫快速Fourier逆變換法算法步驟如下[6]：

3 自相似序列生成實驗及分析

3.1 自相似序列的生成

分別采用RMD算法和Fourier變換法，基于MATLAB軟件進行仿真，設定自相似參數為0.7，0.8，0.9時生成序列長度為 8 192的自相似序列，圖1（a）為 H=0.9時的 RMD算法生成結果，（b）為H=0.9時的Fourier變換法生成結果。

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

3.2 自相似過程中常用的參數估計法

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

1）R/S 方法

2）方差時間曲線圖法

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

3.3 生成序列的自相似性檢測

對RMD算法生成的隨機序列利用R/S方法和方差時間曲線圖法進行Hurst參數估計。分別檢測的是RMD算法指定H值為0.7，0.8和0.9時生成序列的自相似參數H值。

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

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

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

圖3 方差時間曲線圖法檢測3個序列樣本所得到的散點圖Fig.3 Scatters of three sample sequence generated by R/S test algorithm

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

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

2）基于方差時間曲線圖法的流量自相似性估計

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

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

4 結束語

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

[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]朱效穩，譚獻海，陳柏秀.基于多FBM的網絡流量建模研究[J].鐵路計算機應用，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]李林峰，裘正定.自相似網絡流量的Hurst指數的迭代估計算法[J].電子與信息學報，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]徐明偉，仝愛軍.基于自相似模型的網絡性能測試[J].計算機工程與應用，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]傅雷揚，王汝傳，王海艷，等.R/S方法求解網絡流量自相似參數的實現與應用[J].南京航空航天大學學報，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]王新.自相似網絡流量的建模與預測[D].北京：清華大學，2003.

[9]王西鋒，高嶺，張曉孿.自相似網絡流量預測的分析和研究[J].計算機技術與發展，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.