張明洋，陳 劍，聞英友，趙 宏，王玉剛

(1.東北大學 計算機科學與工程學院，沈陽 110819； 2.東軟公司 軟件架構(gòu)新技術(shù)國家重點實驗室，沈陽110179)

基于動態(tài)時間規(guī)整距離指紋匹配的Wi-Fi網(wǎng)絡室內(nèi)定位算法

張明洋1,2，陳 劍1,2，聞英友1,2*，趙 宏1,2，王玉剛1,2

(1.東北大學 計算機科學與工程學院，沈陽 110819； 2.東軟公司 軟件架構(gòu)新技術(shù)國家重點實驗室，沈陽110179)

(*通信作者電子郵箱wenyy@neusoft.com)

Wi-Fi網(wǎng)絡中常規(guī)的基于指紋匹配室內(nèi)定位算法面臨信號時變現(xiàn)象或人為干擾的影響，導致定位精度不高。為此，提出基于動態(tài)時間規(guī)整(DTW)距離相似性指紋匹配的Wi-Fi網(wǎng)絡室內(nèi)定位算法。首先，該算法將定位區(qū)域的Wi-Fi信號特征按照采樣的先后順序轉(zhuǎn)化為時間序列類型指紋，通過計算Wi-Fi信號指紋動態(tài)時間規(guī)整距離的大小來獲取定位點與樣本點的相似性；然后，根據(jù)采樣區(qū)域結(jié)構(gòu)特征，將Wi-Fi信號指紋采集問題劃分為三類基本的動態(tài)路徑采樣方式；最后，結(jié)合多種動態(tài)路徑采樣方式增加指紋特征信息的準確性和完整性，從而提高指紋匹配的準確性和定位精度。大量實驗結(jié)果表明，較瞬時指紋匹配定位算法，所提算法誤差范圍在3m以內(nèi)定位的累積錯誤率：路徑區(qū)域勻速運動提高了10%，變速運動提高了13%；開放區(qū)域交叉曲線運動提高了9%，S型曲線運動提高了3%。所提算法在實際室內(nèi)定位應用中能有效提高指紋匹配的準確性和定位精度。

Wi-Fi網(wǎng)絡；室內(nèi)定位；時間序列；指紋匹配；動態(tài)時間規(guī)整

0 引言

近年來，隨著移動互聯(lián)網(wǎng)絡的發(fā)展，智能終端的普及，公共場所無線局域網(wǎng)絡熱點的大規(guī)模部署，位置服務和位置感知計算等移動互聯(lián)網(wǎng)增值業(yè)務受到關(guān)注，與基于射頻識別或傳感器網(wǎng)絡的定位方法[1- 2]相比，基于Wi-Fi網(wǎng)絡的定位技術(shù)以其網(wǎng)絡接入便利、設(shè)備成本低的特點受到重視[3]。該定位技術(shù)利用終端設(shè)備接收到的部署在Wi-Fi網(wǎng)絡環(huán)境中的無線接入點(Access Point, AP)的信號強度，就可以對移動終端進行定位[4-5]。

基于接收信號強度的定位方法可以分成基于測距的幾何定位法、基于基站的近似定位法[6-7]和基于指紋特征的場景分析法[8-9]等。在室內(nèi)環(huán)境中，由于建筑物布局、多徑、墻面反射吸收、溫濕度變化、人員出入等復雜因素對Wi-Fi信號傳播衰減造成的影響，導致信號強度衰減量與收發(fā)設(shè)備之間距離并不滿足路徑損耗漸變模型[10]，因此使用基于測距的三邊或三角定位算法[11-12]難以獲得較理想的定位效果?；贏P的近似定位法[6-7]主要利用設(shè)備的關(guān)聯(lián)關(guān)系進行位置估計，但其定位精度較低，無法滿足較高定位精度需求?；谥讣y特征的場景分析技術(shù)則利用復雜環(huán)境引起的Wi-Fi信號的特異性來構(gòu)建指紋信息。由于Wi-Fi信號的特異性與地形和傳播時的障礙物具有依賴性，呈現(xiàn)出針對環(huán)境的特殊特征，能獲得比其他定位方法更好的定位結(jié)果。

