室內(nèi)定位:挑戰(zhàn)與機(jī)遇

楊　錚,徐京傲,YAO Lina

(1.清華大學(xué) 軟件學(xué)院，北京　100084;2.新南威爾士大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，澳大利亞 悉尼　2052)

伴隨著物聯(lián)網(wǎng)技術(shù)與各種各樣基于室內(nèi)位置應(yīng)用的快速發(fā)展[1-2],對(duì)高精度以及實(shí)時(shí)性的室內(nèi)定位服務(wù)需求變得越來越強(qiáng)烈。在過去的十年之中,基于WiFi[3]、RFID[4-6]、聲音信號(hào)[7]、磁場信號(hào)[8]以及慣性傳感器[9-11]等眾多室內(nèi)定位技術(shù)發(fā)展了起來。在所有以上的技術(shù)之中,由于WiFi設(shè)施的實(shí)用性以及已經(jīng)在各種室內(nèi)場景中被廣泛地布置，使得基于WiFi的室內(nèi)定位技術(shù)在所有技術(shù)之中最具有吸引力。許多大公司包括蘋果、思科、華為以及百度等都研發(fā)了基于WiFi室內(nèi)定位相關(guān)的產(chǎn)品。

基于WiFi的室內(nèi)定位技術(shù)主要有兩種不同的方向:基于測距的定位技術(shù)與基于指紋的定位技術(shù)。基于測距的定位技術(shù)利用信號(hào)在空間傳播的過程，這也是信號(hào)能量衰減的一個(gè)過程,并且傳播距離越遠(yuǎn)信號(hào)衰減得也越強(qiáng)烈,從而這種衰減暗含了距離信息。基于測距的定位技術(shù)根據(jù)當(dāng)前位置接收到的信號(hào)強(qiáng)度來推算出與接入點(diǎn)之間的距離，從而進(jìn)行定位?；谥讣y的定位技術(shù)利用當(dāng)前位置多個(gè)接受信號(hào)強(qiáng)度直接進(jìn)行位置估計(jì)，而不利用信號(hào)強(qiáng)度進(jìn)行測距,通常將特定位置上的多個(gè)信號(hào)的信號(hào)強(qiáng)度排列在一起構(gòu)造成為一個(gè)高維的向量,這個(gè)向量稱為該位置的無線指紋,通過計(jì)算采集指紋與數(shù)據(jù)庫各個(gè)指紋之間的相似度可以定位未知節(jié)點(diǎn)。

然而,在復(fù)雜的真實(shí)環(huán)境之中,信號(hào)傳播的動(dòng)態(tài)特性以及環(huán)境的不穩(wěn)定性通常會(huì)對(duì)信號(hào)傳播距離的計(jì)算產(chǎn)生很大的誤差,從而使得基于測距的定位技術(shù)很難達(dá)到較高的精度。在目前的實(shí)際運(yùn)用中,基于指紋的定位技術(shù)最廣泛。為了帶領(lǐng)讀者更深入地了解這一項(xiàng)正在蓬勃發(fā)展的技術(shù),本文通過理清基于指紋的室內(nèi)定位技術(shù)的發(fā)展脈絡(luò),展示不同定位方法的優(yōu)勢與不足,同時(shí)展望未來指紋定位的發(fā)展方向。

1　早期指紋定位

早期指紋定位系統(tǒng)體現(xiàn)了指紋定位的基本方法,到目前為止,這些方法也依然在室內(nèi)定位領(lǐng)域有著旺盛的生命力。在此,我們介紹兩種經(jīng)典的室內(nèi)定位系統(tǒng):RADAR[12]與Horus[3],借此兩個(gè)系統(tǒng)來展示指紋定位的核心方法。

1.1　開山之作——RADAR

RADAR[12]是使用無線指紋進(jìn)行室內(nèi)定位的開山之作,RADAR的出發(fā)點(diǎn)在于對(duì)于同一個(gè)信號(hào)接入點(diǎn)(Access point,AP)產(chǎn)生的WiFi信號(hào),不同位置的接收信號(hào)強(qiáng)度(Received signal strength,RSS)會(huì)有一定的區(qū)分度,同一位置的RSS會(huì)保持相對(duì)的穩(wěn)定。基于此兩項(xiàng)RSS分布的特點(diǎn),我們將特定位置上的多個(gè)AP的RSS值排列在一起構(gòu)成的高維向量稱為該位置的WiFi信號(hào)指紋,通過計(jì)算不同指紋之間的相似度來定位未知節(jié)點(diǎn)。RADAR等一系列基于指紋定位的系統(tǒng)主要包含兩個(gè)階段:線下階段與線上階段。

在線下階段,RADAR通過收集所有AP的RSS空間分布信息,完成信號(hào)強(qiáng)度位置(RSS-location)數(shù)據(jù)庫的構(gòu)建。具體而言,可以得到空間之中所有采樣點(diǎn)的位置空間L={l1,l2,…,ln},其中n是空間之中采樣點(diǎn)的個(gè)數(shù),li表示的RSS指紋采樣點(diǎn)坐標(biāo)為(xi,yi)。

