韓雨辰，呂偉才*，仲 臣，肖星星 ，劉清華

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

0 引言

日常生活中，人們在戶外可以方便地利用各種隨身設(shè)備通過GNSS信號實(shí)時(shí)定位，其精度可達(dá)到亞米級。隨著無線終端設(shè)備的不斷發(fā)展與創(chuàng)新，對高精度的室內(nèi)定位服務(wù)需求愈加迫切。由于GNSS信號穿透墻體時(shí)其信號強(qiáng)度大幅衰減，無法再提供定位服務(wù)，室內(nèi)定位往往需要室內(nèi)無線信號介質(zhì)完成[1]。如今基于WiFi、藍(lán)牙、超寬帶、射頻識別、可見光和FM的室內(nèi)定位技術(shù)被廣泛研究，取得了較為滿意的定位結(jié)果[2-7]。但這些技術(shù)需要一定的室內(nèi)物理基礎(chǔ)設(shè)施來完成，造價(jià)昂貴且需要不斷維護(hù)更新。因此，地磁室內(nèi)定位技術(shù)逐漸成為研究熱點(diǎn)。

地磁場具有空間差異性，在某個(gè)區(qū)域內(nèi)任意一處的地磁矢量值都不相同，這為地磁室內(nèi)定位提供了基礎(chǔ)；其次地磁定位具有全天候連續(xù)性、抗環(huán)境干擾能力強(qiáng)等特點(diǎn)。但地磁場的分辨率較低，在定位時(shí)易出現(xiàn)“回跳”現(xiàn)象[8]。因此，高精度地磁定位的關(guān)鍵在于匹配算法。針對這個(gè)問題，學(xué)者們進(jìn)行了深入研究。文獻(xiàn)[9]提出了一種基于布谷鳥非線性優(yōu)化的在線磁校準(zhǔn)算法，通過磁觀測余差動態(tài)對非線性目標(biāo)代價(jià)函數(shù)進(jìn)行加權(quán)，有效解決了磁傳感器中常存在的軟磁誤差和硬磁誤差；文獻(xiàn)[10]提出了改進(jìn)動態(tài)時(shí)間規(guī)整(Dynamic Time Warping，DTW)的地磁匹配算法，對地磁數(shù)據(jù)序列與采集數(shù)據(jù)序列的距離與相似路徑重新規(guī)整，并縮短地磁序列長度，在保證定位精度的同時(shí)提升了定位時(shí)效性；文獻(xiàn)[11]中將RSSI信號與地磁分量進(jìn)行融合，并將其矢量化，進(jìn)行更深層次的提取，彌補(bǔ)了地磁信號存在的低分辨率缺陷。文獻(xiàn)[12]受hausdorff距離測量點(diǎn)設(shè)置匹配理論啟發(fā)，提出了基于初始定位誤差約束的改進(jìn)粒子濾波算法，避免迭代過程中粒子存在的不利影響，提升了定位的穩(wěn)定性。

亦有學(xué)者通過融合機(jī)器學(xué)習(xí)算法對地磁室內(nèi)定位進(jìn)行研究，并取得了一定成果[13-15]。其中K最近鄰算法存在誤匹配的缺陷，且隨著指紋數(shù)量的增加缺陷愈加明顯，幾乎無法應(yīng)用大型場景的地磁定位。神經(jīng)網(wǎng)絡(luò)易因樣本點(diǎn)數(shù)量不足而出現(xiàn)過擬合的現(xiàn)象，且對樣本的采集要求較高。相比之下支持向量機(jī)(Support Vector Machine，SVM)存在更好的普適性，對空間復(fù)雜性的簡化效果更好，在室內(nèi)定位中的表現(xiàn)優(yōu)于另外2種算法[16]。SVM的性能受其懲罰因子及核函數(shù)選取的影響較大，若核函數(shù)選取不當(dāng)，定位精度會大幅下降。

