面向非视距环境的室内定位算法

毛科技,邬锦彬,金洪波,苗春雨,2,夏　明,陈庆章

(1.浙江工业大学计算机科学与技术学院,浙江杭州 310023; 2.浙江师范大学行知学院,浙江金华 321004)



面向非视距环境的室内定位算法

毛科技1,邬锦彬1,金洪波1,苗春雨1,2,夏明1,陈庆章1

(1.浙江工业大学计算机科学与技术学院,浙江杭州 310023; 2.浙江师范大学行知学院,浙江金华 321004)

节点位置信息在无线传感器网络中起着至关重要的作用.大多数定位算法在视距(Line-of-Sight,LOS)环境下能够取得较高的定位精度，然而在非视距(Non-Line-of-Sight,NLOS)环境下，由于障碍物的阻挡，无法取得理想的定位精度.针对室内环境中普遍存在的非视距传播现象，提出了基于RTT(Round Trip Time)和AOA(Angle Of Arrival)混合测距方式的室内定位方法，一种轻量级基于网格的聚类算法(Lightweight Grid-Based Cluster，LGBC)被用来生成移动节点的定位区域.算法不需要获取室内环境的先验信息.仿真结果表明，LGBC算法复杂度低，计算开销小，并且与同类算法相比，定位精度提高约65%.

无线传感器网络；室内定位；非视距环境；聚类

1　引言

近年来，随着WLAN和无线传感器网络的发展普及，室内定位在一些特定场合的实用性和必要性已经日趋显著，其应用前景广阔，研究意义非常大，如大型超市内顾客导航，部署在仓库跟踪物流动态，追踪医院病人的位置信息从而能够及时应对突发事件的发生[1].但是，由于室内障碍物的存在会使信号发生反射、散射，出现多径效应[2](如图1所示)，造成较大的测距误差，许多视距环境下的定位算法无法直接应用到室内定位中.

如何减小多径效应对定位造成的影响是室内定位的研究重点.有两类较为常见的解决方法：(1)通过减小非视距测量误差来得到理想的定位精度；(2)则通过判别出非视距传播信号，并在定位阶段舍弃该信号.神经网络[3]、贝叶斯滤波[4]以及卡尔曼滤波[5,6]等方法被用来减小非视距误差，并取得了良好的效果.但这几种方法均会带来大量的计算.基于泰勒级数展开的加权最小二乘估计算法[7]具有广泛的使用范围，但它需要节点部署环境中误差分布的统计特性作为权值，对不同环境的普适性不强.有的文献基于信号传播特征对无线信道建模或者直接采用已有的信道传播模型，匹配测量数据来进行定位，如文献[8].对于该类算法，建立合适的无线信道模型至关重要.

同时，测距技术是定位系统的基础.常用的测距技术有RSSI[9]、TOA[10]、TDOA[11]、AOA[12]等.每一种测距方法都有其优点及缺陷，单靠一种测距技术来进行定位并不能取得最佳的定位效果.因此，混合测距方法被用来适应更加复杂的定位环境(如室内环境).文献[13]对单一以及混合测距定位方法进行了比较.

针对上述问题，本文提出了基于RTT[14]和AOA混合测距的室内定位方法.通过一种轻量级的网格聚类算法LGBC生成移动节点的定位区域，计算该区域内数据点的平均值求得移动节点的实际坐标.本文的贡献可以归纳为：(1)设计了一种轻量级的网格聚类算法，算法复杂度仅为O(N)，并且与同类算法相比，提高65%左右的定位精度；(2)该室内定位方法不需要获取室内环境先验信息，能够广泛应用于复杂室内环境；(3)LGBC算法可用于集中式节点跟踪或分布式节点自定位.

2　问题描述

首先，通过RTT和AOA混合测距技术，我们能够得到BS与MS之间的飞行时间τ及到达角度φ，如图2所示.根据飞行时间τ，BS与MS之间的距离就可由式(1)确定，其中d表示BS与MS之间的距离，c代表光速.

d=c·τ

(1)

如图2，在二维极坐标下，根据式(2)，我们就可以计算出未知节点MS的坐标.(x,y)表示待定位的MS坐标，称为“估计位置”；(x0,y0)已知，表示BS坐标.

(2)

由于障碍物的存在，使得部分BS与MS存在非视距关系，如图3所示.信号传播受影响导致测量值τ、φ不准确，“估计位置”将会形成如图4的分布.当室内环境越复杂(障碍物阻挡严重)，那么非视距关系BS所占比例也将越大，“估计位置”分布也就越分散；当室内障碍物较少，那么非视距关系BS所占比例越小，MS附近的“估计位置”分布也就相对集中.因此，我们的研究目标为设计一种聚类算法来找到估计位置相对集中的区域，并对该区域内数据进行适当处理，从而实现定位.

