基于图着色理论的异构车联网时隙分配方案①

张鹏涛 周一青 刘 航 田 霖 石晶林

(*重庆邮电大学通信与信息工程学院 重庆 400065) (**中国科学院计算技术研究所移动计算与新型终端北京市重点实验室 北京 100190)



基于图着色理论的异构车联网时隙分配方案①

张鹏涛②*周一青**刘 航**田 霖**石晶林**

(*重庆邮电大学通信与信息工程学院 重庆 400065) (**中国科学院计算技术研究所移动计算与新型终端北京市重点实验室 北京 100190)

针对异构车联网系统车辆较多导致时隙分配困难的问题，提出了一种基于图着色理论的时隙分配方案。该方案以考虑两跳内节点的图为模型，通过图着色的方法分配时隙，有效降低了隐藏终端带来的丢包；另外给出了一种高效实用的时隙重用分配算法。该算法根据度定义权值以确定车辆分配时隙数目，保证了公平性，提高了时隙重用，进而提高了消息发送的可靠性，同时也适用于网络拓扑多变的车联网场景。仿真结果表明，在车辆数为200、时隙数为100时，与传统时隙分配方法相比，该方案的车辆平均收包率获得大幅提升。此外，随着时隙重用的增加，车辆间干扰增强，从而导致平均收包率降低。研究还发现，增加车辆发射功率时，由于接收端信干噪比先增加后趋于不变，所以平均收包率也先增加后趋于不变。

异构车联网， 图着色， 时隙重用， 发射功率， 收包率

0 引 言

道路交通事故已成为全球第二大致人死亡因素。随着道路上汽车的日益增多，道路状况日趋复杂，道路安全形势不容乐观。车联网系统的应用，能够显著降低交通事故率。奔驰公司的研究表明，车联网可通过车-车直接信息交互有效进行危险预警，避免60%以上的事故。因而，车联网系统得到了广泛关注。同时，安全类应用的低时延和高可靠性也对车联网系统提出了极大的挑战。

目前应用较为广泛的车联网协议是专用短程通信(dedicated short rage communication，DSRC)协议,也称无线接入车载环境(wireless access vehicular environment, WAVE)协议[1,2]。它继承于802.11协议家族，采用CSMA/CA载波侦听多路访问/冲突避免的接入方式，方法简单且成熟，适用于网络拓扑多变的车辆通信场景。另外，它采用车车直接通信的方式，使得通信时延缩短，有效保证了安全类应用的要求。在美国，联邦通信委员会(FCC)专门为该协议分配了75MHz的带宽资源。但该协议也存在明显的不足。由于采用竞争接入信道机制，缺乏有效的集中调度，在车辆数目较多时信道拥塞严重，信道利用率低。此外，该协议对于多播类消息支持较差。由于缺乏ACK和重传机制信令设计，隐藏终端问题难以避免，同时多播类消息冲突严重。然而，值得注意的是，在车联网系统中，大多数安全类消息都是多播类消息。文献[3]的研究发现，在车辆密度较大的场景下，很多车辆发包会产生冲突，从而导致系统吞吐量下降，接入时延增大。车辆数目大于50时，时延将远大于100ms，无法满足安全类消息的需求。

