王石， 楊懷江， 董琰

(1.中國(guó)科學(xué)院長(zhǎng)春光學(xué)精密機(jī)械與物理研究所，吉林，長(zhǎng)春 130033；2.中國(guó)科學(xué)院大學(xué)，北京 100039；3.東北師范大學(xué) 信息化管理與規(guī)劃辦公室，吉林，長(zhǎng)春 130024)

?

基于混沌理論的局域網(wǎng)流量預(yù)測(cè)

王石1，2，3， 楊懷江1， 董琰3

(1.中國(guó)科學(xué)院長(zhǎng)春光學(xué)精密機(jī)械與物理研究所，吉林，長(zhǎng)春 130033；2.中國(guó)科學(xué)院大學(xué)，北京 100039；3.東北師范大學(xué) 信息化管理與規(guī)劃辦公室，吉林，長(zhǎng)春 130024)

局域網(wǎng)業(yè)務(wù)流中廣泛存在自相似為特征的現(xiàn)象，并且自相似現(xiàn)象與混沌現(xiàn)象間存在緊密聯(lián)系. 通過采用局域網(wǎng)流量對(duì)應(yīng)的時(shí)間序列分析的方法進(jìn)行研究，基于相空間重構(gòu)思想，通過C-C算法計(jì)算嵌入維和延遲時(shí)間；利用小數(shù)據(jù)量法計(jì)算局域網(wǎng)流量時(shí)間序列的最大Lyapunov指數(shù)來判斷其混沌特性；針對(duì)基于最大Lyapunov指數(shù)的預(yù)測(cè)方法中只考慮中心點(diǎn)的最鄰近點(diǎn)對(duì)預(yù)測(cè)的決定性作用，而忽略了其鄰近點(diǎn)鄰域內(nèi)其他各點(diǎn)對(duì)預(yù)測(cè)結(jié)果的影響的特點(diǎn)，提出了基于最大Lyapunov指數(shù)的加權(quán)鄰域預(yù)測(cè)法；最后通過實(shí)測(cè)局域網(wǎng)流量預(yù)測(cè)驗(yàn)證方法的有效性.

混沌時(shí)間序列；小數(shù)據(jù)量法；局域網(wǎng)流量預(yù)測(cè)

互聯(lián)網(wǎng)誕生以來，網(wǎng)絡(luò)的設(shè)計(jì)者和研究者一直對(duì)網(wǎng)絡(luò)流量的建模和預(yù)測(cè)進(jìn)行不斷的探索. 從早期的傳統(tǒng)模型，如泊松模型、馬爾可夫模型、回歸模型到后來的自相似模型，如on/off模型、排隊(duì)模型、FBM模型、FARIMA模型[1-7]. 傳統(tǒng)模型的不足是當(dāng)業(yè)務(wù)源數(shù)目增加時(shí)，突發(fā)性會(huì)被吸收，聚合業(yè)務(wù)會(huì)變得越來越平滑，而現(xiàn)代網(wǎng)絡(luò)流量特性為高速、突發(fā)、自相似. 因此傳統(tǒng)模型已不適合對(duì)現(xiàn)代網(wǎng)絡(luò)流量進(jìn)行準(zhǔn)確描述. 自相似模型雖可以較好地描述網(wǎng)絡(luò)流量的自相似性，但是存在假設(shè)條件嚴(yán)格、模型功能單一、計(jì)算量大等缺點(diǎn). 已有學(xué)者發(fā)現(xiàn)局域網(wǎng)業(yè)務(wù)流中廣泛存在著以自相似為特征的現(xiàn)象，并且與混沌現(xiàn)象間存在緊密聯(lián)系，因此從混沌時(shí)間序列的角度來研究具有自相似特征的局域網(wǎng)流量是可行的. 本文通過采用局域網(wǎng)流量對(duì)應(yīng)的時(shí)間序列分析的方法進(jìn)行研究，基于相空間重構(gòu)思想[8]，通過C-C算法[9]計(jì)算嵌入維和延遲時(shí)間，利用小數(shù)據(jù)量法[10]計(jì)算最大Lyapunov指數(shù)，判斷時(shí)間序列的混沌特性并進(jìn)行預(yù)測(cè)；針對(duì)基于最大Lyapunov指數(shù)的預(yù)測(cè)方法中只考慮到預(yù)測(cè)中心點(diǎn)的最鄰近點(diǎn)對(duì)預(yù)測(cè)的決定性作用，而忽略了其鄰近點(diǎn)鄰域內(nèi)其他各點(diǎn)對(duì)預(yù)測(cè)結(jié)果的影響的特點(diǎn)，提出了基于最大Lyapunov指數(shù)的加權(quán)鄰域預(yù)測(cè)法；最后，通過對(duì)某高校出口流量數(shù)據(jù)的實(shí)驗(yàn)和分析來驗(yàn)證方法的有效性.

