采用安卓系統的多模室內地圖自動構建系統

許 強，趙 方，尚國強，朱沿旭，左 超

(1.北京郵電大學，北京 100876；2.北京航空航天大學電子信息工程學院，北京 100191；3總裝備部工程設計研究總院，北京 100028)

1 背景介紹

當今世界，電子地圖在人們的生活中越來越突顯出愈發重要的輔助作用，現在室外地圖構建技術已經逐漸趨于成熟，能夠為用戶提供精確的室外地圖，而相關室外位置技術也層出不窮，豐富了人們的日常生活，帶來極大的便利。

然而隨著移動互聯網的迅猛發展，但是室外位置相關技術已經不能完全滿足人們的定位需求了，人們不僅僅滿足于能獲得在室外的精準定位，對室內精準定位提出了迫切需求，室內位置相關技術應用研究逐漸開始流行。

室內位置相關技術的核心就是室內定位，室內定位是指利用各種手持設備基于或者不基于室內已知精確位置基礎設施，推導計算出當前設備在室內所處位置。

現今室內定位大部分是基于已知地圖的，但是由于建筑建成時間、建筑所有權、建筑管理等原因，并不能獲取有效即時室內地圖，所以沒有辦法保證利用地圖進行室內精準定位的方案順利進行。

為了彌補室內地圖的缺失，繪制室內地圖是必不可少的步驟，但是當今常見的室內地圖繪制通常需要使用很大的精力，例如基于達時間差(time difference of arrival，TDOA)的ARIADNE系統[1]，要首先部署室內射頻信號發射點，然后進行海量采樣，才能畫出較精準的可用射頻指紋信息圖，這個繪制過程往往要耗費大量人力物力，有時甚至條件難以滿足。

當完成室內距離、興趣點(points of interests，POI)等數據大量采集后，還需要經過繁雜的處理、運算繪出室內定位可用的矢量地圖，總的來說，從數據采集到室內地圖繪制整個過程都是條件要求極高并且運算量很大的，難以符合快速獲取室內地圖的要求。

針對以上情況，提出一個眾包的解決方案，擬利用群體無意識協作，降低對人力投入的依賴，利用無關人群手持設備中安裝的相關軟件，調用各種內置傳感器采集信號數據，在手機獲得網絡鏈接時，隨機地發送給服務器，從大量數據中提取出室內拓撲圖，并將其應用到室內定位中。

2 相關工作

從各種角度看來，室內定位不可能獨立于室內地圖而存在，離開了室內地圖，室內定位就像是無根之木，定位根本無從談起。只有結合了室內地圖，室內定位才有據可依，才變得有意義。同樣，室內地圖也需要用于室內定位才能彰顯出它的作用，并且室內地圖的獲取同樣也需要部分依賴于室內定位技術，室內定位和室內地圖兩者是相輔相成的一個整體。

現在較先進的繪制室內地圖和室內定位使用的的數據很多都是來源于同樣類型的信號數據，這些數據不僅可以利用到室內定位中，也同樣可以利用到室內地圖的構建繪制中。

對于室內定位來講，近年來定位方案層出不窮，但都離不開以下幾個方向：基于紅外技術、基于超聲波技術、基于藍牙技術、基于射頻識別技、基于無線保真(wireless fidelity，WiFi)相關技術、基于地磁、基于加速度傳感器等。這些方向總結起來可以分為兩大類，一類是基于信號傳播模型的，另一類是基于信號指紋的[2]。

基于信號傳播模型的室內定位，主要是首先在室內部署信標點，即已知信號發射源在地圖上的位置坐標，將在某地點接收到的接收信號強度值(received signal strength，RSS)代入相應的信號傳播模型中，計算推斷出該點位置。較早的RSS相關傳播模型有基于到達時間(time of arrival，TOA)的PinPoint系統，基于到TDOA的Cricket和基于到達角度(angle of arrival，AOA)的VOR系統等。

