基于場強(qiáng)地圖的室內(nèi)定位技術(shù)研究

王韋剛，周 蓉，張云偉，李 韜（南京郵電大學(xué)，江蘇南京 210023）

0 引言

目前室內(nèi)定位系統(tǒng)要求既要節(jié)約成本［1-3］，又要縮短定位時間。基于指紋庫的室內(nèi)定位技術(shù)，能對包括信號指示強(qiáng)度（RSSI）在內(nèi)的多種測量參數(shù)快速地建庫［4-6］。其中，采用反演模式的電波傳播模型，能迅速構(gòu)造用于定位的場強(qiáng)地圖，通過指紋庫匹配的方式進(jìn)行定位，該技術(shù)近年來頗受關(guān)注。估計值和收斂準(zhǔn)則對計算結(jié)果有較大影響，此方法求得的解仍然存在較大的誤差。利用反演模式下的電波傳播模型，構(gòu)造場強(qiáng)地圖進(jìn)行快速定位是當(dāng)前比較實用的方法之一。Y.Shu 等人［7］采用共軛梯度法（CGM——Conjugate Gradient Method）定位室內(nèi)中的位置，但是由于共軛梯度法的局限性，該方法只能在特定的環(huán)境下使用。M.Leigsnering 等人［8］采用正交匹配追蹤法（OMP——Orthogonal Matching Pursuit）求解病態(tài)方程組，有效地減小了計算誤差，但是該方法的不足之處是計算復(fù)雜度比較高。S.Liu 等人［9］利用改進(jìn)的正交匹配追蹤法求解病態(tài)方程組，由于初始在線匹配定位時，多種匹配方法也已經(jīng)運(yùn)用到相關(guān)定位算法中。X.Liu 等人［10］利用并行最近鄰匹配（KNN——K Nearest Neighbor）搜索算法對空間細(xì)分并過濾，該方法有助于減少內(nèi)存占用，其不足之處是精度較低。H.Feng等人［11］提出了一種用KNN 算法對旁路圖像進(jìn)行熵估計的方案，該方法能有效地對互信息進(jìn)行評估。X.Wang 等人［12］設(shè)計了一種基于機(jī)器學(xué)習(xí)中KNN 匹配的分類器，該分類器的安全較高，性能較好，但不適用于數(shù)據(jù)多的情況。P.Botsinis 等人［13］提出一個INTRI 室內(nèi)定位框架，該框架運(yùn)用了加權(quán)最近鄰匹配（WKNN——Weight K Nearest Neighbor）算法進(jìn)行位置匹配，但其可實施性較差。

1 離線階段

1.1 基于電磁傳播模型的構(gòu)建

在無線信號傳播過程中，會存在各種物體遮擋傳輸，大量的信號為非視距（NLOS）傳播，只有極少量信號是視距（LOS）傳播［14］。室內(nèi)的無線傳輸存在多徑效應(yīng)，使得接收信號強(qiáng)度實時變化較大，也都會影響定位效果。然而，場強(qiáng)的波動依然在一定范圍內(nèi)，只要統(tǒng)計樣本足夠則可消除小尺度衰落的影響［15］，通過中值濾波可獲得測試點的有效場強(qiáng)。

為了簡化問題，將預(yù)測區(qū)域分成網(wǎng)格，圖1是信號經(jīng)過虛擬路徑到達(dá)接收機(jī)的場景圖。圖1 中AP 是發(fā)射機(jī)的位置表示第i（i=1???M）條射線，Ai是第i條射線進(jìn)入預(yù)測區(qū)域的交點，Bi是到達(dá)接收機(jī)的點，Gj表示第j（j=1???N）個網(wǎng)格。

圖1 無線傳播模型示意圖

圖1 中用αj表示每個網(wǎng)格對應(yīng)信號的衰減因子，di,j表示傳播路徑i經(jīng)過第j個網(wǎng)格的距離，如果虛擬傳播路徑不經(jīng)過某個網(wǎng)格，則該網(wǎng)格對應(yīng)的距離為0。

設(shè)接收端與發(fā)射源之間的傳播損耗表示為：

式中：

PLoss(r)——信號強(qiáng)度衰減

Pt(r)——信號的發(fā)射功率

Pr(r)——接收信號功率

