基于复合中继的车载自组织网络数据传输算法

刘期烈，陈 林，李 云

(重庆邮电大学 移动通信技术重庆市重点实验室,重庆 400065)

基于复合中继的车载自组织网络数据传输算法

刘期烈，陈 林，李 云

(重庆邮电大学 移动通信技术重庆市重点实验室,重庆 400065)

在车载自组织网络中，传输安全类相关的数据时，要求满足低时延和高可靠性，针对高速公路场景中危险警告消息数据的传输，提出一种基于邻居信息的多候选复合中继安全数据传输算法。车辆节点之间通过相互交换Hello Message构建2跳邻居表，在选择下一跳转发节点时利用2跳邻居节点信息得到一个复合参数，该复合参数综合考虑了车辆速度、位置和行驶方向3个因素。根据得到的复合参数值确定转发优先顺序，最高优先级车辆节点被确定为最佳中继转发节点，次优先级车辆节点作为备选中继转发节点。在最佳转发节点发送消息失败时，由备选转发节点继续完成消息转发任务，从而提高数据传输成功率。理论分析和仿真结果表明，提出的算法在实时性和可靠性方面有明显提升。

车载网络；数据传输；安全信息；邻居信息；复合中继

0 引 言

随着汽车数量增加，道路交通事故已经成为全球性公共安全问题，每年都会发生很多交通事故。车载自组织网络[1](vehicle ad-hoc networks, VANET)作为智能交通系统(intelligent traffic system, ITS)重要组成部分是在这种背景下提出的。VANET是专门为车辆间通信而设计的自组织网络，它创造性地将自组网技术应用于车辆间通信，使司机能够在超视距的范围内获得其他车辆的状况信息(如车速、方向、位置、刹车板压力等)和实时路况信息。作为无线自组织网络[2](mobile ad hoc network, MANET)中的一种特殊网络，VANET已经成为一种非常有前景的研究领域。VANET的典型应用[3]包括：驾驶安全预警、协助驾驶、商业娱乐等。其中，驾驶安全预警对于减少道路交通事故具有非常重要的意义，利用车辆间相互交换状态信息，通过车载自组网提前通知给驾驶人员，建议驾驶人员根据情况做出及时、适当的驾驶行为，有效提升驾驶人员的注意力，提高驾驶的安全性。VANET具有节点移动速度快、网络拓扑变化快[4]、节点分布不均匀、节点运动轨迹可预测等特点，通常采用多跳传播的方式将信息传到较远距离，而传统自组织网络的一些数据传输算法不能够直接用于VANET，因此需要针对车载网络提出与之相适应的数据传输算法。

对于VANET已有许多文献提出不同的数据传输算法，泛洪方式(MFlood)是车载网络中传输数据的一种基本方式，它的基本思想是源节点将数据传给自己所有邻居车辆，这些邻居车辆在收到数据之后再继续将数据传给自己所有邻居车辆。这个方法在稀疏网络环境下会呈现较好的性能，但是随着网络密度的增加，网络中传输的数据过多，容易引起广播风暴问题。

文献[5]中提出DV-CAST(distributed vehicular broadcast)来解决广播风暴问题和网络分离问题，DV-CAST利用周期性的信标消息建立本地拓扑来决定哪些节点来转发消息。DV-CAST能够适用于稀疏和密集的网络，在密集网络环境中采用广播抑制算法降低广播风暴的可能性，稀疏环境中采用“存储-携带-转发”的方式来克服网络分离问题。

文献[6]中提出基于距离的中继选择算法(distance based relay selection，DBRS)，并从平均时延、消息平均副本数等几个指标对算法的性能进行了评估。DBRS是一种比较简单数据传输策略，在收到数据包后车辆节点先将数据包保存一段时间(与到发送车辆的距离倒数成正比)，即距离发送数据车辆越远越早转发，其他准备转发的车辆在收到相同副本时就不再转发以此来避免广播风暴问题[7]。该方法可以有效解决广播风暴问题，缺点是：网络时延会比较高，因为不能保证时延较小的车辆节点一定存在；覆盖范围会减小，因为当接收到相同数据包的时候车辆节点会任意地取消传输消息。

