基于聯(lián)合分簇和LASSO 的室內(nèi)指紋定位算法

樂(lè)燕芬，金施嘉珞，朱一鳴，施偉斌

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

引 言

智能移動(dòng)設(shè)備和無(wú)線傳感器網(wǎng)絡(luò)相關(guān)技術(shù)的融合發(fā)展，使基于位置的服務(wù)（Location?based servic?es，LBSs）如展覽館、倉(cāng)庫(kù)、商場(chǎng)等樓宇環(huán)境內(nèi)的定位、導(dǎo)航等受到越來(lái)越多的關(guān)注［1］。如何在室內(nèi)復(fù)雜的環(huán)境布局下實(shí)時(shí)獲得理想的定位精度成為當(dāng)前的研究熱點(diǎn)之一。相比較基于無(wú)線信號(hào)到達(dá)角度或到達(dá)時(shí)間的定位算法，基于接收信號(hào)強(qiáng)度（Received signal strength，RSS）的定位方法由于只利用無(wú)線終端的信號(hào)收發(fā)功能即可實(shí)現(xiàn)而獲得廣泛的研究［2?4］。利用位置已知的接入點(diǎn)（Access point，AP）或錨節(jié)點(diǎn)（Anchor）來(lái)確定目標(biāo)位置是其中一種方案［5?6］，但實(shí)際應(yīng)用中，由于室內(nèi)無(wú)線信號(hào)傳播中存在的多徑現(xiàn)象、斑塊效應(yīng)和天線方向等因素，很難有確定的信號(hào)傳播模型能準(zhǔn)確描述信號(hào)衰減量與傳播距離之間的關(guān)系。因此基于無(wú)線信號(hào)地圖（Radio map）的位置指紋定位算法獲得了國(guó)內(nèi)外學(xué)者的關(guān)注。該方法在目標(biāo)監(jiān)測(cè)區(qū)域內(nèi)預(yù)先設(shè)立物理位置已知的參考位置點(diǎn)，構(gòu)建反映區(qū)域無(wú)線信號(hào)分布的位置指紋庫(kù)；在線定位時(shí)，通過(guò)實(shí)時(shí)接收的RSS 信號(hào)與指紋庫(kù)中各參考位置的指紋進(jìn)行匹配來(lái)估算目標(biāo)位置。如常用的K近鄰（K?nearest neighbor，KNN）和加權(quán)KNN（WeightedK?nearest neighbor，WKNN）算法，選取指紋庫(kù)中與在線RSS 值歐氏距離最近的K個(gè)參考位置點(diǎn)，其質(zhì)心或加權(quán)質(zhì)心最為目標(biāo)的估算位置。這一方法簡(jiǎn)單高效，易于實(shí)現(xiàn)，但定位精度相對(duì)不高。

