張斯尚，殷鋒，袁平

（1.四川大學(xué)計(jì)算機(jī)學(xué)院，成都610065；2.西南大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，成都610041；3.重慶大學(xué)數(shù)學(xué)與信息工程學(xué)院，重慶400044）

0 引言

成熟的衛(wèi)星定位系統(tǒng)給生活帶來(lái)了極大的便利，但是在室內(nèi)環(huán)境下，由于GPS信號(hào)無(wú)法穿透導(dǎo)致衛(wèi)星定位的方案無(wú)法應(yīng)用在室內(nèi)的環(huán)境中。先前研究中的一些基于無(wú)線電信號(hào)的方案（Wi-Fi、RFID、藍(lán)牙）會(huì)有部署節(jié)點(diǎn)和后期維護(hù)消耗較大的問(wèn)題，不利于傳播，成本較大，因此本文采取基于地磁指紋的定位方案。這種類型的方案由于地磁的普遍存在性、不需要部署電子設(shè)備等優(yōu)勢(shì)在眾多室內(nèi)定位方案中脫穎而出[1]。地磁信號(hào)在時(shí)域上是穩(wěn)定的，并且在空間上是可區(qū)分的，實(shí)際的地理位置能夠用不同的地磁信號(hào)加以區(qū)分，所以地磁RSSI（接收信號(hào)強(qiáng)度）很適合用在室內(nèi)定位場(chǎng)景中。

一般來(lái)說(shuō)，基于地磁的室內(nèi)定位方案工作流程分為3個(gè)步驟[2]：

（1）地磁測(cè)量：勘測(cè)現(xiàn)場(chǎng)環(huán)境、測(cè)量采集地磁信號(hào)是第一步。不同傳感器測(cè)量精度不同，會(huì)一定的誤差。測(cè)量時(shí)的人力消耗等也是考慮的問(wèn)題之一。

（2）地磁信號(hào)指紋庫(kù)的構(gòu)建和維護(hù)：RSSI信號(hào)的之需要和實(shí)際的位置信息進(jìn)行關(guān)聯(lián)。第二步就是將實(shí)際的語(yǔ)義標(biāo)簽（坐標(biāo)）關(guān)聯(lián)到地磁信號(hào)值上，形成一個(gè)可以映射的地圖即指紋庫(kù)。

（3）目標(biāo)定位：當(dāng)用戶請(qǐng)求定位的時(shí)候?qū)?huì)采集當(dāng)前地磁信號(hào)，第三步就是將這個(gè)信號(hào)和指紋庫(kù)的信號(hào)進(jìn)行匹配，最終找到它相應(yīng)的語(yǔ)義標(biāo)簽（坐標(biāo)）顯示給用戶。

研究表明地磁值很容易受到建筑材料鋼筋混凝土或者H型鋼的影響而發(fā)生一些拉伸，產(chǎn)生一些不同于室外地磁場(chǎng)的干擾，形成一些特定的地磁場(chǎng)。而室內(nèi)定位的場(chǎng)景一般發(fā)生在由鋼筋混凝土或者H型鋼這些材料組建而成的建筑里。所以本文利用了這個(gè)特性，提出了改良的構(gòu)建地磁指紋庫(kù)的方法，減少了生成地磁指紋庫(kù)的時(shí)間和計(jì)算消耗，從而改良了算法的特性，使之更加普適。

1 算法可行性分析

定位算法步驟目標(biāo)定位中必不可少的環(huán)節(jié)就是指紋匹配。當(dāng)前主流的基于地磁的指紋定位匹配算法是粒子濾波型的，因?yàn)樗茉诜蔷€性的系統(tǒng)中展示出高的有效性?；谥讣y的方案就是非線性的場(chǎng)景，需要快速地匹配指紋庫(kù)里的數(shù)據(jù)，然而借助粒子濾波算法（貝葉斯概率）匹配指紋需要很大的計(jì)算量。并且通常為了保障定位的精度，指紋庫(kù)里的指紋數(shù)量級(jí)會(huì)很大，這無(wú)疑加重了粒子濾波算法的計(jì)算消耗，同時(shí)時(shí)間也產(chǎn)生了延時(shí)導(dǎo)致了用戶不能及時(shí)獲取定位信息，體驗(yàn)下降。