室內(nèi)Wi-Fi網(wǎng)絡的信號強度除了不滿足路徑損耗漸變模型之外，Wi-Fi信號本身還具有較大的時變性和隨機性[13- 14]，信號接收終端在同一地點觀測到的實時信號值也無法保證與該點的指紋樣本所匹配[15]，由此引起測試點的定位結(jié)果跳動從而影響總體定位效果。針對該問題一般的解決方式大多是在得出定位結(jié)果后再對其進行修正，如采用基于高斯濾波方法[16]、卡爾曼濾波方法[17]、粒子濾波方法[18]等各種濾波方法，通過對定位結(jié)果進行濾波達到對定位的修正，然而該種方式只適用于連續(xù)定位過程修正，針對離散點修正效果不明顯，且無法做到在定位過程中避免信號時變性引起的定位跳動。

考慮到在定位過程中避免定位跳動，本文提出了基于動態(tài)時間規(guī)整距離指紋匹配的Wi-Fi網(wǎng)絡室內(nèi)定位算法，它將采集到Wi-Fi網(wǎng)絡的接收信號強度(Received Signal Strength, RSS)結(jié)合采樣區(qū)域的路徑特征轉(zhuǎn)化為時間序列指紋，利用反映到序列指紋上的路徑特征避免由于個別采樣信號的時變性或人為干擾導致的定位跳動問題，并通過計算動態(tài)時間規(guī)整距離相似性解決由于變速運動造成的時間序列匹配不同步問題，進而在定位過程中抑制了結(jié)果跳變，提高了總體定位效果。

1 路徑特征的時間序列指紋

基于指紋匹配的定位算法一般可以劃分為指紋樣本的采集處理和指紋數(shù)據(jù)的匹配定位兩個步驟。在指紋采集處理過程中，通過Wi-Fi信號采集終端采集定位環(huán)境中AP的信號強度并記錄采集點坐標位置，在指紋匹配定位階段定位終端同樣采集環(huán)境中的AP信號強度信息并與采集階段的樣本信息匹配，獲得最相似的位置作為定位結(jié)果。然而，通?；谥讣y匹配的定位算法采集的指紋數(shù)據(jù)只使用當前地點的AP信號強度，在定位過程中無法避免由于AP信號強度的時變性或人為干擾導致的定位結(jié)果的跳動。相比而言，本文采用路徑特征的序列指紋可以充分結(jié)合采樣路徑的歷史特征信息，對AP信號的抖動以及人為干擾有較強的抵抗能力。

圖1 時間序列指紋

鑒于本文所設(shè)計的數(shù)據(jù)采樣模型主要應用于典型的公共場所定位環(huán)境，例如：商場、超市、樓宇等，本文對上述典型定位場景存在的區(qū)域路徑采樣方式進行規(guī)劃，采樣區(qū)域可分解為以下三類基本的動態(tài)路徑采樣方式：

1)如圖2(a)所示，為兩側(cè)開放路徑，路徑數(shù)據(jù)采集方式為沿著①、②兩個方向各采集一次數(shù)據(jù)，而后將采集到的數(shù)據(jù)分別按照①②和②①的先后順序相接，作為兩條線路數(shù)據(jù)。

2)如圖2(b)所示，為單側(cè)開放路徑，其路徑數(shù)據(jù)采集方式同兩側(cè)開放路徑采集方式，按照②①的先后順序相連作為一條線路。

3)如圖2(c)所示，為開放區(qū)域，可考慮在不影響定位精度的情況下選取其中若干條路徑作為數(shù)據(jù)采集路徑，而后可以按照①②…⑥和⑥⑤…①的順序連接，作為兩條線路。

