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

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

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

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

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

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

0 引言

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

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

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

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

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

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

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

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

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

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

Elman神經(jīng)網(wǎng)絡(luò)是一種典型的動(dòng)態(tài)反饋型遞歸神經(jīng)網(wǎng)絡(luò)[18]，在反向傳播（back propagation,BP）神經(jīng)網(wǎng)絡(luò)的結(jié)構(gòu)基礎(chǔ)上，在隱含層上增加一個(gè)承接層作為延時(shí)算子而達(dá)到記憶的目的，從而使該網(wǎng)絡(luò)具有適應(yīng)時(shí)變特性的能力，增強(qiáng)網(wǎng)絡(luò)的全局穩(wěn)定性，在計(jì)算能力、穩(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）輸入層。信號(hào)傳輸，將學(xué)習(xí)樣本輸入到網(wǎng)絡(luò)；

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

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

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

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

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)解的缺陷，對(duì)該網(wǎng)絡(luò)的訓(xùn)練較難達(dá)到全局最優(yōu)。而差分進(jìn)化算法，具有快速尋優(yōu)、擅長解決多變量的非線性函數(shù)優(yōu)化問題等特點(diǎn)，因此，考慮采用差分進(jìn)化算法對(duì)Elman神經(jīng)網(wǎng)絡(luò)進(jìn)行優(yōu)化，但現(xiàn)有的差分進(jìn)化算法對(duì)算法后期，隨著種群個(gè)體差異減小會(huì)陷入局部最優(yōu)問題的解決效果不佳，因此，本文首先提出一種改進(jìn)的動(dòng)態(tài)的差分進(jìn)化（improved dynamic differential evolution，IDDE）算法，對(duì)差分進(jìn)化算法中的縮放因子和交叉概率因子CR進(jìn)行動(dòng)態(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)的動(dòng)態(tài)差分進(jìn)化算法優(yōu)化原理

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

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

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

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

進(jìn)行交叉后為

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

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

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

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

則得在時(shí)刻，其輸出層的輸出為

式中為Sigmoid函數(shù)。

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

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

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

進(jìn)行交叉后為

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

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

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

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

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

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

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

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

圖4 實(shí)驗(yàn)場(chǎng)地中采集數(shù)據(jù)示意圖

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

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

4.2 本文方法性能分析

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

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

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

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

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

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

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

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

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

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

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

圖7 未采用分級(jí)時(shí)各定位算法的定位誤差CDF對(duì)比

由表3可知，當(dāng)未采用分級(jí)方法時(shí)，本文IDDE-ENN定位模型的平均定位誤差為2.01 m，小于未改進(jìn)的動(dòng)態(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)定位效果時(shí)，其平均定位誤差則為4.24 m。由圖7可知，在未使用分級(jí)情況下的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)定位模型，在定位性能上有一定的提升效果。

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

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

圖8 采用分級(jí)方法時(shí)各定位算法的定位誤差CDF對(duì)比

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

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

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

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

5 結(jié)束語

為了提高室內(nèi)定位的精度并降低指紋庫匹配的復(fù)雜度，本文提出一種改進(jìn)的動(dòng)態(tài)差分優(yōu)化網(wǎng)絡(luò)的室內(nèi)分級(jí)定位方法，首先通過聚類算法將定位區(qū)域內(nèi)、包含WiFi和三軸地磁強(qiáng)度的指紋樣本進(jìn)行聚類，然后根據(jù)聚類中心，將每個(gè)類樣本作為區(qū)域指紋庫，再將每個(gè)區(qū)域指紋庫分別利用本文提出的IDDE-ENN模型進(jìn)行訓(xùn)練，生成區(qū)域定位模型。在線定位階段，首先利用用戶設(shè)備采集的WiFi和三軸地磁強(qiáng)度數(shù)據(jù)，根據(jù)歐氏距離找到最相近的聚類中心進(jìn)行區(qū)域定位，然后通過該聚類中心對(duì)應(yīng)的區(qū)域定位模型實(shí)現(xiàn)精細(xì)定位。通過實(shí)際環(huán)境試驗(yàn)，本文提出的室內(nèi)分級(jí)定位算法的平均定位誤差為1.67 m，在提升定位精度的同時(shí)也降低了指紋匹配復(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信號(hào)指紋室內(nèi)定位技術(shù)[J]. 軟件學(xué)報(bào), 2019, 30(11): 3457-3468.

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

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

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

[7]鄧昀, 朱彥, 楊逸夫, 等. 基于BP神經(jīng)網(wǎng)絡(luò)的RFID室內(nèi)定位算法研究[J]. 小型微型計(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ì)算機(jī)與應(yīng)用, 2017, 7(2): 8-13.

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

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

[12]李志, 趙大哲. 一種基于卷積神經(jīng)元網(wǎng)絡(luò)的室內(nèi)定位算法[J]. 小型微型計(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é)報(bào), 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)的動(dòng)態(tài)差分優(yōu)化網(wǎng)絡(luò)的室內(nèi)分級(jí)定位方法[J].導(dǎo)航定位學(xué)報(bào), 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é)基金項(xiàng)目（61902237）；上海市“科技創(chuàng)新行動(dòng)計(jì)劃”高新技術(shù)領(lǐng)域項(xiàng)目（18511101600）；上海市科委青年科技英才“揚(yáng)帆計(jì)劃”項(xiàng)目（19YF1418200）。

鄢松（1993—），男，河南信陽人，碩士研究生，研究方向?yàn)槭覂?nèi)定位。

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