一種層次Levenshtein距離的無指紋校準的室內定位方法

何富貴，楊錚，吳陳沭，趙姝，周先存

(1.皖西學院 電子與信息工程學院，安徽 六安 237012； 2. 清華大學 軟件學院可信網絡與系統研究所，北京 100084；3.安徽大學 智能計算與知識工程研究所，安徽 合肥 230039)

一種層次Levenshtein距離的無指紋校準的室內定位方法

何富貴1，3，楊錚2，吳陳沭2，趙姝3，周先存1

(1.皖西學院 電子與信息工程學院，安徽 六安 237012； 2. 清華大學 軟件學院可信網絡與系統研究所，北京 100084；3.安徽大學 智能計算與知識工程研究所，安徽 合肥 230039)

隨著移動計算領域的興起，基于位置的服務越來越受青睞。目前各種室內定位的方法層出不窮，由于室內廣泛部署了無線基礎設施，基于WiFi指紋信息的室內定位技術是其主流方法。設備異構和室內環境變化是影響定位精度的主要因素。本文針對以上兩個問題，提出一種層次Levenshtein距離(HLD)的WiFi指紋距離計算算法，實現異構設備的指紋無校準比對。將不同移動設備采集的RSSI信息轉化為AP序列，根據AP對應的RSSI值的差異性計算其層次能級，結合Levenshtein距離計算WiFi指紋之間的距離。對于需定位的WiFi指紋RSSI信息，利用HLD算法獲取K個近鄰，采用WKNN算法進行預測定位。實驗中，為了驗證算法的魯棒性和有效性，在3種不同類型的室內環境中采用5種不同的移動設備來采集WiFi的RSSI信息，其定位的平均精度達1.5 m。

室內定位；WiFi指紋；設備異構；無指紋校準；Levenshtein距離

中文引用格式：何富貴，楊錚，吳陳沭，等.一種層次Levenshtein距離的無指紋校準的室內定位方法[J]. 智能系統學報， 2017, 12(3): 422-429.

英文引用格式：HE Fugui，YANG Zheng，WU Chenshu, et al. An fingerprint calibrations-free indoor localization method based on hierarchical Levenshtein distance[J]. CAAI transactions on intelligent systems, 2017, 12(3): 422-429.

基于位置的服務，如路徑導航、廣告推薦和鄰近社交網絡等，隨著智能手機的普及已變得尤為重要。在室內環境中GPS對衛星信號的接收較弱無法滿足用戶的需求，目前已有許多室內定位技術[1-3]涌現。隨著IEEE802.11(WiFi)普及[4]，基于WiFi指紋室內定位技術已成為研究的熱點。現有的WiFi指紋室內定位主流方案由兩階段組成：現場勘查和指紋匹配。

RADAR[5]在未考慮隨機信號前提下對WiFi指紋利用歐氏距離和K近鄰算法進行室內目標定位，Horus[6]在此基礎上考慮RP信號概率分布進行定位估計。建立和更新指紋庫是決定基于WiFi指紋定位精度高低的關鍵。通過專業人士來收集WiFi成本昂貴，基于眾包模式[7]可明顯降低指紋地圖構建和維護成本，但會帶來一些新的問題。

由于無線信號在傳播過程存在多徑效應，對環境的變化十分敏感，不同時間采集的數據都存在差異。環境動態對室內定位系統精度的影響是與生俱來的。對于設備異構的室內定位問題[8-9]，同一位置的異構設備檢測到的RSSI值通常有不同的值，這嚴重降低了定位精度[10-11]。為了處理基于WiFi指紋識別的室內定位系統所遇到的設備異質性問題，已有不同的解決方案[8,10-15]。

由于用不同設備獲取RSSI存在差異[10,16]，直接用WiFi信號強度進行預測定位無法達到在現場勘查和指紋匹配的過程中用相同的設備采集WiFi指紋的米級定位精度[5-6,17-18]。因此，僅依賴于絕對信號強度測量來實現異構設備的定位是不可行的，迫切需要開發一種替代絕對RSSI的魯棒指紋定位技術。在文獻[8,15]中提出了一些無校準方法，以避免每個測試設備使用繁瑣的手動RSSI校準程序。協作映射通過訓練在線測量的RSSI值來估計線性映射函數[15]。無監督的學習方法(如在線回歸和期望最大化)已被用來學習映射函數[8]。 然而，以上無校準的指紋定位方法都需要耗時的在線處理過程。解決設備異構問題的另一種方式是定義和使用替代位置指紋，而不是絕對RSSI值。在文獻[10]中提出信號強度差(SSD)，Yang[19]和Jiang[20]提出將RSSI測量向量轉換為相對的RSS排序作為指紋，FreeLoc[19]使用Key-Value機制構造指紋。Jiang[20]提出使用長度為n

