分布式AP選擇策略在室內定位中的應用*

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

(1.中國礦業大學計算機科學與技術學院，江蘇徐州221116;2.常熟理工學院計算機科學與工程學院，江蘇常熟215500)

0 引言

室內定位是一種用于獲取室內目標物體位置信息的技術，在民用和軍用領域具有廣泛的應用前景。常見的定位算法主要基于接收信號強度指示(received signal strength indication，RSSI)、到達時間(time of arrival，TOA)、到達角度(angle of arrival，AOA)等技術［1］。其中，基于 RSSI的定位算法具有低功耗、低成本且易實現的優點［2］，被廣泛應用于無線室內定位。

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

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

1 定位模型

不同AP節點的信號強度作為一種可識別的模式(指紋)，被用于區分不同的位置點。假設在位置點A獲取D個AP節點的信號強度，構建D維信號向量RSSD

式中 rssi∈［-100，0］為位置點A處接收到第i個AP節點的信號強度。

位置點A與D維信號向量之間存在映射關系，數學表示為

訓練數據集中包含N條記錄，每條記錄可表示為向量r，向量中包含可用AP節點的信號強度和采樣點的位置

式中 D為AP節點個數，Li為對應RSS向量的位置標簽。

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

2 深度置信網絡

2.1 受限玻耳茲曼機

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

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

該聯合概率分布為

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

2.2 深度置信網絡模型

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

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

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

3 分布式AP選擇策略

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

式中 c為第c個子區域，k為該子區域中位置點的個數，S為定位區域，m為區域個數。

根據子區域與各個AP節點的相關性，將輸入向量RSSD分割為 m 個非空子集 (RSS1，RSS2，RSS3，…，RSSm)，且非空子集RSSc與子區域Rc相對應，最后將非空子集RSSc作為特征輸入來訓練子區域Rc的定位預測模型。

假設在該子區域中，掃描區域中k個位置點上第j個AP節點的信號，那么，該AP節點在此區域的相關性系數定義如下

式中 Pj為第j個AP節點與該區域的相關性，xi為第i個位置點的X軸坐標，x為該區域中k個位置點的X軸坐標的均值，yi為第i個位置點的Y軸坐標，y為該區域中k個位置點的Y軸坐標的均值，rssji為第i個位置點接收的第j個AP節點信號強度的均值，rssj為該區域中k個位置點接收的第j個AP節點信號強度的均值，k為該區域位置點個數，D為AP節點個數。

在每個子區域中，D個AP節點的相關性系數向量表示為

若Pj＞Pτ表示第j個AP節點與該子區域相關;反之，則不相關。選取相關的AP節點作為特征輸入，進行定位模型訓練。

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

1)將定位區域劃分為m個子區域，根據式(7)計算每個AP節點與各個子區域的相關性，建立相關性系數矩陣;

2)選擇相關性系數大于Pτ的AP節點，并將AP節點劃分為m組;

3)在步驟(2)中AP節點分組的基礎上，在每個子區域中，利用分組后的訓練數據集訓練DBN模型，構建定位預測模型;

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

5)利用子區域中訓練的定位預測模型估計目標的位置。

4 實驗分析

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

為不同子區域選擇較優的AP節點，首先分析RSSI的分布特征，選擇最佳的依賴特征計算相關性。在測試點上獲取節點AP9的RSSI的五個分布特征如圖2所示。

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

本文在相同訓練數據集的情況下，將所提DSAP算法與集中式SAP算法進行對比，實驗結果如圖3所示。由圖可見，本文DSAP算法在不同的誤差距離時，均具有較優的定位準確率，且明顯優于集中式的SAP算法。

圖2 AP9節點的五個信號分布特征圖Fig 2 Signal distribution feature diagram of AP9 node with five characteristics

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

本文將預測位置與實際位置之間的歐氏距離作為定位預測誤差，并將區域內位置點的平均預測誤差作為算法評判標準。本文將DSAP算法、RADAR算法［6］以及BP算法在不同區域個數下進行對比，實驗結果如圖4所示。

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

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

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

圖5 三種算法在不同分區域個數下的運行時間Fig 5 Running time of three algorithms in different number of sub regions

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

5 結論

本文提出了一種分布式AP選擇策略，并應用于室內定位。針對定位模型的可伸縮性和定位區域內AP的非全可用問題，該方法將室內區域劃分為若干個子區域，并計算子區域與AP節點之間的相關性，選取與該區域相關的AP節點作為該子區域的訓練節點，最后通過DBN模型進行定位模型訓練。該方法能夠有效去除較大噪聲和位置分辨能力弱的AP節點，降低了AP節點不可用的概率。實驗表明:該算法較BP算法、RADAR算法而言，具有運行時間短且平均定位誤差小的優點。但在復雜的室內環境中，采集有標記的訓練數據將面臨較大困難，今后重點將嘗試利用半監督學習方法來訓練未標記的數據，以提高其與預測能力。

［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］.傳感器與微系統，2014，33(9):132-134.

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

［4］劉軍發，谷 洋，陳益強，等.具有時效機制的增量式無線定位方法［J］.計算機學報，2013，36(7):1448-1455.

［5］Lin Tsungnan，Fang 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］孫志軍，薛 磊，許陽明，等.深度學習研究綜述［J］.計算機應用研究，2012，29(8):2806-2810.