本文作者：海之航。更多內容請關注：Map_technology。
近來作者有機會參加了不少LBS相關的會議和沙龍，很多開發(fā)者通過微信、郵件等形式表示對室內定位所用到的技術方法很感興趣。由于工作緊張，不能一一回復大家的問題，正好借助“百度地圖技術團隊”微信公眾號宣傳普及的機會，給大家做一個系統(tǒng)性介紹，希望對大家了解和應用室內定位技術有所幫助。(文中如有不當詞語或者觀點言論，敬請諒解并聯(lián)系作者以便更正。)
引言
地圖軟件已經成為我們日常出行必不可少的工具之一，在導航和搜索上帶來了很多便捷的幫助。而定位技術在地圖軟件里的應用可謂無法替代，尤其是在小范圍的室內定位環(huán)境下，如何幫助用戶高精度搜索導航，是百度地圖定位技術的研究重點。
我們一提到定位，大家印象中最熟悉的技術可能就是GPS定位。其實更為準確的說法是GNSS(Global Navigation Satellite System)定位，中文含義就是全球衛(wèi)星定位系統(tǒng)，而 GPS只是GNSS中的一種實現(xiàn)方法，該系統(tǒng)是由美國部署的。另外，還有其他類型的定位系統(tǒng)，例如，俄羅斯的格洛納斯(GLONASS)，歐洲的伽利略和中國的北斗。大家可能會有疑問，既然這么多國家投入巨資建設全球定位系統(tǒng)，是不是就可以直接覆蓋到室內定位呢?
答案是否定的。簡單介紹一下原因：衛(wèi)星定位使用的電磁波，屬于L波段，這種信號穿透建筑物或其他阻擋物時，信號強度會被削弱，尤其是在室內環(huán)境中，信號在通過屋頂、墻壁、窗戶等障礙物時，會由于折射和能量吸收而損耗掉部分能量。最壞的情況下，信號直接被完全阻塞，也就是GPS檢測不到任何衛(wèi)星。在一些半開放區(qū)域，有一些能夠勉強透射過來的信號，但由于其損耗過大，信號所攜帶的偽距和載波精度沒有參考意義，它們被GPS接收機接收，精度就會極差。因此，GPS很難覆蓋到室內區(qū)域,要做到室內高精度定位，就必須借助其他”高科技”手段，例如：基于LED定位、基于紅外線定位、基于超寬帶定位、基于藍牙/Wi-Fi定位、基于超聲波定位等。
幾何定位算法
在介紹那些“高科技”的定位設備和手段之前，為了便于大家理解，首先給大家介紹一下相對來說比較“簡單”易懂的定位方法-幾何求解定位法，目前這種方法已經被廣泛用于那些“高科技”定位設備中，所不同的只是他們所依賴的設備和“信號波”不同而已。
幾何求解定位法，就是通過空間中各個線段測量，利用空間幾何關系及公理，求解定位點在空間中的位置。在具體的定位系統(tǒng)中，我們通過測量設備得到準確的觀察量：例如，信號到達時間(TOA)、信號到達時間差(TDOA)、信號到達角度(AOA)、接收信號強度(RSSI)等，然后通過演算得到線段長度或者角度測量，進而利用空間幾何知識求解定位。
下面，我們展開介紹這幾種定位求解方法。
基于TOA定位方法
TOA也被稱為圓周定位技術，實際定位過程中通過設備發(fā)射電磁波測量得到當前定位點到三個標定點的時間：t1、t2、t3。根據(jù)電磁波的傳播速度是光速的知識，很容易得到三邊距離r1,r2,r3。利用平面幾何的兩點距離公式，我們構建方程組，求解出定位位置。
TOA算法示意圖
仔細看一下上圖，大家都會發(fā)現(xiàn)，定位過程中需要對兩個時間點進行測量，就是開始時間t0和到達時間t1，t2，t3，這四個時間變量直接影響測量距離。由此可見，TOA算法對系統(tǒng)的時間同步要求很高，因為即使有很小的時間誤差，但是乘以光速，誤差就會被放大很多倍。因此，如何保持各設備間的時鐘高精度同步問題，是很多專業(yè)定位設備包括GPS系統(tǒng)中需要解決的重要問題。
基于TDOA定位方法
TDOA也被稱為雙曲線定位技術，其所依賴的幾何知識是，如果測定待定位點到周圍兩個標定點的傳播距離差，則待定位點肯定在以這兩個標定點為焦點，點到兩個焦點的距離差值為傳播距離差的雙曲線上。
TDOA算法示意圖
如上圖，ri1為距離差值，通過對其計算公式化簡，很容易將公式中t0消除，避免了對t0的測量誤差引入，這樣定位系統(tǒng)只要保證同時發(fā)送測量信號，然后精確測量到達時間差即可，減少了時間測量誤差影響。TDOA技術常用的算法有Fang算法、Chan算法、Taylor級數(shù)展開算法。若大家對這些算法感興趣，可以通過維基百科進一步了解。
基于AOA定位方法
TOA也被稱為方位角定位技術。根據(jù)平面幾何知識，兩條射線平行或相交于一點，通過設備測量待定位點到兩個標定點間的入射角，很容易確定待定位點的位置。
AOA算法示意圖
如上圖，通過變化公式，很容易消除變量r，直接求解二元一次方程，很容易得到待定位點位置。
相比TOA、TDOA等，AOA機制不需要時間同步，實現(xiàn)同維度的定位任務所需要的參考節(jié)點數(shù)量最少，例如二維平面定位只需要兩個基站。但該方法必須有方向性較強的天線陣列支持。
基于RSSI定位方法
RSSI為信號強度，基于信號強度進行定位。根據(jù)物理知識，我們能夠知道一些信號在自由空間傳播遵循固定的衰減模型，通過該模型我們能夠給出信號強度與距離遠近的準確關系。如下圖。
其中，pd為待定位點接收到的信號強度。p0為距離輻射源d0處的信號強度。n 為信號衰減系數(shù)。
如上圖，是按照信號衰減模型繪制出來的曲線，我們可以看出隨著距離的增加，信號強度逐漸變弱，且這種變化程度逐漸變緩。
定位過程中，通過設備測量三個不同參考點的信號強度，依據(jù)模型計算出三個距離值，那么采用和TOA類似的幾何求解方法，即可以得到定位點。一般的射頻芯片都具有RSSI測量功能，故RSSI機制實施簡便，但易受信道和噪聲影響，在遠距離定位時測量誤差較大，多用于小范圍定位。
基于專業(yè)設備的定位系統(tǒng)
通過上節(jié)給大家介紹一些簡單易懂的幾何定位算法，大家可以隱約體會到，通過那些幾何知識，我們可以利用很多物理信號來實現(xiàn)高精度定位。事實上，無論是研究機構，還是工業(yè)界，都已經對很多信號、設備做過研究實驗。接下來，我給大家做一個匯總，按照信號的物理屬性，可以大致分為兩類：電磁波、超聲波。
電磁波，概念非常寬泛，包含很多種類，按照頻率從低到高的順序排列為：無線電波->紅外線(不可見)->可見光(赤橙黃綠青藍紫)->紫外線(不可見)，其頻率范圍大致在3Hz到3000GHz之間。常見的定位方法有：超寬帶定位、Wi-Fi定位、藍牙定位、ZigBee定位，紅外線定位，LED定位等。
超聲波是一種機械波，區(qū)別與電磁波，它依賴于物體機械振動進行能量傳輸?shù)?，其振動頻率大于20000Hz，超出了人耳聽覺的上限故被稱為超聲波，遵循反射、折射、衍射、散射等傳播規(guī)律，與可見聲波的規(guī)律沒有本質上的區(qū)別。常見定位方法有：超聲波定位。
下面從精確度、成本、是否需要專業(yè)設備、技術優(yōu)勢和技術缺陷等，穿透性，抗干擾性，布局復雜程度，成本5個方面全方位來比較一下這幾種室內定位手段。
下面我們簡單對上述表中各種方法進行補充說明和介紹。
超寬帶定位，是一種基于極窄脈沖無載波的無線技術，傳輸速率高，發(fā)射功率較低，穿透能力較強，用來做室內定位能夠獲取極為準確的結果。利用超寬帶定位需要事先布置好的已知位置的錨節(jié)點和橋節(jié)點。定位過程中，已有節(jié)點與新加入的盲節(jié)點進行通訊，利用TDOA技術來測距定位。該方案總體上看，功耗較高，部署成本比較高，精度較高。
藍牙定位，無線電波的一種，定位系統(tǒng)需要在室內安裝的若干個藍牙設備。定位時，通過手機等設備測量當前位置點掃描到各個藍牙的信號強度，由信號衰減模型換算成距離，然后利用三邊測量等方法推算定位坐標?？傮w來看，該方案實施成本中等偏高，低功耗，對復雜空間環(huán)境，穩(wěn)定性稍差，受噪聲信號干擾大。
Wi-Fi定位，無線電波的一種，此類定位系統(tǒng)也需要在室內安裝的若干個wifi設備。定位時，利用手機等設備對至少3個以上的無線網絡接入點的信號強度測量，通過三角定位、指紋等方法進行位置定位。Wi-Fi定位可以在廣泛的應用領域內實現(xiàn)復雜的大范圍定位、檢測和追蹤任務，總精度比較高，但用于室內定位的精度只能達到2~6米。
Zigbee，無線電波的一種，是一種新興的高可靠、短距離、低速率無線網絡技術，類似于CDMA和GSM網絡，數(shù)據(jù)以接力的方式通過一個節(jié)點傳到另一個節(jié)點。此類定位系統(tǒng)主要包括兩類節(jié)點，一類是錨節(jié)點，一般通過GPS定位或者人工部署的方式知道自身的精確位置。另一類是跟蹤節(jié)點，跟蹤節(jié)點通過準確測量其到數(shù)個錨節(jié)點的距離或方位，然后使用三邊測量等方法來計算節(jié)點位置。該類信號傳輸受多徑效應和移動的影響很大，定位精度取決于信道物理品質、信號源密度、環(huán)境和算法的準確性，因此造成定位軟件的成本較高，提高空間還很大。
紅外線，一種不可見光。利用其進行室內定位有兩種，第一種是被定位目標使用紅外線IR標識作為移動點，發(fā)射調制的紅外射線，通過安裝在室內的光學傳感器接收進行定位;第二種是通過多對發(fā)射器和接收器交織的紅外線網來覆蓋待測空間，直接對運動目標進行定位。紅外線的技術已經非常成熟，用于室內定位精度相對較高，但是紅外線只能視距傳播，穿透性極差，當標識被遮擋時就無法正常工作，也極易受燈光、煙霧等環(huán)境因素影響。另該類系統(tǒng)部署比較復雜，成本較高。
Li-Fi屬于可見光通訊，將需要傳輸?shù)男畔⒕幾g成一段調制信號，用脈寬調制的方法附加到LED燈具的驅動電流上，利用室內無處不在的光源作為發(fā)射再提，當用戶進入燈具照明區(qū)域，利用智能手機的前置攝像頭接收并識別光信號，解析出燈具發(fā)送的唯一身份識別信息。利用所獲取的身份識別信息在地圖數(shù)據(jù)庫中確定對應的位置信息，完成定位。
超聲波定位，一種基于機械波的定位方法，定位系統(tǒng)中包含主測距器、若干個電子標簽等。各個電子標簽需要固定設置在室內空間，定位時，上位機發(fā)送相同頻率的信號給各個電子標簽，待電子標簽接收到后將信號反射傳輸給主測距器，主測距器根據(jù)幾何關系計算得到定位坐標。該方法可以實現(xiàn)厘米級別定位，結構相對簡單。另外，超聲波會收到傳播損耗衰減影響、加上反射測距時受多經效應和非視距傳播影響很大，造成需要精確分析計算的底層硬件設施投資，成本非常高。
Wi-Fi的另一用途——室內定位
ok，終于講到本片文章的核心部分。雖說可以通過那些”高科技”設備做到高精度的定位，要給全國所有商場部署特殊硬件，其成本之大是難以接受的。從定位使用者角度來看，大家不可能隨時隨地攜帶那些各種標簽、發(fā)射器、設備，那么百度是如何切入做室內定位呢?
答案就是Wi-Fi。近年來，中國公眾對WiFi網絡建設與發(fā)展的關注和熱情可以用如火如荼來形容，全國大部分商場、公共交通樞紐等場所都已經密集部署了Wi-Fi設備，有了這些Wi-Fi設備，我們就可以構建室內高精度定位。
那么基于商場中已經部署好的Wi-Fi設備，到底如何構建呢?接下來，我們來看看Wi-Fi定位的技術原理。我們將定位過程進行抽象，變成一個數(shù)學問題，即位置函數(shù)求解: (x,y) = F(ap1,ap2,ap3….apN)。函數(shù)F的輸入數(shù)據(jù)是一系列的掃描到的Wi-Fi的信號強度，輸出是定位坐標。我們知道如果存在函數(shù)F能夠滿足以上關系，也就是說輸入和輸出之間就滿足一定函數(shù)關系，也可以視之為相關性。雖然我們不能夠馬上得到函數(shù)F，但可以通過感性分析和理解，信號與位置之間有沒有相關性?我們看以下分析：
離無線設備越遠，信號越弱。
不同位置掃描到不同的Wi-Fi、藍牙等信號。
設備固定、各處信號強度相對穩(wěn)定。
通過以上三個因素，可以看出信號與位置之間確實存在較強相關性，利用這種相關性，可以構建出一套由無線電信號到XY映射的技術。
結合前半部分講的幾何求解法，我們很容易能夠想到，當空間有三個真實的位置AP([x1,y1]，[x2,y2]，[x3,y3])，通過手機測量Wi-Fi的信號強度，按照信號衰減模型，將信號強度換算成測量距離，利用幾何求解法得到定位點。
三角定位示意圖
總體上來看，這種方法的優(yōu)點是模型簡單，容易實現(xiàn)。如果實際系統(tǒng)使用這個簡單的定位模型來做定位，會存在很多問題。首先我們需要一一標注所有AP的準確位置，其會帶來不小的工作量。其次，該模型對AP信號輻射分布刻畫不足，精度不高。
真實的Wi-Fi信號是怎樣的呢?Wi-Fi信號作為一種電磁波，在空間中傳播也會有散射、衰減、損耗、折射等現(xiàn)象。下圖來自于某篇論文仿真圖片。左圖是完全按照信號衰減模型繪制的信號在空間中分布情況。右圖是通過對現(xiàn)場進行多點多次采樣而繪制出來的信號強度真實分布情況。顯而易見，此種分布肯定不符合衰減模型。
另外，通過實驗，我們也發(fā)現(xiàn)：因為手機不同的制造工藝，不同的芯片，不同的機殼材質，會導致無線電信號RSSI感知的差異，呈現(xiàn)出非線性的規(guī)律。(如下圖)
不同手機RSSI測量差異示意圖(本圖來自于互聯(lián)網)
上圖不同顏色代表不同的手機模型，可以看出這些手機在相同時間地點所測量出來的rssi差異還是挺大的。對于手機感知差異問題，一般業(yè)界比較推崇的做法是要對rssi進行校正。通過一些參考場景逐步迭代式優(yōu)化校正參數(shù)，直至收斂穩(wěn)定。
基于Wi-Fi的室內定位算法系列介紹
下來我們著重介紹一些Wi-Fi相對復雜和靠譜的定位方法。之后也會順便介紹百度目前在用的一種低成本長期有效的定位方法-地磁定位。
真實模型的逼近-指紋法
既然我們很難得到每個Wi-Fi在空間中的信號真實分布模型，那么我們可以直接對空間中各個點的進行各種信號的數(shù)據(jù)采集。用采樣數(shù)據(jù)代表AP復雜模型。
某商場指紋采集識別圖
定位過程中，手機發(fā)送當前掃描到的Wi-Fi Query指紋，服務器端直接計算庫中與之相似的指紋，按照權重進行加權中心點計算，從機器學習角度來看，該方法實質是KNN。
KNN計算示意圖
如上圖是KNN計算示意圖，一般來講，KNN適用于分類問題，在定位問題上，我們將Top K個指紋直接進行加權計算而不是統(tǒng)計分類。整體上看，該方法實現(xiàn)簡單，精度尚可，但是要將所有數(shù)據(jù)和樣本進行比對計算，消耗存儲空間，計算量非常大。
局部模型+指紋法
在實際采集作業(yè)過程中，我們很難將商場所有空間區(qū)域都進行密集采集，總會有一些采集不充分，指紋比較稀疏，那么怎么辦呢?在此，我們可以借助局部模型來生成虛擬指紋。
指紋采集稀疏區(qū)域示意圖
指紋生成階段：針對比較稀疏區(qū)域，選擇周圍范圍內一定數(shù)量的采集指紋，盡量讓指紋覆蓋到四周分布。訓練該區(qū)域中每個AP的輻射模型和被掃描到概率等特征，針對稀疏區(qū)域反向推算出每個AP對該空間點的輻射信號強度，最終合并成為虛擬指紋。定位時可以使用采集指紋和虛擬指紋混合的方式提供定位。
該方法主要用來彌補或者增強采集不充分區(qū)域的定位效果，訓練過程相對復雜，定位精度逼近于指紋法，具備一定的魯棒性。
位置回歸分析法
通過之前分析，某點掃描到AP集合與當前點位置(x,y)形成了一個映射關系，我們求解定位位置，其實就是在做位置的回歸分析問題?；貧w的目標就是得到x和y。相信了解機器學習的同學對接下來做的事情就很熟悉了。首先我們將掃描到AP集合作為特征向量，訓練對x，y的回歸模型。該模型相當于得到那個非常復雜的信號在實際空間輻射分布模型，所以很難用單一公式表達，但是通過回歸分析模型的訓練，我們得到其復雜模型。如下示意圖，整個模型是由很多復雜樹構成。
位置回歸分析模型示意圖
定位過程中，我們同樣將Wi-Fi Query上傳到服務器上，服務器將其轉化為特征向量，然后由回歸模型來進行定位位置預測。整體上來講，該方法實現(xiàn)比較簡單，但模型訓練復雜，需要調參，有一定難度，精度可以逼近指紋法。
地磁定位法
地磁信號來源于地球本身，因為地心引力，地磁場本身存在。鋼筋結構和地板等物體都會對地磁產生影響。地磁強度由于建筑結構不發(fā)生變化，基本上還是比較穩(wěn)定的。如下圖是某個商場內部地磁場強分布示意圖。
某商場地磁場強分布示意圖
一般情況下，在一段時間內磁場強度變化本身就是一種指紋。例如我們從走廊東頭走到走廊西頭的整個過程中，地磁場強變化就很明顯，如下圖，曲線上下變化本身就是一種指紋。
某段地磁場強變化示意圖(本圖來自于互聯(lián)網)
定位過程中，通過計算定位地磁序列指紋與指紋庫中的子序列相似度來得到最佳匹配位置。這是一個模糊子序列查找問題，一般來說，商場地磁指紋數(shù)量比較多，導致實時搜索空間巨大，因此會利用空間索引技術+粒子濾波提高匹配性能。總的來說，地磁定位法的特點是實現(xiàn)相對復雜，需要做地磁校正，但是精度效果優(yōu)秀。
寫在最后
通過上述各章節(jié)介紹，相信大家對室內定位已經有了大體了解。室內定位是垂直專業(yè)方向，除了需要信號處理相關專業(yè)知識，還需要對機器學習有一個很深入的了解。因此，真正要做好，需要很長時間的技術積累和經驗總結。百度一直秉持讓大家平等獲取信息的理念，持續(xù)投入資源，支持該方向的技術研發(fā)。我們的目標是做中國一流的室內定位服務，讓大家隨時可以獲取到高精度定位體驗。
{{item.content}}