1 相空間重構(gòu)

根據(jù)Takens理論，對(duì)于時(shí)間序列{xi}，i=1，2，…，N，如果能選定合適嵌入維數(shù)m，以時(shí)間延遲t重構(gòu)相空間如下

(1)

相點(diǎn)總數(shù)M=N-(m-1)t. 如此得到的相空間在拓?fù)涞葍r(jià)意義下與原混沌序列是微分同胚的，可以把有規(guī)律的軌跡(吸引子)恢復(fù)出來. 有多種方法可以計(jì)算m和t，H.S.Kim等提出C-C算法，該算法應(yīng)用關(guān)聯(lián)積分能同時(shí)估計(jì)出延遲時(shí)間t和嵌入時(shí)間窗tw；同時(shí)根據(jù)D.Kugiumtzis提出的延遲時(shí)間和嵌入維不應(yīng)該是獨(dú)立的量而是存在緊密的內(nèi)在聯(lián)系，并且滿足關(guān)系式tw=(m-1)t的理論，進(jìn)而計(jì)算出嵌入維m.

算法步驟：

① 嵌入時(shí)間序列的關(guān)聯(lián)積分為

(2)

② 定義統(tǒng)計(jì)量

(3)

③ 為研究時(shí)間序列{xi}，i=1，2，…，N的非線性獨(dú)立性并且消除虛假的時(shí)間相關(guān)性，式(3)的計(jì)算過程為將時(shí)間序列分成t個(gè)互不相交的子序列，然后采用分塊平均的策略，即

(4)

④ 選擇最大和最小的兩個(gè)半徑r，定義差量

(5)

ΔS(m，t)～t反映了時(shí)間序列的自相關(guān)特性，仿照求時(shí)延的自相關(guān)法原理，最優(yōu)時(shí)延t可取ΔS(m，t)～t的第一個(gè)局部極小點(diǎn). 此時(shí)表示重構(gòu)吸引子軌道在相空間完全展開.

⑤基于BDS統(tǒng)計(jì)結(jié)果可以得到m，N，r的合理估計(jì)，這里取N=1 760；m=2，3，4，5；ri=ix0.5σ，i=1，2，3，4(σ表示時(shí)間序列標(biāo)準(zhǔn)差). 計(jì)算平均量

(6)

(7)

定義指標(biāo)

(8)

Scor(t)極小點(diǎn)對(duì)應(yīng)的時(shí)間即為嵌入時(shí)間窗tw.

⑥ 利用公式tw=(m-1)t及步驟④求出的時(shí)間延遲t可以計(jì)算出嵌入維m.

2 小數(shù)據(jù)量法

小數(shù)據(jù)量法是一種計(jì)算混沌時(shí)間序列的最大Lyapunov指數(shù)的方法. 最大Lyapunov指數(shù)可以定量描述初始狀態(tài)靠得很近的相空間軌跡隨時(shí)間變化按指數(shù)分離的程度；并且可以依據(jù)其估計(jì)系統(tǒng)的混沌水平和復(fù)雜度. 算法中用關(guān)聯(lián)維數(shù)確定嵌入維數(shù)的方法計(jì)算量較大；結(jié)果易受參數(shù)選擇的影響. 因此采用C-C算法來同時(shí)確定嵌入維數(shù)與時(shí)間延遲.

算法步驟：

① 對(duì)時(shí)間序列{xi}，i=1，2，…，N進(jìn)行FFT變換，以能量光譜的平均頻率的倒數(shù)估計(jì)平均周期P. 平均周期作為限制性條件可以保證估計(jì)最大Lyapunov指數(shù)的鄰近點(diǎn)具有相近的初始條件并且按平均速率分離；

② 根據(jù)C-C算法確定的時(shí)間延遲t和嵌入維數(shù)m重構(gòu)相空間Yi∈Rm；

③ 尋找相空間中每個(gè)點(diǎn)Yi的最鄰近點(diǎn)Yj，并限制短暫分離，即

(9)

