基于微粒群優(yōu)化LSSVM的室內(nèi)指紋定位算法

趙妍 樂燕芬 施偉斌

摘 要：為了降低利用最小二乘支持向量機(jī)（LSSVM）定位過程中參數(shù)選取對(duì)定位精度的影響，提出一種基于微粒群進(jìn)行參數(shù)優(yōu)化的室內(nèi)指紋定位算法。該算法通過離線采集的RSSI數(shù)據(jù)訓(xùn)練最小二乘支持向量機(jī)，利用微粒群算法尋找并確定LSSVM全局最優(yōu)參數(shù)，獲得基于位置指紋的LSSVM定位模型。仿真結(jié)果表明，相對(duì)于傳統(tǒng)LSSVM定位，PSO-LSSVM有效提高了定位準(zhǔn)確度，并能在小樣本情況下保持良好的定位精度。

關(guān)鍵詞：指紋定位;微粒群算法;最小二乘支持向量機(jī);RSSI

DOI：10. 11907/rjdk. 182266

中圖分類號(hào)：TP312文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：1672-7800（2019）004-0087-04

0 引言

隨著無線通信技術(shù)、互聯(lián)網(wǎng)技術(shù)的不斷發(fā)展，具有自組網(wǎng)能力的無線傳感器網(wǎng)絡(luò)（WSN）已成為學(xué)者們關(guān)注的熱點(diǎn)[1-2]。傳感器節(jié)點(diǎn)定位是WSN領(lǐng)域的主要應(yīng)用之一，然而傳感器節(jié)點(diǎn)大多布置在礦井下或地下停車場、商場等各種復(fù)雜室內(nèi)環(huán)境中，室外基于GPS信號(hào)的定位方式易受到環(huán)境非視距、干擾多變、多徑等因素影響而難以實(shí)現(xiàn)。因此，如何獲取傳感器節(jié)點(diǎn)位置信息成為WSN室內(nèi)定位應(yīng)用中必須考慮的問題之一[3]。

針對(duì)節(jié)點(diǎn)定位問題，國內(nèi)外許多學(xué)者進(jìn)行了深入研究，提出了大量可行的室內(nèi)定位算法。當(dāng)前常用定位算法主要包括基于接收信號(hào)強(qiáng)度指示 （Received Signal Strength Indicator，RSSI）[4]、到達(dá)時(shí)間（Time of Arrival，TOA）[5]、到達(dá)時(shí)間差（Time Difference of Arrival， TDOA）[6]與到達(dá)角度（Angle of Arrival，AOA）[7]的定位算法等，其中基于RSSI位置指紋[8]的室內(nèi)定位算法是 WSN 定位中的一種常用定位算法。該算法基于監(jiān)控區(qū)域內(nèi)已知若干參考位置點(diǎn)的無線信號(hào)強(qiáng)度分布，匹配獲得目標(biāo)移動(dòng)節(jié)點(diǎn)位置。然而，由于受到復(fù)雜多變的室內(nèi)環(huán)境因素影響，位置節(jié)點(diǎn)的RSS值具有較強(qiáng)時(shí)變性，從而降低了定位精度，同時(shí)在離線階段需要訓(xùn)練大量樣本點(diǎn)，不利于大場景應(yīng)用[9]。因此，很多學(xué)者提出將機(jī)器學(xué)習(xí)的一些理論，如核嶺回歸（Kernel-based Ridge Regression）[10-11]、支持向量機(jī)（Support Vector Machine，SVM）[12-16]、神經(jīng)網(wǎng)絡(luò)[17]等引入室內(nèi)定位中。

文獻(xiàn)[10]、[11]提出基于機(jī)器學(xué)習(xí)理論結(jié)合卡爾曼濾波的RSSI指紋定位方法，將核嶺回歸引入卡爾曼濾波觀測方程中，解決了非線性回歸問題，并求解了雙重優(yōu)化問題。該算法能夠提高定位精度，但其不足之處在于對(duì)核函數(shù)寬度選取、嶺回歸方程參數(shù)確定比較復(fù)雜，定位速度慢;文獻(xiàn)[12]、[13]均采用基于SVM分類回歸的定位算法，首先對(duì)特征數(shù)據(jù)庫數(shù)據(jù)進(jìn)行分類訓(xùn)練，然后通過SVM回歸算法建立RSS信號(hào)與位置的數(shù)學(xué)模型，從而實(shí)現(xiàn)室內(nèi)定位。該算法對(duì)采集特征向量經(jīng)過無監(jiān)督聚類后的值建立特征數(shù)據(jù)庫，在一定程度上減少了在線定位階段的計(jì)算量，提高了定位準(zhǔn)確性。但是隨著樣本數(shù)據(jù)的增多，在SVM中求解二次規(guī)劃問題變得更加復(fù)雜，訓(xùn)練時(shí)間也會(huì)更長，從而影響了其實(shí)際應(yīng)用價(jià)值。

