0 引言

近年兴起的车载自组织网络原是移动自组织网络的一个分支，随着IEEE802.11p^[1]、IEEE1609^[2]等标准的起草以及逐步确立，车载自组织网络逐渐从移动自组织网络中独立出来。车联网(Vehicular Ad Hoc Network,VANET)是由车辆与路边基础单元组成的车载网络，是以车载自组织网络为基础的多跳混合无线网络。与其他无线网络相比，如移动自组织网络、无线传感器网络、无线网状网络等，车联网具有网络规模大、网络拓扑受限、节点移动可预测性等特征，因此车联网中的路由与转发是一个难点，如何设计具备良好的动态自适应性、高可靠性、高可扩展性的路由算法是车联网研究的一个重点。

目前常用的移动自组织网络路由协议有最优链路状态路由(Optimized Link State Routing,OLSR)协议、目的节点序列距离矢量路由(Destination Sequenced Distance Vector routing,DSDV)协议、无线自组网按需平面距离向量路由(Ad Hoc On-demand Distance Vector routing,AODV)协议和动态源路由(Dynamic Source Routing,DSR)协议。在OLSR^[3]中，节点是通过定期广播Hello包互相发现的，因而运行OLSR算法的节点并不能马上知道链接的断开，因此在模拟城市路况的密集路段上OLSR的性能非常不理想^[4]。而DSDV^[5]采用了Bellman-Ford算法寻路防止出现路由环，还采用了增量更新的方法更新路由信息，提高了寻路效率并减少了网络开销。然而DSDV并不能及时发现链路状态的更新，同样不适合在动态性高的车联网使用^[6]。在AODV^[7]中，节点则是通过动态维护一张路由表来实现路由，然而在动态性高的网络上，路由表的信息很快就失效，AODV需经常重新找路。DSR则是更加纯粹的需求驱动型路由协议^[8-9]，它采用一种名为“源路由”的路由方式^[10]，每个节点只知道通往目标的下一跳是哪个节点，而不知道整条路经的节点，然而路由存储在路由缓存上，并会被加在每一个发送的数据包的包头上。因此DSR的实现、发送开销都更大。有不少学者设计车联网路由中考虑车辆移动速度及位置^[11]、概率论统计^[12]、特殊车辆节点等因素^[13]，然而都不能满足车载网高动态性的需求。

软件定义网络(Software-Defined Network,SDN)是近年来兴起的路由技术，主要应用在有线网络^[14]，以提高其网络带宽的利用率。近几年来，软件定义无线网络方面的研究逐渐成为热点^[15]，在多跳无线自组织网中，文献^[16]设计了基于SDN的路边单元车载云，包含了OpenFlow控制器、云控制层和云资源管理，而数据传输包括了物理数据层面和抽象控制层面。文献^[17]设计了软件定义无线网的编程抽象模块，包括状态管理、资源配置、网络监控和网络重配置。而文献^[18]则针对无线融合网络中的问题设计了抗灾网络，该网络使用了SDN技术去自动选择状态好的网络连接，然后通过周期性监测这些网络连接上节点的网络状态，确定路由所经过的节点。虽然软件定义无线网络相关研究不少，然而SDN在车联网中应用研究不多。

SDN能够更好地实现网络资源的弹性分配和控制，在可扩展性、效率等方面都有明显的优势，这些技术优势正符合车载网络在节点移动性、网络动态性、网络规模等方面的特征和需求，因而在车联网中引入SDN的思想能够更好地解决车联网目前存在的难点。特别是SDN基于控制器的这种集中式管控思想，可以解决车联网无中心、多变化导致的节点协同困难。然而SDN主要在有线网络中应用，其体系结构考虑的是有线链接、固定设备的情况，网络拓扑稳定。而车联网基于车与车(Vehicle-to-Vehicle,V2V)和车与路边(Vehicle-to-Roadside,V2R)单元通信组成的动态性强的无线网络，拓扑动态变化是一般的SDN未考虑的问题。这是在车辆网中应用SDN的主要挑战，也正是本文工作的主要目标。自组织网络中采用SDN技术已经有一些工作^[15-18],也是在动态拓扑下进行SDN实现。

为了满足车联网特性，把每条路段看成一个逻辑链路，整个车联网看成由多个逻辑链路组成的网络，而局部控制器负责维护链路的稳定性。车联网虽然网络拓扑动态性强，然而在每条路段中，可以选择出相对稳定的车辆，由这些车辆负责流数据的转发，局部控制器负责这些车辆的选择策略和维护，提高数据通信的可靠性。

