基于PCOS-ELM的室內(nèi)指紋定位算法*

朱順濤， 盧先領(lǐng)

(江南大學(xué) 物聯(lián)網(wǎng)工程學(xué)院，江蘇 無錫 214122)

0 引 言

近年來，隨著無線局域網(wǎng)(wireless local area network,WLAN)的廣泛部署以及人們對(duì)于室內(nèi)位置服務(wù)的需求與日俱增，WLAN室內(nèi)定位技術(shù)引起了國內(nèi)外學(xué)者的廣泛關(guān)注[1,2]。根據(jù)定位原理的不同，WLAN室內(nèi)定位技術(shù)可分為以下3類：最近接入點(diǎn)(access point,AP)定位、幾何計(jì)算定位和位置指紋定位[3]。其中，位置指紋定位法憑借定位精度較高、對(duì)環(huán)境及設(shè)備要求低等優(yōu)點(diǎn)，目前已經(jīng)成為室內(nèi)定位技術(shù)中的研究熱點(diǎn)[4]。文獻(xiàn)[5]提出了基于極限學(xué)習(xí)機(jī)(extreme learning machine, ELM)的指紋定位算法，大幅減少了離線階段的訓(xùn)練時(shí)間。文獻(xiàn)[6]在ELM中引入了二次錐規(guī)劃提高定位算法的抗噪能力，缺點(diǎn)是未考慮室內(nèi)環(huán)境的變化；文獻(xiàn)[7]對(duì)ELM中的隱含層節(jié)點(diǎn)進(jìn)行增量式添加，但由于隱含層節(jié)點(diǎn)參數(shù)隨機(jī)分配，定位精度提高不明顯。文獻(xiàn)[8]提出了一種混沌優(yōu)化的極限學(xué)習(xí)機(jī)(chaos extreme learning machine，CELM)算法，利用復(fù)合混沌優(yōu)化和混沌尺度變化算法優(yōu)化ELM的隱含層參數(shù)，提高了ELM的泛化性能，但CELM算法容易陷入局部最優(yōu)，導(dǎo)致定位精度下降。

本文針對(duì)現(xiàn)有室內(nèi)指紋定位算法在定位精度和對(duì)環(huán)境適應(yīng)性這兩方面缺乏綜合考慮的問題，提出了一種基于并行混沌優(yōu)化的在線連續(xù)極限學(xué)習(xí)機(jī)(parallel chaos online sequential-ELM，PCOS-ELM)的定位算法。通過對(duì)傳統(tǒng)混沌優(yōu)化二次載波部分進(jìn)行并行化搜索，避免了在處理高維化問題時(shí)陷入局部最優(yōu)；通過分塊矩陣的運(yùn)算法則對(duì)初始化定位模型進(jìn)行在線連續(xù)學(xué)習(xí)，提高了算法對(duì)動(dòng)態(tài)環(huán)境的適應(yīng)性能。

1 CELM定位算法

設(shè)有N個(gè)位置指紋數(shù)據(jù){(xj,tj)}j=1,2,…,N，隱含層節(jié)點(diǎn)個(gè)數(shù)為L，基于ELM的位置估計(jì)模型如下

(1)

式中w為輸入權(quán)值,b為隱含層節(jié)點(diǎn)閾值,g(·)為激活函數(shù),β為隱含層節(jié)點(diǎn)的輸出權(quán)值。式(1)可以寫成矩陣向量形式

Hβ=T

(2)

(3)

T=[t1,t2,…,tN]T,β=[β1,β2,…,βL]T

(4)

因此，訓(xùn)練ELM定位模型即計(jì)算式(2)中隱含層輸出權(quán)值矩陣β

β=H-1T

(5)

CELM定位算法在ELM基礎(chǔ)上，對(duì)隱含層節(jié)點(diǎn)參數(shù)進(jìn)行組合優(yōu)化，使得殘留誤差E最小，即

(6)

式中Y為優(yōu)化后的隱含層節(jié)點(diǎn)參數(shù)，包含輸入權(quán)值w和隱含層節(jié)點(diǎn)閾值b;oj為算法對(duì)第j個(gè)訓(xùn)練數(shù)據(jù)的輸出值。

