樂(lè)燕芬，湯卓，盛存寶，施偉斌

（上海理工大學(xué)光電信息與計(jì)算機(jī)工程學(xué)院，上海 200093）

1 引言

隨著物聯(lián)網(wǎng)、移動(dòng)智能終端的迅猛發(fā)展，位置相關(guān)的服務(wù)和應(yīng)用受到了廣泛的關(guān)注，尤其在無(wú)線傳感器網(wǎng)絡(luò)（WSN, wireless sensor network）相關(guān)領(lǐng)域，室內(nèi)定位技術(shù)成為研究熱點(diǎn)。由于GPS信號(hào)在室內(nèi)復(fù)雜環(huán)境下迅速衰減，使得這種室外定位技術(shù)無(wú)法有效應(yīng)用于室內(nèi)環(huán)境。近年來(lái)，國(guó)內(nèi)外學(xué)者對(duì)室內(nèi)定位技術(shù)展開了大量的研究，其中基于接收信號(hào)強(qiáng)度（RSS, received signal strength）的方法不需要額外的硬件設(shè)備，具有成本低、易實(shí)現(xiàn)、非視距傳輸?shù)奶攸c(diǎn)，因而成為室內(nèi)定位的重要實(shí)現(xiàn)手段之一[1-3]。

室內(nèi)布局復(fù)雜多變，人員活動(dòng)頻繁，無(wú)線信號(hào)傳播過(guò)程中存在多徑效應(yīng)、陰影效應(yīng)，使信號(hào)的強(qiáng)度與傳播距離具有較強(qiáng)的時(shí)變特性，并依賴于具體應(yīng)用環(huán)境，很難找到能夠準(zhǔn)確刻畫兩者關(guān)系的傳播衰減模型。針對(duì)于此，RSS定位算法中的一大類——位置指紋定位算法可用于解決上述問(wèn)題，該方法需要預(yù)先確定監(jiān)控區(qū)域內(nèi)若干參考點(diǎn)位置RSS信號(hào)的分布，也稱為位置指紋，目標(biāo)節(jié)點(diǎn)通過(guò)RSS分布匹配來(lái)獲取自身定位。定位過(guò)程一般分為離線訓(xùn)練和在線定位這2個(gè)階段。首先在定位區(qū)域內(nèi)布置若干個(gè)位置已知的節(jié)點(diǎn)，也稱為錨節(jié)點(diǎn)（anchor node）。離線訓(xùn)練時(shí)，在定位區(qū)域內(nèi)各參考位置點(diǎn)采集來(lái)自多個(gè)錨節(jié)點(diǎn)的RSS信號(hào)，并結(jié)合物理位置構(gòu)成位置指紋；在線定位階段，目標(biāo)節(jié)點(diǎn)接收錨節(jié)點(diǎn)信號(hào)獲取RSS值，利用模式匹配算法與位置指紋空間內(nèi)的數(shù)據(jù)進(jìn)行匹配，估計(jì)目標(biāo)節(jié)點(diǎn)位置。

基于位置指紋的定位算法，不需要預(yù)設(shè)室內(nèi)信號(hào)的傳播衰減模型，定位精度取決于離線訓(xùn)練階段與在線定位階段的RSS信號(hào)是否符合相同的分布模型。而室內(nèi)復(fù)雜的定位環(huán)境使RSS信號(hào)呈現(xiàn)較大時(shí)變特性，并不是信號(hào)越強(qiáng)的接入點(diǎn)（AP，access point）提供的定位精度越高[4]，直接采用信號(hào)強(qiáng)度進(jìn)行匹配，如radar系統(tǒng)采用的K最近鄰算法[5]，定位精度有限。為了有效挖掘 RSS信號(hào)的內(nèi)在特征，目前很多研究工作集中在利用機(jī)器學(xué)習(xí)的方法對(duì)信號(hào)強(qiáng)度進(jìn)行建模。如文獻(xiàn)[6-7]利用基于核函數(shù)的嶺回歸方法獲取參考位置與RSS信號(hào)的匹配模型，文獻(xiàn)[8]則利用基于核函數(shù)的主成分分析法提取來(lái)自多個(gè)AP的RSS信號(hào)間的非線性特征，在此特征空間內(nèi)進(jìn)行匹配獲得位置估計(jì)。這些方法有效地提高了定位精度，但存在的主要問(wèn)題是定位階段需要進(jìn)行復(fù)雜的計(jì)算。如文獻(xiàn)[8]進(jìn)行在線定位時(shí)，接收到的RSS信號(hào)首先需要與所有參考位置點(diǎn)RSS信號(hào)進(jìn)行核函數(shù)運(yùn)算獲得核矩陣，進(jìn)行數(shù)據(jù)修正，以保證核矩陣數(shù)據(jù)中心化條件，在此基礎(chǔ)上，求取該矩陣的特征值和特征向量，并最終獲得該采樣RSS的特征指紋，這一定位過(guò)程引起資源的大量占用，并不適用于移動(dòng)節(jié)點(diǎn)主動(dòng)定位的場(chǎng)合。