④ 對(duì)相空間中每個(gè)點(diǎn)Yi，計(jì)算出該鄰點(diǎn)對(duì)的k個(gè)離散時(shí)間步后的距離di(k)，

(10)

⑤ 對(duì)每個(gè)k，求出所有i的lndi(k)平均值為

(11)

式中：q為非零di(k)的數(shù)目；h為采樣周期.

用最小二乘法作出回歸直線，該直線的斜率即最大Lyapunov指數(shù)λ1.

3 基于最大Lyapunov指數(shù)的預(yù)測(cè)法

最大Lyapunov指數(shù)可定量描述兩個(gè)很靠近的初值所產(chǎn)生的軌道隨時(shí)間推移按指數(shù)方式分離的現(xiàn)象[7-8]. 因此可以按照如下步驟預(yù)測(cè)：

① 根據(jù)由C-C算法確定的時(shí)間延遲t和嵌入維數(shù)m，重構(gòu)相空間Yi∈Rm，相點(diǎn)總數(shù)M=N-(m-1)t；

② 選取預(yù)報(bào)中心點(diǎn)YM，找到Y(jié)M最鄰近點(diǎn)Yj，兩相點(diǎn)各自隨時(shí)間推移一步，其軌道距離將按指數(shù)分離，可表示為

(12)

式(12)中只有YM+1的最后一個(gè)分量xn+1是未知的，從而可以計(jì)算出原時(shí)間序列的一步預(yù)測(cè)值xn+1；

③ 依次隨時(shí)間推移選取預(yù)測(cè)中心點(diǎn)YM+1，YM+2，…，利用步驟②預(yù)測(cè)值并重復(fù)執(zhí)行步驟②，可以計(jì)算有限步推測(cè)值xn+2，xn+3，…；

④ 最大可預(yù)報(bào)時(shí)間依然可以依據(jù)此理論推測(cè). 兩最鄰近相點(diǎn)Yi與Yj，各自隨時(shí)間推移k步，其軌道距離按指數(shù)分離，可表示為

(13)

式中d(0)為兩相點(diǎn)的初始距離.

可以認(rèn)為上式超過臨界C時(shí)，軌道發(fā)散到不可預(yù)言，這時(shí)所經(jīng)歷的時(shí)間就是臨界時(shí)間，即最大可預(yù)報(bào)時(shí)間t0，并且有t0=lnC/λ1. 通常取C=e或更小，可得到最大可預(yù)報(bào)時(shí)間：t0=1/λ1.

4 基于最大Lyapunov指數(shù)的加權(quán)鄰域預(yù)測(cè)法

基于最大Lyapunov指數(shù)的預(yù)測(cè)法只考慮了預(yù)測(cè)中心點(diǎn)與其最鄰近點(diǎn)的距離對(duì)預(yù)測(cè)結(jié)果的決定性作用. 深入分析發(fā)現(xiàn)，最大Lyapunov指數(shù)對(duì)兩個(gè)很靠近的初值所產(chǎn)生的軌道隨時(shí)間推移按指數(shù)分離的定量描述只是一個(gè)帶有主觀因素的大略估計(jì). 實(shí)際上在進(jìn)行局域網(wǎng)流量預(yù)測(cè)時(shí)，由于舍入關(guān)系，按距離計(jì)算個(gè)別點(diǎn)的最鄰近點(diǎn)有時(shí)存在多個(gè)點(diǎn)距離相等或舍入以后相等的情況. 預(yù)測(cè)中心點(diǎn)的最鄰近點(diǎn)的鄰域內(nèi)其他各點(diǎn)距預(yù)測(cè)中心點(diǎn)的空間距離是非常重要的參數(shù)，預(yù)測(cè)的準(zhǔn)確性往往取決于距中心點(diǎn)空間距離最近的那幾個(gè)點(diǎn). 因此將其作為一個(gè)擬合參數(shù)引入預(yù)測(cè)過程，在一定程度上可以提高預(yù)測(cè)的精度，并有一定的消噪能力.

算法步驟為：

① 根據(jù)由C-C算法確定的時(shí)間延遲t和嵌入維數(shù)m，重構(gòu)相空間Yi∈Rm，相點(diǎn)總數(shù)M=N-(m-1)t；

