一种自适应的指纹更新定位方法

叶阿真，张桢萍，孙明辉

(1.福建师范大学计算机与网络空间安全学院，福建 福州 350117；2.福建信息职业技术学院商贸管理学院，福建 福州 350003)

近几年，基于位置服务的需求不断增加，越来越多的人关注到了室内定位[1-2].室内定位服务包括智能营销、精确广告、室内导航、物品监控等.现有全球定位系统的信号无法穿透建筑物[3]，所以在室内环境中无法有效地发挥作用.因此，室内定位成了当前的一个热点研究问题[4-5].出于成本和复杂性的考虑，大多数现有的室内定位都是基于接收信号强度(RSS)[6].信号的多径传播对环境具有很强的依赖性，对于每个具体位置而言，该位置上信号的多径结构是唯一的，发射的信号经过反射和折射，会产生和周围环境相关的信号强度值，这样的信号强度值反映了环境的特征，可以认为是该位置上的信号指纹.基于位置指纹的定位方法[7-10]的核心思想，是通过提读取标签的信号强度值，然后再将信号强度值与事先存储在数据库中的信号指纹进行匹配，找出最相似的结果进行定位.

基于指纹定位系统的工作过程大致可分为两个阶段：离线指纹采集阶段和在线定位阶段.在离线采集阶段，首先在各参考点测量各信标节点的信号特征(如RSSI值)，并将这些RSSI存储为样本，建立一个无线指纹定位地图(指纹数据库)；在在线定位阶段，移动终端实时测量各信标节点的信号特征后，采用相关的匹配算法来确定实时信号特征与哪些参考点的离线信号特征相匹配，再采用定位算法计算出终端的大致位置.然而，由于环境变化，同一地点在不同时间测量出的RSSI值很可能差异很大.这里所谓的环境变化包括人的随机运动、门窗的开关以及温湿度的变化等等.因此，离线阶段建立的信号指纹库可能会过时，从而导致定位精度降低.然而，依靠人工重新标定更新信号指纹库的方式，会消耗大量的时间和人力成本，难以接受.因此需要采用自动更新信号指纹库的方法，本文提出了一种基于模糊聚类的自适应信号指纹库更新方法：

(1)针对环境实时变化导致离线指纹不能充分匹配实时信号特征的问题，提出一种指纹动态更新的定位方案；通过部署校正节点，实现定位指纹的动态更新，从而有效提高基于指纹的定位系统的自适应性和准确性；

(2)提出一种基于模糊聚类的分区机制；以定位指纹数据库中各参考点的传播路径损耗参数为判别依据，引入模糊聚类方法对目标区域进行分区，确保各分区的物理环境具有相近的信号传播特性，为矫正节点的部署以及指纹的动态更新提供依据.

1 相关工作

RADAR是一种典型的指纹定位系统[8].它的工作原理是用多个基站覆盖目标区域，然后记录目标区域的信号强度信息.它结合了经验测量和信号传播模型来确定用户位置.LANDMARC以RFID标签作为定位参考[11]，该方法可实时提供参考位置信息.但需要更多的参考标签来进一步提高定位精度.使用这种方式，一方面会增加定位成本，另一方面也会造成信号之间的相互干扰.Sergios等[12]提出了一种LEASE系统，该系统以静态发射器和嗅探器作为辅助，来训练脱机指纹.文献[13]提出了一种基于位置不确定性约束的室内无线定位方法，利用贪婪算法来求解位置匹配的优化问题.但该算法依赖于当前已有的定位决策，无法保证获得最优解.此外，针对由于无线信号强度不稳定导致定位误差大的问题，研究者也提出了一种基于离散系数改进的WKNN(加权K近邻)算法[14-15].离散系数可以反映单位均值上的离散程度，因此信号源的离散系数可以很好地指示每个基站的信号稳定程度.

2 本文方法

2.1 系统模型

