基于空間劃分的K-means 聚類室內(nèi)定位垂直精度優(yōu)化方法

李 冰，楊珊珊，劉春剛，趙 華，王 翔

（1.河北師范大學(xué) 中燃工學(xué)院，石家莊 050024；2.河北省信息融合與智能控制重點(diǎn)實(shí)驗(yàn)室，石家莊 050024）

隨著物聯(lián)網(wǎng)的快速發(fā)展，高精度室內(nèi)定位技術(shù)的需求愈發(fā)強(qiáng)烈，目前室內(nèi)定位技術(shù)有很多，其中超寬帶（Ultra-Wideband,UWB）定位技術(shù)憑借功耗低、穿透能力強(qiáng)、時(shí)間分辨率高、定位精度高[1]等優(yōu)點(diǎn)，逐漸成為室內(nèi)定位技術(shù)研究的熱點(diǎn)。

UWB 室內(nèi)定位技術(shù)在水平方向上已經(jīng)獲得很高的定位精度。Poulose 等人[2]提出了一種長(zhǎng)短期記憶網(wǎng)絡(luò)（Long Short Term Memory,LSTM）預(yù)測(cè)標(biāo)簽位置的方法，將測(cè)距值作為L(zhǎng)STM 模型輸入，輸出為標(biāo)簽位置預(yù)測(cè)值，實(shí)現(xiàn)了水平方向0.07 m 的定位精度。Fu等人[3]提出了一種自適應(yīng)無(wú)跡卡爾曼濾波（Unscented Kalman Filter,UKF）高精度室內(nèi)定位方法，通過(guò)構(gòu)造狀態(tài)補(bǔ)償函數(shù)，結(jié)合UKF 算法，能夠?qū)Χㄎ粎^(qū)域中的標(biāo)簽任何位置執(zhí)行自適應(yīng)實(shí)時(shí)補(bǔ)償，水平方向定位精度小于0.07 m。Guo 等人[4]設(shè)計(jì)了模擬退火和聚類融合的室內(nèi)定位優(yōu)化算法，該算法利用模擬退火算法的良好局部搜索能力來(lái)優(yōu)化聚類效果，快速確定采樣數(shù)據(jù)的最佳結(jié)果，以實(shí)現(xiàn)準(zhǔn)確定位，水平方向定位誤差小于0.1 m。由此可見(jiàn)，水平方向定位精度可以通過(guò)機(jī)器學(xué)習(xí)方法、濾波算法或智能優(yōu)化算法得到顯著提高。然而，以上方法只提高了水平方向精度，對(duì)垂直方向的定位精度沒(méi)有改善。

三維室內(nèi)定位中，垂直方向的精度受到錨節(jié)點(diǎn)的幾何精度因子[5]（Geometric Dilution of Precision,GDOP）的影響。由于水平方向錨節(jié)點(diǎn)布設(shè)空間更為寬廣，因此水平精度因子（Horizontal Dilution of Precision,HDOP）更小。相比之下，垂直方向的錨節(jié)點(diǎn)布設(shè)范圍較窄，導(dǎo)致垂直精度因子（Vertical Dilution of Precision,VDOP）更大，使得定位方程組出現(xiàn)病態(tài)情況，從而導(dǎo)致垂直方向誤差較大。Li 等人[6]針對(duì)傳統(tǒng)最小二乘法在垂直方向定位中存在不穩(wěn)定性的問(wèn)題，提出魯棒脊估計(jì)方法，解決了到達(dá)時(shí)間差（Time Difference of Arrival,TDOA）定位算法的發(fā)散問(wèn)題。復(fù)雜環(huán)境中，垂直方向定位精度小于1.85 m，但是該方法未分析導(dǎo)致方程病態(tài)的原因，容易出現(xiàn)解算錯(cuò)誤的情況。徐曉蘇等人[7]提出二次解析的室內(nèi)定位垂直方向精度優(yōu)化方法，通過(guò)第一次解析得到標(biāo)簽水平方向坐標(biāo)，然后通過(guò)二次解析過(guò)程中的Tikhonov 正則化方法修正垂直方向上的偏差。該方法垂直方向定位精度小于0.35 m，但計(jì)算復(fù)雜，而且如果一次解析出的水平方向誤差過(guò)大，也會(huì)對(duì)二次解析的垂直方向定位精度造成影響。Yang 等人[8]針對(duì)垂直方向定位誤差比水平方向定位誤差大的問(wèn)題，采用改進(jìn)粒子群優(yōu)化算法確定卡爾曼濾波的最佳參數(shù)，優(yōu)化前置校正點(diǎn)位置，可以實(shí)現(xiàn)0.25 m 的垂直方向定位精度，但該方法需要先驗(yàn)信息，不能直接使用于未知區(qū)域或?qū)崟r(shí)定位場(chǎng)景。所以在受限的環(huán)境下，垂直方向定位精度還有待進(jìn)一步提高。

