一种基于WiFi信号特征的聚类过滤定位算法研究

2018-11-23蔡炯炯沈涵生张文辉王子辉

浙江水利水电学院学报 2018年5期

蔡炯炯，沈涵生，张文辉，王子辉，袁琳

(1.浙江科技学院自动化与电气工程学院，浙江杭州 310023；2.浙江大学电气工程学院，浙江杭州 310013；3.浙江大学苏州工业技术研究院，江苏苏州 215010)

0 引言

随着大型室内车库的增加，研究室内车库实时定位与引导技术，具有重大现实意义和较大的市场价值.WiFi技术因为基础设施完善，普遍应用于现代生活中.近年来，定位在生活中广泛应用，基于移动通信网定位技术的紧急救援服务[1]；通过卫星通信定位对海洋环境的监测[2]；针对WiFi室内定位更多的是对定位算法的研究及改进.文献提出一种改进的RSSI多维标度室内定位算法，通过平面四参数模型进行坐标转换，运用粒子优化参数，该算法能够满足室内定位跟踪及低成本定位系统的需求[3]；陈斌涛等根据用户使用状况和定位参考点的布置情况动态更新WiFi指纹数据库，解决了环境动态变化对信号强度值的影响[4]；郑学理提出PDR和RSSI的室内定位算法，该算法在在RSSI定位抗噪声能方面，以及融合定位精度和滤波实时性方面取得良好的效果，降低定位误差[5]；张文学在WiFi室内指纹定位方案中根据WiFi信号强度的区间变化，提出一种指纹过滤方案，该文献中并未考虑WiFi传播信号强度与传播距离之间的关系，对定位精度产生一定的影响[6].

综述，文献资料显示更多的是采用不同的定位方法用以改善定位精度，而未改善定位速度.本文基于此方面，根据研究了信号特征变化，采用信号聚类对指纹数据库进行指纹数据归类划分，确定了定位目标在一个初选区域；其次对该区域内不同RSSI区域波动进行了对比，提出了过滤区间的自适应方法，将该过滤区间取值方法应用于多次筛选的指纹数据库匹配算法，筛选过后指纹库中剩下少量的数据组；最终计算采样点与少量数据组之间的最小欧氏距离得出目标精确位置.

1 信号特征分析

由于室内车库环境复杂，采集RSSI信号强度时，RSSI存在不同幅度的波动.实验中对不同RSSI均值进行多次测量后作出以下数据统计,分别对均值为-35 dBm、-40 dBm、-45 dBm、-50 dBm、-55 dBm、-60 dBm、-65 dBm、-70 dBm分别进行变化统计(见图1)，其中，β代表信号波动幅度，α代表不同信号强度均值.

图1 不同RSSI均值的波动幅度变化

实验中根据大量数据统计得出：接收信号强度值在不同RSSI均值的波动范围不同，具体如图1所示.说明在不同信号强度值时，其波动范围也是不同的，当信号强度值逐渐变小时，其波动逐渐增大.

2 信号聚类过滤算法

2.1 信号聚类过滤算法流程

基于上述信号波动规律，本文提出一种信号聚类过滤算法.算法步骤如下：第一步，信号聚类，采用距离作为相似性的评价指标，即认为两个对象的距离越近，其相似度就越大，算法认为簇是由距离靠近的对象组成的，因此把得到紧凑且独立的簇作为最终目标，根据采样AP的最强信号强度和距离之间关系，本文以每个信号接入点(AP，access point)所采集的信号强度区间为(-65 dBm，-35 dBm)作为聚类中心，在该信号区间内信号波形相对稳定，以此划分指纹数据库为初选区域，进而在线定位阶段减少位置指纹数据库搜索量；第二步根据不同RSSI波动幅度在初选区域中进行指纹点多次过滤得到少量指纹数据；最终计算少量指纹点与采样点之间的最小欧式距离，完成位置匹配，具体流程(见图2).

图2 信号聚类算法流程图

2.2 信号聚类

在给出n个数据样本中，随机选择K个初始聚类中心Zj，j=1,2,3,…,K.K值决定了初始质心的数量.选择最优的K值没有固定的公式或方法，需要根据实际情况决定，需要注意的是选择较大的K值可以降低数据的误差，但是会增加拟合的风险.

