牟平，凌銘，胡銳

( 上海工程技術(shù)大學(xué) 電子電氣工程學(xué)院，上海 201620 )

0 引 言

隨著無線局域網(wǎng)(WLAN)、云計(jì)算、智能終端以及傳感器的普及與高速發(fā)展，對(duì)位置信息的需求正在不斷增加. 位置信息的需求推動(dòng)了基于位置服務(wù)(LBS)的高速發(fā)展，而定位技術(shù)是LBS 的核心. 目前室外定位采用全球衛(wèi)星導(dǎo)航系統(tǒng)(GNSS)，包括GPS和我國的北斗衛(wèi)星導(dǎo)航系統(tǒng)(BDS)等，定位方法相對(duì)完善. 然而，室內(nèi)GNSS 衛(wèi)星信號(hào)弱或者根本無信號(hào)，導(dǎo)致室內(nèi)無法利用GNSS 衛(wèi)星信號(hào)進(jìn)行正常定位. 特別是一些公共區(qū)域，如大型商場(chǎng)、地下停車場(chǎng)、大型圖書館都需要較為精確的位置服務(wù)[1]，因此，對(duì)于室內(nèi)定位精度的需求變得日益迫切.

自2000 年起，利用無線保真(Wi-Fi)位置指紋進(jìn)行室內(nèi)定位的概念被美國微軟研究院率先提出，同時(shí)推出室內(nèi)定位系統(tǒng)Radar[2]，由于Wi-Fi 的普及程度比超寬帶(UWB)和一些無線射頻識(shí)別(RFID)更為廣泛且定位過程中無需部署[3]，所以近年來許多學(xué)者不斷研究如何在現(xiàn)有的指紋匹配定位模型上改進(jìn)已有算法來提升定位精度以及定位性能，影響模型定位精度的關(guān)鍵因素之一是接收信號(hào)強(qiáng)度(RSS). 文獻(xiàn)[4]提出接入點(diǎn)(AP)選擇法融合K最近鄰算法(KNN)來進(jìn)行室內(nèi)定位，其融合效果比傳統(tǒng)KNN 精度上有較大地提升，但在實(shí)際定位過程中由于數(shù)據(jù)量較大，利用KNN 時(shí)間復(fù)雜度將會(huì)提升，同時(shí)也會(huì)帶來定位精度的下降. 文獻(xiàn)[5]利用每個(gè)AP 在參考點(diǎn)的分組定位和加權(quán)質(zhì)心算法相結(jié)合，多方位測(cè)距減小誤差，以降低RSS 變化帶來的影響. 文獻(xiàn)[6]提出優(yōu)化的隨機(jī)森林(RF)，引入伯努利分布來減少選取訓(xùn)練集中的冗余特征，使得弱分類器之間的隨機(jī)性和多樣性降低.

基于此，本文提出穩(wěn)定性優(yōu)先的AP 選擇方案來降低RSS 變化帶來指紋向量維度和值不同的影響，這樣能夠保證離線數(shù)據(jù)庫中的每個(gè)可用的AP 都是在定位過程中起重要作用的AP，同時(shí)融合集成學(xué)習(xí)中隨機(jī)森林的多個(gè)弱分類器來提高定位精度并減少定位時(shí)間，從而增加定位效率.

1 室內(nèi)定位整體流程

本文采用Wi-Fi 位置指紋來進(jìn)行室內(nèi)定位，主要可分為離線階段和在線階段[7]. 離線階段需要移動(dòng)終端獲取待定位區(qū)域的RSS 信號(hào)值，并對(duì)定位區(qū)域進(jìn)行合理的網(wǎng)格劃分，將搜集到的RSS 數(shù)據(jù)發(fā)送至后臺(tái)，形成初步的指紋數(shù)據(jù)庫. 在后臺(tái)對(duì)初步指紋數(shù)據(jù)庫進(jìn)行AP 選擇，選擇重要的AP，這里的重要AP 是指這些AP 的RSS 信號(hào)有利于定位，比如與地理位置的映射最為明顯、位置分辨能力最高、樣本波動(dòng)小等，然后將所得指紋數(shù)據(jù)庫作為訓(xùn)練集輸入到RF 訓(xùn)練模型中[8]；在線定位階段移動(dòng)終端將搜集到的RSS 信息，根據(jù)離線階段所選擇出有用的AP，過濾掉在線搜集到的那些來源于其他AP 的RSS 信號(hào)，然后將過濾過后的信號(hào)發(fā)送至后臺(tái)進(jìn)入訓(xùn)練好的RF模型中得出最終的位置，其中介質(zhì)訪問控制(MAC)為每個(gè)AP 的唯一標(biāo)識(shí). 圖1 為室內(nèi)定位整體流程.

