基于WiFi的室內定位準確率改進算法

潘維蔚,康 凱,張武雄,王海峰

(1.中國科學院上海高等研究院,上海 201210; 2.中國科學院大學 電子電氣與通信工程學院,北京 100049;3.上海科技大學 信息科學與技術學院,上海 201210; 4.中國科學院上海微系統與信息技術研究所,上海 200050)

0 概述

隨著信息社會的不斷發展,人們對定位服務的需求日益增多,對室內環境而言,由于信號的嚴重衰減和多徑效應[1-2],通用的室外定位設施并不能在建筑物內有效地進行工作,因此人們需要更精密準確的定位方法。無線保真(Wireless Fidelity,WiFi)[3]作為基礎定位設施成為研究人員首先考慮的方法。另外的一些技術,如無線射頻識別(Radio Frequency Identification,RFID)[4]、超聲波、激光等,也可以實現室內定位,但是這些技術在真實環境中的實用性較低,同時存在額外搭建網絡設施導致的安裝和工作成本增加的問題。

對WiFi定位算法而言[5],由于WiFi的接收信號強度(Received Signal Strength,RSS)獲取比較簡單,不受信號帶寬的影響,因此RSS是廣泛應用于WiFi定位中的信號特征。WiFi定位最普遍應用的算法是指紋定位算法[6],目前已有大量高準確率的改進算法被提出,經典算法有貝葉斯算法[7-9]、EZ算法[10]等,文獻[11]提出一種新的高斯過程回歸模型,以估計室內環境的非均勻RSS分布,但是誤差在2 m以內占比僅60%,1 m以內占比僅20%。

除經典算法外,運用機器學習進行匹配的算法也被大量運用在WiFi室內定位領域。文獻[12]引入一種相似度度量信號趨勢指數,使得定位精度平均達到2 m～3.5 m,但是誤差在2 m以內的占比仍不超過60%。文獻[13]對離線指紋進行稀疏表示,但是結果與采樣點自身RSS變動規律嚴重沖突,同時波動性太大,標準差達到1.91 m。一般而言,定位算法的采樣點間距(網格)僅為1 m～2 m,因此上述算法50%以上數據將被誤定位成相鄰網格,嚴重影響定位精度。實際上,無論是傳統算法還是運用機器學習的算法都存在在低于2 m的誤差范圍內定位累計準確率過低的問題。特別是當相鄰網格指代完全不同的信息時,如在室內環境中智能手機使用者是生活區的某家餐廳內還是門外的走廊,此時定位問題轉化為了二分類問題,在低于2 m的誤差范圍內過低的準確率會造成客觀事實的嚴重錯誤。目前相鄰網格問題的研究較少,文獻[14]利用Adaboost算法反復迭代和合并弱學習者的結果最終將定位數據分為室內和室外,屬于二分類問題,并且沒有研究相鄰網格。

本文將室內場景下的相鄰網格定位問題,轉化為對無線訪問接入點(Access Point,AP)收集到的高維RSS數據進行0、1判決的問題,為使判決具有有效性和穩定性,提出一種去異常值的線性判別低維組合算法,根據信號強度數據的自身特征對數據進行處理,并運用線性判別低維組合算法對數據進行約束,以滿足WiFi室內定位的高精度要求。

1 系統模型和問題描述

WiFi室內定位算法通常采用基于RSS的指紋定位算法,指紋定位算法在離線訓練階段將室內區域劃分為網格(間距1 m～2 m),使用接收設備對網格采樣點逐個進行采樣,每個網格對應一個獨特的指紋,這個指紋可以是單維或多維的,是接收信息或信號的一個特征或多個特征,通常可記錄該點位置、所獲取的RSS及AP地址等,對指紋數據進行處理(濾波、均值等),在大量的已知位置上建立一個細粒度的指紋數據庫。在線定位階段用戶持移動設備在定位區域移動,實時獲取當前RSS及AP地址,將該信息上傳到服務器進行匹配。其中,待定位設備的信號強度d與固定信號發射源的距離q符合如下傳播模型:

(1)

