室內多用戶在線協同指紋定位算法

許遠航,張鑫宇,樂燕芬

(上海理工大學 光電信息與計算機工程學院,上海 200093)

0 引 言

隨著移動互聯網和智能終端的蓬勃發展,近年來位置服務(Location-Based Services,LBSs)具有的巨大社會和商業價值引起了國內外學者廣泛的關注[1].衛星信號在復雜的室內環境中接收較弱,使得在室外開放環境中表現良好的全球定位系統(Global Positioning System,GPS)在室內環境中定位誤差較大甚至失效[2].為了獲得準確的室內定位以便提供位置相關的各類服務,近些年來,基于RFID[3]、UWB[4]、光、磁、藍牙[5]、Wi-Fi[6,7]等不同類型可用信號的室內定位技術受到深入研究.其中Wi-Fi指紋識別技術由于其易部署性而成為研究熱點.

Wi-Fi指紋定位通常包括兩個階段:離線階段和在線階段[8].離線階段在室內環境中根據期望的定位精度設置參考點(Reference Point,RP),遍歷該定位區域,構建一個包含不同RP上各接入點(Access Point,AP)接收信號強度指示(Received Signal Strength Indicator,RSSI)的指紋數據庫,即記錄每個RP的位置以及相應的RSSI信號向量.在線階段,為獲取某目標的位置,根據目標實時獲得的RSSI向量值,利用匹配算法與數據庫中存儲的指紋數據進行比較,從而獲取估計位置.

傳統的Wi-Fi指紋定位通常是基于用戶觀測的RSSI信號向量,通過離線訓練的機器學習算法完成用戶位置估計,如:加權K近鄰(Weight K-Nearest Neighbor,WKNN)算法[9]、神經網絡[10,11]、支持向量機[12]、隨機森林[13]等.而動態室內環境中RSSI測量噪聲和瞬態噪聲會導致較大的定位誤差[14].一些研究者融合不同的信號源或不同的定位技術進行融合定位,通過增加額外的定位信息來提高定位精度[15,16].如C-SLAM-RF系統[17]利用室內環境中AP的RSSI信號,并進一步結合來自智能手機的行人航位推算(Pedestrian Dead Reckoning,PDR)系統的運動特征來提高系統的定位精度.MPiLoc系統[18]將傳感器與被RSSI標識的步行軌跡進行聚類和合并,以構建室內環境中用無線信號強度標識的步行路徑圖.這類基于運動輔助定位的基本思想是利用慣性傳感器改進路徑估計,以實現更高的定位精度.值得注意的是,慣性傳感器存在固有偏差引起的測量噪聲,會導致定位誤差隨著行走距離的增加而累積.

上述基于融合的定位系統中用戶均以一種獨立的狀態估計目標位置,也就是說,系統基于目標對其周圍環境的觀察進行定位,而未考慮環境中請求定位服務的其他目標的觀察.由于RSSI信號的強波動性,使得基于用戶獨立觀察的估計不可避免存在誤差,甚至兩個物理位置上相近的目標可能有明顯不同的估計位置.因此,近年來也有不少學者通過獲得和利用多用戶相對位置信息,對單個定位估計進行改進.如PCN系統[19]利用藍牙RSSI信號估計目標與鄰居目標的相對位置,檢測一起移動的群體,從而通過其他群體成員的運動軌跡來協同糾正個人用戶估計軌跡的偏差.Social-Loc系統[20]結合行人航位推算與Wi-Fi指紋識別,將兩個用戶是否在候選RP上相遇作為額外信息,對候選RP進行過濾.這類方案大都利用智能終端中的其他傳感器,如藍牙、麥克風等,來獲取用戶間的相對位置,通過估計位置的約束來提高定位的精度.不僅依賴額外的硬件,并且用戶間需要建立通信和同步,用于用戶間測量信息的傳輸,使得這類多用戶進行協同定位的系統復雜度較高.

針對這些問題,本文對同一室內環境中存在多用戶定位的應用場景展開研究.在無需額外的硬件、無需建立定位用戶間的信息傳輸,也即對用戶透明的情況下,利用同時段提出定位請求的鄰近用戶的觀察信息,對目標用戶位置附近可能的候選RP重新定義權重;同時引入了多子集定位,以消除用戶瞬態噪聲的影響,實現抑制大定位誤差,提高定位性能的目的.

