无人驾驶需要对周边环境进行3维建模，构建高精度地图用于自主定位、轨迹估计、路径规划和车辆控制等。由于激光雷达可以提供低误差且高频率的点云数据，在自动驾驶车辆部署激光雷达传感器已经变得非常普遍(Li等，2018)。典型的SLAM(simultaneous localization and mapping)地图构建需要单独覆盖整个建图区域，这往往带来较长的构建周期和较大的计算资源需求。此外，激光里程计也会随着距离增加而产生累积误差。

一种常见的解决方式是在多辆无人驾驶车上部署SLAM算法(Zhe等，2018)。更具体地说，在多车场景中，每辆车只需要探索其感兴趣的区域，通过与邻近车辆交换地图信息来协同构建环境地图，从而使每辆车获得更多的地图信息。如图 1所示，相比于单车而言，多车建图可以缩小里程计里程误差。然而，车辆只能与邻近车辆进行数据交换，车辆之间的相对坐标转换也是未知的。如何以一致的方式合并所有的局部地图，这需要在协同车辆之间建立一个共同的参考系即通过中心节点对每辆车点云数据的特征信息进行配准和坐标变换，从而实现整体3维地图构建。

基于边缘计算构建具有中心节点的多车协同SLAM系统并非易事。首先，很难有效地匹配和合并重叠的区域。尽管GPS信息缩小了地图的配准范围，但对多辆车的历史点云数据进行精确匹配仍不现实，这往往需要花费极大的算力。其次，无人驾驶车辆如何进行工作负载卸载以保证自身的精准定位，同时在边缘服务器算力有限的情况下，如何满足多辆车的卸载需求也是需解决的问题之一。最后，边缘服务器还需要合并多车建图数据，构建出完整的3维全局地图。

计算卸载调度问题的目标函数往往是非凸函数，通常的做法是使用拉格朗日松弛法来处理约束条件(Yang等，2017)，或者使用一些特定的启发式算法来找到接近最优解。常用的启发式搜索算法有贪婪算法(Cui等，2017；Moubayed等，2020)、遗传算法(Deng等，2015)和粒子群算法(Rodrigues等，2018)等。这类算法通过搜索解空间来接近最优解，不同情况下的相关参数设定要求相对较高，并且合适的迭代次数无法确定，这将造成过多的计算时间和能源消耗。Wei等人(2019)使用强化学习来获得次优解或最优解。但随着问题复杂程度的增加，解空间不断扩大，仅使用Q-learning带来的计算和存储的开销将难以接受。因此，基于深度强化学习的方法(Min等，2019；Liu等，2019)被提出，以用来降低求解空间的维度。深度强化学习除了将Q-learning和神经网络结合(Chen等，2019；Zhang等，2019)来逼近值函数求解外，还可以通过异步优势actor-critic算法(asynchronous advantage actor critic，A3C)(Qi等，2019)在高维度和连续动作空间中获得更高的效率。但深度强化学习需要训练的参数数量庞大，对训练样本的数量和分布情况要求高，训练时间长，且方法的复杂度高。为了减少预设参数的数量，降低方法的复杂度，一些研究人员将问题转换为用户间的博弈来求解次优解(Yang等，2018；Wang等，2020)，但此类方法随着问题规模的扩大，求解时间往往较长，无法满足车辆的低延迟要求。

基于博弈论求解任务调度问题(Chen等，2016)的启发，本文提出了一种基于边缘计算的协同激光雷达SLAM方法。将调度问题建模为策略博弈问题，并证明此问题属于势博弈(Monderer和Shapley，1996)问题。根据势博弈有限的改进特性，设计了快速收敛的多无人驾驶车辆卸载算法。此外，基于相对可信度，计算各个车辆的地图合并序列，可以高效地匹配且合并多个车辆的建图数据。实验结果表明，该方法可以有效地实现点云匹配和地图合并，缩短响应时间，获得准确的定位结果。

基于边缘计算的多车协同SLAM系统框架结构如图 2所示。首先，处于未知环境的无人驾驶车辆会独立进行定位与建图，并通过基站(base station，BS)与边缘服务器相连，进行计算卸载以减少本地负载。此外，点云地图和GPS等数据也被转换到BS坐标下存储到边缘服务器中。然后，系统利用车辆的GPS信息判断车辆之间是否存在重叠区域，存在则进行车辆间的地图匹配，否则根据GPS信息拼接地图。最后，系统根据地图匹配结果合并各无人驾驶车辆的局部地图。在运行时，系统会重复这个过程，直到它绘制出BS覆盖的完整地图。