利用上述基本的動態(tài)路徑采樣方式可以對區(qū)域路徑進行規(guī)劃，針對區(qū)域結(jié)構(gòu)特征主要考慮以下兩種情形：

1)規(guī)則路徑區(qū)域，可以按照路徑劃分成若干條縱向和橫向路徑；而后按照圖2(a)、(b)所示的兩側(cè)開放路徑和單側(cè)開放路徑的基本路徑采樣方式進行采樣生成采樣數(shù)據(jù)。

2)不規(guī)則路徑區(qū)域，主要是針對一些彎曲的、閉合的、分叉的不規(guī)則的路徑，首先將其轉(zhuǎn)化為規(guī)則的若干條規(guī)則路徑，而后按照1)的規(guī)則路徑區(qū)域方式進行處理。

針對其他類型的區(qū)域都可以劃歸到上述兩種情形中的一種或幾種進行處理。

圖2 區(qū)域路徑采樣示意圖

2 基于動態(tài)時間規(guī)整的指紋數(shù)據(jù)匹配算法

動態(tài)時間規(guī)整(DynamicTimeWarping,DTW)算法是一種常用的度量時間序列相似性的方法[19]，用于解決時間序列長度不一致的模板匹配問題，算法應用動態(tài)規(guī)劃的思想，通過對時間序列數(shù)據(jù)進行逐次計算最終獲得與模板數(shù)據(jù)的相似度。因其算法簡單、無需進行復雜的數(shù)據(jù)訓練過程，被廣泛地應用于語音識別、手勢識別、脫氧核糖核酸(DeoxyriboNucleicAcid,DNA)匹配等領(lǐng)域[20-22]。

本文的指紋數(shù)據(jù)模型是基于時間序列的線路數(shù)據(jù)模型，在實際應用中人的行走速度是不確定的，故記錄的時間序列指紋數(shù)據(jù)無法按照傳統(tǒng)指紋匹配中的歐氏距離一一對應進行匹配，存在圖3所示的匹配不一致現(xiàn)象。鑒于此，本文設(shè)計了基于動態(tài)時間規(guī)整的線路指紋匹配算法，不同于傳統(tǒng)的歐氏距離匹配，該算法可以將時間序列的線路數(shù)據(jù)進行彎折而后再進行對應，以此解決速度不確定導致的時間序列指紋數(shù)據(jù)無法對應的問題。

圖3 指紋匹配不一致

本文的匹配算法包括線路內(nèi)匹配和線路間匹配兩個步驟。在線路內(nèi)匹配過程中，針對每條線路計算請求定位指紋數(shù)據(jù)Qt與該線路的時間序列數(shù)據(jù)樣本S的DTW距離，其中對于?R∈Qt，?R′∈S，使得R與R′相似，即是Qt中元素在樣本S中都有與之對應的元素，同時對請求定位序列Qt和樣本序列S之間放寬起點和終點對齊限制，以使得Qt可以遍歷整條線路的樣本S，設(shè)計DTW采用的連續(xù)性條件如圖4所示。

圖4 連續(xù)性條件

階段最優(yōu)判別式為：

(1)

其中:g(i,j)為到請求序列Qt中第i個元素與樣本S第j個元素階段所匹配DTW距離;d(i,j)為請求序列Qt中第i個元素與樣本S第j個元素之間的相似性距離;本文選取指紋信號之間的歐氏距離作為元素之間距離度量。而后選擇其中的DTW距離最小的樣本記錄sj參與線路間匹配。式(1)中:式①相當于S中當前元素與上個元素對應Qt中同一個元素，因為Qt中對應元素未變，因此未增加d(i,j);而式②中相當于S中元素和Qt中元素在窗口中均增加一個，因此增加d(i,j)，同時，式②為時間序列對應完全一致條件下的匹配計算式;式③為Qt中元素在窗口中加1而S中元素未變的情況。本文動態(tài)時間規(guī)整算法即是通過式①、③對時間序列對應的調(diào)整來彌補式②在時間序列對應不一致時的計算誤差。

