一种基于MDS算法的室内W i-Fi指纹地图构建方法

卢峰，袁平，殷锋

（四川大学计算机学院，成都610065）

0 引言

Wi-Fi接入点目前已经普及到千家万户，我们的生活环境中无处不见Wi-Fi信号。因此，基于Wi-Fi的室内定位提供了新方法。现有定位方法主要有两大类：一类是利用AP（Access Point）和定位点之间的几何关系进行定位，如：AOA（Angle Of Arrival），TOA（Time Of Arrival），TDOA（Time Difference Of Arrival）等[4-6]。这类方法需要精确的几何量和时间量的测量，对硬件要求极高，成本高。因此不适用于广泛的定位方法，无法普及。另一类是基于利用一组AP到测量位置之间的接收信号强度（Received Signal Strength，RSS）来衡量测量位置到每个AP点的距离远近，将这些收集到的信息称为指纹（Fingerprint），并进行存储。在实际使用中通过采集用户的实时RSS信息，与数据库中的指纹信息进行匹配，从而算出用户的实际坐标位置。这种方法无需特殊的硬件设施，只需要接收Wi-Fi的信号强度并且存储在存储服务器，节省成本，因此应用广泛。本文提出了一种新颖的Wi-Fi指纹库构建方法。相比较于传统的指纹库构建方法，该方法将采集到的指纹信息通过MDS算法映射到一个二维指纹空间，表现出指纹之间的距离关系。而传统的指纹库构建方法构建出的指纹空间，指纹之间的关系比较孤立，可能存在较大的错误和误差。

指纹地图构建基本框架如图1。

图1 指纹地图构建基本框架

（1）根据建筑物平面图，将其用网格划分，每个交点p(x,y)表示其实际的坐标位置，交点形成原始的位置集合P0={(x,y)|x为横坐标，y为纵坐标}；

（2）计算集合P0中两两点之间的距离，形成距离矩阵M0。注意，此处的距离并非指的是两点之间的直线距离。而是两点之间的行走距离。对于两点之间有障碍物阻挡的情况，则其行走距离必然大于其直线距离；

（3）依据MDS算法计算出标准化位置空间SPS；

（4）用户利用手机等移动端设备采集Wi-Fi指纹构成原始的Wi-Fi指纹集合：F0={(s1,s2,...,sn)|n}为AP点个数，si为测量点处第i个Wi-Fi信号强度，以及连续两个采样点之间所行走的步数m；

（5）通过Floyd-Warshall算法计算两个指纹之间的最短距离。获得指纹之间的距离矩阵M1；

（6）依据MDS算法计算出标准化指纹空间SFS；

（7）通过采集到的特殊的指纹（走廊、门口等）利用最小二乘法拟合出SFS到SPS之间的映射关系：L：SFS→SPS。

1 构建标准化位置空间

如图2为某楼层的平面图，依照1m间距的网格将其划分，每个交点p（x,y）表示其实际的坐标位置。对于其中的两个点pi,pj，由于两个点有墙壁阻挡，所以这两个点之间的距离为：

由此，我们通过计算出集合P0中两两点之间的距离得到距离矩阵M0，然后通过MDS算法将M0映射到一个二维空间中，形成SPS，如图3所示，为某楼层的SPS。

其中可以看出，对于同一个房间中的点，由于它们的实际行走距离比较近，因此形成一簇；二对于不同房间中的点，由于它们之间的行走距离相对较远，则分布在图中的不同簇中。

2 构建标准化指纹空间

类似于构建SPS的方法，我们首先要获取到指纹集合F0的距离矩阵，才能计算出其标准化指纹空间（SFS）。本节内容分为两部分：（1）采集指纹；（2）计算集合F0的距离矩阵；（3）计算SFS。

2.1 采集指纹

