基于加權(quán)極速學(xué)習(xí)機室內(nèi)高動態(tài)環(huán)境的定位算法

周世悅, 張 靜

(上海師范大學(xué) 信息與機電工程學(xué)院,上海 200234)

基于加權(quán)極速學(xué)習(xí)機室內(nèi)高動態(tài)環(huán)境的定位算法

周世悅, 張 靜*

(上海師范大學(xué) 信息與機電工程學(xué)院,上海 200234)

隨著人們對室內(nèi)基于位置服務(wù)的需求越來越大,室內(nèi)定位的研究變得越來越重要.Wi-Fi由于其傳輸距離適中,在智慧城市發(fā)展的推動下,熱點的覆蓋也非常多.因此基于Wi-Fi的定位技術(shù)成為眾多室內(nèi)定位技術(shù)中最具有可行性的.面對室內(nèi)無線環(huán)境高動態(tài)變化的情況,提出了基于加權(quán)極速學(xué)習(xí)機(W-ELM)的定位方法,實驗證明該方法能夠有效提高定位精度.

室內(nèi)定位; 高動態(tài)環(huán)境; 加權(quán)極速學(xué)習(xí)機

0 引 言

定位服務(wù)(LBS)[1],是指通過移動終端和移動網(wǎng)絡(luò)的配合,確定移動用戶的實際地理位置,從而提供用戶所需位置相關(guān)信息的一種移動通信與導(dǎo)航融合的服務(wù)形式.目前,海量LBS都依賴于室內(nèi)位置信息,由于其重要性,近些年來出現(xiàn)很多室內(nèi)定位方案,包括:AGPS定位[2]、移動通信基站定位[3]、超聲波定位[4]、藍(lán)牙定位[5]、Wi-Fi定位[6-8]、紅外線定位[9]等.這些系統(tǒng)在應(yīng)用中都存在一定的應(yīng)用范圍與局限.如AGPS需要對基礎(chǔ)設(shè)施進(jìn)行大量改造,基站定位的精度比較有限,藍(lán)牙的探測范圍較小,需要大量布點才能滿足需求,方案成本太高;超聲波與紅外線方式易受介質(zhì)遮擋.Wi-Fi信號的有效傳播距離為100 m左右,對于室內(nèi)定位距離適中,另外,近年來在“無線城市”理念的推動下,各個城市無線接入點(AP)的覆蓋率日益增加,此外帶有Wi-Fi模塊設(shè)備的持有率也逐漸增加.因此在高無線熱點覆蓋率和Wi-Fi設(shè)備持有率的情況下,基于Wi-Fi的定位最具有可行性.

基于Wi-Fi的定位方法有兩種:1)基于信號傳播模型.根據(jù)信號的強度隨著與信號源的距離增加而衰減的特征,學(xué)習(xí)衰減模型,從而通過把信號強度映射為距離,再用交圓法等進(jìn)行定位;2)基于指紋的定位方法.通過將終端設(shè)備搜索到的周圍環(huán)境中Wi-Fi的信號強度與位置對應(yīng)綁定形成指紋庫,在定位階段將接收到的信號強度與指紋庫進(jìn)行對比計算,相似度最高的位置即為定位結(jié)果.兩種方法中,基于信號傳播的模型因為受到環(huán)境的干擾,得到的距離往往不準(zhǔn)確,造成定位的誤差較大.基于指紋的方法不需要知道AP的位置,并且不通過傳播模型計算距離,而是直接將信號作為指紋特征進(jìn)行比對,因此有較好的普適性以及抗干擾性,是目前普遍采用的定位方法.

基于指紋模型的定位方法是通過信號特征與位置的非線性映射關(guān)系來進(jìn)行定位,因此眾多的機器學(xué)習(xí)方法可以被利用來訓(xùn)練分類器,利用不同AP的信號強度作為輸入數(shù)據(jù),通過模型后的輸出作為位置估計.已經(jīng)有大量的機器學(xué)習(xí)的模型被用于定位中,例如:最近鄰[10]、決策樹[11]、貝葉斯[12]、神經(jīng)網(wǎng)絡(luò)[13],以及今年來非常熱門的極速學(xué)習(xí)機(ELM)[14].在所有上述算法中,ELM由于其模型簡單,并且在離線和在線階段都有很快的學(xué)習(xí)速度,因此得到越來越廣泛的應(yīng)用.

