基于VANETs下的决策树多副本机会路由协议

刘辉元，董春阳，黄 琼

(1.重庆市工业学校，重庆 40043; 2.重庆邮电大学信息产业部移动通信技术重点实验室，重庆400065)

基于VANETs下的决策树多副本机会路由协议

刘辉元1,2，董春阳2，黄 琼2

(1.重庆市工业学校，重庆 40043; 2.重庆邮电大学信息产业部移动通信技术重点实验室，重庆400065)

在车载自组织网络(vehicular Ad hoc networks, VANETs)中，当节点缓存和消息副本数目被限制的情况下，如何合理地选择车载网络的路由节点是实现VANETs高效转发和投递的关键问题。为此提出了一种基于学习方法的决策树理论的多副本VANETs机会路由协议(D-Tree)。D-Tree将VANETs中节点间的传输和连接因素看做多个属性的集合，并与决策树方法得到一个消息转发规则，同时结合多副本路由与机会路由的“存储─携带─转发”优势进行消息投递。真实数据集上的实验结果表明，在场景密集的情况下，D-Tree相比于Bubble和S&W路由算法投递成功率提高了近10%，同时在投递延迟等方面也具有明显优势。

车载自组织网络(VANETs)；机会路由；路由算法；决策树；多副本

0 引 言

车载自组织网络(vehicular Ad hoc networks, VANETs)[1]是专门为了车辆之间通信而设计的自组织网络，它属于移动Ad-hoc网络(mobile Ad-hoc network, MANET)的子集，其主要目标是建立一个普通的通信平台去支持车辆之间各种类型的智能传输应用。车联网是以车际网、车内网和车载移动互联网为基础，按照约定的通信协议和数据交互标准，支持车辆─车辆(vehicle 2 vehicle, V2V)、车辆─通信设施(vehicle 2 infrastructure, V2I)之间的通信[2]。

在VANETs应用中，每个车辆节点分布稀疏不均、网络拓扑变化快以及移动速度快或障碍物造成信号衰减等多种原因都可能导致网络中大多数节点处于中断状态。这种网络环境中，传统的MANET通信模式无法有效运行，因此，车载网络路由协议通常采用“存储─携带─转发”的机会路由[3]机制或者车载容延容断网络(vehicular delay tolerant network, VDTN)[4]进行消息投递。同时，因为VANETs中的节点在车主的控制下具有一定的人类社会网络属性。如公交车沿着固定线路行进，出租车会因车上乘客的需求而进行随机运动[5]，私家车主们购物、上下班等基本都在一些特定区域，组成的网络呈现出社会网络学中“小世界，大世界”现象[5]。

为改善容断连接VANETs网络性能，同时提高资源利用率, 需要节点在网络拓扑信息未知的情况下，充分感知网络在移动过程中的逻辑结构。因此，车载机会网络路由的核心问题是一个利用相关知识进行最优化计算选择合适的下一跳路由节点的决策性问题。因此，一些基于社区的路由算法[6-9]被研究者们提出，它们只是简单地将社会属性选择出来，然后依照选出的社会属性建立一个效用函数或者采用一种单一的社会属性值进行数据的下一跳转发；在此种情形下有可能由于当前网络情况和副本数限制而错失综合性能更高的节点。同时，文献[10]以节点信任度为基础，将节点信任度分为以过程基础和关系基础的信任方式来进行数据传输，并通过结合入侵检测机制的方式来提高网络的QoP(quality-of-protection)和用户QoE(quality of experience)等。

通过对上述问题的分析，本文提出一种基于学习方法的决策树理论的机会VANETs路由决策算法(D-Tree)，以便能够更全面地综合考虑社会属性之间的影响并进行折衷，优化网络综合性能。该算法将VANETs中节点间传输和连接的因素看做多个属性的集合，根据该属性集合与决策树方法得到一个消息转发的决策规则，预测节点的下一个路由能否成功接收数据包，能有效提高网络性能的指标，降低了节点的路由开销和投递延迟等。

1 相关工作

