基于无监督学习的定位数据质量评估及异常检测*

邱颖，代玉琢，王琛，朱亚萍

（同济大学软件学院，上海 201804）

0 引言

随着人类步入信息化时代，电磁波已经充斥人类生存的空间，这些电磁波可以被充分利用进行通信、测距以及导航等服务[1]。利用WSN（Wireless Sensor Network，无线传感器网络）对物体进行定位是其中一个重要的应用[2]。WSN是指大量具有信息感知功能的传感器节点通过无线通信的方式构成一个多跳自组织网络系统[3]。WSN定位就是利用传感器节点之间发送与接收的无线信号确定物体的位置。基于WSN的定位为近年来IoT（Internet of Things，物联网）技术的兴起提供了重要支撑[4-6]。

目前主流的WSN定位可以分为基于测距的和基于非测距的定位[7-8]。基于测距的定位沿袭GPS的基本工作原理，即在需要定位的场景空间预先部署位置已知的锚节点（Anchor）充当“室内小卫星”，通过获取待定位的盲节点（Agent）与多个锚节点之间的距离信息，采用多边测量等几何方法解算得到盲节点的位置坐标，再将其映射到对应的地图中[9]。以二维空间定位为例，盲节点只要同时获取其与至少3个锚节点之间的距离信息，就可根据三角原理唯一确定自身的位置坐标。这种定位方法在所有测距达到一定准确率的情况下，能够取得比较好的定位效果，而且算法相对简单，实施比较容易。然而，在实际应用中，由于定位场所一般较大，锚节点部署数目有限，不可能保证所有区域都能同时被3个及以上的锚节点信号所覆盖，因此，往往会采用协作定位的方式进行定位。协作定位是指不仅利用锚节点与盲节点之间的测量信息，盲节点与盲节点之间的测量也会被利用进行位置估计[10-12]。

相比于只利用锚节点与盲节点之间测量的非协作定位而言，协作定位可以极大程度地提高定位系统的性能，特别是对于稀疏部署的网络[13]。尽管协作定位能够取得更好的整体性能，但是在这种协作的模式下，如果节点提交的数据缺乏质量保证，会对整个定位系统产生重大影响。因此，评估协作定位中每个节点的数据质量是极其重要的。Wen等[14]提出了使用感知数据的质量而不是工作时间来衡量节点贡献，此外，文献[14]中还提出了一个概率模型来评估提交数据的可靠性，并将所提的机制整合到基于Wi-Fi指纹的室内定位系统中，验证了其所提算法的有效性。Xu等[15]提出了一种未来预测函数，利用工人以前的表现情况评估其声誉，并引入了数据准确性和响应时间来评价工作人员的工作绩效，在此基础上设置最终的报酬。Li等[16]提出了一种感知质量度量方法来描述用户隐私保护和提交数据的空间覆盖范围的联合影响，在预算有限的情况下，设计了一种基于拍卖的激励机制来获取用户的真实成本，以最大限度地提高感知质量。

然而，用户在协作定位中所提供的数据的质量不仅仅表示数据本身的准确性，还应当反映出该数据对其他用户定位精度的贡献程度。目前已有的WSN定位中的数据质量评估方式大多采用“数据是否准确”这种单一的衡量标准，并不能恰当描述用户数据在协作定位中对结果的影响情况。而且，在这些机制中大多采用基于反向拍卖的模型，这种模型由于过度依赖用户的诚实性，导致用户间存在恶意欺诈以及“搭便车”等现象[17]。因此，本文针对WSN中的协作定位提出合理的节点数据质量评估方法，准确度量节点在定位过程中的贡献程度；同时，在此基础上制定有效的异常处理措施，对不合格的节点数据进行及时处理，避免对定位系统的不利影响。

1 系统模型

