迭代學習在網絡控制中的應用

（1. 北京交通大學電子信息工程學院， 北京 100044; 2.江蘇大學 計算機科學與通信工程學院， 江蘇 鎮江 212013）



摘 要：

針對網絡擁塞控制中網絡擁塞本身無法建立精確的數學模型的問題，基于迭代學習控制具有結構簡單及對系統精確模型不依賴等優點，首次提出了用迭代學習控制算法來解決網絡擁塞，其主要目的是提高網絡資源的利用率并提供給信源公平的資源分配份額。在提出算法前，首先通過分析網絡模型建立了網絡擁塞被控系統；然后提出了針對該被控系統的開閉環PID型迭代學習控制算法并證明了其收斂性；最后運用此算法建立了網絡擁塞控制模型。通過實驗和仿真表明，該算法對解決網絡擁塞問題有很好的效果。

關鍵詞：網絡擁塞； 迭代學習； 數學模型； 擁塞控制

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

文章編號：10013695(2008)12381003



Applying iterative learning to network control



LI Xingyi1，2， HUO Zhenqiang2， SHI Huaji2， WANG Yi1

（1. School of Electronics Information Engineering， Beijing Jiaotong University， Beijing 100044， China; 2. School of Computer Science Telecommunication Engineering， Jiangsu University， Zhenjiang Jiangsu 212013， China）



Abstract:With the goal of improving the network resource utilization rate and supplying an impartial resource ditribution quota for source， this paper proposed the solution of iterative learning control algorithm to the network congestion problem by making use of the merits of iterative learning control such as simple structure and independence of accurate system model. Prior to describing the algorithm， it constructed a controlled system for the network congestion by analyzing network model， and then gave the controlled system an openclosed loop PID type iterative learning control algorithm and proved its convergence， finally built a network congestion control model using the algorithm. Experiment and simulation prove that this algorithm takes a good effect in solving the network congestion problem.

Key words：network congestion; iterative learning; mathematical model； congestion control



0 引言

資源共享在充分利用了網絡資源的同時，也引發了網絡的擁塞問題。當網絡發生擁塞時，各項性能急劇下降，嚴重時會使網絡崩潰。在當今網絡的速度和規模不斷擴大的情況下，對擁塞的控制已變得越來越重要，并且面臨著新的挑戰。

由于傳統控制理論方法的應用在很大程度上依賴于結構已知的系統數學模型。 而這些數學模型往往受到許多嚴格限制，未能從根本上完全解決擁塞控制問題，因而實際應用中遇到了許多難以逾越的障礙， 導致網絡的性能仍未得到充分的提高或明顯的改善。 

針對上述網絡擁塞控制中存在的問題，首次提出用迭代學習控制來解決。迭代學習控制適合于一類具有重復運行特性的被控對象，其任務是尋找控制輸入，使得被控系統的實際輸出軌跡在有限時間區間上沿整個期望輸出軌跡實現零誤差的完全跟蹤，且整個控制過程要求快速完成。與現有的控制方式相比，迭代學習控制的特點是充分利用前幾次的控制信息構成當前的控制輸入信號，且不依賴被控系統的精確模型，由于其簡單有效其應用面也越來越廣^[1，2]。

1 問題提出

網絡擁塞控制系統的關鍵部分是控制算法，本文使用迭代學習控制算法。在使用迭代學習控制理論方法分析或設計網絡擁塞控制系統，首先應確立被控系統的粗略的數學模型。在圖1的參考模型中，假設每隔Ts，交換機發送信息給信源。對于每個VCs，存在兩種用T歸一化后的延遲: τ1i( i= 1， 2，…，N) ， 它們均是整數。τ1i表示從第i個信源到交換機的路徑延遲，也稱為前向延遲。第i個信源的受控流速率用ui(t)表示;用y(t)表示交換機緩沖區占有量(隊列長度) ，每隔T s經濾波器將其傳給受控信源，基于該信息，受控信源調節其ui(t)。這里假設速率調節器分布運行在每個信源節點(也可位于瓶頸交換機)。按照上述假設，網絡中交換機的動態性(被控系統)可用下面非線性離散時變帶有延時的方程描述。

