樓喜中，方 俊，陟 力

(中國(guó)計(jì)量大學(xué) 信息工程學(xué)院，浙江 杭州 310018)

維特比算法的一種室內(nèi)地磁導(dǎo)航方法

樓喜中，方 俊，陟 力

(中國(guó)計(jì)量大學(xué) 信息工程學(xué)院，浙江 杭州 310018)

慣性導(dǎo)航系統(tǒng)是目前室內(nèi)定位和導(dǎo)航領(lǐng)域一項(xiàng)非常重要的技術(shù)，但是傳統(tǒng)慣性導(dǎo)航系統(tǒng)中是利用算法融合地磁羅盤(pán)及陀螺儀等數(shù)據(jù)，進(jìn)而提高相對(duì)位置的精度，但卻無(wú)法修正已經(jīng)產(chǎn)生的誤差.所以傳統(tǒng)慣性導(dǎo)航系統(tǒng)在內(nèi)部構(gòu)造復(fù)雜的室內(nèi)很容易出現(xiàn)走錯(cuò)房間，穿越墻體等錯(cuò)誤路徑.為了解決這些問(wèn)題，提出一種基于維特比算法的室內(nèi)導(dǎo)航方法,利用自建室內(nèi)地磁數(shù)字地圖結(jié)合維特比算法，動(dòng)態(tài)計(jì)算可能路徑.利用維特比算法特性提高了輸出路徑的糾錯(cuò)能力，可有效排除錯(cuò)誤路徑的干擾.本導(dǎo)航方法能有效避免穿墻錯(cuò)誤路徑的出現(xiàn)，更加符合實(shí)際行走路徑.試驗(yàn)結(jié)果表明，相對(duì)傳統(tǒng)慣性導(dǎo)航系統(tǒng)，它在復(fù)雜室內(nèi)環(huán)境下進(jìn)入正確房間的準(zhǔn)確率提高了23%.

慣性導(dǎo)航系統(tǒng)；維特比算法；地磁數(shù)字地圖

導(dǎo)航技術(shù)儼然成為現(xiàn)代社會(huì)生活中一項(xiàng)非常重要的技術(shù)，近年來(lái)，關(guān)于室內(nèi)導(dǎo)航的研究課題也越來(lái)越多.室內(nèi)導(dǎo)航技術(shù)層出不窮，有基于無(wú)線(xiàn)電的導(dǎo)航技術(shù)，如WLAN導(dǎo)航[1]、RFID導(dǎo)航[2-3]、GPS導(dǎo)航[4-6]和超寬帶定位技術(shù)等.但是這些導(dǎo)航技術(shù)前期的布置成本高，在室內(nèi)極易因?yàn)榻ㄖ锏膬?nèi)部構(gòu)造復(fù)雜從而造成信號(hào)干擾，產(chǎn)生誤差.

近年來(lái)，慣性導(dǎo)航技術(shù)成為熱點(diǎn)，它不需要大量布置成本，自主性強(qiáng)、抵抗外界干擾能力強(qiáng)等特點(diǎn)吸引眾多學(xué)者和機(jī)構(gòu)的研究.它有捷聯(lián)慣導(dǎo)系統(tǒng)和平臺(tái)式慣導(dǎo)系統(tǒng)[7].慣性導(dǎo)航系統(tǒng)是利用慣性元件來(lái)測(cè)量運(yùn)動(dòng)人體的加速度，經(jīng)過(guò)積分和運(yùn)算得到速度和位置，從而達(dá)到對(duì)運(yùn)動(dòng)人體的定位和導(dǎo)航.這種技術(shù)非常依賴(lài)精確的步長(zhǎng)、航向值等信息的收集，同時(shí)通過(guò)卡爾曼濾波[8]和粒子濾波[9]等算法減小傳感器帶來(lái)的誤差，提高步長(zhǎng)等數(shù)據(jù)的精度.

