基于輕量化定位的地下停車場(chǎng)導(dǎo)航路徑優(yōu)化研究

0 引言

地下停車定位與導(dǎo)航系統(tǒng)有助于解決我國(guó)停車難問(wèn)題。根據(jù)2021年10月12日發(fā)布的統(tǒng)計(jì)數(shù)據(jù)顯示，我國(guó)機(jī)動(dòng)車保有量達(dá)3.90億輛，其中汽車為2.97億輛①。面對(duì)機(jī)動(dòng)車保有量的增長(zhǎng)而產(chǎn)生的大量停車需求，公共場(chǎng)所多采取地面停車和地下停車兩種措施去解決該問(wèn)題。地面停車由于受到地面空間狹小、噪音產(chǎn)生等因素的限制，并不能完全滿足停車需求，公共場(chǎng)所多采用修建地下停車場(chǎng)的方式來(lái)緩解“停車難”問(wèn)題。

在自動(dòng)化、半自動(dòng)化停車場(chǎng)尚未普及的情況下，自行式地下停車場(chǎng)仍是用于解決停車問(wèn)題的主要手段，但地下停車環(huán)境常會(huì)面臨GPS信號(hào)弱的情況，無(wú)法像室外環(huán)境一樣使用GPS進(jìn)行導(dǎo)航，這使得車輛在地下環(huán)境尋找車位會(huì)花費(fèi)大量時(shí)間且效率低下，有時(shí)甚至?xí)斐傻叵颅h(huán)境交通阻塞，給人們的生產(chǎn)和生活造成諸多不便。國(guó)內(nèi)大多使用的是LED電子屏等視覺(jué)誘導(dǎo)對(duì)車輛停車進(jìn)行信息展示，但視覺(jué)誘導(dǎo)所能展示的信息也有限且容易分散駕駛員注意力從而使行車危險(xiǎn)性提升，車輛在地下環(huán)境語(yǔ)音誘導(dǎo)主要是依靠傳感器進(jìn)行，而使用TOA算法可以解決地下環(huán)境定位問(wèn)題，但使用TOA算法三邊定位存在成本較高、定位效率低、誤差較大等問(wèn)題。在此背景下，本文研究在TOA算法三邊定位的基礎(chǔ)上對(duì)地下停車環(huán)境中對(duì)導(dǎo)航定位系統(tǒng)進(jìn)行輕量化處理，尋求更便利、快捷的定位和導(dǎo)航解決方案。

1 文獻(xiàn)綜述

室內(nèi)定位方法總體上由定位算法和定位介質(zhì)構(gòu)成，其中定位算法包括TOA、TDOA、AOA、RSSI、位置指紋定位等算法技術(shù)；定位介質(zhì)包括紅外線、可見(jiàn)光、激光雷達(dá)、超聲波、Wi-Fi室內(nèi)定位、RFID室內(nèi)定位、藍(lán)牙室內(nèi)定位、Li-Fi室內(nèi)定位、ZigBee室內(nèi)定位、蜂窩網(wǎng)定位、UWB室內(nèi)定位、偽衛(wèi)星定位技術(shù)、視覺(jué)定位技術(shù)、慣性導(dǎo)航定位技術(shù)和地磁等，當(dāng)前對(duì)于室內(nèi)定位算法的研究，多集中于多種算法的結(jié)合應(yīng)用和算法改進(jìn)上，如TDOA+AOA，TOA+RSS，RSS+AOA，AOA+TOF，TDOA算法改進(jìn)等，而室內(nèi)導(dǎo)航定位介質(zhì)應(yīng)用主要集中在Wi-Fi，UWB，藍(lán)牙，以及各種介質(zhì)的混合使用方面。這些研究對(duì)于定位精度或定位效率提升有不同程度幫助，但由于研究背景大多以室內(nèi)環(huán)境為主，并不完全適用于地下停車場(chǎng)環(huán)境，因此，總體而言定位算法和定位介質(zhì)在地下停車場(chǎng)的研究相對(duì)較薄弱。本研究旨在彌補(bǔ)此領(lǐng)域的研究，并有效針對(duì)地下停車場(chǎng)環(huán)境中慣常使用TOA算法三邊定位成本高、誤差大、效率低的問(wèn)題，在前人研究的基礎(chǔ)上對(duì)定位算法進(jìn)行了輕量化處理，并使用Dijkstra算法對(duì)地下停車場(chǎng)進(jìn)行固定路線的路徑規(guī)劃，通過(guò)固定路線進(jìn)行定位導(dǎo)航可以使導(dǎo)航定位系統(tǒng)更加適應(yīng)地下停車場(chǎng)環(huán)境。（表1）