本文方案的系统模型如图1所示.该系统主要由定位服务器、信标节点(BNs)和校正节点(CNs)3部分组成.定位服务器用于存储指纹地图，它可以部署在网络中的任何位置.如果是基于基础设施的定位系统，则定位服务器还将负责计算位置.信标节点负责为所有参考点提供信标信号.因此，需要确保每个参考位置点都有多个信标节点的信号覆盖.对于基于WLAN的定位系统，无线路由器(AP)可以充当信标节点.校正节点负责对信标信号进行实时观测.因此，校正节点应具备接收信标信号的能力，可以测量RSSI值，并与位置服务器建立网络连接.本方案将定位区域划分为多个更新分区，每个分区中的校正节点负责更新本区域内RPs的指纹.因此，每个子区域至少部署一个校正节点.

图1 系统模型

本文提出的信号指纹库动态更新机制如图2所示.首先，采集和建立全局的静态指纹地图；然后引入模糊聚类，根据路径损耗参数将地图划分为若干个子区域，并在每个子区域部署一个校正节点；最后，根据校正节点的测量信号强度，周期性更新射频指纹地图，用于实时定位.

图2 信号指纹库更新模型

2.2 模糊聚类

在硬聚类中，指纹被划分为不同的聚类，每个指纹恰好属于一个聚类.在模糊聚类中，一个指纹可以属于多个聚类，并且指纹与聚类是相互关联的.

对于室内无线信道，由于无线信号会受到室内障碍物的影响，产生反射、衍射和折射，所以接收到的信号由不同振幅、不同相位的入射信号构成.根据对数距离路径损耗模型，信号的能量会随着传播距离的增加而减小.一般来说，满足Shannon对数模型：

PL(d)=PL(d0)+10ηlog10(d/d0)+Xσ，

(1)

其中，d为发射端与接收端之间的距离.d0为参考距离，一般在室内环境为1 m.PL(d)是距离发射终端d米的接收强度.PL(d0)为参考强度.Xσ为标准差.η为路径损耗参数，表示接收强度随距离增大而减小的速率，其值与周围环境和建筑物类型有关.通常，η值主要由发射机和接收机之间的特定信道环境决定.在实际应用中，不同地区室内环境的η值是不同的.

图3为不同区域内RSSI与对数距离的关系.如果在某一区域η值相同或相近，则说明该区域内无线电信号传播特性相似，同样也说明该区域参考点的指纹受到了类似的环境影响.因此，可以根据η的近似程度对离线指纹进行聚类，从而实现对定位区域的分区.

图3 不同区域内RSSI与对数距离的关系

假设有P个信标节点，在室内定位区域有M个参考点.测量第j个信标对应的参考点i的RSSI时，路径损耗参数可表示为：

(2)

因此，位置i处的RSSI指纹可以表示为其路径损耗参数向量.信号指纹库由参考点的坐标及其RSSI指纹组成.

ηi={ηi1,ηi2,…,ηij, …,ηiP}， 1≤i≤M，

(3)

其中，ηij为第j个信标节点对应的第i个参考点的路径损耗参数.因此，所有参考点的路径损耗参数向量可以表示为：

η={η1,η2, …,ηM}.

(4)

聚类函数定义为：

(5)

其中，φ(ηi)为ηi到高维特征空间的映射；φ(pj)表示聚类j的原型向量在特征空间中的映射；U=[uij]为相关隶属度矩阵；uij表示指纹ηi在第j个聚类中的隶属度；C是聚类数；M是平滑参数；dij为φ(ηi)与φ(pj)的相似性.通常，dij定义为与两个向量之间的欧氏距离有关的函数：

20世纪末，中国文学艺术出现了一种反道德的现象，受拜金主义的不良影响，一些文学艺术作品不以宣扬真善美为己任，而是以低级趣味的东西来迎合一些人的口味。这不仅背离了文学艺术的本质所在，而且造成了自身道德信念的失落。新时代，坚定文化自信，推动社会主义文化繁荣兴盛，提升或者重建文学艺术工作者的道德人格首当其冲。文学艺术工作者只有恪守真理与理想，保持强烈的社会责任感和历史使命感，才能不放弃对假丑恶的批判与抗争，通过作品传播先进的思想和正确的人生观、价值观，真正充分发挥文学艺术的道德价值。

