基于機(jī)會(huì)性位置校正的低功耗城市眾包導(dǎo)航

穆運(yùn)峰，王 林，劉文遠(yuǎn)

（燕山大學(xué) 信息科學(xué)與工程學(xué)院，河北 秦皇島066004）

0 引 言

眾包導(dǎo)航是將獲取位置和規(guī)劃移動(dòng)路徑的計(jì)算由移動(dòng)互聯(lián)［1］用戶分布式完成的一類導(dǎo)航服務(wù)，可應(yīng)用于城市樓群密集區(qū)域人員移動(dòng)引導(dǎo)、文化博覽園內(nèi)觀光導(dǎo)游、園林公園內(nèi)尋人服務(wù)等［2］。目前最常用的室外導(dǎo)航技術(shù)是全球衛(wèi)星定位 系 統(tǒng) （global positioning system，GPS）。GPS 獲取位置精度可滿足戶外導(dǎo)航需求，但其能耗是不可接收的。對(duì)此，文獻(xiàn) ［3］采用GPS、WiFi、全球移動(dòng)通信系統(tǒng)（global system of mobile communication，GSM）等 多 種 傳感器組合定位，延長(zhǎng)續(xù)航時(shí)間；文獻(xiàn) ［4］通過降低GPS的采樣頻率延長(zhǎng)電池的生命周期；文獻(xiàn) ［5］提出在高樓林立城區(qū)和植被茂密的林區(qū)，使用WiFi在GPS失效的位置輔助定位；文獻(xiàn) ［6］提出A－GPS方法，結(jié)合網(wǎng)絡(luò)基站信息和GPS信息對(duì)移動(dòng)臺(tái)進(jìn)行定位，基站輔助定位。基于位置的服務(wù) （LBS）在精度和能耗上的權(quán)衡，使得陸基無線電導(dǎo)航 （例如WiFi、GSM）得到日益重視。文獻(xiàn) ［7］采用連接室外無線接入點(diǎn)，通過旋轉(zhuǎn)尋找RSSI信號(hào)最強(qiáng)的方向；文獻(xiàn) ［8］利用GSM 進(jìn)行初定位，并通過物理環(huán)境確定用戶的邏輯位置；文獻(xiàn) ［9］提出機(jī)會(huì)性的社交網(wǎng)絡(luò)，利用機(jī)會(huì)性的遇見信標(biāo)進(jìn)行重新定位。然而，為了滿足用戶精度的要求，用戶需要在室外大規(guī)模地部署信標(biāo)。針對(duì)現(xiàn)有工作存在的問題，本文設(shè)計(jì)一種基于機(jī)會(huì)性位置校正的低功耗城市眾包導(dǎo)航系iWALK。與傳統(tǒng)導(dǎo)航技術(shù)需要專業(yè)設(shè)備或大規(guī)模錨節(jié)點(diǎn)部署不同，該系統(tǒng)利用手機(jī)自帶的加速度計(jì)和電子羅盤測(cè)量移動(dòng)用戶行走的位移和方向，用戶可以在起點(diǎn)和終點(diǎn)分別開啟GPS，獲得位置標(biāo)記，來確定軌跡長(zhǎng)度。與GPS全球定位系統(tǒng)相比，iWALK 在降低能耗的同時(shí)能實(shí)現(xiàn)眾包導(dǎo)航服務(wù)。

1 iWALK 系統(tǒng)架構(gòu)

圖1是基于機(jī)會(huì)性校正眾包導(dǎo)航系統(tǒng)iWALK 的體系結(jié)構(gòu)。服務(wù)開啟時(shí)，用戶通過GPS全球定位系統(tǒng)獲得初始位置的經(jīng)、緯度坐標(biāo)，并根據(jù)用戶的體重和身高獲得步長(zhǎng)，實(shí)時(shí)采集加速度計(jì)傳感器的讀數(shù)，對(duì)Z 方向的加速度數(shù)值進(jìn)行步態(tài)檢測(cè)，如檢測(cè)到是有效步，則計(jì)步，通過步長(zhǎng)乘以步數(shù)獲得用戶的行走位移；同時(shí)讀取電子羅盤的讀數(shù)，電子羅盤讀數(shù)提供行走的方向。其中，距離用米表示，方向用順時(shí)針偏離磁北的角度表示。（RSSI＿i，SHI＿i，ORI＿i）三元組捕獲用戶的運(yùn)動(dòng)模式，稱為用戶的 “運(yùn)動(dòng)指紋”，其中RSSI＿i，SHI＿i，ORI＿i分別表示i時(shí)刻的GSM 信號(hào)接收強(qiáng)度、位移長(zhǎng)度、移動(dòng)方向。運(yùn)動(dòng)指紋被定期的傳送給服務(wù)器。

