基于区域网格划分的SVM室内定位算法

贾春阳 郭之超

1(北京联合大学智慧城市学院 北京 100101)2(北京航空航天大学计算机学院软件开发环境国家重点实验室 北京 100191)

0 引 言

位置服务LBS(Location Based Service)又称为定位服务，是由卫星定位系统、广域通信基站系统和室内定位系统等系统结合在一起提供综合的定位服务。随着通信设备的更新迭代和通信技术的不断发展，定位服务技术也有了长远发展，不再是初期只依靠定位卫星进行解算定位，而是发展成多种定位技术融合定位的阶段，大大提高了定位精度，也不断拓展了适用范围，深刻影响了人们的生产生活[1]。

在室内定位技术方面，目前流行的定位技术主要有借助Wi-Fi定位、借助蓝牙定位、借助广域基站的附加信号定位等几种方式进行定位。从基本技术原理上分析，所有的室内定位思路都基本相似，是通过不断发送信号的固定基站或信标，为终端提供定位的手段，具体方法包括三角定位、无线频谱定位等方式[3]。

基于IEEE 802.11 b/g/n协议的无线网络在近年来得到迅速发展和普及，并广泛应用于我们的生活场所中。支持Wi-Fi的终端也越来越多，智能手机、平板电脑、智能手表等物联网设备也均包含了无线上网卡，这为Wi-Fi定位提供了必要的物质基础与技术支持，使得基于Wi-Fi的无线定位成为可能[4]。由于室内信号传播的复杂性，定位精度、维护成本、室内地图等逐渐成为室内定位的约束条件[4]。

目前Wi-Fi应用于交通枢纽、机场、车站、商场等公共场所，具有广泛的覆盖面和普及面，并且智能手机都配有Wi-Fi通信功能。借助Wi-Fi的室内定位是网络接入的附加功能，通过软件实现定位，具有很好的复制应用能力。

1 手机Wi-Fi数据的信号特征

1.1 Wi-Fi信号强度的空间分布特征

室内定位的前提是移动设备接收到的RSSI信号强度值能够反映其与AP的位置存在一定的相关性。在室内环境中，信号随着距离信号源的距离增长会有一定程度的衰减。经过前人不断的实验证明，对数路径损耗模型(Pass-Loss)经验公式能够符合Wi-Fi信号RSSI在空气环境下的能量传输损耗，信号强度RSSI与AP的传输频率f和信号的传输距离d相关，遵循以下公式：

(1)

式中:d0为所选取的参考点，PL(d0)为参考点d0处测量到的RSSI损耗值(记为A)，一般取d0=1，即选取距离AP一米处作为参考点。d为发射点到接收点的距离。n为路径损耗指数，表示路径损耗与距离增加的关系，它依赖于其所处的环境和建筑物是否有阻隔。PL(d0)为发射到接收间的损耗，通过实际测量得到PL(d0)[5]。在不同的环境下，路径损耗指数可以从2变化到6，一般室内取值为从2到4。此外在障碍物多的地方，n通常有增长的趋势,而d0的选择通常也和不同的传播环境相关。

图1中的点线是对数路径损耗模型经验公式的拟合数据，无点线是一组在走廊中实际测量的数据。可以看出模型能反映总体趋势，但和真实室内环境下的情况还是有较大区别。走廊是比较简单的场景，如果在其他更复杂的场景下，有更多的信号遮挡、反射等因素存在，RSSI不仅和距离位置有关，还和周围的各种障碍物有关系。

图1 信号强度模型拟合和实际测量对比

1.2 Wi-Fi信号的强度波动特征

基于Wi-Fi信号的室内定位算法直接依靠AP的信号强度特征进行定位，因此AP信号强度的稳定性对于定位精度及可信度是至关重要的。本节将从稳定状态、信道切换状态和移动状态对Wi-Fi信号强度的波动特性进行探究。

1.2.1 稳定状态

稳定状态指的是手机设备处于静止状态，并且连接Wi-Fi网络，网络信道未发生变化的状态。稳定状态下分析Wi-Fi信号强度的波动特性能够反映出Wi-Fi信号在正常条件下的稳定性。

