基于有效AP 選擇和多分類LDA 的室內定位算法

劉桂岐，錢志鴻，李華亮，孫佳妮，馮一諾，王雪

（吉林大學通信工程學院，吉林 長春 130012）

1 引言

近年來，隨著物聯網的發展，基于位置的服務（LBS,location based service）越來越多，推動了定位技術[1-2]的發展。全球定位系統（GPS,global positioning system）[3-4]可以滿足室外場景的定位需求，但在室內環境中，GPS 接收器和衛星之間不具備視線通信條件，無法準確識別室內位置。為實現室內定位，需要借助于射頻識別（RFID,radio frequency identification）、無線傳感器網絡（WSN,wireless sensor network）、超寬帶（UWB,ultra wide band）和無線局域網（WLAN,wireless local area network）等技術[5]。其中，WLAN 技術因具有覆蓋廣泛、接收信號強度（RSS，received signal strength）測量不需要外設硬件等技術優勢，更適于室內定位場景。所以，基于WLAN 的RSS 指紋室內定位技術受到國內外的廣泛關注。

基于RSS 指紋的WLAN 室內定位過程分為離線階段和在線階段[6]。離線階段記錄參考位置上接收到的多個接入點（AP,access point）的RSS 指紋，并建立指紋數據庫。在線階段利用定位算法檢索指紋數據庫，找到最匹配的指紋，并返回其對應的位置。在基于指紋的定位系統中，指紋庫內指紋數據的質量將直接影響定位效果。針對RSS 指紋庫優化的WLAN 室內定位算法，國內外學者做了大量的研究[7-8]，基于無線地圖更新、無線地圖降噪等室內定位算法取得了良好的定位效果。然而，上述研究大都針對單一平面內的定位，沒有考慮待定位人員或物品的縱向位置信息。在物聯網的大部分應用場景中，并不是所有縱向位置信息都有意義，有意義的縱向位置信息一般為人員所在樓層、物品所在貨架層等有效縱向位置信息。目前，在基于WLAN的指紋室內定位系統中，人員的樓層信息主要是以用戶主動參與的方式獲得，有效縱向位置信息獲取受到用戶主觀意愿的影響較大，在一定程度上降低了定位系統的智能性。消防、醫療、導盲等緊急呼叫與特殊需求的室內定位應用需要對目標終端進行高度精確的定位，如果用戶位置被估計到錯誤的樓層，會嚴重影響后續用戶的位置估計。因此，需要研究室內環境下精確的縱向位置信息判別算法。

近年來，室內定位中縱向位置信息判別問題研究主要從以下三方面開展：基于指紋分簇的算法[9]、基于移動設備內置傳感器的算法[10-11]、基于機器學習的算法[12-13]。Cramariuc 等[9]利用引入懲罰對數高斯距離的親和傳播聚類算法對指紋數據庫內的指紋聚類，通過在線指紋與各類指紋的相似度實現縱向信息判定，改善了多層建筑內指紋數據的聚類性能，但是，仍然會出現不同層的指紋數據被分到同一個簇內的情況。Radu 等[10]利用智能手機上加速度傳感器和壓力傳感器等提供的信息，提出了基于行人航跡推算和粒子濾波的縱向信息室內定位算法。周牧等[11]提出一種利用微機電系統傳感器與低功耗藍牙數據融合的室內跨樓層定位算法，利用氣壓計輸出數據和地理位置信息，對目標的縱向高度信息進行估計。基于移動設備中傳感器信息進行縱向信息判定的算法易受氣溫和環境等因素的影響，而且不同手機的傳感器測量值有所差異，無法像無線AP 那樣廣泛使用。Sun 等[12]利用線性判別分析（LDA,linear discriminant analysis）訓練每個AP 的指紋數據，得到基于Wi-Fi 指紋的縱向信息判別模型。在樓層數量較多或者部署AP 數量較多的場景下，將有較高的計算復雜度。Luo 等[13]設計了基于LDA 的多層識別模型MA_LDA，通過對樓層兩兩配對，然后對配對樓層內的AP 再進行兩兩配對，每組配對樓層構成一個分類器，并找到每組配對樓層最優的AP 配對組。但是，由于室內環境復雜，當室內空間較大時，一對最優AP 配對組并不能反映相鄰縱向層間指紋的區別。并且，當室內樓層數較多以及部署的AP 數量較多時，該算法需要構建的樓層判別分類器數量較多。

