秦寧寧，張臣臣

(1.江南大學 輕工過程先進控制教育部重點實驗室，江蘇 無錫 214122；2.南京航空航天大學 電磁頻譜空間認知動態(tài)系統(tǒng)工信部重點實驗室，江蘇 南京 211106)

全球定位系統(tǒng)(GPS)的廣泛使用使室外定位有了一套成熟的解決方案[1]。但由于室內墻壁的阻擋，全球定位系統(tǒng)無法為用戶提供高精度的室內定位，使得室內定位技術成為了當前導航定位領域中的一個研究重點。在眾多的室內定位方法中，由于室內可探測到多個WiFi接入點(Access Point，AP)，且其信號易于測量，使得基于WiFi接收信號強度(Recevied Signal Strength，RSS)的指紋定位方法成為當下最流行的定位技術之一[2]。該方法通常分為離線和在線兩個階段：離線階段采集定位區(qū)域中參考點(Reference Point，RP)的接收信號強度作為指紋庫；在線階段獲取實時定位數據與指紋庫進行匹配，獲得估計位置[3]。

k近鄰查詢是最常見的指紋定位算法，但此算法需要待定位置與數據庫中的所有數據依次進行對比，計算耗時且需要較大的數據內存作為緩存。因此，為降低對數據庫容量的高要求，通常將離線的龐大指紋庫進行聚類預處理，待定位的在線數據經分類后，減少匹配量[4]?；诖怂枷耄墨I[5]中使用k均值算法對指紋進行聚類，但其定位精度受聚類數量影響較大；文獻[6]中提出的AAPC算法提高了WiFi指紋的聚類質量，定位精度相較k均值聚類有所提升，但其忽略了待定位點位于兩個聚類邊界時的誤判風險；文獻[7]中提出VAPFC聚類算法，以接入點為離散點生成泰森多邊形，多邊形區(qū)域形成自發(fā)的聚類空間，但此算法依賴已知接入點位置，普適性較低。

除了離線的聚類方法會對定位結果造成一定的影響外，接入點信號的可靠性也是影響定位精度的重要因素[8]。由于室內可檢測到的接入點數目日漸增多，由噪聲或冗余接入點信號帶來的干擾影響也隨之增大。正如文獻[9]中指出的那樣，室內環(huán)境中并非所有的接入點都有助于定位，某些以通信為目的而安裝的接入點信號不僅會增加計算的復雜度，還可能對定位精度帶來不利影響。為減少冗余接入點，文獻[10]提出基于最大值的接入點選擇策略；CHEN等[11]則根據信息熵的理論，提出一種infoGain的接入點選擇框架；ZHANG等[12]提出了分區(qū)費希爾準則模型，基于費希爾準則對接入點進行選擇。上述幾種方法雖然都被證明可以以較少的接入點來保證一定的定位精度，但所需的接入點數目卻依舊需要人為指定，仍存在接入點過少時誤差大，接入點過多時數據庫冗余的配置尷尬。

針對上述聚類方法以及接入點選擇對定位效率和精度的影響，筆者給出了一種低配移動終端適用的室內定位方法——基于模糊聚類的精簡接入點匹配定位算法(Simplified Access point matching location algorithm based on Fuzzy Clustering，SAFC)。該算法僅依賴單一信號源接入點的信號強度，在模糊聚類機制下，將定位區(qū)域切分為存在共性交叉的子區(qū)域，綜合考量信號穩(wěn)定性與可見性的雙效能力，減少每個區(qū)域中數據匹配時的工作量，建立區(qū)域最小接入點辨識集，最后以速度后驗的方式修正定位結果。

1 系統(tǒng)模型

不失一般性，假設定位區(qū)域Ω內，可探測到N個接入點信號PA1，PA2，…，PAi，…，PAN；部署M個指紋參考點RP1，RP2，…，RPi，…，RPM。如無特殊說明，文中的相關數據描述如下：

