改进的VANET分布式自适应时分多址分配机制①

王梦雪,徐哲鑫,吴 怡,林 潇

(福建师范大学 光电与信息工程学院,福州 350007)

1 引言

车载自组织网(Vehicular Ad-hoc Network,VANET)[1]具有节点高移动性、拓扑高动态性及节点轨迹规律性等特点,使得介质访问控制(Medium Access Control,MAC)协议成为VANET研究的重点之一[2–4].目前,车载自组织网MAC协议主要分成基于“竞争”的、基于“非竞争”的[5].基于“竞争”的MAC协议以CSMA/CA(Carrier Sense Multiple Access with Collision Avoidance)为基础,其中最为经典的是IEEE 802.11p协议[6–8].IEEE 802.11p协议被批准成为VANET 标准MAC协议之一,但是其随机性的信道接入机制导致接入延迟无界,难以精确预估.另外,当车辆节点密度高时,信道冲突急剧增加,导致吞吐量和传输延迟性能严重恶化[9].基于“非竞争”的MAC协议[10,11]中,车辆节点依照一定规则有序使用信道资源,其中以时分多址(Time Division Multiple Access,TDMA)机制应用最为广泛.TDMA[12]机制将频率信道从时间维度上划分为连续时间帧,每一个时间帧又分割成若干个固定时长的时隙,节点以时隙为信道接入的基本单位.TDMA机制主要分为集中式和分布式两大类[13].相比于集中式TDMA需要中心控制器集中分配时隙,分布式 TDMA 无需中心控制器,节点以一定的秩序自主分配时隙的机制显然更加灵活,更加适应于拓扑高度变化的VANET.

ADHOC MAC协议[14]是经典的分布式TDMA MAC协议,以RR-ALOHA协议[15]为基础.车辆节点间通过交互帧信息(Frame Information,FI),其中包含一跳邻居节点时隙占用信息,获知其两跳范围内邻居节点的时隙占用信息,并随机选择一个空闲时隙竞争接入信道.ADHOC MAC协议解决了隐藏节点的问题,但在拓扑变化较频繁和节点密度较高的场景下,信道接入冲突较为严重.其后续改进的版本[16,17]主要解决ADHOC MAC协议时隙利用率较低的问题,并没有解决密集场景下信道冲突严重的问题.

VeMAC协议[18]在ADHOC MAC协议的基础上,为不同行驶方向的车辆节点与路边基础设施(Road-Side Unit,RSU)分配不同的时隙集LRF,降低对向行驶的车辆节点间信道冲突的可能性,提高通信链路生存期.VeMAC协议存在的问题是同向车辆节点间仍然随机地选择空闲时隙来竞争接入信道,当节点密度较高时,由于时隙集的划分导致节点可用空闲时隙范围变小,信道接入性能严重恶化.

文献[19]提出分布式自适应TDMA调度策略(Decentralized Adaptive TDMA Scheduling strategy,DATS).DATS协议车辆节点根据自己与最近车辆节点的相对位置关系竞争对应的空闲时隙.DATS协议利用车辆节点行驶方向与地理位置的差异性,有效缓解VeMAC协议随机选择空闲时隙造成的信道冲突严重的问题.但由于车辆节点的运动受限于道路环境和交通法规,当多个地理位置接近的车辆节点同时进入网络时,DATS协议通过对时隙子集中剩余空闲时隙均分后随机获取完成新加入节点时隙分配,然而这种随机性在高节点密度时将导致严重的冲突.此外,DATS协议根据实时车辆密度变化,动态调整不同行驶方向车辆节点左右时隙集时隙数的节点协商机制较为复杂,不适应于拓扑快速变化的VANET.

为了解决DATS协议中多节点同时接入信道时的竞争冲突问题,本文提出改进的分布式自适应时分多址分配机制(Modified Decentralized Adaptive TDMA Scheduling mechanism,MDATS).MDATS主要借鉴空分多址(Space Division Multiple Access,SDMA)的思想,根据可用空闲时隙数将同向最近已接入信道节点的通信区域均分为若干逻辑区段.车辆节点根据自己的地理位置信息,以及逻辑区段与空闲时隙的映射关系选择对应的空闲时隙竞争接入信道.MDATS协议通过逻辑区段与空闲时隙的映射关系,将位置接近且同时接入网络的车辆节点竞争的时隙在空间上分散化,达到提高信道接入成功率和降低信道接入延迟的目的.同时,MDATS协议摒弃了DATS协议中复杂的左右时隙集时隙数协商调整机制.MDATS协议中,当节点发现可用空闲时隙集为空,即无空闲时隙可用时,允许该节点将对向道路对应的空闲时隙集作为自己的可用空闲时隙集,达到扩展可用空闲时隙集,提高时隙利用率的目的.

