一種改進型幾何聚類指紋室內(nèi)定位方法

李石榮， 符茂勝， 張峰輝， 何富貴

(皖西學院電子與信息工程學院， 安徽 六安 237012)

引 言

隨著物聯(lián)網(wǎng)技術(shù)的不斷應(yīng)用和發(fā)展，基于實時位置服務(wù)的需求越來越多[1]。由于GPS系統(tǒng)受到室內(nèi)障礙物的遮擋使得其不能較好地應(yīng)用于室內(nèi)環(huán)境，關(guān)于室內(nèi)定位技術(shù)的應(yīng)用和研究成為位置服務(wù)的一大熱點[2-3]。目前室內(nèi)定位技術(shù)較多，其中基于WLAN的指紋定位方法由于其較低的成本和較高定位精度而得到廣泛的研究和應(yīng)用?；谥讣y的定位方法主要分為兩個階段：離線階段和在線階段。離線階段主要通過定位設(shè)備采集指紋點的信號強度和位置信息構(gòu)建數(shù)據(jù)信息和位置信息之間的映射關(guān)系；在線階段利用映射關(guān)系對定位點信號強度信息處理獲取定位結(jié)果。文獻[4]提出一種“動態(tài)多雷達搜索策略”自適應(yīng)選取近鄰K值，解決K值選取局限性；文獻[5]提出了一種動態(tài)調(diào)整定位字典方法，使模型動態(tài)適應(yīng)環(huán)境和接收信號強度(Received Signal Strength， RSS)變化。文獻[4-5]解決了室內(nèi)定位過程中環(huán)境變化、位置變化、RSS變化和K值動態(tài)選取問題，然而并未考慮指紋分布中幾何位置關(guān)系。文獻[6-10]分別對信號特征性問題提出了相應(yīng)的解決方法。文獻[6]提出了一種利用核判別和混洗蛙跳方法解決信號時變性問題，減小信號冗余和噪聲；文獻[7]提出了一種利用過濾選取固定的AP點的RSS進行定位；文獻[8]提出了利用KPCA算法和APC算法進行特征提取和聚類減小冗余并解決非線性問題，進行分類并縮小定位范圍；文獻[9]提出了利用RSS統(tǒng)計特性克服信道干擾問題；文獻[10]提出了一種基于相關(guān)向量機的非線性偏最小二乘法來解決多徑效應(yīng)和陰影效益問題。文獻[6-10]充分考慮信號時變性對定位的影響，提出特征提取、統(tǒng)計分布和聚類等方法解決了信號時變性對定位的影響問題，然而并未考慮到信號時變性是信號傳播過程中的固有特性，無法消除由于AP設(shè)備和復雜的環(huán)境影響而產(chǎn)生的部分冗余性和噪聲。文獻[11-15]利用SVM(Support Vector Machine)在非線性問題和高維度問題的優(yōu)勢，使用分類或回歸算法獲取定位結(jié)果，然而由于信號時變性的影響可能會產(chǎn)生個別定位點位置誤差較大而無法及時發(fā)現(xiàn)產(chǎn)生定位誤差較大的問題。文獻[16-17]分別提出了一種基于幾何聚類和多邊形的室內(nèi)定位方法，解決傳統(tǒng)加權(quán)K最近鄰算法WKNN(Weighting K-Nearest Neighbor)存在誤差較大點的問題，然而其只考慮到規(guī)則的幾何聚類多邊形，并未考慮復雜條件下(如邊界位置附近)幾何聚類圖形，邊界位置附近的定位點誤差較大。

