無線網絡中基于強化學習的擁塞控制算法改進

(西南科技大學信息工程學院，四川 綿陽 621010)

0 引言

TCP協議以其可靠性、端到端、定向的傳輸服務被廣泛應用于各種網絡。它主要包括慢啟動、擁塞避免、快速恢復和擁塞處理4個階段[1]。TCP采用擁塞窗口(cwnd)來解決網絡中的擁塞，以上4個階段根據不同的環境狀態改變cwnd值，以適應網絡。雖然現有TCP協議應用廣泛，但對于鏈路帶寬不對稱、節點運動不規則的無線網絡而言，其在擁塞判斷和決策處理上容易使網絡出現擁塞、傳播延遲過大等情況。主要原因是擁塞判斷方式單一以及不合理的cwnd變化方式。擁塞判斷方式單一指TCP在擁塞避免和快速恢復階段分別采用往返時延(round-trip time,RTT)和重復確認(acknowledgement,ACK)決定cwnd值增長和判斷擁塞狀態，這種方式在無線網絡下易出現不能正確判斷丟包或擁塞的現象。因cwnd值表征此時網絡節點可以傳輸的數據包大小，不合理的cwnd變化方式易使網絡在不必要的時候減少網絡吞吐量。

1 算法描述

針對TCP擁塞控制，文獻[2]對往返時延進行壓擴，動態改變加性因子大小。文獻[3]根據前向鏈路的轉發跳數對TCP擁塞窗口增長速率進行控制。文獻[4]采用一種類似學習的TCP思想，對網絡狀態進行學習，反饋動作作用后結果，智能選擇加性因子大小。文獻[2]～[4]都忽略了擁塞控制協議中乘性因子對網絡擁塞產生的影響。文獻[5]對近年來多種AIMD擁塞控制算法進行對比和分析，結果表明，針對無線網絡而言，99%的丟包來自于擁塞。文獻[6]在高速網絡應用下給出了一種學習擁塞控制算法，有效提升了TCP協議在快速網絡下的性能，但該算法須對接收端、發送端以及路由進行改進，實施性不強。

到目前為止，解決現有TCP擁塞控制協議在無線網絡中出現的性能問題受到業界的廣泛關注。為使TCP在無線網絡下擁有更好的性能，本文提出一種基于AIMD的網絡動態學習算法,即NewReno-RF。通過進一步學習網絡帶寬表征量，動態設計cwnd值的變化方式。同時考慮協議自動感知環境和強化決策控制協同作用在整體擁塞控制中的改進對網絡性能的影響。

NewReno-RF算法整體思想如圖1所示。算法通過AI加法因子和MD乘法因子兩部分中的cwnd進行動態調整。

圖1 NewReno-RF算法整體思想框圖

1.1 AI加法因子策略

對于無線網絡而言，往返時延(RTT)值隨著網絡不斷更新。當RTT值較小時，網絡帶寬充裕，可以承載更多數據量；當RTT值增大時，網絡負載增大。此時，AI協議應采取更為有效的擁塞避免措施，使網絡帶寬利用率最大。因此，本文在AI階段對RTT作進一步判斷，動態決定加性因子大小。

1.1.1 RTT量化

本文對RTT進行進一步量化，將區間[RTTmin,RTTmax]均勻量化為M個區間。量化間隔如式(1)所示。

Δv=(RTTmax-RTTmin)/M

(1)

當mi-1≤RTT≤mi時，量化器輸出m=i(i=1,2,…，M)，其中mi=RTTmin+Δv×i。對任意RTT，相應的輸出m作為加性因子選取的判斷條件。

1.1.2cwnd加性因子選取

本文對加性因子x選取采用如下函數關系。

(2)

式中：m為RTT量化值；T為m的量度；α為滾降因子，范圍為[0，1]。

函數將根據m的大小輸出不同比例的加法因子，使cwnd的增長適應網絡變化。函數可根據網絡的不同需求，改變α滾降因子的值來得到不同特性的加性因子。

1.2 MD乘法因子策略

對于網絡傳輸而言，怎樣充分利用帶寬傳輸數據是本文需解決的難題。TCP僅依靠重復ACK來判斷擁塞，單一對cwnd值減半的做法不能充分地利用網絡帶寬。本文將MD階段視為一個有限狀態的離散馬爾科夫決策過程(MDP)，利用強化學習策略，對無線信道帶寬作進一步學習，動態改變cwnd乘性因子，最終達到充分利用帶寬、提高網絡性能的目的。

強化學習把學習看作是一種“試探—評價”的過程。首先學習系統(稱為智能體)感知環境狀態，采取某一個動作作用于環境，環境接受該動作后狀態發生變化，同時給出一個回報反饋。強化學習系統根據強化信號和環境的當前狀態再選擇下一個動作，選擇的原則是使折扣期望回報最大。本文采用強化學習中的Q學習算法，它是一種與模型無關的強化學習算法[6]。