3　LGBC算法

LGBC算法的具体描述如下.

3.1网格单元

定义2“估计位置”与网格单元的关系：对于任意“估计位置”坐标P(x,y)，我们可以通过式(3)来确定它属于哪个网格单元.此时，记作P(x,y)∈Grc.

(3)

定义3邻居网格单元：一个网格单元的邻居网格单元是指与该单元有公共边或公共点的网格单元.二维坐标中，根据网格单元所处位置的不同，其邻居数可能为3个、5个或8个.

3.2矩阵压缩

在算法执行过程中，网格单元信息可以用二维矩阵表示，如图5(a)，矩阵的行列号对应网格单元Grc的行下标和列下标r、c，矩阵的值表示票数V.假如一个房间大小为30m×20m，网格边长设为0.5m，那么就会产生一个60×40的矩阵.很显然，该矩阵将会是一个稀疏矩阵.如果不对它做任何处理，必然会增加数据的存储空间以及计算开销，对于“票数”为0的网格单元进行操作是没有意义的.为此，本文用三元组顺序表压缩稀疏矩阵，稀疏矩阵中的每一个非零元素由一个三元组(r,c,arc)唯一确定，矩阵中所有非零元素存放在由三元组组成的数组中，如图5(b)所示，我们称之为gridList.

3.3算法实现

步骤2投票.遍历估计位置集合P，将每个坐标映射到对应的网格单元.如果gridList中已经存在该网格单元，则将刚网格所对应的票数V加1；否则，将该网格单元添加到gridList，并将票数V置1.

(4)

3.4扩展到三维环境

将算法扩展到三维环境，需要获取MS的高度数据.一方面，我们可以用气压计[15]测量MS所处的高度；另一方面，文献[16]基于混合天线阵列，提出了一种高精度的AOA测量算法，适用于三维环境.因此在三维环境下，我们能够通过该算法获取BS与MS之间的仰角θ，如图6所示.此时，未知节点MS的三维坐标可由式(5)得到.其中(x,y,z)表示待定位的MS坐标；(x0,y0,z0)已知，表示BS坐标.

(5)

在计算得到所有的“估计位置”坐标后，首先将所有的三维坐标投影到二维坐标系，然后利用LGBC算法分别对XY平面、YZ平面以及XZ平面上的坐标点进行聚类.最终根据式(6)，即可获得未知节点MS的坐标.

(6)

可以看出，三维环境下的算法仍然以二维环境为基础，因此，在仿真实验中，我们将针对二维环境进行实验分析.

4　仿真结果

LGBC算法的时间复杂度在最坏情况下为O(M)，其中M=N·n，即数据点个数总和.

(7)

时间τ′以及角度φ′的真实值由式(7)所得，误差来源主要有测距误差(视距误差)及非视距误差.由于非视距误差可能符合指数、均匀以及高斯分布[17]，因此，仿真将在误差符合不同分布的情况下对算法的可行性、定位精度进行验证，具体仿真参数如表1所示.

表1　仿真参数

(8)

4.1视距关系BS数目

在本小节的实验中，我们首先假定无论在哪个位置，至少有一个BS与MS存在视距关系，进而探究视距BS数目Bn对定位造成的影响.当室内环境足够复杂导致视距关系BS数目为0时，我们将对算法的上界进行讨论.

仿真实验中，设置Bn从1变化到20，间隔为1，仿真结果如图7.从图中可以看到，定位误差e随着Bn的递增而逐渐下降，并且在区间[1,4]之间下降速度较快，在Bn=12之后趋于稳定.

然而，在一些复杂的室内环境中，我们无法保证MS能够在任何位置都至少与一个BS存在视距关系.为此，我们通过实验对算法的上界进行了讨论.在仿真实验中，设置视距关系BS数目Bn为0，通过改变平均测距误差(从1m逐渐递增到100m，间隔为1m)来探究定位误差的变化趋势.从仿真结果图8中我们可以看到，随着平均测距误差的增加，定位误差逐渐递增并最终趋于稳定.在高斯分布及均匀分布下，LGBC算法的上界为3m左右；在指数分布下，LGBC算法的上界为2.5m左右.

在后面的仿真中，设置视距关系BS数目的默认值为4.

4.2网格边长l

选取适当的网格边长l对于LGBC算法至关重要.如果将网格划分太小，则可能造成一个估计位置落在一个网格单元；如果将网格划分地太大，则无法显著地区分密集区域及稀疏区域.这两种情况均会造成较大的定位误差.

