一种基于商超WiFi环境的室内定位算法及实现

（中国科学技术大学，安徽 合肥230088）

一、引言

发过快递包裹或者有过线上购物经历的人都了解，快递信息是可以实时跟踪的，这是一套复杂的应用系统，其核心技术在于定位系统。在大型超市购物，通过手机可以实时查到各种商品的摆放位置，甚至能根据个人喜好收到商超的推荐产品，这种应用场景在万达部分区域已经实现了，其核心点也在于定位技术。常见的定位方式是通过卫星实现的，美国的全球卫星定位导航系统（GPS）最为知名，应用也最为广泛。欧洲有伽利略（GALILEO），俄罗斯有格罗纳斯（GLONASS），中国有北斗导航卫星。但是卫星定位具有一定的局限性，在民用领域，卫星定位具有首次定位缓慢，定位精度不高，难以逾越障碍物等缺陷。一方面由于受大气层等影响，信号衰减不一，会有一定误差；另一方面卫星信号易于被遮挡，信号波长难选，波长长了便于绕过障碍物，但是接收信号能力就会降低，波长短了，信号很容易被障碍物遮挡，就收不到信号了。本文通过讨论卫星定位原理，进而提出一种简便易行的室内定位算法，以期在商超这种特定的区域内实现精准定位。

二、三边测量（Silent River）原理及卫星定位应用

常见的定位的算法主要分为两类，基于测距技术的定位算法和距离无关的算法。基于测距技术的算法一般是通过节点之间的距离或者角度来计算出未知节点的位置。距离无关的算法有，质心法、APIT算法、凸规划算法等。这些算法都是利用节点之间的邻近关系实现定位的。一般来说，基于测距技术的算法比无需测距的精度要高，通讯卫星一般采用的是基于测距技术的定位算法。

从几何的角度来看，已知空间中三个点的位置为坐标 A(x1,y1,z1)，B(x2,y2,z2)，C(x3,y3,z3)和到到 D（x,y,z）的距离d1,d2,d3,求D点的坐标。用下面公式一即可，三个方程求三个未知数，能求出唯一解。

卫星定位原理用的也是三边测距算法，从原理上来说，只要用三个卫星就可以定位一个目标位置了。以个人智能手机为例，大多内置辅助全球卫星定位系统(A-GPS)，接收各个卫星发送的消息。接收的消息包含两种主要的信息，一是卫星的空间坐标，另一个就是卫星发送的时间。手机在接收到卫星发送消息后，通过比对手机自带的时间，就可以得出从卫星发送到手机端的时间差，通过这个时间差，就能计算出卫星距离手机的距离。通过下面公式看一下：

其中，di是卫星到手机的距离，Tm是手机端接收到消息的时间，Ts是卫星发送消息时间，C为光速。

在现实生活中，就存在很多问题，比如手机端时钟系统有误差，卫星在发送信息时会收到大气层气流的影响，到了地面接收点，会受到建筑物等障碍物的遮挡等。一般为了使得定位更为准确，把这些因素综合考虑进去，可以给出一个误差范围值。事实上，卫星定位也是这样做的。卫星到接收终端的距离，就变成了具有修正误差值的一个概念。把公式二做个简单的修改：

其中de为估算误差值。这样一来，三边测距的方程公式，就变成了如下公式四：

这样以来，三颗卫星就不能解决问题了，必须有最少有四颗卫星才能解决问题。GPS的空间部分是由24颗工作卫星组成，它位于距地表20200km的上空，均匀分布在6个轨道面上 (每个轨道面4颗),轨道倾角为55°[1]。这也是GPS每个轨道面有四颗卫星的主要原因。

图2　

在视野比较开阔的地带，一般终端能接收到大于四颗卫星的信号。原理上，有两种解决办法：一是，在这些卫星中挑选信号最好的四颗按照公式四计算出具体坐标；二是，能接收多少卫星消息，就使用多少卫星消息数据参与计算。公开的数据显示，GPS实际应用中，一般采用第二种方式，能在一定程度上提高计算的精度。

三、室内定位技术概述

卫星定位已经广泛应用于生活中的各个领域。运动导航，轨迹记录、大地测量、周边信息查询等。但是卫星定位的局限性和缺陷也比较明显，由于卫星导航需要搜星和进行匹配，首次定位缓慢；卫星定位的本质是需要依靠授时系统，其精度取决于发送端和接收端授时系统的精度，往往具有一定的误差，精度不高；接收端耗电量大也是卫星定位很大的一个缺陷；受限于信号波长，难以突破障碍物，因此室内卫星定位几乎难以发挥作用。上文提到的商超应用场景无法实现。如何解决封闭空间定位问题[2]，受到了越来越多的学者的关注，综合参考多种文献，大致有以下三种：

1、ZigBee室内定位技术通过若干个待定位的盲节点和一个已知位置的参考节点与网关之间形成组网，每个微小的盲节点之间相互协调通信以实现全部定位[3]。ZigBee具有功耗低，组网能力强，安全性高等优点。但是也有显著的缺陷，布局成本高，通信距离短，一般建议100米以内，虽然市面上有开发出1000米的产品模块，但是大大增加了功耗，违背了低功耗的基本宗旨，穿透性不好，障碍物厚度严重影响通讯距离。

2、UWB由于信号本身的特性，超宽带信号时间分辨力高，抗室内多径性能强，室内定位的精度很高，可到毫米级别，但是UWB系统成本很高，信号本身受到一定的功率限制和频谱约束，还存在与当前常用频谱信号之间的干扰问题。

3、RFID射频识别，成本低廉，但是不具备通信能力，抗干扰差，一般用于仓储货物管理。

