基于快速部署的室内多楼层定位算法研究

俞敏杰,易 平,关汉男

(上海交通大学信息安全工程学院,上海200240)

基于快速部署的室内多楼层定位算法研究

俞敏杰,易 平,关汉男

(上海交通大学信息安全工程学院,上海200240)

传统的GPS系统在室内由于墙和障碍物的阻隔无法很好地生效,因此需要完善的室内定位系统,弥补定位领域最后100 m的不足。然而当前国内外的主流算法大多是基于水平方向的室内定位,有关垂直方向定位方法的研究较少。为此,提出一种基于快速部署的室内多楼层定位算法,实现在大楼内精确的纵向多楼层定位和设备的实时、按需部署。该算法的核心是多楼层差分算法,通过接收来自不同楼层信号,加以差分计算差值的分布来区分楼层。仿真实验结果表明,该算法能够精确地定位楼层。

基于定位服务;室内定位系统;多楼层定位;多楼层路径衰减模型;多楼层差分算法;快速部署

1 概述

智慧生活的变革无处不在,在楼宇、公共设施、企业、家居、交通等领域已经得到了广泛的应用。这其中最重要的技术之一,也是研究的焦点之一,就是定位服务。定位服务有着广泛的前景,能够极大地提升人们的生活质量,使人们的工作、娱乐、休闲、餐饮、购物等生活方式更便捷。

近些年,以安卓为代表的开源智能手机系统蓬勃发展,同时,硬件的成本也不断降低,智能手机已成为大众手机的主流。在生活中,可以看到安卓手机无处不在,通过使用智能手机也能方便地获得亲朋好友的地理位置,而这些都依赖于像GPS这样的定位服务。GPS是户外定位的最主流的解决方案,在户外,GPS的定位精度能够维持在10 m左右,对于日常使用而言已经足够了。

然而,如果尝试着在室内环境下使用GPS来进行定位,比如在办公室或者在家里使用手机定位,基本收不到GPS的卫星信号,那么得到的定位误差会很大。导致这一问题的主要原因在于室内复杂的环境干扰了卫星信号的传播,卫星信号没法穿越这么多的墙和障碍物。因此,需要专门的室内定位系统来为最后100 m的定位扫清障碍,弥补GPS系统的不足之处。

过去十年间,室内定位技术和算法发展迅速,大部分的室内定位系统都基于无线传感网络的信号处理分析。总体而言,室内定位系统可以分为两大类:距离相关(range-based[1])或是距离无关(range-free[2])的。第1类距离相关的定位方法是早期室内定位的主流,例如像 TOA[3]、TDOA[4]、AOA[5]、RSSI[6]等方法。距离相关的方法通常需要昂贵的硬件和精确的数据支持,也给了距离无关方法巨大的成长空间。近些年,RSD[7]、EZ[8]、BT[9]、UnLoc[10]等距离无关算法相继提出。然而,现有的距离无关算法也有各种各样的缺陷,比如需要花费大量时间和精力来做指纹采集等,因而很难被应用于大规模的通用室内定位系统中。

然而,主流的定位算法研究都是基于水平方向的,在纵向定位上,室内定位的研究较少。现有的支持多楼层定位的算法大多基于在每层楼部署设备,从而可以通过最近的信号源的楼层来判别为当前定位楼层。

基于以上几点,本文提出了基于快速部署的室内多楼层定位算法,与距离无关,且无需指纹采集,可快速地部署相应设备,应用于立体的大楼环境中,多楼层差分算法通过计算来自不同楼层信号差值的分布来区分楼层。

2 多楼层差分算法

与水平定位不同,竖直定位(楼层定位)的研究模型完全不同。楼层间的钢筋混凝土墙的信号衰减量约为20 dB～40 dB[11],这比普通的砖墙(10 dB～15 dB)[9]要大得多。由于每隔一层楼都会有这样的混凝土墙间隔,因此使用传统的三角定位方式很难进行精确定位。本文提出了多楼层差分(Multistorey Differential,MSD)算法来解决楼层定位的问题。

2.1 多楼层定位原理

图1是本文楼层定位的基本模型:假设大楼的高度为H,单位为m,层高为h,单位为m。在底楼(S1)和顶楼(S2)的同一竖直位置各放置一个信号源。因为只考虑竖直方向的定位,所以将三维坐标抽象为二维,分别是X方向(坐标点位置到原点位置的水平距离)以及Z方向(坐标点位置到XOY平面的竖直距离)。假设测试点的坐标P1为(x,z)。

图1 MSD基本模型

定义 多楼层路径衰减(Multi-storey Path Loss, MSPL)是自由空间路径衰减(Free Space Path Loss, FSPL)的扩展,加入了楼层间钢筋混凝土的衰减模型:

其中,PR是信号接收功率,单位为dBm;PT是信号发射功率,单位为dBm;GR是接收端天线增益,单位为dB;GT是发射端天线增益,单位为dB;N是信号穿过的楼层数量;LI是每一层穿墙的信号衰减(约20 dB～40 dB)[11]。

