基于眾包的多樓層定位方法

羅 娟 章翠君 王 純

(湖南大學(xué)信息科學(xué)與工程學(xué)院 長(zhǎng)沙 410082)

隨著物聯(lián)網(wǎng)技術(shù)的快速發(fā)展和移動(dòng)智能終端的廣泛普及，在市場(chǎng)消費(fèi)級(jí)、企業(yè)級(jí)應(yīng)用的需求推動(dòng)下，人們對(duì)于基于位置的服務(wù)(location based services, LBS)需求日益劇增，精準(zhǔn)的室內(nèi)外定位和導(dǎo)航服務(wù)在日常生活中重要性日漸凸顯.室外，全球定位系統(tǒng)(global positioning system, GPS)和北斗定位系統(tǒng)發(fā)展成熟可提供準(zhǔn)確的位置服務(wù).室內(nèi)，隨著大型建筑高度不斷攀升以及建筑物內(nèi)部結(jié)構(gòu)越加復(fù)雜，目前仍缺少成熟的多樓層室內(nèi)定位技術(shù).無(wú)線局域網(wǎng)(wireless local area network, WLAN)的廣泛部署和基礎(chǔ)設(shè)施的完備，基于接收信號(hào)強(qiáng)度(received signal strength indication, RSSI)的WLAN指紋的定位技術(shù)因其無(wú)需額外的硬件設(shè)施，具有成本低、部署簡(jiǎn)單、穿透力強(qiáng)、接入方便等優(yōu)勢(shì)，受到廣大科研工作者的青睞.

基于RSSI指紋定位方法也稱匹配定位法，該方法不需要接入點(diǎn)(access point, AP)位置的先驗(yàn)知識(shí)，但需要在離線階段劃分網(wǎng)格，在位置區(qū)域中設(shè)置固定數(shù)量的采樣點(diǎn)，記錄每一樓層每一網(wǎng)格內(nèi)的RSSI值，構(gòu)建“樓層-位置-信號(hào)強(qiáng)度”指紋庫(kù)，如圖1所示.傳統(tǒng)指紋庫(kù)的構(gòu)建過(guò)程依賴專業(yè)人員的現(xiàn)場(chǎng)勘測(cè)，耗時(shí)費(fèi)力.同時(shí)由于室內(nèi)多徑效應(yīng)，無(wú)線信號(hào)在傳播過(guò)程中存在波動(dòng)性，RSSI值需要隨著室內(nèi)物理環(huán)境的動(dòng)態(tài)變化而進(jìn)行周期性的更新，增加了指紋庫(kù)的維護(hù)成本.

眾包的基本思想是將冗余繁重的指紋數(shù)據(jù)采集任務(wù)隱式分配給多個(gè)普通用戶，很大程度上減少指紋采集的時(shí)間成本和勞動(dòng)成本.近年來(lái)，智能手機(jī)、智能手表等可穿戴式設(shè)備通常都內(nèi)置了慣性傳感單元(inertial measurement unit, IMU)，配置有氣壓計(jì)、加速度傳感器、角速度傳感器、陀螺儀等傳感器，此類智能設(shè)備的廣泛普及使得人群比以往任何時(shí)候都更容易參與眾包.

本文基于眾包提出了一種多樓層指紋庫(kù)構(gòu)建方法——MCSLoc，根據(jù)室內(nèi)地圖構(gòu)建室內(nèi)語(yǔ)義拓?fù)鋱D，利用卡爾曼濾波(Kalman filter, KF)融合智能手機(jī)內(nèi)置加速度傳感器和氣壓計(jì)的值進(jìn)行高度測(cè)量，劃分傳感器數(shù)據(jù)到各個(gè)樓層，利用智能手機(jī)內(nèi)置傳感器獲取眾包用戶相對(duì)軌跡和RSSI序列，使用隱馬爾可夫(hidden Markov model, HMM)模型和軌跡匹配維特比(track matching Viterbi, TM-Viterbi)算法將用戶相對(duì)軌跡和室內(nèi)語(yǔ)義地圖相匹配，從而獲取軌跡絕對(duì)路徑為RSSI標(biāo)注物理位置，構(gòu)建多樓層指紋庫(kù).

Fig. 1 Traditional fingerprint database construction process圖1 傳統(tǒng)指紋庫(kù)構(gòu)建過(guò)程

本文的主要貢獻(xiàn)包括3個(gè)方面:

1) 提出一種“分段式”適用于眾包場(chǎng)景的用戶軌跡獲取方法，設(shè)計(jì)拐角檢測(cè)算法，以拐角劃分軌跡子段，動(dòng)態(tài)獲取用戶步長(zhǎng)，消除眾包用戶步長(zhǎng)異質(zhì)以及智能手機(jī)內(nèi)置傳感器航向漂移問(wèn)題;

