基于SARSA学习算法的USB块传输研究*

张秋云，江 虹

(西南科技大学信息工程学院，四川 绵阳 621010)

USB总线上的数据传输分为同步、中断、控制、块传输等四种类型[1]，不同设备采用的传输方式不尽相同，在有限的带宽资源下如何协调数据传输对实现USB高效传输非常重要。目前仅文献[2]针对同步传输的设备设计并实现了一种实时的USB驱动，使设备获得了可靠的QoS保证，同时也提高了USB带宽利用率，但对于其他方式的传输尚未进行研究。大容量存储设备、大数据量的传输一般采用优先级较低的块传输方式[1]，但目前针对该传输方式仍采用文献[1，3]中所描述的USB软件系统预设的资源分配机制。根据文献[1，3]中对USB软件系统的描述，该机制是一种 “先到先得，尽力而为”的工作模式，进行带宽资源分配时需要不断“试错”以满足预定的分配原则，不具备感知、学习USB总线传输状态，调整预定分配原则的能力，使得数据传输过程中带宽未能得到充分利用。

针对USB软件系统对带宽资源分配中存在的问题，设计一种具有学习能力的带宽分配方法，对提高大数据传输效率很有必要。本文结合SARSA强化学习算法，设计一种大数据传输下的智能带宽分配方法，该方法在行动—评价的过程中获得环境知识，通过不断的“试错”来改进行动方案以适应环境，最终达到提高USB带宽的有效利用率和吞吐量的目的。

1 USB数据传输

1.1 资源分配

USB传输的4种类型中，同步和中断方式属于周期的数据传输(Periodic)，而控制和块方式属于非周期的传输(NonPeriodic)。周期传输可以分配高达90％的总线带宽；控制传输最高可分配10％的总线带宽；块传输以尽力而为的方式利用剩余的总线带宽[1]。每类传输在每1ms帧中共享USB总线带宽，如图 1所示，图中SOF表示帧的开始。

图1 1 ms USB帧中带宽预留分配

数据传输时系统软件根据上述机制对当前传输类型进行资源分配，当传输同步、中断、控制对应业务量少或没有时，USB系统软件可将剩余带宽资源尽量地分配给块传输[1]。

1.2 事务处理与数据帧

事务处理是USB总线数据传输的基本单位，主机和USB设备间的一次通信由一个或多个事务处理组成。总线驱动根据设备相关信息将IRP(I/O Request Packet)转化生成相应的传输事务，主控制器驱动产生与每个传输事务相对应的传输描述符TD(Transfer Descriptors)[4]。主控制器驱动按照“先到先得”和式(1)所述的原则[2-3]，选择TD(即事务调度)组成数据帧列表， USB主控制器依次读取处理该帧列表以完成数据传输。

(1)

其中，TTD(i)表示第i个TD所需处理时间，SOF为每一USB数据帧开始所需的字节，DTD(i)为第i个TD所包含的数据字节数，PTD(i)表示第i个TD传输的协议消耗字节数。USB数据帧结构如图 2所示，每帧包含一个Frame Pointer和若干TD、QH(Queue Heads)，其中一个QH指向的所有TD对应同一个USB设备[4-5]。

图2 帧列表结构

上述事务调度机制由于不具备学习能力，块传输时数据帧的形成受事务属性的影响，使Frame List中某些数据帧对USB带宽资源的利用不够充分，造成资源的浪费。因此，针对上述问题，本文结合强化学习算法对USB传输事务进行智能调度，使得带宽资源利用更充分。

2 基于强化学习的事务调度

2.1 强化学习

强化学习基本模型如图 3所示。在学习过程中，agent选择一个动作a作用于环境，环境接受该动作后转移至新状态s，同时产生一个强化信号r反馈给agent，agent再根据强化信号和环境当前状态选择下一个动作，选择原则是使受到正奖赏的概率增大[6]。

图3 强化学习模型