除了上述的三种应用广泛的技术外，还有GPS、蓝牙、超声，红外、Wi-Fi、计算机视觉等室内定位技术，综合比较，其中以基于WiFi的室内定位技术最为突出，无论从硬件投入、软件投入、实施难度、可控性，还是定位效果方面考察，都是有优势的。

由于智能终端设备的广泛普及，加上各大商超的WiFi布局，基本成了常设基础设施。在商超现有的WiFi基础上，从卫星定位原理发散思考，基于测距的基本方法，用WiFi代替卫星，通过WiFi信号RSSI测距，进而实现室内定位，是一种不错的选择。一方面可以实现室内高精准定位，另一方面在投入成本上也能大幅度降低开支；再次，基于WiFi环境的室内定位能实现封闭区域的场景营销，也能解决上文提到的商超购物模拟场景。

四、基于商超WiFi环境的室内定位算法

商超内实现购物个性化服务，离不开两个要素，基于商超管理的软件（也可以是APP，本文以APP作为阐述对象），商超内基本固定的无线基础设施，也就是WiFi环境。商超APP在请求定位的时候，会需要WiFi信号。商超客户在使用手机时，会探测到周围各个WiFi，包含两个信息维度，一个是WiFi的标识（从实践来看，具有WiFi唯一标识度的，就是物理地址，又称MAC地址），一个是WiFi的信号强度（RSSI）[4]。这样各个 WiFi就构成了一个信号向量 （＜M1，R1＞＜M2，R3＞＜M3，R3＞...＜Mn，Rn＞）。服务端收到客户端请求后，会将信号向量传递给定位引擎，定位引擎结合这些信息返回给服务端定位结果，定位精度等信息，服务端再将结果返回给APP。这里定位引擎起到了关键作用。定位引擎的工作，决定了定位的精度，取决于两个方面，一个是大量的位置信号向量数据，另一个方面是采用的算法模型。本文重点讨论算法模型。其过程如下：

图3　

实现商超内客户精准定位的问题转化为在大量的位置信号信息中，找到一个点D，使得这个位置尽可能的精确。这也是数学模型中的概率论问题。这个适用于贝叶斯定理。已知给定信号向量m（＜M1，R1＞＜M2，R3＞＜M3，R3＞...＜Mn，Rn＞），求解一个点D，是这种可能性最大，公式如下：

这个公式直接求解的难度很大，通过贝叶斯转化一下,如公式六：

分母D(m)标识D在信号向量m中出现的概率，对于商超用户来说，这个是毋庸置疑的，可以忽略不计。那么该贝叶斯公式就可以转化为：

其中D(d)表示位置D出现的概率，D(m|d)表示在位置D出现信号向量m的概率。由于商超环境相比室外环境先对比较单一，为了简化起见，这里假设位置D出现的概率均等。那么公式七就可以转化为如下公式八：

Max(D(m|d))指的是在商超空间里找到一个点D，使得信号向量m出现的概率最大。由于商超空间有限，做到这点很容易。关于WiFi的物理位置，由于是商超环境，范围太小，加之无法找到足够精度的参考点，所以WiFi的物理位置无法使用GPS坐标，只能使用自定义坐标系，这里有2种选择：

1、以商超内的某一个点为参考原点，这样就可以人工测量WiFi相对原点的坐标，包含Z轴，单位是米，甚至可以更小为厘米。

2、以商超的建筑设计测绘图为参考，以WiFi在图中的像素位置为坐标，单位是1像素点。

第二种方法相对简便一些，通过电脑就可以实现，无需增加很大的工程量。在模拟测试中，采用的就是第二种方法。

图4　

因此max（D(m|d)）就转换为在地理空间找到一个像素点，使得信号向量m出现的概率最大。在商超内，由于各个WiFi信号独立，那么公式八可以转换为：

现在问题关键是求解D(wfi＝RSSIi|d)，即在网格d内，mac地址为Mi且信号强度为Ri出现的概率。这样就可以实现精准的定位了。

利用这种朴素贝叶斯算法的难点在于计算精度上，一方面定位的精度取决于WiFi的个数，WiFi信号的稳定程度；另一方面取决于区域面积大小，理论上用户来一个请求，需要遍历信号位置数据库每个像素点对应的概率，并将最大概率网格对应的中心点返回[5]。如果是大范围的应用，比如一个城市，一个小区，哪怕是精确到米级别，计算量都将是海量的。但在商超环境下，由于采用了固定的测绘图像素分割办法，这种计算的工作量很小。计算效率很高，基本可以实现精确度很高的定位。

五、基于商超WiFi环境的室内定位需要解决的问题

首先要建立一个基于商超WiFi环境的位置信号数据库,至少需要如下信息，WIFI的MAC地址，也就是标识,WIFI的物理位置 （基于区域划分的坐标位置）,WIFI的信号强度信息。

用一个简单的程序实现如下：

其次，上述数据库的建立，有个先决条件就是将商超物理地址网格化，由于地理位置空间有限，这里采用了利用建筑测绘图像素化的处理方法。

再次是选择定位算法选择，通过上文的讨论，利用朴素贝叶斯模型，可以在给定商超环境下实现精准的室内定位。

六、总结

室内定位技术的成为目前研究的热点，尤其实在电子商务应用领域，各种基于室内定位技术的应用不断涌现。在大型商超里借助室内导航软件，可以迅速的找到自己心仪的产品；商超管理者根据室内定位的具体位置，可以推送个性化的商品组合等等。甚至在大型商超里购物不用担心走丢这样尴尬的事情发生。这些应用服务于特定范围的消费者，将会极大提高用户的购物体验。虽然商用的室内定位技术已经出现了很多，但是寻求一种成本低廉，部署方便，精准度较高的室内定位技术将仍然是一项非常有意义的工作。