基于D-S證據(jù)理論的室內(nèi)組合定位算法

王續(xù)喬,王瑾琨

中國民航大學(xué) 機(jī)器人研究所,天津 300300)(*通信作者電子郵箱wang_xu_qiao@163.com)

基于D-S證據(jù)理論的室內(nèi)組合定位算法

王續(xù)喬*,王瑾琨

中國民航大學(xué) 機(jī)器人研究所,天津 300300)(*通信作者電子郵箱wang_xu_qiao@163.com)

在非定位系統(tǒng)部署信標(biāo)的大體量場區(qū)環(huán)境下,針對基于位置的服務(wù)(LBS)的室內(nèi)定位需求問題, 提出了一種基于D-S證據(jù)推理理論的無線局域網(wǎng)/慣性測量組件(WiFi/IMU)組合定位算法。該算法首先建立各接入點(AP)單點的信號強(qiáng)度傳輸模型,并利用卡爾曼濾波對接收到的信號強(qiáng)度指示(RSSI)值進(jìn)行去噪修正處理;然后通過D-S證據(jù)理論對實時采集的WiFi信號強(qiáng)度、偏航角、各軸加速度的多源信息進(jìn)行融合處理,選取可信度高的指紋區(qū)塊;最后通過加權(quán)K近鄰(WKNN)算法得到終端估算位置。單元場區(qū)仿真實驗結(jié)果顯示,最大誤差2.36 m,綜合平均誤差1.27 m,驗證了該算法的可行性與有效性；且誤差累計概率分布在小于等于典型距離時為88.20%,優(yōu)于懲罰參數(shù)C支持向量回歸機(jī)(C-SVR)的70.82%和行人航跡推算(PDR)算法的67.85%。進(jìn)一步地,算法在全場區(qū)實際實驗中也表現(xiàn)出了良好的環(huán)境適用性。

無線局域網(wǎng);室內(nèi)定位;接收信號強(qiáng)度指示;位置指紋;D-S證據(jù)理論;加權(quán)K近鄰

0 引言

無線通信技術(shù)和網(wǎng)絡(luò)終端的迅猛發(fā)展及多媒體數(shù)據(jù)業(yè)務(wù)的快速增加擴(kuò)大了人們對于基于位置的服務(wù)(Location Based Service, LBS)的需求,較室外更為復(fù)雜的室內(nèi)環(huán)境中,常常也需要為用戶提供可靠的位置信息[1]。機(jī)場航站樓是值機(jī)托運、安檢通行、候機(jī)登機(jī)等民用航空業(yè)務(wù)集散交互的大型關(guān)鍵場所,各地場區(qū)建設(shè)規(guī)模通常較大,而其中問詢臺、值機(jī)島、安檢區(qū)、餐飲商店、公共服務(wù)點位的部署類型、方式、位置通常不盡相同。旅客出入場區(qū)能夠快速獲取本體位置、目標(biāo)位置,進(jìn)而便捷高效地辦理相關(guān)業(yè)務(wù),已成為當(dāng)前航空出行的必要需求。目前,樓內(nèi)場區(qū)獲取位置信息的方式主要依賴固定點位引導(dǎo)標(biāo)識牌及以人工方式問詢服務(wù)臺,常常因表述抽象、效率低下等問題給旅客出行帶來不便。因此,場區(qū)定位已成為面向航空旅客便捷出行提供服務(wù)保障的關(guān)鍵,有待解決。

室內(nèi)定位技術(shù)有多種分類方法,按照測量技術(shù)的不同進(jìn)行分類:基于到達(dá)時間(Time of Arrival, TOA)測量的定位、基于到達(dá)時間差(Time Difference of Arrival, TDOA)測量的定位、基于達(dá)到角度(Arrival of Angle, AOA)測量的定位以及基于接收信號強(qiáng)度(Received Signal Strength Indication, RSSI)測量的定位。其中,TOA定位要求接入點與終端具備非常精準(zhǔn)的時鐘同步,TDOA定位則要求終端配備時間測量硬件,且此兩種定位方式均需部署專項定位信標(biāo),而航站樓場區(qū)安全標(biāo)準(zhǔn)高、建設(shè)體量大,設(shè)備部署需要管理部許可及調(diào)整樓區(qū)建設(shè),極大地增加了定位成本;航站樓場區(qū)存在信號非視距傳播現(xiàn)象,AOA定位會存在較大誤差;RSSI定位對外在配置要求不高,抗干擾性也較強(qiáng),而且WLAN網(wǎng)絡(luò)接入點(Access Point, AP)遍布航站樓內(nèi),相對于基于藍(lán)牙、ZigBee、RFID(Radio Frequency Identification)、UWB(Ultra WideBand)、紅外線、超聲波等信號進(jìn)行定位[2-6],基于RSSI的WiFi室內(nèi)定位方式可有效利用非定位部署AP,對航站樓場區(qū)具有良好的環(huán)境適用性。

