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

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

0 引 言

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

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

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

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

1.1 KNN匹配算法

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

(1)

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

(2)

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

1.2 余弦相似度匹配算法

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

(3)

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

(4)

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

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

2.1 算法提出依據(jù)

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

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

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

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

2.2 算法步驟

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

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

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

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

(5)

4) 位置估計。利用權(quán)重值對K個參考點(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號學(xué)院樓第六層，平面圖如圖2所示。

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

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

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

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

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

3.2 性能分析

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

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

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

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

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

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

圖6 不同算法的CDF曲線

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

4 結(jié) 語

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

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