车载自组网中基于分布式TDMA的协作数据重发方法

陈 振 韩江洪

(1合肥工业大学计算机与信息学院,合肥230009)(2安徽大学计算机教学部,合肥230601)

车载自组网中基于分布式TDMA的协作数据重发方法

陈 振1,2韩江洪1

(1合肥工业大学计算机与信息学院,合肥230009)(2安徽大学计算机教学部,合肥230601)

为进一步利用车载自组网中分布式TDMA的节点空闲时隙资源,提出了一种分布式协作数据重发方法,即协作分布式TDMA (cooperative distributed TDMA,Co-DTDMA)方法.利用无线信道的广播特性与分布式TDMA的信道访问确定方式,Co-DTDMA中的信息交互过程能够以一种有序和确定的方式进行,在节点未成功发送数据时,附近的邻居节点利用自身空闲时隙进行协作数据重发,从而在不影响正常数据传输业务情形下,传输失败的数据拥有更多的发送机会.上述协作重发不依赖于中心节点,以分布式方式执行,因而适应车载自组网的应用场合.理论分析与仿真结果表明,Co-DTDMA显著提高了数据包发送成功概率,降低了数据包传输时延和丢包率,显著提高了网络可靠性.

移动自组网;车载自组网;时分多址;可靠性

作为移动自组网(mobile ad hoc networks，MANET)的一种新应用，车载自组网(vehicular ad hoc networks，VANET)吸引了人们越来越多的关注.VANET是智能交通不可或缺的重要基础，能够应用于道路安全、交通优化、信息服务、车载娱乐等多个领域[1].

由于交通事故给人类的生命安全和社会财富造成了巨大威胁，对VANET在安全方面的应用需求显得尤为迫切.由于以竞争方式访问信道，车载通信中的IEEE 802.11p协议无法保证VANET安全应用信息及时可靠地传输[2-3].此外,该协议还会产生“信息碰撞”问题,不能对广播的安全信息进行确认等[4].鉴于竞争型MAC协议的诸多问题,近年来人们一直在积极探索研究VANET中的无竞争型MAC协议[5].由于CDMA比较适合于有中心基站的应用情况,对于无中心、节点快速移动的VANET场合并不适用[6],考虑到VANET中的通信内容和要求,针对VANET场合的分布式TDMA(distributed TDMA)获得了广泛关注[7-11].分布式TDMA不但能够及时稳定地传输VANET安全应用信息,而且相对于IEEE 802.11p,该协议在信道利用率、网络吞吐量和信道访问公平性等方面均获得了较好性能[8-9].

然而,考虑到车辆高速移动,以及车辆或路旁建筑物对无线信号的阻挡等因素,相对于一般的通信环境,车载环境下的无线通信更不可靠[12].在上述分布式TDMA中,由于每个节点独占时隙,如果节点在自身时隙内发送数据失败,即使其他节点时隙空闲,它也只能在以后的自身时隙内重发数据.显然,上述分布式TDMA未能充分利用信道资源,且不能避免由于信道质量差所导致的网络可靠性差问题.

近年来,协作通信在学术界和工业界引起了广泛关注,这种方式利用了无线信道的广播特性,能够有效地修复信道并提高网络可靠性[13].文献[14-16]提出了相关TDMA协作通信方法,但它们都是基于有中心节点的应用场合,且这些方法都未考虑再利用分布式TDMA的节点空闲时隙资源.为此,本文基于分布式TDMA提出一种协作分布式TDMA (cooperative distributed TDMA,Co-DTDMA)方法,通过再利用节点自身空闲TDMA时隙进行协作通信以提高VANET中的通信可靠性.不同于已有的基于中心节点的TDMA协作通信方法,Co-DTDMA所有操作都以分布式方式进行,不依赖中心节点,因而适合用于VANET场合.

1 网络模型

参考相关VANET文献和汽车工业发展趋势,本文作如下假设:

1) 车辆都装有GPS和导航系统,不同车辆可借助GPS脉冲信号实现时间同步.

2) 基于高速公路场景或一维空间公路进行研究,且车辆在公路上服从泊松分布[3-4].设车辆平均密度为β,长度为l的公路上有n辆车的概率为

