VANET中利用分布式TDMA空闲时隙的协作中继方法*

欧 莽，陈 振，汪继文

安徽大学 计算机科学与技术学院，合肥 230601

1 引言

随着无线通信和汽车工业技术的融合，车辆装有车载通信模块，与其他车辆或路边通信设施自发通信成为了可能，衍生出一种新的移动自组网（mobile ad hoc networks，MANET）应用——车载自组网（vehicular ad hoc networks，VANET）。作为现代智能交通的基石，VANET 在提升道路安全、优化交通出行、信息服务、车载娱乐等方面都有着非常重要的应用[1]。

考虑到交通事故对人类生命和财富的巨大威胁，道路安全应用在VANET 诸多应用中显得尤为迫切，这类应用通常要保证安全信息及时可靠地传输，否则会带来灾难性的后果。IEEE 802.11系列协议无法满足VANET 安全应用对通信时延和可靠性的严格要求，不能提供有效的信息广播服务（很多VANET安全信息需要以广播方式发送），从而不能很好地适应VANET 应用场景[2-4]。鉴于IEEE 802.11系列协议的诸多问题，人们积极探索研究无竞争型MAC（medium access control）协议在VANET 中的应用[5]，特别是针对VANET场合的分布式TDMA（distributed time division multiple access，DTDMA）协议更是近年来的研究热点[6-11]。DTDMA能够较好地适应VANET安全应用的通信要求[7-8]，并且在信道利用率、网络吞吐量和协议公平性等方面也表现出较好的性能[9-10]。在VANET中，由于缺少中心节点，DTDMA基于包头携带的时隙分配信息工作，节点获得时隙后，就会一直占用时隙，即使不需要发送实际应用数据，也要在自身时隙内发送伪包，以便与其他节点交换时隙分配信息，这种工作方式不可避免地产生了节点空闲时隙问题。而另一方面，由于车辆高速移动，车辆或路旁建筑物对无线传输信号阻挡等，车载环境下的无线信道质量相对于一般的无线通信环境会更差，以至于通信可靠性问题严重制约着VANET 的推广和应用[12]。

由于信道资源受限，且考虑到VANET 应用业务的快速增长，单纯地从点到点无线链路来寻求网络性能的提升会面临诸多限制和瓶颈，而作为现代无线通信的一种重要技术手段，协作通信能够通过节点间的协作来有效提高通信可靠性。文献[13-15]基于有中心基站的TDMA协议提出了相关协作通信方法，在这些方法中，时隙分配管理、协作通信的协调和执行等都要依赖中心基站，况且它们大都只关注移动终端与中心基站之间的通信，因而不适合VANET 场合。Yang 等提出了名为CCB-MAC（cooperative clustering-based MAC）的TDMA 协作通信方法，该方法虽然不依赖实际网络中心节点，但需要依赖簇头节点，产生了簇形成、簇维护和选择簇头节点等网络开销[16]。文献[17-18]基于DTDMA 提出了利用帧内未分配时隙的协作通信方法，但由于利用帧内未分配时隙进行协作通信不可避免地降低其他节点请求获得时隙的机会，影响到网络正常数据传输业务。文献[19]提出名为DC-TDMA 的TDMA 协作通信方法，DC-TDMA 不依赖中心节点，利用节点空闲时隙协作中继转发数据，但每次网络拓扑结构改变时，不同节点需要带外数据（out-of-band，OOB）交换时隙再分配信息，在网络拓扑结构频繁变化时，会产生大量的网络开销，而且针对每次网络拓扑结构的改变，DC-TDMA 需要大量时间对网络进行重置，因而不适合VANET场合。上述TDMA协作通信方法都需要依赖相关数据传输确认信息和机制，如在DCTDMA 中，只有在确认中继节点没有成功接收数据后，相关节点才进行协作中继转发。通常的数据确认方式为，源节点在自身时隙前部分发送数据，目标节点在源节点时隙后部分发送确认信息。这将导致以下问题：首先，目标节点需要发送相关控制包，如ACK（acknowledgement）和NACK（negative acknowledgement）控制包，增加了网络开销；其次，时隙时间需要设置较长，以便除了容纳源节点发送的数据包外，还要容纳目标节点发送的控制包（在VANET 中，如果时隙时间设置较长，则会导致DC-TDMA帧时间较长和节点访问信道时延较长，不利于其安全应用）；最后，需要节点在单个时隙内切换无线通信的收发模式，增加了实现复杂性。

