移动边缘计算环境下基于改进GPSR的VANET路由算法

陈 登，潘 力

(1.川北幼儿师范高等专科学校，四川 广元 628017; 2.郑州工程技术学院，郑州 450044)

0 引言

目前随着生活水平的日益提高，私家车车辆保有量的提升在一定程度上造成的交通拥堵和安全问题形势严峻，因此智能交通系统(ITS，intelligent transportation system)应运而生[1-2]。而车载自组织网络(VANET，vehicular ad-hoc network)作为ITS的核心部分[3]，在实现有效的路侧通信和数据传输过程中发挥着重要作用。

车辆网络是利用移动自组织网络(MANET，mobile ad hoc network)原理建立的，利用无线局域网(WLAN，wireless local area network)技术，通过车与车、车与设施之间实现多跳通信，在不同的距离上建立移动网络[4]。如果一个车辆离开定义的范围，则在网络中添加另一个节点或车辆以保持通信的有效性[5]。在MANET的帮助下，它在车对车(V2V，vehicle to vehicle)模式[6]和车对基础设施(V2I，vehicle to infrastructure)模式[7]过程中传输了多个数据。此外，VANET还改善了旅行时的道路安全，并提供视频、音频传输、电子邮件通信等多种服务。在数据传输过程中，VANET利用诸如Zigbee、WLAN、LTE、基于红外的通信等无线技术，成功地将数据、多跳信息、协同感知信息发送到不同的目的地，即使它们处于较远位置。由于VANET能有效地与车辆协同工作来提高通信质量，在道路数据通信过程中发挥着重要的作用[8]。但仍然面临着一些诸如安全性、数据认证、隐私、数据访问控制、数据机密性、数据不可否认性、数据完整性、网络可用性以及难以预测车辆位置等方面的挑战。此外，无基础设施的通信过程在通信时也会遇到拥塞问题。

针对上述挑战，学者们进行了一定的研究。例如，文献[8]提出了一种改进贪婪周边无状态路由(IGPSR，improved greedy perimeter stateless routing)的车联网路由算法，该算法根据节点的移动速度预测节点间的距离，并选取移动缓慢的、稳定的节点作为中继节点，以确保路由选择的可靠性，一定程度上提高了GPSR路由投递率低、传输时延大的问题。文献[9]开发了一个基于贪婪交通灯队列的路由协议系统，用于在城市环境中传输车辆数据，该系统在减少数据传输延迟的同时，有效地管理了业务负载。文献[10]介绍了用于在车辆自组织网络中传输数据的微生物启发单播路由协议(MIURP,microbial-inspired unicast routing protocol)，利用单播路由过程达到最小延迟和最大分组传输率的效果。文献[11]使用贪婪路由协议(GRP,greedy routing protocol)管理节点移动性和网络开销问题，该方法使用有助于最小化车辆定位误差的链路质量因子来检查节点之间的链路，应用卡尔曼滤波器检测链路质量，提高了车辆网络中数据传输的效率。文献[12]提出了用于管理车辆网络中存在偏差的流量感知路由协议(DFERP,deviation of flow-aware exist routing protocols)，该方法通过计算期望的连通度值来处理交通信息，根据收集的信息选择以最小延迟将信息成功传输到目的地的路由。文献[13]提出了一种新的自适应业务路由协议(ABRP,adaptive business routing protocol)，用于在车载网络中传输数据时管理路径、链路的可靠性，通过使用可靠性参数和启发式函数的自适应路由过程确保在VANET中成功的数据传输。

针对上述VANET路由算法中传输数据质量较低、且数据传输的吞吐量较小等问题，提出了移动边缘计算环境下，结合改进贪婪周边无状态路由(GPSR，greedy perimeter stateless routing)和自适应链路质量评估的VANET路由算法(IGPSR-MSD)。主要创新点总结如下：

1)将边缘计算架构应用于VANET能够有效缓解计算量大、与车辆有限且不均的资源分布之间的矛盾。

