張棟梁， 曲 豪， 海本齋

(1.河南廣播電視大學(xué)，河南 鄭州 450008;2.河南師范大學(xué) 計算機與信息工程學(xué)院，河南 新鄉(xiāng) 453007)

0 引 言

自2015年開始，共享單車逐漸在我國各線城市中得到覆蓋，到2016年底，我國共享單車保有量達到了1 923萬輛[1]。共享單車管理過程中，共享單車的定位跟蹤是需要考慮的主要問題[2]。因為共享單車的出現(xiàn)時間較晚，對于共享單車的定位研究較少[3]。

在現(xiàn)有定位算法中，指紋和慣性測量相結(jié)合后的結(jié)果是平滑的、自校準(zhǔn)的，但由于指紋算法需要假設(shè)唯一的指紋，所以精度仍然受到限制。實際應(yīng)用中，由于多徑效應(yīng)和接入點位置的安排，兩個遙遠的參考點可以共享非常相似的指紋[4]。因此，模式識別算法不能保證正確的估計。不準(zhǔn)確的位置估計會降低整體性能。同時，初始化粒子濾波(particle filtering,PF)所需的時間也是一個重要因素。全局初始化收斂速度較慢。在入口處部署額外的硬件增加了總成本。

本文對PF的改進有兩個主要貢獻：1)基于隨機一致性抽樣(random consistency sampling,RANSAC)方法得到從WiFi指紋在初始化階段消除不準(zhǔn)確的估計[5,6]。與全局初始化相比，其需要更少的迭代收斂。算法選擇正確的估計，從指紋的行人航跡推算(pedestrian dead reckoning,PDR)數(shù)據(jù)建立了高斯模型。利用內(nèi)點估計初始位置。2)為了克服初始化估計錯誤問題，通過單隱含層前饋網(wǎng)絡(luò)(single hidden layer feedforward networks,SLFNs)插值對傳統(tǒng)的PF加權(quán)模型的多個指紋概率進行分析[7]?？紤]了不同的參考點WiFi指紋算法的概率，以盡量減少錯誤所帶來的類似的指紋問題[8]。

1 基于RANSAC加權(quán)粒子濾波的定位算法

1.1 共享單車定位問題描述

基于粒子濾波的共享單車定位問題是對于時刻t查找共享單車軌跡v1:t的聯(lián)合后驗p(v1:t|z1:t,u1:t,m)。在該問題中，z1:t=z1,z2,…,zt為觀測值，u1:t=u1,u2,…,ut為運動的里程計測量[9]。地圖m在系統(tǒng)中通常已知。通常由慣性測量單元(inertial measurement unit,IMU)模塊獲得運動里程測量值。PDR是實現(xiàn)人類導(dǎo)航的常用方法。有多種方法獲得觀測結(jié)果，包括激光測距儀、紅外、WiFi指紋等。本文主要集中于WiFi指紋的解決方案。

如圖1所示，系統(tǒng)的輸入包括WiFi RSSI掃描和IMU讀數(shù)。對傳統(tǒng)粒子濾波算法進行了兩個重大改進。首先，將RANSAC初始化過程引入到系統(tǒng)[10,11]。需要對WiFi模塊進行多次掃描，并使用PDR算法生成軌跡模型。過濾掉所有的異常點的軌跡并保持正確的初始化，以提高PF的收斂速度和精度。在正常采樣階段，引入了一種改進的重要性加權(quán)法。該階段最初收集多個指紋估計的概率。用模型擬合算法構(gòu)造高斯混合模型。每個粒子從構(gòu)造模型中進行權(quán)重獲取。最終進行基于權(quán)值的粒子重采樣，并計算新粒子的位置均值。

圖1 初始相位和改進加權(quán)粒子濾波方案

1.2 基于RANSAC的初始化

算法基于一致隨機抽樣的初始化過程

輸入：指紋估計數(shù)據(jù)ψ、PDR模型MPDR、最大迭代數(shù)N、滿足模型的最小數(shù)據(jù)點min、模型公差因子E、內(nèi)部閾值Ith。

1)whileiterations

8)end if

9)end for

12)end if

13)end while

1.3 模型生成

為了構(gòu)造PDR模型，首先執(zhí)行c迭代的PDR算法。對于每一次迭代，用戶的相對位置可以通過以下方式計算

(1)

(xi+1,yi+1)=(xi+Lisinφi,yi+Licosφi)

(2)

式中xi和yi為坐標(biāo),Li和φi為第i步的步幅和方向。利用高斯最小二乘擬合方法對高斯模型G(x)進行擬合。結(jié)合本文模型,將函數(shù)移到地圖上的任意位置，利用(x′,y′)的2組系數(shù)對初始點進行估計，有

