基于边缘计算的车联网中数据回传新方法

2021-12-23张德干曹利香赵彭真

北京交通大学学报 2021年5期

张德干，曹利香，张婷，赵彭真，张捷

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

在万物互联的背景下，车联网逐渐进入人们的视野.随着车联网的快速发展，车辆数目的增加，海量的数据产生将会导致本地的计算和存储资源不能有效及时的满足需求，基于云计算来解决这些问题会产生大量的时延和一些高额的消耗.边缘计算被视为上述问题的有效解决方法，边缘计算通过将原有的云计算模型的部分计算和存储能力迁移到网络的边缘设备，满足现在计算密集的需求[1-8].

5G技术的发展使得人们对车联网提出了更高的要求，信息传输的高可靠低时延是研究的热点[9-16].其中，数据的传输主要围绕着车、边缘服务器节点、RSU(Road side Unit)路边单元进行传输，通过V2V(Vehicle-to-Vehicle)模式和V2I(Vehicle-to-Vehicle)模式进行信息的交换，V2V和V2I两种模式相互协作提高数据传输的可靠性[17-20].目前的车辆网中，车辆在行驶过程中对数据的处理主要有两种方式：1)少量的数据在本地进行计算.2)卸载到边缘服务器上进行计算.统计发现在实际的情况中经常出现的场景是：任务传输一个车辆或者是多个车辆所处环境的多种类型的数据，任务回传的数据往往是上传消息综合处理后的一条指令信息.消息传递的过程中伴随着车辆的移动和车辆的密度的变化，以及可能出现在RSU覆盖范围之外的区域，这些都将导致网路的拓扑频繁变化，使得节点间的通信不可靠[21-27].

目前，相关的研究人员已经对边缘服务器与车辆进行计算反馈的传输方式进行研究[28-34].当某一区域是在RSU(Road-Sides Unit)覆盖下的时候，在这样的场景下，车辆在获取回传信息的时候有多种方式，既可以通过V2V的方式借助中继车辆完成多跳传输，也可以通过V2I的方式从RSU接受回传数据.Li等[35]提出了一种基于车联网边缘计算时延可容忍的数据传输优化方案，通过观测马尔科夫决策过程，优化网络的开销，缩短数据的计算处理时间.Khabbaz等[36]提出了一种针对车辆网中时延敏感的数据传输策略，以距离等指标作为择优的标准，在RSU未覆盖的区域中选择最优距离车辆作为中继节点进行数据的转发.文献[37]对V2V和V2I两种方式进行了对比，V2V的传输方式较具广泛性，只要在车辆的通信范围内有其他的车辆便可以进行数据的交互，但是由于在实际的场景中大部分的车辆是处于移动的状态，在实际的高速复杂的移动的环境中，V2V的传输的稳定性会差一点，通信链路的有效时间也较短，并且车辆的功耗相较有限.V2I方式的传输往往会局限于RSU的覆盖范围，在特定的范围内，数据传输较为可靠并且数据的传输速率更高.文献[38]提出了一种协同通信策略，以提高车辆网络的容量，尤其是在VoI比例较低的情况下效果较好.

本文作者在车联网边缘计算的框架下，对边缘服务器消息的回传下发方式进行研究，在不同的场景切换V2V、V2I以及混合方式进行消息的回传，综合考虑车辆的运动以及RSU的覆盖情况等因素，以链路的寿命和质量以及消息的传播时延作为可靠性传输的标准.

1 系统模型

图1 车联网边缘计算模型Fig.1 Edge computing model in Internet of Vehicles

本文考虑了一种车联网与边缘计算结合的环境，如图1所示.边缘层在靠近用户的位置提供一定的计算存储能力，主要是在路边单元或者是基站上部署边缘服务器.底层的用户层主要由车辆构成，车辆装有GPS可以实时感知其他车辆以及路边单元的位置，并且装有车载传感器可以感知周围的环境.底层的车辆可以通过移动通信技术和车载通信协议与周边的车辆和路侧基础设施直接通信传递数据.

1.1 道路和车辆区域

