基于小波分析的WiMax網絡業務流長相關性

胡永東 吳國新 徐逸卿

(1東南大學計算機科學與工程學院，南京 211189)

(2東南大學計算機網絡和信息集成教育部重點實驗室，南京 211189)

(3南京林業大學信息科學技術學院，南京 210037)

基于小波分析的WiMax網絡業務流長相關性

胡永東1，2，3吳國新1，2徐逸卿1，2，3

(1東南大學計算機科學與工程學院，南京 211189)

(2東南大學計算機網絡和信息集成教育部重點實驗室，南京 211189)

(3南京林業大學信息科學技術學院，南京 210037)

為了精確有效地檢測WiMax網絡業務流的長相關性，利用自相似隨機過程和小波變換都具有尺度不變性的特性，建立了表征長相關性的Hurst參數和小波系數的統計量.研究了業務流長相關性的小波估計法，反復選擇小波消失矩和優化尺度參數的范圍，減小這些因素對檢測結果的影響.利用ON/OFF模型仿真WiMax網絡中5種不同類型業務流，然后使用小波估計法對trace文件進行分析.檢測分析結果表明:實時業務流的長相關性比較小，非實時業務流的長相關性相對較大;隨著網絡負載的增大，業務流的長相關性會略有變化，聚合業務流的長相關性的檢測值與理論值基本吻合.

WiMax業務流;長相關性;Hurst參數;小波分析

目前，大時間尺度下的長相關性和小時間尺度下的多分形性是網絡流量公認的最重要的統計特征.這些特性不僅存在于互聯網中，也存在于一些具體的物理網絡中.研究WiMax網絡業務流的長相關性對設計網絡的呼叫接納控制算法、保證網絡服務質量(QoS)和改善網絡的性能等具有重要的意義.

Hurst參數是表征網絡業務流長相關性的一個重要參數.一般來說，Hurst參數值越大，網絡業務流的長相關性程度就越高，突發性也越強.但Hurst參數不能由定義直接計算，只能根據網絡流量序列進行估計.常用的Hurst參數估計方法有:方差時間圖法、R/S圖法、聚合時間序列絕對值法、周期圖法、Whittle估計法、回歸殘差法、Higuchi方法和小波分析法AV等.這些方法的精確度和復雜度不盡相同［1］.

Cristina［2］采集了 67 個基站(BS)，將監測到的數據作為樣本，利用R/S圖法對聚合的WiMax網絡業務流的長相關性進行檢測.Putra等［3］同樣采用R/S圖法分析和評估了WiMax網絡業務流的長相關性，與前者不同的是，把WiMax網絡業務流分為4種不同類型來進行研究.R/S圖法是早期的檢測方法，精確度不高且復雜度較高.本文為了提高WiMax網絡業務流長相關性的檢測精度，降低檢測算法的復雜度，提出利用小波分析法對WiMax網絡中不同服務等級的網絡業務流進行長相關性檢測，通過適當選取消失矩和分解級數來降低這些因素對小波法檢測結果的影響，小波分析法具有精度高和復雜度低的優點.根據 IEEE802.16 d/e［4－5］標準，在WiMax系統中有主動授權業務UGS、實時輪詢業務rtPS、擴展的實時輪詢業務ertPS、非實時輪詢業務nrtPS和盡力而為服務BE這5種服務被支持.在檢測的過程中，先分別檢測不同類型業務流的長相關性，估計每種業務流的Hurst參數值，然后在此基礎上，結合長相關性過程的分解與合并性質，計算出聚合流的Hurst參數值，這樣既減少了檢測估計的工作量，又能得到合理的結果.檢測結果表明:實時業務流的長相關性比較小，非實時業務流的長相關性相對較大;隨著網絡負載的增大，業務流的長相關性會略有變化，聚合業務流的長相關性的檢測值與理論值基本吻合.

1 長相關和Hurst參數

首先對長相關和Hurst參數作一個簡單的介紹［6］.

定義 1 長相關(long range dependence，LRD).設Xt，t∈R是廣義平穩隨機過程，若存在H∈(0.5，1)和常數 c1＞0，使得 Xt的自相關函數r(k)滿足

則稱Xt為長相關，參數H稱為Hurst參數.由于廣義的平穩過程的自相關函數和功率譜密度構成一對Fourier變換，它們相互唯一確定，因而條件(1)可以在頻域中等價地定義為

