一种软件定义车载自组织网络的QoS 路由算法

杜欣欣，胡晓辉，赵佳楠

（兰州交通大学电子与信息工程学院，兰州 730070）

0 概述

车载自组织网络（Vehicular Ad-Hoc Network，VANET）是以车辆为节点的特殊移动自组织网络（Mobile Ad-Hoc Network，MANET）［1］。VANET 高动态特性会导致拓扑频繁变化和网络碎片，使当前建立的相关QoS 指标变化迅速，所选的最佳路由会变得低效甚至不可行。而基于VANET 的经典路由协议（AODV、OLSR 等）主要集中在最小化所提供路径的跳数上［2］，不同服务业务QoS 保障困难，如消防、救护车、警车紧急消息和视频流媒体等对传输时延、抖动、分组丢失率有严格制约，若约束无法得到有效的保证，可能会影响用户的视觉体验和听觉体验，甚至会造成重大交通事故。受多个QoS 约束搜索可行路由被定义为NP-Hard 问题，即无法在时间域内求解多项式问题。因此，需要合理的方案解决该问题。

软件定义网络（Software-Defined Network，SDN）是一种新兴的网络架构，它在物理上解耦控制平面和数据平面，在逻辑上通过抽象网络基础设施，将控制和智能决策集中在控制器中［3］，能更有效地实现网络资源分配和调度。因此，将SDN 应用于VANET以简化应用功能，协调路边基础设施（RSU），建立可靠和高效的V2V 和V2I 通信路由，并为VANET 中QoS 优化提供了全新的解决方案。

目前，VANET 中QoS 路由主要基于QoS 参数，由源车辆主动或按需寻找下一跳直至目的车辆。文献［4］利用车辆移动速度、密度和衰落条件提出一种基于移动感知区域的VANET 蚁群优化路由算法。使用蚁群算法来寻找网络中节点之间的多跳路由，以帮助解决链路故障。为了实现可扩展性，将网络划分为多个区域并采用主动方式来查找区域内的路由；对于区域间的路由则使用存储在每个区域的本地信息来进行查找，从而减少广播和拥塞。但由于使用主动的方法来更新域内路由表，导致了较高的路由控制开销。文献［5］将势态感知模型和蚁群机制相结合，提出一种基于势态感知的车辆自组织网络QoS 路由算法，该算法的目标是寻找受多种QoS约束的最佳路径。为了降低计算最优路由所带来的风险，利用情景感知级别和蚁群算法制定了相关的对策，以保证数据的可靠传输。但当网络密度增加时，已建立的路由可能会变得更长，降低了路由的可靠性。如果未发送数据包的一个片段，则会丢弃整个数据包从而造成算法的丢包率较高。文献［6］提出一种基于OLSR 协议的机制，以建立稳定和可持续的移动自组网。在该机制中通过计算邻节点的相对移动度，之后将其代入到稳定性函数中，以稳定性函数作为主要路径选择准则从而选择稳定和可持续的多点中继。该机制在多QoS 约束下减少了多点中继的路由表重计算过程，但并未考虑负载平衡和节点剩余能量等指标。文献［7］提出一种基于适应度的AODV 路由协议，在车辆节点组成网络后，通过广播Hello 报文发现源节点和目的节点之间的路由。然后，结合QoS 适度值和欧几里得距离来确定稳定的下一跳节点，但在路由维护阶段依旧采用了AODV 原有维护更新方式，这将消耗大量的能量。文献［8］提出一种基于QoS 约束、不信任值和移动约束的路由协议。该协议利用QoS 要求、不信任值和移动性约束参数来计算每个车辆的QoS 值，基于此值来选择传输路径，保证了链路的稳定性。但VANET 的仿真场景过于简单，缺少二维复杂路况，不适用于真实场景。