本文以基于RSS 指紋的多樓層室內定位系統為框架，以樓層信息作為有意義的縱向位置信息，針對多樓層室內定位問題，給出了WLAN 場景下多樓層室內定位模型，將室內定位問題分解為有效縱向位置信息和平面位置信息獲取兩部分。在平面信息位置獲取的研究成果基礎上，提出基于AP 選擇和LDA 融合的樓層識別算法。利用基于穩定性和差異性的AP 選擇算法，提取每個樓層中每個子指紋區域的有效AP 子集。利用多分類LDA 對每個有效AP 子集在不同樓層的指紋數據進行訓練，得到與有效AP 子集相對應的樓層判別模型，構建樓層判別指紋數據庫。在線階段，利用在線AP 選擇因子對在線指紋的AP 進行有效AP 提取，選擇與離線有效AP 子集相同的AP 子集，將對應的RSS信息輸入相應的縱向樓層判別模型，得到相應的樓層信息。

2 WLAN 場景下多樓層室內定位模型

針對WLAN 場景下多樓層室內定位問題，本文提出了一種基于RSS 指紋的WLAN 多樓層室內定位模型，將多樓層室內定位問題轉化為縱向樓層判別問題和平面指紋定位問題，如圖1 所示。多樓層室內定位包括2 個階段：離線階段和在線階段。離線階段主要負責指紋庫的構建，包括樓層識別指紋數據庫和位置估計指紋數據庫。在線階段主要負責在線指紋的樓層判別和在線指紋與單樓層指紋庫指紋的匹配。對于以單樓層指紋數據庫為單位進行存儲的多樓層指紋數據庫，樓層識別的目的是先找到在線指紋所屬的樓層號碼，得到單樓層指紋數據庫，然后得到進一步搜索的子指紋數據庫，可提高指紋匹配的效率和精度。確定樓層信息后，定位系統將在經過分區、降維、分層存儲處理的單層位置估計指紋數據庫內進行指紋匹配。

針對單樓層基于RSS 指紋的WLAN 室內定位問題，文獻[14]提出了基于指紋庫分區處理的單樓層室內定位算法。離線階段利用基于密度峰值的聚類算法對原始指紋庫進行分區處理，然后利用主成分分析（PCA,principal component analysis）算法對指紋庫進行降維處理，最后利用kd-tree 算法將分區的子指紋數據庫進行分層存儲。對于單個樓層的指紋數據集，最終以若干小指紋數據集的形式存儲。在線階段利用加權指紋相似性度量法確定在線指紋最相近的子指紋數據庫，并利用搜索算法BBF（best bin first）在子指紋數據庫內進行搜索，找到K個接近的指紋，并通過加權 K 近鄰（WKNN,weighted k-nearest neighbor）算法得到最終的位置。

本文在已有基于WLAN 的單樓層指紋定位算法研究的基礎上，進一步研究基于WLAN 多樓層室內定位問題中的縱向樓層判別問題。

3 基于AP 選擇和LDA 融合的樓層識別算法

首先，利用改進的基于密度的分簇算法對多層建筑的每個樓層進行指紋庫分區處理，每個樓層得到若干個小的子指紋數據庫（指紋簇），其中，單樓層指紋庫分區處理的具體步驟見文獻[14]。

3.1 基于穩定性和差異性的離線AP 選擇算法

由于在一個小監測區域內一般能接收到大致相同的AP 集合，因此基于指紋簇的有效AP 選擇更有意義。針對每個指紋簇內AP 的有效性主要有兩點考慮：1) AP 在指紋簇內同一參考點上的穩定性；2) AP 在指紋簇內不同參考點上的差異性。

指紋簇內每個AP 都對應一組指紋數據集，簇內第i個AP 的指紋數據集為Φapi，記為

其中，u是指紋簇內參考點的個數，p是在同一個參考點上記錄來自某個AP 的RSS 信息的次數。第i個AP 在簇內第j個參考點的RSS 數據集記為RSSj,api={rssj,api(1),rssj,api(2),…,rssj,api(p)}。

