基于PSO-BP神經(jīng)網(wǎng)絡(luò)的網(wǎng)絡(luò)時延預(yù)測算法

時維國，雷何芬

（大連交通大學(xué) 電氣信息工程學(xué)院，大連116028）

網(wǎng)絡(luò)控制系統(tǒng)NCS（networked control system）中傳輸時延受到通信網(wǎng)絡(luò)協(xié)議、節(jié)點驅(qū)動方式、路由算法等因素影響，呈現(xiàn)出隨機變化的非線性特性[1-2]。針對NCS 時延問題，文獻[3-6]通過對NCS 中時延數(shù)據(jù)的分析處理，來建立數(shù)學(xué)模型對網(wǎng)絡(luò)時延進行預(yù)測。盡管數(shù)學(xué)模型能夠準(zhǔn)確地表達輸入與輸出之間的函數(shù)關(guān)系，但由于網(wǎng)絡(luò)時延具有隨機性，很難準(zhǔn)確地對其進行建模，而神經(jīng)網(wǎng)絡(luò)算法是以神經(jīng)元為基礎(chǔ)模擬人腦的計算模型，可以映射和逼近很多函數(shù)，無需對樣本進行分析建立數(shù)學(xué)模型，如文獻[7-10]采用神經(jīng)網(wǎng)絡(luò)對NCS 時延進行預(yù)測。在眾多神經(jīng)網(wǎng)絡(luò)算法中，由于BP 神經(jīng)網(wǎng)絡(luò)BPNN（back propagation neural network）具有網(wǎng)絡(luò)結(jié)構(gòu)比較簡單，神經(jīng)元個數(shù)少，運算量小等優(yōu)點，在預(yù)測方面有著很多的應(yīng)用。

圖1 單隱層BPNN 結(jié)構(gòu)Fig.1 Single hidden layer BPNN structure

在此，采用BPNN 算法對NCS 時延進行預(yù)測，針對BPNN 收斂速度慢，易陷入局部極值的問題，利用粒子群算法PSO 優(yōu)化BPNN 中的初始權(quán)值和閾值來改善BPNN 的性能，提高算法收斂性，避免陷入局部極值點。

1 時延數(shù)據(jù)的采集及處理

1.1 時延數(shù)據(jù)的采集

在此采用Ping Tester Pro 軟件，對從某大學(xué)實驗室（IP 地址為192.168.43.136）訪問到某知名網(wǎng)站（IP 地址為39.156.66.18） 的時延數(shù)據(jù)進行采集，將采集的500 組時延數(shù)據(jù)導(dǎo)出作為試驗數(shù)據(jù)。此次網(wǎng)絡(luò)采集采用電腦連接手機熱點，因NCS 中傳感器采用時間驅(qū)動，故將軟件中參數(shù)設(shè)置為固定間隔發(fā)送，數(shù)據(jù)包大小為32 B。

1.2 時延數(shù)據(jù)的歸一化

數(shù)據(jù)的歸一化就是把需要處理的數(shù)據(jù)通過算法處理后，將數(shù)據(jù)限制在需要的一定范圍內(nèi)。數(shù)據(jù)的歸一化的目的是為了后續(xù)數(shù)據(jù)處理的方便和保證程序運行時快速收斂。在此，采用了最大最小標(biāo)準(zhǔn)化的歸一化方法，將樣本數(shù)據(jù)映射到數(shù)值［0，1］之間。其公式為

式中：x 為樣本數(shù)據(jù)；min（x），max（x）分別為樣本數(shù)據(jù)中的最小值、最大值；x′為數(shù)據(jù)歸一化后的數(shù)值。

2 粒子群優(yōu)化的BPNN 算法

2.1 BP 神經(jīng)網(wǎng)絡(luò)

BPNN 是在1986年由David E.Rumelhart 等學(xué)者提出的，是一種按照誤差逆向傳播算法訓(xùn)練的多層前饋神經(jīng)網(wǎng)絡(luò)。BPNN 由輸入層、隱含層、輸出層組成，每一層之間各神經(jīng)元相互獨立不連接，而層與層之間的神經(jīng)元相互連接。其原理是誤差的反向傳播采用梯度下降法更改網(wǎng)絡(luò)的連接權(quán)值和閾值，最終使網(wǎng)絡(luò)的實際輸出值與期望輸出值的誤差均方值達到要求的精度。單隱層BPNN 結(jié)構(gòu)如圖1 所示。

