VANETs中基于分布式TDMA的协作网络编码方法

欧莽 汪继文

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

作为智能交通的重要组成部分，车载自组织网(Vehicular Ad hoc Networks，VANETs)包含两种基本通信方式：车辆与车辆之间(Vehicle to Vehicle，V2V)以及车辆与路侧单元(Road Side Unit，RSU)之间(Vehicle to Infrastructure，V2I)通信[1-2]。V2I通信能够实现碰撞预警、交通信息播报、位置感知和信息娱乐等移动分布式应用，一直是智能交通领域的研究重点。然而，由于动态拓扑、信道衰落和多普勒效应，VANETs环境中的信道条件相比一般无线环境更差，使得如何及时可靠地将数据从行驶车辆传送到路边RSU面临着很大挑战[3- 5]。

由于媒体访问控制层(Media Access Control，MAC)协议直接控制着数据分组在无线信道上的收发过程，如何设计有效可靠的MAC协议一直是VANETs研究领域的关键。分布式时分多址(Distributed Time Division Multiple Access，DTDMA)协议[6- 12]近年来成为人们探究的热点，例如ADHOC MAC[8]，VeMAC[9- 10]，sdnMAC[11]，MoMAC[12]和DTMAC[13]等，其中最具代表性的协议是VeMAC协议。大量的分析和实验表明，VeMAC协议不但能够满足VANETs安全应用对服务质量(QoS)的严格要求，而且，相对于IEEE802.11系列协议，它在信道利用率、网络吞吐量和协议公平性等方面均获得了较好的性能[9- 10，14- 16]。

由于有限的频谱资源，单纯从点到点无线信道来提升网络性能面临诸多瓶颈，而协作通信可以利用无线信道的广播特性通过节点间的协作来提高无线链路的可靠性。文献[17]中，协作节点在源节点的时隙期间执行协作重传，当不存在协作节点时，源节点重新发送失败的数据分组；文献[18- 19]中，协作节点利用未分配的时隙进行协作，然而，当节点密度较大时，帧中存在未分配时隙的概率极低；文献[20]中，协作节点利用自身的空闲时隙进行协作，但是当网络繁忙时，几乎没有机会找到具有空闲时隙的节点；文献[21]中，认知无线电技术用于访问未授权的无线信道以执行协作重传，不可避免地引入额外的信令开销以获知未授权的信道。

上述所有方案中，协作节点进行协作时，并不传输自己的数据分组。网络编码(Network Coding，NC)能够把多条数据流进行合并，使得协作节点在协作传输其它节点数据分组同时传输自己的数据分组，以提高网络效率[22-24]。然而，NC仅能从正确接收的分组中解码信息，不能处理出错分组的解码。为此，Fasolo等[25]把网络编码和信道编码相结合提出了MIMO_NC编码方法，用以解码出错的数据分组信息[25-26]。本研究将MIMO_NC应用到VANETs上行链路应用场景中，提出一种基于分布式TDMA的协作网络编码(Distributed TDMA Based Cooperative Network Coding For Medium Access Control，DTCNC-MAC)方法，使得协作节点能够在发送自身业务数据的同时协作发送其它节点出错的数据分组，从而在不影响网络正常数据传输业务的情形下实现VANETs上行链路节点间的协作，提高VANETs上行链路通信可靠性；DTCNC-MAC所有操作以分布式方式进行，而且能够适应VANETs网络拓扑结构频繁变化的特点；最后，从数据发送概率、数据发送时延和丢包率3方面对所提方法的可靠性进行了分析和验证。

1 分布式TDMA信道访问

