張 震， 關(guān)維國(guó)， 鄒 穎

(遼寧工業(yè)大學(xué) 電子與信息工程學(xué)院，遼寧 錦州121001)

0 引 言

隨著移動(dòng)通信技術(shù)的快速發(fā)展，基于位置的室內(nèi)定位服務(wù)越來(lái)越受到人們的關(guān)注[1]。無(wú)線保真(wireless fidelity，WiFi)信號(hào)覆蓋范圍廣且WiFi通信模塊廣泛應(yīng)用在智能終端上，使得基于WiFi的定位技術(shù)備受關(guān)注。WiFi定位方法主要包括幾何測(cè)距法和指紋識(shí)別法[2]。幾何測(cè)距法利用信號(hào)傳播模型進(jìn)行位置估計(jì)，但信號(hào)模型受環(huán)境影響比較大，定位精度較低。位置指紋法通過(guò)創(chuàng)建信號(hào)強(qiáng)度與位置坐標(biāo)的指紋庫(kù)進(jìn)行定位，定位精度更高且易于部署，成為了研究的熱門方向[3]。

位置指紋法在離線階段建立接收信號(hào)強(qiáng)度指示(received signal strength indication，RSSI)與位置的數(shù)據(jù)庫(kù)，對(duì)在線測(cè)量的RSSI和數(shù)據(jù)庫(kù)進(jìn)行匹配，從而完成定位。文獻(xiàn)[4]提出基于RSSI概率分布重疊面積的指紋相似度匹配算法實(shí)現(xiàn)定位，但需要建立準(zhǔn)確的RSSI概率分布模型。文獻(xiàn)[5]采用K-means聚類算法對(duì)指紋數(shù)據(jù)初始分類，使用隨機(jī)森林算法進(jìn)行二次分類，但算法計(jì)算量比較大。文獻(xiàn)[6]提出了基于最小二乘支持向量機(jī)(least square support vector machine，LSSVM)的定位方法，LSSVM由于其泛化性能強(qiáng)，算法定位效果較好，但沒(méi)有研究模型參數(shù)優(yōu)化方法。文獻(xiàn)[7]采用最小二乘支持向量回歸機(jī)完成三維定位，通過(guò)粒子群算法對(duì)定位模型參數(shù)進(jìn)行優(yōu)化，具有不錯(cuò)的定位效果,但粒子群算法全局尋優(yōu)能力差，模型優(yōu)化效果不明顯。

本文提出一種基于改進(jìn)多核加權(quán)最小二乘向量回歸(improved multiple kernel weighted least square support vector regression，IMK-WLSSVR)的WiFi室內(nèi)定位算法。針對(duì)傳統(tǒng)基于單核WLSSVR模型的定位效果不佳，選用多項(xiàng)式核函數(shù)和高斯徑向基核函數(shù)通過(guò)線性加權(quán)確定多核函數(shù)，依據(jù)模型擬合誤差為每個(gè)指紋樣本分配不同的權(quán)值，建立RSSI值與位置坐標(biāo)的非線性映射；采用改進(jìn)的模擬退火(improved simulated annealing，ISA)算法進(jìn)一步優(yōu)化模型參數(shù)，通過(guò)優(yōu)化的定位模型進(jìn)行定位，有效提高算法的定位精度。

1 IMK-WLSSVR算法

本文提出的基于IMK-WLSSVR的定位方法主要分為離線訓(xùn)練階段和在線定位階段。離線訓(xùn)練階段，在定位環(huán)境中選定指紋點(diǎn)，然后采集各個(gè)指紋點(diǎn)上的RSSI值，將指紋點(diǎn)RSSI樣本值和對(duì)應(yīng)位置作為輸入樣本對(duì)，采用多項(xiàng)式核函數(shù)和高斯徑向基核函數(shù)構(gòu)建多核函數(shù)，利用正態(tài)分布權(quán)值函數(shù)計(jì)算每個(gè)指紋點(diǎn)的權(quán)值，建立IMK-WLSSVR定位模型，并采用ISA算法確定IMK-WLSSVR參數(shù)，構(gòu)造RSSI值和位置坐標(biāo)的非線性映射。在線定位階段，在待定位點(diǎn)采集RSSI值，通過(guò)構(gòu)造好的IMK-WLSSVR模型估算待定位點(diǎn)的實(shí)際位置。