在本节实验中，设置网格边长l从0.1m递增到1m，间隔为0.1m.从仿真结果图9(a)中，可以看出不管在什么分布的情况下，定位误差呈上升趋势.网格边长l为0.1m时取得最佳的定位效果.

为了探究网格边长小于0.1m时定位误差的变化趋势，再次设置网格边长l从0.01m递增到0.1m，间隔为0.01m，其仿真结果如图9(b)所示.再次证明了在当前仿真环境下，最佳的网格边长为0.1m.

将算法应用到一个新环境时，如何确定该环境下的最佳网格边长l也是一个值得探究的问题.为此，我们设计了一组仿真实验来寻找最佳网格边长与环境因素之间的关系.如果以高斯分布为例，那么平均测距误差u就可以用来表示环境的影响因子.

实验中，设置网格边长从0.05m递增到3m，间隔为0.05m；平均测距误差u从1m递增到100m，间隔为1m.计算在不同网格边长以及误差均值下的定位误差，得到如图10所示的结果.图中的仿真结果和我们的预期结果相似：当室内环境中障碍物遮挡较轻，也就是平均测距误差u较小时，网格边长越大，定位误差也就越大；然而，当室内环境中障碍物遮挡严重，即平均测距误差u较大时，较小的网格边长对定位误差影响并不是非常大.这是由于本文提出的基于RTT和AOA的混合测距方法，理论上只需要有一个视距BS就可以定位，定位成功率高，并且LGBC算法对于坐标点密集区域较为敏感，较小的网格边长l才能更加准确得到坐标点密集区域.

对上述仿真结果做进一步分析，我们得到了如表2所示的结果.从表中我们可以看到，当最佳网格边长l∈(0m,0.1m]∪(0.1m,0.2m]，其所占比例为92%，两个区间平均误差相近.因此，我们认为在新环境下，为了计算及表示方便，最佳网格边长默认可取0.1m.

表2　仿真结果

4.3算法比较

文献[18]将聚类方法引用到室内定位问题中，提出了一种基于坐标聚类的室内定位算法，这里暂时称其为CCA算法.CCA算法不需要提前获取环境信息，并且没有使用先验知识减小多径效应带来的误差，但仍能获得0.4m以内的定位精度，为解决室内定位非视距问题提供了新的思路.

LGBC算法与CCA算法在默认的仿真环境下进行实验，比较在不同分布情况下，视距关系BS数目对各自的定位误差所造成的影响.从仿真结果图11中可以直观地看出，LGBC算法的精度在不同的分布下均优于CCA算法.根据仿真结果的统计数据，高斯分布下LGBC算法的定位精度比CCA算法提高55%，均匀分布下提高约61%，指数分布下提高79%，整体提高65%左右.

5　结语

非视距问题一直都是室内定位的研究热点之一.现有的大部分室内定位算法都存在着计算开销高，或是需要获取环境信息等缺陷.本文提出的室内定位方法不需要室内环境的先验信息，其关键部分LGBC是一个线性复杂度算法，计算开销小，在视距BS所占比例较小时，也能取得较高的定位精度.仿真结果表明，该定位方法在大部分情况下均能取得较好的定位效果，能够应用于不同的室内环境，并且在精度及计算速度上都明显优于同类算法，适用于集中式节点跟踪或分布式节点自定位.

未来的工作方向主要将集中在以下两个方面：(1)加入一定的约束条件，将算法应用于移动节点的快速定位；(2)在真实室内环境中验证算法的可行性.

[1]Nasrullah Pirzada,M Yunus Nayan,Fazli Subhan,et al.Device-free localization technique for indoor detection and tracking of human body:A survey[A].International Conference on Innovation,Management and Technology Research (ICIMTR)[C].Malaysia:Procedia-Social and Behavioral Sciences,2014,129:422-429.

[2]C A Balanis.Antenna Theory:Analysis and Design[M].New Jersey:John Wiley & Sons,2005.

[3]Chi Sing Leung,John Sum,Hing Cheung So,et al.Lagrange programming neural networks for time-of-arrival-based source localization[J].Neural Computing and Applications,2014,24(1):109-116.

[4]Alexander S.Volkov.Accuracy bounds of non-Gaussian Bayesian tracking in a NLOS environment[J].Signal Processing,2015,108(5):498-508.

[5]Hammes U,Wolsztynski E,Zoubir A M.Robust tracking and geolocation for wireless networks in NLOS environments[J].IEEE Journal of Selected Topics in Signal Processing,2009,3(5):389-400.

[6]Yunzhou Zhang,Wenyan Fu,Dongfei Wei,et al.Moving target localization in indoor wireless sensor networks mixed with LOS/NLOS situations[J].EURASIP Journal on Wireless Communications and Networking,2013,2013(1):291.