基于RSSI測量的定位方式通常分為信號傳輸損耗法和位置指紋定位法[7-8]。傳輸損耗法要求精確定義信號傳播模型,人員和障礙物的移動都會影響傳輸特性,航站樓室內(nèi)場區(qū)環(huán)境動態(tài)變化頻繁,對于以該種方式進(jìn)行定位極為不利;位置指紋法主要工作體現(xiàn)在離線訓(xùn)練和在線定位兩個階段,構(gòu)建好位置指紋數(shù)據(jù)庫和采用合適的定位匹配算法是進(jìn)行該種定位的關(guān)鍵。

現(xiàn)有利用位置指紋進(jìn)行定位的算法主要包括加權(quán)K近鄰(WeightedK-Nearest Neighbor, WKNN)算法、人工神經(jīng)網(wǎng)絡(luò)(Artificial Neural Network，ANN)算法、支持向量機(jī)(Support Vector Machine, SVM)算法、最大似然(Maximum Likelihood, ML)算法等。其中,WKNN算法[9]執(zhí)行時間短,但僅依賴鄰近點信號強(qiáng)度值,容易出現(xiàn)漂移,定位準(zhǔn)確度不高；文獻(xiàn)[10]提出的基于神經(jīng)網(wǎng)絡(luò)的定位算法，文獻(xiàn)[11-12]提出的基于支持向量機(jī)的定位算法均不同程度地提高了定位精度,但在處理不確定性問題上效果欠佳；文獻(xiàn)[13]提出的最大似然算法以RSSI值的概率分布作為位置指紋特征,需要建立準(zhǔn)確的RSSI概率分布圖；此外,文獻(xiàn)[14-15]提出了通過移動終端中的傳感器判斷用戶步態(tài)進(jìn)行輔助定位,但消減慣性組件累積誤差也使得該種混合定位的方式受到場景局限。

在實際航站樓室內(nèi)場區(qū),無線信號在傳播過程中會受到多徑效應(yīng)、陰影效應(yīng)的影響,在同一個位置點接收AP的信號強(qiáng)度值往往表現(xiàn)出復(fù)雜的時變特性,本文提出將WiFi信號與慣性傳感數(shù)據(jù)融合處理,基于D-S(Dempster/Shafer)證據(jù)理論推理選擇出可信度高的指紋區(qū)塊,同時對WKNN加權(quán)值進(jìn)行修正,驗證了算法的有效性,針對定位誤差的概率問題,與行人航跡推算(Pedestrian Dead Reckoning, PDR)、支持向量回歸機(jī)(Support Vector Regression, SVR)等相關(guān)算法進(jìn)行了對比探討。

1 算法原理及方案

1.1 離線階段

(1)

通過曲線擬合得到AP信號強(qiáng)度傳播模型。進(jìn)一步地,將Yij代入單AP信號強(qiáng)度傳播模型可求得信號強(qiáng)度Pij,實測得到WiFi信號強(qiáng)度P,與Pij差值可得到R,確立誤差模型F(x,y,R)。最后,在場區(qū)內(nèi)按照一定規(guī)律測量固定參考點的指紋信息{Pm,xm,ym},其中,Pm為被測點信號強(qiáng)度,{xm,ym}為被測點位置坐標(biāo),遍歷采樣點并將采集的指紋點信息存入數(shù)據(jù)庫。

1.2 在線階段

1.2.1 實時信號處理

實時采集WiFi信號強(qiáng)度,依據(jù)單AP信號強(qiáng)度傳播模型和誤差模型,經(jīng)卡爾曼濾波進(jìn)行數(shù)據(jù)處理,預(yù)測誤差和測量誤差都認(rèn)為是高斯白噪聲,誤差模型F(x,y,R)的位置信息來源于慣性組件在定位時獲取的二維軸向加速度。