AP 在指紋簇內的穩定性表現如下，在指紋簇內同一個參考點上多次記錄的RSS 信息盡可能接近，同時，指紋簇內可以記錄穩定RSS 的參考點數量盡可能多，這樣能夠保證選擇的AP 在簇內每個參考點以及整個指紋簇內的穩定性。AP 在指紋簇內不同參考點的差異性主要表現如下，指紋簇內不同參考點上的RSS 信息差別盡可能大，這樣能夠保證所選擇的AP 能夠有效區分不同的參考點。

為表征第i個AP 在第j個參考點上的穩定性，設定一個RSS 閾值為rssthr，引入覆蓋因子

其中，表示第i個AP 在第j個參考點上的覆蓋因子，p表示在參考點j處記錄來自第i個AP 的RSS 值的次數，N p表示p次記錄中rssj,api≥rssthr的次數，α表示可選擇的AP 在p次RSS 記錄中滿足的次數百分比，。式(2)表示在第j個參考點上記錄p次來自第i個AP 的RSS信息，如果記錄的RSS 在大多數情況下都高于閾值rssthr，則認為第i個AP 在第j個參考點上是可靠的。

為表征第i個AP 在簇內各個參考點的穩定性，引入穩定性因子

其中，u表示指紋簇內所有參考點的數量，表示第i個AP 在參考點j的覆蓋因子；i表示第i個AP在簇內的穩定性因子，用來衡量第i個AP 的簇內穩定性，該值越大，表示第i個AP 在這個簇內越穩定，被選擇的機會就越大。

將指紋簇內第i個AP的指紋數據集Φapi作為總的樣本集合，第i個AP 在簇內第j個參考點上多次測量的指紋數據集RSSj,api被看作一個小的樣本集合，即總樣本集合的一個小類別。可見，總的樣本集合Φapi內包含u個類。對于第i個AP 的指紋數據集Φapi，第i個AP 在參考點j上的穩定性在RSS數據上的表現是第j個類的類內方差較小，第i個AP 在簇內不同參考點上的差異性在RSS 數據上的表現是總樣本內類間方差較大。為了進一步理解AP 的穩定性和差異性，引入樣本集合Φapi的類內散度和類間散度。

第j個類的方差可以表示為

樣本集合Φapi的類內離散度可以表示為

樣本集合Φapi的類間離散度可以表示為

為了量化每個AP 的性能指標，本文綜合考慮了AP 在指紋簇內參考點上的穩定性以及在不同參考點上的差異性，引入有效AP 的判別因子Q。第i個AP 的判別因子Qapi可以表示為

其中，是第i個AP 在指紋簇內各參考點上記錄的RSS 數據集的方差之和，反映了第i個AP 在簇內的穩定性，該值越小，表示AP 在簇內的RSS 信息越穩定；是第i個AP 在指紋簇內任意兩不同參考點上記錄的RSS 均值之差的平方和，反映了第i個AP 在簇內不同參考點的差異性，該值越大，說明該AP 在不同參考點上的判別能力越強；是指紋簇內滿足第i個AP 穩定性條件的參考點數量與指紋簇內總的參考點數量之比，從信號強度大小的角度反映了第i個AP 在指紋簇內的穩定性，該值越大，說明第i個AP 的RSS 信號在指紋簇內越穩定。如果AP 的判別因子越大，則表示該AP 在指紋簇內的RSS 信息越穩定，并且在指紋簇內不同參考點的RSS 信息差異性越大，越有可能被選擇成為有效AP。

如果指紋簇內能夠檢測到m個AP，可表示為{AP1,AP2,…,APm}。根據式(7)，m個AP 可以得到m個判別因子，表示為{Qap1,Qap2,…,Qapm}。對m個判別因子進行降序排列，選擇前m_ap 個具有最大判別因子的AP 作為該簇的有效AP 子集{AP1,AP2,…,APm_ap}。注意，這里的AP 序號只表示所在集合內的序號，并不表示整個指紋數據庫內的AP 序號。

針對一個多層的建筑物，需要求得每個樓層內每個指紋簇的有效AP 集合。如果一棟建筑物有F層，并且每層的指紋數據庫被分成ki個簇，i∈{1,2,…,F}，則可以得到（k1+k2+...+kF）個有效AP 集合。

3.2 基于有效AP 集合和多分類LDA 的樓層判別模型建立

