陳立建,楊志凱,施偉元,鄔錦彬,毛科技*,王萬良

(1.浙江工業(yè)大學計算機科學與技術(shù)學院,杭州 310023;2.浙江廣播電視大學蕭山學院,杭州 311201)

近年來,隨著移動網(wǎng)絡與智能終端的普及,室內(nèi)導航系統(tǒng)在一些特定場合的實用性和必要性已經(jīng)日益顯著,其應用前景廣闊,研究意義非常大。例如在大型商場中的智能導購;在陌生的辦公樓里尋找會議室;在龐大的停車場尋找停泊的位置等。全球定位系統(tǒng)GPS(Global Positioning System)被廣泛應用于室外導航系統(tǒng),然而由于信號衰減以及多徑效應的影響,該系統(tǒng)只能工作在戶外開闊地帶,無法實現(xiàn)室內(nèi)復雜環(huán)境下的可靠定位[1]。早期對室內(nèi)定位系統(tǒng)的研究大部分基于紅外線、超聲波、激光測距和射頻無線標簽等[2]。這些定位系統(tǒng)雖然可以達到理想的定位精度,但是它們的定位范圍較小,并且需要特定設(shè)備來獲取信號,在日常生活中并不實用。因此,設(shè)計一種精確可靠,實時性高的室內(nèi)導航方式來滿足人們?nèi)找嬖鲩L的室內(nèi)定位服務需求具有重要意義。

針對上述問題,本文提出了一種基于地磁指紋的眾包室內(nèi)導航方法。本導航系統(tǒng)充分利用了建筑物內(nèi)地磁場局部異常且長期穩(wěn)定的特點,借助眾包思想讓用戶參與到指紋地圖數(shù)據(jù)庫構(gòu)建工作中,通過基于動態(tài)時間規(guī)整DTW(Dynamic Time Warping)的地磁指紋匹配算法實現(xiàn)定位并導航。

1 相關(guān)工作

基于WiFi的室內(nèi)定位系統(tǒng)通過將待定位目標的位置指紋特征與位置指紋數(shù)據(jù)庫進行匹配來獲得目標的位置,這種方法也稱為“位置指紋法”[3]。相關(guān)研究成果如陳斌濤[4]等人設(shè)計并實現(xiàn)的一種基于WiFi射頻信號強度指紋的室內(nèi)定位方法,該方法有效降低了在實際使用過程中用戶手持手機的方向、用戶的身體遮擋以及使用環(huán)境的動態(tài)變化對RSSI值所帶來的影響。文獻[5]基于RSSI指紋信息,同時在構(gòu)建位置指紋地圖時加以考慮普通用戶的運動軌跡,在保障定位精度的同時減少了約三分之二構(gòu)建指紋地圖的工作量。與基于WiFi的室內(nèi)定位導航相類似的還有基于藍牙的室內(nèi)定位系統(tǒng)[6]。然而,基于WiFi和藍牙的室內(nèi)定位方法也存在著缺陷,最明顯的一點就是它們都非常依賴無線基礎(chǔ)設(shè)施,需要安裝大量昂貴的無線基站(無線AP及藍牙基站),對于那些還未架設(shè)無線基礎(chǔ)設(shè)施的場景便束手無策。無線基站的數(shù)量及分布也對定位有著重要影響。假如定位基站節(jié)點失效,那么用戶設(shè)備所采集到的指紋數(shù)據(jù)將無法與數(shù)據(jù)庫中的指紋數(shù)據(jù)進行成功匹配,最終導致無效的定位結(jié)果。同時,兩者的信號在室內(nèi)都容易受到人體、障礙物等影響從而導致信號強度嚴重衰減。

相比于WiFi和藍牙信號,地磁信號同樣易于獲取。有研究表明,自然界中許多動物如海龜、龍蝦等能夠利用磁場辨別方向和感知位置[7],進而完成遷徙。事實上,地球表面大量的含鐵物質(zhì)、礦物等的存在使得磁場產(chǎn)生了異常,正是這些局部異常的地磁場為這些動物指引航向。在建筑物內(nèi),建筑物本身的鋼筋混凝土,電子設(shè)備,電梯等都會對附近的磁場產(chǎn)生影響[8],產(chǎn)生局部的“磁異?！?形成一種與位置相關(guān)、長期穩(wěn)定且無處不在的特殊信號。這些地磁異常信號能夠提供位置指紋信息。Akia[9]、Emter[10]、Lau[11]、Vallivaara[12]等人成功地在智能機器人、智能小車上利用地磁異常進行定位導航。因此,研究人員逐漸將研究目標投向易于獲取并且更加穩(wěn)定且無處不在的地磁信號。

利用地磁信號作為位置指紋信息進行定位最開始用于機器人自定位[13]。芬蘭Oulu大學的Haverinen[12]等人設(shè)計了一種基于地磁信號以及粒子濾波的室內(nèi)導航系統(tǒng),并成功應用于機器人的室內(nèi)導航。然而他們的系統(tǒng)最初只能在一維空間(如礦道)定位并且需要事先采集大量用于匹配的地磁數(shù)據(jù)。Gozick[14]等人在他們的研究中描述了如何利用室內(nèi)地磁信息的獨特性構(gòu)建路標進而區(qū)分不同的教室、實驗室、走廊等。并且進行了大量的實驗,分析了柱子的尺寸、不同形狀材質(zhì)的柱子以及設(shè)備與柱子之間的距離對地磁數(shù)據(jù)的干擾程度。Lau[11]等人通過對海龜利用地磁進行導航這一現(xiàn)象進行深入研究及仿效,利用高斯混合模型對矢量磁場進行建模,并采用直接似然法獲取估計位置,同時利用這些估計位置作為“偽訓練數(shù)據(jù)”提高高斯混合模型的回歸效率。該算法在智能小車上成功地進行了實驗,取得了較好的定位精度。文獻[15]利用慣性導航技術(shù)進行了相對定位獲得移動載體的三維空間中的相對位置,使用地磁匹配算法MSD進行絕對定位,并給予Android平臺實現(xiàn)了該室內(nèi)導航系統(tǒng)。