CELM定位算法主要分為以下3部分：

1)一次載波搜索

采用載波方式將混沌變量引入優(yōu)化變量，將混沌運(yùn)動(dòng)的遍歷范圍映射到優(yōu)化變量的取值范圍[9]

(7)

minE(Yi),ai≤Yi≤bi

(8)

(9)

2)二次載波搜索

在經(jīng)過M次一次載波搜索后，若E*保持不變，則按式(10)進(jìn)行二次載波

(10)

3)計(jì)算CELM算法的輸出權(quán)值和誤差

(11)

(12)

若EL小于期望輸出誤差η，停止循環(huán)；否則，L=L+1，轉(zhuǎn)至一次載波部分循環(huán)搜索。

2 改進(jìn)的CELM定位算法

提出的PCOS-ELM定位算法在CELM算法基礎(chǔ)上，引入了并行混沌優(yōu)化和在線連續(xù)學(xué)習(xí)方法，旨在解決以下2個(gè)問題：1)CELM算法在求解最優(yōu)隱含層節(jié)點(diǎn)參數(shù)時(shí)容易陷入局部最優(yōu)，導(dǎo)致定位精度受到影響；2)基于CELM的定位算法對(duì)動(dòng)態(tài)環(huán)境的適應(yīng)性較差。

2.1 PCOS

對(duì)CELM二次載波部分進(jìn)行并行分類討論，確保優(yōu)化變量不會(huì)全部陷入局部最優(yōu)。

在加入并行混沌優(yōu)化方法后，式(10)的表現(xiàn)形式為

(13)

(14)

式中n為隱含層節(jié)點(diǎn)個(gè)數(shù);p為優(yōu)化變量的個(gè)數(shù)。優(yōu)化后變量的搜索范圍表示為

(15)

2.2 在線連續(xù)學(xué)習(xí)

與傳統(tǒng)CELM算法相比，PCOS-ELM定位算法對(duì)隱含層輸出權(quán)值矩陣β進(jìn)行矩陣分解，使得新增的在線校準(zhǔn)數(shù)據(jù)能夠?qū)Τ跏嘉恢霉烙?jì)模型進(jìn)行動(dòng)態(tài)調(diào)整，從而完成在線學(xué)習(xí)的功能。

(16)

(17)

(18)

則β(1)可寫為

(19)

(20)

從式(20)可以看出，該算法中當(dāng)添加新指紋數(shù)據(jù)時(shí)，不需要將原始訓(xùn)練數(shù)據(jù)重新納入計(jì)算，從而大幅減輕了計(jì)算量，同時(shí)利用新增的樣本信息對(duì)訓(xùn)練模型進(jìn)行修正，提高了對(duì)環(huán)境的適應(yīng)性。

基于PCOS-ELM的指紋定位算法具體步驟如下：

1)給定一個(gè)指紋訓(xùn)練數(shù)據(jù)集，設(shè)置初始化PCOS-ELM算法的隱含層節(jié)點(diǎn)個(gè)數(shù)L=0，最大迭代次數(shù)K=p×M，p為優(yōu)化變量個(gè)數(shù)，M為搜索步數(shù)。

2)對(duì)隱含層節(jié)點(diǎn)個(gè)數(shù)進(jìn)行增量添加，L=L+1，并通過PCOS算法求取隱含層節(jié)點(diǎn)參數(shù)最優(yōu)解。

c.根據(jù)式(11)、式(12)計(jì)算隱含層輸出權(quán)值和誤差。若輸出誤差EL小于期望誤差η，則完成初始化定位模型的構(gòu)建并轉(zhuǎn)至步驟(3)；否則，則轉(zhuǎn)至步驟(2)繼續(xù)進(jìn)行隱含層節(jié)點(diǎn)增量添加，并對(duì)隱含層參數(shù)的進(jìn)行優(yōu)化搜索。

3)在線階段將新采集到的指紋數(shù)據(jù)塊添加到初始化定位模型之中，得到最新的隱含層輸出矩陣Hk+1。