目前，VANETs路由协议可以分为单副本(single copy)和多副本 (multi-copy)路由协议。在单副本路由协议[6]中，每条消息只含有唯一副本；而在多副本协议中，每条消息可以存在多个副本，但又不同于Epidemic算法中每个节点都可以持有该消息副本，只是可以同时有多个节点持有该消息副本。下面主要介绍多副本路由协议。

Spray and Wait[11]算法分为2个阶段，Spray阶段和Wait阶段。在Spray阶段，源节点向网络投入特定数目的L个数据包副本，然后进入Wait阶段，若数据包副本在Spray阶段没有发现目的节点，那么携带数据包副本的节点将通过Direct Delivery[12-16]方式把数据包副本传送到目的节点。但是由于没有考虑到邻居节点的数量问题，当邻居节点过多时，会由于源节点过多的“喷洒”造成节点快速死亡。因此,该算法在不考虑邻居节点选择的情况下，不能取得较好的效果。

Bubble Rap[8]路由算法也是一种基于社会属性的路由算法。该算法将转发策略依赖于2个社团特征(社区和中心度)。消息转发的2个阶段都是基于网络中心性的转发。在转发阶段中，当目标节点所有邻居的网络中心性都较低，那么消息转发将失败，从而导致消息在传输过程中的时延急剧增加。

社会属性感知的数据转发策略[7](social attributes aware date forwarding strategy,SADFS)路由协议利用节点水平和垂直的社会关系，考虑节点之间的社会关系并以分布式方式估计其自身及其他节点的社会属性，进而确定携带节点与目的节点的关系以进行数据转发。文献[12]通过建立时序图模型预测节点链接态势，为消息分布式的选择最佳中继节点进行数据包的转发。

2 基本定义

通常VANETs包含以下几个主要元素：车辆节点、路边设施和车载网络链路。其中， VANETs链路是指在所有车辆之间建立起的连接。同时在VANETs中，车载社会网络与人类社会关系之间存在一定的相互映射等特性。因此，通过利用这些类社会属性之间的关系，可以更好地为车辆间的通信提供有力的保障。为了方便研究上述现象，本文对这样的车辆网络进行了数学抽象并作出了如下定义。

定义1车辆网络。把车辆网络定义为一个含有节点和链路的连通图G=(V,E)，其中，V代表车辆节点集合，E为在通信范围内车辆节点之间的链路集合。

对于每个车辆节点vi,vi∈V,i={1,2,…,n}，用集合A描述车辆节点属性为

(1)

定义3为了能够在VANETs中对属性的分类能力进行度量，在此引入车辆网络信息增益(VehicleGain(A,aj))，即由于使用这个属性分割样例而导致的期望熵降低。更精确的讲，一种属性aj相对于样例集合A在VANETs中的车辆网络信息增益VehicleGain(A,aj)定义为

(2)

(2)式中：Values(aj)是属性aj所有可能值的集合；Av是A中属性aj的值为v的子集(也就是Av={a∈A|aj(a)=v})。需要注意的是(2)式右边的第2项描述的期望熵就是每个子集的熵的加权和。

定义4为避免车辆信息增益在分类时过度偏袒具有较多值的属性，引入车辆网络信息增益比率为

(3)

3 基于D-Tree的路由协议

3.1 VANETs属性

在机会VANETs中，节点的移动产生了终端之间的直接相遇机会，从而使节点之间可以实现点对点的数据通信。但这种通信链路建立的时间不够确定，链路生存时间短，中断时间长，通信能力受限。常用于描述和表征机会VANETs属性链路特征的术语如下。

1)节点新近度(node recency)。它是基于最近多长时间车辆B遇到网络中任意车辆x，为车辆之间最近一次建立连接的时间间隔比例。如果将来接触的概率越高，则说明当前联系时间与下一次联系间隔的间隔越短。

2)节点活跃因子[7](node active factor)。节点活跃因子表示车辆节点的活动能力，车辆遇见的其他车辆越频繁，邻居列表信息变化越剧烈，说明该车辆越活跃，能够成功转发到目的地的机会越大。本文节点活跃因子通过节点在最近一段时间内平均邻居节点个数来衡量。