其中,E為發射端和接收端相隔1 m時的信號強度,q為環境衰減因子。本文選取的室內場景如圖1所示,圖1中環境區域被劃為不同網格(am×bm),虛線為網格邊界,總共有k個AP(k≥4),其中AP用圓形表示,特別地,有4個AP分別為AP1、AP2、AP3、AP4,用 1、2、3、4標注。同一時刻k個AP對應收集的k維RSS數據為m=[RSS1,RSS2,…,RSSk]=M,這里M為m組成的數據集合,M分為由離線階段收集的數據m1組成的集合M1(訓練集和驗證集集合)和在線訓練階段收集的數據m2組成的集合M2(測試集)。

圖1 室內場景

本文的目的是通過對離線階段收集的數據m1和對應的標簽進行學習得到映射f,從而判斷在線訓練階段收集的數據m2輸出的標簽所對應的網格,假設輸出的標簽為集合L={0,1,…,T},分別對應T個網格,室內定位問題即變成多分類問題,數學形式如下:

f:M2→L

(2)

由于目前存在在低于2 m的誤差范圍內定位累計準確率過低導致誤判為相鄰網格的問題,因此選擇一對相鄰網格作為研究對象,特別地,圖1中A和B兩點分別代表門內網格和門外網格,對應的標簽為0或1這2個值,集合為G={0,1},離線學習得到模型g,多分類問題轉變為二分類問題,如現實場景中具有較高實際價值的門內門外狀態,數學形式轉變為:

g:M2→G

(3)

2 線性判別分析算法

對于WiFi室內定位算法,人們采用度量遷移學習(Metric Transfer Learning,MTL)、主成分分析(Principal Component Analysis,PCA)、隨機森林(Random Forest,RF)算法、稀疏表達(Sparse Presentation,SP)等算法得到估算位置[15-17],然而這些算法都是從整體區域的大尺度分類角度進行匹配,最終的分類結果為適用于誤差可允許范圍在2 m以上的場景,并不適合處理相鄰網格的數據。因此,本文引入線性判別分析(Linear Discriminant Analysis,LDA)算法[18],首先處理異常值,并且對LDA算法在低維情況下進行排列組合,通過概率求和對在線訓練數據進行新的約束,最終確定智能手機使用者具體的二分類狀態(如門內或門外)。

LDA算法是將高維的模式(多個AP樣本,不同AP對應不同維度)投影到最佳鑒別矢量空間,以達到抽取分類信息和壓縮特征空間維數的效果,使投影后模式樣本的類間散布矩陣最大,同時類內散布矩陣最小,保證投影后在新的空間中有最小的類內距離和最大的類間距離,即相鄰網格的高維數據在該空間中有最佳的可分離性。區分方法為:首先獲取每類高維數據的均值(中心點)ui,其中,w是投影方向,n為投影值,n=wTm,投影值n被劃分為2個集合。ti是所有被判定為i(i為0或1)的n的集合,對應地,集合si是判定為i的所有m的集合,Ni是所有被判定為i且屬于集合M1點的個數。可以求得高維數據中心點ui為:

(4)

由m通過投影w后的樣本點均值為vi:

(5)

投影后的均值即為樣本中心點的投影,則類間距離為J(w),可表示為:

J(w)=|v1-v2|=|wT(u1-u2)|

(6)

(7)

則最大化目標函數為:

(8)

最終得到映射關系,并根據映射關系w得到預測值:

(9)

3 LDA算法在室內場景的適用性證明

在WiFi室內定位場景中,本文選擇LDA算法的原因是只要AP不是緊鄰被測相鄰網格,就可以得到室內相鄰網格(如門內門外)數據在各自網格內近似方差相等,區分相鄰網格主要與均值有關,以證明以門內門外網格為例,如果AP緊鄰被測相鄰網格,根據式(1),相鄰網格信號強度差異巨大,此時定位準確率本身就很高,不是本文以及所有WiFi室內定位相關論文的討論范圍,本文討論的是普遍存在的一般定位研究中出現的在低于2 m的誤差范圍內定位累計準確率過低的問題。因此,從理論上確立一個邊界,此邊界可廣泛適用于室內WiFi定位場景。WiFi信號傳播示意圖如圖2所示。

圖2 WiFi信號傳播示意圖

