基于标签信息的全局流形对齐定位算法

夏颖，秦娟，王艳春，高鑫

（齐齐哈尔大学 通信与电子工程学院，黑龙江 齐齐哈尔 161006）

随着智能手机的普遍使用及无线通信技术的发展、基于位置服务的业务需求快速增长，室内、外定位导航系统及其应用得到了众多科研工作者的广泛关注[1-4]。截止目前，已有众多的方法应用于室内、外定位服务中，比如，基于红外线、超声波、射频和WLAN 等信号识别的室内定位系统，以及利用卫星信号进行定位导航的北斗卫星定位系统、GPS 卫星定位系统等。基于WLAN 的室内定位系统是利用广泛覆盖的无线局域网基础设施来进行室内移动目标位置估计的，系统的传输带宽低、定位精度较高、无需额外增加其他硬件设备等优势而得到广泛的应用。基于WLAN 的定位技术，包括离线阶段的位置指纹数据库构建，及在线阶段的RSS 信号采集与位置信息映射。离线指纹数据构建阶段，通过在目标区域内选择若干参考点，通过每个参考点采集到的无线接入点信号强度与其位置坐标对应关系，构建离线指纹数据库，即Radio Map。在线阶段，移动终端实时接收来自各个无线接入点的不同强度RSS 信号，通过合适的映射匹配算法，将采集到的信号解算为指纹库中的匹配信号，实现用户位置的估算。

鉴于室内无线信号传播复杂多变的特点，不同时刻，确定参考点上接收到的来自同一接入点的RSS 信号具有较复杂的时变特性。为了提高离线阶段指纹库的数据精度，离线阶段需要对同一参考点采集多个指纹数据，进行不同时段、不同设备的数据融合。位置指纹数据精确程度直接影响着在线阶段的位置估计，因此，如何实现离线阶段构建的指纹库在动态环境下，能够具有稳定的在线定位精度，是将WLAN 广泛应用于室内位置估计的关键。

在众多关于提高静态指纹数据库在动态环境下的定位精度研究中，基于移动终端的志愿感知的构建方法[5-6]需要对非友善用户提交的数据进行数据剔除，给定位解算增加了额外的开销。基于半监督学习的指纹数据构建[7-10]在部分标记数据基础上，通过半监督学习实现未标记数据的标定，很好地利用了多个移动终端充当志愿者随机采集实时RSS 数据，既可以有效减少离线阶段指纹库构建的时间与人力消耗，还可以有效克服无线信号传播时变带来的定位精度下降。基于多维模糊映射AP 优化的室内定位方法[11-13]，通过多维模糊映射构造模糊判定矩阵并计算AP 在线模糊隶属度，同时结合KNN 算法完成对目标的位置坐标估算。上述方法中在使用RSS 信号完成位置估计的同时，对于其多维数据具有的流形结构特征，通过提取非线性特征用于辅助定位，进而实现更精确的定位结果。上述传统的基于半监督学习的位置指纹定位方法中，仅保持RSS 数据的局部流形结构，在局部结构相似的数据间，会产生映射错误，直接影响指纹数据及定位结果的准确性。

本文提出基于标签信息的全局流形对齐定位算法，实现多域间高维数据的低维嵌入，在提取低维特征的同时，保持目标域几何结构和流形间的相似性不变。该算法利用离线阶段采集的少量有标签的指纹数据，结合众多移动终端定位区域采集的实时无标签RSS 数据，通过样本标签信息和局部几何结构重构每个样本点的特征，实现未标记数据的位置标定，减少离线阶段对确定参考点的数据采集；在线定位阶段，将移动终端采集的高维RSS 数据进行位置解算时，保持流形的全局结构。流形对齐目标函数在求解过程中，可以充分挖掘参考点标签数据与位置坐标的对应关系，将指纹数据及位置信息同时投影到共同的标签空间，在计算低维嵌入位置信息的同时获得样本标签信息，可以提高位置信息标定的准确性，提升定位性能。

1 基本理论

基于位置指纹的WLAN 室内定位过程，在线阶段的位置估算，可以归为分类问题。即通过一定的映射匹配算法，将采集的定位信息划分到所属的区域，进而获得目标的位置信息。流形学习作为一种典型的数据特征提取方式，可以获得很好的分类结果，流形对齐则是流形学习算法在多个流形上应用的拓展。