SDN 控制器可以利用车辆数据来定位转发决策，然后确定转发信息分组和到达目的地的最合适路由。文献［9］实现了AODV 在SDN-VANET 中的应用，并且基于最基本的QoS 指标对其性能进行了分析，证明了SDN 架构具有一定的优势。但所选QoS 指标过于单一，不符合实际业务所需的QoS。文献［10］采用了集中式控制器来高效寻找数据报文的有效传递路径。但是，由于所提出的解决方案依赖复杂的预测机制来更新网络拓扑，导致计算延迟大，吞吐量低，不适用于密集车辆情况。而文献［11］采用另一种动态更新车辆拓扑的方法，减少了对路由发现的泛洪需求。该算法依赖信标消息不断更新和跟踪拓扑的动态变化，并使用马尔科夫链模型来确定路由的优先级。但由于算法复杂度高，在高密度环境下扩展性较差。文献［12］提出一种基于雾计算的软件定义车载自组织网络新型节能多播路由协议。此外，还提出了一种基于优先级的调度算法和分类算法，用于在对组播请求进行分类后根据其应用类型和期限约束对组播请求进行调度，地理分区概念的应用减少了SDN 控制器的负载开销。该协议有效减少了平均端到端延迟、归一化开销负载和多播能量消耗。但该协议也存在一定的局限性，一方面是没有考虑到车辆的安全验证，另一方面是车辆的快速接入和断开造成多播协议的开销较大。

本文将SDN 和VANET 相结合，构造SDN-VANET异构混合网络，并提出一种应用于SDN-VANET 架构的QoS 路由算法，利用SDN 的高灵活性、可编程性等优势保障业务传输QoS。该算法在业务调度阶段，SDN控制器优先调度传输截止时间少的车辆业务，保障紧急业务传输。然后在路由选择阶段，基于蛙跳算法设计出自适应混合中继选择算法。通过设计与QoS 约束相匹配的适应度函数来衡量转发路径的优劣，并能根据当前网络状态自适应地更新改进转发策略。最后在路由维护阶段设置备选链路机制和资源消耗阈值，保障业务传输的QoS。

1 系统模型

1.1 SDN-VANET 架构

SDN 控制器为VANET 路由策略提供了更好的适应性和灵活性，在SDN 控制器集中调节下可以实现车辆数据统筹调配，以改善管理车与车（Vehicle to Vehicle，V2V）和车与基础设施（Vehicle to Infrastructure，V2I）通 信。SDN-VANET 架构如图1所示。

图1 SDN-VANET 架构Fig.1 SDN-VANET architecture

SDN-VANET 架构是混合了IEEE 802.11p、蜂窝网络和SDN 的重构体系，利用不同通信技术完成WAVE 协议族的控制数据平面消息转发［13］。SDNVANET 主要包括应用层、控制层和数据层。

应用层：通过北向接口向下层提供关系数据库、车载应用、身份认证信息、环境服务和安全服务等商业服务应用。

控制层：SDN 控制器收集车辆信息（如车辆位置、速度）、网络拓扑信息和交通流信息，并通过南向接口进行流表项的更新，下达路由转发、拓扑管理和交换管理等命令。

数据层：由车辆节点、RSU 和基站组成。RSU 和基站为车辆与SDN 控制器通信提供了4G 网络和WAVE 无线网络等异构接入方式。车辆装载具有V2V 和V2I 通信功能的车载单元（On Board Unit，OBU），定期发送通知到SDN 控制器以增强网络配置并接收来自SDN 控制器控制消息依此来执行数据包的转发行为。具体模型如下：

1）每个RSU 负责一个区域，且每个RSU 之间互不冲突。

2）当车辆进入一个新区域时，能自动发起对应区域RSU 的通信响应并通过GPS 定期向RSU 汇报自身坐标、速度和加速度等动力学信息。车辆与RSU 通过IEEE 802.11p 协议交换信息。RSU 仅传输SDN 控制器下达的流表项命令，无法帮助车辆转发数据包。

3）RSU 能够感知本区域所有入网车辆，并动态存储维护一个车辆信息表，一旦车辆离开该区域，RSU 将自动删除离开车辆的信息。

1.2 路径参数