2) 將隱馬爾可夫模型應(yīng)用到眾包用戶軌跡匹配，提出改進(jìn)的維特比地圖匹配算法TM-Viterbi，相鄰節(jié)點(diǎn)之間加以公共的觀測(cè)狀態(tài)限制，保證匹配后的軌跡節(jié)點(diǎn)序列在語(yǔ)義地圖上的節(jié)點(diǎn)連續(xù)性;

3) 提出一種RSSI眾包指紋位置標(biāo)記方法，利用時(shí)間戳為無(wú)標(biāo)簽RSSI序列標(biāo)記樓層標(biāo)簽以及物理位置標(biāo)簽，獲取用戶軌跡絕對(duì)坐標(biāo).

1 相關(guān)工作

眾包概念提出后，越來(lái)越多的研究學(xué)者致力于以眾包的方式構(gòu)建RSSI指紋庫(kù)，按照用戶的參與程度，眾包技術(shù)可以分為主動(dòng)眾包和被動(dòng)眾包.主動(dòng)眾包要求參與者主動(dòng)貢獻(xiàn)數(shù)據(jù)信息.Yang等人提出的FreeLoc系統(tǒng)要求參與者貢獻(xiàn)記錄的指紋數(shù)據(jù)，并將位置標(biāo)簽上傳到服務(wù)器.Zheng等人通過(guò)用戶主動(dòng)提供的圖像數(shù)據(jù)、WiFi樣本以及IMU感應(yīng)數(shù)據(jù)構(gòu)建視覺導(dǎo)航系統(tǒng)Travi-Navi.相比于主動(dòng)眾包，與智能手機(jī)內(nèi)置IMU相結(jié)合的被動(dòng)眾包技術(shù)應(yīng)用更加廣泛，被動(dòng)眾包用戶通常是無(wú)意識(shí)或弱意識(shí)參與，對(duì)系統(tǒng)的干預(yù)較少.LiFS系統(tǒng)利用用戶的移動(dòng)性，無(wú)需人工現(xiàn)場(chǎng)勘測(cè)實(shí)現(xiàn)房間級(jí)別的定位，該系統(tǒng)是國(guó)內(nèi)基于眾包定位的突破，但是定位精度不高.PiLoc利用智能手機(jī)內(nèi)置IMU，根據(jù)行人航位推(pedestrian dead reckoning, PDR)算法估計(jì)用戶軌跡，將用戶位移和RSSI信號(hào)相結(jié)合，實(shí)現(xiàn)WiFi指紋庫(kù)構(gòu)建，定位精度較高，但系統(tǒng)需要用戶初始位置先驗(yàn)知識(shí).MPiLoc在PiLoc的基礎(chǔ)之上，通過(guò)氣壓傳感器對(duì)用戶軌跡進(jìn)行聚類劃分樓層，構(gòu)建多樓層指紋庫(kù).

有研究表明，將用戶軌跡與室內(nèi)地圖匹配可以顯著提高定位系統(tǒng)的性能，基于HMM的室內(nèi)定位已經(jīng)被證明為一種有效的方法.如基于HMM的室內(nèi)地圖匹配定位、基于HMM的WiFi信號(hào)光線跟蹤3維路徑匹配定位、基于HMM和網(wǎng)格的貝葉斯聯(lián)合跟蹤室內(nèi)移動(dòng)終端定位.隨著IMU的發(fā)展，出現(xiàn)了HMM與慣性傳感器數(shù)據(jù)融合定位，該類方法通常面臨HMM狀態(tài)數(shù)過(guò)大，算法復(fù)雜度較高問(wèn)題.為減少狀態(tài)數(shù)，Lu等人以拐角特征作為PDR軌跡上下文，使用HMM將其與數(shù)據(jù)庫(kù)中的上下文相匹配，獲得行人位置.該方法能夠快速確定行人的起始點(diǎn)，具有良好的穩(wěn)定性和魯棒性.

本文結(jié)合眾包和HMM技術(shù)，采集眾包用戶跨樓層走動(dòng)時(shí)的智能手機(jī)內(nèi)置傳感器信息，提出分段式用戶軌跡獲取方法獲取用戶相對(duì)軌跡，建立HMM模型，利用TM-Viterbi算法將用戶軌跡與地圖匹配，構(gòu)建多樓層指紋庫(kù)，MCSLoc可以去除指紋庫(kù)構(gòu)建階段的專業(yè)人工勘測(cè)，無(wú)需眾包用戶初始位置先驗(yàn)知識(shí).

2 研究框架

MCSLoc方法研究架構(gòu)圖如圖2所示，系統(tǒng)由離線階段和在線階段2部分組成.離線階段構(gòu)建多樓層指紋庫(kù)，為在線階段用戶的位置請(qǐng)求提供服務(wù)，本文的主要工作在于離線階段的基于眾包的多樓層指紋庫(kù)的構(gòu)建，下面將具體描述這部分關(guān)鍵過(guò)程.

