張立曄，王 壯，房 超，孟曉亮，田愛奎

(山東理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，淄博 255000)

定位與導(dǎo)航服務(wù)在人們的日常生活中發(fā)揮著舉足輕重的作用。近年來，隨著移動(dòng)終端和無線局域網(wǎng)(wireless local area network，WLAN)的普及，在移動(dòng)終端實(shí)現(xiàn)基于位置的服務(wù)(location based service，LBS)已經(jīng)逐漸改變了人們的生活和工作方式。越來越多的應(yīng)用程序開始利用位置信息為用戶提供服務(wù)，其中既有如E911的傳統(tǒng)救援服務(wù)，也包含以智慧城市和物聯(lián)網(wǎng)為代表的全新應(yīng)用領(lǐng)域[1-3]。為了獲取用戶的位置信息，眾多定位系統(tǒng)已經(jīng)完成部署。在戶外，以中國北斗定位系統(tǒng)和美國全球定位系統(tǒng)(global positioning system,GPS)為代表的衛(wèi)星定位系統(tǒng)已經(jīng)可以為用戶提供精確的位置信息。然而，由于樓體的遮擋，衛(wèi)星信號(hào)接收設(shè)備不能在室內(nèi)和衛(wèi)星被高樓阻擋的地區(qū)使用。因此，人們提出了多種室內(nèi)定位解決方案用于替代衛(wèi)星定位系統(tǒng)。

基于Wi-Fi的WLAN技術(shù)經(jīng)過多年的研究，已廣泛部署在校園、機(jī)場、商場等公共場所，WLAN技術(shù)的普及為使用WiFi信號(hào)進(jìn)行位置估計(jì)創(chuàng)造了機(jī)會(huì)。由于在公共區(qū)域中的所有可見接入點(diǎn)(access points,APs)都可以利用移動(dòng)終端查看，并且移動(dòng)終端還可以測量每個(gè)AP的接收信號(hào)強(qiáng)度(received signal strength,RSS)，因此利用Wi-Fi的RSS進(jìn)行用戶位置估計(jì)成為常用的方法之一[4]。

基于RSS的位置指紋定位方法分為兩個(gè)階段：離線訓(xùn)練階段和在線定位階段[5]。在離線訓(xùn)練階段，在室內(nèi)空間中設(shè)置大量參考點(diǎn)(reference point,RP)，并在參考點(diǎn)上采集來自所有AP的RSS數(shù)據(jù)，將RSS值與對(duì)應(yīng)RP的位置空間坐標(biāo)組成位置指紋數(shù)據(jù)庫radio map，radio map是位置指紋技術(shù)的基礎(chǔ)，其保存了信號(hào)空間到位置空間的映射。在在線階段，用戶利用移動(dòng)終端采集所有AP的RSS值，并將用戶接收到的RSS值與radio map中的RSS信號(hào)空間進(jìn)行匹配，進(jìn)而得出用戶的當(dāng)前位置[6-7]。

近年來，眾包技術(shù)以其出色的表現(xiàn)引起了室內(nèi)定位領(lǐng)域的關(guān)注[7-8]。在眾包技術(shù)中，radio map不再由專業(yè)人員建立，而是將復(fù)雜煩瑣的工作化整為零，由眾多志愿者分別采集數(shù)據(jù)匯總而成。眾包技術(shù)大大減少了技術(shù)人員在訓(xùn)練階段收集的RSS值的數(shù)量。當(dāng)志愿者在進(jìn)行日常活動(dòng)時(shí)，移動(dòng)終端采集各種傳感器數(shù)據(jù)用于建立radio map，例如，加速度計(jì)數(shù)據(jù)可用于計(jì)算兩次RSS采樣之間的相對(duì)位移；磁力計(jì)或陀螺儀用于測量方位變化等。最后，這些眾包數(shù)據(jù)經(jīng)過處理之后組合在一起，構(gòu)成無radio map。