本文基于動態(tài)時間規(guī)整的線路內(nèi)匹配算法如下：

輸入 請求定位序列Qt，樣本序列S;

輸出 DTW距離和對應樣本序列的位置組X。

1)

分別計算序列Qt和S中元素的個數(shù)n和m;

2)

構(gòu)造Qt與S之間歐氏距離矩陣d(i,j)n×m;

3)

構(gòu)造Qt與S之間的DTW距離矩陣Dn×m;

4)

賦值D的第1列D(:,1)=d(:,1);

5)

計算D的第1行D(1,j)=D(1,j-1)+d(1,j);

6)

fori=2∶n

7)

forj=2∶m

8)

9)

end;

10)

end;

11)

DTW距離=min(D(:,m));

12)

X=Xfind(DTW距離==D(:,m))

本文的線路內(nèi)匹配算法由于利用動態(tài)時間規(guī)整距離進行相似性匹配，可自行計算獲得樣本序列與請求序列的匹配關(guān)系，而無需請求序列的起止點與線路數(shù)據(jù)的起止點一一對應，因此可以獲得各條線路內(nèi)與請求序列Qt最相似的樣本子序列位置組X(Qt中等于DTW距離的一組X按線路采樣時間順序排列)，而后進行線路間匹配，以獲得最終匹配定位結(jié)果，算法如下：

輸入 每條線路的DTW距離和對應樣本序列位置組X以及選取樣本個數(shù)K和對應的一組權(quán)重W={w1,w2,…,wK}；

輸出 匹配定位位置Xfinal。

1) 按照DTW距離由小到大排序?qū)恢媒MX，組成位置組序列{X1,X2,…,Xl};

2) 選擇位置組序列{X1,X2,…,Xl}中前K個位置;

4) 匹配定位位置Xfinal=Xaver

通過線路內(nèi)匹配和線路間匹配獲取最終的定位位置Xfinal作為最終的定位結(jié)果。

對本文定位算法的線路內(nèi)匹配和線路間匹配進行分析，線路內(nèi)匹配的計算復雜度為O(n×m)，而線路間匹配的計算復雜度為O(l2)，均可在平方時間復雜度內(nèi)完成計算，可以滿足實際定位時間需求；而在線路內(nèi)匹配計算過程中所需最大的空間開銷為距離矩陣Dn×m，線路間匹配計算過程中,所需最大的空間開銷為位置組序列{X1,X2,…,Xl}，也均可以滿足實際定位的空間需求。

3 實驗結(jié)果與分析

本文的定位算法主要是基于時間序列數(shù)據(jù)模型進行指紋匹配，算法的定位效果會受到時間序列窗口的大小、采樣的速度以及采樣的路徑所影響，鑒于上述分析，本文實驗部分主要包括窗口大小的選取、變速運動定位測試和開放區(qū)域定位實驗。

3.1 窗口大小的影響

本實驗測試環(huán)境如圖5所示，實驗環(huán)境面積大小為25m×15m，其中的四處“*”為無線AP所在位置，矩形為環(huán)境中不可抵達點(如：辦公桌、機柜、墻體等)，在實驗環(huán)境中以大致勻速沿虛線所示路徑按照規(guī)則路徑區(qū)域采樣方式進行采樣，采樣的時間間隔是0.5s，包括縱向7條采樣線路和橫向1條采樣線路，并將采樣數(shù)據(jù)分別分為采樣樣本和測試數(shù)據(jù)兩部分。

通過對DTW相似性匹配算法的分析，由于定位過程中每次匹配的數(shù)據(jù)特征為一個滑動窗口中的內(nèi)容，故滑動窗口的大小將影響定位的效果，同時隨著滑動窗口增大，定位所需時間增加，本文此處對比滑動窗口大小與定位誤差的變化，累積錯誤率為誤差范圍內(nèi)的定位測試數(shù)據(jù)量占總定位測試數(shù)據(jù)量的比例,得到窗口大小與定位結(jié)果如圖6所示。

