CCIPOS：一种面向WiFi指纹定位的聚类辅助与中心连接插值方法

《Future Generation Computer Systems》：CCIPOS: A Clustering-aided and Center-connected Interpolation Method for WiFi Fingerprinting

　　

摘要

WiFi指纹识别因其成本效益而成为室内定位的流行解决方案。然而，要实现高精度和稳定性，需要从密集分布的参考点（RP）收集大量数据，这可能是资源密集型的过程。插值是一种常用的技术，可以帮助在不增加高昂成本的情况下增加RP的数量。然而，生成插值点（即虚拟参考点（VRP））的位置可能是一个重大挑战，因为它可能会影响定位结果。本文提出了一种新方法，该方法使用混合聚类算法结合中心连接插值方法（CCIPOS）来自动高效地生成VRP，以适应不规则的RP分布。首先，该方法使用两阶段聚类算法，包括k-means算法和Voronoi图，将指纹数据库（DB）中具有相似特征的RP分组到同一聚类中。然后，使用提出的中心连接算法估算每个聚类内的VRP位置。为了满足每个VRP的WiFi数据，应用了反距离加权法（IDW），这是一种简单但有效的插值方法。通过不同公开数据集的实验结果表明，CCIPOS方法有效地将更多VRP生成到原始指纹DB中，但大大减少了查找用户位置所需的时间。CCIPOS平均将DB中的RP总数增加了约七倍，平均定位误差减少了约6%，计算时间减少了近90%。这项研究展示了增强WiFi指纹DB的可行性，特别是在大型和复杂的环境中。

引言

随着全球导航卫星系统的快速发展，室外定位变得越来越可靠。然而，这些系统的性能取决于与卫星收发器之间的视距（LoS）通信，这在室内环境中可能会因信号遮挡、散射和各种障碍物而严重受阻。这一局限性导致了对能够提供建筑物内准确位置信息的室内定位系统的迫切需求。在各种用于室内定位的技术中，基于WiFi的解决方案因其广泛部署和可以利用现有基础设施而无需额外安装硬件而受到广泛关注。基于WiFi的系统有两种类型：几何型和指纹识别型。

基于几何的方法，例如到达角度（AoA）、到达时间（ToA）和到达时间差（TDoA），重点在于测量接收器（例如智能手机、平板电脑或笔记本电脑）与多个具有预定义位置的WiFi接入点（AP）之间的距离。然后，用户的位置基于几何方程进行估算。尽管这些方法可以提供高精度的定位，但它们需要专业硬件和大量校准，并且其性能严重依赖于理想的LoS条件。相比之下，基于指纹识别的方法，如WiFi指纹识别，提供了一种更动态的解决方案，不依赖于AP的位置，因此这些方法适用于AP密度有限的环境。WiFi指纹识别分为两个阶段：在离线阶段，通过在预定义的参考点（RP）处从AP收集接收信号强度（RSS）值来构建WiFi指纹数据库（DB）。在在线阶段，通过将未知位置收集的数据与创建的指纹DB进行比较来执行用户定位，并使用定位算法。尽管WiFi指纹识别具有成本效益和易于部署的特点，但其性能需要大量的WiFi数据收集过程来维持定位精度和稳定性，特别是在大面积区域。

为室内定位构建WiFi指纹DB是一项具有挑战性的任务，因为RP的数量随着部署区域面积的增大而成比例增加。虽然密集的RP可能有助于提高定位精度，但它们给数据收集过程带来了很大的负担。到目前为止，已经尝试了几种方法来减轻构建WiFi指纹DB的负担。众包方法[1,2]利用大量用户的移动模式来减少数据收集的负担。虽然这种方法减少了工作量，但它受到用户位置映射不准确、参与者专业知识不一致和采样密度不均匀等问题的制约。机器人系统[3,4]完全自动化了数据收集过程，提供了精确性和效率。然而，这些系统通常不适合具有复杂架构的环境，并且实施成本很高。信号传播模型[5,6]利用室内楼层平面图，通过整合多条轨迹上的路径损耗来创建指纹DB。虽然这种方法消除了大量手动数据收集的需要，但由于室内环境的复杂性和可变性涉及许多不可预测的参数，因此在实际条件下难以实施。

另一方面，稀疏收集方法通过降低收集点的密度来减少数据收集的工作量，但仍然无法消除手动数据收集的需求。然而，这种方法需要对环境进行不太详细的表示，并且适用于数据增强技术，这些数据增强技术可以增强DB并帮助填补稀疏数据收集造成的空白。在有效的数据增强方法中，插值方法从研究小组那里获得了极大关注。这些方法通过生成具有估计WiFi数据的虚拟RP（VRP）来改进WiFi指纹DB，这些虚拟RP填补了数据空白[7]或通过估计已知点之间的信号值来增强数据[8]，以使数据密度均匀。这些方法提供了一种有效且实用的方法来增强DB密度，然而，这种方法的一个重大挑战是生成VRP的位置，因为它们的位置取决于几个因素，如真实RP的数量、分布和密度。此外，在实际场景中，RP通常是不规则分布的，这意味着它们不是按照矩形网格排列的，而是根据楼层平面图的结构来排列的。因此，迫切需要自动生成VRP来增强插值过程。

