基于北斗和边缘计算的车联网导航技术研究

周启平，何 伟，贾 蕾，郭俊凯，赵建国

(1.安徽继远软件有限公司，安徽 合肥 230088； 2.中国电子科技集团公司第二十研究所，陕西 西安 710068；3.四创电子股份有限公司，安徽 合肥 230011)

车联网是一种新兴的模式，由车载单元、路边单元、移动网络和配备了无线射频识别技术、图像采集设备和各种传感器的车辆组成，具备车辆通信、路况收集、资源共享、交通和安全服务等功能。利用车联网通信和网络，可将采集数据分发给其他车辆和路边设备，并获取驾驶条件、系统运行状态和道路环境等信息。车联网的发展使得人们出行更加智能，让建设智慧城市成为可能，它也是未来智能车辆自主驾驶和智能交通系统的基础。高精度定位技术作为车联网业务中的一项关键技术，为用户提供了精准可靠的位置信息，可有效提升车辆行驶安全性和驾驶体验。但在实际应用中，车联网仍存在系统定位精度低、耗时长等一系列问题，因此提高车联网的定位能力和效率势在必行。

近年来，国内外学者针对车联网定位和导航等方面开展了大量理论研究。文献[1]提出了一种基于稀疏贝叶斯学习(Sparse Bayesian Learning，SBL)的到达角卷积神经网络(Direction of Arrive，DOA)估计方法，实现了非均匀噪声条件下目标车辆的离网DOA估计。在该方法中，非均匀噪声协方差矩阵采用最小二乘法(Least Square，LS)估计，通过求解多项式根实现网格精化，进而细化网格点，从而减少了离网误差。该方法还根据DOA估计结果，在定位系统中通过每两个基站对目标车辆进行一次交叉定位。该方法有效克服了车辆在GPS信号较弱的地方定位精度低的问题，提高了车辆的定位精度，但该方法的定位过程存在较大传输时延。文献[2]提出了一种利用单一信号源的机会信号(Signal of Opportunity，SOP)进行车联网定位的新方法。该方法基于SOP的到达时间差(Time Difference of Arrivals，TDOA)。由于信号中包含了车辆轨迹约束的先验信息，一定程度上有效提高了定位精度，但在受到外界信号和环境干扰时，车辆定位精度无法得到有效保障。文献[3]提出了一种传感器融合算法来对车辆定位及预测车辆未来的运动轨迹，但方向和距离测量的误差会对最终位置产生重大影响，且定位耗时较长。文献[4]提出了一种基于差分定位机制车联网定位方法，其中车辆使用无线介质将其GPS观测值发送到基站。基站融合接收到的GPS数据和本地GPS观测值，实现高精度车辆跟踪，但该方法数据传输耗时较长，无法满足实际应用中的低时延要求。

综上所述，大多数研究方法均存在定位精度较低或传输时延大的缺陷。基于此，本文提出了一种基于北斗定位和边缘计算的车联网技术研究，其可为大规模车联网终端提供实时精准、低延迟和高精度的定位服务。在本方法中，将升级后的蜂窝基站用作边缘节点，可减轻数据中心的计算压力，将计算所得差分校正信息实时播发。为解决终端的多路接入问题，本文提出了一种改进的遗传任务分配算法，该算法可以最大程度地减少服务时延，并确保边缘节点的负载均衡，同时利用基于边缘节点的优化无损卡尔曼滤波算法来提高终端定位精度。

1 算法原理

1.1 实时动态差分法技术

实时动态差分法(Real-Time Kinematic，RTK)又称为载波相位差分技术，该技术原理是在基准站上安置一台接收机，对卫星状态进行连续观测，并通过无线电传输设备实时地将观测数据及测站坐标信息传送给用户站；随后，用户站在接收卫星信号的同时，通过无线接收设备接收基准站信息，根据相对定位原理进行实时处理，解算出用户站的位置坐标[5]。基于数据中心的RTK差分定位系统架构如图1所示，图中车联网节点等同于所述用户站。

图1 基于数据中心的RTK差分定位系统架构Figure 1. RTK differential positioning system architecture based on data center

基准站接收机所测得的载波滞后相位[6]为

(1)

(2)

同理，用户站接收机测得的载波滞后相位表示如式(3)所示。

(3)

(4)

1.2 高效数据通信传输算法

在通常情况下，采用常规高精度RTK定位算法可以获得良好的车辆定位精度。然而在高速移动场景下，由于车辆差分定位数据存在传输时延，导致车辆定位结果存在一定的定位偏差，无法及时获得高精度定位结果，对车辆导航会产生较大影响。基于此，本文利用5G和边缘计算技术，提出一种高效的数据通信传输方法，可有效降低数据传输时延，进而获得实时的高精度定位数据。