針對(duì)上述問(wèn)題，本文提出基于空間劃分的K-means 聚類（Space Grid Division K-means,SGDK）室內(nèi)定位垂直精度優(yōu)化方法。首先，采集錨節(jié)點(diǎn)到標(biāo)簽的TDOA 數(shù)據(jù)，利用拉依達(dá)準(zhǔn)則進(jìn)行異常值篩選，通過(guò)Chan 算法解算標(biāo)簽的估計(jì)位置，得到原始標(biāo)簽數(shù)據(jù)集。然后，采用網(wǎng)格聚類方法將原始標(biāo)簽數(shù)據(jù)集劃分成空間網(wǎng)格單元，根據(jù)設(shè)定的距離閾值合并近鄰空間網(wǎng)格單元，通過(guò)密度原則和K-means++聚類中心選取方法，選取密度大且距離遠(yuǎn)的候選空間網(wǎng)格單元，從中確定初始聚類中心。接下來(lái)，使用K-means 聚類算法將原始標(biāo)簽數(shù)據(jù)集劃分為k個(gè)子區(qū)域，并確定子區(qū)域可信度高的參考位置。最后，計(jì)算參考位置與中心位置離散程度，根據(jù)離散程度對(duì)參考位置賦予權(quán)重因子。對(duì)可能有偏差的參考位置賦予較小的權(quán)重，對(duì)接近中心位置賦予較大權(quán)重，加權(quán)質(zhì)心定位算法確定標(biāo)簽最優(yōu)位置。

1 定位方法

1.1 TDOA 定位原理

TDOA 定位算法[9]通過(guò)測(cè)量待測(cè)標(biāo)簽與錨節(jié)點(diǎn)間距離差來(lái)實(shí)現(xiàn)標(biāo)簽位置的解算，其幾何原理是基于雙曲線或雙曲面相交解析定位，原理如圖1 所示。

圖1 TDOA 定位原理圖Fig.1 TDOA positioning schematic diagram

圖1 中，主錨節(jié)點(diǎn)為BS1，從錨節(jié)點(diǎn)為BS2、BS3、BS4。以BS1 為基準(zhǔn)建立三條雙曲線，交點(diǎn)為待測(cè)標(biāo)簽 MS的位置，其中錨節(jié)點(diǎn)坐標(biāo)為(x?,y?,z?)，?=1～4；MS 坐標(biāo)為(x,y,z)。由上述分析可得：

其中，R1為主錨節(jié)點(diǎn)到MS 的距離；R?為從錨節(jié)點(diǎn)到MS 的距離；R?,1為MS 到從錨節(jié)點(diǎn)和主錨節(jié)點(diǎn)間的距離差；τ?,1為MS 發(fā)送信號(hào)到達(dá)從錨節(jié)點(diǎn)和主錨節(jié)點(diǎn)的時(shí)間差；c為信號(hào)傳播速度。

1.2 Chan 算法

Chan 算法是一種基于TDOA 算法的定位方法，通過(guò)求解非線性雙曲線方程組來(lái)確定標(biāo)簽位置，并采用多次加權(quán)最小二乘（Weighted Least Square,WLS）對(duì)定位誤差進(jìn)行修正。當(dāng)測(cè)距誤差符合高斯分布時(shí)，該算法能夠?qū)崿F(xiàn)較高的定位精度。然而，復(fù)雜室內(nèi)環(huán)境中，非視距誤差（Non-line-of-sight,NLOS）的存在將影響到測(cè)距誤差的分布特性，使其不服從高斯分布[10]，所以Chan 算法的定位精度還有待提高。