為減少上述不利影響，提高定位精度，本文提出一種基于多種群遺傳算法(Multi-Population Genetic Algorithm，MPGA)優(yōu)化SVM的地磁室內(nèi)定位算法。該算法選擇高斯徑向基核函數(shù)作為SVM的核函數(shù)，提高了定位匹配過程中的穩(wěn)定性及準(zhǔn)確性，并通過實(shí)驗(yàn)測試該算法的定位效果。

1 原理與方法

針對上述提出的KNN算法、神經(jīng)網(wǎng)絡(luò)在室內(nèi)定位中存在的不足，將SVM模型應(yīng)用到地磁匹配算法中，并針對核函數(shù)及相關(guān)參數(shù)的選取問題，提出基于粒子群優(yōu)化SVM的算法進(jìn)行地磁匹配。

1.1 SVM原理

SVM屬于一種二分類模型，可將樣本數(shù)據(jù)集映射為空間內(nèi)存在的大量“點(diǎn)”，再利用某條“線”將這些點(diǎn)存在的不同類別最大程度區(qū)分開。對于給定的空間樣本點(diǎn){mi,ni},i=1,2,…,N,mi∈Rd,ni∈{+1,-1}，這條“線”即為劃分超平面，可表示為：

ωT·m+b=0，

(1)

式中，ω=(ω1,ω2,ω3,…,ωd)作為超平面的方向；b為劃分超平面至空間原點(diǎn)的位移量。

若樣本集中所有樣本點(diǎn)均被該超平面正確分類，則存在：

(2)

SVM的分類模型如圖1所示。

圖1 分類模型Fig.1 Classification model

圖1中，h1,h2,h3均為分類函數(shù)，落在函數(shù)h1,h3上的樣本“×”“○”即為支持向量；其分類間隔為：

(3)

此時(shí)需滿足受約束的參數(shù)ω，b，同時(shí)找到最大分類間隔，以便完成最佳分類。即：

(4)

式(4)即為SVM基本型，同時(shí)依據(jù)劃分超平面的函數(shù)模型，結(jié)合凸二次規(guī)劃的優(yōu)化解法構(gòu)造函數(shù)求解[17]，則該函數(shù)為：

(5)

式中，μi(i=1,2,…,N)為拉格朗日乘子，則SVM的決策函數(shù)為：

(6)

式中，h(mi,mj)為核函數(shù)，通?？蛇x擇的核函數(shù)如表1所示。

表1 SVM核函數(shù)Tab.1 SVM kernel functions

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

(7)

式中，C為懲罰因子；η為核函數(shù)的參數(shù)。

1.2 SGA算法

標(biāo)準(zhǔn)遺傳算法(Standard Genetic Algorithm，SGA)受達(dá)爾文進(jìn)化論以及孟德爾遺傳學(xué)說的啟發(fā)，模擬生物在大自然中的繁衍進(jìn)化機(jī)制，對特定目標(biāo)進(jìn)行迭代式概率尋優(yōu)。其算法流程如下：

① 設(shè)定參數(shù)范圍，均勻生成一個(gè)初始種群并確定該種群的大小。

② 確定適應(yīng)度函數(shù)，將該函數(shù)作為衡量種群中個(gè)體是否優(yōu)秀的標(biāo)準(zhǔn)。本文選取定位精度G(x)為適應(yīng)度函數(shù)：

(8)

式中，N為數(shù)據(jù)庫樣本點(diǎn)數(shù)；x′i，y′i分別為第i(i∈[1,N])個(gè)樣本預(yù)測定位點(diǎn)坐標(biāo)；xi，yi分別為其實(shí)際坐標(biāo)。

③ 選擇遺傳算子，該算法中適應(yīng)度越大的個(gè)體被選擇遺傳到下一代的概率越大。假設(shè)初始種群個(gè)體數(shù)量為K，個(gè)體i的適應(yīng)度為hi，則該遺傳算子被選擇的概率為：

(9)

④ 交叉和變異，新個(gè)體通常由交叉、變異產(chǎn)生；若其參數(shù)選取不當(dāng)，遺傳算法的全局搜索能力會大幅下降。參數(shù)公式為：

(10)

式中，pa，pb分別為交叉概率、變異概率；d為0～1之間的任意常數(shù)。

