組合優(yōu)化算法改進(jìn)的室內(nèi)位置感知方法

韓學(xué)法，吳 飛，朱 海，時(shí)瑤佳

（上海工程技術(shù)大學(xué) 電子電氣工程學(xué)院，上海 201620）

0 引言

隨著科學(xué)技術(shù)的不斷發(fā)展，基于位置的服務(wù)（location based service,LBS）的應(yīng)用已經(jīng)遍布生活中的各個(gè)方面，如車(chē)載導(dǎo)航系統(tǒng)、基于LBS的推薦系統(tǒng)以及其他應(yīng)用系統(tǒng)，它們均采用了基于LBS的定位導(dǎo)航技術(shù)[1-2]。但是，這些應(yīng)用在室外環(huán)境效果很好，在室內(nèi)卻無(wú)法進(jìn)行精確位置識(shí)別，所以室內(nèi)位置感知技術(shù)非常具有研究?jī)r(jià)值。由于無(wú)線(xiàn)局域網(wǎng)覆蓋范圍較廣，無(wú)線(xiàn)保真（wireless fidelity,WiFi）定位技術(shù)能夠滿(mǎn)足人們對(duì)室內(nèi)定位的需求，其最大的優(yōu)勢(shì)是成本低、計(jì)算開(kāi)銷(xiāo)小、定位精度較高[3-5]。因此，根據(jù)WiFi 信號(hào)進(jìn)行室內(nèi)移動(dòng)目標(biāo)位置識(shí)別的研究具有重要意義。

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

近來(lái)，對(duì)基于位置的服務(wù)的需求日益增加。尤其是在大型室內(nèi)場(chǎng)所，這種移動(dòng)目標(biāo)的定位需求愈加強(qiáng)烈；研究室內(nèi)移動(dòng)目標(biāo)的位置感知就顯得尤為重要。為了解決現(xiàn)有研究方法的室內(nèi)位置識(shí)別準(zhǔn)確率較低、穩(wěn)定性較差的問(wèn)題，本文提出一種優(yōu)化的室內(nèi)移動(dòng)目標(biāo)的位置感知方法，通過(guò)采集用戶(hù)在室內(nèi)區(qū)域行走時(shí)智能手機(jī)接收到的周邊接入點(diǎn)（access point，AP）的WiFi 信號(hào)數(shù)據(jù)，根據(jù)接收信號(hào)強(qiáng)度指示（received signal strength indicator,RSSI）值來(lái)建立位置指紋數(shù)據(jù)庫(kù)，并將采集的數(shù)據(jù)作為樣本對(duì)本文方法進(jìn)行測(cè)試。

1 相關(guān)方法原理

1.1 粒子群算法

粒子群算法（particle swarm optimization,PSO）是文獻(xiàn)[18]提出的一個(gè)典型的非線(xiàn)性的智能優(yōu)化算法。PSO 受到覓食行為的啟發(fā)，以群體和適應(yīng)度為出發(fā)點(diǎn)，尋求解空間的最優(yōu)解。PSO 算法就是基于目標(biāo)優(yōu)化的數(shù)學(xué)模型，具體定義為：

1.2 引力搜索算法

引力搜索算法（gravitational search algorithm,GSA）是由文獻(xiàn)[19]提出的一種啟發(fā)式優(yōu)化算法，該算法是以萬(wàn)有引力定律和牛頓第二定律為基礎(chǔ)，通過(guò)種群的粒子位置移動(dòng)來(lái)尋找最優(yōu)解。假設(shè)N個(gè)粒子構(gòu)成一個(gè)搜索空間，則第i個(gè)粒子的位置定義為

式中：N為搜索空間的維數(shù)；為第i個(gè)粒子在第d維空間的位置。

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

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

式中：G（t0）為引力系數(shù)初始值；α為引力系數(shù)；k為當(dāng)前迭代次數(shù)。第i個(gè)粒子在第d維空間的引力計(jì)算公式為

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

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

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

式中fi(t)為粒子i在t次迭代時(shí)的適應(yīng)度值。對(duì)于最小值最優(yōu)化問(wèn)題，最優(yōu)適應(yīng)度值fbest(t)和最差適應(yīng)度值fworst(t)的計(jì)算公式為

式中j表示粒子j。對(duì)于最大值最優(yōu)化問(wèn)題，最優(yōu)適應(yīng)度值fbest（t）和最差適應(yīng)度值fworst（t）的計(jì)算公式為

在實(shí)際應(yīng)用過(guò)程中，粒子i的質(zhì)量需要進(jìn)行歸一化，其計(jì)算公式為

2 改進(jìn)的室內(nèi)位置感知方法

