吳 赟, 蔣新華, 齊雁飛, 蔣學(xué)芹

(1.東華大學(xué) 信息科學(xué)與技術(shù)學(xué)院,上海 201620;2.上海航天電源技術(shù)有限責(zé)任公司 軌道交通事業(yè)部,上海 201615)

基于加權(quán)余弦相似度的WiFi指紋室內(nèi)定位

吳 赟1, 蔣新華2, 齊雁飛1, 蔣學(xué)芹1

(1.東華大學(xué) 信息科學(xué)與技術(shù)學(xué)院,上海 201620;2.上海航天電源技術(shù)有限責(zé)任公司 軌道交通事業(yè)部,上海 201615)

基于WiFi的室內(nèi)定位具有低成本、易部署、覆蓋范圍廣、精度高等優(yōu)點,成為室內(nèi)定位技術(shù)研究的熱點.WiFi指紋定位法可以對抗多徑的影響,具有較高的定位精度.但是由于智能移動終端的種類繁多,使得室內(nèi)定位系統(tǒng)離線建立的指紋數(shù)據(jù)庫難以兼容不同的智能移動設(shè)備,降低了定位系統(tǒng)的適用性.為解決此問題,提出了加權(quán)余弦相似度算法,使用信號強度的加權(quán)余弦相似度作為匹配特征.實測表明,采用加權(quán)余弦相似度算法可有效解決終端差異性,提高了室內(nèi)定位系統(tǒng)的精度和普適性.

室內(nèi)定位; 終端差異; 加權(quán)余弦相似度; WiFi

0 引 言

現(xiàn)今,WLAN已經(jīng)覆蓋了人們活動的絕大多數(shù)室內(nèi)環(huán)境.基于接收信號強度(RSS)的WLAN定位不用添加其他硬件裝置,僅通過軟件編程就可以在任何一款內(nèi)置無線模塊的智能移動設(shè)備上實現(xiàn),并且利用指紋法可以有效降低多徑傳播和陰影衰落對定位系統(tǒng)的影響[1-2],因此成為目前研究的熱點.

隨著科技的發(fā)展,智能移動終端的種類越來越豐富,不同種類的智能移動終端采用不同標(biāo)準(zhǔn)的無線模塊.這使得室內(nèi)定位系統(tǒng)在線定位階段所用的智能移動設(shè)備和離線階段建立數(shù)據(jù)庫所用的智能移動設(shè)備存在種類差異,導(dǎo)致在線階段測量的RSS向量與所建立的指紋庫不能有效匹配,降低了定位系統(tǒng)的普適性.為解決終端差異問題,提高定位系統(tǒng)的定位精度和普適性,本文作者提出一種基于加權(quán)余弦相似度算法的WiFi指紋定位技術(shù),使用信號強度的加權(quán)余弦相似度作為匹配特征,消除了終端差異的影響.

1 系統(tǒng)總體設(shè)計

系統(tǒng)的定位原理框圖如圖1所示,離線階段把室內(nèi)空間按照適當(dāng)?shù)拈g隔均勻地劃分為不同的區(qū)域,形成參考點網(wǎng)格,在每一個參考點處接收周圍無線接入點(AP)的RSS并建立樣本向量,每個參考點的位置信息與對應(yīng)的RSS樣本向量構(gòu)成位置指紋,然后,將所有參考點的位置指紋信息存儲起來構(gòu)成指紋庫.建立指紋庫的具體過程如下:

假設(shè)在室內(nèi)區(qū)域有L個參考點,并且每個參考點處可以探測N個AP的RSS,則第i個參考點處指紋信息向量為Ri={xi,yi,bi1,bi2,…,biN},其中i∈(1,2,…,L),(xi,yi)為第i 個參考點處的位置坐標(biāo).參考點的數(shù)量和有效性直接影響著定位系統(tǒng)在線階段的定位精度,定位精度隨著參考點的增加有所提高,但是,參考點增多使離線階段搜集指紋信息的工作量增大,因此,離線階段應(yīng)該根據(jù)室內(nèi)環(huán)境合理地選擇參考點的數(shù)量.在線定位階段,首先通過移動設(shè)備在待測區(qū)域?qū)崟r采集AP的RSS向量,然后,將采集的RSS向量與離線指紋庫中的數(shù)據(jù)進(jìn)行匹配,得出定位結(jié)果[3-7].

圖1 WiFi指紋定位系統(tǒng)的原理框圖

2 室內(nèi)定位算法