⑤ 設(shè)定迭代結(jié)束準(zhǔn)則，達(dá)到所設(shè)定的迭代次數(shù)時(shí)，算法終止，輸出結(jié)果。

1.3 MPGA算法

上述SGA算法具有較好的收斂性與隨機(jī)性。但收斂速度較慢，且樣本數(shù)量大時(shí)穩(wěn)定性較差[18]。因此本文基于SGA的基礎(chǔ)提出了MPGA，該算法的改進(jìn)之處是將單個(gè)初始種群展開為含有不同交叉、變異參數(shù)的多個(gè)種群，每個(gè)種群同時(shí)進(jìn)化；并在種群之間建立移民機(jī)制,即每次迭代后將單個(gè)種群中適應(yīng)度最小的個(gè)體剔除，換取其他種群中適應(yīng)度最大的個(gè)體；將所有種群中每代適應(yīng)度最大的個(gè)體聚合建立精華種群，該種群不存在選擇、交叉和變異。并將該精華種群不斷地延續(xù)獲取更多的優(yōu)秀個(gè)體，以此達(dá)到最佳尋優(yōu)。其算法流程圖如圖2所示。

圖2 MPGA算法流程Fig.2 Flowchart of MPGA algorithm

1.4 MPGA-SVM模型建立

將上文所述SVM模型中的兩參數(shù)C，η作為MPGA所尋最優(yōu)解，建立MPGA-SVM模型，其算法流程如下：

① 采集實(shí)驗(yàn)所需的地磁樣本集，并將其劃分為SVM學(xué)習(xí)與測試2種不同類別。

② 確定粒子群的大小，設(shè)置參數(shù)C，η的取值范圍，并將每個(gè)粒子群初始化。粒子群再展開為M個(gè)粒子群，將所有粒子群以及每個(gè)種群中的所有粒子進(jìn)行編碼，一般選擇二進(jìn)制編碼，并利用式(10)確定交叉、變異概率。

③ 解碼并確定適應(yīng)度函數(shù)。本文選取式(8)作為適應(yīng)度函數(shù)。

④ 將M個(gè)粒子群進(jìn)行選擇、交叉和變異生成新的M個(gè)粒子群，并確定其中每個(gè)粒子的自適應(yīng)度。

⑤ 進(jìn)行移民機(jī)制，即每次迭代后將單個(gè)種群中適應(yīng)度最小的個(gè)體剔除，換取其他種群中適應(yīng)度最大的個(gè)體。將所有種群中每代適應(yīng)度最大的個(gè)體聚合建立精華種群。

⑥ 算法迭代，重復(fù)步驟③～步驟⑤，當(dāng)?shù)?00次或者達(dá)到最優(yōu)迭代次數(shù)時(shí)，算法終止，輸出結(jié)果。

⑦ 利用該輸出結(jié)果對應(yīng)的SVM參數(shù)C，η構(gòu)建地磁室內(nèi)定位模型。其算法流程圖如圖3所示。

圖3 MPGA-SVM算法流程Fig.3 Flowchart of MPGA-SVM algorithm

2 基于MPGA-SVM的地磁室內(nèi)定位

地磁定位通常有2種方式：單點(diǎn)定位或序列匹配，具體情況由特征值的選擇而定[19]。本文把X,Y,Z地磁三軸分量作為特征值，采用單點(diǎn)定位方式。

2.1 定位模型

在定位區(qū)域內(nèi)隨機(jī)采集多個(gè)樣本點(diǎn)的磁場強(qiáng)度，并將第i個(gè)樣本點(diǎn)的位置信息(xi,yi)記錄，數(shù)據(jù)格式為(xi,yi,Mi1,Mi2,Mi3)，設(shè)該點(diǎn)與周圍3個(gè)樣本點(diǎn)的相對磁場強(qiáng)度為(Mi1,Mi2,Mi3)。將這些點(diǎn)作為參考點(diǎn)，利用三角函數(shù)模型建立坐標(biāo)值與磁場強(qiáng)度之間的映射關(guān)系；由于室內(nèi)環(huán)境存在不利影響，輸入的磁場強(qiáng)度與輸出坐標(biāo)值具有隨機(jī)且復(fù)雜的非線性關(guān)系，可利用統(tǒng)計(jì)學(xué)的思想融合SVM，構(gòu)建地磁室內(nèi)定位回歸模型，如圖4所示。

