周 牧 唐云霞 田增山 衛(wèi)亞聰

?

基于流形插值數(shù)據(jù)庫構(gòu)建的WLAN室內(nèi)定位算法

周 牧①②唐云霞*①田增山①衛(wèi)亞聰①

①(重慶郵電大學(xué)移動通信技術(shù)重慶市重點實驗室 重慶 400065)②(天津師范大學(xué)天津市無線移動通信與無線電能傳輸重點實驗室 天津 300387)

針對傳統(tǒng)無線局域網(wǎng)(WLAN)室內(nèi)定位系統(tǒng)中因參考點密集分布及逐點信號采集所帶來的位置指紋數(shù)據(jù)庫構(gòu)建工作量繁重的問題，該文提出一種基于混合半監(jiān)督流形學(xué)習(xí)和3次樣條插值的數(shù)據(jù)庫構(gòu)建方法。該方法利用少量標(biāo)記數(shù)據(jù)和大量未標(biāo)記數(shù)據(jù)求解定位目標(biāo)函數(shù)的最優(yōu)解，同時根據(jù)高維信號強度空間與低維物理位置空間的映射關(guān)系，實現(xiàn)對未標(biāo)記數(shù)據(jù)的位置標(biāo)定。大量實驗結(jié)果表明，該方法能夠在保證較高定位精度的同時，顯著降低位置指紋數(shù)據(jù)庫的構(gòu)建開銷。

無線局域網(wǎng)；位置指紋；半監(jiān)督學(xué)習(xí)；流形對齊；3次樣條插值

1 引言

隨著移動設(shè)備的便攜化發(fā)展，人們對于室內(nèi)基于位置信息的服務(wù)需求與日俱增[1]。全球定位系統(tǒng)(Global Positioning System, GPS)和蜂窩定位系統(tǒng)雖然在室外環(huán)境中能達(dá)到較高的定位精度，但在室內(nèi)環(huán)境中信號容易受到建筑物或設(shè)施的遮擋，使得上述定位系統(tǒng)無法提供精確的位置服務(wù)。與此同時，由于無線局域網(wǎng)(Wireless Local Area Network, WLAN)具有易安裝、易擴展、保密性和抗干擾能力強等優(yōu)點，基于WLAN接收信號強度(Received Signal Strength, RSS)的位置指紋定位方法備受關(guān)注[2,3]，該方法與基于信號到達(dá)時間(Time Of Arrival, TOA)[4]和到達(dá)角度(Angle Of Arrival, AOA)[5]的WLAN定位方法相比，前者僅利用現(xiàn)有WLAN網(wǎng)絡(luò)且無需硬件設(shè)備的升級改造，同時具有較高的定位精度，從而可以有效滿足人們在復(fù)雜室內(nèi)環(huán)境中的定位需求。

位置指紋定位是一種基于模式分類的定位方法，其利用RSS樣本與位置坐標(biāo)的映射關(guān)系來實現(xiàn)用戶的位置估計。該方法通常分為兩個階段：離線階段和在線階段。在離線階段，需在目標(biāo)區(qū)域內(nèi)標(biāo)記若干參考點(Reference Point, RP)，并在每個參考點處采集來自多個接入點(Access Point, AP)的RSS樣本(即位置指紋)，建立目標(biāo)區(qū)域所對應(yīng)的指紋數(shù)據(jù)庫。考慮室內(nèi)無線信號的波動性，在每個參考點處需采集多個RSS樣本以刻畫參考點的信號統(tǒng)計特性。在在線階段，利用相應(yīng)的信號空間搜索匹配算法，將用戶新采集的RSS樣本與預(yù)先存儲的指紋數(shù)據(jù)庫進行匹配，選擇若干鄰近參考點來實現(xiàn)對用戶的位置估計。

