基于SARSA學(xué)習(xí)算法的USB塊傳輸研究*

張秋云，江 虹

(西南科技大學(xué)信息工程學(xué)院，四川 綿陽(yáng) 621010)

USB總線上的數(shù)據(jù)傳輸分為同步、中斷、控制、塊傳輸?shù)人姆N類型[1]，不同設(shè)備采用的傳輸方式不盡相同，在有限的帶寬資源下如何協(xié)調(diào)數(shù)據(jù)傳輸對(duì)實(shí)現(xiàn)USB高效傳輸非常重要。目前僅文獻(xiàn)[2]針對(duì)同步傳輸?shù)脑O(shè)備設(shè)計(jì)并實(shí)現(xiàn)了一種實(shí)時(shí)的USB驅(qū)動(dòng)，使設(shè)備獲得了可靠的QoS保證，同時(shí)也提高了USB帶寬利用率，但對(duì)于其他方式的傳輸尚未進(jìn)行研究。大容量存儲(chǔ)設(shè)備、大數(shù)據(jù)量的傳輸一般采用優(yōu)先級(jí)較低的塊傳輸方式[1]，但目前針對(duì)該傳輸方式仍采用文獻(xiàn)[1，3]中所描述的USB軟件系統(tǒng)預(yù)設(shè)的資源分配機(jī)制。根據(jù)文獻(xiàn)[1，3]中對(duì)USB軟件系統(tǒng)的描述，該機(jī)制是一種 “先到先得，盡力而為”的工作模式，進(jìn)行帶寬資源分配時(shí)需要不斷“試錯(cuò)”以滿足預(yù)定的分配原則，不具備感知、學(xué)習(xí)USB總線傳輸狀態(tài)，調(diào)整預(yù)定分配原則的能力，使得數(shù)據(jù)傳輸過(guò)程中帶寬未能得到充分利用。

針對(duì)USB軟件系統(tǒng)對(duì)帶寬資源分配中存在的問(wèn)題，設(shè)計(jì)一種具有學(xué)習(xí)能力的帶寬分配方法，對(duì)提高大數(shù)據(jù)傳輸效率很有必要。本文結(jié)合SARSA強(qiáng)化學(xué)習(xí)算法，設(shè)計(jì)一種大數(shù)據(jù)傳輸下的智能帶寬分配方法，該方法在行動(dòng)—評(píng)價(jià)的過(guò)程中獲得環(huán)境知識(shí)，通過(guò)不斷的“試錯(cuò)”來(lái)改進(jìn)行動(dòng)方案以適應(yīng)環(huán)境，最終達(dá)到提高USB帶寬的有效利用率和吞吐量的目的。

1 USB數(shù)據(jù)傳輸

1.1 資源分配

USB傳輸?shù)?種類型中，同步和中斷方式屬于周期的數(shù)據(jù)傳輸(Periodic)，而控制和塊方式屬于非周期的傳輸(NonPeriodic)。周期傳輸可以分配高達(dá)90％的總線帶寬；控制傳輸最高可分配10％的總線帶寬；塊傳輸以盡力而為的方式利用剩余的總線帶寬[1]。每類傳輸在每1ms幀中共享USB總線帶寬，如圖 1所示，圖中SOF表示幀的開(kāi)始。

圖1 1 ms USB幀中帶寬預(yù)留分配

數(shù)據(jù)傳輸時(shí)系統(tǒng)軟件根據(jù)上述機(jī)制對(duì)當(dāng)前傳輸類型進(jìn)行資源分配，當(dāng)傳輸同步、中斷、控制對(duì)應(yīng)業(yè)務(wù)量少或沒(méi)有時(shí)，USB系統(tǒng)軟件可將剩余帶寬資源盡量地分配給塊傳輸[1]。

1.2 事務(wù)處理與數(shù)據(jù)幀

事務(wù)處理是USB總線數(shù)據(jù)傳輸?shù)幕締挝唬鳈C(jī)和USB設(shè)備間的一次通信由一個(gè)或多個(gè)事務(wù)處理組成。總線驅(qū)動(dòng)根據(jù)設(shè)備相關(guān)信息將IRP(I/O Request Packet)轉(zhuǎn)化生成相應(yīng)的傳輸事務(wù)，主控制器驅(qū)動(dòng)產(chǎn)生與每個(gè)傳輸事務(wù)相對(duì)應(yīng)的傳輸描述符TD(Transfer Descriptors)[4]。主控制器驅(qū)動(dòng)按照“先到先得”和式(1)所述的原則[2-3]，選擇TD(即事務(wù)調(diào)度)組成數(shù)據(jù)幀列表， USB主控制器依次讀取處理該幀列表以完成數(shù)據(jù)傳輸。

