1. 摘要&引言
- 基于GPS的室外定位當(dāng)前被廣泛使用，但是很少的室內(nèi)定位系統(tǒng)被部署和使用乏沸。本篇論文作者分享了5年的經(jīng)驗(yàn)關(guān)于如何部署和評估一個大規(guī)模的基于wifi的室內(nèi)定位系統(tǒng)冲粤。本系統(tǒng)當(dāng)前在1469個商場美莫、393個辦公樓、35個醫(yī)院部署覆蓋了35座城市梯捕，系統(tǒng)每天給幾百萬的用戶提供定位服務(wù)厢呵。作者發(fā)布了相關(guān)的數(shù)據(jù)集，包括1469個商場和一個辦公樓相關(guān)的指紋數(shù)據(jù)傀顾。系統(tǒng)整體架構(gòu)見下圖所示襟铭。。 相關(guān)數(shù)據(jù)集可以在github中看到：https://github.com/IndoorFingerprint/IndoorFingerprintData
- 室內(nèi)定位常使用的技術(shù)包括：wifi短曾、藍(lán)牙寒砖、UWB等。藍(lán)牙嫉拐、UWB定位需要專門的硬件部署哩都，不太適合大規(guī)模的部署。所以本文考慮使用wifi進(jìn)行室內(nèi)定位婉徘，因?yàn)樵诖蠖鄶?shù)商場漠嵌、辦公樓等區(qū)域都會有wifi的部署，不需要額外部署專門的設(shè)備盖呼。基于Wifi的室內(nèi)定位技術(shù)大致可以分為三類：angle-based（AOA）儒鹿、time-based（TOA）、fingerprint-based塌计。AOA和TOA的wifi定位技術(shù)對WIFI設(shè)備有極高的要求挺身，AOA定位技術(shù)要求有精確的角度測量、TOA技術(shù)要求有精確的時間測量锌仅≌录兀基于指紋的定位技術(shù)包括：CSI和RSSI墙贱。CSI的獲取只有某一些WIFI卡才能獲取比如Inter 5300卡和Atheros AR系列卡。因此最終采用基于RSSI測量的指紋定位技術(shù)贱傀，RSSI值可以在大多數(shù)的WIFI設(shè)備上獲取惨撇。
2. 指紋收集
- 指紋收集是非常費(fèi)時費(fèi)力的，人工收集指紋的方式不太適合大規(guī)模的部署室內(nèi)定位系統(tǒng)府寒，因此本文提出了一種基于眾包的方法收集指紋數(shù)據(jù)魁衙。本文提出了一個通過兩階段的方式是的大規(guī)模的指紋收集成為可能，首先第一個階段獲取WIFI AP數(shù)據(jù)的粗略的位置株搔，通過這種方式獲取初始的指紋庫數(shù)據(jù)剖淀。然后我們通過用戶的反饋迭代更新我們的指紋庫數(shù)據(jù)，通過這種方式獲取更高質(zhì)量的指紋庫數(shù)據(jù)纤房。
2.1 WIFI AP位置估計
WIFI AP的位置估計分為兩個階段：第一個階段我們通過名稱匹配的方式獲取一些AP的位置纵隔，這些AP的名稱通常和POI名稱有一定的關(guān)聯(lián)，在樓層指引的幫助下我們能夠獲取這些AP的較準(zhǔn)確的物理位置炮姨。第二個階段我們使用推測出的AP位置捌刮，去推測剩余AP的位置信息。
第一階段：使用名稱信息估計AP的位置舒岸。 為了匹配Wifi AP的名稱和POI绅作，我們采用NLP工具（Spacy，https://spacy.io/）處理AP名稱蛾派，并且我們考慮名稱縮寫的相似性俄认。最終我們采用Google的wide&deep模型匹配AP的名稱和POI的名稱。在所有的4百萬的AP庫能夠通過名稱匹配的WIFI AP占比約為19.63%碍脏。其中商場梭依、辦公樓、醫(yī)院中能夠通過名稱匹配獲取位置占比分別為：38.23%典尾、13.50%、7.65%糊探。為了評估名稱匹配模型的準(zhǔn)確率钾埂，人工收集8000個AP的真值，最終計算得到模型匹配的準(zhǔn)確率為98.4%科平。
第二階段：估計剩余AP的位置褥紫。 要估計剩余AP的位置，首先需要計算剩余AP與已估計位置AP的相似度瞪慧。
本文首先想到的是通過計算AP之間的共現(xiàn)次數(shù)髓考，來計算兩個AP之間的相似度，計算公式見公式（1）弃酌。其中表示
和
被同一臺手機(jī)掃描到的次數(shù)氨菇，
表示掃描到
-
在估計AP的位置之前豌研，我們首先需要估計AP的樓層信息妹田。如果與
個AP都在同一層，則
- 在商場温眉、辦公樓缸匪、醫(yī)院三個場景下被估計出位置的AP占比分別為：91.10%，91.40%类溢，86.87%凌蔬。為了評估AP位置估計的準(zhǔn)確率，我們?nèi)斯な占?000個AP位置真值闯冷，最終誤差估計的中位數(shù)在三個環(huán)境中分別為：5.16米砂心、8.65米、23.61米蛇耀。
2.2 指紋收集
- 指紋收集過程分為兩步：初始化階段和更新階段辩诞；指紋的兩個重要組成部分是：位置（Location）和這個位置相關(guān)的特征（unique features associated with this location）。 傳統(tǒng)的基于wifi的指紋僅僅使用AP的信號強(qiáng)度作為唯一的特征纺涤，本文中加入了位置的請求次數(shù)作為額外的特征译暂。
- 位置指紋初始化： 本文采用基于迭代的方式更新指紋數(shù)據(jù)，首先通過眾包的方式初始化指紋庫數(shù)據(jù)撩炊，然后通過用戶的反饋刪除那些不正確的指紋數(shù)據(jù)外永。每次請求的時候，根據(jù)用戶手機(jī)接收到的AP及其信號強(qiáng)度我們可以粗略估計用戶的位置拧咳，具體計算公式見公式（4）伯顶。我們能夠通過眾包的方式很快的收集到很多的指紋數(shù)據(jù)。1469個商場平均需要花費(fèi)6.6天的時間收集到87.4%位置的指紋數(shù)據(jù)。剩下的位置用戶很少到訪祭衩，因此對于定位服務(wù)影響不大灶体。
- 位置指紋更新： 通過指紋的初始化可以獲取很多指紋數(shù)據(jù)，但是可能不是很正確汪厨。因此本文繼續(xù)通過大量的用戶反饋修正初始指紋庫數(shù)據(jù)赃春。通過一些獎勵機(jī)制獲取用戶反饋，比如給用戶發(fā)一些優(yōu)惠券等劫乱。大約可以獲取5%的用戶反饋织中，反饋的形式就是讓用戶給系統(tǒng)定位結(jié)果進(jìn)行打分（1~5分）。只有當(dāng)我們接收的用戶得分與之前的得分相等或者更高的時候衷戈，我們才更新我們的指紋庫數(shù)據(jù)狭吼，否則我們使用最新的AP數(shù)據(jù)獲取位置的最新指紋數(shù)據(jù)。對于商場場景平均經(jīng)歷6天的時間殖妇，所有的指紋庫數(shù)據(jù)都會獲得5分的評分刁笙。
3. 數(shù)據(jù)處理
3.1 基于多特征的定位
- 本文的指紋定位使用的特征包括：RSSI和請求次數(shù)特征。為了計算數(shù)據(jù)庫中網(wǎng)格的RSSI列表和在線收集的RSSI列表相似度谦趣，我們首先要定位兩個列表的共同AP疲吸，然后計算RSSI列表相似度。計算的指標(biāo)包括：euclidean distance, rank distance, distribute distance, reverse-pair rate前鹅。 如果共同的AP數(shù)量少于3摘悴，則這個網(wǎng)格將排除不考慮。本文還引入了請求次數(shù)作為另外一個指紋特征舰绘，請求次數(shù)特征能夠告訴我們當(dāng)用戶發(fā)起定位的時候哪個位置更受歡迎蹂喻。作者發(fā)現(xiàn)發(fā)起定位請求的地方大多數(shù)在某個POI的入口，比如飯店的入口捂寿。
- 為了比較好的將兩種特征結(jié)合起來口四，我們使用熟知的LambdaRank模型。LambdaRank模型將網(wǎng)格的特征作為輸入秦陋，對網(wǎng)格進(jìn)行排序蔓彩，排在最前面的網(wǎng)格就是最終估計的位置。本文將用戶反饋的數(shù)據(jù)訓(xùn)練LambdaRank模型驳概。
3.2 現(xiàn)實(shí)世界中的挑戰(zhàn)
- 室內(nèi)外邊界檢測： 邊界檢測對于精確定位至關(guān)重要粪小，比如當(dāng)一個用戶進(jìn)入到一個商場，如果仍然使用GPS服務(wù)抡句，則會產(chǎn)生較大的定位誤差。目前常用的方法是使用智能手機(jī)的傳感器比如亮度和大氣壓傳感器杠愧，用來判別室內(nèi)外待榔。本文僅僅使用GPS和WiFi的信號強(qiáng)度分布用于室內(nèi)外的判別，其基本原理是：WIFI在室內(nèi)外信號強(qiáng)度分布有明顯差異，室內(nèi)環(huán)境強(qiáng)于室外環(huán)境锐锣，然而GPS信號強(qiáng)度在室外環(huán)境強(qiáng)于室內(nèi)環(huán)境腌闯。下圖5展示了室內(nèi)外WiFi和GPS信號強(qiáng)度分布，作者在不同的位置收集了WiFi和GPS信號強(qiáng)度分布訓(xùn)練了室內(nèi)外判別模雕憔，模型獲得的準(zhǔn)確率為98.7%姿骏。注意室內(nèi)外判別跟具體的某個AP沒有關(guān)系，只跟采集到的AP信號強(qiáng)度分布有關(guān)斤彼。
- 建筑中的中空區(qū)域： 在中空區(qū)域（例如電梯口或者室內(nèi)橋）中分瘦，我們發(fā)現(xiàn)會出現(xiàn)大量的樓層識別錯誤。并且我們發(fā)現(xiàn)在中空區(qū)域邊緣的AP信號強(qiáng)度分布出現(xiàn)了兩個波峰琉苇，而其他區(qū)域的AP信號強(qiáng)度分布沒有這樣的表現(xiàn)嘲玫，只出現(xiàn)一個波峰。最終在樓層定位的時候并扇，我們將中空區(qū)域的AP刪除因?yàn)橐胨鼈儗a(chǎn)生較大誤差去团。
4. 大規(guī)模系統(tǒng)實(shí)驗(yàn)
4.1 商場定位
本文提出的室內(nèi)定位系統(tǒng)部署在1469個商場中，所有的WiFi AP都是第三方部署的穷蛹。并且作者發(fā)布了商場的指紋庫數(shù)據(jù)土陪，數(shù)據(jù)采集是基于5mx5m的網(wǎng)格。室內(nèi)定位系統(tǒng)每天可以收到8810萬的定位請求肴熏。 本文提出的定位系統(tǒng)獲得了4.56的評分基于41500個投票結(jié)果鬼雀，投票的時間范圍是從2020年1月到2022年3月。為了評估模型的效果作者手動收集4個商場的groundtruth扮超，包括大中小各種類型的商場取刃。并且選擇一個大型和一個中型的商場，跟蘋果比較室內(nèi)的定位結(jié)果出刷。 最終總共收集了31140個參考點(diǎn)進(jìn)行定位評估（參考點(diǎn)的位置璧疗，通過激光測距儀測量當(dāng)前位置與墻等位置的距離，進(jìn)而通過樓層平面圖推測參考點(diǎn)位置）馁龟，其中大商場包括20300個崩侠，中型商場5230個，小型和特殊形狀的商場分別2510個和3100個坷檩。并且對比了不同系列的Iphone手機(jī)和不同品牌的Android手機(jī)却音，商場定位效果如圖9所示。
-
從下圖9可以看出矢炼，在大型和中型的商場本文提出的室內(nèi)定位系統(tǒng)可以獲得6.12米和6.43米中等誤差定位精度系瓢。本文提出的系統(tǒng)獲得了與蘋果通過人工收集指紋方式（蘋果室內(nèi)定位：https://register.apple.com/resources/indoor/Apple-Indoor-Maps-Program.pdf）差不多的定位精度。在小型和特定形狀的商場句灌，蘋果沒有指紋采集的情況下夷陋，定位效果顯著下降但是本文提出的室內(nèi)定位系統(tǒng)沒有出現(xiàn)顯著的下降欠拾。
本文室內(nèi)定位系統(tǒng)與iPhone手機(jī)定位效果對比.png -
下圖10展示了不同品牌手機(jī)的定位效果對比，從下圖可以看出不同品牌的手機(jī)定位效果沒有顯著的差異骗绕。
不同品牌手機(jī)的定位結(jié)果.png AP位置估計： 在4個商場中通過名稱匹配的方式藐窄，分別可以獲取1592，288酬土，101和176個AP的位置荆忍，分別各自占比52.8%，51.33%撤缴，47.64%刹枉，39.82%，將這種AP使用綠色點(diǎn)表示腹泌。進(jìn)一步通過近似估計的方案嘶卧，可以估計出1251，237凉袱，84和230個AP的位置芥吟，把這些AP標(biāo)記為紅色。最終有位置的AP的占比分別為94.38%专甩，93.58%钟鸵，87.26%，91.85%涤躲，還有一些沒有估計出位置的AP標(biāo)記為灰色棺耍。
- 中空區(qū)域的處理： 通過使用本文提出的中空區(qū)域處理策略，樓層定位準(zhǔn)確率有了顯著的提升：55.63% -> 98.92%, 56.12% -> 99.31%, 56.75% -> 99.53%, 53.82% -> 98.25%种樱。對應(yīng)四個商場樓層識別混淆矩陣如下圖11所示蒙袍。
- AP物理位置改變： 在我們長期對兩個大型商場評估的過程中，我們發(fā)現(xiàn)經(jīng)過一年大約19.1%的AP會發(fā)生移動嫩挤，如果不更新指紋庫數(shù)據(jù)的話會導(dǎo)致很大的定位誤差害幅。通過我們提出的用戶反饋的指紋庫更新策略，能夠很好的解決這樣的問題岂昭。從下圖12可以看出如果長期不更新指紋庫數(shù)據(jù)以现，會導(dǎo)致非常大的定位誤差。
- 多路徑效應(yīng)影響： 本文對工作日和非工作日约啊，不同時間段的定位誤差做了一個詳細(xì)的對比分析邑遏。從圖13我們可以發(fā)現(xiàn)，對于不同時間段工作日和非工作日定位誤差差距不是很大恰矩。
4.2 辦公樓定位
- 雖然本文的定位系統(tǒng)在商場獲得了比較好的定位精度（平均約6.82米）记盒，但是在辦公樓定位精度較差。主要的原因還是辦公樓的AP部署比較稀疏外傅，為了進(jìn)一步提高定位精度孽鸡，本文在辦公樓定位結(jié)合了wifi定位和IMU傳感器數(shù)據(jù)蹂午。一般來說信號強(qiáng)度的采集頻率很低在0.0167Hz ~ 0.5Hz之間，但是IMU數(shù)據(jù)的采集頻率一般在100Hz左右彬碱。利用加速度計、陀螺儀和地磁器的傳感器數(shù)據(jù)和PDR算法奥洼，可以大致估計用戶的行走速度巷疼、方向和位移。為了測試融合后的模型效果灵奖，本文測試了10條不同的軌跡嚼沿，長度范圍從50米到150米。50個志愿者分別去走這10條軌跡瓷患，最終的整體表現(xiàn)如圖15a所示骡尽。從圖15a我們可以看到使用IMU數(shù)據(jù)，中位數(shù)誤差從9.13米下降到3.79米擅编。并且作者也測試了不同RSSI采集頻率對定位誤差的影響攀细，從圖15b我們可以看出中位數(shù)誤差大概在7.37米，4.76米爱态，3.79米谭贪，3.26米和2.55米，分別對應(yīng)不同的采樣頻率锦担。
4.3 醫(yī)院定位
- 醫(yī)院定位和商場定位有很大的不同之處：醫(yī)院部署的AP一般比較少俭识，并且大部分AP都不能通過名字和POI進(jìn)行關(guān)聯(lián)。但是醫(yī)院通常會有一些收銀臺洞渔，并且還有自助打印機(jī)供患者打印檢查報告套媚。為了保證更好的支付和服務(wù)通常會部署WIFI ap在附近。最終醫(yī)院的中位數(shù)定位誤差在11.85米磁椒。
5.結(jié)論
- 應(yīng)用和服務(wù)： 本文的室內(nèi)定位系統(tǒng)可以提供基于位置的廣告堤瘤、打車、外賣服務(wù)衷快。但是在停車場這種場景下宙橱，如何提供室內(nèi)定位服務(wù)具有很大的挑戰(zhàn)，因?yàn)閃ifi AP部署的非常少蘸拔。使用方式： 本文提出的室內(nèi)定位系統(tǒng)师郑，提出了三種方式使用定位服務(wù)：包括App, SDK, Web RESTful API。
參考資料
- 論文：Experience: Pushing Indoor Localization from Laboratory to the Wild
https://dl.acm.org/doi/pdf/10.1145/3495243.3560546 - 犀牛鳥硬核 | 騰訊大出行團(tuán)隊(duì)論文入選MobiCom2022调窍！
https://www.withzz.com/article/208148f9397f/
