基于Markov链的车载自组网MAC层建模及分析

孙 伟，张和生，2，潘 成，杨 军，白 喆

（1.北京交通大学 电气工程学院，北京100044；2.北京交通大学 轨道交通控制与安全国家重点实验室，北京100044）

0 引 言

车 载 自 组 网（Vehicular ad－hoc networks，VANETs）依靠先进的信息技术和通信技术为日益严重的交通问题，如道路拥堵和事故频发，提供了解决方案［1］。

在车辆间和车辆与基础设施间的通信中，VANETs采用2010年批准的IEEE 802.11p［2］作为底层协议以解决车辆环境下的无线接入问题，如车辆高速移动导致的通信拓扑频繁变换及不同应用类型通信性能的不同需求等。而MAC（Media access control）层在上述通信问题解决中起着重要作用。

IEEE 802.11p MAC采用IEEE 802.11e［3］的增强型分布信道访问（Enhanced distributed channel access，EDCA）机制以提供多种应用类型的服务，然而不同类型的服务质量（Quality of service，QoS）要求不同，如安全类应用实时性要求较高［4］。IEEE 802.11p MAC 层对其参数进行了修改以适用于车路环境。为满足不同类型应用的QoS，需要对IEEE 802.11p的网络性能进行分析，并对性能指标进行求解，如吞吐量、时延、丢包率等。

很多文献采用分析模型对IEEE 802.11e EDCA 机制进行了研究。其中大部分是对Bianchi模 型［5］的 改 进，如 文 献［6］对DCF（Distributed coordination function）的非饱和吞吐量进行了计算。文献［7］提出了基于Markov链的分析模型，但未考虑消息内部碰撞。文献［8］建立了IEEE 802.11e的综合分析模型对其性能进行分析。文献［9，10］使用三维Markov 链对IEEE 802.11e EDCA 机制的不同接入类（Access categories，ACs）性能进行了分析。文献［11］采用Markov链模型研究了IEEE 802.11p协议在安全方面的应用。文献［12］采用二维Markov链对IEEE 802.11p EDCA 机制进行了分析，该模型分析时并未考虑信道忙时退避计数器的挂起机制。

本文采用二维Markov链建立了IEEE 802.11p EDCA 机制的饱和模型，通过该模型对吞吐量、丢包率和时延进行了求解。同时还研究了退避挂起机制对丢包率的影响。结果表明，随着通信范围内车辆数的增加，归一化吞吐量逐渐减小，丢包率和时延逐渐增加。高优先级队列始终有较大归一化吞吐量和较小传输时延。同样验证了IEEE 802.11p采用的EDCA 机制能够保证不同应用类型的服务质量。

1 IEEE 802.11p MAC的特点

MAC层采用的EDCA 机制是由DCF 扩展而来，因此其信道访问方式与DCF 一致，均为CSMA／CA（Carrier sense multiple access with collision avoidance）。EDCA 定义了四类AC 以保证不同优先级消息的QoS，用AC［i］（i＝0，1，2，3）表示。

EDCA 机制中，不同优先级的AC 在其信道访问时采用不同的仲裁帧间间隔（Arbitration inter frame spacing，AIFS）和 竞 争 窗 口（Contention window，CW）值，如表1所示。

表1 IEEE 802.11p EDCA参数值［2］Table 1 EDCA parameters of IEEE 802.11p［2］

AC［i］（i＝0，1，2，3）的TAIFS［AC［i］］计 算 公 式如下［2］：

式中：TSIFS是短帧间间隔的持续时间（Short inter frame spacing，SIFS）；TaSlotTime是一个时隙所持续的时间；NAIFSN［AC［i］］是AIFSN［AC［i］］的值。

信道访问过程为：当AC［i］队列有消息发送时，首先监听信道，如果信道空闲持续时间超过AIFS［AC［i］］，且AC［i］的退避计数器的值为0，则该消息直接被发送，如图1站点A 所示。如果不为0，AC［i］的退避计数器在每个空闲时隙减1，若此时检测到信道忙，退避计数器被挂起，停止递减，如图1站点C所示。此后，站点重新监听信道，如果信道持续空闲时间为AIFS［AC［i］］，退避计数器解挂开始递减。若退避计数器值递减为0，站点向信道发送该消息。当同一站点内多个AC队列的退避计数器同时递减为0，消息的同时发送导致内部碰撞。此时，内部碰撞由站点内的虚拟调度器采用冲突避免方式选择高优先级AC消息的发送，从而造成低优先级AC 消息的重传。不同站点间消息产生碰撞时，不论优先级高低，消息都需重传。由表1和式（1）知，高优先级AC 具有较小的AIFS和CW 值，因此可优先获得信道访问权。