文献[8] 中提出分布式自适应数据传输方法(adaptive approach for Information dissemination, AID)，该方法中车辆根据一个时间段内接收到相同数据包的次数来决定是否转发该数据。可以减少广播风暴问题，但是AID协议却没能解决网络分离问题并且在稀疏网络中表现出较差的数据传输性能。

文献[9] 提出的数据传输算法是关于高速公路环境下的分布式数据传输协议，采用车与车(V2V)之间的通信方式，不需要任何基础设施的支持，也不需要维护邻居表。源节点将消息广播出去，由接收车辆根据自身与源节点之间的距离计算一个等待时间，等待时间结束就立即广播消息。与DBRS类似，在收到广播消息后，等待转发的车辆就结束等待过程不再转发消息。但是，由于可能出现两个或者两个以上的车辆并行或者他们之间的距离较小，这样根据距离计算的等待时间长短相近，就可能出现同时转发消息的情况，这样容易导致冲突出现，从而使消息转发失败影响投递率和时延。

因此，为了有效解决由于冲突带来的时延增加和投递率下降以及速度对于最佳转发节点选择的影响，保证VANET中紧急数据传输的实时性和可靠性，让安全信息及时可靠地传输到危险区域，本文提出一种适合于高速公路(highway)场景下的安全信息传输机制即基于2跳邻居信息的多候选复合中继选择安全数据传输机制(two-hops neighbor information based multiple candidates relay data dissemination, MRDD)。MRDD在选择中继转发节点时采用2跳邻居表并且综合考虑距离、速度和方向3个因素的影响，此外还将多个车辆作为候选转发中继节点以提高紧急信息转发的成功率。利用Vanetmobisim[10]产生高速公路场景的运行轨迹，并在NS2仿真平台下对算法进行仿真验证。

1 MRDD算法

本节详细介绍MRDD机制，首先给出一些假设条件，然后定义一些相关概念和变量，最后详细介绍数据分发机制的实现过程及算法。

1.1 假设

首先，假设场景为平直的高速公路，每个方向3条车道，道路宽度相对传输半径来说可以忽略。每个移动车辆都配备有GPS设备可以获取自身的位置、速度、方向、当前时间等信息，车辆之间建立链接的时间可以忽略。车辆之间通过周期性广播Hello message来获取一跳(1-hop)邻居节点的相关信息。每个移动车辆都安装有全向天线覆盖半径R。当发生紧急情况时，车辆立即产生一个警告消息并向周围的车辆广播。

为了让车辆运动与消息传输之间的关系简单化，本文假设任意车辆节点i的到达率λi相互独立且服从Possion分布，

(1)

(1)式中：p(x)为在计数间隔t内到达x辆车的概率；x为给定时间间隔内到达的车辆数目；e为自然对数的底数；λit为计数间隔t内到达的车辆数目平均值，λi=N/3 600，N是小时交通量，λi为车辆平均到达率(veh/s)，t为每个计数间隔持续的时间(s)。车辆i速度为vi(i=1,2,…,N)∈[vmin,vmax]，其中，vmax和vmin分别表示该段高速公路上速度的最大值和最小值，vmin=80 km/h,vmax=120 km/h，N为车辆节点的数目。由概率论知，车辆节点的总到达率λ也服从Possion分布且

(2)

1.2 相关概念定义

定义1 危险警告区域(warning area, WA)：数据表明，在平均速率为100 km/h的情况下，距离事故500 m～1 500 m以内的跟随车辆都处于危险区域内[11]。因此，本文定义危险警告区域为事故发生地点后方1 500 m范围内的路段。

定义Hello Message的消息格式，如图1所示。

VIDPositionSpeedDIRTime

图1 Hello Message消息格式

Fig.1 Format of Hello Message

图1中，VID为每个车辆节点的唯一标识；Position表示车辆的当前位置，用二元组(xi,yi)表示；Speed表示的是车辆的行驶速度v；Time表示时间戳，即产生消息的时刻；DIR表示车辆的行驶方向。

定义警告消息(emergency message,EM)的格式，如图2所示。

SIDEPEDCFIDCFPEDDQUTTL