为了实现路由在VANET 中的执行过程，以加权间接图G（V，E）形式对车辆节点构成的组网拓扑进行建模，其中V代表车辆节点，E是网络中车辆节点之间路径的集合［14］。对于任意两个节点i和j之间的路径，使用ei，j，e∈E表示。在路径ei，j中，为了方便对网络参数进行描述和研究，路径参数选择带宽Bi，j、时 延Ti，j、抖 动Di，j和传输能量消耗Ci，j。除考虑带宽、时延和抖动等基本QoS 因素外，还特别考虑了传输能量因素。随着电动汽车的发展趋势越来越明显，传输能量也应是考虑的参数之一。

车辆节点i和j之间的路径传输能量消耗定义为：

其中：Cs是转发数据所需能量；Cr接收数据所需能量。

当两个车辆节点需转发数据量为k，距离为l时，Cs定义为［15］：

其中：Eelc为电耗能参数；l0为两个节点之间的传输距离阈值；ε1为放大参数。

当接收数据量为k时，Cr(k)定义为：

1.3 约束条件

在某个时隙内，组网中可能存在多个车辆同时需要转发多个数据包数据的情况，为了避免网络阻塞和问题路由，在设计协议时需要对数据包转发条件加以限制。其次还需对剩余带宽及时进行校正，确保下一个车辆业务也能有效传输。

约束1如果数据从节点i发送到j，变量λ将取值1；否则，其值将为0。

约束2当流从节点i发送到节点j时，不得从节点j回流到节点i，用于避免循环。

约束3从节点i发送到节点j的数据流必须小于或等于从节点i到j的链路剩余带宽。其中bi，j为节点i和j链路剩余带宽。

约束4为了提高选择最佳路径时的准确性，组网中节点i和j之间的链路的剩余带宽必须在执行转发或丢弃动作后进行更新［16］。bi，j的计算如式（7）所示：

2 基于SDN-VANET 的QoS 路由算法

2.1 协议概述

车辆节点i进入RSU 控制区域后，向RSU 提交业务请求消息Si，业务请求消息Si主要包含：源节点（Source_IP Address），目的节点（Destination_IP Address），传输的信息量（Size），截止日期（Dealine），QoS 约束信息。业务请求消息Si格式如图2 所示。

图2 业务请求消息格式Fig.2 Service request message format

在图2 中，Type 为消息类型，数值定义为1 表 示业务请求消息，Reserved 为保留位，为后续RSU 设置优先级而预留，B、T、D、C则代表此项业务所需带宽BQoS、时延TQoS、抖动DQoS以及能耗CQoS。

RSU 根据截止日期在Reserved 中为其添加优先级Pi，其中Pi与截止时间成负相关，即截止日期越小优先级越高。之后RSU 向SDN 提交Si，Si将进入等待队列W_queue 等待调度。SDN 控制器根据Pi调度队列中的请求，完成车辆节点的业务请求，为其寻找合适的节点进行转发。车辆业务申请流程如图3 所示。

图3 车辆业务申请流程Fig.3 Procedure of vehicle service application

协议主要分为邻居发现、路由选择和路由维护3 个部分。

1）邻居发现

车辆节点定时向RSU 发送Hello 包，汇报车辆自身基本信息。当RSU 收到Hello 包后，会将包信息加入到该区域的车辆信息表中，根据车辆的通信范围寻找该车辆的邻居节点，并写入该区域的车辆信息表。然后RSU 回传一个包含该车辆地理信息以及车辆邻居节点信息的AckHello 包。车辆也可以根据回传的AckHello 包信息判断是否自己脱离了该RSU控制区域，如果脱离了该区域RSU，车辆将重新发送Hello 包直到下一个RSU 返回AckHello 包。RSU 所维护的车辆信息表包括以下字段：车辆ID（Vehicle ID），邻居节点ID（Neighbor），下一跳（Next hop），flag 标记（Flag），车辆是否被选择为中继转发节点和不转发列表（Not forwarding）。不转发列表定义为当且仅当车辆被选择为中继节点且有意义时，将执行SDN 控制器下达的不转发命令，不转发列表中车辆发来的所有数据包。车辆信息表结构如表1 所示。

表1 RSU 车辆信息表结构Table 1 RSU vehicle information table structure

2）路由选择