为有效利用节点自身空闲时隙协作中继转发数据，针对VANET 场合提出一种基于DTDMA 的协作中继转发方法（cooperative relaying distributed TDMA，CR-DTDMA）。不同于上述TDMA 协作通信方法，CR-DTDMA实现一种网络握手协议来确定协作中继节点，同时采用消息搭载（piggyback，PB）机制传递相关控制信息，从而在不依赖数据传输确认机制、不传递专门控制包、不在单个时隙内切换无线通信收发方式的情形下实现了协作中继过程。由于仅利用节点自身空闲时隙资源，CR-DTDMA 不影响网络中的正常数据传输业务，但提高了相关网络性能。最后，从数据中继转发概率、中继转发时延和丢包率三方面来分析和验证所提方法的可靠性。

2 信道访问

分布式TDMA协议将信道时间划分为不同的帧（frame），每帧包含固定数目时隙（slot），设每帧包含的时隙数为F。为了确定每帧起始时间和帧内各个时隙的起始时间，DTDMA需要不同节点实现时钟同步。随着全球定位系统（global positioning system，GPS）和导航系统的普及，假设车辆可以利用GPS 脉冲信号实现时间同步（即便是对于一般的GPS 接收器来说，GPS 脉冲信号时间误差也在100 ns 以内，足以满足通常情况下的时钟同步要求）[7]。在DTDMA中，由于不存在中心节点分配时隙资源，为了获知帧内时隙状态，各个节点需要交换时隙分配信息。具体方式为[7-8]：每个节点在自身数据包头中插入帧信息（frame information，FI）域，FI域记录了节点一跳传输范围内邻居节点的时隙占用情况，通过与一跳传输范围内的邻居节点交换FI 域，节点判断出两跳传输范围内的邻居节点时隙占用情况。为了避免隐藏节点和信息碰撞问题，节点只能请求访问两跳传输范围内邻居节点未访问的时隙。如图1所示，由于车辆A和车辆G在彼此两跳传输范围外，它们可以访问帧内相同的时隙，而车辆A、B、C、D、E都在彼此两跳传输范围内，它们需要访问帧内不同的时隙。需要指出的是，在分布式TDMA协议中，为了和其他节点交换时隙分配信息，即使节点不需要发送数据，也要在自身时隙内发送虚拟数据包（dummy packet，实际数据为空）[7-8]。

Fig.1 Time slot access mechanism in distributed TDMA protocol图1 分布式TDMA协议时隙访问机制

在VANET 中，距离两跳范围外的车辆节点由于相对移动而彼此接近，可能成为两跳范围内的邻居节点，如果原来这些节点访问帧内同一时隙，就会引发时隙访问冲突问题，这种情形下，冲突节点需要重新申请时隙[7]。文献[7-8]提出了VeMAC 协议，将帧时分为3个不相交的时隙子集，行驶在公路不同方向上的车辆和路旁固定通信设备分别访问帧内不同的时隙子集，从而减少了时隙访问冲突次数，提高了网络性能。下面假设在VeMAC 协议下车辆节点都已获得相应时隙。

3 协作数据中继转发

在很多情形下，源节点到目标节点的距离大于无线一跳传输距离。下面主要关注源节点到目标节点距离为两跳情形时的协作中继转发方法，当源节点到目标节点距离大于两跳情形时，沿着源节点到目标节点路径不断地重复上述两跳过程，直到源节点数据到达目标节点。如图2所示，源节点S到目标节点D的距离大于无线一跳传输距离且小于两跳传输距离，源节点S数据需经过中继节点R中继转发至目标节点D。在源节点S发送数据到中继节点R时，由于无线信道广播特性，同时处于源节点S与目标节点D传输半径内的其他节点也能正确接收源节点S数据。因此，在中继节点R未成功接收到源节点S数据时，这些节点可以利用自身空闲时隙协作中继转发源节点S数据。下面把进行协作中继转发的节点称为协作中继节点。

Fig.2 Cooperative data relaying in two-hop transmission range图2 两跳传输范围内的协作数据中继转发

3.1 CR-REQ与CR-ACK

下面实现一种用于确定协作中继节点的网络握手机制。

Fig.3 CR-DTDMA packet structure图3 CR-DTDMA的数据包结构

当收到源节点S发送的数据，中继节点R通过检验包头中的循环冗余校验码（cyclic redundancy code，CRC）或通过其他错误控制机制来验证是否正确接收数据。如果R未成功接收节点S数据，则如图3（a）所示，中继节点通过在自身数据包头中插入协作中继转发请求（cooperative relay request，CRREQ）域来请求附近其他节点协作中继转发源节点数据。其中，包头中的PHY Header、MAC Header、FI、Payload Data 和CRC 等与DTDMA 相同。在新插入的CR-REQ 域中，Flag 标志为0，表示插入的是CR-REQ 域。此外，Source ID、Packet Sequence 和Destination ID 分别对应了待协作中继转发数据的原来源节点标识、数据包序号以及目标节点标识，用于标识待协作中继转发的数据。

