基于MPGA-SVM的地磁室內定位算法研究

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

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

0 引言

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

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

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

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

1 原理與方法

針對上述提出的KNN算法、神經網絡在室內定位中存在的不足，將SVM模型應用到地磁匹配算法中，并針對核函數及相關參數的選取問題，提出基于粒子群優化SVM的算法進行地磁匹配。

1.1 SVM原理

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

ωT·m+b=0，

(1)

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

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

(2)

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

圖1 分類模型Fig.1 Classification model

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

(3)

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

(4)

式(4)即為SVM基本型，同時依據劃分超平面的函數模型，結合凸二次規劃的優化解法構造函數求解[17]，則該函數為：

(5)

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

(6)

式中，h(mi,mj)為核函數，通常可選擇的核函數如表1所示。

表1 SVM核函數Tab.1 SVM kernel functions

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

(7)

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

1.2 SGA算法

標準遺傳算法(Standard Genetic Algorithm，SGA)受達爾文進化論以及孟德爾遺傳學說的啟發，模擬生物在大自然中的繁衍進化機制，對特定目標進行迭代式概率尋優。其算法流程如下：

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

② 確定適應度函數，將該函數作為衡量種群中個體是否優秀的標準。本文選取定位精度G(x)為適應度函數：

(8)

式中，N為數據庫樣本點數；x′i，y′i分別為第i(i∈[1,N])個樣本預測定位點坐標；xi，yi分別為其實際坐標。

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

(9)

④ 交叉和變異，新個體通常由交叉、變異產生；若其參數選取不當，遺傳算法的全局搜索能力會大幅下降。參數公式為：

(10)

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

⑤ 設定迭代結束準則，達到所設定的迭代次數時，算法終止，輸出結果。

1.3 MPGA算法

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

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

1.4 MPGA-SVM模型建立

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

① 采集實驗所需的地磁樣本集，并將其劃分為SVM學習與測試2種不同類別。

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

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

④ 將M個粒子群進行選擇、交叉和變異生成新的M個粒子群，并確定其中每個粒子的自適應度。

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

⑥ 算法迭代，重復步驟③～步驟⑤，當迭代100次或者達到最優迭代次數時，算法終止，輸出結果。

⑦ 利用該輸出結果對應的SVM參數C，η構建地磁室內定位模型。其算法流程圖如圖3所示。

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

2 基于MPGA-SVM的地磁室內定位

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

2.1 定位模型

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

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

2.2 定位原理

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

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

2.3 數據預處理

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

設存在正態分布模型P(h)，對于第n號點的地磁分量值Mn的測量結果x的均值為：

(11)

方差以及概率密度函數為：

(12)

(13)

式中，x應滿足μ-σ≤x≤μ+σ，將其對應的地磁分量值加權平均即為最終輸出結果：

(14)

地磁分量濾波結果如圖6所示，結果表明高斯濾波能較好地剔除樣本集中的噪聲，保證了數據的準確性。

圖6 高斯濾波Fig.6 Gaussian filtering

3 應用實例

3.1 實驗場景

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

圖7 實驗場景Fig.7 Experimental scenario

3.2 結果分析

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

3.2.1 靜態定位

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

圖8 定位結果統計Fig.8 Statistics of positioning results

圖9 累計誤差分布圖Fig.9 Cumulative error distribution

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

表2 靜態定位精度對比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定位標準差明顯小于PSO-SVM的定位標準差，具有更好的定位穩定性。

3.2.2 動態定位

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

由圖10可以直觀地看出，使用SVM模型應用到地磁室內定位是可行的，同時MPGA-SVM算法與PSO-SVM算法相比具有更好的定位真實性。由表2和表3可知，2組實驗中MPGA-SVM算法的各項定位指標均優于PSO-SVM。由整體定位結果可得，MPGA-SVM算法在定位精度、定位穩定性方面均優于PSO-SVM算法。

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

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

4 結束語

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