基于AR(n)模型的網絡帶寬流量動態分配預測算法研究

趙明

(天津交通職業學院， 天津 300110)

基于AR(n)模型的網絡帶寬流量動態分配預測算法研究

趙明

(天津交通職業學院， 天津 300110)

網絡突發式的流量變化已經逐步取代平穩的語音服務，需要網絡能夠動態預測和調整流量分配。AR(n)模型作為網絡流量預測中常用算法，相比于自相似模型其預測的精度稍有不足，但在計算性能上表現較好，以粒子群算法對AR(n)模型進行預測精度調優，采用AIC準則判斷模型的最佳階數。通過實驗比較研究了最小二乘、灰色理論估計和自相似模型在預測精度和計算性能上差異性，實驗結果表明，基于粒子群的AR(n)模型具有較好的預測精度。

AR(n)模型； 流量預測； AIC準則； 粒子群算法； 預測精度

0 引言

數據快速增長使得網絡流量發生非常明顯的變化，傳統的基于語音傳輸的穩定流量網絡已經逐漸退出主流舞臺，取而代之的是網絡流量趨于動態變化的突發式網絡狀態[1]。通常而言，網絡流量的變化具有一定的不確定性，因為受到多種因素的制約和影響，每個因素都可能導致流量的激增或變化[2][3]。在一定程度上，網絡數據的傳輸依賴帶寬資源，帶寬在傳輸介質固定的情況下較為穩定不易發生改變，因此在網絡帶寬固定的情況下如何動態的調配網絡流量的分配至關重要[4]。

網絡帶寬的流量動態分配需要根據當前網絡的數據傳輸和網絡通道數據量進行動態調整，保證數據傳輸的最大效率和最低時延[5]。研究表明，網絡流量的特性符合自相似分布，表現為網絡流量在不同時間尺度上具有相似的突變尺度，具有長相關性的數據統計規律。針對長相關性的網絡流量預測分為兩個方向：基于時序模型和自相似模型[6]。基于自相似模型通常能夠獲得較高的預測精度，但存在運算復雜度過高的缺陷，難以滿足在網絡傳輸過程中快速高效預測運算的要求[7][8]。本文主要針對基于時序的AR(n)模型預測精度不足的問題，采用粒子群算法對模型階數進行優化訓練，粒子群算法作為一種全局優化算法，在AR(n)模型的階數訓練過程中通過粒子群算法迭代預測誤差，當預測誤差達到設定終止條件則定義當前的階數為最佳階數。

1 AR(n)模型

AR(n)模型將自相似網絡的流量預測通過差值運算或者對數變換轉換為平穩的時間序列預測，時間序列的預測可以通過成熟的數學模型實現[9]。一般情況下，大時間范圍內的時間序列預測的準確性要優于短時間范圍內的時間序列預測。AR(n)模型的時間序列預測通過對歷史時間片段的數據按照一定的線性組合預測當前時刻的樣本值[10]。

假設時間序列X={xt},t∈(1,N)，則對于樣本值X的預測結果,如式1。

(1)

在公式1中，αi表示預測系數，δ服從NID(0,σ2)的高斯分布。從公式1中可以看出，AR(n)模型的關鍵是預測系數和δ的誤差分布[11]。AR(n)模型有別于經典的LR模型，LR模型是基于預測值本身的特質信息進行預測，而時間序列預測的關鍵是根據歷史時間的觀察值預測當前的狀態或者觀察值。

對公式1進行等式變化，得到式(2)。

(2)

根據式(2)，進行方差運算,得到式(3)。

(3)

根據式(3)可知，AR(n)模型的求解α1,α2,…,αt-n過程實際是求解各個預測系數的問題，可以采用經典的參數估計算法——Levinson—Durbin算法實現參數預測[12]。該算法的主要思路是通過最優化當前的樣本序列的預測系數，在滿足當前最小化預測誤差的前提下使用Yule—Walker方法迭代地求解模型參數。

根據式(1)，為方便公式變化和參數整齊，將式(1)中X用xt代替，公式共同遞增xt-k并同時求解期望，如式(4),

