基于WIFI和隱馬爾可夫模型的室內(nèi)定位算法研究

王克會(huì)

摘 要： 移動(dòng)互聯(lián)網(wǎng)技術(shù)的快速發(fā)展，對(duì)移動(dòng)終端的定位方法不斷提出新的要求。由于傳統(tǒng)方法在功耗、精度、通用性方面不能兼顧，設(shè)計(jì)并實(shí)現(xiàn)了一種基于雙射線追蹤的室內(nèi)RSSI指紋空間模型，結(jié)合隱馬爾可夫模型預(yù)測(cè)來提高系統(tǒng)的精度的室內(nèi)定位算法。此方法可以實(shí)現(xiàn)不同設(shè)備無異化定位，有效地減小室內(nèi)環(huán)境帶來的不可知信號(hào)波動(dòng)產(chǎn)生的誤差。實(shí)驗(yàn)結(jié)果表明，該算法在保證低功耗的同時(shí)有效提高了定位精度。

關(guān)鍵詞： 基于位置的服務(wù)； 室內(nèi)定位； 接收信號(hào)強(qiáng)度指紋庫； 隱馬爾可夫模型； 射線追蹤

中圖分類號(hào)：TP319 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：1006-8228（2018）01-09-04

Research on indoor positioning algorithm based on WiFi and Hidden Markov Model

Wang Kehui

（College of Computer Science， Hangzhou Dianzi University， Hangzhou， Zhejiang 310018， China）

Abstract： The rapid development of mobile Internet technology has been putting forward new requirements for the positioning methods of mobile terminals. Because the traditional methods cannot take account of the power consumption， accuracy and universality， this paper designs and implements an indoor RSSI fingerprint spatial model based on dual ray tracing， combining with the Hidden Markov Model prediction to improve the accuracy of the system. This method can realize the non-alienation positioning of different devices， and effectively reduce the error caused by the unknowable signal fluctuation in the indoor environment. The experimental results show that the proposed algorithm can improve the positioning accuracy while ensuring low power consumption.

Key words： location-based service； indoor positioning； RSSI fingerprint library； Hidden Markov Model； ray tracing

0 引言

基于位置的服務(wù)（Location Based Service）隨著互聯(lián)網(wǎng)技術(shù)的發(fā)展得到飛速發(fā)展。目前最常用的移動(dòng)定位方式是GPS全球定位系統(tǒng)（Global Positioning System），定位精度較高，但功耗較大，當(dāng)處于室內(nèi)時(shí)有覆蓋不到的盲區(qū)。以手機(jī)為代表的移動(dòng)終端設(shè)備對(duì)低能耗要求越來越高[6]，雖然借助于陀螺儀和電子羅盤等傳感器可以實(shí)現(xiàn)輔助定位以降低 GPS 的能耗，但這樣將會(huì)限制其通用性[1]。利用WIFI網(wǎng)絡(luò)的信號(hào)強(qiáng)度信息，不需要額外的裝置，能耗低、盲區(qū)少，但定位精度和時(shí)效性上有待提高。馬爾科夫模型是用于建模軌跡的工具，遵循最近的位置歷史可預(yù)測(cè)未來方向的原則[2]。我們研究了馬爾科夫模型，用于描述和預(yù)測(cè)室內(nèi)空間中的人類運(yùn)動(dòng)。

本文在兼顧低能耗和定位精度的基礎(chǔ)上，提出了一種基于WIFI指紋庫和隱馬爾可夫模型（Hidden Markov Model，HMM）結(jié)合的高精度室內(nèi)定位算法。

1 系統(tǒng)結(jié)構(gòu)

此系統(tǒng)主要有Android客戶端和云服務(wù)器構(gòu)成，主要研究?jī)?nèi)容如下。

⑴ 分析傳統(tǒng)指紋庫定位缺陷，并提出基于射線追蹤的室內(nèi)RSSI指紋空間建模思路。

⑵ 結(jié)合隱馬爾可夫預(yù)測(cè)模型進(jìn)行定位。采用隱馬爾可夫預(yù)測(cè)模型和射線追蹤算法結(jié)合，從而提高定位精度。

⑶ 設(shè)計(jì)Android客戶端和服務(wù)器端。在Android采集RSSI指紋，上傳到云服務(wù)器，建立指紋數(shù)據(jù)庫，設(shè)計(jì)實(shí)現(xiàn)我們的定位算法，并在實(shí)際應(yīng)用中測(cè)試驗(yàn)證當(dāng)前定位系統(tǒng)的有效性。

