基于边缘计算的分簇AODV 路由新算法

张德干，龚倡乐，张 婷，张 捷，李 霞

（1a.天津理工大学天津市智能计算及软件新技术重点实验室；1b.计算机视觉与系统省部共建教育部重点实验室，天津300384；2.北京交通大学电子信息工程学院，北京100044）

对于传统的车辆技术而言，在车联网中，现代通 信与网络技术的融合显得格外的重要，车联网环境下智能汽车的使用给智能交通带来了很大便利［1-5］.但是车辆数量大、分布广，如果将所有的服务计算都放置于云端进行，会消耗大量的计算资源.短程通信 技 术（Dedicated Short-Range Communication，DSRC）有两种通信形式，即车-路通信（Vehicle to Road，V2R）以及车-车 通 信（Vehicle to Vehicle，V2V）［6-8］.在DSRC 的体系结构中，每辆车上备有车载设备（On-Board Unit，OBU），相当于移动终端设备，具有一定的数据处理能力，同时，在马路上还部署了相应的路边单元RSU，为车辆提供数据访问服务［9-11］.由于车辆节点的高速移动，节点之间的连接具有不稳定性［12-15］.这些特征给车辆自组网的设计带来了很多的挑战，其中路由协议的设计对于VANETs 中数据的高效传输至关重要.

按需驱动路由协议具有无中心、自组织、多跳路由以及动态路由的特点，协议要求仅当在有通信需求的情况下，才进行路由的建立，而不需要对所有的节点进行维护，因此间接增加了网络的寿命.按需驱动路由协议可以更便捷地达到移动自组织网中关于动态、带宽、消耗等约束条件，是路由协议未来的发展的方向［16-21］.典型的按需路由协议有AODV、DSR、TORA 等.

移动边缘计算（Mobile Edge Computing，MEC）主要用于解决讲任务迁移到位于核心网络的云导致的资源带宽消耗的增大以及带来的额外的网络延迟［22-28］.将MEC 与车联网相结合，能提供具备本地特色的高质量的服务.

考虑到单纯地使用V2R 或者V2V 模式进行车载通信时，会产生大量的资源消耗.因此，本文作者提出一种基于边缘计算的分簇（Ad hoc On-demand Distance Vector，AODV）路由协议（AODV-MEC）.

1 基本原理

1.1 道路模型

引理1［23］：依据模型的设定以及所有车辆沿道路匀速行驶，车辆在道路上的分布情况依照泊松分布，每个车辆都是相互独立.可以实现V2R 以及V2V 的通信技术.MEC 与车联网结合示意图如图1 所示.

图1 MEC 与车联网结合示意图Fig.1 Schematic diagram of combination of MEC and vehicle networking

考虑一条双向通行道路，总长度为LROAD，车辆密度为ρ，且车辆的数目满足泊松分布.沿路设有路边设备RSU，根据802.11p 协议所支持的最大传输距离，考虑天线发射功率的限制，相邻的RSU 之间的距离为LRSU∈[100，600]（单位：m）.RSU 提供在范围内的无线通信，将其无线通信范围设置为LRSU2.综上，整条道路可以被看作分成了为LROADLRSU段.根据V2V 通信模式，任意两辆车都是可以进行相互通信的.同时根据V2R 的通信模式，给定范围内的车辆只能与对应段中的RSU 进行通信.

每个路边设备RSU 都配置有MEC 服务器，具有MEC 节点的能力，且每个MEC 服务器只能够和对应的RSU 通信，因此范围段内的RSU 和MEC 是一一对应的，RSU 和RSU 之间以LRSU2 通信范围进行通信.带有边缘服务器的车辆网络体系结构如图2 所示.

图2 道路模型示意图Fig.2 Schematic diagram of road model

1.2 车载通信路由协议

