李新春,房梽斅,張春華

(1.遼寧工程技術(shù)大學(xué)電子與信息工程學(xué)院,遼寧 葫蘆島 125105;2.遼寧工程技術(shù)大學(xué)研究生學(xué)院,遼寧 葫蘆島 125105; 3.中國聯(lián)合網(wǎng)絡(luò)通信集團有限公司阜新市分公司,遼寧 阜新 123100)

目前,隨著互聯(lián)網(wǎng)和移動終端的全面普及,基于位置服務(wù)的相關(guān)技術(shù)在民用、商用、軍用等定位場所的應(yīng)用越來越廣泛[1-2]。在室外環(huán)境中,GPS可實現(xiàn)高精度定位,但在室內(nèi)環(huán)境中,由于接收信號強度受到室內(nèi)建筑物結(jié)構(gòu)布局以及人員遮擋等因素限制[3],基于無線局域網(wǎng)絡(luò)WLAN(Wireless Local Area Networks)的位置指紋定位算法更有優(yōu)勢[1,4]。目前WLAN網(wǎng)絡(luò)的覆蓋率越來越高,基于WLAN定位具有成本低、設(shè)備功耗小、布網(wǎng)方便等優(yōu)點,使其成為獲取接入點數(shù)量AP(Access point)無線信號強度的首選[5]。在傳感器和移動網(wǎng)絡(luò)環(huán)境中,無線網(wǎng)絡(luò)更容易受到干擾,協(xié)作傳輸過程,外來接入點有機會充當中繼,接收信號強度RSS(Received Signal Strength)值的波動性更大[6],有必要快速準確地提取其主成分。

通常情況下,指紋定位算法主要分為兩個階段[7]:離線訓(xùn)練階段和在線定位階段。離線訓(xùn)練階段采集參考點來自各個AP的RSS值,構(gòu)成原始位置指紋向量X,與其物理位置Y一一對應(yīng),構(gòu)成離線數(shù)據(jù)矩陣(X,Y),通過訓(xùn)練得到RSS值和其位置坐標的映射關(guān)系Y=f(X),構(gòu)成指紋庫;在線階段采集待測參考點的信號強度,構(gòu)成在線位置指紋向量X*,利用離線階段構(gòu)成的匹配回歸模型,預(yù)測待測參考點的位置坐標Y*。這種室內(nèi)定位模型的定位精度主要取決于離線階段和在線階段是否服從同一定位模型。

室內(nèi)定位算法有KNN、WKNN和PCA-WKNN 3種傳統(tǒng)算法。KNN是一種監(jiān)督式機器學(xué)習(xí)算法,在線階段對待測點RSS值分別計算它與指紋庫中各個向量的歐式距離,選取最近的多個指紋作為預(yù)測位置;WKNN算法對指紋庫中各個向量給予權(quán)重,權(quán)重與歐式距離成反比,使其結(jié)果更接近真實性;PCA-WKNN算法采用PCA算法對離線獲取的RSS矩陣降維,在線階段利用WKNN算法進行對比。針對以上傳統(tǒng)算法,許多專家學(xué)者進行了改進。

文獻[8]采用PCA算法對RSS矩陣進行降維,提取其主要特征信息,通過RSS的特征與其對應(yīng)位置關(guān)系,對測試點的位置進行預(yù)測;文獻[9]利用PCA方法降維處理離線階段獲取的位置指紋,以解決因外在環(huán)境問題對信號強度獲取造成的不確定測量,采用LSSVR算法通過非線性映射使低維不可分樣本映射到高維空間,使位置指紋做線性可分類處理。文獻[10]采用單乘法神經(jīng)元(SMN)算法來提高定位精度,離線和在線階段均采用PCA算法來減小RSS的維度并消除噪聲。以上3種算法直接進行降維處理,均未充分利用位置指紋之間的特征信息,導(dǎo)致訓(xùn)練的離線回歸模型不能準確定位待測點,定位誤差較大。文獻[11]采用支持向量機(SVM)對離線階段各接入點的信號強度信息進行特征提取,并用WKNN算法進一步分類,創(chuàng)建離線指紋數(shù)據(jù)庫,在線階段利用指紋庫特征值去修正定位誤差;文獻[12]采用分段匹配追蹤算法來構(gòu)造離線指紋數(shù)據(jù)庫,在線階段采用最小二乘算法預(yù)測位置信息;文獻[13]采用非線性偏最小二乘法(PLS)減少指紋數(shù)據(jù)庫維度,并采用內(nèi)部相關(guān)向量機(RVM)訓(xùn)練離線回歸模型。以上3種算法未根據(jù)特征信息的優(yōu)劣訓(xùn)練離線回歸模型,導(dǎo)致定位誤差較大,且在線階段不能快速實現(xiàn)定位,雖在一定程度上提高了定位準確度,但在訓(xùn)練離線指紋數(shù)據(jù)庫方面仍需改進。

