改進(jìn)的動態(tài)差分優(yōu)化網(wǎng)絡(luò)的室內(nèi)分級定位方法

鄢 松，吳 飛，朱 海，陸雯霞

改進(jìn)的動態(tài)差分優(yōu)化網(wǎng)絡(luò)的室內(nèi)分級定位方法

鄢 松，吳 飛，朱 海，陸雯霞

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

針對指紋定位方法中單一指紋信息特征有限，以及在提升定位精度時，因增大指紋庫造成指紋匹配復(fù)雜度增加，導(dǎo)致定位效率不高等問題，提出一種改進(jìn)的動態(tài)差分優(yōu)化網(wǎng)絡(luò)的室內(nèi)分級定位方法：離線階段，在無線保真（WiFi）指紋中引入三軸地磁強(qiáng)度特征，增加定位區(qū)域的局部特征信息，并將指紋樣本通過均值聚類算法（-means）進(jìn)行聚類切分，形成區(qū)域指紋庫，各區(qū)域指紋庫分別利用改進(jìn)的動態(tài)差分優(yōu)化埃爾曼神經(jīng)網(wǎng)絡(luò)（IDDE-ENN）模型，訓(xùn)練得到每個區(qū)域的精細(xì)定位模型；在線定位階段，根據(jù)用戶的定位數(shù)據(jù)與區(qū)域指紋庫的聚類中心匹配，在減少指紋搜索復(fù)雜度的同時，實現(xiàn)了區(qū)域級定位，然后通過該區(qū)域的定位模型對用戶進(jìn)行精細(xì)定位。實驗結(jié)果表明，該方法在線定位階段的平均定位誤差為1.67 m，驗證了該室內(nèi)定位模型的有效性。

分級定位；動態(tài)差分；埃爾曼神經(jīng)網(wǎng)絡(luò)；地磁導(dǎo)航

0 引言

隨著室外定位技術(shù)的不斷發(fā)展，人們對定位服務(wù)的依賴越來越多，對基于位置服務(wù)的需求也日益增長。目前，室外定位技術(shù)已逐漸發(fā)展成熟，基本滿足民用需求，但是在室內(nèi)定位方面，由于定位場景的多樣性、室內(nèi)環(huán)境復(fù)雜性以及一些定位技術(shù)的局限性等原因，尚未形成一套統(tǒng)一的、穩(wěn)定成熟的解決方案。

針對日常生活中不同的室內(nèi)定位場景和定位需求，人們提出了不同的定位方法，其中主要包括行人航跡推算（pedestrian dead reckoning, PDR）[1-4]、超寬帶（ultra wide band, UWB）[5]、射頻識別（radio frequency identification, RFID）[6-7]、藍(lán)牙[8]、無線保真（wireless fidelity, WiFi）等室內(nèi)定位方法。然而，這些定位技術(shù)都存在著各種各樣的問題，其中基于慣性傳感器的PDR定位方法，慣性傳感器的累積誤差會逐漸地降低定位的精度；雖然UWB的定位精度較高，但高精度且定位時延低的UWB定位系統(tǒng)，價格相對較貴，并且傳輸距離也受限，一般多用于室內(nèi)的小范圍定位場景；此外，采用RFID定位和藍(lán)牙定位方法時，均需要在定位場景中部署大量的定位標(biāo)簽設(shè)備，無疑增加了定位成本。由于WiFi在人們?nèi)粘Ｉ钪惺褂脧V泛，布設(shè)范圍也較廣，因此，采用WiFi進(jìn)行室內(nèi)定位可有效地降低定位成本，同時其定位精度也可達(dá)到室內(nèi)定位的需求。