在圖2中任意選擇一個AP,AP用圓形表示,門內門外的相鄰網格分別用2個網格表示,2條實線分別代表WiFi信號傳播到門內的中心點和邊緣點的2條視線傳輸的路徑,路徑的距離分別用d1、c1表示,2條虛線分別代表傳播到門外的中心點和邊緣點的2條視線傳輸的路徑,路徑的距離分別用d2、c2,橫向雙箭頭所示距離為x,縱向雙箭頭所示距離為y,門內的中心點和邊緣點的信號強度值為rrss1、rrss2,則根據信號強度與距離式(1),有:

(10)

(11)

從而可以得到:

(12)

其中,Δrss1、Δrrss2分別是圖2所示門內、門外點在各自網格的角與中心的信號強度差值,根據大小關系可知RSS同號。網格為a、b的格子形,通過對下面等式做變換:

(13)

(14)

由于網格的邊長a、b一般都在1 m到2 m之間(網格邊長等于相鄰網格的中心距離,而低于2 m的誤差范圍內是相鄰網格的中心距離,即本文所研究的距離區分度),距離比較小,記:a2(y2-ax-by)+ax(-ax-by)為R,式(14)可近似為:

(15)

任意AP需滿足如下條件:

x2+y2∈(4amax(a,b),∞)

(16)

對式(15)中的R進行縮放,可以得到:

-2amax(a,b)(x2+y2)≤

-amax(a,b)(x+y)2≤-(a2+ax)(ax+by)≤R

R≤a2(y2-x2)≤a2(x2+y2)

(17)

從而比較式(15)分子分母,近似可得:

(18)

不等式(18)兩端邊界均在式(16)的下確界取得,因而對式(18)進行邊界處理,由式(12)得:

(19)

上述推導過程證明了網格的角符合信號強度差值幾乎相等的結論,網格其他邊界的點與上述推導過程類似,網格內部的點到AP距離差值較小,而信號強度值差值則更小,由于任何在內網格的兩點位置相對空間關系,都可以找到對應向右(或者相鄰方向)平移a的外網格的相對空間關系,因此因空間位置改變的信號強度值在各自網格內方差幾乎相同。相鄰網格數據的方差主要分為空間位置σ1和自身能量波動σ2兩部分,而自身能量波動主要受發射點能量變化和到達時間變化決定,因而對同一個AP發射點可認為在相鄰網格自身能量波動σ2近似,從而一維數據方差近似,k維數據方差由于獨立性是一維數據方差的簡單代數相加,因此k維數據在各自網格內方差近似,所以LDA算法用以突出類間距離對于處理中心距離低于2 m以內的相鄰網格是合理的。

4 異常值處理方法

圖3 異常值對結果影響的示意圖

如果運用Ransac算法,則無法設定閾值。本文的處理方法是將離線訓練的k維數據代入離線訓練集自身,尋找歐幾里得距離最近的N0個點,用歐幾里得距離直接判斷,當檢測任意的m0為k維數據異常點時,m′是異于m0的其他點,歐幾里得距離表達公式如下:

(20)

如果最近的N0個點中至少有一半以上的點與對應的網格一致,則認為不是異常點;否則視為異常點。

5 LDA低維組合算法

采用LDA算法對k維數據進行0、1判決,等價于0概率是否為0.5的判斷,實際上可以在數據的判斷方面進行更嚴格的約束,以提升判決準確率,因而本文提出一種可以嚴約束的低維組合算法進行低維排列組合,對所得的若干個概率值求和,并設置門限。

算法描述分為訓練驗證和測試,本文已經證明滿足給定條件的任意AP均完全適用LDA算法。

訓練驗證階段步驟如下:

1)對k個AP產生的時序校準過的一維訓練數據集分別進行歸一化。

2)對歸一化后的數據進行異常值處理。

3)對進行異常值處理后的數據運用LDA算法構建模型h。

4)排列組合k個AP,并分為k組,每組依次去除一個AP(一維),得到k-1維數據,對k組k-1維數據運用LDA算法,分別得到輸出的預測值為0的概率P1,P2,…,Pk,則對應預測值為1的概率分別為(1-P1),(1-P2),…,(1-Pk)。