本文針對上述室內(nèi)定位算法定位準確率不高的問題,提出了一種基于KPCA和改進GBRT的室內(nèi)定位算法。在離線階段,采用KPCA算法提取RSS主成分,并利用改進GBRT算法訓(xùn)練離線回歸模型;在線階段根據(jù)離線回歸模型預(yù)測位置信息。通過仿真實驗結(jié)果表明,在相同定位條件下,本文室內(nèi)定位算法在AP數(shù)量、RSS樣本數(shù)量等方面均優(yōu)于傳統(tǒng)的PCA-WKNN室內(nèi)定位算法、文獻[10]的SMN-PCA算法和文獻[13]的RVM-PLS算法,定位誤差更小,實際應(yīng)用效果更好。

1 基于KPCA和改進GBRT的室內(nèi)定位算法

基于KPCA和改進GBRT的室內(nèi)定位算法,命名為KPCA-IGBRT,定位算法流程如圖1所示。

1.1 原始指紋向量采集及預(yù)處理

圖1 KPCA-IGBRT室內(nèi)定位算法流程

由于RSS值的不穩(wěn)定性,同一位置接收的RSS值波動較大,在定位算法處理之前,首先需要對RSS值進行去噪處理。

(1)

利用貝塞爾公式計算數(shù)據(jù)的標準差s,如式(2)所示。

(2)

計算格拉布斯檢驗統(tǒng)計量Gi,如式(3)所示,其中i為異常值的排列序號。

(3)

依據(jù)格拉布斯(Grubbs)法,把Gi與格拉布斯表[14]給出的臨界值Gp(n)相比較,若GiGp(n),則此數(shù)據(jù)為異常值,需要剔除,并繼續(xù)檢測下一個可疑值,直到所有數(shù)據(jù)均滿足Gi

采用式(4)標準化RSS值,使每一個RSS值都在0～1范圍內(nèi),用來簡化和加速訓(xùn)練過程。

(4)

1.2 KPCA算法提取核主成分

主成分分析(PCA)方法是識別領(lǐng)域中的經(jīng)典算法,主要利用降維的思想,把高維中的有效特征信息在低維空間中明顯地展示出來;而KPCA算法[15],主要方式是采用核函數(shù),將原始指紋矩陣在低維空間不能明顯顯示的特征信息,通過非線性映射函數(shù)Φ在更高維的特征空間Q上表現(xiàn)出來,并對Q降維運算,其中心思想是盡可能多地保留訓(xùn)練集中方差的同時,減少該特征訓(xùn)練集的維度[16]。

設(shè)非線性映射函數(shù)Φ將原始位置指紋空間F={F1,F2,…,FM}映射到更高維度的特征空間Q={Φ(F1),Φ(F2),…,Φ(FN)},由于特征空間Q非中心化,需對其做中心化處理,如式(5)所示。

(5)

求解中心化的特征空間Q′的協(xié)方差矩陣,如式(6)所示。

(6)

計算協(xié)方差矩陣特征值λ及其對應(yīng)的特征向量V,如式(7)所示。

(7)

(8)

(9)

定義N×N階核函數(shù)K,它的各個元素表達式如式(10)所示。

Kij=(Φ(Fi)TΦ(Fj))

(10)

進一步推導(dǎo)則有

(11)

進一步化簡可得

(12)

其中矩陣C為N維矩陣,每個元素都是1/N,則式(9)可以化簡為

(13)

(14)

(15)

將式(11)代入式(15)中可得式(16),即KPCA算法提取原始位置指紋的核主成分。

(16)

非線性映射函數(shù)Φ中,高斯核函數(shù)是最高效的,利用高斯核函數(shù)提取的核主成分可最大程度地表示數(shù)據(jù)間的非線性特征信息,高斯核函數(shù)如式(17)所示。