强化学习算法的目的是学习寻找一个策略π:S(A，使得每个状态s的值Vπ(s) (或)Qπ(s,a)达到最大[6]。

(2)

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

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

(3)

(4)

(5)

其中，ri表示在i时刻的立即回报，γ为折扣因子，δ(s,a)表示在状态s时执行动作a的结果状态，V*(s)和Q*(s,a)为最优值函数，其相应的最优策略为

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

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

(6)

SARSA 算法是强化学习中的一种在策略(on-policy)的时序差分算法[7]， 它由 Rummery 和 Naraajan 提出，Singh证明了在策略算法的收敛性。SARSA 在进行迭代更新时用到五元组(s,a,r,s′,a′)，其中s表示当前状态；a表示当前状态下选择的动作；r是动作a的奖励；s′和a′则分别是后续的状态和动作。SARSA 算法中行为值函数采用实际的Q值进行迭代，通过式子(7)迭代规则来获得Q*(s,a)：

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

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

(7)

式中Q(st,at)代表t时刻的Q值；st为状态；at为当前所采取的动作；rt为奖励函数值；γ为折扣因子，表示未来回报相对当前回报的重要性；α为学习率， 其中0≤α≤1 和 0 <γ≤1。

2.2 基于Sarsa学习算法的调度模型

1)状态集合

本文中将块传输事务按照传输数据包的大小进行分类，每一类传输事务用Transi，i=(1,2,…,n)表示。将每种传输事务在每一帧中所分配的数量组合定义为USB总线传输状态：S={NumTran1,NumTran2,NumTran3,…,NumTranN}。

2)动作集合

事务调度过程中，对每种TD的操作将影响USB总线上的传输状态，因此将对每种TD的操作定义为动作集合，Ai={AddTran(i),ReplaceTran(i),Null}，其中AddTran(i)表示增加第i个传输事务，ReplaceTran(i)表示替换第i个传输事务，Null表示不采取任何动作。

3)动作探索策略

Sarsa学习通过探索—利用过程发现最优目标，“利用”过程选择最高Q值所对应的动作；“探索”过程则是随机选择动作以弥补“利用”的不足[7]。本文采用“ε—贪婪探索策略”，在状态s下以小概率ε随机选择动作action，以1-ε选择具有最大Q值的动作。

4)立即回报

将USB总线在状态si下执行动作ai转移到状态sj后，总线带宽利用率的增加值定义为立即回报，r(si,ai)=Utilize_Increaseij。

通过对USB总线传输状态S进行感知，并根据策略π选取动作对块传输事务Transi进行操作，观察回报r与状态s不断的改进策略π，使得USB带宽有效利用率提高，基于SARSA学习算法的调度方法描述如下所示。

1)建立状态空间State和动作空间Action，初始化Q值表和ε；

2)初始化USB总线传输状态s；

3)映射出当前状态statei，并建立一个符合当前状态的数据帧；

4)根据“ε—贪婪探索策略”选择动作actioni；

5)根据所选动作对该帧进行传输事务的增加或替换，构建新的数据帧，观察回报和状态；

6)更新Q值表；

7)更新状态与动作；

8)若USB带宽有效利用率未达到饱和，则跳到步骤3，否则结束。

3 仿真与分析

3.1 仿真建立

为验本文证算法在本应用中的有效性，将本文设计的调度方法与系统本身采用的 “先到先得，尽力而为”的调度方法按照以下描述场景进行仿真实验对比。

本文针对USB Full-Speed(12Mbps)传输速率中的3类块传输事务进行建模仿真。该3类块传输事务分别为：Trans(1)-16Bytes、Trans(2)-32Bytes、Trans(3)-64Bytes。上述三种传输事务在全速块传输的每一帧中所能传输的最大次数分别为51、33、19[1]。因此，USB总线状态集合S={NumTran1,NumTran2,NumTran3}，0≤NumTrans1≤51，0≤NumTrans2≤33，0≤NumTrans3≤19。贪婪探索策略中随机选择动作的概率ε初值设为0.01，每次迭代后将其乘以0.99以降低随机选择动作的概率。

3.2 实验结果与分析