由此可見，傳統(tǒng)位置指紋定位需在離線階段采集每個參考點處的RSS樣本，從而得到大量具有位置標(biāo)定的數(shù)據(jù)(即標(biāo)記數(shù)據(jù))，該過程的人力及時間開銷隨著目標(biāo)區(qū)域的增大而顯著增加。為了解決這一問題，文獻[6-8]利用易于采集的大量未標(biāo)記RSS數(shù)據(jù)與少量RSS標(biāo)記數(shù)據(jù)來構(gòu)建指紋數(shù)據(jù)庫，以降低離線階段的工作量。但是，這類方法未考慮室內(nèi)無線信號的波動性問題，即一旦出現(xiàn)因多徑效應(yīng)等因素所造成的RSS樣本劇烈畸變，則無法實現(xiàn)有效的位置指紋匹配，從而造成定位精度的嚴(yán)重惡化。

針對上述問題，本文提出基于混合半監(jiān)督流形學(xué)習(xí)和3次樣條插值的數(shù)據(jù)庫構(gòu)建方法，其利用大量未標(biāo)記物理位置的用戶路徑數(shù)據(jù)，并結(jié)合用戶路徑的RSS樣本時間戳及標(biāo)記數(shù)據(jù)的物理位置鄰近信息來增強高維空間鄰近RSS數(shù)據(jù)的相關(guān)性，從而保證較高的定位精度。此外，采用施行特征函數(shù)來估計能夠有效刻畫每個參考點處信號統(tǒng)計特征所需的最少標(biāo)記RSS樣本個數(shù)(即樣本容量)，以降低指紋數(shù)據(jù)庫的構(gòu)建開銷。

2 數(shù)據(jù)庫構(gòu)建

2.1 算法流程

圖1給出了本文所提混合半監(jiān)督流形學(xué)習(xí)和3次樣條插值的數(shù)據(jù)庫的構(gòu)建過程。首先，利用假設(shè)檢驗方法估計每個參考點處所需采集的RSS樣本容量，并通過隨機采集大量未標(biāo)記物理位置的用戶路徑數(shù)據(jù)，構(gòu)建相應(yīng)的稀疏指紋數(shù)據(jù)庫。其次，采用3次樣條插值方法擴充稀疏指紋數(shù)據(jù)庫，并基于流形學(xué)習(xí)算法將未標(biāo)記數(shù)據(jù)與指紋數(shù)據(jù)進行信息融合，實現(xiàn)對未標(biāo)記數(shù)據(jù)的物理位置標(biāo)定，進而完成對指紋數(shù)據(jù)庫的拓展；最后，利用K近鄰(K-Nearest Neighbor, KNN)算法，實現(xiàn)對用戶的位置估計。

2.2 樣本容量

由于室內(nèi)無線信號的波動性，傳統(tǒng)指紋定位需在每個參考點處采集大量RSS樣本，并計算其統(tǒng)計量(如均值)作為該參考點的位置指紋，從而指紋數(shù)據(jù)庫的構(gòu)建需要耗費大量的人力和時間開銷。針對這一問題，本文提出采用假設(shè)檢驗方法來估計能夠有效刻畫每個參考點處信號統(tǒng)計特征所需的最少RSS樣本容量，以降低指紋數(shù)據(jù)庫的構(gòu)建開銷。

圖1 本文所提混合數(shù)據(jù)庫構(gòu)建過程

假設(shè)每個參考點處RSS樣本的理想均值、總體均值和樣本均值[9]分別為,和，則根據(jù)法則，得到RSS樣本均值誤差的接受范圍為。為了降低第1類錯誤的影響，本文通過設(shè)定顯著性水平()，使得犯此類錯誤的概率不超過。由于犯第2類錯誤的概率依賴于RSS樣本容量，所以本文利用施行特征函數(shù)來確定樣本容量，使得犯第2類錯誤的概率不超過。由文獻[10]可知，?；诖?，本文雙邊假設(shè)檢驗問題定義為

2.3樣本插值

