一種改進(jìn)的位置指紋智能手機(jī)室內(nèi)定位算法

王忠民， 陳 振， 潘春華

(西安郵電大學(xué) 計(jì)算機(jī)學(xué)院, 陜西 西安 710121)

一種改進(jìn)的位置指紋智能手機(jī)室內(nèi)定位算法

王忠民， 陳 振， 潘春華

(西安郵電大學(xué) 計(jì)算機(jī)學(xué)院, 陜西 西安 710121)

為了減小智能手機(jī)現(xiàn)有室內(nèi)定位算法的時(shí)間復(fù)雜度和空間復(fù)雜度，提出一種將確定型算法和概率分布算法融合的智能手機(jī)室內(nèi)定位新方法。利用最近鄰算法選出K個(gè)最相近的位置點(diǎn)，然后采用貝葉斯算法將K個(gè)位置點(diǎn)中匹配概率最大的點(diǎn)作為最終的估計(jì)位置。在Android手機(jī)上分別采用3種方法進(jìn)行20組室內(nèi)對比定位實(shí)驗(yàn),并隨機(jī)選取10個(gè)位置進(jìn)行定位誤差對比實(shí)驗(yàn)，結(jié)果表明，新方法比貝葉斯算法的復(fù)雜度降低了Ο(4n/5)，比最近鄰算法的定位準(zhǔn)確率提高了約4%，且定位誤差較小。

位置指紋；智能手機(jī)；室內(nèi)定位；最近鄰算法；貝葉斯理論算法

全球定位系統(tǒng)GPS(Global Positioning System)是獲取室外位置的主要方式，然而在室內(nèi)環(huán)境下，由于衛(wèi)星信號(hào)受到建筑物的阻擋，GPS不能滿足室內(nèi)環(huán)境下的定位要求，因此室內(nèi)定位技術(shù)成為研究的熱點(diǎn)。現(xiàn)在室內(nèi)定位系統(tǒng)主要采用紅外、藍(lán)牙、WiFi、射頻識(shí)別等定位技術(shù)。由于基于WiFi室內(nèi)定位系統(tǒng)的成本低、傳輸速度快，方便部署，因此得到了廣泛的應(yīng)用。

隨著移動(dòng)互聯(lián)網(wǎng)的快速發(fā)展和智能手機(jī)的迅速普及，基于智能手機(jī)的室內(nèi)定位系統(tǒng)被廣泛應(yīng)用在旅游、醫(yī)療、民生、社交等領(lǐng)域。例如,在旅游景點(diǎn)或博物館內(nèi)，游客可以利用基于手機(jī)的自動(dòng)導(dǎo)航系統(tǒng)進(jìn)行參觀游玩。在購物商場，用戶可以借助手機(jī)的自動(dòng)導(dǎo)購系統(tǒng)來完成購物等[1]。

最早的基于WiFi的室內(nèi)定位系統(tǒng)是微軟公司開發(fā)的RADAR系統(tǒng)[2]，它采用指紋匹配方法，在指紋庫中保存參考位置點(diǎn)處的信號(hào)強(qiáng)度均值，計(jì)算實(shí)際接收信號(hào)強(qiáng)度與指紋庫中所有信號(hào)值的歐氏距離，選取距離最小的位置點(diǎn)作為估計(jì)位置。瑪麗蘭大學(xué)的Horus系統(tǒng)[3]是在指紋庫中建立概率模型，在定位階段計(jì)算與指紋庫中的匹配概率達(dá)到定位的目的。文[4]研究了幾種基于信號(hào)強(qiáng)度的定位算法，分析了每種定位算法的優(yōu)缺點(diǎn)，并指出了未來定位算法的研究方向。文[5]對面向智能手機(jī)的室內(nèi)定位技術(shù)進(jìn)行了分析探討，并利用圖像識(shí)別和運(yùn)動(dòng)檢測等方法在室內(nèi)進(jìn)行了準(zhǔn)確地定位。RADAR系統(tǒng)的定位方法簡單，但是定位精度較低；Horus系統(tǒng)雖然定位精度高，但是算法復(fù)雜度也比較高，不適合應(yīng)用于資源有限的手機(jī)上。利用圖像和運(yùn)動(dòng)檢測的方法進(jìn)行定位容易受到視線的限制。

