基于D-S證據理論的室內組合定位算法

王續喬,王瑾琨

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

基于D-S證據理論的室內組合定位算法

王續喬*,王瑾琨

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

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

無線局域網;室內定位;接收信號強度指示;位置指紋;D-S證據理論;加權K近鄰

0 引言

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

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

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

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

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

1 算法原理及方案

1.1 離線階段

(1)

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

1.2 在線階段

1.2.1 實時信號處理

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

1.2.2D-S判定可信指紋區塊

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

(2)

表1 Mass證據組合

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

(3)

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

(4)

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

(5)

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

2 實驗與分析

實驗環境以天津濱海國際機場T2航站樓二層離港場區為應用場景,場區內主要旅客活動區域的已有非定位部署AP是按最大公約單元為15m×15m設置的,故本文通過最大公約單元區域實驗驗證和全場區實驗驗證兩個階段對以下三個關鍵問題依次進行論證:

1)通過樣機系統實驗驗證基于D-S證據理論的區塊推斷與定位算法的可行性與有效性;

2)通過PDR、C支持向量回歸機(C-SupportVectorRegression,C-SVR),以及本文算法對目標連續位置分別進行推定實驗,驗證本文算法的相對優越性與環境適用性;

3)通過實際場區實驗驗證非定位部署信標的大體量場區環境下,基于D-S證據理論的室內定位算法的可行性與實用性。

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

2.1 單點定位實驗

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

如圖1所示,通過實測數據擬合獲取了一般狀態下單AP點的信號強度傳播模型,進一步地,得到了圖3中各單元格參考點的強度向量。

圖1 單AP信號強度傳播模型

2)在線實時信號處理。

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

圖2 數據處理前后對比圖

結果表明經過卡爾曼濾波后有效地消除了奇異信號,使得到的WiFi信號強度值平穩有效,能夠滿足定位需求。

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

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

圖3 目標位置移動趨勢

指紋點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所在參考區塊后,通過WKNN所得定位坐標為(8 940,8 956),實際位置坐標為(9 200,9 200),定位誤差為356.6mm。

2.2 連續定位實驗及算法比較

在模擬的單元場區內,推行樣機系統,采用本文算法對目標動態移動進行位置的連續性推定,如圖4所示。

圖4 目標位置連續性推定實驗

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

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

2.3 全場區實驗驗證

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

圖6 實際實驗的推定路線

3 結語

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

)

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

[2] 陳國平, 馬耀輝, 張百珂.基于指紋技術的藍牙室內定位系統[J]. 電子技術應用, 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] 汪東, 葛萬成, 莫國民, 等. 基于參考標簽可信度和偏差自校正RFID室內定位算法[J]. 計算機應用, 2014, 34(11):3170-3712.(WANGD,GEWC,MOGM,etal.ImprovedRFIDindoorpositioningalgorithmbasedonreferencetags’credibilityanddeviationcorrection[J].JournalofComputerApplications, 2014, 34(11):3170-3172.)

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

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

[7] 崔斌, 趙西安. 一種基于傳播模型和位置指紋的混合室內定位方法[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] 鄧志安, 徐玉濱.基于支持向量機回歸算法的 WLAN室內定位系統[J]. 儀器儀表學報, 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室內定位算法[J]. 儀器儀表學報, 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] 謝代軍, 胡捍英, 孔范增.基于分布重疊和特征加權的無線局域網室內定位算法[J]. 計算機科學, 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。 基金項目:天津市自然科學基金資助項目(12JCZDJC34200)。

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

1001- 9081(2017)04- 1198- 04

10.11772/j.issn.1001- 9081.2017.04.1198

TP393.17

A