② 選取預(yù)報(bào)中心點(diǎn)YM，確定其最鄰近點(diǎn)及鄰域各點(diǎn)Yj，j=1，2，…，k，選取點(diǎn)數(shù)k>m+1，太多沒有必要，甚至影響預(yù)測(cè)效果. 依據(jù)基于最大Lyapunov指數(shù)預(yù)測(cè)法分別計(jì)算出鄰域內(nèi)各點(diǎn)對(duì)應(yīng)的下一步預(yù)測(cè)值xn+1(j)，j=1，2，…，k；

③ 設(shè)臨近點(diǎn)距中心點(diǎn)距離為dj，j=1，2，…k，其中d0為dj中最小值，即中心點(diǎn)與其最鄰近點(diǎn)間距離. 定義權(quán)值

(14)

式中：θ為收斂參數(shù)，取θ=k；

則預(yù)測(cè)值可以表示為

(15)

④ 依次隨時(shí)間推移選取預(yù)測(cè)中心點(diǎn)M+1，YM+2，…，利用步驟③預(yù)測(cè)值并重復(fù)執(zhí)行步驟③，可以計(jì)算有限步推測(cè)值xn+2，xn+3，…；

⑤ 最大可預(yù)報(bào)時(shí)間同基于最大Lyapunov指數(shù)的預(yù)測(cè)法.

5 局域網(wǎng)流量的預(yù)測(cè)

所分析局域網(wǎng)流量數(shù)據(jù)來自某高校核心交換機(jī)聯(lián)通出口數(shù)據(jù). 測(cè)試時(shí)間為2014年5月10日至3月15日. 采樣周期30 s，采樣點(diǎn)數(shù)1 800個(gè).

采用C-C算法計(jì)算出m=12，t=10. 利用以上參數(shù)基于改進(jìn)的小數(shù)據(jù)量法計(jì)算最大Lyapunov指數(shù)λ1=0.148 9. 最大Lyapunov指數(shù)大于0，說明該時(shí)間序列具有混沌特征.t0=1/λ1=6.7，最大預(yù)測(cè)時(shí)間為7步. 根據(jù)基于最大Lyapunov指數(shù)的預(yù)測(cè)法及改進(jìn)的加權(quán)鄰域預(yù)測(cè)法分別做出了局域網(wǎng)流量時(shí)間序列后續(xù)7個(gè)點(diǎn)的預(yù)測(cè)值，見表1和表2.

表1 基于最大Lyapunov指數(shù)的預(yù)測(cè)法預(yù)測(cè)結(jié)果

Tab.1 Predicted results based on the largest Lyapunov prediction method

序號(hào)lnk/(Mbit·s-1)預(yù)測(cè)值/(Mbit·s-1)相對(duì)誤差絕對(duì)值/%17.0707.0080.8927.0617.2412.5437.0306.9441.2246.9877.2413.8857.0037.1311.8367.0247.0161.8476.9967.3064.51

注：k為校園網(wǎng)聯(lián)通出口實(shí)測(cè)流量數(shù)據(jù)

表2 基于加權(quán)鄰域預(yù)測(cè)法預(yù)測(cè)結(jié)果

Tab.2 Predicted results based on the weighted neighborhood prediction method

序號(hào)lnk/(Mbit·s-1)預(yù)測(cè)值/(Mbit·s-1)相對(duì)誤差絕對(duì)值/%17.0706.9711.5127.0617.1771.7337.0306.9191.7046.9877.1772.9657.0037.0711.1267.0247.1762.8076.9966.9201.18

注：k為校園網(wǎng)聯(lián)通出口實(shí)測(cè)流量數(shù)據(jù)

由表1和表2的數(shù)據(jù)對(duì)比可知利用基于最大Lyapunov指數(shù)的預(yù)測(cè)法預(yù)測(cè)局域網(wǎng)流量數(shù)據(jù)相對(duì)誤差絕對(duì)值在5%以內(nèi)；利用基于最大Lyapunov指數(shù)的加權(quán)鄰域法進(jìn)行局域網(wǎng)流量預(yù)測(cè)相對(duì)誤差絕對(duì)值在3%以內(nèi)，預(yù)測(cè)精度有明顯提高.

6 結(jié) 論

