车联网中交通安全消息动态优先调度机制*

周永筝，邱恭安，邱永芳

(南通大学 电子信息学院，江苏 南通226019)

车联网中交通安全消息动态优先调度机制*

周永筝，邱恭安*，邱永芳

(南通大学 电子信息学院，江苏 南通226019)

车联网中两类交通安全消息共享有限控制信道带宽，在消息突发状态下无法保证事件触发消息的传播性能，导致预警失效。基于差异化的消息传播性能需求提出了一种动态优先级区分的调度机制，按事件优先级分别进行队列管理，赋予事件触发消息优先权，通过设置优先级调度阈值实现对事件触发消息的动态调度。当优先队列长度高于阈值时，其抢占调度时隙。当队列长度低于阈值一半，退出抢占过程，恢复非抢占优先调度方法。仿真显示，所提调度机制能够减小事件触发消息的端到端时延约1.3 ms，提高周期性消息的公平性约0.22。

车联网；交通安全消息；周期性消息；事件触发消息；区分调度；动态优先

1 引 言

随着智能交通系统的发展，基于车联网的应用日益丰富。车联网通过交通安全应用实现车与车、车与路边设施之间的高效通信，为提高交通安全和交通管理效率提供了可能。车节点通过与周围车节点交换自身状态消息和路况消息，实现交通事故预警[1]，但在高密度交通流状态下，需要传播的消息量极大，而信道带宽有限，易因接入冲突导致传输失败，使交通安全消息传播不够及时，影响交通预警效果[2]。采用基于交通安全消息业务区分的动态优先级调度机制能提高紧急交通安全消息传输性能，实现交通及时预警。

交通安全消息按预警方式不同可分为周期性安全消息(Periodic Safety Messages,PSM)和事件触发型安全消息(Event-Driven Safety Messages,EDSM)两类[3]。 事件触发型安全消息是发生交通紧急事件时产生的预警消息，属于被动预警消息，对端到端传输时延要求高，可容忍一定误差。周期性安全消息是车节点定期广播的交通状态消息，是主动预警消息，对准确度要求高，可容忍一定时延。在资源约束条件下，消息区分的传播机制通过差异化处理两类消息，以保障紧急消息的传播性能，实现交通安全预警。其中，优先级区分的调度机制是减小排队时延的有效方法之一。

目前，安全消息调度机制主要有：先到先传(First Come First Served,FCFS)调度，其消息调度顺序只由到达时间决定，应用于车联网环境下易使得紧急程度高的EDSM可能需要经过较长等待时间之后才能被处理，影响交通预警效果；抢占式(Preemptive)调度[4]，根据消息紧急程度划分优先级，优先级较高的消息先处理，消息处理过程中，如果有优先级更高的消息到达，则中断当前的处理过程，立即处理新到达的消息，应用于车联网环境下易使得PSM因等待时间过长而失效；多队列(Multi-level Queue)调度，每个节点包含多个调度队列，安全消息按种类和紧急程度被分配给不同队列，使得各类消息有序传播，应用于车联网环境下时，消息分类过细会使得队列数目过多，有些队列长期为空，但仍需给其分配时隙造成带宽资源浪费[5]；轮询(Polling)调度，为每个队列提供非竞争的调度机制，有效避免接入冲突，但应用于车联网环境下时，无优先级设置，不能满足队列重载时EDSM的优先处理[6]。

本文基于消息优先级和负载状态，提出的调度机制动态分配不同消息的传输时隙，以保证EDSM低时延传播，避免PSM等待时间过长，提高消息传播的公平性。

2 系统模型

交通安全消息传播模型如图1所示。设车节点通信范围为r，其通信范围内有i-1个邻居车节点，车节点建立并维护两个消息队列，安全消息按类别进入不同队列进行调度转发。当无预警交通事件时，到达车节点的安全消息均为PSM，优先队列1中缓存消息数量为0，安全消息按到达顺序进入普通队列2排队，车节点按FCFS对队列2中的PSM依次调度转发，实现交通状态周期性更新。

