基于嵌入式平台与kNN算法的室内定位研究

张辉 何倩

（安徽师范大学皖江学院 电子工程系，安徽 芜湖 241000）

0 引言

随着城市的发展越来越快，高楼林立已成为许多城市的基本配置。有学者指出，目前对于大多数人来说，处于室内的总时长约为一天的70%左右。由于室内建筑的空间复杂度不断增加，已有的定位技术已经不满足当前的定位需求，室内定位技术的改革引起了关注。传统的室内定位技术硬件成本高、软件上代码执行效率低。当前的定位技术[1]，定位精确度不高，需要使用其他的算法辅助定位。三边定位算法是目前使用较多的定位算法。三边定位的原理简单，实现也很简单，但缺点是设备成本高、可移植性差等。

1 总体结构

本系统的硬件设计是由电子标签、阅读器、天线和嵌入式平台构成，总体结构如图1所示。电子标签通过天线与RFID（Radio Frequency Identification）阅读器建立无线连接，之后，将测得的数据传送给嵌入式平台，平台对数据进行处理并输出最终的定位结果。软件设计是基于嵌入式平台的Ubuntu MATE环境下，实现kNN（k-Nearest Neighbour）定位算法。定位精度和数据处理速度都在一定的程度上得到提高。本设计从硬件与软件两个角度对室内定位的精确度以及算法的数据处理速度都进行了一定的提升，适合做大范围推广。

图1 总体结构图

2 组件简介

2.1 RFID阅读器

RFID全称为射频识别，即射频技术[2]，其组成是阅读器，电子标签和天线[3]。阅读器是RFID的读写终端设备，通常与控制终端，比如电脑等处理设备相连，对接受到的信息进行分析，获得电子标签的具体位置信息，并且可以更改电子标签的内部信息。电子标签的内部芯片编码信息不同，主要用于身份鉴别，当其进入磁场中时，可以利用电磁感应获得感应电流[4]，从而获得能量发送自身内部芯片中的信息。天线可以进行模拟信号与数字信号的双向转换。发射器通过天线向某一区域发射电磁波，该天线用于查找电子标签并获取其内部信息。在接收到电子标签的响应信息后，电磁波信号可以转换成电信号传输到发射机。

图2 超高频RFID四通道阅读器

阅读器作用原理如图2所示，首先，对设备进行连接和供电后，阅读器以天线为介质将电磁波发送到目标区域，电子标签收到信息并响应。其次，阅读器通过天线接收到信息以后，对收到的信息开始进行处理，将其转换成电子标签的位置信息。最后，以信号强度的形式显示到嵌入式平台上。此过程连续循环，实现位置实时更新。

该技术具有以下特点：一是具有非接触性，能够做到远距离定位，受到外界的干扰较小，便于维修管理，易于操作。适用于公共场合，方便与其他平台相结合，进行开发应用，衍生更多的功能。二是无需人工干预，系统利用射频技术，可自动识别信号覆盖范围内的多个目标的信息，适应环境能力强，定位精度高，准确性好。不仅可以用于对物体的定位，比如车辆，物流等。三是还可以用于对人员的定位，比如在一些重要场合对人员进出进行系统控制，对范围内的某人进行快速的寻找定位;主要通过无线通信技术对目标进行定位，目标的具体位置以及身份信息通过阅读器获取，相较于当下的GPS定位技术，成本较低且运行简单，功耗较小，且不受室内复杂环境的影响等优点。本系统的构建便是基于此技术，利用了RFID的室内定位优势创建的室内定位系统，并将其在具体上层应用中实现。

2.2 嵌入式平台

嵌入式平台选用的是Raspberry Pi 3B+款。Raspberry Pi是一款基于ARM的微型电脑主板，其结构如图3所示，自带4个USB2.0接口、一个以太网接口和MicroSD插槽。内存是1GBLPDDR2 SDRAM。CPU是1.4GHz 64位4核ARM Cortex-A53 CPU。存储使用的是Micro-SD。

3 实验模型建立

3.1 实验场景图

本实验基于RFID技术与Raspberry Pi的平台技术进行，在室内进行小规模的实验，以小方格表示一个最小单元坐标单元，每个位置都用三个电子标签进行多次测量取平均数据。

划出一块10 dm×10 dm的正方形区域作为实验，各个边平均分成10份，也就是将整个区域分成100个小块，如图4。A、B、C三个位置都放置天线，RFID阅读器连接并控制天线对电子标签信息进行读写后转换成RSSI数据，且将值传到Raspberry Pi中进行数据处理。

图3 Raspberry Pi结构图

图4 实验环境模拟图

3.2 RSSI信号强度

需要设置一个RSSI仿真环境接收RSSI数据集，建立一典型的离线数据库，进而实现在线定位。前期对模型进行了数据测量，经多次测量得到了多组值，构成了一个离线数据库。

在正方形区域上选择三条边，分别对应着三个方向，实验中记为A，B，C三个位置。在对应的三个位置上分别测得每个小块的信号强度，并依次进行记录。实验数据如表1—表3：

A位置：

A位置接收到RSSI数据的特点是随着横纵坐标的增加而增强。

B位置：

B位置接收到RSSI数据的特点是随着纵坐标的增加而减弱，随着横坐标的增加而增强。

C位置：

C位置接收到RSSI数据的特点是随着纵坐标的增加而增强。随着横坐标的增加而减弱到中心点（1，5）（1，6）处 RSSI数据减到最小，后随着横坐标的增加而增强。

表1 A位置测试采集数据

表2 B位置测试采集数据

表3 C位置测试采集数据

3.3 数学模型

3.3.1 欧氏距离模型