图1 IEEE 802.11p EDCA信道访问Fig.1 EDCA basic access mechanism of IEEE 802.11p

2 模型的建立与分析

2.1 EDCA机制的Markov链模型

MAC层在保证不同AC 的QoS上起着重要作用。为了分析不同AC 的QoS，需对IEEE 802.11p MAC层所采用的EDCA 机制进行建模分析。

采用EDCA 机制进行信道访问时，AC 的退避过程实际为退避计数器状态转移的过程，状态间的转移符合Markov性，即下一状态只与当前状态有关而与过去状态无关。因此可采用二维Markov链描述单个AC 的退避机理，如图2 所示，该模型分析时考虑了不同AC 的不同竞争窗口值、消息的内部碰撞以及信道忙时的退避挂起机制。模型分析采用文献［10］的类似方法。在分析时，假定信道为理想状态，即数据包不存在由于误码导致的重传。同时假定AC 队列饱和，即每个队列始终有消息发送。

图2Markov链中二元组｛s（t），b（t）｝表示信道访问的退避过程，s（t）为t时刻消息的重传次数或称退避阶段（Backoff stage）的值，b（t）为t时刻退避计数器的值。状态Di，j表示退避计数器挂起时所处的状态，即此时的退避阶段和退避计数器的值。pb表示检测到信道忙时退避计数器的挂起概率。当退避计数器值减为0时，站点将向信道发送该消息，若此时同一站点内高优先级队列或其他站点同时发送消息，则消息间发生碰撞，其概率为pc。碰撞使竞争窗口值加倍，重传次数加1，进入下次退避过程，当超过最大重传次数m时，消息将被丢弃。

图2 IEEE 802.11p单个AC的Markov链模型Fig.2 Signal AC Markov model of IEEE 802.11p

由图2Markov链模型知，消息在第j次退避阶段，退避计数器的取值为［0，Wj－1］中的随机整数。Wj的计算式如下：

Markov链的一步转移概率如下：

（1）第j退避阶段，退避计数器值从（j，k＋1）状态转移到（j，k）状态，即时隙内检测到信道空闲的概率为1－pb，其转移表达式为：

（2）第j退避阶段，退避计数器从（j，k＋1）状态转移到Di，k状态，即时隙内检测到信道忙导致退避计数器挂起的概率为pb，其转移表达式为：

（3）第j－1退避阶段，消息发送时，如果发生碰撞，使得消息重传，则重传次数加1，并转至第j退避阶段，其转移表达式为：

（4）第j退避阶段，若消息成功发送，则返回到初始阶段，发送下一条消息，其表达式为：

（5）当达到最大退避阶段m 时，若消息发送成功，则返回初始阶段发送下一消息；反之，则丢弃该消息，同样返回初始阶段发送下一消息。因此在最大退避阶段以概率1返回到初始阶段。表达式为：

2.2 系统稳态概率分析

相邻两个退避阶段的关系式为：

通过式（8）和式（9）可得出任意状态与初始状态的关系式为：

在平稳分布中，根据归一化条件，可得初始状态b0，0如式（11）所示：

任意退避阶段只有退避计数器值减为0时，消息才能被发送。因此消息能被发送的概率τ的表达式为式（12）：

用τi表示站点内AC［i］（i＝0，1，2，3）队列消息能被发送的概率，其表达式如式（13）所示：

由式（13）知，AC［i］队列中消息能被发送的概率与AC［i］的最小竞争窗口值、碰撞概率和信道忙概率有关。需再找出τi、pci、pbi之间的其他关系式，联立求解消息能被发送的概率和碰撞概率等。

若本站点内其他AC队列或其他站点同时有消息发送时，消息间会产生碰撞。消息的内部碰撞依据消息优先级决定消息发送权，高优先级消息继续发送，低优先级消息则重传。与外部站点消息发生碰撞时，无论优先级高低消息都需重传。用PIi表示AC［i］的内部碰撞概率，则其表达式为［13］：

AC［i］队列消息发送概率σi的表达式为［16］：

式中：N 为站点总数量。

AC［i］消息发送时产生碰撞的概率为pci：

执行退避过程时，退避计数器的值在时隙内减少，即信道空闲概率为1－pbi，其表达式为：

将式（13）（17）（18）联立组成一个非线性方程组，可求解出AC［i］的发送概率σi和碰撞概率pci。

2.3 归一化吞吐量

