基于ＰＩＤ神經元網絡和內模控制的擁塞控制算法

(1.南京理工大學 自動化學院， 南京 210094；2.南京人口管理干部學院， 南京 210042)

摘 要：針對網絡系統的大時滯和非線性特性，設計了一種新的擁塞控制算法，將PID神經元網絡與內模控制相結合應用于主動隊列管理中，并使用Lyapunov理論證明了此算法的穩定性。NS仿真結果表明，這種算法的穩態和瞬態性能都優于PID算法，并且在參數變化和負載擾動時具有很強的魯棒性。

關鍵詞：網絡擁塞控制; 主動隊列管理; PID神經元網絡; 內模控制

中圖分類號：TP393文獻標志碼：A

文章編號：1001-3695(2009)04-1443-03

Congestion control algorithm based on

PID neural network and internal model control

HOU Ping1，2，WANG Zhi-quan1

(1.School of Automation， Nanjing University of Science Technology， Nanjing 210094， China;2.Nanjing College for Population Program Management， Nanjing 210042， China）

Abstract:This paper designed a new congestion control algorithm for large delay and nonlinear network systems.Applied proportional integral differential (PID) neural network controller and internal model control(IMC) in active queue management(AQM).Proved stability by Lyapunov theory. The simulation results show that this algorithm’s stability and transient performance are superior to PID algorithm. Moreover it possesses high robustness even when system parameter changes or network load fluctuates.

Key words:network congestion control; AQM(active queue management); PID neural network; IMC(internal model control)

從控制理論的角度看，網絡的擁塞控制算法可以被看做是一個復雜的動態、非線性、時滯的反饋系統。主動隊列管理AQM（active queue management）機制是在路由器中間節點實現的擁塞控制。許多AQM算法[1~10]已經被提出來，然而已有的許多算法都是基于確定的線性化的TCP模型[11，12]，只在平衡點附近有效，由于TCP模型固有的非線性及Internet固有的動態本質，使得這些算法與動態的環境不相適應。同時上述AQM算法沒有充分考慮網絡延時對算法性能的影響，在提出這些算法的文獻中也沒有驗證它們在大延時網絡中的性能。文獻[13]通過仿真實驗證實了已有的幾種典型算法控制的隊列在大時滯網絡中無一例外地出現了劇烈的振蕩，導致瓶頸鏈路利用率下降和延時抖動加劇，并在進行適當模型擬合處理的基礎上應用控制理論的內模補償原理設計了魯棒的延時補償主動隊列管理算法。但是這種算法仍然是針對固定模型的，具有一定的局限性。

1990年，Bhat和McAroy[14]將神經網絡模型引入內模控制結構中，從而提出了一種非線性內模控制算法(NIMC)。基于神經網絡的內模控制主要應用于對非線性對象、時滯對象以及難建模對象等的控制。PID神經元網絡(PID nural network，PIDNN)是一種新的動態網絡結構[13]。它將PID控制規律融入神經網絡之中，實現了兩者的本質結合，既具有PID控制的優點，又克服了一般神經網絡的缺點。本文將PID神經元網絡引入內模控制中，提出一種新算法PID神經元網絡內模控制（PID neural network-internal model control，PIDNN-IMC）應用于主動隊列管理中。利用PID神經元網絡的動態特性充分逼近被控對象，內模控制結構能夠補償大時延的影響，仿真證明該算法具有很好的魯棒性。



1 PID神經元網絡結構

PIDNN是一種具有固定結構的三層前向神經網絡，其結構如圖1所示。網絡的輸入層有兩個神經元，分別接收系統的目標值和被控變量值。隱含層有三個神經元，各神經元的輸出函數互不相同，分別對應比例(P)、積分(I)、微分(D)三個部分。網絡的輸出層完成PIDNN控制規律的綜合，得到系統的輸出。網絡權重的修改使用反傳學習算法，同時完成學習和記憶功能。

輸入層神經元的輸入u(k)=[u1(k)，u2(k)]，其輸出與輸入相等。隱層第j個神經元的輸入為

xj(k)=2i=1wijui(k)；j=1，2，3(1)

式中：wij為輸入層i個節點至隱層第j個節點的權值。隱層神經元的輸出sj(k)(j=1，2，3)采用如下比例、積分、微分的計算規則：

a）比例

s1(k)=x1(k) -1≤x1(k)≤1

1x1(k)>1

-1x1(k)<-1(2)

b)積分

s2(k)=x2(k)+s2(k-1) -1≤s2(k)≤1

1s2(k)>1

-1s2(k)<-1(3)

c)微分