因此，本文提出了软件定义车联网的数据转发机制，本文的主要贡献包括：1) 设计了软件定义车联网的分层次网络模型，该模型由局部控制器和车辆组成，实现控制与数据转发分离，具有可扩展性、独行性等特点；2) 设计了车辆路由转发机制，该机制采用动态规划和二分搜索的方法，以实现高效的数据转发；3) 通过仿真验证了本文设计的机制具有更好的效果。

1 系统模型

要把SDN引用到车联网中，首先需要设计软件定义车联网的网络模型，软件定义车联网网络模型如图 1所示，具体假设如下：

1) 整个车联网分成多个路段，每个路段都有一个局部控制器，局部控制器的通信范围能够覆盖整条路段，不同局部控制器负责的区域相互不重叠。

2) 每个路段上有多个车辆，每辆车具有一定的通信范围，车辆只能和通信范围内的其他车辆进行数据分发，而不在通信范围内的车辆只能通过多跳转发实现数据路由。每个车辆知道自身周围邻居车辆的ID和位置。

3) 车辆进入局部控制器通信范围内，能够发现其所在区域的局部控制器，车辆和局部控制器进行通信，车辆和局部控制器之间只能进行控制信息通信，局部控制器不能帮车辆进行数据转发。

4) 局部控制器能够知道其通信范围内每辆车的ID、位置以及运动速度，并动态维护一个车辆信息表，该信息表保存当前时间内位于其控制区域的车辆基本信息。

5) 系统使用IEEE802.11p中指定的控制信道(Control CHannel,CCH)Ch.178发送路由协议控制信息，使用IEEE802.11p中指定的六条服务信道(Service CHannel,SCH)中的一条传送数据信息。

2 软件定义车联网的数据转发算法 2.1 协议概述

每辆车会定时发送Hello包给其范围内的局部控制器，报告自己的地理信息，当局部控制器收集到来自自己的控制区域的Hello包后，会将车辆信息加入对应控制区域的车辆信息表中，并根据车辆信息表的信息以及控制区域的范围，返回AckHello包，AckHello内包含该车辆的地理信息以及车辆所在的控制区域的范围信息。车辆可以根据这些信息，判断是否需要再次发送Hello包，更新控制器所掌握的自己的地理信息，确保控制器对自己的位置预测误差在预设的范围内。车辆也可以根据这些信息，判断自己是否已经脱离了一个控制器的控制，重新定时发送Hello包直到下一个控制器返回AckHello包。

每个局部控制器为它所控制的控制区域维护一个车辆信息表，车辆信息表保存了其控制区域所有车辆的信息。当局部控制器收到来自所在控制区域的车辆发来的Hello包时，会更新车辆信息，当车辆离开控制区域时，车辆信息将从车辆信息表中删除。局部控制器所维护的信息包括以下几项：

1) 定位信息，包括位置、速度；

2) 选路过程中动态规划时所产生的临时变量，包括下一跳ID以及最小跳数；

3) 车辆的“钦点”结果，指代这辆车是否被选择为转发车；

4) 不转发列表，仅当车辆为转发车时有意义，该转发车将被要求不转发在不转发列表中的车发来的所有数据包，用以防止广播风暴。

2.2 数据转发车辆选择算法 2.2.1 算法描述

局部控制器根据其维护的车辆信息，选择进行信息转发的车辆，其数据转发车辆选择算法可分为三个步骤：确定二份查找的搜索区间，进行二分查找，根据结果选择转发车辆形成转发链。

1) 确定二份查找的搜索区间。

二份查找算法能高效地在区间中找出符合条件的结果。为此需要先确定搜索区间。区间的下界为0，代表不能建立任何的链接。算法的上界是目前有可能选出的最稳定的转发链可能维持的最长时间。这个时间由逗留在首保护区间最久的车辆的逗留时间确定，因为在这个时间之后，首保护区间中原有的车辆已经全部离开首保护区间，必须重新在首保护区间选择出转发车，以保证路段之间的通达性。

2) 二分查找。

根据确定的搜索区间，计算中值mid，然后计算在当前控制区域内是否存在一条能维持mid时间以上的转发链，如果能，则更新区间下界为中值mid，否则更新区间上界为中值mid，然后根据区间范围计算新的中值，循环计算，直到区间长度小于预先设定的σ，结束二分查找。