現(xiàn)階段對于基于地磁信號的室內(nèi)定位導航系統(tǒng)的研究存在著不少缺陷:粒子濾波在基于地磁信號的室內(nèi)定位導航系統(tǒng)中一種常用的算法,但它容易被行為模型誤差所影響,導致定位誤差較大且容易失效;基于高斯混合模型及似然估計方法的室內(nèi)定位系統(tǒng)計算開銷大、回歸效率較低,導航的實時性并不好;構(gòu)建地磁指紋數(shù)據(jù)庫是一件非常耗費人力物力的任務,現(xiàn)有的系統(tǒng)并沒有解決繁雜的地磁指紋數(shù)據(jù)的構(gòu)建工作。文獻[16]設(shè)計了一種室內(nèi)實時定位系統(tǒng),該系統(tǒng)基于多指紋地磁信息,充分借助手機慣性傳感器及地磁傳感器,通過最小方根尋找測試點與地磁數(shù)據(jù)庫相似度最高的點來校正航位推算結(jié)果,進而得到準確地位置,同樣的,根據(jù)最小均方根計算兩個地磁序列之間的相似度會存在一定的誤差,無法處理長度不一的序列。文獻[17]提出了即插即用的導航模型FOLLOWME,雖然看似簡化了建立地磁指紋的工作量,但該系統(tǒng)只能從規(guī)定的起點到達指定的目的地,如果導航過程出錯,只能退回原點,并且不能識別重復路徑,缺少靈活性。文獻[18]中提到的自我系統(tǒng),借助于影像識別,可以識別簡單的重復路徑,但影像識別需要較大的存儲空間,而且受環(huán)境變化的影響非常大,當人較多時可能導致系統(tǒng)無法工作。

本文針對以上缺陷設(shè)計了一種基于地磁指紋的眾包室內(nèi)導航系統(tǒng):①將眾包思想應用于地磁指紋數(shù)據(jù)庫的構(gòu)建,極大的減小了構(gòu)建數(shù)據(jù)庫的工作量;②設(shè)計了一種基于方向傳感器的轉(zhuǎn)角檢測算法;③將動態(tài)時間規(guī)整算法應用于重疊路徑的識別以及地磁指紋匹配算法中來,能有效解決不同長度的地磁時間序列的匹配問題;④在定位導航過程中,利用磁場干擾明顯的區(qū)域以及轉(zhuǎn)角處作為特征點來對當前導航結(jié)果進行校準。

2 系統(tǒng)設(shè)計

本系統(tǒng)的整體模塊設(shè)計如圖1所示,按照不同的功能可以將整個系統(tǒng)分為兩個部分,包括地磁指紋地圖構(gòu)建模塊以及定位導航模塊。

圖1 系統(tǒng)整體模塊圖

2.1 指紋地圖構(gòu)建

利用地磁數(shù)據(jù)進行定位的精確非常依賴于地磁指紋數(shù)據(jù)庫的有效性和準確性,因此本文對如何有效地構(gòu)建準確可靠的地磁指紋數(shù)據(jù)庫進行了深入研究。

首先將地磁指紋地圖看作是由若干給定的點及連接兩點的線所構(gòu)成的無向圖(任意一個點的地磁強度不受手機水平朝向的影響)。因此,某一個建筑物內(nèi)一個樓層的地磁指紋地圖可以表示為Mi=。其中Vi是非空集合,稱為頂點集;Ei是Vi中元素構(gòu)成的無序二元組的集合,稱為邊集。無向圖中的頂點集Vi實際就是建筑物中的轉(zhuǎn)角,而邊集Ei則代表了走廊。

構(gòu)建地磁指紋數(shù)據(jù)庫的工作即通過調(diào)用智能手機豐富的傳感器設(shè)備,來識別并記錄各個轉(zhuǎn)角及各條走廊,并采集相應位置實時的地磁時間序列。但在建筑物內(nèi),由一個位置到另一個位置會有多條可行的路徑,如圖2所示,由A至B可以是AECDFB或者AEFB等。當有兩個不同的地圖構(gòu)建人員分別在這兩條路徑采集了數(shù)據(jù)并上傳至服務器之后,服務器端如何識別出多條路徑的重疊部分(如AE、FB),區(qū)分它們的不同,并采集到的不同路徑匹配成為完整的地磁指紋地圖,這也是需要解決的問題之一。

本文采用DTW算法來判斷所采集路徑的重疊部分,并以眾包方式構(gòu)建地磁指紋地圖;同時采取了一系列措施來保證實時數(shù)據(jù)的穩(wěn)定性。

圖2 多路徑示意圖

2.2 定位導航