s3(k)=x3(k)-x3(k-1) -1≤s3(k)≤1

1s3(k)>1

-1s3(k)<-1(4)

輸出層神經元的輸入是隱層各節點輸出的加權和

x′(k)=3j=1w′jsj(k)(5)

式中：w′j為隱層節點j至輸出節點權值。

輸出層神經元輸出（即網絡的輸出）為

y(k)=x′(k) -1≤x′(k)≤1

1x′(k)>1

-1x′(k)<-1(6)

PIDNN是一種多層前向神經網絡[15，16]，其形式與一般多層前向網絡類似，但又有所不同，主要不同之處在隱含層。一般多層前向神經網絡中的全部神經元的輸入/輸出特性都是相同的和靜態的；而PIDNN的隱含層神經元分別對應比例、積分和微分函數，既有靜態的，又有動態的。同時，PIDNN的各層神經元個數、連接方式、連接權重初值是按PID控制規律的基本原則確定的，這決定了其結構比較簡單和規范。更重要的是，可以利用現有PID控制的大量經驗數據確定網絡權重初值，從而使控制系統保持初始穩定，使系統的全局穩定成為可能。

2 PIDNN-IMC算法設計

2.1 PIDNN-IMC應用于AQM

基于PIDNN內模控制[17]的AQM系統結構如圖2所示。

圖中PIDNNM為系統的內部模型，而PIDNNC為內模控制器。其中系統的輸入q0為參考的隊列長度；p為PIDNNC輸出的控制信號，代表丟包概率；q為被控對象的實際輸出，代表隊列長度；e1為過程輸出與模型輸出之差；e2為輸入與實際輸出之差。在運行過程中，PIDNNM利用PIDNNC的輸出和被控對象的實際輸出在線辨識對象模型，并通過模型偏差e1修正網絡權值，使之逐步適應被辨識對象的特性。PIDNNC的輸入為設定輸入和模型偏差e1，它的權系數利用系統偏差e2以及由PIDNNM通道反饋信號的梯度信息來實時調整，實現對被控過程的自適應控制[17]。PIDNNC和PIDNNM的學習算法與PIDNN相同。PIDNN的前向算法根據網絡的兩個輸入值，按網絡當前權重值和各層狀態函數和輸出函數形成網絡的輸出。PIDNN的反傳算法與傳統多層前向神經元網絡的算法類似。

2.2 學習算法

以PIDNNC為例給出學習算法，與PIDNNM的類似。PIDNNC訓練和學習的目的是使網絡實際輸出和理想輸出的對應時間序列的偏差平方均值最小為訓練和學習的目標。

E=1/2［q0(k)-q(k)］2(7)

按梯度算法調節PIDNN權重值，經k步訓練和學習后，PIDNN各層權重值的迭代方程為

W(k+1)=W(k)-ηE/W(8)

式中η為學習步長。

隱含層至輸出層的權重值w′j和輸入層至隱含層的權重值wij的具體算法分別由以下各式確定。隱含層至輸出層的權重迭代公式為

w′j(k+1)=w′j(k)-ηjE/w′j(9)

式中:

E/w′j=E/q×q/p×p/w′j(10)

對于q/p項，由于對象是未知的，這一項也是未知的，不能直接求解。用符號函數：

sgn [q(k+1)-q(k)]/[p(k)-p(k-1)](11)

近似代替。這種代替在算法上是許可的，因為q/p是權重值變化量乘積式(5)中的一個公共因子，它的符號正負決定著權重值變化的方向，而其數值的大小只影響權重值變化的速度。仿真結果表明，這種代替是行之有效的。輸出層的輸入/輸出相等，因此：

p/x′=1(12)

將式(5)(7)(11)(12)代入式(10)中，可得

E/w′j=-［q0(k)-q(k)］sgn [q(k+1)-q(k)]/[p(k)-p(k-1)]si(k)=-δ′(k)si(k)(13)

再將式(13)代入(9)，得

w′j(k+1)=w′j(k)+ηje(k)sgn [q(k+1)-q(k)]/[p(k)-p(k-1)]si(k)=

w′j(k)+ηjδ′(k)si(k)(14)

式中：

δ′(k)=［q0(k)-q(k)］sgn [q(k+1)-q(k)]/[p(k)-p(k-1)](15)

經過k步訓練后，輸入層至隱含層的權重迭代公式為

wij(k+1)=wij(n0)-ηijE／wij(16)

E/wij=E/q×q/p×p/wij=-［q0(k)-q(k)］sgn [q(k+1)-q(k)]/[p(k)-p(k-1)]p/wij=-δ′(k)p/wij(17)