(1)

3) 用单位圆盘模型表示信道[3-4].设所有车辆的无线一跳传输距离为r.在一跳传输距离内，它们之间能够成功发送数据的概率为p(不考虑信息碰撞)，否则不能够直接通信.

4) 如图1所示，在源节点S发送数据到目标节点D时，附近的其他节点也能成功接收S数据，如果S到D的数据发送失败，附近的其他节点(如节点H2)可以尝试协作重发S数据.

图1 节点H2协作重发源节点S数据

2 利用节点自身空闲时隙协作重发数据

2.1 信道访问

在分布式TDMA中,由于不存在中心节点,各个节点需要交换时隙分配信息来请求确定自身时隙[7-11].每个节点在自身包头中都包含了帧信息(frame information,FI)域[8].设每帧的时隙数为F,则FI实际上含有F个入口的向量,对应了节点所监听到的F个时隙状态.每个时隙只有Busy和Free状态:当节点在一个时隙内正确接收数据包,则在自身包头的FI域中将该时隙标注为Busy状态,否则标注为Free状态.如果时隙为Busy状态,FI还包含在该时隙内发送数据包的源节点标识.参考文献[8],每个节点都采用ID号来标识.在分布式TDMA中,即使节点在自身时隙内不发送实际业务数据,也要发送实际业务数据为空的虚拟数据包(dummy packet),以便和其他节点交换时隙分配信息[7-11].通过与一跳范围内的邻居节点交换FI域，节点获知2跳范围内的邻居节点信息和帧内各时隙的占用情况[7-8].当请求时隙时，节点首先连续侦听F个时隙状态(不必在同一帧内)，随后基于2跳范围内的时隙占用信息选择时隙.

此外，节点的相对移动极大地影响了分布式TDMA的网络性能[8].文献[8-11]基于ADHOC MAC提出了VeMAC方法，将帧内时隙分为3个独立的子集，它们分别对应公路不同方向上的车辆和路旁固定通信设施，从而减少了节点相对移动所造成的影响，提高了网络性能.

在下面研究中，假设网络节点都通过VeMAC请求获得时隙.

2.2 传输确认

FI除提供时隙分配信息外,还提供数据包是否已被正确接收的确认信息.图1中,S在自身时隙内发送数据包到D,若D未成功接收S数据包,则D在随后的自身时隙内所发送的FI域就不含有S的标识信息.因此,当其他节点接收到D发送的FI域时,如果其中未包含S的ID,则判断出D未成功接收S数据包,相当于提供了一个NACK(negative acknowledgement)消息,否则相当于提供了一个ACK消息.

2.3 Coop Header

如图2所示,为了区分节点在自身时隙内是否进行协作数据重发,在分布式TDMA包头中增加了COOP Header域,其中,PHY Header, MAC Header, FI, Payload Data和CRC(cyclic redundancy check)等与分布式TDMA相同.在Coop Header域中,Flag用于标志节点是否进行协作数据重发.

当Flag设置为0时,表明节点发送自身数据(见图2(a));当Flag设置为1时,表明节点进行协作数据重发(见图2(b)).Coop Header域中的Position保存节点自身位置信息,用于确定协作节点范围.此外,如果节点进行协作数据重发,Coop Header还包含了Source ID, Destination ID和Packet Sequence(见图2(b)),它们对应待协作重发数据包的原来源节点标识、包序号和目标节点标识,这些信息标识了待协作重发的数据包.

(a) 节点发送自身数据时的数据包结构

(b) 节点协作重发数据时的数据包结构

2.4 节点间的信息交互

当节点满足以下条件时能成为协作节点：① 成功接收源节点S数据包；② 在自身时隙内不需要发送数据；③ 与目标节点D在S同侧(见图1).

考虑到与目标节点D异侧的节点到D的范围包含了S到D的范围，因而这些节点到D与S到D有着相似的信道特性和条件，而S到D的数据传输已失败，因此选与D同侧的节点为协作节点.此外，与D同侧的节点到D的平均间距也较小.节点从S和D的数据包头中获知S和D的位置信息，基于S,D和自身位置信息，节点判断自身是否与D同侧.