在線上階段,定位系統(tǒng)根據(jù)構(gòu)建好的指紋位置數(shù)據(jù)庫提供定位服務(wù)。一個(gè)未知位置的節(jié)點(diǎn)測量其當(dāng)前所處位置的所有AP的RSS值，并形成一條查詢RSS指紋，然后將該查詢指紋上傳到定位服務(wù)器。定位服務(wù)器將該查詢指紋依次與數(shù)據(jù)庫之中的指紋計(jì)算相似度,并利用最近鄰(nearest neighbor)或者K-近鄰(K-Nearest Neighbor, KNN)算法返回定位結(jié)果。在評(píng)估指紋的相似性方面,最常用的方法是計(jì)算兩個(gè)指紋向量之間的p-范數(shù)距離。具體來說,如果有一條查詢指紋fQ,目前與之匹配的數(shù)據(jù)庫中候選指紋為fC,那么兩條指紋之間的距離d(fQ,fC)可以表示為

d(fQ,fC)=‖fQ-fC‖p=

(1)

其中，m是所有AP的個(gè)數(shù),在通常情況之中p取2,p-范數(shù)距離退化為歐式距離。在最近鄰算法下,定位結(jié)果可以表示為

(2)

1.2　改進(jìn)策略——Horus

Horus[3]是基于無線指紋定位中比較經(jīng)典、用途很廣的系統(tǒng)之一。Horus改進(jìn)了采用確定性指紋匹配策略的RADAR系統(tǒng)。在實(shí)際環(huán)境之中,如圖1所示,RSS具有一定的波動(dòng)性,并且這種波動(dòng)性近似一個(gè)正態(tài)分布。Horus提出了基于統(tǒng)計(jì)的方法,將所有位置上采集到的指紋中每一個(gè)的RSS值建模為一個(gè)高斯分布,同時(shí),對(duì)指紋匹配的算法由計(jì)算歐氏距離改為最大似然估計(jì)的方法。

圖1　RSS波動(dòng)性示意圖Fig.1　RSS bias over time

2　傳統(tǒng)方法的局限性

利用無處不在的WiFi信號(hào)進(jìn)行室內(nèi)定位是定位技術(shù)上的一項(xiàng)重大的突破,盡管RADAR與Horus系統(tǒng)提出了室內(nèi)定位技術(shù)的核心方法與技術(shù),但這兩種傳統(tǒng)的技術(shù)也面臨著極大的挑戰(zhàn),包括:指紋的空間歧義性、指紋的時(shí)間不穩(wěn)定性以及硬件多樣性[13]。之后不斷發(fā)展與完善的指紋定位新方法可以說都是在從不同的角度來解決這些問題。

2.1　指紋空間歧義性

由于室內(nèi)環(huán)境的復(fù)雜性以及多徑效應(yīng),兩個(gè)距離比較遠(yuǎn)的位置處的WiFi信號(hào)RSS指紋可能會(huì)十分相似,導(dǎo)致定位算法會(huì)出現(xiàn)指紋的錯(cuò)誤匹配從而產(chǎn)生較大的誤差。如圖2所示,將數(shù)據(jù)庫之中(6,2)位置的指紋與數(shù)據(jù)庫之中的每一個(gè)位置的指紋計(jì)算歐拉距離,圖中顏色越紅代表距離越小,可以看出(6,2)與(2,3)這兩個(gè)點(diǎn)雖然空間距離比較遠(yuǎn),但是他們的指紋卻長得十分相似,這也就是指紋的空間歧義性。指紋的空間歧義性是最影響指紋定位效果的原因之一,在實(shí)際場景之中,定位系統(tǒng)即使出現(xiàn)了一些小的誤差也不會(huì)影響用戶的體驗(yàn),比如在一個(gè)商場之中,一個(gè)店面的寬度可能就為3m左右,這時(shí)如果我們的定位系統(tǒng)僅存在1m左右的誤差并不會(huì)影響用戶的使用,但指紋的空間歧義性卻會(huì)使距離很遠(yuǎn)的兩個(gè)點(diǎn)錯(cuò)誤地匹配上,可能某個(gè)位置會(huì)達(dá)到8m以上的誤差,這會(huì)嚴(yán)重影響用戶的體驗(yàn)。在近幾年的WiFi定位系統(tǒng)的研究工作中,提升WiFi定位精度的重要工作就是努力解決指紋的空間歧義性。

圖2　空間歧義性示意圖Fig.2　Fingerprint spatial ambiguty

2.2　指紋時(shí)間波動(dòng)性

在實(shí)際環(huán)境之中,在同一個(gè)位置收集到的同一個(gè)AP的信號(hào)強(qiáng)度是會(huì)不斷變化的,這主要出于兩個(gè)原因:第一個(gè)原因是在信號(hào)傳播的過程中可能存在著一個(gè)正態(tài)分布的誤差干擾,如圖3所示,在同一個(gè)位置連續(xù)采集相同AP的RSS值本身就很類似正態(tài)分布;第二個(gè)原因是由于室內(nèi)無線環(huán)境不同,一些商業(yè)AP在不同信道狀態(tài)不同的情況下會(huì)自動(dòng)調(diào)整信道增益,這為保證通訊質(zhì)量做出了貢獻(xiàn)，但是卻給定位帶來極大的不便利性。

