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

吳 赟, 蔣新華, 齊雁飛, 蔣學(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)點(diǎn),成為室內(nèi)定位技術(shù)研究的熱點(diǎn).WiFi指紋定位法可以對(duì)抗多徑的影響,具有較高的定位精度.但是由于智能移動(dòng)終端的種類(lèi)繁多,使得室內(nèi)定位系統(tǒng)離線(xiàn)建立的指紋數(shù)據(jù)庫(kù)難以兼容不同的智能移動(dòng)設(shè)備,降低了定位系統(tǒng)的適用性.為解決此問(wèn)題,提出了加權(quán)余弦相似度算法,使用信號(hào)強(qiáng)度的加權(quán)余弦相似度作為匹配特征.實(shí)測(cè)表明,采用加權(quán)余弦相似度算法可有效解決終端差異性,提高了室內(nèi)定位系統(tǒng)的精度和普適性.

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

0 引 言

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

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

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

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

假設(shè)在室內(nèi)區(qū)域有L個(gè)參考點(diǎn),并且每個(gè)參考點(diǎn)處可以探測(cè)N個(gè)AP的RSS,則第i個(gè)參考點(diǎn)處指紋信息向量為Ri={xi,yi,bi1,bi2,…,biN},其中i∈(1,2,…,L),(xi,yi)為第i 個(gè)參考點(diǎn)處的位置坐標(biāo).參考點(diǎn)的數(shù)量和有效性直接影響著定位系統(tǒng)在線(xiàn)階段的定位精度,定位精度隨著參考點(diǎn)的增加有所提高,但是,參考點(diǎn)增多使離線(xiàn)階段搜集指紋信息的工作量增大,因此,離線(xiàn)階段應(yīng)該根據(jù)室內(nèi)環(huán)境合理地選擇參考點(diǎn)的數(shù)量.在線(xiàn)定位階段,首先通過(guò)移動(dòng)設(shè)備在待測(cè)區(qū)域?qū)崟r(shí)采集AP的RSS向量,然后,將采集的RSS向量與離線(xiàn)指紋庫(kù)中的數(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向量的趨勢(shì)相同,RSS向量間歐式距離的劇烈變化并沒(méi)有引起向量間夾角發(fā)生劇烈變化,可以引入余弦相似度來(lái)衡量向量的相似性,余弦相似度算法公式如下:

(1)

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

(2)

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

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

(3)

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

(4)

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

(5)

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

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

離線(xiàn)階段:

1) 布置實(shí)驗(yàn)場(chǎng)景,在定位區(qū)域布置好AP.

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

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

在線(xiàn)階段:

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

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

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

3 結(jié)果分析

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

圖2 實(shí)驗(yàn)環(huán)境

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

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

圖3 無(wú)終端差異時(shí)不同算法定位精度

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

4 結(jié) 論

為了解決室內(nèi)定位的終端差異性問(wèn)題,提出了使用加權(quán)余弦相似度算法進(jìn)行指紋點(diǎn)匹配,從而消除了由于不同終端接收信號(hào)強(qiáng)度不同造成的定位誤差.實(shí)驗(yàn)結(jié)果顯示,加權(quán)余弦相似度算法的使用不僅可以解決終端差異度對(duì)定位精度的影響,同時(shí)相比現(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ù)的特征級(jí)融合及在手部特征識(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

國(guó)家自然科學(xué)基金項(xiàng)目(61571135)

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

TN 925.93

A

1000-5137(2017)01-0124-05