图1 交通安全消息传播模型Fig.1 Traffic safety message propagation model

通常，车节点通过控制信道获取邻居车节点广播的PSM，当发生紧急事件后，车载设备通过传感器获取事故相关的交通状态信息，生成EDSM。利用IEEE802.11 媒体接入控制(Medium Access Control，MAC)帧头部的帧控制字段中电源管理(Power Management)字节(B12)对两类安全消息进行区分，两类安全消息按类别进入不同的队列。由于EDSM要求低时延处理且为小概率消息，设优先队列1缓存空间小于队列2[7]，则交通安全消息的两队列动态优先级调度过程为：首先，车节点检测两队列的缓存消息长度，按FCFS方式优先处理队列1中的消息，随后开始处理队列2中的PSM；在处理队列2 中消息时，持续监测队列1中的排队消息长度，当消息长度大于抢占阈值且队列2中消息未完成发送处理，则按抢占调度方式，停止队列2中的数据发送，转而优先处理队列1中消息；当队列1中的消息长度低于抢占阈值一半时，结束抢占过程，继续处理队列2中的消息，直至所有排队消息发送完成再转发队列1中的消息。单个周期内调度完成后，车节点对行驶状态做出相应调整以规避交通事故，提高交通效率。

综上，交通安全消息动态优先级调度机制效率关键在于两类安全消息的区分入队列处理，而调度性能关键在于抢占阈值的设置。

3 动态优先级区分调度

在交通安全消息调度过程中，通过对安全消息进行动态优先级区分调度能够提高调度机制对交通环境变化的自适应性和公平性。优先级区分调度过程包括安全消息入队列以及调度转发过程。

3.1 安全消息的定义

基于IEEE802.11p协议，安全消息m定义为(ma,mn,mq,mv)，其中：ma表示安全消息的种类，mn表示车节点序列号(identity，ID)，mq表示消息内容，mv表示车节点速度。安全消息的种类分为EDSM和PSM。车节点ID是车节点之间相互区分的标志，由车载GPS位置决定。消息内容是两类安全消息的具体内容，PSM内容包括十字路口碰撞警告、前方车辆转弯警告等，而EDSM内容包括紧急事件发生的时间地点以及事故种类[8]。未发生交通紧急事件时，每个车节点周期性接收和广播安全状态消息，发生交通紧急事件后，需对接收到的EDSM消息进行泛洪式重复广播，故两类安全消息的消息密度随车节点密度变化。车节点速度指车节点仪表盘显示的当前行驶速度。

两类安全消息到达同一车节点的过程相互独立，车节点建立并维护两个相应的消息队列。设某车节点通信范围内i-1个邻居车节点相互独立地发送其安全消息至该车节点，若其本身将发送某类安全消息，则该车节点缓存队列有i个安全消息。

设车联网控制信道的容量为Cbit/s，基于时分多址接入(Time Division Multiple Access,TDMA)方法，车节点的周期性传输时隙为100 ms[9]。在一个传输周期内，若优先队列中平均有N1个EDSM消息，每个消息为Ebit。普通队列中平均有N2个PSM消息，每个消息为Pbit，则当队列不过载时，调度机制能有效区分转发各队列缓存消息，即

(1)

3.2 安全消息入队列过程

当安全消息m1,m2,m3，…，mi到达车节点时，EDSM消息被赋予高优先级1(Pr1)，进入队列1中排队转发；PSM消息被设置为低优先级2(Pr2)，进入队列2中排队转发。相同类型的消息在各自队列中按到达时间顺序排队。

在某路段上，设到达车节点的安全消息服从到达率为λ的泊松过程[10]。若EDSM到达率为λ1，服务率为1/μ1，PSM到达率为λ2，服务率为1/μ2，且λ=λ1+λ2[11]，则车节点的两类消息队列中，有n个消息的稳态概率分别为

(2)

其中：

(3)

车节点调度系统对不同队列中的安全消息进行动态优先级区分的调度，实现差异化的消息转发。

3.3 安全消息调度过程