圖3　RSS波動(dòng)性示意圖Fig.3　RSS bias over time

圖4與圖5清楚地展示了指紋時(shí)間不穩(wěn)定性,圖4是數(shù)據(jù)庫所有位置的指紋互相計(jì)算指紋的歐式距離的距離矩陣,很顯然,越靠近對(duì)角線的兩個(gè)指紋越相似。過了一段時(shí)間我們?cè)俅问占形恢玫闹讣y并與數(shù)據(jù)庫之中各點(diǎn)原先的指紋計(jì)算指紋距離,結(jié)果如圖5所示,可以看出圖4和圖5已經(jīng)完全不相同,相似指紋出現(xiàn)的位置已經(jīng)毫無規(guī)律可言,這充分體現(xiàn)了指紋的時(shí)間波動(dòng)性。在實(shí)際系統(tǒng)的應(yīng)用過程之中,由于指紋時(shí)間波動(dòng)性的存在,線下階段采集的指紋數(shù)據(jù)庫一段時(shí)間之后就會(huì)失效,這會(huì)導(dǎo)致指紋定位的錯(cuò)誤匹配,同時(shí),為了重新獲得有效的指紋數(shù)據(jù)庫，又需要消耗大量的人力,這些都限制了指紋定位系統(tǒng)的實(shí)用性。

圖4　指紋相似度矩陣Fig.4　The matrix for fingerprint similarity

圖5　新指紋與老指紋相似度矩陣Fig.5　The similarity matrix for new and origin fingerprints

2.3　硬件多樣性

除了指紋的時(shí)間不穩(wěn)定性以及空間歧義性之外,硬件上的多樣性也是限制指紋定位系統(tǒng)沒能夠廣泛應(yīng)用的一個(gè)重要原因。硬件多樣性是指即使在相同的位置、時(shí)間、環(huán)境甚至相同的采集方式的前提下,不同硬件采集到的相同AP的RSS值都會(huì)存在一定的差異,這是由于不同的硬件在天線等設(shè)計(jì)上的差異造成的必然結(jié)果。如圖6所示，選取了兩個(gè)Nexus 6p，一個(gè)Nexus 7進(jìn)行實(shí)驗(yàn),計(jì)算出的兩組相同位置RSS測量值偏差的CDF圖,可以看出即使是相同型號(hào)的手機(jī)也會(huì)出現(xiàn)測量值的偏差,不同型號(hào)的手機(jī)偏差值會(huì)更加顯著。在實(shí)際的情況中,這給我們構(gòu)造的指紋數(shù)據(jù)庫的普適性帶來了很大的挑戰(zhàn)。

圖6　硬件多樣性示意圖Fig.6　RSS bias over different devices

以上介紹的指紋空間歧義性、時(shí)間波動(dòng)性以及硬件多樣性是目前指紋定位系統(tǒng)沒能廣泛運(yùn)用于實(shí)際生活之中的瓶頸所在,掌握了這些問題,我們可以更全面地認(rèn)識(shí)近幾年提出的先進(jìn)的指紋定位系統(tǒng)的創(chuàng)新之處。

3　發(fā)展中的指紋定位

為了解決上文提到的指紋定位系統(tǒng)的3種挑戰(zhàn),眾多的定位系統(tǒng)都從各自的角度來進(jìn)行優(yōu)化與創(chuàng)新,這些角度可以分為3個(gè)方面:更魯棒的匹配算法、更魯棒的指紋、更普適的指紋。接下來將從這3個(gè)分類來介紹一些目前已有的最先進(jìn)的算法。

3.1　更魯棒的匹配算法

當(dāng)我們?cè)谖粗恢貌杉搅艘粭l指紋之后，需要遍歷指紋數(shù)據(jù)庫之中的每一條指紋,將他們依次與未知位置的指紋進(jìn)行匹配,最后將指紋距離最小的指紋對(duì)應(yīng)的位置作為定位結(jié)果。在這個(gè)過程之中，可以看出計(jì)算兩條指紋相似的匹配算法是一個(gè)非常重要的環(huán)節(jié),傳統(tǒng)的定位系統(tǒng)(如RADAR)之中通常使用兩個(gè)向量之間的歐式距離對(duì)其進(jìn)行匹配,但由于指紋的波動(dòng)性，通常簡單地計(jì)算歐式距離會(huì)存在較大的定位偏差;改進(jìn)策略的Horus將信號(hào)強(qiáng)度的波動(dòng)抽象成為一個(gè)正態(tài)分布的概率模型,從而將出現(xiàn)該條指紋概率最大的位置作為定位結(jié)果,但由于正態(tài)分布只是理論上的結(jié)果,在實(shí)際之中也會(huì)有很大的偏差。在本節(jié)中,我們介紹兩種室內(nèi)定位算法,了解它們?cè)隰敯粜云ヅ涞膭?chuàng)新之處。

