基于優(yōu)化最小二乘支持向量機(jī)的室內(nèi)定位算法*

黃 震，羅中良，陳治明

(1. 惠州學(xué)院計算機(jī)科學(xué)系，廣東 惠州 516007;2. 惠州學(xué)院電子科學(xué)系，廣東 惠州 516007)

基于優(yōu)化最小二乘支持向量機(jī)的室內(nèi)定位算法*

黃 震1，羅中良2，陳治明2

(1. 惠州學(xué)院計算機(jī)科學(xué)系，廣東 惠州 516007;2. 惠州學(xué)院電子科學(xué)系，廣東 惠州 516007)

室內(nèi)定位是普適計算應(yīng)用中的關(guān)鍵技術(shù)，針對最小二乘支持向量機(jī)參數(shù)優(yōu)化的難題，提出一種優(yōu)化最小二乘支持向量機(jī)的室內(nèi)定位算法。首先采用主成分分析提取重要定位特征，然后采用最小二乘支持向量機(jī)建立室內(nèi)定位模型，并采用粒子群優(yōu)化算法對最小二乘支持向量機(jī)參數(shù)進(jìn)行優(yōu)化，最后采用仿真實驗測試定位性能。結(jié)果表明，文中算法提高了室內(nèi)定位的精度且定位時間少于其它室內(nèi)定位算法，具有一定的實際應(yīng)用價值。

普適計算；室內(nèi)定位；參數(shù)優(yōu)化；主成分分析

普適計算是新一代的信息技術(shù)，集成通信技術(shù)、電子技術(shù)以及計算機(jī)技術(shù)，用戶可以隨時隨地獲取自己需求的資源，其在智能電梯、環(huán)境監(jiān)控、物流管理等領(lǐng)域得到了成功的應(yīng)用[1]。定位技術(shù)是普適計算一個比較底層的技術(shù)，在普適計算應(yīng)用中扮演重要的角色，定位技術(shù)根據(jù)應(yīng)用場景分為兩類：室內(nèi)定位和室外定位，當(dāng)前在室外空曠的環(huán)境下，一些技術(shù)如GPS定位的精度相當(dāng)高，可以滿足實際應(yīng)用的需求，但是室內(nèi)環(huán)境十分復(fù)雜，障礙物多、信號有多徑現(xiàn)象，GPS不能在室內(nèi)環(huán)境中工作，導(dǎo)致室內(nèi)定位難度增加，因此室內(nèi)定位一直是無線定位技術(shù)研究中的難點(diǎn)[2-4]。

為了實現(xiàn)室內(nèi)準(zhǔn)確定位，人們引入各種技術(shù)對其進(jìn)行研究，出現(xiàn)了一些室內(nèi)定位算法。室內(nèi)定位技術(shù)主要基于位置指紋進(jìn)行設(shè)計，其工作過程分為兩個階段[5]：離線和在線。離線階段主要負(fù)責(zé)“指紋”數(shù)據(jù)的采集，即將設(shè)備放在參考點(diǎn)收集接受信號強(qiáng)度指示(received signal strength indicator，RSSI)信息，構(gòu)建無線信號地圖，但是由于室內(nèi)環(huán)境的復(fù)雜性，RSSI信息具有時變性和噪聲，極不穩(wěn)定，如果直接利用RSSI值作為定位算法的輸入進(jìn)行室內(nèi)定位，定位結(jié)果可靠性差，準(zhǔn)確性低；同時輸入的RSSI信息比較多，具有嚴(yán)重的冗余，因此需要對RSSI值進(jìn)行預(yù)處理[6-8]。當(dāng)前位置指紋匹配的算法主要有神經(jīng)網(wǎng)絡(luò)、支持向量機(jī)、加權(quán)K鄰居算法等[9-13]，其中加權(quán)K鄰居算法最簡單、十分容易實現(xiàn)，但是利用其進(jìn)行室內(nèi)定位，處理結(jié)果誤差比較大差，實際應(yīng)用價值不大；神經(jīng)網(wǎng)絡(luò)的室內(nèi)定位精度要高于加權(quán)K鄰居算法，但是其要求訓(xùn)練樣本的數(shù)量比較多，使得室內(nèi)定位成本增加；支持向量機(jī)比神經(jīng)網(wǎng)絡(luò)的室內(nèi)定位精度進(jìn)一步提高，要求訓(xùn)練樣本的數(shù)量少，但是其訓(xùn)練時間耗時比較長，室內(nèi)定位的效率低。