图3以节点D时隙为时间参考点来说明相关节点时隙的时序关系.在以D时隙为时间参考点的第i帧中(D时隙为帧中最前面时隙),假设源节点S在自身时隙内发送数据到D.在第i+1帧内,假设节点H2为满足上述协作通信条件的第1个时隙空闲节点.

图3 协作通信过程中的时序关系示意图

图4给出了节点H2协作重发S数据包过程.图4(a)表明,节点H1,H2,H3在S的一跳范围内,S在第i帧的自身时隙内发送数据包到D时,由于无线信道的广播特性,若它们成功接收S数据包,则将S数据包保存在自身缓存中.图4(b)表明,目标节点D在第i+1帧的自身时隙内发送数据包,如果H1，H2，H3等节点在D数据包头的FI域中未发现S的ID号,则H1，H2，H3等节点判断出D未成功接收S数据包.图4(c)表明,如果H2在第i+1帧的自身时隙前未侦听到其他节点协作重发S数据包,且H2没有数据需要发送,则H2在第i+1帧的自身时隙内协作重发S数据包.如果附近的其他节点侦听到S数据包已被协作重发,则不再进行协作重发.

上述协作过程没有节点充当中心节点的作用，各个节点都是根据一跳范围内信息来决定是否进行协作数据重发，因此上述协作过程是分布式的.此外,考虑到VANET安全应用通常要求在100 ms内将信息传递给附近的目标车辆[3],为保证VANET节点及时传播信息,分布式TDMA的帧时间长度通常设置的很短(几十ms).从源节点发送数据到协作数据重发完成,全过程发生在1～2帧内,由于时间短,节点的相对位置在此过程中几乎不发生变化.上述协作过程为分布式且时间短,因而能适应VANET无中心节点且网络拓扑结构变化频繁的特点.

(a) S发送数据包到D

(b) D发送数据包

(c) H2协作重发S数据包

2.5 网络开销分析

为实现协作数据重发过程，Co-DTDMA在原来的分布式TDMA包头中增加了Coop Header域.由2.3节知,Coop Header域最多包含了Flag标志(1 bit)、节点自身位置(采用经度和纬度表示,均为4 B)、源节点ID、包序号和目标节点ID信息.参考文献[8],将时隙时间设为1 ms,节点ID设置为7 bit,数据包序号长度设置为2 B(数据包序号大于最大序号时,从0开始重新计数).在上述设置下,Coop Header的最大长度为95 bit.参考车辆专用短程通信(DSRC)标准,将VANET中的数据传输速率设为18 Mbit/s,则节点在自身时隙内能够发送18 874 bit数据.由于Coop Header的最大长度远小于节点在自身时隙内能够发送的数据量,因此,相对于Co-DTDMA利用的空闲时隙资源,Coop Header的长度开销可忽略不计.

3 性能分析

3.1 VeMAC性能分析

设ps为VeMAC的一跳范围内数据发送成功概率.由于信道质量(p)和信息碰撞相互独立,因此ps的计算公式为

ps=(1-pc)p

(2)

式中,pc为信息碰撞概率.由2.1节知,pc=0,因此ps=p.

在源节点S发送数据包后,如果目标节点D未成功接收S数据包,通常情况是在等待一预设的固定时间(如timeout)后,S将继续重发数据包,该过程不断重复进行,直到D成功接收S数据包.考虑到数据包每次重发的时间间隔基本相同,下面将数据包传输时延T定义为在D成功接收S数据包前,S尝试发送数据包的次数.S数据包需要经过k次发送才能被D成功接收的概率为

Pr{T=k}=(1-ps)k-1ps

(3)

由于T服从几何分布,因此T均值为

(4)

在通信系统中,若数据包超过最大的预定发送次数M仍未被正确接收,则通常会丢掉该包.经过M次发送,S数据包仍没有被D成功接收的概率即为丢包率 (PDR),其计算公式为

(5)

3.2 Co-DTDMA性能分析

当S到D的数据包传输失败时,在S的一跳范围内且与D同侧的其他节点将协作重发数据包,设此期间的节点数为Nr,则