WKNN方法是指紋定位方法中算法較簡單、系統(tǒng)較易實現(xiàn)的一種室內(nèi)定位方法。文獻[16]通過在幾何網(wǎng)狀結(jié)構(gòu)內(nèi)自適應(yīng)選取近鄰指紋點，構(gòu)建最佳多邊形區(qū)域后縮小定位區(qū)域范圍來提高定位精度，但該模型只考慮了網(wǎng)狀幾何結(jié)構(gòu)中矩形或正方形定位結(jié)構(gòu)。文獻[17]提出一種對定位區(qū)域進行網(wǎng)格區(qū)域劃分后，利用SVM多分類將位置確定在投票數(shù)最多的四邊形區(qū)域內(nèi)并通過WKNN進行定位，該算法并未考慮可進一步優(yōu)化定位區(qū)域，且算法運算時間較長。文獻[18]通過判斷周圍信號強度的大小篩選信號較強的前M個定位AP參與定位并計算結(jié)果，該算法并未考慮WKNN算法中K的優(yōu)化，應(yīng)用上具有一定的局限性。文獻[4]考慮了在利用WKNN定位過程中固定K值可能存在的定位局限性，在確定沒有新的不確定參數(shù)下利用 “多雷達搜索策略”確定K值獲取定位結(jié)果，該算法并未考慮定位點在網(wǎng)格邊界線上的臨界情況；在實際定位過程中，由于定位點可能出現(xiàn)在網(wǎng)格區(qū)域邊界位置附近，固定多邊形形狀和K值會降低定位效果。

為解決以上問題，本文提出了一種改進型幾何聚類指紋室內(nèi)定位方法。首先，利用網(wǎng)格分布在定位區(qū)域內(nèi)確定定位指紋點幾何位置并采集指紋點RSS和位置信息，利用SVM算法建立指紋RSS數(shù)據(jù)和位置之間的映射關(guān)系，構(gòu)建指紋分類數(shù)據(jù)庫；然后，采集定位點RSS信息并利用映射關(guān)系分類獲取定位點多個近鄰指紋點，計算近鄰指紋點對定位點的貢獻度大小，對貢獻度大小進行排序，選取最佳幾何聚類多邊形定位區(qū)域；最后利用WKNN算法獲取定位結(jié)果。實驗結(jié)果表明，本文提出的方法可解決傳統(tǒng)WKNN定位算法固定K值和固定多邊形區(qū)域存在局限性以及選取近鄰指紋點存在誤差較大影響定位精度的問題，降低了定位誤差。

1 改進型WKNN定位方法

1.1 改進型WKNN定位方法

傳統(tǒng)指紋點分布大多數(shù)基于網(wǎng)格分布結(jié)構(gòu)，將定位區(qū)域劃分成矩形等規(guī)則的四邊形區(qū)域結(jié)構(gòu)中，利用算法將定位點確定在某個固定的區(qū)域中，通過WKNN算法對定位點進行定位。傳統(tǒng)方法忽略了定位點在臨界邊上的情況，影響了定位精度。同時，傳統(tǒng)WKNN算法中的K值的選取也存在較大的局限性。

為解決以上問題，提出了一種基于貢獻度的改進型幾何聚類定位結(jié)構(gòu)。如圖1所示，網(wǎng)格上分布圓圈為指紋點，五角星為某個定位測試點。傳統(tǒng)WKNN定位過程中通常選取指紋點1、2和7圍成的三角形區(qū)域或指紋1、2、6和7圍成的四邊形區(qū)域。當定位點位置靠近網(wǎng)格線邊界位置時，固定區(qū)域和K值會引起較大定位誤差。由于RSS的時變性，定位結(jié)構(gòu)可能存在如圖1所示幾種類型的結(jié)構(gòu)情況，通過計算指紋點貢獻度可動態(tài)選取定位點指紋定位區(qū)域。

圖1 指紋點位置與定位結(jié)構(gòu)圖

1.2 支持向量機

指紋點和定位點接受信號強度數(shù)據(jù)分別為D={RSS1,RSS2,…,RSSN}和RSS，位置信息L={L1,L2,…,LN}，類別yi∈{-1,1}； 構(gòu)造最優(yōu)線性判別函數(shù)：

g(RSS)=ωT·RSS+b

(1)