与绝对优先不同，动态优先级调度机制允许优先队列1缓存少量分组。车联网中，通常用队长Q的大小来描述队列负载状态，只有当队列1消息长度超过门限，赋予其暂时绝对优先权。车节点在调度之前需检测两队列中的消息长度为l1、l2，调度开始后，按优先级高低首先对队列1中的消息进行调度，队列1中的消息按FCFS的方式处理，以保证最低调度时延。队列1中的消息处理完毕后，开始对队列2中的消息按FCFS调度，同时，需检测队列1中的消息长度，当队列1中的消息长度均小于阈值QT时，采用非抢占调度，即队列1中新到的消息需等待队列2 中原先排队消息调度完毕之后再处理；如果在队列2的调度过程中，发现队列1中的消息长度大于阈值QT，则队列2中的调度过程被队列1抢占，处理队列1中的消息使其队长低于阈值QT的一半，再对队列2中的消息继续进行处理直至队列2 中l2个消息调度完毕。安全消息出队列过程的关键是设置阈值QT。

阈值QT与EDSM所在队列1的队长有关。设队列1中可容纳的消息长度为QE，则阈值QT为

QT=δ×QE，0≤δ≤1。

(4)

式中：δ为阈值QT占队列1长度的比率。

对于EDSM，为使消息时延最小，QT需尽量小，即δ需尽量小，但QT的减小会挤占PSM调度机会，导致公平性下降，因此，需设置优化和函数求得最佳阈值[12]。

定义优化函数Zp为

Zp=a×fdelay(δ)+b×ffair(δ)。

(5)

fdelay(QT)和ffair(QT)均是QT在[0,1]上的增函数，分别代表QT对EDSM时延和PSM公平系数的影响，a和b为各自权值系数[13]。设定

(6)

取a=1，b=-1，则优化函数可表达为

Zp=-2δ2+2δ-1。

(7)

对优化函数求导，可得

(8)

当δ=0.5时，导数为0，优化函数取得极大值，故QT为队列1总长度的50%，即队列1中消息长度超过队列1总缓存的50%时，需控制队列2的调度时间。

设优先队列1中当前排队消息队长为Qi，则当对优先队列2中的消息进行调度时，比较Qi和QT的大小，当Qi>QT，需采取抢占式调度，否则不需采取抢占式调度。

队列2被抢占之后，比较Qi和0.5QT的大小，根据比较结果判断抢占是否结束，若Qi>0.5QT，则继续抢占，否则停止抢占调度。

4 性能分析

时延和公平性是衡量调度机制性能的两个重要指标。在区分调度保障两类安全消息各自传输性能的前提下，尽量实现两类安全消息之间的相对公平性，并保持低时延传输至关重要。设队列负载不会过载(λ<1)，用端到端时延来描述两类安全消息性能，对PSM增加公平系数反映该调度机制的相对公平性。

4.1 时延

交通安全消息的端到端传播时延一般包括消息传输时间、消息处理时间、消息在信道中传输时间以及消息排队时间四个部分。若EDSM所在优先队列1的服务率为1/μ1，方差为1/μ12，二阶矩为 2/μ1，PSM所在普通队列2的服务率为1/μ2，方差为1/μ22，二阶矩为2/μ2[11]。当队列2中调度过程未被抢占时，平均剩余服务时间为

(9)

EDSM在队列中的平均等待时延为

(10)

安全消息端到端时延具体表达为

(11)

式中：Mpr1表示事件触发型安全消息的大小，St为消息传输速率，d为当前车节点与信源车节点之间距离，Sp为消息在信道中的传输速率，W11表示消息在队列中的等待时间。所以，队列1中的消息端到端总时延为

(12)

则安全消息平均时延为

(13)

队列2中的调度过程被抢占时，EDSM平均剩余服务时间为

(14)

EDSM在队列中的平均等待时延为

(15)

队列2处理过程中被抢占时，队列1中的消息调度端到端时延具体为

(16)

此时，队列1中端到端总时延为

(17)

则EDSM平均时延为

(18)

对于队列2中的周期性安全消息，未被抢占时，周期性安全消息的时延也为消息传输时间、消息处理所需时间、消息在信道中传输所需时间以及消息排队时间之和。PSM在队列中的平均等待时延为

