基于相似度的K階臨近定位算法①

馬文麗, 李世寶, 張志剛, 楊喜鵬, 王升志, 張 鑫

(中國石油大學(華東)計算機與通信工程學院,青島 266580)

基于相似度的K階臨近定位算法①

馬文麗, 李世寶, 張志剛, 楊喜鵬, 王升志, 張 鑫

(中國石油大學(華東)計算機與通信工程學院,青島 266580)

基于WIFI位置指紋的定位系統能實現較高精度的室內定位,其中基于接收信號強度指示(RSSI)的近鄰選擇算法在進行室內定位時容易入奇異點,導致定位精度降低.針對該問題,本文提出了一種基于相似度的K階臨近定位算法(SKNN).該算法借鑒二部分網絡中求解節點相似性的思想,建立位置指紋與AP之間的二部分網絡,并提出一個相似度參數,用該參數去修正K階臨近定位算法.實驗結果表明,本文提出的SKNN算法可以有效的降低奇異點對定位結果的影響,提高定位精度,80%的定位誤差均在2 m以內,且在大場景中效果明顯.

室內定位;位置指紋;近鄰選擇算法;二部分網絡;相似度

1 相關研究

近鄰選擇算法[4]由于計算簡單、易于實現而得到廣泛應用,其核心在于通過計算歐氏距離尋找與待測點距離最近的一個或多個采樣點.常見的近鄰選擇算法有最近鄰法(Nearest Neighborhood,NN),K階臨近法(K-Nearest Neighborhood,KNN),加權K階臨近法(Weighted K-Nearest Neighborhood,WKNN),聚類過濾法(Cluster Filtered KNN,CFK)等.

NN算法是所有基于RSSI距離近鄰選擇算法中最簡單的一種.將移動端采集到的RSSI向量與指紋數據庫中所有指紋點進行匹配,計算歐氏距離Dist,距離最小的點對應的位置信息(xi,yi)即為對待測點的位置估計.RADAR系統[5]使用NN算法進行指紋的匹配與計算,實現了2～5米的定位精度.KNN算法[6]是對NN算法的改進,用NN算法中計算距離的方法計算得到具有最小距離的個指紋點(xi,yi),i∈(1,K),那么待測點的位置估計就是這K個指紋點位置的質心有效解決偶然性導致較大定位誤差的問題.為了提高了定位精度,文獻[7]提出WKNN算法,在選出K個相近的指紋后,不是直接計算K個點的質心,而是先根據每個指紋點的RSSI值計算它對待測點的貢獻度,將貢獻度作為權值分配給各個指紋點,然后求K個指紋點的加權質心,質心的位置即為最終的位置估計,能有效提高定位精度.由于指紋數據庫中存在RSSI向量相似但實際位置相距較遠的指紋點,將與待測點的RSSI向量值相似但實際位置相距較遠的指紋點稱為奇異點,上述近鄰選擇算法在進行指紋匹配時容易入奇異點,從而導致定位精度降低.

文獻[8]針對指紋數據庫中奇異點,在求解信號歐氏距離時進行加權處理.Jun MA等人提出聚類過濾KNN算法[9],該算法針對利用聚類算法濾除奇異點.王躍等人提出一種基于模擬退火聚類的室內定位算法[10].該算法采用模擬退火聚類的方法消除了具有一定特征相似性的奇異點.文獻[11]提出采用模糊K-均值聚類的方法對KNN方法進行改進,利用K-均值聚類奇異點進行篩選.

通過聚類算法濾除奇異點的方法時間開銷是非常大的,在具體應用上不能滿足用戶對實時性的要求.聚類算法也不能保證達到最優的聚類效果,兩種采用K-均值聚類的算法在聚類的時結果受初始值的影響大,并且容易出現局部最值的問題.雖然一定程度上減小了奇異點的影響,但并沒有提高匹配定位的效率.針對上述問題,本文借鑒二部分網絡中判斷節點之間相似度的思想,將指紋點和AP建成二部分網絡,考慮指紋點之間共同連接的AP數后對定位的影響,提出基于相似度的KNN算法(Similarity-beased K-Nearest Neighborhood,SKNN).