2)传统GPSR路由决定因素单一，存在易超过通信范围、造成链路不稳定的问题。为此，本文考虑了节点移动性，根据节点间距离来估计链路稳定性，实现链路的动态更新，提高链路质量。

3)为了提高传统GPSR的传送率，设计了一种链路传输速率估计方法。最后根据链路稳定性和和传输速率来选择合适的中继节点，提高网络稳定性和成功传送率。

通过SUMO仿真平台对路由算法的性能进行评估，结果表明所提算法受车辆密度、交通流以及车辆相对速度的影响较小，且提高了分组传送率，减少端到端延迟，降低了通信开销。

1 系统模型

VANET是城市交通道上的无线自组织网络，由围绕X*Y网络区域移动的N辆车组成，其通信模型如图1所示。网络中的车辆均装有GPS等无线通信设备，并利用RFID技术将数据传输至网络传输层进行分析和处理。在VANET中主要的通信模式有两种：车辆间通信和车辆到路边通信设施间的通信。其中，边缘计算资源层主要负责资源的优化分配过程与资源共享。例如，车辆间的V2V通信，安全告警类业务的传输可能需要多跳通信，但跳数的增加会引起时延增大，导致可靠性降低。当某一部分的业务实体出现资源短缺时，可以利用边缘服务协助计算、存储。因此，需要将不同车联网业务的需求映射为对通信接入方式和计算资源的选择，实现不同局部范围内车辆间的资源共享。

为不失一般性，本研究假设一共有L个路旁接入设施(RSU或公共WIFI)。同时，每一个路旁接入设施都配置相应的边缘服务器。

在VANET中，两辆车会被物理距离d隔开，因此通过使用专用短程通信和802.11标准定义的车辆环境中的无线接入通信技术进行连接。车辆在行驶过程中具有机动性，速度和方向均会发生改变。假设(xm,ym)和(xn,yn)是车辆m和n的位置坐标，则两者间的距离为[14]：

(1)

车辆m和n之间相对速度vs的估算公式为：

(2)

式中，vm和vn分别是车辆m和n的速度。

2 提出的VANET路由算法

VANET是通过多跳将数据从发送节点转发到目的节点，因此如何选择最优的下一跳节点来转发数据是路由算法设计的关键[15]。所提方法使用改进贪婪周边无状态路由(GPSR，greedy perimeter stateless routing)协议保证网络通信的稳健，并采用自适应链路质量评估提高通信效率。

2.1 问题描述

(3)

式中，▽φ是不成功的数据传播因子。如果链路不可用，则不进行传输。

使用目标车辆上信息接受失败情况来估计不成功传播因子，其为成功发送请求和失败发送请求的组合，其中失败请求根据链路故障和车辆节点移动进行计算。不成功传播因子[16]为：

(4)

式中，dv为目标车辆，qp为网络中的车辆m和dv之间路径p的链路质量。

其中链路质量qp表示两个车辆之间链路的最大可用性，表示为：

qp=(e-1)*Nn+(1-d)×Nnt

(5)

式中，(e-1)为m和dv之间路径车辆的数量。Nn和Nnt分别为确保lm,n=1而发送的信标消息数量，以及在时间t由车辆m生成的信标总数。对于进行V2V通信的车辆n与车辆m而言，车辆n的信噪比可表示为:

(6)

(7)

其中:Nρ为在车队中处于频段ρ的车辆数目。

路由算法的目标是最大化数据成功传输概率，并且保证最大数据传输量，获得更好的传输速率。

2.2 GPSR协议

GPSR路由协议将贪婪转发和边界转发相结合。节点直接根据节点自身、邻居节点和目的节点的位置信息制定数据转发策略。另外，节点通过周期性广播包含自身位置信息的Hello数据包，获取相邻节点的位置信息，从而更新邻居路由表。通常情况下，节点利用贪婪策略来选择下一跳节点，当局部最优现象发生时，启动周边转发策略选择下一跳转发节点[17]。

GPSR协议流程图如图2所示。

