NLOS无线环境中运用最优化原理的定位算法

，， ，,

(1.浙江工业大学 信息工程学院，浙江 杭州 310023；2.东南大学 移动通信国家重点实验室，江苏 南京 210096)

近几年来，无线定位技术已经成为了物联网中一项非常热门的研究内容，并且得到了较大的发展[1].现有定位技术中主要针对测量距离和测量角度这两类参量展开研究[2-3]：包括到达时间(Time of arrival, TOA)[4]、到达时间差(Time difference of arrival, TDOA)[5-6]、接收信号强度(Received signal strength, RSS)[7]、到达角(Angle of arrival, AOA)以及它们的混合参量TOA/AOA和TDOA/AOA等[8-9].但是无论定位算法采用何种参量，它都会受到两种误差影响.其一是测量误差，一般假设其为具有较小标准差的零均值高斯变量[10]，在传统的视距传输(LOS)定位中，这是主要的误差源.而对于城市无线通信，信号传播过程中折射和反射等现象引起的非视距(Non-line of sight, NLOS)误差具有更大的数值，并已成为无线定位最主要的误差.在实际的GSM网络中，NLOS误差可以达到500～700 m[11]，同时其统计分布无法进行精确建模，从而要在定位中消除NLOS误差极为困难.综上，NLOS误差的抑制已经成为无线定位算法实用化的关键.

目前，主要存在三类非视距误差抑制的定位算法.第一类是试图对非视距误差进行精确建模，然后根据所建模型来估计移动终端(MS)的位置[12-13].由于实际中很难得到一个精确的非视距模型用于描述复杂多变的传输环境，这一类算法难以广泛应用.第二类算法认为LOS传输的基站有别于NLOS传输的基站，因而可以据此将NLOS基站识别出来，最后只利用LOS基站进行位置估计[14-15].此类算法需要实际环境中存在一定数目的LOS基站，而且NLOS基站识别的虚警率无法控制，因此定位精度难以确保.第三类算法尝试对测量距离或者中间估计量进行加权，权值来源于基站和终端之间几何关系以及代数关系.该类算法最典型的就是以残差为代价函数，以真实距离和测量距离之间的关系为约束条件，建立最优化问题，终端的位置估计可以通过解决该问题来获得[16-18].这一类算法的优点在于无论MS处于何种环境，总是可以将其位置估计出来，但是缺点也是显然的，它的估计精度并不是非常高.笔者选择第三类方法作为研究方向，为此从传统的LLOP算法出发，通过模型转化将它修正为一个二次规划最优化问题.其中最优化的目标函数定义为距离残差，而约束条件通过真实距离和测量距离之间的关系以及真实位置和可行域之间的关系来确定，最终通过标准的二次规划实现移动终端的位置估计，这一过程区别于传统的定位算法，计算机仿真表明所提出的算法在NLOS环境下明显优于其它定位算法.

1 LLOP定位原理

LLOP定位算法利用测距为参数建立一系列的方程组[19]，其几何意义就是求得以各个基站为圆心，以测距为半径的几个圆的两两相交线，所有相交线的交点就是MS的位置，如图1虚线所示.

图1 LLOP定位原理图

图1中假设(x,y)为待估的MS位置，(Xi,Yi)为已知的第i个基站坐标(基站数量为M个)，则MS和第i个基站之间的距离为

(1)

对式(1)两边分别进行平方，易得

(2)

(3)

式(3)现在仅有M-1条方程.进一步把式(3)改写成矩阵形式，可以得到

Y=AX

(4)

其中

这里X代表MS的真实位置信息，其估计值可以利用最小二乘(Least square,LS)算法[20-21]求得

(5)

2 运用最优化理论的抗NLOS定位算法

2.1 目标函数

在实际传播环境中，NLOS的存在会使得距离的测量要远远大于真实的距离，假设测量距离为di，那么它和ri之间的关系为

ri=αidi

(6)

其中αi为处于0～1之间的某个数.如果把式(6)代入到式(3)中，就能够得到

(7)

同样，可以把式(7)转变成矩阵形式

Y1Y2=AX

(8)

其中

显然如果αi的取值能够通过某种方式获得，那么就可以得到X的LS解为

(9)

根据式(9)，定位精度就取决于能否获得合适的αi取值，这可以通过解最优化问题实现.首先我们定义最优化的目标函数为

(10)

(11)

其中K=[K1-K2,K1-K3,…,K1-KM]T.

2.2 约束条件