2 SKNN算法

針對奇異點影響近鄰選擇算法定位精度的問題,本文對原有的階臨近定位算法進行改進,提出了SKNN算法.在算法設計過程中,需要解決的難點問題是分析奇異點影響定位精度的根本原因、建立指紋點和AP的二部分網絡和相似度的計算.針對以上問題,將該算法的設計分為以下四個步驟:網絡的建立、相似度的計算、基于相似度的加權歐氏距離計算和真實位置估計.算法流程圖如圖1所示.

2.1 網絡的建立

鑒于上述思想,本文將指紋匹配的問題用二部分網絡中求解節點相似性的思想解決,首先將指紋數據庫中的每個指紋點位置作為X集合,AP點的集合作為Y集合,指紋點Xi中收到APj的信號即為Xi與Yj之間產生一條連邊Eij,將實際網絡表示成二部分網絡,如圖3,用不同指紋點之間共同連接的AP的數后來衡量兩個指紋點之間的相似性.本文入一個“鄰居”的概念:在“AP-指紋”網絡中,與指紋點有連邊的AP叫做該指紋點的鄰居節點,如果兩個指紋節點都跟同一個AP相連接,則將這個AP稱為兩個指紋節點的共同鄰居.

圖1 SKNN算法流程圖

圖2 “用戶-商品”二部分圖

圖3 “AP-指紋”網絡

2.2 相似度的計算

在理想的定位環境中,位置越接近的點RSSI向量值就越相似.但在實際室內環境中,信號強度不一定完全由物理位置的遠近造成,也可能由信號強度自身的波動或反射折射等因素造成,通過歐式距離篩選出來的點并不一定全都是距離待測點實際位置接近的點,通常也會包含RSSI值相似但實際位置卻相距很遠的指紋點,如圖4所示,待測點為Z點,運用KNN算法定位時,根據歐式距離的大小篩選出A、B、C三個點,則三個點的質心M即為最終的位置估計.指紋數據庫中的D點與C點的RSSI值相似但與C的實際位置相距較遠,且有比C點更小的歐氏距離,運用KNN(K=3)算法定位時,D點就作為一個奇異點被入,A、B、D三點的質心N為最終定位結果,比較M和N的位置可知:奇異點的入導致了較大的定位誤差.

圖4 奇異點示意圖

在“用戶-商品”二部分網絡中,如果兩個用戶的共同鄰居越多,這兩個用戶的相似性越高,基于這種相似性為用戶推薦更多的有用信息.同理,基于RSSI的指紋匹配算法的后的是在指紋數據庫中找出與待測點相似的K個指紋點.對“AP-指紋”網絡進行分析可知:在歐氏距離相同的情況下,實際距離越相近的兩個指紋點,它們的共同鄰居節點數占鄰居節點總數的比例越高.本文定義了一個“相似度”參數:

即鄰居節點總數與共同鄰居節點數的比值,用X表示待測點,Y表示指紋數據庫中的指紋點.τx、τy分別表示與X,Y相連的AP,Sα表示X與Y共同鄰居數后,Sβ表示X與Y各自鄰居節點的總和.式(1)中m是兩個集合節點數后的比值,表示網絡中的X與Y節點連接的AP的匹配程度.的值越接近于1,證明兩個節點的相似度越高;反之m的值越大,節點相似度越低.

入相似度之后可以有效的減小奇異點對最終定位結果的影響.在奇異點與臨近點有相同歐氏距離的情況下,奇異點會乘以一個遠遠大于1的相似度,會將原先得到的歐氏距離放大很多倍;臨近點則會乘以一個接近于1的相似度,歐氏距離基本不變,由于算法需要將歐式距離最小的K個點的質心作為最終的位置估計,所以相似度的入會大幅降低奇異點對定位結果的影響.

2.3 基于相似度的加權歐式距離

