基于WLAN的室内定位方法研究

任建新，自俊林，宋凯月

(西北工业大学自动化学院，西安 710072)

0 引言

无线局域网络(Wireless Local Area Networks,WLAN)室内定位技术属于无线局域网定位技术，是当前最主要的室内定位技术之一，具有十分广泛的应用前景。由于WLAN技术的飞速发展以及网络的迅速普及，越来越多的路由器接入点(Access Point,AP)被安置在各种公共场所。只要人们携带配置了无线网卡的设备进入AP覆盖区域，即可扫描连接到该AP所在的网络，进而进行联网活动。随着AP布设范围越来越广以及人们对室内定位需求的增加，越来越多的科研人员与工作者将目光放在AP发出的WLAN信号与接入设备位置之间的关系。目前，WLAN室内定位技术主要是基于传播模型[1]或场景分析[2]两种原理。

基于传播模型的WLAN室内定位技术通过获得AP位置和接收者与AP之间的距离反推接收者位置，主要利用几何学的计算方法，其中以三边定位法[3-4]为主。基于场景分析的WLAN室内定位技术通过事先获取定位区域不同位置点的信号特征，与接收端获取的信号特征进行匹配，进而判断接收者位置，主要方法为位置指纹定位法[5-6]。

本文介绍了三边定位法和位置指纹法，分析了上述两种WLAN定位方法的优缺点，结合现有方法的优点并针对实际工作条件进行改进，提出新的定位解算方法——粗定位迭代校准法。通过设计实验验证新算法的实时性和可靠性，并得到以下结论：

1)粗定位迭代校准法的定位结果能够满足行人定位需求，定点定位精度2～3m，移动定位精度3～5m，表明了该算法具有可靠性。

2)相比于一般加权K近邻算法(Weighted K-Nearest Neighborhood,WKNN)，迭代算法通过控制运算量，大大降低了运行时间，单次定位所使用的时间可控制在2ms以内。

1 三边定位法

三边定位法在定位过程中主要分为2个环节，分别是测距环节与定位环节。

1.1 测距环节

使用三边定位法计算位置目标，首先需要在定位区域内安装至少3台不共线AP，且3台AP位置信息已知。当待定目标进入AP覆盖区域后，接收端分别接收来自3台AP发出的无线信号，同时获得不同信号的接收信号强度(Received Signal Strength Indication，RSSI)。根据式(1)的无线信号传播模型即可计算得到接收机端与AP之间的距离

(1)

其中，Pr(d)为接收机端接收到的无线电信号功率；Pt为发射端即AP的发射功率；Gt为发射端增益；Gr为接收端增益；λ为无线电电波波长；L为损耗系数，由信号传播环境决定；d为接收端与发射端之间的距离，即无线电传播距离。

然而，在实际无线电信号传播过程中，上述传播模型往往会受到路径损耗、物体遮挡[7]等因素的影响而导致计算结果不准确。因此，在实际应用中，通常采用式(2)所述模型进行测距

Pr(d)=K-10εlg(d)

(2)

其中，ε为实际环境中无线电信号损耗系数；K为发射端发射功率，对于每台固定AP而言通常为常值。

1.2 定位环节

如图1所示，利用几何关系计算接收机位置。图1中，A、B、C为3台AP位置且坐标已知，分别为(x1,y1)、(x2,y2)、(x3,y3)，D为待定位目标位置(x,y)，AD、BD、CD为待定位目标与3台AP间的距离，分别为d1、d2、d3。将方程式(3)、式(4)、式(5)联立求解出目标位置

(3)

(4)

(5)

图1 三边定位法示意图Fig.1 Schematic of trilateral positioning method

但是，非理想情况下，三圆很难相交于一点，极大可能出现未相交空白区域或者三圆重叠区域，导致上述方程联立求解时无解。针对三圆出现未相交空白区域或者三圆重叠区域两种情况，可以使用三圆多个交点坐标计算近似坐标作为目标位置，近似坐标求解思路如下：

根据方程式(3)和式(4)联立求解得到A圆与B圆的2个交点坐标(xAB1,yAB1)和(xAB2,yAB2)，将交点坐标与圆心C坐标代入平面两点距离式(6)

(6)

