后驗加權貝葉斯算法的WiFi室內(nèi)定位

何 洋，吳 飛，張玉金，朱 海，蔡文炎

后驗加權貝葉斯算法的WiFi室內(nèi)定位

何 洋，吳 飛，張玉金，朱 海，蔡文炎

（上海工程技術大學 電子電氣工程學院，上海 201620）

針對WiFi電磁指紋庫方法的在線定位階段中傳統(tǒng)樸素貝葉斯算法對于定位數(shù)據(jù)樣本的獨立性假設具有主觀性和局限性，且增加了計算開銷的問題，提出基于后驗加權貝葉斯算法的實時定位方法：加權貝葉斯算法為定位數(shù)據(jù)的特征屬性分配適當?shù)臋嘀?，考慮了定位數(shù)據(jù)之間的關聯(lián)性；將其進一步優(yōu)化，依據(jù)定位數(shù)據(jù)特性，加入后驗概率估計過程以提高分類器的實時性；最后將改進后的加權貝葉斯算法與樸素貝葉斯算法和支持向量機算法進行比較分析。實驗結果表明該方法能較好地提高在線定位階段的實時性和精準性。

室內(nèi)定位；屬性權值；后驗概率估計過程；實時性

0 引言

無線傳感網(wǎng)絡技術、大數(shù)據(jù)計算以及智能硬件等先進技術的迅速發(fā)展和應用成本的降低使得人們的日常出行變得更加智能便捷，很多應用以及活動行為均是基于位置信息進行個性化服務。室外開闊環(huán)境能夠使用全球定位系統(tǒng)（global positioning system，GPS）或者北斗衛(wèi)星導航系統(tǒng)（BeiDou navigation satellite system，BDS），這些精準的衛(wèi)星系統(tǒng)為人們的行為活動提供優(yōu)良的定位服務；而在場景錯綜復雜的室內(nèi)環(huán)境下，衛(wèi)星信號難以有效地接入終端設備：因此近年來室內(nèi)定位已經(jīng)成為人們關注的熱點領域。

自從微軟在2000年推出的Radar系統(tǒng)[1]和Maryland大學研發(fā)的Hours系統(tǒng)以來[2]，基于無線保真（wireless fidelity，WiFi）電磁信號的室內(nèi)定位研究受到了廣泛的關注，不同于利用超寬帶（ultra wide band, UWB）、無線射頻識別（radio frequency identification devices, RFID）和紅外線等定位方式需要另外單獨架設專門的傳感設備，由于WiFi在現(xiàn)實生活中的普及程度和設備成本的因素，更有商用價值。根據(jù)文獻[3]針對電磁信號的傳播建立的損耗模型，WiFi信號在傳播過程中經(jīng)過不同區(qū)域會產(chǎn)生一定的質(zhì)量衰減，正是利用這種信號的差異，依據(jù)接收信號強度（received signal strength, RSS）建立電磁指紋庫的定位方式成為主流的方法之一。電磁指紋庫的定位方式分為離線階段和在線階段，其中離線階段掃描、采集周圍區(qū)域中無線接入點（access point, AP）的RSS數(shù)值，并經(jīng)由相關處理建立電磁指紋庫。

在線階段，運用相關的分類算法建立與電磁指紋庫的數(shù)據(jù)映射關系，以實現(xiàn)定位功能。文獻[4]針對RSS數(shù)值利用樸素貝葉斯（Na?ve Bayes，NB）和三角形質(zhì)心算法求解位置坐標，但是由于NB算法本身對于數(shù)據(jù)的獨立性假設具有局限性，這一條件在實際運用中過于苛刻，且并未考慮數(shù)據(jù)分布本身的內(nèi)在聯(lián)系；所以文獻[4-5]也存在相同的問題。同樣從在線階段考慮，文獻[6]提出基于支持向量機（support vector machine, SVM）分類與回歸的定位方法，其中SVM算法分類決策時僅考慮少量的支持向量，所以可以避免維數(shù)爆炸，且分類效果較好，在小數(shù)據(jù)集上表現(xiàn)優(yōu)秀；但是在實際運用中，真實的定位數(shù)據(jù)集規(guī)模通常很大，所以并不適合實際運用[7]。