定義當前時刻移動終端在待測點接收到的各個AP的RSSI向量為Rt,rn是移動終端接收到的APn的RSSI值;指紋數據庫中的向量進行匹配,其中fin表示在第i個參考位置處接收到的APn的指紋信息.則當前待測點與指紋數據庫中第i個指紋點的歐氏距離表示為公式(2):

2.4 位置估計

3 實驗及結果分析

為驗證SKNN算法的性能,在一個大型商場進行定位實驗,商場的平面圖如圖5所示.利用各個商家已經部署的AP(在整個商場中共搜索到83個可用的AP),移動采集終端選擇OPPOr9手機.

圖5 商場平面圖

3.1 離線階段

離線階段即指紋采集階段.指紋采集時,將圖5所示的整個區域劃分成多個1 m×1 m的網格,每個網格采集一個指紋樣本,共采集900個指紋數據.為了減小RSSI時變帶來的影響,在各個網格多次采集各個AP的信號強度.通過大量實測數據分析,如圖6所示在確定的網格內測得特定AP的RSSI值會在56 dB附近波動,所以本文離線階段采用高斯濾波技術,舍棄概率比較低的RSSI值,對概率高的RSSI值求平均,從而降低信號的隨機誤差.

圖6 某一AP的RSSI值分布圖

3.2 在線定位階段及結果分析

在線定位階段,用戶手持移動終端在定位區域進行定位,采集當前位置各個接入點的RSSI值,組成測試集,再將測試集與指紋數據庫中的訓練集進行搜索匹配,匹配算法采用經典KNN算法和SKNN算法.

由于本文提出的SKNN算法適用于較大區域,為了驗證其在不同大小的區域中的效果,在同一個實驗場景中選擇三個大小不同的區域進行了三次實驗,三個區域為map1、map2和map3,面積分別為40 m2、80 m2和200 m2.實驗誤差及分布率示意圖如圖8所示,SKNN算法大場景中的定位效果優于小場景.

圖7 KNN和SKNN算法對比圖

圖8 三種區域下誤差分布率

SKNN算法與KNN算法定位誤差比較如表1所示,從表1可以看出,用SKNN算法計算得到的坐標誤差要小于KNN算法.

表1 定位誤差比較

4 結束語

本文針對基于RSSI的近鄰選擇算法在指紋匹配時入奇異點導致定位精度降低的問題,建立指紋點與AP之間的二部分網絡,基于二部分網絡中求解節點相似性的思想提出相似性參數,用該參數修正經典KNN算法.該算法可以有效的減弱奇異點對定位結果的影響,減小定位誤差,且在大場景中效果更明顯.

1 Chintalapudi K,Padmanabha Iyer A,Padmanabhan VN.Indoor localization without the pain.Proc.of the 16th Annual International Conference on Mobile Computing and Networking.Chicago,Illinois,USA.2010.173–184.

2 席瑞,李玉軍,侯孟書.室內定位方法綜述.計算機科學,2016,43(4):1–6,32.

3 曹世華.室內定位技術和系統的研究進展.計算機系統應用,2013,22(9):1–5.

4 鄧志安.基于學習算法的WLAN室內定位技術研究[博士學位論文].黑龍江:哈爾濱工業大學,2012:10–36.

5 Bahl P,Padmanabhan VN.RADAR:An in-building RF-based user location and tracking system.Proc.of the 19th Annual Joint Conference of the IEEE Computer and Communications Societies.Tel Aviv,Israel.2000,2:775–784.

6 Sun YX,Liu M,Meng MQH.WiFi signal strength-based robot indoor localization.Proc.of the 2014 IEEE International Conference on Information and Automation (ICIA).Hailar,China.2014.250–256.

7 Brunato M,Battiti R.Statistical learning theory for location fingerprinting in wireless LANs.Computer Networks,2005,47(6):825–845.[doi:10.1016/j.comnet.2004.09.004]

8 蔡朝暉,夏溪,胡波,等.室內信號強度指紋定位算法改進.計算機科學,2014,41(11):178–181.[doi:10.11896/j.issn.1002-137X.2014.11.035]