S0(r)——空間傳播時由距離引起的衰落

S1(r)和S2(r)——為陰影衰落和小尺度衰落

由于信號強(qiáng)度的衰減隨距離空間變化，因此可以定義信號強(qiáng)度衰減因子α(r)為：

式中：

r——傳播距離

衰減因子表示單位傳播距離上的強(qiáng)度衰減量。式（2）也可改寫為積分的形式，定義積分算子α(r)，可以將轉(zhuǎn)化為：

它表示通過對積分算子?i的積分，信號強(qiáng)度的損耗表現(xiàn)為通過傳播路徑時所經(jīng)歷的總衰減。

當(dāng)信號沿傳播路徑穿過網(wǎng)格時，每個網(wǎng)格有不同的衰減因子，用αj表示區(qū)域內(nèi)不同網(wǎng)格的衰減因子。當(dāng)不通過某個網(wǎng)格時，則該網(wǎng)格的衰減因子為零。假設(shè)用i表示虛擬傳播路徑，則每條路徑的損耗為：

全部M條路徑組成的總損耗為：

式中：

PLoss——信號在預(yù)測區(qū)域內(nèi)的信號強(qiáng)度損耗，且PLoss=[P1Loss,P2Loss,???,PMLoss]

D——由信號經(jīng)過預(yù)測區(qū)域內(nèi)每個網(wǎng)格的距離組成的M×N矩陣，記作

α——衰減因子向量，且α=α1，α2，???，αj，???，αN

E——由級數(shù)展開時的數(shù)據(jù)估計的近似性和測量引起的誤差

1.2 新型反演模式的信號模型的求解

式（5）是一個病態(tài)方程組，它有多種求解方法。傳統(tǒng)的方法有代數(shù)重建法（ART——Algebraic Reconstruction Technique）［16］、雅可比（Jacobi）算法［17］、共軛梯度法（CGM）、正交匹配追蹤（OMP）等［9］。為了提高網(wǎng)格中衰減因子的求解準(zhǔn)確度，本文提出使用追蹤共軛梯度法（PCG——Pursuit Conjugate Gradient）求解網(wǎng)格中的衰減因子。

根據(jù)壓縮感知的知識，高維的稀疏信號可以從低維的非相關(guān)觀測值進(jìn)行重構(gòu)。在式（5）中，需要從M維觀測值PLoss恢復(fù)N維信號α，其中M?N。然而α本身不具有稀疏性，需要找到某個稀疏基ψ，并有α=ψθ，稀疏矩陣ψ為N×N維，系數(shù)θ為N×1 維的列向量且是K稀疏的（K?N）。

設(shè)b=PLoss-E，則式（5）可寫為：

設(shè)Η=Dψ，則相當(dāng)于求解：

由于展開的系數(shù)θ具備稀疏性，則可由壓縮感知技術(shù)中的OMP 方法恢復(fù)稀疏矩陣θ，進(jìn)而由α=ψθ可得到衰減因子α。求解過程如下：

先初始化參數(shù)設(shè)置，令r0=b，Λk=φ，k=1，尋找λk，使得：

式中：

rk——?dú)埐?/p>

k——迭代次數(shù)

Λk——k次迭代索引（列序號）的集合

λk——第k次迭代找到的索引號

aj——矩陣Η的第j列

Ηk——按索引Λk選出的矩陣Η的列集合

θk——θ中提取的k×1的列向量

令Λk=Λk-1?λk，Ηk=Ηk-1?aj，在此情況下，系數(shù)方程b=Ηkθk求解公式為：

進(jìn)一步，式（11）可以用共軛梯度法求解。設(shè)t是共軛梯度法中的迭代次數(shù)，初始值為θ0，初始梯度方向為其 中=[1,...,1]T，k×1維，g0表示初始值為θ0時的一階偏導(dǎo)數(shù)，建立新的目標(biāo)函數(shù)為：

共軛梯度法迭代式為：

可求得Ω，進(jìn)而可求式（14）的一階偏導(dǎo)數(shù)gt，表示式為：

如果‖gt‖＞ε，則根據(jù)FR（Fletcher-Reeves）公式，得到下降方向：

將式（16）代入式（13），依次迭代直至‖gt‖＜ε，得到θt。