插值方法在定位領(lǐng)域經(jīng)常被用來提高定位精度[12]，圖2為不同插值方法(3次樣條插值(CUBIC)、線性插值(Linear)、徑向基插值(RBF))與無插值(KNN)時的性能對比。從圖2可知，3次樣條插值的定位性能與穩(wěn)定性都優(yōu)于其他插值方法，故本文利用3次樣條插值方法對未標(biāo)記參考點處的RSS均值進行插值。具體方法如下：首先，令目標(biāo)區(qū)域內(nèi)的參考點、標(biāo)記參考點和未標(biāo)記參考點的位置集分別為,和，其中，；其次，對于第個未標(biāo)記參考點處來自第個接入點的RSS均值，通過計算距離找到其所對應(yīng)的個近鄰標(biāo)記參考點及其對應(yīng)的來自第個接入點的RSS均值；最后，利用個近鄰標(biāo)記參考點估計RSS均值。

圖2 不同插值方法的定位性能比較

(4)

3 數(shù)據(jù)庫拓展

3.1 拉普拉斯特征映射

本文利用拉普拉斯特征映射(LaplacianEigenmap, LE)[13]算法，對高維信號樣本進行位置標(biāo)定。該算法保證在高維信號空間中距離鄰近的樣本映射到低維空間中也鄰近[14]。對應(yīng)于WLAN室內(nèi)定位系統(tǒng)，若接收到的高維RSS樣本相似，則所對應(yīng)的目標(biāo)用戶位置在低維空間中鄰近。算法將數(shù)據(jù)分為兩類：標(biāo)記數(shù)據(jù)和未標(biāo)記數(shù)據(jù)。兩類數(shù)據(jù)的主要區(qū)別是：前者為每個參考點處真實采集或插值估計得到的數(shù)據(jù)，其包含位置信息；而后者為未標(biāo)記物理位置的用戶路徑數(shù)據(jù)，其僅含有RSS和時間戳信息。

(6)

(8)

3.2 高維數(shù)據(jù)標(biāo)定

為了求解上述最小化問題且保持高維空間中鄰近RSS數(shù)據(jù)的相關(guān)性，權(quán)值矩陣和拉普拉斯矩陣的計算過程如下：假設(shè)目標(biāo)區(qū)域內(nèi)存在個接入點，分別對高維RSS樣本、路徑的未標(biāo)記數(shù)據(jù)時間戳和標(biāo)記數(shù)據(jù)位置建立鄰接矩陣,和，其所包含的第行列元素分別為

(12)

3.3核參數(shù)校準(zhǔn)

(16)

4 實驗測試及性能分析

4.1實驗環(huán)境

實驗環(huán)境如圖3所示，65.0 m×18.5 m典型WLAN室內(nèi)環(huán)境，其包括走廊和大廳的4個子區(qū)域。環(huán)境中布置5個接入點，選用三星S7568手機和自主開發(fā)的WLAN信號采集軟件采集RSS樣本(采樣頻率1 Hz)。環(huán)境中均勻標(biāo)記327個參考點且在每個參考點處采集20個RSS樣本(即樣本容量20)，同時隨機選擇10條未標(biāo)記位置信息的用戶路徑并采集1210個未標(biāo)記RSS樣本。

4.2參數(shù)比較

4.2.1樣本容量 圖4給出了在不同樣本容量條件下利用皮爾遜相關(guān)系數(shù)[18]得到的子區(qū)域3中每個參考點處采集來自不同接入點的RSS值的信號相似度。以所有參考點接收到AP3的RSS值為例，樣本容量10和100所對應(yīng)的信號熱度圖相似度僅為75.82%，而樣本容量20和100所對應(yīng)的信號熱度圖相似度可提高到91.93%。從而，驗證了本文所選樣本容量20能夠有效刻畫每個參考點處采集信號的變化特征。

圖5比較了在不同樣本容量條件下的定位誤差?？梢姡?dāng)樣本容量增加時定位誤差降低，此外，當(dāng)樣本容量大于20時定位誤差變化不明顯。

圖3 實驗環(huán)境平面圖

圖4 子區(qū)域3的皮爾遜相關(guān)系數(shù)

圖5 不同樣本容量條件下的定位誤差

4.2.3時間戳 由于同一RSS序列所包含的時間戳信息能夠有效刻畫權(quán)重矩陣中不同RSS樣本之間的鄰近關(guān)系，圖7比較了考慮和不考慮時間戳信息的混合位置指紋數(shù)據(jù)庫所對應(yīng)的定位誤差?？梢姡罢咚鶎?yīng)定位誤差在3 m內(nèi)的置信概率為74.35%，其高于后者近10%。