為了改善室內(nèi)定位效果，提出一種優(yōu)化最小二乘支持向量機(jī)的室內(nèi)定位算法(PCA-PSO-LSSVM)。首先采用主成分分析對原始信息進(jìn)行處理提取重要特征，然后采用最小二乘支持向量機(jī)(least squares support vector machine，LSSVM)對特征向量與位置信息之間的關(guān)系進(jìn)行擬合，并采用粒子群優(yōu)化(particle swarm optimization algorithm,PSO)算法對最小二乘支持向量機(jī)進(jìn)行優(yōu)化，仿真實驗結(jié)果表明，相對傳統(tǒng)定位算法，PCA-PSO-LSSVM能夠獲得更高精度的室內(nèi)定位結(jié)果，提升了室內(nèi)定位的效率，可以滿足室內(nèi)定位的實際應(yīng)用需求。

1 RSSI模型

室內(nèi)定位受到障礙物、信號多徑化等多因素影響，使RSSI的變化大、不穩(wěn)定，本文選擇路徑-損耗模型估計RSSI的值，計算公式如下：

(1)

式中，Xσ～N(0,σ2)為噪聲。

對式(1)進(jìn)行簡化，可以得到：

(2)

式中，RSSI(d0)為與發(fā)射地點(diǎn)1 m的RSSI值。

d0為1 m，最后RSSI的計算公式為：

RSSI(d)=RSSI(d0)-10nlgd

(3)

式中，n為損耗系數(shù)。

2 PCA-PSO-LSSVM的室內(nèi)定位

2.1 主成分分析(PCA)

采集到原始RSSI特征之后，對它們進(jìn)行主成分分析。

1) 建立原始特征的向量矩陣A，具體為：

(4)

其中，n是特征總數(shù)。

2) 對A進(jìn)行標(biāo)準(zhǔn)化處理，可以得到矩陣B：

(5)

(6)

(7)

3) 計算協(xié)方差矩陣BTB， 并得到相應(yīng)的特征值和向量P，且滿足：

PTBTBP=Λ

(9)

(10)

4) 計算累計貢獻(xiàn)率，取累計貢獻(xiàn)率超過85%的特征作為主成分：

(11)

2.2 最小二乘支持向量機(jī)(LSSVM)

支持向量機(jī)計算復(fù)雜度與訓(xùn)練樣本的數(shù)量密切相關(guān)，因此對于大規(guī)模的訓(xùn)練樣本，支持向量機(jī)的計算復(fù)雜度相當(dāng)高，訓(xùn)練的效率比較低，影響室內(nèi)定位的實時性，而LSSVM對支持向量機(jī)的損失函數(shù)進(jìn)行改進(jìn)，減少待定參數(shù)，訓(xùn)練速度加快，應(yīng)用范圍更廣泛。設(shè)訓(xùn)練樣本集為：{(xi,yi)},i=1,2,…n，xi∈Rn,yi∈R，LSSVM的最優(yōu)線性回歸方程如下：

(12)

式中，w為權(quán)值向量，b為偏置量。

基于結(jié)構(gòu)風(fēng)險最小化原理可以得到：

s.t.

(13)

式中，γ為正則化參數(shù)；ei為擬合誤差。

采用拉格朗日乘子(αi)對式(13)進(jìn)行簡化，得到：

(14)

核函數(shù)為K(xi,xj)=φ(xi)Tφ(xj)，這樣可以得到：

(15)

采用RBF構(gòu)建LSSVM，其為：

(16)

式中，σ為RBF參數(shù)。

LSSVM回歸函數(shù)為：

(17)

2.3 粒子群優(yōu)化(PSO)算法

PSO算法通過粒子追隨自己歷史最優(yōu)解(Pbest)和粒子群的歷史最優(yōu)解(gbest)找到問題的最優(yōu)解，粒子速度和位置的更新公式為：

(18)

(19)

式中，vid(i)和vid(id+1)分別為粒子當(dāng)前和更新后的速度；xid(i)和xid(id+1)分別為粒子當(dāng)前和更新后的位置；w為慣性權(quán)重；c1、c2為加速因子[14]。

在LSSVM擬合室內(nèi)定位的特征向量與位置信息之間的關(guān)系時，LSSVM學(xué)習(xí)性能取決于參數(shù)γ和σ，為此本文采用PSO算法優(yōu)化LSSVM，參數(shù)γ和σ優(yōu)化的數(shù)學(xué)模型為：

(20)

2.4 PCA-PSO-LSSVM的室內(nèi)定位

1) 確定指紋位置，并采集相應(yīng)的RSSI值，建立無線電地圖，采用PCA提取對室內(nèi)定位結(jié)果有重要貢獻(xiàn)的定位特征，并將其保存在特征數(shù)據(jù)庫中，然后將定位特征作為輸入向量和位置信息輸出構(gòu)建LSSVM的訓(xùn)練樣本集，采用PSO算法選擇LSSVM參數(shù)γ和σ建立擬合特征與位置關(guān)系的定位模型。