在AODV 路由协议中，对3 种消息类型进行了定义，即路由请求RREQ、路由回复RREP 以及路由错误RRER.在路由发现的阶段，当在源节点发送数据包或者转发数据包到目的节点时，会对路由表进行查询.如果在路由表中没有找到对应的路由表项，则会广播一个路由请求分组RREQ，收到路由请求的中间节点会根据所收到的RREQ 信息来建立一个反向路由，其目的节点是发送该RREQ 的源节点，同时继续广播该分组.当目的节点收到RREQ后，会沿着之前所建立的反向路由回复路由应答RREP 到源节点.收到RREP 的中间节点再建立到目的节点的正向路由，当源节点收到RREP 后，表明路由已经找到，即可开始发送数据［22］.路由发现示意图见图3.

图3 路由发现示意图Fig.3 Route discovery schematic

但是在车载网络的环境下，由于道路上车辆的密度大，移动速度快，因此网络拓扑结构变化比较快，导致通信链路的断裂是很频繁的，所以传统的AODV 路由协议并不能很好地适用于车载网络，因此，找到一个稳定的链路是很有必要的.

1.3 道路节点分簇

在给定的车辆模型中，车辆始终行进，不会滞留在同一个簇区当中，必然涉及了进出簇区.因此本文主要结合了动态分簇的方法，在保持每个簇区簇头节点不变，簇内节点改变的情况下，对给定的车辆模型进行动态分簇，用于优化整个路由协议的通信.对做出如下的定义：

定义1 边缘超级节点（RSU-MEC）

将满足以下几个要求的节点定义为边缘超级节点：节点位于源头的边缘处；不具备移动性；具备通信能力以及信息处理能力；具有充足的能量维持工作.

在给定的道路模型中，每LRSU距离都会设置一个路边设备RSU，并且路边设备都配置一个边缘服务器.根据所给定的边缘超级节点的定义，RSUMEC 在道路上是固定的，同时具有稳定的能量输入，可以对路由信息进行处理，因此将其看作是边缘超级节点，每个边缘超级节点为一个簇头.以RSU通信范围进行划分，可以得到LROADLRSU个簇头，并自动的划分成LROADLRSU个簇区，相邻的RSUMEC 可以通过边缘超级节点进行相互通信，即邻近的簇区可以双向进行通信.

1.4 车辆节点相关定义

定义2 因为车辆自身都带有GPS 技术，便于对车辆所在位置信息及速度信息进行获取，因此对车辆运动方向定义（假设车辆a在tn时刻的速度为Va(tn)）：Va(tn)＞0，节点朝着正向运动；Va(tn)＜0节点朝着负向运动.

每个节点都能够捕捉到附近节点的移动状况，在时间tn，车辆a记录自己相对位置Pa(tn)，从而可以得到当前时刻节点运动的速度和方向

根据Va(tn)的正负，即可判断节点运动的轨迹.

定义3 车辆a与b的相对速度

由于节点做匀速运动，此时平均速度与瞬时速度相等.每个节点在广播的同时，会把自身的位置速度信息进行广播.b为相邻的车辆.因此当车辆节点a收到相邻车辆节点b发送的请求时会相对速度，并且记录在路由表中.

定义4 车辆链路保持时间

假设车辆节点的通信范围为LCAR，在完成对于车辆节点的相对速度的估计之后，将对车辆间建立的链路的有效保持的持续时间进行计算，记为TCAR.

式中：Lab为在建立链接时车辆节点a与车辆节点b的初始距离，通过欧式距离进行计算：

1.5 节点能量消耗

一条链路所有节点能量的总消耗需要作为整个路由路径能量的考虑.计算如下

式中：num为每条路径的车辆节点总数；C表示一个任意的常数；Cost(a)表示为车辆节点a的能量消耗，可以通过无线传感网络节点能耗ET(l，d)和ER(l，d)表示，即发送和接受数据时的能量消耗，计算如下

根据无线电能量消耗模型，每发送lbit 的数据，节点的能耗如下

同时，节点接收l消息的能耗计算公式为

1.6 连通概率