LDA 是一種有監督的分類算法[15]，需要每個訓練數據樣本都提供類別標簽信息。基于LDA 二分類思想是將高維數據樣本投影到最佳鑒別矢量空間，以保證投影后的新樣本數據能夠滿足類內距離最小以及類間距離最大的條件，從而在該矢量空間分類原始數據。該算法在對樣本數據維度進行約減的同時，能夠保證樣本在投影后的矢量空間內具有最佳的可分離性。通過對類內散度和類間散度公式的變形，可以將LDA 的二分類思想推廣到多分類問題。本文利用LDA 對有效AP 集合在不同樓層的指紋數據集進行訓練，構建樓層判別模型以實現在線指紋的樓層判定。

其中，nf表示第f個樓層內的參考點數量，表示有效AP 集合內第i個AP 在第f樓層內第j個參考點上的RSS 值。

APk在第f層內所有參考點上RSS 的均值向量，即第f個樣本集合的均值向量，表示為

APk在所有樓層內所有參考點的RSS 均值向量，即總樣本集合Bk的均值向量，表示為

APk在第f層所有參考點上RSS 的協方差矩陣，即第f個樣本集合的協方差矩陣，表示為

根據多類別LDA 定義，F個類別的類間離散度矩陣表示為

F個類別的類內離散度矩陣表示為

LDA 應用于多分類情況下，即將多類別數據投影到低維空間，此時的低維空間將不是一條直線，而是一個超平面。假設低維空間的維度為d，對應的基向量設為(ω1,ω2,…,ωd)，基向量組成的矩陣為W。根據二分類LDA 優化目標求解算法，基于投影后類內方差最小，類間方差最大的原則得到多分類優化目標。由于W、WTS bW、WTSω W均為矩陣，無法直接用二分類LDA 的優化算法，所以需要用替代優化目標求W。這里利用的LDA 多分類優化目標函數為

Η(W)的優化過程可以轉化為

利用投影矩陣W投影后，第f類內的第j個樣本更新為

由于AP 集合在同一樓層不同參考點的指紋符合高斯分布模型，因此利用LDA 將樣本進行投影后，可以利用極大似然估計算法計算各個類別投影數據的均值和方差。

根據極大似然估計算法可知，投影后第f類的數據集的均值為

投影后第f個類的數據集各維度的方差為

其中，i=1,2,...,m_ap，的第i個元素，是矩陣內第i列元素。APk內各AP 在參考點上的RSS 互相獨立，所以第f個類的數據集的協方差為

根據極大似然估計算法，離線有效AP 集合APk的第f類數據集經投影矩陣W投影后得到的高斯分布概率密度函數為

為降低計算量，當在樓層的任何參考點都不能探測到有效AP 集合內的任何一個AP 時，認為該組有效AP 集合在該樓層內是無效AP 集合，即這個有效AP 集合在這個樓層內沒有指紋數據集，同時，有效AP 集合的類也不包含該樓層序號。當樓層上能夠探測到AP 的數量小于有效AP集合內AP 的數量時，其余沒有檢測到的AP 的RSS 被賦予最小的RSS 值，這里為?100 dBm。所以，對每一組有效AP 集合，將有g個類別的指紋數據，并產生g個高斯分布概率密度函數，其中g

由上述分析可得樓層識別指紋數據庫為

3.3 在線指紋的樓層判別

與離線階段類似，在線階段的移動設備也會接收到多個AP 的信號，需要選擇相對可靠的AP 用于樓層識別。

1) 基于AP 選擇因子的在線指紋數據處理

在線階段，在測試點處記錄來自m個AP的RSS值，記為

其中，p是在測試點記錄RSS 值的次數。

為了對在線指紋進行AP 選擇，本文同時考慮了位置點處接收到多次第i個AP 信號的方差和RSS 值的大小，這樣選擇的AP 具有信號值較穩定和數值相對較高的特點。

根據式(4)，測試點處接收到所有AP 信號的方差的集合，記為Γt={σap1,σap2,…,σapm}。

Redesign of a Ship Measurement Module……………WANG Jiehuan, QIU Yicen(2·45)

測試點上接收到的AP 的信號值越大，說明信號質量越好。定義參數Eapi為