當用戶進入一棟已經(jīng)完成地磁指紋地圖構(gòu)建工作的建筑物內(nèi),并需要導航服務內(nèi),系統(tǒng)將從服務器端下載相應的地磁指紋地圖。在導航開始之前,用戶首先需要設(shè)定到達的目的地。接著,用戶只需要手持智能手機(手機朝向?qū)?shù)據(jù)的影響如圖3(a)、(b)、(c)所示,為防止手機朝向變化對數(shù)據(jù)采集造成額外的影響,系統(tǒng)在運行時需要用戶保持手機朝向的固定),沿當前路徑勻速行走時,系統(tǒng)會持續(xù)為用戶提供到達目的地相應的路徑信息,直到導航結(jié)束。

bc中黑線順序相反

在定位導航過程中,用戶的智能手機采集到的連續(xù)地磁數(shù)據(jù)是一種時間序列,基于地磁信號的指紋匹配問題實質(zhì)就是一種時間子序列匹配問題。由于每個人的行走習慣、行走速度不同,用戶所采集到的地磁時間序列與地磁指紋地圖中相對應的子序列存在長度上的差異,無法直接使用歐式距離、曼哈頓距離或者是相關(guān)系數(shù)等常用的相似性度量方法來衡量兩個地磁時間序列之間的相似度。為了解決這一問題,本系統(tǒng)采用了動態(tài)時間規(guī)整算法[19]。動態(tài)時間規(guī)整算法是一種衡量兩個長度不同的時間序列相識度的方法,主要應用在語音識別領(lǐng)域來識別兩端語音是否表示同一個單詞。該算法通過把時間序列進行延伸和收縮,從而實現(xiàn)兩個時間序列之間的相似性的度量。

因此,系統(tǒng)在定位導航過程中只需要將用戶的智能手機所采集到的一定長度(約2 s)的地磁時間子序列與地磁指紋數(shù)據(jù)庫中的參考序列進行遍歷匹配,計算得到參考序列中動態(tài)時間規(guī)整距離最小(即相似度最高)的子序列,并將該子序列轉(zhuǎn)換為相應的地圖坐標即可完成定位。同時系統(tǒng)充分考慮地磁時間子序列的相關(guān)特征,如最大最小值、極值點、變化趨勢等來篩選地磁指紋數(shù)據(jù)庫中的待匹配序列,從未縮小匹配時間、提高匹配的準確率、增強系統(tǒng)的實時性,并且將地磁指紋地圖中地磁干擾嚴重的點作為地磁指紋地圖的“特征點”。這些“特征點”更容易被檢測出來,因此,本文利用這些“特征點”作為“路標”,來對定位導航結(jié)果進行校正。

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

3.1 多傳感器協(xié)同工作

本文提到的導航系統(tǒng)在智能手機上實現(xiàn),利用了其自帶的各種傳感器,如地磁傳感器、氣壓傳感器、方向傳感器。

簡單來說,地磁傳感器記錄地磁數(shù)據(jù)、轉(zhuǎn)向角傳感器記錄轉(zhuǎn)過的角度、氣壓傳感器檢測用戶當前所處環(huán)境中樓層高度的變化而判斷其是否有上下的行為。值得一提的是,當用戶在戶外有GPS信號時,手機后臺會記錄用戶的平均行走速度,當用戶進入室內(nèi)時,可以使用所記錄的行走速度來計算到達目的地所需時間、當前已行走距離等,本文將根據(jù)這些數(shù)據(jù)對用戶的位置進行校準。這些輔助數(shù)據(jù)能夠為定位結(jié)果的校準工作提供幫助。

在智能手機中,傳感器又可以分為基于硬件和基于軟件的?；谟布崿F(xiàn)的傳感器大部分都是采用物理組件,它們往往通過去測量物理世界中的環(huán)境屬性來獲取數(shù)據(jù),如加速度傳感器、地磁傳感器、氣壓傳感器等。另一方面,基于軟件的傳感器不是依靠物理組件,實質(zhì)上是通過一個或更多的硬件傳感器來獲取數(shù)據(jù),如方向傳感器,實質(zhì)上是加速度傳感器加地磁傳感器。

3.1.1 地磁傳感器

地磁場是地球的基本物理場,地球近地空間內(nèi)任意一點都具有磁場強度,且其強度和方向會因經(jīng)度和高度的不同而不同。地磁場有著豐富的參數(shù)信息,如地磁總場、地磁三分量、磁傾角、磁偏角和地磁場梯度等[20]。手機內(nèi)置的三軸地磁傳感器能夠直接讀取地磁三分量的值[21],即相對于設(shè)備坐標系在X、Y、Z3個方向上的地磁值。在研究中發(fā)現(xiàn)當用戶沿著同一條路不同方向行走時,地磁三分量的值在同一地點的差異明顯,而它們的合強度幾乎相同,如圖3所示,因此,本文選擇地磁合強度作為位置指紋信息。

需要注意的是,在獲取正確地磁數(shù)據(jù)前需要校準,通常可用“8字校準法”?！?字校準法”要求用戶使用需要校準的設(shè)備在空中做8字晃動,原則上盡量多的讓設(shè)備法線方向指向空間的所有8個象限即可。

3.1.2 氣壓傳感器

氣壓傳感器也是一種硬件傳感器,它能夠測量出用戶當前所處環(huán)境的大氣壓強(單位為hPa,百帕斯卡),進而根據(jù)氣壓值計算公式計算出當前位置的海拔高度。然而,氣壓傳感器測得大氣壓強容易受到外界環(huán)境(溫度、風速、天氣等)及時間的影響導致計算得到的海拔高度存在一定的誤差,為此,本文根據(jù)一定時間內(nèi)氣壓傳感器測得的壓強差與事先設(shè)定的閾值進行對比,進而判斷用戶是否有上樓行為,樓層變化對氣壓值的影響如圖4所示。