假设W S N 定位网络中部署有M个锚节点和N个盲节点，锚节点的位置已知，盲节点的位置需要估计得到。锚节点和盲节点的集合分别记为M和N，并且M={1,2,…,M}，N={M+1,M+2,…,M+N}。节点i的位置用Pi表示，它从其他所有用户处获得的定位测量数据记为Ɵi。节点之间的数据测量通过波形传播来获取，本文以从波形中提取的TOA（Time of Arrival，到达时间）作为位置估计的信号关联。图1给出了基于TOA的二维测距定位基本原理示意图。对于盲节点i，它从节点j处接收到的波形可以表示成[18]：

图1 基于TOA的二维测距定位示意图

其中，xi j表示传输功率，di j是节点i和节点j之间的距离，β表示与传播环境相关的路径损失，s(t)是产生的波形，τij表示传输延迟，αij表示幅度增益，zij(t)表示加性高斯白噪声。

2 算法描述

本节具体描述所提算法，包括基于不确定的数据质量评估算法和基于无监督学习的异常检测算法。

2.1 基于不确定度的数据质量评估

在协作定位中，任一节点的数据质量对整个网络“牵一发而动全身”的作用关系，决定了准确评估数据质量的重要性。节点数据质量的好坏不仅表示数据本身是否准确，更重要的表现为节点所提供的数据对定位结果是否有利。“好”的数据可以提供更有价值的参考信息、提高定位精度；反之，“坏”的数据可能会干扰系统对位置结果的准确估计。但是，在定位过程中，盲节点位置坐标的Ground Truth是无从得知的，实际上这正是需要估计的值。因此，无法直接利用节点的实际位置来衡量节点数据对定位结果的参考价值。然而，考虑到基于测距的WSN定位算法有这样一个特点，以二维定位举例，盲节点只要能同时获取三组及以上的距离参考信息，就可以对自身的位置进行粗略估计。也就是说，在已经满足可以同时获取三组参考信息的前提下，额外获取某一节点的测量数据对是否能够实现定位没有影响，而只会影响定位结果的精度情况。因此，本文提出通过比较参考节点集合中包含和未包含某一节点这两种情况下定位结果的差异，来衡量该节点提供的数据对定位结果的影响，并在此基础上评估节点的数据质量。

在协作定位的迭代估算过程中，每个节点的位置坐标估计值不是一个绝对精确值，而是服从于某种分布。假设用表示节点i在第t轮迭代中的坐标估计分布，如果越集中（Concentrated），表示节点的位置估计越确切。在实际过程中，很难通过将表示成某一闭合表达式的方法来直接获取用户坐标Pi的具体分布。事实上，也不需要完全知道的精确细节，而只需估计出Pi的平均值以及该估计值的不确定度。基于这种目的，可以利用属于某一类型T的分布fi(Pi)来近似替代，比如，将近似表示成高斯分布[19]。同时，可以采用KLD（Kullback-Leibler Divergence,KL散度）衡量这两种分布之间的近似度[20]，具体表达式为

可以证明，当且仅当fi(Pi)=bi(Pi)时，D(fi(Pi)||bi(Pi))取得最小值。因此，对于给定的分布类型T，可以取使KLD获得最小值时的分布fi*(Pi)作为bi(t)(Pi)的近似分布，即

本文采用高斯分布来近似表示在基于测距的协作定位中的位置坐标估计。不过需要考虑的是，当盲节点同时与两个锚节点通信时，会出现两个高度集中的可能性估计值。这种情况下，仅采用单个高斯分布是无法表示的。因此，本文采用两个高斯分布的混合。尽管的分布有很多种，不过采用两种高斯分布的混合已经足以描述出它的分布情况。因此，可以近似写成

其中：μ1i和μ2i是两个平均值向量，Σ1i和Σ2i表示两个高斯分量的协方差矩阵。在二维定位中，μ是一个对应x和y坐标的2×1向量，Σ是一个2×2的向量。参数ξ1和ξ2分别表示两个高斯分布的权重因子，且满足ξ1,ξ2∈[0,1]以及ξ1+ξ2=1。比较两个协方差矩阵的迹，并用其中较大的值表示节点i位置估计值的不确定度δi，即

得到节点坐标估计值的不确定度后，就可以通过观察其他节点提供的数据对该不确定度的影响来评估其数据质量。