(2)Mj={μj1，μj2，…，μjN}，表示RPj處采集的N個接入點的接收信號強度測量均值集合，μjs表示在RPj處采集的PAs的信號均值。

(3)Sj={σj1，σj2，…，σjN}，表示RPj處采集的N個接入點的接收信號強度測量值Fj的標準差集合，σjs表示在RPj處采集的PAs的信號標準差。

(4)Ω(PAm)表示將參考點劃歸至以PAm為聚類標簽的子區(qū)域，簡記為Ωm。

2 離線階段

2.1 指紋模糊聚類

由于室內環(huán)境下相鄰參考點的最強接收信號極有可能來自相同的接入點，一種簡單的聚類思想便是基于最大信號均值的接入點進行聚類[13]。即對于參考點RPj而言，若其接收到PAi的信號均值最大，即有μji=max(Mj)，則RPj∈Ωi。此方法簡單，計算成本低，但并未考慮到均值不同的接入點信號分布可能高度重合的情況。尤其是在復雜的室內環(huán)境中，僅通過信號均值最大的接入點對參考點進行聚類，極有可能導致在線階段多個相似的高接入點信號強度下的分區(qū)誤判。

基于接入點最大均值聚類通常是以接入點的標號作為參考點聚類的唯一依據，缺乏對信號強度指示信息的考量。但筆者將參考點以最強接入點為分類標簽，通過推論高接入點信號間總體均值差異的顯著程度，提出一種基于T檢驗的模糊聚類方法。圖1給出兩種不同的聚類方法。相比于圖1(a)中的最大均值聚類，圖1(b)對高接入點信號間總體均值差異不顯著的參考點設立模糊類別Ωi&Ωj，最大程度地避免了將相鄰參考點聚為單一的Ωi或Ωj，可以有效地克服接入點信號波動造成的聚類結果過于武斷的不足。

2.1.1T檢驗相關描述

(1)

(2)

2.1.2 參考點聚類流程

使用T檢驗方法檢驗參考點處均值最大的接入點與其他接入點信號總體分布的均值差異是否顯著，獲取每個參考點的最強接入點集合，進而對整個定位環(huán)境進行區(qū)域劃分，是所提模糊聚類算法的核心思想。

基于T檢驗判別機制的模糊聚類思想，對RPj進行區(qū)域聚類的流程如下：

輸入：Mj，Sj，l，α；

輸出：Lj。

步驟1 Initialize：Lj=φ；∥φ表示空集

步驟2i=index(max(Mj))；∥index為獲取最大值索引的函數

步驟3Lj=Lj∪i； ∥紀錄i為RPj處最強接入點的標號

步驟4 Fors∈{1，2，…，N}，s≠i；

步驟8Lj=Lj∪s； ∥增補s進入Lj

步驟9 End If；

步驟10 End For； ∥遍歷N個接入點后，獲得RPj所屬類別標簽集合

步驟11 ReturnLj。

若|Lj|>1，則表明RPj處存在多個最強接入點，RPj應判定屬于多個區(qū)域。遍歷Ω中所有參考點，進而完成其區(qū)域歸屬的劃分。

2.2 最小接入點辨識集合的獲取

離線階段探測到的某些接入點信號不利于在線定位，有必要在聚類后的每個子區(qū)域中對于定位使用的接入點進行選取。為獲得辨識度最高的精簡接入點集合，給出了兩個能夠體現信號對定位判別影響的新指標，以解決噪聲接入點降低定位精度和冗余接入點增加計算成本的問題。

2.2.1 信號穩(wěn)定可見性預篩選

接入點信號的穩(wěn)定可見性主要體現為參考點處的接入點信號在時間上的穩(wěn)定性與在空間內的可見性。

(3)

(4)

(5)

(6)

(7)

2.2.2 快速相關性濾波算法去冗余