假設(shè)在三維實(shí)驗(yàn)環(huán)境中存在N個(gè)錨節(jié)點(diǎn)，位置為(xi,yi,zi)，i=1,2…N。標(biāo)簽位置為(x,y,z)，標(biāo)簽與錨節(jié)點(diǎn)之間的距離為Ri，有：

聯(lián)立式(3)(4)可得：

整理式(5)可得：

由于觀測(cè)噪聲的存在，導(dǎo)致h≠Gza，誤差向量表示為：

假設(shè)za中各個(gè)元素相互獨(dú)立，對(duì)式(8)進(jìn)行WLS得到標(biāo)簽的第一次估計(jì)位置：

za中的元素可以表示為：

實(shí)際上za中各個(gè)元素并不相互獨(dú)立，為了得到更加精確的標(biāo)簽位置，需要對(duì)上述結(jié)果進(jìn)一步優(yōu)化，建立第二次估計(jì)的線性方程：

對(duì)式(11)進(jìn)行WLS 得到標(biāo)簽的第二次估計(jì)位置：

最終得到標(biāo)簽位置為：

2 基于SGDK 聚類的垂直精度優(yōu)化方法

K-means 聚類算法[11]是一種無(wú)監(jiān)督聚類算法，通過(guò)計(jì)算樣本點(diǎn)與簇中心的距離，將相似度高的樣本劃分為同一個(gè)簇。處理較大數(shù)據(jù)時(shí)間復(fù)雜度低、效率高，但隨機(jī)初始聚類中心沒(méi)有考慮數(shù)據(jù)分布情況，容易達(dá)到局部最優(yōu)值，影響聚類效果。故本文對(duì)K-means 聚類算法初始聚類中心的選取進(jìn)行改進(jìn)，在網(wǎng)格聚類與K-means 聚類方法基礎(chǔ)上，提出SGDK 聚類的室內(nèi)定位方法。將定位問(wèn)題轉(zhuǎn)化為三維樣本聚類問(wèn)題，用于提升室內(nèi)定位垂直方向定位精度?？傮w算法流程如圖2 所示。

圖2 算法流程圖Fig.2 Flowchart of the algorithm

2.1 數(shù)據(jù)預(yù)處理與標(biāo)簽位置估計(jì)

對(duì)標(biāo)簽進(jìn)行多次重復(fù)實(shí)驗(yàn)，采集300 組TDOA 數(shù)據(jù)。受室內(nèi)環(huán)境因素影響，其中包含了一些異常數(shù)據(jù)。為了便于后續(xù)的定位分析，采用拉依達(dá)準(zhǔn)則（3σ準(zhǔn)則）來(lái)判斷和篩選異常值[12]。

3σ準(zhǔn)則：以給定的置信概率99.73%為標(biāo)準(zhǔn)，若數(shù)據(jù)的偏差超過(guò)3 倍標(biāo)準(zhǔn)偏差，就會(huì)被當(dāng)作粗大誤差，含有此誤差的數(shù)據(jù)稱為異常值，需要從數(shù)據(jù)集中剔除。計(jì)算公式為：

剔除TDOA 異常值后，通過(guò)Chan 算法求解出標(biāo)簽估計(jì)位置，得到原始標(biāo)簽數(shù)據(jù)集，記為dataα(α=1,2 …300)。在UWB 室內(nèi)定位錨節(jié)點(diǎn)布設(shè)時(shí)，對(duì)水平方向的限制比較小，可以布置在比較合理的范圍，而對(duì)垂直方向的限制比較大，導(dǎo)致標(biāo)簽估計(jì)位置在垂直方向波動(dòng)范圍比水平方向更大，如圖3 所示。為了進(jìn)一步提高垂直方向定位精度，需要對(duì)標(biāo)簽估計(jì)位置進(jìn)行處理，采用聚類算法的目的就是對(duì)標(biāo)簽數(shù)據(jù)集分層劃分，從中確定標(biāo)簽的最優(yōu)位置。