1 室內環境下AP信號的特性

室內環境中Wi-Fi網絡的廣泛部署使得一個位置點通常可以檢測到較多數量的AP,而室內環境的復雜性又使每個AP都有其信號可以到達的特定范圍,即覆蓋區域.圖1給出了實驗指紋庫中第5個AP和第43個AP在實驗區域的RSSI信號分布情況,并分別用直線柱和虛直線柱表示.為了方便比較,將RSSI信號變換到[0,100]范圍.觀察圖1在y坐標0.1m,x坐標21.6m～41.4m附近的連續12個位置點能接收來自第5個AP的RSSI信號;在y坐標12.6m,x坐標0.1m～14.4m附近的連續9個位置點能夠接收來自第43個AP的RSSI.可見鄰近的位置點通常經歷相同的AP信號空間分布,即共享一組AP.基于這些觀察,本文利用復雜室內環境下AP有限的信號覆蓋范圍,選取與目標共享一組AP,也即能接收相似AP子集信號的參考位置點作為目標所在的局部區域,也由此覆蓋向量確定與目標鄰近的用于校準位置估計的協同定位用戶.同時也可觀察到目標未接收到的AP也提供了位置信息[21].如當某個目標未能檢測到圖中的這兩個AP信號時,則意味著目標大概率并不位于圖中直線柱所在的區域內.

圖1 RSSI信號分布示意圖Fig.1 Example of RSSI signal distribution

此外,當目標接收的來自各AP的 RSSI信號未受到大的瞬時噪聲影響時,目標實時監測的信號與指紋庫內目標位置附近的RP的指紋匹配度高,此時估計位置靠近目標真實位置,反之,估計位置則會偏離目標真實位置[22].圖2給出對目標接收的RSSI信號加入較大噪聲時,目標估計位置的變化.

圖2 不同數量AP改變時引起的定位變化Fig.2 Positioning performance with the different numbers of altered APs

實驗隨機選取了不同數量的AP,對其RSSI信號加入異常值,利用WKNN算法對目標進行位置估計.如圖2所示,隨著改變的AP數量的增加,目標獲取的RSSI信號向量與指紋匹配度降低,使得估計位置逐漸偏離目標真實位置.

2 基于多用戶在線協同的定位算法

2.1 算法框架

本文提出的基于多用戶在線協同定位算法的框圖如圖3所示.算法在離線階段遍歷定位區域預設的參考位置點,采集其坐標和來自各個AP的RSSI信號,構建指紋數據庫,并由此確定每個AP的覆蓋向量;

圖3 基于在線協同的定位Fig.3 Block diagram of the proposed positioning method

在線階段主要包括:

1)確定候選RP:定位服務器獲取目標用戶RSSI信號,由目標用戶的AP覆蓋向量,從指紋庫中選取相似度最高的若干RP作為候選RP,即將當前用戶定位到一定數量RP對應的局部空間內,以減少后續定位的計算復雜度.

2)確定協同定位用戶:從當前向定位服務器請求服務的其他用戶中,利用他們的RSSI信號,選取與目標用戶位于同一局部空間的用戶作為鄰近的協同用戶.

3)AP子集采樣:用戶的RSSI信號向量中既有接收到的AP信號,也有未檢測到的AP,它們都提供了用戶一定的位置信息;且考慮到部分指紋信號也可完成定位,由此根據目標用戶的RSSI信號構建了多個AP子集.此過程能有效利用目標接收的 RSSI信號,同時又能盡可能消除異常AP信號引入的大定位誤差.

4)在線協同校準:定位時,在每個AP子集內計算目標用戶的RSSI信息與候選RP相應的子指紋的相似度,融合協同定位用戶對候選RP進行的可信度評估,從而篩選最近鄰RP,并利用WKNN算法獲得校準后的目標用戶的定位估計.每個協同定位用戶獨立對目標用戶進行位置校準.此過程綜合考慮了目標用戶獨立的RSSI信號觀察值與協同定位用戶的觀察值對參考點進行篩選,可避免單個定位用戶的RSSI信號存在瞬態噪聲時可能引入的大定位誤差.

5)位置密度檢測:根據目標用戶校準估計位置之間的距離獲得每個校準估計位置的局部密度,以評估每個校準估計位置的可信度.