目前在基于WiFi的室內(nèi)定位方法當(dāng)中，利用WiFi指紋進(jìn)行定位的研究比較多，WiFi指紋定位主要分為兩個階段：1）離線指紋庫采集階段，需要對定位區(qū)域內(nèi)的定位信號進(jìn)行大量采集并形成指紋庫；2）在線定位階段，根據(jù)定位設(shè)備實時采集的信號，與指紋庫進(jìn)行匹配來獲取位置信息。相關(guān)學(xué)者也提出了各自不同的WiFi指紋定位方法，文獻(xiàn)[9-10]為采用近鄰（-nearest neighbor, KNN）進(jìn)行在線指紋匹配的室內(nèi)定位算法，但由于KNN算法在在線定位時，需要與指紋庫的所有指紋進(jìn)行匹配計算，當(dāng)指紋庫較大時，無疑帶來了較大指紋匹配復(fù)雜度，影響了在線定位效率，并且單一的指紋特征也限制著定位精度的提升。文獻(xiàn)[11]提出一種均值聚類算法（-means clustering algorithm）與加權(quán)近鄰（weighted-nearest neighbors, WKNN）相結(jié)合的室內(nèi)定位方法：首先在離線階段對指紋庫進(jìn)行聚類；然后在線定位時，仍需要對聚類后的指紋庫進(jìn)行搜索匹配，該方法雖采用了分級定位的思想，但是在線定位時，仍需要對聚類后的指紋庫的所有指紋進(jìn)行搜索匹配，并未有效地降低在線定位階段的指紋匹配復(fù)雜度。文獻(xiàn)[12]采用一種基于卷積神經(jīng)元網(wǎng)絡(luò)的室內(nèi)定位算法，將無線接入點(diǎn)（access point,AP）指紋樣本轉(zhuǎn)換為灰度圖像指紋樣本后，再利用卷積神經(jīng)網(wǎng)絡(luò)進(jìn)行訓(xùn)練，但未對指紋庫進(jìn)行有效劃分，在較大區(qū)域定位時，直接使用整個指紋庫訓(xùn)練也會在一定程度上影響定位精度。因此，目前WiFi指紋定位方法主要存在兩個問題: 1）在較大區(qū)域的定位場景中，指紋庫的體積往往也較大，從而使在線定位階段進(jìn)行指紋搜索匹配的復(fù)雜度增加，降低了在線定位效率；2）當(dāng)增大指紋采集密度時，相鄰指紋采集間隔較小，從而導(dǎo)致單一的WiFi指紋特征相似度較高，影響定位精度。

此外，在基于差分進(jìn)化算法的室內(nèi)定位研究中，文獻(xiàn)[13]提出一種基于差分進(jìn)化算法的指紋庫定位方法，利用差分進(jìn)化算法對AP的放置位置進(jìn)行優(yōu)化，以得到較好的指紋信息，但是也并未考慮WiFi指紋庫體積導(dǎo)致的指紋匹配復(fù)雜度及WiFi指紋特征相似問題。文獻(xiàn)[14]提出一種混合粒子群融合差分進(jìn)化算法的室內(nèi)多邊定位方法，利用差分進(jìn)化算法對混合粒子群算法進(jìn)行優(yōu)化，但由于WiFi信號的多徑效應(yīng)帶來的距離估計誤差及錨點(diǎn)的位置測量誤差，使得該種方法定位誤差比指紋庫匹配定位方法的誤差要大很多。文獻(xiàn)[15]提出一種利用差分進(jìn)化算法結(jié)合灰狼優(yōu)化（grey wolf optimizer,GWO）算法，進(jìn)行優(yōu)化支持向量回歸（support vector regression, SVR）的射頻識別（radio frequency identification, RFID）指紋定位方法，由于SVR算法一般只適合解決小樣本問題，對于定位區(qū)域比較大的指紋庫定位，并不能夠得到很好地解決；文獻(xiàn)[16]提出一種利用差分進(jìn)化改進(jìn)貝葉斯壓縮感知的定位算法，由于貝葉斯模型也是在小規(guī)模的數(shù)據(jù)集上表現(xiàn)較好，在較大規(guī)模的指紋數(shù)據(jù)集中性能并不佳。

針對上述問題，本文提出一種改進(jìn)的動態(tài)差分優(yōu)化網(wǎng)絡(luò)的室內(nèi)分級定位方法，在WiFi指紋中增加指紋點(diǎn)屬地的三軸地磁強(qiáng)度，有助于降低在增加指紋采集密度后的指紋相似度；又考慮在離線階段，將定位區(qū)域所采集的指紋利用-means算法進(jìn)行聚類，形成每個聚類中心所對應(yīng)的區(qū)域指紋庫，然后由本文所提出的改進(jìn)的動態(tài)的差分進(jìn)化算法優(yōu)化埃爾曼（Elman）神經(jīng)網(wǎng)絡(luò)（improved dynamic differential evolution-Elman neural network, IDDE-ENN）模型，利用各區(qū)域指紋庫，分別訓(xùn)練出每個區(qū)域的定位模型；在線階段，首先根據(jù)定位設(shè)備所采集的WiFi和三軸地磁強(qiáng)度信息與聚類中心進(jìn)行匹配，實現(xiàn)區(qū)域級定位，然后再利用該區(qū)域的定位模型實現(xiàn)精細(xì)定位，在提升定位精度的同時，有效地解決了隨著指紋采集密度增加導(dǎo)致指紋庫體積增大所帶來的指紋搜索匹配時間復(fù)雜度增加、在線定位效率不高的問題。

1 差分進(jìn)化算法

差分進(jìn)化算法[17]與遺傳算法、粒子群算法相似，都是一種基于群體的隨機(jī)并行優(yōu)化算法，利用模擬生物種群內(nèi)個體的合作和競爭關(guān)系進(jìn)行群體內(nèi)的優(yōu)化搜索，通常用于求解非線性、不可微問題，具有速度快和魯棒性好等特點(diǎn)。