1.1 流形对齐算法

流形对齐是通过挖掘不同流形原始空间的几何结构，将不同的流形投影到同一低维空间，并保持在投影空间的局部或全局几何结构一致。已知高维流形空间的样本点x1,x2,…,xn，维数为D，其中xi∊RD，流形对齐的目的就是求得每个样本点在低维特征空间R d(d≪D)中的低维嵌入y1,y2,…,yn，其中yj∊Rd。算法的一般步骤为：

（1）构建全部样本点的邻域点距离矩阵：计算每个样本点与其他样本点的欧氏距离，按距离由近及远升序排列。采用经典k-近邻方法，为每个样本点选取k个样本点组成的集合作为其邻域。（2）高维流形空间的几何结构构建：其构建的准确性直接影响降维结果，经典的等距特征映射算法（ISOMAP）、局部线性嵌入算法（LLE）、拉普拉斯特征映射算法（LE），分别从流形全局与局部结构角度优化非线性降维。（3）低维嵌入：以最大化保持流形内在几何结构的权值矩阵、相似性矩阵为目标，构造目标函数，求解特征值、特征向量，将高维空间中的样本点映射到共同的低维空间。

1.2 基于特征层的流形对齐

假设待对齐的l个流形X1,X2,…,Xl，其中任意Xk=∊R1×D，定义目标函数：

2 基于标签信息的流形全局结构对齐定位算法

上述流形对齐算法，仅对具有线性关系的流形可以有效保持对齐后的几何结构。基于位置指纹的室内定位算法，在实现不同指纹数据更新时，需要实现多流形对齐，其关键在于将每一个数据集合找到对应的映射。在对移动目标采集的指纹信息进行位置匹配映射时，可以借助离线阶段构建的指纹数据库中标签数据，通过标签信息建立待对齐未知域和目标域之间的联系，利用未知域中测试样本和目标域中参考样本，预测未知域中测试样本数据的目标域映射。

2.1 算法模型

设高维流形样本集X=[x1,x2,… ,xm]∊RD×m和Y∊Rd×n，两样本集可以视为各自流形中的采样点。假设X中的样本点信息全部已知，包括布设参考点的位置坐标及接收的来自各个无线AP 的RRS 信息，坐标信息简记为。Y中只有部分样本点的位置信息是已知的，将已知位置坐标信息的样本点集作为目标域训练样本集，其位置坐标信息记为，其余的样本即为没有位置信息的待定位目标。

基于标签信息的流形全局结构对齐定位算法（Label Information Manifold Structure Alignment of Location Algorithm, LIMSALA），通过离线阶段采集的参考点信息，作为标签建立未知域和目标域之间的联系，利用未知域中测试样本和目标域中参考样本估计未知域中的待测样本的位置信息。LIMSALA 对齐算法首先计算每个测试点到各个参考点的欧式距离，利用多维矩阵表示各个测试点，然后通过距离位置相似性计算样本点间的相似性。保持其目标域局部几何结构和流形间的相似性不变，获取未知域测试样本的标签信息。算法流程如图1 所示。离线阶段，通过在定位区域合理布设若干参考点，采集来自各个无线接入点的RSS 信号，构建位置指纹数据库及其对应位置间的对齐映射特征向量，获取信号的低维本征空间与物理空间位置的对应关系，得出相应的流形对齐向量，构成在线定位映射数据库，用于在线阶段的映射定位过程。

图1 基于标签信息的流形全局结构对齐定位算法流程

2.2 LIMSALA算法步骤

步骤1. 离线阶段参考点布设及指纹库构建。

①在目标区域合理划分不同区域及布设参考点，对每个参考点x i,X∊RD×m构建体现RSS 信息矩阵R与位置坐标信息矩阵P，构成位置指纹数据库Radio Map；

②建立数据集样本点特征层相似度矩阵W，通过最小化L(h)的特征值分解来求解。

步骤2. 建立源域X同目标域测试样本ty之间的联系。

①在源域中计算参考点到每个样本点欧式距离，在目标域中计算测试点yt到每个特征层的欧式距离；