1.1 多核函數(shù)構(gòu)建

核函數(shù)可以解決非線性關(guān)系，但在室內(nèi)環(huán)境中，RSSI受到多徑、陰影效應(yīng)的影響，單核方法往往不能很好擬合RSSI，因此，為了提高定位精度，采用多核方法建立定位模型。為了更好擬合RSSI值與位置的非線性映射，本文選用全局性核函數(shù)即三階多項(xiàng)式核結(jié)合局部性核函數(shù)即高斯核,通過(guò)線性加權(quán)構(gòu)建多核函數(shù)[8]

K=λ1Kpoly+λ2KRBF,

s.t.λ1+λ2=1

(1)

(2)

式中y(i)為第i個(gè)坐標(biāo)y的真實(shí)值，y′(i)為相應(yīng)的模型估計(jì)值,則每個(gè)基核函數(shù)的權(quán)重λm為

(3)

同理可得到坐標(biāo)x的多核函數(shù)。

1.2 IMK-WLSSVR建模

定位問(wèn)題的關(guān)鍵就是獲取RSSI值與位置坐標(biāo)之間的映射關(guān)系，可以采用人工神經(jīng)網(wǎng)絡(luò)和最小二乘支持回歸機(jī)擬合位置和信號(hào)強(qiáng)度的非線性映射[9]。本文利用基于多核的WLSSVR算法構(gòu)造RSSI值與位置坐標(biāo)的非線性關(guān)系，有效提高模型的定位精度。

支持向量回歸[10](support vector regression ，SVR)具有良好的非線性性能，但其訓(xùn)練過(guò)程涉及二次規(guī)劃問(wèn)題，導(dǎo)致訓(xùn)練時(shí)計(jì)算復(fù)雜。作為SVR的擴(kuò)展，最小二乘支持向量回歸(least square support vector regression，LSSVR)算法[11]利用最小二乘方法將二次規(guī)劃問(wèn)題等價(jià)為線性方程組求解, 有效提高了SVR運(yùn)算速度，但算法魯棒性能欠佳。Suykens J A K等人在LSSVR算法的基礎(chǔ)上提出加權(quán)最小二乘支持向量回歸(weighted least square support vector regression，WLSSVR)算法[12]，從而有效提高了LSSVR算法魯棒性能。

假設(shè)Pi=(pi1,pi2,…piM) 表示指紋點(diǎn)(xi,yi)處接收到來(lái)自M個(gè)WiFi熱點(diǎn)的RSSI向量，通過(guò)一個(gè)非線性映射φ，將RSS值映射到高維特征空間F，在高維空間中構(gòu)造物理位置y與RSSI向量的最優(yōu)回歸關(guān)系

(4)

式中Wk∈H為權(quán)系數(shù)，λk≥0為第k個(gè)核函數(shù)的系數(shù)，b為偏置矩陣。根據(jù)結(jié)構(gòu)風(fēng)險(xiǎn)化最小原則，將二次規(guī)劃問(wèn)題轉(zhuǎn)化為

(5)

建立式(5)對(duì)應(yīng)的拉格朗日函數(shù)

(6)

分別求取式(6)關(guān)于各變量的偏微分

(7)

式(7)消去向量Wk,β和η，可得式(8)

(8)

(9)

解式(9)可得

α=(Ω+γ-1ω)-1(Y-b·E)

(10)

由式(10)可求出最優(yōu)回歸函數(shù)

(11)

坐標(biāo)x求解過(guò)程與上述方法類似，根據(jù)式(1)和式(11)，可得指紋點(diǎn)的RSSI向量與物理位置的非線性關(guān)系

(12)

