分布式AP選擇策略在室內(nèi)定位中的應(yīng)用*

葛柳飛，趙秀蘭，李克清，戴 歡，張 騫

(1.中國礦業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇徐州221116;2.常熟理工學(xué)院計(jì)算機(jī)科學(xué)與工程學(xué)院，江蘇常熟215500)

0 引言

室內(nèi)定位是一種用于獲取室內(nèi)目標(biāo)物體位置信息的技術(shù)，在民用和軍用領(lǐng)域具有廣泛的應(yīng)用前景。常見的定位算法主要基于接收信號強(qiáng)度指示(received signal strength indication，RSSI)、到達(dá)時(shí)間(time of arrival，TOA)、到達(dá)角度(angle of arrival，AOA)等技術(shù)［1］。其中，基于 RSSI的定位算法具有低功耗、低成本且易實(shí)現(xiàn)的優(yōu)點(diǎn)［2］，被廣泛應(yīng)用于無線室內(nèi)定位。

基于RSSI的定位算法通常分為:基于信號傳播模型的定位算法［3］和基于指紋模型的定位算法［4］。在具有大量AP節(jié)點(diǎn)部署的無線網(wǎng)絡(luò)中，為了獲得目標(biāo)位置，上述方法所處理的數(shù)據(jù)都是高維向量(AP節(jié)點(diǎn)的個數(shù))。同時(shí)，由于物體遮擋和節(jié)點(diǎn)故障等因素，導(dǎo)致將所有AP節(jié)點(diǎn)作為特征輸入的定位效果并不一定最優(yōu)，冗余的AP節(jié)點(diǎn)增加了位置估計(jì)的難度，易造成過度擬合，并增加了時(shí)間和空間的復(fù)雜度。針對該問題，采用合適的選擇機(jī)制篩選AP節(jié)點(diǎn)，獲得較優(yōu)的AP節(jié)點(diǎn)作為特征輸入，既達(dá)到降維的作用，又提高了定位精度。文獻(xiàn)［5］提出使用數(shù)據(jù)挖掘技術(shù)選擇較優(yōu)的AP節(jié)點(diǎn)，通過篩選的AP節(jié)點(diǎn)建立位置指紋庫。

本文提出一種分布式AP選擇(distributed selection on AP，DSAP)算法，能夠有效去除較大噪聲或者位置分辨能力弱的AP節(jié)點(diǎn)。實(shí)驗(yàn)表明:在12 m×12 m的區(qū)域范圍內(nèi)，該算法平均定位誤差為0.4151 m，較反向傳播(back propagation，BP)算法、RADAR［6］算法而言，定位誤差低，且降低了定位算法的復(fù)雜度。

1 定位模型

不同AP節(jié)點(diǎn)的信號強(qiáng)度作為一種可識別的模式(指紋)，被用于區(qū)分不同的位置點(diǎn)。假設(shè)在位置點(diǎn)A獲取D個AP節(jié)點(diǎn)的信號強(qiáng)度，構(gòu)建D維信號向量RSSD

式中 rssi∈［-100，0］為位置點(diǎn)A處接收到第i個AP節(jié)點(diǎn)的信號強(qiáng)度。

位置點(diǎn)A與D維信號向量之間存在映射關(guān)系，數(shù)學(xué)表示為

訓(xùn)練數(shù)據(jù)集中包含N條記錄，每條記錄可表示為向量r，向量中包含可用AP節(jié)點(diǎn)的信號強(qiáng)度和采樣點(diǎn)的位置

式中 D為AP節(jié)點(diǎn)個數(shù)，Li為對應(yīng)RSS向量的位置標(biāo)簽。

在線定位就是利用離線階段建立的信號—位置映射模型預(yù)測移動目標(biāo)的位置。

2 深度置信網(wǎng)絡(luò)

2.1 受限玻耳茲曼機(jī)

受限玻耳茲曼機(jī)(restricted Boltzmann machine，RBM)由可見層和隱含層兩部分構(gòu)成，神經(jīng)元之間的連接被限制在不同層，相同層之間不存在神經(jīng)元的連接，如圖1(a)所示。RBM是一種基于能量的模型，其能量函數(shù)定義如下

式中 I和J分別為可見層和隱含層的神經(jīng)元個數(shù)，xi和hj分別為可見層第i個神經(jīng)元與隱含層第j個神經(jīng)元的值。θ =(wij，ai，bj)為 RBM 的參數(shù)，wij為可見層節(jié)點(diǎn) xi與隱含層節(jié)點(diǎn)hj之間的連接權(quán)值，ai和bj分別為xi和hj的偏置值。