為減少定位階段的匹配計(jì)算量，文獻(xiàn)[4]提出了基于信息熵進(jìn)行 AP子集選擇的方法。在監(jiān)控范圍內(nèi)所有能檢測(cè)的 AP中，選擇對(duì)所有參考位置點(diǎn)信息增益最大的k個(gè) AP構(gòu)成特征輸入，并按照接收到的這k個(gè)RSS信號(hào)的相似度對(duì)參考位置點(diǎn)進(jìn)行聚類。在線定位時(shí)根據(jù)接收到的RSS信號(hào)判定目標(biāo)所屬的簇，然后在該簇內(nèi)利用決策樹進(jìn)行精確定位。這種算法不考慮參考位置點(diǎn)的物理位置，按AP子集的RSS信號(hào)進(jìn)行聚類，有效地減少了定位階段的計(jì)算量。但需要指出的是，AP子集的選擇是基于監(jiān)控范圍內(nèi)所有參考位置點(diǎn)接收的 RSS，考慮到 AP具有區(qū)域性，即同一個(gè) AP對(duì)不同區(qū)域具有不同的信息熵貢獻(xiàn)率，這種方法所選出的 AP子集對(duì)部分區(qū)域并不一定最佳，導(dǎo)致部分區(qū)域定位精度不高。文獻(xiàn)[9-10]則考慮不同AP在同一位置的RSS具有相關(guān)性的特點(diǎn)，剔除包含冗余信息的AP，通過(guò)最優(yōu)AP子集匹配完成位置估計(jì)。此類算法需要在定位階段對(duì)收到的各個(gè)維度RSS進(jìn)行高斯擬合，并計(jì)算各AP的RSS分布聯(lián)合互信息，利用最小化互信息準(zhǔn)則獲取包含信息量最多的最優(yōu) AP子集。指紋匹配過(guò)程中，以 KL散度為標(biāo)準(zhǔn)計(jì)算待定位節(jié)點(diǎn)與指紋庫(kù)中所有參考位置點(diǎn)的高維度高斯密度函數(shù)的相異度，并選擇相異度最低的位置參考點(diǎn)作為位置估計(jì)。此類算法的優(yōu)點(diǎn)是離線訓(xùn)練階段數(shù)據(jù)庫(kù)保留的 AP數(shù)量減少，降低了數(shù)據(jù)庫(kù)規(guī)模，但在線定位階段，所選的最優(yōu) AP需要與庫(kù)中所有參考點(diǎn)的AP子集進(jìn)行RSS分布差異度分析，時(shí)間復(fù)雜度較高。文獻(xiàn)[11-12]分別在室內(nèi)和室外環(huán)境下，利用目標(biāo)節(jié)點(diǎn)與參考位置點(diǎn)是否接收相同AP集合的信號(hào)來(lái)判斷兩者的距離，來(lái)剔除不可能的參考位置點(diǎn)。而實(shí)際環(huán)境中，相距30 m的2個(gè)位置點(diǎn)接收的同一個(gè)錨節(jié)點(diǎn)的信號(hào)強(qiáng)度差值可能達(dá)到10 dBm，使這一方法只適用于粗定位。文獻(xiàn)[13]則針對(duì)移動(dòng)目標(biāo)的運(yùn)動(dòng)狀況和實(shí)際環(huán)境布局，建立基于位置的馬爾可夫鏈來(lái)剔除不可能的位置跳變，這在實(shí)際應(yīng)用中存在一定困難。當(dāng)定位不是連續(xù)密集進(jìn)行時(shí)，目標(biāo)在較短的時(shí)間內(nèi)可能越過(guò)多個(gè)參考網(wǎng)格，很難明確界定運(yùn)動(dòng)目標(biāo)的物理可達(dá)范圍，這在某種程度上限制了此方法的應(yīng)用。

