一種基于MDS算法的室內(nèi)W i-Fi指紋地圖構(gòu)建方法

盧峰，袁平，殷鋒

（四川大學(xué)計(jì)算機(jī)學(xué)院，成都610065）

0 引言

Wi-Fi接入點(diǎn)目前已經(jīng)普及到千家萬(wàn)戶(hù)，我們的生活環(huán)境中無(wú)處不見(jiàn)Wi-Fi信號(hào)。因此，基于Wi-Fi的室內(nèi)定位提供了新方法?，F(xiàn)有定位方法主要有兩大類(lèi)：一類(lèi)是利用AP（Access Point）和定位點(diǎn)之間的幾何關(guān)系進(jìn)行定位，如：AOA（Angle Of Arrival），TOA（Time Of Arrival），TDOA（Time Difference Of Arrival）等[4-6]。這類(lèi)方法需要精確的幾何量和時(shí)間量的測(cè)量，對(duì)硬件要求極高，成本高。因此不適用于廣泛的定位方法，無(wú)法普及。另一類(lèi)是基于利用一組AP到測(cè)量位置之間的接收信號(hào)強(qiáng)度（Received Signal Strength，RSS）來(lái)衡量測(cè)量位置到每個(gè)AP點(diǎn)的距離遠(yuǎn)近，將這些收集到的信息稱(chēng)為指紋（Fingerprint），并進(jìn)行存儲(chǔ)。在實(shí)際使用中通過(guò)采集用戶(hù)的實(shí)時(shí)RSS信息，與數(shù)據(jù)庫(kù)中的指紋信息進(jìn)行匹配，從而算出用戶(hù)的實(shí)際坐標(biāo)位置。這種方法無(wú)需特殊的硬件設(shè)施，只需要接收Wi-Fi的信號(hào)強(qiáng)度并且存儲(chǔ)在存儲(chǔ)服務(wù)器，節(jié)省成本，因此應(yīng)用廣泛。本文提出了一種新穎的Wi-Fi指紋庫(kù)構(gòu)建方法。相比較于傳統(tǒng)的指紋庫(kù)構(gòu)建方法，該方法將采集到的指紋信息通過(guò)MDS算法映射到一個(gè)二維指紋空間，表現(xiàn)出指紋之間的距離關(guān)系。而傳統(tǒng)的指紋庫(kù)構(gòu)建方法構(gòu)建出的指紋空間，指紋之間的關(guān)系比較孤立，可能存在較大的錯(cuò)誤和誤差。

指紋地圖構(gòu)建基本框架如圖1。

圖1 指紋地圖構(gòu)建基本框架

（1）根據(jù)建筑物平面圖，將其用網(wǎng)格劃分，每個(gè)交點(diǎn)p(x,y)表示其實(shí)際的坐標(biāo)位置，交點(diǎn)形成原始的位置集合P0={(x,y)|x為橫坐標(biāo)，y為縱坐標(biāo)}；

（2）計(jì)算集合P0中兩兩點(diǎn)之間的距離，形成距離矩陣M0。注意，此處的距離并非指的是兩點(diǎn)之間的直線距離。而是兩點(diǎn)之間的行走距離。對(duì)于兩點(diǎn)之間有障礙物阻擋的情況，則其行走距離必然大于其直線距離；

（3）依據(jù)MDS算法計(jì)算出標(biāo)準(zhǔn)化位置空間SPS；

（4）用戶(hù)利用手機(jī)等移動(dòng)端設(shè)備采集Wi-Fi指紋構(gòu)成原始的Wi-Fi指紋集合：F0={(s1,s2,...,sn)|n}為AP點(diǎn)個(gè)數(shù)，si為測(cè)量點(diǎn)處第i個(gè)Wi-Fi信號(hào)強(qiáng)度，以及連續(xù)兩個(gè)采樣點(diǎn)之間所行走的步數(shù)m；

（5）通過(guò)Floyd-Warshall算法計(jì)算兩個(gè)指紋之間的最短距離。獲得指紋之間的距離矩陣M1；

（6）依據(jù)MDS算法計(jì)算出標(biāo)準(zhǔn)化指紋空間SFS；

（7）通過(guò)采集到的特殊的指紋（走廊、門(mén)口等）利用最小二乘法擬合出SFS到SPS之間的映射關(guān)系：L：SFS→SPS。

1 構(gòu)建標(biāo)準(zhǔn)化位置空間

如圖2為某樓層的平面圖，依照1m間距的網(wǎng)格將其劃分，每個(gè)交點(diǎn)p（x,y）表示其實(shí)際的坐標(biāo)位置。對(duì)于其中的兩個(gè)點(diǎn)pi,pj，由于兩個(gè)點(diǎn)有墻壁阻擋，所以這兩個(gè)點(diǎn)之間的距離為：

由此，我們通過(guò)計(jì)算出集合P0中兩兩點(diǎn)之間的距離得到距離矩陣M0，然后通過(guò)MDS算法將M0映射到一個(gè)二維空間中，形成SPS，如圖3所示，為某樓層的SPS。

其中可以看出，對(duì)于同一個(gè)房間中的點(diǎn)，由于它們的實(shí)際行走距離比較近，因此形成一簇；二對(duì)于不同房間中的點(diǎn)，由于它們之間的行走距離相對(duì)較遠(yuǎn)，則分布在圖中的不同簇中。

2 構(gòu)建標(biāo)準(zhǔn)化指紋空間

類(lèi)似于構(gòu)建SPS的方法，我們首先要獲取到指紋集合F0的距離矩陣，才能計(jì)算出其標(biāo)準(zhǔn)化指紋空間（SFS）。本節(jié)內(nèi)容分為兩部分：（1）采集指紋；（2）計(jì)算集合F0的距離矩陣；（3）計(jì)算SFS。