图2 警告消息格式

Fig.2 Format of Emergency Message

图2中，SID(Source ID)表示产生警告消息的车辆节点ID，EP(event position)表示事故发生的位置，ED(event description)表示对事故的简单描述。CFID(current forwarder ID)表示当前转发车辆节点的ID，CFP(current forwarder position)表示当前转发车辆节点的位置信息，EDD(event driving direction)表示发生事故的车辆所在的行驶方向，QU用来存储多个候选转发节点的转发顺序，TTL表示警告消息的生存时间。

1.3MRDD机制

由于现有的一些数据传输算法一般采用一跳邻居表即通过周期性的信标消息(hello message, HM)只获取一跳范围内的邻居节点信息，一跳范围外的车辆信息不能够获取，因此可能会出现位于通信半径R外边缘位置的车辆，下个时刻可能会进入R内，但是由于不能通过Hello消息让源节点知道它的存在，而被忽略的情况发生。如图3所示，ti时刻C不在S覆盖范围R内，而ti+1时刻，C进入R内并且可以作为候选中继节点，但是这种情况却被忽略。

图3 车辆位置变换示意图Fig.3 Transformation of vehicles’ position

为了解决上面这一问题提出采用2跳(2-hops)邻居表，即在邻居表中增加一跳邻居节点的邻居节点信息。通过一跳邻居节点间接获取2跳邻居节点的信息，在交换Hello消息时每个节点将自己的信息和一跳邻居信息放在Hello消息中。这样就可以将自己的信息和自己一跳邻居信息都发给下一个邻居节点，若收到同一个车辆的多条信息则根据时间戳用最新消息更新邻居列表，较早的信息则被删除。两跳邻居信息传递过程如图4所示。

图4 两跳邻居信息传递过程Fig.4 Process of information transmission between two neighbors

图4中，在ti-2时刻，交换Hello消息时C将自己的信息和一跳邻居的信息放在hello消息中发给B，因此B能够得到C的位置、速度等信息并记录到邻居表中。在下一个周期，B将自己的位置等信息以及一跳邻居C的信息放在Hello消息中发送给节点S，此时S的邻居表中除了有一跳邻居A，B的信息外还有可以通过一跳邻居节点获得的2跳范围的节点C的信息，在S收到B的Hello消息包括A节点的信息，而A节点在ti-1时刻也要与S交换Hello消息，因此在更新邻居表的时候，S保留A最新的一条信息而删除较早ti-2时刻获取的信息。当源节点S在ti时刻要发送信息时，就可以根据邻居表里面的信息做出相应的计算来判断候选的中继节点。

现有的一些数据传输算法在选择下一跳中继节点时仅以距离大小作为唯一的判断标准。由于相对速度的存在使这种单一的选择标准会出现选取的中继节点不是最优的情况。因此，针对这个情况，提出一种综合考虑速度和位置这2个因素的中继选择方案。

这里假设忽略车辆大小，近似认为车辆都位于一条直线上(如图5所示)，通过周期性地发送信标消息Hello建立两跳邻居表，车辆可以获取周围车辆的信息(位置、速度等)。车辆节点间的距离如图5所示。车辆ID用i(i=0,1,2,…,其中，源节点S的ID为0)表示，节点i的位置为(xi(t),yi(t))，速度为vi。因此可以根据距离公式计算出某时刻t车辆i与源节点S之间的距离

(3)

车辆节点i与源节点S间的相对速度为

(4)

(4)式中：若相对速度Δvi>0表示车辆i速度大于源节点S的速度；若Δvi<0则表示车辆i的速度小于源节点S的速度。

然后再通过相对速度计算Δt内行驶的距离

(5)

(5)式中：tcurrent为发送消息的当前时间；t为源节点S的邻居表中车辆i时间戳。因此，当前时刻车辆i与源节点S的距离为

(6)

(6)式中：在计算出di(tcurrent)后，就可以用di(tcurrent)与R之间的关系判断哪一个车辆i作为中继节点的最佳选择。这里定义复合因子p作为选择中继节点的指标，定义节点i的复合因子pi为

(7)

