周世悅, 張 靜

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

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

周世悅, 張 靜*

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

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

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

0 引 言

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

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

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

1 ELM模型

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

(1)

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

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

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

(2)

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

(3)

公式(3)可以寫成:

Hβ=T,

(4)

式中

(5)

(6)

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

(7)

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

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

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

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

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

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

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

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

(8)

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

(9)

(10)

(11)

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

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

后文將通過(guò)實(shí)驗(yàn)驗(yàn)證3種權(quán)重計(jì)算方式對(duì)定位精度的影響.

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

3 實(shí)驗(yàn)驗(yàn)證部分

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

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

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

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

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

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

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

綜合上述的實(shí)驗(yàn),能夠看到所提出的W-ELM對(duì)定位精度的提升有明顯的效果.

4 結(jié) 論

針對(duì)室內(nèi)基于Wi-Fi的定位方法精度不高的問(wèn)題,提出了基于加權(quán)急速學(xué)習(xí)機(jī)W-ELM的定位方法,在ELM方法模型的基礎(chǔ)上,加入了近鄰加權(quán)求和的方法,有效提高了定位精度.實(shí)驗(yàn)證明該方法能夠達(dá)到誤差在3 m以內(nèi)85%的定位精度.該研究工作下一步將繼續(xù)Wi-Fi室內(nèi)定位AP位置無(wú)關(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-),女,碩士研究生,主要從事無(wú)線通信與自適應(yīng)信號(hào)處理方面的研究.E-mail:zhoushiyue1122@163.com

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

TN 929.5

A

1000-5137(2017)02-0206-07

*通信作者