基于轻量化定位的地下停车场导航路径优化研究

0 引言

地下停车定位与导航系统有助于解决我国停车难问题。根据2021年10月12日发布的统计数据显示，我国机动车保有量达3.90亿辆，其中汽车为2.97亿辆①。面对机动车保有量的增长而产生的大量停车需求，公共场所多采取地面停车和地下停车两种措施去解决该问题。地面停车由于受到地面空间狭小、噪音产生等因素的限制，并不能完全满足停车需求，公共场所多采用修建地下停车场的方式来缓解“停车难”问题。

在自动化、半自动化停车场尚未普及的情况下，自行式地下停车场仍是用于解决停车问题的主要手段，但地下停车环境常会面临GPS信号弱的情况，无法像室外环境一样使用GPS进行导航，这使得车辆在地下环境寻找车位会花费大量时间且效率低下，有时甚至会造成地下环境交通阻塞，给人们的生产和生活造成诸多不便。国内大多使用的是LED电子屏等视觉诱导对车辆停车进行信息展示，但视觉诱导所能展示的信息也有限且容易分散驾驶员注意力从而使行车危险性提升，车辆在地下环境语音诱导主要是依靠传感器进行，而使用TOA算法可以解决地下环境定位问题，但使用TOA算法三边定位存在成本较高、定位效率低、误差较大等问题。在此背景下，本文研究在TOA算法三边定位的基础上对地下停车环境中对导航定位系统进行轻量化处理，寻求更便利、快捷的定位和导航解决方案。

1 文献综述

室内定位方法总体上由定位算法和定位介质构成，其中定位算法包括TOA、TDOA、AOA、RSSI、位置指纹定位等算法技术；定位介质包括红外线、可见光、激光雷达、超声波、Wi-Fi室内定位、RFID室内定位、蓝牙室内定位、Li-Fi室内定位、ZigBee室内定位、蜂窝网定位、UWB室内定位、伪卫星定位技术、视觉定位技术、惯性导航定位技术和地磁等，当前对于室内定位算法的研究，多集中于多种算法的结合应用和算法改进上，如TDOA+AOA，TOA+RSS，RSS+AOA，AOA+TOF，TDOA算法改进等，而室内导航定位介质应用主要集中在Wi-Fi，UWB，蓝牙，以及各种介质的混合使用方面。这些研究对于定位精度或定位效率提升有不同程度帮助，但由于研究背景大多以室内环境为主，并不完全适用于地下停车场环境，因此，总体而言定位算法和定位介质在地下停车场的研究相对较薄弱。本研究旨在弥补此领域的研究，并有效针对地下停车场环境中惯常使用TOA算法三边定位成本高、误差大、效率低的问题，在前人研究的基础上对定位算法进行了轻量化处理，并使用Dijkstra算法对地下停车场进行固定路线的路径规划，通过固定路线进行定位导航可以使导航定位系统更加适应地下停车场环境。（表1）

表1 定位介质和定位算法

2 定位算法模型的构建

2.1 基于轻量化定位的TOA算法构建原理

现有地下停车定位及导航研究多利用已成熟的室内定位方法进行，如利用Wi-Fi和位置指纹定位的方式[1]，但地下停车场与普通室内导航存在较大差异：一方面，地下停车环境中的车位或不可通行路段具有较低的精准定位价值，而真正具备定位价值的部分所占比例相对较少，因此，使用TOA、TDOA等算法时经常出现进行无效运算的情况；另一方面，使用AOA算法获取角度信息要求天线数量大于路径数，通常室内存在6～8个主要多径信号，因此传感器需要很多根天线，这对目前的商业传感器也是不行的[2]，所以使用室内定位进行研究时能够兼容地下停车环境，但容易出现成本上升、误差较大和计算过程冗余等问题。

本文研究对地下停车场平面图进行拓扑处理，将地下停车场内的道路拓扑为一条矢量线称为道路线，将道路上的车辆拓扑为一个点称为移动端，并将道路的交点、车位拓扑为节点，其中道路的交点拓扑成的点称为道路交点节点，车位拓扑成的点称为车位坐标节点，道路交点节点和车位坐标节点统称为道路节点。由于定位系统误差，车位拓扑点为投影到道路线上的中心点等影响因素存在，进行路线规划时是将车诱导到车位附近，然后通过语音提示引导车辆到达指定目标附近并提示车位是位于道路左侧或右侧，再通过图像或灯光等视觉方法将车辆引导至指定位置。

轻量化拓扑处理方法受相关学者研究启发而得。田增山（2019）等提出基于CFR的角度/距离联合单站定位，利用直射路径分辨算法在获得AOA和TOA二维信息的基础上，通过AOA和TOA信息进行聚类来区分路径，但是此种方法对于定位精度和设备运算能力的要求较高。同时，采用离群点检测算法有助于提高聚类的准确性，也可以利用权值来选取直射路径，但是此种方法仍然容易出现因仪器精度、环境中噪音等因素引起的较大误差[2]，本文提出的改进后TOA算法在田增山（2019）提出的算法基础上对其进行了轻量化处理，根据TOA算法获取车辆与传感器的距离，再通过对道路、车位和车辆的拓扑处理来确定直射路径，最后通过定向天线确定车辆同传感器的相对位置来进行位置定位，减少了误差出现的可能性，提高了算法的运行效率，使其更加适应地下停车环境。

2.2 定位算法模型优化

2.2.1 TOA算法三边定位

TOA算法主要是通过接收信号在传感器和移动端之间的到达时间来转换为距离进行定位的。在以往研究中，室内定位通常需要安装三个传感器，其测得与移动端的距离分别为r1，r2，r3，以各自基站为圆心测量距离为半径，绘制三个圆，其交点即为移动端的位置。图1（a）为三边定位模型。