上述文獻(xiàn)都試圖通過(guò)最優(yōu) AP子集選擇來(lái)減少位置指紋算法的計(jì)算復(fù)雜度或數(shù)據(jù)存儲(chǔ)量，而在 WSN室內(nèi)定位中，若參考位置點(diǎn)分布密度大或者由于定位區(qū)域廣導(dǎo)致參考位置點(diǎn)分布數(shù)量大，則上述方法對(duì)定位性能的改善有限。同時(shí)考慮到室內(nèi)環(huán)境復(fù)雜多變，無(wú)線信號(hào)傳播特性與局部的物理空間密切相關(guān)，統(tǒng)一的選擇策略并不一定局部最佳，因此提出了基于不同分布密度的位置指紋、精度漸進(jìn)的室內(nèi)定位算法，在保證定位精度的同時(shí)，降低定位的能耗、計(jì)算復(fù)雜度和存儲(chǔ)空間。該方法把定位區(qū)域按錨節(jié)點(diǎn)的信號(hào)傳達(dá)率分成若干局部空間，并按分布密度把參考位置點(diǎn)分成2類，分別為粗網(wǎng)格和細(xì)網(wǎng)格。定位時(shí)利用空間濾波法確定可能的局部空間集合，并利用主成分分析法（PCA，principal component analysis）[14-15]提取的粗網(wǎng)格的位置指紋特征匹配確定這些局部空間集合中目標(biāo)節(jié)點(diǎn)可能所在的初步位置，最后利用WKNN（weighted K nearest nodes）方法完成細(xì)網(wǎng)格的精確匹配。所提出的方法兼顧了地理位置特征和RSS信號(hào)的分布特點(diǎn)，在降低運(yùn)算量的同時(shí)保證定位精度。

2 算法的框架與原理

本文提出的多分布密度位置指紋定位算法，將大監(jiān)控區(qū)域按照環(huán)境特點(diǎn)劃分為多個(gè)局部空間，每個(gè)局部空間內(nèi)選擇若干個(gè)粗網(wǎng)格和分布相對(duì)密集的細(xì)網(wǎng)格。算法具體步驟如下。

步驟1離線訓(xùn)練階段

這一階段需要獲取錨節(jié)點(diǎn)在每個(gè)局部空間的分布及粗、細(xì)網(wǎng)格的指紋特征。

1） 為每個(gè)局部空間建立錨節(jié)點(diǎn)信號(hào)的覆蓋向量。該覆蓋向量具體描述了在特定的物理環(huán)境下各錨節(jié)點(diǎn)在每個(gè)局部空間的信號(hào)分布。

2） 在局部空間內(nèi)選擇若干粗網(wǎng)格，通過(guò) PCA訓(xùn)練離線RSS信號(hào)，獲取可描述粗網(wǎng)格特征的指紋數(shù)據(jù)庫(kù)。

3） 在每個(gè)局部空間的細(xì)網(wǎng)格點(diǎn)采集RSS信號(hào)，獲取描述細(xì)網(wǎng)格的位置指紋。

步驟2在線定位階段

這一階段，目標(biāo)節(jié)點(diǎn)實(shí)時(shí)采集來(lái)自錨節(jié)點(diǎn)的RSS信號(hào)，完成自身定位。

1） 采用空間濾波法確定目標(biāo)節(jié)點(diǎn)可能的局部空間。采集RSS信號(hào)獲得動(dòng)態(tài)覆蓋向量，與各局部空間的覆蓋向量進(jìn)行比較，選擇漢明距離較小的若干局部空間作為可能區(qū)域。

2） RSS信號(hào)經(jīng)PCA變換后獲取主成分，與局部空間內(nèi)的粗網(wǎng)格的指紋數(shù)據(jù)特征進(jìn)行匹配，選擇歐式距離最小的若干粗網(wǎng)格作為目標(biāo)節(jié)點(diǎn)的位置范圍。

3） 在粗網(wǎng)格內(nèi)，采用WKNN方法，選取匹配度最高的K個(gè)細(xì)網(wǎng)格加權(quán)平均后作為估計(jì)位置。

上述方法中，離線階段不需要增加樣本采集數(shù)量，在線定位階段節(jié)點(diǎn)的計(jì)算量主要集中在粗、細(xì)網(wǎng)格的匹配過(guò)程，但不需要與定位區(qū)域全部指紋進(jìn)行匹配，減少了節(jié)點(diǎn)對(duì)資源（包括存儲(chǔ)空間、能量）的消耗。

2.1 空間濾波法