(17)

1.3 IGBRT算法構(gòu)建回歸模型

梯度提升回歸GBRT算法是泛化能力較強的一種回歸算法,由多棵決策樹組成。而IGBRT算法主要采用自助抽樣法,從初始訓(xùn)練集中有放回的均勻抽樣構(gòu)成多個子訓(xùn)練集。計算一個訓(xùn)練集的回歸模型,初始時,GBRT算法為每一個低維空間的特征賦同一個初值,即每一個特征信息都一樣重要。訓(xùn)練特征信息后每一次得到新的模型,會導(dǎo)致對特征信息的預(yù)測有一定的誤差[17-18]。為了消除每一次訓(xùn)練特征信息的錯誤,通過在減小誤差最快的方向上構(gòu)建新的回歸模型,且只需學(xué)習(xí)上一次模型的殘差,使原來的模型的殘差向梯度減小的方向上進行收斂。

IGBRT算法采用多個回歸模型替代一個回歸模型,從初始特征樣本集中抽樣,有放回地隨機選取大小和特征集T一樣的子特征集T(i),構(gòu)成k個子特征集,作為各個回歸模型的初始特征集。在一個子特征集中,可能含有多個重復(fù)的樣本。

假設(shè)一個回歸模型初始值如式(18)所示。

(18)

在構(gòu)建一個回歸模型過程中,首先找到最優(yōu)切分點j與切分點s,如式(19)所示,遞歸地將每個區(qū)域劃分為兩個子區(qū)域,并計算每個子區(qū)域的輸出值,構(gòu)建一棵二叉決策樹。

(19)

輸入空間根據(jù)選定的(j,s)劃分區(qū)域R決定相應(yīng)的輸出值,如式(20)所示。

Ti(RSS)=cmI

(20)

回歸模型繼續(xù)學(xué)習(xí)真實值L與二叉決策樹迭代后的預(yù)測值fk(RSS)的差,即擬合殘差rki作為下一次學(xué)習(xí)的位置信息,如式(21)所示。

(21)

調(diào)用式(19)～式(21)循環(huán)迭代M次,結(jié)束生成M棵樹。

將一個子特征集T(i)劃分為M個區(qū)域R1,R2,…,Rm,得到m個二叉分類決策樹,訓(xùn)練一個回歸模型,如式(22)所示。

(22)

綜上所述,IGBRT算法得到的強回歸模型(23)由多個式(22)的回歸模型組成。

(23)

1.4 在線位置指紋處理

在線定位階段,測試點采集來自每個接入點的無線信號強度,構(gòu)成在線位置指紋向量F,利用式(16)對F進行KPCA變換,得到位置指紋非線性特征向量F′,然后送入強學(xué)習(xí)模型式(23)進行學(xué)習(xí),得到每個模型輸出的位置信息,最終預(yù)測結(jié)果根據(jù)各個回歸模型的預(yù)測位置輸出的眾數(shù)而定。

圖2 實驗定位區(qū)域

2 實驗結(jié)果及仿真分析

2.1 實驗設(shè)置

為驗證本文改進室內(nèi)定位算法的定位情況,考慮諸多因素后,實驗場所選在遼寧工程技術(shù)大學(xué)靜遠樓進行,選擇西門8 m×8 m的大廳作為實驗場所,其定位區(qū)域如圖2所示。在選定的定位場所中,包含立柱、裝飾品等,并放置兩排桌椅作為障礙物,在第1排桌子上放置手機、電腦等一些干擾裝置。整個實驗場所干擾噪聲較復(fù)雜,采集的無線信號強度較不穩(wěn)定但具有代表性。

采集數(shù)據(jù)過程起點為矩形中心,其初始的位置坐標設(shè)為(0,0)。數(shù)據(jù)采集位置如圖3所示,參考位置以中心點為圓心,半徑為1時,每隔60°選取參考點;半徑為2時,每隔30°選取參考點;半徑為3時,每隔20°選取參考點;半徑為4時,每隔20°選取參考點。實驗區(qū)域一共54個參考位置,其采集位置如圖3中的RP;另外在定位場所選取10個測量點,采集位置如圖3中的TP,可得到RP和TP真實的物理坐標;在線定位過程,測量待測點實時的無線信號強度,按照一定的順序組成指紋向量,通過本文改進的回歸模型估算待測點的物理坐標,并用估計坐標與實際坐標的比較結(jié)果,判斷本文改進算法的定位情況。