圖1 室內(nèi)定位整體流程

2 改進(jìn)的AP 選擇算法

2.1 AP 選擇的基本理論

在基于指紋的無線室內(nèi)定位中，定位的精度受RSS 信號(hào)的嚴(yán)重影響，并且處于不斷波動(dòng)的狀態(tài). 即使是在同一個(gè)位置上接收來自同一個(gè)AP 的RSS 信號(hào)也有可能隨著環(huán)境發(fā)生變化. 在復(fù)雜的室內(nèi)環(huán)境下，雖然可用的AP 很多，但是有很多AP 是無用的甚至?xí)档投ㄎ痪?，因此需要選擇合適的AP 數(shù)目來提升定位精度，以確保離線階段數(shù)據(jù)庫的構(gòu)建更準(zhǔn)確[9].

在離線階段和在線階段均可以執(zhí)行AP 選擇. 此外，AP 選擇過程可以為所有參考點(diǎn)選擇AP 的統(tǒng)一子集，可以是整個(gè)區(qū)域或由粗略定位選擇的子集，被稱為統(tǒng)一AP 選擇. 相反，基于參考點(diǎn)的選擇方法單獨(dú)為每個(gè)參考點(diǎn)選擇一組AP. 這樣，每個(gè)參考點(diǎn)可以包含與其他AP 不同的AP 集合[10]. 本文考慮改進(jìn)離線階段的統(tǒng)一AP 選擇，利用AP 穩(wěn)定性優(yōu)先來衡量AP 質(zhì)量，同時(shí)對(duì)于AP 選擇定義如下：對(duì)于定位區(qū)域中AP 集合P={P1,P2,···,Pn} ，我們需要找到其中的一個(gè)子集P′使得在該子集上完成定位的精度最高，即

式中：Φi為除選定的AP 索引之外的所有索引歸零來定義所選AP；L′為子集P′的基數(shù)；Φ為選擇矩陣用來選擇眾多AP 中有用的AP.

2.2 改進(jìn)的AP 選擇算法

傳統(tǒng)的基于信息增益(IG) AP 選擇算法[11]，雖然考慮到AP 之間的相關(guān)性，但是并沒有考慮AP 的RSS 樣本數(shù)據(jù)的穩(wěn)定性.因此，本文提出一種基于穩(wěn)定性優(yōu)先的AP 選擇算法，其中穩(wěn)定性包含：每個(gè)AP的RSS 樣本的方差；在同一位置下AP 所出現(xiàn)的頻率.

在定位區(qū)域中，同一位置采集到來自同一AP 的RSS 樣本可能會(huì)隨時(shí)間以及環(huán)境的變化而變化. 對(duì)于參考點(diǎn)L，會(huì)接收到來自n個(gè)AP 的RSS 信號(hào)，AP 集合表示成 {AP1,AP2,···,APn} ，為了使指紋數(shù)據(jù)庫能更好地反映數(shù)據(jù)特征和數(shù)據(jù)維度以及減少在線階段的計(jì)算量.本文通過穩(wěn)定性優(yōu)先的AP 選擇算法從這n個(gè)AP 中選擇出合適的m個(gè)AP，主要流程如圖2所示.

圖2 改進(jìn)AP 算法流程

在采樣點(diǎn)L上接收到第i個(gè)AP 的n次采樣數(shù)據(jù)為 {RSS1,RSS2,···,RSSn} ，于是該AP 的RSS 數(shù)據(jù)波動(dòng)幅度可以通過方差計(jì)算得到，即

式中，RSS為n次RSS 數(shù)據(jù)的均值. 此處的n與上述保持一致，每個(gè)AP 的RSS 樣本方差實(shí)際上就反映了數(shù)據(jù)波動(dòng)，同時(shí)考慮到方差可能為0，所以加入拉普拉斯平滑引入 ε 以避免方差為0 的情況，與此同時(shí)考慮到每個(gè)AP 在整個(gè)采樣點(diǎn)出現(xiàn)的頻率，結(jié)合數(shù)據(jù)波動(dòng)與出現(xiàn)的頻率衡量RSS 樣本的穩(wěn)定性，即

