开放科学（资源服务）标志码（OSID）：

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所示。

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

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

控制层：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之间的路径，使用$ {e}_{i, j}, e\in E $表示。在路径$ {e}_{i, j} $中，为了方便对网络参数进行描述和研究，路径参数选择带宽$ {B}_{i, j} $、时延$ {T}_{i, j} $、抖动$ {D}_{i, j} $和传输能量消耗$ {C}_{i, j} $。除考虑带宽、时延和抖动等基本QoS因素外，还特别考虑了传输能量因素。随着电动汽车的发展趋势越来越明显，传输能量也应是考虑的参数之一。

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

$ {C}_{i, j}={C}_{s}+{C}_{r} $

(1)

其中：$ {C}_{s} $是转发数据所需能量；$ {C}_{r} $接收数据所需能量。

当两个车辆节点需转发数据量为k，距离为l时，$ {C}_{s} $定义为^[15]：

$ {C}_{s}\left(k, l\right)={E}_{\mathrm{e}\mathrm{l}\mathrm{c}}k+{\varepsilon }_{1}k{l}^{2}, l\le {l}_{0} $

(2)

其中：$ {E}_{\mathrm{e}\mathrm{l}\mathrm{c}} $为电耗能参数；$ {l}_{0} $为两个节点之间的传输距离阈值；$ {\varepsilon }_{1} $为放大参数。

当接收数据量为k时，$ {C}_{r}\left(k\right) $定义为：

$ {C}_{r}\left(k\right)={E}_{\mathrm{e}\mathrm{l}\mathrm{c}}\times k $

(3)

1.3 约束条件

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

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

$ {\lambda }_{i, j}\in \left\{\mathrm{0, 1}\right\}, \forall i, j\in V $

(4)

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

$ {\lambda }_{i, j}+{\lambda }_{j, i}\le 1, \forall i, j\in V $

(5)

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

$ k\le {\lambda }_{i, j}\times {b}_{i, j}, \forall i, j\in V $

(6)

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

$ {b}_{i, j}={B}_{i, j}-\sum {\lambda }_{i, j}k, \forall i, j\in V $

(7)

2 基于SDN-VANET的QoS路由算法 2.1 协议概述

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

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

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

协议主要分为邻居发现、路由选择和路由维护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所示。

2）路由选择

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

3）路由维护

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

$ \left({Q}_{i}-{Q}_{i}^{\mathrm{*}}\right)/{Q}_{i}\ge R $

(8)

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

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

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

步骤1  种群编码。设有N个车辆节点，$ {d}_{\mathrm{m}\mathrm{a}\mathrm{x}} $为种群中节点最大出度，则车辆节点的基因维数L定义如式（9）所示：

$ L=⌈\mathrm{l}\mathrm{b}\left({d}_{\mathrm{m}\mathrm{a}\mathrm{x}}\right)⌉ $

(9)

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

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

$ F=\frac{{\mu }_{b}\times {b}_{i, j}+{\mu }_{c}\times {C}_{i, j}}{{\mu }_{t}\times {T}_{i, j}+{\mu }_{d}\times {D}_{i, j}} $

(10)

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

步骤3  初始化种群。满足通信范围和截止日期约束的N个车辆节点组成初始种群$ X=\left\{{X}_{1}, {X}_{2}, \cdots , {X}_{N}\right\} $，在约束D维问题的解空间中第i个节点表示$ {X}_{i}=\left\{{x}_{i1}, {x}_{i2}, \cdots , {x}_{iD}\right\} $。初始种群确定以后，将种群N内的每个节点按照式（10）计算适度值并降序排序，且记录种群中适度值最小的节点为$ {X}_{g\_\mathrm{b}\mathrm{e}\mathrm{s}\mathrm{t}} $。