該聯(lián)合概率分布為

式中 Z(θ)為歸一化項(xiàng)。

2.2 深度置信網(wǎng)絡(luò)模型

為解決BP網(wǎng)絡(luò)易陷入局部最優(yōu)的問題，Hinton G等人［7］于2006年提出了深度置信網(wǎng)絡(luò)(deep belief networks，DBN)，其在圖像處理［8］、語音識別［9］等領(lǐng)域發(fā)揮了重要作用。

RBM是DBN的基本構(gòu)建塊，如圖1(b)所示。當(dāng)高維數(shù)據(jù)輸入RBM1可見層，隱含層將通過連接權(quán)值提取輸入數(shù)據(jù)的特征;同時(shí)，RBM1隱含層的輸出將作為RBM2可見層的輸入，RBM2隱含層將進(jìn)一步提取數(shù)據(jù)的深層次特征［10］。若干個RBM模塊構(gòu)成了DBN模型，其在預(yù)訓(xùn)練的過程中通過層與層之間的能量函數(shù)初始化網(wǎng)絡(luò)權(quán)值，最后通過BP算法來微調(diào)網(wǎng)絡(luò)間的權(quán)值。

圖1 RBM和DBN模型Fig 1 RBM and DBN models

3 分布式AP選擇策略

在復(fù)雜的室內(nèi)環(huán)境中，AP節(jié)點(diǎn)非全可用的問題增加了位置估計(jì)的不確定性。本文提出了一種分布式AP選擇策略，首先將定位區(qū)域S劃分為m個子區(qū)域，子區(qū)域定義如式(6)所示

式中 c為第c個子區(qū)域，k為該子區(qū)域中位置點(diǎn)的個數(shù)，S為定位區(qū)域，m為區(qū)域個數(shù)。

根據(jù)子區(qū)域與各個AP節(jié)點(diǎn)的相關(guān)性，將輸入向量RSSD分割為 m 個非空子集 (RSS1，RSS2，RSS3，…，RSSm)，且非空子集RSSc與子區(qū)域Rc相對應(yīng)，最后將非空子集RSSc作為特征輸入來訓(xùn)練子區(qū)域Rc的定位預(yù)測模型。

假設(shè)在該子區(qū)域中，掃描區(qū)域中k個位置點(diǎn)上第j個AP節(jié)點(diǎn)的信號，那么，該AP節(jié)點(diǎn)在此區(qū)域的相關(guān)性系數(shù)定義如下

式中 Pj為第j個AP節(jié)點(diǎn)與該區(qū)域的相關(guān)性，xi為第i個位置點(diǎn)的X軸坐標(biāo)，x為該區(qū)域中k個位置點(diǎn)的X軸坐標(biāo)的均值，yi為第i個位置點(diǎn)的Y軸坐標(biāo)，y為該區(qū)域中k個位置點(diǎn)的Y軸坐標(biāo)的均值，rssji為第i個位置點(diǎn)接收的第j個AP節(jié)點(diǎn)信號強(qiáng)度的均值，rssj為該區(qū)域中k個位置點(diǎn)接收的第j個AP節(jié)點(diǎn)信號強(qiáng)度的均值，k為該區(qū)域位置點(diǎn)個數(shù)，D為AP節(jié)點(diǎn)個數(shù)。

在每個子區(qū)域中，D個AP節(jié)點(diǎn)的相關(guān)性系數(shù)向量表示為

若Pj＞Pτ表示第j個AP節(jié)點(diǎn)與該子區(qū)域相關(guān);反之，則不相關(guān)。選取相關(guān)的AP節(jié)點(diǎn)作為特征輸入，進(jìn)行定位模型訓(xùn)練。

基于分布式AP選擇策略的定位算法的具體步驟:

1)將定位區(qū)域劃分為m個子區(qū)域，根據(jù)式(7)計(jì)算每個AP節(jié)點(diǎn)與各個子區(qū)域的相關(guān)性，建立相關(guān)性系數(shù)矩陣;

2)選擇相關(guān)性系數(shù)大于Pτ的AP節(jié)點(diǎn)，并將AP節(jié)點(diǎn)劃分為m組;