6)獲得目標用戶估計位置:根據位置密度檢測結果,選取局部密度最大的若干校準估計位置,其質心作為用戶的估計位置.

2.2 確定候選RP和協同定位用戶

設N為定位區域RP數量,M為定位區域可以檢測到的總的AP數量,則第n個RP的指紋可表示為:

Ψn=[ln,rssn]=[xn,yn,rssn1,…,rssnm,…,rssnM]

(1)

式(1)中,ln=[xn,yn]表示第n個RP的二維坐標,rssn表示第n個RP的RSSI向量,rssnm,m=1,…,M是RPn接收的來自APm的RSSI信號,當在該參考點位置無法檢測到APm的信號時,則rssnm設置為一確定值,如-90 dBm.

根據指紋庫中每個RP的RSSI向量,同時可確定相應的AP覆蓋向量,則第n個RP的AP覆蓋向量Hn表示為:

Hn=[hn1,…,hnm,…,hnM]

(2)

式(2)中,若RPn能夠接收到APm的RSSI信號,則hnm=1,否則hnm=0.

在線階段,設某一個時刻,定位區域有S個用戶向定位服務端發送RSSI向量請求定位服務.其中第s個用戶的RSSI向量表示為:

fs=[fs1,…,fsm,…,fsM],m=1,…,M,s=1,…,S

(3)

式(3)中,如果用戶沒有檢測到第m個AP,則定義fsm為一確定值,同時也可確定其AP覆蓋向量:

Gs=[gs1,…,gsm,…,gsM]

(4)

對S個用戶中的任一個目標用戶us,首先確定其所在的局部空間,也即候選RP集.算法利用覆蓋向量的相似度來尋找目標用戶所在局部空間內的候選RP集.利用公式(5)確定目標用戶us與指紋庫內所有參考點覆蓋向量的漢明距離,距離越小,則認為相似度越高.

(5)

根據漢明距離對所有RP進行排序,并取前N′個最小的dsn所對應的RP作為目標用戶us的候選RP,表示為Rs={RP1,…,RPn′,…,RPN′}.這些RP能接收到的AP和目標用戶us接收到的AP列表重合度高,根據無線信號的傳播特性,目標用戶us最有可能靠近這些RP.

同時,利用AP覆蓋向量,找到與目標用戶us鄰近的其他用戶,也即協同定位用戶:

(6)

式(6)中,Gt為與目標用戶us同一時刻請求定位服務用戶的AP覆蓋向量,dst越小,表示該用戶越可能與目標用戶位于同一局部區域.算法選取前S′個最小的dst所對應的用戶作為協同定位用戶,用Us={u1,…,us′,…,uS′}表示.為避免單個定位用戶的RSSI信號存在瞬態噪聲時可能引入大定位誤差,協同用戶的數量S′大于等于2,當協同定位用戶數量S′為0或1時,目標用戶只利用自己的RSSI信號觀察值采用經典的WKNN算法進行位置估計.

2.3 AP子集采樣

設A1為目標用戶檢測到的AP集合,A2為目標用戶未檢測到的AP集合,經過AP子集采樣生成E個AP子集.為充分利用A1和A2里的各AP提供的位置信息,則第e個AP子集可表示為:

Ae={A1,A2e},e=1,…,E

(7)

式(7)中,Ae包含的AP數量記為M′,A2e?A2為包含隨機選擇的α個目標用戶檢測不到的AP的子集.

2.4 在線校準估計位置

在線校準的基本思想是根據無線信號強度隨著距離的增加而衰減的傳播特性,對接收同一AP信號的多個用戶,根據RSSI信號強弱來推斷與AP的遠近距離關系.每個協同定位用戶根據自身接收的RSSI信號,各候選RP以及目標用戶接收的RSSI信號的大小關系對候選RP的可信度進行評估,并融合目標用戶與指紋的相似度對候選RP進行篩選,完成校準定位.

通過式(5)、式(6)已確定目標用戶us的候選RP集Rs和協同定位用戶集Us.在第e個AP子集內,以第s′個協同用戶校準定位的過程為例.定義信號差向量δs′、δs′n′:

δs′=fs′-fs,s′=1,2,…,S′

(8)

δs′n′=fs′-rssn′,n′=1,2,…,N′