本文研究基于智能手機(jī)的室內(nèi)定位方法，為了保證足夠的定位精度，又能減少手機(jī)的資源消耗，在分析現(xiàn)有基于位置指紋的室內(nèi)定位算法的基礎(chǔ)上，提出一種將確定型算法和概率分布算法融合的智能手機(jī)室內(nèi)定位新方法,并通過對比實(shí)驗(yàn)對該方法進(jìn)行驗(yàn)證。

1 基于位置指紋的定位原理

基于位置指紋[4]的定位過程如圖1所示，其中AP1，AP2，AP3表示3個(gè)位置的無線路由，(x,y)|(RSS1,RSS2,RSS3)表示位置點(diǎn)(x,y)處收到的3個(gè)無線路由的信號(hào)強(qiáng)度。

圖1 基于位置指紋的定位原理

位置指紋法分為離線指紋庫構(gòu)建階段和在線定位階段。離線指紋庫構(gòu)建階段是在定位區(qū)域內(nèi)選取若干參考點(diǎn)，收集參考點(diǎn)的信號(hào)強(qiáng)度與位置信息來構(gòu)建指紋庫。在線定位階段通過實(shí)時(shí)采集到的信號(hào)強(qiáng)度值，利用定位算法將其與指紋庫中的數(shù)據(jù)進(jìn)行匹配、比較，進(jìn)而得到待定位點(diǎn)的估計(jì)位置。位置指紋法常用的定位方法主要有兩種：確定型方法和概率分布法。確定型方法是在指紋庫中保存一定時(shí)間段內(nèi)信號(hào)強(qiáng)度的平均值，將實(shí)時(shí)收集到的接收信號(hào)強(qiáng)度批示(Received Signal Strength Indication, RSSI)與指紋庫中數(shù)據(jù)進(jìn)行匹配、比較，通常選擇歐氏距離較小的幾個(gè)位置點(diǎn)的質(zhì)心作為估計(jì)位置。概率分布法是在指紋庫中保存一定時(shí)間內(nèi)信號(hào)強(qiáng)度的概率分布，采用貝葉斯方法計(jì)算位置點(diǎn)的后驗(yàn)概率，取概率最大的點(diǎn)作為估計(jì)位置。確定型方法簡單，實(shí)現(xiàn)更方便，但是定位精度較低；概率法實(shí)現(xiàn)較復(fù)雜，但是抗干擾性能較好，精度較高。

2 定位算法

2.1 最近鄰算法

最近鄰算法(K-nearest neighbor, KNN)是一種確定型的定位算法[6]。通常在指紋庫中保存每個(gè)位置點(diǎn)在一定時(shí)間段內(nèi)接收到的無線訪問節(jié)點(diǎn)(Access Point, AP)信號(hào)強(qiáng)度均值作為該點(diǎn)的特征值，定位階段計(jì)算實(shí)際接收信號(hào)強(qiáng)度與指紋庫中各個(gè)位置點(diǎn)的歐氏距離，取距離較小的K個(gè)位置點(diǎn)的平均坐標(biāo)或者加權(quán)位置坐標(biāo)[7]作為估計(jì)位置。當(dāng)K=1時(shí)，就是最近鄰算法，即選取歐氏距離

2.2 貝葉斯算法

由于室內(nèi)環(huán)境復(fù)雜多變，人群密集程度，人的隨意行為，門的開關(guān)，物體擺放位置的變化都會(huì)影響WiFi信號(hào)的強(qiáng)度，導(dǎo)致同一點(diǎn)處的信號(hào)強(qiáng)度值并不是一個(gè)恒定的值，而是在一個(gè)值附近波動(dòng)。在同一點(diǎn)連續(xù)采集100組信號(hào)強(qiáng)度值的統(tǒng)計(jì)直方圖如圖2所示。

圖2 接收信號(hào)強(qiáng)度的統(tǒng)計(jì)直方圖

同一位置的信號(hào)強(qiáng)度分布可以近似用高斯概率分布描述[8-9]，即其概率密度函數(shù)可表示為

其中x表示實(shí)際接收信號(hào)強(qiáng)度值，μ表示信號(hào)強(qiáng)度均值，σ表示標(biāo)準(zhǔn)偏差。

在線定位階段，根據(jù)實(shí)際收到的信號(hào)強(qiáng)度S(RSSI1,RSSI2,…,RSSIn)計(jì)算在每個(gè)參考點(diǎn)Wi的后驗(yàn)概率p(Wi|S),根據(jù)貝葉斯定理可得