x#8226;(t)=f(t，x(t-τ1i))+B(t)u(t)

y(t)=C(t)x(t)

（1）



式中： x(t)∈Rn×l，y(t)∈Rm×l，u(t)∈Rr×l分別為系統的狀態和輸出向量； t∈[0，T]， f， B， C為適當的維數的向量或矩陣。當系統是可重復多次運行的，要求在時間區間t∈[0， T]內系統輸出y(t)精確的跟蹤期望輸出yd(t)。第k次運行時，系統的迭代學習動態方程表示為

x#8226;k(t)=f(t，xk(t-τ1i))+B(t)uk(t)

yk(t)=C(t)xk(t)

（2）



網絡被控系統及其擁塞控制系統結構確定后，主要需解決的問題是速率控制器的確定以及選擇相應的最佳控制參數。在本文中速率調節器的分析和設計方法為基于智能控制理論方法，即迭代學習控制的開閉環PID型迭代學習控制算法。

2 開閉環PID型迭代學習控制律及其收斂性

針對上述被控系統，所提出的開閉環PID 型迭代學習控制律^[4]為

uk+1=uk(t)+Lp(t)ek(t)+Li(t)∫t0ek(ζ)dζ+Ld(t)e#8226;k(t)+

Lp(t)ek+1(t)+Li(t)∫t0ek+1(ζ)dζ+Ld(t)e#8226;k+1(t)

（3）



定理給定可達的期望軌跡yd(t)(t∈[0，T])。如果由式(1)(2)描述的非線性離散時變帶有延時的系統滿足條件：

a)f(t，x(t-τ1i))滿足Ｌｉｐｓｃｈｉｔｚ連續條件： ‖f(t，x1(t-τ1i))-f(t，x2(t-τ1i))‖≤M‖x1-x2‖，且 M＞0；

b)存在惟一的理想輸入ud(t)使系統的狀態和輸出值為xd(t)、yd(t)；

c）初始狀態序列{xk(0)}k≥1滿足limk→∞xk(0)=xd(0)，k=1，2，…；

d）ρ([I+Ld(t)C(t)B(t)]-1[I-Ld(t)C(t)B(t)])＜1， t∈[0， T];

e）f(t)、 B(t)、 C(t)、 t∈[0， T]均有界，則當k→∞時，系統迭代輸出yk(t)在[0，T]上一致收斂于期望軌跡yd(t)，即limk→∞yk(t)=yd(t)， t∈[0，T]。

證明 假設

δxk+1(t)=xd(t)-xk(t)

δyk+1(t)=yd(t)-yk(t)

δuk+1=ud(t)-uk(t)

，令f1(t，xi)=f(t，xd)-f(t，xd-xi)。由條件a）可得‖f(t，xi)‖≤M‖xi‖，Mi＞0且有界，則第ｋ次運行時有δxk(t)=xd(t)-xk(t)。

δx#8226;k(t)=x#8226;d(t)-x#8226;k(t)=f1(t，δxk(t))+B(t)δuk(t)

（４）

δyk(t)=C(t)δxk(t)

(5)



對式（５）求導得

δy#8226;k(t)=C#8226;(t)δxk(t)+C(t)δx#8226;k(t)

(6)

δuk+1(t)=ud(t)-uk+1(t)=δuk(t)-Lp(t)ek+1(t)+

Li(t)∫t0δyk(ζ)dζ-Ld(t)δy#8226;k(t)-Lp(t)δyk+1(t)-

Li(t)∫t0δyk+1(ζ)dζ-Ld(t)δy#8226;k+1(t)

（7）



將式(4) ～(6) 代入式(7)，若選取適當的Ld(t)，使得(I-Ld(t)C(t)B(t))可逆時，經過整理可得

δuk+1(t)=[I+Ld(t)C(t)B(t)]-1[I-Ld(t)C(t)B(t)]δuk(t)-