(6)

Pr{Nh=0Nr=u}=

(7)

当Nr=u时,存在协作节点的概率为

(8)

在所有可能条件下,存在协作节点的概率为

Pr{Nh>0}= Pr{Nh>02

Pr{Nh>0Nr>F}

(9)

当2

Pr{Nh>02

(10)

当Nr>F时,

Pr{Nh>0Nr>F}=

(11)

S发送数据包失败时,可能存在协作节点协作重发数据包,因此Co-DTDMA的数据包发送成功概率为

(12)

(13)

(14)

4 网络仿真

用Matlab仿真一段公路车辆行驶场景.公路有2条方向相反的车道,每条车道上车辆服从泊松分布,设每车道的车辆密度为βl,则公路车辆密度β=2βl.车辆平均速度为80 km/h,标准偏差为20 km/h.帧内时隙数F为60.VeMAC把帧内时隙分为3个不相交的子集,分别对应了朝相反方向行驶的车辆和路旁固定通信设备,本文不考虑路旁固定通信设备,因此每车道对应的时隙数为30.下面在不同参数下仿真比较VeMAC与Co-DTDMA的性能.在仿真过程中,对于每组参数,根据其中的β值随机生成500种不同的网络拓扑结构,并在每种拓扑结构上抽取1.0×105帧的仿真数据进行统计,结果取均值.

图5为2种方法的数据包发送成功概率比较.VeMAC数据包发送成功概率取决于信道质量p,Co-DTDMA数据包发送成功概率除取决于p外,还受到节点发送数据概率pd、车辆密度β和一跳传输距离r的影响.图5表明,相对于VeMAC,Co-DTDMA显著地提高了数据包发送成功概率,这是由于Co-DTDMA能够利用附近节点空闲时隙协作重发传输失败的数据包.

(a) 不同β值

(b) 不同pd值

(c) 不同r值

图5(a)表明,当r=200 m和pd=0.5时,车辆密度β越大,源节点一跳范围内的邻居节点就越多,从而能够协作重发数据包的节点就越多,Co-DTDMA数据包发送成功概率就越大.

图5(b)表明,当r=200 m和β=0.04 veh/m时,节点发送数据概率pd越大,拥有空闲时隙的节点就越少,从而能够协作重发数据包的节点就越少,Co-DTDMA数据包发送成功概率就越小.

图5(c)表明,当pd=0.5和β=0.04 veh/m时,一跳传输距离r越大,源节点一跳范围内的邻居节点就越多,从而能够协作重发数据包的节点就越多,Co-DTDMA数据包发送成功概率就越大.

图5表明,随着p增大,VeMAC与Co-DTDMA的数据包发送成功概率不断增大.当p=0时,信道质量差,所有数据发送失败,2种方法的数据包发送成功概率为0;当p=1时,信道质量好,所有数据发送成功,2种方法的数据包发送成功概率为1.此外,随着p增大,Co-DTDMA数据包发送成功概率有着相似的变化曲线.为此,下面对Co-DTDMA数据包发送成功概率的性能增量进行规格化处理:

(15)

图6为r=200 m、pd=0.5、β=0.06 veh/m时的Co-DTDMA性能增量规格化曲线.由图可见,当p<0.2时,信道质量较差,Co-DTDMA数据包发送成功概率的性能增量随着信道质量的改善而显著增加;当0.2≤p≤0.5时,Co-DTDMA数据包发送成功概率的性能增量超过40%;当p>0.5时,随着信道质量的进一步改善,由于协作重发的必要性降低,Co-DTDMA数据包发送成功概率的性能增量变小.

图6 Co-DTDMA的数据包发送成功概率性能增量规格化图

图7比较了r=200 m、pd=0.5时2种方法的数据包传输时延.在信道质量较差时,相对于VeMAC,Co-DTDMA传输时延的降低幅度超过了30%.如当p=0.3时,VeMAC平均传输时延为3.4帧,Co-DTDMA平均传输时延为2.1帧(β=0.06 veh/m时)和2.3帧(β=0.03 veh/m时).在源节点发送数据包失败时,Co-DTDMA利用其他节点空闲时隙协作重发数据包,在这种情况下,源节点重发数据包的次数就会减少,从而减小了数据包传输时延.当信道质量越来越好(p不断增大)时,协作重发的必要性变小,2种方法的传输时延差异也变小.此外,协作重发的发生概率越大(β越大),Co-DTDMA传输时延越小.

图7 2种方法的数据包传输时延比较

图8比较了r=200 m、pd=0.5时2种方法的丢包率,图8(a)、(b)中数据包最大发送次数M分别取值为1和3.在不同信道质量下,Co-DTDMA丢包率始终低于VeMAC,且随着M增大,2种方法的性能差异越大.如p=0.5、β=0.06 veh/m时,图8(a)中VeMAC丢包率为50%,Co-DTDMA丢包率为37%;图8(b)中VeMAC丢包率为13%,Co-DTDMA丢包率降低到2%以下.在源节点发送数据包失败时,Co-DTDMA利用附近节点空闲时隙协作重发数据包,M增大时,Co-DTDMA拥有更多的机会重发数据包,从而拥有更多的机会防止数据包被丢弃,因此,随着M增大,2种方法的性能差异越大.此外,协作重发的发生概率越大,Co-DTDMA丢包率越小.

5 结论

1) 基于分布式TDMA提出了一种利用节点自身空闲时隙进行协作数据重发的方法,当源节点未成功发送数据时,附近的邻居节点利用自身空闲时隙协作重发数据.由于仅利用节点自身空闲时隙进行协作数据重发,该方法未影响正常数据传输业务.

2) 仿真结果表明,由于利用节点空闲时隙进行协作数据重发,该方法显著地提高了数据包发送成功概率,降低了数据包传输时延和丢包率,从而显著地提高了网络可靠性.