1 ELM模型

ELM是由Huang等[14]在2006年提出的,它是一個單隱層前饋網(wǎng)絡(luò),屬于神經(jīng)網(wǎng)絡(luò)的一種,其優(yōu)勢在于模型的學(xué)習(xí)不需要迭代過程.在給定N個訓(xùn)練數(shù)據(jù)(xi,ti)∈Rn×Rm,i=1,2,…,N.這里xi是一個n×1輸入向量xi=[xi1,xi2,…,xin]T,ti是一個m×1目標(biāo)向量ti=[ti1,ti2,…,tim]T.ELM網(wǎng)絡(luò)有一個隱層,里面有L個隱結(jié)點,如圖1所示.具有L隱結(jié)點的網(wǎng)絡(luò)輸出為:

(1)

圖1 ELM模型網(wǎng)絡(luò)

這里的ai表示特征層到隱層的轉(zhuǎn)移權(quán)重,bi表示隱層上第i個隱結(jié)點的偏移量,βi表示第i個隱結(jié)點到輸出層的轉(zhuǎn)移權(quán)重.G(ai,bi,x)則是第i個隱結(jié)點的輸出值,其中已經(jīng)包含了來自特征層的信息.當(dāng)隱層的映射函數(shù)g(x):R→R(例如:sigmoid 和 threshold),G(ai,bi,x)給定后,則隱層的輸出可以表示為:

G(ai,bi,x)=g(ai·x+bi),bi∈R.

(2)

如果一個有L個隱結(jié)點的單隱層前饋網(wǎng)絡(luò)能夠?qū)條數(shù)據(jù)實現(xiàn)完全擬合,則存在βi,ai和bi滿足

(3)

公式(3)可以寫成:

Hβ=T,

(4)

式中

(5)

(6)

根據(jù)[15]可知,ELM模型中的隱層結(jié)點個數(shù)L以及ai和bi(輸入權(quán)重和隱層節(jié)點偏移量)不需要迭代計算,而直接隨機生成即可.上述線性系統(tǒng)的最小二乘解如下:

(7)

式中H?是H的Moore-Penrose廣義逆[16-17].因此有很多方法可以被用來求解該逆矩陣,比如正投影法,正交投影法,迭代求解方法,奇異值分解法(SVD)[17]等.其中正交投影法在兩種情況下可以使用[17]:當(dāng)HTH是非奇異的,并且H?=(HTH)-1HT,或者H?=HT(HHT)-1.

2 基于加權(quán)ELM(W-ELM)的定位方法

上述模型中,在分類模型中,是根據(jù)輸出層矩陣T來判斷類別.T是一個N×m的矩陣,其中N表示數(shù)據(jù)的條數(shù),m表示類別數(shù),因此,對每一條獨立的特征向量,經(jīng)過ELM網(wǎng)絡(luò)后在輸出層有一個1×m的向量對應(yīng),該向量中最大的數(shù)值對應(yīng)的類別即為最后的分類結(jié)果.

針對定位的問題,通過網(wǎng)格法構(gòu)造指紋庫模型的時候,例如將要定位的區(qū)域按照一定的大小劃分為m個小格子,在每個網(wǎng)格的中心點采集信號強度,形成一條指紋數(shù)據(jù){(xm,ym)～(rssi1,rssi2,…,rssin)}.在在線階段,通過ELM模型的輸出,選擇輸出值最大的所對應(yīng)的網(wǎng)格中心點即為定位的結(jié)果,從而造成定位的誤差.如圖2所示,(a)是原始ELM方法,在輸出層取單個輸出結(jié)點的方法,假定被定位的用戶所在的位置在紅色點上,定位結(jié)果就會被映射到p1;(b)是加權(quán)ELM方法,選定了最近的K個備選位置(K=4),通過這4個備選位置以及相應(yīng)的權(quán)重來插值得到,這種方法得到的定位精度會相對更高.

圖2 (a)原始ELM方法;(b)加權(quán)ELM方法

針對這個問題,引入基于近鄰加權(quán)的方法,提出基于加權(quán)ELM的定位模型,在原來ELM模型的三層基礎(chǔ)上加入兩層:近鄰點層和最終的結(jié)果層.如圖3所示.