以下是不同信号强度均值的波动幅度，将K值定义为2进行聚类，并随机选择3和5作为两个类别的初始质心.

(2)求解每个数据样本与初始类中心的距离D(xi,Z)，i=1,2,3，…，n，若满足D(xi,Z)=min{D(xi,Z),i=1,2,…,n}，那么xi∈wk；

(4)判断：如果|Jc(I+1)-Jc(I)|<ξ，那么表示算法结束，反之重返第(2)步骤执行.

(5)算法终止条件：将两组中数据的均值作为新的质心，并重复之前的方法计算每个信号强度波动幅度到质心的距离.

在算法开始的第一步中提到迭代计算每个数据到质心的距离，直到新的质心和原质心相等，算法结束，在使用上一步分组的均值3.5和12.5作为质心，并计算波动幅度到质心的距离.以表1为算出的结果列表.

表1 算法终止条件

按照波动幅度到新质心的距离进行分组，并计算每组的均值作为新质心.这里两组的均值新质心与原质心相等，则算法终止.

本文采用了聚类算法对不同信号强度值的信号波动进行分类，得到对信号波动的了分成两类，即信号波动值在2 dBm到5 dBm范围内为第一类，信号波动值在12 dBm分为第二类.从信号波动幅度角度可以得出，波动范围有大小之分，而不同波动范围对应了不同信号强度，当波动幅度进行分类，即对应的不同信号强度值也随之分类.信号强度值越大，其波动范围越小，信号强度值变化相对稳定；信号强度值越小，其波动范围越大，信号强度值变化相对较大.

在线定位阶段，本文首先随机采样得到六个不同信号强度值，根据信号波动进行分类，下一步根据不同信号强度的波动范围设置过滤区间，最终完成快速定位.

2.3 自适应阈值调整

实验中采集信号强度值时产生一定的波动，但波动存在一定的范围，在该范围内不会出现偏离过大的值.实验中大量数据分析得出：RSSI采样值在(-65 dBm，-35 dBm)为有效区间内，该区间内RSSI波动相对平稳，当RSSI值小于-65 dBm时波动幅度较大，对指纹数据库过滤效果不佳，所以选择(-65 dBm，-35 dBm)内的数值作为有效信号强度值[7].

实验中对每个采样点(本实验采用六个接入点，故每个采样点可采集6个RSSI数值)中取其中最大的3个在有效区间内的RSSI值进行过滤，接收AP信号强度的个数小于3，对定位精度有一定的影响[8].若该组有效信号强度值个数小于3，则需进行重新采样.在一定的波动区间[RSSI-t,RSSI+t)，来找出指纹数据库中相关性的点，其中t为波动范围，根据不同时间段的t值变化对指纹数据库进行过滤，t值(见表2).

表2 不同信号强度区间t取值

通过上述方法，信号过滤能够快速得到与测试位置相关性较大的一组或者若干组的指纹数据，用这些数据辅以基本的定位算法，可以减少基本算法匹配时所需的点，同时剔除大部分与定位无关点，在保证定位精度不变的同时，减少了大量的计算过程.

2.4 自适应阈值的算法流程

(1)设置自适应过滤区间的波动范围t值；

(2)判断采样点A中6个数据中是否在(-65 dBm，-35 dBm)之间，采样值在该区间为有效值，采样值中有效值个数小于3，则重新采样，若6个数据中存在该区间的个数大于或等于3，则进行下一步；

(3)将A中有效值赋予R，将指纹数据库中的对应AP维度的数据组进行过滤，过滤区间为(R-t,R+t)，过滤次数和采样点有效值个数有关，过滤次数至少3次，最多6次；

图3 自适应阈值的算法流程图

(4)经多次过滤后得出满足条件的一组或若干组数据组；

(5)通过计算这些数据组与采样点之间的最小欧氏距离[9]，即可得出数据库中关系相近的匹配点.

3 实验验证与分析

3.1 实验环境

在面积约为2 000 m2的室内地下车库环境中，完成对AP点部署及数据采样点的规划，另外除了参与测试的随机移动的两实验人员及信号采集设备外，其它物体位置保持不变动，仪器正常运作.

