基于余弦相似度的加權(quán)K近鄰室內(nèi)定位算法

黃運(yùn)穩(wěn) 陳 光 葉建芳

(東華大學(xué)信息科學(xué)與技術(shù)學(xué)院 上海 201600)

0 引 言

隨著社會(huì)的進(jìn)步與發(fā)展，人們對(duì)室內(nèi)位置服務(wù)LBS(Location Based Services)的需求日益強(qiáng)烈[1]。將全球定位系統(tǒng)GPS應(yīng)用于室內(nèi)定位時(shí)，由于衛(wèi)星信號(hào)受建筑物環(huán)境的影響很大，定位的效率較低，定位的精度也較差，因此不能達(dá)到實(shí)時(shí)和準(zhǔn)確的定位要求。

隨著無線通信技術(shù)的應(yīng)用發(fā)展，基于接收信號(hào)強(qiáng)度的Wi-Fi室內(nèi)定位成為目前研究的熱點(diǎn)[2-3]。Wi-Fi信號(hào)不受視距傳播的影響，信號(hào)的覆蓋范圍較大，而且不易受到噪聲的干擾，適合于復(fù)雜的室內(nèi)環(huán)境定位。尤其是，Wi-Fi指紋定位不用添加其他任何硬件，利用現(xiàn)有的WLAN，通過軟件編程就可以在移動(dòng)智能終端上實(shí)現(xiàn)定位[4-6]。

有鑒于此，國(guó)內(nèi)外學(xué)者近年來對(duì)Wi-Fi指紋定位的匹配算法做了大量深入的研究，其中KNN[7]、WKNN[8-10](K Weighted Nearest Neighbor)以及余弦相似度[11-12]算法由于計(jì)算簡(jiǎn)單、易于實(shí)現(xiàn)而得到廣泛應(yīng)用。以上算法的核心在于通過RSS進(jìn)行歐氏距離或相似度的匹配。然而一方面，由于接收信號(hào)強(qiáng)度自身的不穩(wěn)定性與環(huán)境的多變性，導(dǎo)致接收信號(hào)強(qiáng)度不能完全準(zhǔn)確反映客觀物理位置。另一方面，歐氏距離體現(xiàn)的是接收信號(hào)強(qiáng)度數(shù)值的絕對(duì)差異，而余弦相似度是從方向上區(qū)分接收信號(hào)強(qiáng)度的差異，以上因素導(dǎo)致各算法在定位過程中容易引入奇異點(diǎn)[14]。針對(duì)上述問題，本文對(duì)K最近鄰和余弦相似度的組合策略進(jìn)行了分析研究與實(shí)驗(yàn)比較，給出了定位精度更高的優(yōu)化組合算法。

1 Wi-Fi指紋定位匹配算法

1.1 KNN匹配算法

KNN算法通過測(cè)量?jī)蓚€(gè)向量之間歐式距離來度量它們之間的相似度。該算法將待定位點(diǎn)采集到的信號(hào)強(qiáng)度RSS向量[s1,s2,…,sn]與指紋數(shù)據(jù)庫(kù)中的信號(hào)強(qiáng)度RSS均值矩陣[Si1,Si2,…,Sin]相匹配。設(shè)定位區(qū)域有m個(gè)參考點(diǎn)，共有n個(gè)AP，sj為待測(cè)點(diǎn)收到第j個(gè)AP的信號(hào)強(qiáng)度，Sij為指紋庫(kù)中第i個(gè)參考點(diǎn)采集到第j個(gè)AP的RSS均值，i=1,2,…,m，j=1,2,3，…,n。距離的定義公式如下：

(1)

KNN算法在歐氏距離中從小到大依次選取K個(gè)參考點(diǎn)，然后以該K個(gè)參考點(diǎn)的質(zhì)心作為估計(jì)位置。

(2)

KNN定位算法原理相對(duì)簡(jiǎn)單，以信號(hào)強(qiáng)度來反映物理位置關(guān)系，有利于定位系統(tǒng)的實(shí)現(xiàn)。

1.2 余弦相似度匹配算法

余弦相似度通過測(cè)量?jī)蓚€(gè)向量?jī)?nèi)積空間夾角的余弦值來度量它們之間的相似性。余弦值越接近1，表示兩個(gè)向量的夾角越接近0度，向量的方向越相近，即表示兩個(gè)向量越相似。如A和B的余弦相似度的計(jì)算公式如下：