3)节点度(node degree)。车辆节点在车辆网络图中的度。描述了车载用户在网络中的流行程度。车辆之间进行信息传递时，车辆节点的度将是路由选择的一个重要度量值。

4)接近中心度(closeness centrality)。接近中心度表示与其他所有节点具有最短路径的节点。描述了最高效的路径和网络可视性，选取接近中心度最高的节点作为信息分发和扩散的节点，可以有效减少信息扩散时延和网络开销。

5)中介中间性(betweenness centrality)。在车辆网络中，节点作为2个相邻节点的中间桥梁节点的度量。连接2个车辆节点的中间节点会具有很高的中介中间性，这个中间节点在车辆节点之间信息交互过程中，起到了很关键的作用。

6)网络密度(density)。车载用户之间的连接密度。描述了网络中节点之间连接密度的分布。

在上述几种属性链路特征中，节点新近度和节点活跃因子反应了节点在一定时期内车辆节点自身“活动”能力情况的大小，而节点度、接近中心度等反应了车辆节点在区域性社区或者局部网络架构中节点相互作用的属性特征。在同时考虑车辆节点自身与车辆网络结构的情况下，能够更加合理地选取下一条路由。

3.2 D-Tree协议

D-Tree主要包括2个阶段：扩散阶段和转发阶段。在扩散阶段，源节点持有的消息副本数量为L(L>1)，如果遇到一个不含该消息的节点，则根据决策规则和二分法扩散副本。在之后的过程中，当节点持有的消息副本数为1且与不含该副本的节点相遇时,则进入转发阶段。在转发阶段，节点只根据决策规则向相遇节点转发此消息副本。当遇到的节点如果是目的节点，无论是在扩散阶段还是转发阶段，都直接向其转发该消息 。D-Tree协议流程如图1所示。

3.2.1 基于C4.5的VANETs规则树算法

在数据收集及预处理后，进行决策树建立阶段。根据3.1节中对机会VANETs属性概念的定义，并且依照属性特征值对整个网络系统的数据进行收集、处理。然后将处理的属性特征值按照定义3与定义4的过程分别进行处理、计算，并将其按照机器学习算法C4.5[17]对各属性的重要度进行评级和划分，学习算法伪代码如下。

图1 D-Tree协议流程Fig.1 D-Tree Protocol Processing

算法:Generate_Decision_Tree

算法输入：训练样本samples,候选属性的集合Attribute-List

算法输出：决策树

/* C:类别属性; test_attribute:测试属性; */

Create node N

If samples are all in class C Then

return N as leaf node and label it as class C

If Attribute-List Null ThenL return N as leaf node and label it as normal node in samples

Choose the attribute with the highest VehicleGainRatio in Attribute-List

Label node N as Attribute-List

For each aiin Attribute-List

If test-attribute=aithen create branch after node N

set sias another sample with test-attribute=ai

If siis NULL Then

add a leaf node and label it as the most normal class

Else add the node by the return value of

Generate_decision_tree(si,attribute_list,test_attribute)

对计算出的各属性值，每次选取车辆网络信息增益比率(VehicleGainRatio(A,aj))最大且获取的车辆网络信息增益(VehicleGain(A,aj))又不低于所有属性平均值的属性作为树的节点，每一个分支都是一个可能值，依此递归的形成决策树，直到子集中的数据记录在主属性上取值都相同，或没有属性可再供划分使用。

3.2.2 扩散阶段

VANETs中的节点通过对网络属性的收集和处理，依据建立的决策树对多副本的消息进行“有向扩散”。对与本节点相遇的节点副本数的副本分配方法采用经典的“二分法”。

3.2.3 转发阶段

消息从源到目的节点转发延迟取决于搜索树的延迟、扩散延迟和转发延迟之和。为降低投递时延，提高消息投递成功率。持有单个副本的节点在转发阶段，将按照决策规则向未持有相同消息的节点转发此消息。

