許 強(qiáng)，趙 方，尚國強(qiáng)，朱沿旭，左 超

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

1 背景介紹

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

然而隨著移動互聯(lián)網(wǎng)的迅猛發(fā)展，但是室外位置相關(guān)技術(shù)已經(jīng)不能完全滿足人們的定位需求了，人們不僅僅滿足于能獲得在室外的精準(zhǔn)定位，對室內(nèi)精準(zhǔn)定位提出了迫切需求，室內(nèi)位置相關(guān)技術(shù)應(yīng)用研究逐漸開始流行。

室內(nèi)位置相關(guān)技術(shù)的核心就是室內(nèi)定位，室內(nèi)定位是指利用各種手持設(shè)備基于或者不基于室內(nèi)已知精確位置基礎(chǔ)設(shè)施，推導(dǎo)計算出當(dāng)前設(shè)備在室內(nèi)所處位置。

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

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

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

針對以上情況，提出一個眾包的解決方案，擬利用群體無意識協(xié)作，降低對人力投入的依賴，利用無關(guān)人群手持設(shè)備中安裝的相關(guān)軟件，調(diào)用各種內(nèi)置傳感器采集信號數(shù)據(jù)，在手機(jī)獲得網(wǎng)絡(luò)鏈接時，隨機(jī)地發(fā)送給服務(wù)器，從大量數(shù)據(jù)中提取出室內(nèi)拓?fù)鋱D，并將其應(yīng)用到室內(nèi)定位中。

2 相關(guān)工作

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

現(xiàn)在較先進(jìn)的繪制室內(nèi)地圖和室內(nèi)定位使用的的數(shù)據(jù)很多都是來源于同樣類型的信號數(shù)據(jù)，這些數(shù)據(jù)不僅可以利用到室內(nèi)定位中，也同樣可以利用到室內(nèi)地圖的構(gòu)建繪制中。

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

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

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

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

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

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

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

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

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

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

3 方法設(shè)計

當(dāng)前在做室內(nèi)定位方面，大部分是需要基于已知地圖的，在地圖未知的情況下，進(jìn)行室內(nèi)定位非常艱難，而本研究主旨就是利用WiFi指紋以及其他輔助AP挖掘室內(nèi)拓?fù)浣Y(jié)構(gòu)、構(gòu)建室內(nèi)地圖，為進(jìn)一步室內(nèi)定位提供基礎(chǔ)。

本文提出一種C/S(Client+Server)架構(gòu)的系統(tǒng)來實現(xiàn)室內(nèi)拓?fù)鋱D繪制的方案，基于安卓(Android)系統(tǒng)的客戶端主要負(fù)責(zé)利用手機(jī)內(nèi)自帶的各類傳感器，收集目標(biāo)數(shù)據(jù)并對數(shù)據(jù)進(jìn)行初步處理，將其保存在手機(jī)本地。當(dāng)手機(jī)偶然獲得網(wǎng)絡(luò)訪問的時候，將存儲的數(shù)據(jù)發(fā)送到服務(wù)器上，在服務(wù)器上，對采集到的數(shù)據(jù)進(jìn)行聚類分析等后續(xù)處理，并挖掘出室內(nèi)拓?fù)浣Y(jié)構(gòu)，繪制室內(nèi)地圖。

圖1 系統(tǒng)結(jié)構(gòu)圖

3.1 客戶端設(shè)計

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

以下介紹使用的室內(nèi)地理信息特征點。

3.1.1 WiFi-MARK

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

圖2 WiFi空間信號強(qiáng)度示意圖

由于WiFi傳播信號如圖2，在三維空間中WiFi信號強(qiáng)度相同的空間可以構(gòu)成一個球面，而對于水平的樓層來說則是一個圓，行走過程的軌跡相當(dāng)于是“等WiFi強(qiáng)度”圓形區(qū)域的一條割線，根據(jù)幾何知識可知，在這條割線的正中間是WiFi信號最強(qiáng)的點，如圖3所示，在采集數(shù)據(jù)的時候?qū)⑵溆涗浵聛?，作為一個WiFi標(biāo)記，稱作WiFi-PEAK。WiFi-PEAK記錄格式為：

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

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

圖3 WiFi信號強(qiáng)度變化

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

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

3.1.2 電梯樓梯

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

圖4 電梯、樓梯和正常行走時的重力讀數(shù)區(qū)別

3.1.3 轉(zhuǎn)彎點

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

CP={bDirection，aDirection，pPosition}；

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

3.1.4 門

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

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

3.1.5 室內(nèi)靜止點

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

3.2 服務(wù)器端設(shè)計

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

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

4 系統(tǒng)實現(xiàn)

針對上一節(jié)定義的需要采集的點，設(shè)計出的客戶端核心代碼結(jié)構(gòu)如下：

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)；//得到轉(zhuǎn)彎點

if(threshold0

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

}

if(statictime>threshold3)

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

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

write(elevator)；

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

Write(stair)；

}

將采集到的點存儲在移動終端本地，當(dāng)獲得網(wǎng)絡(luò)的時候隨機(jī)將數(shù)據(jù)文件發(fā)送到服務(wù)器端，服務(wù)器接收到數(shù)據(jù)之后，將接收到的數(shù)據(jù)進(jìn)行聚類，并多次迭代。聚類的相關(guān)偽碼如下：

Algorithm2 Anchor points clustering

//數(shù)據(jù)讀取

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')；//轉(zhuǎn)彎點

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

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

//擬合處理

polyfit(line.x，line.y)；

根據(jù)以上系統(tǒng)實現(xiàn)，將客戶端安裝在不同型號的手機(jī)上(MEIZU MX，MEIZU MX3，SAMSUNG NOTE2，htc one)并在北京郵電大學(xué)明光樓內(nèi)采集數(shù)據(jù)，得到結(jié)果如下圖：

圖5 數(shù)據(jù)分類聚類以及擬合直線

與明光樓的室內(nèi)實際圖對比如下：

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

圖6 走廊圖放在實際地圖內(nèi)

5 結(jié)束語

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

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

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

[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的室內(nèi)定位技術(shù)評述[J].傳感器與微系統(tǒng)，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.