基于Wi-Fi 的三边定位算法的改进

郭阳，曹子腾，赵正旭，王威，刘曼云

（1.石家庄铁道大学复杂网络与可视化研究所，石家庄050043；2.青岛理工大学机械与汽车工程学院，青岛266520；3.西交利物浦大学计算机科学与软件学院，苏州215123）

0 引言

随着信息时代的到来，人们对各种信息的需求越来越多，位置信息也变得越来越重要，不论是在老人赡养时的位置监视，还是在大型商场中对所需商品位置的快速定位，还有在地下停车场中快速寻找车位等，都显示出位置信息的重要性。不止在生活中对位置信息有着强烈的需求，在工业、商业等都需要位置的信息，甚至在安全救援方面，快速确定受困人员位置也十分重要[1]。所以，对定位技术的研究是非常有意义的。

现如今，室外定位技术发展已经足够成熟，例如美国全球卫星导航系统GPS、俄罗斯的“格洛纳斯”、欧盟的“伽利略”以及中国的北斗卫星导航系统[2]。但是因为在室内环境中，墙壁、家具等建筑物可能会对卫星信号产生遮挡，所以室外定位技术并不能很好地应用到室内，所以专门用于室内条件下的定位技术逐渐成为研究热点。常见的室内定位技术主要有红外线定位技术、超声波定位技术、蓝牙定位技术、Wi-Fi 定位技术等。这些室内定位技术因为其自身特性各有优缺点[3]。例如红外线定位技术虽然定位精度高但是成本高，不能普遍适用。蓝牙定位技术虽然硬件环境简单，但是蓝牙信号容易受到室内其他信号的干扰产生误差。

上述定位技术中，Wi-Fi 定位技术因为其成本低、覆盖面广等优点被广泛使用。现在智能移动设备越来越普及，Wi-Fi 广泛分布在各种大小区域，不论是商场、停车场还是个人住所，Wi-Fi 都随处可见。所以对Wi-Fi 室内定位技术的研究成为一个热点。在Wi-Fi 定位技术中，三边定位算法是最基础、最简单的一种定位算法，也是基于测距的定位技术中使用较多的一种算法。但是因为其在使用过程中会产生累积误差，本文针对三边定位法精度不高的问题[4]，在使用三边定位法进行定位的过程中对其进行改进从而减小定位误差。

1 Wi-Fi定位技术的定位原理

Wi-Fi 已被开发用于无线电信号的数据通信，其定位应用变得十分流行[5]。

Wi-Fi 定位技术是一种基于辅助设备的定位技术，其定位原理是通过在室内区域中部署一定数量的AP（无线接入点，Access Point），每一个AP 都有自己独立的MAC 地址和名称。在室内建立好坐标系，设立好原点位置和横纵轴方向。其中放置的这些AP 的坐标已知。当待定位设备进入此室内区域后，可以接收到来自各个AP 发射出的信号，并测出Wi-Fi 的RSSI 值（Received Signal Strength Indication，可接收信号强度值）[6]。根据信号传播的衰减模型，推算出信号强度和距离的转化公式，后台可以计算出待定位设备与每个AP 的距离，再通过三边定位算法或其他定位算法对待定位设备的位置坐标进行计算。

2 信号强度与距离

Wi-Fi 定位技术中可以采用基于测距的定位方法[7]，计算方法是根据接收到的信号强度值转化为距离，因为信号在传播环境中会产生衰减，所以信号强度和距离不能直接转化，需要考虑信号的衰减，并且要考虑不同环境中信号的衰减速度是不同的，也就是信号穿过不同的障碍物时产生的信号衰减都不相同。例如信号在空气中传播和穿透墙壁后如果按相同的公式计算就会产生较大误差。计算时一般采用无线信号的传输损耗模型，传输损耗模型的公式为[8]：

其中，d 表示距离辅助设备的距离，n 为环境衰减因子，PR（d）是距离辅助设备距离为d 时的信号强度RSSI 值，PR（d0）是距离待测设备为d0 时的信号强度，一般取d0 为1m。所以根据此式可得出距离与信号强度的转化公式如下：

其中，d 是测量设备距发射信号强度设备的距离，单位是m。RSSI 为信号强度值，测出的信号强度值一般情况下是负数。A 是测量设备距离发射信号强度设备1m 时的RSSI 值的绝对值，需要在实验中进行测量得到。n 为环境衰减因子，需要进行校正测试，不同的障碍物中信号的衰减是不同的，所以需要后期实验得到。

3 三边定位算法

三边定位算法的主要流程是先通过测量信号强度计算出待定位设备与每个AP 的距离，选出待定位设备距离附近的三个AP，分别为AP1、AP2、AP3，且距离这三个AP 的距离分别为的d1、d2、d3。分别以AP1、AP2、AP3 为圆心，以d1、d2、d3 为半径作圆，三个圆的交点就是待定位设备的位置。如图1 所示。

图1 三边定位（a）

但是这种情况只出现在理想条件下，也就是没有定位误差的条件下。由于在测量信号强度的时候信号会在空气中产生衰减，所以会存在误差，在信号强度转化为距离的时候也会存在误差，所以一般情况下三圆很难相交于一点，出现较多的可能是三个圆相交于一个区域，甚至还可能出现其中两个圆不相交。

4 三边定位算法的改进

