螢火蟲算法優化支持向量機室內定位研究*

仲 臣，余學祥，邰曉曼，韓雨辰，肖星星，劉清華

(1.安徽理工大學空間信息與測繪工程學院,安徽 淮南 232001；2.安徽理工大學礦山采動災害空天地協同監測與預警安徽普通高校重點實驗室,安徽 淮南 232001；3.安徽理工大學礦區環境與災害協同監測煤炭行業工程研究中心,安徽 淮南 232001)

1 引言

隨著無線信息及智能終端的快速發展，基于位置服務的需求量日益增長。目前，室外定位技術已趨于成熟，其精度可達亞米級。相比之下，室內定位技術由于全球導航衛星系統GNSS(Global Navigation Satellite System)定位信號難以穿透墻體，同時受室內環境條件限制難以獲取高精度定位。

近年來，基于室內信號介質的WiFi技術、藍牙技術、射頻識別技術、超寬帶技術、紅外線定位技術和地磁定位技術等被廣泛研究。其中，WiFi定位技術能較好地滿足日常生活所需，但WiFi信號強度具有多變性，且信號接入點存在冗余信息，使基于WiFi的室內定位面臨挑戰。針對上述問題，一些學者利用數理統計理論，將機器學習算法與其結合，提升了定位精度。文獻[1]引入K鄰近KNN(K-Nearest Neighbor)算法,利用指紋存在的時序特征差異性對WiFi指紋信息進行基準坐標選擇，并修正其輸出結果附加權值，獲得了較為穩定的定位結果。文獻[2]提出了一種高斯徑向基核函數加權的KNN算法，并對無線信道狀態信息進行濾波處理，使定位精度進一步提升。文獻[3]利用卷積神經網絡模型結合WiFi指紋庫，提升了定位精度的同時縮短了定位所需時間。文獻[4]提出利用人工魚群算法對BP神經網絡進行優化，將神經網絡的初始權值與閾值作為種群的尋優目標，以此建立位置坐標與信號強度之間的對應關系，提升了定位可靠性。文獻[5]基于信號結構的多樣性建立無線電室內地圖，并將其2種不同頻率合成至指紋數據集中，進一步優化了定位精度。文獻[6]基于KNN算法，將空間距離參數進行優化，在低成本硬件設施的基礎上提高了WiFi的定位精度及穩定性。

由以上研究成果可知,KNN、神經網絡均可與WiFi定位融合達到實際應用要求的精度。但是，當室內定位范圍較大時，樣本數量較多，采用KNN算法空間復雜性高，易出現分布不均勻的情況，且對K值的選擇過于敏感，導致計算量增大[7]。同樣神經網絡對樣本點有嚴格的要求，易出現過擬合情況，從而限制其應用范圍。相比以上2種算法，支持向量機SVM(Support Vector Machine)具有一定的普適性，能很好地簡化空間復雜性，且存在更好的泛化推廣性。研究表明，核函數的選取對支持向量機的優劣有著決定性作用，在室內定位中，函數參數選擇不當會導致定位精度較低。

針對核函數參數的選取問題，本文提出一種基于螢火蟲算法FA(Firefly Algorithm)優化的支持向量機室內定位算法。螢火蟲算法的原理與實現均較為簡單，無需調整過多參數，能較好地改善SVM的回歸過程，從而進一步提升定位效果[8]。

2 算法原理

2.1 支持向量機

對于給定的某一樣本集{mi,ni},i=1,2…,N,mi∈Rd,ni∈{+1,-1}，利用超平面將樣本集中不同類別的樣本區分開，該超平面可表示為式(1)：

ωT·m+b=0

(1)

其中,ω=(ω1,ω2,ω3,…,ωd)為法向量，m為樣本向量，b為原點至超平面的位移。同時，若該超平面能將所有樣本正確分類，應滿足式(2)，最優分類超平面如圖1所示。圖1中，F1,F2,F3分別代表分類函數，分別位于F1和F3上的正樣本(+)和負樣本(-)即為支持向量。

(2)

Figure 1 Classification hyperplane圖1 分類超平面

分類完成后，最大化決策間隔可使分類效果達到最優，其間隔表達式如式(3)所示：