3)在步驟(2)中AP節(jié)點(diǎn)分組的基礎(chǔ)上，在每個子區(qū)域中，利用分組后的訓(xùn)練數(shù)據(jù)集訓(xùn)練DBN模型，構(gòu)建定位預(yù)測模型;

4)在線預(yù)測階段，獲取移動設(shè)備接收的RSS指紋信息并作為輸入向量，利用分區(qū)域模塊選擇對應(yīng)子區(qū)域;

5)利用子區(qū)域中訓(xùn)練的定位預(yù)測模型估計(jì)目標(biāo)的位置。

4 實(shí)驗(yàn)分析

定位數(shù)據(jù)的采集實(shí)驗(yàn)場景設(shè)于綜合實(shí)驗(yàn)室內(nèi)，數(shù)據(jù)采集設(shè)備為三星手機(jī)(I9228)，系統(tǒng)為Android 4.1.2。實(shí)驗(yàn)室長約12.8 m，寬約12.5 m，高約3 m，室內(nèi)布置有工位、電腦等辦公用品，AP節(jié)點(diǎn)高度保持1.6 m。在該區(qū)域內(nèi)，能夠收集到25個AP節(jié)點(diǎn)的信號，部分AP信號的傳播路徑為非視距的，存在柱子的阻隔。將區(qū)域劃分為144個小區(qū)域，每個小區(qū)域大小為1 m×1 m，以小區(qū)域中心為信號強(qiáng)度采集點(diǎn)。為保證樣本數(shù)據(jù)的準(zhǔn)確性，每個信號采集點(diǎn)獲取600次AP信號集，每秒一次。

為不同子區(qū)域選擇較優(yōu)的AP節(jié)點(diǎn)，首先分析RSSI的分布特征，選擇最佳的依賴特征計(jì)算相關(guān)性。在測試點(diǎn)上獲取節(jié)點(diǎn)AP9的RSSI的五個分布特征如圖2所示。

由圖可見，均值、中值、最大值以及最小值的分布特征較相似，但是方差的分布特征變化無明顯規(guī)律。因此，方差不能作為依賴特征。在缺乏足夠信號樣本的情況下，利用中值、最大值以及最小值來實(shí)時(shí)統(tǒng)計(jì)的定位效果明顯次于均值的效果。因此，本文將信號均值作為依賴特征，計(jì)算子區(qū)域與AP節(jié)點(diǎn)的相關(guān)性。

本文在相同訓(xùn)練數(shù)據(jù)集的情況下，將所提DSAP算法與集中式SAP算法進(jìn)行對比，實(shí)驗(yàn)結(jié)果如圖3所示。由圖可見，本文DSAP算法在不同的誤差距離時(shí)，均具有較優(yōu)的定位準(zhǔn)確率，且明顯優(yōu)于集中式的SAP算法。

圖2 AP9節(jié)點(diǎn)的五個信號分布特征圖Fig 2 Signal distribution feature diagram of AP9 node with five characteristics

圖3 DSAP算法與SAP算法在不同誤差距離下的定位準(zhǔn)確率Fig 3 Location accuracy of DSAP and SAP algorithms in different error distance

本文將預(yù)測位置與實(shí)際位置之間的歐氏距離作為定位預(yù)測誤差，并將區(qū)域內(nèi)位置點(diǎn)的平均預(yù)測誤差作為算法評判標(biāo)準(zhǔn)。本文將DSAP算法、RADAR算法［6］以及BP算法在不同區(qū)域個數(shù)下進(jìn)行對比，實(shí)驗(yàn)結(jié)果如圖4所示。

圖4 三種算法在不同區(qū)域個數(shù)下的平均預(yù)測誤差Fig 4 Average prediction error of three algorithms in different number of regions

由圖可見，隨著區(qū)域個數(shù)增加，三種算法的平均預(yù)測誤差呈遞減趨勢變化;本文DSAP算法在不同區(qū)域數(shù)的情況下，具有較低的平均預(yù)測誤差且明顯優(yōu)于BP算法和RADAR算法。

在英特爾 i5處理器，2GB內(nèi)存的 PC環(huán)境下，利用Matlab軟件執(zhí)行DSAP算法、RADAR算法以及BP算法，算法執(zhí)行時(shí)間主要包括分區(qū)域模塊執(zhí)行時(shí)間和位置估計(jì)時(shí)間，其取值為測試數(shù)據(jù)運(yùn)行100次所需時(shí)間的均值。三種算法在不同區(qū)域個數(shù)下的執(zhí)行時(shí)間如圖5所示。