归一化吞吐量为时间段内数据帧成功发送的量。设Pidle为信道空闲即时隙内无消息发送的概率；PTr为时隙内至少有一个站点发送消息的概率；PSi为AC［i］消息成功发送即时隙内只有一个站点发送AC［i］消息的概率；PFail为由于碰撞导致消息发送失败即时隙内有两个或两个以上的站点同时发送消息的概率。则其表达式为：

设Si为站点内AC［i］的归一化吞吐量，则：

式中：TE［Li］为传输AC［i］数据包所需时间。分母第一部分为信道空闲时间的均值；第二部分为数据包成功发送的时间均值；第三部分为数据包发送失败的时间均值。式（20）中TSi为消息成功发送的传输时延，TCi为消息间发生碰撞所持续的时间。其表达式为：

式中：THead为消息帧帧头的传输时间；TLi为数据包的传输时间；δ为传播时延；TSIFS为SIFS的持续时间；TACK为ACK 的传输时间；为碰撞时数据包最大传输时间。

2.4 丢包率

设PDropi为站点内AC［i］队列的丢包率。若数据包第m 次重传失败，则该数据包将被丢弃造成丢包，丢包率表达式为：

2.5 时延分析

MAC层时延定义为：消息从成为AC队列的队首开始到接收站点成功接收到该帧为止的时间段，由接入时延和传输时延组成。用TD表示消息的时延，E［TDi］为AC［i］消息时延的均值，表达式如下［5］：

式中：E［Ni］为AC［i］消息退避重传次数的均值，其表达式为：

式（23）中：E［BDi］为AC［i］消息的退避时间，该时间由两部分组成，分别为：不挂起情况下，退避计数器连续减少到0所持续的时间，用Xi表示，其期望表达式如式（25）所示；检测到信道忙导致退避计数器挂起所等待的时间，用FRi表示，表达式如式（26）所示。

式中：E［Nbacki］为AC［i］的退避计数器在递减过程中被挂起的次数，其表达式为［5］：

AC［i］队列消息的退避时间为：

T0为消息发生碰撞时，重新监听信道前所等待的时间，在基本接入模式下其表达式为：

3 结果分析

3.1 性能指标分析

建立如图3所示的通信场景。联立求解得到归一化吞吐量、丢包率和时延性能指标，并通过NS－2［14］仿真验证了分析模型的准确性。计算中所需要参数的列表如下：数据包长度为512 bytes；位传输速率为6 Mbit／s；通信范围为500 m；数据包产生量为10packet／s；短帧间间隔SIFS为32μs；时隙时间slottime为13μs；帧头传输时间Thead为57μs；ACK 传输时间TACK为39μs；传播时延δ为2μs。

图4为不同AC队列的归一化吞吐量随通信范围内车辆数的变化情况。可见，随着通信范围内车辆数的增加，AC 队列的归一化吞吐量值逐渐减小。AC［3］队列的吞吐量最大，而AC［0］最小。原因为发生内部冲突时，虚拟调度器会选择高优先级消息发送，造成低优先级消息重传。

图3 通信场景Fig.3 Communication scenario

图4 归一化吞吐量随车辆数变化图Fig.4 Normalized throughput variation with number of vehicles

图5 为不同AC队列的丢包率随通信范围内车辆数的变化情况。通过求解公式知，丢包率只与碰撞概率有关。由图5可知，不同AC 队列的丢包率随车辆数的增加而上升。当通信范围内仅有一辆车时，AC［3］的丢包率为0，AC［0］的丢包率为1.3%，该丢包是由于消息的内部碰撞造成的。随着通信范围内车辆数的增加，消息碰撞加剧，导致消息重传次数增加，丢包现象加剧。当通信范围内有35辆车时，4个AC 的丢包率均超过了20%。为满足丢包率不超过10%［3］的要求，由图5知，在饱和情况下通信范围内最大车辆数为19辆。

随着通信范围内车辆数的增加，不同AC 队列消息的时延也增加，如图6所示。其中，高优先级队列AC［3］和AC［2］队列的时延增加不明显，而较低优先级队列AC［1］和AC［0］的时延急剧增加，原因为高优先级消息发送的增加，阻塞了低优先级发送，从而导致时延增大。通信范围内车辆数为35时，AC［3］和AC［2］的时延均小于100 ms，满足安全应用数据交互的时限要求［12］。AC［1］和AC［0］可应用于非时间苛求类型的场合，如娱乐等。

图5 丢包率随车辆数变化图Fig.5 Drop rate variation with number of vehicles

图6 时延随车辆数变化图Fig.6 Time delay variation with number of vehicles

3.2 退避挂起机制对性能的影响