表1 定位介質(zhì)和定位算法

2 定位算法模型的構(gòu)建

2.1 基于輕量化定位的TOA算法構(gòu)建原理

現(xiàn)有地下停車定位及導(dǎo)航研究多利用已成熟的室內(nèi)定位方法進(jìn)行，如利用Wi-Fi和位置指紋定位的方式[1]，但地下停車場(chǎng)與普通室內(nèi)導(dǎo)航存在較大差異：一方面，地下停車環(huán)境中的車位或不可通行路段具有較低的精準(zhǔn)定位價(jià)值，而真正具備定位價(jià)值的部分所占比例相對(duì)較少，因此，使用TOA、TDOA等算法時(shí)經(jīng)常出現(xiàn)進(jìn)行無(wú)效運(yùn)算的情況；另一方面，使用AOA算法獲取角度信息要求天線數(shù)量大于路徑數(shù)，通常室內(nèi)存在6～8個(gè)主要多徑信號(hào)，因此傳感器需要很多根天線，這對(duì)目前的商業(yè)傳感器也是不行的[2]，所以使用室內(nèi)定位進(jìn)行研究時(shí)能夠兼容地下停車環(huán)境，但容易出現(xiàn)成本上升、誤差較大和計(jì)算過(guò)程冗余等問(wèn)題。

本文研究對(duì)地下停車場(chǎng)平面圖進(jìn)行拓?fù)涮幚?，將地下停車?chǎng)內(nèi)的道路拓?fù)錇橐粭l矢量線稱為道路線，將道路上的車輛拓?fù)錇橐粋€(gè)點(diǎn)稱為移動(dòng)端，并將道路的交點(diǎn)、車位拓?fù)錇楣?jié)點(diǎn)，其中道路的交點(diǎn)拓?fù)涑傻狞c(diǎn)稱為道路交點(diǎn)節(jié)點(diǎn)，車位拓?fù)涑傻狞c(diǎn)稱為車位坐標(biāo)節(jié)點(diǎn)，道路交點(diǎn)節(jié)點(diǎn)和車位坐標(biāo)節(jié)點(diǎn)統(tǒng)稱為道路節(jié)點(diǎn)。由于定位系統(tǒng)誤差，車位拓?fù)潼c(diǎn)為投影到道路線上的中心點(diǎn)等影響因素存在，進(jìn)行路線規(guī)劃時(shí)是將車誘導(dǎo)到車位附近，然后通過(guò)語(yǔ)音提示引導(dǎo)車輛到達(dá)指定目標(biāo)附近并提示車位是位于道路左側(cè)或右側(cè)，再通過(guò)圖像或燈光等視覺(jué)方法將車輛引導(dǎo)至指定位置。

輕量化拓?fù)涮幚矸椒ㄊ芟嚓P(guān)學(xué)者研究啟發(fā)而得。田增山（2019）等提出基于CFR的角度/距離聯(lián)合單站定位，利用直射路徑分辨算法在獲得AOA和TOA二維信息的基礎(chǔ)上，通過(guò)AOA和TOA信息進(jìn)行聚類來(lái)區(qū)分路徑，但是此種方法對(duì)于定位精度和設(shè)備運(yùn)算能力的要求較高。同時(shí)，采用離群點(diǎn)檢測(cè)算法有助于提高聚類的準(zhǔn)確性，也可以利用權(quán)值來(lái)選取直射路徑，但是此種方法仍然容易出現(xiàn)因儀器精度、環(huán)境中噪音等因素引起的較大誤差[2]，本文提出的改進(jìn)后TOA算法在田增山（2019）提出的算法基礎(chǔ)上對(duì)其進(jìn)行了輕量化處理，根據(jù)TOA算法獲取車輛與傳感器的距離，再通過(guò)對(duì)道路、車位和車輛的拓?fù)涮幚韥?lái)確定直射路徑，最后通過(guò)定向天線確定車輛同傳感器的相對(duì)位置來(lái)進(jìn)行位置定位，減少了誤差出現(xiàn)的可能性，提高了算法的運(yùn)行效率，使其更加適應(yīng)地下停車環(huán)境。

2.2 定位算法模型優(yōu)化

2.2.1 TOA算法三邊定位

TOA算法主要是通過(guò)接收信號(hào)在傳感器和移動(dòng)端之間的到達(dá)時(shí)間來(lái)轉(zhuǎn)換為距離進(jìn)行定位的。在以往研究中，室內(nèi)定位通常需要安裝三個(gè)傳感器，其測(cè)得與移動(dòng)端的距離分別為r1，r2，r3，以各自基站為圓心測(cè)量距離為半徑，繪制三個(gè)圓，其交點(diǎn)即為移動(dòng)端的位置。圖1（a）為三邊定位模型。

