室内定位算法那些事儿总览

随着数据业务和多媒体业务的快速增加，人们对定位与导航的需求日益增大，尤其在复杂的室内环境，如机场大厅、展厅、仓库、超市、图书馆、地下停车场、矿井等环境中，常常需要确定移动终端或其持有者、设施与物品在室内的位置信息。但是受定位时间、定位精度以及复杂室内环境等条件的限制，比较完善的定位技术目前还无法很好地利用。因此，专家学者提出了许多室内定位技术解决方案，如A-GPS定位技术、超声波定位技术、蓝牙技术、红外线技术、射频识别技术、超宽带技术、无线局域网络、光跟踪定位技术，以及图像分析、信标定位、计算机视觉定位技术等等。这些室内定位技术从总体上可归纳为几类，即GNSS技术(如伪卫星等)，无线定位技术(WiFi、BLE、RFID、ZigBee、UWB、红外、超声、地磁、激光、LED、地磁、光跟踪技术等)，其它定位技术(计算机视觉、航位推算等)，以及GNSS和无线定位组合的定位技术(A-GPS或A-GNSS)。

由于在室内环境下对于不同的建筑物而言，室内布置，材料结构，建筑物尺度的不同导致了信号的路径损耗很大，与此同时，建筑物的内在结构会引起信号的反射，绕射，折射和散射，形成多径现象，使得接收信号的幅度，相位和到达时间发生变化，造成信号的损失，定位的难度大。虽然室内定位是定位技术的一种，和室外的无线定位技术相比有一定的共性，但是室内环境的复杂性和对定位精度和安全性的特殊要求，使得室内无线定位技术有着不同于普通定位系统的鲜明特点，而且这些特点是户外定位技术所不具备的。因此，两者区域的标识和划分标准是不同的。基于室内定位的诸多特点，室内定位技术和定位算法已成为各国科技工作者研究的热点。如何提高定位精度仍将是今后研究的重点。

其实，WiFi、BLE、RFID、ZigBee、UWB同属于802.11协议，定位原理完全类似，算法也类似，下面我们就着重介绍一下这五种定位技术的主流算法，定位算法根据定位过程中所需信息的不同可分为两大类：

•  基于测距(range—based)

•   测距无关(range—free)

先说说测距无关(range—free)的算法

从字面上就能判断，其实就是无需确定距离和角度信息，仅根据网络对通性等信息加以实现。主要算法有：

1. 质心算法;

2. APIT(approximate point-in-triangulation teat)               近似三角形内点测试法

3. DV-Hop

再接着介绍基于测距(range—based)的算法，故名思议就是通过测量节点问点到点的距离或角度信息，使用三边测量法、三角测量法或最大似然估计法计算节点位置。主要算法有：

TOA(time of arrival)

TDOA(Time Difference 0f Arrival)

AOA(Angle of Arrival )

RSSI(Received Signal Strength Indication)

下面我们着重介绍一下“路索”智能室内定位引擎主要采用的RSSI算法。

无线电信号强度，又称RSSI(Radio Signal Strength Indicator)。已知发射功率，接受节点通过接收功率，计算传播损耗，再通过理论或者经验的传播模型将传播损耗转换为距离。在自由空间中，距发射d处的天线接收到的信号强度由下面的公式给出：

式中，d为接收端与发射端之间的距离( m)；d0为参考距离( m)，一般取1 m；Pr(d)是接收端的接收信号功率(dBm)；Pr(d0)是参考距离d0点对应的接收信号功率(dBm)； XdBm是一个平均值为0的高斯随机变量(dBm)，反映了当距离一定时，接收信号功率的变化；n为路径损耗指数，是一个与环境相关的值。通过测量接收信号的强度，利用这个公式即可计算收发节点之间的大概距离。一旦可以得到参考节点与未知节点之间的距离信息，就可以采用三边测量法或者最大似然估计法计算出未知节点的位置。在三维空间中，三边测量法指的己知一个未知节点到三个以上参考节点的距离，就可以确定该点的坐标;三边测量法在二维空间里可以用几何图形表示为:当得到未知节点到一个参考节点的距离时，就可以确定，此未知节点在以此参考节点为圆心，以距离为半径的圆上;如果得到未知节点到3个参考节点的距离，则3个圆的交点就是该未知节点的位置。

n的几种典型值

RSSI值采集