因为持有消息节点与目标在同一个网络环境中，则只要相遇节点不是目的节点，就按决策规则转发，这样更容易将消息传递到目标节点区域附近，如果遇到目的节点则直接转发。因此，在转发阶段采用决策规则转发，在整个消息的转发过程中避免盲目转发，能有效降低消息向目标节点的投递时延。

3.2.4 算法设计

通过模型分析以及上述扩散阶段与转发阶段的分析，可以对D-Tree建立一个算法，算法的伪代码如下。

算法输入：消息的源节点S，目标节点D，且当前网络中所有节点都含有决策树准则R，消息副本数Copies，下一路由节点Ns，当前消息msg。

If Copies > 1 Then

Copies = Copies/2

Else If Copies = 1 Then

Exit;

For Ns in Ns1,Ns2,…Nsn Do

If (S,Ns) match R Then

Else If Ns is D Then

Break;

End If;

End For;

While Ns carries the msg Do

For Ns’ in Ns1’,Ns2’,…Nsn’Do

If (Ns,Ns’) match R Then

Else If Ns meets with D Then

End If;

End For;

End While;

3.3 规则分析

对于每个携带数据包状态的车辆节点，每个阶段的状态与选择的转发决策将影响下一阶段的决策。设共有N+1个阶段，标记为n=0,1,…,N，其中将开始阶段标记为0。设系统在阶段n+1时的状态为Tn(i,a)∈Sn+1(称Tn为n时的状态转移函数)。因此，数据包选择何种决策规则进行转发的决策问题可以规划为如下的模型形式

{Sn,(An(i),i∈Sn),rn(i,a),Tn(i,a),n=

1,2,3,…,N,V}

(4)

目标函数V的常见形式是使各个阶段的报酬之和达到最大。

定义阶段n时的决策函数为映射

(5)

且满足条件f(i)∈An(i),i∈Sn。阶段n时的决策函数全体记为Fn。f∈Fn的含义是：若系统处于状态i，且在阶段n，则选择决策f(i)。

因此，策略就是一个决策函数序列

π=(f0,f1,…,fN),f∈Fn,

n=0,1,…,N

(6)

对n=0,1,…,N，fn在阶段n时使用。使用策略π是指：若系统在阶段n处于状态i(i∈Sn)，则选择决策fn(i)(fn(i)∈An(i))。记策略的全体为Π。

下面论述通过C4.5算法生成的决策树中的规则，一定存在着最优策略。

设决策树生成的策略π∈Π,且初始状态为i0∈S0，则可以确定各个阶段的状态in与所选择的决策an，它们可由in+1=Tn(in,an),an+1=fn+1(in+1),n=0,1,…,N-1递推得到，从而可以得到阶段n的报酬rn(in,an)，进而确定各个阶段的报酬之和(称之为总报酬)。由于这个总报酬值依赖于所选择的策略，以及初始状态，因此，我们记为V(π,i0)，即

(7)

(7)式只与所使用的策略π及初始状态i0有关。称V(π,i0)为系统在策略π下从初始状态i0出发时的总报酬。且定义

(8)

(8)式表示初始状态为i时，所可能获得的最大总报酬，称V为决策问题的最优值函数。且在决策规则中，对所有的初始状态i∈S0一定都成立，即取到(10)式的上确界。根据Bellman最优性原理[19]，则策略π是最优策略，且Vn(π,i)=V(i),i∈S0。即对于车辆节点在每个阶段n转发数据包时，根据决策规则的选择转发，一定存在一个最优策略在当前阶段进行转发，使系统的综合性能得到保障。

4 数据仿真及分析

通过在真实数据集Cambridge的Haggle项目[20]提供校园相遇轨迹数据集和Cabspotting项目[21]提供出租车轨迹的数据集上仿真D-Tree路由协议的性能，与现有的基于社会网络的多副本路由算法Bubble Rap和多副本路由算法Spray and Wait(S&W)进行了对比。

本文采用机会网络(opportunistic network environment，ONE)[22]仿真平台进行性能评估工作。对比了3种路由性能指标：消息投递成功率，消息被目标节点成功接收的数量与产生的总消息数量之比；平均投递时延，从消息生成到投递到目标节点所需要的时间；路由开销率，所有节点成功转发数据分组总数与目的节点收到数据分组总数的差和目的节点收到数据分组总数之比。