基于位置指紋庫(kù)的定位方法，目前很多研究工作主要集中在兩方面：提高定位精度［7?11］和減少定位階段的匹配復(fù)雜度來(lái)提高算法的實(shí)時(shí)性［12?16］。對(duì)于前者，研究的方向具有多樣性。如文獻(xiàn)［7］采用優(yōu)化的WKNN 算法，首先用自適應(yīng)卡爾曼濾波器對(duì)在線接收的RSS 信號(hào)進(jìn)行濾波，降低環(huán)境噪聲影響，同時(shí)采用Memetic 算法確定K個(gè)最近鄰參考位置點(diǎn)的權(quán)值；文獻(xiàn)［8?10］則采用機(jī)器學(xué)習(xí)的方法進(jìn)行建模，其中文獻(xiàn)［8］基于核嶺回歸（Kernel?ridge，KR）獲取參考位置與RSS 信號(hào)的匹配模型，而文獻(xiàn)［9］首先利用線性判別法對(duì)原始指紋庫(kù)提取主要特征，再用這些特征值訓(xùn)練梯度提升決策樹構(gòu)建學(xué)習(xí)器進(jìn)行定位。文獻(xiàn)［10］采用深度學(xué)習(xí)中的Autoencoder，利用大量的訓(xùn)練樣本基于極限學(xué)習(xí)機(jī)完成定位。文獻(xiàn)［11］則通過(guò)核主成分分析法提取RSS 信號(hào)間的非線性特征，在特征空間進(jìn)行指紋匹配獲得估計(jì)位置。這些方法均涉及較大的計(jì)算量，提升了目標(biāo)的位置估計(jì)精度。對(duì)于后者，分簇是目前研究較多的方法，如文獻(xiàn)［12］基于信息熵對(duì)離線階段的參考位置點(diǎn)進(jìn)行分簇，構(gòu)建接入點(diǎn)（Access point，AP）子集；文獻(xiàn)［13?14］采用AP 聚類算法對(duì)參考位置點(diǎn)進(jìn)行分簇。上述方法均涉及每個(gè)參考點(diǎn)之間RSS 信號(hào)相似度的計(jì)算，一般采用信號(hào)歐式距離的倒數(shù)作為相似度，有一定的計(jì)算量。另有部分文獻(xiàn)［15?16］采用錨節(jié)點(diǎn)的覆蓋向量對(duì)參考位置點(diǎn)進(jìn)行分簇。具有相似覆蓋向量的參考位置點(diǎn)歸為一簇。只涉及二進(jìn)制的漢明距離計(jì)算，運(yùn)算簡(jiǎn)單。這些方法都基于RSS 信號(hào)特征，要求離線階段錨節(jié)點(diǎn)的信號(hào)分布較穩(wěn)定。聚類對(duì)定位精度最大的影響是，若在線階段簇匹配錯(cuò)誤，則會(huì)引入粗大定位誤差。

本文所提算法的基礎(chǔ)是分簇和機(jī)器學(xué)習(xí)，首先充分利用復(fù)雜環(huán)境下RSS 信號(hào)的分布特點(diǎn)，提出了基于RSS 信號(hào)覆蓋向量的聯(lián)合分簇方法，綜合參考位置點(diǎn)覆蓋向量的相似度和物理位置分布對(duì)參考位置點(diǎn)進(jìn)行聚類，盡可能避免簇匹配錯(cuò)誤；其次針對(duì)簇匹配后的二次精確定位，參考位置點(diǎn)RSS 樣本數(shù)量少，模型容易出現(xiàn)過(guò)擬合的問(wèn)題，引入正則項(xiàng)，選擇簡(jiǎn)單的線性回歸模型結(jié)合L1范數(shù)正則化的最小絕對(duì)值收縮和選擇因子（Least absolute shrinkage and selection operator，LASSO）算法［17］獲得稀疏目標(biāo)解。所提出的分簇方法兼顧RSS 信號(hào)的分布特征和物理位置布局，簇內(nèi)LASSO 算法在降低計(jì)算量的同時(shí)盡可能提高定位精度。

1 算法框架和設(shè)計(jì)

本文提出的基于聯(lián)合分簇（Hybrid clustering，HC）和LASSO 的室內(nèi)定位算法，命名為HC?LAS?SO。圖1 給出了算法的框架。

定位算法分離線和在線2 個(gè)階段。離線階段通過(guò)采集的各參考位置點(diǎn)的RSS 信號(hào)確定覆蓋向量，并據(jù)此完成分簇，構(gòu)建多個(gè)簇指紋庫(kù)；在線階段，目標(biāo)節(jié)點(diǎn)獲取RSS 信號(hào)，根據(jù)信號(hào)的覆蓋向量完成簇匹配，確定相應(yīng)的簇指紋庫(kù)；利用LASSO 算法，用簇指紋庫(kù)擬合在線RSS 信號(hào)，確定回歸系數(shù)，并以此回歸系數(shù)作為權(quán)值確定目標(biāo)位置。

圖1 室內(nèi)定位算法HC-LASSO 的框架Fig.1 Block diagram of the proposed indoor positioning system HC-LASSO

1.1 離線階段分簇

