多信道车载网中基于时分多址的MAC改进算法*

张栋梁，曲 豪，海本斋

(1.河南广播电视大学 信息工程学院，郑州 450008；2.河南师范大学 计算机与信息工程学院，河南 新乡 453007)

多信道车载网中基于时分多址的MAC改进算法*

张栋梁1，曲 豪*1，海本斋2

(1.河南广播电视大学 信息工程学院，郑州 450008；2.河南师范大学 计算机与信息工程学院，河南 新乡 453007)

车载网(VANETs)需提供时延敏感的安全应用和非安全应用的通信服务。这就使得媒体接入控制(MAC)协议既要满足安全消息的时延和可靠率，又要保证非安全消息的服务信道利用率，给MAC的设计提出了挑战。为此，提出基于时分多址的MAC改进算法(I-TDMA-MAC)。I-TDMA-MAC算法在每个同步帧内给每辆车分配两个子时隙，旨在提高无碰撞信道接入率和安全消息的传递率。同时，对空闲时隙采取重分配策略，并基于最短作业优先准则(SJF)给空闲时隙设置优先级，旨在提高服务信道利用率。仿真结果表明，提出的I-TDMA-MAC算法的安全消息传递率高达99%，当车流密度到达100 vehicle/km时，服务信道利用率接近于90%。

车载网；IEEE 1609 标准；时分多址；媒体接入控制；时隙分配

1 引 言

车载网(Vehicular Ad-Hoc Networks,VANETs)是智能交通系统(Intelligent Transportation System,ITS)的重要组成部分。VANETs为车间通信(Vehicle-to-Vehicle,V2V)和车与路边设施通信(Vehicle-to-Roadside,V2R)提供了平台[-2]。通过VANETs，车与车之间或车与路边设施间交互信息，可提高交通安全和交通管理效率。这些交互的信息可分实时安全消息和非安全消息，如事故预警消息、道路拥塞消息等[3-4]。

VANETs是基于IEEE 1609.4标准，支持专用短程距离通信(Dedicated Short Range Communication,DSRC)[5]。FCC为VANETs划分5.9 GHz的频谱，并划分了7个信道，用于安全消息和非安全消息的传输。这7个信道由1个控制信道(Control CHannel,CCH)和6个服务信道(Service CHannel,SCHs)组成，前者用于安全消息的传输，而后者一般用于非安全消息的传输。

然而，尽管给安全消息分配了1个专用的CCH，但是安全消息的突发性导致需要在CCH和SCH间快速地切换，这给安全消息的传输提出了挑战。而IEEE 802.11p的当前标准并不支持在高车流密度环境下的安全和非安全应用，也无法满足在多信道结构下非安全应用的高信道利用率[6-8]。

为了提高多信道利用率，文献[9]提出基于簇化的多信道MAC算法TC-MAC。与IEEE 1609.4标准结构不同，TC-MAC中每一帧并不是由两个CCH和SCH组成。换而言之，每一帧均有固定时长的时隙，且为50 ms。车辆可依据需求切入CCH或SCH。实验数据表明，TC-MAC协议的性能优于IEEE 1609.4标准。然而，TC-MAC协议仍存在一些不足:在低车流密度环境下，TC-MAC协议丢失大量的安全消息，而在高车流密度环境下，SCH信道利用率低。文献[10]提出了基于分簇多信道车载网MAC协议CM_MAC。在CM_MAC中，簇内和簇间通信采用不同的机制，前者采用非竞争的TDMA机制，而后者使用基于竞争的CSMA/CA机制。然而，基于竞争的CSMA/CA机制并不能有效地支持时延敏感的安全应用，也难以为吞吐量敏感服务提供保障。

由于VANETs网络中的车辆分布密度动态变化较大，基于竞争的CSMA/CA机制难以保证在高密度区域的性能。当多辆车同时接入信道，必然会引起冲突和导致信道拥塞。即使在车辆分布密度较低的情况，多数消息就非安全应用，CCH时隙的安全信道使用较少，SCH时隙的服务信道频繁使用，导致50 ms长的SCH时隙难以满足要求。显然，这种固定时隙的方案存在不足。因此，需要设置一种可变的、动态切换机制，以满足VANETs对安全应用和非安全应用的要求。

为此，本文以多信道车载网络为背景，以时分接入(Time Division Multiple Access,TDMA)为基础，提出基于改进的时分接入的MAC协议，记为I-TDMA-MAC协议。在I-TDMA-MAC协议中，每个移动车辆使用单一无线电接口，它能够在CCH和SCH间切换。I-TDMA-MAC协议采用了两个策略：首先，引用自适应双-子时隙分配策略，给每辆分配两个子时隙，旨在提高无碰撞信道接入和增强时延敏感的安全消息传输的可靠性;然后，采用空闲时隙重分配的策略，提高服务信道SCH的利用率。