圖3 估計(jì)位置分布情況Fig.3 Estimated location distribution

2.2 SGDK 聚類算法

在傳統(tǒng)K-means 聚類算法中，隨機(jī)初始聚類中心導(dǎo)致每次聚類結(jié)果不同，嚴(yán)重影響標(biāo)簽數(shù)據(jù)集聚類的準(zhǔn)確性，使得標(biāo)簽最終定位精度也受到影響。因此本文提出SGDK 聚類算法，通過(guò)網(wǎng)格聚類方法對(duì)原始標(biāo)簽數(shù)據(jù)集進(jìn)行空間網(wǎng)格劃分，并結(jié)合密度原則和K-means++聚類中心選取方法，從中確定初始聚類中心。

2.2.1 數(shù)據(jù)空間網(wǎng)格劃分

SGDK 聚類算法通過(guò)網(wǎng)格聚類方法，進(jìn)行數(shù)據(jù)集空間網(wǎng)格劃分，將原始標(biāo)簽數(shù)據(jù)集中的樣本點(diǎn)映射到各空間網(wǎng)格單元中。但是如果空間網(wǎng)格劃分過(guò)于細(xì)化，不僅會(huì)導(dǎo)致計(jì)算效率降低，甚至還會(huì)出現(xiàn)某些網(wǎng)格中的樣本點(diǎn)數(shù)量過(guò)少的情況。因此，本文結(jié)合原始標(biāo)簽數(shù)據(jù)集分布特點(diǎn)，通過(guò)確定聚類個(gè)數(shù)k值來(lái)劃分原始標(biāo)簽數(shù)據(jù)集。

定義 1原始標(biāo)簽數(shù)據(jù)集空間為L(zhǎng)×W×H，空間網(wǎng)格單元記為Si,j,r，標(biāo)簽估計(jì)位置分布在每一空間網(wǎng)格單元內(nèi)。

定義 2網(wǎng)格邊長(zhǎng)

設(shè)原始標(biāo)簽數(shù)據(jù)集dataα三個(gè)維度范圍為[xmin,xmax]、[ymin,ymax]、[zmin,zmax]。將數(shù)據(jù)集按各維度劃分k3個(gè)均等不相交網(wǎng)格。數(shù)據(jù)空間為：

其中，ε為足夠小的閾值。

定義 3標(biāo)簽估計(jì)位置與空間網(wǎng)格單元存在如式(19)所示的關(guān)系：

定義 4網(wǎng)格密度

空間網(wǎng)格劃分后，網(wǎng)格單元樣本點(diǎn)個(gè)數(shù)記為網(wǎng)格密度ρg(g=1,2…k3)。

定義 5近鄰網(wǎng)格

存在公共邊的空間網(wǎng)格單元，記為近鄰空間網(wǎng)格單元。

定義 6網(wǎng)格質(zhì)心

若落入網(wǎng)格m個(gè)樣本點(diǎn)，網(wǎng)格質(zhì)心為網(wǎng)格單元中所有樣本點(diǎn)的均值，記為ηg。

其中，Cie為網(wǎng)格單元中第i個(gè)樣本點(diǎn)。

2.2.2 K-means 初始聚類中心的確定

數(shù)據(jù)空間網(wǎng)格劃分后，需要在空間網(wǎng)格單元中選取候選初始聚類中心網(wǎng)格，從中確定初始聚類中心。然而，在候選初始聚類中心網(wǎng)格集中，同一簇可能存在多個(gè)候選網(wǎng)格。為了避免初始聚類中心出現(xiàn)在同一簇中，本文根據(jù)文獻(xiàn)[13]的網(wǎng)格距離設(shè)置方法，設(shè)定距離閾值ω。如果任意近鄰空間網(wǎng)格質(zhì)心之間的距離小于ω，則合并兩個(gè)空間網(wǎng)格單元。

密度原則：各空間網(wǎng)格單元密度按照從高到低順序排序，選取前k2個(gè)密度最高的空間網(wǎng)格單元作為候選初始聚類中心網(wǎng)格單元DCP(P=1,2…k2)。