圖4 氣壓值隨著樓層變化而變化

3.1.3 方向傳感器

方向傳感器是一種典型的軟件傳感器,它的數(shù)據(jù)是通過加速度傳感器和地磁傳感器共同獲得的。方向傳感器返回的數(shù)據(jù)包含X、Y、Z3個方向的值[22],包括指向地心的方位角、俯仰角以及翻轉(zhuǎn)角。本文中利用了指向地心的方位角來成檢測轉(zhuǎn)角以及其對應的角度。為了避免手機的不同姿態(tài)對采集到的數(shù)據(jù)造成差異,本文默認手機保持水平朝向。本系統(tǒng)中利用方向傳感器在數(shù)據(jù)采集模塊中制作了一個水平儀,使得用戶在數(shù)據(jù)采集過程中能夠更加直觀地了解當前手機的姿態(tài),方便其校正手機朝向。

3.2 地磁指紋地圖構(gòu)建模塊

地磁指紋地圖的構(gòu)建工作往往非常繁瑣,需要耗費大量的人力、精力。隨著智能手機的廣泛普及以及“眾包”[23]概念的深入人心,這一難題也就迎刃而解。

在3.1節(jié)中,本文中提到的指紋地圖可看作是由若干點和連接兩點的線所構(gòu)成的無向圖,因此,地圖構(gòu)建工作就能夠分解為兩個關(guān)鍵部分:利用用戶采集的方向傳感器的數(shù)據(jù)識別轉(zhuǎn)角,也是無向圖中的點;識別出轉(zhuǎn)角,那么兩個轉(zhuǎn)角之間便是一條完整的走廊,對應無向圖中的邊,記錄走廊的地磁數(shù)據(jù),同時利用地磁數(shù)據(jù)來判斷不同用戶所采集的數(shù)據(jù)中的路徑重疊部分,并將不同的部分拼接起來最終形成完整的地磁指紋地圖。

3.2.1 數(shù)據(jù)采集處理

為保證采集數(shù)據(jù)的可靠及準確,系統(tǒng)在數(shù)據(jù)采集過程中首先利用“8字法”對手機內(nèi)的傳感器進行校準。其次,對傳感器數(shù)據(jù)進行了濾波處理。地磁傳感器和氣壓傳感器的數(shù)據(jù)變化比較平穩(wěn),使用低通濾波算法(如式(1)所示)對數(shù)據(jù)進行平滑去噪處理。

datai=datai-1(1-α)+newData·α

(1)

式中:newData為當前讀取到的數(shù)據(jù),datai-1為上一次從傳感器獲取的數(shù)據(jù),datai為本次傳感器讀取結(jié)果,α為濾波系數(shù),本文中取α=0.1。

另外,本文使用限幅濾波算法去除方向傳感器由于偶然因素引起的跳變干擾,限幅濾波算法如式(2)所示。

(2)

式中:newData為當前采樣值,datai-1為上一次從傳感器采樣獲取的結(jié)果,datai為本次傳感器讀取結(jié)果,ε為限幅系數(shù),本文中取ε=20,即方向傳感器兩次采樣之間最大偏差不超過20°。

在數(shù)據(jù)采集過程中,用戶的手機朝向水平固定。記錄每個采樣時間點ti對應的地磁強度mi(xi,yi,zi)并根據(jù)式(3)計算該點地磁合強度,并進一步計算出氣壓強度pi以及當前手機指向的方位角di。本文中默認的數(shù)據(jù)采樣頻率為5 Hz。為了使數(shù)據(jù)更加平滑精細,系統(tǒng)對采樣的數(shù)據(jù)進行插值處理(三樣條插值算法),將數(shù)據(jù)精度調(diào)整至0.1 s對應 10 Hz 的采樣頻率。以地磁傳感器為例,圖5展示了采集到的原始地磁數(shù)據(jù)經(jīng)由低通濾波算法及插值算法處理的效果。

(3)

對于每一個傳感器數(shù)據(jù),本文中都給它增加了一個時間戳,這是為后面地磁指紋匹配算法做準備。

3種傳感器所采集的數(shù)據(jù)格式如表1所示。

表1 傳感器原始數(shù)據(jù)格式

3.2.2 轉(zhuǎn)角識別

在本小節(jié)將詳細闡述如何利用方向傳感器所采集的數(shù)據(jù)檢測轉(zhuǎn)角并計算其對應的角度。

如圖6(a)所示,該數(shù)據(jù)采集地點為浙江工業(yè)大學屏峰校區(qū)廣知C樓4樓(樓層平面圖如圖7所示),數(shù)據(jù)采集路徑為S-a-b-c-d-e-f-D),圖中橫坐標表示時間,縱坐標表示所采集到的方位角。圖7中用戶每一次轉(zhuǎn)彎,都能在圖6(a)中很直觀地區(qū)分出來。然而,由于圖6(a)一個波峰或者波谷表示方位角發(fā)生了兩次改變(兩個轉(zhuǎn)角),這并不利于系統(tǒng)用算法對其進行識別。為此,系統(tǒng)首先計算前后兩次方位角的差值,并對該角度進行限幅濾波(濾波的閾值為20°)處理,其圖像如圖6(b)所示。然后,設(shè)置一個長度為2 s的滑動窗口,計算滑動窗口內(nèi)角度差之和即計算當前滑動窗口內(nèi)累積的角度變化,得到如圖6(c)所示的圖像。最后,只需要識別出在一定閾值范圍內(nèi)(本文中認為超過30度為一次有效的轉(zhuǎn)彎)的波峰及波谷,就成功識別出了轉(zhuǎn)角。算法的執(zhí)行步驟如表2所示。并且,從中能夠獲取更多信息:波峰即代表一次右轉(zhuǎn),波谷及代表一次左轉(zhuǎn),波峰或波谷的值即代表的該轉(zhuǎn)角的角度。