為了更加規(guī)范地進(jìn)行數(shù)據(jù)采集，技術(shù)人員在室內(nèi)的設(shè)置起點(diǎn)和終點(diǎn)，手持移動(dòng)終端從起點(diǎn)移動(dòng)到終點(diǎn)，在移動(dòng)過程中采集RSS數(shù)據(jù)和傳感器數(shù)據(jù)。利用加速度計(jì)和陀螺儀等傳感器計(jì)算兩個(gè)連續(xù)RSS樣本之間的相對(duì)位移，每一個(gè)采集RSS數(shù)據(jù)的位置即為參考點(diǎn)(reference point,RP)。通過同時(shí)收集RSS值和傳感器數(shù)據(jù)，可以快速構(gòu)建無線電地圖。

在上述數(shù)據(jù)采集方法中，在每個(gè)RP上只能采集一個(gè)RSS數(shù)據(jù)，考慮到RSS值會(huì)受到噪聲和信道衰落的影響，單個(gè)RSS數(shù)據(jù)很難準(zhǔn)確反映該位置的實(shí)際的RSS分布。為了消除噪聲對(duì)radio map的影響，中外專家學(xué)者提出了多種噪聲抑制算法。文獻(xiàn)[9]提出了相關(guān)時(shí)間窗濾波(sliding correlation time window,SCTW)算法對(duì)radio map進(jìn)行平滑，在采集數(shù)據(jù)時(shí)，利用一段時(shí)間內(nèi)采集的RSS數(shù)據(jù)對(duì)實(shí)時(shí)采集的RSS數(shù)據(jù)進(jìn)行濾波，從而消除RSS數(shù)據(jù)的波動(dòng)。文獻(xiàn)[10]提出了一種基于Hankel矩陣的radio map噪聲消除算法，該算法從radio map中提取不同AP對(duì)應(yīng)的信號(hào)向量來構(gòu)造Hankel矩陣，對(duì)Hankel矩陣進(jìn)行求解從而實(shí)現(xiàn)信號(hào)和噪聲的分離。文獻(xiàn)[11]提出利用輕量級(jí)深度學(xué)習(xí)算法在基于信道狀態(tài)信息的室內(nèi)定位系統(tǒng)中實(shí)現(xiàn)噪聲消除和降維，本算法對(duì)批量數(shù)據(jù)點(diǎn)多項(xiàng)式回歸，從而濾除噪聲。文獻(xiàn)[12]提出在同一RP上采集不同AP的RSS值，并計(jì)算不同AP的RSS值的差值，并將該差值與原始RSS數(shù)據(jù)融合作為指紋特征生成radio map，最后利用神經(jīng)網(wǎng)絡(luò)算法進(jìn)行用戶位置的解算。文獻(xiàn)[13]提出了WiDeep系統(tǒng)，該系統(tǒng)結(jié)合了堆疊式去噪自編碼器深度學(xué)習(xí)模型和概率框架來處理接收到的WiFi信號(hào)中的噪聲，同時(shí)得到RSS數(shù)據(jù)與相應(yīng)RP位置之間的關(guān)系。文獻(xiàn)[14]提出了一種基于稀疏表示和低秩矩陣恢復(fù)的無線電地圖更新方法，該算法將RSS矩陣的低秩特性和稀疏先驗(yàn)結(jié)合起來，處理指紋缺失和稀疏噪聲。從以上算法可以看出，現(xiàn)階段研究主要利用radio map中的部分?jǐn)?shù)據(jù)之間的相關(guān)性實(shí)現(xiàn)對(duì)噪聲的抑制，而其他數(shù)據(jù)的信息被忽略了，因此無法實(shí)現(xiàn)最優(yōu)的噪聲抑制效果。

受到這些算法的啟發(fā)，現(xiàn)研究一種多維尺度變換(multidimensional scaling,MDS)算法，對(duì)離線階段利用眾包技術(shù)采集的RSS值進(jìn)行平滑處理。MDS算法是在一組數(shù)據(jù)對(duì)象上分析其相似性或非相似性的一種技術(shù)。在MDS算法中，由于APs和RPs的位置固定，在不同RPs處采集的RSS值具有內(nèi)在關(guān)系，用相似矩陣表示[15-17]?；谛盘?hào)傳播模型，考慮APs和RPs位置，可以計(jì)算得到在兩個(gè)RPs上采集的RSS數(shù)據(jù)的相似性距離。在離線訓(xùn)練階段，利用MDS算法和相似度矩陣能夠降低噪聲和測量誤差對(duì)RSS數(shù)據(jù)的影響，從而實(shí)現(xiàn)對(duì)radio map的平滑處理，最終提高定位精度。