IEEE 802.11p协议规定退避时存在挂起机制。而很多文献采用Markov链分析时没予以考虑，退避计数器的值以概率1 递减，即图2 中pb＝0，不存在Di，j状态。所以研究退避挂起机制对网络性能（特别是对丢包率）的影响是必要的。

图7 退避挂起机制对丢包率的影响Fig.7 Effect of backoff mechanism on drop rate

图7 为退避挂起机制对丢包率的影响。当通信范围内车辆数较少时，退避挂起机制对改善丢包率无明显作用。但随着通信范围内车辆数的增加，无退避挂起机制会导致丢包率的急剧上升。若无退避机制，当通信范围内有19辆车时，丢包率会达到90%以上，而存在退避挂起机制时，丢包率仅为10%。从而说明退避过程中采用挂起机制能有效地减少数据包碰撞概率，从而降低丢包率。

4 结束语

本文考虑了不同类型消息间的影响，在消息内部碰撞和信道忙时的退避挂起机制情况下，采用二维Markov链对IEEE 802.11p的EDCA 机制进行了建模。研究了归一化吞吐量、丢包率和时延性能指标，并分析了退避挂起机制对丢包率的影响。结果表明：当通信范围内车辆数固定时，单个站点的归一化吞吐量和时延与不同优先级AC队列有关；丢包率只与AC 队列和碰撞概率有关。而高优先级队列始终有较大吞吐量、较低时延和较小丢包率。通过分析得出为满足安全类应用丢包率的要求，通信范围内的车辆数最多为19辆。同样也验证了IEEE 802.11p 的EDCA机制能满足不同类型消息的服务质量。

［1］Dar K，Bajhouya M，Gaber J，et al.Wireless communication technologies for ITS applications［J］.IEEE Communications Magazine，2010，48（5）：156－162.

［2］IEEE Std.IEEE 802.11p：Wireless LAN medium access control（MAC）and physical layer（PHY）specifications－amendment 7：wireless access in vehicular environment［S］.2010.

［3］IEEE 802.11e／D6.0.Draft supplement to part 11：Wireless medium access control（MAC）and physical layer specifications：medium access control（MAC）enhancement for quality of service（QoS）［S］.2003.

［4］Cheng H T，Shan H，Zhuang W.Infotainment and road safety service support in vehicular networking：From a communication perspective［C］∥Mech Syst Signal Process，2011，25（6）：2020－2038.

［5］Bianchi G.Performance analysis of the IEEE 802.11 distributed coordination function［J］.IEEE Journal on Selected Areas in Communications，2000，18（3）：535－547.

［6］杨卫东，李亚辉，马建峰.衰落信道中802.11DCF的非饱和吞吐量分析［J］.吉林大学学报：工学版，2008，38（3）：695－699.Yang Wei－dong，Li Ya－Hui，Ma Jian－feng.Non－saturation throughput analysis of 802.11DCF in fading channel［J］.Journal of Jilin University（Engineering and Technology Edition），2008，38（3）：695－699.

［7］Robinson J，Randhawa T.Saturation throughput analysis of IEEE 802.11eenhanced distributed coordination function［J］.IEEE Journal Selected Areas Communication，2004，22（5）：917－928.

［8］Tursunova S，Kim Young－tak.Realistic IEEE 802.11eEDCA model for QoS－aware mobile cloud service provisioning［J］.IEEE Transactions on Consumer Electronics，2012，58（1）：60－68.

［9］Gas M，Kosek－saott K，Natkaniec M，et al.3D Markov chain－based saturation throughput model of IEEE 802.11EDCA［J］.Electronics Letters，2011，47（14）：826－827.

［10］Inan I，Keceli F，Ayanoglu E.Analysis of the 802.11eenhanced distributed channel access function［J］.IEEE Transactions on Communications，2009，57（6）：1753－1764.

［11］Yao Yuan，Rao Lei，Liu Xue.Performance and reliability analysis of IEEE 802.11p safety communication in a highway environment［J］.IEEE Transactions on Vehicular Technology，2013，62（9）：4198－4212.

［12］Han C，Dianati M，Tafazollir E，et al.Analytical study of the IEEE 802.11p MAC sublayer in vehicular networks［J］.IEEE Transactions on Intelligent Transportation Systems，2012，99：1－14.

［13］Huang C L，Liao W.Throughput and delay performance of IEEE 802.11e enhanced distributed channel access（EDCA）under saturation condition［J］.IEEE Transactions on Wireless Communications，2007，6（1）：136－145.

［14］The Network Simulator－ns－2.［DB／OL］［2014－06－21］.http：／／www.isi.edu／nsnam／ns／.