式中，P1(xP1,yP1)和P2(xP2,yP2)为两点坐标；dP1P2为两点距离。计算两圆交点与圆心C之间的距离，取距离圆心C较近交点作为近似坐标计算点，记为(xAB,yAB)。同理，按照相同的方法，可计算出近似坐标计算点(xAC,yAC)和(xBC,yBC)。3个近似坐标计算点的均值即为定位点坐标，如式(7)所示

(7)

除此之外，三边定位法还存在AP的选择问题。在实际应用中，观测到的AP数量往往多于3个，如果直接选择信号最强的3台AP进行三边定位，有可能导致DOP不佳，并且丢失信息。在AP数量多于3个的情况下可以基于信息增益[8](Infor-mation Gain，InfoGain)方法，选择最能反映待定位点信息的AP，根据InfoGain准则估计每一个AP的区分度能力D，并选择区分度能力最高的3个AP用于三边定位。

三边定位法的精度主要由测距环节得到的3个距离精度决定，而距离精度又由无线电信号传播模型精度决定。在实际环境中，传播模型中的损耗系数难以准确确定，不同室内环境中的信号传播模型均不一样。所以，在实际应用中使用三边定位法难以实现较为准确的定位目的，但是该方法根据3个信号强度值及3台AP坐标即可推算自身坐标位置，具有运算速度快的优点。

2 位置指纹定位法

位置指纹定位法利用接收机端RSSI与接收端物理位置之间的关联性进行定位，指纹定位工作流程主要分为离线数据采集建立指纹库环节和在线位置解算环节[9]。

2.1 离线环节

离线环节的主要工作是对定位区域进行指纹网格划分，确定指纹点坐标，采集指纹点(Finger Point,FP)处WLAN信息，包括MAC地址和RSSI值，将三者合并作为一条指纹信息保存起来，所有指纹信息将构成定位所需的指纹数据库。离线环节中对定位区域进行指纹网格划分，确定指纹点坐标如图2所示。在图2中，AP1、AP2、AP3及AP4是在定位区域内布设的4台AP，其坐标已知；FP1、FP2、FP3、…、FP16为通过网格划分得到的指纹点。将每个指纹点分别接收到4台AP的RSSI记为RSSI1、RSSI2、RSSI3、RSSI4，则指纹的信息采集如图3所示。

图2 指纹网格划分示意图Fig.2 Fingerprint grid division diagram

图3 指纹点信息采集Fig.3 Fingerprint points information collection

2.2 在线环节

指纹库建立完成后，接收端进入定位区域并采集所处位置接收到的所有WLAN信号的MAC地址及RSSI值。采集完毕后，首先筛选有效定位AP信息，将不在指纹库内或者强度非常低的AP滤除，以免干扰指纹匹配导致指纹点漏选或错选。筛选完毕后，将剩余AP信息与指纹库内指纹点信息进行比对，选出相似程度最大的指纹点，即最接近当前所处位置的指纹点。指纹定位流程如图4所示。

图4 指纹定位流程Fig.4 Fingerprint location process

当接收端获取扫描到AP信号的MAC地址及RSSI值后，需要从指纹库中寻找到最为相似的指纹点用于坐标解算。目前所应用的指纹点匹配方法很多，包括：最近邻法(Nearest Neighborhood,NN)、K近邻算法(K-Nearest Neighborhood,KNN )、WKNN神经网络法、支持向量回归法[10]等。由于本文以手机作为接收端实现WLAN定位，从程序运算量及手机处理器运算性能考虑，所选方法运算量和数据量不能过大，所以本文对前三种方法进行对比介绍[11-12]。

2.2.1 最近邻法

最邻近法首先根据接收端实时采集到的RSSI值与指纹库内的指纹点RSSI值,计算二者之间的欧氏距离，如式(8)所示

(8)

2.2.2 K近邻算法

K近邻法是最近邻法的改进，利用式(8)计算得到所有指纹点的欧氏距离后，选取K(K≥2)个距离最小的指纹点，将这K个指纹点坐标进行均值计算得到接收端位置坐标，如式(9)所示

(9)

最近邻法可以看成是K=1时的K近邻法，相比于最近邻法，K近邻法提高了定位精度。

2.2.3 加权K近邻算法