其中，rssr,th為在線定位階段RSS 信號的閾值。當測試點第l次接收到來自第i個AP 的RSS 值大于閾值時，Eapi(l)=1；否則，Eapi(l)=0。

定義在線指紋的AP 選擇因子

其中，p是在測試點采集第i個AP 的RSS 值的總次數；ε0是極小值，避免分母為0。

在線指紋的所有AP 選擇因子的集合可以表示為Ω r={χap1,χap2,…,χapm}。對在線指紋所有AP 的選擇因子進行由大到小的排序，取前m′個AP 作為在線指紋rt的有效AP 集合。并且，將p次記錄的RSS求平均之后，得到在線指紋。

2) 在線樓層判別

首先，找到在線指紋的有效AP 集合中與離線的有效AP 集合相同的AP 集合，利用投影矩陣W將該有效集合的RSS 向量進行投影；然后將投影后的樣本特征分別代入與該有效AP 集合相對應類別的高斯分布概率密度函數，計算它屬于這個類別的概率，最大的概率對應的類別即預測樓層，樓層投票數加1。當在線指紋的AP 集合中不能找到完整的離線有效AP 集合時，先找到與有效AP 集合中AP元素重合最多的集合，然后沒有探測到的AP 的RSS值用最小RSS 值補齊。依次類推，直到找到3 個可以進行判別的AP 子集合。

4 算法性能分析

1) 計算復雜度分析

本文提出的基于AP選擇和多分類LDA的樓層判別算法主要包括2 個階段，即離線樓層判別模型建立和在線樓層判別階段。構建樓層識別模型的時間復雜度為O(kn1)+O(k)，其中，O(kn1)為有效AP選擇的復雜度，k為子指紋區域的數量，n1為子指紋區域內AP 的數量，O(k)為構建判別模型的復雜度，所提算法只需要構建與有效AP 集合數量同的樓層判別模型，即與子指紋庫的數量相同。在線階段，僅需要找到與離線有效AP 集合相同的集合進行判別，所以時間復雜度為O(1)。

Luo 等[13]提出的MA_LDA 算法需要兩兩樓層進行組合，構建樓層判別模型，并對兩兩樓層內的AP 兩兩組合得到最優判別AP 組合，算法復雜度O(n2)+O(f2)，其中，n為建筑物內AP 的數量，n>n1；f為樓層數。在線階段，需要找到與最優AP 配對相同的AP 集合進行判別，時間復雜度為O(1)。

盡管隨著樓層的增加，子指紋區域的數量k也會隨之增加，但是每一層分區的數量不會太大。當樓層較高，且AP 部署較多時，提出的基于AP 選擇和多分類的樓層判別算法在構建樓層判別模型時具有更低的時間復雜度，在線判別時與MA_LDA具相當的時間復雜度。但是，在大面積場景下，如果測試點不能接收到最優判別AP 組合的信息，在線指紋內將找不到最優判別AP 組合，MA_LDA 算法需要進行判別的AP 對的數量將增加。本文所提算法通過對指紋區域進行分區，移動設備在監測區域內不同地點總是能接收到有效AP 集合內的部分或全部AP 的信息。

2) 穩定性分析

本文算法是利用有效AP 集合進行樓層判定，如果網絡中存在有效AP 不能正常工作，則在線階段，不能夠接收到該AP 的信息，但是，樓層判別階段，將該AP 的值設置為最小RSS 值的同時，仍然能夠選擇與離線有效AP 集合內其余有效AP 相同的AP 集合進行樓層判別。可見該算法對AP 故障具有一定的穩健性。

5 仿真實驗與分析

5.1 實驗場景

利用文獻[16]給出的公共指紋數據庫進行仿真驗證，該指紋數據庫的采集地點是西班牙海梅一世大學的三棟樓。表1 給出了三棟建筑的相關細節，包括每棟建筑物的樓層數量F、訓練樣本的數量Nf、測試樣本的數量Nt以及每棟樓接入AP 的數量Nap。

表1 三棟建筑內指紋數據的相關細節

利用指紋庫分區方法[14]對三棟建筑內每一層的指紋數據庫進行分區處理。其中，T2第三層指紋數據庫的分區示意如圖2 所示。

5.2 算法仿真分析

1) rssthr和α對樓層判別的影響