4.3定位性能

圖8比較了不同數(shù)據(jù)庫所對應(yīng)的定位誤差，圖9比較了分別利用傳統(tǒng)數(shù)據(jù)庫[2]、流形數(shù)據(jù)庫[6]和本文數(shù)據(jù)庫所得到的測試點估計位置和真實位置，其中，對應(yīng)位置間用線段連接?？梢姡疚臄?shù)據(jù)庫在降低整體定位誤差的同時，還可有效剔除大誤差點(即減小拖尾誤差概率)。圖10給出了不同標(biāo)記RSS樣本數(shù)條件下的平均定位誤差?？梢姡?dāng)標(biāo)記RSS樣本數(shù)較多時，3種數(shù)據(jù)庫所對應(yīng)的定位誤差相近，而當(dāng)標(biāo)記RSS樣本數(shù)較少時，3種數(shù)據(jù)庫所對應(yīng)的定位誤差均呈上升趨勢，且傳統(tǒng)數(shù)據(jù)庫的性能最為惡化。由此可知，本文數(shù)據(jù)庫具有最優(yōu)的定位性能，且在標(biāo)記RSS樣本數(shù)較少的情況下具有較好的穩(wěn)定性。

4.4 數(shù)據(jù)庫構(gòu)建開銷

圖11比較了不同參考點數(shù)條件下數(shù)據(jù)庫構(gòu)建所需的時間開銷?？梢?，當(dāng)參考點個數(shù)為327時，構(gòu)建流形和本文數(shù)據(jù)庫所需的時間開銷僅為傳統(tǒng)數(shù)據(jù)庫的10%左右。此外，由于構(gòu)建傳統(tǒng)數(shù)據(jù)庫需要在每個參考點處采集400個RSS樣本且采樣頻率為1 Hz，于是RSS采集時間為。然而，流形和混合數(shù)據(jù)庫的構(gòu)建僅需在每個參考點處采集20個RSS樣本，同時隨機采集10條用戶路徑以得到1210個未標(biāo)記RSS樣本，所需時間開銷為，其相對于傳統(tǒng)數(shù)據(jù)庫的構(gòu)建減少約34.1 h的RSS采集時間。綜上所述，本文數(shù)據(jù)庫能夠在保證較高定位精度的同時，顯著降低位置指紋數(shù)據(jù)庫的構(gòu)建開銷。

圖6 不同和值條件下的核校準(zhǔn)結(jié)果

圖7 時間戳信息對定位誤差的影響

圖8 不同數(shù)據(jù)庫所對應(yīng)的定位誤差

圖9 不同數(shù)據(jù)庫所對應(yīng)的測試點估計位置

圖10 不同標(biāo)記RSS樣本數(shù)條件下的平均定位誤差

圖11 不同參考點數(shù)條件下的數(shù)據(jù)庫構(gòu)建開銷

5 結(jié)束語

本文所提基于混合半監(jiān)督流形學(xué)習(xí)和3次樣條插值的指紋庫構(gòu)建方法相比于傳統(tǒng)方法的改進內(nèi)容如下：首先，利用假設(shè)檢驗方法對每個參考點處需要采集的RSS樣本容量進行優(yōu)化，以降低標(biāo)記數(shù)據(jù)的采集開銷；其次，結(jié)合未標(biāo)記位置信息的用戶路徑數(shù)據(jù)，采用流形學(xué)習(xí)方法拓展位置指紋數(shù)據(jù)庫以提高系統(tǒng)的定位性能；最后，通過考慮用戶路徑數(shù)據(jù)中所包含的時間戳信息，進一步提高數(shù)據(jù)庫的定位精度和穩(wěn)定性。實驗結(jié)果表明，本文所提數(shù)據(jù)庫構(gòu)建方法無需改變現(xiàn)有WLAN網(wǎng)絡(luò)硬件設(shè)施，且能夠在保證較高定位精度的同時，顯著降低離線階段數(shù)據(jù)庫的構(gòu)建開銷。