Fig. 2 MCSLoc method research framework圖2 MCSLoc方法研究框架

2.1 地圖預(yù)處理

通過(guò)讀取JPG形式的室內(nèi)平面圖，獲取地圖坐標(biāo)和屬性信息，采用“霍夫變換+Harris角點(diǎn)檢測(cè)”算法將室內(nèi)平面圖轉(zhuǎn)換為由節(jié)點(diǎn)和路段構(gòu)成的語(yǔ)義地圖

G

(

Q

,

V

)，其中路段表示室內(nèi)地圖可行走區(qū)域的主要路徑，

V

={

v

,

v

,…,

v

}表示路段集;節(jié)點(diǎn)表示路徑的拐角點(diǎn)以及路徑的端點(diǎn)(起始點(diǎn)和終止點(diǎn))，

Q

={

q

,

q

,…,

q

}表示節(jié)點(diǎn)集

.

()描述語(yǔ)義地圖如圖3所示:

(1)

其中，

w

表示節(jié)點(diǎn)

q

到節(jié)點(diǎn)

q

之間的位移長(zhǎng)度，即路段長(zhǎng)度，當(dāng)節(jié)點(diǎn)

q

和

q

是相同節(jié)點(diǎn)，

w

=0，當(dāng)節(jié)點(diǎn)

q

和

q

不相鄰或者不在一條直線上，

w

為無(wú)窮

.n

表示節(jié)點(diǎn)的數(shù)量，

m

表示路段的數(shù)量

.

Fig. 3 Indoor floor plan and semantic map圖3 室內(nèi)平面圖及語(yǔ)義地圖示意圖

Fig. 4 Process of segmented trajectory acquisition method圖4 分段式軌跡獲取流程

2.2 分段式軌跡獲取過(guò)程

軌跡獲取即是利用智能手機(jī)內(nèi)置傳感器獲取數(shù)據(jù)計(jì)算用戶運(yùn)動(dòng)軌跡，設(shè)計(jì)了一種分段式眾包用戶軌跡獲取方法，其流程如圖4所示.眾包用戶智能手機(jī)后臺(tái)采集的傳感器數(shù)據(jù)由以下五元組組成:

P

=(

t

,

dirc

,

rss

,

acc

,

pres

)，分別有時(shí)間戳、陀螺儀方向數(shù)據(jù)、RSSI序列、加速度值、氣壓值.主要分為3個(gè)步驟:傳感器數(shù)據(jù)所屬樓層劃分、拐角檢測(cè)、子段長(zhǎng)度獲取.

2.2.1 傳感器數(shù)據(jù)所屬樓層劃分

由于眾包參與者為跨樓層行走，采集的傳感器數(shù)據(jù)為多樓層連續(xù)型數(shù)據(jù)，按照分層思想，首先將傳感器數(shù)據(jù)劃分到各個(gè)樓層.采用文獻(xiàn)[15]中提出的高度測(cè)量方法(Kalman filter and floor change detection, KF_FCD)劃分傳感器數(shù)據(jù)，即利用KF融合智能手機(jī)內(nèi)置加速度傳感器和氣壓計(jì)的值進(jìn)行高度測(cè)量，利用樓層變化檢測(cè)算法對(duì)KF輸出的值進(jìn)一步修正，根據(jù)實(shí)時(shí)測(cè)量的高度和時(shí)間戳判斷傳感器數(shù)據(jù)所屬樓層.

2.2.2 拐角檢測(cè)

根據(jù)傳感器數(shù)據(jù)估計(jì)眾包用戶在相應(yīng)樓層的軌跡.航向角的大小反映了行人行走的方向，航向角的偏移導(dǎo)致的誤差會(huì)隨著時(shí)間累積，但是短時(shí)間內(nèi)航向角偏移較小，即行人軌跡的行走方向相鄰2步之間角度的誤差較小.假設(shè)眾包用戶在室內(nèi)沿直線行走且拐彎呈直角，由室內(nèi)地圖的構(gòu)造可知，用戶在拐彎處有左拐或右拐.即可通過(guò)航向角獲知用戶是否拐彎.據(jù)此，設(shè)計(jì)了一種拐角檢測(cè)算法檢測(cè)軌跡拐角.設(shè)定角度變化允許的上下限閾值分別為

thMin

，

thMax

，其中

thMin

為陀螺儀允許的最大角度誤差，通過(guò)經(jīng)驗(yàn)將其設(shè)為50°，

thMax

為相鄰2步角度變化最大值，根據(jù)經(jīng)驗(yàn)將其設(shè)為180°

.

算法具體步驟算法1所示，輸入陀螺儀角度數(shù)組

ω

，其中

ω

[

i

]為第

i

步的行走角度，算法時(shí)間復(fù)雜度為

O

(

n

)

.

算法1.

拐角檢測(cè)算法.輸入：陀螺儀角度數(shù)組

ω

、閾值

thMin

,

thMax

