基于四叉树的WiFi室内定位算法研究*

（61773部队 乌鲁木齐 831400）

1 引言

无线通信和移动智能设备的激增推动了基于的位置服务和需求不断增长，相比于室外定位，室内定位技术可能更能改变人类行为；它是许多潜在实际应用的推动者，例如建筑物内的室内导航，智能图书馆或可轻松定位物体的智能工作场所等。虽然诸如GPS、GLONASS、北斗等基于空间卫星的导航定位系统在室外提供高的定位系统，但是来自卫星的GNSS信号在许多室内区域并不总是可以接受的，这限制了它们的使用［1～2］。WIFI系统已被广泛应用于室内环境，WIFI提供对固定网路的本地无线接入，固定网络成本低、部署广泛，并且其室内覆盖仍然快速增加，使用现有的基础设施进行定位是非常有吸引力的选择。

使用WIFI信号定位的技术主要分为两类，第一类技术要求在系统定位之前离线收集标记数据的映射，这主要涉及构建WIFI的RSSI指纹识别环境的无线电地图；第二类依赖于数学建模方法来确定设备位置，如最典型的三边测量就是通过测量用户与各个参考点位置的距离来确定用户的位置，而基于WIFI信号强度RSSI的指纹识别方法一直是近十年研究的热点，因为不需要接入点的视线测量也不需要角度测量，位置的特征在于其检测到的信号模式，因此在复杂的室内环境中实现了高适用性。

传统的KNN算法在计算过程中由于要遍历所有数据，所以存在运算量大，噪声影响大等缺点［3］。本文将四叉树RSS算法应用于室内WiFi定位中并进行算法改进，解决了在四叉树分割期间，相同的地理实体最有可能存储在多个节点中导致浪费索引存储空间。同时地理空间物体的分布可能不均衡导致传统的四叉树生成非常不平衡的树，树结构的不平衡，浪费存储空间。通过Matlab仿真验证，与传统的遍历算法与KD树相比，改进的四叉树算法的精确度明显更高，速度也更快。

2 WiFi室内定位技术

基于WiFi技术的室内定位技术，可实现无线局域网（WLAN）的实时定位。它结合了WLAN和实时定位技术，在室内空间实现复杂的人员定位，监控和跟踪任务。并准确地找到目标。

2.1 指纹定位

“指纹定位”将实际环境中的位置与指纹数据库（FP）相关联，指纹数据库是对应唯一指纹的特殊位置。指纹可以是一维的或多维的。位置指纹可以是多种类型，并且任何“独特位置”特征可以用作位置指纹。对于某个位置的通信信号的多径结构，可以在某个位置检测到接入点或基站，从某个位置检测到的基站信号中接收RSS（信号强度），以及在某个位置进行沟通。这些都可以用作位置指纹，或者它们可以组合成指纹。

RSS或信号的接收功率取决于接收器的位置。RSS很容易获得，因为大多数无线通信设备需要它才能正常运行。许多通信系统需要RSS信息来感知链路的质量，实现切换并适应传输速率。因此，RSS是一种非常流行的信号特性并广泛应用于定位。

假设有一个固定的信号源，在其距离平均不同的距离上，RSS衰减与对数和距离的平方成正比，在最简单的情况下，RSS可表示为

α被称为路径损耗指数，Pt是发射功率，K是一个取决于环境和频率的常数。RSS可用于计算移动设备与AP（基站）之间的距离。虽然提取的距离可用于测量移动设备的三个角来定位，但是由于阴影衰落引起RSS强度变化造成定位较大误差。因此，这种基于RSS的三边测距方法并不是一个好的解决方案［5］。

大多数WiFi网卡可以测量来自多个AP的RSS，可以使用多个接收器的RSS来组成RSS向量作为与位置相关联的指纹。

2.2 指纹定位过程