圖4 地磁定位回歸模型圖Fig.4 Model diagram of geomagnetic positioning regression

2.2 定位原理

單點(diǎn)定位過程分為離線階段和在線階段[20]。離線階段在定位區(qū)域獲取各個(gè)位置的地磁特征值，與采集點(diǎn)坐標(biāo)相對應(yīng)，經(jīng)高斯濾波去噪后建立地磁指紋庫；在線階段將實(shí)時(shí)采集的地磁特征值與地磁指紋庫匹配，利用上文建立的定位模型及匹配算法輸出用戶的實(shí)時(shí)位置，其定位框架如圖5所示。

圖5 地磁定位框架圖Fig.5 Frame diagram of geomagnetic positioning

2.3 數(shù)據(jù)預(yù)處理

由于室內(nèi)環(huán)境多變，采集地磁指紋過程中存在著不可避免的誤差，使樣本數(shù)據(jù)波動較大。本文采用高斯濾波去除樣本集中小概率的噪聲干擾，進(jìn)一步提升定位可靠性。每次數(shù)據(jù)采集均可視為獨(dú)立且地磁分量服從正態(tài)分布，選取概率更高的地磁分量值利用幾何平均法求值，并將其作為濾波輸出。

設(shè)存在正態(tài)分布模型P(h)，對于第n號點(diǎn)的地磁分量值Mn的測量結(jié)果x的均值為：

(11)

方差以及概率密度函數(shù)為：

(12)

(13)

式中，x應(yīng)滿足μ-σ≤x≤μ+σ，將其對應(yīng)的地磁分量值加權(quán)平均即為最終輸出結(jié)果：

(14)

地磁分量濾波結(jié)果如圖6所示，結(jié)果表明高斯濾波能較好地剔除樣本集中的噪聲，保證了數(shù)據(jù)的準(zhǔn)確性。

圖6 高斯濾波Fig.6 Gaussian filtering

3 應(yīng)用實(shí)例

3.1 實(shí)驗(yàn)場景

本文選擇安徽理工大學(xué)空間信息與測繪工程學(xué)院一樓作為實(shí)驗(yàn)場所，場地大小為20 m×42 m，如圖7所示。將整個(gè)試驗(yàn)場地均勻劃分為1 m×1 m的網(wǎng)格，在每個(gè)網(wǎng)格節(jié)點(diǎn)進(jìn)行地磁指紋采集，采集設(shè)備為VIVO S9，采集頻率設(shè)置為50 Hz，采集過程中設(shè)備的姿態(tài)保持不變。數(shù)據(jù)采集完成后利用高斯濾波預(yù)處理，并對實(shí)驗(yàn)結(jié)果進(jìn)一步對比分析。

圖7 實(shí)驗(yàn)場景Fig.7 Experimental scenario

3.2 結(jié)果分析

為體現(xiàn)MPGA-SVM算法的性能，本文選用粒子群(Particle Swarm Optimization，PSO)優(yōu)化SVM算法與其做對比并進(jìn)行結(jié)果分析。粒子群算法是模擬鳥類群體之間信息的相互共享交換衍生的算法，具有較好的尋優(yōu)性。實(shí)驗(yàn)整體分為靜態(tài)定位實(shí)驗(yàn)以及動態(tài)定位實(shí)驗(yàn)兩部分。

3.2.1 靜態(tài)定位

將預(yù)處理后整體數(shù)據(jù)集的20%作為測試集，剩余數(shù)據(jù)作為訓(xùn)練集。采用五折交叉驗(yàn)證法將樣本輸入至已建立的MPGA-SVM地磁室內(nèi)定位模型中，MPGA-SVM與PSO-SVM的定位結(jié)果如圖8所示,累計(jì)誤差分布圖如圖9所示。