为了简化模型，本文考虑道路上存在两个对向的车道的场景，一条由西向东另一条由东向西，前者称其为A车道(正向)，后者为B车道(反向).在道路内，假设有N_vehicle个车辆随机的分布在道路上，车道A的车速为va，车道B的车速为vb.车辆的密度为ρ.在该区域中，随机分布了N_RSU个路边单元，同时，所有的RSU均配备了具有一定计算和存储能力的边缘服务器，对于大多数的计算场景，需要车辆将计算任务卸载到RSU上进行计算.

1.2 计算区域

车辆在行驶过程中有计算需求时，通常会采取任务卸载.计算需求可以分类为本地计算和需卸载到RSU上进行的计算，本文重点研究需要车辆将计算任务卸载到RSU上进行计算的场景.本文默认卸载到边缘服务器上的待计算的数据大于计算后输出的数据，假设卸载任务的数量大小为Ctask，上行数据的总带宽为Bup，完成某个计算任务需要的资源为M，服务器的计算速度为SMEC，则从卸载到任务完成的时间为

(1)

若非特意声明，本文所有公式中变量的单位均为国际单位制基本单位及其导出单位.

1.3 数据传输区域

模型中数据传输的方式有V2I和V2V两种.V2V和V2I两种模式相互协作提高数据传输的可靠性已成共识.V2V通信方式建立在车辆与车辆之间，适用范围较广，但传输速率和稳定性相对较低，V2I通信建立在车辆与路边单元之间，稳定性较高，且传输速率较高，但是需在路边单元覆盖的区域下使用.假设车辆在单个RSU下完成了计算任务的卸载，并且在车辆未驶离该范围时，直接进行V2I的方式进行数据的传输，反之，则需要选择其他辅助回传策略进行传输.本文使用V2I等待策略和V2V辅助回传策略.

1)V2I等待策略：V2I等待策略是指车辆驶离RSU的覆盖范围时，进入等待状态，RSU通过核心网络将待回传数据下发至下一个RSU，等待车辆驶入到下一个RSU覆盖范围内通过V2I的方式建立通信进行传输.当道路上的车辆密度较小时或者使用其他策略的能耗较大或者对时延可以有较大的限度的容忍时，可以使用.基于此传输方式的时延通常是RSU覆盖盲区的距离除以车辆的平均速度.

2)V2V辅助回传策略：在RSU未覆盖的区域通过寻找中继节点进行通信，寻找中继节点的方式也有两种.因为是在双向车道中，可以通过同方向的节点进行传输，也可以由对向车道中的节点进行传输，借助对向车道进行传输需要RSU先将数据传输至下一RSU.

本文在设计回传策略时，底层的车辆可以通过移动通信技术和车载通信协议与周边的车辆和路侧基础设施直接通信传递数据，则RSU通过对接收的车辆发送的信息进行整合计算，可以获知路段上的各个车辆位置及车流量，然后多个RSU间进行通信可得出路网的信息.当车辆不在RSU覆盖范围内时，先比较车辆与不同RSU间的距离，选择距离最近的RSU作为下一个RSU.

2 回传策略设计与分析

2.1 状态初始化

在车辆驶入到非RSU覆盖的区域下，计算任务的回传可以从往来的车辆中选择最优的节点作为中继节点，为了更好地描述，本文做以下表述.

假设源车辆S_vehicle的平均速度为vs，目的车辆D_vehicle的平均速度为vd，在初始时刻(源节点和目的节点建立连接的时刻)，车辆S_vehicle的初始位置为ps(0)，车辆D_vehicle的初始位置为pd(0)，两车间初始距离d0的表示如公式(2)所示.

(2)

假设Xs(t)与Xd(t)分别表示两个车辆在时间间隔t内的位移量，可记作Xs与Xd，则

Xs(t)=vst,Xd(t)=vdt

(3)

假设回传任务的大小为Cdown，车辆间通信信道的带宽为Bv2v，则回传任务的传输时延为

(4)

车辆在道路上随机分布，假设车辆驶入符合泊松分布，并且参数为λ，则在时间[0,t]范围内，有m辆车驶入的概率为