為獲得最小接入點辨識集合，采用快速相關性濾波(Fast Correlation-Based Filter，FCBF)算法對接入點進行過濾。FCBF算法是一種基于無關、弱相關且冗余、弱相關非冗余和強相關4類特征的特征選擇框架，其保證輸出的結果至少具備后兩種特征[16]。若將每個參考點視作為一個類，每個接入點視作為一個特征，則室內定位問題可轉化為分類問題，可將FCBF用于提取每個區(qū)域中接入點的最小辨識集合。

(1) 子區(qū)域內接入點相關性分析

(8)

其中，G(RP|PAi)表示PAi與Ωs內參考點的互信息增益；H(RP)表示當接入點值未知時在Ωs內參考點的信息熵；H(PAi)表示在Ωs內PAi的信息熵。

(2) 接入點間冗余性分析

(9)

其中，G(PAi|PAj)表示在Ωs中PAi和PAj的互信息增益。

2.3 離線指紋庫的建立

模糊聚類和最小接入點辨識集合的篩選過程，幫助每個參考點在離線構建指紋庫的過程中，直接面向有效和高辨識價值的精簡接入點集合采集數據，在降低數據保存成本的同時，也提高了數據的質量。每個參考點根據所屬子區(qū)域內的EAP獲得精簡后的接收信號強度均值向量，連同參考點坐標上傳至數據庫中存儲，形成離線指紋數據庫。

3 在線階段

3.1 基于接入點最大值的區(qū)域判定方法

3.2 待定位點位置的預估

在傳統(tǒng)指紋定位中，通常使用歐氏距離度量在線數據與離線指紋的相似度。但歐氏距離將接收信號強度向量各個維度之間的差值等同對待，并未考慮不同接入點信號所表示的距離可信程度的差異?？紤]到穩(wěn)定性較差的接入點信號攜帶的定位信息有限，故可通過對接入點賦權，利用區(qū)域內接入點的穩(wěn)定性對傳統(tǒng)歐氏距離度量進行修正。

若判定TP∈Ωv，則基于該區(qū)域內接入點的穩(wěn)定性，TP與Ωv內參考點RPj的信號距離dj被表征為

(10)

(11)

其中，wk為修正歐氏距離后第k個近鄰點權重值。wk的公式如下：

(12)

3.3 基于速度約束的定位結果驗證

由于接入點缺失或物理阻擋等因素導致的定位野值點，會嚴重影響定位系統(tǒng)的性能。當待定位用戶在室內移動時，短時段內速度變化不會太大，故可采用基于速度的加權滑動窗作為約束，對可能出現的定位野值進行篩選。

定義加權速度滑動窗Gm，記錄用戶在前m個時間段的平均速度，通過判斷定位前一時刻到當前定位時刻的行進速度是否在Gm速度閾值內，對定位結果進行驗證。

不失一般性，假設在tn時刻TP定位坐標為(xn，yn)，則在[tn-h，tn-h+1]時間內，用戶的平均速度為

(13)

令Δth=tn-tn-h，定義與當前定位時刻間距成反比的權重配置wh，以提高近定位點時刻用戶速度的定位價值：

(14)

得Gm速度

(15)

(16)

4 定位流程

筆者所提SAFC定位算法的流程如圖2所示。離線階段，SAFC采用模糊聚類機制，以接入點信號的總體均值差異和單次測量的波動程度為參考進行區(qū)域劃分，并在每個子區(qū)域中篩選定位辨識度最佳的接入點信源集合，有效地回避了不穩(wěn)定接入點造成的區(qū)域誤判及定位復雜度高的問題；在線階段，利用修正距離預估位置，結合速度后驗篩選定位野值，返回定位坐標或區(qū)域，使定位結果的可信度更高。

為保證算法的初始啟動，待定位用戶初次發(fā)出定位請求時，由于無前m個時間段的平均速度，不進行定位檢驗，直接向用戶輸出預估坐標；滑動窗Gm構建完成后，算法正式啟動。若發(fā)現定位野值，則只向待定位用戶輸出所在區(qū)域。此為定位精度與定位可靠性的折中處理，在大型商場等定位場景中可極大地提高用戶的定位體驗。

5 實驗場景與結果分析