2) 對測試樣本集進(jìn)行處理，然后采用建立好的室內(nèi)定位模型估計其位置信息。

基于PCA-PSO-LSSVM的室內(nèi)定位算法框架如圖1所示。

圖1 PCA-PSO-LSSVM算法的框架Fig.1 Framework of the PCA-PSO-LSSVM algorithm

3 結(jié)果與分析

為了驗證PCA-PSO-LSSVM的室內(nèi)定位有效性，實驗環(huán)境為學(xué)院大樓的室內(nèi)大廳，包括過道、實驗室、辦公室等定位區(qū)域，每一個位置均有一些障礙物，在不同時間對每個位置點(diǎn)RSSI值進(jìn)行采集， PCA-LSSVM(手工方式確定LSSVM參數(shù))、PCA-GA-LSSVM(遺傳算法優(yōu)化LSSVM參數(shù))進(jìn)行對比測試，采用定位誤差和平均定位誤差對室內(nèi)定位結(jié)果進(jìn)行評價，計算公式為：

(21)

(22)

式中，n表示測試點(diǎn)的數(shù)量。

采用LSSVM擬合特征向量與位置信息之間的關(guān)系時，參數(shù)γ和σ的選擇至關(guān)重要，采用PCA-LSSVM和PCA-GA-LSSVM以及PCA-PSO-LSSVM進(jìn)行定位實驗，參數(shù)如表1所示。定位結(jié)果如圖2所示，可以得到如下結(jié)論：

1) 相對于PCA-LSSVM，PCA-GA-LSSVM以及PCA-PSO-LSSVM的定位精度均有不同程度的提高，因為其它條件相同，這種優(yōu)勢是因為GA、PSO算法可以找到更加合理的LSSVM參數(shù)γ和σ的值，建立的LSSVM可以更好擬合特征向量與位置信息之間的映射關(guān)系，定位結(jié)果更加可靠。

2) PCA-GA-LSSVM，PCA-PSO-LSSVM的室內(nèi)定位精度更加理想，這是由于PSO算法較好的避免了GA易陷入局部極值的缺陷，難以搜索到全局最優(yōu)的參數(shù)γ和σ，而PSO算法通過粒子的迭代過程中，可以找到更優(yōu)參數(shù)γ和σ值，實驗結(jié)果驗證了PSO算法解決LSSVM參數(shù)優(yōu)問題的優(yōu)越性。

表1 LSSVM參數(shù)γ和σ的值

圖2 PCA-PSO-LSSVM與對比算法的定位誤差對比Fig.2 Location error comparison of PCA-PSO-LSSVM with other algorithms

為了測試室內(nèi)定位的實時性，在4核 Intel 2.80 GHz CPU，8 GB 內(nèi)存，Win7操作系統(tǒng)，Matlab 2012的測試平臺上統(tǒng)計PCA-LSSVM、PCA-GA-LSSVM和PCA-PSO-LSSVM的運(yùn)行時間，結(jié)果見表2。從表2的運(yùn)行時間可知，PCA-LSSVM的運(yùn)行時間最短，因為其是手工直接確定參數(shù)γ和σ的值，因此實時性最好，但是全憑經(jīng)驗設(shè)置參數(shù)，其定位精度太低，無法應(yīng)用于實踐；而PCA-PSO-LSSVM的運(yùn)行時間要少于PCA-GA-LSSVM，主要是因為PSO算法尋優(yōu)速度要優(yōu)于GA，使 LSSVM的訓(xùn)練時間變短，定位的實時性更優(yōu)，更符合室內(nèi)定位要求，能給用戶帶來更好的室內(nèi)定位結(jié)果。

表2 運(yùn)行時間對比

4 結(jié) 論

針對室內(nèi)定位過程中的特征提取和LSSVM參數(shù)優(yōu)化難題，提出基于PCA-PSO-LSSVM的室內(nèi)定位算法，該算法采用PCA提取RSSI信息中對定位結(jié)果貢獻(xiàn)重要的特征，對數(shù)據(jù)進(jìn)行一定的壓縮，減少LSSVM的輸入維數(shù)，然后采用LSSVM擬合特征與位置信息的非線性關(guān)系，采用PSO算法搜索最優(yōu)參數(shù)，測試結(jié)果表明，PCA-PSO-LSSVM的定位精度要高于其它算法，而且運(yùn)行時間更具優(yōu)勢，可以給用戶帶來更好的室內(nèi)定位效果。