本文使用的单车SLAM是基于Zhang和Singh(2014)提出的激光雷达里程计与建图(laser dometry and mapping，LOAM)算法，其不需要使用额外的高成本惯性测量单元(inertial measurement unit，IMU)就可以提供足够的定位精确度。算法流程如图 3所示，主要有4个部分：特征提取、里程估计、建图和定位。算法从激光雷达中收集原始数据作为输入。然后根据数据的空间信息进行分类，并提取平面特征和角特征。接下来，里程估计需要分析连续两帧激光雷达点云的特征，并使用非线性最小二乘算法估计两者之间的坐标转换关系。再利用上述坐标转换关系估计车辆位姿，获得粗略的定位结果。在建图部分，算法通过累积点云帧的方式将点云映射到全局坐标系，得到局部区域地图，并再次使用非线性最小二乘算法估计车辆位姿，获得精确的定位结果。

地图匹配的关键是准确匹配多辆车的局部地图重叠区域，并找出参考帧的相对变换。给定两帧点云作为输入，使用匹配算法(Rusinkiewicz和Levoy，2002；Biber和Strasser，2003)可以找出最优的4×4旋转平移矩阵(rotation and translation，${{\rm{RT}}}$)，使得点云中相应点之间的距离最小化

$ {\mathit{\boldsymbol{T}}_{{\rm{RT}}}} = \left[ {\begin{array}{*{20}{l}} {{\mathit{\boldsymbol{R}}_{3 \times 3}}}&{{\mathit{\boldsymbol{T}}_{3 \times 1}}}\\ {{{\bf{0}}_{1 \times 3}}}&1 \end{array}} \right] $

(1)

式中，$\mathit{\boldsymbol{R}}$表示旋转矩阵，$\mathit{\boldsymbol{T}}$表示平移矩阵。随后使用${{\rm{RT}}}$矩阵将地图转换到同一坐标下完成地图合并。

$ {\mathit{\boldsymbol{M}}_2} = {\mathit{\boldsymbol{T}}_{{\rm{RT}}}} \times {\mathit{\boldsymbol{M}}_1} $

(2)

式中，${\mathit{\boldsymbol{M}}_2}$和${\mathit{\boldsymbol{M}}_1}$为各自参考系中的点坐标。

系统中的匹配节点订阅了每辆车的位姿、地图、GPS信息和以车辆ID标识的点云帧等信息，并将位姿和建图结果等转换到BS的全局坐标下。然后，各车辆的局部地图通过点云匹配算法计算${{\rm{RT}}}$矩阵进行地图合并。

在进行点云匹配时，匹配节点首先确定是否是第一辆无人驾驶车辆。如果是新车辆，则使用其GPS信息生成${{\rm{RT}}}$矩阵并存储；否则, 系统将使用GPS信息搜索当前全局地图来确定局部地图是否已经存储。系统将进一步检查匹配车辆的${{\rm{RT}}}$矩阵列表，如果不存在两者通过匹配算法生成的${{\rm{RT}}}$矩阵，系统使用点云匹配算法，如迭代最近点(iterative closest point，ICP)或正态分布变换(normal distributions transform，NDT)来计算车辆之间坐标转换关系，并存储${{\rm{RT}}}$矩阵。

此外，匹配的两帧点云在具有较大的平移和旋转值时，匹配算法可能需要较长时间才能收敛，甚至无法收敛。因此，本文提出了由粗到精的点云匹配方法。在粗匹配阶段，利用不同车辆的点云帧进行初步匹配。首先，使用快速点特征直方图(fast point feature histograms，FPFH)算法(Rusu等，2009)从点云中提取关键点和描述符，存储法线的相对方向和位于关键点的球面邻域内的点对之间的距离，再通过随机抽样一致算法(random sample consensus，RANSAC)(Holz等，2015)来估计关键点之间的点到点关系，得到粗略描述局部地图转换关系的${{\rm{RT}}}$矩阵，并以此作为精匹配阶段初始输入。在精匹配阶段，使用ICP算法进一步优化匹配结果，提高匹配精度。同时，计算匹配分数(Holz等，2015)来量化点云匹配的精准程度。匹配分数越小，匹配结果越精确。图 4显示了由粗到精匹配算法的有效性，其中ICP匹配、粗匹配、精匹配得分分别为19.6、3.2、1.7E-08。