GPSR协议的优点在于：使用局部最优的贪婪算法，无需在节点中构建并动态更新路由表，路由开销较小；只要网络是连通的，便能获得可以传输数据的路由；采用与最短欧氏距离相近的路由，数据传输时延较小。

然而，VANET中车辆节点的移动较快，网络拓扑结构动态变化较大。节点的移动会使路由中下一跳会节点变化，需要重新调用路由算法。这就导致传统GPSR协议存在一些缺点，主要有：

1)GPSR协议中没有充分考虑节点的移动速度信息，可能会使用距离越远的节点。如果这个节点移动速度较快，易超出通信范围，导致路径有效时间将会很短。这不仅造成数据包在转发过程中丢失，降低服务质量，而且还会导致频繁调整路由，降低算法效率。

2)GPSR协议仅简单地根据距离信息确定路由策略，并未考虑链路的数据传输速率。传输速率受到交通道路拓扑中的静态和动态属性影响，如路段上的车流密度、方向等。

2.3 改进GPSR协议

结合VANET的网络特点，针对GPSR协议存在的问题，提出了基于节点移动速度(MS，moving speed)和节点间距离(ND，node distance)的改进GPSR协议(IGPSR-MSD)。根据节点移动速度和距离来估计消息传输速率和链路稳定性权重，从而选择出高链路质量且高消息传输率的最佳链路。

2.3.1 链路质量估计

由于GPSR路由协议没有考虑动态交通拓扑属性，可能产生错误或不可用的链路，因此需要对链路质量进行自适应评估，使用一个权重因子对链路节点进行修正。

假定节点最大通信范围R，且系数δ(0<δ<1)表示某个节点的通信能力。本文在拓扑结构中节点通信范围δR～R内，选取链路质量较高的节点作为中继节点。通常节点停留时间越长，表明节点移动速度越缓慢，则该节点越稳定[18]。

假定车辆k以速度vk移动，在间隔时间T内转发数据包，中继节点与转发节点j的相邻距离开始为ΔdTj，则下个时间间隔T+1内车辆k的移动距离为：

(8)

式中，at为车辆的加速度。转发节点与中继节点j间的距离Δd与车辆移动速度vk相关，计算公式为：

Δd=ΔdTj+(dj-dk)=

(9)

通过距离Δd来计算链路稳定性权重α(lm,n)，计算如下：

(10)

图3 中继节点选择过程

根据链路稳定性权重α(lm,n)可以将不可用的链路从列表中丢弃，以此精简局部最优解。如果两个或多个局部最优解相同时，则由其中最大值生成全局解。在传统的路由过程中，为了选择最优的相邻节点，需要估计与节点相关的度量。为了提高通信速率，选择通信范围内的最大节点数目以最大化带宽，有利于提高数据传输速率。

2.3.2 数据传输速率估计

假设两辆车之间的相对速度分布Δv为：

(11)

式中，μk和σk是消息发送节点的平均速度和标准偏差向量，ρRi是通信范围R内的邻居的密度，dmax为移动距离设定的最大值。

假定两节点的连接时间为Δt，那么链路lm,n中的消息传输成功的概率[19]为：

(12)

当消息传输成功概率满意一定条件时，进行消息传输。对于中继节点，如果lm,n=1，即两车在移动过程中，处于连通状态。

则中继节点与转发节点的消息传输速率Δmjk为：

(13)

从上式中可以看出，数据传输速率与节点的速度有关。

最后，可以根据链路稳定性权重α(lm,n)和数据传输速率来动态评估链路质量，从而选择出最佳中继节点的相邻节点。因此，可以克服传统GPSR协议中链路质量评估没有考虑到动态特性的问题。

3 实验结果与分析

仿真中的区域设置为5 km×5 km的区域内，包含最多400个车辆节点，车辆速度设置为20到100 km/h，通信半径为250 m。本仿真实验一共有10个(5+5)路旁接入设施，其中5个接入设施随车辆的移动而逐渐远离车辆。车载 CPU和MEC服务器性能均设置为1 GHz。MAC层协议为IEEE802.11，传输层协议为UDP，信标消息大小为512 Bytes，带宽为2 Mbps，数据包发送间隔时间为5 s。