通過對WiFi指紋信息分析得知：1)對于同一位置，在容忍一定差異情況下，不同設備檢測的AP的RSSI值形成的變化表現出很高的相似性；2)對于不同位置，在定位匹配過程中不同AP對其準確定位的貢獻不同。不同AP在同一位置測量得到的RSSI值存在差異。其中一些AP對應的RSSI值較大，這些AP對定位的準確性影響較大。

為了實現無指紋校準的室內定位，考慮設備異構和環境動態的影響，本文提出基于層次Levenshtein距離的WiFi指紋距離計算算法。為了刻畫同一位置不同設備檢測的RSSI值的變化的相似性，將不同移動設備采集的RSSI信息按照從大到小進行降序排列索引，將絕對RSSI信息轉化為相對的AP序列，以實現不同設備采集的數據量綱的一致性。同時，對于各數據采集點根據各AP對應的RSSI值的差異性計算其層次能級，將各個AP映射到不同層次能級上，以描述各AP對位置定位的影響等級。聯合各AP層次能級，利用Levenshtein距離來計算AP序列間的距離，實現異構設備的指紋無校準比對。對于需定位的WiFi指紋RSSI信息，利用HLD算法獲取K個近鄰，采用WKNN算法進行預測定位。

1 問題描述

2 基于層次Levenshtein距離的距離算法

Levenshtein距離這個概念由Vladimir Levenshtein在1965年提出，通過最少編輯(修改、刪除和插入)操作次數來計算字符串之間的相似度d(ai,bj)。

式中：ai，bj分別為長度為i，j字符串序列；ai，bj分別為ai，bj字符串中第i，j序號。

結論 在一定噪聲范圍內，接收信號強度之差小于ω，區域內AP序列順序無差異。

證明 以實際環境中常用無線信號傳輸模型——Shadowing模型來論證。

不失一般性，現有接收端到發射機A和B距離分別為dA和dB,則有

對于同一區域的近鄰位置，βA≈βB=β，將式(5)與式(6)相減，有

則有

由式(8)可知：在噪聲存在的情況下，兩接收信號強度差值大于閾值ω(其大小與環境噪聲有關)時，才能區別dA和dB大小。故有兩個接收信號強度之差小于ω，那么認為由這兩個接收信號強度的排序得到的AP序列順序無差異。證畢。

由于AP序列中各AP在WiFi指紋中的能級等級不同，刪除和插入操作需要考慮AP的能級等級。由結論1可知，接收信號強度之差越小，AP序列SeqRPi順序差異越小。修改操作距離通過修改前后兩個AP的RSSI變化差異性來表現。對Levenshtein距離進行修正，得到基于Levenshtein距離的距離函數Dis(SeqRPi,SeqRPj)。

Dis(SeqRPi(m),SeqRPj(n))=