因此考慮在線定位階段的定位區(qū)域分類效果和應用的普適性[8]，提出后驗加權貝葉斯（posteriorweighted Na?ve Bayes，PWNB）算法，結合定位數(shù)據(jù)自身特性為特征屬性分配適當?shù)臋嘀?，從?shù)據(jù)之間的關聯(lián)性考慮，能更有效地反映定位數(shù)據(jù)密度之間的真實關系，打破傳統(tǒng)算法基于獨立性假設的局限性。從定位實時性考慮，加入后驗概率估計過程可減小計算開銷、降低實際運用的延遲性。

1 基于WiFi電磁指紋庫定位方法

利用WiFi電磁指紋庫的定位方法主要分為離線階段和在線階段[9]。其中，離線階段主要使用相關設備采集定位環(huán)境區(qū)域內(nèi)WiFi的RSS數(shù)值，并對所采集到的數(shù)據(jù)做一定的處理，合理劃分，形成離線電磁指紋數(shù)據(jù)庫[10]。在線階段，對于進入定位區(qū)域內(nèi)的待定位目標，依據(jù)其獲得的RSS值與離線電磁指紋數(shù)據(jù)庫中的數(shù)值進行分類運算[11]，獲取該目標當前所處的位置信息。圖1為電磁指紋庫方法原理圖。

圖1 電磁指紋庫方法原理

2 樸素貝葉斯算法

樸素貝葉斯算法在很多實際應用中有著良好的效果，算法設計思想簡單，主要基于貝葉斯理論[12]，其表達式為

根據(jù)機器學習理論，樸素貝葉斯算法分類器主要分為訓練階段和測試階段：訓練階段的流程為

Input:定位數(shù)據(jù)集

3 后驗加權貝葉斯算法

由于傳統(tǒng)的樸素貝葉斯算法主要基于獨立性假設進行分類器的設計，但是現(xiàn)實中的定位數(shù)據(jù)之間必然存在一定的關聯(lián)性[15]；因此使用樸素貝葉斯分類器顯然并不合理。實際運用的室內(nèi)定位系統(tǒng)將會處理大量的定位數(shù)據(jù)集，并且為了保證良好的用戶體驗度，要求功能具有實時性，否則也將失去意義。根據(jù)傳統(tǒng)樸素貝葉斯算法的不足，提出改進加權貝葉斯算法，作出了以下2點改進。

3.1 增加后驗概率估計過程

圖2 傳統(tǒng)算法與改進算法區(qū)別

因此根據(jù)方差的波動程度，不同的定位分類單元根據(jù)自身對應的分類區(qū)域能夠有效區(qū)別自身的定位類型，減小了計算開銷，從宏觀上提升了定位的實時性。

3.2 依據(jù)特征屬性分配適當權值

真實的定位數(shù)據(jù)之間存在有效的關聯(lián)性，根據(jù)每個樣本屬性的貢獻程度為其分配適當?shù)臋嘀?，從而緩解了傳統(tǒng)樸素貝葉斯算法中主觀的獨立性假設。

考慮特征屬性之間的關聯(lián)，加入適當權重后的貝葉斯分類方法為

所以改進后的加權貝葉斯算法流程為：

Input: 定位數(shù)據(jù)樣本、標簽數(shù)據(jù)；

依式（4）、式（5）進行后驗概率估計；通過式（6）判別最大后驗概率

Output: 定位區(qū)域location

改進后的加權貝葉斯算法設計思路簡單，沒有增加復雜的公式計算。算法相比于樸素貝葉斯的獨立性假設，改進后的算法為相關的特征分配合適的權重，從數(shù)據(jù)之間的關聯(lián)性考慮更符合數(shù)據(jù)的真實意義，從而提高了定位的精準性。并且，加入后驗概率估計過程讓不同的定位分類單元能夠有效辨識自身分類元素特征，避免了對所有數(shù)據(jù)后驗概率重復性的計算，降低了計算開銷，從宏觀體驗上提高了定位的實時性。

4 實驗與結果分析

4.1 實驗設計

為了更好地驗證改進算法對于室內(nèi)定位的效果，本次實驗共采集986個WiFi電磁信號形成電磁指紋庫，連續(xù)采集100組數(shù)據(jù)，采集時間間隔為1 s，以1.5 m×1.5 m為基準劃分網(wǎng)格。其中實驗場地選自實訓樓走廊，如圖3所示。