差分進(jìn)化算法的詳細(xì)步驟如下：

1）種群初始化。在解空間中隨機(jī)均勻地產(chǎn)生個個體，組成初始種群，即：

2 Elman神經(jīng)網(wǎng)絡(luò)

Elman神經(jīng)網(wǎng)絡(luò)是一種典型的動態(tài)反饋型遞歸神經(jīng)網(wǎng)絡(luò)[18]，在反向傳播（back propagation,BP）神經(jīng)網(wǎng)絡(luò)的結(jié)構(gòu)基礎(chǔ)上，在隱含層上增加一個承接層作為延時算子而達(dá)到記憶的目的，從而使該網(wǎng)絡(luò)具有適應(yīng)時變特性的能力，增強(qiáng)網(wǎng)絡(luò)的全局穩(wěn)定性，在計算能力、穩(wěn)定性方面，Elman 神經(jīng)網(wǎng)絡(luò)比BP神經(jīng)網(wǎng)絡(luò)更優(yōu)，能夠快速解決尋優(yōu)問題。Elman神經(jīng)網(wǎng)絡(luò)的結(jié)構(gòu)主要分為四層，分別為輸入層、隱藏層、承接層和輸出層，其網(wǎng)絡(luò)結(jié)構(gòu)如圖1所示。

圖1 Elman神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)

1）輸入層。信號傳輸，將學(xué)習(xí)樣本輸入到網(wǎng)絡(luò)；

2）隱含層。將輸入層的輸出和網(wǎng)絡(luò)中與隱含層相連接的承接層的輸出，一起作為隱含層的輸入，其表達(dá)式為

3）承接層。主要用來存儲隱含層各單元前一時刻的輸出，可以看作一個時延算子，其表達(dá)式為

4）輸出層。為隱含層單元的加權(quán)輸出，其表達(dá)式為

3 改進(jìn)的動態(tài)差分優(yōu)化網(wǎng)絡(luò)的室內(nèi)分級定位方法

3.1 基于改進(jìn)差分進(jìn)化算法融合Elman神經(jīng)網(wǎng)絡(luò)

由于Elman神經(jīng)網(wǎng)絡(luò)與BP神經(jīng)網(wǎng)絡(luò)類似，都是采用梯度下降法進(jìn)行網(wǎng)絡(luò)優(yōu)化，容易出現(xiàn)訓(xùn)練速度慢以及局部最優(yōu)解的缺陷，對該網(wǎng)絡(luò)的訓(xùn)練較難達(dá)到全局最優(yōu)。而差分進(jìn)化算法，具有快速尋優(yōu)、擅長解決多變量的非線性函數(shù)優(yōu)化問題等特點(diǎn)，因此，考慮采用差分進(jìn)化算法對Elman神經(jīng)網(wǎng)絡(luò)進(jìn)行優(yōu)化，但現(xiàn)有的差分進(jìn)化算法對算法后期，隨著種群個體差異減小會陷入局部最優(yōu)問題的解決效果不佳，因此，本文首先提出一種改進(jìn)的動態(tài)的差分進(jìn)化（improved dynamic differential evolution，IDDE）算法，對差分進(jìn)化算法中的縮放因子和交叉概率因子CR進(jìn)行動態(tài)改進(jìn)，然后將改進(jìn)的差分進(jìn)化算法與Elman神經(jīng)網(wǎng)絡(luò)融合進(jìn)行優(yōu)化，提出一種IDDE-ENN算法，這樣可以有效地克服Elman神經(jīng)網(wǎng)絡(luò)的收斂速度慢和局部最優(yōu)問題，IDDE-ENN算法原理如圖2所示。

圖2 本文IDDE-ENN算法原理

3.1.1 改進(jìn)的動態(tài)差分進(jìn)化算法優(yōu)化原理

針對現(xiàn)有的差分進(jìn)化算法并沒有很好地解決算法后期隨著種群個體差異的減小，算法收斂速度會變慢，容易陷入局部最優(yōu)問題。本文提出一種IDDE算法，具體改進(jìn)原理為：

1）對差分進(jìn)化算法中的縮放因子進(jìn)行改進(jìn)。由差分進(jìn)化算法原理可知，縮放因子的特性是：當(dāng)較大時，種群能夠以較快速度進(jìn)行更新迭代；較小時，收斂速度也會變慢。因此，相較于固定的，本文的IDDE算法是使縮放因子能夠跟隨迭代次數(shù)進(jìn)行動態(tài)更新，即在迭代前期，由于種群差異較大，可使較大，從而以較快速度進(jìn)行迭代；而在種群個體迭代后期，隨著迭代次數(shù)增加，種群個體差異減小逐漸趨于最優(yōu)個體，因此使縮放因子根據(jù)迭代次數(shù)也逐漸減小，從而使種群能夠在較小的范圍內(nèi)尋找到最優(yōu)個體。