位置指紋定位是利用室內(nèi)空間內(nèi)，尤其存在墻壁遮擋等情況時(shí)，RSS信號(hào)的衰減體現(xiàn)出很強(qiáng)的空間性?？臻g濾波法綜合考慮物理空間的具體情況和信號(hào)衰減特性之間的相關(guān)性，認(rèn)為目標(biāo)節(jié)點(diǎn)與網(wǎng)格點(diǎn)越接近，則兩者接收到的RSS信號(hào)越相似，利用這一特性完成局部空間的粗定位。

局部空間內(nèi)的RSS信號(hào)分布用覆蓋向量C描述，CM=[IM1,IM2,…,IML]是第M個(gè)局部空間的覆蓋向量。如果在該局部空間內(nèi)能連續(xù)接收到第i個(gè)錨節(jié)點(diǎn)的RSS信號(hào)，則IMi=1，否則IMi=0。具體實(shí)施時(shí)，離線訓(xùn)練階段的連續(xù)接收可以定義為：該錨節(jié)點(diǎn)的信息可以被該局部空間內(nèi)隨機(jī)運(yùn)動(dòng)的節(jié)點(diǎn)在90%的采樣時(shí)間內(nèi)接收到或在90%的細(xì)網(wǎng)格接收到。

覆蓋向量C為二進(jìn)制數(shù)據(jù)類型，因此適合采用漢明距離來(lái)表征2個(gè)向量間的差異大小，若目標(biāo)節(jié)點(diǎn)定位過(guò)程中接收的 RSS信號(hào)分布向量為C′，則

通過(guò)式（1）對(duì)所有局部空間進(jìn)行匹配，若dH（CM,C′）＜αL，則該局部空間作為候選空間。參數(shù)α（0 ＜α＜ 1）的大小影響算法的復(fù)雜度和定位的準(zhǔn)確度。若α過(guò)大，則空間濾波性能不佳，可能引入較多的無(wú)效區(qū)域；若α過(guò)小，在RSS存在較大時(shí)變時(shí)，可能漏掉有效區(qū)域。α的選擇應(yīng)參考實(shí)際應(yīng)用環(huán)境RSS的時(shí)變情況。

通過(guò)空間濾波，目標(biāo)節(jié)點(diǎn)可能的局部空間集合定義為P′={CM,dH（CM,C′）＜αL}，且|P′|=M′。下面將通過(guò) PCA提取粗網(wǎng)格的特征，通過(guò)特征匹配確定目標(biāo)節(jié)點(diǎn)處于局部空間集合P′的那些粗網(wǎng)格內(nèi)。

2.2 PCA粗定位算法

在大監(jiān)控區(qū)域內(nèi)可能布置較多的錨節(jié)點(diǎn)，目標(biāo)節(jié)點(diǎn)在某一位置可能同時(shí)接收到10多個(gè)錨節(jié)點(diǎn)的信號(hào)。常用的降低定位算法計(jì)算復(fù)雜度的方法是按某種策略選擇最優(yōu)AP或錨節(jié)點(diǎn)集合。不同于以上方法，PCA經(jīng)過(guò)線性變換從來(lái)自各錨節(jié)點(diǎn)的 RSS信號(hào)中提取包含原始信息的少數(shù)幾個(gè)綜合指標(biāo)，這些指標(biāo)互不相關(guān)，也稱為主成分，在降維的同時(shí)保持了信號(hào)變量的總方差不變。PCA變換可用式（2）表示。

其中，S=[s1,s2,…,sL]代表目標(biāo)節(jié)點(diǎn)定位中實(shí)時(shí)接收到的L個(gè)錨節(jié)點(diǎn)的 RSS信號(hào)，若無(wú)法接收某個(gè)錨節(jié)點(diǎn)的信號(hào)，則相應(yīng)的值設(shè)為最小值-95 dBm；是變換后獲取的主成分；變換矩陣A是L×K維矩陣，表明了每個(gè)錨節(jié)點(diǎn)RSS對(duì)主成分的貢獻(xiàn)量。從式（2）中可看出，PCA在降維時(shí)并沒(méi)丟棄原RSS數(shù)據(jù)，而是融合了所有錨節(jié)點(diǎn)的信息。文獻(xiàn)[11]的研究也表明該方法可有效提高定位精度。值得說(shuō)明的是，PCA提取的是數(shù)據(jù)間的線性特征，而二階以上的高維非線性關(guān)系需要通過(guò)其他方法，如基于核函數(shù)的PCA來(lái)提取[8]，但后者定位階段涉及復(fù)雜的計(jì)算，因此，本文使用PCA訓(xùn)練RSS數(shù)據(jù)，獲得線性變換矩陣A，把S′作為局部空間內(nèi)粗網(wǎng)格的指紋特征，把目標(biāo)定位到某一粗網(wǎng)格內(nèi)。