在分布式TDMA协议中，信道时间被划分成不同的帧(Frame)，每帧包含固定数目的时隙(Slot)，设每帧包含的时隙数为F。为了确定每帧起始时间和帧内各个时隙的起始时间，DTDMA中不同车辆节点利用全球定位系统(Global Positioning System，GPS)实现时钟同步[7]。在DTDMA中，为了获知帧内时隙状态，各个节点需要交换时隙分配信息，具体方式为[9- 10]：每个节点在自身数据分组头部中插入帧状态信息(Frame Information，FI)域，FI域记录了车辆节点一跳传输半径范围内邻居节点的时隙分配及占用情况，通过与一跳传输半径内的邻居节点交换FI域，节点判断出两跳传输半径范围内的邻居节点的时隙分配及占用情况。为了避免隐藏节点和信息碰撞问题，节点只能请求访问两跳传输半径范围内邻居节点未访问的时隙。分布式TDMA协议时隙访问机制如图1所示，由于车辆A和车辆G在彼此两跳传输半径外，它们可以访问帧内相同的时隙，而车辆A、B、C、D、E都在彼此两跳传输半径内，它们需要访问帧内不同的时隙。

车辆节点访问时隙序号E1F2…3…4车辆节点访问时隙序号B5A/G6C7D8

图1 分布式TDMA协议时隙访问机制

Fig.1 Slot access mechanism in distributed TDMA protocol

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

2 MIMO_NC编码

实现DTDMA协议的编码重传，必须考虑两个因素：(1)处理编码重传的物理层；(2)用于协调访问的MAC层。对于(1)，如图2所示，假设源节点S发送数据分组x到D，但是D不能正确接收x，记D接收的出错分组为x′。如果节点D接收到编码分组x⊕y(符号⊕代表NC编码操作)，则NC不能通过分组x′和x⊕y解码出分组x、y，因为NC只能对完全正确接收的分组进行解码。而MIMO_NC可以利用分组x′和x⊗y解码出分组x、y(符号⊗代表MIMO_NC编码操作，x⊗y是应用物理层NC原理在伽罗瓦域中矢量的线性组合)。

如图2(c)所示，MIMO_NC将网络编码下潜到物理层的信道编码之后，在编码阶段，每个节点根据经典NC方法将其缓冲器中信道编码后的信息单元(Information Units，IUs)组合成由8比特伽罗瓦域中符号阵列表示的编码分组(Coded Packets，CPs)，然后经由BPSK调制器调制并发送。解码阶段在采用MIMO解码算法的物理层执行。将接收存储到缓冲器中的分组样本执行基于球形解码的软解码方案重建IUs。MIMO_NC相对于经典方法的主要区别在于所有接收的分组，包括损坏的分组和冗余分组，都可用以解码，从而获得SNR增益和分集阶数的提升，进一步了解请参考文献[25]。

(a)NC编码/解码

(b)MIMO_NC编码/解码

(c)MIMO_NC编码/解码过程[25]

用pMIMO_NC表示MIMO_NC正确解码的概率。文献[25]研究表明，即使在较差的信道条件下，MIMO_NC仍有较高的解码概率。例如，即使信道干扰(加噪声)功率上升到信号功率，该值也超过66%[26]。文中，重点关注因素(2)——MAC层实现。

3 结合MIMO_NC的分布式TDMA协议

考虑VANETs上行链路，如图3所示，其中，RSU部署在道路旁，车辆以相同的平均速度(例如高速公路场景)经过RSU。我们假设RSU和车辆的传输半径是相同的，每对节点(V2V和V2I)仅在彼此传输半径内才能通信，并且RSU和车辆都配备了相应的MINO_NC编码/解码模块。

图3 VANETs上行链路中的协作编码转发

Fig.3 Cooperative network coding and forwarding in VANETs uplink

车辆节点S1发送数据分组到路侧单元RSU时，由于无线信道广播特性，处于S1节点与RSU节点共同传输半径内的其它节点S2、S3也能正确接收源节点S1数据，因此，在RSU未能正确接收S1数据时，这些节点可以利用自身时隙协作编码转发节点S1数据。下面把进行协作编码转发的节点称为协作节点。

3.1 协作编码请求与协作编码确认域

设计一种网络握手协议来确定协作节点，同时，为避免发送专门的控制分组，采用消息搭载(Piggyback)机制来交换相关控制信息。

(1)协作编码请求域(Cooperative Network Coding Request，CNC-REQ)