2 网络模型及问题描述

媒体接入控制协议(Medium Access Control,MAC)为VANETs的安全应用提供有效的、可靠广播服务[11-13]。然而，VANETs的拓扑结构动态变化、车辆的快速移动给MAC的设计提出了挑战。例如：当车辆行驶速度为100 km/h、车辆通信半径为250 m时，只有57%通信链路可以维持15 s。

而VANET中的V2V和V2R通信采用专用短距离通信DSRC标准，通信半径一般在300 m之内。DSRC频谱被划分为7个信道，一个控制信道CCH和6个服务信道SCHs，如图1所示。CCH间隔和SCH间隔均为50 ms,而CCH和SCH间的保护间隔为4 ms，并且在每组10 MHz带宽上的速率可达27 Mbit/s。

在当前的VANET场景中，通信信道面临信道拥塞问题，这直接影响了安全应用的性能。现在多数安全应用消息产生频率为10 Hz。当车辆数较多时，网络内将产生大量的安全消息，这将耗尽信道容量，最终会引起安全消息碰撞[11]。因此，如果信道已经拥塞，若仍继续传输安全消息，这将导致大的传输时延，甚至丢失安全消息。为此，必须保证信道处于最小拥塞状态。

图1 DSRC 频谱模型

本文针对信道拥塞问题，提出多信道接入策略，给安全消息分配足够的带宽资源，使得安全消息传输时延满足要求。同时，采用空闲时隙重分配策略，提高SCH信道利用率。

3 I-TDMA-MAC算法

与固定的时隙接入机制不同，I-TDMA-MAC协议采用自适应时隙分配策略[16]。具体而言，先自适应分配子时隙，然后对于空闲时隙进行重分配，进而提高时隙利用率。

3.1 自适应双-子时隙分配

为了提高传输安全消息的可靠性，I-TDMA-MAC算法首先给每辆车分配两个连续CCH时隙内的两个子时隙，即自适应双-子时隙分配。I-TDMA-MAC算法引用了簇群概念，并由簇头实施自适应双-子时隙分配。分配的流程如下：

Step 1 Fori=0 toNdo

Step 2K=IDi%(2NSCH)

Step3Forj=1to2do