(3)

基于余弦相似度算法理論，定位點(diǎn)采集的RSS矩陣s=[s1,s2,…,sn]與指紋數(shù)據(jù)庫(kù)中第i個(gè)參考點(diǎn)的RSS均值矩陣Si=[Si1,Si2,…,Sin]相匹配，通過式(4)計(jì)算余弦值，以余弦值從大到小依次選取K個(gè)參考點(diǎn)，并以式(2)計(jì)算得出估計(jì)位置。

(4)

通過余弦相似度算法匹配，考慮了RSS向量的內(nèi)在聯(lián)系。余弦相似度使用兩個(gè)向量夾角的余弦值作為衡量?jī)蓚€(gè)向量間差異的大小。相比歐氏距離，余弦相似度更加注重兩個(gè)向量在方向上的差異。

2 基于余弦相似度的加權(quán)KNN算法

2.1 算法提出依據(jù)

針對(duì)以上對(duì)兩種定位算法的介紹，通過三維坐標(biāo)來進(jìn)一步分析歐式距離和余弦相似度的區(qū)別，如圖1所示。

圖1 KNN與余弦相似度區(qū)別

由圖1可以看出，歐氏距離衡量的是空間各點(diǎn)的絕對(duì)距離，即與RSS向量各分量的大小直接相關(guān)；而余弦相似度衡量的是空間向量的夾角，體現(xiàn)的是RSS向量在方向上的差異。KNN和余弦相似度算法各自有不同的計(jì)算方式和衡量特征，KNN算法能夠體現(xiàn)RSS向量的絕對(duì)差異，余弦相似度是從方向上區(qū)分差異，而對(duì)絕對(duì)的數(shù)值不敏感。

針對(duì)以上分析，本文提出了基于KNN和余弦相似度的組合算法，旨在彌補(bǔ)單一區(qū)分方式的不足，從而提高定位精度。

2.2 算法步驟

在KNN算法篩選出K個(gè)近鄰點(diǎn)的條件下，計(jì)算K個(gè)近鄰點(diǎn)的余弦值。由1.2節(jié)分析可知，余弦值越大，表示兩個(gè)向量越相似，在歐氏距離相近的前提下，余弦值大的近鄰點(diǎn)定位精度越高。本文采用線下加權(quán)的方式來確定權(quán)值，從而包含位置指紋全部數(shù)據(jù)信息，進(jìn)而提升定位精度。算法步驟如下：

1) 篩選近鄰點(diǎn)?；谑?1)計(jì)算出定位點(diǎn)RSS向量與指紋庫(kù)中各向量的歐氏距離Li，在Li中從小到大順次篩選出K個(gè)參考點(diǎn)，坐標(biāo)為(xi,yi)，i=1,2,…,K。

2) 計(jì)算余弦值?；谑?4)分別計(jì)算待定位點(diǎn)與K個(gè)參考點(diǎn)之間的余弦值，余弦值的大小分別為S1,S2,…,SK。

3) 確定權(quán)值。S1,S2,…,SK中，余弦值越大，在位置估算時(shí)所作的貢獻(xiàn)越大，那么第i個(gè)參考點(diǎn)的權(quán)重值ωi可表示為：

(5)

4) 位置估計(jì)。利用權(quán)重值對(duì)K個(gè)參考點(diǎn)估算定位點(diǎn)的位置坐標(biāo)，即：

(6)

3 實(shí)驗(yàn)分析

3.1 實(shí)驗(yàn)環(huán)境與系統(tǒng)

為了檢驗(yàn)組合算法的定位性能，進(jìn)行如下實(shí)驗(yàn)。實(shí)驗(yàn)環(huán)境為東華大學(xué)2號(hào)學(xué)院樓第六層，平面圖如圖2所示。

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

文獻(xiàn)[15]得出結(jié)論，當(dāng)K=5或K=6時(shí)，系統(tǒng)定位的效果最佳。因此本文K值選擇5對(duì)參考點(diǎn)坐標(biāo)進(jìn)行篩選。其中數(shù)據(jù)庫(kù)信號(hào)采集與定位軟件界面如圖3所示。

(a) 離線信號(hào)采集 (b) 在線定位圖3 軟件界面截圖

