基于稀疏指紋采集和改進WKNN的定位算法

李新春，王 歡

(1.遼寧工程技術(shù)大學 電子與信息工程學院，遼寧 葫蘆島 125105；2.遼寧工程技術(shù)大學 研究生院，遼寧 葫蘆島 125105)

0 引 言

隨著物聯(lián)網(wǎng)的發(fā)展和日益普及，基于位置服務(wù)的相關(guān)技術(shù)成為人們?nèi)粘９ぷ?、生活的基本需求。在室外環(huán)境中，GPS可實施高精度定位，但在室內(nèi)環(huán)境中，基于Wi-Fi位置指紋定位算法更具優(yōu)勢[1]。這種定位算法無需添加硬件、成本低、應(yīng)用廣泛，但仍面臨著指紋采集工作量大、定位精度低的問題[2]。

位置指紋定位算法包括2個階段：離線階段和在線階段。離線階段，在參考點上逐一采集來自各接入點(access point，AP)的接收信號強度(received signal strength，RSS)，組成有序RSS向量，同其位置坐標構(gòu)成位置指紋，存入指紋庫中；在線階段，定位目標實時采集RSS向量，并由匹配算法與指紋庫中的指紋進行相似度匹配，最后計算定位位置。

在現(xiàn)有的研究中，對位置指紋定位算法的改進主要集中在基于空間和時間的信號模式、協(xié)作定位和運動輔助定位，但構(gòu)建位置指紋庫是不可避免的過程，那么降低現(xiàn)場指紋勘測開銷成為亟待解決的問題[3]。文獻[4-6]無需指紋現(xiàn)場勘測，利用眾包方法將位置指紋與用戶移動蹤跡相結(jié)合構(gòu)建邏輯平面圖，通過匹配邏輯平面圖和實際平面圖來實現(xiàn)定位，該方法需要志愿者用戶報告他們的數(shù)據(jù)，但非專業(yè)的勘測數(shù)據(jù)通常受到質(zhì)疑，且會產(chǎn)生大量的冗余數(shù)據(jù)；文獻[7-8]通過現(xiàn)場勘測獲得部分指紋信息，利用地質(zhì)學插值算法對其他指紋進行預(yù)測，由稀疏采集的指紋數(shù)據(jù)構(gòu)建密集的指紋庫，但插值算法要求區(qū)域化變量(RSS變量)滿足二階平穩(wěn)，要求嚴格。

通過上述分析，本文考慮到現(xiàn)場勘測指紋數(shù)據(jù)的可靠性及RSS向量的非線性特征，以減少指紋采集工作量、提高定位精度為目標，利用機器學習的自主學習能力，提出基于稀疏指紋采集和改進WKNN的定位算法。離線階段，稀疏采集指紋數(shù)據(jù)，訓練優(yōu)化的高斯過程回歸模型，對未采集的指紋數(shù)據(jù)進行預(yù)測，構(gòu)建密集指紋庫；在線階段，改進WKNN算法，用卡方距離代替歐氏距離計算RSS相似度，并根據(jù)各AP穩(wěn)定性賦予不同的權(quán)值。實驗結(jié)果表明，與其他算法相比，本文算法具有良好的指紋預(yù)測能力及定位性能，適用于室內(nèi)靜態(tài)定位。

1 基于稀疏指紋采集構(gòu)建指紋庫

基于稀疏指紋采集構(gòu)建指紋庫，需要以下幾個步驟：指紋預(yù)處理、訓練指紋預(yù)測模型、優(yōu)化模型參數(shù)、指紋預(yù)測、構(gòu)建指紋庫。

由于傳播過程中RSS易受影響，本系統(tǒng)采用容錯四分位算法[9]檢測RSS異常值并濾除，對指紋數(shù)據(jù)進行預(yù)處理；將定位區(qū)域內(nèi)的參考點分成兩部分：①稀疏分布于定位區(qū)域內(nèi)，將其指紋數(shù)據(jù)作為高斯過程回歸模型的訓練集；②作為測試集，此設(shè)置要求兩部分參考點不重疊；將訓練集和測試集輸入至模型中，利用訓練集訓練模型，并對測試集進行指紋預(yù)測；模型參數(shù)直接影響模型的預(yù)測能力，本文利用共棲生物搜索算法優(yōu)化模型參數(shù)，以下小節(jié)分別介紹算法的具體實現(xiàn)過程。

