基于PSO—KNN的WiFi—RSSI指纹算法的四旋翼室内定位

孙瑶 王磊 王延召 周云天 陶少俊

摘要：针对室内无GPS下的四旋翼定位问题，文章提出一种基于PSO-KNN的WiFi-RSSI指纹算法。运用粒子群算法对1；最近邻算法的权重进行优化，去除信号不稳定产生的干扰项，快速选择全局最优权值，实现室内四旋翼的较高精度定位。与传统的NN和KNN比较分析表明，文章所设计基于PSO-KNN的WiFi-RSSI指纹算法可搜索到全局最优的权值，有效提高分类的精度，降低定位误差。

关键词：室内定位；K最近邻算法；粒子群算法；四旋翼飞行器

近年来，得益于非线性控制理论的发展和微电子技术的进步，使得精确控制如四旋翼无人机这样的非线性、欠驱动系统成为可能，其所具备的在三维空间运动的能力带来了新的研究挑战。四旋翼在军民领域表现出极强的应用潜力。例如战场上对未知环境的侦察以及辅助打击，电力线路的自主巡检，偏远地区的快递投送等。但在室内飞行时，卫星信号无法穿透墙体，传统的GPS定位方案难以满足四旋翼的自主飞行要求，从而制约了其在室内的应用范围。

WiFi，ZigBee。Bluetooth和UWB等无线通信技术被用于实现室内定位，成为工业界和学术界的研究热点[1]。室内定位也是小型无人机在室内应用的关键技术之一[2]。根据定位方法的数学原理，常用的方法有基于信号到达的角度（Angle of Arrival，AOA）、基于信号到达时间（Time ofArrival，TOA）、基于信号到达时间差（Time Different ofArrival，TDOA）、位置指纹法。三角定位法设备复杂且价格昂贵，容易因信号不稳定而导致位置定位不精确。TOA的定位方式因为多径效应和时钟分辨率低，定位效果较差。而基于接收的信号强度指示（ Received Signal StrengthIndication，RSSI）指纹定位法是目前主流的WiFi定位方法[3]，不需要将信号强度RSSI置换成距离，对环境复杂的室内空间定位时精度较高。它通过与指纹数据库中事先存储的不同位置信号特征参数进行对比，估算所在位置，定位精度取决于校准点的密度。目前广泛使用的匹配算法有近邻算法[4]、K最近邻算法[5]、加权近邻算法[6]、贝叶斯概率算法[7]、神经网络算法[8]、SVM算法[9]）等。但以上算法存在计算量大、难以保证实时性、精度不高、对输入数据的表达形式敏感等缺点。本文利用粒子群算法结构简单、收敛速度快、搜索能力强、易于工程实现的特点，提出一种基于PSO-KNN的WiFi-RSSI指纹算法。

在定位过程中，四旋翼无人机停在指定位置，通过机载无线定位芯片测定其周边的无线信号特征参数，发回上位机。上位机通过离线指纹数据库进行匹配计算，将计算出的四旋翼与目标点的位置信息发送给四旋翼。机载微控制器接收到控制指令后，控制四旋翼飞向目标点。1WiFi-RSSI指纹算法概述

WiFi-RSSI指纹算法主要思想是利用来自于无线局域网中路由器产生的RSSI在室内分布的差异性，为每一个地点产生一个RSSI指纹并录入离线指纹库。在线定位时，将当前的信号特征与RSSI指纹库匹配，确定目标位置。如图1所示，整个过程分为离线数据采集建库和在线定位两个阶段。

2 改进WiFi-RSSI指纹算法描述

2.1离线数据采集建库

离线数据采集建库是指针对待定位区域建立指纹数据库。首先在室内待定位区域内布置6个无线访问接入点（Access Point，AP），按照间距1 m划分该区域并标记参考点位置，然后使用设备遍历所有参考点，并记录下每个参考点接收的AP的信号强度、媒体访问控制（MediaAccess Control，MAC）地址、参考点的物理位置等信息，存入指纹数据库，每个指纹唯一对应一个地址。数据采集过程中，我们对采样数据取均值，以提高离线指纹数据库的精确度。