使用无向图$\mathit{\boldsymbol{UCG}} = \{ \mathit{\boldsymbol{V}}, \mathit{\boldsymbol{R}}\} $来表示车辆构建点云地图的关系，其中$\mathit{\boldsymbol{V}}$表示车辆节点集，$\mathit{\boldsymbol{R}}$表示边集。对于每个节点$\mathit{\boldsymbol{v}} = \{ id, S\} \in \mathit{\boldsymbol{V}}$，它有一个对应的编号$id$和对应的权重$S$。车辆局部地图的累积误差随地图增大而增大, 因此以地图的大小作为可信度，即权重$S$。每条边${\mathit{\boldsymbol{r}}_{ij}} \in \mathit{\boldsymbol{R}}$表示车辆$i$与车辆$j$的局部地图之间存在一个重合区域。通过GPS可以粗略判断是否存在重合区域, 当两者通过地图匹配算法匹配成功时，则认为存在重合区域。为了有效和准确地合并地图，需要优先保留更可靠的局部地图信息。筛选重合区域的相对可信度$Rc$，保留相对可信度大的重合区域，即

$ R{c_{ij}} = \frac{{P{l_{ij}}}}{{R{l_{ij}}}} $

(3)

式中，${P{l_{ij}}}$为车辆$i$与车辆$j$重合区域部分的里程数，${R{l_{ij}}}$为车辆$i$起点到重合区域末端的相对里程数。

初始阶段，将用来存储已遍历节点的集合$\mathit{\boldsymbol{Se}}$初始化为空。1)选择集合$\mathit{\boldsymbol{V}} - \mathit{\boldsymbol{Se}}$中权值最小的节点$min $，并寻找节点集$\mathit{\boldsymbol{U}} \subseteq \mathit{\boldsymbol{V}} - \mathit{\boldsymbol{Se}}$，其每个节点均与$min $节点有边; 2)计算$min $和$\mathit{\boldsymbol{U}}$中所有节点对应的重合区域的相对可信度$Rc$，根据$Rc$由大到小进行排序; 3)对具有相同$Rc$的重合区域以区域大小为依据进行由小到大的重新排序；4)按照得到的顺序进行拼图，同时设置$\mathit{\boldsymbol{Se}} = \mathit{\boldsymbol{Se}} \cup \{ min \} $。重复步骤1)— 4)，直到$\mathit{\boldsymbol{Se}} = \mathit{\boldsymbol{V}}$时停止，即获得全局地图。该方法合并过程如图 5所示。图 5(a)是多个无人车辆对应的局部地图，车辆本身是无序的。随后，它被转换为图 5(b)所示的无向图$\mathit{\boldsymbol{UGG}}$。图 5(c)—(f)是实现一次循环的过程。图 5(g)则是进入下一次循环时的第一步。特别地，这里仅描述了一次循环的过程。

考虑车辆集合$\mathit{\boldsymbol{N}} = \{ 1, 2, 3, \cdots, N\} $，假设场景中只有一个基站$s$，基站有$M$个信道，则信道集合$\mathit{\boldsymbol{M}} = \{ 1, 2, 3, \cdots, M\} $。每辆车可以在决策周期内选择在本地执行计算任务或将任务通过某一信道卸载至边缘服务器。在每个决策周期内车辆集合不变，但不同决策周期内的车辆集合可能是不相同的。

车辆$n$的卸载决策表示为${a_n} \in \{ 0\} \cup \mathit{\boldsymbol{M}}$，所有车辆的决策集合$\mathit{\boldsymbol{a}} = \left\{ {{a_1}, {a_2}, \cdots, {a_N}} \right\}$，其中${{a_n}}$表示车辆$n$在本地执行计算任务，而${a_n} > 0$则表示车辆$n$通过信道${{a_n}}$将任务卸载至边缘。当${a_n} > 0$时，根据所有车辆的决策集合，可以计算出车辆$n$通过信道${{a_n}}$将任务进行卸载时所能获得的上行速率为

$ {r_n}(\mathit{\boldsymbol{a}}) = W \cdot {\log _2}\left({1 + \frac{{{q_n}{g_{n, s}}}}{{\omega + \sum\limits_{i \in N\backslash \left\{ n \right\}:{a_i} = {a_n}} {{q_i}} {g_{i, s}}}}} \right) $