2.2.1 粗網(wǎng)格的PCA變換

設(shè)整個(gè)定位區(qū)域劃分為多個(gè)局部空間，每個(gè)局部空間內(nèi)有若干個(gè)粗網(wǎng)格，共有N個(gè)粗網(wǎng)格。離線階段在每個(gè)粗網(wǎng)格上采集來(lái)自L個(gè)錨節(jié)點(diǎn)的RSS信號(hào)，將多次采集的RSS均值作為該粗網(wǎng)格li（xi,yi）的原始位置指紋信息Si=[s1,s2,…,sL]T。全部粗網(wǎng)格的原始位置指紋構(gòu)成了一個(gè)N×L維的矩陣S，相當(dāng)于L維的N個(gè)訓(xùn)練數(shù)據(jù)。在進(jìn)行PCA變換前，首先保證數(shù)據(jù)空間滿足中心化的條件，對(duì)S按式（3）進(jìn)行調(diào)整。

根據(jù)式（4）計(jì)算數(shù)據(jù)空間的協(xié)方差矩陣CΓ。

協(xié)方差矩陣CΓ的特征值{λ1,λ2,…,λL}和特征向量{V1,V2,…,VL}滿足

將特征值從大到小排列，并取前K個(gè)最大的特征值λ1＞λ2＞…＞λK及對(duì)應(yīng)的特征向量V1,V2,…,VK。

PCA保證所選擇的轉(zhuǎn)換矩陣A使得

此時(shí)滿足

這樣，通過(guò)PCA處理，原始位置指紋S包含的RSS信號(hào)變換為包含K個(gè)主成分的S′特征位置指紋。

2.2.2 粗網(wǎng)格定位

在線定位階段，目標(biāo)節(jié)點(diǎn)采集各個(gè)錨節(jié)點(diǎn)的RSS信號(hào)F=[rss1,rss2,…,rssL]，通過(guò)矩陣線性變換，獲得表征其主成分的特征指紋F′=FA。假設(shè)空間濾波后匹配的局部空間內(nèi)共有M個(gè)粗網(wǎng)格，則計(jì)算F′與粗網(wǎng)格特征指紋S′的歐式距離，如式（8）所示。其中，Dj（F′,S′j）表征F′與第j個(gè)粗網(wǎng)格的相似程度，其值越小，兩者越相似。取Dj（F′,S′j）值最小的粗網(wǎng)格作為目標(biāo)節(jié)點(diǎn)初步估計(jì)位置。

2.3 細(xì)網(wǎng)格匹配

細(xì)網(wǎng)格的匹配也是定位的最終階段，可以根據(jù)具體應(yīng)用選取目前已有且定位精度較高的方法，如基于核函數(shù)的 PCA方法、基于貝葉斯最大估計(jì)的后驗(yàn)概率估計(jì)法等。由于粗定位已經(jīng)把目標(biāo)鎖定于粗網(wǎng)格，因此不管采用何種方法，在線定位階段均不涉及大量的運(yùn)算。需要說(shuō)明的是，這些方法均使用高斯模型來(lái)描述室內(nèi)復(fù)雜環(huán)境對(duì) RSS可能產(chǎn)生的誤差[15-16]，同時(shí)離線階段的工作量仍然較大，如基于核函數(shù)的 PCA方法，需要完成細(xì)網(wǎng)格點(diǎn)的特征提取，而基于后驗(yàn)概率估計(jì)的定位方法，則需要利用最大似然估計(jì)完成每個(gè)細(xì)網(wǎng)格點(diǎn)的高斯分布參數(shù)。本算法采用 WKNN方法，離線階段需要采集RSS作為原始指紋，而不需要其他額外工作，在線階段則只需計(jì)算目標(biāo)節(jié)點(diǎn)采集的 RSS與匹配粗網(wǎng)格內(nèi)細(xì)網(wǎng)格的歐式距離，選取距離最小的R個(gè)細(xì)網(wǎng)格位置的加權(quán)平均作為目標(biāo)節(jié)點(diǎn)的最終位置估計(jì)，如式（9）所示。

其中，w是目標(biāo)節(jié)點(diǎn)估計(jì)位置；wr是選取的R個(gè)匹配的細(xì)網(wǎng)格位置；Pr代表wr網(wǎng)格歸一化的權(quán)重系數(shù)，表示為

其中，Di（F,Si）是目標(biāo)節(jié)點(diǎn)采集的RSS信號(hào)F與第i個(gè)細(xì)網(wǎng)格點(diǎn)的原始位置指紋S的歐式距離。

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