在公共无线通信方面，随着蜂窝移动通信的迅速发展[4-7]而提出的高效可靠的通信技术，有望与车联网需求结合，大幅提升车联网性能[8]。其中3GPP的长期演进(LTE)协议获得广泛支持，LTE商用网络已经在全球广泛部署。LTE采用集中式控制架构，具有带宽灵活配置，支持高速运动等特点。但是LTE协议目前不支持车车直接通信，所用数据都需要经过基站转发，系统时延明显增大。文献[3]评估了LTE协议应用于车联网的性能。在车辆较少时，LTE网络可以满足车联网众多应用的要求，且性能优于DSRC，但当车辆增多时，很多应用的时延和可靠性都无法得到保障。为了综合利用DSRC和LTE的优势，文献[9-14]提出了融合DSRC和LTE的双层异构车联网架构。其中基于时分多址接入(TDMA)的异构车联网架构通过LTE蜂窝网集中控制车辆接入DSRC的时隙，采用DSRC无线资源进行车车直接通信。这样既避免了CSMA/CA接入方式导致的信道拥塞，同时也保留了低时延的车车通信方式，降低了系统时延。然而，目前针对该系统的许多研究还不足，车辆接入机制设计和资源分配方案研究都亟待展开[12]。其中，文献[15]以最大化长期奖励为目标针对车辆云计算系统提出了一种最优计算资源的分配方案。针对时隙资源的分配方案研究不多，在系统车辆数目较多时，传统无重用地为所有车辆分配不同时隙的方法会导致时隙不足的情况。本文针对这种情况研究异构车联网时隙接入管理机制，给出基于图着色理论的时隙分配方案，提高资源利用率，提升系统性能。本文首先给出了基于TDMA的异构车联网系统模型，然后给出了时隙重用分配方案。该方案根据时隙重用范围构建两跳内节点的图模型，采用时隙分配算法确定车辆分配时隙数目，并通过图着色的方法为车辆分配时隙。最后，仿真验证了本文提出方案的有效性。仿真表明平均收包率将随着时隙重用率的升高而降低。随着发射功率的增加，收包率会相应增加，但当功率增大到一定程度后，收包率不再有明显的增加。

1 系统模型

考虑基站全覆盖的郊区公路为研究场景，本文关注基于TDMA的异构车联网通信系统[13]中周期安全类消息的传输。周期安全类消息为车联网安全应用中至关重要的应用，它由车辆周期产生并广播其状态信息(本文仅考虑车辆位置信息，假设车辆均安装GPS装置，可以准确定位自己的位置)给周围其他车辆来有效避免交通事故。广播周期[2]不能超过100ms，本文采用均分100ms的方式划分时隙。

如图1所示，异构车联网系统包括LTE和DSRC网络，其中LTE蜂窝网以高功率的基站为中心，覆盖范围较广，基站间可共享信息。车辆发射功率较低，车车通信距离较短，车车通信基于DSRC协议进行，采用TDMA多址接入。车辆采用直接接入和簇头转发接入LTE网络的方式分别完成与基站的初次通信与后续通信。由于初次通信只发生在基站开机和车辆初始进入基站覆盖区域两种情况下，而后续通信仅选取簇头接入LTE系统，所以该方法可以有效降低LTE系统负荷。基站根据车辆实时位置信息对车辆分簇，同时覆盖区域内车辆采用簇头转发的方式上报实时位置信息给基站，即上述两个过程相互依赖相互作用。

图1 异构车联网模型

下面分别介绍两个过程。初次或后续通信后，基站获得车辆位置信息后的分簇具体过程如下：首先，基站根据车辆行驶方向和地理位置信息可以将车辆分成不同方向不同车道的集合；然后，以基站覆盖道路的中心为中心，以DSRC传输距离[13]为覆盖范围，根据车辆位置信息，进一步将集合内车辆分成多个簇；最后，选取簇内接近中心位置(如果没有则选取接近簇内1/4和3/4地理位置)且信号较强的车辆作为簇头。本文以三个广播周期(300ms)作为簇的生命周期，虽然车辆移动速度较快，但同车道同方向车辆的相对速度较小，所以可以认为簇内车辆位置拓扑基本无变化。覆盖区域内车辆完成分簇后，其经簇头转发上报位置信息给基站的过程如下：簇中车辆根据分配的不同时隙接入DSRC网络，广播安全位置信息。图2为以簇头为中心，根据DSRC传输距离得到无线广播信道连续三个周期时序图。第N-1个广播周期(100ms)内，簇头通过DSRC网络收集得到簇内其他车辆位置信息。第N个广播周期开始到簇头发送时隙之间，簇头完成与基站的上下行通信。具体过程如下：簇头通过LTE蜂窝网上报收集获得的簇内车辆位置信息给基站。基站根据得到的车辆位置拓扑，集中控制确定第N+1个广播周期(100ms)每辆车接入DSRC网络的时隙和发送功率，并通过LTE蜂窝网发送给簇头。簇头在其广播时隙上通过DSRC网络，将时隙分配信息分发给簇内其他车辆。最后，簇内车辆在第N+1个广播周期内采用分配得到的时隙和发射功率，利用DSRC的无线资源广播安全位置信息。假设簇头通过LTE蜂窝网与基站的通信完全成功，且第N-1个广播周期内簇头收集和第N个广播周期内簇头分发控制信息过程也完全成功。