(4)

式中，$W$是信道带宽，${{q_n}}$是车辆$n$的传输能量，${{g_{n, s}}}$是车辆$n$和基站$s$间的信道增益，$\omega $是背景噪声能量，“${i \in N\backslash \left\{ n \right\}:{a_i} = {a_n}}$”表示$i$属于$N$($n$除外)的前提下, ${{a_i} = {a_n}}$。目前本文只考虑无线干扰模型下的计算卸载问题。在该情况下，采用码分多址(code division multiple access，CDMA)信道访问方案即可允许多个车辆同时高效地共享同一频段资源。由式(4)可以看出，如果过多车辆选择同一信道将产生严重干扰，导致传输速率降低。

在决策周期内，车辆$n$的计算任务${\mathit{\boldsymbol{K}}_n} = \left({{b_n}, {d_n}} \right)$，其中${{b_n}}$表示输入数据的大小，${{d_n}}$表示完成任务${\mathit{\boldsymbol{K}}_n}$需要的中央处理单元(central process unit，CPU)周期总数。每个任务有两种可选计算模式：

1) 本地计算。当车辆$n$进行本地计算时，仅考虑延迟的影响，则其开销$C_n^l$由任务的执行时间$T_n^l$组成。设$f_n^m$(CPU周期/s)为车辆$n$的计算能力, 且每个车辆的计算能力可以不同。则车辆$n$完成任务${\mathit{\boldsymbol{K}}_n}$的时间为

$ T_n^l = \frac{{{d_n}}}{{f_n^m}} $

(5)

因此对本地计算来说，总开销为

$ C_n^l = T_n^l $

(6)

2) 卸载计算。当车辆$n$选择通过信道${{a_n}}$将任务进行卸载时，其开销$C_n^e(\mathit{\boldsymbol{a}})$由任务的执行时间$T_n^e(\mathit{\boldsymbol{a}})$和传输时间$T_n^{tr}(\mathit{\boldsymbol{a}})$两个部分组成。设边缘服务器的计算能力为${f_n^e}$，卸载的车辆均分其计算资源。则车辆$n$将任务${\mathit{\boldsymbol{K}}_n}$卸载到边缘时所需要的任务执行时间为

$ T_n^e(\mathit{\boldsymbol{a}}) = \frac{{\sum\limits_{i \in N} {{I_{\left\{ {{a_i} > 0} \right\}}}} {d_n}}}{{f_n^e}} $

(7)

式中，指示函数${I_{\left\{ A \right\}}}$用来表示事件$A$的真假，事件$A$为真时，${I_{\left\{ A \right\}}} = 1$；反之，${I_{\left\{ A \right\}}} = 0$。

车辆$n$将任务${\mathit{\boldsymbol{K}}_n}$卸载时所需要的传输时间为

$ T_n^{tr}(\mathit{\boldsymbol{a}}) = \frac{{{b_n}}}{{{r_n}(\mathit{\boldsymbol{a}})}} $

(8)

因此对卸载计算来说，总开销为

$ C_n^e(\mathit{\boldsymbol{a}}) = T_n^e(\mathit{\boldsymbol{a}}) + T_n^{tr}(\mathit{\boldsymbol{a}}) $

(9)

设${{a_n}}$为车辆$n$的卸载决策，${{a_{ - n}}}$为其他车辆的卸载决策。则最小开销问题可以被建模为策略博弈$\mathit{\boldsymbol{ \boldsymbol{\varGamma} }} = \left({\mathit{\boldsymbol{N}}, {{\left\{ {{\mathit{\boldsymbol{A}}_n}} \right\}}_{n \in N}}, {{\left\{ {{Z_n}} \right\}}_{n \in N}}} \right)$，车辆集合$\mathit{\boldsymbol{N}}$为参与者集，${{\mathit{\boldsymbol{A}}_n}}$为车辆$n$的策略集，开销函数${Z_n}\left({{a_n}, {a_{ - n}}} \right)$表示车辆$n$的成本函数，${{{\left\{ {{Z_n}} \right\}}_{n \in N}}}$为车辆$n$的开销函数，因此最小开销问题被建模为