3.1 實(shí)驗(yàn)設(shè)置

為了評(píng)估本文所提出定位算法的性能，在上海理工大學(xué)光電大樓進(jìn)行了數(shù)據(jù)采集和定位實(shí)驗(yàn)。實(shí)驗(yàn)區(qū)域?yàn)榈?層的大廳和走廊位置，大小為36 m×14 m。其中，大廳中有會(huì)客沙發(fā)、自習(xí)桌椅等物體，且有較多的人員走動(dòng)；目標(biāo)定位區(qū)域均勻劃分為1.8 m×1.8 m大小的90個(gè)網(wǎng)格。兩側(cè)走廊以4.2 m為間隔均勻布置了共18個(gè)錨節(jié)點(diǎn)。對(duì)每個(gè)網(wǎng)格點(diǎn)進(jìn)行2 min的RSS信號(hào)采集，從中隨機(jī)抽取10個(gè)RSS觀測(cè)向量，將其均值作為測(cè)試數(shù)據(jù)；其余的RSS觀測(cè)向量均值處理后作為原始位置指紋數(shù)據(jù)。信號(hào)采集過(guò)程中，可以觀察到由于電梯井、樓梯房間墻壁等的阻擋以及人員走動(dòng)等因素，在網(wǎng)格點(diǎn)收到的RSS信號(hào)并不是均勻地來(lái)自所有錨節(jié)點(diǎn)。有的錨節(jié)點(diǎn)能收到100多次信號(hào)，而有的只有30多次信號(hào)，甚至有些網(wǎng)格點(diǎn)會(huì)無(wú)法收到部分錨節(jié)點(diǎn)的信號(hào)，并且表現(xiàn)為持續(xù)性無(wú)法接收，這些未接收到的RSS信號(hào)統(tǒng)一用最小值-95 dBm填充。

圖1給出了在某一測(cè)試點(diǎn)獲取的來(lái)自同一個(gè)錨節(jié)點(diǎn)的RSS信號(hào)分布直方圖，圖中的曲線是RSS信號(hào)分布的概率密度函數(shù)。從圖1中可看出，即使在同一位置，來(lái)自同一個(gè)錨節(jié)點(diǎn)的RSS也是隨時(shí)間變化的。

圖1 RSS信號(hào)分布直方圖

3.2 定位性能評(píng)估

3.2.1 空間濾波對(duì)定位精度的影響

根據(jù) RSS信號(hào)的分布特點(diǎn)并結(jié)合定位物理環(huán)境，實(shí)際目標(biāo)定位區(qū)域分為5個(gè)局部空間，對(duì)應(yīng)的覆蓋向量為C=[C1,C2,C3,C4,C5]T。如1#區(qū)域C1=[1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,0,1]表明此區(qū)域內(nèi)的網(wǎng)格點(diǎn)無(wú)法接收到 15#和 17#錨節(jié)點(diǎn)的信號(hào)。隨機(jī)抽取30個(gè)網(wǎng)格點(diǎn)的測(cè)試數(shù)據(jù)進(jìn)行空間濾波，結(jié)果如表1所示。

表1 局部空間匹配結(jié)果

由表1可以看出，當(dāng)設(shè)定覆蓋向量C漢明距離dH=0，也即要求覆蓋向量完全匹配，22個(gè)網(wǎng)格點(diǎn)確定了唯一的所處局部空間，還有8個(gè)網(wǎng)格點(diǎn)與5個(gè)局部區(qū)域的覆蓋向量都存在漢明距離，無(wú)法判定所處的局部區(qū)域。隨著漢明距離的增大，匹配的局部區(qū)域數(shù)也增多。當(dāng)漢明距離為5時(shí)，其中有23個(gè)網(wǎng)格與3個(gè)局部空間的漢明距離小于或等于5，甚至有2個(gè)網(wǎng)格與所有局部空間的漢明距離都不大于5。因此在本定位區(qū)域內(nèi)，dH選擇2，通過(guò)空間濾波，使得目標(biāo)節(jié)點(diǎn)初步定位在1～3個(gè)局部空間內(nèi)，有效地減少了指紋匹配量。

3.2.2 粗網(wǎng)格定位性能分析