其中：ω為分類超平面垂直向量，b為構(gòu)造最優(yōu)分類平面常數(shù)。

為解決凸函數(shù)和非線性問題，引入拉格朗日乘子α={α1,α2,…,αN}和高斯核函數(shù)K(·)。構(gòu)造拉格朗日函數(shù)：

(2)

將對偶問題轉(zhuǎn)化為求極值問題：

(3)

對ω,b求偏導可得：

(4)

將對α的極大值問題轉(zhuǎn)換成對偶問題：

(5)

α*為對偶問題的解，根據(jù)KKT條件可以將分類超平面轉(zhuǎn)化為：

(6)

SVM可解決指紋點分類過程中高維度和非線性問題[19]。

1.3 定位貢獻度計算

根據(jù)SVM分類算法獲取定位點近鄰指紋點，利用歐氏距離計算定位區(qū)域上的近鄰指紋點對定位點的貢獻度，再通過改進WKNN算法重新構(gòu)建定位區(qū)域結(jié)構(gòu)，計算定位結(jié)果。具體定位貢獻度計算過程如下：

(1) 首先利用SVM多分類算法獲取定位點M(M>6)個近鄰指紋點，計算定位點RSS到所有近鄰指紋點的歐氏距離，記為d1,d2,…,dM，di=|RSS-RSSi|,i=0,1,…,M。

(3) 將近鄰指紋點貢獻度進行排序，判斷選取定位結(jié)構(gòu)。主要分為以下幾種情況：

(a) 當前4個近鄰指紋點位置結(jié)構(gòu)滿足結(jié)構(gòu)1～結(jié)構(gòu)3時，利用結(jié)構(gòu)1～結(jié)構(gòu)3對定位點進行定位。

(b) 當不滿足情況a時，增加近鄰指紋點的選取，當選取的近鄰指紋點中可組成結(jié)構(gòu)1～結(jié)構(gòu)3位置時，停止選取，構(gòu)造結(jié)構(gòu)1～結(jié)構(gòu)3進行定位。

(c) 當近鄰指紋點不低于6個且可構(gòu)造結(jié)構(gòu)4時，選取結(jié)構(gòu)4定位。

(d) 對選取指紋點貢獻度進行二次貢獻度分配，重現(xiàn)獲取對定位的權(quán)值。

(f) 當選取的近鄰指紋點不能滿足結(jié)構(gòu)1～結(jié)構(gòu)4幾何圖形時，說明定位點數(shù)據(jù)誤差較大，重新采集定位點數(shù)據(jù)。

(4) 利用WKNN算法對定位點進行定位。

2 定位流程

定位流程圖如圖2所示：

圖2 定位流程圖

具體定位計算過程如下：

(1) 利用SVM獲取定位點前M(M>6)個近鄰指紋點，計算定位點RSS到近鄰指紋點歐氏距離分別為D1,D2,…,DM。

(7)

(2) 根據(jù)指紋點歐氏距離計算對定位點的貢獻度從大到小依次為W1,W2,…,WM，選取前K(3≤K≤6)個貢獻度較大的指紋點并根據(jù)改進WKNN方法構(gòu)建定位結(jié)構(gòu)區(qū)域；

(8)

(3) 利用前K個指紋點的貢獻度和位置信息，計算定位結(jié)果P。

(9)

3 實驗結(jié)果分析

3.1 實驗環(huán)境

為驗證本文提出的改進WKNN室內(nèi)定位方法的效果，在皖西學院實驗實訓部一樓實驗室進行了實驗，實驗環(huán)境如圖3所示。實驗區(qū)域長36 m、寬18 m，指紋點之間間隔距離選取為2 m，測試點位置選取定位區(qū)域內(nèi)，每次數(shù)據(jù)采集次數(shù)為30次，取平均值作為RSS指紋數(shù)據(jù)和定位數(shù)據(jù)。

圖3 實驗環(huán)境

3.2 實驗結(jié)果分析

