基于iBeacon的商场室内定位及导航系统设计与实现

前晋， 陈淑荣

(上海海事大学 信息工程学院，上海 201306)

0 引言

随着商场、地下停车场、机场等大型室内场馆的兴建，手机室内定位及导航需求日趋强烈，如商场中基于位置信息给予用户手机特定的商品消息推送，地下停车场智能寻车，机场室内位置导航等。目前手机室内定位技术主要通过蓝牙iBeacon和Wi-Fi来实现，文献[1][2]使用Wi-Fi指纹定位算法，将接收Wi-Fi信号的RSSI值与已建立的指纹数据库进行对比实现定位；文献[3][4]使用iBeacon定位技术，首先建立iBeacon信号强度与距离之间的关系，再通过三边定位算法实现定位。以上两种定位技术均能满足商场室内定位精度需求，但商场人流较大，商铺位置易变动，导致Wi-Fi指纹库需要时常更新维护，人工成本较大，相比之下iBeacon技术更适用于商场环境。

导航是手机位置信息服务的一种，可转化为找寻定位点与目的地之间的最短可行路径。常用的路径规划算法包括Dijkstra算法、A*搜索算法、蚁群算法等。文献[5]指出Dijstra算法搜索全局空间，难以满足快速规划路径的需求，而通过改进A*算法建立平滑的A*模型,其性能优于蚁群算法，且能处理障碍物随机分布的复杂环境下的路径规划问题。可见A*算法更适用于障碍物较多的室内环境。

本文利用蓝牙iBeacon技术实现手机室内定位及导航功能，首先在室内部署ibeacon设备，测量室内环境中各点的RSSI值，得出信号强度与距离之间的关系，建立iBeacon距离-RSSI损耗模型；其次手机接收iBeacon的RSSI值，上传至服务器，利用上述模型和三边质心法计算手机位置坐标；服务器端按照用户输入的目的地，采用引入回退机制的A*算法计算最优路径，并在手机端自制的商场地图上标示最优导航路径。

1 系统概述

系统主要由3个部分组成：iBeacon设备、Android智能手机、服务器，如图1所示。

多个已知位置坐标的iBeacon部署在室内空间中，周期性地向外界广播信号。

手机应用由Android Studio开发环境搭建而成，其功能包括接收iBeacon信号并上传iBeacon的Major值及对应RSSI值至服务器；上传用户输入的目的地；接受返回信息并在室内地图标示当前位置；显示服务器返回的最优导航路径。

图1 系统结构

服务器由MyEclipse结合Apache Tomcat搭建而成，内部存储了iBeacon信息和地图信息，采用基于HTTP协议的doPost方式与手机端进行数据交互，功能包括接收手机端上传的RSSI值，运行iBeacon距离-RSSI损耗模型确定手机与iBeacon的距离；利用三边质心法计算手机位置坐标；接收输入的目的地信息，并运行引入回退机制的A*算法规划最优导航路径。

2 系统实现的关键技术

2.1 iBeacon室内定位

采用iBecaon进行室内定位，需先建立iBeacon距离-RSSI损耗模型，获取手机与最近的3个iBeacon之间的距离，再通过三边质心法计算手机位置坐标，实现定位。算法步骤如下：

第一步：RSSI值采集预处理。部署iBeacon应选取周围无遮挡物的位置降低信号损耗，在信号稳定后采集RSSI值以防其它信号干扰，减少环境误差；在同一地点采集多个RSSI值采用均值滤波预处理，以减少测量误差，如式(1)。

(1)

第二步：建立iBeacon距离-RSSI损耗模型。已有实验数据表明无线信号强度与距离存在对数关系[3-6]，如式(2)。

(2)

其中，PL(d)、PL(d0)分别表示无线信号在d和d0米处的信号强度损耗，n为环境变量因子，Xσ是方差为σ的正态随机分布，单位为dB。设d0=1 m， (2)式变为式(3)。

Rssi(d)=R1+10nlg(d)+Xσ

(3)

式中，Rssi(d)表示d米处的无线信号强度值，R1表示iBeacon与手机相距1 m时的无线信号强度值。距离d和信号强度Rssi(d)由实际测量得到，n和R1为模型的待定参数。

第三步：参数R1和n的最优估计。采用最小二乘法[7]，利用最小化误差的平方和寻找数据的最佳匹配函数，从而确定最优参数值。误差函数如式(4)。

(4)

(5)

其中α为梯度因子，取α=0.02，使J(R1,n)达到最小即可求得所需的R1和n。根据最优参数建立的iBeacon距离-RSSI损耗模型如式(6)。

(6)

将手机端接收的RSSI值代入式(6)即可得出手机与iBeacon的距离d。

第四步：获取手机位置坐标。采用三边质心法[6]，如图2所示。

图2 三边质心法计算手机坐标示意图

其中，A、B、C三点代表iBeacon设备位置，r1、r2、r3表示通过式(6)模型求得手机与离其最近的三个iBeacon设备的距离d。阴影三角形的三个顶点坐标分别为D(xd,yd)、E(xe,ye)、f(xf,yf)，三角形的质心坐标P(x,y)即为确定的手机位置坐标，如式(7)。

(7)

2.2 商场室内导航

导航作为室内位置服务的重要部分，实质是寻找定位点和用户搜索目的地之间的最短可行路径。如图3所示。