欧几里德距离在二维平面内都可以表示两点之间的距离。

二维空间的公式：

其中，ρ为点（x2，y2）与点（x1，y1）之间的欧式距离；|X|为点（x2，y2）到原点的欧氏距离。

3.3.2 kNN数学模型

k近邻中的分类决策规则通常采用多数表决，这意味着输入实例的类由最相似的k个相邻训练实例中的大多数类决定的[5]。多数表决规则（Majority Voting Rule）有如下解释：如果分类的损失函数为0-1损失函数，分类函数为：

那么误分类的概率是：P（Y≠f（X））=1-P（Y=f（X））

对于所给的实例x∈X，它最邻近的k个训练实例点构成的集合 Nk（x）。 如果涵盖 Nk（x）的区域类别是cj，那么误分类率是：

为了使误分类率最小也就是经验风险最小，就要使∑xi∈Nk（x）I（yi≠cj）最大，意即大多表决规则与经验风险的最小化是等同的。

3.3.3 kNN的应用

k最近邻算法（kNN）最常用的应用是位置指纹法：使用最近的k个RSSI的指纹位置估计当前位置。通过比较特征RSSI数据的不同，定位标签的位置。kNN算法的关键就是从数据中提取出一个从特征到标签的映射关系模型[6]。

对于在线RSSI数据s，算出它和所建立的指纹库中每个 RSSI数据{s1，s2，…，sM}的间隔（比如欧氏距离），选择最邻近k个位置指纹（一个指纹是一个RSSI数据与一个位置的对应）。

对于kNN回归，选取k个指纹的位置坐标X与Y分别计算平均值，即为定位结果。最终，将标签的位置信息以（X，Y）的形式打印在Raspberry Pi的显示屏上[7]。

对于kNN划分，把所取定位的范围分成10 dm×10 dm大小方格，一个方格视为一个类别，分别用网格标号来替代，k个网格标号都进行投票和统计，并且选择具有最大投票数的网格用于定位结果。

4 kNN算法实现

一个样本x与样本集中k个最邻近样本中的多数都属于另一个类别Y，那么也就是说这个样本x也含于类别Y，并且还包含这个类别样本的特性[8]。简单来说，就是x属于类别Y，且具有Y的特性。

依据该理论可以得到结论，kNN是用测量不同特征值之间的间隔再进行分类，并在决策样本类别时，只需要参照样本周围k个近邻样本的类别。所以该方法更适合用于处理样本集存在很多重叠的场合，例如聚类分析、预测分析、文本分类、降维等。算法流程如图5所示。

图5 kNN算法流程图

kNN算法的伪代码实现：

4.1 具体实现

具体实现分为以下步骤：a.串口传输数据；b.读入数据；c.数据预测；d.数据比较。a.串口传输数据代码如下所示。

b.读入数据的部分结果，如图6所示。

图6 读入数据

代码如下所示。

c.数据预测得到特征值，运行结果如图7所示。

图7 数据预测

代码如下所示。

d.数据比对得出结果，如图8所示。

图8 数据处理输出结果图

代码如下所示。

4.2 实验过程

（1）Raspberry Pi通过串口接收到RSSI数据，并将数据存到TXT文档中。接收到的数据如下：A69.3，72.0，72.0B。

A和B是为了保证收到的数据的完整性，只有当收到的数据中以A开头B结尾才读取数据，防止因为数据丢失等问题造成的定位精度变大。69.3，72.0，72.0是RFID在定位点采集到的三个RSSI数据。

（2）导入接收的RSSI数据，分析处理。通过串口接收的数据可能会产生数据丢失的情况，为了解决这个问题我们写了一个协议用于处理保存这个数据。

（3）将处理好的RSSI数据进行分类和处理，并输出坐标信息，如图9。图中在TXT文本中存储接收到的数据，在命令行中运行Python程序进行数据处理。输出的第一行显示的是这组RSSI数据的特征值，第二行显示的是与这组RSSI数据的特征值最接近的坐标点，最后一行输出定位结果，即该组值所定点的坐标位置。

4.3 实验论证

实验的最后数据处理部分选用了三种方法，并对处理后的数据进行比对，选取了其中精度最高的方法。比对结果如表4。

研究发现，该算法在RFID信号覆盖范围较弱的区域内定位精度较低，在RFID信号覆盖较强的区域内定位精度较高[9]。通过选取16个点（点的位置如图10），分别测出其RSSI数据，运行程序输出定位结果，定位结果如表5所示。

图9 Raspberry Pi上输出的定位信息

表4 数据处理方法数据对比表

图10 选取的测试点位置

表5 定位结果图

通过搭建模型进行测试,得出表1—表3的数据，作为离线数据库，用于实验测量时作为比对数据，并且进行多次重复实验，取得最为接近的数据值。为了验证该实验的定位精度，进行了多组实验数据的比对（如表5）和与其他定位算法的定位精度的比对。比对结果如表6。由此可知，该方法的确在一定程度上提高了定位精度。

表6 定位算法精度对比表

5 结论

研究主要设计了一种基于嵌入式平台与kNN的室内定位技术[10]，较好的解决了室内定位精确度不高的问题。由于没有经过更大更复杂的区域验证、实验数据不够全面等，设计本身还存在一定不足，有待后续进一步改进。过程中，通过实验对kNN算法进行了具体验证，实验结果显示与嵌入式平台上代码运行分析的结果基本一致。由此可见，两者的结合能够实现较高精确度的定位，这也体现了在如今大数据时代，特别是伴随5G网络的建设，嵌入式平台与边缘计算的结合可为人们提供更加智能、便捷的产品和服务。