圖3 實驗場地

為了便于對定位效果進行更好的分析，引入用于評判的誤差函數(shù)，其表達式為

4.2 實驗分析

本實驗利用本文所提出的PWNB算法同經(jīng)典的NB算法和SVM算法進行合理有效的對比，其中區(qū)域1~5如圖3所示，相關實驗數(shù)據(jù)如表1所示。

表1 實驗定位指紋數(shù)據(jù)

續(xù)表1

為了更好地分析上述算法在實際定位中的效果，實驗數(shù)據(jù)均經(jīng)過去噪、缺失值等預處理。實驗結果表明，所提出的PWNB算法相比于NB算法和SVM算法，在不同定位區(qū)域的定位性能有很大程度的提高。

圖4所示為定位誤差分析，提出的PWNB算法同經(jīng)典的NB算法相比，對于后驗概率的求解并未使用獨立性假設策略，而是充分考慮了定位數(shù)據(jù)特征屬性之間的相互影響，顯然更符合實際情況。SVM算法對于二分類的小數(shù)據(jù)集問題上表現(xiàn)優(yōu)異，但是對于實際中大量的定位數(shù)據(jù)進行多區(qū)域分類處理則顯得較為吃力；而PWNB算法主要依據(jù)統(tǒng)計的思想，針對大數(shù)據(jù)集反而能夠進一步提升其精確度。實驗表明PWNB算法有93.2%的定位誤差可控制在1.5 m范圍內(nèi)，而NB算法和SVM算法，誤差在1.5 m內(nèi)的定位誤差分別為53%和74%，顯然提出的PWNB算法效果最優(yōu)。

圖4 定位誤差分析

為了更進一步對上述3種算法在實際定位應用中進行效果的比較，特選取區(qū)域1中的位置，選擇50組定位序列進行仿真，結果如圖5所示。

經(jīng)過實驗分析，表明運用PWNB算法相比于NB算法精度提高了2.3 m，與SVM算法相比提高了1 m；所以提出的PWNB算法明顯優(yōu)于其他二者。

從定位在線階段的實時性進行分析，由于PWNB算法相比于傳統(tǒng)NB算法而言，加入了后驗概率估計過程；與相關特征屬性關聯(lián)的分類單元能夠有效識別是否為自身屬性，避免了對不屬于自身屬性的概率計算，從用戶定位體驗度來看，提高了定位的時效性。從圖6不同區(qū)域定位時間對比圖可以看到：PWNB算法平均定位時間均在14.6 s，SVM在針對大規(guī)模定位數(shù)據(jù)集處理時，需要將所有的數(shù)據(jù)一次性讀入內(nèi)存進行計算，顯然對設備性能有極高的要求，降低了定位的時效性，相比之下NB算法的計算開銷稍低。因此，從定位的時效性考究，PWNB算法性能最好。

圖5 定位結果誤差

圖6 不同區(qū)域定位時間對比

5 結束語

經(jīng)過以上算法分析和實驗總結，針對WiFi室內(nèi)定位的在線階段使用PWNB算法的定位性能明顯優(yōu)于同類的分類算法。結合后驗概率估計過程，讓針對不同定位特征屬性的分類單元發(fā)揮最優(yōu)效率，降低了計算開銷，提升了在線定位的時效性。同時，從定位數(shù)據(jù)的真實意義考慮，強調(diào)了定位數(shù)據(jù)之間的關聯(lián)性，更切合實際場景的運用。

[1] BAHL P, PADMANABHAN V N. RADAR: an in-building RF-based user location and tracking system[EB/OL]. [2018-08-28]. http://www.cs.columbia.edu/~drexel/CandExam/RADAR_in_building_RF.pdf.

[2] YOUSSEF M, AGRAWALA A. The Horus WLAN location determination system[EB/OL]. [2018-08-28]. https://www.cs.umd.edu/~moustafa/papers/horus_usenix.pdf.

[3] WANG Y, JIA X, LEE H K. An indoor wireless positioning system based on wireless local area network infrastructure [EB/OL].[2018-08-28]. http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.69.1364&rep=rep1&type=pdf.

[4] 郭菲菲. 基于貝葉斯學習的RFID室內(nèi)定位方法的研究[D].哈爾濱: 哈爾濱工業(yè)大學, 2008.