5G通信技术的发展为导航和通讯两者的融合奠定了坚实的基础。通过对导航和通信设备进行综合集成，将移动蜂窝网络基站改造升级为基准站用来观测卫星导航信号，基于现有基准站形成边缘计算网络，为终端提供导航和定位服务[8]。

车联网系统架构如图2所示，目前车联网系统传输采用3G/4G技术，存在较为严重的传输延迟，无法及时获得车辆数据，难以满足车辆实时定位的要求。由车辆侧传输的数据一般传输到数据中心云端，由于车辆数据体量大，数据中心需要承受巨大的处理负荷，一定程度上影响数据处理响应效率，导致其无法为车辆提供实时的高精度定位服务。

图2 车联网系统架构Figure 2. Architecture of internet of vehicles

边缘计算是一种靠近终端的小型数据中心周边网络边缘的计算技术。基站作为车联网的重要组成部分，负责连接终端和云服务。将位于终端侧的基准站用作边缘节点，能够为大量已部署且地理位置分散的车联网终端节点提供高精度定位服务，具有低延迟、实时交互、移动性支持等特点[9]。

如图3所示为基于边缘计算的定位系统架构，主要包括物理层、边缘层和云层。其中物理层主要包括车联网节点、边缘层包括基准站及其网络；云层包括云服务器和数据中心等内容。物理层和边缘层负责定位，云层负责数据的收集、分析和处理工作，具体描述如下：

图3 基于边缘计算的定位系统架构Figure 3. Positioning system architecture based on edge computing

(1)车联网节点由传感器、设备和终端等构成。首先终端发起定位请求，北斗定位模块测量卫星信号，并将测量数据发送到边缘节点；随后边缘节点根据某些规则和策略进行计算，最终得到终端用户的定位信息[10]；

(2)边缘节点相当于小型数据中心，为终端的定位服务提供计算和存储资源。边缘节点可以进行数据预处理、简单数据分析和预测，并将结果发送到云服务器或终端。边缘节点可进行相互通信，连接到边缘计算网络并进行分布式计算。根据终端的大致位置坐标，由边缘节点动态生成差分校正信息，为用户提供实时的高精度定位结果；

(3)云使用终端收集的数据，可为终端提供历史数据分析、数据存储和用户行为预测等关键服务。云服务包括终端用户跟踪、配置、分析、报告、认证和授权等服务。

基于边缘计算的定位方法旨在解决数据中心集中计算的高延迟问题。将基站用作边缘节点，当终端发出定位请求时，最近的边缘节点接收到定位请求，并计算出差分校正信息，再将其发送到终端进行解算。

1.3 算法优化

1.3.1 基于5G和边缘计算的定位算法

该算法的基本思路是当终端发出定位请求时，每个终端选择距离最近的边缘节点进行定位计算。边缘节点将计算所得差分校正信息通过5G网络发送给终端，终端根据该校正信息获得当前位置的高精度定位信息。但该算法并未考虑负载均衡策略，在终端高并发请求场景下，可能出现流量过载现象。由于终端数量较多且地理分布较广，通过利用链路调度方法可以实现最佳负载均衡和最小链路时延。

边缘计算网络可以用加权有向图G=(V，E)进行表示，其中V={v1，…，vi，…，vm}为边缘节点集合，E={e1，2，…，ei，j，…，em-1，m}为边缘连线集合[11]。ei，j表示vi和vj之间的边缘连线，其通信时延为τi，j。每个边缘节点所赋予的计算能力为ri。U={u1，…，uk，…，un}为定位请求任务集合，该集合U服务时延表示为

d=max{Ci/ri+tk，i+τi，jxi，j}

(5)

式中，Ci为边缘节点vi上的请求容量；Ci/ri为边缘节点vi的计算时间，也可表示任务uk的等待时间；tk，i为终端k与最近边缘节点vi之间的传输时延。如任务uk从边缘节点vi传输至vj并在vj进行计算，令-xi，j=1，否则xi，j=0，即任务uk在最近的边缘节点vi处进行计算。考虑到终端移动性和边缘节点的服务范围受限，回程时延表示为

(6)

式中，ε是边缘节点vi的服务范围。若终端k在边缘计算节点vi的覆盖范围内，则将差分校正信息由边缘计算节点vi发送到终端k，否则由最近的边缘节点vj发送到终端k。

边缘计算网络中定位请求的服务时延等于所有终端的最大时延。为达到定位请求时延最小的目标，需要使目标函数d最小化，因此任务分配问题的目标函数可表示为式(7)。

(7)

将定位任务分配给这些边缘节点时，为使得服务时延最小化，每个定位请求应被分配给最近的边缘节点。由于终端地理位置分布不均以及各边缘节点的计算能力有所不同，定位请求的初始化可能引起某些边缘节点的过载现象[12]。