(19)

端到端时延具体表达为

(20)

式中：Mpr2表示周期性安全消息的大小,W21表示消息在队列中的等待时间。所有周期性安全消息时延之和为

(21)

平均时延为

(22)

队列2处理过程中，被队列1抢占时，PSM平均剩余服务时间为

(23)

PSM在队列中的平均等待时延为

(24)

端到端时延具体表达式为

(25)

此时，总时延为

(26)

平均时延为

(27)

4.2 公平性

(28)

称σfair为周期性安全消息的公平系数，系数值越大表示调度周期性安全消息公平性越高。

4.3 时间复杂度分析

若车节点总数为i，两类交通安全消息按到达时间入队列需进行(i-1)次比较，时间复杂度为O(lgi)。随后，在调度队列2中消息时，检测队列1中消息长度以判断是否抢占时间复杂度为O(1)，因此，一个周期内，调度总时间复杂度为O(lgi)。现有调度机制(如文献[5]中多队列调度)时间复杂度为O(i)，可见，所提调度机制时间复杂度较小。

5 算法仿真分析

为检验动态优先级区分调度对两类消息的影响，仿真统计了不同事件触发型安全消息到达率的情况下，事件触发型安全消息和周期性安全消息的端到端时延，同时计算了周期性安全消息的调度公平系数。在长度为2 km的单向车道上，设置车节点速度为80～100km/h，考虑目前车节点通信范围为200～300 m,r取250 m，根据IEEE802.11p协议，信道容量设为6 Mbit/s。仿真场景为发生交通紧急事件后的单向车道，调度队列包括两类安全消息，EDSM和PSM的到达分别服从参数为λ1、λ2的泊松分布，则单个周期内，EDSM到达率为λ1，PSM到达率为λ2，设λ=0.8，λ1从0.02～0.1递增，在实际应用中，λ一般小于0.8。消息密度更低，消息在信道中的传播速率为198×106m/s，消息传输速率为6 Mbit/s。设置每个PSM和EDSM大小分别为256 B和512 B。队列总缓存为Bmax=50个安全消息，队列1可容纳的消息长度为总长度的10%。在λ1递增的情况下，分别统计对比FCFS调度，多队列调度和本文所提动态优先级调度(Dynamic Priority Schedule,DPS)的端到端时延和公平系数。

图2显示了不同调度机制下，EDSM端到端时延随到达率变化趋势。由图2可以看出，EDSM到达率越大，消息端到端平均时延越大。相对于FCFS调度和多队列调度，本文提出的调度机制的EDSM端到端时延总体处于1.5～1.8 ms之间，低于其他两类调度机制平均时延。EDSM到达率低于0.04时，队列1不抢占队列2调度过程，本文提出的调度机制平均时延在1.8 ms左右，时延增长比其他两种缓慢，当EDSM到达率高于0.04，队列1抢占队列2调度过程，EDSM端到端平均时延降低至1.5 ms。采取部分抢占调度时，本文所提调度机制平均时延随EDSM到达率继续增长，但始终低于其他两种调度机制。以EDSM到达率为0.06为例，本文所提调度机制时延比FCFS调度降低1.3 ms，比多队列调度机制平均时延降低0.9 ms，保证了队列1重载时EDSM的低时延传播。

图2 EDSM端到端时延随到达率变化趋势Fig.2 End-to-end delay of EDSM over the arrival rate

图3显示了不同调度机制下，PSM端到端时延随其到达率变化趋势。由图3可以看出，PSM到达率越大，消息的端到端时延越大。相对于FCFS调度和多队列调度，本文所提出的调度机制时延处于3.6～4.3 ms之间，总体低于其他两种调度机制时延，且增长幅度较其他两类调度更为缓慢。当PSM到达率低于0.74，即EDSM到达率高于0.06，队列1抢占队列2的调度过程，PSM的时延增长幅度变大，但由于抢占结束阈值的设置，增长幅度并未上升过多且仍然低于FCFS和多队列调度平均时延。以PSM到达率为0.74为例，此时，本文所提调度机制平均时延为4.15 ms，比FCFS调度时延低0.8 ms，比多队列调度时延低1.75 ms，因此本文所提的调度机制可以在保证EDSM低时延传播的前提下避免PSM等待时间过长。