$ \mathop {\min }\limits_{{a_n} \in \left\{ 0 \right\} \cup {A_n} \buildrel \Delta \over = \left\{ {0, 1, \cdots, M} \right\}} {Z_n}\left({{a_n}, {a_{ - n}}} \right)\quad \forall n \in \mathit{\boldsymbol{N}} $

(10)

同时根据式(6)和式(9)可得

$ {Z_n}\left({{a_n}, {a_{ - n}}} \right) = \left\{ {\begin{array}{*{20}{l}} {C_n^l}&{{a_n} = 0}\\ {C_n^e(\mathit{\boldsymbol{a}})}&{{a_n} > 0} \end{array}} \right. $

(11)

引入纳什均衡的定义：

定义1  如果所有玩家的决策集合${\mathit{\boldsymbol{a}}^ * } = \left({a_1^*, \cdots, a_N^*} \right)$达到纳什均衡，没有用户有动机改变策略，即

$ \begin{array}{*{20}{c}} {{Z_n}\left({a_n^*, a_{ - n}^*} \right) \le {Z_n}\left({{a_n}, a_{ - n}^*} \right)}\\ {\forall {a_n} \in {\mathit{\boldsymbol{A}}_n}, n \in \mathit{\boldsymbol{N}}} \end{array} $

(12)

根据纳什均衡的定义，当最小开销问题存在纳什均衡时，可以获得次优解。为了证明最小开销问题存在纳什均衡，引入势博弈的概念，如定义2所示。势博弈的特性之一是至少有一个纳什均衡且具有有限的改进特性。

定义2  一个博弈被称为势博弈，则其有势函数$P(\mathit{\boldsymbol{a}})$对每个$n \in \mathit{\boldsymbol{N}}, {a_{ - n}} \in \prod\limits_{i \ne n} {{A_i}} $，${a_n^\prime }$和${{a_n}}$都属于${{\mathit{\boldsymbol{A}}_n}}$，如果满足

$ {{Z_n}\left({a_n^\prime, {a_{ - n}}} \right) < {Z_n}\left({{a_n}, {a_{ - n}}} \right)} $

(13)

则有

$ {P\left({a_n^\prime, {a_{ - n}}} \right) < P\left({{a_n}, {a_{ - n}}} \right)} $

(14)

为了证明最小开销问题是势博弈，构造基于阈值的卸载函数，函数包括延迟约束和信号质量约束，定义如下：

1) 延迟约束。为了最小化延迟，仅当边缘计算的开销小于本地计算的开销时，用户$n$才进行卸载，即

$ T_n^e(\mathit{\boldsymbol{a}}) + T_n^{tr}(\mathit{\boldsymbol{a}}) < T_n^l $

(15)

2) 信号质量约束。为了保证接收信号质量，干扰噪声能量不能大于用户$n$的信号能量，即

$ \omega + \sum\limits_{i \in N\left\{ n \right\}:{a_i} = {a_n}} {{q_i}} {g_{i, s}} < {q_n}{g_{n, s}} $

(16)

此外，定义$C = {\varepsilon _1}T_n^l + {\varepsilon _2}{q_n}{g_{n, s}}$为计算卸载的阈值，当车辆$n$的阈值${C_n}$小于$C$时，则进行任务卸载；反之，则选择本地计算。阈值函数为

$ \begin{array}{l} {C_n} = {\varepsilon _1}\left({T_n^e(\mathit{\boldsymbol{a}}) + T_n^{tr}(\mathit{\boldsymbol{a}})} \right) + \\ {\kern 1pt} {\kern 1pt} {\kern 1pt} {\varepsilon _2}\left({\omega + \sum\limits_{i \in \mathit{\boldsymbol{N}}\backslash \{ n\} :{a_i} = {a_n}} {{q_i}{g_{i, s}}} } \right) \end{array} $

(17)

式中，$0 \le {\varepsilon _1}, {\varepsilon _2} \le 1$分别为两种约束下对应的权重且${\varepsilon _1} + {\varepsilon _2} = 1$。

因此构造势函数

$ \begin{array}{*{20}{c}} {P(a) = \frac{1}{2}\sum\limits_{i = 1}^N {\sum\limits_{i \ne n} {{C_n}} } {C_i}{I_{\left\{ {{a_n} = {a_i}} \right\}}}{I_{\left\{ {{a_n} > 0} \right\}}} + }\\ {\sum\limits_{i = 1}^N {{C_n}} C{I_{\left\{ {{a_n} = 0} \right\}}}} \end{array} $