2 基于射線追蹤的RSSI指紋模型

在基于RSSI位置指紋數(shù)據(jù)的WIFI室內(nèi)定位技術(shù)中，需要對(duì)當(dāng)前環(huán)境RSSI值進(jìn)行實(shí)際測(cè)量，構(gòu)建匹配指紋庫。但由于現(xiàn)場(chǎng)環(huán)境的改變或者采集點(diǎn)不夠全面容易使采集的RSSI樣本不具有代表性。本章分析無線電波能量變化，提出一種基于雙射線追蹤的室內(nèi)RSSI位置指紋空間建模思路。

2.1 無線電波能量傳播模型

麥克斯韋方程描述了電磁波的邊界條件和基本特性。要對(duì)實(shí)際傳輸中的電磁波傳輸模型進(jìn)行分析，就要有一些已知條件，例如天線高度、頻率等參數(shù)。最常用的是Friis公式，利用傳播距離，天線增益和波長(zhǎng)建立了發(fā)射端和接收端的無線電波能量關(guān)系。

⑴

Pr表示接收功率，Pt表示發(fā)射功率，r表示傳播距離，Gr表示接收天線增益，Gt表示發(fā)射天線增益，λ表示電磁波長(zhǎng)。

2.2 RSSI指紋數(shù)據(jù)庫雙射線追蹤建模endprint

在室內(nèi)環(huán)境中WIFI信號(hào)在轉(zhuǎn)播過程中路徑分為散射、衍射、反射、直射四種情況，如圖1所示。直射和單次反射信號(hào)是接收端WIFI信號(hào)的主要組成，衍射和散射信號(hào)微弱基本可以忽略。

RSSI雙射線追蹤模型：

WIFI信號(hào)的波段是厘米級(jí)別，由于高頻電磁波的波長(zhǎng)較短，信號(hào)的繞射能力較差而直線傳播特性較強(qiáng)，所以可以采用射線追蹤的方式計(jì)算信號(hào)強(qiáng)度。WIFI信號(hào)由磁場(chǎng)和電場(chǎng)能量構(gòu)成，根據(jù)麥克斯韋方程可以計(jì)算出傳播中信號(hào)磁場(chǎng)強(qiáng)度H和電場(chǎng)強(qiáng)度E。

⑵

其中|E|為電場(chǎng)強(qiáng)度的模，|H|是磁場(chǎng)強(qiáng)度的模，S是信號(hào)傳輸?shù)穆烦?，參?shù)k等于2π除以信號(hào)波長(zhǎng)，用于計(jì)算S的相位變化。由于信號(hào)強(qiáng)度與電磁波的相位和當(dāng)前振幅都有關(guān)，結(jié)合公式⑴信號(hào)能量與傳播距離關(guān)系，可以得到磁場(chǎng)強(qiáng)度和電場(chǎng)強(qiáng)度與直射路徑長(zhǎng)度及初始強(qiáng)度的關(guān)系如下，|E0|和|H0|為初始場(chǎng)強(qiáng)的模，λ為電磁波長(zhǎng)度。

⑶

WIFI信號(hào)強(qiáng)度可以使用電場(chǎng)或磁場(chǎng)強(qiáng)度的平方值來表示，所以直射路徑的接收信號(hào)強(qiáng)度RSSIdir可由下式計(jì)算得到，其中RSSI0是WIFI信號(hào)發(fā)射功率對(duì)應(yīng)的信號(hào)強(qiáng)度。

⑷

由于WIFI在室內(nèi)接收到信號(hào)強(qiáng)度主要由直射和單次反射信號(hào)組成，參考圖1中單次反射路徑，假設(shè)信號(hào)發(fā)射端和接收端坐標(biāo)分別為（xt，yt），（xr，yr），我們可以通過斯涅爾定律確定接收點(diǎn)的鏡像點(diǎn)（xt，-yt），如圖2所示。根據(jù)上述三點(diǎn)坐標(biāo)可以計(jì)算得到入射角：

⑸

信號(hào)經(jīng)過反射會(huì)損失部分能量，反射過程中能耗損失系數(shù)為γ（α）是關(guān)于入射角α的函數(shù)，從而，可以確定反射后接收端信號(hào)強(qiáng)度RSSIref。

⑹