圖5 實驗環(huán)境示意圖

圖6 窗口大小與定位結(jié)果

圖6中，本文分別對同一組測試數(shù)據(jù)按照1～5個大小的窗口應用本文的算法進行定位測試，并分別統(tǒng)計其1～10m的定位誤差。由圖6可以看出，隨著窗口增加，定位誤差減小，當窗口大小為5時，誤差范圍3m的定位達到72%，誤差范圍5m的定位達到91%。因此，該實驗驗證了將指紋數(shù)據(jù)按照時間序列方式轉(zhuǎn)化為滑動窗口模型，增加了指紋匹配的信息量，提高了指紋匹配定位的精度，但窗口的設(shè)置在考慮定位精度的同時也要兼顧定位的時間，即是當窗口增大時首次定位時間會由于需要足夠的窗口數(shù)據(jù)而延長，且當切換線路時會由于窗口數(shù)據(jù)的存在而導致定位延遲，因此，折中選擇窗口的大小為3～6既可以提高總體定位精度又不會在感覺上造成較大的影響。

3.2 變速運動定位效果

本文的數(shù)據(jù)模型是基于時間序列的，因此，采樣時間間隔的變化對指紋匹配的結(jié)果會有影響，反映在采樣線路就是運動速度的變化，鑒于此本實驗針對圖5的測試環(huán)境，分別進行變速、勻速指紋采集，而后將變速、勻速的測試數(shù)據(jù)代入勻速建立的指紋樣本庫進行測試，用以比較傳統(tǒng)的指紋匹配算法和本文的基于時間序列模型的指紋算法的定位效果。如圖7所示，本文選擇的窗口大小為5，從圖中可以看到基于動態(tài)時間規(guī)整的指紋匹配定位算法因為能夠較好地吻合時間序列特征獲得線路的相似數(shù)據(jù)，勻速運動誤差范圍在3m以內(nèi)的定位達到72%，較傳統(tǒng)的歐氏距離瞬時指紋匹配的定位方法的累積錯誤率提高了10%，本文算法的平均定位誤差為2.06m，較文獻[18]中的3.18m定位誤差相比，定位精度提高了35%，且本文所提算法定位誤差受速度變化的影響相對不大，變速運動誤差范圍在3m以內(nèi)的定位達到65%，與傳統(tǒng)的歐氏距離瞬時指紋匹配的定位相比，累積錯誤率高于勻速運動3%，高于變速運動13%，因此，本文的基于時間序列模型的指紋定位算法以其特征數(shù)據(jù)量大的優(yōu)勢獲得較好的定位效果。

3.3 開放區(qū)域定位效果

本文基于時間序列的指紋匹配算法，所建立的模型是基于路徑的時間序列的指紋數(shù)據(jù)，因此定位效果會受到路徑所影響，而對于開放區(qū)域路徑規(guī)劃較為困難，因此，本文針對該類型區(qū)域定位效果進行實驗測試，如圖8所示，本文針對橫向3條曲線以及與橫向交叉的縱向12條曲線和一條S型曲線進行采樣，并用橫向曲線建模作為樣本數(shù)據(jù)，對交叉的縱向曲線和S型曲線進行測試。

圖7 變速運動定位結(jié)果

圖8 開放區(qū)域測試環(huán)境

如圖9所示，針對交叉曲線本文的基于時間序列模型的DTW定位算法與傳統(tǒng)指紋定位算法的在1～10m誤差范圍內(nèi)本文算法定位效果均好于傳統(tǒng)指紋定位算法，誤差范圍在3m以內(nèi)的定位達到46%，較傳統(tǒng)的歐氏距離瞬時指紋匹配的定位方法的累積錯誤率提高了9%，因其將整個開放區(qū)域作為一條路徑可將一定范圍內(nèi)時間序列作為一個樣本進行指紋匹配，即使無法達到與樣本線路完全吻合也會略好于瞬時指紋數(shù)據(jù)，因此，定位效果較比傳統(tǒng)指紋算法要好。