[I+Ld(t)C(t)B(t)]-1[Lp(t)C(t)δxk+1(t)+Ld(t)C#8226;(t)δxk+1(t)+

Ld(t)C(t)f1(t，δxk+1(t))]+Li(t)∫t0C(t)δxk+1(ζ)dζ-[I+

Ld(t)C(t)B(t)]-1[Lp(t)C(t)δxk(t)+Ld(t)C#8226;(t)δxk(t)+

Ld(t)C(t)f1(t，δxk(t))+Li(t)∫t0C(t)δxk(ζ)dζ]

（８）



根據積分中值定理，存在有界的ξi(t)，使‖∫t0δxk+1dζ‖≤‖ξi(t)‖‖δxk+1(t)‖成立。

對式（８）兩端去范數有

‖δuk+1(t)‖≤‖[I+Ld(t)C(t)B(t)]-1

[I-Ld(t)C(t)B(t)]‖×‖δuk(t)‖+∑l0bi‖δxk+1(t)‖

（９）



式中：

bi=supt∈[0，T]‖[I+Ld(t)C(t)B(t)]-1[Lp(t)C(t)+Ld(t)

C#8226;(t)+MiLd(t)C(t)+ξi(t)Li(t)C(t)]‖



下面給出δxk(t)的估計。由于xk(0)=xd(0)(k=1，2，…)，根據式（４）可得

‖δxk(t)‖=‖∫t0(t(t，xd(t))+B(t)uk(t))dα‖≤

∫t0(‖f(t，xd(t))-f(t，xk(t))‖+‖B(t)ud(t)-B(t)uk(t)‖)dα≤

∫t0(M‖δxk‖+bB‖δuk(t)‖)dα

（10）



式中： bB為B(t)的上界。應用BellmanGronwall 引理可得‖δxk(t)‖≤∫t0eMαbB‖δuk(t)‖dα。

將條件d）和式（１０）代入式（９），則



‖δuk+1(t)‖≤ρ‖δuk(t)‖+∑li=0γ∫t0eγ(t-α)‖δuk+1(t)‖dα



式中：γ=max{Mi， bibB}。兩端同時乘以函數e-λt(λ＞γ)，有

‖δuk+1‖λ≤ρ‖δuk(t)‖λ+γ（1-e(γ-λ)T）/（λ-γ）‖δuk+1(t)‖λ+

γ（1-e(γ-λ)T）/（λ-γ）‖δuk+1(t)‖λ

（11）



由式(11) 可得

‖δuk+1(t)‖λ≤ρ‖δuk(t)‖λ

（12）



式中：ρ=(ρ+（1-e(γ-λ)T）/（λ-γ)）/(1-γ(1-e(γ-λ)T)/（λ-γ）)。當選取足夠大的λ時，條件d) 蘊涵ρ＜1，因此可推知limk→∞‖δuk(t)‖λ=0。又因為

‖δxk(t)‖λ≤bB(1-e(γ-λ)T)/（λ-γ)‖δuk(t)‖λ， λ＜γ

(13)

‖ek‖λ=‖δyk‖λ=‖C(t)δx(t)‖λ≤C(t)‖‖δx(t)‖λ≤

bCbB(1-e(γ-λ)T)/（λ-γ)‖δuk(t)‖λ

(14)



式中： bC為C(t)上界。當λ>>γ時，由式（12）~（14）可推知limk→∞‖δek(t)‖λ=0，即limx→∞yk(t)=yd(t)，t∈[0，t]。

3 本文中提出的網絡擁塞控制模型

通過對圖1進行分析，可以得出：基于迭代學習控制算法的網絡擁塞控制可以在網絡協議的各個層次上實施。由于數據鏈路層靠近擁塞的發生點，在數據鏈路層進行控制可以快速地對擁塞作出反應；原來的擁塞控制只能解決短時間內的擁塞，但基于迭代學習控制算法的網絡擁塞控制很好地解決了這一點。由于缺乏分析工具來精確地描述不可預測的流量時變行為和統計波動。控制器根據以前所獲得經驗以適應新的情況是很重要的，而 迭代學習控制具有此功能。于是在高速網絡中，首次提出用迭代學習控制來解決擁塞問題。本文提出的擁塞控制是一種基于開閉環PID型迭代學習控制的調節算法， 它是一種非線性控制器且分布運行于每個交換機中，其模型如圖2所示。其收斂性已經在第2節中得到了證明，由此可以看出其可行性。

