基于有效AP 選擇和多分類LDA 的室內(nèi)定位算法

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

（吉林大學(xué)通信工程學(xué)院，吉林 長春 130012）

1 引言

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

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

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

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

2 WLAN 場景下多樓層室內(nèi)定位模型

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

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

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

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

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

3.1 基于穩(wěn)定性和差異性的離線AP 選擇算法

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

指紋簇內(nèi)每個AP 都對應(yīng)一組指紋數(shù)據(jù)集，簇內(nèi)第i個AP 的指紋數(shù)據(jù)集為Φapi，記為

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

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

為表征第i個AP 在第j個參考點(diǎn)上的穩(wěn)定性，設(shè)定一個RSS 閾值為rssthr，引入覆蓋因子

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

為表征第i個AP 在簇內(nèi)各個參考點(diǎn)的穩(wěn)定性，引入穩(wěn)定性因子

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

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

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

樣本集合Φapi的類內(nèi)離散度可以表示為

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

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

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

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

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

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

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

其中，nf表示第f個樓層內(nèi)的參考點(diǎn)數(shù)量，表示有效AP 集合內(nèi)第i個AP 在第f樓層內(nèi)第j個參考點(diǎn)上的RSS 值。

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

APk在所有樓層內(nèi)所有參考點(diǎn)的RSS 均值向量，即總樣本集合Bk的均值向量，表示為

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

根據(jù)多類別LDA 定義，F(xiàn)個類別的類間離散度矩陣表示為

F個類別的類內(nèi)離散度矩陣表示為

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

Η(W)的優(yōu)化過程可以轉(zhuǎn)化為

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

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

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

投影后第f個類的數(shù)據(jù)集各維度的方差為

其中，i=1,2,...,m_ap，的第i個元素，是矩陣內(nèi)第i列元素。APk內(nèi)各AP 在參考點(diǎn)上的RSS 互相獨(dú)立，所以第f個類的數(shù)據(jù)集的協(xié)方差為

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

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

由上述分析可得樓層識別指紋數(shù)據(jù)庫為

3.3 在線指紋的樓層判別

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

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

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

其中，p是在測試點(diǎn)記錄RSS 值的次數(shù)。

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

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

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

測試點(diǎn)上接收到的AP 的信號值越大，說明信號質(zhì)量越好。定義參數(shù)Eapi為

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

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

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

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

2) 在線樓層判別

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

4 算法性能分析

1) 計(jì)算復(fù)雜度分析

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

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

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

2) 穩(wěn)定性分析

本文算法是利用有效AP 集合進(jìn)行樓層判定，如果網(wǎng)絡(luò)中存在有效AP 不能正常工作，則在線階段，不能夠接收到該AP 的信息，但是，樓層判別階段，將該AP 的值設(shè)置為最小RSS 值的同時，仍然能夠選擇與離線有效AP 集合內(nèi)其余有效AP 相同的AP 集合進(jìn)行樓層判別?？梢娫撍惴▽P 故障具有一定的穩(wěn)健性。

5 仿真實(shí)驗(yàn)與分析

5.1 實(shí)驗(yàn)場景

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

表1 三棟建筑內(nèi)指紋數(shù)據(jù)的相關(guān)細(xì)節(jié)

利用指紋庫分區(qū)方法[14]對三棟建筑內(nèi)每一層的指紋數(shù)據(jù)庫進(jìn)行分區(qū)處理。其中，T2第三層指紋數(shù)據(jù)庫的分區(qū)示意如圖2 所示。

5.2 算法仿真分析

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

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

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

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

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

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

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

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

T0第二層指紋數(shù)據(jù)庫被分為7 個子指紋數(shù)據(jù)庫，根據(jù)有效AP 選擇算法得到相應(yīng)的有效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}在第一層的部分指紋數(shù)據(jù)如表3 所示，經(jīng)過投影后得到新的指紋數(shù)據(jù)如表4 所示。通過多分類LDA 算法處理后可得到4 個高斯分布概率密度函數(shù)，表5 給出了4 個高斯分布概率密度函數(shù)的均值和方差。

表3 有效AP 集合在第一層的部分RSS 指紋數(shù)據(jù)

表4 有效AP 集合在第一層的部分RSS 指紋數(shù)據(jù)經(jīng)過投影后的新數(shù)據(jù)

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

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

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

4) 不同算法比較

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

表6 EAP-LDA 算法主要仿真參數(shù)

表7 不同算法樓層識別準(zhǔn)確率比較

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

6 結(jié)束語

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