(7)式中：若pi<0，说明车辆i不在S的通信半径R内，链路断开；pi>0，说明车辆i在S的通信半径R内，能够进行通信，并且pi越小说明车辆i越远越接近半径R，越可能作为最佳中继节点转发信息。

图5 车辆节点间的距离Fig.5 Distance between vehicles

上面的方法能够选出最佳的中继转发节点，但是在实际的传输过程中，源节点或者中继节点发出的消息能不能被下一个中继节点成功接收并转发出去还受到信道状态、路面设施等因素的影响，特别是由于无线网络MAC层缺乏对广播消息的确认机制，当源节点或中继节点发送广播消息时不能确定广播消息是否被下一跳的中继节点成功接收并转发。因此，为了保证传输的成功率，本文提出一种多候选中继节点转发方案。

根据计算出来的p值的大小顺序0

(8)

(8)式中：tDIFS表示MAC层的长帧间间隔时间；Wmax为广播消息遇到的最大退避窗口数(32)；σ表示一个退避窗口的时隙大小(16 μs)；tsend表示发送一个包所需的时间。

当车辆密度较小时，车辆之间的距离大于R，不能够直接进行数据交换，这种情况下就采取“存储-携带-转发”的方式传输数据。

2 仿真结果及分析

本节将通过仿真结果对本文所提出的MRDD数据传输协议的性能进行评估。本文采用的仿真工具是开源软件Network Simulator(NS2.35)，仿真实验中采用的具体参数如表1所示。实验中用一个固定节点模拟源节点发送数据，车辆节点运动轨迹由VanetMobiSim产生，单次仿真时间为500 s，共进行20次仿真求出各性能指标的平均值。

表1 仿真参数表

2.1 平均时延性能及分析

平均时延定义为：在整个仿真过程中成功达到目的节点的消息在节点间传输过程中经过时间的平均值。图6所示为不同车辆密度条件下MRDD，MFlood，DBRS 3个数据传输算法平均延时性能对比。从图6可以看出，随着车辆密度的增加传输数据的时延逐渐减低，原因是当车辆密度增加时将会有更多的车辆位于危险警告区域WA中，网络的连通性更好，车辆越多则转发消息需要的时间越少。由于MFlood在收到数据后就把数据转发出去，因此MFlood传输数据的速度较快时延最低，而DBRS协议根据到源节点距离的大小而得出一个等待时间，等待时间结束才继续转发消息，从而消耗更多的时间延时较大。而提出的MRDD采用基于2跳邻居信息的复合中继策略，在选择中继转发节点的过程中同时考虑距离和速度，这样能够选择出最佳的中继转发节点，从整个过程来看，可以让每一跳的传输距离最大化，从而数据传输过程的时间将会减少，即延时会降低。

图6 平均时延与车辆密度间的关系Fig.6 Average delay and vehicle density

2.2 覆盖率性能及分析

用覆盖率来评估本文所提出的数据传输协议在不同车辆密度条件下的效率。覆盖率的定义为：危险警告区域中收到信息的节点数与危险警告区域内所有节点总数的比值。图7所示为不同车辆密度下的覆盖率。由图7可以看出随着车辆密度的增加MFlood和MRDD可以实现对危险警告区域内的车辆覆盖率达到100%即能够将警告信息传输给危险警告区域内的所有车辆，而DBRS只有不到40%的覆盖率。这其中的原因是，MFlood协议所有收到信息的节点都会转发给周围节点，随着车辆密度的增加可以将信息传输给所有车辆，MRDD采用了多个候选节点，当高优先级的节点转发失败时次优节点会接着转发信息，因此可以让危险区域内所有车辆都接收到警告消息。而DBRS仅以距离作为选择下一跳转发节点的参数，当车辆密度增加时，产生冲突的概率也增加了从而导致覆盖率低的结果。

图7 覆盖率与车辆密度间的关系Fig.7 Coverage and vehicle density

2.3 平均副本数性能及分析

