针对分析模型和仿真模型研究车载自组网IEEE 802.11p广播模式网络性能存在的不足, 采用层次随机着色Petri网(HSCPN)对协议的媒体访问控制层进行建模, 模型着重描述了消息的产生、重传、退避和虚拟碰撞的过程.在此模型的基础上, 对网络性能指标进行了分析.结果表明:高优先级队列的消息具有较小的时延和时延抖动. HSCPN建模方法的采用可直观地了解协议的运行机制, 有利于协议的改进, 并可为车载自组网的部署提供理论依据.
Due to the shortages of the analytical model and simulation model, hierarchical stochastic colored Petri net has been proposed to model the media access control layer of IEEE 802.11p, which is used for investigating the broadcast performance of vehicular ad hoc networks. The proposed model has been used to describe the generation, retransmission, backoff and internal collision process. Then, the performance metrics have been simulated and analyzed. The results show that the higher priority access category has the shorter time delay and delay jitter. Moreover, the operation of the IEEE 802.11p can be intuitively understood by using the hierarchical stochastic colored Petri net(HSCPN) model, which is helpful for the protocol improvement, and it can also provide theoretical basis for the deployment of VANETs.
车载自组网(VANETs，vehicular Ad-hoc networks)采用IEEE 802.11p作为底层协广播安全消息.该消息需要及时可靠地传送至周围车辆，以保障行车安全. IEEE 802.11p的CSMA/CA机制具有不确定性，为此，需要研究IEEE 802.11p MAC层广播模式的网络性能.目前，IEEE 802.11p广播模式网络性能的研究主要采用分析模型[1-2].
针对分析模型需要假设和仿真模型在时间特性方面存在疑问的问题，很多文献采用Petri网对网络进行建模和分析.文献[3]使用随机Petri网(SPN，stochastic Petri net)描述了IEEE 802.11e的动态特性.文献[4]采用NMSPN(non Markov SPN)建立了IEEE 802.11e的MAC层模型.上述文献中没有区分不同类型消息，因而不能准确分析消息类型与性能指标间的关系.可采用着色Petri网(CPN，colored Petri net)[5]的颜色集进行区分.
为此，将随机Petri网[6]和CPN相结合提出了层次随机着色Petri网(HSCPN, hierarchical stochastic colored Petri net)模型研究IEEE 802.11p MAC层广播模式的网络性能.利用SPN中变迁的时间特性，能够清晰描述IEEE 802.11p消息的产生、退避，重传以及消息碰撞过程. CPN的颜色集用来描述不同类型消息，可简化IEEE 802.11p MAC层模型的构造.分层方法的采用，使不同过程的描述模块化，方便模型理解和调用.在HSCPN模型的基础上，对时延和时延抖动等指标进行了分析.
1 HSCPN模型的提出定义 随机着色Petri网(SCPN, stochastic CPN)是一个多元组，SCPN={Σ, P, T, A, N, C, G, E, λ, M0, I}，满足下列条件：
1) Σ是一组非空有限的集合，称为颜色集；
2) P是库所(Place)的有限集合；
3) T是变迁(Transition)的有限集合，它满足T=Tt∪Ti, Tt∩Ti=∅，其中Tt表示时间变迁的集合，Ti表示瞬时变迁的集合；
4) A是弧(Arc)的有限集合，满足P∩T=P∩A=T∩A=∅；
5) N是节点(Node)函数，满足N:A→(P×T)∪(T×P), 仅存在P与T的元素之间；
6) C是颜色(Color)函数，满足C:P→Σ;
7) G是门卫(Guard)函数，其中G:T→expr，满足∀t∈T:[Type(G(t))=B∧Type(Var(G(t)))⊆Σ]，B为布尔型(Boolean);
8) E是弧表达式(Arc expression)函数的集合，其中E:A→expr，满足∀ a∈A:[Type(E(a))=C(p)MS∧Type(Var(E(a)))⊆Σ]，C(p)MS是C(p)上的多重集的集合；
9) λ是时间变迁的实施速率或瞬时冲突变迁之间的优先级集合；
10) M是标识(Token)的集合，通常M0表示初始标示；
11) I是初始(Initialization)函数的集合，其中I:P→expr，且满足∀p∈P:[Type(I(p))=C(p)MS].
上述定义中，expr为表达式(expression)，Type(x)表示x值的类型，Var(x)表示x为一个变量.
在SCPN定义的基础上，给出HSCPN的定义.
定义层次随机着色Petri网(HSCPN, hierarchical SCPN)是由一组SCPN子网组成的有限集合，如HSCPN={SCPN1，SCPN2，…，SCPNn}，其中n是SCPN子网的数量.
2 IEEE 802.11p的HSCPN模型2.1 IEEE 802.11p顶层模型根据HSCPN定义和IEEE 802.11p协议规范，建立了分层模型.以目标车辆通信范围有4辆车为例，其顶层结构如图 1所示.
|
图 1 顶层结构 |
顶层结构中包含6个变迁，除消息广播变迁外，其余均为替代变迁.每个替代变迁都对应相应子模型(subpage)，可对替代变迁进行详尽描述.消息广播变迁用来描述消息在无线信道中的广播行为，其中“@+时延”表示传输时延.
图 1替代变迁的子模型用来描述IEEE 802.11p协议，为更详尽的描述每部分协议，将子模型划分为：消息产生模型、消息重传模型、消息退避模型以及虚拟碰撞模型，下面将对各模型进行具体描述.
2.2 消息产生模型图 2描述了消息由高层产生并到达其MAC层队列的过程.由于每个站点的接入类型(AC，access category)队列具有相同的产生过程，以AC[i](i=0, 1, 2, 3) 为例进行描述.图中，从初始化变迁到消息库所或消息产生变迁回到消息库所间的弧表达式为“()@+exp(100 000)”，exp(100 000) 表示参数为100 000的指数分布，用来表示消息产生服从Poisson过程，时间单位为μs.
|
图 2 消息产生模 |
消息产生变迁的主要作用是将消息映射到不同的AC队列，即将UNIT颜色集转化为MSG颜色集. MSG颜色集由3部分(i, Data, AT)组成，其中i表示AC[i]队列，Data表示该消息帧长度，AT表示该消息到达MAC层时的时间戳.时间戳用来准确测量消息从MAC层到被广播的延迟时间.
2.3 消息重传模型当站点内多个AC队列消息同时发送时会导致虚拟碰撞.虚拟碰撞由站点内的虚拟调度器选择高优先级队列消息的发送，从而造成低优先级队列消息的重传.因此只有AC[2]，AC[1]，AC[0]3个队列存在消息重传，而最高优先级AC[3]队列则无重传.消息重传模型如图 3所示，其中i=0, 1, 2.
|
图 3 消息重传模型 |
由图 3知，若虚拟碰撞变迁实施时，消息则返回到图 2的AC[i]MAC库所重新发送，此时计数器的值加1，若计数器值达到重传次数，AC[i]消息丢弃变迁的实施将AC[i]MAC库所的消息放入图 1的消息丢弃库所中，丢弃该消息.
2.4 消息退避模型消息退避模型如图 4所示，AC[i]MAC变迁实施后，开始执行AC[i]AIFS变迁，即检测信道在仲裁帧间间隔(AIFS，arbitration inter-frame space)时间段内是否忙碌.若信道忙，则信道忙推迟访问变迁实施，该变迁的实施采用门卫函数，只有满足该函数的条件，变迁才能可实施.信道忙变迁的门卫函数为图 1消息数量计数器的值大于0.若消息数量计数器的值等于0，信道空闲变迁实施，变迁的实施会在竞争窗口(CW，contention window)中随机选择值作为退避计数器的初始值.
|
图 4 消息退避模型 |
虚拟碰撞发生时，站点内的虚拟调度器选择高优先级AC队列消息的发送，造成低优先级AC队列消息的重传，虚拟碰撞模型如图 5所示.
|
图 5 消息虚拟碰撞模型 |
为验证HSCPN模型分析IEEE 802.11p的正确性和有效性，借助CPN Tools进行建模和分析，并采用Matlab对模型进行验证.
图 6所示为不同AC队列消息的平均时延随通信范围内车辆数变化的结果.通过分析得出，消息时延与队列优先级有关，高优先级队列始终有较小的时延，以满足安全消息的实时性要求.随着通信范围内车辆数的增加，消息时延呈增长趋势；而高优先级队列的消息不存在虚拟碰撞，时延几乎保持不变.
|
图 6 消息时延 |
图 7所示为消息的时延抖动.由于消息产生量少，不存在排队现象，造成时延抖动的主要原因是消息退避计数器的不同随机选择值.高优先级队列的消息无重传，CW值保持不变，因此其时延抖动固定不变.而低优先级队列的消息存在重传，其CW值随重传次数的增加而指数增加，导致时延抖动变化较大.通过分析仿真结果，造成图 7中异常即时延抖动急剧增加的原因为：消息在退避过程中检测到信道忙，导致退避计数器冻结.
|
图 7 时延抖动 |
采用提出的HSCPN对应用于车载自网络的IEEE 802.11p进行了建模，模型着重描述了消息的产生、重传、退避和虚拟碰撞过程.通过分析可得出HSCPN模型可直观地了解IEEE 802.11p协议广播模式的运行机制，有利于协议改进，并为VANETs的部署提供理论依据.
| [1] | Ye F, Yim R, Roy S, et al. Efficiency and reliability of one hop broadcasting in vehicular Ad hoc networks[J].IEEE Journal on Selected Areas in Communications, 2011, 29(1): 151–160. doi: 10.1109/JSAC.2011.110115 |
| [2] | Yuan Y, Lei R, Xue L. 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. doi: 10.1109/TVT.2013.2284594 |
| [3] | Moraes R, Portugal P, Vasques F. A stochastic Petri net model for the simulation analysis of the IEEE 802.11e EDCA communication protocol[C]//2006 IEEE Conference on Emerging Technologies and Factory Automation. Prague: IEEE Press, 2006: 38-45. |
| [4] | Escheikh M, Barkaoui K. Opportunistic MAC layer design with stochastic Petri nets for multimedia Ad hoc networks[C]//IEEE Symposium on Computers and Communications. Sousse: IEEE Press, 2009: 23-29. |
| [5] | Jensen K. Coloured Petri nets: basic concepts analysis methods and practical use[M]. Berlin: Springer-Verlag Press, 1997: 234-240. |
| [6] | Chiola G, Marsan M A, Balbo G, et al. Generalized stochastic Petri nets: a definition at the net level and its implications[J].IEEE Transactions on Software Engineering, 1993, 19(2): 89–107. doi: 10.1109/32.214828 |