若源节点所传输数据的目的节点为其邻居节点，则直接进行传输，否则SDN 控制器根据随机点路移动模型和源节点所提出业务请求的截止时间，预测在该时限内各车辆位置，确定符合截止日期约束的备选中继车辆。在中继选择过程中为满足不同业务的QoS 约束指标，提出一种基于改进的自适应混合蛙跳中继选择算法（Adaptive Hybrid Shuffled Frog Leading Algorithm，AH-SFLA）。在保障各约束的同时，以最小化QoS 资源将数据包从源车辆传输到目的车辆。

3）路由维护

若车辆出现异常情况即无法进行通信，此时SDN 控制器根据AH-SFLA 的计算进行次优替换。次优路径替换的首尾是故障车辆的前驱和后继，这样有利于提高计算效率，降低控制器运算开销。同时为避免车辆被过度选择为中继，设置车辆资源消耗变换率阈值，来动态实现车辆资源维护［17］。若车辆i的初始资源为Qi，在被选为中继节点后带宽资源变为，当节点资源变化率满足以下不等关系式时：

即表明车辆i的资源消耗变化达到了设定的阈值R。这时车辆i向SDN 控制器申请重路由请求，SDN 控制器收到重路由请求后，根据AH-SFLA 算法重新选择一条通信链路。这种动态路由维护的方式可以减少车辆被过度使用，及网络故障问题发生的概率。

2.2 基于改进的自适应蛙跳中继节点选择算法

蛙跳算法是进化计算领域一种新兴有效亚启发式、结合遗传学模因演算的群体进化算法，该算法拥有优良高效的计算性能和解空间能力［18］。为了找到多QoS 约束下的最优路径，本文提出了AH-SFLA 算法，该算法结合当前网络状态自适应地动态搜寻最优解。主要步骤如下：

步骤1种群编码。设有N个车辆节点，dmax为种群中节点最大出度，则车辆节点的基因维数L定义如式（9）所示：

通过采用二进制编码来表示节点的基因位，即可选路径。若车辆节点出度为1，该节点可选下一跳仅有1 个，用一位二进制比特位0 对该路径进行编码；若车辆节点通信范围内可选择作为下一跳的节点有4 个，用两个二进制比特位00、01、10、11 来表示4 个可选的传输路径，并以此类推。如果车辆节点的出度超过了基因维数，则采取整取余的方法对多出的维数进行编码，并对余数编码作特殊标记以便区分。如果车辆节点编码数小于基因维数，则剩下的基因位将忽略不计。

步骤2适度函数构造。AH-SFLA 在进化搜索中主要依赖种群内部环境条件，以适度值为基准进行搜索和改进［19］。AH-SFLA 适应函数是基于QoS约束加权和之比而制定的，该函数是用于量化约束确定传输最优路径，保障各业务QoS 同时降低传输能量消耗。因此，适度函数如式（10）所示：

其中：μb、μc、μt和μd表示相应指标的权重因子，即不同的业务需求，对不同的约束所占比重有所不同。例如视频流的业务需求，μb和μt的权重因子大于其他业务需求。

步骤3初始化种群。满足通信范围和截止日期约束的N个车辆节点组成初始种群X={X1，X2，…，XN}，在约束D维问题的解空间中第i个节点表示Xi={xi1，xi2，…，xiD}。初始种群确定以后，将种群N内的每个节点按照式（10）计算适度值并降序排序，且记录种群中适度值最小的节点为Xg_best。

步骤4子种群划分。初始种群划为J个子种群，并将第1 个节点分配给子种群1，第2 个节点分配给子种群2，第J个节点分配给子种群J，第J+1 个节点分配给子种群1，以此类推直到每个子种群内包含I个节点，初始种群与子种群关系满足N=I×J。同时需记录子种群中适度值最小的节点Xf_best和适度值最大节点Xf_worst。

步骤5局部搜索。局部搜索仅对子种群内适度值最大的车辆节点Xf_worst进行进化更新策略，更新策略如式（11）和式（12）所示：