考虑到K近邻算法中所选取的K个指纹点RSSI值与实测RSSI值之间的差别，相应地,最终计算坐标时的贡献也有所不同，与实测点距离更近的指纹点RSSI值匹配程度更高。因此，在坐标计算时权重更高。式(9)中的均值计算方法导致更有利于定位的指纹点没有被充分利用。加权K近邻算法坐标计算如式(10)所示

(10)

其中，di为第i个指纹点与实测点间的欧式距离；η为归一化加权系数；ε为避免分母为0而设计的很小的常值。式中，加权系数与欧式距离成反比，保证距离实测点越近的指纹点在计算坐标时贡献越大，从而在一定程度上提高了系统的定位精度。

最近邻法、K近邻算法和加权K近邻算法在定位精度上逐步提高，但运算量也相对增大，目前主要以加权K近邻算法作为指纹匹配算法。

3 粗定位迭代校准法

三边定位法定位迅速、计算量小，但由于环境因素对无线信号影响的不确定性导致其精度降低；位置指纹定位法事先采集环境中的信号特征，在一定程度上弱化了环境因素的影响，提高了定位精度，但随着定位区域的扩大，指纹点数量激增，利用指纹法计算位置时会存在大量无关指纹点计算，增大了计算量，影响实时性。考虑两种方法的工作原理，若将两种方法进行融合，利用三边定位法确定大致区域范围，再从指纹库中提取出该范围内的相关指纹点，进而利用指纹法进行定位，则可以大大提高精度且减少运算时间。但如果三边定位法所确定范围偏差较大，则直接影响后续指纹法的定位精度。因此，本文提出了利用多次定位迭代校准的方法修正初始定位偏差，将三边定位法、指纹定位加权K近邻算法和迭代校准三部分融合成新的定位算法——粗定位迭代校准法。

粗定位迭代校准法的思想是，首先使用三边定位法粗略确定接收机位置，然后多次利用小范围指纹定位不断将计算坐标向真实坐标逼近。此种方法既可以弥补初始三边定位误差较大的缺陷，又可以节约直接使用指纹法时计算大量无关指纹点消耗的时间。粗定位迭代校准法示意图如图5所示。图5中，矩形框为整体定位区域，四角黑色实心圆点为4台定位AP，矩形框内空心圆和交叉线圆点为指纹点，其中交叉圆点代表迭代定位区域圆心，黑色五角星为行人实际位置，黑色三角形为三边定位法定位结果。

图5 粗定位迭代校准法示意图Fig.5 Rough positioning iterative calibration method diagram

首先，利用三边定位法计算得到初始坐标，即黑色三角形位置。以该初始坐标为圆心确定初始定位区域R1，只选用该区域内的指纹点做WKNN算法计算，该次计算结果落于R1范围内，但位于接近五角星方向。该次计算除了得到坐标值，同时还保留了WKNN法计算时权重最高的指纹点，权重越高代表距离实际距离越近，即图5中的交叉圆点FP1。以FP1作为圆心确定新的定位区域R2，R2相比R1距离实际距离更近，重复上述工作得到FP2、R3、FP3、R4……直到某2次WKNN法计算结果差值小于设定阈值，则认为所选定位区域覆盖实际位置，定位完成。

由于粗定位迭代校准法中迭代校准环节可有效弥补三边定位法初始坐标计算误差较大的缺陷，所以在使用三边定位法粗略计算接收机位置时可不用式(1)或式(2)所述模型，根据式(11)和式(12)进行三边定位法计算初始坐标

(11)

(12)

式中，(X,Y)为初始定位坐标；(Xi,Yi)为用于计算的AP坐标；K为AP数量；RSSIi为接收机收到每台AP的信号强度。在式(11)、式(12)中只使用了信号强度一个参数，而式(1)或式(2)所述模型均需要已知大量如发射功率、接收功率等相关参数。因此，利用式(11)、式(12)计算初始坐标降低了运算的复杂度，减少了运算时间。

4 实验验证与分析

为了验证本文所提出的粗定位迭代校准法的可行性，进行了包括定点定位实验、行走定位实验以及运算速度检测3个部分的实验，以验证该定位算法下WLAN定位的定位精度以及该定位算法的实时性。实验过程中以手机作为信号接收端。

4.1 WLAN定点定位实验