(18)

根据定义2，要证明最小开销问题是势博弈，有如下3种情况：

1) 假设当前的决策为${a_k} = 0$，车辆需要将决策从${a_k} = 0$更新到$a_k^\prime > 0$。基于${Z_n}\left({a_k^\prime, {a_{ - k}}} \right) < {Z_n}\left({{a_k}, {a_{ - k}}} \right)$，同时根据卸载的阈值定义有$\sum\limits_{i \ne k} {{C_i}} {I_{\left\{ {{a_i} = a_k^\prime } \right\}}} < C$，因此

$ \begin{array}{*{20}{c}} {P\left({a_k^\prime, {a_{ - k}}} \right) - P\left({{a_k}, {a_{ - k}}} \right) = }\\ {\frac{1}{2}{C_k}\sum\limits_{i \ne k} {{C_i}} {I_{\left\{ {{a_i} = a_k^\prime } \right\}}} + \frac{1}{2}\sum\limits_{k \ne i} {{C_k}} {C_i}{I_{\left\{ {a_k^\prime = {a_i}} \right\}}} - }\\ {{C_k}C < 0} \end{array} $

(19)

2) 假设当前的决策为${a_k} > 0$，车辆需要将决策从${a_k} > 0$更新到$a_k^\prime = 0$。与情况1)类似，可以得到当${Z_n}\left({a_k^\prime, {a_{ - k}}} \right) < {Z_n}\left({{a_k}, {a_{ - k}}} \right)$时，$P\left({a_k^\prime, {a_{ - k}}} \right) < P\left({{a_k}, {a_{ - k}}} \right)$。

3) 假设当前的决策为${a_k} > 0$，车辆需要将决策从${a_k} > 0$更新到$a_k^\prime > 0$，且${a_k} \ne a_k^\prime $。因为车辆进行决策更新前后均选择进行卸载，因此$\sum\limits_{i \in \mathit{\boldsymbol{N}}} {{I_{\left\{ {{a_i} > 0} \right\}}}} $不变，所以有$T_{n}^{e}(a)$不变。则${Z_n}\left({a_k^\prime, {a_{ - k}}} \right)$和${Z_n}\left({{a_k}, {a_{ - k}}} \right)$的差异仅与信道干扰相关，同时函数$W \cdot {\log _2}(x)$随$x$单调递增。所以基于${Z_n}\left({a_k^\prime, {a_{ - k}}} \right) < {Z_n}\left({{a_k}, {a_{ - k}}} \right)$有

$ \sum\limits_{i \in \mathit{\boldsymbol{N}}\backslash \{ k\} :{a_i} = {a^\prime }k} {{q_i}{g_{i, s}}} < \sum\limits_{i \in \mathit{\boldsymbol{N}}\backslash \{ k\} :{a_i} = {a_k}} {{q_i}{g_{i, s}}} $

(20)

同时当$\sum\limits_{i \in \mathit{\boldsymbol{N}}} {{I_{\left\{ {{a_i} > 0} \right\}}}} $不变时，${{C_i}}$与$\sum\limits_{j \in \mathit{\boldsymbol{N}}\backslash \{ i\} :{a_j} = {a_i}} {{q_j}{g_{j, s}}} $正相关，因此

$ \begin{array}{*{20}{c}} {P\left({a_k^\prime, {a_{ - k}}} \right) - P\left({{a_k}, {a_{ - k}}} \right) = }\\ {\frac{1}{2}{C_k}\sum\limits_{i \ne k} {{C_i}} {I_{\left\{ {{a_i} = a_k^\prime } \right\}}} + \frac{1}{2}\sum\limits_{k \ne i} {{C_k}} {C_i}{I_{\left\{ {a_k^\prime = {a_i}} \right\}}} - }\\ {\frac{1}{2}{C_k}\sum\limits_{i \ne k} {{C_i}} {I_{\left\{ {{a_i} = {a_k}} \right\}}} - \frac{1}{2}\sum\limits_{k \ne i} {{C_k}} {C_i}{I_{\left\{ {{a_k} = {a_i}} \right\}}} = }\\ {{C_k}\left({\sum\limits_{i \ne k} {{C_i}} {I_{\left\{ {{a_i} = a_k^\prime } \right\}}} - \sum\limits_{i \ne k} {{C_i}} {I_{\left\{ {{a_i} = {a_k}} \right\}}}} \right) < 0} \end{array} $