我们设计了一款手机端的APP用来采集楼层中的Wi-Fi信号强度和用户行走的步数间隔，上传到服务器。对于两个连续采样的Wi-Fi指纹fi,fj,他们之间的行走步数为di,j。当收集到足够的采样点后，采样集合F0中共有m个Wi-Fi指纹。同时获得k条采样路线，每条路线包含若干个采样点。

此时，我们只知道同一条路线上的采样点之间的距离。而对于不同路径上的采样点的距离我们是不知道的。因此，想要得到距离矩阵，还需要计算不同采样路径上的点之间的距离。

2.2 计算F0的距离矩阵和SFS

对于某同一条路径上的点之间的步行距离是很容易计算得到。而（1）对于不同路径上的点之间的距离还未知；（2）对于相同路径上的点也有可能不是其最短路径，可能有更近的路径没有被发现，如图4。因此，我们还要计算出所有指纹之间的步行距离。

我们使用走廊、门口等这些特殊点位作为路径的连接点，并且利用指纹之间的余弦相似度合并其中的相似的指纹。对于指纹fj=[x1,x2,...,xn],fk=[y1,y2,...,yn],二者之间的余弦相似度为：

图4 指纹采集路线图

图5 合并后的路线图

当其小于某设定阈值δ,则合并这两个指纹。合并后的指纹示意图如图5，其中红色点表示合并后的指纹点，可见对于走廊上的大多数的点都将被合并，路径的交点也会被合并。进而利用Floyd-Warshall算法计算出两两指纹之间的最短路径。得到距离矩阵M1。

同样的，以距离矩阵M1作为输入，利用MDS算法计算出SFS。

3 构建空间映射关系

根据获取到的SPS和SFS（SPS为楼层地图的具体位置的空间映射，SFS为采集的指纹信息的空间映射）。如果二者能够从SFS映射到SPS，则就可以实现指纹定位功能。

对于SPS中的子集SPSA是楼层地图中走廊、门口等特殊位置的空间映射点；对于SFS中的子集SFSA是采集的指纹集合中的走廊、门口等特殊位置的空间映射点。现在我们以这些特殊点，利用最小二乘法拟合出SFSA到SPSA之间的映射关系L：SFS→SPS。

指纹fi∈SFSA的坐标为SA的维度。在SPSA中对应的点为可得到如下等式：

经过变换为：

其中。根据最小二乘法，得到最小化的解析解为：

则根据可得到变换矩阵A和B，从而可以将SFS中的任意指纹映射到SPS中某个位置上。

4 结语

本文提出了一种新的Wi-Fi指纹地图构建方法，该方法基于多维标度算法（MDS）将楼层平面图转化为标准化位置空间（SPS）。收集用户采集到的Wi-Fi指纹信息算出指纹的距离矩阵，同样通过MDS算法得到标准化指纹空间（SFS）。进而利用采集到的特殊走廊、门口等特殊位置的指纹拟合出SFS到SPS的映射关系。从而达到定位的目的。该方法只需少量的人力来初始化指纹空间，在实际使用中通过不断收集用户上传的指纹信息，重新构建SFS和映射关系，达到提高定位精度的目的，具有很高的应用价值。

参考文献：

[1]肖超.基于无线信号的室内定位方法综述[J].黑龙江科技信息,2017（12）:62.

[2]Borg I,Groenen P.Modern Multidimensional Scaling:Theory and Applications.Springer Verlag,2005.

[3]贾小勇,徐传胜,白欣.最小二乘法的创立及其思想方法[J].西北大学学报（自然科学版）,2006（03）:507-511.

[4]席瑞,李玉军,侯孟书.室内定位方法综述[J].计算机科学,2016,43（04）:1-6+32.

[5]阮陵,张翎,许越,郑星雨.室内定位:分类、方法与应用综述[J].地理信息世界,2015,22（02）:8-14+30.

[6]赵锐,钟榜,朱祖礼,马乐,姚金飞.室内定位技术及应用综述[J].电子科技,2014,27（03）:154-157.