图3 PSM端到端时延随到达率变化趋势Fig.3 End-to-end delay of PSM over the arrival rate

图4依据定义的公平性对PSM进行了估计。由图4可以看出，随着EDSM到达率增加，3类调度机制中PSM的公平系数均降低，但本文所提调度机制PSM公平系数处于0.77～0.8之间，明显高于FCFS调度和多队列调度。在EDSM到达率高于0.04时，由于队列2的调度过程被抢占，公平系数降低幅度增加，但仍高于FCFS调度和多队列调度，所以，本文所提的调度策机制能在保证EDSM性能的前提下并未过多牺牲PSM的公平性。

图4 公平系数随EDSM到达率变化趋势Fig.4 Fairness over the EDSM arrival rate

综上所述，本文所提调度机制具有低时延、高公平性的优势，可以在EDSM重载时保证低时延传播，同时避免PSM等待时间过长。

6 结束语

传统调度算法应用于车联网环境中不能根据队列状态对不同类别的消息调度方式进行调整，导致较大端到端传播时延。本文利用两类交通安全消息性能互补的特性，提出了适用于车联网下基于交通安全消息区分业务的动态优先级调度机制以提高调度的有效性和公平性，减小了端到端时延。所提调度机制在交通事故发生之后，车节点在时隙内将接收交通安全消息按类别进入两个队列，检测队列长度，设置抢占阈值，实现动态自适应调度。仿真结果表明，所提调度机制可以在EDSM队列重载时有效减缓其端到端时延的增长，同时并未过多降低PSM的公平性。

在实际应用中，车节点可以根据队列状态切换调度规则，但在双向车道情况下，车节点如何独立选择合适调度规则需要进一步讨论。

[1] 孙健,李宏智,郭灵波,等. VANET中一种安全消息拥塞控制机制[J].通信学报,2014,35(5):134-140. SUN Jian，LI Hongzhi，GUO Lingbo，et al. Congestion control mechanism in VANET for safety messaging[J].Journal on Communications,2014,35(5):134-140.(in Chinese)

[2] 罗涛,李俊涛,刘瑞娜,等. VANET中安全信息的快速可靠广播路由算法[J].计算机学报,2015,38(3):663-672. LUO Tao,LI Juntao,LIU Ruina,et al. A fast and reliable broadcast routing algorithm for safety related information in VANET[J].Chinese Journal of Computers,2015,38(3):663-672.(in Chinese)

[3] NASSER N,KARIM L,TALEB T. Dynamic multilevel priority packet scheduling scheme for wireless sensor network[J].IEEE Transactions on Wireless Communications,2013,12(4):1448-1459.

[4] NG S C,ZHANG W,ZHANG Y,et al. Analysis of access and connectivity probabilities in vehicular relay networks[J].IEEE Journal on Selected Areas in Communications,2011,29(1):140-150.

[5] ZHANG R,CHENG X,YANG L,et al. A novel centralized TDMA-based scheduling protocol for vehicular networks[J].IEEE Transactions on Intelligent Transportation Systems,2015,16(1):411-416.

[6] 李亚军,王全宝,董亚光,等. 基于TD-LTE系统的无线资源调度策略分析与实现[J].电讯技术,2012,52(11):1711-1714. LI Yajun,WANG Baoquan,DONG Yaguang,et al. Analysis and implementation of radio resource scheduling in TD-LTE system[J].Telecommunication Engineering,2012,52(11):1711-1714.(in Chinese)

[7] OMAR R,HASSAN A,ZHUANG W H,et al. A TDMA-based MAC protocol for reliable broadcast in VANETs[J].IEEE Transactions on Mobile Computing,2013,12(9):1724-1736.