1 問題分析

考慮典型的Wi-Fi室內(nèi)定位場景，其中用戶攜帶一個(gè)裝有Wi-Fi適配器的移動(dòng)設(shè)備，在室內(nèi)環(huán)境中從Wi-Fi AP采集RSS數(shù)據(jù)。在離線訓(xùn)練階段，實(shí)驗(yàn)人員在n個(gè)參考點(diǎn)上采集來自m個(gè)AP的RSS值，所有RSS數(shù)據(jù)與其對(duì)應(yīng)的坐標(biāo)信息構(gòu)建成一個(gè)radio map。第i指紋(ri,ci)是由一個(gè)m×1維的RSS向量ri和相對(duì)應(yīng)的坐標(biāo)ci組成，其中ri為在第i個(gè)RP采集的來自m個(gè)AP的RSS值，第i個(gè)RP的坐標(biāo)ci=(xi,yi)T。在傳統(tǒng)的Wi-Fi定位方法中，通常會(huì)在每一個(gè)RP采集數(shù)百個(gè)RSS數(shù)據(jù)，并計(jì)算這些RSS數(shù)據(jù)的平均值，利用該平均值最終得到無線電地圖。無線電地圖可以用矩陣形式表示為

(1)

式(1)中：rij為在第i個(gè)RP上采集的來自第j個(gè)AP的RSS平均值。在在線定位階段，用戶利用移動(dòng)設(shè)備在某未知位置Sj處采集來自AP的RSS值rj，然后通過比較rj與radio map中的RSS數(shù)據(jù)來估計(jì)用戶所處的位置。在基本的定位理論中，如果所采集的rj與radio map中的ri相似，則認(rèn)為用戶的位置Sj必定靠近Si。

眾包定位系統(tǒng)存在的一個(gè)問題是在離線訓(xùn)練階段和在線定位階段會(huì)有大量不同品牌不同型號(hào)的移動(dòng)終端在定位系統(tǒng)中運(yùn)行。由于不同移動(dòng)終端設(shè)備中配置的Wi-Fi信號(hào)接收器不同，而對(duì)于同一個(gè)AP，不同Wi-Fi信號(hào)接收器接收到的RSS強(qiáng)度有較大差別，從而得到不同的數(shù)據(jù)分布。大量研究表明，由于硬件的差異，不同設(shè)備采集的RSS差異甚至超過25 dBm[18-19]。因此，由于不同設(shè)備采集的RSS數(shù)據(jù)波動(dòng)較大，造成定位系統(tǒng)的定位精度大大降低。針對(duì)上述問題，在文獻(xiàn)[20]中提出了基于線性回歸(linear regression，LR)算法的設(shè)備多樣性消除算法，該算法解決了設(shè)備多樣性問題，在離線訓(xùn)練階段和在線定位階段都得到了具有一致性的RSS數(shù)據(jù)。

室內(nèi)定位的另一個(gè)問題是移動(dòng)設(shè)備在室內(nèi)環(huán)境中采集的RSS值波動(dòng)較大。首先，RSS數(shù)據(jù)會(huì)受到多種噪聲源的影響，例如路徑損耗、多徑和陰影；第二，AP的發(fā)射功率會(huì)隨著時(shí)間的不同而不同；第三，對(duì)于所有可用的AP，移動(dòng)設(shè)備可能無法掃描整個(gè)頻譜采集RSS數(shù)據(jù)。因此，用來建立radio map的RSS數(shù)據(jù)必然包含大量環(huán)境噪聲和測量誤差。為了說明這一點(diǎn)，從多倫多大學(xué)Bahen大樓的某個(gè)位置采集了100個(gè)RSS值，并在圖1中繪制了直方圖。如圖1所示，雖然利用同一設(shè)備在同一位置采集來自同一個(gè)AP的這些RSS數(shù)據(jù)，但是所采集的RSS數(shù)據(jù)的功率分布在-70～-50 dBm的較大區(qū)間內(nèi)。