2.2在线定位

上位机通过PSO-KNN算法与指纹数据库中的数据信息进行匹配计算。首先初始化粒子群，将式（1）作为目标函数进行优化。式中，Di表示定位时获取的指纹矢量与数据库中第i个指纹矢量的欧氏距离，Wi表示其权重。

然后计算每个粒子的适应值，式（2）和式（3）更新粒子速度和位置，求出每个粒子的个体最优，进而求出整个群体的全局最优值，从而匹配出最相似的数据信息用于定位结果计算。

式中，c1、，c2为加速常数；r1，r2为区间[0，1]内的随机数：Xi（xil，xi2，…，xid），Vi（vi1，vi2，…，vid）表示粒子i当前的位置与速度：Pi（pi1，pi2，…pid）表示粒子当前的最优位置；Pg（pg1，pg2，…，pgd）表示整个粒子群的全局最优位置；k为迭代次数。

3 仿真实验

定位区域为15m×20 m的方形区域，AP和参考点部署如图2所示。图中圆点处为参考点，五角星处为布置的AP，边界上菱形为所标记的四旋翼，圆柱为目标点。每个参考点采样5次后取均值，构建离线指纹数据库，目标点在定位区域内随机生成。参数取值如下：

距离最小的指纹矢量个数K=4，初始种群个数N=50，迭代次数ger=100，惯性权重w=0.8，自我学习因子c1=1.494 45，群体学习因子c2=1.494 45。

NN算法[4]、KNN算法[5]、PSO-KNN算法的平均误差曲线如图3所示。3种算法定位误差对比分析如表1所示。

从图3和表1可以分析出，相对于NN算法、KNN算法，利用粒子群对权重进行优化PSO-KNN算法精度更优且误差波动较小。部分参考节点误差较大是由于此部分节点所在区域信号强度指纹区分度不明显。

4 结语

本文在原有WiFi-RSSI指纹算法的基础上，提出一种基于PSO算法对K最近邻算法的权重进行优化的改进WiFi-RSSI指纹算法。仿真结果表明，该方法可快速有效地搜索出全局最优的权重值，去除因信号不稳定引起的干扰项，有较好的分类精度，并获得较高的室内定位精度。

[参考文献]

[1]高业，何敏，室内定位技术研究综述[A.江苏省测绘地理信息学会、江苏省测绘工程院.2017年度江苏省测绘地理信息学会GPS、大地专业委员会学术年会暨JSCORS技术交流大会论文集[C].南京：江苏省测绘地理信息学会、江苏省测绘工程院，2017：5.

[2]陈小龙，唐强，车军，等基于人工视觉的四旋翼飞行器室内定位与控制[J].兵工自动化，2012（5）：61-64.

[3]YUAN Y， PEI L， XU C， et al.Efficient WiFi fingerprint traimng using semi-supervised learning[C].Corpus Christ： Ubiquitous Positioning Indoor Navigation and Location Based Service （UPINLBS）， 2014： 148-155.

[4]CAMPOS R s，LOVISOLO L， DECAMPOS M L R.Wi-Fi multi-floor indoor positioning considering architectural aspects and controlled computational complexity[J].Expert Systems with Applications， 2014 （14）： 6211-6223.

[5]畢京学，甄杰，汪云甲，等高斯函数定权的改进KNN室内定位方法[J]测绘通报，2017 （6）：9-12，35.

[6]孙新，欧阳童，严西敏，等基于训练集裁剪的加权K近邻文本分类算法[J].情报工程，2016 （6）：8-16.

[7]彭玉旭，杨艳红，一种基于RSSI的贝叶斯室内定位算法[J].计算机工程，2012 （10）：237-240.

[8]李瑛，基于BP神经网络的室内定位技术研究[D]长沙：中南大学，2007.

[9]周锦，李炜，金亮，等基于KNN-SVM算-法的室内定位系统设计[J].华中科技大学学报（自然科学版），2015 （Sl）：517-520.