基于神經(jīng)網(wǎng)絡(luò)的多源融合室內(nèi)定位算法①

陳 娟, 單志龍,2, 鄧嘉豪, 曾衍華

1(華南師范大學(xué) 計(jì)算機(jī)學(xué)院, 廣州 510631)

2(華南師范大學(xué) 網(wǎng)絡(luò)教育學(xué)院, 廣州 510631)

1 引言

目前常用的室內(nèi)定位技術(shù)包括藍(lán)牙[1]、超寬帶(UWB)[2]、射頻識(shí)別(RFID)[3]、紅外[4]、Zigbee[5]、視覺(jué)[6]和可見(jiàn)光[7]等, 這些技術(shù)需要部署特定的基礎(chǔ)設(shè)施, 方法復(fù)雜且昂貴, 很難大規(guī)模推廣. 隨著智能手機(jī)的普及, 手機(jī)配備的各種傳感器可以采集各種信號(hào), 為室內(nèi)定位技術(shù)的研究提供了方便. WiFi 的普及使得很多的室內(nèi)定位研究基于WiFi 信號(hào)進(jìn)行, 但WiFi 信號(hào)受到多徑效應(yīng)的影響, 衰減會(huì)比較快. 在全局空間,WiFi 具有較高的區(qū)分度, 但對(duì)于距離相近的位置點(diǎn), 采集的RSSI 數(shù)據(jù)較為相似, 在局部空間上缺乏唯一性.在室內(nèi)環(huán)境的局部空間, 地磁場(chǎng)具有較高的區(qū)分度, 但在定位空間很大時(shí), 多個(gè)相距較遠(yuǎn)的位置可能具有非常相似的地磁特征, 在全局空間上缺乏唯一性. 因此僅使用WiFi 或地磁場(chǎng)等單一定位源進(jìn)行定位, 都難以達(dá)到較高的精度.

針對(duì)單一定位源存在較大誤差的現(xiàn)象, 多源信息融合定位應(yīng)運(yùn)而生. 目前, 國(guó)內(nèi)外對(duì)于多源信息融合定位方面有較多的研究. Pham 等[8]將WiFi 信號(hào)和視覺(jué)信號(hào)進(jìn)行融合進(jìn)行定位, 文獻(xiàn)[9]融合了WiFi、藍(lán)牙以及光學(xué)傳感器三維坐標(biāo)和磁傳感器旋轉(zhuǎn)屬性來(lái)定位,Shu 等[10]采用雙向粒子濾波過(guò)程融合地磁信號(hào)和WiFi 信號(hào), 余劉勇等[11]采用地磁和慣性導(dǎo)航的聯(lián)合定位. 實(shí)驗(yàn)數(shù)據(jù)表明, 多源信息融合都要比單信號(hào)方法進(jìn)行定位的效果好. 基于WiFi 和地磁場(chǎng)信號(hào)具有一定互補(bǔ)性的特點(diǎn), 本文通過(guò)指紋匹配的方式來(lái)實(shí)現(xiàn)WiFi 和地磁場(chǎng)信號(hào)的融合定位.

指紋匹配定位的離線階段主要完成指紋庫(kù)的構(gòu)建,在線階段則是通過(guò)KNN[12]、WKNN[13]、機(jī)器學(xué)習(xí)[14]、深度學(xué)習(xí)[15]等匹配算法將待定位點(diǎn)與指紋庫(kù)中的指紋進(jìn)行匹配, 然后估計(jì)其位置. 如何解決指紋數(shù)據(jù)和物理坐標(biāo)的映射關(guān)系是需要考慮的首要問(wèn)題. BP 神經(jīng)網(wǎng)絡(luò)因其有較強(qiáng)的非線性映射能力[16], 能建立指紋數(shù)據(jù)和物理坐標(biāo)之間的非線性關(guān)系被廣泛應(yīng)用于定位預(yù)測(cè).但BP 神經(jīng)網(wǎng)絡(luò)因隨機(jī)產(chǎn)生權(quán)值和閾值易出現(xiàn)收斂時(shí)間長(zhǎng), 迭代次數(shù)多, 精度不高等現(xiàn)象[17,18]. 差分進(jìn)化算法是一個(gè)全局優(yōu)化算法, 有收斂速度快、控制參數(shù)少且設(shè)置簡(jiǎn)單、優(yōu)化結(jié)果穩(wěn)健等優(yōu)點(diǎn)[19]. 利用差分進(jìn)化算法的全局搜索能力, 能夠有效改進(jìn)BP 模型的性能.