然后，由動態(tài)更新的縮放因子進(jìn)行個體變異，即

2）對交叉過程中的交叉概率因子進(jìn)行改進(jìn)。在種群交叉過程中，將Elman神經(jīng)網(wǎng)絡(luò)的損失函數(shù)作為自適應(yīng)度函數(shù)，即由自適應(yīng)度函數(shù)得到的自適應(yīng)度值越大，其損失函數(shù)值也越大。由式（4）可知，當(dāng)交叉概率因子CR較大時，實驗個體能夠保留變異個體中更多的元素，當(dāng)CR較小時，則會淘汰變異個體中的大部分元素。因此，合理地對CR進(jìn)行取值，能夠使算法達(dá)到更優(yōu)效果。本文提出的IDDE算法為：首先在種群中隨機(jī)選擇三個個體，由自適應(yīng)度函數(shù)得到每個個體的自適應(yīng)度值后，由小到大進(jìn)行排序；然后根據(jù)變異個體的自適應(yīng)度值與隨機(jī)選擇的個體中的最大自適應(yīng)度值之間的差值來動態(tài)更新CR，從而使CR能夠根據(jù)當(dāng)前迭代過程中變異個體的優(yōu)劣來進(jìn)行動態(tài)更新，從而使得在交叉過程中得到的實驗個體也更優(yōu)。具體改進(jìn)原理為：

進(jìn)行交叉后為

3.1.2 本文IDDE算法對Elman神經(jīng)網(wǎng)絡(luò)進(jìn)行優(yōu)化

針對Elman神經(jīng)網(wǎng)絡(luò)采用梯度下降法進(jìn)行訓(xùn)練時，易出現(xiàn)收斂慢、局部最優(yōu)解的缺陷，本文將提出的IDDE算法與Elman神經(jīng)網(wǎng)絡(luò)進(jìn)行融合優(yōu)化，將Elman神經(jīng)網(wǎng)絡(luò)的權(quán)值和偏置作為IDDE算法種群個體，將Elman神經(jīng)網(wǎng)絡(luò)的損失函數(shù)作為IDDE算法選擇過程中的自適度函數(shù)，從而改善Elman神經(jīng)網(wǎng)絡(luò)在訓(xùn)練過程中陷入局部最優(yōu)的缺陷，以達(dá)到最優(yōu)解，實現(xiàn)對Elman神經(jīng)網(wǎng)絡(luò)的優(yōu)化。

本文提出的IDDE-ENN算法的具體步驟如下：

1）計算Elman神經(jīng)網(wǎng)絡(luò)的損失函數(shù)，即均方根誤差函數(shù)，并將其作為IDDE算法的自適應(yīng)度函數(shù)，在時刻，Elman網(wǎng)絡(luò)的隱含層輸出為

則得在時刻，其輸出層的輸出為

式中為Sigmoid函數(shù)。