(4)

令自相關函數R(k)如式(5),

(5)

根據式(4)和式(5)可以得到預測系數的線性表示方式,如式6。

(6)

2 流量分配預測

網絡流量呈現突發式的變化，在固定的網絡環境下網絡的承載能力是有限的，根據網絡歷史的負載情況預測當前的網絡流量具有非常重要的意義。網絡流量在時間上符合一定的時序特性，通過時間序列挖掘分析預測當前時間下的流量。

2.1 粒子群算法

粒子群算法作為一種全局優化算法，通過模擬群鳥覓食的場景而產生，每個粒子都維持一個局部的最優解，時刻調整全局的最優解來更新路徑[13]。粒子群算法可描述為在D維空間n個粒子構成的集合X=(X1,X2,…,Xn),每個粒子都維持一個當前的優化速度vi,同時記錄當前迭代次數的最優狀態和全局的最優狀態，動態更新全局最優狀態和每個粒子的優化方向,如式(7),

(7)

在式(7)中，pc表示當前最優解，pg表示全局最優解，r表示隨機數，η1和η2表示系數[14]。粒子群算法可以歸納為如下步驟。

1) 初始化粒子群，設定初始狀態下局部最優解pc和全局最優解pg；

2) 對每個粒子分別比較當前搜索狀態下的最優解是否需要更新當前局部最優解；

3) 針對每個粒子的局部最優解和全局最優解進行比較權衡更新；

4) 更新每個粒子的速度和位置信息；

5) 若算法不收斂，則跳轉到步驟2繼續。

2.2 流量預測

(8)

采用AR(n)模型進行階數訓練時采用AIC準則判斷收斂條件，如式9。

(9)

AIC準則[15]需要考慮當前對原始數據的擬合程度又需要考慮模型中參數的個數，設最大階數為M,M的取值一般為總數據的三分之一。將數據集X中每個分量X(i)表示為X(i)=(x(i-1),x(i-2),…,x(i-p))(i=p+1,…,k),得到式(9)。

(9)

3 實驗與分析

試驗以本校校園網絡作為測試載體，共監聽一天的網絡流量數據，將一天以小時作為切分單位，共分為24個時間段，選取15個時間段中正常時間段(夜間等時間段需要剔除)，試驗以4 ms為一個測試時間段，在15個時間段中隨機抽取某個4 ms時間范圍進行流量監測。試驗首先對比在不同網絡負載下本文算法的預測方差如圖1所示。

在圖1中共對比網絡負載在0.2、0、5和0、8 3種情況下本文算法的預測方差，網絡負載的值越大表明當前的網絡越繁忙，需要處理更多的數據傳輸。從3種負載情況下的數據對比可以很明顯地看出本文算法的預測效果，本文算法在不同網絡負載情況下的表現較為明顯，網絡負載越大方差越小，說明本文算法在網絡負載較大時的預測準確性較高。另外，在不同網絡負載的情況下方差并非完全單調呈現一定的變化趨勢，這與選取的網絡時段有關系，4 ms的時間段范圍非常窄網絡突變情況下網絡流量的監測較為不易，對異常網絡流量的監測存在一定的不及時性,如圖2所示。

圖1 不同網絡負載下AR(n)模型預測方差對比圖

圖2 不同算法在網絡負載0.8下AR(n)模型預測方差對比圖

圖2中分別對比了本文算法(POS_ALG)、最小二乘算法(LSM_ALG)、灰色估計算法(GREY_ALG)三種算法在網絡負載為0.8時算法的預測情況。從圖2中可以看出，本文算法的預測準確性上要優于最小二乘算法和灰色估計算法，另外本文算法的預測準確性也是要優于其它兩種算法。相比于在網絡負載為0.2和0.5時情況，本文算法的預測效果和最小二乘、灰色估計這兩種算法相近。

4 總結