图2 无线广播信道时序图

本文主要关注时隙重用方案对周期安全消息进行车车通信性能的影响。车车通信的无线信道采用双折线衰落模型[16-18]。该模型假设在临界距离dc内，衰落指数为γ1，如果传播距离大于dc，衰落指数为γ2。因此，接收功率P可以表示如下：

P(d)=

(1)

m=-0.69ln(d)+4.929, m∈[0.5, 3.9]

(2)

表1 双折线衰落模型参数

由异构车联网模型可知，车辆发送安全消息时，是基于DSRC在不同的时隙发送。传统方法是正交地为所有车辆分配不同时隙，没有考虑重用，当车辆数目较大时，会导致许多车辆无法获得发送时隙。事实上，由于车车直接基于DSRC的传输距离较短，当时隙不足时，互相在一定距离外的车辆可以重用相同的时隙资源，有望大幅度提升时隙资源的利用率，让更多车辆获得接入时隙发送安全消息，从而提升行车安全。基于上述思想，本文研究了在给定时隙重用距离下的时隙重用分配方案。

2 时隙分配方案

以顶点表示车辆，以边表示不能分配相同的时隙车辆对。研究区域中所有车辆可以构成顶点集合V，所有不能分配相同时隙的车辆对可以构成边集合E。顶点集和边集构成无向图G=(V,E)。以不同颜色代表不同时隙，可为车辆分配时隙的过程构建成图着色模型。

2.1 构建图着色模型

本小节以郊区公路为研究区域说明图着色模型。由系统模型可知，第N-1个广播周期内，簇头通过DSRC网络收集得到车辆的位置信息，然后通过LTE蜂窝网上行链路发送给基站。基站可以得到每100ms车辆的位置分布图(如图3)，其中车辆用圆圈表示，所关注的公路区域用虚线框表示。于是，所有车辆构成顶点集。

图3 车辆位置分布例图

在本文提出的可重用时隙机制下，基站分配时隙时，必须考虑到车辆会在分配的时隙内利用DSRC频带资源广播发送周期安全消息给周围车辆。为避免严重干扰，在时隙重用距离内的车辆采用不同的时隙接入DSRC网络。因此，相互在时隙重用距离内的车辆对加入边集合(图4中实线)。

图4 时隙重用单跳例图

如图4所示，对于相互不在时隙重用距离内的车辆(如1和4)，如果各自的重用范围存在相同的其他车辆(如2和3)，若1和4采用相同的时隙发送安全消息，会出现其他车辆不能正确接收它们的安全消息的问题，即隐藏终端问题。因此，为了降低由于隐藏终端导致的丢包，两跳连线的车辆节点也不能分配相同的时隙，于是也将两跳连线的车辆对加入边集合(图5中虚连线)。

图5 时隙重用两跳例图

最后，顶点集和所有边集构成无向图模型。以不同颜色代表不同时隙，那么为车辆分配时隙的过程与对图中节点着色的过程相同。基于图着色的方法为车辆分配时隙，得到的一种分配结果如图6所示。

由图6可知，在同一研究区域中，相距较远的不同车辆可以重用相同的时隙，但同时也会带来一定的相互干扰，干扰功率随着可重用距离的增加呈指数级数下降。此外，图着色问题存在最小颜色数，即最小所需时隙数目。当系统可提供的时隙数目小于车辆数目但大于最小所需时隙数时，时隙重用的方法可以有效保证所有车辆获得更多的接入时隙进行通信。当时隙数目小于最小所需时隙数目时，部分车辆会无法获得接入时隙发送安全消息。定义系统等效时隙总数为所有车辆时隙数目总和。因此，当系统正交时隙数目、网络拓扑确定后，需要研究时隙分配算法，在保证公平性的前提下，尽可能地为每辆车分配更多的时隙，增大系统等效时隙总数。