上述傳統(tǒng)的慣性導(dǎo)航方法都是基于硬件誤差的減小和利用算法建立誤差模型提高數(shù)據(jù)精度的方式提高導(dǎo)航準(zhǔn)確性，但是在進(jìn)入極易混淆的相鄰房間的時(shí)候，受誤差的影響，會(huì)產(chǎn)生進(jìn)錯(cuò)房間等錯(cuò)誤路徑，并在后續(xù)的行走過(guò)程中發(fā)生穿越墻體的情況.本文通過(guò)對(duì)導(dǎo)航區(qū)域自建地磁數(shù)字地圖，結(jié)合維特比算法，利用維特比算法中度量值計(jì)算判斷路徑可能性，拋棄無(wú)效路徑的方式有效避免穿越墻體的路徑產(chǎn)生.該方法結(jié)合慣性導(dǎo)航系統(tǒng)，提高導(dǎo)航系統(tǒng)的糾錯(cuò)能力.由仿真試驗(yàn)結(jié)果表明，相較傳統(tǒng)慣性導(dǎo)航技術(shù)中依賴(lài)高精度數(shù)據(jù)完成導(dǎo)航，本文提出的方法作為輔助手段可有效避免穿越墻體等錯(cuò)誤路徑的產(chǎn)生.

1 基于維特比算法的室內(nèi)導(dǎo)航

1.1 地磁數(shù)字地圖

由于地磁是遍布在近地空間的，而且地磁的數(shù)值大小相對(duì)比較固定.雖然室內(nèi)空間布局和內(nèi)部構(gòu)造會(huì)對(duì)地磁大小產(chǎn)生影響，但是我們?cè)谥谱鞯卮诺貓D的時(shí)候是將這些影響一起記錄進(jìn)去的.同時(shí)室內(nèi)空間對(duì)地磁的影響也增加了地磁地圖的磁場(chǎng)特征，有利于算法對(duì)路徑的篩選.制作地磁數(shù)字地圖具體步驟為：

1)利用慣性導(dǎo)航設(shè)備中的高精度磁傳感器在室內(nèi)劃分好的網(wǎng)格點(diǎn)交點(diǎn)處收集磁場(chǎng)數(shù)據(jù)；

2)慣性導(dǎo)航設(shè)備在室內(nèi)劃分好的網(wǎng)格點(diǎn)交點(diǎn)處停留一段時(shí)間s，再將慣性導(dǎo)航系統(tǒng)中的磁場(chǎng)強(qiáng)度值截取中間若干個(gè)，若干個(gè)的磁場(chǎng)強(qiáng)度值組成一個(gè)集合M，從而計(jì)算出集合M的均值Ma=M/Ms，Ms表示集合M的個(gè)數(shù)；

3)慣性導(dǎo)航系統(tǒng)將得到集合M的均值Ma依次錄入到磁場(chǎng)數(shù)據(jù)中的網(wǎng)格點(diǎn)交點(diǎn)中，從而完成自建立網(wǎng)格型的磁場(chǎng)數(shù)據(jù)庫(kù).如圖1，其中地磁地圖中X軸代表實(shí)際室內(nèi)空間的長(zhǎng)度，Y軸代表實(shí)際室內(nèi)空間的寬度，Z軸代表實(shí)際室內(nèi)空間磁場(chǎng)強(qiáng)度大小.數(shù)字地圖中坐標(biāo)(dx,dy,dz)中dz為二維平面位置(dx,dy)的磁場(chǎng)強(qiáng)度大小.dx表示X軸坐標(biāo)，dy表示Y軸坐標(biāo).

圖1 地磁數(shù)字地圖示意圖Figure 1 Magnetic field digital schematic map

1.2 維特比算法

維特比算法是一種在數(shù)字通信中經(jīng)常使用的譯碼算法，于1976年由維特比(Viterbi)提出.作為隱馬爾科夫模型[10]基本算法之一，維特比算法主要解決的問(wèn)題就是在給定模型的情況下，在對(duì)應(yīng)的觀測(cè)值序列中找出最優(yōu)狀態(tài)序列[11].所以它是一種最優(yōu)的動(dòng)態(tài)規(guī)劃算法，在眾多路徑當(dāng)中找出最優(yōu)路徑，并且能夠回溯輸出整條路徑.在本文中，將它應(yīng)用在解決室內(nèi)導(dǎo)航中，利用其尋找最優(yōu)路徑的特性，動(dòng)態(tài)規(guī)劃人體行走路徑.