(9)

式(8)、式(9)中,fs、fs′和rssn′分別是目標用戶us,協同定位用戶us′和第n′個候選RP的RSSI向量.信號差向量的每一個元素大小反映了Ae子集中每個AP對應的RSSI信號對于目標用戶、協同定位用戶和參考點的相對距離.

當上述信號差向量滿足式(10),則認為從us′角度觀察APm的信號強度,候選RPn′具有高可信度并設置其λs′n′(m)=1,反之則認為其可信度不高并設置λs′n′(m)=-1.

(10)

上述可信度判斷的依據如下:假設δs′(m)>0,根據無線信號的衰減特性,us′比us更靠近APm,若δs′n′(m)<0,候選RPn′比us′更靠近APm.此時,如果把用戶us定位到候選RPn′位置,這與根據δs′(m)信號差得出的結論相矛盾.因此從us′角度觀察APm的信號強度,候選RPn′用于估計目標用戶us的位置時的可信度不高,設λs′n′(m)=-1.

由式(10)對Ae中所有AP觀察后,利用式(11)確定候選RPn′的可信度cs′n′:

(11)

式(11)中,可信度cs′n′值表示從協同定位用戶us′的角度觀察,候選RPn′用于估計目標用戶us位置的可信程度,cs′n′值越大,則候選RPn′越可信.雖然協同定位用戶提供的RSSI信息可以用來校準目標用戶us的位置,但目標用戶us自身獲取的RSSI信號觀察值同樣重要.算法計算Ae子集內目標用戶us與候選RP相應的子指紋的相似度dn′:

(12)

式(12)中,·為內積運算,dn′值越大,則表明兩者的相似度越大,即目標用戶us越接近RPn′.這里指紋相似度dn′的計算采用余弦相似度,其他相似度度量也適用.

通過以上算法步驟,對于N′個候選RP可以獲得相應相似度集D={d1,…,dn′,…,dN′}和可信度集C={cs′1,…,cs′n′,…,cs′N′}.采用min-max標準化對D和C的各數據進行處理:

(13)

(14)

通過式(15)將目標用戶us獨立的RSSI信號觀察值與協同定位用戶us′的校準相結合,對候選RPn′進行權重賦值:

(15)

根據ωs′n′的大小選取權重值最大的K個RP,利用WKNN算法獲得協同定位用戶us′校準后的目標用戶us的定位估計:

(16)

式(16)中,ln′=[xn′,yn′]為篩選出的候選RP的位置,K為WKNN算法的近鄰數,本文統一設置為4.

S′個協同定位用戶進行上述校準操作,共可以獲得S′個校準后的定位估計,其質心作為us的校準估計位置le:

(17)

在E個AP子集內進行上述操作,則可以獲得E個校準估計位置,表示為:L={l1,…,le,…,lE}.

2.5 位置密度檢測

為剔除Ae中APs存在較大瞬態噪聲時產生的異常校準估計位置,定義每個校準估計位置的局部密度為:

(18)

式(18)中,dej表示兩個校準估計位置間的距離,dc>0為截斷距離,通常設置所有樣本間距離的前2%作為截斷距離[23].由式(18)可知,與校準估計位置le的距離小于dc的其他校準估計位置越多,le局部密度越大.當某個校準位置存在異常,嚴重偏離真實位置時,通常具有較小的局部密度.選取局部密度最大的E′個校準估計位置,其質心作為目標用戶最終的估計位置:

(19)

式(19)中,L′為局部密度最大的E′個校準估計位置的集合.

3 算法流程

輸入:指紋庫[ln,rssj]、某一個時刻,定位區域請求定位服務用戶的RSSI向量fs、候選RP數量N′、協同定位用戶數量S′、AP子集數量E、隨機選取AP數α、最大局部密度對應的校準估計位置數E′、WKNN算法近鄰數:K

1.利用公式(5)確定其候選RP集:Rs={RP1,…,RPn′,…,RPN′}

2.利用公式(6)確定其協同定位用戶集:Us={u1,…,us′,…,uS′}

3.利用公式(7)確定其AP子集:Ae={A1,A2e}

4.fore= 1,2,…,Edo

5.fors′ = 1,2,…,S′do

6.forn′ = 1,2,…,N′do

7. 利用公式(8～11)計算可信度cs′n′