对于自由空间的衰减模型,接收功率可以表示为[12]:

结合式(2),代入λ=c/f,可以得到:

对于一般的信号传播,信号频率f的单位为MHz,距离d的单位为m。假设使用无线路由器作为发射源(f=2 400 MHz):

kMSPL是一个常数,在当前假设下,kMSPL=40.05。

对于测试点(x,z),可以看到N等于z/h的下确界。对于信号源S1和S2,可以计算MSPL:

可以得到MSPLS1和MSPLS2的差值:

本文的目标是进行楼层定位,因而可以将数学推导和实际的模型相结合,即本文的研究重点是楼层而不是精确的高度值。

要区分楼层,假设每层楼的测试点,相对于本楼层水平面的高度是一致的,而绝对高度则是(Ni-1)·h,其中,Ni是当前楼层数。要区分楼层,需要证明在相邻2个楼层的任意位置上,都能通过ΔMSPL来区分。

为了证明算法的可行性,在2个不同的楼层上选择测试点,分别为P1(x1,z1),P2(x2,z2)。不妨设z1＜z2,即z2=z1+h。定义ΔDMSPL为2个测试点上ΔMSPL的差值:

需要减少x对于式(9)的影响。考虑不同x的2种情况:

(1)x1=x2,那么:

将ΔDMSPL对x求导,可以得到:

当x→∞时,式(10)变为:

(2)x1≠x2,那么不妨假设x1＜x2。要区分不同楼层的测试点,需要分析极端情况:x1→0,x2→∞。式(10)变为:

式(12)～式(14)考虑了不同情况下ΔDMSPL的可能取值,而这些公式的第1项对于公式的贡献较小(0～10 dB),而第 2项 2·LI的贡献较大(40 dB～60 dB)。

通过以上推导,证明了在不同楼层下,可以通过ΔMSPL来区分不同楼层的测试点。

2.2 多对信号源下的复杂MSD模型

理论上可以用ΔMSPL的值来进行楼层定位,但是在实际情况下,由于复杂的室内环境和无线信号的波动性,需要设计一个稳定的、可利用多对信号源的模型来提高楼层定位的准确性。

考虑实际的部署情况。需要在整栋楼中部署无线信号源。假设在第i层上,部署了mi个信号源。

本文算法的特性之一是快速部署,要尽量减少信号源的部署,同时尽量减少对精度的影响。因而,可以按照如下方式来部署信号源,即每隔n层布置m个节点。

当x＞0时,dΔDMSPL/dx＜0,因而ΔDMSPL随着x的增大单调递减。当x→0时,式(10)变为:

其中,m的取值决定于水平定位算法需要部署的信号源数量;n的取值决定于信号源可以穿透的楼层数。

当大楼超过n+1层时,将高楼分解为多个n+1层的子模型,从而应用本文的MSD算法。

因此,权重模型为:

3 实验结果与分析

3.1 仿真实验

为了验证MSD算法的可靠性,做了一些仿真实验。

3.1.1 一对信号源的MSD仿真

首先,设计仿真的大楼环境:在大楼的第一层和第(n+1)层的同一位置防止了2个信号源,并计算大楼内不同位置下的ΔMSPL。测试点的水平距离范围为0～20 m,层高为3.5 m,钢筋混凝土的信号衰减值为25 dB。图2为不同n值情况下ΔMSPL的分布图。

图2 n=3,4,5,10时ΔMSPL的分布

3.1.2 多对信号源的MSD仿真

本节仿真了多对信号源情况下的MSD算法。仿真环境和3.1.1节实验相同,并做出了相应的扩展:定义di为第i对信号源到原点的水平距离;n的取值为4。图3展示了本文的仿真结果。

图3 5对信号源时ΔMSPL的分布

3.1.3 仿真结果分析

通过以上的仿真实验可以看出在同一楼层上,不同水平位置的点获得的ΔMSPL值在一个很小的区间内波动,每一条ΔMSPL的楼层曲线基本与X轴垂直。当信号源增加时,曲线的波动更平滑,能够更好地区分楼层。因此,理想环境下可以通过MSD算法来进行楼层定位。

3.2 平台搭建与实验结果

为了验证实际环境中MSD算法的准确性,搭建了室内定位系统的平台来进行实际的测试。

3.2.1 室内定位系统平台

图4展示了本文的室内定位系统,该系统是一个普适的系统,可以使用任何频段或种类的信号源。为了方便部署与实验,使用了无线路由器作为信号源,并使用了安卓智能手机作为信号的接收端。并在后台搭建了服务器用于接收手机数据并进行数据处理与计算。

图4 室内定位系统平台

3.2.2 寝室楼内的实际实验

图5是本文进行实验的具体环境。在1楼和3楼分别放置了2对路由器(间隔为10 m)。可以看到路由器的信号随着时间变化在波动。

图5 实验环境

分别在1,2,3层楼进行数据的采集工作。每隔2 m选择一个测试点,在每个测试点记录20个信号值,每次间隔5 s。图6显示了实验的具体数据,X轴为采样时间,单位为s,Y轴为水平距离,单位为m,Z轴为信号强度,单位为dB。虚线和实线分别表示了1楼与3楼在同一水平位置2个路由器的信号强度分布。