① 基于相空間重構(gòu)理論，用C-C算法計(jì)算嵌入維和延遲時(shí)間，再利用小數(shù)據(jù)量法計(jì)算局域網(wǎng)時(shí)間序列的最大Lyapunov指數(shù)，可以通過最大Lyapunov指數(shù)是否大于0明確判斷時(shí)間序列是否具有混沌性. 使基于混沌理論的局域網(wǎng)流量預(yù)測(cè)有了有力的理論依據(jù). 需要注意的是，局域網(wǎng)流量在較長(zhǎng)的時(shí)間范圍內(nèi)體現(xiàn)明顯的周期性，周期為24 h，因此本方法在局域網(wǎng)流量時(shí)間序列的選取上有一定的限制條件，但是基于混沌理論的局域網(wǎng)流量短時(shí)預(yù)測(cè)比較可靠，是一種很有意義的嘗試.

② 針對(duì)基于最大Lyapunov指數(shù)預(yù)測(cè)法沒有利用到預(yù)報(bào)中心點(diǎn)的最鄰近點(diǎn)鄰域內(nèi)其他各點(diǎn)的物理含義進(jìn)行預(yù)測(cè)的情況，提出了基于最大Lyapunov指數(shù)的加權(quán)鄰域預(yù)測(cè)法. 對(duì)實(shí)際局域網(wǎng)流量進(jìn)行預(yù)測(cè)分析，結(jié)果表明改進(jìn)的預(yù)測(cè)算法在不嚴(yán)重增加計(jì)算復(fù)雜度的前提下，有效提高了預(yù)測(cè)精度.

[1] Bonald T. The Erlang model with non-poisson call arrivals[J]. ACM Sigmetrics Performance Evaluation Review， 2006，34(1):276-286.

[2] Yang X S， Petropulu A P. The extended alternating fractal renewal process for modeling traffic in high-speed communication networks[J]. IEEE Trans On Signal Processing， 2001，49(7):1349-1363.

[3] Frost V， Melamed B. Traffic modeling for telecommunications networks[J]. IEEE Communications Magazine， 1994，32(3):70-81.

[4] Sarvotham S， Riedi R， Baraniuk R. Network and user driven alpha-beta on-off source model for network traffic[J]. Computer Networks， 2005，48(3):335-350.

[5] Krunz M， Makowski M. Modeling video traffic using M/G/∞ input processes[J]. IEEE Journal of Selected Areas in Communications， 1998，16(5):733-748.

[6] Norros I. A storage model with self-similar input[J]. Queueing System， 1994，16(3，4):387-396.

[7] Beran J， Sherman R， Taqqu M S， et al. Long-range dependence in variable-bit-rate video traffic[J]. IEEE Trans on Communications， 1995，43 (2-4):1566-1579.

[8] Takens F. Detecting strange attractors in turbulence[J]. Lecture Notes in Math，1981，898:361-381.

[9] Kim H S， Eykholt R， Salas J D. Nonlinear dynamics， delay times and embedding windows[J]. Physica D: Nonlinear Phenomena， 1999，127(1):48-60.

[10] Rosenstein M T， Collins J J， Deluca C J. A practical method for calculating largest Lyapunov exponents from small data sets[J]. Physica D: Nonlinear Phenomena， 1993，65(1):117-134.

(責(zé)任編輯：李兵)

Prediction in LAN Traffic Flow Based on Chaos Theory

WANG Shi1，2，3， YANG Huai-jiang1， DONG Yan3

(1.Changchun Institute of Optics， Fine Mechanics and Physics， Chinese Academy of Sciences， Changchun， Jilin 130033， China; 2.University of Chinese Academy of Sciences， Beijing 100039， China 3.Office of Information Management and Planning， Northeast Normal University， Changchun， Jilin 130024，China )

There exists widely the self-similarity in LAN traffic flow, and there is a close relationship between the self similarity characteristics and chaotic phenomena. The LAN time series of traffic flow were reconstructed in phase space theory. The embedding dimension and the delay time were computed by the C-C algorithm, and the largest Lyapunov exponent was then calculated via the small data method to determine its chaotic level. The weighted neighborhood prediction method was proposed and conducted considering the only decisive role of the nearest point on the center point based on the largest Lyapunov exponent while ignoring its neighborhood points on the predicting affection. The validation of the method was done by predicting the actual LAN traffic flow.

chaos time series; small data method; LAN traffic flow prediction

2015-03-11

吉林省教育廳“十二五” 科技與社科研究規(guī)劃資助項(xiàng)目(2014B053)；吉林省科技廳吉林省自然科學(xué)基金資助項(xiàng)目(20140101189JC)

王石(1979—)，男，碩士，工程師，E-mail：wangs@nenu.edu.cn.

TP393

A

1001-0645(2016)06-0616-04

10.15918/j.tbit1001-0645.2016.06.012