(21)

综合上述，最小化开销卸载博弈是势博弈，得证。

基于势博弈的卸载算法流程:

initialization

while ${{\rm{RT}}}$U exists do

    for each $n \in \mathit{\boldsymbol{N}}$ do

    compute ${C_n}$

    compute ${b_n}(t)$

    if ${C_n} > C$ then

        ${b_n}(t) = 0$

    if ${b_n}(t) \ne {a_n}(t)$ then

        send ${{\rm{RT}}}$U

        if receive UD then

            ${a_n}(t + 1) = {b_n}(t)$

        else

            ${a_n}(t + 1) = {a_n}(t)$

      else

        ${a_n}(t + 1) = {a_n}(t)$

end

首先，每辆车$n$的卸载决策${a_n}(t)$初始化为0，当边缘仍能接收到请求更新信息(request-to-update，${{\rm{RT}}}$U)时，车辆对当前的情况进行决策更新判断。在每个决策时隙$t$中，每辆车计算${C_n}$和最佳响应${{b_n}(t)}$，若不满足卸载条件则将${{b_n}(t)}$设置为0。为了加快算法的收敛速度，这里引入$\alpha - Nash{\rm{ }}$最佳响应动态的概念(Awerbuch等，2008)。因此

$ \begin{array}{*{20}{c}} {{b_n}(t) = \left\{ {\tilde a:\tilde a = \arg \mathop {\min }\limits_{a \in {\mathit{\boldsymbol{A}}_n}} {Z_n}\left({a, {a_{ - n}}(t)} \right)} \right.{\rm{ and }}}\\ {\left. {{Z_n}\left({\tilde a, {a_{ - n}}(t)} \right) \le (1 - \alpha){Z_n}\left({{a_n}(t), {a_{ - n}}(t)} \right)} \right\}}\\ {0 \le \alpha \le 1} \end{array} $

当获得的${{b_n}(t)}$和当前的决策${{a_n}(t)}$不同时，车辆发送${{\rm{RT}}}$U以竞争更新决策。在每一时隙中边缘服务器仅选择一辆车发送更新决策信息(update decision，UD)。收到UD的车辆更新自己在下一时隙中的初始决策${{a_n}(t + 1)}$，未收到的车辆则不进行决策更新。当获得的${{b_n}(t)}$和当前的决策${{a_n}(t)}$相同时，车辆同样不进行决策更新。

在仿真场景中，基站$s$的覆盖区域设置为50 m(Quek等，2013)，并假定车辆随机地散落在覆盖区域内。其中，基站$s$包括$M{\rm{ = 5}}$个信道，信道带宽$W$=5 MHz，传输能量${q_n}$=0.1 W，背景噪声$\omega $=－100 dBm(m表示绝对值)，车辆$n$和基站$s$间的信道增益${g_{n, s}} = l_{n, s}^{ - \beta }$(${l_{n, s}}$是用户$n$与基站的距离，$\beta $=4是路径损耗因子)。假定每辆车需要调度的任务相同，且计算任务输入数据的大小${b_n}$=5 MB，运算需要的CPU周期数${d_n}$=3 000 MHz。每辆车的计算能力$f_n^m$在[0.5, 1]GHz范围内进行随机设置，基站的计算能力为$f_n^e$=10 GHz。

本文使用平均时隙数量和平均系统开销作为评估指标，以验证算法的收敛速度和减少系统开销的效率，实验结果如图 6和图 7所示。本实验暂不考虑信号能量约束，$\varepsilon_{1}$的值被设置为1。为了寻找一个合适的$\alpha $保证算法效率，实验中$\alpha $分别设置为0.4, 0.6, 0.8, 1，在车辆数量$n$=10, 20, …, 50情况下重复实验100次。从图 6可以看出，在不同车辆数量下，随着$\alpha $增大，收敛需要的平均时隙数量增大，即收敛速度降低。图 7则表示了在不同车辆数量下，较大的$\alpha $下通常得到的平均系统开销更小，即减少系统开销的效率更高。为了在加快收敛速度的情况下保证减少系统开销的效率，$\alpha $设置为0.8。此外，从图 6和图 7中可以看出算法具有较快的收敛速度并且能很好地适应多车的不同规模。

实验使用4辆硬件配置相同的电动巡逻车和3个基站实现道路测试，并与单车建图结果进行对比。

