后驗加權貝葉斯算法的WiFi室內定位

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

后驗加權貝葉斯算法的WiFi室內定位

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

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

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

室內定位；屬性權值；后驗概率估計過程；實時性

0 引言

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

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

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

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

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

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

圖1 電磁指紋庫方法原理

2 樸素貝葉斯算法

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

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

Input:定位數據集

3 后驗加權貝葉斯算法

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

3.1 增加后驗概率估計過程

圖2 傳統算法與改進算法區別

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

3.2 依據特征屬性分配適當權值

真實的定位數據之間存在有效的關聯性，根據每個樣本屬性的貢獻程度為其分配適當的權值，從而緩解了傳統樸素貝葉斯算法中主觀的獨立性假設。

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

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

Input: 定位數據樣本、標簽數據；

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

Output: 定位區域location

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

4 實驗與結果分析

4.1 實驗設計

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

圖3 實驗場地

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

4.2 實驗分析

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

表1 實驗定位指紋數據

續表1

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

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

圖4 定位誤差分析

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

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

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

圖5 定位結果誤差

圖6 不同區域定位時間對比

5 結束語

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

[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室內定位方法的研究[D].哈爾濱: 哈爾濱工業大學, 2008.

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

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

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

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

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

[10] 楊萌, 修春娣, 鄒坤,等.一種基于感知概率的室內定位匹配算法[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融合定位方法在室內定位中的應用[J]. 導航定位學報, 2016, 4(4): 81-87.

[13] 李帥鑫，李廣云，符京楊，等. 室內移動定位與測圖系統的高精度標定[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）；上海高校青年教師培養資助計劃項目（ZZGCD 15090）；上海工程技術大學科研啟動項目（2016-56）。

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

吳飛（1967—），男，上海人，博士，教授，研究方向為計算機網絡與計算機能耗優化。

何洋，吳飛，張玉金，等.后驗加權貝葉斯算法的WiFi室內定位[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.