為了提高節(jié)點(diǎn)定位精度與效率，本文結(jié)合最小二乘支持向量機(jī)（Least Square Support Vector Machine，LSSVM）和微粒群算法的優(yōu)點(diǎn)，提出一種基于微粒群優(yōu)化LSSVM的室內(nèi)指紋定位算法（PSO-LSSVM）。利用微粒群算法對(duì)最小二乘支持向量機(jī)參數(shù)進(jìn)行優(yōu)化，可以有效改善模型訓(xùn)練性能，進(jìn)而提高LSSVM在室內(nèi)定位算法中的定位精度。

1 基本理論

1.1 LSSVM原理

支持向量機(jī)基本思想是通過一個(gè)非線性映射，將數(shù)據(jù)從輸入空間映射到高維特征空間，將實(shí)際問題轉(zhuǎn)化成凸二次規(guī)劃問題。最小二乘支持向量機(jī)（LSSVM）修正了支持向量機(jī)的損失函數(shù)和約束條件，相比于標(biāo)準(zhǔn)SVM算法，其簡化了復(fù)雜性，從而提高了運(yùn)算速度[17]。

綜上可知，建立基于LSSVM的室內(nèi)定位模型，通過確定[g]的值有利于參數(shù)優(yōu)化。

1.2 微粒群算法

微粒群優(yōu)化算法（PSO）是由Kennedy&Eberhart提出的一種智能優(yōu)化算法[19]，其所需參數(shù)少，且容易實(shí)現(xiàn)。本文利用粒子群算法對(duì)LSSVM參數(shù)進(jìn)行全局最優(yōu)化，并對(duì)優(yōu)化后的參數(shù)建立定位模型，以更好地體現(xiàn)定位輸入與輸出之間的非線性關(guān)系，而且不易受環(huán)境因素影響。

2 基于LSSVM的室內(nèi)指紋定位算法

2.1 算法介紹

室內(nèi)指紋定位原理是利用位置特征信息，例如信號(hào)強(qiáng)度指示、空間頻譜、圖像亮度等，將相關(guān)定位特征信息與該位置建立映射關(guān)系，并作為一個(gè)信息集合，組成一個(gè)獨(dú)特的指紋信息，建立指紋信息庫（Fingerprint或Radio-map）。本文提出的基于LSSVM的室內(nèi)指紋定位算法主要包括兩個(gè)階段：離線訓(xùn)練（地圖生成）階段和在線匹配階段。

（1）離線訓(xùn)練階段。在待定位區(qū)域放置若干錨節(jié)點(diǎn)，通過采集某位置特征信息訓(xùn)練樣本數(shù)據(jù)，即記錄每個(gè)位置點(diǎn)的RSSI 信息并作為該位置特征數(shù)據(jù)，稱為位置指紋;然后將所有位置指紋保存到數(shù)據(jù)庫中，得到一張無線電地圖;最后利用定位區(qū)域若干位置點(diǎn)的訓(xùn)練樣本進(jìn)行LSSVM訓(xùn)練，并采用微粒群算法優(yōu)化LSSVM參數(shù)，得出基于位置指紋的LSSVM定位模型。

（2）在線匹配階段。當(dāng)移動(dòng)節(jié)點(diǎn)在待定位區(qū)域內(nèi)移動(dòng)時(shí)，將實(shí)時(shí)接收到的RSSI信息輸入到LSSVM模型，通過模型計(jì)算出移動(dòng)節(jié)點(diǎn)位置。

綜上所述，基于LSSVM的室內(nèi)指紋定位模型如圖1所示。

2.2 PSO-LSSVM定位算法具體步驟

LSSVM參數(shù)γ、g對(duì)其性能影響很大，然而γ、g通常很難確定，一般工程采用窮舉法確定參數(shù)。為了優(yōu)化LSSVM定位模型，本文采用PSO優(yōu)化LSSVM。步驟如下：

（1）離線訓(xùn)練階段：①建立訓(xùn)練樣本，并對(duì)樣本數(shù)據(jù)進(jìn)行預(yù)處理;②導(dǎo)入種群大小、迭代次數(shù)、變異概率最大與最小值等參數(shù)，以及需要訓(xùn)練的RSSI樣本值;③初始化參數(shù)γ、g，以及每一個(gè)微粒位置、速度、pbest和gbest等，初始化LSSVM模型，并計(jì)算初始適應(yīng)度值;③通過PSO中的粒子運(yùn)動(dòng)迭代優(yōu)化參數(shù)γ、g;④按照公式（7）、（8）更新微粒速度與位置，計(jì)算適應(yīng)度值，并更新個(gè)體、全局極值;⑤更新微粒群體全局極值;⑥判斷是否滿足迭代條件，如果滿足則終止尋優(yōu)，輸出全局最優(yōu)值，否則跳轉(zhuǎn)到步驟④繼續(xù)尋優(yōu);⑦由步驟⑥得到最優(yōu)參數(shù)γ和g，并構(gòu)建定位模型。