圖3 W-ELM網(wǎng)絡(luò)結(jié)構(gòu)

由ELM的原輸出層到近鄰點層需要通過輸出點的值來排序篩選,選中其中輸出點值最大的K個點,在通過加權(quán)的方法來得到最終的結(jié)果,其中加權(quán)方法如下:

(8)

在本模型中,相似度是通過ELM模型的計算得到的,而且輸出結(jié)點的值越大,表示相似度越高,因此按照相似度來給予不用的輸出點相應(yīng)的權(quán)重,這里的輸出結(jié)點的值用ti表示,則有幾種構(gòu)造權(quán)重的方法:

(9)

(10)

(11)

權(quán)重的構(gòu)造方式有兩個基本原則:1)保證權(quán)重的和為1,這一點稱作歸一化原則;2)要具有物理可解釋性.上述第一種權(quán)重計算表示所有的備選鄰居點權(quán)值一樣,平等對待.而后兩種構(gòu)造方式表示在輸出結(jié)點值ti取值較大的時候,權(quán)值相應(yīng)較大.

(10)式的權(quán)重計算是一種倒數(shù)權(quán)重,仍然滿足了ti取值大時權(quán)重大的要求,且權(quán)值之和為1的要求,但是倒數(shù)的權(quán)重計算會使得在ti增大的過程中,相應(yīng)的權(quán)重增加速度減緩.公式(11)的權(quán)重計算是一種高次權(quán)重,是對輸出結(jié)點值ti的二次方歸一化,即將所有輸出結(jié)點值ti先各自求二次方,然后再進(jìn)行歸一化.也滿足ti取值大時權(quán)重大的要求,且權(quán)值之和為1.但是高次權(quán)重會是的ti增大的過程中,相應(yīng)的權(quán)重增加速度增快.圖4形象地表示了上述結(jié)論.

后文將通過實驗驗證3種權(quán)重計算方式對定位精度的影響.

圖4 輸出結(jié)點值和權(quán)重的關(guān)系

3 實驗驗證部分

本文作者提出了基于加權(quán)ELM的定位算法,是基于Wi-Fi指紋定位方法的一種.為了驗證方法的有效性以及與同類其他方法的優(yōu)勢,在上海師范大學(xué)香樟苑的四樓選擇了2個辦公室環(huán)境對算法進(jìn)行測試.實驗場地如圖5所示.將場地按照邊長為2 m的正方形網(wǎng)格進(jìn)行劃分,在每一個網(wǎng)格的中心點面向四個方向各采集若干條指紋數(shù)據(jù)形成指紋庫,然后讓用戶在房間里任意一些位置停留并采集一些數(shù)據(jù)形成測試數(shù)據(jù)集.下面將通過實驗來確定加權(quán)的鄰居數(shù)K以及W-ELM方法對定位精度的所帶來的影響.

圖5 兩個定位精度測試環(huán)境:(a) 402房間; (b) 412房間

選擇了環(huán)境中最穩(wěn)定的15個AP作為特征維來進(jìn)行試驗,對信號缺失值用-95 dBm,即該空間中能夠搜索到的信號最低值作為補充.

在確定了鄰居數(shù)目后,進(jìn)一步驗證所提出方法的有效性,對比ELM以及W-ELM方法,并且對比3種不同的權(quán)重計算公式.實驗的定位精度如圖7所示.

圖6 鄰居數(shù)對定位精度的影響

圖7 4種定位方法的定位精度對比:(a)402房間;(b)412房間

從圖7能夠明顯的看到,3種權(quán)重計算方式得到的定位精度均比ELM定位方法有所提升,W-ELM中權(quán)重計算方法1((9)式)和方法2((10)式)定位結(jié)果相差不多,在402房間,相對于ELM方法,有差不多5%的提升,在412房間有近10%的提升.

綜合上述的實驗,能夠看到所提出的W-ELM對定位精度的提升有明顯的效果.

4 結(jié) 論