K-means 初始聚類中心選取步驟如下：

步驟1：設(shè)定聚類個(gè)數(shù)k，劃分k3個(gè)空間網(wǎng)格單元，根據(jù)定義4 和定義6 計(jì)算網(wǎng)格密度ρg和網(wǎng)格質(zhì)心ηg。

步驟2：若任意近鄰空間網(wǎng)格質(zhì)心之間的距離小于距離閾值ω，則合并兩個(gè)空間網(wǎng)格單元。

步驟3：再次計(jì)算空間網(wǎng)格單元密度，并根據(jù)密度原則確定候選初始聚類中心網(wǎng)格DCP，其中最高密度空間網(wǎng)格質(zhì)心被選為第一個(gè)初始聚類中心center1。

步驟4：根據(jù)K-means++初始聚類中心選取方法，在候選初始聚類中心網(wǎng)格中選擇與第一個(gè)初始聚類中心距離最遠(yuǎn)的空間網(wǎng)格質(zhì)心作為新的聚類中心，直到選定k個(gè)聚類中心。初始聚類中心空間網(wǎng)格選取如圖4所示，深色虛線部分空間網(wǎng)格中樣本數(shù)最多并且它們的距離較遠(yuǎn)。

圖4 初始聚類中心空間網(wǎng)格選取Fig.4 Initial cluster center spatial grid selection

其中，datat為第t個(gè)初始聚類中心空間網(wǎng)格內(nèi)坐標(biāo)樣本點(diǎn)；ρt為空間網(wǎng)格密度。

2.3 算法步驟

綜合上述過(guò)程，基于SGDK 聚類的室內(nèi)定位垂直精度優(yōu)化方法具體實(shí)現(xiàn)步驟為：

步驟1：采集標(biāo)簽TDOA 數(shù)據(jù)，利用3σ準(zhǔn)則剔除異常值，使用Chan 算法解算標(biāo)簽估計(jì)位置，確定原始標(biāo)簽數(shù)據(jù)集dataα。

步驟2：標(biāo)簽數(shù)據(jù)集聚類劃分為k個(gè)子區(qū)域，確定各子區(qū)域參考位置。

設(shè)定聚類中心個(gè)數(shù)k，根據(jù)K-means 初始聚類中心選取規(guī)則確定初始聚類中心。

其中，centerq=(xq,yq,zq),q=1,2…k。

計(jì)算標(biāo)簽數(shù)據(jù)集中樣本點(diǎn)dataα到各聚類中心的距離d，將樣本點(diǎn)劃分到距離最近的簇中。

取每個(gè)簇?cái)?shù)據(jù)的均值，獲得新的聚類中心。

其中，Pj為聚類后第j個(gè)簇樣本點(diǎn)總個(gè)數(shù)；為第j個(gè)簇中樣本點(diǎn)數(shù)據(jù)之和。

若聚類中心不再變化或者達(dá)到最大迭代次數(shù)，則停止迭代，得到最終聚類中心。聚類中心即為每個(gè)簇的代表點(diǎn)，也被稱為標(biāo)簽數(shù)據(jù)集k子區(qū)域參考位置。

步驟3：加權(quán)質(zhì)心定位算法確定標(biāo)簽優(yōu)化位置。

計(jì)算各子區(qū)域參考位置到數(shù)據(jù)集中心位置μ的離散程度，中心位置為標(biāo)簽估計(jì)位置的均值。二者距離越近，相關(guān)性越高，離散程度越小，越具有參考價(jià)值。各參考位置與中心位置距離的倒數(shù)定義為權(quán)重因子σj。

將參考位置作為質(zhì)心定位算法中的多邊形頂點(diǎn)，分別為k個(gè)參考位置賦予權(quán)重因子σj，加權(quán)質(zhì)心法確定標(biāo)簽最終優(yōu)化位置。

2.4 算法復(fù)雜度分析