圖9 交叉曲線運動定位效果

圖10所示的S型曲線的測試是為了驗證本文算法在跨越線路的隨機運動的定位效果，同樣本文算法的定位效果優(yōu)于傳統(tǒng)的指紋定位算法。誤差范圍在3m以內(nèi)的定位達到48%，較傳統(tǒng)的歐氏距離瞬時指紋匹配的定位方法的累積錯誤率提高了3%。本文算法的平均定位誤差為3.05m，較文獻[18]中的3.77m定位誤差相比，定位精度提高了19%。

圖10 S型曲線運動定位效果

4 結(jié)語

本文針對基于指紋匹配室內(nèi)定位算法面臨的Wi-Fi信號時變特性引起的定位精度問題，提出了基于DTW距離指紋匹配定位算法，利用Wi-Fi采樣信號在時間上先后順序的相關(guān)性，建立了基于時間序列Wi-Fi信號指紋模型，并根據(jù)采樣區(qū)域結(jié)構(gòu)特征，將Wi-Fi信號指紋采集問題歸納為三類基本動態(tài)路徑采樣方式和兩種區(qū)域路徑規(guī)劃情況，使指紋匹配準確性和定位精度得到提高，實驗結(jié)果表明本文算法在勻速運動、變速運動以及開放區(qū)域等方面的定位效果均優(yōu)于瞬時指紋定位算法。但是，在計算定位指紋匹配過程中，本文的DTW距離計算仍需平方時間復雜度，在一定程度影響了定位性能，這也是今后需要改進的方面。

)

[1] 孫利民.無線傳感器網(wǎng)絡[M].北京:清華大學出版社,2005:135-156.(SUNLM.WirelessSensorNetworks[M].Beijing:TsinghuaUniversityPress, 2005: 135-156.)

[2]WENYY,GAOR,ZHAOH.Energyefficientmovingtargettrackinginwirelesssensornetworks[J].Sensors, 2016, 16(1):ArticleNo. 29.

[3] 田增山,代海鵬. 基于曲面擬合的WiFi指紋數(shù)據(jù)庫更新[J].計算機應用,2016,36(5):1192-1195.(TIANZS,DAIHP.WiFifingerprintdatabaseupdatingbasedonsurfacefitting[J].JournalofComputerApplications, 2016, 36(5): 1192-1195.)

[4]MAJEEDK,SOROURS,AL-NAFFOURITY,etal.Indoorlocalizationandradiomapestimationusingunsupervisedmanifoldalignmentwithgeometryperturbation[J].IEEETransactionsonMobileComputing, 2016, 15(11): 2794-2808.

[5]YANGH,ZHANGR,BORDOYJ,etal.Smartphone-basedindoorlocalizationsystemusinginertialsensorandacoustictransmitter/receiver[J].IEEESensorsJournal, 2016, 16(22): 8051-8061.

[6]TSALOLIKHINE,BILIKI,BLAUNSTEINN.Asingle-base-stationlocalizationapproachusingastatisticalmodeloftheNLOSpropagationconditionsinurbanterrain[J].IEEETransactionsonVehicularTechnology. 2011, 60(3): 1124-1137.

[7]SCHLOEMANNJ,DHILLONHS,BUEHRERRM.Atractablemetricforevaluatingbasestationgeometriesincellularnetworklocalization[J].IEEEWirelessCommunicationsLetters, 2016, 5(2): 140-143.

[8]JIANGQD,MAYT,LIUKH,etal.Aprobabilisticradiomapconstructionschemeforcrowdsourcing-basedfingerprintinglocalization[J].IEEESensorsJournal, 2016, 16(10): 3764-3774.