計(jì)算出穩(wěn)定度之后對(duì)穩(wěn)定度進(jìn)行排序，選擇穩(wěn)定度最高的前m個(gè)AP 用來作為AP 選擇的結(jié)果，并以此來構(gòu)建指紋數(shù)據(jù)庫，根據(jù)對(duì)AP 數(shù)目對(duì)室內(nèi)定位產(chǎn)生影響的相關(guān)研究[12-13]，本文選擇AP 數(shù)目為5 個(gè).

3 RF 算法

RF[14]模型是在2001 年提出的一種基于決策樹分類的集成學(xué)習(xí)算法，通過對(duì)訓(xùn)練集進(jìn)行N次有放回取樣構(gòu)建基分類器. 在RF 中，訓(xùn)練集中的樣本就是在離線階段所采集到的一條RSS 數(shù)據(jù)，其中的特征則是經(jīng)過AP 選擇后離線數(shù)據(jù)庫中的每個(gè)AP 在采樣點(diǎn)對(duì)應(yīng)的RSS 值，標(biāo)簽是每個(gè)采樣點(diǎn)的位置信息. 隨機(jī)抽樣從特征中隨機(jī)選取幾個(gè)特征，因此基分類器是隨機(jī)的，最終N個(gè)隨機(jī)且彼此獨(dú)立的分類器決策樹構(gòu)成隨機(jī)森林，當(dāng)實(shí)時(shí)定位階段用戶發(fā)來經(jīng)過篩選的RSS 信號(hào)后，進(jìn)入隨機(jī)森林模型中，所有的基分類器產(chǎn)生預(yù)測(cè)結(jié)果，最終投票結(jié)果的眾數(shù)作為輸出位置.圖3 為隨機(jī)森林算法流程.

圖3 RF 算法

RF 算法流程為：

輸入：離線數(shù)據(jù)庫中的所有樣本和位置標(biāo)簽作為初始訓(xùn)練集，記為D.

輸出：對(duì)于待測(cè)樣本xt，N棵決策樹的輸出，即最終移動(dòng)終端的.

開始

Fori=1，2，···，Ntree

1) 對(duì)初始訓(xùn)練集D進(jìn)行隨機(jī)抽樣，生成每個(gè)分類器的對(duì)應(yīng)的訓(xùn)練集Si；

2) 使用訓(xùn)練集Si生成所對(duì)應(yīng)的決策樹Ti，并從每棵決策樹結(jié)點(diǎn)上隨機(jī)選取最優(yōu)特征，不斷的分裂樹至樹生長到最大.

在線階段發(fā)送經(jīng)AP 篩選的RSS 信號(hào)進(jìn)入隨機(jī)森林模型中得出最后移動(dòng)終端的位置.

結(jié)束

隨機(jī)森林分類是指當(dāng)訓(xùn)練集的因變量是不連續(xù)變量時(shí)，此時(shí)輸出最終位置用式(5)表示為

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

4.1 實(shí)驗(yàn)環(huán)境

本文的實(shí)驗(yàn)場(chǎng)地選在上海工程技術(shù)大學(xué)實(shí)訓(xùn)樓四樓，實(shí)驗(yàn)環(huán)境保持不變，測(cè)試環(huán)境周圍的AP 是利用學(xué)校布置的AP 點(diǎn)，不會(huì)隨意更改AP 或者加入其他AP. 其中測(cè)試區(qū)域結(jié)構(gòu)如圖4 所示，信號(hào)采集所用的裝置為華為P20，采用的AP 是學(xué)校已有的AP，通過自主開發(fā)的軟件采集RSS 信息，其中每個(gè)網(wǎng)格點(diǎn)大小設(shè)置為1.5 m×1.5 m，并在每個(gè)網(wǎng)格點(diǎn)東南西北四個(gè)方向共采集100 組信號(hào)，采集的頻率為1 Hz.

圖4 測(cè)試區(qū)域結(jié)構(gòu)

實(shí)驗(yàn)中采樣點(diǎn)共有205 個(gè)，為將定位結(jié)果量化，利用真實(shí)值與測(cè)量值之間的距離定義為誤差

4.2 實(shí)驗(yàn)結(jié)果分析

本文利用改進(jìn)的AP 選擇方法融合RF 來對(duì)位置做出更精確的估計(jì)，同時(shí)與基于IG 的AP 選擇融合RF，未經(jīng)AP 選擇的RF 和改進(jìn)的AP 選擇融合加權(quán)的K近鄰算法(WKNN)進(jìn)行實(shí)驗(yàn)對(duì)比. 本實(shí)驗(yàn)中參數(shù)設(shè)置為：AP 最佳數(shù)目選擇為5，RF 分類器個(gè)數(shù)為500 個(gè)，WKNN 的K值選擇為4，對(duì)于權(quán)重的選擇為歐氏距離的倒數(shù). 實(shí)驗(yàn)所需的部分?jǐn)?shù)據(jù)采集如表1所示.