根據(jù)之前的研究表明[3]，地磁的磁通量和RSSI值很容易受到建筑材料影響而拉伸，之前的方案中沒(méi)有利用這一特性來(lái)改造指紋庫(kù)的做法。利用這種建筑環(huán)境帶來(lái)的優(yōu)勢(shì)，本文提出了一種利用樣條插值來(lái)簡(jiǎn)化指紋庫(kù)構(gòu)建的方法，使之在能夠達(dá)到相同的定位精度的同時(shí)精簡(jiǎn)了指紋庫(kù)，從而減少了目標(biāo)定位階段的計(jì)算消耗，提升了用戶體驗(yàn)的同時(shí)也加快了算法的部署實(shí)施。

因?yàn)榛谥讣y庫(kù)的定位方法一般在設(shè)計(jì)數(shù)據(jù)庫(kù)的時(shí)候需要先將待定位區(qū)域進(jìn)行劃分[4]，選擇參考點(diǎn)進(jìn)行地磁值的采樣。我們將實(shí)驗(yàn)的場(chǎng)地選為四川大學(xué)計(jì)算機(jī)學(xué)院4樓，先將4樓的樓道區(qū)域劃分成一塊塊半徑60cm的區(qū)域，然后在這些區(qū)域里面選出參考點(diǎn)進(jìn)行數(shù)據(jù)采集。采集數(shù)據(jù)的過(guò)程中會(huì)記錄當(dāng)前參考點(diǎn)的坐標(biāo)信息，同一個(gè)參考點(diǎn)的多次值將采用K-means算法找出合適值，最后將合適的RSSI值關(guān)聯(lián)上相關(guān)的地理坐標(biāo)存在數(shù)據(jù)庫(kù)里面。在數(shù)據(jù)庫(kù)更新的時(shí)候也采用同樣的方式進(jìn)行更新。

我們?cè)谒拇ù髮W(xué)計(jì)算機(jī)學(xué)院4樓進(jìn)行了地磁值的采樣，整棟教學(xué)樓主要相關(guān)材料是鋼筋混凝土，實(shí)驗(yàn)平面圖如圖1，彩色的點(diǎn)指代實(shí)驗(yàn)環(huán)境下的采樣點(diǎn)。我們的采樣機(jī)器主要是由一個(gè)遠(yuǎn)程操控的底座小車(chē)和智能手機(jī)組成，如圖2。小車(chē)由底層程序驅(qū)動(dòng)用來(lái)控制前進(jìn)的距離、速度和方向，用作底座，每個(gè)小車(chē)是由鋁合金、丙烯酸、銅版和塑料組成，通過(guò)小車(chē)來(lái)控制采樣點(diǎn)水平方向上的變化，盡量減少了采集的地磁信號(hào)的影響。通過(guò)在底座小車(chē)上墊上平滑的書(shū)本來(lái)控制采樣點(diǎn)垂直高度的變化。實(shí)驗(yàn)中的智能手機(jī)采用華為Mate10作為硬件，內(nèi)嵌了數(shù)據(jù)采集程序。

圖1 四川大學(xué)計(jì)算機(jī)學(xué)院4樓平面圖

圖2 采樣機(jī)器底座

在反復(fù)測(cè)量走廊區(qū)域的地磁值后，取得穩(wěn)定的RSSI地磁值（三軸數(shù)據(jù)取模值），繪制出走廊區(qū)域的RSSI磁場(chǎng)分布圖如圖3，橫軸代表著水平的距離，數(shù)軸代表著垂直的距離，不同顏色表示了不同的RSSI值大小。圖中顯示越靠近混凝土墻壁的地磁值越大，有一種明顯的趨勢(shì)。這種特征值有明顯變化的曲線可以建立數(shù)學(xué)模型進(jìn)行分析，接下來(lái)就引入插值的方式來(lái)補(bǔ)全地磁指紋庫(kù)。