2.1 改進(jìn)的混合優(yōu)化算法

由于PSO 算法的全局搜索能力強(qiáng)但速度較慢，而GSA 算法的局部搜索能力有限，它們各有所長(zhǎng)，于是本文將二者結(jié)合起來(lái)，提出一種改進(jìn)的組合優(yōu)化算法，即PSOGSA 算法，以提高算法的適用性。

由式（9）和式（10）可知，GSA 算法僅保留迭代過(guò)程中當(dāng)前位置信息，而無(wú)法在搜索過(guò)程中找到最優(yōu)解，也就是說(shuō)GSA 算法是一種缺失記憶能力的算法。本文結(jié)合PSO 算法全局搜索能力強(qiáng)的特點(diǎn)，對(duì)GSA 算法進(jìn)行改進(jìn)，增強(qiáng)其記憶搜索能力。整個(gè)搜索過(guò)程中，粒子運(yùn)動(dòng)方程為

式中：V（it）是粒子i在第t次迭代時(shí)的速度；為加速度系數(shù)；Xgbest為粒子i在迭代過(guò)程中位置的最優(yōu)解。則權(quán)重系數(shù)的計(jì)算公式為

式中：ωmax和ωmin分別為ω的上下限；Tmax為迭代次數(shù)的上限。PSOGSA 算法實(shí)現(xiàn)過(guò)程如圖1 所示。

圖1 PSOGSA 算法實(shí)現(xiàn)過(guò)程

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

神經(jīng)網(wǎng)絡(luò)（neural network,NN）是一種易于理解且使用廣泛的模型，該模型可以使用反向傳播（back propagation,BP）算法進(jìn)行預(yù)測(cè)分類(lèi)[20]。對(duì)于室內(nèi)定位來(lái)說(shuō)，準(zhǔn)確高效地識(shí)別出行人等移動(dòng)目標(biāo)的位置很關(guān)鍵。因此，本文將采集到的WiFi信號(hào)覆蓋區(qū)域的RSSI 值作為位置指紋特征，以移動(dòng)用戶(hù)所在的位置區(qū)域作為分類(lèi)標(biāo)簽，構(gòu)建樣本數(shù)據(jù)集，且樣本數(shù)據(jù)集定義為

式中：i、j分別為區(qū)域位置的數(shù)目和AP 個(gè)數(shù)；為在第i個(gè)區(qū)域采集到第j個(gè)AP的RSSI 值。基于神經(jīng)網(wǎng)絡(luò)的室內(nèi)位置感知模型主要包括輸入層、隱含層和輸出層，具體的模型結(jié)構(gòu)如圖2 所示。

圖2 室內(nèi)位置感知模型

式中：fi為粒子i當(dāng)前的適應(yīng)度值；fmin和fmax分別為粒子i最大和最小適應(yīng)度值，其實(shí)就是將每個(gè)粒子的適應(yīng)度值歸一化。θ的計(jì)算公式如下：

式中Vtc為第t次迭代時(shí)粒子當(dāng)前的速度。

在室內(nèi)定位中，通過(guò)sj和θ可以確定ω′，從而提高室內(nèi)位置感知模型的識(shí)別率和準(zhǔn)確率?；赑SOGSA-NN的位置感知模型如圖3 所示。

由圖3 可知，基于PSOGSA-NN 位置感知模型的核心是PSOGSA-NN 算法，該算法的具體實(shí)現(xiàn)過(guò)程如圖4 所示。

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

圖4 PSOGSA-NN 算法實(shí)現(xiàn)過(guò)程

3 實(shí)驗(yàn)與結(jié)果分析

3.1 實(shí)驗(yàn)環(huán)境

為了驗(yàn)證本文所提方法，選擇某實(shí)驗(yàn)大樓中4個(gè)較為空曠的教室作為實(shí)驗(yàn)區(qū)域進(jìn)行定位實(shí)驗(yàn)。實(shí)驗(yàn)場(chǎng)地的平面示意圖如圖5 所示。

實(shí)驗(yàn)人員手持裝有自主開(kāi)發(fā)的信號(hào)采集軟件GetSensorData2.1的智能手機(jī)，行走在實(shí)驗(yàn)區(qū)域內(nèi)，采集實(shí)驗(yàn)區(qū)域周邊AP的WiFi 信號(hào)。

3.2 數(shù)據(jù)采集與處理

實(shí)驗(yàn)人員通過(guò)采集實(shí)驗(yàn)區(qū)域周邊AP的RSSI值來(lái)構(gòu)建位置指紋數(shù)據(jù)庫(kù)，從而得到實(shí)驗(yàn)所需要的樣本數(shù)據(jù)集。實(shí)驗(yàn)時(shí)，實(shí)驗(yàn)人員右手手持P30 智能手機(jī)于胸前，行走在實(shí)驗(yàn)區(qū)域進(jìn)行WiFi 信號(hào)采集。采集過(guò)程中，頻率均為50 Hz，數(shù)據(jù)采集界面如圖6 所示。

