基于動態時間規整距離指紋匹配的Wi-Fi網絡室內定位算法

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

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

基于動態時間規整距離指紋匹配的Wi-Fi網絡室內定位算法

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

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

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

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

Wi-Fi網絡；室內定位；時間序列；指紋匹配；動態時間規整

0 引言

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

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

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

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

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

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

圖1 時間序列指紋

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

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

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

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

利用上述基本的動態路徑采樣方式可以對區域路徑進行規劃，針對區域結構特征主要考慮以下兩種情形：

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

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

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

圖2 區域路徑采樣示意圖

2 基于動態時間規整的指紋數據匹配算法

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

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

圖3 指紋匹配不一致

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

圖4 連續性條件

階段最優判別式為：

(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中元素未變的情況。本文動態時間規整算法即是通過式①、③對時間序列對應的調整來彌補式②在時間序列對應不一致時的計算誤差。

本文基于動態時間規整的線路內匹配算法如下：

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

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

1)

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

2)

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

3)

構造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))

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

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

輸出 匹配定位位置Xfinal。

1) 按照DTW距離由小到大排序對應位置組X，組成位置組序列{X1,X2,…,Xl};

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

4) 匹配定位位置Xfinal=Xaver

通過線路內匹配和線路間匹配獲取最終的定位位置Xfinal作為最終的定位結果。

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

3 實驗結果與分析

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

3.1 窗口大小的影響

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

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

圖5 實驗環境示意圖

圖6 窗口大小與定位結果

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

3.2 變速運動定位效果

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

3.3 開放區域定位效果

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

圖7 變速運動定位結果

圖8 開放區域測試環境

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

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

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

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

4 結語

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

)

[1] 孫利民.無線傳感器網絡[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指紋數據庫更新[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概率統計分布的室內定位方法[J].計算機工程與應用,2016,52(11):119-124.(LISR,LIFT.MethodforindoorpositioningbasedonRSSIstatisticalprobabilitydistribution[J].ComputerEngineeringandApplications, 2016, 52(11): 119-124.)

[14] 趙方，羅海勇，馬嚴，等.基于公共信標集的高精度射頻指紋定位算法[J].計算機研究與發展,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行人航位推算融合室內定位[J].計算機應用,2016,36(5):1188-1191,1200.(ZHOUR,LIZQ,LUOL.WiFi-pedestriandeadreckoningfusedindoorpositioningbasedonparticlefiltering[J].JournalofComputerApplications, 2016, 36(5): 1188-1191, 1200.)

[19] 王少鵬，聞英友，李志，等.一種關于數據流區間Disjoint查詢的快速處理算法[J].計算機研究與發展,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—)，男，遼寧遼陽人，博士研究生，主要研究方向：無線網絡、無線傳感器網絡、定位技術； 陳劍(1980—)，男，湖南邵陽人，副教授，博士，主要研究方向：無線傳感器網絡、定位技術、網絡管理； 聞英友(1974—)，男，遼寧沈陽人，副教授，博士，主要研究方向：移動通信、網絡安全； 趙宏(1954—)，男，河北河間人，教授，博士，主要研究方向：分布式多媒體信息處理、計算機網絡、圖像處理；王玉剛(1989—)，男，山東德州人，碩士研究生，主要研究方向：無線定位技術。

1001- 9081(2017)06- 1550- 05

10.11772/j.issn.1001- 9081.2017.06.1550

TP 393.17

A