[9]XUXL,TANGY,WANGXH,etal.Variance-basedfingerprintdistanceadjustmentalgorithmforindoorlocalization[J].JournalofSystemsEngineeringandElectronics, 2015, 26(6): 1191-1201.

[10]ZHOUG,HET,KRISHNAMURTHYS,etal.Modelsandsolutionsforradioirregularityinwirelesssensornetworks[J].ACMTransactionsonSensorNetworks, 2006, 2(2): 221-262.

[11]TOMICS,BEKOM,DINISR.DistributedRSS-AoAbasedlocalizationwithunknowntransmitpowers[J].IEEEWirelessCommunicationsLetters, 2016, 5(4): 392-395.

[12]JAMALABDOLLAHIM,ZEKAVATS.ToArangingandlayerthicknesscomputationinnonhomogeneousmedia[J].IEEETransactionsonGeoscienceandRemoteSensing, 2017, 55(2): 742-752.

[13] 李石榮,李飛騰.基于RSSI概率統(tǒng)計分布的室內(nèi)定位方法[J].計算機工程與應用,2016,52(11):119-124.(LISR,LIFT.MethodforindoorpositioningbasedonRSSIstatisticalprobabilitydistribution[J].ComputerEngineeringandApplications, 2016, 52(11): 119-124.)

[14] 趙方，羅海勇，馬嚴，等.基于公共信標集的高精度射頻指紋定位算法[J].計算機研究與發(fā)展,2012,49(2):243-252.(ZHAOF,LUOHY,MAY,etal.Anaccuratefingerprintinglocalizationalgorithmbasedoncommonbeacons[J].JournalofComputerResearchandDevelopment, 2012, 49(2): 243-252.)

[15] 張明洋，陳劍，聞英友，等.基于滑動窗口最長公共子序列Wi-Fi指紋定位算法[J].東北大學學報(自然科學版),2014,35(10):1390-1394.(ZHANGMY,CHENJ,WENYY,etal.Wi-Fifingerprintlocalizationalgorithmbasedonslidingwindowcombinedwithlongestcommonsubsequence[J].JournalofNortheasternUniversity(NaturalScience), 2014, 35(10): 1390-1394.)

[16]YIUS,YANGK.Gaussianprocessassistedfingerprintinglocalization[J].IEEEInternetofThingsJournal, 2016, 3(5): 683-690.

[17]ROMANIUKS,AMBROZIAKL,GOSIEWSKIZ,etal.RealtimelocalizationsystemwithextendedKalmanfilterforindoorapplications[C]//Proceedingsofthe2016 21stInternationalConferenceonMethodsandModelsinAutomationandRobotics.Piscataway,NJ:IEEE, 2016: 42-47.

[18] 周瑞，李志強，羅磊.基于粒子濾波的WiFi行人航位推算融合室內(nèi)定位[J].計算機應用,2016,36(5):1188-1191,1200.(ZHOUR,LIZQ,LUOL.WiFi-pedestriandeadreckoningfusedindoorpositioningbasedonparticlefiltering[J].JournalofComputerApplications, 2016, 36(5): 1188-1191, 1200.)

[19] 王少鵬，聞英友，李志，等.一種關(guān)于數(shù)據(jù)流區(qū)間Disjoint查詢的快速處理算法[J].計算機研究與發(fā)展,2014,51(5):1136-1148.(WANGSP,WENYY,LIZ,etal.Afastprocessingalgorithmonsectiondisjointqueryofdatastream[J].JournalofComputerResearchandDevelopment, 2014, 51(5): 1136-1148.)

[20]ESLINGP,AGONC.Time-seriesdatamining[J].ACMComputingSurveys, 2012, 45(1):ArticleNo. 12.

[21]LE-KHACNA,BUEM,WHELANM,etal.Aclustering-baseddatareductionforverylargespatio-temporaldatasets[C]//ADMA’10:Proceedingsofthe6thInternationalConferenceonAdvancedDataMiningandApplications,LNCS6441.Berlin:Springer, 2010: 43-54.