引理2［24］：车辆密度：在给定路段上，一个车道或一个方向上某一瞬时的车辆数.用以表示在一条道路上车辆的密集程度.

在给定的道路中，两个车辆节点如果处于彼此的通信范围内，他们可以直接通信.但是由于车流密度比较稀疏的情况下，下一跳通信范围内不一定有车辆，即可能造成连通中断.

定义5 连通概率（P）：在规定的路段中，车辆节点间通信链路连通并且可以正常进行通信功能的概率.

定义6 断开概率：当链路保持时间超出规定的阈值后，车辆节点间的通信链路将会断开，断开概率即链路保持时间低于阈值的概率.

在每个RSU-MEC 的通信范围内，只考虑V2V通信模式的前提下，由于车辆的快速运动，导致拓扑变化频繁，以车辆的通信半径LCAR划分，可以得到每个簇区单元格个数为

如图2 所示，结合式（3），节点会优先选择方向相同的进行链路连接，当处于同一个运动方向的链路无法建立时，车辆节点可以向对立方向的车辆发起通信连接的请求，以此来增加车辆连通的概率.两条道路上运动的车辆可建立连接的概率密度函数如下

式中：re与rw代表车道的双向；ρe与ρw代表双向车道的车流量密度.在以正方向为主运动方向进行通信时，负方向上的车辆由于车辆链路保持时间较短，因此将其作为备选链路.用Pal来表示负方向道路上可建立连接的车流量密度为0 而造成无连通链路率，其计算公式为

根据式（11）可以得到，车辆节点间存在链路率为1-Pal，考虑到一个车辆节点可能存在多个邻居车辆节点进行链路连接，设为h，因此可得邻居车辆节点间存在链路率为

另外，考虑到链路保持时间，当链路保持时间低于最低链路保持时间阈值TBRE时，通信链路也会断开，因此可以得到链路断开的概率为

对于有N-1 跳通信链路来说，链路是否断开的情况满足二项分布，得到h条断开链路的概率为

综上，根据全概率公式可以得到，在给定的车辆模型下，车辆节点间的连通概率为

2 通信方式的选择

2.1 簇区内通信

如图4 所示，当车辆a与b处于同一个边缘超级节点的簇区内通信时（Cluster_inside），边缘服务器需要同时接收以及发送同一个簇区的节点通信请求，容易造成信息的拥塞且加大边缘服务器的能耗，因此选择通过V2V 模式，即车辆与车辆间的模式直接进行通信.

图4 簇区内通信示意图Fig.4 Schematic diagram of intra-cluster communication

当使用V2V 模式进行通信的时候，本文主要使用的是按需路由协议中的AODV 路由协议，并通过使用Q-Learning 算法，对中间节点的选择进行优化.

引理3［25］：在强化学习算法中，Q-Learning 是其中最为重要的算法之一.S为给定的状态空间，A为给定的动作集合，在t时刻的st状态下（stϵS）采取动作at(at∈A)，同时根据动作反馈相应的奖励R，即为Q(s，a).Q-Learning 采用状态-动作迭代的方式来得到最优策略，因此可以得到函数Q 更新的公式如下

式 中：α为 学 习 率，α越 大，Q 值 收 敛 越 快；maxaQ(st+1，a)指的是从动作集合A中选择使得Q(st+1，a)取值最大的动作；γ在这里为折扣因子，γ∈[0，1]，接近1 时指的是函数考虑将来回报，反之则是考虑即刻回报.

考虑到Q-Learning 中，Q 值的确定和奖励R的计算有着十分重要的关系，因此在奖惩函数的选择上，本文对传统的AODV 路由协议，综合考虑跳数HOP、车辆与邻居车辆节点间的链路保持时间T，以及能量消耗ENG，相结合生成