s.t.ni(ωTmi+b)≥1,i=1,2,…,N

(3)

式(3)即為SVM基本型，同時依據超平面的函數模型，結合凸二次規劃的優化解法，將拉格朗日乘子引入式(3)中并構造如式(4)所示的函數：

(4)

其中，拉格朗日乘子δi(i=1,2,…,N)為標量，可將約束條件函數與原函數聯系起來；N為樣本向量m的個數。決策函數如式(5)所示：

(5)

通常核函數的選取標準不唯一，根據實際問題來確定。二維高斯函數具有旋轉對稱性，且可分離性較好，因此本文選擇高斯徑向基核函數，則式(5)變換為式(6)：

(6)

其中,C為懲罰因子，σ為徑向基核函數的參數。

2.2 螢火蟲算法

螢火蟲算法的靈感源自螢火蟲群體的信息交換行為，螢火蟲之間通過光亮進行相互吸引。該算法原理較為簡單、性能穩定且全局和局部尋優能力強，能得到令人滿意的優化精度，被廣泛應用于各種優化問題，在WiFi指紋定位中能更好地建立信號與平面坐標之間的非線性關系。

為方便起見，假設螢火蟲之間的吸引度與其亮度成正比。為了降低算法的復雜度，設第v只螢火蟲所處的位置向量為xv=(xv1,xv2,xv3,…,xvn)，n為位置向量維度，位置向量的目標函數值與其絕對亮度Iv相等，即Iv=f(xv)；再設存在另外一只螢火蟲j的亮度值更大，即Ij>Iv，Ij=f(xj)；此時，該螢火蟲存在吸引力使亮度較小的螢火蟲聚集。若上述2只螢火蟲的距離為dvj，相對亮度為Ivj(dvj),考慮到距離變化及空氣吸收對光亮的影響，可得式(7)：

(7)

(8)

其中，ρ為空氣對光的吸收系數，一般取[0.01,100]的任意常數。

設螢火蟲v、j之間的吸引力與相對亮度Ivj(dvj)成一一映射關系，可定義吸引力αvj(dvj)如式(9)所示：

(9)

其中，α0為光源處對螢火蟲的吸引力，即最大吸引力，取值為1，同時吸引過程中亮度較小的螢火蟲v會隨時刻變化不斷更新自身位置，如式(10)所示：

xv(t+1)=xj(t)+αvj(dvj)(xv(t))+βλj

(10)

其中，xv和xj分別為2只螢火蟲所處的位置向量，t為迭代次數，β為[0,1]的常數，λj為隨機向量。

2.3 螢火蟲算法優化的支持向量機算法

本文針對SVM模型中的2個主要參數C和σ，引入螢火蟲算法對其進行優化，提出FA-SVM算法并應用于WiFi室內定位，其步驟如下所示：

(1)采集實驗所需數據，并將其劃分為學習與測試2種不同的類別。

(2)設定SVM模型中的2個主要參數C和σ的取值范圍,以此確定螢火蟲種群大小，并初始化種群個體的位置與亮度。

(3)進入循環。通過計算獲得螢火蟲個體間的吸引力αvj(dvj)與其相對亮度Ivj(dvj)，并更新螢火蟲種群的個體位置和適應度值。

(4)根據SVM參數優化的數學模型及最優定位精度更新螢火蟲個體的適應度值。

(5)判定是否滿足終止條件。若不滿足，返回步驟(3)，若尋得最優參數解，則輸出結果。

(6)將該參數結果應用于室內定位中，并進行數據預測。

FA-SVM算法流程圖如圖2所示。

Figure 2 Flow chart of FA-SVM algorithm圖2 FA-SVM算法流程圖

3 基于FA-SVM的室內定位

在室內定位離線階段，對于從定位區域采集的信號強度值RSSI(Received Signal Strength Indication)，通過奇異譜分析進行預處理，去除信號噪聲，以提高數據質量，保證定位精度及結果的穩定性[9]。將預處理后的數據分為訓練樣本和測試樣本，計算適應度值次數作為迭代次數，達到最大迭代次數即滿足終止條件，通過螢火蟲算法尋求最優參數(C,σ)，訓練數據并建立對應的室內定位回歸模型，對測試樣本進行預測，分析定位誤差，判斷模型的可靠性及穩定性。定位研究在線階段以用戶采集的實時RSSI數據作為輸入，通過離線階段建立的室內定位回歸模型輸出預測的位置坐標[10]。