本文提出了一种名为CCIPOS的创新方法来增强WiFi指纹DB并有效提高WiFi指纹识别技术的定位精度。在离线阶段，我们使用k-means和Voronoi图算法的集成对离线DB中的WiFi数据进行聚类。对于每个聚类，使用提出的中心连接算法自动估计VRP，这解决了随机放置或均匀网格化VRP的不灵活性和空间不一致性问题。随后，通过应用反距离加权（IDW）插值算法来估算这些VRP处的WiFi数据，以确保指纹DB的空间连续性和信号一致性。最后，创建了一个新的聚类插值WiFi指纹DB。定位阶段包括两个步骤：粗定位和精定位。粗定位过程确定估计的用户位置落在哪个聚类中。随后，精定位过程确定用户在已识别聚类中的具体坐标。本研究的关键贡献总结如下：

• •
  我们通过结合基于RSS的k-means聚类算法和Voronoi图划分来集成混合空间聚类，根据信号相似性和地理位置对RP进行分组，从而产生空间一致的聚类，更适合插值和定位任务。
• •
  我们提出了一种新的中心连接算法，在每个聚类边界内自动在RSS插值之前生成VRP，这使得可以为规则和不规则RP分布创建VRP，而无需手动放置VRP。
• •
  我们应用IDW插值方法来生成每个VRP的WiFi数据，由于其简单性和合理的性能，这增加了指纹密度同时保持了空间一致性。
• •
  我们使用五个不同的公开WiFi指纹数据集评估了所提方法与其他比较方法的有效性和鲁棒性。

本文其余部分组织如下：第二节回顾了相关工作。第三节详细描述了研究中使用的方法论。第四节讨论了实验结果。最后，第五节总结了论文并提供了未来研究方向。

章节摘要

相关工作

许多研究提出了插值方法来增强WiFi指纹识别中的数据收集过程。然而，关于VRP的自动生成和放置的研究有限。RP的分布可以分为两种类型：规则分布和不规则分布。规则分布指的是方形或矩形等网格排列[9,10]。相比之下，当RP散开且没有特定模式时，就会发生不规则分布[11,12]，这在

方法论

如上所述，先前的研究尚未专注于解决VRP自动定位的问题。本研究提出了CCIPOS方法来增强WiFi指纹DB，同时提高定位精度并减少计算时间。CCIPOS的详细模型如图1所示。

图1通过WiFi指纹识别模型的离线和在线阶段展示了CCIPOS的框图。首先，在前一阶段，稀疏的WiFi指纹DB是

数据集

本文描述了使用五个数据集进行的实验：TUJI [21]、TUT 1 [22]、TUT 2 [23]、TAU [24]和UJIIndoorLoc [25]。TUT 1、TUT 2和TAU在坦佩雷大学（芬兰）收集，而UJIIndoorLoc和TUJI在胡安·卡洛斯一世大学（西班牙）收集。选择这些数据集是因为它们具有不同的特征，包括不同的场景大小、每个RP收集的RSS数据量、单层与多层环境、来自单个设备还是多个设备

结论

本文提出了CCIPOS，一种通过数据聚类和自动生成VRP来增强WiFi指纹识别性能的新方法。在离线阶段，创建增强的指纹数据库。通过使用k-means聚类结合Voronoi图，将具有相似特征的RP划分为聚类。接下来，使用提出的中心连接方法和IDW插值在每个RP聚类内确定VRP及其对应的RSS值。

CRediT作者贡献声明

Trung Vu-Thanh：撰写——初稿，软件，方法论，概念化。Jing He：撰写——审阅与编辑，监督，方法论，资金获取，概念化。Khanh Nguyen-Huu：撰写——初稿，可视化，形式分析。Ninh Duong-Bao：撰写——审阅与编辑，验证。Seon-Woo Lee：撰写——审阅与编辑，可视化。Luong Nguyen Thi：撰写——审阅与编辑，监督，资金获取。

Trung Vu-Thanh于2014年获得越南河内大学理学学士学位，2019年获得中国湖南大学理学硕士学位，专业均为计算机科学。他目前正在中国湖南大学计算机科学与电子工程学院攻读博士学位。自2021年起，他一直在越南国家大学河内分校跨学科科学与艺术学院担任讲师。他的研究兴趣包括Android应用开发、软件

Trung Vu-Thanh|Jing He|Khanh Nguyen-Huu|Ninh Duong-Bao|Seon-Woo Lee|Luong Nguyen Thi

湖南大学，计算机科学与电子工程学院，中国