；輸出：拐角方向數(shù)組

Ψ

(1代表右拐、-1代表左拐)

.

① for

i

=1:

n

-2 do②

nextS

=abs(

ω

[

i

-1]-

ω

[

i

]);③

tnextS

=abs(

ω

[

i

]-

ω

[

i

+1]);④ if (

nextS

>180°)∨(

tnextS

>180°)⑤

next

=360°-

nextS

;

tnext

=360°-

tnextS

;

⑥ end if

⑦

/

*比較角度變化值

nextS

和

tnextS

與閾值的大小*

/

if (

nextS

>

thMin

∧

nextS

<

thMax

∧

tnextS

>

thMin

∧

tnextS

<

thMax

)⑧ if (

ω

[

i

+1]-

ω

[

i

]>0)

/

*右拐*

/

⑨

Ψ

[

i

+1][0]=

ω

[

i

+1];

⑩ end if

2

.

2

.

3 子段長(zhǎng)度獲取子段為拐角檢測(cè)算法檢測(cè)到一條軌跡相鄰2個(gè)拐角間的距離，

n

個(gè)拐角即可劃分

n

-1條子段

.

那么軌跡

D

可由

m

條子段組成，

D

={

d

,

d

,…,

d

}，獲取各子段的長(zhǎng)度

d

(1<

j

<

m

=

n

-1)，即可得到眾包用戶預(yù)估軌跡

.

根據(jù)拐角時(shí)刻時(shí)間戳獲取相鄰拐角時(shí)間間隔內(nèi)傳感器數(shù)據(jù)，以此估計(jì)各子段長(zhǎng)度

.

研究表明，行人在行走過(guò)程中，加速度具有周期性類正弦波特性，波峰檢測(cè)法根據(jù)此特性對(duì)波形的峰值波谷進(jìn)行計(jì)數(shù)，可有效估計(jì)行人的步頻

.

此外，也可有效估計(jì)行人步長(zhǎng)，為減少行人運(yùn)動(dòng)狀態(tài)影響，選擇合加速度作為特征值

.

公式為

(2)

其中，

a

(

t

)表示時(shí)刻

t

的合加速度，

a

(

t

),

a

(

t

),

a

(

t

)分別表示3軸加速度傳感器在

X

軸、

Y

軸和

Z

軸的加速度，

g

表示重力加速度，其值為9

.

81 m/s.受智能手機(jī)內(nèi)置傳感器本身精度的制約以及行人身體抖動(dòng)等外部因素的影響，加速度傳感器采集的數(shù)據(jù)通常含有噪聲.有限脈沖響應(yīng)(finite impulse response, FIR)數(shù)字濾波器為高保真低通濾波器，它可以同時(shí)滿足幅頻特性和線性相位特性.為了去除高頻噪聲降低誤檢率，采用FIR數(shù)字濾波器最優(yōu)化設(shè)計(jì)方法設(shè)計(jì)低通濾波器，其中，采樣頻率

f

=500 Hz，期望幅頻特性的頻率向量=(4,0,2,3,500)

/f

，幅值向量=(1,1,0,0)，加速度傳感器合加速度濾波前后對(duì)比如圖5所示

.

低通濾波后的偽波峰基本消除，噪聲干擾大大減少

.

Fig. 5 Contrast before and after acceleration FIR low pass filtering圖5 加速度FIR低通濾波前后對(duì)比圖

目前常用的行人步長(zhǎng)估計(jì)方法有:常數(shù)步長(zhǎng)模型、運(yùn)動(dòng)機(jī)械模型、線性模型、非線性模型以及人工智能模型等

.

其中非線性模型通常在步頻與步長(zhǎng)之間建立相應(yīng)的非線性估計(jì)模型，該類模型僅與加速度、速度等特征變量有關(guān)，受行人自身身高、體重、腿長(zhǎng)等因素影響較小

.

結(jié)合更適合眾包場(chǎng)景的非線性模型Weinberg算法動(dòng)態(tài)估計(jì)用戶每一步步長(zhǎng)

.

子段長(zhǎng)度公式為

(3)

其中，1≤

i

≤

n

，

d

表示子段的長(zhǎng)度，

S

表示本子段內(nèi)第

i

步的步長(zhǎng)，

K

為模型系數(shù)，取值為0

.

42，

a

max和

a

min分別表示步頻檢測(cè)本子段第

i

步中得到的最大加速度值和最小加速度值，

n

表示本子段內(nèi)的行走步數(shù)

.

2.3 HMM模型

HMM模型是關(guān)于時(shí)序的概率模型，可由=(,,)表示

.

應(yīng)用于本場(chǎng)景的Markov過(guò)程即是將未知起點(diǎn)的眾包用戶軌跡與語(yǔ)義地圖匹配獲取絕對(duì)軌跡過(guò)程

.