为了确定控制区域内是否存在一条能维持x时间以上的转发链，本文采用动态规划的方法为控制区域内的每一辆车计算若作为转发车时的下一跳ID(next_id)以及最小跳数(minhop)。转移方程如下：

$\begin{align} & next\_i{{d}_{i}},\min ho{{p}_{i}}= \\ & \left\{ \begin{matrix} j,\min ho{{p}_{j}}+1, & CHL\left( i,j,mid \right) \\ next\_i{{d}_{i}},\min ho{{p}_{i}}, & 其他 \\ \end{matrix} \right.;{{d}_{i}}＜{{d}_{j}} \\ \end{align}$

(1)

其中CHL(i,j,x)函数的计算如下：

v_i、v_j为车i、车j在当前控制区域的速度，d_i、d_j为车i、车j在当前控制区域的距离。当车i、车j与时间x满足以下关系时CHL(i,j,x)的值为真，不满足则为假。

a) d_j-d_i＜signal_range //当前车i与车j能通信；

b) d_i+v_i*x＜road_legth //x秒后车i仍在当前控制区域；

c) d_j+v_i*x＜road_legth //x秒后车j仍在当前控制区域；

d) |d_i+v_i*x-d_j+v_i*x|＜signal_range //x秒后车i与车j能通信；

e) minhop_j+1＜minhop_i //使用车j作为下一跳点比当前的选择更佳。

在计算开始之前，除能在尾保护区间的逗留长于x时间的车初始化minhop=1外，所有车都初始化为minhop=INF；而所有车都初始化为next_id=null。

在对路段中所有车辆完成计算后，若能在首保护区间中找到有车辆的minhop＜INF，即首保护区间中存在车辆能建立转发链，则认为控制区域内存在能维持x时间以上的转发链；否则认为控制区域内不存在能维持x时间以上的转发链。

3) 根据结果选择转发车辆。

如果区间下界仍为0，说明算法无法找到任何的链接，返回空的转发链。

如果区间下界不为0，则说明存在链接，依照区间下界，再次运用上述的动态规划计算控制区域中每一辆车的转发信息，然后从首保护区间中选择跳数最少的，预期逗留在首保护区间最久的车辆作为首辆转发车，并根据其下一跳，递归选择车辆生成转发链，直到下一跳为空。

此时便获得了一条完整的转发链路，数据转发车辆选择算法伪代码如下所示。

max_time:=0

FOR each Car in The_First_Section(TFS) DO

time_left_in_TFS:=

(LengthOfTFS-PositionOfCar)/VelocityOfCar;

IF time_left_in_TFS>max_time THEN

max_time:=time_left_in_TFS;

L:=0;R:=max_time;

WHILE R-L>σ DO

mid:=(L+R)/2;

ALL minhop:=INF;

FOR i:=the_farthest_car-1 to the_nearest_car DO

FOR j:=the_farthest_car to i+1 DO

IF d_j-d_i＜signal_range && d_i+v_i*mid＜road_length && d_j+v_j*mid＜road_length &&

|(d_i+v_i*mid)-(d_j+v_j*mid)|＜ signal_range && minhop_j+1＜minhop_i

THEN

next_id_i,minhop_i=j,minhop_j+1;

IF ∃Car in TFS,minhop≠INF THEN

L:=mid;

ELSE R:=mid;

ALL minhop:=INF;

FOR i:=the_farthest_car-1 to the_nearest_car DO

FOR j:=the_farthest_car to i+1 DO

IF d_j-d_i＜signal_range && d_i+v_i*L＜road_length && d_j+v_j*L＜road_length && |(d_i+v_i*L)-(d_j+v_j*L)|＜signal_range && minhop_j+1＜minhop_i

THEN

next_id_i,minhop_i=j,minhop_j+1;

min_minhop:=INF;

TheFirstCar:=NIL;

FOR each Car in The_First_Section(TFS) DO

time_left_in_TFS:=

(LengthOfTFS-PositionOfCar)/VelocityOfCar;

IF (time_left_in_TFS>L) && (minhop_Car＜min_minhop) THEN

min_minhop:=minhop_Car;

TheFirstCar:=Car;

ALL appointment:=NORMAL;

Next:=TheFirstCar;

WHILE Next≠NIL DO

appointment_Next=FORWARDER;

Next=next_id_Next;

2.2.2 举例说明