针对文献[1,5]所描述的系统自身事务调度方法和本文设计的方法，分别进行独立仿真实验，并对USB带宽有效利用率、吞吐量用、有效数据传输量、带宽剩余量等指标进行分析。两种方法仿真结果如图 4所示，图中Sarsa曲线代表本文方法，System代表系统调度方法，横坐标每一个值代表10次仿真，纵坐标每一个值为每10次仿真的平均值。 本实验结果对应SARSA算法迭代算子中的折扣因子γ、学习率α分别取0.9和0.5。经多次仿真实验，当折扣因子γ取值较小(0.5、0.8)时，容易收敛于次优策略，仍造成一定带宽资源浪费，且收敛较慢；取值0.9及以上时对实验结果影响不明显，且能获得较好的效果。学习率α的取值较小(0.1、0.2)或越接近1时，容易产生扰动，影响收敛速度，造成带宽利用率波动。

图4 仿真结果

从图 4中可知，USB软件系统本身的调度方法不具备学习能力，在整个过程中上述四种指标均处于波动状态。基于SRASA算法的调度方法在学习初期，由于系统未获得环境的全部先验知识，带宽利用率较低，但随着学习次数的增加，经过约120次左右的学习后各项指标均达到一个较好值，且保持稳定。

为进一步验证算法的性能，分别对上述两种方法进行1 000次实验测试，实验结果如图 5所示，两种方法各项指标对比如表 1。

从表 1两种方法1 000次实验测试结果对比可看出，基于SARSA算法的调度方法的各项指标均优于系统方法，且波动较小，性能稳定。前者相对后者平均有效利用率提高21.94％，平均吞吐量提高3.53％，平均有效数据传输量提高了21.94％，平均剩余带宽降低了86.36％。可看出采用SARSA学习算法后的USB块事务调度能够使USB带宽资源得到充分的利用，提高数据传输的效率。

表1 1 000次测试实验结果统计分析

图5 1 000次测试实验结果

3.3 收敛性分析

SARSA学习算法是一种在线策略强化学习算法，动作探索策略的选择对算法的收敛性具有关键作用。文献[8]给出了SARSA学习算法的收敛性定理，并在分别采取GLIE和RRR渐进贪心动作探索策略的情况下，对该定理进行了证明。

定理1[7]对一个有限“动作—状态”空间的MDP，将一个固定的GLIE学习策略π作为概率Pr(a|s,t,nt(s),Q)的一个集合。假设在时间步t时，根据策略π选择动作at，此时Q=Qt，Qt的值根据式(7)进行计算。当同时满足以下三个条件时，Qt收敛于最优值Q*，策略πt收敛于最优策略π*：

1)Q值存储于一个查找表中；

3)回报值方差Var{r(s,a)} <∞。

本文选择三种块传输所有组合中满足带宽限制条件的6 450种组合作为状态集合，并采用查找表对Q值进行存储。根据文献[8]的证明可知本文所采用的“ε—贪婪探索策略”属于GLIE学习策略，且满足渐近贪心和对“状态—动作”空间无限遍历的条件。

回报值方差定义如下：

Var{r(s,a)}=

(8)

由于-1

(9)

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

Var{r(s,a)}=

(10)

综上所述，本文中采用的基于SARSA算法的事务调度满足定理1的收敛条件，因此，该调度方法可通过一定次数的学习，获得最优调度策略π*。

4 结 论

带宽资源的有效利用对于大数据传输十分重要，本文针对包含多种块传输类型的情况，结合强化学习算法，设计了一种基于SARSA学习算法的传输事务调度方法。该方法在学习过程中，通过评估函数对所选动作进行评价、影响后续动作的选取，极大提高了传输事务的调度效率。本文通过建立模型并仿真，比较了系统调度方法和本文方法。仿真结果表明在相同传输环境下，本文所设计的基于SARSA算法的调度方法能够获取较高的带宽有效利用率，且提高USB总线吞吐量。

参考文献：

[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]舒波，李大铭，赵新良，等.基于强化学习算法的公交信号优先策略[J].东北大学学报：自然科学版,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.