圖2所示為Bahen大樓4樓走廊的RSS數(shù)據(jù)分布(不包括異常值-110 dBm)。在圖2中，每一個(gè)色塊代表在該RP上采集的來自某一AP的RSS值，為了便于顯示該值，對(duì)所有RSS值加110，使所有RSS值都大于0 dBm，取值范圍變?yōu)?0～110 dBm)，而顏色越偏紅色代表RSS值越大，顏色越偏藍(lán)色代表RSS值越小，后續(xù)radio map分布都遵從該范圍。因此圖中顯示的RSS值范圍從圖2中可以看出，雖然在整個(gè)走廊中，RSS數(shù)據(jù)的信號(hào)分布在一定程度上符合信號(hào)傳播模型，但是RSS數(shù)據(jù)在某些位置卻有較大的差異。利用這種包含大量波動(dòng)的RSS數(shù)據(jù)進(jìn)行定位會(huì)導(dǎo)致較大的位置估計(jì)誤差。

圖2 多倫多大學(xué)Bahen樓4樓走廊某AP的信號(hào)分布Fig.2 Signal distribution in corridor of 4th floor of Bahen building at University of Toronto

如上所述，可以得到室內(nèi)定位系統(tǒng)中一個(gè)關(guān)鍵的挑戰(zhàn)：如何處理眾包定位系統(tǒng)采集的RSS數(shù)據(jù)，使其更接近理論值？采用MDS算法來抑制RSS值的波動(dòng)，從而得到更加平滑的radio map。

定義D為AP與RP之間距離的矩陣，表達(dá)式為

D=[d(Si,APk)]n×m

(2)

式(2)中：d(Si,APk)為參考點(diǎn)Si與接入點(diǎn)APk之間的歐氏距離，即

d(Si,APk)=‖ci-cAPk‖2

(3)

式(3)中：cAPk為第k個(gè)AP的坐標(biāo)。

定義R=[r(Si,Sj)]n×n為在參考點(diǎn)Si和Sj上采集的RSS數(shù)據(jù)的相似性矩陣，值得注意的是，RPs與參考點(diǎn)Si和Sj之間的相對(duì)RSS值與歐氏距離有關(guān)，公式為

r(Si,Sj)≈F[d(Si,APk)]

(4)

式(4)中：F為室內(nèi)環(huán)境中的電磁波傳播模型。

2 基于MDS算法的RSS平滑理論

如前文所述，利用眾包技術(shù)獲得的RSS數(shù)據(jù)是在室內(nèi)環(huán)境中正常行走時(shí)測量得到的，因此建立的radio map中RSS數(shù)據(jù)包含大量噪聲。利用MDS算法，根據(jù)采集點(diǎn)之間的相對(duì)距離、已知AP位置和信號(hào)傳播模型實(shí)現(xiàn)對(duì)radio map數(shù)據(jù)的平滑。

2.1 經(jīng)典MDS算法

在離線訓(xùn)練階段構(gòu)建radio map時(shí)，數(shù)據(jù)空間中所有數(shù)據(jù)點(diǎn)之間的相似性距離的平方r2(Si,Sj),其中，i,j=1,2,…,n，由式(5)計(jì)算得到，即

(5)

然后得到數(shù)據(jù)空間中的平方相似矩陣為

(6)

在MDS算法中，相對(duì)點(diǎn)RSS′由R計(jì)算，計(jì)算過程如下。

首先，對(duì)相似性矩陣進(jìn)行雙定心處理，表達(dá)式為

(7)

給出J的定義為

(8)

用奇異值分解(singular value decomposition,SVD)對(duì)B進(jìn)行分解，即

B=UΛUT

(9)

式(9)中：Λ=diag(λ1,λ2,…,λm)為B的特征值的對(duì)角矩陣，λ1≥λ2≥…≥λn≥0；U=[u1,u2,…,un]，為一個(gè)正交矩陣，其中每一列是特征值對(duì)應(yīng)的特征向量。

假設(shè)需要得到m維的解，用矩陣Λm表示前m個(gè)最大特征值，Um表示矩陣U的前m列，則經(jīng)典尺度變換的坐標(biāo)矩陣為