1.2.2D-S判定可信指紋區(qū)塊

在選擇可信指紋點時,采用D-S證據(jù)理論。設(shè)所有固定參考方格信息(信號強(qiáng)度信息和位置信息)為一個全完備的論域集合Ω,其中各個元素相互獨立。對于任何一個固定參考方格信息P有函數(shù)m:2Ω→[0,1],且滿足:

(2)

表1 Mass證據(jù)組合

表1中：mθ()是偏航角度的Mass函數(shù),mx()是X軸加速度的Mass函數(shù),my()是Y軸加速度的Mass函數(shù),mp()是WiFi信號強(qiáng)度的Mass函數(shù),Prssii是第i個指紋點。

(3)

其中：θi為參考方格中間點固定偏北角度,θm為采集的偏航角度,xi和yi為固定參考方格中間點的坐標(biāo),xm和ym為由采集到的相對于各固定參考方格中間點的X軸和Y軸加速度得到的定位點坐標(biāo)。Pp1是根據(jù)直接測得WiFi信號強(qiáng)度估測的所在方格區(qū)域并按照方格位置比例換算的概率。據(jù)Dempster合成規(guī)則:

(4)

選取Bel(P)信任度最高的固定參考指紋區(qū)塊,其中K值為歸一化常數(shù),如式(5)所示：

(5)

最后采用加權(quán)K近鄰法(WKNN),即在N個指紋中選出與測得實時WiFi信號強(qiáng)度K個最近鄰者(此處認(rèn)為最近鄰者是所在方格的四個固定參考點),再通過一定的加權(quán)系數(shù)算出定位坐標(biāo)。

2 實驗與分析

實驗環(huán)境以天津濱海國際機(jī)場T2航站樓二層離港場區(qū)為應(yīng)用場景,場區(qū)內(nèi)主要旅客活動區(qū)域的已有非定位部署AP是按最大公約單元為15m×15m設(shè)置的,故本文通過最大公約單元區(qū)域?qū)嶒烌炞C和全場區(qū)實驗驗證兩個階段對以下三個關(guān)鍵問題依次進(jìn)行論證:

1)通過樣機(jī)系統(tǒng)實驗驗證基于D-S證據(jù)理論的區(qū)塊推斷與定位算法的可行性與有效性;

2)通過PDR、C支持向量回歸機(jī)(C-SupportVectorRegression,C-SVR),以及本文算法對目標(biāo)連續(xù)位置分別進(jìn)行推定實驗,驗證本文算法的相對優(yōu)越性與環(huán)境適用性;

3)通過實際場區(qū)實驗驗證非定位部署信標(biāo)的大體量場區(qū)環(huán)境下,基于D-S證據(jù)理論的室內(nèi)定位算法的可行性與實用性。

單元區(qū)域的實驗在校工程訓(xùn)練中心一層大廳按實地環(huán)境要素進(jìn)行仿真設(shè)置,標(biāo)示出了邊長15m的正方形區(qū)域,區(qū)域4個頂點各部署一個AP,區(qū)域內(nèi)進(jìn)行柵格化處理,劃分成100個1.5m×1.5m的方格,每個方格的頂點為固定參考點。

2.1 單點定位實驗

1)建立了單AP點信號強(qiáng)度傳播模型。

如圖1所示,通過實測數(shù)據(jù)擬合獲取了一般狀態(tài)下單AP點的信號強(qiáng)度傳播模型,進(jìn)一步地,得到了圖3中各單元格參考點的強(qiáng)度向量。

圖1 單AP信號強(qiáng)度傳播模型

2)在線實時信號處理。

依據(jù)單AP信號強(qiáng)度傳播模型和誤差模型,實時采集WiFi信號強(qiáng)度并經(jīng)過卡爾曼濾波進(jìn)行數(shù)據(jù)處理,數(shù)據(jù)處理前后對比如圖2所示。

圖2 數(shù)據(jù)處理前后對比圖

結(jié)果表明經(jīng)過卡爾曼濾波后有效地消除了奇異信號,使得到的WiFi信號強(qiáng)度值平穩(wěn)有效,能夠滿足定位需求。