[1] GU Y Y, LO A, NIEMEGEERS I. A survey of indoor location systems for wireless personal networks [J]. IEEE Communications Surveys & Tutorials, 2009, 11(1): 13-32.

[2] 鄧罡,陳穎文,徐明,等. 無線傳感器網(wǎng)絡(luò)環(huán)境感知的節(jié)點(diǎn)定位方法[J]. 中山大學(xué)學(xué)報(自然科學(xué)版), 2008, 47(6): 114-119.

[3] 孫寅博,王宏剛,李波. 基于參考標(biāo)簽的射頻識別室內(nèi)定位算法研究[J]. 電視技術(shù),2015, 39(1): 109-112.

[4] 周錦,李煒,金亮,等. 基于KNN-SNM算法的室內(nèi)定位系統(tǒng)設(shè)計[J]. 華中科技大學(xué)學(xué)報(自然科學(xué)版), 2015, 43(1): 517-520.

[5] 蔡朝暉,夏溪,胡波,等. 室內(nèi)信號強(qiáng)度指紋定位算法改進(jìn)[J].計算機(jī)科學(xué),2014,41(11):178-181.

[6] 徐風(fēng)燕,石鵬,王宗欣. 基于參數(shù)擬合的距離-損耗模型室內(nèi)定位算法[J]. 電路與系統(tǒng)學(xué)報, 2009, 12(1):1-5.

[7] 張會清,石曉偉,鄧貴華,等. 基于BP神經(jīng)網(wǎng)絡(luò)和泰勒級數(shù)的室內(nèi)定位算法研究[J]. 電子學(xué)報,2012,40(9):1876-1880.

[8] 劉春燕,王堅. 基于幾何聚類指紋庫的約束KNN室內(nèi)定位模型[J]. 武漢大學(xué)學(xué)報(信息科學(xué)版) , 2014, 39(11): 1287-1291.

[9] 谷紅亮, 史元春.一種用于智能空間的多目標(biāo)跟蹤室內(nèi)定位系統(tǒng)[J]. 計算機(jī)學(xué)報, 2007, 30(9): 1603-1611.

[10] 蒙靜. IR_UWB定位系統(tǒng)距離誤差建模及性能研究[J]. 通信學(xué)報, 2011,32(6):10-16.

[11] 林以明,羅海勇,李錦濤,等. 基于動態(tài)Radio Map的粒子濾波室內(nèi)無線定位算法[J]. 計算機(jī)研究與發(fā)展, 2011,48(1):139-146.

[12] 徐玉濱,鄧志安,馬琳. 基于核直接判別分析和支持向量回歸的 WLAN 室內(nèi)定位算法[J]. 電子與信息學(xué)報, 2014, 25(11):2631-2651.

[13] 石柯, 陳洪生, 張仁同. 一種基于支持向量回歸的802.11無線室內(nèi)定位方法[J]. 軟件學(xué)報, 2014, 25(11):2631-2651.

[14] 曾艷姍,李仲飛. 基于粒子群優(yōu)化算法的均值 -VaR投資組合選擇[J]. 中山大學(xué)學(xué)報(自然科學(xué)版), 2012, 51(6): 1-9.

Indoor location algorithm based on optimizing least square support vector machine

HUANGZhen1,LUOZhongliang2,CHENZhiming2

(1. Department of Computer Science, Huizhou University, Huizhou 516007 China;2. Department of Electronic Science, Huizhou University, Huizhou 516007 China)

Indoor location is a key technology in the application of pervasive computing, and aims at solving the problem of least square support vector machine parameters. An indoor localization algorithm based on the least square support vector machine is proposed. The principal component analysis is used to extract important features, and then, least square support vector machine is established for indoor localization model using particle swarm optimization algorithm. The simulation experiment is used to test location performance. The results show that the proposed algorithm improves the accuracy of indoor location, and the location time is less than other indoor location algorithm.

pervasive computing; indoor location; parameter optimization; principal component analysis

10.13471/j.cnki.acta.snus.2016.02.009

2015-11-29

廣東省科技計劃資助項目(2012B010100038)；廣東省高等學(xué)校教學(xué)質(zhì)量與改革工程本科類資助項目(粵高教函[2013]113號-113，粵高教函[2015]173號-584)；惠州市科技計劃資助項目(2015ZX023)；惠州學(xué)院自然科學(xué)資助項目(hzuxl201417)

黃震(1980年生)，男 ；研究方向：無線傳感器網(wǎng)絡(luò)、智能算法；通訊作者：陳治明;E-mail:1276106@qq.com

TP

A

0529-6579(2016)02-0048-04