8. 利用公式(12)計算相似度dn′

11. 利用公式(15)篩選候選RPn′

12.endfor

13. 利用公式(16,17)獲得目標用戶us的校準估計位:le

14.endfor

16.endfor

4 實驗結果及分析

4.1 實驗環境建立

為了驗證本文提出的多用戶在線協同定位算法的有效性和可行性,分別在本校面積約為70m×14m的光電大樓八樓、九樓進行相關實驗,實驗布局如圖4所示,記為區域A、B,并使用UCI公開數據集[24]進一步驗證所提算法的性能.

圖4 實驗布局圖Fig.4 Floor maps of the experiments

由于目前Wi-Fi網絡已經廣泛部署,本實驗利用了樓層內能掃描到已布置的AP,并沒有在實驗區域部署額外的AP.圖4中,圓點代表RP的位置,三角形代表測試點也即目標的位置.在信號采集中以1.8m網格大小收集各RP位置點的RSSI信號,取RSSI的均值作為指紋存入指紋數據庫中,并在實驗區域測試點上收集RSSI信號.區域A共有88個RP,36個測試點,區域B共有136個RP,44個測試點,并且分別在兩個區域共檢測到324個AP和452個AP.離線指紋數據庫的采集持續數日,測試點信號的采集并不是同時進行,而是采用文獻[25]中的方法,在數小時內連續采集.

實驗中,一個測試點的定位誤差定義為其真實坐標與估計位置坐標之間的歐氏距離.計算所有測試點定位誤差的平均值即平均定位誤差(average localization error,ALE)以及定位誤差的累積分布函數(cumulative distribution function,CDF)作為衡量算法定位性能的指標.

4.2 基于多用戶在線協同定位算法性能測試

4.2.1 算法的定位精度

在評估本文所提算法的定位性能時,除非另有說明,算法設置如下實驗參數:N′=20個候選RP,S′=4個協同定位用戶,E=30個AP子集,α=30個隨機選擇的目標用戶未檢測的AP,最大局部密度對應的估計位置數E′=10.圖5給出了區域A和區域B中各測試點的定位誤差.可以看出在大多數情況下,本文算法通過綜合考慮目標用戶獨立的RSSI信號觀察值與協同定位用戶的觀察值對參考點進行篩選和權重賦值,并由此對目標用戶進行位置估計,降低了RSSI信號中噪聲帶來的影響.例如:在區域A中,采用WKNN算法定位時,有6個位置點的定位誤差大于3m,最大定位誤差為6.3m;采用本文算法定位時,有1個位置點的定位誤差大于3m,最大定位誤差為3.3m.在區域B中,采用WKNN算法定位時,有9個位置點的定位誤差大于3m,最大定位誤差為5.4m;采用本文算法定位時,有3個位置點的定位誤差大于3m,最大定位誤差為3.8m.

圖5 各測試點的定位誤差Fig.5 Positioning error of the test points

圖6進一步給出本文算法對區域B中第26個測試點具體的位置校準結果.如圖6所示,協同定位用戶校準產生的目標用戶估計位置,有的圍繞在目標用戶周圍,有的則分散遠離目標用戶.利用位置密度檢測方法對校準估計位置中的異常點進行剔除,最終產生的用戶估計位置靠近用戶真實位置.對比WKNN算法,使用本文算法進行位置估計,使得區域B第26個測試點的誤差從2.9m下降到0.3m.

圖6 區域B中第26個測試點的定位結果Fig.6 Positioning result of 26th location point in area B

4.2.2 參數選擇對定位性能的影響

為研究各參數對定位性能的影響,在區域A、B中進行相應實驗,設置各參數與上述實驗參數相同時,觀察某一參數變化對定位性能的影響.

1)候選RP數量N′

候選RP數量N′決定了所選取的目標用戶所在的局部空間大小.如圖7(a)所示,候選RP數量對定位精度影響不大,但實際應用中不建議選取過大數量的候選RP.一方面大數量的候選RP中包含某些遠離目標用戶的RP,從而模糊目標用戶在整個定位區域的局部位置,使得定位精度降低;另一方面隨著候選RP數量的增加,算法的計算復雜度也隨之增加.

圖7 參數選擇對ALE的影響Fig.7 Influence of parameter selection on ALE