因此可得Elman神經(jīng)網(wǎng)絡(luò)的損失函數(shù)RMSE(,），將其作為IDDE-ENN模型的自適應(yīng)度函數(shù)，即

2）種群初始化。在解空間中隨機(jī)均勻地產(chǎn)生個個體，組成初始種群，即：

然后進(jìn)行變異，即

進(jìn)行交叉后為

3.2 基于IDDE-ENN算法的室內(nèi)分級定位方法

本文基于IDDE-ENN算法，提出一種改進(jìn)的動態(tài)差分優(yōu)化網(wǎng)絡(luò)的室內(nèi)分級定位方法，該定位方法主要分為兩個階段，離線階段和在線階段。

1）離線階段。在離線階段主要分為兩部分：一是構(gòu)建區(qū)域指紋庫，首先實驗人員利用采集設(shè)備，在定位區(qū)域內(nèi)采集每個指紋點(diǎn)的WiFi和三軸地磁場強(qiáng)度的樣本數(shù)據(jù)，然后利用基于密度聚類的-means算法，對采集的樣本進(jìn)行聚類，再將聚類后得到的每個類的聚類中心與該類數(shù)據(jù)做映射，形成每個區(qū)域指紋庫；二是進(jìn)行區(qū)域定位模型訓(xùn)練，將聚類形成的每個區(qū)域指紋庫分別利用本文提出的IDDE-ENN模型進(jìn)行訓(xùn)練，得到每個對應(yīng)區(qū)域的室內(nèi)定位模型。

圖3 改進(jìn)的動態(tài)差分優(yōu)化網(wǎng)絡(luò)的室內(nèi)分級定位方法

2）在線階段。首先根據(jù)定位區(qū)域內(nèi)用戶設(shè)備實時采集到的WiFi和三軸地磁強(qiáng)度數(shù)據(jù)，與每個區(qū)域指紋庫對應(yīng)的聚類中心，利用歐氏距離進(jìn)行搜索匹配，找到最相近的聚類中心，實現(xiàn)區(qū)域級定位，然后利用該區(qū)域的IDDE-ENN室內(nèi)定位模型，再進(jìn)行精細(xì)定位。

4 實驗與結(jié)果分析

4.1 實驗環(huán)境與數(shù)據(jù)采集

為驗證本文提出的改進(jìn)的動態(tài)差分優(yōu)化網(wǎng)絡(luò)的室內(nèi)分級定位方法的定位性能，本文選取了學(xué)校實訓(xùn)樓二樓中的走廊和空曠的大廳區(qū)域作為實驗場地，指紋點(diǎn)采集面積約為411 m2，在場地中使用7個實驗AP，實驗場地中采集數(shù)據(jù)示意圖如圖4所示，為便于數(shù)據(jù)采集，將實驗場地分成1 m×1 m的網(wǎng)格。對指紋采集過程中未收集到的AP，則將其接收信號強(qiáng)度賦值為-100 dB·m。

圖4 實驗場地中采集數(shù)據(jù)示意圖

1）指紋庫數(shù)據(jù)采集。采集設(shè)備為榮耀magic2手機(jī)，在每個劃分的網(wǎng)格的中心，以2 Hz的頻率采集WiFi和地磁數(shù)據(jù)的采集，分別在每個網(wǎng)格中心的東、南、西、北四個方向上采集20 s，即每個網(wǎng)格的采集總時長為80 s，共采集指紋點(diǎn)415個，指紋數(shù)目共66400條。

2）測試指紋數(shù)據(jù)集采集。在試驗場地中設(shè)計一條測試數(shù)據(jù)集的采集路徑，如圖4中的藍(lán)色線所示，藍(lán)色路徑上的黃色點(diǎn)為測試指紋數(shù)據(jù)采集點(diǎn)，實驗人員手持手機(jī)采集設(shè)備，在每個采集點(diǎn)進(jìn)行測試數(shù)據(jù)采集，每個采集點(diǎn)的間隔為1 m，在每個網(wǎng)格中心的東、南、西、北四個方向上分別采集20 s，共采集測試指紋點(diǎn)170個，采集的測試指紋數(shù)目共為27200條。

4.2 本文方法性能分析

1）每個區(qū)域的IDDE-ENN定位模型性能分析。在模型離線訓(xùn)練階段，首先根據(jù)在實驗場地中所采集的每個指紋點(diǎn)的WiFi和三軸地磁強(qiáng)度數(shù)據(jù)，利用-means算法進(jìn)行樣本聚類，以歐氏距離作為相似性度量。根據(jù)聚類的實驗結(jié)果，當(dāng)聚類算法中的參數(shù)=6時，定位性能最佳，然后將每個類的樣本數(shù)據(jù)作為每個聚類中心所映射的區(qū)域指紋庫。根據(jù)聚類得到每個區(qū)域指紋庫，按照7:3的比例進(jìn)行劃分，分別得到每個區(qū)域定位模型的訓(xùn)練數(shù)據(jù)集和測試數(shù)據(jù)集，由每個區(qū)域的訓(xùn)練數(shù)據(jù)集分別進(jìn)行訓(xùn)練，得到每個區(qū)域的IDDE-ENN定位模型。通過指紋聚類，將整個定位區(qū)域內(nèi)的指紋樣本聚為6個類，分別對應(yīng)區(qū)域1至區(qū)域6的區(qū)域指紋庫，每個區(qū)域的定位模型性能如表1所示。

表1 每個區(qū)域定位模型性能分析

每個區(qū)域定位模型的定位誤差的累積分布函數(shù)（cumulative distribution function, CDF）如圖5所示。由表1分析可知，除區(qū)域5和區(qū)域6以外，其他區(qū)域的平均定位誤差在2 m以下。

圖5 每個區(qū)域定位模型的定位誤差CDF

由圖5可知，當(dāng)CDF不小于70%時，區(qū)域1至區(qū)域6的定位誤差在2 m以內(nèi)。

2）采用WiFi指紋與WiFi/地磁指紋，對整個定位模型性能進(jìn)行對比分析。為了分析三軸地磁強(qiáng)度與WiFi指紋結(jié)合有助于增強(qiáng)定位指紋特征，從而減小隨著指紋采集密度增加而導(dǎo)致的較大的指紋相似度，首先采用WiFi的指紋樣本、WiFi和三軸地磁強(qiáng)度融合的指紋樣本，分別進(jìn)行訓(xùn)練得到各自的IDDE-ENN模型，然后分別利用4.1節(jié)中的測試指紋數(shù)據(jù)集進(jìn)行對比測試分析，WiFi與WiFi/地磁的指紋定位性能對比如表2所示，定位誤差的CDF對比如圖6所示。

表2 WiFi與WiFi+地磁的指紋定位性能對比 單位：m

圖6 WiFi指紋與WiFi+地磁指紋定位誤差CDF對比

通過表2對比可看出，只有WiFi數(shù)據(jù)訓(xùn)練得到的定位模型，其平均定位誤差為2.04 m，而WiFi融合三軸地磁強(qiáng)度信息的指紋樣本，訓(xùn)練得到的定位模型的定位誤差為1.67 m，平均定位誤差相比降低了18.1%。由圖6可知，當(dāng)CDF為80%時，WiFi融合三軸地磁強(qiáng)度的指紋樣本訓(xùn)練模型的定位誤差為1.96 m，而WiFi樣本訓(xùn)練的模型定位誤差為2.34 m，相比較于只有WiFi特征的指紋樣本訓(xùn)練得到的室內(nèi)定位模型，WiFi與地磁特征融合的指紋樣本對單獨(dú)的WiFi指紋有一定的改善效果，從而使得定位模型的性能得到了一程度的提升。

3）與其它定位算法對比分析。將本文將提出的改進(jìn)的動態(tài)差分優(yōu)化網(wǎng)絡(luò)的室內(nèi)分級定位方法與基于其它算法的室內(nèi)定位模型，分別進(jìn)行了采用分級方法的定位實驗和未采用分級方法的定位實驗做對比分析。未采用分級方法時，各定位算法的定位性能對比如表3所示，各算法的CDF對比結(jié)果如圖7所示。

表3 未采用分級方法時本文IDDE-ENN模型與其它定位方法性能對比 單位：m

圖7 未采用分級時各定位算法的定位誤差CDF對比

由表3可知，當(dāng)未采用分級方法時，本文IDDE-ENN定位模型的平均定位誤差為2.01 m，小于未改進(jìn)的動態(tài)差分進(jìn)化算法優(yōu)化Elman神經(jīng)網(wǎng)絡(luò)（dynamic differential evolution-Elman neural network, DDE-ENN）的定位模型的平均定位誤差，采用BP模型的平均定位誤差為2.63 m，基于WKNN算法的定位模型的平均定位誤差在3 m以上，而KNN算法定位模型在=5達(dá)到最優(yōu)定位效果時，其平均定位誤差則為4.24 m。由圖7可知，在未使用分級情況下的IDDE-ENN定位模型，在3 m以內(nèi)定位誤差的CDF達(dá)到90%，優(yōu)于DDE-ENN和BP模型、以及基于KNN、WKNN算法的定位模型，因此，本文所提出的IDDE-ENN定位模型相比于基于DDE-ENN、BP、KNN以及WKNN算法的室內(nèi)定位模型，在定位性能上有一定的提升效果。

采用分級方法時，首先將本文中利用-means算法聚類好的區(qū)域指紋庫分別與基于DDE-ENN、BP神經(jīng)網(wǎng)絡(luò)、KNN、WKNN算法結(jié)合作為分級定位定位模型，然后與本文的IDDE-ENN分級定位模型進(jìn)行對比試驗，各定位模型的定位性能對比如表4所示，不同CDF定位誤差對比如圖8所示。

表4 采用分級方法時本文IDDE-ENN模型與其它定位方法性能對比 單位：m

圖8 采用分級方法時各定位算法的定位誤差CDF對比

當(dāng)參數(shù)=4時，使用分級方法后的KNN算法模型定位誤差最小。由表4可知，在使用分級方法時，本文IDDE-ENN模型的平均定位誤差為1.67 m，而基于DDE-ENN、BP、KNN、WKNN的模型的平均定位誤差均在2 m以上。由圖8可知，定位誤差CDF為80%時，IDDE-ENN模型的定位誤差為1.96 m，而基于BP、KNN以及WKNN的定位模型的定位誤差均在3 m以上。與未采用分級方法時的IDDE-ENN模型相比，采用分級后的IDDE-ENN模型，其定位誤差相對降低16.9%，與采用分級后的DDE-ENN模型相比，其定位誤差降低17.3%。因此，通過對比分析可知，分級定位的方法對本文的提出的IDDE-ENN定位模型的定位精度也具有一定的提升效果。

4）與其它定位方法的指紋庫以及指紋匹配復(fù)雜度對比分析。為說明本文提出的IDDE-ENN定位模型在提高定位精度的同時，也降低了在線定位階段指紋匹配的復(fù)雜度，將本文IDDE-ENN模型與其它定位方法所使用的指紋庫容量、指紋匹配時間復(fù)雜度以及模型訓(xùn)練時長這三個方面進(jìn)行對比，其對比結(jié)果如表5所示。

表5 各方法的指紋庫以及在線定位指紋匹配的復(fù)雜度對比分析

為便于分析，設(shè)指紋點(diǎn)總數(shù)為個，KNN和WKNN算法是取每個指紋點(diǎn)每個采集方向上的指紋強(qiáng)度的均值作為一條指紋，則可得KNN和WKNN所使用的指紋數(shù)量為4，而BP、DDE-ENN和IDDE-ENN算法的指紋數(shù)量則為160；采用常采用衡量算法時間復(fù)雜度的大O符號表示法，對各定位算法的指紋匹配復(fù)雜度進(jìn)行對比分析，設(shè)利用-means聚類算法將指紋庫分為個區(qū)域指紋庫，由于在使用KNN和WKNN算法時，不管將指紋庫分為多少個類，在線定位時其總是需要遍歷所有指紋庫才能找到最相近的個指紋，因此可得KNN和WKNN定位算法的在線定位指紋匹配的復(fù)雜度為O（4），而BP、ENN和IDDE-ENN算法則只需要與個聚類中心進(jìn)行比較即可，所以BP、DDE-ENN和IDDE-ENN算法的在線定位指紋匹配復(fù)雜度為O（），其中遠(yuǎn)小于4，指紋匹配復(fù)雜度相對更低；在模型訓(xùn)練時長方面，KNN和WKNN算法不需要進(jìn)行訓(xùn)練，由表5可知，IDDE-ENN模型訓(xùn)練時長與BP和DDE-ENN網(wǎng)絡(luò)相比，也較長。通過對采用分級方法時，各定位方法的平均定位誤差對比可知，雖然IDDE-ENN模型的所使用的指紋庫較大，離線階段訓(xùn)練時長也較大，但由于IDDE-ENN模型的定位誤差更小，且在線定位時指紋匹配復(fù)雜度也相對較低，在模型訓(xùn)練完后，在線定位時只需加載訓(xùn)練好的模型即可，所以IDDE-ENN模型相對更優(yōu)。

5 結(jié)束語

為了提高室內(nèi)定位的精度并降低指紋庫匹配的復(fù)雜度，本文提出一種改進(jìn)的動態(tài)差分優(yōu)化網(wǎng)絡(luò)的室內(nèi)分級定位方法，首先通過聚類算法將定位區(qū)域內(nèi)、包含WiFi和三軸地磁強(qiáng)度的指紋樣本進(jìn)行聚類，然后根據(jù)聚類中心，將每個類樣本作為區(qū)域指紋庫，再將每個區(qū)域指紋庫分別利用本文提出的IDDE-ENN模型進(jìn)行訓(xùn)練，生成區(qū)域定位模型。在線定位階段，首先利用用戶設(shè)備采集的WiFi和三軸地磁強(qiáng)度數(shù)據(jù)，根據(jù)歐氏距離找到最相近的聚類中心進(jìn)行區(qū)域定位，然后通過該聚類中心對應(yīng)的區(qū)域定位模型實現(xiàn)精細(xì)定位。通過實際環(huán)境試驗，本文提出的室內(nèi)分級定位算法的平均定位誤差為1.67 m，在提升定位精度的同時也降低了指紋匹配復(fù)雜度，證明了本文所提出的定位方法的有效性。

[1]FAN Q G, ZHANG H, PAN P, et al. Improved pedestrian dead reckoning based on a robust adaptive Kalman filter for indoor inertial location system[J]. Sensors, 2019, 19(2): 294-315.

[2]YU J G, NA Z Y, LIU X, et al. WiFi/PDR-integrated indoor localization using unconstrained smartphones[J]. EURASIP Journal on Wireless Communications and Networking, 2019(1): 1-13.

[3]石柯, 宋小妹, 王信達(dá), 等. 多傳感器輔助的WiFi信號指紋室內(nèi)定位技術(shù)[J]. 軟件學(xué)報, 2019, 30(11): 3457-3468.

[4]宋世銘, 王繼, 韓李濤. 一種基于改進(jìn)粒子濾波算法的室內(nèi)融合定位方法[J]. 導(dǎo)航定位學(xué)報, 2020, 8(1): 99-106.

[5]張寶軍, 田奇, 王珩, 等. 基于CNN和在線學(xué)習(xí)的UWB室內(nèi)定位算法[J]. 傳感技術(shù)學(xué)報, 2020, 33(4): 511-516.

[6]李麗, 鄭嘉利, 王哲, 等. 基于異步優(yōu)勢動作評價的RFID室內(nèi)定位算法[J]. 計算機(jī)科學(xué), 2020, 47(2): 233-238.

[7]鄧昀, 朱彥, 楊逸夫, 等. 基于BP神經(jīng)網(wǎng)絡(luò)的RFID室內(nèi)定位算法研究[J]. 小型微型計算機(jī)系統(tǒng), 2019, 40(8): 1707-1712.

[8]武濤. 基于WiFi和藍(lán)牙融合的室內(nèi)定位算法的研究[D]. 蕪湖: 安徽工程大學(xué), 2019.

[9]羊宗灝, 程凱, 周寶定, 等. 基于RSS相關(guān)性的位置指紋室內(nèi)定位方法[J]. 智能計算機(jī)與應(yīng)用, 2017, 7(2): 8-13.

[10]吳澤泰, 蔡仁欽, 徐書燕, 等. 基于K近鄰法的WiFi定位研究與改進(jìn)[J]. 計算機(jī)工程, 2017, 43(3): 289-293.

[11]王亞濤, 王新珩, 董育寧, 等. 基于Kmeans和動態(tài)WKNN的兩層Wi-Fi改進(jìn)定位方法[J]. 南京郵電大學(xué)學(xué)報(自然科學(xué)版), 2017, 37(5): 41-47.

[12]李志, 趙大哲. 一種基于卷積神經(jīng)元網(wǎng)絡(luò)的室內(nèi)定位算法[J]. 小型微型計算機(jī)系統(tǒng), 2019, 40(3): 533-537.

[13]LIU J L, XU B G, WAN Y H, et al. A rang-free location method based on differential evolution algorithm[C]//The Institute of Electrical and Electronic Engineers (IEEE). Proceedings of Cross Strait Quad-regional Radio Science & Wireless Technology Conference. Chengdu: IEEE, 2013: 381-384[2020-05-28].

[14]吳斌, 金潔麗. 混合粒子群和差分進(jìn)化的定位算法[J]. 通信技術(shù), 2020, 53(4): 873-879.

[15]徐楊杰, 王艷, 嚴(yán)大虎, 等. 基于Newton插值與混合灰狼優(yōu)化SVR的RFID定位算法[J]. 系統(tǒng)仿真學(xué)報, 2017, 29(9): 1921-1929.

[16]李文浩. 矩陣填充結(jié)合貝葉斯壓縮感知的位置指紋定位[D]. 沈陽: 遼寧大學(xué), 2016.

[17]STORN R, PRICE K. Differential evolution - a simple and efficient heuristic for global optimization over continuous spaces[J]. Journal of Global Optimization, 1997, 11(4): 341-359.

[18]ELMAN J L. Finding structure in time[J]. Cognitive Science, 1990, 14(2): 179-211.

Indoor hierarchical positioning based on dynamic differential optimization network

YAN Song, WU Fei, ZHU Hai, LU Wenxia

（School of Electronic and Electrical Engineering, Shanghai University of Engineering Science, Shanghai 201620, China）

Aiming at the problems of limited single fingerprint information features in fingerprint positioning methods, and high fingerprint matching complexity and low positioning efficiency due to the increase of fingerprint database when improving positioning accuracy, the paper proposed an indoor hierarchical positioning method based on dynamic differential optimization network: at the offline stage, three-axis geomagnetic features were introduced into Wireless Fidelity (WiFi) fingerprints to increase the local feature information of the positioning area, and the fingerprint samples were clustered and segmented to form a regional fingerprint database by the-means algorithm, then the fingerprint database of each region was trained to obtain a fine positioning model for each region by using the Improved Dynamic Differential Evolution-Elman Neural Network (IDDE-ENN) algorithm; at the online positioning stage, the location data of the user were matched with the cluster center of the regional fingerprint database, and the region-level positioning was achieved with reducing the complexity of fingerprint searching, then the user was finely positioned through the regional positioning model. Experimental result showed that at the online positioning stage, the average positioning error of the proposed method would be 1.67 m, indicating the validity of the indoor positioning model.

hierarchical positioning; dynamic difference; Elman neural network; geomagnetism navigation

P228

A

2095-4999(2021)02-0012-09

鄢松，吳飛，朱海，等.改進(jìn)的動態(tài)差分優(yōu)化網(wǎng)絡(luò)的室內(nèi)分級定位方法[J].導(dǎo)航定位學(xué)報, 2021, 9(2): 12-20.（YAN Song, WU Fei, ZHU Hai,et al. Indoor hierarchical positioning based on dynamic differential optimization network[J].Journal of Navigation and Positioning, 2021, 9(2): 12-20.）

10.16547/j.cnki.10-1096.20210203.

2020-06-19

國家自然科學(xué)基金青年科學(xué)基金項目（61902237）；上海市“科技創(chuàng)新行動計劃”高新技術(shù)領(lǐng)域項目（18511101600）；上海市科委青年科技英才“揚(yáng)帆計劃”項目（19YF1418200）。

鄢松（1993—），男，河南信陽人，碩士研究生，研究方向為室內(nèi)定位。

吳飛（1968—），男，上海人，博士，教授，研究方向為計算機(jī)并行處理與節(jié)能控制，信息物理融合系統(tǒng)，室內(nèi)定位技術(shù)等。