(1)架设无线路由器，无线路由器统一架设在离地高度为2 m的挂袋中，固定放置6个编号为AP1-AP6(路由型号为TP-Link TL-WR802N外置全向天线，全向天线垂直地面放置，并设置无线路由工作于无线AP模式，命名每一个路由SSID名称,设置路由工作于不同信道，发射统一稳定功率的无线信号；

(2)建立室内二维平面坐标系，以室内每个车位为基点，以室内较长的一侧为坐标系X轴,另一边为Y轴，对室内所测范围进行区域划分，在室内车库区域x,y方向上每隔2 m进行网格划分，即每4平方米为一个网格，以每一个网格的中心点作为实验观测采样点;

(3)华硕F456U笔记本(Intel CORE i5处理器)内置无线网卡作为无线信号接收端,为保障实验的统一性,无线信号接收端的架设高度为1m,获取无线信号强度的检测软件Homedale1.5对每一个无线路由所发射的无线信号的RSSI 值进行采集，测试接收端每5 s进行一次信号采集，每个采样点采集时间为100 s,即连续采集RSSI信号20次；

(4)WiFi信号接收装置(笔记本)放置离地高1 m左右，整个采集的过程在白天7:00到晚上11:00进行，持续测试1个月，真实有效的反应正常生活状态下的实际测量情况.

实验中除了随机移动的实验人员及信号采集设备外，其他物体位置保持不动.实验中首先以每隔两米划分，即为4 m2为一个网格点；下一步实验中每隔5 s采集一次RSSI值，每个采样点采集40次；其次采用均值法完成对采样数据的处理；最终将采样点的位置坐标与RSSI均值一一对应，完成指纹库的建立.

3.2 实验过程

实验中指纹数据[10]库包含192个点的RSSI数据组，同时根据实验流程图使用C#编写的地下车库定位软件，实验中采用了6个AP并以此分为6个聚类中心，每个中心的信号强度区间为[-65 dBm，-35 dBm]，以采集的最大RSSI数值为指向.

在室内车库任一点采集一组RSSI值R=(-64，-70，-68，-46，-43，-50)，其中最大值为AP5=-43 dBm，可知该点指向AP5的聚类中心附近；下一步进行多次过滤，第一次过滤目的是形成一个环形初始区域，其过程由采样点中的最大值可知该点在AP5附近，根据-43 dBm所对应的最大波动范围是3 dBm，即在指纹库中AP5所对应的信号区域间[-46 dBm，-40 dBm]以内的区域作为环形初选区域，在该区域以外的将被剔除，保留环形区域内的数据.后面3个信号强度值-46 dBm，-50 dBm，-64 dBm进行3次信号过滤类似于第一步过滤方法，先确定波动幅度，再确定过滤区间，最终过滤得到指纹库中少量数据组(见图4).

图4 四次过滤示意图

根据表1中数据，对采集点A在指纹库中设置有效信号值对应的波动范围、过滤区间，然而此过程只能确定一个环形初选区域并不能确定采样点的准确位置，下一步对该区域内指纹点进行信号波动多次过滤和匹配计算，得到精确位置信息.

3.3 复杂度和运算量分析

本文采用先聚类后过滤的方法，确保在定位过程如果出现某个路由器的损坏，即存在有个别AP无法接收信号，不会导致整个定位系统失效或者瘫痪.

中本文算法相对于最近邻算法进行了算法复杂度分析.设用于计算一次开方运算的复杂度为A，计算加减法的复杂度为M，过滤算法的复杂度为N(过滤在某种程度上复杂度可与加减运算相同)，其中A复杂度远大于M与N.

运算次数分布(见表3)，最近邻法执行了193次开方运算和192次的加减法运算，即可认为复杂度K1=193×A+192M；同理可知K近邻法(K=2)的复杂度K2=193×A+383M.本文的算法进行了337次的过滤运算和3次的加减运算，以及剩余剩下4个点进行的4次开方运算，即复杂度可认为K2=4×A+3×M+383×N，由于过滤算法与加减运算复杂度相同，下表二中对不同算法的运算次数进行统计.