(5)

引理1在同向双车道的环境下，假设车道1和2的分布参数分别为λ1，λ2，令R′=δR，其中0<δ≤1，则在源车辆节点和其通信范围内同车道内距离最近的节点间距的累积分布函数表达式为

(6)

在源车辆节点和其通信范围内的不同车道内最近节点间距的累积分布函数表达式为

(7)

推论1假设参考节点有M个层间邻居，定义参考节点与最远层间邻居的距离为

(8)

则Y的累积分布函数表达式为

(9)

在V2V辅助传输策略中，按照逐条的方式选择中继节点，第l个中继节点的选取取决于第(l-1)个中继.假设在1车道上有k个邻居，在1车道上的一跳的距离为X，则第2跳的条件为

(10)

2.2 链路维持时间评估

同向车道的场景如图2所示，在同向上寻找中继节点，目的车辆D_vehicle驶出RSU覆盖区域，与中继车辆S_vehicle在同一方向行驶，两车间的初始距离为d0，0

1)当vs>vd时，两车间的距离会越来越小，直到后车超越前车拉大两车距离，直至驶离彼此的通信范围，距离间关系和链路生存时间如下

Xs-Xd=d0+R

(11)

(12)

2)当vs

Xs-Xd+d0=R

(13)

(14)

3)当vs=vd时，两车是处于相对静止的状态，链路建立有效时间认为是无限的，t=∞.假设正向道路的最大速度为vmax，最小速度为vmin，vmin

(15)

反向车道的场景如图3所示，在对向车道上寻找中继节点，目的车辆D_vehicle驶离RSU覆盖区域，与中继车辆S_vehicle在不同方向行驶建立链路，两车间的初始距离为d0(0

假设源车辆S_vehicle的平均速度为vs，目的车辆D_vehicle的平均速度为vd，无论源节点速度与目标节点速度大小关系如何，距离间关系和链路生存时间分别为

Xs+Xd=d0

(16)

(17)

假设反向道路与正向道路的速度范围一致，最大速度为vmax，最小速度为vmin，vmin

(18)

图2 同向车道场景Fig.2 Scenario of lane in the same direction

图3 反向车道场景Fig.3 Reverse lane scenario

2.3 稳效值的定义与计算

本文定义的稳效值(Link stability and efficiency，LSE)主要用来评估链路的稳定性和传输的效率，其值越大则说明链路状态越理想，反之则不理想.在建立链路的过程中，优先选择稳效值最大的作为下一跳节点.特别注意，LSE是一个相对值，用于本地择优，仅在评估通信范围内的候选节点中生效.定义

(19)

对于指标的权值估计是使用网络层次分析法(Analytic Network Process,ANP).ANP是将系统元素划分为两大部分见图4.

图4 网络层次分析法Fig. 4 Network hierarchy analysis

本文目标是寻找最佳的下一跳转发节点，决策准则是链路的稳定性.首先是将元素中的元素按其影响因子大小进行对比，构造判断矩阵.根据得出的结果构造比较矩阵，元素和元素集的局部权重向量矩阵Wi,j可通过计算比较矩阵的特征向量获得.对于判断矩阵，通过求和法对每个矩阵内的元素进行求和得到向量α=(α1,α2,…,αi)τ如下

(20)

(21)

通过c=αω汇总可以得到加权超矩阵.然后以加权超矩阵为基础，通过式(22)对加权超矩阵做稳定性处理得

(22)

2.4 V2V辅助策略算法描述

辅助策略主要有以下步骤：

步骤1 车辆节点通过广播消息包得到邻居节点的位置和速度信息.路边单元先将回传数据传递至下一个路边单元，两个路边单元再将回传数据传至覆盖范围内距离边界最近的车辆节点；

步骤2 从两个方向进行寻找最优路径，根据式(4)计算出回传任务的传输时延ttrans，先与反向最小链路寿命进行对比，若满足

(23)

说明传输时延小于反向链路的最小寿命，则任务反向链路可以候选条件，反之，若满足

(24)

则方向链路失效，直接转向步骤4)；