当目标节点与源节点共同传输范围内的其他节点收到中继节点发送的CR-REQ 域时，如果满足条件：自身时隙空闲；已成功接收源节点数据；未侦听到其他节点协作中继转发源节点数据，则节点在自身时隙内协作中继转发源节点数据，并在协作中继转发的数据包头中插入协作中继转发确认（cooperative relay acknowledgement，CR-ACK）域，确认已协作中继转发数据。如图3（b）所示。在CR-ACK域中，Flag标志设置为1，表示数据包头中插入的是CR-ACK域，其余信息与CR-REQ域相同。

3.2 协作中继转发中的信息交互

基于图2所示场景，图4说明相关信息交互过程。

（1）如图4（a）所示，源节点S在自身时隙内发送数据到中继节点R，由于H1、H2等节点在S与D的共同传输范围内，如果它们成功接收S数据，将数据保存在自身缓存中。

（2）如图4（b）所示，如果S数据未被中继节点R成功接收，则中继节点R在自身时隙内发送数据时，在要发送的数据包头中插入CR-REQ 域，通过CRREQ域请求附近其他节点协作中继转发源节点S数据，即中继节点R采用PB机制传递CR-REQ域。

（3）如图4（c）所示，节点H1接收到CR-REQ 域，如果节点H1满足上述协作中继转发条件，则节点H1在自身空闲时隙内协作中继转发源节点S数据，并在协作中继转发的数据包头中插入CR-ACK 域，通过CR-ACK域确认已协作中继转发源节点S数据（节点H1也是采用PB机制传递CR-ACK域）。当其他节点（如节点H2等）侦听到节点H1发送的CR-ACK 域，不再协作中继转发源节点S数据。

Fig.4 Information exchange process in CR-DTDMA图4 CR-DTDMA中的信息交换过程

在上述过程中，当源节点数据未被中继节点成功接收时，中继节点发送协作中继转发请求信息CRREQ，当有节点协作中继转发数据时，该节点便发送协作中继转发确认信息CR-ACK。上述过程不需要其他节点确认中继节点是否成功接收源节点数据，从而避免发送用于传输确认的控制包。此外，为避免发送控制包，上述过程采用PB 机制来传递CRREQ和CR-ACK信息。

VANET 安全应用通常要求在100 ms 内将安全信息传递给附近车辆[3]，为了及时传播信息，分布式TDMA协议的帧时间通常要求设置在几十毫秒内[7-8]。上述整个过程（从源节点发送数据到协作数据中继转发完成）发生在1～2帧内，持续时间短，因此在此过程中节点相对位置几乎没有变化。由于上述过程不依赖中心节点，且持续时间短，因而能满足VANET无中心节点且网络拓扑结构频繁变化的特点。

3.3 网络开销分析

CR-DTDMA 网络开销为在包头中插入的CRREQ/CR-ACK 域。CR-REQ/CR-ACK 域包含了Flag标志（长度为1 bit）、源节点ID号、数据包序号和目标节点ID 号。参考文献[8]，将节点ID 号长度设置为7 bit，数据包序号长度设置为2 Byte（当大于最大序号时，数据包序号从0开始重新计数），时隙时间长度设置为1 ms。在上述设置下，CR-REQ/CR-ACK域所占用的数据位数为31 bit。参考相关专用短程通信（dedicated short range communications，DSRC）标准，将数据传输速率设为18 Mb/s，则节点能够在1个时隙内发送长度为18 874 bit 数据。由于CR-REQ/CRACK 域所占用的数据位数远小于节点在1个时隙内所发送的数据位数，因此相对于利用的空闲时隙资源，CR-REQ/CR-ACK域开销可以忽略不计。在下面分析和仿真中，假设CR-REQ/CR-ACK域都能够被车辆节点正确地发送和接收。

4 相关网络性能分析

与传统无线网络中节点随机运动情形不同，车辆的行驶必然受到公路拓扑结构的限制。同时，无线一跳传输范围远大于公路宽度，VANET 可当成线状网络[17-18]。下面基于一维空间公路场景进行分析。由于车辆交通流量在公路上服从Poisson分布[3-4，16-17]，设车辆在公路上的平均密度为β，则公路上长度为l的区间存在i辆车的概率为：

节点以恒定的无线发射功率发送数据。设源节点到目标节点的距离为d，目标节点的瞬时接收功率为Power(d)。为了能够成功地解码数据，Power(d)必须等于或大于一个阈值th。如果目标节点在源节点的传输半径r内，设目标节点成功接收源节点数据的概率为p，否则不能成功接收源节点数据[3-4，16]：