表1 實(shí)驗(yàn)采集的部分RSS 數(shù)據(jù)dBm

如圖5 所示，為了直觀顯示上述算法在定位誤差上的表現(xiàn)，統(tǒng)計(jì)了多組實(shí)驗(yàn)求取平均定位誤差用來衡量算法的好壞. 由圖5 可知，改進(jìn)的AP 和RF 算法的平均定位誤差為1.26 m，要比IG+RF、RF、改進(jìn)的AP+WKNN 分別降低17.2%、29.3%、23.2%.

圖5 四種不同算法的平均定位誤差

圖6 為不同定位算法定位誤差的累計(jì)概率分布.由圖6 可知，改進(jìn)的AP 選擇和RF 算法有78%的概率保證定位誤差在1.5 m 以內(nèi)，90%的概率保證定位誤差在2 m 以內(nèi)； IG+RF 有60%的概率保證定位誤差在1.5 m 以內(nèi)，80%的概率定位誤差在2 m 以內(nèi)；改進(jìn)的AP+WKNN 有50%的概率定位誤差在1.5 m以內(nèi)，63%的概率定位誤差在2 m 以內(nèi)；RF 有42%的概率定位誤差在1.5 m 以內(nèi)，57%的概率定位誤差控制在2 m 以內(nèi). 綜上可知，在定位精度上，本文提出的算法與其余三種算法相比有明顯提升.

圖6 各種算法的定位誤差累積概率分布

由于RF 在離線階段需要訓(xùn)練出RF 模型，所以需要一些時(shí)間，但定位系統(tǒng)實(shí)時(shí)性衡量的是在線定位階段是否能實(shí)時(shí)反映移動(dòng)終端的位置信息. 因此，本文考慮的是在線定位階段上述算法的定位時(shí)間. 如圖7 所示，以6 個(gè)待定位點(diǎn)為例，展示上述算法在在線定位階段的定位時(shí)間. 驗(yàn)證算法從圖7 可以看出，改進(jìn)的AP+RF 的定位時(shí)間平均0.98 s，對(duì)于改進(jìn)的AP+WKNN 而言數(shù)據(jù)量大的情況下，需要在線定位階段遍歷數(shù)據(jù)庫進(jìn)行比對(duì)，通過統(tǒng)計(jì)100 組實(shí)驗(yàn)下的平均定位時(shí)間分析可知，其定位時(shí)間比改進(jìn)的AP+RF 長；由于RF 未經(jīng)AP 選擇所以數(shù)據(jù)庫中包含有大量對(duì)定位結(jié)果無用甚至有害的AP，所以導(dǎo)致在線定位時(shí)間平均在1.3 s；IG+RF 算法利用信息增益最大化選擇AP 考慮到了AP 之間的相關(guān)性，但并未考慮數(shù)據(jù)穩(wěn)定性，其中會(huì)存在一些不穩(wěn)定AP 加大在線定位階段的計(jì)算量，導(dǎo)致定位時(shí)間平均在1.15 s.

圖7 各個(gè)算法的定位時(shí)間

5 結(jié)束語

本文提出了改進(jìn)的AP 選擇融合RF 的算法. 首先對(duì)初始指紋數(shù)據(jù)庫進(jìn)行AP 選擇，根據(jù)每個(gè)AP 的RSS 樣本的穩(wěn)定度來選取前5 個(gè)AP 作為定位AP，然后將處理好的指紋數(shù)據(jù)庫作為數(shù)據(jù)集進(jìn)行RF 的訓(xùn)練，形成RF 模型. 在在線定位階段通過離線階段已經(jīng)選好的5 個(gè)AP 對(duì)RSS 數(shù)據(jù)篩選，然后經(jīng)過RF模型投票得出最后的結(jié)果. 實(shí)驗(yàn)結(jié)果表明：本文提出的算法在定位誤差以及定位時(shí)間方面優(yōu)于其他算法，且改進(jìn)AP+RF 的平均定位誤差穩(wěn)定在1.26 m，在線定位時(shí)間平均也只有0.98 s；在Wi-Fi 室內(nèi)定位中一定程度地減小了定位誤差和降低定位時(shí)間，在室內(nèi)定位技術(shù)中有一定的意義.