在IMK-WLSSVR定位模型中，不同的定位誤差ηi對(duì)應(yīng)不同的權(quán)重ωi，選取恰當(dāng)?shù)臋?quán)重可以有效降低異常指紋數(shù)據(jù)對(duì)模型定位精度的影響，本文采用基于正態(tài)分布的加權(quán)函數(shù)表達(dá)式為：

|ηi|<0.2μ或|ηi|>0.8μ

(13)

1.3 多核模型參數(shù)優(yōu)化

IMK-WLSSVR算法的定位性能與支持向量回歸機(jī)參數(shù)(懲罰因子γ、核參數(shù)σ、C)的選擇有著極為緊密的聯(lián)系。文獻(xiàn)[13]提出了基于網(wǎng)格搜索的SVR優(yōu)化方法，但網(wǎng)格方法搜索模型參數(shù)的精度較低，優(yōu)化性能不理想。為了提高IMK-WLSSVR定位模型的定位性能，本文改進(jìn)模擬退火算法來(lái)優(yōu)化模型參數(shù)。模擬退火算法[14,15]作為一種全局搜索算法，以一定的幾率接受差解，擴(kuò)大了算法搜索范圍，避免尋優(yōu)過(guò)程陷于局部最優(yōu)，提高了算法得到全局最優(yōu)解的概率。

本文將當(dāng)前溫度值加入到擾動(dòng)模型中，在接近最優(yōu)解時(shí)能減緩擾動(dòng)幅度；同時(shí)，增加一個(gè)最優(yōu)參數(shù)變量，從而保證在退火過(guò)程中始終保持最優(yōu)解?；诟倪M(jìn)模擬退火算法的IMK-WLSSVR定位模型參數(shù)優(yōu)化過(guò)程如下：

1)設(shè)定待優(yōu)化參數(shù)γ,δ,C范圍，溫度T1和擾動(dòng)步長(zhǎng)V0，隨機(jī)生成γ,δ,C并作為當(dāng)前優(yōu)解γbest,δbest,Cbest。依據(jù)式(12)得到當(dāng)前參數(shù)下的IMK-WLSSVR模型，計(jì)算位置預(yù)測(cè)值與真實(shí)值的均方根誤差S。

2)在溫度Tm下，根據(jù)式(14)擾動(dòng)模型計(jì)算新參數(shù)γ1，δ1，C1，計(jì)算新參數(shù)下的位置坐標(biāo)均方根誤差S′,選擇其中誤差最小的參數(shù)作為γbest,δbest,Cbest，然后與上一次的誤差S比較，若S′小，則接受新參數(shù)；若S大，則計(jì)算ΔS=S′-S，并生成一個(gè)(0,1)范圍的隨機(jī)值ρ，若exp(-ΔS/Tk)大于ρ，接受新參數(shù)，否則拋棄新參數(shù)，并對(duì)上一次參數(shù)重新擾動(dòng)

(14)

式中θ為(0,1)范圍內(nèi)的隨機(jī)數(shù)。

3)若到達(dá)規(guī)定迭代次數(shù)，則更新溫度Tm+1=Tm·α，迭代次數(shù)清零并跳至步驟(2)，否則直接跳轉(zhuǎn)至步驟(2)。若Tk小于最低溫度，算法終止，輸出待優(yōu)化參數(shù)的最優(yōu)值組合(γbest,δbest,Cbest)。

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

2.1 實(shí)驗(yàn)條件