3.1.1分布匹配:KL-散度KL-散度(KL-Divergence)[14]核心出發(fā)點(diǎn)與Horus類似,都是利用概率的辦法找出一個(gè)出現(xiàn)該條指紋概率最大的位置,但與Horus不同,KL-散度沒有將AP的RSS分布抽象成為一個(gè)正態(tài)分布,而是計(jì)算未知位置的RSS分布與采樣RSS分布之間的KL-散度。KL-散度是一個(gè)統(tǒng)計(jì)學(xué)上常用的比較兩個(gè)分布相似程度的標(biāo)準(zhǔn),具體來說,如果兩個(gè)概率分布的密度函數(shù)為p與q,在密度函數(shù)離散的情況下定義式(3)，

(3)

在數(shù)學(xué)意義上KL(p‖q)可以理解為如果我們用q來代替p所帶來的信息損耗。p與q的KL-散度D進(jìn)而被定義為

D(p,q)=KL(p‖q)+KL(q‖p)。

(4)

下面將KL-散度運(yùn)用到我們的指紋定位系統(tǒng)之中。定義S={S1,S2，…,SJ}為某一位置采集到的所有APi(i=1,2,…,J)下的RSS采樣集合。當(dāng)我們?cè)谖粗恢?x,y)采集到的所有AP下的RSS分布為p=p(S|{x,y}),遍歷指紋數(shù)據(jù)庫之中的每一個(gè)點(diǎn),得到的數(shù)據(jù)庫準(zhǔn)確位置(xl,yl)，所有AP下的RSS分布為q=q(S|{xl,yl})，將KL-散度作為兩組分布之間的匹配標(biāo)準(zhǔn),具體定義為

(5)

相比于Horus,KL-散度沒有將信號(hào)強(qiáng)度的分布抽象成為一個(gè)具體的概率模型,而是通過單純地匹配兩個(gè)分布從而增強(qiáng)了匹配的魯棒性。KL-散度系統(tǒng)相比于Hours效果提升了30%以上。

3.1.2考慮AP權(quán)重DorFin相比于Horus與KL-散度將AP的分布抽象為一個(gè)概率模型,DorFin[15]直接通過兩條指紋之間的魯棒匹配來增強(qiáng)系統(tǒng)的準(zhǔn)確性。具體來說，在實(shí)際環(huán)境中，信號(hào)強(qiáng)度隨距離變化的理想數(shù)學(xué)模型可以被刻畫為對(duì)數(shù)距離路徑損失模型(Log-distance path loss model, LDPL)，

(6)

(7)

其中,f0是一個(gè)固定的RSS強(qiáng)度(在DorFin的實(shí)驗(yàn)中取值為-55dB),η是LDPL公式中的路徑損耗參數(shù),α與c是根據(jù)η來確定的常數(shù)。通過式(7)可以看出,當(dāng)接收到某個(gè)AP的信號(hào)強(qiáng)度比較強(qiáng)的時(shí)候,我們通過LDPL模型估算距離計(jì)算出一個(gè)比較大的權(quán)重;當(dāng)信號(hào)強(qiáng)度比較弱的時(shí)候,我們通過模型來賦予一個(gè)比較小的權(quán)重,這樣使得指紋的匹配更加魯棒。

3.2　更魯棒的指紋

除了更加魯棒的指紋匹配算法之外,目前在室內(nèi)定位系統(tǒng)上創(chuàng)新最多的地方是尋找更加魯棒的指紋,正如前文所說,在定位的過程中，最直觀能用的信息就是AP的RSS強(qiáng)度,但計(jì)算RSS的理論公式并不一定是完全準(zhǔn)確的,所以直接使用RSS作為指紋可能會(huì)在本質(zhì)上造成難以避免的誤差。更魯棒的指紋將相鄰位置RSS之間的梯度關(guān)系或者連續(xù)采樣得到的RSS之間的變化趨勢作為更魯棒的結(jié)構(gòu)進(jìn)行匹配,從而取得了更好的定位結(jié)果。在本節(jié)中,我們將介紹幾種經(jīng)典的魯棒性指紋定位系統(tǒng)。

1.2.2.2 環(huán)境準(zhǔn)備 為患者提供一個(gè)舒適、安靜、光線柔和的房間，沒有條件的可以拉上屏風(fēng)或簾子營造一個(gè)相對(duì)獨(dú)立、私密的空間，請(qǐng)其他病友保持安靜，不要大聲講話，手機(jī)關(guān)機(jī)。給予患者舒適體位。