(a) M=1

(b) M=3

3) 该方法在协作重发时不依赖于中心节点,以分布式方式执行,因此适用于VANET应用场景.

本文基于基本信道模型(单位圆盘模型)对所提方法进行了性能分析和仿真比较,以后将研究更加真实的信道模型对该方法性能的影响.

References)

[1]Sarakis L, Orphanoudakis T, Leligou H C, et al. Providing entertainment applications in VANET environments [J].IEEEWirelessCommunications, 2016, 23(1):30-37. DOI:10.1109/mwc.2016.7422403.

[2] Jiang D, Delgrossi L. IEEE 802.11p: Towards an international standard for wireless access in vehicular environments [C]//VTCSpring2008—IEEEVehicularTechnologyConference. Calgary, Canada, 2008:2036-2040. DOI:10.1109/vetecs.2008.458.

[3] Ma X M, Zhang J S, Yin X Y, et al. Design and analysis of a robust broadcast scheme for VANET safety-related services [J].IEEETransactionsonVehicularTechnology, 2012, 61(1):46-61. DOI:10.1109/tvt.2011.2177675.

[4] Yao Y, Rao L, Liu X. Performance and reliability analysis of IEEE 802.11p safety communication in a highway environment [J].IEEETransactionsonVehicularTechnology, 2013, 62(9):4198-4212. DOI:10.1109/tvt.2013.2284594.

[5] Dharsandiya A N, Patel R M. A review on MAC protocols of Vehicular Ad Hoc Networks [C]//2016InternationalConferenceonWirelessCommunications,SignalProcessingandNetworking. Chennai, India, 2016:1040-1045. DOI:10.1109/wispnet.2016.7566295.

[6] Hadded M, Muhlethaler P, Laouiti A, et al. TDMA-based MAC protocols for vehicular ad hoc networks: A survey, qualitative analysis, and open research issues [J].IEEECommunicationsSurveys&Tutorials, 2015, 17(4):2461-2492.

[7] Borgonovo F, Capone A, Cesana M, et al. ADHOC MAC: New MAC architecture for ad hoc networks providing efficient and reliable point-to-point and broadcast services [J].WirelessNetworks, 2004, 10(4):359-366. DOI:10.1023/b:wine.0000028540.96160.8a.

