組合優化算法改進的室內位置感知方法

韓學法，吳 飛，朱 海，時瑤佳

（上海工程技術大學 電子電氣工程學院，上海 201620）

0 引言

隨著科學技術的不斷發展，基于位置的服務（location based service,LBS）的應用已經遍布生活中的各個方面，如車載導航系統、基于LBS的推薦系統以及其他應用系統，它們均采用了基于LBS的定位導航技術[1-2]。但是，這些應用在室外環境效果很好，在室內卻無法進行精確位置識別，所以室內位置感知技術非常具有研究價值。由于無線局域網覆蓋范圍較廣，無線保真（wireless fidelity,WiFi）定位技術能夠滿足人們對室內定位的需求，其最大的優勢是成本低、計算開銷小、定位精度較高[3-5]。因此，根據WiFi 信號進行室內移動目標位置識別的研究具有重要意義。

根據室內移動目標所處的環境信息進行室內場景準確識別，是基于位置服務的應用的技術關鍵。目前，基于位置感知的研究已成為學術界和工業界的研究熱點[6-8]。現有的研究主要利用全球定位系統（global positioning system,GPS）、藍牙、地磁、射頻識別（radio frequency identification,RFID）、超寬帶（ultra wide band,UWB）以及同步定位和制圖（simultaneous location and mapping,SLAM）等信號源進行位置感知。但是，GPS 信號在室內環境中存在弱缺現象而無法滿足人們室內定位的需求[9-11]；藍牙定位技術僅適用于小范圍的定位[12]；其他方法也存在各自的不足。文獻[13]采用GPS信號進行移動用戶的定位，但該方法適用范圍有限，無法滿足室內定位需求；文獻[14]提出一種通過監視人們的日常行為進行位置估計的方法，這種技術在火災等緊急情況中比較適用，但易受周邊環境的干擾；文獻[15] 提出了一種基于支持向量機（support vector machines,SVM）的位置識別算法，結合用戶不同行走姿勢進行位置感知，但是識別準確率低，定位均值誤差達3.53 m；文獻[16]提出一種基于神經網絡的多傳感器數據融合定位算法，能夠對行人行走情況進行預判分類，但準確性不高；文獻[17]利用機器學習方法，提出了一種適應多種環境的室內定位策略，但位置識別效果不是很好。

近來，對基于位置的服務的需求日益增加。尤其是在大型室內場所，這種移動目標的定位需求愈加強烈；研究室內移動目標的位置感知就顯得尤為重要。為了解決現有研究方法的室內位置識別準確率較低、穩定性較差的問題，本文提出一種優化的室內移動目標的位置感知方法，通過采集用戶在室內區域行走時智能手機接收到的周邊接入點（access point，AP）的WiFi 信號數據，根據接收信號強度指示（received signal strength indicator,RSSI）值來建立位置指紋數據庫，并將采集的數據作為樣本對本文方法進行測試。

1 相關方法原理

1.1 粒子群算法

粒子群算法（particle swarm optimization,PSO）是文獻[18]提出的一個典型的非線性的智能優化算法。PSO 受到覓食行為的啟發，以群體和適應度為出發點，尋求解空間的最優解。PSO 算法就是基于目標優化的數學模型，具體定義為：

1.2 引力搜索算法

引力搜索算法（gravitational search algorithm,GSA）是由文獻[19]提出的一種啟發式優化算法，該算法是以萬有引力定律和牛頓第二定律為基礎，通過種群的粒子位置移動來尋找最優解。假設N個粒子構成一個搜索空間，則第i個粒子的位置定義為

式中：N為搜索空間的維數；為第i個粒子在第d維空間的位置。

該算法首先將所有粒子隨機放置在一個搜索空間中，在t次迭代運算時，粒子i、j間的相互引力定義為

式中：Mpi和Maj分別為粒子i、j的慣性質量；ε為常數；G（t）為第t次迭代時的引力系數；Rij為粒子i、j的歐式距離。Gt和Rij的計算公式為：