3.2.1 實驗數(shù)據(jù)

表1和表2分別給出的一組指紋點和定位實驗數(shù)據(jù)，分別有4個AP上的特征信號數(shù)據(jù)。

表1 指紋點信號強度數(shù)據(jù)(單位：dBm)

表2 定位點信號強度數(shù)據(jù)(單位：dBm)

3.2.2 不同定位方法結(jié)果對比

本文對四種基于WKNN算法的不同定位方法的結(jié)果進行了對比。定位方法分別為：

(1) 傳統(tǒng)WKNN算法：固定K值獲取定位結(jié)果。

(2) WKNN+四邊形：將定位點固定在某個四邊形區(qū)域中進行定位。

(3) WKNN+幾何聚類：利用最佳多邊形幾何聚類原理動態(tài)選取多邊形區(qū)域和K值。

(4) 改進WKNN算法：本文提出的利用近鄰指紋點對定位的貢獻度重構(gòu)定位區(qū)域獲取定位結(jié)果。

定位結(jié)果統(tǒng)計見表3，對比如圖4所示。表3為一組7個定位點數(shù)據(jù)的多次數(shù)據(jù)處理定位誤差統(tǒng)計結(jié)果。圖4是利用傳統(tǒng)WKNN算法(固定K值為4)、WKNN+四邊形、WKNN+幾何聚類和改進WKNN算法對定位點多次數(shù)據(jù)處理獲取的平均定位誤差分別為1.81 m、1.55 m、1.53 m和1.38 m左右[16-17]。

表3 定位誤差累計概率統(tǒng)計結(jié)果

圖4 定位結(jié)果對比

3.2.3 K值對定位結(jié)果的影響

本文從不同K值對傳統(tǒng)WKNN算法和改進WKNN算法下的定位精度進行了對比。不同的K值影響的定位精度的變化如圖5所示。從圖5可以看到，當K值在3～6之間時，改進WKNN方法可構(gòu)建最佳多邊形結(jié)構(gòu)定位區(qū)域，當K值超過這個范圍時，定位誤差較大。傳統(tǒng)WKNN算法由于在選擇K值過程中未對定位結(jié)構(gòu)區(qū)域作優(yōu)化處理，存在誤差較大的近鄰指紋點使得定位誤差較大。當K值取3、4、5和6時，與傳統(tǒng)WKNN方法相比下平均定位誤差分別減小了0.57 m、0.45 m、0.56 m和0.17 m。

圖5 不同K值對定位誤差影響

3.2.4 邊界近鄰定位點測試

在網(wǎng)格分布臨界邊上選取7個定位點進行測試，經(jīng)過多次反復的采集數(shù)據(jù)、處理數(shù)據(jù)和計算并獲取定位結(jié)果。7個不同位置的定位點在傳統(tǒng)WKNN算法和改進WKNN算法下定位誤差的對比如圖6所示。從圖6可以出，當定位點在臨界邊附近時，傳統(tǒng)WKNN算法定位誤差較大，而本文提出的改進WKNN方法可較好地適應(yīng)邊界附近定位點。

圖6 臨界定位點定位結(jié)果對比

4 結(jié)束語

本文針對傳統(tǒng)WKNN算法在定位過程中由于K值和定位結(jié)構(gòu)區(qū)域選取過程中存在誤差的問題，提出了一種改進型WKNN室內(nèi)定位方法。該方法首先構(gòu)建最佳多邊形定位結(jié)構(gòu)區(qū)域，接著利用SVM分類獲取近鄰指紋點并根據(jù)指紋點的貢獻度大小構(gòu)建最佳定位區(qū)域，最后利用WKNN算法獲取定位結(jié)果。實驗結(jié)果表明，本文提出的方法優(yōu)于傳統(tǒng)基于WKNN的定位方法。本文在研究過程中并未考慮定位點移動的情況，關(guān)于定位點移動條件下如何解決信號時變性的問題有待下一步研究。