9 Ma J,Li XS,Tao XP,et al.Cluster filtered KNN:A WLAN-based indoor positioning scheme.Proc.of the 2008 International Symposium on a World of Wireless,Mobile and Multimedia Networks.Newport Beach,CA,USA.2008.2008.1–8.

10 王躍,崔維嘉,王大鳴,等.基于模擬退火聚類的室內定位算法.信息工程大學學報,2016,17(2):161–164.

11 都伊林.一種模糊聚類KNN位置指紋定位算法.微型機與應用,2012,31(23):55–58.[doi:10.3969/j.issn.1674-7720.2012.23.017]

Similarity-Based K-Nearest Neighborhood Location Algorithm

MA Wen-Li,LI Shi-Bao,ZHANG Zhi-Gang,YANG Xi-Peng,WANG Sheng-Zhi,ZHANG Xin
(Department of Computer and Communication Engineering,China University of Petroleum (East China),Qingdao 266580,China)

The positioning system based on WIFI location fingerprint can achieve high precision indoor location.The neighbor selection algorithm based on

Signal Strength Indicator (RSSI)is easy to introduce singular points when locating indoors,which leads to the decrease of positioning accuracy.To solve this problem,this paper proposes a Similarity-based K-Nearest Neighborhood Location Algorithm (SKNN).Referring to the idea used to solve the problem of similarity of nodes in bipartite networks,this algorithm builds a bipartite network between the location fingerprint and the AP.It proposes a similarity parameter which can be used to modify the K-Nearest Neighborhood localization algorithm.The experimental results show that the SKNN algorithm proposed in this paper can effectively reduce the influence of singular points on the positioning results and improve the positioning accuracy,with 80% of the positioning errors within 2m,and the effect is obvious in the large scene.

indoor localization;location fingerprint;nearest neighbor selection algorithm;bipartite network;similarity

signal Strength Indicator,RSSI)的指紋定位技術因其硬件成本和計算開銷低而被廣泛使用,常用的匹配算法有概率法、神經網絡法、支持向量機法和近鄰選擇算法.其中概率法、神經網絡法和支持向量機法的算法復雜難以實現,并且計算量大,不能滿足用戶對實時性的要求.因此本文在后面章節將主要針對近鄰選擇算法進行研究和改進.

馬文麗,李世寶,張志剛,楊喜鵬,王升志,張鑫.基于相似度的K階臨近定位算法.計算機系統應用,2017,26(9):165–169.http://www.c-sa.org.cn/1003-3254/5982.html

① 基金項后:中國自然科學基金青年基金(61402433);山東省自然科學基金面向項后(ZR2014FM017);中央高?；究蒲袠I務費專項資金(15CX05025A)

2016-12-29;采用時間:2017-02-13

隨著情景感知、環境智能等應用需求的增加,人們對用戶位置信息精度的要求也在不斷提高.室外環境中,全球定位系統(Global Positioning System,GPS)、網絡輔助全球衛星定位系統(Assisted Global Positioning System,A-GPS)和蜂窩網定位系統等可以滿足絕大部分的定位需求.但是,在室內環境中,由于建筑物的遮擋,使得GPS等已有的定位系統不再適用.然而,在現實生活中,人們對室內定位服務需求越來越強烈,例如在商場導購、博物館導航、地下車庫導航、導盲等方面,均開始熱切關注室內定位的問題,因此,研究一種適用于室內環境的定位系統是很有必要的.

基于WIFI信號的室內定位方法[1]因其成本低廉、硬件易于實現、精度高、定位過程簡單成為研究的熱點.按照定位原理可以劃分為基于測距[2]的定位方法和基于指紋的定位方法.室內環境中無線信號的NLOS現象導致基于測距的定位方法在進行估算距離時易產生誤差.基于指紋的定位方法利用了WIFI信號空間位置差異性進行定位,有效的減小NLOS現象對定位結果的影響.