這里是 Xt的功率譜密度，c2＞0為常數

由定義1可知，長相關過程的自相關函數之和是發散的，即∑r(k)=∞.

2 Hurst參數的小波估計法

2.1 小波估計法理論基礎［7］

隨機過程Xt，t∈R基于小波ψ(t)的離散小波變換可表示為

式中，dj，k表示尺度參數為 j、平移參數為 k的小波系數;ψj，k(t)表示小波母函數 ψ(t)經過伸縮和平移變換的小波函數，兩者關系如下:

性質1 設隨機過程Xt，t∈R是一個平穩增量過程，則對于固定的 j∈Z，其小波系數 dj，k，k∈Z是一個平穩隨機序列.

性質2 設隨機過程Xt，t∈R是一個自相似過程，H為自相似Hurst參數，則對于固定的j∈Z，其小波系數 dj，k==d2j(H+1/2)d0，k.

證明

由式(2)和式(3)可以直接得到性質3.

性質3 設隨機過程Xt，t∈R是一個具有平穩增量的自相似過程(H－sssi)，0＜H＜1，且均值為0，方差存在，則

對式(5)兩邊取以2為底的對數，可以得到

2.2 Hurst參數的小波估計法AV

在式(6)中已經得到了隨機過程Xt，t∈R的離散小波變換中的尺度參數j與存在某種線性關系，可通過一元線性回歸估計出此直線的斜率μ，然后根據H=(μ－1)/2得到H值.這里選擇db小波作為小波基，具體算法描述如下:

該算法有2個難點:①對小波消失矩regu的適當選取;②對尺度參數的最小值j1和尺度參數的最大值j2的優化.這2個因素會影響Hurst參數H值的估計值.文獻［8］指出消失矩regu在滿足約束條件 regu＞(2H+1)/2下，消失距的階數越小，擬合誤差越小，所得的參數H越精確.

3 WiMax業務流的仿真及長相關性分析

以NS2為仿真平臺，利用WiMax－v2.03 module對 WiMax進行仿真.WiMax－v2.03 module是NS2上支持WiMax QoS 5種不同服務等級的模塊，因此利用它來仿真5種不同的服務等級WiMax業務流，然后用 AV法來估計每種不同業務流的Hurst參數H值，通過對不同負載下業務流的H值進行比較分析，得出不同WiMax業務流的長相關特性.同時，將AV法檢測到的Hurst參數值與R/S法檢測值進行對比分析，得出AV法更適合檢測Hurst參數.仿真環境的物理層和數據鏈路層的參數設置見文獻［9］.

3.1 仿真參數設置

在NS2中設計一個1 000 m×1 000 m的WiMax仿真環境.在仿真環境中有一個基站BS和若干個用戶站SS，各個參數的具體設置見表1.

表1 無線仿真環境參數表

3.2 業務流的仿真及長相關性分析

業務流的仿真模型為 ON/OFF模型［10］，該模型為大量的ON/OFF源疊加，每個源都有2個周期ON和OFF狀態交替出現.在ON狀態，數據源以連續的速率發送數據分組，在OFF狀態，不發送任何數據分組.每個發送源的ON和OFF的時長獨立地符合重尾分布(例如Pareto分布).通過對ON期和OFF期運用不同的分布以及設置不同分布的參數值來仿真 UGS，rtPS，ertPS，nrtPS和 BE 5種不同類型的業務流.

圖1 UGS長相關性圖

1)主動授權業務UGS

UGS主要用來支持周期性有固定長度的分組的連結，故在仿真UGS類型的業務流時，ON期發送分組長度相等，OFF期時長符合泊松分布，SS的數分別為5，10，15，20，25 和30，仿真總時長為200 s.利用R/S法和AV法來對trace文件進行分析，分別得到長相關參數值如圖1所示.由圖可見，UGS業務流的長相關參數值在0.5左右，說明這種業務流的長相關性不明顯;從AV法估計得到的結果可以看到，隨著SS數的增大，長相關性略有增加，但變化不大.

2)實時輪詢業務rtPS