離線采集：選用魅族M578C建立離線指紋數(shù)據(jù)庫(kù)，并將數(shù)據(jù)庫(kù)信息存儲(chǔ)在服務(wù)器。離線采樣間隔為1 m，為了減少數(shù)據(jù)庫(kù)建立的誤差，每個(gè)離線采樣點(diǎn)采集20組數(shù)據(jù)，以20組信號(hào)強(qiáng)度均值作為采樣點(diǎn)的最終樣本值。其中，數(shù)據(jù)庫(kù)中的數(shù)據(jù)包括采樣點(diǎn)坐標(biāo)、掃描到每個(gè)AP的ID和接收到每個(gè)AP信號(hào)強(qiáng)度。

在線定位：選取30個(gè)定位點(diǎn)測(cè)試，分別包括每個(gè)實(shí)驗(yàn)室選取2個(gè)參考點(diǎn)，走廊選取10個(gè)參考點(diǎn)。移動(dòng)終端向服務(wù)器發(fā)送連接請(qǐng)求，并向服務(wù)器發(fā)送當(dāng)前RSS向量，服務(wù)器接受RSS向量后通過組合算法進(jìn)行匹配，估算定位點(diǎn)的坐標(biāo)，并將坐標(biāo)信息發(fā)送到移動(dòng)終端。

3.2 性能分析

圖4為走廊中間位置的定位點(diǎn)連續(xù)進(jìn)行30次RSS采集，參與定位AP數(shù)量為5個(gè)時(shí)RSS的變化。由圖可知，室內(nèi)環(huán)境復(fù)雜多變，引起AP信號(hào)強(qiáng)度起伏變化。因此單一的傳統(tǒng)算法極易造成匹配出現(xiàn)偏差，引入奇異點(diǎn)。

圖4 不同定位點(diǎn)信號(hào)強(qiáng)度變化曲線

首先在實(shí)驗(yàn)環(huán)境中選2個(gè)AP參與在線定位階段，分別是6F-03和6F-07中的AP，采集30個(gè)參考點(diǎn)接收到參與定位的2個(gè)AP的數(shù)據(jù)，與數(shù)據(jù)庫(kù)中的數(shù)據(jù)相匹配，不參與定位的AP不匹配，計(jì)算此條件下，組合算法及傳統(tǒng)算法定位的平均誤差。然后每次增加一個(gè)AP參與定位，以相同方式算出不同算法的定位平均誤差。實(shí)驗(yàn)中第六個(gè)AP是校園公共網(wǎng)絡(luò)。不同算法在AP個(gè)數(shù)不同情況下，定位平均誤差的結(jié)果如圖5所示。

圖5結(jié)果表明，當(dāng)不同個(gè)數(shù)的AP參與定位時(shí)，組合算法的平均誤差均低于傳統(tǒng)算法，由此排除了組合算法在特定AP數(shù)量下提升定位性能的可能性。

圖5 參與定位的AP個(gè)數(shù)對(duì)定位結(jié)果影響

根據(jù)性能分析中不同AP個(gè)數(shù)對(duì)定位精度影響，我們選用5個(gè)AP參與定位，進(jìn)一步比較不同算法的累加誤差概率，如圖6所示。

圖6 不同算法的CDF曲線

由圖6可知，本文提出的組合算法定位精度明顯優(yōu)于單一的傳統(tǒng)算法。組合算法定位精度優(yōu)于1 m的置信概率為42%，優(yōu)于2 m的置信概率為72%，最大誤差為4.3 m，相對(duì)傳統(tǒng)算法均有改善。實(shí)驗(yàn)結(jié)果表明，文中提出的基于余弦相似度的加權(quán)KNN算法能夠有效地提高室內(nèi)定位的精度。

4 結(jié) 語(yǔ)

為了提高室內(nèi)定位的精度，考慮到KNN和余弦相似度匹配算法在定位特點(diǎn)的互補(bǔ)性，提出了基于余弦相似度的加權(quán)KNN算法，從而彌補(bǔ)單一傳統(tǒng)算法的不足。實(shí)驗(yàn)結(jié)果表明，基于余弦相似度的加權(quán)KNN算法在5個(gè)AP參與定位時(shí)，平均誤差減少到1.67 m，定位精度明顯提高。

隨著室內(nèi)定位技術(shù)的發(fā)展，基于余弦相似度的加權(quán)KNN算法需要在更大面積的環(huán)境、更復(fù)雜的干擾因素、更大量的指紋樣本條件下進(jìn)一步測(cè)試和優(yōu)化，使得該算法更加完善。