步骤3 若反向距离大于距离的一半，构建反向辅助链路，否则直接转步骤4).通过定时更新的本地路由表信息根据式(19)计算出邻居节点的LSE的值，选择满足条件的最大LSE值的节点，当LSE值不变时选择距离最大的节点.若在时间阈值内未收到链路建立信息，则证明反向链路失效.反之，直接转向第四步；

步骤4 构建正向辅助链路，通过定时更新的本地路由表信息根据式(19)计算出邻居节点的LSE的值，选择满足条件的最大LSE值的节点，当LSE值一样时选择距离最大的节点.若在阈值内未收到链接回复信息，则证明辅助回传策略失效.

基于V2V的辅助回传策略如算法1所示.

算法1基于V2V的辅助回传策略

1 初始化道路车辆密度ρ、回传的数据量Cdown、车辆节点的信息(速度、方向、位置)，道路最大速度vmax、最小速度vmin；

3 重复

4 计算反向速度影响因子；

5 计算反向距离因子；

6 根据式(19)更新LSE；

7 直到计算所有的邻居节点，从邻居节点中选择LSE值最大的节点作为中继节点，重复执行上个流程；

8 若在时间阈值范围内与节点D建立好通信链路，则返回正确建立链路的状态；

9 否则

10 重复

11 计算正向速度影响因子；

12 计算正向距离因子；

13 根据式(19)更新LSE；

14 直到计算所有的邻居节点，从邻居节点中选择LSE值最大的节点作为中继节点，重复执行上个流程，若在时间阈值范围内与节点D建立好通信链路，则返回链路正确建立状态值，否则返回建立失败状态值；

算法1复杂度分析：算法的时间复杂度为O(nlogn).V2V辅助回传算法的时间复杂度主要由建立的路径和判断使用正向辅助策略还是反向辅助策略决定的.链路的建立的过程是对道路上的N个车辆节点的操作，最坏的情况是从源节点到目的节点利用了网络中的每个剩余节点，因此最复杂的情况是计算所有节点的LSE的值.在计算过程中，计算备选节点与本节点之间的几个参数，其复杂度为O(n).然后算法的最大时间消耗是每次选择一个最大LSE的值.对于从N个值中选择最值的复杂度为O(nlogn).因此辅助回传算法的时间复杂度为O(nlogn).

2.5 回传算法描述与分析

回传算法步骤如算法2所示.

算法2完整回传算法

输入：车辆属性值

输出：链路状态码

1 判断目标车辆所在位置，若目标车辆仍在本单元的覆盖范围内，则直接进行V2I的直接传输，返回链路成功状态并退出.若车辆行驶至临旁的路边单元，则直接转第三步.若目标车辆位于路边单元未覆盖的范围，则进行第二步；

2 调用算法1，根据返回的状态值进行判断，若返回的链路建立成功的值，则直接返回该状态并退出算法；

3 路边单元将待回传的数据传递至距离车辆最近的同向路边单元.若车辆已经驶入，则直接进行V2I的传输.若车辆未驶入，设置监听状态，等待车辆驶入该覆盖范围直接进行通信，返回链路建立状态码.

等待回传策略性能分析：V2I等待回传策略是在辅助回传策略失效时使用，其时间的消耗主要是发生在从开始节点到驶入RSU覆盖区域的等待时间，假设距离为Xw对于较少的数据量V2I的通信时间可以忽略，则回传的等待时间tw表示为

(25)

则其均值可以表示为

(26)

算法2复杂度分析：算法的时间复杂度为O(nlogn).回传策略的时间复杂度主要计算在于辅助回传策略，辅助回传策略的时间复杂度在上文已经分析完成，回传策略的最大传输时延为等待回传策略的时延.

3 实验与分析

3.1 测试环境和参数设置

采用NS-2.35平台对本文提出的算法进行仿真实验分析，并将本文提出的辅助回传策略与no-co(不使用辅助车辆)回传策略、ra-co(随机选择车辆进行辅助下载)、CPB(基于连通概率)、DSRelay(基于动态时槽的协助方法)以及NICDM(无间隙协助回传算法)进行对比分析.仿真参数如表1所示.