式中：

p/wij=p/x′x′/sjsj/xjxj/wij=x′/sjsj/xjri(18)

式中r1=q0，r2=q，

x′/sj=/sjjwjsj=wj(19)

sj/xj用sj和xj相對變化量的符號函數近似代替：

sgn [sj(k)-sj(k-1)]/[xj(k)-xj(k-1)](20)

將式(17)～ (20)代入(16)得

wij(k+1)=wij(k)+ηijδj(k)ri(k)(21)

式中：δj(k)=δ′(k)w′jsgn [sj(k)-sj(k-1)]/[xj(k)-xj(k-1)]。

2.2 PIDNN的連接權重初值選取

一般神經元網絡連接權重初值多被取為隨機數，存在陷入局部極小值的可能，使控制性能難以達到預期的效果；特別是由于連接權重值的隨機性，很難保證控制系統初始運行的穩定性。如果控制系統初始運行不穩定，就失去了應用的基礎。PIDNN的連接權重初值按PID控制規律的基本原則確定[16]，在此初值的基礎上進行網絡的訓練、學習和調整，使網絡的收斂速度很快且不易陷入局部極小點。更重要的是，可以利用現有PID控制的大量經驗數據確定網絡權重初值，從而使控制系統保持初始穩定，使系統的全局穩定成為可能。

為使PIDNN連接權重初值時的輸出等價于PID控制器的輸出，選取其輸入層至隱含層連接權重初值為

w1j=1，w2j=-1

隱含層至輸出層連接權重初值為

w′1=Kp，w′2=Ki，w′3=Kd

3 PIDNN-IMC算法穩定性分析

采用PIDNN-IMC算法，如果控制參數選擇合適就可以保證該控制算法的收斂性。由于在此算法中，被控對象辨識器和控制器都是由PID神經元網絡描述的，只要保證各個PID神經元網絡的收斂性，就可以保證整個控制算法的收斂性。下面就從梯度下降迭代理論和非線性函數逼近理論來分析該算法的收斂性，并得到其收斂的條件。

定理 如果一個PIDNN控制系統的輸入為r，且學習步長η滿足0<η<1/ε2。式中 ε=e(n0)/W，則PIDNN學習k步后的權重值調整算法W(k+1)=W(k)-ηE/W保證PIDNN控制系統在學習過程中收斂。式中W表示PIDNN的連接權重值wij和w′j，E=1/2(γ(k)-y(k))2。

證明 定義李亞普諾夫函數

L(k)=1/2e2(k)(22)

式中:

e(k)=1/2［r(k)-y(k)］2=E

E為網絡學習的目標函數。因為：

ΔL(k)=L(k+1)-L(k)=1/2［e2(k+1)-e2(k)］

e(k+1)=e(k)+Δe(k)，Δe(k)=e(k)/W×ΔW

式中ΔW為網絡權重變化量。

ΔW=-ηE/W=-η /W［e2(k)］=-2η e(k) e(k)/W=-2η e(k)/W(E)

ΔL(k)=L(k+1)-L(k)=1/2［e2(k+1)-e2(k)］=

2η［e(k)e(k)/W］2［η(e(k)/W)2-1］

因此，當ηηe(k)/W2-1<0時，ΔL(k)<0，可以保證系統的收斂性。解以上不等式，并考慮η>0，可得0<η<1/［(e(k)/W)2］。所以只要PIDNN反傳學習算法的學習步長滿足一定條件，就可以保證PIDNN控制系統是收斂的。

4 算法性能評價與仿真

下面利用網絡仿真軟件NS2進行仿真，驗證PIDNN-IMC算法的性能。模擬網絡拓撲結構如圖3所示。si(i=1～n)為TCP應用發送端；sd為UDP應用發送端；節點nn1與nn2為瓶頸鏈路。隊長期望值qref=200 packet，經整定得到PID控制器的初始參數kp=4.75×10-5， ki=1.74×10-5，kd=8.37×10-6。采樣時間T=0.033 s。

實驗1 考察大時滯對算法的影響。圖3中由TCP連接承載FTP業務模擬網絡負載，數據源為60個FTP產生的數據流，包大小為500 Byte，瓶頸鏈路帶寬C為15 Mbps，任意兩節點之間的傳播延時均為50 ms，則總的RTT至少為400 ms。連接節點緩沖區空間均為500個包。瓶頸鏈路采用PIDNN-IMC控制策略，其他鏈路隊列管理算法均采用DropTail算法。實驗仿真結果如圖4所示。