(3)

(4)

式中Distance(d;MPDR(x,y))為實例和模型之間的距離。并在曲線(xo,yo)上選擇最接近點o。最終計算距離為

Distance(d;MaPDR(x,y))=

(5)

式中C為d到兩個端點距離的最小值。

1.4 模型評價

RANSAC可將評價問題作為一個優(yōu)化問題歸結(jié)為

(6)

(7)

1.5 利用SLFNs插值的指紋概率建模

(8)

(9)

(10)

圖2 SLFNs插值算法框架

在實際應(yīng)用中使用插值算法，建議使用極限學(xué)習(xí)機(extreme learning machine,ELM)算法，主要優(yōu)點是：1)學(xué)習(xí)速度非?？?，訓(xùn)練時間在毫秒(ms)范圍。2)ELM網(wǎng)絡(luò)支持訓(xùn)練集的任何小訓(xùn)練誤差，而隱藏的神經(jīng)元不大于訓(xùn)練樣本的數(shù)量。

2 實驗分析

收集PDR數(shù)據(jù)和指紋數(shù)據(jù)。實驗在人們進入共享單車跟蹤場景時進行，RSSI樣本受環(huán)境因素的影響，如移動物體和人。因此，基于接收信號強度指示(received signal strength indication,RSSI)指紋的方法受到多徑效應(yīng)和運動目標(biāo)的顯著影響，這與實際場景相似。PDR算法在手機上實現(xiàn)，使用IMU收集的數(shù)據(jù)。應(yīng)用這些數(shù)據(jù)測試所提出的PF方案的初始化階段和估計精度。對于指紋算法，在30 m×35 m范圍內(nèi)選擇了84個參考點。在每個參考點收集了30個指紋。選擇了支持向量機和概率估計算法作為對比算法。

2.1 初始化實驗階段

為了測試所提出的初始化方法，在10個不同軌道上不同位置的初始條件下收集了10個數(shù)據(jù)集。每個初始數(shù)據(jù)集包括11個步驟和11個WiFi掃描。首先研究每個數(shù)據(jù)集上的高斯模型擬合。PF在所獲取的模型的當(dāng)前位置初始化。實驗的模擬結(jié)果如表1。

表1 初始化實驗結(jié)果

PDR模型擬合誤差用于檢驗?zāi)Ｐ偷木?，結(jié)果表明：平均誤差為0.21 m。數(shù)量的異常值論證了RANSAC方法的有效性。本實驗中，該方法平均濾除了4.2個離群值。初始化誤差距離和最大誤差距離說明初始化的準(zhǔn)確性。作為比較算法，選擇基于K最近鄰(K-nearest neighbor,KNN)的指紋初始化。該方法將平均誤差距離減小1.6 m，減小最大誤差距離2.6 m。為提高收斂速度，該方法只需要這11個迭代過程進行模型擬合和RANSAC算法。作為比較，全局初始化需要平均19.1次迭代才能收斂。

2.2 PF方案測試實驗

實驗中，所有的算法均使用相同的指紋數(shù)據(jù)庫和相同的PDR數(shù)據(jù)。圖3(a)給出了用原始指紋法估計的共享單車軌跡。利用紅線連接進行連續(xù)估計?？梢钥闯觯航Y(jié)果受到不一致的觀察和估計。在某些情況下，由于缺失值、噪聲數(shù)據(jù)或指紋的相似性，連續(xù)估計的彼此距離較遠。圖3(b)給出了來自原始PDR的軌跡。圖中，每個點代表一個步驟。方法在前3個走廊表現(xiàn)良好，但是積累了大量的錯誤。圖3(c)給出本文方法的軌跡，結(jié)合了指紋和PDR的信息。實驗結(jié)果表明，本文算法對含噪指紋數(shù)據(jù)和PDR數(shù)據(jù)進行了修正，提高了最終性能。

圖3 跟蹤軌跡

如表2所示，本文方法與SVM和概率算法的平均誤差距離分別為1.2 m和1.3 m。這個值較PDR值低1 m，利用經(jīng)典高斯加權(quán)法融合PF的概率方法。在最大誤差距離方面也有很大改進。

表2 不同方法的誤差距離

3 結(jié)束語

本文提出一種基于SLFNs插值指紋粒子濾波的共享單車跟蹤算法，利用慣性傳感器進行數(shù)據(jù)測量，并提出了一種新的PF方案，產(chǎn)生平穩(wěn)和穩(wěn)定的局部化知識。同時利用隨機一致性抽樣進行算法初始化，以減少收斂時間。實驗結(jié)果驗證了本文算法性能優(yōu)勢。