在地圖匹配問(wèn)題中，語(yǔ)義地圖的節(jié)點(diǎn)作為隱藏狀態(tài)；語(yǔ)義地圖的路段作為觀測(cè)狀態(tài)；智能手機(jī)內(nèi)置傳感器數(shù)據(jù)獲取的眾包用戶軌跡子段的長(zhǎng)度序列視為觀測(cè)序列

.

根據(jù)HMM模型原理，地圖匹配過(guò)程遵循2個(gè)規(guī)則:1)任意時(shí)刻的隱藏狀態(tài)值依賴于前一時(shí)刻，即每個(gè)節(jié)點(diǎn)之間轉(zhuǎn)移的可能性為狀態(tài)轉(zhuǎn)移概率；2)任意時(shí)刻的觀測(cè)狀態(tài)只依賴當(dāng)前時(shí)刻的隱藏狀態(tài)

.

假設(shè)

Q

={

q

,

q

,…,

q

}是隱藏狀態(tài)的集合，即語(yǔ)義地圖節(jié)點(diǎn)集合，

N

表示隱藏狀態(tài)數(shù);

V

={

v

,

v

,…,

v

}是觀測(cè)狀態(tài)集合，即語(yǔ)義地圖中路段集合，

M

表示觀測(cè)狀態(tài)數(shù)

.

圖6是以圖2為對(duì)象建立的HMM模型示意圖

.P

(

q

|

q

)表示轉(zhuǎn)移概率，即每一時(shí)刻節(jié)點(diǎn)之間轉(zhuǎn)移的可能性，

P

(

v

|

q

)表示發(fā)射概率，即節(jié)點(diǎn)下觀測(cè)到路段的概率

.

表示初始時(shí)刻隱藏狀態(tài)的概率向量

.

Fig. 6 Hidden Markov model schematic diagram圖6 HMM示意圖

由于在未知起點(diǎn)下，用戶在任意一個(gè)節(jié)點(diǎn)位置的概率相等，因此

.

(4)

=[

a

]×表示節(jié)點(diǎn)之間轉(zhuǎn)移概率矩陣，由轉(zhuǎn)移概率組成，定義與節(jié)點(diǎn)

q

處于一條路段上的節(jié)點(diǎn)的集合為

Ψ

，集合

Ψ

的節(jié)點(diǎn)數(shù)量之和為

k

.

狀態(tài)轉(zhuǎn)換概率計(jì)算公式為

(5)

表示發(fā)射概率矩陣，即在某個(gè)節(jié)點(diǎn)下觀測(cè)到某個(gè)路段的概率

.

將與節(jié)點(diǎn)直接相連的路段作為該狀態(tài)下的可觀測(cè)值

.

定義節(jié)點(diǎn)

q

可觀測(cè)的路段的集合為

φ

，集合

φ

中路段的數(shù)量之和為

z

.

發(fā)射概率公式為

(6)

2.4 TM-Viterbi地圖匹配算法

Viterbi算法是HMM模型求解預(yù)測(cè)問(wèn)題的算法之一， 已知模型

λ

=(,,)和觀測(cè)序列

O

={

o

,

o

,…,

o

}，求對(duì)給定觀測(cè)序列條件概率最大的狀態(tài)序列，其基本思想是基于動(dòng)態(tài)規(guī)劃尋找最優(yōu)路徑的隱藏狀態(tài)序列

.

MCSLoc利用TM-Viterbi算法求解語(yǔ)義地圖中與眾包用戶軌跡最相似的路徑，即輸入一條軌跡的子段長(zhǎng)度序列

O

=

D

={

d

,

d

,…,

d

}，求語(yǔ)義地圖中最有可能出現(xiàn)該序列的節(jié)點(diǎn)序列

.

TM-Viterbi算法對(duì)傳統(tǒng)Viterbi算法的改進(jìn)主要有:1)傳統(tǒng)的Viterbi算法依賴概率矩陣，未考慮節(jié)點(diǎn)序列的物理連續(xù)性.因此，本文對(duì)節(jié)點(diǎn)的轉(zhuǎn)移加入物理約束，即尋找最優(yōu)路徑時(shí)，本節(jié)點(diǎn)與下一個(gè)節(jié)點(diǎn)加以公共的觀測(cè)狀態(tài)限制，利用路段關(guān)聯(lián)節(jié)點(diǎn).2)通過(guò)傳感器獲取的用戶軌跡子段長(zhǎng)度與真實(shí)路段長(zhǎng)度存在誤差，即存在觀測(cè)子段長(zhǎng)度

d

不屬于觀測(cè)狀態(tài)集合

V.

為獲取該類觀測(cè)值的發(fā)射概率，使用高斯函數(shù)來(lái)表達(dá)誤差因素的發(fā)射概率

.

計(jì)算公式為

(7)

其中，

μ

表示路段集合

φ

中與子段

d

絕對(duì)值最小的路段長(zhǎng)度，

δ

表示誤差，取值為(

μ

-1)

/

4

.