4.1 参数设置

在Cambridge的Haggle项目中，节点是基于校园终端设备的社会网络的跟踪数据采集。车联网中的社会属性可以类比于在人类社会生活中，并以此情景模拟移动情况。因此，在基于ONE的仿真平台下，将速度范围增大到车辆行驶下的速度大小，同时将运动范围增大以便模拟车辆在基于社会网络下的移动场景。在仿真实验中，场景参数设置情况如表1所示。

Cabspotting项目提供跟踪出租车轨迹的数据集，该数据集记录了500个节点的轨迹情况，数据采集时长为 30 天(如果考虑车辆网络的实际场景，则还存在其他车辆对这个数据集车辆间数据投递的影响，在本实验中排出这些因素的影响)。在仿真实验中，场景参数设置情况与表1相同，只需对仿真时间、网络区域及节点数进行更改。同时，因为在同一个数据集上重复完整长度的实验没有意义，也为了模拟多次随机实验，我们将整个数据集依时间分成多段进行模拟。

表1 Haggle参数设置

4.2 生存时间(TTL)对性能的影响

图2和图3中分别对比了在Haggle项目和Cabspotting项目数据集下，在不同TTL(time-to-live)限制条件下评估D-Tree的性能，以Spray and Wait等协议作为参考。

图2 不同TTL的D-Tree的性能对比(Haggle项目)Fig.2 Performance Comparison of different TTL of D-Tree

图3 不同TTL的D-Tree的性能对比(Cabspotting项目)Fig.3 Performance Comparison of different TTL of D-Tree

从图2中可以看出，在相同条件下，D-Tree具有较好的性能。Bubble Rap在投递率方面和D-Tree较为相近，但路由开销率比D-Tree高了接近20%～30%，这是因为在转发阶段，Bubble Rap转发的中继节点比D-Tree多，即转发的盲目型要比D-Tree大。而Spra yand Wait比两者都低，是因为Spray and Wait的转发阶段是被动等待，消息副本只会忠实的等待目的节点的到来。同时，在图2中随着TTL的增加，由于网络密度的影响和 Bubble Rap只考虑单社会属性节点中心度会导致在某一阶段节点邻居中心度无法计算或者都较低，且又因TTL未过期，不能将数据包丢弃，转发的次数会增多，因此，随着TTL的增加，Bubble Rap协议的开销会出现先减小后增大的趋势。

从图3中可以看出，在网络规模大幅增加的情况下，D-Tree仍然具有较好的性能。D-Tree的性能和Spray and Wait较为相近，但投递率比Spray and Wait略高。D-Tree和Spray and Wait的路由开销率都比Bubble Rap低分别是因为：D-Tree比Bubble具有较准确的转发性，而Spray and Wait是因为Wait阶段不会对网络产生较大开销。且在网络密度较大的情况下，对于D-Tree和Bubble Rap的社会属性值会相对较好采集，根据路由开销的定义，在图3b中随着TTL的增加，开销是递减的趋势。

4.3 副本数对性能的影响

图4和图5中分别对比了在不同副本数限制条件下评估D-Tree的性能，从图4中可以看出：随着副本数的增加，D-Tree的性能在投递率和投递延迟都优于Bubble Rap和Spray and Wait，但路由开销随着副本数的增加而增加，且明显高于Spray and Wait。

图4 不同副本数的D-Tree的性能对比(Haggle项目)Fig.4 Performance Comparison of different copies of D-Tree

在图4b中，D-Tree与Spray and Wait随着副本数的增加，投递时延都呈下降的趋势，因为副本数的增加会增加携带消息节点与网络中其他节点的相遇机会，这样更有机会到达目的节点。而Bubble Rap在只计算节点中心度的情况下，虽然副本数增加，但依然会因为邻居节点中心度较低而进行多次无效的转发，因此增加了延时，只有当副本数目增加到一定程度时，即消息的覆盖面积足够大时，投递延时才会出现下降的趋势。