其中：rand 为0～1 的随机小数；Ri为移动步长，满足-Rmax≤Ri≤Rmax约 束，Rmax为其移动最大步长；若，则用更新后的取代当前子种群最差节点Xf_worst，否则以概率pm动态进行变异更新。pm由SDN 控制器依据当前网络状态下的带宽可用率、数据堆积率、车辆节点稳定性以及对应影响因子构成。更新策略如式（13）、式（14）和式（15）所示：

对于变异更新操作，在正常情况下根据数据流的性能要求指标采取相应的变异方案，产生对应的个体。若更新过后的适应度仍没有取得改进，则按式（16）随机生成新的个体并替换。

其中：max 是当前网络状态下随机最大值；min 为随机最小值。

步骤6全局搜索。局部搜索完成后，将重新混合构成的下一代种群记录适度值最小车辆节点Xg_best。判断算法是否达到最大迭代次数G，若满足则结束搜索并输出；否则将继续进行搜索。

2.3 AH-SFLA 实现

为了更好地适应VANET 动态变化，AH-SFLA会根据当前网络状态对转发路径进行动态调整更新，这主要是通过局部搜索中变异更新操作产生当前网络状态下的可选路径，根据适度值选择转发代价较小路径转发，达到自适应目的。算法基本流程为首先对VANET 中车辆节点进行基因编码，通过车辆移动模型和数据包截止时间约束确定初始种群，根据式（10）计算适度值，进行子种群划分。SDN 控制器基于当前网络状态对子种群的最差个体进行动态变异更新，并对更新后的子种群混合再次计算适度值选出新种群最优，这样的动态更新策略能更好地自适应VANET 的动态变化，最大化地利用网络资源，保障各业务的QoS。算法伪代码如下：

算法1AH-SFLA 中继节点选择算法

3 仿真实验与性能分析

在仿真实验中，联合SUMO［20］、Mininet-wifi 和POX［21］来仿真SDN-VANET 环境［22］。城市道路模拟是通过Openstreetmap 和SUMO 创建的1 500 m×1 000 m甘肃省兰州市街道区域，如图4所示。而POX和Mininetwifi 则实现SDN 控制器和车辆节点的模拟和配置，从而建立SDN-VANET 的仿真环境。环境参数配置表如表2 所示。

图4 兰州市道路拓扑Fig.4 Lanzhou city road topology

表2 环境参数配置Table 2 Environmental parameter configuration

为了证明本文路由协议的有效性和SDN 体系架构优越性，将所提出的路由协议和单播路由协议IGA［23］、IICSFLA［24］在不同场景下进行对比。IGA 是基于遗传算法而设计的多约束单播路由协议，该协议在计算适度函数时引入一种新的惩罚函数和约束权重，加快了种群“优胜劣汰”的速度。而IICSFLA是结合免疫算法和蛙跳算法的路由协议，该协议的更新策略是通过克隆变异种群最优节点完成的。IGA 的参数配置如表3 所示。

表3 IGA 参数配置Table 3 IGA parameter configuration

模拟实验中使用的性能指标如下：

平均端到端延迟［25］：指数据包从源传输到目的地所需的平均时间延迟，包括所有类型的延迟，如排队延迟、传送延迟以及路由发现缓冲延迟。

丢包率：是指测试中所丢失数据包数量占所发送数据组的比率。

标准化路由开销［26］：发送控制数据包与成功接收数据包之间的比率。该度量不考虑控制器的控制开销。

场景1研究车辆密度对AH-SFLA、IGA 和IICSFLA 性能的影响，此场景的参数如表4 所示。

表4 场景1 参数配置Table 4 Scenario 1 parameter configuration