p越大，对应的信道质量越好。

下面基于图2所示场景分析VeMAC 和CRDTDMA 的数据中继转发概率、中继转发时延和丢包率。

4.1 VeMAC性能分析

设数据在源节点发送成功概率为ps，以概率p表示信道质量，pc为信息碰撞概率，由于p和pc彼此独立，则ps为：

由第2章信道访问可知，pc=0，因此ps=p，即ps决定于信道质量。

在图2中，首先中继节点R接收源节点S发来的数据，然后将数据中继转发到目标节点D。在源节点S发送数据后，设数据能够被中继节点R中继转发的概率为prelay（假设中继节点成功接收源节点数据后就能够中继转发源节点数据），则：

在源节点S发送数据后，如果数据未被中继节点R中继转发，则通常情形为在等待固定时间（如timeout）后，源节点S重发数据，该过程不断重复进行，直到数据被中继节点R中继转发。因此，从源节点S开始发送数据到中继节点R中继转发源节点S数据的时延决定于源节点S发送数据的次数。下面将数据中继转发时延定义为在数据被中继转发前，源节点发送数据的次数。在源节点S每次发送数据后，数据能够被中继转发的概率为prelay，设T为数据中继转发时延，则：

T服从几何分布，均值为：

在通信系统中，如果超过最大发送次数后数据包仍未被正确处理，通常会丢掉该包。设数据包的最大发送次数为M，则数据包在源节点S处的丢包率PLR（packet loss rate）为：

4.2 CR-DTDMA性能分析

本文主要关注源节点S距目标节点D的距离为两跳的情形，即目标节点D距源节点S的距离大于r且小于2r，当目标节点D距源节点S的距离趋近r时，它们共同传输范围的长度趋近于最大值r；当目标节点D距源节点S的距离趋近2r时，它们共同传输范围的长度趋近于最小值0。因为目标节点D均匀分布在距源节点S距离r到2r的范围内，所以它们共同传输半径的长度平均为0.5r。在图2中，当中继节点R未成功接收源节点S数据时，源节点S与目标节点D共同传输半径内的其他节点可以利用自身空闲时隙协作中继转发源节点S数据。设目标节点D与源节点S共同传输半径内的节点数为Nc，则：

当u≤1时，除中继节点R外，目标节点D与源节点S共同传输半径内没有其他节点，这种情况下不存在协作中继节点；当1 ＜u≤F-2时，除了中继节点R外，可能有u-1个节点成为协作中继节点；考虑到帧内时隙数为F，除了目标节点D与源节点S外，最多有F-2个节点能够获得时隙，因此当u＞F-2时，把u当作F-2处理。当1 ＜u≤F-2时，除中继节点R外，可能成为协作中继节点的有u-1个，在这u-1个节点中，下列事件之一将导致节点不能成为协作中继节点：

（1）没有成功接收源节点S数据；

（2）成功接收源节点S数据，但在自身时隙内有数据需要发送。

设节点有数据需要在自身时隙内发送的概率为pd（节点时隙空闲的概率为1-pd），则上述u-1个节点都不能成为协作中继节点的概率为，式中v为u-1个节点中已成功接收源节点S数据的节点数目。设Nh为协作中继节点数目，则在Nc=u时，协作中继节点不存在的概率为：

在Nc=u，u＞1时，协作中继节点的存在概率为：

因此，在所有条件下，存在协作中继节点的概率为：

在源节点S发送数据后，如果中继节点R未能中继转发数据，则存在可能协作中继转发数据的节点，且协作中继节点的存在概率为Pr{Nh＞0}。因此，在源节点S发送数据后，源节点S数据能被中继转发的概率为：

5 仿真实验

用Matlab 仿真一维空间公路或高速公路场景，公路有两条车道，分别代表公路不同的行驶方向。在每条车道上，车辆平均速度为80 km/h，速度标准偏差为20 km/h，车辆平均密度为βl（公路车辆密度β为2βl）。无线信道采用车辆专用短程通信标准参数，其中工作频段为DSRC 5.9 GHz，数据传输速率为18 Mb/s。帧中的时隙数F为80，时隙时间长度为1 ms。仿真过程不考虑公路旁固定通信设备，每条车道上的车辆能够访问的时隙数目为40。下面仿真比较VeMAC与CR-DTDMA两种方法的网络性能。