CNC-REQ用于RSU请求其它节点协作重发源节点数据。如果RSU未能正确接收来自源节点的数据分组，但接收的数据信号干扰噪声比(Signal To Interference And Noise Ratio，SINR)大于MIMO_NC解码阈值θTH，即SINR≥θTH，则RSU通过在自身数据分组头部中插入CNC-REQ域来请求其它节点利用MIMO_NC技术协作编码重发传输失败的数据。如图4(a)所示，在新插入的CNC-REQ域中，标识位为0，表示数据分组头部中插入的是协作编码请求域，源节点ID、分组序号和目标节点ID分别对应了待协作编码重发数据的源节点标识、分组序号和RSU标识，这些信息标识了待协作编码重发的数据信息。

(2)协作编码确认域(Cooperative Network Coding Acknowledgement，CNC-ACK)

CNC-ACK用于协作节点确认协作编码重发。如图4(b)所示，在CNC-ACK域中，标识位设置为1，表示插入的是协作编码确认域，其余信息与CNC-REQ域相同。当RSU与源节点共同传输半径内的某个节点收到RSU发送的CNC-REQ域时，但没有侦听到其它节点发送CNC-ACK域时，节点将自身数据和待重发的源节点数据进行编码发送，并在数据分组头部中插入CNC-ACK域确认已协作重发数据。

(a)CNC-REQ

(b)CNC- ACK域

Fig.4 CNC-REQ/ACK field in DTCNC-MAC packet

3.2 节点间的信息交互

基于图3所示的应用场景，下面结合图5(以节点RSU时隙为时间参考点)来说明相关节点信息交互过程。

(1)第i帧中，当源节点S1在自身时隙中发送数据PS1到RSU时，节点S2、S3等在节点S1与RSU的共同传输半径内，如果它们正确接收数据PS1，则将数据PS1保存在自身缓存中。

(2)如果RSU未完全正确接收数据PS1，但接收的数据平均信号干扰噪声比SINR≥θTH，则在第i+1帧中，RSU在自身时隙中发送的数据分组头部中插入CNC-REQ域来请求协作节点协作编码重发源节点S1数据PS1。

(3)节点S2要发送数据PS2到节点RSU，且已接收到RSU发送的CNC-REQ域，则在第i+1帧中自身时隙内编码发送PS1⊗PS2，并在其分组头部中插入CNC-ACK域来确认已协作重发源节点S1数据。当其它节点(如节点S3等)侦听到节点S2发送的CNC-ACK后，则不再协作重发源节点S1数据。

(4)在接收到S2发送的PS1⊗PS2后，节点RSU利用MIMO_NC解码得到PS1和PS2。

需要指出的是，如果节点RSU解码失败，在下一帧时节点S1重发数据分组PS1，节点RSU利用MIMO_NC解码PS1⊗PS2和PS1得到数据分组PS2。

上述协作过程各个节点根据所接收的一跳范围内信息来决定时隙的获取和协作编码数据的重发，因此，协作过程是分布式的(节点根据自身局部范围内的信息工作)，同时，协作过程利用TDMA的确定信道访问方式(不同节点对应了不同时隙，且只在自身时隙内发送数据，在其它时隙内接收数据)，使得源节点、目标节点和协作节点能以确定和有序的分布式方式进行交互。另外，VANETs安全应用要求在100 ms内将信息传送到RSU，为保证车辆节点及时传递信息，分布式TDMA设置长度很短(几十毫秒)的帧时间。通常只需1～2帧时间就能完成协作数据重发，期间节点的相对位置几乎没有发生变化，因而能满足VANETs快速网络拓扑变化等特点。

图5 DTCNC-MAC节点协作时序

Fig.5 DTCNC-MAC node cooperation timing

3.3 开销分析

为避免发送专门用于控制的数据，DTCNC-MAC采用消息搭载机制来传输相关控制信息，即通过在相关节点数据分组头部中插入CNC-REQ/ACK域来交换控制信息，其开销为插入的CNC-REQ/ACK域。CNC-REQ/ACK域包含了标识位(大小为1 b)、源节点ID、分组序号和RSU节点ID。参考文献[9]，节点ID数据位为7 b、分组序号大小为2B、时隙时间长度设为1 ms。这样CNC-REQ/ACK域所占用的数据位数为31 b。参考车辆专用短程通信(Dedicated Short Range Communications，DSRC)标准，设置数据传输速率为24 Mbps，则在1个时隙内节点能够发送25 165 b数据。由于CNC-REQ/ACK域所占用的数据位数远小于节点在1个时隙内所传输的数据位数，因此，相对于DTCNC-MAC复用的时隙资源，CNC-REQ/ACK域开销可以忽略不计。在下面分析中，假设节点都能正确地收发CNC-REQ/ACK域。