2 系统模型

2.1 场景设定

道路上每隔一定距离铺设路边基础设施(Road-Side Unit,RSU),为其覆盖范围内的车辆节点周期性地广播道路基本信息、帧结构信息、网络基本信息等.每个车辆节点均配备车载通信单元(Onboard Unit,OBU)、全球定位系统(Global Positioning System,GPS)等设备.车辆节点通过GPS定位系统周期性获取精确的地理位置信息,判断行驶方向,同时通过GPS模块提供的1PPS信号实现车辆节点间的时钟同步.

本文主要考虑双向四车道的城市道路场景.为了降低对向行驶的车辆节点间的信道冲突的概率,本文将每帧的时隙划分为左时隙集SL和右时隙集SR,分配给不同行驶方向的车辆节点.如图1所示,车辆行驶方向定义如下:以南北方向线为基准,车辆节点行驶方向位于其左边定义其行驶方向为左;车辆节点行驶方向位于其右边的定义其行驶方向为右,如图1所示.因此,左时隙集SL和右时隙集SR分别分配给左行驶方向R的车辆节点和右行驶方向DR的车辆节点进行信道接入.

图1 时隙规划图

车辆节点仅接收通信半径R范围内的邻居节点(即一跳邻居节点)发送的信号,通信范围之外节点的信号默认无法接收.但隐藏节点的问题仍然存在,导致节点同时接收通信范围内多个邻居节点发送的信号而无法正确解析信号,造成信道冲突.

2.2 帧信息FI

为了保证道路环境的安全性,每个车辆节点必须周期性地广播自己的位置、速度、方向信息为安全应用提供服务.此外,为了保证车辆节点能够获知其两跳邻居节点的时隙占用信息,每个车辆节点还必须周期性地发送帧信息[14],其中包含节点自己及其一跳邻居节点的时隙占用信息.

对于每个节点而言,空闲时隙定义为未被其两跳邻居节点占用的时隙.同时,MDATS协议中定义新加入节点为初始接入网络,还未成功占用时隙的节点;成功节点定义为已成功占用时隙的节点.一旦节点成功占用一个时隙,即无冲突地接入信道,则在接下来的每帧里该节点都将占用相同的时隙,直至发生信道冲突或该节点无通讯需求时才释放该时隙.

图2 MDATS协议总体流程

MDATS协议针对节点X定义以下5类相关集合:

list(X):节点X的一跳邻居节点运动状态信息列表,具体内容包括其一跳邻居节点的ID、位置信息、速度、行驶方向以及所占用的时隙号.

TL(X):节点X两跳邻居节点中行驶方向为左的节点所占用的时隙号.

TR(X):节点X两跳邻居节点中行驶方向为右的节点所占用的时隙号.

IL(X):左时隙集SL中节点X可用空闲时隙号.

IR(X):右时隙集SR中节点X可用空闲时隙号.

3 MDATS时隙分配机制

MDATS时隙分配机制可分为初始化过程、逻辑区段-空闲时隙映射过程、时隙分配过程和可用空闲时隙集扩展的过程,其详细的机制流程如图2所示.

3.1 初始化过程

新加入节点X根据GPS定位系统获得自己的位置信息(x,y),判断其行驶方向dr.当节点X 初始接入网络时,首先侦听信道一帧的时长,接收其一跳邻居节点发送的运动状态信息与FI消息.节点X根据一跳邻居节点的运动状态信息,维护运动状态信息列表list(X)={(id1,x1,y1,v1,dr1,s1),···,(idn,xn,yn,vn,drn,sn)},其中idi、xi、yi、vi、dri、si(i=1,2,…,n)分别为节点X的一跳邻居节点i的ID、位置坐标、速度、行驶方向以及所占用的时隙号.同时,节点X根据一跳邻居节点广播的FI 消息,收集其两跳邻居节点的时隙占用信息TL(X)、TR(X),从而可计算出左空闲时隙集和右空闲时隙集,且分别定义IL(X)、IR(X)对应的空闲时隙数分别为NLI(X)、NRI(X).