2.2 时隙分配算法

本小节在图着色模型的基础上研究时隙分配算法，以确定每辆车可分配的时隙数目。首先，本文基于无向图定义了车辆在分配时隙过程中的公平性，即车辆的地位与其处于无向图的位置密切相关。对于一个由n点构成的完全图，定义图中n个节点地位平等，即可以平等分配相同数量的时隙。对于非完全图，定义图中度较大的节点地位较低，即可分配的时隙数目较少。原因是度较大的节点多分得一个时隙，与该节点相连的更多节点少分配一个时隙。同时，基于公平性分配时隙也可以有效增加系统时隙重用(系统等效时隙总数更多)。另外，完全图中的所有节点相互之间均不能分配相同的时隙，而非完全图的节点包含于多个完全子图中。因此，本文根据节点的度定义了权值，量化了公平性，并分别以完全图或子图为分配集合，根据权值比例确定每种集合中车辆获得时隙的数目。最后，为保证所有分配集合不会出现接入时隙冲突，取其中最小值作为车辆分配的时隙数。

图7 时隙分配例图

系统可提供的正交时隙总数设为N，基于权值的时隙分配算法具体如下：

(1) 对于图中任意的节点n，其度为deg(n), 存储与该节点相连的所有节点得到节点集: Tn={m;m与n相连，m≠n}

(2) 对于图中任意节点n, 定义其权值为: imp(n)=1/(deg(n)+1)；

3 仿真及结果

以4车道郊区公路为仿真区域，车辆总数为200，车辆均匀分布，车辆间距分为25m和10m两种情况，对应公路长度分别为5km和2km。安全类消息大小为300Byte，采用BPSK调制，时隙总数为100，均分100ms，即每个时隙1ms,带宽为10M,载频为5.850GHz,考虑全向天线，天线高度1.5m，忽略速度影响[19]。系统整体仿真配置参数见表2。

表2 系统仿真配置

由系统模型可知，本文假设簇头与基站通过LTE蜂窝网的通信完全成功，且簇头收集车辆位置信息和分发控制信息的过程也完全成功。仿真采用简化的基于权值时隙分配算法确定车辆分配时隙数目，根据图着色模型随机选择接入时隙分配给车辆，时隙的优先级等同。车辆以给定的发射功率,在分配时隙上接入DSRC网络，并发送周期安全类包。经过无线信道后，计算在接收端的SINR。其中接收端的背景噪声为-104dBm[18]。如果SINR大于阈值[19]则认为接收成功，否则丢包。

仿真分别研究了车辆平均收包率随时隙重用范围的变化，系统等效时隙总数随时隙重用范围的变化情况，以及发射功率对平均收包率的影响。

图8所示为车辆发射功率为23dBm,统计范围为0～300m时，时隙重用距离与收包成功率的关系。由于研究区域中车辆总数为200，而正交时隙只有100个，当用传统方法为所有车辆分配不同时隙时，会导致许多车辆无法获得发送机会，在两种车辆间距下，平均收包率均接近0.5。但采用本文提出的时隙重用方案，平均收包率可以获得大幅度提升。重用距离越大，在相同时隙上发送安全消息的车辆相距越远，互干扰越低，平均收包率越高。但重用距离增大到一定程度时，会出现正交时隙数目小于最小所需时隙数目的情况，如图中车辆间距为10m，时隙重用范围大于400m时，会出现部分车辆无法获得接入时隙发送消息的情况，且随着重用距离的增加，无法分配获得时隙的车辆增多，从而平均收包率会降低。车辆间距为25m时，由于车辆密度较小，在最大重用范围600m时，最小所需时隙数目不会多于正交时隙数目，因此，车辆平均收包率没有下降。另外，车辆间距越小，网络拓扑越密集，车辆平均获取时隙数目较少，从而时隙分布越稀疏，互干扰越小，所以在重用距离较小时，车辆间距为10m的收包率要高于25m间距的收包率。

图8 平均收包率与重用距离的变化

