基于輕量化定位的地下停車場導航路徑優化研究

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算法和定向天線可以通過一個傳感器將移動端位置準確定位，該改進算法成立需要配備以下前提條件：①定位介質可以計算出移動端到傳感器間的距離；②可以獲得移動端與傳感器的角度信息?；谝韵录僭O該定位前提可以得到滿足：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.