根據(jù)電磁波發(fā)射理論，可以計(jì)算出損耗系數(shù)γ（α）

⑺

真空介電常量值，系數(shù)在天線垂直極化時(shí)等于，天線水平極化時(shí)等于1。εr是由反射面材料決定，其值為反射面材料的相對(duì)電容率。

根據(jù)上述直射路徑RSSI和反射路徑RSSI計(jì)算，可以得到雙射線追蹤法接收端RSSI計(jì)算公式：

⑻

根據(jù)場(chǎng)強(qiáng)疊加原理可知，WIFI信號(hào)接收端接收信號(hào)強(qiáng)度RSSIall為直射路徑、前、后、左、右、上、下單次反射路徑RSSI值之和：

⑼

3 隱馬爾科夫模型建立

隱馬爾可夫模型包含兩組狀態(tài)序列，一個(gè)狀態(tài)序列是不能直接觀測(cè)的，另外一個(gè)狀態(tài)序列是可觀測(cè)的狀態(tài)。當(dāng)一個(gè)可觀測(cè)狀態(tài)序列已知時(shí)，可以使用 Viterbi 算法來確定最優(yōu)的隱含狀態(tài)序列[3]。隱馬爾可夫模型一般用五元組{S，O，π，A，B}進(jìn)行描述，本文中提出的定位算法非常適合用隱馬爾可夫模型求解，模型元素如下：

S，將定位區(qū)域整體劃分成區(qū)域塊；

O，指手機(jī)檢測(cè)到的RSSI信號(hào)強(qiáng)度；

π，指初始時(shí)刻，用戶位于某個(gè)路段的概率；

A，指從一個(gè)路段到另一個(gè)路段的概率；

B，指在各路段上，出現(xiàn)各種信號(hào)強(qiáng)度的概率。

首先得到定位區(qū)域經(jīng)過劃分后的路徑集S，初始時(shí)刻位于各路徑的概率矩陣π，提前統(tǒng)計(jì)用戶常用路線，用戶在不同路段和路口的選擇差異，對(duì)路口繪制轉(zhuǎn)移狀態(tài)圖得到各路徑之間的轉(zhuǎn)移概率矩陣A，以及各路徑上出現(xiàn)各種信號(hào)強(qiáng)度的概率矩陣B的后，再給出一個(gè)使用終端設(shè)備觀測(cè)到的RSSI序列，利用Viterbi算法得出用戶最有可能走過的路徑序列，用戶的當(dāng)前位置就是最優(yōu)路徑序列的最后一個(gè)路徑所在位置。

3.1 區(qū)域劃分與路徑分段

將當(dāng)前定位區(qū)域劃分為足夠小的區(qū)域塊，把實(shí)際行人可以通過的位置分為兩種：樓廊和房間。對(duì)于走廊， 可以分成很多小路段，由于在交叉路口處行走方向可能會(huì)發(fā)生變化，所以需要作為某個(gè)路段的終點(diǎn)和另一個(gè)路段的起點(diǎn)。單個(gè)路段越長(zhǎng)，越有利于增大不同路段RSSI信號(hào)差異，但是如果路段太長(zhǎng)將會(huì)導(dǎo)致路段內(nèi)的估計(jì)誤差。對(duì)于房間可以按照網(wǎng)格劃分，同樣網(wǎng)格長(zhǎng)度也會(huì)影響定位精度。

3.2 各路段信號(hào)強(qiáng)度概率矩陣B構(gòu)建

建立信號(hào)強(qiáng)度概率矩陣B，需要在各路段上選多個(gè)點(diǎn)，借助雙射線追蹤模型分別測(cè)量RSSI值，根據(jù)數(shù)據(jù)得出信號(hào)強(qiáng)度直方圖，從而得到不同RSSI值概率，對(duì)所有路段進(jìn)行分析可得到矩陣B。

3.3 轉(zhuǎn)移矩陣A構(gòu)建

概率轉(zhuǎn)移矩陣是隱馬爾可夫模型中決定定位算法精度的重點(diǎn)。常用構(gòu)建轉(zhuǎn)移矩陣A的方法是假設(shè)各路段等概率轉(zhuǎn)移，但是這種方式忽略了個(gè)體的差異[4]。所以我們統(tǒng)計(jì)用戶常用路線，在不同路段和路口的選擇差異，繪制轉(zhuǎn)移狀態(tài)圖，建立不同的轉(zhuǎn)移矩陣。在定位階段，根據(jù)用戶所在路段自動(dòng)選擇采用哪種轉(zhuǎn)移矩陣。