在默认情况下，可以根据节点间的距离进行获取相应的跳数.使用均衡的权值来选取适应度，即跳数、车辆与邻居车辆节点间的链路保持时间和能量消耗三者的权重相同，认为w1=w2=w3=1 3.当R(s，a)的值越大，则说明奖励值越高，得到的Q 值也就越高.在V2V 通信模式下，由AODV 路由算法并结合Q-Learning 算法，在此过程中，中间车辆节点对于下一跳节点的选择，会依照自身状态，按照式（17），依据跳数、车辆连通概率以及自身能量的消耗，反复计算不同下一跳节点的奖励函数R，并结合式（16）更新Q 值直到选出最佳的节点，从而优化中间节点的选择.最终目的车辆节点收到请求，并沿着建立的反向路由应答到源车辆节点，最终完成路由链路的建立.

2.2 簇区间通信

假设源车辆节点位于P1簇区，目的车辆节点位于Pn簇区，如果使用V2V 模式进行通信，会导致中间车辆节点过多，在传输过程中，过多的中间车辆节点存在大量的不稳定因素导致链路的失效，如车辆间的距离过大导致链路断开，会使网络拓扑进行重新建立，因此会浪费大量的资源.为避免V2V 模式带来的问题，当车辆节点在簇区间进行通信时，采用V2R 模式，即车辆与道路的模式进行通信.

当源节点车辆发出通信请求后，RSU-MEC 会接收到该通信请求，在自身维护的路由表中查找目的车辆节点是否在路由表内，如果不在，则向附近的RSU 发起请求，此时会出现两种情况：

1）非相邻簇区通信(Cluster_away).

如图5 所示，假设目的车辆节点位于源车辆节点的非相邻簇区，此时采用V2R 模式进行通信.当源车辆节点发出路由请求到该簇区的RSU-MEC后，查看到目的节点并不在当前簇区内，向RSUMEC 发起请求，接收到请求的RSU-MEC 检查目的车辆节点是否在自身路由表中，在找到对应节点后，建立连接.

图5 非相邻簇区通信示意图Fig.5 Schematic diagram of non-adjacent cluster communication

2）相邻簇区通信(Cluster_neighbor).

如图6 所示，假设目的车辆节点位于P2簇区，相邻于P1簇区，此时两个簇区处于相邻的状态.

图6 相邻簇区通信示意图Fig.6 Schematic diagram of adjacent cluster communication

由于相邻簇区的特殊性，由于通信请求从车辆到RSU-MEC 存在时延，如果在相邻簇区通信时，全部使用V2R 的通信模式进行通信，过多的通信请求会导致信息的拥塞，增大服务器的压力，其资源的消耗以及传输时延有可能大于V2V 模式的消耗，车辆与RSU-MEC 之间的链路也有可能因为车速的原因导致链路的断开.

另一方面，如果使用V2V 通信模式进行通信，当车辆在两个簇区间进行通信时，有可能出现下一跳节点中不存在节点的概率，即下一个单元格内的车辆数量为0.在这种概率的情况下，车辆间通信需要等待到下一跳车辆链路的连通，因此对于链路连通概率有影响，且时延也有所增加.

因此对于相邻簇区间的通信，在考虑到概率不确定性的前提下，需要综合考虑V2R 与V2V 通信模式相结合的方法进行通信，从而降低链路断开的风险.

在V2R 的模式下，源车辆节点与P1簇区RSUMEC 之间的通信距离以及目的车辆节点与P2簇区RSU-MEC 之间的距离可以通过式（4）计算欧式距离LCTR，簇区之间的距离为LROAD，再通过式（6）计算出能量的消耗.由于RSU-MEC 是静止的，所以不存在相对速度的计算.

另外，根据图7，处于簇区P1 的车辆从A点沿着正方向运动，当运动到C点时即将离开P1 簇区边缘超级节点的通信范围，在规定的簇区内，车辆与RSU-MEC 间能维持的最大通信时间为TCTR，即链路保持时间可以计算出来.

图7 RSU-车辆链路保持时间示意图Fig.7 RSU-vehicle link hold time schematic