圖7 樓層平面圖

圖6 轉(zhuǎn)角識別

表2 轉(zhuǎn)角識別算法

3.2.3 地圖拼接與動態(tài)時間規(guī)整(DTW)算法

假設(shè)某天有用戶A來到圖7所示樓層,并決定貢獻自己的力量為該樓層采集地磁指紋信息。他手持智能手機,沿著S-a-b-c-d-e-f-D的路線完成了數(shù)據(jù)采集,并將數(shù)據(jù)上傳至服務端。服務端將采集結(jié)果顯示在地圖上,由用戶A進行再次確認。另一天,又有一名用戶B來到該樓層,當他打開APP發(fā)現(xiàn)該樓層的地磁指紋地圖完成了大半部分,便決定完成一小部分的地圖構(gòu)建工作。于是,他便手持智能手機,沿著另外一條路徑S-a-b′-c′-d-e-f-D采集了地磁數(shù)據(jù),同樣地用戶B也將其采集的數(shù)據(jù)上傳至服務器端并完成了確認。此時,本系統(tǒng)只需要設(shè)法在用戶A和用戶B所采集的數(shù)據(jù)中,區(qū)分出路徑的重疊部分,并將不同部分(a-b-c-d和a-b′-c′-d)進行拼接,就能夠完成該樓層的地磁指紋地圖構(gòu)建工作。

在構(gòu)建地圖過程中,系統(tǒng)需要對傳感器采集到的地磁原始數(shù)據(jù)進行處理。除了轉(zhuǎn)角檢測外,還需要將地磁強度和大氣壓強度按照時間先后組成相應的時間序列,并在地磁時間序列中加入相應的地圖坐標信息,從而將地磁指紋信息與地圖形成映射,其格式如表3所示。

表3 時間序列格式

在同一路徑采集的地磁時間序列往往形狀相似,但是由于用戶行走速度以及行走習慣的不同,導致地磁時間序列之間存在長度上的差異(如圖8(b)所示),因此無法直接用歐式距離、曼哈頓距離或者是相關(guān)系數(shù)等常用的相似性度量方法來衡量兩個地磁時間序列之間的相似度。為了解決這一問題,本文中采用了動態(tài)時間規(guī)整算法。動態(tài)時間規(guī)整算法是一種衡量兩個長度不同的時間序列相似度的方法。給定兩個時間序列X=x1,x2,…,xm和Y=y1,y2,…,yn,它的遞推計算公式如式(4)所示,當兩條地磁時間序列的DTW距離小于閾值σdtw時,系統(tǒng)便認為它們表示同一段路徑。

圖8 手機不同朝向及相同路徑下不同速度下產(chǎn)生的地磁時間序列

(4)

3.2.4 眾包激勵機制

對于參與地圖構(gòu)建的用戶,當后臺人員確認其上傳的數(shù)據(jù)是有效的,可以給予一定的獎勵,如商場折扣卷、抽獎機會等,以此激勵更多的用戶參與到地圖構(gòu)建當中。

3.3 定位與指紋匹配算法

當?shù)卮诺貓D構(gòu)建完成后,用戶便能夠利用地磁指紋數(shù)據(jù)庫及智能手機實現(xiàn)定位導航。在定位過程中,用戶手持智能手機,并且為了得到更加精確的定位結(jié)果,應盡量使手機保持水平朝向。

3.3.1 基于DTW的指紋匹配算法

在定位過程中,本系統(tǒng)設(shè)置了一個隊列用來保存待匹配的地磁時間子序列,一個校正數(shù)據(jù)緩沖區(qū)用來對定位結(jié)果進行校正,保存兩個轉(zhuǎn)角之間完整的地磁時間序列,每當檢測到一個新的轉(zhuǎn)角時將其清空。這里需要說明的是,地磁時間子序列長度會影響匹配時間及定位誤差,待匹配的地磁時間子序列越長,定位精度相對也越高,但是相對的匹配時間越久實時性越低,反之則相反。為此,本文中設(shè)置待匹配地磁子序列的長度為2 s。

定位開始,系統(tǒng)會有一個“預熱”階段。此時,程序后臺會不斷采集當前用戶周圍的地磁信息,同時將三軸地磁數(shù)據(jù)根據(jù)式(3)轉(zhuǎn)換為地磁合強度。在采集到長度為2 s的待匹配地磁子序列后,使用三樣條插值算法對該序列進行插值處理。同時,從地磁指紋數(shù)據(jù)庫中取出參考序列,利用滑動窗口技術(shù),計算窗口內(nèi)參考子序列與待匹配地磁時間子序列的動態(tài)時間規(guī)整距離。最后,找出與待匹配地磁時間子序列相似度最高,即動態(tài)時間規(guī)整距離最小的地磁序列,并將該序列的終點映射為相應地圖坐標,那么該坐標即為定位結(jié)果。算法的具體步驟如表4所示。

表4 地磁指紋算法

3.3.2 定位校正