5.1 測試場景與數據處理

為驗證SAFC定位算法的性能，在江南大學物聯(lián)網工程學院C區(qū)四樓進行數據測試。在60 m×42 m的室內環(huán)境中，沿走廊均勻設置368個參考點，相鄰參考點間隔1 m，每個參考點處采集50次指紋數據，采樣間隔為2.3 s。離線階段在整個定位區(qū)域共探測到105個位置未知的接入點，將其按照Mac地址從1至105編號，每個參考點處未探測到的接入點信號強度值用-100表示。離線階段的數據采集工作分4天完成，測試點數據在3天后采集，測試人員在走廊中間勻速行走兩周共采集到370個測試數據進行后續(xù)實驗。在數據采集時，測試環(huán)境中人員走動頻繁，所有數據均在Matlab 2018b中進行處理。

5.2 實驗結果與分析

5.2.1 T檢驗模糊聚類效果

按照節(jié)2.1.2中的聚類流程，在2 520 m2的實驗場景中，形成11個子區(qū)域。因文中所提聚類算法是以接入點的編號作為每個子區(qū)域的標簽的，故所形成的區(qū)域為Ω2、Ω4、Ω6、Ω10、Ω12、Ω14、Ω16、Ω32、Ω33、Ω35及Ω74，如圖3所示。由于SAFC考慮了每個參考點處高強度接入點信號總體分布的均值差異，所以會出現同一個參考點被判定屬于兩個區(qū)域的情況。但由于這些參考點的存在，使得處于兩區(qū)域交界處的待定位點，其接入點信號值無論怎樣波動使其被判定屬于哪個區(qū)域，都不會出現較大的誤差。此外，聚類的結果也說明，該聚類方法只有有限幾個參考點會被聚類至多個類別，因此增加的工作量是可控的。

在圖3中RP1、RP2和RP3處各采集300次接收信號強度進行分析，每個參考點處均值最強的兩個接入點信號重疊情況如圖4所示。RP1和RP2最強接入點的接收信號強度測量均值差異不明顯，依據T檢驗模糊聚類將這兩個參考點同時劃分到Ω6和Ω35。在RP3處兩個接入點信號的測量值雖有少許重合，但其數據總體均值差異顯著，且單次采樣時PA6的信號強度均為最大值，故只判定RP3∈Ω6，這也進一步證明了所提聚類算法的合理性。

5.2.2 實驗參數選擇

為使定位系統(tǒng)的性能達到最佳，對節(jié)3.2中的參數Ps和閾值γ進行測試尋優(yōu)。在K=3時，把每個子區(qū)域中P∈{3，4，…，25}與γ∈{0，0.01，0.02，…，0.3}的所有取值組合。在每個子區(qū)域的離線數據中隨機選擇10%作為測試數據，其余為訓練數據，重復10次試驗取定位誤差ρ的平均值。選擇每個子區(qū)域中最小定位誤差的組合作為該區(qū)域的最優(yōu)參數，進而得到每個區(qū)域中的EAP。

限于篇幅，表1給出其中幾個子區(qū)域的最優(yōu)參數。

表1 代表性子區(qū)域內最優(yōu)參數

5.2.3 接入點精簡效果分析

為驗證筆者所提接入點選擇策略的有效性，將EAP與MaxMean[7]、infoGain[8]、Fisher[9]3種接入點選擇方法以及全接入點參與定位的貪婪方式進行對比實驗。由于在整個測試場景中，|EAP|∈[3，15]，故3種接入點選擇算法以3為最小值，15為最大值，在每個區(qū)域中尋找最佳接入點數量并提取相關接入點信息后進行比較運算。