實(shí)驗(yàn)時(shí)，分別采集房間1～房間4的數(shù)據(jù)，每個(gè)房間采集500 次，每次取接收到AP 信號(hào)的RSSI均值作為位置指紋，實(shí)驗(yàn)區(qū)域的RSSI 信號(hào)變化如圖7 所示，圖7（a）～圖7（d）分別為房間1～房間4的RSSI 信號(hào)變化情況。

圖7 不同房間的RSSI 信號(hào)變化

由圖7 可知，不同位置的RSSI 信號(hào)存在差異，即RSSI 信號(hào)存在空間差異性，故可通過(guò)位置指紋來(lái)進(jìn)行區(qū)域識(shí)別。數(shù)據(jù)經(jīng)過(guò)處理后，每個(gè)房間僅保留500 條位置指紋樣本，部分位置指紋樣本信息如表1 所示，前7 列為RSSI 值，單位為dB，最后一列為房間類(lèi)別編號(hào)。

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

3.3 結(jié)果分析

為了進(jìn)一步驗(yàn)證本文方法的可行性，將2 000 條樣本數(shù)據(jù)分為2 個(gè)部分，1 400 條作為訓(xùn)練集，600 條作為測(cè)試集。在機(jī)器學(xué)習(xí)中，ROC（receiver operating characteristic）即接收器操作特征曲線(xiàn)是用來(lái)描繪學(xué)習(xí)器的泛化能力的有力工具；而AUC（area under ROC curve）即ROC 曲線(xiàn)下的面積，用來(lái)度量分類(lèi)模型的好壞。本文實(shí)驗(yàn)過(guò)程中，通過(guò)繪制不同類(lèi)別的 ROC 曲線(xiàn)來(lái)進(jìn)行模型評(píng)估，用AUC 作為模型評(píng)價(jià)指標(biāo)。對(duì)于分類(lèi)問(wèn)題，也常用分類(lèi)準(zhǔn)確率作為評(píng)價(jià)指標(biāo)。對(duì)于本文的位置感知識(shí)別準(zhǔn)確率（racc）的定義為

式中：ntp為預(yù)測(cè)房間類(lèi)別與真實(shí)房間類(lèi)別一致的樣本數(shù)；nfp為預(yù)測(cè)房間類(lèi)別與真實(shí)房間類(lèi)相反的樣本數(shù)；nfn為將預(yù)測(cè)錯(cuò)誤的房間分類(lèi)結(jié)果作為正確結(jié)果的樣本數(shù)；ntn為將預(yù)測(cè)正確的房間分類(lèi)結(jié)果當(dāng)作錯(cuò)誤結(jié)果的樣本數(shù)。在ROC 曲線(xiàn)中橫縱坐標(biāo)分別為假正率（rfp）和真正率（rtp），它們的定義公式為：

為了進(jìn)一步評(píng)價(jià)本文所提方法的性能，通過(guò)實(shí)驗(yàn)得出如圖8 所示的效果。

圖8 本文方法的效果

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

圖9 模型對(duì)比的效果

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

4 結(jié)束語(yǔ)

為了解決現(xiàn)有研究方法的室內(nèi)位置識(shí)別準(zhǔn)確率較低、穩(wěn)定性較差的問(wèn)題，本文提出一種基于組合優(yōu)化算法改進(jìn)的室內(nèi)位置感知方法。通過(guò)采集用戶(hù)在室內(nèi)區(qū)域行走時(shí)智能手機(jī)接收到的周邊AP的WiFi 信號(hào)數(shù)據(jù)，根據(jù)采集的RSSI 值來(lái)建立位置指紋數(shù)據(jù)庫(kù)，將采集的數(shù)據(jù)作為樣本對(duì)本文方法進(jìn)行測(cè)試。實(shí)驗(yàn)結(jié)果表明本文方法的室內(nèi)位置感知識(shí)別準(zhǔn)確率為98.35%，與同類(lèi)方法相比，識(shí)別準(zhǔn)確率至少提高4.79%。由于本文所進(jìn)行的實(shí)驗(yàn)是以位置區(qū)域類(lèi)別作為位置標(biāo)簽，AP的RSSI 值為位置特征，且位置標(biāo)簽是已知的，所以具有應(yīng)用局限性。下一步將研究如何在位置未知的情況下進(jìn)行室內(nèi)位置識(shí)別，從而提高模型的適用性。