(1)

其中，TTD(i)表示第i個(gè)TD所需處理時(shí)間，SOF為每一USB數(shù)據(jù)幀開(kāi)始所需的字節(jié)，DTD(i)為第i個(gè)TD所包含的數(shù)據(jù)字節(jié)數(shù)，PTD(i)表示第i個(gè)TD傳輸?shù)膮f(xié)議消耗字節(jié)數(shù)。USB數(shù)據(jù)幀結(jié)構(gòu)如圖 2所示，每幀包含一個(gè)Frame Pointer和若干TD、QH(Queue Heads)，其中一個(gè)QH指向的所有TD對(duì)應(yīng)同一個(gè)USB設(shè)備[4-5]。

圖2 幀列表結(jié)構(gòu)

上述事務(wù)調(diào)度機(jī)制由于不具備學(xué)習(xí)能力，塊傳輸時(shí)數(shù)據(jù)幀的形成受事務(wù)屬性的影響，使Frame List中某些數(shù)據(jù)幀對(duì)USB帶寬資源的利用不夠充分，造成資源的浪費(fèi)。因此，針對(duì)上述問(wèn)題，本文結(jié)合強(qiáng)化學(xué)習(xí)算法對(duì)USB傳輸事務(wù)進(jìn)行智能調(diào)度，使得帶寬資源利用更充分。

2 基于強(qiáng)化學(xué)習(xí)的事務(wù)調(diào)度

2.1 強(qiáng)化學(xué)習(xí)

強(qiáng)化學(xué)習(xí)基本模型如圖 3所示。在學(xué)習(xí)過(guò)程中，agent選擇一個(gè)動(dòng)作a作用于環(huán)境，環(huán)境接受該動(dòng)作后轉(zhuǎn)移至新?tīng)顟B(tài)s，同時(shí)產(chǎn)生一個(gè)強(qiáng)化信號(hào)r反饋給agent，agent再根據(jù)強(qiáng)化信號(hào)和環(huán)境當(dāng)前狀態(tài)選擇下一個(gè)動(dòng)作，選擇原則是使受到正獎(jiǎng)賞的概率增大[6]。

圖3 強(qiáng)化學(xué)習(xí)模型

強(qiáng)化學(xué)習(xí)算法的目的是學(xué)習(xí)尋找一個(gè)策略π:S(A，使得每個(gè)狀態(tài)s的值Vπ(s) (或)Qπ(s,a)達(dá)到最大[6]。

(2)

Qπ(s,a)=Eπ{r(s,a)+

γVπ(δ(s,a))|s0=s,a0=a}

(3)

(4)

(5)

其中，ri表示在i時(shí)刻的立即回報(bào)，γ為折扣因子，δ(s,a)表示在狀態(tài)s時(shí)執(zhí)行動(dòng)作a的結(jié)果狀態(tài)，V*(s)和Q*(s,a)為最優(yōu)值函數(shù)，其相應(yīng)的最優(yōu)策略為

π*(s) = argmaxV*(s) 或

π*(s) = argmaxQ*(s,a)

(6)

SARSA 算法是強(qiáng)化學(xué)習(xí)中的一種在策略(on-policy)的時(shí)序差分算法[7]， 它由 Rummery 和 Naraajan 提出，Singh證明了在策略算法的收斂性。SARSA 在進(jìn)行迭代更新時(shí)用到五元組(s,a,r,s′,a′)，其中s表示當(dāng)前狀態(tài)；a表示當(dāng)前狀態(tài)下選擇的動(dòng)作；r是動(dòng)作a的獎(jiǎng)勵(lì)；s′和a′則分別是后續(xù)的狀態(tài)和動(dòng)作。SARSA 算法中行為值函數(shù)采用實(shí)際的Q值進(jìn)行迭代，通過(guò)式子(7)迭代規(guī)則來(lái)獲得Q*(s,a)：

Q(st,at)←Q(st,at)+α[rt+

γQ(st+1,at+1)-Q(st,at)]

(7)

式中Q(st,at)代表t時(shí)刻的Q值；st為狀態(tài)；at為當(dāng)前所采取的動(dòng)作；rt為獎(jiǎng)勵(lì)函數(shù)值；γ為折扣因子，表示未來(lái)回報(bào)相對(duì)當(dāng)前回報(bào)的重要性；α為學(xué)習(xí)率， 其中0≤α≤1 和 0 <γ≤1。

2.2 基于Sarsa學(xué)習(xí)算法的調(diào)度模型

1)狀態(tài)集合