經(jīng)研究發(fā)現(xiàn),不同設(shè)備接收到AP的RSS向量不同,終端差異使得基于歐式距離算法的室內(nèi)定位系統(tǒng)的定位精度降低,甚至?xí)霈F(xiàn)定位失敗的情況.但是RSS向量的趨勢相同,RSS向量間歐式距離的劇烈變化并沒有引起向量間夾角發(fā)生劇烈變化,可以引入余弦相似度來衡量向量的相似性,余弦相似度算法公式如下:

(1)

式中,a為在線階段移動終端在待測區(qū)域內(nèi)實時采集到的來自N 個AP的RSS向量,bi為準(zhǔn)備階段所構(gòu)建的指紋庫中第i個參考點處收集到的周圍的N個AP的RSS向量,采用余弦相似度算法計算出在線階段信號強度向量與指紋庫中向量的相似性,相似程度越大,兩個參考點就越匹配[8],然后,對結(jié)果進(jìn)行排序,選取相似程度較大的前K個參考點.將選取的K個參考點的位置坐標(biāo)作均值處理,估算出移動定位終端在待測區(qū)域的位置坐標(biāo),即:

(2)

(2) 式的余弦相似度算法采用相同權(quán)重對選取的K個參考點位置作均值處理,獲得最終的位置坐標(biāo),但實際上K個參考點的位置信息具有不同的可信度,余弦相似度大的參考點提供的位置信息將更可信.為了更有效地利用不同參考點的信息,提出根據(jù)余弦相似度的大小,賦予不同的權(quán)重值來估算待測點的位置坐標(biāo),所提出的這種方法稱為加權(quán)余弦相似度算法.假設(shè)待測點N與K個參考點的余弦相似度的大小分別為S1,S2,…,SK(按余弦相似度降序排列),相似度越大,在位置估算時所作的貢獻(xiàn)越大,權(quán)重值也越大.

余弦相似度的取值范圍為從[-1,1],考慮到參考點的權(quán)重值沒有負(fù)值的情況,首先把相似度轉(zhuǎn)化為正數(shù),即:

(3)

第i個參考點的權(quán)重值wi可以表示為:

(4)

式中,k為臨近的參考點數(shù)目,利用不同參考點估算待測點的位置坐標(biāo),即:

(5)

從(5)式可知,加權(quán)余弦相似度算法首先考慮相似度較大的參考點,權(quán)重值的大小能更好地反映待測點與參考點間的關(guān)系.

基于加權(quán)余弦相似度的室內(nèi)定位的流程分為以下步驟:

離線階段:

1) 布置實驗場景,在定位區(qū)域布置好AP.

2) 在實驗區(qū)域內(nèi)按照間隔為1m的間隔劃分網(wǎng)格,每個網(wǎng)格的4個頂點作為離線階段建立指紋庫的參考點.

3) 基于空間因素和時間因素對RSS的影響,在每個參考點處的東、西、南、北4個方向上分別采集120 次,然后對這120次的采樣值去奇異值求平均值,結(jié)合RSS平均值和參考點的位置坐標(biāo)信息,構(gòu)成系統(tǒng)的指紋數(shù)據(jù)庫.

在線階段:

1) 移動定位終端向服務(wù)器發(fā)送連接請求并定位,然后向服務(wù)器發(fā)送RSS向量.

2) 服務(wù)器接收RSS向量后通過 (5) 式的加權(quán)余弦相似度算法與離線階段指紋庫進(jìn)行匹配,估算待測點的坐標(biāo),并將坐標(biāo)信息發(fā)送到移動定位終端.

3) 移動定位終端獲得位置坐標(biāo)后,在室內(nèi)地圖上實時顯示.

3 結(jié)果分析

為了驗證算法的實際效果,比較了沒有終端差異時加權(quán)余弦相似度算法與WKNN算法的精度,并且比較了存在終端差異時加權(quán)余弦相似度算法、余弦相似度算法、WKNN算法以及指紋差值法[5]的精度.實驗環(huán)境為東華大學(xué)2號綜合實驗樓第四層的兩間教室,在室內(nèi)部署5個AP覆蓋試驗區(qū)域,如圖2所示.

圖2 實驗環(huán)境