在图5中，D-Tree由于避免了盲目的消息转发，而且优势随着网络规模的增加而增加，这种潜在的“Wait-遇到更优”转发机制的节点的可能性越大，因此性能优势越明显。

图5 不同副本数的D-Tree的性能对比(Cabspotting项目)Fig.5 Performance Comparison of different copies of D-Tree

5 结束语

利用VANETs中节点的社会属性特征，本文提出了一种基于决策树的多副本VANETs机会路由协议D-Tree。这种算法根据车载网中节点间的社会属性和节点自身属性，并通过决策树算法对这些属性进行分类、评级，依照级别高低建立决策树，然后建立决策规则对数据包进行投递转发。这种算法克服了消息的盲目转发性，提高了数据包的投递成功率，降低了传输中的延迟，还通过对副本数量的有效限制达到了控制网络开销的目的，取得相对较好的综合性能。在对决策规则更新的问题上，本文将在今后继续深入研究，以便在更新问题上给予一个准确性的理论支持。

[1] FALL K. A delay-tolerant network architecture for challenged internets[C]// Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications. Seattle: ACM Press, 2003:27-34.

[2] HUANG C,LIN S.An early collision warning algorithm for vehicles based on V2V communication[J].International Journal of Communication Systems,2012,25(6):779-795.

[3] 熊永平，孙利民，牛建伟. 机会网络[J]. 软件学报, 2009, 20(1):124-137. XIONG Y P,SUN L M,NIU J W,et al.Opportunistic networks[J].Journal of Software,2009,20(1):124-137.

[4] ISENTO J, RODRIGUES J, DISA J, et al. Vehicular delay-tolerant networks-a novel solution for vehicular communications[J]. IEEE Intelligent Transportation Systems Magazine, 2013, 5(4):10-19.

[5] HUANG J, WANG S, CHENG X, et al. Mobility-Assisted routing in intermittently connected mobile cognitive radio networks[J]. IEEE Transactions on Parallel & Distributed Systems, 2014, 25(11):2956-2968.

[6] DALY E M, HAAHR M. Social network analysis for routing in disconnected delay-tolerant MANETs[C]// ACM Interational Symposium on Mobile Ad Hoc NETWORKING and Computing. Seattle: ACM Press, 2010:32-40.

[7] 吴大鹏,孔晓龙,张洪沛,等.社会属性感知的间断连接无线网络数据转发策略[J].通信学报,2015,15(1):38-47. WU Dapeng, KONG Xiaolong, ZHANG Hongpei, et al. Social attributes aware data forwarding strategy in intermittently connected wireless networks[J]. Journal on Communication, 2015,15(1):38-47.

[8] HUI P, CROWCROFET J, YONEKI E. BUBBLE Rap: Social-Based Forwarding in Delay-Tolerant Networks[J]. IEEE Transactions on Mobile Computing, 2010, 10(11):1576-1589.

[9] 吉福生, 王燕燕, 徐明玉,等. 社会化机会网络中节点归属位置感知的路由机制[J]. 重庆邮电大学学报:自然科学版, 2015, 27(3):404-410. JI Fusheng, WANG Yanyan, XU Mingyu, et al. Node home location aware routing mechanism for social opportunistic network[J]. Journal of Chongqing University of Posts and Telecommunications: Natural Science Edition, 2015, 27(3):404-410.

[10] WU D, ZHANG H, WANG H, et al. Quality-of-protection-driven data forwarding for intermittently connected wireless networks[J]. IEEE Wireless Communications, 2015, 22(4):66-73.

[11] SPYROPOULOS T, PSOUNIS K, RAGHAVENDRA C S. Spray and wait: an efficient routing scheme for intermittently connected mobile networks[J]. Sigcomm, 2005, 5(4):252-259.

[12] 吴大鹏, 张普宁, 王汝言. 节点连接态势感知的低开销机会网络消息传输策略[J]. 通信学报, 2013, 34 (3):44-52. WU Dapeng, ZHANG Puning, WANG Ruyan. Connection status aware cost efficient message transmission mechanism in opportunistic networks[J]. Journal on Communication, 2013, 34(3):44-52.