(10)

2.2 估計(jì)r2(Si,Sj)

為了平滑radio map中的RSS值，需要精確的相似距離矩陣。當(dāng)在RPSi上采集的RSS值包含噪聲時(shí)，使用信號(hào)傳播模型來計(jì)算相似性距離r(Si,Sj)。如圖3所示，考慮在室內(nèi)區(qū)域中安裝的第k(k=1,2,…,m)個(gè)AP。利用文獻(xiàn)[21]中的CS方法可以精確地估計(jì)AP的位置cAP，因此將其位置視為已知。利用文獻(xiàn)[22]中的室內(nèi)信號(hào)傳播模型來模擬無線信號(hào)在環(huán)境中的傳播。

圖3 一個(gè)AP的典型Wi-Fi網(wǎng)絡(luò)Fig.3 A typical Wi-Fi network with one AP

那么從在位置Si處接收到的來自第k(k=1,2,…,m)個(gè)AP的RSS值，可以表示為

(11)

式(11)中：dik為第k個(gè)AP與測量位置之間的距離；P為AP的傳輸功率；αi為環(huán)境中的傳播損耗指數(shù)；hjk為包含路徑損耗、衰落和陰影的衰減。

使用式(11)的模型和文獻(xiàn)[15]的方法，可以得到

(12)

定義r(Si,Sj)為在位置Si和Sj上采集的來自所有AP的RSS值的差值矩陣。r(Si,Sj)的第k個(gè)元素為在位置Si和Sj上采集的來自第k個(gè)AP的RSS值的差值，可以表示為

rk(Si,Sj)=rik-rjk

(13)

r(Si,Sj)的歐氏距離范數(shù)可以寫為

(14)

r(Si,Sj)的歐氏距離范數(shù)可以寫為

(15)

2.3 MDS算法的應(yīng)用

在室內(nèi)區(qū)域的n個(gè)RP上采集來自m個(gè)AP的RSS值，得到一個(gè)n×m階的radio map。由于在RSS矩陣RSS中，含有噪聲的RSS值是未知的，因此假設(shè)在RPSi上采集的RSS值ri是含有噪聲的，利用MDS算法，基于坐標(biāo)矩陣C和RSS矩陣中除ri之外的RSS值可以實(shí)現(xiàn)對(duì)ri平滑。利用該方法，其余RP上的RSS值可以一一實(shí)現(xiàn)平滑處理。radio map可以通過以下步驟進(jìn)行平滑。

步驟1利用式(14)計(jì)算RPSi與其他RPs在數(shù)據(jù)空間中的相似距離。其余的相似距離由RSS值計(jì)算，最終，MDS算法所需的相似性距離矩陣由這兩部分相似距離組成。

步驟2對(duì)距離矩陣應(yīng)用MDS，保留前m個(gè)最大的特征值和特征向量，構(gòu)建m維相對(duì)RSS矩陣。

步驟3利用線性變換(可能包括縮放、旋轉(zhuǎn)和反射)，基于除ri外的矩陣RSS將相對(duì)RSS矩陣轉(zhuǎn)換為絕對(duì)RSS矩陣。

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

利用仿真和實(shí)驗(yàn)對(duì)基于MDS算法的RSS平滑進(jìn)行了驗(yàn)證。離線訓(xùn)練階段，利用移動(dòng)終端在多倫多大學(xué)Bahen中心4樓采集RSS數(shù)據(jù)和傳感器數(shù)據(jù)，然后利用傳感器數(shù)據(jù)和計(jì)步算法自動(dòng)計(jì)算RPs的坐標(biāo)。在實(shí)驗(yàn)過程中，由于在每個(gè)RP只采集5個(gè)RSS值，結(jié)合計(jì)算得到的與RSS值對(duì)應(yīng)的坐標(biāo)，在30 min內(nèi)構(gòu)建了一個(gè)radio map。在線定位階段，實(shí)驗(yàn)人員手持移動(dòng)終端從房間4000(圖4的頂部)移動(dòng)到房間4148(圖4的底部)，在該路徑上共收集到35個(gè)測試點(diǎn)的序列。

圖4 測試點(diǎn)實(shí)際位置Fig.4 Actual locations of Test Points