（2）在線定位階段：將需要定位坐標(biāo)接收的RSSI值輸入到LSSVM模型，即可輸出對(duì)應(yīng)位置坐標(biāo)。

算法具體實(shí)現(xiàn)過程如圖2所示。

3 仿真實(shí)驗(yàn)及分析

為了驗(yàn)證粒子群優(yōu)化最小二乘支持向量機(jī)算法的可行性與正確性，首先對(duì)傳統(tǒng)LSSVM采用試湊法選取模型參數(shù)，運(yùn)用PSO優(yōu)化算法對(duì)LSSVM輸入信號(hào)進(jìn)行全局最優(yōu)選擇，并將本文方法與傳統(tǒng)LSSVM方法作對(duì)比。

3.1 仿真環(huán)境

為了測試PSO-LSSVM室內(nèi)定位算法性能，本文利用Matlab R2016b仿真軟件進(jìn)行驗(yàn)證，并利用奧村-哈他（Okumura-Hata）模型[19，21]生成RSSI 測試數(shù)據(jù)，即：

本文使用的訓(xùn)練樣本數(shù)據(jù)為900個(gè)，測試樣本數(shù)據(jù)為100個(gè)，每個(gè)樣本由9個(gè)來自不同錨節(jié)點(diǎn)的RSSI值構(gòu)成。仿真實(shí)驗(yàn)環(huán)境及參數(shù)設(shè)置如表1所示。

3.2 結(jié)果與分析

本文采用PSO對(duì)LSSVM進(jìn)行參數(shù)優(yōu)化，PSO具體參數(shù)如下：種群大小為20，迭代次數(shù)為100代。本文將測試樣本模型預(yù)測結(jié)果的均方誤差作為適應(yīng)度，適應(yīng)度曲線如圖3所示。在前60代，適應(yīng)度逐漸上升，60代之后適應(yīng)度則逐漸收斂并趨于平穩(wěn)，此時(shí)可得到全局最優(yōu)參數(shù)，即[γ]=2.863 9、[g]=0.008 1，且收斂速度快、定位精度高、效果好。

圖4是PSO-LSSVM預(yù)測模型與傳統(tǒng)LSSVM模型預(yù)測結(jié)果對(duì)比。從圖4可看出，相比于傳統(tǒng)LSSVM算法，PSO-LSSVM算法誤差更小，可將大多數(shù)目標(biāo)位置估計(jì)結(jié)果控制在2.5m以內(nèi)，且許多估計(jì)誤差在1.5m內(nèi)。從定位誤差上可以看出，基于PSO優(yōu)化的LSSVM算法比傳統(tǒng)LSSVM算法定位精度更高，說明采用PSO算法獲取LSSVM參數(shù)建立的定位模型，能更好地反映輸入與輸出之間的非線性關(guān)系。

PSO-LSSVM與傳統(tǒng)LSSVM兩種算法定位統(tǒng)計(jì)結(jié)果如圖5所示。由圖5可知，PSO-LSSVM算法在2m內(nèi)的定位概率達(dá)到80%以上，而傳統(tǒng)LSSVM算法定位概率僅為60%。因此，PSO-LSSVM算法在定位精度方面優(yōu)于傳統(tǒng)LSSVM算法。

表2為分別通過PSO-LSSVM與傳統(tǒng)LSSVM方式得到的懲罰因子γ和徑向基核函數(shù)g，采用PSO優(yōu)化后預(yù)測模型平均定位誤差為1.69m，相對(duì)了傳統(tǒng)LSSVM預(yù)測模型定位結(jié)果，定位誤差有所提高。由此可以看出，粒子群算法改進(jìn)了最小二乘支持向量機(jī)的定位性能，也證明了粒子群優(yōu)化最小支持向量機(jī)定位的可行性。

4 結(jié)語

為了降低支持向量機(jī)室內(nèi)定位過程中參數(shù)選取對(duì)定位精度的影響，提出一種基于微粒群優(yōu)化LSSVM的室內(nèi)指紋定位算法。該方法通過微粒群算法尋找最優(yōu)參數(shù)，并利用離線采集的RSSI數(shù)據(jù)訓(xùn)練最小二乘支持向量機(jī)，從而獲得基于位置指紋的LSSVM定位模型。仿真實(shí)驗(yàn)結(jié)果表明，將RSSI作為定位特征向量輸入能有效提高PSO-LSSVM的定位精度，尤其在小樣本學(xué)習(xí)情況下從而精度很高。與傳統(tǒng)定位算法相比，該算法定位性能更好，具有一定應(yīng)用價(jià)值。但是由于訓(xùn)練樣本數(shù)據(jù)量較大，增加了計(jì)算量，訓(xùn)練時(shí)間也較長。因此，如何在保證精度的情況下，進(jìn)一步減少訓(xùn)練時(shí)間將是未來的研究方向。