維特比算法完成動(dòng)態(tài)規(guī)劃的迭代計(jì)算過(guò)程如下：

(1)

(2)

δt(j)表示在觀察時(shí)刻t正處在狀態(tài)j產(chǎn)生出的路徑的最大概率即度量值，Ψt(j)表示一個(gè)狀態(tài)值，該值由上一狀態(tài)計(jì)算產(chǎn)生.

同時(shí)我們還能回溯最優(yōu)路徑，回溯公式為

(3)

1.3 基于維特比算法的導(dǎo)航方法

本方法通過(guò)提供基礎(chǔ)磁場(chǎng)數(shù)據(jù)計(jì)算每條可能路徑的度量值，輸出其中最大度量值對(duì)應(yīng)的路徑作為室內(nèi)導(dǎo)航結(jié)果.

在傳統(tǒng)慣性導(dǎo)航系統(tǒng)中，人行走的軌跡路徑取決于人體航向值、步長(zhǎng)和步數(shù)三個(gè)數(shù)據(jù).其算法的基本原理如圖2，(x0,y0)為行走起始點(diǎn)，(xi,yi)為行走的第i步點(diǎn)位置，H為人體行走航向值，航向值為繞Z軸旋轉(zhuǎn)角度，初始角度為設(shè)備中默認(rèn)值，S為步長(zhǎng).利用這些信息可以推算人體行走路徑.

圖2 傳統(tǒng)慣性導(dǎo)航系統(tǒng)軌跡推算Figure 2 Traditional track estimate of inertial navigation

在此基礎(chǔ)上的可能路徑計(jì)算方式為：

1)根據(jù)人體航向值大小所在區(qū)間判斷人體行走方向，因?yàn)榉抡嬖囼?yàn)中使用的設(shè)備默認(rèn)0°方向?yàn)檎保詰T性導(dǎo)航系統(tǒng)中預(yù)設(shè)45°到135°為向東方向，135°到225°為向南方向，225°到315°為向西方向，315°到360°和0°到45°為向北方向.

3)依次計(jì)算可能位置，輸出路徑.因此可以實(shí)時(shí)計(jì)算出人體在行走過(guò)程中產(chǎn)生的所有可能路徑.

圖3 基于維特比算法慣性導(dǎo)航軌跡推算Figure 3 Inertial navigation track estimate base on Viterbi algorithm

圖4 基于維特比算法導(dǎo)航示意圖Figure 4 Navigation algorithm base on Viterbi algorithm

由此可以知道，如果一條可能路徑偏離了實(shí)際路徑，那么其地磁場(chǎng)序列和給定模型的序列誤差增大，導(dǎo)致其度量值增大，這條錯(cuò)誤的路徑也就越容易被舍棄.而最貼近實(shí)際路徑的可能路徑會(huì)在排序中越來(lái)越高.為了防止可能路徑計(jì)算中遺漏正確路徑，導(dǎo)致最終偏離實(shí)際路線(xiàn)，出現(xiàn)進(jìn)錯(cuò)房間，穿越墻體等錯(cuò)誤路徑出現(xiàn)，需要在算法中記錄室內(nèi)極易混淆的區(qū)域，如兩個(gè)房間緊挨的區(qū)域.在此區(qū)域中，增加可能路徑方向上的選擇性，如圖5.

圖5 復(fù)雜區(qū)域可能位置選擇示意圖Figure 5 Select a possible location of complex regions

即保留前進(jìn)方向上的下一位置點(diǎn)和與之垂直的方向上的相鄰四個(gè)點(diǎn)，同時(shí)保留與路徑前一位置相鄰兩點(diǎn)，共7個(gè)位置作為當(dāng)前可能位置.