除此之外，較常用的信號傳播模型有長距離路徑衰減模型(long-distance path loss，LDPL)模型，它是利用測量到的RSS值根據射頻(radio frequency，RF)傳播距離模型來確定當前位置距離已知錨點(anchor point，AP)長度，然后通過AP點位置和長度來確定當前所處具體位置。但是很明顯這種模型犧牲了室內復雜環境下的定位精度，換取降低初期大量人工采樣的代價。雖然這種模型算法免去了人工采樣的過程，但是需要初期部署AP點，并設定AP點精準坐標，這樣才能利用已知精確位置AP點進行定位。EZ模型是基于LDPL模型的一種變型，它利用無線信號傳播測算距離并利用遺傳算法解決定位問題，EZ要根據在窗戶或者建筑入口處隨機獲得全球定位系統(global positioning system，GPS)信號來確定位置的絕對坐標。

這種測算距離位置已知信號源長度的方法不僅僅可以用在室內定位，也可以用于室內地圖繪制，但是這類方法要實現知道所有的信號源坐標，所以部署過之后，繪制室內地圖的意義并不大。

對于基于信號指紋的室內定位來說，最重要的就是室內多種類型的興趣點，興趣點是指已知位置點或者可以通過分析某種數據的變化特征得出的點，可以在室內定位中用做AP點，常見的使用這些特征點指紋的方法是通過大量采集信號數據，分析得出相應特征點指紋，并將得出的指紋存入數據庫，然后利用人當時所處地理位置信息與指紋匹配，進行定位。

最早使用基于指紋匹配技術的室內定位系統是RADAR[3]，RADAR是一個利用射頻指紋(radio frequency identification devices，RFID)來進行用戶室內定位和室內移動軌跡記錄的系統。之后的一些室內定位系統有基于RADAR改進的Horus系統，使用室內RFID[4]定位的LANDMARC系統[5]，和利用室內WiFi指紋的WILL系統[2]。

這種采集信號指紋用作室內定位的思路，也同樣適用于室內地圖挖掘，而且比基于信號傳播模型的方法更契合實際。通常在挖掘繪制室內地圖的時候，室內的POI點也是可以利用的，最常見的思路就是采集到室內的各個AP之后，根據AP之間的連通關系畫出室內連通圖。

最初的室內地圖繪制，主要是通過人工測量室內相關數據，再由相關人員利用繪圖軟件繪制地圖。后來的利用定位技術的繪制地圖方法也主要是基于這種最原始的思路，都是需要測量各種距離數據，然后利用數據繪制出地圖來，例如現在蘋果(Apple)公司推出的利用iBeacon方式繪制室內地圖，這些方式都要預先部署基礎設施，并且知道設施的具體位置，這樣很難做到大規模繪制室內地圖。

后來利用室內各種信號指紋挖掘室內地圖，雖然在方法上更方便，但是還是存在缺點，例如仍然無法消除對人工部署已知基礎設施的依賴，仍然需要安排一些人員進行數據采集工作，并且當前的地圖繪制方法很難找到一種低消耗且高質量的思路。

鑒于以往地圖繪制技術通常需要有目的性的部署相關基礎設施，并且需要專門人員在建筑內采集數據，導致繪制成本較高，并且有些前提條件不能很好的滿足，所以為了避免這些短處，本系統主要是基于眾包的方式采集數據，眾包主要是指利用人群的無意識協作，即利用裝在很多人手機上軟件的附加功能，在平時用戶手持手機活動的時候開始采集相關數據，并臨時存儲在手機上。當手機獲取網絡訪問的時候，將采集到的數據傳輸到服務器端。這種模式大大地降低了采數據開銷，能夠將數據采集的任務分配給很多人共同完成。而繪制地圖主要是基于WiFi基礎設施，以智能手機為輔助，采集多種室內地理信息特征點，挖掘室內地圖并利用得到的地圖進行室內定位。

