基于隨機(jī)子集抽樣的高效室內(nèi)指紋定位算法

中圖分類號：TP391 文獻(xiàn)標(biāo)志碼：A

Efficient indoor fingerprinting localization algorithm based on random subset sampling

LEI Ruolan， LE Yanfen （School of Optical-Electrical and Computer Engineering， University of Shanghai for Science and Technology， Shanghai 200093， China）

Abstract： In view of the fact that the strength of wireless signals in complex indoor environments has anomalies due to the influence of the sudden noise in the propagation environment， an algorithm for WiFi fingerprinting localization based on online coarse positioning and random subset sampling was proposed. First， the algorithm utilized the specific coverage characteristics of access point （AP） signals to rapidly and accurately constrain the target's position to a local region， thereby identifying candidate reference points （RP） near the true location. Subsequently， random subset sampling was employed to generate multiple subsets of signal distances， which were then averaged to mitigate the influence of abnormal AP signals on distance measurements. Finally， a weighted K-nearest neighbors algorithm was applied to estimate the target's position. Experiments were conducted using a publicly available dataset collected from real indoor environments to evaluate the accuracy of both online caorse positioning and random subset sampling. The results demonstrate the efectiveness of the proposed algorithm and reveal the impact of parameter selection on localization performance. Comparative studies with existing fingerprint-based localization algorithms show that the online coarse localization method effectively identifies candidate reference points near the user's true position， while the random subset sampling technique significantly reduces large localization errors. Even when AP signals exhibit abnormalities， the proposed algorithm maintains superior positioning accuracy compared to conventional algorithms.

Keywords： fingerprinting localization; AP covering vector; online coarse positioning; random subset sampling; AP abnormality

隨著互聯(lián)網(wǎng)和智能終端的快速發(fā)展，基于位置服務(wù)（locationbased services，LBS）受到各行業(yè)的廣泛關(guān)注。在開放的室外環(huán)境中，全球定位系統(tǒng)（global positioningsystem，GPS）能夠提供高精度的定位服務(wù)，但在復(fù)雜的室內(nèi)環(huán)境中，GPS信號會快速衰減，無法完成有效定位[1]。近年來，研究人員提出了多種不同類型的無線信號，如藍(lán)牙[2]WiFi[3]、超寬帶（ultra wide band，UWB）[4]、射頻識別（radio frequency identification，RFID）[5]等，用于實(shí)現(xiàn)不同定位場景中的室內(nèi)定位。

基于WiFi指紋的室內(nèi)定位技術(shù)由于低成本、低功耗、易部署的特點(diǎn)成為研究熱點(diǎn)。WiFi指紋定位包括兩個(gè)階段：離線階段和在線階段。離線階段：定位服務(wù)提供商（localizationserviceprovider，LSP）在室內(nèi)環(huán)境中采集參考點(diǎn)（referencepoint，RP）中來自各接入點(diǎn)（accesspoint，AP）的接收信號強(qiáng)度（received signal strength，RSS），并與其對應(yīng)的位置信息一起構(gòu)建離線指紋數(shù)據(jù)庫；在線階段：實(shí)時(shí)獲取目標(biāo)對象的RSS向量，通過匹配算法與離線數(shù)據(jù)庫進(jìn)行比較，求得目標(biāo)估計(jì)位置。