3.1 奇異譜分析

由于室內定位存在不確定因素，采集的數據易受到干擾，RSSI值存在信號波動，為了獲得相對穩定的數據，本文采用奇異譜濾波算法對數據進行預處理。奇異譜分析主要包括4個步驟：嵌入、分解、分組和重構。

輸入序列長度為M的數據集X={x1,x2,x3,…,xM}，選擇合適的窗口長度L(通常取L<2/M)，確定K=M-L+1(即K>L)，將輸入的原始序列映射為L×K的軌跡矩陣，則嵌入的軌跡矩陣X如式(11)所示：

(11)

(12)

接著進行分組，對矩陣的奇異值進行降序排序，一般取前幾個較大的奇異值反映數據的特征，其余部分作為噪聲去除。

最后采用對角平均化的方式，將軌跡奇異分解的矩陣轉化為長度為M的序列，將L行K列的矩陣P作為分組后的矩陣，p為矩陣P中的元素。則重構序列rk如式(13)所示：

(13)

通過式(13)獲得去噪后的數據，信號強度濾波后如圖3所示，結果表明奇異譜濾波去除了噪聲，提高了數據的準確度。

Figure 3 Signal strength filtering圖3 信號強度濾波

為驗證信號濾波后可以提高定位精度，本文選取濾波處理后的數據和未經濾波處理后的數據進行待測點預測，誤差對比如圖4所示，具體數值如表1所示。對比室內定位精度發現，3 m以下定位誤差占比明顯增多，濾波處理后的數據較未濾波處理的數據平均定位誤差提高了18%。實驗說明濾波處理后的數據具有更高的準確度且保留了原始信號的特征。

Figure 4 Comparison of positioning accuracy before and after filtering圖4 濾波前后定位精度對比

3.2 基于FA-SVM分類和回歸的室內定位

假設選取長為l、寬為w的教室作為實驗區域并將其劃分為1 m×1 m組成的格網進行數據采集。

Table 1 Comparison of filtering performance

筆記本電腦作為信號接收器，在每個網格節點處進行數據采集，實測數據為h個接入點AP(Access Point)的RSSI組成的向量。

室內定位離線階段對實測數據進行奇異譜濾波預處理，將實測數據中的80%作為訓練數據，其余20%作為測試數據，以(RSSI1,RSSI2,RSSI3,RSSI4,x,y)數據格式輸入SVM模型中，設置SVM參數區間為C(0,100],σ(0,1000]，FA-SVM算法中適應度函數f(x)的計算公式如式(14)所示：

(14)

其中,Q為數據庫樣本點數；x′q和y′q分別為第q(q∈[1,Q])個樣本預測定位點坐標；xq和yq分別為第q個樣本實際坐標。

經過100次迭代尋優，求得最佳參數(C,σ)，用于SVM室內定位模型預測未知點。在線階段利用實時RSSI值計算位置坐標。

4 應用實例

4.1 實驗環境

本文選取安徽理工大學空間信息與測繪工程學院一樓作為實驗區域，實驗區域長20 m，寬30 m，涵蓋球場、廁所、走廊及實驗室，具體情況如圖5所示；選取4個相同的小米路由器作為接入點，布置在房間拐角處，信號覆蓋整個實驗區域。除墻體外，將實驗區域劃分為2 m*2 m的網格，于網格節點處采集RSSI值，共有145個節點，每個節點處采集50次。通過奇異譜濾波預處理RSSI數值，將處理后的數據的80%用于訓練，其余20%用于測試，把訓練集輸入支持向量機中，利用螢火蟲算法尋找最優懲罰參數C和屬性系數σ，建立室內定位回歸模型，并且采用5折交叉驗證，確保模型的精度。

Figure 5 Experimental area圖5 實驗區域

4.2 結果與分析