[1] KASHIF A, TAYYAB J, HOSSAM S H,. Non-audible acoustic communication and its application in indoor location-based services[C]. IEEE Wireless Communications and Networking Conference, Doha, Qatar, 2016: 1-6.

[2] 周牧, 蒲巧林, 田增山. 室內(nèi)WLAN定位中位置指紋優(yōu)化的接入點部署方法[J]. 通信學(xué)報, 2015, 36(Z1): 30-41. doi: 10.11959/j.issn.1000-436x.2015279.

ZHOU Mu, PU Qiaolin, and TIAN Zengshan. Location fingerprint optimization based access point deployment in indoor WLAN localization[J]., 2015, 36(Z1): 30-41. doi: 10.11959/j.issn.1000-436x.2015279.

[3] 陳兵, 楊小玲. 一種基于概率密度的WLAN接入點定位的算法[J]. 電子與信息學(xué)報, 2015, 37(4): 855-862. doi: 10.11999/ JEIT140661.

CHEN Bing and YANG Xiaoling. A WLAN access point localization algorithm based on probability density[J].&, 2015, 37(4): 855-862. doi: 10.11999/JEIT140661.

[4] HE Jie, LI Shen, PAHLAVAN Kaveh,. A realtime testbed for performance evaluation of indoor TOA location system[C]. IEEE International Conference on Communications, Ottawa, Canada, 2012: 482-486.

[5] TAPONECCO L, AMICO A D, and MENGALI U. Joint TOA and AOA estimation for UWB localization applications [J]., 2011, 10(7): 2207-2217. doi: 10.1109/TWC.2011.042211.100966.

[6] ZHANG Liye, MA Lin, and XU Yubin. A semi-supervised indoor localization method based on l1-graph algorithm[J].(), 2015, 22(4): 55-61.

[7] OUYANG R, WONG A, LEA C,. Indoor location estimation with reduced calibration exploiting unlabeled data via hybrid generative/discriminative learning[J]., 2011, 11(11): 1613-1626. doi: 10.1109/TMC.2011.193.

[8] PAN J J, PAN S J, YIN J,.Tracking mobile users in wireless networks via semi-supervised colocalization[J]., 2012, 34(3): 587-600. doi: 10.1109/TPAMI.2011.165.

[9] 勵晶晶, 郭文. 兩類錯誤條件下的樣本容量選擇[J]. 統(tǒng)計與決策, 2010, (15): 14-18.

LI Jingjing and GUO Wen. Select the sample size under two types of error conditions[J]., 2010, (15): 14-18.

[10] 賈俊平. 統(tǒng)計學(xué)[M]. 北京. 中國人民大學(xué)出版社. 2011: 220-224.

JIA Junping. Statistics[M]. Beijing, China Renmin University Press, 2011: 220-224.

[11] 彭小輝, 晏政, 李艷軍, 等. 一種基于解析冗余關(guān)系的半定性故障隔離方法在航天器推進系統(tǒng)中的應(yīng)用[J]. 國防科技大學(xué)學(xué)報. 2012, 34(6): 104-110. doi: 10.3969/j.issn.1001-2486. 2012.06.018.

PENG Xiaohui, YAN Zheng, LI Yanjun,. A semi- qualitative fault isolation method based on analytical redundancy relations for spacecraft propulsion system[J]., 2012, 34(6): 104-110. doi: 10.3969/j.issn.1001-2486.2012.06.018.

[12] 陳家琪, 嚴(yán)梓乘. 一種Newton插值的RFID室內(nèi)定位改進算法[J]. 計算機系統(tǒng)應(yīng)用, 2012, (1): 45-48. doi: 10.3969/j.issn. 1003-3254.2012.01.010.

CHEN Jiaqi and YAN Zicheng. Improvement algorithm of Newton interpolation for RFID indoor positioning[J].&, 2012, (1): 45-48. doi: 10. 3969/j.issn.1003-3254.2012.01.010.

[13] BELKIN M and NIYOGI P. Laplacian eigenmaps for dimensionality reduction and data representation[J]., 2003, 15(6): 1373-1396. doi: 10.1162/ 089976603321780317.