1.2.1 狀態和動作值描述

Q學習算法中狀態值和動作值的選取須結合MD階段特性。網絡中節點變動、信道變化時刻會觸發系統狀態的改變。因此，本文將MD階段的cwndmax(即當前時段內cwnd峰值)作為Q學習模型狀態(s)值。

學習策略是一個在當前狀態(s)下從可能的動作集中隨機選擇動作，即故意執行一種目前不是最優的動作來獲得關于那些未知狀態的知識[7]。當建立了足夠多的樣本值之后，系統將利用Q值來選擇當前狀態的下一最優動作值。為確保探索的有效性，本文結合現有系統的乘法因子特性，采用與之相近的隨機值，以求找到系統動作最優解。

1.2.2 回報值的設計

本文將cwndmax歸一化為R(0,1)，衡量某一動作在該狀態下的性能好壞。轉換關系如式(3)、式(4)所示。

(3)

(4)

式中：BM為當前系統認為表現較好的cwndmax的均值，即滿足當前AIMD階段持續時間與之平均持續時間差值εt和實時cwndmax與平均cwndmax的差值εcm在一定范圍內的cwndmax；cw為實時cwndmax。

為使R歸一化為(0,1)，δ取固定值-2。當cw越接近BM，R越接近于1，當前動作對當前狀態的影響越大；當cw相對BM越小，則R越接近于0。

1.2.3Q學習算法

Q學習算法的基本形式為Q*(s,a)，表明在狀態s下執行動作a所得到的最優獎賞值的和，如式(5)所示。

(5)

式中：T(st,at,st+1)為學習系統在時間步t時由于采取行動at，而使環境從狀態st轉移到狀態st+1的轉移概率。

最優策略π*(s,a)，即在狀態s下執行動作a使得：

(6)

Q學習可直接優化一個迭代公式(7)來獲得最優策略。更新系統Q值表，選取下一狀態的最優動作解。

(7)

式中：Q(st,at)為舊Q值；Rt+1為狀態st的下一狀態st+1所對應at回報值；αt(s,a)(0<α<1)為學習效率，若αt(s,a)衰減合適，即滿足條件∑∞n=0αnt(s,a)=∞,∑∞n=0[αnt(s,a)]2<∞，且所有狀態-動作對都能被無窮次訪問更新Q值，則Q值最終將依概率1收斂于Q*，其收斂性已得到證明[8]；0<γQ<1為折扣因子，γQ如取值較小，則表示Q學習策略更關注最近動作的影響，如取值大，則表示當前Q值要受系統較長時間狀態動作對的影響；maxQ(st+1,at+1)為狀態st的下一狀態st+1所對應動作at產生最大Q回報值。

在每一個離散的時間步t中，智能體感知當前狀態st，執行相應動作at，給出回報值Rt，并產生一個后繼狀態st+1。在無線網絡環境初始時，系統對于所有狀態的Q值和回報值都默認為0。因此，針對式(7)，Q值將變成0。為使系統不產生此種情況，本文在系統初始時，采用式(8)更新Q值。

(8)

式中：γR(0,1)為回報函數的折扣率，γR的取值表明當前回報值函數受前向回報的影響大小。

2 算法實現

根據上述分析，基于AIMD的TCP改進算法NewReno-RF的分析如下。

① 初始化系統中所需各固定參數。

② 重復步驟③～⑥。

③ 由式(1)得到m，由式(2)更新加法因子x，cwnd=cwnd+x。

④ 根據當前狀態執行的動作，由式(4)得到γ，Q(R)←γ；根據式(7)、式(8)更新Q值。

⑤ 選擇當前st中Q最大對應的at，執行此時乘法因子at。

⑥ 根據AIMD持續時間和cwndmax大小更新BM。

3 場景設置及結果分析

本文基于網絡模擬器(network simulator,NS)，實現改進算法NewReno-RF。其中量化區間M為16，滾降因子α=0.72，cwndmax選取差值范圍低于平均量的5%。為滿足收斂條件，本文設置學習效率αt(s,a)=0.2。系統建立足夠樣本之前，設置式(8)中回報函數折扣率γR=0.3,以使當前狀態受回報折扣影響較小。進入Q學習值迭代系統，即利用式(7)對MD階段進行優化，折扣因子γQ=0.95，充分考慮前向回報對系統的影響。本文討論所述協議在兩種網絡場景下的性能情況。為和現實試驗環境匹配，兩種場景都規定各節點的傳輸能耗。根據文獻[9]對NS2中能量模型和無線傳輸模型的說明，場景設置為室外自由空間。本文采用陰影無線傳輸模型，路徑損耗指數βs為2.0，陰影方差σdB為4.0。NS中實現的能量模型是一個節點的屬性，表示一個主機的能量水平[9]。本文中設置各個節點初始能量1 000 W，發送能量0.660 W，接收能量0.395 W以及天線增益5.5 dBi，高度1 m。