图5到图7为两种方法的数据中继转发概率比较。图5到图7表明，CR-DTDMA 方法相对于VeMAC 方法在数据中继转发概率上得到显著提高。由于利用了节点空闲时隙协作中继转发数据，在中继节点未能转发数据时，数据就有了更多的中继转发机会，从而在CR-DTDMA方法中数据中继转发概率得到显著的提高。VeMAC的数据中继转发概率主要决定于信道质量p，CR-DTDMA的数据中继转发概率除了决定于信道质量p外，节点发送数据概率pd、车辆密度β和一跳传输距离r对它也有很大影响。

图5表明，在一跳传输距离r（200 m）和节点发送数据概率pd（0.5）固定时，如果车辆密度β越大，则在源节点与目标节点共同传输半径内能够协作中继转发数据的节点就越多，CR-DTDMA 的数据中继转发概率就越大。

Fig.5 Comparison of data relaying probabilities between two methods under different β values图5 不同β 值下两种方法的数据中继转发概率比较

图6表明，在一跳传输距离r（200 m）和车辆密度β(0.04车/m)固定时，如果节点发送数据概率pd越大，则拥有空闲时隙的节点就越少，能够转发数据的协作中继节点就越少，CR-DTDMA 的数据中继转发概率就越小。

Fig.6 Comparison of data relaying probabilities between two methods under different pdvalues图6 不同pd值下两种方法的数据中继转发概率比较

图7表明，在节点发送数据概率pd（0.5）和车辆密度β（0.04车/m）固定时，如果一跳传输距离r越大，则源节点与目标节点的共同传输范围就越大，能够转发数据的协作中继节点就越多，CR-DTDMA 的数据中继转发概率就越大。

Fig.7 Comparison of data relaying probabilities between two methods under different r values图7 不同r 值下两种方法的数据中继转发概率比较

图8比较了两种方法的数据中继转发时延，其中，r为200 m，pd为0.5。在信道质量较差时，CRDTDMA的性能优势明显。如p为0.3时，VeMAC的数据中继转发时延为3.3帧，CR-DTDMA的数据中继转发时延为1.8帧（β为0.04车/m 时）和1.3帧（β为0.08车/m 时），中继转发时延至少降低了45%。在CR-DTDMA 中，当源节点数据不能被中继节点中继转发时，附近的其他节点利用自身空闲时隙协作中继转发源节点数据，从而在源节点不需要重发数据的情况下，数据就能被协作中继转发，减小了中继转发时延。此外，如果协作中继转发的发生概率越大（图8中对应了β值较大的情形），CR-DTDMA 的数据中继转发时延就越小。随着p不断增大，信道质量越来越好，协作中继转发的必要性越来越小，VeMAC 和CR-DTDMA 的数据中继转发时延差异也逐渐变小。

Fig.8 Comparison of data relay forwarding delays between two methods图8 两种方法的数据中继转发时延比较

图9在图8的相同条件下比较了VeMAC 和CRDTDMA的丢包率，其中M取值为3。在不同的信道质量下，CR-DTDMA丢包率始终低于VeMAC。如在p为0.3，β为0.04车/m时，VeMAC的丢包率为34%，CR-DTDMA的丢包率为9%，丢包率降低了73%。此外，协作中继转发的发生概率越大，CR-DTDMA的丢包率越小。

图5到图9表明，随着p增大，VeMAC 和CRDTDMA的数据中继转发概率都在增大，中继转发时延和丢包率都在减小。在p为0时，由于信道质量极差，所有数据都不能被中继转发，VeMAC 和CRDTDMA的数据中继转发时延无限大，所有数据都会丢失；在p值为1时，由于信道质量好，所有数据都会被中继转发，VeMAC 和CR-DTDMA 的中继转发时延相同且没有数据丢失。

Fig.9 Comparison of packet loss rates of two methods图9 两种方法的丢包率比较

6 结束语

本文提出了一种利用分布式TDMA协议节点空闲时隙的协作中继方法CR-DTDMA，当中继节点未能中继转发数据时，协作中继节点利用自身空闲时隙协作中继转发数据。该方法不依赖中心控制节点，能够适应VANET 网络拓扑结构的频繁变化，而且不需要发送专门的控制包，不要求节点在单个时隙内切换通信的收发模式，系统实现简单，网络开销小。同时，由于仅利用节点自身空闲时隙资源，CRDTDMA 方法不影响网络中的正常数据传输业务。分析和仿真结果表明，由于CR-DTDMA方法利用了节点空闲时隙协作中继转发数据，数据就有了更多的中继转发机会，从而显著提高数据中继转发概率，有效降低中继转发时延和丢包率。

本文基于简化的信道模型对所提方法进行分析和仿真，后续将进一步研究更加真实的信道模型对所提方法的性能影响。