平均副本数定义为：危险警告区域内车辆接收到的多余副本数的平均值。平均副本数可以用来衡量数据传输算法的效率，平均副本数越少说明传输的效率越高。图8给出了平均副本数与车辆密度之间的关系，从图8中可以看出，与MFlood算法相比，MRDD和DBRS算法由于在传输数据的过程中不是所有节点都参与数据包的转发，从而减少了网络中多余副本的转发，因此平均副本数明显低于MFlood。但是，随着车辆密度的增加，3个算法的副本数都有小幅度的增加，这是由于车辆密度增加后参与转发的节点数量会增加导致的，但MRDD与DBRS的增幅相比MFlood小。MRDD由于采用的复合中继选择策略，因此与DBRS相比转发的次数减少了从而平均副本数低于DBRS。

图8 平均副本数与车辆密度间的关系Fig.8 Average duplications and vehicle density

2.4 转发节点比例性能及分析

转发节点比例定义为：参与转发的节点与所有接收到消息的节点总数的比值。若转发节点比例越大则越多的节点参与了数据包的转发过程，在同等条件下，虽然参与转发的节点越多成功率就越大，但是这样会增加网络开销。图9给出了转发节点比例与车辆密度之间的关系，从图9中可以看出，由于MFlood算法中所有节点收到数据包之后都会转发，因此转发节点比例为100%。随着车辆密度的增加，MRDD和DBRS的转发节点比例有所下降，这是因为随着节点密度的增加，节点总数增加比参与转发的节点数增加幅度大，因此转发节点的比例有所下降。而由于MRDD采用基于2跳邻居信息的复合中继选择策略，每次都选择最佳节点转发消息，每一跳覆盖范围更大，因此参与转发的节点总数比DBRS协议少，从而节点转发比例较小。

图9 转发节点比例与车辆密度的关系Fig.9 Ratio of forwarding nodes and the vehicle density

2.5 平均包冲突数性能及分析

平均包冲突数定义为：在仿真过程中发生冲突的数据包的平均值，用于评估数据传输协议对于抑制广播风暴问题的效果。图10给出了平均包冲突数与车辆密度之间的关系，如图10所示，随着车辆密度的增加，包冲突的数量都有所增加，但是MRDD和DBRS增加幅度较小，而MFlood增加幅度非常大，这是由于MFlood协议对于数据包重传过程缺乏协调机制，当同时有多个车辆试图接入信道时会发生冲突，尤其是当车辆密度较大时冲突的概率会急剧增加，这就是图中MFlood曲线随着车辆密度增加而大幅上升的根本原因。MRDD和DBRS在下一跳转发节点的选择上都各自采取了策略而不是盲目的全部转发，因此发生的冲突次数相比MFlood减少很多，由于综合考虑速度和距离因素MRDD相比DBRS则表现更好。

图10 平均包冲突数与车辆密度间的关系Fig.10 Average collisions and vehicle density

3 结束语

为了让道路安全信息快速可靠地传输给危险区域内的车辆，本文提出一种基于2跳邻居信息的多候选复合中继转发节点选择机制，通过仿真实验表明，提出的数据传输机制能够降低数据传输的时延，减少广播风暴带来的冲突问题，同时多候选机制可以提高消息传输的可靠性和覆盖率，对于高速公路上紧急信息的传输以避免更大交通事故的发生具有重要意义。

[1] KUMAR S S. Vehicular Ad Hoc Network[J]. International Journal of Computer, Information, Systems and Control Engineering, 2014, 8(4): 628-630.

[2] CONTI M, GIORDANO S. Mobile ad hoc networking: milestones, challenges, and new research directions[J]. IEEE Communications Magazine, 2014, 52(1): 85-96.

[3] 常促宇,向勇,史美林.车载自组网的现状与发展[J].通信学报, 2007, 28(11): 116-126. CHANG Cuyu, XIANG Yong, SHI Meilin. Development and status of vehicular ad hoc networks[J]. Journal on Communications, 2007, 28(11): 116-126.

[4] 陈立家,江昊,吴静,等.车用自组织网络传输控制研究[J].软件学报, 2007, 18(6): 1477-1490. CHEN Lijia, JIANG Hao, WU Jing, et al. Research on Transmission Control on Vehicle Ad-Hoc Network[J]. Journal of Software, 2007, 18(6):1477-1490.