表1 仿真参数Tab.1 Simulation parameters

通过改变驶入车道的车辆的密度、速度因子以及研究RSU分布密度等因素，利用数据包交付率、数据交付时延以及转发节点比率3个性能指标，评估本文提出的传输策略.

数据包交付率定义为成功传送到目标节点的数据分组的数量与源节点传输的数据分组的数量之间的比率.该指标反映了数据传输可靠性.

数据交付延迟又叫作端到端传输时延是指数据包从分组生成到传递到目的地的时间延迟.此度量标准指示从源节点发送数据包后目标接收的速度，用来评估传输的效率.

转发节点比率定义为参与转发的中继节点在车道上总的节点数的比率，用于反链路的开销，参与转发的中继节点越多，网络的开销就越大.

3.2 仿真实验测试与分析

在改变车道上车辆密度的情况下，保证其他因素一致，对比结果如图5～图7所示.

图5 不同车辆密度与数据交付时延之间关系Fig.5 Relationship between different vehicle densities and data delivery delays

由图5可以清晰地看出，不使用车辆辅助传输的NO-CO因为使用V2I的方式进行传输，所以其性能与车辆密度无关.而其余4个方法皆随着车辆密度的增加，数据的交付时延随之降低.本文提出的算法交付时延一直小于其他方法，原因是本文提出的方法在选择中继节点，综合考虑链路的生命周期，保证在链路的生命周期内完成数据的传输，防止因为节点移动而导致的链路中断所耗费的时间，并且在LSE相等的情况下优先考虑选择距离目标节点最近的节点作为中继节点.实验分析表明，本文提出的回传算法在时效性上具有更大的优势.

图6 不同车辆密度与数据包交付率之间关系Fig.6 Relationship between different vehicle densities and packet delivery rates

由图6看出，随着车辆密集度的增加，除NO-CO的其余4个方法的R包的交付率均呈上升的趋势.本文提出的算法的数据包的交付率始终高于其他几个方法，究其原因是当车辆密度增加时，可供选择作为中继节点的车辆数随之增加，最后从中选取LSE最优并且距离目标节点最近的节点作为中继节点，提高了数据包交付率.实验证明当车辆密度相同时，本文提出的算法的可靠性更高.

图7 不同车辆密度与转发节点比率之间关系Fig.7 Relationship between different vehicle densities and forwarding node ratios

通过实验7可以看出，在链路开销方面本文方法是最少的，这是因为本文的方法在构建链路时综合考虑相对距离和速度因子等因素，在构建链路时在保证质量的前提下保证最少的跳数.

图8 不同速度与数据交付时延之间关系Fig.8 Relationship between different speeds and data delivery delays

在改变车辆平均速度的情况下，保证其他因素一致，对比结果如图8～图10所示.由图8可得，不使用车辆辅助传输的NO-CO因为使用V2I的方式进行传输，所以其性能与速度无关.随着速度的增大，平均端到端时延变大，导致网络拓扑发生变化，已有的路径可能不再满足通信的需求，导致需要重启路由发现过程，这无疑增大了传输时延，但相比其他方法，本文的方法有较好的性能.

图9 不同速度与数据包交付率之间关系Fig.9 Relationship between different speeds and packet delivery rates

图10 不同速度与转发节点比率之间关系Fig.10 Relationship between different speeds and forwarding node ratios

图9中，随着速度因子的增加，除NO-CO的其余4个方法的R包的交付率均呈下降的趋势.这是因为随着车速的增加导致链路的有效时间减少，会出现频繁的重连甚至增加网络的跳数，但本文提出的算法的数据包的交付率始终高于其他方法.

通过图10可以看出，在链路开销方面随着速度的增加导致跳数的增加.这是因为在构建传输链路时，由于车辆的移动速度不一致，当车辆的移动速度过大，目标车辆与缓存车辆的通信链路维持时间缩短，导致链路频繁中断甚至需要多次重连，最终表现为转发节点比率增加.这也从侧面解释了为什么本文提出的算法在车辆速度为20前较低，而在20后较高，验证了之前的分析.