步骤4  子种群划分。初始种群划为J个子种群，并将第1个节点分配给子种群1，第2个节点分配给子种群2，第J个节点分配给子种群J，第J+1个节点分配给子种群1，以此类推直到每个子种群内包含I个节点，初始种群与子种群关系满足$ N=I\times J $。同时需记录子种群中适度值最小的节点$ {X}_{f\_\mathrm{b}\mathrm{e}\mathrm{s}\mathrm{t}} $和适度值最大节点$ {X}_{f\_\mathrm{w}\mathrm{o}\mathrm{r}\mathrm{s}\mathrm{t}} $。

步骤5  局部搜索。局部搜索仅对子种群内适度值最大的车辆节点$ {X}_{f\_\mathrm{w}\mathrm{o}\mathrm{r}\mathrm{s}\mathrm{t}} $进行进化更新策略，更新策略如式（11）和式（12）所示：

$ {R}_{i}=\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{d}\times \left({X}_{f\_\mathrm{w}\mathrm{o}\mathrm{r}\mathrm{s}\mathrm{t}}-{X}_{f\_\mathrm{b}\mathrm{e}\mathrm{s}\mathrm{t}}\right) $

(11)

$ {X}_{f\_\mathrm{w}\mathrm{o}\mathrm{r}\mathrm{s}\mathrm{t}}^{\text{'}}={R}_{i}+{X}_{f\_\mathrm{w}\mathrm{o}\mathrm{r}\mathrm{s}\mathrm{t}} $

(12)

其中：rand为0~1的随机小数；$ {R}_{i} $为移动步长，满足$ -{R}_{\mathrm{m}\mathrm{a}\mathrm{x}}\le {R}_{i}\le {R}_{\mathrm{m}\mathrm{a}\mathrm{x}} $约束，$ {R}_{\mathrm{m}\mathrm{a}\mathrm{x}} $为其移动最大步长；若$ {X}_{f\_\mathrm{w}\mathrm{o}\mathrm{r}\mathrm{s}\mathrm{t}}^{\text{'}} < {X}_{f\_\mathrm{w}\mathrm{o}\mathrm{r}\mathrm{s}\mathrm{t}} $，则用更新后的$ {X}_{f\_\mathrm{w}\mathrm{o}\mathrm{r}\mathrm{s}\mathrm{t}}^{\text{'}} $取代当前子种群最差节点$ {X}_{f\_\mathrm{w}\mathrm{o}\mathrm{r}\mathrm{s}\mathrm{t}} $，否则以概率pm动态进行变异更新。pm由SDN控制器依据当前网络状态下的带宽可用率、数据堆积率、车辆节点稳定性以及对应影响因子构成。更新策略如式（13）、式（14）和式（15）所示：

$ {R}_{i}=\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{d}\times \left({X}_{f\_\mathrm{w}\mathrm{o}\mathrm{r}\mathrm{s}\mathrm{t}}-{X}_{g\_\mathrm{b}\mathrm{e}\mathrm{s}\mathrm{t}}\right) $

(13)

$ {R}_{i}^{\text{'}}={R}_{i}+{R}_{i}\times pm $

(14)

$ {X}_{f\_\mathrm{w}\mathrm{o}\mathrm{r}\mathrm{s}\mathrm{t}}^{\text{'}}={R}_{i}^{\mathrm{\text{'}}}+{X}_{f\_\mathrm{w}\mathrm{o}\mathrm{r}\mathrm{s}\mathrm{t}} $

(15)

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

$ {X}_{f\_\mathrm{w}\mathrm{o}\mathrm{r}\mathrm{s}\mathrm{t}}^{\text{'}}={R}_{i}\times \left(\mathrm{m}\mathrm{a}\mathrm{x}-\mathrm{m}\mathrm{i}\mathrm{n}\right)+\mathrm{m}\mathrm{i}\mathrm{n} $

(16)

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

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

2.3 AH-SFLA实现

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

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

输入  网络拓扑，目的节点，QoS约束

输出  最优路径

1.根据约束条件确定车辆节点数量N

2.for i：= 0 to G do//G为迭代次数

3.节点基因进行编码→ Topology_code

4.update F //计算适度值F

5.divide（J）//划分J个子种群

6.$ \mathrm{q}\mathrm{s}\mathrm{o}\mathrm{r}\mathrm{t}\left(\mathrm{J}, {\mathrm{x}}_{\mathrm{i}}\right) $//降序排序

7.temp=$ {\mathrm{X}}_{\mathrm{f}\_\mathrm{w}\mathrm{o}\mathrm{r}\mathrm{s}\mathrm{t}} $//记录种群最差个体

8.for j：=0 to J do//局部搜索

9.根据式（11）和式（12）更新$ {\mathrm{X}}_{\mathrm{f}\_\mathrm{w}\mathrm{o}\mathrm{r}\mathrm{s}\mathrm{t}} $

10.if（$ {\mathrm{X}}_{\mathrm{f}\_\mathrm{w}\mathrm{o}\mathrm{r}\mathrm{s}\mathrm{t}}^{\mathrm{\text{'}}} $ < $ {\mathrm{X}}_{\mathrm{f}\_\mathrm{w}\mathrm{o}\mathrm{r}\mathrm{s}\mathrm{t}} $）then

11.$ {\mathrm{X}}_{\mathrm{f}\_\mathrm{w}\mathrm{o}\mathrm{r}\mathrm{s}\mathrm{t}} $=$ {\mathrm{X}}_{\mathrm{f}\_\mathrm{w}\mathrm{o}\mathrm{r}\mathrm{s}\mathrm{t}}^{\mathrm{\text{'}}} $

12.else根据式（13）、式（14）和式（15）更新$ {\mathrm{X}}_{\mathrm{f}\_\mathrm{w}\mathrm{o}\mathrm{r}\mathrm{s}\mathrm{t}} $

13.if（$ {\mathrm{X}}_{\mathrm{f}\_\mathrm{w}\mathrm{o}\mathrm{r}\mathrm{s}\mathrm{t}}^{\mathrm{\text{'}}} $ < $ {\mathrm{X}}_{\mathrm{f}\_\mathrm{w}\mathrm{o}\mathrm{r}\mathrm{s}\mathrm{t}} $）then

14.$ {\mathrm{X}}_{\mathrm{f}\_\mathrm{w}\mathrm{o}\mathrm{r}\mathrm{s}\mathrm{t}} $=$ {\mathrm{X}}_{\mathrm{f}\_\mathrm{w}\mathrm{o}\mathrm{r}\mathrm{s}\mathrm{t}}^{\mathrm{\text{'}}} $

15.else根据式（16）产生新的$ {\mathrm{X}}_{\mathrm{f}\_\mathrm{w}\mathrm{o}\mathrm{r}\mathrm{s}\mathrm{t}}^{\mathrm{\text{'}}} $

16.$ {\mathrm{X}}_{\mathrm{f}\_\mathrm{w}\mathrm{o}\mathrm{r}\mathrm{s}\mathrm{t}} $=$ {\mathrm{X}}_{\mathrm{f}\_\mathrm{w}\mathrm{o}\mathrm{r}\mathrm{s}\mathrm{t}}^{\mathrm{\text{'}}} $

17.end if

18.end if

19.end for

20.end for

21.mix（J）//混合子种群

22.$ \mathrm{q}\mathrm{s}\mathrm{o}\mathrm{r}\mathrm{t}\left(\mathrm{J}, {\mathrm{x}}_{\mathrm{i}}\right) $//新种群排序寻找适度值最小的$ {\mathrm{X}}_{\mathrm{g}\_\mathrm{b}\mathrm{e}\mathrm{s}\mathrm{t}} $

23.end

3 仿真实验与性能分析

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

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

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

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

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

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

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

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

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

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

图 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中因资源有限而出现的自私车辆进行分析研究，并结合演化博弈，设计有效的惩罚机制促使自私车辆转发数据包，降低协议的丢包率。