1.1 高斯過程回歸

高斯過程回歸(Gaussian process regression，GPR)是機器學習的一種回歸方法，具有嚴格的統(tǒng)計學習理論基礎(chǔ)，與神經(jīng)網(wǎng)絡(luò)、支持向量機相比，易實現(xiàn)、超參數(shù)自適應(yīng)獲取以及輸出具有概率意義，對于處理非線性復(fù)雜問題具有良好的適應(yīng)性[10]。

高斯過程為隨機過程，任何有限數(shù)量集合f(x)服從聯(lián)合高斯分布。D={(x,y)|x∈Rn×d,y∈Rn}為訓練集，其中，x=[x1,x2,…,xn]T為訓練輸入，y=[y1,y2,…,yn]T為輸出，訓練輸入集合服從n維高斯分布，其概率函數(shù)用GP表示，性質(zhì)由均值函數(shù)m(x)和協(xié)方差函數(shù)k(xi,xj)確定。為不失一般性，令均值為零，有f(x)～GP(0,k(xi,xj))[11]。

GPR把系統(tǒng)噪聲ε考慮其中，回歸模型為

yi=f(xi)+ε

(1)

ε具有獨立性，則y也屬于高斯過程。在給定訓練集D中，可以得到目標輸出y的先驗分布為

(2)

對于測試集D*={(x*,y*)|x*∈Rd,y*∈R}，其中，x*為測試輸入；y*為測試輸出，則訓練輸出y和測試輸出y*的聯(lián)合先驗分布為

(3)

(3)式中，協(xié)方差矩陣為

K**=k(x*,x*)

協(xié)方差矩陣定義式中：K表示訓練輸入x的n×n階協(xié)方差矩陣；k(xi,xj)為核函數(shù)，描述xi與xj的相關(guān)性；K*表示訓練輸入x與測試輸入x*的1×n階協(xié)方差矩陣；K**表示測試輸入x*自身的協(xié)方差矩陣。

本文采用最常用的平方指數(shù)核函數(shù)描述不同位置xi與xj間RSS的相關(guān)性[12]為

(4)

根據(jù)貝葉斯后驗概率公式，在已知測試輸入x*與訓練集D的條件下，對應(yīng)的輸出y*滿足

(5)

(6)

(7)

超參數(shù)的取值直接影響模型的預(yù)測能力，傳統(tǒng)超參數(shù)求解方法為共軛梯度法，但該方法在優(yōu)化過程中過于依賴初值，容易陷入局部最優(yōu)[13]。本文利用共棲生物搜索算法代替共軛梯度法優(yōu)化超參數(shù)，將最優(yōu)超參數(shù)回代入(6)式即得到指紋預(yù)測模型。

1.2 共棲生物搜索算法優(yōu)化GPR超參數(shù)

1.2.1 共棲生物算法

2014年，Min Yuan Cheng等提出一種新穎的生物啟發(fā)式算法——共棲生物搜索(symbiotic organisms search，SOS)算法。與其他生物啟發(fā)式算法相比，SOS算法不需要任何特定參數(shù)，正是由于這一特點，陷入局部最優(yōu)而出現(xiàn)早熟的可能性很小，得到全局最優(yōu)的可能性很大[14-15]，非常適合參數(shù)優(yōu)化。本文利用SOS算法優(yōu)化超參數(shù)，模擬生態(tài)系統(tǒng)中物種的3種共棲關(guān)系，通過物種間交互規(guī)則產(chǎn)生新物種，搜索并保留具有最強生存能力的物種。

設(shè)生態(tài)系統(tǒng)的物種數(shù)量為N。第1種共棲關(guān)系為互利關(guān)系，指2個隨機物種Xi，Xj均能通過交互規(guī)則產(chǎn)生新生物種，可以由(8)—(10)式表示為

Xinew=Xi+rand(0,1)×(Xbest-M×BF1)