通過表1對比可以看出本文提出的擁塞控制雖然在某些方面存在不足，如有延遲，控制系統潛入到交換機中，增加了網絡模型的復雜性，但也可以看出其綜合性能優于其他兩種控制方式^[6~10]。

表1 TCP、IP擁塞控制與本文中的擁塞控制的比較

比較項TCP擁塞控制IP擁塞控制本文中的擁塞控制

實現位置端系統網絡內部交換機

延遲較大無較小

不同數據流間的公平性難以實現可以實現較好實現

長期擁塞可以處理無法處理可以處理

短期擁塞可以處理較好處理理想處理

由圖3所示的實驗結果可以看出，經過本文所提出的基于開閉環PID型迭代學習控制算法的擁塞控制后，其網絡流量得到了很好的控制，發生擁塞的次數較以前有了明顯減少，并提高了網絡資源的利用率和提供給信源公平的資源分配份額，說明本文所提出的網絡擁塞控制有很好的效果。

4 結束語

迭代學習控制由于其結構簡單和對系統精確模型的不依賴性使其在控制系統中得到了廣泛的應用。但開環迭代學習控制只利用了系統前次運行的信息，而忽略了系統當前的信息，使得系統對被控制對象無鎮定作用，閉環迭代學習控制往往又需要高增益反饋從而影響了系統迭代收斂速度。 本文提出了一種同時利用開閉環PID 型迭代學習控制律，并證明了其收斂性。將這一方法應用于網絡擁塞控制中，其主要目標是控制進入網絡的數據流量，保證通信網絡不會被用戶發送的數據流阻塞，并合理地使用瓶頸資源，克服了傳統控制方法的許多局限，取得了較好的效果。 

參考文獻：[1]XU Jianxin， TAN Ying. Linear and nonlinear iterative learning control[C]//Proc of Lecture Notes in Control and Information Sciences.[S.l.]: SpringerVerlag， 2003.

[2]XU Jianxin， TAN Ying. On the convergence speed of a class of higher order ILC schemes[C]//Proc of the 40th IEEE Conference on Decision and Control Orlando. Florida:[s.n.]， 2001:49324937.

[3]CHEN W， SAIF M. Avariable structure controller for a class of uncertain systems with unknown uncertainty bounding function[C]//Proc of American Control Conference. 2006. 

[4]ZHENG K， LEE A H， BENTSMAN J， et al. Steadystate bumpless transfer under controller uncertainty using the state/output feedback topology[J].IEEE Trans on Control Systems Technology，2006，14(1):317. 

[5]MACRI P A， PIONTTI A L P， BRAUNSTEIN L A. Reducingcongestionon complexnetworksby dynamic relaxation processes[J]. Physical A: Statistical Mechanics and its Applications， 2007，386(2):776779.

[6]CEHN Hualiang， LIU Zhongxin， CHEN Zengqiang， et al. Extending TCPcongestioncontrol to multicast[J]. Computer Networks， 2007，51(11):30903109.

[7]JIN C， WEI D， LOW S H， et al. FAST TCP: from theory to experiments [J]. IEEE Network， 2005，19(1):411.

[8]TAN Liansheng， YUAN Cao， ZUKERMAN M. FAST TCP: fairness and queuing issues[J].IEEE Communications Letters， 2005，9(8):762764.

[9]CASETTI C， GERLA M， MASCOLO S， et al.TCP westwood: endtoend congestion control for wired/ wireless networks[J]. Wireless Networks. 2002，8(5):467479.

[10]GRIECO L A， MASCOLO S. Endtoend bandwidth estimation for congestion control in packet networks[C]//Proc of Lecture Notes in Computer Science on Quality of Service in Multiservice IP Networks. London: SpringerVerlag，2003.