3 方法設計

當前在做室內定位方面，大部分是需要基于已知地圖的，在地圖未知的情況下，進行室內定位非常艱難，而本研究主旨就是利用WiFi指紋以及其他輔助AP挖掘室內拓撲結構、構建室內地圖，為進一步室內定位提供基礎。

本文提出一種C/S(Client+Server)架構的系統來實現室內拓撲圖繪制的方案，基于安卓(Android)系統的客戶端主要負責利用手機內自帶的各類傳感器，收集目標數據并對數據進行初步處理，將其保存在手機本地。當手機偶然獲得網絡訪問的時候，將存儲的數據發送到服務器上，在服務器上，對采集到的數據進行聚類分析等后續處理，并挖掘出室內拓撲結構，繪制室內地圖。

圖1 系統結構圖

3.1 客戶端設計

根據前人在基于信號指紋的室內定位技術的卓越研究成果，主要基于計步器[6]，采集室內WiFi指紋、用加速度傳感器采集樓梯電梯以及利用陀螺儀采集轉彎點等地理位置信息特征點。首先經過粗粒度處理之后臨時存儲在用戶手機上，然后當手機獲得網絡訪問的時候，將數據文件發送給服務器端。

以下介紹使用的室內地理信息特征點。

3.1.1 WiFi-MARK

采集WiFi數據的時候，并不需要知道WiFi信號源的具體位置，亦即不需要事先部署滿足需要的WIFI設施，而是只需要利用室內已存在的基礎設施即可。

圖2 WiFi空間信號強度示意圖

由于WiFi傳播信號如圖2，在三維空間中WiFi信號強度相同的空間可以構成一個球面，而對于水平的樓層來說則是一個圓，行走過程的軌跡相當于是“等WiFi強度”圓形區域的一條割線，根據幾何知識可知，在這條割線的正中間是WiFi信號最強的點，如圖3所示，在采集數據的時候將其記錄下來，作為一個WiFi標記，稱作WiFi-PEAK。WiFi-PEAK記錄格式為：

WP={RSSID，RSSI，wPosition，A}；

其中RSSID指該點接收到的WIFI信號的ID，RSSI代表對應的RSSID信號強度，wPosition是指該點基于計步器的相對位置，A是指該點接收到的臨近WiFi接入點集合，用來分辨當前點和RSSID的相對位置。

圖3 WiFi信號強度變化

之所以要采用WiFi信號最強點而不是采集普通WiFi信號用作為WiFi指紋是因為：由于設備差異性、設備位置不同和采樣時間變化，采集到的WiFi信號強度并不相同，甚至還有相對較大的誤差，這些誤差給生成WiFi指紋的過程帶來很大麻煩，而采集信號最強點則避免了這些麻煩[8]。

使用滑動窗口的方式采集WiFi信號最強點，亦即在一條沒有拐彎的路徑上，使用7個窗口的滑動窗口機制，識別出信號最強點。

3.1.2 電梯樓梯

利用手機中自帶的加速度傳感器，能夠測量記錄手機的實時重力讀數。根據重力讀數以及在電梯、扶梯和樓梯處的重力變化特征，如圖3.4所示，能識別出相應的電梯扶梯和樓梯，這些地點通過走廊連接入室內地圖[9]。

圖4 電梯、樓梯和正常行走時的重力讀數區別

3.1.3 轉彎點

在常見的室內定位中，轉彎點通常是無用的，有些甚至將其視作產生噪聲干擾的來源之一，但是在本系統中，通過記錄手機中自帶的陀螺儀讀數變化，識別出轉彎點(cornerpoint，CP)，并將其記錄下來。識別過程也使用滑動窗口機制，轉彎點記錄格式如下：

CP={bDirection，aDirection，pPosition}；

其中bDirection是指在轉彎前的前進方向，aDirection是轉彎之后的前進方向，pPosition是指由計步器所得的轉彎點的相對位置。轉彎點可以用在約束兩段直的走廊路徑上，鏈接兩個不同方向的走廊。