为了方便理解，举例说明。设路段长度为600 m，通信距离为250 m。搜索区间目标长度σ=0.5按照前面的定义，首尾保护区间长度应该是通信距离的一半，为125 m，但为了简化例子，本例子设首尾保护区间长度都为200 m。车辆位置及连接关系如图 2所示。表 1则给出了各车的准确位置、速度以及根据位置和速度计算得出的车辆离开控制区域的时间以及车辆离开首保护区间的时间。表 2则给出了车辆之间的连接的预测维持时间。

由于在首保护区中，只有车1以及车2，其中预期逗留时间最长的车1在15 s后就会离开首保护区，所以这里的二分搜索的上界是15 s，即搜索区间为[0,15]，那么第一个中值是7.5，那么4 → 6和5 → 6两条连接就被去掉了，变成如图 3所示，然后进行动态规划计算后结果如图 4所示。

由于有1 → 3 → 5这个通路连接首尾区间，而且车1离开首区间的时间是15 s、车5离开路段的时间是15 s都大于7.5 s，所以有一条可行的转发链，那么就要更新搜索区间为[7.5，15] s，新的中值为11.25 s。由于在刚才的计算中，余下的连接的持续时间都大于11.25 s，所以这一回合并没有去掉任何连接，依然能得到一条可行的转发链，那么再次更新搜索区间为[11.25，15] s，新的中值为13.125 s。此时2 → 4、3 → 4和4 → 5三条连接就被去掉了，结果如图 5所示，动态规划计算后的结果则如图 6所示。

此时1 → 3 → 5这个通路仍然存在，那么即仍有可行转发链，并且由于图 6即第四次二分后余下的所有连接的维持时间都大于等于搜索区间的上界15 s，所以直到搜索结束，余下的链路都如图 6所示。搜索一直进行到区间为[14.53,15] s，区间长度小于σ=0.5，搜索结束。

选出转发链后，控制器要将最新的转发链广播给邻近的控制器，以便它们修改辖下车辆的不转发表。

在最后一次动态规划中，获得了1 → 3 → 5这条转发链，由于搜索区间下界是14.53,不为0，所以返回这条转发链。那么现在只要让车1、车3、车5在接下来的14.53 s中向前转发数据包，就可以形成一条覆盖全路段的虚拟网线了。

3 仿真结果及分析

本次模拟采用NS-3::FriisPropagationLossMode信号衰减模，介质访问控制(Media Access Control,MAC)层采用NS-3::NqosWaveMacHelper进行配置，设备采用NS-3::Wifi80211pHelper进行配置。SCH选择IEEE802.11p中的Ch172信道，频率中心点为5.860 GHz，CCH选择IEEE802.11p中的Ch178信道，频率中心点为5.890 GHz。CCH和SCH的信道编码均为OfdmRate27MbpsBW10MHz。SCH上的设备的发射强度为23 dbm(测试通信范围约为437 m)，CCH上的设备的发射强度为31 dbm(测试通信范围约为1089 m)。

系统网络模型仿真如图 7所示。

实验中配置了3条道路，道路1从(0，0) 通往(1000，0) ，道路2从(1000，0) 通往(1000，1000) ，道路3从(1000，1000) 通往(2000，1000) 。在每条路中间均安放了一个局部控制器，三个局部控制器的通信距离(signal_range)均为400 m。二分搜索算法的σ设置为0.5。

为了方便地获取数据，在(0，0) 安放了一个数据源(Source)，在(2000，1000) 放置了一个数据接收终端(Sink)。在AODV、DSDV、DSR和OLSR的模拟中，Source和Sink均被当作普通节点。而在本文设计的系统中，Source和Sink被当作既不是局部控制器(Local Controller,LC)也不是车辆的第三类节点，只往SCH发包或监听SCH，不接收、不参与CCH的通信。ODV、DSDV、DSR和OLSR均只使用SCH。Source持续以500000 b/s发送单个大小为512 B的UDP(User Datagram Protocol)数据包，当运行AODV、DSDV、DSR和OLSR时，发送目标为Sink的地址；当运行本协议时，发送到广播地址。

模拟使用的数据集由道路交通仿真(Simulation of Urban MObility,SUMO)软件生成，车流总是从(0，0) 开往(2000，1000) 。本文采用2类共8组数据对三个算法进行测试。1) 车速对照组：5 m/s、10 m/s、15 m/s、20 m/s；2) 发车间隔(车辆密度)对照组：2 s、5 s、10 s、15 s。

1) 发车间隔变化仿真结果。