3)D-S推斷區(qū)塊與定位。

定義上一定位點為A,坐標(biāo)為(7 500,7 500),當(dāng)前定位點為B,如圖3所示。因定位點只與相鄰的9個固定參考方格有關(guān),故只選定9個作標(biāo)示。將慣性傳感器采集到的位姿信息通過D-S證據(jù)理論選取可信度最大的固定參考方格,如表2所示。

圖3 目標(biāo)位置移動趨勢

指紋點mθ()mx()my()mp()m(Prssi)Prssi10.1470.1100.1280.1550.186Prssi20.1630.1260.1280.2130.325Prssi30.1420.1260.1100.1500.171Prssi40.1220.1260.0950.0610.052Prssi50.1010.1100.0950.0540.033Prssi60.0800.0970.0950.0580.025Prssi70.0600.0970.1100.0620.023Prssi80.0380.0970.1280.0910.025Prssi90.1470.1100.1100.1560.161

得到可信度最高的指紋點Prssi2所在參考區(qū)塊后,通過WKNN所得定位坐標(biāo)為(8 940,8 956),實際位置坐標(biāo)為(9 200,9 200),定位誤差為356.6mm。

2.2 連續(xù)定位實驗及算法比較

在模擬的單元場區(qū)內(nèi),推行樣機(jī)系統(tǒng),采用本文算法對目標(biāo)動態(tài)移動進(jìn)行位置的連續(xù)性推定,如圖4所示。

圖4 目標(biāo)位置連續(xù)性推定實驗

航站樓場區(qū)行李車平面尺寸長邊通常為1 ～1.2m,旅客推行行李車,以旅客為圓心、行李車長邊為半徑的圓形區(qū)域作為最小定位單元,則區(qū)分兩名旅客的典型距離為2.5m。相同實驗條件下,與PDR、C-SVR算法等方法進(jìn)行了比較,RSSI信號采樣次數(shù)為90時,目標(biāo)平均定位誤差累積概率分布如圖5所示?？梢钥闯?當(dāng)平均誤差小于或等于2.5m時,本文采用算法的誤差累積概率為88.20%,優(yōu)于C-SVR的70.82%和PDR的67.85%。

圖5 定位算法的平均定位誤差累計概率分布比較

2.3 全場區(qū)實驗驗證

進(jìn)一步地,對樣機(jī)系統(tǒng)在天津濱海國際機(jī)場T2航站樓二層離港場區(qū)進(jìn)行了實地實驗驗證。如圖6(a)為依據(jù)本文算法在實際場區(qū)進(jìn)行路線推定的結(jié)果,能夠看出,在由問詢臺出發(fā)至安檢口的過程中,在底部的AP結(jié)構(gòu)化部署區(qū)域表現(xiàn)良好,在左側(cè)面異形結(jié)構(gòu)區(qū)域,因人員分布問題,推定結(jié)果受到一定影響,但區(qū)段趨勢正確。圖6(b)為經(jīng)過本文算法推定、再進(jìn)行端線擬合后的推定路線,即將推定的目標(biāo)定位點歸算在距離最近的固定端線上,面向大體量空間現(xiàn)場應(yīng)用時,該方式表現(xiàn)出良好的實用特性。

圖6 實際實驗的推定路線

3 結(jié)語

復(fù)雜環(huán)境下的室內(nèi)定位問題表現(xiàn)出一定的不確定特性,而在滿足比貝葉斯概率論更弱的條件下,D-S證據(jù)理論具備處理不確定性信息的能力。本文采用D-S證據(jù)理論對經(jīng)卡爾曼濾波處理的RSSI測量值與慣性測量單元(InertialMeasurementUnit,IMU)反饋的偏航角度和加速度信息進(jìn)行融合處理,推斷測試點最大可能出現(xiàn)的指紋區(qū)塊,再在區(qū)塊內(nèi)依據(jù)離線階段訓(xùn)練建立指紋信息數(shù)據(jù)庫,應(yīng)用WKNN算法進(jìn)行定位處理。實驗結(jié)果表明,本文算法在單元場區(qū)條件下,表現(xiàn)出良好的定位精度,在小于或等于系統(tǒng)所要求典型距離時,平均定位誤差較PDR、C-SVR算法表現(xiàn)得更為優(yōu)越,實際航站樓環(huán)境下在結(jié)構(gòu)化場區(qū)表現(xiàn)出了良好的環(huán)境適用性,但對異型結(jié)構(gòu)區(qū)域及人物體動態(tài)變化條件下仍有待進(jìn)一步研究及改進(jìn)。

)