如果k≤K，令k=k+1，繼續(xù)尋找索引λk；否則重構(gòu)出，進(jìn)而求出α。

PCG算法步驟如表1所示。

表1 PCG算法

為了對各種算法復(fù)雜度進(jìn)行分析，各算法迭代次數(shù)總體分析如表2 所示。k表示索引的迭代次數(shù)，t是共軛梯度法迭代次數(shù)。

表2 幾種方法的典型性能分析比較

PCG 算法的迭最大代次數(shù)由稀疏度K和迭代次數(shù)t2 項決定，前者在稀疏的前提條件下是小于M的常數(shù)，而后者則已經(jīng)由經(jīng)典的OMP 算法證明是收斂的［9］。

1.3 場強(qiáng)地圖的建立

通過對預(yù)測區(qū)域網(wǎng)格作精細(xì)劃分，并利用衰減因子對各位置的場強(qiáng)統(tǒng)計特征值做出預(yù)測，得出網(wǎng)格的信號場強(qiáng)的計算方法如下：

式中：

P?(Ai)——測試區(qū)域邊界Ai處的信號強(qiáng)度

式（18）表明接收點強(qiáng)度為發(fā)射點場強(qiáng)減去各網(wǎng)格上的衰減總和。

信號場強(qiáng)地圖中保存了多種信息，包括信號樣本強(qiáng)度、位置等。假設(shè)室內(nèi)AP 點個數(shù)為S，則信號強(qiáng)度矩陣可記為：RSSI=(rssi1,???,rssiu,???,rssiS)，其中該矩陣中的每個列向量可以具體寫為rssiu=(rssiu,1,???,rssiu,j,???,rssiu,N)T，其中，u=1,???,S，代表AP 個數(shù)，j代表網(wǎng)格Gj(j=1,???,N)，場強(qiáng)地圖的參數(shù)矩陣形式為：

其中xj,yj(j=1 ???N)為場強(qiáng)地圖中第j個網(wǎng)格的位置坐標(biāo)。

2 在線階段

經(jīng)過建立好場強(qiáng)地圖后，接收終端在線可獲得最新的信號強(qiáng)度等數(shù)據(jù)，經(jīng)濾波及相關(guān)處理后，采用匹配算法進(jìn)行匹配與定位。

2.1 傳統(tǒng)的在線匹配算法

傳統(tǒng)的定位匹配算法常采用基于歐幾里德距離的思想，計算實測均值與場強(qiáng)地圖中對應(yīng)值的差值，將差值最小的點作為定位點。

假設(shè)第u個AP 發(fā)射信號時，在線測得的Q位置處RSSI 均值為,u=1,???,S，求得距離Lu，其表達(dá)式為：

對信號強(qiáng)度進(jìn)行初步過濾，計算滿足該條件的歐氏距離：

記錄滿足式（21）的位置Gj、對應(yīng)場強(qiáng)地圖中信號強(qiáng)度值rssiu,j、以及坐標(biāo)(xj,yj)，并將坐標(biāo)重新排序整理為（xj，y）j，j=1，???，q。如果Lu大于閾值，則調(diào)整縮小ε，并刷新記錄。假設(shè)在線需要測量的實際位置為，通過式（21）計算后，將記錄的位置與實際位置進(jìn)行對比，得到最終位置信息。

目前廣泛應(yīng)用的匹配算法是KNN（K Nearest Neighbor）［18］，WKNN（Weight K Nearest Neighbor）［19］以及DC-WKNN（Differential Coordinates-WKNN）［20］。但是這些算法在復(fù)雜的室內(nèi)環(huán)境中存在以下2個問題。

a）定位中人員走動、門開關(guān)都會引起某些RSSI發(fā)生巨大波動，導(dǎo)致求得的近鄰坐標(biāo)與實際的坐標(biāo)產(chǎn)生較大誤差，但是上述的幾種算法中沒有對坐標(biāo)誤差進(jìn)行約束，因此這種影響仍然存在。

b）當(dāng)AP 信號受環(huán)境影響尤為嚴(yán)重時，對接收端接收到的RSSI 影響較大，因此需要考慮AP 點的權(quán)重性問題，而上述算法在計算距離時，對各個AP 的處理一樣，沒有考慮到這個問題。