實驗中離線階段選取紅米Note建立指紋庫,指紋庫主要包含采樣點的位置坐標(biāo)、AP的BasicServiceSetIdentifier(BSSID)和AP的RSS.在線階段分別采用紅米Note手機和酷派5216s手機在實驗區(qū)域進(jìn)行數(shù)據(jù)采集.圖3為不存在終端差異時,采用WKNN算法和加權(quán)余弦相似度算法定位精度的對比,由圖3可見在不存在終端差異時,兩種算法的定位精度相近.

圖4為存在終端差異時選用加權(quán)余弦相似度算法、WKNN算法定位[7]和余弦相似度算法[8]的精度對比.由圖4可見存在終端差異時,通過權(quán)值對余弦相似度算法進(jìn)行改進(jìn)后,系統(tǒng)在3m內(nèi)的定位精度較WKNN算法提高了3.8%.差值指紋法弱化了RSS向量和空間位置的關(guān)系,導(dǎo)致采用差值法時定位精度并不能夠達(dá)到人們的需求.

圖3 無終端差異時不同算法定位精度

圖4 存在終端差異時不同算法定位精度

4 結(jié) 論

為了解決室內(nèi)定位的終端差異性問題,提出了使用加權(quán)余弦相似度算法進(jìn)行指紋點匹配,從而消除了由于不同終端接收信號強度不同造成的定位誤差.實驗結(jié)果顯示,加權(quán)余弦相似度算法的使用不僅可以解決終端差異度對定位精度的影響,同時相比現(xiàn)有方法(余弦相似度和指紋差值法)具有更好的定位表現(xiàn).

[1] Liu H,Darabi H,Banerjee P,et al.Survey of wireless indoor positioning techniques and systems [J].IEEE Transactions on Applictions and Reviews,2007,37(6):1067-1080.

[2] 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.

[3] Brumitt B,Meyers B,Krumm J,et al.Easy Living:technologies for intelligent environments [J].Lecture Notes in Computer Science,2000,1927(2-3):12-29.

[4] 朱曉鳳.基于核函數(shù)的特征級融合及在手部特征識別上的應(yīng)用 [D].北京:北京交通大學(xué),2009.

Zhu X F.Feature level fusion based on kernel function and its application in hand feature recognition [D].Beijing:Beijing Jiaotong University,2009.

[6] Borenovic M,Neskovic A,Budimir D.Space partitioning strategies for indoor WLAN positioning with cascade-connected ANN structures [J].International Journal of Neural Systems,2011,21(1):1-15.

[7] Youssef M,Agrawala A.Handling samples correlation in the horus system [C].Twenty-third Annual Joint Conference of the IEEE Computer and Communications Societies,2004 (2):1023-1031.

[8] 趙聰.基于位置指紋的WLAN室內(nèi)定位算法研究 [D].哈爾濱:哈爾濱工業(yè)大學(xué),2014.

Zhao C.Research on WLAN indoor location algorithm based on location fingerprint [D].Harbin:Harbin Institute of Technology,2014.

[9] Castro P,Chiu P,Kremenek T.A probabilistic room location service for wireless networked environments [C]//ACM.Ubi Comp′01 Proceedings of the 3rd international conference on Ubiquitous Computing,Atlanta:ACM,2001.

(責(zé)任編輯：包震宇)

WiFi fingerprint indoor localization based on weighted cosine similarity

Wu Yun1, Jiang Xinhua2, Qi Yanfei1, Jiang Xueqin1

(1.College of Information Science & Technology,Donghua University,Shanghai 201620,China;2.Rail Transit Division,Shanghai Aerospace Power Technology,Co.,Ltd.,Shanghai 201615,China)

Benefiting from the low cost,easy deployment,wide coverage and high precision,the WiFi based indoor positioning has attracted a lot of research attentions recently.The fingerprint location method has high location accuracy since it can combat the multipath effect.But because of the wide variety of intelligent mobile terminals,it is difficult to be compatible with different intelligent mobile devices,which reduces the universality of the positioning system.In order to overcome this shortcoming,a weighted cosine similarity algorithm was proposed.The experiments demonstrate that the proposed algorithm can effectively solve the terminal difference and improve the accuracy and universality of the indoor positioning system.

indoor positioning; terminal difference; weighted cosine similarity; WiFi

10.3969/J.ISSN.1000-5137.2017.01.021

2016-11-16

國家自然科學(xué)基金項目(61571135)

吳 赟(1976-),女,博士,副教授,主要從事無線通信中的信號處理技術(shù)研究、視頻跟蹤及圖像處理方面的研究.E-mail:wuyun_hit@dhu.edu.cn

TN 925.93

A

1000-5137(2017)01-0124-05