由于傳統(tǒng)導(dǎo)航方法中，路徑輸出始終只有一條，一旦出現(xiàn)偏離現(xiàn)象，后面路徑的規(guī)劃會(huì)始終基于此錯(cuò)誤路徑之上，所以無(wú)法糾正自己的錯(cuò)誤.但在本方法中，算法保留了正確路徑，后面路徑的規(guī)劃會(huì)同時(shí)基于這些可能路徑之上，進(jìn)入正確房間的路徑的排序會(huì)越來(lái)越高，同時(shí)錯(cuò)誤路徑將逐漸被舍棄.

此外，由于本導(dǎo)航方法中引入了地磁地圖，可以將室內(nèi)不可能到達(dá)區(qū)域的地磁強(qiáng)度設(shè)置為零，如墻體，柱體內(nèi)部.當(dāng)可能路徑到達(dá)這些區(qū)域之后，當(dāng)前位置的地磁誤差會(huì)非常大，導(dǎo)致其度量值非常大，這條錯(cuò)誤路徑也會(huì)被舍棄.

錯(cuò)誤路徑的舍棄在算法中能夠有效排除干擾，使后面可能路徑的計(jì)算能夠基于正確路徑，輸出最優(yōu)結(jié)果.

2 仿真試驗(yàn)

為了保證試驗(yàn)數(shù)據(jù)的準(zhǔn)確性，本文中使用的慣性導(dǎo)航模塊是DRM4000L.制作相關(guān)室內(nèi)空間的地磁數(shù)字地圖方法如下：我們將導(dǎo)航模塊綁在腰間，按照事先劃分好的網(wǎng)格點(diǎn)，在上面停留一段時(shí)間s，點(diǎn)與點(diǎn)之間的距離設(shè)置為0.6米.為保證網(wǎng)格點(diǎn)上取到的地磁數(shù)據(jù)的準(zhǔn)確性，我們停留5 s.將慣性導(dǎo)航模塊設(shè)置為每0.5 s記錄一次.因?yàn)殚_(kāi)始檢測(cè)地磁和結(jié)束時(shí)的移動(dòng)可能會(huì)帶來(lái)誤差，所以我們只取中間的5組地磁數(shù)據(jù)，根據(jù)Ma=M/Ms計(jì)算得出當(dāng)前網(wǎng)格點(diǎn)的地磁數(shù)據(jù).依次記錄，完成地磁數(shù)字地圖的制作，如圖6.

圖6 地磁數(shù)字地圖Figure 6 Magnetic field digital map

在仿真試驗(yàn)中，慣性導(dǎo)航系統(tǒng)中預(yù)設(shè)45°到135°為向東方向，135°到225°為向南方向，225°到315°為向西方向，315°到360°和0°到45°為向北方向，當(dāng)初始位置A為(11,4)，同時(shí)在計(jì)算可能路徑時(shí)，步數(shù)發(fā)生更新，根據(jù)人體航向值判斷，A后的第一步為向東.此時(shí)在地圖中，(11,3),(11,4),(11,5)都是第二步可能落下的位置，系統(tǒng)會(huì)記錄可能路徑，同時(shí)計(jì)算度量值.