室內(nèi)定位環(huán)境選取學(xué)校3號(hào)教學(xué)樓8層實(shí)驗(yàn)實(shí)訓(xùn)室，如圖1所示。實(shí)驗(yàn)選用6個(gè)型號(hào)為TL-WR886N的WiFiAP，AP固定高度為2 m,使用華為手機(jī)采集各WiFiAP的RSSI值，手機(jī)與地面相隔1.2 m。實(shí)驗(yàn)布置了60個(gè)指紋點(diǎn)和60個(gè)測(cè)試點(diǎn)，指紋點(diǎn)的間距是3 m,每個(gè)指紋點(diǎn)位置采集50個(gè)樣本，每次間隔5 s，測(cè)試點(diǎn)位置隨機(jī)選取，每個(gè)位置采集10次。實(shí)驗(yàn)選擇60組指紋數(shù)據(jù)作為訓(xùn)練樣本建立IMK-WLSSVR定位模型，利用訓(xùn)練好的模型對(duì)60組測(cè)試數(shù)據(jù)進(jìn)行定位測(cè)試，實(shí)驗(yàn)對(duì)比了WKNN，LSSVR及MK-WLSSVR算法。

圖1 室內(nèi)定位測(cè)試

2.2 實(shí)驗(yàn)結(jié)果分析

為了驗(yàn)證本文的IMK-WLSSVR算法的有效性，分別采用WKNN、LSSVR、MK-WLSSVR和IMK-WLSSVR4種方法進(jìn)行定位對(duì)比。其中，WKNN的近鄰數(shù)為4，LSSVR算法的核函數(shù)選取徑向基函數(shù)。構(gòu)建等價(jià)核函數(shù)，利用式(3)計(jì)算每個(gè)基核函數(shù)的權(quán)重λ1=0.46，λ2=0.54，由式(13)確定各個(gè)指紋點(diǎn)的權(quán)值，建立LSSVR模型、MK-WLSSVR模型及IMK-WLSSVR模型， 3種模型的定位誤差如圖2所示。

圖2 不同模型定位誤差對(duì)比

從圖2可知，組合核函數(shù)MK-WLSSVR的總體預(yù)測(cè)性能較好，其預(yù)測(cè)誤差小于單一核函數(shù)LSSVR模型。IMK-WLSSVR模型具備較好的抗干擾性和較高的定位精度，通過(guò)調(diào)整模型誤差的權(quán)重，進(jìn)一步減小了位置估計(jì)誤差，其定位誤差小于MK-WLSSVR的定位誤差，表明IMK-WLSSVR模型精度更高、泛化能力更強(qiáng)。根據(jù)圖2的模型定位誤差計(jì)算得到均方根誤差，IMK-WLSSVR的均方根誤差為1.54 m，優(yōu)于LSSVR的1.86 m、MK-WLSSVR的1.68 m，可見(jiàn)本文算法的定位誤差受影響較小，抗噪性能良好。

同時(shí)，為了驗(yàn)證ISA算法對(duì)IMK-WLSSVR參數(shù)尋優(yōu)的有效性，分別使用網(wǎng)格搜索以及改進(jìn)的模擬退火算法方法優(yōu)化模型參數(shù)，利用IMK-WLSSVR模型來(lái)估計(jì)測(cè)試點(diǎn)位置。

圖3所示的是使用ISA優(yōu)化算法平均定位誤差的對(duì)比，改進(jìn)模擬退火算法的誤差相比網(wǎng)格搜索定位誤差明顯減小，說(shuō)明了ISA算法對(duì)IMK-WLSSVR模型的參數(shù)優(yōu)化可以有效減少定位誤差。對(duì)于通過(guò)IMK-WLSSVR構(gòu)建RSSI值和物理位置的映射關(guān)系的過(guò)程中，ISA算法有著良好的全局優(yōu)化IMK-WLSSVR算法參數(shù)的能力，使得IMK-WLSSVR有著更好的學(xué)習(xí)能力和泛化能力。

圖3 網(wǎng)格搜索法與ISA算法的誤差對(duì)比

3 結(jié) 論

將本文算法與WKNN算法、LSSVR算法及MK-WLSSVR算法進(jìn)行定位對(duì)比。實(shí)驗(yàn)結(jié)果表明：LSSVR算法因其泛化性好的優(yōu)點(diǎn)，定位精度比WKNN較好；本文算法的平均誤差為1.54 m，最大誤差為3.3 m，在定位精度上相比于其他三種方法有明顯提高，定位精度得到明顯提升，可滿足實(shí)際室內(nèi)定位需求。