圖1 眾包導(dǎo)航系統(tǒng)的體系結(jié)構(gòu)

服務(wù)器使用航跡推算方法生成行走軌跡，對(duì)行走軌跡置反后得到用戶的返回導(dǎo)航路徑。航跡推算方法依賴自包含的慣導(dǎo)傳感器主動(dòng)定位，能夠隨時(shí)提供連續(xù)的行人位置信息。由于行人行走的行為具有隨機(jī)性和多變性，在步數(shù)、步長(zhǎng)以及航向3個(gè)因素中都存在誤差，使用戶的行走軌跡嚴(yán)重偏離用戶的實(shí)際軌跡，本文中利用音頻信號(hào)檢測(cè)相遇，機(jī)會(huì)性的獲取開啟GPS 設(shè)備的用戶位置信息進(jìn)行位置校正，最后采用漂移消除，進(jìn)一步減小軌跡映射的誤差。

2 機(jī)會(huì)性位置校正

目前智能手機(jī)大多數(shù)都已經(jīng)包含了多種傳感器，借助它們自帶的傳感器進(jìn)行開發(fā)，不僅拓展了行人導(dǎo)航定位的使用范圍，也使得室外定位更加靈活。但在實(shí)際運(yùn)用中仍然存在許多問題，例如加速度計(jì)噪聲導(dǎo)致計(jì)算用戶運(yùn)動(dòng)位移產(chǎn)生錯(cuò)誤［6］、電子羅盤噪聲導(dǎo)致記錄用戶運(yùn)動(dòng)方向存在偏差等。為了解決此類問題，本文利用機(jī)會(huì)性的相遇事件來糾正這些錯(cuò)誤。

2.1 相遇檢測(cè)

對(duì)于檢測(cè)相遇，系統(tǒng)應(yīng)該能夠準(zhǔn)確的捕捉到相遇事件的發(fā)生，檢測(cè)機(jī)制必須十分敏銳。現(xiàn)有的工作是基于藍(lán)牙機(jī)制來發(fā)現(xiàn)鄰近的用戶［10］，但藍(lán)牙機(jī)制對(duì)于發(fā)現(xiàn)短暫的相遇反應(yīng)太慢，實(shí)驗(yàn)結(jié)果表明50%的相遇事件藍(lán)牙是檢測(cè)不到的，所以該方法不適用。文獻(xiàn) ［9］中作者提出了采用音頻信號(hào)檢測(cè)相遇，并在不同的噪聲情況下進(jìn)行了音頻檢測(cè)實(shí)驗(yàn)，證明利用音頻信號(hào)處理實(shí)際的相遇是可行的。利用自組織網(wǎng)絡(luò)機(jī)制GSM 全球移動(dòng)通信系統(tǒng)，采用文獻(xiàn) ［9］中的檢測(cè)方法，我們?cè)谛[的步行街上進(jìn)行了音頻實(shí)驗(yàn)，其中手機(jī)距離為1 m。實(shí)驗(yàn)結(jié)果如圖2 所示，該音調(diào)頻帶（虛線表示）在2500 Hz～3000 Hz之間，而語音信號(hào)在1000Hz左右，所以能夠很好的區(qū)分開來。

圖2 音頻檢測(cè)

2.2 用戶位置校正

用戶位置校正［11］建立在音頻檢測(cè)的基礎(chǔ)之上。當(dāng)手機(jī)檢測(cè)到兩個(gè)用戶相遇時(shí)，根據(jù)用戶接收到的GSM 基站指紋來判斷兩個(gè)用戶位置的相似度，這里采用Tanimoto 系數(shù)法，用來測(cè)量?jī)蓚€(gè)指紋之間的相似。和余弦相似度相比，它需要更少的共享信標(biāo)，定義如下