测试场景路段约1.49 km，包括转弯、直行和变道，如图 8所示。单车建图时，仅使用本地车载单元进行计算，沿着轨迹${\rm{A - B - C - D - E - F - G - H - I - J - K - L - I - H - A - D}}$进行建图。在多车场景中，由于实际车辆数量有限，以基站为中心将测试区域分为3个部分来模拟9辆车的SLAM效果，分别为${\rm{A - B - C - D - A}}、{\rm{A - D - E - F - G - H - A}}、{\rm{H - I - L - K - J - I - H}}$，并保证每个部分内至少3辆车同时运行。每辆车上均安装一台Velodyne HDL-32激光雷达扫描仪和一系列惯性测量单元设备。使用搭载ARM A57 qual-core的Tegra X2和搭载Intel Xeon Platinum 8168的服务器分别作为车载单元和边缘服务器。Tegra X2通过无线网桥与边缘服务器通信，详细的硬件规格列于表 1。为了更快地执行在边缘端，边缘服务器也部署了SLAM算法，因此在运行时平台之间只需传输传感器数据。

激光雷达SLAM构建的3维地图如图 9所示。其中，图 9(a)为单车SLAM构建的3维地图，图 9(b)则是基于边缘计算多车协同的建图效果。可以发现，单车建图因为在连续点云帧匹配过程中累积误差，从而导致偏移越来越大；而协同建图各车辆路程相对较短，累积误差相对更小，能够通过边缘服务器，利用地图合并方法快速合成相比于单车更精确的地图，且与真实环境地图更接近。

图 10展示了协同建图、单车建图以及${{\rm{RTK}}}$这三者的车辆行驶轨迹。${{\rm{RTK}}}$是由差分全球地位系统(difference global positioning system，DGPS)获得的地理测量轨迹。DGPS的精度可以在分米以内，所以${{\rm{RTK}}}$测量的数据可以作为轨迹的真值来评估其他情况下轨迹定位精度。从图 10中对比发现，单车定位建图性能更差，与${{\rm{RTK}}}$的偏差更大。其原因是单车车载单元受到计算资源限制，无法及时修正累积误差。而基于边缘计算的多车定位建图与${{\rm{RTK}}}$的轨迹基本吻合，定位结果误差较小。

从图 11中可以看到更多关于定位误差的细节。相比于协同建图，单车SLAM的横、纵向误差波动更明显，且在转弯处更容易出现漂移。这是因为此时点云的特征快速变化，更容易积累里程估计误差。而在A、H点处(图 11中协同建图误差的两大高峰)，由于缺少协同建图车辆的相关的转弯轨迹信息，导致协同建图后的轨迹误差也相对较高，甚至高于单车建图。但当有足够多的车辆覆盖弯道信息时，这种误差将会减小。与单车SLAM相比，基于边缘计算的多车协同SLAM的横向定位和纵向定位的平均精度分别提高了6.0倍(从3.604 m降低至0.599 m)和3.9倍(从2.681 m降低至0.680 m)。在最坏情况下，其横向精度提高了1.7倍(从23.321 5 m降低至13.757 4 m)，纵向精度提高了1.6倍(从13.510 3 m降低至8.554 6 m)。相比于单车建图，基于边缘计算的协同SLAM算法可以获得更好的性能，更准确的建图结果。

为了解决多车构建高精度地图与定位问题，提出了一种基于边缘计算的多车协同激光雷达SLAM算法。通过将多无人驾驶车辆之间的计算卸载决策问题建模为多用户计算势博弈问题, 设计实现了基于势博弈的卸载算法, 在模型具有纳什均衡的基础上实现任务调度。此外，基于相对可信度实现了地图合并，这种方法优先保留了相对可信度高的局部地图以提高整体建图的准确度。实验结果表明，基于博弈论的调度算法可以实现卓越的计算卸载性能。在定位方面，与单车建图结果相比，基于边缘计算卸载的协同SLAM算法也更接近${{\rm{RTK}}}$的实验结果，获得更精准的定位数据。

但是本文方法依然存在以下不足：在线调度策略仅考虑了延迟和信号质量的约束，忽略了能耗的影响。此外，调度策略考虑的是静态场景，缺少对实际场景下车辆的运动预测建模。今后将进一步探索能耗因素和车辆移动性对在线调度策略的影响，完善调度框架结构，使得方法更符合实际，以期得到更好的质量性能。