图6 楼层实验的信号强度数据

然后使用本文的加权MSD模型来计算具体的加权信号值,并最终得到本文的ΔMSPL值。图7及表1是本文的一些关键数据,包括了ΔMSPL的均值、方差,以及ΔDMSPL。图7(a)、图7(b)、图7(c)中的实线表示了1楼路由器的加权信号强度,虚线表示了3楼路由器的加权信号强度;图7(d)显示了3个楼层的ΔMSPL的分布情况。

图7 加权信号强度及ΔMSPL分布

表1 实验数据分析

4 结束语

本文介绍了一种基于快速部署的室内多楼层定位算法,结合水平方向的定位算法(如三角定位、区块划分算法)能为多层的大楼提供高精度、稳定、便捷的室内定位解决方案。多楼层差分算法的提出弥补了室内定位领域纵向定位上的不足之处,能够极大地减少信号源的部署,同时提高节点的利用率,达到本文快速部署且高精度与可靠性的目标。最后做了一系列仿真实验,并搭建实际的定位系统来验证算法的可靠性。更重要的是,低成本的基础设施与快速部署的特性使本文系统在未来能够有广阔的应用前景。

[1] 李桔鸿.基于Range-based的无线传感器网络定位算法研究与改进[D].成都:西南交通大学,2012.

[2] 史 龙,王福豹,段渭军,等.无线传感器网络Rangefree自身定位机制与算法[J].计算机工程与应用, 2004,40(23):127-130,151.

[3] 田孝华,廖桂生.一种有效减小非视距传播影响的TOA定位方法[J].电子学报,2003,31(9):1429-1432.

[4] 刘 影.基于TDOA的无线传感器网络节点定位技术研究[D].长春:吉林大学,2008.

[5] Niculescu D,Nath B.Ad Hoc Positioning System(APS) Using AOA[C]//Proc.of the 23nd Annual Joint Conference of the IEEE Computer and Communications. [S.l.]:IEEE Press,2003:1734-1743.

[6] 方 震,赵 湛,郭 鹏,等.基于RSSI测距分析[J].传感技术学报,2007,20(11):2526-2530.

[7] Zhong Ziguo,He Tian.Achieving Range-free Localization Beyond Connectivity[C]//Proc.of the 7th ACM Conference on Embedded Networked Sensor Systems. [S.l.]:ACM Press,2009:281-294.

[8] Chintalapudi K,Iyer A P,Padmanabhan V N.Indoor Localization Without the Pain[C]//Proc.of the 16th Annual International Conference on Mobile Computing and Networking.[S.l.]:ACM Press,2010:173-184.

[9] Chen Pengpeng,Zhong Ziguo,He Tian.Bubble Trace: Mobile Target Tracking Under Insufficient Anchor Coverage[C]//Proc.of the 31st International Conference on Distributed Computing Systems.[S.l.]:IEEE Press, 2011:770-779.

[10] Wang He,Sen S,Elogohary A,et al.Unsupervised Indoor Localization[D].Durham,UK:Duke University,2012.

[11] Gibson T B,Jenn D C.Prediction and Measurement of Wall Insertion Loss[J].IEEE Transactions on Antennas and Propagation,1999,47(1):55-57.

[12] Walfisch J,Bertoni H L.A Theoretical Model of UHF Propagation in Urban Environments[J].IEEE Transactions on Antenna and Propagation,1988,36(12):1788-1796.

编辑 任吉慧

Research of Indoor Multi-storey Localization Alogorithm Based on Quick Deployment

YU Min-jie,YI Ping,GUAN Han-nan
(School of Information Security Engineering,Shanghai Jiaotong University,Shanghai 200240,China)

The traditional GPS is hard to do localization in indoor environment due to the complicated walls and obstacles.The mainstream of localization alogorithm is conducted on horizontal direction,and method on vertical direction is still a new topic.This paper presents an on-demand indoor multi-storey localization alogorithm,which can be fingerprint-free and deployed rapidly and on-demand in a multi-storey building.On vertical direction,it proposes Multistorey Differential(MSD)alogorithm,the main idea of which is to differentiate the RSSI from different floors to distinguish the exact floor of test point.It conducts both simulation and practical experiments to prove the accuracy of this alogorithm.

Location Based Service(LBS);indoor localization system;multi-storey localization;Multi-storey Path Loss(MSPL)model;Multi-storey Differential(MSD)alogorithm;quick deployment

1000-3428(2014)09-0023-04

A

TP393.02

10.3969/j.issn.1000-3428.2014.09.005

国家“973”计划基金资助项目(2013CB329603);国家自然科学基金资助项目(61271220,61170164,60932003)。

俞敏杰(1989-),男,硕士研究生,主研方向:无线Mesh网络,实时操作系统,室内定位;易 平,副教授、博士;关汉男,硕士研究生。

2013-10-08

2013-11-10E-mail:ymj1037@sjtu.edu.cn