由于使用三边定位算法时分为测距阶段和定位阶段，在测距阶段，由于信号传播的不稳定性，一次测量得到的RSSI 值可能会与实际的值有偏差，所以在转换成距离的时候也会产生一定的误差。在定位阶段，由于上述误差使三个圆不会相交于一点，而是相交于一个区域，所以在这个区域中找出待定位点也会产生误差。这两个阶段的误差会累积导致测出的位置与实际位置偏差较大，所以分别在这两个阶段采取措施减小误差的累积，最后达到缩小定位误差的目的。在测距阶段，分别对每一个AP 的RSSI 值进行多次测量，将得到的数据采用Mahalanobis 距离检测方法去除噪声数据，得到一组相对准确的RSSI 值再进行距离的转换。在定位阶段，通过计算三圆相交区域的质心点，得到待定位坐标。

4.1 Mahalanobis距离

Mahalanobis 距离又称为马氏距离，表示数据的协方差距离，是一种有效计算两个未知样本的相似度的方法。定义为：设总体G 为m 维样本，均值向量为μ（μ1，μ2，…，μm）′，协方差阵为∑（σ ），则样品X=（x1，x2，…，xm）′与总体G 的马氏距离定义为：

当m=1 时，只有一个考量单位，公式可转化为：

因为只需涉及信号强度一个考量单位，所以采用m=1 时的马氏距离公式。计算RSSI 值样本的均值μ，以及方差σ2，再根据公式计算出每个样本与均值之间的Mahalanobis 距离。即：

设定好参数，样本RSSI 值与均值之间的Mahalanobis 距离超过此参数，将该RSSI 值判定为噪声数据，并进行剔除。余下的RSSI 值求平均数得到最终要转换为距离的RSSI 值。

采用Mahalanobis 距离的优点是Mahalanobis 距离的计算是建立在总体样本的基础上的，两个相同的样本在不同的总体中计算的结果一般也是不同的。所以对每一个AP 多次测量RSSI 值，即使每一组的均值都相同，可能要剔除的奇异点也是不相同的，这会在一定程度上减小误差。

4.2 三边质心定位算法

在使用三边定位算法的时候，如图3、图4 所示，三个圆相交于一个区域，待定位坐标在此区域内，在此区域内要求得待定位点的位置，采用求多边形质心点的方法[9]。求一个多边形质心点的过程是：已知多边形的顶点坐标（X1，Y1），（X2，Y2），…，（Xn，Yn），则质心点（X，Y）的解法如下式：

三边质心定位算法的主要流程是：如图3 和图4所示，三个圆围成了一个类似于三角形的区域，分别对三个圆两两求交点，得到这个区域的三个顶点坐标，再求质心点，所得到的质心点的坐标就是待定位设备的坐标位置。

具体流程是在室内环境中部署4 个AP，分别为AP1、AP2、AP3 和AP4，并且位置已知。从这四个中选出三个进行组合，根据排列组合原理可得到四组，分别为（AP1，AP2，AP3），（AP1，AP2，AP4），（AP1，AP3，AP4），（AP2，AP3，AP4）。对每一个组合分别用三边质心定位算法求出一个坐标，这样可以求出四个坐标，再对所求得的四个坐标求平均值，得到最终的待定位点的位置坐标。如果在计算过程中出现有一组数据三个圆有不相交的情况，表明误差过大该组数据不可用，舍弃该组数据，余下的可用数据再求平均值。算法流程如图2 所示。

图2 三边定位（b）

图3 三边定位（c）

图4 算法流程

5 算法的实验验证

在实验验证阶段，需要的硬件设备有：路由器和至少四个AP。本次实验场景选择石家庄铁道大学第九实验楼230 室，实验场景和硬件设备如图5 所示。

图5 硬件设备

通过在室内环境中放置四个AP，建立坐标系，选取好坐标原点和横纵轴方向，并记录好AP 的坐标位置，待定位设备采用日常使用的可以接收到Wi-Fi 信号的智能移动设备，当开始定位时，待定位设备分别接收到四个位置的AP 信号并对每个AP 的信号强度进行五十次测量。记录下测量数据，通过Mahalanobis 距离去除奇异值，再求平均值得到一组RSSI 值。再将RSSI 值转化为距离。在五个未知点分别对四个AP 测量信号强度并进行去噪处理后可得到五组数据如表1所示。

表1 信号强度表

距离与RSSI 值的转化利用转化公式，在转化之前的第一步需要先测量出A 的值，测量方法是室内部署好AP 后，距离其中一个AP 一米时测量信号强度，同样采用多次测量去除奇异点得到一个较为准确的值。第二步，矫正测试环境衰减因子n 的值，因为在不同室内环境中，环境衰减因子n 的值是不同的，经过矫正测试，得到一个最佳值。第三步，将RSSI 值转化为距离。因为实验场景障碍物较少，无墙壁、石膏等障碍，所以环境中信号衰减相对较少。经实验，最后确定A的值为30，环境衰减因子n 的值为1.5，再根据信号强度与距离的转化公式求得与每个AP 的距离。

最后分别采用原始的三边定位算法和本文提出的三边算法的改进流程进行定位，定位结果如表2 所示。按照本文提出的先采用Mahalanobis 距离去除奇异RSSI 值，再采用三边定位算法后求质心点得到的未知点坐标要比原始的三边定位算法所求出的未知点坐标在一定程度上更加精确，减少了误差的累积。

表2 定位结果

6 结语

三边定位算法在许多基于测距的定位技术中使用频率相对较高，但是由于其每个过程都会产生一定的误差最终会造成误差的累积，所以直接使用会使最终数据与实际值偏差较大。本文提出的定位流程先对测量出的信号强度进行处理去噪，再通过三边定位算法，最后求出三圆交点围成三角形区域的质心点的方法求出定位坐标，该方法可以在每一个过程中减小一定的误差，最终避免误差的累积导致最终数据失实。经实验验证，基于Wi-Fi 定位技术使用该定位方法比传统的三边定位方法的定位精度在一定范围内有所提高。