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

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

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

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

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

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

室內(nèi)定位；屬性權(quán)值；后驗(yàn)概率估計(jì)過程；實(shí)時(shí)性

0 引言

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

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

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

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

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

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

圖1 電磁指紋庫方法原理

2 樸素貝葉斯算法

樸素貝葉斯算法在很多實(shí)際應(yīng)用中有著良好的效果，算法設(shè)計(jì)思想簡單，主要基于貝葉斯理論[12]，其表達(dá)式為

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

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

3 后驗(yàn)加權(quán)貝葉斯算法

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

3.1 增加后驗(yàn)概率估計(jì)過程

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

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

3.2 依據(jù)特征屬性分配適當(dāng)權(quán)值

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

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

所以改進(jìn)后的加權(quán)貝葉斯算法流程為：

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

依式（4）、式（5）進(jìn)行后驗(yàn)概率估計(jì)；通過式（6）判別最大后驗(yàn)概率

Output: 定位區(qū)域location

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

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

4.1 實(shí)驗(yàn)設(shè)計(jì)

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

圖3 實(shí)驗(yàn)場(chǎng)地

為了便于對(duì)定位效果進(jìn)行更好的分析，引入用于評(píng)判的誤差函數(shù)，其表達(dá)式為

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

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

表1 實(shí)驗(yàn)定位指紋數(shù)據(jù)

續(xù)表1

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

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

圖4 定位誤差分析

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

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

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

圖5 定位結(jié)果誤差

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

5 結(jié)束語

經(jīng)過以上算法分析和實(shí)驗(yàn)總結(jié)，針對(duì)WiFi室內(nèi)定位的在線階段使用PWNB算法的定位性能明顯優(yōu)于同類的分類算法。結(jié)合后驗(yàn)概率估計(jì)過程，讓針對(duì)不同定位特征屬性的分類單元發(fā)揮最優(yōu)效率，降低了計(jì)算開銷，提升了在線定位的時(shí)效性。同時(shí)，從定位數(shù)據(jù)的真實(shí)意義考慮，強(qiáng)調(diào)了定位數(shù)據(jù)之間的關(guān)聯(lián)性，更切合實(shí)際場(chǎng)景的運(yù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] 郭菲菲. 基于貝葉斯學(xué)習(xí)的RFID室內(nèi)定位方法的研究[D].哈爾濱: 哈爾濱工業(yè)大學(xué), 2008.

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

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

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

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

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

[10] 楊萌, 修春娣, 鄒坤,等.一種基于感知概率的室內(nèi)定位匹配算法[J]. 導(dǎo)航定位學(xué)報(bào), 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)定位中的應(yīng)用[J]. 導(dǎo)航定位學(xué)報(bào), 2016, 4(4): 81-87.

[13] 李帥鑫，李廣云，符京楊，等. 室內(nèi)移動(dòng)定位與測(cè)圖系統(tǒng)的高精度標(biāo)定[J]. 導(dǎo)航定位學(xué)報(bào), 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

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

何洋(1995—)，男，安徽合肥人，碩士生，研究方向?yàn)闊o線定位。

吳飛（1967—），男，上海人，博士，教授，研究方向?yàn)橛?jì)算機(jī)網(wǎng)絡(luò)與計(jì)算機(jī)能耗優(yōu)化。

何洋，吳飛，張玉金，等.后驗(yàn)加權(quán)貝葉斯算法的WiFi室內(nèi)定位[J].導(dǎo)航定位學(xué)報(bào),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.