室內(nèi)復(fù)雜空間環(huán)境內(nèi)有墻壁、電梯井等會(huì)嚴(yán)重堵塞信號(hào)，使某個(gè)區(qū)域只能接收到部分錨節(jié)點(diǎn)的信號(hào)。同時(shí)，錨節(jié)點(diǎn)也可能存在掉電、故障等原因，這樣離線與在線階段接收的RSS 信號(hào)可能并不是來(lái)自同一批錨節(jié)點(diǎn)，而無(wú)法實(shí)現(xiàn)指紋匹配。通常對(duì)未接收到的錨節(jié)點(diǎn)信號(hào)統(tǒng)一填充某個(gè)信號(hào)接收閾值，如-100 dBm 來(lái)解決這一問(wèn)題。這種方法對(duì)于離線與在線階段都適用，簡(jiǎn)單有效。為充分利用RSS 信號(hào)分布提供的位置信息，引入了指紋定位中重要的分簇概念。分簇可實(shí)現(xiàn)粗定位，避免在整個(gè)監(jiān)測(cè)范圍搜索目標(biāo)節(jié)點(diǎn)位置而引入大計(jì)算量和大能耗，并且使最大定位誤差限制在簇內(nèi)。但是如果簇選擇錯(cuò)誤，則引入的定位誤差將不可預(yù)測(cè)。另外基于RSS 信號(hào)特征的分簇，同一簇內(nèi)的成員即參考位置點(diǎn)常有較分散的物理位置。這就使即使在RSS 信號(hào)匹配度高的情況下，物理位置仍可能存在大偏差。因此本文采用基于RSSI 信號(hào)特征的分簇與物理區(qū)域劃分相結(jié)合的方式進(jìn)行混合分簇。

圖2 給出了本文實(shí)驗(yàn)中某個(gè)位置錨節(jié)點(diǎn)在定位區(qū)域的RSS信號(hào)分布。

圖2 中灰色圓點(diǎn)是錨節(jié)點(diǎn)所在位置，未布置參考位置點(diǎn)的區(qū)域是電梯和樓梯間，也即錨節(jié)點(diǎn)在電梯間的墻后?？梢园l(fā)現(xiàn)由于墻壁阻擋，很多參考位置點(diǎn)無(wú)法接收到該錨節(jié)點(diǎn)信號(hào)，RSS信號(hào)分布具有較明顯的區(qū)域性，而這一塊區(qū)域有較相近的覆蓋向量。因此可利用RSS 信號(hào)的覆蓋向量作為特征進(jìn)行分簇來(lái)盡可能降低粗定位誤差。分簇具體過(guò)程如下。

離線采集RSS 信號(hào)構(gòu)建原始指紋庫(kù)Ψ，根據(jù)參考位置點(diǎn)能否接收到錨節(jié)點(diǎn)的信號(hào)，確定相應(yīng)的覆蓋向量Η。分別表示為

圖2 某一錨節(jié)點(diǎn)在各參考位置點(diǎn)的RSS 信號(hào)強(qiáng)度分布Fig.2 RSS distribution in reference points from an anchor

式中：φi為第i個(gè)參考位置點(diǎn)Si的指紋，共N個(gè)參考位置點(diǎn)；φi，j為在第i個(gè)參考位置點(diǎn)接收到的來(lái)自第j個(gè)錨節(jié)點(diǎn)的RSS 信號(hào)，共M個(gè)錨節(jié)點(diǎn)，實(shí)際應(yīng)用中，該值一般為一段時(shí)間內(nèi)接收到RSS 信號(hào)的時(shí)間均值；γi為參考位置點(diǎn)Si的覆蓋向量，一般形式為

式中j位置的向量元素1 表示在指紋采集時(shí)間內(nèi)能接收到第j個(gè)錨節(jié)點(diǎn)的信號(hào)。反之，則表示無(wú)法接收。

分簇首先采用K中心點(diǎn)算法。相較于K均值算法，前者對(duì)噪聲和異常點(diǎn)數(shù)據(jù)不敏感，雖然時(shí)間復(fù)雜度稍大，不過(guò)此分簇過(guò)程是在離線階段，不影響在線階段的定位實(shí)時(shí)性。按照算法，以覆蓋向量為特征，計(jì)算每個(gè)參考位置點(diǎn)與聚類中心參考位置的漢明距離，把N個(gè)參考位置點(diǎn)分成K個(gè)聚類。算法過(guò)程如下：