[22]TOYODAM,SAKURAIY,ISHIKAWAY.Patterndiscoveryindatastreamsunderthetimewarpingdistance[J].TheVLDBJournal, 2013, 22(3): 295-318.

ThisworkispartiallysupportedbytheNationalHighTechnologyResearchandDevelopmentProgram(863Program)ofChina(2015AA016005),theNationalNaturalScienceFoundationofChina(61402096, 61173153, 61300196).

ZHANG Mingyang, born in 1989, Ph. D. candidate. His research interests include wireless network, wireless sensor network, localization technology.

CHEN Jian, born in 1980, Ph. D., associate professor. His research interests include wireless sensor network, localization technology, network management.

WEN Yingyou, born in 1974, Ph. D., associate professor. His research interests include mobile communication, network security.

ZHAO Hong, born in 1954, Ph. D., professor. His research interests include distributed multimedia information processing, computer network, image processing.

WANG Yugang, born in 1989, M. S. candidate. His research interests include wireless localization technology.

Fingerprint matching indoor localization algorithm based on dynamic time warping distance for Wi-Fi network

ZHANG Mingyang1,2, CHEN Jian1,2, WEN Yingyou1,2*, ZHAO Hong1,2, WANG Yugang1,2

(1.SchoolofComputerScienceandEngineering,NortheasternUniversity,ShenyangLiaoning110819,China; 2.StateKeyLaboratoryofSoftwareArchitecture,NeusoftCorporation,ShenyangLiaoning110179,China)

Focusing on the low accuracy problem of regular fingerprint matching indoor localization algorithm for Wi-Fi network confronted with signal fluctuation or jamming, the fingerprint matching indoor localization algorithm based on Dynamic Time Warping (DTW) similarity for Wi-Fi network was proposed. Firstly, the Wi-Fi signal characteristics in localization area were converted to the time-series fingerprints according to the sequence of sampling. The similarity between the locating data and sampling data was obtained by computing the fingerprint DTW distance of Wi-Fi signal. Then, according to the structural characteristics of the sampling area, the fingerprint sampling problem of Wi-Fi signal was divided into three kinds of basic sampling methods based on dynamic path. Finally, the accuracy and completeness of the fingerprint feature information were increased by the combination of multiple dynamic path sampling methods, which improved the accuracy and location precision of fingerprint matching. The extensive experimental results show that, compared with the instantaneous fingerprint matching indoor localization algorithm, within the location error of 3 m, the cumulative error frequency of the proposed localization algorithm, was 10% higher for uniform motion and 13% higher for variable motion within routing area, and 9% higher for crossed curvilinear motion and 3% higher for S-type curvilinear motion within open area. The proposed localization algorithm can improve accuracy and location precision of fingerprint matching effectively in real indoor localization applications.

Wi-Fi network; indoor localization; time series; fingerprint matching; Dynamic Time Warping (DTW)

2016- 10- 26;

2017- 01- 14。

國家863計劃項目(2015AA016005)；國家自然科學基金資助項目(61402096,61173153,61300196)。

張明洋(1989—)，男，遼寧遼陽人，博士研究生，主要研究方向：無線網(wǎng)絡、無線傳感器網(wǎng)絡、定位技術(shù)； 陳劍(1980—)，男，湖南邵陽人，副教授，博士，主要研究方向：無線傳感器網(wǎng)絡、定位技術(shù)、網(wǎng)絡管理； 聞英友(1974—)，男，遼寧沈陽人，副教授，博士，主要研究方向：移動通信、網(wǎng)絡安全； 趙宏(1954—)，男，河北河間人，教授，博士，主要研究方向：分布式多媒體信息處理、計算機網(wǎng)絡、圖像處理；王玉剛(1989—)，男，山東德州人，碩士研究生，主要研究方向：無線定位技術(shù)。

1001- 9081(2017)06- 1550- 05

10.11772/j.issn.1001- 9081.2017.06.1550

TP 393.17

A