基于微粒群優化LSSVM的室內指紋定位算法

趙妍 樂燕芬 施偉斌

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

關鍵詞：指紋定位;微粒群算法;最小二乘支持向量機;RSSI

DOI：10. 11907/rjdk. 182266

中圖分類號：TP312文獻標識碼：A文章編號：1672-7800（2019）004-0087-04

0 引言

隨著無線通信技術、互聯網技術的不斷發展，具有自組網能力的無線傳感器網絡（WSN）已成為學者們關注的熱點[1-2]。傳感器節點定位是WSN領域的主要應用之一，然而傳感器節點大多布置在礦井下或地下停車場、商場等各種復雜室內環境中，室外基于GPS信號的定位方式易受到環境非視距、干擾多變、多徑等因素影響而難以實現。因此，如何獲取傳感器節點位置信息成為WSN室內定位應用中必須考慮的問題之一[3]。

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

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

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

1 基本理論

1.1 LSSVM原理

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

綜上可知，建立基于LSSVM的室內定位模型，通過確定[g]的值有利于參數優化。

1.2 微粒群算法

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

2 基于LSSVM的室內指紋定位算法

2.1 算法介紹

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

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

（2）在線匹配階段。當移動節點在待定位區域內移動時，將實時接收到的RSSI信息輸入到LSSVM模型，通過模型計算出移動節點位置。

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

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

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

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

（2）在線定位階段：將需要定位坐標接收的RSSI值輸入到LSSVM模型，即可輸出對應位置坐標。

算法具體實現過程如圖2所示。

3 仿真實驗及分析

為了驗證粒子群優化最小二乘支持向量機算法的可行性與正確性，首先對傳統LSSVM采用試湊法選取模型參數，運用PSO優化算法對LSSVM輸入信號進行全局最優選擇，并將本文方法與傳統LSSVM方法作對比。

3.1 仿真環境

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

本文使用的訓練樣本數據為900個，測試樣本數據為100個，每個樣本由9個來自不同錨節點的RSSI值構成。仿真實驗環境及參數設置如表1所示。

3.2 結果與分析

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

圖4是PSO-LSSVM預測模型與傳統LSSVM模型預測結果對比。從圖4可看出，相比于傳統LSSVM算法，PSO-LSSVM算法誤差更小，可將大多數目標位置估計結果控制在2.5m以內，且許多估計誤差在1.5m內。從定位誤差上可以看出，基于PSO優化的LSSVM算法比傳統LSSVM算法定位精度更高，說明采用PSO算法獲取LSSVM參數建立的定位模型，能更好地反映輸入與輸出之間的非線性關系。

PSO-LSSVM與傳統LSSVM兩種算法定位統計結果如圖5所示。由圖5可知，PSO-LSSVM算法在2m內的定位概率達到80%以上，而傳統LSSVM算法定位概率僅為60%。因此，PSO-LSSVM算法在定位精度方面優于傳統LSSVM算法。

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

4 結語

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

參考文獻：

[1] 馮亞超，賀康，楊紅麗，等. 一種無線傳感器網絡數據收集協議的研究與優化[J]. 傳感技術學報，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] 汪煬. 基于無線傳感器網絡定位技術研究[D]. 合肥：中國科技大學，2007.

[7] 朱曉娟，孟祥瑞. 基于加權質心的無線傳感器網絡動態節點定位算法[J]. 計算機工程與科學，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] 徐玉濱，鄧志安，馬琳. 基于核直接判別分析和支持向量機回歸的WLAN室內定位算法[J]. 電子與信息學報，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] 邱愛昆.? 基于機器學習的 WiFi 高精度定位研究[D]. 無錫：江南大學，2016.

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

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

[14] 楊晉生，林振軍.? 一種改進支持向量機的無線定位方法[J].? 應用科學學報，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] 張會清，石曉偉，鄧貴華. 基于BP神經網絡和泰勒級數的室內定位算法研究[J]. 計算機科學， 2012， 39（4）：32-35.

[18] 孫斌，姚海濤. 基于 PSO 優化 LSSVM 的短期風速預測[J]. 電力系統保護與控制， 2012， 40（5）：85-89.

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

[20] 申靜濤. 基于 RSSI 的對數距離路徑損耗模型研究[J]. 電子質量，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.

（責任編輯：黃 健）