图1 TOA算法三边定位

TOA算法三边定位计算步骤：

传感器的位置坐标已知分别为（x1，y1），（x2，y2），（x3，y3），设移动端的位置坐标为（x，y），

其中c为电磁波传播速度，t1、t2、t3为移动端发出的信号到达传感器1、2、3的时间，根据式（1）可求得移动端的位置坐标。

由于TOA三边定位法需要三个以上的传感器获取与移动端的距离才能实现位置坐标的定位，所以进行位置定位时成本相对较高，而且TOA定位算法会因为多径效应、反射和噪声等干扰而对距离计算的精确度造成较大的影响[3]。三个传感器的距离计算会产生三项误差，而该多项误差会在平面上形成一个误差区域，使得系统难以确定移动端的位置（见图1（b）中阴影区域），因此该方法存在一定导航偏差。

2.2.2 基于改进后TOA定位算法优化

在地下停车环境中，可以根据地下停车场实际情况对平面图进行拓扑，将道路、车位和车辆都抽象到一维坐标轴上，利用TOA算法和定向天线可以通过一个传感器将移动端位置准确定位，该改进算法成立需要配备以下前提条件：①定位介质可以计算出移动端到传感器间的距离；②可以获得移动端与传感器的角度信息。基于以下假设该定位前提可以得到满足：1）当车辆进入接收端定位范围时，根据TOA算法可以确定移动端与传感器间的距离。2）车辆沿道路固定方向行进，基于传感器测出在线性道路上车辆位置，且为传感器与线性道路信号交接点。3）根据定向天线得出的角度信息从而对车辆所处的位置进行判断。

改进后TOA算法计算步骤：

传感器的位置坐标已知分别为（x，y），设移动端位置坐标为（x1，y），

其中c为电磁波传播速度，t为移动端发出的信号到达传感器的时间。此方程可以解出x1，根据x1可以得知移动端位于图2（a）中的虚线上，由于移动端沿规划的固定路线道路拓扑线上运动，可以得出移动端位于位置1或位置2处，最后根据定向天线确定移动端位置为位置1处，移动端位置判断逻辑如图2（b）所示。

图2 移动端位置判断逻辑图

3 导航路径模型设计

3.1 泊位分派设计

本文运用Dijkstra算法对轻量化的车位定位进行最短路径计算，然后对出口到车位距离进行排序记录，当车辆请求泊位时根据该排序根据距离从小到大进行分配，从而避免在导航过程中由于动态规划而产生大规模低效率计算。

Dijkstra算法步骤：①给Vs以P标号，P（Vs）=0，其余各节点均给T标号，T（Vi）=+∞；②若Vi点刚得到P标号，考虑这样的点Vj，（Vi，Vj）属于E，且Vj为T标号，对Vj的T标号进行如下的更改：T（Vj）=min[T（Vj），P（Vi）+Lij]；③比较所有具有T标号的点，把最小者改为P标号，即P（Vi）=min[T（Vi）]，当同时两个以上最小者，可同时改为P标号；若全部点均为P标号则停止。其中Vs即为地下停车场入口，Vi为道路交点节点和车位节点，将从地下停车场入口到道路节点，道路节点之间以及道路节点到目标车位之间根据道路长度设置路权，T标号（tentative label）表示从Vs出发到Vi的估计最短路权的上界，是临时标号，P标号（permanent label）表示从Vs出发到Vi的估计最短路权，是永久标号。每一步要将某一节点的T标号改为P标号，若停车场的道路节点数为n，则最多经n-1步骤可得从始点到终点的最短路径。

3.2 路线规划设计

通过泊位分配系统可以确定目标车位标号和位置，只需确定车库入口到指定车位的最短路径，便可对车辆进行路径导航。实际操作时可以通过提前使用Dijkstra算法分别计算出停车场各入口到各车位的最短路径，并将所得结果储存到系统中，之后直接通过分派的车位编号为车辆匹配最短路径，然后利用改进后TOA算法为车辆进行实时定位导航并进行语音提醒，同时将分配的车位状态改为非空车位，可以节省在导航过程中所需时间，也可以提高导航效率。

4 结论

本文利用TOA和定向天线对导航定位系统进行了轻量化处理，与传统的TOA算法相比，改进后TOA定位算法实现了单传感器对用户进行位置定位，使导航成本降低。同时本文方法相对于TOA算法三边定位误差产生的可能性降低，提升了定位的准确性，而且由于计算的简化使得导航的效率也得到一定程度的提升。使用Dijkstra算法提前计算出泊位距停车场出入口（楼梯口、电梯口等）距离并将结果汇总到系统中，首先根据距离由小到大为用户分配泊位，再根据分配的泊位利用路线规划系统为用户匹配最短路径，这样既有利于提高用户的停车效率，也为使用该地下导航定位系统的用户带来更好的使用体验。

由于现在地下停车场自动停车研究方向多以机械式停车场为主，所以本文提出的定位算法并未直接将车辆引导到车位，而是将车辆引导到车位附近的空车位，由车辆驾驶员自主泊车。此外，本文的导航定位系统使用范围具有局限性，目前适用于解决路径相对固定环境的导航定位问题，在后续研究中结合其他研究进一步模拟并测试该方法。

注释：

①新华社.《3.90亿辆、4.76亿人！公安部发布最新全国机动车和驾驶人数据》.2021年10月12日.[EB/OL].http://www.gov.cn/shuju/2021-10/12/content_5642074.htm.