(8)

Xjnew=Xj+rand(0,1)×(Xbest-M×BF2)

(9)

(10)

(8)—(10)式中：Xi,Xj為原始物種；Xinew,Xjnew為新生物種；Xbest為最優(yōu)物種；rand(0,1)表示在(0,1)的隨機數(shù)；BF1,BF2為受益因子，通常為1或2；M為物種Xi,Xj間關(guān)系特征。

第2種共棲關(guān)系為共生關(guān)系，指2個隨機物種Xi,Xj中只有一個物種Xi能通過交互產(chǎn)生新生物種。該交互規(guī)則為

Xinew=Xi+rand(-1,1)×(Xbest-Xj)

(11)

第3種共棲關(guān)系為寄生關(guān)系，指生態(tài)系統(tǒng)中隨機一個物種Xi充當寄生物，利用隨機數(shù)更改維度產(chǎn)生新生寄生物，新生寄生物與物種Xj競爭生存。

1.2.2 適應(yīng)度函數(shù)

SOS算法優(yōu)化GPR超參數(shù)的適應(yīng)度函數(shù)為訓練集和待優(yōu)化參數(shù)構(gòu)成的對數(shù)似然函數(shù)對超參數(shù)的偏導(dǎo)數(shù)，其表達式為

(12)

適應(yīng)度函數(shù)值最小的物種為最優(yōu)物種，其對應(yīng)的超參數(shù)即為最優(yōu)超參數(shù)，比較新生物種與原始物種的適應(yīng)度函數(shù)值可以表示為

(13)

1.2.3SOS算法優(yōu)化GPR超參數(shù)

SOS算法優(yōu)化GPR超參數(shù)的過程如下。

1)SOS算法初始化：隨機生成N個d維數(shù)組作為物種的初始值X={X1,X2,…,XN}；迭代次數(shù)記t=0，設(shè)置最大迭代次數(shù)tmax；

2)計算各物種初始值的適應(yīng)度函數(shù)，選擇函數(shù)值最小的物種作為生態(tài)系統(tǒng)的最優(yōu)物種Xbest；

3)令Xi=Xbest，增加迭代次數(shù)t=t+1；

4)互利階段：隨機物種Xj與Xi交互產(chǎn)生新生物種，計算新生物種的適應(yīng)度函數(shù)值，與原始物種比較，保留最小函數(shù)值的物種；

5)共生階段：隨機物種Xj按交互規(guī)則使Xi產(chǎn)生新生物種，對比新生物種與原始物種的適應(yīng)度函數(shù)值，保留最小函數(shù)值的物種；

6)寄生階段：隨機物種Xj作為寄生物，通過隨機數(shù)更改維度產(chǎn)生新生寄生物并計算其適應(yīng)度函數(shù)值，保留具有最小適應(yīng)度函數(shù)值的物種；

7)搜索當前生態(tài)系統(tǒng)的最優(yōu)物種Xbest；

8)判斷是否達到tmax，若是，進行步驟9，若否，回到步驟3)繼續(xù)迭代；

9)顯示最優(yōu)物種Xbest。

最優(yōu)物種對應(yīng)的超參數(shù)即為最優(yōu)超參數(shù)，基于最優(yōu)超參數(shù)得到SOS-GPR的預(yù)測模型，輸入定位區(qū)域內(nèi)非參考點的位置，預(yù)測對應(yīng)位置上的RSS后，構(gòu)建指紋存入指紋庫中。

2 改進WKNN算法

在WKNN算法中，定位目標RSS向量與各參考點RSS向量之間的歐氏距離只能表示它們之間的絕對距離。因RSS易受環(huán)境變化的影響，絕對距離并不能反映定位目標與參考點之間的實際位置，需用相對距離來表示它們位置上的相似性，而卡方距離能夠很好地體現(xiàn)特征量之間的相對距離。

用卡方距離(chi-square distance，CSD)描述定位目標與第i個參考點上接收來自第j個AP的RSS的相似度[16]有

(14)

(14)式中：RSSj為定位目標上接收第j個AP的RSS；rssij為第i個參考點上接收第j個AP的RSS。