圖8 定位結(jié)果統(tǒng)計(jì)Fig.8 Statistics of positioning results

圖9 累計(jì)誤差分布圖Fig.9 Cumulative error distribution

分析圖8和圖9可得，MPGA-SVM定位誤差集中在2 m以內(nèi)，最大定位誤差不超過6 m；PSO-SVM有一半以上的定位誤差在2 m以上，最大定位誤差超過7 m，且1 m以內(nèi)的精確定位誤差占比仍小于MPGA-SVM算法。由分析結(jié)果可知，MPGA優(yōu)化的SVM在地磁室內(nèi)定位方面具有更好的性能。PSO-SVM與MPGA-SVM的動態(tài)定位精度對比如表2所示。

表2 靜態(tài)定位精度對比Tab.2 Comparison of static positioning accuracy 單位：m

由表2可知，MPGA-SVM算法的最小定位誤差、最大定位誤差、平均定位誤差均小于PSO-SVM；MPGA-SVM平均定位誤差為1.39 m，較之PSO-SVM定位精度提升1.1 m；MPGA-SVM定位標(biāo)準(zhǔn)差明顯小于PSO-SVM的定位標(biāo)準(zhǔn)差，具有更好的定位穩(wěn)定性。

3.2.2 動態(tài)定位

首先確定行人的初始位置坐標(biāo)，按照規(guī)劃的路線行走并進(jìn)行地磁數(shù)據(jù)采集，采集設(shè)備、頻率設(shè)置均不變，采集過程中保持設(shè)備的姿態(tài)保持不變。將預(yù)處理后的數(shù)據(jù)作為測試集，離線階段采集的全部地磁數(shù)據(jù)作為訓(xùn)練集，將訓(xùn)練樣本輸入至已建立的MPGA-SVM地磁室內(nèi)定位模型中，其定位結(jié)果如圖10所示，動態(tài)定位精度對比如表3所示。

由圖10可以直觀地看出，使用SVM模型應(yīng)用到地磁室內(nèi)定位是可行的，同時(shí)MPGA-SVM算法與PSO-SVM算法相比具有更好的定位真實(shí)性。由表2和表3可知，2組實(shí)驗(yàn)中MPGA-SVM算法的各項(xiàng)定位指標(biāo)均優(yōu)于PSO-SVM。由整體定位結(jié)果可得，MPGA-SVM算法在定位精度、定位穩(wěn)定性方面均優(yōu)于PSO-SVM算法。

圖10 定位軌跡圖Fig.10 Positioning trajectory diagram

表3 動態(tài)定位精度對比Tab.3 Comparison of dynamic positioning accuracy 單位：m

4 結(jié)束語

隨著室內(nèi)定位技術(shù)的不斷發(fā)展與應(yīng)用，基于地磁的室內(nèi)定位技術(shù)具有連續(xù)性強(qiáng)、抗環(huán)境干擾能力強(qiáng)等優(yōu)勢；且不需要額外的室內(nèi)物理設(shè)施支持，擁有較可觀的發(fā)展前景。本文針對地磁匹配中的傳統(tǒng)難點(diǎn)以及現(xiàn)有算法的缺陷，選擇高斯徑向基核函數(shù)作為SVM的核函數(shù)；利用MPGA的尋優(yōu)性與其融合提出基于MPGA-SVM的地磁室內(nèi)定位算法。試驗(yàn)結(jié)果表明，該算法具有更好的定位精度及穩(wěn)定性，可有效應(yīng)用于中小型場景室內(nèi)定位。由于地磁場分辨率低，在大型場景中，隨著指紋數(shù)量的增加，不同位置坐標(biāo)對應(yīng)的地磁特征值會存在更多相似的情況，導(dǎo)致單點(diǎn)定位誤匹配概率較大。因此，未來可引入其他室內(nèi)定位技術(shù)例如WiFi定位、藍(lán)牙定位和行人航跡推算等與其融合，增加不同坐標(biāo)對應(yīng)的特征量，彌補(bǔ)單一地磁定位技術(shù)缺陷的同時(shí)進(jìn)一步提升定位精度與穩(wěn)定性。