針對上述2 個問題，本文提出一種加權(quán)差分坐標(biāo)K最近鄰法（WDC-WKNN——Weight Differential Coordinates-WKNN）。

2.2 改進(jìn)的在線匹配算法

針對2.1 節(jié)中指出的在線匹配過程中存在的問題，本節(jié)提出的WDC-WKNN 算法主要進(jìn)行了2 個方面的改進(jìn)。

改進(jìn)一是設(shè)置單個AP 所測得的坐標(biāo)誤差門限ζ，要求測得的坐標(biāo)誤差小于門限值，如果不滿足要求，則舍棄并重新匹配。該門限值的設(shè)置主要解決當(dāng)單個AP 的RSSI 波動較大時，導(dǎo)致變大，使得求(x,y)時誤差變大的問題。

改進(jìn)二是對于穩(wěn)定的和某些受環(huán)境影響尤為嚴(yán)重的AP信號，根據(jù)影響大小設(shè)置AP權(quán)重系數(shù)。

由式（21）測得的滿足條件坐標(biāo)可分別求與實測位置的誤差值，表達(dá)式為：

記錄滿足式（22）的坐標(biāo)個數(shù)q、誤差ej及位置(xj,yj)，并按照誤差大小重新排序整理為（xj，yj），j=1，???，q。第u個AP點發(fā)射信號時，估計出的相應(yīng)坐標(biāo)為：

其中，wj為滿足條件的q個坐標(biāo)的權(quán)重系數(shù)。

針對改進(jìn)一，增加門限值ζ。由公式（23）計算出后，如果，說明此次測量誤差較大，則刪去由式（22）記錄的坐標(biāo)（xj，yj），j=1，???，q中誤差最大的一個數(shù)值，并重新計算式（23）得到，直至滿足

針對改進(jìn)二，考慮AP 的權(quán)重問題，對于S個AP點，估計的坐標(biāo)為：

其中，Wu為第u個AP 的權(quán)重系數(shù)。坐標(biāo)的絕對誤差計算表達(dá)式為：

最后，總結(jié)出WDC-WKNN算法步驟如表3所示。

表3 WDC-WKNN算法

由于場強(qiáng)地圖在線匹配都是線性匹配，所以此階段的算法的復(fù)雜度都相同。另外，由于該算法為匹配算法，只要選擇并調(diào)整合適的ζ值，一定能滿足條件，因此能實現(xiàn)快速收斂。

3 實驗結(jié)果評估

3.1 仿真環(huán)境

設(shè)在室內(nèi)布置3 個AP 點，仿真的室內(nèi)環(huán)境是10×10 m，模擬測試區(qū)域如圖2所示。

圖2中，格子中的方框代表采樣點位置，三角形代表AP點位置。

3.2 仿真結(jié)果比較

為了比較本文所提的PCG 算法與傳統(tǒng)ART、CGM、Jacobi、OMP算法的性能，分別使用這5種算法求解衰減因子，并且比較場強(qiáng)地圖中RSSI 的值與實測RSSI 的值。為了不重復(fù)性展示，選AP2 作為場強(qiáng)地圖的詳細(xì)分布顯示。AP2 發(fā)射信號時，仿真的RSSI 覆蓋情況如圖3所示。

圖2 測試區(qū)域平面圖

圖3（a）、（b）、（c）、（d）、（e）為分別采用ART、Jacobi、CGM、OMP、PCG 算法求解衰減因子并得到的RSSI值?？梢钥闯觯啾扔谄渌惴?，PCG 算法計算衰減因子后得到的RSSI值噪點較少，因此本章提出的PCG算法更接近于室內(nèi)環(huán)境。

考慮3個AP發(fā)射信號時，圖4 為ART、Jacobi、CGM、OMP、PCG 算法求解衰減因子后，得到的RSSI值分布情況與參照組進(jìn)行對比的誤差分析圖。

圖3 5種算法計算出的RSSI值