式中：G（t0）為引力系數初始值；α為引力系數；k為當前迭代次數。第i個粒子在第d維空間的引力計算公式為

式中rj為分布于[0,1]的隨機數。第t次迭代時，粒子i的加速度與合力成正比，引力質量成反比，其計算公式為

式中：t為迭代次數；Mi（t）為粒子i的引力質量。每次迭代時，粒子i的速度和位置迭代更新的計算公式為：

式中ri為分布于[0,1]的隨機數。假設每次迭代時，粒子的引力質量與慣性質量相等，則第t次迭代時，粒子i的質量mi（t）迭代更新計算公式為

式中fi(t)為粒子i在t次迭代時的適應度值。對于最小值最優化問題，最優適應度值fbest(t)和最差適應度值fworst(t)的計算公式為

式中j表示粒子j。對于最大值最優化問題，最優適應度值fbest（t）和最差適應度值fworst（t）的計算公式為

在實際應用過程中，粒子i的質量需要進行歸一化，其計算公式為

2 改進的室內位置感知方法

2.1 改進的混合優化算法

由于PSO 算法的全局搜索能力強但速度較慢，而GSA 算法的局部搜索能力有限，它們各有所長，于是本文將二者結合起來，提出一種改進的組合優化算法，即PSOGSA 算法，以提高算法的適用性。

由式（9）和式（10）可知，GSA 算法僅保留迭代過程中當前位置信息，而無法在搜索過程中找到最優解，也就是說GSA 算法是一種缺失記憶能力的算法。本文結合PSO 算法全局搜索能力強的特點，對GSA 算法進行改進，增強其記憶搜索能力。整個搜索過程中，粒子運動方程為

式中：V（it）是粒子i在第t次迭代時的速度；為加速度系數；Xgbest為粒子i在迭代過程中位置的最優解。則權重系數的計算公式為

式中：ωmax和ωmin分別為ω的上下限；Tmax為迭代次數的上限。PSOGSA 算法實現過程如圖1 所示。

圖1 PSOGSA 算法實現過程

2.2 基于PSOGSA-NN的位置感知模型

神經網絡（neural network,NN）是一種易于理解且使用廣泛的模型，該模型可以使用反向傳播（back propagation,BP）算法進行預測分類[20]。對于室內定位來說，準確高效地識別出行人等移動目標的位置很關鍵。因此，本文將采集到的WiFi信號覆蓋區域的RSSI 值作為位置指紋特征，以移動用戶所在的位置區域作為分類標簽，構建樣本數據集，且樣本數據集定義為

式中：i、j分別為區域位置的數目和AP 個數；為在第i個區域采集到第j個AP的RSSI 值。基于神經網絡的室內位置感知模型主要包括輸入層、隱含層和輸出層，具體的模型結構如圖2 所示。

圖2 室內位置感知模型

式中：fi為粒子i當前的適應度值；fmin和fmax分別為粒子i最大和最小適應度值，其實就是將每個粒子的適應度值歸一化。θ的計算公式如下：

式中Vtc為第t次迭代時粒子當前的速度。

在室內定位中，通過sj和θ可以確定ω′，從而提高室內位置感知模型的識別率和準確率。基于PSOGSA-NN的位置感知模型如圖3 所示。

由圖3 可知，基于PSOGSA-NN 位置感知模型的核心是PSOGSA-NN 算法，該算法的具體實現過程如圖4 所示。

圖3 基于PSOGSA-NN的位置感知模型

圖4 PSOGSA-NN 算法實現過程

3 實驗與結果分析

3.1 實驗環境

為了驗證本文所提方法，選擇某實驗大樓中4個較為空曠的教室作為實驗區域進行定位實驗。實驗場地的平面示意圖如圖5 所示。

實驗人員手持裝有自主開發的信號采集軟件GetSensorData2.1的智能手機，行走在實驗區域內，采集實驗區域周邊AP的WiFi 信號。

3.2 數據采集與處理