用卡方距離代替歐氏距離，體現(xiàn)定位目標與各參考點上接收來自各AP的RSS之間的相對關(guān)系，接下來考慮AP加權(quán)問題。在位置指紋定位中，AP的穩(wěn)定性影響定位結(jié)果，本文基于卡方距離對不同AP賦予不同的權(quán)值。

方差可以判別每個AP的穩(wěn)定性，RSS方差較小表示該AP的穩(wěn)定性較好，應(yīng)賦予較大的權(quán)值。計算AP的RSS方差公式為

(15)

那么，第j個AP的RSS對應(yīng)的權(quán)值vj及定位目標與各參考點的相對距離disti為

(16)

(17)

(17)式中，Dij為定位目標與第i個參考點接收來自第j個AP的RSS的卡方距離。

將相對距離disti升序排列，取前K個參考點進行位置估計的表達式為

(18)

(19)

3 實驗與結(jié)果分析

3.1 實驗準備

于遼寧工程技術(shù)大學行政樓一樓進行實驗，該區(qū)域包括辦公室、走廊、大廳，如圖1。實驗環(huán)境內(nèi)有大廳裝飾物、立柱等障礙物。本文將實驗區(qū)域分成實驗區(qū)域1和實驗區(qū)域2，分別進行指紋預(yù)測實驗和定位實驗。實驗過程均使用榮耀8手機作為數(shù)據(jù)采集移動終端，運行系統(tǒng)為Android 4.4，實驗仿真在MATLAB R2013b上完成。

圖1 實驗區(qū)域布局Fig.1 Layout of the experimental area

為驗證本文基于稀疏指紋采集建庫方法的有效性，取大廳中面積為20 m×8 m的典型環(huán)境為實驗區(qū)域1，將該區(qū)域劃分成邊長為1 m的網(wǎng)格，參考點布設(shè)于網(wǎng)格中心位置，在其四角和中心位置布設(shè)5個藍牙beacon基站AP1—AP5，對該區(qū)域內(nèi)160個參考點逐一作AP1—AP5的RSS采集，每個參考點上采集100次，并對采集到的數(shù)據(jù)進行預(yù)處理。

3.2 實驗與結(jié)果分析

3.2.1 指紋預(yù)測實驗與結(jié)果分析

對于SOS-GPR指紋預(yù)測模型來說，若定位區(qū)域內(nèi)所選參考點數(shù)量過少，訓練數(shù)據(jù)無法對整體數(shù)據(jù)分布進行估計，常常會導(dǎo)致過擬合，模型泛化能力差；若參考點數(shù)量過多，又違背了本文減小指紋采集工作量的初衷。所以，為找到最優(yōu)訓練數(shù)據(jù)數(shù)量，在實驗區(qū)域1中均勻選擇40,60,80,100,120個參考點作為模型訓練點，其余120,100,80,60,40個參考點作為模型測試點，共同輸入SOS-GPR模型預(yù)測RSS，計算估計誤差[8]可以表示為

(20)

圖2為SOS-GPR模型在不同訓練點數(shù)量下的RSS估計誤差，為了驗證本文指紋預(yù)測模型的性能，將其與克里金(Kriging)算法、文獻[8]的改進克里金(SA-Kriging)算法進行實驗對比。

圖2 不同訓練點數(shù)的指紋估計誤差Fig.2 Fingerprint estimation errors of different training node numbers

由圖2可看出，隨著訓練點數(shù)量增加，3種指紋預(yù)測方法的估計誤差都在減小。當訓練點數(shù)量為80時，SOS-GPR，SA-Kriging，Kriging算法預(yù)測指紋的估計誤差分別為3.8%，4.9%，5.8%，此時指紋采集工作量為傳統(tǒng)全采集法的50%；當訓練點數(shù)量繼續(xù)增加，SOS-GPR的估計誤差幾乎不再減小，而SA-Kriging算法在訓練點數(shù)為100時估計誤差達到3.9%，此時采集工作量為傳統(tǒng)全采集法的62.5%。