约束条件就是目标参数需要遵循的几种规则，而最优化算法就是在这些符合约束条件的可选点中找出使目标函数达到预期值的最优解.所提出算法的约束条件主要有两种，第一种可以根据前人文献[16]的参量取值界限思想推广得到.首先定义向量V的下限Vmin

(12)

图2 基站-移动台的几何拓扑

第二个约束条件可以从图2中观察得到：由于在NLOS环境中，MS和BS之间的距离必然小于测量距离，因此MS必然位于几个圆的公共区域，我们可以称MS可能出现的区域为可行域(Feasible region,FS)，即图中A，B，C，D几个点包围的弧形区域，那么第二个约束条件可以表示为

MS坐标∈可行域

(13)

基于可行域的特性，可以把此约束条件重写成

(14)

其中

2.3 最优化问题

根据2.1和2.2小节的分析，我们可以把NLOS环境中的权值搜索问题转变为解一个最优化问题，该最优化问题如下：

(15)

式(15)可以用标准二次规划算法[22]求解，在得到向量V的最优解之后，将其代入到式(9)就能够得到MS的最优位置估计.

3 仿真分析

基于上述仿真参数，所提出的算法将和TDOA两次ML算法(TSML)[23]、LLOP算法以及CLS算法[24]进行比较，仿真结果中的nBS指参与定位的基站为n个.每个仿真独立运行1 000次，所有的仿真均在MATLAB 7.0下完成.

3.1 NLOS误差对定位精度的影响

由于MAX的大小必然影响各定位算法的精度，因此将测试NLOS误差极限值MAX的变化对各算法的影响.假设MAX的大小为100～600 m之间，间隔为100 m，基站数目为5个.

图3 NLOS对各算法RMSE的影响

图3给出了各个算法均方根误差(Root mean square error, RMSE)的对比，可以发现：所有算法的精度都随着NLOS误差的MAX变大而降低，而与笔者算法相比TSML，LLOP和CLS算法，精度的下降更缓慢.可见所提出算法比其他算法稳定.另外，当NLOS误差的MAX为180 m时，所提出算法的精度要略低于CLS算法，而在其他情况下，该算法的精度都是最高的.

3.2 基站数目对定位精度的影响

假设参与定位的基站分别有3，4，5个，MAX的值为400 m，这里各算法的精度将以概率的累积分布函数(Cumulative distribution function, CDF)表示，结果如图4所示.

图4 基站数目对各算法CDF的影响

从图4的概率CDF结果可以看出:所提出算法总体而言是要优于其他算法，尤其参与定位的基站数目较多时，而BS数目的增加对于其他算法的性能改善明显小于笔者算法.

3.3 LOS-BS对定位精度的影响

显然LOS基站的存在与否也会对定位精度产生影响，因此非常有必要对此进行仿真分析.假设基站数目为5，LOS基站数目分别为0，1，2个，MAX为400 m.仿真结果如图5所示.

图5 LOS基站数目对各算法精度的影响

从图5可以看到：如果LOS-BS数目非0，所提出算法的精度可以明显提高，且在对比的算法中表现最佳，特别是把LOS-BS数目为2时的情况和不存在LOS-BS数目的时候进行比较，就能看出它们的显著差别.因而可以预见，当存在更多LOS-BS时，所提出算法的精度将变得更高.而对于另外几种传统算法而言，LOS-BS的存在对定位精度的改善十分有限.

综上所述，在定位精度上，所提出算法要优于传统的定位算法.而且基站数目的增加会使得该算法的精度显著上升.同时LOS基站的存在会使可行域的范围缩小，还会使算法的定位精度进一步上升.

5 结 论

非视距误差是无线定位研究中的一个难点，它的存在会显著降低传统算法的定位精度，因而必须对其影响进行抑制甚至移除.在对传统NLOS抑制算法的研究基础上提出了一种新型的基于最优化理论的NLOS抑制定位算法，该算法通过把LLOP定位模型转换为最优权值的搜索问题，进而用二次规划解决这一最优化问题，从而显著改善了定位性能，在仿真对比中优于其他算法.另外BS数目增加或者存在LOS-BS，笔者算法的定位精度将进一步提高，而传统算法的精度则没有明显变化.

本文得到了东南大学移动通信国家重点实验室开放课题(2010D06)的资助.

参考文献：

[1]吕彩忠,李炜,廖小辉.GPS测量在公路控制网建设中的应用[J].浙江工业大学学报,2012,40(2):178-182.

[2]XU E, DING Z, DASGUPTA S. Source localization in wireless sensor networks from signal time-of-arrival measurements[J]. IEEE Transactions on Signal Processing,2011,59(6):2887-2897.