實驗人員通過采集實驗區域周邊AP的RSSI值來構建位置指紋數據庫，從而得到實驗所需要的樣本數據集。實驗時，實驗人員右手手持P30 智能手機于胸前，行走在實驗區域進行WiFi 信號采集。采集過程中，頻率均為50 Hz，數據采集界面如圖6 所示。

實驗時，分別采集房間1～房間4的數據，每個房間采集500 次，每次取接收到AP 信號的RSSI均值作為位置指紋，實驗區域的RSSI 信號變化如圖7 所示，圖7（a）～圖7（d）分別為房間1～房間4的RSSI 信號變化情況。

圖7 不同房間的RSSI 信號變化

由圖7 可知，不同位置的RSSI 信號存在差異，即RSSI 信號存在空間差異性，故可通過位置指紋來進行區域識別。數據經過處理后，每個房間僅保留500 條位置指紋樣本，部分位置指紋樣本信息如表1 所示，前7 列為RSSI 值，單位為dB，最后一列為房間類別編號。

表1 不同房間的位置指紋樣本信息

3.3 結果分析

為了進一步驗證本文方法的可行性，將2 000 條樣本數據分為2 個部分，1 400 條作為訓練集，600 條作為測試集。在機器學習中，ROC（receiver operating characteristic）即接收器操作特征曲線是用來描繪學習器的泛化能力的有力工具；而AUC（area under ROC curve）即ROC 曲線下的面積，用來度量分類模型的好壞。本文實驗過程中，通過繪制不同類別的 ROC 曲線來進行模型評估，用AUC 作為模型評價指標。對于分類問題，也常用分類準確率作為評價指標。對于本文的位置感知識別準確率（racc）的定義為

式中：ntp為預測房間類別與真實房間類別一致的樣本數；nfp為預測房間類別與真實房間類相反的樣本數；nfn為將預測錯誤的房間分類結果作為正確結果的樣本數；ntn為將預測正確的房間分類結果當作錯誤結果的樣本數。在ROC 曲線中橫縱坐標分別為假正率（rfp）和真正率（rtp），它們的定義公式為：

為了進一步評價本文所提方法的性能，通過實驗得出如圖8 所示的效果。

圖8 本文方法的效果

由圖可知，本文方法在室內的識別準確率較好，房間1 為99.99%，房間2 為99.91%，房間3 為79.41%，房間4 為99.96%，且平均準確率為98.35%。為了對比分析本文提出模型的效果，將本文模型（PSOGSA_NN）與支持向量機（SVM）分類算法、納伊夫·貝葉斯（Na?ve Bayes）分類算法、神經網絡（NN）分類算法、粒子群-神經網絡（PSO_NN）算法及引力搜索-神經網絡（GSA_NN）算法進行對比，各類模型的識別準確率（所有類別的識別率的均值）如圖9 所示。

圖9 模型對比的效果

由圖可知，與同類方法對比，本文方法的位置感知識別準確率為 98.35%，比 SVM 算法高4.79%，比Na?ve Bayes 算法高7.88%，比NN 算法高25.98%，比PSO_NN 高15.07%，比GSA_NN高19.82%。因此，本文方法的室內位置感知識別效果最佳，與同類方法相比，識別準確率至少提高4.79%。

4 結束語

為了解決現有研究方法的室內位置識別準確率較低、穩定性較差的問題，本文提出一種基于組合優化算法改進的室內位置感知方法。通過采集用戶在室內區域行走時智能手機接收到的周邊AP的WiFi 信號數據，根據采集的RSSI 值來建立位置指紋數據庫，將采集的數據作為樣本對本文方法進行測試。實驗結果表明本文方法的室內位置感知識別準確率為98.35%，與同類方法相比，識別準確率至少提高4.79%。由于本文所進行的實驗是以位置區域類別作為位置標簽，AP的RSSI 值為位置特征，且位置標簽是已知的，所以具有應用局限性。下一步將研究如何在位置未知的情況下進行室內位置識別，從而提高模型的適用性。