在测试环境中，将手机放置在某一位置不动，连接上测试环境Wi-Fi，并开启手机Wi-Fi传感器数据记录功能，将手机静止放置30分钟。同时在AP端设置固定的信道，防止出现AP自动扫描信道，进行信道切换的情况。记录完成后，将数据汇总，绘制成如图2所示的折线图。

图2 稳定状态下信号波动分布图

从图2我们不难发现，即使手机处于稳定状态，AP也没有发生信道变化，移动设备采集到的AP信号强度仍然具有一定的波动性，但是波动幅度不大，幅度基本在5 dB的范围之内，这是由信号传播的过程中可能发生的多径效应以及反射、绕射等原因造成的。

1.2.2 信号切换状态

目前市面上的大部分AP都具是双频的，分别提供2.4 GHz和5 GHz双频段的通信模式，而且每个频段下根据频率的不同划分了不同的信道。为了减少信道的通信压力，充分利用带宽特点，大部分AP在出厂时会被默认设置成自动选择信道，即AP会在不同的信道上定时发送探测报文探测信道的使用率，如果当前工作信道使用率较高经常发生拥塞时，自动选择一个较为空闲的信道继续完成传输数据的工作。

信道的切换有两种情况，一种是同一频段下不同信道的切换(例如5 GHz频段内某信道的切换)，另一种是不同频段下信道的切换(例如5 GHz频段内某信道切换到2.5 GHz的某信道)。根据Path-Loss损耗模型公式得知，频率对于信号强度有一定影响。图3、图4也反映了信道切换时信号强度会发生一定改变。

图3 2.4 GHz频段下信道1切换到信道9信号强度变化图

图4 5 GHz频段下下信道44切换到2.4 GHz频段 下信道6信号强度变化图

实验表明，信道切换会造成同一位置的同一设备信号强度不同，有一定的波动性。同一频段下信号强度变化波动较小，大约在10 dBm左右；不同频段下造成的信号强度变化波动较大，大于20 dBm。而且两种信道切换发生时都有比较大的瞬时波动。

故信道切换对于室内定位精度具有非常大的影响。对于Wi-Fi信号的频率高度复合，应做好相应的信道频率规划。2.4 GHz的波段内选用1、6、11信道作为固定信道，关闭AP的自动信道选择功能，防止频繁的更改信道。

1.2.3 移动状态

用户在室内的移动状态分为慢速行走、常速行走和快速行走。手持手机，分别以三种不同速度进行测试。图5为三种速度下信号强度随移动位置的变化情况，图6为该段测试数据的采集起始点、经过路径以及AP的实际位置。

图5 不同速度下信号强度变化情况

图6 数据采集路线及AP位置图

图5表示了分别以慢速、常速和快速三种速度行走所感知到的某一具体AP的信号强度变化情况，图6表示行走的起止点、移动方向和AP的具体位置。从数据上看，由于用户是先靠近AP所在位置，然后再远离AP所在位置，三种速度在整体趋势是一致的，但是随着速度的增加，折线图的斜率越大，即表明波动越大。从微观上分析，由于人行走的速度在0～2 m/s的范围内，室内定位的计算速度在1 s内至少能够完成一次定位，所以行走状态可以在微观上认为是静止的。

1.3 Wi-Fi信号的无线广播特征

Wi-Fi信号的广播特性指的是，Wi-Fi信号发射端广播发射beacon信号让无线信号接收端(如手机)的无线接收模块搜索到该发射端的无线信号，以便于连接该无线网上网，如果关闭了那么就无法搜索到该无线信。故Wi-Fi信号发射端需要高频率的、定期的发射beacon信号。在实际应用中，由于AP之间主动广播和接收beacon帧和物理环境不可控等因素，定位服务器会接收到很大一部分信号强度数据为无效的报文数据，即系统内部自身AP之间的信号强度数据和系统外部AP的信号强度数据，据统计该类数据量约占数据总量的70%以上，极大浪费了物理存储资源和实时计算资源，导致定位引擎计算压力大、定位响应不及时的问题。

2 手机Wi-Fi数据预处理

2.1 无效AP的动态监测与过滤