由于室內(nèi)環(huán)境的復(fù)雜性，在不同區(qū)域的衰減是不同的。因此，在室內(nèi)環(huán)境的不同位置采用不同的傳播損耗指數(shù)α值，以獲得更好的定位結(jié)果。當(dāng)AP在RP的視線范圍內(nèi)時(shí)，設(shè)α=3.5。當(dāng)RP位于角落附近時(shí)，設(shè)置α=1.5來模擬由墻壁反射造成的信號(hào)衰減的減小。當(dāng)從AP到RP中間有遮擋，即不在視線范圍時(shí)，設(shè)α=5，同時(shí)，如果信號(hào)傳播路徑中有更多障礙物時(shí)，該值會(huì)繼續(xù)增大。

如圖5(a)所示，盡管AP在室內(nèi)環(huán)境中RSS的信號(hào)分布值與信號(hào)傳播模型基本一致，但是大量的噪聲和測量誤差使得radio map中某些RP上的RSS值出現(xiàn)劇烈波動(dòng)。利用原始的radio map，得到如圖6所示的定位結(jié)果?？梢钥吹?，與圖4中的實(shí)際位置相比，定位結(jié)果存在明顯的誤差。此外，某些不同的測試點(diǎn)被錯(cuò)誤地定位到相同的位置。

為了提高定位精度，在離線訓(xùn)練階段，采用提出的MDS算法平滑接收到的RSS值。圖5(b)為平滑后的radio map信號(hào)分布，可以看到，經(jīng)過MDS算法平滑之后，原始radio map中的RSS數(shù)據(jù)去除了很多噪聲和測量誤差，得到的radio map更符合室內(nèi)信號(hào)模型。圖6為利用原始radio map進(jìn)行定位測試得到的定位結(jié)果，可以看出，很多不同位置的測試點(diǎn)被錯(cuò)誤地定位在同一位置。而圖7為利用平滑后的radio map進(jìn)行定位得到的定位結(jié)果，從圖7可以看出，利用平滑之后的radio map進(jìn)行定位得到的定位精度明顯提高，在圖6中堆積在一起的定位結(jié)果被定位在不同位置，并且更接近它們的實(shí)際位置。因此，提出的MDS算法能夠提供更高質(zhì)量的位置服務(wù)。

圖5 radio map信號(hào)分布比較Fig.5 Comparison of signal distribution of radio map

圖6 利用原始radio map的定位結(jié)果Fig.6 Positioning results using original radio map

圖7 利用MDS算法后的定位結(jié)果Fig.7 Positioning results using the MDS algorithm

MDS算法定位誤差的累計(jì)分布曲線如圖8所示。作為對(duì)比，還利用文獻(xiàn)[8]中提出的光滑CHKS函數(shù)孿生(smooth twin CHKS support，SCTW)算法對(duì)radio map進(jìn)行平滑，并利用該radio map和原始數(shù)據(jù)進(jìn)行了定位測試。由于SCTW方法只使用了少量的無線電地圖RSS值，大部分radio map信息都被舍棄了，因此無法獲得更優(yōu)的radio map。由于所提出的MDS算法得到了更加精確的radio map，因此與其他方法相比，利用MDS算法進(jìn)行radio map平滑處理可以得到更高的定位精度，從測試結(jié)果可以看出，利用MDS算法對(duì)radio map進(jìn)行平滑使得最大定位誤差由10 m減小到4 m，平均誤差由2.89 m減小到2.11 m。

圖8 定位誤差累計(jì)分布函數(shù)Fig.8 Cumulative distribution function of Positioning error

4 結(jié)論

提出了一種基于MDS算法的RSS平滑方法，在基于指紋的眾包室內(nèi)定位系統(tǒng)中，由于RPs的固定位置，不同RPs之間的RSS值有內(nèi)在的關(guān)系，利用MDS算法，可以挖掘不同RP上采集的RSS之間的內(nèi)在關(guān)系，從而有效校正有噪聲的RSS值，得到更平滑的radio map。在多倫多大學(xué)Bahen中心測試了該方法，實(shí)驗(yàn)結(jié)果表明該方法能顯著提高定位精度。