基于DTW的室內指紋定位方法

徐莉莉， 范 洪， 胡軍國

(浙江農林大學 信息工程學院，浙江 臨安 311300)

0 引 言

在大型室內場景中定位需求日益顯著，如在物流倉庫為搬運機器人提供路徑導航等[1～3]。然而目前的室內定位方法(如全球定位系統(global positioning system,GPS)、北斗、無線局域網(WiFi)定位、藍牙定位、ZigBee定位、超寬帶定位[4]等)存在諸多問題，很難應用于實際，因此研究一種可靠、低成本的定位方法意義重大。

目前室內定位方法可分為2種趨勢：基于信號強度的測距定位方法；基于特征匹配的指紋定位方法。其中測距定位主要是利用信號強度隨著傳播距離衰減的特征進行測距，計算未知節點的位置。如文獻[5,6]通過優化接收信號強度指示(recieved signal strength indication,RSSI)測距模型從而使得定位結果更加準確。文獻[7]研究了一種新的信號強度觀測模型并利用多錨節點協作定位。而基于特征匹配的指紋定位方法主要通過建立定位區域的特征指紋，然后利用匹配算法獲得定位結果。如文獻[8,9]采用WiFi構建定位指紋，通過控制指紋的匹配范圍從而獲得較高的定位精度。文獻[10]利用Kriging插值方法構建定位區域指紋并通過K-means算法優化定位結果。文獻[11]通過在室內普通電源線上注入寬帶高頻信號來構造定位指紋從而實現高精度定位。綜合考慮實用性和定位精度，利用地磁特征進行室內定位是較好的選擇[12～14]。

本文提出一種基于動態時間規整(dynamic time warping,DTW)的室內定位方法。該方法通過采集室內的地磁數據建立定位區域指紋，然后采用DTW算法進行特征匹配，同時為了提高定位精度，引入匹配范圍和K-means誤差排除等方法。

1 系統框架

定位方法總體框架如圖1，定位過程主要可分為2部分：定位區域地磁指紋構建；地磁與氣壓融合進行定位。

圖1 系統框架圖

2 指紋構建

2.1 特征數據采集

在地磁指紋構建和定位兩個過程中都需要智能設備采集數據，為了保證定位的實時性，采集數據的頻率為60 Hz，采集的數據包括地磁的x,y,z三軸數據和氣壓數據。由于地磁的三軸數據與傳感器的方向相關，但是x,y,z三軸地磁數據的模與地磁傳感器方向無關，因此采用地磁的向量模進行后續計算，地磁的向量模(geomagnetic-vector module,GM)為

(1)

2.2 地磁波形配準和物理坐標標定

為了構建可靠的地磁指紋數據庫，需要對定位區域進行多次數據采集，而每次采集數據時由于采集者的行走速度等原因的不同，會導致波形之間有錯位。如果直接將多條地磁波形融合構建地磁指紋數據庫會造成指紋數據庫的不準確，從而影響定位結果。本文通過平移法對地磁波形進行配準，每次平移10個地磁數據然后記錄每次平移后兩個波形的余弦相似度，最后選擇余弦相似度最高的位置作為波形配準后的位置。假設待配準的地磁波形用集合D={d1,d2,d3，…，dm}表示，樣本地磁波形用集合Dy={dy1,dy2,dy3，…，dys}表示，配準前后如圖2所示，配準后的地磁波形能夠較好吻合。地磁波形配準方法為：

輸入:樣本地磁波形Dy；待配準的地磁波形D。

輸出:待配準的地磁波形需要平移的位數。

1)擴展集合D，擴展后的集合為D′={0,0,0，…，d1,d2,d3，…，dm}，共m+s個元素。

2)擴展集合Dy，擴展后的集合為D′y={dy1,dy2,dy3，…，dys,0,0，…，0}，共m+s個元素。

3)計算D′和D′y的余弦相似度并保存到數組S中。

4)刪除集合D′最前面10個元素，刪除集合D′y最后面10個元素。

5)判斷集合D′的元素數量是否小于m/2，如果是，則退出循環并根據數組S中的最大值輸出配準需要平移的位數；否，則執行步驟(3)。

圖2 波形配準

為了構建地磁指紋數據庫，還需要為采集的地磁波形映射物理坐標。在采集數據的過程中記錄下行走的路徑，然后將該路徑對應的物理坐標均勻映射到地磁波上，從而構建了地磁波形和物理坐標一一對應的指紋數據庫。

3 定位過程

3.1 DTW地磁匹配

由于在定位過程中不同使用者的行走速度并不相同，這會導致在經過同一段路程時采集的地磁波形不完全相同，因此用傳統的方法(如余弦相似度)計算波形相似度很難達滿足需求。 本文采用DTW算法進行波形相似度匹配，能夠動態規劃兩條波形的匹配點，即使地磁指紋數據庫波形和待匹配的地磁波形在時間序列上的地磁數據數量不同也能較好地進行波形匹配。