圖3 走廊區(qū)域地磁分布值

2 利用插值的指紋庫(kù)方法

通常的定位算法的定位精確度和地磁信號(hào)的穩(wěn)定性和指紋庫(kù)的精確性成正比。地磁信號(hào)越穩(wěn)定，定位的精度就越高。同樣的指紋數(shù)據(jù)庫(kù)越精確，定位的準(zhǔn)確性就越高[5]?？梢酝ㄟ^(guò)多次采樣，不斷迭代，用濾波器和聚類算法獲得最穩(wěn)定的值，進(jìn)而保證地磁信號(hào)的穩(wěn)定性。而指紋數(shù)據(jù)庫(kù)的精確度受到采樣點(diǎn)的間距影響。間距太長(zhǎng)，定位精度達(dá)不到要求；間距過(guò)短，增加采樣工作的消耗，使得數(shù)據(jù)庫(kù)過(guò)大影響定位速度，導(dǎo)致不良用戶體驗(yàn)。

一般來(lái)說(shuō)，參考點(diǎn)的采集間距是設(shè)置為20cm，衡量了前期的采集消耗和定位精度，這個(gè)間隔距離是能保證定位精度且不消耗多余資源的最佳距離。但是即使是這個(gè)最佳距離，不計(jì)算沿途行走的時(shí)間，在一個(gè)4m的區(qū)域內(nèi)采集數(shù)據(jù)需要消耗10分鐘的時(shí)間。插值的方法是用來(lái)解決定位區(qū)域參考點(diǎn)過(guò)多問(wèn)題的一個(gè)很好的方法。插值法可以用來(lái)預(yù)測(cè)參考點(diǎn)之間的一些地磁RSSI值，加入插值法就能增加采樣點(diǎn)之間的距離從而達(dá)到減少數(shù)據(jù)庫(kù)構(gòu)建消耗的目的。

2.1 三次樣條插值模型

插值的方法是從已知點(diǎn)來(lái)預(yù)估未知點(diǎn)的近似計(jì)算方法，抽象成數(shù)學(xué)概念即需要構(gòu)造一個(gè)多項(xiàng)式函數(shù)，使其通過(guò)所有已知點(diǎn)，然后用求得的函數(shù)預(yù)測(cè)位置點(diǎn)。一個(gè)典型的使用場(chǎng)景就是用在圖像處理上。圖片的被放大后因?yàn)榉直媛实膯?wèn)題像素會(huì)有缺失，可以用插值的方式用周?chē)阎南袼貋?lái)預(yù)測(cè)未知的像素值，通過(guò)諸如線性方程、回歸曲線分析、傅里葉級(jí)數(shù)、樣條曲線、克里克法、移動(dòng)均值、三次樣條方法等等來(lái)實(shí)現(xiàn)。我們采用樣條插值的法案，根據(jù)實(shí)驗(yàn)劃分的小區(qū)域可以建立三次多項(xiàng)式，結(jié)果能夠產(chǎn)生更加平滑的曲線來(lái)通過(guò)一些已知的值，受到的影響更加小，所以建立三次樣條插值的公式。樣條曲線S（x）是一個(gè)分段的定義的公式。假設(shè)我們?cè)趯?shí)驗(yàn)環(huán)境下按照間距L采集N+1個(gè)采樣點(diǎn)（x，y）：

給出的N+1個(gè)采樣點(diǎn)會(huì)形成N個(gè)區(qū)間，在每個(gè)分段區(qū)間[xi，xi+1]，S（x）=Si（x）都是一個(gè)三次多項(xiàng)式。滿足S（xi）=yi，我們建立三次多項(xiàng)式為：

給出樣條曲線后帶入已知點(diǎn)（x，y）就可以求出系數(shù)ai，bi，ci，di。從而補(bǔ)足未知點(diǎn)的值。