系统等效时隙数目与重用距离的关系如图9所示。从图9看出，随着时隙重用距离的增加，系统等效时隙数目降低。车辆间距为10m时，由于车辆密度较大，网络拓扑图密集，车辆获取时隙数目较少，所以系统等效时隙数目少于车辆间距为25m的时隙数。车辆间距为10m，时隙重用距离为450m时，系统等效时隙总数低于车辆总数200，即出现部分车辆无法获得发送时隙的情况，与图8中正交时隙数目低于最小所需时隙数目的情况对应。车辆间距为25m时，车辆密度较小，网络拓扑稀疏，等效系统时隙总数多于车辆总数200，即不会出现车辆无法获得发送时隙的情况。

图9 系统等效时隙数目随重用距离的变化

图10所示为不同发射功率，统计范围为0～300m时，车辆间距为25m,时隙重用距离与平均收包率的关系。随着发射功率的增加，平均收包率会相应增加，但当增加到一定程度后，平均收包率不再有明显的增加。因为达到一定功率后，噪声相对于干扰已经可以忽略，车辆接收到信干噪比趋于不变，所以平均收包不再明显增加。

图10 不同发射功率，平均收包率随重用距离的变化

4 结 论

本文研究了融合DSRC协议和LTE协议优点形成的基于TDMA的异构车联网架构下安全消息的发送机制。在车辆数目较多时，传统的为所有车辆分配不同时隙的方法，会导致许多车辆无法获得发送机会，从而降低了消息发送的可靠性。本文基于图着色理论，提出了一种异构车联网时隙分配方案。该方案以两跳节点构建图模型，有效降低了隐藏终端带来的丢包，同时，提出了时隙分配算法，保证了车辆的公平性，提高了时隙重用，适用于网络拓扑多变的车联网场景。仿真表明，在传统方法分配时隙不足时，该方案保证了车辆获得足够的发送时隙，显著提高了周期安全类信息可靠性。此外，仿真还得到了平均收包率随着发射功率的增大而先升高后趋于不变的结论。

[1] Uzcategui R A, Marum G A. WAVE: a tutorial.IEEECommunicationsMagazine, 2012, 47(5): 126-133

[2] Karaginanis G, Altintas O, Ekici E, et al. Vehicular networking: A survey and tutorial on requirements, architectures, challenges, standards and solutions.IEEECommunicationSurveys&Tutorials, 2011, 13(4): 2036- 2040

[3] Mir Z H, Filali F. LTE and IEEE 802. 11p for vehicular networking: a performance evaluation.EURASIPJournalonWirelessCommunicationsandNetworking, 2014, 2014: 89

[4] Zhou Y, Liu H, Pan Z, et al. Spectral and energy efficient two-stage cooperative multicast for LTE-A and beyond.IEEEWirelessMagazine, 2014, 21(2): 34-41

[5] Liu L, Zhou Y Q, Tian L, et al. CPC-based backward compatible network access for LTE cognitive radio cellular networks.IEEECommunicationMagazine, 2015, 53(7): 93 -99

[6] Garcia V, Zhou Y Q, Shi J L. Coordinated multipoint transmission in dense cellular networks with user-centric adaptive clustering.IEEETransactionsonWirelessCommunication, 2014, 13(8):4297-4308

[7] Zhou Y Q, Liu H, Pan Z, et al. Two-stage cooperative multicast transmission with optimized power consumption and guaranteed coverage.IEEEJournalonSelectedAreasinCommunications, 2014, 32(2):274-284

[8] Liu H, Zhou Y Q, Tian L, et al. How can vehicular communication reduce rear-end collision probability on highway. In: Proceedings of the 2015 IEEE GLOBECOM, San Diego, USA, 2015. 1-6

[9] Yang Y, Wang P, Wang C, et al. An eMBMS based congestion control scheme in cellular-VANET heterogeneous networks. In: Proceedings of the 2014 IEEE 17th International Conference on Intelligent Transportation System, Qingdao, China, 2014. 1-5

[10] Rubin I, Baiocchi L Y Y A, Cuomo F, et al. Micro base station aided vehicular ad hoc networking. In: Proceedings of the 2014 International Conference on Computing, Networking and Communications, Honolulu, USA, 2014. 231-235