在定位過程中智能設備實時采集地磁數據，利用滑動窗口截取實時數據流中的一段地磁波形作為待匹配的地磁波形用于和地磁指紋數據庫中的地磁波形進行匹配。系統每進行1次定位，DTW算法會匹配地磁指紋數據庫中所有的地磁波形并計算相似度，然后選擇波形匹配相似度最高的前n個匹配點作為匹配結果，根據匹配點對應的物理坐標得到n個定位坐標，最后根據誤差排除方法，融合n個定位結果獲得最終的一個定位結果。

3.2 定位誤差排除

為了提高定位精度、防止匹配偶然性帶來的定位誤差，本文選擇匹配度最高的前n個定位結果作為定位結果集群，然后對定位結果集群進行誤差點排除，最終獲得精度較高的定位結果，如圖3所示，圖中陰影區域表示誤差較大的定位結果，橢圓形內的有色區域表示誤差較小的定位結果。

本文采用K-means對n個定位結果進行聚類，共聚為K類，選擇元素最多的1類作為有效定位結果集，然后以有效定位結果集的重心作為最終定位結果，而其他元素較少的誤差類則能夠有效排除，從而提高了定位精度。

圖3 定位結果優化

3.3 樓層判斷

樓層的判斷可通過氣壓傳感器實現，不同的樓層氣壓有明顯的差異，當用戶上樓時，氣壓減小，當用戶下樓梯時，氣壓增大，如圖4所示。圖中記錄了用戶從四樓下到三樓(A～B)，在三樓稍作停留后又上到四樓(C～D)，稍作停留后又上到五樓(E～F)的氣壓變化情況。結果表明:每次上下樓梯，氣壓的變化值大約為40 Pa，而在同一樓層，氣壓值基本沒有太大的變化。

圖4 大氣壓強變化

本文利用氣壓變化值的大小判斷用戶在定位過程中是否發生了樓層的變化。如果當前傳感器讀取的氣壓值為P，則系統計算前T時間內采集的氣壓值與當前氣壓P的差值，尋找差值中絕對值最大的值，設前T時間內與氣壓P的差值絕對值最大的氣壓為PT，若P-PT<0且PT-P>Pth(本文設定閾值40 Pa)，則表明此時用戶上了一層樓，若P-PT>0且P-PT>Pth，則表明此時用戶下了一層樓。

4 系統實驗

本文將定位算法部署到Nexus智能手機上，該手機配備地磁傳感器和氣壓傳感器。定位實驗場景是三層教學樓內的走廊，三條走廊形狀一致，走廊中定位的路程總長度為14.2 m，走廊寬度為1.3 m。

4.1 定位時間間隔對精度的影響測試

定位的精度和定位實時性是算法的重要指標，地磁波形子序列越長，則匹配過程中的依據越多，匹配準確率越高，定位精度也就越高，而地磁波形子序列越長，在匹配過程中則需要更大的運算量，定位消耗的時間也就越長。因此,本實驗研究地磁波形子序列長度對定位精度和算法實時性的影響，圖5所示。圖5(a)表明，地磁波形序列越長，定位誤差越小，因為地磁波形序列越長，在匹配時的特征點越多，匹配越準確。當地磁波形序列長度為3 s時，定位誤差基本達到穩定，誤差大約為1.6 m。圖5(b)表明地磁波形序列越長，則每次定位需要消耗的時間越長，因為波形越長，在波形匹配時，運算量越大，因此消耗時間越多。本文將地磁波形序列長度設置為1.8 s，即在定位過程中，每隔1.8 s進行1次定位。

圖5 算法性能

4.2 定位結果優化實驗

對定位結果進行優化能夠提高定位精度，本實驗對比了沒有進行誤差排除和進行定位結果優化的結果，如圖6所示，在進行誤差排除前，共選擇了10個最高相似度的位置作為有效定位結果集，排除誤差后最終計算得到一個較可靠的定位結果。

圖6 定位結果優化

實驗結果表明:沒有經過誤差排除處理的定位結果誤差較大，且存在跳動的情況，平均定位誤差在2 m以上，而采用K-means方法進行誤差排除，其定位結果比較穩定，平均定位誤差約為1.4 m。

4.3 匹配范圍

根據上次定位結果為下次定位限定地磁指紋數據庫搜索范圍，既可以提高定位精度，還可以減少系統運算量。本次實驗對比限制地磁指紋數據庫搜索范圍前后對定位精度的影響，實驗結果如圖7所示。

圖7 匹配范圍影響

實驗結果表明：限制了地磁指紋數據庫的搜索范圍能夠較大幅度提高定位精度，其定位誤差最小約為1.6 m，而不限制搜索范圍的定位精度比較差，最小定位誤差約為3.1 m 左右，因為本文根據上次匹配的定位結果和匹配相似度限制了地磁指紋數據庫的搜索范圍，使得DTW算法匹配準確率更高，從而提高了定位精度。

5 結 論

本文采用室內地磁場構建定位指紋，利用DTW算法進行指紋匹配，實現初步定位，并引入匹配范圍減少系統運算量，最后采用K-means優化定位結果，實驗結果表明，提出的定位方法具有較高的定位精度和適應性，能夠滿足室內定位的需求。