實驗過程中,在定位區(qū)域共布設(shè)8個AP設(shè)備,過程忽略了AP設(shè)備性能對算法的不確定影響;參考點設(shè)備使用vivo X9i手機作為數(shù)據(jù)采集移動終端,每個參考點都經(jīng)過100次測量,構(gòu)成原始位置指紋向量,實驗仿真在MATLAB R2014a上完成。

實驗場所的局部測量結(jié)果如表1所示,把其中的測量數(shù)據(jù)作為初始位置指紋向量,通常情況下表中的數(shù)據(jù)不用經(jīng)過處理即可作為初始實驗數(shù)據(jù)用來算法研究。

實驗數(shù)據(jù)采集100次,去噪過程設(shè)定檢出水平為0.1,那么置信概率P=0.9,則格拉布斯表給出的臨界值Gp(n)=3.017。

圖3 RSS數(shù)據(jù)采集位置

實驗數(shù)據(jù)經(jīng)過去噪歸一化處理后,有放回地隨機抽取36次,構(gòu)成36個訓(xùn)練集計算回歸模型。

每一棵決策樹的構(gòu)建都經(jīng)過GBRT算法處理,由多棵二叉樹迭代的方式去替代一棵決策樹,每棵決策樹都是學(xué)習(xí)上一棵決策樹的殘差,避免了單棵決策樹出現(xiàn)過擬合現(xiàn)象,最終形成一個強學(xué)習(xí)器模型。

實驗過程采用定位精度和平均定位誤差SE(Standard Error)作為評判指標來比較5種室內(nèi)定位算法。原始位置指紋向量在核主成分提取,即根據(jù)式(16)得到特征空間為五維和十二維的數(shù)據(jù)矩陣,如表2和表3所示。

表1 進行100次采集的原始指紋數(shù)據(jù)庫RSS 單位:dBm

表2 特征空間五維的數(shù)據(jù)庫

表3 特征空間十二維的數(shù)據(jù)庫

2.2 AP數(shù)量對算法性能的影響

在室內(nèi)定位算法中,AP數(shù)量是衡量室內(nèi)定位算法性能的重要指標。一般情況下,AP數(shù)量越多,算法定位效果越好,平均定位誤差越小。實驗過程中,選取表1中前2～8個AP測量數(shù)據(jù)作為參考數(shù)據(jù),KPCA算法將原始指紋映射到15維特征空間,IGBRT算法構(gòu)建36個強學(xué)習(xí)回歸模型,每個回歸模型由15個二叉決策樹組成。

圖4是AP數(shù)量變化對平均定位誤差的影響,從圖中可以看出5種定位算法隨著AP數(shù)量增多,算法平均定位誤差越小。當AP數(shù)量為8時,KPCA-IGBRT算法的平均定位誤差達到了1.16 m,明顯優(yōu)于1.51m的PCA-WKNN算法、1.43 m的SMN-PCA算法、1.29m的RVM-PLS算法和1.48 m的IGBRT算法。當AP數(shù)量從6增加7時,平均定位誤差變化不大,原因可能是隨著AP數(shù)量增多,引入更多的誤差,對定位效果產(chǎn)生影響。

圖4 平均定位誤差隨AP數(shù)量變化

表4為AP數(shù)量為8時,5種定位算法結(jié)果對比。從表中可知,本文算法在方差上能夠提供相對可靠的數(shù)據(jù)。IGBRT算法在平均定位誤差與SMN-PCA、RVM-PLS算法接近,但是方差較大,可能的原因是構(gòu)建回歸模型時,沒有提取主成分,而是隨機地采用RSS值。

表4 5種算法定位結(jié)果對比 單位:m

由圖4可知,上述5種算法的平均定位誤差在0.5 m～3 m,選取1.5 m來判斷5種誤差定位算法的準確度。圖5是誤差為1.5 m時5種算法的定位準確率情況,從圖中可以看出5種算法用于定位的AP數(shù)量越多,在線定位精度越高,且本文算法明顯優(yōu)于其他4種算法。當AP數(shù)量為8時,本文算法在誤差距離為1.5m的定位精度達到71.2%,相比于PCA-WKNN、SMN-PCA、RVM-PLS和IGBRT算法的48.8%,58.4%,61.1%和55.7%,分別提高了22.4%、12.8%、10.1%和15.5%。從圖4和圖5中可以看出,在相同的定位條件下,本文改進算法需要更少的AP數(shù)量。