3.2.1WiFi“地標(biāo)”:Walkie-MarkieWalkie-Markie[16]是一個(gè)典型的利用用戶在行走的過程中連續(xù)測量的WiFi信號(hào)進(jìn)行定位的系統(tǒng),之后基于連續(xù)測量的室內(nèi)定位方法都或多或少受Walkie-Markie的影響。Walkie-Markie系統(tǒng)不使用RSS的絕對(duì)讀數(shù),而是使用用戶在行走過程中RSS的變化趨勢。如圖7所示,雖然我們并不知道RSS衰減的準(zhǔn)確公式,但是可以肯定的是，距離越遠(yuǎn),接收到的RSS越小,所以當(dāng)用戶從靠近到遠(yuǎn)離AP的時(shí)候,接收到的RSS強(qiáng)度會(huì)先增大后減小。反過來,如果RSS的變化出現(xiàn)這個(gè)趨勢,那么可以認(rèn)為在這周圍出現(xiàn)了一個(gè)WiFi“地標(biāo)”,如果我們用三元組來記錄這個(gè)WiFi地標(biāo),可以表示為WM={BSSID,(D1,D2),N},其中BSSID是該AP的MAC層地址,用來區(qū)分空間之中的AP,D1與D2代表靠近地標(biāo)和遠(yuǎn)離地標(biāo)的方向,該方向可以通過采集的地磁數(shù)據(jù)得出,N代表該位置收集到的其他AP,這是為了區(qū)分開兩條平行的軌跡。在線下階段,通過用戶不斷行走過程中采集到的連續(xù)RSS構(gòu)造空間的Wifi地標(biāo)-RSS變化趨勢數(shù)據(jù)庫;在線上階段,通過比較用戶在運(yùn)動(dòng)過程中采集到的所有AP的RSS變化趨勢在數(shù)據(jù)庫中找到相應(yīng)的地標(biāo)位置從而進(jìn)行定位。由于Walkie-Markie在整個(gè)過程中沒有用到RSS的絕對(duì)讀數(shù)，而只是使用了用戶在行走過程之中的RSS變化趨勢,使得系統(tǒng)的魯棒性取得了大幅度的提升。

圖7　WiFi地標(biāo)示意圖Fig.7　Illustration of using WiFi landmarks

(8)

由于實(shí)際采樣次數(shù)(>50次)已經(jīng)不算是一個(gè)小樣本,所以這里GIFT采用t-統(tǒng)計(jì)檢測方法，這里的t值可以為

(9)

通過查找t-分布表可以查到tk對(duì)應(yīng)的概率,如果這個(gè)概率大于置信區(qū)間1-α,那么就有理由拒絕原假設(shè)H0而接受備擇假設(shè)H1,也就是代表著實(shí)際結(jié)果顯示μik≠μjk,反之亦然,需要說明的是在這里置信區(qū)間0.85≤1-α≤0.95,在實(shí)際運(yùn)用之中GIFT取1-α=0.92。

圖8　GIFT示意圖Fig.8　Illustration of GIFT

如圖9所示,對(duì)于每一個(gè)位置的指紋來說,ViVi結(jié)合周圍臨近位置的指紋構(gòu)造一條FSG曲線,FSG曲線刻畫了當(dāng)前的指紋和一些周圍位置指紋之間的相似度變化趨勢,位置li位置的FSG曲線gi為

gi={〈d(li,lj),φ(fi,fj)〉,i-r≤j≤i+r}。

(10)

其中,φ(fi,fj)是位置li的指紋fi與位置lj的指紋fj之間的指紋相似度,通?？坍嫗闅W氏距離;d(li,lj)是位置li與位置lj之間的物理距離,位置li-1到位置li-r和位置li+1到位置li+r是圍繞在當(dāng)前位置li兩側(cè)的周圍位置子集。在匹配時(shí)，有兩條FSG曲線gQ={〈dQ,φQ〉}與gC={〈dC,φC〉},由于在構(gòu)造FSG曲線的時(shí)候都選取了2r+1個(gè)點(diǎn)并且排列方式相同,所以匹配gQ與gC實(shí)際上就是在匹配φQ與φC,在ViVi之中使用了效果不錯(cuò)的余弦相似度來對(duì)相似度進(jìn)行刻畫，

(11)

圖9　FSG曲線示意圖Fig.9　Illustration of FSG profile

除了提出了FSG這種魯棒性的匹配結(jié)構(gòu),ViVi在其基礎(chǔ)上還設(shè)計(jì)了精妙的選取周圍點(diǎn)的辦法以及FSG匹配算法,相比于目前已有的定位系統(tǒng)的精度提升了20%以上。

3.3　更普適的指紋

實(shí)現(xiàn)更加細(xì)粒度的定位。本小節(jié)通過介紹幾種融合額外傳感器數(shù)據(jù)的定位方法來了解這種室內(nèi)定位領(lǐng)域發(fā)展的新趨勢。

3.3.1WiFi+地磁由于在空間之中無處不在并且比WiFi有更強(qiáng)的抗動(dòng)態(tài)性，使得地磁信號(hào)逐步走入了室內(nèi)定位領(lǐng)域[8,18-19]。如圖10所示,可以發(fā)現(xiàn)在定位效果上,WiFi在大范圍上的區(qū)分效果比較好,不同的屋子或者相距很遠(yuǎn)的兩個(gè)位置的指紋會(huì)很不相似;而地磁信號(hào)在細(xì)粒度上的區(qū)分效果更加良好,即使兩個(gè)位置比較接近,但是采集到的地磁信號(hào)強(qiáng)度也會(huì)有一定的差異,所以，基于以上的觀察，結(jié)合WiFi與地磁進(jìn)行定位能夠融合兩種信號(hào)之間的優(yōu)勢,是一種理想的定位方法。