[1] 羅利. 基于Android的WiFi室內(nèi)定位技術(shù)研究[D]. 成都:西南交通大學(xué), 2014:19-20.(LUOL.StudyonWiFiindoorlocationtechniquesbaseonAndroid[D].Chengdu:SouthwestJiaotongUniversity, 2014: 19-20.)

[2] 陳國平, 馬耀輝, 張百珂.基于指紋技術(shù)的藍(lán)牙室內(nèi)定位系統(tǒng)[J]. 電子技術(shù)應(yīng)用, 2013, 39(3):104-107.(CHENGP,MAYH,ZHANGBK.Bluetoothindoorpositioningbaseonfingerprintingtechnology[J].ApplicationofElectronicTechnique, 2013, 39(3):104-107.)

[3]CHOIB-S,LEEJ-W,LEEJ-J,etal.AhierarchicalalgorithmforindoormobilerobotslocalizationusingRFIDsensorfusion[J].IEEETransactionsonIndustrialElectronics, 2011, 58(6): 1-10.

[4] 汪東, 葛萬成, 莫國民, 等. 基于參考標(biāo)簽可信度和偏差自校正RFID室內(nèi)定位算法[J]. 計算機(jī)應(yīng)用, 2014, 34(11):3170-3712.(WANGD,GEWC,MOGM,etal.ImprovedRFIDindoorpositioningalgorithmbasedonreferencetags’credibilityanddeviationcorrection[J].JournalofComputerApplications, 2014, 34(11):3170-3172.)

[5] 寧靜. 采用紅外織網(wǎng)的室內(nèi)定位技術(shù)[J]. 激光與紅外, 2011, 41(7):774-778.(NINGJ.Indoorobjectlocationtechnologyusinginfraredweaving[J].LaserandInfrared, 2011, 41(7):774-778.)

[6] 韓霜, 羅海勇, 陳穎, 等. 基于TDOA的超聲波室內(nèi)定位系統(tǒng)的設(shè)計與實現(xiàn)[J]. 傳感技術(shù)學(xué)報, 2010, 23(3):347-353.(HANS,LUOHY,CHENY,etal.ThedesignandimplementationofaTDOA-basedultrasonicindoorlocalizingsystem[J].ChineseJournalofSensorsandActuators, 2010, 23(3):347-353.)

[7] 崔斌, 趙西安. 一種基于傳播模型和位置指紋的混合室內(nèi)定位方法[J]. 測繪通報, 2015(6):35-38.(CUIB,ZHAOXA.Ahybridindoorpositioningmethodbasedonpropagationmodelandlocationfingerprint[J].BulletinofSurveyingandMapping, 2015(6):35-38.)

[8]SHINBJ,LEEKW,CHOISH,etal.IndoorWiFipositioningsystemforAndroid-basedsmartphone[EB/OL]. [2016- 03- 10].https://www.researchgate.net/profile/Mohammed_Lubbad2/publication/276812019_Robust_Indoor_Wi-Fi_Positioning_System_for_Android-based_Smartphone/links/5642005c08aeacfd8937ee80.pdf.

[9]ZHANGG,XUZ,LIUD.ResearchandimprovementonindoorlocalizationbasedonRSSIfingerprintdatabaseandK-nearest neighbor point [C]// Proceedings of the 2013 International Conference on Communications, Circuits and Systems. Piscataway, NJ: IEEE, 2013:68-71.

[10] BORENOVIC M, NESKOVIC A. ANN based models for positioning in indoor WLAN environments[C]// Proceedings of the 2011 19th Telecommunications Forum. Piscataway, NJ: IEEE, 2011:305-312.

[11] 鄧志安, 徐玉濱.基于支持向量機(jī)回歸算法的 WLAN室內(nèi)定位系統(tǒng)[J]. 儀器儀表學(xué)報, 2009, 30(6):578-582.(DENG Z A, XU Y B. A support vector regression algorithm for indoor positioning in wireless local area network [J]. Chinese Journal of Scientific Instrument, 2009, 30(6): 578-582.)