圖1 TOA算法三邊定位

TOA算法三邊定位計(jì)算步驟：

傳感器的位置坐標(biāo)已知分別為（x1，y1），（x2，y2），（x3，y3），設(shè)移動(dòng)端的位置坐標(biāo)為（x，y），

其中c為電磁波傳播速度，t1、t2、t3為移動(dòng)端發(fā)出的信號(hào)到達(dá)傳感器1、2、3的時(shí)間，根據(jù)式（1）可求得移動(dòng)端的位置坐標(biāo)。

由于TOA三邊定位法需要三個(gè)以上的傳感器獲取與移動(dòng)端的距離才能實(shí)現(xiàn)位置坐標(biāo)的定位，所以進(jìn)行位置定位時(shí)成本相對(duì)較高，而且TOA定位算法會(huì)因?yàn)槎鄰叫?yīng)、反射和噪聲等干擾而對(duì)距離計(jì)算的精確度造成較大的影響[3]。三個(gè)傳感器的距離計(jì)算會(huì)產(chǎn)生三項(xiàng)誤差，而該多項(xiàng)誤差會(huì)在平面上形成一個(gè)誤差區(qū)域，使得系統(tǒng)難以確定移動(dòng)端的位置（見(jiàn)圖1（b）中陰影區(qū)域），因此該方法存在一定導(dǎo)航偏差。

2.2.2 基于改進(jìn)后TOA定位算法優(yōu)化

在地下停車環(huán)境中，可以根據(jù)地下停車場(chǎng)實(shí)際情況對(duì)平面圖進(jìn)行拓?fù)?，將道路、車位和車輛都抽象到一維坐標(biāo)軸上，利用TOA算法和定向天線可以通過(guò)一個(gè)傳感器將移動(dòng)端位置準(zhǔn)確定位，該改進(jìn)算法成立需要配備以下前提條件：①定位介質(zhì)可以計(jì)算出移動(dòng)端到傳感器間的距離；②可以獲得移動(dòng)端與傳感器的角度信息?；谝韵录僭O(shè)該定位前提可以得到滿足：1）當(dāng)車輛進(jìn)入接收端定位范圍時(shí)，根據(jù)TOA算法可以確定移動(dòng)端與傳感器間的距離。2）車輛沿道路固定方向行進(jìn)，基于傳感器測(cè)出在線性道路上車輛位置，且為傳感器與線性道路信號(hào)交接點(diǎn)。3）根據(jù)定向天線得出的角度信息從而對(duì)車輛所處的位置進(jìn)行判斷。

改進(jìn)后TOA算法計(jì)算步驟：

傳感器的位置坐標(biāo)已知分別為（x，y），設(shè)移動(dòng)端位置坐標(biāo)為（x1，y），

其中c為電磁波傳播速度，t為移動(dòng)端發(fā)出的信號(hào)到達(dá)傳感器的時(shí)間。此方程可以解出x1，根據(jù)x1可以得知移動(dòng)端位于圖2（a）中的虛線上，由于移動(dòng)端沿規(guī)劃的固定路線道路拓?fù)渚€上運(yùn)動(dòng)，可以得出移動(dòng)端位于位置1或位置2處，最后根據(jù)定向天線確定移動(dòng)端位置為位置1處，移動(dòng)端位置判斷邏輯如圖2（b）所示。

圖2 移動(dòng)端位置判斷邏輯圖

3 導(dǎo)航路徑模型設(shè)計(jì)

3.1 泊位分派設(shè)計(jì)

本文運(yùn)用Dijkstra算法對(duì)輕量化的車位定位進(jìn)行最短路徑計(jì)算，然后對(duì)出口到車位距離進(jìn)行排序記錄，當(dāng)車輛請(qǐng)求泊位時(shí)根據(jù)該排序根據(jù)距離從小到大進(jìn)行分配，從而避免在導(dǎo)航過(guò)程中由于動(dòng)態(tài)規(guī)劃而產(chǎn)生大規(guī)模低效率計(jì)算。