5)設置約束門限,點m如果滿足下式,則m判決值取0:

P1+P2+…+Pk≥kλ

(21)

6)對應地,如果滿足下式,則m判決值取1:

P1+P2+…+Pk≤k(1-λ)

(22)

7)如果概率和不在步驟4)和步驟5)范圍,則認為步驟2)的預測值是對的,其中,λ∈(0.5,1)。

測試階段步驟如下:

1)對k個AP產生的時序校準過的每一維在線訓練數據分別進行歸一化。

2)用模型h預測k維歸一化后的在線訓練數據,得到預測值(0或1)。

3)重復訓練驗證階段的步驟4)～步驟7)。

6 實驗結果與分析

6.1 真實數據實驗

實驗選用華為手機NEM-10作為接收設備,其中手機內置有WiFi模塊,辦公室內放置有4個AP,通過HL-340 USB串行口分別與4臺個人計算機相連。在測試前對AP內核寫入程序并充分調試,使AP在接收到手機反向的應答信號時,將RSS信息、手機的MAC地址、收到應答信號的時刻通過串行口輸出到個人計算機上,并進行同時性校準。測試時個人計算機保存記錄并整合4臺個人計算機的信息。

實驗所用的真實環境為辦公室環境(見圖1),其中辦公室所在的門內網格和走廊所在的門外格點用A、B標注,4個AP位置分別是AP1、AP2、AP3、AP4所在的位置,選取的相鄰格點是門內以門為邊界線的內網格和門外對應的外網格(本文網格為1 m×1 m的正方形,即相鄰網格中心距離可以充分保證算法處理的數據低于2 m誤差范圍,實現網格區分度最小時的準確率提升,同時為使準確率提升更具有一般性,門內門外沒有門的阻隔,這樣相鄰網格信號強度差異本身更小,網格之間區分難度更大),實驗時實驗人員攜帶手機在室內室外網格的時間相等,實驗人員每6 min輪換網格(這樣可以保證訓練數據的均衡性),共分3個時間段進行3次不同真實辦公室環境(如辦公室內物體的擺放以及人員的變化)的實驗。具體而言,該辦公室環境內外人員和物體(如人員的背包、筆記本等放置的位置)具有一定的流動性和進行社會活動的特征,3次實驗環境的人數在8人到13人之間波動,同時辦公室外的走廊上也會有行人經過。對辦公室內部署的4個AP而言,有2個AP部署在附近(約一個小網格尺度)較為空曠的地方,其信號會被流動人員的活動(比如行走聚集等)隨機干擾;另有2個AP部署在兩張有人持續使用的的辦公桌上,其信號不僅被隨機干擾,還會被辦公設施具體使用者頻繁干擾(如翻閱文件、變換坐姿等)。這樣可以保證3次實驗環境的不同,對應地可以分別獲取3種在真實變動環境(實際環境中存在人員和物體相對無變化的環境,真實變動環境要求算法泛化能力更強)的不同數據集。第1種環境共收集2 383組的4維數據,第2種環境總共收集535組的4維數據,第3種環境總共收集957組的4維數據,計算機總計收集到3 875組的4維數據。

6.2 結果分析

根據實驗設備得到的數據,對數據處理后的去異常值的LDA低維組合算法與LDA算法、支持向量機(Support Vector Machine,SVM)算法進行比較研究[20],其中文獻[21]運用SVM算法通過基站確定全球移動通信系統(GSM)制式手機位置,具有較好的魯棒性,并具備泛化能力強的特征。

對去異常值的LDA低維組合算法的λ分別取0.7、0.8、0.9,N0分別取50、75、100,結果表明,去異常值的LDA低維組合算法本身對于λ和N0這2個參數不敏感,當λ比較大而N0不是太小時,去異常值的LDA低維組合算法在各種環境下總的判斷準確的數據個數波動始終在2個以內,對測試集準確率影響忽略不計,原因在于算法準確率提高,對參數依賴性比較低。

本文首先對每種相同環境劃分為訓練集、驗證集和測試集3個部分。如環境1自身被隨機分為3個部分,即測試集也來自于環境1,同理環境2、環境3自身內部也被隨機地劃分為3個部分,分別得到各自在3種算法下的測試集準確率,如表1所示。

