VANET中基于碰撞概率和过期概率的自适应退避算法研究*

刘委婉，陈志佳，刘南杰，仲 浩，赵海涛

（1.南京邮电大学通信与信息工程学院 南京210003；2.南京邮电大学网络基因工程研究所 南京210003；3.国网上海市电力公司信息通信公司 上海200122；4.江苏有线数据网络有限公司 南京210003）

1 引言

车载自组织网络[1]（vehicular Ad Hoc network，VANET）(以下简称车载网）作为智能交通系统的基本组成部分，是指在交通道路上车辆之间、车辆与固定接入点之间相互通信组成的移动Ad Hoc网络。提供车辆与车辆（vehicle-tovehicle，V2V）、车辆与基础设施（vehicle-to-infrastructure，V2I）之间的相互通信，用于传递辅助驾驶或避免事故的实时信息或提供娱乐信息、Internet接入等数据服务，为实现安全便捷驾驶提供了强大的通信支持，在事故预警、保障交通安全以及优化交通流量等方面发挥了重要作用。

IEEE 802.11p[2]协议是WAVE（wireless access in vehicular environment）协议栈的底层协议，它是IEEE 802协议族的新成员，专门用于支持车载网下的应用。目前IEEE 802.11p协议仍然处于草案阶段。IEEE 802.11p将信道分为7个子信道，每个子信道是10 MHz，在5.9 GHz的频谱之上，如图1所示。每个子信道拥有27 Mbit/s的带宽，保护间隔是IEEE 802.11a的两倍，信号传输的范围能够延伸到1 km。IEEE 802.11p的物理层采用的是IEEE 802.11a传输技术。MAC层采用两种访问机制：基本接入协议是基于IEEE 802.11的DCF（distributed coordination function,分布式协调功能）机制，该机制不区分消息的优先级，节点应该在指定的时间间隔内，利用载波侦听机制判断信道是否空闲，通过退避减少消息间的碰撞；扩展层接入协议是基于IEEE 802.11e的EDCA机制[3]，通过EDCA（enhanced distributed channel access）机制，IEEE 802.11p可以将不同的数据流按优先级分成不同的接入类别，这样可以保证车载应用的服务质量。EDCA定义了4个不同的接入类别，分别对应于MAC层的4个传输队列。由于本文研究的是车辆间传输的信标信息，该消息不需要区分消息优先级类别，因此本文重点研究DCF接入机制。

信标消息又叫做合作性提醒消息（cooperative awareness message，CAM），与分布式紧急消息通知（decentralized emergency notification，DEN）的不同之处在于，它不需要任何的触发机制，每隔一定的时间都会向周围的车辆广播一次自身的行驶速度、方向、位置等信息，并且它的生命周期是有限的。因此，在车载网中需要采取有效的退避机制来保证信标消息能够实时准确地传递给周边车辆。本文针对车载网中信标消息的特性，根据分组丢失中过期消息数与预先设定门限值的相对大小提出一种新的退避算法CEB（collision-expiration back-off）。

2 相关工作

IEEE 802.11 DCF的核心是带冲突检测的载波侦听多址接入（CSMA/CA）协议及随机退避机制。DCF接入机制为：当某个站点需要传输数据分组时，它首先侦听信道直到检测到信道的空闲时长达到DIFS为止。在这DIFS媒体空闲时间之后，节点开始在[0,CWmin-1]随机选择时间进行退避，当退避计数器为0时节点开始传输数据分组[4]。DCF采取二进制指数退避（binary exponential back-off，BEB）算法[5]来选择退避时间。在该算法中，节点在每次碰撞后会将竞争窗口（contention window，CW）值增大一倍，直到CW达到最大竞争窗口（maximum contention window，CWmax）值为止，当节点成功传输一个信号时，就将当前的CW值恢复为CWmin。Li J等人在参考文献[6]中指出，IEEE 802.11 DCF在处理大量竞争节点尤其是隐藏节点存在的网络时，性能很差；Stanica R等人在参考文献[7]中对BEB算法进行了改进，根据信标消息过期的特性提出了RBEB算法。在RBEB算法中，最小竞争窗口的初始值设置得相对较大，每当有消息过期时就将竞争窗口值减半，直到达到IEEE 802.11p规定的最小值为止。一旦成功传输一个信标消息，最小竞争窗口值就恢复为初始值。但是该算法主要存在以下几个缺点。

·退避初始时将最小竞争窗口值设置得过大会增加信标消息的时延。

·每当有消息过期时就将竞争窗口值减半，竞争窗口值变化幅度过大，不能很好地反映当前网络信道的竞争情况。

图1 IEEE 802.11p频谱段和信道分配

·没有考虑消息碰撞概率对网络性能的影响。魏李琦等人在参考文献[8]中指出车辆间的相对速度对于信道接入的公平性有重要影响，并提出基于相对速度的退避算法，该算法相对于BEB算法具有一定程度的改进。

纵观近年来车载网中信标消息接入机制的研究工作，关于碰撞概率和过期概率对于信标消息性能的影响并没有给予足够的重视，尤其是在V2V通信模式下联合考虑碰撞消息和过期消息对最小竞争窗口进行调整的问题。本文在RBEB算法的基础上，根据其算法的不足并结合参考文献[8]中的研究方法，提出一种新的基于碰撞消息概率和过期消息概率的退避算法CEB。

本文的贡献如下。

·建立马尔可夫链模型推出信标消息中碰撞概率与过期概率随最小竞争窗口的变化关系。

·结合碰撞概率和过期概率与最小竞争窗口的关系提出一种新的退避算法CEB。

·通过NS2和VanetMobiSim联合仿真，就广播接收率和平均到达时延的性能，将CEB算法与BEB算法及参考文献[7]中提出的RBEB算法进行了比较。

3 信标消息性能建模

为了能够更好地理解信标消息的特性（考虑信标消息具有有限的生命时长），通过建立如图2所示的马尔可夫链模型进行分析。

马尔可夫状态转移概率为：

W0为最小竞争窗口值。在退避阶段，节点会从[0,W0-1]随机选择值进行退避。

（1）单独考虑某一时刻(t=i)的退避过程，一阶马尔可夫链的平稳概率为：

其中：

解式（2）得：

设τ为节点在该时刻进行信息传输的概率，则：

不考虑信道存在误码的情况，有：

其中，Pc为消息产生碰撞的概率，Ps为消息成功传输的概率，Pb为信道繁忙的概率：

（9）

（2）考虑多个时刻时，由参考文献[7]知：

其中，Pe为信标消息过期的概率，表 示t=i时 退 避值为1的概率。根据式（9）和式（10）可知，当增大竞争窗口W0时，消息的碰撞概率Pc会减小，而消息的过期概率Pe会增加。

综上所述，可以得出如下结论：当竞争窗口在一个较小范围时，消息的碰撞概率大于消息的过期概率，而碰撞概率会随着竞争窗口的增大而减小，因此为了增加广播的接收率应该增加最小竞争窗口的值；当竞争窗口处于较大值范围时，消息的过期概率占据主要成分，而消息的过期概率会随着最小竞争窗口的增大而增大，所以为了增加广播的接收率，此时应该减小最小竞争窗口的值；当消息的碰撞概率与过期概率达到均衡时，广播接收率能够达到最大值。因此最优的竞争窗口应该能够保证消息的碰撞概率和过期概率之间的均衡。

图2 信标消息的马尔可夫链（当t=T时消息过期）

4 基于碰撞率和过期率的退避算法

为了解决V2V通信模式下信标消息广播接收率过低的问题，针对车载网中信标消息的特性，提出一种基于碰撞消息概率和过期消息概率的退避算法CEB。由于无法统计分组丢失中的碰撞消息数，在本文中采取一种折中的方法：每个车辆节点根据本节点统计的过期消息数目与预先设定的过期消息数门限的比值动态调整最小竞争窗口值，以达到提高车载网中广播接收率的目的。

CEB算法是基于信标消息过期概率、碰撞概率与最小竞争窗口的关系这一思想而提出的，它的实现也十分简单方便。每个节点只需要在MAC帧头增加一个区域用于统计过期消息数，并设定一个合理的过期消息数门限m0（m0为经过多次仿真后取得的合理值）。节点根据区域里的值与m0的大小关系进行最小竞争窗口调整。在本文中认为当过期消息数小于m0时，网络中的分组丢失主要由消息的碰撞导致，此时根据前面的分析，为了提高广播的接收率应该增加最小窗口的值；当过期消息数大于m0时，认为网络中的分组丢失主要由消息过期导致，此时应该减小最小竞争窗口的值；当过期消息数为m0时，最小竞争窗口的值保持不变。在统计区域内的过期消息数时，需要将时间分成周期性的观察间 隔（observation interval，OI），每过一个OI就统计当前的过期消息数目并将当前区域内的值清空。在本文中将OI的值设定为一个信标消息周期。

CEB算法具体的伪代码如下，其中mi表示当前OI内某个特定车辆节点的过期消息数目，CWinit为IEEE 802.11p协议规定的最小竞争窗口值。

算法1 CEB算法伪代码

if（在OI内）//统计OI内信标消息过期数目，包括收到的和在节点队列里因过期而丢弃的

{

mi=0;

if(过期消息被丢弃)then

mi+=1;//统计当前节点过期消息数

end if

d=mi/m0;

mi=0;//在OI结尾清空区域内的值

}end if

CW=CWinit;//将IEEE 802.11p协议规定的最小竞争窗口值赋给当前的最小竞争窗口

CW=CW/d;//根据d调整最小竞争窗口的值。

if(CW≤3)

CW=3;//如果最小竞争窗口值小于或等于3，取IEEE 802.11p规定的最小竞争窗口值的最小值3

end if

if(CW≥15)

CW=15;//如果最小竞争窗口值大于或等于15，取IEEE 802.11p规定的最小竞争窗口值的最大值15

end if

end if

5 CEB性能仿真

为了验证CEB算法对车载网中信标消息性能的影响，本文采取VanetMobiSim1.1和NS2.35进行联合仿真。车载网络移动性模拟器VanetMobiSim[9]能够方便地定义车辆的真实移动模型和具体移动参数。它所具有的IDM_IM模型和IDM_LC模型均考虑了真实的交通规则和场景，考虑了车辆之间的相互作用，能得到更真实的车辆移动性仿真轨迹。NS2[10]是UC Berkeley大学开发的一个离散事件仿真器，是进行网络研究主流仿真软件之一，它的仿真过程如 图3所 示[11]。

图3 NS2仿真流程

在仿真平台中，本文对直线型的高速公路进行模拟，每个方向两个车道共4个车道，采用IDM_LC模型。每条道路的长度为2 000 m，车辆数为10～80，广播的通信范围设置为300 m。具体的仿真参数见表1。

表1 仿真参数设置

图4表示改变车辆节点总数时，信标消息的广播接收率在BEB、RBEB和CEB算法下的变化趋势。通过对比可以发现，在车载网环境下利用CEB算法，广播接收率的性能相比于BEB算法和RBEB算法有明显的提高。观察曲线可知，随着节点数的增加，CEB算法的优势越趋明显。这是因为CEB算法综合考虑了信标消息的碰撞概率和过期概率，相比于RBEB算法中只考虑信标消息的过期概率和BEB算法只考虑信标消息的碰撞概率来说，更能够根据当前的信道情况进行最小竞争窗口的调整，使得当前的竞争窗口值能够最大化反映当前网络中信道的竞争情况。

图4 广播接收率变化

分析单个广播接收率的曲线可以发现，信标消息的广播接收率与周围竞争节点数是密切相关的。当周围邻居节点数目较少时，信标消息的信道访问竞争程度轻，此外，隐藏终端的影响也较小，因此此时的广播接收率较大；而当周围的邻居节点数目增多时，竞争信道的节点增多，传输冲突概率增加，因此广播接收率有所下降。

图5 广播平均到达时延变化

图5 表示改变车辆节点总数时，信标消息的平均到达时延在BEB、RBEB和CEB算法下的变化趋势。通过对比可以发现，CEB算法在提高广播接收率的同时也带来了信标平均到达时延性能的提升。这是因为相对于BEB和RBEB算法中最小竞争窗口以指数幂变化来说，CEB算法的最小竞争窗口是线性变化的，能够较好地反映当前网络中信道的竞争情况。

6 结束语

车载网是由车辆节点组成的移动Ad Hoc网络，具有网络拓扑动态变化、信道不稳定等特点。IEEE 802.11p协议中MAC层的DCF机制在高动态拓扑变化的车载网中性能并不是很好，尤其是针对车载网中的广播消息，由于没有反馈机制，传统的BEB算法并不能应用在车载网中。本文针对车载网中信标消息的特性，提出基于碰撞概率和过期概率的最小竞争窗口调整算法CEB，通过优化退避机制来降低信标消息传送过程中信道竞争程度，提高了信标消息的广播接收率，降低了平均到达时延。

1 Preparation for Driving Implementation and Evaluation of C-2-X Communication Technology,Detailed Description of Selected Use-Cases and Corresponding Technical Requirements.Pre-Drive C2X Deliverable D4.1,2008

2 IEEE P802.11pTM/D5.0.Draft Standard for Information Technology—Telecommunications and Information Exchange between Systems-Local and Metropolitan Area Networks—Specific Requirements—Part11:Wireless LAN Medium Access Control(MAC)and Physical Layer(PHY)Specifications Amendment 7:Wireless Access in Vehicular Environments,2011

3 Rawat D B,Popescu D C,Yan G,et al.Enhancing VANET performance by joint adaptation of transmission power and contention window size.IEEE Transactions on Parallel and Distributed Systems,2011,22(9):1528～1535

4 Ma X,Chen X,Refai H H.Unsaturated performance of IEEE 802.11 broadcast service in vehicle-to-vehicle networks.Proceedings of Vehicular Technology Conference 2007,Baltimore,USA,2007:1957～1961

5 于倩.基于Ad Hoc网络退避算法的研究.燕山大学硕士学位论文,2012

6 Li J,Blake C,Couto D D,et al,Capacity of Ad Hoc wireless networks.Proceedings of the ACM Annual International Conference on Mobile Computing and Networking(MOBICOM 2001),Rome,Italy,2001

7 Stanica R,Chaput E,Beylot A L.Enhancements of IEEE 802.11p protocol for access control on a VANET control channel.Proceedings of IEEE International Conference on Communications,ICC 2011,Kyoto,Japan,2011:1～5

8 魏李琦,肖晓强,陈颖文等.基于相对速度的IEEE 802.11p车载网络自适应退避算法.计算机应用研究,2011(10)

9 VanetMobiSim.http://vanet.eurecom.fr/,2013

10 Network Simulator 2(ns2).http://nsnam.isi.edu/nsnam/index.php/Main Page,2013

11 熊栋宇,陈前斌,唐伦等.车载安全应用广播性能分析.计算机应用研究，2010(4)