為了驗(yàn)證本方法的性能，在測(cè)試時(shí)，測(cè)試人員的行走路線(xiàn)要盡量復(fù)雜，所以在試驗(yàn)中，要求測(cè)試人員按照Z(yǔ)字型行走.同時(shí)要求走進(jìn)兩個(gè)極易混淆的相鄰教室，兩個(gè)教室之間只有一道墻的距離.一共進(jìn)行200組試驗(yàn)，分兩種行走路線(xiàn)，其中100組的行走路線(xiàn)為(10,4)、(20,1)、(30,6)、(40,1)、(41,6)、(41,12)、(50,12).另100組的行走路線(xiàn)為(10,4)、(20,6)、(30,1)、(40,6)，(41,6)、(41,12)、(50,12).點(diǎn)與點(diǎn)之間按照直線(xiàn)行走.根據(jù)上面方法描述的特性，在行走過(guò)程中，慣性導(dǎo)航系統(tǒng)輸出的原始路徑若是發(fā)生穿墻行為是不會(huì)糾正自己的.但是本方法中，若發(fā)生穿墻行為，最終算法會(huì)自動(dòng)拋棄錯(cuò)誤的幸存路徑，驗(yàn)證本方法的糾錯(cuò)能力.隨著測(cè)試人員的行走，可能路徑的數(shù)量會(huì)急速增加，需要設(shè)置合理的幸存路徑條數(shù)，將其余路徑排除.試驗(yàn)中各計(jì)算設(shè)置32、64、128、256、512條幸存路徑的性能.

圖7 仿真試驗(yàn)結(jié)果圖Figure 7 Simulation results