3.1 場景一

本文所述場景一為隨機Ad hoc網絡。本文對該場景進行N(N≥10)次仿真試驗，試驗場景中節點隨機分布。大體遵循以下規則：10個節點初始位置隨機分布，在場景大小為1 000 m×1 000 m內以最大10 m/s的速度隨機運動，仿真開始10 s即在n5和n4間建立TCP數據傳輸，直至結束。仿真結果在相應點取N次平均。在Ad hoc網絡下，改進NewReno-RF算法和NewReno協議在吞吐量、傳播延遲和重傳率方面的性能狀況如圖2所示。

圖2 Ad hoc網絡仿真結果

由圖2可以看出，由于Ad hoc網絡中節點運動的隨機性，協議在各時段表現不平穩。但總體而言，NewReno-RF在吞吐量上一直高于NewReno，平均提升了40%。傳播延遲和重傳率方面則總是低于NewReno，分別平均減少11%和27%。

3.2 場景二

場景二為在無線多跳鏈式網絡下對改進協議進行N(N≥10)次仿真試驗。鏈式網絡拓樸模型如圖3所示。試驗中，場景大小1 000 m×1 000 m，N次仿真試驗于n5和n4間建立TCP數據傳輸，開始時間在10 s內隨機分布。場景中節點初始位置略有不同，但節點運動曲線和速度基本一致。各節點保持不超過10 m/s的鏈式勻速運動，運動過程中兩節點間距離保持不變。仿真結果在相應點取10次平均，如圖4所示。

圖3 鏈式網絡拓撲模型

圖4 鏈式網絡仿真結果

由圖4可以看出，雖然NewReno-RF協議初始時由于對環境感知的不完全性，在吞吐量、傳播延遲、重傳率上都表現不穩定，但隨著學習次數的增多，NewReno-RF性能逐漸優于NewReno。重傳率呈現大幅降低的趨勢，平均降低34%；傳播延遲同比減少了17%；NewReno-RF吞吐量比NewReno平均提升53%。

4 結束語

隨著網絡的日益發展，現有TCP協議不足以滿足其復雜性、多樣性的需求。本文提出一種基于AIMD擁塞控制協議的改進算法，加入量化和強化學習理念，提高了TCP協議在網絡傳輸方面性能。通過和現有版本TCP-NewReno在兩種傳輸模型上進行多次仿真比較，結果表明，改進協議在傳播延遲、吞吐量、重傳率方面都有明顯提升。

[1] Ghassan A A,Mahamod I,Kasmiran J.Exploration and evaluation of traditional TCP congestion control techniques[J].Computer and Information Sciences,2012,24(2):145-155.

[2] 劉俊.擁塞窗口自適應的TCP擁塞避免算法[J].計算機應用,2011,31(6):1472-1475.

[3] 宋軍,李浩,李媛源,等.Ad Hoc中的TCP改進方案-Adaptive ADTCP[J].計算機應用,2010,30(7):1750-1756.

[4] Badarla V,Murthy C S R.Learning-TCP:A stochastic approach for efficient update in TCP congestion window in Ad Hoc wireless networks[J].Journal of Parallel and Distributied Computing,2011,71(6):863-878.

[5] Hiroki N,Nirwan A,Nei K.Wireless loss-tolerant congestion control protocol based on dynamic AIMD theory[J].IEEE Wireless Communications,2010,17(2):7-14.

[6] 褚建華.Q-Learning強化學習算法改進及其應用研究[D].北京:北京化工大學,2009.

[7] Kento T,Junichi M.A study on use of prior information for acceleration of reinforcement learning[C]∥SICE Annual Conference,2011:537-543.

[8] Nicholas M,Mihaela V S.Reinforcement learning for energy-efficient wireless communications[C]∥IEEE Transactions on Signal Processing,2011:6262-6266.

[9] NS2.The network simulator ns-2[EB/OL].[2010-10-25].http://www.isi.edu/nsnam/ns.

[10]Marek G,Daniel K.Online learning of shaping rewards in reinforcement learning[J].Neural Networks,2010,23:541-550.

[11]Maryam S.Knowledge ofopposite actions for reinforcement learning[J].Applied Soft Computing,2011(11):4097-4109.

[12]Nadim P,Anirban M,Carey W.An analytic throughput model for TCP NewReno[J].IEEE/ACM Transmission on Networking,2010,18(2):448-461.