rtPS主要用來支持周期性不固定長度的分組連結，所以在仿真rtPS類型的業務流時，ON期發送分組長度符合衰減速率為α=1.4的Pareto分布，OFF期時長符合泊松分布，SS數和仿真總時長與UGS相同.利用R/S法和AV法來對trace文件進行分析，分別得到長相關參數值如圖2所示.由圖可見，rtPS業務流的長相關參數值在0.6左右，這種業務流的長相關性比UGS的長相關性略微強一些.從AV法估計得到的結果可以看到，隨著SS數的增大，長相關性略有增大，但變化不大.

圖2 rtPS長相關性圖

3)擴展的實時輪詢業務ertPS

ertPS主要用來支持實時無固定長度的分組連結，故在仿真ertPS類型的業務流時，ON期發送分組長度符合衰減速率為α=1.5的Pareto分布，OFF期時長符合泊松分布，SS數和仿真總時長也與UGS相同.利用R/S法和AV法來對trace文件進行分析，分別得到長相關參數值如圖3所示.由圖可見，ertPS業務流的長相關參數值在0.6左右，這種業務流的長相關性與rtPS業務相當.從AV法估計得到的結果可以看到，隨著SS數的增大，長相關性略有增大，但變化不大.

圖3 ertPS長相關性圖

4)非實時輪詢業務nrtPS

nrtPS主要用來支持時延容忍無固定長度的分組連結，故在仿真nrtPS類型的業務流時，ON期發送分組長度符合衰減速率為α=1.2的Pareto分布，OFF期時長符合泊松分布，SS數和仿真總時長也與UGS相同.利用R/S法和AV法來對trace文件進行分析，分別得到長相關參數值如圖4所示.由圖可見，nrtPS業務流的長相關參數值在0.8左右，這種業務流的長相關性非常明顯.從AV法估計得到的結果可以看到，隨著SS數的增大，長相關性略有增大，但變化比較明顯.

圖4 nrtPS長相關性圖

5)盡力而為服務BE

BE主要用來支持沒有最小服務等級需求的分組連結，故在仿真BE類型的業務流時，ON期發送分組長度符合衰減速率為α=1.8的Pareto分布，OFF期時長符合泊松分布，SS數和仿真總時長也與UGS相同.利用R/S法和AV法來對trace文件進行分析，分別得到長相關參數值如圖5所示.由圖可見，BE業務流的長相關參數值在0.75左右，說明這種業務流的長相關性也比較明顯.從AV法估計得到的結果可以看到，隨著SS數的增大，長相關性略有增大，但變化不大.

圖5 BE長相關性圖

由于小波的多尺度不變性與自相似過程的尺度不變性有著自然的聯系，利用小波法來對自相似過程進行特征分析有著自然優勢，而且具有精度高和復雜度低(復雜度為O(n))等優點.從圖1～圖5可以看出，AV法估計長相關參數值H受到業務流規模大小的影響較小，而R/S法隨業務流規模大小波動較大，所以AV法比R/S法更適合來研究網絡業務流的長相關性.

3.3 聚合的WiMax業務流

由文獻［11］可知，當多個長相關過程聚合時，合成過程仍具有長相關性，其H值與獨立輸入源過程中H最大值相近.根據這一理論，聚合業務流的H值可以由獨立的業務流的H值推導出來.為了驗證這個結論的正確性，設計由5個UGS，rtPS，ertPS，nrtPS和BE聚合而成的業務流，利用AV法來對trace文件進行分析可以得到此聚合的業務流的H=0.763，而理論推導出該聚合業務流的H=0.749，因此理論值與AV法的估計值基本吻合.

4 結語

為了精確有效地檢測WiMax網絡業務流的長相關性，本文深入研究了業務流長相關性的小波估計法，檢測時反復優化消失矩和尺度參數，以減小這些參數對檢測結果的影響.設計了一個1 000 m×1 000 m的基于NS2的WiMax仿真環境，利用ON/OFF模型來仿真WiMax網絡中不同類型的業務源，然后，用 AV 法來檢測 UGS，rtPS，ertPS，nrtPS和BE 5種不同業務流的長相關性.檢測結果表明，5種獨立的業務流的長相關程度明顯不同，UGS，rtPS和ertPS 3種實時業務流的長相關性相對較小;nrtPS和BE 2種非實時業務流長相關性相對較大，并隨著SS數的增大，網絡負載的加大，業務流的長相關性也會略有變化.同時，在已知每種業務流的長相關性的基礎之上，根據長相關過程的聚合理論，可以得到聚合業務流的長相關性.小波消失矩的確定和尺度參數的范圍優化作為下一步研究工作.