节点X根据自己的行驶方向dr选择对应的空闲时隙集IL(X)或IR(X)作为可用空闲时隙集.节点X检查list(X)是否为空集,即节点X是否有一跳邻居节点.若list(X)为空集,则节点X从可用空闲时隙集IL(X)或IR(X)中随机选择一个空闲时隙进行信道接入;若list(X)不为空集,则节点X根据list(X)计算距离自己最近的同向成功节点,计算公式如下:

其中,(x′,y′)为节点X相同行驶方向上的一跳邻居节点的位置信息,即(x′,y′)∈list(X)且dr′=dr.

若节点X根据公式(1)得到多个距离相等的最近同向成功节点,即节点X位于最近同向成功节点的中间.节点X选择占用时隙号最小的最近同向成功节点作为参考节点.

3.2 逻辑区段-空闲时隙映射过程

假设节点X的参考节点为Y,则将节点Y通信区域均分为M个逻辑区段.当 X ∈DL时,M=NLI(X);当X∈DR时,M=NRI(X).其中逻辑区段1～M沿节点所在车道行驶方向连续排列,空闲时隙依照时隙号由小到大,且沿车道行驶方向排列,逐一对应于相应的逻辑区段,形成逻辑区段-空闲时隙映射表.

3.3 时隙分配过程

节点X判断自己位于参考节点的第m个逻辑区段,则根据逻辑区段-空闲时隙映射表选择在逻辑区段m对应的空闲时隙tm竞争接入信道,其中m∈ {1,2,3,···,M}.节点X的一跳邻居节点在时隙tm成功接收到节点X发送的数据后,将自己FI消息中时隙tm标识为节点X的ID.若节点X在接下来一帧时长内接收的所有的FI消息中时隙tm均标识为节点X的ID,则表示节点X成功占用时隙tm.否则表示节点X未成功占用时隙tm,与其他车辆节点发生信道冲突,则当下一帧到来时,节点X从对应空闲时隙子集中随机选择一个空闲时隙竞争信道.

若节点X成功占用时隙tm,则在接下来的每帧中都使用该时隙,直至发生信道冲突或该节点无通讯需求时,才释放该时隙.

3.4 可用空闲时隙集扩展过程

节点X发现其可用空闲时隙集为空,即无空闲时隙可用,则节点X可将另一个行驶方向对应的空闲时隙集扩展为自己可用的空闲时隙集,并从中随机选择一个空闲时隙竞争接入信道.

图3表示了MDATS协议详细的时隙分配示意图,车辆节点A、E、F、G为成功节点且分别占用时隙7、时隙2、时隙3、时隙4.假设车辆节点B、C、D为右行驶方向上的新加入节点且同时准备接入网络.为了更加简洁明了地介绍MDATS时隙分配过程,首先以车辆节点B为例详细分析时隙占用过程.

车辆节点B根据GPS定位系统获得地理位置信息,判断自己的行驶方向为右.当车辆节点准备接入网络时,首先在信道上侦听一帧的时长,通过接收车辆节点A、E、F、G的FI消息,获知TL(B)={2,3,4},TR(B)={7},故而能够计算出IL(B)={1,5},IR(B)={6,8,9,10}.由于车辆节点B其行驶方向为右,故选择空闲时隙集IR(B)作为可用空闲时隙集,可用空闲时隙数NRI=4.同时,根据公式(1)计算得知其同向最近的成功节点为车辆节点A,则将车辆节点A通信区域沿着道路方向划分为4个相等的逻辑区段,将逻辑区段与IR(B)的空闲时隙号进行一一映射,形成逻辑区段-空闲时隙映射表.车辆节点B判断自己位于逻辑区段1,则根据逻辑区段-空闲时隙映射表选择与逻辑区段1对应的空闲时隙6来竞争接入信道.同理,由于车辆节点C、D与车辆节点B同时接入网络,根据公式(1)计算同向最近的成功节点也是车辆节点A,故逻辑区段-空闲时隙映射表与车辆节点B的相同.车辆节点C、D判断自己的行驶方向为右,分别位于逻辑区段3与逻辑区段4,故车辆节点C选择竞争接入时隙9,车辆节点D选择竞争接入时隙10.

4 性能仿真与分析

本文利用交通流仿真软件SUMO(Simulation of Urban Mobility)[20]和Matlab工具构建VANET仿真环境.SUMO是一个微观的、多模态的、空间连续的、时间离散的交通流仿真平台,通过道路环境和车辆行驶模型的设定生成相应交通流数据.仿真过程中,首先利用SUMO工具生成交通流数据,将其导入Matlab中构建VANET的通信环境,仿真VAENT MAC协议.本文所选的对比对象为DATS协议[19]、VeMAC协议[18]、ADHOC MAC协议[14].仿真参数如表1所示,仿真场景示意图如图4所示,本文采用3 km×3 km曼哈顿网格为道路拓扑形状,双向四车道的道路场景如图3.