針對(duì)實(shí)驗(yàn)中目標(biāo)定位區(qū)域的具體環(huán)境特點(diǎn)，1#、2#、4#和5#局部區(qū)域不再劃分粗網(wǎng)格，也即每個(gè)局部區(qū)域本身就是一個(gè)粗網(wǎng)格，并設(shè)置2個(gè)參考位置點(diǎn)；而3#局部區(qū)域即大廳13 m×14 m的空間內(nèi)劃分2個(gè)粗網(wǎng)格，每個(gè)粗網(wǎng)格內(nèi)設(shè)置8個(gè)參考位置點(diǎn)。實(shí)驗(yàn)時(shí)在粗網(wǎng)格內(nèi)的參考位置點(diǎn)各采集 80次RSS信號(hào)，由此產(chǎn)生1 920個(gè)訓(xùn)練數(shù)據(jù)用于PCA分析，獲得變換矩陣A和18個(gè)特征值。

圖2給出了實(shí)驗(yàn)中獲得的RSS信號(hào)提取的特征值，18個(gè)錨節(jié)點(diǎn)對(duì)應(yīng)18個(gè)特征值。特征值越大，說(shuō)明相應(yīng)的主成分包含的原始信息越多。根據(jù)特征值的信息貢獻(xiàn)率，可確定提取的主元個(gè)數(shù)。實(shí)驗(yàn)中選取9個(gè)主元，此時(shí)

圖2 粗網(wǎng)格PCA變換后提取的特征值

即 9個(gè)主元提供的信息占原 18個(gè)錨節(jié)點(diǎn)的 RSS所包含信息的90%以上。因此實(shí)驗(yàn)中的轉(zhuǎn)換矩陣A是18×9維的矩陣，粗網(wǎng)格內(nèi)參考位置點(diǎn)的指紋由S=[s1,s2,…,s18]變換為S′=[s′1,s′2,…,s′9]。在線采集的RSS信號(hào)F=[rss1,rss2,…,rss18]經(jīng)PCA 變換為F′。

3.2.3 定位性能評(píng)估

實(shí)驗(yàn)采用定位的平均誤差ME（mean error）和定位誤差的累計(jì)密度函數(shù)（CDF, cumulative density function）作為標(biāo)準(zhǔn)來(lái)評(píng)估算法的性能。

圖 3給出了本文提出的 A-WKNN算法與WKNN算法、InfoGain[4]算法、Bayes-PCA算法[15]的累計(jì)誤差分布函數(shù)。其中本文的算法空間濾波中參數(shù)dH=2，匹配粗網(wǎng)格數(shù)為4，匹配細(xì)網(wǎng)格數(shù)為4，加權(quán)平均后作為估算位置；WKNN算法中選取4個(gè)最近鄰細(xì)網(wǎng)格點(diǎn)加權(quán)平均后作為估算位置；InfoGain算法則從18個(gè)錨節(jié)點(diǎn)中提取信息熵最大的10個(gè)錨節(jié)點(diǎn)的RSS作為特征；Bayes-PCA算法對(duì)所有的細(xì)網(wǎng)格進(jìn)行 PCA變換獲得特征指紋庫(kù)，再選取后驗(yàn)概率最大的4個(gè)細(xì)網(wǎng)格加權(quán)平均后作為估算位置。

圖3 4種定位算法誤差累計(jì)分布

實(shí)驗(yàn)結(jié)果表明，WKNN算法平均定位誤差為1.91 m，InfoGain算法平均定位誤差為 2.28 m，Bayes-PCA算法平均定位誤差為1.74 m，本文所提算法平均定位誤差為1.82 m。結(jié)合圖3可知，本文提出的算法在降低能耗時(shí)并未犧牲定位精度。此外也采用文獻(xiàn)[8]中提出的 Kernel-PCA算法進(jìn)行了定位。根據(jù)本實(shí)驗(yàn)定位區(qū)域 RSS信號(hào)的實(shí)際分布特點(diǎn)，算法中高斯核寬度ε取2，提取20個(gè)特征，實(shí)驗(yàn)結(jié)果與文獻(xiàn)所報(bào)道的定位精度存在很大差距，這可能是由于實(shí)驗(yàn)場(chǎng)景不同使得RSS特征不一致或參數(shù)未優(yōu)化而導(dǎo)致。

實(shí)驗(yàn)中也發(fā)現(xiàn)，由于特征值貢獻(xiàn)率的不同，主元數(shù)量K的選擇對(duì)定位性能有很大的影響。主元數(shù)量過(guò)多使計(jì)算量增大，而過(guò)小則可能會(huì)損失較多的原始信息。圖 4給出了選取不同主元數(shù)量時(shí)的PCA重建誤差，誤差計(jì)算如式（6）所示。當(dāng)主元數(shù)在7個(gè)以上時(shí)，重建誤差小于35，意味著這幾個(gè)主元可以較好反映原 RSS信息。不過(guò)值得一提的是，RSS信號(hào)與環(huán)境密切相關(guān)，當(dāng)環(huán)境中存在很強(qiáng)的非線性噪聲時(shí)，PCA可能因無(wú)法剔除噪聲而不能有效提取信息。