式中：F1——用戶掃描到的GSM 指紋數(shù)據(jù)，F(xiàn)2——檢測(cè)到遇見的用戶掃描到的GSM 指紋數(shù)據(jù)，相似值T（F1，F(xiàn)2）越大說明兩個(gè)用戶間相似程度越大，距離越近。另外，用戶同一時(shí)間可能會(huì)檢測(cè)到遇見多個(gè)用戶，此時(shí)選取其中相似值最大的且已知GPS 的用戶的位置作為該用戶的地理位置。

2.3 用戶軌跡漂移消除

用戶位置糾正是用戶軌跡的漂移消除的前提。用戶在初始時(shí)刻tr1獲得自己的經(jīng)、緯度坐標(biāo)，當(dāng)下一個(gè)時(shí)刻tr2用戶遇見已知經(jīng)、緯度坐標(biāo)的用戶時(shí)，進(jìn)行位置校正，此時(shí)能夠計(jì)算出從估計(jì)位置到校正位置需要糾正的向量大小，標(biāo)記糾正向量為。由于tr2時(shí)刻用戶的位置是正確的，所以整個(gè)過程的漂移累計(jì)只有在時(shí)間tr1－tr2內(nèi)，基于這一觀察，可以糾正兩個(gè)連續(xù)校正位置間的軌跡，稱之為 “漂移消除”。

式中：L（t）——用戶在時(shí)間t時(shí)刻的位置。漂移消除路徑如圖3所示。

圖3 漂移消除：實(shí)線表示用戶真實(shí)路徑；點(diǎn)虛線表示用戶被計(jì)算的路徑；虛線表示漂移消除后被糾正的路徑

與文獻(xiàn) ［9］類似，我們都在兩次重新定位之間采用分段糾正方法進(jìn)行漂移消除，不同之處在于兩次重新定位的方式不同，文獻(xiàn) ［9］中需在導(dǎo)航場(chǎng)景中部署信標(biāo)節(jié)點(diǎn)為原點(diǎn)生成坐標(biāo)系，并基于用戶與信標(biāo)節(jié)點(diǎn)的相對(duì)位置，用距離信標(biāo)較近的節(jié)點(diǎn)校正離信標(biāo)較遠(yuǎn)節(jié)點(diǎn)的位置信息；而本文基于運(yùn)動(dòng)指紋匹配，利用機(jī)會(huì)性GPS 信息進(jìn)行位置校正，從而大大降低了對(duì)導(dǎo)航基礎(chǔ)設(shè)施的依賴程度。圖4給出用戶在燕山大學(xué)校園內(nèi)步行100 m 時(shí)的路徑，其中點(diǎn)虛線表示通過加速度計(jì)和電子羅盤數(shù)據(jù)計(jì)算得到的路徑，這里稱為慣性；點(diǎn)線表示相遇、糾正用戶位置和漂移消除共同作用的結(jié)果；實(shí)線為用戶真實(shí)行走路徑。從圖4可以看出采用漂移消除可以更好地糾正用戶的行走軌跡，能指導(dǎo)用戶回到距離初始位置更近的地方。

3 仿真實(shí)驗(yàn)及分析

為了評(píng)估iWALK 系統(tǒng)的性能，測(cè)試整個(gè)系統(tǒng)范圍內(nèi)用戶的運(yùn)動(dòng)和相遇模式，我們使用HTC G1智能手機(jī)收集傳感器數(shù)據(jù)，在燕山大學(xué)采集實(shí)驗(yàn)數(shù)據(jù)，同時(shí)使用GPS準(zhǔn)確記錄用戶真實(shí)走過路徑，生成回程導(dǎo)航軌跡，并將用戶終點(diǎn)位置作為回程的起點(diǎn)進(jìn)行回程導(dǎo)航實(shí)驗(yàn)。

3.1 實(shí)驗(yàn)數(shù)據(jù)及仿真環(huán)境