SGDK 聚類算法的時(shí)間復(fù)雜度主要包括數(shù)據(jù)空間網(wǎng)格化過(guò)程和K-means 聚類過(guò)程。假設(shè)原始標(biāo)簽數(shù)據(jù)集在空間大小為L(zhǎng)×W×H的區(qū)域內(nèi)共有n個(gè)樣本點(diǎn)，劃分N個(gè)空間網(wǎng)格單元，每個(gè)空間網(wǎng)格單元中有m個(gè)樣本點(diǎn)。算法在數(shù)據(jù)空間網(wǎng)格化的時(shí)間復(fù)雜度為O(N+m)，統(tǒng)計(jì)空間網(wǎng)格單元密度的時(shí)間復(fù)雜度為O(n)，計(jì)算各空間網(wǎng)格單元與其近鄰網(wǎng)格單元距離的時(shí)間復(fù)雜度為O(n2)，K-means 聚類過(guò)程時(shí)間復(fù)雜度為O(knT)，k是聚類個(gè)數(shù)，T是迭代次數(shù)。算法總時(shí)間復(fù)雜度為：

由式(29)可以看出，算法的計(jì)算量主要與空間網(wǎng)格單元數(shù)量N、聚類個(gè)數(shù)k和迭代次數(shù)T相關(guān)。

算法總空間復(fù)雜度為O(Nm+m)，其中數(shù)據(jù)空間網(wǎng)格化過(guò)程為O(Nm)，K-means 聚類過(guò)程為O(m) 。

3 實(shí)驗(yàn)分析與驗(yàn)證

3.1 實(shí)驗(yàn)環(huán)境

本實(shí)驗(yàn)采用的UWB 定位芯片為易百德微電子有限公司研發(fā)的EB1003，測(cè)距誤差小于0.1 m，主控芯片為國(guó)民技術(shù)的N32G452 系列MCU。

實(shí)驗(yàn)室搭建模擬實(shí)際應(yīng)用場(chǎng)景：實(shí)驗(yàn)室空間為8.3 m×7.3 m×3.7 m。貨架質(zhì)地為鐵質(zhì)，尺寸為6 m×0.5 m×2 m，分為三層，每層高度為0.85 m，間距為0.82 m。貨架上的物品為金屬制儀器設(shè)備，模擬真實(shí)應(yīng)用環(huán)境。實(shí)驗(yàn)環(huán)境和所用設(shè)備如圖5-6 所示。

圖5 實(shí)驗(yàn)環(huán)境模擬圖Fig.5 Simulation diagram of experimental environment

圖6 實(shí)驗(yàn)場(chǎng)景和設(shè)備Fig.6 Experimental scenarios and equipment

錨節(jié)點(diǎn)位置（單位為m）分別為：BS1(0,0,0)、BS2(1.200,3.577,-1.340)、BS3(5.796,3.677,-0.460)、BS4(7.556,0,-1.700)、BS5(5.796,-3.430,-0.460)、BS6(1.200,-3.460,-1.340)。采用激光測(cè)距儀測(cè)量標(biāo)簽真實(shí)位置，測(cè)距精度可達(dá)±5 mm。定位模塊與激光測(cè)距儀性能如表1 所示。

表1 實(shí)驗(yàn)設(shè)備性能Tab.1 Experimental equipment performance

實(shí)驗(yàn)共采集了14 個(gè)標(biāo)簽位置數(shù)據(jù)，圖7 展示了在復(fù)雜實(shí)驗(yàn)條件下具有代表性的4 個(gè)標(biāo)簽位置。每0.2～0.3 s 標(biāo)簽與錨節(jié)點(diǎn)之間會(huì)發(fā)送和接收信號(hào)一次，對(duì)每個(gè)標(biāo)簽位置進(jìn)行 300 次數(shù)據(jù)采集，并利用MATLAB R2018b 仿真軟件進(jìn)行數(shù)據(jù)處理。

圖7 標(biāo)簽位置Fig.7 Label position

3.2 實(shí)驗(yàn)結(jié)果與性能分析

1) 標(biāo)簽垂直方向誤差對(duì)定位精度的影響。

在室內(nèi)環(huán)境下，標(biāo)簽定位受到錨節(jié)點(diǎn)布設(shè)限制和鐵質(zhì)貨架等障礙物的干擾，導(dǎo)致定位精度受到一定程度的影響，垂直方向上的干擾和誤差通常會(huì)比水平方向上大。