图8 车辆通信流程图Fig.8 Flow chart of vehicle communication

3）节点位置的确定.

根据已经划分好的簇区，当簇区P的RSUMEC 收到车辆节点发出通信请求后，首先在查找目的车辆节点是否位于本簇区，如果不在当前簇区，则向相邻的边缘超级节点发出请求，以此来确定目的车辆节点所处的位置.

4）通信方式选择及路由建立.

①如果节点处于同一个簇区，采用簇区内的通信方式，采用V2V 的通信模式.根据通过优化后的AODV 路由协议.

通过式（2）计算出车辆自身与邻居车辆节点的相对速度，在按照式（3），即出预测出自身与附近邻居车辆节点在建立链路后的车辆链路保持时间.根据式（5）～式（8）可以得到节点能量消耗，综合然后综合判断链路保持时间，节点能量消耗以及跳数，根据式（17）的奖励函数，使用Q-Learning 算法对于中间节点的选择以及通信的路径进行优化，从而建立一条通信链路进行通信，建立路由.

②如果节点处于相邻簇区，采用相邻簇区的通信方式.

结合概率不确定性，在V2V 以及V2R 通信模式的选择上，根据式（2）和式（3）可以预测出在V2V模式下车辆间的链路保持时间.再通过式（9）～式（15）可以得到V2V 模式下车辆链路连通概率.

③如果节点处于非相邻簇区，采用非相邻簇区的通信方式.使用V2R 通信模式，源车辆节点与该簇区的RSU-MEC 进行通信，中间RSU-MEC 相互进行通信，然后目的节点所在簇区的RSU-MEC 与目的车辆节点进行通信.其中，源车辆节点与RSUMEC 以及目的车辆节点与RSU-MEC 的链路长度可通过式（4）来进行获取.

3 算法测试与分析

3.1 测试仿真环境设置

本实验使用Matlab 平台，对设置的算法AODV-MEC 进行测试.将其和传统的AODV 路由协议，DSR 路由协议，GA-BFODSR 路由协议以及AODV-EO 路由协议进行对比.针对车辆节点在不同的行驶速度，不同的数据包发送速率，不同的车辆节点数目的情况下，对车辆节点之间的数据包分组交付率，节点间的平均端到端时延以及在整个路由过程中的拓扑开销控制进行分析.仿真参数设置为：节点分布范围2 000（m）×50（m）；节点个数200 辆；节点初始能量为1 J；车辆通信半径为100 m；RSU-MEC 通信半径为220 m；节点最大移动速度Vmax=40 km/h；最大数据包发送速率Smax=20 个/s；数据包长度为2 000 Bit；电路能耗系数为5.0×10-8J/bit；信道传播模型能耗系数为Efs：1.0×10-11J/（bit·m-2）；Em：1.3×10-15J/（bit·m-4）；φ1=φ2=φ3=1/3；w1=w2=w3=1/3；学习率α=0.8；折扣因子γ=0.2.

3.2 实验结果分析

图9 是在给定的道路模型上，在车辆稳定行驶时，数据包发送速率不同的情况下，给定的5 种路由算法的网络性能.每个车辆进行匀速运动且方向不变，数据包发送的速率规定在4～20 个/s 的范围之间，并且数据包的大小固定为2 000 Bit.

如图9（a）所示，在车辆匀速稳定且运动方向不变的情况下，随着数据包发送率的增加，5 种协议的分组投递率都有着下降的趋势.这主要的原因在于，数据包发送量不断扩大的同时，将会导致在整个网络中的数据量的增加，即可能产生网络拥堵的情况.在整个仿真实验过程中，本文所提出的AODVMEC 的路由新算法，分组投递率整体下降了约2.7%，相比于其他几种算法，数据包递交率比较高.当数据包发送率达到最大值时，相比于DSR 算法提高了2%.