通過(guò)上面的200組試驗(yàn)，傳統(tǒng)慣性導(dǎo)航算法成功進(jìn)入131次，成功率為65.5%.維特比算法的導(dǎo)航方法成功進(jìn)入177次，成功率為88.5%.不同幸存路徑最后正確率依次為51.5%，71%，88.5%，89.5%，90.5%.由于設(shè)置256條和512條幸存路徑對(duì)最終準(zhǔn)確率的提升并不明顯，為了提高計(jì)算性能，選擇128條幸存路徑的試驗(yàn)結(jié)果作為最終試驗(yàn)結(jié)果.我們發(fā)現(xiàn)相較于傳統(tǒng)慣性導(dǎo)航算法，基于維特比算法的導(dǎo)航方法在復(fù)雜室內(nèi)環(huán)境下進(jìn)入正確房間的準(zhǔn)確率提高了23%.圖7為其中一組試驗(yàn)仿真結(jié)果，由圖7可以看出，慣性導(dǎo)航系統(tǒng)輸出路徑顯示從走廊進(jìn)入A教室后穿越墻體進(jìn)入B教室，這是和圖中實(shí)際行走路線(xiàn)不相符的錯(cuò)誤路徑.在兩個(gè)相鄰的教室中還是發(fā)生混淆.而度量值最大的可能路徑區(qū)分出了兩個(gè)教室，在仿真輸出的幸存路徑中也有走入A教室的，但是由于偏離實(shí)際路徑，在后面的行走過(guò)程中逐漸被舍棄了.同時(shí)行走軌跡基本符合實(shí)際行走路線(xiàn).有效克服傳統(tǒng)導(dǎo)航系統(tǒng)中因?yàn)檎`差因素的影響進(jìn)錯(cuò)房間并發(fā)生穿墻的情況，同時(shí)解決了傳統(tǒng)慣性導(dǎo)航系統(tǒng)中只依賴(lài)精確步長(zhǎng)和航向值等信息才能進(jìn)行室內(nèi)導(dǎo)航的缺點(diǎn)，提高室內(nèi)導(dǎo)航糾錯(cuò)能力.

3 結(jié) 語(yǔ)

本文中所述的基于維特比算法的室內(nèi)導(dǎo)航方法的優(yōu)缺點(diǎn)如下所述.

優(yōu)點(diǎn)：1)不嚴(yán)重依賴(lài)精確步長(zhǎng)和航向值等信息；2)具有糾錯(cuò)能力，能夠拋棄錯(cuò)誤路徑獲得最優(yōu)路徑.

缺點(diǎn)：1)和實(shí)際路徑之間的誤差較大；2)路徑方向改變不敏感.鑒于以上缺點(diǎn)，我們需要對(duì)本方法做進(jìn)一步的改進(jìn)，以便能夠在實(shí)際工程應(yīng)用中得到更廣泛的運(yùn)用.

[1] ZOU Han, JIANG Hao, LU Xiaoxuan, et al. An online sequential extreme learning machine approach to WiFi based indoor positioning[C]//2014 IEEE World Forum on Internet of Things (WF-IoT). Seoul: IEEE,2014:111-116.

[2] MILLER L E, BRYNER N P, FRANCIS M H, el al. RFID-assisted indoor localization and communication for first responders[C]//European Conference on Antennas & Propagation. Nice: IEEE,2006:1-6.

[3] 韓晶.基于RFID標(biāo)簽的定位原理和技術(shù)[J].電子科技,2011,24(7):64-67. HAN Jin. Position principles and location techniques based on RFID tags[J]. Electronic and Technology,2011,24(7):64-67.

[4] 李天文.GPS原理及應(yīng)用[M].北京:科學(xué)出版社,2010:18-21.

[5] 施閣,盧江麗,孫延偉,等.航模動(dòng)力及飛行環(huán)境無(wú)線(xiàn)實(shí)時(shí)監(jiān)測(cè)系統(tǒng)設(shè)計(jì)[J].中國(guó)計(jì)量學(xué)院學(xué)報(bào),2009,20(1):22-26. SHI Ge, LU Jiangli, SUN Yanwei, el al. Aeromodelling's power and flight environment wireless real-time monitoring system[J]. Journal of China University of Metrology,2009,20(1):22-26.

[6] 雷波,陳華德,李青,等.基于動(dòng)態(tài)差分GPS的滑坡位移監(jiān)測(cè)系統(tǒng)[J].中國(guó)計(jì)量學(xué)院學(xué)報(bào),2011,22(63):203-207. LEI Bo, CHENG Huade, LI Qing, el al. Design of landslide displacement monitoring system based on dynamic differential GPS[J]. Journal of China University of Metrology,2011,22(63):203-207.

[7] TITTERTON D H, WESTON J L. Strapdown inertial navigation technology[J]. Aerospace & Electronic Systems Magazine IEEE,1997,20(7):33-34.

[8] GREWAL M S, ANDREWS A P. Kalman Filtering Theory and Practice Using MATLAB[M]. 3th ed.[S. 1.]: Circuit Theory & Design.2001:100-123.

[9] RISTIC B, ARULAMPALAM S, GORDON N. Beyond the kalman filter-particle filters for tracking applications[J]. IEEE Trans of Aerospace & Electronic Systems,2004,19(7):37-38.

[10] RABINER L. A tutorial on hidden markov models and selected applications in speech recognition[J]. Proceedings of the IEEE,1989,77(2):257-286.

[11] 劉功生,張春良,岳夏.基于HMM算法體系的逆維特比算法理論研究[J].機(jī)電工程技術(shù),2014,43(11):7-10. LIU Gongsheng, ZHANG Chunliang, YUE xia. Research on theory of inv-viterbi algorithm based on the basic algorithm system of HMM[J]. M&E Engineering Technology,2014,43(11):7-10.

An indoor magnetic navigation method based on Viterbi algorithm

LOU Xizhong, FANG Jun, ZHI li

(College of Information Engineering, China Jiliang University, Hangzhou 310018, China)

The inertial navigation system is the most important technology of indoor navigation and positioning. The traditional inertial navigation system that uses the algorithm merge magnetic compass, gyroscopes and other data to improve the accuracy of a relative position can not correct the errors. Therefore, in a complex internal structure, it is easy to walk into a wrong room, walk through a wall and so on. In order to solve these problems, a kind of interior navigation method based on the Viterbi algorithm by using the self-built indoor digital maps to dynamically calculate possible paths was proposed. The Viterbi algorithm could improve the error correction capability and could effectively eliminate interferences caused by wrong paths. This navigation method could effectively avoid wrong paths through the wall appearing. Compared with the conventional inertial navigation system, the accuracy of the walk in correct rooms in complex indoor environments increased by 23%.

inertial navigation system; Viterbi algorithm; magnetic digital map

2096-2835(2016)04-0429-06

10.3969/j.issn.2096-2835.2016.04.013

2016-09-27 《中國(guó)計(jì)量大學(xué)學(xué)報(bào)》網(wǎng)址：zgjl.cbpt.cnki.net

TN96

A