圖5 誤差1.5 m的定位準確度

2.3 離線階段RSS樣本數(shù)量對算法性能的影響

室內(nèi)定位算法中,另一個影響算法定位性能的因素是各個測量點上無線信號強度的樣本數(shù)量,它用來表示離線過程提取位置指紋向量特征信息消耗的時間。在定位精度相同的情況下,需要的無線信號強度的樣本數(shù)量越少,表示此算法提取位置指紋特征信息需要的時間越少。

圖6是在AP數(shù)量為8時,本文定位算法隨不同RSS數(shù)量變化的定位情況,從圖中可以看出5種定位算法的RSS樣本數(shù)量越多,定位準確率越高。顯然,當RSS樣本數(shù)量達到20時,本文提出的算法定位精度已經(jīng)達到57.8%,遠遠優(yōu)于45.8%的PCA-WKNN算法、39.1%的SMN-PCA算法、51.2%的RVM-PLS算法和50.2%的IGBRT算法,而PCA-WKNN算法需要RSS樣本數(shù)量為80時才可以與本文算法定位準確率相同,因此本文改進算法與5種算法相比,需要更少的RSS樣本數(shù)量就可以達到更高的定位準確率。在RSS數(shù)量增多的情況下,定位準確率不是一味的提高,產(chǎn)生的原因可能是引入了更多的噪聲,對定位結(jié)果造成影響。

圖6 定位算法隨不同RSS數(shù)量變化的定位情況

2.4 特征位置指紋空間的維度對定位算法的影響

圖7是定位精度隨非線性特征空間維度Q的定位變化,從圖中可以看出在特征空間維度Q增加的情況下,定位準確率也越來越高。當Q為16時,定位精度已達到0.85 m;當Q>16時,定位精度隨Q的影響趨于穩(wěn)定;當Q為22時,定位精度可達到0.82 m。

圖7 定位算法隨特征指紋空間維度的定位情況

2.5 模型離線訓(xùn)練和測試平均時間對算法的影響

表5是在AP數(shù)量為8,RSS樣本數(shù)量為100,KPCA的特征空間維度為15時,各個模型離線訓(xùn)練和測試平均時間。從表中可以看出,離線訓(xùn)練時間PCA-WKNN算法最短達到26.752 s,IGBRT和KPCA-IGBRT算法次之,產(chǎn)生這種現(xiàn)象的原因是PCA-WKNN算法處理RSS計算量較小,IGBRT算法并行化方法訓(xùn)練多個回歸模型;測試平均時間SMN-PCA算法最短達到0.034 6 ms,IGBRT和KPCA-IGBRT算法次之,但是SMN-PCA離線訓(xùn)練時間最長。綜合離線訓(xùn)練和測試平均時間,IGBRT和KPCA-IGBRT算法最好,而KPCA-IGBRT算法比IGBRT算法定位誤差更小,因此選取KPCA-IGBRT算法,在實際應(yīng)用中效果更好。

表5 模型離線訓(xùn)練和測試平均時間

3 結(jié)束語

本文針對真實WLAN網(wǎng)絡(luò)中無線信號強度易受環(huán)境等因素影響而產(chǎn)生的噪聲問題,提出了一種基于KPCA和改進GBRT的室內(nèi)定位算法。該算法在離線過程訓(xùn)練離線指紋數(shù)據(jù)庫,得到離線強回歸模型;在線階段根據(jù)離線回歸模型估測在線位置。實驗結(jié)果表明,在相同的定位條件下,本文室內(nèi)定位算法在AP數(shù)量、RSS樣本數(shù)量等方面均優(yōu)于PCA-WKNN、SMN-PCA、RVM-PLS和IGBRT 4種算法,在更少的AP和RSS數(shù)量的情況下,定位誤差更小,且模型離線訓(xùn)練和測試平均時間相對更少,實際應(yīng)用效果更好。本研究考慮到測試場所設(shè)備有限,不同型號的接入點和接收端設(shè)備都可能對無線信號強度獲取產(chǎn)生不確定影響,并且整個實驗過程的測試位置是不移動的,對可移動目標的定位情況尚需進一步深入研究。