本文中將塊傳輸事務(wù)按照傳輸數(shù)據(jù)包的大小進(jìn)行分類，每一類傳輸事務(wù)用Transi，i=(1,2,…,n)表示。將每種傳輸事務(wù)在每一幀中所分配的數(shù)量組合定義為USB總線傳輸狀態(tài)：S={NumTran1,NumTran2,NumTran3,…,NumTranN}。

2)動(dòng)作集合

事務(wù)調(diào)度過(guò)程中，對(duì)每種TD的操作將影響USB總線上的傳輸狀態(tài)，因此將對(duì)每種TD的操作定義為動(dòng)作集合，Ai={AddTran(i),ReplaceTran(i),Null}，其中AddTran(i)表示增加第i個(gè)傳輸事務(wù)，ReplaceTran(i)表示替換第i個(gè)傳輸事務(wù)，Null表示不采取任何動(dòng)作。

3)動(dòng)作探索策略

Sarsa學(xué)習(xí)通過(guò)探索—利用過(guò)程發(fā)現(xiàn)最優(yōu)目標(biāo)，“利用”過(guò)程選擇最高Q值所對(duì)應(yīng)的動(dòng)作；“探索”過(guò)程則是隨機(jī)選擇動(dòng)作以彌補(bǔ)“利用”的不足[7]。本文采用“ε—貪婪探索策略”，在狀態(tài)s下以小概率ε隨機(jī)選擇動(dòng)作action，以1-ε選擇具有最大Q值的動(dòng)作。

4)立即回報(bào)

將USB總線在狀態(tài)si下執(zhí)行動(dòng)作ai轉(zhuǎn)移到狀態(tài)sj后，總線帶寬利用率的增加值定義為立即回報(bào)，r(si,ai)=Utilize_Increaseij。

通過(guò)對(duì)USB總線傳輸狀態(tài)S進(jìn)行感知，并根據(jù)策略π選取動(dòng)作對(duì)塊傳輸事務(wù)Transi進(jìn)行操作，觀察回報(bào)r與狀態(tài)s不斷的改進(jìn)策略π，使得USB帶寬有效利用率提高，基于SARSA學(xué)習(xí)算法的調(diào)度方法描述如下所示。

1)建立狀態(tài)空間State和動(dòng)作空間Action，初始化Q值表和ε；

2)初始化USB總線傳輸狀態(tài)s；

3)映射出當(dāng)前狀態(tài)statei，并建立一個(gè)符合當(dāng)前狀態(tài)的數(shù)據(jù)幀；

4)根據(jù)“ε—貪婪探索策略”選擇動(dòng)作actioni；

5)根據(jù)所選動(dòng)作對(duì)該幀進(jìn)行傳輸事務(wù)的增加或替換，構(gòu)建新的數(shù)據(jù)幀，觀察回報(bào)和狀態(tài)；

6)更新Q值表；

7)更新?tīng)顟B(tài)與動(dòng)作；

8)若USB帶寬有效利用率未達(dá)到飽和，則跳到步驟3，否則結(jié)束。

3 仿真與分析

3.1 仿真建立

為驗(yàn)本文證算法在本應(yīng)用中的有效性，將本文設(shè)計(jì)的調(diào)度方法與系統(tǒng)本身采用的 “先到先得，盡力而為”的調(diào)度方法按照以下描述場(chǎng)景進(jìn)行仿真實(shí)驗(yàn)對(duì)比。