另一方面，MIMO_NC采用球形译码算法把搜索空间限制在以接收向量为球心的超球体格点内，大大缩短计算时间。在某些 SNR和天线数范围内，球检测算法复杂度已是多项式的。因此，对于具有高计算通信能力和能量不受限的VANETs车辆节点，相对于频谱效率的提高和传输时延的降低，MIMO_NC解码计算开销也可以忽略不计。

4 性能分析

参考文献[18- 20]中单位圆盘模型表示信道。假设车辆具有相同的无线一跳传输半径，在不考虑数据碰撞的情况下，在一跳传输半径内，车辆之间成功发送数据的概率为p。p是信道质量的反映，p越大，受到信道衰落和多普勒效应等影响就越小，信道质量越好，相反，信道质量越差。

为了简化分析，我们基于一维场景进行分析，并假设车辆在一维直线车道上服从泊松分布[9，19]。如有M条车道，m∈{1，2，3，…，M}，βm为车道m上的平均车辆密度，则在长度为l的道路上分布j辆车的概率为

(1)

假设RSU和车辆的传输半径是相同的，并记传输半径为r，则车辆节点前后一跳传输半径内的相邻节点数Nn(包括节点自身)等于j的概率Pr{Nn=j}可用l=2r代入式(1)得：

(2)

下面分析和比较VeMAC和DTCNC-MAC的网络数据成功发送概率、数据分组传输时延和丢包率。

4.1 VeMAC性能分析

设ps为VeMAC的一跳传输半径内数据成功发送的概率，pc为信息相互碰撞的概率。由于信道质量(p)和信息相互碰撞彼此独立，则ps为

ps=(1-pc)p

(3)

由前文可知，由于分布式TDMA中使用确定的信道访问方式，故pc为0，所以ps=p。

在传输失败时，源节点尝试重传数据包直到它成功到达目的节点。在DTDMA中，分组传输时延(Packet Transmission Delay，PTD)定义为成功将分组发送到目的节点所需的帧数。在VeMAC中，设TDVeMAC为分组传输时延，数据分组经过i次重发才能被目标节点正确接收的概率为

Pr{TDVeMAC=i}=(1-ps)i-1ps

(4)

因此，TDVeMAC均值为

(5)

在通信系统中，当源节点无法在预定义的时间限制内将数据包传送到目的节点时，源节点从其缓冲存储器中丢弃该数据包。在DTDMA中，根据帧数考虑这个时间限制。令Imax表示源节点尝试发送分组的最大帧数，称为最大传输限制。把超过最大传输限制Imax帧后数据还没有被发送到目的节点的概率定义为丢包率。因此，对于给定的Imax值，VeMAC的丢包率(Packet Dropping Rate，PDR) PDRVeMAC由下式给出：

(6)

4.2 DTCNC-MAC性能分析

如果RSU没有正确接收数据分组，为了获得较高的重传解码概率，在数据分组的SINR≥3 dB时(此时MIMO_NC解码概率pMIMO_NC大于2/3)，RSU才请求协作编码重传(根据MIMO_NC的BER/SINR表[26]，当SINR<3 dB，编码重传的解码概率pMIMO_NC低于2/3)。

当S1到RSU的数据传输失败时，在S1一跳传输半径r内且与RSU同侧的其它节点(异侧的节点与S1到RSU有着相似的信道特性和条件，且间距更大，协作重发成功概率小，不予考虑)将协作重发数据，设其间的节点数为Nr，用r替换式(1)的l，则Nr等于u的概率为

(7)

式中，u=0，1，2，…。

Pr{Nh>0|Nr=u}=

(8)

在Nr所有条件下，存在协作编码节点的概率为