[13] JINDAL A, PSOUNIS K. Contention-aware analysis of routing schemes for mobile opportunistic networks[C]// Proceedings of the 1st international MobiSys workshop on Mobile opportunistic networking. Seattle: ACM Press, 2007:1-8.

[14] LIU B, FIROIU V, KUROSE J, et al. Capacity of Cache Enabled Content Distribution Wireless Ad Hoc Networks[C]// Mobile Ad Hoc and Sensor Systems (MASS), 2014 IEEE 11th International Conference on. Seattle: IEEE Press, 2014:309-317.

[15] Jones E, Ward P. Routing strategies for delay-tolerant networks[J]. IEEE Transactions on Parallel & Distributed Systems, 2006, 25(11):2636-2653.

[16] ZHANG Z. Routing in intermittently connected mobile ad hoc networks and delay tolerant networks: overview and challenges[J]. Communications Surveys & Tutorials IEEE, 2006, 8(1):24-37.

[17] MITCHELL T, CARBONELL J, MICHALSKI R. Machine learning [M].Machine Learning. Springer US, 1986:417-433.

[18] LI Z, SHEN H. SEDUM: Exploiting Social Networks in Utility-Based Distributed Routing for DTNs[J]. Computers IEEE Transactions on, 2013, 62(1):83-97.

[19] BELLMAN R. Dynamic Programming[J]. Science, 1966, 153(3731):352-352.

[20] RAWDAD.A Community Resource for Archiving Wireless Data At Dartmouth[EB/OL].(2012-12-19)[2015-04-15]. http://crawdad.org/cambridge/haggle/.

[21] RAWDAD.Exploratorium Cabspotting project 2012[EB/OL]. (2013-12-19)[2015-04-15].http://cabspotting.org/index.html/.

[22] VINICIUS M.Helsinki University of Technology. The opportunistic network environment simulator 2012[EB/OL]. (2010-12-19)[2014-04-15]. http://www.netlab.tkk.fi/tutkimus/dtn/theone/.

刘辉元 (1971-)，重庆人，高级讲师，主要研究方向为无线网络通信。Email：307519688@qq.com。

董春阳(1989-)，男，四川人，硕士研究生，主要研究方向为车载网络路由协议。E-mail：dasyang@foxmail.com。

(编辑：田海江)

Multiple copies of VANETs based on decision-tree for opportunistic routing protocol

LIU Huiyuan1，2, DONG Chunyang2, HUANG Qiong2

(1. Chongqing School of Industry, Chongqing 400043,P.R.China； 2. Chongqing Key Lab of Mobile Communication Technology, Chongqing University of Posts and Telecommunications, Chongqing 400065,P.R.China)

In order to effectively forward and deliver the messages in the Vehicle Ad Hoc Networks (VANETs), the selection of routing node is the key issue in the Vehicle Networks in the case of fixed node buffer and limited number of message copy. Therefore, in this paper, we propose an effective opportunistic routing protocol for the multiple copies of VANETs based on the decision tree theory (D-Tree). The proposed scheme takes the intermediate node’s transmission and connection as the set of multiple attributes, and then we can obtain a rule of message forwarding based on the attributes and D-Tree. Furthermore, we can combining the advantages of multiple copies routing scheme and adopting the storage-carry-forwarding of opportunistic routing to deliver the messages. Simulation results confirm that our proposed D-Tree network model, decision rule procedure and calculating method improve the success rate of delivery compared with the conventional Bubble routing algorithm by 10% under the case of density environment. The proposed scheme also demonstrates better performance in delivery delay.

vehicular Ad hoc networks(VANETs); opportunistic routing; routing algorithm; decision tree; multiple copies

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

2015-12-21

2016-06-12

董春阳 409105807@qq.com

国家自然科学基金项目(61171111)；重庆市自然科学基金(CSTC2011jjA40046)

Foundation Items：The National Natural Science Foundation of China (61171111)；The Natural Science Foundation Project of CQ CSTC(CSTC2011jjA40046)

TN914.53

A

1673-825X(2016)06-0769-08