在離線AP 選擇階段，引入信號強度閾值rssthr和參考點上信號強度大于閾值的概率α來求解參考點上的覆蓋因子，并得到每個AP 的判別因子，以確定候選AP 的選擇順序。所以，rssthr和α影響離線有效AP 子集的選取，從而影響樓層判別結果。為了驗證rssthr和α對樓層識別準確率的影響，通過改變閾值rssthr和α，觀察樓層識別準確率的變化情況。

令離線有效AP 選擇個數m_ap=5，在線AP 選擇個數m′=7，α=0.75，rssthr以?5 dBm 為間隔在[?100 dBm,70 dBm]內取值，分別得到建筑物T0～T2內每層樓測試指紋的樓層識別準確率，分別如圖3～圖5 所示，實線分別表示在設定不同rssthr時相應樓層測試指紋的樓層識別準確率，虛線表示所有樓層測試指紋的平均樓層識別準確率，黑色圓圈表示在不同rssthr下每個樓層測試指紋的最大樓層識別準確率。從圖3～圖5 中可以看出，在rssthr取相同值時，建筑物內每層的樓層識別準確率有較大差異，并且在相同rssthr情況下并不能保證每層測試指紋都獲得最大樓層識別準確率。所以，在離線AP 選擇階段，一個固定的閾值并不能得到較好的樓層識別效果。

通過大量的實驗分析發現，針對不同的參考點應用不同的rssthr將會產生更好的樓層識別效果。令閾值rssthr=median（rssap1,rssap2,…,rssapm），其中，（rssap1,rssap2,…,rssapm）表示參考點處接收到來自m個AP 的接收信號強度值，rssapm表示參考點處多次接收來自第m個 AP 的接收信號強度的均值，median（rssap1,rssap2,…,rssapm）表示取中值。當取變化的閾值時，給出每棟建筑物內各樓層測試指紋的樓層識別準確率和每棟建筑物內測試指紋的平均樓層識別準確率，如表2 所示。

表2 取變化rssthr時各樓層測試指紋的樓層識別準確率

令離線有效AP 選擇個數m_ap=5，在線AP 選擇個數m′=7，rssthr=median（rssap1,rssap2,…,rssapm），觀察α為0.5～0.9 時，每棟樓的平均樓層識別準確率，結果如圖6 所示。從圖6 中可以看出，隨著α值的增加，樓層識別準確率先增加后下降。其原因是，當α較小時，參考點處接收到某個AP 的信號強度不夠穩定，這樣的AP 被選入離線AP 子集將會降低樓層識別準確率；當α較大時，參考點處接收到某個AP 的信號強度較穩定，將有較少的AP滿足條件進入離線AP 子集，會忽略質量相對好的AP，從而使樓層識別準確率稍有降低。當α為0.7～0.8 時，樓層識別準確率在95%以上。

2) 離線有效AP 數量m_ap 對樓層判別的影響

當在線有效AP 數量取10 時，離線AP 選擇階段有效AP 的數量對樓層判別準確率的影響如圖7所示。從圖7 可以看出，當有效AP 數量較少時，樓層識別準確率相對較低。這是因為，在子指紋數據庫內選擇的有效AP 較少，將不能很好地反映該指紋數據庫的特征，即訓練樣本不足以獲得有效的分類。當有效AP 數量增加時，樓層識別準確率也隨之增加，當達到一定值時，繼續增加AP 的數量，樓層識別準確率略有下降，這是因為繼續增加會導致質量并不好的AP 被選擇，即過量冗余的、不穩定的樣本數據使分類效果降低。從圖7 可以看出，當簇內AP 數量達到5 左右時，樓層識別準確率可以達到98%。

T0第二層指紋數據庫被分為7 個子指紋數據庫，根據有效AP 選擇算法得到相應的有效AP 集合分別為{53,54,29,30,225}、{35,36,162,161,33}、{26,25,40,80,39}、{161,51,162,52,25}、{39,40,156,155,81}、{224,75,161,76,162}和{51,35,34,161,162}。第四個有效AP 集合{161,51,162,52,25}在第一層的部分指紋數據如表3 所示，經過投影后得到新的指紋數據如表4 所示。通過多分類LDA 算法處理后可得到4 個高斯分布概率密度函數，表5 給出了4 個高斯分布概率密度函數的均值和方差。