使用HTC G1手機(jī)采集傳感器數(shù)據(jù)，該手機(jī)內(nèi)置GPS、加速度計(jì)和電子羅盤。7 名志愿者被要求在燕山大學(xué)校園內(nèi)以水平手持智能手機(jī)分別以不同的速度、不同的傳感器采樣頻率和不同的路徑移動(dòng)，累計(jì)數(shù)據(jù)采集時(shí)間12小時(shí)。通過收集用戶在移動(dòng)過程中的GPS、加速度和磁偏北方向數(shù)據(jù)，獲取到實(shí)驗(yàn)所需的真實(shí)數(shù)據(jù)。實(shí)驗(yàn)過程中建立笛卡爾坐標(biāo)系，標(biāo)記坐標(biāo)系的縱軸的正向?yàn)榈乩矸较虻谋?，?fù)向?yàn)榈乩矸较虻哪?，橫軸正向?yàn)榈乩矸较虻臇|，負(fù)向?yàn)榈乩矸较虻奈?，例?（－5，0）處表示在原點(diǎn)位置向西行5 m。在實(shí)驗(yàn)過程中默認(rèn)起始點(diǎn)位置為坐標(biāo)原點(diǎn) （0，0）處。電子羅盤讀數(shù)為偏離北的角度，東方向即為偏離北90°，因此，在實(shí)驗(yàn)中順時(shí)針旋轉(zhuǎn)為正角，旋轉(zhuǎn)一圈為360°。

圖4 用戶在燕山大學(xué)校園內(nèi)的行走路徑

3.2 移動(dòng)軌跡映射精度

3.2.1 瞬時(shí)錯(cuò)誤對(duì)軌跡映射精度的影響

圖5 用戶的瞬時(shí)錯(cuò)誤隨時(shí)間的變化情況

在燕山大學(xué)校園內(nèi)進(jìn)行實(shí)驗(yàn)，以測(cè)試iWALK 的實(shí)用性。利用一部HTC G1智能手機(jī)收集傳感器數(shù)據(jù)，同時(shí)用另一部HTC G1手機(jī)獲得GPS坐標(biāo)作為糾正用戶瞬時(shí)位置的數(shù)據(jù)。圖5顯示了用戶的瞬時(shí)錯(cuò)誤在不同方案下隨時(shí)間的變化情況。實(shí)驗(yàn)結(jié)果表明，iWALK 可以使誤差減小到10m 左右，能夠滿足用戶室外的精度要求。只使用加速度計(jì)和電子羅盤記錄軌跡是不可行的，因?yàn)檫@些傳感器的噪聲會(huì)導(dǎo)致瞬時(shí)錯(cuò)誤迅速增長(zhǎng)，嚴(yán)重偏離用戶的實(shí)際軌跡；當(dāng)檢測(cè)到相遇，并進(jìn)行重新定位后，瞬時(shí)錯(cuò)誤明顯下降；漂移消除進(jìn)一步糾正用戶的軌跡，誤差繼續(xù)減小。

3.2.2 行走速度、采樣頻率和路徑對(duì)軌跡映射精度的影響由于不同人群的行走速度是不同的，即使是同一個(gè)人在不同時(shí)間、不同環(huán)境下的行走速度也會(huì)不一樣。因此步行速度是評(píng)價(jià)iWALK 系統(tǒng)的一個(gè)重要標(biāo)準(zhǔn)。圖6 （a）是在相同的起點(diǎn)和沿直線行走40m 的情況下，不同步行速度的實(shí)驗(yàn)結(jié)果比較，其中點(diǎn)線表示在較快的步行速度下的實(shí)驗(yàn)結(jié)果，虛線表示正常走路下的實(shí)驗(yàn)結(jié)果。由圖6 （a）知，行走速度較快時(shí)計(jì)算出的路徑為37m，比正常走路時(shí)準(zhǔn)確2 m。可見速度越快震動(dòng)越大，計(jì)步方法計(jì)算位移越準(zhǔn)確。因此，用戶的行走模式對(duì)iWALK 有重要影響。另外從實(shí)驗(yàn)結(jié)果可以看出，即使在相同的地點(diǎn)，由于傳感器噪音，實(shí)驗(yàn)也會(huì)存在一定的誤差，圖6 （a）中兩次實(shí)驗(yàn)存在2°的誤差。

圖6 用戶不同行走速度、采樣頻率和路徑對(duì)軌跡映射精度的影響