（1）從N個(gè)參考位置中，隨機(jī)選取K個(gè)，作為初始中心點(diǎn)；

（2）計(jì)算其余（N-K）個(gè)參考位置與K個(gè)中心點(diǎn)的覆蓋向量的漢明距離，選取距離最小的為所屬簇；

（3）任選一個(gè)參考位置R，確定其所屬的簇；

（4）在該簇內(nèi)，以此參考位置R為簇中心點(diǎn)，計(jì)算簇內(nèi)所有成員與R的覆蓋向量漢明距離之和作為新的距離代價(jià)函數(shù)；

（5）與原代價(jià)函數(shù)比較，若新的距離代價(jià)函數(shù)較小，則參考位置R作為該簇新的簇中心點(diǎn)；重復(fù)步驟（2）—（5）；

（6）若新的距離代價(jià)函數(shù)較大，則分簇完成；

（7）簇內(nèi)各成員相應(yīng)的指紋構(gòu)成簇指紋庫(kù)。

相應(yīng)的原始指紋庫(kù)Ψ也分為K個(gè)簇指紋庫(kù)，第i個(gè)簇指紋庫(kù)包含n個(gè)參考位置點(diǎn)，由屬于該簇的位置參考點(diǎn)指紋構(gòu)成，表示為

本文以聚類中心對(duì)應(yīng)的參考位置點(diǎn)作為簇頭，用于在線階段的簇匹配。

基于物理位置的分簇則相對(duì)簡(jiǎn)單，按照參考位置點(diǎn)的物理地址，結(jié)合具體定位區(qū)域的空間布局特點(diǎn)，把指紋庫(kù)相應(yīng)分為L(zhǎng)個(gè)區(qū)域指紋庫(kù)，分別用表示。在線階段的簇匹配，采用與簇內(nèi)所有成員計(jì)算覆蓋向量的漢明距離來(lái)完成。

1.2 在線定位

在線定位涉及2 個(gè)步驟。首先根據(jù)采集到的RSS 信號(hào)確定目標(biāo)節(jié)點(diǎn)所屬的簇，也即粗定位；其次利用定位算法完成位置估算，也稱二次精確定位。

1.2.1 簇匹配

粗定位方法與分簇方法密切相關(guān)。比如離線階段利用RSS 信號(hào)相似度進(jìn)行分簇，那么粗定位時(shí)，在線RSS 信號(hào)需要與每個(gè)簇進(jìn)行相似度比較。這個(gè)相似度比較可以與表征簇特征的簇頭比較，也可以與簇內(nèi)的每個(gè)成員比較。對(duì)于前者，簇頭的選擇會(huì)極大影響粗定位；對(duì)于后者則會(huì)引入相對(duì)大的計(jì)算量。本文采用覆蓋向量進(jìn)行分簇，簇匹配也是利用覆蓋向量的相似度來(lái)完成。

在線階段接收的RSS 信號(hào)φr表示為

相應(yīng)的覆蓋向量表示為γr。對(duì)于聚類產(chǎn)生的K個(gè)簇，采用式（5）計(jì)算在線RSS 測(cè)量值φr與第j個(gè)簇頭的相似度

式中γHDj為第j個(gè)簇頭的覆蓋向量。選擇距離最小的簇頭對(duì)應(yīng)的簇作為匹配簇，其指紋記為ΨCP。

對(duì)于物理分簇產(chǎn)生的L個(gè)簇，采用下式計(jì)算測(cè)量值φr與第l個(gè)簇的相似度

式中γZj為屬于簇l的第j個(gè)參考位置點(diǎn)的覆蓋向量，|ClZ|為第l個(gè)簇內(nèi)的成員數(shù)量。同樣選擇距離最小的簇作為匹配簇，記為ΨZP。最終在線RSS 測(cè)量值所對(duì)應(yīng)的匹配簇指紋為

式中簇內(nèi)的參考位置點(diǎn)表示為集合ΔP。

1.2.2 簇內(nèi)定位