Step4If(j=1ANDK

Step5minSlot[j]=(IDi+NSCH)%(2NSCH)

Step6else

Step7minSlot[j]=IDi%(2NSCH)

Step 8 end if

Step 9 Ifj==1 then

Step 10M[j]=IDi/(2NSCH)

Step 11 else

Step 12 IfK

Step 13M[j]=(IDi-K+2NSCH-1)/(2NSCH)

Step 14 else

Step 15M[j]=(IDi-K+3NSCH-1)/(2NSCH)

Step 16 end if

Step 17 end if

Step 18L=⎣M[j]」+0.5

Step 19 If(j==1 ANDM[j]

Step 20CSlot[j]=(2×⎣M[j]」-NSCH/2-1)%(⎣Nmax/NSCH」)

Step 21 else

Step 22CSlot[j]=(2×⎣M[j]」+1-NSCH/2-1)%(⎣Nmax/NSCH」)

Step 23 end if

Step 24 end for

Step 25 SCHChannel=IDi%NSCH

Step 26 SCHSlot=⎣IDi/NSCH」

Step 27 end for

假定网络内所有车辆已划分不同的簇群，每个簇内有一个簇头CH。簇头给簇内车辆分配不同时隙。假定簇内每个车辆都具有一个ID号，从0～N-1。对于车辆υi，其ID号表示为IDi。NSCH表示服务信道数。首先计算因子K,定义如式(1)所示:

K=IDi%(2NSCH)。

(1)

假定给车辆υi分配的两个子时隙分别表示为minSlot[1]、minSlot[2]。为了保证这两个子时隙不冲突，需使得每辆车的两个子时隙不同，分配过程如Step 4～Step 7。

分配了两个子时隙后，需要计算这两个子时隙所在的两个信道时隙CSlotx，其中x=0,1,2,…,⎣Nmax/NSCH」,Nmax表示一个簇内具有的最多车辆数，⎣·」表示向下取整数。

在每个时隙CSlotx内，分配12个子时隙minSlotm，其中m=0,1,2,…,11。所分配的两个子信道时隙是连续的，分配过程如Step 9～Step 23。

最后，给车辆分配服务信道和服务信道时隙[15]。所谓服务信道分配就是从NSCH中选择一个信道，用于车辆使用。而每个服务信道Nmax/NSCH个时隙SCHSloty，y=0,1,2,…,⎣Nmax/NSCH」。对于车辆υi，它所分配的服务信道、服务信道时隙分别如式(2)、(3)所示：

SCHCi=IDi%NSCH，

(2)

SCHSloti=⎣IDi/NSCH」。

(3)

为了更好地理解时隙分配过程，举例说明。如图2所示，NSCH=6，某车辆其ID=0，它所分配的两个子时隙为

minSlot[1]=(IDi+NSCH)%(2NSCH)=6,

minSlot[2]=IDi%(2NSCH)=0。

相对应地，这两个子时隙所对应的信道时隙分别为

CSlot[1]=(2×⎣M[1]」-NSCH/2-1)%(⎣Nmax/NSCH」)=23,

CSlot[2]=(2×⎣M[2]」-NSCH/2-1)%(⎣Nmax/NSCH」)=24。

此外，所分配的服务信道以及时隙分别为SCHCi=IDi%NSCH=0、SCHSloti=⎣IDi/NSCH」=0。

图2 时隙分配过程示例

3.2 空闲时隙的重分配

在I-TDMA-MAC算法中，车辆通过CCH信道的子时隙所携带的状态信息，分析其他车辆状态。如果某车辆在其SCH时隙内并没有任何非安全消息传输，它就将它自己标为空闲状态，并告知其他车辆。反之，若它有多个非安全消息需要传输，它就与其他具有空闲时隙的车辆协商。

那些使用偶数时隙的车辆只能使用偶数的空闲时隙。采用两个循环周期实现空闲时隙重分配[16]。如图3所示，假定有3辆车X、Y、Z均采用了偶数时隙，所分配的时隙分别为2、4、0。在第一个循环周期中，车辆X、Y有多个数据包需要传输，因此它需要多个时隙。因此，它们向邻居节点广播请求时隙消息。而由于车辆Z没有非安全消息，因此所分配给它的时隙是空闲的，未使用。这个时隙可分配车辆X或Y使用。

当车辆Z收到来自X、Y的请求消息后，需要决策是将自己的空闲时隙分配给X还是Y使用。车辆Z依据最短作业优先准则(Shortest Job First,SJF)进行决策，优先选择ID号小的车辆使用空闲时隙。由于X的ID号小于Y，因此X可优先使用Z的空闲时隙。

图3 空闲时隙重分配过程

4 性能仿真

4.1 仿真参数及性能指标

引用NS3[17]网络仿真器建立仿真平台，并利用智能驾驶模型(Intelligent Driver Model,IDM)模拟车辆移动。仿真参数如表1所示，仿真时间为100 s。每次实验独立重复50次，取平均值作为最终的仿真数据。

表1 仿真参数

此外，为了更好地分析I-TDMA-MAC协议的性能，选择IEEE 1609.4 WAVE[18]、TC-MAC协议作比较。同时选择数据包传递率、平均端到端传输时延以及信道利用率作为性能指标。

4.2 数据包传递率

图4显示了3个协议的数据包传递率随车流密度的变化情况。每辆车随机产生安全数据包，且产生率为10 packet/s。从图4可知，随着车流密度的增加，TC-MAC协议的数据包传递率随之增加，当车流密度达到140 vehicle/km，其数据包传递率接近于95%，逼近于I-TDMA-MAC协议。而在整个车流密度的变化期间，I-TDMA-MAC协议都具有高数据包传递率，接近于100%。这主要是因为I-TDMA-MAC协议在两个连续的CCH时隙内选择两个子时隙传输数据包，降低了接入信道的成功率，即使在高车流密度时，仍具有高的数据包传递率。相反，1609.4 WAVE在高车流密度时，丢失了大量的数据包，当车流密度达到140 vehicle/km，数据包传递率仅为30%。

图4 数据包传递率

4.3 平均端到端传输时延

本次实验主要考查3个协议传输安全消息所产生的端到端传输时延，实验数据如图5所示。从图5可知，在低车流密度时，TC-MAC协议的端到端平均时延高于I-TDMA-MAC协议。原因在于：I-TDMA-MAC协议给每辆车分配了两个子时隙传输安全消息，降低了接入信道时延，缩短了端到端传输时延。

图5 端到端传输时延

4.4 信道利用率

图6显示了6个服务信道的利用率。从图6可知，IEEE 1609.4 WAVE信道利用率非常低，即使在车流密度达到140 vehicle/km，利用率也低于50%。而TC-MAC协议的信道利用率也非常低，这主要是因为它没有充分利用空闲时隙，浪费了信道资源。相反，提出的I-TDMA-MAC协议采用了空闲时隙重分配策略，充分利用了信道资源。当车流密度达到100 vehicle/km时，利用率高达90%,而TC-MAC、IEEE 1609.4 WAVE协议的信道利用率分别为10%和21%。

图6 信道利用率

4.5 开销

为了比较I-TDMA-MAC、IEEE 1609.4 WAVE、TC-MAC协议的复杂度，分析它们的系统开销。系统开销越大，则协议越复杂。本文引用的系统开销是指网络内平均每个节点每秒所接收和发送的数据比特数。实验数据如图7所示。

图7 系统开销

从图7可知，I-TDMA-MAC的开销高于IEEE 1609.4 WAVE，原因在于：I-TDMA-MAC协议引用了空闲时隙重分配策略，增加了一定的系统开销，但是增加的幅度不大。换而言之，I-TDMA-MAC协议是以略高的系统开销换取低的端到端传输时延(如图5所示)和高信道利用率(如图7所示)。

通过实验数据可知，提出的I-TDMA-MAC协议有效地提高了信道利用率，并增加了数据包传输成功率。当然，I-TDMA-MAC协议增加了一定的系统开销，但只是略高于IEEE 1609.4 WAVE协议，即I-TDMA-MAC协议并没有以牺牲高的系统开销换取高的信道利用率和数据包传输率。在VANETs网络中，可使用I-TDMA-MAC协议。换而言之，I-TDMA-MAC协议具有可实现性。

5 结 论

考虑到车载网的安全应用和非安全应用对消息传输的要求，本文提出了基于TDMA的MAC改进算法I-TDMA-MAC。I-TDMA-MAC协议兼顾了安全消息传输的时延和可靠性以及服务信道的利用率。I-TDMA-MAC协议给每辆车分配两个子时隙，提高安全消息传输性能，同时，对空闲时隙进行重分配，提高了服务信道的利用率。仿真结果表明，与TC-MAC相比，提出I-TDMA-MAC协议的数据包传递率提高至99%，服务信道利用率提高至90%。

[1] RAJ C,UPADHAYAYA U,MAKWANA T,et al.Simulation of VANETS using NS-3 and SUMO[J].Advanced Computing Science Software Engineering,2014,4(2):563-569.

[2] GORRIERI A,FERRARI G. Irresponsible AODV routing[J].Vehicular Communications,2015,3(2):47-57.

[3] LOCHERT C. A routing strategy for vehicular ad hoc networks in city environments[C]//Proceedings of 2013 IEEE Intelligent Vehicular Symposim.Gold Coast,Australia:IEEE,2013:156-161.

[4] 江帆，卢光跃. 认知无线网络中基于业务区分的自适应MAC协议[J].电讯技术，2013,53(7):878-884. JIANG Fan,LU Guangyue. A service-differentiated based adaptive MAC protocol for cognitive radio networks[J].Telecommunication Engineering,2013,53(7):878-884.(in Chinese)

[5] KENNEY J B. Dedicated short-range communications standards in the united states[J].Proceedings of the IEEE,2011,99(7):1162-1182.

[6] WANG Q,LENG S,FU H,et al. An IEEE 802.11p-based multichannel coordination for vehicular ad hoc networks[J].IEEE Transactions on Intelligent Transportation Systems,2012,13(2):449-458.

[7] HAN C,DIANATI M,TAFAZOLLI R. A novel distributed asynchronous multichannel MAC scheme for large-scale vehicular ad hoc networks[J].IEEE Transactions on Vehicular Technology,2012,61(7):3125-3138.

[8] ALMALAG M S,OLARIU S,WEIGLE M.TDMA-cluster-based MAC for VANETs[C]//Proceedings of 2015 IEEE International Symposium on a World of Wireless,Mobile and Multimedia Network(WoWMoM 2015).Boston,Massachusetts,USA:IEEE,2015:1-6.

[9] ALAMAG M S,OLARIU S,WEIGLE M.A modified TC-MAC protocol for multi-hop cluster communications in VANETs[C]//Proceedings of 2013 International Conference on Connected Vehicles.Las Vegas,Nevada:IEEE,2013:832-837.

[10] 何鹏，阎保平，李志，等.CM-MAC:一种基于分簇的多信道车载网MAC协议[J].计算机研究与发展，2014，51(3):502-510. HE Peng,YAN Baoping,LI Zhi,et al.CM-MAC:a cluster-based multi-channel MAC Protocol for VANET[J].Journal of Computer Research and Development,2014，51(3):502-510.(in Chinese)

[11] SHAHIN N,KIM Y T.An enhanced TDMA cluster-based MAC for multichannel vehicular networks[C]//Proceedings of 2016 International Conference on Selected topics in Mobile and Wireless Networking.[S.l.]:IEEE,2016:34-42.

[12] 张伟龙，吕娜，杜思深. 应用于航空Ad Hoc网络的高负载优先级均衡MAC协议[J].电讯技术，2014,54(4):656-661. ZHANG Weilong,LYU Na,DU Sishen. A balancing priority MAC protocol under high load for aviation Ad Hoc network[J].Telecommunication Engineering,2014,54(4):656-661.(in Chinese)

[13] ZHANG H L,QIANG Z. A novel road topology-aware routing in VANETs[C]//Proceedings of 2014 Asia-Pacific Web Conference.New York:Springer,2014:167-176.

[14] AKAMATSU R. Adaptive delay-based geocast protocol for data dissemination in urban VANET[C]//Proceedings of 2014 Seventh International Conference on Mobile Computing and Ubiquitous Network.Singapore:IEEE,2014:43-51.

[15] NADEMBEGA A,HAFID A,TALEB T. Mobility prediction-aware bandwidth reservation scheme for mobile networks[J].IEEE Transactions on Vehicle Technology,2015,64(6):2561-2576.

[16] LI H,CHENG Y,ZHOU C,et al. Routing metrics for minimizing end-to-end delay in multiradio multichannel wireless networks[J].IEEE Transactions on Parallel Distributed Systems,2013,24(11):2293-2303.

[17] KIM B,LEE D,CHOI T. Performance evaluation for Modbus/TCP using Network Simulator NS3[C]//Proceedings of 2015 IEEE Region 10 Conference(TENCON 2015).Dhaka,Bangladesh:IEEE,2015:1-6.

[18] CAMPOLO C,MOLINARO A.IEEE 1609.4 wireless access in vehicular environments-multichannel operation[J].IEEE Communications Magazine,2013(5):158-169.

An Improved TDMA-based MAC Algorithm for Multichannel VANETs

ZHANG Dongliang1,QU Hao1,HAI Benzhai2

(1.Department of Information Engineering,Henan Radio & Television University,Zhengzhou 450008,China; 2.Department of Computer and Information Engineering,Henan Normal University,Xinxiang 453007,China)

The Vehicular Ad-Hoc Networks(VANETs) provide communication services for time-critical road safety applications and non-safety applications. The challenges of multichannel VANETs Medium Access Control(MAC) protocol include successful delivery of time-critical safety messages and high reliability,and high channel utilization for non-safety messages. Therefore,an improved time division multiple access-based MAC(I-TDMA-MAC) is proposed in this paper. In I-TDMA-MAC,the two mini-slots in synchronous frame interval are allocated to each vehicle to increase the collision-free channel access ratio and reliable time-critical safety message deliveries. At the same time,empty slots are reallocated to enhance bandwidth utilization of service channels,and the Shortest Job First(SJF) algorithm is used to give the prioritization to allocate the empty slots. The simulation results show that the packet delivery ratio of safety messages is enhanced as high as 99%,and the bandwidth utilization of service channels is up to 90% when traffic density is more than 100 vehicle/km.

vehicular ad-hoc network(VANET);IEEE 1609 standard;time division multiple access(TDMA);medium access control(MAC);time slot allocation

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

张栋梁，曲豪，海本斋.多信道车载网中基于时分多址的MAC改进算法[J].电讯技术，2017,57(4):463-468.[ZHANG Dongliang,QU Hao,HAI Benzhai.An improved TDMA-based MAC algorithm for multichannel VANETs[J].Telecommunication Engineering,2017,57(4):463-468.]

2016-07-02；

2016-11-29 Received date:2016-07-02；Revised date：2016-11-29

国家自然科学基金资助项目(1404602);河南省高等学校重点科研项目(15B520006);河南省科技厅2017年科技攻关项目(172102210564)；国家开放大学2014年研究课题(G14A2402Y)；河南省教育厅2015年重点研究项目(15A520060)

TN929.5

A

1001-893X(2017)04-0463-06

张栋梁(1982—)，男，河南洛阳人，硕士，讲师，主要研究方向为低能耗网络、多跳协议、信号传输制式等；

曲 豪(1975—)，男，河南唐河人，硕士，讲师，主要研究方向为低能耗网络；

Email:Z1897865@qq.com

海本斋(1980—)，男(回族)，河南新乡人，副教授，主要研究方向为计算机网络、复杂系统建模。

*通信作者：Z1897865@qq.com Corresponding author：Z1897865@qq.com