圖4 原RSS信號(hào)與PCA重建信號(hào)之間的誤差

圖5給出了進(jìn)行PCA變換時(shí)選擇不同主元數(shù)量對(duì)定位精度的影響。從圖5中可看出，主元數(shù)量與定位精度兩者并不是正相關(guān)的關(guān)系，當(dāng)采用過(guò)多的主元時(shí)，數(shù)據(jù)在這些主元方向都進(jìn)行了投影，反而模糊了信號(hào)特征之間的差異。實(shí)際應(yīng)用時(shí)應(yīng)根據(jù)錨節(jié)點(diǎn)的數(shù)量選擇合適的主元數(shù)量，以達(dá)到最佳的特征提取，同時(shí)兼顧系統(tǒng)定位精度和計(jì)算量的要求。

圖5 PCA變換中取不同主元數(shù)量對(duì)定位精度的影響

在指紋定位算法中，錨節(jié)點(diǎn)的分布密度是影響定位性能的重要參數(shù)。本實(shí)驗(yàn)中大廳走廊兩側(cè)共布置了 18個(gè)錨節(jié)點(diǎn)，不考慮位置分布對(duì)定位性能的影響，實(shí)驗(yàn)中考察了布置6個(gè)、10個(gè)、14個(gè)和18個(gè)錨節(jié)點(diǎn)時(shí)定位性能的變化。由于錨節(jié)點(diǎn)的數(shù)量變化，相應(yīng)的主元個(gè)數(shù)也需要調(diào)整。圖6給出了不同錨節(jié)點(diǎn)和不同主元數(shù)量時(shí)算法的定位性能。

圖6 定位平均誤差隨錨節(jié)點(diǎn)數(shù)和主元數(shù)變化的情況

圖6中可以看出，錨節(jié)點(diǎn)數(shù)量與定位精度之間并沒(méi)有確定的相關(guān)性。具體分析如下，在布置 18個(gè)錨節(jié)點(diǎn)的情況下，主元數(shù)量為 10時(shí)，定位平均誤差為1.81 m；在布置10個(gè)錨節(jié)點(diǎn)，主元數(shù)量取6時(shí)，定位平均誤差為1.89 m；而在取5個(gè)主元數(shù)時(shí)，10個(gè)錨節(jié)點(diǎn)的情況定位誤差最小。這說(shuō)明通過(guò)選擇合適的主元數(shù)量，錨節(jié)點(diǎn)數(shù)量的變化對(duì)本方法的定位精度影響不大。實(shí)際應(yīng)用時(shí)，選擇合適的錨節(jié)點(diǎn)數(shù)量，可以在保證定位精度的同時(shí)大幅降低定位計(jì)算量，減少節(jié)點(diǎn)能耗。

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

基于 RSS的指紋定位技術(shù)，從減小定位計(jì)算量、降低能耗的角度提出了一種基于不同分布密度指紋的室內(nèi)定位算法。該算法考慮到某些室內(nèi)環(huán)境中既有相對(duì)空曠的空間，又有眾多墻體等障礙物或狹長(zhǎng)走廊等復(fù)雜的環(huán)境特點(diǎn)，結(jié)合實(shí)際物理環(huán)境和RSS分布，把定位區(qū)域劃分為多個(gè)局部區(qū)域及相應(yīng)的RSS信號(hào)覆蓋向量。在局部區(qū)域內(nèi)又設(shè)定稀疏分布的粗網(wǎng)格，離線階段通過(guò) PCA提取特征主元作為粗定位的位置指紋數(shù)據(jù)；在線階段通過(guò)覆蓋向量及 PCA線性變換確定目標(biāo)節(jié)點(diǎn)的初步位置，再利用 WKNN算法由分布相對(duì)密集的參考位置點(diǎn)確定最終的估算位置。實(shí)驗(yàn)表明本文提出的算法在有效減少定位階段節(jié)點(diǎn)能耗的同時(shí)保持了定位精度，同時(shí)降低了錨節(jié)點(diǎn)的分布密度對(duì)定位結(jié)果的影響。但本實(shí)驗(yàn)還未實(shí)現(xiàn)針對(duì)更大定位區(qū)域及移動(dòng)目標(biāo)的實(shí)時(shí)定位，這也是本算法下一階段的研究目標(biāo)。