[8] HAFEEZ K A,ZHAO L,MARK J W,et al. Distributed multichannel and mobility-aware cluster-based MAC protocol for vehicular ad hoc networks[J].IEEE Transactions on Vehicular Technology,2013,62(8):3886-3902.

[9] 邵苏杰,郭少勇,邱雪松,等. 基于加权队列的无线智能电网通信网采集数据流量调度算法[J].电子与信息学报,2014,36(5):1209-1214.

SHAO Sujie,GUO Shaoyong,QIU Xuesong,et al. Traffic scheduling algorithm based on weighted queue for meter data collection in wireless smart grid communication network[J].Journal of Electronics and Information Technology,2014,36(5):1209-1214.(in Chinese)

[10] 刘纯尧,张立臣. 信息物理融合系统的动态多优先级调度[J].计算机科学,2015,42(1):28-32. LIU Chunyao,ZHANG Lichen. Dynamic multi-priority scheduling for cyber-physical systems[J].Computer Science,2015,42(1):28-32.(in Chinese)

[11] 李建东. 通信网络基础[M].北京：高等教育出版社,2011.

[12] 闫军. 提高无线mesh网服务质量的队列管理和调度研究[D].长沙：中南大学,2010. YAN Jun. Research on imporving the queue management and schedule of QoS for WMN[D].Changsha:Central South University,2010.(in Chinese)

[13] 孙健. 车辆自组织网络中安全消息的优先级调度和拥塞控制[D].西安:西安电子科技大学,2012. SUN Jian. Priority schedule and congestion control mechanism in VANET for safety messages[D].Xi′an:Xidian University,2012.(in Chinese)

Dynamic Priority Scheduling of Traffic Safety Messages in Internet of Vehicles

ZHOU Yongzheng,QIU Gongan,QIU Yongfang
(School of Electronics and Information,Nantong University,Nantong 226019,China)

In Internet of Vehicles,two categories of traffic safety messages share the limited control channel bandwidth,so the performance of disseminating event-driven safety messages can not be guaranteed in emergency,which will lead to the failure of traffic accidents warning. The differentiated disseminated performance of traffic safety messages based on dynamic priority scheduling mechanism is proposed. The mechanism manages the two queues according to the event priorities,gives high priority to the event-driven safety messages and sets a scheduling threshold for the high priority messages dynamic scheduling. That is to conduct the preemptive priority scheduling when the queue length is over the threshold. When the queue length is less than half of the threshold,the preemptive scheduling terminates and then the non-preemptive priority scheduling is recovered. Simulation shows that the proposed dynamic priority scheduling mechanism of event-driven safety messages can reduce the end-to-end delay about 1.3 ms,and the fairness of the periodic safety messages increases about 0.22.

Internet of Vehicles；traffic safety message;periodic safety message；event-driven safety messages；differentiated scheduling；dynamic priority

2016-06-03；

2016-08-10 Received date:2016-06-03；Revised date：2016-08-10

国家自然科学基金资助项目( 61371113) ; 交通运输部应用基础研究项目(2013319825110);南通大学研究生科技创新计划项目(YKC15015)

10.3969/j.issn.1001-893x.2017.02.002

周永筝，邱恭安，邱永芳.车联网中交通安全消息动态优先调度机制[J].电讯技术，2017,57(2):132-138.[ZHOU Yongzheng,QIU Gongan,QIU Yongfang.Dynamic priority scheduling of traffic safety messages in internet of vehicles[J].Telecommunication Engineering,2017,57(2):132-138.]

TN92

A

1001-893X(2017)02-0132-07

周永筝(1992—)，女，江苏如皋人，硕士研究生，主要研究方向为车联网中的安全消息快速传播；

Email:yolandazyz@sina.com

邱恭安(1973—)，男，湖北浠水人，博士，副教授，主要研究方向为认知车载网络理论与技术；

Email:qiugongan@ntu.edu.cn

邱永芳(1991—)，女，江苏宿迁人，硕士研究生，主要研究方向为基于LTE的车联网资源调度。

*通信作者：qiugongan@ntu.edu.cn Corresponding author：qiugongan@ntu.edu.cn