在BP 神經(jīng)網(wǎng)絡(luò)中, 神經(jīng)網(wǎng)絡(luò)層之間的初始權(quán)值和偏差是隨機(jī)初始化的, 這不僅增加了收斂時(shí)間, 還有陷入局部最優(yōu)的可能性. 因此, 為提高BP 神經(jīng)網(wǎng)絡(luò)的學(xué)習(xí)能力, 充分發(fā)揮其強(qiáng)大的非線性映射能力, 文獻(xiàn)[20]利用DE 差分進(jìn)化算法(differential evolution, DE)來(lái)優(yōu)化BP 神經(jīng)網(wǎng)絡(luò)的參數(shù), 但標(biāo)準(zhǔn)的DE 算法有控制參數(shù)、進(jìn)化策略選擇困難[21]等諸多問(wèn)題. 為了提高差分進(jìn)化算法的優(yōu)化能力, 本文提出了一種改進(jìn)的差分進(jìn)化算法來(lái)優(yōu)化BP 神經(jīng)網(wǎng)絡(luò), 有助于BP 模型更好地學(xué)習(xí)WiFi 和地磁指紋數(shù)據(jù)的特征, 以此來(lái)提高定位精度和網(wǎng)絡(luò)的收斂速度.

2 改進(jìn)的自適應(yīng)差分進(jìn)化算法

DE 算法主要過(guò)程包括種群初始化、變異、交叉和選擇等步驟, 其中變異操作是生成具有較好適合度值的新向量操作, 以獲得更好的搜索能力[22]. 目前最常用的變異策略DE/rand/1[23]操作如式(1)所示:

其中,G為進(jìn)化代數(shù);xr1,G為當(dāng)前個(gè)體;xr2,G,xr3,G分別為第G代種群中隨機(jī)選擇的兩個(gè)不同個(gè)體;F為變異因子. 如圖1 所示, DE/rand/1 在二維參數(shù)空間的突變過(guò)程中, 種群進(jìn)化的搜索方向vi與全局最優(yōu)解(global optimum)方向有較大偏差.

圖1 DE/rand/1 的突變策略過(guò)程圖

2.1 改進(jìn)的變異操作

集體智能(collective intelligence, CI) 是可以為種群進(jìn)化提供更好搜索方向的突變算子, 能引導(dǎo)種群走向一個(gè)更好的搜索區(qū)域, 該算子由混合了部分適應(yīng)性較好的向量和隨機(jī)選擇的向量的集合信息來(lái)生成.vmix_mbest,G是第G代中適應(yīng)度排名最好的m個(gè)向量組成的復(fù)合向量, 本文取m=5, 可表示為:

基于CI 的突變策略可以表示為:

如圖2 所示, 在二維參數(shù)空間上, 基于CI 的突變策略過(guò)程在種群進(jìn)化的搜索方向vmix,G與全局最優(yōu)解方向比較一致, CI 突變算子將引導(dǎo)種群走向一個(gè)更好的搜索區(qū)域.

圖2 基于CI 的突變策略的過(guò)程圖

2.2 自適應(yīng)參數(shù)設(shè)置

DE 算法的變異因子F和交叉概率因子CR(crossover rate) 在整個(gè)種群進(jìn)化過(guò)程中控制著種群多樣性和收斂速度.

當(dāng)進(jìn)化代數(shù)G小時(shí), 較大的F值才能保證個(gè)體的多樣性, 跳出局部極值找到全局最優(yōu)值, 但其收斂速度會(huì)降低; 當(dāng)G變大時(shí), 群體的多樣性需求降低, 較小的F值更易于保持搜索局部最優(yōu)值的穩(wěn)定性. 為此, 本文用改進(jìn)的Logistic 函數(shù)作為自適應(yīng)變異因子F(G), 隨著種群的進(jìn)化, 變異因子F會(huì)慢慢變小, 即:

其中,Fmax和Fmin分別為F的最大值和最小值,a為初始衰減率, 通過(guò)改變a的值可以調(diào)節(jié)F的下降速度.

根據(jù)交叉概率因子的特點(diǎn),CR值越大, 算法局部搜索能力越強(qiáng), 收斂越快;CR值越小, 全局搜索能力越強(qiáng), 有利于保持種群多樣性. 為保持種群前期的多樣性和后期的收斂速度, 利用Sigmoid 函數(shù)作為自適應(yīng)交叉概率因子CR(G), 可以兼顧種群的多樣性和收斂速度, 故:

其中,CRmax和CRmin分別為交叉概率因子的最大和最小邊界,CRmax,CRmin一般取經(jīng)驗(yàn)值分別為0.9, 0.1,β為控制CR增長(zhǎng)速率的參數(shù), 一般取經(jīng)驗(yàn)值5.

3 IDEBP 定位算法

IDEBP 定位算法主要包括離線階段和在線定位階段. 離線階段需要完成指紋庫(kù)的構(gòu)建和IDEBP 模型的訓(xùn)練. 在線定位階段將測(cè)試數(shù)據(jù)集輸入到訓(xùn)練好的模型中, 然后得到最終的定位結(jié)果.

3.1 離線階段

3.1.1 指紋庫(kù)的構(gòu)建

在離線階段首先需要對(duì)定位區(qū)域進(jìn)行網(wǎng)格劃分,然后借助智能手機(jī)采集每個(gè)網(wǎng)格點(diǎn)的RSSI 值、地磁場(chǎng)強(qiáng)度值以及該點(diǎn)對(duì)應(yīng)的物理坐標(biāo)值, 并且將數(shù)據(jù)寫(xiě)入后臺(tái)數(shù)據(jù)庫(kù)中. 每條指紋數(shù)據(jù)的格式如下:

其中,Di,j表示坐標(biāo)為(i,j)位置的指紋數(shù)據(jù),mx,my和mz分別表示該位置上地磁信號(hào)在手機(jī)坐標(biāo)系3 個(gè)坐標(biāo)軸上的分量; {RSSI1,RSSI2,RSSI3,···,RSSIn}表示該位置上掃描到的n個(gè)AP (access point)點(diǎn)的RSSI 值.

指紋庫(kù)D的結(jié)構(gòu)圖如表1 所示, 表中t為指紋點(diǎn)的個(gè)數(shù).

表1 指紋庫(kù)D 的結(jié)構(gòu)表

3.1.2 模型訓(xùn)練

模型訓(xùn)練過(guò)程如下:

(1)本文以n個(gè)AP 在各個(gè)參考點(diǎn)的RSSI 值以及三維的地磁場(chǎng)強(qiáng)度值作為BP 神經(jīng)網(wǎng)絡(luò)的輸入, 以各個(gè)參考點(diǎn)位置的坐標(biāo)(i, j)作為輸出, 中間層為隱含層. 確定神經(jīng)網(wǎng)絡(luò)的結(jié)構(gòu)之后, 對(duì)種群中個(gè)體進(jìn)行編碼, 編碼長(zhǎng)度d=m×l+l×n+l+n, 其中,m、l、n分別是輸入層、隱藏層和輸出層的節(jié)點(diǎn)數(shù)量.

(2)訓(xùn)練集樣本輸入到BP 模型中進(jìn)行訓(xùn)練, 計(jì)算出模型輸出與樣本輸出之間的誤差. 通過(guò)誤差來(lái)計(jì)算種群個(gè)體的適應(yīng)度, 并用適應(yīng)度函數(shù)判斷種群中個(gè)體的優(yōu)劣程度:

其中,x是與BP 神經(jīng)網(wǎng)絡(luò)的權(quán)重和偏差相對(duì)應(yīng)的種群個(gè)體,E(x) 是相應(yīng)的BP 神經(jīng)網(wǎng)絡(luò)輸出的均方誤差.C是一個(gè)常數(shù).

