室内定位系列 ——WiFi位置指纹（译）
摘要
GPS難以解決室內(nèi)環(huán)境下的一些定位問題，大部分室內(nèi)環(huán)境下都存在WiFi，因此利用WiFi進(jìn)行定位無需額外部署硬件設(shè)備，是一個非常節(jié)省成本的方法。然而WiFi并不是專門為定位而設(shè)計的，傳統(tǒng)的基于時間和角度的定位方法并不適用于WiFi。近十年來，在室內(nèi)WiFi場景下的定位中，位置指紋法被廣泛研究和采用。本文對WiFi位置指紋法進(jìn)行綜述，提出了這個領(lǐng)域面臨的挑戰(zhàn)，介紹最新的研究，以及提供一些實際的指導(dǎo)。
介紹
室內(nèi)環(huán)境下的定位一直是一個很多問題未被解決的領(lǐng)域。由于信號的嚴(yán)重衰減和多徑效應(yīng)，通用的室外定位設(shè)施（比如GPS）并不能在建筑物內(nèi)有效地工作。定位準(zhǔn)確性也是一個問題，GPS也許可以指出移動設(shè)備在哪一個建筑物，但是室內(nèi)場景下，人們希望得到更精確的室內(nèi)位置，這需要更精密的地圖信息和更高的定位精度。
我們可以在室內(nèi)搭建一套完整的基礎(chǔ)設(shè)施用來定位，但是這樣需要很大的代價，包括定位信號占用的頻譜資源、用于感知定位信號的嵌入在移動設(shè)備中的額外硬件、安裝在固定位置的用來發(fā)送定位信號的錨節(jié)點。因此，大家傾向于使用那些已有的被廣泛部署的無線設(shè)備去實現(xiàn)室內(nèi)定位。
基于無線信號的定位方法首先考慮的是使用WiFi（基于IEEE802.11標(biāo)準(zhǔn)的WLAN）作為基礎(chǔ)定位設(shè)施。現(xiàn)在，包括智能手機(jī)、筆記本電腦在內(nèi)的大部分移動通信設(shè)備都內(nèi)嵌了WiFi模塊。實際上，WiFi已經(jīng)被廣泛地在室外定位與導(dǎo)航中使用（通過智能手機(jī)以及被維護(hù)的wifi熱點位置與其對應(yīng)的mac地址的數(shù)據(jù)庫進(jìn)行查找，很多公司有維護(hù)這樣的數(shù)據(jù)庫，包括Google、Apple、Microsoft，以及Skyhook這樣的定位服務(wù)提供商等等）。其他還有一些技術(shù)，比如用藍(lán)牙、RFID、移動電話基站信號等，也可以用來實現(xiàn)室內(nèi)定位，但是它們不像WiFi這樣到處都有，因此流行程度不如WiFi。移動電話信號并不能在所有的室內(nèi)場景下都能穩(wěn)定傳播，使用RFID需要額外的安裝硬件的花費，此外，基于超聲波的定位技術(shù)使用在一些實驗性的工作中，而實際利用超市波的商用設(shè)備很少，因此實際應(yīng)用并不多。
WiFi廣泛使用在家庭、旅館、咖啡館、機(jī)場、商場等各類大型或小型建筑物內(nèi)，這樣使得WiFi成為定位領(lǐng)域中一個最引人注目的無線技術(shù)。通常，一個WiFi系統(tǒng)由一些固定的接入點（AP）組成，它們部署在在室內(nèi)一些便于安裝的位置，系統(tǒng)或網(wǎng)絡(luò)管理員通常知道這些AP的位置。能連接WiFi的移動設(shè)備（比如筆記本電腦、移動電話）相互之間可以直接或間接地（通過AP）通信，因此可以考慮在通信功能外同時實現(xiàn)定位功能。但是WiFi信號并不是為定位而設(shè)計的，通常是單天線、帶寬小，室內(nèi)復(fù)雜的信號傳播環(huán)境使得傳統(tǒng)的基于到達(dá)時間/到達(dá)時間差（TOA/TDOA）的測距方法難以實現(xiàn)，基于到達(dá)信號角度的方法也同樣難以實現(xiàn)，如果在WiFi網(wǎng)絡(luò)中安裝能定向的天線又需要額外的花費。因此，近年來大家詳細(xì)研究的主要是位置指紋方法。
本文涉及的是在室內(nèi)環(huán)境下的定位，提供一些使用WiFi的接入點和移動設(shè)備進(jìn)行位置指紋法定位的指導(dǎo)。本文包括：WiFi位置指紋法的基本概念，WiFi如何用于定位，使用WiFi的位置指紋算法，存在的挑戰(zhàn)和性能方面的問題，以及WiFi位置指紋法中其他的一些事項。
位置指紋法的基本概念
“位置指紋”把實際環(huán)境中的位置和某種“指紋”聯(lián)系起來，一個位置對應(yīng)一個獨特的指紋。這個指紋可以是單維或多維的，比如待定位設(shè)備在接收或者發(fā)送信息，那么指紋可以是這個信息或信號的一個特征或多個特征（最常見的是信號強(qiáng)度）。如果待定位設(shè)備是在發(fā)送信號，由一些固定的接收設(shè)備感知待定位設(shè)備的信號或信息然后給它定位，這種方式常常叫做遠(yuǎn)程定位或者網(wǎng)絡(luò)定位。如果是待定位設(shè)備接收一些固定的發(fā)送設(shè)備的信號或信息，然后根據(jù)這些檢測到的特征來估計自身的位置，這種方式可稱為自身定位。待定位移動設(shè)備也許會把它檢測到的特征傳達(dá)給網(wǎng)絡(luò)中的服務(wù)器節(jié)點，服務(wù)器可以利用它所能獲得的所有信息來估計移動設(shè)備的位置（翻譯存疑...），這種方式可稱為混合定位。在所有的這些方式中，都需要把感知到的信號特征拿去匹配一個數(shù)據(jù)庫中的信號特征，這個過程可以看作一個模式識別的問題。
位置指紋由什么組成？
位置指紋可以是多種類型的，任何“位置獨特”的（對區(qū)分位置有幫助的）特征都能被用來做為一個位置指紋。比如某個位置上通信信號的多徑結(jié)構(gòu)、某個位置上是否能檢測到接入點或基站、某個位置上檢測到的來自基站信號的RSS（接收信號強(qiáng)度）、某個位置上通信時信號的往返時間或延遲，這些都能作為一個位置指紋，或者也可以將其組合起來作為位置指紋。下面我們介紹兩種最常用的信號特征（Bahl and Padmanabhan, 2000; Pahlavan and Krishnamurthy 2002）：多徑結(jié)構(gòu)、RSS。
多徑結(jié)構(gòu)
載頻比較大（比如大于500Mhz）的無線電信號的傳播可以近似看作是光學(xué)射線的傳播（Pahlavan and Krishnamurthy 2002）。無線電信號傳播時，這些“射線”可以在光滑的平面（比如建筑物的墻壁、地板）上進(jìn)行反射，遇到銳利的邊緣會發(fā)生衍射，遇到小型的物體（比如樹葉）會發(fā)生散射。發(fā)射源發(fā)出的無線電信號可以通過多條路徑傳播到同一位置，因此在一個位置上會接收到多條射線，每條射線有不同的能量強(qiáng)度和時延。時延取決于射線傳播的距離，強(qiáng)度取決于距離和具體的傳播情況（反射、衍射等）。每條到達(dá)接收器的射線稱為一個多徑分量，信道的多徑結(jié)構(gòu)指的是這一組（多條射線）信號強(qiáng)度和時延。多徑結(jié)構(gòu)也稱作功率時延分布，圖1是一個典型的功率時延分布的例子，其中，有6個有效的多徑分量，功率和時延分別為β1β1，β2β2，β3β3，β4β4，β5β5，β6β6和τ1τ1，τ2τ2，τ3τ3，τ4τ4，τ5τ5，τ6τ6。
圖1 功率時延分布
如果信號的帶寬足夠大（比如使用直接序列擴(kuò)頻技術(shù)或者超寬帶技術(shù)），那么在接收器上可以分解和處理各個多徑分量。某個位置上得到的多徑結(jié)構(gòu)取決于實際的環(huán)境，是獨特的，能夠被用來作為位置指紋。Ahonen and Eskelinen (2003）提出了這種方法定位3G UMTS網(wǎng)絡(luò)中的手機(jī)，他們的研究結(jié)果指出，使用這樣的多徑結(jié)構(gòu)作為位置指紋可以達(dá)到67%的情況下25m以內(nèi)的定位精度，以及95%的情況下188m的定位精度，這樣的定位性能滿足了FCC的關(guān)于手機(jī)定位的E-911要求。
接收信號強(qiáng)度（RSS）
信號的RSS或者接收功率取決于接收器的位置。RSS的獲取很簡單，因為它是大多數(shù)無線通信設(shè)備正常運行中所必需的。很多通信系統(tǒng)需要RSS信息用來感知鏈路的質(zhì)量，實現(xiàn)切換，適應(yīng)傳輸速率等功能。RSS不受信號帶寬的影響，沒必要高的帶寬（大多數(shù)通信方式的信號帶寬都比較窄），因此RSS是一個很受歡迎的信號特征，并廣泛應(yīng)用于定位中。
假設(shè)有一個固定的信號發(fā)射源，在離它不同距離的位置上的平均RSS的衰減（in db）和距離的對數(shù)成正比，在最簡單的情況下，RSS可以表示為：
RSS=Pt?K?10αlog10dRSS=Pt?K?10αlog10?d 其中， αα稱為路徑損耗指數(shù)， PtPt為發(fā)送功率， KK是一個取決于環(huán)境和頻率的常數(shù)。RSS可以被用來計算移動設(shè)備與AP（或基站）之間的距離，那么這個提取出來的距離是否可以用來做移動設(shè)備的三邊角測量從而定位呢，可以，但是定位誤差可能會很大，因為RSS的變動范圍可能會很大（注意上面的公式中RSS指的是某個距離的可能RSS的平均），這是由實際環(huán)境的影響造成的（稱為陰影衰落）。因此這種基于RSS測距的三邊角方法并不是一個好的解決方案。然而，如果一個移動設(shè)備能接收到來自多個發(fā)射源的信號，或者固定的多個基站都能感知到同一個移動設(shè)備，那么我們也許可以使用來自多個發(fā)射源或者多個接收器的RSS組成一個RSS向量，作為和位置相聯(lián)系的指紋。這個就是本文描述的典型的WiFi位置指紋。大多數(shù)WiFi的網(wǎng)卡可以測得來自多個AP的RSS（可能是依次測量）。現(xiàn)在在大多數(shù)室內(nèi)場景，移動設(shè)備常常可以檢測到多個AP，因此使用來自多個AP的RSS作為位置指紋是有意義的，后文以此方法為基礎(chǔ)。
注意到RSS本身就是在一段時間內(nèi)計算或測得的，因此只采集一個RSS樣本是不合理的。在WiFi網(wǎng)絡(luò)中，AP常常要發(fā)送一個beacon幀，包含了一些網(wǎng)絡(luò)信息、服務(wù)組ID（無線網(wǎng)絡(luò)的名字）、支持的傳輸速率，以及一些其它的系統(tǒng)信息。這個beacon幀是用在WiFi中的很多的控制幀之一，它大約100ms發(fā)送一次，RSS通常是使用這個beacon幀來測量的。beacon幀是未加密的，所以即使是一個封閉的網(wǎng)絡(luò)（移動設(shè)備未能連接上）也能用來定位。beacon幀接近于周期性地被發(fā)送，但并不是完全周期性的，當(dāng)檢測到傳輸媒介阻塞的時候需要延遲發(fā)送，一旦檢測到不阻塞的時候就發(fā)送，下一次發(fā)送還是會在之前預(yù)計的100ms時刻，即使離上一次發(fā)送還不足100ms。更進(jìn)一步，如果AP工作在多個信道上，為了避免沖突，在測量RSS之前，移動設(shè)備必須花時間掃描各個信道。WiFi標(biāo)準(zhǔn)（IEEE 802.11）指定了2.4GHz頻帶的11個信道以及更多的5GHz頻帶的信道。盡管在一個地理區(qū)域中使用多個信道的情況并不罕見，但實際WiFi僅僅使用2.4GHz頻帶中三個不重疊的信道。關(guān)于WiFi和IEEE 802.11標(biāo)準(zhǔn)的更多細(xì)節(jié)可以參閱（Perahia and Stacey 2008）。
由測量值和指紋庫估計位置
使用位置指紋進(jìn)行定位通常有兩個階段：離線階段和在線階段。在離線階段，為了采集各個位置上的指紋，構(gòu)建一個數(shù)據(jù)庫，需要在指定的區(qū)域進(jìn)行繁瑣的勘測，采集好的數(shù)據(jù)有時也稱為訓(xùn)練集。在在線階段，系統(tǒng)將估計待定位的移動設(shè)備的位置。接下來我們將對這兩個階段進(jìn)行更詳細(xì)的描述。需要注意的是，室內(nèi)定位中所得到的位置坐標(biāo)通常是指在當(dāng)前環(huán)境中的一個局部坐標(biāo)系中的坐標(biāo)，而不是經(jīng)緯度。
離線階段
位置和指紋的對應(yīng)關(guān)系的建立通常在離線階段進(jìn)行。最典型的場景如圖2.2所示，地理區(qū)域被一個矩形網(wǎng)格所覆蓋，這個場景中是4行8列的網(wǎng)格（共32個網(wǎng)格點），2個AP。這些AP本來是部署在這里用來通信的，也可以用來做定位。在每一個網(wǎng)格點上，通過一段時間的數(shù)據(jù)采樣（5到15分鐘，大約每秒采集一次）得到來自各個AP的平均RSS，采集的時候移動設(shè)備可能有不同的朝向和角度。這個例子中，一個網(wǎng)格點上的指紋是一個二維的向量ρ=[ρ1,ρ2]ρ=[ρ1,ρ2]，其中ρiρi是來自第ii個AP的平均RSS。在后面會看到，我們也可以記錄RSS樣本的分布（或者其他的一些統(tǒng)計參數(shù)，比如標(biāo)準(zhǔn)差）作為指紋。簡單起見，后文沒有特別說明的情況下都認(rèn)為指紋是RSS樣本的均值。
圖2 基于WiFi信號強(qiáng)度的位置指紋法，以及RSS空間中的歐氏距離
這些二維的指紋是在每個網(wǎng)格點所示的區(qū)域（如圖2）采集到的，這些網(wǎng)格點坐標(biāo)和對應(yīng)的指紋組成一個數(shù)據(jù)庫，這個過程有時稱為標(biāo)注階段（calibration phase），這個指紋數(shù)據(jù)庫有時也稱為無線電地圖（radio map）（譯者注：后面都簡稱為指紋庫），表1是這個指紋庫的一個局部。圖2右邊的部分在二維向量空間（后文都統(tǒng)一稱作信號空間）中展示了這些指紋。在更一般的場景下，假設(shè)有NN個AP，那么指紋ρρ是一個NN維的向量，這在信號空間中就難以畫出來了。
表1
盡管RSS樣本的坐標(biāo)點是實際物理空間中的直角網(wǎng)格點，但是位置指紋在信號空間中不會這樣有規(guī)律。我們之后會看到，呈直角網(wǎng)格的位置點轉(zhuǎn)換到信號空間中后變成了一些沒有規(guī)律的模式。有些信號向量即使在物理空間中離得很遠(yuǎn)，在信號空間中卻有可能很近，這會增加錯誤的幾率。因此，指紋采集的有些部分也許沒有什么用，甚至有時會對定位效果不利。
在線階段
在在線階段，一個移動設(shè)備處于這個地理區(qū)域之中，但是不知道它的具體位置，它甚至不太可能正好處于網(wǎng)格點上。假設(shè)這個移動設(shè)備測量到了來自各個AP的RSS（在圖2的例子中，僅僅能測量到兩個AP的RSS）。這里我們假設(shè)只測量到一個樣本，當(dāng)來自各個AP的RSS都被測量到的時候，RSS向量的測量值被傳輸?shù)骄W(wǎng)絡(luò)中。設(shè)圖2中的例子中RSS向量的為r=[r1,r2]r=[r1,r2]。要確定移動設(shè)備的位置，就是要找到在指紋庫中找到和rr最匹配的指紋ρρ。一旦找到了最佳的匹配，那么移動設(shè)備的位置就被估計為這個最佳匹配的指紋所對應(yīng)的位置。比如，如果r=[?65,?49]r=[?65,?49]，那么最匹配的樣本是表1中的第一項，移動設(shè)備被定位在坐標(biāo)(0,0)(0,0)。在更一般的情況下，向量rr是NN維的。
以上的討論對坐標(biāo)、指紋、測量值、匹配向量rr和ρρ做了很多的簡化。后文我們考慮一些更詳細(xì)的問題。首先從匹配rr和ρρ的算法開始。
基于位置指紋的定位算法
基于位置指紋的定位通常分為兩種類型。一種是確定性的算法，比較信號特征（比如向量rr）和存在指紋庫中的預(yù)先計算出來的統(tǒng)計值。另一種是是概率性的算法，計算信號特征屬于某個分布（存儲在指紋庫中）的可能性。下面介紹一些基本的方法，但并不進(jìn)行詳盡的綜述。
確定性的定位算法
微軟在2000年最早開始進(jìn)行WiFi位置指紋法定位的研究工作（Bahl and Padmanabhan 2000），他們使用RSS向量rr與指紋向量ρρ的歐氏距離去確定移動設(shè)備的位置。假設(shè)位置指紋是NN維的，也就是說有NN個可見的AP，M個網(wǎng)格點，這樣指紋庫里面有M個指紋。rr和ρρ的歐氏距離定義為：
D=∑i=1N|ri?ρi|2???????????D=∑i=1N|ri?ρi|2 這樣的話，最簡單的定位算法可以描述如下：在指紋庫中的M個指紋中，找到在信號空間中與RSS觀測值的歐氏距離最近的指紋，然后將它所對應(yīng)的位置坐標(biāo)作為移動設(shè)備的位置。這個使用歐氏距離的方法也叫做在信號空間中找到最近鄰，因為目標(biāo)是在信號空間中找到一個離RSS觀察值最近的指紋。圖2的右邊展示了這個方法的基本原理，其中，五角星代表RSS觀測值，圓代表信號空間中的位置指紋。決策邊界可以使用泰森多邊形的方法畫出來，信號空間中每個泰森多邊形包含的區(qū)域距離這個位置指紋最近。RSS觀測值所處的泰森多邊形區(qū)域中的位置指紋的位置，作為定位結(jié)果。后文我們將看到，不是所有的位置指紋都是可靠的，一個更復(fù)雜的指紋庫可能還包括了RSS的標(biāo)準(zhǔn)差信息，或者給了每個AP不同的權(quán)值，這樣的話，我們可能要使用加權(quán)的歐氏距離，有時可能要對整個指紋加一個權(quán)值，有時需要對指紋的每個元素分別加一個權(quán)值。此外，其他的距離度量（比如曼哈頓距離或者馬氏距離）也常常被用來做定位。
概率性的定位算法
最早的基于WiFi位置指紋的概率性定位算法是Youssef et al. (2003).提出的，基本的思路是，如果簡單地使用一個RSS樣本的統(tǒng)計量（比如RSS的均值）可能會帶來誤差，因為實際的RSS值應(yīng)該是一個分布。因此，我們可以使用聯(lián)合概率分布（有多個AP，所以是聯(lián)合概率分布）來作為指紋。通過采集RSS樣本獲取聯(lián)合概率分布并不是一個簡單的事情，因為來自各個AP的RSS之間的相互關(guān)系不明顯。他們假設(shè)這是獨立的（這種假設(shè)是合理的），然后簡單地使用RSS的邊緣分布的乘積作為聯(lián)合分布。假設(shè)觀測到的RSS向量為r=[r1,r2,r3,???,rN]r=[r1,r2,r3,???,rN]，估計位置時將選擇一個網(wǎng)格點，這個網(wǎng)格點上有最大的概率可能產(chǎn)生這個rr。對于給定的rr，可以使用貝葉斯準(zhǔn)則來估計移動設(shè)備的位置，某個網(wǎng)格點上能產(chǎn)生rr的概率可以這樣計算：
計算出所有的網(wǎng)格點這個概率，然后選擇最大概率的那個網(wǎng)格點作為移動設(shè)備的位置。
指紋的聚類
以上有一個問題沒有考慮到，并不是所有的網(wǎng)格點上都總能能檢測到同樣的一組AP。Youssef et al. (2003)最早對這個問題進(jìn)行的描述
，Swangmuang and Krishnamurthy (2008b)考慮了不同的一些聚類的方式。Youssef et al. (2003)的工作基于各個AP的平等性來給網(wǎng)格點分組。分享同一組AP的網(wǎng)格點被認(rèn)為是一個簇，簇的確定是基于各個網(wǎng)格點上能看到這些AP的概率，因此這個方法也叫做“聯(lián)合聚類”或者作者所稱的JC技術(shù)。Swangmuang and Krishnamurthy在信號空間中對指紋進(jìn)行聚類，可以減少指紋搜索的復(fù)雜度，因此，他假設(shè)所有的位置都能看到同樣的一組AP。
其他
其他很多模式匹配算法都可以應(yīng)用于WiFi位置指紋法。包括貝葉斯推理、統(tǒng)計學(xué)習(xí)理論、支持向量機(jī)、神經(jīng)網(wǎng)絡(luò)等。(參考文獻(xiàn)很多，比如Battiti et al. 2002).
位置指紋法的性能
這一部分，我們考慮位置指紋法的定位性能（精度和準(zhǔn)確度），分析指紋數(shù)據(jù)采集的工作量以及如何去減少工作量。我們首先分析為什么使用位置指紋法定位會存在誤差，然后描述一些論文中報告的誤差性能分析的結(jié)果。
造成誤差的原因
在最理想的情況，觀測RSS應(yīng)該和它匹配到的指紋非常接近，同時這個指紋所對應(yīng)的位置和移動設(shè)備的實際位置非常接近。但實際情況往往不是如此，有幾個原因會造成顯著的誤差。
無線電傳播的復(fù)雜性
無線電的傳播很容易受到環(huán)境影響，特別是在室內(nèi)區(qū)域或者城市的高樓之間。圖3顯示了連續(xù)測得的一組RSS樣本，這個例子使用的是一個筆記本電腦，當(dāng)用戶正常坐著工作的時候它測得某個AP的RSS，持續(xù)幾分鐘。很顯然，RSS隨時間變化，而且有時變化得很顯著。不過在五分鐘內(nèi)RSS的變化基本不會超過20dB。人的朝向?qū)σ苿釉O(shè)備測量到的RSS有顯著的影響。來自不同供應(yīng)商的網(wǎng)卡計算RSS的方式也有些不同，這個也會造成RSS測量上的不一致。RSS的分布可能是不平穩(wěn)的，因此，當(dāng)測量到觀測向量rr時，它有可能會匹配到離真實位置較遠(yuǎn)的位置指紋，這一點超過了本文要描述的RSS特性的范圍。感興趣的讀者可以參考Kaemarungsi and Krishnamurthy (2004b, 2011)，其中針對室內(nèi)定位詳細(xì)地分析了WiFi的RSS的特性。
圖3：筆記本電腦測得的RSS（dBm）序列
刪失數(shù)據(jù)（Censored Data）
之前提到過，并不是在所有的位置都總能檢測到所有的AP。比如，在采集數(shù)據(jù)的時候，在一個網(wǎng)格點上只有三個AP是可見的，但是在在線定位階段移動設(shè)備檢測到了4個或5個AP。在這種情況下，增加指紋的維度是有益的，因為可以使得網(wǎng)格點在信號空間中互相區(qū)分開。然而有些信號的不可靠會使得定位算法這樣難以準(zhǔn)確定位。當(dāng)然，指紋庫也可以有AP的一些其他信息（比如每個AP的Mac地址），但是刪失數(shù)據(jù)的處理并不簡單。Youssef et al. (2003）嘗試每次都只使用kk個AP，忽略掉其他可見的AP。這kk個AP通過信號的可靠性來選擇。這樣，如果一旦選擇了不合適的kk個AP，定位誤差可能會很大。
誤差分析
首先，我們總結(jié)一些文獻(xiàn)中報導(dǎo)的誤差性能分析的結(jié)果。大多數(shù)結(jié)論通過仿真或?qū)嶒瀬泶_定。在Bahl and Padmanabhan的開創(chuàng)性工作中，AP個數(shù)為3，使用的是確定性的定位算法（最近鄰），他們的中值誤差在3m到6m之間，具體誤差取決于使用的網(wǎng)格點的個數(shù)。Swangmuang and Krishnamurthy (2008a)使用了一個類似的確定性的定位算法，采用誤差的累計分布函數(shù)來展示定位誤差的可能性，在辦公室區(qū)域內(nèi)，25個網(wǎng)格點，3個可見的AP，90%的可能性定位誤差小于4m。Youssef et al. (2003),采用了一個聯(lián)合聚類的概率性的定位方法，實驗場景的尺寸大約為68m*26m，構(gòu)建指紋庫共使用了110個網(wǎng)格點，大多數(shù)指紋是隨著走廊采集的，cdf曲線顯示90%的概率誤差小于2.1m。
接下來討論的問題中，對于位置指紋定位誤差的分析考慮很少。最早分析位置指紋法的定位性能的是Kaemarungsi and Krishnamurthy (2004a)，他們假設(shè)RSS樣本服從正態(tài)分布，樣本的均值就是正態(tài)分布的均值，不同AP的RSS的正態(tài)分布的方差是一樣的。這種假設(shè)使得性能分析變得簡單。實際中，RSS的分布不是高斯分布（(Kaemarungsi and Krishnamurthy 2004b, 2011).）。圖4顯示了兩個RSS的直方圖，一個距離AP比較近，一個距離AP比較遠(yuǎn)。第一個分布是左偏的，第二個分布更加對稱，可以近似建模成一個高斯分布。RSS分布的方差也并不是一樣的。Kaemarungsi and Krishnamurthy 2011的工作表明：距離AP越遠(yuǎn)，方差越大。因此，上面那個簡單的假設(shè)在現(xiàn)實中不一定有效。Kaemarungsi and Krishnamurthy 2004a的工作對（Swangmuang and Krishnamurthy 2008a）做了進(jìn)一步的延伸，其中的分析結(jié)果和仿真實驗的誤差cdf是匹配的，特別是當(dāng)定位誤差為幾米的時候。因此，即使這些假設(shè)做了一些簡化，分析結(jié)果也可能是有用的。這些分析可以用來評估增加位置指紋的維度帶來的邊邊際效益，以及簡單場景下（(Kaemarungsi and Krishnamurthy 2004a).）路徑損耗指數(shù)的影響。
圖4：RSS樣本的直方圖
假設(shè)RSS服從高斯分布，那么這個誤差分析和數(shù)字通信系統(tǒng)中計算比特誤碼率的誤差分析很相似。RSS的方差越大會導(dǎo)致誤差的概率越大。然而不同的是，信號空間中的RSS指紋沒有明顯的規(guī)律，RSS分布的方差在不同的維度上可能區(qū)別很大，所以很難解析地求出定位誤差的封閉解。如果如圖5中，僅僅考慮兩個維度，有可能導(dǎo)出誤差的概率表達(dá)式（使用圖中的決策邊界來比較距離觀察RSS最近的指紋與正確的指紋）。但是當(dāng)有了更多的指紋點的時候，創(chuàng)建出越來越多的不規(guī)則的泰森多邊形，如果不做近似，根本處理不了。Swangmuang and Krishnamurthy (2008a)的研究中，就使用臨近圖來近似正確的分析結(jié)果。
圖5 在兩個AP的情況下信號空間中的RSS分布
位置指紋的采集工作
盡管和那些需要額外設(shè)備的定位系統(tǒng)相比，WiFi位置指紋法的成本較低， 但是它也有需要付出的代價。大多數(shù)研究都假設(shè)位置指紋在虛擬的網(wǎng)格點上采集數(shù)據(jù)得到。比如，在一個100m*100m的區(qū)域，劃分成50*50個網(wǎng)格（每個網(wǎng)格2m*2m），每個網(wǎng)格中間采集一組指紋，每組指紋記錄的是這個網(wǎng)格點上接收到的包括了來自各個AP的RSS，5到15分鐘，有時可能還要使用不同的測量設(shè)備（手機(jī)或者筆記本電腦）或者設(shè)定幾個不同的設(shè)備方向。這樣的采集工作及其繁瑣，而且為了適應(yīng)環(huán)境的變化需要周期性地更新。在上面這個例子中，使用單個設(shè)備和固定的方向，整個采集過程需要2500*5=125000分鐘，接近9天。當(dāng)然我們也可以并行地采集不同位置上的指紋，但是仍這然需要耗費很大的人力，下文我們將研究一些在減少離線階段數(shù)據(jù)采集量方面的方法和嘗試。
減少指紋采集的數(shù)量
如果所有采集到的數(shù)據(jù)有用，都能改善系統(tǒng)的性能，那么這樣的時間和人力上的投資是有必要的。但實際常常很多數(shù)據(jù)并沒有那么有用，Youssef et al. (2003)和Swangmuang and Krishnamurthy (2008b) 的工作證明了的確沒有必要如此。一個“好”的指紋不應(yīng)該帶來定位上的錯誤，或者至少是”多半不會帶來錯誤“。從RSS指紋的角度來看，RSS的方差應(yīng)該盡量小，在信號空間中沒有其他的位置指紋距離它非常近。然而，有些指紋的實際位置并不接近，而在信號空間中的歐氏距離卻比較小，這樣的指紋采集過來也許不會改善性能，反而會造成定位的時候額外的計算量。把這樣的指紋放入指紋庫中甚至?xí)档投ㄎ痪取?/p>
考慮一個簡單的例子，如圖6，一個50m*50m的正方形區(qū)域，數(shù)據(jù)采集的參考點如圖中所畫出的。我們使用路徑損耗模型IEEE 802.11n “D” ，發(fā)射功率為10dBm，兩個AP的位置分別為（0， 0， 10）和（50， 50， 10）。(Perahia and Stacey 2008)給出的路徑損耗模型的公式為：
Lp=20log10(f)?127.5+35log10(ddbk),d>dbkLp=20log10?(f)?127.5+35log10?(ddbk),d>dbk 其中， ff是頻率， dbkdbk為斷點距離，10m。網(wǎng)格點如圖6中所示的規(guī)律性地分布，這些網(wǎng)格點上的指紋在信號空間中的分布如圖7（在不同的網(wǎng)格大小的情況下）。顯然，每1m或2m采集指紋并沒有太大的意義，因為在信號空間中很多已經(jīng)很接近了。當(dāng)移動設(shè)備觀測到 rr時，系統(tǒng)也許會把它匹配到最接近的指紋的時候犯錯誤，特別是當(dāng)RSS方差比較大的時候。因此，網(wǎng)格大小設(shè)為4m或者8m都是合乎情理的，即使網(wǎng)格很小，準(zhǔn)確度也不會改變很多。
圖6 數(shù)據(jù)采集工作量的簡單考慮，有用的位置指紋
圖7 網(wǎng)格劃分的區(qū)域中各個指紋在信號空間中的表示
在Swangmuang and Krishnamurthy (2008a)的工作中，他們假設(shè)RSS高斯分布，使用位置指紋被判定為距離測量RSS最近的概率來消除指紋庫中一些“壞”的指紋。結(jié)果顯示高達(dá)20%的指紋可以被去掉，同時并不影響定位精度。雖然這個過程中，“壞指紋”在采集數(shù)據(jù)建立完指紋庫后才被去除，但是作者也提出了一些減少部署工作量的定性的指導(dǎo)。
子區(qū)域定位
其他的一些減少離線采集工作量的方法中，有一種是在線測量APs之間的RSS，而不是像傳統(tǒng)那樣繁瑣地去標(biāo)記指紋（比如Gwon and Jain 2004)。（Aksu and Krishnamurthy (2010)）中的工作僅僅使用AP能不能檢測到移動設(shè)備這一信息，而不是使用細(xì)粒的位置指紋，也就是說，不用再記錄某個位置上RSS的平均值，而是僅僅記錄1或0來代表各個AP是不是能檢測到。比如，假設(shè)有4個AP，放置在正方形區(qū)域的四個角落，如果說我們能繪制出這些AP分別的的覆蓋范圍，那么有13個獨特的子區(qū)域，這些子區(qū)域分別被這些AP的一個子集所覆蓋。這樣的話，使用這些信息我們就能根據(jù)”是否檢測到“來判斷移動設(shè)備在哪個子區(qū)域。這些AP的位置以及覆蓋范圍決定了各個子區(qū)域的大小，直接影響定位的精度和準(zhǔn)確性。注意，在這個例子中有16個獨特的指紋，從[0,0,0,0][0,0,0,0]到[1,1,1,1][1,1,1,1]，但是并不是所有的組合都存在，這使得最大的獨特指紋的個數(shù)為13。這個個數(shù)也許會更小，比如，如果這4個AP都能覆蓋整個方形區(qū)域，那么就只有一個指紋[1,1,1,1][1,1,1,1]，這樣的定位結(jié)果只能告訴我們移動設(shè)備在這個方向區(qū)域中。
指紋庫的有機(jī)構(gòu)建
最近，有人開始提出采用基于用戶的RSS采集，來減少采集位置指紋的工作量。比如Park et al. 2010）的工作中，用戶被提示去提供指紋，但是這種增量式地構(gòu)建指紋庫也存在很多挑戰(zhàn)。Park et al. (2010)使用聚類和Voronoi圖來有組織地發(fā)展這個指紋庫。他們把空間（比如一個房間）劃分成一些Voronoi圖，促進(jìn)有組織的指紋庫的構(gòu)建。
其他的一些問題
這部分我們簡單地考慮一些之前沒有談到的和WiFi位置指紋法相關(guān)的其他問題，包括減少能力消耗、吞吐量問題、延遲和安全。
多種技術(shù)的使用
隨著移動設(shè)備（特別是智能手機(jī)）越來越多地被安裝多種無線技術(shù)（比如，有些設(shè)備同時有藍(lán)牙、RFID、近場通信），使用多種技術(shù)來定位是合理和可行的。有一些文章考慮同時使用GSM和室內(nèi)的WiFi，但在使用多種技術(shù)融合位置指紋定位中還沒有全面的研究。
減少能量損耗
通過有效的通信協(xié)議來減少移動設(shè)備通信的能耗是這幾年的一個研究領(lǐng)域（Pahlavan and Krishnamurthy 2002）。因為GPS在手機(jī)上消耗了很多的能量，最近有一些工作試圖讓定位過程更加節(jié)能。Paek et al. (2010)提出了智能手機(jī)的GPS速率自適應(yīng)的定位，這里的想法是通過減少GPS的忙閑度，這樣降低了定位準(zhǔn)確性，但是能夠節(jié)省能耗。但是GPS并不能在各種地方都能定位準(zhǔn)確（比如，在城市區(qū)域定位精度會降低），在室內(nèi)可能根本不可用。系統(tǒng)通過檢測是否室內(nèi)或城區(qū)，可以關(guān)掉GPS或者降低忙閑度來延長手機(jī)中電池的壽命。Lin et al. (2010)建議使用低能量的定位模式（比如使用WiFi而不是GPS）來減少能耗，但是同樣也可能會帶來準(zhǔn)確度的降低。
吞吐量
當(dāng)WiFi被用來定位的時候，移動設(shè)備要花費很多時間來掃描WiFi信號，這會暫時中斷數(shù)據(jù)的傳輸，從而影響吞吐量。King and Kjaergaard (2008）研究發(fā)現(xiàn)，在用戶沒有移動的時候減少掃描WiFi的周期，使得吞吐量增加到了122%，丟包率為原來的73%。將掃描速度與用戶是否移動聯(lián)系起來，當(dāng)檢測到用戶移動的時候，讓掃描速度增加，否則設(shè)備就不掃描，因為我們假設(shè)沒有檢測到移動的時候用戶的位置不會改變。
延遲
當(dāng)有很多的定位請求的時候，WiFi定位系統(tǒng)的容量和延遲也是一個需要考慮的問題，但目前這個方面似乎還沒有相關(guān)的研究工作。time-to-first-fix（首次定位時間）這樣的度量在WiFi指紋定位中不存在（GPS定位中，首次定位時間比較長）。當(dāng)請求的數(shù)量較小的時候，WiFi中粗粒度的位置估計速度比GPS快很多，GPS通常需要幾秒有時甚至需要幾分鐘得到一個位置。
安全性
大量的設(shè)備都支持WiFi，而且WiFi信號的監(jiān)控非常簡單，如果為了惡意目的而創(chuàng)建監(jiān)控這些設(shè)備的網(wǎng)絡(luò)，則可以基于它們的MAC地址和RSS值來跟蹤大量設(shè)備，這將導(dǎo)致嚴(yán)重的用戶隱私問題。Husted and Myers (2010)的工作中就嘗試了創(chuàng)建一個“惡意網(wǎng)絡(luò)”來跟蹤移動設(shè)備。
總結(jié)
本文提供了位置指紋法的概述，描述了這一領(lǐng)域的一些重要研究工作。考慮了用于定位的位置指紋的基本概念、使用位置指紋進(jìn)行定位的算法、定位性能分析，以及一些其他的方面。隨著室內(nèi)導(dǎo)航和室內(nèi)的其他應(yīng)用越來越收到重視，WiFi位置指紋法將可能成為這些室內(nèi)應(yīng)用的基石。
WiFi幾乎無處不在的可用性使其稱為一個很有吸引力的定位方法（無需額外的硬件花費），基于時間和角度的定位方法不適用于WiFi信號，使得位置指紋法成為定位主要的選擇。然而位置指紋法需要很繁瑣的數(shù)據(jù)采集工作，并且可能需要隨著環(huán)境的變化而經(jīng)常更新。此外，由于無線電傳播的復(fù)雜多變，位置指紋的收集本身也不是容易的問題。一些測量、分析和仿真已經(jīng)表明可以采取一些經(jīng)驗的方法來減少指紋采集的工作量。如果對定位精度的要求不高，諸如子區(qū)域定位或位置指紋的有機(jī)構(gòu)建等其他方法可以用來減少指紋采集的工作量。
盡管僅使用WiFi的位置指紋法已經(jīng)被證明是室內(nèi)精確定位的可行方案，但是隨著新技術(shù)的出現(xiàn)和具有附近感測能力的智能手機(jī)的普及，最終的解決方案可能是使用多種定位技術(shù)進(jìn)行融合的方案。在接下來的幾年中，可能可以使用近場通信、智能手機(jī)中的加速度計、以及可能的來自藍(lán)牙信號，作為附加參數(shù)來改善定位精度，同時保持合理的成本。
參考文獻(xiàn)
Ahonen, S., and P. Eskelinen. 2003. Mobile terminal location for UMTS. IEEE Aerospace and Electronic Systems Magazine, vol.18, no. 2, pp. 23–27.
Aksu, A., and P. Krishnamurthy. 2010. Sub-area localization: A simple calibration free approach. ACM MSWiM’10.
Bahl, P., and V. N. Padmanabhan. 2000. Radar: An in-building RF based user location and tracking system. IEEE INFOCOM 2000, pp. 775–784.
Battiti, R., M. Brunato, and A. Villani. 2002. Statistical learning theory for location fingerprinting in wireless LANs. Technical Report (October 2002).?http://rtm.science.unitn.it/?~battiti/archive/86.pdf.
Gwon, Y., and R. Jain. 2004. Error characteristics and calibration-free techniques for wireless LAN-based location estimation. Proceedings of the Second International Workshop on Mobility Management & Wireless Access Protocols, October 1, Philadelphia, Pennsylvania.
Husted, N., and S. Myers. 2010. Mobile location tracking in metro areas: Malnets and others. ACM CCS.
Kaemarungsi, K. and P. Krishnamurthy. 2004a. Modeling of indoor positioning systems based on location fingerprinting. IEEE INFOCOM, Hong Kong, China.
Kaemarungsi, K., and P. Krishnamurthy. 2004b. Properties of indoor received signal strength for WLAN location fingerprinting. IEEE/ACM Mobiquitous.
Kaemarungsi, K., and P. Krishnamurthy. 2011. Analysis of WLAN’s received signal strength indication for indoor location fingerprinting. Pervasive and Mobile Computing, DOI: 10.10.16/j.pmcj.2011.09.003.
King, T., and M. B. Kjaergaard. 2008. Composcan: Adaptive scanning for efficient concurrent communications and positioning with 802.11. ACM Mobisys.
Lin, K., A. Kansal, D. Lymberopolous, and F. Zhao. 2010. Energy-accuracy aware localization for mobile devices. ACM Mobisys.
Paek, J., J. Kim, and R. Govindan. 2010. Energy-efficient rate-adaptive GPS-based positioning for smartphones. ACM Mobisys.
Pahlavan, K., and P. Krishnamurthy. 2002. Principles of Wireless Networks: A Unified Approach. Prentice Hall PTR.
Park, J.-G., B. Charrow, D. Curtis, et al. 2010. Growing an organic indoor location system. ACM Mobisys.
Perahia, E., and R. Stacey. 2008. Next Generation Wireless LANs. Cambridge University Press.
Swangmuang, N., and P. Krishnamurthy. 2008a. Location fingerprint analyses toward efficient indoor positioning. PerCom’08, IEEE, pp. 100–109.
Swangmuang, N., and P. Krishnamurthy. 2008b. On clustering RSS fingerprints for improving scalability of performance prediction of indoor positioning systems. ACM MELT.
Youssef, M. A., A. Agrawala, and A. U. Shankar. 2003. WLAN location determination via clustering and probability distributions. Proceedings of IEEE International Conference on Pervasive Computing and Communications (PerCom ’03), Dallas-Fort Worth, Texas, pp. 23–26.
總結(jié)
以上是生活随笔為你收集整理的室内定位系列 ——WiFi位置指纹（译）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 位置指纹法的实现（KNN）
- 下一篇： CNN理解比较好的文章