3.1.4 門

由以上的點可以畫出走廊的形狀，為了繪制室內地圖還需要房間的形狀。而房間和走廊的連接點是門，同樣在繪制地圖的時候，也可以通過門來將室內數據和走廊數據聯系起來。

門是跟走廊直接連接的，根據采集到的數據分析，其中較大概率的情況下，在門的位置的地方會有靜止并且方向不規則變化的特征，根據這個概率性特征以及判斷是否與走廊緊密相連，可以確定出門所在位置。

3.1.5 室內靜止點

房間在室內地圖中是很重要的一部分，在繪制室內地圖的過程中，不僅要繪制出房間的大致形狀，并且還要將相鄰房間區分出來。在大多數情況下，人們在房間內通常會有較長時間的靜止(例如10 min以上的靜止)，在設計的系統中，當手機長時間靜止的話，將其認為是在室內，并記錄該點位置及相關信息，相關信息主要是指在該點接收到的部分WiFi信號的RSSID以及其對應強度，其中部分是指僅記錄RSS>-40以及RSS<-80的信號特征，由于每個房間是墻壁封閉的，所以每個房間里的點采集到的該特征是有較大差別的，通過這個特征將不同房間的點區分出來，并標示出房間[10]。

3.2 服務器端設計

將服務器設計為迭代式的，在服務器端將采集到的數據梳理分類，利用K-means算法，剔除噪聲點，將采集到的室內WiFi-PEAK、樓梯電梯點和轉彎點數據進行聚類，得到相對應的可用AP，通過轉彎點的約束走廊方向，連接分段走廊，并且加入AP點即可擬合出較為精確的走廊地圖，根據采集到的室內靜止點和從門到室內靜止點之間的行走軌跡，可以畫出房間的形狀，并且通過室內靜止點的數據可以區分出房間，利用門的點將房間和走廊連接起來就可以得到房間和走廊的完整地圖。

接下來可利用手機在窗口或者門口偶然獲得的GPS信號，以修正室內相關地理信息點在地球坐標系中的精確位置，最終獲得室內外無縫銜接的地圖。

4 系統實現

針對上一節定義的需要采集的點，設計出的客戶端核心代碼結構如下：

Algorithm1 Anchor points recognition

Scanresult=Wifimanager.ScanWifi()；//掃描WiFi信號

Δdegree=| oldDegree - curDegree |；//陀螺儀角度變化