定位誤差分析如圖6所示。筆者提出的在每個子區(qū)域中選取EAP的方式，在同等的誤差范圍內，均優(yōu)于所有接入點均參與定位的定位結果。說明在噪聲環(huán)境下，并不是所有的接入點信號均有利于定位。由于接入點信號的不穩(wěn)定甚至某些接入點信號的缺失，離線階段探測到的不良接入點特征參與定位運算將會加大誤差。同時，由于MaxMean方法只選用子區(qū)域中均值較大的接入點信號，忽略了均值低但穩(wěn)定的接入點信息，定位效果最差，平均定位誤差達到了1.270 m；infoGain和Fisher未考慮接入點信號的穩(wěn)定可見性，選用了某些在線階段未探測到的接入點，定位精度提升有限，均值誤差分別為1.140 m和1.182 m。而EAP在每個子區(qū)域中考慮接入點信號的穩(wěn)定可見性，并去除了無關及冗余接入點，整體定位性能最優(yōu)，平均誤差僅為0.995 m，較MaxMean、infoGain、Fisher算法分別提升了21.7%、12.3%和15.8%。

5.2.4 接入點穩(wěn)定性修正效果分析

如節(jié)3.2所述，針對傳統(tǒng)歐氏距離只考慮在線數據與離線指紋整體相似度的局限性，提出利用接入點穩(wěn)定性對歐氏距離進行修正，減少不穩(wěn)定接入點信號所占的距離權重。為比較其對定位精度的影響，與無穩(wěn)定性修正的定位結果進行了對比實驗，結果如表2所示。

表2 接入點修正歐氏距離對定位誤差的影響分析

可見，采用穩(wěn)定性修正的整體定位效果最好，平均誤差為0.977 m，較傳統(tǒng)歐氏距離的0.995 m提高了約1.8%；同時，1 m之內的定位誤差占比最高，說明利用區(qū)域中接入點穩(wěn)定性修正度量的方法的確有利于提高定位的精度。在后續(xù)實驗中，SAFC將采用接入點穩(wěn)定性修正距離的方式進行對比運算。

5.2.5 速度約束效果分析

為使定位結果可信度更高，筆者提出基于速度約束篩選定位野值。其中浮動參數δ的取值越小，約束能力越強，但會造成較多待定位點無法給出確切位置，使得用戶體驗較差。結合定位性能與實驗場景的整體需求，在當前場景環(huán)境中設定δ=1.5，m=5，此時基于速度約束剔除13個野值點。表3給出了δ=1.5時定位驗證對定位誤差的分析，證明了SAFC基于用戶的移動速度對定位結果進行驗證的可行性。

表3 定位驗證對定位估計誤差的影響(δ=1.5)

5.2.6 整體定位結果

為驗證SAFC的整體性能，分別與DDWKNN[5]、AAS算法[18]以及傳統(tǒng)的WKNN算法進行對比運算。實驗中，所有算法的K=3，DDWKNN根據空間特征將聚類數目選為6。為保證測試數據的一致性，在SAFC中取δ=5，此時無定位野值從數據中濾除。

從圖7可知，在對測試點估計位置時，在同等的誤差范圍內，SAFC均優(yōu)于其他定位算法，其估計誤差在1 m之內的數據占比達到了63.2%，而其他算法均不足55%。表4給出了4種定位算法的位置估計誤差值，SAFC在誤差平均值、最大值及方差值方面均優(yōu)于其他定位方法。在整個定位環(huán)境中，其平均誤差保持在1 m以內，達到了0.977 m，相比于WKNN，定位精度提升了約15.9%。這說明SAFC在復雜的室內環(huán)境中對定位結果的提升是全方面的。

6 結束語

針對復雜的室內定位環(huán)境，傳統(tǒng)的聚類方法難以劃分物理空間，且室內接入點數目繁多從而影響定位性能的問題，筆者提出了一種新的室內定位算法。該算法通過分析接入點信號總體的均值特征判定參考點所屬區(qū)域，經雙重篩選獲取每個子區(qū)域中接入點的最佳辨識集，最后通過修正距離及速度后驗的方式反饋定位位置，力求給用戶最可信的定位結果。實驗證明，所提算法在提高定位精度的同時，大大地減少了數據庫中所需存儲的數據量，在室內環(huán)境下具有較高的實用價值。