[11] Benslimane A, Taleb T, Sivaraj R. Dynamic clustering- based adaptive mobile gateway management in integrated VANET-3G heterogeneous wireless networks.SelectedAreasinCommunications, 2011, 29(3): 559-570

[12] Zheng K, Zheng Q, Xiang W, et al. Heterogenous vehicular networking: a survey on architecture, challenges, and sloutions.IEEECommunicationSurveys&Tutorials, 2015, 17(4): 2377-2396

[13] Taleb T, Benslimane A. Design guidelines for a network architecture integrating VANET with 3G & beyond networks. In: Proceedings of the 2010 IEEE Global Telecommunications Conference, Miami, USA, 2010. 1-5

[14] Zhou W, Ren C, Ma C, et al. Multicast/broadcast service in integrated VANET-cellular heterogeneous wireless networks. In: Proceedings of the 2013 International Conference on Wireless Communications & Signal Processing, Hangzhou, China, 2013. 1-6

[15] Zheng K, Meng H, Lei L, et al. An SMDP-based resource allocation in vehicular cloud computing systems.IEEETransactionsonIndustrialElectronics, 2015, 62(12): 7920- 7928

[16] Cheng L, Henty B E, Stancil D D, et al. Mobile vehicle- to-vehicle narrow-band channel measurement and characterization of the 5.9 GHz dedicated short rage communication (DSRC) frequency band.IEEEJournalonSelectedAreasinCommunications, 2007, 25(8): 1501-1506

[17] Cheng L, Henty B E, Bai F, et al. Highway and rural propagation channel modelling for vehicle-to-vehicle communications at 5.9 GHz. In: Proceedings of the 2008 IEEE Antennas and Propagation Society International Symposium, San Diego, USA, 2008.1-4

[18] Islam T, Hu Y, Boltjes D E. Realistic simulation of IEEE 802.11p channel in mobile vehicle to vehicle communication. In: Proceedings of the 13th Conference on Microwave Techniques COMITE 2013, Pardubice, CzechRepublic, 2013. 156-161

[19] Chen Q, Schmidt-Eisenlohr F, Jiang D. Network simulator ns-2. http://ww w.isi.edu/nsnam/ns/: WiKi, 2007

A scheme based on graph coloring theory for time slot allocation in integrated VANET-cellular heterogeneous networks

Zhang Pengtao*, Zhou Yiqing**, Liu Hang**, Tian Lin**, Shi Jinglin**

(*College of Communication and Information Engineering, Chongqing University of Posts and Telecommunications Communication, Chongqing 400065) (**Beijing Key Laboratory of Mobile Computing and Pervasive Device, Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100190)

To solve the problem that the time slots of integrated VANET-cellular heterogeneous networks are not easy to allocate when there are more vehicles on the road, a new time slot allocation scheme is proposed based on the graph coloring theory, and its time slot allocation algorithm is given. The scheme uses the nodes within two-hop to form the graph coloring model, and allocates time slots by using the graph coloring method to reduce the packet loss caused by hidden terminals. Through defining a weight coefficient based on the degree of node, the algorithm ensures the fairness, and improves the reuse of time slots, thus improving the reliability of message delivery. Moreover, it is efficiently and practically applicable to the vehicle networking scene whose topology changes rapidly. The simulation showed that, compared with the traditional method, the average packet reception increased greatly in the condition of 200 vehicles and 100 time slots. In addition, it showed a trade-off between the time slot reuse and the average packet reception rate. The study also found that the packet reception rate increased with the increasing of the transmit power until to a certain value when the SINR tends to a constant.

VANET-cellular heterogeneous networks, graph coloring theory, time slot reuse, transmit power, packet reception rate

10.3772/j.issn.1002-0470.2016.06.005

①国家自然科学基金(61331009)和科技创新基地培育与发展工程专项(Z15110000161503)资助项目。

2016-01-11)

②男，1989年生，硕士；研究方向：车联网，宽带无线通信，物理层基带算法；联系人，E-mail: zhangpengtao@ict.ac.cn