图 8是传递成功比随发车间隔变化结果，由图 8可知：本协议的传递成功比总是比其他四种分布式算法要高，特别是在车辆密度高时，本协议的传递成功比能达到0.9；而在车辆密度低，连接不稳定时，本协议算法的传递成功比仍是最好的分布式算法(DSDV)的两倍。

图 9是平均端到端延迟随发车间隔变化结果。

由图 9可以发现，本协议在发车间隔为2 s、5 s、15 s时，平均延迟均为最低，OLSR因在发车间隔为2 s、5 s时的高密度状态下，发送成功率为0。而在发车间隔为10 s时，结合图 8可知，AODV、DSDV、DSR三种协议的传递成功比均不足0.1，而此时本协议的发送成功比接近0.2，即在连接不稳定时，本协议虽然会花更长的时间传递，但传递成功比要比其他协议要高。

从图 8~9可以看出，传统协议(特别是OLSR)在车辆密度过高、或者车辆密度过低(连接不稳定)时，性能均会有所下降。同样的结果也可以在文献^[19-21]中发现。这是因为车辆密度高后，传统协议需要与更多地相邻节点通信交流信息，路由开销急剧变大。而采用了增量更新信息的DSDV虽然是在高密度环境下表现最好的，但性能依然无法比肩本协议。

2) 车速变化仿真结果。

图 10是传递成功比随车速变化结果，由图 10可以看出，本协议的传递成功比随车速变化不大，而其他四种协议在车速变大后，传递成功比均出现了下降。在网络结构较为稳定的车速5 m/s的环境下，四种对比协议都得了它们在几个数据点中最好的结果，但随着车速上升，网络拓扑变得不稳定，出现了明显的下降。而本协议的传递成功比一直很稳定，远高于其他四个协议。

图 11是平均端到端延迟随车速的变化结果。从图 11可以看到，除了本协议的平均端到端延迟随着车辆的速度的增加而平稳增加外，其他四种协议均在车速增加后，出现平均端到端延迟下降的情况。这是因为分布式算法在动态性较高的网络环境中，只能成功传递少量的包，更多的包被丢弃了，只有最优条件下(如主动式算法(AODV、DSR)恰好在找到路后，链路结构未发生变化时、网络质量最好的一瞬间所发出的)的包才能到达目标车辆，所以显示的平均端到端延迟要比本协议低。而OLSR在速度为15 m/s以上的环境下，并不能成功传递任何的数据包，所以在图 11上显示平均端到端延迟为0。同样的结果也可以在文献^[22]中发现。

3) 二分搜索循环次数。

在模拟的过程中，程序也对LC每次寻路时的二分搜索循环次数进行了统计(如表 3)。二分搜索算法大多在进行4到8次的搜索后便得到了结果，最大值不大于11，均值不大于8。可见二分搜索算法在这个应用中也是十分高效的。

通过以上实验结果可以看出，本文设计的软件定义车联网数据转发机制在传递成功比和延迟上都有较大优势，本文设计的数据转发机制比传统的自组织网络技术具有更好的效果，在传递成功比上提高大约100%，而端到端延迟时间降低大约20%。对比现有的车联网路由转发机制，机会网络主要考虑在车联网不连通的状态，通过车辆的相遇机会完成车辆间的数据交换，而动态路由更多的是由车辆根据地理位置、速度等信息来选择路由策略，车辆充当车辆选择和数据分发任务。车联网的节点动态性很强，这些技术也同样面临节点频繁移动，链路不稳定等问题。本文设计的软件定义车联网数据转发机制，使用分层次结构，局部控制器负责路由选择和控制信息发送，而车辆则只需要负责进行流数据转发，从而能够实现高效高可扩展高可靠的车联网数据通信。

4 结语

由于车载网具有高动态性、网络拓扑受限等特征，现有的数据转发技术无法满足车载网的需求。软件定义网络能够更好地解决有线网络带宽分配问题，其设计思想能够更好地解决车载网问题，因此本文研究如何利用软件定义网络的思想来实现车载网中的数据转发。首先，本文设计了一个分层次的软件定义车载网模型，该模型具有可扩展行、独立性等特征；其次，本文设计了一个完整的软件定义车载网中数据转发机制，在该机制中，控制和数据转发独立，以实现更高效的数据转发；最后，本文使用NS-3进行仿真，仿真结果表明，本文设计的数据转发比传统的数据转发技术效果更优。

软件定义网络技术能够更好地解决车载网问题，目前有不少学者在研究如何更好地实现软件定义车载网。下一个研究目标是如何利用软件定义网络技术实现车载网的带宽分配。