2.2 實(shí)驗(yàn)測(cè)得最佳間距

使用插值產(chǎn)生的補(bǔ)足RSSI是用來(lái)更新指紋數(shù)據(jù)庫(kù)的，在初始數(shù)據(jù)庫(kù)建立后更新指紋數(shù)據(jù)庫(kù)。在指紋數(shù) 據(jù) 庫(kù) 中 的 值 是 一 個(gè) 二 維 的 值 {x，y，mag_x，mag_y，mag_z}，（x，y）是空間上的坐標(biāo)信息，mag_x、mag_y、mag_z分別是地磁信號(hào)的三軸數(shù)據(jù)。

實(shí)驗(yàn)設(shè)計(jì)將采樣點(diǎn)的間距作為變量劃分出不同大小的采樣區(qū)域，以定位精度來(lái)評(píng)估最后的效果。初始標(biāo)準(zhǔn)數(shù)據(jù)庫(kù)的間距設(shè)置為20cm，采用傳統(tǒng)的方式獲得指紋數(shù)據(jù)庫(kù)DB_20。實(shí)驗(yàn)時(shí)將間距分別拓展為40cm、60cm和80cm，如圖4，采樣數(shù)據(jù)后獲得數(shù)據(jù)庫(kù)DB_40、DB_60和DB_80。使用插值法補(bǔ)足DB_40、DB_60和DB_80中間缺失的采樣點(diǎn)值產(chǎn)生20cm間距的新的指紋數(shù)據(jù)庫(kù)DB_40_20、DB_60_20和DB_80_20。

最后比較標(biāo)準(zhǔn)數(shù)據(jù)庫(kù)DB_20和插值補(bǔ)足數(shù)據(jù)庫(kù)DB_40_20、DB_60_20和DB_80_20的相似度，數(shù)據(jù)表明在實(shí)驗(yàn)環(huán)境下，本次方法的采樣間距可以到達(dá)60cm，這種補(bǔ)足的數(shù)據(jù)庫(kù)可以和原始的采樣間距為20cm的數(shù)據(jù)庫(kù)相媲美。如圖5和圖6，分別計(jì)算了標(biāo)準(zhǔn)數(shù)據(jù)庫(kù)DB_20和插值補(bǔ)足數(shù)據(jù)庫(kù)DB_40_20和DB_60_20，可以看到插值算法補(bǔ)足數(shù)據(jù)庫(kù)和原始的數(shù)據(jù)庫(kù)數(shù)據(jù)值基本接近。即是說(shuō)給出的插值算法滿足可以至少將采樣間距擴(kuò)展到60cm，極大減少了采集過(guò)程的工作。

圖4 對(duì)比標(biāo)準(zhǔn)采集點(diǎn)和插值補(bǔ)足點(diǎn)

圖5 標(biāo)準(zhǔn)采樣數(shù)據(jù)庫(kù)和插值數(shù)據(jù)庫(kù)DB40的相似度對(duì)比

圖6 標(biāo)準(zhǔn)采樣數(shù)據(jù)庫(kù)和插值數(shù)據(jù)庫(kù)DB60的相似度對(duì)比

3 結(jié)語(yǔ)

本文的目標(biāo)是減少指紋數(shù)據(jù)庫(kù)構(gòu)建消耗，首先是證明建筑材料會(huì)對(duì)磁通量產(chǎn)生拉伸，較大程度影響了室內(nèi)地磁指紋，進(jìn)而指明建立數(shù)學(xué)模型的可行性。隨后驗(yàn)證在構(gòu)建指紋庫(kù)的時(shí)候使用插值方法可以增加采樣間距，在前期構(gòu)建上減少了消耗。但是由于指紋庫(kù)中的指紋相似度很高，接下來(lái)的工作將從補(bǔ)足粒子濾波算法上入手，使數(shù)據(jù)庫(kù)更加的精簡(jiǎn)。