2.1 采集指紋

我們?cè)O(shè)計(jì)了一款手機(jī)端的APP用來(lái)采集樓層中的Wi-Fi信號(hào)強(qiáng)度和用戶(hù)行走的步數(shù)間隔，上傳到服務(wù)器。對(duì)于兩個(gè)連續(xù)采樣的Wi-Fi指紋fi,fj,他們之間的行走步數(shù)為di,j。當(dāng)收集到足夠的采樣點(diǎn)后，采樣集合F0中共有m個(gè)Wi-Fi指紋。同時(shí)獲得k條采樣路線，每條路線包含若干個(gè)采樣點(diǎn)。

此時(shí)，我們只知道同一條路線上的采樣點(diǎn)之間的距離。而對(duì)于不同路徑上的采樣點(diǎn)的距離我們是不知道的。因此，想要得到距離矩陣，還需要計(jì)算不同采樣路徑上的點(diǎn)之間的距離。

2.2 計(jì)算F0的距離矩陣和SFS

對(duì)于某同一條路徑上的點(diǎn)之間的步行距離是很容易計(jì)算得到。而（1）對(duì)于不同路徑上的點(diǎn)之間的距離還未知；（2）對(duì)于相同路徑上的點(diǎn)也有可能不是其最短路徑，可能有更近的路徑?jīng)]有被發(fā)現(xiàn)，如圖4。因此，我們還要計(jì)算出所有指紋之間的步行距離。

我們使用走廊、門(mén)口等這些特殊點(diǎn)位作為路徑的連接點(diǎn)，并且利用指紋之間的余弦相似度合并其中的相似的指紋。對(duì)于指紋fj=[x1,x2,...,xn],fk=[y1,y2,...,yn],二者之間的余弦相似度為：

圖4 指紋采集路線圖

圖5 合并后的路線圖

當(dāng)其小于某設(shè)定閾值δ,則合并這兩個(gè)指紋。合并后的指紋示意圖如圖5，其中紅色點(diǎn)表示合并后的指紋點(diǎn)，可見(jiàn)對(duì)于走廊上的大多數(shù)的點(diǎn)都將被合并，路徑的交點(diǎn)也會(huì)被合并。進(jìn)而利用Floyd-Warshall算法計(jì)算出兩兩指紋之間的最短路徑。得到距離矩陣M1。

同樣的，以距離矩陣M1作為輸入，利用MDS算法計(jì)算出SFS。

3 構(gòu)建空間映射關(guān)系

根據(jù)獲取到的SPS和SFS（SPS為樓層地圖的具體位置的空間映射，SFS為采集的指紋信息的空間映射）。如果二者能夠從SFS映射到SPS，則就可以實(shí)現(xiàn)指紋定位功能。

對(duì)于SPS中的子集SPSA是樓層地圖中走廊、門(mén)口等特殊位置的空間映射點(diǎn)；對(duì)于SFS中的子集SFSA是采集的指紋集合中的走廊、門(mén)口等特殊位置的空間映射點(diǎn)。現(xiàn)在我們以這些特殊點(diǎn)，利用最小二乘法擬合出SFSA到SPSA之間的映射關(guān)系L：SFS→SPS。

指紋fi∈SFSA的坐標(biāo)為SA的維度。在SPSA中對(duì)應(yīng)的點(diǎn)為可得到如下等式：

經(jīng)過(guò)變換為：

其中。根據(jù)最小二乘法，得到最小化的解析解為：

則根據(jù)可得到變換矩陣A和B，從而可以將SFS中的任意指紋映射到SPS中某個(gè)位置上。

4 結(jié)語(yǔ)

本文提出了一種新的Wi-Fi指紋地圖構(gòu)建方法，該方法基于多維標(biāo)度算法（MDS）將樓層平面圖轉(zhuǎn)化為標(biāo)準(zhǔn)化位置空間（SPS）。收集用戶(hù)采集到的Wi-Fi指紋信息算出指紋的距離矩陣，同樣通過(guò)MDS算法得到標(biāo)準(zhǔn)化指紋空間（SFS）。進(jìn)而利用采集到的特殊走廊、門(mén)口等特殊位置的指紋擬合出SFS到SPS的映射關(guān)系。從而達(dá)到定位的目的。該方法只需少量的人力來(lái)初始化指紋空間，在實(shí)際使用中通過(guò)不斷收集用戶(hù)上傳的指紋信息，重新構(gòu)建SFS和映射關(guān)系，達(dá)到提高定位精度的目的，具有很高的應(yīng)用價(jià)值。

參考文獻(xiàn)：

[1]肖超.基于無(wú)線信號(hào)的室內(nèi)定位方法綜述[J].黑龍江科技信息,2017（12）:62.

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

[3]賈小勇,徐傳勝,白欣.最小二乘法的創(chuàng)立及其思想方法[J].西北大學(xué)學(xué)報(bào)（自然科學(xué)版）,2006（03）:507-511.

[4]席瑞,李玉軍,侯孟書(shū).室內(nèi)定位方法綜述[J].計(jì)算機(jī)科學(xué),2016,43（04）:1-6+32.

[5]阮陵,張翎,許越,鄭星雨.室內(nèi)定位:分類(lèi)、方法與應(yīng)用綜述[J].地理信息世界,2015,22（02）:8-14+30.

[6]趙銳,鐘榜,朱祖禮,馬樂(lè),姚金飛.室內(nèi)定位技術(shù)及應(yīng)用綜述[J].電子科技,2014,27（03）:154-157.