②根据映射目标函数，构造x i,yt的特征表示v xi,vyt；

步骤3. 计算待定位点的低维嵌入。

①依据在线接收到的RSS 信息，利用已采集样本点X的部分标签信息，构造样本点低维坐标U；

②根据目标函数L(f,g)的求解结果，计算Y的低维嵌入，获取目标域中每个待测样本点的位置信息，实现室内定位。

3 实验结果与分析

为评估基于标签信息的流形全局结构对齐定位算法的性能，本文采集图2 所示典型的WLAN 多墙环境下的RSS 数据，进行定位效果的测试与分析，并与3 种MDFM-AP、LLEMA 及k-means定位算法进行了性能比较。

3.1 实验环境和数据采集

图2 所示为典型的室内办公场景，位于某大学实验办公楼的中间层，楼层主体结构包括走廊和若干房间，定位实验选择在走廊完成。整个实验区域使用面积为49 m ×14 m，走廊宽度3m，长度约为128m，均匀划分为247 m 个网格，中心作为参考点的物理位置。

图2 实验环境楼层平面图

整个楼层布设多个同型号Linkksys WRT54G 无线接入点，用以整个区域的无线信号全覆盖，在室内多墙环境中，无线射频信号经过室内墙体、桌椅等障碍物的时候，信号强度都会受到衰减，终端设备接收的实时RSS 具有复杂的时变统计特性。因而，利用终端驱动和RSS 信号采集软件，在每个参考点从4 个方向、每个方向100 次，以2样本/s采样频率分别采集400 个RSS 向量样本，经时间分集后作为训练样本的离线阶段指纹数据库。实验一共选取测试点514 个，其中124 个参考点的指纹数据，作为标签数据用于流形对齐映射输入值，同时采集随机路径上390 个待定位目标点的RSS 作为未标记数据。

3.2 定位结果比较分析

图3 所示为参考点依据物理位置均匀分布时，选取部分参考点的信息作为标签数据，采用基于标签信息的全局流形对齐定位算法LIMSALA，与基于多维模糊映射AP 优化的MDFM-AP 定位算法、局部线性嵌入的流形对齐算法LLEMA、及传统k-means算法的定位结果比较分析。当定位误差小于或等于3 m 时，本文算法的误差累积概率分布为84.1%，另外3 种算法的误差累积概率分布分别为69.7%,62.1%, 52.3%。由此可见，本文算法具有较好的定位性能，仅需较少的标签信息，即可实现与传统的k-means 算法相似的定位精度。该算法利用标签信息建立流形间的联系，可以实现在复杂定位环境下通过全局特征的保持，将参考点样本和待测位置点样本投影到共同的标签空间，因而可以获得较好的定位结果。

图3 不同算法的定位性能比较

表1 给出了在线测试样本数相同的条件下，不同算法的定位性能比较：从定位计算复杂度来看，LIMSALA 算法稳定，所需定位时间较少，仅需0.174 s，相比其它两种算法分别减少了11.3%,87.3%，而且该算法具有最小的平均定位误差。由此可得，在复杂的室内环境下，基于标签信息的全局流形对齐定位算法可以准确地得出信号的低维本征空间与物理空间位置的对齐向量，使在线定位更准确，从而能更精确地估计位置。

表1 不同算法定位时间与定位性能的比较

4 结束语

本文提出了基于标签信息的全局流形对齐定位算法，仅需利用少量的标签信息构建室内指纹定位系统Radio Map，通过欧氏距离获得位置坐标与高维射频信号RSS 的重构向量表示，映射两者间全局结构对齐向量。该对齐映射能够确保流形对齐过程的正确性，反映高维指纹数据与其位置空间二维坐标的映射关系，准确完成了对定位区域目标点RSS 信号的位置估计。通过学习算法提取该数据所隐含的位置信息，用于对离线采集的已标记数据进行更新，可以避免因指纹库重建而带来的人力和物力的消耗，便于室内定位系统的大规模推广和应用。实验结果表明，该算法可有效减少流形对齐过程中的错误映射，提取的全局特征结构完整，同时无需更多的标记数据即可实现待测目标的位置估计，在提高系统定位性能的前提下，能够有效地减少校准工作。