本文針對(duì)USB Full-Speed(12Mbps)傳輸速率中的3類塊傳輸事務(wù)進(jìn)行建模仿真。該3類塊傳輸事務(wù)分別為：Trans(1)-16Bytes、Trans(2)-32Bytes、Trans(3)-64Bytes。上述三種傳輸事務(wù)在全速塊傳輸?shù)拿恳粠兴軅鬏數(shù)淖畲蟠螖?shù)分別為51、33、19[1]。因此，USB總線狀態(tài)集合S={NumTran1,NumTran2,NumTran3}，0≤NumTrans1≤51，0≤NumTrans2≤33，0≤NumTrans3≤19。貪婪探索策略中隨機(jī)選擇動(dòng)作的概率ε初值設(shè)為0.01，每次迭代后將其乘以0.99以降低隨機(jī)選擇動(dòng)作的概率。

3.2 實(shí)驗(yàn)結(jié)果與分析

針對(duì)文獻(xiàn)[1,5]所描述的系統(tǒng)自身事務(wù)調(diào)度方法和本文設(shè)計(jì)的方法，分別進(jìn)行獨(dú)立仿真實(shí)驗(yàn)，并對(duì)USB帶寬有效利用率、吞吐量用、有效數(shù)據(jù)傳輸量、帶寬剩余量等指標(biāo)進(jìn)行分析。兩種方法仿真結(jié)果如圖 4所示，圖中Sarsa曲線代表本文方法，System代表系統(tǒng)調(diào)度方法，橫坐標(biāo)每一個(gè)值代表10次仿真，縱坐標(biāo)每一個(gè)值為每10次仿真的平均值。 本實(shí)驗(yàn)結(jié)果對(duì)應(yīng)SARSA算法迭代算子中的折扣因子γ、學(xué)習(xí)率α分別取0.9和0.5。經(jīng)多次仿真實(shí)驗(yàn)，當(dāng)折扣因子γ取值較小(0.5、0.8)時(shí)，容易收斂于次優(yōu)策略，仍造成一定帶寬資源浪費(fèi)，且收斂較慢；取值0.9及以上時(shí)對(duì)實(shí)驗(yàn)結(jié)果影響不明顯，且能獲得較好的效果。學(xué)習(xí)率α的取值較小(0.1、0.2)或越接近1時(shí)，容易產(chǎn)生擾動(dòng)，影響收斂速度，造成帶寬利用率波動(dòng)。

圖4 仿真結(jié)果

從圖 4中可知，USB軟件系統(tǒng)本身的調(diào)度方法不具備學(xué)習(xí)能力，在整個(gè)過(guò)程中上述四種指標(biāo)均處于波動(dòng)狀態(tài)。基于SRASA算法的調(diào)度方法在學(xué)習(xí)初期，由于系統(tǒng)未獲得環(huán)境的全部先驗(yàn)知識(shí)，帶寬利用率較低，但隨著學(xué)習(xí)次數(shù)的增加，經(jīng)過(guò)約120次左右的學(xué)習(xí)后各項(xiàng)指標(biāo)均達(dá)到一個(gè)較好值，且保持穩(wěn)定。

為進(jìn)一步驗(yàn)證算法的性能，分別對(duì)上述兩種方法進(jìn)行1 000次實(shí)驗(yàn)測(cè)試，實(shí)驗(yàn)結(jié)果如圖 5所示，兩種方法各項(xiàng)指標(biāo)對(duì)比如表 1。

從表 1兩種方法1 000次實(shí)驗(yàn)測(cè)試結(jié)果對(duì)比可看出，基于SARSA算法的調(diào)度方法的各項(xiàng)指標(biāo)均優(yōu)于系統(tǒng)方法，且波動(dòng)較小，性能穩(wěn)定。前者相對(duì)后者平均有效利用率提高21.94％，平均吞吐量提高3.53％，平均有效數(shù)據(jù)傳輸量提高了21.94％，平均剩余帶寬降低了86.36％。可看出采用SARSA學(xué)習(xí)算法后的USB塊事務(wù)調(diào)度能夠使USB帶寬資源得到充分的利用，提高數(shù)據(jù)傳輸?shù)男省?/p>

表1 1 000次測(cè)試實(shí)驗(yàn)結(jié)果統(tǒng)計(jì)分析

圖5 1 000次測(cè)試實(shí)驗(yàn)結(jié)果

3.3 收斂性分析

SARSA學(xué)習(xí)算法是一種在線策略強(qiáng)化學(xué)習(xí)算法，動(dòng)作探索策略的選擇對(duì)算法的收斂性具有關(guān)鍵作用。文獻(xiàn)[8]給出了SARSA學(xué)習(xí)算法的收斂性定理，并在分別采取GLIE和RRR漸進(jìn)貪心動(dòng)作探索策略的情況下，對(duì)該定理進(jìn)行了證明。