假设协作定位网络中，节点k的参考节点集合记为Nk，且Nk包含节点i。在Nk中所有节点提供的参考数据下，节点k的坐标估计不确定度为δk。如果去除节点i，节点k的坐标估计不确定度变为δk’，则节点i的数据对k的定位结果提供的参考价值为δk’-δk，节点i在整个协作定位网络中的数据质量Ωi表示成

2.2 基于无监督学习的异常检测

在整个协作定位过程中，节点的数据质量不可能一直处于稳定状态。由于一些突发状况，节点可能会在一段时间内无法提供高质量的数据；又或者，一些恶意节点故意提供质量很差的数据干扰定位系统的性能。因此，本文在动态观测节点数据质量的基础上，提出一种基于无监督学习的异常检测算法，及时剔除一些不合格的节点数据，保证定位系统整体性能的稳定性。

如果只根据节点在一次迭代中的数据质量情况来判断其是否异常显然是不合理的，因此，记录节点提供的历史定位数据，并在此基础上利用无监督学习建立节点的声誉（Reputation）评价体系，以此作为判定节点是否存在异常的标准。一般情况下，一个人在社会上的声誉往往是在一系列可靠的行为下逐渐建立起来的，而在几次不诚实的行为后可能很快就会“毁于一旦”。因此，声誉函数的设计需要满足这样几个特点：①在节点贡献出较高质量的数据时，节点的声誉会得到些微提高；②当节点提供的数据质量很差时，声誉值会大幅度下降。基于以上分析，本文采用逻辑函数来对节点的声誉进行建模，因为逻辑函数的数值增长速度在左右两侧最快、在中间部分最慢。具体地，使用Richard生长曲线，表达式为：

其中：A是累计生长的饱和值，B是生长初始值参数，a是生长速率参数，b是异速增长函数。

为了描述节点数据在长期阶段的表现情况，对节点的历史数据进行汇总。同时，为了区分不同时段历史数据的重要性，采用指数因子对每轮迭代中的数据进行加权。因此，节点i在第t轮迭代时，声誉估算函数的输入参数设计为：

其中：ω表示不同阶段节点的历史数据占比，ω是取值空间为N的不同大小的数值，且0＜ω＜1。

下面，将利用DQN（Deep Q-network，深度Q-网络）得到节点在每轮迭代中当前数据的权重大小。DQN的内核是Q-Learning机器学习算法，假设所采用的Q函数记为

该函数用来计算给定输入φ(st)时，采取行为at所能得到的预期累积奖励，其中：ϑ是将输入映射到输出决策的行为价值函数，φ(st)表示状态重建。在每轮学习中，使用∈-greedy策略选取可能的行为，即选择权重ω的值。在每轮输入-输出映射中，Q-网络生成一个由当前状态φ(sk)、当前行动ak、即时奖励rk+1以及下一时刻状态φ(sk+1)组成的元组。将这些结果存储在复盘存储器D中。每次学习时，从D中随机采样一个小批量（Minibatch），结合目标网络，计算损耗并训练Q-网络。具体地，损失函数可以设计为

其中：E[*]表示期望值；yk是目标函数值，表达式为

其中：rk+1表示奖励（Reward），γ是一个正常量。学习出不同时段节点数据的权重ωi t后，节点i在第t轮迭代时的声誉值就可以通过将公式(8)代入到公式(7)中计算R(qi,t(ωi t))的值来得到。最后，将节点当前时刻的声誉值与固定阈值RThre进行比较，如果低于该阈值，则判定节点当前的数据异常，在协作定位的计算中将不采用该节点的数据。本文所提出的算法框架如图2所示。

图2 本文提出的定位节点数据质量的动态评估和异常处理算法框架示意图

3 实验结果与讨论