位置指纹定位方法的定位流程是定位服务器接收AP或者移动设备发送来的定位原始数据和定位请求，由定位引擎通过一定的搜索匹配算法匹配位置指纹信息，结合室内地图资源，将定位结果返回给定位请求者。

但是在实际应用中，由于AP之间主动广播和接收beacon帧和物理环境不可控等因素，定位服务器会接收到很大一部分信号强度数据为无效的报文数据，即系统内部自身AP之间的信号强度数据和系统外部AP的信号强度数据。该类数据量约占数据总量的70%以上，极大浪费了物理存储资源和实时计算资源，导致定位引擎计算压力大、定位响应不及时等问题。

因此需要克服目前WIFI室内定位无效报文多、存储的无效数据多、定位引擎计算压力大、定位请求响应不及时等问题，需要在预处理、定位引擎定位计算之前设计一种方法进行无效AP的动态检测与过滤。这种方法能够有效动态检测出无效AP，在定位服务器的网关部分及时将无效数据过滤掉，避免定位引擎进行无效计算，提高移动设备定位请求的响应及时性。无效AP的动态监测与过滤部署位置如图7所示。

图7 无效AP的动态监测与过滤部署位置示意图

2.2 数据筛选

手机能够探测到的最小AP信号强度为-100 dBm。当信号强度小于-95 dBm，根据路径损耗模型以及实验测试得知，距离至少在30米之外。因此，即使是稳定的信号数据，对于提高定位精度的影响已经十分微小，不能满足定位的需求，所以在数据筛选时，应当将低于-95 dBm的数据删除。

2.3 数据修正

数据修正主要以滤波为主。常用的滤波方法有卡尔曼滤波法、Alpha-Beta滤波法、滑动平均滤波法等。

从定量角度进行分析，用同一段数据对卡尔曼滤波法、Alpha-Beta滤波法和滑动平均滤波法进行比较和评价如图8所示。

图8 采样数据与三种滤波方法的比较

卡尔曼滤波法对信号有很好的平滑效果，但在信号波动较大的采样时刻，滤波效果较差，不能对大范围波动进行有效抑制。Alpha-Beta滤波法可以反映信号的时间变化，但平滑效果较差，不推荐使用。滑动平均滤波器在平滑性和实时性方面优于前两种滤波方法。

3 基于区域网格划分的SVM定位算法

3.1 区域网格划分

当待测区域较大，定位区域包含大量采样点时，采用全局SVM定位算法依次遍历每个采样点，然后进行匹配判断，大大增加了定位所需的时间。此外，将所有采样点模型加载进内存会增加所使用的内存量。在定位相应的时间及时性和内存空间使用量上不能满足类似于交通枢纽这样的大面积、多楼层场景下的定位需要。

解决上述问题的一个方法是对室内整体进行区域网格划分，见图9。将待测区域的大面积划分为多个较小的子区域。在定位过程中，首先确定移动设备所在的子区域及相邻的几个区域，然后在该区域内进行精确的SVM定位。

图9 区域网格划分图

划分好区域后，从“位置指纹”数据库中参考点属于该区域的数据中取出每个参考点“位置指纹”向量中信号强度RSSI最大一项的AP的MAC地址，作为该点的代表，然后与该区域内所有代表点的AP的MAC的并集作为该区域的特征集合。

3.2 支持向量机

支持向量机SVM方法建立在统计学习VC维(VC dimension)理论和结构风险最小(structural risk minimization)原理基础上，根据有限的样本信息在分类能力(对任意样本进行无错误分类)和模型的复杂性(对特定样本的学习精度，Accuracy)之间寻求折衷，以期使分类器获得最好的推广能力(Generalization Ability)。它是一种非参数化的有监督分类器[6]。

假设当前存在一个线性样本集(xi,yi)，i=1，2,…，n，x∈R2其中y是类别标号且y∈{-1,1}，d维空间中的线性判别函数为：

g(x)=ω·x+b

(1)

若线性分类线能够将两类样本准确分开，则应当满足如下条件：

(2)

αi[yi(ω·xi+b)-1]=0

(3)

最后可得到最优分类函数为：

(4)

