车载网中保证服务质量的HCCA优化策略

车载网中保证服务质量的HCCA优化策略摘要：在车载网中，为了保证数据传输的服务质量，一个稳定高效的信道访问策略是十分必要的。据此，在802.11p协议的链路层信道访问控制协议HCCA策略的基础上，提出了一种基于马尔科夫决策过程的紧急数据优先的策略(URF-HCCA)来保证数据传输的服务质量。该策略采用按需分配资源的方式来减少系统的传输冗余和传输延迟。此外,它还引入了基于延迟预测的接入控制模型。仿真结果表明,与其他几种策略相比，URF-HCCA优化策略可以很好的满足传输的服务质量需求，提高信道利用率、降低平均传输延迟以及系统的丢包率。关键词：车载网，IEEE 802.11P，服务质量，URF-HCCA，接入控制，马尔科夫决策过程。1. 概述在车载网环境中，特别是在密集的高速移动场景或者事故频发的车辆移动场景中，一些意外情况的发生可能会引起数个小时乃至数天的交通拥堵。因此，建立一个健壮的，稳定的，以及中断容忍度高的车辆网络是十分必要的，它可以及时的传送紧急状况信息以及有效道路信息来提高交通的安全系数和交通的高效性。HCCA策略是802.11p45协议中链路层的一种无竞争的集中式信道访问策略，它的协调器会维护一个轮询表来控制其他节点对信道资源的使用。HCCA策略会有效减少信道访问延迟，但是，它的资源分配并不是自适应的，大量的轮询包和空数据包也会产生大量的数据冗余。此外，在HCCA方案的接入控制策略也将难以满足数据传输的延迟、带宽以及丢包率等服务质量的要求。本文在HCCA策略的基础上提出了一种紧急请求优先的信道访问策略（URF-HCCA）以及基于延迟预测的接入控制策略。在路边设备端，协调器首先给要收集各个车载节点的数据传输请求，并根据各个请求的参数进行资源分配，为了保证传输的服务质量，协调器引入接入控制策略来对请求的数据流进行准入控制；在车载单元端则会应用马尔可夫决策过程来管理传输队列。URF-HCCA策略以及相应的接入控制策略会在很大程度上提高信道的利用率，减少平均传输延迟以及丢包率。2. 研究背景本文主要研究的是车辆与路旁设备通信的密集公路场景。网络中有n个移动节点分享1个控制信道以及6个服务信道，这些车载单元在这两种信道间隔中不停的转换，控制信道用来传输管理控制信息，服务信道用来进行数据传输。按照HCCA策略的定义，每个超级帧中包含非竞争阶段以及竞争阶段，协调器主要控制非竞争阶段的数据传输，它会为每个数据请求分配占用信道的时间，占用带宽，以及传输优先级。我们将紧急数据的传输设置为最高优先级进行传输。当数据流请求过多以至于系统不能满足所有的传输请求时，就需要建立一个接入控制模型来对数据流进行准入控制。一个标准的接入控制模型需要有两类输入：对当前流量的具体描述和对请求数据的服务质量需求，这些信息都会存储在TSPEC要素里。协调器会根据输入的这两类条件来判断是否同意接下来的数据传输，如果当前条件不能满足服务质量需求，则协调器必须拒绝该数据传输。TSPEC要素主要包含项如表1所示。马尔可夫决策过，是在决策结果一部分随机，另一部分是在决策者的控制的情况下，为决策模型提供的一个数学框架。决策者需要以一定的概率采取一个措施来从一个状态转移到下一个状态，在这个过程中也会产生一定的报酬。到到达最终状态时，报酬的总和要尽可能的达到最大值。决策模型是由五个参数组成的： S, A, PAs,s, RAs, s, ，其中，S是系统的有限状态集，A是系统的有限行动集合，PAs,s是当系统从一个状态转移到另一个状态时，采取某一个行动的概率，RAs, s是当系统采取一个行动从状态s转移到状态s时，得到的报酬值，是报酬函数。关键的问题是根据系统当前的状态，从有限行动集中选取一个行动，为了尽可能的找出最优策略，在作出决策时也可以参考当前状态和历史状态信息。在有很多不确定因素的情况下，MDP决策模型已经被大范围的应用于许多领域例如生态科学，经济理论和通信系统等等91314。经过多种反复验证，马尔科夫决策模型被证明可以应用于调度算法的改进，并且可以取得很好的效果。表1 TSPEC要素定义参数定义M数据流的最大传入速率m数据流的平均传入速率U数据包的平均大小P物理层最小比特率B传输一个数据包的时间和带宽分配值S两个连续SP的时间间隔D数据流传输的最大延迟值3. URF-HCCA策略及接入控制模型3.1 URF-HCCA策略模型在URF-HCCA策略中，车载单元将会主动向协调器请求资源预定。这些移动节点每间隔一段时间会收集本节点的传输请求，然后将这些请求写入ADDTS请求列表，将他们发送给协调器。协调器收集到所有的ADDTS请求列表后，会根据接入控制模型来评估这些请求，如果评估后确定该请求可以被满足，协调器会根据己端的调度策略来分配网络资源，包括传输时间、传输优先级、带宽以及其他的TSPEC信息，并把这些信息写入ADDTS反馈信息中。在下一个超级帧的beacon帧中，将这些ADDTS反馈信息广播给车载单元节点；如果评估后确定该请求应该被拒绝，那么就不会产生对应的ADDTS反馈信息。在beacon广播之后，其他的车载节点会查看反馈信息列表，如果在这些列表中发现了自己的地址及反馈信息，那么它会立即按照分配给自己的信道资源进行数据传输。相反，如果该车载节点的地址以及反馈信息并没有在广播列表中出现，这就意味着该请求被拒绝了，在这种情况下，移动节点会调整自己的请求列表，并在下一个超级帧中重新将请求发送出去。如果移动节点在当前时间段内没有传输请求，则不会产生ADDTS请求列表。这种策略会有效的减少信息冗余，具体的URF-HCCA策略过程将在图1中展示。3.2 接入控制模型当协调器从车载节点接收到请求时，它会通过衡量当前的情况来允许或者拒绝请求者对信道的使用权。协调器通过采用这种衡量标准来减少传输延迟或者提高系统利用率。在TSPEC要素表中78，有一项内容是延迟边界，它定义的是传输延迟的最大期望值，当传输一个数据包的端到端延迟小于最大延迟期望值小于阈值时，该传输请求就应该被允许，相反则应该拒绝。在讨论数据包的平均端到端延迟之时，需要用到以下几个变量，包括服务时间以及端到端延迟。对于输入速率为数据流请求，服务时间被定义为从数据包到达数据最前端到ACK数据包被成功接收的时间间隔。在非竞争阶段中，访问延迟并不存在，因此，数据包的服务时间可以入公式（1）所示，服务速率可以表示为服务时间TS的倒数，因此，交通密度可以定义为。TS=B+SIFS+END+i=1x(SIFS+Dt+SIFS+ACK) (1)端到端延迟D可以定义为从数据包到达队列到ACK数据包被成功接收的时间间隔。一个随机数据包的平均端到端延迟可以表示为平均队列长度除以平均输入速率，如公式（2）所示。对于一个输入数据流来说，只要平均端到端延迟小于要求的阈值，该数据流请求就会被接受，反之则被拒绝。在公式（2）中，Qavg表示平均队列长度，avg表示任意节点的平均输入速率。Dbound值为延迟阈值。D=QavgavgDbound (2)在M/M/1模型中，根据排队论原理，平均队列长度Qavg可以表示为公式（3）。其中m表示队列长度的最大值。表示数据流的平均密度，表示数据的输入速率，TS表示每个数据包的平均服务时间。图1 HCCA策略与URF-HCCA策略对比Qavg=1-(m+1)1-m+1=Ts1-Ts(m+1)(Ts)m+11-(Ts)m+1 (3)平均输入速率avg可以表示为公式（4），其中表示当前数据流的输入速率，ext则表示已经存在的数据流的平均输入速率，新的数据流只有在不影响已有的数据流传输的情况下，才可能被满足。协调器首先要确保已经允许传输但是尚未传输完成的数据流仍旧可以使用预定的带宽及其他资源，之后，剩余的信道资源才会分配给新接收的数据流请求，qsat表示队列已满的概率，该参数根据排队论可以被表示为公式（5）。avg=ext+(1-qsat)(4)qsat=(1-)m (5)当前已存在的数据流请求的输入速率ext可以表示为公式（6）, SysLoad_ext表示协调器所接收到的所有的数据的输入速率。N表示该协调器所覆盖的所有移动节点数量，由于非饱和状态的信道容量与饱和状态的信道容量的斜率几乎可以表示为一条直线，并且该斜率与非饱和状态的输入速率与饱和状态的输入速率的斜率相同，如公式（7）所示。因此，根据我们的分析模型，饱和状态的信道容量与输入速率可以被计算出来。由于协调器会定期的检测各个节点的信道利用率，Capacityext也会被估测出来。ext=SysLoad_extN (6)SysLoad_ext=CapacityextCapacitysatSysLoad_sat (7)以上公式合起来描述的是实时端到端延迟与请求的延迟阈值的比较模型。如果模型计算出的延迟小于阈值，则请求被接受，否则，请求会被拒绝。该接入控制模型的过程如图2所示。3.3基于MDP的调度模型在协调器收集所有的传输请求之后，一旦确定某些请求可以被接受，则协调器会尽可能多的分配传输资源并使信道利用率最大化，基于马尔科夫决策过程的调度策略可以很好的实现上述功能当兵提高系统的鲁棒性以及灵活性。此外，在车载节点端，当接收到协调器分配的信道资源使用权之后，也会应用马尔科夫决策过程模型来对当前缓存中的数据包进行重新调度，以确保优先级最高的数据先传输。图2 接入控制模型及MDP模型系统设定在协调器的覆盖范围内有n个车载移动节点，因此，系统的状态集可以表示为s1,sn!。每个数据流的的传输延迟可以表示为x1,x2,xn。协调器每采取一个措施都会产生一个相应的报酬，该报酬值应与系统的性能相关。该报酬值是传输延迟与丢包率的参数。系统的丢包率是由每个车载节点检测出来的，该值是由有效的数据传输率与数据重传率连合得到的，因此，丢包率可以被用来计算系统的报酬值。数据包的传输延迟越小，丢包率越小，则报酬值越大。公式（8）描述了在时刻m，当协调器采取动作am时，产生的报酬值，该值是传输延迟与丢包率的倒数。W(delay(m,am)和W(lossRatem)表示的是在采取动作am时的传输延迟和丢包率的标准化值。由于采取不同的动作会导致不同的报酬值，因此协调器总是会采取产生最大报酬值的动作。协调器采取某个动作的概率如公式（9）所示，其中W(m,am)表示的是在时刻m，采取动作am所产生的报酬的加权值。R:1W(delay(m,am)W(lossRatem) (a1amat )(8)Pm,a=W(m,am)W(m,a1)+W(m,at)a1amat (9):DrealDbound (10)公式（10）表示的是报酬指标。由于实时传输延迟是由队列延迟Dqueue以及自身的传输延迟Dself组成的，因此，公式（10）也可以改写为公式（11）。其中Dqueue和Dself的关系由公式（12）表示。Dqueue+DselfDlimit (11)Dqueuei=Dself1+Dself2+Dselfi-1 (12)数据流i的队列延迟可以表示为前（i-1）个数据流的传输延迟的总和。马尔科夫决策过程的设计模型如图2所示。这里需要注意的是，可能有多个数据流需要传输，以至于在一个周期内不能完全传输完这些请求，在这种情况下，为每个请求节点所分配的带宽以及传输时间长度都要相应减小，对传输时间的分配调度如公式（13）（14）所示。如公式所示，当请求数据流在一个周期中处理不完时，所有的请求节点都需要作出牺牲。另一方面，这些请求节点也需要根据相应的调度策略来尽量满足优先级高的数据包的传输要求，或者在下一个周期中继续传输未完的数据。i=1nTXOPi-TXOPi=TC (13)TXOPI=i=1nTXOPITc (14)3.4复杂度分析复杂度的计算可以被分作两部分：马尔科夫决策模型的计算以及队列重排，这两部分的复杂度均为O(n2)。因此，总复杂度也是O(n2)。C=OAdmission+OCalMDP+O(Sort)=On2+On+1+O(n2)=O(n2) (15)4. 仿真结果分析4.1仿真设计在图3的仿真场景中，最多有50个移动节点在方圆1公里的范围内移动，这个范围正好可以控制在一个协调器的覆盖范围之内。如图所示，当出现某些特殊状况时，车载节点将会发送紧急信息到协调器来把这种情况广播给其他的节点知晓。每个车载节点的移动速度的初始值都是设定的，以此来保证紧急信息的数据量占到总数据量的10%。仿真是从非饱和系统状态逐渐过渡到饱和的系统状态。数据的密度可以通过移动节点的数量以及数据速率来调节。仿真试验实在Qualnet 4.0平台上完成的。紧急数据包的优先级我们设定为6,7两个级别，而其他的数据包包括在CP阶段的数据包的优先级都设定为0-5。在仿真过程中，每个参与的车载节点都会不停的在范围中移动进出持续7200s以使系统性能达到稳定状态。数据的产生符合正态分布。我们首先会比较标准的HCCA策略5，URF-HCCA策略，WPCF3策略以及EDF-CSMA1策略在非饱和状态，中等饱和状态和饱和状态的信道利用率。在这三种状态中，各个车载节点的缓存不为空的概率分别被设置为0.1, 0.5和0.9。其中的非饱和状态和饱和状态的信道利用率值分别为系统的下限和上限值，而中等饱和状态的信道利用率的期望值应该在这两个值之间。此外，我们也会比较URF-HCCA，WPCF以及HCCA策略的平均传输延迟以及丢包率。图3 仿真场景设计图4.2结果及分析图4，5，6描述了在非饱和状态，中等状态以及饱和状态的信道利用率情况。如图4所示，在非饱和状态，URF-HCCA策略的信道利用率要远远高于其他三种策略。随着移动节点数量从5增加到50,，这四种策略的信道利用率都呈现出平滑上涨趋势，上涨的速率逐渐减小。对于URF-HCCA策略来说，最大的信道利用率可以达到83%。而随着移动节点数量的增加，URF-HCCA策略与EDF-CSMA策略之间的信道利用率差距逐渐增大，而URF-HCCA策略与WPCF策略之间的差距则会增大到22%。HCCA策略的信道利用率要比URF-HCCA策略的低10%左右。图5显示的是在中等饱和状态中，这四种策略的信道利用率情况。在这种条件下，URF-HCCA策略，EDF-CSMA策略与WPCF策略间的信道利用率差别比在非饱和状态下的差别要小很多。其中，URF-HCCA策略的利用率一直比其他三种策略要高，最高可以达到85%。从图中我们可以看出，URF-HCCA策略与WPCF策略的信道利用率曲线变化趋势几乎相同，而EDF-CSMA策略的曲线变化趋势则减缓很多。与非饱和状态相比，各条曲线的变化趋势愈加平缓，这意味着各个策略的CFP阶段长度已经开始达到极限值，各策略的调度策略开始产生更重要的影响。图6显示的是在饱和状态下的信道利用率情况。在这种状态下，URF-HCCA策略，EDF-CSMA策略以及WPCF策略的利用率都达到了一个很高的水平 - 都高于80%。URF-HCCA策略下的利用率最高可以达到86%。URF-HCCA策略与EDF-CSMA策略间的差别在4%左右，而URF-HCCA策略与WPCF策略间的差别则不是特别明显 在2%左右，HCCA策略的利用率则一直稳定在70%到72%之间。随着移动节点数量的增加，这四种策略的信道利用率都呈现出平稳的缓慢增长。综上，图6展示了这四种策略的信道利用率的极限值，与此同时，它也显示出URF-HCCA策略的利用率要高于同等状态下的其他三种策略。图7展示的是URF-HCCA策略的平均延迟。图7中包含了三条曲线，分别是EDF-CSMA策略的理论延迟，WPCF策略的理论延迟，以及URF-HCCA策略的仿真试验得到的平均延迟。从图中可以看出，这些曲线所代表的