結(jié)合WiFi與地磁信號(hào)的核心方法是:用戶在行走一條軌跡的過程之中會(huì)采集到了一系列指紋與地磁信號(hào)強(qiáng)度序列,一方面可以根據(jù)Wi-Fi指紋定位算法算出用戶行走的軌跡,另一方面,可以通過動(dòng)態(tài)時(shí)間規(guī)整(Dynamic time wrapping, DTW)算法，通過地磁信號(hào)強(qiáng)度序列匹配出數(shù)據(jù)庫中相似度最高的一段軌跡,這樣就通過不同的定位方法算出了兩種軌跡,通過Wi-Fi計(jì)算出的軌跡全局性高,能大體知道用戶在空間中的位置;用地磁信號(hào)算出的軌跡形狀精確,能夠知道用戶行走的方向與距離,因此,將兩種結(jié)果結(jié)合就實(shí)現(xiàn)了對(duì)用戶的軌跡追蹤。當(dāng)然,地磁信號(hào)強(qiáng)度序列計(jì)算出的軌跡也能糾正WiFi指紋定位存在的空間歧義問題。

圖10　不同信號(hào)定位效果示意圖Fig.10　Illustration of localization results of different signals

3.3.2WiFi+慣導(dǎo)利用慣性測量單元(Inertial measurement unit, IMU)協(xié)助WiFi進(jìn)行室內(nèi)定位或者軌跡追蹤的思路與WiFi+地磁類似[11,20],都是利用WiFi算出一個(gè)大體的位置,再由IMU數(shù)據(jù)解算出用戶行走的一個(gè)精確的軌跡,結(jié)合二者從而實(shí)現(xiàn)高精度的室內(nèi)定位或追蹤。

圖11展示了利用IMU協(xié)助定位的一般示意圖,加速度計(jì)會(huì)不斷檢測用戶是否發(fā)生了運(yùn)動(dòng),如果檢測到用戶行走,利用對(duì)陀螺儀數(shù)據(jù)的積分可以算出用戶行走的方向與距離,利用這個(gè)精確的方向與距離結(jié)合WiFi定位的結(jié)果就可以實(shí)現(xiàn)對(duì)用戶精確的定位。至于結(jié)合兩種定位方法的算法,目前用途最廣泛的是卡爾曼濾波器(Kalman-Filter, KF)與粒子濾波器(Particle-Filter, PF)?？柭鼮V波器的工作方式是對(duì)IMU算出的用戶下一時(shí)刻位置與用WiFi估算出的位置進(jìn)行加權(quán)平均;粒子濾波器工作流程如圖12所示,在用戶的當(dāng)前位置周圍隨機(jī)撒下很多粒子,所有的粒子按照IMU數(shù)據(jù)計(jì)算出的軌跡信息進(jìn)行相同的轉(zhuǎn)移,在根據(jù)與采集到的WiFi指紋進(jìn)行相似度匹配，給每一個(gè)粒子計(jì)算一個(gè)權(quán)重,之后取權(quán)重最高的前10%的粒子的加權(quán)平均作為用戶下一時(shí)刻的位置。

圖11　IMU協(xié)助定位示意圖Fig.11　Illustration of IMU-assisted system

圖12　粒子濾波器流程示意圖Fig.12　Illustration of Particle-Filter

3.3.3WiFi+聲音區(qū)別于上述的WiFi+傳感器需要引入一條軌跡的方式,WiFi+聲音[7，21]采用了多用戶協(xié)同定位的方法。如圖13所示,當(dāng)多個(gè)用戶進(jìn)行協(xié)同定位時(shí),利用聲音信號(hào)測量兩兩用戶之間距離,利用用戶之間的這個(gè)準(zhǔn)確的位置多邊形對(duì)WiFi指紋定位的結(jié)果進(jìn)行限制,有效減輕指紋定位的空間歧義性與時(shí)間不穩(wěn)定性。在通過聲音測距的過程之中,為了不影響用戶的體驗(yàn)，通常是麥克風(fēng)發(fā)送一段超聲波,利用Beep算法進(jìn)行測距。

圖13　WiFi+聲音多用戶協(xié)同定位示意圖Fig.13　Illustration of indoor peer-assisted localization