min(Dis(SeqRPi(m-1),SeqRPj(n))+α,

Dis(SeqRPi(m),SeqRPj(n-1))+β,

(9)

Dis(SeqRPi,SeqRPj)=min(Dis(SeqRPi(m-1),

SeqRPj(n))+α,Dis(SeqRPi(m),SeqRPj(n-1))+β,

(10)

(11)

3 性能評價

3.1 實驗準備

我們在5種不同的安卓設備上測試算法性能，這5種設備分別為Huawei G9、Huawei M2、Samsung s6、Samsung note3、Nexus 5。分別對3種不同室內場景(實驗室、圖書館和教室)進行實驗。實驗室的布局分布如圖1(a)，總體布局為15 m×45 m；圖書館的布局分布如圖1(b)，總體布局為78 m×95 m；教室的各層布局分布如圖1(c)，平面總體布局為20 m×120 m，共3層。各實驗場景的WiFi是事先已布置的，本次實驗沒有額外布置AP。考慮環境變化和不同實驗操作者對采集信號的影響，5個志愿者在4個時間段(間隔一個星期、1個月和3個月)內手持上述5種不同的安卓設備各自獨立在不同場景下采集WiFi的RSSI信息，并記錄采集點的地理位置。各個采集點采集時間間隔不等，其跨度在10～25 s。為了客觀評估定位性能，現場勘查的指紋數據庫選擇前3次采集的數據，對同一個位置的多條數據只隨機保留一條記錄，且保證各數據之間的地理位置距離大于等于1 m；定位測試數據選擇第3、4次采集的數據。3個實驗場景下4種不同時間的AP數量變化、指紋數據庫和測試數據數量如表1所示。

表1 3個實驗場景在4種不同時間的AP數量、指紋數據庫和測試數據數量

Table 1 Number of AP in three experiment scenarios at four different times and number of fingerprint database, and test data

實驗場景第1次AP數量第2次AP數量第3次AP數量第4次AP數量指紋數據庫數量測試數據數量實驗室1921192237050圖書館181718181450100教室262126246500300

(a)實驗室

(b)圖書館

(c)教室圖1 實驗場景 Fig.1 Experiment building

3.2 實驗結果

在實驗中，本文提出的方法與3種經典室內定位方法進行對比。第一種方法是文獻[5]提出的RADAR算法。因為不同設備獲取的RSSI差異較大，無法用歐氏距離來計算各RP的相似度，在實驗中將RADAR算法中歐氏距離替換為余弦距離計算各RP的相似度；第二種方法是文獻[19]提出的FreeLoc算法，該算法的基本思想是通過Key-Value機制構造指紋來容忍諸如設備多樣性和信號變化的環境動態；第三種方法是文獻[23]提出的HED算法，該算法利用容錯序列匹配策略來實現動態環境下WiFi指紋定位。采用平均定位誤差和累計定位誤差兩種誤差度量來對比4種室內定位方法的定位性能優越程度。

1)能量層級參數θ、近鄰數目K選擇

為了測試能量層級參數θ、近鄰數目K對定位精度的影響，分別設定θ=3，4，4.5，5，5.5，6，7和K=2，3，4，5，6，對比在三種場景下的定位測試。對于不同場景，通過兩個參數交叉驗證。當θ=5時，算法達到最優。K=5時參數θ對預測定位的影響如圖2所示。結合分析圖3～5的累計定位誤差和表2的平均定位誤差:K=5時，在實驗室和圖書館場景下，其算法達到最優；K=4時，在教室場景下，其算法達到最優。其原因是，實驗室和圖書館場景是二維位置數據信息，教室的數據是立體地理位置。

表2 HLD算法在3種實驗場景下不同K值情況的平均定位誤差

Table 2 Average error of HLD algorithm under different K in three experiment scenarios m

圖3 HLD算法在實驗室環境下的不同K值的累計定位誤差比較Fig.3 Cumulative localization error comparison of HLD algorithm under different K values in laboratory

圖4 HLD算法在圖書館環境下的不同K值的累計定位誤差比較Fig.4 Cumulative localization error comparison of HLD algorithm under different K values in library

圖5 HLD算法在3層教室環境下的不同K值的累計定位誤差比較Fig.5 Cumulative localization error comparison of HLD algorithm under differet K values in three floors classroom

2)與RADAR、FreeLoc和HED算法性能比較

在實驗室和圖書館場景下，HED算法的K取值5；在教室場景下，HED算法的K取值4。RADAR算法中K值和HED算法相同。在3種實驗場景下4種方法累計定位誤差對比如圖6～8所示，表3描述了3種實驗場景下4種方法平均定位誤差對比。RADAR對于平面環境下的定位誤差在4～6 m，2 m內誤差準確度在20%以下，基本達不到定位的效果；對三維環境下的定位效果更差。FreeLoc、HED對于平面環境下的定位誤差在2～4 m，3 m內誤差準確度在50%～60%，但在三維環境下的定位效果3 m內誤差準確精度下降到40%左右。HLD算法整體的平均誤差為1.5 m，2 m內誤差準確度為70%～80%，對空間維度敏感度較低。

在定位過程中，與FreeLoc、HED算法執行效率進行比較，HLD算法時空復雜度比FreeLoc低40%，比HED空間復雜度高10%，時間復雜度相當。

圖6 實驗室環境下的4種方法累計定位誤差比較Fig.6 Cumulative localization error comparison of four methods in laboratory

Tab 3 The average error comparison of four methods in three experiment scenarios m

圖7 圖書館環境下的4種方法累計定位誤差比較Fig.7 Cumulative localization error comparison of four methods in library

4 總結