dij=‖φ(ηi)-φ(pj)‖.

(6)

聚类的原则是最小化Jm.由于矩阵U中的列元素相互独立，故Jm的最小值为：

(7)

式(7)的约束条件为：

(8)

隶属度表达式可通过拉格朗日乘数法求解：

(9)

根据uij和样本，可以得到聚类中心：

(10)

最后，归属参考指纹最接近pj的位置为聚类j的检查点.

2.3 信号指纹库更新

经过模糊聚类后，可以将信号指纹聚类为C类.同一聚类内的信号具有相近的信号传播参数(η).在每个聚类中部署一个校验节点，观察环境变化引起的信号传播参数的相应变化，从而更新相应的聚类信号指纹库.

2.4 定位计算

通常，使用KNN算法作为指纹方法中的定位算法.该算法以距离度量，如曼哈顿距离或欧氏距离，作为实时指纹与参考指纹匹配值.然后通过比较匹配值来估计目标位置.广义距离公式定义如下：

(11)

其中s为实时指纹，s′为参考指纹.当q= 1和2时，d分别为曼哈顿距离和欧几里得距离.

KNN算法通过匹配值进行升序排列，选择k个最接近的参考点.然后取这些候选位置的质心作为估计位置：

(12)

3 实验

3.1 实验设置

本文实验基于Zigbee平台上实现，硬件平台采用TI公司的CC2431芯片，软件部分基于VC++平台编码，并选用XML文件存储数据信息.实验物理环境为所在实验室的6楼，以1.5 m的间隔设置85个参考点(用绿色标记)，并在房间的角落和走廊共设置5个信标节点，分别记为B1、B2、B3、B4、B5，如图4所示.信标节点的部署如图5所示.在每个参考点分别采集100次不同信标节点的信号指纹，然后取平均值后存入指纹数据库.

图4 实验环境

图5 信标节点的部署

定位误差采用真实位置和估计位置的欧式距离计算：

e=(x-x0)2+(y-y0)2,

(13)

其中(x,y)为目标节点的定位坐标，(x0,y0)为目标节点的真实位置坐标.

3.2 结果以及分析

首先通过移动节点采集所有参考点的信号指纹，并建立指纹地图.然后采用2.2节提出的模糊聚类方法对定位地图进行分区处理，结果如图6所示，实验环境大致可以划分为7个子区域.由此，在每个区域部署一个校验节点，用于实时更新指纹.一方面，该指纹库对环境具有较强的自适应能力；另一方面，自适应更新机制可以节省人力物力，降低系统部署成本.

图6 分簇结果与校验点部署

图7对比了动态更新信号指纹库的方法与静态信号指纹库方法(naive KNN)定位累积误差的概率分布.从图7中可以看出，动态更新信号指纹库的方法表现较好，2 m以内的误差为92%，1 m以内的误差为67%.与naive KNN相比，整体定位性能更好.这是因为该方法不是基于静态信号指纹库，而是基于动态更新的信号指纹库.因此，该方法能够有效地适应环境和干扰的变化，从而提高定位精度.

图7 累积误差概率分布

4 结论

对于室内指纹定位，本文提出了一种新的自适应信号指纹库更新方法.不同于典型的指纹定位方法，该方法将静态信号指纹库转换为动态更新的自适应指纹库.利用模糊聚类将指纹分为几个聚类，然后为每个聚类选择代表.在定位阶段，信号指纹库会通过观察检查站信号特征的变化来进行自我更新.该方法既能适应环境变化，又能降低信号指纹库更新的人工成本.实验表明，该方法在定位精度方面有较好的表现.