直接根據(jù)指紋匹配算法得到的結(jié)果存在6 m左右的平均誤差(子序列長度設(shè)置為2 s時),仍然有很大的改進空間,為此,根據(jù)室內(nèi)地磁信號,本文設(shè)計了一套定位校正方案。

首先,建筑物內(nèi)每條走廊上都或多或少存在著強磁異常點,也就是地磁干擾較強的點,這些點直觀地顯示在圖像中往往就是波峰或者波谷,將這些點看作是“特征點”從而當用戶經(jīng)過這些點時,就能獲得置信度非常高的定位結(jié)果。

其次,利用建筑物內(nèi)的轉(zhuǎn)角及設(shè)置的校正數(shù)據(jù)緩沖區(qū)也能夠被用來對定位結(jié)果進行校正。由于方向傳感器測得的角度較為準確,該算法也能夠準確地識別出用戶的每一次轉(zhuǎn)向,并且每個轉(zhuǎn)角都會有轉(zhuǎn)向、角度信息,這些信息均能夠縮小定位范圍:例如當用戶沿著圖7中的起點S開始行走,當他走到分叉點a時選擇了右轉(zhuǎn),此時通過本文中的轉(zhuǎn)角檢測算法就能判斷該用戶轉(zhuǎn)動的方向及對應的角度,此時將校正數(shù)據(jù)緩沖區(qū)的地磁數(shù)據(jù)與各條走廊的參考序列進行DTW匹配就能識別出用戶上一段走過的路徑為S-a,在a點向右轉(zhuǎn)向了90度,進而判斷用戶將沿a-b繼續(xù)行走而非a-b′。

3.3.3 樓層識別

在第2章中已經(jīng)對氣壓傳感器進行了簡單的介紹,本小節(jié)將詳細介紹如何利用氣壓傳感器來判斷用戶是否有上下樓行為。

大氣壓強在一天內(nèi)會隨著時間的改變而變化(1 hPa～3 hPa),在同一個地點早、中、晚的大氣壓強也會有所差異,但是在短時間內(nèi)不會有大明顯的波動。并且,當所處海拔越高,大氣壓強也就越小;反之,所處海拔越低,那么大氣壓強也就會越大。同時,用戶上下樓時,局部氣壓變化并不會太明顯,因此,系統(tǒng)通過觀察氣壓傳感器讀取的大氣壓強的變化,來斷定用戶是上樓還是下樓,甚至是乘坐電梯。

圖9 樓層變化引起的氣壓值變化

圖9中記錄了用戶從教學樓四樓行走至三樓(AB段),在三樓處理了一些工作稍作停留后(BC段)便回到了四樓(CD段),大約0.5 min后又行走至五樓(EF段),這期間的手機氣壓傳感器數(shù)值的變化情況。從圖中可以很清楚地看到樓層變化對于氣壓值的影響,同時也符合海拔變化對于氣壓值的影響規(guī)律。

為了檢測樓層的變化,首先需要對采集到的氣壓數(shù)據(jù)進行低通濾波平滑處理。緊接著,如果當前讀取到的氣壓值為pn,那么尋找在前Ts內(nèi)(本文默認為20 s)與該氣壓值差值最大的點,假設(shè)該點的氣壓值為pm。計算兩者的差值的絕對值|pn-pm|,如果該差值大于氣壓閾值(本文設(shè)定為0.4 hPa),便可以判斷用戶上樓或者下樓的行為以及其上下樓具體的樓層數(shù)。當然,由于每個建筑物的樓層高度不同,室內(nèi)環(huán)境也大不相同,因此,前面提到的閾值及有效時間需要根據(jù)具體建筑具體分析再進行設(shè)定。

本文中還借助加速度傳感器對用戶行走步伐進行檢測,假如檢測到用戶有上下樓的行為而行走的步數(shù)較少(在一定閾值內(nèi),如只走了10步但是樓層數(shù)變化了一層),那么系統(tǒng)就可以認為該用戶乘坐了電梯等其他工作。

3.4 導航模塊

在導航之前,用戶需要手動選定目的地。然后,系統(tǒng)將當前定位結(jié)果作為起點,用戶所選的目的地作為終點。在構(gòu)建地磁地圖時將整個地磁地圖看作是一個以轉(zhuǎn)角為點,兩個轉(zhuǎn)角之間的走廊為邊的無向圖,其每條邊的權(quán)值即為對應地磁時間序列的長度(即時間),因此系統(tǒng)中直接能夠使用最短路徑算法Dijkstra規(guī)劃導航路徑[24],并將規(guī)劃結(jié)果在智能手機端顯示以及給出相應提示。

圖10 數(shù)據(jù)采集及數(shù)據(jù)檢測模塊

本文提出的室內(nèi)導航系統(tǒng)在Google Nexus5(安卓版本 4.4.4)智能手機上實現(xiàn),demo程序截圖如圖10、圖11 所示。

其中:圖10(a)為數(shù)據(jù)采集模塊。在數(shù)據(jù)采集模塊中,大氣壓強、地磁強度、手機方向以及水平儀等信息實時顯示在屏幕上,地圖構(gòu)建者能夠選擇系統(tǒng)根據(jù)其行走習慣設(shè)定的默認采樣頻率,同時也能夠自己設(shè)定采樣頻率。同時,地圖構(gòu)建者需要為每次采集的數(shù)據(jù)添加標簽以區(qū)分不同的路徑。在采集數(shù)據(jù)時,地圖構(gòu)建者只需要按下“START”按鈕,勻速沿采集路徑行走,并盡量保持水平儀上的紅點在十字的中心即可,當采集完成時再按下按鈕即可。