非线性SVM分类器使用适当的核函数K(xi,xj)实现不同维度间的映射，在不增加计算复杂度的前提下达到线性分类的作用，如图10所示。对应的分类函数也变为：

(5)

图10 非线性情况下的最优分类面

3.3 SVM离线训练

SVM离线训练步骤如下：

(1) 初始化离线采样标准数据类型 首先需要对每条原始采样数据标定各自的类型。对于SVM的原始数据而言，因为需要进行具体到每个位置点的定位，所以对于某个采样位置点采集的数据，标定的类型应该是其采样的位置点编号。

(2) 分类器构建 由于SVM是一种典型的两类分类器，但根据需求需要将类型扩展为多个，实现多分类的功能。因此需要对SVM分类方式进行扩展。目前，构造SVM多分类器主要有两种方式，一种是直接分类，另一种是间接分类。对于间接分类法，可能会出现“数据集偏斜”问题，即正类别数远小于负类别数，造成分类精度降低。所以使用直接分类法实现SVM多分类。

(3) SVM参数的选取 同其他机器学习方法一样，SVM分类器的性能也受到多种参数的影响，主要是惩罚参数C和核函数参数γ。其中C代表对误差的容忍度，C值越高，说明对错误分类容忍度越低，分类器泛化能力越低；γ是核函数内的一个参数，该参数一定程度上影响了数据映射到新的特征空间后的分布。本文在这两个参数的选取上采用二维网格划分法，以便使分类器效果最佳，如图11所示。

3.4 基于区域网格划分的SVM室内定位算法

在线阶段的主要工作步骤如下：

第一步数据获取移动设备主动扫描当前环境中能够探测到的所有AP，并解析出其MAC地址、信号强度、信道、采集时间等信息。

第二步定位请求。手机客户端软件请求定位服务，将第一步中收集到的数据作为参数进行定位POST请求。

第三步数据预处理。服务器网关部分经过无效AP的动态监测和过滤、数据筛选、数据修正等数据预处理工作。

第四步基于区域网格的初定位。服务器定位引擎将上报的所有数据按信号强度降序排列，选取信号强度最好的K个。然后根据这K个AP的MAC地址从区域网格中匹配所属区域。区域有可能一个，也可能多个。一般情况下K=3，如果室内环境比较复杂则应增大K值以提高定位成功率，但是相应的会延长定位的响应时间。

第五步在区域网格内进行SVM精确定位。第四步已经将定位范围缩小到某一个或者某几个区域网格内，则此时只需在区域网格内进行SVM定位，确定用户更精确的位置坐标。该过程使用SVM分类器对测试样本数据进行类型预测，且只挑选出定位所包含的位置点对应的二分类器组。最终通过投票法确定移动终端的位置。若投票得出的位置点为多个，则选取这几个位置点几何上的中心点作为定位结果。

4 定位测试

4.1 测试指标

假设计算得到的定位点的坐标为(xe,ye),而其真实的位置点坐标为(xi,yi),那么定位误差E为：

(6)

(7)

4.2 测试结果

本文使用KNN定位算法与基于区域网格划分的SVM定位算法分别计算包含46个测试点的数据集，其定位算法精度如图12所示。

图12 定位算法精度折线图

两种定位算法的精确度综合比较如表1所示。

表1 定位算法精确度综合比较

基于区域划分的SVM定位算法在46个点的整体定位误差为3.29 m，比基于KNN的定位算法提高了37.45%，并且在绝大多数点的误差基本小于5 m，如果再结合室内地图匹配，基本能够满足室内高精度定位需求。

5 结 语

本文首先对手机Wi-Fi数据的信号特征进行了分析，具体分析了Wi-Fi信号的空间分布特征、强度波动特征、无线广播特征。然后针对具体特征进行了预处理，包含无效AP的动态监测与过滤、数据筛选、数据修正，以得到真实有效的定位数据。最后进行基于区域网格化分的SVM室内定位算法。实验结果证明，采用本文的定位算法能够有效降低实验环境随机噪声带来的波动影响，在不降低定位实时性的前提下，大幅度提高了定位准确度。非常适合类似于交通枢纽、购物广场等客流量大的室内定位场景。