一種改進型幾何聚類指紋室內定位方法

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

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

引 言

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

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

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

1 改進型WKNN定位方法

1.1 改進型WKNN定位方法

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

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

圖1 指紋點位置與定位結構圖

1.2 支持向量機

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

g(RSS)=ωT·RSS+b

(1)

其中：ω為分類超平面垂直向量，b為構造最優分類平面常數。

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

(2)

將對偶問題轉化為求極值問題：

(3)

對ω,b求偏導可得：

(4)

將對α的極大值問題轉換成對偶問題：

(5)

α*為對偶問題的解，根據KKT條件可以將分類超平面轉化為：

(6)

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

1.3 定位貢獻度計算

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

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

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

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

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

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

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

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

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

2 定位流程

定位流程圖如圖2所示：

圖2 定位流程圖

具體定位計算過程如下：

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

(7)

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

(8)

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

(9)

3 實驗結果分析

3.1 實驗環境

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

圖3 實驗環境

3.2 實驗結果分析

3.2.1 實驗數據

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

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

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

3.2.2 不同定位方法結果對比

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

(1) 傳統WKNN算法：固定K值獲取定位結果。

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

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

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

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

表3 定位誤差累計概率統計結果

圖4 定位結果對比

3.2.3 K值對定位結果的影響

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

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

3.2.4 邊界近鄰定位點測試

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

圖6 臨界定位點定位結果對比

4 結束語

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