图3 MDATS时隙分配示意图

图4 仿真场景

表1 网络性能仿真参数设置

假设,每帧时长为Tframe,帧数为n,每帧的时隙数量为N,新加入节点数为K.图5表示n帧内所有新加入节点成功获得时隙的概率.当N=20,K=20时,若要保证9 5%以上的新加入节点成功获得时隙,MDATS协议和DATS协议都需要4个帧长,即时延τ=4·Tframe;VeMAC协议需要 5个帧长,时延τ=5·Tframe;ADHOC MAC协议需要6个帧长,时延τ=6·Tframe.当N=64,K=50时,若要保证95%以上的新加入节点成功获得时隙,MDATS协议和DATS协议都需要3个帧长,即时延 τ=3·Tframe;VeMAC协议需要4个帧长,时延 τ=4·Tframe;ADHOC MAC协议需要4个帧长,时延 τ=4·Tframe.MDATS协议相比于DATS协议,虽然整体时延相近,但在相同时间维度时,MDATS协议有更多数量的节点成功获得时隙.因为MDATS协议将地理位置相近且同时接入网络的新加入节点选择的空闲时隙分散化,降低信道冲突的概率.MDATS协议相对于VeMAC协议至少能减少20%的接入时延,而比ADHOC MAC协议至少能减少30%的接入时延.

图6表示每个帧成功获取时隙节点的平均数目,即平均成功节点数.由图6可以看出,当N=100,K=100时,MDATS协议在5帧内就能够让所有新加入节点都成功接入信道,而DATS协议需要6帧,VeMAC协议与ADHOC MAC协议则需要12帧.当N=100,K=50时,MDATS协议在3帧内就能够让所有新加入节点都成功接入信道,而DATS协议需要4帧,VeMAC协议与ADHOC MAC协议则需要5帧.因此,当N＞K时,MDATS协议能够使车辆节点相比于其他三类MAC协议更加快速地接入信道,且平均成功节点数更多.当N=K时,MDATS协议的优势就更为明显.

图5 n帧内所有节点成功获得时隙的概率

图6 平均成功节点数

图7则是比较了不同节点密度下,MDATS、DATS、VeMAC、ADHOC MAC四种MAC协议在冲突节点数上的对比.相同节点密度的场景下,MDATS协议比DATS协议降低至少40%的冲突节点数,比VeMAC协议降低至少50%的冲突节点数,比

ADHOC MAC协议降低至少60%的冲突节点数.其原因在于,MDATS协议通过借鉴空分多址的概念,将新加入节点竞争的空闲时隙在空间上分散化,降低信道冲突的概率.而DATS协议仅是将相对位置和行驶方向作为新加入节点竞争的空闲时隙的依据,竞争时隙选择范围较小,比MDATS协议更易发生信道冲突.VeMAC协议和ADHOC MAC协议则是完全随机地选择空闲时隙来竞争接入信道,信道冲突概率比DATS协议更高.

图7 冲突节点数

5 结束语

本文针对VANET环境下,为了解决DATS协议中多节点同时接入信道时的竞争冲突问题,提出改进的分布式自适应时分多址分配机制.MDATS协议借鉴空分多址的概念,新加入节点根据可用空闲时隙集的空闲时隙数将同向最近成功节点的通信区域划分为若干逻辑区域,并形成逻辑区域与空闲时隙的映射关系.新加入节点根据逻辑区域-空闲时隙映射关系,则竞争接入相应的空闲时隙.MDATS协议将位置接近且同时接入网络的新加入节点所竞争的时隙分散化,缓解信道冲突严重的情况.同时,在MDATS协议利用可用空闲时隙扩展过程代替了DATS协议复杂的左右时隙比例协商调整机制,当节点发现自己的可用空闲时隙集为空,即无空闲时隙可用时,可将对向道路空闲时隙集作为自己的扩展可用空闲时隙集使用,以提高时隙利用率.由仿真结果可得,MDATS协议中的车辆节点相比于DATS协议接入时延更小,节点能够更加快速地接入信道,信道冲突率更低;当节点密度相同时,MDATS协议相比于DATS协议降低至少40%的冲突节点数;MDATS协议与VeMAC协议、ADHOC MAC协议相比,网络性能提升更为显著.