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

(1.安徽理工大學(xué)空間信息與測繪工程學(xué)院,安徽 淮南 232001；2.安徽理工大學(xué)礦山采動災(zāi)害空天地協(xié)同監(jiān)測與預(yù)警安徽普通高校重點實驗室,安徽 淮南 232001；3.安徽理工大學(xué)礦區(qū)環(huán)境與災(zāi)害協(xié)同監(jiān)測煤炭行業(yè)工程研究中心,安徽 淮南 232001)

1 引言

隨著無線信息及智能終端的快速發(fā)展，基于位置服務(wù)的需求量日益增長。目前，室外定位技術(shù)已趨于成熟，其精度可達(dá)亞米級。相比之下，室內(nèi)定位技術(shù)由于全球?qū)Ш叫l(wèi)星系統(tǒng)GNSS(Global Navigation Satellite System)定位信號難以穿透墻體，同時受室內(nèi)環(huán)境條件限制難以獲取高精度定位。

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

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

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

2 算法原理

2.1 支持向量機

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

ωT·m+b=0

(1)

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

(2)

Figure 1 Classification hyperplane圖1 分類超平面

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

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

(3)

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

(4)

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

(5)

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

(6)

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

2.2 螢火蟲算法

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

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

(7)

(8)

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

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

(9)

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

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

(10)

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

2.3 螢火蟲算法優(yōu)化的支持向量機算法

本文針對SVM模型中的2個主要參數(shù)C和σ，引入螢火蟲算法對其進(jìn)行優(yōu)化，提出FA-SVM算法并應(yīng)用于WiFi室內(nèi)定位，其步驟如下所示：

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

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

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

(4)根據(jù)SVM參數(shù)優(yōu)化的數(shù)學(xué)模型及最優(yōu)定位精度更新螢火蟲個體的適應(yīng)度值。

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

(6)將該參數(shù)結(jié)果應(yīng)用于室內(nèi)定位中，并進(jìn)行數(shù)據(jù)預(yù)測。

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

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

3 基于FA-SVM的室內(nèi)定位

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

3.1 奇異譜分析

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

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

(11)

(12)

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

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

(13)

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

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

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

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

3.2 基于FA-SVM分類和回歸的室內(nèi)定位

假設(shè)選取長為l、寬為w的教室作為實驗區(qū)域并將其劃分為1 m×1 m組成的格網(wǎng)進(jìn)行數(shù)據(jù)采集。

Table 1 Comparison of filtering performance

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

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

(14)

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

經(jīng)過100次迭代尋優(yōu)，求得最佳參數(shù)(C,σ)，用于SVM室內(nèi)定位模型預(yù)測未知點。在線階段利用實時RSSI值計算位置坐標(biāo)。

4 應(yīng)用實例

4.1 實驗環(huán)境

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

Figure 5 Experimental area圖5 實驗區(qū)域

4.2 結(jié)果與分析

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

4.2.1 SVM參數(shù)尋優(yōu)

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

Figure 6 Optimization convergence curves圖6 尋優(yōu)收斂曲線

Table 2 SVM parameters

4.2.2 定位精度

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

Figure 7 Comparison of positioning results圖7 定位結(jié)果對比

Figure 8 Positioning result statistics圖8 定位結(jié)果統(tǒng)計

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

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

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

Table 3 Performance comparison of four algorithms

選取部分實驗點進(jìn)行室內(nèi)定位坐標(biāo)點對比，如圖10所示。FA-SVM算法待測點預(yù)測坐標(biāo)更加貼合實際坐標(biāo)，PSO-SVM算法待測點預(yù)測坐標(biāo)幾乎偏離實際位置，對比可得，F(xiàn)A-SVM算法定位待測點具有更高的穩(wěn)定性和更高的定位精度。

Figure 10 Comparison of positioning coordinates圖10 定位坐標(biāo)對比圖

4.2.3 定位速度

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

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

5 結(jié)束語

針對KNN、神經(jīng)網(wǎng)絡(luò)等機器學(xué)習(xí)在室內(nèi)定位應(yīng)用中存在的不足，本文提出了一種基于螢火蟲算法優(yōu)化支持向量機的室內(nèi)定位算法。室內(nèi)定位離線階段，將奇異譜濾波后的數(shù)據(jù)輸入支持向量機中，并用螢火蟲算法尋求支持向量機最優(yōu)參數(shù)，建立室內(nèi)定位回歸模型。實驗結(jié)果表明，F(xiàn)A-SVM算法不僅收斂速度快、尋優(yōu)效率高且不易受環(huán)境影響，提高了室內(nèi)定位的精度及魯棒性，能較好地應(yīng)用于實際生活中。