定理1[7]對(duì)一個(gè)有限“動(dòng)作—狀態(tài)”空間的MDP，將一個(gè)固定的GLIE學(xué)習(xí)策略π作為概率Pr(a|s,t,nt(s),Q)的一個(gè)集合。假設(shè)在時(shí)間步t時(shí)，根據(jù)策略π選擇動(dòng)作at，此時(shí)Q=Qt，Qt的值根據(jù)式(7)進(jìn)行計(jì)算。當(dāng)同時(shí)滿足以下三個(gè)條件時(shí)，Qt收斂于最優(yōu)值Q*，策略πt收斂于最優(yōu)策略π*：

1)Q值存儲(chǔ)于一個(gè)查找表中；

3)回報(bào)值方差Var{r(s,a)} <∞。

本文選擇三種塊傳輸所有組合中滿足帶寬限制條件的6 450種組合作為狀態(tài)集合，并采用查找表對(duì)Q值進(jìn)行存儲(chǔ)。根據(jù)文獻(xiàn)[8]的證明可知本文所采用的“ε—貪婪探索策略”屬于GLIE學(xué)習(xí)策略，且滿足漸近貪心和對(duì)“狀態(tài)—?jiǎng)幼鳌笨臻g無(wú)限遍歷的條件。

回報(bào)值方差定義如下：

Var{r(s,a)}=

(8)

由于-1

(9)

將式(9)代入式(8)，可得

Var{r(s,a)}=

(10)

綜上所述，本文中采用的基于SARSA算法的事務(wù)調(diào)度滿足定理1的收斂條件，因此，該調(diào)度方法可通過(guò)一定次數(shù)的學(xué)習(xí)，獲得最優(yōu)調(diào)度策略π*。

4 結(jié) 論

帶寬資源的有效利用對(duì)于大數(shù)據(jù)傳輸十分重要，本文針對(duì)包含多種塊傳輸類型的情況，結(jié)合強(qiáng)化學(xué)習(xí)算法，設(shè)計(jì)了一種基于SARSA學(xué)習(xí)算法的傳輸事務(wù)調(diào)度方法。該方法在學(xué)習(xí)過(guò)程中，通過(guò)評(píng)估函數(shù)對(duì)所選動(dòng)作進(jìn)行評(píng)價(jià)、影響后續(xù)動(dòng)作的選取，極大提高了傳輸事務(wù)的調(diào)度效率。本文通過(guò)建立模型并仿真，比較了系統(tǒng)調(diào)度方法和本文方法。仿真結(jié)果表明在相同傳輸環(huán)境下，本文所設(shè)計(jì)的基于SARSA算法的調(diào)度方法能夠獲取較高的帶寬有效利用率，且提高USB總線吞吐量。

參考文獻(xiàn)：

[1]COMPAQ,HEWLETT-PACKARD,INTEL.Universal serial bus specification[S].Revision 2.0,2000.

[2]HUANG C Y,KUO T W,PANG A C.QoS support for USB2.0 periodic and sporadic device requests [C]//IEEE International Real-Time Systems Symposium,2004:395-404.

[3]INTEL.Universal host controller interface (UHCI) design guide[S].Revision 1.1,Intel,1996.

[4]MISSIMER E,LI Y,WEST R.Real-time USB communication in the quest operating system [C]//IEEE Real-Time Technology and Applications-Proceedings,2013:11-20.

[5]ANDERSON DON,DZATKO DAVE,MINDSHARE INC.Universal serial bus system architecture [M].2nd ed.Addison-Wesley Educational Publishers Inc,2001:141-154.

[6]舒波，李大銘，趙新良，等.基于強(qiáng)化學(xué)習(xí)算法的公交信號(hào)優(yōu)先策略[J].東北大學(xué)學(xué)報(bào)：自然科學(xué)版,2012,33(10):1513-1516.

[7]JIANG L B,JIANG H,WU S,et al.Decentralized cognitive MAC protocol based on SARSA [C]//IEEE International Conference on Communication Technology Proceedings,ICCT,2012:392-396.

[8]SINGH S,JAAKKOLA T,SZEPESVRI C,et al.Convergence results for single-step on-policy reinforcement learning algorithms [J].Machine Learning,2000,38(03):287-308.