iWALK 利用手機(jī)自帶的慣導(dǎo)傳感器采集數(shù)據(jù)，不同手機(jī)所配置的傳感器型號(hào)可能不同，采樣頻率也就會(huì)隨之不同。為了檢測(cè)軌跡記錄是否與傳感器的采樣頻率有關(guān)，本文在相同的起點(diǎn)、沿直線正常行走40m 的情況下，使用不同的采樣頻率收集數(shù)據(jù)進(jìn)行實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果如圖6 （b）所示，其中點(diǎn)線的采樣頻率為1.5 Hz，實(shí)線的采樣頻率為0.75Hz。由圖6 （b）可以看出，采樣頻率減小一倍，實(shí)驗(yàn)得到的位移幾乎也減小一倍。原因是當(dāng)傳感器采集數(shù)據(jù)的頻率較低時(shí)，一部分?jǐn)?shù)據(jù)會(huì)丟失，使實(shí)驗(yàn)計(jì)算得到的用戶行走步數(shù)遠(yuǎn)遠(yuǎn)小于其實(shí)際步數(shù)，從而得到錯(cuò)誤的位移。因此對(duì)于iWALK 系統(tǒng)，手機(jī)配置的傳感器的采樣頻率越高回程效果越好。

iWALK 要求在陌生復(fù)雜路況的環(huán)境下能夠提供回程導(dǎo)航服務(wù)，因此本文方法能否滿足用戶的精度要求，能否準(zhǔn)確識(shí)別路況是非常重要的。在不同的路徑下進(jìn)行實(shí)驗(yàn)，圖6（c）分別是在直線行走、一次轉(zhuǎn)彎、多次轉(zhuǎn)彎的情況下步行40m 的實(shí)驗(yàn)結(jié)果，其中保持正常行走、采樣頻率一致。由圖6 （c）可以看出，在3條路徑下實(shí)驗(yàn)分別得到37m、34m 和23m 的位移，可見iWALK 受路徑的影響很大，尤其在轉(zhuǎn)彎時(shí)會(huì)嚴(yán)重影響加速度計(jì)和電子羅盤的讀數(shù)，導(dǎo)致位移計(jì)算產(chǎn)生較大誤差。因此，路況越復(fù)雜，轉(zhuǎn)彎次數(shù)越多，位移計(jì)算誤差越大，回程導(dǎo)航服務(wù)越不準(zhǔn)確。另外，從實(shí)驗(yàn)結(jié)果中可以看出iWALK 能夠準(zhǔn)確檢測(cè)到轉(zhuǎn)彎，即使是小角度的偏轉(zhuǎn)。

3.3 系統(tǒng)運(yùn)行能耗

最后測(cè)試整個(gè)回程導(dǎo)航服務(wù)過程中的能量消耗情況。為了評(píng)估能量消耗，使用平均能量消耗來估計(jì)手機(jī)電池的生命周期，圖7 （a）為實(shí)驗(yàn)獲得的HTC G1智能手機(jī)在不同GPS環(huán)境下的平均能量消耗和傳感器在不同采樣頻率下的平均能量消耗生命周期。從圖7 （a）可以看出，使用傳感器代替GPS將大大提高電池的生命周期，實(shí)現(xiàn)了低功耗的目的。

圖7 系統(tǒng)能量消耗情況

為了更好的證明iWALK 系統(tǒng)可以實(shí)現(xiàn)低功耗的效果。我們?cè)谛@、公園、景區(qū)和市中心4 個(gè)地點(diǎn)分別使用iWALK 和SensLoc［11］、GPS在10分鐘的時(shí)間內(nèi)使用回程導(dǎo)航下的電量消耗情況進(jìn)行比較，結(jié)果如圖7 （b）所示，可以看出市中心由于被高大建筑物環(huán)繞，GPS導(dǎo)航需要較長(zhǎng)時(shí)間的延遲，因此消耗電量較大；相反公園周圍高大建筑物較少，信號(hào)較強(qiáng)，消耗電量最少。而使用加速度計(jì)和電子羅盤消耗的能量與使用GPS 消耗的能量相比不到10%。由于iWALK 使用音頻檢測(cè)是在手機(jī)正常使用的情況下已經(jīng)開啟，不需要在服務(wù)時(shí)專門的開啟，因此iWALK與手機(jī)閑置時(shí)的能量消耗是非常接近的。另外，在室外環(huán)境下，SensLoc使用降低GPS采樣頻率的方法降低能量消耗。而iWALK 只有在起點(diǎn)和終點(diǎn)開啟GPS，和SensLoc方法相比，進(jìn)一步節(jié)約了能量消耗的60%。