3.3.4WiFi+圖像WiFi+圖像與WiFi+聲音的定位方法核心思想類似,WiFi+圖像[22]的定位算法利用多個(gè)圖像計(jì)算出用戶的實(shí)際位置空間多邊形來限制指紋定位的結(jié)果,從而實(shí)現(xiàn)高精度的室內(nèi)定位。如圖14所示,用戶在4個(gè)位置分別拍攝了一些圖片并且采集到了所在位置的WiFi指紋,利用 SfM算法在圖像數(shù)據(jù)庫之中匹配拍攝的圖片,形成一個(gè)圖像定位四邊形,這個(gè)四邊形相對(duì)而言比較精確。再在指紋數(shù)據(jù)庫之中匹配指紋,得到一個(gè)WiFi定位多邊形,這個(gè)多邊形只能知道用戶大體上的空間位置。最后,結(jié)合這兩個(gè)多邊形就能夠?qū)τ脩魧?shí)現(xiàn)高精度的室內(nèi)定位。相比于基于聲音測距的方法,計(jì)算機(jī)視覺領(lǐng)域上的圖片匹配算法更加精準(zhǔn),同時(shí)利用圖像的方法還不需要多個(gè)用戶進(jìn)行協(xié)作,提高了系統(tǒng)的易用性。除此之外,從一張圖片之中可以發(fā)掘出大量的語義信息,這些語義信息也會(huì)為我們提供進(jìn)一步的服務(wù)。

4　指紋定位的未來

從開山之作RADAR誕生開始的近20年之中,基于WiFi指紋的室內(nèi)定位技術(shù)層出不窮,也伴隨著技術(shù)的發(fā)展融入新的定位手段，從而給這個(gè)傳統(tǒng)的領(lǐng)域帶來了新的生機(jī)。本文所列出的一些定位系統(tǒng)只是這個(gè)領(lǐng)域中比較有代表性的很小的一部分。盡管定位手段多種多樣,但在實(shí)際中能有效運(yùn)行的卻并不是很多,這主要有兩部分原因:第一個(gè)重要的原因是我們無法準(zhǔn)確刻畫信號(hào)傳播模型以及實(shí)際空間中的環(huán)境復(fù)雜性，導(dǎo)致“魯棒”的匹配算法與“魯棒”的指紋并沒有那么“魯棒”,一些魯棒性的前提假設(shè)在實(shí)際環(huán)境面前面臨著挑戰(zhàn);第二個(gè)重要的原因是基于WiFi指紋的定位方式都需要前期進(jìn)行指紋數(shù)據(jù)庫的構(gòu)建以及指紋數(shù)據(jù)庫的維護(hù),這導(dǎo)致指紋定位系統(tǒng)需要大量的人力開銷,在大規(guī)模場景下難以部署?；谝陨现讣y定位存在的問題，指紋定位技術(shù)未來的發(fā)展有以下幾個(gè)方面。

圖14　WiFi+圖像協(xié)助定位示意圖Fig.14　Illustration of computer vision-based localization

4.1　更實(shí)用的室內(nèi)定位技術(shù)

指紋定位技術(shù)的實(shí)用性包括指紋的魯棒性以及系統(tǒng)的可維護(hù)性。如何從傳統(tǒng)的指紋基礎(chǔ)之上提取出魯棒的結(jié)構(gòu)是重中之重,比如RSS讀數(shù)可能是不魯棒的,但距離AP越近RSS越大,距離AP越遠(yuǎn)RSS越小，這個(gè)關(guān)系是魯棒的,如何發(fā)掘這些特征是實(shí)現(xiàn)魯棒性的重要問題。而系統(tǒng)的可維護(hù)性主要體現(xiàn)在眾包技術(shù)以及指紋數(shù)據(jù)庫更新技術(shù)中,減輕系統(tǒng)的人力開銷也是需要解決的一個(gè)重要問題。

4.2　更智能的室內(nèi)定位技術(shù)

正如3.3.3節(jié)WiFi+圖像中提到的,從一張圖片中可以發(fā)掘出大量的語義信息,如何利用這些語義信息也會(huì)給定位系統(tǒng)帶來智能化的突破,在之后可能用戶想知道的不僅僅是一個(gè)空間中的二維坐標(biāo),而更想知道的是:我想去KFC應(yīng)該怎么走?我應(yīng)該怎么找到他/她?他/她和誰在一起做什么?所以在未來的發(fā)展中，WiFi+計(jì)算機(jī)視覺的技術(shù)會(huì)在定位領(lǐng)域有所發(fā)展與突破。

禪宗提到過悟道三境界:第一重是在悟道初期，“看山是山,看水是水”;第二重是小有所成，“看山不是山,看水不是水”;第三重是真正領(lǐng)悟大道,返歸“看山還是山,看水還是水”的境界。其實(shí)室內(nèi)定位發(fā)展的腳步也是這樣的一個(gè)過程,早期的室內(nèi)定位系統(tǒng)用單純的WiFi指紋進(jìn)行定位,雖小有所成但難以突破自身的局限性。在技術(shù)發(fā)展的過程中引入大量傳感數(shù)據(jù)協(xié)同定位,取得大量的突破，但由于對(duì)用戶的使用與系統(tǒng)的維護(hù)進(jìn)行過多的限制導(dǎo)致仍然沒能實(shí)用,但這一階段的發(fā)展開闊了我們的研究思路,使得我們對(duì)信息的使用提升了一個(gè)檔次。到了如今,發(fā)現(xiàn)返璞歸真從單純的WiFi信號(hào)之中提取出魯棒性的結(jié)構(gòu)才是能夠幫助室內(nèi)定位技術(shù)使用化的重要途徑。“我是誰”、“我在哪”永遠(yuǎn)是人們追求的兩大問題，希望室內(nèi)定位技術(shù)能夠幫助到更多的人——不要讓空間上的迷失帶來心靈上的迷失。