考慮到某一時(shí)刻目標(biāo)節(jié)點(diǎn)只能在某一確定物理空間位置，該位置可能在幾個(gè)參考位置點(diǎn)的附近或者也可能正巧在某一參考位置點(diǎn)上。從信號(hào)分布的角度，可認(rèn)為目標(biāo)點(diǎn)的RSS 信號(hào)可由所選簇內(nèi)若干參考位置點(diǎn)的RSS 信號(hào)表示。滿足

式中y為在線測(cè)得的目標(biāo)位置RSS 信號(hào)，ΨP為所匹配簇的指紋，ε為未知的測(cè)量誤差，而θ為待定的回歸系數(shù)矩陣。

定位問(wèn)題就轉(zhuǎn)化為θ的求解。壓縮感知（Compressive sensing，CS）算法［13］把θ作為一個(gè)稀疏矩陣進(jìn)行求解，即大部分元素為0。在足夠稀疏的情況下式（8）的求解可轉(zhuǎn)化為求解

CS 算法要求ΨP指紋中各樣本也即參考位置點(diǎn)的RSS 信號(hào)是非相關(guān)測(cè)量，否則需進(jìn)行正交變換［13］，而實(shí)際應(yīng)用中通常不滿足這點(diǎn)，使CS 算法的復(fù)雜度增加。如前所述，樣本之間存在相關(guān)性，使普通最小二乘法不適用回歸系數(shù)θ的求解。從而引入懲罰方法來(lái)同時(shí)實(shí)現(xiàn)樣本選擇和參數(shù)估計(jì)。當(dāng)懲罰函數(shù)為L(zhǎng)1范數(shù)時(shí)，則稱為L(zhǎng)ASSO，其模型為

式中t為調(diào)節(jié)系數(shù)。也即LASSO 算法在使回歸系數(shù)的絕對(duì)值之和小于某個(gè)常數(shù)的條件下，使殘差平方和最小。這一表達(dá)式也等價(jià)于

式中：λ為正則項(xiàng)系數(shù)，與t一一對(duì)應(yīng)，用于平衡算法復(fù)雜度和擬合精度，λ越大，則懲罰程度加大，更多的系數(shù)壓縮為0，從而達(dá)到特征選擇或稀疏的效果。總體而言回歸系數(shù)θ盡可能小，防止過(guò)擬合。

若匹配簇ΨP的指紋集合ΔP有N p個(gè)元素，此時(shí)θ是N p×1 的向量，其中有n個(gè)元素不為0，則目標(biāo)位置表示為

式中Si是匹配簇內(nèi)的第i個(gè)參考位置點(diǎn)，（xi，yi）是其相應(yīng)的坐標(biāo)。

從某種角度來(lái)說(shuō)，目標(biāo)的估計(jì)位置是不為0 的元素所對(duì)應(yīng)的參考位置點(diǎn)坐標(biāo)的加權(quán)平均。值得一提的是，線性回歸模型的模型復(fù)雜度與特征維數(shù)有關(guān)。簇匹配和簇內(nèi)LASSO 算法二次定位的方式，使LASSO 算法的復(fù)雜度由未分簇前原始指紋庫(kù)Ψ對(duì)應(yīng)的N維降低到匹配簇指紋ΨP對(duì)應(yīng)的N p維，這在大監(jiān)控環(huán)境下參考點(diǎn)分布數(shù)量較大時(shí)有利于降低算法的復(fù)雜度。

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

2.1 算法的定位精度

實(shí)驗(yàn)在上海理工大學(xué)光電學(xué)院9 樓辦公層的大廳和走廊進(jìn)行。整個(gè)無(wú)線傳感器網(wǎng)絡(luò)定位系統(tǒng)由錨節(jié)點(diǎn)、網(wǎng)關(guān)節(jié)點(diǎn)和移動(dòng)節(jié)點(diǎn)組成，節(jié)點(diǎn)采用CC2430 作為主控芯片，搭載TinyOS 操作系統(tǒng)進(jìn)行RSS 信號(hào)的采集。在兩側(cè)走廊距離地面約2.2 m 的位置共布置了18 個(gè)錨節(jié)點(diǎn)。在面積約為40 m×15 m 的監(jiān)測(cè)區(qū)域以1.8 m 為間隔共設(shè)置90 個(gè)參考位置點(diǎn)。每個(gè)參考位置點(diǎn)采集的錨節(jié)點(diǎn)RSS 信號(hào)，均值化處理后構(gòu)成原始位置指紋庫(kù)Ψ。按照本文所提的分簇方法，圖3 給出了參考位置點(diǎn)各自的所屬簇。其中K中心點(diǎn)分簇法把參考位置點(diǎn)分為3 簇，用不同的標(biāo)記表示了相應(yīng)的簇；3 個(gè)虛線框分別表示了物理分簇后各參考位置點(diǎn)所屬的簇。