其中p(S|Wi)為在已知位置處信號(hào)強(qiáng)度的概率,p(Wi) 稱為位置Wi的先驗(yàn)概率，由于用戶可能出現(xiàn)在定位區(qū)域的任意位置，因此可以認(rèn)為每個(gè)位置出現(xiàn)的概率相等。在同一位置能夠接收到多個(gè)AP的信號(hào)，而不同AP間的信號(hào)強(qiáng)度之間是獨(dú)立不相關(guān)的，不存在相互干擾[10]。因此 可以采用聯(lián)合概率分布函數(shù)描述為

p(S|Wi)=p(S1|Wi)p(S2|Wi)…p(Sn|Wi)。

最后選取后驗(yàn)概率最大的點(diǎn)作為最終的估計(jì)位置。

2.3 改進(jìn)算法

KNN算法雖然實(shí)現(xiàn)簡單，但是定位精度較低。貝葉斯算法定位精度高，但是計(jì)算比較復(fù)雜。在現(xiàn)有智能手機(jī)終端資源有限的情況下，為了能夠達(dá)到理想的定位效果，又能降低算法的復(fù)雜度、資源消耗以及存儲(chǔ)空間，將KNN算法和貝葉斯理論算法進(jìn)行融合。先通過KNN算法選取與待定位點(diǎn)距離較小的K個(gè)位置點(diǎn)，縮小下一步的搜索范圍，然后利用貝葉斯算法分別計(jì)算優(yōu)選出來的這K個(gè)位置點(diǎn)的匹配概率，選取概率最大的點(diǎn)作為最終的估計(jì)位置。算法偽碼如下。

Input： L(RSSI1,RSSI2,…,RSSIn)

For each Li(i=1,2…m)

Calculate Euclidean distance d[i]

End ForSelect the minimum distance of K positions L1,L2,…,LK

For i=1,2，…，K

Calculate the matching probability p(Wi|S) that L and the K positions according to Bayesian theory algorithm

End ForReturn Liwhere max p(Wi|S)

3 實(shí)驗(yàn)

實(shí)驗(yàn)在如圖3所示的室內(nèi)環(huán)境下進(jìn)行，圖3示三角形位置上布置3個(gè)無線路由，使用的是TP-LINK無線路由，定位實(shí)驗(yàn)所用終端設(shè)備是華為Android手機(jī)。

圖3 室內(nèi)環(huán)境結(jié)構(gòu)

在同一位置點(diǎn)同時(shí)采集3個(gè)路由的信號(hào)強(qiáng)度，連續(xù)采集25s信號(hào)強(qiáng)度值，如圖4所示。

圖4 同一位置點(diǎn)3個(gè)路由的接收信號(hào)強(qiáng)度

采集信號(hào)初始10 s內(nèi)信號(hào)波動(dòng)比較大[10]，之后便趨于相對穩(wěn)定的狀態(tài)，因此忽略前10 s的信號(hào)值，可以減小信號(hào)波動(dòng)對信號(hào)特征的影響。

離線階段，在走廊上共設(shè)置20個(gè)位置參考點(diǎn)，如圖3中的黑點(diǎn)所示，相鄰間隔約為1.5 m。用手機(jī)在每個(gè)參考點(diǎn)同時(shí)采集3個(gè)無線路由的信號(hào)強(qiáng)度，連續(xù)采集100 s，每秒采集一組數(shù)據(jù)，忽略前10 s的信號(hào)，求出該時(shí)間段內(nèi)的信號(hào)強(qiáng)度均值和標(biāo)準(zhǔn)偏差，連同位置坐標(biāo)一起構(gòu)建位置指紋庫

定位階段，首先分別采用文中所述三種算法進(jìn)行對比定位實(shí)驗(yàn)，在實(shí)驗(yàn)區(qū)域每個(gè)參考位置點(diǎn)分別測試3次，計(jì)算準(zhǔn)確率，結(jié)果如圖5所示。再隨機(jī)選取10個(gè)非參考位置點(diǎn)計(jì)算定位誤差，誤差結(jié)果如圖6所示。

圖5 實(shí)驗(yàn)結(jié)果

圖6 定位誤差比較