實驗區(qū)域1內(nèi)選取25個定位目標進行定位實驗，定位匹配階段采用傳統(tǒng)WKNN算法，考慮到最近鄰點選擇太多，其中可能摻雜著實際距離較遠的“假最近鄰點”，且K值一般選取3或4[17]，故本文設(shè)置K=3。圖3為基于不同訓練點數(shù)的定位誤差與全采集法定位誤差的對比。

圖3 不同訓練點數(shù)的定位誤差Fig.3 Positioning errors of different training node numbers

由圖3可知，當訓練點數(shù)達到80時，基于SOS-GPR建立指紋庫的定位精度最先趨于全采集法的定位精度，隨著訓練點數(shù)的繼續(xù)增加，其定位誤差幾乎不變?？紤]盡量減小指紋采集量，且估計誤差在可接受范圍內(nèi)，本文選擇全采集法50%的參考點訓練SOS-GPR模型并建立指紋庫。

為了驗證更大區(qū)域內(nèi)基于SOS-GPR建庫方法的效果及改進WKNN算法的定位性能，本文在實驗區(qū)域2進行定位實驗，包括大廳和走廊的實驗環(huán)境。在實驗區(qū)域均勻布設(shè)150個參考點，參考點間距為2 m，通過稀疏指紋采集和SOS-GPR算法構(gòu)建指紋庫。但為了檢驗算法的性能，通過全采集法采集300個參考點的指紋數(shù)據(jù)建立另一個指紋庫，此時參考點間距為1 m，并在定位區(qū)域選取55個定位目標，驗證定位算法的性能。利用樓內(nèi)WLAN基礎(chǔ)設(shè)施，移動終端可檢測到22個AP，這些AP的類型和位置未知。當在參考點上無法檢測到某AP的RSS時，設(shè)置其RSS值為-95 dBm。

對于AP現(xiàn)存的問題：受多徑效應(yīng)影響嚴重的AP穩(wěn)定性差，可能導(dǎo)致定位精度下降；參與定位的AP數(shù)越多計算量越大。為了提高定位精度同時減小計算開銷，通過RSS方差選擇n個穩(wěn)定性好的AP參與定位。分別統(tǒng)計定位區(qū)域內(nèi)參考點上來自各AP的RSS值并計算每個AP的RSS方差，RSS方差越小表示各參考點上檢測到來自AP的RSS值偏離其平均值越小，該AP的穩(wěn)定性越好，適合于定位匹配，否則表示該AP穩(wěn)定性差，不應(yīng)參與定位匹配。確定適合參與定位的AP后，在線階段對定位目標進行特定AP的RSS選擇，形成RSS向量與指紋庫中的指紋進行定位匹配。

為確定參與定位的最佳AP數(shù)，基于全采集法構(gòu)建的指紋庫計算各AP的RSS方差并按升序排列，取前n個AP進行實驗，對比不同AP數(shù)(3～22)對定位精度的影響，實驗結(jié)果如圖4，定位匹配階段本文依然選擇WKNN(K=3)算法。

圖4 不同AP數(shù)量的定位結(jié)果對比Fig.4 Positioning accuracy comparison of different APs

由圖4可看出，當參與定位的AP數(shù)在3～12時，隨著AP數(shù)增加，定位誤差減小；當AP數(shù)為12時，定位誤差最小2.021 m；但AP繼續(xù)增加，定位誤差不再減小，甚至出現(xiàn)增大，例如，AP數(shù)為14或16時對應(yīng)的定位誤差分別為2.078 m和2.113 m。雖然每個AP都能提供位置信息，但并不是參與定位的AP數(shù)越多定位效果越好，穩(wěn)定性好的AP對定位貢獻較大，而穩(wěn)定性弱的AP反而會影響定位精度，本文選取前12 個AP參與定位。

表1 不同超參數(shù)取值對指紋估計誤差的影響

3.2.2 定位實驗

表2展示了3種指紋庫，它們的區(qū)別在于參考點個數(shù)：庫1以稀疏全采集法采集了150個參考點；庫2在庫1的數(shù)據(jù)基礎(chǔ)上由SOS-GPR預(yù)測了150個參考點，庫2共有300個參考點；庫3以密集全采集法采集了300個參考點。

表2 3種位置指紋庫