在上述定位區(qū)域隨機(jī)選取了21 個(gè)目標(biāo)位置點(diǎn)，采集的RSS 信號(hào)均值化后作為在線階段的φr，用本文所提的HC?LASSO 定位算法對(duì)目標(biāo)進(jìn)行了位置估計(jì)，并與其他幾種算法進(jìn)行了比較。圖4 給出了各算法的誤差累計(jì)分布函數(shù)。

圖3 生成的簇分布Fig.3 Example of the clustering result

圖4 HC-LASSO 算法與其他算法的定位精度比較Fig.4 CDF for HC-LASSO and other positioning methods

圖4 中 HC?LASSO 是本文所提的聯(lián)合分簇結(jié)合簇內(nèi) LASSO 定位算法，KC?LASSO 表示K中心分簇結(jié)合簇內(nèi) LASSO 定位算法；LASSO 表示全局采用 LASSO 算法定位［15］，WKNN 算法中K取 4，采用在線與離線RSS 信號(hào)歐氏距離的倒數(shù)作為權(quán)值。比較過(guò)程中，其他未提及的參數(shù)均保持一致。4 種算法的平均定位誤差分別是：1.74，1.90，1.83 和2.58 m。而從圖4 的累計(jì)誤差分布圖也可以看出，HC?LASSO 算法與KC?LASSO 和LASSO 比較，相對(duì)定位誤差最小，說(shuō)明混合分簇法能避免粗定位階段的簇匹配錯(cuò)誤；而LASSO 定位算法總體精度均高于WKNN 算法，說(shuō)明二次精確定位階段的LASSO 算法也具有較好的定位精度。

2.2 粗定位階段分簇和錨節(jié)點(diǎn)對(duì)定位的影響

避免粗定位階段粗大誤差的關(guān)鍵是避免簇匹配錯(cuò)誤，這要求離線階段對(duì)參考位置點(diǎn)要有合理的分簇且在線階段簇匹配要精確。本文研究了不同的分簇方法對(duì)定位精度的影響，結(jié)果如圖5 所示。

圖5 中 Kmedoids?LASSO、PC?LASSO 和K?means?LASSO 表示二次精確定位階段均采用 LASSO算法，但離線階段分別采用K中心點(diǎn)算法、物理位置和K均值算法對(duì)參考位置點(diǎn)進(jìn)行分簇。圖5 中LASSO 則表示無(wú)粗定位，直接利用LASSO 算計(jì)進(jìn)行全局匹配定位。4 種算法的平均誤差分別是：1.90，2.34，2.21 和1.83 m。從圖中看出有幾個(gè)位置點(diǎn)誤差很大，其中第6 個(gè)位置點(diǎn)PC?LASSO 方法定位誤差達(dá)到 6.87 m，而K?means?LASSO 算法有 3 個(gè)位置點(diǎn)誤差在 4.5 m 左右，Kmedoids 有 2 個(gè)位置定位誤差在4 m 左右。經(jīng)分析是由于粗定位階段簇匹配錯(cuò)誤導(dǎo)致，因此本文選擇了K中心點(diǎn)分簇和物理區(qū)域分簇結(jié)合的方式來(lái)盡可能避免粗大誤差。

除了不同分簇方法會(huì)影響目標(biāo)位置的粗定位，實(shí)驗(yàn)也對(duì)錨節(jié)點(diǎn)數(shù)量和分簇?cái)?shù)量對(duì)定位精度的影響進(jìn)行了分析。表1 中二次定位階段均采用LASSO 算法，且參數(shù)保持不變。