從圖4可以看出，在大時滯情況下，PID算法瞬時隊列曲線出現了振蕩和抖動，最初幾秒內鏈路利用為空，丟包率較高。相比之下， PIDNN-IMC算法在長時滯情況下具有較好的控制效果。

實驗2 考察網絡參數配置發生變化對算法的影響。保持鏈路帶寬C和RTT不變，僅改變連接數N。在實驗開始時，有60個FTP源發送數據；在80 s時，有12個新的FTP源開始發送數據，180 s時，這12個FTP源停止發送數據。仿真結果如圖5所示。保持C、N和RTT不變，加入一個UDP/CBR源作為噪聲干擾，每個CBR包的大小為1 000 Byte，其發送帶寬為1.5 MB，在80 s時開始發送數據，在180 s時停止發送數據。仿真結果如圖6所示。

由圖5～6可以看出，在網絡參數發生變化的情況下，PIDNN-IMC算法體現了較強的抗干擾能力，超調量小，振蕩輕微，快速收斂于隊列長度期望值，同時具有較大的鏈路利用率。

5 結束語

本文針對長時滯和網絡動態變化，提出一種大時滯網絡自適應主動隊列管理新算法，將PID神經元網絡融入內模控制中。所選用的PID神經元網絡克服了一般神經網絡的缺點。 NS2仿真表明，該算法在大時滯的情況下具有很好的控制性能；在網絡環境變化的情況下，能快速穩定地適應動態網絡環境，收斂于期望隊列長度，具有穩定性和魯棒性。該算法適合復雜網絡環境的在線實時控制。

參考文獻：

［1］

ATHURALIYA S，LOW S H，LI V H，et al.REM:active queue management[J].IEEE Network Mag， 2001，15（3）:48-53.

［2］FENG Wu-chang，SHIN K G，KANDLUR D D，et al.The blue queue management algorithms[J].IEEE/ACM Trans on Networking，2002，10（4）:513-528.

［3］FLOYD S，GUMMADI R，SHENKER S.Adaptive RED:an algorithm for increasing the robustness of RED’s active queue management[EB/OL].(2001).http://www.icir.org/.oyd/red.html.

［4］HOLLOT C V，MISRA V，TOWSLEY D，et al.On designing improved controllers for AQM routers supporting TCP flows[C]//Proc of IEEE INFOCOM.2001:1726-1734.

［5］KUNNIYUR S S，SRIKANT R.An adaptive virtual queue (AVQ) algorithm for active queue management[J].IEEE/ACM Trans on Networking，2004，12(2):286-299.

［6］REN Feng-yuan，LIN Chuang，WEI Bo.A robust active queue management algorithm in large delay networks[J].Computer Communications，2005，28(5):485-493.

［7］SUN Jin-sheng，CHEN Guang-rong，KO K T，et al.PD-Controller:a new active queue management scheme[C]//Proc of IEEE Globecom.2003:3103-3107.

［8］SUN Jin-sheng，KO K T，CHEN Guang-rong，et al.PD-RED:to improve the performance of RED[J].IEEE Communications Letters，2003，7（8）:406-408.

［9］WYDROWSKI B，ZUKERMAN M.GREEN:an active queue management algorithm for a self managed Internet[C]//Proc of ICC.2002:2368-2372.

［10］WANG Chong-gang，LI Bo，HOU Y T，et al.A stable rate-based algorithm for active queue management[J].Computer Communications，2005，28(15):1731-1740.

［11］MISRA V，GONG W B，TOWSLEY D.Fluid-based analysis of a network of AQM routers supporting TCP flows with an application to RED[C]//Proc of ACM/SIGCOMM.Stockholm:ACM Press，2000:386-399.

［12］HOLLOT C V，MISRA V，TOWSLEY D，et al.A control theoretic analysis of RED[C]//Proc of IEEE INFOCOM.2001.

［13］任豐原，林闖，任勇，等.大時滯網絡中的擁塞控制算法[J].軟件學報，2003，14(3):503-511.

［14］BHAT N，McAVOY T.Use of neural nets for dynamic modeling and control of chemical process systems[J].Computers and Chemical Engineering，1990，14(4/5):573-583.

［15］任雪梅，黃鴻，艾亮，等.主動隊列管理的PID型神經網絡控制[J].北京理工大學學報，2006，26（10）：892-896.

［16］舒懷林.PID神經元網絡及其控制系統[M].北京：國防工業出版社，2006.

［17］沈永俊，顧幸生.PID神經網絡內模控制在濕法煙氣脫硫中的應用[J].清華大學學報：自然科學版，2007，47(S2):1798-1802.