圖5 三種算法在不同分區(qū)域個數(shù)下的運(yùn)行時(shí)間Fig 5 Running time of three algorithms in different number of sub regions

由圖可見，當(dāng)區(qū)域數(shù)為16時(shí)，由于分區(qū)域模塊執(zhí)行時(shí)間較長，導(dǎo)致三種算法的運(yùn)行時(shí)間明顯增加;當(dāng)區(qū)域數(shù)分別為6和8時(shí)，DSAP算法執(zhí)行時(shí)間短且明顯低于其它兩種算法。由圖4和圖5可知，當(dāng)區(qū)域數(shù)為8時(shí)，本文算法定位誤差小且運(yùn)行時(shí)間短，較BP算法、RADAR算法而言，平均定位誤差分別降低了35.95%，46.78%，運(yùn)行時(shí)間分別減少了22.8%，32.9%。

5 結(jié)論

本文提出了一種分布式AP選擇策略，并應(yīng)用于室內(nèi)定位。針對定位模型的可伸縮性和定位區(qū)域內(nèi)AP的非全可用問題，該方法將室內(nèi)區(qū)域劃分為若干個子區(qū)域，并計(jì)算子區(qū)域與AP節(jié)點(diǎn)之間的相關(guān)性，選取與該區(qū)域相關(guān)的AP節(jié)點(diǎn)作為該子區(qū)域的訓(xùn)練節(jié)點(diǎn)，最后通過DBN模型進(jìn)行定位模型訓(xùn)練。該方法能夠有效去除較大噪聲和位置分辨能力弱的AP節(jié)點(diǎn)，降低了AP節(jié)點(diǎn)不可用的概率。實(shí)驗(yàn)表明:該算法較BP算法、RADAR算法而言，具有運(yùn)行時(shí)間短且平均定位誤差小的優(yōu)點(diǎn)。但在復(fù)雜的室內(nèi)環(huán)境中，采集有標(biāo)記的訓(xùn)練數(shù)據(jù)將面臨較大困難，今后重點(diǎn)將嘗試?yán)冒氡O(jiān)督學(xué)習(xí)方法來訓(xùn)練未標(biāo)記的數(shù)據(jù)，以提高其與預(yù)測能力。

［1］Dai Huan，Zhu Zhaomin，Gu Xiaofeng.Multi-target indoor localization and tracking on video monitoring system in a wireless sensor networks［J］.Journal of Network and Computer Application，2013，36(1):228-234.

［2］孫中廷，華 鋼，黃金城.基于進(jìn)化理論的無線網(wǎng)絡(luò)室內(nèi)定位算法［J］.傳感器與微系統(tǒng)，2014，33(9):132-134.

［3］文春武，宋 杰，姚家振.基于RSSI校正的無線傳感器網(wǎng)絡(luò)定位算法［J］.傳感器與微系統(tǒng)，2014，33(12):134-136.

［4］劉軍發(fā)，谷 洋，陳益強(qiáng)，等.具有時(shí)效機(jī)制的增量式無線定位方法［J］.計(jì)算機(jī)學(xué)報(bào)，2013，36(7):1448-1455.

［5］Lin Tsungnan，F(xiàn)ang Shihhau，Tseng Weihan，et al.A group-discrimination-based access point selection for WLAN fingerprinting localization［J］.IEEE Transactions on Vehicular Technology，2014，63(8):3967-3975.

［6］Bahl P，Padmanabhan V N.RADAR:An in-building RF-based user location and tracking system［C］∥Proceeding of the IEEE INFOCOM，New York:IEEE Computer and Communications Society，2000:775-784.

［7］Hinton G，Salakhutdinov R.Reducing the dimensionality of data with neural networks［J］.Science，2006，313(5786):504-507.

［8］Chen Yushi，Lin Zhouhan，Zhao Xing，et al.Deep learning-based classification of hyperspectral data［J］.IEEE Journal of Selected Topics in Applied Earth Observations and Remote Sensing，2014，7(6):2094-2107.

［9］Mohamed A R，Dahl G E，Hinton G.Acoustic modeling using deep belief networks［J］.IEEE Transactions on Audio，Speech and Language Processing，2012，20(1):14-22.

［10］孫志軍，薛 磊，許陽明，等.深度學(xué)習(xí)研究綜述［J］.計(jì)算機(jī)應(yīng)用研究，2012，29(8):2806-2810.