基于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