［1］Taqqu M S，Teverovsky V，Willinger W.Estimators for long－range dependence:an empirical study［J］.Fractals，1995，3(4):785－798.

［2］Cristina Stolojescu.Long－range dependence in WiMAX traffic:a preliminary analysis［C］//International Symposium on Electronics and Telecommunications.Timisoara，Romania，2010:241－244.

［3］Putra D R，Ke K W，Wu H T.Self－similar traffic assessment on QoS service classes of WiMAX network［C］//International Symposium on Modeling and Optimization in Mobile，Ad Hoc and Wireless Networks.Seoul，Korea，2009:558－563.

［4］IEEE 802.16 WG.IEEE standard for local and metropolitan area networks part 16:air interface for fixed broadband wireless access systems［S］.New York:IEEE，2004.

［5］IEEE 802.16 WG.IEEE standard for local and metropolitan area networks part 16:air interface for fixed and mobile broadband wireless access systems，amendment 2:Physical and medium access control layers for combined fixed and mobile operation in Licensed bands and corrigendum［S］.New York:IEEE，2006.

［6］Abry P，Veitch D.Wavelet analysis of long－range－dependent traffic［J］.IEEE Transactions on Information Theory，1998，44(1):2－15.

［7］Abry P，Flandrin P，Taqqu M S，et al.Self－similarity and long－range dependence through the wavelet lens［M］//Long-Range Dependence:Theory and Applications.Boston:Birkh?user，2003:527－556.

［8］Abry P，Goncalves P，Flandrin P.Wavelets，spectrum analysis and 1/fprocesses［C］//IEEE International Conference on Acoustics，Speech，and Signal Processing.Minneapolis，USA，1993:237－240.

［9］Chen J H，Wang C C，Tsai F C D，et al.Design and implementation of WiMAX module for ns－2 simulator［C］//Proceedings of the Workshop on ns-2:the IP Network.New York，USA，2006:1－6.

［10］Adas A.Traffic models in broadband networks［J］.IEEE Communications Magazine，1997，35(7):82－89.

［11］Fan Y H，Georganas N D.On merging and splitting of self－similar traffic in high－speed networks［C］//Proceedings of the12th International Conference on Computer Communication on Information Highways.Seoul，Korea，1995:1－6.

Wavelet analysis-based long range dependence in WiMax traffic

Hu Yongdong1，2，3Wu Guoxin1，2Xu Yiqing1，2，3

(1School of Computer Science and Engineering，Southeast University，Nanjing 211189，China)(2Key Laboratory of Computer Network and Information Integration of Ministry of Education，Southeast University，Nanjing 211189，China)(3College of Information Science and Technology，Nanjing Forestry University，Nanjing 210037，China)

In order to detect long－range dependence(LRD)in the WiMax network traffic accurately and efficiently，using the scale invariance property of self－similar stochastic process and the wavelet transform，the statistics of LRD Hurst parameters and wavelet coefficients are established.Then，the wavelet analysis algorithm of LRD in network traffic is studied.Repeated selection of wavelet vanishing moments and the optimization of the range of the scale parameter can reduce the impact on the test results.By the ON/OFF model，five different types of traffic in WiMax networks are simulated.And then the wavelet analysis method is used to analyze the trace file.The test results show that LRD of the real－time traffic is small，but LRD of non－real－time traffic is relatively large.As the network load increases，LRD of network traffic may change slightly.The detection value of LRD of aggregate flow is basically consistent with the theoretical value.

WiMax traffic;long range dependence;Hurst parameter;wavelet analysis

TP393

A

1001－0505(2013)01－0001－05

10.3969/j.issn.1001－0505.2013.01.001

2012－06－18.

胡永東(1973—)，男，博士生;吳國新(聯系人)，男，教授，博士生導師，gwu@seu.edu.cn.

江蘇省自然科學基金資助項目(BK2011335).

胡永東，吳國新，徐逸卿.基于小波分析的WiMax網絡業務流長相關性［J］.東南大學學報:自然科學版，2013，43(1):1－5.［doi:10.3969/j.issn.1001 －0505.2013.01.001］