圖4 中，橫坐標(biāo)是場強(qiáng)地圖中的RSSI 與樣本均值的誤差絕對值，縱坐標(biāo)是誤差百分比。當(dāng)絕對誤差為3 dB，AP1 發(fā)射信號時，PCG 算法對應(yīng)曲線高于OMP、CGM、Jacobi、ART 對應(yīng)曲線分別約為14%，46%，54%和56%；AP2 發(fā)射信號時，PCG 算法對應(yīng)曲線高于OMP、CGM、Jacobi、ART 對應(yīng)曲線分別約為8%，22%，24%和26%；AP3 發(fā)射信號時，PCG 算法對應(yīng)曲線高于OMP、CGM、Jacobi、ART 對應(yīng)曲線分別約為6%，14%，24%和28%。由此說明PCG 算法所求出的信號強(qiáng)度誤差比其他算法所求出的信號強(qiáng)度誤差小，可以得出PCG 算法計算出衰減因子后，構(gòu)建的場強(qiáng)地圖中RSSI覆蓋效果更好，準(zhǔn)確度較高。

可以看出，AP2 在室內(nèi)中心位置，計算出的RSSI誤差最小，AP1 在室外，AP3 在室內(nèi)邊角位置，計算出的誤差相對較大?？梢缘贸觯?dāng)AP 在室內(nèi)的時候，PCG 算法相對于其他算法，構(gòu)建場強(qiáng)地圖的效果更好；當(dāng)AP 點在室外的時候，雖然PCG 算法計算出衰減因子后誤差增大，但構(gòu)建的場強(qiáng)地圖中RSSI覆蓋效果也優(yōu)于其他算法。

3.3 定位效果評估

圖4 不同AP發(fā)射信號時RSSI誤差分析圖

為了評估本文提出的PCG 算法以及WDC-WKNN算法與傳統(tǒng)匹配算法的效果，利用PCG 算法求解衰減因子并構(gòu)建場強(qiáng)地圖，然后利用結(jié)合WDC-WKNN 算法和傳統(tǒng)的WKNN、DC-WKNN 算法進(jìn)行在線定位匹配的誤差比較如圖5所示。

圖5 不同方法進(jìn)行在線匹配的PDF誤差

從圖5 可以看出，誤差在3 m 的時候，PCG-WDCWKNN 算法對應(yīng)的柱形圖高度比PCG-WKNN、PCGDC-WKNN 算法對應(yīng)的柱形圖分別約高0.5%，1.5%，表示提出的WDC-WKNN 算法比傳統(tǒng)的匹配算法定位效果好，精度高。

為了更直觀地分析本文提出的WDC-WKNN 算法的性能，仿真得到PCG-WDC-WKNN、PCG-DCWKNN、PCG-WKNN 算法進(jìn)行定位的誤差CDF 曲線圖，仿真圖如圖6所示。

圖6 不同方法進(jìn)行在線匹配的CDF誤差

從圖6 中看出，當(dāng)都采用PCG 算法求解衰減因子得到場強(qiáng)地圖時，PCG-WDC-WKNN 算法的定位誤差在3 m以內(nèi)的點約占95%，定位誤差在2 m以內(nèi)的點約占50%。而PCG-WKNN、PCG-DC-WKNN 算法的定位誤差在3 m 以內(nèi)的點分別約占90%，70%，定位誤差在2 m 以內(nèi)的點分別約占45%，40%，另外定位誤差超過3.5 m 的概率分別接近3%，20%，可以視為定位完全失敗?？梢缘贸鯬CG-WDC-WKNN 算法與PCGWKNN、PCG-DC-WKNN 算法相比，定位效果較好，本章提出的WDC-WKNN 定位匹配算法比傳統(tǒng)匹配算法的位置定位準(zhǔn)確。

4 結(jié)束語

本文采用了基于電磁傳播反演模型進(jìn)行定位。針對離線階段采集場強(qiáng)工作量大的問題，本文提出了PCG 反演算法，通過實驗得到場強(qiáng)地圖的結(jié)果可以看出，本文算法建立的場強(qiáng)地圖和傳統(tǒng)算法相比，場強(qiáng)信號誤差均有減小。在線階段，針對AP 信號受環(huán)境影響尤為嚴(yán)重的問題，本文提出了改進(jìn)的在線匹配WDC-WKNN算法，仿真結(jié)果顯示該算法在3 m以內(nèi)的累積誤差分布明顯高于傳統(tǒng)算法，說明該算法能很好地將誤差范圍進(jìn)行有效控制。所提的仿真實驗方法也加強(qiáng)了工程與科研人員對電磁傳播的學(xué)習(xí)與應(yīng)用。