圖10(b)為數(shù)據(jù)檢測模塊,用來幫助地圖構(gòu)建者更好地觀測當前環(huán)境中地磁變化,方便其發(fā)現(xiàn)地磁異常點。

定位導航模塊如圖11(a)、11(b)所示,僅對用戶進行了定位,尚未啟動導航功能。藍色箭頭即表示用戶當前位置,箭頭朝向即當前用戶手機的朝向(利用了方向傳感器的方位角實現(xiàn))。當用戶需要使用導航功能時,只需要在文本框中輸入需要導航的位置,如417房間,然后按下文本框側(cè)面的開始按鈕,那么程序就會啟動導航,如圖11(b)所示。

圖11 定位導航模塊

4 實驗及系統(tǒng)評估

本文的實驗在6層高的校園辦公樓中進行,每個樓層面積大概700 m2左右(10 m×70 m)。這是兩幢“回”型大樓連接而成的建筑,連廊處于半開放狀態(tài)。實驗環(huán)境平面示意圖如圖7所示。為了評估導航性能,建立了第4層樓的整個磁場地圖,實驗一共有3個志愿者幫助采集數(shù)據(jù)并完成導航系統(tǒng)的測試任務。

4.1 參數(shù)測試

首先利用志愿者采集的樓層地磁數(shù)據(jù)探究地磁指紋匹配算法中的地磁數(shù)據(jù)隊列MagDeq長度l與定位誤差(未校正)以及耗時之間的關(guān)系,并確定合適的隊列長度。在實驗中,設(shè)置隊列的長度l由1 s逐漸增長至5 s,并記錄匹配誤差以及每次匹配所消耗的時間,實驗如圖12所示,圖12(a)顯示了序列長度與誤差之間的關(guān)系,圖12(b)為誤差的累計分布函數(shù),圖12(c)顯示了序列長度與耗時之間的關(guān)系。從圖12(a)、12(c)中,能很直觀的看出來,隨著序列長度的增加定位誤差逐漸下降而耗時逐漸上升。綜合考慮導航系統(tǒng)的精度以及定位的實時性,本文將地磁數(shù)據(jù)隊列的長度l設(shè)置為2 s。

圖12 待匹配子序列長度與定位誤差和耗時的關(guān)系

4.2 導航性能

首先讓4個志愿者分別將手機置于胸前,按照自己的行走習慣沿相同路徑,如圖7中所示S-a-b-c-d-e-f-D完成一次導航測試,表5記錄了四名用戶在不同路段各自的行走誤差以及平均誤差(單位:m)。這說明地磁地圖導航效果穩(wěn)定,對不同行走習慣的用戶影響基本一致。同時,從表5中能夠看出,較長的路徑對應了較大的誤差(如bc段和fD端)。本文認為這是由于路徑較長時,對應的參考地磁序列中會出現(xiàn)多條極其相似的子序列,從而使地磁指紋匹配算法得出錯誤的結(jié)果,最終導致定位產(chǎn)生誤差。

表5 不同路段的定位誤差

圖13藍色線條部分為四名志愿者測試結(jié)果整體的誤差累積分布函數(shù),從圖13可以看出,有95%左右的跟蹤誤差都在3 m范圍內(nèi),最高的精度達到了1 m。對比未校正前的誤差累計分布函數(shù),能夠直觀地發(fā)現(xiàn)本文中采用的定位校正方案的有效性。

圖13 經(jīng)過校正后的誤差累計分布函數(shù)

4.3 樓層和角度檢測

當志愿者所在樓層發(fā)生變化時,氣壓傳感器的數(shù)據(jù)變化顯著且平穩(wěn),因此本文中提出的樓層識別算法能夠有效監(jiān)測出樓層變化(接近100%)以及對應變化的層數(shù)。

圖14 轉(zhuǎn)角檢測算法的誤差累計分布函數(shù)

另外,志愿者還對轉(zhuǎn)角檢測算法進行了測試。測試樓層的轉(zhuǎn)角均為90°,以此為基準,要求志愿者采集多組轉(zhuǎn)彎的數(shù)據(jù),并且盡量保持每次轉(zhuǎn)動角度為90°。每人采集了約50組轉(zhuǎn)角處方向角變化的數(shù)據(jù),總共約200組數(shù)據(jù)。實驗結(jié)果表明,在總共200組左右的數(shù)據(jù)中,僅有2次未能檢測出轉(zhuǎn)向,成功率接近100%。在所有檢測出轉(zhuǎn)角的結(jié)果中,全部正確地判斷出了用戶的轉(zhuǎn)向。最終對轉(zhuǎn)角誤差的累計分布進行了統(tǒng)計如圖14所示。實驗表明本文采用的轉(zhuǎn)角檢測算法有著出色的效果。

5 結(jié)論

盡管基于WiFi指紋及藍牙指紋的室內(nèi)定位導航系統(tǒng)有著廣泛應用,然而它們均非常依賴昂貴的無線基礎(chǔ)設(shè)施(無線AP及藍牙基站),對于那些沒有安裝無線基礎(chǔ)設(shè)施的建筑便束手無策。同時,兩者的信號在室內(nèi)都容易受到信號衰減、人體干擾等的影響。針對以上問題,本系統(tǒng)利用建筑物內(nèi)局部異常且長期穩(wěn)定的地磁指紋數(shù)據(jù),加入眾包的概念來減輕地磁指紋地圖的構(gòu)建工作,利用基于動態(tài)時間規(guī)整的指紋匹配算法實現(xiàn)定位,同時充分利用了建筑物內(nèi)磁異常較強的點以及轉(zhuǎn)角對定位結(jié)果進行校正,實現(xiàn)了無需網(wǎng)絡基礎(chǔ)設(shè)施、實時性高、定位準確的室內(nèi)定位導航系統(tǒng)。