路线图由交叉口和长车道组成，通过对车辆发送功率的标定来建立通信范围，并且为车辆确定适当的网络、传输层协议以及应用类型。将本文提出的IGPSR-MSD路由算法与现有的文献[10]提出的MIURP、文献[8]提出的IGPSR和文献[13]提出的ABRP算法进行比较。分别在不同的车辆密度、交通流和车辆移动速度情况下，从分组传送率、通信开销和端到端延迟等指标上进行对比分析。

3.1 车辆密度的影响

车辆密度将直接影响车载自适应网络性能。车辆密度的变化改善了网络连通性，也改善了干扰区域。仿真实验以65 km/h的速度分析车辆密度对分组传送率[20]、丢包率[21]以及通信开销[22]的影响。其中设置车辆数量为30到400之间不等。

3.1.1 分组传送率

将所提算法的分组传送率与现有算法进行对比，结果如图4所示。车辆密度增加，高度集中导致暂停或者慢速通信。所提算法中通过估计Δmjk优化数据速率，根据Δv和Δd选择最优的中继节点，并且验证α(lm,n)，选择一条稳健的链路以确保传送率最大。

图4 车辆数量与分组传送率

从图4中可看出，相比于其他算法，所提出的IGPSR-MSD算法的分组传送率最高，并且随着车辆的增加，该值也逐渐增大。文献[13]中考虑了静态和动态的道路信息，但未充分链路质量的影响，因此分组传送率较低。文献[8]根据节点的移动速度预测节点间的距离，但对中继节点的选择标准太过宽泛，分组传送率有待提高。文献[10]仅考虑车辆速度和位置等因素的影响，但对于道路信息等未进行动态更新，因此分组传送率较低。

此外，将所提算法的丢包率与现有算法进行对比，结果如表1所示。由于最优的中继节点选择，IGPSR-MSD中节点间重新连接和路由链路错误的数量较少，并且自适应链路质量评估确保了可靠链路，提高了成功的分组传送，降低了丢包率。

表1 车辆数量与丢包率(100%)

3.1.2 通信开销

车辆数量的增加导致控制信息交换的速率增加，其中路由请求和响应确认的总数用于估计通信开销。将所提算法的通信开销与现有算法进行对比，结果如图5所示。在提出的IGPSR-MSD算法中，车辆的状态经过初步分类，车辆距离和链路权重α(lm,n)共同决定数据转发时的中继节点选择，以实现较少的控制消息。

图5 车辆数量与通信开销

从图5中可看出，所提出的IGPSR-MSD算法的通信开销最小，尤其随着车辆数量的增加，该优势越明显，由于其选择最优的中继节点，无需传送大量的控制信息。文献[13]中由于考虑道路信息的静态和动态信息，且缺乏高效的传输策略，因此通信开销较多。文献[8]利用IGPSR完成VANET路由，其中根据移动节点实时预测车辆，且选择中继节点，对通信的要求较高，开销也较高。文献[10] 通过使用可靠性参数和启发式函数的自适应路由过程确保在VANET中成功的数据传输，动态调整路径，因此通信开销相比文献[8]和文献[10]有所降低。

3.2 交通流的影响

评估交通流量对所提出算法和现有算法在端到端延迟和分组传送率等方面的影响。不同的流量会增加网络拥堵的可能性，从而影响车辆的速度和数据的传输速录。实验中设置交流流量为1到6不等，其中1代表各个路口基准交通流量，设置为15辆/分钟。

3.2.1 端到端延迟

交通流的增加导致通信过程中的分组传送时间延长。将所提算法的端到端延迟与现有算法进行对比，结果如图6所示。所提出的IGPSR-MSD算法中，通过基于移动方向选择速度和距离较小的节点来保证链路的可用性。基于距离和最优的δc的节点选择提高了链路的稳定性，qp保证了传输质量，防止了响应时间的延长。因此，与现有算法相比，IGPSR-MSD具有更少的延迟。