[7]Zhang Y,Ren J,Chen W.A ToA-based location algorithm reducing the NLoS error under location-aware networks[A].International Conference on Wireless Communications,Networking and Mobile Computing (WiCOM)[C].China:IEEE,2011.1-4.

[8]Mohamed Zhaounia,Mohamed Adnan Landolsi,Ridha Bouallegue.Mobile localization under non-line-of-sight conditions using scattering information[J].International Journal of Wireless Information Networks,2010,17(1):1-10.

[9]Huanhuan Wang,Jianchen Wan,Ruyou Liu.A novel ranging method based on RSSI[J].Energy Procedia,2011,12(39):230-235.

[10]Huang J,Xue Y,Yang L.An efficient closed-form solution for joint synchronization and localization using TOA[J].Future Generation Computer Systems,2013,29(3):776-781.

[11]Johannes Wendeberg,Fabian Høflinger,Christian Schindelhauer,et al.Calibration-free TDOA self-localisation[J].Journal of Location Based Services,2013,7(2):121-144.

[12]Shahriar Shirvani-Moghaddam,Farida Akbari.A novel ULA-based geometry for improving AOA estimation[J].EURASIP Journal on Advances in Signal Processing,2011,2011(1):1-11.

[13]Alejandro De Gante,Mario Siller.A survey of hybrid schemes for location estimation in wireless sensor networks[J].Procedia Technology,2013,7(4):377-383.

[14]Yi H C,Kim H J,Kim Y J,et al.RTT estimation method in WSN[A].International Conference on Information and Computer Networks (ICICN 2012)[C].IACSIT Press,2012.17-21.

[15]Li B,Harvey B,Gallagher T.Using barometers to determine the height for indoor positioning[A].International Conference on Indoor Positioning and Indoor Navigation (IPIN)[C].France:IEEE,2013.1-7.

[16]Chuang S F,Wu W R,Liu Y T.High-resolution AoA estimation for hybrid antenna arrays[J].Antennas and Propagation,IEEE Transactions on,2015,63(7):2955-2968.

[17]刘琚,李静.一种在非视距环境中的TDOA/AOA混合定位方法[J].通信学报,2005,26(05):63-68.

LIU Ju,LI Jing.TDOA/AOA hybrid wireless location method in NLOS situation[J].Journal on Communications,2005,26(5):63-68.(in Chinese)

[18]M Dakkak,A Nakib,B Daachi,et al.Indoor localization method based on RTT and AOA using coordinates clustering[J].Computer Networks,2011,2011(55):1794-1803.

毛科技(通信作者)男，1979年生于浙江省诸暨市.浙江工业大学计算机科学与技术学院教师，博士，主要研究方向为无线传感器网络.

E-mail:maokeji@zjut.edu.cn

邬锦彬男，1991年生于浙江省宁波市.浙江工业大学硕士研究生在读，主要研究方向为无线传感器网络节点定位技术.

E-mail:wujinbin91@foxmail.com

Indoor Localization Algorithm for NLOS Environment

MAO Ke-ji1,WU Jin-bin1,JIN Hong-bo1,MIAO Chun-yu1,2,XIA Ming1,CHEN Qing-zhang1

(1.CollegeofComputerScienceandTechnology,ZhejiangUniversityofTechnology,Hangzhou,Zhejiang310023,China; 2.CollegeofXingzhi,ZhejiangNormalUniversity,Jinhua,Zhejiang321004,China)

Location of sensor plays a pivot role in WSNs.Most of the localization algorithms can achieve extremely high positioning accuracy in line of sight (LOS) environment.However,they are unable to obtain ideal accuracy due to the obstacles in non-line of sight (NLOS) environment.In order to solve the NLOS propagation problem in indoor environment,we propose an indoor localization method based on RTT and AOA using a lightweight grid-based clustering (LGBC) algorithm.The LGBC algorithm does not depend on any prior information of indoor environment and possesses significant flexibility.The simulation results show that LGBC algorithm has low time complexity and small computational overhead.Furthermore,it outperforms the other method by about 65 percent in terms of localization accuracy.

WSNs(wireless sensor networks);indoor localization;NLOS(non line of sight) environment;clustering

2015-06-01;

2015-12-07;责任编辑:马兰英

国家自然科学基金(No.61379023,No.61401397);浙江省自然科学基金(No.LY14F020020);浙江省公益性技术应用研究计划项目(No.2015C31066);浙江省计算机科学与技术重中之重学科(浙江师范大学)资助课题(No.ZC323014074)

TN915.9

A

0372-2112 (2016)05-1174-06

电子学报URL:http://www.ejournal.org.cn10.3969/j.issn.0372-2112.2016.05.023