图9（b）呈现的是不同数据包发送率情况下，平均端到端时延所受到的影响，可以明显看出，随着发送率的提高，5 种算法的平均端到端时延都有所增加，其中DSR 路由算法增加的最明显. 由于AODV，DSR 路由都是按需路由协议，即仅当节点发出路由请求时，才开始寻找路由.此外，由于车辆一直处于运动状态，且不同方向运动的车辆在通信范围内有建立链接的可能，考虑到DSR 路由算法的路由方式，所建立的链路出现断开的可能性更大，所以有需要使用一定量的数据包对断掉的路由进行维护，造成了端到端时延的缓慢递增.AODV-MEC 在进行路由建立的过程中，结合传统的AODV 路由算法的逐跳路由建立方式，添加了对于链路维持时间的考虑，舍弃了部分不稳定的链路，使得平均端到端时延有所提高.在数据包发送率最大时，AODVMEC 算法比DSR 算法的平均端到端时延低10%，比传统的AODV 算法低大约3%，比AODV-EO 算法高1%，比GA-BFODSR 算法低大约1.9%.

图9 不同数据包发送率下的测量指标Fig.9 Measurement indicators under different packet transmission rates

图9（c）显示了在网络拓扑控制开销随着数据包发送速率的增大，总体有着下降的趋势.原因在于车辆运行速度相对稳定，因此网络拓扑结构的变化差异并不大，然而在数据包发送速率增大的情况下，维护网络拓扑的信息所占比例有所减少，所以整体呈现下降的趋势.相比于最小数据包发送率时的拓扑控制开销，AODV-MEC 算法在到达最大数据包发送率时开销下降约29.3%，效率高于其他4 种算法.

3.3 场景测试

场景设置在车流量密度大的高速公路上，如图10 所示，有6 条主干道，其中A，D 超车道，最低时速为每小时110 km，B，E 为行车道，最低车速为每小时90 km，C，F 为减速车道，速度在50 km/h 内，每隔500 m 设置一个RSU-MEC 设备.

图10 双向3 车道高速路Fig.10 Two-way 3-lane expressway

在该场景中，RSU-MEC 与车辆，车辆与车辆间可以进行相互通信，并且存在出现超车变道的情况.在车流量密度不同的情况下，节点间的网络拓扑控制开销如图11 所示.

图11 不同车流量密度网络拓扑控制开销Fig.11 Network topology control overhead with different traffic flow densities

由图11 可知，随着车流量的增大，网络拓扑控制开销均呈下降趋势，且逐渐平缓.这是因为，在车流量较小的情况下，车辆节点间不容易建立稳定可靠稳定链路，因此在网络拓扑控制开销上有所增加，在车流量增大后，网络拓扑情况相对有所好转，因此在控制开销上有所改善，在车流量趋于饱和时，网络拓扑控制开销优化率相比于低车流量时期变缓.在车辆数量到达最大时，AODV-MEC 算法的拓扑控制开销减小约27%，比DSR 算法低约2.7%，比AODV 算法低约2.5%，比AODV-EO 低大约1.3%.

综上，本文所提出的AODV-MEC 路由协议由于综合了V2V 以及V2R 的通信模式，通过结合车辆节点间的能量消耗，链路保持时间以及车辆节点与RSU-MEC 的链路保持时间，总体上在分组投递率，网络拓扑控制开销以及平均端到端时延上较优于其他四种路由协议.

4 结论

1）提出了基于边缘计算的分簇AODV 路由算法，作为一种按需路由协议，与传统的AODV 路由协议相比较，本算法不仅是以最小跳数作为条件来进行最佳路径的选择，而是综合考虑了车辆移动速度，车辆节点能量信息以及预计链路保持时间，以此作为适应度函数来进行路由的选择.

2）结合V2V 与V2R 的通信模式，使用分簇的方式，在路边设备RSU 上部署边缘服务器，以此来提高路由寻找的效率，从而减少了平均端到端时延及网络拓扑控制开销.实验结果表明，该方法确实对网络综合效率有较大的提高.