本文討論了設備異構和室內環境變化情形下的室內定位問題，提出了基于層次Levenshtein距離的WiFi指紋距離計算算法。在無校準情形下，將不同移動設備采集的RSSI信息轉化為AP序列，以解決不同設備獲取的RSSI信息的量綱一致性問題。根據AP對應的RSSI值的差異性計算其層次能級，結合Levenshtein距離計算WiFi指紋之間的距離，提供一種適應異構設備和動態環境下計算各RP間指紋距離的魯棒性方法。對于需定位的WiFi指紋RSSI信息，采用WKNN算法進行預測定位。實驗中，為了驗證算法的魯棒性和有效性，在3種不同類型的室內環境中用5種不同的移動設備來采集WiFi的RSSI信息，其定位的平均精度達1.5 m，2 m內誤差準確度在70%～80%，對空間維度敏感度較低。

[1]GU Y, LO A, NIEMEGEERS I. A survey of indoor positioning systems for wireless personal networks[J]. IEEE commun. surveys and tutorials, 2009,11(1): 13-32.

[2]HARLE R. A survey of indoor inertial positioning systems for pedestrians[J]. IEEE commun. surveys & tutorials, 2013,15(3): 1281-1293.

[3]SUBBU K P. Analysis and status quo of smart-phone-based indoor localization systems[J]. IEEE wireless commun, 2014,21(4): 106-112.

[4]石柯,陳洪生,張仁同.一種基于支持向量回歸的802.11無線室內定位方法[J].軟件學報,2014,25(11): 2636-2651. SHI Ke, CHEN Hongsheng, ZHANG Rentong. Indoor location method based on support vector regression in 802.11 wireless environments[J]. Journal of software, 2014,25(11): 2636-2651.

[5]BAHL P, PADMANABHAN V. RADAR: an in-building rf-based user location and tracking system[C]//Proc. Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Tel Aviv, Israel, 2000:775-784.

[6]YOUSSEF M, AGRAWALA A . The horus wlan location determination system[C]//Proceedings of the 3rdInternational Conferenceon Mobile Systems, Applications, and Services,Washington, USA, 2005: 205-218.

[7]WANG B, CHEN Q, YANG L T, et al. Indoor smartphone localization via fingerprint crowdsourcing: challenges and approaches[J]. IEEE wireless communication, 2016(6):82-89.

[8]TSUI A W, CHUANG Y H, CHU H H. Unsupervised learning for solving rss hardware variance problem in wifi localization[J].Mobile networks and applications, 2009,14(5): 677-691.

[9]CHENG H, WANG F, TAO R, et al. Clustering algorithms research for device-clustering localization[C]//2012 International Conference on Indoor Positioning and Indoor Navigation (IPIN),Sydney, Australia, 2012:1-7.

[10]MAHTAB HOSSAIN A , JIN Y ,SOH W S, et al. SSD: a robust RF location fingerprint addressing mobile devices heterogeneity[J]. IEEE transactions on mobile computing, 2013,12(1): 65-77.

[11]PARK J G, CURTIS D, TELLER S, et al. Implications of device diversity for organic localization[C]//The 30th IEEE International Conference on Computer Communications, Shanghai, China, 2011:3182-3190.

[12]FIGUERA C, ROJO-LVAREZ J L, MORA-JIMNEZ I, et al. Time-space sampling and mobile device calibration for wifi indoor location systems[J]. IEEE transactions on mobile computing, 2011,10(7):913-926.

[13]HAEBERLEN A, FLANNERY E, LADD A M, et al. Practical robust localization over large-scale 802.11 wireless networks[C]//Proceedings of the 10th Annual International Conference on Mobile Computing and Networking, Philadelphia, USA, 2004: 70-84.

[14]KJRGAARD M B. Indoor location fingerprinting with heterogeneous clients[J]. Pervasive and mobile computing, 2011, 7(1):31-43.

[15]DELLA ROSA F, LEPPAKOSKI H, BIANCULLO S, et al. Ad-hoc networks aiding indoor calibrations of heterogeneous devices for fingerprinting applications[C]//2010 International Conference on Indoor Positioning and Indoor Navigation (IPIN), Zurich, Switzerland, 2010: 1-6.[16]CHEN L H , WU E H K, JIN M H, et al. Homogeneous features utilization to address the device heterogeneity problem in fingerprint localization[J]. IEEE sensors journal, 2014,14(4): 998-1005.