3.4 算法流程

⑴ 劃分當(dāng)前環(huán)境路徑，從而確定隱藏狀態(tài)集S；

⑵ 統(tǒng)計(jì)用戶特定時(shí)間內(nèi)行走軌跡，確定用戶在各個(gè)路段之間的轉(zhuǎn)移概率矩陣A；

⑶ 初始概率矩陣的計(jì)算可以由得到；

⑷ 借助雙射線模型采集某個(gè)點(diǎn)的RSSI值，并對(duì)數(shù)據(jù)進(jìn)行處理；

⑸ 可以由Viterbi算法得到用戶目前最可能在的路段序列。

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

實(shí)驗(yàn)結(jié)果從三個(gè)方面對(duì)定位系統(tǒng)性能進(jìn)行評(píng)估。

⑴ 馬爾科夫鏈序列長(zhǎng)度影響

圖3展示了不同長(zhǎng)度的馬爾科夫鏈對(duì)定位的影響程度，最終可以得出結(jié)論在長(zhǎng)度為11時(shí)，相比而言，定位的準(zhǔn)確度最高。

⑵ 結(jié)合個(gè)人行為對(duì)定位精度影響

實(shí)驗(yàn)中首先選擇各相鄰路徑等概率轉(zhuǎn)移模型，建立不結(jié)合個(gè)人習(xí)慣的隱馬爾科夫模型。與結(jié)合個(gè)人路徑習(xí)慣的模型對(duì)比結(jié)果如圖4所示，可以得出結(jié)論，結(jié)合個(gè)人行為習(xí)慣的算法，在定位準(zhǔn)確度上有較大提高。

將本文基于雙射線空間模型和隱馬爾科夫模型的室內(nèi)定位算法與參考文獻(xiàn)[5]中算法精確度對(duì)比，如圖5所示[5]。本系統(tǒng)的定位精度最好可達(dá)到1.1米，準(zhǔn)確率有70%，這說明本系統(tǒng)具有很好的定位效果。

5 結(jié)束語

本文主要介紹了一種基于雙射線追蹤的室內(nèi)RSSI指紋空間模型，通過麥克斯韋方程組和Friis方程用以射線追蹤方式追蹤接收信號(hào)強(qiáng)度建立位置指紋數(shù)據(jù)庫結(jié)合隱馬爾可夫模型的室內(nèi)定位算法。此方法可以實(shí)現(xiàn)不同設(shè)備無異化定位并且通過隱馬爾可夫模型預(yù)測(cè)來提高系統(tǒng)的精度。實(shí)驗(yàn)結(jié)果表明該算法有效提高了定位精度，有助于普及室內(nèi)定位在學(xué)校、停車場(chǎng)、大型商場(chǎng)等公共場(chǎng)所的應(yīng)用，具有良好的應(yīng)用前景。

本文算法僅使用了軌跡數(shù)據(jù)信息，在移動(dòng)物體對(duì)信號(hào)的遮擋以及溫度等因素對(duì)WIFI信號(hào)傳輸?shù)挠绊懖⑽纯紤]，因此對(duì)定位精度還有待進(jìn)一步提高，將在未來的工作中進(jìn)行優(yōu)化。

參考文獻(xiàn)（References）：

[1] 汪苑，林錦國.幾種常用室內(nèi)定位技術(shù)的探討[J].中國儀器儀

表，2011.2：1005-2852

[2] Aditya Jitta， Arto Klami. Partially hidden Markov models

for privacy-preserving modeling of indoor trajectories，2017.

[3] Illhoe Hwang， Young Jae Jang. Process Mining to Discover

Shoppers' Pathways at a Fashion Retail Store Using a WiFi-Base Indoor Positioning System，IEEE，2017.

[4] 黃永鋒.基于煤礦環(huán)境下的兩層隱馬爾科夫模型定位方法研

究[D].東華大學(xué)碩士學(xué)位論文，2016.

[5] 沙學(xué)鋒.基于WiFi的室內(nèi)定位算法的設(shè)計(jì)與實(shí)現(xiàn)[J].大連理

工大學(xué)，2015.

[6] 路錦博.基于隱馬爾可夫模型的移動(dòng)終端定位算法[J].計(jì)算

機(jī)系統(tǒng)應(yīng)用，2017.8.endprint