图6 交通流与端到端延迟

从图6中可看出，相比于现有算法，所提出的IGPSR-MSD算法的端到端延迟时间是最小的，虽然随着交通流的增加，其延迟时间也会上升，但上升幅度明显比现有方法缓。尤其是文献[8]和文献[10]由于缺乏高效的分流策略，无法快速获得可靠的链路，其端到端延迟时间长，且随着交通流的增加快速上升。文献[13]利用ABRP算法自适应调整传输路径，端对端延迟较小。

3.2.2 分组传送率

交通流对所提算法与现有算法的分组传送率的影响如图7所示。所提出的IGPSR-MSD算法通过在通信时qp和Δd选择可靠的链路来处理通信量。对于不同的车辆密度和速度，在任何时刻设置链路，通过在通信路径中选择适当的车辆，最大化Δmjk，以实现更高的分组传送率。

图7 交通流与分组传送率

从图7中可看出，所提算法的分组传送率是最高的，但随着交通流的增加，由于传送时间延长，分组传送率逐渐降低，但下降幅度在高交通流时较小。边缘计算层的引入使得车联网环境中的车辆间的资源优化调度策略变得更加灵活，进行通信、计算资源的合理分配，实现不同局部范围内实体间的资源高效利用。文献[8]根据节点的移动速度预测节点间的距离，并且选择运动缓慢的节点作为中继节点，一旦交通流增大，大部分节点运动缓慢，均可作为中继节点，加快数据传送，因此当交通流为5时有一个短暂的上升，但是节点数量有限，因此分组传送率会再次降低。文献[13]由于具有适用于较高交通流的路由协议，因此在交通流为4时有短暂的上升。文献[10]利用单播路由过程，当交通流增大时，其数据传输压力较大，因此分组传送率持续降低。

3.3 车辆相对速度的影响

车辆速度的变化会导致频繁的链路变化和路由更新，如果仅路由过程是周期性变化的，lm,n=1能够处理车辆速度的干扰而不影响网络性能。车辆相对速度对所提算法与现有算法性能的影响如图8所示。所提出的IGPSR-MSD算法中，由于路由过程中通过分析有利的传输条件以确定最优的中继节点，并且所需的信标信息最少，从而确保了链路的可用性。

图8 车辆相对速度与信标信息

所提出的IGPSR-MSD算法所需的信标信息最少，这是因为算法中考虑了车辆相对速度分布Δv，并且优化链路选择，因此对信标信息的依赖性较低。文献[10]由于较依赖车辆速度和位置的信息，因此其信标信息较多。文献[8]需要选择中继节点，对信标数量有一定的要求，随着车辆相对速度越大，节点间距离越大，为了保证通信质量，对信标数量的需求也会提高。而文献[13]中较多依靠静态和动态道路信息，因此需要的信标信息较少。

4 结束语

为了提高VANET中的数据传输速率，所提出的移动边缘计算环境下的IGPSR-MSD算法，结合了GPSR协议和自适应链路质量评估，通过链路稳定性权重和链路传输速率来选择最优的中继节点，确保链路的可靠性，完成高效的数据传输。IGPSR-MSD协议通过对车辆的通信范围和位置、速度信息保持较好的链路稳定性，针对路由协议中可能出现的路径错误，引入了自适应链路质量评估，简化了中继节点与转发节点的数据流和传输流。实验结果验证了车辆密度、车辆流和车辆相对速度对所提算法的影响较小，并且分组传送率较高、端到端延迟较短且通信开销较小，链路选择时对信标信息依赖程度不高。因此，所提算法能够在众多干扰下保持可靠的数据传输，适用于实际的车载网络环境。

然而，所提方法中未考虑车辆方向突然改变这一因素的影响，并且实际道路信息复杂，目前考虑的因素有所欠缺。因此，后期将进一步完善VANET路由算法影响因素的分析并进行算法优化。