[8] Omar H A, Zhuang W H, Li L. VeMAC: A TDMA-based MAC protocol for reliable broadcast in VANETs [J].IEEETransactionsonMobileComputing, 2013, 12(9):1724-1736. DOI:10.1109/tmc.2012.142.

[9] Omar H A, Zhuang W H, Li L. On multihop communications for in-vehicle Internet access based on a TDMA MAC protocol [C]//IEEEINFOCOM2014—IEEEConferenceonComputerCommunications. Toronto, Canada, 2014:1770-1778. DOI:10.1109/infocom.2014.6848115.

[10] Omar H A, Zhuang W H, Li L. Gateway placement and packet routing for multihop in-vehicle Internet access [J].IEEETransactionsonEmergingTopicsinComputing, 2015, 3(3):335-351. DOI:10.1109/tetc.2015.2395077.

[11] Omar H A, Lu N, Zhuang W H. Wireless access technologies for vehicular network safety applications [J].IEEENetwork, 2016, 30(4):22-26. DOI:10.1109/mnet.2016.7513860.

[12] Boban M, Vinhoza T T V, Ferreira M, et al. Impact of vehicles as obstacles in vehicular ad hoc networks [J].IEEEJournalonSelectedAreasinCommunications, 2011, 29(1):15-28. DOI:10.1109/jsac.2011.110103.

[13] Zhou Y, Zhuang W H. Throughput analysis of cooperative communication in wireless ad hoc networks with frequency reuse [J].IEEETransactionsonWirelessCommunications, 2015, 14(1):205-218. DOI:10.1109/twc.2014.2335732.

[14] Yang Z, Yao Y D, Li X C, et al. A TDMA-based MAC protocol with cooperative diversity [J].IEEECommunicationsLetters, 2010, 14(6): 542-544. DOI:10.1109/lcomm.2010.06.092451.

[15] Yuan G X, Peng M G, Wang W B. Opportunistic user cooperative relaying in TDMA-based wireless networks [J].WirelessCommunicationsandMobileComputing, 2012, 10(7):972-998. DOI:10.1002/wcm.811.

[16] Hu N S, Yao Y D, Yang Z. Analysis of cooperative TDMA in Rayleigh fading channels [J].IEEETransactionsonVehicularTechnology, 2013, 62(3):1158-1168. DOI:10.1109/tvt.2012.2229307.

Cooperative retransmission based on distributed TDMA for VANET

Chen Zhen1,2Han Jianghong1

(1School of Computer and Information, Hefei University of Technology, Hefei 230009, China) (2Department of Computer Teaching, Anhui University, Hefei 230601, China)

To further utilize the idle time slots of the distributed TDMA (time division multiple address) for VANET (vehicular ad hoc networks), a distributed cooperative retransmission scheme, referred to as cooperative distributed TDMA (Co-DTDMA), is presented. Based on the broadcasting nature of wireless medium and the determinate way that the distributed TDMA accesses channel, nodes can interact with each other orderly and determinately in Co-DTDMA. When a node fails to transmit a packet, neighboring nodes exploit their idle slots for retransmitting the failed packet cooperatively, and thus the failed packet has more chance to be transmitted, without interrupting the normal packet transmissions. The cooperative retransmission does not rely on any central node, and is performed in a distributed manner, which makes it suitable for VANET. The numerical and simulation results demonstrate that Co-DTDMA significantly increases the probability of successful packet transmission, decreases the packet transmission delay and packet dropping rate, thus significantly increasing the network reliability.

mobile ad hoc networks; vehicular ad hoc networks; time division multiple access (TDMA); reliability

10.3969/j.issn.1001-0505.2017.04.003

2016-12-26. 作者简介: 陈振(1980—)，男，博士生；韩江洪(联系人)，男，教授，博士生导师，czahu@163.com.

国家自然科学基金资助项目(61370088，61502142)、安徽省自然科学基金资助项目(1408085MKL80).

陈振，韩江洪.车载自组网中基于分布式TDMA的协作数据重发方法[J].东南大学学报(自然科学版),2017,47(4):642-648.

10.3969/j.issn.1001-0505.2017.04.003.

TP393.0

A

1001-0505(2017)04-0642-07