(3)種群中個(gè)體進(jìn)行變異、交叉以及選擇操作之后, 判斷種群進(jìn)化次數(shù)是否滿足種群的最大迭代要求.若滿足要求, 則得到最優(yōu)個(gè)體; 反之, 則更新BP 神經(jīng)網(wǎng)絡(luò)的權(quán)值和偏差.

(4)得到最優(yōu)個(gè)體后, 利用最優(yōu)個(gè)體給BP 神經(jīng)網(wǎng)絡(luò)的權(quán)值和偏差賦值并進(jìn)行BP 神經(jīng)網(wǎng)絡(luò)模型的訓(xùn)練.

3.2 定位階段

將測(cè)試集數(shù)據(jù)歸一化后輸入到訓(xùn)練好的BP 模型中, 模型根據(jù)測(cè)試數(shù)據(jù), 輸出預(yù)測(cè)結(jié)果. 然后將得到的數(shù)據(jù)進(jìn)行反歸一化, 得到最終的定位結(jié)果, 即每個(gè)測(cè)試數(shù)據(jù)所對(duì)應(yīng)的(i,j)坐標(biāo).

4 實(shí)驗(yàn)設(shè)計(jì)與結(jié)果分析

為驗(yàn)證算法的性能, 項(xiàng)目組開(kāi)發(fā)了一套以Android智能手機(jī)為終端的室內(nèi)定位APP, 實(shí)驗(yàn)中, 通過(guò)智能移動(dòng)設(shè)備上的室內(nèi)定位APP 采集數(shù)據(jù). 實(shí)驗(yàn)采集數(shù)據(jù)所用的智能移動(dòng)設(shè)備為紅米K30.

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

實(shí)驗(yàn)環(huán)境選在華南師范大學(xué)計(jì)算機(jī)學(xué)院3 樓空間信息研究中心實(shí)驗(yàn)室, 該實(shí)驗(yàn)室是一個(gè)長(zhǎng)約為23 m, 寬約為8 m 的室內(nèi)空間. 圖3 是實(shí)驗(yàn)環(huán)境的平面圖, 圖4是數(shù)據(jù)采集的實(shí)景圖, 圖5 是實(shí)驗(yàn)應(yīng)用系統(tǒng)圖. 實(shí)驗(yàn)者在實(shí)驗(yàn)場(chǎng)所中劃了11×35 個(gè)網(wǎng)格點(diǎn), 每個(gè)網(wǎng)格點(diǎn)的邊長(zhǎng)為0.6 m, 其中長(zhǎng)方形的小方塊為學(xué)生工位, 小圓點(diǎn)為采集數(shù)據(jù)的網(wǎng)格點(diǎn), 五角星為WiFi 接入點(diǎn), 共有16 個(gè). 除去學(xué)生工位、會(huì)議桌以及墻體等有障礙物的網(wǎng)格點(diǎn)外, 有效的網(wǎng)格點(diǎn)共有283 個(gè). 為保證實(shí)驗(yàn)數(shù)據(jù)的可靠性, 每臺(tái)設(shè)備在每個(gè)網(wǎng)格點(diǎn)上, 以1 s 作為時(shí)間間隔, 采集120 次數(shù)據(jù). 在整個(gè)實(shí)驗(yàn)過(guò)程中, 十幾個(gè)實(shí)驗(yàn)室成員在該區(qū)域內(nèi)正?；顒?dòng)學(xué)習(xí).

圖3 實(shí)驗(yàn)環(huán)境平面圖

圖4 數(shù)據(jù)采集實(shí)景圖

圖5 實(shí)驗(yàn)應(yīng)用系統(tǒng)圖

4.2 IDEBP 定位算法實(shí)驗(yàn)與對(duì)比分析