4)根據(jù)式(20)，利用新增位置指紋數(shù)據(jù)對(duì)定位模型進(jìn)行動(dòng)態(tài)調(diào)整。

5) 將測試數(shù)據(jù)輸入到調(diào)整后的模型中，得出估計(jì)的位置坐標(biāo)。

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

本文位置指紋數(shù)據(jù)的采集點(diǎn)位于江南大學(xué)物聯(lián)網(wǎng)學(xué)院5樓，實(shí)驗(yàn)的覆蓋范圍為20 m×15 m的室內(nèi)環(huán)境，AP節(jié)點(diǎn)采用TL-WR885N，移動(dòng)設(shè)備采用華為P6手機(jī)。指紋數(shù)據(jù)庫中的數(shù)據(jù)信號(hào)強(qiáng)度如表1。

表1 部分指紋數(shù)據(jù) dBm

對(duì)于PCOS-ELM算法，迭代次數(shù)K為影響算法性能重要參數(shù)之一。如圖1所示由各算法迭代次數(shù)與定位誤差關(guān)系知：ELM和CELM算法的定位誤差在初始階段波動(dòng)較大，在加入PCOS算法后，實(shí)驗(yàn)結(jié)果不再隨著代次數(shù)的增加而大幅振蕩。另外，PCOS-ELM算法在迭代50次左右時(shí)，定位誤差趨于穩(wěn)定。相比ELM算法和CELM算法，定位誤差降低了34 %和23 %。

圖1 各算法迭代次數(shù)與定位誤差關(guān)系

圖2為各算法迭代次數(shù)與訓(xùn)練時(shí)間關(guān)系，可以看出：ELM算法所需訓(xùn)練時(shí)間最長，而PCOS-ELM算法的訓(xùn)練時(shí)間與CELM算法類似。當(dāng)?shù)螖?shù)為50左右，即PCOS-ELM定位誤差收斂時(shí)，所需時(shí)間為1.8 s，滿足實(shí)際定位的需要。

圖2 各算法迭代次數(shù)與訓(xùn)練時(shí)間關(guān)系

本實(shí)驗(yàn)中算法并行混沌搜索的最大迭代次數(shù)K置為50。各算法的誤差累積分布概如圖3所示，可以看出：定位誤差在1.5 m范圍內(nèi)，ELM和CELM算法誤差累積分布概率僅為63 %和54 %，PCOS-ELM算法的誤差累計(jì)分布概率達(dá)到81 %，有效提高了定位精度。

圖3 各算法的誤差累積分布概率

為了驗(yàn)證PCOS-ELM定位算法對(duì)環(huán)境的適應(yīng)性能，本文在不同時(shí)間段內(nèi)采集100個(gè)在線校準(zhǔn)數(shù)據(jù)，對(duì)模型進(jìn)行在線動(dòng)態(tài)調(diào)整。由圖4可知ELM隨著新的指紋數(shù)據(jù)的加入，定位精度下降最為迅速，而CELM的精度也有著較大程度的下降。只有本文提出的PCOS-ELM算法，由于添加了在線連續(xù)學(xué)習(xí)功能，定位誤差保持在1.75 m左右，相比初始階段最終的定位誤差僅下降了4.52 %。因此，與傳統(tǒng)的批量學(xué)習(xí)算法相比，基于PCOS-ELM的室內(nèi)指紋定位算法對(duì)動(dòng)態(tài)環(huán)境的適應(yīng)能力有著顯著提高。

圖4 不同時(shí)間段內(nèi)算法定位誤差變化

4 結(jié) 論

提出了基于PCOS-ELM的室內(nèi)指紋定位算法，在傳統(tǒng)CELM算法基礎(chǔ)上，通過并行混沌優(yōu)化和在線連續(xù)學(xué)習(xí)的方法，解決了傳統(tǒng)指紋定位算法定位精度低以及對(duì)環(huán)境動(dòng)態(tài)調(diào)整能力弱的問題。從實(shí)驗(yàn)仿真結(jié)果可以看出，算法的定位精度及對(duì)不同時(shí)間段內(nèi)環(huán)境的適應(yīng)性明顯提高。