導(dǎo)入變量

θ

和

φ

，變量

θ

(

i

)為時(shí)刻

t

概率最大值，變量

φ

(

i

)為時(shí)刻

t

所有單個(gè)路徑中概率最大的路徑的第

t

-1個(gè)節(jié)點(diǎn)

.

TM-Viterbi算法步驟如算法2所示.傳統(tǒng)Viterbi算法的時(shí)間復(fù)雜度為

O

(

N

M

)，

N

表示隱藏狀態(tài)數(shù),

M

表示觀測(cè)狀態(tài)數(shù)，TM-Viterbi算法對(duì)節(jié)點(diǎn)的轉(zhuǎn)移加以約束，在尋找最佳路徑時(shí)，下一節(jié)點(diǎn)需為上一節(jié)點(diǎn)的鄰居節(jié)點(diǎn)，因此其TM-Viterbi算法時(shí)間復(fù)雜度為

O

(

NMγ

)，

γ

表示上一節(jié)點(diǎn)的相鄰節(jié)點(diǎn)數(shù)量

.

分析可知，改進(jìn)的TM-Viterbi算法時(shí)間復(fù)雜度明顯降低，且地圖匹配過(guò)程為離線階段，運(yùn)行時(shí)間可容忍性強(qiáng)，時(shí)延要求低，該時(shí)間復(fù)雜度滿足需求

.

算法2.

TM-Viterbi算法.輸入：HMM模型

λ

=(,,)、子段序列

O

={

d

,

d

,…,

d

}；

①

θ

(

i

)=

b

(

d

),

φ

(

i

)=0,

i

=1,2,…,

N

;

/

*初始化*

/

② for

t

=2:

T

do③ if

d

?

V

then

⑤ end if

/

*誤差因素發(fā)射概率*

/

⑥ if

b

(

d

-1)>0,

i

=1,2,…,

N

；

/

*判斷節(jié)點(diǎn)是否有連接*

/

2,…,

N

;

/

*遞推計(jì)算最大概率*

/

2,…,

N

;

/

*記錄路徑*

/

⑨ end if

⑩ end for

/

*終止*

/

/

*返回最優(yōu)節(jié)點(diǎn)序列*

/

2.5 多樓層指紋庫(kù)構(gòu)建

地圖匹配獲取的節(jié)點(diǎn)序列可視為軌跡拐角序列， 由于語(yǔ)義地圖節(jié)點(diǎn)的絕對(duì)坐標(biāo)已知，因此可快速獲取軌跡的起始位置、終止位置以及拐角絕對(duì)位置坐標(biāo).本文設(shè)置WiFi接收器采集RSSI數(shù)據(jù)的頻率為1 Hz，設(shè)

a

(

x

,

y

)和

b

(

x

,

y

)分別為軌跡的2個(gè)相鄰拐角坐標(biāo)，

t

和

t

分別為用戶的智能手機(jī)記錄經(jīng)過(guò)拐角的時(shí)間戳(單位為s)，假設(shè)眾包用戶勻速行走，那么RSSI的位置標(biāo)簽

Crss

(

x

,

y

)為

(8)

其中，

t

=1,2,…,

t

-

t

.

由此，即可為每一條RSSI值序列標(biāo)記位置標(biāo)簽，一條RSSI指紋構(gòu)成:[

F

,

Crss

(

x

,

y

),

RSSI

,

RSSI

,…,

RSSI

]，其中

F

表示樓層，

n

表示AP的數(shù)量，RSSI指紋匯總即可構(gòu)建多樓層指紋庫(kù)

.

2.6 在線定位

在線階段定位過(guò)程包括待定位點(diǎn)所在樓層判別與2維坐標(biāo)獲取.定位過(guò)程采用基于多分類線性判別分析(linear discriminant analysis, LDA)的樓層判別方法判斷用戶所在樓層，樓層判別精度為99%～100%;利用位置指紋加權(quán)

k

最近鄰(

k

weighted nearest neighbor, WKNN)算法獲取最終位置坐標(biāo)，其中

k

=4.具體描述為：根據(jù)多分類LDA的樓層判別模型，分別對(duì)樓層和AP屬性進(jìn)行兩兩分組，利用LDA方法求出各分組的廣義瑞利商

J

最大化的目標(biāo)值，根據(jù)分組中的最大值

J

選擇最優(yōu)分組進(jìn)行兩兩樓層的判定，利用投票法選擇最終的樓層號(hào)，確定用戶所在樓層

F

. 2維坐標(biāo)獲取階段，采集待定位點(diǎn)RSSI指紋序列，在多樓層指紋庫(kù)

F

層指紋中選取與待定位點(diǎn)RSSI指紋相似程度最高的

k

個(gè)指紋的位置坐標(biāo)，并根據(jù)相似程度賦予指紋位置坐標(biāo)相應(yīng)權(quán)值，最終加權(quán)平均得到待定位點(diǎn)2維位置坐標(biāo)(

x

,

y

)