為驗(yàn)證錨節(jié)點(diǎn)布設(shè)限制和鐵質(zhì)貨架等障礙物對(duì)標(biāo)簽定位精度的影響，在貨架中間層隨機(jī)選取一個(gè)定位點(diǎn)進(jìn)行實(shí)驗(yàn)，采集150 組TDOA 數(shù)據(jù)，通過(guò)Chan 算法解算出標(biāo)簽的估計(jì)位置。X、Y、Z 三個(gè)方向上的點(diǎn)位誤差如圖8 所示，標(biāo)簽水平方向點(diǎn)位誤差多數(shù)在0.2～0.4 m 范圍內(nèi)波動(dòng)，垂直方向點(diǎn)位誤差多數(shù)在0.2～1 m 范圍內(nèi)波動(dòng)。Chan 算法解算出的標(biāo)簽估計(jì)位置的定位誤差通常垂直方向比水平方向大，因此在受限環(huán)境下，提升垂直方向的定位精度是影響整體定位準(zhǔn)確性的關(guān)鍵。

圖8 Chan 算法在不同方向的點(diǎn)位誤差絕對(duì)值Fig.8 Absolute value of point position errors of Chan algorithm in different directions

本文提出的基于SGDK 聚類的室內(nèi)定位垂直精度優(yōu)化算法可以有效減小垂直方向定位誤差，表2 給出了將原始標(biāo)簽數(shù)據(jù)集劃分兩個(gè)區(qū)域確定標(biāo)簽優(yōu)化位置時(shí)的實(shí)驗(yàn)數(shù)據(jù)，垂直方向最大點(diǎn)位誤差0.246 m，最小點(diǎn)位誤差0.006 m，平均點(diǎn)位誤差為0.134 m。垂直方向定位精度可以達(dá)到毫米級(jí)。

表2 實(shí)驗(yàn)數(shù)據(jù)Tab.2 Experimental data

2) 聚類個(gè)數(shù)k值對(duì)定位精度的影響。

在實(shí)驗(yàn)中，將聚類個(gè)數(shù)k設(shè)置為2～6。聚類過(guò)程如圖9 所示，SGDK 聚類算法將原始標(biāo)簽數(shù)據(jù)集劃分為兩個(gè)區(qū)域，區(qū)域中心即為該區(qū)域的參考位置（圖中六角星標(biāo)記的位置）。對(duì)參考位置賦予不同權(quán)重因子，通過(guò)加權(quán)質(zhì)心法確定標(biāo)簽最終優(yōu)化位置（圖中紅色菱形標(biāo)記的位置）。

圖9 聚類過(guò)程Fig.9 Clustering process

為驗(yàn)證不同k值對(duì)定位精度的影響，計(jì)算了14 個(gè)標(biāo)簽位置垂直方向點(diǎn)位誤差，結(jié)果如圖10 所示。當(dāng)k為2～6 時(shí)，垂直方向平均點(diǎn)位誤差分別為0.134 m、0.142 m、0.140 m、0.152 m 和0.158 m。通過(guò)實(shí)驗(yàn)數(shù)據(jù)可以發(fā)現(xiàn)，在大多數(shù)情況下將數(shù)據(jù)集劃分為兩個(gè)區(qū)域確定標(biāo)簽最優(yōu)位置時(shí)，垂直方向的定位精度最高。

圖10 不同k 值下垂直方向點(diǎn)位誤差絕對(duì)值Fig.10 Absolute value of point position errors in the vertical direction at different k values

圖11 顯示了使用SGDK 聚類算法將數(shù)據(jù)集劃分兩個(gè)區(qū)域以確定標(biāo)簽最優(yōu)位置時(shí)三個(gè)方向上的點(diǎn)位誤差。從圖中可知，水平方向點(diǎn)位誤差小于0.4 m，垂直方向點(diǎn)位誤差小于0.3 m。其中，X 方向平均點(diǎn)位誤差為0.157 m；Y 方向平均點(diǎn)位誤差為0.164 m；Z 方向平均點(diǎn)位誤差為0.134 m，驗(yàn)證了本文算法不僅可以提升標(biāo)簽垂直方向的定位精度，對(duì)系統(tǒng)整體的定位精度也有所提升。

