劉桂岐，錢(qián)志鴻，李華亮，孫佳妮，馮一諾，王雪

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

1 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

其中，u是指紋簇內(nèi)參考點(diǎn)的個(gè)數(shù)，p是在同一個(gè)參考點(diǎn)上記錄來(lái)自某個(gè)AP 的RSS 信息的次數(shù)。第i個(gè)AP 在簇內(nèi)第j個(gè)參考點(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)同一個(gè)參考點(diǎn)上多次記錄的RSS 信息盡可能接近，同時(shí)，指紋簇內(nèi)可以記錄穩(wěn)定RSS 的參考點(diǎn)數(shù)量盡可能多，這樣能夠保證選擇的AP 在簇內(nèi)每個(gè)參考點(diǎn)以及整個(gè)指紋簇內(nèi)的穩(wěn)定性。AP 在指紋簇內(nèi)不同參考點(diǎn)的差異性主要表現(xiàn)如下，指紋簇內(nèi)不同參考點(diǎn)上的RSS 信息差別盡可能大，這樣能夠保證所選擇的AP 能夠有效區(qū)分不同的參考點(diǎn)。

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

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

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

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

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

第j個(gè)類(lèi)的方差可以表示為

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.3 在線指紋的樓層判別

與離線階段類(lèi)似，在線階段的移動(dòng)設(shè)備也會(huì)接收到多個(gè)AP 的信號(hào)，需要選擇相對(duì)可靠的AP 用于樓層識(shí)別。

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

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

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

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

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

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

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

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

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

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

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

2) 在線樓層判別

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

4 算法性能分析

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

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

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

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

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

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

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

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

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

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

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

5.2 算法仿真分析

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

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

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

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

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

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

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

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

T0第二層指紋數(shù)據(jù)庫(kù)被分為7 個(gè)子指紋數(shù)據(jù)庫(kù)，根據(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}。第四個(gè)有效AP 集合{161,51,162,52,25}在第一層的部分指紋數(shù)據(jù)如表3 所示，經(jīng)過(guò)投影后得到新的指紋數(shù)據(jù)如表4 所示。通過(guò)多分類(lèi)LDA 算法處理后可得到4 個(gè)高斯分布概率密度函數(shù)，表5 給出了4 個(gè)高斯分布概率密度函數(shù)的均值和方差。

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

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

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

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

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

4) 不同算法比較

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

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

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

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

6 結(jié)束語(yǔ)

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