參考文獻(xiàn)：

[1]劉云浩.從互聯(lián)到新工業(yè)革命[M]. 北京:清華大學(xué)出版社, 2016:23-26.

[2]楊錚, 吳陳沭, 劉云浩.位置計(jì)算:無線網(wǎng)絡(luò)定位與可定位性[M]. 北京:清華大學(xué)出版社, 2014:7-9, 28-29.

[3]YOUSSEF M, AGRAWALA A. The Horus location determination system[J].Wireless Networks, 2008,14(3): 357-374.

[4]NI L M, LIU Y, LAU Y C, et al. LANDMARC:Indoor location sensing using active RFID[J].Wireless Networks,2004,10(6): 701-710.

[5]WANG J, KATABI D.Dude, where′s my card?: RFID positioning that works with multipath and non-line of sight [J]. ACM SIGCOMM Computer Communication Review,2013,43(4): 51-62.

[6]SHANGGUAN L, YANG Z, LIU A X, et al. STPP: Spatial-temporal phase profiling-based method for relative RFID tag localization[J]. IEEE/ACM Transactions on Networking (ToN), 2017, 25(1): 596-609.

[7]LIU K K, LIU X X, LI X L. Guoguo: Enabling fine-grained indoor localization via smartphone[C]∥Proceeding of the 11th Annual International Conference on Mobile Systems, Applications, and Services. ACM, 2013: 235-248.

[8]SHU Y, SHIN K G, HE T, et al. Last-mile navigation using smartphones[C]∥Proceedings of the 21st Annual International Conference on Mobile Computing and Networking. ACM, 2015: 512-524.

[9]YANG Z, WU C S, LIU Y H. Locating in fingerprint space:Wireless indoor localization with little human intervention[C]∥Proceedings of the 18th Annual International Conference on Mobile Computing and Networking. ACM, 2012: 269-280.

[10] WU C S, YANG Z, LIU Y H. Smartphones based crowdsourcing for indoor localization[J]. IEEE Transactions on Mobile Computing, 2015, 14(2): 444-457.

[11] YANG Z, WU C S, ZHOU Z M, et al. Mobility increases localizability: A survey on wireless indoor localization using inertial sensors[J]. ACM Computing Surveys (Csur), 2015, 47(3): 54.

[12] BAHL P, PADMANABHAN V N. RADAR: An in-building RF-based user location and tracking system[C]∥INFOCOM 2000. Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies. IEEE, 2000, 2:775-784.

[13] WU C S, XU J A, YANG Z, et al. Gain without pain: Accurate WiFi-based localization using fingerprint spatial gradient[J]. Proceedings of the ACM on Interactive, Mobile, Wearable and Ubiquitous Technologies, 2017,1(2):29.

[14] MIROWSKI P, WHITING P, STECK H, et al. Probability kernel regression for WiFi localisation[J]. Journal of Location Based Services，2012，6(2):81-100.

[15] WU C S, YANG Z, ZHOU Z M, et al. Mitigating large errors in WiFi-based indoor localization for smartphones[J]. IEEE Transactions on Vehicular Technology, 2017, 66(7): 6246-6257.

[16] SHEN G B, CHEN Z, ZHANG P C, et al. Walkie-Markie: Indoor pathway mapping made easy[C]∥Proceedings of the 10th USENIX Conference on Networked Systems Design and Implementation. USENIX Association, 2013: 85-98.

[17] SHU Y C, HUANG Y H, ZHANG J Q, et al. Gradient-based fingerprinting for indoor localization and tracking[J]. IEEE Transactions on Industrial Electronics, 2016, 63(4): 2424-2433.

[18] SHU Y C, BO C, SHEN G B, et al. Magicol: Indoor localization using pervasive magnetic field and opportunistic WiFi sensing[J]. IEEE Journal on Selected Areas in Communications, 2015, 33(7)：1443-1457.

[19] XIAO Z L, WEN H K, MARKHAM A, et al. Lightweight map matching for indoor localisation using conditional random fields[C]∥Proceedings of the 13th International Symposium on Information Processing in Sensor Networks. IEEE Press, 2014：131-142.

[20] MADGWICK S O H, HARRISON A J L, VAIDYANATHAN R. Estimation of IMU and MARG orientation using a gradient descent algorithm[C]∥Rehabilitation Robotics (ICORR), 2011 IEEE International Conference on. IEEE, 2011：1-7.

[21] LIU H B, GAN Y, YANG J, et al. Push the limit of WiFi based localization for smartphones[C]∥Proceedings of the 18th Annual International Conference on Mobile Computing and Networking. ACM, 2012: 305-316.

[22] XU H, YANG Z, ZHOU Z M, et al. Enhancing wifi-based localization with visual clues[C]∥Proceedings of the 2015 ACM International Joint Conference on Pervasive and Ubiquitous Computing. ACM，2015：963-974.