貝葉斯理論算法涉及到的參數(shù)多，計(jì)算復(fù)雜，如果只采用貝葉斯算法，需要在m個(gè)位置點(diǎn)分別計(jì)算n個(gè)AP信號(hào)強(qiáng)度的概率，然后再計(jì)算每個(gè)位置點(diǎn)的聯(lián)合概率，復(fù)雜度為Ο(mn)。而融合后的算法只需要計(jì)算優(yōu)選出來的K(K

4 結(jié)束語

分析基于位置指紋的室內(nèi)定位算法，提出將KNN算法和貝葉斯理論算法融合的智能手機(jī)室內(nèi)定位新方法，融合后的定位算法在保證一定的定位精度前提下，既可降低算法的復(fù)雜度，又可減少手機(jī)終端的資源消耗。實(shí)驗(yàn)結(jié)果證明，融合后的算法定位準(zhǔn)確率高于最近鄰算法，比貝葉斯算法的復(fù)雜度低，而且定位誤差較小，具有一定的優(yōu)勢。

[1] 王忠民,史育蘭,張榮,等. 一種移動(dòng)智能搜索個(gè)性化客戶端[J].西安郵電大學(xué)學(xué)報(bào)，2013，18(3)：71-75.

[2] Bahl P, Padmanabhan V N. Radar: An In-Building RF-based User Location and Tracking System[C]//Proceeding of IEEE INFOCOM. Israel: IEEE, 2000: 775-789.

[3] Youssef M, Agrawala A. The Horus WLAN Location Determination System[C/OL].(2011-12-12)[2013-08-10]. http://www.docin.com/p-305713112.html.

[4] 張明華,張申生,曹健.無線局域網(wǎng)中基于信號(hào)強(qiáng)度的室內(nèi)定位[J].計(jì)算機(jī)科學(xué),2007,34(6):68-71.

[5] 婁路.面向移動(dòng)LBS的智能手機(jī)室內(nèi)定位技術(shù)探討[J].電信科學(xué),2012(6):98-103.

[6] Xiao Chubing, Huang Junyuan, Wei Liqiong. Research on the KNN-Based Location Algorithm for WLAN Indoor Location Method[C]//International Conference on Engineering and Business Management(EBM2012). Shanghai, China, 2012:3430-3433.

[7] 雷地球,羅海勇,劉曉明.一種基于WiFi的室內(nèi)定位系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)[C/OL]//.(2011-09-21)[2013-08-10]. http://www.doc88.com/p-60999153239.html.

[8] 何強(qiáng),劉軍發(fā),陳益強(qiáng).基于歷史路徑概率匹配的室內(nèi)定位方法[J].微計(jì)算機(jī)信息，2010，26(31): 220-222.

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

[10] 張明華.基于WLAN的室內(nèi)定位技術(shù)研究[D].上海：上海交通大學(xué)，2009：54-64.

[責(zé)任編輯:王輝]

Improved fingerprinting algorithm for
smart phone indoor positioning

WANG Zhongmin， CHEN Zhen， PAN Chunhua

(School of Computer Science and Technology, Xi’an University of Posts and Telecommunications, Xi’an 710121, China)

In order to reduce the time complexity and space complexity of smartphone indoor positioning algorithm, a new method of smartphone indoor positioning is proposed in this paper. This method combines the deterministic algorithm and the probability distribution algorithm together. By using theK-Nearest Neighbor algorithm to selectKpoints which are nearest in position and then using the Bayesian algorithm to make the maximum matching probability point inKpoints, the final position is estimated. Three contrast methods are used on 20 groups in indoor positioning experiments respectively on Android mobile phone. Ten positions are then selected randomly for positioning error comparison experiment. The results show that the new method has the lower algorithm complexity ofΟ(4n/5) than the Bayesian algorithm, and that the positioning accuracy has increased 4% than theK-nearest neighbor algorithm. It also has a small position error.

fingerprinting, smart phone, indoor positioning,K-nearest neighbor algorithm, Bayesian theory algorithm

10.13682/j.issn.2095-6533.2014.01.003

2013-09-13

國家自然科學(xué)基金資助項(xiàng)目(61100166)，陜西省教育廳產(chǎn)業(yè)化培育基金資助項(xiàng)目(2012JC22)

王忠民(1967- )，男，博士，教授, 從事智能信息處理研究。E-mail:wzm_678@163.com 陳振(1989- )，男，碩士研究生，研究方向?yàn)榍度胧较到y(tǒng)設(shè)計(jì)與開發(fā)。E-mail：243571594@qq.com

TP301.5

A

2095-6533(2014)01-0017-04