圖11 三個(gè)方向點(diǎn)位誤差絕對(duì)值Fig.11 Absolute value of point position errors in three directions

3.3 方法對(duì)比

圖12 顯示了隨機(jī)選取一個(gè)標(biāo)簽定位點(diǎn)進(jìn)行實(shí)驗(yàn)，采集 150 組 TDOA 數(shù)據(jù)，通過(guò) Chan 算法[14]、Chan-Taylor 算法[15]、Kalman-Chan 算法[16]得到標(biāo)簽估計(jì)位置在垂直方向上的點(diǎn)位誤差，Chan 算法和Chan-Taylor 算法誤差可達(dá)到1.3 m，Kalman-Chan 算法誤差可達(dá)到0.7 m。結(jié)果表明，傳統(tǒng)定位算法很難降低標(biāo)簽在垂直方向上的定位誤差。

圖12 垂直方向點(diǎn)位誤差絕對(duì)值Fig.12 Absolute value of point position errors in vertical direction

為了驗(yàn)證本文提出SGDK 聚類的垂直精度優(yōu)化算法的定位效果，對(duì)14 個(gè)標(biāo)簽位置采用了Chan 算法、Chan-Taylor 算法、Kalman-Chan 算法、Chan-Kmeans算法以及本文提出的算法進(jìn)行了比較，結(jié)果如圖13所示。從圖中可以看出，相比于傳統(tǒng)的定位算法，本文提出的算法可以顯著降低垂直方向的定位誤差。傳統(tǒng)的K-means 聚類隨機(jī)選取初始聚類中心，定位結(jié)果易受離群值影響，并且每次聚類得到的定位結(jié)果都有所不同。本文算法在此基礎(chǔ)上進(jìn)行了改進(jìn)，相比于隨機(jī)初始聚類中心的Chan-Kmeans 算法，本文算法具有更優(yōu)的定位精度，垂直方向的定位誤差可以達(dá)到毫米級(jí)。

圖13 垂直方向平均點(diǎn)位誤差絕對(duì)值Fig.13 Absolute value of average point position errors in vertical direction

表3 顯示了五種算法在垂直方向上的平均絕對(duì)誤差（Mean Absolute Error,MAE）和總體均方根誤差（Root Mean Square Error,RMSE）。MAE 和RMSE定義如式(30)(31)所示：

表3 定位算法精度對(duì)比Tab.3 Precision comparison of positioning algorithms

相比較于 Chan 算法、Chan-Taylor 算法、Kalman-Chan 算法和Chan-Kmeans 算法，本文算法在垂直方向定位精度分別提升了62.88%、70.81%、41.74%、27.96%，總體定位精度分別提升了54.46%、55.82%、18.68%、7.79%。

4 結(jié)論

在室內(nèi)定位中，由于錨節(jié)點(diǎn)高度布設(shè)限制，導(dǎo)致標(biāo)簽在垂直方向定位精度往往比水平方向的定位精度更低，提升標(biāo)簽垂直方向定位精度一直是亟待解決的難點(diǎn)。本文提出了基于SGDK 聚類的室內(nèi)定位垂直精度優(yōu)化方法，將K-means 聚類算法和網(wǎng)格聚類算法結(jié)合起來(lái)，對(duì)所獲得的原始標(biāo)簽數(shù)據(jù)集進(jìn)行分類，進(jìn)而確定標(biāo)簽最終優(yōu)化位置，不僅提高了室內(nèi)定位垂直方向的定位精度，還減少了離群點(diǎn)對(duì)K-means 聚類結(jié)果的影響。實(shí)驗(yàn)結(jié)果表明，本文算法與傳統(tǒng)定位算法相比在垂直方向具有更高的定位精度。

未來(lái)將采用多傳感器融合定位或利用深度學(xué)習(xí)算法對(duì)信號(hào)進(jìn)行預(yù)處理和優(yōu)化等方式，進(jìn)一步提升室內(nèi)定位精度。