.

Fig. 7 Plan of experimental building圖7 實(shí)驗(yàn)平面圖

3 實(shí)驗(yàn)結(jié)果與分析

為了評(píng)估MCSLoc的性能，實(shí)驗(yàn)在真實(shí)3層實(shí)驗(yàn)樓建立實(shí)驗(yàn)場(chǎng)地，實(shí)驗(yàn)樓3D平面圖如圖7所示，總面積4 800 m，其中1樓樓層高4.3 m，2樓樓層高2.64 m，3樓樓層高2.48 m.由室內(nèi)平面圖轉(zhuǎn)換的語(yǔ)義地圖如圖8所示，共158個(gè)節(jié)點(diǎn).使用了4種不同類型的安卓智能手機(jī)進(jìn)行實(shí)驗(yàn)，分別是:小米5 s、小米8、華為Mate 20 Pro、華為Mate 30 Pro.實(shí)驗(yàn)過(guò)程中，為了盡可能模擬眾包場(chǎng)景，眾包參與者手持智能手機(jī)隨機(jī)從不同的位置(不指定起始位置)開始行走.采集10位眾包參與者使用不同型號(hào)手機(jī)的80條用戶軌跡數(shù)據(jù).其中加速度傳感器的采集頻率為250 Hz，氣壓計(jì)的采樣頻率為100 Hz，陀螺儀和WiFi接收器的采樣頻率為1 Hz，實(shí)驗(yàn)區(qū)域記錄可檢測(cè)到15個(gè)AP.

Fig. 8 Semantic map of experimental building圖8 實(shí)驗(yàn)樓語(yǔ)義地圖

3.1 傳感器數(shù)據(jù)所屬樓層劃分

由2.2節(jié)可知，MCSLoc利用軌跡高度和時(shí)間戳劃分傳感器數(shù)據(jù)到所屬樓層.一條軌跡的高度測(cè)量情況如圖9所示，虛線為真實(shí)高度，實(shí)線為KF_FCD方法測(cè)量高度，由圖9可知，KF_FCD方法測(cè)量的高度幾乎與真實(shí)高度一致，誤差圖如圖10所示，平均誤差為0.11 m，最大誤差為0.31 m.由于實(shí)驗(yàn)大樓樓層高度已知，1樓高度范圍為0～4.3 m，2樓為4.3～6.94 m，3樓為6.94～9.42 m.根據(jù)眾包參與者每一時(shí)刻測(cè)量的高度所屬的樓層范圍判定每時(shí)刻所屬樓層，結(jié)合時(shí)間戳劃分加速度傳感器、陀螺儀以及WiFi接收器的數(shù)據(jù)到各個(gè)樓層.需要說(shuō)明的是，實(shí)驗(yàn)未對(duì)樓梯之間的信號(hào)進(jìn)行處理，因此上下樓過(guò)程中的采集的傳感器數(shù)據(jù)為無(wú)用數(shù)據(jù)，已將其剔除.

Fig. 9 Height measured by KF_FCD method圖9 KF_FCD測(cè)量高度

Fig. 10 Height error measured by KF_FCD method圖10 KF_FCD高度測(cè)量誤差

3.2 拐角檢測(cè)算法與子段分析

實(shí)驗(yàn)選擇代表性軌跡進(jìn)行分析說(shuō)明，拐角檢測(cè)算法檢測(cè)到9個(gè)拐角，即可劃分10個(gè)子段，利用拐角檢測(cè)算法獲取的拐彎方向以及利用加速度值獲取的步數(shù)、子段長(zhǎng)度與真實(shí)值對(duì)比如表1所示:

Table 1 Comparison of Measured Value and Real Value of Sub Segment

該軌跡中，實(shí)際總步數(shù)為233步，檢測(cè)總步數(shù)為236步，根據(jù)每一子段的步數(shù)的誤差，步數(shù)檢測(cè)精度為97%;該層軌跡總長(zhǎng)度為90 m，測(cè)量總長(zhǎng)度為91.27 m，子段長(zhǎng)度平均誤差為0.905 m，拐彎方向檢測(cè)精度為100%.

3.3 TM-Viterbi地圖匹配算法分析與定位精度分析

為驗(yàn)證TM-Viterbi地圖匹配算法性能，實(shí)驗(yàn)分別獲取20條、40條、60條、80條軌跡的子段序列，將傳統(tǒng)的Viterbi算法與TM-Viterbi算法進(jìn)行對(duì)比.匹配精度如圖11所示.當(dāng)軌跡條數(shù)在40～80條時(shí)，傳統(tǒng)的Viterbi算法匹配精度穩(wěn)定在66%左右，而TM-Viterbi算法匹配精度穩(wěn)定在85%左右，精度將近提高了20個(gè)百分點(diǎn).由圖11可知，當(dāng)軌跡條數(shù)足夠多時(shí)，TM-Viterbi算法可以獲得足夠高的地圖匹配精度.

