李新春,房梽斅,張春華

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

目前,隨著互聯(lián)網(wǎng)和移動(dòng)終端的全面普及,基于位置服務(wù)的相關(guān)技術(shù)在民用、商用、軍用等定位場所的應(yīng)用越來越廣泛[1-2]。在室外環(huán)境中,GPS可實(shí)現(xiàn)高精度定位,但在室內(nèi)環(huán)境中,由于接收信號(hào)強(qiáng)度受到室內(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)點(diǎn),使其成為獲取接入點(diǎn)數(shù)量AP(Access point)無線信號(hào)強(qiáng)度的首選[5]。在傳感器和移動(dòng)網(wǎng)絡(luò)環(huán)境中,無線網(wǎng)絡(luò)更容易受到干擾,協(xié)作傳輸過程,外來接入點(diǎn)有機(jī)會(huì)充當(dāng)中繼,接收信號(hào)強(qiáng)度RSS(Received Signal Strength)值的波動(dòng)性更大[6],有必要快速準(zhǔn)確地提取其主成分。

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

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

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

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

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

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

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

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

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

(1)

利用貝塞爾公式計(jì)算數(shù)據(jù)的標(biāo)準(zhǔn)差s,如式(2)所示。

(2)

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

(3)

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

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

(4)

1.2 KPCA算法提取核主成分

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

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

(5)

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

(6)

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

(7)

(8)

(9)

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

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

(10)

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

(11)

進(jìn)一步化簡可得

(12)

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

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

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

(18)

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

(19)

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

Ti(RSS)=cmI

(20)

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

(21)

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

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

(22)

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

(23)

1.4 在線位置指紋處理

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

圖2 實(shí)驗(yàn)定位區(qū)域

2 實(shí)驗(yàn)結(jié)果及仿真分析

2.1 實(shí)驗(yàn)設(shè)置

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

由圖4可知,上述5種算法的平均定位誤差在0.5 m～3 m,選取1.5 m來判斷5種誤差定位算法的準(zhǔn)確度。圖5是誤差為1.5 m時(shí)5種算法的定位準(zhǔn)確率情況,從圖中可以看出5種算法用于定位的AP數(shù)量越多,在線定位精度越高,且本文算法明顯優(yōu)于其他4種算法。當(dāng)AP數(shù)量為8時(shí),本文算法在誤差距離為1.5m的定位精度達(dá)到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中可以看出,在相同的定位條件下,本文改進(jìn)算法需要更少的AP數(shù)量。

圖5 誤差1.5 m的定位準(zhǔn)確度

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

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

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

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

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

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

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

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

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

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

3 結(jié)束語

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