由于无线信号的非线性时变特性,在同一个点不同时刻采集到的信号强度值是不同的，并且无法判断哪一个值较为准确。在距离发射端1m远处的接受端采集100次信号，对结果进行分析，见下图。

由上图可见，即使在同一点，采集到的RSSI值也有很大的不同。但基本都在一个范围内波动。由于采集信号的随机性，采集的RSSI参数并不能直接用于运算，需要对其进行处理。方法有：

1.均值法

2.高斯分布法

节点定位计算方法（可以参考的算法）

1) 最小二乘法

用最小二乘法来估算节点位置坐标也是无线定位中一种经常采用的方法。最小二乘法的突出优点是只需要一个假定的信号传播模型和信号观测值，计算简单，易于实现。

已知1，2，3等n个节点的坐标分别为(x1，y1)，(x2，y2)，(x3，y3)…(xn，yn)，它们到节点D的距离分别为d1，d2，d3···dn，假设节点D的坐标为(x，y)。

从第一行开始分别减去最后一行，得：

     
使用最小二乘法得：

这里的向量X就是移动节点的坐标。

2）三角质心法

在圆周定位模型中，三角质心法是一种较易实现、便于理解的算法。三角质心法的原理如下：在圆周定位模型中，理论上如果知道移动节点到三个信标节点的物理距离，用这三个信标节点做三个圆的圆心，到移动节点的物理距离为半径，画三个圆，这三个圆与移动节点都应该是相交的，即三个圆的公共交点就是移动节点MS的位置。但在实际中，由于噪声的影响，信号遇到障碍物以后的急剧衰落，测量工具带来的误差等原因，在圆周模型中的三个圆是不可能相交于一点的。由于在室内环境下，周围的障碍物等对电磁波信号的吸收，一般使得接收机接收到的信号强度值会小于预计的信号强度值，反映到推导出来的移动节点到信标节点的估计距离上，结果就是所画的三个圆的半径都偏大。这一种情况应该算是最为常见的情况，如下图所示（就是我们标题用的那张图了）：

下图画出来的三个圆一共有三个交点，形成一个三角形区域。所求的移动节点MS的位置就在这三个圆的公共交集区域内。通过取三角形的质心，作为移动节点MS的估计位置。

图2  基于圆周模型的三角质心法

3）加权三角质心算法

通过对无线电传播路径损耗模型的分析, 可以发现利用普通质心算法, 没有反映出信标节点对节点位置的影响力的大小, 影响了定位精度. 文中设计了加权质心算法, 它的基本思想是: 在质心算法中, 通过加权因子来体现信标节点对质心坐标决定权的大小, 利用加权因子体现各信标节点对质心位置的影响程度, 反映它们之间的内在关系. 通过下式中的加权因子来体现这种约束力。

4）加权质心算法

普通的质心算法同上面所描述的三角质心算法有所不同，它不需要知道未知节点到锚节点的距离。加权质心算法就是质心算法的基础上加上一个权值，提高定位精度。公式如下：

其中， 为未知节点估计位置的坐标， 为锚节点j的坐标，

为权值。

为未知节点i与锚节点之间的距离，g是一个可以根据实际环境进行调节的参数。

5）改进的加权质心算法

此方法对上面的的表达式进行了改进。

如图所示，RNi (i=1~9)是任意放置的锚节点。未知节点j能够接收到RNm(m=1~4)的数据包。我们把其中一个接收信号强度最大的锚节点定义为RNmax，其信号强度为Pmaxj(d)，再将它与其他信号进行相减，得

各位同学，看到上面如此多的数学公式，是不是有点头昏眼花的感觉？你要是真的全部理解上面的公式了，就能将上述的算法变成实用的室内定位技术了，不过上面是基本的算法，真的完全照搬公式，估计定位精度完全就在10米以上了。

所以，室内定位真的是一个很专业的技术活儿：所以，我们专注于算法的研究，把应用的活儿交给合作伙伴做；所以，想要在这个方面创业，就赶紧和我联系吧。我的微信号：43055209.

杭州优体科技有限公司是由海外留学人员归国创业的企业，致力于智能化设备与移动互联网技术的开发与推广，团队中既有在欧洲师从4G-LTE技术权威的专家，也有中国工程院院士的高足，因深信技术颠覆世界而走到了一起，“路索”智能室内定位系统是优体科技首个商业化项目，以高精度、云工勘、多种定位方式为主要特点，为各行各业提供定位与导航服务。