最早基于WiFi的定位研究出現(xiàn)于RADAR系統(tǒng)中，服務(wù)商通過計(jì)算不同的RSS向量之間的距離，采用K近鄰[算法得到定位結(jié)果。后續(xù)研究為改善性能，引入加權(quán)K近鄰[8（weightedK-nearestneighbor，WKNN）算法來優(yōu)化權(quán)重。隨著機(jī)器學(xué)習(xí)算法的發(fā)展，神經(jīng)網(wǎng)絡(luò)[]、回歸模型[10]、貝葉斯網(wǎng)絡(luò)模型[11]、支持向量機(jī)[12-1]等方法被用到定位中來完成目標(biāo)位置估計(jì)，但這類算法通常需要離線訓(xùn)練大量數(shù)據(jù)，復(fù)雜度較高。且定位環(huán)境的變化，如短時(shí)布局變動(dòng)、人員短時(shí)活動(dòng)等，會導(dǎo)致在線RSS出現(xiàn)瞬時(shí)大的波動(dòng)，此時(shí)，在線指紋與離線指紋匹配度較低，離線訓(xùn)練模型的準(zhǔn)確性會有一定的降低，引起定位誤差的增大。針對動(dòng)態(tài)環(huán)境中信號存在大波動(dòng)的應(yīng)用場景，He 等[14] 首次提出了一種基于指紋子空間的定位方案（LAAFU），通過構(gòu)建多個(gè)指紋子集來生成多個(gè)估計(jì)位置?？紤]到當(dāng)指紋子集中包含異常AP信號時(shí)，生成的估計(jì)位置會遠(yuǎn)離自標(biāo)的真實(shí)位置，該方案引入了AP（affinitypropagation）聚類算法來確定可信度最高的若干參考點(diǎn)。該方法無需離線階段訓(xùn)練定位模型，但要求獲得足夠數(shù)量的指紋子集才能形成有效聚類。針對LAAFU的完全隨機(jī)子集生成方式，樂燕芬等[15]對其進(jìn)行改進(jìn)，綜合考慮了目標(biāo)可接收和不可接收的AP信號對定位的影響，提出了新的子集生成方式。但該方式同樣需要生成足夠數(shù)量的估計(jì)位置來形成有效的分簇，不適用于AP數(shù)量不多的定位環(huán)境。

為減小定位過程中的計(jì)算開銷，也有文獻(xiàn)提出對目標(biāo)進(jìn)行粗定位，用計(jì)算開銷小的算法首先把目標(biāo)定位到某一局部區(qū)域內(nèi)，再進(jìn)行二次精確定位。如田洪亮等[1提出基于K-means算法對離線指紋RSS進(jìn)行分簇的方法，計(jì)算目標(biāo)RSS與各個(gè)簇中心向量的距離，選取相似度最高的目標(biāo)簇，取簇中RP作為粗定位的候選RP。基于RSS信號特征分簇，同一簇內(nèi)RP可能出現(xiàn)信號特征相似但實(shí)際物理位置較分散的情況。Feng等[17]采用

AP聚類算法對參考位置點(diǎn)進(jìn)行分簇，僅考慮各指紋中對應(yīng)RSS值較高的AP，以確定其對應(yīng)的AP集合，通過AP聚類實(shí)現(xiàn)分簇，達(dá)到粗定位目的。該方案要求離線階段AP信號分布較穩(wěn)定，以確定較為準(zhǔn)確的AP集合。Khalajmehrabadi等[18]利用離線指紋的AP覆蓋向量對其進(jìn)行分簇，在線階段對目標(biāo)AP覆蓋向量進(jìn)行簇匹配，覆蓋向量相似的兩者通常物理位置相近。但是，當(dāng)目標(biāo)接收的RSS信號出現(xiàn)波動(dòng)或者目標(biāo)處于多個(gè)簇的臨界位置時(shí)，以上方案可能出現(xiàn)簇的誤匹配問題，由于后續(xù)是在粗定位簇內(nèi)的候選RP中進(jìn)行二次精確定位，上述情況可能導(dǎo)致最終定位結(jié)果出現(xiàn)較大誤差。

針對上述問題，本文提出了一種基于AP覆蓋向量的在線粗定位方法。考慮到具有相似覆蓋向量的兩點(diǎn)物理位置通常較接近，將目標(biāo)的AP覆蓋向量與離線指紋的AP覆蓋向量進(jìn)行距離比較，選定 N 個(gè)最近鄰作為候選RP。此時(shí)，各RP物理位置較接近，有效避免了上述相關(guān)方案中由信號波動(dòng)而引起的定位誤差，且無需進(jìn)行離線分操作以及面對在線階段簇的誤匹配問題，大幅度減小了二次精確定位階段指紋匹配的計(jì)算開銷。同時(shí)，引入一種新的隨機(jī)子集抽樣方法來選取更優(yōu)K近鄰，降低外界突發(fā)噪聲的干擾。該算法相較于LAAFU，無需形成足夠多的估計(jì)位置，定位過程只涉及一次位置估計(jì)，可以有效抑制大的定位誤差，提高了定位性能。

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

本文提出了一種基于在線粗定位和隨機(jī)子集抽樣的指紋定位算法。離線階段，LSP建立各RP對應(yīng)的指紋數(shù)據(jù)庫；在線階段，目標(biāo)對象采集自身RSS向量，服務(wù)器端計(jì)算得到相應(yīng)的AP覆蓋向量，同時(shí)計(jì)算其與離線RP的AP覆蓋向量的Jaccard相似度，選取相似度較高的 N 個(gè)RP作為候選RP集，實(shí)現(xiàn)粗定位。然后，服務(wù)器端隨機(jī)生成一個(gè)AP子集索引向量，對目標(biāo)對象的RSS向量進(jìn)行子集抽樣操作?；谠揂P索引，計(jì)算第s 個(gè)候選RP的離線指紋與目標(biāo)指紋子集向量間的信號距離 d_s ， s∈[1，N] 。重復(fù) M 次子集抽樣過程，各候選RP與目標(biāo)間得到 M 個(gè)距離，對 M 個(gè)距離進(jìn)行均值處理，將此均值作為兩者間的最終信號距離 D_s 。方案中采用多次子集抽樣形成的平均信號距離，可降低目標(biāo)RSS信號中可能包含的異常值對真實(shí)最近鄰選擇的影響。本文所提出的方案依據(jù) D_s 選取K近鄰，采用WKNN算法求得目標(biāo)估計(jì)位置。算法流程圖如圖1所示。

1.1 離線階段

LSP采集各RP的位置信息以及來自所有AP的RSS信號，構(gòu)成原始離線指紋數(shù)據(jù)庫。假設(shè)目標(biāo)監(jiān)測區(qū)域部署有 ?m 個(gè) RP 、 n 個(gè)AP，構(gòu)建的指紋庫中第 i 條指紋可表示為

式中： ，表示第 i 條指紋的位置； 表示第 i 個(gè)RP接收的來自所有AP的RSS向量；r_in 表示來自第 n 個(gè)AP的RSS。對于未檢測到信號強(qiáng)度的AP，將其信號值定義為0。同時(shí)，由RSS指紋信息可確定每個(gè)AP覆蓋向量。設(shè)第 i 個(gè)離線指紋的覆蓋向量為

式中， c_in 為二進(jìn)制向量值，如果該AP處RSS值不為0， c_in 就為1，否則取 0 。

1.2 在線階段

在線階段，LSP首先要利用覆蓋向量的相似性確定候選RP集，完成目標(biāo)粗定位；然后再通過基于子集抽樣的二次精確定位，完成對目標(biāo)的最終位置估計(jì)。

1.2.1 確定候選RP

當(dāng)原始離線指紋庫的數(shù)據(jù)量較大時(shí)，指紋匹配過程需要在整個(gè)監(jiān)控區(qū)域內(nèi)進(jìn)行，這會造成較大的計(jì)算開銷。本文通過下述方法確定一個(gè)候選RP集，將目標(biāo)定位在局部區(qū)域內(nèi)，以減小后續(xù)定位過程中目標(biāo)指紋與離線指紋匹配時(shí)的計(jì)算開銷。在線階段，假設(shè)目標(biāo)接收到的RSS向量為

對目標(biāo)指紋也采用與離線指紋類似的方法，確定當(dāng)前AP的覆蓋向量 c_t ，表示為

如果 r_tn 不為0， c_tn 就為1，否則取0。

在復(fù)雜的室內(nèi)環(huán)境中，AP無線信號的衰減特性與環(huán)境布局密切相關(guān)，且都有其特定的信號覆蓋區(qū)域。因此，覆蓋向量可以表明該位置處AP的分布情況。為了考察每個(gè)AP的覆蓋區(qū)域，現(xiàn)選取某實(shí)際室內(nèi)場景的公開數(shù)據(jù)集[19]中的2個(gè)AP（AP23和AP29）進(jìn)行實(shí)驗(yàn)，繪制出其信號覆蓋情況，如圖2所示?？梢园l(fā)現(xiàn)，被同一AP所覆蓋的RP位置相近，說明具有較相似覆蓋向量的兩點(diǎn)其物理位置通常較接近。

本文采用Jaccard系數(shù)來衡量 c_i 和 C_t 的相似度，Jaccard系數(shù)通常用于比較有限樣本集之間的相似性與差異性。Jaccard系數(shù)越大，說明 c_i 和C_t 在相同位置有更多的相同元素，即可接收或不可接收的AP集越相似，說明目標(biāo)對象與該參考點(diǎn)位置越接近。本方案提出計(jì)算 c_i 與 C_t 之間的Jaccard相似度，表示為

對于兩個(gè) n 維二進(jìn)制向量，它們之間的Jaccard相似度計(jì)算可轉(zhuǎn)化為

式中： ; 。

利用式（6計(jì)算用戶與指紋庫內(nèi)所有RP覆蓋向量的相似度，選取相似度較高的前 N 個(gè)覆蓋向量對應(yīng)的RP作為候選RP，其所在區(qū)域構(gòu)成了目標(biāo)的粗定位區(qū)域。候選RP的RSS向量可以表示為

1.2.2二次精確定位

本文所提出的二次精確定位算法具體步驟如下：

a.AP隨機(jī)子集抽樣

對目標(biāo)接收到的信號 進(jìn)行AP子集抽樣，根據(jù)隨機(jī)生成的長度為 l（l

根據(jù)所抽取的AP子集，任一候選RP相應(yīng)的指紋子集表示為

式中， s∈[1，N] 。

計(jì)算 與 信號空間的余弦距離，得到第s 個(gè)候選RP的離線指紋與目標(biāo)指紋子集向量間的信號距離 d_s ：

重復(fù)該子集隨機(jī)抽樣過程 M 次，則各離線指紋對于目標(biāo)指紋均求得 M 個(gè)距離，對這 M 個(gè)距離求取平均值，得到兩者間的最終距離 D_s

式中， d_sj 表示第 s 個(gè)候選RP的離線指紋在第 j 次子集抽樣過程中與目標(biāo)指紋間的信號距離，

由于抽樣的隨機(jī)性，子集可能抽到大量信號值為0的AP或者異常 AP 。AP有效信息量的不足會對定位結(jié)果產(chǎn)生較大影響，通過重復(fù)多次隨機(jī)抽樣操作取平均值的方式，不僅能充分利用AP信息，同時(shí)，最小化異常子集對信號空間距離計(jì)算的影響，得出目標(biāo)指紋與候選RP間更精準(zhǔn)的距離值，以確保后續(xù)選出目標(biāo)真實(shí)位置附近的K近鄰，達(dá)到提高定位性能的目的。

b.求取目標(biāo)估計(jì)位置

選取距離最小的前 K 個(gè)指紋對應(yīng)的RP位置作為最近鄰，取距離倒數(shù)作為各RP位置 P_i（x，y） 的初始權(quán)重，而后歸一化該權(quán)重，對各RP位置依照歸一化后權(quán)重求和，得到目標(biāo)估計(jì)位置 P（x，y） ：

該算法具體過程如表1所示。

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

通過在實(shí)際室內(nèi)場景的公開數(shù)據(jù)集[19]中進(jìn)行實(shí)驗(yàn)來驗(yàn)證本文算法的有效性。該數(shù)據(jù)集共采集3層樓的RSS信息，每層樓布局一致，面積為 1425m² ，共部署有32個(gè)AP。數(shù)據(jù)集包含各樓層不同RP處所測得的RSS信息及其對應(yīng)位置信息。其中，一樓采集到397條指紋信息，二樓采集到711條指紋信息，三樓采集到431條指紋信息。以二樓為例，實(shí)驗(yàn)布局如圖3所示，“*”代表參考位置點(diǎn)，“#”代表從指紋庫隨機(jī)抽取的在線測試點(diǎn)。

在每層數(shù)據(jù)庫中隨機(jī)抽取100個(gè)RSS指紋信息作為在線測試數(shù)據(jù)，其余作為離線指紋信息，后續(xù)實(shí)驗(yàn)此參數(shù)保持不變。測試點(diǎn)的定位誤差定義為其真實(shí)坐標(biāo)與估計(jì)位置坐標(biāo)之間的歐氏距離，計(jì)算所有測試點(diǎn)的平均定位誤差及定位誤差的累積分布函數(shù)（cumulativedistribution function，CDF）作為衡量算法定位性能的指標(biāo)。

2.1 在線粗定位的準(zhǔn)確度分析

為驗(yàn)證本文所提出的在線粗定位方法的實(shí)用性，將其與文獻(xiàn)[16所提到的基于K-means的離線粗定位方法進(jìn)行對比實(shí)驗(yàn)，兩種實(shí)驗(yàn)僅存在前期粗定位方法的差異，后續(xù)實(shí)驗(yàn)均按照本文所提出的隨機(jī)子集抽樣方法進(jìn)行二次精確定位

圖4給出了兩種粗定位方法下各測試點(diǎn)的定位誤差情況。實(shí)驗(yàn)參數(shù)如下：選取50個(gè)測試點(diǎn)，在粗定位階段，本文所提出的在線粗定位方法根據(jù)覆蓋向量選取40個(gè)候選RP，離線粗定位方法將全指紋庫數(shù)據(jù)劃分為5簇；然后，在二次精確定位階段，兩種方法均對粗定位得到的RP集進(jìn)行隨機(jī)抽取AP子集，隨機(jī)10次，AP子集長度為10；最終WKNN匹配時(shí)最近鄰點(diǎn) K=5 。由結(jié)果可知：兩種方法 80% 的測試點(diǎn)定位誤差在 4m 以下；本文所提出的在線粗定位方法平均定位誤差為 2.62m ：而離線粗定位方法平均定位誤差為 3.20m ，且其中部分測試點(diǎn)的定位誤差過大，最大達(dá)到 20.03m 。造成這一差距的原因可能與離線粗定位時(shí)簇的劃分有關(guān)。

為進(jìn)一步分析定位誤差，選取誤差最大的測試點(diǎn)，圖5、圖6分別給出了該測試點(diǎn)在離線、在線粗定位兩種情況下的定位結(jié)果。

離線K-means算法將誤差最大的測試點(diǎn)劃分到簇4中，但由圖5可知，該測試點(diǎn)實(shí)際距離簇4較遠(yuǎn)，距離類1更近。由于該測試點(diǎn)出現(xiàn)在不同簇類的邊緣，在計(jì)算測試點(diǎn)與不同簇中心的距離時(shí)出現(xiàn)偏差，導(dǎo)致其所屬簇的錯(cuò)誤劃分。后續(xù)是在粗定位簇內(nèi)（即簇4）的RP中進(jìn)行二次精確定位，錯(cuò)誤的簇匹配導(dǎo)致了最終定位結(jié)果出現(xiàn)較大誤差。采用本文所提出的基于覆蓋向量的候選RP在線選擇方式，最終選出的 N 個(gè)RP如圖6所示。盡管有部分候選RP分布在測試點(diǎn)較遠(yuǎn)的位置，但其真實(shí)位置附近的大多數(shù)RP均被選為候選RP，有效避免了離線分簇可能導(dǎo)致的較大定位誤差。

2.2 隨機(jī)子集抽樣的準(zhǔn)確度分析

為驗(yàn)證本文所提出的隨機(jī)子集抽樣方法的有效性，將其與固定子集抽樣方法進(jìn)行對比。在確定測試點(diǎn)候選RP集后，分別使用本文所提出的隨機(jī)子集抽樣與固定子集抽樣進(jìn)行測試點(diǎn)的二次精確定位。在4次實(shí)驗(yàn)中，固定子集抽樣方法分別選取指紋庫中前15個(gè)AP、中間15個(gè)AP、后15個(gè)AP，隨機(jī)子集抽樣方法則隨機(jī)選取15個(gè)AP，實(shí)驗(yàn)結(jié)果如圖7所示?？梢钥闯觯S機(jī)子集抽樣方法表現(xiàn)出更加穩(wěn)定的定位性能。在固定子集抽樣實(shí)驗(yàn)中，后3次實(shí)驗(yàn)相較于第1次實(shí)驗(yàn)的定位誤差均明顯增大，達(dá)到 3m 以上，這可能由于其所抽取的AP子集中包含異常AP，影響了最終的定位性能。隨機(jī)子集抽樣方法降低了定位中采用異常AP的概率，有利于定位性能的提高。

2.3 算法高效性分析

本文算法通過在線粗定位確定的候選RP分布如圖8所示。相較于傳統(tǒng)定位方案的全局指紋匹配，在線粗定位可將目標(biāo)快速、準(zhǔn)確地定位到局部區(qū)域內(nèi)，可有效降低后續(xù)二次精確定位階段指紋匹配的計(jì)算開銷。

本文算法提出了在線粗定位階段采用Jaccard相似度作為指紋匹配的依據(jù)，為驗(yàn)證其高效性，將其與傳統(tǒng)的基于漢明距離、歐氏距離的指紋匹配方法進(jìn)行實(shí)驗(yàn)對比。隨機(jī)選取一條指紋庫指紋作為在線指紋，與剩下的710條離線指紋進(jìn)行匹配，比較不同情況下的時(shí)間開銷，實(shí)驗(yàn)結(jié)果如表2所示。本文所提出的基于Jaccard相似度的指紋匹配方法具有較低時(shí)間開銷，實(shí)用性優(yōu)于其他兩種方法。

2.4 參數(shù)選擇對性能的影響

本文算法在離線階段不需要進(jìn)行定位模型的訓(xùn)練，而是直接根據(jù)在線接收的RSS向量進(jìn)行目標(biāo)定位。在粗定位和隨機(jī)子集抽樣過程中，涉及到多個(gè)參數(shù)，如：粗定位時(shí)的候選RP數(shù) N 、隨機(jī)抽樣子集數(shù) M 、子集中的AP數(shù)l。為研究各參數(shù)對定位性能的影響，通過上述公共數(shù)據(jù)集進(jìn)行相應(yīng)實(shí)驗(yàn)，實(shí)驗(yàn)參數(shù)與上文一致。

a.候選RP數(shù) N

在粗定位階段，候選RP數(shù)對于確定目標(biāo)可能所在局部空間的大小起著重要作用。實(shí)驗(yàn)初始抽取10個(gè)子集，每個(gè)子集中包含隨機(jī)抽取的15個(gè)AP，改變粗定位階段的候選RP數(shù)，觀察定位誤差變化，實(shí)驗(yàn)結(jié)果如圖9所示。在一定范圍內(nèi)，隨著候選RP數(shù)的增加，平均定位誤差逐漸減小，當(dāng)候選RP數(shù)達(dá)到一定值后，其改變對定位精度的影響不大。在實(shí)際應(yīng)用中，過多的候選RP會增加算法的計(jì)算復(fù)雜度，還可能包含一些距離目標(biāo)較遠(yuǎn)的RP，從而降低定位精度。因此，需要在合理范圍內(nèi)選擇適當(dāng)數(shù)量的候選RP來平衡定位精度和計(jì)算復(fù)雜度。

b.抽樣子集數(shù) M

實(shí)驗(yàn)設(shè)置粗定位階段選取40個(gè)候選RP，在后續(xù)子集抽樣中，每個(gè)子集包含15個(gè)隨機(jī)抽取的AP。改變子集的個(gè)數(shù) M 進(jìn)行實(shí)驗(yàn)，所得結(jié)果如圖10所示。在一定范圍內(nèi)，隨著子集數(shù)量的增多，定位誤差逐漸減小，當(dāng)子集個(gè)數(shù)達(dá)到一定數(shù)量后，其對定位精度的影響逐漸減小。由于子集抽樣過程中的AP選擇是隨機(jī)的，可能導(dǎo)致抽取的子集中包含大量信號值為0的AP，RSS信息量不足會導(dǎo)致后續(xù)算法的定位結(jié)果產(chǎn)生偏差，選擇較多數(shù)量的子集可以有效降低以上特殊情況對定位精度的影響。在實(shí)際應(yīng)用中，為降低算法的復(fù)雜度，需要在合理范圍內(nèi)選擇適當(dāng)數(shù)量的子集。

c.子集中的AP數(shù)1

實(shí)驗(yàn)設(shè)置粗定位階段選取40個(gè)候選RP，抽取10個(gè)子集，改變子集中的AP數(shù)l，實(shí)驗(yàn)結(jié)果如圖11所示。隨著所選AP數(shù)量的增加，定位精度不斷提高。充分利用AP信息，有利于更加準(zhǔn)確地實(shí)現(xiàn)目標(biāo)的定位，實(shí)際應(yīng)用中可根據(jù)整個(gè)定位區(qū)域AP數(shù)量進(jìn)行選取。

2.5 與已有方法的比較

為進(jìn)一步驗(yàn)證本文算法的性能，與已有的WKNN、WKNN-Kmeans、PCA-KRR 算法[20]進(jìn)行對比實(shí)驗(yàn)。其中：WKNN-Kmeans在離線階段利用Kmeans算法對指紋聚類，在線階段通過簇匹配實(shí)現(xiàn)目標(biāo)粗定位，再在簇內(nèi)利用WKNN實(shí)現(xiàn)定位；PCA-KRR算法是對指紋庫中數(shù)量眾多的AP信號提取主成分，實(shí)現(xiàn)數(shù)據(jù)降維，再利用核嶺回歸算法建立位置與RSS信號的模型。在本實(shí)驗(yàn)中，已將各對比算法參數(shù)調(diào)至最優(yōu)，所得定位誤差的累積分布函數(shù)如圖12所示，

權(quán)衡本文算法的計(jì)算復(fù)雜度和定位精度，將參數(shù)設(shè)置為：粗定位階段選取40個(gè)候選RP，抽取10個(gè)子集，每個(gè)子集包含15個(gè)隨機(jī)抽取的AP。由圖12可知，本文算法中： 90% 的定位誤差小于 5m ；WKNN算法和 WKNN-Kmeans算法中，70% 的定位誤差小于 5m ；PCA-KRR算法中， 60% 的定位誤差小于 5m 。本文算法、WKNN、WKNN-Kmeans、PCA-KRR算法的平均定位誤差分別為2.47、4.06、4.20、 4.54m 。本文算法有效降低了平均定位誤差，對比WKNN、WKNN-Kmeans、PCA-KRR算法，本文算法的定位精度分別提升了39% 、 41% 、 46% 。

2.6 AP異常對定位精度的影響

在實(shí)際應(yīng)用中，可能存在某些AP異常的情況，如目標(biāo)在線采集信號時(shí)，少數(shù)AP被關(guān)閉或被交換位置，導(dǎo)致信號接收出現(xiàn)偏差，從而對定位結(jié)果產(chǎn)生影響。實(shí)驗(yàn)對比了兩種AP異常情況下本文算法與WKNN、WKNN-Kmeans、PCA-KRR算法定位誤差的差異，結(jié)果如表3和表4所示。

隨著交換AP、關(guān)閉AP個(gè)數(shù)的逐漸增多，4種方法的定位性能均逐漸下降，但本文算法有效抑制了指紋偏差引入的大定位誤差。對比于WKNN、WKNN-Kmeans、PCA-KRR算法，本文算法的定位精度提升了至少 20% 。在實(shí)際應(yīng)用中，本文算法具有更好的魯棒性，面對AP異常時(shí)，能夠?qū)崿F(xiàn)更好的定位性能

3結(jié)論

針對RSS信號受傳播環(huán)境突發(fā)噪聲影響以及AP信號存在異常的實(shí)際情況，提出了一種基于隨機(jī)子集抽樣的高效室內(nèi)指紋定位算法。該算法在線階段利用AP覆蓋向量完成目標(biāo)粗定位，可快速將目標(biāo)定位到局部區(qū)域，然后采用隨機(jī)子集抽樣實(shí)現(xiàn)了目標(biāo)位置的二次精確估計(jì)。此外，從不同粗定位方法、不同的參數(shù)選擇、AP異常等方面對算法進(jìn)行了分析，并與其他室內(nèi)定位算法進(jìn)行了對比。實(shí)驗(yàn)結(jié)果表明，本文所提出的定位算法能有效降低指紋匹配的計(jì)算開銷，具有良好的定位性能。

參考文獻(xiàn)：

[1] HE S N， CHAN S H G. Wi-Fi fingerprint-based indoor positioning：recentadvancesandcomparisons[J]. CommunicationsSurveysamp; Tutorials， 2016，18（1）： 466-490.

[2]RUAN L， ZHANG L， ZHOU T， et al. An improved bluetooth indoor positioning method using dynamic fingerprint window[J]. Sensors （Basel）， 2020，20（24）： 7269.

[3]許遠(yuǎn)航，張鑫宇，樂燕芬.室內(nèi)多用戶在線協(xié)同指紋定位 算法[J].小型微型計(jì)算機(jī)系統(tǒng)，2024，45（3）：699-706.

[4]周軍，魏國亮，田昕，等.融合UWB和IMU數(shù)據(jù)的新型 室內(nèi)定位算法[J].小型微型計(jì)算機(jī)系統(tǒng)，2021，42（8）： 1741-1746.

[5]高銳，程良倫，胡莘.一種基于空間分割的無源RFID室 內(nèi)定位方法[J].計(jì)算機(jī)應(yīng)用研究，2012，29（1）： 184-186，210.

[6] BAHL P， PADMANABHAN V N. RADAR： an inbuildingRF-baseduserlocationand tracking system[C]//ProceedingsofNineteenth AnnualJoint Conference of the IEEE Computer and Communications Societies. Tel Aviv： IEEE， 2000： 775-784.

[7] LU X M， QIU Y， YUAN W L， et al. An improved dynamic prediction fingerprint localization algorithm based on KNN[C]//Proceedingsof2016SixthInternational Conference on Instrumentation amp; Measurement， Computer， Communication and Control （IMCCC）. Harbin： IEEE， 2016： 289-292.

[8] HU J S， LIU D W， YAN Z， et al. Experimental analysis on weight K-nearest neighborindoor fingerprint positioning[J]. IEEE Internet of Things Journal， 2019， 6（1）： 891-897.

[9]HSIEH C H， CHEN JY， NIEN B H. Deep learming-based indoor localization using received signal strength and channel state information[J]. IEEE Access，2019，7： 33256-33267.

[10] LE Y F， ZHANG H N， SHI W B， et al. Received signal strength based indoor positioning algorithm using advanced clustering and kernel ridge regression[J]. Frontiers of Information Technology amp; Electronic Engineering， 2021， 22（6）： 827-838.

[11] YOUSSEF M， AGRAWALA A. The Horus WLAN location determination system[C]/Proceedings of the 3rd International Conference on Mobile Systems， Applications， and Services. Seattle： ACM， 2005： 205-218.

[12] CHEN C， WANG Y J， ZHANG Y， et al. Indoor positioning algorithm based on nonlinear PLS integrated with RVM[J]. IEEE Sensors Journal， 2018，18（2）： 660-668.

[13] PETRIC M， NESKOVIC A， NESKOVIC N， et al. Indoor localization using multi-operator public land mobile networksandsupportvectormachinelearning algorithms[J]. Wireless Personal Communications， 2019， 104（4）： 1573-1597.

[14] HE S N， LIN W B， CHAN S H G. Indoor localization and automatic fingerprint update with altered AP signals[J]. IEEE Transactions on Mobile Computing，2017，16（7）： 1897-1910.

[15］樂燕芬，許遠(yuǎn)航，施偉斌.基于DPC 指紋子空間匹配的室 內(nèi)WiFi定位方法[J].儀器儀表學(xué)報(bào)，2021，42（11）： 106-114，

[16]田洪亮，錢志鴻，梁瀟，等.離散度WKNN位置指紋WiFi定位算法[J].哈爾濱工業(yè)大學(xué)學(xué)報(bào)，2017，49（5）： 94-99.

[17] FENG C， AU W S A， VALAEE S， et al. Received signal strength based indoor positioning using compressive sensing[J]. IEEE Transactions on Mobile Computing， 2012，11（12）： 1983-1993.

[18]KHALAJMEHRABADI A， GATSIS N， AKOPIAN D. Structured group sparsity： a novel indoor WLAN localization， outlier detection， and radio map interpolation scheme[J]. IEEE Transactions on Vehicular Technology， 2017，66（7）： 6498-6510.

[19]TOTH Z， TAMAS J. Miskolc IIS hybrid IPs： dataset for hybrid indoor positioning[C]//Proceedings of the 26th International Conference Radioelektronika. Kosice：IEEE， 2016： 408-412.

[20]張賀娜，樂燕芬，施偉斌.基于特征降維的核嶺回歸室內(nèi) 定位算法[J].儀器儀表學(xué)報(bào)，2020，41（10）：83-91，

（編輯：董偉）