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

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

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

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

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

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

室內(nèi)定位;位置指紋;近鄰選擇算法;二部分網(wǎng)絡(luò);相似度

1 相關(guān)研究

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

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

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

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

2 SKNN算法

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

2.1 網(wǎng)絡(luò)的建立

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

圖1 SKNN算法流程圖

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

圖3 “AP-指紋”網(wǎng)絡(luò)

2.2 相似度的計算

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

圖4 奇異點示意圖

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

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

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

2.3 基于相似度的加權(quán)歐式距離

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

2.4 位置估計

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

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

圖5 商場平面圖

3.1 離線階段

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

圖6 某一AP的RSSI值分布圖

3.2 在線定位階段及結(jié)果分析

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

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

圖7 KNN和SKNN算法對比圖

圖8 三種區(qū)域下誤差分布率

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

表1 定位誤差比較

4 結(jié)束語

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

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 席瑞,李玉軍,侯孟書.室內(nèi)定位方法綜述.計算機科學(xué),2016,43(4):1–6,32.

3 曹世華.室內(nèi)定位技術(shù)和系統(tǒng)的研究進展.計算機系統(tǒng)應(yīng)用,2013,22(9):1–5.

4 鄧志安.基于學(xué)習(xí)算法的WLAN室內(nèi)定位技術(shù)研究[博士學(xué)位論文].黑龍江:哈爾濱工業(yè)大學(xué),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 蔡朝暉,夏溪,胡波,等.室內(nèi)信號強度指紋定位算法改進.計算機科學(xué),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 王躍,崔維嘉,王大鳴,等.基于模擬退火聚類的室內(nèi)定位算法.信息工程大學(xué)學(xué)報,2016,17(2):161–164.

11 都伊林.一種模糊聚類KNN位置指紋定位算法.微型機與應(yīng)用,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)的指紋定位技術(shù)因其硬件成本和計算開銷低而被廣泛使用,常用的匹配算法有概率法、神經(jīng)網(wǎng)絡(luò)法、支持向量機法和近鄰選擇算法.其中概率法、神經(jīng)網(wǎng)絡(luò)法和支持向量機法的算法復(fù)雜難以實現(xiàn),并且計算量大,不能滿足用戶對實時性的要求.因此本文在后面章節(jié)將主要針對近鄰選擇算法進行研究和改進.

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

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

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

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

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