2. 中山大学广东省城市化与地理环境空间模拟重点实验室, 广东 广州 510275
2. Guangdong Key Laboratory for Urbanization and Geo-simulation, Sun Yat-sen University, Guangzhou, 510275, China
1 引言
卫星导航定位系统,诸如GPS和北斗系统受制于微弱的地面到达信号,在城市峡谷和室内区域定位表现不佳。红外[2]、超声波[3]、压力传感器[4]、数字电视信号[5]、蜂窝通信网络[6]、无线传感网(wireless sensor network,WSN)[7]、无线局域网(wireless local area networks,WLAN)[8, 10, 11, 12, 13, 14]、射频标识(radio frequency identification,RFID)[9]等定位技术被看作是卫星导航定位系统的补充,辅助其提供无缝定位服务[1]。其中WLAN是最具潜力的技术之一。但是作为WLAN定位的常用算法,传统位置指纹匹配(location fingerprinting)[8]在室内外动态环境中难以保持定位精度。原因在于,参与计算的必要数据除了实时观测量还有当前区域的先验数据(即radio map)。如果两者之间欠缺关联性,定位精度便得不到保证。而先验radio map不能够适应人员活动、环境温湿度等时变因素以及无线接入点(access point,AP)移动、环境结构改变等空间变化因素。因此,传统位置指纹匹配在动态环境下的定位表现通常不理想。
针对动态环境下位置指纹匹配定位面临的问题,近些年国内外学者提出了多种自适应方法[9, 10, 11, 12, 13, 14]。其中文献[9, 10]提出利用足够多的参考设备(基站)实时输出的接收信号强度(received signal strength,RSS)样本内插或直接组成radio map。这类方法可以适应动态环境变化,但是radio map的实时生成给定位系统带来了较重的运行负荷,且传统内插方法不适用于复杂的室内环境。而文献[11—14]借助radio map采样点及参考设备(基站)之间的静态映射关系,然后根据参考设备实时采集的RSS样本更新radio map。这类方法实现了radio map自适应时变动态环境的目的。但是,其中的静态映射关系并不适用于环境空间变化的情形。因为环境空间变化改变了RSS的空间分布,也改变了参考设备与采样点之间的映射关系。
本文针对当前已有方法的不足提出了兼顾环境时空变化因素的动态自适应模型(dynamic adaptive model,DAM),实时生成radio map支持稳健室内定位。该模型以多个基站数据为输入,radio map为输出,基于基站与静态radio map(static radio map,SRM)采样点之间的空间关联性,利用具有较强映射能力的反向传播(back propagation,BP)神经网络[17, 18, 19, 20, 21]建立对应每个AP的基站和采样点RSS之间的静态映射模型(static functional model,SFM);借助多元异常数据探测技术检验基站数据,捕捉时空环境变化;根据探测结果以顾及室内布局的数值内插和再训练的方式自动更新映射模型,使其适应时空环境变化并能输出更新的radio map进行定位。
2 室内WLAN定位与动态自适应模型 2.1 问题描述与定义在WLAN位置指纹匹配定位中,先验radio map表示接收自所有可扫描到的接入点{APk:k∈ΓAP}(ΓAP为全部AP集合)的RSS在指定区域的先验空间分布及特性。图 1中AP1、AP2、AP3、AP4共4个AP在指定区域的瞬时值的叠加便形成了radio map。其通常由终端设备在有限采样点{lj:j∈Γr}(Γr为全部采样点集合)采集的离散数据表达。其中的数据点,如图 1中向下投射的网格,称为位置指纹(location fingerprint),即关于此位置能够接收到的所有AP的RSS样本模式{sj:j∈ΓAP}。理论上位置越相近,模式越相似;反之,模式越相似,位置越接近。微软最早提出了基于WLAN位置指纹的模式匹配方法进行室内定位——位置指纹匹配。
由于RSS容易受到环境时空变化因素的影响,先验radio map难以适应动态环境变化。以IEEE 802.11 WLAN信号为例,其运行在2.4 GHz波段,很容易受楼层、墙壁、家具和人体的影响,信号绕射、反射、散射等造成了RSS观测值的波动。从空间的角度,RSS的变化可以分为大尺度和小尺度两种[15]。大尺度空间变化是指长距离(远大于电磁波长)传播或遮挡等引起的信号衰减。小尺度空间变化是指短距离(接近电磁波长)移动、短时间内的信号波动。通常用来描述无线信号衰减规律的是对数正态分布模型[15]
式中,Xσ是均值为0,标准差为σ的高斯随机变量;d0为参考距离(WLAN环境下取1 m);n为信号穿过某种介质时的衰减系数;d为发射端与接收端之间的距离;Pr(d0)为参考距离平均RSS。在室内环境下,必须考虑墙壁、家具等障碍物造成的信号衰减,模型主要有WAF(wall attenuation factor)模型[8]等 式中,C是衰减因子变化时障碍物数目阀值;nW是发射器与接收器之间障碍物数目;WAF是墙壁衰减因子。信号传播由于穿透介质不同,障碍物数目不同而呈各向异性,RSS空间变化复杂。从时空的角度,RSS还随着时间的推移而呈现不同的变化特性。图 2展示了办公室环境下固定点的RSS观测值24 h变化序列。直观看来,在办公时段内,RSS的波动幅度较大,而在非办公时段内,RSS的波动幅度较小。这是由于RSS的影响因素在不同时间段的作用程度不同。综上,为了进行稳健室内定位,不能完全依赖先验radio map,而必须不断更新radio map以适应环境的时空变化。
为了更新radio map,本文提出的DAM将多个基站数据作为输入,radio map作为输出,针对每个无线接入点APk建立采样点{lj:j∈Γrk}(Γrk为APk的相关采样点集合)与基站{Bi:i∈ΓBk}(ΓBk为APk的相关基站集合)之间的映射模型fk
式中,rik为基站观测的对应样本均值;利用多元异常数据探测技术检验基站数据,探测环境的时空变化并以顾及室内布局的数值内插和再训练的方式更新fk,使其适应环境的时空变化。 2.2 动态自适应模型(DAM)位置指纹采样点与邻近基站之间具有很强的空间关联性,而与采样位置密切相关且本质上由空间变化主导的RSS同样存在类似的邻域性质。在未发生大尺度空间变化的情形下,本文假设这种关联性是不变的。令XBk代表所有基站{Bi:i∈ΓBk}处的RSS取值集合,Yrk代表所有采样点{lj:j∈Γrk}处的RSS取值集合,fk是XBk到Yrk的映射,即fk:XBk→Yrk。假设和分别是XBk和Yrk上的Borel σ-代数[16],易证对E∈∑rk,fk-1E∈∑Bk,那么fk:XBk→Yrk是(∑Bk,∑rk)Borel可测函数[16]。具有S型隐含层和线性输出层的神经网络可以逼近任意Borel可测函数[17]而被用来构建模型。而发生大尺度空间变化之后,原始映射关系被破坏,需要根据基站数据捕捉环境空间变化并进行修复。室内环境下信号传播规律复杂,很难建立全局传播模型。邻近且环境相似的基站能够较精确地反映周围环境的动态变化,本文根据室内布局将目标区域划分为环境相似且紧凑的分区,并假设每个分区内RSS分布遵循空间位置越近值越相似的规律。因此,本文根据基站数据,分区域插值修正radio map,并再训练修复映射模型。
DAM如图 3所示,包括以下3个部分。
2.2.1 神经网络映射模型DAM首先利用了基站与radio map采样点之间的映射关系,以基站数据为输入,radio map采样点数据为输出构建模型。模型中采用如图 3所示的3层网络结构,包括输入层、隐含层和输出层。输入层由相关AP在基站处的观测值{rik:i∈ΓBk}组成,而输出层由radio map采样点处的观测值{sjk:j∈Γrk}组成。在输入层与隐含层之间采用S型传输函数
式中,n_hiddent为隐含层神经元;wi,t和NB分别是输入层神经元的权重和数目,NB取值为集合ΓBk中元素数目。在隐含层和输出层之间采用线性传输函数 式中,wt,j和m分别为隐含层神经元的权重和数目;输出层神经元数目Nr为集合Γrk中元素数目。借助Kolmogorov定理确定隐含层神经元数目m的取值为(2NB+1)。利用BP算法对神经网络模型进行训练。 2.2.2 环境空间变化探测在利用映射模型更新radio map之前,基站数据首先经过多元数据异常探测以捕捉环境空间变化(如图 3所示)。与时变特性不同,空间变化导致RSS空间分布特性改变,所以对基站数据的及时检验能够实现对环境空间变化的捕捉。
根据基站对于每个AP持续24 h的观测,发现在不发生环境空间变化的情形下固定点的RSS观测值近似高斯分布N(μ,δ2)或者分时段近似高斯分布(如图 4所示)。所以本文将环境空间变化探测当作多元高斯分布数据的异常检验。基于马氏(Mahalanobis)距离估计的方法是此类数据异常检验的常用方法,即根据数据样本X到数据集重心之间的距离
检验样本异常。式中,T是数据集重心;C为协方差阵。此方法的关键在于C的估计和D的判别准则的确定。因为基站与基站之间以及AP之间通常相互独立,所以易得C的估计。另外,如果X符合多维正态分布,那么马氏距离的平方遵循分布χ2p(参见文献[22—23])。这意味着根据人员活动情况分时段处理相关数据,就可以利用χ2p分布临界值作为判别准则,即当D2大于或等于χ2分布表中的临界值时,判定数据异常。在动态定位环境中,具体探测过程见图 3,按照先局部后全局进行:
(1) 局部异常探测。局域空间变化表现为少数几个基站的RSS长时间大幅度改变。造成的原因可能是基站附近空间格局的改变,如家具的移动。因此,针对每个基站进行局域空间变化探测。将基站处所有相关AP的观测值{ri,i∈ΓAP*,ΓAP*为基站处所有相关AP的集合}作为多元样本数据进行检验。
(2) 全局异常探测。全局空间变化表现为所有基站关于某个或某几个AP的RSS发生长时间大幅度改变。造成这种改变的原因可能是AP的移动。因此,针对每个AP进行全局异常探测。将全部相关基站接收自该AP的观测值{rj,j∈ΓB*,ΓB*为能够扫描到的AP全部相关基站的集合}作为多元样本数据进行检验。
如果全局连续异常超过时限则对整个模型更新;如果全局检验正常,而局部连续异常超过时限则对模型局部更新。
2.2.3 模型自适应更新环境的空间变化导致SRM的部分或者全部背离RSS的实际分布。在连续异常未超限时依赖数据内插技术对SRM进行修正是一种简便而高效的办法。在室内环境下,信号传播呈各向异性,很难建立全局传播模型。由于墙壁、楼层等障碍物造成信号强度大幅衰减,RSS分布出现突变等不规则变化。因此,SRM插值修正较为复杂。在基站合理分布的前提下,本文提出根据室内布局将目标区域划分为环境相似且紧凑的分区,使同一分区内不出现墙壁等障碍物,那么RSS便呈现规则分布,遵循空间位置越近值越相似的规律。分区内的基站作为插值控制点也能够较精确反映周围环境的动态变化。对于radio map的内插[10, 24],已经有利用倒数距离加权法(inverse distance weighted,IDW)、Akima样条函数法、通用克里金法(universal Krigging)等方法的先例。本文分别测试了以上3种方法,对各自内插精度和计算时间负荷作了对比。综合考虑内插精度和计算时间负荷,模型中采用了幂值为2的IDW[25]分区域插值方法。
在连续异常超限后,以类似静态模型的训练过程更新映射模型,针对模型中过时的部分,利用更新后的SRM与基站信息进行训练更新,这就使得映射模型能够适应环境的空间变化。另外,异常探测中的协方差阵C亦需要重新估计。 实时定位时,将基站处实时采集的RSS样本输入到动态自适应模型中,模型就可以自动输出更新的radio map。
3 试验验证 3.1 试验设计在某科研大楼第5层长48 m、宽21 m的场地进行了试验。为了表达良好的空间关联性,本文根据建筑的结构分区域均匀布设基站。现场布局如图 5所示,图中斜杠填充区为插值分区。在WLAN环境中,10台装有IEEE802.11n无线网卡的电脑均匀分布于其中作为基站,具体位置见图中示例。试验中每次扫描平均可以探测到环境中7个WLAN AP,为了进一步进行信号空间环境变化的测试,本文在已有AP的基础上增设了3个AP,具体位置见图中示例。另外,一台笔记本作为移动端在走廊上60个点(见图中叉符号)采集RSS样本以构建SRM,另外在图中圆圈表示的27个点采集定位数据。试验中采取的位置估算方法是K加权最近邻算法(K weighted nearest neighbors,KWNN)。
式中,Xi是位置指纹的位置;wi是RSS样本向量之间欧氏距离倒数;K是RSS样本空间里最靠近估算位置的位置指纹个数,本文中取8。另外,试验中神经网络的训练误差阈值为0.001 dBm。根据神经网络收敛时的正常训练次数,防止系统可能受到模型收敛过慢的影响,另设训练次数阀值为999次。首先针对环境的时空变化情形检验所提模型(DAM)的表现,包括定位精度与运行速度,并与已有方法进行对比。作为对比,本文另外采用了SRM和文献[14]提出的基于SFM的radio map生成方法。最后检验了模型参数对于DAM的定位表现的影响情况。
3.2 试验结果与分析 3.2.1 环境的时空变化对模型定位表现的影响首先在不同时段进行试验,检验模型在时变环境中的定位表现。图 6给出了3次试验的平均定位误差对比结果。对比SRM的定位结果,采用DAM在3个时段都削弱了动态环境造成的影响,平均误差分别下降10%、13%和20%。这说明由于基站与radio map采样点受环境影响相似而利用他们之间的映射关系生成radio map可以使得系统在一定程度上适应时变环境,并且随着运行时间的增加,DAM的优势更明显。
但是在真实情形中,定位环境非常复杂。简单地利用基站与radio map采样点之间的映射关系并不能够保证定位的准确性。因此本文又以AP移动为例进行试验,检验模型对于彻底改变RSS空间分布的环境空间变化的适应性。总共在3种情形下进行了试验:①一个AP移动,将图 5中AP1移到AP3的位置;②两个AP移动,将图 5中AP1和AP3互换位置;③3个AP移动,将图 5中AP1移到AP2的位置,将AP2移到AP3的位置,将AP3移到AP1的位置。
应用DAM,基站数据并不是被简单地用来生成radio map,而首先经过多元数据异常探测。图 7和图 8分别给出了一个AP移动后全局和选定基站处局部异常探测结果。可以看出移动发生前检验度量值较平稳且低于临界值,而移动发生后,检验度量值远高于临界值,易于探测。表明将基站数据当作多维高斯分布数据合理可行,利用多元异常数据探测技术可以检验出异常数据支持捕获环境的空间变化因素。
图 9给出了前文提到的3种AP移动方案对应的基于SRM、SFM和DAM的平均定位误差对比。可以发现DAM的定位误差在AP发生移动后只有小幅变动,上升了10%~20%,而基于SRM和SFM的定位误差在AP发生移动后显著上升了至少165%。
图 10展示了3个AP移动后采用不同模型的定位精度,包括RMS和X、Y坐标分量误差。可以发现基于DAM的方法的定位精度与发生变化前相比几乎一样,大部分精度都在3 m左右,而基于ORM和SFM的方法的定位精度都大幅度下降到10~30 m,已经很难满足室内应用的需求。
通过以上试验可以看出,在环境时空变化情形中,DAM的自适应性得到了有力的验证,特别是在AP移动等彻底改变RSS空间分布的环境空间变化中它的表现远好于现有模型和方法(包括SRM和SFM),并使定位系统能够保持原有定位表现。
此外,在型号为w17e,配置为2.99 GHz双核AMD 1222处理器、2 GB内存、Windows XP Professional SP3系统的惠普计算机上进行了不同模型运行时间的比较。图 11展示了基于SRM、SFM以及DAM的单次定位运行时间。由于实时生成radio map,SFM定位运行时间比SRM略有增加,而DAM由于附带异常检验步骤导致定位运行时间进一步增加。
3.2.2 模型参数对其定位表现的影响最后在未发生环境空间变化的情形下分别测试了基站数目和神经网络训练阈值两个参数对于DAM定位结果的影响。图 12展示了基站数目对应的平均定位误差。因为至少需要6个基站均匀分布才能良好构建与所有采样点之间的映射模型,所以测试的最少基站数目为6。从结果看,在未发生环境空间变化的情形下,在达到最基本的基站分布和数目要求之后,增加基站对于定位结果的影响有限。图 13展示了神经网络映射模型训练阈值对应的平均定位误差。从结果看,训练阈值对于模型定位结果的影响也较小,并且阈值达到0.001 dBm时,定位结果便稳定地处于最佳水平。因此,本文取此阈值作为模型默认值。
4 结论
为了辅助卫星导航定位系统提供无缝定位服务,WLAN等技术被应用到室内和城市峡谷等遮蔽区域的定位之中。但是,在WLAN位置指纹匹配室内定位系统中,匹配数据库——radio map需要更新甚至重建以适应环境的时空变化。利用多个基站的实时数据获取更新的radio map是可行的措施之一。神经网络建模的基站与radio map采样点RSS之间的映射关系有效利用了基站与采样点之间的空间关联性而使得模型自适应环境的时变因素;多维异常数据探测对基站实时采集的RSS样本的检验能够捕获环境空间变化;顾及室内布局数值内插和再训练的方式可以自动更新模型而使得模型适应环境的空间变化因素。利用动态自适应模型获取的radio map使得定位系统能够自适应环境的时空变化而保持原有的定位表现。考虑到模型的实际应用,笔者将在后续研究中开展以下工作:①精化模型,提升系统的定位速度;②讨论基站的分布和数目对于数据内插和系统复杂度的影响。
[1] | TIAN Hui, XIA Linyuan, MO Zhiming, et al. Signals of Opportunity Assisted Ubiquitous Positioning and Its Key Elements for Outdoor/Indoor Environment[J]. Geomatics and Information Science of Wuhan University, 2009, 34(11): 1372-1376. (田辉, 夏林元, 莫志明, 等. 泛在无线信号辅助的室内外无缝定位方法与关键技术, 武汉大学学报: 信息科学版, 2009, 34(11): 1372-1376.) |
[2] | WANT R, HOPPER A, FALCĀO V, et al. The Active Badge Location System[J]. ACM Transactions on Information Systems, 1992, 10(1): 91-102. |
[3] | PRIYANTHA N B, MIU A K L, BALAKRISHNAN H, et al. The Cricket Compass for Context-aware Mobile Applications[C]//Proceedings of the 7th Annual International Conference on Mobile Computing and Networking. New York: ACM, 2001: 1-14. |
[4] | ORR R J, ABOWD G D. The Smart Floor: A Mechanism for Natural User Identification and Tracking[C]//Proceedings of the CHI 2000 Extended Abstracts on Human Factors in Computing Systems. New York: ACM, 2000: 275-276. |
[5] | RABINOWITZ M, SPILKER J J Jr. A New Positioning System Using Television Synchronization Signals[J]. IEEE Transactions on Broadcasting, 2005, 51(1): 51-61. |
[6] | SOLIMAN S, AGASHE P, FERNANDEZ I, et al. GPSOneTM: A Hybrid Position Location System[C]//Proceedings of the 2000 IEEE 6th International Symposium on Spread Spectrum Techniques and Applications. Parsippany, NJ: IEEE, 2000, 1: 330-335. |
[7] | PATWARI N, ASH J N, KYPEROUNTAS S, et al. Locating the Nodes: Cooperative Localization in Wireless Sensor Networks[J]. IEEE Signal Processing Magazine, 2005, 22(4): 54-69. |
[8] | BAHL P, PADMANABHAN V N. RADAR: An In-building RF-based User Location and Tracking System[C]//Proceedings of the 19th Annual Joint Conference of the IEEE Computer and Communications Societies. Tel Aviv: IEEE, 2000, 2: 775-784. |
[9] | NI L M, LIU Yunhao, LAU Y C, et al. LANDMARC: Indoor Location Sensing Using Active RFID[C]//Proceedings of the 1st IEEE International Conference on Pervasive Computing and Communications. Fort Worth: IEEE, 2004, 10(6): 701-710. |
[10] | KRISHNAN P, KRISHNAKUMAR A S, JU W H, et al. A System for LEASE: Location Estimation Assisted by Stationary Emitters for Indoor RF Wireless Networks[C]//Proceedings of the 23rd Annual Joint Conference of the IEEE Computer and Communications Societies. Hong Kong: IEEE, 2004, 2: 1001-1011. |
[11] | XIA Linyuan, WU Dongjin. On Realtime and Adaptive Indoor Positioning Method under Multi-base-station Mode[J]. Bulletin of Surveying and Mapping, 2012(11): 1-6. (夏林元, 吴东金. 多基站模式下的实时与自适应室内定位方法研究[J]. 测绘通报, 2012(11): 1-6.) |
[12] | YIN Jie, YANG Qiang, NI M L. Learning Adaptive Temporal Radio Maps for Signal-strength-based Location Estimation[J]. IEEE Transactions on Mobile Computing, 2008, 7(7): 869-883. |
[13] | WANG Huimin, MA Lin, XU Yubin, et al. Dynamic Radio Map Construction for WLAN Indoor Location[C]//Proceedings of 2011 International Conference on International Conference on Intelligent Human-machine Systems and Cybernetics. Hangzhou: IEEE, 2011, 2: 162-165. |
[14] | LIN Yiming, LUO Haiyong, LI Jintao, et al. Dynamic Radio Map Based Particle Filter for Indoor Wireless Localization[J]. Journal of Computer Research and Development, 2011, 48(1): 139-146. (林以明, 罗海勇, 李锦涛, 等. 基于动态Radio Map的粒子滤波室内无线定位算法[J]. 计算机研究与发展, 2011, 48(1): 139-146.) |
[15] | RAPPAPORT T S. Wireless Communications: Principles and Practice[M]. 2nd ed. Upper Saddle River, NJ: Prentice Hall, 2002. |
[16] | KUANG Jichang. Real and Functional Analysis[M]. Beijing: Higher Education Press, 2002. (匡继昌. 实分析与泛函分析[M]. 北京: 高等教育出版社, 2002.) |
[17] | HAGAN M T, DEMUTH H B, BEALE M. Neural Network Design[M]. Boston: PWS Publishing Company, 1996. |
[18] | ZHU Taoye, ZHU Jianjun, ZHANG Xuezhuang, et al. Atmospheric Refraction Numerical Fitting Research Based on Mapping Function and Neural Network[J]. Acta Geodaetica et Cartographica Sinica, 2007, 36(3): 290-295. (朱陶业, 朱建军, 张学庄, 等. 大气折射的映射函数与神经网络拟合比较分析[J]. 测绘学报, 2007, 36(3): 290-295.) |
[19] | GAO Weiguang, YANG Yuanxi. Neural Network Aided GPS/INS Integrated Navigation Fault Detection Algorithms[J]. Acta Geodaetica et Cartographica Sinica, 2008, 37(4): 403-409. (高为广, 杨元喜. 神经网络辅助的GPS/INS组合导航故障检测算法[J]. 测绘学报, 2008, 37(4): 403-409.) |
[20] | LIU Hanli, ZHOU Chenghu, ZHU Axing, et al. Multi-population Genetic Neural Network Model for Short-term Traffic Flow Prediction at Intersections[J]. Acta Geodaetica et Cartographica Sinica, 2009, 38(4): 363-368. (刘汉丽, 周成虎, 朱阿兴, 等. 多子群遗传神经网络模型用于路口短时交通流量预测[J]. 测绘学报, 2009, 38(4): 363-368.) |
[21] | TAN Xinglong, WANG Jian, ZHAO Changsheng. Neural Network Aided Adaptive UKF Algorithm for GPS/INS Integration Navigation[J]. Acta Geodaetica et Cartographica Sinica, 2015, 44(4): 384-391. (谭兴龙, 王坚, 赵长胜. 神经网络辅助的GPS/INS组合导航自适应UKF算法[J]. 测绘学报, 2015, 44(4): 384-391.) |
[22] | FILZMOSER P, MARONNA R, WERNER M. Outlier Identification in High Dimensions[J]. Computational Statistics & Data Analysis, 2008, 52(3): 1694-1711. |
[23] | JOHNSON R A, WICHEM D W. Applied Multivariate Statistical Analysis[M]. 4th ed. Upper Saddle River, NJ: Prentice Hall, 1998. |
[24] | LI Binghao, WANG Yufei, LEE H K, et al. Method for Yielding a Database of Location Fingerprints in WLAN[J]. IEE Proceedings-Communications, 2005, 152(5): 580-586. |
[25] | ZHANG Hong, WEN Yongning, LIU Aili. Foundation of Geographic Information System Algorithms[M]. Beijing: Science Press, 2006, 6. (张宏, 温永宁, 刘爱利. 地理信息系统算法基础[M]. 北京: 科学出版社, 2006, 6.) |