[3]CAFFERY J J, STUBER G L. Subscriber location in CDMA cellular networks[J]. IEEE Trans Veh Tech,1998,47(2):406-416.

[4]CHAN Y T, HANG Y C, CHINH P C. Exact and approximate maximum likelihood localization algorithms[J]. IEEE Transactions on Vehicular Technology,2006,55(1):10-16.

[5]ZHANG H, YU M, CUI X, GULLIVER T A. An improved Taylor series based location algorithm for IEEE 802.15.4a channels[C]//2011 IEEE Pacific Rim Conference on Communications, Computers and Signal Processing. Victoria, BC, Canada: IEEE,2011:499-503.

[6]SMITH J O. Closed-form least-squares source location estimation from range-difference measurements[J]. IEEE Transactions on Acoustics Speech and Signal Processing,1987,25(8):1223-1225.

[7]YAN Y. Efficient convex optimization method for underwater passive source localization based on RSS with WSN[C]//2012 IEEE International Conference on Signal Processing, Communication and Computing. Hongkong: IEEE,2012:171-174.

[8]LEE Y S. A study on the performance of wireless localization system based on AOA in WSN environment[C] //2011 Third International Conference on Intelligent Networking and Collaborative Systems. Fukuoka, Japan: IEEE,2011:184-187.

[9]ZHANG V Y, WONG A K, WOO K T, et al. Hybrid TOA/AOA-based mobile localization with and without tracking in CDMA cellular networks[C]//2010 IEEE Wireless Communications and Networking Conference. Sydney, Australia: IEEE,2010:1-6.

[10]CHAN Y T, TSUI W Y, SO H C, et al. Time-of-arrival based localization under NLOS conditions[J]. IEEE Transactions on Vehicular Technology,2006,55(1):17-24.

[11]SILVENTOINEN M, RANRALAINEN T. Mobile station emergency locating in GSM [C] // 1996 IEEE International Conference on Personal Wireless Communication. New Delhi, India: IEEE,1996:232-238.

[12]AL-JAZZAR S, CAFFERY J J, YOU H R. A scattering model based approach to NLOS mitigation in TOA location systems[C]// 2002 IEEE Vehicular Technology Conference, Birmingham, UK: IEEE,2002:861-865.

[13]AL-JAZZAR S, CAFFERY J J. ML and Bayesian TOA location estimators for NLOS environments[C] // 2002 IEEE Vehicular Technology Conference. Birmingham, UK: IEEE,2002:856-860.

[14]GUVENC I, CHONG C C, WANTANABLE F, INAMURA H. NLOS identification and weighted least squares localization for UWB systems using multipath channel statistics[J]. EURASIP Journal on Advances in Signal Processing,2008,36(1):1-14.

[15]CONG L, ZHUANG W H. Non-line-of-sight error mitigation in mobile location[J]. IEEE Transaction on Wireless Communications,2004,4(2):560-573.

[16]VENKATRAMAN S, CAFFERY J J, YOU H R. A novel TOA location algorithm using LOS range estimation for NLOS environments[J]. IEEE Transaction on Vehicular Technology,2004,53(5):1515-1524.

[17]KHAJEHNOURI N, SAYED A H. A non-line-of-sight equalization scheme for wireless cellular location[C] // 2003 IEEE International Conference on Acoustics, Speech and Signal Processing. Hongkong: IEEE,2003:549-552.

[18]CHEN P P, A non-line-of-sight error mitigation algorithm in location estimation[C]//1999 IEEE Wireless Communications and Networking Conference. New Orleans, LA, USA: IEEE,1999:316-320.

[19]CAFFERY J J. A new approach to the geometry of TOA location[C]//2000 IEEE Vehicular Technology Conference. Boston, Ma USA: IEEE,2000:1943-1949.

[20]王理同.带随机线性约束的最小二乘估计的相对效率[J].浙江工业大学学报，2012,40(3):352-354.

[21]许晓辉,王炳忠,刘志.基于最小二乘法的二维条码图像倾斜校正方法[J].浙江工业大学学报，2008,36(3):250-253.

[22]龚纯,王正林.精通MATLAB最优化计算[M].1版.北京：电子工业出版社，2009.

[23]CHAN Y T, HO K. A simple and efficient estimator for hyperbolic location [J]. IEEE Transaction on Signal Processing,1994,42(8):1905-1915.

[24]WANG X, WANG Z, ODEA B. TOA-based location algorithm reducing the errors due to non-line-of-sight propagation [J]. IEEE Transactions on Vehicular Technology,2003,52(1):112-116.