基于SLFNs插值指紋粒子濾波的共享單車跟蹤算法*

張棟梁， 曲 豪， 海本齋

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

0 引 言

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

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

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

1 基于RANSAC加權粒子濾波的定位算法

1.1 共享單車定位問題描述

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

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

圖1 初始相位和改進加權粒子濾波方案

1.2 基于RANSAC的初始化

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

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

1)whileiterations

8)end if

9)end for

12)end if

13)end while

1.3 模型生成

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

(1)

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

(2)

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

(3)

(4)

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

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

(5)

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

1.4 模型評價

RANSAC可將評價問題作為一個優化問題歸結為

(6)

(7)

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

(8)

(9)

(10)

圖2 SLFNs插值算法框架

在實際應用中使用插值算法，建議使用極限學習機(extreme learning machine,ELM)算法，主要優點是：1)學習速度非常快，訓練時間在毫秒(ms)范圍。2)ELM網絡支持訓練集的任何小訓練誤差，而隱藏的神經元不大于訓練樣本的數量。

2 實驗分析

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

2.1 初始化實驗階段

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

表1 初始化實驗結果

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

2.2 PF方案測試實驗

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

圖3 跟蹤軌跡

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

表2 不同方法的誤差距離

3 結束語

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