Dijkstra算法步驟：①給Vs以P標(biāo)號(hào)，P（Vs）=0，其余各節(jié)點(diǎn)均給T標(biāo)號(hào)，T（Vi）=+∞；②若Vi點(diǎn)剛得到P標(biāo)號(hào)，考慮這樣的點(diǎn)Vj，（Vi，Vj）屬于E，且Vj為T(mén)標(biāo)號(hào)，對(duì)Vj的T標(biāo)號(hào)進(jìn)行如下的更改：T（Vj）=min[T（Vj），P（Vi）+Lij]；③比較所有具有T標(biāo)號(hào)的點(diǎn)，把最小者改為P標(biāo)號(hào)，即P（Vi）=min[T（Vi）]，當(dāng)同時(shí)兩個(gè)以上最小者，可同時(shí)改為P標(biāo)號(hào)；若全部點(diǎn)均為P標(biāo)號(hào)則停止。其中Vs即為地下停車場(chǎng)入口，Vi為道路交點(diǎn)節(jié)點(diǎn)和車位節(jié)點(diǎn)，將從地下停車場(chǎng)入口到道路節(jié)點(diǎn)，道路節(jié)點(diǎn)之間以及道路節(jié)點(diǎn)到目標(biāo)車位之間根據(jù)道路長(zhǎng)度設(shè)置路權(quán)，T標(biāo)號(hào)（tentative label）表示從Vs出發(fā)到Vi的估計(jì)最短路權(quán)的上界，是臨時(shí)標(biāo)號(hào)，P標(biāo)號(hào)（permanent label）表示從Vs出發(fā)到Vi的估計(jì)最短路權(quán)，是永久標(biāo)號(hào)。每一步要將某一節(jié)點(diǎn)的T標(biāo)號(hào)改為P標(biāo)號(hào)，若停車場(chǎng)的道路節(jié)點(diǎn)數(shù)為n，則最多經(jīng)n-1步驟可得從始點(diǎn)到終點(diǎn)的最短路徑。

3.2 路線規(guī)劃設(shè)計(jì)

通過(guò)泊位分配系統(tǒng)可以確定目標(biāo)車位標(biāo)號(hào)和位置，只需確定車庫(kù)入口到指定車位的最短路徑，便可對(duì)車輛進(jìn)行路徑導(dǎo)航。實(shí)際操作時(shí)可以通過(guò)提前使用Dijkstra算法分別計(jì)算出停車場(chǎng)各入口到各車位的最短路徑，并將所得結(jié)果儲(chǔ)存到系統(tǒng)中，之后直接通過(guò)分派的車位編號(hào)為車輛匹配最短路徑，然后利用改進(jìn)后TOA算法為車輛進(jìn)行實(shí)時(shí)定位導(dǎo)航并進(jìn)行語(yǔ)音提醒，同時(shí)將分配的車位狀態(tài)改為非空車位，可以節(jié)省在導(dǎo)航過(guò)程中所需時(shí)間，也可以提高導(dǎo)航效率。

4 結(jié)論

本文利用TOA和定向天線對(duì)導(dǎo)航定位系統(tǒng)進(jìn)行了輕量化處理，與傳統(tǒng)的TOA算法相比，改進(jìn)后TOA定位算法實(shí)現(xiàn)了單傳感器對(duì)用戶進(jìn)行位置定位，使導(dǎo)航成本降低。同時(shí)本文方法相對(duì)于TOA算法三邊定位誤差產(chǎn)生的可能性降低，提升了定位的準(zhǔn)確性，而且由于計(jì)算的簡(jiǎn)化使得導(dǎo)航的效率也得到一定程度的提升。使用Dijkstra算法提前計(jì)算出泊位距停車場(chǎng)出入口（樓梯口、電梯口等）距離并將結(jié)果匯總到系統(tǒng)中，首先根據(jù)距離由小到大為用戶分配泊位，再根據(jù)分配的泊位利用路線規(guī)劃系統(tǒng)為用戶匹配最短路徑，這樣既有利于提高用戶的停車效率，也為使用該地下導(dǎo)航定位系統(tǒng)的用戶帶來(lái)更好的使用體驗(yàn)。

由于現(xiàn)在地下停車場(chǎng)自動(dòng)停車研究方向多以機(jī)械式停車場(chǎng)為主，所以本文提出的定位算法并未直接將車輛引導(dǎo)到車位，而是將車輛引導(dǎo)到車位附近的空車位，由車輛駕駛員自主泊車。此外，本文的導(dǎo)航定位系統(tǒng)使用范圍具有局限性，目前適用于解決路徑相對(duì)固定環(huán)境的導(dǎo)航定位問(wèn)題，在后續(xù)研究中結(jié)合其他研究進(jìn)一步模擬并測(cè)試該方法。

注釋：

①新華社.《3.90億輛、4.76億人！公安部發(fā)布最新全國(guó)機(jī)動(dòng)車和駕駛?cè)藬?shù)據(jù)》.2021年10月12日.[EB/OL].http://www.gov.cn/shuju/2021-10/12/content_5642074.htm.