[5] 焦瑞強. 貝葉斯懲罰回歸中正則化參數(shù)的選擇[D]. 成都: 西南交通大學, 2017.

[6] 華海亮. 基于WiFi和藍牙的室內(nèi)定位技術研究[D]. 錦州: 遼寧工業(yè)大學, 2016.

[7] 朱榮, 白光偉, 沈航,等. 基于貝葉斯過濾法的CSI室內(nèi)定位方法[J].計算機工程與設計, 2015(3):567-571.

[8] 彭玉旭, 楊艷紅.一種基于RSSI的貝葉斯室內(nèi)定位算法[J].計算機工程, 2012, 38(10):237-240.

[9] 桑楠, 袁興中, 周瑞. 基于SVM分類和回歸的WiFi室內(nèi)定位方法[J].計算機應用研究, 2014, 31(6):1820-1823.

[10] 楊萌, 修春娣, 鄒坤,等.一種基于感知概率的室內(nèi)定位匹配算法[J]. 導航定位學報, 2014, 2(4):49-53.

[11] JOHN G H,LANGLEY P. Estimating continuous distributions in Bayesian classifiers[EB/OL].[2018-08-28]. http://web.cs.iastate.edu/~honavar/bayes-continuous.pdf.

[12] 雷雨偉, 修春娣, 楊威,等. WiFi與MEMS-IMU融合定位方法在室內(nèi)定位中的應用[J]. 導航定位學報, 2016, 4(4): 81-87.

[13] 李帥鑫，李廣云，符京楊，等. 室內(nèi)移動定位與測圖系統(tǒng)的高精度標定[J]. 導航定位學報, 2018, 6(3): 23-30．

[14] DAS K, WYMEERSCH H. Censoring for Bayesian cooperative positioning in dense wireless networks[J]. IEEE Journal on Selected Areas in Communications, 2012, 30(9): 1835-1842.

[15] OUYANG R W, WONG K S, LEA C T, et al. Indoor location estimation with reduced calibration exploiting unlabeled data via hybrid generative/discriminative learning[J]. IEEE Transactions on Mobile Computing, 2012, 11(11): 1613-1626.

WiFi indoor positioning based on posterior weighted Bayesian algorithm

HE Yang, WU Fei, ZHANG Yujin, ZHU Hai, CAI Wenyan

（School of Electronic and Electrical Engineering, Shanghai University of Engineering Science, Shanghai 201620, China）

Aiming at the problems that it is liable to subjectivity and limitations on the independence of positioning data samples and to large computational overhead in the online positioning stage of WiFi electromagnetic fingerprint library method for traditional Na?ve Bayes (NB) algorithm, the paper proposed a real-time localization method based on posterior weighted Na?ve Bayes (PWNB) algorithm: the feature attributes of the positioning data were assigned the appropriate weights by weighted NB considering the correlation between the positioning data; and further optimization was carried out, then the posterior probability estimation process was added to improve the real-time performance of the classifier according to the characteristics of the positioning data; finally the modified weighted Bayesian algorithm was compared with NB algorithm and spport vector machine (SVM) algorithm. Results showed that the proposed method could efficiently improve the real-time and the accuracy of the online positioning phase.

indoor positioning; attribute weight; posterior probability estimation process; real-time

P228

A

2095-4999(2019)03-0051-06

2018-10-22

國家自然科學基金資助項目（61272097）；上海市科技學術委員會重點項目（18511101600）；上海市自然科學基金項目（17ZR1411900）；上海市信息安全綜合管理技術研究重點實驗室項目（AGK2015006）；上海高校青年教師培養(yǎng)資助計劃項目（ZZGCD 15090）；上海工程技術大學科研啟動項目（2016-56）。

何洋(1995—)，男，安徽合肥人，碩士生，研究方向為無線定位。

吳飛（1967—），男，上海人，博士，教授，研究方向為計算機網(wǎng)絡與計算機能耗優(yōu)化。

何洋，吳飛，張玉金，等.后驗加權貝葉斯算法的WiFi室內(nèi)定位[J].導航定位學報,2019,7(3):51-56.（HE Yang, WU Fei, ZHANG Yujin,et al.WiFi indoor positioning based on posterior weighted Bayesian algorithm[J].Journal of Navigation and Positioning,2019,7(3):51-56.）

10.16547/j.cnki.10-1096.20190309.