王韋剛，周 蓉，張?jiān)苽ィ?韜（南京郵電大學(xué)，江蘇南京 210023）

0 引言

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

1 離線階段

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

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

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

圖1 無(wú)線傳播模型示意圖

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

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

式中：

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

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

Pr(r)——接收信號(hào)功率

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

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

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

式中：

r——傳播距離

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

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

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

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

式中：

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

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

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

E——由級(jí)數(shù)展開(kāi)時(shí)的數(shù)據(jù)估計(jì)的近似性和測(cè)量引起的誤差

1.2 新型反演模式的信號(hào)模型的求解

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

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

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

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

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

式中：

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

k——迭代次數(shù)

Λk——k次迭代索引（列序號(hào)）的集合

λk——第k次迭代找到的索引號(hào)

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，初始梯度方向?yàn)槠?中=[1,...,1]T，k×1維，g0表示初始值為θ0時(shí)的一階偏導(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算法

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

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

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

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

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

式中：

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

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

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

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

2 在線階段

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

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

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

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

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

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

目前廣泛應(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個(gè)問(wèn)題。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

表3 WDC-WKNN算法

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

3 實(shí)驗(yàn)結(jié)果評(píng)估

3.1 仿真環(huán)境

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

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

3.2 仿真結(jié)果比較

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

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

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

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

圖3 5種算法計(jì)算出的RSSI值

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

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

3.3 定位效果評(píng)估

圖4 不同AP發(fā)射信號(hào)時(shí)RSSI誤差分析圖

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

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

從圖5 可以看出，誤差在3 m 的時(shí)候，PCG-WDCWKNN 算法對(duì)應(yīng)的柱形圖高度比PCG-WKNN、PCGDC-WKNN 算法對(duì)應(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 算法求解衰減因子得到場(chǎng)強(qiáng)地圖時(shí)，PCG-WDC-WKNN 算法的定位誤差在3 m以內(nèi)的點(diǎn)約占95%，定位誤差在2 m以內(nèi)的點(diǎn)約占50%。而PCG-WKNN、PCG-DC-WKNN 算法的定位誤差在3 m 以內(nèi)的點(diǎn)分別約占90%，70%，定位誤差在2 m 以內(nèi)的點(diǎn)分別約占45%，40%，另外定位誤差超過(guò)3.5 m 的概率分別接近3%，20%，可以視為定位完全失敗。可以得出PCG-WDC-WKNN 算法與PCGWKNN、PCG-DC-WKNN 算法相比，定位效果較好，本章提出的WDC-WKNN 定位匹配算法比傳統(tǒng)匹配算法的位置定位準(zhǔn)確。

4 結(jié)束語(yǔ)

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