Pr{Nh>0}=Pr{Nh>0|2

Pr{Nh>0|Nr>F}

(9)

其中，Nh为u-2个节点中满足协作条件节点数。

当2

Pr{Nh>0|2

u}

(10)

当Nr>F时：

Pr{Nh>0|Nr>F}=

(11)

RSU接收数据失败时，可能存在协作节点协作编码重发数据，所以，DTCNC-MAC的成功发送数据的概率为

(12)

(13)

其中，TDDTCNC-MAC为DTCNC-MAC的数据传输时延。

(14)

5 网络仿真

车辆行驶场景用MATLAB进行仿真。假设车辆行驶在方向相反的两条车道上，则道路上车辆密度β=2βm。车辆平均速度为50 km/h，标准偏差为10 km/h。无线信道采用DSRC标准参数，其中，工作频段为5.9 GHz，数据传输速率为24 Mbps。公路旁路侧单元RSU和两跳范围内的车辆已经在VeMAC协议下获得相应时隙，时隙长度为1 ms，每帧中包含60时隙，记为F。仿真参数如表1所示。

表1 模拟参数

对于不同的参数，下面就VeMAC和DTCNC-MAC的成功发送数据的概率、传输时延和数据丢包率进行比较。

在仿真过程中，对于每组参数，500种不同的网络拓扑结构由β值随机产生，在每种拓扑结构上统计105帧的仿真数据，结果取平均值[19- 20]。

仿真结果如图6-9所示。VeMAC成功发送数据的概率取决于信道质量(p)；DTCNC-MAC成功发送数据的概率除决定于信道质量(p)外，还受到车辆密度(β)、传输半径(r)和RSU接收到SINR大于阈值θTH的数据概率pTH，以及RSU解码概率pMIMO_NC的影响。在p=0时，由于信道衰落和多普勒效应等影响导致信道质量非常差，所有分组传输都失败。对于DTCNC-MAC，所有节点都无法从源节点接收数据包，因此无法找到协作节点，因而无法触发协作编码重传，导致PTD为无限大，并且两个协议的PDR都为1。随着p增加，源节点在传输失败时由于协作节点编码重传获得相应的协作分集增益。而在p=1时，由于信道条件良好导致所有分组传输都是成功的，因而源节点的所有分组都成功发送到目标节点，因此不需要协作重传，导致两个协议的PTD为1，PDR为0。

由图6-9可知，相对于VeMAC，DTCNC-MAC显著地提高了数据发送成功概率、减少了数据传输时延和数据丢包率。数据在节点自身时隙内发送失败时，VeMAC必须等待下一帧节点相应时隙才能进行数据重发，而DTCNC-MAC利用协作节点帧内编码重发数据，提高成功发送数据概率、减少数据传输时延和降低数据丢包率。从图6-9可以看出，所有仿真结果都较好的拟合了分析结果。

(a)成功发送数据的概率

(b)数据传输时延

图6 两种方法在不同车辆密度下成功发送数据的概率和传输时延

Fig.6 Probability of successful packet transmission and packet transmission delay in the two methods at different vehicle densities

(a)成功发送数据的概率

(b)数据传输时延

图7 两种方法在不同传输半径下成功发送数据的概率和传输时延

Fig.7 Probability of successful packet transmission and packet transmission delay in the two methods at different transmission radius

(a)成功发送数据的概率

(b)数据丢包率

图8 两种方法在不同pTH下成功发送数据的概率和丢包率

Fig.8 Probability of successful packet transmission and packet dropping rate in the two methods under differentpTH

(a)成功发送数据的概率

(b)数据丢包率

图9 两种方法在不同的pMIMO_NC下成功发送数据的概率和丢包率

Fig.9 Probability of successful packet transmission and packet dropping rate in the two methods under differentpMIMO_NC

在一跳传输半径r(400 m)、概率pTH(0.8)和pMIMO_NC(0.95)固定时，图6(a)表明，车辆密度(β)越大，一跳传输半径内存在的车辆节点就越多，能够进行协作编码重发数据的节点就越多，因而DTCNC-MAC成功发送数据的概率就越大，如p=0.5时，VeMAC成功发送数据的概率为0.5，而DTCNC-MAC成功发送数据的概率为0.708(β=0.02)和0.735(β=0.08)，分别提高41.7%和47.0%；图6(b)表明，车辆密度(β)越大，一跳传输半径内存在的车辆节点就越多，能够进行协作编码重发数据的节点就越多，源节点重发数据的次数就会减少，DTCNC-MAC的数据传输时延就越小，如p=0.5时，VeMAC传输时延为2.010，而DTCNC-MAC传输时延为1.412(β=0.02)和1.361(β=0.08)，分别下降29.8%和32.3%。

在车辆密度β(0.04车/m)、概率pTH(0.8)和概率pMIMO_NC(0.95)固定时，图7(a)表明，一跳传输半径(r)越大，一跳传输半径内存在的车辆节点就越多，能够进行协作编码重发数据的节点就越多，因而DTCNC-MAC成功发送数据的概率就越大；图7(b)表明，一跳传输半径(r)越大，一跳传输半径内存在的车辆节点就越多，源节点重发数据的次数就会减少，DTCNC-MAC的数据传输时延就越小。

在车辆密度β(0.04车/m)、一跳传输半径r(400 m)和pMIMO_NC(0.95)固定时，图8(a)显示，随着概率pTH变大，协作编码需求就会越高，节点协作编码发送数据的几率就越高，DTCNC-MAC成功发送数据的概率就越大；同样，图8(b)显示，DTCNC-MAC数据传输时丢包率就越低。如p=0.4时，VeMAC丢包率为21.8%，而DTCNC-MAC丢包率为7.3%(pTH=0.3)和5.3%(pTH=0.9)，分别下降66.6%和75.6%。

在车辆密度β(0.04车/m)、一跳传输半径r(400 m)和pTH(0.8)固定时，图9(a)显示，随着pMIMO_NC变大，RSU解码概率就越高，DTCNC-MAC成功发送数据的概率就越大；图9(b)显示，随着pMIMO_NC变大，RSU解码概率越高，DTCNC-MAC数据传输时的丢包率就越低。

图10所示为不同Imax值下两种方案的PDR。对于给定的信道条件，DTCNC-MAC的PDR总是小于VeMAC的PDR。随着p增大信道条件变好，DTCNC-MAC和VeMAC的PDR值之间的差距也在增加。当β=0.08时两个协议之间的差距大于β=0.02时的差距。在p=0.4的条件下，当Imax=3时，VeMAC和DTCNC-MAC的丢包率分别是21.8%和7.0%(β=0.02)、5.2%(β=0.08)，分别下降67.9%(β=0.02)和75.9%(β=0.08)；当Imax=5时，VeMAC和DTCNC-MAC的丢包率分别是7.9%和1.2%(β=0.02)、0.7%(β=0.08)，分别下降84.9%(β=0.02)和90.7%(β=0.08)。对于相同的信道条件，Imax值越大，两个协议的PDR值之间的差距越大。在传输失败时，在DTCNC-MAC中，协作节点使用MIMO_NC方法重传分组。因此，更大的Imax意味着DTCNC-MAC中的节点获得比VeMAC更多的重传机会。这增加了数据包在Imax帧内成功传送到目的节点概率，防止在缓冲存储器中被丢弃。

(a)Imax=3 帧

(b)Imax=5帧

图10 不同Imax下DTCNC-MAC和VeMAC的丢包率

Fig.10 Packet Dropping Rate of DTCNC-MAC and VeMAC with differentImax

6 结语

基于分布式TDMA提出一种协作编码数据重发方法，当源节点数据传输失败时，协作节点利用MIMO_NC技术来编码自身业务数据和源节点数据，从而实现协作节点在发送自身数据的同时协作重发源节点数据。该方法利用分布式TDMA本身所包含的信息来确认数据传输结果，同时采用消息搭载机制交换控制信息，避免发送专门的控制分组。方法中所有操作都以分布式方式进行，能够适合VANETs场合。性能分析和实验表明，该方法显著地提高了成功发送数据的概率、有效降低了数据传输时延和丢包率。

文中基于基本的信道模型对所提方法进行了分析和比较；在后续研究中，将进一步研究更加真实的物理信道模型对所提方法性能的影响。