[12] 張勇, 黃杰, 徐科宇. 基于PCA-LSSVR的WLAN室內(nèi)定位算法[J]. 儀器儀表學(xué)報, 2015, 36(2):408-414.(ZHANG Y, HUANG J, XU K Y. Indoor positioning algorithm for WLAN based on principal component analysis and least square support vector regression[J]. Chinese Journal of Scientific Instrument, 2015, 36(2): 408-414.)

[13] 謝代軍, 胡捍英, 孔范增.基于分布重疊和特征加權(quán)的無線局域網(wǎng)室內(nèi)定位算法[J]. 計算機(jī)科學(xué), 2013, 40(11): 38-42.(XIE D J, HU H Y, KONG F Z. Indoor positioning algorithm for WLAN based on distribution and feature Weighting [J]. Computer Science, 2013, 40(11):38-42.)

[14] BONILLA M N I, ESCAMILLA-AMBROSIO P J, CORTéS J M R. Pedestrian dead reckoning towards indoor location based applications[C]// Proceedings of the 2011 8th International Conference on Electrical Engineering Computing Science and Automatic Control. Piscataway, NJ: IEEE, 2011:1-6.

[15] LI W L, ILTIS R A, WIN M Z. A smart phone localization algorithm using RSSI and inertial sensor measurement fusion [C]// Proceedings of the 2013 IEEE Global Communications Conference. Piscataway, NJ: IEEE, 2013:3335-3340.

[16] CHEN R C, LIN Y C, LIN Y S. Indoor position location based on cascade correlation networks [C]// 2011 IEEE International Conference on Systems, Man, and Cybernetics. Piscataway, NJ: IEEE, 2011:2295-2300.

This work is partially supported by Major Program of Natural Science Foundation of Tianjin (12JCZDJC34200).

WANG Xuqiao, born in 1983, M. S., experimentalist. His research interests include wireless sensor network, intelligent system.

WANG Jinkun, born in 1990, M. S. candidate. His research interests include intelligent optimization algorithm.

Integrated indoor positioning algorithm based on D-S evidence theory

WANG Xuqiao*, WANG Jinkun

(Robotics Institute, Civil Aviation University of China, Tianjin 300300, China)

An integrated positioning algorithm for Wireless Fidelity / Inertial Measurement Unit (WiFi/IMU) based on D-S evidence inference theory was proposed for large indoor area Location Based Service (LBS) without beacons deployment. Firstly, the transmission model of signal strength of a single Access Point (AP) was established, then Kalman Filter was used to denoise the

Signal Strength Indication (RSSI). Secondly, Dempster/Shafer (D-S) evidence theory was applied in the data fusion process for real-time acquisition of multi-sources, including the signal strength of WiFi, yaw and accelerations on all shafts; then the fingerprint blocks with high confidence were selected. Finally, the WeightedK-Nearest Neighbor (WKNN) method was exploited for the terminal position estimation. Numerical simulations on unit area show that the maximum error is 2.36 m and the mean error is 1.27 m, which proves the viability and effectiveness of the proposed algorithm; the cumulated error probability is 88.20% when the distance is no greater than the typical numerical value, which is superior to 70.82% of C-Support Vector Regression (C-SVR) or 67.85% of Pedestrian Dead Reckoning (PDR). Furthermore, experiments on the whole area of the real environment also show that the proposed algorithm has an excellent environmental applicability.

Wireless Local Area Network (WLAN); indoor positioning; Received Signal Strength Indication (RSSI); location fingerprint; Dempster/Shafer (D-S) evidence theory; WeightedK-Nearest Neighbor (WKNN)

2016- 08- 04;

2016- 12- 27。 基金項目:天津市自然科學(xué)基金資助項目(12JCZDJC34200)。

王續(xù)喬(1983—),男,吉林吉林人,實驗師,碩士,主要研究方向:無線傳感器網(wǎng)絡(luò)、智能系統(tǒng); 王瑾琨(1990—),男,河北廊坊人,碩士研究生,主要研究方向:智能優(yōu)化算法。

1001- 9081(2017)04- 1198- 04

10.11772/j.issn.1001- 9081.2017.04.1198

TP393.17

A