表1 不同環境下3種算法測試集準確率比較

從表1可以看出,去異常值的LDA低維組合算法在同一種環境下,能準確地區分出多維數據位于相鄰網格的哪一側,相對于LDA算法、SVM算法有比較明顯的提升。

利用任一環境下的數據集作為訓練集進行3種算法的訓練和驗證,在實驗中表示一次離線數據收集過程,用其他環境下的實測數據集的任一實測數據作為測試集進行測試,獲得測試集的準確率,如環境1作為訓練驗證集,其他環境作為測試集,用來驗證算法的泛化能力,以檢驗算法在一次離線采集基礎上對不同環境下相鄰網格的分辨能力。

表2為去異常值的LDA低維組合算法、LDA算法、SVM算法在辦公室不同環境下對完整的訓練集進行學習的準確率,可以看出去異常值的LDA低維組合算法對比另外2種算法,在每一種狀態下準確率都有提高。這是由于去異常值的LDA低維組合算法根據相鄰網格點RSS數據特征進行了合理的處理,并且低維組合的思想通過概率和和門限的設置,進行了對數據的約束。在上述方法的應用下,在環境1中,LDA的準確率為65%,SVM的準確率為72%,去異常值的LDA低維組合有至少4%的提升;在環境2中,LDA的準確率為74%,SVM的準確率為77%,去異常值的LDA低維組合為79%;在環境3中,LDA的準確率為63%,SVM的準確率為77%,去異常值的LDA低維組合為83%,具有顯著提升。3種環境下的實驗結果表明了本文算法的正確性和有效性。

表2 不同環境下3種算法訓練集準確率比較

對于不同的環境,3種算法的準確率具有比在相同環境下區分相鄰網格有顯著下降,這符合信號強度受外界因素變化較大的現實情況,表明室內Wifi定位的準確率在低于2 m的誤差范圍內過低的問題確實存在,文獻[6-8]的準確率與本文實際測試的LDA算法、SVM算法準確率結果是一致的,這也表明本文算法是有效的。

圖4是在不同辦公室環境下,訓練集抽取不同數量的數據對去異常值的LDA降維組合算法的準確率,從圖中可以看出,在相同的辦公室狀態下,環境1要隨機抽取250個數據,訓練達到測試集準確率的上限0.93,在實際訓練過程中抽取200個點時,準確率雖然平均達到0.92,但是隨著抽取的隨機狀態不同而波動,表明隨機抽取200個點數據具有局限性而容易過擬合,訓練集至少需要250個點;環境2要隨機抽取300個數據,訓練達到準確率的上限0.90,環境3要隨機抽取300個數據,訓練達到準確率的上限0.89,在實際訓練過程中抽取250個點時,環境2、環境3準確率雖然平均達到0.89、0.88,但也會隨著抽取的隨機狀態不同而波動,表明隨機抽取250個點數據具有局限性而容易過擬合,至少需要300個點,因而實施算法所需的訓練集至少要有300個點。同時,在實際訓練過程中,只要訓練集抽取超過300個點,無論選擇何種環境,去異常值的LDA低維組合算法的準確率不隨抽取的隨機狀態而改變,這表明該算法具有魯棒性。

圖4 不同辦公室環境下LDA降維組合算法的準確率

從表1、表2、圖4的結果可以看出,去異常值的LDA低維組合算法可以有效提高本文所述二分類(如門內門外狀態)的判決準確率,具有正確性和魯棒性。

7 結束語

本文提出一種去異常值的線性判別低維組合算法。通過對室內WiFi定位的信號強度數據自身特征的研究,完成LDA適用性和去異常值的理論分析,并利用線性判別算法在低維情況下進行排列組合,對所得的若干個概率值求和,通過門限的設置對數據進行額外的約束。實驗結果表明,該算法能滿足企業和用戶對基于位置的定位服務的需求。本文方法主要用于小網格,下一步將研究傳統大尺度粗略分類與小尺度精確定位的聯合算法,以及WiFi定位與其他定位方法的聯合判決來提高定位準確率。