2)協同定位用戶數量S′

協同定位用戶可為目標用戶提供其所處信號空間的額外觀察.如圖7(b)所示,當協同定位用戶數量為0和1時,由于只利用目標用戶的RSSI信號觀察值并采用WKNN算法進行位置估計,所以定位效果較差.隨著協同定位用戶數量的增加,ALE隨之減少.當協同定位用戶數量為3～6時,即可對定位性能有較大的改善.

3)AP子集數量E

AP子集數量E決定了位置密度檢測方法中截斷距離dc以及最大局部密度對應的校準估計位置數E′的大小,為保證位置密度檢測方法的有效性,該參數不建議取值過小.如圖7(c)所示,該參數對定位精度影響不大,實際應用中可權衡定位精度與計算復雜度進行選取.

4)隨機選取AP數α

為充分利用目標用戶未檢測到的APs包含可能的位置信息,從目標用戶未檢測到的APs中選取α個AP與目標用戶可檢測到的APs構建AP子集.如圖7(d)所示,該參數對定位精度影響不大,實際應用中可根據整個定位區域AP數量進行選取.

5)最大局部密度對應的校準估計位置數E′

由位置密度檢測方法選取E′個局部密度最大的校準估計位置估計目標用戶的位置.如圖7(e)所示,該參數對定位精度影響不大,實際應用中可根據AP子集數量E進行選取.

4.2.3 與已有定位方法的比較

為進一步驗證所提算法的定位性能,圖8給出了在區域A、B中本文算法、OCLoc算法[25]、PCA-KRR算法[26]以及WKNN算法的定位誤差累積分布函數值.考慮到算法計算復雜度和定位精度的權衡,各參數與4.2.1小節實驗參數相同.由圖8可見,在區域A中,本文算法97%的定位誤差小于3m,OCLoc算法中80%的定位誤差小于3m,PCA-KRR算法中63%的定位誤差小于3m,WKNN算法中83%的定位誤差小于3m.在區域B中,也可觀察到類似的性能改善.在區域A中,4種算法的平均定位誤差分別為:1.5m,1.9m,2.8m,2.2m.在區域B中,4種算法的平均定位誤差分別為:1.6m,1.8m,2m,2.1m.對比其他4種算法,在兩個區域中,本文算法有效抑制了指紋偏差引入的大定位誤差并且降低了平均定位誤差.相比經典的WKNN算法,本文算法的定位精度分別提升了大約30%和23%.

圖8 定位誤差累積分布函數Fig.8 Positioning error CDF

4.2.4 公開數據集上的實驗結果

為進一步驗證所提算法的定位性能,在公開數據集上進行同樣的實驗.由于公開數據集中只包含32個AP,所以實驗參數中隨機選取未檢測的AP數量α設置為10,其它實驗參數與上述實驗參數相同.圖9給出每個測試點的定位誤差,可以看出在公開數據集上,本文所提算法同樣可以抑制大定位誤差,如第11個測試點的定位誤差從18.58m減少到9.8m.

圖9 公開數據集各測試點的定位誤差Fig.9 Positioning error of the test points in public dataset

圖10給出,本文算法、OCLoc算法、PCA-KRR算法以及WKNN算法在公開數據集上的定位誤差累積分布函數值.從圖中可以看出對比其他兩種算法,本文算法有效抑制了大定位誤差并提升了定位精度.

圖10 公開數據集定位誤差累積分布函數Fig.10 Positioning error CDF in public dataset

5 結 論

針對室內環境中RSSI信號存在強波動性造成基于用戶獨立觀察的室內定位精度低的實際情況,本文提出一種基于多用戶在線協同定位的室內定位算法.對于多個用戶同時請求定位服務的應用場景,該算法充分利用AP信號在室內空間分布的區域性和信號強度隨距離衰減的特性,結合協同用戶對目標所在局部區域的RP進行可信度和相似度的判定,篩選出若干RP完成定位.所提算法不涉及離線階段定位模型的學習,無需額外硬件支持,各定位目標之間也無需進行信息交換.而實驗研究和分析表明本文所提的結合協同定位用戶觀察的RSSI信號,對最近鄰參考點重新定義權重,從而校準用戶的估計位置,有效降低了RSSI信號波動對定位的影響,抑制了大定位誤差,提高了定位精度.