為驗證改進算法的定位性能，選取參與定位的AP 數(shù)為12，WKNN算法中K值為3，將基于卡方距離和AP加權(quán)的WKNN算法(WKNN algorithm based on chi-square distance and AP weighting,CSW-WKNN)、傳統(tǒng)WKNN算法、基于卡方距離改進的WKNN算法(WKNN algorithm based on chi-square distance,CS-WKNN)以及文獻[18]的M-WKNN(modified-WKNN matching algorithm)算法進行基于表2中3種指紋庫的定位仿真，圖5為4種算法定位結(jié)果的比較。

經(jīng)過仿真實驗，CSW-WKNN算法的定位誤差均比其他3種算法低。在庫1、庫2、庫3中，CS-WKNN算法在1.5 m時定位精度累計概率分別為36.3%，47.2%和45.4%，分別高出傳統(tǒng)WKNN算法10.9%，12.7%和12.7%，表明卡方距離比歐氏距離對環(huán)境噪聲的敏感度低；在庫1、庫2、庫3中，CSW-WKNN算法在1.5 m定位精度累計概率分別為56.3%，72.7%，67.2%，分別高出CS-WKNN算法20%，25.5%，21.7%，高出M-WKNN算法9.1%，16.4%，14.6%，表明加權(quán)AP對定位結(jié)果具有影響。

圖6為庫1、庫2、庫3中4種定位算法在累積概率分別為30%，50%，80%時所對應(yīng)的定位誤差。

圖5 4種算法定位精度對比Fig.5 Comparison of four algorithms positioning accuracy

由圖6可看出，庫2、庫3的定位誤差均小于庫1，表明在定位區(qū)域內(nèi)參考點布設(shè)密集程度對定位結(jié)果具有影響；庫2與庫3定位精度相近，表明基于SOS-GPR建立指紋庫的方法具有可行性；庫2的定位精度略高于庫3的原因在于邊界位置指紋采集的RSS易受外界因素的影響，而本文的指紋預(yù)測模型考慮了噪聲影響因素，故邊界區(qū)域預(yù)測的指紋較采集到的指紋具有穩(wěn)定性。

圖6 定位誤差對比Fig.6 Comparison of positioning errors

在庫1、庫2、庫3中CSW-WKNN算法的平均定位誤差分別為1.514 m，1.091 m，1.181 m，相較于M-WKNN的1.745 m，1.482 m，1.469 m提高了13.23%，26.32%，19.61%。實驗環(huán)境存在的多徑效應(yīng)影響定位精度，本文的CSW-WKNN算法利用卡方距離表示定位目標與參考點位置的相似度，降低信號對環(huán)境的敏感性，對不同AP賦予不同權(quán)值提高定位精度。

4 結(jié)束語

針對位置指紋采集工作量大及定位精度低的問題，本文提出了基于稀疏指紋采集和改進WKNN的定位算法。離線階段，將定位區(qū)域內(nèi)稀疏參考點上采集的RSS進行預(yù)處理，利用預(yù)處理后的指紋數(shù)據(jù)訓練GPR模型，為提高模型的泛化能力，采用SOS算法優(yōu)化模型超參數(shù)；最后SOS-GPR模型預(yù)測非參考點上的RSS，實現(xiàn)由稀疏指紋數(shù)據(jù)構(gòu)建密集指紋庫。在線階段，將WKNN算法中表示定位目標RSS與參考點RSS相似度的歐氏距離換為卡方距離，并對各AP根據(jù)其RSS方差賦予不同的權(quán)值。實驗結(jié)果表明，基于SOS-GPR算法在參考點個數(shù)為全采集法50%的情況下即能得到與之相近的定位精度，且改進WKNN算法能進一步減小定位誤差。

SOS-GPR指紋預(yù)測模型減少了指紋采集工作量，所付出的代價是構(gòu)建指紋庫階段計算量的增加，但指紋預(yù)測模型的訓練數(shù)據(jù)是經(jīng)過預(yù)處理的，減少了原指紋采集過程中會因環(huán)境變化等外界因素產(chǎn)生RSS異常值的情況，提高了指紋庫的可靠性。