本节通过仿真实验来验证所提算法的有效性。考虑一个100 m*100 m的正方形定位区域，在区域中随机部署10个锚节点和100个盲节点，图3给出了节点部署的示意图。本实验的训练数据集通过模拟产生，用于训练的输入数据为每个节点与其他所有节点在每一次定位中的距离测量的方差，输出的数据是根据网络中所有盲节点的平均定位误差设定的权重值，具体包括9个数值，分别为0.01，0.1，0.5，1，2，5，10，20，50。在实际使用时，节点之间的测量往往会采用多次重复的方式，因此可以提取出每轮距离测量值的方差作为输入。本实验模拟产生100 000组训练数据，涉及的具体参数如表1所示。

表1 仿真参数

图3 节点分布图（蓝色圆圈表示盲节点，红色星号表示锚节点）

首先，图4描述了不同数据质量下位置估计值的PDF（Probability Distribution Function，概率分布函数）。在该实验中，分别采用了距离测量值方差在1 m2、5 m2和10 m2的情况下对盲节点位置估计的影响，所需估计的盲节点的实际位置坐标为[146 m,76 m]。从图中可以看出，质量越高的测量数据（方差为1 m2）产生的位置估计值越集中，从图4（a）中可以很精确地推算出所要估计的位置值。然而，随着数据质量的恶化（方差逐渐增大），位置估计的可能性值变得不再集中(如图4（c）所示)，因而在实际算法的推算中落在其他错误位置上的可能性变大，使得估计结果变得不准确。

图5分析了在所提的非监督学习算法下对提供不同质量的数据的节点进行声誉值估计的情况。从图5（a）可以看出，所提算法能够对不同质量的数据提供者进行比较好的权重分类。根据学习出的权重情况，进一步利用声誉估计函数计算每个节点的声誉值，如图5（b）所示。低于声誉阈值（RThre）的节点提供的数据在本轮的位置估计中将不被采纳。

最后，分析剔除挑选出的低声誉节点数据（异常数据）后对定位结果的影响。图6定量描述了异常数据对定位结果的影响。图6（a）分析了单个节点的异常数据在是否被剔除时的情况，其中的两条曲线分别给出了在不同噪声水平下，使用和未使用异常数据时对定位结果的影响。在仿真模拟中，对其中某个节点的定位测量数据添加不同程度的噪声（从10-2m～104m），观察在两种情况下位置估计的RMSE（Root Mean Squared Error，均方根误差）值的变化情况。从图中可以看出，当异常数据的值被剔除掉时，网络中的节点位置估计能维持较好的水平。事实上，如果网络中的节点数量足够多时，有效剔除个别（数量较少）异常数据对定位结果几乎不产生影响。因为根据已有的工作可以证明，在三边定位中，当参考节点的数量超过一定数值时，再额外增加其他节点的测量信息对定位精度的增加会变得不明显。因此，在节点数量充足时，剔除掉异常的测量数据并不会因为参考数据的减少而使精度降低，反而会因为剔除了不准确的参考信息使得位置估计结果避免受到负面影响。特别需要指出的是，异常节点对协作定位的影响更为严重。在图6（a）中，随着噪声水平的增加，异常数据对定位结果的影响导致在协作模式下的定位效果甚至不如协作定位。图6（b）给出了使用所提的异常检测算法后网络中所有盲节点的定位误差的CDF（Cumulative Distribution Function，累计分布函数）。从图中可以看出，如果未能及时剔除异常数据，节点的位置估计会受到严重影响。随着噪声水平的增加，节点位置估计的精确度会急剧恶化。这种现象进一步验证了在协作定位中及时剔除异常数据的重要性。

图6 异常数据对定位结果的影响

4 结束语

本文研究WSN协作定位网络中的数据质量评估以及异常检测问题。提出了一种基于不确定度的数据质量评估算法，利用基于测距的协作定位算法中三角原理的应用特性，在Ground Truth未知的情况下设置有效的节点定位数据质量评价基准；同时，提出了一种基于无监督学习的异常检测算法，结合历史数据，考察节点的长期表现情况，提高异常判断标准的合理性。仿真证明，所提算法能够对不同质量的数据进行有效的评估及区分，在此基础上提出的异常检测及剔除算法可以有效避免异常数据对定位结果的负面影响，极大程度地提升网络的定位精度。