图5 为不同网络密度对AH-SFLA、IGA 和IICSFLA 协议的性能度量。图5（a）显示了AHSFLA、IGA 和IICSFLA 的平均E2E 延迟。从图中可以明显看出，AH-SFLA 的平均E2E 延迟要低于IGA和IICFLA，相比IGA 和IICFLA，AH-SFLA 分别平均提高了57.74%和46.6%。SDN 控制器根据中继节点选择算法计算最佳传输路径，以此为依据更新流表项。车辆节点无需启动泛洪机制寻找下一跳，而通过更新后的流表完成转发操作。图5（b）显示了3 种路由协议的丢包率与车辆密度之间的关系。AHSFLA 比IGA 和IICFLA 的丢包率平均降低了29.9%和18.6%。随车辆密度的增加，3 种路由协议的丢包率都有所下降，这是因为在车辆密度较低时车辆间的连通性较差，但随着车辆节点的增多，车辆节点会面机遇的概率增加，降低了空路由的概率。在车辆密度稀疏时AH-SFLA 协议的丢包率高于其他两种路由协议，原因是数据包转发受到了流表更新的限制，但随着车辆密度的增加，SDN 控制器可以灵活地选择最佳路由，使得数据包受流表限制减少，因此车辆间的数据传输更加可靠。图5（c）描述了3 种路由协议车辆密度与标准化路由开销之间的关系。相比其他两个协议，AH-SFLA 的标准化路由开销分别提高了36.93%和27.2%。在AH-SFLA 协议中，SDN 控制器计算出最佳路径下发更新流表，以在指定路径上的节点建立车辆间通信。此外，由于在确定路径时考虑了稳定性参数，减少了重复路由通信，车辆间通信将变得更加稳定。IGA 和IICSFLA 协议在缺乏网络状况全局概览的情况下，通过贪婪和泛洪路由技术进行通信，标准化路由开销随着车辆数量的增加而显著增加。

图5 不同车辆密度下IGA，IICSFLA 和AH-SFLA 的性能指标Fig.5 Performance indexs of IGA，IICSFLA and AHSFLA with different vehicle densities

场景2研究车速对 AH-SFLA、IGA 和IICSFLA 性能影响，在不同最大车速下根据评价指标来证明AH-SFLA 的有效性。此场景的参数配置如表5 所示。

表5 场景2 参数配置Table 5 Scenario 2 parameter configuration

图6展示了不同速度下AH-SFLA、IGA和IICSFLA协议的性能指标。

图6 不同车速下IGA，IICSFLA 和AH-SFLA 的性能指标Fig.6 Performance indexs of IGA，IICSFLA and AHSFLA with different speed

图6（a）所示为AH-SFLA、IGA 和IICSFLA 的平均E2E 延迟。通过增加车辆速度，车辆间通信链路断开更加频繁，寻找新路径的过程将增加延迟。然而AH-SFLA 的平均E2E 延迟优于IGA 和IICSFLA，因为AH-SFLA 协议可以通过SDN 控制器掌握全局拓扑信息，能及时校正更新流表项从而延迟较低。如图6（b）所示，AH-SFLA 协议丢包率分别优于IGA的31.1%和IICSFLA 的21.32%。在高动态拓扑变化情况下，如何保证在多QoS 约束下寻找最优路径点，SDN 控制器的优势显而易见。如图6（c）所示，当车辆速度从5 m/s 逐渐増长到30 m/s 时，网络中链路断裂次数增多，3 个协议的标准化路由开销随之增加。车辆移动速度増加，导致IGA 和IICSFLA 协议在建立路由时极易发生断裂，需要发送大量控制报文来进行路由的重新建立。而AH-SFLA 具有QoS 路由维护机制，在车辆通信出现断裂时能及时恢复，比其他两种协议在标准化路由开销方面有着较好的性能表现。

4 结束语

VANET 是一种特殊的MANET，具有节点高速移动、拓扑动态变化的特点，但也导致QoS 无法得到有效保障。针对该问题，本文将SDN 与VANET 相结合，提出一种适用于SDN-VANET 的QoS 路由算法。SDN 控制器根据全局信息，计算出一条符合业务QoS 需求且转发代价最小的解作为转发路径。同时根据VANET 动态变化，通过适度函数自适应地调整转发路径。仿真结果表明，AH-SFLA 协议在平均E2E 延迟、丢包率、标准化路由开销方面都有所提高，在保证QoS 上具有一定的优势。下一步将引入博弈理论对VANET 中因资源有限而出现的自私车辆进行分析研究，并结合演化博弈，设计有效的惩罚机制促使自私车辆转发数据包，降低协议的丢包率。