王克会
摘 要： 移动互联网技术的快速发展，对移动终端的定位方法不断提出新的要求。由于传统方法在功耗、精度、通用性方面不能兼顾，设计并实现了一种基于双射线追踪的室内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