if(0<Δdegree<40){

if(Scanresult.slidewindow.hasMidPeak)

Write(scanresult.peak)；//滑動窗口得出WIFI-PEAK

}else if(Δdegree>40 &&Δdegree<320){

if(preSteps>3 && postSteps>3)

Write(turning)；//得到轉彎點

if(threshold0

Write(door)；//得到門的位置

}

if(statictime>threshold3)

write(roompoint)；//得到室內靜止點

if(accellorator.patten==ELEVATOR){//根據加速度傳感器的變化得到相應的電梯和樓梯的位置

write(elevator)；

}else if(accellorator.patten==STAIR){

Write(stair)；

}

將采集到的點存儲在移動終端本地，當獲得網絡的時候隨機將數據文件發送到服務器端，服務器接收到數據之后，將接收到的數據進行聚類，并多次迭代。聚類的相關偽碼如下：

Algorithm2 Anchor points clustering

//數據讀取

read(wifidata)；

read(turningdata)；

read(stepdata)；

read(elevatordata)；

read(stairdata)；

//聚類處理

line[1]=kmeans(firststep，'sqEuclidean')；//起點

for i=1：wifidata.length //WIFI-PEAK

record[wifidata[i].mac].insert(wifidata[i].position)；

for i=1：record.length

line[i+1]=kmeans(record[i]，'sqEuclidean')；

line[i]=kmeans(turndata，'sqEuclidean')；//轉彎點

line[i+1]=kmeans(stairdata，'sqEuclidean')；

line[i]=kmeans(elevatordata，'sqEuclidean')；//電梯

//擬合處理

polyfit(line.x，line.y)；

根據以上系統實現，將客戶端安裝在不同型號的手機上(MEIZU MX，MEIZU MX3，SAMSUNG NOTE2，htc one)并在北京郵電大學明光樓內采集數據，得到結果如下圖：

圖5 數據分類聚類以及擬合直線

與明光樓的室內實際圖對比如下：

以上數據是總共行走了50次之后得到的路徑，可以看出已經與實際情況相差無幾。

圖6 走廊圖放在實際地圖內

5 結束語

從實驗結果來看，本系統在精確度上是值得認可的，在不需要事先布置任何先驗基礎設施的情況下，可以無障礙的獲取室內可用的地理信息特征點，并將其轉化為AP點，并用來繪制室內地圖。

在數據采集的過程中，如果采集數據的程序一直運行的話，陀螺儀讀數——即角度變化讀數累積誤差將會變得大到不能接受，所以必須要對陀螺儀讀數過一段時間內進行重置校正。

門的識別在當前研究領域都是一個比較困難的問題，在本文中采取的方法也只是利用一定概率出現某種特征的方法判別門的位置，這是一個可以繼續研究的方向。

[1] JI Yi-ming，BIAZ S，PANDEY S，et al.ARIADNE：A Dynamic Indoor Signal Map Construction and Localization System[C]//Proceedings of the 4th International Conference on Mobile Systems，Applications and Services.NY：ACM，2006：151-164.

[2] WU Chen-shu，YANG Zheng，LIU Yun-hao，et al.WILL：Wireless Indoor Localization without Site Survey[C]//Proceedings of INFOCOM 2012.Orlando：IEEE，2013：839-848.

[3] BAHL P，PADMANABHAN V N .RADAR：An In-building RF-based User Location and Tracking System[EB/OL].[2014-08-15].http：//research.microsoft.com/en-us/people/padmanab/infocom2000.pdf.

[4] 王小輝，汪云甲，張偉.基于RFID的室內定位技術評述[J].傳感器與微系統，2009，28(2)：1-3+7.

[5] NI L M，LIU Yun-hao，LAU Y C，et al.LANDMARC：Indoor Location Sensing Using Active RFID[EB/OL].[2014-08-15].http：//www.cs.ust.hk/～liu/Landmarc.pdf.

[6] ALZANTOT M，YOUSSEF M.UPTIME：Ubiquitous Pedestrian Tracking Using Mobile Phones[C]//Proceedings of Wireless Communications and Networking Conference(WCNC)，Shanghai：IEEE，2012：3204-3209.

[7] CHINTALAPUDI K，IYER A P，PADMANABHAN V N.PADMANABHAN.Indoor Localization without the Pain[EB/OL].[2014-08-15].http：//research.microsoft.com/pubs/135721/ez-mobicom.pdf.

[8] SHEN Guo-bin，CHENG Zhuo，ZHANG Pei-chao，et al.Walkie-markie：Indoor Pathway Mapping Made Easy[C]//Proceedings of the 10th USENIX Conference on Networked Systems Design and Implementation.CA：USENIX Association，2013：85-98.

[9] WANG Feng，LUO Hai-yong，LI Zhao-hui，et al.Activity-based Smartphone-oriented Landmark Identification for Localization[C]//Proceedings of Principle and Application Progress in Location-based Services.Switzerland：Springer International Publishing，2014：59-71.

[10] ERIC T，ZAKHOR A.Floor Plan Generation and Room Labeling of Indoor Environments from Laser Range Data[C]//Proceedings of the 10th International Joint Conference on Computer Vision，Imaging and Computer Graphics Theory and Applications.Lisbon：GRAPP，2014：22-33.