一種基于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.