參考文獻(xiàn)：

[1] 馮亞超，賀康，楊紅麗，等. 一種無線傳感器網(wǎng)絡(luò)數(shù)據(jù)收集協(xié)議的研究與優(yōu)化[J]. 傳感技術(shù)學(xué)報(bào)，2014，27（3）：355-360.

[2] AKYILDIZ W S，SANAKARASUBRAMANIAM Y，CAYICI E，et al. Wireless sensor networks：a survey[J]. Computer Networks，2002，38（4）：393-422.

[3] HAO Z，WANG S. Survey on localization algorithms for wireless sensor networks[J]. Journal of Huazhong University of Science and Technology （Natural Science Edition），2008，36（1）：224-227.

[4] LI X，ZHOU F，DU J. LDTS：a lightweight and dependable trust system for clustered wireless sensor network[J].IEEE Transactions on Information Forensics and Security，2013，99：1.

[5] CHONG C Y，KUMAR S P. Sensor networks：evolution，opportunities， and chanllenges[J]. Proceedings of the IEEE，2003.

[6] 汪煬. 基于無線傳感器網(wǎng)絡(luò)定位技術(shù)研究[D]. 合肥：中國科技大學(xué)，2007.

[7] 朱曉娟，孟祥瑞. 基于加權(quán)質(zhì)心的無線傳感器網(wǎng)絡(luò)動(dòng)態(tài)節(jié)點(diǎn)定位算法[J]. 計(jì)算機(jī)工程與科學(xué)，2011，33（11）：15-19.

[8] JAVIER R，VALENTíN B，ESCUDERO C J. Architecture for multi-technology real-time location systems[J]. Sensors，2013，13（2）：2220-2253.

[9] 徐玉濱，鄧志安，馬琳. 基于核直接判別分析和支持向量機(jī)回歸的WLAN室內(nèi)定位算法[J]. 電子與信息學(xué)報(bào)，2011，33（4）：13-17.

[10] MAHFOUZ S，MOURAD-CHEHADE F，HONEINE P，et al. Target tracking using machine learning and Kalman filter in wireless sensor networks[J].? Sensors Journal IEEE，2014，14（10）：3715-3725.

[11] 邱愛昆.? 基于機(jī)器學(xué)習(xí)的 WiFi 高精度定位研究[D]. 無錫：江南大學(xué)，2016.

[12] 桑楠，袁興中，周瑞. 基于SVM分類和回歸的WiFi室內(nèi)定位方法[J]. 計(jì)算機(jī)應(yīng)用研究， 2014，31（6）：52-53.

[13] 趙銀龍，安勝彪. 基于核化K-means和SVM分類回歸的WiFi室內(nèi)定位算法[J]. 信息技術(shù)，2018（1）：26-27.

[14] 楊晉生，林振軍.? 一種改進(jìn)支持向量機(jī)的無線定位方法[J].? 應(yīng)用科學(xué)學(xué)報(bào)，2017， 35（6）：685-692.

[15] FARJOW W，CHEHRI A，MOUFTAH H，et al. Support vector machines for indoor sensor localization[C]. Wireless Communications & Networking Conference. IEEE， 2011.

[16] CORTES C，VAPNIK V. Support-vector networks[J]. Machine Learning，1995， 20（3）：273-297.

[17] 張會(huì)清，石曉偉，鄧貴華. 基于BP神經(jīng)網(wǎng)絡(luò)和泰勒級(jí)數(shù)的室內(nèi)定位算法研究[J]. 計(jì)算機(jī)科學(xué)， 2012， 39（4）：32-35.

[18] 孫斌，姚海濤. 基于 PSO 優(yōu)化 LSSVM 的短期風(fēng)速預(yù)測[J]. 電力系統(tǒng)保護(hù)與控制， 2012， 40（5）：85-89.

[19] 馬立新，王宏宇. 基于非支配解的多目標(biāo)粒子群無功優(yōu)化[J]. 控制工程，2014，21（5）：748-752.

[20] 申靜濤. 基于 RSSI 的對(duì)數(shù)距離路徑損耗模型研究[J]. 電子質(zhì)量，2013（12）：15-17.

[21] MEDEISIS A，KAJACKAS A. On the use of the universal Okumura-Hata propagation prediction model in rural areas[C]. IEEE Vehicular Technology Conference. IEEE Xplore， 2000.

（責(zé)任編輯：黃 ?。?/p>