表3 有效AP 集合在第一層的部分RSS 指紋數據

表4 有效AP 集合在第一層的部分RSS 指紋數據經過投影后的新數據

表5 LDA 處理后有效AP 集合在4 個樓層的均值和方差

3) 在線有效AP 數量m′對樓層判別的影響

當離線有效AP 數量m_ap=5 時，在線有效AP數量m′對樓層識別準確率的影響如圖8 所示。如圖8所示，樓層識別準確率隨著m′的增加而增加，當m′達到一定值后，樓層識別準確率增加不明顯。當m′較小時，樓層識別準確率不高，主要是因為，當m′<5時，為了滿足樓層識別模型的輸入條件，需要利用最低RSS 信息補足5?m′個指紋信息，補足信息并不能真實反映指紋的位置特征，所以，會增加錯誤識別的概率。當m′≥5 時，樓層識別準確率隨著m′的增加先迅速增加，然后基本保持不變，但是，隨著m′的增加，需要判別的AP 組合數量將增加，為樓層識別帶來計算負擔，所以不宜選擇較大的m′。

4) 不同算法比較

為驗證提出算法的性能，選擇3 個算法進行比較。第一種對比算法是利用k-means 算法對每層的指紋數據庫進行分簇，然后將在線指紋距離最近的指紋簇的所屬樓層作為樓層判定結果。第二種對比算法[9]是利用改進的親和傳播聚類算法對所有的指紋數據進行聚類，引入懲罰對數高斯距離度量，利用在線指紋與各聚類指紋的相似程度來確定樓層，將這種算法稱為 PLGD。第三種對比算法是MA-LDA 算法[13]。本文提出的基于有效AP 選擇和多分類LDA 的樓層識別算法用EAP-LDA 代表，仿真參數如表6 所示。表7 給出了不同算法在不同指紋數據庫下的樓層識別準確率。從表7 中可以看出，與對比算法相比，所提EAP-LDA 算法具有相對高的樓層識別準確率。

表6 EAP-LDA 算法主要仿真參數

表7 不同算法樓層識別準確率比較

圖9 給出了不同對比算法的平均定位誤差累積分布函數，其中，離線有效AP 數量m_ap=5，在線有效AP 數量m'=8。在識別樓層后，對比算法的定位算法分別為k-means 算法和PLGD 算法，能夠在獲得樓層識別的同時，將在線指紋鎖定在識別樓層的一個小的指紋數據集內，然后利用KWNN 算法實現指紋的位置確定；MA-LDA 算法在識別樓層的指紋數據集內利用WKNN 算法求得在線指紋的位置；EAP-LDA 算法利用PCA 算法對在線指紋進行降維處理，找到所在樓層內的子指紋數據集，然后利用KWNN 算法實現指紋的位置確定。由圖12 可見，當定位誤差為2m 時，本文提出算法的CDF約為0.74，而k-means算法、PLGD、MA-LDA的CDF 分別為0.21、0.40、0.29。雖然與單樓層定位相比，多樓層定位算法的定位結果有一定惡化，但是相比其他對比算法，本文的室內定位算法由于樓層識別準確率高而有較好的定位效果。

6 結束語

針對多樓層室內定位問題，本文給出了基于WLAN 的多樓層室內定位模型，并提出了一種基于有效AP 選擇和多分類LDA 的樓層判別算法。利用離線AP 判別因子選擇有效AP 集合，并通過多分類LDA 算法對每個有效AP 集合在不同樓層的指紋數據進行訓練，得到樓層判別模型。在線定位階段，利用在線有效AP 選擇算法選擇在線的有效AP 信息，并選擇與離線有效AP 子集相同的集合進行樓層判別，最后利用基于指紋數據庫分區的平面定位算法實現最終位置的確定。實驗結果表明，所提樓層判別算法在多樓層室內定位場景下，能夠獲得較高的樓層判別準確率。本文提出的基于有效AP 選擇和多分類LDA 的樓層判別算法將基于RSS 指紋的多樓層室內定位系統作為框架，以樓層信息作為有用的縱向位置信息。下一步工作需要將本文提出的有效縱向位置信息判別算法用于多層WSN 部署或多層RFID 部署的指紋定位系統框架進一步驗證，以求得到一種在多層網絡部署場景下普適的有效縱向位置信息判別模型。