在边缘节点上重新分配定位请求来确保负载平衡，能有效降低系统服务时延，提高系统吞吐量。在定位请求初始化完成后，将边缘节点的平均计算时间设置为阈值，超出阈值φ的定位请求将被重新分配，每个边缘节点用于重新分配定位请求的容量为ΔCi。任务分配问题如式(8)所示。

(8)

常用任务分配算法有蚁群算法(Ant Colony Algorithm，ACA)和遗传算法(Genetic Algorithm，GA)。相较于ACA，GA的复杂程度较低，运行时间更短，可有效满足实时定位场景应用需求。采用基于自然选择的遗传算法进行任务分配，其具有良好的隐含并行搜索特性，能够解决大规模组合优化问题。该算法具备全局解空间搜索能力，为获得最优解或近似最优解，可对群体迭代执行选择、交叉和变异等遗传操作[13]。

为有效解决终端定位请求服务时延问题，提升终端定位请求效率，本文将改进的遗传算法用于重新分配超出阈值φ的定位请求，以确保系统服务时延最小化。该遗传算法包括3个步骤：

步骤1选择操作。为缩短该算法执行时间，将计算时间低于阈值φ的边缘节点解空间作为第1代染色体。选用混合选择策略来选择染色体，首先将种群中最优的20%个体复制到下一代，然后采用轮盘赌算法对其余80%个体进行选择。

首先计算每个个体的适应度值fk，并计算每个个体的遗传概率

(9)

然后计算每个个体的累积概率

(10)

最后，确定选择的个体。产生1个[0，1]内的随机数r，若r

步骤2交叉操作。交叉运算决定算法的全局搜索能力，其选择出来的个体具有很高的适应性。随机生成一个随机数rand∈[0，1]，并与交叉概率pc比较，如果rand

步骤3变异操作。采用单点变异方法，即从边缘节点中随机选择1个进行基因突变，这种随机性有利于加快趋向最优解的收敛速度。该方法合理地将每个定位请求分配给相应的边缘节点，能有效降低定位时延，提高终端定位的实时性。

相较于常规遗传算法，改进遗传算法在全局收敛性和收敛速度方面都有改善。为验证该算法有效性，采用具有相当复杂度的测试函数Shaffer′s F6函数[14]，如式(11)所示。

(11)

对于常规遗传算法，经过几百次的进化，其解分别收敛于局部极大值，而始终没有收敛到全局最大点(0，0)。对于改进遗传算法，进化经过几百代甚至几十代后，无论初始群体如何，均收敛于全局最大值。

表1 两种算法收敛比较Table 1. Comparison on the convergence of the two algorithms

边缘计算网络的负载均衡度由每个节点的任务处理时间标准差(Time Standard Deviation，TSD)测量得出，为获得良好的负载均衡性能，TSD应较低[15]

(12)

经过任务分配后，所有终端的定位请求都分配给了记录为主站的边缘节点。将5G基站用作边缘节点，结合主站与至少两个辅站等数据进行计算，得到终端近似坐标的差分校正信息。由于终端近似坐标(x′u，y′u，z′u)与实际坐标(xu，yu，zu)之间相距几米到十米，故可根据近似坐标的差分校正信息来校正观测值，进而获得精确的定位结果[16]。

ΔImi+ΔTmi+Δεmi

(13)

对于终端近似值u′，主站m与u′两者单差为

ΔImi+ΔTmi+Δεmi

(14)

类似地，辅站1和2表示为式(15)。

(15)

已知主站和辅站的位置坐标，伪距单差可通过观测数据计算得到，系数可由式(13)求解得到。

(16)

在将电离层、对流层、卫星轨道和时钟等误差具有较强空间相关性的误差消除之后，则终端u与卫星s之间的几何距离表示为式(17)。

(17)

根据终端的近似坐标，距离差值可通过坐标差值表示。由于两个坐标之间的距离非常接近，泰勒展开的高阶导数几乎为零，仅保留一阶导数，则修正后伪距观测方程的误差方程为[18]

(18)

卫星数为n，对应的误差方程为

V=AδX+L

(19)

其中

(20)

当观测到不少于4颗卫星时，通过加权最小二乘法求得最小二乘解，其中L均值为0，方差矩阵为Q

(21)

最终终端精确坐标信息表示为式(22)。

(22)

如图4所示为基于边缘计算的定位算法流程。

图4 基于边缘计算的定位算法流程图Figure 4. The flow chart of the positioning method based on edge computing

1.3.2 优化后算法

由于最小二乘算法相对简单，每次定位结果相互独立，具有较大的定位误差。无损卡尔曼滤波(Unscented Kalman Filter，UKF)[19]算法具有计算量小和定位精度高等特点，可通过滤波减少误差对定位精度的影响，实现精准的目标跟踪。

