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

王克會

摘 要： 移動互聯網技術的快速發展，對移動終端的定位方法不斷提出新的要求。由于傳統方法在功耗、精度、通用性方面不能兼顧，設計并實現了一種基于雙射線追蹤的室內RSSI指紋空間模型，結合隱馬爾可夫模型預測來提高系統的精度的室內定位算法。此方法可以實現不同設備無異化定位，有效地減小室內環境帶來的不可知信號波動產生的誤差。實驗結果表明，該算法在保證低功耗的同時有效提高了定位精度。

關鍵詞： 基于位置的服務； 室內定位； 接收信號強度指紋庫； 隱馬爾可夫模型； 射線追蹤

中圖分類號：TP319 文獻標志碼：A 文章編號：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 引言

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

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

1 系統結構

此系統主要有Android客戶端和云服務器構成，主要研究內容如下。

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

⑵ 結合隱馬爾可夫預測模型進行定位。采用隱馬爾可夫預測模型和射線追蹤算法結合，從而提高定位精度。

⑶ 設計Android客戶端和服務器端。在Android采集RSSI指紋，上傳到云服務器，建立指紋數據庫，設計實現我們的定位算法，并在實際應用中測試驗證當前定位系統的有效性。

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

在基于RSSI位置指紋數據的WIFI室內定位技術中，需要對當前環境RSSI值進行實際測量，構建匹配指紋庫。但由于現場環境的改變或者采集點不夠全面容易使采集的RSSI樣本不具有代表性。本章分析無線電波能量變化，提出一種基于雙射線追蹤的室內RSSI位置指紋空間建模思路。

2.1 無線電波能量傳播模型

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

⑴

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

2.2 RSSI指紋數據庫雙射線追蹤建模endprint

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

RSSI雙射線追蹤模型：

WIFI信號的波段是厘米級別，由于高頻電磁波的波長較短，信號的繞射能力較差而直線傳播特性較強，所以可以采用射線追蹤的方式計算信號強度。WIFI信號由磁場和電場能量構成，根據麥克斯韋方程可以計算出傳播中信號磁場強度H和電場強度E。

⑵

其中|E|為電場強度的模，|H|是磁場強度的模，S是信號傳輸的路程，參數k等于2π除以信號波長，用于計算S的相位變化。由于信號強度與電磁波的相位和當前振幅都有關，結合公式⑴信號能量與傳播距離關系，可以得到磁場強度和電場強度與直射路徑長度及初始強度的關系如下，|E0|和|H0|為初始場強的模，λ為電磁波長度。

⑶

WIFI信號強度可以使用電場或磁場強度的平方值來表示，所以直射路徑的接收信號強度RSSIdir可由下式計算得到，其中RSSI0是WIFI信號發射功率對應的信號強度。

⑷

由于WIFI在室內接收到信號強度主要由直射和單次反射信號組成，參考圖1中單次反射路徑，假設信號發射端和接收端坐標分別為（xt，yt），（xr，yr），我們可以通過斯涅爾定律確定接收點的鏡像點（xt，-yt），如圖2所示。根據上述三點坐標可以計算得到入射角：

⑸

信號經過反射會損失部分能量，反射過程中能耗損失系數為γ（α）是關于入射角α的函數，從而，可以確定反射后接收端信號強度RSSIref。

⑹

根據電磁波發射理論，可以計算出損耗系數γ（α）

⑺

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

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

⑻

根據場強疊加原理可知，WIFI信號接收端接收信號強度RSSIall為直射路徑、前、后、左、右、上、下單次反射路徑RSSI值之和：

⑼

3 隱馬爾科夫模型建立

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

S，將定位區域整體劃分成區域塊；

O，指手機檢測到的RSSI信號強度；

π，指初始時刻，用戶位于某個路段的概率；

A，指從一個路段到另一個路段的概率；

B，指在各路段上，出現各種信號強度的概率。

首先得到定位區域經過劃分后的路徑集S，初始時刻位于各路徑的概率矩陣π，提前統計用戶常用路線，用戶在不同路段和路口的選擇差異，對路口繪制轉移狀態圖得到各路徑之間的轉移概率矩陣A，以及各路徑上出現各種信號強度的概率矩陣B的后，再給出一個使用終端設備觀測到的RSSI序列，利用Viterbi算法得出用戶最有可能走過的路徑序列，用戶的當前位置就是最優路徑序列的最后一個路徑所在位置。

3.1 區域劃分與路徑分段

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

3.2 各路段信號強度概率矩陣B構建

建立信號強度概率矩陣B，需要在各路段上選多個點，借助雙射線追蹤模型分別測量RSSI值，根據數據得出信號強度直方圖，從而得到不同RSSI值概率，對所有路段進行分析可得到矩陣B。

3.3 轉移矩陣A構建

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

3.4 算法流程

⑴ 劃分當前環境路徑，從而確定隱藏狀態集S；

⑵ 統計用戶特定時間內行走軌跡，確定用戶在各個路段之間的轉移概率矩陣A；

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

⑷ 借助雙射線模型采集某個點的RSSI值，并對數據進行處理；

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

4 實驗結果分析

實驗結果從三個方面對定位系統性能進行評估。

⑴ 馬爾科夫鏈序列長度影響

圖3展示了不同長度的馬爾科夫鏈對定位的影響程度，最終可以得出結論在長度為11時，相比而言，定位的準確度最高。

⑵ 結合個人行為對定位精度影響

實驗中首先選擇各相鄰路徑等概率轉移模型，建立不結合個人習慣的隱馬爾科夫模型。與結合個人路徑習慣的模型對比結果如圖4所示，可以得出結論，結合個人行為習慣的算法，在定位準確度上有較大提高。

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

5 結束語

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

本文算法僅使用了軌跡數據信息，在移動物體對信號的遮擋以及溫度等因素對WIFI信號傳輸的影響并未考慮，因此對定位精度還有待進一步提高，將在未來的工作中進行優化。

參考文獻（References）：

[1] 汪苑，林錦國.幾種常用室內定位技術的探討[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] 黃永鋒.基于煤礦環境下的兩層隱馬爾科夫模型定位方法研

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

[5] 沙學鋒.基于WiFi的室內定位算法的設計與實現[J].大連理

工大學，2015.

[6] 路錦博.基于隱馬爾可夫模型的移動終端定位算法[J].計算

機系統應用，2017.8.endprint