4 結(jié)束語

本文提出一種陸基眾包無線電導(dǎo)航模式，大幅減少了開啟GPS的時(shí)間，有效降低了導(dǎo)航服務(wù)過程中的能耗?；谝纛l信號(hào)檢測(cè)相遇，根據(jù)GSM 指紋的相似性來尋找更準(zhǔn)確的已知GPS坐標(biāo)的用戶，采取軌跡校正，消除了用戶行走的軌跡漂移，有效提高了回程導(dǎo)航路線的精度。基于Google Android系統(tǒng)智能手機(jī)獲取了大量真實(shí)慣導(dǎo)數(shù)據(jù)，仿真實(shí)驗(yàn)及分析結(jié)果表明，在能耗較低的條件下，用戶能夠獲得較高的眾包導(dǎo)航精度。后續(xù)工作在校正行人移動(dòng)方向時(shí)將考慮移動(dòng)終端放置的隨機(jī)性等因素。

［1］LUO Junzhou，WU Wenjia，YANG Ming.Mobile Internet：Terminal devices，network and services ［J］.Chinese Journal of Computers，2011，34 （11）：2029－2051 （in Chinese）.［羅軍舟，吳文甲，楊明.移動(dòng)互聯(lián)網(wǎng)：終端、網(wǎng)絡(luò)與服務(wù) ［J］.計(jì)算機(jī)學(xué)報(bào)，2011，34 （11）：2029－2051.］

［2］ZHOU Aoying，YANG Bin，JIN Cheqing，et al.Locationbased services：Architecture and progress ［J］.Chinese Journal of Computers，2011，34 （7）：1156－1171 （in Chinese）.［周傲英，楊彬，金澈清，等.基于位置的服務(wù)：架構(gòu)與發(fā)展［J］.計(jì)算機(jī)學(xué)報(bào)，2011，34 （7）：1156－1171.］

［3］Constandache I，Gaonkar S，Sayler M，et al.EnLoc：Energy－efficient localization for mobile phones［C］／／Proceedings of the 28th IEEE International Conference on Computer Communications，2009：2716－2720.

［4］Ra M－R，Paek J，Sharma A B，et al.Energy－delay tradeoffs in smartphone applications［C］／／Proceedings of the 7th International Conference on Mobile Systems，Applications，and Services，2010：255－270.

［5］Kjaergaard M B，Langdal J，Godsk T，et al.Entracked：Energy－efficient robust position tracking for mobile devices［C］／／Proceedings of the 7th International Conference on Mobile Systems，Applications，and Services，2009：22－25.

［6］Constandache I，Choudhury R R，Rhee I.Towards mobile phone localization without war－driving ［C］／／Proceedings of the 29th IEEE International Conference on Computer Communi－cations，2010：1－9.

［7］Zhang Z.I am the antenna：Accurate outdoor AP location using smartphones［C］／／Proceedings of the 17th Annual International Conference on Mobile Computing and Networking，2011：19－23.

［8］Azizyan M，Constandache I，Choudhury R R.Surroundsense：Localizing mobile phones via ambience fingerprinting ［C］／／Proceedings of the 15th Annual International Conference on Mobile Computing and Networking，2009：261－272.

［9］Constandache I，Bao X，Azizyan M，et al.Did you see Bob？：Human localization using mobile phones［C］／／Proceedings of the 16th Annual International Conference on Mobile Computing and Networking，2010：149－160.

［10］Smith T J，Saroiu S，Wolman A.Bluemonarch：A system for evaluating Bluetooth applications in the wild ［C］／／Proceedings of the 7th International Conference on Mobile Systems，Applications，and Services，2009：41－54.

［11］Kim D H，Kim Y，Estrin D，et al.Sensloc：Sensing everyday places and paths using less energy ［C］／／Proceedings of the 8th ACM Conference on Embedded Networked Sensor Systems，2010：43－56.