UKF非线性系统可表示为

(23)

式中，f和h分别为非线性状态函数和非线性测量函数；Wk和Vk是相互独立的，且均值为0；协方差矩阵分别为Qk和Rk的白噪声。

为了确保估计的公正性，滤波的初始值为式(24)。

(24)

基于边缘计算的定位算法模型，提出了一种基于边缘节点的无损卡尔曼滤波(Unscented Kalman Filter Based on the Edge Node，EUKF)算法。考虑到终端的计算能力有限，由边缘节点负责计算并将定位结果发送到终端。为有效提高定位精度，将终端周边大量边缘节点用于协同定位，并由主站将定位结果发送给终端[21]。

(25)

组合测量值可表示为式(27)。

(26)

利用主站周边的边缘节点进行递归操作来校正测量误差[22]，误差协方差矩阵可以表示为

(27)

式中，Ai为加权矩阵，由边缘节点到终端之间距离和边缘节点的置信度确定。加权矩阵Ai表示为式(28)。

Ai=diag(a1，a2，…，an)

(28)

如果从边缘节点到终端的距离很远，且边缘节点的置信度较低，则Ai值较大，滤波器增益相应减小，进而减小系统误差对定位精度的影响。

终端的状态向量为

(29)

式中包含终端的三维位置坐标、三维速度、三维加速度和接收机钟差等参数，终端的状态方程为

Xk+1=ΦXk+Wk

(30)

(31)

根据上述模型可以求解出终端的位置坐标。

2 测试验证

如图5所示，本文采用诺瓦泰接收机板卡NovAtel OEM719D接收卫星数据，并接收来自基准站的差分数据，为车联网节点提供高精度差分定位服务。

图5 诺瓦泰OEM719D板卡Figure 5. Novatel OEM719D broad

为了验证卫星观测数据定位的可行性，对一定观测时段内可视卫星进行观测。如图6所示，在观测期间，可视卫星的数量均不少于4颗，满足定位要求。如图7所示，位置精度因子(Position Dilution of Precision，PDOP)均小于3，属于比较理想的状态，因此可利用观测数据可计算出准确定位结果。

图6 可视卫星数变化Figure 6. Variation of the number of visible satellites

图7 PDOP值变化Figure 7. Variation of PDOP

本文采用MATLAB软件对算法进行仿真实验。根据5G网络基站的平均覆盖率，基站间距设置为500 m，将安徽合肥500个5G基站选作边缘节点。假设边缘节点具有相同计算能力，且终端定位请求是随机生成的。遗传算法相关参数设置如下：cp=0.2；pc=0.6；初始种群个体数为100个；迭代次数为100次。利用接收机实测数据计算终端定位结果。

2.1 定位精度

为获得真实可靠的验证数据，通过跑车试验，采集北斗定位和惯导数据，并以惯导数据作参考标准，对北斗定位数据进行统计分析，得出车联网终端的平均定位误差为0.921 6 m。

在不同环境下的定位误差如图8所示，结果表明EUKF算法利用边缘节点消除了系统误差，其定位精度高于UKF算法。

(a)

(b)图8 动态定位误差 (a)开放环境 (b)复杂环境Figure 8. Errors of dynamic positioning (a)Open environment (b)Complex environment

2.2 服务时延

如图9所示为不同方法的服务时延对比情况。结果表明，基于边缘计算的定位算法会减轻数据中心的计算压力。差分校正信息由靠近终端的边缘节点求解，缓解了数据中心计算量大、带宽受限、吞吐量高的问题，有效减小了系统服务时延。如果最近的边缘节点接收定位请求并在初始化后计算差分校正信息，由于终端定位请求的不平衡会增加服务时延，但改进GA的边缘计算网络可以实现负载平衡，边缘节点上的过载终端定位请求会被重新分配，可进一步降低服务时延。

图9 服务时延对比曲线Figure 9. Comparison of the different service delay

边缘网络在改进GA前后的负载平衡性能如图10所示。随着终端数量的增加，进行负载均衡改进的定位算法可以平衡终端的定位请求分配，有效缩短边缘网络的任务处理时间。

(a)

(b)图10 负载均衡性能 (a)任务处理时间标准差 (b)处理请求标准差Figure 10. Load balancing performance (a)Task processing time standard deviation (b)Processing request standard deviation

3 结束语

本文开展了基于北斗定位和边缘计算的车联网技术研究，利用北斗定位技术解决车辆高精度定位问题，通过5G通讯技术实现定位信息的高速传输，并采用基于边缘计算技术，有效缓解了数据中心计算压力，提升了系统运行效率和实时响应速度。仿真结果表明，本文所提方法可以为车联网提供实时准确的定位服务，解决了车联网中高精度、低延时、数据并发量大等实际问题，且满足了车联网系统的可靠性和实时性要求。