將訓(xùn)練集數(shù)據(jù)輸入到程序中進(jìn)行訓(xùn)練, 訓(xùn)練結(jié)束得到BP 神經(jīng)網(wǎng)絡(luò)和IDEBP 模型的訓(xùn)練誤差曲線分別如圖6 和圖7 所示. 圖中橫坐標(biāo)表示訓(xùn)練次數(shù), 縱坐標(biāo)表示訓(xùn)練誤差. 從圖6 可以看出, BP 神經(jīng)網(wǎng)絡(luò)在100 步時(shí)訓(xùn)練誤差仍然大于0.1, 且整體的迭代誤差下降速度慢. 這是因?yàn)锽P 神經(jīng)網(wǎng)絡(luò)存在迭代次數(shù)多, 訓(xùn)練時(shí)間長(zhǎng), 誤差精度大等問(wèn)題. 從圖7 中可以看出, IDEBP 神經(jīng)網(wǎng)絡(luò)在第28 次迭代時(shí)就已經(jīng)到達(dá)了所設(shè)定的目標(biāo)誤差, 即0.001. 由上可知, 差分進(jìn)化算法優(yōu)化BP 神經(jīng)網(wǎng)絡(luò)的算法在一定程度上可以改進(jìn)傳統(tǒng)BP 算法收斂時(shí)間長(zhǎng), 迭代次數(shù)多, 精度不高等缺點(diǎn).

圖6 BP 神經(jīng)網(wǎng)絡(luò)訓(xùn)練誤差曲線

圖7 IDEBP 神經(jīng)網(wǎng)絡(luò)訓(xùn)練誤差曲線

針對(duì)BP 神經(jīng)網(wǎng)絡(luò)隨機(jī)初始化權(quán)值和閾值易出現(xiàn)收斂時(shí)間長(zhǎng), 迭代次數(shù)多等問(wèn)題, 文獻(xiàn)[24] 提出了GABP (genetic algorithm BP)算法, 文獻(xiàn)[25] 提出了DEBP (differential evolution BP)算法對(duì)BP 神經(jīng)網(wǎng)絡(luò)進(jìn)行優(yōu)化. 圖8 對(duì)GABP 算法, DEBP 算法和IDEBP算法中種群適應(yīng)度曲線隨著迭代次數(shù)增加的變化情況進(jìn)行了比較. 圖中橫坐標(biāo)表示迭代次數(shù), 縱坐標(biāo)表示種群適應(yīng)度. 由圖可知, GABP 算法和DEBP 算法分別在第43 次和第33 次迭代中趨于穩(wěn)定, 而IDEBP 算法在第28 次迭代中就能趨于穩(wěn)定, 算法加快了種群的收斂速度. 同時(shí)GABP 算法和DEBP 算法的適應(yīng)度水平分別約為0.34 和0.38, IDEBP 約為0.44, 而較高的適應(yīng)度水平可以找到更好的權(quán)重和偏差.

圖8 優(yōu)化的BP 神經(jīng)網(wǎng)絡(luò)適應(yīng)度圖

圖9 比較了BP 算法[26]、GABP 算法、DEBP 算法和IDEBP 算法的定位誤差累積分布曲線. 由圖可知,因?yàn)镮DE 算法較強(qiáng)的全局搜索能力可以優(yōu)化BP 神經(jīng)網(wǎng)絡(luò)的初始權(quán)值和偏差, 所以IDEBP 算法具有最優(yōu)的定位效果, DEBP 算法的定位效果次之, GABP 算法與BP 算法的定位精度依次排在其后面.

圖9 定位誤差百分比圖

考慮上述4 種定位算法的平均定位誤差和最大最小誤差, 如表2 所示, IDEBP 算法平均誤差為1.14 m,相對(duì)于其他定位算法的定位精度分別提高了1.88 m,0.92 m, 0.55 m.

表2 不同模型的定位性能比較 (m)

5 結(jié)論

針對(duì)標(biāo)準(zhǔn)的DE 算法進(jìn)化策略、控制參數(shù)選擇困難等諸多問(wèn)題, 本文改進(jìn)了差分進(jìn)化算法, 并與BP 神經(jīng)網(wǎng)絡(luò)相結(jié)合, 克服了BP 神經(jīng)網(wǎng)絡(luò)迭代次數(shù)多, 訓(xùn)練時(shí)間長(zhǎng), 誤差精度大等缺點(diǎn), 提出了應(yīng)用于WiFi 和地磁場(chǎng)的聯(lián)合指紋定位的IDEBP 算法. 實(shí)驗(yàn)結(jié)果表明,IDEBP 算法可以有效地提高指紋定位的精度, 加快神經(jīng)網(wǎng)絡(luò)的收斂速度.