Fig. 11 Accuracy comparison of Viterbi map matching algorithm圖11 Viterbi地圖匹配算法精度對(duì)比

為驗(yàn)證構(gòu)建的多樓層指紋庫(kù)的性能，實(shí)驗(yàn)采集了400個(gè)不同樓層不同待定位點(diǎn)的RSSI值進(jìn)行精度分析.定位過(guò)程包括基于多分類LDA樓層判別與基于WKNN算法的2維坐標(biāo)獲取.由圖12可知，平均定位誤差為1.87 m，82%的定位誤差在3 m以內(nèi)，91%定位誤差在5 m以內(nèi)，定位誤差主要是地圖匹配算法誤差導(dǎo)致的多樓層指紋庫(kù)“指紋-位置”根本性錯(cuò)位偏差.由于MCSLoc指紋庫(kù)構(gòu)建方法可操作性強(qiáng)、成本低，可實(shí)現(xiàn)指紋庫(kù)的定期更新，有效減少室內(nèi)環(huán)境變化導(dǎo)致RSSI指紋的不穩(wěn)定波動(dòng)性對(duì)定位精度的影響，分析可知，構(gòu)建的基于眾包的多樓層指紋庫(kù)可以滿足室內(nèi)基本定位需求.

Fig. 12 Cumulative distribution function of location error in multi-floor fingerprint database圖12 多樓層指紋庫(kù)定位誤差累積分布圖

步數(shù)檢測(cè)精度∕%子段長(zhǎng)度平均誤差∕m拐彎方向檢測(cè)精度∕%970.905100

3.4 系統(tǒng)對(duì)比

本文將提出的基于眾包的多樓層定位方法-MCSLoc從定位精度、實(shí)驗(yàn)面積、是否需要室內(nèi)地圖以及是否為多樓層4個(gè)方面與其他前沿的基于眾包的WiFi指紋定位方法進(jìn)行了比較.如表3所示:

Table 3 Comparison of System Performance表3 系統(tǒng)性能對(duì)比

LiFS達(dá)到的是房間級(jí)別的定位精度，MCSLoc的定位精度明顯優(yōu)于LiFS系統(tǒng).Zee利用拓?fù)鋱D和粒子濾波限制行人軌跡，但粒子濾波比較耗時(shí)，不適合運(yùn)行在計(jì)算能力有限的智能手機(jī)平臺(tái).定位精度與實(shí)驗(yàn)面密切相關(guān)，與RCILS和Ma等人方法相比，MCSLoc部署范圍與實(shí)驗(yàn)場(chǎng)景面積相之較大，結(jié)果更具說(shuō)服力；UnLoc定位精度較高，但是需要在室內(nèi)環(huán)境中部署一定數(shù)量的錨節(jié)點(diǎn)，這必然會(huì)增加定位成本.除此之外，MCSLoc針對(duì)多樓層場(chǎng)景，更加符合當(dāng)前市場(chǎng)定位需求，應(yīng)用范圍更廣.

4 結(jié)束語(yǔ)

本文基于眾包提出了一種融合智能手機(jī)傳感器數(shù)據(jù)的多樓層指紋庫(kù)構(gòu)建方法MCSLoc，根據(jù)行人室內(nèi)行走特點(diǎn)，設(shè)計(jì)分段式軌跡獲取方法，建立HMM模型，設(shè)計(jì)改進(jìn)的Viterbi算法、TM-Viterbi算法，將用戶軌跡與語(yǔ)義地圖匹配，獲取絕對(duì)位置，有效構(gòu)建多樓層指紋庫(kù).與其他經(jīng)典的基于眾包的定位方法相比，本文提出的方法效率更高、成本更低、適用范圍更廣.實(shí)驗(yàn)結(jié)果表明，MCSLoc可達(dá)到米級(jí)定位精度，具有良好的穩(wěn)定性.

未來(lái)，進(jìn)一步的研究包括：設(shè)計(jì)眾包參與者運(yùn)動(dòng)狀態(tài)檢測(cè)算法，識(shí)別參與者快走、慢走、跑步等運(yùn)動(dòng)狀態(tài)；考慮眾包參與者智能手機(jī)的異質(zhì)性；將語(yǔ)義地圖的主路徑抽取模式轉(zhuǎn)成網(wǎng)格化抽取模式，拓展應(yīng)用場(chǎng)景至大型空曠室內(nèi)場(chǎng)所.

作者貢獻(xiàn)聲明

：羅娟提出研究思路和創(chuàng)新點(diǎn)，進(jìn)行論文模型方法設(shè)計(jì)和文字修改;章翠君設(shè)計(jì)研究方案，進(jìn)行實(shí)驗(yàn)和數(shù)據(jù)分析,起草論文；王純協(xié)助進(jìn)行實(shí)驗(yàn)和論文修訂.