(a)

(b)

以上海正大广场1层为例，如图3(a)所示，导航算法步骤如下：

第一步：室内地图建模。将商场地图的所有可行走路径转化为节点图，如图3(b)所示。每一节点代表一个地点，线段代表可行路径。节点信息如下：

(1)N：整数型节点标识符，以数字形式标识节点。

(2) Floor：整数型楼层标识符，记录该节点楼层信息。

(3) Name：字符型，记录节点名称，一般为对应地图所在地名称。

(4)X、Y：double型，记录该节点对应地图所在位置的二维坐标值。

(5) Next：数组型，记录该节点可到达的下一个节点的N值。

以1节点为例，其中N=1，Floor=1，Name=“扶梯”，X=450，Y=330，Next=[2,3,4,5]。

第二步：建立最优路径搜索算法。在A*算法的基础上引入回退机制实现室内最优路径规划，流程如图4所示，其中p，q分别为手机定位点和用户输入的目的节点，path为路径节点集，close为已搜索节点集。搜索下一节点时，取出下一节点集Next中的所有值，若其属于close，则跳过，否则计算其评估函数f(n)[5]，并加入close；当遍历完Next中所有值后，将f(n)值最小的节点作为新的p，并加入到path中，依次循环，直至p=q后，输出最优路径集path。节点x的评估函数f(n)如式(8)。

f(n)=g(n)+h(n)

(8)

其中，g(n)表示初始节点p到节点x的代价函数，表示节点x到目的节点q的启发式函数，采用标准的曼哈顿距离，如式(9)。

h(n)=(|x1-x2|+|y1-y2|)

(9)

式中，x1、y1表示该节点x的二维坐标，x2、y2表示目的节点q的二维坐标。

第三步：引入回退机制的路径选取策略。在搜索节点时，会遇到死节点，即除了上一节点没有其它连接节点，如图3(b)中，若以1节点为p，6节点为q，根据传统的A*算法下一节点会选择4节点，此时4节点即死节点，为了应对这种异常情况，算法增加了回退机制，如图4中虚框所示。

遇到死节点时将已搜索节点集close回退到上一状态，并加入死节点，使再次搜索路径时忽略该节点，避免错误发生；另外将路径节点集中的末值赋给p，使p恢复到上一状态，从而实现回退过程。回退机制消除了死节点的影响，增加了算法运行的稳定性。

3 实验结果与分析

3.1 iBeacon距离-RSSI损耗模型参数选取实验

为确定模型的待定参数n和R1，在室内距离iBeacon设备0.1 m、0.7 m、1.3 m、1.9 m……处，选取13个点，按照定位算法步骤一对采集的RSSI值进行均值滤波，再根据步骤二运用最小二乘法选取最优参数，得出具体数值如式(10)。

(10)

为了验证参数选取的最优性，式(5)中误差函数J(R1,n)值的渐变情况如图5所示。

图4 最优路径搜索流程

图5 误差函数J(R1,n)的渐变图

可见当循环次数达到2 000次以上时，误差函数值已基本趋于平稳且接近于零，表明参数和的估计已达到最优。

为了验证模型的有效性，将建立的iBeacon距离-RSSI损耗模型曲线与实际测量数据进行对比，如图6所示。

图6 模型曲线与实际数据对比图

其中×点表示实际测量数据，图6中显示曲线能有效反映iBeacon信号强度与距离之间的关系。

由上可知，模型参数选取已达最优，建立的iBeacon距离-RSSI损耗模型有效可行。

3.2 定位实验

为了测量定位算法的误差，在5.4*16.2室内部署3个iBeacon设备，二维坐标分别为A(0,7.2)、B(2.7,0)、C(2.3,16.2)，单位为m。 随机选择30个采样点，将采集数据代入iBeacon距离-RSSI损耗模型，再根据定位步骤三计算出手机位置坐标，与实际测量的坐标数据比较，得出定位误差值如图7所示。

图7 手机室内定位误差图

其中最大定位误差在3米以内，且误差值在2米内有24次，定位精度较好。

10组实际坐标与模拟坐标的对比图，如图8所示。

图8 实际坐标与模拟坐标对比图

图中可以看出在定位点距离墙壁较近时，蓝牙信号发生反射，折射，产生多径效应[6]，定位误差较大，而在室内中心区域则定位误差较小。

以上10组定位算法计算总时间为6.777 s，平均每次定位算法实现时间为0.677 7 s，满足实时定位的需求。

3.3 商场室内导航实验

根据服务器计算的定位坐标，在手机端的商场地图上标示当前位置，当用户输入目的地，手机上传输入信息，服务器根据改进的A*导航算法规划出最优路径并返回至手机，结果如图9所示。

其中绿点代表起点，蓝点代表终点，红线标示为最优导航路径。

4 总结

针对商场手机定位和导航应用，首先通过实验建立iBeacon距离-RSSI损耗模型，利用三边质心法实现手机室内定位，在此基础上实现了C/S架构的商场室内手机定位导航系统。手机端通过接收iBeacon信号并上传服务器，后台运行定位算法，计算手机的位置信息；并按照用户输入的目的地址，运行路径搜索算法，返回最优可行路径，实现商场室内导航。实验结果表明，定位最大误差在3 m以内，导航路径精确，能满足大型室内场馆手机定位导航需求。

图9 最优导航路径结果图