[14] SHI Lei, ZHANG Lefei, ZHAO Lingli,. Adaptive Laplacian eigenmap-based dimension reduction for ocean target discrimination[J]., 2016, 13(7): 902-906. doi: 10.1109/LGRS. 2016.2553046.

[15] ZHANG Yanming, HUANG Kaizhu, HOU Xinwen,. Learning locality preserving graph from data[J]., 2014, 44(11): 2088-2098.doi: 10.1109/TCYB.2014.2300489.

[16] 曾孝平, 劉刈, 劉國金. 基于圖譜理論和隨機游走核的圖像去噪[J]. 通信學(xué)報. 2010, 31(7): 116-121. doi: 10.3969/j.issn. 1000-436X.2010.07.017.

ZENG Xiaoping, LIU Yi, and LIU Guojin. Image denoising based on spectral graph theory and random walk kernel[J]., 2010, 31(7): 116-121. doi: 10.3969/j.issn.1000-436X. 2010. 07.017.

[17] 金珠. 改進的支持向量機分類算法及其在煤礦人因事故安全評價中的應(yīng)用[D]. [博士論文], 中國礦業(yè)大學(xué), 2011, 81-89. JIN Zhu. Improved support vector machine classification algorithm and application for human factors of coal mine accidents safety evaluation[D]. [Ph.D. dissertation], China University of Mining, 2011, 81-89.

[18] RENAN S, PASCAL D C, RICHARD P,. Human step detection from a piezoelectric polymer floor sensor using normalization algorithms[C].IEEE Sensors 2014, Valencia, Spain, 2014: 1169-1172.

WLAN Indoor Localization Algorithm Based on Manifold Interpolation Database Construction

ZHOU Mu①②TANG Yunxia①TIAN Zengshan①WEI Yacong①

①(,,400065,)②(,,300387,)

To deal with the high cost involved in the location fingerprint database construction due to the dense Reference Points (RPs) distribution and point-by-point Received Signal Strength (RSS) collection in the conventional Wireless Local Area Network (WLAN) indoor localization systems, a new database construction approach based on the integrated semi-supervised manifold learning and cubic spline interpolation is proposed. The proposed approach utilizes a small amount of labeled data and a massive amount of unlabeled data to find the optimal solution to localization target function, and meanwhile relies on the mapping relations between the high-dimensional signal strength space and low-dimensional physical location space to calibrate the unlabeled data with location coordinates. The extensive experiments demonstrate that the proposed approach is able to guarantee the high localization accuracy, as well as significantly reduce the cost involved in location fingerprint database construction.

Wireless Local Area Network (WLAN); Location fingerprint; Semi-supervised learning; Manifold alignment; Cubic spline interpolation

TN929.5

A

1009-5896(2017)08-1826-09

10.11999/JEIT161269

2016-11-24；

改回日期：2017-03-20；

2017-05-02

唐云霞 13629735505@139.com

國家自然科學(xué)基金(61301126)，長江學(xué)者和創(chuàng)新團隊發(fā)展計劃(IRT1299)，重慶市科委重點實驗室專項經(jīng)費，重慶郵電大學(xué)青年科學(xué)研究項目(A2013-31)

The National Natural Science Foundation of China (61301126), The Program for Changjiang Scholars and Innovative Research Team in University (IRT1299), The Special Fund of Chongqing Key Laboratory (CSTC), Young Scientific Research Program of CUPT (A2013-31)

周 牧： 男，1984年生，教授，博士后，研究方向為無線定位與導(dǎo)航技術(shù)、信號偵察與檢測技術(shù)、凸優(yōu)化與深度學(xué)習(xí)理論等.

唐云霞： 女，1994年生，碩士生，研究方向為無線定位技術(shù)、機器學(xué)習(xí).

田增山： 男，1968年生，教授，博士生導(dǎo)師，研究方向為移動通信、個人通信、GPS及蜂窩網(wǎng)定位技術(shù)等.

衛(wèi)亞聰： 女，1993年生，碩士生，研究方向為無線定位技術(shù)、數(shù)值分析.