當然,本系統(tǒng)在獲取數(shù)據(jù)的時候需要用戶保持手機與身體呈90°影響體驗以及準確定位前需要“預熱”過程等缺陷都是在未來工作中需要解決的問題。

參考文獻:

[1] Misra P,Enge P. Global Positioning System:Signals,Measurements and Performance Second Edition[M]. Lincoln,MA:Ganga-Jamuna Press,2006.

[2] Hightower J,Borriello G. Location Systems for Ubiquitous Computing[J]. Computer,2001(8):57-66.

[3] Wu C,Yang Z,Liu Y,et al. WILL:Wireless Indoor Localization without Site Survey[J]. IEEE Transactions on Parallel and Distributed Systems,2013,24(4):839-848.

[4] 陳斌濤,劉任任,陳益強,等. 動態(tài)環(huán)境中的WiFi指紋自適應室內(nèi)定位方法[J]. 傳感技術(shù)學報,2015,28(5):729-738.

[5] Alonazi A,Ma Y,Tafazolli R. Less-Calibration Wi-Fi-Based Indoor Positioning[C]//IEEE International Conference on Communications. IEEE,2015:2733-2738.

[6] Altini M,Brunelli D,Farella E,et al. Bluetooth Indoor Localization with Multiple Neural Networks[C]//Wireless Pervasive Computing(ISWPC),2010 5th IEEE International Symposium on. IEEE,2010:295-300.

[7] Lohmann K J,Lohmann C M F. Sea Turtles,Lobsters,and Oceanic Magnetic Maps[J]. Marine and Freshwater Behaviour and Physiology,2006,39(1):49-64.

[8] Yamazaki K,Kato K,Ono K,et al. The Analysis of Magnetic Disturbance due to Buildings[C]//Magnetics Conference,2003. INTERMAG 2003. IEEE International. IEEE,2003:CR-06.

[9] Akai N,Hoshino S,Inoue K,et al. Monte Carlo Localization Using Magnetic Sensor and LIDAR for Real World Navigation[C]//System Integration(SII),2013 IEEE/SICE International Symposium on. IEEE,2013:682-687.

[10] Emter T,Petereit J. Multi-Sensor Fusion for Localization of a Mobile Robot in Outdoor Environments[C]//Robotics(ISR),2010 41st International Symposium on and 2010 6th German Conference on Robotics(ROBOTIK). VDE,2010:1-6.

[11] Lau T K,Cheuk C,Liu Y H,et al. Turtle-Inspired Localization on Robot[C]//Intelligent Robots and Systems(IROS),2013 IEEE/RSJ International Conference on. IEEE,2013:5950-5955.

[12] Vallivaara I,Haverinen J,Kemppainen A,et al. Simultaneous Localization and Mapping Using Ambient Magnetic Field[C]//Multisensor Fusion and Integration for Intelligent Systems(MFI),2010 IEEE Conference on. IEEE,2010:14-19.

[13] Suksakulchai S,Thongchai S,Wilkes D M,et al. Mobile Robot Localization Using an Electronic Compass for Corridor Environment[C]//Systems,Man,and Cybernetics,2000 IEEE International Conference on. IEEE,2000,5:3354-3359.

[14] Gozick B,Subbu K P,Dantu R,et al. Magnetic Maps for Indoor Navigation[J]. Instrumentation and Measurement,IEEE Transactions on,2011,60(12):3883-3891.

[15] 宋鏢,程磊,周明達,等. 基于慣導輔助地磁的手機室內(nèi)定位系統(tǒng)設(shè)計[J]. 傳感技術(shù)學報,2015,28(8):1249-1254.

[16] 張榮吉. 基于移動設(shè)備多維感知的室內(nèi)定位方法研究[D]. 燕山大學,2013.

[17] Shu Y,Shin K G,He T,et al. Last-Mile Navigation Using Smartphones[C]//Proceedings of the 21st Annual International Conference on Mobile Computing and Networking. ACM,2015:512-524.

[18] Haverinen J,Kemppainen A. Global Indoor Self-Localization Based on the Ambient Magnetic Field[J]. Robotics and Autonomous Systems,2009,57(10):1028-1035.

[19] Müller M. Dynamic Time Warping[J]. Information REtrieval for Music and Motion,2007:69-84.

[20] 龍禮,張合. 三軸地磁傳感器誤差的自適應校正方法[J]. 儀器儀表學報,2013,34(1):161-165.

[21] 陳龍彪,李石堅,潘綱. 智能手機:普適感知與應用[J]. 計算機學報,2015,38(2):423-438.

[22] Atzori L,Dessi T,Popescu V. Indoor Navigation System Using Image and Sensor Data Processing on a Smartphone[C]//Optimization of Electrical and Electronic Equipment(OPTIM),2012 13th International Conference on. IEEE,2012:1158-1163.

[23] Howe J. The Rise of Crowdsourcing[J]. Wired Magazine,2006,14(6):1-4.

[24] 鮑培明. 距離尋優(yōu)中Dijkstra算法的優(yōu)化[J]. 計算機研究與發(fā)展,2001,38(3):307-311.