針對室內(nèi)基于Wi-Fi的定位方法精度不高的問題,提出了基于加權(quán)急速學(xué)習(xí)機W-ELM的定位方法,在ELM方法模型的基礎(chǔ)上,加入了近鄰加權(quán)求和的方法,有效提高了定位精度.實驗證明該方法能夠達(dá)到誤差在3 m以內(nèi)85%的定位精度.該研究工作下一步將繼續(xù)Wi-Fi室內(nèi)定位AP位置無關(guān)性的研究,進(jìn)一步提高定位精度.

[1] Park M H,Kim H C,Lee S J.Implementation results andservice examples of GPS-Tag for indoor LBS and message service [C].15th international conference on advanced communicationtechnology (ICACT).PyeongChang:IEEE,2013.

[2] Ma Y.Research and Optimization of assisted global positioning system in smart-phone [D].Beijing:Beijing University of Posts and Telecommunications,2008.

[3] Wang J H.Research on location techniques based on information fusion [D].Zhengzhou:PLA Information Engineering University,2011.

[4] Kim S J,Kim B K.Dynamic ultrasonic hybrid localization system for indoor mobile robots [C].Industrial Electronics,IEEE Transactions on,2013,60(10):4562-4573.

[5] Chung J,Donahoe M,Schmandt C,et al.Indoor location sensing using geo-magnetism [C].Proceedings of the 9th international conference on Mobile systems applications and services,New York:ACM Press,2011.

[6] Liu H,Darabi H,Banerjee P,Liu J.Survey of wirelessindoor positioning techniques and systems [J].IEEE Transactions on Systems Man and Cybernetics,2007,37(6):1067-1080.

[8] Brunato M,Battiti R.Statistical learning theory for locationfingerprinting in wireless LANs [J].Computer Networks,2005,47(6):825-845.

[9] Lu Q,Shu G H.An indoor orientation system based on singlechips [J].Micro Processors,2006(2):66-71.

[10] Bahl P P.RADAR:an in-building RF-baseduser location and tracking system [C].Proceeding of INFOCOM2000,Tel Aviv:IEEE,2000.

[11] Yim J.Introducing a decision tree-based indoor positioning technique [J].Expert Systems with Applications,2008,34(2):1296-1302.

[12] Ito S,Kawaguchi N.Bayesian based location estimationsystem using wireless LAN [C].PerCom 2005 workshops,Kauai Island:IEEE,2005.

[13] Ahmad U,Nasir U,Iqbal M.In-building localization usingneural networks [C].IEEE International Conference on Engineering of Intelligent Systems,Islamabad:IEEE Press,2006.

[14] Huang G B,Zhu Q Y,Siew C K.Extreme learning machine:A new learning scheme of feedforward neural networks [C].2004 International Joint Conference on Neural Networks (IJCNN′2004),Budapest:IEEE,2004.

[15] Chandra R,Mahajan R,Moscibroda T.A case for adapting channel width in wireless networks [C].Proceedings of the ACM SIGCOMM 2008 Conference on Data Communication,New York:ACM Press,2008.

[16] Serre D.Matrices:Theory and applications [M].New York:Springer Verlag,2002.

[17] Rao C R,Mitra S K.Generalized inverse of matrices and its applications [M].New York:Wiley,1971.

(責(zé)任編輯：包震宇)

Indoor localization algorithm in high dynamic environmentbased on W-ELM

Zhou Shiyue, Zhang Jing*

(College of Information,Mechanical and Electrical Engineering,Shanghai Normal University,Shanghai 200234,China)

With increasing needs of people on the indoor location-based services,indoor localization research becomes more and more important.With the developing of smart city,Wi-Fi is getting more popular than before because of its moderate transmission distance.Thus,Wi-Fi based location method is the most feasible technology among many other types of indoor location methods.For the problem of signal changes dynamically in indoor environment,we proposed a weighted extreme learning machine(W-ELM)-based indoor localization algorithm to build a stable model,and experiment results show that this method can effectively improve the positioning accuracy.

indoor localization; high dynamic environment; weighted extreme learning machine

2015-09-12

周世悅(1990-),女,碩士研究生,主要從事無線通信與自適應(yīng)信號處理方面的研究.E-mail:zhoushiyue1122@163.com

導(dǎo)師簡介: 張 靜(1971-),女,副教授,主要從事移動通信信號處理方面的研究.E-mail:jannety@shnu.edu.cn

TN 929.5

A

1000-5137(2017)02-0206-07

*通信作者