[5] TONGUZ O K, WISITPONGPHAN N, BAI F. DV-CAST: A distributed vehicular broadcast protocol for vehicular ad hoc networks[J]. IEEE Wireless Communications, 2010, 17(2): 47-57.

[6] KIM T H, HONG W K, KIM H C, et al. An effective data dissemination in vehicular Ad-Hoc network[C]//Proc. of the International Conference on Information Networking(ICOIN 2007). Estoril: Springer Press. 2007: 295-304.

[7] 罗涛,李俊涛,刘瑞娜,等.VANET中安全信息的快速可靠广播路由算法[J].计算机学报, 2015, 38(3): 663-672. LUO Tao, LI Juntao, LIU Ruila, et al. A Fast and Reliable Broadcast Routing Algorithm for Safety Related Information in VANET[J]. Chinese Journal of Computers, 2015, 38(3): 663-672.

[8] BAKHOUYA M, GABER J, LORENZ P. An adaptive approach for information dissemination in Vehicular Ad hoc Networks[J]. Journal of Network & Computer Applications, 2011, 34(6):1971-1978.

[9] VILLAS L A, BOUKERCHE A, MAIA G, et al. DRIVE: An efficient and robust data dissemination protocol for highway and urban vehicular ad hoc networks[J]. Computer Networks, 2014(75): 381-394.

[10] AHUJA B, GOHIL A, KUMAR R, et al. Simulation of VANET using VanetMobiSim and NS-2[J]. Wireless Communication, 2013, 5(9): 381-384.

[11] GREEN M. “How Long Does It Take to Stop” Methodological Analysis of Driver Perception-Brake Times[J]. Transportation Human Factors, 2000, 2(3): 195-216.

(编辑：张 诚)

A data dissemination algorithm based on composite relay in VANET

LIU Qilie, CHEN Lin, LI Yun

(Chongqing Key Lab of Mobile Communications Technology, Chongqing University of Posts and Telecommunications, Chongqing 400065, P.R. China)

Data dissemination in VANET, especially the dissemination of safety related data, requires low delay and high reliability. Based on two-hop neighbor information, this paper proposes a Multiple candidate Relay Data Dissemination algorithm (MRDD) to transmit emergency message in highway scenarios. The two-hop neighbor information table is constructed by exchanging Hello Messages. The composite criterion is gotten from the neighbor information table, which considering both the velocity and location of the vehicle. According to the value of composite criterion, the highest priority vehicle node is chosen as the optimal relay node. When the optimal relay node fails, the candidate vehicle will rebroadcast the data. Theoretical analysis and simulation results show that the proposed algorithm can achieve lower packet transmission delay and higher reliability.

VANET; data dissemination; safety information; neighbor information; composite relay

10.3979/j.issn.1673-825X.2017.01.008

2016-01-16

2016-05-25 通讯作者：刘期烈 liuql@cqupt.edu.cn

重庆市自然科学基金项目(cstc2014jcy40044)；重庆市教委科学技术研究项目(KJ1400406,KJ1500405)；长江学者和创新团队发展计划资助(IRT1299)；重庆市科委重点项目(cstc2015jcyjBX0068)；重庆市科委重点实验室专项经费

Foundation Items：The Natural Science Foundation Project of CQ CSTC (cstc2014jcy40044)；The Science and Technology Research Project of Chongqing Municipal Education Commission of China (KJ1400406,KJ1500405)；The Program for Changjiang Scholars and Innovative Research Team in University (IRT1299)； The Foundation and Frontier Research Project Chongqing(cstc2015jcyjBX0068); The Special Fund of Chongqing Key Laboratory

TN919.5;TP393

A

1673-825X(2017)01-0049-07

刘期烈(1974-)，男，四川隆昌人，副教授，博士。主要研究方向为机会网络。E-mail:liuql@cqupt.edu.cn。

陈 林(1989-)，男，四川遂宁人，硕士研究生。主要研究方向为车载网络。E-mail:815778335@qq.com。 李 云(1974-)，男，四川西充人，教授，博士，博士生导师，主要研究方向为无线网络技术。E-mail:liyun@cqupt.edu.cn。