圖5 不同分簇下目標(biāo)位置點(diǎn)的定位誤差比較Fig.5 Comparison of positioning errors under differ?ent clustering methods

表1 不同錨節(jié)點(diǎn)數(shù)量和分簇?cái)?shù)量的定位精度統(tǒng)計(jì)Table 1 Statistics of positioning accuracy under dif?ferent numbers of anchors and clusters

表1 中，K 表示采用K中心點(diǎn)算法，P 表示物理分簇，其后的數(shù)字表示分簇的數(shù)量，如K3?P3 表示采用K中心點(diǎn)算法把參考位置點(diǎn)分成3 個(gè)簇，物理分簇也是3 個(gè)簇。分析表中數(shù)據(jù)可知，當(dāng)前的監(jiān)測(cè)區(qū)域內(nèi)，K3?P3 對(duì)應(yīng)的定位算法精度最高。說(shuō)明過(guò)多追求分簇的數(shù)量容易發(fā)生簇匹配錯(cuò)誤，從而產(chǎn)生粗大定位誤差。實(shí)驗(yàn)也研究了錨節(jié)點(diǎn)數(shù)量在18，12 和9 變化時(shí)定位精度的統(tǒng)計(jì)特性，其對(duì)WKNN 算法的影響，也具有類似的相關(guān)性。說(shuō)明在分簇情況下，較多的錨節(jié)點(diǎn)數(shù)量更有利于準(zhǔn)確的簇匹配。

2.3 在線階段二次精確定位算法的選擇

對(duì)于二次精確定位階段的算法，本文對(duì)所提的LASSO 算法與 KR 算法［8］、WKNN 算法、CS 算法［13］和嶺回歸算法［15］進(jìn)行了定位精度比較。

圖6 給出了5 種定位算法的累積誤差分布，同時(shí)也獲得平均定位誤差分別是：1.83，1.58，2.58，2.71 和 3.18 m。從圖6 中也可看出核嶺回歸算法定位精度略高于LASSO 算法。但是考慮到核嶺回歸算法是訓(xùn)練模型來(lái)描述參考點(diǎn)的RSS和物理位置之間的關(guān)系，需要利用核函數(shù)來(lái)完成線性到非線性關(guān)系的轉(zhuǎn)換，計(jì)算量較大，同時(shí)為獲得最理想模型需要涉及正則化參數(shù)和核函數(shù)的帶寬2 個(gè)參數(shù)的搜索，在分簇情況下，意味著對(duì)每個(gè)簇要分別進(jìn)行參數(shù)選擇。因此本文采用了計(jì)算量相對(duì)小，定位精度也較高的LASSO 算法作為二次精確定位算法。

圖6 不同定位算法的誤差累計(jì)分布函數(shù)Fig.6 Cumulative error distribution for dif?ferent positioning methods

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

基于RSS 指紋定位算法，在提高定位精度的前提下為減小在線階段的指紋匹配量，提出一種聯(lián)合分簇方法，該方法基于RSS 信號(hào)的覆蓋向量采用K中心點(diǎn)算法對(duì)參考位置點(diǎn)進(jìn)行分簇，同時(shí)利用物理位置對(duì)參考位置點(diǎn)進(jìn)行劃分，構(gòu)建簇指紋庫(kù)，融合了RSS 信號(hào)的空間分布和實(shí)際物理空間的分布特點(diǎn)。定位階段利用簇匹配完成目標(biāo)的粗定位，在小樣本的前提下，采用LASSO 算法完成目標(biāo)位置的二次精確估計(jì)。本文從不同分簇方法、分簇?cái)?shù)量、錨節(jié)點(diǎn)數(shù)量等方面對(duì)算法進(jìn)行了分析，并與其他室內(nèi)定位算法進(jìn)行了對(duì)比。實(shí)驗(yàn)結(jié)果表明，本文所提的定位算法通過(guò)合理的分簇，在降低在線匹配計(jì)算量的同時(shí)能保持良好的定位效果。更大規(guī)模區(qū)域的算法應(yīng)用及實(shí)時(shí)在線定位系統(tǒng)的實(shí)現(xiàn)是下一步的研究目標(biāo)。