樂燕芬，金施嘉珞，朱一鳴，施偉斌

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

引 言

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

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

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

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

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

定位算法分離線和在線2 個階段。離線階段通過采集的各參考位置點的RSS 信號確定覆蓋向量，并據(jù)此完成分簇，構(gòu)建多個簇指紋庫；在線階段，目標(biāo)節(jié)點獲取RSS 信號，根據(jù)信號的覆蓋向量完成簇匹配，確定相應(yīng)的簇指紋庫；利用LASSO 算法，用簇指紋庫擬合在線RSS 信號，確定回歸系數(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)有墻壁、電梯井等會嚴(yán)重堵塞信號，使某個區(qū)域只能接收到部分錨節(jié)點的信號。同時，錨節(jié)點也可能存在掉電、故障等原因，這樣離線與在線階段接收的RSS 信號可能并不是來自同一批錨節(jié)點，而無法實現(xiàn)指紋匹配。通常對未接收到的錨節(jié)點信號統(tǒng)一填充某個信號接收閾值，如-100 dBm 來解決這一問題。這種方法對于離線與在線階段都適用，簡單有效。為充分利用RSS 信號分布提供的位置信息，引入了指紋定位中重要的分簇概念。分簇可實現(xiàn)粗定位，避免在整個監(jiān)測范圍搜索目標(biāo)節(jié)點位置而引入大計算量和大能耗，并且使最大定位誤差限制在簇內(nèi)。但是如果簇選擇錯誤，則引入的定位誤差將不可預(yù)測。另外基于RSS 信號特征的分簇，同一簇內(nèi)的成員即參考位置點常有較分散的物理位置。這就使即使在RSS 信號匹配度高的情況下，物理位置仍可能存在大偏差。因此本文采用基于RSSI 信號特征的分簇與物理區(qū)域劃分相結(jié)合的方式進(jìn)行混合分簇。

圖2 給出了本文實驗中某個位置錨節(jié)點在定位區(qū)域的RSS信號分布。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1.2 在線定位

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

1.2.1 簇匹配

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

在線階段接收的RSS 信號φr表示為

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

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

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

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

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

1.2.2 簇內(nèi)定位

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

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

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

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

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

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

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

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

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

2 實驗結(jié)果及分析

2.1 算法的定位精度

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

在上述定位區(qū)域隨機(jī)選取了21 個目標(biāo)位置點，采集的RSS 信號均值化后作為在線階段的φr，用本文所提的HC?LASSO 定位算法對目標(biāo)進(jìn)行了位置估計，并與其他幾種算法進(jìn)行了比較。圖4 給出了各算法的誤差累計分布函數(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 信號歐氏距離的倒數(shù)作為權(quán)值。比較過程中，其他未提及的參數(shù)均保持一致。4 種算法的平均定位誤差分別是：1.74，1.90，1.83 和2.58 m。而從圖4 的累計誤差分布圖也可以看出，HC?LASSO 算法與KC?LASSO 和LASSO 比較，相對定位誤差最小，說明混合分簇法能避免粗定位階段的簇匹配錯誤；而LASSO 定位算法總體精度均高于WKNN 算法，說明二次精確定位階段的LASSO 算法也具有較好的定位精度。

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

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

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

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

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

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

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

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

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

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

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

3 結(jié)束語

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