圖中，i 為輸入層的數(shù)目；j 為隱含層的數(shù)目；k為輸出層的數(shù)目；y 為BPNN 的實際輸出；yp為期望輸出；ωij為輸入層第個節(jié)點到隱含層第個節(jié)點之間的連接權(quán)值；ωjk為隱含層第個節(jié)點到輸出層第個節(jié)點之間的連接權(quán)值；θj為隱含層第個節(jié)點的閾值；θk為輸出層第個節(jié)點的閾值。

BPNN 包含數(shù)據(jù)傳輸?shù)那跋蛲ǖ篮驼`差的反向計算。在數(shù)據(jù)傳輸?shù)那跋蛲ǖ肋^程中，數(shù)據(jù)經(jīng)輸入層的神經(jīng)元處理后與ωij進行計算，其計算結(jié)果作為隱含層神經(jīng)元的輸入，隱含層神經(jīng)元的輸出與ωjk計算后作為輸出層神經(jīng)元輸入，輸出層神經(jīng)元的輸出即為BPNN 的輸出。將BPNN 的輸出值與期望值比較計算誤差。若誤差滿足設(shè)定的精度要求，則不進行誤差的反向計算； 否則需進行誤差的反向計算，通過梯度下降法改變各層神經(jīng)元之間的連接權(quán)值和神經(jīng)元的閾值，直至達到設(shè)定的誤差精度，或達到最大迭代次數(shù)停止計算。

2.2 粒子群算法

粒子群算法是一種群體智能的優(yōu)化算法，最早是在1995年由Kennedy 和Eberhart 提出。在PSO優(yōu)化算法中，將所有的優(yōu)化類問題當(dāng)做鳥群的捕食行為進行分析，鳥群中的一只鳥代表著優(yōu)化問題中的一個潛在的解，即PSO 算法中的一個粒子。鳥類在捕食的行為中會根據(jù)同伴的方向、速度來不斷地調(diào)整自己的位置，即PSO 中的粒子會根據(jù)適應(yīng)值調(diào)整自己的速度和位置迭代找到最優(yōu)解。

PSO 算法中，粒子的當(dāng)前特征可以通過粒子自身的適應(yīng)值表示其優(yōu)劣程度，粒子的搜索狀態(tài)用其當(dāng)前位置和速度表示。Pb為個體粒子在自身歷史的適應(yīng)值中為最優(yōu)的值所對應(yīng)的位置；Gb為所有粒子在歷史的適應(yīng)值中為最優(yōu)值所對應(yīng)的位置。粒子的適應(yīng)值隨迭代而更新，將新的適應(yīng)值與自己過去的最優(yōu)的適應(yīng)值Pb比較，如果新的適應(yīng)值比Pb對應(yīng)的適應(yīng)值小，則將新的適應(yīng)值對應(yīng)的位置賦值給Pb，再將Pb對應(yīng)的適應(yīng)值與Gb對應(yīng)的適應(yīng)值比較，若Pb對應(yīng)的適應(yīng)值比較小，則用Pb賦值給Gb，成為當(dāng)前全局最優(yōu)的位置。

假設(shè)，PSO 算法中，有H 個粒子組成一個種群，每個粒子的維度為N，xh為種群中第h 個粒子的位置，即xh=（xh1，xh2，…xhN），h＝1，2，…，H；vh為種群中第h 個粒子的速度，即vh=（vh1，vh2，…vhN）。

確定PSO 算法中求適應(yīng)值大小的目標(biāo)函數(shù)，根據(jù)目標(biāo)函數(shù)求出粒子的適應(yīng)值大小，通過比較適應(yīng)值大小確定粒子的當(dāng)前最優(yōu)位置和群體最優(yōu)位置。第h 個粒子的當(dāng)前最優(yōu)位置為Pbh；群體的當(dāng)前最優(yōu)位置為Gbh。即

在PSO 算法中，粒子通過當(dāng)前最優(yōu)位置和群體最優(yōu)位置，在每次的迭代中更新自己的速度和位置。PSO 算法公式為

其中

式中：ω 為慣性權(quán)重，其值的大小影響著粒子的全局和局部的尋優(yōu)能力；k 為粒子的當(dāng)前迭代次數(shù)；c1和c2為粒子的學(xué)習(xí)因子，其值大小影響著粒子的收斂性；r1和r2為選取的［0，1］之間的隨機數(shù)。PSO 算法中需對粒子的位置和速度設(shè)置合理范圍。PSO 算法的迭代停止條件為粒子達到最大迭代次數(shù)或適應(yīng)值大小滿足設(shè)定的要求。

2.3 PSO-BPNN 的時延預(yù)測模型

BPNN 算法對網(wǎng)絡(luò)連接權(quán)值和閾值的初始值很敏感，在相同條件的下對BPNN 賦予不同初始值的網(wǎng)絡(luò)連接權(quán)值和閾值，BPNN 會表現(xiàn)出不同的收斂速度。網(wǎng)絡(luò)連接權(quán)值和閾值的初始值離極值點近則收斂速度快；網(wǎng)絡(luò)連接權(quán)值與閾值的初始值離極值點遠則收斂速度慢。

PSO 算法是一種不斷學(xué)習(xí)的優(yōu)化算法，只需通過更新粒子的速度和位置就能實現(xiàn)對解空間的全局搜索從而得到最優(yōu)解，算法簡單且效率高。PSO優(yōu)化BPNN 的基本思想是：將BPNN 的連接權(quán)值和閾值的初始值當(dāng)成PSO 算法中的一個粒子，粒子的維度等于權(quán)值的個數(shù)加閾值的個數(shù)之和，取測試樣本的BPNN 的輸出值與實際期望值差值的平方和為PSO 算法的中適應(yīng)值函數(shù)，對BPNN 的初始連接權(quán)值和閾值進行優(yōu)化，利用優(yōu)化后PSO 算法的輸出值作為BPNN 的初始連接權(quán)值和閾值對樣本數(shù)據(jù)進行訓(xùn)練。

2.3.1 PSO-BPNN 的時延預(yù)測基本步驟

步驟1將測得500 組時延數(shù)據(jù)做歸一化處理后分為樣本數(shù)據(jù)400 組，測試數(shù)據(jù)100 組。

步驟2初始化BPNN。確定BPNN 的網(wǎng)絡(luò)結(jié)構(gòu)、各層神經(jīng)元處理函數(shù)，給各參數(shù)賦初值。

步驟3初始化PSO 算法。隨機選取H 組滿足BPNN 初始權(quán)值和閾值要求的粒子，并給PSO 算法中其他參數(shù)賦初值；將測試數(shù)據(jù)通過BPNN 的正向傳播的輸出值與期望值之間的差值的平方和作為PSO 算法的適應(yīng)值函數(shù)。

步驟4計算粒子的適應(yīng)值。

步驟5判斷粒子的迭代次數(shù)。若粒子的迭代次數(shù)未達到設(shè)定值，則根據(jù)式（2）和式（3）更新粒子的速度、位置，且迭代次數(shù)加1，再將更新的粒子返回步驟4 重新計算粒子的適應(yīng)值； 若迭代次數(shù)達到設(shè)定值，則停止迭代，輸出PSO 算法中群體最優(yōu)位置Gb。

步驟6獲取最優(yōu)權(quán)值和閾值。將PSO 算法中群體最優(yōu)位置Gb賦值給BPNN 作初始權(quán)值和閾值。

步驟7計算誤差。將PSO 算法優(yōu)化過的初始權(quán)值和閾值的BPNN 對400 組樣本數(shù)據(jù)進行訓(xùn)練。選取BPNN 的輸出值與期望值之間的差值的平方和作為誤差函數(shù)。

步驟8判斷滿足條件。將誤差值與設(shè)定值比較，若誤差值沒有達到設(shè)定的精度，則采用誤差的反向傳播通道更新BPNN 的權(quán)值和閾值；若誤差值達到設(shè)定的精度則輸出BPNN 的輸出。

PSO-BPNN 的流程如圖2 所示。

圖2 PSO-BPNN 的流程Fig.2 PSO-BPNN flow chart

2.3.2 PSO-BPNN 時延預(yù)測的參數(shù)設(shè)置

在此，選取前2 個時刻時延數(shù)據(jù)來預(yù)測下一時刻的時延數(shù)據(jù)，即BPNN 輸入層神經(jīng)元數(shù)為2 個，輸出層神經(jīng)元數(shù)為1 個。文獻[11]表明，BPNN 隱含層個數(shù)為1 時可以對任意精度的函數(shù)進行逼近。故在此BPNN 選取單隱含層，隱含層神經(jīng)元的個數(shù)由進行選取，當(dāng)取a＝9 時，l＝10，即隱含層神經(jīng)元的個數(shù)為10。隱含層的神經(jīng)元函數(shù)選為“l(fā)ogsig”，輸出層神經(jīng)元函數(shù)選為“l(fā)ogsig”。BPNN 的最大訓(xùn)練次數(shù)設(shè)為1000，誤差精度為0.01，學(xué)習(xí)速率為0.5。

PSO 算法中粒子的維數(shù)根據(jù)BPNN 的連接權(quán)值和閾值的個數(shù)來確定。在此，粒子的維數(shù)取N＝41；學(xué)習(xí)因子c1為粒子對“自身”的認(rèn)知，學(xué)習(xí)因子c2為粒子對“社會”的認(rèn)知，且c1＝c2＝1.49；將PSO 算法中粒子的位置和速度限制在［-0.5，0.5］范圍。慣性權(quán)重ω 為PSO 算法中粒子繼承上一代粒子速度的能力。慣性權(quán)重的大小影響著PSO 算法的全局搜索能力和局部搜索能力。為了平衡全局搜索能力和局部搜索能力，采用式（4）對慣性權(quán)重進行線性遞減：

式中：ωstart為初始慣性權(quán)重；ωend為迭代至最大次數(shù)時的慣性權(quán)重；Tmax為最大允許迭代次數(shù)；k 為當(dāng)前迭代次數(shù)。初始慣性權(quán)重ωstart取較大值可以提高PSO 算法的全局搜索能力，隨著迭代次數(shù)的增加，粒子位置越來越靠近最優(yōu)值時將ωend取較小值可以提高PSO 算法的局部搜素能力。故在此取ωstart＝0.9，ωend＝0.4[12]。

3 仿真分析

3.1 BPNN 的仿真

將500 組時延數(shù)據(jù)分為2 組，取400 組時延數(shù)據(jù)作為BPNN 的訓(xùn)練樣本，100 組時延數(shù)據(jù)作為BPNN 的測試樣本。用BPNN 對400 組訓(xùn)練樣本進行訓(xùn)練，若達到誤差精度要求則用訓(xùn)練后的BPNN對100 組測試樣本進行測試，若測試結(jié)果也滿足誤差精度要求，則用此BPNN 對500 組時延數(shù)據(jù)進行預(yù)測。若不滿足誤差精度要求則返回繼續(xù)訓(xùn)練。BPNN 對500 組時延數(shù)據(jù)進行預(yù)測的結(jié)果如圖3 所示，BPNN 對樣本進行訓(xùn)練時訓(xùn)練次數(shù)與誤差的關(guān)系曲線如圖4 所示。

圖3 BPNN 對時延的預(yù)測Fig.3 Delay prediction by BPNN

圖4 BPNN 訓(xùn)練迭代次數(shù)與誤差的關(guān)系Fig.4 Relationship between training iterations and errors of BPNN

3.2 PSO-BPNN 的仿真

用PSO 優(yōu)化后的BPNN 對網(wǎng)絡(luò)時延進行預(yù)測，先取測試樣本誤差平方和為粒子群的適應(yīng)值函數(shù)，用粒子群算法優(yōu)化求得全局粒子最優(yōu)的位置即為BPNN 的初始權(quán)值和閾值。再用BPNN 對樣本數(shù)據(jù)進行訓(xùn)練，用訓(xùn)練完的BPNN 對500 組數(shù)據(jù)樣本進行預(yù)測。PSO-BPNN 對500 組時延數(shù)據(jù)進行預(yù)測的結(jié)果如圖5 所示，PSO-BPNN 對樣本進行訓(xùn)練時訓(xùn)練次數(shù)與誤差的關(guān)系曲線如圖6 所示。

圖5 PSO-BPNN 對時延的預(yù)測Fig.5 Delay prediction by PSO-BPNN

圖6 PSO-BPNN 訓(xùn)練迭代次數(shù)與誤差的關(guān)系Fig.6 Relationship between training iterations and errors of PSO-BPNN

3.3 數(shù)據(jù)的分析對比

為了更直觀地表示BPNN 和PSO-BPNN 的訓(xùn)練過程中誤差與迭代次數(shù)的關(guān)系，圖4 和圖6 中縱坐標(biāo)誤差分別取數(shù)據(jù)歸一化后BPNN，PSO-BPNN的輸出值與歸一化后的期望輸出值差值的絕對值。

對BPNN 時延預(yù)測和PSO 優(yōu)化初始權(quán)值，與閾值后的BPNN 時延預(yù)測的數(shù)據(jù)進行對比分析，結(jié)果見表1。

表1 BPNN 與PSO-BPNN 仿真數(shù)據(jù)比較Tab.1 Comparison of BPNN and PSO-BPNN simulation data

由表1 中第1 次迭代誤差的比較，結(jié)合圖4 與圖6，可知利用BPNN 對網(wǎng)絡(luò)時延進行預(yù)測時，初次迭代誤差較大，且算法易陷入局部極小值； 利用PSO 對BPNN 的初始權(quán)值與閾值進行優(yōu)化后的BPNN，對網(wǎng)絡(luò)時延進行預(yù)測時，第1 次迭代誤差得到了減小，同時避免了算法陷入局部極小值。

由表1 中迭代次數(shù)的比較可知，利用BPNN 進行訓(xùn)練，權(quán)值和閾值是隨機選取的，網(wǎng)絡(luò)訓(xùn)練了543次后才達到設(shè)定的誤差精度；利用PSO 優(yōu)化后的權(quán)值與閾值的BPNN，只需要訓(xùn)練197 次就能達到設(shè)定的誤差精度。說明利用PSO 優(yōu)化后的權(quán)值與閾值的BPNN，比利用隨機選取的權(quán)值和閾值的BPNN，在達到相同的設(shè)定誤差精度時迭代次數(shù)少，收斂性好。

由表1 中預(yù)測值與實際值最大相對誤差的比較中可知，PSO 優(yōu)化的BPNN 對500 組網(wǎng)絡(luò)時延數(shù)據(jù)樣本的預(yù)測，最大相對誤差為2.44%，比未優(yōu)化初始權(quán)值和閾值的BPNN 對500 組網(wǎng)絡(luò)時延數(shù)據(jù)樣本的預(yù)測，最大相對誤差8.13%要小。說明PSO 優(yōu)化的BPNN 對網(wǎng)絡(luò)時延預(yù)測的精度要好。

4 結(jié)語

為更好地對NCS 隨機時延進行預(yù)測，采用了PSO-BPNN 算法對時延進行預(yù)測。針對BPNN 算法在時延預(yù)測中的缺點，在對粒子群算法和BPNN 的理論分析基礎(chǔ)上，提出將PSO 算法與BPNN 相結(jié)合。利用PSO 算法強大的全局搜索能力，對BPNN的連接權(quán)值和閾值初始值進行優(yōu)化，加快了BPNN的收斂速度，提高了BPNN 的訓(xùn)練效率，同時也避免了BPNN 陷入局部極小值得可能。利用PSOBPNN 算法能夠很好地預(yù)測網(wǎng)絡(luò)控制時延，算法迭代次數(shù)少，精度更好。