本文選取螢火蟲算法和粒子群優化PSO(Particle Swarm Optimization)算法對SVM參數優化進行對比，并選用KNN算法和加權K-最近鄰WKNN(Weighted K-Nearest Neighbor)算法對比驗證FA-SVM算法用于大范圍室內定位具有更明顯的定位優勢，證明螢火蟲算法尋優的SVM回歸模型提高了定位精度和穩定性，可將定位誤差控制在實際應用的范圍內。

4.2.1 SVM參數尋優

FA-SVM和PSO-SVM參數尋優曲線如圖6所示，具體數值如表2所示。相對于PSO-SVM算法，本文提出的FA-SVM算法收斂速度更快、尋優效率更高，可在較短時間內尋找到最優參數向量。

Figure 6 Optimization convergence curves圖6 尋優收斂曲線

Table 2 SVM parameters

4.2.2 定位精度

前文數據預處理部分的實驗表明了濾波前后定位誤差存在差異，為控制單一變量，以下實驗均使用奇異譜濾波處理后的數據進行待測點預測。FA-SVM、PSO-SVM、WKNN和KNN 4種定位算法的定位結果如圖7所示，定位結果統計如圖8所示，定位累計誤差分布如圖9所示。

Figure 7 Comparison of positioning results圖7 定位結果對比

Figure 8 Positioning result statistics圖8 定位結果統計

Figure 9 Distribution of cumulative positioning errors圖9 定位累計誤差分布圖

分析圖表可得，FA-SVM算法定位誤差在5 m以內，且2 m以內誤差占比過半;而PSO-SVM算法定位誤差仍集中在3 m左右，部分誤差在6 m以上。說明螢火蟲算法優化的SVM參數優于粒子群優化算法，不易受到數據噪聲的影響，魯棒性好，能更好地刻畫RSSI值與平面坐標xy的非線性關系。同時，觀察FA-SVM算法、WKNN和KNN算法發現，WKNN和KNN算法定位誤差波動大，存在10 m以上誤差，嚴重影響室內定位實用性和穩定性，表明本文算法魯棒性更好。

4種算法定位誤差對比如表3所示。比較表3的最大定位誤差、最小定位誤差和平均定位誤差可知，FA-SVM平均定位誤差較PSO-SVM算法降低了17.7%，最小定位誤差較PSO-SVM算法降低了23.8%，最大定位誤差較PSO-SVM算法降低了19.3%。說明螢火蟲算法尋找的最優參數存在更高的穩定性，可提高室內定位的定位精度。觀察WKNN和KNN算法可知，大部分點定位于8 m以下，且存在10 m以上誤差，定位過程中可能隨時偏移實際位置，影響室內定位效果。

Table 3 Performance comparison of four algorithms

選取部分實驗點進行室內定位坐標點對比，如圖10所示。FA-SVM算法待測點預測坐標更加貼合實際坐標，PSO-SVM算法待測點預測坐標幾乎偏離實際位置，對比可得，FA-SVM算法定位待測點具有更高的穩定性和更高的定位精度。

Figure 10 Comparison of positioning coordinates圖10 定位坐標對比圖

4.2.3 定位速度

FA-SVM和PSO-SVM的定位耗時如圖11所示。通過2種尋優算法建立的室內定位回歸模型進行定位，可發現隨著訓練集中樣本數量增加，未知點定位耗時不斷增加，但是，FA-SVM定位耗時一直低于PSO-SVM，總體趨勢幾乎沒有變化。說明FA-SVM算法簡單，定位速度更快，定位耗時不易受樣本數量大小的影響，在數據庫樣本數量較大時，提高了室內定位的時效性，滿足了室內實時定位的要求，應用前景更廣。

Figure 11 Comparison of positioning speed圖11 定位速度對比

5 結束語

針對KNN、神經網絡等機器學習在室內定位應用中存在的不足，本文提出了一種基于螢火蟲算法優化支持向量機的室內定位算法。室內定位離線階段，將奇異譜濾波后的數據輸入支持向量機中，并用螢火蟲算法尋求支持向量機最優參數，建立室內定位回歸模型。實驗結果表明，FA-SVM算法不僅收斂速度快、尋優效率高且不易受環境影響，提高了室內定位的精度及魯棒性，能較好地應用于實際生活中。