Wi-Fi指纹定位通常分两个阶段进行：离线数据采集阶段和在线定位阶段，在图1中，我们展示了它的基本操作。在离线阶段，进行现场勘测以收集来自已知位置的参考点（RP）处的不同接入点（AP）的所有检测到的Wi-Fi信号的接收信号强度指示符（RSSI）的矢量，以此类推，直到所有的参考点的数据都被记录到数据库中。所有RSSI向量形成站点的指纹并存储在数据库中以进行在线查询。

图1 指纹的建立

在线定位阶段，用户在他/她的位置采样或测量RSSI向量并将其报告给服务器［6］。使用信号空间中的一些相似性度量（例如欧几里德距离），服务器将接收的目标矢量与存储的指纹数据库进行比较，选择最相似的“邻居”作为估计目标位置，其中指纹是与目标的RSSI紧密匹配的参考点的集合。

之后的在线阶段系统中，将定位移动设备的位置。移动设备位于此地理区域，但确切位置未知。它甚至不可能处于网格点。假设移动设备测量来自各种AP的RSS。假设只测量一个样本，并且从每个AP测量RSS，RSS矢量的值被传输到网络。在图1的示例中，RSS向量是r=［r1，r2］［7］。为了确定移动设备的位置，找到与指纹数据库中的r最佳匹配指纹，则估计移动设备的位置是最佳匹配指纹的位置。随着待定区域变大，离线指纹数据库将获得更多数据，这意味着在线计算需要更多的时间和来源，使用数据挖掘算法可以大大加快计算速度，提高定位精度。

3 四叉树

3.1 传统四叉树

KD树仅支持一维数据，对于标量值，它不能应用于地图上有关x和y方向信息的位置。四叉树（Q-tree）是树数据结构，它每个节点下最多可以有四个子节点，通常将二维空间的一部分划分为四个象限或区域，并将相关信息存储在四叉树节点中。该区域可以是正方形，矩形或任何形状。如图2中四叉树的二维空间结构（左）和存储结构（右）。因此四叉树在数据挖掘中具有重要意义［8～9］。

四叉树的每个节点代表一个矩形区域，如图2黑色根节点上方的图片代表最外围的黑色边框矩形，每个矩形区域可以分为四个小矩形区域，四个小矩形区域作为四个子节点代表一个矩形区域。

图2 四叉树的二维空间结构和存储结构

通过使用四叉树分割网格，我们可以建立一个完整的四叉树如图3所示，假设矩形区域中有N个对象，一个黑点代表一个对象，每个对象坐标都是已知的。使用存储对象的四叉树节点构建四叉树，将所有黑点插入四叉树［11～12］。

图3 建立四叉树

与二叉树类似，使用盲搜索通过以下顺序遍历或逆序遍历搜索某个对象，时间复杂度为O（N）。基于区域中对象的位置的研究，时间复杂度对应于四叉树的深度。与盲搜索相比，搜索区域的对象越多，效果越好。

3.2 优化四叉树

四叉树对区域查询更有效。但如果空间物体的分布不均匀，随着地理空间物体的不断插入，四叉树的水平将不断加深，形成严重的不平衡四叉树。根据每次增加的查询深度，它将导致查询效率急剧下降。

将地理实体信息存储在最小矩形节点中，而不是存储在其父节点中。每个地理实体仅在树中存储一次，以避免浪费存储空间。首先生成一个完整的四叉树，避免在插入地理实体时重新分配内存。加快插入速度，最后释放空节点的内存空间。四叉树的深度通常在4～7之间最佳［13］。

四叉树面临边界点问题，节点中的每个点必须相邻，但相邻点不一定在同一节点中。如图4所示，点A和点B非常靠近。如果A点是我们查询的点，则仅提取节点A中的所有位置是不够的。它还需要找到它的邻居节点。

图4 边界点问题图