本文分析了當前互聯網快速發展時代網絡流量突然的情形，網絡環境已經從傳統的穩定語音傳輸到流量時刻突變的網絡時代，在硬件條件固定的情況下，網絡的傳輸能力是一定的，根據時間序列的預測方式預測網絡流量并實時地調整信道傳輸，從而使得網絡數據傳輸效率最大化。本文以AR(n)模型作為流量預測模型，以粒子群算法訓練時序模型的階數克服了AR(n)模型預測精度不高的缺陷，實驗結果表明，本文算法在網絡負載較大情況下表現要優于低負載情況，同時對比了最小二乘和灰色估計算法的預測準確性，本文算法預測方差較為穩定且較低，從而表明本文算法具有較高的預測準確性。

[1] 楊斌博,李廣成. RoF和xPON的混合組網探討[J]. 光通信技術,2016,05:1-4.

[2] 鄺斌,劉人榕,吳雅婷,等. 基于流量預測的OFDMA-PON動態帶寬分配算法[J]. 光通信技術,2016(5):11-14.

[3] 韓丹,陳雪. 結合狀態指示和流量預測的GPON DBA算法[J]. 光通信技術,2009(5):14-17.

[4] Chen P, Pedersen T, Bak-Jensen B, et al. ARIMA-based time series model of stochastic wind power generation[J]. IEEE Transactions on Power Systems, 2010, 25(2): 667-676.

[5] 于立曉,陳科明,馬琪. 周期可變和流量預測的XG-PON DBA算法[J]. 光通信技術,2011(7):57-59.

[6] 唐麗珠. 出院病人人均醫藥費用的AR(n)嶺估計模型及預測應用[J]. 時代金融,2013(32):302.

[7] 羅娟,唐利民. 正則化的時間序列AR模型及其在經濟分析中的應用[J]. 價值工程,2010(2):86-87.

[8] 付子義,呂鎖柱,宋昀. 基于多業務預測的EPON動態帶寬分配算法[J]. 光通信技術,2010(4):12-14.

[9] 鄒鋒,汪敏,鄒君妮. WDM EPON中的動態波長帶寬分配算法[J]. 光通信技術,2008(12):25-28.

[10] Box G E P, Jenkins G M, Reinsel G C, et al. Time series analysis: forecasting and control[M]. John Wiley & Sons, 2015.

[11] 唐毅,劉衛寧,孫棣華,等. 改進時間序列模型在高速公路短時交通流量預測中的應用[J]. 計算機應用研究,2015(1):146-149.

[12] 郭海華,劉瑞瑞. 基于聚類分析和時間序列方法的我國物流量預測研究[J]. 商業經濟研究,2015(20):29-30.

[13] Brockwell P J, Davis R A. Time series: Theory and methods[M]. Springer Science & Business Media, 2013.

[14] 鄧榮. 基于包絡特征的網絡流量預測閾值調控算法[J]. 科技通報,2015(10):67-69.

[15] 劉朝霞. 基于隨機陣列向量模型的流量預測算法研究[J]. 科技通報,2015(10):196-198.

[16] 張鳳荔,趙永亮,王丹,等. 基于流量特征的網絡流量預測研究[J]. 計算機科學,2014,04:86-89.

[17] 田梅. 基于混沌時間序列模型的圖書借閱流量預測研究[J]. 圖書館理論與實踐,2013(7):1-3+26.

Research on Network Bandwidth Allocation Algorithm Based on AR(n) Model

Zhao Ming

(Tianjin Transportation Vocational College，Tianjin 300110, China)

Network burst traffic changes have gradually substituted the smooth voice service, and the network needs to be able to dynamically predict and adjust the flow distribution. AR(n) model, a network traffic prediction algorithm, has several shortages compared with self-similar model on prediction accuracy, but holds well computing performance. Particle swarm optimization algorithm is adopted to optimize the AR(n) model with the AIC criterion. The experimental results on an open dataset show that the improved algorithm acquires well prediction accuracy compared with least-square, grey theory and self-similar models.

AR(n) model; Flow prediction; AIC criterion; PSO algorithm; Prediction accuracy

趙明(1981-)，男，天津人，碩士，講師，研究方向：軟件工程、計算機與網絡技術。

1007-757X(2017)06-0061-03

TN929

A

2017.03.29)