[17]ZOU H , LU X , JIANG H,et al. A fast and precise indoor localization algorithm based on an online sequential extreme learning machine[J]. Sensors, 2015,15(1): 1804-1824.

[18]LYMBEROPOULOS D, LIU J, YANG X, et al. A realistic evaluation and comparison of indoor location technologies: experiences and lessons learned[C] //Proceedings of the 14th International Conference on Information Processing in Sensor Networks, Catania, Italy, ACM, 2015: 178-189.

[19]YANG S. Freeloc: calibration-free crowdsourced indoor localization[C]//The 32th IEEE International Conference on Computer Communications, Turin, Italy, 2013: 2481-2489.

[20]JIANG Y. Ariel: automatic wi-fi based room fingerprinting for indoor localization[C]//Proc ACM Conf. Ubiquitous Computing, Pittsburgh, Pennsylvania, United States, 2012:441-50.

[21]SHU Y, HUANG Y, ZHANG J, et al. Gradient-based fingerprinting for indoor localization and tracking[J]. IEEE transactions on industrial electronics, 2016,63(4):2424-2433.

[22]ZOU H, HUANG B, LU X, et al. Standardizing location fingerprints across heterogeneous mobile devices for indoor localization[C]//IEEE Wireless Communications and Networking Conference (WCNC 2016). Doha, Qatar, 2016:1-6.

[23]GU Y, CHEN M, REN F, et al. HED: handling environ-mental dynamics in indoor wifi fingerprint localization[C]//IEEE Wireless Communications and Networking Conference (WCNC 2016), Doha, Qatar, 2016: 5-10.

An fingerprint calibrations-free indoor localization method based on hierarchical Levenshtein distance

HE Fugui1,3， YANG Zheng2， WU Chenshu2， ZHAO Shu3， ZHOU Xiancun1

(1. School of Electronics and Information Engineering, West Anhui University, Lu’an 237012, China; 2. Institute of Trustworthy Network and System, School of Software, Tsinghua University, Beijing 100084, China; 3. Institute of Intelligent Computing and Knowledge Engineering, Anhui University, Hefei 230039, China)

In the era of mobile computing, location-based services have become extremely important for a wide range of applications, and various wireless indoor localization techniques have been emerging. Amongst these techniques, WiFi fingerprint-based indoor localization is one of the most attractive because of the wide deployment and availability of WiFi infrastructure. The accuracy of indoor localization is affected by two main factors: equipment heterogeneity and environmental dynamics. To solve the obove two problems, an algorithm based on hierarchical Levenshtein distance (HLD) was proposed to realize calibration-free fingerprint comparison of heterogeneous devices.

signal strength indication(RSSI) information collected via different mobile devices was transformed into an AP sequence. The difference in the Received signal strength indication RSSI values was used to calculate the hierarchical energy level of each access point(AP). Next, the distance between the WiFi fingerprints was calculated using the Levenshtein distance. To locate WiFi fingerprint RSSI information, the HLD algorithm was used to obtainKneighbors and the weightedKnearest neighbor(WKNN) algorithm was used to predict its position. Five different mobile devices were used to collect WiFi RSSI information in three different types of indoor environments to verify the robustness and effectiveness of the algorithm. The average localization accuracy was 1.5 m.

indoor localization; WiFi fingerprint; heterogeneous device; fingerprint calibration-free; Levenshtein distance

10.11992/tis. 201704031

http://kns.cnki.net/kcms/detail/23.1538.TP.20170703.1854.014.html

2017-04-23. 網絡出版日期：2017-07-03.

國家自然科學基金項目(61572366, 61303209, 61522110, 61402 006,61673020)；2016年安徽省高校優秀中青年骨干人才國內外訪學研修重點項目(gxfxZD2016190)；安徽大學信息保障技術協同創新中心2015年度開放課題(ADXXBZ201504).

何富貴. E-mail：fuguihe@163.com.

TP181

A

1673-4785(2017)03-0422-08

何富貴，男，1982年生，副教授，主要研究方向為移動計算、室內定位和粒計算。發表學術論文10余篇。

楊錚，男，1983年生，副教授，博士生導師，研究方向為無線網絡與移動計算，包括傳感網、Mesh網絡、室內定位、群智感知等。發表論文60余篇，其中CCF推薦A類論文40余篇；出版中、英文學術專著各1部。獲得國家自然科學獎二等獎。

吳陳沭，男，1989年生，博士，研究方向為無線網絡與移動計算，包括室內定位、群智感知等。