用于定点定位实验的实验室平面图如图6所示。实验室长7.5m，宽7.5m，在四角布置4台家用普通AP，实验室内摆放有金属柜、桌椅、金属实验器材等物件，对WLAN信号有一定干扰作用，可认为实验室接近或等同真实使用环境，定位结果具有实际参考意义。

图6 实验室平面示意图Fig.6 Laboratory plan diagram

图6中，黑色实心圆点代表4台AP，分别布置在4个角落。室内坐标系以左下角为原点，X轴正向向右，Y轴正向向上。

在实验室内以1.8m为间隔选取指纹点，共25个指纹点。实验室内随机设立10个测试点，覆盖实验室角落、边缘和中心地带，每个测试点采集100组有效定位数据，共1000组有效数据。以实验室选取的测试点真实坐标值为实际坐标，每一测试点的100组计算坐标的均值作为定位坐标，定位坐标与实际坐标间的距离为坐标误差，100组定位误差的均值为误差平均值。得到的定点定位实验数据见表1。

表1 定点定位坐标及误差Tab.1 Fixed points positioning coordinates and errors cm

1000组定位误差累积分布曲线如图7所示。由表1的定位误差数据可得，10组测试数据的单次定位误差主要集中在2～3m，而每一测试点100组数据平均后的定位误差，即表1中的坐标误差主要在2m以内。同时，由图7的累积分布曲线可得，1000次定位结果中95%的定位误差在3.3m以内，67%在2m以内，50%在1.5m以内，定位精度较高。

图7 定位误差累积分布曲线Fig.7 Positioning error cumulative distribution curve

综上所述，对于移动缓慢或者静止状态的定位对象，可以通过多次定位求平均值的方法提高定位精度。

4.2 WLAN行走定位实验

行走定位实验的实验场地为实验室所在地的主楼，主楼定位区域由3条室内走廊及1条室外走廊构成。每条走廊长约64m，宽约2.3m，室内走廊每间隔15m安装1台吸顶AP，共11台。图8所示为主楼平面示意图，黑心实圆点代表11台AP，主楼坐标系以左下角为原点，X轴正向向右，Y轴正向向上。

图8 主楼平面示意图Fig.8 Main building floor plan diagram

在行走定位实验时，主楼走廊以2.5m间隔选取指纹点，共102个。移动实验路线为U型走廊一端至另一端，为计算并分析定位精度，在移动路线上选取20个位置作为测试点,且每次定位解算为单次扫描，即每个测试点只采集1组数据。20个测试点定位解算结果及对应误差数据见表2。根据表1和表2的误差数据可知，在移动过程中，坐标误差要大于定点实验的坐标误差。如表2所示，行走定位实验的坐标误差一般为3～5m。

表2 定位测试点坐标及误差Tab.2 Positioning test point coordinates and error cm

4.3 WLAN定位算法速度检测

为了验证迭代算法与一般WKNN算法的计算速度，本文在已有指纹库的基础上利用插值方法进行扩充，得到粗定位迭代校准法与一般WKNN法的运行时间见表3。

表3 迭代算法与一般WKNN法运行时间Tab.3 Iterative algorithm and general WKNN method running time

由表3可以看出，相比于一般WKNN法，迭代算法有效地控制了运算量，极大程度地降低了运算时间。

5 结论

本文首先介绍了WLAN室内定位技术的两种基本原理以及基于不同原理的定位方法，主要是：三边定位法和位置指纹定位法；阐述了两种主要方法的工作原理并对比分析其优缺点；结合现有方法的优点并针对实际工作条件进行改进，提出了新的定位解算方法：粗定位迭代校准法。通过设置合适的实验环境，利用已有WLAN设备或铺设WLAN设备设计实验验证算法的可行性。实验共分为定点定位实验、行走定位实验以及运算速度检测3个部分。综合上述3个部分的实验数据结果表明，本文提出的粗定位迭代校准法在初始阶段使用三边定位法确定粗略位置可以大大减少无关指纹点的计算量，引入迭代校准定位方式可以有效降低初始三边定位大误差对最终结果的影响。从定位结果来看，定点定位精度2～3m，移动定位精度3～5m，不存在定位失效情况，满足行人定位需求。并且此种定位思想大大减少了计算量，降低了运算时间，单次定位所使用的时间可控制在2ms以内，大大降低了运行时间。