与传统的穷举算法和KD树相比，四叉树是一种更好的室内定位算法，能够在速度和准确性方面有更好的表现［14］。与传统算法不同，它有两个阶段。在离线阶段，离线FP数据库将无线电地图保存为2*2，4*4，8*8，… 2n*2n网格。而在线阶段计算欧几里德距离与离线数据库进行比较，可以减少大量计算，加快在线定位，其准确性优于一般算法。四叉树算法定位示意图如图5所示。但是，四叉树算法存在一个很大的问题。如果估计位置划分为错误区域，则不再进行校正。它可能会导致边界上的错误率非常高，我们必须调整划分区域的方法，以降低边界上的定位错误率。同时，四叉树算法无法找到分裂可以适当停止的时刻，甚至不正确的网格可能会被拆分。因此，需要修改四叉树算法。本文算法可以提供一种新的基于多元逻辑回归的算法，具有更高的可靠性和准确性。

图5 四叉树算法定位示意图

在离线阶段中，主要任务与前一阶段相同。我们需要重新划分区域并更正分类，特别是在边界上，这是值得的。根据新的分区定义离线无线电地图（RM）定义为 2×2，4×4，8×8…2n×2n的正方形。无线电地图应以四叉树的形式存储（Φ）。定位的区域分为四个子集群，每个子集代表存储在四叉树中的子节点。对于每个FP的子节点是向量un(n=1，2，3，4)。 Γ ( )tλk表示是否可以拆分当前群集。

在线阶段中，定位过程被认为是基于四叉树的搜索问题。搜索过程描述如表1。

表1 改进四叉树搜索流程

4 仿真计算及结果分析

在本文中采用Matlab软件和使用实测数据对以上算法进行仿真与验证，设置8 AP并在16×16网格中选择随机4 AP，并与传统穷举算法、KD树算法进行对比研究。

4.1 Matlab仿真分析

采用Matlab仿真后的结果曲线如图6所示。

使用穷举算法，KD树和改进四叉树的累积分布函数定位误差曲线如图6a所示。

图6 Matlab仿真结果

纵坐标表示从0%～100%精确定位的概率，而横坐标表示定位误差值从0～10m的距离。红线表示传统的穷举算法，绿线表示KD树，蓝线表示改进四叉树。我们可以看到，这三条曲线是绝对收敛的。但收敛速度不同，改进四叉树速度最快，穷举算法最慢。值得注意的是，KD树的曲线比其他两种算法更平滑。原因可能是KD树分类算法的随机性大于其他两种算法。改进四叉树已成功定位，定位率达到100%，定位误差为4m，而KD树需要6m定位误差才能达到同样的效果。传统的穷举算法甚至需要10m的定位误差。曲线所包围的区域越大，定位效果越好。结果表明，使用改进四叉树算法，位置精度明显优于其他方法。

4.2 实测数据验证

通过用测量数据替换模拟数据来进行实验，实验结果如图7所示。虽然存在信号噪声和干扰，但实验结果仍具有代表性。如图7（a）所示，三条曲线的收敛速度较慢。这意味着在实际的室内定位中，位置的准确性较低，但是改进四叉树算法仍然比其他两种算法具有更好的准确性。改进四叉树成功定位率达到100%，定位误差为6m。

类似地，随着计算量的增加，实际的室内定位变得越来越大，传统的穷举算法仍然需要大量的计算，如图7（b）所示。当要定位的区域变得足够大时需要很多时间。改进四叉树的性能仍然稳定，蓝色曲线的上升趋势保持平稳，这意味着改进四叉树比其他两种算法使用更少的时间来完成定位。值得注意的是，曲线不如模拟结果稳定。原因可能是数据收集过程中的错误数据，但曲线趋势仍然合理。错误数据的原因可能是实验室里走动的人，或者其他人产生的未知WiFi信号，例如有人打开手机热点。

图7 实测数据验证结果

5 结语

本文在依据聚类和分类理论实现室内WiFi定位中提出一种基于改进四叉树RSS定位算法。通过采用传统穷举算法、KD树等传统算法进行对比，采用Matlab仿真和采集的数据进行实测实验，实验结果表明，与传统方法相比基于改进四叉树RSS定位算法在WiFi室内定位中可以提高室内定位的准确性，有效地解决边界条件问题，提高了定位效果，同时可以节省大量的在线计算时间，加快定位速度，在实际应用中具有重要意义。